Concurrency in LSM Trees

LSM Tree 并发的主要挑战在于表视图间的切换 (即驻留在内存跟磁盘的表集合的刷新跟压缩) 跟日志的同步。Memtables 通常都是可以并发访问的 (除了类似 ScyllaDB 那种 core-partitioned store)，只是内存数据结构的并发访问并不在本书的范畴内。

在刷新时需要遵循以下规则：

• 使用新的 Memtable 来提供读取跟写入支持
• 旧的 (刷新中的) Memtable 会被写入磁盘
• 刷新后丢弃 Memtable 以及创建驻留于磁盘的表需要以原子操作来完成
• 预写日志中包含了被刷新的 Memtable 部分的日志条目需要被丢弃

比如说，Apache Cassandra 通过使用 Operation order barriers 操作顺序屏障 来解决上面的问题：所有被接受的写操作需要等待，直到他对应的前一个 Memtable 被刷新。使用这个方式负责刷新的处理器 (作为消费者) 就能够知道其他哪些处理者*(作为消费者)*是依赖于他的 。

更通用的说，我们需要遵守下面的同步的关键点：

• Memtable Switch

  在这个操作之后，所有的写入只会发生在新的 Memtable 中，让他作为主表，同时旧的表仍然会提供读取操作。

• Flush finalization

  在表的视图中替换旧的 Memtable 所产生的驻留磁盘的表

• Write-ahead log truncation

  丢弃跟被刷新的 Memtable 关联的日志段

以上的操作需要严格的保证其正确性。对旧的 Memtable 进行写入的话可能会导致数据的丢失，比如将信息写入到已经被刷新的 Memtable 中。类似的，如果旧的 Memtable 在驻留磁盘的表未完成前不能提供读取操作，则会导致读取得到不完整的结果。

在压缩过程中，表的视图也是会发生改变的，不过这部分会稍微直观一些：旧的驻留磁盘的表会被丢弃，并使用压缩后的版本来进行替换。旧的表在新的表完全写入并准备好进行替换前，仍需要提供读取的操作。还有一种情况是需要避免的，就是不能够让同一个表同时参与到多个并行的压缩中。

在 B-Tree，日志的截断需要跟从页缓存中刷新脏页进行协调，来保证数据的持久性。在 LSM Tree 中，我们有一个类似的要求：写入都会被缓存到 Memtable 中，并且他们的内容在完全刷新前是没有被持久化的，因此日志的截断需要与 Memtable 的刷新进行协调。在刷新完成的同时，日志管理器会提供最新刷新的日志段的相关信息，这时他的内容才可以被安全的丢弃。

不对刷新跟日志截断进行同步也会导致数据的丢失：如果日志段在刷新完成前被丢弃，这时节点崩溃了，日志的内容就无法被拿来进行重演，因此这个段内的数据也就无法恢复了。