学步园

我最近一段时间在研究 consistent hash。介绍它的paper(Consistent
Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web byDavid
Karger et al) 十年前就出现了，不过直到最近才悄悄的有越来越多的service开始使用consistent hash，这些service包括Amazon’s Dynamo，以及memcached (向Last.fm敬礼)。那么到底什么是consistent
hash呢？大家为什么要关注它呢？

consistent hash的需求来自于运行一个cache集群(例如web cache)时遇到的一些限制。如果你拥有一个由n台cache机器组成的集群，那么最普通的load balance方式就是把进来的对象o放在编号为hash(o) mod n的那一台上。你会觉得这个方案简介优美，直到有一天，由于种种原因你不得不增加或者移除一些cache机器，这时，集群的机器数目n变了，每个对象都被hash求余到了新的机器。这将是一场灾难，因为真正存放内容的server会被来自于cache集群的request拖垮。这时整个系统看起来就像没有cache一样。这就是大家为什么关心consistent
hash，因为大家需要使用它来避免系统被拖垮。

情况如果是这样的就好了：当集群添加了一台cache机器，该机器只从其他cache机器中读取应得的那些对象；相应的，当一个cache机器从集群中移除，最好是它cache住的对象被分配给其他的cache机器(而没有更多的数据移动)。这种理想的情境就是consistent hash所追求并实现的：如果可能的话，始终将同一组对象分配给相同的机器。

consistent hash算法背后最基础的思想就是：对object和cache machine使用相同的hash函数。这样做的好处是能够把cache机器映射到一段interval上，而这段interval就会包含一定数目的对象的hash值。如果某台cache机器被移除了，那么它映射到的interval被和它相邻的一个cache机器托管，其他所有的cache机器都不用变。

描述

让我们来更深入的来了解一下consistent hash。Hash的作用就是把object和cache映射到一个数值范围上。Java程序员对hash应该很熟悉了–每个对象的hashCode方法会返回一个在[-2³¹,
2³¹-1]的int型整数。我们把这个数值范围首尾相接的映射到一个环上。下图描述了一组object(1,
2, 3, 4)和一组cache(A, B, C)分别映射在Hash环上。(图片源于Web
Caching with Consistent Hashing by David Karger et
al)

图1

要确定某个object会缓存在哪个cache，我们从这个object开始顺时针前进，知道我们遇到一个cache点。这样，从上图的例子我们看到object 1和4 归cache A，object 2归cache B，而cache C缓存的事object 3。考虑一下，当cache C被移除了，会发生什么？在这种情况下，object 3被cache A缓存住，所有其他object都不用移动。如果如图2，cache集群添加了cache D，那么D会缓存object 3和4，把object 1留给A。

图2

一切都很好，除了一点：指派给每个cache的间距大小太随机了，这样就会object的分配也极度的不均匀。 为了解决这个问题，我们引入”virtual nodes”这个概念：即每个cache在hash环上有多个副本，也就是说，每当我们加入一个cache，在环上都会为这个cache增加多个点。

我下面的代码做了一个仿真实验，将10,000个object存入10个cache，你会在下面的plot图中看到virtual nodes的影响。x轴上是每个cache的副本数(对数刻度)。当x值较小时，我们看到objects在caches中的分布是不平衡的(y轴是以百分比形式表示objects在caches中分布的标准差)。随着cache的replica的增加，objects的分布趋向于更加平衡。这个实验说明了每个cache大概100-200的replica能够使object的分布较为平衡(标准差在5%-10%)

experiment result

实现

下面是使用Java的一个简单实现。要使consistent hash的效果明显，很重要的一点是使用一个mix的很好的hash函数。Java中object的hashCode方法的大多数实现都没有提供很好的mix性能。所以我们提供一个HashFunction接口，以便于定制使用的hash函数。在这里推荐MD5.

