Paimon之LSM-Tree及其分层策略

斯坦SteinY

410人浏览 · 2026-04-20 11:47:03

斯坦SteinY · 2026-04-20 11:47:03 发布

LSM-Tree（Log-Structured Merge-Tree）是 Paimon 存储引擎的核心骨架。它通过牺牲部分读性能来换取极高的写吞吐量，并通过后台分层合并逐步将随机写转为顺序读。下面从原理到 Paimon 的具体实现，用一个完整实例带你走完数据从内存到落盘再到深层合并的全生命周期。

一、LSM-Tree 核心思想：为什么分层？

传统 B+ 树（如 MySQL InnoDB）的更新是原地修改：找到数据页 → 加载到内存 → 修改 → 刷回磁盘。这导致大量随机 IO。

LSM-Tree 的哲学是追加写（Append-Only）：

所有写入先进入内存排序结构（MemTable），顺序刷盘为不可变文件（Immutable File）
磁盘上的文件按**层级（Level）**组织，上层文件无序或弱序，下层文件严格有序且不重叠
后台异步合并（Compaction），像"沉淀"一样把数据从上层洗到下层

核心权衡：用空间放大（多版本共存）和读放大（可能查多层）换取写放大的降低。

二、Paimon 的分层架构定义

Paimon 的单个 Bucket 内，数据文件严格遵循层级编号：

层级	文件特征	Key 范围特征	合并触发条件
L0	MemTable Flush 结果	文件间无序，文件内有序	MemTable 满（默认 128MB）
L1	L0 合并产物	文件间可能重叠	L0 文件数达到阈值
L2+	深层合并产物	文件间严格不重叠，且全局有序	下层文件总大小达到阈值

关键配置参数（Flink SQL 中可设）：

'num-sorted-run.stop-trigger' = '5',        -- L0 文件数达到 5 触发 Minor Compaction
'num-sorted-run.compaction-trigger' = '5',  -- 同上（旧版参数）
'compaction.max.size.amplification' = '10',  -- 大小放大倍数限制
'full-compaction.delta-records' = '1000000', -- 触发 Full Compaction 的增量行数

三、具体实例：从空表到深层合并

假设我们创建一张用户余额表，主键为 user_id，单 Bucket（简化演示）：

CREATE TABLE user_balance (
    user_id STRING PRIMARY KEY NOT NULL,
    balance DECIMAL(18,2),
    update_time TIMESTAMP
) WITH (
    'bucket' = '1',
    'changelog-producer' = 'lookup',
    'num-sorted-run.stop-trigger' = '3'
);

Phase 1：初始写入（生成 L0）

操作：Flink 作业第一次 Checkpoint，写入 3 条记录。

user_id	balance	update_time
A	100.00	10:00:00
B	200.00	10:00:01
C	150.00	10:00:02

磁盘状态：

bucket-0/
└── data-0-0.orc  (L0, 3 rows)
    └── 内部有序: [A, B, C]

此时 L0 有 1 个文件。因为 num-sorted-run.stop-trigger=3，暂不触发 Compaction。

Phase 2：持续写入（L0 堆积）

操作：后续两个 Checkpoint 又写入两批数据（含更新）。

Batch 2（更新 B，新增 D）：

user_id	balance
B	250.00
D	300.00

Batch 3（更新 A，新增 E）：

user_id	balance
A	120.00
E	500.00

磁盘状态：

bucket-0/
├── data-0-0.orc  (L0)  [A, B, C]      -- Batch 1
├── data-0-1.orc  (L0)  [B, D]         -- Batch 2
└── data-0-2.orc  (L0)  [A, E]         -- Batch 3

问题分析：

L0 文件数 = 3，达到 stop-trigger 阈值
文件间无序：data-0-0 有 A，data-0-2 也有 A（更新）
读 A 时需要查 2 个文件（读放大）

触发 Minor Compaction！

Phase 3：Minor Compaction（L0 → L1）

合并逻辑：

读取所有 L0 文件（data-0-0, data-0-1, data-0-2）
按主键归并排序（Merge Sort）
同一主键保留 Sequence Number 最大的记录（最新值）
输出为 L1 文件

合并过程可视化：

输入 L0 文件:
  data-0-0: [A:100, B:200, C:150]
  data-0-1: [B:250, D:300]
  data-0-2: [A:120, E:500]

归并排序 + 去重（保留最新 Sequence Number）:
  A:120 (来自 data-0-2, seq=3)
  B:250 (来自 data-0-1, seq=2)  
  C:150 (来自 data-0-0, seq=1)
  D:300 (来自 data-0-1, seq=2)
  E:500 (来自 data-0-2, seq=3)

合并后磁盘状态：

bucket-0/
└── data-1-0.orc  (L1)  [A, B, C, D, E]  -- 全局有序，无重复 Key

