Paimon

{  \"version\

ADD

snapshot expire快照过期清理

sst-005.orc （DELETE）（pk301 - pk400 ）sorted

bucket-2

manifest-2

snapshot reader全量

LSMmemtable

当前主流的LSM-Tree基本结构如下图，分为内存和磁盘两部分。内存采用MemTable数据结构，可以通过B+树或跳表实现。MemTable用于接受最新的数据更新操作，维护内部数据in-tree逻辑上的有序。磁盘中的部分数据存储物理有序。数据按照层进行堆放，层次越往下，数据写入的时间就越早。每层内部按是否有序可划分为一个或多个sorted run。一个sorted run内部的数据必定有序（通常指物理上有序）。sorted run数据可进一步划分为不同的SSTable。当MemTable中的数据写满时，其会向L0进行落盘操作即Flush操作。如果LSM-Tree的某一层也达到容量阈值，就会向下合并，将同样的key的过期版本清除，即compaction操作

提供高吞吐、低延迟的数据摄入、流式订阅以及实时查询能力高性能更新：LSM 的 Minor Compaction，保障写入的性能和稳定性高性能合并：LSM 的有序合并效率非常高高性能查询：LSM 的 基本有序性，保障查询可以基于主键做文件的 Paimon 的 Partial-Update 合并引擎可以根据相同的主键实时合并多条流，形成 Paimon 的一张大宽表，依靠 LSM 的延迟 Compaction 机制，以较低的成本完成合并。合并后的表可以提供批读和流读：批读：在批读时，读时合并仍然可以完成 Projection Pushdown，提供高性能的查询。流读：下游可以看到完整的、合并后的数据，而不是部分列使用 Paimon 的 Changelog 生成功能，总是能够在流读时获取完全正确的变更日志。Append-only 表Append-only 表功能是一种性能改进，只接受 INSERT_ONLY 的数据以 Append 到存储，而不是更新或删除现有数据，适用于不需要更新的用例（如日志数据同步）。Bucket 扩缩容单个 Bucket 内是一个单独的 LSM 结构，Bucket 的数量会影响性能：过小的 Bucket 数量会导致写入作业有瓶颈，吞吐跟不上写入速度。过大的 Bucket 数量会导致有大量小文件，且影响查询速度。 SortRun 和 Universal-Compaction 策略snapshot expire 才会真正删除  sst  数据文件

manifest-list-4-delta变更

binlog reader增量

bucket-1hash_func(pk) % bucket_count

commiter operator

执行  DELETE  操作snapshot-3

snapshot

manifest-n

manifest-list-3-base基线

manifest-4-0

第二次 insert sql  执行后：snapshot-2的基线变为 snapshot-1的全量数据，snapshot-2的变更为在分区 n 的 bucket-0 内分别创建一个数据文件

bucket writer2 写入数据到 Paimon 表（3 缓存满  or checkpoint 进行 flush）

DEL

执行  COMPACT  操作snapshot-4

sst-001（pk0 - pk100 ）sorted

snapshot-1: {  \"version\

partition-0create_time=20230101

manifest

schema-0

manifest-list-3-delta变更

table: users

LSM

LSM-Tree的初衷是想通过空间放大和读放大来换取写放大的降低，从而达到极致的写性能，但也需要做好三方面因素的权衡。EDBT 2016的一篇论文首先提出RUM猜想（R为read，U为update，M为memory usage，RUM为三者缩写）。该论文认为，三者之间存在权衡关系，无法使得三个方面的性能都达到最优，因此必须在三者之间进行有效权衡。

func

checkpoint

ORC

提交后生成 snapshot

manifest-list-4-base基线

4 发送 committable 信息commit tablenewfile.orc

从查询角度进行分析。点查使用Bloom filter进行过滤，将其分成两类：1、读穿透，即查询数据不存在。2、假设知道每次发生假阳性的概率，如果判定结果为假阳性，则需要读一次磁盘。  - 在Leveling compaction策略中，每层只有一个sorted run，实现完全有序，因此每层只需要查询一次Bloom过滤器。根据二项分布期望公式，推导出的期望读盘次数为L×e的-m/n次方。  - 在Tiering compaction策略中，每层最多有T个sorted run，最多可能查询T次Bloom filter，在前述结构基础上乘以T的系数，根据推导出的期望读磁盘次数，其查询性能落后于Leveling compaction。长范围查询在归并前各版本数据大部分来自最后一层，因此上述两种策略的代价分别为返回block数的大小、返回block数的大小再乘以T，因此Leveling compaction比Tiering compaction的读性能更好。

Lastest-snapshot

commiter6 负责最终提交写入使数据可见

manifest-list-1-delta变更

flush

bucket-0hash_func(pk) % bucket_count

manifest-3-0

执行  INSERT  操作snapshot-2

span data-style=\

manifest-1-0

manifest-list-2-delta变更

compact manager异步触发 bucket 级别的小文件合并

partition-1create_time=20230102

snapshot-1

创建 快照-5 的时候执行快照过期，判断需要清理 快照-1 到 快照-4。过程如下：对于所有被标记删除的数据文件，执行物理删除，记录删除的数据文件对应的分区和 bucket删除该快照下的所有 changelog 和符合条件的 manifest 文件删除快照文件，并更新最早的快照（snapshot目录下的EARLIEST记录）

5 checkpoint

LSM tree

manifest-1sst PK 范围- sst+ sstpk min/max..字段统计信息

manifest-list-2-base基线

Earliest-snapshot

schema

sst-004（pk301 - pk400 ）sorted

先从写入操作复杂度进行分析  - 在leveling compaction策略中，第i层向第i+1层最多合并T次，在第j层合并到第i层时，其可被后续的数据项反复进行t-j次合并。  - 在Tiering compaction策略中，每条KV在第i层时只会被合并一次，因此从MemTable一直向下合并到最后一层即第L层，会得到平均写磁盘数即L/B，（B 是 block  大小，每层  sst  文件大小）span style=\

通过上述理论分析，可以得到如下结论：Tiering compaction的写放大低，compaction频率低，其缺陷为空间放大高、查询效率低，更利于update频繁的workload；Leveling compaction的写放大高，compaction操作更频繁，但空间放大低，查询效率高。尽管Tiering compaction和Leveling compaction的空间放大不同，但导致空间放大的主要原因相同，即受最下层的过期版本数据影响。越往下的层，做一次compaction的I/O代价越高，但发生的频率也更低，不同层之间做compaction的期望代价大致相同。点查、空间放大、长范围查询的性能瓶颈在LST-tree的最下层，而更新操作则更加均匀地分布在每一层。因此，减少非最后一层的compaction频率可以有效降低更新操作的代价，且对点查、空间放大、长范围查询的性能影响较小。

1

Compaction优化策略与分析Leveling compaction策略中，每层只有一个sorted run，sorted run内部的数据保持物理有序。具体实现上我们以RocksDB为例。一个sorted run可以由多个key不重叠且有序的SSTable files组成。当第L层满时，L层会选取部分数据即部分SSTable，与L+1层有重叠的SSTable进行合并，该合并操作即compaction操作。（会有写放大问题，频繁  compaction）Tiering compaction策略中，每层可以有至多T个sorted run，sorted run内部有序但每层不完全有序。当第L层满时，L层的T个sorted run会合并为L+1层的1个sorted run。因为每层允许有多个sorted run，因此SST文件间可能会存在数据范围的重叠，compaction操作的频率会更低，写性能也会更强。（会有读放大问题，读多个  sorted run）

manifest-list-1-base基线

paimon sink

sst-n...（pk401 - pkn.. ）sortedfooter---稀疏索引chunk min/max统计offset

source

bucket-3

partition-n...create_time=20230103