Home | About | English | RSS

  • Feeds

    • Archive for September, 2009


    Paxos在大型系统中常见的应用场景

    Wednesday, Sep 23rd, 2009 by Tim | 24 Comments
    Filed under: 分布式 | Tags: , ,

    在分布式算法领域，有个非常重要的算法叫Paxos, 它的重要性有多高呢，Google的Chubby [1]中提到

    all working protocols for asynchronous consensus we have so far encountered have Paxos at their core.

    关于Paxos算法的详述在维基百科中有更多介绍，中文版介绍的是choose value的规则[2]，英文版介绍的是Paxos 3 phase commit的流程[3]，中文版不是从英文版翻译而是独立写的，所以非常具有互补性。Paxos算法是由Leslie Lamport提出的，他在Paxos Made Simple[4]中写道

    The Paxos algorithm, when presented in plain English, is very simple.

    当你研究了很长一段时间Paxos算法还是有点迷糊的时候，看到上面这句话可能会有点沮丧。但是公认的它的算法还是比较繁琐的，尤其是要用程序员严谨的思维将所有细节理清的时候，你的脑袋里更是会充满了问号。Leslie Lamport也是用了长达9年的时间来完善这个算法的理论。

    实际上对于一般的开发人员，我们并不需要了解Paxos所有细节及如何实现，只需要知道Paxos是一个分布式选举算法就够了。本文主要介绍一下Paxos常用的应用场合，或许有一天当你的系统增大到一定规模，你知道有这样一个技术，可以帮助你正确及优雅的解决技术架构上一些难题。

    1. database replication, log replication等， 如bdb的数据复制就是使用paxos兼容的算法。Paxos最大的用途就是保持多个节点数据的一致性。

    2. naming service, 如大型系统内部通常存在多个接口服务相互调用。
    1) 通常的实现是将服务的ip/hostname写死在配置中，当service发生故障时候，通过手工更改配置文件或者修改DNS指向的方法来解决。缺点是可维护性差，内部的单元越多，故障率越大。
    2) LVS双机冗余的方式，缺点是所有单元需要双倍的资源投入。
    通过Paxos算法来管理所有的naming服务，则可保证high available分配可用的service给client。象ZooKeeper还提供watch功能，即watch的对象发生了改变会自动发notification, 这样所有的client就可以使用一致的，高可用的接口。

    3.config配置管理
    1) 通常手工修改配置文件的方法，这样容易出错，也需要人工干预才能生效，所以节点的状态无法同时达到一致。
    2) 大规模的应用都会实现自己的配置服务，比如用http web服务来实现配置中心化。它的缺点是更新后所有client无法立即得知，各节点加载的顺序无法保证，造成系统中的配置不是同一状态。

    4.membership用户角色/access control list, 比如在权限设置中，用户一旦设置某项权限比如由管理员变成普通身份，这时应在所有的服务器上所有远程CDN立即生效，否则就会导致不能接受的后果。

    5. 号码分配。通常简单的解决方法是用数据库自增ID, 这导致数据库切分困难，或程序生成GUID, 这通常导致ID过长。更优雅的做法是利用paxos算法在多台replicas之间选择一个作为master, 通过master来分配号码。当master发生故障时，再用paxos选择另外一个master。

    这里列举了一些常见的Paxos应用场合，对于类似上述的场合，如果用其它解决方案，一方面不能提供自动的高可用性方案，同时也远远没有Paxos实现简单及优雅。

    Yahoo!开源的ZooKeeper [5]是一个开源的类Paxos实现。它的编程接口看起来很像一个可提供强一致性保证的分布式小文件系统。对上面所有的场合都可以适用。但可惜的是，ZooKeeper并不是遵循Paxos协议，而是基于自身设计并优化的一个2 phase commit的协议，因此它的理论[6]并未经过完全证明。但由于ZooKeeper在Yahoo!内部已经成功应用在HBase, Yahoo! Message Broker, Fetch Service of Yahoo! crawler等系统上，因此完全可以放心采用。

    另外选择Paxos made live [7]中一段实现体会作为结尾。

    *  There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. In order to build a real-world system, an expert needs to use numerous ideas scattered in the literature and make several relatively small protocol extensions. The cumulative effort will be substantial and the final system will be based on an unproven protocol.
    * 由于chubby填补了Paxos论文中未提及的一些细节，所以最终的实现系统不是一个理论上完全经过验证的系统

    * The fault-tolerance computing community has not developed the tools to make it easy to implement their algorithms.
    * 分布式容错算法领域缺乏帮助算法实现的的配套工具, 比如编译领域尽管复杂，但是yacc, ANTLR等工具已经将这个领域的难度降到最低。

    * The fault-tolerance computing community has not paid enough attention to testing, a key ingredient for building fault-tolerant systems.
    * 分布式容错算法领域缺乏测试手段

    这里要补充一个背景，就是要证明分布式容错算法的正确性通常比实现算法还困难，Google没法证明Chubby是可靠的，Yahoo!也不敢保证它的ZooKeeper理论正确性。大部分系统都是靠在实践中运行很长一段时间才能谨慎的表示，目前系统已经基本没有发现大的问题了。

    Resources
    [1] The Chubby lock service for loosely-coupled distributed systems (PDF)
    [2] http://zh.wikipedia.org/wiki/Paxos算法
    [3] http://en.wikipedia.org/wiki/Paxos_algorithm
    [4] Paxos Made Simple (PDF)
    [5] ZooKeeper
    [6] The life and times of a zookeeper
    [7] Paxos Made Live – An Engineering Perspective (PDF)

    Memcached数据被踢(evictions>0)现象分析

    Monday, Sep 7th, 2009 by Tim | 85 Comments
    Filed under: data | Tags: , ,

    很多同学可能熟知Memcached的LRU淘汰算法，它是在slab内部进行的，如果所有空间都被slabs分配，即使另外一个slab里面有空位，仍然存在踢数据可能。你可以把slab理解为教室，如果你的教室满了，即使别的教室有空位你的教室也只能踢人才能进人。

    mc

    本文介绍的却是另外一种现象。今天监控发现线上一memcached发生数据被踢现象，用stats命令看evictions>0,因为以前也出现过此问题，后来对这个参数增加了一个监控，所以这次主动就发现了。由于给memcached分配的内存远大于业务存储数据所需内存，因此初步判断是“灵异现象”。

    第一步，netstat查看所有连接，排除是否被一些未规划的client使用，经排查后断定无此可能。

    第二步，用tcpdump抽样检查set的指令，排除是否有忘记设cache过期时间的client，初步检查所有典型的业务都有expire time。

    第三步，Google，未果

    第四步，看源代码，了解evictions计数器增加时的具体细节，oh, no…

    in items.c, memcached-1.2.8,

    125         for (search = tails[id]; tries > 0 && search != NULL; tries--, search=search->prev) {
126             if (search->refcount == 0) {
127                 if (search->exptime == 0 || search->exptime > current_time) {
128                     itemstats[id].evicted++;
129                     itemstats[id].evicted_time = current_time - search->time;
130                     STATS_LOCK();
131                     stats.evictions++;
132                     STATS_UNLOCK();
133                 }
134                 do_item_unlink(search);
135                 break;
136             }
137         }

    从源代码发现踢数据只判断一个条件，if (search->refcount == 0)，这个refcount是多线程版本计数用，在当前服务器未启用多线程情况下，refcount应该始终为0,因此初步判断memcached是从访问队列尾部直接踢数据。

    为了证实想法，设计以下场景：

    1. 部署一个memcached测试环境，分配比较小的内存，比如8M
    2. 设置1条永远不过期的数据到memcached中，然后再get一次，这条数据后续应该存在LRU队尾。
    3. 每隔1S向memcached set(并get一次) 1,000条数据，过期时间设为3秒。
    4. 一段时间后，stats命令显示evictions=1

    按我以前的理解，第2步的数据是永远不会被踢的，因为有足够过期的数据空间可以给新来的数据用，LRU淘汰算法应该跳过没过期的数据，但结果证实这种判断是错误的。以上业务的服务器发生被踢的现象是由于保存了大量存活期短的key/value,且key是不重复的。另外又有一业务保存了小量不过期的数据，因此导致不过期的数据惨遭被挤到队列踢出。

    本来这个问题就告一段落了，但在写完这篇文章后，顺便又看了新一代memcached 1.4.1的源代码，很惊喜发现以下代码被增加。

    items.c, memcached 1.4.1

    107     /* do a quick check if we have any expired items in the tail.. */
