一、概述

现代数据库系统通过利用复杂的存储引擎来写入和读取数据，旨在保证一组功能，例如可靠性、一致性、高吞吐量等。

在本教程中，我们将深入研究Apache Cassandra 使用的存储引擎的内部结构，该引擎专为写入繁重的工作负载而设计，同时还保持良好的读取性能。

2. 对数结构的合并树（LSMT）

Apache Cassandra 利用基于日志结构合并树的两级数据结构进行存储。在高层次上，这样的LSM 树中有两个树状组件，一个内存缓存组件(C 0 ) 和一个磁盘组件(C 1 )：

直接从内存读取和写入通常比磁盘快。因此，按照设计，所有请求在到达C 1之前都会先到达C 0 。此外，同步操作会定期将数据从C0 持久化到C1。因此，它通过减少I/O 操作来有效地使用网络带宽。

在接下来的部分中，我们将详细了解Apache Cassandra 中两级LSM 树的C 0和C 1数据结构，通常分别称为MemTable 和SSTable。

3. 内存表

顾名思义，MemTable 是一种驻留内存的数据结构，例如具有自平衡二叉搜索树属性的红黑树。因此，所有的读写操作，即搜索、插入、更新和删除，都可以以O(log n) 的时间复杂度实现。

作为内存中的可变数据结构，MemTable 使所有写入顺序并允许快速写入操作。此外，由于物理内存的典型限制，例如容量有限和易失性，我们需要将数据从MemTable 持久化到磁盘：

一旦MemTable 的大小达到阈值，所有的r/w 请求都会切换到新的MemTable，而旧的MemTable 在刷新到磁盘后被丢弃。

到目前为止，一切都很好！我们可以有效地处理大量写入。但是，如果节点在刷新操作之前崩溃，会发生什么？好吧，这很简单——我们会丢失尚未刷新到磁盘的数据。

在下一节中，我们将看到Apache Cassandra 如何通过使用预写日志(WAL) 的概念来解决这个问题。

4. 提交日志

Apache Cassandra 推迟了将数据从内存持久保存到磁盘的刷新操作。因此，意外的节点或进程崩溃可能导致数据丢失。

持久性是任何现代数据库系统的必备能力，Apache Cassandra 也不例外。它通过确保所有写入在名为Commit Log 的仅附加文件中持久保存到磁盘上来保证持久性。此后，它使用MemTable 作为写路径中的回写缓存：

我们必须注意，仅附加操作速度很快，因为它们避免了磁盘上的随机寻道。因此，Commit Log 在不影响写入性能的情况下带来了持久性能力。此外，Apache Cassandra 仅在崩溃恢复场景中引用Commit Log，而常规读取请求不会进入Commit Log。

5. SSTable

排序字符串表(SSTable) 是Apache Cassandra 存储引擎使用的LSM 树的磁盘驻留组件。它的名称来源于一个类似的数据结构，首先由Google 的BigTable 数据库使用，并表明数据以排序格式提供。一般来说，来自MemTable 的每个刷新操作都会在SSTable 中生成一个新的不可变段。

让我们尝试可视化SSTable 在包含有关动物园中饲养的各种动物数量的数据时的外观：

尽管这些段是按键排序的，但是，相同的键可能存在于多个段中。因此，如果我们要查找特定的键，我们需要从最新的段开始搜索，并在找到后立即返回结果。

使用这样的策略，对最近写入的键的读取操作会很快。然而，在最坏的情况下，算法的执行时间复杂度为O( N*log( K))，其中N是段的总数，K是段的大小。由于K是常数，我们可以说整体时间复杂度为O( N)，效率不高。

在接下来的几节中，我们将了解Apache Cassandra 如何优化SSTable 的读取操作。

6.稀疏索引

Apache Cassandra 维护一个稀疏索引，以限制在查找键时需要扫描的段数。

稀疏索引中的每个条目都包含段的第一个成员，以及它在磁盘上的页面偏移位置。此外，索引作为B-Tree 数据结构保存在内存中，因此我们可以在O(log( K)) 时间复杂度的索引中搜索偏移量。

假设我们要搜索关键字“beer”。我们将从搜索稀疏索引中出现在单词“beer”之前的所有键开始。之后，使用偏移值，我们将只查看有限数量的段。在这种情况下，我们将查看第一个键是“鳄鱼”的第四段：

另一方面，如果我们必须搜索诸如“kangaroo”之类的缺失键，我们就必须徒劳地查看所有片段。因此，我们意识到使用稀疏索引在有限程度上优化了搜索。

此外，我们应该注意到SSTable 允许相同的键出现在不同的段中。因此，随着时间的推移，同一个键会发生越来越多的更新，从而在稀疏索引中也会产生重复的键。

在接下来的部分中，我们将了解Apache Cassandra 如何在布隆过滤器和压缩的帮助下解决这两个问题。

7. 布隆过滤器

Apache Cassandra 使用称为布隆过滤器的概率数据结构优化读取查询。简而言之，它通过首先使用布隆过滤器对键执行成员资格检查来优化搜索。

因此，通过将布隆过滤器附加到SSTable 的每个段，我们将为我们的读取查询获得显著优化，特别是对于段中不存在的键：

由于布隆过滤器是概率数据结构，我们可以得到“可能”作为响应，即使是缺少键也是如此。但是，如果我们得到“否”作为响应，我们可以确定密钥肯定丢失了。

尽管有它们的局限性，我们可以计划通过为它们分配更大的存储空间来提高布隆过滤器的准确性。

8. 压实

尽管使用了布隆过滤器和稀疏索引，但读取查询的性能会随着时间的推移而下降。这是因为包含不同版本的键的段的数量可能会随着每个MemTable 刷新操作而增加。

为了解决这个问题，Apache Cassandra 运行了一个后台压缩过程，将较小的排序段合并为较大的段，同时只保留每个键的最新值。因此，压缩过程具有更快读取和更少存储的双重好处。

让我们看看在我们现有的SSTable 上执行一次压缩会是什么样子：

我们注意到压缩操作通过只保留最新版本回收了一些空间。例如，“elephant”和“tiger”等旧版本的键不再存在，从而释放了磁盘空间。

此外，压缩过程可以硬删除键。虽然删除操作会用墓碑标记键，但实际删除会延迟到压缩。

9. 结论

在本文中，我们探索了Apache Cassandra 存储引擎的内部组件。在此过程中，我们了解了LSM Tree、MemTable 和SSTable 等高级数据结构概念。此外，我们还学习了一些使用预写日志、布隆过滤器、稀疏索引和压缩的优化技术。