LevelDB 源码分析（三）：相关文档

栏目: 数据库 · 发布时间: 6年前

内容简介：LevelDB 源码分析（三）：相关文档

在 leveldb 源码目录的 doc 目录下有关于 leveldb 的一些文档，这篇文章是对 index.html 文件的翻译。

leveldb 库提供了一个持久化的 key-value 数据库。key 和 value 都是任意大小的字节数组。所有的 key 是根据用户指定的比较器有序的存储在 key-value 数据库中。

1. 打开数据库

每一个 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());
...

如果你想，当这个数据库已经存在时就报错，可以添加下面的一行内容到 leveldb::DB::Open 调用之前： 

options.error_if_exists = true;

2. Status

你也许已经注意到了上面的 leveldb::Status 类型，leveldb 上大多数会出错的函数会返回这个类型的值。你可以检查这样的结果是否正确，还可以打印相应的出错信息： 

leveldb::Status s = ...;
if (!s.ok()) cerr << s.ToString() << endl;

3. 关闭数据库

当你完成一个数据库操作的时候，只要删除这个数据库的对象就行了。例如：

... open the db as described above ...
... do something with db ...
delete db;

4. 读写操作

数据库提供了 Put ， Delete 和 Get 方法来修改(查询)数据库。例如，下面的代码把 key1 对应的 value 值存到 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);

5. 原子更新

请注意，上面的例子中，如果进程在 puut key2 之后与 delete key1 之前死亡了，那么可能会存在多个 key 有相同的 value。可以利用 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 封装了对数据库的一系列的操作，这些批处理的操作会按一定的顺序去执行。注意到，我们在调用 Put 之前调用 Delete ，所以如果 key1 和 key2 相同，我们最终不回完全的丢弃这个 value 值。

除了原子性的优点外， WriteBatch 还可以通过将多个改变添加到相同的批处理中来加快批量更新的速度。

6. 同步写

默认情况下，对 leveldb 的每一个写都是异步的：把写操作从进程推送到操作系统后就返回。从操作系统内存到底层持久化存储的传输是异步的。 同步标志 可以为一个特定的写操作打开，使这个写操作直到数据被写入到持久化存储器中才返回。（在 Posix 系统上，这是通过在写操作返回前调用 fsync(...) 或 fdatasync(...) 或 msync(..., MS_SYNC) 来实现的。） 

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

异步写的速度通常是同步写的1000倍。异步写入的缺点是，系统的崩溃可能会导致最后的一些更新丢失。请注意，只是写过程(例如，不是重启)的崩溃不会导致任何的丢失，因为即使关闭了同步写，一个更新操作会在它被认为完成之前，从进程的内存推送到操作系统。

异步写入通常可以安全地使用。例如，当导入大量的数据到数据库时，你可以在崩溃后重启批处理导入程序来弥补丢失的更新。混合方案也是可能的，每N个写是同步的，在崩溃发生时，批处理导入程序只会在最后一个同步写在上一次的运行中完成之后被重启。（同步写可以更新一个崩溃后在哪里重启的标志。）

WriteBatch 提供了一个异步写的替代品。多个更新也许会被放在相同的 WriteBatch 上，并用同步写入(把 write_options.sync 设置为 true )一起执行。同步写入的额外开销将会平摊在批处理的所有写操作上。

7. 并发

一个数据库在同一时刻只能被一个进程打开。在 leveldb 的实现中，通过从操作系统获取锁来防止误用。在单线程中，相同的 leveldb:DB 对象可以被多个并发的线程安全地共享。即，不同的线程可以在不需要外部同步信号的情况下，在相同的数据库上写入或者读取迭代器或者调用Get（leveldb 的实现会自动地进行所需的同步）。然而，其他的对象(像迭代器和WriteBatch)也许需要外部同步。如果两个线程共享这样的一个对象，他们必须使用自己的锁协议保护地访问。更多详细信息，在公共头文件中提供。

8. 迭代

下面的例子演示了怎么打印数据库中所有的 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, limit) 范围内的 key：

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

你还可以逆序来处理记录。（警告：反向迭代可能会比向前迭代要慢一些。）

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

9. 快照

快照提供了整个 key-value 数据库状态的一致的只读的视图。 ReadOptions::snapshot 应该是非NULL的，表明一个读操作应该在一个特定的数据库状态的版本上进行。如果 ReadOptions::snapshot 是 NULL，读操作将会在当前状态的隐式快照上进行。

快照是由 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);

请注意，当一个快照不在被需要时，应该用 DB::ReleaseSnapshot 接口释放它。

