다중 선택 해싱(Multiple Choice Hashing)은 여러 개의 해시 함수를 사용한다는 점에서 그 이름이 유래했습니다.
- 높은 수준에서 보면, 여러 해시 함수가 존재할 때 각 항목(item)은 여러 버킷(bucket)에 동시에 매핑되며, 알고리즘 설계자는 그중 어느 버킷에 항목을 저장할지 자유롭게 선택할 수 있습니다.
- 흥미롭게도 이러한 선택의 자유 덕분에, 단일 해시 함수만 사용했을 때보다 훨씬 균형 잡힌 할당(allocation)을 달성하는 알고리즘을 설계할 수 있음이 밝혀졌습니다.
- 본 글에서는 이러한 알고리즘의 핵심 아이디어와 함께, 알고리즘이 만들어내는 할당의 상한(bounds)을 증명하기 위해 활용되는 주요 수학적 도구들을 소개합니다.
- 또한 이 분석 기법이 기본 모델의 다양한 변형에도 충분히 강건하여, 실제 응용 분야에서 이 알고리즘들이 높은 효과를 발휘하는 이유를 잘 설명해 준다는 점을 확인할 수 있습니다.
공-통(Balls-into-Bins) 모델로 이해하는 다중 선택 해싱
다중 선택 해싱 알고리즘은 '공-통(balls-into-bins)' 모델의 예시를 통해 직관적으로 설명할 수 있습니다.
- 부하 분산(load balancing) 과정을 분석하기 위한 일반적인 프레임워크는 바로 '공(ball)'과 '통(bin)'의 개념입니다. 여기서 수요(키, 프로세스, 파일 등)는 '공'으로 표현되고, 자원의 공급(테이블 슬롯, 서버, 저장 장치 등)은 '통'으로 표현됩니다.
- 이 설정에서 m개의 공이 미리 정해진 할당 규칙(allocation rule)에 따라 순차적으로 n개의 통에 던져집니다.
- 목표는 전체 과정이 완료된 후 공들이 통에 어떻게分配되었는지를 이해하는 것이며, 일반적으로 가장 많이 적재된(max-loaded) 통의 부하(=공의 개수)에 대한 상한을 구하는 것입니다.
- 이 모델에서 공의 배치는 하나 이상의 해시 함수를 적용하여 수행됩니다.
- 해시 함수는 공의 고유 식별자(id, 일반적으로 모델 내에 암묵적으로 존재)를 1부터 n까지 번호가 매겨진 통의 집합으로 매핑하는 역할을 담당합니다.
- 단순히 무작위로 통을 추첨하는 방식 대신 해시 함수를 사용해 공을 통에 매핑하는 것이 유용한 이유는, 이후 특정 시점에 공의 위치를 해당 id로부터 다시 복원해야 하는 경우가 실무에서 매우 흔하기 때문입니다.