什么是partitioning（划分）
有时一台机器存不下所有数据，这时，可以把数据存储在多台机器上。如何划分每台机器应该存储哪些数据，这就是partitioning（划分）。
最简单的划分方法
假设有N台机器，把一个key映射到某台机器最简单方法：pos = hash(key) % N
优点是，足够简单，并且数据均匀分布在每台机器上。
但是，如果集群需要增减机器，存在致命缺陷！用一个小例子来说明：
假设当前集群包含3台机器，编号是0,1,2，集群中已存储数据是：0,1,2,3,4,5,6,7,8,9,10,11，共12个数字。用此方法，第0号机器存储0,3,6,9；第1号机器存储1,4,7,10；第2号机器存储2,5,8,11；
现在新增一台机器，编号变为0,1,2,3。那么此时，正确的数据分布是：第0号机器存储0,4,8；第1号机器存储1,5,9；第2号机器存储2,6,10；第3号机器存储3,7,11；如果不是这样分布，客户端就无法读取到数据，因此新加机器后，需要对数据进行移动（data rebalance）
需要发生移动的数据用黑体标出：0,1,2,3,4,5,6,7,8,9,10,11。几乎所有数据都需要移动，假设集群包含100台机器，一共存储了100TB数据，就需要100TB数据在集群间传输，消耗太多资源。理论上，只要从原来的100台机器上，每一台拿出一点数据，凑出1TB数据移动到新增的那台机器上，即可达到数据均匀分布。
教导主任的方法
上面介绍的方法，一条数据的去向，完全由取模运算决定。
假设，学校有n个班，有一天要新增一个班，学校会怎么做？？？
很自然，由教导主任决定每个班应该有哪些小朋友去新班。
教导主任掌握了每一个班的情况，由她来做分配自然是最简单的方法。
这里，班级相当于机器，小朋友相当于数据，教导主任相当于掌握全局信息的人。
教导主任只需要维护：小朋友-->班级 的映射。家长来接孩子时，只需问一下教导主任，就知道自己孩子在哪个班，记住就好，以后就不用经常麻烦教导主任了。
对教导主任的方法做一点优化
教导主任需要记录所有 小朋友-->班级 的映射，笔者的小学有2000多个小朋友，估计教导主任维护这么多条记录，一定要疯了。
一个优化是，把小朋友分组，例如按照姓氏，姓“王”的一组，姓“李”的一组，教导主任此时只要维护 组-->班级 的映射。需要维护的映射数量，变少了很多。此时，一个班级包含“王”，“刘”，“李”三个组，另一个班级包含“祝”，第三个班级包含“房”，“蔡”
但是，现在的问题是，不同组的小朋友数量差别很大；有的班级，人数很多，有的班级人数很少。
但无论如何，通过分组，解决了教导主任需要维护太多映射的问题。下一个问题是，如何让组的规模均匀，这个问题不难想，这里不再讲了。
总结
增加教导主任的好处：
- 通过教导主任，由她掌握全局信息，划分班级的问题变得简单而自然；
- 在分布式问题中，增加一个教导主任，很多情景可以变得简单；
2018-06-15更新
其实，总结起来，有两种方式：将key分桶，每个机器负责一些桶（一致性哈希也是这个原理），易保持负载均衡，但是每台机器会失去key的连续性；另一种方式是按key范围切分，能保持key有序，但是易打破负载均衡。
网友评论