为什么需要 Kudu

在 Hadoop 生态中结构化的数据通常使用两种方式进行存储：一是通过 Apache Parquet 等二进制数据格式，将静态数据集存储在 HDFS 上，二是将可变数据以半结构化的方式存储在 HBase 中。这里面临的问题是存储在 HDFS 上的数据无法提供单个记录的随机访问，HBase 中存储的数据尽管允许低延迟的读取和写入，但是基于 SQL 分析的应用中顺序读取的吞吐方面要远远落后于静态文件格式。

当需要在一个系统中需要这两种访问模式的时候，HDFS 上的静态数据集提供的分析性能力与 HBase 的低延迟行级随机访问能力之间的差距就需要复杂的架构设计，一种可以想到的方式就是采用类似于 Lambda 架构的方案：架构中通过 HBase 构建一个实时层，通过 HDFS 构建一个批处理层。数据流式的进入实时层，然后定期将数据导入到 Parquet 批处理层，以提供历史分析。这一架构看似能够解决这个差异性的问题，但是却有这样几个缺点：

  1. 由于要管理两个层的数据流之间的同步，这样应用层的架构会变得复杂；
  2. 需要跨两个系统管理一致性备份、安全和监控；
  3. 新数据达到数据在实时层和可用于分析的批处理层之间会表现出滞后；
  4. 现实世界中，系统需要容纳后到达的数据、还需要对迁移到不可变存储中数据进行删除，这一过程会设计到昂贵的分区重写以及手动干预。

为了解决上面的问题，Kudu 被设计以一种折中的方式解决这些问题。Kudu 是一种全新设计和实现的新存储系统，旨在填补 HDFS 等高吞吐量顺序访问存储系统与 HBase 或 Cassandra 等低延迟随机访问系统之间的空白。特别是，Kudu 为行级插入、更新和删除提供了一个简单的 API，同时以类似于 Parquet的吞吐量提供表扫描。

用户视角下的 Kudu

表与模式

在用户视角下，Kudu 是一个结构化数据表的存储系统，可以有任意数量的表，每个表都有一个由有限数量的列组成的明确定义的模式。每列具有列名和类型。对于列设置类型有这样两个好处：

  1. 特定的类型在进行列式存储的时候可以进行充分的压缩；
  2. 显式类型允许我们将类似 SQL 的元数据公开给其他系统。

Kudu 表有主键，主键负责唯一性约束，并充当更新和删除行的唯一索引。同样与关系型数据库类似的是，用户在创建表的时候需要定义表的架构，插入不存在的列或者违反主键唯一性约束都会引起错误，用户可以添加删除列但是不能删除主键列。

与关系型数据库不同的是 Kudu 表不提供二级索引。

写操作

创建表之后的写操作必须指定主键，Kudu 提供了多种语言的客户端。这些 API 允许精确控制批处理和异步错误处理，以在执行批量数据操作（例如数据加载或大型更新）时分摊往返成本。Kudu 不提供跨行事务。

读操作

Kudu 提供 Scan 操作从表中检索数据，扫描时，用户可以添加谓词进行过滤，支持列和常量值之间的比较以及主键范围，谓词操作会下推到 Kudu 后台，减少数据扫描传递时的磁盘和网络开销。

Kudu 支持指定扫描的投影，投影由要检索的列的子集组成。由于 Kudu 是列式存储的，这样可以显著提高分析负载的性能。

其他 API

除了 data path 相关的 API API 之外，Kudu 客户端库还提供其他有用的功能。特别是，Hadoop 生态系统通过数据局部性调度获得了很大的性能。 Kudu 为调用者提供 API 来确定数据范围到特定服务器的映射，以帮助分布式执行框架（例如 Spark、MapReduce 或 Impala）进行调度。

一致性模型

Kudu 提供两种一致性模型: 快照一致性 (snapshot consistency)和外部一致性 (external consistency guarantee)。

