Portability | portable |
---|---|
Stability | experimental |
Maintainer | mkscrg@gmail.com |
Safe Haskell | Safe-Infered |
Data.HashRing
Description
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.