是beansdb的一些资料整理和总结

转自这里 http://sunisdown.me/gobeansdb-jia-gou-she-ji.html

为什么要自己实现一套 k/v 存储

我在刚刚接手 GoBeansDB 的时候，想过这个问题。既然有那么多优秀的数据库系统，为什么豆瓣还需要自己重新实现一套 k/v 存储？ 这个问题可以拆分成两个方面，一个是为什么要用 K/V 数据库。一个是为什么要自己造轮子。

  1. 首先是因为数据大，而且数据是非结构化数据，像豆瓣的日记，就是一批很长的字符串。
  2. 其次是非常多的随机读。
  3. 有的时候会有大量的写操作
  4. 不需要外键什么的

上面四点可以排除掉类似 MySQL 这种传统的关系型数据库。

排除掉传统的关系行数据库之后，就需要对比现存的 K/V 数据库。

现在比较流行的 K/V 数据库有 LevelDB ， MongoDB ，还有 Cassandra ，现在看来这些项目都足够成熟。但是如果追溯到 BeansDB 项目最开始的时候，也就是 2012 年的时候，那个时间点并没有太好的选择。即使现在看来，除了 Cassandra 之外，像 LevelDB， MongoDB 也不能满足我们的目标：

  1. 读写都需要比较低的 latency
  2. 数据量非常大，所以数据要写在磁盘上，数据库需要能够容纳比内存大的多的数据
  3. 高可用，单点故障不影响系统正常运行
  4. 高吞吐，尤其是针对写操作
  5. 能够快速恢复有问题的节点

这 5 点也可以排除调 MongoDB 与 LevelDB 。

当然上面这些都是我做的推断，但是这些应该都不是最主要的原因。最主要的原因应该是豆瓣的工程师文化比较好，鼓励工程师去寻找一个最贴合业务的解决方案，并且这个工程师的团队还足够强，两者缺一不可。如果没有很强的工程师文化，可能会直接引入开源的解决方案，虽然不一定合适，但是应该足够解决痛点。如果工程师实力不够，也就没有能力去自己实现一套类似的系统。而且与其去引入一个复杂的，自己无法完全掌控的开源项目，不如自己实现一套贴合业务的，简单的系统。这样内部可以根据业务的需要来作调整，同时自己实现一个系统也比完全掌握一个庞大的开源项目要简单。一旦出现问题也比较容易找到问题所在。

为什么要用 Go 重新实现 BeansDB

BeansDB 是用 C 来实现的，为什么现在改用 Go 来实现？

  • 一个很重要的原因是 Go 的代码相比与 C 更容易维护。对一个工程师而言，Go 的学习成本比 C 要低很多。
    • 用 Go 可以比较快速的写出健壮的系统，而用 C 来写的话，则需要一定的经验积累。
    • Go 提供了可用的测试框架，写测试相对于 C/C++ 要方便
    • Go 标准库里面提供了方便的性能分析工具，用 C 也有类似的工具，但是做不到开箱即用
  • 还有 Go 的标准库也足够完善，不需要用 C 来重复造轮子。
  • Go 的执行效率虽然比 C 差，但是 BeansDB 的瓶颈是 IOPS，所以 Go 的执行效率并不会成为瓶颈。

GoBeansDB 的架构设计

GoBeansDB 是基于 Dynamo 与 Bitcask 两篇论文来做的实现，这里优先讨论基于 Bitcask 实现的存储引擎。Bitcask 有一个缺点在于所有的 key 值都必须放在内存里面，GoBeansDB 这这个基础之上做了一些优化，绕过了 Bitcask 这个痛点。

GobeansDB 的存储有有两个比较重要的组成部分，一个是索引(htree)，一个是数据文件(data)。索引与数据文件组成 Bucket。Bucket 的概念类似与关系行数据库里面的 table，在 GoBeansDB 的实现中就是给一个 Bucket 分配一个文件夹，这个文件夹下面放着相关的数据。每个 Bucket 下面一次只允许打开一个文件。打开的这个文件会一直保持打开的状态，一直等到追加到活跃文件超出阈值。文件超出阈值之后就关闭，然后新建一个新的继续添加。data 文件一旦关闭之后，文件就转换成为不活跃的数据文件。无法再往这个 data 文件上面追加数据。

img

状态为 active 的数据文件只做追加操作，这样连续的写入操作也不会明显增加磁盘的 IO 使用量。这种设计也极大的简化了数据的写入操作。

上面的图简单描述了 Bucket 内部文件的架构，每条数据里面包含TS（TimeStamp）,Flag，Ver（Version），ValueHash，RecSize（单条记录的主要内容的大小）,Value，crc（key，value，header 的 crc），ksz（Key Size）,vsz（Value Size）,pos（Position，这条记录在文件中的位置）,Header。

当插入新数据的时候，直接在文件尾部添加这种结构的数据。删除操作是对原有的数据做更新操作，并将 Ver 绝对值+1，转变为负数。

在文件写入完成之后，需要更新内存里面的数据结构，也就是前面提到的 HTree，HTree 是一个 Hash Tree，结构如下

img

levels 表示真实的树状结构， leafs 是树的叶子，保存着真实的数据。

img

这种数据结构下读取一个值也非常简单，大多数情况下最多只需要一次 seek 。我们首先在 Htree 中通过 levels 找到 key 对应的 leafs ， 然后通过 leafs 里面的报错的 Pos 来拿到文件编号（chunkID）以及 offset，这样就可以通过文件编号（chunkID）和 offset 来拿到保存的数据。在很多情况下文件系统的缓存会让这个读操作比预期的要快。

到这里关于 GoBeansDB wirte/delete/read 相关的操作都已经基本完成。但是仅仅这样还不能完备。

