Elixir에서 **HRW 해싱 알고리즘**을 활용한 분산 시스템 설계

HRW(Highest Random Weight)는 키와 각 노드를 결합하여 해싱 함수를 적용하고, 가장 높은 값을 반환하는 노드를 선택하는 방식이다. :erlang.phash2와 같은 빠른 해싱 함수를 사용하며, ExHashRing과 달리 별도의 상태 관리 프로세스가 필요하지 않다. 이러한 stateless 특성은 단순성과 유연성을 제공하지만, 노드 수가 증가함에 따라 성능 저하가 발생할 수 있다.

HRW.Skeleton은 노드를 효율적인 데이터 구조로 구성하여 HRW 알고리즘의 시간 복잡도(Time Complexity)를 O(n)에서 O(log n)으로 개선한다. 이는 노드 수가 많은 환경에서 ExHashRing에 근접하는 성능을 가능하게 한다. HRW.Skeleton은 노드들을 클러스터로 묶어 각 클러스터의 주소를 계산하고, 해당 클러스터 내에서 해싱을 수행하는 방식으로 작동한다.

HRW와 ExHashRing의 성능 비교 결과, 노드 수가 적을 때는 큰 차이가 없지만, 노드 수가 증가함에 따라 HRW의 성능이 저하된다. HRW.Skeleton은 ExHashRing에 비해 약 3배 느리지만, NIF(Native Implemented Functions)와 상태 관리 프로세스가 필요 없다는 장점이 있다. 벤치마크 결과(Benchmark Results)에 따르면, HRW.Skeleton은 10,000개의 노드에서 141µs의 평균 처리 시간을 보였다.

HRW는 분산 환경에서 키를 노드에 균등하게 분배하는 데 사용된다. 다양한 해싱 함수를 지원하며, :erlang.phash2, Murmur3 등을 활용하여 키 분배의 효율성을 높일 수 있다. 또한, HRW.Weighted를 통해 노드에 가중치를 부여하여 이기종 클러스터(Heterogeneous Clusters)에서 유연한 키 할당을 지원한다. HRW.Bounded는 키의 범위를 미리 알고 있는 경우, 키 분배의 정밀도를 높이는 데 사용된다.