从 LSM-Tree 到列表引擎:分布式 KV 存储内核、读写放大与「轻索引 + mGet 回表」模式实战

分布式存储KVKey-ListLSM-TreeRocksDB存储架构工程化

从 LSM-Tree 到列表引擎:分布式 KV 存储内核、读写放大与「轻索引 + mGet 回表」模式实战

TL;DR 在第 1 篇总纲中,我们完成了架构的「第一刀」:轻重分离。把几十 KB 的风控决策大报文剥离出关系型主表,送入底层基于 LSM-Tree 的分布式 KV,单笔点查稳定在 0.1~0.3ms;同时留下了悬念:既然底层引擎吞吐如此惊人,能不能直接用 KV 或定制的 Key-List 列表引擎来承载千万级台账?

答案是:KV 的 Value 是纯粹的黑盒字节流,天然缺少二级索引;而白盒 Key-List 虽支持服务端下推过滤,但其物理分片强依赖外层分片键(Sharding Key)。

本篇把分布式 KV 和 Key-List 拆开讲透:

  • 拆清 LSM-Tree 的核心四构件(WAL、MemTable、SSTable、Compaction)与不可兼得的 RUM 放大三角;
  • 讲透为什么点查能做到亚毫秒(Bloom Filter + Block Index + Block Cache 三级跳),而范围扫描却代价沉重;
  • 剖析为什么 KV 没有 SQL 里的 LIMIT offset, limit,只能走 Iterator.Seek() + 游标 Skip;
  • 还原「Key-List 轻索引筛出 ID + mGet 批量回表拿详情」的黄金搭档架构;
  • 回到业务场景闭环:为什么风控决策大报文完美契合 KV,而多条件台账列表绝对不能用 KV 强扭。

📚 《千万级业务存储架构与实战》系列


📌 本文要点

  • B+ 树以写换读,LSM-Tree 以读换写:LSM-Tree 通过顺序写 WAL 和内存 MemTable 换取极致的写入吞吐,但多层不可变 SSTable 让读取必须在多路归并和磁盘层级间穿梭。
  • RUM 放大三角不可调和:写放大(Write Amplification)、读放大(Read Amplification)与空间放大(Space Amplification)之间只能权衡,Leveled Compaction 牺牲写吞吐换取读与空间,Size-Tiered 优先保障写吞吐但放大读与空间。
  • KV 存储根本没有廉价的 offset:存储引擎底层暴露的是迭代器(Iterator)语义。跳过 N 行要么通过业务游标 Seek(cursor) 直达,要么从当前位置线性调用 N 次 Next(),越往后跳耗时越长,这与第 2 篇拆解的 MySQL 索引扫描本质完全相同。
  • 点查亚毫秒的秘密:单行 Get 能够在毫秒甚至亚毫秒级返回,靠的是 MemTable 命中、Block Cache 缓存、Bloom Filter 单次计算快速否定绝大多数 SSTable,以及 Block Index 二分定位三道防线。
  • 「轻索引 + mGet 回表」的边界:将排序与过滤所需的轻量字段塞入有序列表,筛选出业务 ID 后并发 mGet 回大 KV 取详情,这是 C 端长列表的性能利器;但它成立的前提是「查询必带主键锚点(如 userId)」,一旦失去锚点做全网全局检索,系统就会退化为全分片广播与超级热点 Key。

一、LSM-Tree 到底长什么样:核心四构件与读写路径

在工业级分布式 KV(例如基于 RocksDB 封装的存储服务)中,存储引擎的核心数据结构绝大多数采用 LSM-Tree(Log-Structured Merge-tree)。

与 MySQL InnoDB 的 B+ 树就地更新(In-place Update,每次修改都要随机 IO 刷盘修改对应的数据页)不同,LSM-Tree 采用的是**异地追加写(Append-only)**思想。

