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页，涉及了不少公式，因此翻起来也不会那么简单。