本文简单总结RDMS对数据进行shard的一些套路。
Why sharding
早期的RDMS（Relational Database Management System）是单物理机单实例。随着用户量、访问量的急剧上升，20%的表可能占据了80%的数据量（二八法则），这时你可能会考虑将大数据表拆到机器A和机器B，小数据表拆到机器C。好处是显而易见的，原先压在一部机器的负载分散到多部机器，坏处是以前的一些SQL可能需要改写，因为我们无法跨库做join，尽可能把需要join的表分在一部机器的同一个库内可以暂时规避这个问题。
很快的，用户量和数据继续蹭蹭蹭的往上涨，有些表已经是百万行级别了，很快又要撑不住了。这时，你把目光聚焦在那些大表上，发现有些表的某些列是BLOB型数据（图片或文件等）。这些数据一般不需要范围查询，基本都是指定主键查出来的，于是你把这些列分离出去，单独存在文件或图片服务器上，你的一些糟糕的select * from xxx的语句从此性能得到提升，新增的insert因为不需要写BLOB也比以前快了一丢丢，数据表的总体数据量大小也大大减少，代价是你需要根据主键到图片或文件服务器获取你要的BLOB数据。
（知识扩展：select *语句需要查聚簇索引——主键索引，因为BLOB数据一般不建立索引，需要在主键索引才能拿到没建立索引的列的数据）
但是，把部分列分离出去，行数还是那么多啊！按照业务规模发展下去，行数分分钟就要破千万了啊！所有读写负载都打在了单表单服务器上，想想都是噩梦，怎么破？
这时候只能把一张大表水平切几刀（表结构不变），切成多张小表了。这便是本文讨论的范围，主要是一些思路上的总结。
- 怎么切：sharding strategy
- 切完后怎么扩容：resharding
- 切完有什么好处，又有何副作用以及业界是怎么解决这些问题的：side effect
Sharding strategy compare
Case 1 静态算式规则切分
上图的id是主键，4是结点总数，id % 4即静态算术规则。输入主键计算出数值下标，由数值到LOOKUP表就可以确定数据在哪台服务器上。
（注：LOOKUP表维护下标与真实服务器信息的对应关系，简单实现可以考虑配置在服务器，复杂的可以考虑引入Zookeeper）
1、如何扩容？
对于id % 4的规则，扩容类似于Java HashMap的rebash的过程。如果id不是一个整型数值，规则需要改写成hash(id) % 4，hash函数用于将id转为int。假如新增一个节点，此时需要经历以下过程：
- 将第0结点上的id做
id % 5，如果值不为0，则将该行记录移动到其他服务器上； - 其他结点以此类推。
这里有两个显而易见的坏处，
- 几乎每个结点的数据都需要重新打散，分发到其他服务器。这需要大量的磁盘IO，可谓伤筋动骨，改进办法见下文；
- 在扩容未完成时，该从哪个结点读？该从哪个结点写？如果要做到动态扩容不影响读写，那么就需要做非常非常多的额外工作。一个可以考虑的策略是，挂个升级公告，停止对外服务，扩容期间数据库无任何读写，这应该算是一般游戏公司的做法了。
2、好处是什么？
读和写能够比较均匀的打到各个节点。
- 对于自增主键式的写入，不会出现负载都打在一个结点的情况；
- 对于频繁读最近新增的数据的case，也不会出现负载都打在一个结点的情况。
3、代价是什么？是否有解决思路？
对于上面的id % 4问题，其实可以换一个思路。虽然我们只有4台物理机，但我们可以把规则定为id % 1024，即逻辑上有1024台机。然后通过配置上面说的LOOKUP表，实现4台物理机均摊这1024台逻辑机器的角色，这样可以规避上面的新增结点需要全部数据打散的问题，这也是一致性哈希
的思想。1024这数值必须是公司业务理论上不能达到的上限（除了顶尖的那几家互联网公司，一般公司也不会超过这个值了），否则还是会出现上面的痛点。
主键被打散，对按主键范围查询不友好，范围查询基本退化成了全表查询。如果主键范围查询时还带order by，那还得在查询完后自行对数据进行排序。
解决思路是，数据在单节点是有序的，将查询分发给每个结点，并行去查数据，最后对返回结果做合并。如果要求order by，则在合并结果集时进行两两的归并排序。
Case 2 范围规则切分
与上面的算式规则不同的是，这里需要一个range函数，输入主键后得到一个range数值，然后再去查LOOKUP表确定数据落在哪个结点。range函数一般有两种，有序型和无序性。输入[1,2,3,4]这一组数据后，输出的数据依然是有序的称为有序型（一般应用在数据类型），输出无序的称为无序型（比如hash函数）。
1、如何扩容？
相比“静态算式规则”，“范围规则”的扩容较为简单。以将范围[10, 30]拆成[10,20]和[21,30]为例，大概需要以下过程，
- 新增物理节点；
- 标记旧节点[10,30]当前binlog的ID为A；
- 利用MySQL的可重复读（repeatable read）的特性，将数据copy到新节点；
- 完成copy后，新节点从上文binlog的ID为A的位置，同步旧节点的binlog数据，仅应用对[21,30]范围有影响的语句；
- binlog同步完成后，修改LOOKUP表，使得后续对[21,30]范围的读写路由到新节点，清除旧节点[21,30]这个范围的数据；
这里有几个挑战，1）数据表太大一次性拷贝将导致长事务
怎么办，2）如何确保数据已全部同步到新节点，3）修改LOOKUP表前已经有读写数据的请求被路由到旧节点该怎么办？
对于第1点，可以考虑，
- 先拷贝[21至25]的数据，然后读取旧节点的最新binlog的ID为B；
- 紧接着拷贝[26至30]的数据；
- 将binlog的id为A至B的改动应用在[21至25]这个数据范围；
- 将binlog的id为B至最新binlog的ID的全部数据应用到[21至30]这个范围；
对于第2点，可以考虑通过新、旧节点间的lag来判断，并产生一个触发信号。
对于第3点，需要有某个仲裁节点，在收到前述触发信号后，阻塞后续所有对于[20,30]的读写请求，直到旧节点对于[20,30]已发起的SQL语句已经全部处理返回后，修改LOOKUP表再让被阻塞的读写请求通行。
2、好处是什么？
相较于“静态算式规则”，“范围规则”的扩容更为简单，且不存在预设的最大节点数的影响。
对于上文的range函数，如果是有序型的，
- 则对范围查询较为友好；
- 但却对自增主键式写入不友好（负载都压在最后一个结点），以及可能会导致hotspot（最近新增数据的读都压在最后一个结点），除非更换range函数为无序型的否则没有解决方案。
如果是无序型的，
- 则对范围查询不友好，解决思路同上文；
- 但却能很好的将读写负载分散到各节点。
3、代价是什么？是否有解决思路？
上文已提及。
Common issue
上面提到的两种sharding的case，有一些共同问题如下。
一、都需要解决跨节点join的问题。业界解决思路是通过应用层代码去处理join，即先查小表A，再用小表A的结果作为参数去查询需要join的大表B（这里的大、小是相对的含义）；另外一种则是通过代理层去解决。
二、都需要解决跨节点transaction的问题。业界的解决思路一般是改进式的2PC(Two-phase commit protocol)。
三、如果主键有多个列应该如何sharding。假如主键是id和time，可以先通过id来定位到机器组0（假设有A、B、C、D四部机器组成），然后再由time来定位到A、B、C、D的其中一部机器。如果有超过2个主键呢？你确定你需要这么多主键吗？
四、如何支持非聚簇索引。RDMS中，表除了聚簇索引，还有非聚簇索引。在已经sharding的前提下，如果要以非聚簇索引的列作为查询条件去查询数据，此时查询便退化成了全节点扫描。一个解决思路是，将非聚簇索引和聚簇索引单独建一张表（冗余表），然后以非聚簇索引去sharding，查询时先查冗余表，然后再回表到主表，以此避免全节点扫描。
Conclusion
本文介绍了两种sharding方式。一种是算术规则式，需要先预估逻辑节点的最大值，以避免代价昂贵的全节点rehash；另一种是范围规则式，其关键在于range函数的选取——有顺序型和无序型两种。
Reference
How Sharding Works
ClustrixDB Data Distribution
Challenges of Sharding MySQL