The Ketama Algorithm for Consistent Hashing

There are already plenty of articles discussing the principle and applications of consistent hashing. If you have no idea what consistent hashing is at all, you can first read this article: Consistent Hashing.

Relatively speaking, the principle of consistent hashing is fairly easy to understand. But in daily development I’ve found that while most colleagues have a rough understanding of the principle, very few know the concrete implementation. Of course, different languages have different implementations; one of the more famous ones is the Ketama algorithm, originally implemented by programmers at Last.fm and widely adopted. Some open-source frameworks such as spymemcached and twemproxy have this algorithm built in.

This article mainly analyzes the concrete implementation of the Ketama algorithm based on the spymemcached source code.

In the class KetamaNodeLocator.java there is a setKetamaNodes() method responsible for initializing the consistent hash ring. The code is as follows:

protected void setKetamaNodes(List<MemcachedNode> nodes) {
    TreeMap<Long, MemcachedNode> newNodeMap = new TreeMap<Long, MemcachedNode>();
    int numReps = config.getNodeRepetitions();

    for (MemcachedNode node : nodes) {
      // Ketama does some special work with md5 where it reuses chunks.
      if (hashAlg == DefaultHashAlgorithm.KETAMA_HASH) {
        for (int i = 0; i < numReps / 4; i++) {
          byte[] digest = DefaultHashAlgorithm.computeMd5(config.getKeyForNode(node, i));
          for (int h = 0; h < 4; h++) {
            Long k = ((long) (digest[3 + h * 4] & 0xFF) << 24)
                    | ((long) (digest[2 + h * 4] & 0xFF) << 16)
                    | ((long) (digest[1 + h * 4] & 0xFF) << 8)
                    | (digest[h * 4] & 0xFF);

            newNodeMap.put(k, node);
            getLogger().debug("Adding node %s in position %d", node, k);
          }
        }
      } else {
        for (int i = 0; i < numReps; i++) {
          newNodeMap.put(hashAlg.hash(config.getKeyForNode(node, i)), node);
        }
      }
    }
    assert newNodeMap.size() == numReps * nodes.size();
    ketamaNodes = newNodeMap;
}

Let’s analyze the implementation of setKetamaNodes in detail. First, the MemcachedNode class wraps the network connection parameters and methods of a Memcached node. TreeMap is used here to simulate the ring structure of a consistent hash ring.

int numReps = config.getNodeRepetitions();

The getNodeRepetitions() method reads the configuration and returns the number of virtual nodes corresponding to one real Memcached node. By default it returns 160, meaning a Memcached node corresponds to 160 virtual nodes on the consistent hash ring.

config.getKeyForNode(node, i)

getKeyForNode() generates a key based on the passed MemcacheNode object and the variable i, e.g. returning a value like “127.0.0.1:11311-0”.

computeMd5() generates a 16-byte MD5 digest from the key, so the digest array has 16 bytes:

byte[] digest = DefaultHashAlgorithm.computeMd5(config.getKeyForNode(node, i));

Group the digest array into groups of four bytes and use bit operations to produce a long integer of at most 32 bits. The reason it’s 32 bits is that the consistent hash ring ranges from 0 to 2^32. Going back to the example above, for a Memcached node like “127.0.0.1:11311”, the for loop produces 40 replicas — “127.0.0.1:11311-0”, “127.0.0.1:11311-1” … “127.0.0.1:11311-39”. For each replica like “127.0.0.1:11311-0”, it produces 4 long integers corresponding to 4 positions on the ring, so with the default configuration one Memcached node occupies 4×40=160 positions on the ring.

Long k = ((long) (digest[3 + h * 4] & 0xFF) << 24)
          | ((long) (digest[2 + h * 4] & 0xFF) << 16)
          | ((long) (digest[1 + h * 4] & 0xFF) << 8)
          | (digest[h * 4] & 0xFF);

Put the MemcacheNode object into the TreeMap with k as the key:

newNodeMap.put(k, node);

Because TreeMap’s values are sorted by key, TreeMap can be used to simulate the ring structure of consistent hashing: smaller k values come first, larger k values come later.

That’s the basic analysis of the consistent hash ring initialization process. Now let’s look at the lookup process. The getPrimary() function takes a key, e.g. “123”, and first computes the hash value of that key.

public MemcachedNode getPrimary(final String k) {
    MemcachedNode rv = getNodeForKey(hashAlg.hash(k));
    assert rv != null : "Found no node for key " + k;
    return rv;
  }

MemcachedNode getNodeForKey(long hash) {
	final MemcachedNode rv;
	if (!ketamaNodes.containsKey(hash)) {
	  // Java 1.6 adds a ceilingKey method, but I'm still stuck in 1.5
	  // in a lot of places, so I'm doing this myself.
	  SortedMap<Long, MemcachedNode> tailMap = getKetamaNodes().tailMap(hash);
	  if (tailMap.isEmpty()) {
	    hash = getKetamaNodes().firstKey();
	  } else {
	    hash = tailMap.firstKey();
	  }
	}
	rv = getKetamaNodes().get(hash);
	return rv;
}

The key point is the following statement: TreeMap’s tailMap() method returns a SortedMap object tailMap, whose keys are all greater than the passed-in hash. This is equivalent to, given a hash value, searching clockwise on the consistent hash ring until the first node whose key is greater than the passed hash is found; that node is the Memcached node corresponding to this hash value.

SortedMap<Long, MemcachedNode> tailMap = getKetamaNodes().tailMap(hash);

That’s the analysis of the Ketama algorithm implementation in the spymemcached source code.

• Tags:
• Algorithm
• Distributed
• Consistent Hashing