Data.HashRing

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.

Map type

data HashRing a

The constructor for this data type is not exported. See empty, singleton, or fromList.

Note that HashRing is parameterized by the node type and not by the message type. As made clear by the type signatures for !, find, and lookup, any Hashable type can be used as a message.

Instances

Eq a => Eq (HashRing a)

(Read a, Ord a, Hashable a) => Read (HashRing a)

Show a => Show (HashRing a)

Construction

empty :: Int -> HashRing a

Construct an empty ring with a specific R value.

singleton :: (Ord a, Hashable a) => Int -> a -> HashRing a

Construct a single-node ring with a specific R value.

Operators

(!) :: Hashable b => HashRing a -> b -> a

Get the node in the ring corresponding to a message, or error if the ring is empty.

Query

null :: HashRing a -> Bool

True if the ring is empty, False otherwise.

size :: HashRing a -> Int

Number of nodes in the ring.

replicas :: HashRing a -> Int

Number of replica nodes (R) in the ring for each real node.

member :: Ord a => a -> HashRing a -> Bool

True if the node is in the ring, False otherwise.

lookup :: Hashable b => b -> HashRing a -> Maybe a

Get the node in the ring corresponding to a message, or Nothing if the ring is empty.

find :: Hashable b => b -> HashRing a -> a

Get the node in the ring corresponding to a message, or error if the ring is empty.

Insertion

insert :: (Ord a, Hashable a) => a -> HashRing a -> HashRing a

Add a node to the ring.

Deletion

delete :: (Ord a, Hashable a) => a -> HashRing a -> HashRing a

Remove a node from the ring.

Conversion

fromList :: (Ord a, Hashable a) => Int -> [a] -> HashRing a

Construct a ring from an R value and a list of nodes.

toList :: HashRing a -> [a]

Construct a list containing the nodes in the ring.