1 设计初衷

提起大数据存储，我们很容易想到HDFS，HDFS上的列式存储技术Apache Parquet，以KV形式存储半结构化数据的Apache Hbase。对于列式存储，一方面体现在存储上能节约空间、减少 IO，另一方面依靠列式数据结构做了计算上的优化。

事实上，以上的这些存储技术都存在着一定的局限性。对于会被用来进行分析的静态数据集来说，使用Parquet存储是一种明智的选择。但是目前的列式存储技术更新数据性能都不太行，而且随机读写性能感人。而可以进行高效随机读写的HBase等数据库，却并不适用于基于SQL的数据分析方向。所以现在的企业中，经常会存储两套数据分别用于实时读写与数据分析，先将数据写入HBase中，再定期通过ETL到Parquet进行数据同步。但是这样做有很多缺点：

1. 用户需要在两套系统间编写和维护复杂的ETL逻辑。
2. 时效性较差。因为ETL通常是一个小时、几个小时甚至是一天一次，那么可供分析的数据就需要一个小时至一天的时间后才进入到可用状态，也就是说从数据到达到可被分析之间是会存在一个较为明显的“空档期”的。

1. 更新需求难以满足。在实际情况中可能会有一些对已经写入的数据的更新需求，这种情况往往需要对历史数据进行更新，而对Parquet这种静态数据集的更新操作，代价是非常昂贵的。
2. 存储资源浪费。两套存储系统意味着占用的磁盘资源翻倍了，造成了成本的提升。

我们知道，基于HDFS的存储技术，比如Parquet，具有高吞吐量连续读取数据的能力；而HBase和Cassandra等技术适用于低延迟的随机读写场景，那么有没有一种技术可以同时具备这两种优点呢？Kudu提供了一种满足这两个条件的选择。

Kudu的设计，就是试图在实时分析与随机读写之间，寻求一个最佳的结合。另外一个初衷，在Cloudera发布的《Kudu: New Apache Hadoop Storage for Fast Analytics on Fast Data》一文中有提及，Kudu作为一个新的分布式存储系统也是为了进一步提升CPU的适用效率。

2 kudu相关概念

kudu本身的数据存储也是使用的列式存储，底层的存储格式CFile格式，列式数据存储是将数据存储在强类型列中，这样的话可以实现kudu的高效读取，允许读取单个列或该列的一部分同时忽略其他列，这意味着您可以在磁盘上读取更少块来完成查询。与基于行的存储相比，即使只返回几列的值，仍需要读取整行数据。

由于给定的列只包含一种类型的数据，基于模式的压缩比压缩混合数据类型（在基于行的解决方案中使用）时更有效几个数量级。结合从列读取数据的效率，压缩允许您在从磁盘读取更少的块时完成查询。

Kudu允许使用LZ4、Snappy或zlib压缩编解码器进行每列压缩。默认情况下，使用位变换编码（Bitshuffle-encoded）的列天生就使用LZ4压缩进行压缩。否则，将存储未压缩的列。如果减少存储空间比原始扫描性能更重要，请考虑使用压缩。

以下为kudu主要概念：

• Table

        一张 talbe 是数据存储在 Kudu 的位置。表具有 schema 和全局有序的 primary key（主键）。table可以被分成很多段，这就是tablet。

• Tablet

        tablet是table的连续段，类似于其他数据存储引擎或关系数据库中的一个分区。给定的 tablet 冗余到多个 tablet 服务器上，并且在任何给定的时间点，其中一个副本被认为是 leader tablet。任何副本都可以对读取进行服务，并且写入时需要在为 tablet 服务的一组 tablet server之间达成一致性。

• Tablet server

        一个 tablet server 存储 tablet 和为 tablet 向 client 提供服务。对于给定的 tablet，一个 tablet server 充当 leader，其他 tablet server 充当该 tablet 的 follower 副本。只有 leader 服务写请求，然而 leader 或 followers 为每个服务提供读请求。