10. Slice

上面 it->key() 和 it->value() 的返回值都是 leveldb::Slice 类型的实例。Slice 是一个简单的结构，包含一个长度和一个指向外部字节数组的指针。返回一个 Slice 比返回 std:string 更加方便，因为我们不需要去复制原始的大量的key和value的数据。此外，leveldb 的函数不返回 null 结尾的C风格的字符串，因为leveldb 的 key 和 value 的值允许包含 ‘\0’ 字节。

C++字符串和 null 结尾的C风格字符串很容易转换成Slice：

leveldb::Slice s1 = "hello";

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

Slice 也很容易转换回C++字符串：

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

使用 Slice 时应当小心，它是由调用者来确保 Slice 的指针指向的外部字节数组在 Slice 被使用时是不为空的。例如，

leveldb::Slice slice;
if (...) {
    std::string str = ...;
    slice = str;
}
Use(slice)

当 if 语句超出范围， str 将会被销毁， slice 的后备存储也会消失。

11. 比较器

前面的例子中对 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);
...

向下兼容性

比较器名字方法的结果在数据库被创建时就附着到数据库上了，在随后每一次打开数据库时都会检查。如果名字改变了， leveldb::DB::Open 的调用将会失败。因此，当且仅当新的key格式和比较函数与现有的数据库不兼容时，才改变名字。它确实会丢弃所有现有数据库的内容。

但是，你仍然可以随着时间的推移渐渐地按着前期的规划一点点地演化你的key的格式。例如，你可以在每个key的末尾存一个版本号(一个字节应该就可以满足大部分的用途)。如果你想切换一个新的key格式(例如，给key添加一个由 TwoPartComparator 产生的可选的第三部分)，(a)保持相同的比较器名称；(b)对新的key递增版本号；(c)改变比较器函数，因此使用key里面的版本号来决定怎么解释他们。

12. 性能

性能可以通过改变 include/leveldb/options.h 里定义的类型的默认值来调整。

Block size

leveldb 将相邻的key组织在一起放到相同的block中，这样的一个block也是与永久性存储器之间传输的单元。默认的block大小约为4096个未压缩的字节。对于经常需要批量扫描数据库内容的应用程序，希望能够增加block的大小。如果性能能够提升，对于经常需要对小的value进行大量读的应用程序，希望block比较小。使用低于1kB或者高于几兆的block并没有太多的改善。另外注意到，大的block会有利于压缩。

压缩

每个block在写入持久性存储器之前都会被单独压缩。压缩是在默认的情况下，因为默认的压缩方法很快，而且对于不可压缩的数据将自动禁用。在极少数情况下，应用程序会完全禁止压缩，但如果基准测试能够显示性能有提升的话，也只能这样做：

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

缓存

数据库的内容存储在文件系统的一组文件中，每个文件存储了压缩块的一个序列。如果 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;

注意，缓存保存着未压缩的数据，因此，它的大小应该与应用层数据大小相对应，没有任何的压缩的扣除。（压缩块的缓存是留给操作系统的缓冲区的，或者由客户端提供的自定义的 Env 实现。）

当进行批处理的读请求时，应用程序可能希望禁止缓存，这样批量读取的数据最终不会替代缓存里面的大部分内容。per-iterator 操作可以用来实现这个：

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

key的布局

注意，磁盘的传输单元和缓存的单元都是block。相邻的key(根据数据库的排序顺序)总是被放在相同的block中。因此，应用程序可以通过把一起访问的key放在相邻的位置和把频繁使用的key放在一个独立的区域来提高系统的性能。

例如，假设我们正在 leveldb 的顶层实现一个简单的文件系统。我们想要存储的记录的类型如下：

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

我们可能想给 filename key 添加一个字母(比如’/‘)的前缀，给 file_block_id key 添加一个不同的字母(比如’0’)的前缀，使扫描只是在元数据上进行，不强迫我们取出并缓存大量的文件内容。

Filter

由于 leveldb 数据在磁盘上的组织方式，一个 Get() 调用就有可能引起多次的磁盘读。可选的 FilterPolicy 机制能够大幅减少磁盘读的数量。 

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;

上面的代码将基于过滤策略的 Bloom filter 与数据库联系在一起。基于过滤的 Bloom filter 原理是，为每一个 key 在内存中保留一定数量的 bit 位(在当前情况下，每个key 10个bit，因为这是传给 NewBloomFilterPolicy 的参数)。这个过滤器大约会减少10倍的由 Get() 调用引起的磁盘读的数量。增加每个key的bit位，会减少更多的磁盘读，但是会增加内存使用。我们建议，那些工作集不适合在内存中的且需要大量随机读的应用程序设置一个过滤器。

