Log files

log文件保存一系列的最新更新，每次更新都追加到当前的log文件中，当log文件达到其预定义的size上限时，其将会被转换成sorted table（*.ldb），并且创建一个新的log文件用于接收更新。在内存中保存当前log文件的副本(memtable)，每次读都会查阅一次memtable，以便每次读取的时候都可以获取到最新的更新

Sorted tables

sorted table(*.ldb)是一系列的根据key排序的entry组成。entry中的每个key对应一个value或者一个Deletion marker（Deletion marker用于淘汰存在于之前的sorted table中的entry)。 所有的sorted table被组织成一系列的level。从log file产生的sorted table被放置在young level(也就是level 0)，当young file的数量超过一定数量的时候（目前4个），所有的young files将和所有的与之有重叠的level 1 files merge成新的level 1 files(每个level 1文件存储2MB数据) 在young level可能存在重叠的keys，然而其它层的的文件不存在重叠的key 。对于L>=1，当我们合并后的level L文件总大小超过10^L时，并且与所有的与之重叠的level L+1的文件合并成一系列新的level L+1 files。这些合并操作产生的效果是，逐渐地令所有的在young level的最新更新操作仅仅以bulk read和bulk write的方式写入到largest level

overlap(重叠) level 0中的各个文件之间的key有overlap，但是level > 0的层的文件中没有重叠。 有序 文件中的key是有序的，就是说在文件中小key记录排在大Key记录之前，各个level的SSTable都是如此。当level > 0时，在文件间也是有序的(level > 0)

SSTable: 1.Table::Open() 打开文件调用Table::Open()，该函数读取sstable的除了data block之外的其他所有的block 2.cache: Table中维护的对data block的lru缓存，每次读取data block时，需要先从缓存中读取，如果缓存中没有，再去硬盘文件中读取该data block，并放入_cache中 3.VersionSet::table_cache: Table缓存 为table维护了一个缓存–>TableCache(lru cache), 缓存所有已打开的文件。

当从sstable中查找一个key时: 1.先去TableCache中去查找Table，如果查找到了，说明该文件已经打开过（即已经读取过除data block之外的所有block）, 如果没有找到，则先调用Table::Open打开文件，并将其加入缓存中。 2.调用Table::InternalGet去查找key。首先从meta block（bloom filter）查看该key是否存在，如果bloom filter说明不存在，那么就真的不存在，直接返回。如果bloom filter说明存在，则不一定存在，需要调用Table::BlockReader去查找data block。 2.1 首先从_cache中查找该data block是否被缓存, 如果已缓存，则直接从_cache中获取data block, 否则则需要从硬盘中读取该data block, 然后在data block中去查找该key(有序的)