import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash<T> {

 private final HashFunction hashFunction;
 private final int numberOfReplicas;
 private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();

 public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
     Collection<T> nodes) {
   this.hashFunction = hashFunction;
   this.numberOfReplicas = numberOfReplicas;

   for (T node : nodes) {
     add(node);
   }
 }

 public void add(T node) {
   for (int i = 0; i < numberOfReplicas; i++) {
     circle.put(hashFunction.hash(node.toString() + i), node);
   }
 }

 public void remove(T node) {
   for (int i = 0; i < numberOfReplicas; i++) {
     circle.remove(hashFunction.hash(node.toString() + i));
   }
 }

 public T get(Object key) {
   if (circle.isEmpty()) {
     return null;
   }
   int hash = hashFunction.hash(key);
   if (!circle.containsKey(hash)) {
     SortedMap<Integer, T> tailMap = circle.tailMap(hash);
     hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
   }
   return circle.get(hash);
 }

}

 
上面的代码用一个integer的sorted map来表示hash circle。当ConsistentHash创建时，每个node都被添加到circle map中(添加的次数由numberOfReplicas控制)。每个replica的位置，由node的名字加上一个数字后缀所对应的hash值来决定。
 要为一个object找到它应该去的node(get方法)，我们把object的hash值放入map中查找。大多数情况下，不会恰好有一个node和这个object重合(即使每个node都有一定量的replica，hash的值空间也比node数要多得多)，所以用tailMap方法找到map中的下一个key。如果tail map为空，那么我们转一圈，找到circle中的第一个key。

使用
  

那么你应该如何使用consistent hash呢？一般情况下，你可以使用一些library，而不是自己去写代码。例如上面提到的memcached–一个分布式的内存cache系统，现在已经有了支持consisitent hash的client。由Last.fm的Richard

 Jones实现的ketama是第一个，现在是有Dustin

 Sallings贡献的Java实现。很有趣的是只有客户端需要实现consisitent

 hash算法，server端的代码不需要任何改变。其他使用consisitent hash的系统有Chord，一个分布式hash表的实现，和Amazon的Dynamo，一个key-value存储系统。(没有开源)


libketama - a consistent hashing algo for memcache clients

Posted by muesli inDevelopment

Wednesday, April 11. 2007 
We wrote ketama to replace how our memcached clients mapped keys to servers. Previously, clients mapped keys->servers like this:
server = serverlist[hash(key)%serverlist.length];
This meant that whenever we added or removed servers from the pool, everything hashed to different servers, which effectively wiped the entire cache. We add (and sometimes remove) servers from the memcached pool often enough to warrant writing this - if your

 memcached pool never changes, you can probably stop reading now 
Ketama is an implementation of a consistent hashing algorithm, meaning you can add or remove servers from the memcached pool without causing a complete remap of all keys.
Here's how it works:
- Take your list of servers (eg: 1.2.3.4:11211, 5.6.7.8:11211, 9.8.7.6:11211)

- Hash each server string to several (100-200) unsigned ints

- Conceptually, these numbers are placed on a circle called the continuum. (imagine a clock face that goes from 0 to 2^32)

- Each number links to the server it was hashed from, so servers appear at several points on the continuum, by each of the numbers they hashed to.

- To map a key->server, hash your key to a single unsigned int, and find the next biggest number on the continuum. The server linked to that number is the correct server for that key.

- If you hash your key to a value near 2^32 and there are no points on the continuum greater than your hash, return the first server in the continuum.
If you then add or remove a server from the list, only a small proportion of keys end up mapping to different servers.
The majority of the code is a C library (libketama) and a PHP4 extension that wraps it. I've also included a class from our Java client. (Java Collections makes it rather easy). We use a single-server memcache client wrapped with a native php class to make

 it multi-server capable, so we just replaced the hashing method with a ketama_find_server call. (should be easy enough to plug this into libmemcache if need be)
http://static.last.fm/ketama/ketama-0.1.1.tar.bz2
We've been using this in production for all our PHP installs and Java services at Last.fm for around 10 days now. We deployed it just in time to smooth over moving loads of webservers between datacenters.
For further information, please refer to the README inside the tarball or these threads on the memcached mailing list:
http://lists.danga.com/pipermail/memcached/2007-April/003853.html
http://lists.danga.com/pipermail/memcached/2007-April/003834.html