• hashtable的所有key都是64字节对齐，抵消 false-sharing影响
• hashtable 核心：无锁 原子操作，hashtable 的value是int64，可以CAS
• 每个key算出hash定位到具体的位置，并且将一部分hash存在tag中。hashtable是索引，具体的key value打包在一起放到Hybird log中
• 乍一看有点像mmap，不过是无锁

union {
    struct {
        uint64_t address_ : 48; // corresponds to logical address一般指针只用到48位
        uint64_t tag_ : 14;  //用来保存一段hash
        uint64_t reserved_ : 1;
        uint64_t tentative_ : 1;  //如果是1，说明在外面
    };
    uint64_t control_;
};

• 数据的存储格式 recordinfo + key - value
• 所有的record也字节对齐排列到一起

union {
    struct {
      uint64_t previous_address_ : 48; //冲突的key 链表节点
      uint64_t checkpoint_version : 13;
      uint64_t invalid : 1;
      uint64_t tombstone : 1;
      uint64_t final_bit : 1;
    };
                      
    uint64_t control_;
  };

• 这个recordinfo还是有扩展空间的，毕竟checkpoint_version用不了多少，比如实现ttl

• Hybird log可以理解成一个追加写的文件
• 之所以叫hybird，本身有内存和文件两部分，内存区域分可变区和只读区，可变区写满就会主动刷到只读区，然后再刷到磁盘 类似 rocksdb 中的 memtable， immutable memtable， sstfile这三者的关系，不过hlog是hash对应文件，没有顺序信息
• 也可以理解成一个ring-buffer
• 可读区和可变区的边界点比较重要，不同线程看到的可能不是同一个地址，引入fuzzy region，可以理解成一段边界，后面再决议出来
• 完全插件化设计，可定制hlog落盘的disk，实现WriteAsync/ReadAsync以及文件管理就可以，甚至可以直接写到对象存储，可定制文件读写API(aio/epool/iouring)
  • 比如MR 直接写到azure
  • 不同disk需要的checkpoint recover能力需要补齐/调整。不同文件读写的能力也需要调整

存在的问题

• 需要定期checkpoint，不然遇到崩溃，距离上次快照的所有hash index都会丢失

文件Device disk设计 FileSystemDisk

• WriteAsync和ReadAsync完全能读写到具体的文件，文件handle的获取存在竞争，需要加锁
• 资源释放的动作(OpenSegment/TruncateSegment)挂在epoch上。完美解决更新竞争问题
• 文件也用统一的address来描述 checkpoint和recover没有多余的处理，只要更新好address边界就可以保证正确读取数据
• 如何回收？可以简单的做TTL直接删除，也可以走compact逻辑，扫描删除（社区版本有bug）

azure存储作为device disk的方案

• WriteAsync和ReadAsync完全能读写到具体的文件，文件周期性淘汰到远端的磁盘上。此时读写远端存储
• 同样，更新的动作也挂在epoch上，推动evict/上传文件
• 文件也用统一的address来描述 没有多余动作
• 没有回收compact。直接指定address来删除

一个内存池fake device的方案 MemoryPoolDisk

存在的问题 以及 如何解决

• checkpoint的问题同样存在，崩溃必丢数据。不过使用fasterkv主要是为了快以及当成能持久化的cache来用
• 如何保证刷盘与内存池一一对应？ WriteAsync保证串行
• 内存池不能基于链表。不然持久化复杂。基于相对地址的page模式简单。碎片回收放在CURD的冲突检查中
• 如何回收？CURD给同hash的链上锁，清理（有延迟但都在内存中，可以接受
• checkpoint recover如何保证 - 提前flush

被毙掉的方案

• WriteAsync任务队列，队列信息可能会丢导致大量page没落盘。hlog page要落地一个index-mempool page。过于复杂
• Hlog本身hook WriteAsync。过于复杂，也不符合这个分离的设计
• 使用基于链表的内存池 落盘困难

epoch原理文字版

• 系统维护一个原子全局计数器E，以记录当前epoch，它可被任何线程递增。
• 每个线程维护一个thread-local版本的E，即Et，它会周期性刷新。而Et保存在一个共享的epoch表中，每个线程使用1个cache line大小。
• 当epoch c是安全时，任意线程的Et>c。而系统会维护一个最大的安全epoch Es。因此有Es<ET≤ E
  • 当epoch变得安全时，框架可以通过触发器执行任意的全局操作。
  • 当增加当前epoch时（如从c→c+1），线程可以绑定一个回调，当某个时刻c安全时，可以触发该回调操作。这个绑定维护在drain-list列表中，每一项为(epoch, action)。该表用小数组实现，并用CAS保证线程安全。
  • 当前epoch改变时，Es会被重新计算，而该表会被扫描，回调会被触发。
• bw-tree用的也是这个方案

如果用内存池作为disk，备份存在的问题

• checkpoint期间需要完全阻塞写入。不然会出现hash index 和内存池不对应
• checkpoint文件分为 hash index和内存池文件，不同于原来hlog address的统一处理，转到内存池，address不满足原有的递增逻辑
  • 要绝对的保证hash index 和内存池一致，且在hlog buffer中的内存完全刷到内存池中，flush hlog buffer -> dump hash index -> dump memory pool

备份流程: 文字版

• REST Commit在数据处于rest phase状态的时候被请求。设这个时候数据的版本为v。这个阶段由Commit函数触发。这个函数中更新数据库的状态为prepare，并添加一个PrepareToInProg。这个tigger会在所有的线程进入prepare状态后触发。每个线程也会更新本地的保存的信息。之后进入prepare阶段
• PREPARE 准备版本推进 这里如果遇到了大于目前版本V的数据版本，这个事务的执行abort。这个线程会更新线程本地的信息
• IN-PROGRESS 执行版本推进 PrepareToInProg函数会在所有的线程进入prepare状态之后被触发。它会更新系统的状态为in-progress，然后添加另外的一个trigger，刷新本地的信息。一个In-Progress状态的线程在数据版本为v+1的状态下面执行事务。这个操作的时候，如果一个线程遇到去读写记录集合内，且版本小于v+1的，它会将这些记录的版本信息修改为v+1。这么处理的原因是为了其它线程防止读取到这些还没有提交的数据。为了相互操作的不Blocking。这里会将记录live的数据拷贝到stable部分中。
• WAIT-FLUSH 等待版本下盘 InProgToWaitFlush操作。这个操作会首先设置全局状态信息为wait-flush。如果对于版本信息为v+1的记录，收集起stable版本，否则收集live版本。这个时候进来的事务会按照在in-progress阶段中处理的方式一样处理，所有的记录被收集且持久化之后，更新状态为rest，并更新全局的版本信息为v+1

compact存在的问题

• 开销很大，小key大量新数据可能需要很多compact，性价比低
• compact如果崩溃，可能就会有数据不一致的问题，数据删了，却没有落地

实际数据？？