Übung macht den Meister

【读】Pinot: Realtime OLAP for 530 Million Users

Posted on 2025-03-02 Word count in article: 7.5k Reading time ≈ 13 mins.

介绍

作者对大数据时代下近实时的 OLAP 服务提出了如下要求：

高性能：系统应当能够快速的返回用户的查询请求
可扩展性：为了能够在处理大量并发查询请求的同时做到近实时的消费大量数据，系统应当提供近线性的扩展性和容错性来满足大规模的服务部署
低成本：随着数据容量以及查询并发量的增加，系统的成本不能无限制的增长
低延迟的实时数据消费：用户期望能够近实时的查询到刚添加到系统中的数据
灵活性：系统应当能够支持用户查询时下钻到任意维度，而不受限于预聚合的数据；同时，系统也能够以零停机的方式在生产环境增加新的查询模式
容错性：系统异常时能够提供优雅的服务降级
非中断式运维：系统能够以零停机的方式进行服务升级或者表结构变更
云服务友好的架构：系统应当能够轻易的部署到商用的云服务环境中

架构

Pinot 诞生于 LinkedIn，作为一款可扩展的分布式 OLAP 数据库，能够提供低延迟的实时数据分析。Pinot 构建在不可变的追加式数据存储之上，专门为数据分析查询场景作了优化，数据自开始接入到可被查询仅需几秒。

在 LinkedIn 内部，业务数据会先接入到 Kafka 中，然后经过 ETL 处理存储到 HDFS。Pinot 既支持近实时的从 Kafka 中消费数据，也支持从类似 Hadoop 的离线系统中导入数据。因此，Pinot 遵循 lambda 架构，能够自动合并从 Kafka 接入的流式数据和 Hadoop 导入的离线数据。

数据和查询模型

和常见的数据库一样，Pinot 也以表的方式管理数据，每个表背后由 schema 定义了有哪些列。支持的数据类型包括不同长度的整型，浮点数，字符串，布尔值，以及基于这些数据类型的数组。Pinot 中的列即可以是 dimension，也可以是 metric。

Pinot 还支持一个特殊的时间列，一方面在查询时基于该列合并流式数据和离线数据，另一方面作为数据过期判断的依据。

Pinot 的表以 segment 为单位存储，每个 segment 一般能存储几千万条记录，一张表能支持几万个 segment。segment 可以有副本，从而确保数据的高可用性。segment 中的数据是不可修改的，但是可以整个替换 segment 来更新数据（数据更新代价较大）。

segment 采用列存储保存数据，并支持多种编码策略来减少单个 segment 的大小。一个 segment 的大小一般在几百 MB 到几 GB 不等。下图展示了 segment 的数据存储方式：

alt

Pinot 的查询语言为 PQL，是 SQL 的子集，支持 select，projection，aggregation，和 top-n 查询，不过不支持连接和嵌套查询。PQL 不支持单条记录级别的创建，更新或者删除。

组件

Pinot 有四个主要的组件用于数据存储，数据管理和查询：

controller
broker
server
minion

除此之外，Pinot 还依赖 Zookeeper 和持久化的对象存储。Pinot 借助 Apache Helix 来管理集群，Apache Helix 是一个通用的集群管理框架，用于管理分布式系统内的分区和副本。

server 主要负责存储 segment 并处理针对所负责的 segment 的查询请求。每个 segment 在 UNIX 的文件系统上对应一个目录，目录中保存了 segment 的元数据和索引文件。segment 的元数据保存了列的信息，包括类型，cardinality，编码，各式各样的统计信息，以及支持的索引。索引文件保存了每列的索引。索引文件只能追加写入，从而支持按需创建倒排索引（inverted index）。server 可插拔的架构支持从多种不同的存储格式加载列索引，以及在于运行时生成衍生列（synthetic column）。同时也能轻易的扩展从类似 HDFS 或者 S3 这样的分布式存储系统读取数据。Pinot 会维护一个 segment 的多个副本，并且所有副本都会参与查询。

controller 负责管理 segment 到 server 的分配。controller 会根据运维需求或者 server 的可用性动态更新 segment 的分配。另外，controller 还负责一系列管理任务，例如查询所有可用的表、segment，添加或者删除表、segment。Pinot 的表可以设置过期时间，超过过期时间的 segment 会被 controller 删除。segment 的所有元数据及 segment 到 server 的映射都由 Apache Helix 管理。出于容错性的考虑，LinkedIn 一般会在每个数据中心部署三个 controller 实例，其中一个作为主节点，由 Apache Helix 管理，非主节点在大多数时间里是空闲的。

broker 负责处理查询请求，它首先将查询分发到负责的各个 server 上，然后合并各个 server 的查询结果，最后返回给客户端。客户端通过 HTTP 和 broker 交互，所以可以前置负载均衡器来分摊各个 broker 的压力。

minion 负责运行一些计算密集型的任务，其任务由 controller 的调度器分配。另外，任务管理和调度支持扩展添加新的任务和调度类型以支持变化的业务需求。minion 的其中一个应用场景是数据清洗，出于数据合规的要求，LinkedIn 有时候需要清理特定成员的数据。由于 Pinot 数据的不可变性，minion 运行时需要先下载 segment，然后清洗数据，接着重新生成 segment 以及重建索引，最后上传 segment 到 controller 覆盖旧的 segment。

Zookeeper 用于持久化存储元数据，并作为集群中各节点间通信的渠道。集群的状态，segment 的分配，以及元数据都通过 Helix 保存在 Zookeeper 中。segment 本身保存在持久化的对象存储中。在 LinkedIn 内部，Pinot 使用本地的 NFS 作为数据存储层，而运行在 LinkedIn 数据中心之外则借助 Azure Disk。

下图是 Pinot 的架构图：
alt

常见操作

加载 segment

Helix 借助状态机来描绘集群的状态，集群中的每个资源都有当前的状态以及期望的状态。当状态发生变更时，对应的节点就会执行状态变更流程。

下图展示了 segment 的状态流转：

alt

segment 的初始状态为 OFFLINE，然后 Helix 会要求 server 执行 segment 从 OFFLINE 到 ONLINE 的状态迁移。server 首先会从对象存储拉取 segment，解压然后加载，完成后就可以服务查询请求，此时 segment 在 Helix 中的状态为 ONLINE。

对于还在消费 Kafka 的 segment，Helix 会要求 server 执行 segment 从 OFFLINE 到 CONSUMING 的状态迁移。server 会从指定的 Kafka 分区的 offset 开始创建消费者，所有的副本也同时从这个 offset 开始消费。

下图展示了 segment 的加载过程：

alt

更新路由表

每当 server 加载或者卸载 segment，Helix 都会更新集群的状态。broker 会监听集群状态的变更，并更新 server 到可用 segment 的路由表映射。这就确保 broker 能将查询请求正确的路由到可用的 server 上。

查询

当 broker 收到查询请求后，会执行以下步骤：

解析查询并优化
随机选择被查询表的路由表
broker 将查询发送给路由表中的所有 server，各个 server 会各自查询本地的 segment
server 根据可用的索引和列的元数据生成逻辑和物理查询计划
server 会调度执行查询计划
当所有查询计划执行完成后，server 会合并各个查询计划的结果，然后返回给 broker
当 broker 收到所有 server 的查询结果后，broker 会合并结果。如果某些 server 的查询出现了错误或者超时，那么该次查询会被标记为不完整，客户端就可以决定是否展示不完整的数据给用户还是之后重新提交查询
broker 返回查询结果给客户端

Pinot 会自动合并来自实时和离线的数据。如下图所示，该表每天生成两个 segment，实时数据和离线数据在8月1号和8月2号存在重合，当 Pinot 收到一个覆盖这段时间范围的查询时，会将其改写为两个查询，一个负责查询离线数据，其查询时间范围在8月2号之前，另一个负责查询实时数据，其查询时间范围在8月2号及其之后。

alt

这也正是为什么 Pinot 的表需要一个时间列的原因。

`server` 如何执行查询

server 收到查询后，会生成逻辑和物理查询计划。因为每个 segment 中可用的索引和物理数据组织方式有可能不同，因此查询计划的粒度是 segment。这使得 Pinot 能够根据某些特殊场景做针对性的优化，例如判断 segment 中的值是否匹配某个查询条件。另外，Pinot 也会根据 segment 的元数据生成某些特殊的查询计划，例如查询 segment 中某列的最大值。

Pinot 会根据预估的执行代价选择物理算子（physical operator），并根据每一列的统计信息对物理算子重排序从而降低查询的整体成本。之后 Pinot 会将查询计划提交给查询执行器，然后并行处理。

下图展示了查询计划生成的过程：

alt

上传数据

用户可以通过 HTTP POST 将 segment 上传给 controller。当 controller 收到 segment 后，首先会先将其解压，并检查数据的完整性，并确保新添加的 segment 的大小不会造成表的配额超出限制，然后将 segment 的元数据写入 Zookeeper 中，最后触发 segment 的状态变更为 ONLINE 并分配给合适的副本节点，从而将集群更新至期望的状态，各 server 就可以执行 segment 的加载流程。

下图展示了这一过程：

alt

完结实时 segment

对于从 Kafka 接入实时数据的场景，每个副本都是独立的以相同的起始 offset 开始消费 Kafka 中的数据，并以相同的条件停止消费。当正在消费的 segment 结束消费时，server 会将其持久化到磁盘并提交给 controller。因为 Kafka 本身也有数据的过期策略，因此 Pinot 支持按照已消费的数据的条数或者所经过的时间来提交一个 segment。

对于按照已消费的数据的条数来提交 segment 的场景，只要各副本都从相同的 Kafka 分区的 offset 开始消费，以及消费相同的数据条数，则生成的 segment 一定是相同的。不过，根据经过的时间来提交 segment 的场景，则可能因为各副本的本地时钟不同而造成生成的 segment 不一致。因此，Pinot 实现了一套 segment 完结协议来确保所有副本对最终生成的 segment 达成共识。

当一个 segment 准备完结时，server 会将其目前所在的 Kafka 分区的 offset 发给 controller，并要求 controller 下发进一步的指令。controller 返回给 server 的指令可能有：

等待：什么也不做，过段时间再继续询问 controller
丢弃：丢弃当前的 segment，并从 controller 拉取替代的 segment；这个发生的情况在于有其他副本已经提交了另一个版本的 segment
追赶：server 会继续消费直到 controller 指定的 offset，然后再次询问 controller
保持：将当前 segment 刷新到磁盘并加载；这个发生的情况在于有其他副本已经提交了一个完全一样的 segment
提交：将当前 segment 刷新到磁盘并尝试提交；如果提交失败，则继续尝试询问 controller，否则加载 segment
非主节点：当前 controller 不是主节点，需要 server 重新询问真正的主节点

server 询问 controller 的回复同样由状态机实现，controller 会等待直到足够数量的副本已经和 controller 进行了通信，或者距离第一次询问已经过去了足够的时间能够决定哪个副本能够提交 segment。controller 状态机会要求各个副本消费到所有副本中已消费的最大 Kafka 分区的 offset，然后让消费到最新 offset 的副本提交 segment。如果当前 controller 发生异常，则新的主节点会发起一个全新的状态机，接着继续上述的操作，所以这会暂缓 segment 的提交，不过对正确性没有影响。

这个策略减少了网络的传输并确保当 segment 被提交时，所有副本都有相同的数据。

云计算友好的架构

Pinot 的设计专门为在云计算环境中运行而优化。商用的云服务提供商为 Pinot 的执行提供了两个重要的条件：配有本地临时存储的计算实例，以及持久化的对象存储系统。

因此，Pinot 被设计为 share-nothing 的架构，各实例都是无状态的。所有持久化的数据都存储在对象存储，所有的系统元数据都存储在 Zookeeper 中；本地磁盘仅作为缓存使用，当实例重启时，所有数据都会从对象存储或者 Kafka 重新读取。因此，可以随时删除一个节点并替换，而不会影响集群的正常运行。

另外，所有面向用户的操作都通过 HTTP 完成，使得用户可以自行选择适合的负载均衡器。

扩展 Pinot

查询执行

Pinot 的查询执行模型被设计为可以扩展支持新的算子以及新的查询类型。例如，Pinot 的最初版本不支持 SELECT COUNT(*) 这样的查询，为了支持该查询则需要修改查询计划器，以及添加新的基于元数据的物理算子，不过不会涉及任何架构上的修改。

