一、背景
1.1 分布式数据库架构
以后分布式数据库架构有不少，然而总体架构相差不大，次要组件都蕴含协调节点、数据分片、元数据节点、全局时钟。一种常见的分布式架构如下图：
- gtm：全局事务管理器 (全局时钟)，一主多备；
- catalog: 元数据管理，一主多备；
- group: 程度分片, 每个 group 由一主多备数据存储节点组成；
- proxy : 协调节点，无状态，负责解决客户端的申请，把申请依照分片规定发送到数据分片，汇总数据分片返回的数据，协同其它组件保障分布式事务的一致性。
1.2 排序问题
分布式数据库中排序也是一种重要的性能。一条查问排序语句 select *from t1 order by field1，须要查问的数据可能会散布在不同的数据分片中。这就须要 proxy 对为不同数据分片返回的有序数据进行重排序，而后后给 client 返回全局有序的数据。
当相干的数据量不大时，proxy 可把不同数据分片返回的数据保留在内存中，而后对内存中的数据重排序后返回给 client。当相干的数据量比拟大时，如果把待重排序数据放到内存中则可能会导致 OOM，如果把待重排序数据暂存在 proxy 的磁盘中，则也有耗尽磁盘的危险并且会存在大量的磁盘 IO。上面将介绍一种分布式数据库排序及优化办法。
二、解决方案
2.1 排序计划介绍
为了进步分布式排序的性能，每个数据分片自身也要参加排序。这样在 proxy 上失去分片返回的数据是有序的，proxy 对有序的数据重排序能够采纳归并排序或者优先级队列排序办法，大大加重 proxy 的压力。
能够依据 proxy 内存大小配置 sort buffer 大小，通常默认为 10M。如果一次查问语句关联 N 个数据分片，则须要到 sort buffer 依照 N 份进行切分，每个数据分片对应切分后的 sort buffer 大小为 10M/N。
间接在内存中进行，具体步骤如下图：
- client 向 proxy 下发排序查问语句 select *from t1 order by id。
- proxy 依据分片键以及分片规定向相干的数据分片 group1、group2 下发排序查问语句 select *from t1 order by id。
- 数据分片在本地对数据进行查问排序后，发送有序数据到 proxy。
- proxy 把数据分片返回的有序数据存储在数据分片对应的 sort buffer 中，并对有序数据进行归并排序。
- proxy 把归并排序好的数据发送给 client。
2.2 排序计划缺点
这种办法只能满足小数据量排序，当排序的数据量较大咱们能够抉择调大 proxy 上的 sort buffer。然而调大 sort buffer 会占用更多的内存资源，所以不能无限度的调大 sort buffer。
2.3 排序优化思路
把数据分片返回的有序数据保留到磁盘上，而后对磁盘数据进行重排序。上面将介绍一种优化计划，针对大数据量进行分布式排序的办法。
三、优化计划
3.1 排序计划介绍
因为内存的限度，在内存中对大数据量数据进行归并排序计划不可行，针对这种状况须要把数据分片返回的数据暂存在磁盘中。具体优化计划步骤如下图：
1）client 向 proxy 下发排序查问语句 select *from t1 order by id。
2）proxy 依据分片键向相干的数据分片 group1、group2 下发排序查问语句 select *from t1 order by id。
3）数据分片在本地对数据进行查问排序后，发送有序数据到 proxy。
4）proxy 把数据分片返回的有序数据存储在数据分片对应的磁盘文件中。
5）应用优先级队列排序办法进行重排序：
- 每个数据分片出一条数据构建堆，heap 蕴含的节点个数等于数据分片的个数。
- 为了防止优先级队列排序过程中从磁盘中逐条读取数据造成的性能问题，proxy 从磁盘文件中读取数据预填充到数据分片对应的 sort buffer。
- 每个分片的 sort buffer 出一条数据结构成一个 heap。
- 从堆顶弹出数据发送给 client。
- 堆顶数据弹出后，从已弹出节点对应的 sort buffer 再读取一条数据 push 到堆。
- 分片 sort buffer 中的数据取完后，须要持续从对应的磁盘文件中拉取数据，对 sort buffer 进行填充。
- 直至取完所有数据发送到 client。
3.2 排序计划缺点
- proxy 须要收集完所有相干数据分片的有序数据存入磁盘能够解决内存不够的问题，然而磁盘也是无限的，当数据量太大在 proxy 上磁盘也可能无奈包容须要排序的数据。
- proxy 上把数据存在磁盘，存在大量的磁盘 IO。
- 以 select from t1 order by field1 limit 100w 为例：如果本次查问的数据在 50 个数据分片上，则 proxy 节点须要从每个数据分片上拉取 100w 数据而后保留到磁盘上。这样须要保留 5000W 数据 (100w50)，而 client 只须要 100w 条数据，节约了很多网络带宽和磁盘 IO。
3.3 排序优化思路
这种办法是 proxy 把相干数据分片的有序数据全副拉取到 proxy 上，而后再进行排序。咱们是否分批从数据分片拉取数据，批量数据处理后再从数据分片拉取下一批数据呢？上面将介绍一种分批排序的办法。
四、最终计划
4.1 排序计划介绍
proxy 上磁盘上不保留数据分片数据，一次从数据分片拉取固定大小的有序数据，proxy 把拉取的数据填充到分片对应的 sort buffer，sort buffer 中数据应用完后再次从对应的数据分片上拉取。具体步骤如下图：
1）client 向 proxy 下发排序查问语句 select *from t1 order by id。
2）proxy 依据分片键向相干的数据分片 group1、group2 下发排序查问语句 select *from t1 order by id。
3）数据分片在本地对数据进行查问排序后，发送固定大小有序数据到 proxy。
4）proxy 把数据分片返回的有序数据存储在数据分片对应的 sort buffer 中。
5）优先级队列排序。
- 每个数据分片对应的 sort buffer 出一条数据构建堆，堆节点的个数等于数据分片的个数.
- 从堆顶弹出数据发送给 client.
- 堆顶数据弹出后，从已弹出节点对应的 sort buffer 再读取一条数据 push 到堆.
- 分片 sort buffer 中的数据取完后，须要持续从对应的数据分片节点中拉取数据，对 sort buffer 进行填充.
- 直至取完所有数据发送到 client.
4.2 排序计划剖析
针对优化计划 3.2 存在的三个缺点的解决状况。
缺点 1 ：proxy 须要收集完所有相干数据分片的有序数据存入磁盘能够解决内存不够的问题，然而磁盘也是无限的，当数据量太大在 proxy 上磁盘也可能无奈包容须要排序的数据。
解决状况 ：从图中能够看出 proxy 的磁盘上不保留数据分片的数据。
缺点 2 ：proxy 上把数据存在磁盘，存在大量的磁盘 IO。
解决状况 ：proxy 的磁盘上不保留数据分片的数据，所以不存在磁盘压力太大问题。
缺点 3 ：select from t1 order by field1 limit 100w 为例：如果本次查问的数据在 50 个数据分片上，则 proxy 节点须要从每个数据分片上拉取 100w 数据而后保留到磁盘上，须要保留 5000W 数据 (100w50)，而 client 只须要 100w 条数据，节约了很多网络带宽和磁盘 IO。
解决状况 ：每次从数据分片拉取固定大小的数据，边排序边给客户端返回数据，当给客户端返回的数据达到 100W 时则实现本次查问，网络带宽节约失去大大改善。
假如 proxy 上数据分片对应的 sort buffer 大小为 2M，从数据分片拉取的数据量：
- 最坏状况 ：拉取的数据量为 2M*50+100W，并且不须要保留磁盘。
- 最好状况 ：数据分布很平均，给 client 返回 100w 数据后，所有 sort buffer 分片对应的数据正好根本取空 (都剩下一条)，此时拉取的数据量为 100W+50。
4.3 计划应用限度
1）数据分片节点自身反对排序，绝大多数数据分片都是反对排序的。
2）数据分片须要反对分批读取。
以 MySQL 作为数据分片为例，则须要 proxy 上能够应用流式查问或者游标查问。另外有些分布式数据库在设计时就思考到一些分布式的问题，它们数据分片节点在查问完结前始终保留上下文，它们的分批读取性能更高，这里就不在举例。
五、参考文献
1.JDBC 操作 MySQL（3）—查问
2.MySQL JDBC StreamResult 通信原理浅析
作者：vivo 互联网数据库团队 -Xia Qianyong