大数据翻页的难点和技巧

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
云数据库 RDS MySQL,高可用系列 2核4GB
简介:

screenshot

今天要讨论一个传统的问题,问题本身比较简单,就是针对大数据,如何优化方案做到性能与成本的平衡。我们经常会遇到一种Key-list类型数据, 如一个用户的好友关系 {“uid”:{1,2,3,4,5}},表示uid包含有5个好友;一条微博下面的评论id列表{“weibo_id”: {comment_id1, comment_id2……}},一个用户发表的微博id列表等。

在list长度较少时候,我们可以直接的使用数据库的翻页功能,如

SELECT * FROM LIST_TABLE LIMIT offset, row_count;

根据经验,在大部分场景下,单个业务的list数据长度99%在1000条以下,在数据规模较小时候,上面的方法非常适合。但剩下的1%的数据可能多达100万条,在数据规模较大的时候,当访问offset较大的数据,上述方法非常低效(可参看Why does MYSQL higher LIMIT offset slow the query down?),但在实现方案的时候不能忽视这些超大数据集的问题,因此要实现一个适合各种变长list的翻页方案,考虑到数据的长尾问题,并没有简单高效的方案。这也体现了常说的80%+的时间在优化20%-的功能。

List数据访问模型常见的有两种方式

1 . 扶梯方式

扶梯方式在导航上通常只提供上一页/下一页这两种模式,部分产品甚至不提供上一页功能,只提供一种“更多/more”的方式,也有下拉自动加载更多的方式,在技术上都可以归纳成扶梯方式。

screenshot
(图:blogspot的导航条)
screenshot

(图:很多瀑布流式的产品只提供一个more的导航条)

扶梯方式在技术实现上比较简单及高效,根据当前页最后一条的偏移往后获取一页即可,在MySQL可使用以下方法实现。

SELECT * FROM LIST_TABLE WHERE id > offset_id LIMIT n;

由于where条件中指定了位置,因此算法复杂度是O(log n)

2. 电梯方式

另外一种数据获取方式在产品上体现成精确的翻页方式,如1,2,3……n,同时在导航上也可以由用户输入直达n页。国内大部分产品经理对电梯方式有特殊的喜好,如图
screenshot

但电梯方式在技术实现上相对成本较高,当使用以下SQL时

SELECT * FROM LIST_TABLE LIMIT offset, row_count;

我们可以使用MySQL explain来分析,从下文可以看到,当offset=10000时候,实际上MySQL也扫描了10000行记录。

screenshot

为什么会这样?在MySQL中,索引通常是b-tree方式(但存储引擎如InnoDB实际是b+tree),如图

screenshot

从图中可以看到,使用电梯方式时候,当用户指定翻到第n页时候,并没有直接方法寻址到该位置,而是需要从第一楼逐个count,scan到 countpage时候,获取数据才真正开始,所以导致效率不高。对应的算法复杂度是O(n),n指offset,也就是pagecount。

另外Offset并不能有效的缓存,这是由于

1、在数据存在新增及删除的情况下,只要有一条变化,原先的楼层可能会全部发生变化。在一个用户并发访问的场景,频繁变化的场景比较常见。

2、电梯使用比较离散,可能一个20万条的list,用户使用了一次电梯直达100楼之后就走了,这样即使缓存100楼之下全部数据也不能得到有效利用。

以上描述的场景属于单机版本,在数据规模较大时候,互联网系统通常使用分库的方式来保存,实现方法更为复杂。

在面向用户的产品中,数据分片通常会将同一用户的数据存在相同的分区,以便更有效率的获取当前用户的数据。如下图所示

screenshot

(图:数据按用户uid进行hash拆分)

