深入浅出Clickhouse: MergeTree引擎设计

发表于 2021-08-15 更新于 2024-03-06 分类于技术文章本文字数： 8.3k 阅读时长 ≈ 8 分钟

LSM(Log-Struct Merge Tree)是大数据领域一种非常常见的技术, 例如LevelDB, RocksDB亦或是HBase都采用了LSM结构来完成存储系统的构架.

但你有没有发现, 这些大数据系统, 大多数都是KV方式的存储系统, 对外的接口也是以点查方式提供的.

虽然例如HBase的RowKey是全局有序的, 但是如果使用RowKey做大规模的范围查询, 它的整体效果可能还比不上在HDFS的文件上直接做过滤更有效.

基于以上的问题, 我们再回顾一下LSM的设计, 解答一下为什么LSM最适合点查, 然后再介绍Clickhouse基于LSM做了哪些取舍, 让MergeTree适合做范围的查询分析.

LSM树回顾

LSM的架构如上图所示, 数据先存放在Memory中, 然后通过一次的合并, 数据会固化到磁盘上.

为了防止每次合并都处理全部的数据, 因此LSM会将数据分层, 上一层比下一层小很多, 并且上一层的合并频率也比下一层多很多次.

由于需要合并去重的要求, 因此LSM树必须要指定一个类似主键之类的不重复的key.

另外一个点, 在Level-1以上, Key是在不同的文件块中, 是绝对不重复的, 而由于一般多是采用Range分区的方式, 我们可以称LSM树是Key键是全局有序且不重复的

当数据更新的时候, LSM只会将数据标记为删除, 或者更新一个数据的版本, 等到后续做数据合并的时候, 再做去重或者删除数据的动作

这就是所谓的写放大问题

当读取数据的时候, 会先读取MemTable, 再读取Immutable MemTable, 最后在磁盘上一层一层读取文件, 直到最后读取到数据.

造成读放大的原因有两个点: 第一, 数据一旦没有命中, 就要往更深的层查找; 第二, 每个层中, 虽然因为全局有序, 点查只需要扫描一个SST文件, 但必须一次扫描整个SST文件.

总结一下, LSM的特点有:

必须有Key键, 且全局有序不重复
写入时, 一层一层写入, 更新删除只做标记
读取时, 一层一层读取, 读取效率在于命中率

然后再结合点查询的场景, 回答一下为什么LSM最适合点查:

Key键全局有序且不重复, 这样查询时一下就能定位到对应的数据地址, 符合点查对对查询时延的要求
插入修改删除只是在Mem中添加数据, 这里就要求一次插入的数据不能太多, 不然内存存储不下, 就要开始合并, 会导致系统不稳定, 而点查一般一次只修改一行数据, 完美符合
读取数据时候, 时延在于命中率, 而点查询的热点效应明显, 主要在前几层能够命中, 整体读取的效率可以接受.

LSM树相对于B+树来说, 强化了Update和Delete的能力, 相对弱化的读取的能力

但是如果是范围查询, 就会出现:

一次更新数据可能是全部数据的20%以上, 例如修改某个字段的标号, 或者删除某些字段的数据
读取时给一个宽裕的过滤范围, 大多数的数据都能匹配中, 例如一个宽泛的前缀匹配

上面两个场景, 如果用LSM树的架构, 基本上是不可取的.

LSM树的参考文章1, 文章2

Clickhouse MergeTree设计

Clickhouse作为一个OLAP系统放弃了对于点查场景的支持, 而是主要面向范围查询的支持, 因此对于MergeTree做了大刀阔斧的修改.

对于Clickhouse来说, 没有单条的插入, 插入修改都抽象为对DataPart的操作.

DataPart在逻辑可以理解为批量的一组数据, 在物理上是磁盘上的一个文件夹,

Clickhouse的数据组织, 如上图所示, 相比于MergeTree:

放弃了全局有序的约束, 只保证DataPart级别是有序的, 此时面对OLAP场景的批量插入, 只需要针对当前插入的数据做排序, 并插入为DP即可
放弃了多层的架构, 没有Memory层, 磁盘也只有一层. 在做Mutation(LSM对应Delete和Update)的时候, 也是DataPart到DataPart的转化