默认情况下，Kudu 不提供外部一致性保证。也就是说，如果一个客户端执行写入，然后通过外部机制（例如消息总线）与另一个客户端通信，而另一个客户端执行写入，则不会捕获两个写入之间的因果关系。第三个读者可能会看到包含第二次写入而没有第一次写入的快照。

外部一致性则是需要用户额外的代码实现的，对于需要更强保证的用户，Kudu 提供了在客户端之间手动传播时间戳的选项：执行写入后，用户可以向客户端库请求时间戳令牌。该令牌可以通过外部通道传播到另一个客户端，并传递到另一端的 Kudu API，从而保留跨两个客户端进行的写入之间的因果关系。

如果传播令牌太复杂，Kudu 可以选择使用提交等待，类似 Spanner 。在启用提交等待的情况下执行写入后，客户端可能会延迟一段时间，以确保任何后续写入都将按因果顺序正确排序。这个方案需要用户做 NTP 时间校准，如果没有专门的计时硬件，这可能会导致显着的写入延迟（默认 NTP 配置为 100-1000 毫秒）。

时间戳

虽然Kudu内部使用时间戳来实现并发控制，但是Kudu不允许用户手动设置写操作的时间戳。但是，我们允许用户为读取操作指定时间戳。这允许用户在过去执行时间点查询，并确保共同构成单个“查询”的不同分布式任务（例如在 Spark 或 Impala 中）读取一致的快照。

架构

集群角色

类似 GFS、HDFS、HBase 等开源实现，Kudu 依赖于一个维护元数据的单个 Master server 和任意数量的维护数据的 Tablet server。 Master server 通过被复制用于容错，在发生故障时支持快速故障转移。

分区

Kudu 表是水平分区的，这些分区称为 tablets，每行可以根据其主键精准的映射到一个 tablet，这个保证随机访问操作仅影响单个 tablet。对于一些大表，吞吐量很重要，一件每个机器上分布 10 ～ 100 个tablet，每个 tablet 的容量可达到数十G。

Kudu 支持灵活的分区模式。创建表时，用户指定该表的分区模式。分区模式充当可以从主键元组映射到二进制分区键的函数。每个 tablet 覆盖这些分区键的连续范围。因此，客户端在执行读取或写入时可以轻松确定哪个 tablet 应保存给定 key 并相应地路由请求。

分区模式由零个或多个散列分区规则组成，后跟一个可选的范围分区规则，例如：

CREATE TABLE cust_behavior (
  id BIGINT,
  sku STRING,
  salary STRING,
  edu_level INT,
  usergender STRING,
  `group` STRING,
  city STRING,
  postcode STRING,
  last_purchase_price FLOAT,
  last_purchase_date BIGINT,
  category STRING,
  rating INT,
  fulfilled_date BIGINT
)
DISTRIBUTE BY HASH (id) INTO 4 BUCKETS,
RANGE (sku) SPLIT ROWS(('g'), ('o'), ('u'))
TBLPROPERTIES(
'storage_handler' = 'com.cloudera.kudu.hive.KuduStorageHandler',
'kudu.table_name' = 'cust_behavior',
'kudu.master_addresses' = 'kudu-master.example.com:7051',
'kudu.key_columns' = 'id, sku'
);

通过采用这些分区规则，用户可以根据其特定的工作负载轻松地在查询并行性和查询并发性之间进行权衡，合适的分区规则能够避免数据热点问题。尽管用户必须了解分区的概念才能最佳地使用 Kudu，但分区键编码的细节对用户来说是完全透明的：编码后的分区键不会在 API 中公开。

复制

为了提供高可用性，Kudu 跨多个机器复制所有的表数据。创建表的时候，用户指定复制因子（replication refactor），通常是 3 或者 5，由 Kudu master 确保所请求副本 (replica) 数。

