一致性 Hash 算法

一致性哈希算法（Consistent Hashing）最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。

• 负载均衡

• 过渡平滑

• 关键词单调



1.技术出现的背景、初衷，要解决什么样的问题

在使用缓存服务器集群时，为了实现“负载均衡”，可以通过模n的方式将数据固定路由到某个服务器节点。

但这种方式存在较大弊端：当减少或增加服务器节点后，由于n值发生了变化，所以访问数据的请求将被路由到新的缓存服务器上，导致缓存失效。此时，大量的访问请求会瞬间打到数据库上，可能造成数据库宕机，即缓存雪崩。



一致性哈希算法可以用来解决这样的问题。当某个节点发生变化时，只会影响路由到该节点上的缓存数据，也就是只有部分缓存失效，从而避免了缓存雪崩。



当新加入节点Node3时，只影响Node3后面的一部分数据。



2.技术的优势和劣势，即trade-off是什么

缺点：数据倾斜问题。

为解决此问题，引入的虚拟节点机制，即每一个服务节点计算多个哈希值，都放置到Hash环中，以达到数据能够较好的均匀分布的效果。



3.技术适用场景

Memcached、Key-Value Store、Bittorrent DHT、LVS中都有应用。



负载均衡可用时应用服务器、缓存、数据库，一致性hash算法并不能都适用，例如：数据库在扩容后就不能失效，所处要根据不同场景选择不同的算法。



4.技术的组成部分和关键点

1) 构造一个长度为2^32的整数环，称为Hash环；

2) 计算服务器节点的哈希值，并将其配置到0~2^32-1的环上；

3) 计算出存储数据的键的哈希值，映射到圆上；

4) 从数据映射的位置开始顺时针查找，将数据保存到第一个找到的服务器上。若找不到，取第一个节点。形成环形；



5.技术的底层原理换关键实现

1) 如何构造Hash环，即使用什么数据结构

Node必须能够快速的检索到，以便读取缓存数据，HashMap<hash, node>最快的算法O(1)；



环上的Node需要是有序的，且能快速定位（比hash(key)大，且离hash值最近的节点），可以选择的方式：数组+排序O(NlogN)、二叉搜索树O(logN)。



面向接口编程：getNode()，然后用不同的方式实现。



6.已有的实现和他之间的对比