D98dae758b492337afdc10c1ed51e3ba
F4 —— Facebook 的温存储系统

概览

首先说下 BLOB 的意思, 英文全称是 Binary Large OBjects,可以理解为任意二进制格式的大对象;在 Facebook 的语境下,也就是用户在账户里上传的的图片,视频以及文档等数据,这些数据具有一次创建,多次读取,不会修改,偶尔删除 的特点。

之前简单翻译了 Facebook 的前驱之作 —— Haystack,随着业务量发展,数据量进一步增大,过去玩法又不转了,如果所有 BLOG 都用 Haystack 存,由于其三备份的实现,在这个量级下,性价比很低。但是完全用网络挂载+传统磁盘+Unix-like(POSIX)文件系统等冷存储,读取跟不上。于是计算机科学中最常用的分而治之的思想登场了。

他们首先统计了 BLOBs 的访问频次与创建时间的关系,然后提出了随着时间推移 BLOB 访问出现的冷热分布概念(和长尾效应差不多)。并据此提出了热、温分开的访问策略:用 HayStack 当做热存储去应对那些频繁访问的流量,然后用 F4 去响应剩下的不那么频繁访问的 BLOB流量,在此假设(F4只存储那些基本不怎么变动,访问量相对不大的数据)前提下,可以大大简化 F4 的设计。当然有个专门的路由层于两者之上进行了屏蔽,并进行决策和路由。

对于 Haystack 来说,从其论文出来时,已经过去了七年(07~14)。相对于当时,做了少许更新,比如说去掉了 Flag 位,在 data fileIndex file 之外,增加了 journal file,专门用来记录被删除的 BLOB 条目。

对于 F4 来说,主要设计目的在于保证容错的前提下尽可能的减小有效冗余倍数effective-replication-factor),以应对日益增长的温数据 存取需求。此外更加模块化,可扩展性更好,即能以加机器方式平滑扩展应对数据的不断增长。

我总结一下,本论文主要高光点就是温热分开,冗余编码,异地取或

数据量级

到2014年,Facebook 大概有超 4000 亿张图片。

访问频度的热力图

论文的结论是,访问频度的热力图是存在的,创建时间是影响其变化关键因子,而且温部数据是持续增长的

论文的度量方法也很简单,就是追踪其网站上不同类型的 BLOB 数据的访问频次随着创建时间变化曲线,创建时间小于一天的数据的访问频次大概是创建时间一年的数据的100多倍。具体数据就不列了,可以去 paper 里看。

然后论文探讨了区分热数据温数据的一个界限,通过对访问频次和删除频次随着创建时间的变化的分析,对于大部分 BLOG,得到了一个的大概值:一个月。但是有两个例外,一个是用户头像,一直是热数据;另外一个普通图片,使用三个月作为阈值。

热数据总是那些头部数据,相对来说增长较慢。但是历史数据,也就是温数据是随着时间推移而尾巴越来越长,这势必要求存储架构进行相应的调整。

存储系统总体架构

设计原则是让每个组件尽可能简单、内聚并且高度契合其要承担的工作。这是从 UNIX 以来就一直在强调的一个原则。下图是总体架构图,包括创建(C1-C2,由 Haystack 负责),删除(D1-D2,大部分是 Haystack 负责,少部分是 f4 负责)和读取(R1-R4 由 Haystack 和 f4 共同负责)。

over BLOB Storage Architecture

over BLOB Storage Architecture

如前述论文 Haystack 所述,我们将一批 BLOG 集结为逻辑卷,尽可能减少 meta 信息,从而减少IO次数。每个逻辑卷我们设计了 100G 左右的容量,在满之前是为 未锁定unlocked) 的状态,一旦达到容量,就变为锁定locked)状态,只允许读取和删除。

每个卷包含三个文件,一个数据文件,一个索引文件和一个备忘文件(journal file)。和 Haystack 论文提到的一样,数据文件就是记录 BLOG 本身和其原信息,索引文件就是内存中的查找结构的快照。备忘文件是新增的,它通过记录所有被删除的 BLOG 的记录来进行删除操作。而原 Haystack 论文中,删除文件是通过直接修改索引文件和数据文件来实现的。在未锁定阶段,三个文件均可读写,在锁定阶段,只有备忘文件可以读写,其他两个文件都会变成只读的。

控制模块(Controller)

