실시간 데이터 캡처 백분위수

https://stackoverflow.com/questions/1248815

12-09-2019
|

문제

실시간 데이터 캡처를 위한 백분위수를 결정하는 알고리즘을 찾고 있습니다.

예를 들어, 서버 애플리케이션 개발을 생각해 보세요.

서버의 응답 시간은 다음과 같습니다.17밀리초 33밀리초 52밀리초 60밀리초 55밀리초 등.

90번째 백분위수 응답 시간, 80번째 백분위수 응답 시간 등을 보고하는 것이 유용합니다.

순진한 알고리즘은 각 응답 시간을 목록에 삽입하는 것입니다.통계가 요청되면 목록을 정렬하고 적절한 위치의 값을 가져옵니다.

메모리 사용량은 요청 수에 따라 선형적으로 확장됩니다.

제한된 메모리 사용량을 고려하여 "대략적인" 백분위수 통계를 생성하는 알고리즘이 있습니까?예를 들어, 수백만 개의 요청을 처리하지만 백분위수 추적을 위해 1KB의 메모리만 사용하는 방식으로 이 문제를 해결하고 싶다고 가정해 보겠습니다. 모든 요청에 적용됩니다).

또한 분포에 대한 사전 지식이 없어야 합니다.예를 들어, 버킷 범위를 미리 지정하고 싶지 않습니다.

해결책

나는 이 문제에 대한 좋은 근사 알고리즘이 많이 있다고 믿습니다.좋은 첫 번째 접근 방식은 단순히 고정 크기 배열(예: 1K 상당의 데이터)을 사용하는 것입니다.일부 확률을 수정합니다 p.각 요청에 대해 확률 p를 사용하여 해당 응답 시간을 배열에 씁니다(가장 오래된 시간을 대체).배열은 라이브 스트림의 서브샘플링이고 서브샘플링은 분포를 유지하므로 해당 배열에 대한 통계를 수행하면 전체 라이브 스트림의 통계에 대한 대략적인 결과를 얻을 수 있습니다.

이 접근 방식에는 다음과 같은 몇 가지 장점이 있습니다.선험적 정보가 필요하지 않으며 코딩도 쉽습니다.특정 서버에 대해 버퍼 증가가 응답에 미미한 영향을 미치는 지점을 신속하고 실험적으로 결정할 수 있습니다.이는 근사치가 충분히 정확한 지점입니다.

충분히 정확한 통계를 제공하기 위해 너무 많은 메모리가 필요하다고 판단되면 더 자세히 조사해야 합니다.좋은 키워드는 다음과 같습니다."스트림 컴퓨팅", "스트림 통계" 및 물론 "백분위수"."화와 저주"의 접근 방식을 시도해 볼 수도 있습니다.

다른 팁

점점 더 많은 데이터를 얻을 때 메모리 사용량을 일정하게 유지하려면 다음을 수행해야 합니다. 다시 샘플링하다 그 데이터가 어떻게든.이는 일종의 적용을 해야 함을 의미합니다. 리비닝 계획.리비닝을 시작하기 전에 일정량의 원시 입력을 얻을 때까지 기다릴 수 있지만 완전히 피할 수는 없습니다.

따라서 귀하의 질문은 "내 데이터를 동적으로 비닝하는 가장 좋은 방법은 무엇입니까?"를 묻는 것입니다.많은 접근 방식이 있지만, 얻을 수 있는 값의 범위나 분포에 대한 가정을 최소화하려는 경우 간단한 접근 방식은 고정된 크기의 버킷에 대한 평균을 계산하는 것입니다. 케이, 대수적으로 분포된 너비를 갖습니다.예를 들어, 한 번에 1000개의 값을 메모리에 저장하고 싶다고 가정해 보겠습니다.사이즈 선택 케이, 100이라고 해 보세요.최소 해상도(1ms)를 선택하세요.그 다음에

첫 번째 버킷은 0-1ms(너비=1ms) 사이의 값을 처리합니다.
두 번째 버킷:1-3ms(w=2ms)
세 번째 버킷:3-7ms(w=4ms)
네 번째 버킷:7-15ms(w=8ms)
...
열 번째 버킷:511-1023ms(w=512ms)

