分页无处不在,查看邮件、刷朋友圈、浏览新闻等,我们无不是在一页一页地获取信息。对于服务端来说,针对不同场景,分页有不同的设计方案,本文主要以MySQL为例(数据样例见文末)。

页码分页

最简单的是通过页码来分页:

-- 请求地址类似于https://localhost/user?page=1&limit=10
SELECT * FROM `user` LIMIT 0,10;
SELECT COUNT(*) FROM user;

不要嗤之以鼻,如果只是系统初期的小小的后台管理系统,这样的分页已经足够了,没必要整得花里胡哨的,够用就好。
随着业务增长,系统越来越大了(大部分系统没有这样的福气),上面的分页方法逐渐显得有点捉襟见肘了。过早的优化是万恶之源,因此咱们一开始只是简单粗暴地分页也无可厚非,现在我们要逢山开路遇水架桥。

假设我们的用户量单表去到了1000万(这里不考虑分库分表的情况),瓶颈出现了:

mysql> SELECT COUNT(*) FROM user;
+----------+
| count(*) |
+----------+
| 10000000 |
+----------+
1 row in set (3.72 sec)

这个查询需要好几秒,因为user表用的是InnoDB存储引擎,它需要检查所有记录才能得出总行数,这是为了支持MVCC而付出的代价。那用索引字段代替星号会不会有性能提升?很遗憾,几乎没有。其实使用星号MySQL会自动帮你优化选择最小的索引。那怎么办?第一,你可以选用MyIASM来避免这个问题(它是直接从元数据中读取总数),如果你可以放弃使用事务特性。第二,使用缓存,弊端是当查询条件复杂的时候,维护缓存也是一个麻烦,而且构建缓存时依然很慢。第三,无解,那干脆不用select count(*)了,那用什么呢?这个下面会谈到。

游标分页

我们还发现有些用户喜欢从最后一页倒回来看,弄出类似下面这样的语句:

-- 请求地址类似于https://localhost/user?page=999999&limit=10
mysql> SELECT * FROM `user` LIMIT 9999990,10;
10 rows in set (2.87 sec)

即使查询条件走了索引,而且也只是查了仅仅10条数据,但还是卡得要死,为什么呢?
用explain查看一下执行计划,你会发现这条语句几乎是全表扫描!稍微优化一下:

SELECT * FROM `user` WHERE id >= 9999990 LIMIT 10;
-- 10 rows in set (0.00 sec)

哇,几乎瞬间结果就出来了。你可以脑补,它在一颗B-Tree上,只需走几个分叉,就找到了目标,而不是无脑地扫描。我们可以把这个分隔条件值称作游标(cursor),例如上面的9999990。现在可以不用页码来分页了,而是直接使用cursor来分页,因此也不需要提供总页数这个信息。客户端可以根据游标查询下一页或上一页的数据,游标为空时默认是第一页,每一页数据都会返回下一页或上一页的游标,这样也就可以一页地翻上翻下,直至没有数据返回。Yeah,可以跟前面提到的select count(*)说拜拜了。

可以把这个想象为一个双向列表,下拉时告诉服务端当前列表最后一条数据的标识,上拉时告诉服务端最前一条数据的标识。注意这个cursor不一定就是数字,它应该是一个payload,可以包含很多有用的信息,例如cursor=abc.123.855.bbb。前端不需要了解cursor值是什么东西,他只知道把cursor传给服务端就能拿到下一页,然后又获得一个新的cursor。后端可以随意修改这个cursor的实现方式,只要保证排序向后兼容,前端是无感知的。

使用id作为游标,确实好用,有时候,如果你需要对created_at进行排序,不必为它创建索引,直接使用自增id排序即可,如果你不想用自增id,也可以使用Twitter所创的snowflake,它直接把时间信息嵌入到一个64位的整型当中。
但还有一个问题,如果是根据用户性别排序,即出现重复数据时这个游标应该怎么设计?给性别字段gender创建索引,它的基数太小(只有3),得不偿失。但我们可以增加一个基数大的字段gender_order,专门用于排序,这个字段的排序结果就是gender字段的排序结果。因此只要满足:

gender_order=gender*(1<<62) +id

这时候就可以拿gender_order当做游标了,一般来说取int64的高位保存原值,低位保存一个唯一值例如id,也可以取少一些的整数例如1000亿,当然要保证不会溢出哦。上面公式的id可以是当前用户的id,也可以是使用其它办法生成的唯一id,公式还可以是其它的组合形式,保证gender_order是唯一值即可。这里只是提供了这种思路,需求千变万化,但万变不离其宗。如果你还想了解更为复杂的游标设计,可以参考Redis是如何通过游标来遍历非常大的集合的。

