一致性哈希（consistent hash）
一致性哈希（consistent hash）
本文将围绕以下几个问题展开：
- 一致性哈希的出现为了解决什么问题？
- 为什么叫一致性哈希，是否实现了分布式一致性？
- 它是怎么做的(基本原理）
- 优缺点
一致性哈希的诞生
一致性哈希算法是由1997年由麻省理工学院提出一种分布式哈希（DHT）实现算法。
论文链接：Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web，论文中提出利用一致性哈希解决了热点问题。除此之外，还有解决了一个分布式中常见的问题：假设在一个分布式集群中有m台服务器，使用传统的取模哈希将数据均匀存放存放在这m台服务器中。但是当某一台机器宕机或者有新的机器加入，需要对新的集群重新散列，那就意味着需要进行大量通信，数据迁移。如果是网络服务的Cache，就会造成缓存失效。一致性哈希能够有效解决上述两个问题。
目前一致性哈希更多的使用在分布式存储和p2p系统中。
基本原理
基本原理参考文章：五分钟理解一致性哈希
首先按照常用的hash算法来将对应的key哈希到一个具有2^32次方个桶的空间中，即0~(2^32)-1的数字空间中。现在我们可以将这些数字头尾相连，想象成一个闭合的环形。然后把数据通过一定的hash算法处理后映射到环上。按照相同的方法将机器通过hash算法映射到环上，然后以顺时针的方向计算，将所有数据存储到离自己最近的机器中。
机器的删除与添加
普通hash取模算法最为不妥的地方就是在有机器的添加或者删除之后会照成大量的数据存储位置失效，需要对所有数据重新计算放置位置。但一致性哈希能够避免这样的事情发生。例如节点故障被删除了，那么按照顺时针迁移的方法，该节点的数据将会被迁移到顺时针的下一个正常运行的节点中。增加节点同理。
虚拟节点
为了尽可能实现负载均衡，一致性哈希环还引入了“虚拟节点”（ virtual node ），它是实际节点（机器）在 hash 空间的复制品（ replica ），一实际个节点（机器）对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以hash值排列。
一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：
1、平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
2、单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
3、分散性(Spread)：相同的内容要尽可能少的被分散到不同缓冲区中，即降低冗余度。在分布式环境中，网络分区是常态，每个客户端只能看到一部分缓冲（view）,不同客户端获得的结果也可能并不相同，由此会造成数据不一致。好的哈希算法应能够降低分散性，有助于避免数据不一致的情况发生。
4、负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
应用
1.热点问题的解决：
当某一台Cache节点A由于存储热点数据而负载较大时，可以在该热点区域增设Cache节点B。但是，可能会随着数据量的增加，A难以承受负载压力而宕机，假如按照规则，A的数据迁移至B，B需要承受A+B的数据压力，也随之宕机……，这将造成雪崩效应。
因此，解决上述问题比较好的方式是使用虚拟机节点（有效的解决负载均衡）。一个真实节点可以有多个虚拟节点，此时需要采用合适的算法将虚拟节点均匀分布，因为虚拟节点是平衡负载的关键。参考：一致性哈希。
2.分布式集群中节点数目震荡问题：
普通hash求余算法最为不妥的地方就是在有机器的添加或者删除之后会照成大量的对象存储位置失效，这样就大大的不满足单调性了。而一致性哈希在处理某节点被删除时，是将存储在该节点的对象按规则迁移到距离它最近的节点。其他对象并不受影响。在处理节点添加时，也是按规则将距离自己最近的数据迁移过来，环节相邻节点的压力。
一致性哈希让节点震荡的时候，影响最小，以提高分布式cache的命中率。
常用实现方案
一致性哈希是一个概念，有很多种实现方式。
具体应用中，一致性Hash环通常使用二叉查找树存储实现（例如红黑树，较适用于频繁的插入删除操作），Hash查找过程实际上是在二叉査找树中查找不小于査找数的最小数值。当然这个二叉树的最右边叶子节点和最左边的叶子节点相连接，构成环。一致性哈希的c++实现。
在使用平衡二叉树存储桶和数据段对应关系的情况下，假如有C个桶，那么查找的时间复杂度为O(logC),插入删除一个桶的时间复杂度为O(C) .
还有一个经典的实现算法：Chord。Chord具有几乎最优的路由效率，其目的是提供一种能在P2P网络快速定位资源的的算法，Chord并不关心资源是如何存储的，只是从算法层面研究资源的取得，因此Chord的API就简单到只有一个set、get。（Chord主要关注点在路由，即如何快速定位资源）。
假如一个Chord环上有C个桶，将这些桶按大小顺时针标号，Node（机器的IP地址和Port）与Key（资源标识）都被哈希到Chord环上对应的桶里面，这样我们就假定了整个P2P网络的状态为一个虚拟的环，因此我们说Chord是结构化的P2P网络。
每个节点都拥有一张Finger表，表中以顺时针方向，并按照2的倍数等比递增存储节点的前继和后继（即表内顺时针记录离本节点2、4、8、16、32.……2i的距离的log2N个其他节点的位置信息，主要是为了查询加速），上述查找过程是指数收敛的，类似二分法的查找，收敛速度很快的，查找时间或路由复杂度是对数级(logN)。参考链接：Chord原理。
优缺点
优点
1.较好的解决热点问题；
2.解决了分布式场景下某节点宕机或者上线后缓存失效的问题，极大提高缓存命中率；
3.引入虚拟节点较好的实现负载均衡
缺点
1.无法避免单一数据热点问题，因为某一数据被海量请求，而数据始终存在一台节点上。此时需要采用备份策略来缓解。
2.在网络分区（partition）存在的情况下，分区之间不一致性无法避免，一致性哈希没有解决分布式数据的一致性问题。
3.若负载不均衡可能造成雪崩效应，使整个集群无法工作。
综上所述，个人认为，一致性哈希的命名是由于将服务器节点和数据内容使用同样的哈希函数映射到同一空间，而与分布式一致性问题无关。（若有误欢迎指出）
热点问题其他解决办法
过去，人们对于热点数据一般采用复制策略，由多个服务器同时拥有热点数据。常用解决办法是使用代理缓存（proxy cache）。代理将拥有频繁被访问的数据备份，所有用户请求都将通过代理实现，如果代理没有请求的数据，则向原服务器转发请求。这样做将引发难以协调的问题：更多的用户共享同一缓存会更加高效（从分布式一致性问题，cache空间利用率来考虑），但是也将导致该缓存难以承受负载。
另一种方式是Malpani等人提出的缓存路由表法，将一组cache结合起来存储相同的内容，客户端请求到来时分配到随机一个cache中，如果该cache没有缓存被请求的内容，则采用IP组播的方式向别组cache请求。但是，这种采用多播的方式随着网络分区的增加会导致通信讯息失控，造成通信压力。而一致性哈希可以使用在这样的分布式缓存中而不需要一直通信。
参考：web缓存技术概述