Sharding 分页原理分析

优质博文：IT-BLOG-CN

如果业务上需要执行如下分页查询，Sharding-JDBC如何执行分页查询的？ 官方文档

select * from student_time ORDER BY create_time ASC limit 1000, 5;

Sharding-JDBC分页查询时在每个分表中都查询1005条数据，然后在内存中排序，但问题是分页越大，数据量就越多，就会导致内存溢出。Sharding-JDBC对于合并排序做了很好的优化，但是还是需要传输1005条非常大的数据量，查询也非常耗时。

我们先看看Sharding-JDBC中对分页做的优化：

【1】采用流式处理 + 归并排序： 避免内存的过量占用。由于SQL改写不可避免的占用了额外的带宽，但并不会导致内存暴涨。 与直觉不同，大多数人认为Sharding-JDBC会将1,000,010 * 2记录全部加载至内存，进而占用大量内存而导致内存溢出。 但由于每个结果集的记录是有序的，因此Sharding-JDBC每次仅获取各个分片的当前结果集记录，驻留在内存中的记录仅为当前路由到的分片的结果集的当前游标指向而已。 对于本身即有序的待排序对象，归并排序的时间复杂度仅为O(n)，性能损耗很小。

Sharding-JDBC分片查询流程：
1、从各个数据节点获取对应的数据集；
2、将数据集进行组合/归并最后得到一个符合预期的结果集；
3、将正确的数据集返回；

Sharding-JDBC的归并由归并引擎负责，归并引擎提供了三种归并方式：
1、流式归并： 流式归并是指每一次从结果集中获取到的数据都能够通过逐条获取的方式返回正确的单条数据，他与数据库原生的返回结果集的方式最为契合。遍历、排序以及流式分组都属于流失归并的一种。

因为流式归并是从数据库中返回的结果集是逐条返回的，并不需要将所有的数据一次性加载至内存中，因此，在进行结果归并时，沿用数据库返回结果集的方式进行归并，能够极大减少内存的消耗，是归并方式的优先选择。

优点：
节省内存： 流式处理允许在内存中只保留当前处理的数据，而不是将整个结果集加载到内存中。这对于处理大数据集非常有利，因为它避免了内存溢出的问题。
实时性： 流式处理可以在数据还在传输的过程中开始处理，这样可以减少等待时间，提高查询的实时性。

缺点：
长连接占用资源： 每次只获取一条数据会导致数据库连接长时间占用，可能会消耗更多的数据库连接资源，特别是在并发查询较多的情况下。
性能开销： 每次获取一条数据需要多次网络往返，这可能会增加网络开销和延迟，特别是在高延迟网络环境中。

2、内存归并： 内存归并则是需要将结果集的所有数据都遍历并存储在内存中，再通过统一的分组、排序以及聚合等计算之后，再将其封装成为逐条访问的数据结果集返回。
3、装饰者归并： 装饰者归并是对所有的结果集归并进行统一的功能增强，目前装饰者归并有分页归并和聚合归并这2种类型。

流失归并的原理

ShardingJDBC的流式处理和JDBC的ResultSet的原理是一样的，主要是通过和数据库保持长连接，每次next都只取当前游标所在位置的一条数据，然后在内存中进行归并。

具体流程如下： 假设user表分为db0: user_0,db1: user_1, db2: user_2三张表

1、当进行分页查询时，会将查询语句下发到三个数据源分别进行获取：

2、数据源执行了sql后，并不会将查询到的数据集直接返回给客户端，而是先将结果集存储在数据源本地，等待client通过游标一条条读取。每一个表都会维护一个自己表的游标，初始位置为第一条记录。

3、每一轮都只传输游标当前指向的记录，client会将接收到的记录加入优先级队列，第一轮的时候client维护的优先级队列如下所示。优先级队列是按照sql要求的排序字段排序。

4、优先级队列队首出队到优先级队列PriorityQueue，会执行next，去对应的db中取下一条记录，此时数据源维护的游标要向下移动一格。上述例子中，便会去user_1中取出下一条记录，再重新入队进行排序，第二轮的结果如下图所示。

出队的数据存在哪里？
内存缓冲区： 当查询结果从各个分片返回时，Sharding-JDBC会将这些结果暂时存储在内存缓冲区中。在调用next()方法时，从缓冲区中获取下一条记录并返回给调用者。这种方式确保了数据在内存中是可用的，直到被处理完毕。
合并和排序： 在分页查询过程中，·Sharding-JDBC会将来自不同分片的结果集进行合并和排序。合并和排序后的结果集也会暂时存储在内存中，以便在调用next()方法时能够顺序返回正确的记录。 **游标位置：** 游标会记录当前的位置，以便在调用next()时能够正确返回下一条记录。这种机制确保了分页查询的顺序性和一致性。 **临时存储：** 在某些情况下，如果查询结果集非常大，内存不足以存储所有数据，Sharding-JDBC`可能会使用临时文件或其他形式的临时存储来保存部分结果集。这样可以避免内存溢出问题，但会牺牲一些性能。

在Sharding-JDBC的分页查询过程中，数据通常会暂时存储在内存缓冲区中，直到被处理完毕。如果内存不足，可能会使用临时存储来保存部分数据。游标记录当前的位置，以确保能够顺序返回正确的记录。

5、优先级队列操作next的同时，内部维护了一个rowNumber，用来表示当前记录是第几个，每次取next时，都会+1，源码部分如下：

public boolean next() throws SQLException {
  if (this.skipAll) {
    return false;
  } else if (this.limit.getRowCountValue < 0) {
    return this.getMergerdResult().next();
  } else {
    return ++this.rowNumber <= this.limit.getRowCountValue() && this.getMergedResult().next();
  }
}

limit分页的时候，便是通过这个字段找到对应开始的记录，开始拼接有效的结果集。

【2】Sharding-JDBC对仅落至单分片的查询进行进一步优化。 落至单分片查询的请求并不需要改写SQL也可以保证记录的正确性，因此在此种情况下，Sharding-JDBC并未进行SQL改写，从而达到节省带宽的目的。