L1 特征：文件内全局有序，但此时只有一个文件，所以"文件间不重叠"条件自然满足。

Phase 4：继续写入与新 L0 生成

操作：又经过 3 个 Checkpoint，写入新数据。

Batch 4: [F:400, G:600]
Batch 5: [C:180, H:700] – 更新 C
Batch 6: [A:130, I:800] – 再次更新 A

磁盘状态：

bucket-0/
├── data-1-0.orc  (L1)  [A, B, C, D, E]  -- 旧数据，Key 范围 [A~E]
├── data-0-3.orc  (L0)  [F, G]           -- Batch 4
├── data-0-4.orc  (L0)  [C, H]           -- Batch 5
└── data-0-5.orc  (L0)  [A, I]           -- Batch 6

此时 L0 又达到 3 个文件，再次触发 Minor Compaction。

Phase 5：带重叠范围的 Minor Compaction

这次合并的关键在于：L0 的 Key 范围与 L1 重叠。

L1 data-1-0 范围：[A, E]
L0 data-0-3 范围：[F, G] → 不重叠
L0 data-0-4 范围：[C, H] → 与 L1 重叠（C）
L0 data-0-5 范围：[A, I] → 与 L1 重叠（A）

Paimon 的合并策略：

对于不重叠的 L0 文件（如 data-0-3 [F, G]），直接提升为 L1 文件，避免无效读写
对于重叠的 L0 文件，必须与重叠的 L1 文件一起归并

合并过程：

参与合并的文件组:
  L1: [data-1-0: A, B, C, D, E]
  L0: [data-0-4: C, H]
  L0: [data-0-5: A, I]

归并排序 + 去重:
  A:130 (来自 data-0-5, 最新)
  B:250 (来自 data-1-0)
  C:180 (来自 data-0-4, 最新)
  D:300 (来自 data-1-0)
  E:500 (来自 data-1-0)
  H:700 (来自 data-0-4)
  I:800 (来自 data-0-5)

不参与的文件：

data-0-3 [F, G] 直接重命名为 L1：data-1-1.orc

合并后磁盘状态：

bucket-0/
├── data-1-0.orc  (L1)  [A, B, C, D, E, H, I]  -- 新合并
└── data-1-1.orc  (L1)  [F, G]                  -- 原封不动提升

注意：此时 L1 有两个文件，且范围不重叠：

data-1-0: [A ~ I]
data-1-1: [F ~ G]

等等，这里有个问题：[A~I] 和 [F~G] 是重叠的！实际上在真正的 Size-Tiered Compaction 中，如果 L1 文件大小相近且重叠，它们会继续参与 Major Compaction。让我修正这个例子，让边界更清晰。

修正后的合理状态：
假设 data-1-0 是 [A~E]，data-1-1 是 [F~G]，它们确实不重叠（E < F），符合 L1 的弱序要求。但如果 L1 文件过多且重叠严重，就会触发 Major Compaction。

Phase 6：Major Compaction（L1 → L2）

触发条件：

L1 文件总大小达到阈值（默认下一层大小的 10 倍）
或 L1 文件间重叠严重，读放大过高

假设 L1 又积累了多个文件：

L1:
  data-1-0: [A, C, E]  (大小 100MB)
  data-1-1: [B, D, F]  (大小 100MB)
  data-1-2: [G, H, I]  (大小 100MB)

问题：L1 文件间存在重叠（data-1-0 有 A,C,E；data-1-1 有 B,D,F，如果 Key 空间交叉则重叠）。为消除读放大，触发 Major Compaction 到 L2。

Major Compaction 过程：

选取部分或全部 L1 文件（通常选大小相近的一组）
多路归并排序
输出为严格不重叠的 L2 文件，每个文件大小固定（如 128MB）

输入 L1:
  data-1-0: [A, C, E]
  data-1-1: [B, D, F]
  data-1-2: [G, H, I]

归并后按 128MB 切分:
  data-2-0: [A, B, C]  (128MB)
  data-2-1: [D, E, F]  (128MB)
  data-2-2: [G, H, I]  (128MB)

合并后状态：

bucket-0/
├── data-2-0.orc  (L2)  [A, B, C]
├── data-2-1.orc  (L2)  [D, E, F]
└── data-2-2.orc  (L2)  [G, H, I]

L2 特征：

文件间 Key 范围严格不重叠
全局有序
查询时通过二分查找定位文件，再查文件内 Bloom Filter，最多访问 1 个文件

四、读路径：如何查找数据？

以查询 user_id = 'C' 为例，展示不同层级的读放大差异：

阶段	磁盘状态	需要检查的文件	读放大
Phase 2	3 个 L0 文件	data-0-0, data-0-1, data-0-2	3 次
Phase 3	1 个 L1 文件	data-1-0	1 次
Phase 5	2 个 L1 文件（有重叠）	可能 2 个	2 次
Phase 6	3 个 L2 文件	通过二分定位到 data-2-0	1 次

