kudu之tablet设计原理

╰+攻爆jí腚メ 2022-01-23 00:29 352阅读 0赞

Tablet是Kudu表的水平分区，就像是BigTable中的tablets和HBase中的regions一样。每个tablet中都由一系列连续的行组成，这些行不会与任何其他tablet重叠。所有tablet一起构成了整张表。

每个tablet进一步细分为多个称为RowSet的行集。每个RowSet由一组行的数据组成。RowSet是不相交的，即不同RowSet的行集不相交，因此任何给定的key最多存在于一个RowSet中。虽然RowSets是不相交的，但它们的key空间可能会重叠。

# 处理插入 #

保存在内存中的RowSet，称为MemRowSet。所有插入都直接进入MemRowSet，它是一个按表的主键排序的内存中的B-Tree。在插入数据时，它会在MemRowSet中累积，数据一旦进入MenRowSet中就立刻对读可见，并且遵守MVCC（多版本并发控制）。

注意：与BigTable不同，只有插入的数据和最近数据的更新才会进入MemRowSet - 本文后面的部分将讨论诸如磁盘中数据更新和删除之类的操作。

每个行数据只存在于MemRowSet中的一个实体中。这个实体的值由一个特定的header信息，以及行数据的打包格式组成（下面有更多详细信息）。由于MemRowSet完全在内存中，它最终将被填满并“刷新”到磁盘 - 此过程将在本文档的后面部分详细介绍。

# MVCC概述 #

Kudu使用多版本并发控制来提供许多有用的功能：

*  快照查询：当一个查询被创建时，它将查询某个时间点的快照数据。将忽略在查询过程中对tablet进行的任何更新。此外，该时间点的快照可以存储并重新用于同一tablet上的其他查询，例如，如果应用程序想要执行分析，需要在一致的数据视图上进行多次传递。
 *  历史快照查询：与上边的快照查询一样。用户可以指定历史的一个时间点创建一个查询，MVCC可以保证历史快照的一致性。这个功能可以被用来在某个时间点上的一致性备份。
 *  历史变更查询：给定两个MVCC快照，用户可以查询任意给定行的这两个快照之间的增量集。可以利用此功能来执行增量备份，执行跨群集同步或进行离线审计分析。
 *  tablet中的多行原子更新：单个操作可以修改tablet中的多个行，并且它将在单个原子动作中可见。

为了提供MVCC，每个操作都标有时间戳。时间戳由一个名为TS-wide Clock 的实例生成，并通过tablet的MvccManager确保在tablet中是唯一的。经过MvccManager确认时间戳后的状态被称为已提交状态，已提交状态的数据可以被后来的查询可见。查询创建后，会获取MvccManager状态的快照，然后将该查询看到的任何数据与MvccSnapshot进行比较，以确定哪些插入，更新和删除后的数据应被视为可见。

每个tablet的时间戳单调递增的。我们使用一种名为HybridTime的技术来创建时间戳，这些时间戳对应于真正的挂钟时间，但也反映了节点之间的因果关系。

为了支持这些快照查询，数据库中必须保持每行数据的多个版本。为了防止无限制的空间使用，用户可以配置保留期，超过该保留期可以对旧的事务记录进行回收（从而防止从历史记录中的那个点之前的任何快照读取）。（注意：历史GC目前尚未实现）

# MemRowSet中的MVCC操作 #

为了在MemRowSet中支持MVCC，每行都标有插入行的时间戳。此外，该行包含一个单链表，其中包含插入后对该行进行的任何进一步操作，每个操作都标记有操作的时间戳：

MemRowSet Row
    +----------------------------------------------------+
    | insertion timestamp  | mutation head | row data... |
    +-------------------------|--------------------------+
                              |
                              v          First mutation
                      +-----------------------------------------------+
                      | mutation timestamp | next_mut | change record |
                      +--------------------|--------------------------+
                                __________/
                               /
                               |         Second mutation
                      +--------v--------------------------------------+
                      | mutation timestamp | next_mut | change record |
                      +--------------------|--------------------------+
                                __________/
                               /
                               ...

在传统的数据库术语中，人们可以认为操作列表形成了一种“REDO日志”，其中包含影响该行的所有变化。

任何遍历MemRowSet的读者都需要通过以下逻辑应用这些操作来读取行的正确快照：

*  如果这行数据插入时的timestamp，不在scanner 的MVCC snapshot里（即scanner快照指定的timestamp小于数据插入的时间戳，数据还没创建），忽略该行
 *  否则将这行数据放入output缓存里
 *  对于列表中的每个操作：
    
     *  如果mutation的timestamp在MVCC snapshot里，在内存的缓存中执行这个更新。如果不在，则跳过此mutation
     *  如果mutation是一个DELETE操作，则在buffer中标记为已经被删除了，并清空之前加载缓存里的数据。