Pinot 的物理算子针对每一种数据形式都进行了专门处理；每一种数据编码都有对应的算子，从而能灵活的针对查询优化添加新的索引类型和特定的数据结构。Pinot 可以动态的由 server 或者 minion 重建 segment 内的索引，从而能动态的部署新的索引类型和编码，并且用户不会感知。

索引和物理数据存储

类似 Druid，Pinot 也支持基于位图的倒排索引。不过，如果能在存储数据时按照主列和二级列排序，则可以支持某些场景下更高效的查询。

例如，LinkedIn 网站上有个功能叫做“谁看了我的档案“，所有相关的查询都涉及到根据 vieweeId 列过滤。如果将数据按照 vieweeId 列排序，那么对于任意一个相关的查询，只需要扫描连续的一部分数据即可，因此 Pinot 可以只保存每一个 vieweeId 的起始和终止位置。这种数据的相邻特性也使得使用向量查询成为了可能。

因此，当创建物理过滤算子时，会先应用执行在已排序的列上，然后将过滤后的数据起始范围传递给后续的算子。后续的算子只需要扫描少部分的数据，从而提高了查询性能。

Iceberg 查询

Iceberg 查询是数据库查询的一个重要使用场景，它用于查询数据集中满足条件的一部分数据，然后进行聚合计算（如 sum，max，min）。例如，如果想知道哪个国家的人访问某个页面最多，只需要先查询出访问次数大于某个最小阈值的国家即可，然后就能回答谁访问最多这个问题。这特别适合分析数据有长尾分布的场景，并且查询只关注某些关键的指标。

Pinot 实现了 star-tree 索引对 iceberg 查询进行了优化。star-tree 包含了一系列预聚合的记录节点，树的每一层包含满足了 iceberg 的查询条件的某个维度的节点，以及表示这一层所有数据的 star-node。遍历树就等同于执行多个过滤条件的查询。下图展示了 star-tree 的两个例子：

alt

查询路由和分区

Pinot 对于未分区的表会事先生成一个路由表，用于 server 到 segment 的映射，并支持多种路由策略。默认的路由策略是平衡策略（balanced strategy），它将 segment 均匀的分配给 server。当查询到达时，所有的 server 都会收到查询请求并查询对应的 segment。

平衡策略适合于中小规模的集群，不过不适用于大型集群。因为集群越大，出现异常节点的概率也越高，从而由于异常节点拖慢一次查询。因此，Pinot 针对大型集群实现了另一种策略，从而尽量减少单词查询需要通信的 server 的数量。

Pinot 同时也支持对表按照某个分区函数进行分区。对于分区表，Pinot 不会生成路由表，而是根据查询条件将请求路由到持有特定 segment 的 server。另一方面，Pinot 的分区函数也会和 Kafka 的分区函数行为保持一致，从而确保 Pinot 的离线数据也能和实时数据一样按照相同的分区方式分区。

多租户

对于大型公司来说，如果给每一个应用场景创建一个 Pinot 集群则过于昂贵和难以维护。因此，多租户的支持就尤为重要。为了避免某个租户的查询请求占用另一个租户的资源，Pinot 会给每个租户分配令牌桶（token bucket）。每个查询请求都会根据实际查询的耗时来按比例的消耗令牌，当令牌不足时，查询就会被放入队列中等待。令牌桶会随着时间推移缓慢恢复，一方面满足了瞬时的查询高峰，另一方面也避免了某个租户的查询耗尽另一个租户的资源。

产线中的 Pinot

在 LinkedIn 的产线中，Pinot 运行在超过3000台分布在不同地理位置的服务器上，维护了超过1500张表，对应超过100万个 segment。压缩后的数据大小将近30 TB（未计算副本数据的大小）。各数据中心每秒共处理超过50000次查询。

应用场景类型

LinkedIn 的 Pinot 的使用场景主要分为两类：

高吞吐，简单的查询
低频，复杂的查询或者涉及数据量巨大

对于第一种场景，要求数据尽量在内存中缓存从而能提供每秒几万的查询，这类查询的查询模式一般不多。

对于第二种场景，一般数据都在磁盘上，由于其低频的查询，因此可以按需加载数据。虽然这类查询频率较低，但是有可能会有瞬时的大量查询，比如用户在访问某个报表页面。对于这种情况，实现资源的多租户共享就显得尤为重要，从而实现最小化硬件资源的占用，避免资源在长时间内处于空闲状态。

运维考量

为了减轻运维的压力，LinkedIn 在设计 Pinot 时就考虑到了尽可能的将 Pinot 设计为能够让用户自助运维的系统。

例如，可以随时修改表的结构来添加新的字段而不需要停机。当 schema 添加了新的列时，Pinot 会在几分钟内给所有已有的 segment 以某个默认值添加该列。同时，Pinot 的运维团队也在持续收集查询日志和执行统计信息，从而能自动的为某些列添加倒排索引以提高查询性能。

不过，在多个数据中心之间和环境（测试和生产环境）之间复制表配置成为了一个问题。目前的解决方案是将表配置保存在源代码控制软件内，然后通过 Pinot 的 REST 接口进行同步。这样做的好处在于能够追踪所有配置的变化，以及提供搜索，验证，代码审查等功能。

参考

Pinot: Realtime OLAP for 530 Million Users

【读】The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing

Posted on 2025-02-27 Word count in article: 9.7k Reading time ≈ 16 mins.

介绍

面对日益增长的大规模无界、无序数据的处理需求，当前的技术手段存在诸多不足：

以 MapRecue 为代表的批处理系统无法满足数据处理的及时性要求，因为需要先收集所有的数据，然后再处理
很多流式系统对于大规模处理下的容错性缺少明确的保证
能够提供大规模处理和容错性的系统又缺少表达性和正确性
很多系统也缺少 exactly-once 语义保证，从而影响正确性
缺少对窗口（windowing）计算的支持或支持有限
某些支持基于事件时间（event-time）的窗口计算的系统要么要求事件必须有序，要么窗口触发语义不够丰富
缺少高层次的编程模型能够直观的支持基于事件时间的会话（session）
虽然 Lambda 架构能够解决大部分的问题，但是需要同时构建和维护两套系统，增加了成本

当前已有系统的主要问题在于认为数据是有界的，这个假设对当下海量且无序的数据处理的需求是不成立的；另外，需要一个简单但又强大的工具在满足上述场景的同时，又能在正确性，延迟和成本之间取得平衡；最后，需要转变由执行引擎决定系统语义的思想，不管是批处理，微批处理，还是流式处理，只要经过了合理的设计和实现，都能提供同等水平的正确性保证，而这三种执行引擎如今都广泛用于处理无界的数据。因此，在正确性保证的前提下，选择不同的执行引擎的决定因素就在于延迟和资源成本。

本文提出了一个统一的数据处理模型：

对无界，无序的数据，能够根据事件本身的维度特征进行窗口聚合，并按照事件时间排序计算，并且在正确性，延迟，和成本之间灵活调优
将 pipeline 的实现拆解为四个维度，以提供清晰性，可组合性和灵活性：
- What：计算的结果是什么
- Where：参与计算的事件时间
- When：数据处理时间
- How：先前的计算结果如何与后续优化关联
将数据处理的逻辑概念与底层物理实现剥离，对于批处理，微批处理，和流式处理的选择，取决于用户对正确性，延迟，和成本的考量

具体来说，本文的主要贡献在于提出了：

窗口模型：支持非对齐的事件时间窗口，并提供简单的 API 用于创建和使用窗口
触发模型：将数据处理结果的输出时机与 pipeline 的运行时特征相绑定，并提供了强大和灵活的声明式 API 来描述触发的语义
增量式的处理模型：集成窗口模型和触发模型，支持计算的撤销和更新
可扩展的实现：既支持流式处理引擎（MillWheel），也支持批处理引擎（FlumeJava），以及对 Google Cloud Dataflow 的外部二次实现，并提供了运行时无关的开源 SDK
一系列指导本文描述的模型设计的核心准则
Google 产线环境下大规模无界，无序数据处理的真实案例探讨，正是这些真实需求驱动了本文描述的模型的开发

无界/有界与流式/批

相比于流式/批，本文倾向于使用无界/有界来描述无限/有限的数据集，因为前者可能暗示使用了特定的执行引擎。实际上，无界的数据同样可以用连续运行的批处理引擎处理，而设计合理的流式处理引擎同样可以处理有界的数据。

窗口

窗口将一个数据集划分为有限个数的组。在处理无界数据时，窗口对于某些操作是必须的（如聚合，外连接，以时间为界的操作），而对于其他操作（如过滤，映射，内连接）则不是必须的。对于有界数据来说，窗口是可选的，不过依然在很多场景下适用（如对已经处理过的无界数据的一部分进行大批量的更新，即 backfill）。窗口始终是基于时间的，虽然某些系统支持基于元组的窗口，不过这依然是基于时间的窗口，其中有序的元素隐含着对应递增的逻辑时间。窗口分为对齐和非对齐，前者窗口的边界与特定的时间间隔同步，后者不同的窗口可以在不同的时间开始和结束。

固定窗口

alt

也称为滚动窗口（tumbling window），每个窗口都是固定的大小，且彼此之间没有重叠，通常都是对齐的，例如，每小时生成大小为1小时的窗口：

窗口1：[12:00, 13:00)
窗口2：[13:00, 14:00)
窗口3：[14:00, 15:00)
…

不过，有时候为了保证窗口对齐，会将窗口按照键以某个随机值进行偏移。

滑动窗口

alt

滑动窗口由窗口大小和滑动周期构成，例如，每分钟生成大小为1小时的窗口：

窗口1：[12:00, 13:00)
窗口2：[12:01, 13:01)
窗口3：[12:02, 13:02)
…

滑动周期可能会小于窗口大小，所以相邻两个窗口之间有重叠，当滑动周期等于窗口大小的时候，滑动窗口就退化成了滚动窗口。滑动窗口一般也是对齐的。

会话窗口

alt

会话窗口用于框住某段时间内产生的数据子集，其大小一般以超时时间来衡量，在该超时时间内发生的事件都会归于该会话窗口。会话窗口一般是非对齐的。

时间

数据处理中有两类时间：

事件时间：事件实际发生的时间
处理时间：事件被系统观测到并处理的时间

一般来说事件时间一旦生成后就不会改变，而处理时间则随着事件在系统中流动而不断变化。理想情况下，如果分别对事件时间和处理时间画一条线，那么这两条线是重合的。不过在实际中，由于通信延迟，调度算法，处理单个事件需要的耗时，以及 pipeline 的序列化等因素，事件时间与处理时间之间存在偏差（如下图所示）。本文使用类似于 MillWheel 的 watermark 来表示这种偏差，watermark 定义了事件时间的一个下界，表示所有事件时间小于 watermark 的事件都已经处理完毕。不过，这依然是个理想情况，为了容忍一定程度的事件到达系统的延迟，watermark 会滞后于最新的事件时间，而这个容忍时间又不可能无限长，所以实际中即使生成 watermark 后也依然有可能存在事件时间比 watermark 小的事件到达系统，这些事件称为 late event。

alt

Dataflow 模型

核心原语

在批处理下，Dataflow SDK 提供了操作 (key, value) 键值对的两种方式：

ParDo：对每个输入，通过调用用户定义的方法（在 Dataflow 中称为 DoFn），返回0个或者多个输出，各输入之间无关联，天然的适用于无界数据处理
GroupByKey：将相同键的值聚合在一起，不过对于无界数据来说，何时将相同键聚合后的数据发给下游成为了一个问题，因为无法预知数据的边界，通用的解决方法是借助窗口

以下是一个 ParDo 的例子，对于每个输入，通过调用 ExpandPrefixes 方法，返回每个键的所有可能的前缀：

(\text{fix}, 1), (\text{fit}, 2) \\ \bigg\downarrow \quad \text{ParDo(ExpandPrefixes)} \\ \bigg\downarrow \\ (\text{f}, 1), (\text{fi}, 1), (\text{fix}, 1), (\text{f}, 2), (\text{fi}, 2), (\text{fit}, 2)

以下是一个 GroupByKey 的例子，将相同键的值聚合在一起：