[Client Put/Delete]
         │
         ├───► 1. 顺序追加写 WAL (Write-Ahead Log, 保证崩溃不丢数据)
         │
         └───► 2. 写入内存 MemTable (跳表 SkipList, 内存中有序)
                     │
               (达到大小阈值,转为不可变 Immutable MemTable)
                     │
                     ▼
         ────── 3. 内存异步刷盘 (Flush) ──────
                     │
                     ▼
             Level 0 SSTable (文件内部有序,但文件之间 Key 区间重叠)
                     │
               Compaction 合并下沉
                     │
                     ▼
             Level 1 SSTable (同层内各文件 Key 区间严格互斥、全局有序)
                     │
               Compaction 合并下沉
                     │
                     ▼
             Level 2..N SSTable (容量逐层放大 10 倍)

1. 核心四构件职责

构件物理载体组织形式与职责
WAL (Write-Ahead Log)磁盘文件磁盘预写日志,只追加不就地改,顺序写入性能极高。机器断电或进程崩溃时重放它恢复内存状态。
MemTable内存读写内存缓冲区,底层通常是跳表(SkipList)。所有写入、更新和逻辑删除先落在此处,保持 Key 有序。
SSTable (Sorted String Table)磁盘文件磁盘上的只读静态文件,按数据块(Data Block)紧凑切分,包含数据块、Filter Block(布隆过滤器)和 Index Block(块索引)。文件一旦生成绝不修改。
Compaction (压实合并)后台线程异步合并多个 SSTable,清除过期版本和已被标记删除(Tombstone 墓碑)的数据,并重新排序下沉到下一层级。

2. 写入与更新路径

  1. 写入:一条写请求到达节点后,并发写 WAL 与 MemTable。WAL 顺序落盘后即可向客户端返回成功,耗时通常在微秒级别。
  2. 删除与更新:LSM-Tree 没有物理上的「就地修改」或「原地删除」。
    • 更新操作:直接追加写入一条相同 Key 但版本号(Sequence Number)更大的新记录。
    • 删除操作:写入一条该 Key 的墓碑记录(Tombstone)。
  3. Flush:当 MemTable 达到配置阈值(如 64MB),它会被冻结为只读的 Immutable MemTable,同时开辟新的 MemTable 承接写入。后台线程将 Immutable MemTable 顺序刷盘,生成 Level 0 的 SSTable 文件。

二、LSM 的代价:不可调和的 RUM 放大三角

LSM-Tree 用极致的写入性能征服了大数据领域,但分布式系统没有免费的午餐。数据库理论中的 RUM 假说(Read-Update-Memory Conjecture) 指出:写放大、读放大、空间放大三者不可能同时最优,优化其中两个必然恶化第三个。

                  写放大 (WA)
                 /          \
                /            \
               /   RUM 权衡   \
              /                \
      读放大 (RA) ───────────── 空间放大 (SA)
放大指标定义与成因恶化后的后果
写放大 (Write Amplification, WA)实际写入磁盘的物理字节数 / 业务实际写入的数据量。源于 Compaction 时一个 SSTable 会被多次读取、归并重写到下一层。固态硬盘(SSD)磨损加速、磁盘写带宽被后台吞噬,引发前台写停顿(Write Stall)。
读放大 (Read Amplification, RA)业务查询 1 个 Key 时实际读取磁盘的数据量与次数。源于一个 Key 可能存在于 MemTable 以及不同 Level 的多个 SSTable 中,必须逐层比对。磁盘 IOPS 被打满,点查与范围扫描延迟大幅上升。
空间放大 (Space Amplification, SA)磁盘实际占用的总空间 / 业务有效数据真实体积。源于旧版本数据、未被清理的删除墓碑,以及 Compaction 过程中的临时备份副本。磁盘容量利用率低,存储成本大幅飙升。

两大主流 Compaction 策略的取舍

RocksDB 等底层存储引擎提供了两种核心合并策略:

  1. Leveled Compaction(分层合并,默认首选):
    • 每一层的容量上限是上一层的 10 倍(Level 1 往往为 10MB,Level 2 为 100MB……)。
    • 除 Level 0 之外,每一层内的所有 SSTable 文件 Key 区间严格互斥。
    • 特点:点查时在每一个非 L0 层最多只需要检查一个 SSTable 文件,读放大和空间放大得到严格控制(空间放大通常 < 1.33);但代价是写放大极高(典型场景在 10~30 倍),写入频繁时后台 Compaction 吞吐极重。
  2. Size-Tiered / Universal Compaction(分级/按大小合并):
    • 当某层积累了若干个大小相近的 SSTable 时,一次性顺序归并成一个更大的 SSTable。
    • 特点:写放大非常低,写入吞吐极大;但由于同层文件的 Key 互相重叠,读放大和空间放大非常严重(合并时可能需要预留与待合并文件等量的空闲磁盘,空间放大常超 200%)。

