Portability | portable |
---|---|

Stability | experimental |

Maintainer | mkscrg@gmail.com |

Safe Haskell | Safe-Infered |

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.

- data HashRing a
- empty :: Int -> HashRing a
- singleton :: (Ord a, Hashable a) => Int -> a -> HashRing a
- (!) :: Hashable b => HashRing a -> b -> a
- null :: HashRing a -> Bool
- size :: HashRing a -> Int
- replicas :: HashRing a -> Int
- member :: Ord a => a -> HashRing a -> Bool
- lookup :: Hashable b => b -> HashRing a -> Maybe a
- find :: Hashable b => b -> HashRing a -> a
- insert :: (Ord a, Hashable a) => a -> HashRing a -> HashRing a
- delete :: (Ord a, Hashable a) => a -> HashRing a -> HashRing a
- fromList :: (Ord a, Hashable a) => Int -> [a] -> HashRing a
- toList :: HashRing a -> [a]

# Map type

# Construction

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

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

# Operators

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

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

# Query

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

Get the node in the ring corresponding to a message, or `Nothing`

if the
ring is empty.

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

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