本期关键词：InfiniFS、Decentralized Social Networks、杨海崧
InfiniFS: An Efficient Metadata Service for Large-Scale Distributed Filesystems
本期是关于分布式文件系统论文的又一期解读，再之前已经介绍过如第 1 期的 CFS（也就是 ChubaoFS，后来又改名叫 CubeFS）、第 8 期的 GFS 以及第 10 期的 Tectonic。
本期介绍的这篇论文发表在 2022 年的 FAST 会议（和 Tectonic 一样），论文作者大部分来自清华大学的存储研究组（Storage Research Group），这个研究组过往发表的论文都集中在存储领域，仅分布式文件系统就有至少三四篇相关的论文，本篇基本算是这个研究系列的最新成果，感兴趣的同学可以去他们的网站查看历史发表的论文。本篇论文还有一个作者来自阿里云分布式存储团队，因此也能在论文中看到很多数据是基于阿里云的盘古来分析的，不过文中并没有透露这个文件系统目前是否有在阿里云中正式使用。另外这个来自阿里云的同学的个人博客也有挺多不错的内容，也都是围绕在分布式系统相关的话题。
铺垫了这么多我们来实际看看这个被称为 InfiniFS（名字挺有野心）的分布式文件系统到底有什么独特之处吧，和前几期介绍的系统不太一样的地方是，本文核心的关注点是在文件系统的元数据管理，而关于数据存储的部分则不是本文的重心（论文中也压根没提）。论文摘要中已经简要概括了 InfiniFS 的几个独特的设计点：
- 把目录元数据中的 Access 和 Content 进行分离：这样分割（partition）目录树以后既能满足元数据的数据本地性，也能实现负载均衡。关于这里的 Access 和 Content 具体是指什么元数据后面会详细介绍；
- 设计了一个可推测的路径解析（speculative path resolution）方法：这样可以把路径解析并行化，熟悉文件系统的同学应该能理解这个优化能带来什么显著变化；
- 在客户端引入一个乐观访问的元数据缓存（optimistic access metadata cache）：再强大的服务端也架不住茫茫多的客户端，一定程度的客户端缓存还是需要的。
经过这些优化设计以后 InfiniFS 号称可以支撑千亿级的文件存储并提供可观的性能，在论文最后的实验验证环节他们也的确模拟了这么大量级的测试数据。
在正式介绍这三个优化的详细设计之前，先来了解一下背景，也就是最初设计 InfiniFS 的动机是什么（当然不只是为了发论文）。文中首先提出了当下分布式文件系统元数据设计的几个特点：
- 首先文件的元数据都是按照目录树（directory tree）的组织形式来管理的，这是个非常自然的设计，因为我们已经习惯于按照目录树来管理文件（计算机里之所以采用这种管理形式应该也是将现实生活中的方式直接映射过来，具体原因可能要考据一下计算机交互设计的历史）；
- 在以目录树为基础设计的元数据访问中有两个关键步骤，一个是路径解析，一个是处理元数据。所谓「路径解析」可以举个栗子，当我们想要访问一个文件时首先需要提供一个文件路径，比如
/home/alice/abc.txt，可以看到这是一个多级路径，分别是home/、alice/和abc.txt，这里面的每一部分都有对应的元数据，路径解析就是获取每部分的元数据，通常路径解析是串行的，也就是先解析home/，再解析alice/，最后解析abc.txt，也就是说路径越长花费在路径解析上的时间也会越长。「处理元数据」对应的就是实际的元数据操作，比如重命名、修改权限、移动文件等。
由于元数据服务在整个文件系统中的角色至关重要，因此很容易就成为瓶颈。随着数据量的增长，数据存储服务可以相对容易地横向扩展，但是元数据服务往往比较困难。于是在分布式文件系统的运维实践中，人们通常倾向于管理很多个小的集群，而不是管理一个非常大的集群（况且很多文件系统往往也支撑不了特别大的规模）。文中举了一个实际的栗子，阿里云上目前已经运维了近千个盘古文件系统集群来支撑数据中心百亿级的文件存储需求。Facebook 也同样如此，因为单个 HDFS 集群最多能支撑 1 亿左右的文件，所以在 Facebook 内部维护了很多大大小小的 HDFS 集群（这一点在第 8 期介绍的 Tectonic 里也有说明）。
运维数个分布式集群的成本显然不小，而仅用一个集群就能支撑整个数据中心存储需求的「诱惑」又是如此之大，人们才会想要不断探索和突破。关于运维单一文件系统的好处这里就不再赘述，同样可以参考第 8 期里 Tectonic 的内容。
以上就是 InfiniFS 设计的背景和动机，简单讲就是希望通过优化元数据服务来支撑更大规模的数据存储需求。具体优化的几个点前面已经简单介绍过了，下面会详细说明。
首先来看看 InfiniFS 中具体有哪些组件（注意这个系统只包含元数据的部分，不包含数据存储）：
- 客户端：与大多数分布式文件系统一样，InfiniFS 有一个专用的客户端，这个客户端以用户态库或者 FUSE 的形式存在，也就意味着 InfiniFS 支持 POSIX 接口（是否完全兼容 POSIX 论文中并没有说）。前面提到的 3 个设计亮点中的 2 个都与客户端有关，包括「可推测的路径解析」和「乐观元数据缓存」。
- 元数据服务器：文件系统的目录树通过前面提到的「access-content 解耦分割」的方法分布到集群中不同的元数据服务器上。每个元数据服务器将这些元数据存储到本地的 KV 存储中，这里的 KV 存储通常会将元数据缓存在内存中，以及通过追加日志（append log）的形式将数据持久化到 NVMe SSD 盘上（虽然论文里没有明说用的是什么 KV 存储，但估计是类似 LevelDB、RocksDB 的组件）。同时元数据服务器上还会维护一个「缓存失效列表（invalidation list，简写为 Inv. List）」，顾名思义这个列表是和客户端的元数据缓存有关的，后面在介绍「乐观元数据缓存」时会详细解释工作机制。
- 重命名协调器（Rename Coordinator）：InfiniFS 的最后一个组件是重命名协调器，这个组件主要用来处理目录
rename和目录set_permission请求。重命名协调器会通过「重命名图（renaming graph）」来检查并发的目录重命名以防止局部死循环（orphaned loop），同时还会广播修改信息给元数据服务器以更新缓存失效列表。
接下来依次介绍 InfiniFS 的 3 个设计亮点，即：Access-Content 解耦分割、可推测的路径解析、乐观元数据缓存。
在理解「Access-Content 解耦分割」的好处之前得先了解常见分布式文件系统中分割目录树元数据的挑战是什么。第一个挑战是保证元数据的本地性（locality），简单讲就是把相互关联的元数据尽量放到一个元数据服务器上。这背后的缘由是因为一个文件系统操作通常会同时涉及多个元数据的修改，比如「创建文件」这个操作需要先锁住父目录（以保证目录列表的一致性），然后原子更新 3 个元数据（包括文件的元数据、父目录的文件列表以及目录的时间戳）。想象一下如果这些元数据分布在不同的元数据服务器上，势必需要引入分布式锁和分布式事务来保证一致性，但是分布式锁和分布式事务的开销是很大的，如果能分布在同一个元数据服务器上可以大大简化设计以及大幅提升性能。第二个挑战是负载均衡，这个挑战和第一个看起来似乎是悖论，理想情况下把所有元数据放在同一个服务器上的话肯定能最大化本地性，但这个服务器很自然也就变成了单点，没法负载均衡。同一个目录树下的所有文件很可能在短时间内被频繁访问，从而导致局部热点。
现有分布式文件系统分割元数据的方法可以大体上总结为两类：细粒度分割（Fine-grained Partitioning）和粗粒度分割（Coarse-grained Partitioning），这两类方法都只能满足「本地性」或「负载均衡」中的任意一点，无法同时满足。比如细粒度分割通常的做法是无脑哈希元数据（论文中引用的例子是 HopsFS 和 Giraffa），这种方式最大限度地提升了负载均衡的能力，但同时也牺牲了元数据本地性。反之粗粒度分割通常的做法是将文件系统的元数据按照子树为单元进行拆分，并分布到不同的服务器上，这样元数据本地性能获得一定的保障，但显然会产生负载不均衡的问题。
InfiniFS 的作者认为以上两种方式没法同时满足本地性和负载均衡的根因在于把目录的元数据看作了一个整体，在他们看来目录的元数据由两个独立的部分组成：Access 和 Content。Access 元数据指的是目录名、目录 ID（应该是指 inode）、权限等，顾名思义这些是与访问目录有关的信息。Content 元数据包含条目列表（entry list）、时间戳等，这些是与当前目录的子目录或子文件相关的信息。通过分析所有元数据操作可以将它们分为 3 类：仅处理目标文件/目录、处理目标文件/目录以及父目录、重命名（这是个特例后面会单说）。因此可以通过把「目录的 Content 元数据」与「子目录的 Access 元数据」及「文件的元数据」组合在一起的方式满足元数据本地性的需求，同时「目录的 Content 元数据」按照当前目录的 ID 哈希分割、「目录的 Access 元数据」和「文件的元数据」都按照父目录的 ID 哈希分割。还是继续拿前面举的「创建文件」操作为栗子，因为文件的元数据和父目录的 Content 元数据是组合在一起的，并且它们都是基于同一个 ID（父目录的 ID）哈希分割，因此创建文件必定是在一个元数据服务器上完成的，同时哈希分割也可以很自然地分散请求负载。
然后来看看「可推测的路径解析」。前面已经讲过随着文件在文件系统目录树中的深度越深，路径解析的成本也越高。这其中的根本原因就是每一级目录的 ID（或者说 inode）都是未知的，只有通过逐级解析才能最终获取到想要访问的目录或文件的元数据。这也就是为什么 InfiniFS 要提出可推测的路径解析的原因，当每一级目录的 ID 是可推测时，路径解析流程就可以由串行执行变成并行执行。
要实现「可推测的路径解析」第一步就是生成可推测的目录 ID，而不能单纯用一个递增数字作为 ID。当创建一个新目录时，InfiniFS 的做法是哈希这样一个三元组 <第一个父目录的 ID，新目录的名称，名称版本号>，哈希得到的结果即为这个新目录的 ID。新目录的第一个父目录被形象地称作「生父（birth parent）」，之所以强调第一个是因为目录在创建以后可能被移动到其它父目录下，但生父只会有一个。生父会记录一个「重命名列表（rename-list，简称 RL）」，这个列表中的元素是 <子目录的名称，名称版本号> 这样的数据结构。同时子目录会记录一个「回溯指针（back-pointer，简称 BP）」，这个指针的数据结构是 <生父的 ID，名称版本号>。RL 和「目录的 Content 元数据」存储在一起，BP 和「目录的 Access 元数据」存储在一起。RL 中记录的是所有「出生」在这个目录中并且已经被移动到其它地方的子目录，一个目录被移动以后它的 BP 依然指向的是生父。「名称版本号」的初始值都是 0，它存在的目的主要是为了解决目录移动（或者说重命名）后可能导致的名称冲突。
这里举一个实际的栗子，假设当前的目录结构是 /A/B，根目录的 ID 是 1， A 目录的 ID 是 2，B 目录的 ID 是 hash(2,B,0) = 3。然后把 /A/B 移动到 /B，此时需要做几件事情：
- 移动
B目录的 Access 元数据到新的元数据服务器，因为B目录的父目录从A变成了根目录，所以 Access 元数据哈希分割的 key 也变成了根目录； - 在
A目录的 Content 元数据中新增 RL 条目，值为<B,0>； - 在
B目录的 Access 元数据中记录 BP，值为<2,0>； - 注意
B目录的 ID 并没有变（因为生父没变），依然是 3。但是这里留了一个疑问就是如果B目录的名称也变了那它的 ID 是否会变呢（通常来说文件系统中的 inode 应该是不变的）？
此时如果在 A 目录下又创建一个 B 目录（假设叫 B'），因为 A 目录的 RL 中已经记录了一个同名的目录，所以「名称版本号」要加 1，因此这个 B' 目录的 ID 是 hash(2,B,1) = 13。如果没有「名称版本号」，就会生成重复的目录 ID，这是绝对不允许的。如果先把 /B 目录删除，除了 B 目录自身的元数据以外还会删除它的生父（即 A 目录）的 RL 条目。删除 RL 条目也就意味着「名称版本号」减 1，下一次创建 /A/B 时「名称版本号」就已经回到 0 了。引入「名称版本号」从理论上保证了目录 ID 的唯一性，但是哈希算法是有一定概率碰撞的，即便 InfiniFS 已经用了密码学哈希算法（比如 SHA-256）来尽量减少碰撞概率。如果发生碰撞，InfiniFS 的处理方法和刚才举的移动目录的栗子一样，即通过名称版本号、RL 和 BP 来保证生成的 ID 是唯一的，同时也可以通过 RL 中条目的格式来区分它是因为哈希碰撞还是重命名导致的。
知道了怎么生成可推测的目录 ID，路径解析的流程就比较清晰了，大概分为以下几步（这里以解析 /A/B/C/foo.txt 路径为例）：
- 客户端使用某种哈希算法计算每一级目录的 ID，即
A、B、C这 3 个目录的 ID，这一步是串行的。计算时假设「名称版本号」都为 0，根据前面的介绍应该能发现计算出的 ID 有可能是错误的，后面会讲如何处理这种情形； - 客户端发送 lookup 请求到元数据服务器，因为步骤 1 已经计算出了每一级目录的 ID，所以这一步是并行的。Lookup 请求获取的是每一级目录的 Access 元数据，元数据服务器会返回这个目录的「真实 ID」和对应的权限信息。比如 lookup
B目录，请求的参数是父目录（即A目录）的 ID 和B目录的名称，假设这个B目录的生父不是A目录，此时元数据服务器返回的B目录的「真实 ID」一定不等于步骤 1 中计算的 ID（「名称版本号」不为 0）。当遇到这种情况时客户端会以B目录作为起点回到步骤 1 重新开始； - 不断重复步骤 1 和步骤 2 直到得到所有目录的真实 ID，其实最终目的是为了获取最后一级目录（即
C目录）的真实 ID。
可以看到上述算法的最坏情况是所有中间目录的「名称版本号」都不为 0，这种情况的时间复杂度肯定比传统的路径解析算法高不少，但这属于小概率情况，大部分时候应该可以在 1 次迭代中完成。
最后介绍 InfiniFS 的乐观元数据缓存设计。InfiniFS 只会在客户端缓存目录的 Access 元数据，即目录名称、目录 ID 和目录权限。这些缓存是以文件系统目录树的结构组织，这棵树的所有叶子节点会连接在一起组成一个列表，当需要淘汰缓存时，会根据 LRU 算法从叶子节点列表中驱逐条目，这个算法能最大程度保证根目录元数据的缓存命中率（因为根目录更容易成为访问热点）。目录的 Access 元数据会因为 rename 和 set_permission 操作而失效，主动失效所有客户端的元数据缓存显然成本比较高，InfiniFS 的选择是把与缓存失效相关的信息主动推送到元数据服务器上，毕竟相比客户端的数量，元数据服务器的数量会小不少。所谓「乐观元数据缓存」就是客户端任何时候都乐观地认为自己的缓存是最新的，并以这个缓存为基础来请求元数据服务器，因为元数据服务器拥有最新的缓存失效信息，所以元数据服务器可以判断当前请求的客户端上的元数据缓存是否已经过期，如果过期就会告知客户端更新或者失效缓存。在具体实现上元数据服务器会维护一个「缓存失效列表」，这个列表中的每个条目包含两个信息：版本号以及对应的操作（如 rename、set_permission），版本号是递增的，当产生了需要失效缓存的操作时客户端会推送到所有元数据服务器，元数据服务器会在「缓存失效列表」中记录一个新的版本号。同时每个客户端本地也维护了一个版本号，这个版本号有可能小于元数据服务器上的「最新」版本号。当客户端请求元数据服务器时会带上操作的「路径名」和「自己本地的版本号」，元数据服务器可以将它们与「缓存失效列表」中的版本号进行对比，一旦发现客户端操作的路径名已经有变化就会告知客户端最新的版本号和对应的信息。
至此基本将 InfiniFS 的 3 个设计亮点介绍完毕，当然还有很多细节没有涉及，比如分布式事务如何实现（InfiniFS 用的是 2PC）、重命名协调器的工作机制是什么，有兴趣的同学可以继续阅读论文了解。论文最后的验证章节的数据也挺有意思，例如在比较元数据集群的横向扩展能力时，通过与 LocoFS（这是 InfiniFS 团队的上一篇文件系统论文）、HopsFS 和 CephFS 的比较中发现只有 InfiniFS 的吞吐（每秒处理的操作数）可以随着元数据服务器的数量增长而线性增长，HopsFS 和 CephFS 甚至在集群规模已经扩大了 32 倍的情况下吞吐也只有一点点增长。另一个验证是评估存储不同规模文件时的元数据集群吞吐变化，这个测试一直测到了 1 千亿文件，不敢说这是目前分布式文件系统的存储上限（理论上肯定还可以继续横向扩展），但是从现实世界的数据来看已经能满足单个数据中心的存储需求了（比如 Tectonic 论文中披露的数据是总共存储了约 100 亿文件，阿里云的一个数据中心里也存储了约 100 亿文件）。InfiniFS 在不同存储规模下的吞吐表现基本保持在一个恒定的水平，也就是说不管存储多少数据 InfiniFS 都能提供稳定的性能保障。
InfiniFS 的编程语言未知，目前也没有开源（大概率应该不会开源），是否已经应用在阿里云上也未知。另外「华中大高性能体系结构与系统实验室」完整翻译了本篇论文，可以点击这里查看。
Decentralized Social Networks
这篇文章来自 Jay Graber，你可能对于这个名字比较陌生，但你有可能听过最初由 Twitter 公司发起的去中心化社交媒体项目 Bluesky，而 Jay Graber 目前是 Bluesky 项目的总负责人。不过本期并不是要介绍 Bluesky，关于这个项目以后可以慢慢聊。这篇文章也并不是要聊区块链，当下有一个不好的风气，就是一旦提到「去中心化」似乎就必须和区块链扯上点什么关系，但是如果你纵观计算机的发展历史，去中心化是一个非常古老的概念，区块链只能说是去中心化的一种形态，并不是唯一的实现方式。
本文发表于 2020 年年初，聚焦在介绍有别于中心化社交网络的两种新形态：联邦（federated）网络和点对点（P2P）网络，以及基于这两种网络的社交产品。所谓「联邦网络」就是用户自由选择接入一个服务器，他可以通过这个服务器以一种「标准开放的协议」阅读和发布内容，而接入服务器同样以这个协议与这个网络中的其它服务器通信，进而传播不同用户产生的内容。与中心化网络的区别是，联邦网络的服务器并不是由某一个公司掌控，所有处于这个网络中的节点都可能分布在大大小小不同的组织中，这里的「组织」可能是某个人也可能是某个公司。联邦网络的一个实际例子就是 Email，Email 的收发协议是标准且公开的（IMAP、POP3、SMTP 等），任何邮件服务提供商和邮件客户端都需要依照这些协议来实现，因此用户可以选择任何客户端与邮件服务商通信。但是联邦网络的弊端是用户很难甚至无法在不同服务商之间迁移，想象一下把你的 Gmail 帐号迁移到其它地方的成本会有多大。
另一个更加松散的网络就是「P2P 网络」，在这个网络中没有服务端和客户端的区别，任何一个节点都可能同时具有这两种角色，这给予用户最大程度的控制权，不论是数据还是帐号，因此用户切换「服务商」（准确说在 P2P 网络中用户自己就是服务商）的成本是很低的。P2P 网络的弊端也很明显，换取松散自由以及完全的掌控权的代价是每一个用户都需要成为联邦网络或者中心化网络中的那个服务商，这意味着用户不仅要付出资源（CPU、内存、磁盘等），还需要自己来维护网络，保证这个网络的稳定性和一致性，甚至要以牺牲效率为前提。
鹈鹕 Hits 043 | 回顾兵马司，杨海崧觉得最可惜的是什么？
在 Maybe News 的「关于」中已经介绍过这个项目的名字由来，而标题中的「杨海崧」则是现在兵马司厂牌的主理人。如果你关注中国近代的摇滚乐，即便没有听过杨海崧也可能听过 P.K. 14 这个乐队（喜不喜欢另说）。P.K. 14 的乐队成员（包括历史成员）对于中国摇滚乐（特别是独立摇滚）的发展有着无法忽视的影响，比如曾经的鼓手华东目前是乐队「重塑雕像的权利」的核心，现任吉他手许波是豆瓣的 5 号员工（豆瓣音乐人、豆瓣 FM、阿比鹿音乐奖都与他有关）、曾经的大福唱片主理人、现在的美丽唱片主理人。
稍微扯远了，本期介绍的是由鹈鹕 Hits 采访杨海菘的一期播客，除了 P.K. 14 乐队成员这个身份，杨海菘日常还会作为制作人给很多乐队（以兵马司厂牌的为主）制作专辑。因此这期播客首先聊了聊杨海菘最近为这些乐队制作专辑的感想和背后的故事，在聊天的过程中穿插着介绍了几个有意思的新乐队，比如今日出品、暴力香槟。也聊到了杨海菘自己的最新分支项目弗拉基米尔，你在这个神奇乐队的介绍里根本看不出乐队成员具体有谁，但是听了这期播客就能知道（其实都是「老朋友」）。最后推荐一张专辑《Mind Shop》，来自已经解散多年的上海乐队 Muscle Snog。