用Twitter的cursor方式进行Web数据分页

标签: Web mysql performance twitter | 发表时间:2010-01-19 22:16 | 作者:Tim yuaz
出处:http://timyang.net

本文讨论Web应用中实现数据分页功能,不同的技术实现方式的性能方区别。

上图功能的技术实现方法拿MySQL来举例就是

select * from msgs where thread_id = ? limit page * count, count

不过在看Twitter API的时候,我们却发现不少接口使用cursor的方法,而不用page, count这样直观的形式,如 followers ids 接口

URL:

http://twitter.com/followers/ids.format

Returns an array of numeric IDs for every user following the specified user.

Parameters:
* cursor. Required. Breaks the results into pages. Provide a value of -1 to begin paging. Provide values as returned to in the response body’s next_cursor and previous_cursor attributes to page back and forth in the list.
o Example: http://twitter.com/followers/ids/barackobama.xml?cursor=-1
o Example: http://twitter.com/followers/ids/barackobama.xml?cursor=-1300794057949944903

http://twitter.com/followers/ids.format

从上面描述可以看到,http://twitter.com/followers/ids.xml 这个调用需要传cursor参数来进行分页,而不是传统的 url?page=n&count=n的形式。这样做有什么优点呢?是否让每个cursor保持一个当时数据集的镜像?防止由于结果集实时改变而产生查询结果有重复内容?
在Google Groups这篇Cursor Expiration讨论中Twitter的架构师John Kalucki提到

A cursor is an opaque deletion-tolerant index into a Btree keyed by source
userid and modification time. It brings you to a point in time in the
reverse chron sorted list. So, since you can’t change the past, other than
erasing it, it’s effectively stable. (Modifications bubble to the top.) But
you have to deal with additions at the list head and also block shrinkage
due to deletions, so your blocks begin to overlap quite a bit as the data
ages. (If you cache cursors and read much later, you’ll see the first few
rows of cursor[n+1]’s block as duplicates of the last rows of cursor[n]’s
block. The intersection cardinality is equal to the number of deletions in
cursor[n]’s block). Still, there may be value in caching these cursors and
then heuristically rebalancing them when the overlap proportion crosses some
threshold.

在另外一篇new cursor-based pagination not multithread-friendly中John又提到

The page based approach does not scale with large sets. We can no
longer support this kind of API without throwing a painful number of
503s.

Working with row-counts forces the data store to recount rows in an O
(n^2) manner. Cursors avoid this issue by allowing practically
constant time access to the next block. The cost becomes O(n/
block_size) which, yes, is O(n), but a graceful one given n < 10^7 and
a block_size of 5000. The cursor approach provides a more complete and
consistent result set.

Proportionally, very few users require multiple page fetches with a
page size of 5,000.

Also, scraping the social graph repeatedly at high speed is could
often be considered a low-value, borderline abusive use of the social
graph API.

通过这两段文字我们已经很清楚了,对于大结果集的数据,使用cursor方式的目的主要是为了极大地提高性能。还是拿MySQL为例说明,比如翻页到100,000条时,不用cursor,对应的SQL为

select * from msgs limit 100000, 100

在一个百万记录的表上,第一次执行这条SQL需要5秒以上。
假定我们使用表的主键的值作为cursor_id, 使用cursor分页方式对应的SQL可以优化为

select * from msgs where id > cursor_id limit 100;

同样的表中,通常只需要100ms以下, 效率会提高几十倍。MySQL limit性能差别也可参看我3年前写的一篇不成熟的文章 MySQL LIMIT 的性能问题

结论

建议Web应用中大数据集翻页可以采用这种cursor方式,不过此方法缺点是翻页时必须连续,不能跳页。

Similar Posts:

相关 [twitter cursor web] 推荐:

用Twitter的cursor方式进行Web数据分页

