확률적 자료 구조: 일관된 해싱, 블룸 필터, 카운트 민 스케치, 하이퍼로그로그

개요

개발자를 위한 시스템 설계 수업을 읽고 있는데 확률적 자료 구조로 언급된 도구들이 재미있고 또 처음 알게된 것들도 있어 정리해본다. 다만 개념에 대한 이해보다는 어떠한 상황에서 어떠한 이점을 얻기 위해 사용하는지를 보려 한다. GPT의 도움을 받아 정리하였다.

일관된 해싱(Consistent Hashing)

해싱을 사용해 노드마다 골고루 키-값을 분산해두었는데 노드 수가 늘거나 줄면 키-값을 재배치해야 한다. 이때 재배치되는 키의 비율을 최소화 하는 것이 목표이다.

실제 사용 상황 예시

• 분산 캐시 클러스터(Memcached/Redis) 증설·축소 시 캐시 미스 폭증을 피하고 싶을 때
• 샤딩된 키-값 저장소(Cassandra/Riak 등)에서 노드 장애/교체가 잦을 때
• CDN/오브젝트 스토리지에서 콘텐츠를 엣지/스토리지 노드에 균일하게 나눌 때
• 세션 스티키니스(로그인 세션을 앱 서버에 붙여둘 때)에서 서버 수가 바뀌어도 세션 이동을 최소화하고 싶을 때
• 작업 분배(큐/스케줄러)에서 작업 키별 담당 워커를 안정적으로 고정하고 싶을 때
• 멀티테넌시에서 테넌트별 데이터/부하를 노드에 고르게 흩뿌리고 싶을 때

분산 캐시 증설을 자세히 들여다보자

상황: 4대의 Redis 캐시가 운영 중인데, 트래픽 증가로 5대로 롤링 증설해야 한다고 하자.

• 단순 모듈러 해싱(key % N)을 쓰면 N이 4→5로 바뀌는 순간 대부분의 키가 다른 노드로 튀어 캐시 미스가 폭증한다.
• 일관적 해싱을 쓰면 신규 노드가 맡게 될 키 구간만 재배치되고, 기존 키의 대다수는 원래 자리(노드)에 남는다.
• 효과: 캐시 미스 급증 억제, 네트워크 재적재 비용 감소, 사용자 지연시간 스파이크 완화.
• 운영 팁: 가용성 유지 위해 단계를 나눠 순차적으로 링에 노드를 추가(혹은 가중치↑)하고, 가상노드(vnode) 로 분산을 더 매끄럽게 만든다.

동작 개념 이해

• 해시 링: 해시 공간(예: 0..2^m−1)을 원형으로 본다. 각 노드를 해시해 링 위 여러 지점(가상노드 포함)에 배치한다.
• 키 배치: 키를 해시해 링 위에 올리고, 시계방향으로 가장 가까운 노드(첫 번째 후속 노드)를 담당자로 정한다.
• 노드 추가: 새 노드가 링에 들어오면 그 노드 “앞 구간”의 일부 키만 새 노드로 이동한다. 나머지는 그대로. (평균적으로 약 1/(노드수+1) 비율만 이동)
• 노드 제거/장애: 해당 노드가 맡던 키는 다음 노드로 넘어간다. (평균 이동량 ~1/노드수)
• 가상노드(vnode): 각 물리 노드를 링에 여러 포인트로 등록해 키 분포를 고르게 하고, 노드 성능에 따라 가중치(포인트 개수)로 비중을 조절한다.
• 복제(Replication): 내구성과 가용성을 위해 한 키를 연속된 R개 노드에 복제한다(첫 번째 후속 노드부터 R개). 단일 노드 장애로 읽기/쓰기 중단을 피한다.

마무리

• 장점
  • 노드 증감에 따른 키 이동 최소화 → 캐시 미스/재적재 비용 감소
  • 확장성과 장애 복원력 향상(복제와 결합 시)
  • 가상노드로 부하 균형과 가중치 배분 용이
• 한계/함정
  • 해시 함수가 나쁘면 핫스팟 발생(키 쏠림)
  • 노드 메타데이터(링, vnode) 관리 복잡성
  • 일관된 해싱 자체가 핫키 문제를 해결해 주지는 않음(캐시 레이어 정책, 레이트 리밋, 미러링 등 보완 필요)