leader使用 Raft Consensus Algorithm 来进行选举。一个 tablet server 可以服务多个 tablets，并且一个 tablet 可以被多个 tablet server 服务着。

• Master
  • 该 master 保持跟踪所有的 tablets，tablet servers，Catalog Table 和其它与集群相关的 metadata。在给定的时间点，只能有一个起作用的 master（也就是 leader）。如果当前的 leader 消失，则选举出一个新的 master，使用 Raft Consensus Algorithm 来进行选举。
  • master 还协调客户端的 metadata operations（元数据操作），Kudu集群中的每个tablet server都需要配置master的主机名列表。当集群启动时，tablet server会向master注册，并发送所有tablet的信息。tablet server第一次向master发送信息时会发送所有tablet的全量信息，后续每次发送则只会发送增量信息，仅包含新创建、删除或修改的tablet的信息。作为集群协调者，master只是集群状态的观察者。对于tablet server中tablet的副本位置、Raft配置和schema版本等信息的控制和修改由tablet server自身完成。master只需要下发命令，tablet server执行成功后会自动上报处理的结果。例如，当创建新表时，客户端内部将请求发送给 master。 master将新表的元数据写入catalog table，并协调在tablet server 上创建 tablet的过程。
  • 作为catalog manager，master节点管理着集群中所有table和tablet的schema及一些其他的元数据。Catalog table是kudu元数据的中枢，主要存储table和tablet的信息。不能通过直接读取或者操作catalog table，相反，只能通过客户端api中公开的元数据操作方式对它进行访问。主要存储的两类信息：
    • tables：表结构、位置、表状态
    • tablet：已存的tablet列表，每个tablet副本所在的tablet服务器，tablet当前状态以及起始和结束的键。
  • tablet server 以定时向 master 发出心跳（默认值为每秒一次），跟踪每个tablet的位置，因为master上缓存了集群的元数据，所以client读写数据的时候，肯定是要通过master才能获取到tablet的位置等信息。但是如果每次读写都要通过master节点的话，那master就会变成这个集群的性能瓶颈，所以client会在本地缓存一份它需要访问的tablet的位置信息，这样就不用每次读写都从master中获取。因为tablet的位置可能也会发生变化（比如某个tablet server节点crash掉了），所以当tablet的位置发生变化的时候，client会收到相应的通知，然后再去master上获取一份新的元数据信息。
• Raft Consensus Algorithm

        无论是普通的tablet数据还是master数据，kudu都是使用Raft Consensus Algorithm来保证集群的容错性和一致性。通过这个算法，tablet的多个副本选举出一个leader，主要负责follower副本的复制和写操作。一旦写入被持久化到大多数副本中，它就会被客户端确认。一个给定的N个副本组(通常是3个或5个)能够接受最多(N - 1)/2个有错误的副本的写操作。

• 逻辑复制

        kudu复制的是操作而不是数据，这被称为逻辑复制而不是物理复制。主要有如下几个好处：

1. 虽然插入和更新确实通过网络传输数据，但是删除不需要移动任何数据。删除操作被发送到每个tablet服务器，它在本地执行删除操作。
2. 物理操作，例如压缩，不需要在Kudu中通过网络传输数据。这与使用HDFS的存储系统不同，在HDFS中，需要通过网络传输块来满足所需的副本数量。
3. tablet 不需要在同一时间或相同的时间表上执行压缩，或者在物理存储层上保持同步。这会减少由于压缩或大量写入负载而导致所有 tablet server同时遇到高延迟的机会。

3 kudu架构

下图显示了一个具有三个master和多个tablet server的Kudu集群，每个服务器都支持多个tablet。它说明了如何通过Raft一致性算法保证leader和tablet服务器的leader和follower的一致性。此外，某些tablet server可以是某些tablet的leader，也可以是某些tablet的follower。

TMaster 主要用来管理元数据，即tablet 和 表的基本信息，监听TServer的状态，TMaster之间通过raft协议进行数据同步。

TServer 主要用来管理tablet 。tablet 负责这一张表的某块内容的读写，接受其他tablet leader 传来的同步信息。

