关于数据库:ShardingSphere-4x-数据分片内核剖析之归并引擎

30次阅读

共计 3712 个字符,预计需要花费 10 分钟才能阅读完成。

将从各个数据节点获取的多数据后果集,组合成为一个后果集并正确的返回至申请客户端,称为后果归并。

ShardingSphere 反对的后果归并从性能上分为遍历、排序、分组、分页和聚合 5 种类型,它们是组合而非互斥的关系。
从构造划分,可分为流式归并、内存归并和装璜者归并。流式归并和内存归并是互斥的,装璜者归并能够在流式归并和内存归并之上做进一步的解决。

因为从数据库中返回的后果集是逐条返回的,并不需要将所有的数据一次性加载至内存中,因而,在进行后果归并时,沿用数据库返回后果集的形式进行归并,可能极大缩小内存的耗费,是归并形式的优先选择。

流式归并是指每一次从后果集中获取到的数据,都可能通过逐条获取的形式返回正确的单条数据,它与数据库原生的返回后果集的形式最为符合。遍历、排序以及流式分组都属于流式归并的一种。

内存归并则是须要将后果集的所有数据都遍历并存储在内存中,再通过对立的分组、排序以及聚合等计算之后,再将其封装成为逐条拜访的数据后果集返回。

装璜者归并是对所有的后果集归并进行对立的性能加强,目前装璜者归并有分页归并和聚合归并这 2 种类型。

遍历归并

它是最为简略的归并形式。
只需将多个数据后果汇合并为一个单向链表即可。在遍历实现链表中以后数据后果集之后,将链表元素后移一位,持续遍历下一个数据后果集即可。

排序归并

因为在 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 的形式排序队列。

下图则展示了进行 next 调用的时候,排序归并是如何进行的。
通过图中咱们能够看到,当进行第一次 next 调用时,排在队列首位的 t_score_0 将会被弹出队列,并且将以后游标指向的数据值(也就是 100)返回至查问客户端,并且将游标下移一位之后,从新放入优先级队列。
而优先级队列也会依据 t_score_0 的以后数据后果集指向游标的数据值(这里是 90)进行排序,依据以后数值,t_score_0 排列在队列的最初一位。
之前队列中排名第二的 t_score_2 的数据后果集则主动排在了队列首位。

在进行第二次 next 时,只须要将目前排列在队列首位的 t_score_2 弹出队列,并且将其数据后果集游标指向的值返回至客户端,并下移游标,持续退出队列排队,以此类推。
当一个后果集中曾经没有数据了,则无需再次退出队列。

能够看到,对于每个数据后果集中的数据有序,而多数据后果集整体无序的状况下,ShardingSphere 无需将所有的数据都加载至内存即可排序。
它应用的是流式归并的形式,每次 next 仅获取惟一正确的一条数据,极大的节俭了内存的耗费。

从另一个角度来说,ShardingSphere 的排序归并,是在保护数据后果集的纵轴和横轴这两个维度的有序性。
纵轴是指每个数据后果集自身,它是人造有序的,它通过蕴含 ORDER BY 的 SQL 所获取。
横轴是指每个数据后果集以后游标所指向的值,它须要通过优先级队列来保护其正确程序。
每一次数据后果集以后游标的下移,都须要将该数据后果集从新放入优先级队列排序,而只有排列在队列首位的数据后果集才可能产生游标下移的操作。

分组归并

分组归并的状况最为简单,它分为流式分组归并和内存分组归并。
流式分组归并要求 SQL 的排序项与分组项的字段以及排序类型(ASC 或 DESC)必须保持一致,否则只能通过内存归并能力保障其数据的正确性。

举例说明,假如依据科目分片,表构造中蕴含考生的姓名(为了简略起见,不思考重名的状况)和分数。通过 SQL 获取每位考生的总分,可通过如下 SQL:

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

在分组项与排序项完全一致的状况下,获得的数据是间断的,分组所需的数据全数存在于各个数据后果集的以后游标所指向的数据值,因而能够采纳流式归并。如下图所示。

进行归并时,逻辑与排序归并相似。
下图展示了进行 next 调用的时候,流式分组归并是如何进行的。

通过图中咱们能够看到,当进行第一次 next 调用时,排在队列首位的 t_score_java 将会被弹出队列,并且将分组值同为“Jetty”的其余后果集中的数据一起弹出队列。
在获取了所有的姓名为“Jetty”的同学的分数之后,进行累加操作,那么,在第一次 next 调用完结后,取出的后果集是“Jetty”的分数总和。
与此同时,所有的数据后果集中的游标都将下移至数据值“Jetty”的下一个不同的数据值,并且依据数据后果集以后游标指向的值进行重排序。
因而,蕴含名字顺着第二位的“John”的相干数据后果集则排在的队列的前列。

流式分组归并与排序归并的区别仅仅在于两点:

  1. 它会一次性的将多个数据后果集中的分组项雷同的数据全数取出。
  2. 它须要依据聚合函数的类型进行聚合计算。

对于分组项与排序项不统一的状况,因为须要获取分组的相干的数据值并非间断的,因而无奈应用流式归并,须要将所有的后果集数据加载至内存中进行分组和聚合。
例如,若通过以下 SQL 获取每位考生的总分并依照分数从高至低排序:

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

那么各个数据后果集中取出的数据与排序归并那张图的上半局部的表构造的原始数据统一,是无奈进行流式归并的。

当 SQL 中只蕴含分组语句时,依据不同数据库的实现,其排序的程序不肯定与分组程序统一。
但因为排序语句的缺失,则示意此 SQL 并不在意排序程序。
因而,ShardingSphere 通过 SQL 优化的改写,主动减少与分组项统一的排序项,使其可能从耗费内存的内存分组归并形式转化为流式分组归并计划。

聚合归并

无论是流式分组归并还是内存分组归并,对聚合函数的解决都是统一的。
除了分组的 SQL 之外,不进行分组的 SQL 也能够应用聚合函数。
因而,聚合归并是在之前介绍的归并类的之上追加的归并能力,即装璜者模式。聚合函数能够归类为比拟、累加和求平均值这 3 种类型。

比拟类型的聚合函数是指 MAXMIN。它们须要对每一个同组的后果集数据进行比拟,并且间接返回其最大或最小值即可。

累加类型的聚合函数是指 SUMCOUNT。它们须要将每一个同组的后果集数据进行累加。

求平均值的聚合函数只有 AVG。它必须通过 SQL 改写的SUMCOUNT进行计算,相干内容已在 SQL 改写的内容中涵盖,不再赘述。

分页归并

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

ShardingSphere 的分页性能比拟容易让使用者误会,用户通常认为分页归并会占用大量内存。
在分布式的场景中,将 LIMIT 10000000, 10 改写为LIMIT 0, 10000010,能力保障其数据的正确性。
用户非常容易产生 ShardingSphere 会将大量无意义的数据加载至内存中,造成内存溢出危险的错觉。
其实,通过流式归并的原理可知,会将数据全副加载到内存中的只有内存分组归并这一种状况。
而通常来说,进行 OLAP 的分组 SQL,不会产生大量的后果数据,它更多的用于大量的计算,以及大量后果产出的场景。
除了内存分组归并这种状况之外,其余状况都通过流式归并获取数据后果集,因而 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;

归并引擎的整体构造划分如下图。

正文完
 0