Dremel

标签

分布式/计算

字数

16722 字

阅读时间

65 分钟

Dremel 是只读嵌套数据的交互式分析查询系统。它把两件事合在一起 —— 多级执行树与列式数据布局 —— 从而做到在万亿行表上以秒级完成聚合查询；系统能扩到数千 CPU 与 PB 级数据，在 Google 内部有数千用户。

它不是 MapReduce 的替代品，定位是互补：常用来分析 MapReduce 管道的输出，或者为更大的计算做快速原型。2006 年起就在生产环境，部署实例从几十节点到几千节点。

为什么需要它：交互式响应与原地数据

交互式响应时间在数据探索、监控、在线客服、快速原型、调试数据管道这些事上带来的是质的差别，不是量的差别。而在大尺度上做交互式分析需要很高的并行度，这里有两个规模账：

用当时的商用磁盘，1 秒读完 1 TB 压缩数据需要数万块磁盘；
CPU 密集的查询可能需要数千个核才能在秒级完成。

Google 的并行计算跑在共享的商用机器集群上，这个环境有几个必须正视的性质：集群里同时跑着大量分布式应用、负载差异很大、机器硬件参数各异；一个 worker 执行某个任务可能比别的慢得多，也可能因为故障、或者被集群管理系统抢占而永远跑不完。因此对付掉队者与故障是拿到快速执行与容错的前提。

另一个前提是数据形态：web 与科学计算里数据常常是非关系型的，编程语言的数据结构、分布式系统交换的消息、结构化文档，天然适合用嵌套表示；而把它们规范化再在 web 规模上重组，通常是不可行的。

Dremel 的答案有两个要素：

要素	内容
in situ（原地）	不搬数据，直接在所在的存储层上访问 —— 分布式文件系统（GFS）或别的存储层（Bigtable）
不翻译	用类 SQL 的高层语言写 ad hoc 查询，原生执行，不把它们翻译成 MapReduce job（这是与 Pig、Hive 这类层的分别）

"原地"这件事的价值值得说清：它省掉了耗时很长的加载阶段 —— 而在分析型处理里，这个加载阶段正是数据库难以被用起来的主要原因之一，往往可以跑上几十个 MapReduce 分析，一个 DBMS 还没把数据加载完、连一条查询都没执行。附带的好处是文件系统里的数据可以用标准工具摆弄（搬到别的集群、改访问权限、按文件名圈出要分析的那一部分）。

它借鉴了三个已有想法：分布式检索引擎里的 serving tree（查询沿树下推、每一层都重写一次、结果靠聚合下层回包得到）、类 SQL 的高层语言、以及列条纹（column-striped）存储表示。列存用在平面关系数据上早已成功，但没有被扩展到嵌套数据模型 —— 这正是 Dremel 的主要贡献所在。

它的使用场景很杂，一共列了 11 类：抓取到的 web 文档分析、Android Market 的应用安装数据跟踪、Google 产品的崩溃上报、Google Books 的 map 结果、垃圾内容分析、Google Maps 地图瓦片的调试、托管 Bigtable 实例的 tablet 迁移、分布式构建系统上的测试结果、几十万块磁盘的 I/O 统计、数据中心作业的资源监控、以及代码库里的符号与依赖关系。

两条规模账值得放在一起读，因为它们分别框定了"读"与"算"两侧的下限：

约束	量级	推出的结论
磁盘读带宽（当时的商用磁盘）	1 秒读完 1 TB 压缩数据需要数万块磁盘	不减少要读的字节数，执行层的优化补不上这个缺口
计算	CPU 密集的查询要数千个核才能在秒级完成	算力这一侧是可以靠并行度买到的

两相对照能看出整套设计把力气花在哪一侧：并行度可以靠加机器解决，而"要读多少字节"只能靠把数据按列摆。这也是为什么"原地访问"与"列式布局"这两个要素是配套的 —— 就地读一份列式数据，读的字节数由查询引用到的字段决定，与表的宽度无关。

"不绑定某种数据处理工具的格式"这个选择还有一个不显眼的后果：文件系统里的数据可以用标准工具处理 —— 搬到别的集群、改访问权限、按文件名圈出要分析的那一部分。以文件名划分范围这件事，在后来的系统里长成了分区裁剪：把筛选条件编码进目录结构，扫描阶段直接跳过整片目录。这是"表还在文件系统里"这个前提换来的能力 —— 数据一旦先被加载进某个私有格式的存储，这条路就没有了。

"in situ 的代价"值得补一句：省掉加载阶段的另一面是每次查询都要重新做解析 —— 没有一份"已经加载好、附带索引与统计信息"的副本可以复用。列式格式用"按列裁剪 + 逐列统计量"把这件事的代价压到了可接受的范围，但它自始至终没有索引层：能跳过的只有"整片不匹配的文件或 row group"，做不到"精确定位到某几行"。这是"面向扫描"这个定位的直接后果 —— 靠并行度把一次全量扫描做快，而不是靠预先建好的结构少扫一点。

这条差别在选型时会变成一个很实际的问题："点查"这类只取极少几行的查询，在这套系统上仍然是"扫一遍再筛"，代价由数据量而不是结果量决定。它的定位从一开始就写明了 —— 用来分析 MapReduce 管道的输出、为更大的计算做快速原型；要低延迟地点查少量记录，那是另一类系统该做的事。

数据模型：强类型嵌套记录

这个数据模型来自分布式系统的序列化需求（"Protocol Buffers"这个名字就是那么来的），在 Google 广泛使用，有开源实现。它基于强类型的嵌套记录，抽象语法是

τ = dom ∣ ⟨ A_{1} : [τ ∣ ?], \dots, A_{n} : [τ ∣ ?] ⟩

其中 $dom$ 是原子类型（整数、浮点、字符串等）。记录由一个或多个字段构成。字段的"多重性"只有三种：

标签	语义
*repeated（ $$ ）**	可以在记录里出现多次，解释为值的列表 —— 因此字段出现顺序是有意义的
optional（ $?$ ）	可以从记录里缺失
required（无标签）	必须恰好出现一次

举个例子，一个表示 web 文档的 Document：它有 required 的整数 DocId、optional 的 Links（里面是若干 Forward 与 Backward 条目，各自持有别的网页的 DocId）；一个文档可以有多个 Name（即引用它的不同 URL）；一个 Name 里是一个 Code 与 optional Country 配对构成的序列。

字段构成一棵树的层级，嵌套字段的完整路径用点号记法（如 Name.Language.Code）。

跨语言互操作靠一份标准的二进制线格式：字段值按它们出现在记录里的顺序依次排布。于是 Java 写的 MapReduce 程序可以消费由 C++ 库暴露的记录。这条互操作要求直接推出一个工程约束：一旦记录以列式表示存储，"快速装配出记录"就变得很重要 —— 否则与 MapReduce 及其他数据处理工具的互操作会被拖垮。

嵌套列存：三个挑战

目标是把某个字段的全部值连续存放：这样读 A.B.C 就不必连带读 A.E、A.B.D。

记录式（行）：  [ DocId | Links | Name₁(Url, Lang) | Name₂(Url, Lang) ]  ← 读一个字段要穿过整行
                 ────────────────────────────────────────────────▶

