乐趣区

关于存储技术:论文精读Finding-a-needle-in-Haystack-Facebooks-photo-storage

jiezi

背景介绍

本论文发表自 2010 年，是过后 facebook 所利用的存储系统。在 2010 年前后 facebook 上存储的照片数量开始迅猛的增长，过后有差不多 2600 亿张图片、20PB 的数据量，每周有 60TB 新的照片上传至 facebook 零碎，服务器每秒须要解决百万张。此外，这些照片有一个特点就是照片的都是小文件照片。基于以上特点，传统的存储架构曾经无奈满足以后的存储需要。
因而，facebook 团队提出了一个新的存储架构 Haystack 来满足日益增长的存储需要。Haystack 架构有以下四点需要：

  • 高吞吐、低提早：升高磁盘读取次数、放弃元数据存储在主存中
  • 容错性：分布式存储，数据备份
  • 低成本：更高的存储利用率、执行效率更高
  • 设计简略：生产环境中更便捷的开发和部署新零碎

前序设计

NFS-based Design

如上图所示，是基于 NFS 的传统存储架构(NFS 是网络文件系统能使使用者拜访网络上别处的文件就像在应用本人的计算机一样)，图中的 NAS（网络从属存储）是连贯着网络上的存储设备，如下图所示：

传统的设计用户若要拜访 facebook 的网站时将会通过以下步骤：

  1. 浏览器向 web Server 发送页面申请
  2. web Server 给浏览器返回一系列的 URL 链接，每个 URL 链接对应着照片文件的存储信息。
  3. 浏览器失去 URL 后向 CDN（内容散发网络，能够了解成缓存）发送资源申请申请。此时，若 CDN 中存储着申请的资源文件则间接返回资源至浏览器，否则 CDN 向 photo store server 发送申请申请。
  4. photo store server 先在本人的缓存中查找照片文件，若没有再去 NAS 上查找对应的照片资源，找到再返回给 CDN
  5. CDN 收到照片资源后在本人这里缓存一份而后再将照片反回给浏览器。

以上，便是传统的照片存储系统的运行机理。在基于 NFS 的存储系统中 facebook 本人总结了以下几点不足之处，

  1. Cache/CDN is not practical

  2. Too many disk operations per action

    1. inefficient as the directory’s blockmap was too large to be cached effectively by appliance
    2. common to incur 10 disk operations to retrieve a single image

  3. Caching in filesystem level wouldn’t work either

    1. long tail

第一点：Cache/CDN（能够了解成 CDN 为第一级缓存、Cache 为第二级缓存）在实践中的成果很差的起因在于，如果 CDN 不命中那么在 Cache 上命中的可能性也不大（Cache 是指 photo store server 上的第二级缓存）。至于为什么 CDN 不命中 Cache 命中的概率也不大能够这样了解：用户拜访的基本上都是新上传的照片，新上传的照片自身大部分就在 CDN 中有缓存，如果 CDN 中都没有代表着用户拜访的极有可能是老照片，所以老照片在 Cache 中有缓存的可能性也不大。

第二点：每找一张照片操作系统所进行的文件 IO 操作次数太多，导致效率低下（起因下一节解释）。在本零碎中，facebook 将关上的文件描述符缓存起来了 photo server 外面(文件描述符体现进去就是一个数字)，下次读取无需再次查找和关上文件（文件名—->handle 这一层映射存在主存中），然而存在一个问题：CDN 不命中，阐明申请的照片是不罕用的照片，所以前面的零碎中大概率也不会名字，再 cache 一层实际意义不大（CND 若命中则可间接取走数据，不命中的话后续命中的概率也不大 所以再 cache 一层的意义不大）

第三点：与第一点的解释类似，因为 long tail 效应（如果 CDN 不命中则 Cache 也大概率不会命中，所以 Cache 的意义不是很大）

此外，facebook 团队在后期犯了一个谬误导致存储效率低下：
在一个文件夹下搁置上千张图片。这样导致每次查问一张照片所付出的查问代价都是不小的。在后续的版本中 facebook 改良了它在一个文件夹下存数百张照片。

文件系统的工作机制

须要留神的是本文写于 2010 年，过后的文件系统和当初的有肯定的差别，过后所采纳的是 ex2（当初 ex4）。在这个背景下了解上一节所留下的问题：读取一张照片所须要的 IO 次数过多（常常读一张须要 10 来次 IO 操作）。

读取一个文件的步骤（表层）

fopen 一个文件、read 数据。在咱们应用的层面读取一个文件很简略只需调研编程语言所提供的接口例如 fopen 函数关上一个文件，而后零碎会给你返回一个文件描述符（一个数字，代表着你须要读的文件）而后再对该描述符进行读写即可。

