欢迎关注头条号：石杉的架构笔记
周一至周五早八点半！精品技术文章准时送上！！！
精品学习资料获取通道，参见文末
本文来自程序员历小冰的投稿
在此感谢历小冰同学的分享
一致性杂凑算法在分散式快取领域的 MemCached，负载均衡领域的 Nginx 以及各类 RPC 框架中都有广泛的应用
它主要是为了解决传统杂凑函式新增杂凑表槽位数后要将关键字重新对映的问题。
本文会介绍一致性杂凑算法的原理及其实现，并给出其不同杂凑函式实现的效能资料对比，探讨Redis 丛集的资料分片实现等，文末会给出实现的具体 github 地址。
Memcached 与客户端分散式快取
Memcached 是一个高效能的分散式快取系统，然而服务端没有分散式功能，各个服务器不会相互通讯。
它的分散式实现依赖于客户端的程式库，这也是 Memcached 的一大特点。比如第三方的 spymemcached 客户端就基于一致性杂凑算法实现了其分散式快取的功能。
先来一张图，直观的感受一把：
其具体步骤如下:
向 Memcached 新增资料，首先客户端的算法根据 key 值计算出该 key 对应的服务器。服务器选定后，储存快取资料。
获取资料时，对于相同的 key ，客户端的算法可以定位到相同的服务器，从而获取资料。在这个过程中，客户端的算法首先要保证快取的资料尽量均匀地分布在各个服务器上，其次是当个别服务器下线或者上线时，会出现资料迁移，应该尽量减少需要迁移的资料量。
其中，客户端算法是客户端分散式快取效能优劣的关键。
普通的杂凑表算法一般都是计算出杂凑值后，通过取余操作将 key 值对映到不同的服务器上
但是当服务器数量发生变化时，取余操作的除数发生变化，所有 key 所对映的服务器几乎都会改变，这对分散式快取系统来说是不可以接收的。
一致性杂凑算法能尽可能减少了服务器数量变化所导致的快取迁移。
杂凑算法
首先，一致性杂凑算法依赖于普通的杂凑算法。大多数同学对杂凑算法的理解可能都停留在 JDK 的 hashCode 函式上。
其实杂凑算法有很多种实现，它们在不同方面都各有优劣，针对不同的场景可以使用不同的杂凑算法实现。
下面，我们会介绍一下几款比较常见的杂凑算法，并且了解一下它们在分布均匀程度，杂凑碰撞概率和效能等方面的优劣。
MD5 算法：全称为 Message-Digest Algorithm 5，用于确保资讯传输完整一致。是计算机广泛使用的杂凑算法之一，主流程式语言普遍已有 MD5 实现。
MD5 的作用是把大容量资讯压缩成一种保密的格式（就是把一个任意长度的字节串变换成定长的16进位制数字串）。常见的档案完整性校验就是使用 MD5。
CRC 算法：全称为 CyclicRedundancyCheck，中文名称为循环冗余校验。它是一类重要的，编码和解码方法简单，检错和纠错能力强的杂凑算法，在通讯领域广泛地用于实现差错控制。
MurmurHash 算法：高运算效能，低碰撞率，由 Austin Appleby 创建于 2008 年，现已应用到 Hadoop、libstdc++、nginx、libmemcached 等开源系统。
Java 界中 Redis，Memcached，Cassandra，HBase，Lucene和Guava 都在使用它。
FNV 算法：全称为 Fowler-Noll-Vo 算法，是以三位发明人 Glenn Fowler，Landon Curt Noll，Phong Vo 的名字来命名的，最早在 1991 年提出。
FNV 能快速 hash 大量资料并保持较小的冲突率，它的高度分散使它适用于 hash 一些非常相近的字串，比如 URL，hostname，档名，text 和 IP 地址等。
Ketama 算法：一致性杂凑算法的实现之一，其他的杂凑算法有通用的一致性杂凑算法实现，只不过是替换了杂凑对映函式而已，但 Ketama 是一整套的流程，我们将在后面介绍。
一致性杂凑算法
下面，我们以分散式快取场景为例，分析一下一致性杂凑算法环的原理。
首先将快取服务器（ ip + 埠号）进行杂凑，对映成环上的一个节点，计算出快取资料 key 值的 hash key，同样对映到环上，并顺时针选取最近的一个服务器节点作为该快取应该储存的服务器。具体实现见后续的章节。
比如说，当存在 A，B，C，D 四个快取服务器时，它们及其 key 值为1的快取资料在一致性杂凑环上的位置如下图所示，根据顺时针取最近一个服务器节点的规则，该快取资料应该储存在服务器 B 上。
当要储存一个 key 值为4的快取资料时，它在一致性杂凑环上的位置如下所示，所以它应该储存在服务器 C 上。
类似的，key 值为5，6的资料应该存在服务 D 上，key 值为7，8的资料应该储存在服务 A 上。
此时，服务器 B 宕机下线，服务器 B 中储存的快取资料要进行迁移，但由于一致性杂凑环的存在，只需要迁移key 值为1的资料，其他的资料的储存服务器不会发生变化。这也是一致性杂凑算法比取余映射算法出色的地方。
由于服务器 B 下线，key 值为1的资料顺时针最近的服务器是 C ，所以资料存迁移到服务器 C 上。
现实情况下，服务器在一致性杂凑环上的位置不可能分布的这么均匀，导致了每个节点实际占据环上的区间大小不一。
这种情况下，可以增加虚节点来解决。通过增加虚节点，使得每个节点在环上所“管辖”的区域更加均匀。
这样就既保证了在节点变化时，尽可能小的影响资料分布的变化，而同时又保证了资料分布的均匀。
具体实现
下面我们实现 Memcached 分散式快取场景下的一致性杂凑算法，并给出具体的测试效能资料。
该实现借鉴了 kiritomoe 博文中的实现和 spymemcached 客户端程式码。具体实现请看我的github，地址为
https://github.com/ztelur/consistent-hash-algorithm。
NodeLocator 是分散式快取场景下一致性杂凑算法的抽象，它有一个 getPrimary 函式，接收一个快取资料的 key 值，输出储存该快取资料的服务器例项。
下面是通用的一致性杂凑算法的实现，它使用 TreeMap 作为一致性杂凑环的资料结构，其 ceilingEntry 函式可以获取环上最近的一个节点。
buildConsistentHashRing 函式中包含了构建一致性杂凑环的过程，预设加入了 12 个虚拟节点。
public class ConsistentHashNodeLocator implements NodeLocator {
private final static int VIRTUAL_NODE_SIZE = 12;
private final static String VIRTUAL_NODE_SUFFIX = "-";
private volatile TreeMap hashRing;
private final HashAlgorithm hashAlg;
public ConsistentHashNodeLocator(List nodes, HashAlgorithm hashAlg) {
this.hashAlg = hashAlg;
this.hashRing = buildConsistentHashRing(hashAlg, nodes);
}
@Override
public MemcachedNode getPrimary(String k) {
long hash = hashAlg.hash(k);
return getNodeForKey(hashRing, hash);
}
private MemcachedNode getNodeForKey(TreeMap hashRing, long hash) {
/* 向右找到第一个key */
Map.Entry locatedNode = hashRing.ceilingEntry(hash);
/* 想象成为一个环，超出尾部取出第一个 */
if (locatedNode == null) {
locatedNode = hashRing.firstEntry();
}
return locatedNode.getValue();
}
private TreeMap buildConsistentHashRing(HashAlgorithm hashAlgorithm, List nodes) {
TreeMap virtualNodeRing = new TreeMap();
for (MemcachedNode node : nodes) {
for (int i = 0; i // 新增虚拟节点的方式如果有影响，也可以抽象出一个由物理节点扩充套件虚拟节点的类
virtualNodeRing.put(hashAlgorithm.hash(node.getSocketAddress().toString() + VIRTUAL_NODE_SUFFIX + i), node);
}
}
return virtualNodeRing;
}
}
在 getPrimary 函式中，首先使用 HashAlgorithm 计算出 key 值对应的杂凑值，然后呼叫 getNodeForKey 函式从 TreeMap 中获取对应的最近的服务器节点例项。
HashAlgorithm 是对杂凑算法的抽象，一致性杂凑算法可以使用各种普通的杂凑算法，比如说 CRC ，MurmurHash 和 FNV 等。
下面，我们将会对比各种杂凑算法给该实现带来的效能差异性。
效能测试
测试资料是评价一个算法好坏的最为真实有效的方法，量化的思维模式一定要有，这也是程序员进阶的法宝之一。
我们以下面四个量化的指标对基于不同杂凑函式的一致性杂凑算法进行评测。
统计每个服务器节点储存的快取数量，计算方差和标准差测量快取分布均匀情况，我们可以模拟 50000个快取资料，分配到100 个服务器，测试最后个节点储存快取资料量的方差和标准差。
随机下线10%的服务器，重新分配快取，统计快取迁移比率。测量节点上下线的情况，我们可以模拟 50000 个快取资料，分配到100 个指定服务器，之后随机下线 10 个服务器并重新分配这50000个数据，统计快取分配到不同服务器的比例，也就是迁移比率。使用JMH对不同杂凑算法的执行效率进行对比。具体评测算法如下。
public class NodeLocatorTest {
/**
* 测试分布的离散情况
*/
@Test
public void testDistribution() {
List servers = new ArrayList();
for (String ip : ips) {
servers.add(new MemcachedNode(new InetSocketAddress(ip, 8080)));
}
// 使用不同的DefaultHashAlgorithm进行测试，得出不同的资料
NodeLocator nodeLocator = new ConsistentHashNodeLocator(servers, DefaultHashAlgorithm.NATIVE_HASH);
// 构造 50000 随机请求
List keys = new ArrayList();
for (int i = 0; i keys.add(UUID.randomUUID().toString());
}
// 统计分布
AtomicLongMap atomicLongMap = AtomicLongMap.create();
for (MemcachedNode server : servers) {
atomicLongMap.put(server, 0);
}
for (String key : keys) {
MemcachedNode node = nodeLocator.getPrimary(key);
atomicLongMap.getAndIncrement(node);
}
System.out.println(StatisticsUtil.variance(atomicLongMap.asMap().values().toArray(new Long[]{})));
System.out.println(StatisticsUtil.standardDeviation(atomicLongMap.asMap().values().toArray(new Long[]{})));
}
/**
* 测试节点新增删除后的变化程度
*/
@Test
public void testNodeAddAndRemove() {
List servers = new ArrayList();
for (String ip : ips) {
servers.add(new MemcachedNode(new InetSocketAddress(ip, 8080)));
}
//随机下线10个服务器, 先shuffle，然后选择0到90，简单模仿随机计算。
Collections.shuffle(servers);
List serverChanged = servers.subList(0, 90);
NodeLocator loadBalance = new ConsistentHashNodeLocator(servers, DefaultHashAlgorithm.NATIVE_HASH);
NodeLocator changedLoadBalance = new ConsistentHashNodeLocator(serverChanged, DefaultHashAlgorithm.NATIVE_HASH);
// 构造 50000 随机请求
List keys = new ArrayList();
for (int i = 0; i keys.add(UUID.randomUUID().toString());
}
int count = 0;
for (String invocation : keys) {
MemcachedNode origin = loadBalance.getPrimary(invocation);
MemcachedNode changed = changedLoadBalance.getPrimary(invocation);
// 统计发生变化的数值
if (!origin.getSocketAddress().equals(changed.getSocketAddress())) count++;
}
System.out.println(count / 50000D);
}
static String[] ips = {...};
}
JMH的测试指令码如下所示。
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Thread)
public class JMHBenchmark {
private NodeLocator nodeLocator;
private List keys;
@Benchmark
public void test() {
for (String key : keys) {
MemcachedNode node = nodeLocator.getPrimary(key);
}
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(JMHBenchmark.class.getSimpleName())
.forks(1)
.warmupIterations(5)
.measurementIterations(5)
.build();
new Runner(opt).run();
}
@Setup
public void prepare() {
List servers = new ArrayList();
for (String ip : ips) {
servers.add(new MemcachedNode(new InetSocketAddress(ip, 8080)));
}
nodeLocator = new ConsistentHashNodeLocator(servers, DefaultHashAlgorithm.MURMUR_HASH);
// 构造 50000 随机请求
keys = new ArrayList();
for (int i = 0; i keys.add(UUID.randomUUID().toString());
}
}
@TearDown
public void shutdown() {
}
static String[] ips = {...};
}
分别测试了 JDK 杂凑算法，FNV132 算法，CRC 算法，MurmurHash 算法和Ketama 算法，分别对应 DefaultHashAlgorithm 的 NATIVE_HASH， FNV1_32_HASH， CRC_HASH， MURMUR_HASH 和 KETAMA_HASH 。
具体资料如下所示。
虚拟槽分割槽
有些文章说，Redis 丛集并没有使用一致性杂凑算法，而是使用虚拟槽分割槽算法。但是外网上都说 Redis 使用的虚拟槽分割槽只是一致性杂凑算法的变种，虚拟槽可以允许 Redis 动态扩容。
或许只有去了解一下Redis的源代码才能对这个问题作出准确的回答。
END
一大波微服务、分散式、高并发、高可用的原创系列文章正在路上,
欢迎关注头条号：石杉的架构笔记
周一至周五早八点半！精品技术文章准时送上！！！
十余年BAT架构经验倾囊相授
