히스토그램

히스토그램은 값이 여럿일 때 그 값들이 어디에 몰려 있는지를 보여 줍니다. 값이 놓일 범위를 구간으로 미리 나눠 두고, 구간마다 몇 건이 들어왔는지만 셉니다. 값 하나하나는 남기지 않습니다. 이렇게 세어 둔 표도, 그 표를 막대로 그린 그림도 같은 이름으로 부릅니다.

상세

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

구간 하나를 세는 칸을 버킷이라고 부릅니다. 이 글에서는 칸이라고 씁니다. 칸은 값을 담아 두는 통이 아니라 몇 건이 지나갔는지를 세는 수 하나입니다. 어떤 값이 들어왔는지는 안 남고 몇 건이었는지만 남습니다.

구간과 건수

센 표가 어떻게 생겼는지부터 봅니다. 아래는 요청 천 건의 응답 시간을 구간 다섯으로 나눠 센 표입니다. 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초는 이 표에서 구별되지 않습니다.

값을 버려서 얻는 것

버리는 대신 얻는 것은 공간입니다. 관측이 n 건 들어오고 구간을 k 개로 그었다면, 들고 있어야 하는 수는 언제나 k 개입니다. n 이 백만이든 십억이든 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 는 값 하나를 받아 칸 번호를 찾고 그 칸을 올립니다. 관측 다섯 건이 다섯 칸에 나뉘어 담겼습니다. 넘겨준 0.05·0.2·0.9 같은 수는 어디에도 안 남았습니다.

건수를 다 더하면 몇 건을 셌는지가 나옵니다. 이 합은 표를 읽을 때 다시 씁니다.

구간에서 분위수를 어림한다

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

읽는 법은 앞 칸부터 건수를 더해 가며 목표 등수가 어느 칸에서 넘어가는지를 찾는 것입니다. 앞에서 건수를 다 더하면 몇 건을 셌는지가 나온다고 했습니다. 412·380·150·50·8 을 더한 천 건이 그 수입니다.

천 건을 백 등분하면 한 토막이 열 건입니다. 아흔아홉 토막을 지난 곳이 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]

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

구간을 어떻게 긋나

구간을 어디에 긋느냐가 이 구조의 품질을 거의 다 정합니다. 값이 고르게 퍼진 묶음은 같은 폭으로 나누면 됩니다. 스무 살부터 여든 살까지의 나이를 다섯 살씩 자르는 식입니다.

지연처럼 대부분이 앞쪽에 몰리고 뒤로 길게 끌리는 묶음은 뒤로 갈수록 폭을 넓힙니다. 앞쪽을 촘촘히, 뒤쪽을 성기게 긋는 것입니다.

보통 얼마나 걸리는지를 보려면 앞쪽이 촘촘해야 합니다. 드물게 오래 걸린 소수 요청의 지연인 꼬리 지연을 보려면 뒤쪽에도 칸이 남아 있어야 합니다.

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

구간은 값을 재기 전에 정해 두어야 합니다. 다 세고 나서 경계를 옮기려면 원래 값이 필요합니다. 그 값은 이미 버렸습니다. 이 점이 히스토그램을 쓸지 정할 때 제일 먼저 걸리는 대목입니다.

성능 지표로 쓰는 히스토그램

서비스의 메트릭을 모으는 계측에서 히스토그램은 흔한 형태입니다. 서버마다 요청이 얼마나 걸렸는지를 구간별로 셉니다. 모니터링 도구가 여러 대의 건수를 더한 뒤 그 표에서 분위수를 읽습니다.

평균 하나만 내보내는 방식과 견주면 차이가 큽니다. 평균은 모든 값을 섞어 수 하나로 줄입니다. 오래 걸린 몇 건은 나머지에 묻힙니다.

이런 값을 이상치라고 부릅니다. 히스토그램은 이들을 뒤쪽 칸의 건수로 남겨 둡니다.

서비스 수준 목표를 「백 건 중 아흔아홉 건이 0.5초 안」처럼 적었다면, 그 약속을 지켰는지 재는 수가 이 표에서 나옵니다. 함께 적어 두는 것은 구간 경계입니다. 경계를 모르면 나중에 읽은 분위수가 얼마나 거친 어림인지 알 수 없습니다.

데이터베이스 통계의 히스토그램

같은 구조가 통계 정보에도 쓰입니다. 질의 최적화기는 인덱스를 탈지 테이블을 다 읽을지 정하려고 「이 조건에 몇 행이 걸릴까」를 미리 어림합니다. 그러려면 열의 값이 어떻게 퍼져 있는지를 알아야 합니다. 알아보겠다고 테이블을 다 읽으면 질의보다 비쌉니다.

그래서 열마다 값의 분포를 히스토그램으로 미리 셉니다. 조건이 걸리면 해당 구간의 건수를 보고 몇 행이 남을지 어림합니다. 그 어림한 비율이 선택도입니다.

주문 테이블의 상태 열을 값마다 세어 두면, 「상태 = '취소'」라는 조건에 백만 행 중 이천 행쯤 걸린다는 어림이 그 표에서 바로 나옵니다. 남을 행이 전체의 0.002 라는 이 비율이 선택도입니다. 어림한 행 수가 적으면 인덱스를 탑니다. 많으면 테이블을 통째로 읽는 편이 쌉니다.

값이 한쪽에 심하게 몰린 열에서 이 표가 낡거나 없으면 최적화기가 실행 계획을 크게 잘못 고릅니다.

막대그래프와 가르는 선

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

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

막대 순서도 바꿀 수 없습니다. 구간이 수직선 위에 놓인 순서가 곧 막대 순서입니다.

쓰는 때와 안 쓰는 때

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

잰 건수가 적으면 쓸 까닭이 없습니다. 백 건이면 값을 그대로 들고 있어도 됩니다. 줄을 세워 중앙값을 바로 읽으면 어림하지 않은 답이 나옵니다. 건수가 적을수록 칸마다 들어가는 수도 적어서 어느 칸이 높은지가 몇 건에 휘둘립니다.

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

관련 항목

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

이진 탐색 · 정렬 · 선택 알고리즘 · 구간 트리 · 누적 합