列式（列条纹）：
   DocId:            d1      d2      d3  ...
   Links.Backward:   ...
   Links.Forward:    ...
   Name.Url:         u1      u2      u3  ...        ← 同一字段的值连续
   Name.Language.Code: ...

代价是结构信息不能丢。要解决三件事：在列式格式里无损表达记录结构、编码要快、装配的代价要低。

repetition level 与 definition level

光有值不足以表达结构。 给两个来自重复字段的值，无法知道它们在哪一层发生了重复 —— 是两条不同记录里的两个值，还是同一条记录里的两个重复值。同理，给一个缺失的 optional 字段，也不知道哪些外层记录是被显式定义过的。

repetition level 回答前一个问题：它说明在该字段的路径上，哪一个重复字段处发生了重复。

以 Name.Language.Code 为例，它的路径里有两个重复字段（Name 与 Language），所以 repetition level 取值 0 到 2，其中 0 表示一条新记录的开始。自上而下扫描样本记录 $r_{1}$ ：

值	判断	repetition level
`en-us`	还没遇到任何重复字段	0
`en`	`Language` 发生了重复	2
`en-gb`	最近发生重复的是 `Name`（`Language` 在那之后只出现过一次）	1

所以 Code 在 $r_{1}$ 里的三个值，repetition level 依次是 0、2、1。还有一处细节： $r_{1}$ 的第二个 Name 里根本没有 Code，为了把这个事实表达出来，要在 en 与 en-gb 之间插入一个 NULL —— 否则无从判断 en-gb 属于第三个 Name 而不是第二个。

definition level 回答后一个问题：路径 $p$ 上每个值（尤其是每个 NULL）都有一个 definition level，表示 $p$ 上那些本来可能未定义的字段（因为 optional 或 repeated）里实际出现了几个。三个例子都来自样本记录：

$r_{1}$ 没有 Backward 链接，但 Links 字段是定义了的（在第 1 层）→ 为保住这个区别，往 Links.Backward 列里加一个 definition level 为 1 的 NULL；
Name.Language.Country 在 $r_{2}$ 的缺失处，definition level 是 1；
同一个字段在 $r_{1}$ 的两处缺失，definition level 分别是 2（在 Name.Language 内）与 1（在 Name 内）。

为什么用整数 definition level，而不是"是不是 NULL"的位：这样叶子字段（如 Name.Language.Country）的数据里就带着它那些父字段的出现情况。后面讲记录装配时会用到这份信息。

这套编码无损地保留了记录结构。

把两个 level 的性质收成一句话：repetition level 描述"值与值之间的边界"，definition level 描述"值与结构之间的边界"。前者回答"同一列里的相邻两个值，是不是同一条记录、或同一个父记录里的"，后者回答"这个值（或这个 NULL）在路径上走到第几层才第一次出现"。

由此有两条容易记混的推论：

repetition level 只在"同一列有多个值"时才需要 —— 一个不在任何 repeated 字段之下的 required 叶子字段，它的列里每个值都属于新记录，repetition level 恒为 0，于是被省掉；
definition level 携带的是"父字段的出现信息" —— 这正是它不能用"是不是 NULL"一个位来表达的原因。NULL 的位只能说明"这里没有值"，而整数能说明"缺在第几层"，后者决定了装配时该往上补几层空壳。

还有一处只有动手构造过才会知道的细节：要在缺失处的两个值之间插入 NULL。前面那个例子（ $r_{1}$ 的第二个 Name 里没有 Code）说明，不插入这个 NULL 的话，en-gb 会被装配到第二个 Name 下 —— 结构信息在列里的唯一载体就是"每个值带着自己的 levels"，值在列里的位置本身不携带结构信息。凡是"结构变了、值没变"的地方，都必须由 NULL 补齐这个位置。

一个常被问到的边界：这套编码能表达"值在列表里的位置"，但不携带类型、字段名与记录边界标记。列本身就是"字段名 + 类型"的载体（写在文件元数据里），而记录边界完全由 repetition level 为 0 来标记。于是列一旦按字段拆开，"这一列里有几条记录"这个量只能靠数 repetition level 为 0 的个数得到 —— 这也解释了定义里为什么要强调 0 表示"一条新记录的开始"：那个 0 是唯一的记录边界信号，缺了它，一列值就退化成"一堆没有归组的数"。

编码形态

每个列存成一组 block，每个 block 里是 levels（repetition + definition）与压缩后的字段值。几处省法：

NULL 不显式存储 —— 由 definition level 决定：任何小于"路径上 repeated 与 optional 字段总数"的 definition level 都表示 NULL；
永远有定义的字段不存 definition level；
repetition level 只在需要时存 —— 例如 definition level 为 0 蕴含 repetition level 为 0，后者可以省掉；
样本数据里 DocId 这一个 level 都不存。

levels 按位序列打包，需要几位用几位 —— 例如最大 definition level 是 3 时，每个 definition level 用 2 位。

把记录拆成列

基础算法会递归进记录结构、为每个字段值算出 levels。一个不能忽略的事实：字段值缺失时也照样要把 levels 算出来。而 Google 的很多数据集很稀疏 —— schema 有几千个字段、某条记录只用到其中几百个，并不罕见 —— 所以缺失字段的处理必须尽量便宜。

做法是建一棵与 schema 字段层级同构的 field writer 树。核心思路：

field writer 只在自己有数据时被更新，不主动把父状态往树里传播。

为此，子 writer 从父那里继承 levels，并在有新值加入时与父的 levels 同步。

记录装配：一台有限状态机

对面向记录的工具（例如 MapReduce）来说，装配记录的代价是关键。给定字段子集，目标是重建出"只含被选字段、其余字段都被剥掉"的原记录。

核心思路是造一台有限状态机（FSM）：它读各字段的值与 levels，把值按顺序追加到输出记录上。

一个 FSM 状态对应"为每个被选字段各配一个 field reader"；
状态转移用 repetition level 打标签；
某个 reader 取到一个值后，看下一个 repetition level 决定接下来用哪个 reader；
每条记录把 FSM 从 start 走到 end 一次。

（示意图，非精确还原。自环的含义是：当下一个 repetition level 等于该字段自身的层级时，继续用同一个 reader。）

转移怎么构造：设当前 field reader 为字段 $f$ 返回的下一个 repetition level 是 $l$ 。在 schema 树里从 $f$ 出发，找到"在 level $l$ 处重复的那个祖先"，再选该祖先内部的第一个叶子字段 $n$ ，就得到转移 $(f, l) \to n$ 。举例： $f = Name.Language.Country$ 读出 $l = 1$ ，它在 level 1 处重复的祖先是 Name，而 Name 的第一个叶子字段是 $Name.Url$ 。

只取字段子集时，构造一台更简单的 FSM，执行也更便宜。

一处容易被忽略的价值：这套编码与装配算法保住了 Country 的外层结构 —— 对需要访问"第二个 Name 的第一个 Language 里的 Country"的应用来说这很重要，对应 XPath 里的 /Name[2]/Language[1]/Country。