另外建议,不要在原表做分页操作,要把分页独立为一个组件或接口,方便将来扩展。例如上面的gender排序可以单独设计一个索引表添加user_id,gender_order字段来实现,保持原user表的清晰简洁。你甚至可以把gender_order这个索引保存在Redis的有序集合中,以获得更快的速度。我不关心你是如何实现分页的,你只需给我那一页的id列表即可。你也许几经周折走遍千山万水才搞出下一页的id列表,但最终数据是通过一条简单的查询读出来:

-- 初始化索引
USER test;
CREATE TABLE IF NOT EXISTS `user_gender_order` (
  `id` bigint NOT NULL AUTO_INCREMENT COMMENT '唯一标识',
  `user_id` bigint NOT NULL COMMENT '用户ID',
  `gender_idx` bigint NOT NULL COMMENT '性别索引',
  PRIMARY KEY `pk_id` (`id`),
  UNIQUE `uk_user_id` (`user_id`),
  UNIQUE `uk_gender_idx` (`gender_idx`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci COMMENT='用户性别索引';
INSERT INTO user_gender_order(`user_id`,`gender_idx`) SELECT `id`,`gender`*100000000000 + `id` FROM `user`;

-- 分页查找
SELECT * FROM `user_gender_order` WHERE `gender_idx` > 100005000000 ORDER BY `gender_idx` ASC LIMIT 10;
SELECT * FROM `user` WHERE `id` IN (...);

总的来说,游标分页有以下几个好处:

  1. 性能极好,用户体验好;
  2. 翻页不会看到重复的数据或缺漏新增的数据,例如在翻页过程中新增了数据导致数据位移;
  3. 容易扩展。

分页性能的问题解决了,下面再来聊聊一些有特色的分页设计。

随机分页

假如有一些文章,我们希望每一篇文章都有同等的机会被用户看到,用户分页查看时又不会看到重复的内容。由于我们了解到大部分用户都只会看前面几页,后面的很大可能不会被翻到,因此不能使用通常的方式分页,否则排在后面的文章容易被冷落。为了达成这个目的只能使用随机的方式进行分页,即每个用户都会看到一份随机的文章列表副本。
如果直接用MySQL来实现:

SELECT * FROM `user` ORDER BY RAND(1) LIMIT 10;
-- 10 rows in set (46.56 sec)

把rand(1)中的1替换为用户ID,这样每个用户看到的数据排序都不一样,翻页时又不会重复,在数据量比较小时不失为一个简单粗暴的方案。
但遗憾的是,当数据量比较大时,这个查询的效率非常非常低,实际上MySQL把所有的记录读到一个临时表中,然后创建一个随机索引,可想而知不慢的话,图灵的棺材板都按不住了。
也许没有完美的解决方案,那我们折中一下,把MySQL创建临时表的步骤提前先做了,避免每次查询都重复构建临时表。另外,也不必让每个用户所看到的排序都与众不同,可以让id%10的用户看到的排序是相同的。那就可以创建10个随机索引,每个用户从这10个随机索引中固定选择一个用来排序即可。

USER test;
CREATE TABLE IF NOT EXISTS `user_order_0` (
  `id` bigint NOT NULL AUTO_INCREMENT COMMENT '唯一标识',
  `user_id` bigint NOT NULL COMMENT '用户ID',
  PRIMARY KEY `pk_id` (`id`),
  UNIQUE `uk_user_id` (`user_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci COMMENT='用户排序';

-- 构建索引
mysql> INSERT INTO `user_order_0`(`user_id`) SELECT `id` from `user` ORDER BY RAND(0);
-- INSERT INTO `user_order_1`(`user_id`) SELECT `id` from `user` ORDER BY RAND(1);

-- 新增用户时(假设用户ID=10000010),随机跟一个已存在的的用户交换位置
mysql> SELECT * FROM `user_order_0` WHERE `id` >= ((SELECT MAX(`id`) FROM `user_order_0`) * RAND()) ORDER BY `id` ASC limit 1;
+------+---------+
| id   | user_id |
+------+---------+
| 3627 | 9751955 |
+------+---------+
1 row in set (0.00 sec)
mysql> UPDATE `user_order_0` SET `user_id`=10000010 WHERE `id`=3627;
Query OK, 1 row affected (0.01 sec)
Rows matched: 1  Changed: 1  Warnings: 0
mysql> INSERT INTO `user_order_0`(`user_id`) VALUES(9751955);
Query OK, 1 row affected (0.00 sec)

-- 分页
-- SELECT * FROM `user` WHERE `id` IN (SELECT `id` FROM `user_order_0` ORDER BY `order_idx` ASC where `order_idx` > [cursor] limit 10);
mysql> SELECT `id`,`user_id` FROM `user_order_0`  where `id` > 9000000 ORDER BY `id` ASC limit 10;
+---------+---------+
| id      | user_id |
+---------+---------+
| 9000001 | 2660263 |
| 9000002 | 9922642 |
| 9000003 | 4403574 |
| 9000004 | 4163208 |
| 9000005 | 4422244 |
| 9000006 | 9140096 |
| 9000007 | 6704706 |
| 9000008 | 2019025 |
| 9000009 | 3015331 |
| 9000010 | 3798143 |
+---------+---------+
10 rows in set (0.01 sec)
mysql> SELECT * FROM `user` WHERE `id` IN (2660263,9922642,4403574,4163208,4422244,9140096,6704706,2019025,3015331,3798143);
10 rows in set (0.00 sec)

-- 查看user_order_0占用空间大小
mysql> use information_schema; 
mysql> SELECT `data_length`,`index_length` FROM tables WHERE `table_schema` = 'test' AND `table_name` = 'user_order_0';
+-------------+--------------+
| DATA_LENGTH | INDEX_LENGTH |
+-------------+--------------+
|   361660416 |    317718528 |
+-------------+--------------+
1 row in set (0.02 sec)

不要虚,在时间成本、内存成本、硬盘成本中,硬盘是最廉价的。不要总是绞尽脑汁想出一个石破天惊的技术方案才罢休,我们只需要解决问题即可。

热榜分页

有时候我们需要维护一份数据热榜,例如知乎热榜等。我们知道热榜是在不断变化的,每时每刻都会有新鲜的数据蹭蹭蹭的登上热榜。假设我浏览第一页时停留了5分钟,在这五分钟里,原本最热门的第一条数据因为没什么人点击了导致被挤下去,恰好去到了第二页,这时候我翻到第二页,what?怎么还是第一页的数据?如果是那种不断append的下拉式刷新,就会尴尬地看到重复的数据。
首先热数据都是少数的,因此我们先要限制一下热榜的数据量,例如100条。我们对每次热榜的数据生成时的时间戳作为其版本号。每次用户浏览时都会获得一个版本号,如果他一直往下一页翻,这个版本号不会变。只有他刷新整个列表时(例如下拉刷新),才去重新获取一个最新的版本号。然后定期清理过期的热榜数据即可。

复杂条件分页

有些情况下,分页条件非常复杂,这时使用联合索引(注意最左前缀匹配)和覆盖索引(防止回表)来提升效率,再结合游标分页即可实现。另外对于全文搜索,最好使用支持倒排序或内存型的数据库,例如ElasticSearch、MongoDB等。

缓存分页

如果我们需要缓存分页,我们应该把排序列表和数据内容分开来缓存,而不是把返回结果直接进行缓存。先从缓存(例如Redis)读取某一页数据的id列表,再根据id列表从缓存(例如Memcached)中读取数据内容。
在绝大部分场景,用户都只会查看前面10页左右的内容,因此对于热点数据可适当使用缓存,对冷数据直接查库,冷数据很少会被访问到,直接查库也不会对数据库造成很大压力。

基本上所有的分页都可以使用上面的设计方案,一个或组合多个来实现。

附录

init.sql:

CREATE DATABASE `test` DEFAULT CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci;
CREATE USER 'test_user'@'%' IDENTIFIED BY 'Abc@123456';
GRANT ALL PRIVILEGES ON test.* TO 'test_user'@'%';
FLUSH PRIVILEGES;
USE test;
CREATE TABLE IF NOT EXISTS `user` (
  `id` bigint NOT NULL AUTO_INCREMENT COMMENT '唯一标识',
  `uuid` char(36) NOT NULL COMMENT 'uuid',
  `name` varchar(64) NOT NULL COMMENT '用户名',
  `gender` tinyint NOT NULL DEFAULT 0 COMMENT '性别,0未知,1男,2女',
  `status` tinyint NOT NULL DEFAULT 0 COMMENT '状态,0正常,1禁用',
  `updated_at` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE  CURRENT_TIMESTAMP COMMENT '更新时间',
  `created_at` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
  PRIMARY KEY `pk_id` (`id`),
  UNIQUE `uk_uuid` (`uuid`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci COMMENT='用户';

init.py

from faker import Faker
import random
import pymysql
import uuid
# pip3 install Faker
# pip3 install PyMySQL
batch_count=10000
repeat_count=1000

fake = Faker()
random.seed()

db = pymysql.connect("localhost","test_user","Abc@123456","test" )
cursor = db.cursor()
cursor.execute("SELECT VERSION()")
data = cursor.fetchone()
print ("Database version : %s " % data)

# 批量生成fake数据
cursor.execute("truncate user")
while repeat_count > 0:
    repeat_count=repeat_count-1
    values=[]
    for num in range(0,batch_count):
        values.append('(\'%s\',\'%s\',%d,%d)' % (uuid.uuid4(),fake.name(),random.randint(1,2),0))

    sql="INSERT INTO `user`(`uuid`,`name`,`gender`,`status`) VALUES " + ",".join(values)
    try:
        cursor.execute(sql)
        db.commit()
        print("remaining:%d\n"%repeat_count)
    except Exception as e:
        db.rollback()
        print("Error: unable to insert data")
        print(e)
        break

db.close()

MySQL版本:8.0.22