请注意，操作可以是以下三种类型之一：

*  更新：更改一列或多列的值
 *  DELETE：从数据库中删除行
 *  REINSERT：重新插入行（仅发生在先前有DELETE操作的MemRowSet行上）

作为一个具体示例，请看表结构为key STRING, val UINT32)的如下操作

INSERT INTO t VALUES (“row”, 1); \[timestamp 1\]  
UPDATE t SET val = 2 WHERE key = “row”; \[timestamp 2\]  
DELETE FROM t WHERE key = “row”; \[timestamp 3\]  
INSERT INTO t VALUES (“row”, 3); \[timestamp 4\]  
以上一系列的操作会在MemRowSet生成如下结构：

+-----------------------------------+
      | tx 1 | mutation head | ("row", 1) |
      +----------|------------------------+
                 |
                 |
             +---v--------------------------+
             | tx 2 | next ptr | SET val=2  |
             +-----------|------------------+
                  ______/
                 |
             +---v-------v----------------+
             | tx 3 | next ptr | DELETE   |
             +-----------|----------------+
                  ______/
                 |
             +---v------------------------------------+
             | tx 4 | next ptr | REINSERT ("row", 3)  |
             +----------------------------------------+

请注意，当更新频率较高时，这会有一些不良影响：

*  读操作必须通过单链表追逐指针，可能导致许多CPU缓存未命中。
 *  更新必须附加到单个链表的末尾，时间复杂度为O（n），其中“n”是此行已更新的次数。

但是，考虑到以下假设，我们认为上述低效率是可以容忍的：

*  Kudu的目标使用场景具有相对较低的更新率：我们假设单行不会有高频率的更新
 *  只有总数据库的一小部分将在MemRowSet中 - 一旦MemRowSet达到某个目标大小阈值，它将刷新。因此，即使由于更新频繁导致MemRowSet很慢，它也只占整个查询时间的一小部分。

如果事实证明上述低效率会影响实际应用程序，则可以在将来应用各种优化以减少开销。

# MemRowSet刷新 #

当MemRowSet填满时，会发生Flush，将数据保存到磁盘。

+------------+
    | MemRowSet  |
    +------------+
         |
         | Flush process writes entries in memory to a new DiskRowSet on disk
         v
    +--------------+  +--------------+    +--------------+
    | DiskRowSet 0 |  | DiskRowSet 1 | .. | DiskRowSet N |
    +-------------+-  +--------------+    +--------------+

当数据被刷新，它将会以CFiles的形式被存储在磁盘中。数据中的每一行都可以通过有序的rowid被定位，该rowid在此DiskRowSet中是密集的，不可变的和唯一的。例如，如果给定的DiskRowSet包含5行，则按升序的顺序为它们分配rowid 0到4。在不同的DiskRowSet中，将有不同的行具有相同的rowid。

读取可以使用索引结构在主键（用户可见）和rowid（内部）之间进行映射。在主键是简单键的情况下，键结构嵌入在主键列的CFile中。否则，用独立的索引CFile存储编码后的复合键并提供类似的功能。

注意：rowid不是与每一行显式存储，而是基于文件中行的序数索引的隐式标识符。源代码的某些部分将rowid称为“row indexes” 或者 “ordinal indexes”。

注意：其他系统（如C-Store）将MemRowSet称为“写入优化存储”（WOS），磁盘上的文件称为“读取优化存储”（ROS）。

# DiskRowSets中的历史MVCC #

为了继续为磁盘数据提供MVCC，每个磁盘上的RowSet不仅包含当前的列数据，还包含“UNDO”记录，这些记录提供了将行数据回滚到早期版本的能力。

+--------------+       +-----------+
    | UNDO records | <---  | base data |
    +--------------+       +-----------+
    - time of data progresses to the right --->

当用户想要在刷新后立即读取最新版本的数据时，只需要基础数据。由于基础数据以列式存储，因此这种查询性能是很好的。相反，如果用户想要运行历史数据查询，则需要查询UNDO记录，以便将可见数据回滚到较早的时间点。

当查询过程中遇到一行时，它会按如下方式处理MVCC信息：

*  读取行的基本数据
 *  对于每个UNDO记录： 如果相关的操作timestamp还未提交，则执行回滚操作。即查询指定的快照timestamp小于mutation的timestamp，mutation还未发生。

例如，回想一下上面“MemRowSet中的MVCC Mutations”中使用的一系列操作：

INSERT INTO t VALUES ("row", 1);         [timestamp 1]
     UPDATE t SET val = 2 WHERE key = "row";  [timestamp 2]
     DELETE FROM t WHERE key = "row";         [timestamp 3]
     INSERT INTO t VALUES ("row", 3);         [timestamp 4]

将此行刷新到磁盘时，我们将按以下方式将其存储在磁盘上：

