히스토그램

히스토그램은 값이 여럿일 때 그 값들이 어디에 몰려 있는지를 보여 줍니다. 값이 놓일 범위를 미리 구간으로 나눠 둡니다. 남기는 것은 구간마다의 건수뿐입니다. 이렇게 센 표도, 그 표를 막대로 그린 그림도 같은 이름으로 부릅니다.

상세

히스토그램은 값 묶음을 구간과 건수 두 줄로 줄여 담는 구조입니다. 값이 놓일 범위를 미리 구간으로 갈라 둡니다. 값이 하나 들어올 때마다 그 값이 속한 구간의 수를 하나 올립니다. 요청 천 건의 응답 시간을 이렇게 세면 천 개의 수가 구간 다섯 개의 건수로 줄어듭니다.

구간 하나를 세는 수를 버킷(bucket)이나 빈(bin)이라고도 부릅니다. 이 글에서는 칸이라고 씁니다. 칸은 값을 담아 두는 통이 아닙니다. 몇 건이 지나갔는지를 세는 수 하나입니다.

값을 버리면 표가 작게 유지됩니다. 관측이 몇 건 들어오든 남는 수는 칸 개수만큼입니다. 재는 기간이 길어져도 표가 안 자랍니다.

구간과 건수

센 표가 어떻게 생겼는지부터 봅니다. 아래는 요청 천 건의 응답 시간을 구간 다섯으로 나눠 센 표입니다. 0.9초짜리 요청 한 건이 새로 들어와 셋째 칸의 수를 올리는 장면입니다.

flowchart TD
    V["응답 시간 한 건 · 0.9초"] --> F{"어느 구간인가"}
    F --> B3
    subgraph T["센 표 · 요청 천 건"]
        B1["0.1초 미만 · 412"]
        B2["0.1 ~ 0.3초 · 380"]
        B3["0.3 ~ 1초 · 150"]
        B4["1 ~ 3초 · 50"]
        B5["3초 넘음 · 8"]
    end

표에 남는 것은 구간 경계 넷과 건수 다섯뿐입니다. 칸 다섯을 가르는 안쪽 경계는 넷입니다. 양 끝 칸은 한쪽이 열려 있어 경계가 하나씩만 필요합니다.

0.9초라는 수는 셋째 칸의 건수를 151로 올립니다. 그 수 자체는 어디에도 안 남습니다. 같은 칸에 든 0.35초와 0.99초는 이 표에서 구별되지 않습니다.

경계에 딱 걸린 값은 어느 칸으로 가는지 미리 정해 둡니다. 한 예로 칸의 아래 경계는 빼고 위 경계는 넣는 규칙이 있습니다. 이 규칙이면 정확히 0.3초인 값은 「0.1 ~ 0.3초」 칸에 듭니다.

재기 전에 긋는 경계

구간은 값을 재기 전에 그어 두어야 합니다. 다 세고 나서 경계를 옮기려면 원래 값이 필요합니다. 그 값은 이미 버렸습니다.

그래서 경계를 어디에 긋느냐가 이 구조의 품질을 거의 다 정합니다. 같은 폭으로 그을 수도 있습니다(등폭). 뒤로 갈수록 일정한 배율로 폭을 넓힐 수도 있습니다(지수 폭). 칸마다 건수가 같아지게 그을 수도 있습니다(등높이). 긋는 법마다 얻는 것과 치르는 것이 달라서 아래 갈래 절이 하나씩 짚습니다.

구간으로 어림하는 분위수

값을 작은 것부터 줄 세웠을 때 몇 번째 위치에 선 값인지를 분위수라고 부릅니다. 그중 줄을 백 등분해 읽는 것이 백분위수입니다. 센 표에서도 이 값을 어림해 읽을 수 있습니다.

읽는 법은 앞 칸부터 건수를 더해 가며 목표 등수가 어느 칸에서 넘어가는지를 찾는 것입니다. 이렇게 앞 칸부터 더해 간 수를 누적 건수라고 부릅니다. 어떤 표는 처음부터 칸마다 이 누적 건수를 적습니다. 그러면 마지막 칸의 수가 곧 전체 건수입니다.

천 건을 백 등분하면 한 토막이 열 건입니다. 아흔아홉 토막을 지난 곳이 990 번째입니다. 아흔아홉 번째 백분위수를 보고 싶다면 990 번째 요청이 어느 칸에 들었는지를 찾습니다.