- yuaz - Tim[后端技术]
本文讨论Web应用中实现数据分页功能,不同的技术实现方式的性能方区别. 上图功能的技术实现方法拿MySQL来举例就是. 不过在看Twitter API的时候,我们却发现不少接口使用cursor的方法,而不用page, count这样直观的形式,如 followers ids 接口. Provide values as returned to in the response body’s next_cursor and previous_cursor attributes to page back and forth in the list..

鼠标指针手写笔:Big Big Cursor

- weawea - 爱…稀奇~{新鲜:科技:创意:有趣}
虽然从苹果iPhone开始的全触摸式操作风行还没有几年,但是鼠标就已经显露出颓势了,以至于就连小弟这种非iPhone用户,面对笔记本的时候也忍不住会想用手指在屏幕上划拉……. ——看上去,我们似乎可以开始悼念鼠标了,比如说用这款鼠标指针手写笔(Big Big Cursor):. 针对iPhone、iPad、安卓等全触摸操作环境设计,采用了超级经典的鼠标指针图案——我们是不能指望在平板上出现这些手势了,但是手里拿着一个放大版的鼠标指针,然后放肆地在娇嫩的屏幕上戳啊戳的,那种视觉效果还挺震撼的,哈哈.

向Web开发人员推荐12款优秀的 Twitter Bootstrap 组件和工具

- - 博客园_梦想天空
  Bootstrap 是基于 HTML,CSS 和 JavaScript 的简洁灵活的流行前端框架及交互组件集,由微博的先驱 Twitter 在2011年8月开源的整套前端解决解决方案. Bootstrap 有非常完备和详尽的开发文档,. Web 开发人员能够轻松搭建出清爽风格的界面以及实现良好的交互效果.

Bootstrap: Webアプリケーションのための高度なCSSフロントエンドを手早く作れるツールをTwitterがリリース

- 三十不归 - TechCrunch Japan
Twitterが今日(米国時間8/19)、Bootstrapをリリースした. CSSを使うWebアプリケーションを作るためのツールキットで、CSSの文字指定、フォーム、ボタン、テーブル、グリッド、ナビゲーション、アラートなどなどを使ってアプリケーションのフロントエンドを作る. Bootstrapの入手は、GitHubのここで.

Twitter 中文版

- 幻幽 or A書 - Gea-Suan Lin&#39;s BLOG
前幾天 Twitter 推出了中文版 (包括繁體與簡體):「Five new languages」. 對岸的市場可能還是進不去,但在台灣會加速 Plurk 的死亡… 從 Google+ 的出現以後就愈來愈明顯了,現在 Microblogging 的大魔頭再加入戰局,應該會更快….

Twitter和Facebook合作

- Woooon - cnBeta.COM
很重磅的新闻,两大社交网络巨头开始有合作了. Twitter 今天在用户的个人档案页面添加「Post Tweets to Facebook」按钮,让用户快速将自己的 Tweets 同步到 Facebook 状态中去.

twitter-mysql改进点

- - CSDN博客推荐文章
目前最新的twitter-mysql版本基于mysql5.5.22,以下总结了一些比较明显的改进点,大部分已经亲自证实,其他一些诸如修复的比较次要的问题(例如编译问题)这里暂不列出,可以详细参阅 https://github.com/twitter/mysql/wiki/Change-History .

Web未死

- Sinan - GeekPark 捕风捉影
App的极限已经浮现,而Web则是突破此极限,推动下一个数字时代革命的起点. 距离美国《连线》杂志发表《Web已死,互联网永生》这篇文章还不到一年的时间,业界为Web平反的声音渐起. 2010年1月,苹果发布iPad,紧随其后在6月又发布了iPhone4. 没有人质疑过苹果的iTunes+App的商业模式,App可谓如日中天.

web的演变

- 酿泉 - 前端观察
这是一个基于GAE的项目,有mgmt design、GOOD、Hyperakt和Vizzuality开发,也有Google chrome团队的参与,记录了浏览器与互联网技术的演变. 不多介绍,直接去看看吧:Evolution Of Web. 值得一提的是,这个项目的代码很不错,值得学习一下.