• Feeds

  • Twitter“鲸鱼”故障技术剖析

    很多人都熟悉Twitter访问故障时候那条白色的鲸鱼。今年新推出的Twitter Engineering Blog讲述了Twitter白鲸技术故障的原因及解决思路。这是到目前为止Twitter公开的最底层的一篇技术资料。
    http://engineering.twitter.com/2010/02/anatomy-of-whale.html

    当Web Server发生503错误后,Twitter配置了一个前端鲸鱼的显示页面。Twitter对鲸鱼页面有监控体系,当每秒超过100个鲸鱼就会引起报警。

    为什么在单位时间内会有大量的”fail whale”呢?Twitter成立了一个小组来专门分析此原因。

    1. 分析背景资料

    “分析性能问题不是一门科学,而是一门艺术”。

    鲸鱼页面实际上是对HTTP 503错误的前端展示,503错误通常是调用后台请求超时产生,为了避免用户长时间等待,Twitter的前端(Tim: 也可能是HTTP反向代理)给请求加了超时,避免用户无限制的等待。超时通常是由于单位时间内访问的用户数过大,也有可能是后台某个服务突然变慢造成。
    由于Twitter网站每个时刻都有海量的数据流过,因此要简单的定位并解决此问题并不容易。

    2. Web page请求分解

    Twitter的页面请求后端分成2个阶段,在Twitter内部称为IO phase及CPU phase。IO phase指通过网络服务获取用户的关注关系及相关的Tweets。第2阶段为CPU phase,指将数据聚合、排序及按用户请求的条件输出。IO及CPU各自在1天内消耗的时间如下。

    从图上看到,latency增大时IO是主要瓶颈。IO对应于Network service,因此可以判断是某个网络服务性能降级造成。

    3. 深度分析

    理想情况是网络服务在应答相同参数的请求消耗时间应该基本相同。但实际情况并非如此,我们大胆假设某一网络服务性能下降厉害,于是我们就从统计分析中去寻找这个服务,我们看到Memcached的统计图表如下

    4. Memcached 竟然是鲸鱼故障的直接原因

    可提高的空间及解决思路

    1. 从上图看,Memcached在 latency高峰的性能比低谷相差一倍,因此最简单的判断是增加硬件即可提高50%的性能。
    2. 另外一种思路就是优化Memcached程序,判断程序热点和瓶颈并进行优化。

    分析

    1. 通过 Google perf-tools project 工具来分析, http://code.google.com/p/google-perftools/ http://github.com/tmm1/perftools.rb
    2. 通过自己些的一段分析代码来监控 http://github.com/eaceaser/ruby-call-graph
    3. 通过上面工具的call graph来分析热点和瓶颈

    最后分析数据Memcached请求分布比例如下

    get         0.003s
    get_multi   0.008s
    add         0.003s
    delete      0.003s
    set         0.003s
    incr        0.003s
    prepend     0.002s
    
    get         71.44%
    get_multi    8.98%
    set          8.69%
    delete       5.26%
    incr         3.71%
    add          1.62%
    prepend      0.30%
    

    结论:从上面数据来看,调用热点和瓶颈主要集中在Get操作

    因此回头取看Twitter页面执行流程代码,找出优化方法见注释。

    get(["User:auth:missionhipster",              # 将昵称转换成uid
    get(["User:15460619",                         # 获取user object(用于检查密码)
    get(["limit:count:login_attempts:...",        # 防止密码字典攻击
    set(["limit:count:login_attempts:...",        # 大部分情况不需要, bug
    set(["limit:timestamp:login_attempts:...",    # 大部分情况不需要, bug
    get(["limit:timestamp:login_attempts:...",
    get(["limit:count:login_attempts:...",        # 重复调用,可记住
    get(["limit:count:login_attempts:...",        # 重复调用
    get(["user:basicauth:...",                    # 防止解密的优化
    get(["limit:count:api:...",                   # 请求数限制
    set(["limit:count:api:...",                   # 设置请求数,大部分情况不需要,为什么?
    set(["limit:timestamp:api:...",               # 大部分情况不需要, bug
    get(["limit:timestamp:api:...",
    get(["limit:count:api:...",                   # 重复调用
    get(["home_timeline:15460619",                # home_timeline业务调用
    get(["favorites_timeline:15460619",           # favorites_timeline业务调用
    get_multi([["Status:fragment:json:74736693",  # multi_get所有tweets内容
    

    上面这段代码将17个请求优化成10个,部分重复调用通过本地cache避免,另外一些没必要的调用直接删除。通过一个简单的优化性能就提高了42%。

    结论

    1. 在前文2010年的技术架构建议中提过Cache已经是Web 2.0系统核心元素。从Twitter的故障案例来看Memcached竟然成为了瓶颈并导致了Twitter服务的不稳定。由于在social应用中cache核心化的设计,“RAM is the new disk”,在cache广泛使用后也变得调用成本增加,需要考虑进行系统的规划减少不必要的调用。避免开发人员在代码中随意使用cache
    2. 如何定位瓶颈,可以借鉴Google perf-tools项目及上面其他分析工具的思路。
    3. Twitter页面执行流程值得参考
    4. 整个故障流程分析图如下

    Dynamo一个缺陷的架构设计(译)

    在云计算的时代,Dynamo可以说是一本实现分布式存储的红宝书,借鉴Dynamo实现的产品如雨后春笋般冒出。前段时间本人曾在Twitter上戏称

    这年头,如果一个号称有“海量数据”的互联网公司,不做一个自己的Dynamo, 出去都不好意思跟人打招呼
    (http://twitter.com/xmpp/status/8023241449)

    另外一方面对于Dynamo设计思想也有不少反对的声音,比如2009/11/1在Hacker News上链接的一篇文章Dynamo: A flawed architecture引起不少争议,最后竟引起Amazon CTO Werner Vogels在Twitter上回应

    Darn, someone figured out that Dynamo is a flawed architecture. Luckily its only use is storing hundreds of millions of shopping carts :-)
    (http://twitter.com/Werner/statuses/5345892061)
    汗,有人发现Dynamo是一个缺陷的架构,幸运的是,我们只用它来存储了成百上亿的购物篮数据。:-)

    以下是这篇批判Dynamo文章大部分中心观点,所翻译的观点并不代表Tim立场。

    –译文开始–

    Dynamo: A flawed architecture

    在发表此文章之前,我也争论过Dynamo是否适合我们的系统。但是我很清楚这篇论文充满缺陷,它将错误的引导了读者让大家相信其设计,它的很多设计前后自相矛盾。下文会详细介绍这些缺陷。

    Dynamo的最终一致性

    首先,最终一致性对开发者意味什么呢?

    1. 写入的数据不能在后续的读操作中获取到。
    2. 写入的数据也有可能在后续的读操作中获取到,但读到后可能下一次又读不到。
    3. 因此对写操作后面的读取没有SLA(Service Level Agreement)保证。

    举例说明,由于Dynamo是一个key value存储,我们假设value中存储的是一个list, 当list写入数据之后另外一个client却未读取到,这时候它需要写入数据的话只能重新构建一个新的list,添加要存的值并将新list存入,这就会导致老的list数据丢失。

    (Update: 论坛上一些人指出,由于Vector Clock机制,数据丢失的场景不可能出现,我同意,不过我再提出几个其他问题。)

    1. Cassandra未用vector clock, 而只用client timestamps也达到了同样效果。
    2. Dynamo依赖合并冲突来解决此问题,一些场合下冲突很难解决。比如从list中错误的截取操作。(if deletion from the list is a valid operation – then how would one reconcile after mistaken truncation?)
    3. 另外一个场景,读取到脏数据后可能会影响后续的写入。(a stale read may end up affecting writes to other keys)

    一般的常识是读取脏数据是需要避免的,但是Dynamo中无任何措施来避免读取脏数据以及避免读取脏数据的客户端再次写入,这个在单IDC环境其实是完全可以避免的。

    Quorum一致性

    (译者注:Quorum是Dynamo的一个核心特性,主要思想是 写最小节点数W + 读最小节点数R > 所有节点数N)
    Dynamo开始就提到系统按最终一致性设计,但是在4.5中却提出用Quorum的方法来实现一定程度的一致性,意思是如果R+W>N, 则读操作就具备(强)一致性了。明显是误导。由于节点会出现不可用的情况,尤其在跨IDC情况下,任一节点随时都有可能离开quorum组,当它离开再加入的时候,R个节点返回的数据就是不一致的,因为故障节点的数据只具备“最终一致性”,而在当时返回的只能是脏数据。

    这就带来一个明显的问题,为什么要让未同步到最新数据的节点加入组?答案是Dynamo中无任何方法来判断一个节点是否数据同步,也无法判断有哪些数据不同步。因此只能做一个完全数据比较才能判断,Dynamo中用一种叫Merkle Tree的方法来实现,这个当然是一个代价昂贵且不灵活的操作,因为为了不影响Dynamo正常的读写业务,同步需要在后台执行。

    实现强一致性也可以用读取所有节点(R=N)的方式来达到,不过有2个问题。

    1. 一旦有一个节点未同步,读取就会失败。
    2. 读取的代价极高。

    我并不是第一个发现这些问题的人,比如另一知名的Cassandra产品Cassandra-225中就提到用一个中心commit log的方法来解决此问题。

    WAN considerations 跨IDC的问题

    值得指出的是,如果将Dynamo部署到多个机房,节点的断续情况会很容易发生。当一个节点连接不到,Dynamo的”hinted handoff”策略会使用一致性哈希算法将数据放入下一个节点。在多IDC环境下,下一节点通常在另一机房,因此会造成异地数据传输增加。当异地整个IDC都连不上网络分裂情况发生时,数据需要很长时间才能完全恢复。

    Disaster Recovery 灾难恢复

    Dynamo最终一致性及同步的设计对于是节点故障是有价值的,但是却无法估算有多少数据未同步。如果改用常规的commit log方式的话,很容易就能实现故障恢复并且计算未同步的数据量。

    未使用时间一致性(译者:基于timestamp的合并?)在某些场合下很难合并冲突。

    一致性还是可用性 Consistency versus Availability

    一般认为Dynamo选择了CAP理论中的AP,而BigTable选择了CA。不幸的是,Dynamo并没有搞清什么是A(availability)和P(Partition Tolerance)。读者被误导只能在C和P中做一个取舍,这个当然是错的。我们很容易在单IDC实现一致性及高可用性。大部分商业数据库就是如此,HBase/HDFS也是如此。

    很多人误以为即使在单IDC架构中,Dynamo方式比BigTable/GFS架构更合理。但Dynamo的优势其实是在多IDC。

    中心化还是去中心化

    Dynamo中提到

    In the past, centralized control has resulted in outages and the goal is to avoid it as much as possible. This leads to a simpler, more scalable, and more available system.
    过去,中心化设计导致了很多灾难,我们意识到要远离中心化。去中心化后,系统会更简洁,更具有可扩展性及高可用性。

    中心化确实会形成瓶颈,但是没有证据说明中心化就低可用性。大部分专业的存储系统通过双机热备的方式都具备高可用性。简单的说,只需要所有中心模块(电源,主板,RAID,交换机等)都按双份的方式来设计,只需要额外增加一点硬件成本,这些系统基本可以达到5个9的可用性。

    值得讽刺的是Dynamo其实在部分情况下还是一个中心化的体系,如交换机故障发生了网络分片,服务器分成2个独立的小网,这时候Dynamo对客户端是不可用的,尽管客户端可以连接上Dynamo。

    更讽刺的是我们看到Dynamo很多一致性问题都是去中心化设计所导致。

    –译文完–

    此文的讨论也非常精彩,对于想深入了解Dynamo的朋友是不可多得的资料。可参看 http://news.ycombinator.com/item?id=915212

    多IDC的数据分布设计(一)

    上个月跟某个朋友谈及多IDC数据同时读写访问的问题(tweet),当时觉得有不少解决方案,但觉得思路还不够清晰。最近看了Google App Engine工程师Ryan Barrett介绍GAE后端数据服务的演讲稿Transactions Across Datacenters(视频),用Ryan的方法来分析这个问题后就豁然开朗。

    按Ryan的方法,多IDC实现有以下几种思路。

    一、Master/slave

    这个是多机房数据访问最常用的方案,一般的需求用此方案即可。因此大家也经常提到“premature optimization is the root of all evil”。
    优点:利用mysql replication即可实现,成熟稳定。
    缺点:写操作存在单点故障,master坏掉之后slave不能写。另外slave的延迟也是个困扰人的小问题。

    二、Multi-master

    Multi-master指一个系统存在多个master, 每个master都具有read-write能力,需根据时间戳或业务逻辑合并版本。比如分布式版本管理系统git可以理解成multi-master模式。具备最终一致性。多版本数据修改可以借鉴Dynamo的vector clock等方法。

    优点:解决了单点故障。
    缺点:不易实现一致性,合并版本的逻辑复杂。

    三、Two-phase commit(2PC)

    Two-phase commit是一个比较简单的一致性算法。由于一致性算法通常用神话(如Paxos的The Part-Time Parliament论文)来比喻容易理解,下面也举个类似神话的例子。

    某班要组织一个同学聚会,前提条件是所有参与者同意则活动举行,任意一人拒绝则活动取消。用2PC算法来执行过程如下

    Phase 1

    Prepare: 组织者(coordinator)打电话给所有参与者(participant) ,同时告知参与者列表。
    Proposal: 提出周六2pm-5pm举办活动。
    Vote: participant需vote结果给coordinator:accept or reject。
    Block: 如果accept, participant锁住周六2pm-5pm的时间,不再接受其他请求。

    Phase 2

    Commit: 如果所有参与者都同意,组织者coodinator通知所有参与者commit, 否则通知abort,participant解除锁定。

    Failure 典型失败情况分析

    Participant failure:
    任一参与者无响应,coordinator直接执行abort
    Coordinator failure:
    Takeover: 如果participant一段时间没收到cooridnator确认(commit/abort),则认为coordinator不在了。这时候可自动成为Coordinator备份(watchdog)
    Query: watchdog根据phase 1接收的participant列表发起query
    Vote: 所有participant回复vote结果给watchdog, accept or reject
    Commit: 如果所有都同意,则commit, 否则abort。

    优点:实现简单。
    缺点:所有参与者需要阻塞(block),throughput低;无容错机制,一节点失败则整个事务失败。

    四、Three-phase commit (3PC)

    Three-phase commit是一个2PC的改进版。2PC有一些很明显的缺点,比如在coordinator做出commit决策并开始发送commit之后,某个participant突然crash,这时候没法abort transaction, 这时候集群内实际上就存在不一致的情况,crash恢复后的节点跟其他节点数据是不同的。因此3PC将2PC的commit的过程1分为2,分成preCommit及commit, 如图。

    (图片来源:http://en.wikipedia.org/wiki/File:Three-phase_commit_diagram.png)

    从图来看,cohorts(participant)收到preCommit之后,如果没收到commit, 默认也执行commit, 即图上的timeout cause commit。

    如果coodinator发送了一半preCommit crash, watchdog接管之后通过query, 如果有任一节点收到commit, 或者全部节点收到preCommit, 则可继续commit, 否则abort。

    优点:允许发生单点故障后继续达成一致。
    缺点:网络分离问题,比如preCommit消息发送后突然两个机房断开,这时候coodinator所在机房会abort, 另外剩余replicas机房会commit。

    五、Paxos

    Google Chubby的作者Mike Burrows说过, “there is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos. 意即“世上只有一种一致性算法,那就是Paxos”,所有其他一致性算法都是Paxos算法的不完整版。相比2PC/3PC, Paxos算法的改进

    • P1a. 每次Paxos实例执行都分配一个编号,编号需要递增,每个replica不接受比当前最大编号小的提案
    • P2. 一旦一个 value v 被replica通过,那么之后任何再批准的 value 必须是 v,即没有拜占庭将军(Byzantine)问题。拿上面请客的比喻来说,就是一个参与者一旦accept周六2pm-5pm的proposal, 就不能改变主意。以后不管谁来问都是accept这个value。
    • 一个proposal只需要多数派同意即可通过。因此比2PC/3PC更灵活,在一个2f+1个节点的集群中,允许有f个节点不可用。

    另外Paxos还有很多约束的细节,特别是Google的chubby从工程实现的角度将Paxos的细节补充得非常完整。比如如何避免Byzantine问题,由于节点的持久存储可能会发生故障,Byzantine问题会导致Paxos算法P2约束失效。

    以上几种方式原理比较如下

    (图片来源:http://snarfed.org/space/transactions_across_datacenters_io.html)

    后文会继续比较实践环境选取何种策略合适。

    (PS: 写完后在Google Reader上发现本文跟王建硕最近发表的《关于两个机房的讨论》文章有点类似,特别是本文一、二方式。不过他的文章偏MySQL的实现,我的重点是一致性算法,大家可以有选择性的阅读。)