论文阅读《Lance: Efficient Random Access in Columnar Storage through Adaptive Structural Encodings》

论文《Lance: Efficient Random Access in Columnar Storage through Adaptive Structural Encodings》讨论的是一个看似底层，但对 AI/ML 数据系统非常关键的问题，即 列式存储格式不仅要擅长顺序扫描，也要能高效地做随机访问。

现代 AI/ML 工作负载同时需要“扫描大量数据”和“随机读取少量数据”，而传统列式格式的瓶颈不只在压缩算法，也在结构信息如何编码。Lance 通过自适应结构编码，在全扫描和随机访问之间取得了更好的平衡。这篇论文会围绕以下问题展开：

为什么列式存储在 AI/ML 场景下需要重视随机访问？
什么是论文反复强调的“结构编码”？
Parquet、Arrow 和 Lance 分别做了什么取舍？
Lance 的 Full Zip、Miniblock 和 Struct Packing 如何工作？
这篇论文对文件格式、向量数据库和 ML 数据系统有什么启发？

先从一个实际场景说起

假设我们有一个多模态检索系统，数据表大致长这样：

id	text	image	embedding	metadata
1	一段文本	一张图片	768 维向量	JSON 信息
2	一段文本	一张图片	768 维向量	JSON 信息
…	…	…	…	…

这个系统至少会有两类访问模式。

第一类是全表扫描。例如构建向量索引时需要读取所有 embedding 列；训练模型时需要一批批扫过图片、文本或特征列。列式存储天然适合这种模式，因为它可以只读需要的列，而且同一列的数据类型相同，压缩和向量化执行都更友好。

第二类是随机访问。例如向量索引召回了 100 个候选行号：

1	[1042, 99102, 812300, 1200033, ...]

接下来系统需要根据这些行号取回对应的 text、image、metadata 列。这些行号通常没有连续性，也不一定与文件中的物理顺序相关，这就是典型的随机访问。

传统经验里，列式格式适合扫描，行式格式适合点查，但 AI/ML 工作负载打破了这种简单划分，要求同一份数据既要服务训练和分析，又要服务检索、RAG、样本回放、调试和在线推理链路。论文关注的正是这个矛盾，即 能不能设计一种列式格式，既保留列式扫描和压缩优势，又能在随机访问时尽量接近底层 NVMe 存储的能力？

为什么 NVMe 改变了问题的重心

过去谈云上数据湖时，很多系统默认数据主要放在 S3 这类对象存储里。对象存储带宽高，但单次请求延迟较高，IOPS 相对有限。所以很多格式设计会倾向于较大的读取块，例如一次读几百 KB 或几 MB。但论文指出，新的存储层正在改变这个假设，越来越多系统会在云存储和计算之间加一层 NVMe 缓存，或者直接使用低延迟存储。NVMe 的特点是：

可以支持非常高的随机 IOPS。
小块读取也可以很快，典型扇区大小是 4KB。
如果文件格式每次随机访问都要读取远大于实际需要的数据，就会浪费 NVMe 的潜力。

这里有三个关键指标：

指标	含义	例子
IOPS	每秒能发起多少次 I/O 操作	随机读取 100 个候选行，需要多少次读？
读放大	实际读取的数据量 / 真正需要的数据量	只需要 100 字节，却读了 8KB 页面
解码开销	读到数据后 CPU 需要做多少工作	为了取一个值，是否要解压整页？

举个例子，如果要读取一条 16 字节的字符串：

1
2
3

真正需要：16 字节
实际读取：8KB 页面
读放大：8192 / 16 = 512 倍

这不一定总是坏事，因为一次 8KB 读取可能刚好适合磁盘，也可能顺带读到附近数据，但如果访问完全随机，读放大会很快变成瓶颈。论文的重要前提是：在 NVMe 场景下，文件格式应该把重心放在更好的去适配小块随机读取，而不是把随机访问当作列式格式天生无法解决的弱点。

结构编码：平衡顺序与随机访问的性能矛盾

很多人谈列式格式性能时会首先想到压缩算法，例如 Snappy、LZ4、字典编码、bit packing、FSST，但这篇论文强调 压缩之前还有一层同样关键的设计，即结构编码。

