LLAMA and Mindful Stacking

在 Bw-Trees 中，我们讨论了称为 Bw-Tree 的不可变的 B-Tree 版本，Bw-Tree 使用的是一个分层的 Latch-free 无锁的、Log-structured 结构化日志的、Access-method aware 访问模式认知 (LLAMA) 的存储子系统。这个分层允许 Bw-Tree 能够动态的增长跟收缩，同时保持垃圾回收跟页管理之间的透明度。在这里，我们主要的兴趣点在于 Access-method aware 部分，他展示了软件分层所带来的好处。

先简单总结，一个 Bw-Tree 的逻辑节点由物理增量节点的链表组成，链中的节点包含了最新的更新到最旧的更新，最后以原始节点结尾。逻辑节点使用的是保存在内存中的映射表，映射表指向了最新更新节点在磁盘中的位置。Key 跟 Value 会从逻辑节点上进行添加跟删除，但他们在物理上的表示则仍然是不变的。

结构化日志存储缓存了节点的更新 (通过增量节点) 到一个 4Mb 的闪存中，当这个页被填满时，他就会被刷新到磁盘中。周期性的，垃圾回收会回收那些不再使用的增量跟基础节点，并为仍然存活的节点重新分配控件来释放碎片化的页。

在不使用 Access-method Awareness 访问模式认知时，不同逻辑节点间交替的增量节点会按照他们的插入顺序保存。Bw-Tree 的 LLAMA 认知下，允许将多个增量节点连续的保存到物理地址中。如果两个增量节点的更新会互相抵消 (比如插入之后进行删除操作)，那可以为他们执行逻辑性的合并，并且只保留最后的删除操作。

LSS 垃圾回收可以对合并 Bw-Tree 节点的内容提供帮助，这意味着垃圾回收不只是回收空闲的控件，还可以直观的减少物理节点中的碎片。如果垃圾回收只是重写了多个连续的增量节点，那他们仍然会占用相同大小的空间，而且读取者仍然需要将大量的增量节点应用到基础节点来得到最终结果。与此同时，更高级别的系统将节点合并并连续的写到了新的位置，则 LSS 仍然需要去回收那些旧的版本。

通过对 Bw-Tree 语义的了解，在垃圾回收时，可以通过将多个增量节点应用到基础节点来将其重写为一个单独的基础节点。这减少了Bw-Tree 节点所需要使用的磁盘空间，也降低了读取操作时读取到那些已经被丢弃的页面所造成的延迟。

你可以看到，在仔细考虑的前提下，层次的叠加能够带来许多的益处。并不必须总是要去构建紧凑的单层的结构。良好的 API 跟暴露正确的信息也可以显著的提高性能。

Open-Channel SSDs

一种替换叠加多个软件层次的方案是跳过所有的中间层直接访问硬件。比如可以通过绕开文件系统跟闪存转换层，直接使用 Open-Channel SSDs。使用这种方式我们可以避免至少两层的日志跟对损耗的均衡、垃圾回收、数据的布局跟调度有更多的控制。这种方式的其中一个实现是 LOCS (LSM Tree-based KV Sotre on Open-Channel SSD)。另一个使用 Open-Channel SSDs 的例子是 LightNVM，他是在 Linux 的内核中实现的。

闪存转换层通常要处理数据的布局，垃圾回收跟页的重分配，Open-Channel SSDs 在不通过 FTL 的前提下，暴露出了他的内部信息、驱动管理器跟 I/O 调度信息。虽然从开发人员的角度来看会需要去关注更多的细节，但这个方式可能能带来更直观的性能提升。你可以使用 O_DIRECT 标志来跳过内核的页缓存从而获得更好的控制，但与此同时也意味着需要你去手动的管理页信息。

Software Defined Flash (SDF)，一个硬件/软件签名的 Open-Channel SSDs 系统，公开了一些非对称的接口可以让我们将 SSD 的规则考虑进去。读取跟写入单元的尺寸是不同的，写入单元的尺寸对应于删除单元的尺寸 (块)，这可以大大的减少写放大。这个配置非常合适于结构化日志的存储，因为他只有一个用来执行垃圾回收跟页重分配的软件层级。此外，开发人员可以对 SSD 内部进行并发的访问来提高性能，因为 SDF 中的每个 Channel 都可以作为一个独立的块设备来使用。

将复杂度隐藏在简单的 API 后听起来是非常好的，但在软件层具有不同的语义时也可能带来额外的复杂度。因此公开一些底层系统内部的信息可能对对集成带来更多的好处。