• 적용 체크리스트
  • 해시 함수 품질(균등성) 확인
  • 가상노드 개수와 가중치로 노드 간 성능 차 보정
  • 복제 수(R)와 장애 시 재배치/복구 전략 명확화
  • 링 변경시 관측 가능성/모니터링 준비
  • 핫키 완화 전략(캐시 분할, TTL, 레이트리밋, 멀티겟 분산) 병행
• 알아둘 대안
  • Rendezvous/HRW 해싱: 구현이 단순, 균형 우수(링 구조 불필요).
  • Jump Consistent Hash: O(1) 계산, 메모리 거의 없음, 이동률/균형 양호.

블룸 필터(Bloom Filter)

대규모 데이터에서 “이 값이 집합에 존재하는지” 빠르게 확인할 때 쓰인다. 다만 결과는 확률적이다.

→ “없다”는 건 확실하지만, “있다”는 건 가끔 틀릴 수 있다(FP, False Positive)

실제 사용 상황 예시

• 웹 브라우저 캐시: URL이 캐시에 있는지 먼저 확인해 불필요한 디스크 접근 차단.
  • 캐시에 없는건 확실히 알려주니깐 바로 디스크로 접근
  • FP 일때는: 캐시에 있다고 했는데 없는 경우에는 디스크에 접근해야 함
• 스팸 필터링: 이메일에 블랙리스트 단어가 들어 있는지 1차 판별
  • 단어가 없는 건 빠르게 판별하므로 바로 다음 작업
  • FP 일때는: 블랙리스트 단어 있다고 해서 들여다봤더니 없었음
• 데이터베이스 쿼리 최적화: 없는 데이터를 조회하기 전 아예 걸러냄 → DB 부하 경감
  • 데이터 없는건 바로 알 수 있으니 조회하지 않음
  • FP 일때는: 있다고 해서 조회했는데 없음
• 분산 시스템의 membership 체크: 어떤 노드가 특정 키를 가지고 있는지 확인할 때
  • 없는 노드는 바로 아니깐 조회할 노드에서 제외
  • FP 일때는: 키가 있다고 해서 노드에 요청했더니 없음
• 네트워크 라우터: IP가 허용 목록에 있는지 빠르게 판별
  • 허용목록에 없는건 바로 아니깐 차단
  • FP 일때는: 허용 목록에 있다길래 확인해봤더니 없었음

데이터베이스 조회 최적화를 자세히 보자

상황: 전자상거래 DB에는 10억 개의 상품이 있다. 사용자가 특정 상품 ID를 조회한다고 하자.

• 블룸 필터 없이: 모든 요청이 DB까지 가서 SELECT ... WHERE id=... 실행 → 불필요한 조회 폭증
• 블룸 필터 적용 후:
  • 먼저 메모리에 있는 블룸 필터를 확인 → 결과가 “없음”이면 DB까지 가지 않아도 된다.
  • “있을 수도 있음”일 경우에만 DB 조회 → 트래픽과 쿼리 횟수 대폭 감소. 어쩌다 조회했는데도 없을 수는 있음.
• 효과: DB 부하 완화, 응답 속도 개선, 비용 절감
• 운영 팁: 블룸 필터는 주기적으로 재구성(리빌드)하거나 false positive율을 고려해 비트 배열 크기/해시 함수 개수를 조정해야 한다.

동작 개념 이해

• 비트 배열 초기화: N비트짜리 배열을 0으로 세팅한다.
• 데이터 삽입: 원소를 여러 개의 해시 함수로 해싱 → 각각 나온 위치의 비트를 1로 세팅
• 존재 확인: 원소를 동일한 해시 함수로 해싱 → 해당 위치 비트가 모두 1이면 “있을 수도 있음”, 하나라도 0이면 “절대 없음”
• 특징:
  • 오탐(False Positive)은 있음 (없는데 있다고 할 수 있음)
  • 누락(False Negative)은 없음 (있는데 없다고는 절대 안 함)
  • 메모리를 아주 작게 쓰면서도 대규모 집합을 다룰 수 있음

마무리

• 장점
  • 메모리 효율 극대화 (몇 MB로 수억 개 항목 관리 가능)
  • 매우 빠른 판별 속도 (O(k), k=해시 함수 수)
  • “없음”을 빠르게 보장할 수 있어 시스템 부하 절감
• 한계/함정
  • false positive 가능성 → “있다”를 맹신하면 안 됨
  • 삭제가 어렵다 (비트 충돌 때문에) → Counting Bloom Filter 같은 변형 필요
  • 해시 함수와 비트 배열 크기 설계가 잘못되면 오탐률 급증
