LLAMA: A Cache/Storage Subsystem for Modern Hardware

Bw-Tree, 即 “Buzz Word Tree”，由微软在 2013 年提出，基本是给 SQL Server 做内存引擎的。Bw-Tree 及其底座 LLAMA 的一作 Justin Levandoski 最早在 MS，后来去了 Aurora，现在在 Google BigQuery。

Bw-Tree 主要内容是 SSD 友好的数据结构，它希望对 Bw-Tree 的操作都是 Lock-free 的，它的数据基于 Page (Inner node + Leaf node) + Log （Delta node），用 Mapping Table 和 64-bit uuid 来映射到对应的 node （Page 或者 Delta node），它用 Epoch-based Reclaim 来回收空间，回收的时候，Bw-Tree 并没有做到 interval-GC（或者是它论文没说），相对的，在 Consolidation （Log + Page 产生新的 Page）之后，会把旧的 Node 给放到可 GC 的区域中。

它的分裂合并操作和 Blink-Tree 有一点相似，Split 和 Merge 都分裂成多个阶段，并引入了 Split / Merge 节点。SMO 本身是个多步的操作，当发现系统中有 SMO 的时候，别的操作会先帮助推进 SMO（有点像是在说这个 SMO 是 wait-free 的？）。

Bw-Tree 论文在国内已经有不少二手文章了，除了 Bw-Tree 文章外，CMU 在 SIGMOD’18 发表了一篇文章，描述了一些 In-memory 的 Bw-Tree 的行为和工程优化，测试(diss)了一下它的性能。笔者认为，B-Tree 族的算法比较复杂，而且和实现高度相关，移步这些专业人士写的二手文章相对来说更靠谱。不过，关于 LLAMA，介绍的二手文章比较少。

84102576-8957-4691-92DB-772A07FB6F53

LLAMA 提供了一个所谓 Log Structured “Page” Store 的引擎，对上层提供 Page 的接口和 更新/覆盖(替换) Page，但又提供以 Delta Log 和整个 Page 的形式写入具体的存储层的接口。下层类似 LFS。同时，LLAMA 提供 lock-free 的操作族，它的 flush 等操作都可以是异步的。

需求

LLAMA 提供了 Cache / Storage 两层的管理，以 Page 和 Page-Delta 的形式提供服务。它不需要理解 Page 的内容。它分为两层：CL 和 SL，即缓存层和存储层。可以简单把 LLAMA 当成一个 BufferPool：

  1. Storage + Cache
  2. Mapping Table + Page + Delta
  3. lock-free

逻辑上的结构可以见下图（不考虑更新和 Delta Log）：

33FB84CE-4078-45D9-AC16-DCF1BB31A7A6

LLAMA 并不会知道 Page 的内容，相关的 WAL/LSN/Checkpoint 需要外部维护，它只提供 Page 的 Allocate/Update/Overwrite/Flush/Remove。虽然表面上存储的是 Page，但是其实类似 LFS，这些数据会以 Log 的形式写到存储系统上，这个和 Delta Log 系统一起，降低了系统的写入开销。LLAMA 还提供了系统事务，用来支持类似 Bw-Tree SMO 等对多个 Page 的原子操作。

LLAMA Interface

这批论文一张图都没有。

Page Data Operations

LLAMA 提供了 Page Data Operations 操作数据，包括：

  1. Update-D(PID, in-ptr, out-ptr, data). D 是 delta 的意思，data 通常包含 <lsn, key, data> 这样的逻辑数据。in-ptr out-ptr 其实是塞给 mapping table 或者存储那一套，会把更新后的句柄丢出来
  2. Update-R(PID, in-ptr, out-ptr, data): R 是 replace 的意思，这里相当于整个页面的状态一把更新
  3. Read(PID, out-ptr): 返回 out-ptr 指向的内存地址，如果 Page 在盘上，也要把这个捞起来。

Page Management Operations