(\text{f}, 1), (\text{fi}, 1), (\text{fix}, 1), (\text{f}, 2), (\text{fi}, 2), (\text{fit}, 2) \\ \bigg\downarrow \quad \text{GroupByKey} \\ \bigg\downarrow \\ (\text{f}, [1, 2]), (\text{fi}, [1, 2]), (\text{fix}, [1]), (\text{fit}, [2])

窗口

支持按键聚合的系统一般会将 GroupByKey 以 GroupByKeyAndWindow 的形式实现，本文的首要贡献在于支持非对齐的窗口。具体来说：

Dataflow 模型的视角下可以将所有窗口都当做非对齐的，并交由具体实现来为对齐式的窗口场景优化
窗口计算可以拆解为两个操作：
- Set<Window> AssignWindows(T datum)：将输入分配给0个或者多个窗口
- Set<Window> MergeWindows(Set<Window> windows)：聚合时将多个窗口合并为一个

为了支持基于事件时间的窗口，需要将数据传输的格式从 (key, value) 改为 (key, value, event_time, window)，event_time 是事件时间，window 默认是一个全局窗口，覆盖所有的事件，同时也适配了有界数据的场景。

窗口分配

如果一个输入属于多个窗口，那么窗口分配会给每个窗口创建一个输入的副本。

在下面这个例子中，键值对 (k, v1) 和 (k, v2) 分别复制到了两个窗口中。窗口的分配也不需要等到聚合时，可以在 pipeline 的任意执行点发生：

(\text{k}, \text{v1}, \text{12:00}, [0, \infty)), (\text{k}, \text{v2}, \text{12:01}, [0, \infty)) \\ \bigg\downarrow \quad \text{AssignWindows(Sliding(2m, 1m))} \\ (\text{k}, \text{v1}, \text{12:00}, [11:59, 12:01)), \\ (\text{k}, \text{v1}, \text{12:00}, [12:00, 12:02)), \\ (\text{k}, \text{v2}, \text{12:01}, [12:00, 12:02)), \\ (\text{k}, \text{v2}, \text{12:01}, [12:01, 12:03))

窗口合并

窗口合并发生于 GroupByKeyAndWindow 操作，我们以超时时间为30分钟的会话窗口为例，假设有 (k1, v1)，(k2, v2)，(k1, v3)，(k1, v4) 四个事件，其初始默认的窗口都为 $[0, \infty]$ 。然后，AssignWindows 根据每个事件到达的起始时间分配一个时长为30分钟的会话窗口，在这期间如果有相同键的事件到达，则也将其归到同一个窗口内。然后，GroupByKeyAndWindow 操作可以拆解为如下步骤：

(\text{k1}, \text{v1}, \text{13:02}, [0, \infty)), \\ (\text{k2}, \text{v2}, \text{13:14}, [0, \infty)), \\ (\text{k1}, \text{v3}, \text{13:57}, [0, \infty)), \\ (\text{k1}, \text{v4}, \text{13:20}, [0, \infty)), \\ \bigg\downarrow \quad \text{AssignWindows(Sessions(30m))} \\ (\text{k1}, \text{v1}, \text{13:02}, [13:02, 13:32)), \\ (\text{k2}, \text{v2}, \text{13:14}, [13:14, 13:44)), \\ (\text{k1}, \text{v3}, \text{13:57}, [13:57, 14:27)), \\ (\text{k1}, \text{v4}, \text{13:20}, [13:20, 13:50)) \\ \bigg\downarrow \quad \text{DropTimestamps} \\ (\text{k1}, \text{v1}, [13:02, 13:32)), \\ (\text{k2}, \text{v2}, [13:14, 13:44)), \\ (\text{k1}, \text{v3}, [13:57, 14:27)), \\ (\text{k1}, \text{v4}, [13:20, 13:50)) \\ \bigg\downarrow \quad \text{GroupByKey} \\ (\text{k1}, [(\text{v1}, [13:02, 13:32)), \\ (\text{v3}, [13:57, 14:27)), \\ (\text{v4}, [13:20, 13:50))]), \\ (\text{k2}, [(\text{v2}, [13:14, 13:44))]) \\ \bigg\downarrow \quad \text{MergeWindows(Sessions(30m))} \\ (\text{k1}, [(\text{v1}, \textbf{[13:02, 13:50)}), \\ (\text{v3}, [13:57, 14:27)), \\ (\text{v4}, \textbf{[13:02, 13:50)})]), \\ (\text{k2}, [(\text{v2}, [13:14, 13:44))]) \\ \bigg\downarrow \quad \text{GroupAlsoByWindow} \\ (\text{k1}, [(\textbf{[v1, v4]}, [13:02, 13:50)), \\ (\textbf{[v3]}, [13:57, 14:27))]), \\ (\text{k2}, [(\textbf{[v2]}, [13:14, 13:44))]) \\ \bigg\downarrow \quad \text{ExpandToElements} \\ (\text{k1}, \text{[v1, v4]}, \textbf{13:50}, [13:02, 13:50)), \\ (\text{k1}, \text{[v3]}, \textbf{14:27}, [13:57, 14:27))), \\ (\text{k2}, \text{[v2]}, \textbf{13:44}, [13:14, 13:44))

DropTimestamps：丢弃事件的时间戳，因为这里只涉及窗口计算
GroupByKey：按照键聚合 (value, window) 元组
MergeWindows：合并每个键下 (value, window) 元组中的窗口，具体的合并逻辑由窗口策略决定。在上述的例子中，如果两个 (value, window) 元组中的窗口存在重叠，则每个元组合并后的窗口为两个窗口的并集
GroupAlsoByWindow：对每个键下的 (value, window) 元组按照窗口聚合，在上述例子中，v1 和 v4 因为有相同的窗口，所以被聚合在了一起
ExpandToElements：将每个键下的 (value, window) 元组展开为 (key, value, event_time, window) 的形式，新的 event_time 在上述例子中采用的是窗口的结束时间，不过实际上只要是大于窗口内最早的事件的时间戳都行。

API

现在通过 Cloud Dataflow SDK 的代码示例来展示如何使用窗口。下述代码将数据按照键聚合后，求所有值的加和：

1
2
3

PCollection<KV<String, Integer>> input = IO.read(...);
PCollection<KV<String, Integer>> output = input
  .apply(Sum.integersPerKey());

如果要支持超时时间为30分钟的会话窗口，则在求和前调用 Window.into 即可：

PCollection<KV<String, Integer>> input = IO.read(...);
PCollection<KV<String, Integer>> output = input
  .apply(Window.into(Sessions.withGapDuration(
    Duration.standardMinutes(30))))
  .apply(Sum.integersPerKey());

触发器和增量处理

目前为止，还遗留两个问题：

需要支持基于元组和处理时间的窗口，不然会和当前已有的系统不兼容
需要知道窗口中的数据计算结果何时可以下发到下游

本文认为借助 watermark 来解决第二个问题是不够的，因为 watermark 不能百分百确保所有数据都已经到达，真实场景中总会有晚到的数据。Lambda 架构则提供了一个思路：流式引擎部分提供低延迟的计算，不过其结果是近似值，而批处理引擎则提供最终一致性正确的结果。不过，如何将两者合并到一个 pipeline 中？

本文提出了触发器（trigger）的概念，和窗口的关系为：

窗口：根据事件时间决定如何对事件分组
触发器：决定何时（处理时间）告知窗口计算的数据结果可以下发到下游

Google 实现的系统内置了几类触发器的实现用于在多种场合触发：

当所有的数据已被系统接收时（预估，非精确，如 watermark）
处理时间线上的某个时间点
响应数据到达（如数量，大小，data punctuations，模式匹配等满足了一定的条件）

另外，不同的触发器之间还可以进行逻辑组合，例如使用 and，or，循环，序列等等。

引入触发器后，同一个窗口的计算结果就有可能被多次下发，系统也提供了三种处理模式：

丢弃（Discarding）：一旦窗口被触发，其内容下发后即被丢弃，后续触发和之前的触发没有任何关系。如果多次窗口触发的结果是幂等的，则可以采用该模式
累加（Accumulating）：窗口被触发后，其计算结果会持久化，后续触发结果会作为历史结果的修正。适合于数据消费方收到新的窗口数据，直接替换旧数据的场景。例如某个窗口计算是求窗口中所有数据的最大值，第一次触发时下发目前的最大值，后续有数据再次到达时根据持久化的历史值，直接和当前值比较就可以得到最新的最大值
累加和撤销（Accumulating and Retracting）：在 Accumulating 的基础上，触发的窗口计算结果同样会先持久化，如果后续有新的触发，则会下发两个值，一个是用于告知下游系统撤销上次的值，另一个是最新的窗口计算结果。不过，这也需要下游系统具有响应数据撤销事件的能力

实现和设计

设计原则

Dataflow 模型的一些设计原则：

永远不要依赖任何完整性的概念
要有足够好的灵活性，既可以适应已知的各种使用场景，又能支持未来可能的扩展
在预想的执行引擎中要添加有价值的东西，而不仅仅是因为合理
鼓励清晰的实现
支持在数据产生的上下文中进行强大的数据分析

参考

The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing

【读】RocksDB: Evolution of Development Priorities in a Key-value Store Serving Large-scale Applications

Posted on 2025-02-17 Word count in article: 17k Reading time ≈ 28 mins.

本文是 Facebook 对 RocksDB 8年开发历程的回顾，重点讨论了为支持大规模分布式系统所做的开发优先级取舍与演进，以及在生产环境中运行大规模应用的经验。

介绍

RocksDB 是 Facebook 在2012年创建的高性能 KV 持久存储引擎，代码衍生自 Google 的 LevelDB。它针对 SSD 的某些特性进行了优化，目标是服务于大型（分布式）应用，在使用上则以类库的方式和上层应用集成。每个 RocksDB 实例是个单机版程序，本身不提供跨主机间的操作，例如副本管理和负载均衡，同时也不提供高阶 API，例如不支持 checkpoint，这些都留给上层应用自行实现。

RocksDB 及其高度可定制的组件设计使其能够从容应对不同的业务需求和工作负载。除了作为数据库系统的存储引擎外，RocksDB 还被用于以下几种不同类型的服务：

流式处理：典型代表如 Flink 借助 RocksDB 保存 checkpoint 的状态数据
日志/队列服务：依托于 RocksDB 可定制化的合并策略，这些服务能够以不亚于追加写单个文件的效率实现高吞吐的写入，同时有着较低的写放大，以及享受内置索引带来的便利
索引服务：RocksDB 的 bulk loading 特性能够为索引服务提供大规模加载离线数据的能力，同时也有着高效的查询性能
基于 SSD 的二级缓存：因为 RocksDB 针对 SSD 进行了优化，所以某些内存式的缓存服务会借助 RocksDB 在内存不够时将部分数据置换到 SSD。这些服务往往要求存储引擎有着足够高的写入速度和优秀的点查询性能

背景

RocksDB 的设计极大的受到了 SSD 特性的影响，SSD 不对称的读写性能和有限的耐用性给 RocksDB 的数据结构设计和系统架构带来了机遇和挑战。

基于 SSD 的嵌入式存储

相比于机械硬盘，SSD 读写的 IOPS 可以达到十万至百万，读写速度可以达到几百至几千 MB/s。一方面，这给如何设计软件从而能充分利用 SSD 的性能带来了挑战；另一方面，受限于 SSD 有限的擦除次数，同时也需要考虑如何设计合理的数据结构，避免提前耗尽 SSD 的寿命。

正因为 SSD 有着出色的性能，在大多数情况下，应用的性能瓶颈也从设备 I/O 转向了网络；应用架构设计时也更倾向于将数据存储在本地 SSD 而不是远程存储服务，因此，能够内嵌在应用中的本地 KV 存储引擎的需求就日渐上涨。

在这个背景下，Facebook 实现了 RocksDB，其中 LSM 树扮演了重大的角色。

RocksDB 的架构和 LSM 树的使用

RocksDB 使用 LSM 树作为主要的数据结构来保存数据并支持以下核心的操作。

写

写入时会先将数据写入到名为 MemTable 的内存写缓冲中，同时也会在磁盘上记录 Write Aghead Log (WAL)。MemTable 由跳表（skiplist）实现，插入和查询的时间复杂度都是 O(logn)。WAL 可按需开启，用于 RocksDB 从崩溃后恢复数据。当 MemTable 的大小达到所配置的阈值时：