Kudu 使用一致性算法 Raft 复制 tablets，它通过 Raft 就每个 Tablet 的操作逻辑日志（例如插入/更新/删除）达成一致。当客户端想要进行写操作的时候，首先定位到 leader 副本, 然后向这个副本发送一个写 RPC。如果客户端的信息已过时并且这个副本已经不再是领导者，它拒绝请求，导致客户端失效并刷新其元数据缓存，并将请求重新发送给新的 leader。如果副本实际上仍然充当 leader，它会使用本地锁管理器针对其他并发操作序列化该操作，选择 MVCC 时间戳，并通过 Raft 向其 follower 建议该操作。如果大多数副本接受写入并将其记录到自己的本地预写日志，则写入被视为持久复制，因此可以在所有副本上提交。这里并没有限制 leader 必须在提交操作之前将操作写入其本地日志：即使 leader 的磁盘性能不佳，这也提供了良好的延迟平滑属性。

在少数副本发生故障的情况下，leader 可以继续向 tablet 的复制日志提议并提交操作。如果 leader 本身失败，Raft 算法会快速选出新的领导者。默认情况下，Kudu 使用 500 毫秒的心跳间隔和 1500 毫秒的选举超时；因此，领导者失败后，通常会在几秒钟内选出新的 leader。

Kudu 的实现中对 Raft 算了做了一些小的优化：

  1. leader 选举失败后采用指数退避算法
  2. 当新 leader 联系其日志与自己的日志不同的 follower 时，Raft 建议一次向后执行一项操作，直到发现他们的分歧点。相反，Kudu 会立即跳回最后一个已知的 commitIndex，该索引始终保证出现在任何不同的追随者上。这样最大限度地减少了潜在的往返次数，但代价是可能通过网络发送冗余操作。

Kudu 仅对操作日志进行副本同步，而不是 tablet 的磁盘物理存储，这有下面的优点:

  • 后台任务(例如 Table Compaction) 错峰执行，而写操作只需要超过半数副本投票便可以通过，因此可以提升写操作效率；
  • 各个副本是完全自治的，这会防止错误通过副本同步迁移到其他副本，在发生错误时，恢复的机会会更高。

配置更改

Kudu 按照 1 中提出的 one-by-one 算法，Raft 配置中的投票者数量在每次配置更改中最多可以更改 1 个。为了将 3 个副本配置增长到 5 个副本，必须提出并提交两个单独的配置更改（3→4、4→5）。Kudu 通过一个叫做 remote bootstrap 的过程来完成这个操作。

添加一个新副本的时候，首先将其添加到 Raft 配置当中，完成之后 Leader 会向新的主机触发 StartRemoteBootstrap RPC，导致目标服务器从当前领导者处提取 Tablet 数据和日志的快照。传输完成后，新的 server 将按照与服务器重新启动后相同的过程打开 tablet。当打开 tablet 数据并重放任何必要的预写日志时，它已经完全复制了 leader 在开始传输时的状态，并且可以开始作为全功能副本响应 Raft RPC。

在上面的这个实现中，新服务器会立即作为 VOTER 副本添加。但是这样做的缺点是，从 3 服务器配置转移到 4 服务器配置后，四台服务器中的三台必须确认每个操作。由于新服务器正在复制过程中，因此无法确认操作。如果另一台服务器在快照传输过程中崩溃，tablet 将无法写入，直到 remote bootstrap 完成。

为了解决这个问题，Kudu 中增加了一个 PRE_VOTER 的状态, 在这个状态下计算配置多数的规模时不将其算作 Voter。一旦检测到 PRE VOTER 副本已完全赶上当前日志，领导者将自动提议并提交另一个配置更改，以将新副本转换为完整 VOTER。

驱逐节点的时候，Leader 提出操作，将配置修改为不包含被驱逐节点的配置，该操作提交之后，剩余节点将不再向被驱逐节点发送消息，被驱逐的节点自己并不知道自己已经被删除，配置修改被提交的时候，其余节点会向 Master 报告配置修改，Master 负责清理孤立的副本。

