4장: 일관된 해싱과 확률적 자료구조

3장의 후반부는 이론에서 자료구조로 넘어간다. 앞에서 본 CAP나 합의 알고리즘이 "무엇을 포기할지"에 관한 이야기였다면, 여기서 다루는 것들은 "제한된 메모리와 노드 변동 속에서 어떻게 실용적으로 버틸지"에 관한 도구다.

모듈로 해싱의 문제

분산 저장소에서 키를 노드에 배정하는 가장 단순한 방법은 모듈로 해싱이다. 키를 해시 값으로 변환한 뒤 노드 개수로 나눈 나머지를 사용해 노드를 정한다.

node = hash(key) % N

문제는 N이 바뀌는 순간 드러난다. 노드 하나가 죽어서 N이 5에서 4로 줄면, 나머지 연산 결과가 거의 모든 키에서 달라진다. 즉 전체 데이터를 다시 매핑해야 한다. 책의 표현대로, 일부 서버가 죽으면 다음 서버가 고장난 서버의 작업까지 떠안게 되어 과부하 연쇄 반응이 일어난다.

일관된 해싱

일관된 해싱(Consistent Hashing) 은 이 문제를 해결한다. 데이터를 여러 노드에 효율적으로 분배하면서, 노드를 추가하거나 삭제할 때 옮겨야 하는 데이터를 최소화하는 방식이다.

핵심 아이디어는 해시 공간을 원형 링으로 보는 것이다. 노드와 키를 모두 같은 해시 공간에 배치하고, 각 키는 링을 시계 방향으로 돌면서 처음 만나는 노드에 배정된다.

노드 C가 죽으면 C가 담당했던 구간의 키만 링을 따라 다음 노드(D)로 넘어간다. 나머지 노드의 키 배정은 그대로다. 노드를 추가할 때도 마찬가지로 인접한 한 구간만 영향을 받는다. 결국 일관된 해싱이 개선하는 것은 확장성과 장애 허용성이다.

가상 노드

일관된 해싱만으로는 부하가 고르게 분산되지 않는다. 노드 수가 적으면 링 위의 구간 크기가 제각각이 되어, 어떤 노드는 넓은 구간을 담당하고 어떤 노드는 좁은 구간만 담당한다.

그래서 실제 구현에서는 가상 노드(Virtual Node) 를 쓴다. 물리 노드 하나를 링 위의 여러 지점에 반복 배치하는 방식이다. 물리 노드 A를 A-1, A-2, ..., A-150처럼 링 위에 흩어 놓으면, 각 물리 노드가 담당하는 총 구간의 합이 통계적으로 균등해진다. 노드 하나가 죽었을 때 그 부하가 특정 이웃 하나에 몰리지 않고 여러 노드에 나뉘어 흡수되는 부수 효과도 얻는다.

블룸 필터

여기서부터는 확률적 자료구조(Probabilistic Data Structure) 다. 정확한 답을 포기하는 대가로 메모리를 극적으로 줄인다.

블룸 필터(Bloom Filter) 는 특정 요소가 집합에 속해 있는지를 아주 적은 메모리로 확인하는 구조다. 해시 함수 k개와 크기 m의 비트 배열로 구성된다.

[삽입] 원소 x에 대해 h1(x), h2(x), ..., hk(x) 위치의 비트를 1로 설정
[조회] 원소 y에 대해 h1(y) ~ hk(y) 위치의 비트가 모두 1이면 "있을 수도 있음"
       하나라도 0이면 "확실히 없음"

블룸 필터의 성격은 비대칭이다.

다른 원소들이 남긴 1 비트가 우연히 겹쳐서 "있다"로 보일 수 있기 때문이다. 해시 함수 개수 k와 비트 배열 크기 m을 조절하면 거짓 양성 확률을 원하는 수준까지 낮출 수 있다.

활용 사례는 이 비대칭성을 잘 이용하는 곳들이다.

• 포함 여부 검사(Membership Testing) — 원소가 있는지 빠르게 걸러낸다
• 캐싱 — 캐시에 있을 가능성이 없으면 캐시 조회 자체를 생략한다
• 데이터베이스 최적화 — 디스크에 없는 키를 조회하는 비용을 절약한다
• 네트워크 라우팅 — 전송 가능한 목적지를 파악한다
• 중복 제거 — 대규모 데이터에서 중복 항목을 확인한다

카운트-민 스케치

카운트-민 스케치(Count-Min Sketch) 는 데이터 스트림에서 요소의 빈도를 추정하는 확률적 자료구조다. 블룸 필터가 "있는가/없는가"를 다룬다면, 이쪽은 "몇 번 나왔는가"를 다룬다.

