跳转到内容
Jason's Study

SILT — 0.7 字节内存索引一条记录的 flash 键值存储

是什么

SILT（Small Index Large Table）是一套把键值数据放在 SSD 上、但只用极少内存做索引的系统。日常类比：图书馆有 100 万本书放在书架（SSD），但前台只用一张 A4 纸（内存）就能告诉你”这本书在第 4 排第 17 格”——纸虽小但精准。

SILT 给每条记录平均只花 0.7 字节内存（同期 LevelDB 要 4-12 字节，BerkeleyDB 几十字节），同时保证一次 GET 命中只读 1 次 SSD。它不是一种数据结构，而是三层流水线：新数据先进”快但费内存”的层，慢慢被搬到”慢但极省内存”的层。

读写路径都用代码自动选层，开发者用起来就是普通 KV 接口。

为什么重要

不理解 SILT，下面这些事都没法解释：

  • 为什么 SSD 时代 KV 系统的瓶颈从”磁盘 I/O”变成”内存索引”——SSD 快到内存索引成为新瓶颈
  • 为什么 RocksDB / LevelDB 走 LSM 路线、SILT 不走——LSM 每层都排序，SILT 只让最后一层排序
  • 为什么”省内存”和”少 SSD 读”看起来矛盾，SILT 却同时做到——靠分层 + Bloom filter
  • 为什么 0.7 字节几乎是信息论下限——一条记录至少要”指针告诉它在 SSD 哪里”，紧凑哈希 + trie 把这部分压到极限

核心要点

SILT 的设计可以拆成 三步：

  1. 写入先进 LogStore：append-only 写盘 + 内存哈希索引。每条占 6.5 字节内存，多但写入快。类比：刚收的快递先扔门口箱子，方便随时拿。

  2. 冷却进 HashStore：LogStore 满了 → 后台进程把它转成只读的 HashStore，内存降到 2.2 字节/条，用紧凑哈希。类比：箱子满了搬进抽屉，按字母分格。

  3. 归档进 SortedStore：多个 HashStore 合并、排序、压缩成最终层，内存降到 0.4 字节/条，用一种叫 trie 编码的索引。类比：抽屉满了装订成书，目录页极薄。

整体每条平均 ≈ 0.7 字节。GET 时按层查（命中即返），写时永远进 LogStore，后台 merger 不断推数据下移。

实践案例

案例 1：一次 GET 在三层里怎么走

假设 key = user:42：

1. 查 LogStore 内存哈希 → 命中？返回 SSD 偏移 → 1 次 flash 读
2. 没命中 → 查每个 HashStore 的 Bloom filter → 命中？读对应 SSD 槽
3. 还没命中 → 查 SortedStore 的 trie 索引 → 必命中（数据存在的话）

关键：每层都有过滤器，绝大多数 GET 只触发 1 次 SSD 读。Bloom filter 假阳率 ~0.001，三层叠加后 99.9% 的查询不会多读。

读路径的代码骨架近似：

def get(key):
    if v := log_store.lookup(key): return v       # 内存哈希
    for hs in hash_stores:
        if hs.bloom.probably_contains(key):
            if v := hs.lookup(key): return v       # 一次 SSD 读
    return sorted_store.lookup(key)                # trie 解码 + SSD 读

案例 2：trie 编码索引为什么能压到 0.4 字节

SortedStore 的 key 是排好序的，比如 [apple, art, banana, ...]。SILT 不存完整指针，存”每个 key 比上一个多了多少字节”——叫 熵编码 trie：

apple    → 存 5 字节
art      → 公共前缀 "a"，新增 "rt"，存 (1, 2)
banana   → 公共前缀 "" ，新增 "banana"，存 (0, 6)

平均每条只花几个 bit 表示位置，加上少量校验位 ≈ 0.4 字节/条。代价：只读——任何插入都要重建整层。

案例 3：写入 → 后台合并的完整生命周期

t=0   PUT(user:42, value)
      → 写 LogStore SSD，内存哈希 +1 条
t=10s LogStore 满 256MB
      → 后台启 Convert：扫一遍变成 HashStore（紧凑哈希）
t=60s 累计 5 个 HashStore
      → 启 Merge：5 个 HashStore + 当前 SortedStore 排序合并 → 新 SortedStore

写入永远是 append，O(1)；合并在后台分摊。读路径无锁——SortedStore 是只读的。

PUT 同 key 多次，三层可能各留一份；查询按 LogStore → HashStore → SortedStore 的顺序，前者优先，所以读到的总是最新版本。旧版本在下次 SortedStore 重建时被丢弃。

