con-hash

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)

Usage

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"

Related Projects

See also:

• Consistent Hashing in Clojure by Shriphani Palakodety, with a blog post and visualization.

License

Copyright 2014 Bluemont Labs LLC

Distributed under the Eclipse Public License either version 1.0 or (at your option) any later version.