UniqueMergeTree 开发的业务背景
首先，咱们看一下哪些场景须要用到实时更新。
咱们总结了三类场景：
- 第一类是业务须要对它的交易类数据进行实时剖析，须要把数据流同步到 ClickHouse 这类 OLAP 数据库中。大家晓得，业务数据诸如订单数据天生是存在更新的，所以须要 OLAP 数据库去反对实时更新。
- 第二个场景和第一类比拟相似，业务心愿把 TP 数据库的表实时同步到 ClickHouse，而后借助 ClickHouse 弱小的剖析能力进行实时剖析，这就须要反对实时的更新和删除。
- 最初一类场景的数据尽管不存在更新，但须要去重。大家晓得在开发实时数据的时候，很难保障数据流里没有反复数据，因而通常须要存储系统反对数据的幂等写入。
咱们能够总结一下这三类场景的共同点：
- 从数据的新鲜度看
这三个场景其实都不须要亚秒级的新鲜度，往往做到秒级或者分钟级的数据新鲜度就能够了，因而能够采纳 mini-batch 的实时同步计划。
- 从应用上看
这三类场景都能够通过提供基于惟一键的 upsert 性能来实现，不论是更新还是幂等解决的需要。
- 从读写要求上看
因为大家用 OLAP 数据库最外围的诉求是心愿查问能够有一个非常低的提早，所以对读的性能要求是十分高的。对于写，尽管也须要高吞吐，但更多关注 Scalability，即是否通过加资源来进步数据流的写吞吐。
- 从高可用性上看
这三个场景都须要能反对多正本，来防止整个零碎存在单点故障。
以上就是咱们开发 UniqueMergeTree 的背景。
常见的列存储实时更新计划
上面介绍下在列存储里反对实时更新的常见技术计划。
key-based merge on read
第一个计划叫 key-based merge on read，它的整个思维比拟相似 LSMTree。对于写入，数据先依据 key 排序，而后生成对应的列存文件。每个 Batch 写入的文件对应一个版本号，版本号能用来示意数据的写入程序。
同一批次的数据不蕴含反复 key，但不同批次的数据蕴含反复 key，这就须要在读的时候去做合并，对 key 雷同的数据返回去最新版本的值，所以叫 merge on read 计划。ClickHouse 的 ReplacingMergeTree 和 Doris 用的就是这种计划。
大家能够看到，它的写门路是非常简单的，是一个很典型的写优化计划。它的问题是读性能比拟差，有几方面的起因。首先，key-based merge 通常是单线程的，比拟难并行。其次 merge 过程须要十分多的内存比拟和内存拷贝。最初这种计划对谓词下推也会有一些限度。大家用过 ReplacingMergeTree 的话，应该对读性能问题深有体会。
这个计划也有一些变种，比如说能够保护一些 index 来减速 merge 过程，不必每次 merge 都去做 key 的比拟。
mark-delete + insert
mark-delete + insert 刚好反过来，是一个读优化计划。在这个计划中，更新是通过先删除再插入的形式实现的。
Ref“Enhancements to SQLServer Column Stores”
上面以 SQLServer 的 Column Stores 为例介绍下这个计划。图中，每个 RowGroup 对应一个不可变的列存文件，并用 Bitmap 来记录每个 RowGroup 中被标记删除的行号，即 DeleteBitmap。解决更新的时候，先查找 key 所属的 RowGroup 以及它在 RowGroup 中行号，更新 RowGroup 的 DeleteBitmap，最初将更新后的数据写入 Delta Store。查问的时候，不同 RowGroup 的扫描能够齐全并行，只须要基于行号过滤掉属于 DeleteBitmap 的数据即可。
这个计划就义了写入性能。一方面写入时须要去定位 key 的具体位置，另一方面须要解决 write-write 抵触问题。
这个计划也有一些变种。比如说写入时先不去查找更新 key 的地位，而是先将这些 key 记录到一个 buffer 中，应用后台任务将这些 key 转成 DeleteBitmap。而后在查问的时候通过 merge on read 的形式解决 buffer 中的增量 key。
因为 ClickHouse 的 ReplacingMergeTree 曾经实现了计划一，所以咱们心愿 UniqueMergeTree 能实现读优化的计划。
UniqueMergeTree 应用与实现
上面介绍 UniqueMergeTree 的具体应用。咱们先介绍一下它的个性。
UniqueMergeTree 表引擎个性
首先 UniqueMergeTree 反对通过 UNIQUE KEY 关键词来指定这张表的惟一键，引擎会实现惟一束缚。对于 UNIQUE 表的写入，咱们会采纳 upsert 的语义，即如果写入的是新 key，那就直接插入数据；如果写入的 key 曾经存在，那就更新对应的数据。
而后咱们也反对，指定 UNIQUE KEY 的 value 来删除数据，满足实时行删除的需要。而后和 ReplacingMergeTree 一样，也反对指定一个版本字段来解决回溯场景可能呈现的低版本数据笼罩高版本数据的问题。最初咱们也反对数据在多正本的同步。
上面是一个应用示例。首先咱们建了一张 UniqueMergeTree 的表，表引擎的参数和 ReplacingMergeTree 是一样的，不同点是能够通过 UNIQUE KEY 关键词来指定这张表的惟一键，它能够是多个字段，能够蕴含表达式等等。
上面对这张表做写入操作就会用到 upsert 的语义，比如说第 6 行写了四条数据，但只蕴含 1 和 2 两个 key，所以对于第 7 行的 select，每个 key 只会返回最高版本的数据。对于第 11 行的写入，key 2 是一个曾经存在的 key，所以会把 key 2 对应的 name 更新成 B3; key 3 是新 key，所以直接插入。最初对于行删除操作，咱们减少了一个 delete flag 的虚构列，用户能够通过这个虚构列标记 Batch 中哪些是要删除，哪些是要 upsert。
示例展现的是单 shard 的写入，而生产环境通常蕴含多个 shard，。多个 shard 写入的时候就波及到了你要解决数据分片的问题，其实它的次要目标就是咱们须要把雷同的 key 的数据写到同一个 shard 里，不然如果你的 key 可能存在多个 shard 的话，你的去重开销就十分大。
分布式表写入: 分片计划抉择
下面的示例展现了单 shard 的写入，然而生产环境通常蕴含多个 shard，如何实现雷同 key 的数据写往同一个 shard 呢？这里有两种计划。
- internal sharding: 即由引擎自身来实现数据的分片。具体来说，能够间接把数据写到 ClickHouse 的分布式表，它会依据 sharding key 实现数据的分片和路由。Internal sharding 的长处是分片形式对用户通明，不容易出错；另外不同表的分片算法是统一的，在做多表关联的时候，能够利用数据的分片特色来优化查问。这是 ByteHouse 云数仓版应用的形式。
- external sharding: 由用户或者 SDK 负责数据的分片和路由，这是 ByteHouse 企业版应用的形式。Internal sharding 有个问题是，在实时写入场景，每个微批自身就不大，如果再对它进行分片会产生更多的小文件，影响写入吞吐。External sharding 在内部实现数据的攒批，每个微批只写一个 shard，这样 batch size 更大，整体的写吞吐会更高。它的问题是须要由用户端保障分片的正确性，比拟容易出错。External sharding 比拟适宜 kafka 导入等繁多写入场景。如果表有多个写入通道，用户须要保障多个通道采纳统一的分片形式，老本更高。
单机版实现: UniqueMergeTree 读写链路
上面介绍下 UniqueMergeTree 在单节点的读写链路。
- 写链路: 首先要判断写入 key 所属的 part 以及它在 part 中的行号，接着去更新对应 part 的 delete bitmap，将写入 key 从原来的 part 里标记删除掉，最初将新数据写入新 part 里。为了实现下面的逻辑，咱们为每个 part 新增了一个 key index，用于减速从惟一键值到行号的查找。另外每个 part 蕴含多个 delete file，每个 delete file 对应一个特定版本的 delete bitmap。
- 读链路: 先获取所有 part 的 delete bitmap 快照，而后读取每个 part 的时候应用对应的 delete bitmap 过滤掉标记删除的行。这样就保障了整体的唯一性束缚。
此外，还须要思考并发场景的两种抵触: write-write conflict 和 write-merge conflict。
先介绍 write-write conflict。产生该抵触的起因是 write 应用了 upsert 语义，因而当两个并发事务更新同一行的时候会产生抵触。比方左图中的两个并发事务同时更新 P1 的 Key A 行，如果不做并发管制，两个事务可能都去标记删除 P1 中的 Key A 行，而后写出 P2 和 P3，最终 P2 和 P3 就同时蕴含了 Key A。
TP 数据库个别通过锁或者 OCC 的形式解决 write-write conflict，但在 AP 场景中用行锁或者行级冲突检测的代价是比拟高的。思考到 AP 场景数据都是批量写入，咱们采纳了更简略的表锁来实现单表的写入串行化。
再来看右图的 write-merge conflict。多个 part 在后盾合并过程中，并发的前台写入事务可能会更新 part 的 delete bitmap。如果不做并发管制，就会产生写入事务标记删除的行在 part 合并后“复活”的景象。要解决这个问题，后盾合并工作须要感知到合并过程中，前台写入事务更新了哪些 key。
解决 Write-Merge Conflict
咱们给每个 merge task 新增了一个 DeleteBuffer，用于缓存 merge 过程中前台写入工作删除的 key。
Merge task 开始时，先获取表锁创立 DeleteBuffer，并获取 input part 的 delete bitmap 快照。接着读取 input part，过滤掉标记删除的行，生成合并后的长期 part。这个过程中，并发的写入事务如果发现要更新 delete bitmap 的 part 正在被合并，就会将要删除的 key 记录到 merge task 的 DeleteBuffer。Merge task 在提交前会再次获取表锁，将 DeleteBuffer 中的 key 转成新 part 的 delete bitmap。
那么如何限度 DeleteBuffer 的内存应用呢？一种简略无效的形式是，写入事务如果发现 DeleteBuffer 的大小超过了阈值，就间接 abort 对应的 merge 工作，期待下次合并。因为 DeleteBuffer 比拟大阐明在合并过程中 input part 有很多增量的删除，重试能够减小 merge 后的 part 大小。
性能评估
咱们应用 YCSB 对 UniqueMergeTree 的写入和查问性能做了性能测试，后果如上图。能够看到，与 ReplacingMergeTree 相比，UniqueMergeTree 的写入性能尽管会有 40% 到 50% 的降落，但在查问性能上获得了数量级的晋升。咱们进一步比照了 UniqueMergeTree 和一般 MergeTree 的查问性能，发现两者是十分靠近的。查问性能的晋升次要归功于以下几点：
- 防止了单线程的 merge-on-read，流水线齐全并行化
- DeleteBitmap 的最新版本常驻内存
- 标记删除的 Mark 能够间接跳过
- Combine pre-where filter & delete filter，缩小 IColumn::filter 次数
总结：教训与后续布局
咱们在 2020 年初上线了 UniqueMergeTree，目前线上利用的表数量超过了 1000，还是十分受业务欢送的。整个过程中，我认为做的比拟对的决策有两点：
- 在读写衡量方面，就义一部分写性能来换取更高的读性能。咱们发现很多业务场景的痛点是查问性能。尽管 UniqueMergeTree 的写吞吐不如 MergeTree，但通过减少 shard 横向扩大，曾经能满足大部分业务的需要。
- 设计上没有对表的数据量做太多限度。例如 KeyIndex，一种做法是假如 KeyIndex 能够齐全存储在内存中，但咱们认为这会限度 UniqueMergeTree 的利用场景。因而尽管咱们第一版实现的也是 in-meomry index，但起初比较顺利地演进到了 disk-based index。
对于后续布局，咱们会重点尝试两个方向：
- 局部列更新：有些场景须要多个数据流更新同一张表的不同字段，因而须要局部列更新的能力。
- 写吞吐优化：写吞吐会间接影响每个集群能接入的实时数据规模。咱们在表锁粒度和 KeyIndex 两方面都看到了进一步优化的空间。
欢送点击理解 ByteHouse
基于开源 ClickHouse 的剖析型数据库，反对用户交互式剖析 PB 级别数据，通过多种自研表引擎，灵便反对各类数据分析和利用。
欢送关注字节跳动数据平台微信公众号，回复【1】进入官网交换群