为什么稀疏数据的处理必须便宜，用一个数字就能说清：schema 有几千个字段、某条记录只用到其中几百个，这在 Google 的许多数据集里很常见。拆列与装配算法如果按"字段数 × 记录数"的规模工作，成本就直接由 schema 决定、与数据无关 —— 这是稀疏数据下最坏的一种开销结构。

field writer 树的取舍正落在这里：它只在自己有数据时被更新，不主动把父状态往树里传播；父状态通过"子 writer 从父继承 levels、有新值时与父同步"传下来，于是没有数据的那些子树根本不参与。代价是父子之间多维护一层同步关系，换来的是开销与"实际用到的字段数"成正比，而非与 schema 字段数成正比。

装配侧有个对称的难点：拆列是记录驱动的，装配是列数驱动的。取字段子集时，FSM 的状态数由"被选字段数"决定 —— 这也解释了为什么只取少量字段时构造出的 FSM 更简单、执行也更便宜：状态多少直接对应自动机的规模，而规模决定了每条记录要走的转移数。

最后一处与表达力相关的价值：这套编码顺带保住了嵌套的序号语义。访问"第二个 Name 的第一个 Language 里的 Country"（对应 XPath 里的 /Name[2]/Language[1]/Country）是可表达的 —— 因为 repeated 字段的顺序有意义，而 levels 把这个顺序完整带了下来。如果当初选了"把嵌套摊平成列名"的做法，这种按序号定位的语义就丢了。

拆列与装配这两条路径不对称，值得记住这个不对称：拆列发生在写入侧、一次成型；装配发生在读取侧、每次查询都要做一次。优化投入的分布也就由此定了 —— 写入侧可以做复杂的编码与压缩（一次成本），读取侧必须尽量少做事（反复成本）。这也解释了为什么"让执行层绕开记录装配"的收益远大于"把装配算法写快一点"：前者的收益随查询次数累加，后者只是把一个固定成本压低。

底层依赖：编码、压缩与存储层

这套编码的压缩收益具体从哪来，值得逐条拆开，因为"列式省空间"这个说法在实测里并不成立 —— 记录式用了更重的压缩，磁盘占用大致相同。收益落在别处。

① NULL 不占空间。 任何小于"路径上 repeated 与 optional 字段总数"的 definition level 都表示 NULL，于是 NULL 不必显式存一个值。稀疏数据集上这一条的收益最大 —— schema 有几千个字段、某条记录只用到几百个，是很常见的情形。

② 冗余的 level 被去掉。 三处：永远有定义的字段不存 definition level；definition level 为 0 蕴含 repetition level 为 0，后者可省；样本里 DocId 一个 level 都不存。

③ levels 按位打包，需要几位用几位。 最大 definition level 是 3 时，每个 definition level 用 2 位 —— 而不是固定用一个字节或一个整数。这一步是"元数据随列走"的代价控制：如果 levels 用固定宽度存，嵌套层级一深、列一多，元数据会先膨胀起来。

④ 压缩按列独立选。 同一张表里，字符串列和高基数数值列该用的编码完全不同；逐列指定编码与压缩，是"列式"这个布局顺带换来的自由度。

把这些合起来看，列式真正的收益是"读的字段数少"，而不是"存得少"。实测支持这个读法：记录式与列式的磁盘占用大致相同，但只读少数列时，列式表示的收益大约是一个数量级；列式嵌套数据的检索时间随字段数线性增长 —— 后一句反过来也说明，列式省的正是"不必读的那些列"。

存储层的分工也决定了几处实测条件：

列式格式落在分布式文件系统上（GFS 这类），于是"原地访问"省掉的加载阶段，是靠存储层本身的可用性换来的；
副本因子直接决定调度侧的余地：tablet 通常 三副本，某个副本访问不到就落到另一个；而实测里那张万亿行的表是两副本，于是"改派工作"的机会更少、掉队者更容易拖慢执行；
两级 cache 的作用不同：OS cache 让重复读变快（所以实测每次扫描前要刷掉 OS cache，保证所有时间都是冷读），而 stripe 内 block 的异步预取让同一列的连续读变快 —— read-ahead 缓存通常能达到 95% 的命中率。这两者一个服务跨查询复用，一个服务单次扫描的流水线。

几处实测里的硬件数字值得记下，因为它们框定了结论的适用范围：双核 Intel 处理器、磁盘读带宽 70 MB/s；以及开头那条规模账 —— 用当时的商用磁盘，1 秒读完 1 TB 压缩数据需要数万块磁盘。这条推算其实已经说明为什么必须做列裁剪：不减少要读的字节数，任何执行层的优化都补不上这个缺口。

把这一节带到的数字合起来，能看出瓶颈落在哪一环：

环节	量级	是不是瓶颈
存储带宽	磁盘读 70 MB/s；1 TB 要数万块盘	是，所以要列裁剪
解压	记录式里"大头花在解压上"，压缩数据从磁盘读出来只占约一半时间	是，所以要挑编码
装配 + 解析	各自都可能让执行时间翻倍	是，所以要让执行层绕开记录
列内预取	read-ahead 缓存命中率通常 95%	已经被压下去
元数据（levels）	需要几位用几位	被刻意控制过

五行里三行是"要减少的东西"，一行是"已经做好的"，一行是"被控制的" —— 这个配比说明这套系统的主要敌人不在存储层，而在**"列式数据 → 强类型对象"之间的那段转换**。这也解释了为什么"不翻译"和"原地访问"是一件事的两面：数据一旦被搬进某个私有格式或私有内存布局，这些开销就会在每次查询里重付一遍。

一条实用推论：判断一个列式系统是不是真省下了成本，不能看磁盘占用，要看它的读取路径上有几次"列 → 行"的转换。 每多一次，前面省下的带宽收益就可能被抵掉。

最后一处依赖藏在"位宽"上：levels 按位打包，需要几位用几位。这个选择在嵌套层级浅的时候看不出差别，层级一深就不一样了 —— 路径上 repeated 与 optional 字段的总数每增加一个，就需要多一位，而每一位都摊到该列的全部值上。于是深层嵌套表的元数据开销会随"最大层级"增长，而这份开销不能靠增加列数来摊薄。嵌套层数在这种格式里是一个带持续成本的维度，它与"列数多只是多存几列"是两类成本。

查询语言

语言基于 SQL，并且是面向"能在列式嵌套存储上以低代价实现"来设计的。没有给出形式化定义，只展示风格。每个语句（以及它翻译成的代数算子）吃一到多个嵌套表及其 schema，产出一个嵌套表及其输出 schema；字段用路径表达式引用。示例查询同时做了投影、选择与记录内聚合 —— 它产生嵌套结果，尽管查询里没有任何"构造记录"的写法。

三个算子的语义值得逐个记：

选择（WHERE）—— 剪枝。 把嵌套记录想成一棵带标签的树，每个标签对应一个字段名。选择算子把不满足条件的树枝剪掉 —— 只有那些 Name.Url 有定义、且以 http 开头的嵌套记录被留下。

