一致性hash

应用领域（数据分布式存储）

• 数据缓存集群（redis、memcache）
• hadoop
• ESearch
• 分布式数据库

演进产生的问题

1.本地缓存

image.png

• 由于用户访问量的上升，DB的并发数增加，对数据库造成巨大压力，所以使用缓存数据库的一部分数据（经常被访问），为数据库减轻压力。

2.远程分布式缓存

image.png

• V1版存在的问题，应用程序（假设是web服务部署在Tomcat，而Tomcat单个服务大概可以同时支持700或800的访问量）访问量的上升，需要分布式部署多个服务支持更多的访问量。

3.大型高并发系统

image.png

• V2版解决对应用程序服务访问量的支持，但是没有解决缓存支持。例如memcache最高支持20w/s的访问，并且需要能够存储更多的海量的数据，单个缓存服务往往不能够支持，这时候就需要缓存服务集群。

上面的解决方案是设置数据缓存集群，但是哪些数据该存在哪个缓存服务器里面呢？

1.hash求余

• 数据对key进行求余（散列值=key%节点数），然后存到对应的节点（写），需要时就根据key从对应的节点进行获取（读）。例如：某数据key = 1，节点从0~2一共3个节点，1%3得出要讲该数据存入节点1。
• 但是当增加一个节点后，就会一部分数据获取失败，从缓存获取失败，就得重新往数据库进行查找，但如果失效的数据百分比很高时，相当于这些缓存服务基本都没有用，全部都去查询数据库，数据库一下子就会奔溃。
• 例如：原先只有3个节点，后面加了1个节点，一共4个节点。key = 0，1，2，3，4，5，6，7，8，9，10，11中，只有key = 0,1,2,3还能正确查找到数据，这样失效的数据就有75%，当节点99增加到100时，同理可得失效的数据就有99%。这就hash求余存在的缺陷。

2.一致性hash

实现：

• hash值是个整数非负数值，所有的hash值形成一个闭圆环
• 对集群的的节点的某个属性求hash值，放到环上
• 数据key求hash值，也放到环上
• 数据的hash值按顺时针找到离它最近的节点，放在该节点上。

image.png

增加一个节点：

• 如下图，在节点n2和n0增加节点n3后，失效的数据就会存在n2与n3之间（hash计算找n3节点数据，而不去节点n0上找存储的数据），使得失效的数据占比不超过1/3（同理可推断，当已有n节点，再上1个节点，失效的数据不超过1/n），解决hash求余
• 但也有存在一定的问题，要是数据尽可能的均匀分布，就需要节点的数量越大越好，这也意味需要作为硬件服务器数量越来越多，但实际上并没有那么多的硬件服务器。

image.png

3.一致性hash + 虚拟节点

• 每个硬件服务器虚拟出多个节点，使环上的数据可以均匀散列到每个虚拟节点上。

  
  image.png