xkv

用来高效率的验证kv引擎feature的项目。

内存数据结构

跳表

• xkv在内存中存储数据的主要容器
• O(logN)时间复杂度完成增删改查
• 为什么不用O(1)的哈希表？
  • 需要有序
  • 方便归并排序
• 索引动态更新
  • 概率算法：每一层的节点，被提到上一层的概率是1/2
• 快读比较
  • 引入hash，对前8位计算分数值

布隆过滤器

• 功能：O(1)时间复杂度判断集合中是否存在某个元素，存在假阳性，不存在假阴性
• 结构：K个hash函数、长度为M的比特数组
• 推导
  • 给定比特数组长度M和插入的元素个数n，确定哈希函数K
  • 给定假阳性率p，确定比特数组大小

内存池

在kv系统的应用场景下，处理的是大量的kv键值对的插入和删除。不可避免频繁向OS申请内存。OS分配内存需要借助系统调用，并陷入内核态，带来额外的上下文切换的开销。

• 为什么不用golang自带的内存管理
  • golang的内存分配不区分业务逻辑，不同业务的变量完全可能使用连续的内存空间。极有可能导致大量内存碎片的产生。
• 解决
  • 预分配一块较大的内存，直接在用户态下进行再分配，而且这时候分配只是移动指针。
  • 只提供分配空间的操作，xkv的应用场景中，所有操作都是在内存池中追加，超过一定阈值后会将整个memtable变成immutable，随后持久化成sst文件。
    • 不提供是释放空间的操作，借助golang的内存回收机制即可。
• 内存对齐
  • 举例：避免6字节的数据横跨两个8字节的存储单元

缓存

1. 已打开的sst文件对象和相关元数据
2. sst中的dataBlock内容

• lru
  • 如果一个数据在最近一段时间没有被访问到，那么在将来被访问的可能性也很低
  • 但是没考虑频率
• lfu
  • 难以应对突发的稀疏流量，可能存在就数据长期不被淘汰。
• W-TinyLFU
  • 全量数据先进入 Window-LRU(1%)
  • 被淘汰的数据进入 Segmented-LRU
    • 通过布隆过来快速判断是否在SLRU中
    • 使用 count-min sketch 算法计算频率
    • 放入20%的 probation
    • 淘汰的数据或二次访问的数据 放入80%的 protected
  • 针对一次性数据，在wlru中很快被淘汰，不占用缓存空间
  • 针对突发性的稀疏数据，wlru可以很好的适应这种访问模式
  • 针对真正的热点数据，很快就会从wlru中进入到Protected区中，并且会经过保鲜机制存活下来

硬盘数据结构

SST

• sst文件是LSM用来持久化kv的文件。
• 创建
  • 当向kv引擎put数据时，会检查当前内存表是否达到指定的阈值，如果达到阈值即会出发flush行为，该行为最终会将整个skiplist的数据序列化到磁盘上

• 检索

Manifest

Manifest 文件是一个用于存储sst所属的层级关系的元数据文件，当数据库重启时，需要读取该文件用于恢复层级关系的元信息。其次每次flush或者merge了sst文件后都需要变更Manifest文件

1. 能够存储sst文件的层级元信息
2. 支持高性能的update操作（顺序写）

• 逻辑
  • 加载manifest文件
    • 打开工作目录下的manifest文件
    • 如果manifest不存在
      • 则创建一个内存中的manifest结构
      • 并通过覆写的方式创建一个manifest文件
        • 创建一个remanifest文件
        • 将当前的状态全部抽象为changes对象，然后追加得到一个list
        • 将其整个序列化到刚刚打开的remanifest文件
        • 然后将remanifest文件重命名为manifest文件
      • 并直接返回结果
    • 如果文件中存在新的数据，则会执行重放逻辑
      • 将文件格式循环解析manifestChangeSet结果
      • 遍历manifestChangeSet逐条应用change消息
        • 如果是创建 则更新内存中的manifest中的levels和tables，并统计创建命令的次数
        • 如果是删除 则删除manifest中的levels和tables，并统计删除命令的次数
  • 构建levelmanager
    • 从manifest的元信息中解析出sst文件的fid
    • 对比工作目录中多余的fid，将其删除，保证从正确的状态启动
    • 然后逐一写入对应的levellist中，并且按fid排序
    • 根据fid逐一打开sst文件，并加载其索引块
  • 添加一个sst文件到manifest中
    • 创建一个changeSet对象
    • 应用到内存的manifest中
    • 判断是否达到覆写阈值，如果达到则覆写manifest文件
    • 序列化后追加写入到当前的manifest文件
    • 手动调用sync接口同步manifest文件

