分布式系统

作者：LESLIE LAMPORT 2001 译者：phylips@bmy 2011-4-30

出处：http://duanple.blog.163.com/blog/static/709717672011440267333/

 [

序：在PODC2001会议上，我总是听到人们在抱怨paxos算法是那么的难以理解。人们总是被那些古希腊的名称弄得晕头转向，而使得他们觉得论文难以理解，实际上算法本身是很简单的。于是在会议期间我就找了几个人聚在一起，试着直接向他们口头解释该算法。回家之后，我将这些内容整理了下来，后来又基于Fred Schneider 和 Butler Lampson的建议做了修改。就形成了现在的这个版本，虽然已经有13页长了，但是其中仍未包含任何一个比n1>n2更复杂的公式。{!本部分摘自Lamport的my writings，my writings是Lamport本人对自己以往发表的论文的一些总结，其中很多文字涉及到这些论文的创作来源。可以看出该论文的产生经历，与拜占庭将军问题有着截然相反的历程，在发表The Byzantine General Problem的时候，作者是用拜占庭将军这一场景引入到原来的算法中，而Paxos则是作者最初就是用古希腊的故事情节来描述，我想当时作者之所以采用一个故事性的背景，也是因为拜占庭将军这一写作方法带来的成功而受到的影响。只是事与愿违，人们觉得那篇The Part-Time Parliament太难理解了，而且通篇没有数学化的公式证明。根据Lamport的说法，当时的三个审稿人认为这篇文章虽然重要性不够但还有点意思，只是还应该把所有有关Paxos(Lamport在论文中虚构出的一个岛屿的名称)这一描述的地方全部删掉，但是Lamport觉得这些人太没幽默感了，也就没有按照他们要求的去做。以至于作者虽然在1990年就将它提交给了TOCS，但直到1998年才被发表。但是发表之后，很多人还是觉得原来那篇太难理解了，于是才产生了这一篇。不过现在回头再看，虽然当时Lamport的写作方式令文章被埋没了数年，但是也正因此才产生了如此有趣的一则轶闻，Paxos也成为该算法无可争议的名称，虽然另一篇文章<<Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems>>在1988年就独立地提出了类paxos的一致性算法。} read more

作者：phylips@bmy 时间：2011-3-27

出处：http://duanple.blog.163.com/blog/static/70971767201133011171419/ 

作为这个星球上最大的互联网公司，毫无疑问google正在引领着海量数据处理实践的潮流。虽然Google经常发表一些对于自己来说已经过时甚至不再使用的技术的论文，但是发表之后总会有类似的系统被业界实现出来，也足以说明google的技术至少领先业界数年。 read more

你好。
其实到现在为止距离淘宝双十一事件已经过去蛮多天了，但在整个技术圈里面大家还是津津乐道。我这次在采访之前在和一些网友做沟通的时候，他们也提出了非常多非常有意思的问题，包括一些高并发的，一些压力测试的等等，那我希望也代表这些网友和你做一个交流。那第一个问题就是，在那么大的访问量，淘宝的技术团队是如何做到一个高并发处理的？ read more

作者：phylips@bmy 时间：2011-2-26

出处：http://duanple.blog.163.com/blog/static/70971767201133011171419/

还在上研的时候，由于当时在做并行计算相关的方向，老师推荐阅读下google的MapReduce以做参考，当时并没有仔细的去看论文只是大概看了些中文的介绍。第一次真正阅读google关于分布式系统的论文大概是2009年，临近毕业，当我向未来公司的老大询问需要提前看下哪些资料的时候，老大告诉我只需要看google的三篇论文就可以了。那时才知道google的三篇经典论文：GFS MapReduce BigTable。于是便去网上搜索了下，并根据网上的推荐额外加了几篇将它们打印成册，其中增加的比较重要的两篇就是关于google cluster和chubby的论文，然后寒假的时候便把它们带回了家，阅读的时候发现，基本就cluster这篇还能理解，其他的都比较困难，尤其是Chubby，基本没有明白其中的内容，尽管如此还是把它们都通读了一遍。 read more

分布式领域经典论文译序

sql&nosql年代记

SMAQ：海量数据的存储计算和查询

一．google论文系列

0.     google系列论文翻译集(合集)

1.      google系列论文译序

2.      The anatomy of a large-scale hypertextual Web search engine (译 zz)

3.      web search for a planet :the google cluster architecture(译) read more

　　继成功举办首期TUP活动后，日前在北京丽亭华苑酒店鸿运二厅，由CSDN和《程序员》杂志联合策划组织的TUP第二次活动如期而至，本次活动以Web 2.0技术为主题，聚焦当下火热的社交网、微博架构与实时搜索领域。就相关领域及产品研发背后的技术、产品设计及用户体验话题为与会者提供全开放式的交流平台。即使是付费沙龙，参会报名人数仍在不断上升，本次活动有超过300人来到现场。 read more

from:http://tech.sina.com.cn/i/2010-11-16/17574872122.shtml

新浪科技讯 11月16日下午消息，由新浪微博(http://t.sina.com.cn)主办的中国首届微博开发者大会在北京举行，这是国内微博行业的首场技术盛宴。作为国内微博市场的绝对领军者，新浪微博将在此次大会上公布一系列针对开发者的扶持政策，以期与第三方开发者联手推动微博行业的整体发展。图为微博平台首席架构师杨卫华演讲。 read more

作者：Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson 1983

转载请注明译者：phylips@bmy 2011-3-12

出处：http://duanple.blog.163.com/blog/static/70971767201122011858775/

[序：这篇论文虽然只有短短的6页不到，但却包含了一个分布式系统领域最重要的结论。同时因为该结论的重要性和影响力，该论文获得了2001年度的Edsger W. Dijkstra Prize。这个著名的结论被称为FLP结论或者FLP不可能性，”FLP”即该论文的三位作者Fischer Lynch Paterson的首字母。这三位都是分布式领域非常重要的科学家，尤其是Nancy A. Lynch，她的研究成果几乎遍及所有重要的分布式算法。] read more

       作者：LESLIE LAMPORT, ROBERT SHOSTAK, and MARSHALL 1982

译者：phylips@bmy 

出处：http://duanple.blog.163.com/blog/static/7097176720112643946178/

[序：我一直觉得正是因为通过用一组围坐在圆桌旁的哲学家来表述，Dijkstra 的哲学家就餐问题才变得如此让人关注。(比如在理论界，它可能比读者/写者问题都引人注目，尽管读者/写者问题可能更具实际意义)，我认为<<Reaching Agreement in the Presence of Faults >>所描述的问题十分重要，值得计算机科学家们去关注。哲学家就餐问题使我认识到，把问题以讲故事的形式表达出来更能引起人们的关注。 read more

作者：phylips@bmy 时间：2011-5-3

出处：http://duanple.blog.163.com/blog/static/70971767201133011171419/ 

       关于分布式理论的研究已经有数十年的历史。 

本系列论文的选择主要是参照文章<<a brief history of consensus,2pc and transaction commit>>中涉及的那些。同时也会参考该领域的重要的计算机科学家的重要著作，比如Lesslie Lamport。Lesslie Lamport就是著名软件Latex的作者，他在分布式领域的很多研究工作奠定了分布式系统的理论基础。其最重要的论文主要是如下几篇：“Time, Clocks, and the Ordering of Events in a Distributed System”,该论文获得了2000年度 the PODC最具影响力论文奖；“The Byzantine Generals Problem”；“Distributed Snapshots: Determining Global States of a Distributed System”；“Reaching agreement in the presence of faults“，该论文获得2005年度 Edsger W. Dijkstra奖；“The Part-Time Parliament”，该论文中描述了解决分布式一致性的Paxos算法。 同时分布式计算领域还有一个重要的奖项，Edsger W. Dijkstra奖，该奖项每年选择一些对分布式计算理论和实践重要意义的经典论文，它们通常都经过了至少十年的检验。  read more

by Mark Mc Keown

http://betathoughts.blogspot.com/2007/06/brief-history-of-consensus-2pc-and.html

转载请注明译者：phylips@bmy

出处：http://duanple.blog.163.com/blog/static/70971767201103051639551/

这是一段关于一致性，事务以及两阶段提交的历史的描述。阅读关于一致性的文献可能会有些困难，因为：各种用语在不断的演化着(比如一致性<consensus>最初叫做协商<agreement>)；各种研究成果并不是以一种逻辑性的顺序产生出来；同时描述整个分布式算法的框架与这些研究工作又是平行地演化着；此外除了Lynch的《分布式算法》外，很少有书籍涉及到这个主题。 read more

转载请注明作者：phylips@bmy       

出处：http://duanple.blog.163.com/blog/static/70971767201102944512890/

        1961年，通用电气公司(General Electric Co.)的Charles Bachman成功地开发出世界上第一个网状DBMS也是第一个数据库管理系统——集成数据存储(Integrated DataStore IDS)，奠定了网状数据库的基础，并在当时得到了广泛的发行和应用。后来Charles Bachman因在数据库方面的贡献获得图灵奖。 read more

        本文翻译自The SMAQ stack for big data 

        英文原文：http://radar.oreilly.com/2010/09/the-smaq-stack-for-big-data.html

SMAQ代表了存储，MapReduce和查询。

转载请注明译者：phylips@bmy

出处：http://duanple.blog.163.com/blog/static/709717672011016103028473/  read more

Brewer’s CAP Theorem 中文版 
http://pt.alibaba-inc.com/wp/dev_related_728/brewers-cap-theorem.html

原版： http://www.julianbrowne.com/article/viewer/brewers-cap-theorem

可伸缩性最佳实践：来自eBay的经验
NoSQL数据库笔谈 http://www.yankay.com/wp-content/uploads/2010/02/NoSql%20Database%20Note/ read more

云计算平台是非常巨大的分布式系统，需要处理庞大的处理请求，因此任何小概率事件在此平台中都必然发生。

DBMS强调ACID：原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)、持久性 (Durability)。其中的一致性强调当程序员定义的事务完成时，数据库处于一致的状态，如对于转帐来说，事务完成时必须是A少了多少钱B就多了多少钱。而对于很多互联网应用来说，对于一致性和隔离性的要求可以降低，而可用性(Availability)的要求则更为明显。从而产生了两种弱一致性的理论：BASE和CAP。 read more

数据收集和存储的速度正在惊人地发展，对Google而言，数以万计的服务器中存储的PB级数据，以及每天在服务器中处理的数以亿计的图片文件，都对其未来的系统架构提出了新的挑战。重新设计系统架构以此优化搜索引擎的增量处理能力已是Google当务之急。 read more

Updated As its custom-built file system strains under the weight of an online empire it was never designed to support, Google is brewing a replacement.

Apparently, this overhaul of the Google File System is already under test as part of the "Caffeine" infrastructure the company announced earlier this week. read more

zz from:

http://blog.csdn.net/AE86_FC/archive/2010/08/08/5796640.aspx

Abstract
许多实际应用问题中都涉及到大型的图算法。比如网页链接关系和社会关系图等。这些图都有相同的特点：规模超大，常常达到数十亿的顶点和上万亿的边。这么大的规模，给需要在其上进行高效计算的应用提出了巨大的难题。在这篇论文中，我们将提出一种适合处理这类问题的计算模式。将程序用一系列的迭代来描述(Programs are expressed as a sequence of iterations)，在每一次迭代中，每一个顶点都能接收来自上一次迭代的信息，并将这些信息传送给下一个顶点，并在此过程中修改其自身的状态信息，以该顶点为起点的出边的状态信息，或改变整个图的拓扑结构。这种面向顶点的方法足够的灵活，可以用来描述一系列的算法。这种计算模式被设计的足够高效，可扩展，和足够的容错，并在有上千台的计算节点的集群中得以实现。这种模式中隐式的同步性(implied synchronicity)使得它对程序的确认变得简单。分布式相关的细节已经被一组抽象的API给隐藏。而展现给人们的仅仅是一个表现力很强，很容易编程的大型图算法处理的计算框架。
Keywords
分布式计算，图算法
1．Introducetion
Internet使得Web graph成为一个人们争相分析和研究的热门对象。Web 2.0更是将对社会关系网的关注推向高潮。同时还有其他的大型图对象（如交通路线图，报纸文献，疾病爆发路径，以及科学研究的发表文章中的引用关系等），也已经被研究了很多年了。同时也有了许多相应的应用算法，如最短路径算法，page rank理论演变而来的图相关算法等等。同时还有许多其他的图计算问题也有着相当的实际价值，如最小切割，以及连通分支等相关问题。
事实证明，高效的处理大型图对象的计算是一件极具挑战性的事情。图算法常常暴露出类似不高效的本地内存访问，针对每个顶点的处理过少，以及在计算过程中改变并行度等问题。分布式的介入更是加剧了locality的问题，并且加剧了在计算过程中机器发生故障而影响计算的可能性。尽管大型图形无处不在，其商业应用也非常普及，但是一种通用的，适合各种图算法的大型分布式环境的实现到目前还不存在。
要实现一种大型图计算的算法通常意味着要在以下几点中作出选择: read more

Spanner: Google s next Massive Storage and Computation infrastructure

MapReduce Bigtable and Pregel have their origins in Google and they all deal with large systems . But all of them may be dwarfed in size and complication by a new project Google is working on which was mentioned briefly (may be un-intentionally) at an event last year. read more

zz from:

http://horicky.blogspot.com/2010/10/scalable-system-design-patterns.html

Looking back after 2.5 years since my previous post on scalable system design techniques, I’ve observed an emergence of a set of commonly used design patterns. Here is my attempt to capture and share them.
Load Balancer
In this model, there is a dispatcher that determines which worker instance will handle the request based on different policies. The application should best be "stateless" so any worker instance can handle the request.
This pattern is deployed in almost every medium to large web site setup.

Scatter and Gather
In this model, the dispatcher multicast the request to all workers of the pool. Each worker will compute a local result and send it back to the dispatcher, who will consolidate them into a single response and then send back to the client.
This pattern is used in Search engines like Yahoo, Google to handle user’s keyword search request … etc.

Result Cache
In this model, the dispatcher will first lookup if the request has been made before and try to find the previous result to return, in order to save the actual execution.
This pattern is commonly used in large enterprise application. Memcached is a very commonly deployed cache server.

Shared Space
This model also known as "Blackboard"; all workers monitors information from the shared space and contributes partial knowledge back to the blackboard. The information is continuously enriched until a solution is reached.
This pattern is used in JavaSpace and also commercial product GigaSpace.

Pipe and Filter
This model is also known as "Data Flow Programming"; all workers connected by pipes where data is flow across.
This pattern is a very common EAI pattern.

Map Reduce
The model is targeting batch jobs where disk I/O is the major bottleneck. It use a distributed file system so that disk I/O can be done in parallel.
This pattern is used in many of Google’s internal application, as well as implemented in open source Hadoop parallel processing framework. I also find this pattern can be used in many many application design scenarios.

Bulk Synchronous Parellel
This model is based on lock-step execution across all workers, coordinated by a master. Each worker repeat the following steps until the exit condition is reached, when there is no more active workers.
Each worker read data from input queue
Each worker perform local processing based on the read data
Each worker push local result along its direct connection
This pattern has been used in Google’s Pregel graph processing model as well as the Apache Hama project.

Execution Orchestrator
This model is based on an intelligent scheduler / orchestrator to schedule ready-to-run tasks (based on a dependency graph) across a clusters of dumb workers.
This pattern is used in Microsoft’s Dryad project

Although I tried to cover the whole set of commonly used design pattern for building large scale system, I am sure I have missed some other important ones. Please drop me a comment and feedback.
Also, there is a whole set of scalability patterns around data tier that I haven’t covered here. This include some very basic patterns underlying NOSQL. And it worths to take a deep look at some leading implementations. read more