投影 —— 层级由"最重复的输入字段"决定。 SELECT 里每个标量表达式在与该表达式所用到的"最重复的输入字段"相同的嵌套层级上发射一个值。所以字符串拼接表达式发射的 Str 值落在输入 schema 里 Name.Language.Code 的层级上。

记录内聚合。 COUNT 在每个 Name 子记录内部做聚合，为每个 Name 发射 Name.Language.Code 的出现次数，类型是 64 位无符号整数。

语言还支持嵌套子查询、记录间与记录内聚合、top-k、join、用户定义函数。

查询语言的三个取向

语法是 SQL 风格的，但有三处取舍与常见 SQL 引擎不同，而三处都直接服务于"能在列式嵌套存储上低代价执行"这个目标。

取向一：层级由"最重复的输入字段"决定，于是不需要构造语法。

SELECT 里每个标量表达式在与它用到的"最重复的输入字段"相同的嵌套层级上发射一个值。一个字符串拼接表达式如果用了 Name.Language.Code，发射出的值就自动落在 Name.Language.Code 那一层 —— 结果的嵌套形状是从输入字段的层级推出来的，用户不必写任何"构造记录"的语法。

好处很直接：执行路径可以完全绕开记录装配。投影只是一组按列扫描的迭代器，各自发射值并带上正确的 repetition 与 definition level，中间没有"建一个记录再把字段填进去"这一步 —— 而那一步正是"解析与装配各自都能让执行时间翻倍"里的一半。对照之下，XQuery 与面向对象查询语言通常需要显式重构（嵌套 for 循环加构造器），把"结果长什么样"交给用户写、也交给执行层去建。把层级交给推导，是用一部分表达力换执行路径的直通。

取向二：选择算子被定义成"剪枝"。

嵌套记录被看成一棵带标签的树，WHERE 的语义是把不满足条件的树枝剪掉。这与关系代数里"过滤行"不同：过滤的粒度落在子树上，而不在记录上。"只保留 Name.Url 以 http 开头的那些嵌套记录"落到执行上，是"在 Name 这一层做筛选、把不合格的整枝丢掉"，而不是"先取出所有记录再逐条判断"。

取向三：记录内聚合是一个独立算子。

COUNT 之类的聚合可以在每个子记录内部做，为每个子记录发射一个计数。这类需求是嵌套数据特有的，平面关系代数里没有对应物；收益也很直接 —— 实测里那条"只读了 70 TB 中的 13 GB、15 秒完成"的查询就靠它。

三件事合起来是同一个思路：把"嵌套"当作第一等的结构来处理，而不是把它摊平成行之后再想办法拼回去。

查询执行

serving tree 与查询重写

Dremel 用一棵多级 serving tree 执行查询：root server 收到查询、读表的元数据、把查询路由到下一级；叶子 server 与存储层通信，或者访问本地磁盘上的数据。

以一条聚合查询为例：

sql

SELECT A, COUNT(B) FROM T GROUP BY A

root server 收到后先确定 $T$ 的全部 tablet（表的水平分区），把查询重写成：

sql

SELECT A, SUM(c) FROM (R¹₁ UNION ALL ... R¹ₙ) GROUP BY A

其中

sql

R¹ᵢ = SELECT A, COUNT(B) AS c FROM T¹ᵢ GROUP BY A

$T_{1}^{i} \dots T_{n}^{i}$ 是第 1 级 server $i$ 所处理的那些 tablet 构成的一个不相交分区。每一级 serving 层都做同样的重写。最终查询抵达叶子，并行扫描 $T$ 里的 tablet；在回程上，中间 server 对部分结果做并行聚合。

这个模型的适用面要说清：它很适合返回小到中等结果的聚合查询 —— 而这类正是交互式查询里非常常见的一种。大聚合以及其他类别的查询，则需要借助并行 DBMS 与 MapReduce 里的那些机制。

query dispatcher：调度、容错、掉队者

Dremel 是多用户系统（通常同时有多条查询在跑）。query dispatcher 按优先级调度查询并做负载均衡；它另一个重要作用是容错 —— 应对"某个 server 变得比别的慢得多"或"某个 tablet 副本变得不可达"。

一个关键概念是 slot：slot 就是叶子 server 上的一个执行线程。举例换算：3000 个叶子 server 各用 8 个线程 = 24,000 个 slot；一张跨 10 万个 tablet 的表，可以按每个 slot 分到约 5 个 tablet 来处理。

调度侧的机制：

执行期间 dispatcher统计 tablet 处理时间的直方图；某个 tablet 耗时明显离谱，就把它改派到另一台 server；有些 tablet 需要被改派多次；
叶子 server 按列式表示读 stripe（数据条带）；stripe 里的 block 被异步预取，read-ahead 缓存通常能达到 95% 的命中率；
tablet 通常三副本；某个副本访问不到时落到另一个副本；
dispatcher 认一个参数：返回结果前必须扫过的 tablet 最小百分比。把它调低 —— 例如从 100% 调到 98% —— 往往能显著加快执行，副本因子小的时候尤其明显。

服务器内部

每台 server 有一棵内部执行树，对应物理查询执行计划（含标量表达式的求值）。多数标量函数会生成经过优化的、类型专用的代码。 对 project-select-aggregate 类查询，执行计划是一组以锁步（lockstep）方式扫描输入列的迭代器，它们发射聚合与标量函数的结果、并带上正确的 repetition 与 definition level —— 也就是执行期间完全绕过记录装配。

另有一处取舍：有些查询（如 top-k、count-distinct）用已知的单趟算法返回近似结果。

一个聚合查询从收到到返回

前面讲了 serving tree 的每一层都重写查询，但一次执行在时间轴上的形状还值得摊开一次 —— "每层都重写"这个说法要看到回程才完整。

以 SELECT A, COUNT(B) FROM T GROUP BY A 为例：

① root server 收到查询
   ├─ 读表 T 的元数据，确定它的全部 tablet
   └─ 把查询重写成对「第 1 级各 server 的不相交分区」的并集聚合：
       SELECT A, SUM(c) FROM (R¹₁ UNION ALL ... R¹ₙ) GROUP BY A
       其中 R¹ᵢ = SELECT A, COUNT(B) AS c FROM T¹ᵢ GROUP BY A
        │
        ▼
② 第 1 级各 server 收到的是「已被重写过」的查询
   ├─ 把自己那部分 tablet 再切成不相交分区
   └─ 再做一次同样的重写（层数越多，重复越多次）
        │
        ▼
③ 叶子 server：并行扫描 tablet
   ├─ 按列式表示读 stripe，block 被异步预取
   └─ 迭代器以锁步方式扫描输入列，发射带正确 levels 的部分聚合
        │
        ▼
④ 回程：中间 server 对下层回包做并行聚合，逐层收敛到 root

三处值得停一下。

第一次重写里 COUNT(B) 变成 COUNT(B) AS c 再套一层 SUM(c)，是这套模型的全部技巧：分组键 $A$ 原样上抛，聚合函数用"可再聚合的形式"上抛 —— COUNT 不能跨分区相加，但 SUM(COUNT) 可以。可再聚合性是挑选聚合函数的硬约束：COUNT 要变成 SUM，AVG 必须拆成 SUM 与 COUNT 两个分量分别上抛。不支持"可再聚合"的聚合函数，在这棵树上表达不出来。

第二次重写的意义是让"层数"成为一个可调项：每多一层，上抛的中间结果就多被合并一轮，root 侧要处理的分组数随之减少。这解释了实测里的分野 —— 分组少（几百条）时加层数收益不大，分组多（上百万）时加层数让耗时减半，因为瓶颈从"扫描"换成了"root 合并"。

回程做的是"再聚合"，而不只是"收集"：中间 server 拿到的是下属各分区已经部分聚合过的结果，它做的是同一个归约运算的又一次应用。这棵树上的每一层都在做同一件事，区别只在输入是"扫描出来的原始值"还是"下层回来的部分结果"。

实测

数据与条件：未压缩、未复制的状态下这些数据集约占 1 PB；所有表都是三副本（其中一张两副本）；含 10 万到 80 万个大小不一的 tablet。实验在两个数据中心、与许多其他应用同跑、常规业务时段进行；除非另作说明，执行时间是五次运行的平均；表名与字段名做了匿名化。

本地磁盘：列式 vs 记录式

对象是表 $T_{1}$ 的 1 GB 片段（约 30 万行）。在本地磁盘上，它以压缩列式表示占约 375 MB；记录式格式用了更重的压缩，磁盘占用大致相同。机器是双核 Intel、磁盘读带宽 70 MB/s。所有时间都是冷读 —— 每次扫描前刷掉 OS cache。 列式的每个数据点由 30 次运行平均得到，每次随机挑一组给定基数的列。

步骤	列式	记录式
读 + 解压	图 (a)	图 (d)：大头花在解压上，压缩数据从磁盘读出来只占大约一半时间
装配嵌套记录	图 (b) 在 (a) 之上叠加	——
解析成强类型 C++ 结构	图 (c) 再叠加	图 (e)：解析在读 + 解压之上再加 50%

记录式的这些开销是为所有字段付的，包括不需要的那些字段。

三条结论：

只读少数列时，列式表示的收益大约是一个数量级；
列式嵌套数据的检索时间随字段数线性增长；
记录装配与解析都很贵，各自都可能让执行时间翻倍。

还有一个实用的数：记录式开始优于列式的交叉点，经验上常常落在"几十个字段"，随数据集而变，也取决于是否需要做记录装配。

MapReduce 与 Dremel 的对照

算 $T_{1}$ 里 txtField 字段的平均词数。MapReduce 用 Sawzall 写（两个累加器 numRecs 与 numWords，每条记录 emit numWords <- CountWords(input.txtField)，最后算 numWords / numRecs）；SQL 等价写法是

sql

Q1: SELECT SUM(CountWords(txtField)) / COUNT(*) FROM T1

两个 MapReduce job 跑在 3000 个 worker 上；Dremel 用 3000 节点实例跑 $Q_{1}$ 。

配置	读入的压缩数据
MapReduce on records	87 TB
MapReduce on columns / Dremel	约 0.5 TB

（图 10 的说明是:3000 节点、850 亿条记录。）

由此得到两级台阶：MapReduce 从记录式换到列式，效率提升一个数量级 —— 从小时级到分钟级；再换成 Dremel，又提升一个数量级 —— 从分钟级到秒级。

serving tree 的层数：多分组聚合才吃这一层

两条 GROUP BY 查询，各自只扫一遍数据。表 $T_{2}$ 有 240 亿条嵌套记录，每条记录有一个重复字段 item 含数值 amount；item.amount 在数据集里重复了约 400 亿次。

sql

Q2: SELECT country, SUM(item.amount) FROM T2 GROUP BY country

$Q_{2}$ 返回几百条记录，读约 60 GB 压缩数据。

sql

Q3: SELECT domain, SUM(item.amount) FROM T2
     WHERE domain CONTAINS '.net' GROUP BY domain

$Q_{3}$ 读约 180 GB，产出约 110 万个不同的 domain。

三种拓扑下叶子 server 数固定为 2900（这样累计扫描速度可比）：2 级 = 1:2900、3 级 = 1💯2900、4 级 = 1:10💯2900。

查询	结果
$Q_{2}$ （分组少）	3 级时 3 秒；再加一层收益不大
$Q_{3}$ （分组多）	层数增加让执行时间减半；2 级时根本画不进图 —— root server 不得不近乎顺序地聚合来自数千节点的结果

结论：返回大量分组的聚合能从多级 serving tree 里获益。

再往下一层看每 tablet 的耗时直方图：计时从"tablet 被调度到某个可用 slot"开始，不含在作业队列里的等待 —— 这样能把其他并发查询的影响排除掉。 $Q_{2}$ （或 $Q_{3}$ ）有 99% 的 tablet 在一秒（或两秒）内处理完。

记录内聚合能省多少

$Q_{4}$ 在表 $T_{3}$ 上统计"记录内 a.b.c.d 之和大于 a.b.p.q.r 之和"的记录数，这些字段在不同的嵌套层级上重复：

sql

Q4: SELECT COUNT(c1 > c2) FROM (
      SELECT SUM(a.b.c.d) WITHIN RECORD AS c1,
             SUM(a.b.p.q.r) WITHIN RECORD AS c2
      FROM T3)

因为列条纹化，只从磁盘读了 13 GB —— 而 $T_{3}$ 总共 70 TB —— 查询 15 秒完成。 若不支持嵌套，这个查询在 $T_{3}$ 上会贵得离谱。

可扩展性

$Q_{5}$ 在 $T_{4}$ 上取 top-20 的 aid 及其出现次数，扫描 4.2 TB 压缩数据，用 1000 到 4000 节点四种配置：

sql

Q5: SELECT TOP(aid, 20), COUNT(*) FROM T4
     WHERE bid = {value1} AND cid = {value2}

每次运行消耗的总 CPU 时间几乎相同，约 30 万秒，而用户感知的时间随系统规模接近线性下降。这个结果的读法是：更大的系统在资源使用上可以和小系统一样有效，同时允许更快的执行。

掉队者

$Q_{6}$ 在万亿行的 $T_{5}$ 上跑。与别的数据集不同， $T_{5}$ 是两副本 —— 于是改派工作的机会更少，掉队者拖慢执行的可能性更高：

sql

Q6: SELECT COUNT(DISTINCT a) FROM T5

它读超过 1 TB 压缩数据，被检索字段的压缩比约 10。99% 的 tablet 每 tablet 每 slot 处理时间在 5 秒以内；但一小部分 tablet 慢得多，把查询响应时间从不到一分钟拖到好几分钟（2500 节点系统）。

观察小结

规模锚点先摆出来：Dremel 每月扫过的记录数达到千万亿条（quadrillions）；在典型月度负载里，大多数查询在 10 秒内处理完，稳稳落在交互式范围内；有些查询在共享集群上做到接近每秒 1000 亿条记录的扫描吞吐，在专用机器上更高。

八条观察：

