004.精读《Bigtable: A Distributed Storage System for Structured Data》

孙中明

2039人浏览 · 2024-11-03 21:51:18

孙中明 · 2024-11-03 21:51:18 发布

文章目录

1. 引言：

在本期的精读会中，我们将深入解读另一篇具有里程碑意义的论文——《Bigtable: A Distributed Storage System for Structured Data》。这篇论文详细介绍了 Bigtable 作为谷歌用于管理结构化数据的分布式存储系统，其独特的设计使得 Bigtable 能够在数千台服务器上高效地处理 PB 级数据量。作为谷歌多个核心产品的基础架构，Bigtable 在大规模数据处理、分布式存储系统设计中具有重要的参考意义。

通过本文，我们将带领读者：

探讨 Bigtable 在 Google诞生的背景，其出现究竟是为了解决什么样的问题；
深入剖析 Bigtable 的数据模型 和其设计如何实现灵活的存储和访问控制；
解析 Bigtable 在分布式环境中的实现过程底层数据结构；
展望 Bigtable 对 大数据存储系统 的影响及其未来可能的发展方向。

欢迎在评论区分享您的观点与见解，期待与您交流讨论！

2. 精读

2.1 背景

在 GFS 和 MapReduce出现后，仍然很长一段时间内没有在大型的分布式系统上可以高并发、保障一致性，并且支持随机读写数据的系统。

当然在本篇论文出现之前，大多数的分布式数据都是通过MySQL来实现对大规模数据的管理的。如果只是维护一个几十乃至几百台服务器的 MySQL 集群其实也并不为过，但是，如果要像 GFS 维护成千上万的服务器，还有能做到吗？我们可以简单的看一下。

例如，我们建立一个MySQL集群来管理全国的人口信息，可以采用垂直拆分和水平拆分两种策略来进行分布式数据管理。

首先，我们可以按照数据库中的表按照业务逻辑进行拆分，每个拆分出来的数据库（或实例）包含一部分表。这种拆分方式适用于业务模块之间耦合度较低的情况。对于全国人口信息管理，可以按照不同的业务模块（如户籍管理）进行垂直拆分。例如：中国目前有34个省级行政区，那么就可以按照每个省级行政性拆一张表进行数据存储，这样可以减少单个数据库的并发压力，提高查询效率。

但是我们又会发现不同省级行政区的人口数量还不一致，中西部人口普遍少一些一张表可能够用，而沿海多一些可能就不够用，所以我们要进行水平拆分，所以我们可以进行水平拆分，将单张表的数据按照一定的规则分布到多个数据库或表中，每个表仅包含数据的一部分。对于全国人口信息管理，可以按照地域、时间或其他业务规则（如Hash、Range等）将人口信息数据分布到不同的数据库或表中。例如我们可以按照身份证信息对4取模，然后每个省级行政区可以均匀的分配到不同的四张表里面。

后期维护怎么样呢，如果遇到如上世纪六七十年代的生育潮，我们继续对数据进行扩容。如果我们只增加 2 台服务器，把各个服务器的分片，从模上 4 变成模上 6，我们就需要在增加服务器之后，搬运大量的数据，而数据迁移时，可能会遇到带宽和存储压力、服务中断、读写复杂性增加、资源浪费和成本问题。同时缩容的情况也是，其集群的“伸缩性”太差，以及后面的维护性工作也不少。

所以，Bigtable的设计目标就有了：

灵活的资源管理：能够根据实时需求，随时增加或减少服务器数量，以适应业务高峰期和低谷期的变化，实现高效资源利用。
智能的数据分片：系统能够自动根据数据负载进行分片，当某个分片负载过高时，自动拆分以平衡负载；同时，在添加新服务器后，能够迅速重新分配数据，确保所有节点均衡承担压力。
高可用性：即使部分节点发生故障，集群仍能继续运行，确保整个系统的稳定性和可靠性。

现在就引入本文主角：Bigtable 是一个分布式存储系统，用于管理结构化数据，设计可以扩展到极大的规模，涵盖PB级数据并分布在数千台通用服务器上。