flowchart TD
    Q["찾는 것 · 아흔아홉 번째 백분위수 = 990 번째"] --> C1
    subgraph T2["앞 칸부터 건수를 더해 간다"]
        C1["0.1초 미만 · 412건 · 누적 412"] --> C2["0.1 ~ 0.3초 · 380건 · 누적 792"]
        C2 --> C3["0.3 ~ 1초 · 150건 · 누적 942"]
        C3 --> C4["1 ~ 3초 · 50건 · 누적 992 · 여기서 990 을 넘는다"]
        C4 --> C5["3초 넘음 · 8건 · 누적 1000 · 위쪽 경계가 없다"]
    end
    C4 --> S["넷째 칸 안 · 990 - 942 = 48 번째 · 그 칸은 50건"]
    S --> A["1초와 3초 사이를 48 대 2 로 가른다 · 2.92초"]

찾고 나면 답으로 나오는 것은 값이 아니라 구간입니다. 「1초에서 3초 사이」까지는 말할 수 있습니다. 그 안의 어느 값인지는 표가 모릅니다. 그래서 그 구간 안에 값이 고르게 퍼져 있다고 봅니다. 그리고 두 경계 사이를 비율로 갈라 수 하나를 냅니다. 그림의 2.92초가 그렇게 낸 수입니다.

이 어림의 오차는 그 값이 든 구간의 폭을 넘지 않습니다. 구간을 잘게 그을수록 어림이 촘촘해집니다. 대신 칸이 늘어납니다.

마지막 칸에 답이 들면 오차가 특히 큽니다. 「3초 넘음」에는 위쪽 경계가 없어서 갈라 쓸 두 수가 없기 때문입니다.

여러 대의 표 합치기

구간을 똑같이 그은 히스토그램 둘은 칸마다 건수를 더하면 하나가 됩니다. 서버 두 대가 각자 센 표를 더하면 두 대를 합쳐 센 표가 나옵니다.

같은 범위를 가리키는 칸끼리 줄을 맞춰 더합니다. 앞 세 칸만 그리면 이렇습니다.

flowchart TD
    subgraph SA["서버 A"]
        A1["0.1초 미만 · 1건"]
        A2["0.1 ~ 0.3초 · 2건"]
        A3["0.3 ~ 1초 · 1건"]
    end
    subgraph SB["서버 B"]
        B1["0.1초 미만 · 0건"]
        B2["0.1 ~ 0.3초 · 3건"]
        B3["0.3 ~ 1초 · 2건"]
    end
    subgraph SM["더한 표"]
        M1["0.1초 미만 · 1건"]
        M2["0.1 ~ 0.3초 · 5건"]
        M3["0.3 ~ 1초 · 3건"]
    end
    A1 --> M1
    B1 --> M1
    A2 --> M2
    B2 --> M2
    A3 --> M3
    B3 --> M3

각 칸이 건수라서 더하기가 됩니다. 건수는 여러 곳에서 센 것을 합쳐도 뜻이 안 변합니다.

대신 두 표의 구간 경계가 같아야 합니다. 경계가 다르면 같은 번호의 칸이 다른 범위를 가리킵니다. 그 둘을 더한 수는 아무 뜻도 없습니다.

칸마다 건수를 더하는 일은 목록 둘을 짝지어 더하는 것이 전부입니다.

a = [1, 2, 1, 0, 1]   # 서버 A
b = [0, 3, 2, 1, 0]   # 서버 B

merged = [x + y for x, y in zip(a, b)]
merged                # [1, 5, 3, 1, 1]

앞 절에서 읽은 백분위수는 이렇게 못 더합니다. 줄 세운 위치를 읽은 값이라 두 서버의 값을 평균 내도 전체 값이 안 나옵니다. 여러 곳에서 잰 것을 합쳐 봐야 할 때 히스토그램을 쓰는 큰 이유가 이것입니다.

쓰는 때와 안 쓰는 때

값이 끝없이 흘러드는 곳에서 씁니다. 그 분포를 계속 보고 싶을 때입니다. 재는 기간이 길어져도 크기가 안 자랍니다. 여러 곳에서 센 것을 더할 수 있습니다. 이 두 성질이 이런 일에 맞습니다.

잰 건수가 적으면 쓸 이유가 없습니다. 백 건이면 값을 다 저장해도 됩니다. 줄을 세워 중앙값을 바로 읽으면 어림하지 않은 답이 나옵니다.

가장 큰 값을 알아야 할 때도 안 맞습니다. 마지막 칸이 「3초 넘음」이면 그 안에 3.1초짜리가 들었는지 30초짜리가 들었는지 이 표는 말하지 못합니다. 그럴 때는 최댓값을 따로 셉니다.

막대그래프와 가르는 선

그림으로 그린 히스토그램은 막대그래프와 비슷하게 생겼습니다. 그러나 가로축이 다릅니다. 막대그래프의 가로축은 서로 이어지지 않는 이름들입니다. 도시 이름이나 제품 이름 같은 것입니다.

히스토그램의 가로축은 이어진 수의 범위입니다. 막대 하나가 그 범위의 한 토막입니다. 그래서 막대 사이를 띄우지 않고 붙여 그립니다. 막대 순서도 바꿀 수 없습니다.

