해시 심화 (블룸필터, 일관성해싱)
자료구조 #6에서 해시 테이블의 기본을 다뤘다면, 본 글은 그 응용으로 한 단계 더 들어간다. 거대한 데이터 셋에서 "존재 여부"를 메모리 단 몇 비트로 검사하는 블룸 필터(Bloom Filter), 분산 캐시·분산 DB에서 노드를 추가·제거할 때 키 재배치를 최소화하는 일관성 해싱(Consistent Hashing), 그리고 암호학적 해시 함수의 핵심 성질까지 — 해시가 시스템 설계 전반에서 어떻게 변형되어 쓰이는지를 세심하게 정리한다(출처: 위키백과 — Bloom filter). 제가 학교 캡스톤에서 사용자가 100만 명 가까이 늘었을 때 "이 이메일이 가입자 목록에 있는지" 검사를 매번 DB 쿼리로 하다가 화면 응답이 5초 가까이 늦어진 사고를 겪고 나서, 블룸 필터를 앞단에 두자 99%의 요청을 메모리 1ms에서 처리하게 된 모습을 본 후로는 "해시는 단순한 자료구조가 아니라 시스템 설계의 무기"라는 사실을 손끝으로 받아들였다.
해시 함수의 핵심 성질과 충돌 해결 복습
해시 함수는 임의 크기의 입력을 고정 크기의 출력으로 매핑하는 함수이며, 좋은 해시 함수는 네 가지 핵심 성질을 만족해야 한다. 시험에서 자주 출제되는 정리이다.
| 성질 | 의미 |
|---|---|
| 결정성 (Determinism) | 같은 입력에 대해 항상 같은 출력 |
| 균일성 (Uniformity) | 출력이 가능한 범위에 균등하게 분포 |
| 효율성 (Efficiency) | O(1)에 가까운 계산 비용 |
| 충돌 저항성 (Collision Resistance) | 다른 입력이 같은 출력을 가질 확률이 매우 낮음 |
자료구조의 해시 테이블에서 충돌(collision)은 피할 수 없으며, 두 가지 표준 해결 방식이 있다. 체이닝(Chaining)은 같은 버킷에 연결 리스트(또는 트리)를 매달아 충돌된 모든 키를 저장하는 방식이고, 개방 주소법(Open Addressing)은 충돌 시 다음 빈 슬롯을 찾아가는 방식(선형 탐사·이차 탐사·이중 해싱)이다.
| 충돌 해결 | 강점 | 약점 |
|---|---|---|
| 체이닝 | 적재율 1 이상도 동작 · 삭제 단순 | 메모리 할당 비용 · 캐시 지역성 약함 |
| 개방 주소법 | 캐시 지역성 강함 · 추가 메모리 없음 | 적재율 0.7 이상이면 급격히 느려짐 |
| Java HashMap (8 이상) | 체이닝 + 체인 길이 8 이상이면 트리(RB-Tree)로 변환 | 최악 O(log n) 보장 |
여기서 적재율(load factor)이란 해시 테이블의 (저장된 항목 수) / (전체 버킷 수) 비율을 가리키며, 적재율이 임계치(보통 0.75)를 넘으면 테이블 크기를 두 배로 늘리고 모든 항목을 새 자리에 다시 해싱하는 리해싱(rehashing)이 발생한다. 리해싱은 한 번 일어날 때 O(n)이지만 평균적으로는 O(1)로 분산되므로 amortized 분석에서 해시 테이블의 평균 연산이 여전히 O(1)이 된다.
# 파이썬 dict의 평균 O(1) 보장 검증
import time
d = {}
n = 10_000_000
t0 = time.time()
for i in range(n):
d[i] = i
print(f'10M 삽입: {time.time() - t0:.2f}s') # 약 2초 (n당 200ns)
t0 = time.time()
for i in range(n):
_ = d[i]
print(f'10M 조회: {time.time() - t0:.2f}s') # 약 1초솔직히 제 경험상 학교에서 처음 파이썬 dict이 1000만 건에서도 1초 안에 처리된다는 사실을 직접 측정해 본 후로는 "거의 모든 일상 자료구조 선택은 dict(해시) 또는 list"라는 단순한 결론에 도달했고, 다른 자료구조는 명확한 이유가 있을 때만 사용한다는 패턴이 자리 잡았다.
블룸 필터 — "있는 건 모르고, 없는 건 확실하다"
블룸 필터(Bloom Filter)는 1970년 버튼 H. 블룸이 제안한 확률적 자료구조로, "어떤 원소가 집합에 있는가?"를 매우 적은 메모리로 빠르게 검사한다. 핵심 트릭은 k개의 독립적인 해시 함수로 입력을 비트 배열의 k개 위치에 매핑하고, 그 k 비트를 모두 1로 켜는 일이다.
| 동작 | 절차 |
|---|---|
| 삽입 | k개 해시 위치를 모두 1로 켜기 |
| 조회 | k개 위치가 모두 1이면 "있을 수도" · 하나라도 0이면 "확실히 없음" |
여기서 거짓 양성(false positive)은 가능하지만 거짓 음성(false negative)은 불가능하다는 비대칭이 블룸 필터의 결정적 특징이다. 즉 "있다"는 답은 틀릴 수 있어도, "없다"는 답은 항상 맞다. 이 비대칭이 캐시·DB의 앞단에 블룸 필터를 두어 "확실히 없는" 요청은 즉시 거절하고, "있을 수도 있는" 요청만 실제 저장소에 보내는 패턴을 가능하게 한다.
import hashlib
class BloomFilter:
def __init__(self, size=10000, k=3):
self.size = size
self.k = k
self.bits = [0] * size
def _hashes(self, item):
for i in range(self.k):
# 단일 해시 + seed 트릭으로 k개 해시 시뮬레이션
h = hashlib.md5(f'{item}:{i}'.encode()).hexdigest()
yield int(h, 16) % self.size
def add(self, item):
for idx in self._hashes(item):
self.bits[idx] = 1
def contains(self, item):
return all(self.bits[idx] for idx in self._hashes(item))
bf = BloomFilter(size=10000, k=3)
for email in ['a@x.com', 'b@x.com', 'c@x.com']:
bf.add(email)
print(bf.contains('a@x.com')) # True (실제 있음)
print(bf.contains('z@x.com')) # False (확실히 없음)
print(bf.contains('q@x.com')) # 대개 False, 가끔 True (false positive)블룸 필터의 메모리 효율은 압도적이다. 1000만 원소를 1%의 거짓 양성률로 처리하는 데 약 12MB만 필요하며, 같은 일을 해시 셋(set)으로 하면 수백 MB가 든다. 실제로 Chrome의 안전 브라우징 캐시·Bitcoin SPV 클라이언트·Cassandra·HBase·Redis Bloom 모듈 같은 거대 시스템이 블룸 필터를 핵심 부품으로 사용한다.
블룸 필터의 한계는 두 가지다. 첫째, 원소 삭제가 불가능하다(한 비트를 0으로 돌리면 다른 원소에도 영향). 이를 해결하려고 카운팅 블룸 필터(Counting Bloom Filter, 비트 대신 작은 카운터 사용)가 만들어졌다. 둘째, 거짓 양성률은 적재율과 비트 배열 크기로 결정된다. 메모리 절약과 정확도가 트레이드오프이며, 어떤 비율로 둘지가 시스템 설계의 결정 포인트다.
일관성 해싱 — 분산 시스템의 키 배치 표준
일관성 해싱(Consistent Hashing)은 분산 캐시·분산 DB에서 키를 여러 노드에 분배할 때, 노드가 추가되거나 제거되어도 재배치되는 키의 비율을 최소화하는 해시 기법이다. 1997년 MIT의 David Karger 등이 분산 웹 캐시의 부하 분산을 위해 제안했으며, Amazon DynamoDB·Apache Cassandra·Redis Cluster·Akka Cluster·Discord의 메시지 라우팅이 모두 일관성 해싱 변형을 사용한다(출처: 위키백과 — Consistent hashing).
| 비교 항목 | 단순 모듈로 해싱 (hash(key) % n) |
일관성 해싱 |
|---|---|---|
| 노드 추가·제거 시 재배치 | 거의 모든 키 (n이 바뀜) | k/n만큼만 (k=키 수, n=노드 수) |
| 부하 균형 | 균등 | 가상 노드(virtual node)로 균등 |
| 구현 복잡도 | 한 줄 | 링·이진 탐색·가상 노드 필요 |
여기서 단순 hash(key) % n 방식의 결정적 약점은 노드 수 n이 1만 바뀌어도 거의 모든 키의 매핑이 달라진다는 점이다. 분산 캐시에서 노드 한 대 추가했을 뿐인데 캐시 적중률이 0%로 떨어지는 사고가 정확히 이 이유 때문에 발생한다. 일관성 해싱은 노드와 키를 같은 해시 공간의 원형 링 위에 올려놓고, 각 키를 시계 방향으로 만나는 첫 노드에 배치해 노드 변화의 영향을 일부 키에만 한정한다.
import hashlib
import bisect
class ConsistentHash:
def __init__(self, nodes, virtual_replicas=150):
self.virtual_replicas = virtual_replicas
self.ring = [] # 정렬된 (hash, node) 리스트
self.hash_to_node = {}
for n in nodes:
self.add_node(n)
def _hash(self, key):
return int(hashlib.md5(key.encode()).hexdigest(), 16)
def add_node(self, node):
for i in range(self.virtual_replicas):
h = self._hash(f'{node}:{i}')
bisect.insort(self.ring, h)
self.hash_to_node[h] = node
def remove_node(self, node):
for i in range(self.virtual_replicas):
h = self._hash(f'{node}:{i}')
self.ring.remove(h)
del self.hash_to_node[h]
def get_node(self, key):
if not self.ring: return None
h = self._hash(key)
idx = bisect.bisect_right(self.ring, h) % len(self.ring)
return self.hash_to_node[self.ring[idx]]
ch = ConsistentHash(['node-A', 'node-B', 'node-C'])
print(ch.get_node('user:1234')) # 예: node-B
print(ch.get_node('user:9999')) # 예: node-A여기서 가상 노드(virtual node)란 한 물리 노드를 링 위에 150개 정도 분산 배치해 한 노드가 빠질 때 그 부하가 다른 노드들에 골고루 흩어지도록 만드는 기법을 가리키며, 가상 노드가 없으면 각 노드의 부하가 들쭉날쭉해진다. Cassandra·DynamoDB·Akka가 모두 가상 노드 개념을 표준으로 채택했다.
솔직히 이건 예상 밖이었는데, 학교에서 처음 일관성 해싱을 배웠을 때는 "왜 이렇게 복잡하게 링까지 만들지" 싶었다가, 실제 운영 환경에서 캐시 노드 1대 추가에 적중률이 무너지는 사고를 본 후로는 "분산 시스템에서 해시는 자료구조가 아니라 인프라"라는 점을 손끝으로 받아들였다. 마지막으로 시험 답안에서 자주 쓰이는 정형 표현을 정리하면, "블룸 필터는 k개의 해시 함수로 비트 배열에 매핑해 '존재 여부'를 O(k) 시간·O(m) 비트 공간에 검사하는 확률적 자료구조로, 거짓 양성은 가능하지만 거짓 음성은 불가능하다. 일관성 해싱은 노드와 키를 원형 해시 링 위에 올려 노드 변화 시 재배치되는 키의 비율을 최소화하는 분산 시스템의 표준 키 배치 기법이며, 가상 노드로 부하 균형을 보장한다"는 두 문장이 표준 답안 표현으로 통한다.
메타 디스크립션: 해시 함수의 4대 핵심 성질과 충돌 해결(체이닝·개방주소법), 블룸 필터의 비대칭(거짓 양성 가능·거짓 음성 불가능)과 메모리 효율, 일관성 해싱과 가상 노드를 통한 분산 시스템의 키 배치를 자료구조 입문자 관점에서 세심하게 정리합니다.