• Feeds

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

    本文讨论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方式,不过此方法缺点是翻页时必须连续,不能跳页。

    2010年的技术架构建议

    在 2009年最后一天,根据自己小小的视角提出一些技术建议,供同行参考。

    编程语言

    首先要能跳出语言之争及语言偏见,架构师需要在中立的角度选择最合适团队的语言,避免在技术决策中加入过多个人喜好。在系统语言层面,主要可关注以下几种
    Erlang, 会继续在小圈子内流行,业界应用Erlang技术最大的障碍不是Erlang技术本身,而在于缺乏这方面专业人才。
    Scala, 和Erlang不同,Scala有成熟JVM及丰富的周边library,在异构系统中集成也很容易,新项目使用Scala风险很小,所以Scala在新语言中应该有较大的提升优势。
    Go, 由于刚开始推出,不适合正式项目使用,2010年会稳步上升,可适当关注。
    其他语言基本保持现状。

    架构

    LAMP中的Linux, Apache, MySQL会受到云计算中的App Engine模式的冲击,因为App Engine在分布式处理,可扩展性,稳定性方面都有很大的优势。 在App Engine模式中,MySQL作用会降低,退化成一种存储服务。而且App Engine的存储服务含义会更广泛,传统架构中的MySQL, Memcached, 及key value store在App Engine框架下都会以底层的服务方式提供。存储不再是软件,而是一种可靠服务,因此也会带来分布式存储相关技术的繁荣。

    Web 2.0的设计中,Cache会成为一个中心元素。传统的web应用cache只是一个可选的锦上添花层,即使去掉,PHP + MySQL这种模式也可正常运行。但随着未来应用social化及realtime的趋势,从facebook及twitter的设计来看,cache已经从可选层成为核心层。cache设计的好坏直接决定架构的成败。

    由于web发展的趋势会使应用更realtime化,体现到技术层面是HTML5(websockets)及类似技术具有更高的价值。但由于阻碍生产力的IE存在,HTML5无法一步到位。建议关注能解决HTML5及旧ajax自适应的框架。

    网络模型方面,由于多核的硬件环境,轻量级的进程模型值得采用。如传统的C++ boost的asio, 各公司自己实现的coroutine, Erlang的process, go的goroutines, Java/Scala的Netty/Mina框架等。但C++框架的代码优雅性可维护性欠佳,性能也没有突出的优势,可关注后面几种方案。

    分布式方面,Dynamo及Chubby的思想会逐渐在国内的项目等到更广泛的应用,架构师会逐步丢弃双写,双机心跳等山寨式的容错设计思想,可靠的分布式设计思想会更普及。

    存储

    2009是key value/nosql产品百花齐放的年代。到2010年,它们之中优秀的会脱颖而出逐步主流化,主流化的产品周边的工具会更丰富,运维相关经验也会更成熟。目前阻碍很多key value产品推广很大一个障碍是运维的顾虑,而不是它们本身的性能。究竟会是Memcachedb/Tokyo Cabinet/Redis这样的小巧软件走向主流,还是Cassandra这样的巨无霸更受欢迎,我们拭目以待。

    Twitter API最近的一些飞跃

    Twitter的平台总监Ryan Sarver在最近一封给开发者公开email Platform announcements from LeWeb提到,打算将API用户请求限制扩大10倍,由目前的150次/小时扩大到1,500次/小时(但同时将搜索范围缩短到7天)。

    *Auth announcements*
    With the recent launches of Retweet, Lists and Geotagging we have seen
    applications struggle to provide the experience they want for their users
    within the 150 req/hr limit. We are excited to open the skies up a bit and
    provide some more room for developers to work within. Starting in a few
    weeks all OAuth requests to api.twitter.com/1/ will be able to take
    advantage of a 10x rate limit increase. Basic Whitelisting still exists and
    is unchanged. We look forward to what this means in terms of the increased
    richness around the user experience in Twitter apps.

    注意文中的限制是OAuth客户端,为什么只限OAuth客户端?由于OAuth客户端可控性较强。如果发现app有滥用api嫌疑,可以直接suspend这个app;而另外一种鉴权方式Basic Authentication方式并不强制client传递app id, 服务器判断app abuse较困难。

    在我的理解,microblog的最大的特性应该是realtime,(另外一特性应是social graph), 即使Twitter扩大rate limit, REST方式的HTTP协议终究没法实现realtime,如果所有的客户端都1分钟请求25次(1,500/60=25),twitter服务器稳定性一向声誉不佳,增大后能否经住考验也是一个疑问。

    如果要实现真正的realtime, 目前有http callback或者XMPP等方案。callback由于客户端通常在防火墙内并不可行。XMPP由于协议栈庞大,服务端及客户端编写都比较繁琐,而且XMPP是为IM协议设计,所以并不十分适合twitter api。

    另外Twitter在邮件中还提到,打算将所有最新更新feed的数据流(Twitter称为Firehose)向所有人开放。

    *Firehose for everyone*
    Finally, the announcement that has garnered the most coverage and
    excitement. As I stated in the session at LeWeb we are committed to
    providing a framework for any company big or small, rich or poor to do a
    deal with us to get access to the Firehose in the same way we did deals with
    Google and Microsoft. We want everyone to have the opportunity — terms will
    vary based on a number of variables but we want a two-person startup in a
    garage to have the same opportunity to build great things with the full feed
    that someone with a billion dollar market cap does. There are still a lot of
    details to be fleshed out and communicated, but this a top priority for us
    and we look forward to what types of companies and products get built on top
    of this unique and rich stream.

    Firehose可以理解成所有Twitter最近更新的水龙头,目前只对 Microsoft, Google等少量公司开放。Twitter表示以后即使”a two-person startup in a garage”这样的公司也可以获取firehose访问权限, “We want everyone to have the opportunity”。相信不少公司将会为这一特性而激动甚至疯狂。firehose开放意味为第三方提供了无限的创意空间,另外它也会对Twitter已有的服务search, geotag等业务构成威胁,走出这一步需要很大的勇气。

    以上文字基本已在新浪微博发表过,整理后就成了一篇blog, 欢迎在新浪微博关注我,点这里进入 http://t.sina.com.cn/timyang