如果你在使用一个自定义的比较器，你应该确保你正在使用的过滤策略跟你的比较器兼容。例如，假设一个比较器，在比较key时，忽略尾部的空格， NewBloomFilterPolicy 不能与这样的比较器一起使用。相反，应用程序应该提供一个自定义的过滤策略同样忽略尾部的空格，例如： 

class CustomFilterPolicy : public leveldb::FilterPolicy {
    private:
        FilterPolicy* builtin_policy_;
    public:
        CustomFilterPolicy() : builtin_policy_(NewBloomFilterPolicy(10)) { }
        ~CustomFilterPolicy() { delete builtin_policy_; }

        const char* Name() const { return "IgnoreTrailingSpacesFilter"; }

        void CreateFilter(const Slice* keys, int n, std::string* dst) const {
            // Use builtin bloom filter code after removing trailing spaces
            std::vector<Slice> trimmed(n);
            for (int i = 0; i < n; i++) {
                trimmed[i] = RemoveTrailingSpaces(keys[i]);
            }
            return builtin_policy_->CreateFilter(&trimmed[i], n, dst);
        }

        bool KeyMayMatch(const Slice& key, const Slice& filter) const {
            // Use builtin bloom filter code after removing trailing spaces
            return builtin_policy_->KeyMayMatch(RemoveTrailingSpaces(key), filter);
        }
};

更好的应用程序可以提供不使用 bloom filter 的过滤策略，但使用一些其他的机制来总结一组key。通过 leveldb/filter_policy.h 可以了解详细细节。

13. Checksums

leveldb 把 checksum 和存储在文件系统中的所有数据关联在一起。有提供对这些校验是如何积极地验证的两套独立的控制：

  • ReadOptions::verify_checksums 可以被设置为true，在一个特定的读操作上，强制地对从文件系统中读取的所有数据进行 checksum 的校验。默认情况下，没有这样的验证完成。
  • Options::paranoid_checks 可以在数据库打开之前设置为true，能够使数据库检测到内部错误的时候迅速报错。根据数据库的哪部分被破坏了，可以在数据库打开时或者随后的数据库操作中进行报错。默认情况下，paranoid checking 是关闭的，所以即使数据库的持久化存储已经被破坏了，它还能使用。

如果一个数据库被破坏了(当paranoid_checks关闭时也许还能打开)， leveldb::RepairDB 函数可以用于恢复尽可能多的数据。

14. Approximate Sizes

GetApproximateSizes 函数可以获得由一个或多个范围内的key使用的文件系统空间的字节的近似数量。 

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

上面的调用将会把 size[0] 设置为 [a..c) 范围内的key在文件系统空间上使用的近似的字节数量，把 size[1] 设置为 [x..z) 范围内的key所使用的近似的字节数量。

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

16. 移植

leveldb 可以通过提供由 leveldb/port/port.h 导出的 types/methods/functions 的平台特定的接口说明来将其移植到新的平台上。可以从 leveldb/port/port_example.h 中了解到更多细节。

此外，新的平台可能需要一个新的默认的 leveldb::Env 的实现。 leveldb/util/env_posix.h 可以作为一个例子。

17. 其他信息

关于 leveldb 实现的更多细节可以参考下面的文档：

  • Implementation notes
  • Format of an immutable Table file
  • Format of a log file

翻译如有不当之处，欢迎指正。


以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍
啊哈!算法

啊哈!算法

啊哈磊 / 人民邮电出版社 / 2014-6-1 / 45.00元

这不过是一本有趣的算法书而已。和别的算法书比较，如果硬要说它有什么特点的话，那就是你能看懂它。 这是一本充满智慧和趣味的算法入门书。没有枯燥的描述，没有难懂的公式，一切以实际应用为出发点， 通过幽默的语言配以可爱的插图来讲解算法。你更像是在阅读一个个轻松的小故事或是在玩一把趣味解谜 游戏，在轻松愉悦中便掌握算法精髓，感受算法之美。 本书中涉及到的数据结构有栈、队列、链表、树......一起来看看 《啊哈!算法》 这本书的介绍吧!

码农工具
在线进制转换器
在线进制转换器

各进制数互转换器

SHA 加密
SHA 加密

SHA 加密工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

  • New
  • 文章
  • 话题
  • 教程
    • 关注 码农网 公众号
    版权所有，保留一切权利！© 2018-2024 码农网 粤ICP备17054400号-3