原始论文地址 Finding a needle in Haystack: Facebook’s photo storage
该论文主要介绍了一个对象存储系统Haystack，该存储系统主要针对大规模的图片存储进行优化。传统的存储系统设计基于NFS，由于涉及到大量的文件元数据的查找操作，因此会有大量的磁盘I/O增加了总的操作的时间。该论文中采取减少图片元数据的方法，将所有的元数据放入到内存当中操作来提升性能。这样，仅需要读取图片的时候才需要磁盘操作。
存储在云端的图片有一个特点，就是只会写一次、会被经常读取、不会被修改以及很少被删除。不会被修改这个特点是由于FB采取将修改后的图片存储在新位置的策略导致的。
目前，文件系统普遍基于POSIX标准，文件存放在目录下，并且文件有对应的元数据。下面是一个图片的元数据。虽然元数据数据量比较小，但是对于大型的数据中心来说，成百万的图片的元数据会是一个比较大的数据量。
$ exiftool IMG_20151104_102543.jpg
ExifTool Version Number : 9.46
File Name : IMG_20151104_102543.jpg
Directory : .
File Size : 2.8 MB
File Modification Date/Time : 2015:11:04 10:25:44+05:30
File Access Date/Time : 2015:11:17 18:56:49+05:30
File Inode Change Date/Time : 2015:11:11 14:55:43+05:30
File Permissions : rwxrwxrwx
File Type : JPEG
MIME Type : image/jpeg
Exif Byte Order : Big-endian (Motorola, MM)
GPS Img Direction : 0
GPS Date Stamp : 2015:11:04
GPS Img Direction Ref : Magnetic North
GPS Time Stamp : 04:55:43
Camera Model Name : Micromax A121
Aperture Value : 2.1
Interoperability Index : R98 - DCF basic file (sRGB)
Interoperability Version : 0100
Create Date : 2002:12:08 12:00:00
Shutter Speed Value : 1/808
Color Space : sRGB
Date/Time Original : 2015:11:04 10:25:44
Flashpix Version : 0100
Exif Image Height : 2400
Exif Version : 0220
Exif Image Width : 3200
Focal Length : 3.5 mm
Flash : Auto, Did not fire
Exposure Time : 1/809
ISO : 100
Components Configuration : Y, Cb, Cr, -
Y Cb Cr Positioning : Centered
Y Resolution : 72
Resolution Unit : inches
X Resolution : 72
Make : Micromax
Compression : JPEG (old-style)
Thumbnail Offset : 640
Thumbnail Length : 12029
Image Width : 3200
Image Height : 2400
Encoding Process : Baseline DCT, Huffman coding
Bits Per Sample : 8
Color Components : 3
Y Cb Cr Sub Sampling : YCbCr4:2:0 (2 2)
Aperture : 2.1
GPS Date/Time : 2015:11:04 04:55:43Z
Image Size : 3200x2400
Shutter Speed : 1/809
Thumbnail Image : (Binary data 12029 bytes, use -b option to extract)
Focal Length : 3.5 mm
Light Value : 11.9
对于上传到云端的图片来说，有些元数据字段，比如上面的FilePermissons是不会被用到的。
论文中介绍了Haystack的三个优势：
论文在该部分介绍了FB在使用Haystack之前采用的架构以及得到的经验。
上图是浏览器、CDN以及存储系统之间如何交互的简易结构图。在使用Haystack之前，FB使用基于NFS的存储系统，CDN缓存了经常被访问的图片数据。但是社交软件上虽然有很多流量请求访问了那些热门的图片，但是还有大量的请求访问的是比较冷门，时间较为久远的图片。
基于NFS的存储系统中，每个图片是单独的一个文件。上图是图片存储系统，基于NFS处理HTTP请求的过程。
由于当目录下有大量的文件的时候 ，数据块映像(blockmap)不能有效地被缓存，因此一般目录下最多只有几百个文件。但是即使这样，访问某个图片依然需要进行三次磁盘操作：首先将目录的元数据读取内存，之后读取inode最后读取图片。为了进一步减少磁盘操作，使用服务器缓存从设备访问的图片的文件句柄。当某个请求的文件的文件句柄已被缓存，通过使用系统调用 open_by_filehandle来打开文件，该系统调用是FB自己加上去的。但是，前面提到过很多访问并不是针对热门图片的，因此，这些请求很难命中缓存。论文中总结，依靠存储设备或者一些外部缓存，比如memcache，对性能提升有限。因此，基于这些经验，设计定制化的存储系统，减少每张图片的元数据，以及足够大的内存使得文件元数据能够全部放在内存中操作。
FB使用CDN去缓存那些热门的图片，并使用Haystack处理那些请求中的长尾数据。Haystack的目标是尽量减少对于磁盘的操作，通过采取减少图片元数据的大小，将元数据放在主存中来达到目标。前面提到，在基于NFS的方式中，每个图片保存为一个文件。为了减少平均每个图片的元数据大小，Haystack采取将多张图片保存在一个文件中的方法。
Haystack主要包含三个部分，分别是Haystack Store, Haystack Directory 以及Haystack Cache。其中Haystack Store包含了存储系统，并且管理图片的元数据。Haystack Store按照物理卷(volume)管理，并将多个物理卷构成的组抽象为一个逻辑卷。当Haystack 将图片存储在逻辑卷中时，图片被写入到所有相关的物理卷中，这些冗余数据用作备份。
用户端使用类似如下的URL访问图片数据
http://<CDN>/<Cache>/<Machine id>/<Logical volumn, Photo>
首先，CDN接收到请求，CDN首先根据URL最后的逻辑卷以及图片的id查找，如果没有，则请求转到Cache，Cache进行类似的操作，如果依然没有找到该图片，则最终由Haystack Store处理。
在上图中，Haystack Directory与Web Server 直接交互。Haystack Directory主要有四个功能：
Cache 从CDN或者是直接从客户端接收到请求。Cache 被设计为一个分布式的哈希表，使用图片的id定位cache缓存的数据。如果Cache中没有该图片的数据，则会到存储设备上读取数据，并返回给CDN或者是浏览器端。
Cache 对满足下面两个条件的图片进行缓存：
其中第一个条件是因为，如果是来自CDN的请求，则CDN上没有的数据，Cache上也很难有。第二个条件的目的是为了减少对允许写设备的读取操作。比如当某个相册上传到服务器上之后，一般都会进行查看操作，缓存这些数据可以减少读取操作。
Haystack Store中的每个机器管理多个物理卷，每个逻辑卷包含多个物理卷。图片的读取通过逻辑卷号以及文件的偏移(offset)来获取。
如上图所示，每个物理卷包含一个超级块以及保存在该物理卷上的图片(上图中的Needle)。为了加快检索的过程，每个物理卷在内存当中都有对应的数据结构，该数据结构将图片的id映射到对应的needle上，包括设备的标记、文件的大小、偏移等。当出现故障时，该映射关系会根据存储的情况重建。
当Cache向存储设备请求图片的时候，需要使用到逻辑卷号，key, alternate key和cookie。其中cookie 是保存在URL中的一串数字，是在图片上传的时候随机分配并保存在Directory中的，这可以避免猜测图片的URL进行的攻击。
对于图片的写操作，相关的物理卷将图片数据添加，并更新内存中的映射关系。Haystack不允许对图片的修改操作，只能将对图片的修改另外保存，但是key和alternative key是相同的。如果新版本的图片文件与原始版本保存在不同的逻辑卷中，Directory 更新元数据，之后的数据请求不会去获取旧版本的图片文件。如果新版本的图片与原始版本的图片保存在相同的逻辑卷中，Haystack会根据文件的地址偏移值来区分文件的版本。
对于文件的删除，Haystack Store设置内存中映射关系中的flag以及设备上对应的flag。 被标记为删除的空间的收回操作在后面介绍。
前面提到，HayStack Store重建内存中的映射关系表，可以通过读取所有的物理卷来构建。但是读取所有的磁盘是很费时的，所以可以通过索引文件来加快这个过程。
索引文件的结构如上图所示，与物理卷的结构相似，首先是超级块，之后是一系列的索引文件。索引文件中这些Needle的顺序需要和物理卷中的顺序相同。基于索引文件重构内存中的映射关系表相比于读取物理卷来重构需要面临一个问题。因为索引文件是异步更新的，所以重建时不一定是最新的。这可能导致某个文件标记为删除，但是由于还未更新到索引文件，或者是某个图片文件已保存但是索引文件中没有记录。针对第一个问题，可以在Haystack Store读取图片数据之后检查一下标志位，如果标记为已删除，则更新内存中的映射关系表，并通知Cache该图片已删除；针对第二个问题，由于Haystack Store添加记录是在最后append，所以可以从最后一个记录开始，就可以判断哪些记录是没有对应索引的。
Haystack Store使用XFS文件系统，XFS有两个优势，一是针对连续的大文件的blockmap 足够小，可以放入到内存当中；二是XFS有高效的空间预分配(preallocation)机制，可以消除存储碎片以及控制blockmap 增长的大小。
针对故障检测与恢复，Haystack运行一个后台进程，称为pitch-fork，定期地检测设备。pitch-fork 尝试连接存储设备并测试读取，如果操作失败，则将该设备上涉及的逻辑卷全部标记为只读,之后是人工维修。
Haystack 主要使用下面这三种方式来优化性能。