An efficient implementation of consistent hashing, as described in

• David Karger et al., "Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web", 29th Annual ACM Symposium on Theory, http://dl.acm.org/citation.cfm?id=258660

In distributed computing applications, it's usually necessary route messages to some group of N nodes in the network. Message locality, wherein messages of the same kind are routed to the same node, is often desirable. "Normal" hashing, where a message's node is determined by some hash function modulo N, has the undesirable property that adding or removing a node from the network causes the key sets of all other nodes to change drastically. In contrast, consistent hashing has the property that small changes to the size of the node set cause only small changes to key sets of the nodes.

This implementation is built on top of IntMap and Set. It provides O(1) lookup functions as well as O(min(log n, R)) insertion and deletion functions, where R is the number of replica nodes used in the ring (see empty).

The key space of the ring is the full range of Int values. To insert a node, we generate (R > 0) keys by hashing the node with R successive salts, and the node is referenced by those keys in the ring. To get a node for a message, we hash the message to an Int value k and find the smallest key k' in the ring such that k <= k'. The node is the value referenced by k'. Higher values of R give a more even distribution of keys to nodes but slow down insertions and deletions of nodes. R is specified when constructing a HashRing with empty, singleton, or fromList and retrievable with replicas.

The ability of HashRing to fairly distribute messages among nodes relies on the implementations of hashWithSalt for the message and node types. For example, the default implementation for ByteString is non-uniform on short inputs, and so it's unsuitable for use with HashRing. Reimplementing hashWithSalt for your message and node types with a cryptographic hash function (like MD5 or SHA1 from the cryptohash package) will give better results.