Paimon 的读优化：

Manifest 统计信息：先查 Manifest File，知道每个文件的 Min/Max Key，直接跳过不相关文件
Bloom Filter：文件内对主键建 Bloom Filter，阴性结果直接排除
Partition & Bucket 裁剪：先定位到具体 Bucket，减少搜索空间

五、Compaction 策略详解

Paimon 支持三种 Compaction 模式，对应不同的业务场景：

1. Minor Compaction（默认）

范围：L0 → L1，或部分 L1 内部整理
特点：轻量、快速、不阻塞写入
适用：实时写入场景，平衡写放大与读放大
配置：num-sorted-run.stop-trigger

2. Major Compaction

范围：L1 → L2，或深层合并
特点：重 IO，彻底消除重叠，生成严格有序文件
适用：批量加载后、或读多写少场景
效果：最大程度降低读放大

3. Full Compaction（全量合并）

范围：所有层级 → 重新输出为单层有序文件
触发：full-compaction.delta-records 达到阈值，或手动触发 CALL sys.compact(...)
特点：
- 生成完全有序的单层结构，读放大 = 1
- 清理所有历史版本，空间放大最小
- 代价极高，会暂时消耗大量磁盘 IO
适用：
- 离线数仓批量导入后
- 需要生成 Changelog 的 lookup 模式（减少 State 查找）
- 准备做重大 Schema 变更前

六、Paimon 的特殊设计：Changelog 与 Compaction 的关系

在 changelog-producer = lookup 模式下，Compaction 不仅是存储整理，还直接影响流读的正确性：

写入新数据 (A:130)
    │
    ▼
查询 LSM 旧值 (A:100)  ← 需要从 L0/L1/L2 查找，产生点查开销
    │
    ▼
生成 Changelog: -U (A:100), +U (A:130)
    │
    ▼
写入 Changelog 文件

优化：如果刚刚做过 Full Compaction，L2 文件完全有序且带 Hash Index，lookup 点查性能最高，Changelog 生成延迟最低。

七、实例总结：数据生命周期全景图

时间线 ───────────────────────────────────────►

Checkpoint 1: 写入 [A,B,C] 
              └── MemTable Flush → L0: data-0-0

Checkpoint 2: 写入 [B,D]
              └── L0: data-0-1

Checkpoint 3: 写入 [A,E]  
              └── L0: data-0-2
              └── 触发 Minor Compaction
              └── L1: data-1-0 [A,B,C,D,E]

Checkpoint 4-6: 继续写入，L0 堆积到 3 个文件
              └── 触发 Minor Compaction
              └── 部分提升 L1，部分与旧 L1 合并

凌晨低峰期: 触发 Full Compaction
              └── L1/L2 全部归并
              └── 输出严格有序的 L2 文件
              └── 清理旧版本，释放空间

八、与 B+ 树的本质对比

维度	B+ 树 (InnoDB)	LSM-Tree (Paimon)
写入模式	原地更新，随机 IO	追加写，顺序 IO
更新成本	高（寻址+修改）	低（追加新版本）
读取成本	低（树高 3-4 层）	高（需查多层，靠合并缓解）
空间放大	低	高（多版本共存）
适合场景	OLTP，点查多	流式写入，批量分析
并发控制	页级锁/Latch	文件级不可变 + MVCC

对你工作的启示：你在处理门店基础信息和运费模板时，如果表是主键表且更新频繁（如运费规则变更），Paimon 的 LSM 结构会自然将更新转为追加写。但需注意：

L0 堆积过多会导致流读延迟增加（读放大），建议根据 Checkpoint 间隔调整 num-sorted-run.stop-trigger
Full Compaction 适合在凌晨低峰期调度，清理运费模板的历史版本，降低存储成本
如果下游需要强一致的 Changelog，确保 Compaction 策略与 changelog-producer 模式匹配

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

【LeetCode 134】加油站：图解指针跳跃与 O(N) 极简贪心，避开 Python 隐藏坑！

AtomGit开源社区

Agent Harness 综述：同一个模型，为什么做出来的 Agent 差这么远

AtomGit开源社区

企业内部AI Agent的权限管理与数据隔离

术语简明定义企业内部AI Agent部署在企业内部、用于处理内部业务的大模型驱动智能体，具备自主调用工具、访问数据、记忆上下文的能力Agent身份标识每个Agent唯一的数字身份，包含所属域、创建者、权限范围、能力边界等属性，是权限管控的核心主体动态权限引擎基于ABAC（属性-based访问控制）的实时权限决策系统，可根据Agent属性、数据属性、环境、上下文动态判断访问权限上下文隔离每个Agen