众多 Google 产品，包括网页索引、Google Earth 和 Google Finance，都使用 Bigtable 进行数据存储。尽管这些应用对 Bigtable 的需求差异很大——无论是从数据大小（从 URL 到网页，再到卫星图像）还是延迟要求（从后台批量处理到实时数据服务）来看，Bigtable 依然为这些产品提供了一个灵活且高性能的解决方案。

实际上，Bigtable 并不是传统意义上的“表（table）”。在其底层，数据的物理存储形式是一个排序的 Map。该 Map 的 key 由行关键字、列关键字和时间戳组成的复合结构，而 value 则是一个简单的字符串：(row:string, column:string, time:int64) → string。

Bigtable 提供了一个简单的数据模型，允许客户端动态控制数据的布局和格式，从而满足各种应用场景的需求。

2.2 数据模型

所以为了解决上述的问题， Bigtable设计了一个数据模型：一个稀疏、分布式、持久的多维有序映射表（map），数据通过行键、列键和时间戳进行索引。表中的每个数据项都是不作理解的字节数组，映射关系为：
(row:string, column:string, time:int64) → string

A Bigtable is a sparse, distributed, persistent multidimensional sorted map. The map is indexed by a row key, column key, and a timestamp; each value in the map is an uninterpreted array of bytes.

在 Bigtable 中，每条数据都通过一个行键（Row Key）进行标识，这相当于数据库的主键。Bigtable 提供了通过行键进行随机读写的接口，这也是为什么很多人将这种数据库称为 KV（键值）数据库的原因。

每一行数据需要指定一个或多个列族（Column Family）。在这些列族下，你无需预先定义具体的列（Column）。这意味着每一行数据可以拥有不同的列集，列的存在与否取决于是否有值。如果某个列没有值，那么在底层存储中就不会记录这个列。这种特性使得 Bigtable 成为一种“稀疏”表。

Bigtable 允许在列下存储多个版本的数据，每个版本都附带有时间戳（Timestamp）。你可以选择保留最近的 N 个版本，比如保留时间戳最近的三个版本；或者，你也可以指定保留某个时间点之后的所有版本。这种灵活的版本管理为数据的历史追踪与恢复提供了便利。

举个例子：创建了一个表，称之为 Webtable，在 Webtable 中，使用网页的 URL 作为行键，网页的某些信息作为列键。网页内容存储在 contents: 列中，并且每次抓取时记录相应的时间戳。最终的存储布局如上图所示。

行索引：使用 URL 作为行键。
contents: 列：存储页面内容（page content）。
anchor: 开头的列：存储引用了该页面的 anchor（HTML 锚点）的文本（text of the anchors that reference this page）。

如图所示，CNN 的主页被 Sports Illustrated（cnnsi.com）和 MY-look 主页（my.look.ca）引用，因此表中有 anchor:cnnsi.com 和 anchor:my.look.ca 两列，每列包含一个版本。与此同时，contents: 列有三个版本，时间戳分别为 t3、t5 和 t6。

行键（Row Key）

行键（row key） 在 Bigtable 中可以是任意字符串，当前最大支持 64KB，大多数用户的行键长度在 10-100 字节之间。对于同一行的读写操作是原子的，无论该行涉及多少列，原子性设计确保了在多个客户端并发更新同一行时，系统行为的可预见性。

数据组织 上，Bigtable 根据行键的词典顺序（lexicographic order）进行存储，并会根据需要动态切分行范围（row range）。每个行范围称为一个 tablet，它是分布和负载均衡的基本单位。因此，读取较小的行范围通常非常高效，只需与少量机器进行通信即可。客户端可以通过合理选择行键，优化数据访问的本地性（locality）。

例如，在 Webtable 中，通过翻转 URL 的 hostname 字段，来自同一域名的页面将会存储在连续的行中。举个例子，maps.google.com/index.html 的行键会存储为 com.google.maps/index.html。这种存储方式不仅优化了存取效率，还使得针对主机和域的分析（host and domain analyses）变得更加高效。

列族（Column Family）

列族column key 的格式：family:qualifier

family 必须为可打印的（printable）字符串，
qualifier（修饰符）可以为任意字符串。

