分布式数据库的分页方案

本篇文章介绍了在 DRDS 上做时间序数据分页展示的一种方法，初看简单，实则细节较多，需要一定的关系型数据库基础，也是我们用户在实际使用产品过程中碰到的问题之一，这里分享给大家。

来实现一个分页吧

日常业务需求中，按时间序对数据进行分页展示是一个非常普遍的需求，单机关系型数据库有比较标准化的解决方案，但是这个需求在分布式数据库中实现，粗看比较简单，实际上却相当复杂，如果要做好，需要有比较扎实的关系型数据库认知。 

这个问题分为两个部分：

1. 功能性要求：

   a.数据需按照时间顺序进行返回

   b.所有数据均需要被遍历到，不能有遗漏

   c.每页返回100条数据

   d.同一个时间精度内（例如同一个毫秒内），会有多条数据同时被插入

2. 性能要求：

   a.性能不能随页码的增加而衰减，需要高效并且恒定

   b.性能不能随着数据量的增加而衰减，例如10W条数据的时候很高效，100亿条数据的时候也很高效

单机数据库的做法

对于单机数据库而言，以MySQL 为例，功能部分，直接按照自增主键从小到大排列即可，因为自增主键的大小能够区分出数据生成的前后关系，所以功能上不存在问题。

性能部分优化，在 SQL带其他过滤条件的情况下，可以将扁平的带 LIMIT m,n 语句优化成嵌套子查询以便让优化器做索引覆盖，避免在磁盘上遍历数据，SQL 如下所示:

SELECT *
        FROM table a JOIN(
        SELECT pk FROMtable
        WHERE some_column= ?
        ORDER BY pk LIMIT m, n) b ON a.pk= b.pk

在分布式数据库中实现的难点

对于单机数据库来说，因为存在时间序的自增主键，这个需求变得比较简单，但是对于分布式数据库而言，这个问题就变得比较复杂，主要因为主键大小和数据生成时间并没有本质关联，即使是分布式强一致数据库，保证严格时间序代价也很高，这个导致只能通过类似 GMT_CREATE 这种时间字段进行排序分页，但是 GMT_CREATE 可能重复，或者存在大量重复，这个导致分页按时间排序处理变得更加复杂。

另外性能层面，我们如同MySQL 不能使用扁平的带LIMIT m,n语句进行分页处理，但是同时也不能优化成带子查询的分页语句，因为数据分片的原因，需要将 LIMIT m,n 优化成 LIMIT 0,m+n ,分页挪到非常大的时候，需要返回到 DRDS 大量数据,再 skip 掉不必要的数据，即使做了倒序优化，一张拆分表性能最差的一页数据查询需要返回表中一半的数据才能满足需求，这个在拆分表有10亿或者100亿数据的时候，很难满足性能需求。

DRDS的方案

对这个问题仔细分析后，我们提出了一个方案。为了避免返回大量的中间结果数据，我们希望不指定 LIMIT 的 OFFSET，而是用上一页的最大值直接跳转到下一页的起始处，因此业务做一定的妥协，功能上增加如下约束：

 1. 提供下一页、上一页、首页、尾页功能

 2. 可以在当前页相邻的几页进行跳转（例如前后10页）

 3. 不允许做任意页的跳转 

对于单机数据库，我们可以使用如下的 SQL 实现上述的需求：

SELECT *
        FROM table
        WHERE pk> 上一页pk最大值 ORDRE BY pk LIMIT n

分布式数据库：

1. 增加 GMT_CREATE 字段，其默认值为CURRENT_TIMESTAMP

2. 我们仍然按照 GMT_CREATE 时间字段进行第一个维度排序，但是 GMT_CREATE 有重复，我们希望有一个固定顺序，所以再以主键为第二个维度排序，所以排序部分为 ORDER BY gmt_create,pk 。

3. 我们记住每一页 GMT_CREATE 和 PK 的最大值作为下一页数据的起始值，但是前面提到过 GMT_CREATE 有数据重复，如果通过简单AND条件拼接，会导致漏数据，所以我们将条件写为：

gmt_create>= ?
        AND(gmt_create> ?or pk> ?)

从查询逻辑上规避掉GMT_CREATE 重复带来的可能漏数据的状况，分页 SQL 变成了这个：

SELECT *
        FROM page_test
        WHERE gmt_create>= ?
        AND(gmt_create> ?
        OR pk> ?)
        ORDER BY gmt_create,
        pk LIMIT n

当然在MySQL 5.7上，我们还可以直接做二元组的比较（5.7之前的版本，多元组的比较 MySQL 无法利用到组合索引）：

SELECT *
        FROM page_test
        WHERE(gmt_create, pk)> （?, ?）ORDER BY gmt_create, pk LIMIT n

结果验证和总结

如下图page_test3表，数据量为36亿多条，表结构如图所示，总共拆了96张表，4个RDS存储数据。

 其中数据起始值如下:

如果我们挑选数据集中间的值，从下图看性能也很好，所以只要按照这套方案做分布式数据库分页或者全量扫描数据，性能将不会劣化，可以严格按照时间序排列，并且不会扫漏已经存在于数据库中的数据。

代码

package com.taobao.tddl.sample;

import java.sql.Connection;
import java.sql.PreparedStatement;
import java.sql.ResultSet;

import com.alibaba.druid.pool.DruidDataSource;

public class PageSample {

    public static void main(String[] args) throws Exception {

        DruidDataSource ds = new DruidDataSource();
        ds.setUrl(
                "jdbc:mysql://drdsxxxx.drds.aliyuncs.com:3306/dbname?characterEncoding=utf8&rewriteBatchedStatements=true&clobberStreamingResults=true&allowMultiQueries=true");
        ds.setUsername("user");
        ds.setPassword("password");
        ds.init();
        int index = 0;
        boolean first = true;
        Object maxGmtCreate = null;
        long maxId = -1;
        while (true) {
            Connection conn = null;
            try {
                conn = ds.getConnection();
                PreparedStatement ps = null;
                if (first) {
                    ps = conn.prepareStatement("SELECT * FROM page_test  order by gmt_create,id limit 99");

                    first = false;
                } else {
                    ps = conn.prepareStatement(
                            "SELECT * FROM page_test where gmt_create >= ? and (gmt_create > ? or id > ?) order by gmt_create,id limit 99");
                    ps.setObject(1, maxGmtCreate);
                    ps.setObject(2, maxGmtCreate);
                    ps.setLong(3, maxId);

                }
                ResultSet rs = ps.executeQuery();
                maxGmtCreate = null;
                maxId = -1;
                while (rs.next()) {
                    System.out.println((++index) + " " + rs.getInt("id") + " " + rs.getString("gmt_Create"));
                    maxGmtCreate = rs.getObject("gmt_create");
                    maxId = rs.getLong("id");
                }
                if (maxId == -1) {
                    break;
                }
            } finally {
                conn.close();
            }

        }

    }
}