/smallkv

A small Key-Value storage engine written in C++.

Primary LanguageC++MIT LicenseMIT

SmallKV Logo


GitHub top language GitHub stars LICENSE

smallkv 是一个列存的、基于LSM架构的存储引擎。

项目正在疯狂迭代中!!

Attention: This is a toy project, so it cannot be used in production environment.

客户端演示

基本操作类似Redis,如下图所示:
cli

进度

  • 跳表
  • 布隆过滤器
  • 内存池
  • 缓存模块
  • FileWriter/FileReader(todo: 支持mmap)
  • SSTable
  • MANIFEST
  • WAL模块
  • memtable
  • 读流程
  • 写流程
  • BatchPut、BatchDelete
  • Compaction模块
  • 用FreeListAllocate(src/memory/allocate.h)替换系统内存分配器
  • 简易客户端:smallkv-cli

BUILD

You must use the g++ compiler(with C++ 17 supported) and Ubuntu 22.04 system.

build from docker (Highly recommended)

git clone git@github.com:yangyang233333/smallkv.git
docker pull qianyy2333/smallkv-test
docker run -it -v /{smallkv代码所在的目录}:/test qianyy2333/smallkv-test /bin/bash
./build.sh         ## 编译
./main_run.sh      ## 主程序
./unittest_run.sh  ## 单元测试

build from source code:

# 安装依赖
apt update && apt upgrade -y && apt install cmake make git g++ gcc -y && cd ~ \
    && git clone https://github.com/gabime/spdlog.git && cd spdlog && mkdir build && cd build && cmake .. && make -j && sudo make install && cd ~ \
    && git clone https://github.com/google/googletest && cd googletest && mkdir build && cd build && cmake .. && make -j && sudo make install && cd ~ \
    && git clone https://github.com/nlohmann/json && cd json && mkdir build && cd build && cmake .. && make -j && sudo make install && cd ~ \
    && git clone https://github.com/abseil/abseil-cpp.git && cd abseil-cpp && mkdir build && cd build && cmake .. && make -j && make install && cd ~ \
    && rm -rf spdlog googletest json
git clone git@github.com:yangyang233333/smallkv.git
cd smallkv
./build.sh         ## 编译
./main_run.sh      ## 主程序
./unittest_run.sh  ## 单元测试

设计

1. 内存池设计

mem_pool

2. 缓存设计

cache Cache中持有N(默认为5)个指向CachePolicy的指针,相当于5个分片,可以减少哈希冲突以及减少锁的范围;LRUCache和LFUCache都是CachePolicy的子类。

3. SSTable设计

每个.sst文件存储一个SSTable结构,SSTable结构如下所示:
sstable_schema 下面细说每个模块的内容:

  • 3.1 DataBlock

data_block_schema 1)上图中,每个Record存储了具体的KV数据,并且记录了连续的Key的共享长度(为了差值压缩);
2)Restart主要用来进行二分查找,根据Restart中记录的offset信息可以解析出对应的Record Group中最小的Key,通过比对连续的Restart中的Key可以快速定位K-V pair,每个Restart记录了一个Record Group中的Record数量,以及对应的size和offset,每个Restart长度为12字节;
3)Restart_NUM记录了Restart的数量;
4)Restart_Offset记录了Restart的size和offset信息;

  • 3.2 MetaBlock

MetaBlock中存储了Filter信息(位数组和哈希函数个数),也就是布隆过滤器的数据。为什么需要这个数据?因为sst是顺序append结构,所以写入很快(O( 1)),但是查找非常慢(O(N)),于是需要一个布隆过滤器来对请求进行初步的过滤(可以过滤掉一定不存在的KV pair)。

  • 3.3 IndexBlock

index_block_schema IndexBlock存储对应的DataBlock中的最大key信息(注意:实际存储的是shortest_key,并且shortest_key = min{shortest_key > 对应的DataBlock的最大key},这样可以减小比较次数,缓解高并发下的压力);Offset_Info存储了对应DataBlock的size和offset。

  • 3.4 Footer

footer_schema MetaBlock_OffsetInfo记录了MetaBlock的size和offset,IndexBlock_OffsetInfo记录了IndexBlock的offset(第一个IndexBlock的offset)和size(所有IndexBlock的总大小)。

4. Read/Write Op

rw_op

  • 4.1 Read

先读缓存, 有则立即返回; 否则读memtable, 有则立即返回; 否则使用SST Parser解析磁盘的SST文件,找到对应的key.

  • 4.2 Write

先写wal, 保证数据安全; 在写memtable和cache.


第三方依赖:

  1. spdlog
  2. gtest
  3. nlohmann/json
  4. abseil

有用的参考资料:

  1. 阿里云NewSQL数据库大赛
  2. corekv
  3. leveldb
  4. Linux I/O: fsync, fflush, fwrite, mmap

Thanks to JetBrains for donating product licenses to help develop **smallkv **