이름은 통계학자 칼 피어슨(Karl Pearson)이 붙였습니다. 그는 통계 강의에서 이 낱말을 들였다고 1895년에 적었습니다. 밑변이 가리키는 범위의 도수, 곧 그 범위에 든 건수를 기둥의 넓이로 나타내는 흔한 그림을 부르는 이름이었습니다.

복잡도

히스토그램은 관측이 몇 건이든 칸 수만큼의 공간만 씁니다. 관측 한 건을 기록하는 비용도 칸 번호 찾기 한 번이라 가볍습니다. 비싼 일은 하나뿐입니다. 경계를 데이터에서 새로 그을 때는 흔히 표본을 정렬합니다.

아래 표에서 n 은 들어온 관측의 수, k 는 칸의 수입니다. 경계를 새로 긋는 줄의 m 은 경계를 정하려고 뽑은 표본 행의 수입니다.

값을 버려서 얻는 공간

값을 다 저장하는 방식은 저장할 것이 관측 수 n 에 비례해 늘어납니다. 오래 재는 서비스에서는 곧 감당하기 어려워집니다.

히스토그램이 저장하는 수는 언제나 k 개입니다. n 이 백만이든 십억이든 k 는 안 변합니다. 이 차이가 값을 버린 대가로 얻는 것입니다.

관측 한 건을 기록하는 비용

값이 하나 들어오면 두 가지를 합니다. 먼저 어느 칸인지 찾습니다. 그다음 그 칸의 수를 하나 올립니다. 올리는 비용은 덧셈 한 번이라 늘 같습니다. 비용을 가르는 것은 찾는 일입니다.

구간을 같은 폭으로 그었으면 값을 폭으로 나눠 칸 번호를 냅니다. 지수 폭이면 값에 로그를 한 번 씌워 칸 번호를 냅니다. 폭이 제각각이면 경계 목록에서 이진 탐색으로 찾아야 해서 log k 에 비례합니다.

경계 넷과 칸 다섯을 두고 관측 다섯 건을 넣어 보면 이렇습니다.

import bisect
edges  = [0.1, 0.3, 1.0, 3.0]  # 구간 경계 넷
counts = [0, 0, 0, 0, 0]       # 칸 다섯

def observe(v):
    counts[bisect.bisect_left(edges, v)] += 1

for v in [0.05, 0.2, 0.2, 0.9, 5.0]:
    observe(v)

counts       # [1, 2, 1, 0, 1]
sum(counts)  # 5

observe 는 값 하나를 받아 이진 탐색으로 칸 번호를 찾습니다. 그다음 그 칸의 수를 하나 올립니다. bisect_left 는 경계와 같은 값을 왼쪽 칸에 넣습니다. 앞 절의 「위 경계는 넣는다」 규칙과 같은 동작입니다. 넘겨준 0.05·0.2·0.9 같은 수는 어디에도 안 남았습니다.

최악과 평균

관측 기록·합치기·분위수 어림은 어떤 값이 들어와도 비용이 같습니다. 이 셋은 최악과 평균이 같습니다. 해시테이블처럼 값이 한곳에 몰려 느려지는 일이 없습니다. 값이 한 칸에 몰려도 그 칸의 수를 하나 올리는 비용은 같습니다.

이 구조에서 비용이 가장 커지는 때는 위 세 연산이 아니라 경계를 데이터에서 새로 그을 때입니다. 칸마다 건수가 같아지게 그으려면 값이 몇 번째로 큰지를 알아야 합니다. 그래서 흔히 표본을 정렬하는 O(m log m) 이 듭니다. 이 비용은 관측마다 드는 것이 아니라 통계를 새로 모을 때 한 번 듭니다.

예시

성격이 다른 실물 둘을 봅니다. 하나는 데이터베이스가 행 수를 어림하는 표입니다. 다른 하나는 성능 지표에서 목표 달성 비율을 세고 분위수를 어림하는 표입니다.

PostgreSQL 의 histogram_bounds

PostgreSQL 은 질의를 어떤 방법으로 읽을지 정하기 전에 조건에 걸릴 행 수를 어림합니다. 이렇게 정한 읽기 순서와 방법을 실행 계획이라고 부릅니다. 조건에 걸리는 행이 전체에서 차지하는 비율은 선택도라고 부릅니다.

아래는 PostgreSQL 회귀 테스트용 테이블 tenk1 에 범위 조건을 건 질의입니다. 이 테이블은 1만 행입니다. unique1 은 값이 겹치지 않는 열입니다.

EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000;

 Bitmap Heap Scan on tenk1  (cost=24.06..394.64 rows=1007 width=244)
   Recheck Cond: (unique1 < 1000)
   ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
         Index Cond: (unique1 < 1000)