Kudu Master

为了简单 Kudu 采用的是集中式的，复制 Leader 设计，而不是 peer-to-peer 的设计。

Kudu master 职责：

  1. 充当目录管理器（catalog manager），跟踪存在哪些表和 tablet，以及它们的架构、所需的复制级别和其他元数据。创建、更改或删除表时，Master 会在 tablet 上协调这些操作并确保它们最终完成；
  2. 充当集群协调员 （cluster coordinator），跟踪集群中哪些服务器处于活动状态，并在服务器故障后协调数据的重新分配；
  3. 充当 tablet 目录 （tablet directory），跟踪 tablet server 上托管的副本

目录管理器 Catalog Manager

Master 本身持有一个单个 tablet 的表，该表用户无法直接访问。Master 在内部会想目录信息写入这个 tablet，同时会在内存中保留目录的直写缓存。

目录表为系统中的每个表维护少量状态。它保留表模式的当前版本、表的状态（创建、运行、删除等）以及组成该表的 tablets 集合。在接受创建表的请求的时候，master 会在目录表中写入一条表记录指示 CREATING 状态。它选择 tablet 服务器来托管 tablet 副本，创建 master 端的 tablet 元数据，并发送异步请求以在 tablet 服务器上创建副本。如果大多数副本上的副本创建失败或超时，则可以安全地删除该 tablet，并使用一组新副本创建新 tablet。如果 Master 在此操作过程中失败，则表记录表明需要前滚，并且 Master 可以从中断处恢复。其他的操作（删除/更改）是类似的。在所有情况下，从 master 到 tablet 服务器的消息都被设计为幂等的，以便在崩溃和重新启动时，可以安全地重新发送它们。

由于目录表本身保存在 Kudu 片中，因此 Master 支持使用 Raft 将其持久状态复制到备份主进程。目前，备份主节点仅充当 Raft Follower，不服务客户端请求。在通过 Raft 算法当选为领导者后，备份主服务器会扫描其目录表，加载其内存缓存，并开始充当活动主服务器，遵循与主服务器重新启动相同的过程。

集群协调者 Cluster Coordination

集群中所有的tablet server 静态配置了 master 主机名列表，tablet server 启动之后会向 master 进行注册，并且会持续性的发送 tablet 报告，报告中包含了记录了 tablet server 中持有的 tablet 集合。第一个报告中的信息包含全部的 tablet 信息，此后的信息是增量发送的，仅包含变更的信息。

Kudu 的一个关键设计点是，虽然 Master 是目录信息的来源，但它只是集群状态的观察者。 Tablet 服务器本身始终对 Tablet 副本的位置、当前 Raft 配置、Tablet 的当前模式版本等具有权威性。因为 Tablet 副本通过 Raft 同意所有状态更改，所以每个此类更改都可以映射到特定的 Raft 提交的操作索引。这使得 Master 能够确保所有tablet 状态更新都是幂等的并且能够适应传输延迟：Master 简单地比较 tablet 状态更新的 Raft 操作索引，如果该索引不比 Master 当前观察到的更新，则将其丢弃。

这样的设计让 tablet 具有更多的责任，比如 master 不会取探测 tablet server 是否 crash，而是将这个责任委托给了 crash 机器上具有副本的 tablet 的 Raft Leader 副本。Leader 跟踪上次与每个 follower 成功通信的时间，如果很长时间没有成功通信，那么 leader 会声明 follower 已经死亡，并提出 Raft 配置更改，将 follower 从 raft 配置中驱逐。当配置更改成功提交之后，剩余的 tablet server 会向 master 发出 tablet 报告，告知 leader 的决定。

