Elixir에서 **HRW 해싱 알고리즘**을 활용한 분산 시스템 설계
by DD
1개월 전
조회수 10
HRW(Highest Random Weight)는 분산 시스템에서 키를 노드에 할당하는 stateless 알고리즘으로, ExHashRing의 대안으로 제시됨
기본 HRW 알고리즘은 간단하지만, 노드 수가 증가함에 따라 선형 시간 복잡도(Linear Time Complexity) 문제를 보임
HRW.Skeleton 기법을 통해 O(log n)의 시간 복잡도를 달성하여 ExHashRing에 근접하는 성능을 보임
분산 환경에서의 키 분배(Key Distribution)를 위한 다양한 해싱 함수와 가중치 부여 전략을 제공하며, ExHashRing 대비 장단점을 분석함
HRW 알고리즘의 기본 원리
HRW(Highest Random Weight)는 키와 각 노드를 결합하여 해싱 함수를 적용하고, 가장 높은 값을 반환하는 노드를 선택하는 방식이다. :erlang.phash2와 같은 빠른 해싱 함수를 사용하며, ExHashRing과 달리 별도의 상태 관리 프로세스가 필요하지 않다. 이러한 stateless 특성은 단순성과 유연성을 제공하지만, 노드 수가 증가함에 따라 성능 저하가 발생할 수 있다.
HRW.Skeleton을 통한 성능 최적화
HRW.Skeleton은 노드를 효율적인 데이터 구조로 구성하여 HRW 알고리즘의 시간 복잡도(Time Complexity)를 O(n)에서 O(log n)으로 개선한다. 이는 노드 수가 많은 환경에서 ExHashRing에 근접하는 성능을 가능하게 한다. HRW.Skeleton은 노드들을 클러스터로 묶어 각 클러스터의 주소를 계산하고, 해당 클러스터 내에서 해싱을 수행하는 방식으로 작동한다.