이 유형의 로그 스케일링된 접근 방식은 다음에서 사용되는 청킹 시스템과 유사합니다. 해시 테이블 알고리즘, 일부 파일 시스템 및 메모리 할당 알고리즘에서 사용됩니다.데이터의 동적 범위가 클 때 잘 작동합니다.

새로운 값이 들어오면 요구 사항에 따라 리샘플링 방법을 선택할 수 있습니다.예를 들어 이동 평균, 선입선출, 또는 다른 좀 더 정교한 방법을 사용할 수 있습니다.참조 카뎀리아 한 가지 접근 방식에 대한 알고리즘( 비트토렌트).

궁극적으로 리비닝을 수행하면 일부 정보가 손실됩니다.비닝에 대한 선택에 따라 손실되는 정보의 세부 사항이 결정됩니다.이를 달리 표현하면, 일정한 크기의 메모리 저장소는 두 메모리 사이의 균형을 의미한다는 것입니다. 동적 범위 그리고 샘플링 충실도;절충 방법은 귀하에게 달려 있지만 다른 샘플링 문제와 마찬가지로 이 기본 사실을 피할 수는 없습니다.

장점과 단점에 정말로 관심이 있다면 이 포럼의 답변만으로는 충분하지 않을 것입니다.당신은 조사해야 샘플링 이론.이 주제에 관한 엄청난 양의 연구가 가능합니다.

그만한 가치가 있다고 생각하기 때문에 서버 시간은 상대적으로 작은 동적 범위를 가지므로 공통 값을 더 많이 샘플링할 수 있도록 보다 완화된 크기 조정을 하면 더 정확한 결과를 제공할 수 있습니다.

편집하다:귀하의 의견에 답변하기 위해 다음은 간단한 비닝 알고리즘의 예입니다.

10개의 저장소에 1000개의 값을 저장합니다.따라서 각 bin에는 100개의 값이 저장됩니다.각 bin이 동적 배열(Perl 또는 Python 용어로 '목록')로 구현된다고 가정합니다.
새로운 값이 들어오면:
- 선택한 저장소 제한에 따라 어떤 저장소에 저장해야 하는지 결정하세요.
- 저장소가 가득 차지 않은 경우 저장소 목록에 값을 추가합니다.
- 저장소가 가득 차면 저장소 목록 상단의 값을 제거하고 저장소 목록 하단에 새 값을 추가합니다.이는 시간이 지남에 따라 오래된 값이 폐기된다는 것을 의미합니다.
90번째 백분위수를 찾으려면 Bin 10을 정렬하세요.90번째 백분위수는 정렬된 목록(요소 900/1000)의 첫 번째 값입니다.

이전 값을 버리고 싶지 않다면 대신 사용할 대체 구성표를 구현할 수 있습니다.예를 들어, 저장소가 가득 차면(제 예에서는 값이 100개에 도달) 가장 오래된 50개 요소의 평균을 구할 수 있습니다(예:목록의 처음 50개), 해당 요소를 삭제한 다음 새 평균 요소를 빈에 추가하면 이제 49개의 새 값을 담을 수 있는 공간이 있는 51개 요소의 빈이 남습니다.이것은 리비닝의 간단한 예입니다.

리비닝의 또 다른 예는 다음과 같습니다. 다운샘플링;예를 들어, 정렬된 목록에서 매 5번째 값을 버립니다.

이 구체적인 예가 도움이 되기를 바랍니다.핵심 포인트는 지속적인 메모리 노화 알고리즘을 달성하는 방법이 많다는 것입니다.귀하의 요구 사항에 따라 무엇이 만족스러운지는 귀하만이 결정할 수 있습니다.

나는 방금 논문을 발표했습니다. 이 주제에 대한 블로그 게시물.기본 아이디어는 "95%의 응답에 500ms-600ms 이하가 소요됩니다"(500ms-600ms의 모든 정확한 백분위수에 대해)를 위해 정확한 계산에 대한 요구 사항을 줄이는 것입니다.