rows=1007 이 어림한 행 수입니다. 이 수는 unique1 열의 히스토그램에서 나왔습니다. 그 히스토그램은 pg_stats 뷰에서 이렇게 꺼내 봅니다.

SELECT histogram_bounds FROM pg_stats
WHERE tablename='tenk1' AND attname='unique1';

{0,993,1997,3050,4040,5036,5957,7057,8029,9016,9995}

경계 열한 개가 칸 열 개를 가릅니다. 첫 경계 0 과 끝 경계 9995 가 양 끝 칸도 닫습니다. 그래서 경계가 칸보다 하나 많습니다. 이 표는 칸마다 행 수가 대략 같도록 그은 등높이 방식입니다(갈래 절). 그래서 건수 배열 없이 경계만 적습니다. 칸 하나가 전체 행의 10분의 1을 맡습니다.

1000 은 둘째 칸(993 ~ 1997)에 듭니다. 첫 칸은 전부 조건을 만족하니 한 칸으로 셉니다. 둘째 칸은 안에 값이 고르게 퍼졌다고 봅니다. 그래서 1000 이 그 칸의 어디쯤인지를 비율로 셉니다.

flowchart TD
    subgraph H["unique1 의 칸 열 개 · 칸마다 행 10분의 1"]
        K1["첫 칸 · 0 ~ 993 · 전부 1000 미만"]
        K2["둘째 칸 · 993 ~ 1997 · 1000 이 여기 든다"]
        K3["나머지 여덟 칸 · 1997 ~ 9995 · 전부 1000 이상"]
    end
    K1 --> P1["한 칸 통째 · 1"]
    K2 --> P2["칸 안 비율 · 1000 - 993 = 7 · 칸 폭 1004 · 7/1004"]
    P1 --> R["1 + 7/1004 를 칸 수 10 으로 나눈다 · 0.100697"]
    P2 --> R
    R --> N["1만 행 × 0.100697 = 1007 행"]

selectivity = (1 + (1000 - bucket[2].min)/(bucket[2].max - bucket[2].min))/num_buckets
            = (1 + (1000 - 993)/(1997 - 993))/10
            = 0.100697

rows = rel_cardinality * selectivity
     = 10000 * 0.100697
     = 1007  (rounding off)

앞 칸 하나를 통째로 더하고 걸친 칸 안을 비율로 가르는 것은 상세 절에서 분위수를 어림한 법과 같습니다. 그 셈이 EXPLAIN 의 rows=1007 로 나옵니다.

값이 겹치는 열에는 대개 히스토그램과 함께 MCV(most common values, 가장 흔한 값 목록)가 있습니다. MCV 는 자주 나오는 값을 빈도와 함께 따로 적은 목록입니다. 히스토그램은 MCV 에 든 값을 뺀 나머지로만 긋습니다.

같은 테이블의 문자열 열 stringu1 은 MCV 가 있는 열입니다. 여기에 stringu1 < 'IAAAAA' 조건을 걸면 행이 두 몫으로 갈립니다. 문자열에서 < 는 정렬 순서로 'IAAAAA' 보다 앞에 오는 값을 고릅니다.

flowchart TD
    A["stringu1 의 행 전체 · 1만 행"] --> M["MCV 에 든 값의 행"]
    A --> H["MCV 가 아닌 나머지 행 · 전체의 0.96966667"]
    M --> M2["MCV 몫 · 조건에 맞는 값의 빈도 합 · 0.01833333"]
    H --> H2["히스토그램 몫 · 나머지 안에서 0.298387"]
    M2 --> S["0.01833333 + 0.298387 × 0.96966667 = 0.307669"]
    H2 --> S
    S --> R["1만 행 × 0.307669 = 3077 행"]

MCV 몫은 목록의 값 가운데 조건에 맞는 값의 빈도를 더한 수입니다. 이 조건에서는 0.01833333 입니다. 목록에 적힌 빈도를 바로 쓰니 칸 안을 비율로 가를 일이 없습니다.

히스토그램 몫 0.298387 은 MCV 가 아닌 나머지 행 안에서 조건에 걸리는 비율입니다. 앞의 unique1 예와 같은 법으로 stringu1 의 히스토그램에서 냅니다. 전체에 대한 비율로 바꾸려면 나머지 행이 전체에서 차지하는 비율 0.96966667 을 곱합니다. 그 값에 MCV 몫을 더하면 선택도 0.307669 가 됩니다.

Prometheus 의 le 칸

Prometheus 는 요청이 걸린 시간 같은 값을 칸마다 따로 내보냅니다. 칸 하나는 http_request_duration_seconds_bucket{le="0.3"} 처럼 le 라는 이름표(레이블)가 붙은 값 하나입니다. le 는 「less or equal」, 곧 「이하」라는 뜻입니다.

이 칸은 0.3초 이하인 관측을 전부 셉니다. 0.2 ~ 0.3초만 세는 것이 아닙니다. 앞 칸의 건수를 다 품는 누적 칸입니다. le 값은 그 칸의 포함 상한입니다. 경계를 0.1·0.2·0.3·0.45초에 둔 표라면 칸끼리 이렇게 겹칩니다.

flowchart TD
    subgraph L4["le=0.45 · 0.45초 이하 전부"]
        subgraph L3["le=0.3 · 0.3초 이하 전부"]
            subgraph L2["le=0.2 · 0.2초 이하 전부"]
                L1["le=0.1 · 0.1초 이하 전부"]
            end
        end
    end

그래서 칸 하나와 전체 건수만 읽어도 「300ms 안에 끝난 요청의 비율」이 나옵니다. 아래 식은 PromQL(Prometheus Query Language)로 적은 그 계산입니다.

  sum by (job) (rate(http_request_duration_seconds_bucket{le="0.3"}[5m]))
/
  sum by (job) (rate(http_request_duration_seconds_count[5m]))

rate(...[5m]) 는 지난 5분 동안 초당 늘어난 건수입니다. 윗줄은 0.3초 이하 칸의 증가분입니다. 아랫줄은 전체 건수 _count 의 증가분입니다. sum by (job) 은 같은 job 이름을 단 서버들의 것을 더합니다.

이 식은 0.3 에 경계가 있어야만 답을 냅니다. 그 경계가 없으면 칸 사이를 비율로 가르는 어림을 하지 않습니다. 결과가 아예 안 나옵니다. 합치는 표 가운데 일부에만 그 경계가 있으면 덜 센 결과가 경고 없이 나옵니다.

경계가 성기면 분위수 어림이 얼마나 틀리는지를 수치로 봅니다. 경계를 0.1·0.2·0.3·0.45초에 손으로 정해 둔 고전 히스토그램(classic histogram)과, 지수 폭으로 칸을 잘게 긋는 native histogram(갈래 절)을 나란히 둔 실험입니다. 요청 대부분이 한 값 근처에 몰려 있다고 놓고 95번째 백분위수를 어림합니다.

참값 220ms 때 native 가 쓴 칸의 범위는 미확인이라 비워 두었습니다.

95번째 백분위수 300ms 를 서비스 수준 목표(SLO, Service Level Objective)로 둔 서비스라고 합시다. 참값이 220ms 일 때 고전 칸은 295ms 로 읽어 목표를 곧 넘길 것처럼 보입니다. 모든 요청에 100ms 가 더해져 320ms 가 되면 고전 칸은 443ms 로 읽습니다. 목표를 조금 넘은 상태가 훨씬 나빠 보입니다.

칸이 넓으면 어림이 그만큼 크게 빗나갈 수 있습니다. 200 ~ 300ms 칸이면 어림이 그 100ms 안 어디로든 갈 수 있습니다. native 칸은 폭이 27ms 라 어림이 참값 가까이 붙습니다.

갈래

갈래를 가르는 축은 경계를 어떻게 긋나입니다. 같은 칸 수로도 경계를 어디에 두느냐에 따라 어느 값 범위를 촘촘히 보는지가 달라집니다.

등폭

값의 범위를 같은 폭으로 자릅니다. 통계에서 가장 흔한 방식입니다. 스무 살부터 여든 살까지의 나이를 다섯 살씩 자르는 식입니다. 값을 폭으로 나누면 칸 번호가 나옵니다.

약점은 값이 한쪽에 몰린 묶음에서 드러납니다. 지연처럼 대부분이 짧고 드물게 긴 값이 섞이면 앞의 칸 하나에 대부분이 들어갑니다. 뒤의 칸은 거의 빕니다. 0초에서 3초까지를 같은 폭과 뒤로 넓어지는 폭으로 그어 보면 경계가 놓이는 곳이 이렇게 다릅니다.

block-beta
columns 8
  L1["등폭 · 경계가 고르게 놓인다"]:8
  a1["0 ~ 0.75초"]:2 a2["0.75 ~ 1.5초"]:2 a3["1.5 ~ 2.25초"]:2 a4["2.25 ~ 3초"]:2
  L2["뒤로 넓어지는 폭 · 앞부분에 몰렸다가 뒤로 벌어진다"]:8
  b1["0 ~ 0.1초"]:1 b2["0.1 ~ 0.3초"]:1 b3["0.3 ~ 1초"]:2 b4["1 ~ 3초"]:4

데이터베이스가 값 분포를 어림하는 데 히스토그램을 쓰자는 첫 제안은 알려진 한 1980년 Kooi 의 박사 논문입니다. 그 제안은 통계에서 가장 단순한 꼴인 등폭을 그대로 빌려 온 것입니다. 그전까지는 열 전체에 값이 고르게 퍼졌다고 가정했습니다. 칸 하나짜리 히스토그램과 같은 셈입니다. 그래서 등폭만으로도 어림이 크게 나아졌습니다.

지수 폭

경계를 한 배율의 거듭제곱 위에 긋습니다. 칸이 뒤로 갈수록 같은 비율로 넓어집니다. 그래서 작은 값이 드는 칸은 좁습니다. 큰 값이 드는 칸은 넓습니다. 오차가 값의 크기에 비례하게 됩니다.

배율은 scale 이라는 정수 하나로 정합니다. scale 이 클수록 칸이 잘게 쪼개져 정밀도가 높습니다. 배율은 base = 2^(2^-scale) 입니다. scale 이 0 이면 배율은 2 입니다. 경계는 1·2·4·8 처럼 놓입니다. scale 이 1 오를 때마다 2의 거듭제곱 사이의 칸이 두 배로 늘어 2^scale 개가 됩니다.

값 v 가 드는 칸의 번호는 ceil(log v / log base) - 1 입니다. 로그 한 번이면 나옵니다.

칸은 시작 칸 번호(offset) 하나와 건수 배열 하나로 담습니다. 배열의 i 번째 수가 칸 번호 offset + i 의 건수입니다.

scale 을 하나 내리면 이웃한 두 칸이 한 칸에 꼭 맞게 겹칩니다. 그래서 해상도가 다른 두 표도 낮은 해상도에 맞춰 오차 없이 합칩니다. OpenTelemetry 의 ExponentialHistogram 과 Prometheus 의 native histogram 이 이 방식입니다. Prometheus 는 scale 을 schema 라고 부릅니다. 지금은 -4 부터 8 까지를 씁니다.

flowchart TD
    subgraph S1["scale 1 · 배율 약 1.414"]
        a["1 ~ 1.414"]
        b["1.414 ~ 2"]
        c["2 ~ 2.828"]
        d["2.828 ~ 4"]
    end
    subgraph S0["scale 0 · 배율 2"]
        e["1 ~ 2"]
        f["2 ~ 4"]
    end
    a --> e
    b --> e
    c --> f
    d --> f

경계를 손으로 정한 표끼리는 사정이 다릅니다. 경계가 서로 다르면 대개 합칠 수 없습니다.

로그-선형

큰 칸은 지수 폭으로 넓어집니다. 큰 칸 하나 안에는 같은 개수의 작은 칸이 같은 폭으로 들어갑니다. 아래 그림은 큰 칸 셋을 그린 것입니다. 큰 칸 경계(1·2·4·8)와 큰 칸마다 넷인 작은 칸은 그림을 위해 고른 값입니다.

flowchart TD
    subgraph G1["큰 칸 1 ~ 2 · 작은 칸 폭 0.25"]
        g11["1 ~ 1.25"]
        g12["1.25 ~ 1.5"]
        g13["1.5 ~ 1.75"]
        g14["1.75 ~ 2"]
    end
    subgraph G2["큰 칸 2 ~ 4 · 작은 칸 폭 0.5"]
        g21["2 ~ 2.5"]
        g22["2.5 ~ 3"]
        g23["3 ~ 3.5"]
        g24["3.5 ~ 4"]
    end
    subgraph G3["큰 칸 4 ~ 8 · 작은 칸 폭 1"]
        g31["4 ~ 5"]
        g32["5 ~ 6"]
        g33["6 ~ 7"]
        g34["7 ~ 8"]
    end
    G1 ~~~ G2
    G2 ~~~ G3

작은 칸의 개수는 큰 칸마다 같습니다. 그래서 큰 칸이 넓어지면 작은 칸의 폭도 따라 넓어집니다. 부동소수점 수가 크기를 정하는 지수와 유효 숫자를 담는 가수로 나뉘는 것과 닮았습니다. 큰 칸이 지수 몫을, 그 안의 작은 칸이 가수 몫을 맡습니다.

정밀도는 유효 숫자를 몇 개 지킬지로 정합니다. 유효 숫자를 셋으로 잡으면 범위 어디서든 칸 폭이 그 값의 1000분의 1(0.1%)을 넘지 않습니다. 칸 번호는 값에서 바로 계산합니다. 탐색도 되풀이도 없습니다. HdrHistogram 이 이 방식입니다.

등높이

칸마다 건수가 대략 같도록 경계를 긋습니다. 건수가 다 같으니 건수 배열이 필요 없습니다. 경계만 적습니다. 값이 몰린 구간은 칸이 잘게, 성긴 구간은 칸이 넓게 잘립니다.

1984년 Piatetsky-Shapiro 와 Connell 이 등폭 대신 이 방식을 냈습니다. 등폭보다 어림이 꽤 잘 맞는다는 근거가 쌓이자 상용 데이터베이스 여럿이 이 방식으로 옮겨 갔습니다. 대신 경계를 데이터에서 새로 그어야 합니다. 복잡도 절의 정렬 비용이 여기서 듭니다.

