背景介绍

本论文发表自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太小须要屡次读能力读完一张照片的数据）

总结

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