💡 写停顿(Write Stall)警惕:当外部批量写入吞吐过猛、后台刷盘和 Compaction 线程追赶不上时,存储引擎会主动踩刹车(强制延缓或挂起写请求),防止未合并的 SSTable 堆积到失控。上一篇总纲提到「夜间 T-1 批量同步大报文必须做 QPS 限速」,根源就在于此。


三、为什么点查能做到亚毫秒:三道防线

既然磁盘上有层层重叠的 SSTable 文件,为什么按主键点查(Get(Key))依然能稳在 0.1~0.3ms 的亚毫秒级?

答案在于存储引擎在内存和磁盘块布局上构建的三道防线:

Get(Key)
   │
   ├──► 1. 查活跃 MemTable & Immutable MemTable (内存跳表,O(log N)) ──[命中]──► 返回
   │
   ├──► 2. 查 Block Cache (内存 LRU,缓存热点解压后的 Data Block) ──[命中]──► 返回
   │
   └──► 3. 逐层排查 SSTable 文件
             │
             ├──► Filter Block (布隆过滤器 Bloom Filter, 内存中位图)
             │      │
             │      └───[判定不存在] ──► 跳过整个 SSTable 文件!(0 次磁盘 IO)
             │
             ├──► Index Block (两级索引块,折半查找定位目标 Data Block)
             │
             └──► 读取目标 Data Block (仅读 4KB 磁盘块并载入缓存)

1. 布隆过滤器(Bloom Filter):快速否定 99% 的无效文件

布隆过滤器用很小的内存代价,为「判断某个 Key 是否在某集合内」提供确定性的否定回答:如果它说不存在,那就 100% 绝对不存在;如果它说存在,有极低概率发生误判(False Positive)。

在 RocksDB 中,通常为每个 Key 分配 10 个 bit 的内存空间(bits_per_key = 10),此时布隆过滤器的误判率约为 1%。这意味着在点查未命中的层级时,99% 的 SSTable 文件在读内存位图后被直接略过,根本不需要发生物理磁盘 IO。

2. Block Index 与两级索引块

SSTable 内部被切分为固定大小的 Data Block(通常为 4KB)。Index Block 记录了每个 Data Block 中最大的 Key 及其在文件中的偏移量。引擎通过在 Index Block 上二分查找,直接锁定唯一的 4KB 目标数据块。

3. Block Cache:热点内存缓冲

未命中的磁盘块在读取后被放入内存的 Block Cache(支持分片 LRU 或 CLOCK 算法)。高频访问的业务单号或者元数据索引常驻内存,免除了二次系统调用。


四、为什么 KV 根本没有廉价的 offset:迭代器底层语义

在做 API 设计或数据模型迁移时,有些开发者会习惯性地问:“KV 引擎能不能支持类似 MySQL 的 LIMIT offset, limit 分页查询?”

答案是:KV 存储在协议和引擎层面都不存在廉价跳过 offset 的能力。

1. 底层暴露的是 Iterator(迭代器)模型

关系型数据库给人一种“跳过前 10000 行很简单”的错觉,但上一篇我们讲清楚了:即便是 MySQL,InnoDB 也必须先在内存或索引上线性扫过前 10000 条记录。

而在分布式有序 KV 引擎(如 RocksDB、TiKV)中,底层暴露的标准接口是迭代器模型:

// 真实的底层有序 KV 迭代器操作语义
try (RocksIterator iterator = db.newIterator()) {
    // 1. Seek: 二分定位到起始 Key(或大于等于该 Key 的最近位置)
    iterator.seek(startKeyBytes);

    // 2. 线性向后移动
    while (iterator.isValid() && count < limit) {
        byte[] key = iterator.key();
        byte[] value = iterator.value();
        
        // 业务处理...
        iterator.next(); // 推动底层多路归并指针移动
        count++;
    }
}