为了让 tablet 达到指定的复制计数，master 会从视图选择一个 Tablet 服务器来托管新的副本。选择服务器后，Master 建议 tablet 的当前 leader 副本进行配置更改。但是，Master 本身无权更改 Tablet 配置——它必须等待 Leader 副本提出并提交配置更改操作，此时 Master 会通过 Tablet 报告通知配置更改成功。如果Master的建议失败（例如，因为消息丢失），它将定期重试，直到成功。由于这些操作都用降级配置的唯一索引进行标记，因此它们是完全幂等且无冲突的，即使主服务器发出多个冲突的建议（主服务器故障转移后可能会发生）也是如此。

Master 对 tablet 的额外副本的响应类似。如果 Master 收到一个 table t报告，表明某个副本已从 tablet配置中删除，它会顽固地向删除的节点发送 DeleteTablet RPC，直到 RPC 成功。为了确保即使在主服务器崩溃的情况下也能最终清理，主服务器还会发送此类 RPC 来响应数据块报告，该报告标识 tablet 服务器正在托管不在最新提交的 Raft 配置中的副本。

Tablet 目录 Tablet Directory

为了高效的执行读写操作，客户端会向 master 查询 tablet 的位置信息。客户端维护了一个本地元数据缓存，其中有之前它们访问过的每个 tablet 的最近信息，包括 tablet 分区键范围以及 Raft 配置信息。在任何时间点，客户端的缓存都可能是陈旧的；如果客户端尝试向不再是 Tablet 的领导者的服务器发送写入，则服务器将拒绝该请求。然后，客户联系 master 以了解新 leader 的情况。如果客户端收到与假定的 leader 通信的网络错误，它会遵循相同的策略，假设 tablet 可能已经选出了新的 leader。由于 master 将信息维护在内存中，因此单 master 也可以支撑较大的 QPS。

Tablet 存储

在 Tablet 服务器内，每个 Tablet 副本都作为一个完全独立的实体运行，与 3.2 和 3.3 节中描述的分区和复制系统显着解耦。在 Kudu 的开发过程中，发现在某种程度上独立于更高级别的分布式系统来开发存储层是很方便的，事实上 Kudu 的许多功能和单元测试完全在 tablet 实现的范围内运行。

由于这种解耦，我们正在探索提供在每个表、每个 tablet 甚至每个副本的基础上选择底层存储布局的能力的想法——这是 Fractured Mirrors 的分布式类似物。但是，当前仅仅提供单一存储布局的方式。

概览

在 kudu 中 tablet 的存储主要是为了解决这样几个问题：

  1. 快速列扫描：为了提供与相似类型，如 Parquet 相媲美的分析性能，关键是大多数扫描可以通过有效编码的列式数据文件来提供服务。
  2. 低延迟随机更新：为了提供更新或读取任意行的快速访问，需要 $ O(logn) $随机访问的查找复杂度。
  3. 性能的一致性：根据其他数据存储系统的经验，发现用户愿意牺牲峰值性能来实现可预测性。

为了同时提供这些特性，Kudu 没有重用任何预先存在的存储引擎，而是选择实现新的混合列式存储架构。

RowSets

Kudu 中的 Tablet 本身被细分为更小的单元，称为 RowSet。一些 RowSet 仅存在于内存中，称为 MemRowSet，而其他 RowSet 则存在于磁盘和内存的组合中，称为 DiskRowSet。任何给定的活动（未删除）行恰好存在于一个 RowSet 中；因此，RowSet 形成不相交的行集。但请注意，不同 RowSet 的主键间隔可能会相交。

在任何时间点，tablet 都有一个 MemRowSet，用于存储所有最近插入的行。由于这些存储完全位于内存中，因此后台线程会定期将 MemRowSet 刷新到磁盘。这些刷新的调度在第 4.11 节中有更详细的描述。

当选择刷新某个 MemRowSet 时，会交换一个新的空 MemRowSet 来替换它。先前的 MemRowSet 被写入磁盘，并成为一个或多个DiskRowSet。此刷新过程是完全并发的：读取器可以在刷新旧的 MemRowSet 时继续访问旧的 MemRowSet，并且刷新 MemRowSet 中行的更新和删除会被仔细跟踪，并在刷新过程完成后前滚到磁盘上的数据中。