PostgreSQL 의 histogram_bounds 가 이 방식입니다. Oracle 은 이것을 높이 균형(height-balanced)이라 부릅니다. Oracle Database 12c 부터는 표본 크기를 자동(AUTO_SAMPLE_SIZE)으로 두면 새로 만들지 않는 옛 방식이 됐습니다.

빈도

서로 다른 값 하나마다 칸 하나를 줍니다. 서로 다른 값의 수가 칸 수보다 적거나 같을 때 씁니다. 칸 사이를 비율로 가를 일이 없어 값마다 건수가 남습니다. 그래서 행이 많은 칸도, 적은 칸도 생깁니다.

Oracle 은 여기에 둘을 더 씁니다. 상위 빈도(top frequency)는 빈도의 변형입니다. 서로 다른 값이 칸 수보다 많아도 상위 값들이 행을 거의 다 차지하면 씁니다. 문턱은 (1 - 1/칸 수) × 100 퍼센트입니다. 칸이 기본값 254 개면 상위 254 개 값이 행의 99.6% 이상을 차지할 때입니다. 그때 드문 값은 버리고 상위 값에만 칸을 줍니다.

하이브리드(hybrid)는 등높이와 빈도를 합친 방식입니다. 상위 값이 그 문턱에 못 미칠 때 씁니다. 경계는 등높이처럼 긋습니다. 여기에 칸마다 가장 큰 값이 몇 번 되풀이되는지(endpoint repeat count)를 같이 적습니다. Oracle 이 셋 가운데 하나를 고르는 기준을 그리면 이렇습니다.

flowchart TD
    S["열의 서로 다른 값의 수"] --> Q1{"칸 수 이하인가 · 기본 254"}
    Q1 -->|예| F["빈도"]
    Q1 -->|아니오| Q2{"상위 254 개 값이 행의 99.6% 이상인가"}
    Q2 -->|예| T["상위 빈도"]
    Q2 -->|아니오| HY["하이브리드"]

사용처

히스토그램을 쓰는 곳은 크게 두 갈래입니다. 하나는 서비스가 걸린 시간을 재는 성능 지표입니다. 다른 하나는 데이터베이스가 실행 계획을 고르려고 열의 값 분포를 어림하는 통계 정보입니다. 데이터베이스 안에서 질의마다 실행 계획을 고르는 부품을 질의 최적화기라고 부릅니다.

성능 지표

Prometheus 는 합치기 때문에 히스토그램을 고릅니다. 서비스를 여러 인스턴스로 띄우면 인스턴스마다 잰 시간을 모아 전체 95번째 백분위수를 보고 싶어집니다. 인스턴스마다 미리 계산해 둔 분위수를 평균 내면 통계적으로 뜻이 없는 값이 나옵니다. 히스토그램은 칸을 더한 뒤 histogram_quantile() 로 분위수를 어림합니다.

avg(http_request_duration_seconds{quantile="0.95"}) // BAD!

histogram_quantile(0.95, sum by (le) (rate(http_request_duration_seconds_bucket[5m]))) // GOOD.

OpenTelemetry SDK(Software Development Kit)는 경계를 손으로 정하는 히스토그램의 기본 경계를 [0, 5, 10, 25, 50, 75, 100, 250, 500, 750, 1000, 2500, 5000, 7500, 10000] 으로 둡니다. 경계 열다섯이 칸 열여섯을 가릅니다. 이 기본값은 Prometheus 클라이언트의 기본 칸에 크게 영향받았습니다.

지수 폭 히스토그램은 양수와 음수 범위마다 칸을 기본 최대 160 개 둡니다. 이 160 은 1ms 에서 100s 까지 뻗는 긴 꼬리 지연 분포를 상대 오차 5% 아래로 덮으려고 고른 값입니다. scale 은 들어온 데이터에 맞춰 구현이 스스로 고칩니다.

HdrHistogram 은 지연과 성능에 민감한 프로그램 안에서 값을 기록하려고 만든 라이브러리입니다. 2012년 무렵 인텔 CPU(Central Processing Unit)에서 한 건 기록에 짧게는 3 ~ 6ns 가 걸렸습니다. 기록할 때 메모리를 새로 잡지 않습니다. 1마이크로초에서 1시간까지를 유효 숫자 셋으로 잡으면 약 185KB 를 고정으로 씁니다. 기록한 값이 몇 건이든 이 크기는 안 변합니다.

데이터베이스 실행 계획

