현실 시스템을 움직이는 알고리즘과 자료구조

알고리즘 공부는 구현에 치우치기 쉽다. 시스템을 설계할 때는 「이 알고리즘이 실제 시스템의 어느 문제를 푸는가」를 아는 것이 구현 세부보다 중요하다. 그래서 자료구조와 알고리즘을 쓰임새 중심으로 묶어 본다.

일상 속 자료구조

기초 자료구조의 구현은 기초 자료구조에 있다.

시스템 설계에 자주 나오는 알고리즘

이 중 일관된 해싱, 블룸 필터, 지오해시·쿼드트리처럼 여러 설계 문제에 반복해서 나오는 것을 먼저 이해한다. 합의 알고리즘이나 CRDT는 선임 수준에서 원리를 알아 두면 된다.

블룸 필터: 중복 URL 걸러 내기

웹 크롤러는 수십억 개의 URL 중 이미 본 것을 다시 넣지 않아야 한다. 선택지는 셋이다.

flowchart LR
  M["비트 배열(크기 m)<br>0 0 0 0 0 0 0 0 0 0 0 0"]
  subgraph ADD["추가"]
    U1["url1"] --> H1["해시 A, B, C"] --> P1["위치 1, 5, 9를 1로"]
    U2["url2"] --> H2["해시 A, B, C"] --> P2["위치 3, 5, 11을 1로<br>(5는 겹친다)"]
  end
  subgraph GET["조회"]
    U3["url3"] --> H3["해시 A, B, C"] --> P3["위치 1, 3, 5"] -- "세 칸 모두 1" --> R3["#quot;아마 있다#quot;<br>실제로는 없다(거짓 양성)"]
    U4["url4"] --> P4["위치 2, 5, 9"] -- "2가 0" --> R4["#quot;확실히 없다#quot;"]
  end

• 거짓 음성은 없고 거짓 양성만 있다. 비트는 0에서 1로 세우기만 하고 되돌리지 않으므로, 한 번 넣은 원소의 k칸은 언제까지나 1이다. 그래서 "없다"(어느 한 칸이 0)는 답은 항상 맞다. 반대로 "있다"는 다른 원소들이 세운 비트가 우연히 k칸을 모두 덮었을 때도 나오므로 틀릴 수 있다. 크롤러가 새 URL을 가끔 놓치는 것은 감수할 수 있으므로 잘 맞는다.
• 거짓 양성률은 비트 배열 크기 m, 해시 함수 개수 k, 넣은 원소 수 n으로 정해진다. 근사식은 p ≈ (1 - e^(-kn/m))^k이고, 가장 낮아지는 k는 (m/n)·ln 2다. 이때 원소당 약 9.6비트면 1%, 14.4비트면 0.1%다. 원소가 기대보다 많이 들어오면 비율이 급격히 나빠지므로 기대 원소 수에 맞춰 크기를 미리 잡는다.
• 해시 함수는 고르게 퍼지고 빨라야 한다. 암호 해시 대신 MurmurHash, xxHash 같은 비암호 해시를 쓴다.
• 기본 블룸 필터는 원소를 지울 수 없다. 지우려고 비트를 0으로 되돌리면 그 비트를 함께 쓰던 다른 원소가 "없다"로 나와 거짓 음성이 생긴다. 삭제가 필요하면 칸마다 비트 대신 카운터를 두는 카운팅 블룸 필터나 쿠쿠 필터를 쓴다.

크롤러 전체 설계에서 블룸 필터가 놓이는 자리는 대규모 웹 크롤러 설계에 있다.

세상을 움직이는 아홉 가지 알고리즘

검색 엔진, SNS, Wi-Fi, 휴대폰, 위성까지 일상 기술 밑에는 다음 알고리즘이 있다.

정리

• 자료구조는 쓰임새로 기억한다. 실행 취소는 스택, 캐시는 해시 테이블, 스케줄링은 힙, 위치 검색은 R-트리다.
• 대규모 시스템의 단골 알고리즘은 일관된 해싱, 지오해시·쿼드트리, 블룸 필터, 근사 집계(HyperLogLog, Count-Min Sketch), 속도 제한, 머클 트리, 합의다.
• 블룸 필터는 "확실히 없다"를 싸게 판정한다. 거짓 양성을 감수할 수 있는 곳에 쓴다.
• 설계에서는 구현보다 어떤 문제를 어떤 대가로 푸는지를 설명할 수 있어야 한다.

관련 노트: 기초 자료구조, 대규모 웹 크롤러 설계, 데이터베이스 샤딩, 시스템 설계의 선택지와 흔한 문제의 해법, 빅오 표기법과 시간 복잡도, 데이터 압축: 무손실과 손실, 실시간 트렌딩과 Top-K 집계