2. 如果强行在 KV 上实现 offset 分页会发生什么?

假设一个接口硬要在 KV 上拉取第 5000 页(每页 20 条,即 offset = 100000, limit = 20):

  • 客户端执行 Seek(prefix) 定位到前缀起始位置。
  • 为了跳过 100000 条数据,存储引擎内部必须调用 100000 次 iterator.next()!
  • 每次 next(),底层都要在一个优先队列(Priority Queue / Min-Heap)中重新归并 MemTable、Level 0 和其他各个 Level 的 SSTable 当前项。
  • 10 万次内存比较与块载入开销,会让单次分页请求耗时从 0.5ms 直接恶化到数秒,并发一高瞬间耗尽存储节点 CPU。

3. 正确的做法:基于业务游标(Cursor-based Pagination)

在有序 KV 上做长列表拉取,唯一合理的方案是游标分页(Seek-by-Key),绝不传 offset:

第一页:
  Seek("user:10086#20261118_235959")
  往后 Scan 20 条记录
  拿到第 20 条的 Key: "user:10086#20261118_210000" 作为下一页的 cursor

第二页:
  直接 Seek("user:10086#20261118_210000")
  向后跳过 1 条(或利用开区间语义),直接读接下来 20 条

无论拉取第 1 页还是第 10000 页,耗时完全一致(均为一次 Seek 亚毫秒开销 + 20 次顺序 next)。


五、白盒 Key-List 列表引擎:数据布局与「索引回表」模式

既然知道了 KV 原生是键值黑盒,那大厂内部常用来抗亿级 C 端长列表的 Key-List 列表引擎,底层到底是怎么做出来的?

1. 黑盒 KV 与白盒 Key-List 的结构差异

【标准分布式 KV:黑盒模型】
Key:   "loan:iou:202611180001"
Value: 0x1F8B0800... (一坨由业务自行序列化、Gzip 压缩后的二进制字节流,存储引擎完全不可见)

【分布式 Key-List:白盒强 Schema 模型】
Outer Key (分片键): "user:10086"
Item List (有序列表):
  ├─ Item 1: [Score/SubKey: 1731920000000] -> { iouId: "IOU-01", status: 1, rate: 0.12 }
  ├─ Item 2: [Score/SubKey: 1731910000000] -> { iouId: "IOU-02", status: 2, rate: 0.15 }
  └─ Item 3: [Score/SubKey: 1731900000000] -> { iouId: "IOU-03", status: 1, rate: 0.18 }

Key-List 在物理存储上通常以 KV 引擎为底层底座,通过编码规则把一个逻辑上的「外层主 Key + 子列表」打平成有序的底层 KV:

底层物理 Key 编码 = [OuterKeyPrefix] + [分片键 Hash] + [Score/排序权重] + [内部唯一自增序列]

因为定义了强 Schema,存储引擎节点可以在本地直接运行过滤算子(例如只挑出 status == 1 的 Item),甚至实现正序/逆序 Scan,完全免除了将几千条全量列表拉回 Java 应用层过滤的网络开销。

2. 「轻索引 + mGet 回表」设计模式

在海量数据且单条记录详情较大的场景下,业界最经典的黄金组合是:Key-List 存轻量索引 + 分布式 KV 存全量大报文。

[前端请求:查询用户 10086 的还款计划列表]
                │
                ▼
      ┌──────────────────┐
      │  业务网关/服务层   │
      └─────────┬────────┘
                │
   第一步: 带着 userId = 10086 访问 Key-List 列表引擎
   (外层 Key 精准路由到单存储节点,只拉取轻索引字段)
                │
                ▼
      ┌──────────────────────────────────┐
      │  Key-List 列表引擎 (白盒)         │
      │  按时间逆序 Scan 筛选出 20 个:    │
      │  [iouId, status, createTime]     │
      └─────────┬────────────────────────┘
                │
                │ 拿到当前页的 20 个全局唯一单号 iouId
                ▼
   第二步: 拿着 20 个单号,向底层分布式 KV 发起并发 mGet
   (多分片并行拉取每笔 10KB~50KB 的完整决策/账务报文)
                │
                ▼
      ┌──────────────────────────────────┐
      │  分布式 KV 存储 (黑盒)             │
      │  mGet(iouId_1, iouId_2, ...)     │
      │  纯主键点查,0.2ms 批量返回       │
      └─────────┬────────────────────────┘
                │
                ▼
          组装最终响应给前端

