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页，涉及了不少公式，因此翻起来也不会那么简单。
1.序
通过对Google发表的论文进行梳理，我们了解到了当前分布式系统领域的一些最新热点和发展趋势。梳理下这些论文，我们会发现它们主要发表在OSDI、SOSP、SIGMOD、VLDB、Macro、Eurosys、SIGCOMM、CIDR、SIGARCH、SIGCOMM等顶级期刊和会议上。反过来通过关注这些会议和期刊，我们就可以持续跟踪该领域的最新进展。但是也会发现这些会议和期刊每个每年都会发表几十上百篇文章，让人应接不暇。同时如在第一篇文章所指出的，这些文章背后的理论基础却很少发生变化，基本上还是几十年前就已提出的。为了更好更快地理解这些层出不穷的新论文，理清其所依赖的理论基础显得尤为重要。正如前文所述，”如果要真正理解这些论文，除了论文本身内容之外，也还需要去了解传统的分布式系统和关系数据库理论”。
按照习惯，还是在这岁月交替之际，写一篇小小的总结吧。虽许久不再写流年，而流年依旧如流年。依旧觉得很快这一年就又过去了。
过去的一年里，起了很多变化，无论是工作还是生活。刚工作的时候，一个人度着周末，经常就是打印个三两篇论文，读着读着就是一天。偶尔还看点闲书，生活倒也惬意，只是颇有些单调。所以在那极单调的日子里，倒也看了不少东西。很多人会觉得能有时间看这么多文章而且还翻译出来的人，一定是在学校或者研究所的吧。其实如果想看，又何需一定是悠闲的人呢。也忘了是哪年哪月读到的了，只是记忆犹新，欧阳修<<归田录>>中有云”余平生所作文章，多在三上，乃马上、枕上、厕上也。盖惟此尤可以属思尔“。其实并不是没有时间，只是需要自己去找，即使每天给自己一个小时的阅读时间，累积下来，一周，一月，一年，只要坚持，就能读很多东西。
作者：Dhruba BOrthakur & Joydeep Sen Sarma etc. Facebook Inc 2011-6
原文：http://wenku.baidu.com/view/5b1f48ef0975f46527d3e18b.html
译者：phylips@bmy 2011-9-11
出处：http://duanple.blog.163.com/blog/static/7097176720118121573597/
摘要
Facebook最近部署了Facebook Messages，这是它的首个构建于Apache Hadoop平台上的user-facing应用。使用构建于Hadoop之上的类数据库层Apach HBase来对每天数十亿的消息信息进行处理支持。这篇论文描述了Facebook在众多系统中(比如Apache Cassandra，Voldemort)最终选择了Hadoop和HBase的原因，并讨论了应用程序在一致性、可用性、分区容忍性、数据模型及可扩展性上的需求。我们还会探讨一下为了让Hadoop成为一个更有效的实时性系统所做的那些改进，在配置系统过程中所做的那些权衡，以及这种基于Hadoop的解决方案与Facebook和很多其他互联网公司在很多应用程序中采用的那种分片(sharded)MySQL数据库模式相比所具有的优势。我们还会讨论各种设计选择的背后动机，我们在日常工作中面临的挑战，一些未来的还在开发中的功能和改进。我们提供的这些关于部署中的各种观点可以为那些正在考虑使用基于Hadoop的解决方案取代传统分片RDBMS部署的公司，提供一种参考性的模型。
译者：phylips@bmy 2011-10-1
出处：http://duanple.blog.163.com/blog/static/70971767201191661620641/
本文翻译自：http://ofps.oreilly.com/titles/9781449396107/architecture.html
作为开源类BigTable实现。HBase目前已经应用在很多互联网公司中。