PostgreSQL 은 ANALYZE 가 큰 테이블에서 무작위 표본을 떠서 히스토그램을 그립니다. 그래서 큰 테이블도 짧은 시간에 끝납니다. 대신 통계는 어림이라 ANALYZE 를 돌릴 때마다 조금씩 바뀝니다. 칸 수 상한은 default_statistics_target 이 정합니다. 기본은 100 입니다. 올리면 값이 고르지 않은 열에서 어림이 나아질 수 있습니다. 그만큼 통계가 차지하는 공간이 늘어납니다. 어림 계산도 조금 더 걸립니다.

Oracle 은 히스토그램이 없으면 열의 서로 다른 값마다 행이 고르게 나뉜다고 가정합니다. 캘리포니아의 한 서점이 책의 95% 를 캘리포니아로, 4% 를 오리건으로, 1% 를 네바다로 보낸다고 합시다. 주문 테이블은 30만 행입니다. 히스토그램이 없으면 오리건 주문을 30만 ÷ 3 = 10만 행으로 어림해 테이블 전체를 읽습니다. 히스토그램이 있으면 4% 로 셈해 인덱스를 탑니다.

Oracle 은 서로 다른 값의 수와 데이터 분포에 따라 빈도·상위 빈도·하이브리드 가운데 하나를 고릅니다. 칸 수는 기본 254 입니다. 고르는 기준은 갈래 절의 빈도 소절 그림에 있습니다.

SQL Server 는 마이크로소프트의 데이터베이스입니다. 이 제품은 칸을 단계(step)라고 부릅니다. 통계는 열 하나 이상을 묶은 단위로 만듭니다. 이 단위를 통계 객체라 부릅니다. 통계 객체가 열을 여럿 묶어도 히스토그램은 그 가운데 첫 열 하나에만 만듭니다.

만드는 법은 이렇습니다. 열 값을 정렬한 뒤 최대 200 개의 이어진 단계로 묶습니다. 단계가 넘치면 정보를 가장 덜 잃는 이웃 두 단계를 하나로 합칩니다. 그래서 단계는 200 개를 넘지 않습니다.

단계마다 위 경계 값(range_high_key)을 적습니다. 그 값이 나온 횟수(equal_rows)도 적습니다. 두 경계 사이의 값들은 값 하나가 평균 몇 번 나왔는지(average_range_rows)로만 남깁니다. 단계 둘을 이어 놓으면 이 셋이 어디에 붙는지 보입니다.

block-beta
columns 5
  L["한 단계 = 경계 사이 값들 + 위 경계 값"]:5
  n1["첫 단계"]:1
  r1["경계 사이 값들 · average_range_rows"]:3
  h1["위 경계 값 · range_high_key · equal_rows"]:1
  n2["둘째 단계"]:1
  r2["경계 사이 값들 · average_range_rows"]:3
  h2["위 경계 값 · range_high_key · equal_rows"]:1

경계 값 자신은 사이 값들의 범위에서 빠집니다. 그 값의 건수는 equal_rows 가 따로 셉니다.

관련 항목

히스토그램을 이루는 구성 요소

버킷 · 구간 경계 · 도수 · 누적 도수 · 버킷팅 · 표본 크기

히스토그램의 하위 종류

등폭 히스토그램 · 등높이 히스토그램 · 지수 히스토그램 · 로그-선형 히스토그램 · 빈도 히스토그램 · 하이브리드 히스토그램 · 누적 히스토그램 · native histogram · ExponentialHistogram

히스토그램이 요약하는 분포의 성질

분포 · 치우침 · 긴 꼬리 · 이상치 · 최빈값 · 분산 · 표준편차

히스토그램에서 어림해 읽는 통계량

분위수 · 백분위수 · 중앙값 · 사분위수 · 높은 분위수 · 평균 · 누적 분포 함수

같은 일을 더 적은 공간으로 하는 요약 구조

t-digest · 근사 분위수 · 스케치 · 카운트 민 스케치 · 저수지 샘플링 · summary

히스토그램으로 재는 성능 지표

지연 · 응답 시간 · 꼬리 지연 · 처리량 · 오류율 · 서비스 수준 지표 · 서비스 수준 목표

히스토그램을 내보내고 그리는 관측 도구

메트릭 · 계측 · 모니터링 · 관측성 · 대시보드 · 시계열 데이터베이스 · 경보 · PromQL · histogram_quantile

히스토그램을 채택한 제품

Prometheus · OpenTelemetry · HdrHistogram · PostgreSQL · Oracle · SQL Server

히스토그램으로 실행 계획을 고르는 데이터베이스 기능

통계 정보 · 선택도 · 카디널리티 · 실행 계획 · 질의 최적화기 · 인덱스 · MCV · ANALYZE · default_statistics_target · NDV

히스토그램과 생김새가 헷갈리는 그림

막대그래프 · 산점도 · 상자 그림 · 히트맵 · 꺾은선 그래프

히스토그램을 다루는 계산 절차

이진 탐색 · 정렬 · 선택 알고리즘 · 구간 트리 · 누적 합 · 부동소수점