读取一个文件的步骤（底层）

  1. 过程调用库函数向内核发动读文件申请；
  2. 内核通过查看过程的文件描述符定位到虚构文件系统的已关上文件列表表项；
  3. 调用该文件可用的零碎调用函数 read()
  4. read()函数通过文件表项链接到目录项模块，依据传入的文件门路，在目录项模块中检索，找到该文件的 inode；
  5. 在 inode 中，通过文件内容偏移量计算出要读取的页, 读取文件数据。

若一个文件的存储门路是：/etc/passwd。则 read 找到这个文件在磁盘上所存储的地位的步骤是：

  1. 先查看根目录下的文件夹在磁盘上存储的地位，找到 etc 这一行发现其在 7(i-node)这个地位。
  2. 而后跳转到 7 这里查找 passwd 这个文件的 i -node 信息（如同所示存储在 6422 这个地位）
  3. 而后磁盘指针再指向 6422 这个地位 passwd 这个文件具体的 data block 指针指向的地位上读取相应的文件信息。（一个文件会存储在不同的地位，即 data block 指针指向的地位很可能不是间断的）

所以，如上这个例子所示，read(“/etc/passwd”)这个操作便有 3 次 IO 操作。此外因为在 ex2 文件系统下，在以后文件夹下查找指定文件的 i -node 信息是线性查问（当初 ex4 是一个树的构造），所以若一个文件夹下有上千个文件，则均匀查问到一个文件的查问次数是 500 次。

在 linux 零碎下能够用 ls -li 来查看文件的 i -node 信息，如下所示。

至此，讲清楚了传统的架构设计，接下来解说 Haystack 的工作。

Haystack 的设计与实现

Haystack 存在两种 metadata：

  1. Application metadata：形容浏览器能检索到图片存储信息的元数据
  2. Filesystem metadata：形容图片存储的具体位置的元数据（相当于二级缓存）

依据这两种元数据便能够找到找的存储的地位，例如：利用 Application metadata 找到记录照片元数据的地位，再去该服务器上找到该元数据，而找到的这个元数据是记录着照片的具体的存储信息。（可能有点绕）举个形象的例子，比如说你干了什么坏事件，警察叔叔要来找你，警察叔叔先去警察局查小册子（Application metadata）找到你在哪个小区，而后再去该小区找到你的住宿信息（filesystem metadata）再依据该住宿信息找到你这个人。

若每一张照片有一个 metadata 则会造成 metadata 的数量十分多，无奈存储在主存中，所以 Haystack 将多个文件数据存储在一个文件中，以此来缩小元数据（简略无效，即缩小了元数据也缩小了 IO 操作）。

URL 设计

每张照片由这样一个 URL 来定位，首先依据 CDN 的信息去对应的 CDN 找，若没找到则去掉 CDN 的局部用剩下的链接去 Cache 下面找，若还是没找到则去掉 Cache 的局部，用 Machine id 结尾的局部去找数据。

https://scontent-xsp1-2.xx.fbcdn.net/v/t1.0-9/s960x960/117626438\_694963981232505\_2939587164346987203\_o.jpg?\_nc\_cat=102&\_nc\_sid=e007fa&\_nc\_ohc=J92KKoh-gT4AX8XBxXJ&\_nc\_ht=scontent-xsp1-2.xx&\_nc\_tp=7&oh=8b2848b261b59aad56c2684c994e65fb&oe=5F6219F9

如上所示是以后的 facebook 的照片存储信息，有局部还是能够参考的。然而在 2020 年的当初架构预计曾经产生了变动。

Haystack 零碎的外围组件

Haystack 次要有三个外围组件组成：

  1. Haystack Store：实质上还是之前的那些 NAS，定义一个 logical volume，每个 logical volume 对应治理着若干个 phisical volume。
  2. Haystack Directory：负责 metadata 的 mapping，实质上是做如何从 logical vlolume 映射到 physical volume 上。决定生成的是 Cache 的 URL 还是 CDN 的 URL（实现 Cache 和 CDN 的负载平衡），并且将写满的磁盘标记为只读磁盘。
  3. Haystack Cache：Cache 实质上还是一个 CDN，因为 CDN 太贵了，能够了解成 CDN 为外层缓存，Cache 是内层的缓存，Cache 能够缩小零碎对于外层 CDN 的依赖。Cache 和 CDN 相当于一个两层的缓存。CDN 找不到则去 Cache 外面找，Cache 找不到再去零碎外面找

如上图所示，新的 Haystack 的工作流程如下：

  1. 浏览器向 web server 发送网址申请。
  2. web server 进一步向 Directory 发送申请。
  3. Directory 生成所须要的照片的 URL 等信息后返回数据给 server 再返回给浏览器（Directory 同时负责负载平衡的作用，即决定浏览器是去 CDN 还是 Cache 找资源）。
  4. 若浏览器去 CDN 找资源（如果是读则走 Cache），CDN 中若缓存着所需照片的资源，则间接返回数据，若没找到则进一步去 Cache 中找。
  5. 若 Cache 中也没有则向 Store 零碎发送申请。
  6. Cache 拿到数据后缓存一份而后一步一步返回给浏览器。

