共计 7254 个字符，预计需要花费 19 分钟才能阅读完成。
实时数据的剖析对企业数字化经营和决策未然至关重要，因而很多用户构建了实时数据分析平台。为了对业务各类“变更”进行实时剖析、疾速响应业务变动，实时数据更新 成了实时剖析的外围要求。很多用户在进行实时数据更新时，查问性能不够现实，大大降低了业务剖析效率。
和其余行业当先 OLAP 数据库不同，StarRocks 设计和实现了 Primary Key 模型 ，让数据能够更好地实时更新，并且具备极速的查问能力。以后 Primary Key 模型曾经打磨了一年多，基于全新的设计和实现， 在大规模实时数据进行写入时，查问性能能够做到其余行业当先 OLAP 数据库的 3-5 倍。
以后 StarRocks 曾经在 超过 110 家大型用户的外围业务场景下进行大规模应用，其中很多用户已胜利采纳 Primary Key 模型晋升了实时剖析能力，如腾讯、Airbnb、顺丰、众安保险等。
本文就将介绍 StarRocks 2.x 版本中实现的 Primary Key 模型的技术底细，包含实时数据更新机制，以及针对实时更新数据的极速查问的实现原理。
#01
背景
—
随着实时数据分析场景的倒退，对实时可更新数据的剖析需要也越来越多，例如：
- TP 零碎通过 CDC 实时同步数据 Binlog 到 AP 零碎，能够十分不便地实时对业务数据“变更”进行剖析，这是最常见的场景。
-
传统的 OLAP 数据流采纳 ETL (Extract-Transform-Load) 的模式，数据充沛加工后再导入 AP 零碎，而随着古代 AP 零碎的能力晋升，ELT (Extract-Load-Transform) 模式的数据流逐步风行。
即把原始或者粗加工的数据先导入 AP 零碎，在 AP 零碎外部应用 SQL 对数据进行各种加工转换后再查问。
这种形式有很多益处：对立应用一套零碎开发保护老本更低；相比应用其余计算框架解决 ETL，SQL 易用性更好；最初在同一个 AP 数据库系统内通过事务机制能够更加简略便当地保证数据的一致性。
而要反对实时 ELT 中的各种数据加工解决逻辑，数据库对于实时更新的反对也变成了强需要。
#02
技术计划
—
AP 数据库系统中通常应用列存作为底层的存储引擎，通常一个表蕴含多个文件（或 Rowset），每个文件应用列存格局组织（例如 Parquet），并且是不可批改的。
在这种组织构造的前提下反对更新，常见的技术计划有上面几种：
Copy-on-Write
当一批更新到来后，须要查看其中每条记录跟原来的文件有无抵触（或者说 Key 雷同的记录）。对有抵触的文件，从新写一份新的、蕴含了更新后数据的。
这种形式读取时间接读取最新数据文件即可，无需任何合并或者其余操作，查问性能是最优的，然而写入的代价很大，因而适宜 T+1 的不会频繁更新的场景，不适宜实时更新场景。
很多数据湖都应用了这种形式实现更新，例如 Delta Lake、Hudi 的 Copy-on-Write 表等。
Merge-on-Read
当一批更新到来后，间接排序后以列存或者行存的模式写入新的文件。因为数据在写入时没有做去重或者说抵触查看，就须要在读取时通过 Key 的比拟进行 Merge 的形式，合并多个版本的数据，仅保留最新版本的数据返回给查问执行层。
这种形式写入的性能最好，实现也很简略，然而读取的性能很差，不适宜对查问性能要求很高的场景。采纳这种计划的包含 Hudi 的 Merge-on-Read 表，StarRocks 的 Unique 模型表，ClickHouse 的实时更新模型等。
Delta Store
当一批更新到来后，通过主键索引，先找到每条记录原来所在的文件和地位（通常是一个整数的行号）。把地位和所做的批改作为一条 Delta 记录，放到跟原文件对应的一个 Delta Store 中。查问时，须要把原始数据和 Delta Store 中的数据合并（或者说利用 Delta 数据）。
因为 Delta 数据是依照行号组织的，合并过程间接依照行号进行合并即可，和 Merge-on-Read 的依照 Key 进行合并相比，查问性能好很多。这种形式因为写入时要查问索引，写入性能稍差，然而读取的性能要好很多。相当于就义了一些写入性能换来读性能。另外因为引入了主键索引和 Delta Store，复杂性进步。采纳这种计划的典型零碎就是 Kudu，当然还有一些内存数据库 TP 零碎也罕用这种计划。
Delete-and-Insert
当一批更新到来后，通过主键索引，先找到每条记录原来所在的地位，把该条记录标记为删除，而后把最新数据作为新记录写入新文件。读取时，依据删除标记来将旧版本过期数据过滤掉，留下最新更新后的数据。
因为无需像 Merge-on-Read 和 Delta Store 模式下进行 Merge，另外过滤算子能够下推到 Scan 层间接利用各类索引进行过滤缩小扫描开销，所以查问性能的晋升空间更大。
和 Delta Store 相似，此模式也就义了一些写入性能换取读性能，以后业界也有一些利用：比方 SQL Server 的 In-memory 列存等。Delete-and-Insert 模式须要引入主键索引以及存储和治理删除标记，在大规模实时更新和查问场景下实现难度十分大。
以后 StarRocks 的 Primary Key 模型次要采纳了 Delete-and-Insert 模式，并且进行了很多新的设计，以反对在大规模实时数据更新时提供极速的查问性能。
#03
StarRocks 实时更新实现
—
StarRocks 全新增加了一种新的表模型: Primary Key，该模型的表反对依照主键对一行或多行进行更新 (Upsert) 或者删除 (Delete) 操作。
StarRocks 对表的操作通过导入 (Load) 的模式载入零碎。每个导入工作能够看作一个独自的写入事务，StarRocks 保障导入事务的 ACID 属性。也就是说，对于一个跨多个 Tablet 的大批量导入事务，导入也是原子失效的，并且保障并发导入事务之间的隔离性。
事务整体流程
如下图所示，一个导入事务能够分为两个阶段：Write , Commit.
- Write 阶段，客户端把该导入事物的数据依照分辨别桶规定散发到对应的 Tablet，每个 Tablet 收到数据后把数据写成外部的列存格局，造成一个 Rowset；
- Commit 阶段，所有数据都写入胜利后，FE 向所有参加的 Tablet 发动事务、提交 Commit，每个 Commit 会携带一个 Version 版本号，代表 Tablet 数据的最新版本。
Tablet 内部结构
Tablet 是 StarRocks 底层存储引擎的根本单元，每个 Tablet 外部能够看作一个单机列存引擎，负责对数据的读写操作。
为了反对实时更新，Primary 模型的单机存储引擎从新设计，与其余三个模型 (Duplicate, Aggregate, Unique) 原有的存储引擎曾经有了显著的区别。如下图所示，其次要蕴含以下 4 个组件：
- Meta: 元数据，保留 Tablet 的版本历史以及每个版本的信息，比方蕴含哪些 Rowset 等。序列化为 Protobuf 后存储在 RocksDB 中，为了快速访问，也会缓存在内存中。
- Rowset: 一个 Tablet 的所有数据被切分成多个 Rowset，每个 Rowset 以列存文件的模式存储，其外部组织编码方式相似 Parquet 文件，然而是 StarRocks 特有的格局。
- Primary Index: 主键索引，保留主键到该记录所在位置的映射。目前残缺保护在内存中，不长久化到磁盘，在导入进行时按需构建，一段时间没有继续导入时又会开释以节约内存。
- DelVector: 记录每个 Rowset 中被标记为删除的行，比方一个文件中有 10000 行数据，其中 200 行被标记删除，则能够应用一个 Bitmap 来标记被删除的行。个别都是很稠密的，应用 RoaringBitmap 能够高效存储和操作，同样保留在 RocksDB 中，但也会缓存在内存中以便可能快速访问。
元数据组织
元数据的组织会有一个版本历史，每次 Commit 或者 Compaction 都会生成一个新版本，记录了该版本蕴含了那些数据，相比上一个版本做了那些改变。下图是一个元数据版本历史的例子:
能够看到每次 Rowset Commit 或者 Compaction Commit，都会生成一个新的版本，每个版本会记录该版本蕴含哪些 Rowset。
当然随着数据导入，版本历史会逐步积攒，而较老的版本不太会再被应用到，所以后盾 GC 线程会定期删除老版本。随着老版本的删除，一些 Rowset 可能不会被任何版本援用，也能够一并删除，如下图所示：
写入流程
上文提到，一个写入事务的数据会依据分辨别桶信息散发到相干的 Tablet，每个 Tablet 负责写入一部分数据，每个 Tablet 接管到这部分数据后，会执行一个写入流程，最终把这部分数据退出本人治理的数据集。下图展现了写入流程的各个阶段:
具体流程如下:
- 收到的各个批次数据在 MemTable 中积攒，MemTable 满了之后，须要 Flush 到磁盘
- Flush 蕴含 Sort、Merge、Split 三个操作，Sort 先按主键对数据排序，Merge 对主键雷同的多条记录进行合并，只保留最新版本的数据。Split 把这批操作中的 Upsert 和 Delete 操作拆分开来，写入不同的文件
- 该导入的所有数据发送结束并且 Flush 后，会生成一个蕴含多个文件的新 Rowset
- FE 发动 Commit 流程，针对 Tablet 执行 Commit 流程，BE 蕴含 3 步:
- 查找并更新 Primary Index，记录所有被更新的记录，标记为删除
- 依据标记为删除的记录，生成 DelVector
- 生成新版本的 Meta，与 DelVector 一起写入 RocksDB
写入事务并发管制
StarRocks 反对并发导入，多个导入事务间可能产成抵触，须要在并发管制解决抵触，每个导入事务分为两个阶段：Write 和 Commit.
- Write: 写入数据生成 Rowset 文件阶段，能够并行执行，占据事务的绝大部分工夫
- Commit: FE 发动 Commit 后，查找主键索引，生成 DelVector 和元数据的操作，须要序列化执行，但只占整个导入的很小一部分工夫，所以序列化执行对导入性能影响较小
导入遵循 Last Write Wins 准则，对于并发导入事务中雷同 Key 的记录抵触，版本大的记录笼罩版本小的记录。对于并发事务中写写抵触的解决形式，个别有两种：
- 一种是乐观的加锁形式，毛病是有加锁的开销，并且行级别的锁对超大写事物不太事实，另外加锁也会影响并发写入的性能。
- 一种是乐观形式，写入时不查看抵触，在 Commit 时查看抵触，如果抵触再 Abort，AP 零碎中的导入通常是超大事务，Abort 从新导入的代价太大也不现实。
StarRocks 并没有采纳这两种经典的形式，其在事务抵触解决上是独特的。Commit 阶段序列执行，应用 DelVector 来解决抵触，防止了加锁的开销和性能影响。
写入抵触后也不须要回滚，只须要将抵触中老的记录标记为删除，非常适合导入数据这种导入工作能够依照纯写大事务进行解决的场景。
主键索引
Commit 阶段的最次要工作是查找和更新主键索引，约占整个 Commit 过程 90% 以上的工夫。Commit 的速度次要取决于主键索引的性能，因而主键索引目前应用内存 HashMap 来实现，和计算层一样应用高性能 HashMap 库 phmap。HashMap 的 key 是多列编码后的 Binary 串，Value 是由 (rowset_id, rowid) 组成的 64bit 整数，能够依据主键查找主键对应的行在哪个 Rowset 的第几行。
内存 HashMap 相比 RocksDB 等通用 KV 存储在性能上有很大劣势，通常在古代 CPU 上每个操作耗时仅 20ns~200ns，也就是单核能够达到 5M-50Mop/s，可能保障批量导入的大事务疾速实现 Commit。然而其最大的劣势是须要耗费内存。咱们针对定长和变长类型的主键别离做了一些优化，以升高内存占用，将来会继续优化 HashMap 的内存占用，另外会摸索实现基于 SSD/PMEM 的可长久化的主键索引。
主键索引目前是按需加载的，在有写入时会读取主键列构建，在长时间没有写入后会开释以节约内存。这非常适合有冷热数据模式的场景，即一条记录在创立后的一段时间内是热数据常常被更新，过一段时间后逐步变冷不再更新。数据按天分区后，只有最近几天的分区才会有导入存在，这样最近几天的 Tablet 的主键索引才会被加载，整体内存使用量可控。
典型的场景比方各种订单场景，包含电商的订单、打车 / 共享单车订单等，或者利用或者设施的 Session 等。
Compaction
数据继续实时导入会导致存在大量小的 Rowset 文件，另外对数据的更新和删除也会使得 Rowset 中的大量记录被标记为删除，这些都会影响查问的读取性能，并且会节约存储空间。
和 LSM 等存储引擎相似，StarRocks 也会在后盾利用 Compaction 来优化数据的组织，但其具体机制和 LSM 也有很大不同：
- 首先在抉择 Rowset 进行 Compaction 的策略上，会依据 Cost，优先选择小文件和大量记录被删除的文件。
- 因为在写入时曾经去除了反复数据，存储中曾经不存在反复的记录，所以 Compaction 不须要思考重复记录的合并。
- 因为原生反对 Delete，Rowset 文件中也不存在 Delete 或者 RangeDelete 的 Tombtone 标记，所以解决上也更加简略。
- 然而因为引入了主键索引，Compaction 会使得记录的理论地位发生变化，须要额定保护主键索引的一致性，减少了复杂度。
Compaction 的流程和失常写入流程相似：
- 依据抉择策略，筛选 Compaction 的输出 Rowsets
- 合并 Rowsets，生成新的 Rowset
- Commit 该 Rowset，更新主键索引，生成 DelVector，在元数据中原子替换掉输出的 Rowsets
在 Compaction 的过程中，同样可能有并发的导入在执行，可能会与 Compaction 发生冲突。为了检测并解决抵触，咱们会记录 Compaction 的原始 Rowset 的 ID，在 Commit 更新主键索引时，查看每一行对应 Rowset ID 是否产生过扭转。如果产生过扭转，意味着这一样曾经被更新过，则疏忽对这一行的更新，并把 Rowset 中对应的行标记为删除。
读取流程
相比其余设计和实现，Primary Key 表在读取性能上有很大劣势，多个因素综合下来，查问性能会有 3-5 倍以上的晋升，其中次要起因有:
- 去除 Merge 操作：因为历史重复记录曾经在写入时标记“删除”，读取时不再须要 Merge 过程来去重以找到最新版本数据，对于很多查问来说，Merge 过程是整个查问流程的瓶颈，无需 Merge 能够很大进步性能。另外，去除 Merge 操作后整个执行树都能够向量化计算，查问性能也有极大晋升。
- 谓词下推：其余很多零碎里谓词下推无奈下推到 Merge 操作以下。咱们在去除 Merge 操作后，谓词下推能够中转低层 Rowset 的 Scan 操作。这样 Rowset 文件中的二级索引 (zonemap, bitmap, bloom) 才能够发挥作用，减速查问实现数倍的晋升。
- 并行扫描：有多个 Rowset 文件，多个文件的 Scan 能够并行操作。
下图是一个查问应用 Merge-on-Read 模式 (比方 StarRocks 的 Unique key 模型和 ClickHouse 的实时更新模型) 和 Delete+Insert 模式 (StarRocks 的 Primary Key 模型) 的比照:
可见，应用 Primary Key 模式，省去了 Merge 操作的开销，省去了读取 order_id 的 io, state==2 的谓词能够利用 Bitmap 索引减速，整个操作树传输的数据量也少了很多。
咱们模仿了一个订单表的场景，测试比照 Unique 模型表和 Primary 模型表的性能。该表每天 1000 万订单，每个订单会被更新屡次，咱们继续导入了 20 天的数据。在边实时导入边查问的状况下，简略查问最好状况下会有 10 倍以上的性能晋升；在暂停导入一段时间后独自查问的状况下，也会有 3 倍左右的性能晋升。
#04
将来工作
—
以后反对的操作类型包含 Upsert 和 Delete，能够满足最罕用的场景，包含 TP 零碎 CDC 同步数据到 StarRocks 需要，失常的批量导入去重需要等。随着利用场景的复杂性进步，对 StarRocks 提出了各种新的需要，这些是咱们下一步要鼎力投入的个性：
Partial-Update（局部列更新）
反对局部列更新，典型的场景是上游几个模块实时写入一个大宽表，每个模块仅更新表中的一部分列，在大宽表里主动实现 Join 的操作。
目前实现这种 Join 操作，一个计划是应用 T+1 的形式，在内部应用 Hive/Spark 等计算框架批量实现，无奈做到实时；另一个计划是在 Flink 等流式零碎中实时 Join 后再导入 AP 零碎，限度较大，实现也非常复杂。
Conditional-Update（条件更新）
反对依据条件更新，导入数据满足肯定条件才更新。典型的一个场景是：上游数据乱续达到，须要通过一个工夫戳来判断是否须要更新。
Read-Write Update（通用读写事务）
局部列更新和条件更新操作实质上是一种读写事务，相比 Upsert / Delete 这种纯写事务，实现上要简单一些。发生冲突后，简略的 Last-Write-Wins 策略不再实用，须要进一步解决。然而相比通用的读写事务，还是有一些个性能够利用，来优化抵触的检测和解决。
ELT 更新
ELT(Extract-Load-Transform)逐步风行。先把原始数据导入 AP 零碎，在零碎外部应用各种 SQL 语句对数据进行进一步加工。这样岂但能够减速查问，简化了开发和运维难度，还实现了在一个零碎内治理数据的依赖关系。
在简单的 ELT 数据流中，常会波及对数据的批量更新。这通常是批量数据的大规模读写事务，传统 TP 零碎的并发管制机制并不能很好解决大事务带来的挑战，须要有创新性的解决方案。
作者
常冰琳 | StarRocks 外围研发、Apache Kudu PMC