在数据存储方面，Kudu完全由自己实现，而没有借助于已有的开源方案。tablet存储主要想要实现的目标为：

• 快速的列扫描。
• 低延迟的随机读写。

• 一致性的性能。

一张table 会分成若干个tablet ，每个tablet中会包含的是 MetaData（元信息）和 若干个RowSet，每个RowSet里面包含的是一个MemRowSet 和若干个DiskRowSet，其中MemRowSet负责的是存储插入和更新的数据，当MemRowSet 写满后（默认是1G或者两分钟），会刷写到DiskRowSet（磁盘中）。

DiskRowSet用于对老数据的mutation（变化）操作，例如对数据更新，合并，删除历史和无用数据，减少查询过程的IO开销。一个DiskRowSet中，包含一个BloomFile、一个Ad_hoc Index、多个UndoFile、RedoFile、BaseData和DeltaMem

• BloomFile：根据DiskRowSet中key生成一个bloom filter，用于快速模糊的定位某一个key是否在DiskRowSet中
• Ad_hoc Index：是主键的索引，用于定位key在DiskRowSet中具体哪个偏移位置

• BaseData：基线数据，是MemRowSet flush下来的数据，按照列存储，按照主键有序
• UndoFile：增量，是BaseData之前的数据历史数据，简单解释就是，在对基线数据进行修改的时候，kudu 会跟踪所有的更新操作，并将这些操作保存到UndoFile中，超过15分钟这些数据会被删除。

• RedoFile：未合并的增量，是BaseData之后的mutation记录，可以获得较新的数据。解释：有些增量修改并不会被执行，因为可能是修改太小，不能为合并 带来好处，便被保留下来等待下一次的合并。
• DeltaMem：用于在内存中存储mutation记录，先写到内存中，然后写满后flush到磁盘，形成 DeltaFile

4 kudu的模式设计

Kudu表具有与传统RDBMS中的表类似的结构化数据模型。模式设计对于实现Kudu的最佳性能和运行稳定性至关重要。每个工作负载都是独一无二的，没有一个最合适每个表的单一模式设计。

在高层次上，创建 Kudu表有三个问题：

• 列设计
• 主键设计

• 分区设计

4.1 列设计

4.1.1 列编码

Kudu表中的每一列都可以根据列的类型使用一种编码来进行创建。

• 编码类型

Column Type ( 列类型 )	Encoding ( 编码 )	Default ( 默认 )
int8, int16, int32	plain, bitshuffle, run length	bitshuffle
int64, unixtime_micros	plain, bitshuffle, run length	bitshuffle
float, double	plain, bitshuffle	bitshuffle
bool	plain, run length	run length
string, binary	plain, prefix, dictionary	dictionary

下面简单介绍下各种编码方式：

• plain Encoding ( 普通编码 )

数据以其自然格式存储。例如，int32 values 作为固定大小的 32 位 little-endian integers 存储。

• Bitshuffle Encoding

大概原理是按照数据出现频次来对bit重新分布，最终采用LZ4压缩落地。 Bitshuffle 编码对于具有许多重复值的列或按主键排序时少量更改的列是不错的选择。

• Run Length Encoding ( 运行长度编码 )

该编码方式按照相邻相同元素按长度进行编码存储。比如原始数据为aaabbbbc，编码后变为a3b4c1。如果某列出现的值的类别比较少，如性别、国家等，使用该编码方式比较不错。

• Dictionary Encoding ( 字典编码 )

字典编码方式把按输入的字符串转换为[0-n]的整数，n为所有字符串去重后的个数。显而易见，n越小，字典的编码方式越高效。另外当n比较大时，kudu会进行相应的降级处理，编码方式自动降为plain encoding。

• Prefix Encoding ( 前缀编码 )

前缀编码可以近似的认为内部使用Trie（字典树）进行存储，当数据前缀相同部分较多时比较适合使用此编码方式。另外主键中第一列是按照前缀进行字典序排序，此时可采用此编码方式。

4.1.2 列压缩