Base data:
          ("row", 3)
       UNDO records (roll-back):
          Before Tx 4: DELETE
          Before Tx 3: INSERT ("row", 2")
          Before Tx 2: SET row=1
          Before Tx 1: DELETE

UNDO中的操作都是与真实的操作相反的 - 例如，事务1中的INSERT在保存为UNDO记录时变为“DELETE”。

此处使用UNDO保留插入时间戳：查询的MVCC快照指定的时间早于Tx1时，Tx1还未提交，此时将会执行DELETE操作，那么这时这条数据是不存在的。

看以下两个例子：

Current time scanner (all txns committed)
      -----------------------------------------
      - Read base data
      - Since tx 1-4 are committed, ignore all UNDO records
      - No REDO records
      Result: current row ("row", 3)
    
    
      Scanner as of timestamp 1
      ---------------------
      - Read base data. Buffer = ("row", 3)
      - Rollback Tx 4:  Buffer = <deleted>
      - Rollback Tx 3:  Buffer = ("row", 2)
      - Rollback Tx 2:  Buffer = ("row", 1)
      Result: ("row", 1)

每个案例处理正确的UNDO记录集，以获取所需时间点的行数据。

最常见的情况就是查询当前数据。在这种情况下，我们希望通过避免处理任何UNDO记录来优化查询执行。为了达到这个目标，我们引入文件级别的元数据，指向UNDO record的数据范围。如果查询的MVCC快照符合的所有事务都已经提交了（查询最新的数据），这组deltas就会短路（不处理UNDO record），这时查询将没有MVCC开销。

# 处理磁盘中行数据的变更 #

已刷新到磁盘中的数据的更新或删除不会进入MemRowSet。而是在所有RowSet中搜索更新的key，以便找到保存该keyt的唯一RowSet。此过程首先使用区间树来定位可能包含要查询的key的一组候选RowSet。在此之后，用boom filter去判断候选RowSet中是否包含这个key。对于通过两个检查的RowSet，再用索引找到目标行的rowId。

一旦确定了数据所在的RowSet，mutation将拿到主键对应的rowid，然后mutation会被写入到一个称为DeltaMemStore的内存结构中。

DeltaMemStore是一个在内存中的并行BTree，BTree的key是使用rowid和mutation的timestamp混合成的。在读取时，以与新插入数据的mutation相同的方式处理这些mutation。

当Delta MemStore变得太大时，它会对将数据刷新到磁盘上的DeltaFile中，并将自身重置为空：

+------------+      +---------+     +---------+     +----------------+
    | base data  | <--- | delta 0 | <-- | delta N | <-- | delta memstore |
    +------------+      +---------+     +---------+     +----------------+

DeltaFiles包含与Delta MemStore相同类型的信息，但是压缩为密集的磁盘序列化格式。由于这些增量文件中包含将基础数据更新到最新版本的事务记录，因此它们被称为“REDO”文件，而其中包含的mutations 称为“REDO”记录。与驻留在MemRowSet中的数据类似，需要应用REDOmutations 来读取更新版本的数据。

给定行可以具有多个delta结构中的delta信息。在这种情况下，deltas 是有序的，后来的修改优先于早期的修改。

注意，给定行的mutation 跟踪结构不需要包括整行数据。如果仅更新行中的单个列，则mutation 结构将仅包括更新的列。这允许快速更新少数的列而无需读取或重写大量的列（与C-Store和PostgreSQL等系统使用的MVCC技术相比具有优势）。

# delta 文件处理流程的总结 #

每个DiskRowSet由3个部分组成

+--------------+       +-----------+      +--------------+
    | UNDO records | <---  | base data | ---> | REDO records |
    +--------------+       +-----------+      +--------------+

Base data: RowSet刷新后的列数据

UNDO records:历史数据，用于将当期数据回滚到之前的某个版本

REDO records:用于将数据更新到最新版本的数据，它包含了数据刷新之后的改动

UNDO records 和 REDO records 是用相同的格式存储的，称为DeltaFile

# delta数据的压缩 #

在RowSet中，随着越来越多的操作在delta跟踪结构中累积，读取效率会越来越低; 特别是，当读取base data时，每个刷新过的delta文件都会被搜索和合并。此外，如果数据已多次更新，则必须获取许多REDO记录才能得到最新版本的数据。

为了减轻这种影响并提高读取性能，Kudu执行后台处理，将RowSet从低效的物理布局转换为更高效的布局，同时保持相同的逻辑内容。这些类型的转换称为“delta compactions”。Delta压缩有几个主要目标：

1、减少增量文件的数量  
RowSet拥有的delta文件越多，获取最新版本数据时需要读取的文件就越多。每次随机读取都会导致每个增量文件的磁盘搜索，从而导致性能下降。

2、将REDO记录合并到UNDO记录  
如上所述，RowSet由base data（按列存储），一组“undo”记录（用于回滚到以前版本）和一组“REDO”记录（用于更新到最新版本）。鉴于大多数查询将针对当前版本的数据库进行，我们希望尽量减小REDO记录存储。

在任何时候，行的REDO记录可以合并到base data中，并由等效UNDO记录集替换。

3、回收旧的UNDO记录。  
UNDO记录只需保留在用户配置的历史保留期之后。在此期间之后，我们可以删除旧的“撤消”记录以节省磁盘空间。

注意：在BigTable设计中，时间戳与数据相关联，而不是与更改相关联。在Kudu设计中，时间戳与更改相关联，而不是与数据相关联。删除历史UNDO日志后，没有剩余的记录显示何时插入或更新了任何行或单元格。如果用户需要此功能，他们应该保留自己的“inserted\_on”时间戳列，就像在传统的RDBMS中一样。

# Delta 压缩的类型 #

REDO delta压缩可以分为“minor”或“major”：

## Minor REDO delta compaction ##

‘minor’ compaction不包含base data的压缩。在这种类型的压缩中，生成的文件本身就是一个增量文件。

+------------+      +---------+     +---------+     +---------+     +---------+
    | base data  | <--- | delta 0 + <-- | delta 1 + <-- | delta 2 + <-- | delta 3 +
    +------------+      +---------+     +---------+     +---------+     +---------+
                        \_________________________________________/
                               files selected for compaction
    
      =====>
    
    +------------+      +---------+     +-----------------------+
    | base data  | <--- | delta 0 + <-- | delta 1 (old delta 3) +
    +------------+      +---------+     +-----------------------+
                        \_________/
                      compaction result

minor REDO delta压缩仅用于目标1：因为它们不读取或重写基础数据，所以它们无法将REDO记录转换为UNDO。

## Major REDO delta compaction ##

Major REDO压缩是包含基础数据以及任意数量的REDO delta文件的压缩。

+------------+      +---------+     +---------+     +---------+     +---------+
    | base data  | <--- | delta 0 + <-- | delta 1 + <-- | delta 2 + <-- | delta 3 +
    +------------+      +---------+     +---------+     +---------+     +---------+
    \_____________________________________________/
          files selected for compaction
    
      =====>
    
    +------------+      +----------------+      +-----------------------+     +-----------------------+
    | new UNDOs  | -->  | new base data  | <--- | delta 0 (old delta 2) + <-- | delta 1 (old delta 3) +
    +------------+      +----------------+      +-----------------------+     +-----------------------+
    \____________________________________/
               compaction result

‘major’ REDO满足delta压缩的目标1和2，但由于它们必须读取和重写base data（通常大于delta数据），因此成本高于次要delta压缩。

可以对DiskRowSet中的所有列的任意子集执行major REDO delta压缩 - 如果只有单个列接收到大量更新，则可以只对这列的数据做压缩。在企业级应用中会经常遇到这种情况，例如更新订单的状态、更新用户的访问量。

请注意，这两种类型的delta压缩都在RowSet中维护了row ID：因此，它们可以完全在后台完成而不进行锁定。compact的结果文件会采用原子swapping的方式被引入进RowSet。Swap操作结束后，compact前的那些老文件将会被删除。

# Merging compactions #

随着更多数据插入tablet，越来越多的DiskRowSets将会累积。这可能会影响以下情况的性能：

a）随机访问（通过主键获取或更新单行）

在这种情况下，为了定位key的具体位置，所有key范围包含查询key的rowSet将会被访问。 bloom 过滤器可以减少物理搜索的次数，但增加的 bloom 过滤器访问会影响CPU并且还会增加内存使用量。

b）使用指定范围扫描（例如查询“A”和“B”之间的主键）

在这种情况下，所有key范围与查询范围有重叠的RowSet都会被搜索。特定的索引结构可能会有所帮助，但同样会以消耗内存为代价等。

c）排序查询  
如果用户查询要求以主键排序顺序生成查询结果，则那么查询结果一定需要经过合并。Merge的消耗通常与输入的数据量成对数级增长，即随着数据量的增大，merge将越耗性能。

鉴于上述情况，最好将RowSet合并在一起以减少RowSet的数量：

+------------+
    | RowSet 0   |
    +------------+
    
    +------------+ \
    | RowSet 1   | |
    +------------+ |
                   |
    +------------+ |                            +--------------+
    | RowSet 2   | |===> RowSet compaction ===> | new RowSet 1 |
    +------------+ |                            +--------------+
                   |
    +------------+ |
    | RowSet 3   | |
    +------------+ /

与上述Delta Compactions不同，请注意，行ID 不会在Merging Compaction中维护。这使得处理并发操变得错综复杂。