MemRowSet 的实现

MemRowSets 由具有乐观锁定的内存中并发 B 树实现，大致基于 MassTree 的设计，但有以下更改：

  1. 不支持从树上移除元素，相应的使用 MVCC 记录删除。 MemRowSets 最终会刷新到其他存储，因此我们可以将这些记录的删除推迟到系统的其他部分。
  2. 不支持任意的原地更新树上的记录，相反，只允许不改变值大小的修改：这允许原子的 compare-and-swap 操作将突变附加到每个记录的链接列表中。
  3. 通过指针将叶子节点连接在一起以提高顺序扫描的性能。
  4. 没有实现完整的 trie of tree，而是仅仅实现一棵单树，因为与原始应用程序相比，我们不太关心极高的随机访问吞吐量。

为了优化随机写的性能，使用了更大的叶子节点和内部节点，每个节点大小为四个缓存行（256 字节）。

与 Kudu 中的大多数数据不同，MemRowSets 以行式布局存储行。这仍然提供了可接受的性能，因为数据始终在内存中。为了在选择行存储的情况下最大化吞吐量，Kudu 利用 SSE2 内存预取指令在扫描器之前预取一个叶节点，并使用 LLVM 进行 JIT 编译记录投影操作。相对于简单的实现，这些优化提供了显着的性能提升。

为了形成插入 B 树的键，使用第 3.2 节中所述的保序编码对每行的主键进行编码。这允许仅使用 memcmp 操作进行比较的高效树遍历，并且 MemRowSet 的排序性质允许对主键范围或单个键查找进行有效扫描。

DiskRowSet 实现

当MemRowSets刷新到磁盘时，它们变成DiskRowSets。在刷新 MemRowSet 时，在每 32 MB IO 之后滚动 DiskRowSet。这确保了没有 DiskRowSet 太大，从而允许高效的增量压缩，如稍后第 4.10 节中所述。因为 MemRowSet 是按排序顺序排列的，所以刷新的 DiskRowSet 本身也将按排序顺序排列，并且每个滚动段将具有不相交的主键间隔。

DiskRowSet 由两个主要部分组成：基础数据和增量存储。基础数据是 DiskRowSet 中行的按列组织的表示。每列都以单个连续数据块的形式单独写入磁盘。列本身被细分为小页，以允许细粒度随机读取，并且嵌入 B 树索引允许根据行集中的序号偏移量高效地查找每个页。列页使用多种编码方式进行编码，例如字典编码、bitshuffle、并且可以选择使用通用二进制压缩方案（例如 LZ4、gzip 或 bzip2）进行压缩，这些编码和压缩选项可以由用户在每列的基础上显式指定，例如指定应该对不经常访问的大文本列进行 gzip 压缩，而通常存储小整数的列应该进行位打包。 Kudu 支持的几种页面格式与 Parquet 支持的页面格式很常见，kudu 的实现与 Impala 的 Parquet 库共享许多代码。

除了刷新表中每个用户指定的列之外，我们还编写一个主键索引列，它存储每行的编码主键。还刷新了一个分块的布隆过滤器，它可用于根据编码的主键测试行是否可能存在。

由于列式编码很难就地更新，因此基础数据中的列一旦刷新就被认为是不可变的。相反，更新和删除是通过称为增量存储的结构来跟踪的。增量存储要么是内存中的 DeltaMemStore，要么是磁盘上的 DeltaFile。 DeltaMemStore 是一个并发 B 树，它共享上述实现。 DeltaFile 是二进制类型的列块。在这两种情况下，增量存储都维护从（行偏移、时间戳）元组到 RowChangeList 记录的映射。行偏移量只是 RowSet 中行的序数索引 - 例如，主键最低的行的偏移量为 0。时间戳是最初写入操作时分配的 MVCC 时间戳。 RowChangeList 是行更改的二进制编码列表，例如 SET column id 3 = ‘foo’ 或 DELETE。