• 적용 체크리스트
  • 목표 오탐률에 맞춰 비트 배열 크기·해시 함수 수 계산
  • 주기적 재구성 필요 여부 검토
  • false positive가 비즈니스적으로 문제 없는지 확인
• 알아둘 대안
  • Counting Bloom Filter: 원소 삭제 가능
  • Cuckoo Filter: 오탐률 낮고 삭제 용이, membership test 대안
  • Trie/HashSet: 메모리는 많이 쓰지만 정확도 100%

카운트 민 스케치(Count-Min Sketch)

대규모 스트리밍 데이터에서 “이 값이 얼마나 자주 등장했는지” 빈도를 추정할 때 쓰인다. 정확한 카운트는 아니지만, 메모리를 매우 적게 쓰면서 빈도 순위를 빠르게 계산할 수 있다.

실제 사용 상황 예시

• 네트워크 트래픽 모니터링: 어떤 IP가 얼마나 많은 요청을 보내는지 추정
• 검색 엔진 쿼리 통계: 가장 많이 입력된 검색어 집계
• 실시간 로그 분석: 어떤 이벤트가 얼마나 발생했는지 추적
• 광고 클릭 수/뷰 카운트: 대규모 로그에서 상위 인기 항목만 파악
• 스트리밍 데이터 처리 플랫폼(Kafka, Flink, Spark)에서 빠른 빈도 집계

실시간 로그 분석을 자세히 보자

상황: 한 서비스에서 매초 수백만 건의 이벤트 로그가 쏟아진다. 운영팀은 특정 에러 코드가 얼마나 발생했는지 파악하고 싶다.

• 일반 해시맵 사용: 키마다 카운트를 저장 → 메모리 폭발 (수억 개 키)
• 카운트 민 스케치 사용:
  • 각 이벤트 키를 여러 해시 함수로 해싱 → 그 위치의 카운터를 +1
  • 나중에 빈도를 조회할 때는 여러 카운트 값 중 최소값(min)을 반환
  • 정확히 “103,421번” 같은 수치는 알 수 없지만, “이 에러가 저 에러보다 많다”는 건 확실히 알 수 있다
• 효과: 메모리 수십~수백 배 절약, 실시간 대시보드 제공 가능
• 운영 팁: 주로 heavy hitter(상위 빈도 항목) 탐지에 적합. 드문 이벤트는 다소 부정확해질 수 있다.

동작 개념 이해

• 구조: 2차원 배열(가로=여러 해시 함수, 세로=카운터)
• 삽입: 키를 여러 해시 함수로 해싱해 각각 대응되는 카운터에 +1
• 조회: 같은 방식으로 해싱해 나온 카운터 값들을 확인 → 그중 최소값을 결과로 사용
• 특징:
  • “과소 추정”은 없다. 항상 실제 빈도 이상(과대 추정)으로 나온다.
  • 오차는 해시 충돌에 의해 생기며, 해시 함수 개수와 테이블 크기를 늘리면 줄어든다.
  • 메모리 크기는 O(1/ε · log 1/δ), ε=허용 오차, δ=실패 확률

마무리

• 장점
  • 스트리밍 데이터에서 실시간 빈도 추정 가능
  • 메모리 효율적 (수억 개 키도 수 MB로 추적 가능)
  • 단순 연산 → 매우 빠른 속도(O(k), k=해시 함수 수)
• 한계/함정
  • 정확한 값이 아니라 상한선 → “많이 나온 것”만 보는 데 적합
  • 드문 이벤트는 상대적으로 더 큰 오차 가능성
  • 키 삭제가 어렵다(Counting Bloom Filter처럼 확장 가능하지만 복잡해짐)
• 적용 체크리스트
  • “정확한 개수”가 필요한가? → 그렇다면 다른 방식 필요
  • “상위 인기 항목”만 빠르게 보고 싶다면 적합
  • 해시 함수 개수와 테이블 크기를 오차 허용 수준에 맞게 설계해야 함
• 알아둘 대안
  • Heavy Hitters 알고리즘 (Misra-Gries 등): 상위 빈도만 더 정확히 추적
  • HyperLogLog: 고유 항목 수(카디널리티) 추정에 특화
  • 샘플링 기법: 메모리 절약하지만 정확도는 더 떨어짐

하이퍼로그로그(HyperLogLog)

매우 큰 데이터셋에서 “고유한 원소가 몇 개인지(카디널리티)” 를 추정할 때 쓴다. 정확히 각 원소를 저장하지 않고도, 작은 메모리만으로 유니크 카운트를 계산할 수 있다.

실제 사용 상황 예시