这一模式的精髓在于:

  1. 轻重彻底隔离:Key-List 的单个 Item 只有几十个字节,一个用户名下即便挂载 10000 条历史记录,总数据量也不过几百 KB,扫描与内存加载极其轻量;
  2. 读写分离与零冗余:全量详情大报文(几十 KB)只在 KV 中存放一份,只承担精准 Get,绝不参与多条件索引与扫描;
  3. 回表批量化:先在轻量列表节点过滤出当页最终需要的 10~20 个 ID,再通过 mGet 批量回表取数,消灭无效回表。

六、为什么这个模式在「无锚点全局台账」上直接失效

学习了上面的「轻索引 + mGet 回表」模式,有人可能会灵机一动: “既然 Key-List 这么快,那我能不能在列表里存 status:OVERDUE 做 Key,把所有逾期的借据全挂在这个 Key 下面,用来做逾期台账查询?”

这在生产环境中是一剂致命毒药。

在第 1 篇总纲中,我们反复强调过**无锚点全局检索(No Sharding Key)**这个概念。我们对比一下为什么「用户个人列表」行得通,而「全局业务台账」必然翻车:

对比维度用户个人订单/房产列表全局信贷台账多条件检索
查询模式必传且只传 userId = 10086条件全部可选:运营经常只选「状态 = 逾期 AND 定价 >= 18%」,不传用户 ID
主 Key 粒度单个用户,天然分布在海量离散哈希桶中若以 status 作为主 Key,全国逾期单全部集中在 status:OVERDUE 一个 Key 下
单 Key 数据规模单用户一般几十到几千条(有界长列表)单个状态可能对应 数百万甚至数千万条 记录(巨型大 Key)
存储节点结局读写极度均匀,并发吞吐线性扩展产生单机超级热点(Hotspot),单个存储节点网卡与 CPU 被打穿,集群倾斜崩溃
多条件组合能力只要 userId 固定,单机本地扫描几十毫秒搞定无法支持「金额区间 + 定价区间 + 资方 + 期限」多个宽条件的自由动态组合过滤

这就是为什么我们在总纲中坚定地下了结论:Key-List 适合做带主 ID 锚点的 C 端长列表,而绝对承载不了无分表键、自由筛选的千万级 B 端全局管理台账。


七、闭环:回到风控台账场景的存储落子

把底层原理全部穿透之后,再看我们真实生产系统的架构组合拳,脉络就变得无比清晰:

                    【风控信贷台账业务体系】
                               │
            ┌──────────────────┴──────────────────┐
            ▼                                     ▼
   【轻量结构化列表层】                     【大报文详情层】
   (300 字节/行,千万级)                   (20~60 KB/行,全量数 TB)
            │                                     │
   多条件自由组合筛选/分页                  单号精准单笔点查
            │                                     │
   首期:单机 MySQL 宽覆盖索引              底层:基于 RocksDB 的分布式 KV
   (7ms 列表取数,承受 1~2 QPS 内部并发)   (亚毫秒点查,无缓存双写不一致)
            │                                     │
   远期规划 (数据超 5000 万或并发破千):              │
   平滑演进到 TiDB 全局索引 / ES 位图                 │
            │                                     │
            └───────────────┬─────────────────────┘
                            │
               点击「详情」时,由应用层拿单号
               点查分布式 KV 拼装展示大报文
  1. 风控决策大报文(几十 KB)落入分布式 KV:
    • 充分利用 LSM-Tree 的 WAL 顺序写与高吞吐;
    • 依赖布隆过滤器、Block Index 与 Block Cache 实现亚毫秒单笔点查;
    • 单对象设置 2 年 TTL,过期自动在 Compaction 过程中物理清除,免去繁重的数据清理脚本。
  2. 多条件列表层坚决不强扭 KV:
    • 不搞伪倒排、不造巨型 Key;
    • 在 20 人低并发后台阶段,用单机 MySQL 宽覆盖索引彻底消灭回表与 filesort,把取数耗时死死压在 7ms;
    • 严格在离线同步时执行「先写大报文 KV、后写列表表」,保障数据全局时序一致。