Haystack Directory

  • 提供逻辑卷到物理卷的映射，能够结构 URL
  • 负责逻辑卷的写和物理卷的读之间的平衡（the Directory load balances writes across logical volumes and reads across physical volumes.）
  • 判断须要的照片须要缓存在 CND 还是 Cache 中（缩小对于 CDN 的依赖）
  • 将存储满的物理卷标记为只读卷

Haystack Cache

  • 分布式哈希的模式，将照片的 ID 作为哈希表的 key 来定位缓存的数据，若哈希表不命中则去存储系统中查找。这里的 value 示意着是照片的存储门路，即 logical volume id/offset/size 等信息。（Haystack 将一个数百万个照片存储在一个大的 100G 文件中）

  • 缓存照片只会在以下两种状况下产生

    • 申请间接来自用户而非 CDN

      • 教训论断：CDN 未命中的数据在 Cache 中大概率也不会命中（CDN 自身就是一个大 Cache）

    • 存储照片的机器是可写的（存储空间未满）

      • read only 代表该卷曾经存在较长时间，很可能曾经在 CDN 上曾经有缓存，其次，依据教训照片的数据越新，越容易被再次拜访，老磁盘上的数据代表着数据年代比拟久了
  • 相似 CDN 的性能，存储着较为热点的数据（依据 facebook 直本人的考察数据，照片上传相差一周 拜访频率差了 10 倍 6 个月后只剩下百分之一）

Haystack Store

  • 每个存储机器对应着数个物理卷，每个物理卷存储这数百万张图片
  • 每个物理卷能够看作一个微小的文件（100GB），利用照片 ID 和偏移量能够定位存储具体照片的地位。（这样设计将成千上万个文件合在一个文件外面（100GB），治理一个文件描述符，这样的量级便能够现实的存储这一层映射关系。能够将其存储在主存当中）

读：依据文件描述符、文件名字、文件大小、文件在 volume 上的偏移量，这样便可间接读出文件。
写：间接生成相应照片的 needle，append 到前面就能够，再更新主存中的相应索引信息

  • Haystack 零碎的关键技术：做到不必 IO 操作便可读取到文件的名字、偏移量、文件大小等信息（信息存储在内存中）

  • 结构化存储模式

    • 只需晓得文件名、偏移量、文件大小便可读出相应的文件
    • 为了能疾速定位照片，每个存储机器在主存中维持每个物理卷的相应数据（照片的块地位、照片大小、卷内偏移量）
    • 文件存储构造

上传照片

当用户上传照片时将通过以下几个步骤：

  1. 将照片数据发送到 web server 服务器上
  2. web server 依据照片的数据信息向 Directory 发送调配申请
  3. Directory 依据照片信息调配一个可写的逻辑卷地址，并返回该地址
  4. web server 失去逻辑卷地址后将照片数据上传至相应的逻辑卷上
  5. 逻辑卷失去数据后，将照片写入到其治理的每个物理卷中（貌似过后一个逻辑卷负责三个物理卷，每个物理卷的地位不肯定在一起，以这样的形式做到了容错）

如果是更新照片则有两种策略：

  • 新照片和老照片不在一个物理卷上，则间接在以后物理卷上新增，并更新缓存信息
  • 若新照和老照片在同一物理卷，则在物理卷的前面减少该信息，并更新缓存（依据偏移量判断新旧，越大的代表最新上传的）

照片读取

  • 向存储机器发送逻辑卷 ID、key 等信息申请照片
  • 存储机器在主存中查找相应的元数据，若存在该照片则依据该元数据去读取具体的照片

删除照片

  • 在相应的缓存和物理卷的地位上将其 delete flag 至 1 标记为已删除
  • 删除的空间等当前一起回收（回收是将以后物理卷上的所有文件拷贝到另外一个物理卷上，并略过那些 flags 上删除位为 1 的 needle）

索引文件

  • 传统的文件系统的索引信息在零碎开机时遍历整个物理卷，而后生产的索引信息
  • 为了避免机器宕机导致索引隐没（映射关系存储在主存中），Haystack 须要周期性的将索引信息备份到磁盘中（1. 进步了容错性 2. 放慢了从新构建映射关系的速度（若不存储则须要遍历所有文件从新结构映射关系））
  • Haystack 索引文件的信息（依据这个信息，定位照片、判断照片是否曾经被删除）


存储引擎 -XFS

XFS 的底层文件块是以 extents 的模式存储的（间断）而 block 块大部分是不间断存储的所以会有很多的索引信息导致无奈存储到主存中。
extents：每块 1GB 大小
RAID：每块 block 大小为 256kb
这样能够做到一次读取便可把文件读到缓存中（block 太小须要屡次读能力读完一张照片的数据）

总结

这样本论文的外围局部都曾经介绍了，以上是基于本人的了解和网上的一些材料信息写出的。必定存在一些问题，如果有问题间接提出来修改。

退出移动版