踩过的坑

  1. SortedStore 用 trie 索引，只读：任何更新都要重建整层。所以 SILT 让新写全走 LogStore，等批量再合并下来——绝不能在 SortedStore 上原地改。

  2. 后台 merger 跑得慢内存就膨胀：LogStore 每条 6.5 字节，如果 workload 突增、merger 跟不上，内存可能涨到几 GB。生产上需要给写入限流或加速合并。

  3. 三层都要查 → 必须 Bloom filter 过滤：否则一次 GET 变 3 次 SSD 读，把”省 I/O”的优势抹掉。Bloom 假阳率要调到 0.001 以下。

  4. value 必须定长或带头部长度：SortedStore 的紧凑布局假设能按偏移精确切片，变长 value 不带长度就解析不出来。论文用 1KB 定长 value 跑 benchmark，工程实现要自己加长度前缀。

  5. 删除是 tombstone：SILT 不在原地擦数据，DELETE 写一条墓碑标记到 LogStore，等下次合并时真正清掉。短时间反复 PUT/DELETE 同 key 会让三层都堆墓碑，浪费空间。

适用 vs 不适用场景

适用：

  • flash/SSD 上的只读重 + 写入相对均匀的 KV 工作负载（缓存、用户档案、特征服务）
  • 内存预算紧但数据量大的场景（10 亿条记录只想花 700MB 内存做索引）
  • 对单条 GET 延迟敏感、能接受范围扫描慢的应用

不适用：

  • 需要范围扫描或 secondary index → SortedStore 排序但不暴露范围 API，要用 LSM
  • 写入极不均衡（突发峰值 10×）→ merger 跟不上，LogStore 内存爆
  • 频繁更新同一 key → 三层都会留旧版本，合并代价高
  • 通用持久化数据库 → SILT 是嵌入式 KV，不带事务、不带复制

历史小故事（可跳过）

  • 2008-2009：CMU 的 FAWN 项目（Andersen et al.）证明”低功耗 CPU + flash”能省电跑 KV，但内存索引用的是普通哈希，每条几十字节。
  • 2010：DRAM 价格仍在 ~10 美元/GB，数据中心用十亿级条目时内存成本是大头。
  • 2011：Lim、Fan、Andersen、Kaminsky 在 SOSP 发表 SILT，三层结构 + 熵编码 trie，把内存压到 0.7 字节/条，论文成 SOSP 当年 best paper 候选。
  • 此后：思想被 RocksDB / WiscKey / Faster 等系统借鉴（Bloom filter 分层、value 分离），但完整的”hash → sorted 三层”并未广泛采用，因为它牺牲了范围查询。

学到什么

  1. 存储系统的瓶颈在 SSD 时代换位——内存索引成为新约束，0.7 字节是逼近信息论下限的工程艺术
  2. 分层 + 数据结构按角色选——写入层用哈希、归档层用排序 trie，每层只解决自己擅长的问题
  3. 只读结构能压到极致——所有”原地更新”开销转嫁到合并，但合并可以分摊到后台
  4. Bloom filter 是分层系统的胶水——没有它，每次 GET 都得查所有层，分层就失去意义

延伸阅读

  • 论文 PDF：SILT SOSP 2011（14 页，前 5 页讲清楚思想）
  • 相关项目：FAWN-KV（SILT 前身，同一作者团队）
  • 视频讲解：SOSP 2011 talk 录像（搜 “SILT key-value store SOSP 2011”）
  • 对照阅读：wisckey —— LSM 上把 value 分离，思路与 SILT 互补
  • 综述：Mark Callaghan 博客 “On the SILT paper”（讲为什么 RocksDB 没采纳 SILT 路线）

关联

  • lsm-tree-1996 —— LSM 让所有层都排序，SILT 只让最后一层排序
  • rocksdb-2017 —— 工业级 LSM，借鉴 SILT 的 Bloom filter 分层但不用 trie 索引
  • rocksdb-lsm —— RocksDB 的 LSM 实现细节，对照看更能理解 SILT 的取舍
  • bigtable-2006 —— Google 提出 SSTable + Memtable，SILT 的三层是它的极致内存版
  • skip-list-1990 —— LevelDB 的 Memtable 用跳表，SILT 的 LogStore 用哈希
  • b-tree-1972 —— 磁盘时代的标准结构，B-tree 内存占用比 SILT 高数十倍
  • cassandra-2010 —— 分布式 LSM，每节点本质也是分层存储

反向链接

  • b-tree-1972 —— B-Tree 1972 — 磁盘友好的索引结构
  • bigtable-2006 —— Bigtable 2006 — Google 把行级随机读写做到 PB 级的存储系统
  • cassandra-2010 —— Cassandra 2010 — 把 Dynamo 的 P2P 骨架和 Bigtable 的列族数据模型拼成一个东西
  • lsm-tree-1996 —— LSM-Tree 1996 — 写优化存储引擎
  • rocksdb-2017 —— RocksDB 2017 — 把 LSM-Tree 的”空间放大”压到极低的工业经验
  • rocksdb-lsm —— LSM-tree 与 RocksDB — 把所有写都变成顺序写
  • skip-list-1990 —— Skip List — 用抛硬币代替平衡树