对于分布式在线服务,一个请求需要经过系统中多个模块,上百台机器的协作完成单次请求,典型场景就是Search Engine的一次用户检索,单靠人力无法掌握整个请求中各个阶段的性能开销,更无法快速的定位系统中性能瓶颈。Google Dapper文章描述了广泛用于Google内部服务的Trace Infrastruce—Dapper(原文地址见这里,译文地址见这里),文章本身的很易懂,没有复杂、精巧的实现机制(好像也是g公司publish出来的文章的特点),有一些分布式在线服务经验的程序员都可以很好的理解(英文版),这里就只抽一些点出来记录。而Zipkin是Twitter开源出来的一个Trace系统组件,实现中就参考了Google Dapper,项目主页见http://twitter.github.io/zipkin/

Google Dapper

目标: 无所不在的持续跟踪(ubiquitous deployment,and continuous monitoring),只有无所不在和持续,才能保证所有的问题都能被跟踪到,因为服务也是7*24的。为了做到这两点,Dapper对于这个Tracing组件,拆分出如下几个目标。

阅读全文…

, , ,

实际的生产环境中,经常会由于机器故障、机房掉电、网络异常、软件bug等原因,造成整个系统中某台机器、某些集群异常,无法提供稳定的服务;而系统也可能因为某些突发事件、外部攻击等原因,出现流量瞬间的大幅度增长,超过系统承载能力。因此,在系统设计时,需要充分的考虑系统的优雅降级、流量控制等。最近阅读了不少相关的文档,本文进行了整理,列举了一些构建大规模分布式服务的design principle如下。

Design Target

在设计初期,就需要充分考虑可扩展性、系统的可用性、运维和管理的便捷性以及成本,几点说明如下:

  • Scalability : Resource usage increase linearly(or better!) with load
  • Availability : Resilience to partial failure, Graceful degradation, Recoverability from failure
  • Manageability : Simplicity, Maintainability, Diagnostics
  • Cost : Machine cost and Operation cost

阅读全文…

工作中碰到一个内存分配导致的多线程server性能问题,网上翻到一个文档讨论多线程场景下的malloc性能——<malloc() Performance in a Multithreaded Linux Environment>,2000年的,有点旧,提到了多thread的时候,由于竞争单个堆分配器,导致malloc时间增长的问题。

写了小程序,使用同步模型,预分配固定个数的work thread,使用一种自定义的内存池(slab方式管理的内存池,当单次申请的内存大于4MB的时候,直接调用系统级的malloc)。循环1kw次的malloc模拟了下,统计每个线程的1kw总共耗时,结合文档中的Benchmark 1 Test的Result,有以下的几点可以供在平常开发多线程server时借鉴。

  1. work thread中尽可能的避免调用系统级的malloc,陷入内核态后等待时间很长。特别是在多线程场景下,由于竞争单个堆分配器,导致多线程下malloc巨慢无比。 (场景3):
  2. slab内存池使用要很小心,由于大于了预定义max_size后会调用系统级别的malloc,需要明确自己的使用场景会最大单次申请多大内存。如果某个场景下会经常超过max_size时,就特别要注意slab。测试场景2随机有1/1000的概率会超过4M。(场景2)。从结果看,线程越多,整个处理时间增长也很快,特别是当线程数超过Cpu的核数12后,增长迅速(猜测这个与malloc系统调用陷入内核态后,无法被随时抢占进行线程切换,导致处理时间变长,2.6后支持内核态抢占CONFIG_PREEMPT,但也不是任意时刻,线上机器编译参数好像也没开)。
  3. 场景1中1kw次malloc中,每个都小于4M,能够保证从slab内存池中分配,在线程增加的时候,性能没有明显变化,即使线程数超过了cpu核数,增加幅度也相对较小。结合server工作模型的特点(检索),一次query算一个task,完成后可以清理所有检索中allocate的object/memory,通过提供全局的nofree的一次性clear mempool来管理内存,有整体性能收益,也降低基础组件的设计实现难度。可以考虑在设计基础组件时,都是通过宿主程序统一传递内存池的方式。

结合测试结果,多线程server性能突增的场景原因的推测:绝大多数情况下,虽然我们开了N个work threads,但其实大部分都是在闲置cond_wait状态;当压力增大时,同时处在工作状态的线程上涨,多个线程竞争系统级malloc的概率增大,导致性能突增。

场景1 :  统计每个线程申请1kw次的时间,每次申请的大小都 < 4M。

image001

场景2 :  统计每个线程申请1kw次的时间,1/1000的概率申请的大小> 4M(调用系统malloc)。

image002

场景3:统计每个线程申请1kw次的时间,每次的申请大小> 4M(调用系统malloc)。

image003

,

Microsoft在2007年的文章中描述了他们用于维护大规模互联网服务的工具利器AutoPilot,采用简单的模型和设计思想,AutoPilot负责自动化的运维数据中心中提供服务的大规模机器。想起每次上线时的等待,尤其在部分模块启动时间很长的时候,必须到全部都部署完成并check完成后才能完事的痛苦过程,就感叹国外的先进生产力。原文pdf见这里

Design Principles

  1. 被autopilot管理的large-scale web service必须自身有一定的容错性,任何一个节点或者部分节点的失效都应该不影响系统对外的正常服务。autopilot是一个lazy action的监控&修复Service。
  2. Simplicity is as important as fault-tolerance when building a large-scale reliable, maintainable system。最近一年对这句话感触很深,一个本身就很庞大的系统,在很多地方必须尽可能的简单,任何过于精巧的实现解决的问题,一旦出了问题,很可能都会带来更严重的问题,并且很难处理。Autopilot在设计上的机制上非常简单,从错误分类、到执行的操作以及节点的状态定义都简单通用,不进行特化。同时允许用户端程序自己进行部分扩展。