基于扫描的查询可以在磁盘驻留、多达万亿条记录的数据集上以交互速度执行；
对数千节点的系统，在列数与 server 数上的近线性扩展是可以做到的；
MapReduce 能像 DBMS 一样从列式存储里获益；
记录装配与解析很贵 —— 查询处理层之外的软件层需要被优化到能直接消费列式数据；
MapReduce 与查询处理是互补的：一层的输出可以喂另一层的输入；
在多用户环境里，更大的系统既有规模经济，又给出质上更好的用户体验；
如果接受用速度换精度，查询可以提前很多就终止，却已经看到了大部分数据；
web 规模数据集的大部分能很快扫完；但要在一个紧的时间界内拿到最后几个百分点，很难。

最后一个规模指标：Dremel 的代码库很紧凑 —— 不到 10 万行 C++、Java、Python。

什么时候该用列式：一张判据表

列式与记录式的取舍在这套系统里被量过，把那些数字收成一张表，比记结论有用。

场景特征	选列式	选记录式
查询只引用少数列	是 —— 只读少数列时收益约一个数量级
查询要取完整记录		是 —— 装配开销会把列裁剪的收益吃掉
字段数很少（几十个以内）		是 —— 记录式开始优于列式的交叉点经验上落在"几十个字段"
字段数很多、访问很稀疏	是 —— 稀疏数据的收益最大
数据要逐条流式消费（管道、格式转换）		是 —— 回归记录形态的转换是纯开销
以聚合统计为主	是 —— 可以直接在 levels 上算，绕开装配
需要按行定位（取第 N 条、随机访问）		是 —— 这套格式没有索引层
数据极稀疏（schema 几千字段、只用到几百）	是 —— NULL 与未用字段几乎不占空间

四条判断规则比表更好记：

看"被引用的字段数 / 总字段数"这个比值。 比值越小，列式越占优 —— 因为省的正是"不必读的那些列"。
看下游能不能直接消费列。 这是最关键也最常被忽略的一条：链路的下一环如果只能吃完整记录，前一步的列裁剪就白做了。实测里"解析让执行时间翻倍"那一项，就是为下游的记录式接口付的。
看是否需要按行定位。 列式把"第几行"这个信息散到了各列里（靠 levels 重建），随机访问某一条记录要读的列数等于全部被引用列。
不要把磁盘占用当依据。 实测里记录式用了更重的压缩、磁盘占用与列式大致相同。列式的收益落在读取路径上，不落在存储上 —— 拿压缩率去论证列式的优势，方向一开始就错了。

一处补充的边界：列式并不排斥记录式，两者常常在同一套系统里分工。 扫一批宽表做聚合用列式，把结果喂给只认记录的下一环时只需在最后一步转换一次。要避免的是让这个转换在链路中间反复发生 —— 每多一次，前面省下的带宽收益就被抵掉一截。

格式的参数与可调项

Dremel 本身是 Google 内部系统，没有公开的配置文档页。所以这一节分两栏：模型层定下了哪些旋钮，以及这套列式嵌套格式在开源直系后代（Apache Parquet，用在 Spark 里）被具体化成什么参数与默认值。下面的默认值照录官方文档，不做推测。

模型层的旋钮，多数是"资源与完整性的交换"：

旋钮	影响什么	取值与默认
返回结果前必须扫过的 tablet 最小百分比	用数据完整性换响应时间	默认 100%；调到 98% 常能显著加速，副本因子小时尤其明显
slot 数	叶子 server 上的执行并发度	slot 就是叶子 server 的一个执行线程；3,000 server × 8 线程 = 24,000 slot
serving tree 的层数	多分组聚合时的合并成本	实测对比过 2 级、3 级、4 级
tablet 的大小与数量	调度粒度，以及故障时改派工作的余地	实测表含 10 万 ~ 80 万个 tablet
副本因子	掉队者与副本不可达时的应对余地	通常 3；实测里有张表是 2
levels 的位宽	每列元数据的大小	最大 definition level 为 3 时用 2 位
逐列的压缩与编码	磁盘占用与解压耗时	每列独立指定

Parquet 侧的参数（Spark 4.2.0 文档），挑与这套编码直接相关的几条：

参数	默认值	引入版本
`spark.sql.parquet.compression.codec`	`snappy`	1.1.1
`spark.sql.parquet.filterPushdown`	`true`	1.2.0
`spark.sql.parquet.int96AsTimestamp`	`true`	1.3.0
`spark.sql.parquet.mergeSchema`	`false`	1.5.0
`spark.sql.parquet.enableVectorizedReader`	`true`	2.0.0
`spark.sql.parquet.recordLevelFilter.enabled`	`false`	2.3.0
`spark.sql.parquet.outputTimestampType`	`INT96`	2.3.0
`spark.sql.parquet.columnarReaderBatchSize`	`4096`	2.4.0
`spark.sql.parquet.aggregatePushdown`	`false`	3.3.0
`spark.sql.parquet.enableNestedColumnVectorizedReader`	`true`	3.3.0

按六要素把其中三个摊开。

spark.sql.parquet.mergeSchema（默认 false） —— 语义是"是否把各 part-file 的 schema 合并起来读"。默认值是纯粹的性价比判断：官方写明 schema 合并是相对昂贵的操作、且多数场景并不需要，所以从 1.5.0 起默认关闭。改成 true 的后果是每种 schema 不一致的文件都能读出来（列增删后的历史文件可以一起读），代价是每次读都要扫全部 part-file 的 footer。联动的是 respectSummaryFiles：它为 true 时假定 part-file 与 summary file 一致、跳过合并，官方标注为"专家选项，不明白含义前不要开"。失败模式很隐蔽：读到的 schema 取决于抽中的那个文件，症状是"同一个目录、两次读出来的列数不同"。

spark.sql.parquet.enableNestedColumnVectorizedReader（默认 true） —— 语义是"对嵌套列（struct、list、map）也启用向量化解码"。这条默认值从"关"变成"开"花了很久：平铺列的向量化解码在 2.0.0 就默认开启了，嵌套列要到 3.3.0。原因就在这套 levels 编码上 —— 向量化要求"同一列的一批值能按固定步长批量取"，而嵌套列的每个值要带着自己的 repetition 与 definition level，两者的对齐比平铺列难得多。改成 false 的后果是嵌套列退回逐行解码，在"只读少量嵌套字段"的场景下退化明显。联动父开关 enableVectorizedReader（必须为 true 才生效）。

spark.sql.parquet.columnarReaderBatchSize（默认 4096） —— 语义是"一次向量化读取装多少行"。它是批量开销与内存占用之间的旋钮：调大能摊薄每次调用的固定开销，但单批占用的内存按比例上升。官方描述里直接点了"要小心选择以避免 OOM"。联动的是列数 —— 单批内存大致是"批大小 × 列宽 × 列数"，所以宽表上同一个 4096 会吃掉远多于窄表的内存。失败模式是调大之后出现 GC 压力或 OOM，而症状看起来像"查询变慢"。

一处值得对照的默认值：outputTimestampType 默认 INT96。INT96 在 Parquet 里是非标准类型，被 Hive 与 Impala 广泛使用；默认写非标准类型，图的是兼容遗留生态。默认值常常服务于兼容性，而不服务于最优 —— 这与 Pregel 那篇里"checkpoint 默认关闭"是同一类现象，读参数表时值得先分辨这一层。

