原标题：: A Cache/Storage Subsystem for Modern Hardware

周末，杭州大雪，凄风惨雨，只能待在家里喝茶读文。

微软之前提出了一个叫做Deuteronomy（dutəˈrɑnəmi，a book of the Bible that repeats the Ten Commandments and records much of Mosaic Law.）的架构，这套架构的核心思想是将数据里的事务组件（Transaction Component）和存储组件（Storage Component）分开，这样带来的好处就是系统的灵活度增加了，而且各个模块可以独立的向前演进，方便适配快速变化的基础环境。精细分工+尖端化这个演进方向是个很有意思的话题，想想微服务，小而美，日本制造和德国制造，啊扯远了。

论文中实现的LLAMA可以作为Deuteronomy的存储组件，其提供了面向page操作的缓存和存储功能，并保证对page状态的修改是原子的。

LLAMA架构图见下，既可以作为一个通用的存储组件，也可以作为数据库内核的存储模块提供服务。

图1 LLAMA 架构

LLAMA的背景是随着硬件的快速发展，传统软件架构虽然也获得了红利，但是没有充分的利用硬件能力，论文认为需要重新思考数据库架构。重新思考的核心是三个方面，

1. 充分利用无锁发挥多核能力
2. 考虑多级Cache的影响，减少cache invalidtions（偏重指CPU cache）
3. 通过Log Structuring节约写，变随机为顺序

LLAMA从两个角度去解决上面三个问题。

