原文：Geoff Langdale, Daniel Lemire. Parsing Gigabytes of JSON per Second. arXiv:1902.08318v7 [cs.DB], 2024 年 7 月 23 日版。

本文是原文的中文翻译，保留了原 paper 的章节编号、图、表与脚注。原文作者单位：branchfree.org（澳大利亚）与 Université du Québec (TELUQ)（加拿大魁北克大学）。

原文：Viktor Leis, Peter Boncz, Alfons Kemper, Thomas Neumann. Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age. SIGMOD 2014, pp. 743–754.

本文是原文的中文翻译，保留了原 paper 的章节编号、图、表与脚注。原文作者单位：Technische Universität München（慕尼黑工业大学）与 CWI（荷兰数学与计算机科学研究基础研究所）。

摘要

随着现代计算机架构的演进，两个问题共同阻碍了并行查询执行的前沿方法：(i) 为了利用多核，所有查询工作必须均匀地分配到（很快会是）数百个线程上才能获得好的加速比，然而 (ii) 即使拥有准确的数据统计信息，由于现代乱序执行核心的复杂性，把工作均匀地划分也依然很困难。结果是，现有的"plan-driven（计划驱动）“并行方法撞上了负载均衡和上下文切换的瓶颈，因此不再具备可扩展性。多核架构面临的第三个问题是内存控制器的去中心化，这导致了非一致性内存访问（NUMA）。

对此，我们提出"morsel-driven（小块驱动）“查询执行框架，其中调度成为一个细粒度的、NUMA 感知的运行时任务。Morsel-driven 查询处理取输入数据的小片段（“morsels”），把它们调度给 worker 线程，由 worker 线程执行完整的算子流水线直到下一个 pipeline breaker。并行度不是被烘焙进计划里，而是在查询执行过程中可以弹性地改变，因此 dispatcher（调度器）能够对不同 morsel 的执行速度做出反应，也能根据工作负载中新到达的查询动态调整资源。此外，dispatcher 还感知 NUMA 本地 morsel 和算子状态的数据局部性，使得绝大部分执行都发生在 NUMA 本地内存上。我们在 TPC-H 和 SSB 基准上的评估显示出极高的绝对性能，以及在 32 核上超过 30 的平均加速比。

关键词：Morsel-driven parallelism；NUMA-awareness

原文：Jeff Shute, Radek Vingralek, Bart Samwel, Ben Handy, Chad Whipkey, Eric Rollins, Mircea Oancea, Kyle Littlefield, David Menestrina, Stephan Ellner, John Cieslewicz, Ian Rae, Traian Stancescu, Himani Apte. F1: A Distributed SQL Database That Scales. VLDB 2013.

摘要

F1 是 Google 构建的一套分布式关系型数据库，用于支撑 AdWords 业务。F1 是一种混合型数据库，同时具备高可用性、Bigtable 这类 NoSQL 系统的可扩展性，以及传统 SQL 数据库的一致性和易用性。F1 构建在 Spanner 之上，Spanner 提供了跨数据中心的同步复制与强一致性。同步复制意味着更高的 commit 延迟，但 F1 通过带结构化数据类型的层次化 schema 模型以及合理的应用设计缓解了这种延迟。F1 还包含一套功能完整的分布式 SQL 查询引擎，以及自动的变更追踪和发布机制。最近的若干出版物曾断言这些设计目标相互排斥 ⁵, ¹¹, ²³。本文的一个关键贡献就是展示我们如何在 F1 的设计中同时达成所有这些目标，以及我们在何处做了取舍与牺牲。

为什么值得单独讲

Hash 表的性能通常取决于两件事：冲突发生后如何找下一个候选位置，以及这些候选位置离缓存有多远。传统链式哈希把冲突元素串成链表，逻辑简单，但一次查询可能要跳过多个指针；普通开放寻址没有指针跳跃，却常常只能逐个 slot 检查。

