LevelDB学习与实践
一、原理
1、Files
leveldb的实现类似于Bigtable中的一个tablet（Google），只不过底层的文件组织形式稍有不同。
每个Database有一系列本地文件组成，这些文件有不同的类型：
Log文件
log文件存储了一序列的最近更新操作，每个更新（update）都会append到当前log文件的尾部，当log文件的尺寸达到预设定的大小时，将会把此log文件转换成一个sorted table（.sst）文件，然后滚动创建一个新的log文件来保存此后的updates操作。
当前log文件的数据copy被保存在一个内存结构中，称为memtable。每个read操作都会访问memtable，因此这些update数据都可以在read操作中反应出来。
Sorted tables（简称SST）
Sorted table（.sst）文件存储了一序列按照key排序的entries，每个entry可以是key-value，或者是一个key的删除标记（marker）。（删除标记可以屏蔽掉先前sst文件中保存的较旧的数据，即如果一个key被标记为删除，那么先前的sst文件中关于此key的数据，将不会被read到）
Sorted tables按照层次（level）进行组织，由log文件生成的SST将会放置在一个特殊的young level中--即level-0，当young level中SST文件的个数超过一个阀值（4个），这些young文件将会与level-1中的那些有数据重叠的文件合并，并生成一序列新的level-1文件（每个新文件大小位2M）。
备注：“重叠”意义为key区间在两个文件中都存在。keys在SST文件中保存是严格排序的。
young level中的文件可能包含重叠的keys，不过其他level中的SST文件只会包含不同的“非重叠”的keys区间。假如level-L，其中L >= 1，当level-L中SST文件的总大小达到(10^L)MB时（例如level-1位10MB，level-2位100MB），那么level-L中的一个文件，将会和level-(L+1)中那些有keys重叠（覆盖）的文件merged，并生成一组新的level-(L+1)文件。这写merge，只通过批量的文件读写操作，即可将最新的updates数据从young level迁移到最高的level。
Manifest（清单）
manifest文件中列举了构成每个level的SST文件列表，以及相应的key区间，还包括一些重要的metadata。当database被reopened时，都会创建一个新的manifest文件（文件命中包含一个新的number序列号）。manifest文件的格式像log，“serving data”的变更（比如SST文件的创建、删除）操作都会被append到此log中。
Current
CURRENT文件是一个简单的文本文件，保存了当前最新的manifest文件的名称。
其他：略
2、Level 0
当log文件的尺寸增长到一定的大小（默认1M）：
3、Compactions
当level-L的尺寸达到了它的限制，我们将使用一个后台线程对它进行Compaction。压缩时，将会从level-L中选择一个文件，同时选择level-(L+1)中所有与此文件key有重叠的文件。如果level-L中一个文件只与level-(L+1)中某个文件的一部分重叠，那么level-(L+1)中的此文件作为压缩时的输入，在压缩结束后，此文件将被抛弃。不过，level-0比较特殊（文件中的keys可能互相重叠），对于level-0到level-1的压缩我们需要特殊处理：level-0中文件中互相重叠的话，那么将可能一次选择多个level-0的文件作为输入。
压缩将选择的文件内容重新输出到一序列新的level-(L+1)文件中（多路合并），当每个输出文件达到2M时将会切换一个新的文件，或者当新输出的文件中key区间覆盖了level-(L+2)中多于10个文件时，也会切换生成新文件；第二个规则保证此后level-(L+1)的压缩时无需选择太多的文件。
当level-(L+1)中的新文件加入到“serving state”时，那么旧的文件将会被删除（包括level-L和level-(L+1)）。
压缩时，将会抛弃那些“overwritten”的值；如果遇到删除标记，且对应的key在更高的level中不存在，也会直接抛弃。
Timing
level-0将会读取4个1M的文件（每个1M，level-0最多4个文件），最坏的情况是读取level-1的所有文件（10M），即我们读写各10MB。
和level-0不同，对于其他level-L，我们将读取2M的一个文件，最坏的情况是它与level-(L+1)中12文件有重叠（10个文件，同时还有2个处于边界的文件）；那么一次压缩将读写26MB数据。假定磁盘IO速率位100M/S，那么一次压缩耗时大约0.5秒。
如果我们对磁盘速率受限，比如10M/S，那么压缩可能耗时达到5秒。
文件个数
每个SST文件的大小为2M，事实上我们可以通过增大此值，来减少文件的总数，不过这会导致压缩更加耗时（读取的文件尺寸更大，磁盘密集操作）；另外，我们可以将不同的文件放在多个目录中。
4、数据恢复
1）从CURRENT中读取最新的manifest文件的名字。
2）读取manifest文件。
3）清理那么过期的文件。
4）我们可以打开所有的SST文件，不过通常lazy更好。
5）将log存留文件转存成新的level-0中的SST文件。
6）引导write操作到新的log文件中。
7）回收垃圾文件。
每次压缩和recovery操作后，将会调用DeleteObsoleteFiles()：从database中查询出所有的file的名字，然后将当前log文件之外的其他log文件全出删除，删除那些所有level中都不包含的、以及压缩操作没有引用的SST文件。
二、使用
leveldb为一个本地化的K-V存储数据库，设计思想类似于Bigtable，将key按照顺序在底层文件中存储，同时为了加快读取操作，内存中有一个memtable来缓存数据。
根据leveldb官网的性能基准测试，我们大概得出其特性：
1）leveldb的顺序读（遍历）的效率极高，几乎接近文件系统的文件顺序读。比BTree数据库要快多倍。
2）其随机读性能较高，但和顺序读仍有几个量级上的差距。leveldb的随机读，和基于BTree的数据库仍有较大差距。（个人亲测，其随机读的效率并不像官网所说的如此之高，可能与cache的配置有关）随机读，要比BTree慢上一倍左右。
3）顺序写，性能极高（无强制sync），受限于磁盘速率；随机写，性能稍差，不过性能相对于其他DB而言，仍有极大的优势。无论是顺序写还是随机写，性能都比BTree要快多倍。
4）leveldb为K-V存储结构，字节存储。属于NoSql数据库的一种，不支持事务，只能通过KEY查询数据；支持批量读写操作。
5）leveldb中key和value数据尺寸不能太大，在KB级别，如果存储较大的key或者value，将对leveld的读写性能都有较大的影响。
因为leveldb本身尚不具备“分布式”集群架构能力，所以，我们将有限的数据基于leveldb存储（受限于本地磁盘）。
案例推演：
1）leveldb具备“cache + 磁盘持久存储”特性，且不支持RPC调用，那么leveldb需要和application部署在同一宿主机器上。类似于“嵌入式”K-V存储系统。
2）如果存储数据较少，3~5G，且“读写比”（R:W）较高，我们可以让leveldb作为本地cache来使用，比如Guava cache + leveldb，这种结合，可以实现类似于轻量级redis。即作为本地缓存使用。
3）如果数据较多，通常为“顺序读”或者“顺序写”，我们可以将leveldb作为Hadoop HDFS的“微缩版”，可以用来缓存高峰期的消息、日志存储的缓冲区。比如我们将用户操作日志暂且存储在leveldb中，而不是直接将日志发送给remote端的Hadoop（因为每次都直接调用RPC，将会对系统的吞吐能力带来极大的影响），而是将这些频繁写入的日志数据存储在本地的leveldb中，然后使用后台线程以“均衡”的速度发送出去。起到了“Flow Control”（流量控制）的作用。
其中ActiveMQ即采用leveldb作为底层的消息数据存储，性能和容错能力很强。
三、API简析（JAVA版）
原生leveldb是基于C++开发，java语言无法直接使用；iq80对leveldb使用JAVA语言进行了“逐句”重开发，经过很多大型项目的验证（比如ActiveMQ），iq80开发的JAVA版leveldb在性能上损失极少（10%）。对于JAVA开发人员来说，我们直接使用即可，无需额外的安装其他lib。
1、pom.xml
<dependency> <groupId>org.iq80.leveldb</groupId> <artifactId>leveldb</artifactId> <version>0.7</version> </dependency> <dependency> <groupId>org.iq80.leveldb</groupId> <artifactId>leveldb-api</artifactId> <version>0.7</version> </dependency>
2、代码样例
boolean cleanup = true;
Charset charset = Charset.forName("utf-8");
String path = "/data/leveldb";
//init
DBFactory factory = Iq80DBFactory.factory;
File dir = new File(path);
//如果数据不需要reload，则每次重启，尝试清理磁盘中path下的旧数据。
if(cleanup) {
factory.destroy(dir,null);//清除文件夹内的所有文件。
}
Options options = new Options().createIfMissing(true);
//重新open新的db
DB db = factory.open(dir,options);
//write
db.put("key-01".getBytes(charset),"value-01".getBytes(charset));
//write后立即进行磁盘同步写
WriteOptions writeOptions = new WriteOptions().sync(true);//线程安全
db.put("key-02".getBytes(charset),"value-02".getBytes(charset),writeOptions);
//batch write；
WriteBatch writeBatch = db.createWriteBatch();
writeBatch.put("key-03".getBytes(charset),"value-03".getBytes(charset));
writeBatch.put("key-04".getBytes(charset),"value-04".getBytes(charset));
writeBatch.delete("key-01".getBytes(charset));
db.write(writeBatch);
writeBatch.close();
//read
byte[] bv = db.get("key-02".getBytes(charset));
if(bv != null && bv.length > 0) {
String value = new String(bv,charset);
System.out.println(value);
}
//iterator，遍历，顺序读
//读取当前snapshot，快照，读取期间数据的变更，不会反应出来
Snapshot snapshot = db.getSnapshot();
//读选项
ReadOptions readOptions = new ReadOptions();
readOptions.fillCache(false);//遍历中swap出来的数据，不应该保存在memtable中。
readOptions.snapshot(snapshot);//默认snapshot为当前。
DBIterator iterator = db.iterator(readOptions);
while (iterator.hasNext()) {
Map.Entry<byte[],byte[]> item = iterator.next();
String key = new String(item.getKey(),charset);
String value = new String(item.getValue(),charset);//null,check.
System.out.println(key + ":" + value);
}
iterator.close();//must be
//delete
db.delete("key-01".getBytes(charset));
//compaction，手动
db.compactRange("key-".getBytes(charset),null);
//
db.close();
参考文献：
1、LevelDB实现原理：http://leveldb.googlecode.com/git-history/1.17/doc/impl.html
2、LevelDB性能测试：http://leveldb.googlecode.com/git-history/1.17/doc/benchmark.html?r=1.17