首先，使用delta（图2里面的record）描述对page的修改，而不是直接修改page 本身(见下图）。传统B+Tree在更新page时候是加锁，修改，放锁，这种操作对上面三个问题的前两个都造成了很大的破坏。频繁的加锁放锁导致较低的多核性能（如果将CPU每次操作的流程可视化，我们就能更直观的认识锁对性能的巨大影响，只是我也没见过这样的工具），且让系统变得复杂。同时，页面被修改之后，旧的页面被回收也导致了cache失效，进一步影响了性能。使用delta同时缓解了两个问题。首先，对page的修改先放到delta里面，这样原始的page不用做任何改动，自然也不用加锁，也不会导致cache失效。如果修改很多，将delta和page做一次consolidation（读的时候是从最新的delta一直读下去，所以如果长时间不做consolidation，读性能会很差，这里跟一些K-V系统使用的Log-Structured-Merge思路类似，只是更加偏向读一些），使用新page换掉旧page，此时会有一次cache失效，但是并没有加锁，原因见下一条。

图2 页面以及对其的修改delta

第二，使用page mapping table隔离页面真正的物理位置，见图3。每个page都有一个唯一的ID，这个ID可以认为是逻辑ID，是在新页面生成的时候系统分配的（从文章看，这个ID是自然数且会回收利用），逻辑ID和物理位置构成了mapping table里面的一项。从图3看到，页面不管是存储在内存中（Cache）还是磁盘上，都可以用64bit表示，这样如果页面consolidation后要换成新的页面，只要根据被替换页面的逻辑ID找到其物理地址，然后CAS就可以了，这就解决了上面问题一中的替换页面时候锁的问题。

图3 page mapping 示意

至此，LLAMA的背景和核心思路已经清楚，即LLAMA是一个页面管理器，通过page mapping table隔离了页面的物理位置和逻辑位置，以增加其自身的灵活性，且为无锁打下基础；其不仅管理固定大小的页面，还管理变长的delta page；不仅管理存储，还管理缓存；不仅保证单个页面的操作原子性还保证多页面联合操作（分裂、合并）的原子性。

下面看一些关键细节。

关键细节一：LLAMA提供的操作。主要有两类，一类是针对页面数据的操作，主要有三个

1. Update-D(PID, in-ptr, out-ptr, data)，将某个页面的修改（Delta）连接到页面上，data是辅助结构，一般跟调用方有关
2. Update-R(PID, in-ptr, out-ptr, data)，将某个页面换掉（Replace）
3. Read(PID, out-ptr)，页面读取，如果页面不在内存，会从磁盘读出来，跟文件系统的page cache行为类似，调用方很好用

第二类是跟页面状态有关，

1. Flush(PID, in-ptr, out-ptr, annotation)：将页面拷贝到LSS（Log Structure Store，写盘模块）的buf并将返回地址填充到out-ptr，annotation不知道明确目的，可能跟上层调用方的某些约束有关。文中强调这个行为只是将page拷贝到buf，并不落盘。论文中还提到有专门策略控制buf里面哪些数据可以落盘，这是系统无锁得以实现的一部分
2. Mk-Stable(LSS address)：保证LSS address之前的页面全部落盘（secondary storage）
3. Hi-Stable(out-LSS address)：返回当前落盘的最高LSS地址
4. Allocate(out-PID)：分配一个页面ID，所有分配过的页面都得记录，否则分配重了就不对了，这里是依靠事务机制完成的，论文称为system transaction
5. Free(PID)：释放PID，也是要记录的。文中说有一个和epoch相关的free list专门记录，epoch是LLAMA回收模块（Garbage Collection，GC）的概念，也是比较通用的GC手段

关键细节二：系统事务（System transaction）

LLAMA在完成页面状态管理的时候，也需要保证一致性。比如页面分裂，父页面和子页面状态都要改，此时有一个事务会更加容易理解。具体做法文中说的不多，提到了为了避免undo带来的复杂性，Update-R不允许使用在事务中，看起来可以接受，毕竟有了Update-D，Update-R可以基于Update-D实现。同时，这个事务也做的非常简单（重启后事务ID不需要唯一），直到Commit所有操作才会应用，跟一些K-V系统里面的简单事务有点类似。

关键细节三：页面刷盘

如果发现delta太多，可以在内存中就把这些delta变成contiguous delta，然后写入LSS，这样的话，LSS里面会同时存在多个小的delta和一个大得contiguous delta，多占用了一些空间，交给LSS Cleaner解决。

文中特意提到了一个无锁带来的难题，即当页面flush到存储的时候，同时也需要修改mapping table的page state，那么是先flush再尝试修改mapping table还是反过来？简单的组合都是有缺陷的，作者巧妙的利用预留位置和可能多用一些存储解决掉了，该方案如果冲突严重可能也会浪费很多空间，感兴趣可以看原文。从对这个问题的讨论看，LLAMA对无锁的实现是贯穿到方方面面的。

关键细节四：贯穿全局的回收

因为无锁是系统的主旋律，那么所有资源类的释放就只能依靠后台回收，而后台回收的核心思路是epoch，见图4。如果有一个参与方判断某个对象要被回收了，就将其link到一个不断递增epoch链表上，当所有参与者都越过这个epoch后，那么这个epoch以及之前epoch上挂接的对象都可以回收了。这个epoch和事务约束（MVCC）可以互相做映射，从而使得整个系统的回收都可以很方便的执行。图4只是内存对象的GC，store的GC思路是类似的，策略会多一些，这些内容被包括在文中提到的LSS Cleaner部分。

图4 . 系统GC

关键细节五：page在LSS的组织

图5是mapping table和LSS page布局的示意图。可以看到类似一个磁盘上的链表，每个delta必然指向一个base或者其他delta，delta的大小是变化的，也即是一个磁盘物理块里面可能包含多个delta，这也是文中说该系统利用率高的一个原因，毕竟之前的Log Structuring Filesystem还是固定大小的page，逻辑page和物理page是一对一的，有空间浪费的嫌疑。另外，文字还给了一个数字，即传统基于块的B-tree空间利用率只有69%，这样使得Log Structure的优势又多了一个。

图5 mapping table和LSS page 布局

关键细节六：mapping table的failover

mapping table的变化是随着LSS写下去的，这里LSS有点像是mapping table这个Database的Write-Ahead-Log一样的角色，保证了其持久化，但是不可能每次系统起来都replay所有的log，所以还是要定期做checkpoint。文中提到说可以使用增量方式一点点对mapping table做checkpoint，提到了增量的起始和结束点如何选择，这就解决了增量checkpoint的一个难题，即如何选额一个稳定的增量边界。当然，增量checkpoint还会有其他的问题，比如合并问题。

从全文来看，LLAMA的设计充分践行了无锁和减少随机写的思想，顺便也把数据库系统设计灵活性提高了一个档次，是一个很新颖的设计。其中也有很多细节值得学习探讨，欢迎读过此文的一起讨论。

如无特殊说明，所有图片来自论文[1]。

最后，公众号的编辑器终于不那么土了，真不容易。

[1]. LLAMA: A Cache/Storage Subsystem for Modern Hardware

责任编辑：