108     int tries = 50;
109     item *search;
110
111     for (search = tails[id];
112          tries > 0 && search != NULL;
113          tries--, search=search->prev) {
114         if (search->refcount == 0 &&
115             (search->exptime != 0 && search->exptime < current_time)) {
116             it = search;
117             /* I don't want to actually free the object, just steal
118              * the item to avoid to grab the slab mutex twice ;-)
119              */
120             it->refcount = 1;
121             do_item_unlink(it);
122             /* Initialize the item block: */
123             it->slabs_clsid = 0;
124             it->refcount = 0;
125             break;
126         }
127     }

    重复进行上述测试，未发生evictions。

    9/8 Update: 注意到L108的tries=50没有？试想把测试第2步设置51条不过期数据到cache中，情况会怎样？因此新版的Memcached也同样存在本文描述问题。

    几条总结：

    • 过期的数据如果没被显式调用get，则也要占用空间。
    • 过期的不要和不过期的数据存在一起，否则不过期的可能被踢。
    • 从节约内存的角度考虑，即使数据会过期，也不要轻易使用随机字符串作为key，尽量使用定值如uid，这样占用空间的大小相对固定。
    • 估算空间大小时候请用slab size计算，不要按value长度去计算。
    • 不要把cache当作更快的key value store来用, cache不是storage。

    某分布式应用实践一致性哈希的一些问题

    Sunday, Sep 6th, 2009 by Tim | 49 Comments
    Filed under: 架构 | Tags: ,

    最近项目中一个分布式应用碰到一些设计问题，听过上次技术沙龙key value store漫谈的同学可能会比较容易理解以下说明。

    场景
    假定一个有状态的服务，可以理解成web或者socket服务器，每个用户在这个服务上登录后是有状态的，我们把它的状态连同其他加载到内存的用户数据统称用户session。由于session数据实时会变化，加上程序访问session频率大，几乎所有的操作都跟session数据相关，因此不适合放在远程memcached中

    第一阶段
    考虑到单服务器不能承载，因此使用了分布式架构，最初的算法为 hash() mod n, hash()通常取用户ID，n为节点数。此方法容易实现且能够满足运营要求。缺点是当单点发生故障时，系统无法自动恢复。

    figure1

    第二阶段
    为了解决单点故障，使用 hash() mod (n/2), 这样任意一个用户都有2个服务器备选，可由client随机选取。由于不同服务器之间的用户需要彼此交互，所以所有的服务器需要确切的知道用户所在的位置。因此用户位置被保存到memcached中。

    当一台发生故障，client可以自动切换到对应backup，由于切换前另外1台没有用户的session，因此需要client自行重新登录。

    figure2

    这个阶段的设计存在以下问题

    • 负载不均衡，尤其是单台发生故障后剩下一台会压力过大。
    • 不能动态增删节点
    • 节点发生故障时需要client重新登录

    第三阶段
    打算去掉硬编码的hash() mod n 算法，改用一致性哈希(consistent hashing)分布
    假如采用Dynamo中的strategy 1(可参看Dynamo: Amazon’s Highly Available Key-value Store, PDF, P216)
    我们把每台server分成v个虚拟节点，再把所有虚拟节点(n*v)随机分配到一致性哈希的圆环上，这样所有的用户从自己圆环上的位置顺时针往下取到第一个vnode就是自己所属节点。当此节点存在故障时，再顺时针取下一个作为替代节点。

    figure3

    优点：发生单点故障时负载会均衡分散到其他所有节点，程序实现也比较优雅。

    应用一致性哈希分布后若干问题
    1.如何解决单点故障时候的session迁移？是否所有session都像Dynamo那样写入到多个节点(或双写)？如果双写所有的服务器需要消耗2倍的内存及更多CPU资源，所以优先不考虑双写方案。

    2.如果不双写，则发生故障切换时，即使服务器内部自动帮用户切换节点不重新登录，都需要牵涉到大量session重建，会引起集群震荡。当然这里可以稍微优化，比如session按需建立，IDLE的用户可以先不重建。

    3.当故障节点恢复时候如何处理？Dynamo的策略是故障期间所有的数据都属于hinted handoff, 就是备用机起业务代理作用，一旦故障机恢复就立即把所有临时数据从备用机拉回去，然后整个集群恢复正常流程。但由于本场景session数据比较笨重，而且牵涉到复制时存在并发变更，如果直接借鉴Dynamo的话则感觉切换成本过高，大部分开发人员倾向于继续用备用机处理该用户业务。如果恢复正常后不切换，则存在用户位置的不确定性，使用一致性哈希算出来的结果和用户实际所在的节点不同。需要顺着圆环往下找用户,效率很低。因此就有提议把所有用户所在的当前节点位置写入memcached。

    5. 假如需要将位置写入memcached,那似乎一致性哈希算法又成了花瓶，完全可以由client在create session时候随机选取一个没有故障的节点, 然后把位置写入memcached, 某个节点发生故障时，client再另外选一个随机的，并把新的位置写入memcached, 所有用户所在节点的位置都通过memcached来存储，服务器之间实时的通讯也通过查询memcached来寻址。从实用的角度来看，这样似乎程序更简单。

    因此，一致性哈希分布对于这个场景来说是无用的？

    12