我们先假设有三台分布式缓存服务器
这个时候我们怎么存放缓存信息？最简单的就是随机存放，但是随机存放有非常明显的问题
一个是同一份数据可能被存在不同的机器上而造成数据冗余，第二个是有可能某数据已经被缓存但是访问却没有命中，因为无法保证对相同key的所有访问都被发送到相同的服务器，为了解决这个问题，我们可以使用简单的hash算法，比如
h = Hash(key) % 3
这里的hash作用是将输入的key，转换成一个整数，然后对3取余数，所以计算出来的结果只有0，1，2三个数字，并且相同的key每次计算出来的结果肯定是相同的
假设我们有N台机器，现在我们把上面的公式抽象，就是
h = Hash(key) % N
现在我们解决了随机存放带来的两个问题，看起来似乎不错，但是大家想一下，如果N台机器里面，万一有一台机器X挂了，会出现什么样的情况。
首先挂了的这台机器X无论是存放还是获取操作，都是会失败的，所以一般监控系统检测到有机器挂了，肯定会把这台机器摘除出去，机器数就从N台减到了N-1台，那么X后面的机器就需要序号减1，并且计算公式需要调整成
h = Hash(key) % (N-1)
我们再来假设另外一种情况，现在有N台机器提供服务，但是已经支持不下去了，所以新增了一台机器，那么计算公式需要调整成
h = Hash(key) % (N+1)
大家发现上面有什么问题没有，就是每次有机器挂了，或者新增机器的时候，都需要调整计算公式，这会导致大量的缓存命中不了，我们把这个叫做容错性和扩展性不强，怎么解决这个问题？
我们来看看一致性hash是怎么做的
一个设计良好的分布式哈希方案应该具有良好的单调性，即服务节点的增减不会造成大量哈希重定位。一致性哈希算法就是这样一种哈希方案。最早是1997年由麻省理工大学提出的。
简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0 - 232-1（即哈希值是一个32位无符号整形），整个哈希空间环如下：
整个空间按顺时针方向组织。0和232-1在零点中方向重合。
下一步将各个服务器使用H进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中三台服务器使用ip地址哈希后在环空间的位置如下：
接下来使用如下算法定位数据访问到相应服务器：将数据key使用相同的函数H计算出哈希值h，通根据h确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。
例如我们有A、B、C、D四个数据对象，经过哈希计算后，在环空间上的位置如下：
根据一致性哈希算法，数据A会被定为到Server 1上，D被定为到Server 3上，而B、C分别被定为到Server 2上。
下面分析一致性哈希算法的容错性和可扩展性。现假设Server 3宕机了：
可以看到此时A、C、B不会受到影响，只有D节点被重定位到Server 2。一般的，在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即顺着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。
下面考虑另外一种情况，如果我们在系统中增加一台服务器Memcached Server 4：
此时A、D、C不受影响，只有B需要重定位到新的Server 4。一般的，在一致性哈希算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即顺着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。
综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。
一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。例如我们的系统中有两台服务器，其环分布如下：
此时必然造成大量数据集中到Server 1上，而只有极少量会定位到Server 2上。为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况，我们决定为每台服务器计算三个虚拟节点，于是可以分别计算“Memcached Server 1#1”、“Memcached Server 1#2”、“Memcached Server 1#3”、“Memcached Server 2#1”、“Memcached Server 2#2”、“Memcached Server 2#3”的哈希值，于是形成六个虚拟节点：
同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Memcached Server 1#1”、“Memcached Server 1#2”、“Memcached Server 1#3”三个虚拟节点的数据均定位到Server 1上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。
网友评论