大数据存储引擎——Kudu

╰半夏微凉° 2022-12-01 05:28 325阅读 0赞

# 一、什么是Kudu【Fast Analytics on Fast Data】 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70][]

是一个既支持随机读写，又支持OLAP（Online analytical processing）分析的大数据存储引擎，平衡HDFS和HBase随机读写和批量分析性能的存储引擎。

## 1、组织架构 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 1][]

**Master Server：**负责监听集群tserver状态、管理元数据catalog tablet等功能

**Table Server：**负责数据tablet存储，并向client提供数据读写服务。对于给定tablet，一个tablet server充当leader，其他tablet server充当follower副本，只有leader负责写请求，leader和follower负责读请求。

**Table：**一张table是数据存储在kudu的位置，其具有schema和全局有序的primary key，Table被分为很多段（Tablets）

**Tablet：**一张table连续的“segment”，与其他数据存储一样存在副本机制。

**Catalog Table：**元数据表，用来存储table（schema、locations、states）与tablet（现有tablet列表，每个tablet及其副本所处tserver，tablet当前状态以及开始和结束键）信息。

Kudu利用副本实现分区容错性，各副本间通过Raft协议来保证数据一致性，与ZAB类似，都是Paxos协议的工程简化版本。

## 2、数据分区 ##

与大多数大数据存储引擎类似，Kudu对表同样进行横向切分，利用灵活的数据分区策略将数据分别存储在多个tablets中。一般数据分区策略主要包含：**Range Partitioning**（HBase）和**Hash Partitioning**两种。

**Range Partitioning：**按照字段值范围进行分区，其优势是有利于批量的顺序读写，劣势是同一范围内的数据写入会落在单个tablet中，写压力增大。

**Hash Partitioning：**将数据按照Hash均匀分散到各个tablet中，其优势是写入速度快，劣势是顺序读写时，数据太分散，降低吞吐量。

Kudu融合两种分区策略，支持用户对一个表指定一个范围分区规则和多个Hash分区规则。

## 3、存储实现（列式存储） ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 2][]

Kudu通过[LSM][]树实现数据的存储，一个Table包含多个Tablets，而每个Tablet又由存储其元数据信息的MetaData 和RowSet组成，其中，RowSet为Kudu的最小存储单元，RowSet内部又分为MemRowSets、DiskRowSets，数据先写入MemRowSet（缓存），MemRowSet满后再刷入磁盘成为一个DiskRowSet（持久），而DiskRowSet一经写入，就无法修改，该过程同样利用WAL做数据恢复。DiskRowSet又分为多个文件（UndoFile： BaseData之前的数据历史数据；RedoFile：BaseData之后的mutation改变记录；其他后续会讲到）。

![20200826142042244.png][]

因为DiskRowSet不可修改，为了**实现数据更新**，Kudu将DiskRowSet分为两部分：base data、delta stores。base data负责存储基础数据，而delta store负责存储base data中的变更数据。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 3][]

Kudu数据从MemRowSet刷到磁盘后就形成一份DiskRowSet（只包含base data），每份DiskRowSet在内存中都会有一个对应的DeltaMemStore，负责记录该DiskRowSet的数据变更操作（更新、删除）。DeltaMemStore内部通过维护一棵B树索引，映射到每个row\_offset对应的数据变更。DeltaMemStore数据增长到一定程度后转化成二进制文件存储到磁盘，形成一个DeltaFile。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 4][]

**为提高随机读写性能**，Kudu在base data中针对主键做了几类索引。

（1）主键范围索引：记录本DiskRowSet中主键范围，用于粗粒度过滤一些主键范围；

（2）布隆过滤器（BloomFile）：通过主键的布隆过滤器实现不存在数据的过滤；

（3）主键索引（Ad\_hoc Index）：精确定位一个主键是否存在，以及具体位置，通过B树为数据结构的主键索引快速查找。

同样，随着时间的增长，Kudu中base data和其对应的若干DeltaFile越来越多，因此Kudu会定期执行Compaction，主要包含两部分compaction：

**DeltaFile compaction：**定期将DeltaFile合并回base data，由于Kudu是列式存储，因此文件合并时只合并部分变更列到base data中对应列。

**DiskRowSet compaction：**定期将DiskRowSet合并，将被删除的数据彻底删除，减少同key范围内数据的文件数，提升索引效率。

## 4、写入数据 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 5][]

当Client发起写请求时，先根据主键从Master Server中获取要访问的目标Tablet，然后依次到对应的Tablet获取数据。首先通过主键范围过滤掉一批不存在的目标主键；然后根据RowSet中记录的布隆过滤器（BloomFile），过滤掉确定不存在的目标主键；最后通过B树索引（Ad\_hoc Index），精确定位目标主键是否存在。

## 5、更新数据 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 6][]

前面与写数据类似，根据索引定位到具体row\_offset后，将变更写到对应的delta store中。

## 6、读取数据 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 7][]

首先扫描数据的主键范围，定位到目标Tablets，然后读取Tablets中的RowSets，读取RowSet时，先根据主键过滤要scan范围，然后加载范围内的base data，再扫描对应delta stores，应用所有变更，最后union上MenRowSet中内容，返回数据给Client。

## 7、内部实现原理 ##

根据上述介绍，可以串联下图，Kudu内部实现原理。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 8][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70]: /images/20221123/22dd2f29d72e4eacb12e0aef5e8ea4af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 1]: /images/20221123/b8d8f3bef06c4104af2f74cc74632019.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 2]: /images/20221123/700526c81c1a4a35a03a76f176a9b57f.png
[LSM]: https://www.jianshu.com/p/3fb899684392
[20200826142042244.png]: /images/20221123/83425235fb7c4e4aa79e4908a2cf064a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 3]: /images/20221123/0aefe2f86dbf416fbdee4cf5869f710e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 4]: /images/20221123/b19ac1add92746708876db91014bb01d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 5]: /images/20221123/b8e2e1011e99493b886a9483a7a718a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 6]: /images/20221123/a906c9ed7fa14f9789914c958c80fc66.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 7]: /images/20221123/775c978a27c04ace962c8e81a4b2fe41.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1MDYyMjk5_size_16_color_FFFFFF_t_70 8]: /images/20221123/90a8109268b249f3b09669bf18037bf4.png