编码	回答的问题	类比
结构编码	一个逻辑列（尤其是带 null、字符串、list、struct 的复杂列）应该拆成哪些物理缓冲区存储？这些缓冲区如何排列？读取某一行时需要访问哪些缓冲区？	决定家具如何摆进房间
压缩编码	每个缓冲区本身如何压得更小？	决定每件家具如何折叠、压缩、打包

如果家具摆放方式不合理，即使每件家具都压缩得很好，取某一件东西时仍然可能要搬开一堆箱子。

可以用一个 List<String> 类型的列来直观感受结构编码的重要性：

row 0: ["apple", "banana"]
row 1: null
row 2: ["cat"]
row 3: []

这个逻辑列看起来只有一列，但底层可能需要很多结构信息：

哪些行是 null list？
每个 list 从哪里开始、到哪里结束？
list 里面的哪些 string 是 null？
每个 string 的字节范围在哪里？
真正的字符串字节数据在哪里？

在 Arrow 风格布局中，这些信息通常分布在多个缓冲区中：

list validity buffer
list offsets buffer
string validity buffer
string offsets buffer
string data buffer

如果要随机读取第 10 行，就可能需要先读 list 的有效性和偏移，再根据偏移去读 string 的有效性和偏移，最后再读 string 数据。论文中提到，对于含 null 的 List<String>，一次取值可能需要 5 个 IOPS，并且还分成多个阶段，因为后一个读取依赖前一个读取的结果。这就是结构编码影响随机访问的直观原因，随机访问慢不一定是因为数据压缩得不好，而可能是因为找到一个值需要太多跳。

Parquet：支持随机访问，但代价是调参和缓存

Parquet 的核心做法是把列数据分成 Page，每个 Page 中包含一段值，以及对应的重复层级、定义层级等结构信息。可以简化理解为：

Column Chunk
├── Page 0: rows 0..999
├── Page 1: rows 1000..1999
├── Page 2: rows 2000..2999
└── ...

如果有 Page Offset Index，系统可以先查出某一行属于哪个 Page，然后读取这个 Page。这带来一个好处，即对某一行的随机访问通常只需要读它所在的 Page，而不是到处读取多个缓冲区，但问题在于 Page 大小很难两全。

Page 较大	Page 较小
扫描和压缩通常更友好	随机访问读放大更小
随机访问会读很多无关数据	元数据和 Page Offset Index 更多
对大块顺序 I/O 友好	更依赖调度和系统调用效率

论文中一个很重要的结论是：Parquet 如果正确配置，随机访问性能可以比默认设置高很多，甚至超过 60 倍。这说明 Parquet 格式本身并不是完全不能做随机访问，问题在于默认配置和常见使用方式往往不是为这种场景而优化的。

不过 Parquet 还有一个大问题：当列值很大时，小 Page 会导致 Page 数量巨大，Page Offset Index 也会变大。论文举例说，如果大型列做到一个值一个 Page，parquet-rs 中 Offset Index 可能达到每十亿行约 20GB 搜索缓存，这对向量、图片、长文本这类 ML 数据非常不友好。

Arrow：内存中很优雅，磁盘上不一定高效

Arrow 的设计目标之一是内存中的高效列式表示，它的布局非常适合零拷贝、向量化执行和跨系统共享内存数据。对于固定宽度、无压缩、无复杂嵌套的数据，Arrow 风格布局非常直接。例如 UInt64 列：

1	values buffer: [10, 20, 30, 40, ...]

要访问第 i 个值，只要算出偏移：

1	offset = i * 8

这在内存里非常高效，但当数据在磁盘或对象存储上，并且类型变成字符串、list、struct 后，Arrow 的多个缓冲区布局就可能导致随机访问需要多次 I/O。也就是说，Arrow 的问题不是表达能力不够，而是它的结构编码更偏向内存访问，不一定适合以 IOPS 为成本模型的磁盘随机访问。

可以这么理解，Arrow 像是把所有零件整齐分类放在不同抽屉里，因为在内存中打开抽屉很便宜，所以很舒服，但磁盘上每打开一个抽屉都是一次 I/O，所以就贵了。

Lance 的核心思路：根据数据大小选择结构编码

Lance 的目标不是简单地说永远使用某一种布局，而是做自适应选择。论文提出两种主要结构编码：

