A simplified Consistent Hashing Ring Implementation based on Mike Bayer (zzzeek)'s Python 2 code

simplified_consistent_hashing_ring.py

# Reference:
# https://techspot.zzzeek.org/2012/07/07/the-absolutely-simplest-consistent-hashing-example/

# Changes done on top of Mike Bayer's original Implementation
# - Remove replica concept to (over)simplify the code
# - Address Python2 -> Python3 changes

import bisect
import hashlib

class ConsistentHashRing:
    """Implement a consistent hashing ring."""

    def __init__(self):
        """Create a new ConsistentHashRing.
        """
        self._keys = []
        self._nodes = {}

    def _hash(self, key):
        """
        Given a string key, return a hash value.
        It will be used for both node name and key name
        """
        return hashlib.md5(key.encode()).hexdigest()

    def __setitem__(self, nodename, node):
        """Add a node, given its name.

        The given nodename is hashed

        """
        hash_ = self._hash(nodename)
        if hash_ in self._nodes:
            raise ValueError("Node name %r is "
                        "already present" % nodename)
        self._nodes[hash_] = node
        bisect.insort(self._keys, hash_)

    def __delitem__(self, nodename):
        """Remove a node, given its name."""

        hash_ = self._hash(nodename)
        # will raise KeyError for nonexistent node name
        del self._nodes[hash_]
        index = bisect.bisect_left(self._keys, hash_)
        del self._keys[index]

    def __getitem__(self, key):
        """Return a node, given a key.

        The node with a hash value nearest
        but not less than that of the given
        name is returned.

        If the hash of the given name is
        greater than the greatest hash,
        returns the lowest hashed node.
        (That's why it's like a "ring")

        """
        hash_ = self._hash(key)
        start = bisect.bisect(self._keys, hash_)
        if start == len(self._keys):
            start = 0
        return self._nodes[self._keys[start]]


cr = ConsistentHashRing()
print(cr._keys)
print(cr._nodes)
print("-" * 16)

cr["node1"] = "<node 1>"
print(cr._keys)
print(cr._nodes)
print("-" * 16)

cr["node2"] = "<node 2>"
print(cr._keys)
print(cr._nodes)
print("-" * 16)

client = cr["bar"]
print(cr._hash("bar"))
print(client)
print("-" * 16)

client = cr["foo"]
print(cr._hash("foo"))
print(client)