2020-01-15

在有序的KV引擎之上建造结构化数据库引擎

Views: 24383 | 2 Comments

KV 数据结构极大地简化了存储引擎的接口和实现. 基本的 KV 接口一般就是 Get(), Set(), 实现上代码也很简单, 极简的实现可以直接利用编码语言提供的 map(哈希, 红黑树)来提供内存数据结构, 而且硬盘上直接 dump 内存数据即可(类似 Redis 的策略).

不过, KV 存储引擎自己省事了, 但使用者不喜欢, 因为大部分的业务并不是 KV 所能表达的, 业务需要丰富的数据结构, 表格(table), 列表(list), map 等各种容器. 另外还需要排序功能, 业务依赖排序.

当前比较流行的 KV 存储引擎如 LevelDB, RocksDB, 因为其数据是 key 有序的, 所以许多结构化数据库引擎都基于其开发. 大家的思路都是使用 LevelDB 作为底层的持久化存储引擎, 通过在 key 上面做文章来实现丰富的数据结构支持. 类似的数据库有:

* SSDB, 兼容 Redis 数据结构
* TiDB, 分布式关系数据库, 支持 SQL
* MyRocks, FaceBook 开源的 MySQL 引擎

SSDB 应该是最先开创在 KV 存储引擎之上建立结构化数据库的项目, SSDB 在 2012 年就使用这种模式开发并开源了生产环境使用的数据库.

在 KV 存储引擎之上建立数据结构, 关键点是利用其数据的有序性, 实现方式是巧妙地设计 key 以及数据冗余来表达数据结构. 例如 map 集合结构, 就可以这样在 LevelDB 上设计 key 的结构:

* 集合的 size: key = "map" + $name + "size", value = $size
* 集合的 pair: key = "map" + $name + $key, value = $value

而 SSDB 的 zset(SortedSet) 就相对复杂一些:

* 集合的 size: key = "zset" + $name + "size", value = $size
* 集合的元素按 score 排序: key = "zset_score" + $name + $score" + $item, value = ""
* 集合的元素按 item 排序: key = "zset_item" + $name + $item, value = $score

像 TiDB 和 MyRocks 这样的关系数据库, 要实现表结构也并不更加复杂, 只是可能要存储更多的信息:

* 表的 meta 信息
* 主键索引: key = "PK" + $table + $PK, value = json_encode($row)
* 普通索引: key = "NK" + $table + $col + $PK, value = ""
* 更多的普通索引

可以看到, 主键索引是聚簇的, 其它索引带有主键的信息, 类似 innodb.

Related posts:

  1. 百行代码实现一个简单的Zset(SortedSet)
  2. SSDB在大数据量日志分析中的应用案例
  3. 如何使用SSDB的zscan命令
  4. 用PHP遍历SSDB中的zset集合
  5. SSDB – 支持 zset 的 LevelDB 服务器
Posted by ideawu at 2020-01-15 19:30:00

2 Responses to "在有序的KV引擎之上建造结构化数据库引擎"

  • 请教一下 以你对leveldb/tidb的了解 如果相同硬件条件下 mysql的update操作以insert+删除标识来替代 对比tidb性能会相差多少? 另外感觉leveldb这种 在内存内合并 再批量写入磁盘 和磁盘内存带宽比正相反 没有优化反而钝化了 Reply
  • 有两个小建议:
    1 添加unixdomainsocket,便于通过socket文件快速访问。
    2 在BinlogQueue::del_range中加入CompactRange可以显著提升启动速度。


    int BinlogQueue::del_range(uint64_t start, uint64_t end){
    while(start <= end){
    leveldb::WriteBatch batch;
    for(int count = 0; start <= end && count < 1000; start++, count++){
    batch.Delete(encode_seq_key(start));
    }

    Locking l(&this->mutex);
    if(!this->db){
    return -1;
    }
    leveldb::Status s = this->db->Write(leveldb::WriteOptions(), &batch);
    if(!s.ok()){
    return -1;
    }
    }
    std::string range_min = encode_seq_key(0);
    std::string range_delete_end = encode_seq_key(end);

    leveldb::Slice smin(range_min);
    leveldb::Slice smax(range_delete_end);
    this->db->CompactRange(&smin,&smax);
    return 0;
    } Reply

Leave a Comment