数据分区问题

数据集被分散到多个节点，有利用水平扩展，提高吞吐，因此有一系列的算法用于做数据分区，这些算法各有自己的优缺点。

• 随机分配(数据分布相对均匀，但是客户端不能识别出数据在哪个node上)
• 单个全局的缓存(单点问题，可用性低，性能问题，锁竞争)
• 按照key的range来分区(数据分布不均，不利于水平扩展)
• 静态的hash函数来分区(需要处理hash冲突，不利于水平扩展，节点的动态新增和删除会导致数据rehashed)
• 一致性hash(当节点动态变化时，一致性哈希可以最小化数据rehashed的影响)

一致性哈希是如何工作的?

• hash函数的输出会放到一个hash环(hash ring)上
• 每一个node对其IP进行hash，以此来在hash环上进行分配
• 使用相同的hash函数对数据的key进行hash，以找到该key在hash环上的位置
• hash环从key的位置开始按顺时针方向遍历，直到找到有效的node
• 最终数据存储在找到的node节点上

如下图，可以看到，首先使用hash函数针对node的ip/hostname进行hash，将其分布到hash环上。当客户端获取对应key的数据时，先使用相同的hash函数进行hash，如果发现对应位置没有node，就按照顺时针往下寻找，直到找到一个有效的node，然后从node中查询对应的key，如果没有查询到就miss了。

任何一个节点移除只会影响这个节点本身，对于其他节点不影响，对于移除节点的访问，都会继续请求这个节点在hash ring中的下一个节点。导致被移除节点上的数据被转移到下一个节点上。

对于新增的节点，也不影响hash ring中的其他节点本身，只会导致下一个节点中的部分key会转移到新增的节点上。