分布式 - 跨库分页

 select * from T order by time offset X limit Y 的跨M个库分页。

全局

每个库都必须返回 X+Y 个数据,所得到的 M*(X+Y) 在服务层进行内存排序,然后再取总的偏移量X后的Y条记录。

  • 优点: 精准返回所需数据。
  • 缺点: (1)每个分库需要返回更多的数据,占用网络带宽;(2)需要服务层的计算;(3)这个算法随着页码的增大(即X的增大),性能平方级下降。

禁止跳页查询(业务折衷)

获取第一页的方式和全局策略是一样的,但获取第N页(N>1)时,我们取 N-1 页的最大time,即time_max, 对于每个分库执行 select * from T order by time where time > time_max limit Y,这样在服务层再总排序取前Y条记录。

  • 优点: 相比全局策略的性能平方级下降,该策略的性能是恒定的。
  • 缺点: 禁止跳页查询。

[推荐] 二次查询

数学原理:对于一个有序序列分成 M 个长度不等的有序子序列,M个有序子序列中每个有序子序列前X个元素中的最大值集中起来,再取其中最小值,则该最小值一定小于等于原来有序序列的第 M*X 个元素值。
假设该最小值大于原序列的第 MX 个元素值,那么M个有序子序列后面第X+个元素值都大于原序列的第 MX 个元素值,即构成原序列前MX 个元素只能是M个有序子序列的前X-个元素,因为MX- < M*X,所以假设不成立。

步骤:

  1. 改写分库sql为: select * from T order by time offset ceil(X/M) limit Y
  2. 获取所有分库sql中返回的最小time中的最小time,即time_min(详见上面原理)
  3. 改写分库sql为:select * from T order by time between time_min and 各自分库的最大time(从第1步中得到)
  4. 第3步的各个分库的返回结果比第一步多,当然time_min的那个分库的返回结果肯定不变(所以time_min的那个分库的sql在实现时可以不用执行)。假设所有分库总共多出 K 条数据,则全局_offset = ceil(X/M) * M - K 。(详见上面原理)
  5. 将第3步返回的结果集合并,即第一条数据就是time_min的那条,其_offset由第四步已经得到;我们直接在该结果集的中从第(原始sql的offset - _offset + 2)条数据开始获取Y条数据。
  • 优点: 该策略的性能是几乎恒定。
  • 缺点: 两次查询;内存中要将结果集合并。

你可能感兴趣的