LLAMA 还提供了一组数据管理接口，支持 flush 等接口：

  1. Flush(PID, in-ptr, out-ptr, annotation): 把 Page 的状态拷贝到 log structured store(下文称 LSS ) 的 IO-Buffer，并且添加一个 Flush 的 Delta 记录，如后文的图。Flush 其实是个 async 接口，并不代表成功写到盘上了。这里还有个要注意的是，这里刷的时候可能大小不固定，然后 annotation 可能是 LSN 这些业务语义，也会带下去。
  2. Mk-Stable(LSS address): 保证在 LLS address 之前的 IO-Buffer 上的记录都已经写到持久存储上了。
  3. Hi-Stable(out-LSS address): 返回刷到持久存储的最高位点
  4. Allocate(out-PID) 懂得都懂，申请一个 Page 返回 pid 然后在 mapping table 注册一下. 同时这样的 Page 也要持久化
  5. Free(PID): 准备会收掉对应的 PageID / Page

我吐槽下，这论文也没说什么模型，data 是啥，我感觉只能猜测是一些 Delta Log 和什么别的了。LSS 数据估计是一个无线长的数据段或者环状 buffer。至于别的基本上都是 BufferPool 该有的，只是存储变成 Delta 了。

System Transaction Operations

这里会产生系统内部事务，读写会 buffer 在内存中，在 commit 的时候提交。commit 阶段的时候，所有的 Page 会原子性添加到 LSS 的 IO-Buffer 中，然后被刷下去。LLAMA 这里好像并没有描述任何的并发控制和策略，估摸着是上层控制了，BwTree 的事物靠上层的 Deuteronomy 来控制。

这里提供了大概如下的接口：

  1. TBegin(out-TID): 拿到一个 TID，这需要维护一个 active transaction table (下称 ATT)
  2. Commit(TID): 从 ATT 中取出来，原子性的写到哪步
  3. TAbort(TID): 从 ATT 出来 abort

这里不应该 Update-R，似乎是觉得 Replace 会导致这个内部事务过于复杂，所以没支持。总之会被刷进去。

Bw-Tree 如何利用 LLAMA

Bw-Tree 提供 Key-Value 接口，自己维护 LSN，根据事务接口并发控制和管理 Ckpt。通过 Update-D 和 Update-R 来更新/Consolidate。通过 Allocate 和 Free 来申请/收缩。

Cache Layer

可以视作，Cache Layer 对外提供了 Mapping Table 等抽象，并能够换出对应的内容。如我们在 Bw-Tree 所描述的一样，这里依靠 Write Log-> CAS mapping table 一对操作来进行原子的写入。这里 Mapping 的内容会无论如何存储一个指向 LSS 中位置的指针，来作为 CAS 的主体，用户的指针也会携带一个对应的 LSS。

这节的内容其实比较 hacking，我估摸着得翻翻实现才能好理解。上面这段话说的比较绕，实际逻辑可以看下面，大概就是无论如何会放一个 LogOffset.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#[allow(clippy::module_name_repetitions)]
#[derive(Clone, Copy, PartialOrd, Ord, Eq, PartialEq, Hash)]
pub struct HeapId {
    pub location: u64,
    pub original_lsn: Lsn,
}

/// A pointer to a location on disk or an off-log heap item.
/// 
/// (log_offxet, heap_id)
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum DiskPtr {
    /// Points to a value stored in the single-file log.
    Inline(LogOffset),
    /// Points to a value stored off-log in the heap.
    Heap(Option<NonZeroU64>, HeapId),
}

LLAMA 会存储成 Delta / Page, 大概是 PID -> Delta LSS -> Delta LSS -> Page, 需要靠上层 Update-R 之类的来 consolidate.

450839E1-75FD-48DC-81E9-BC8E10FE04EE

Flush 的原子性

Flush 包括：

  1. 拷贝到 LSS 的内容中
  2. CAS 发布

如果同时有更新，可能需要保证正在 copy 的内容不要和 flush 的流混了。这里它的策略如下：

  1. 在 LSS Buffer 给 Allocate 一段 IO Buffer
  2. 创建一个 Flush Delta, 尝试 CAS 这个 LSS
  3. (2) 成功了，就拷贝到 Buffer 中；否则在 Buffer 写一个 FAILED_FLUSH 记录，防止恢复的时候数据错误

Page 换出

这里允许记录或者 Page 换出，为了防止内容空悬，可以用一个 PARTIAL SWAP 记录表示内存中的结构 Swap 出去了：