编码	适合对象	核心取舍
Full Zip	对大值进行编码，例如向量、图片、长文本	尽量把一个值需要的信息放在一起，随机访问更直接
Miniblock	对小值进行编码，例如标量、小字符串	保留分块和向量化处理，扫描更高效

这就是论文标题里的 Adaptive Structural Encodings，即自适应结构编码。

Full Zip：把一个值需要的信息放近一点

Full Zip 的直觉很像把列式布局的一部分转成“按值聚合”的布局。假设一个可变长度字符串列在传统列式布局中可能是：

1
2
3

offsets: [0, 3, 8, 12]
data:    "foobarbazqux"
validity: 1110...

要读第 2 个字符串，需要先看 offset，再去 data 里取对应范围。Full Zip 的想法是把每个值相关的控制信息和值放在一起：

[value 0 control][value 0 length][value 0 bytes]
[value 1 control][value 1 length][value 1 bytes]
[value 2 control][value 2 length][value 2 bytes]
...

其中 Control Word 存放定义层级和重复层级等结构信息。

这对大值特别合适。以 4KB 的向量为例，每个值本身很大，为它额外放一个 1 字节 Control Word 几乎不影响空间效率，但随机访问时可以更快定位并读取这个值。对于可变长度值，Full Zip 还需要 Repetition Index，可以把它理解成一个“目录”：

1	row id -> 该行值在压合缓冲区中的字节偏移

随机访问时先查目录，再读目标值。论文的目标是让可变宽度列在随机访问时最多 2 个 IOPS。

Full Zip 的核心价值是：对大值来说，减少 IOPS 和搜索缓存比极致列式向量化更重要。

论文还专门提到了搜索缓存（Search Cache），指代打开文件或首次搜索时加载到内存的小型辅助元数据，其作用类似索引目录，帮助随机访问快速定位数据。搜索缓存的难点在于它不能太大，如果一个系统有十亿行数据，每列都需要大量搜索缓存，那么缓存本身就会变成内存负担。对于向量数据库、RAG 系统、在线检索系统，内存还要留给向量索引、过滤索引、查询执行和服务进程，不可能全部交给文件格式元数据。

这正是 Full Zip 对大值有吸引力的地方，它不需要为大值维护类似 Parquet 每页 Offset Index 的搜索缓存，而是通过值布局和 Repetition Index 控制随机访问成本。

Miniblock：小值不适合逐值 zip

如果每个值只有 8 字节，例如 UInt64，还给每个值都加 Control Word、长度、逐值组织，就可能让 CPU 做很多额外工作。对于小值，全扫描时最重要的是批量处理和向量化。所以 Lance 对小类型使用 Miniblock 方案。它类似 Parquet Page，但块更小，目标是让每个压缩块接近 1 到 2 个磁盘扇区，也就是大约 4KB 到 8KB。

可以简化理解为：

Column
├── Miniblock 0: 约 4KB-8KB 压缩数据
├── Miniblock 1: 约 4KB-8KB 压缩数据
├── Miniblock 2: 约 4KB-8KB 压缩数据
└── ...

读取某个小值时，需要读它所在的 miniblock，并解码整个块，这会有读放大和计算放大问题，但换来的是：

块内可以使用不透明压缩，例如 Snappy、LZ4 一类需要成块解压的编码。
扫描时可以批量解码，CPU 更容易向量化。
搜索缓存相对可控。

Miniblock 的核心价值是：对小值来说，牺牲一点随机访问精度换取更好的扫描效率和压缩灵活性。

Struct Packing：列式和行式之间的可调旋钮

论文还讨论了 Struct Packing，它的想法是：如果经常一起读取一个 struct 的多个字段，就可以把整个 struct 当成一个列来存。例如有一个列：

user: Struct {
  id: UInt64,
  age: UInt8,
  country: String,
  score: Float32
}

普通列式布局会把它拆成多个叶列：

user.id
user.age
user.country
user.score

如果查询经常只读 user.age，这种拆分固然很好，但如果随机访问时总是要取完整 user，那么拆得太细会导致多个列都要读取。Struct Packing 则会把整个 struct 打包成一个列。这样读取完整 struct 的随机访问更快，但单独扫描某个字段会变慢，因为你必须读整个 struct 再丢弃不需要的字段。

这本质上提供了一个在列式和行式之间移动的旋钮：

更列式：适合单列扫描、投影、分析。
更行式：适合整行随机访问、点查、搜索结果回表。

这对 AI/ML 系统很有启发，因为很多对象不是传统表格里的简单字段，而是一组经常一起访问的样本，包含图片、文本、标签、向量、元信息。它们是否应该完全拆列，还是局部打包，取决于访问模式。

总结

这篇论文的价值不只是介绍一个新文件格式，而是把一个长期被低估的问题讲清楚了，即列式存储的性能不只由压缩算法决定，也由结构信息如何组织决定。论文将 Lance 与代表性的列式存储格式 Parquet 和 Arrow 进行对比，可以把三种格式的取舍类比成仓库取货：

格式	类比	优点	缺点	关键
Parquet	把货物按箱打包	整箱搬运、批量扫描很高效	只要一个小物品时也要搬一整箱	箱子大小很重要
Arrow	把零件按类别放在不同货架	分类清晰、拿取直接	每去一个货架都要刷卡、开门、等待就会很慢	内存访问便宜，磁盘 I/O 不便宜
Lance	根据货物大小和使用方式重新组织仓库	大件货把说明书、标签、货物绑在一起直接取走；小件货按小箱批量打包；经常一起取的组合可以打成套装	块大小、打包方式仍带启发式	自适应结构编码

落到具体设计上：

Parquet 证明了 Page 结构可以让列式格式具备不错的随机访问潜力，但它需要谨慎调参，并可能在大值场景下面临搜索缓存压力。
Arrow 证明了内存列式布局可以非常直接高效，但它的多缓冲区结构在磁盘随机访问中可能产生过多 IOPS。
Lance 则尝试把这两类经验结合起来，对大值使用 Full Zip 编码让随机访问尽量直接，对小值使用 Miniblock 编码保留批量扫描和压缩效率，对经常一起访问的结构使用 Struct Packing 在列式和行式之间提供可调空间。

这篇论文对数据系统工程也有几条直接启发：

不要只看压缩率。压缩率高不一定代表系统快，如果为了取一个值必须解压大量无关数据或读取多个分散缓冲区，随机访问仍然会很慢。评估格式时至少要同时看压缩后文件大小、全扫描吞吐、随机访问 IOPS、读放大、解码 CPU 开销和搜索缓存大小。
文件格式需要理解硬件。S3、NVMe、本地 SSD、内存的成本模型不同，对 S3 合理的读取粒度对 NVMe 可能过大，对内存友好的多缓冲区布局对磁盘可能产生过多 IOPS。这意味着文件格式不能只抽象成“逻辑表如何序列化”，还必须考虑底层硬件的访问模式。
AI/ML 数据不是传统 OLAP 表。传统 OLAP 主要关心扫描、聚合、过滤和投影，而 AI/ML 数据还经常包含大向量、图片/音频/视频等 blob、长文本、Deeply-nested Metadata、检索后回表、训练中的随机采样，这些都让“随机访问 + 列式扫描”的组合变成一等需求。
可配置结构编码可能比单一格式更重要。论文提到不存在普遍正确的结构编码，一种格式如果把结构编码写死就很容易只适合某一类工作负载，更理想的方向是允许不同列、不同类型、不同访问模式选择不同结构编码，Lance 的 Full Zip 和 Miniblock 就体现了这种思想。

当然，论文提出的方向也有一些值得继续观察的地方：

Lance 2.1 在论文中仍被视为实验性格式，结构编码设计是否能在更多语言绑定、更多引擎、更多真实数据集上稳定发挥还需长期验证。
论文实验主要聚焦 NVMe，虽然也讨论了云存储，但不同对象存储、缓存层、网络环境和并发模型会改变结果。
Miniblock 的块大小选择仍带启发式，在多列场景中选择合适块大小并不容易。
格式层面的优势要转化为端到端系统收益，还依赖查询引擎、调度器、缓存策略、索引结构和并发控制，文件格式是关键基础但不是全部。

从更大视角来看，这篇论文反映了 AI/ML 数据系统的一个趋势，即数据格式不再只是离线分析的存储容器，而是正在成为训练、检索、推理和数据管理之间的共同性能基础。谁能更好地同时服务扫描和随机访问，谁就更有机会成为下一代 ML 数据基础设施中的关键组件。