一个简单的consistent hashing的样例，非常easy理解。
首先有一个设备类，定义了机器名和ip：
public class Cache
{
public String name;
public String ipAddress;
}
然后是基本的实现：
public class Shard<T> {
//hash 算法并非保证绝对的平衡，假设 cache 较少的话，对象并不能被均匀的映射到 cache 上，
//所以添加虚拟节点
private TreeMap<Long, T> nodes;
private List<T> shards; //节点碎片
private final int NODE_NUM = 10; // 每一个机器节点关联的虚拟节点个数
public Shard(List<T> shards) {
this.shards = shards;
init();
}
private void init() {
nodes = new TreeMap<Long, T>();
for (int i = 0; i < shards.size(); i++)
{ // 遍历真实节点
final T shardInfo = shards.get(i);
for (int n = 0; n < NODE_NUM; n++)
{
// 真实节点关联虚拟节点，真实节点是VALUE；
nodes.put((long) Hash("SHARD-" + i + "-NODE-" + n), shardInfo);
}
System.out.println(shardInfo);
}
}
public T getShardInfo(String key) {
SortedMap<Long, T> tail = nodes.tailMap((long) Hash(key));
if (tail.size() == 0) {
return nodes.get(nodes.firstKey());
}
//找到近期的虚拟节点
return tail.get(tail.firstKey());
}
/**
* 改进的32位FNV算法，高离散
*
* @param string
* 字符串
* @return int值
*/
public static int Hash(String str)
{
final int p = 16777619;
int hash = (int) 2166136261L;
for (byte b : str.getBytes())
hash = (hash ^ b) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
}
到这里就完了，是不是非常easy，以下来測试下：
public class Test
{
/**
* @param args
*/
public static void main(String[] args)
{
List<Cache> myCaches=new ArrayList<Cache>();
Cache cache1=new Cache();
cache1.name="COMPUTER1";
Cache cache2=new Cache();
cache2.name="COMPUTER2";
myCaches.add(cache1);
myCaches.add(cache2);
Shard<Cache> myShard=new Shard<Cache>(myCaches);
Cache currentCache=myShard.getShardInfo("info1");
System.out.println(currentCache.name);
// for(int i=0;i<20;i++)
// {
// String object=getRandomString(20);//产生20位长度的随机字符串
// Cache currentCache=myShard.getShardInfo(object);
// System.out.println(currentCache.name);
// }
}
public static String getRandomString(int length) { //length表示生成字符串的长度
String base = "abcdefghijklmnopqrstuvwxyz0123456789";
Random random = new Random();
StringBuffer sb = new StringBuffer();
for (int i = 0; i < length; i++) {
int number = random.nextInt(base.length());
sb.append(base.charAt(number));
}
return sb.toString();
}
}
我们有两台设备，computer1和computer2，第一次初始化要构建一个2的32次方的环，并往上面放设备。这个环由改进的FNV算法实现。位置也由hash算法确定。
但我们仅仅有两台设备，非常明显在环上会分布不均匀（这个就不解释了，网上非常多资料）。于是我们每台设备添加10个虚拟设备。
最后分布例如以下：
-1561290727=Hash.Cache@10f11b8,
-1083588870=Hash.Cache@10f11b8,
-697149481=Hash.Cache@10f11b8,
-253517545=Hash.Cache@10f11b8,
397383558=Hash.Cache@10f11b8,
1078505027=Hash.Cache@10f11b8,
1810977445=Hash.Cache@10f11b8,
1844081498=Hash.Cache@10f11b8,
2004894833=Hash.Cache@10f11b8,
2051863688=Hash.Cache@10f11b8
-2147483648到2147483647之间是不是比較均匀，这是java的，假设是c#的就是0~2的32次方。我们hash计算出KEY值为2049553054，然后顺时针找到近期的位置，即为
2051863688=Hash.Cache@10f11b8
结果我们定位到了COMPUTER1
最好我们要看看平衡性怎样：取消上面凝视的代码，循环20次，得到结果例如以下：
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER1
COMPUTER1
COMPUTER2
COMPUTER2
COMPUTER2
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER1
COMPUTER1
COMPUTER2
COMPUTER1
COMPUTER2
大家能够自己取试试，
FNV哈希算法是一种高离散性的哈希算法，特别适用于哈希很相似的字符串，比如：URL，IP，主机名，文件名称等。
下面服务使用了FNV:
1、calc
2、DNS
3、mdbm key/value查询函数
4、数据库索引hash
5、主流web查询/索引引擎
6、高性能email服务
7、基于消息ID查询函数
8、auti-spam反垃圾邮件过滤器
9、NFS实现（比方freebsd 4.3, linux NFS v4）
10、Cohesia MASS project
11、Ada 95的spellchecker
12、开源x86汇编器：flatassembler user-defined symbol hashtree
13、PowerBASIC
14、PS2、XBOX上的文本资源
15、非加密图形文件指纹
16、FRET
17、Symbian DASM
18、VC++ 2005的hash_map实现
19、memcache中的libketama
20、 PHP 5.x
21、twitter中用于改进cache碎片
22、BSD IDE project
23、deliantra game server
24、 Leprechaun
25、IPv6流标签