分布式算法 - 一致性哈希

哈希(hash)算法

一致性哈希算法的前提是哈希算法

Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
(百度百科)

公式

key –[哈希]–> 值 –[取模]–> 余数

分布式系统下的应用

文件(标识值) –[哈希]–> 值[整数] –[对机器数取模]–> 余数 [对应服务器编号]

缺陷

当服务器数量改变时,会直接导致改变后, 文件使用公式取得的余数(服务器编号),
与其原先存储的服务器编号不一致, 从而无法获取到该文件.

应用在分布式缓存中导致的结果就是, 一段时间内大量请求无法从缓存中取得文件地址,
而直接访问数据库造成缓存雪崩.

一致性哈希

原理

以2^32(32位系统 4字节 * 8位)组成一个hash环, 然后用服务器编号对2^32取模

文件存储的时候也用文件标识对2^32取模,然后对应放到环上,
存储在顺时针查找到的第一台服务器上

接下来新增一台服务器D

如图红色区域为新增的服务器D, 这样一来, 文件3就受到了影响, 它原本存储在服务器C,
现在根据一致性hash算法查到是在服务器D, 但是,仅仅是红色区域受到了影响, 并没有影响
文件1, 文件2的访问.

应用场景

通过上述的分析可以了到一致性hash在服务器数量改变时只会影响一小部分应用,
所以被广泛的应用于分布式缓存, 因为这种机制可以极大程度地减少缓存雪崩发生的
概率. (memcache就是使用一致性hash这种机制来做分布式缓存)

Hash环偏斜及解决方案

所谓Hash环偏斜就是当我们服务器数量比较少时, 极有可能导致服务器在hash环上较为集中发布,
这样可能导致大量文件存储到一台服务器上, 缓存不均匀从而导致系统崩溃.

如图, 按照一致性hash算法, 文件1,2,3都会缓存到服务器A上

解决方案(保证缓存均匀):
1. 服务器数量尽量多
2. 基于现有的物理节点映射出许多虚拟节点