kudu允许的压缩算法是LZ4、Snappy、zlib(gz)。默认情况下，kudu不压缩数据。通常情况下，压缩算法会提高空间利用率，但是会降低scan性能。

LZ4和Snappy类似，空间和时间上能够较好的平衡，zlib方式具有较高的压缩比，但是他的scan性能最差。

需要注意的是Bitshuffle encoding已经在最后使用了LZ4压缩，所以对于这种编码方式的列不需要额外的采用另外压缩算法。

4.2 主键设计

每个kudu表有且仅有一个由一列或多列组成的主键。主键列必须不可为空，并且不能使用bool或者浮点类型。同RDBMS一样，kudu的主键同样采用了唯一性约束。

在创建表期间，一旦主键创建了之后便不能更改。目前而言，kudu主键并不支持主键自增，因此应用程序必须在插入期间始终提供完整的主键。行删除和更新操作还必须指定要更改的行的完整主键。但是可以通过删除行并使用更新后的值重新插入。

与许多传统的关系型数据库一样，kudu的主键在一个聚集索引中，一个tablet内的所有行都按照其主键进行排序，扫描kudu行时，在主键列上使用相等或范围谓词来进行有效的查询。

注意:

主键索引适用于单个tablet上的扫描。

4.3 分区设计

为了提供可伸缩性，Kudu表被划分为称为tablet的单元，并分布在许多tablet上。一行总是属于一个tablet。将行分配给片的方法由表的分区决定，分区数是在表创建期间设置的。

选择分区策略需要理解数据模型和表的预期工作负载。对于写操作繁重的工作负载，设计分区以便将写操作分散到多个tablet服务器上非常重要，以避免使单个tablet服务器超载。对于涉及许多短扫描的工作负载(其中主要是连接远程服务器的开销)，如果扫描的所有数据都位于同一台tablet服务器上，那么性能可以得到改善。理解这些基本的权衡是设计有效的分区模式的关键。

注意：没有默认分区

Kudu在创建表时没有提供默认的分区策略。建议新表的读写工作负载至少与tablet服务器一样多。

Kudu提供了两种类型的分区:范围分区和散列分区。表也可以有多级分区，它结合了范围分区和哈希分区，或者有多个哈希分区实例。

优化一个数据库表需要考虑随机读、随机写、扫描三种操作：

• 随机写压力场景

对于写压力比较大的场景，最重要的一点是把写压力平均分担到不同的tablet中，这种场景通常采用hash partitioning，hash分区拥有良好的随机性。相比hbase而言，kudu的架构可以较为轻松的应对随机写的场景。

• 随机读压力场景

对于随机读压力比较大的业务场景并不是很建议使用kudu，通常情况下hbase会是一个更好的选择，不过kudu也有不错的随机读性能。kudu官方的性能测试，在杜雅丽分布符合 齐夫定律（在自然语言的语料库里，一个单词出现的频率与它在频率表里的排名成反比。所以，频率最高的单词出现的频率大约是出现频率第二位的单词的2倍，而出现频率第二位的单词则是出现频率第四位的单词的2倍）时，hbase具有读性能优势，随机分布下，kudu和hbase的随机读性能相当。不过通常情况下场景的读分布符合齐夫定律。

• 小范围scan场景

对于拥有大量小范围scan的业务场景，比如扫描一个店铺的所有商品、找到一个用户看到的所有商品，诸如此类的业务场景最好将同一个scan所需要的数据放置在同一个tablet里。按userId做hash，可以把同一个用户的所有信息放置在同一个tablet里面。

• 大范围scan

如果业务场景的scan需要扫描的数据量比较大，又想这类scan速度较快，则需要把这类scan所需要的数据分布到多个tablet中，充分利用多级分布式计算能力。假如我们有一个表存储了将近12个月的数据，一个设计方案是按照月进行分区，一个12个tablet，但如果大部分BI查询对应的scan仅需要最近一个月的数据，则这种设计便不合理，因为scan都集中到了一个tablet中，这种情况更好的一个设计方案是按月分区再按照hash分区。