多个 column keys 可以组织成 column families（列族）。 column family 是访问控制（access control）的基本单位。

时间戳（Timestamp）

在 Bigtable 中，每个数据项可以存储多个版本，使用时间戳进行索引。

时间戳为一个 64 位整数，既可以由 Bigtable 自动生成（表示毫秒级的真实时间戳），也可以由客户端应用自行指定。为了避免冲突，客户端必须确保时间戳的唯一性。

不同版本的数据按照时间戳降序存储，确保每次读取时，最新版本总是优先返回。

为了简化版本化数据的管理，Bigtable 提供了两个配置选项，使系统能够自动执行垃圾回收（GC）。客户端可以指定：

保留最新的 N 个版本；
保留指定时间段内的版本（例如，只保留过去 7 天内写入的版本）。

随机读写的接口

Bigtable API 提供了创建和删除表及列族的功能。此外，它还允许更改集群、表和列族的元数据，例如访问控制权限。
下面代码块展示了一段向 Bigtable 写入数据的 C++ 代码，使用 RowMutation 抽象来执行一系列更新操作。为保持代码简洁，例子中省略了一些无关的技术细节。

// 打开指定路径的表，如果表不存在则创建它
Table* T = OpenOrDie("/bigtable/web/webtable");
// 创建一个行对象，用于对指定行进行修改
RowMutation r1(T, "com.cnn.www");
// 在指定的列族和列键下设置一个值
// 这里设置列族为"anchor"，列键为"www.c-span.org"，值为"CNN"
r1.Set("anchor:www.c-span.org", "CNN");
// 在指定的列族和列键下删除一个值
// 这里删除列族为"anchor"，列键为"www.abc.com"的数据
r1.Delete("anchor:www.abc.com");
// 创建一个操作对象，用于存储对行的修改操作
Operation op;
// 应用之前定义的修改操作到表中
Apply(&op, &r1);

Apply() 方法对 Webtable 执行一次原子操作，包括添加一个 anchor 到 www.cnn.com，并删除另一个 anchor。

下面代码块展示了另一个例子，使用 Scanner 抽象遍历一行内的所有 anchor。

// 创建一个扫描器对象，用于扫描表中的数据
Scanner scanner(T);
// 声明一个扫描流对象，用于获取特定列族的数据
ScanStream* stream;
// 使用扫描器获取名为"anchor"的列族数据
stream = scanner.FetchColumnFamily("anchor");
// 设置扫描流返回所有版本的数据
stream->SetReturnAllVersions();
// 使用扫描器查找特定行的数据
scanner.Lookup("com.cnn.www");
// 遍历扫描流中的数据，直到到达流的末尾
for (; !stream->Done(); stream->Next()) {
    // 打印行名、列名、微秒级时间戳和数据值
    printf("%s %s %lld %s\n",
        scanner.RowName(),            // 行名
        stream->ColumnName(),        // 列名
        stream->MicroTimestamp(),    // 微秒级时间戳
        stream->Value());             // 数据值
}

客户端可以在多个列族（column family）上进行遍历，并通过多种机制限制 scan 的结果行、列和时间戳。例如，可以指定 scan 只产生列键匹配正则表达式 anchor:*.cnn.com 的 anchors，或时间戳在最近 10 天内的 anchor。

2.3 实现过程

将数据表根据其主键的不同，分散存储于多个服务器上，在分布式数据库领域，这一做法被称为数据分区（Partitioning）。分区后的数据片段，在不同的分布式系统中有着不同的称呼。在MySQL中，我们通常称之为Shard，而在Bigtable中，则被称为Tablet。

MySQL集群在分区时会对某个字段进行哈希处理，然后根据结果将其分配到预先设定的N个分片中。这种方法最大的弊端在于，分区策略需要在一开始就被设计好，而不是能够随着数据的变化而自动调整。然而计划赶不上变化。一旦我们的业务发展与最初的计划有所偏差，就可能需要进行数据迁移，或者面临分片间负载不均衡的问题。