임의 크기의 버킷을 원하는 만큼 사용할 수 있습니다(예:0ms-50ms,50ms-100ms,...귀하의 사용 사례에 맞는 모든 것).일반적으로 문제가 되지 않지만 특정 응답 시간을 초과하는 모든 요청(예:마지막 버킷(예: 웹 애플리케이션의 경우 5초)> 5000ms).

새로 캡처된 각 응답 시간에 대해 해당하는 버킷에 대한 카운터를 늘리기만 하면 됩니다.n번째 백분위수를 추정하려면 합계가 전체의 n%를 초과할 때까지 카운터를 합산하면 됩니다.

이 접근 방식에는 버킷당 8바이트만 필요하므로 1K 메모리로 128개의 버킷을 추적할 수 있습니다.50ms 단위로 웹 애플리케이션의 응답 시간을 분석하는 데 충분합니다.

예를 들면 다음과 같습니다. 구글 차트 1시간 동안 캡처된 데이터에서 생성했습니다(버킷당 200ms의 60개 카운터 사용).

멋지지 않나요?:) 내 블로그에서 자세한 내용을 읽어보세요..

(이 질문을 받은 지 꽤 시간이 지났지만, 관련 연구 논문 몇 가지를 언급하고 싶습니다.)

지난 몇 년 동안 데이터 스트림의 대략적인 백분위수에 대한 상당한 양의 연구가 있었습니다.전체 알고리즘 정의가 포함된 몇 가지 흥미로운 논문:

이들 논문은 모두 데이터 스트림에 대한 대략적인 백분위수 계산을 위해 준선형 공간 복잡도를 갖는 알고리즘을 제안합니다.

"Sequential Procedure for Simultaneous Estimation of Multiple Percentiles"(Raatikainen) 논문에 정의된 간단한 알고리즘을 사용해 보세요.속도가 빠르고 2*m+3 마커(m 백분위수의 경우)가 필요하며 신속하게 정확한 근사값을 얻는 경향이 있습니다.

큰 정수의 동적 배열 T[] 또는 T[n]이 응답 시간이 n 밀리초인 횟수를 계산하는 것을 사용하십시오.실제로 서버 애플리케이션에 대한 통계를 수행하는 경우 어쨌든 250ms의 응답 시간이 절대적인 한계일 수 있습니다.따라서 1KB는 0에서 250 사이의 모든 ms에 대해 하나의 32비트 정수를 보유하며 오버플로 저장소를 위한 여유 공간이 있습니다.더 많은 빈이 있는 것을 원한다면 1000개의 빈에 대해 8비트 숫자를 사용하고 카운터가 오버플로되는 순간(예:해당 응답 시간의 256번째 요청) 모든 bin의 비트를 1씩 아래로 이동합니다.(효과적으로 모든 저장소의 값을 절반으로 줄입니다.)즉, 가장 많이 방문한 저장소가 포착하는 지연의 1/127 미만을 캡처하는 모든 저장소를 무시한다는 의미입니다.

정말로 특정 저장소 세트가 필요한 경우 요청 첫날을 활용하여 합리적인 고정 저장소 세트를 마련하는 것이 좋습니다.동적이며 성능에 민감한 실제 애플리케이션에서는 매우 위험합니다.해당 경로를 선택하면 자신이 무엇을 하고 있는지 더 잘 알 수 있습니다. 그렇지 않으면 어느 날 통계 추적기가 갑자기 프로덕션 서버에서 CPU 90%와 메모리 75%를 소모하는 이유를 설명하기 위해 침대에서 호출을 받게 될 것입니다.

추가 통계는 다음과 같습니다.평균과 분산에는 몇 가지가 있습니다. 좋은 재귀 알고리즘 메모리를 거의 차지하지 않습니다.이 두 통계는 그 자체로 많은 분포에 유용할 수 있습니다. 중심 극한 정리 충분히 많은 수의 독립 변수에서 발생하는 분포가 정규 분포(평균과 분산으로 완전히 정의됨)에 접근한다고 명시하면 다음 중 하나를 사용할 수 있습니다. 정규성 테스트 마지막 N(여기서 N은 충분히 크지만 메모리 요구 사항에 따라 제한됨)에서 정규성 가정이 여전히 유지되는지 모니터링합니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow