一、背景
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