作者： Jeff Dean, Sanjay Ghemawat
原文： http://leveldb.googlecode.com/svn/trunk/doc/index.html
译者： phylips@bmy 2011-8-16
译文： http://duanple.blog.163.com/blog/static/70971767201171705113636/
LevelDB 库提供了一种永久性的 key value 存储。 Key 和 value 都是任意的字节序列。在这个 key value 存储系统中， key 按照用户声明的比较函数有序排列。
打开一个数据库
一个 LevelDB 数据库有一个文件系统目录名称与之关联。该数据库的所有内容都存储在该目录下。下面的例子展示了如何打开一个数据库，或者如何在必要的时候创建一个：
#include <assert>
#include "leveldb/db.h"
leveldb::DB* db;
leveldb::Options options;
options.create_if_missing = true;
leveldb::Status status = leveldb::DB::Open(options, "/tmp/testdb", &db);
assert(status.ok());
...
如果你想在数据库已经存在的情况下，让上面的代码产生一个错误，需要再 Open 调用之前加入如下一行：
options.error_if_exists = true;
状态 (status)
你可能注意到了上面的 leveldb::Status 数据类型。在 LevelDB 中绝大多数可能出错的函数调用都会返回这种类型的值。也可以在出错的情况下，打印出一些错误提示信息
leveldb::Status s = ...;
if (!s.ok()) cerr << s.ToString() << endl;
关闭数据库
在完成一个数据库的处理之后，直接删除该数据库对象即可。
... open the db as described above ...
... do something with db ...
delete db;
读操作与写操作
数据库提供了 Put, Delete, 和 Get 方法来对数据库进行修改 / 查询。比如下面的代码会将存储在 key1 下面的值存到 key2 下面。
std::string value;
leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value);
if (s.ok()) s = db->Put(leveldb::WriteOptions(), key2, value);
if (s.ok()) s = db->Delete(leveldb::WriteOptions(), key1);
原子性更新
需要注意的是。在上面的操作中，如果在 Put key2 之后， delete key1 之前，进程死掉了，那么相同的 value 值就可能会存储在多个 key 值下面。可以通过使用 WriteBatch 类原子性的执行一组更新操作，来避免这样的问题：
#include "leveldb/write_batch.h"
...
std::string value;
leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value);
if (s.ok()) {
leveldb::WriteBatch batch;
batch.Delete(key1);
batch.Put(key2, value);
s = db->Write(leveldb::WriteOptions(), &batch);
}
WriteBatch
会持有对数据库的一系列更改操作，这些操作会按照它们加入顺序被执行。除了提供这种原子性的保证外， WriteBatch 还可以通过将多个更新放到同一个 batch 里，在存在大量更新操作时，加速它们的执行。
同步性的写操作
默认情况下，对于 leveldb 的写操作是异步的：在将写操作从进程交给操作系统之后它就会返回。从操作系统内存空间到底层永久性存储设备之间的传输是异步进行的。可以通过打开 sync flag 来，使得一个写操作要等到数据真正的写入到永久性存储后才返回。 ( 在 Posix 系统中，这是通过在写操作返回之前调用 fsync(...) 或者 fdatasync(...) 或者是 msync(..., MS_SYNC)) 来实现的 )
leveldb::WriteOptions write_options;
write_options.sync = true;
db->Put(write_options, ...);
异步性的写操作通常要比同步性的快 1000 倍。它的缺点是，当机器 crash 掉的时候，可能会丢失最后的一些更新。需要注意的是，如果仅仅是写操作进程的 crash( 比如，不是 reboot) 并不会引起任何的丢失，因为即使 sync=false ，一个更新操作在完成之前必须要把数据从应用程序空间传到系统空间。
异步性的写操作通常都可以安全的使用。比如，在将大量数据加载到数据库中时，你可以通过在 crash 之后重新加载一遍来处理那些丢失的更新。也可以采用一种混合模式，比如每隔 N 个写操作，进行一次同步，这样在 crash 发生时，只需要从最后一次同步的地方开始重新执行即可 ( 只需要让同步性的写操作更新一个重启时从何处开始的标记即可 ) 。
WriteBatch 也可以为异步性的写操作的提供一个改进。多个更新操作可以放到同一个 WriteBatch ，然后使用一个同步性的写操作 ( 比如令 write_options.sync=true) 。这样额外的同步开销就可以分摊到多个写操作中。
并发
同一时刻只能有一个进程打开数据库。为了防止误用， LevelDB 实现会从操作系统申请一把锁。在一个进程内部，同一个 leveldb::DB 对象可以安全地被多个并发线程共享。比如，多个线程可以在同一个数据库中写数据，获取迭代器，执行 Get 调用而不需要额外的同步 (LevelDB 实现会自动的完成所需的同步 ) 。然而其他对象 ( 比如迭代器和 WriteBatch) 可能需要额外的同步。如果两个线程共享相同的此类对象，它们必须使用自己的锁机制来保护对此类对象的访问。
迭代
下面的例子用来说明如何打印出数据库中的所有 key value 对。
leveldb::Iterator* it = db->NewIterator(leveldb::ReadOptions());
for (it->SeekToFirst(); it->Valid(); it->Next()) {
cout << it->key().ToString() << ": " << it->value().ToString() << endl;
}
assert(it->status().ok());
// Check for any errors found during the scan
delete it;
下面的例子说明如何只处理那些给定 key 值边界 [start,limit) 内的数据 :
for (it->Seek(start);
it->Valid() && it->key().ToString() < limit;
it->Next()) {
...
}
也可以以逆序方式进行处理 ( 可能比顺序处理慢些 )
for (it->SeekToLast(); it->Valid(); it->Prev()) {
...
}
Snapshots
Snapshots 提供了关于整个 key-value 存储状态的一致性的只读视图。可以通过设置 ReadOptions::snapshot 为非空值，来指定从数据库的某个特殊的版本中读取。如果它的值为空，则默认读取当前状态。 Snapshots 通常通过 DB::GetSnapshot() 方法创建：
leveldb::ReadOptions options;
options.snapshot = db->GetSnapshot();
... apply some updates to db ...
leveldb::Iterator* iter = db->NewIterator(options);
... read using iter to view the state when the snapshot was created ...
delete iter;
db->ReleaseSnapshot(options.snapshot);
需要注意，在一个 snapshot 不再需要的时候，必须通过 DB::ReleaseSnapshot 接口来显示的进行释放 。这样就可以让底层实现丢弃掉那些为支持对该 snapshot 的读取操作所维护的一些状态数据。一个写操作也可以返回一个应用了一系列特殊的更新操作集合后的数据库状态的 snapshot:
leveldb::Snapshot* snapshot;
leveldb::WriteOptions write_options;
write_options.post_write_snapshot = &snapshot;
leveldb::Status status = db->Write(write_options, ...);
... perform other mutations to db ...
leveldb::ReadOptions read_options;
read_options.snapshot = snapshot;
leveldb::Iterator* iter = db->NewIterator(read_options);
... read as of the state just after the Write call returned ...
delete iter;
db->ReleaseSnapshot(snapshot);
Slice
上面 it->key() 和 it->value() 调用的返回值都是 leveldb::Slice 类型。 Slice 是一个包含了长度及指向外部字节数组的指针的简单结构。返回 Slice 比返回一个 std::string 类型开销要低，因为这种我们就不必对那些大的 key 和 value 值进行拷贝。另外， LevelDB 方法也不能返回以 null 结尾的 C 风格字符串，因为它的 key 和 value 都允许包含 '\0' 。
C++ string 和以 null 结尾的 C 风格字符串可以简单的转化为一个 Slice 类型：
leveldb::Slice s1 = "hello";
std::string str("world");
leveldb::Slice s2 = str;
一个 Slice 类型也可以简单的转化为一个 C++ string 类型：
std::string str = s1.ToString();
assert(str == std::string("hello"));
在使用 Slices 需要格外小心，因为它依赖于调用者去保证 Slice 所指向的外部字节数组的有效性 。比如下面代码的就是有问题的：
leveldb::Slice slice;
if (...) {
std::string str = ...;
slice = str;
}
Use(slice);
因为 if 语句的作用域已经结束， str 将会被析构，这样 slice 指向的空间就不存在了。
比较器
前面的那些例子为 key 使用了默认的排序函数，会按字典序进行排序。你可以在打开数据库的时候提供一个自定义的比较器。比如假设数据库的 key 是由两个数组成，我们首先按照第一个数进行排序，如果相等再比较第二个。首先需要定义一个满足如下规则的 leveldb::Comparator 的子类：
class TwoPartComparator : public leveldb::Comparator {
public:
// Three-way comparison function:
// if a < b: negative result
// if a > b: positive result
// else: zero result
int Compare(const leveldb::Slice& a, const leveldb::Slice& b) const {
int a1, a2, b1, b2;
ParseKey(a, &a1, &a2);
ParseKey(b, &b1, &b2);
if (a1 < b1) return -1;
if (a1 > b1) return +1;
if (a2 < b2) return -1;
if (a2 > b2) return +1;
return 0;
}
// Ignore the following methods for now:
const char* Name() const { return "TwoPartComparator"; }
void FindShortestSeparator(std::string*, const leveldb::Slice&) const { }
void FindShortSuccessor(std::string*) const { }
};
现在使用定制的比较器，创建一个数据库 :
TwoPartComparator cmp;
leveldb::DB* db;
leveldb::Options options;
options.create_if_missing = true;
options.comparator = &cmp;
leveldb::Status status = leveldb::DB::Open(options, "/tmp/testdb", &db);
向后兼容 (Backwards compatibility)
比较器的 Name 方法的返回结果会在数据库创建时与之绑定，同时在后面每次打开数据库时都会进行检查。如果返回名称发生了变化，那么 leveldb::DB::Open 调用会失败。因此，当且仅当新的 key 格式及比较函数与现有数据库不兼容的时候才需要去改变它，同时此时丢弃掉所有现存数据库的内容也应是可以接受的。
你也可以有计划的逐步改变 key 的格式。比如，可以在每个 key 的后面存储一个版本号 ( 对于大多数的情况一个字节就足够了 ) 。当切换到一种新的 key 格式 ( 比如，为 TwoPartComparator 处理的 key 增加一个可选的第三块内容 ) ， (a) 保持相同的比较器名称 (b) 新的 key 增加版本号 (c) 改变比较器函数，使得它可以通过 key 里面的版本号来决定如何解释它们。
性能
可以通过改变 include/leveldb/options.h 里的默认值来对性能进行调整优化。
块大小
LevelDB 会将相邻的 key 值组合在一块放到同一个 block 中，这样的一个 block 是与永久性存储设备进行传输的基本单元。默认的块大小大概是 4096 个未压缩字节。那些经常需要扫描整个数据库内容的应用可能希望增大这个值。那些读取大量小的 value 值的应用，如果可以得到性能上的改进，可能倾向于将这个值设得更小。如果这个值过大或过小，也不会有太多好处，比如小于 1KB 或者大于数 MB 的情况下。需要指出的是，对于那些大的 block 大小，压缩可能会更有效。
压缩
每个块被写入永久性存储设备之前会被单独压缩。由于默认的压缩方法速度很快，同时对于那些很难压缩的数据它会自动的关闭，因此默认情况下压缩就是开启的。只有在很特殊的情况下，应用才会去关闭压缩，但是只有当通过 benchmarks 能看到性能提升时才应该这样做。
leveldb::Options options;
options.compression = leveldb::kNoCompression;
... leveldb::DB::Open(options, name, ...) ....
缓存
数据库内容被存储在文件系统的一系列文件中，每个文件保存了一系列的压缩的 blocks 。如果 options.cache 值是非 NULL 的，这时那些已经用过的未压缩的块内容会被缓存。
#include "leveldb/cache.h"
leveldb::Options options;
options.cache = leveldb::NewLRUCache(100 * 1048576); // 100MB cache
leveldb::DB* db;
leveldb::DB::Open(options, name, &db);
... use the db ...
delete db
delete options.cache;
需要说明的是，缓存里存放的是未压缩数据，因此它的大小是应用级别的数据大小，而不是压缩后的 。 ( 对于已压缩的 blocks 的缓存交给操作系统 buffer 去缓存，或者是由客户端提供自己的 Env 实现来完成 ) 。 在执行大的读操作的时候，应用程序可能希望不使用缓存，这样就可以避免这些大数据的读操作消耗掉大量的缓存 。一个针对迭代器的 option 参数可以实现这个目的：
leveldb::ReadOptions options;
options.fill_cache = false;
leveldb::Iterator* it = db->NewIterator(options);
for (it->SeekToFirst(); it->Valid(); it->Next()) {
...
}
Key 的 layout
需要注意的是磁盘传输和缓存的单位是 block 。相邻的 key( 根据数据库排序结果 ) 通常会被放到同一个 block 里。因此应用程序可以通过将那些相邻近的 key 值放到一块进行访问，将那些很少被使用的 key 值放到一个独立的 key 值空间内。
比如，假设在 LevelDB 之上实现一个简单的文件系统。通常需要存储的记录数据如下：
filename -> permission-bits, length, list of file_block_ids
file_block_id -> data
我们可以为 filename 添加个前缀 ( 比如 '/') ，为 file_block_id 加上另一个 ( 比如 '0') ，这样对于文件元数据的扫描就不不需要去获取及缓存大量的文件内容数据。
Checksums
LevelDB 会为它存储在文件系统中的所有数据生成相应的 checksums 。通常有两种方式来控制对 checksums 进行何种程度的验证： ReadOptions::verify_checksums 设为 true ，会强制对从文件系统中读出的所有数据都进行 checksum 验证。默认情况下，不进行验证。 Options::paranoid_checks 可以在打开数据库之前将其设为 true ，这会使得 数据库底层实现只要检测到内部数据错误时就会产生一个 error 。 Error 产生的时机取决于数据库的哪个部分出了问题，比如可能在数据库打开时或者是在后面执行某个数据库操作时。默认情况下， paranoid checking 是关闭的，这样即使数据库的某些永久性存储出了问题，它仍然也是可以使用的。 如果数据库被破坏了 ( 可能是因为打开了 paranoid checking 而导致它无法打开 ) ， leveldb::RepairDB 函数可以用来尽量地对数据进行恢复。
Approximate Sizes
GetApproximateSizes 方法可以被用来得到一个或多个 key range 所占用的文件系统空间的近似大小。
leveldb::Range ranges[2];
ranges[0] = leveldb::Range("a", "c");
ranges[1] = leveldb::Range("x", "z");
uint64_t sizes[2];
leveldb::Status s = db->GetApproximateSizes(ranges, 2, sizes);
上面的调用，会设置 sizes[0] 的值为 range [a..c) 所占用的文件系统空间的近似大小， sizes[1] 的值为 range [x..z) 所占用的文件系统空间的近似大小。
Environment
所有由 LevelDB 实现产生的文件操作 ( 及其他的操作系统调用 ) 都是通过 leveldb::Env 对象统一管理。为了进行更好的控制，某些客户端可能希望提供自己的 Env 实现。比如应用程序可能希望在文件 IO 中引入自定义的延时来限制 LevelDB 对系统其他动作产生的影响。
class SlowEnv : public leveldb::Env {
.. implementation of the Env interface ...
};
SlowEnv env;
leveldb::Options options;
options.env = &env;
Status s = leveldb::DB::Open(options, ...);
移植性 (Porting)
通过提供一个 leveldb/port/port.h 中的 types/methods/functions 的平台描述实现，就可以将 LevelDB 移植到一个新平台上。具体细节可以参考： leveldb/port/port_example.h
下面是运行 db_bench 程序得到的性能测试报告。结果有些杂乱，但是足以说明问题。
测试环境
使用一个具有百万条记录的数据库，每条记录有一个 16 字节的 key 及 100 字节的 value 。对于 values 值压缩后可能大概只有原始大小的一半。
LevelDB: version 1.1
Date: Sun May 1 12:11:26 2011
CPU: 4 x Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz
CPUCache: 4096 KB
Keys: 16 bytes each
Values: 100 bytes each (50 bytes after compression)
Entries: 1000000
Raw Size: 110.6 MB (estimated)
File Size: 62.9 MB (estimated)
写性能
"fill" benchmarks 会以顺序地或者随机的方式创建一个全新的数据库。 "fillsync" benchmark 的每次操作都会将数据从操作系统 flush 到磁盘；其他的写操作会允许数据在操作系统 buffer 中停留一段时间。 "overwrite" benchmark 会进行随机的写入以更新数据库中现有的 key 值。
fillseq : 1.765 micros/op; 62.7 MB/s
fillsync : 268.409 micros/op; 0.4 MB/s (10000 ops)
fillrandom : 2.460 micros/op; 45.0 MB/s
overwrite : 2.380 micros/op; 46.5 MB/s
上面的一次” op ”意味着对于单个 key/value 对的一次写人。比如随机写 benchmark 每秒大概可以近似达到 400,000 写操作。
每个 "fillsync" 操作花费 (0.3ms) 远小于一次磁盘 seek 操作 ( 通常需要 10ms) 。我们怀疑这是因为硬盘本身会将这些更新缓存到它的 memory 里，在数据真正写入到扇区之前就做出了响应。这种情况下的安全性取决于硬盘在电力供应出问题时是否有足够的电力去保存它的 memory 中的数据。
读性能
我们列出了正向及反向顺序读的性能，以及随机查找的性能。需要注意的是，由 benchmark 创建的数据库是很小的。因此这个报告只是刻画了工作集可以载入到内存时的 LevelDB 的性能。对于那些未命中操作系统缓存的单片数据读取操作来说，开销主要是由为从磁盘获取数据所需进行的一次或两次磁盘 seek 操作造成的。而写操作性能几乎不受工作集能否载入到内存的影响。
readrandom : 16.677 micros/op; ( 每秒大概 60,000 reads)
readseq : 0.476 micros/op; 232.3 MB/s
readreverse : 0.724 micros/op; 152.9 MB/s
LevelDB 为提高读性能会在后台压缩它的底层存储数据。上面的测试是在进行过大量的随机写操作之后立即进行的。在进行过 compactions( 通常是自动触发的 ) 再进行测试结果会更好些。
readrandom : 11.602 micros/op; ( 每秒大概 85,000 reads)
readseq : 0.423 micros/op; 261.8 MB/s
readreverse : 0.663 micros/op; 166.9 MB/s
某些读操作的高花费是由于从硬盘读取出的 blocks 的重复解压导致的。如果我们可以为 LevelDB 提供足够的缓存使得它可以将所有的未压缩块放入内存，那么读性能会有更大地改善：
readrandom : 9.775 micros/op; ( 每秒大概 100,000 reads before compaction)
readrandom : 5.215 micros/op; ( 每秒大概 190,000 reads after compaction)
其他信息
实现相关
Immutable table 文件格式
Log 文件格式
译考文献
http://leveldb.googlecode.com/svn/trunk/doc/index.html
http://code.google.com/p/leveldb/