8B64DF88-DD1E-4107-862A-A276B5313E76

这里还使用使用 Epoch Base Reclaim 来回收内存，不再赘述。

3E209D4B-B2B4-45F4-A240-C3643AA78B54

Storage Layer

这节说是 Storage Layer，其实就是介绍了它的 Log 写入层和一些 lock-free 的 WAL，和 LFS/MySQL 8.0 WAL 很像。LLAMA 这里没说怎么 GC，不过我感觉因为 Consolidation，早点的记录基本都能被清除掉。

7F968374-1EDD-41E9-BB82-683D2F88BECC

比较关键的是 Flushing 部分，它希望 Flushing 是 lock-free 的，每个 Buffer 有一个固定大小。这里有几个控制字段：

  1. Sealed bit
  2. Active writers
  3. Offset

78BF2138-B283-4EF7-BC9A-FF97521E1749

那么实现的逻辑如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
WriteOnBuf(buf, data):
	while True:
	  (sealed, active_writers, offset) = buf.ctl.load()
    if (sealed):
      去写另外的 Buf
    offset += data.size()
    if offset 超过限制:
      设置 sealed = True
    设置 writer += 1
    if buf.ctl.cas():
      break
  拷贝 data 到给定的字段
  cas 减少 writer, 如果 active writer = 0 且 Sealed, 推进拷贝到存储空间

这里其实和 MySQL 那个 Lock-free WAL 协议很像。

LSS Clean (GC)

这里内容类似 LFS 或者 WiscKey。LSS 可以视作无限增长的，然后内容写在一个环状缓冲区上。

InnoDB 会两个 log 文件换着写，我觉得基本也就这个样子。

性能

作为一个缝合怪，这里性能描述如下:

First, there is no empty space in pages that are flushed. They are written as packed variable length strings. On average, traditional B-tree pages are only 69% utilized. Second, because we will frequently flush only deltas since the prior flush, much less space will be consumed per page flush. Finally

我觉得没啥意思…

System Transaction

这里不提供通用的事务，多个 Page 的更新可能会被 Partial 的读到。但是这里靠框架上的更新来处理这一点。

我上面说的话我自己读了一遍都没太懂，所以我贴个 Cow-Btree:

updated-btree

这里不是说 Bw-Tree 是 Cow-Btree, 不过其实差不多，这里 Split/Merge 本身是能够做到原子被看见的：

F06B0563-9E77-407A-85D8-086EF2A10580

Recovery

这里 Recover 其实挺类似 WiscKey Recover 的，麻烦在于恢复 Mapping Table。这里会定期写快照，然后 Replay log 来恢复。

EF1946C6-A748-4289-98A7-8EF5720F92C7

sled

sled 是一个 LLAMA 的实现。它上层并没有用 Bw-Tree，用了一个 Epoch GC 的实现。这里有几个关键内容：

  1. IoBuf 和 IoBufs 对应论文里面的无锁 Buffer，由 Log 包装。基本上实现了论文描述的内容。
  2. PageTable 是对应的 Mapping Table 的实现
  3. Node 代表 Page 或者 Delta, 用 link 添加新操作。这里由更新的次数来决定是否 consolidation
  4. transaction.rs 有事务相关的内容。
  5. GC 使用 crossbeam 的 crossbeam-epoch 实现

Reference

  1. [ICDE’13] The Bw-Tree: A B-tree for New Hardware Platforms
  2. [PVLDB’13] LLAMA: A Cache/Storage Subsystem for Modern Hardware
  3. [SIGMOD’18] Building a Bw-Tree Takes More Than Just Buzz Words
  4. [PODS’21] ArkDB: A Key-Value Engine for Scalable Cloud Storage Services
  5. Sled: https://docs.rs/sled/0.34.1/sled/doc/sled_architectural_outlook/index.html#caching (已不再维护)
  6. 数据库月报的 Bw-Tree 栏目：http://mysql.taobao.org/monthly/2018/11/01/
  7. Indexing on Modern Hardware: Hekaton and Beyond
  8. https://github.com/spacejam/sled
  9. CMU 15-721

二手材料