PhotonDB

PhotonDB是一个基于BwTree和LLAMA实现的键值数据库“引擎“，打引号是因为这个项目已经完蛋了，目前为止它实现了BwTree和LSS（Log Structured Store）部分，以及一个runtime抽象（这个和数据库本身无关），这里就了解下PhotonDB做的工作，在这之前，需要先讲一下背景

BwTree

BwTree是2013年微软在ICDE论文中提出的一种latch-free的B+树的变种，用在了SQL Server的Hekaton内存存储引擎中，这篇论文只介绍了BwTree本身，关于事务和ARS（Atomic Record Storage）在另外两篇论文中描述，其中一个就是LLAMA（Latch-free Log-structured Access-method Aware）。虽然但是，这篇论文没有提供开源的实现，因此没有广为流传，后来cmu-db/peloton也将它作为内存引擎实现（当然peloton也完蛋了）。目前为止，据我所知，只有sled的master版本基于BwTree和LLAMA做了完整的实践，sled的master分支也很久不更新了，作者在project_bloodstone重写（后续会专门介绍）

说回BwTree本身，它有几个新的东西：latch free、append only、elastic page、delta update，其中最核心的东西是page table和节点逻辑连接

通常基于B+树实现的都是在节点中原地修改数据，这在HDD上会造成随机写，而HDD的特性决定了，随机写的性能不如顺序写；再者，每次写入都是以page为单位，对于一个字节的修改也需要整个页面的写入，这就导致了严重的写放大；再者，采用固定的page大小（也有例外，如： umbra）对于大于page的数据，一般都采用间接的方式管理，即，在记录中存放数据的指针，这就导致在读取时需要额外的操作；最后，在多核场景通常采用细粒度的latch来尽量减小加锁范围和锁竞争

对于以上的问题，在BwTree中都找到了答案（或许并不完美），BwTree在树节点中存放子节点的逻辑页面的ID，这个ID通过page table映射到物理地址，而B+树的节点变成了由多个delta和一个base组成的逻辑节点，page table的地址要么指向base要么指向delta，delta和base之间使用额外的指针（物理地址）链接成串。节点的更新变成了在page table中更新page id的映射为delta的物理地址，这个操作通过CAS完成，在这之前同样通过CAS将delta插入到base或delta的前面，如

插入前

page table
+---+
| 1 |-------->+-------+
| 2 |         | a = b |     base page
| 3 |         +-------+
|...|
+---+

插入后
page table
+---+            delta         base page
| 1 |--------->+-------+————>+-------+
| 2 |          | a = c |     | a = b |
| 3 |          +-------+     +-------+
|...|
+---+

----> 逻辑链接 
————> 物理链接

当然，BwTree解决了问题的同时也引入了另外的问题，比如：page table如何做到scale？ 并发访问的内存如何回收？append only如何做，GC如何做？

PhotonDB的实现

parent update

在PhotonDB中，按照论文的描述实现了BwTree，同时加入了一些修改。原文中为了加快查找会在delta记录中存放low key或high key，这样可以快速判断要查找的key是否在这个逻辑节点，同时也作为节点分裂和合并时辅助；在PhotonDB中通过在node header中引入一个48位的epoch来辅助分裂完成，结果就是delta的存储存储成本降低了，但查找的成本上升了，因为必须遍历整个delta链表，只有在base上才能使用binary search，不过对于B+树来说，内部节点远远少于叶子节点，结果就是内部节点的delta很少，所以这个修改谈不上糟糕，具体影响还需要从测试结果来看（可惜的是PhotonDB的源码已经无法编译通过了）

page table

对于page table的实现，PhotonDB和Sled都一样，采用了多级页表的方式，每一级有64K个entry，在PhotonDB中使用了三级，足够塞满整个内存。不过这也只是设置了一个预料中的最大值，并不能随着数据规模scale，因为page table总是需要整个载入到内存中的，一旦载入就固定了。虽然PhotonDB没有实现scale，但这种方式足够应对99.99%的场景了。当然，容易想到的实现scale的办法就是将page table拆成固定id范围的块，一个用完再申请下一个，这下就scale了，但对于PhotonDB的实现来说，scale却是一个伪需求

reclaiming

废弃的delta或base（在合并delta或合并是产生）可能还有其他线程在访问，不能立即进行回收。在原文中描述了基于epoch的回收算法(EBR：Epoch Base Relamining)，大致流程是：在访问对象时，对象需要登记当前的epoch，并且为访问的对象增加引用计数，当不再访问时减少引用计数，同时后台会按照固定时间间隔增加epoch，如果 epoch - 1 的对象的引用计数为0，那么这个对象就可以安全的回收了。在PhotonDB中，由于采用了Rust的async/await实现，这种方式会导致问题。PhotonDB中所有的BwTree对象都是从WriteBuffer中分配的，因此回收实际上的回收这些不再访问的WriteBuffer，PhotonDB又把WriteBuffer和page file等一些资源打包称一个Version，修改都反应在DeltaVersion上，而Version又通过VersionOwer经由EBR管理

page table持久化

原文中page table是整个一起持久化的，这种方式对于少量的修改来讲很浪费，在PhotonDB中将page id到page addr的映射记录在每个修改中，在持久化时整理成一个map，存放在WriteBuffer的元数据区域，这样即既做到了增量持久化，在恢复时也不用扫描所有page file

GC

PhotonDB中将每个WriteBuffer都持久化为page file，因此会存在多个page file（每个page file有唯一递增的id），这样废弃的记录是散落在page file中的，回收这些空间就需要一种策略（Min Decline Rate），找到一个page file进行处理

在处理时又会遇到新的问题：page file中除了需要回收的部分，还有正在被使用的部分。对于append only的系统来说，回收通常就是将正在使用的部分拷贝到一个新的地方，但这中方法在BwTree中会遇到问题，因为BwTree的节点通过page table映射到物理地址，这些正在使用的部分，要么是page table的值，要么就在delta链上，这么做意味这不仅要修改page table还需要遍历整个delta链。因此直接拷贝数据是行不通的，但可以增加一个delta，将它插入到拷贝后的链前，载替换到page table中。在PhotonDB中并没有这样实现，而是采用了另外一直方法page rewriting(详见引用）

目前基于BwTree的开源引擎一只手都能数过来，个人认为可能的原因有：1. 原文缺少细节，没有官方的开源实现，2. 对于B+树有Optimistic Latch-Coupling的性能要更好（不加上LLAMA），3. BwTree本身的复杂性以及它仅为引擎的一小部分