在Bigtable中，采用了一种不同的分区策略，即动态区间分区。这种方法不再需要在一开始就确定分区的数量和具体的分区方式，而是通过自动“分裂”（split）和“合并”（merge）的方式来动态调整分区。Bigtable会根据行键对整个数据表进行排序，然后按照连续的行键区间进行分区。如果某个区间内的数据量不断增加，导致存储空间需求增大，系统会自动将这个区间的分区分裂成两个更小的分区。相反，如果某个区间的数据被大量删除，占用的空间减少，系统则会将这个区间的分区与相邻的分区合并，以优化存储和性能。

若要实现上述功能，需要依赖于Bigtable系统架构中的关键组件，如下图所示，包括GFS、Chubby、Tablet Server和Master等。这些组件共同构成了Bigtable的核心架构，确保了数据的高效存储、管理和访问。

GFS（Google File System）：承担着存储数据的核心职责。

GFS 是 Google 内部开发的分布式文件系统，专为处理大规模数据而设计。它通过将数据分成块并在多个服务器上复制，提供了高可用性和容错性。在 Bigtable 中，GFS 负责存储所有的数据文件和日志文件。每个操作都会被记录在日志中，确保即使在服务器故障时数据也不会丢失。

GFS 的设计使其能够处理大规模的数据流和批量处理任务。通过使用标准的硬件和软件，GFS 显著降低了运营成本，同时提高了系统的整体效率。（来自：002.精读《The Google File System》| 大数据的三驾马车之一：GFS）

数据存储：GFS负责存储Bigtable中的实际数据。
数据持久化：确保数据在系统故障时不会丢失，通过在多个位置存储数据副本。
高可用性：提供高可用的数据访问，即使部分硬件或服务器出现问题，数据依然可以被访问。
大规模数据处理：支持Bigtable处理和存储PB级别的大数据。
数据块管理：将数据分割成块，便于管理和在多个服务器间复制，以提高效率和可靠性。

Chubby：扮演着分布式锁和目录服务的角色，确保系统的协调和一致性。

A Chubby service consists of five active replicas, one of which is elected to be the master and actively serve requests.Chubby uses the Paxos algorithm to keep its replicas consistent in the face of failure.Chubby provides a namespace that consists of directories and small files.Each directory or file can be used as a lock, and reads and writes to a file are atomic.

Chubby服务由五个副本构成，其中一个副本担任master角色，负责处理所有请求。Chubby采用Paxos算法来确保副本之间的数据一致性。它提供的命名空间由目录和小型文件组成，这些可以被用作锁，并且支持原子性的读写操作。客户端通过建立会话与Chubby服务进行交互，如果会话超时，则会导致失去锁和句柄。Bigtable利用Chubby来确保只有一个活跃的master，存储数据的启动位置，发现tablet服务器，维护架构信息以及存储访问控制列表（ACLs）。

The average percentage of Bigtable server hours during which some data stored in Bigtable was not available due to Chubby unavailability (caused by either Chubby outages or network issues) was 0.0047%. The percentage for the single cluster that was most affected by Chubby unavailability was 0.0326%.

长时间的 Chubby 不可用会导致 Bigtable 不可用，但这种情况很少见，影响极小。

维护单一Master实例：确保系统中仅存在一个Master，以保持集群的一致性和稳定性。
管理Bigtable数据的引导位置（Bootstrap Location）：负责存储Bigtable数据的启动位置信息，以便快速引导和恢复。
监控Tablet Server的生命周期：发现新加入的Tablet Servers，并在它们停止服务后完成必要的清理工作。
维护Bigtable的Schema信息：负责存储和管理Bigtable的Schema信息，确保数据结构的准确性和一致性。
管理ACL（访问控制列表）：存储Bigtable的访问权限（ACL），控制用户对数据的访问，保障数据安全。

Tablet Server：直接提供在线服务，处理实际的数据操作。

处理数据请求：响应客户端的读写请求。
存储数据：保存和管理分配给它的数据片段（Tablets）。
数据分裂与合并：根据数据量自动分裂大的Tablet或合并小的Tablet。
数据复制：确保数据在多个服务器间复制，以提高数据的可靠性。
查询执行：执行数据查询并返回结果。
故障恢复：在发生故障时快速恢复服务。
负载均衡：与Master Server合作，动态调整数据分布以平衡负载。

