场景：分布式缓存
解决：缓存服务器的动态变化时，系统伸缩性
场景
缓存的目的就是 提高速度，改善用户体验，减轻后端服务器压力。存在的多台服务器，我们需要哈希命中，路由到某个缓存服务器上取数据。
问题
如果我们通过对缓存项键值进行普通的取余hash，来命中哪台服务器上存有我们所需要的缓存数据，比如我们有三台存储图片缓存服务器：
- hash(图片)%3
- 服务器(0,1,2),命中后进行存储和取出
情况：如果其中一台缓存服务器故障，我们需要移除掉
导致：大量的缓存项会无效，导致缓存雪崩，一时间内会导致后端服务系统压力过大
分析：该算法使用节点数取余的方法，强依赖node的数目，当节点数目发生改变时，会导致大量缓存项无效,映射到与之前不一样的节点上
系统伸缩性
这里就需要谈及一个名词”系统伸缩性”
是指通过不断向集群中加入服务器的手段来缓解不断上升的用户并发访问压力和不断增长的数据存储需求
衡量架构伸缩性的指标
是否可用多台服务器架构集群
是否容易向服务器中添加新的服务器
加入的服务器是否可以提供和原服务器无差别的服务
集群中容纳的总服务器是否有限制
下面我们进入正题！DHT！！
一致性哈希算法（DHT）
- 按照常用的hash算法映射到一个2^32的哈希桶，0~(2^32)-1的数字空间中，形成了一个hash闭合的环形。
- 对服务器的地址进行hash后对2^32取模，映射到环上。
- 对数据对象进行相同的hash后对2^32取模得到key
- key按照顺时针的方向，在环找寻最近的节点，这个节点就是存储对象的节点
让我们看下集群的动态变化，对整个系统的影响。
移除节点
object3因为NODE2的移除，现在映射到NODE3，其他数据映射不变
增加节点
NODE4的增加，object2映射到NODE2，其他数据映射不变
优点：服务器的数量如果发生改变，并不是所有缓存都会失效，而是只有部分缓存会失效，前端的缓存仍然能分担整个系统的压力，而不至于所有压力都在同一时间集中到后端服务器上。
hash环的偏斜
- 问题：可能会出现服务器节点映射到hash环上比较集中
- 结果：换上映射的数据根据之前的规则顺时针靠近最近的节点，会出现负载不均的情况
- 解决：虚拟节点
虚拟节点
“虚拟节点”是”实际节点”（实际的物理服务器）在hash环上的复制品,一个实际节点可以对应多个虚拟节点，使缓存对象更均匀的分布在哈希环上。
例如创建N个虚拟节点
实现：
在ip地址后面加上后缀（例如：ip：port#virN），然后对此进行hash计算，映射到环上
跟之前操作一样，顺时针获取节点路径，然后substring后缀之前的地址。
判断哈希算法好坏
一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：
平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。