当前接受写入的 MemTable 和 WAL 变为只读
后续新的写入转到新创建的 MemTable 和 WAL
系统会将变为只读的 MemTable 和 WAL 的内容落盘到 Sorted String Table (SSTable) 内
已落盘的 MemTable 和 WAL 则可以丢弃

SSTable 中的数据按序存储，并以等大小的块（block）组织。SSTable 生成后同样只能只读，同时，其内部会维护一个索引块，索引块中会给每个数据块维护一条索引，从而能借助二分查找快速搜索。

合并

alt

如上图所示，一个 LSM 树分为多层。最新的 SSTable 由 MemTable 刷盘生成，并放置在 Level-0。其他层的 SSTable 则统一由合并程序维护。当第 L 层的 SSTable 大小触及了配置值，合并程序会选择该层的部分 SSTable，并将其和第 L + 1 层内键的范围存在重合的 SSTable 进行合并，从而在第 L + 1 层生成一个新的 SSTable。通过这个操作，RocksDB 就可以将已删除和过时的数据清除，同时新生成的 SSTable 也进行了瘦身，节省了磁盘空间，最终写入的数据会逐渐从 Level-0 迁移到最后一层。整个合并过程的 I/O 效率也比较高，一方面不同层的合并可以并行执行，另一方面 I/O 操作只涉及整个 SSTable 文件的批量读和写。

MemTable 和 Level-0 层的 SSTable 键的范围可能会存在重合，而 Level-1 及其之后的每一层内，RocksDB 会确保每个 SSTable 之间键的范围不会重合（但是不同层之间的 SSTable 键的范围是有可能重合的）。

RocksDB 支持不同类型的合并策略：

Leveled Compaction：借鉴自 LevelDB 并加以改进。每一层可容纳的文件大小呈指数级放大。系统会积极的触发合并以确保每层的文件大小不会超过指定阈值
Tiered Compaction：在 RocksDB 中也被称为 Universal Compactioin，与 Apache Cassandra 或 HBase 采取的合并策略类似。当 Level-0 层文件的个数或者非 Level-0 层的个数超过指定的阈值时，又或者整个数据库的大小和最深层文件大小之比超过指定的阈值时，就会触发合并多个 SSTable。有别于 Leveled Compaction，Tiered Compaction 是惰性合并，实际的合并会推迟到读性能或者空间效率发生衰减时进行，从而能够一次性合并更多的数据
FIFO Compaction：当数据库大小触及到指定阈值时，丢弃最老的 SSTable，且只进行轻量级的合并。适合于基于内存的缓存应用

RocksDB 的读写性能在不同的合并策略下有着不同的表现，应用开发者需要结合自身服务的工作负载来选择合适的合并策略。

读

读取时，RocksDB 首先在所有的 MemTable 中查找，如果没有找到则继续在位于 Level-0 层的所有 SSTable 中查找，如果还没有找到，则继续向下一层中键的范围包含要查找的键的 SSTable 中查找，所有的查找都借助了二分搜索。另外还有两项辅助查找的优化：

频繁被访问的 SSTable 块会在内存中缓存从而减少文件 I/O，以及解压缩的开销
布隆过滤器用于快速排除一定不包含要查找的键的 SSTable

Column Family

RocksDB 在2014年引入了 column family 功能，不同的 column family 下可以包含相同的键，每个 column family 有独立的 MemTable 和 SStable，但是共享 WAL。其优势在于：

每个 column family 可独立配置，如合并，压缩，merge operators 以及 compaction filters
共享的 WAL 能够原子性的记录多个 column family 的更新
column family 可动态高效的删除和创建

资源优化目标的演进

写放大

RocksDB 最初的资源优化目标在于减少 SSD 的擦除周期以及写放大，写放大包含两方面：

SSD 本身的写放大：SSD 不能直接覆盖已有的数据，需要先将其擦除，再写入，写入的粒度为 page，但是擦除的粒度是 block，一个 block 包含多个 page；同时 SSD 的垃圾回收也会造成数据移动和擦除；最后 SSD 的 Wear Leveling 特性会保证各个 memory cell 均衡的写入，也引入了数据移动
数据库软件带来的写放大

在这两个因素下有时候写放大能达到100倍。

Leveled Compaction 的写放大倍数基本在10到30，在大多数情况能够数倍优于 B 树的实现。更进一步，Tiered Compaction 能将写放大倍数降至4到10，不过缺点是读性能会有一定的下降。一般来说，当应用的写负载较高时，可以配合写放大较低的合并策略，而当写负载不高时，则可以采用更激进的合并策略，从而有更好的空间效率和读性能。

空间放大

经过了多年的开发后，RocksDB 团队认为对于大多数应用来说，空间使用率远比写放大重要，因为这些场景下还没有触及 SSD 本身的限制，不恰当的比喻来说就是：

以大多数应用程序的稳定性来说，还远没有到比拼不同的操作系统稳定性的地步。

而实际上，应用本身也没有充分利用 SSD 提供的读写吞吐，因此这一阶段的优化重心就转移到了磁盘空间上。

由于 LSM 树无碎片的数据组织方式，天然的避免了由于数据碎片带来的磁盘空间浪费。另一方面，RocksDB 也引入了新的合并策略 Dynamic Leveled Compaction，其中 LSM 树每一层的大小上限会动态的根据最深层文件的大小调整，而不是固定值。这么做的原因是为了减少 LSM 树中无效的数据（已删除和已被覆盖），而和最深层文件大小的比值则可作为有多少无效数据的度量指标。最终的结果也表明相比于 Leveled Compaction，Dynamic Leveled Compaction 有着更稳定的空间效率。

CPU 利用率

随着 SSD 的发展，一种潜在的担忧是应用程序已不能完全充分利用 SSD 的潜能。因此，系统的瓶颈也从设备 I/O 转移到了 CPU。不过，RocksDB 的开发人员不这么看，因为：

只有少部分的应用受限于 SSD 的 IOPS，大部分应用受限于磁盘空间
一个高端 CPU 足够服务于一个高端 SSD。在 Facebook 的生产环境中还没有遇到 RocksDB 不能充分利用 SSD 能力的情况。当然，如果一个 CPU 配备多个 SSD 还是有可能会有 CPU 瓶颈的，不过这属于系统配置层面的资源不均衡问题。另一方面，写密集型的应用也有可能存在 CPU 瓶颈的问题，不过这可以通过使用更轻量级的合并策略解决。而在这之外的场景，其工作负载则可能不适合使用 SSD，因为有可能提前让 SSD 的寿命完结

不过，优化 CPU 利用率也不等于说是无用功，因为空间放大的优化余地已经不多了。优化了 CPU 也等同于省钱，毕竟 CPU 和内存的价格也在节节攀升。一些针对 RocksDB 的 CPU 优化的尝试包括前缀布隆过滤器，在查找索引前先用布隆过滤器判断，以及其他的一些布隆过滤器优化。

适配新技术

一些 SSD 的新技术例如 open-channel SSDs，multi-stream SSDs，ZNS 能让 SSD 有着更低的查询延迟以及更少的擦除周期损耗。不过，如前面所述，RocksDB 的开发团队认为大部分应用的瓶颈在于磁盘空间，适配这些新技术反而会给 RocksDB 的一致性体验带来挑战，所以这项的优先级不高。

In-storage computing 可能会给应用带来巨大的提升，不过 RocksDB 的开发团队目前还不确定 RocksDB 能从这项技术中受益多少，而且对 API 的改动可能也比较大。

Disaggregated (remote) storage 则更具吸引力，并且也是当前的一个优化重点。前文的优化背景都是应用直接访问本地 SSD，不过，如今更快的网络带宽使得远程访问 SSD 成为了可能，因此，如何优化 RocksDB 使其更好的适配远程 SSD 也变得有意义。在远程存储模式下，CPU 和 SSD 资源可以同时做到充分利用以及独立扩展，相反本地 SSD 的模式则较难实现。目前 RocksDB 的开发团队正在优化远程模式下的 I/O 延迟。

最后，non-volatile memory (NVM) （它相比于 SSD 有着更高的 IO 读写吞吐）这项技术也在考量中：

将 NVM 作为 DRAM 的扩展
1. 如何实现核心数据结构（block cache 还是 MemTable）从而结合 NVM 和 DRAM 一起使用
2. 会引入哪些额外的开销
将 NVM 作为数据库的主要存储：不过实践表明 RocksDB 的瓶颈主要在于磁盘空间或者 CPU，而不是 I/O
用 NVM 保存 WAL：其成本是否值得有待考虑，毕竟 WAL 中的数据量不大，并且会刷盘到 SSD

再次审视 RocksDB 使用 LSM 树的合理性

LSM 树依然是最适合的，因为 SSD 还没有到白菜价的地步，对于大多数应用来说，其有限的寿命依然是无法忽略的因素。而另一方面，RocksDB 的开发团队也发现某些写密集型的应用会写大量的大对象，如果能分别存储键值对则能减少 SSD 的写入，其功能实现为 BlobDB。

运行大规模系统的经验总结

资源管理

大规模分布式数据服务往往会将数据以 shard 的粒度分区到多个节点上，一个节点可能会持有几十上百个 shard。不过 shard 的大小有限，因为 shard 是负载均衡和副本的最小单位，需要在各节点之间进行拷贝。在 Facebook 的环境内，一个 shard 由一个 RocksDB 实例提供服务，因此一个节点会运行很多 RocksDB 实例，它们可能会共享一个地址空间，也有可能会独享。

在上述背景下，就需要考虑如何进行资源管理，包括：

分配给 write buffer，MemTable，block cache 的内存
合并程序占用的 I/O 带宽
合并程序线程数
磁盘使用量
文件删除速率

资源管理包括两个维度，全局（分配给每个节点的资源）和局部（分配给每个 RocksDB 实例的资源）。对后者来说，RocksDB 允许应用程序创建 resource controller （以 C++ 对象实现并传递给多个 RocksDB 实例）来对上述提到的资源进行分配。例如，一个实现了对合并程序占用的 I/O 带宽限流的 C++ 对象可以传递给多个 RocksDB 实例，从而保证任一时刻所有 RocksDB 实例的合并程序占用的 I/O 带宽之和不会超过指定值。另外，资源管理需要能够支持按优先级分配，使得最迫切需要资源的实例能够优先获取资源。

另一个在一个进程内运行多个 RocksDB 实例的经验总结是将各实例中执行相似任务的线程统一以一个线程池进行管理，而不是每个实例各自维护线程池。这些线程执行的往往是后台任务，统一了线程池也变相的限制了后台任务执行时占用的 I/O，使得资源使用更具预测性。独立维护线程池的情况下有可能会有瞬时的 CPU 或者 I/O 毛刺，造成服务不稳定。不过，有得则有失，共享线程池的缺点就在于某些实例有可能无法及时的获取线程，从而阻塞后台任务，例如无法及时执行 SSTable 的合并，甚至造成写停顿（write stall）。

相比而言，当不同的 RocksDB 实例运行在多个进程时，全局的资源管理则更具有挑战性，毕竟各进程之间没有信息交互。文中提出了两种策略：

为每个 RocksDB 实例配置较为保守的资源额度，缺点就是全局资源利用率不一定最优
各进程间交换资源使用的情况，从而动态调整资源配比

支持副本和备份

RocksDB 本身不提供开箱即用的副本和备份的支持，需要应用自行实现，不过 RocksDB 为实现这两个功能提供了必要的支持。

副本

从一个节点复制出一个全新的副本节点有两种方式：

逻辑复制（logical copying）：遍历源节点的所有键值对，然后写入到目标节点。在源节点端，借助 RocksDB 的快照功能保证了数据的读一致性。同时，RocksDB 支持 scan 操作从而在数据复制时减少对在线查询的影响。在目标节点端，RocksDB 提供了 bulk loading 的功能来批量加载数据
物理复制（physical copying）：直接复制 SSTable 和其他辅助文件到目标节点。RocksDB 在复制时会确保没有文件被修改或删除

备份

备份对于数据库来说至关重要，和副本复制一样，备份的实现同样有逻辑备份和物理备份两种。副本和备份的其中一个区别在于上层应用经常会需要同时管理多个备份。RocksDB 也内置了一个备份引擎针对简易的备份场景。

更新副本面临的挑战