4.3.1 范围分区

范围分区的分区方式将数据按照范围进行分类，每个partition会分配一个固定的范围，每个数据只会属于一个分区，不同的partition的范围不能有重叠，分区在表的创建阶段配置，后续不可修改，但是可以删除和新增，如果数据找不到所属的分区将会插入失败。

范围分区通常和时间有关系，但需要注意的是，老的分区可以删掉，同时又可以增加新的分区，意味着与时间强相关的数据可以按照这种方式进行分区，老的数据可以通过删除分区的方式进行删除。同时kudu对于这类操作的支持非常高效，完全不用担心删除或者新增分区会影响数据的读写。单个分区的数据量过大会影响kudu的性能，配置为时间相关的范围分区方式可以很好地控制每个分区的数据总大小。比如日志型数据，每秒平均有100条数据写入，配置为每天一个分区，最多有864w，如果配置为hash分区则单个分区的数据会随着时间推移越来越大。

分区的设计对Scan性能的影响至关重要，比如对于时间序列类型的数据而言，往往查询的是近期的数据，如果按时间进行切片，则Scan操作可以跳过大部分数据，如果单纯按照默认的hash方式切片，Scan操作则需要扫描全表。

• 范围分区管理

Kudu 允许在运行时从表中动态添加和删除范围分区，而不影响其他分区的可用性。删除分区将删除属于分区的 tablet 以及其中包含的数据。随后插入到丢弃的分区将失败。可以添加新分区，但不能与任何现有的分区分区重叠。 Kudu 允许在单个事务性更改表操作中删除并添加任意数量的范围分区。

动态添加和删除范围分区对于时间序列使用情况尤其有用。随着时间的推移，可以添加范围分区以覆盖即将到来的时间范围。例如，存储事件日志的表可以在每月开始之前添加一个月份的分区，以便保存即将到来的事件。必要时可以删除旧范围分区，以便有效地删除历史数据。

4.3.2 hash分区

hash分区将行通过hash值分配到其中一个存储桶（buckets）中，在single-level hash partitioned tables（单机散列分区表）中，每个存储桶将对应一个tablet。在创建表的时候设置桶数。通常，主键列用作散列的列，但与范围分区一样，可以使用主键列的任何子集。

哈希分区是一种有效的策略，当不需要对表进行有序访问时。哈希分区对于在 tablet 之间随机散布这些功能是有效的，这有助于减轻热点和 tablet 大小不均匀。

需要注意的是hash的分区方式是不可修改的，所以随着数据量的增长，hash的分区方式会造成单片的数据量过大，甚至超过单个tablet服务所能承受的数据量。

hash的分区方式对于随机读写友好，对于写操作而言，hash的分区方式会均匀的把写入压力分担到多个分区之中。对于随机读而言，按照主键进行hash之后Kudu可以提前预知读操作所对应的分区，避免每个切片都查一次。

4.3.3 多级分区

kudu支持多层的分区方式，将hash分区和范围分区结合起来。比如按照月分区将数分到多个分区中，每个月的数据按照hash进行二次分区。

• 分区修剪（调优）

当可以通过扫描谓词确定分区可以完全过滤时，Kudu扫描将自动跳过扫描整个分区。要删除哈希分区，扫描必须在每个哈希列上包含相等谓词。要删除范围分区，扫描必须在范围分区列上包含相等或范围谓词。在多级别分区表上的扫描可以独立地利用任何级别上的分区修剪。

• 分区设计案例

为了说明与为表设计分区策略相关的因素和权衡，我们将通过一些不同的分区方案。 考虑存储机器度量数据的下表模式（为了清楚起见，使用 SQL 语法和日期格式的时间戳）：

CREATE TABLE metrics (

host STRING NOT NULL,

metric STRING NOT NULL,

time INT64 NOT NULL,

value DOUBLE NOT NULL,

PRIMARY KEY (host, metric, time),

);

• 范围分区示例

