데이터 스트리밍에 사용할 데이터 구조

Question

서버가 지난 1 시간 동안 처리 된 요청 수를 알려줄 수있는 어떤 데이터 구조를 사용해야합니까?

예를 들어, 10:20:23에서 몇 개의 요청이 처리되었는지 묻습니다. 9시 20 분 23 초에서 지금까지 총계를 말해야합니다. 마찬가지로 10시에 9 시부 터 총계를 말해야합니다.

Answer 1

하나의 옵션은 시간순으로 정렬 된 표준 동적 배열에 모든 데이터를 저장하는 것입니다. 들어오는 요청이있을 때마다 배열의 끝에 추가합니다.

지난 1 시간 동안 요청 된 요청 수를 조회하려면 해당 배열에서 이진 검색을 수행하여 해당 시간에 발생한 첫 번째 요청을 찾습니다. 이 배열 요소의 인덱스를 총 요소 수와 비교하면 해당 시간 창에서 총 요청 수가 제공됩니다.

배열이 너무 커지지 않도록하려면 배열을 성장하는 링 버퍼로 처리하는 것이 좋습니다. 배열의 공간이 부족할 때마다 지난 1 시간 내에 발생한 배열의 첫 번째 요소에 대한 이진 검색을 수행하십시오. 그 전에 모든 요소는 버려 질 수 있습니다. 배열을 링 버퍼로 저장하면 시작 위치를 조정하여 버퍼에서 논리적으로 제거하기 만하면 O (1) 시간 내에 모든 요소를 ​​효과적으로 삭제할 수 있습니다. 여전히 공간이 더 필요하다면, 링 버퍼의 크기를 두 배로 늘리고 이전 요소를 복사 할 수 있습니다. 이전 요소 (예 : 75 %)를 삭제 한 후 버퍼의 일정 부분 이상을 채우는 경우 항상 모든 내용을 복사하는 정책을 적용하면 삽입 당 상각 된 O (1) 시간이 필요합니다.

간단히 말해, 지난 한 시간 동안의 요청 수를 O (1) 삽입 및 O (log n) 최악의 경우 조회합니다.

희망이 도움이됩니다.