八、什么时候该上 KV、什么时候坚决别上

适用场景

  • 纯主键点查(Key-Value Get/Put):单条数据在 256KB 以内,并发 QPS 达到数万至数百万,追求 1ms 以内极低读写延迟。
  • 高吞吐写入与日志/时序暂存:写入压力极大,MySQL 已经频繁发生锁争用或刷盘瓶颈。
  • 带固定主 ID 的轻量长列表(Key-List):主 Key 离散分布(如 userId、deviceId),单 Key 下挂载有序的轻量数据项,需要服务端下推排序与游标 Scan。

禁用红线

  • 多条件无锚点全局查询:筛选条件动态组合、不带主键前缀,需要任意翻页与精确总数统计。
  • 需要大跨度随机 offset 跳页:业务强依赖 LIMIT 100000, 20 这种深分页交互。
  • 频繁全量 Scan 整库数据:LSM-Tree 的全局 Scan 会遍历所有层级的 SSTable,极其昂贵,极易冲垮内存 Block Cache 并导致线上点查抖动。

✅ Checklist:分布式 KV 与列表引擎选型落地核对表

  • 数据是不是纯主键访问? 如果需要按非主键字段进行多维组合过滤,KV 本身无法直接承载,需评估 ES 或分布式关系型数据库。
  • 是否已规避巨型大 Key(Big Key)? 单个 Key 下挂载的数据量严格控制在 MB 级以内,杜绝向单一状态 Key(如 status:1)无限追加列表项。
  • 分页是不是基于游标(Cursor)而非 offset? 列表拉取必须采用 Seek(cursor) 语义,前端交互配合下拉加载或仅支持上一页/下一页。
  • 单条 Value 体积是否在最佳区间? KV 最佳承载体积为几百字节至 256KB;大于数 MB 的大对象应移步对象存储(OSS),防止 Compaction 写放大拖垮磁盘。
  • 离线批量写入是否配置了限速? 批量同步或数据重放必须限制写入 QPS,防止触发存储节点的 Write Stall 导致线上读写抖动。
  • 轻重分离的时序是否保证? 先写入底层 KV 大报文,再写入上层索引或列表表,杜绝“列表能查到、点详情 404”的数据不一致。

写在最后

存储引擎的底层设计,永远是在硬件物理边界(磁盘顺序写 vs 随机写、内存带宽、CPU 缓存)与业务访问模式之间的精巧平衡。

搞懂了 LSM-Tree 的写放大与点查三防线,看透了迭代器为什么天生没有 offset,你就能在面对海量高并发数据流时保持清醒:既不盲信任何组件的“吞吐神话”,也不在不适用的场景里做徒劳的架构挣扎。

下一篇,我们将直面单机 MySQL 也无法承受的物理极限:当数据量突破数千万甚至数亿、并发翻页突破数千 QPS 时,TiDB 是如何用分布式 Region 切分彻底实现无分表键全局索引的?Elasticsearch 又凭什么靠 Roaring Bitmap 压缩位图在 CPU 指令级实现毫秒级多条件求交?


系列目录

  1. 第 1 篇 · 存储架构全景与选型边界推演(总纲)
  2. 第 2 篇 · 单机 MySQL 千万级台账任意翻页实战
  3. 第 3 篇 · 从 LSM-Tree 到列表引擎:分布式 KV 存储内核、读写放大与「轻索引 + mGet 回表」模式实战(本篇)
  4. 第 4 篇 · 突破单机极限:TiDB 全局索引与 ES 位图检索实战(待更)

👉 开源: Solo Workspace (独立开发者 CLI)· solo-spring-scaffold (Spring Boot 脚手架)

👉 其它平台: 知乎 · 掘金

👉 联系: [email protected] (合作 / 线上问题交流欢迎来信)