当对 DiskRowSet 中的数据进行更新时，我们首先查阅主键索引列。通过使用其嵌入的 B 树索引，我们可以有效地查找包含目标行的页面。使用页面级元数据，我们可以确定该页面内第一个单元格的行偏移量。通过在页面内搜索（例如通过内存中的二分搜索），我们可以计算目标行在整个 DiskRowSet 中的偏移量。确定此偏移量后，我们将新的增量记录插入到行集的 DeltaMemStore 中。

Delta Flushes

由于 DeltaMemStore 是内存存储，因此容量有限。调度 MemRowSet 刷新的同一后台进程也安排 DeltaMemStore 刷新。刷新 DeltaMemStore 时，会交换一个新的空存储，同时将现有存储写入磁盘并成为 DeltaFile。 DeltaFile 是一个简单的二进制列，其中包含先前在内存中的数据的不可变副本。

INSERT path

如前所述，每个tablet都有一个MemRowSet，用于保存最近插入的数据；然而，仅仅将所有插入直接写入当前 MemRowSet 是不够的，因为 Kudu 强制执行主键唯一性约束。换句话说，与许多 NoSQL 存储不同，Kudu 将 INSERT 与 UPSERT 区分开来。

为了强制执行唯一性约束，Kudu 在插入新行之前必须查阅所有现有的 DiskRowSet。由于每个tablet 可能有数百或数千个DiskRowSet，因此高效地完成此操作非常重要，方法是剔除要查询的DiskRowSet 数量并提高DiskRowSet 内的查找效率。

为了挑选 DiskRowSet 集合以在 INSERT 操作上进行检查，每个 DiskRowSet 都存储存在的键集合的 Bloom 过滤器。由于新的键永远不会插入到现有的 DiskRowSet 中，因此该 Bloom 过滤器是静态数据。我们将布隆过滤器分块为 4KB 页面，每个页面对应一小部分键，并使用不可变的 B 树结构为这些页面建立索引。这些页面及其索引缓存在服务器范围的 LRU 页面缓存中，确保大多数布隆过滤器访问不需要物理磁盘查找。

此外，对于每个 DiskRowSet，存储最小和最大主键，并使用这些键边界在区间树中对 DiskRowSet 进行索引。进一步剔除 DiskRowSet 集合以在任何给定的键查找上进行检查。第 4.10 节中描述的后台压缩过程重新组织 DiskRowSets 以提高基于间隔树的剔除的有效性。

对于无法剔除的 DiskRowSet，必须回退查找要插入其编码主键列中的键。这是通过该列中嵌入的 B 树索引来完成的，这可确保在最坏的情况下磁盘寻道次数为对数。同样，该数据访问是通过页缓存执行的，确保对于关键空间的热区域，不需要物理磁盘寻道。

Read Path

与 X100 等系统类似，Kudu 的读取路径始终以批量行的方式运行，以便分摊函数调用成本并为循环展开和 SIMD 指令提供更好的机会。 Kudu 的内存批处理格式由一个顶级结构组成，其中包含指向正在读取的每列的较小块的指针。因此，批处理本身在内存中是列式的，这避免了从列式磁盘存储复制到批处理时的任何偏移计算成本。当从 DiskRowSet 读取数据时，Kudu 首先确定扫描中的范围谓词是否可用于剔除此 DiskRowSet 内的行范围。例如，如果扫描设置了主键下限，我们在主键列内执行查找以确定下限行偏移量；对于主键上限，也执行同样的操作。这会将键范围谓词转换为行偏移范围谓词，这更容易满足，因为它不需要成本更高的字符串比较。