统筹整个系统,比如提供新的存储机器;维持一个未锁定卷(unlocked volumes )的池子;确保所有逻辑卷有足够的物理卷来备份;根据需求适时创建物理卷;进行周期性的维护任务,比如说数据紧缩(compaction)和垃圾回收。

路由层(Route Tier)

路由层负责BLOB 存储系统向对外提供接口,它屏蔽了系统底层的实现,使得可以方便添加如 f4 一样的子系统。所有的路由层的机器角色都是一样的,因为该层将所有状态(如逻辑卷到物理卷的映射)都存在了另外的数据库里(将所有相关状态收集起来额外存储,使得剩下的部分无状态可以平滑扩展,这也是系统设计常用的原则)。这使得路由层的可以不依赖其他模块来平滑扩展。

对于读取请求,路由模块会从 BLOB id 中解析出 逻辑卷 id,然后根据数据库中读出的映射关系来找到对应的所有物理卷信息。一般来说会从最近一个主机取数据,如果失败的话,会产生一个超时事件,去下一个物理卷所在的主机进行尝试。

对于创建请求,路由模块会选取一个有空闲空间的逻辑卷,然后将 BLOB 发送到该逻辑卷对应的所有物理卷进行写入(是并行发,还是链式发还是串行发?)如果遇到任何问题,就会中断写,并且已经写入的数据会被废弃,且户重新挑选一个可用逻辑卷,重复上述过程。(看起来像并行写,容错策略也超级粗暴)

对于删除请求,路由模块会将其发送到所有对应的物理卷(然后就快速返回),然后对应物理主机程序会异步的进行删除,遇到错误就一直重试,直到成功删除所有对应物理卷上的对应 BLOB。(倒也简单,但不知道实现的时候是会写入 journal file 后返回,还是只是在内存中标记下就返回。对应的数据文件上的 BLOB 肯定是在 compact 的时候才会删掉)。

路由层通过将实现细节隐藏,使得(对用户)无感知地构建温存储成为可能,当一个卷被从热存储移到温存储的时候,会在两者上同时存在一段时间,直到有效(逻辑卷到物理卷)的映射被更新后,客户端的请求将被无感知的地导向温存储。

转换层(Transformer Tier)

转换层负责处理对检索到的 BLOB 数据的变换操作,比如图片的缩放和裁剪。在 Facebook 的老版本的系统中,这些计算密集型的操作会在存储节点上完成。

增加转换层可以解放存储节点,使其专注于提供存储服务。将计算任务分离出来也有利于将存储层和转换层进行独立的扩展。然后,它也可以让我们精确地控制存储节点的容量以恰好满足需求。更进一步,也可以使我们针对不同任务类型进行更优的硬件选型。比如说我们可以将存储节点设计为具有大量硬盘,但只有一个CPU和少量内存。

缓存栈(Caching Stack)

一开始是为了处理热点 BLOB 数据的请求,缓解后端存储系统的压力。对于温存储来说,它也可以减小其请求压力。这里说的应该是 CDN 以及类似 akamai 内容分发商提供的缓存。

Haystack 热存储(Hot Storage with Haystack)

Haystack 开始是被设计来尽可能的提高 IOPS 的,通过揽下所有创建请求,大部分的删除请求和高频读请求,使得温存储的设计可以大大简化。

如相关 paper 提到的,Haystack 通过合并 BLOB 和简化元信息使得 IOPS 大大提高。具体来说,包括将逻辑卷设计为集合了一批 BLOB 的单个文件,利用三个物理卷对同一个逻辑卷进行冗余备份等等。

读请求过来后,会在内存中拿到请求的 BLOB 的元信息,并且看其是否被删除,然后通过物理文件位置+ offset + size ,仅进行一次 IO 拿到对应 BLOB 数据。

当主机收到创建请求后,会同步的将 BLOB 数据追加到数据文件上,然后更新内存中的元信息并将更改写入索引文件和备忘文件中(备忘文件不是只记录删除操作吗?)。

当主机收到删除请求时,会更新索引文件和备忘文件。但是对应数据仍然存在于数据文件中,定期地我们会进行紧缩操作,才会真正的删除数据,并回收相应空间。

容错(Fault tolerance)