基本功能

恢复

• 为解决数据库进程奔溃造成数据丢失情况的发生，需要一种能够让数据库在重启时恢复上一次运行最后一个正确状态的机制
• 每一个memtable都对应一个wal文件，当这个memtable成功变为sst文件后，与之对应的wal文件随即被删除

并行压缩

LSM是非就地更新的，通过不断追加不同版本的kv来实现高性能写入，但我们并不需要过于陈旧的key，这会造成存储空间的浪费，存储过多版本key的同时也会使得检索key的时候查询更多无效key2而增加耗时。因此我们的需求是

1. 实现一种Lx到Ly压缩（归并排序）sst的分层机制，提高查询效率
2. 正确地识别无效的key（不会再被访问的key）并将其删除，提高空间利用率。

• L0层sst是无序的，合并式会涉及较多的sst，如何优化？
  • 合并时，对涉及的sst加读锁，保证依旧可以对外检索，而flush过程只会向L0添加新sst，因此可以保证是无阻塞的，同时当压缩结束后才会删除旧sst文件，此步骤会造成阻塞（可通过mv方式原子删除提高并发度）
  • 对L0层的查询最坏情况可能要遍历所有的sst文件，因此L0层sst文件自身进行压缩，可以有效减少L0层sst文件的数量，进而提高查询性能
• 压缩过程需要从Ln到Ln+1，一个有效key至少经历7次的移动，写放大严重，如何解决？
  • 如果Lmax层没有达到预期的容量，可以直接实现L0到Lmax的压缩，进行跨层级压缩，来减少写放大的可能性。
• L6层的数据会越来越多，是否会导致数据倾斜？过期的key在L6层如何被清理？
  • 数据达到L6层后将无法被压缩到下一层，因此实现L6层自身的压缩，可以清理L6层的无效数据，提高空间利用率和性能

• 为充分发挥ssd的并行度，如何实现并行压缩，来提高性能？

  level级别和table级别都加上读写互斥锁，然后维护一个全局的关于sst的状态表，记录每一个压缩任务的执行状态以及涉及的sst有哪些，在生成压缩计划的时候，检查其互斥性，如果当前压缩任务涉及的sst文件与正在执行的其他压缩任务没有冲突则可以执行，否则失败
• 对于Lx到Ly的压缩，如何选择x与y才能使得整体压缩效益最大化，节省空间提高性能？
  • L0层根据sst文件的数量来决定，其他层根据每个level的去除正在压缩状态的sst文件的总size与每层的期望size的比值作为优先级，而每个level的期望size之间相差一个数量级
• 压缩过程执行到一半，数据库崩溃后数据的一致性如何保证？
  • 只有在manifest文件状态变更成功后，才会向Lx中删除老旧sst，并在Ly中添加新的sst文件
• 多个协程执行并行压缩，如果频繁出现并发冲突该如何解决？
  • 在多个并发执行的压缩器初始化时，给予一个500ms左右的随机时间，使得每个压缩器执行的并发性被打散，降低冲突的可能性。
• 压缩时读取sst文件到内存进行排序是否会造成oom？
  • 归并排序，逐条拉区

KV分离

• set kv时判断值的字节大小是否超过阈值，是则将其写入vlog文件并将返回的指针写入sst中
• get key时从sst中查询值并判断其是否为值指针，是则从vlog中查询真正的值，否则直接返回
• vlog文件是一组fid自增的文件，写入的数据超过设定阈值大小就会通过滚动的方式写入到fid+1的文件中
• 存在一种gc触发方式，从vlog文件组中选择一个脏key数量最多的文件进行重写操作
• 重写操作就是删除无效的key，保留有效key到一个新vlog文件中的过程
• 对于重新写回LSM的有效key，可以批量的写入以提高性能
• kv先写vlog文件再写LSM，因此必须保证vlog文件与sst文件的一致性