Master：负责调度Tablet的分配和负载均衡，以优化整体性能。

分配Tablets至Tablet Server：负责将Tablets指派给相应的Tablet Server。
监控Tablet Server的动态：检测并处理Tablet Server的加入与退出。
负载均衡：平衡各个Tablet Server的负载，确保资源的高效利用。
数据垃圾回收：在GFS上执行数据的垃圾回收（Garbage Collection, GC），以维护数据的整洁和存储空间的有效利用。
管理Schema变更：负责表（Table）和列族（Column Family）的Schema变更管理，包括创建和删除表以及列族。

The first level is a file stored in Chubby that contains the location of the root tablet.
The root tablet contains the location of all tablets in a special METADATA table.
The root tablet is just the first tablet in the METADATA table, but is treated specially—it is never split—to ensure that the tablet location hierarchy has no more than three levels.

使用三级层次结构存储tablet的位置信息，类似于B+树。这包括存储在Chubby中的根tablet位置、METADATA表中的tablet位置，以及用户tablet的位置。

第一层：一个存储在Chubby中的文件，其中包含了根tablet（root tablet）的位置信息。这个文件作为整个系统的入口点，用于快速定位根tablet。
第二层：根tablet在一个特殊的METADATA表中，包含了所有其他tablet的位置信息。根tablet是METADATA表中的第一个tablet，但它被特殊对待，因为它永远不会被分裂（split），这样可以确保tablet位置层次结构不超过三层。
第三层：每个METADATA tablet（除了根tablet包含一组用户tablet的位置信息。这些METADATA tablets负责存储用户数据表中tablet的位置信息，使得客户端能够根据这些信息定位到具体的数据。

If the client’s cache is empty, the location algorithm requires three network round-trips, including one read from Chubby.If the client’s cache is stale, the location algorithm could take up to six round-trips.

客户端库通过缓存tablet位置信息来提升访问效率。当缓存信息失效时，它会递归查询tablet位置层级。初次查找通常需要三次网络往返，而缓存信息过期时可能需要多达六次网络往返——这种情况通常发生在缓存未命中时，且前提是METADATA tablets的移动不是非常频繁。为了优化性能，客户端库在读取METADATA表时会预先获取多个tablet的位置信息。这样可以减少未来的网络往返次数，提高整体的数据访问效率。

如果客户端缓存为空：当客户端的缓存中没有存储任何关于tablet位置的信息时，客户端需要执行一个定位算法来确定数据的位置。这个过程需要三次网络往返（round-trips）：
1. 第一次网络往返可能是客户端向Chubby请求根tablet的位置。
2. 第二次网络往返是客户端根据Chubby提供的信息去请求METADATA表中的相应tablet位置。
3. 第三次网络往返是客户端根据METADATA表中的位置信息去请求实际的数据。
如果客户端缓存过时：当客户端缓存的信息已经不再有效（即缓存过时）时，客户端需要更新其缓存以获取最新的tablet位置信息。这个过程可能需要多达六次网络往返：
1. 第一次网络往返可能是客户端尝试使用缓存中的信息去请求数据。
2. 当发现缓存信息过时后，客户端需要重新查询Chubby以获取最新的根tablet位置。
3. 第二次网络往返是客户端根据Chubby提供的最新信息去请求METADATA表中的相应tablet位置。
4. 第三次网络往返是客户端根据METADATA表中的位置信息去请求实际的数据。
5. 如果在请求数据的过程中发现METADATA表中的信息也过时了，客户端可能需要额外的网络往返来更新METADATA表中的信息。
6. 最后，客户端再次根据更新后的METADATA表信息去请求实际的数据。

让我们通过一个具体的例子来说明Bigtable的读写流程：

读流程实例：

假设我们有一个在线书店，想要查询某个特定书籍的信息。

