A basic Clojure implementation of consistent hashing.
Not all implementations of consistent hashing are the same. This one is probably one of the simpler ones you'll find. It is designed to provide a consistent hash given these bits of information:
- An item (e.g. a keyword, such as
:elephant) - An item hashing function (e.g.
hash) - A sequence of nodes (e.g.
["N1" "N2" "N3" "N4"]) - A node hashing function (e.g.
hash)
Add this to your project.clj dependencies:
[con-hash "0.1.0"](require '[con-hash.core :refer [consistent-hash-fn]])First, create a consistent hashing function using consistent-hash-fn. It
takes two arguments, an item hashing function and a node hashing function. For
this example, we'll use the hash function. As of Clojure 1.6, hash uses
Murmur hashing.
(def chf (consistent-hash-fn hash hash))This gives chf, a reusable consistent hashing function. (Yes, this is
possible without using an AbstractConsistentHashingFunctionFactory.)
Here is how you use the hashing function:
(def nodes #{"N1" "N2" "N3" "N4"})
(chf "1A" nodes) ; "N3"
(chf "2B" nodes) ; "N3"
(chf "3C" nodes) ; "N1"
(chf "4D" nodes) ; "N4"
(chf "5E" nodes) ; "N3"
(chf "6F" nodes) ; "N4"
(chf "7G" nodes) ; "N4"
(chf "8H" nodes) ; "N3"
(chf "9I" nodes) ; "N3"According to Consistent Hashing by Tom White, "for consistent hashing to be effective, it is important to have a hash function that mixes well."
As you can see above, using hash is not mixing well for the above inputs.
What happens when we add more nodes?
(chf "item-42" nodes) ; "N3"
(def nodes (conj nodes "N5"))
(chf "item-42" nodes) ; "N5"
(def nodes (conj nodes "N6"))
(chf "item-42" nodes) ; "N6"
(def nodes (conj nodes "N7"))
(chf "item-42" nodes) ; "N6"What happens when we remove a node?
(def nodes (disj nodes "N6"))
(chf "item-42" nodes) ; "N5"See also:
- Consistent Hashing in Clojure by Shriphani Palakodety, with a blog post and visualization.
Copyright 2014 Bluemont Labs LLC
Distributed under the Eclipse Public License either version 1.0 or (at your option) any later version.