图中的不同年份的数据的格子是逻辑概念,实际上同一用户的数据是保存在一张表中。因此方案在常见的使用场景中存在很大不足,大部分产品用户只访问最 近产生的数据,历史的数据只有极小的概率被访问到,因此同一个区域内部的数据访问是非常不均匀,如图中2014年生成的属于热数据,2012年以前的属于 冷数据,只有极低的概率被访问到。但为了承担红色部分的访问,数据库通常需要高速昂贵的设备如SSD,因此上面方案所有的数据都需要存在SSD设备中,即 使这些数据已经不被访问。

简单的解决方案是按时间远近将数据进行进一步分区,如图。

screenshot

注意在上图中使用时间方式sharding之后,在一个时间分区内,也需要用前一种方案将数据进行sharding,因为一个时间片区通常也无法用一台服务器容纳。

上面的方案较好的解决了具体场景对于key list访问性能及成本的平衡,但是它存在以下不足

  • 数据按时间进行滚动无法全自动,需要较多人为介入或干预
  • 数据时间维度需要根据访问数据及模型进行精巧的设计,如果希望实现一个公用的key-list服务来存储所有业务的数据,这个公用服务可能很难实现
  • 为了实现电梯直达功能,需要增加额外的二级索引,比如2013年某用户总共有多少条记录

由于以上问题,尤其是二级索引的引入,显然它不是理想中的key list实现,后文继续介绍适合大数据翻页key list设计的一些思路及尝试。

文章转载自 开源中国社区 [http://www.oschina.net]

相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps 
相关文章
报错org.springframework.jdbc.UncategorizedSQLException: Error attempting to get column ‘xxx‘ from resu
报错org.springframework.jdbc.UncategorizedSQLException: Error attempting to get column ‘xxx‘ from resu
报错org.springframework.jdbc.UncategorizedSQLException: Error attempting to get column ‘xxx‘ from resu
|
12月前
|
安全 API 数据安全/隐私保护
​发送邮件接口有什么好的平台?5个平台建议及对比
五个顶级邮件发送接口对比:AOKSend适合中小企及开发者,以其高可靠性和易集成著称;SendGrid和Mailgun提供丰富功能与灵活性,适合复杂需求;Amazon SES以高扩展性和低成本吸引大规模发送者;Postmark专注事务邮件,速度快、可靠。各平台在功能、成本、扩展性和用户支持上各有优势,选择时应根据企业具体需求。
|
8月前
|
缓存 算法 关系型数据库
写出好的Join语句,前提你得懂这些!
写出好的Join语句,前提你得懂这些!
133 0
|
10月前
|
安全 Java Spring
Spring Boot 关闭 Actuator ,满足安全工具扫描
Spring Boot 关闭 Actuator ,满足安全工具扫描
915 0
|
Docker 容器
932.【docker】解决目录挂载无效
932.【docker】解决目录挂载无效
254 2
|
12月前
|
安全 前端开发 中间件
中间件在API跨域资源共享(CORS)
【6月更文挑战第16天】
159 7
|
NoSQL Java 数据库
优惠券秒杀案例 - CAS、Redis+Lua脚本解决高并发并行
优惠券秒杀案例 - CAS、Redis+Lua脚本解决高并发并行
509 0
|
Serverless 应用服务中间件 文件存储
Serverless 应用引擎操作报错合集之 出现"Connection reset by peer",是什么导致的
Serverless 应用引擎(SAE)是阿里云提供的Serverless PaaS平台,支持Spring Cloud、Dubbo、HSF等主流微服务框架,简化应用的部署、运维和弹性伸缩。在使用SAE过程中,可能会遇到各种操作报错。以下是一些常见的报错情况及其可能的原因和解决方法。
211 6
|
12月前
|
前端开发 JavaScript CDN
一文搞懂:免费观看全网VIP视频资源
一文搞懂:免费观看全网VIP视频资源
1450 0
|
JSON 负载均衡 Java
SpringCloud Feign 远程调用(史上最详细讲解)
SpringCloud Feign 远程调用(史上最详细讲解)
11889 0
SpringCloud Feign 远程调用(史上最详细讲解)