本期关键词：Tectonic、Redlock、Flexible Paxos、明天的盐
Facebook’s Tectonic Filesystem: Efficiency from Exascale
这篇论文发表在 2021 年的 FAST 会议，介绍了 Facebook 自研的分布式文件系统 Tectonic，这个系统早在 2016 年就已经公开分享过，在内部又被叫做 Warm Storage。Tectonic 的目标是用一个系统同时满足对象存储（blob storage）和数据仓库（data warehouse）这两种截然不同的存储需求，目前已经有数十个租户（关于租户的概念后面会讲）以及 EB 级的数据量。
在介绍 Tectonic 之前需要先介绍 Facebook 在用的另外几个存储系统：Haystack、f4 以及 HDFS。Haystack 和 f4 都是 Facebook 自研的对象存储，HDFS 则是大数据数仓最主要的存储系统。
Haystack 的论文发表在 2010 年的 OSDI 会议，当时的 Facebook 已经存储了超过 2600 亿张照片以及 20PB 的数据，传统的存储方案并不适合管理这么大规模的图片，因此才有了 Haystack 这个系统。f4 的论文发表在 2014 年的 OSDI 会议，距离 2010 年 Facebook 存储的照片数量已经增长到超过 4000 亿张，Haystack 的存储变得越来越昂贵，急需一个更高效的存储系统来管理那些不常被访问的温数据，f4 的核心便是通过 Reed-Solomon（RS）编码来降低存储成本，在 f4 上线 19 个月以后总共存储了超过 65PB 的数据，并节省了 53PB 的存储空间。Haystack 的理论副本数（replication factor）是 3.6x，但是由于每块磁盘的 IOPS 不会随着磁盘容量的增加而有显著提升，因此 Haystack 集群需要额外配置大量的「空闲」磁盘才能满足系统对于 IOPS 的要求，导致实际的副本数增加到了 5.3x，相比之下 f4 的副本数是 2.8x。Haystack 对于 IOPS 的需求使得集群的存储容量明显过剩，而 f4 的数据因为不经常被访问磁盘的 IOPS 又有很多空闲，可以看到这两种系统的资源都有很大的浪费，也有明显可以互补的空间。
HDFS 已经是大数据领域存储系统的事实标准，它的优点不用过多介绍（有兴趣的同学可以看看第 8 期对 GFS 的介绍），缺点其实也很明显，因为 NameNode 是单点，不管是在可用性还是集群容量上都有很大限制。因此 Facebook 管理了数十个大大小小的 HDFS 集群，这不仅带来了很大的运维成本，对于上层服务来说也需要感知到不同集群的数据。按照 Facebook 目前的数据量，单个 HDFS 集群已经无法承载某些数仓的数据集，因此不得不把数据拆分到不同的集群，进一步将计算引擎的逻辑复杂化。
因此回到 Tectonic 面临的 3 个挑战（同时也是目标）：单集群支撑 EB 级数据存储，不同租户之间的性能隔离，以及支持一定程度的租户个性化定制。Tectonic 的架构由几部分组成：chunk 集群、元数据集群、无状态的后台服务以及客户端库。Chunk 集群负责存储数据；元数据集群负责管理文件系统目录结构、block 到 chunk 的映射关系等；无状态的后台服务负责如垃圾回收、数据重新均衡（rebalance）等工作；客户端库与 chunk 和元数据集群交互，并提供类似 HDFS 的 API。每个 Tectonic 集群支持十个左右的租户，租户之间不会共享数据，比如对象存储和数仓分别是不同的租户，每个租户同时又服务上百个应用，比如 Newsfeed、搜索、广告等。
在 Tectonic 中一个文件会被分割为数个 block，每个 block 又会由多个 chunk 组成，chunk 集群即是存储这些 chunk 的服务。这里的 block 是一个逻辑概念，chunk 集群并不感知，而是由元数据集群来维护文件到 block、block 到 chunk 的映射关系。论文中并没有说明每个 block 和 chunk 的具体大小，但是从后面列举的生产环境数据中可以大概估算出单个 block 的大小在 90MB 左右。Chunk 节点使用了 XFS 文件系统，每个 chunk 即为一个文件，对外暴露的接口包括 get、put、append、delete、list 以及 scan。每个 chunk 节点配置了 36 块硬盘（同样的根据生产环境数据可以算出单块硬盘的容量在 10TB 左右），并同时有一块 1TB 的 SSD 用于存储 XFS 的元数据以及缓存热的 chunk。数据复制的最小单元是 block，block 的持久性可以通过 Reed-Solomon 编码或者复制来完成。Tectonic 支持单独对每个 block 使用不同的持久化方法，而不是像其它系统一样是一个全局配置直接影响所有数据，也就是说可以在一个系统中实现多种复制策略。
在任何存储系统中，元数据都是整个系统的核心，Tectonic 的元数据设计有这么几个特点：存算分离，多层元数据，基于哈希分片，元数据缓存，read-after-write 一致性。下面分别讲解。
存算分离是指元数据集群分为逻辑节点和存储节点，逻辑节点是无状态的后面会提到，存储节点目前使用的是 Facebook 自研的分布式 K/V 存储 ZippyDB。ZippyDB 是基于 RocksDB 和 Paxos 来实现的分布式存储系统，广泛用于 Facebook 内部各种业务，如 Newsfeed、Instagram、WhatsApp 等。ZippyDB 根据 shard 进行复制，支持单 shard 内的事务操作，但不支持跨多个 shard 的事务。ZippyDB 也会自动地在不同节点之间进行 shard 迁移，实现负载均衡。Tectonic 的元数据会根据某个 ID 来分片进而分布到不同的 shard，例如目录 ID、文件 ID、block ID。
Tectonic 将元数据分为了 Name、File、Block 三层，Name 层保存的是文件系统的目录结构，File 和 Block 层分别保存文件到 block、block 到 chunk 的映射关系。之所以要把元数据拆分成多层结构，是为了避免请求热点，热点问题在大数据场景尤为常见，例如访问一个目录中的所有文件。这个设计与 Azure Data Lake Store（ADLS）非常类似，不过 ADLS 的元数据是范围分割（range partitioning）的，而 Tectonic 是哈希分割，在之前介绍如何设计一个分布式索引框架的文章中已经介绍过这两种数据分割方法各自的优缺点。简单讲范围分割的优点是可以快速扫描（比如递归遍历一个目录），缺点是容易产生热点，因此采用范围分割的系统通常都需要搭配一个好的自动负载均衡系统，动态分割、合并、迁移数据。哈希分割的优点是数据天然就是均匀分布的，也就没有了范围分割的热点问题，但是缺点是没法快速扫描。Tectonic 将近 2/3 的请求都是在 Block 层，因此哈希分割可以很好地实现负载均衡（想象如果采用范围分割那么一个目录中所有文件的 block 元信息可能都会集中在 1 个节点上）。有兴趣了解 ADLS 为什么采用范围分割的同学可以衍生阅读 Windows Azure Storage 的这篇论文。
Tectonic 允许 block、文件、目录被密封（seal），当一个目录被密封以后将不能在这个目录中创建新的对象（但是子目录不受限制）。因为文件系统中的对象一旦密封将不会被修改，所以他们的元数据可以缓存在元数据服务节点和客户端上，大大降低读负载，也不用担心产生一致性问题。一个例外是 block 到 chunk 的映射关系有可能被更新，例如 chunk 从一个磁盘迁移到另一个磁盘，此时需要失效 Block 层的缓存。当读取的时候会主动检测缓存是否过期，如果过期便会触发缓存更新。
为了保证同一个目录内的元数据操作的强一致性，Tectonic 依赖 K/V 存储本身提供强一致性的操作以及单分片内（in-shard）的 read-modify-write 级别的原子事务。具体来说，Tectonic 保证包括数据操作（如 append 和 read）、涉及单个对象的文件和目录操作（如 create 和 list）、同一个父目录内的移动（move）操作在内的这些操作的 read-after-write 一致性。ZippyDB 目前还不支持跨多分区（cross-shard）的事务，因此 Tectonic 也没法提供原子的跨目录移动操作，现在的实现是一个两阶段的过程。比如要把一个子目录从当前的父目录移动到另一个父目录，首先在新的父目录创建一个链接，然后删除旧父目录中的链接；跨目录的文件移动也是类似的，先把文件拷贝到新目录，然后从原目录中删除，这里的拷贝不会涉及到底层数据，仅仅是元数据维度的操作。
Tectonic 的客户端库通过编排元数据和 chunk 服务的信息来暴露一个文件系统抽象给上层应用，使得每个应用对每一次读写操作都可以非常灵活地控制。读写操作的粒度是 chunk，当写入数据时客户端库会负责复制或者 RS 编码这些 chunk，并且在读取的时候重新组织。Tectonic 限制每个文件同一时间只能有一个写入方（single-writer），当应用写入数据时需要先生成一个 token 并在打开文件时把这个 token 添加到文件的元数据中，此时如果有另一个应用也尝试写入，会用新的 token 覆盖当前写入方的 token，并且密封所有当前写入方已经打开的 block。如果应用需要多写入方的语义，可以在 Tectonic 之上实现。
以上是 Tectonic 核心的系统实现，不过 Tectonic 是面向多租户设计的，因此还需要解决多租户场景的很多问题，例如如何保障资源能公平分配给每个租户、如何在维持高资源利用率的情况下进行性能隔离、如何让每个租户有一定的定制空间去优化它自己的请求。
Tectonic 把资源分为两种类型：长期（non-ephemeral）和短期（ephemeral）。存储容量即属于长期资源，一旦分配给某个租户就不会再分给其它租户。每个租户会有一个预先定义好的容量配额，这个配额不会动态伸缩，需要手动调整。短期资源是那些随着时间需求不断变化的资源，比如存储的 IOPS 容量、元数据请求容量。因为短期资源需求变化得很快，所以需要一个细粒度的实时自动化管理来确保资源共享的公平性、资源隔离性以及高的资源利用率。
短期资源共享是 Tectonic 面临的一个比较大的挑战，原因在于不仅租户的需求是多种多样的，而且每个租户服务的应用也有着不同的请求模式和性能要求，比如对象存储类型的租户会同时包含来自 Facebook 生产环境的请求以及后台的垃圾回收请求。如果按照租户的粒度来管理短期资源将没法应对同一租户内部的不同需求，但如果按照应用的粒度来管理也不合适，因为 Tectonic 服务着上百个应用，应用这个粒度过于细也增加了管理的复杂度。
因此 Tectonic 把短期资源按照应用组的粒度来管理，这些应用组被叫做 TrafficGroup。同一个 TrafficGroup 中的应用有着相似的资源和响应时间要求，比如一个 TrafficGroup 是来自生产环境请求的应用组，另一个 TrafficGroup 是来自后台服务请求的应用组。每个 Tectonic 集群支持大约 50 个 TrafficGroup，每个租户都有不同数量的 TrafficGroup，租户需要负责为他们的应用选择适合的 TrafficGroup。每个 TrafficGroup 会对应一个 TrafficClass，TrafficClass 用来描述对于响应时间的需求以及决定哪些请求可以获得空闲资源。目前有 3 种 TrafficClass：黄金、白银、青铜，分别对应延迟敏感、普通和后台应用。空闲资源会根据不同 TrafficClass 的优先级来分配到同一租户内的不同应用，如果某个租户的资源有剩余，会优先给它自己的 TrafficGroup，之后才是给其它租户。
客户端库通过一个速率限制器（rate limiter）来控制请求速率，这个速率限制器基于 leaky bucket 算法实现，通过一个高性能、近实时的分布式计数器来统计近期每个租户、每个 TrafficGroup 的请求次数。当客户端发起请求时会增加计数，同时会按照自己的 TrafficGroup、同租户内的其它 TrafficGroup 以及其它租户的顺序检查是否有空闲容量，如果有，请求会继续发送给后端，如果没有则请求会被延迟发送或者拒绝，具体如何处理视请求的超时时间而定。
为了保障在每个存储节点上黄金 TrafficClass（延迟敏感）应用的请求不会被低优先级请求阻塞，Tectonic 实现了一个权重轮询（weighted round-robin，WRR）调度器。具体的，WRR 有三个策略。首先当调度器认为低优先级请求可以延迟执行时就会优先执行更高优先级的请求，如何界定是否可以延迟执行是通过一个贪心优化来实现，简单理解是确保低优先级请求延迟执行以后也有足够的时间来完成。其次，调度器会限制每个磁盘即将执行（in flight）的非黄金等级的 IO 请求数量，如果超过设定的阈值这些低优先级请求就会被阻塞。最后，如果某个磁盘的黄金等级的请求已经等待了足够长时间还没有被执行，将会停止调度非黄金等级的请求到这个磁盘。
每个 Tectonic 集群支持大约 10 个租户，每个租户可以根据自己的需求非常灵活地控制请求。这个灵活性主要得益于两点：客户端库能够直接在 chunk 粒度操作数据，以及为每次请求设置不同的配置。其它一些系统（如 HDFS）只支持目录级别的持久性配置，然而 Tectonic 能支持到 block 级别。论文接下来分别介绍了 Tectonic 在数仓和对象存储这两种类型场景如何进行针对性优化，简单总结几个点：数仓场景写入时会等数据缓冲到一整个 block 大小以后再进行 RS 编码；长期数据用 RS(9,6) 编码，短期数据（如 shuffle 数据）用 RS(3,3) 编码；写入数据前会先发送预留请求，且请求会超过实际所需的节点数（如 RS(9,6) 会发送给 19 台存储节点）；对象存储场景写入时只要大多数节点返回就代表请求成功；当 block 被密封以后会按照 RS(10,4) 进行编码。从评测结果来看，Tectonic 在读写性能上基本和 Haystack 相当，但整体还是要更慢一些，特别是长尾读请求（如 P95、P99）。
论文中分享了一些 Facebook 生产环境的真实数据，某个 Tectonic 集群一共有 4208 台存储节点，总容量是 1590PB，目前已经使用了 1250PB，总共 100.7 亿文件和 150 亿 block。这个集群有两个租户，也就是对象存储和数仓，对象存储大约使用了 49% 的空间，剩下 51% 是数仓。从 IOPS 和吞吐看，对象存储请求一直比较稳定，而数仓则有明显的波峰波谷。三层元数据服务按 QPS 从大到小排列分别是：File、Name、Block，每个元数据分片最高能支撑 1 万 QPS，只有 1% 的 Name 层请求超过了这个最大 QPS 限制。
最后是一些在 Tectonic 设计过程中的权衡、妥协和总结。之所以选择通过客户端库而不是代理与底层交互是为了减少网络、硬件开销（Tectonic 每秒的网络吞吐能达到 TB 级），当然客户端库这个方案也有缺点，比如库的稳定性会直接影响应用。在跨数据中心访问的场景还是需要通过代理，客户端库直接请求不适合。Tectonic 的元数据性能相比 HDFS 还是差不少，毕竟 NameNode 是全内存存储也不涉及多分区操作，因此在使用 Tectonic 时应用可能也需要做一些优化，例如重命名一批文件在 HDFS 中可以一个一个串行操作，但是在 Tectonic 中计算引擎需要并行操作。因为 Tectonic 是哈希分割数据，所以并不支持递归遍历目录，也就不支持类似 HDFS 中的 du 操作，一个变通的实现是 Tectonic 会周期性地聚合每个目录的统计信息。第一版 chunk 存储会将多个 block 组合并进行 RS 编码，目的是减少元数据，但是后来发现这样会大幅降低集群的可用性。最初 Name 和 File 层元数据也没有分开，直到后来发现容易产生热点才分开。在 Tectonic 这个量级内存数据损坏变得非常常见，因此在各个环节都需要强制检查 checksum 来保证数据的完整性。
总的来说 Tectonic 的设计比较简洁，没有太多外部依赖。在 EB 级这个数据规模元数据管理是一个很大的挑战，用一套存储系统来满足不同类型租户的需求也是一个很有意思的点，虽然单纯从性能上比较肯定不如专有系统，不过很多时候性能并不是唯一的衡量因素。尽管叫做文件系统，但也牺牲了一些传统文件系统的特性（如 POSIX 兼容），这也大大简化了很多方面的系统设计。
How to do distributed locking
这篇文章来自 Martin Kleppmann，他同时也是著名技术书籍《Designing Data-Intensive Applications》的作者，曾在 LinkedIn 工作。文章源自他写书过程中做的各种研究，主要论证了 Redis 官方的分布式锁 Redlock 的设计是否足够安全。具体论证过程可以查看文章，大体的结论就是 Redlock 用一个复杂的设计实现了一个并不安全的锁，特别是 Redlock 的算法依赖了一些危险的假设（比如时间、系统时钟），一旦这些假设不成立，锁的安全性将很容易被打破。这篇文章的草稿其实也被 Redis 的作者 Salvatore Sanfilippo 审核过，Salvatore 后来还在自己的博客上写了一篇叫做「Is Redlock safe?」的文章来逐一反驳 Martin 的观点，不过 Martin 表示自己依然坚持之前的观点。
A More Flexible Paxos
这篇文章来自 Sugu Sougoumarane，这个名字你也许陌生，不过他是著名开源项目 Vitess 的创始成员之一，曾在 YouTube 和 PayPal 工作。文章的主题是介绍一种更灵活的 Paxos 算法实现，通常我们对于共识算法的理解都认为当进行 leader 选举或者复制数据时需要至少多数票（quorum）才能保证分布式系统的强一致性，但是 Sugu 提出一个假设，在包含 N 个节点的集群中，如果参与选举的节点数是 L，参与数据复制的节点数是 P，那么只要 L + P > N，这个算法依然是可靠的。例如集群有 11 个节点，传统上需要 11 / 2 + 1 = 6 个节点参与选举和数据复制，按照新的算法可以用 9 个节点参与选举，然后用 11 - 9 + 1 = 3 个节点参与数据复制。这个新算法带来的好处是随着 N 的增大不会影响写性能（更小的 P）。无独有偶，Heidi Howard、Dahlia Malkhi 和 Alexander Spiegelman 也有类似的观察（上一期曾经提到过 Dahlia），并写了一篇论文称之为 Flexible Paxos。目前 Flexible Paxos 最著名的实现恐怕就是 Facebook 开源的 LogDevice，已经被用在了包括 Scribe、TAO、机器学习 pipeline 等场景。
昨天的黎忘年和明天的盐
最早听说黎忘年是来自一个朋友介绍，这个朋友和黎忘年是浙大校友，虽然不同级也不同专业，但因为有着音乐这个共同的爱好而结识。初次见面觉得这个男生瘦瘦高高，讲话声音也不大，没想到后来竟然组建了一个后朋乐队，也就是「智齿」。从智齿的音乐能听出很多乐队的影子，比如 Joy Division、P.K. 14，看过唯一一次智齿的现场是在上海的老育音堂，那天他们翻唱了 P.K. 14 的《快》，现在想来也是比较幸运的，因为后来智齿就解散了，留下了一张由杨海菘制作的专辑。智齿虽然解散了，但是黎忘年的乐队生涯还在，最新的乐队叫做「明天的盐」，这篇采访中也透露了今年将会发布首张专辑，制作人是我非常喜欢的音乐人杨帆。