在多副本场景下，如何将主节点的更新以一致的顺序同步到各个副本是一个挑战。直白的做法是依次按序向各个副本写入，当然缺点就是性能很差，无法利用多线程。另外，当某个副本停止同步很久之后，需要有相应的机制能让其快速同步至最新的状态。

而无序写的问题在于读取时有可能数据不一致，一种解决方法是引入快照读，客户端读取时指定序列号，RocksDB 会返回执行快照时对应时间点的数据，而不会受当前正在进行中的写入的影响。

WAL 处理

传统的数据库一般要求每次写入前先写 write-ahead-log (WAL) 来保证数据的持久性。相反，大型分布式存储系统一般使用多副本来提升性能和可用性，例如，如果某个副本的数据损坏或者无法访问，那么系统可以基于其他完好的副本重新构建损坏的副本。对于这些系统来说，WAL 就不是那么重要。另外，分布式系统一般也有自己的一致性协议日志（如 Paxos 协议），这种情况下 WAL 就可以不需要了。

因此，RocksDB 需要能够针对不同的场景灵活配置 WAL，RocksDB 提供了三种选项：

同步刷盘写 WAL
先将 WAL 写入到缓冲区，然后定期由后台低优先级线程刷盘
无 WAL

数据格式兼容性

大型分布式应用往往运行在诸多节点上，并且最好不发生服务中断。因此，软件更新往往是逐台（或者小批量同时）发布，出现问题时再回滚。因此，RocksDB 需要能够保证存储在磁盘上的数据能够后向和前向兼容。另外，出于副本构建或者负载均衡的需要，系统会在各节点之间复制数据，因此整个集群可能运行着多个版本格式的数据。

对于后向兼容来说，RocksDB 需要能够识别之前的所有数据格式，这无疑增加了实现了维护的复杂度。对于前向兼容来说，RocksDB 需要能识别新的数据格式，并且至少要支持一年的前向兼容，这方面的技术手段借助于 Protocol Buffer 或者 Thrift。对于配置项的兼容性来说，RocksDB 需要能够识别未知的配置，并尽最大可能尝试猜测配置的含义或者忽视。

错误处理的经验总结

RocksDB 的开发团队通过产线的实践总结了三条关于错误处理的经验：

数据损坏越早监测到越好，从而最低程度的避免数据不可用或丢失，同时也能精确定位数据损坏的源头。RocksDB 通过在系统各层级计算数据的校验和并在数据传输时验证校验和来识别数据是否损坏
完整性保护必须覆盖整个系统，从而避免由于静默的硬件数据损坏传递给 RocksDB 客户端或者其他副本。仅仅在数据未使用或者传输时检测是不够的，因为数据损坏有可能由异常的软件，异常的 CPU 或者其他异常的硬件引入。不过，即使基础设施一直扫描系统中是否有异常的硬件，某些硬件异常也不一定能够被发现
错误需要能够区别对待。RocksDB 的开发团队最开始将所有非 EINTR （系统调用中断）类型的文件系统错误统一处理。如果错误发生在读取操作，那么 RocksDB 直接将错误传递给客户端。如果错误发生在写操作，那么 RocksDB 认为这是一个不可恢复的错误，然后永久中断所有的写入；RocksDB 需要重启才能恢复写入，并且可能还需要额外的运维操作。为了减少这种粗暴的重启，RocksDB 的开发团队开始对错误按照严重性分门别类，并且只有在遇到确实是不可恢复的错误时才中断操作

静默损坏的频率

在真实的 RocksDB 使用场景中，多久会发生一次静默的数据损坏？这很难直接给出答案。出于成本的考虑，应用所使用的存储设备一般不提供端到端的数据保护，相反，应用依赖 RocksDB 提供的块校验和来检测数据损坏。另一方面，基于 RocksDB 的应用本身也会运行数据校验程序来对比副本间的数据，不过这个过程识别出的数据损坏既有可能是 RocksDB 引入的，也有可能是应用本身引入的。

通过比较 MyRocks 中主键和二级索引的使用情况，RocksDB 的开发团队推断出每 100 PB 数据在每三个月内会发生一次由 RocksDB 本身引起的数据损坏。其中40%的情况下，这些数据损坏已经扩散到了其他副本上。

另一方面，数据损坏也有可能发生在数据传输中，这经常是由于软件 bug 导致。例如，底层存储系统在处理网络异常时的一个 bug 会导致一段时间后，每传输 1 PB 数据大约有17个校验和不匹配。

多级保护

数据损坏需要尽早识别，以免扩大影响范围，并尽可能的减少服务中断时间和数据丢失。大多数的 RocksDB 应用会持有一份数据的多个副本，并定期检测副本的校验和来识别损坏的副本，一旦发现损坏的副本，应用就可以丢弃该副本并替换为正确的备份。不过，这种做法的前提是系统中始终持有有效数据的副本。

如下图所示，RocksDB 启用了多级校验和保护，从而能尽早的发现数据损坏。

alt

块完整性

块校验和继承自 LevelDB，是为了避免文件系统层的数据损坏传递到客户端。这里的块不仅仅指 SSTable 块，也包括了 WAL 段（fragment），在块生成时会同时生成校验和。每当一个块被读取时，RocksDB 都会检验它的校验和。

SSTable 完整性

每个 SSTable 文件也保存了一个校验和，该功能在2020年引入，是为了避免 SSTable 在传输时造成损坏，校验和会在生成 SSTable 时同时生成，并保存在 SSTable 的元数据中，RocksDB 会在传输 SSTable 时检验校验和。不过，这篇文章发表时，还没有 WAL 文件级别的校验和。

Handoff 完整性

在往文件系统写入数据前，会同时生成一个 handoff 校验和，然后将数据和校验和一起传递给下一层，由下一层进行数据校验。RocksDB 的开发团队期望用这种方式对 WAL 进行校验，因为 WAL 都是增量的追加写，不过可惜的是，很少有本地文件系统支持这种校验方式。不过，当 RocksDB 结合远程存储使用时，可以修改 write 接口使其接收额外的校验和，然后将其添加到存储服务内部的 ECC （Error Correction Code，用于校验数据完整性）中，最后远程存储服务在收到写请求时就可以进行校验。

端到端的键值对完整性保护

上述的完整性校验依然存在不足，其中一个不足在于文件系统之外的数据没有完整性保护，例如 MemTable 和 block cache 中的数据。因此，在这一层的数据损坏就无法被监测并有可能最终扩散到上层应用。而如果此时发生了 MemTable 的刷盘或者合并操作，则会将损坏的数据永久的持久化到磁盘上。

因此，RocksDB 的开发团队的解决方案是实现每个键值对级别的校验和，从而在文件系统层之外发现数据损坏。当某个键值对被复制时，其校验和也会随之复制，不过在写入到文件时这部分校验和会忽略，因为在文件系统级别已经有其他校验和机制来保证完整性了，从而减少数据冗余。

基于严重性的错误处理

大部分情况下，RocksDB 遇到的故障都是底层存储系统返回的错误。这些错误可能来自于各种各样的问题，从比较严重的问题例如文件系统变成了只读，到短暂的问题例如磁盘空间满了或者访问远程存储时网络异常。在早些时候，如果是读操作时发生的错误，RocksDB 就简单的将错误信息返回给客户端，而如果是写操作时发生的错误，RocksDB 则会永久性的暂停所有写操作。

而优化后 RocksDB 仅在遇到无法本地恢复的错误时才中断操作，例如暂时的网络错误不应该要求重启 RocksDB 实例。对于暂时性的错误，RocksDB 会周期性的重试。

配置管理和可定制化的经验总结

配置管理

一开始，RocksDB 的配置管理继承自 LevelDB，所有的配置都写死在代码中。这带来两个问题：

某些配置和保存的数据强相关，因此，由某项配置生成的数据文件可能无法由其他配置的 RocksDB 实例打开
没有在代码中声明的配置会采用默认值，一旦 RocksDB 版本更新并修改了某些配置的默认值，上层应用可能会遇到不可预知的问题

为了解决配置的问题，RocksDB 可以在打开某个数据库的同时额外接受某些参数配置，之后 RocksDB 又支持将配置持久化到文件中。RocksDB 也提供了额外的两个辅助工具：

验证配置参数是否和要打开的数据库兼容
将数据库按照期望的参数配置进行迁移（不过存在使用限制）

配置管理的另一个严峻的问题就是配置项太多了，用户很难知道每个配置参数的影响，进而不知道如何根据自身应用找到最优的配置。但是又很难找到一套放之四海皆准的默认配置，因为每个应用的使用场景，工作负载都不同。另一方面，对于集成了 RocksDB 的应用，例如 MySQL，数据库管理员可能对 RocksDB 了解不多也不知道如何优化。

在这个背景下，RocksDB 的开发团队花费了大量时间去优化默认配置下 RocksDB 的性能以及简化配置。同时，当前的重点在于提供配置的自适应性（automatic adaptivity），另一方面也持续提供 RocksDB 可自定义配置的能力，从而能适配不同类型的应用。同时做到这两方面会显著的增加代码维护的负担，不过一个统一的存储引擎的重要性大于代码的复杂度。

回调函数的威力

RocksDB 需要周期性的合并底层的 LSM 树来清理已删除和过期的数据，如果能在合并时为应用提供额外的接口则能方便的为应用做功能扩展，而不需要额外的标准读写操作。因此，RocksDB 提供了两个在合并时的回调方法 compaction filter 和 merge operator。

Compaction Filter

在合并时，RocksDB 提供了执行合并时针对每个被处理的键值对的回调函数，应用可以自行决定：

丢弃这个键值对
修改值
不做任何修改

一个典型的应用场景是实现 time-to-live (TTL)，每个键值对在写入时保存了过期时间，然后在合并期间判断是否过期从而删除数据。另一个应用场景是实现 multi-version concurrency control (MVCC) 中的垃圾回收。另外，compaction filter 也可以用于修改数据，例如，从旧数据格式迁移到新的数据格式，或者根据时间来修改数据。最后，compaction filter 有时候也可以用来收集统计信息。

compaction filter 也非常适合需要扫描全部数据的管理任务，虽然也可以遍历整个数据集然后通过 delete() 或 put() 操作，但是使用 compaction filter 更高效且使用更少的 I/O 操作。借助 compaction filter，用户无需额外维护定时任务，也不用担心由自定义实现可能造成的写入毛刺。

不过，compaction filter 在使用上也有些限制。例如，错误的使用 compaction filter 可能会破坏基本的数据一致性保证，多次快照读也可能返回不一致的结果（如果数据在两次读之间发生了修改）。因此，compaction filter 在不要求一致性的场景下更容易使用。另一个限制是 compaction filter 无法原子的丢弃或者修改一批键值对，例如，无法原子的删除一个键值对并丢弃相应的二级索引中的数据。

Merge Operator

RocksDB 原生支持三类操作：put()，delete()，和 merge()。每一个操作都会写入到相应的 MemTable，然后刷盘到 SSTable。merge() 方法使得应用不需要先读取键就能更新键的值，也不需要写入完整的键的内容。在随后的读操作或者合并操作时，如果 RocksDB 遇到了一个 merge record 以及之前调用 put() 写入的记录，或者是多个 merge record，RocksDB 会调用 merge operator 回调函数，应用可以将这些记录合并成一个，既可以是一个 put record，也可以是一个 merge record。

merge operator 的一个显著的应用是实现 read-modify-write 操作，例如实现一个计数器或者更新某个复杂对象中的单个字段。相比于用 get() 和 put() 整个键值对来实现，用 merge operator 来实现则更为轻量。不过，这会影响读的性能，因为找到一个 merge record 不代表查询结束，最坏的情况可能需要遍历 LSM 树的所有层，或者直到找到一个 put record 为止（更频繁的合并能缓解这个影响）。

优化删除

删除往往是 LSM 树中被忽略的一个操作。RocksDB 中无法直接删除键值对，删除操作本质上是插入一条标记删除的记录，这使得删除操作很快，但后续对该键的查询有可能变慢。在执行合并操作时，如果遇到标记删除的键值对，并不能直接将其物理删除，因为无法保证该键值对是否还存在于更深层的 SSTable 中。因此，RocksDB 针对删除场景也做了一些优化。

假设应用对同一个键依次执行了三次操作：put()，delete()，put()，前两个操作属于 MemTable1，后一个操作属于 MemTable2，之后刷盘成 SSTable1 和 SSTable2。因为合并操作只是选取一部分 SSTable，所以有可能 SSTable2 先合并到了更深层。

