分库分表在sharding中的实现

随着公司业务快速发展，数据库中数据量猛增，访问性能变慢。关系型数据库本身比较容易成为系统瓶颈、单机存储容量、连接数、处理能力有限。当单表的数据量达到1000W或100G以后，由于查询纬度较多，即使添加从库、优化索引，做很多操作时性能仍下降严重。

方案一：通过提升硬件来提高数据处理能力，比如增加存储容量、CPU等，这种方案成本较高，并且瓶颈在数据库服务本身，通过提高硬件得到的提升有限;

方案二：分库分表，使得单一数据库、单一数据表的数据量变小，从而达到提升数据库性能的目的。

通过将一个表按字段拆分成多张表，每张表只存储其中的部分字段。

带来的提升：

1. 减少了IO争抢，并减少了锁表的概率，浏览商品的用户，跟运营配置商品使用规则不会互相冲突。

2. 提升数据库IO效率，防止跨页，提高索引效率，充分发挥热门数据的操作效率，商品信息的操作效率不会被拖累。

垂直拆分后，可以对商品信息表再做水平拆分。

按照业务将一张大表里的数据根据规则拆分到多张表中。（对数据的拆分，不影响表结构）

1. 减少节点时;

2. 增加节点时;

一致性哈希算法通过一个叫作一致性哈希环的数据结构实现。这个环的起点是 0，终点是 2^32 - 1，并且起点与终点连接，故这个环的整数分布范围是 [0, 2^32-1]，如下图所示：

假设，我们现在对认领记录t，按opportunity_id维度分表，分成了t_0,t_1,t_2,t_3四张表，然后我们将这4张表分别进行hash运算，取值范围是0-2^32-1，这样，我们可以得到hash环上的4个点，分别标记为4张表的位置。

然后我们用同样的hash函数对接下来收到的每一条认领记录的opportunity_id进行运算，这样我们也得到了每一条认领记录在hash环上的位置。

然后接下来，在hash环上按顺时针方向找到离认领记录最近的一张表，将认领记录保存到这张表中。

假设在t1/t2表节点中间新增了一张表t5，那么需要移动的数据只有t1-t5之间的数据，相比于普通的hash算法，需要转移的数据大大减少。

1. 停机迁移

2. 双写

在包含分表的场景中，需要将分表配置中的逻辑表名称改写为路由之后所获取的真实表名称。仅分库则不需要表名称的改写。除此之外，还包括补列和分页信息修正等内容。

标志符改写

需要改写的标识符包括表名称、索引名称以及Schema名称。

表名称改写是指将找到逻辑表在原始SQL中的位置，并将其改写为真实表的过程。表名称改写是一个典型的需要对SQL进行解析的场景。从一个最简单的例子开始，若逻辑SQL为：

SELECT order_id FROM t_order WHERE order_id=1;

假设该SQL配置分片键order_id，并且order_id=1的情况，将路由至分片表1。那么改写之后的SQL应该为：

SELECT order_id FROM t_order_1 WHERE order_id=1;

补列

需要在查询语句中补列通常由两种情况导致。第一种情况是ShardingSphere需要在结果归并时获取相应数据，但该数据并未能通过查询的SQL返回。这种情况主要是针对GROUP BY和ORDER BY。结果归并时，需要根据GROUP BY和ORDER BY的字段项进行分组和排序，但如果原始SQL的选择项中若并未包含分组项或排序项，则需要对原始SQL进行改写。先看一下原始SQL中带有结果归并所需信息的场景：

SELECT order_id, user_id FROM t_order ORDER BY user_id;

由于使用user_id进行排序，在结果归并中需要能够获取到user_id的数据，而上面的SQL是能够获取到user_id数据的，因此无需补列。

如果选择项中不包含结果归并时所需的列，则需要进行补列，如以下SQL：

SELECT order_id FROM t_order ORDER BY user_id;

由于原始SQL中并不包含需要在结果归并中需要获取的user_id，因此需要对SQL进行补列改写。补列之后的SQL是：

SELECT order_id, user_id AS ORDER_BY_DERIVED_0 FROM t_order ORDER BY user_id;

补列的另一种情况是使用AVG聚合函数。在分布式的场景中，使用avg1 + avg2 + avg3 / 3计算平均值并不正确，需要改写为 (sum1 + sum2 + sum3) / (count1 + count2 + count3)。这就需要将包含AVG的SQL改写为SUM和COUNT，并在结果归并时重新计算平均值。例如以下SQL：

SELECT AVG(price) FROM t_order WHERE user_id=1;

需要改写为：

SELECT COUNT(price) AS AVG_DERIVED_COUNT_0, SUM(price) AS AVG_DERIVED_SUM_0 FROM t_order WHERE user_id=1;

然后才能够通过结果归并正确的计算平均值。

分页修正

从多个数据库获取分页数据与单数据库的场景是不同的。假设每10条数据为一页，取第2页数据。在分片环境下获取LIMIT 10, 10，归并之后再根据排序条件取出前10条数据是不正确的。举例说明，若SQL为：

SELECT score FROM t_score ORDER BY score DESC LIMIT 1, 2;

下图展示了不进行SQL的改写的分页执行结果。

通过图中所示，想要取得两个表中共同的按照分数排序的第2条和第3条数据，应该是95和90。由于执行的SQL只能从每个表中获取第2条和第3条数据，即从t_score_0表中获取的是90和80；从t_score_0表中获取的是85和75。因此进行结果归并时，只能从获取的90，80，85和75之中进行归并，那么结果归并无论怎么实现，都不可能获得正确的结果。