版本演进：两个贡献各自长成了什么

Dremel 这篇真正留下的，是两个后来变成行业默认的做法：列式嵌套的编码方式与多级聚合的执行树。这两件事各自长成了一条独立的线。

第一条线：列式嵌套格式 → Apache Parquet。

Parquet 由 Twitter 与 Cloudera 的工程师在 2013 年合作发起，目标是"把压缩、列式表示的收益带给 Hadoop 生态里的任意项目"；2014 年 4 月进入 Apache 孵化器，2015 年 4 月毕业为顶级项目。它官方写明的技术来源是这套编码：

Parquet 从设计之初就以复杂嵌套数据结构为出发点，采用 Dremel 那套记录拆分与装配算法。这种做法比"把嵌套命名空间简单摊平"更合适。

这句话值得停一下，因为它正是本笔记前半部分那套 repetition / definition level 的直接继承声明 —— Parquet 不是"另一套列存"，它是同一套算法的开源实现。两处细节也继承了下来：压缩与编码按列独立指定；文件物理结构是 PAR1 魔数 + 若干 row group（每个含各列的 column chunk）+ 写在末尾的文件级元数据，元数据里带每列的统计量，于是能跳过不可能匹配的 row group（谓词下推）。

它的实现生态里有一条物证很说明问题：Parquet 的 C++ 实现是 Arrow C++ 的子项目，Go 与 Rust 实现同样是 Arrow 对应语言项目的子项目。格式与其内存表示被放在同一个组织下维护 —— 这正是下面第二条线在做的事。

第二条线：内存列式表示 → Apache Arrow。

Dremel 在观察小结里留了一句判断："记录装配与解析很贵 —— 查询处理层之外的软件层需要被优化到能直接消费列式数据。" Arrow 就是对这句话的回答：它把列式布局从磁盘带到内存，并做到跨语言零拷贝。时间线是 2016 年 2 月进 Apache 孵化器、2018 年 2 月毕业为顶级项目。磁盘上已经是列、内存里还是"逐行对象"，中间的装配开销就永远省不掉；Arrow 的作用是让这条链路上不再有"行"这个中间形态。

第三条线：向量化执行 —— 同一条观察的另一半。

"直接消费列式数据"落到执行层，就是向量化：一次处理一批值，而不是一次一行。这条线的进度可以用两个默认值量出来：

能力	默认开启的版本
平铺列的向量化解码	2.0.0
嵌套列的向量化解码	3.3.0
读取批大小	2.4.0 引入，默认 4096

嵌套列比平铺列晚了很久才默认开启，这件事本身就是"嵌套"这个难点没被彻底解决的证据 —— 而这套难点的源头，正是本笔记前面那套 levels 编码：向量化要按固定步长批量取值，而嵌套列的每个值都带着自己的 repetition 与 definition level。Dremel 用整数 levels 换来了表达力，留给后人的就是这里。

一条判断：Dremel 的系统形态（serving tree + 专用查询语言）没有被广泛复制，被复制的是它的两个中间产物 —— 编码方式成了文件格式标准，多层聚合成了查询引擎的通用形状。今天任何一个"用 Spark 读 Parquet 做聚合"的作业，都在同时用这两样东西。

两处时间线放在一起，能看出传播的次序：Parquet 2013 年发起，2014 年 4 月进孵化器，2015 年 4 月毕业为顶级项目；Arrow 2016 年 2 月进孵化器，2018 年 2 月毕业。磁盘格式先标准化，内存格式晚了三年 —— 顺序不是偶然：先把"数据怎么存"定下来，才会暴露"数据在内存里怎么摆"这个问题，因为存储层的统一恰好让跨系统的序列化开销变成了剩下的那块成本。

一条选型上的判断：今天这套链路上已经没有"要不要用列式"这个选项了 —— 列式嵌套格式是分析型数据的默认存法，列式内存表示是分析引擎之间的默认交换格式。能选的只剩编码与压缩、批大小、以及哪些环节允许回到行式 —— 而这三样恰好就是前面那张参数表上的内容。

还有一处继承关系值得点出：这套编码的后代不只停在文件格式上 —— 同一套"按列摆 + 带层级信息"的思路也进了内存表示（Arrow），以及表格式（把"一堆文件怎么当成一张表"的元数据从文件里挪出来单独一层）。三层叠起来就是今天的默认栈：文件格式管"一列的值怎么存"，内存格式管"一批值怎么传给下一个算子"，表格式管"一堆文件怎么当成一张表"。这套分层里最底层的位置，就是本笔记讲的那套 levels。

与相关工作的边界

与 MapReduce 一样，Dremel 提供容错执行、可表达嵌套的数据模型、以及原地数据处理。差别在取向：MapReduce 面向长时间运行的批处理作业，Dremel 强调两者互补而非替代。MapReduce 的成功带来了第三方实现（尤其是开源的 Hadoop），以及一批"并行 DBMS + MapReduce"的混合系统（Aster、Cloudera、Greenplum、Vertica 这些厂商的产品，HadoopDB 是其中的研究系统）。

两处它明确指出的空白：

哪怕是并行 DBMS，也没有公开发表的工作或行业报告尝试把它扩到数千节点；
也没有先前文献研究过"MapReduce + 列式存储"。

列式表示本身建立在几十年前的两个想法上：把结构与内容分离、用转置表示。与 XML 存储路线的比较值得记：XML 方案同样试图分离结构与内容，但因为 XML 数据模型自身的自由度而面临更多挑战；而 XMill 是个压缩工具 —— 它把结构对所有字段合并在一起存，不适于按列做选择性检索。

数据模型是复杂值模型与嵌套关系模型的一个变体。查询语言则建立在 1989 年的一项工作之上：那个语言在访问嵌套数据时避免重构；相比之下 XQuery 与面向对象查询语言通常需要重构（用嵌套 for 循环和构造器）。那项工作没有已知的实际实现。 其他可比的并行数据处理系统还有 Scope、DryadLINQ；Pig 是较近的一个作用于嵌套数据的类 SQL 语言。

排查：从症状到判据

这套系统的行为特征很集中：它读得多还是读得少，一眼能从"扫描量"上看出来；而慢的部分几乎总是落在调度与解码上，落在存储带宽上的情况反而少见。

症状	判据	先看什么	常见归因
扫描量远大于实际需要的列	读入字节数与"被引用字段的压缩大小之和"对不上	投影列表、分区条件	列裁剪或分区裁剪没生效（查询写了整行）
扫描量对，但耗时远高于按带宽估算的值	读 + 解压之后的耗时占比	各阶段耗时（读、解压、装配、解析）	解压或解码成为主项；压缩算法与数据分布不匹配
耗时随字段数线性上涨	被选字段数	投影列表	这是列式布局的固有性质，只能靠减少字段解决
只读少量列却没拿到收益	是否走了记录式路径	是否被迫做记录装配	下游工具只能消费记录，装配开销把列裁剪的收益吃掉了
结果偶发不完整	是否放宽了"必须扫过的 tablet 百分比"	该阈值的配置	阈值被调低（用完整性换速度）
响应时间被少数 tablet 拖长	每个 tablet 的耗时直方图	调度侧统计	掉队者；副本因子小则改派机会少
多级 tree 加层数没收益	返回结果的分组数	查询的分组基数	分组太少时多级合并没有用武之地
schema 读出来两次不一致	是否开了 schema 合并	该目录下的 part-file schema	schema 合并默认关闭，读到的是抽中的那一个
读取批次一调大就 OOM	单批占用的内存	批大小、列数	单批内存 ≈ 批大小 × 列宽 × 列数，宽表上更早撞墙