支持对大范围标记删除的数据范围扫描

应用经常会大批量删除连续或者临近的键，在这种场景下，调用 scan() 遍历每个键时就会遇到一堆已被标记删除的数据需要被跳过，从而浪费 CPU 和 I/O 资源。例如，某个应用可能用 RocksDB 保存文件系统中每个文件的绝对路径，而如果删除了文件夹则会导致一大批键被删除。再例如，使用 RocksDB 模拟队列时，每个出队的元素都会被删除，那么队首的元素则天然的挨着一批被删除的元素。遍历这些被删除的键一方面加重了资源负担，另一方面对查询结果也没有影响。在极端情况下，RocksDB 的开发团队在实践中遇到扫描了几百万个标记删除的键，最终只为了返回几个键值对。

一种解决思路是当出现大量连续标记删除的键时，触发合并操作。RocksDB 提供了几个功能：

当标记删除的键占所有键之比超过50%时，合并会更积极的发生，并且随着标记删除的键占比增加而更频繁。不过，不能很好的处理标记删除的键占比不超过50%的情况
允许应用自己标记哪些 SSTable 需要执行合并。在执行合并生成新的 SSTable 时，RocksDB 提供了插件机制能够访问每个被处理的键值对，当新的 SSTable 创建后，RocksDB 会调用该插件从而判断是否需要将该 SSTable 放入下次的合并操作中。RocksDB 的统计信息中也包含了一次查询涉及了多少个标记删除的键，从而辅助应用更好的判断是否需要发起合并
执行 scan() 操作时，如果遇到了指定数量的标记删除的键，则提前中止遍历。当然，这样做的结果就是返回的数据不全，不过应用就能知道遇到了大量被标记删除的键，需要应用自行决定是否需要继续扫描还是放弃

上述措施一定程度上能缓解前述的问题，不过依然有局限性：

合并需要时间，在这期间 scan() 的性能依然受限
更频繁的合并意味着更大的写放大，这对于某些应用来说是不可接受的

目前，这方面的优化工作仍然在进行中。

回收磁盘空间

一般来说，如果数据被删除了，那么其所占用的磁盘空间也应当被释放。不过在 RocksDB 中数据不是立即删除，需要等待一段时间，而应用可能会要求在指定的时间内就需要释放磁盘空间。因此，RocksDB 提供了一个功能保证在指定时间内所有被标记删除的键都会移动到 LSM 树的最后一层，那么这些数据在随后的合并中就可以被清理。RocksDB 通过在 SSTable 的元数据中维护每个键首次添加到系统中的时间来实现该功能。

文件删除限流

RocksDB 一般构建于能够感知 SSD （flash-SSD-aware）的文件系统之上，当某个文件被删除时，它会发送一个 TRIM 命令给 SSD。TRIM 的性能较好且对于 SSD 的寿命影响较小。不过，它可能会造成其他的性能问题：除了更新地址映射（大多数位于 SSD 的内部内存中）之外，SSD 固件还需要将这些变更作为 FTL 日志写到闪存上，这又会触发 SSD 内部的垃圾回收，从而造成大量的数据迁移，并最终影响上层应用的 I/O 延迟。所以，RocksDB 增加了文件删除的限流来控制同一时刻删除的文件个数。

内存管理

RocksDB 对于内存的使用主要在于 SSTable 的 block cache 以及保存 MemTable。相比于其他数据库自己维护缓冲池，RocksDB 则依托于 jemalloc 进行内存分配。

尽管块的大小是可配置的，RocksDB 的实际实现则是采用变长的块，不过其大小会尽可能的接近所配置的值。例如，如果某个键值对的大小超过了指定的块大小，那么 RocksDB 会为其创建较大的块。类似的，如果某个块中已经存在一部分键值对，而此时再放入一个键值对就会超过块的大小时，则该键值对不会被放入该块中，并且 RocksDB 会选择一个较小的块来存放原来的那批键值对。另外，SSTable 的索引块和布隆过滤器的块大小也没有采用固定大小。出于这么做的原因是因为 RocksDB 采用的数据结构不支持就地更新，采用固定大小的块收益不大。

不过，在实践中，借助 jemalloc 来管理内存在分配和回收时都存在不可忽视的开销，其外部的内存碎片和元数据带来的额外内存开销也值得应用注意。这种情况下应用开发者可以选择换一个内存分配器，或者对 jemalloc 进行调优。

另外，RocksDB 的用户也经常对如何高效的调优内存参数感到迷茫。RocksDB 能够精确限制 block cache 和 MemTable 的内存参数，但是对 jemalloc 的外部内存碎片和元数据无法掌控，所以用户需要自行判断应该给这部分预留多少内存。因此，实验是检验真理的唯一标准。

尽管如此，RocksDB 的开发团队认为使用 jemalloc 仍然是一个合理的决定，因为可以将精力放到其他更重要的方面上。不过未来可能也会将这个内存管理问题提上日程。

Key-Value 接口设计的经验教训

RocksDB 的核心接口就四个：

put()
delete()
get()
iterators (scans)

很少有应用无法基于这四个接口实现需要的功能，KV 接口的键和值都是变长的字节数组，因此应用程序可以很自由的存储想要的数据，只需要做好序列化和反序列化。另外一个好处是可移植性，应用可以轻易的从一个 KV 系统迁移到另一个。

不过，天下没有完美的事物，部分应用的性能反而会受限于这精简的接口。例如，在 RocksDB 之外处理并发控制就很难做的高效，尤其是两阶段提交场景下需要在事务提交前先持久化一部分数据的场景。因此，RocksDB 增加了事务的功能，并持续添加新的功能，例如对某个范围内的数据加锁，以及支持大事务。

在其他场景下，应用则受限于过于精简的接口，为此 RocksDB 增加了两项扩展：

由应用定义的时间戳
列支持

版本和时间戳

为了支持诸如 multi-version concurrency control (MVCC) 和从历史某个时间点读取（point-in-time reads）的功能，RocksDB 需要能够支持数据的版本管理，并能高效的访问各个版本。

目前，RocksDB 内部使用一个56位长度的序列号来标识键值对的每个版本。客户端的每一次写请求都会对版本号加1，不过客户端无法直接修改这个版本号。RocksDB 允许应用对其执行快照，RocksDB 保证只要这个快照没有被应用释放，那么在这个快照执行的时间点时的数据就都能始终被访问。

不过，对很多应用来说这依然不够，为了读取历史上的数据，前提是应用必须先曾经做过快照，RocksDB 不支持在当前时间对历史的某个时间点执行快照，因为根本没有这样的接口。另外，RocksDB 的版本号是每个实例各自维护，快照也是各实例粒度。因此，对于多 shard 的应用来说，很难对所有节点同时做一致的快照。

虽然应用可以将时间戳写入到键或者值中，不过这会影响应用的性能。如果将时间戳写入到键中，则点查询的性能会很差，因为实际保存的键和用户查询的键已经不同，需要做前缀扫描遍历；如果将时间戳写入到值中，则会影响对同一个键乱序写入的性能，因为乱序写入时如果不考虑相互间的时间戳顺序则有可能发生数据覆盖，并且读取旧版本的数据也变得复杂。因此，RocksDB 需要提供在键值之外由应用自行指定时间戳的能力。

经过实验，由应用指定时间戳的情况下，RocksDB 相比于将时间戳写入到键的方案有1.2倍的吞吐提升。提升的原因在于：

时间戳是键值对元数据的一部分，因此点查询依然高效
布隆过滤器可以继续发挥作用
每个 SSTable 在元数据中同时也维护了所有键所覆盖的时间戳范围，因此在搜索时有可能直接忽略整个 SSTable

当然缺点就是磁盘使用空间会变大以及移植性变差。

列支持

一些基于 SQL 的数据库实现会以列的形式组织 RocksDB 的数据，虽然应用可以将数据库中一整行的数据以单条 KV 的形式保存在 RocksDB，但是如果能直接在 RocksDB 层面支持列则对应用的性能提升有很大帮助。

假设有些大对象的某些列更新非常频繁，那么在整行数据保存的方案下更新就非常不高效。如果支持列，则只需要更新部分列。另外，如果数据库的某个查询也只涉及部分列，那么也不必读取完整的一行数据。

某些应用已经尝试对上述的问题进行优化。例如 Rocksandra 借助 merge operator 来进行部分列的更新，不过代价就是读性能较差，因为需要读完所有的 merge record 或者遇到一个 put record 才能知道最终的结果。另一种方案是将一行数据的每一列保存为一个键值对，缺点在于：

读取一行数据需要进行范围扫描（比如所有的列数据的键都以主键为前缀）
删除和更新一整行数据变得困难

因此，如果能在 RocksDB 层面直接支持列，则能大大提高应用的性能：

更新和读取单列的数据变得高效
当应用发起针对某些列的过滤查询时，某些过滤条件可以下推到 SSTable
某些列可以用不同配置的 column family 保存
可以像列数据库一样高效压缩保存列数据

另外，支持列也能够让 RocksDB 在主键索引和二级索引间校验数据完整性。

来自失败的提案的经验总结

一路走来，RocksDB 实现了很多的功能，其中也有些失败的案例。

支持基于 DRAM 的存储设备

在2014年，RocksDB 的开发团队决定将 RocksDB 适配到 Ramfs （RAM File System）上，从而有比 SSD 更低的访问延迟。为此，RocksDB 将 SSTable 和 MemTable 的格式改为插件式，从而针对 Ramfs 进行了特定的优化。

这个结果本身是成功的并且也应用到了某些服务上。不过，在战略上来说这个功能提的太早了。对于大型纯内存式的持久化存储系统来说，RocksDB 的这套方案并未像预期的那样获得关注。而对于内存式的应用来说，一般也不会考虑集成 RocksDB，因为完全直接自己操作内存来的更快和便捷。

支持混合式存储设备

SSD 比 HDD 更快，不过也更贵而且寿命也有限。因此，如果能结合 SSD 和 HDD 一起使用，那么对于大多数的应用来说可以在性能和成本之间做到更好的平衡。同样是在2014年，RocksDB 支持能将 LSM 树的不同层保存到不同的存储设备上。

不过，在该功能推出的时候用户并没有买账。另一方面，在实践中将 SSD 和 HDD 同时配置到一个节点上的情况也比较罕见，RocksDB 的开发团队认为混合存储方案的潮流应该对远程存储服务更有吸引力，而这要到2018年才开始着手。不过，最近RocksDB 的开发团队又重拾了混合式存储项目，因为要支持混合式的本地/远程存储服务，不过依然还有额外的工作要做。

更丰富，高层次的接口

RocksDB 最开始支持的是传统的 KV 接口，不过，在过去的几年中也尝试过扩展支持更为丰富的接口，从而更方便某些应用使用。例如，在2013年 RocksDB 添加了类似于 Redis 的 lists 的接口；在2014年添加了2个与空间相关的接口；在2015年支持了文档类型的数据。所有这些接口都基于核心的 KV 接口实现。

但是，这些接口同样没有被广泛采纳，并最终废弃和移除。因此，对于 RocksDB 的开发团队来说，将精力放在核心功能上更有价值。大部分 RocksDB 的用户都能借助简单的 KV 接口构建更为丰富的上层接口，而不需要由 RocksDB 来提供。用户的首要痛点在于效率和易管理性。总结来说，扩展核心接口的前提在于能够显著提升性能。

附录

经验总结

