银河里的星星
微博上看到的一篇文章，存储领域非常系统的介绍，尤其给出了各个部分的经典论文，需要翻墙，为方便阅读抄录如下
原文地址： 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. read more
如下内容是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文件。 read more
本文基本上是对现有的图计算框架论文或文档的一个综述。由于附图较多，未上传至相册，此处有pdf版本：http://pan.baidu.com/s/1uvjHW。
转载请注明作者：phylips@bmy
出处：http://duanple.blog.163.com/blog/static/7097176720123215230365/ read more
4.Concurrency and Recovery in the LSM-tree
本节我们来研究下用于LSM-tree并发访问和恢复的技术。为此，我们需要更深入地描述出rolling merge过程。我们将该并发访问和恢复算法正确性的形式化证明作为以后的工作，目前只是在此处简单地描述下它们的具体过程。 read more
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更划算。 read more