以上这两个设计的特点, 解决了写入和修改的场景, 但有一个明确的假设条件: 高吞吐的插入和 低频次大数据量的修改

此外这种方式, 比较实现列存模式(一个DP包含很行的数据), 因此天然比较适合OLAP, 而LSM比较适合行存, 一般用于OLTP.

但任何设计都有好坏, 一旦应用场景无法满足Clickhouse假设, 那么整体效果就会比较差:

插入批次小: Clickhouse由于不像LSM一样全局有序, 可以明确数据必然在一个数据块中, 因此查询时需要扫描分区裁剪后的所有DP, 因此CK会根据DataPart数量, 合并DataPart, 防止DataPart个数太多, 扫描性能太慢. 但如果插入批次小, 就会不停的触发Merge动作, 导致不必要的资源浪费, 因此都推荐在客户端攒批的方式写入
修改频次高: Mutation在Clickhouse被设计为一个非常重的操作, 因为需要处理大量数据, 但如果此时频次一高, 整个系统CPU马上就会上去
数据要求实时去重: 在Clickhouse设计中, DataPart数据间是没有关联的, 只有在Merge时才会产生关系, 但如果需要实时去重, 那么DP之间就会产生关联性(后写入的数据需要覆盖前面写入的数据), 不管后面如何优化, 这类场景的查询和写入都会比原生的差很多.

各种MergeTree

普通MergeTree

MergeTree表引擎主要用于海量数据分析，支持数据分区、存储有序、主键索引、稀疏索引、数据TTL等。MergeTree支持所有ClickHouse SQL语法，但是有些功能与MySQL并不一致，比如在MergeTree中主键并不用于去重，

CREATE TABLE test_tbl (
  id UInt16,
  create_time Date,
  comment Nullable(String)
) ENGINE = MergeTree()
PARTITION BY create_time
ORDER BY  (id, create_time)
PRIMARY KEY (id, create_time)
TTL create_time + INTERVAL 1 MONTH
SETTINGS index_granularity=8192;

-- 虽然主键定义为(id, create_time), 但是最后还是5条数据, 并不会改变
insert into test_tbl values(0, '2019-12-12', null);
insert into test_tbl values(0, '2019-12-12', null);
insert into test_tbl values(1, '2019-12-13', null);
insert into test_tbl values(1, '2019-12-13', null);
insert into test_tbl values(2, '2019-12-14', null);

ReplacingMergeTree

为了解决MergeTree相同主键无法去重的问题，ClickHouse提供了ReplacingMergeTree引擎，用来做去重, 但这个引擎依然有很多限制:

在没有彻底optimize之前，可能无法达到主键去重的效果，比如部分数据已经被去重，而另外一部分数据仍旧有主键重复；
在分布式场景下，相同primary key的数据可能被sharding到不同节点上，不同shard间可能无法去重；
optimize是后台动作，无法预测具体执行时间点；
手动执行optimize在海量数据场景下要消耗大量时间，无法满足业务即时查询的需求；

CREATE TABLE test_tbl_replacing (
  id UInt16,
  create_time Date,
  comment Nullable(String)
) ENGINE = ReplacingMergeTree()
PARTITION BY create_time
ORDER BY  (id, create_time)
PRIMARY KEY (id, create_time)
TTL create_time + INTERVAL 1 MONTH
SETTINGS index_granularity=8192;

-- 写入主键重复的数据
insert into test_tbl_replacing values(0, '2019-12-12', null);
insert into test_tbl_replacing values(0, '2019-12-12', null);
insert into test_tbl_replacing values(1, '2019-12-13', null);
insert into test_tbl_replacing values(1, '2019-12-13', null);
insert into test_tbl_replacing values(2, '2019-12-14', null);
-- 此时数据依然为5条
-- 强制后台compaction：
optimize table test_tbl_replacing final;
-- 此时数据为3条

CollapsingMergeTree