客户端请求：
- 用户在书店网站上搜索《月亮与六便士》这本书的详细信息。
客户端定位数据：
- 客户端（网站服务器）的缓存中没有这本书的库存信息，因此它需要查询Bigtable。
- 客户端首先查询Chubby以获取根tablet的位置信息。
获取METADATA信息：
- 客户端使用根tablet找到METADATA表中负责书籍信息的tablet位置。
- 客户端可能需要查询多个METADATA tablets，直到找到正确的tablet位置。
请求Tablet Server：
- 客户端向托管该tablet的Tablet Server发送读取请求。
Tablet Server处理请求：
- Tablet Server在本地查找《月亮与六便士》的数据，如果数据不在内存中，它会从GFS中读取。
返回数据给客户端：
- Tablet Server将书籍的详细信息返回给客户端，客户端随后将这些信息展示给用户。

写流程实例：

现在，假设书店想要更新《月亮与六便士》的库存数量。

客户端请求：
- 书店的库存管理系统减少了《月亮与六便士》的库存数量。
写入数据：
- 客户端（库存管理系统）将更新请求发送给托管目标tablet的Tablet Server。
Tablet Server处理写入：
- Tablet Server接收到更新请求，将新的库存数量写入其管理的Tablet。
- Tablet Server还会将这个更新复制到其他副本，以保证数据的一致性和可靠性。
数据分裂和合并：
- 如果这个tablet因为频繁的写入操作变得太大，Tablet Server会将其分裂成两个新的tablets。
- 如果这个tablet因为数据删除变得太小，可能会与相邻的tablet合并。
更新METADATA：
- 写入操作完成后，相关的METADATA信息会被更新，以反映库存数据的新位置。
返回写入结果给客户端：
- Tablet Server确认写入操作成功，并返回结果给客户端，客户端随后更新库存管理系统中的状态。

2.4 底层结构

Bigtable内部采用Google的SSTable格式来存储数据。SSTable是一种持久化、有序且不可变的键值存储结构，其中键和值均可以是任意的字节字符串序列。它支持通过键进行查询以及对指定键范围进行遍历。

An SSTable provides a persistent, ordered immutable map from keys to values, where both keys and values are arbitrary byte strings.A lookup can be performed with a single disk seek: we first find the appropriate block by performing a binary search in the in-memory index, and then reading the appropriate block from disk.

SSTable由多个数据块构成，每个块的标准大小为64KB，但这个大小是可配置的。这些数据块通过位于SSTable文件末尾的块索引来定位，当SSTable被打开时，这个索引会被加载进内存。查询操作仅需一次磁盘查找：首先在内存中的索引里通过二分查找确定所需数据块的位置，然后直接从磁盘读取该数据块。此外，SSTable文件可以被完整地映射到内存中，这样可以实现无需磁盘I/O的快速数据查找和范围扫描，从而大幅提升性能。

Bigtable实际写入数据的过程如下：

当一个写请求到来时，Tablet Server 首先执行基础的数据验证，包括检查数据格式是否合法，以及确认发起请求的客户端是否有权限进行对应的操作。这个权限设置，是 Tablet Server 从 Chubby 中获取到，并且缓存在本地的。
如果写入的请求是合法的，对应的数据写入请求会以追加写的形式，写入到 GFS 上的提交日志文件中，这个写入对于 GFS 上的硬盘来说是一个顺序写。在这个阶段，我们便认为整个数据写入就已经成功了。
提交日志写入成功后，Tablet Server 会再把数据写入到一张内存表中，也就是我们常说的 MemTable。随着写入的数据量增加，当达到预设的阈值时，Tablet Server 会把当前内存里的整个 MemTable 冻结，然后创建一个新的 MemTable。
被冻结的这个 MemTable，一般被叫做 Immutable MemTable，它会被转化成一个叫做 SSTable 的文件，写入到 GFS 上，然后再从内存里面释放掉。这个写入过程，是完整写一个新文件，所以自然也是顺序写。如果在上述第2步，也就是提交日志写入完成之后，Tablet Server 因为各种原因崩溃，那么在重启时，可以通过重新播放提交日志来恢复 MemTable 中的数据。

实际上，Bigtable在处理数据时，并不会直接修改已写入的数据。无论是插入还是更新操作，我们都是在追加新版本的数据。删除操作也只是写入一个墓碑标记，这本质上也是添加了一个特殊的新版本数据。数据的“修改”和“删除”主要在两个阶段发生：

