Mastering Consistent Hashing: Custom Ordered Map and Performance Tips

Background

Consistent hashing is frequently asked in interviews to test understanding of its principle and problem solving. It is used in distributed IM systems to select a service node after client login.

Consistent hashing builds a ring of size 2^32‑1, maps service nodes and client keys onto the ring, and selects the nearest node clockwise; virtual nodes are introduced to balance distribution.

Custom Ordered Map

We can simulate the ring with a custom ordered array (SortArrayMap). The process includes initializing an array, inserting hashed nodes, sorting, hashing the client key, and traversing to find the first node with a hash greater or equal, wrapping to the first node if none is found.

Best case O(1), worst case O(N) lookup.

Implementation details: a SortArrayMap class with an internal Node array storing hashcode and value, write logic similar to ArrayList with expansion, and a sort method using Arrays.sort (TimSort).

TreeMap Implementation

TreeMap provides a red‑black tree that maintains natural ordering of keys, eliminating the need for explicit sorting and improving write performance.

Performance test with one million entries shows TreeMap (≈1316 ms) is almost twice as fast as SortArrayMap (≈2237 ms).

Application in CIM

In the CIM project, the consistent‑hash algorithm is encapsulated in an abstract class AbstractConsistentHash defining template methods add, sort, getFirstNodeValue, and process. Subclasses such as SortArrayMapConsistentHash or TreeMapConsistentHash provide concrete implementations.

A RouteHandle interface with a single method routeServer(List<String> values, String key) abstracts the routing strategy. Implementations for round‑robin, consistent hash, or custom strategies can be swapped via configuration without changing client code.

Extensibility

The design allows adding new routing algorithms (e.g., random) by implementing RouteHandle and configuring the fully‑qualified class name. The client only injects RouteHandle and calls routeServer.

Conclusion

Understanding consistent hashing and its data‑structure choices helps design scalable routing mechanisms and can impress interviewers.