ClickHouse实现了CollapsingMergeTree来消除ReplacingMergeTree的限制。该引擎要求在建表语句中指定一个标记列Sign，后台Compaction时会将主键相同、Sign相反的行进行折叠，也即删除。

CollapsingMergeTree将行按照Sign的值分为两类：Sign=1的行称之为状态行，Sign=-1的行称之为取消行。

每次需要新增状态时，写入一行状态行；需要删除状态时，则写入一行取消行。

在后台Compaction时，状态行与取消行会自动做折叠（删除）处理。而尚未进行Compaction的数据，状态行与取消行同时存在。

因此为了能够达到主键折叠（删除）的目的，需要业务层进行适当改造

-- 建表
CREATE TABLE UAct
(
    UserID UInt64,
    PageViews UInt8,
    Duration UInt8,
    Sign Int8
)
ENGINE = CollapsingMergeTree(Sign)
ORDER BY UserID;

-- 插入状态行，注意sign一列的值为1
INSERT INTO UAct VALUES (4324182021466249494, 5, 146, 1);

-- 插入一行取消行，用于抵消上述状态行。注意sign一列的值为-1，其余值与状态行一致；
-- 并且插入一行主键相同的新状态行，用来将PageViews从5更新至6，将Duration从146更新为185.
INSERT INTO UAct VALUES (4324182021466249494, 5, 146, -1), (4324182021466249494, 6, 185, 1);
-- 查询数据：可以看到未Compaction之前，状态行与取消行共存。

-- 为了获取正确的sum值，需要改写SQL： 
-- sum(PageViews) => sum(PageViews * Sign)、 
-- sum(Duration) => sum(Duration * Sign)
SELECT
    UserID,
    sum(PageViews * Sign) AS PageViews,
    sum(Duration * Sign) AS Duration
FROM UAct
GROUP BY UserID
HAVING sum(Sign) > 0;

-- 强制后台Compaction
optimize table UAct final;

-- 再次查询，可以看到状态行、取消行已经被折叠，只剩下最新的一行状态行。
select * from UAct;

CollapsingMergeTree虽然解决了主键相同的数据即时删除的问题，但是状态持续变化且多线程并行写入情况下，状态行与取消行位置可能乱序，导致无法正常折叠。

VersionedCollapsingMergeTree

为了解决CollapsingMergeTree乱序写入情况下无法正常折叠问题，VersionedCollapsingMergeTree表引擎在建表语句中新增了一列Version，用于在乱序情况下记录状态行与取消行的对应关系。主键相同，且Version相同、Sign相反的行，在Compaction时会被删除。

-- 建表
CREATE TABLE UAct_version
(
    UserID UInt64,
    PageViews UInt8,
    Duration UInt8,
    Sign Int8,
    Version UInt8
)
ENGINE = VersionedCollapsingMergeTree(Sign, Version)
ORDER BY UserID;


-- 先插入一行取消行，注意Signz=-1, Version=1
INSERT INTO UAct_version VALUES (4324182021466249494, 5, 146, -1, 1);
-- 后插入一行状态行，注意Sign=1, Version=1；及一行新的状态行注意Sign=1, Version=2，将PageViews从5更新至6，将Duration从146更新为185。
INSERT INTO UAct_version VALUES (4324182021466249494, 5, 146, 1, 1),(4324182021466249494, 6, 185, 1, 2);

-- 为了获取正确的sum值，需要改写SQL： 
-- sum(PageViews) => sum(PageViews * Sign)、 
-- sum(Duration) => sum(Duration * Sign)
SELECT
    UserID,
    sum(PageViews * Sign) AS PageViews,
    sum(Duration * Sign) AS Duration
FROM UAct_version
GROUP BY UserID
HAVING sum(Sign) > 0;
-- 强制后台Compaction
optimize table UAct_version final;

-- 再次查询，可以看到即便取消行与状态行位置乱序，仍旧可以被正确折叠。

SummingMergeTree

ClickHouse通过SummingMergeTree来支持对主键列进行预先聚合。在后台Compaction时，会将主键相同的多行进行sum求和，然后使用一行数据取而代之，从而大幅度降低存储空间占用，提升聚合计算性能。

