当我们在做数据库分库分表或者是分布式缓存时，不可避免的都会遇到一个问题:
如何将数据均匀的分散到各个节点中，并且尽量的在加减节点时能使受影响的数据最少。
Hash 取模
随机放置就不说了，会带来很多问题。通常最容易想到的方案就是 hash 取模了。
可以将传入的 Key 按照 index = hash(key) % N 这样来计算出需要存放的节点。其中 hash 函数是一个将字符串转换为正整数的哈希映射方法，N 就是节点的数量。
这样可以满足数据的均匀分配，但是这个算法的容错性和扩展性都较差。
比如增加或删除了一个节点时，所有的 Key 都需要重新计算，显然这样成本较高，为此需要一个算法满足分布均匀同时也要有良好的容错性和拓展性。
简单的例子
比如一台数据库如果能放下 1T 的数据，那么超过1T之后就放在第二个数据库里。当我们有 3 台数据库的机器，于是想到按照 from_user_id % 3 进行拆分。假如 3 台机器不够用了，现在就会出现问题了，我现在新买了1台机器，原来的%3，就变成了%4几乎所有的数据都要进行位置大迁移。
过多的数据迁移会造成的问题：
1. 慢，容易造成数据的不一致性
2. 迁移期间，服务器压力增大，容易挂
一致性 Hash 算法
由于上面的问题，所以我们需要一个Hash算法，当新增服务器的时候不需要大面积地转移数据。
一个简单的一致性Hash算法：
• 将 key 模一个很大的数，比如 360
• 将 360 分配给 n 台机器，每个机器负责一段区间
• 区间分配信息记录为一张表存在 Web Server 上
• 新加一台机器的时候，在表中选择一个位置插入，匀走相邻两台机器的一部分数据
比如n从2变化到3，只有1/3的数据移动
有什么问题呢？
1. 因为算法是“将数据最多的相邻两台机器均匀分为三台”。比如，3台机器变4台机器时，无法做到4台机器均匀分布
2. 新机器的数据只从两台老机器上获取，导致这两台老机器负载过大
改良版的一致性哈希算法 Consistent Hashing
1. 将取模的底数从 360 拓展到 2^64。
2. 将 0~2^64-1 看做一个很大的圆环(Ring)。
3. 将数据和机器都通过 hash function 换算到环上的一个点。
1. 数据取 key / row_key 作为 hash key
2.机器取MAC地址，或者机器固定名字如，database01，或者固定的 IP 地址
4. 每个数据放在哪台机器上，取决于在 Consistent Hash Ring 上顺时针碰到的下一个机器节点。
虚拟节点 Virtual Node
上面的方法还是有可能导致服务器上数据分配不均匀，为了更好地均匀分配数据，我们又加入了虚拟节点。
1. 一个实体机器(Real node) 对应若干虚拟机器(Virtual Node)，通常是1000个
2. 用一个数据结构存储这些 virtual nodes，支持快速的查询比某个数大的最小数（红黑树）