单个Autopilot实例负责管理的一堆机器被成为一个cluster,数据中心中的购置的机器配置都是符合一系列标准套餐中的某种。

阅读全文…

paxos算法是为了解决在分布式系统中,多个process有关某一个值达成一致决议的算法,即一种一致性算法(Consensus Algorithm)。Google的分布式锁Chubby和Yahoo的Zookeeper的实现中都采用了此算法思想,Lamport(此人的牛逼程度可以参看他发表的文章和被引用的次数)在《paxos made simple》的第二页给出的abstract就一句话:“The Paxos algorithm, when presented in plain English, is very simple.”,有关paxos发布的背后的事情还挺有趣的,paxos从提出到发布用了9年,<The Part-Time Parliament>,Lamport虚拟了一个希腊的城邦paxos,用该城邦的人如何就一条法令达到一致来描述了整个算法,但计算机界的N多人都不悲剧幽默感,Lamport就在2001年写了一篇相对简短的《paxox made simple》,估计也就是这句abstract的来由

paxos算法将分布式系统的process划分为三种角色,分别为proposer, acceptor以及learner,其中只有proposer和acceptor参加决议过程,learner只是了解决议被批准以后系统具体选择的决议值,整个算法采用基于消息的传递模型,假设整个系统是消息异步,并且没有拜占庭失效问题(non-Byzantine model),就是整个系统中的消息可以延迟到达,可以重复发送甚至可以丢失,但不能被篡改,允许系统中的节点失效和重启,但需要这些节点在失效到重启之间具有永久性存储介质用以记录信息。

整个paxos算法的过程是一个两段式提交,由proposer提出决议(value),acceptor接受并选择决议,用一个{n,v}来对传递的消息进行描述,n表示一个严格递增不重复的编号,有关这个编号的实现在paxos made simple中提到的是让所有的proposer都从不相交的数据集合中进行选择,例如系统有5个proposer,则可以为每一个proposer分配一个标识j(0~4),则每一个proposer每次提出决议的编号可以为5*i + j(i可以用来表示round),v表示value。

Phase 1a: proposer提出一个决议并选择一个编号N,发送message prepare(N)给大多数(Majority)的Acceptor。

Phase 1b: acceptor接受到prepare(N)的消息后,如果不违法自己给其他proposer的承诺,即没有收到过比N编号更高的prepare请求,则返回给proposer消息{n,v},n是自己上次批准的请求编号,v是自己上次accept的value。并承诺自己不再接受任何小于N的编号的prepare请求。如果acceptor之前已经收到过其他高于N的编号的prepare请求,则忽略prepare(N),也可以给一个deny反馈(出于效率考虑,不反馈不影响正确性)。

Phase 2a: proposer收到多数的acceptor的确认反馈后,即可以进入批准阶段,proposer选择一个value(V)(V所有acceptor回馈的消息中,编号最大的value),或者当任何acceptor都没有value反馈时,proposer可以自己任意选择value值,发送Accept(N,V)给所有的acceptor。

Phase 2b: 当acceptor接受到一个accept(N,V)的请求时,acceptor就批准这个请求,除非该acceptor之前收到了一个比编号N更高的prepare请求。

整个算法的执行过程中,proposer可以任何时间随意的抛弃一个proposal,不影响正确性。算法的执行图解如下(from wikipedia)

 Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,Vn)
   |         |<---------X--X--X------>|->|  Accepted(N,Vn)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Learner需要了解被选择了的value,从上图可以看出在Phase 2b阶段时,当acceptor接受了一个决议后,会给Learner发送消息通知learner,为了尽快的使得Learner了解到被选择的value,可以每一个Acceptor都发送消息给每一个Learner,这样会产生大量的消息,是Acceptor个数和Learner的乘积。另外一种是由于系统中没有拜占庭失效,可以采用一个主Learner接受Acceptor发送的决议并且通知其他的Learner,这样减少了消息总量但会引起单点失效和多一级的传递。因此可以在实践中做一个权衡,选一个主learner集合来对learner进行通知。

由于有可能存在活锁的情况,即两个proposer轮流的用更高的编号提出新的prepare请求,使得没有任何一方的决议能成功的被批准。因此会选择一个主proposer,只有该proposer才能提出决议,如果主proposer提出一个决议遇到了deny,即存在另外一个更高的编号决议,则直接选择一个足够大的编号进行提议。主proposer,即leader包括主learn的选择一般也采用paxos算法,zookeeper中leader的选择就采用了fast paxos算法。

虽然Lamport说paxos算法非常simple,然后文章也很简短,但跟所有学习者的感觉一样,远没有大师的智慧,不会觉得他特别simple,看了几天也还只了解大概,特别是在看到相关引申的各种文章后。有关paxos算法在实现角度的描述以及实现可以参考Lamport在2005年写的<Fast Paxos>,以及他人写的<Paxos Made Live – An Engineering Perspective>,和<Paxos在大型系统中常见的应用场景>。

Reference:

[1] http://en.wikipedia.org/wiki/Paxos_algorithm (对整个paxos系列描述的相当详细)

[2] http://zh.wikipedia.org/wiki/Paxos算法 (paxos made simple的简单译文)

[3] Paxos Made Simple

[4] Paxos Made Live – An Engineering Perspective