正确的做法是将分页条件改写为LIMIT 0, 3，取出所有前两页数据，再结合排序条件计算出正确的数据。下图展示了进行SQL改写之后的分页执行结果。

越获取偏移量位置靠后数据，使用LIMIT分页方式的效率就越低。有很多方法可以避免使用LIMIT进行分页。比如构建行记录数量与行偏移量的二级索引，或使用上次分页数据结尾ID作为下次查询条件的分页方式等。

分页信息修正时，如果使用占位符的方式书写SQL，则只需要改写参数列表即可，无需改写SQL本身。

批量拆分

在使用批量插入的SQL时，如果插入的数据是跨分片的，那么需要对SQL进行改写来防止将多余的数据写入到数据库中。插入操作与查询操作的不同之处在于，查询语句中即使用了不存在于当前分片的分片键，也不会对数据产生影响；而插入操作则必须将多余的分片键删除。举例说明，如下SQL：

INSERT INTO t_order (order_id, xxx) VALUES (1, 'xxx'), (2, 'xxx'), (3, 'xxx');

假设数据库仍然是按照order_id的奇偶值分为两片的，仅将这条SQL中的表名进行修改，然后发送至数据库完成SQL的执行 ，则两个分片都会写入相同的记录。虽然只有符合分片查询条件的数据才能够被查询语句取出，但存在冗余数据的实现方案并不合理。因此需要将SQL改写为：

INSERT INTO t_order_0 (order_id, xxx) VALUES (2, 'xxx');

INSERT INTO t_order_1 (order_id, xxx) VALUES (1, 'xxx'), (3, 'xxx');

使用IN的查询与批量插入的情况相似，不过IN操作并不会导致数据查询结果错误。通过对IN查询的改写，可以进一步的提升查询性能。如以下SQL：

SELECT * FROM t_order WHERE order_id IN (1, 2, 3);

改写为：

SELECT * FROM t_order_0 WHERE order_id IN (2);

SELECT * FROM t_order_1 WHERE order_id IN (1, 3);

可以进一步的提升查询性能。

排序归并

由于在SQL中存在ORDER BY语句，因此每个数据结果集自身是有序的，因此只需要将数据结果集当前游标指向的数据值进行排序即可。这相当于对多个有序的数组进行排序，归并排序是最适合此场景的排序算法。

ShardingSphere在对排序的查询进行归并时，将每个结果集的当前数据值进行比较（通过实现Java的Comparable接口完成），并将其放入优先级队列。每次获取下一条数据时，只需将队列顶端结果集的游标下移，并根据新游标重新进入优先级排序队列找到自己的位置即可。

通过一个例子来说明ShardingSphere的排序归并，下图是一个通过分数进行排序的示例图。

图中展示了3张表返回的数据结果集，每个数据结果集已经根据分数排序完毕，但是3个数据结果集之间是无序的。将3个数据结果集的当前游标指向的数据值进行排序，并放入优先级队列，t_score_0的第一个数据值最大，t_score_2的第一个数据值次之，t_score_1的第一个数据值最小，因此优先级队列根据t_score_0，t_score_2和t_score_1的方式排序队列。

分组归并

分组归并的情况最为复杂，它分为流式分组归并和内存分组归并。流式分组归并要求SQL的排序项与分组项的字段以及排序类型（ASC或DESC）必须保持一致，否则只能通过内存归并才能保证其数据的正确性。

举例说明，假设根据科目分片，表结构中包含考生的姓名（为了简单起见，不考虑重名的情况）和分数。通过SQL获取每位考生的总分，可通过如下SQL：

SELECT name, SUM(score) FROM t_score GROUP BY name ORDER BY name;

在分组项与排序项完全一致的情况下，取得的数据是连续的，分组所需的数据全数存在于各个数据结果集的当前游标所指向的数据值，因此可以采用流式归并。如下图所示。

聚合归并

比较类型的聚合函数是指MAX和MIN。它们需要对每一个同组的结果集数据进行比较，并且直接返回其最大或最小值即可。

累加类型的聚合函数是指SUM和COUNT。它们需要将每一个同组的结果集数据进行累加。

求平均值的聚合函数只有AVG。它必须通过SQL改写的SUM和COUNT进行计算。

分页归并

上文所述的所有归并类型都可能进行分页。分页也是追加在其他归并类型之上的装饰器，ShardingSphere通过装饰者模式来增加对数据结果集进行分页的能力。分页归并负责将无需获取的数据过滤掉。

ShardingSphere的分页功能比较容易让使用者误解，用户通常认为分页归并会占用大量内存。在分布式的场景中，将LIMIT 10000000, 10改写为LIMIT 0, 10000010，才能保证其数据的正确性。用户非常容易产生ShardingSphere会将大量无意义的数据加载至内存中，造成内存溢出风险的错觉。其实，通过流式归并的原理可知，会将数据全部加载到内存中的只有内存分组归并这一种情况。除了内存分组归并这种情况之外，其他情况都通过流式归并获取数据结果集，因此ShardingSphere会通过结果集的next方法将无需取出的数据全部跳过，并不会将其存入内存。

但同时需要注意的是，由于排序的需要，大量的数据仍然需要传输到ShardingSphere的内存空间。因此，采用LIMIT这种方式分页，并非最佳实践。由于LIMIT并不能通过索引查询数据，因此如果可以保证ID的连续性，通过ID进行分页是比较好的解决方案，例如：

SELECT * FROM t_order WHERE id > 100000 AND id <= 100010 ORDER BY id;

或通过记录上次查询结果的最后一条记录的ID进行下一页的查询，例如：

SELECT * FROM t_order WHERE id > 10000000 LIMIT 10；