Haystack 通过在一个数据中心的不同机架上各放一个副本,然后再不同数据中心再放一个副本的三副本策略获得了对硬盘,主机,机架甚至数据中心的容错能力。然后通过 RAID-6(1.2倍冗余数据编码,能够小范围的纠正错误,可以读读纠错码之类的文章)进行额外的硬盘容错,更上一层保险。但是付出的代价是 3*1.2 = 3.6 倍的有效冗余因子,这也是 Haystack 的局限之处,虽然最大化了 IOPS,但是在存储使用上却并不高效,造成了很多 BLOB 的数据冗余。

暂存内容驱动(Expiry-Driven Content)

有些类型的 BLOB 具有一定的过期时间,比如说用户上传的视频,会从原始格式转化为我们的存储格式。在此之后原始视频需要删掉。我们会避免将此类具有过期时间的数据移动到 F4 上,从而让 Haystack 负责这些频繁的删除请求,并通过频繁紧缩来回收空间。

f4 设计

设计目标是在容错的基础上尽可能高效。也就是在能够容忍硬盘错误,主机故障,机架问题,数据中心灾难的前提下,把有效冗余倍数降一降。

f4 概览(f4 Overview)

f4 是温数据存储架构的子系统。包含一系列 数据单元(cell),每个 cell 都在同一个数据中心(机房,datacenter)里。当前(2014)的 cell 包含 14 个机架,每个机架有15个主机,每个主机有三十块 4T 容量的硬盘。cell 负责存储逻辑卷,每个逻辑卷实际存储时,会将数据利用里所码(Reed-Solomon coding,简称RS,这是前面提到的RAID-6 标准的重要成员)进行冗余编码,比如 RS(n, k) 就是每存 n 个比特,就要编入额外的 k 个比特,以此来容忍最多 k 个比特的出错。通过这种编码方式可以解决硬盘,主机和机架出错问题。

此外利用异或编码(XOR coding)来解决跨数据中心或者地理位置的出错问题。我们选取两个不同机房的对等数量 volume/stripe/block 结成对子,然后将每一对的异或值存在第三个机房。

单个 f4 cell(Individual f4 Cell)

每个 f4 数据单元(cell) 只处理锁定的卷(Volume),也就是只用支持读取和删除操作。数据文件和索引文件都是只读的,Haystack 中的备忘文件在 f4 中是不存在的。我们用了另一种方式来达到“删除”的效用,将每个 BLOB 进行加密后存储,将用于加密的秘钥(key)存在一个外部数据库中。响应删除请求时,只需要将 BLOB 对应的秘钥删掉就行(有点绝,对用户提供了隐私保证,而且将删除操作的延时降到很低)。

索引文件由于比较小,直接用了三副本存储来保证可靠性,可以省去编解码带来的额外复杂度。数据文件用 n=10, k = 4 的里所码进行编码。具体来说,将每个数据文件切分为 n 个连续的数据块(block),每个具有固定尺寸 b(最后一个块不满,而又写不进去一个新 BLOB 的情况下,在结尾补零,类似这种打 padding 也是数据对齐常用的手法);对于每 n 个这样的块,生成 k 个同样尺寸的奇偶校验块(parity block),这样 n+k 个数据块构成一个逻辑上的 条带(stripe)。同一条带上的任意两个块互称为兄弟块(companion block)。正常读取时,可以直接从数据块中读(我猜是那n个块,不用额外进行计算还原,有待考证,还得看里所码原理以及具体实现)。如果某些块不可用了,就会在同一条带上任取 n 块,解码后还原;此外还有个性质,就是读取 n 个 block 上对应的 n 截数据(比如某个 BLOB),也可以进行解码(这两个性质都是编码决定的,类似于 n 元线性方程组,有 k 个冗余方程)。

BLOBs in Block in Stripes in Volumes

BLOBs in Block in Stripes in Volumes

通常 b 为 1G,即每个数据块(Block)选取 1G 大小(这有个疑问,看起来每个Block仍在Volume中,而不是单独拿出来,那么定位一个物理block是不是就得通过 volume 文件打开句柄 + offset + length),选这么大有两方面的考虑,一个是尽量减小 BLOB 的跨块概率,以减少读取一个 BLOB 还得多次 IO 的频率;另一个是降低 block 所需要维护的总元信息数量。不选更大的是因为重建起来会付出更大代价(但为什么就是 1G 呢?)。

下图是架构图,接下来逐一介绍下各个模块。

overall architecture

overall architecture

top Created with Sketch.