理解leveldb

leveldb提供一个key value的持久化单机存储功能。
key value对是以用户自定义的比较函数来对key排序存储的。

打开数据库

leveldb用文件系统的一个文件目录来对应一个数据库。数据库所有的内存存放在对应的文件目录下。
下面是一个打开leveldb数据库的例子。

#include <cassert>
#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());
...

如果想数据库存在则报错，可以通过下面的代码来实现

options.error_if_exists = true;

关闭数据库

delete db;

读写

数据库提供一下操作：

• put
• get
• delete

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);

批量

一个事务需要先del key1然后update key2，如果进程在del key1后退出进程，那会导致业务不完整。
这时可以通过批量来解决

#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);
}

批量操作除了可以提供事务性功能，还可以加速写入数据库的性能

同步写

默认写是异步的。write在把消息写入了操作系统则马上返回。操作系统在一定时间后会把数据写入磁盘。
可以开启同步写，通过设置sync=true。这时每次write都会等待操作系统把数据写入磁盘后才返回。

leveldb::WriteOptions write_options;
write_options.sync = true;
db->Put(write_options, ...);

异步写通常会比同步写快1千倍。
异步写只有在操作系统崩溃活着重启的时候才会丢失最后若干条数据；进程的崩溃是不会丢失数据的。

并发

一个数据库只能被一个进程打开。leveldb通过操作系统的文件锁来防止多个进程同时打开一个数据库。
在一个进程内，相同的DB对象可以被多个线程共享。对于put get del不需要额外加锁来控制；但是对于其他的一些API，例如WriteBatch/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;

下面的例子展示了如果遍历start:end

for (it->Seek(start);
   it->Valid() && it->key().ToString() < limit;
   it->Next()) {
  ...
}

下面的例子展示了从后往前遍历

for (it->SeekToLast(); it->Valid(); it->Prev()) {
  ...
}

快照

快照提供一个一致性的只读视图给用户使用。
ReadOptions::snapshot非空则返回一个特定状态下的视图
ReadOptions::snapshot为空，将会读当前状态下的数据。

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);

slice

slice是leveldb的字符串类型。它包含了长度和bytes。
上面的it->key(); it->value()都是slice类型。
数据库返回slice可以避免字符串拷贝。

下面展示了slice和string的转换方法：

std::string str("world");
leveldb::Slice s2 = str;

leveldb::Slice s1 = "hello";
std::string str = s1.ToString();

比较器

数据库是以key为排序来存储的，key的排序规则可以自定义
例子如下：

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);
...

向前兼容

在调用leveldb::DB::Open时，如果发现比较器和key的格式不匹配，会失败。
所以为了让比较器可以更新，可以通过在key引入版本信息，并在比较器中加入版本兼容代码，来保证向前兼容

性能

可以通过以下方式来提高数据库操作的性能

block size 块大小

数据库是以块为单位来存储数据的。默认的块大小是4k。当应用程序多以扫描或者批量等方式操作，更大的块会性能更好；当应用以随机读，读小范围的值，则更小的块会性能更好。
小于1k或者大于几mb是不推荐的。数据块的压缩在大块的时候会更优

压缩

每一个数据块在写入磁盘前都会先压缩。默认是打开压缩的，因为压缩算法很快。
在很少的一些情况，应用会关闭压缩来提高性能，但只有压测发现关闭压缩的确会提高性能时才关闭压缩

leveldb::Options options;
options.compression = leveldb::kNoCompression;
... leveldb::DB::Open(options, name, ...) ....

缓存

如果不设置缓存，数据的内存是存放在一系列文件中的，每个文件存储一系列压缩的块。
通过设置缓存，可以在内存中存储经常被使用的key value。

#include "leveldb/cache.h"

leveldb::Options options;
options.block_cache = leveldb::NewLRUCache(100 * 1048576);  // 100MB cache
leveldb::DB* db;
leveldb::DB::Open(options, name, &db);
... use the db ...
delete db
delete options.block_cache;

对于批量操作，为了避免这些批量数据污染缓存，可以通过屏蔽缓存来进行操作