구조는 2차원 카운터 배열이다. 행의 개수는 해시 함수의 개수이고, 열의 개수는 각 행의 배열 크기다. 두 값이 정확도와 오류율을 결정한다.

[삽입] 원소 x가 들어오면 각 행 i에 대해 counter[i][h_i(x)] += 1

[조회] 원소 x의 빈도 추정 = min( counter[1][h_1(x)], ..., counter[k][h_k(x)] )

조회할 때 최솟값을 쓰는 이유가 이 구조의 핵심이다. 해시 충돌이 일어나면 다른 원소의 카운트가 섞여 들어와 값이 실제보다 커진다. 절대로 작아지지는 않는다. 따라서 여러 행의 값 중 가장 작은 값이 실제 빈도에 가장 가까운 추정치가 된다. 이름의 "Min"이 여기서 나온다.

활용 사례는 다음과 같다.

• 빈도 추정 — 스트림에서 자주 등장하는 항목 파악
• 트래픽 분석 — 특정 프로토콜이나 네트워크 주소 관련 패킷/흐름 수 파악
• 웹 분석 — 방문 횟수, 클릭 수, 사용자 상호 작용 빈도 추적
• 분산 시스템 — 여러 노드에 걸친 요청 빈도 추적
• 데이터 스트림 처리 — 전체를 메모리에 담을 수 없을 때 근사값으로 빈도 추정

하이퍼로그로그

하이퍼로그로그(HyperLogLog, HLL) 는 집합 내 중복되지 않은 요소의 개수, 즉 카디널리티(Cardinality) 를 매우 적은 메모리로 추정하는 알고리즘이다. 집합 크기와 상관없이 고정된 양의 메모리만 사용한다는 점이 결정적이다.

책이 설명하는 절차는 이렇다.

1. 데이터를 해시 함수에 통과시켜 해시값을 얻고, 앞쪽 비트를 버킷 선택용으로 분리한다. 예를 들어 011000010101...에서 앞 세 자리 011을 버킷 인덱스로 쓰기로 하면, 버킷 수는 2의 3승, 즉 8개가 된다.
2. 나머지 해시값에서 연속으로 나오는 0의 개수를 세고 1을 더한다. 이는 결과적으로 첫 번째 1이 등장하는 위치를 구하는 것이다.
3. 해당 버킷의 레지스터에 저장된 현재 값과 비교해 더 큰 값을 저장한다.
4. 모든 레지스터 값을 조화 평균 방식으로 결합해 최종 추정치를 구한다.

직관은 이렇다. 해시값이 균등하게 분포한다면, 앞에 0이 10개 연속으로 나오는 값을 관측했다는 것은 대략 2의 10승 개 정도의 서로 다른 원소를 봤다는 신호다. 이 관측을 여러 버킷에 나누어 평균하면 분산이 줄어든다.

실무에서는 레디스의 PFADD / PFCOUNT 명령이 하이퍼로그로그를 그대로 제공한다. 12KB 남짓의 고정 메모리로 수억 개 규모의 고유 방문자 수를 오차 1% 미만으로 추정할 수 있다. 정확한 집합을 유지하려 했다면 원소 수에 비례하는 메모리가 필요했을 일이다.

세 구조를 나란히 놓고 보기

세 자료구조는 같은 계열이지만 답하는 질문이 다르다.

공통점은 오차의 방향이 예측 가능하다는 것이다. 블룸 필터는 절대 거짓 음성을 내지 않고, 카운트-민 스케치는 절대 과소 추정하지 않는다. 이 성질이 있어야 시스템 설계에 안전하게 끼워 넣을 수 있다. 오차가 어느 방향으로든 날 수 있다면 그 위에 논리를 쌓을 수 없다.

정리

일관된 해싱은 노드가 들어오고 나가는 환경에서 데이터 이동을 최소화하는 배치 전략이고, 가상 노드는 그 배치를 균등하게 만드는 보정 장치다. 이 조합은 5장의 키-값 저장소 설계에서 그대로 재등장한다.

확률적 자료구조 세 개는 "정확한 답이 필요 없는 곳에서는 정확성을 팔아 메모리를 산다"는 하나의 아이디어에서 나온 변형들이다. 하이퍼로그로그 절에서 확인한 대로 책의 설명이 곳에 따라 단순화되어 있으므로, 실제로 도입할 때는 원 논문이나 구현체 문서를 한 번 더 확인하는 편이 안전하다.