DataSketches KLL Sketch 모듈

Apache DataSketches 라이브러리의 KllFloatsSketch와 KllDoublesSketch를 기반으로 한 숫자 분위수(quantiles) 애그리게이터를 제공하는 모듈이에요. 값의 분포를 추정하고 순위, PMF/CDF, 분위수 등을 근사적으로 계산해요.

출처: 문서

본문

이 모듈은 Apache DataSketches 라이브러리의 숫자 분위수 KllFloatsSketch와 KllDoublesSketch를 기반으로 한 Apache Druid 애그리게이터를 제공해요. KLL quantiles sketch는 값의 분포를 추정하고, 값의 순위, 분포의 확률 질량 함수(PMF) 또는 히스토그램, 누적 분포 함수(CDF), 분위수(중앙값, min, max, 95번째 백분위수 등)에 대한 질문에 근사적으로 답하는 병합 가능한 스트리밍 알고리즘이에요. Quantiles Sketch Overview를 참고하세요. 이 문서는 KllFloatsSketch와 KllDoublesSketch 모두에 적용돼요. 예제에서는 둘 중 하나만 사용돼요.

세 가지 주요 작동 모드가 있어요:

Druid 외부에서 만들어진 sketch 인제스트(Pig 또는 Hive 사용 등)
인제이션 중 원시 데이터에서 sketch 생성
쿼리 시점에 원시 데이터에서 sketch 생성

이 애그리게이터를 사용하려면 config 파일에 확장 기능을 포함하세요:

druid.extensions.loadList=["druid-datasketches"]

Druid가 지원하는 추가 sketch 유형은 DataSketches extension을 참고하세요.

애그리게이터 (Aggregator)

집계 결과는 원시 데이터에서 생성되었거나 세그먼트에서 읽은 모든 sketch의 union인 KllFloatsSketch 또는 KllDoublesSketch예요.

{
  "type" : "KllDoublesSketch",
  "name" : <output_name>,
  "fieldName" : <metric_name>,
  "k": <parameter that controls size and accuracy>
 }

| Property | Description | Required? | | type | Either "KllFloatsSketch" or "KllDoublesSketch" | yes | | name | A String for the output (result) name of the calculation. | yes | | fieldName | String for the name of the input field, which may contain sketches or raw numeric values. | yes | | k | Parameter that determines the accuracy and size of the sketch. Higher k means higher accuracy but more space to store sketches. Must be from 8 to 65535. See KLL Sketch Accuracy and Size . | no, defaults to 200 | | maxStreamLength | This parameter defines the number of items that can be presented to each sketch before it may need to move from off-heap to on-heap memory. This is relevant to query types that use off-heap memory, including TopN and GroupBy . Ideally, should be set high enough such that most sketches can stay off-heap. | no, defaults to 1000000000 |

Post aggregator (Post aggregators)

Quantile

입력 스트림의 가상 정렬 버전에서 주어진 분수(fraction)가 앞서는 값의 근사치를 반환해요.

{
  "type"  : "KllDoublesSketchToQuantile",
  "name": <output name>,
  "field"  : <post aggregator that refers to a KllDoublesSketch (fieldAccess or another post aggregator)>,
  "fraction" : <fractional position in the hypothetical sorted stream, number from 0 to 1 inclusive>
}

Quantiles

주어진 분수 배열에 해당하는 분위수 배열을 반환해요.

{
  "type"  : "KllDoublesSketchToQuantiles",
  "name": <output name>,
  "field"  : <post aggregator that refers to a KllDoublesSketch (fieldAccess or another post aggregator)>,
  "fractions" : <array of fractional positions in the hypothetical sorted stream, number from 0 to 1 inclusive>
}

Histogram

히스토그램 빈을 정의하는 분할점(split points) 배열 또는 빈 수(둘 다는 아님)가 주어지면 히스토그램의 근사치를 반환해요. m개의 고유하고 단조 증가하는 분할점 배열은 실수선을 m+1개의 연속적이고 서로소인 구간으로 나눠요. 구간의 정의는 왼쪽 분할점 포함(inclusive)이고 오른쪽 분할점 제외(exclusive)예요. 분할점 대신 빈 수가 지정되면 최소값과 최대값 사이의 구간이 주어진 수의 균등 간격 빈으로 나뉘어요.

{
  "type"  : "KllDoublesSketchToHistogram",
  "name": <output name>,
  "field"  : <post aggregator that refers to a KllDoublesSketch (fieldAccess or another post aggregator)>,
  "splitPoints" : <array of split points (optional)>,
  "numBins" : <number of bins (optional, defaults to 10)>
}

Rank

주어진 값보다 작은 분포의 분수인, 주어진 값의 순위 근사치를 반환해요.

{
  "type"  : "KllDoublesSketchToRank",
  "name": <output name>,
  "field"  : <post aggregator that refers to a KllDoublesSketch (fieldAccess or another post aggregator)>,
  "value" : <value>
}

CDF

빈의 가장자리를 정의하는 분할점 배열이 주어지면 누적 분포 함수(Cumulative Distribution Function)의 근사치를 반환해요. m개의 고유하고 단조 증가하는 분할점 배열은 실수선을 m+1개의 연속적이고 서로소인 구간으로 나눠요. 구간의 정의는 왼쪽 분할점 포함이고 오른쪽 분할점 제외예요. 결과 분수 배열은 항상 1인 추가 순위 하나와 함께 각 분할점의 순위로 볼 수 있어요.

{
  "type"  : "KllDoublesSketchToCDF",
  "name": <output name>,
  "field"  : <post aggregator that refers to a KllDoublesSketch (fieldAccess or another post aggregator)>,
  "splitPoints" : <array of split points>
}

Sketch Summary

디버깅에 사용할 수 있는 sketch의 요약을 반환해요. toString() 메서드를 호출한 결과예요.

{
  "type"  : "KllDoublesSketchToString",
  "name": <output name>,
  "field"  : <post aggregator that refers to a KllDoublesSketch (fieldAccess or another post aggregator)>
}

DataSketches KLL Sketch 모듈