分割度量表的一种自然方式是在时间列上对范围进行分区。假设我们想要每年都有一个分区，该表将保存 2014 年，2015 年和 2016 年的数据。表格至少有两种方式可以被分割：具有无界范围的分区，也可以是有限范围的分区。

上图显示了度量表可以在时间列上进行范围分区的两种方式。在第一个示例（蓝色）中，使用默认范围分区边界，并在 2015-01-01 和 2014 年 1 月分隔。这导致三个 tablet ： 2015 年之前的第一个值， 2015 年的第二个值，以及 2016 年以后的第三个值。第二个例子（绿色）使用了[(2014-01-01) ，(2017-01-01)]，并分期于 2015-01-01 和 2016-01-01 。第二个例子可以等价地通过[(2014-01-01)，(2015-01-01)]，[(2015-01-01)，(2016-01-01)]和[(2016-01-01)，(2017-01-01)]，没有分裂。第一个例子有无界的下限和上限分区，而第二个例子包括边界。

上面的每个范围分区示例都允许有时间限制的扫描来删除超出扫描时间限制的分区。当有许多分区时，这可以极大地提高性能。在编写时，这两个示例都存在潜在的热点问题。因为度量指标往往总是在当前时间写入，所以大多数写入将进入单个范围分区。

第二个示例比第一个更灵活，因为它允许将未来年份的范围分区添加到表中。在第一个示例中，2016-01-01之后的所有写操作都将落在最后一个分区中，因此该分区可能最终会变得太大，单个tablet服务器无法处理。

• hash分区示例

分割metrics表的另一种方法是在host和metrics columns列上进行hash分区。

在上面的例子中，metrics表在主机上被散列分区，而metric列被分成四个bucket。与前面的范围分区示例不同，这种分区策略将均匀地将写分散到表中的所有tablet上，这有助于提高总体的写吞吐量。对特定主机的扫描和度量可以通过指定相等谓词来利用分区修剪，从而将扫描tablet的数量减少到一个。使用纯哈希分区策略时要注意的一个问题是，随着越来越多的数据插入到表中，tablet可能会无限增长。最终tablet将变得太大，个人tablet服务器无法容纳。

需要注意的是：

虽然这些示例编号为tablet，但实际上tablet只提供UUID标识符，hash分区表中tablet之间没有自然排序。

• hash和范围分区结合示例

上面提到的两种分区的优缺点：

Strategy ( 策略 )	Writes ( 写入 )	Reads ( 读取 )	Tablet Growth ( tablet 增长 )
range(time)	✗ - 所有写入到最新分区	✓ - 可以修剪与时间绑定的 scan	✓ - 可以在未来的时间段添加新的 tablets
hash(host, metric)	✓ - 在 tablets 上均匀分布	✓ - 可以修剪对特定 hosts 和 metrics 的 scan	✗ - tablets 可以增长到很大

hash分区有利于最大限度的提高写入吞吐量，而范围分区可避免tablet无限增长的问题。这两种策略都可以利用分区修剪来优化不同场景下的扫描。使用多级分区，可以组合这两种策略，已获得两者的优点。同时最大限度的减少每个策略的缺点。

在上面的示例中， time column 上的范围分区与 host 和 metric columns 上的哈希分区相结合。这个策略可以被认为具有二维划分：一个用于哈希级别，一个用于范围级别。在当前时刻写入此表将并行化到哈希桶的数量，在 4 这种情况下。读取可以利用时间限制和特定的 host 和 metric 谓词来修剪分区。可以添加新的范围分区，这将导致创建 4 个额外的 tablet （好像新列已添加到图表中）。

• 双重hash示例

kudu可以在同一个表中支持任意数量的hash分区，只要这些hash分区使用的列是不同的即可。

在上面的示例中，表是host列上的hash分区，分为四个存储桶，散列在metrics上的分区分为三个存储桶，从而产生12个tablet。尽管在使用此策略的时，所有tablets中的写入都将趋于分散，但是与在多个单独列上进行hash分区相比，这种策略更容易出现热点查找。扫描时可以分别利用host和metric列上的等式谓词来进行剪裁分区。