mace

mace 是基于 Bw 树的KV存储，最早的想法是用来替代 sled 在文件系统中的使用，主要的原因是 sled 的空间放大很严重，其次是 sled 已经很久没有更新了，而作者开的新坑已经变成了内存数据库（存疑）

Related work

在 rust 世界中KV存储并不多，大多都是其他语言的绑定，像是 rocksdb、lmdb 这种，rust 原生的实现要么是内存数据库，比如 surrealkv， 要么是基于 LSM 树的，比如 Fjall （可惜没有早遇到），而基于 Bw 树的就更少了，开源的还活着的基于 Bw 树的KV存储，大约只有 mace 了😅

为什么选择基于 Bw 树实现呢？Bw 树是 B+ 树的一个变种，目前主流的数据库实现要么采用 B+ 树，要么就是 LSM 树，前者适合读多写少，后者则相反，而 Bw 树则填补了 B+ 树原地更新的短板，将随机IO变为顺序IO，从而适配频繁写入（更新）场景，而几十年积累的 B+ 树的优化经验同样可以应用上去（比如 这里）

Overview

mace 的结构如下

Bw Tree

在 mace 中，Bw 树的实现借鉴了 PhotonDB，并添加了子树支持，同时适配事务增加了sibling，虽然市面上 Bw 树的实现没多少，但讲原理的还是有一些，这里不赘述

Buffer

这是 mace 中非常重要的模块，在 mace 中，buffer 是一个对外的接口，供 Bw Tree 使用，其内部包括了内存分配 arena、内存块管理 pool，缓存 cache，以及数据文件读写 flush/load

arena

它是一个无锁的内存分配器，用于在固定内存块上分配小块的变长内存，用作 delta page 和 base page 使用，通过在结构内部维护一个 offset 指针，依赖 CAS 实现

pool

它是 arena 的容器，当一个 arena 分配完成时，切换到下一个 arena，当 arena 不再被访问时将其刷入硬盘

cache

它是一个简单的 second chance 实现，目标时去中心化可以更好的 scale out，但目前仍然使用了锁，好在 DashMap 的锁粒度较细

在 mace 中，它的作用主要存放文件中加载数据，其次，如果一个分配完的 arena 还没有刷写到硬盘，那么也会在访问时加入到 cache 中，特别是对于密集写入场景

flush/load

目前数据文件完全由 flush 线程完成，它的工作是迭代传入的 arena 找到 active 的 frame 生成映射，然后刷入硬盘，在大量并发写入时 flush 可能是一个瓶颈，当然，这还取决于 arena 的数量

load 则是 flush 的“逆”操作，它只解析数据文件的映射部分，在需要时才读取数据。这也就意味着，当缓存受限时会有大量的文件读请求

Transaction

---

以上写的很烂，👴很不满意，后面找时间详细的写下