GC 操作

GoBeansDB 的模型非常简单，write/delete 操作都是在文件尾部追加新的数据，这样存在一个问题就是占用的磁盘空间比真实的数据要多。所以我们引入了 GC 机制来回收垃圾，释放内存与磁盘空间。

在 GoBeansDB 中，通过增量 GC 来减小 GC 的开销。xiufeng 通过分析 BeansDB 的日志，统计出一条新写入的数据，修改操作基本在写入之后的 7 天之内，所以我们保留 7 天之内的新数据不做 GC。然后在每天晚上，访问量较低的时候，分批做增量 GC。

GC 的过程是将 datafile 里面已经过时的数据清除掉，比如旧版本的value，已经标记为删除掉的key。

img

如 上图所示，GC 会读取状态为不活跃的数据文件，用其中存活的数据或者最新版本的数据生成一份新的数据文件，同时为这个新的数据文件创建一个 hint file。

c的代码走读

hstore

main -> 各种init -> store = hs_open(dbhome, height, before_time, settings.num_threads); -> bc_scan -> scanHintFile根据hintRecord能重建 hashtree -> thread_init(settings.num_threads); -> pthread_create(&flush_id, NULL, do_flush, NULL) -> loop_run(settings.num_threads);

hs是重点 应该代表hashtree，会根据hashtree的高度创建 2 的 4* 高度次方个bitcask实例。然后各个实例下面来进行实际的动作

inline int get_index(HStore *store, char *key)
{
    if (store->height == 0) return 0;
    uint32_t h = fnv1a(key, strlen(key));
    return h >> ((8 - store->height) * 4);
}

hstore有锁

struct t_hstore {
    int height, count;
    time_t before;
    int scan_threads;
    int op_start, op_end, op_limit; // for optimization
    Mgr* mgr;
    pthread_mutex_t locks[NUM_OF_MUTEX];
    Bitcask* bitcasks[];
};

这个锁只在hs_append和hs_incr上会加锁，因为涉及到get

bitcask内部有三个锁

struct bitcask_t {
    uint32_t depth, pos;
    time_t before;
    Mgr    *mgr;
    HTree  *tree, *curr_tree;
    int    last_snapshot;
    int    curr;
    uint64_t bytes, curr_bytes;
    char   *write_buffer;
    time_t last_flush_time;
    uint32_t    wbuf_size, wbuf_start_pos, wbuf_curr_pos;
    pthread_mutex_t flush_lock, buffer_lock, write_lock;
    int    optimize_flag;
};

本身是一个服务而不是一个嵌入式的库，锁多可以理解。

CURD

hs_set -> get_index -> bc_set -> pthread_mutex_lock(&bc->write_lock); -> ht_get 根据key查hashtree拿到value的指针。可以比较value hash，如果hash相同，区分不出，那就去拿到实际的value比较value bc_get(bc, key); -> 有版本信息，ht_add(bc->tree, key, it->pos, it->hash, ver); 更新版本 通常逻辑，走append -> pthread_mutex_lock(&bc->buffer_lock); -> 如果空间不够走bc_flush -> 重新分配buffer -> bc_rotate -> build_thread -> build_hint -> ht_add(bc->curr_tree, key, pos, hash, ver); 这里tree和curr_tree都更新了。为啥需要两个hashtree？ -> tree也有个锁 pthread_mutex_lock(&tree->lock);

hs_get -> get_index -> bc_get DataRecord -> ht_get -> check_key -> 锁tree -> get_item_hash 虽然是hashtree，但是get没用上hash，前面用到了，tree内部还是对比key

hashtree 和hint文件的关系

hashtree 构成，Node -> Data -> Item

struct t_item {
    uint32_t pos;
    int32_t  ver;
    uint16_t hash;
    uint8_t  length;
    char     key[1];
};

如何定位到Node？

通过build_hint生成hint -> ht_visit(tree, collect_items, &p); -> lock, visit node, -> collect_items -> write_hint_file(p.buf, p.curr, hintpath);

typedef struct hint_record {
    uint32_t ksize:8;
    uint32_t pos:24;
    int32_t version;
    uint16_t hash;
    char key[NAME_IN_RECORD]; // allign
} HintRecord;

hint文件是key hash pos，通过这个就构建出hashtree了

void scanHintFile(HTree* tree, int bucket, const char* path, const char* new_path)
{
    HintFile* hint = open_hint(path, new_path);
    char *p = hint->buf, *end = hint->buf + hint->size;
    while (p < end) {
        HintRecord *r = (HintRecord*) p;
        p += sizeof(HintRecord) - NAME_IN_RECORD + r->ksize + 1;
        if (p > end){
            break;
        }
        uint32_t pos = (r->pos << 8) | (bucket & 0xff);
        if (r->version > 0)
            ht_add2(tree, r->key, r->ksize, pos, r->hash, r->version);
        else
            ht_remove2(tree, r->key, r->ksize);
    }
    close_hint(hint);
}

这个hint用rocksdb存也是可以的，scan一遍就重新构造出来了。问题在于什么时候hint文件落地？会存在hashtree和hint不对应的场景么？

越看越眼熟。这和blobdb差不太多吧，无非索引有差别，一个是hashtree一个是skiplist

如果把rocksdb用hashtable替换skiplist我估计差不多吧

ref

  1. https://blog.csdn.net/lemonk3664/article/details/9970293
  2. 作者的记录 比较bitcask https://www.douban.com/note/122507891/
  3. https://github.com/douban/beansdb 代码
  4. https://github.com/douban/gobeansdb/ 后面他们用go实现了
  5. https://zhuanlan.zhihu.com/p/53682577 提到了c版本的优化，位域之类的