leveldb源代码分析2 理论基础

leveldb其实就相当于是bigtable中简化的每个数据节点，其中关键性的思想如下(来自于http://www.slideshare.net/sunzhidong/google-leveldb-study-discuss)：

也就是说原始的想法就是向如何将随机的io操作转换成顺序的io写操作，下面可能需要考虑的问题就是基于LSM这种数据结构如何进行insert, delete, update操作。这篇论文中写的很详细，如下：

Lsm

View more documents from xuqianghitsoft

下面只是简单的说明一下如何使用LSM实现上面的操作：

insert:数据首先写入到内存中，之后内存如果到达了一定的阀值之后，再将大块的数据刷新到磁盘上去。

delete操作：使用LSM结构实际上没有数据的删除工作，所谓的删除也仅仅是做标记，那这样可能带来一个问题就是如何保证删除的数据的查询不到？这里就设计到了数据查询的流程，首先肯定是先找内存，之后查找磁盘上的文件，并且磁盘上的文件的查找按照生成文件的先后顺序来排列（这里的假设就是新数据最可能是用户查找的数据）。这样就能保证如果存在某个key是被删除的，那么一定是先找到那个标记了删除的那个键值对，这样就能保证删除的数据是查询不到的。

update：和delete类似，只有追加操作，剩下的操作是在后续compact和spli中完成。

数据恢复：这里使用了通常的做法Write Ahead Log来实现，保证数据的可靠性。

同时上面的论文还提到了FiveMinuteRule原则，基本思想如下：

Simple cost-benefit arguments allow one to compute the break-even point for trading central-memory residence against disc accesses for data. If an item is accessed frequently enough, it should be main memory resident. In current technology, “frequently enough” means about every five minutes.如果数据被频繁的使用的话，那么就尽量将数据写入到内存中，这里的“频繁”具体是指五分钟，也就是如果数据被使用的频率在5分钟以内，那就尽量经该数据写入到内存中去。

Changing topics, another interesting questionis: “When does it makeeconomic sense to use more memory to save some cpu power?以空间换取时间的想法”, or conversely save some memory atthe expense of some cpu cycles? This issue comes up in codeoptimization where one can save some instructions by unwinding loops and indata structure design where one can pack data at the expense of masking andshifting operations to extract the data.

The logic is quitesimilar to the Five Minute Rule. Onepicks a certain price for memory (say 5K$/MB) and a certain price per MIP (say50K$/MIP). This means that 5 bytes costabout .005$. Similarly, one instructionper second costs about .005$. So 5 bytescosts about as much as 1 instruction per second.This gives the rule

Spend 5 bytes of main memory to save 1 instruction per second

更多参考这里：http://www.slideshare.net/xuqianghitsoft/five-minuterule

Five minuterule

View more documents from xuqianghitsoft

上面基本上就是leveldb的基本的理论基础，以后的几篇博文中将分析leveldb在代码上如何实现的及对LSM的变形。