• Feeds

  • Archive for March, 2010


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

    在前文《多IDC的数据分布设计(一)》中介绍了多IDC数据一致性的几种实现原理,遗憾的是,目前虽然有不少分布式产品,但几乎都没有开源的产品专门针对IDC来优化。本文从实践的角度分析各种方法优缺点。

    背景资料 Latency差异

    Jeff Dean提到不同数据访问方式latency差异

    Numbers Everyone Should Know
    L1 cache reference                           0.5 ns
    Branch mispredict                            5 ns
    L2 cache reference                           7 ns
    Mutex lock/unlock                           25 ns
    Main memory reference                      100 ns
    Compress 1K bytes with Zippy             3,000 ns
    Send 2K bytes over 1 Gbps network       20,000 ns
    Read 1 MB sequentially from memory     250,000 ns
    Round trip within same datacenter      500,000 ns
    Disk seek                           10,000,000 ns
    Read 1 MB sequentially from disk    20,000,000 ns
    Send packet CA->Netherlands->CA    150,000,000 ns

    这个数据对于我们设计多IDC数据访问策略具有关键的指导作用,我们可以用这个数据来衡量数据架构来如何设计才能满足高并发低延迟的目标。
    这份数据实际上对所有网络应用及分布式应用开发者都具有很大借鉴作用,数据需要根据访问频率尽量放在latency小的地方

    1. 2PC/3PC/Paxos模式

    在上文中提到,2PC/3PC相比Paxos有明显的缺点,因此最好不用于生产环境,这里就不再详述。
    Paxos选择了CAP理论中的”Consistency, Partition”, 需要牺牲availability。它可以在多个IDC之间实现强一致性复制。

    Paxos缺点

    • IDC之间需要高速稳定网络
    • 一个2f+1个节点的网络中,需要f+1个节点完成事务才能成功。
    • Throughput低,不适合高请求量的场合。所以大部分分布式存储产品并不直接使用Paxos算法来同步数据。

    2. Dynamo模式

    Dynamo论文中并未专门描述Dynamo算法是否适合多IDC场景,只有少量文字提到

    In essence, the preference list of a key is constructed such that the storage nodes are spread across multiple data centers. These datacenters are connected through high speed network links. This scheme of replicating across multiple datacenters allows us to handle entire data center failures without a data outage.

    从上文看到,前提条件是“high speed network links” 可能对国内的情况不太适用。假如IDC之间网络不稳定,那会发生哪些情况呢?

    Quorum 算法中,如果要考虑高可用性,则数据需要分布在多个机房。双机房如NRW=322由于单机房故障后可能会发生3个点中2个点都在故障机房,导致出现数据不 可用的情况,所以合适的部署是NRW=533,需要3个机房。大部分请求需要2个机房节点返回才能成功,考虑到多IDC的带宽及latency,性能自然会很差。

    Quorum算法在读写的时候都要从quorum中选取一个coordinator,算法如下

    A node handling a read or write operation is known as the
    coordinator. Typically, this is the first among the top N nodes in
    the preference list. If the requests are received through a load
    balancer, requests to access a key may be routed to any random
    node in the ring. In this scenario, the node that receives the
    request will not coordinate it if the node is not in the top N of the
    requested key’s preference list. Instead, that node will forward the
    request to the first among the top N nodes in the preference list.

    如果严格按照Dynamo协议,coodinator一定要在N中第一个节点,那在3个机房中将有2/3的请求需要forward到异地机房的 coordinator执行,导致latency增大。如果对coodinator选择做优化,让client选取preference list中前N个节点中在本地机房的一个节点作为coordinator,这样会一定程度降低latency,但是会存在相同的key选择不同节点作为 coordinator的概率增大,导致数据conflict的概率增大。

    同时在多机房模式下,Failure detection容易产生混乱。Dynamo并没有使用一致性的failure view来判断节点失效。而是由每个节点独自判断。

    Failure detection in Dynamo is used to avoid attempts to
    communicate with unreachable peers during get() and put()
    operations and when transferring partitions and hinted replicas.
    For the purpose of avoiding failed attempts at communication, a
    purely local notion of failure detection is entirely sufficient: node
    A may consider node B failed if node B does not respond to node
    A’s messages (even if B is responsive to node C’s messages).

    而最近非常流行的Cassandra基本上可以看作是开源的Dynamo clone, 它在Facebook Inbox Search项目中部署在150台节点上,并且分布在美国东西海岸的数据中心。

    The system(Facebook Inbox Search) currently stores about 50+TB of data on a 150 node cluster, which is spread out between east and west coast data centers.

    虽然在它的JIRA中有一个提案 CASSANDRA-492 是讲”Data Center Quorum”,但是整体看来Cassandra并没有特别的针对对IDC的优化,它的paper[5]中提到

    Data center failures happen due to power outages, cooling
    failures, network failures, and natural disasters. Cassandra
    is configured such that each row is replicated across multiple
    data centers. In essence, the preference list of a key is con-
    structed such that the storage nodes are spread across mul-
    tiple datacenters. These datacenters are connected through
    high speed network links. This scheme of replicating across
    multiple datacenters allows us to handle entire data center
    failures without any outage.

    跟Dynamo中的描述几乎是相同的。

    3. PNUTS模式

    PNUTS模式是目前最看好的多IDC数据同步方式。它的算法大部分是为多IDC设计。

    PNUTS主要为Web应用设计,而不是离线数据分析(相比于Hadoop/HBase)。

    • Yahoo!的数据基本都是用户相关数据,典型的以用户的username为key的key value数据。
    • 统计数据访问的特征发现85%的用户修改数据经常来源自相同的IDC。

    根据以上的数据特征,Yahoo!的PNUTS实现算法是

    • 记录级别的master, 每一条记录选择一个IDC作为master,所有修改都需要通过master进行。即使同一个表(tablet)中不同的记录master不同。
    • master上的数据通过Yahoo! Message Broker(YMB)异步消息将数据复制到其他IDC。
    • master选择具有灵活的策略,可以根据最新修改的来源动态变更master IDC, 比如一个IDC收到用户修改请求,但是master不在本地需要转发到远程master修改,当远程修改超过3次则将本地的IDC设成master。
    • 每条记录每次修改都有一个版本号(per-record timeline consisitency),master及YMB可以保证复制时候的顺序。

    Yahoo!的PNUTS实际可理解为master-master模式。
    一致性:由于记录都需通过master修改,master再复制到其他IDC, 因此可达到所有IDC数据具有最终一致性。
    可用性

    • 由于所有IDC都有每条记录的本地数据,应用可以根据策略返回本地cache或最新版本。
    • 本地修改只要commit到YMB即可认为修改成功。
    • 任一IDC发生故障不影响访问。

    论文中提到的其他优点

    hosted, notifications, flexible schemas, ordered records, secondary indexes, lowish latency, strong consistency on a single record, scalability, high write rates, reliability, and range queries over a small set of records.

    总之,PNUTS可以很好的适合geographic replication模式。

    • 记录publish到本地YMB则认为成功,免除Dynamo方式需要等待多个Data Center返回的latency。
    • 如果发生master在异地则需要将请求forward到异地,但是由于存在master转移的策略,需要forward的情况比较少。

    极端情况,当record的master不可用时候,实现上似乎有些可疑之处,读者可自行思考。

    Under normal operation, if the master copy of a record fails, our system has protocols to fail over to another replica. However, if there are major outages, e.g. the entire region that had the master copy for a record becomes unreachable, updates cannot continue at another replica without potentially violating record-timeline consistency. We will allow applications to indicate, per-table, whether they want updates to continue in the presence of major outages, potentially branching the record timeline. If so, we will provide automatic conflict resolution and notifications thereof. The application will also be able to choose from several conflict resolution policies: e.g., discarding one branch, or merging updates from branches, etc.

    初步结论

    低带宽网络
    PNUTS record-level mastering模式最佳。
    高带宽低延迟网络
    (1Gbps, Latency < 50ms)
    1. 用Dynamo Quorum, vector clock算法实现最终一致性
    2. 用Paxos实现强一致性

    后记

    本文从开始准备到发布时间较长,由于在多IDC数据访问方面目前业界并无统一的成熟方案,相关资料和文献也相对较少,而且对这方面有兴趣且有相应环境的人不多,短时间要提出自己成熟独立的见解也具有一定难度,本文仅包含一些不成熟的想法的整理,由于自己对文中的观点深度也不是满意,所以一直没有最终完稿发布。但考虑到最近工作较忙,暂时没有精力继续深入研究,所以希望公开文章抛砖引玉,同时也欢迎对这方面课题有兴趣者进一步交流探讨。

    Resource

    1. Ryan Barrett, Transactions Across Datacenters
    2. Jeff Dean, Designs, Lessons and Advice from Building Large Distributed Systems (PDF)
    3. PNUTS: Yahoo!’s Hosted Data Serving Platform (PDF)
    4. Thoughts on Yahoo’s PNUTS distributed database
    5. Cassandra – A Decentralized Structured Storage System (PDF)
    6. Yahoo!的分布式数据平台PNUTS简介及感悟

    FarmVille(美版开心农场)谈架构:所有模块都是一个可降级的服务


    在2009年Facebook Developer Garage Shanghai活动上,Five Minutes程延辉 介绍开心农场架构,让大家了解了SNS game的一些挑战和设计模式。

    由于农场游戏风靡全球,最近highscalability.com网站采访了美版开心农场FarmVille的Luke Rajlich,他介绍了FarmVille的部分架构资料(1)。

    所有模块都是一个可降级的服务

    For any web application, high latency kills your app and highly variable latency eventually kills your app.

    由于大型的网络应用需要依赖各种底层及内部服务,但是服务调用的高延迟是各种应用的最大问题,在竞争激烈的SNS app领域更是如此。解决此问题的方法是将所有的模块设计成一种可降级的服务,包括Memcache, Database, REST API等。将所有可能会发生大延迟的服务进行隔离。这可以通过控制调用超时时间来控制,另外还可以通过应用中的一些开关来关闭某些某些功能避免服务降级造成的影响。

    上面这点我也有一些教训,曾碰到过由于依赖的一些模块阻塞造成服务不稳定的现象。

    1. 某Socket Server使用了ThreadPool来处理所有核心业务。
    2. 不少业务需要访问内网的一个远程的User Service(RPC)来获取用户信息。
    3. User Service需要访问数据库。
    4. 数据库有时候会变慢,一些大查询需要10秒以上才能完成。

    结果4造成3很多调用很久才能执行完,3造成2的RPC调用阻塞,2造成1的ThreadPool堵塞,ThreadPool不断有新任务加入,但是老的任务迟迟不能完成。因此对于最终用户的表现是很多请求没有响应。部分用户认为是网络原因会手工重复提交请求,这样会造成状况并进一步恶化。上面的问题根本是没有意识到远程服务可能会超时或失败,把远程服务RPC调用当成一个本地调用来执行。

    解决思路一:RPC增加Timeout
    解决思路二:将RPC改成异步调用。

    另一分布式大牛James Hamilton谈到(2)上面这种做法就是他论文Designing and Deploying Internet-Scale Services中的graceful degradation mode(优雅降级)。

    FarmVille其他数据

    • FarmVille基于LAMP架构,运行在EC2上。
    • 读写比例是3:1。
    • 使用开源工具来做运维监控,如nagios报警,munin监控,puppet配置。另外还开发了很多内部的程序来监控Facebook DB, Memcache等。
    • 到Facebook接口的流量峰值达到3Gb/s,同时内部的cache还承担了1.5Gb/s。
    • 另外可动态调整到Facebook与Cache之间的流量,Facebook接口变慢时,可以利用cache数据直接返回,终极目的是不管发生了那个环节的故障,能够让用户继续游戏。

    小结

    尽管FarmVille公布了上面一些技术资料,凭借上面这些资料无法全部了解FarmVille的架构。但是所有模块都是一个可降级服务的概念值得设计大规模应用的同行参考。

    Resource

    1. How FarmVille Scales to Harvest 75 Million Players a Month
    2. Scaling FarmVille

    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. 整个故障流程分析图如下

    12