对于存储引擎来说，能够调优适配不同的工作场景至关重要
大多数使用 SSD 的应用的瓶颈在于空间效率
降低 CPU 开销对系统的高效运行越来越重要
如果一台机器上运行了多个 RocksDB 的实例，那么全局的资源管理就是必须的
WAL 的可配置性（同步刷盘写 WAL；先将 WAL 写入到缓冲区，然后定期刷盘；无 WAL）能够给上层应用带来性能提升
需要正确的支持数据副本和备份
RocksDB 需要对数据和配置文件提供后向和前向兼容
越早识别数据损坏越好，而不是在最后检测
完整性保护必须能够覆盖整个系统来避免数据损坏（例如，由 CPU 或内存引起的 bitflip）扩散给客户端或者其他副本；只在数据空闲时或者传输时进行损坏检测是不够的
错误处理需要能够根据类别和严重性分别处理
即使概率很低，CPU 和内存造成数据损坏也有可能发生，因此数据副本并不一定总是能解决这种情况
自适应的配置对简化配置管理大有益处
可以通过用户自定的回调函数来提升性能，不过当前的技术方案仍有进步的空间
在 LSM 树中删除连续的键会带来性能问题
SSD 的 TRIM 对性能大有帮助，不过需要对文件删除作限流来避免偶发的性能问题
借助第三方内存分配器来管理内存使得开发团队能将精力放在其他重要的功能上，不过缺点是带来了可管理性问题
目前的 KV 接口已足够有用，不过对于某些应用场景来说可能会有性能问题；在键值之外添加时间戳能够在性能和简洁性上达到较好的平衡
应用可以在 RocksDB 提供的 KV 接口之上实现列数据并且有着较好的性能，不过如果存储引擎本身支持列则会有更好的性能

设计抉择回顾

可定制化对用户始终有用：结果就是用户迷失在大量的配置里，而且很难找到最优的配置
RocksDB 无法感知 CPU 的 bitflip：完整性保护需要端到端覆盖
遇到任何 I/O 错误时可以直接中断操作：过于粗暴，所以需要根据错误的类别和严重性做不同的处理

参考

【读】How to Read a Paper

Posted on 2025-01-28 Word count in article: 965 Reading time ≈ 2 mins.

介绍

本文提出了一种高效阅读文献的方式，相比于一上来就从头读到尾，作者将其拆解为三趟式阅读：

第一遍了解论文讲什么，解决了什么问题，提出了什么方法
第二遍理解论文的内容，但忽略细节
第三遍深入理解论文

第一遍阅读

第一遍阅读建议控制在5到10分钟内，阅读内容包括：

仔细阅读标题，摘要和简介部分
阅读每一节和每小节的标题，但忽略内容
阅读结论部分
扫一遍论文引用，并标记哪些已经读过

第一遍读完后，你应该能够回答5个问题：

Category：这是一篇什么类型的论文？
Context：有哪些其他相关的论文？
Correctness：论文中的假设对吗？
Contributions：这篇论文的主要贡献是什么？
Clarity：这篇论文写的清晰易懂吗？

当回答了这5个问题后，你就可以决定是否要继续读下去，不继续读的原因可能是因为这篇论文对你价值不大，也可能是因为你还没有足够的知识储备来理解，甚至是论文中描述的假设都是错的。

第二遍阅读

第二遍开始仔细阅读论文，但忽略细节比如证明环节：

仔细阅读论文中的图表，尤其是图片。一些图表中的常见错误可以提前让你甄别出不严谨甚至是粗制滥造的论文
标记还没有读过的相关论文引用以便之后阅读，这有助于更好理解该篇论文的背景

第二遍阅读应该控制在1小时以内，通过第二遍阅读，你应该能够理解论文的内容，并能够自我总结论文的要旨给第三者。这个层次的掌握程度对于阅读感兴趣的论文已经足够，但用于科研工作还不够。

如果第二遍读完还不能理解怎么办？这有可能是因为论文的主题对你来说是一个新事物，也可能是因为论文的作者采用的证明让你摸不着头脑，或者这篇论文就是写的晦涩难懂，甚至是因为夜深了。你可以选择：

把论文放一边，即使不理解这篇论文也不影响你事业的成功
之后再看，先补充点背景材料
硬着头皮开始第三遍阅读

第三遍阅读

第三遍阅读能让你真正的理解这篇论文。这次阅读的关键是假设自己是论文的作者，并且基于原作者的假设，重新构建论文。通过你所构建的论文和原论文对比，你就能轻易的发现原论文的创新点，以及潜在隐藏的缺点和假设。

第三遍阅读需要高度关注细节，并时刻本着以怀疑的态度看待论文中的每一个假设。通过这次阅读，也能够为你之后的科研工作提供一些想法。

对于新手来说第三遍阅读大概要花4到5个小时，而对于有经验的读者来说只需要1小时。

参考

How to Read a Paper

【读】Bitcask - A Log-Structured Hash Table for Fast Key/Value Data

Posted on 2025-01-05 Word count in article: 2.5k Reading time ≈ 4 mins.

介绍

Bitcask 是一个单机 KV 存储引擎，项目起因于 Riak 分布式 KV 数据库需要一个能满足以下条件的单机 KV 存储引擎：

低延迟的单条读写
高吞吐，尤其是面对流式随机 KV 写入
能支持远比内存大的数据量
能从崩溃中快速恢复以及不丢失数据
能轻松的备份和还原数据
相对简单，易理解的代码结构和数据格式
在高负载和大数据场景下系统的行为是可预期的
软件的许可证要能轻易的适配 Riak 使用

作者看了一圈发现市面上还没有一款 KV 存储能全部满足这些条件，因此 Bitcask 就应运而生。

API

Bitcask 的接口非常精简：

接口	描述
bitcask:open(DirectoryName, Opts) -> BitCaskHandle \| {error, any()}	在指定目录下以指定选项打开或新建一个 `Bitcask` 实例。支持的选项包括 `read_write` 或者 `sync_on_put`： `read_write`：可读可写 `sync_on_put`：每次写操作后刷盘连接的进程需要有 `DirectoryName` 对应目录的读写权限，同时一个时刻只能有一个进程以 `read_write` 的方式打开 `Bitcask` 实例。
bitcask:open(DirectoryName) -> BitCaskHandle \| {error, any()}	在指定目录下以只读模式打开或新建一个 `Bitcask` 实例。连接的进程需要有 `DirectoryName` 对应目录及其内部所有文件的读权限。
bitcask:get(BitCaskHandle, Key) -> not_found \| {ok, Value}	获取指定键对应的值。
bitcask:put(BitCaskHandle, Key, Value) -> ok \| {error, any()}	插入一个键值对。
bitcask:delete(BitCaskHandle, Key) -> ok \| {error, any()}	删除指定键。
bitcask:list_keys(BitCaskHandle) -> [Key] \| {error, any()}	返回所有的键。
bitcask:fold(BitCaskHandle, Fun, Acc0) -> Acc	对每一个键值对应用 `Fun` 函数，`Fun` 的函数签名为 `F(K, V, Acc0) -> Acc`。类似于 `JavaScript` 的 `reduce`。
bitcask:merge(DirectoryName) -> ok \| {error, any()}	合并目录下的数据文件以减少重复的键值对。同时生成 `hintfile` 辅助加速程序启动时间。
bitcask:sync(BitCaskHandle) -> ok	强制刷盘。
bitcask:close(BitCaskHandle) -> ok	关闭 `Bitcask` 实例的连接并刷盘。

存储

文件组织

Bitcask 的文件组织非常简单，任意时刻目录下最多只有一个 active data file 接收写操作，其余都是不可修改的历史数据文件。任意时刻 Bitcask 只允许一个进程以写模式建立连接，写入进程只会向 active data file 写入，当其大小超过指定阈值后就会关闭当前文件，然后新建一个 active data file。

alt

数据格式

写入进程以追加写的方式写入 active data file，从而避免了随机写的磁盘寻址，其写入数据格式如下：

alt

crc：循环冗余校验码，验证数据完整性
tstamp：32位整型本地时间戳，仅内部使用，不对外暴露
ksz：键的长度
value_sz：值的长度
key：键的内容
value：值的内容

对于每一条记录，前面四个部分都是定长，以此为基址 base，则 base 到 base + ksz 就是键的内容，base + ksz 到 base + ksz + value_sz 就是值的内容。

如果要删除指定的键，Bitcask 会再次追加写入一个键值对，只不过写入的值是一个特殊值，程序后续读到这条记录时比较值的内容就可以判断该条记录是否已被删除。所以，Bitcask 每个文件内容就是一行行的记录：

alt

读写

写

Bitcask 写入的同时会在内存中维护写入的键到数据文件的映射（keydir）：
alt

其中 file_id 能够定位具体的数据文件，value_pos 是该条记录的值在文件中的起始偏移位置，那么 value_pos 到 value_pos + value_sz 就是值的内容。因为 Bitcask 每次写数据的长度是可知的，值在每条记录中的偏移量可知，写之前 active data file 文件总长也可知，所以 value_pos 也能够推算出来。

对于重复写入的键值对，磁盘上会存在同一个键的多条记录，但是 keydir 中始终只保留最新的映射。

读

读取时先根据键查询 keydir 得到数据文件的映射，然后根据 file_id 定位数据文件，最后根据 value_pos 和 value_sz 返回值的内容，整个读取只涉及一次磁盘寻址。另一方面，文件系统的 read-ahead 缓存会进一步减少磁盘的交互：

alt

数据合并

由于 Bitcask 追加写的特性，有两种类型的数据是冗余的：

被标记删除的数据
同一个键的旧版本的数据

所以，为了避免磁盘空间的浪费，需要额外的数据合并操作对磁盘上的数据瘦身。数据合并只处理只读的数据文件，遍历剔除掉已删除和旧版本的数据。另外，每一个合并后的数据文件同时额外有一个对应的 hint file：

alt

hint file 也是行记录的文件，每一行存储了：

tstamp：时间戳
ksz：键的长度
value_sz：值的长度
value_pos：值在数据文件中的起始地址偏移量
key：键

当程序启动时，如果 hint file 存在，那么就可以直接扫描 hint file 构建 keydir 从而加速程序启动；反之，则要扫描数据文件。

性能数据

原文并没有给出非常正规的测试报告，仅列出了一些早期未优化的测试数据：

读写延迟：毫秒内
写吞吐：5000~6000次/秒
内存占用：几百万的键在 1GB 内（keydir 需要）

总结

Bitcask 的整体设计思路非常简单，其设计目的也不是为了成为最快的 KV 存储，而是最适合 Riak 的存储引擎，在足够快的同时有着高质量、简洁的代码，设计和数据格式。

参考

Bitcask - A Log-Structured Hash Table for Fast Key/Value Data

GNU - 什么是自由的软件

Posted on 2025-01-04 Word count in article: 1.3k Reading time ≈ 2 mins.

定义

自由的软件的定义四要素：

以任何意愿，目的运行软件的自由
学习软件运行原理的自由，并且能按自主意愿修改（前提还需要能自由访问源代码）
将软件的副本再次分发给其他人的自由
将修改后的软件的副本分发给其他人的自由

一个软件只有具备了上述四点才是自由的软件。

不过，自由的软件不表示不能商用，相反，GNU 鼓励并且认为商用是自由软件社区成功的重要途径。自由的软件必须能够在商业上使用，开发，以及分发。

自由与非自由的边界

以任何意愿运行软件的自由

任何个人或组织可以在任意计算机系统上，出于任意目的运行软件，而不需要事先和开发者或者其他组织联系。同时，你也可以将软件再分发给其他用户，其他用户也能自由的以他们自己的意愿去运行软件而不受你的约束。

学习软件源代码并修改的自由

自由的获取软件的源代码是能够自由修改软件和再分发的前提，不过，经过代码混淆工具处理过的代码不算是源代码。

同时，如果对修改软件有限制，那么该软件也不算是自由的软件，例如：

某软件引用了修改后的软件 A，但不允许将其替换为你自己修改的版本
要求你成为所修改的代码的版权拥有者
只能做出其他人认为是改进的修改

软件再分发的自由

你可以自由的再分发未修改或修改后的软件副本给任何人，即使是收费。同时，你也可以自由的修改软件然后私用，而不需要让其他任何人知道；如果你将修改后的软件再分发，也不需要以任何形式知会任何人。

自由再分发的软件副本必须包含可执行文件，以及修改和未修改的源代码。不过有些软件可能（暂时）无法生成可执行的文件，但是依然要保留能够再分发可执行文件的自由。

Copyleft

版权的单词是 copyright，copyleft 与之对应。它要求所修改和扩展的软件都必须依然保留自由软件的四要素（而不仅仅是免费），GNU 自己的项目就使用符合 copyleft 的许可证来保证软件的自由。不过，这里并不是说所有自由的软件都必须用 copyleft 许可证，不然也违背了自由一词。

软件分发的约束

只要不限制分发修改后的软件的自由，不限制私用修改后的软件，对软件分发做一定程度的约束是可接受的。例如，要求给修改后的软件换个名字，删除原有软件的 logo，或者声明修改为你所有。

出口规定