接下来，Kudu 一次执行一列扫描。首先，它在目标列中查找正确的行偏移量（如果未提供谓词，则为 0；如果先前确定了下限，则为起始行）。接下来，它使用页面编码特定解码器将源列中的单元格复制到我们的行批次中。最后，它会根据当前扫描的 MVCC 快照查询增量存储，查看是否有任何后续更新已将单元替换为较新版本，并根据需要将这些更改应用到内存中的批次。由于增量是基于数字行偏移而不是主键来存储的，因此该增量应用程序过程非常高效：它不需要任何每行分支或昂贵的字符串比较。

对投影中的每一行执行此过程后，它会返回批处理结果，该结果可能会被复制到 RPC 响应中并发送回客户端。 Tablet 服务器在服务器端为每个扫描器维护有状态迭代器，以便连续的请求不需要重新查找，而是可以从每个列文件中的前一个点继续。

Lazy Materialization

如果为扫描器指定了谓词，我们将执行列数据的延迟具体化。特别是，我们更喜欢在读取任何其他列之前读取具有关联范围谓词的列。读取每个这样的列后，我们评估相关的谓词。在谓词过滤该批次中的所有行的情况下，我们短路其他列的读取。这在应用选择性谓词时提供了显着的速度提升，因为来自其他选定列的大多数数据永远不会从磁盘读取。

增量压缩

由于增量不是以列格式存储的，因此随着越来越多的增量应用于基础数据，tablet 的扫描速度将会降低。因此，Kudu 的后台维护管理器定期扫描 DiskRowSets 以查找累积大量增量（由基本数据行计数和增量计数之间的比率标识）的任何情况，并安排增量压缩操作，将这些增量合并回基础数据列。

特别是，增量压缩操作标识了大多数增量仅适用于列的子集的常见情况：例如，SQL 批处理操作通常只更新宽表中的一列。在这种情况下，增量压缩将仅重写该单个列，从而避免其他未修改列上的 IO。

RowSet 压缩

除了将增量压缩为基础数据之外，Kudu 还会在 RowSet 压缩的过程中定期将不同的 DiskRowSet 压缩在一起。此过程对两个或多个 DiskRowSet 执行基于键的合并，从而产生输出行的排序流。输出被写回新的 DiskRowSet，再次每 32 MB 滚动一次，以确保系统中的 DiskRowSet 不会太大。

RowSet 压缩有两个目标：

  1. 借此机会删除已删除的行。
  2. 此过程减少了在键范围内重叠的 DiskRowSet 的数量。通过减少 RowSet 重叠的数量，我们减少了 Tablet 中预计包含随机选择的键的 RowSet 的数量。该值充当布隆过滤器查找数量的上限，因此磁盘查找的数量预计将服务于 tablet 内的写入操作。

Scheduling maintenance

如上面各节所述，Kudu 执行多种不同的后台维护操作，以减少内存使用并提高磁盘布局的性能。这些操作由在 Tablet 服务器进程中运行的维护线程池执行。为了实现一致性能的设计目标，这些线程始终运行，而不是由特定事件或条件触发。完成一个维护操作后，调度程序进程会评估磁盘存储的状态，并根据一组启发式方法选择要执行的下一个操作，这些启发式方法旨在平衡内存使用、预写日志保留和未来读和写操作的性能。

为了选择要压缩的 DiskRowSet，维护调度程序解决了一个优化问题：给定 IO 预算（通常为 128 MB），选择一组 DiskRowSet，以便压缩它们将减少预期的查找次数，如上所述。这种优化结果是著名的整数背包问题的一系列实例，并且能够在几毫秒内有效地解决。

由于维护线程始终运行小型工作单元，因此操作可以对工作负载行为的变化做出快速反应。例如，当插入工作负载增加时，调度程序会快速做出反应并将内存中的存储刷新到磁盘。当插入工作负载减少时，服务器会在后台执行压缩以提高未来写入的性能。这提供了性能的平滑过渡，使开发人员和运营商能够更轻松地执行容量规划并估计其工作负载的延迟概况。

  1. D. Ongaro. Consensus: Bridging Theory and Practice. PhD thesis, Stanford University, 2014. ↩︎