两条判读原则：

先分清"读得太多"与"算得太慢"。 两者的解法完全不同：读得太多要动查询写法（少投影、加过滤、按分区圈定范围），算得太慢要动执行层（批大小、向量化开关、解码路径）。判据是读入字节数 —— 这个量偏大就一定是前一类，它正常就一定是后一类。
看直方图，不看平均值。 调度侧的统计是逐 tablet 的耗时分布，而"响应时间"由最慢的那批 tablet 决定。平均值好看但尾部很长，就是掉队者问题的全部特征 —— 而它的解法是增加副本、缩短 tablet、或加大改派机会，与"提升平均处理速度"是两回事。

最后一条与前面接得上：这套系统对"最后几个百分点"很无力，而这正是它自己写下的第八条观察 —— web 规模的数据集大部分能很快扫完，但要在一个紧的时间界内拿到最后几个百分点，很难。排查时该问的是"慢的是主体还是尾部"，而不是"为什么慢"。

把排查收成一条主线：这套系统的性能问题几乎都能归到三个量上 —— 读了多少字节、解码花了多少时间、最慢的那批 tablet 有多慢。三个量对应三种动作，混在一起看就会绕圈。

量	从哪里看	偏大时改什么
读入字节数	扫描量对比被引用字段的压缩大小	查询写法：少投影、加过滤、按分区圈定范围
解码与装配耗时	读之后的各阶段耗时	编码与压缩的选择、批大小、是否走向量化路径
尾部 tablet 耗时	逐 tablet 的耗时直方图	副本因子、tablet 大小、改派机会

一条容易反向操作的判断：看到"扫描量已经很小、但查询还是不够快"，直觉会去调执行层的参数；更该先确认的是"下游是不是只能消费记录" —— 消费方要求完整记录时，装配开销会把列裁剪的收益重新吃掉，这时调参数治不好，要改的是输出形态。

还有一条与多用户环境相关的：这类系统通常同时跑着很多查询，所以"某次查询变慢"未必是它自己的问题。实测把计时起点定在"tablet 被调度到某个可用 slot 、不含在作业队列里的等待"，就是为了把其他并发查询的干扰排除掉。排查时照这个口径取数，才能分清"慢"是自己的还是排队的。

最后收一句关于"读得多还是算得慢"的分辨方法：这两类问题的分界线是**"用更少的列能不能更快"**。做法很直接 —— 把投影列表砍到只剩必需的字段再跑一次：耗时明显下降就是"读得太多"，耗时几乎不动就是"算得太慢"。这个实验只花一条查询的时间，却能把后面所有参数调整的方向定下来。

顺带一条与它配套的经验：这套系统的收益是按"字段数"而不是按"数据量"兑现的。同一张表，取三个字段和取三十个字段的差距，往往比"表大十倍"的差距还大。排查时先动投影，再动参数 —— 这是这套系统上最省事的次序。

参考

S. Melnik, A. Gubarev, J. J. Long, G. Romer, S. Shivakumar, M. Tolton, T. Vassilakis. Dremel: Interactive Analysis of Web-Scale Datasets. VLDB 2010.
Apache Parquet. Motivation 与 File Format. https://parquet.apache.org/docs/overview/motivation/ —— 用于核对格式的技术来源与物理结构
Apache Software Foundation. Apache Incubator Case Studies. https://cwiki.apache.org/confluence/display/INCUBATOR/ —— 用于核对 Parquet 与 Arrow 进入孵化器与毕业为顶级项目的时间
Apache Spark. Parquet Files（Spark 4.2.0 文档）. https://spark.apache.org/docs/latest/sql-data-sources-parquet.html —— 用于核对 Parquet 各配置项的默认值与引入版本

贡献者

文件历史

最后编辑于 1 天前查看完整历史

语法基础

gpu

cuda

train

infer

Dremel

为什么需要它：交互式响应与原地数据

数据模型：强类型嵌套记录

嵌套列存：三个挑战

repetition level 与 definition level

编码形态

把记录拆成列

记录装配：一台有限状态机

底层依赖：编码、压缩与存储层

查询语言

查询语言的三个取向

查询执行

serving tree 与查询重写

query dispatcher：调度、容错、掉队者

服务器内部

一个聚合查询从收到到返回

实测

本地磁盘：列式 vs 记录式

MapReduce 与 Dremel 的对照

serving tree 的层数：多分组聚合才吃这一层

记录内聚合能省多少

可扩展性

掉队者

观察小结

什么时候该用列式：一张判据表

格式的参数与可调项

版本演进：两个贡献各自长成了什么

与相关工作的边界

排查：从症状到判据

相关

参考

贡献者

文件历史

Dremel ​

为什么需要它：交互式响应与原地数据 ​

数据模型：强类型嵌套记录 ​

嵌套列存：三个挑战 ​

repetition level 与 definition level ​

编码形态 ​

把记录拆成列 ​

记录装配：一台有限状态机 ​

底层依赖：编码、压缩与存储层 ​

查询语言 ​

查询语言的三个取向 ​

查询执行 ​

serving tree 与查询重写 ​

query dispatcher：调度、容错、掉队者 ​

服务器内部 ​

一个聚合查询从收到到返回 ​

实测 ​

本地磁盘：列式 vs 记录式 ​

MapReduce 与 Dremel 的对照 ​

serving tree 的层数：多分组聚合才吃这一层 ​

记录内聚合能省多少 ​

可扩展性 ​

掉队者 ​

观察小结 ​

什么时候该用列式：一张判据表 ​

格式的参数与可调项 ​

版本演进：两个贡献各自长成了什么 ​

与相关工作的边界 ​

排查：从症状到判据 ​

相关 ​

参考 ​

贡献者 ​

文件历史 ​

Dremel

为什么需要它：交互式响应与原地数据

数据模型：强类型嵌套记录

嵌套列存：三个挑战

repetition level 与 definition level

编码形态

把记录拆成列

记录装配：一台有限状态机

底层依赖：编码、压缩与存储层

查询语言

查询语言的三个取向

查询执行

serving tree 与查询重写

query dispatcher：调度、容错、掉队者

服务器内部

一个聚合查询从收到到返回

实测

本地磁盘：列式 vs 记录式

MapReduce 与 Dremel 的对照

serving tree 的层数：多分组聚合才吃这一层

记录内聚合能省多少

可扩展性

掉队者

观察小结

什么时候该用列式：一张判据表

格式的参数与可调项

版本演进：两个贡献各自长成了什么

与相关工作的边界

排查：从症状到判据

相关

参考

贡献者

文件历史