有时候政府的出口管制会限制你在国际上分发软件的自由。虽然身为开发人员无法对抗这些规定，但是你可以做也必须做的是，不添加这些法律条文作为软件的使用条件。

合规考虑

如果软件的用户没有做任何不合规的事，那么软件的开发人员不能随意的撤销软件的许可证，或添加使用限制，否则这就不是自由的软件。

基于合约的许可证

有些基于合约的许可证会引入较多的使用限制，从而可能违背自由软件的四要素，因此这类许可证不被认为是自由的许可证。例如某些免费的软件许可证会规定允许被安装的设备的数量，以及限制分享给他人使用。

软件之外

软件的使用手册也必须是自由的，因为手册也是软件的一部分。再扩展一步，自由不仅仅是用在软件上，任何能够以数字形式呈现的产物都可以是自由的。

参考

个人向最喜欢的十款单机游戏

Posted on 2025-01-01 Word count in article: 817 Reading time ≈ 1 mins.

豆瓣个人评分标准：

五星：一见钟情，简直停不下来，必然多周目起步
四星：依然优秀，但是相比五星存在无法忽略的缺点，可能会多周目
三星：没什么吸引人的地方，大部分能坚持到一周目结束，基本不会多周目
二星：肉眼可见的烂，中途就弃
一星：还没遇到过

以下是个人向五星里最喜欢的十款单机游戏，重剧情、代入感，轻玩法、动作，按接触时间倒序。

赛博朋克2077

一开始被蠢驴泼天的 bug 劝退了，一直没有上手。不过，看到 DLC 往日之影发售之后大受好评，而且据说2.0版本相比初版已改进不少，遂抱着试试看的心理购入，最终真香，依然吃蠢驴这套。遗憾的是支线的量不够多，意犹未尽。

上古卷轴5

2024年才接触老滚5，而且还没装 Mod，玩了200小时之后依然觉得还有200小时的内容在等待发掘。个人认为老滚5和荒野之息体现了做开放世界的两个赛道，在老滚5里我能停下来和每个人对话，探索世界的动力在于我会遇到什么样的人，会发生什么事。

荒野大镖客2

R 星的另一个代表作道德与法治5由于缺少对三个主角的代入感，加上整体枪车戏份过多，玩了一遍后就没有重拾的动力。反而比较适合大表哥2慢悠悠的世界，最终随着结尾曲响起，代入感达到顶峰，仿佛失去了一位朋友。

女神异闻录5

中二的剧情，新奇的 UI，魔性的音乐，不知不觉就过了100小时，并且回合制战斗也不显得枯燥。

巫师3

蠢驴入坑之作，虽然相比老滚5显得并不开放，但丰富的支线加上优秀的音乐让人流连忘返。

最后生还者

线性叙事的巅峰，没有一丝冗余，剧情和动作完美结合，无时无刻不在关注下一秒的走向。

空之轨迹

一首星之所在伴随至今，相比于现在注水冗余的轨迹系列，剧情优秀，人物感情细腻。

三国志11

独特的水墨画风，恰到好处的音乐，相比于即时制更喜欢回合制的操控，能够一直待在电脑里，历史感十足。

太阁立志传5

自由度满分，做一个躺平散养的人，喝茶交友，四处乱逛，没有 KPI。

最终幻想10

很难想象当初顶着看不懂的日文玩到了最后，惊艳的 CG 和音乐，共情最深的 FF。

为什么 Python 的负整数除法结果和 C 不同

Posted on 2024-12-29 Word count in article: 1.6k Reading time ≈ 3 mins.

对于整数-5除以2，在 Python 中的结果是-3，但是在 C 中是-2。如果扩展到其他几种常见的语言，可以看到和 C 一致的比较多：

语言	结果
C	-2
C++	-2
Java	-2
C#	-2
Rust	-2
Go	-2
Python	-3
Ruby	-3

区别在于对于结果-2.5是选择向0取整还是向负无穷取整，Python 和 Ruby 选择了后者。

对于整数 a 和 n，记 a 除以 n 的结果是 q，余数是 r，则有：a = n * q + r，其中 |r| < |n|。在数论中，r 始终是正数，但是不同的编程语言各自有不同的实现。

In number theory, the positive remainder is always chosen, but in computing, programming languages choose depending on the language and the signs of a or n.

编程语言实现

Truncated division

很多语言采用这种实现，约定 $q = trunc(\frac{a}{n})$ ，其中 trunc 表示向0取整，代表语言如 Java。

Floored division

Donald Knuth 提倡这种实现，约定 $q = \lfloor \frac{a}{n} \rfloor$ ，即向下取整，代表语言如 Python。

Euclidean division

Raymond T. Boute 则提倡这种实现，约定：

q = sgn(n)\lfloor \frac{a}{|n|} \rfloor = \begin{cases} \lfloor \frac{a}{n} \rfloor & \text{if n > 0}\\ \lceil \frac{a}{n} \rceil & \text{if n < 0} \end{cases}

即根据 n 的正负号来判断是向下取整还是向上取整，代表语言如 ABAP。

Rounded division

这是 Common Lisp 和 IEEE 754 采用的实现，约定 $q = round(\frac{a}{n})$ ，其中 round 使用 rounding half to even，即在常规的取整之外，对于1.5，2.5，x.5这样的数字取整到最近的偶数，例如6.5取整到6，7.5取整到8。

Ceiling division

这是 Common Lisp 提供的另一种实现，约定 $q = \lceil \frac{a}{n} \rceil$ ，即向上取整。

Python 实现

回到 Python，很难说上述哪种实现一定最优，Python 的作者提到采用 floored division 是因为对于某些应用来说，如果取模运算返回负数没有意义。例如，给定一个 POSIX timestamp，如何返回该天的时间部分，即时分秒？因为一天有86400秒，假设时间戳是 t，那么 t % 86400 就表示该天过了多少秒，就可以进一步转化为时分秒。而对于在 1970-01-01T00:00:00Z 之前的日期，t 则是负数，采用 floored division 的情况下 t % 86400 依然返回正数，并且结果也是正确的，而 truncated division 则返回负数，需要应用程序进一步处理。

不过，一种编程语言中不一定只提供一种实现，其他实现可以借助函数库。例如，Python 中 -5 % 2 结果是1，实现方式为 floored division，但是 math.fmod(-5, 2) 结果是-1，实现方式为 truncated division。

参考

Snowflake 配置 S3 Storage Integration

Posted on 2024-03-31 Word count in article: 3.7k Reading time ≈ 6 mins.

介绍

Snowflake 的 Data Loading 和 Data Unloading 可以通过 S3 导入和导出数据。用户可以使用 AWS_KEY_ID 和 AWS_SECRET_KEY 来授权 Snowflake 访问 S3，不过出于安全和权限控制的考虑，一般不会这么做。

Snowflake 建议通过 Storage Integration 来管理权限。

获取 VPC ID

在配置 Storage Integration 前，需要设置 S3 策略。首先获取 Snowflake 的 VPC ID，后续的 S3 策略配置中将只允许该 VPC 访问。

允许特定 VPC 访问的功能要求 Snowflake 实例和对应的 S3 Bucket 运行在相同的 AWS 区域内。

切换到 ACCOUNTADMIN 角色在 Snowflake 中执行：

1 2	USE ROLE ACCOUNTADMIN; SELECT SYSTEM$GET_SNOWFLAKE_PLATFORM_INFO();

记录下返回的 VPC ID：

1	{"snowflake-vpc-id":["vpc-abc"]}

创建 IAM 策略

然后，需要创建一个 S3 策略来定义 Snowflake 访问 S3 Bucket 的权限。

从 AWS 控制台进入 IAM，在左侧导航栏 Access management 下选择 Account settings：

alt

在 Security Token Service (STS) 下查看所在区域的 STS 状态是否是 Active：

alt

接着，在左侧导航栏 Access management 下选择 Policies，之后点击 Create policy：

alt

切换到 JSON 后输入 S3 策略：

alt

下面的策略中 vpc-abc 是 Snowflake 实例的 VPC，snowflake-storage-integration-example 是示例 Bucket 的名字，unloading 和 loading 是该 Bucket 下的两个文件夹，分别用于 Data Unloading 和 Data Loading 使用：

{
	"Version": "2012-10-17",
	"Statement": [
		{
			"Sid": "Statement1",
			"Effect": "Allow",
			"Action": [
				"s3:PutObject",
				"s3:GetObject",
				"s3:GetObjectVersion",
				"s3:DeleteObject",
				"s3:DeleteObjectVersion"
			],
			"Resource": [
				"arn:aws:s3:::snowflake-storage-integration-example/unloading/*",
				"arn:aws:s3:::snowflake-storage-integration-example/loading/*"
			],
			"Condition": {
				"StringEquals": {
					"aws:SourceVpc": "vpc-abc"
				}
			}
		},
		{
			"Sid": "Statement2",
			"Effect": "Allow",
			"Action": [
				"s3:ListBucket",
				"s3:GetBucketLocation"
			],
			"Resource": [
				"arn:aws:s3:::snowflake-storage-integration-example"
			],
			"Condition": {
				"StringLike": {
					"s3:prefix": [
						"unloading/*",
						"loading/*"
					]
				},
				"StringEquals": {
					"aws:SourceVpc": "vpc-abc"
				}
			}
		}
	]
}

创建 IAM 角色

接着，创建一个 IAM 角色并绑定前一步创建的 S3 策略。在 IAM 左侧导航栏 Access management 下选择 Roles，之后点击 Create role：

alt

Trusted entity type 选择 AWS account，然后在 An AWS account 下选择 Another AWS account，Account ID 暂时先填当前账号的 ID，之后会修改：

alt

同时，选择 Require external ID (Best practice when a third party will assume this role)，External ID 暂时用一个假的例如 0000 替代，之后同样会修改：

alt

最后绑定先前创建的 S3 策略：

alt

创建角色之后，记录下角色的 ARN，接下来会用到：

alt

创建 Storage Integration

这时就可以在 Snowflake 中创建 Storage Integration 了：

CREATE STORAGE INTEGRATION snowflake_storage_integration_example
  TYPE = EXTERNAL_STAGE
  STORAGE_PROVIDER = 'S3'
  ENABLED = TRUE
  STORAGE_AWS_ROLE_ARN = 'arn:aws:iam::123:role/snowflake-integration-role'
  STORAGE_ALLOWED_LOCATIONS = ('s3://snowflake-storage-integration-example/loading/', 's3://snowflake-storage-integration-example/unloading/')

其中 STORAGE_AWS_ROLE_ARN 是之前所创建的 IAM 角色的 ARN，STORAGE_ALLOWED_LOCATIONS 是示例 Bucket 下的两个文件夹的地址。

只有授权了 CREATE INTEGRATION 权限的角色才能创建 STORAGE INTEGRATION，默认只有 ACCOUNTADMIN 才有这个权限。

获取 Snowflake 的用户 ARN 和 External ID

接着需要获取所创建的 Storage Integration 对应的 Snowflake IAM 用户的 ARN 和 External ID：

1	desc integration snowflake_storage_integration_example;

alt

记录下 STORAGE_AWS_IAM_USER_ARN 和 STORAGE_AWS_EXTERNAL_ID。

授权 Snowflake 用户

回到之前创建的 IAM 角色，在 Trust relationships 下替换掉之前填写的临时 Account ID 和 External ID：

alt

完成后，我们就可以执行一条 Data Unloading 命令来验证配置是否成功：

copy into 's3://snowflake-storage-integration-example/unloading/'
from (select OBJECT_CONSTRUCT_KEEP_NULL(*) from (select * from MY_DATABASE.MY_SCHEMA.MY_TABLE limit 10))
FILE_FORMAT = (type = json, COMPRESSION = NONE)
STORAGE_INTEGRATION = snowflake_storage_integration_example

如果配置成功，那么 Snowflake 会将表 MY_DATABASE.MY_SCHEMA.MY_TABLE 的数据导出到 s3://snowflake-storage-integration-example/unloading/ 文件夹下。

参考

【读】Newton 科学世界 - 就诊指南

Posted on 2024-03-03 Word count in article: 62 Reading time ≈ 1 mins.

翻到了一本压箱底的 Newton 科学世界，本期主题为 就诊指南，大概整理了一下，源文件。

alt

参考

Newton 科学世界（2022.5）

介绍

架构