• 웹 서비스의 DAU/MAU 집계: 중복 접속을 제거하고 순수한 사용자 수 추정
• 광고 노출/클릭 추적: 몇 명의 서로 다른 유저가 봤는지 계산
• IoT 센서 네트워크: 고유한 장치 수 추정 (중복 보고 제거)
• 로그 분석 플랫폼: 유니크 에러 코드, 유니크 IP, 유니크 URL 개수 추정
• 데이터 웨어하우스: “유니크 고객 수” 같은 메트릭을 빠르게 얻을 때

DAU(일간 활성 사용자 수) 집계를 자세히 보자

상황: 글로벌 SNS에서 하루 수억 명이 접속한다. 운영팀은 매일 **“오늘 접속한 고유 사용자 수”**를 대시보드에 띄워야 한다.

• 단순 방식: 모든 사용자 ID를 Set에 저장 후 크기를 세면 정확하지만, 메모리가 엄청나게 든다(수억 개 ID × 수 바이트).
• 하이퍼로그로그 사용:
  • 각 사용자 ID를 해싱해 특정 패턴(해시값 내 가장 긴 0의 길이 등)을 관찰.
  • 통계적으로 “이 정도 패턴이 나왔으니 대략 몇 명이다”를 계산.
  • 결과: 단 몇 MB 메모리로도 수십억 개 사용자의 유니크 카운트를 오차율 1~2% 이내로 추정 가능.
• 효과: 실시간 대시보드에서 빠르고 싸게 지표 제공 가능.

동작 개념 이해

• 핵심 아이디어: 랜덤 해시값을 보면 “긴 0이 몇 번 나왔는가”가 전체 개수와 통계적으로 비례한다.
• 구조: 해시값을 여러 구간(bucket)에 나눠 기록하고, 각 구간에서 “가장 긴 0의 접두사 길이”를 추적한다.
• 추정치 계산: 모든 구간의 통계를 합쳐서 전체 유니크 원소 수를 추정.
• 특징:
  • 메모리 사용량은 입력 데이터 개수와 무관 → 고정적 (예: 12KB로 10억 원소 추정 가능)
  • 오차율은 약 ±1~2% 수준 (파라미터에 따라 조절 가능)
  • 정확히 어떤 원소가 있었는지는 알 수 없다 (집합 자체를 복원 불가)

마무리

블룸 필터가 “있나/없나”, 카운트 민 스케치가 “얼마나 자주 나오나” 라면, 하이퍼로그로그는 “서로 다른 게 몇 개나 있나”를 추정하는 도구라고 할 수 있다.

• 장점
  • 극도로 적은 메모리로도 수십억 개 고유 원소 개수 추정 가능
  • 빠른 계산 속도 (O(1) 업데이트)
  • 빅데이터 환경에서 실시간 집계에 적합
• 한계/함정
  • 개별 원소 정보를 전혀 알 수 없음 (단순히 “몇 개나 있다”만 알 수 있음)
  • 카디널리티 추정에만 특화 → 빈도 분석에는 쓸 수 없음
  • 작은 데이터셋에서는 오차가 크게 느껴질 수 있음
• 적용 체크리스트
  • 목표 오차율에 맞게 파라미터 선택
  • “정확히 몇 명”이 아니라 “대략 몇 명”이 중요한 지표인지 확인
  • 원소 자체를 추적해야 하는 경우에는 다른 방법 사용
• 알아둘 대안
  • Exact Set/HashSet: 메모리는 많이 쓰지만 정확도 100%
  • Linear Counting: 작은 집합에는 더 효과적
  • Count-Min Sketch: 빈도 추정에 특화, 카디널리티가 아니라 “얼마나 자주”를 보고 싶을 때 적합

마지막으로 한 문장씩으로 복습

• 일관된 해싱(Consistent Hashing) → 노드 수가 변해도 데이터 재배치를 최소화하며 분산 저장을 안정적으로 운영할 때 쓴다.
• 블룸 필터(Bloom Filter) → 값이 존재하는지 여부를 빠르게 판별해야 하고, 약간의 오탐(false positive)을 감수할 수 있을 때 쓴다.
• 카운터 민 스케치(Count-Min Sketch) → 스트리밍 데이터에서 어떤 항목이 얼마나 자주 등장하는지 빈도를 추정할 때 쓴다.
• 하이퍼로그로그(HyperLogLog) → 대규모 데이터에서 서로 다른 항목(고유 수)의 개수를 메모리 효율적으로 추정할 때 쓴다.