银河里的星星
[说明：本文是阅读Google论文“Dapper, a Large-Scale Distributed Systems Tracing Infrastructure”之后的一个简要总结，完整译文可参考此处。 另论文“Uncertainty in Aggregate Estimates from Sampled Distributed Traces”中有关于采样的更详细分析。此外，Twitter开源的Zipkin就是参考Google Dapper而开发。]
作者：Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman. 1987
原文：Concurrency Control and Recovery in Database Systems
译者：phylips@bmy 2013-02-14
译文：http://duanple.blog.163.com/blog/static/70971767201311810939564/
[序：历史上，数据库领域共产生过三位图灵奖得主Charles Bachman，E.F.Codd和Jim Gray
作者：Tushar Chandra&Rebert Griesemer&Joshua Redstone 2007 Google.Inc
原文：http://labs.google.com/papers/paxos_made_live.pdf
译者：phylips@bmy 2012-11-28
译文：http://duanple.blog.163.com/blog/static/7097176720121123114918404/
[序：Google在它的分布式系统中，大量使用了Paxos，比如Chubby、MegaStore、Spanner等系统中。这篇文章详细讲述了最初实现Paxos碰到的一系列问题及解决方案，是一篇全面讲解分布式系统工程实践的文章。其中提到的很多真实发生的场景，相信做过分布式系统的人都会感同身受，每个人或多或少都会遇到过一些类似的问题。与理论界的文章相比，这篇文章显得非常实际，所有内容都来自Google一线工程师的实战，非常值得一看。]
作者：phylips@bmy 2012.12.21
出处：http://duanple.blog.163.com/blog/static/709717672012112203543166/
自Paxos提出，迄今已有20多年了，围绕着该算法曾经发生过一些非常有趣的事情，这些也已成为人们津津乐道的一段轶事，故事的主角自然是Paxos的提出者Lamport，当然Lamport的特立独行也是很早就出了名的。首先来讲述下这些有趣的八卦，之后会再理一下Paxos的整个发展过程，以及在这个过程中产生的一系列比较重要的论文，总共会涉及到十几篇论文，如果有时间还是最好都研读一下。由于时间关系，我也只是选择了其中最为重要的三篇，进行了阅读，并将它们翻译了出来，稍后会整理出来。
zz from：http://blog.csdn.net/hoping/article/details/5164194
前段时间看到一篇文章：On Understanding Data Abstraction, Revisited。其中对数据抽象这个概念进行了深入的探讨，清晰地给出了抽象数据类型和对象的定义，并阐述了其区别以及对于实际编程的影响。因此抽空翻译出来供大家学习、参考。
作者：Butler W.Lampson 1996
原文：http://research.microsoft.com/en-us/um/people/blampson/58-consensus/Acrobat.pdf
译者：phylips@bmy 2012-11-18
译文：http://duanple.blog.163.com/blog/static/709717672012102185013508/
[序：关于这篇文章，其实之前在“A brief history of Consensus, 2PC and Transaction Commit”中有过一些介绍，它最重要的意义在于使得Paxos算法为理论研究领域的科学家们所重视，并最终使得Leslie Lamport那篇“The Part-Time Parliament”从故纸堆里重见天日。
作者：Leslie Lamport. 1978
原文：http://www.stanford.edu/class/cs240/readings/lamport.pdf
译者：phylips@bmy 2012-10-13
译文：http://duanple.blog.163.com/blog/static/709717672012920101343237/
[
序：时间是一个很抽象的概念，爱因斯坦说时间是幻觉，马赫(Ernst Mach)说：我们根本沒有能力以时间來测量事物的变化，相反的，我们是透过事物的变化因而产生时间流动的抽象概念。那么在分布式系统中是如何定义时序的呢？这篇论文进行了讨论，该论文首先通过定义一整套逻辑时钟系统对所有事件进行ordering，然后通过解决一个资源互斥访问问题说明了如何将此应用到分布式系统中，并引入了状态机复制的方法。之后又由逻辑时钟所存在的一个问题引出了物理时钟的使用，由于物理时钟本身会存在偏差，又给出了一个物理时钟同步算法，并给出了一个关于物理时钟同步的定理。
作者：dullgull
原文：http://www.dullgull.com/ 文章链接
源地址：http://research.microsoft.com/en-us/um/people/lamport/pubs/ds-interview.pdf
Dejan Milojicic: 你从事的许多具有想象力的问题都在实际应用中有成就，甚至在几十年之后仍有影响。你对研究方向的选择在时机上有什么特别么？
zz from:http://www.myoops.org/main.php?act=course&id=2165
翻譯：林家弘
編輯：朱學恒，陳盈
The honeycomb shown above is a common architectural metaphor for distributed algorithms. Similar to bees performing different functions to build a honeycomb, multiple computing devices depend on each other to accomplish a task. (Image by MIT OCW.)
Google内部的介绍
Spanner: Google’s Globally-Distributed Database 论文原文
Thread on G+ by Jeff Dean
Building Spanner 视频 keynote Google工程师 Alex Lloyd
Lessons and Advice from Building Large Distributed Systems 最早提到Spanner的，Jeff Dean在LADIS2009的keynote
作者：Grzegorz Malewicz, Matthew H. Austern .etc.Google Inc 2010-6
原文：http://people.apache.org/~edwardyoon/documents/pregel.pdf
译者：phylips@bmy 2012-09-14
译文：http://duanple.blog.163.com/blog/static/70971767201281610126277/
[说明：Pregel这篇是发表在2010年的SIGMOD上，Pregel这个名称是为了纪念欧拉，在他提出的格尼斯堡七桥问题中，那些桥所在的河就叫Pregel。最初是为了解决PageRank计算问题，由于MapReduce并不适于这种场景，所以需要发展新的计算模型去完成这项计算任务，在这个过程中逐步提炼出一个通用的图计算框架，并用来解决更多的问题。核心思想源自BSP模型，这个就更早了，是在上世纪80年代由Leslie Valiant(2010年图灵奖得主)提出，之后在1990的Communications of the ACM 上，正式发表了题为A bridging model for parallel computation的文章。目前实际上已经有针对Pregel这篇文章的翻译版本了，不过只翻译了出了前半部分关于Pregel的设计与实现部分。其实后半部分也很重要，有助于理解整个图计算的历史背景，以及Pregel本身的性能和项目本身的演化等，另外最近越来越多的人开始关注这一文章，所以还是抽出时间重新阅读了一遍，并重新翻译出来，以供参考]
序：Sawzall的论文早在2006年就发表了，后来Google又推出了Tenzing，Dremel等数据分析系统，到了2010年就把Sawzall给开源了，项目主页：http://code.google.com/p/szl/。与Tenzing，Dremel相比， Sawzall所能做的事情还是比较有限，但是作为一种DSL，毕竟还是要比直接写MapReduce job要更易用些。本文就简单描述下其原理使用及扩展方法，转载请注明：
微博上看到的一篇文章，存储领域非常系统的介绍，尤其给出了各个部分的经典论文，需要翻墙，为方便阅读抄录如下
原文地址： http://dirkmeister.blogspot.com/2010/01/storage-systems-course-my-own-idea.html 作者：Dirk Meister
In my last post, I summarized some of the storage systems courses from international top universities with storage system labs.
如下内容是Sanjay发表在Google Groups leveldb 上的初始设计方案。实际实现可能与此不同。对于bloom filter的支持是在最新的1.4版本中加入的，在此之前的版本中并无此支持。
人们希望可以在LevelDB中加入bloom filter的支持。目前针对一次查询，LevelDB可能需要在每个level上进行一次磁盘随机访问。通过使用bloom filter可以大大减少所需要的随机访问操作次数。比如，假设调用者正在查找一个值为”Foo”的key，LevelDB会从每个level下选择相应的SSTable文件(那些range包含了该key的文件)，之后会在这些SSTable文件上进行随机读。如果每个SSTable都有一个对应的bloom filter，那么查找时就可以很容易地通过检查bloom filter跳过那些不包含该key的SSTable文件。
本文基本上是对现有的图计算框架论文或文档的一个综述。由于附图较多，未上传至相册，此处有pdf版本：http://pan.baidu.com/s/1uvjHW。
转载请注明作者：phylips@bmy
出处：http://duanple.blog.163.com/blog/static/7097176720123215230365/
4.Concurrency and Recovery in the LSM-tree
本节我们来研究下用于LSM-tree并发访问和恢复的技术。为此，我们需要更深入地描述出rolling merge过程。我们将该并发访问和恢复算法正确性的形式化证明作为以后的工作，目前只是在此处简单地描述下它们的具体过程。
3.3 Multi-Component LSM-Trees
对于给定的LSM-tree，参数M代表了rolling merge过程中插入到每个C1树的叶子节点中的C0树的平均记录数。在merge到C1树的节点中之前，这些新记录会首先在C0中积累一段时间，因此通常我们认为M是大于1的。但是，通过公式(3.2){! M=(Sp/Se)·(S0/(S0+S1))}能够看出，如果与C0树相比C1树足够大，或者是单条记录非常大以至于单个page中只能放下很少的记录，那么M的值就可能会小于1。这样的一个M值意味着，为了能将C0中的一条记录移出内存将不得不读入多个C1的page。根据公式(3.4){! COST(LSM-ins)/ COST(B-ins)=K1·(COSTπ/COSTp)·(1/M)}，在M< K1·(COSTπ/COSTp)的情况下，将会抵消掉multi-page的批处理效果，此时对于插入操作来说使用B-树要比使用LSM-tree更划算。
说明：转载请保留全部信息
作者：Patrick O’Neil &Edward Cheng etc. 1996
原文：http://www.springerlink.com/content/rfkpd5yej9v5chrp/
译者：phylips@bmy 2011-12-25
译文：http://duanple.blog.163.com/blog/static/7097176720120391321283/
【随着NoSql系统尤其是类BigTable系统的流行，LSM-Tree这个名词也开始变得不再陌生。相信大多数了解NoSql系统的人，基本上都会听到过LSM-Tree这个名词，但是读过其原始论文的人估计就不是很多了。在我看来，LSM-Tree之于BigTable的重要性就像一致性hash之于Dynamo。溯本求源一向是本人的追求，希望可以从最初的文字中找到蕴含在结构之下的更多思考。老实说，这篇论文也算是很长的了，原文共30页，涉及了不少公式，因此翻起来也不会那么简单。