Swiss Table 的核心贡献是在开放寻址表前面加了一层非常小的元数据，让 CPU 能按 group 批量排除大量不可能匹配的 slot。它不改变 hash 表的基本语义，而是改变查找、插入、删除时的观察方式：先用极小的哈希指纹过滤，再对少数候选 key 做精确比较。

这个设计来自 Google 的工程实践，后来成为 Abseil flat_hash_map 的底层实现，也被 Rust 标准库 HashMap 采用。Go 1.24 之后，内置 map 的默认运行时实现也切换到了 Swiss Table 风格。

百分位数是描述数据分布最常用的指标之一:P95、P99 告诉你接口长尾延迟,中位数告诉你"典型"水平。SQL 标准为精确计算提供了 PERCENTILE_CONT 和 PERCENTILE_DISC,大数据引擎则普遍内置了以 sketch 为核心的近似算法。本文从原理出发介绍这些函数与算法,给出每种算法的伪代码,并配上可以手算验证的例子。

一、从一个常见但反直觉的现象说起

你可能听过这样的话：“网线明明是千兆的，为什么下载速度总是上不去？”

或者更具体一点：你用 speedtest 测速，自己买的 200M 宽带，下行只能跑到 80M；公司升级到 10G 专线，看 YouTube 4K 仍然时不时卡顿。

很多人第一反应是"运营商限速"或"网站服务器不行"。但如果你是做后端的、或者管过一段广域网链路，会知道罪魁祸首往往不是带宽不够，而是 TCP 的拥塞控制策略本身。

一、从一个常见的运维难题说起

假设你正在运营一个分布式限流系统，全公司上百个服务都要经过你分配的"带宽配额"。预算就这么多，但每个服务的真实需求你事先不清楚——有的服务平时风平浪静，促销时流量能翻 10 倍；有的服务每月稳定增长 30%。

你会怎么分配这些带宽？

• 分配固定配额：结果几乎是灾难——资源浪费和争抢同时发生。
• 让业务方报需求：这种"自报家门"在 KPI 面前几乎一定会虚报，最后仍然会把系统打爆。
• 让业务方主动试：先少申请一点，发现不够再加。这种"摸着石头过河"的思路，恰恰是 TCP 拥塞控制的核心。

30 多年前，Van Jacobson 在设计 TCP 拥塞控制时面对的是同一个问题：网络（链路）的带宽是共享资源，发送方不知道链路的当前容量，也不知道有多少其他发送方在抢资源。他必须设计一个让所有发送方在不知道对方存在的情况下，依然能公平、高效地共享链路的算法。

如果你写过监控告警、自适应限流或者负载均衡，大概率遇到过这个问题：怎么用一个数值，实时地描述"当前系统有多慢"？EWMA（Exponentially Weighted Moving Average，指数加权移动平均）几乎是工程实践里的标准答案——它只需要一个 float 的内存，一行加法就能更新，却能给出比简单平均更贴近"当下"的估计。

一、从一个常见的运维难题说起

先抛个场景：某个核心服务运行了一段时间后，运维同学收到告警——Full GC 次数突然飙高。登录机器一看，Metaspace 使用率长期维持在 90% 以上，老年代被反复撑爆。

按照经验，第一反应是加大 -XX:MetaspaceSize。但问题是：加大到多少合适？ 设 256M，下次告警；设 512M，内存浪费严重；设 1G，业务方立刻投诉资源利用率低。

先看一段栈，再决定要不要继续读——

# 这两份 stack dump 间隔 14 分钟抓的，"jdbc:mysql://10.14.127.31:19030/xxx"
# 的 connection adder 线程，tid 完全一致，栈帧一帧没动。
# 业务侧呢？告警群里全是 SQLTransientConnectionException。

说真的，这种栈谁都不想看到——10 个 HikariCP 连接池、每个池的 adder 都卡在 socketRead0，不是忙，是死等。更扎心的是，业务方第一时间甩锅 HikariCP “卡死了”，但 HikariCP 的 MAIN 池好好的；另一边 DBA 看到 MySQL 进程没崩、SHOW PROCESSLIST 也查不出明显异常。两边都没事，问题到底出在哪？