-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Efficient consistent hashing. -- -- An efficient implementation of consistent hashing. See the -- documentation for Data.HashRing for more info. @package hashring @version 0.0.0 -- | An efficient implementation of consistent hashing, as described in -- -- -- -- 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. module Data.HashRing -- | 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. data HashRing a -- | Construct an empty ring with a specific R value. empty :: Int -> HashRing a -- | Construct a single-node ring with a specific R value. singleton :: (Ord a, Hashable a) => Int -> a -> HashRing a -- | Get the node in the ring corresponding to a message, or error if the -- ring is empty. (!) :: Hashable b => HashRing a -> b -> a -- | True if the ring is empty, False otherwise. null :: HashRing a -> Bool -- | Number of nodes in the ring. size :: HashRing a -> Int -- | Number of replica nodes (R) in the ring for each real node. replicas :: HashRing a -> Int -- | True if the node is in the ring, False otherwise. member :: Ord a => a -> HashRing a -> Bool -- | Get the node in the ring corresponding to a message, or -- Nothing if the ring is empty. lookup :: Hashable b => b -> HashRing a -> Maybe a -- | Get the node in the ring corresponding to a message, or error if the -- ring is empty. find :: Hashable b => b -> HashRing a -> a -- | Add a node to the ring. insert :: (Ord a, Hashable a) => a -> HashRing a -> HashRing a -- | Remove a node from the ring. delete :: (Ord a, Hashable a) => a -> HashRing a -> HashRing a -- | Construct a ring from an R value and a list of nodes. fromList :: (Ord a, Hashable a) => Int -> [a] -> HashRing a -- | Construct a list containing the nodes in the ring. toList :: HashRing a -> [a] instance Eq a => Eq (HashRing a) instance (Read a, Ord a, Hashable a) => Read (HashRing a) instance Show a => Show (HashRing a)