leveldb::ReadOptions options;
options.fill_cache = false;
leveldb::Iterator* it = db->NewIterator(options);
for (it->SeekToFirst(); it->Valid(); it->Next()) {
  ...
}
delete it;

key的布局

由于数据是以块来存储的，我们希望对于关系紧密的key可以放在同一个块或者附近。
例如我们要在leveldb上构建一个存储系统，结构如下：

filename -> permission-bits, length, list of file_block_ids
file_block_id -> data

filename希望可以存放在一起
file_block_id可以存放在别处
这时我们可以通过在filename前面加上相同的前缀；id前加上另外一个前缀。这样在数据库存储的时候，就可以做到隔离存储了。

bloom过滤器

数据是存放在磁盘中的。当调用get()可能会发生数次的磁盘调用，filter_policy可以减少磁盘调用的发生次数。

leveldb::Options options;
options.filter_policy = NewBloomFilterPolicy(10);
leveldb::DB* db;
leveldb::DB::Open(options, "/tmp/testdb", &db);
... use the database ...
delete db;
delete options.filter_policy;

Checksums

Checksums可以用来检验数据是否正确存储

• ReadOptions::verify_checksums
  在read调用的时候，检验数据的一致性
• Options::paranoid_checks
  在打开数据库的时候，检验数据的一致性

Approximate Sizes

GetApproximateSizes可以获取key占系统存储的大致大小

leveldb::Range ranges[2];
ranges[0] = leveldb::Range("a", "c");
ranges[1] = leveldb::Range("x", "z");
uint64_t sizes[2];
db->GetApproximateSizes(ranges, 2, sizes);

Env

leveldb发出的所有操作系统调用，可以通过leveldb::Env来路由。
例如应用程序可能会在文件IO中加入人为延迟，来限制level对系统的其他应用的影响

class SlowEnv : public leveldb::Env {
  ... implementation of the Env interface ...
};

SlowEnv env;
leveldb::Options options;
options.env = &env;
Status s = leveldb::DB::Open(options, ...);

实现原理

文件

文件是以LSM结构来存储的。

log 文件

每次发生update，都会追加log文件。
当log达到预定的大小4mb，它会生成一个排序的table，并生成一个新的log文件
内存中会保持一个当前log的有序表memtable（以key为排序）

有序表

有序表存储以key为排序的实体，实体要么是value，要么是标志key被del。

有序表被分成不同的level，level-0是最年轻的数据，当有序表的大小达到预定值，level内的块会被合并，并生成老一代的块，例如level-1

一般的，level-0 -> level-1: 2m; level-1 -> level-2: 10m; level-2 -> level-3: 100m

manifest

manifest文件包含了某一个level下的key的范围和一些重要的元数据。

文件数

2m的文件大小，很容易产生大量的文件。为了减少文件数，可以使用更大的块大小，代价是更多的突发压缩。

恢复

• 从CURRENT中找到最新的manifest文件
• 从manifest中读取文件命名
• 清理旧文件
• 打开所有的sstable
• 把日志块转换成sstable
• 开始接收新写入

文件回收

在每次压缩结束和恢复结束时进行文件回收。
它会删除不是当前日志的日志文件；删除未被引用的文件

性能对比

测试数据

单位：ops/sec

条件	行为	LevelDB	Kyoto TreeDB	SQLite3
基准测试	顺序读	4,030,000	1,010,000	383,000
基准测试	随机读	129,000	151,000	134,000
基准测试	顺序写	779,000	342,000	48,600
基准测试	随机写	129,000	151,000	134,000
同步写	顺序写	100	7	88
同步写	随机写	100	8	88
不压缩	顺序读	4,880,000	1,230,000	383,000
不压缩	随机读	149,000	175,000	134,000
不压缩	顺序写	594,000	485,000	48,600
不压缩	随机写	135,000	159,000	9,860
cache	顺序读	5,210,000	1,070,000	609,000
cache	随机读	190,000	463,000	186,000
cache	顺序写	812,000	321,000	48,500
cache	随机写	355,000	284,000	9,670

引用:

• https://github.com/google/leveldb/blob/main/doc/index.md
• https://github.com/google/leveldb/blob/main/doc/impl.md