Major Compaction 机制：根据前面描述的数据写入机制，随着数据不断写入，会产生越来越多的SSTable文件。为了减少这些文件占用的GFS硬盘空间，后台进程会不断对这些SSTable文件进行合并，这个过程称为Major Compaction，意为“压实”数据。例如，如果有10个文件中都包含了com.cnn.www这个行键的多个版本数据，合并后，根据设定的数据保留策略，我们可能只保留时间戳最新的三个版本。在这个过程中，旧版本的数据在物理上被真正删除。
读取数据时的合并视图：在读取数据时，我们实际上是从MemTable和多个SSTable文件中读取数据，形成一个合并视图。也就是说，我们从MemTable和所有相关的SSTable中获取对应行键的数据后，在内存中合并这些数据，并根据时间戳或墓碑标记对数据进行“修改”和“删除”，然后将处理后的数据返回给客户端。

综上： Bigtable将硬盘的随机写操作转化为顺序写操作。这是通过提交日志（Commit Log）以及将内存表（MemTable）输出到磁盘的Minor Compaction机制实现的。同时利用局部性原理最近写入的数据会保留在内存表中，以便快速访问。这样可以减少对磁盘的直接访问，提高数据读取速度。并且，对于不存在的行键查询，Bigtable使用内存中的布隆过滤器（BloomFilter）进行快速过滤，这样可以减少不必要的磁盘随机访问次数，提高查询效率。

MemTable 的数据结构通常是通过一个 AVL 红黑树，或者是一个 Skip List 来实现的。而 Bigtable 的 MemTable 和 SSTable 的源码，一般被认为就是由 Google 开源的 LevelDB 来实现的。在实际的 LevelDB 源码中，MemTable 是选择使用 Skip List 来作为自己的数据结构。之所以采用这个数据结构，原因也很简单，主要是因为 MemTable 只有三种操作：

随机数据插入：第一种是根据行键的随机数据插入，这个在数据写入的时候需要用到；
随机数据读取：第二种是根据行键的随机数据读取，这个在数据读取的时候需要用到；
有序遍历：最后一种是根据行键有序遍历，这个在我们把 MemTable 转化成 SSTable 的时候会被用到。

AVL 红黑树和 Skip List 在这三种操作上，性能都很好，随机插入和读取的时间复杂度都是 O(logN)，而有序遍历的时间复杂度，则是 O(N)。

当MemTable的大小超出预设阈值之后，我们会进行一次转换过程，将其变成一个名为SSTable的文件。SSTable的文件格式其实非常简洁明了，它主要包含以下两个核心部分：

数据块（Data Block）：
- 第一部分是实际存储的数据，包括行键、列、值以及时间戳。这些数据按照行键的顺序排序，并被分割成固定大小的块进行存储。在SSTable中，这部分内容被称为数据块。数据块的设计允许高效地存储和检索结构化数据，同时保持数据的有序性，这对于范围查询和随机访问都是非常重要的。
元数据和索引信息：
- 第二部分包含一系列的元数据和索引信息。其中包括用于快速过滤掉SSTable中不存在的行键的Bloom Filter，以及包含整个数据块的一些统计指标，这些统称为元数据块（Meta Block）。
- 另外，还有针对数据块和元数据块的索引，分别为元数据索引块（Metaindex Block）和数据索引块（Index Block）。这些索引使得客户端能够快速定位到具体的数据块，极大地提高了数据检索的效率。

SSTable的数据顺序存储简化了Major Compaction过程，只需进行多路归并排序，有效减少了随机硬盘访问，提升了读写效率。在查询数据时，我们首先利用索引定位到数据块，然后从中提取所需的KV数据，并将其返回给客户端。此外，我们还对压缩和缓存机制进行了优化：通过压缩算法，我们牺牲一定的CPU资源来减少存储和缓存空间的需求。SSTable中的布隆过滤器被缓存在Tablet Server中，以便快速判断行键是否存在。Bigtable实现了两级缓存机制：Scan Cache用于缓存查询结果，而Block Cache则缓存整个数据块，这两者都提高了数据访问的效率。这些缓存机制不受新写入数据的影响，因为新数据被存储在MemTable中，不会干扰SSTable的缓存。