Redis的Hash一致性

Hash一致性

Hash一致性算法介绍

一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真正得到应用。

Hash一致性应用

1.首先求出服务器（节点）的哈希值，并将其配置到0～232的圆上。
2.然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。
3.然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过232仍然找不到服务器，就会保存到第一台服务器上。
如图-12所示


当新增node节点时,那么根据哈希值计算的数据中node节点会落到该圆中,那么这时数据会发生动态的迁移,那么在新节点左侧的数据会受到影响,动态进行挂载.
如图-13所示

Hash一致性特点

平衡性(Balance)

说明:由于所有的节点进行hash一致性的计算,可能获取的结果在内存中位置相邻.可能会导致数据库分片不均的现象.这样会造成某些节点内存溢出.某些节点内存使用率较少.为了解决这类问题.提出了均衡性.
概念:让节点尽可能保证数据的均匀.每个节点只保存其中1/n的数据.
实现:哈希一致性算法中提出了虚拟节点的概念.如果出现数据存储偏差较大,则会为少的节点添加虚拟节点,共同争抢数据,最终达到1/n
如图-14所示

单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

分散性(Spread)

在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
如图-15所示

负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
如图-16所示