值得注意的是：

ClickHouse只在后台Compaction时才会进行数据的预先聚合，而compaction的执行时机无法预测，所以可能存在部分数据已经被预先聚合、部分数据尚未被聚合的情况。因此，在执行聚合计算时，SQL中仍需要使用GROUP BY子句。
在预先聚合时，ClickHouse会对主键列之外的其他所有列进行预聚合。如果这些列是可聚合的（比如数值类型），则直接sum；如果不可聚合（比如String类型），则随机选择一个值。
通常建议将SummingMergeTree与MergeTree配合使用，使用MergeTree来存储具体明细，使用SummingMergeTree来存储预先聚合的结果加速查询。

-- 建表
CREATE TABLE summtt
(
    key UInt32,
    value UInt32
)
ENGINE = SummingMergeTree()
ORDER BY key

-- 插入数据
INSERT INTO summtt Values(1,1),(1,2),(2,1)

-- compaction前查询，仍存在多行
select * from summtt;
┌─key─┬─value─┐
│   1 │     1 │
│   1 │     2 │
│   2 │     1 │
└─────┴───────┘

-- 通过GROUP BY进行聚合计算
SELECT key, sum(value) FROM summtt GROUP BY key
┌─key─┬─sum(value)─┐
│   2 │          1 │
│   1 │          3 │
└─────┴────────────┘

-- 强制compaction
optimize table summtt final;

-- compaction后查询，可以看到数据已经被预先聚合
select * from summtt;
┌─key─┬─value─┐
│   1 │     3 │
│   2 │     1 │
└─────┴───────┘


-- compaction后，仍旧需要通过GROUP BY进行聚合计算
SELECT key, sum(value) FROM summtt GROUP BY key
┌─key─┬─sum(value)─┐
│   2 │          1 │
│   1 │          3 │
└─────┴────────────┘

AggregatingMergeTree

AggregatingMergeTree也是预先聚合引擎的一种，用于提升聚合计算的性能。与SummingMergeTree的区别在于：SummingMergeTree对非主键列进行sum聚合，而AggregatingMergeTree则可以指定各种聚合函数。

AggregatingMergeTree的语法比较复杂，需要结合物化视图或ClickHouse的特殊数据类型AggregateFunction一起使用。在insert和select时，也有独特的写法和要求：写入时需要使用-State语法，查询时使用-Merge语法。

-- 建立明细表
CREATE TABLE visits
(
    UserID UInt64,
    CounterID UInt8,
    StartDate Date,
    Sign Int8
)
ENGINE = CollapsingMergeTree(Sign)
ORDER BY UserID;

-- 对明细表建立物化视图，该物化视图对明细表进行预先聚合
-- 注意：预先聚合使用的函数分别为： sumState, uniqState。对应于写入语法<agg>-State.
CREATE MATERIALIZED VIEW visits_agg_view
ENGINE = AggregatingMergeTree() PARTITION BY toYYYYMM(StartDate) ORDER BY (CounterID, StartDate)
AS SELECT
    CounterID,
    StartDate,
    sumState(Sign)    AS Visits,
    uniqState(UserID) AS Users
FROM visits
GROUP BY CounterID, StartDate;

-- 插入明细数据
INSERT INTO visits VALUES(0, 0, '2019-11-11', 1);
INSERT INTO visits VALUES(1, 1, '2019-11-12', 1);

-- 对物化视图进行最终的聚合操作
-- 注意：使用的聚合函数为 sumMerge， uniqMerge。对应于查询语法<agg>-Merge.
SELECT
    StartDate,
    sumMerge(Visits) AS Visits,
    uniqMerge(Users) AS Users
FROM visits_agg_view
GROUP BY StartDate
ORDER BY StartDate;

-- 普通函数 sum, uniq不再可以使用
-- 如下SQL会报错： Illegal type AggregateFunction(sum, Int8) of argument 
SELECT
    StartDate,
    sum(Visits),
    uniq(Users)
FROM visits_agg_view
GROUP BY StartDate
ORDER BY StartDate;

描述和示例皆摘抄自阿里云