Highest Random Weight in Elixir
a day ago
- #Distributed Systems
- #Consistent Hashing
- #Elixir
- Consistent hashing is a common building block for distributed Elixir systems, enabling design patterns like distributed rate limiters or caches.
- ExHashRing is a battle-tested library for consistent hashing but requires stateful processes and management, unlike stateless alternatives like HRW (Highest Random Weight).
- HRW (Rendezvous hashing) offers a stateless, functional approach for key assignment, with linear complexity (O(n)) making it slower for large node counts but acceptable for smaller clusters (e.g., ~14 nodes).
- Performance benchmarks show HRW.owner is slightly slower than ExHashRing for small node counts (e.g., 1.11x slower) but significantly slower for large node counts (e.g., 4200x slower at 10K nodes).
- HRW.Skeleton optimizes HRW by using a pre-built data structure, reducing lookup time from milliseconds to microseconds and improving performance to only ~3x slower than ExHashRing for 10K nodes.
- Distribution analysis shows HRW provides better key distribution consistency across nodes compared to ExHashRing, especially at larger node counts, with hash functions like phash2 performing well.
- The hrw library on Hex.pm includes additional strategies like HRW.Weighted for heterogeneous clusters and HRW.Bounded for known key sets, offering flexibility for different use cases.