Facebook在2010年的时候发表过一篇在分布式存储系统领域很有名的一篇文章《Finding a needle in Haystack》来描述他们的图片存储系统，Haystack 存储了超过2600亿张图片，大约占了20TB的数据，用户每周都会上传10亿张图片，高峰时期的并发量在100万以上（这是2010年的数据，现在很有可能上了一个数量级)。
在这个数量级之下，需要考虑的问题不仅仅是高吞吐，低延时，保证数据的一致性，还要考虑如何能节省流量，容易扩展，容错等等。下面我们就来看下Haystack是怎样满足这些分布式系统的要素的。
图片存储系统的最大特点是数据只写一次，读取频繁，不会修改，很少删除。Facebook 一开始的存储系统是基于NFS的NAS(Network Attached Storage), 但这种基于 POSIX 的文件系统无法支撑如此大的负载。其中主要的问题在于在图片寻址的过程中会产生过多的磁盘操作。
我们知道从传统文件系统里面读取一个文件需要至少三次磁盘操作，第一次从硬盘中读取目录的 metadata 到内存中，然后读取inode到内存，最后才从磁盘中读取文件内容。
再者这些metadata里面包含了大量比如权限控制这些对于图片存储系统来说无用的信息，也浪费了大量的磁盘空间。当像图片这样的静态资源服务出现瓶颈的时候，自然就会想到使用 CDN (Content Delivery Networks) 系统。在传统的设计中，一个图片的 HTTP 请求发送后， 如果 CDN 有这个资源的缓存，就会立马返回，反之 ，CDN 会将根据请求的 URL 从存储系统里面读取图片，更新缓存，然后再返回。在这样的设计中，CDN 确实可以很有效地处理热点图片的请求。
但像 Facebook 这样的社交网络中，有大量的请求是针对那些非热点或者老内容的，用户在请求那些长尾 (long tail) 内容时将没有优化。当然，有些同学会说，那我可以将所有的图片都缓存到 CDN，那确实会解决这个问题，但将会极大地增加资源的开销。
为了减少那些直接 hit 到存储系统的请求的磁盘操作，他们想到在第一次读取文件的时候把filename到 file handle 的映射缓存到内存，在下一次读取文件的时候，会调用自定义的open_by_filehandle来减少磁盘操作，但这对于long tail的读取问题依然存在，因为这些文件的映射关系没有提前放在内存中。
于是，Facebook 决定从头研发图片存储系统，从前面我们可以看出，Haystack 的核心任务就是在处理每一次的请求中尽可能地减少磁盘操作。我们先来描述下 Haystack 读取和上传图片流程是怎样的，然后再来看其中的细节是如何处理的。
1、读取图片过程
当发起一次图片读取请求的时候会通过一个事先构建好的 URL
http://///这个 URL 实际上显示出了访问的顺序，先从外部 CDN 读取，如果没有，访问内部 Cache，如果还是没有，就直接访问 Store Machine.（URL最后一部分提供了图片的唯一标识）
![]()
2、上传图片过程
用户上传图片的时候先会上传到 web 服务器, 然后服务器从Directory中找到一个可写的physical volume,最后服务器会给这个图片生成一个唯一ID, 然后写入到这个logical volume 所对应的所有physical volume中。
上面的过程中出现了几个陌生的名词，别着急，我们一个个来看。我们先来介绍 Haystack 的三个主要组件:
Store,Directory,Cache.
Store
Store 是核心组件，负责图片的存储。Store 的容量决定了这个存储系统的容量，整个 Store 组件由很多个 store machine 组成，store machine 的容量又由一系列的 physical volume 决定。
例：要提供 10TB容量，我们可分摊到 100 个 physical volume，每个 physical volume 提供 100 GB 的容量。这时候有的同学会问，那么数据冗余是怎么解决的呢？Haystack 借鉴了普通硬盘中的 logical volume 的概念，将不同机器上的多个 physical
volume 组成了一个虚拟的 logical volume。
当存储一张图片的时候，实际上是存储到了 logical volume 对应的所有 physical volume中。它们之间的映射关系连同其它的metadata都存储在 Directory组件中。每个physicalvolume 中都存储了上百万张图片，可以把它想象成一个巨大的 append-only 文件，然后通过 offset 来访问文件。
我们来详细看下这个文件到底是如何存放的，如何来达到减少磁盘操作目的的。对于每个这样超大的文件，都由一个 superblock 和一系列的 needles 组成，每个 needle 就是每张图片的信息。看下下面这张图，它的结构就一目了然了。
每个needle包含的细节信息有图片ID，图片大小，图片数据等等，还会有数据校验的属性。每个 store machine 都有若干个physical volume大文件， 为了提高检索needles 的速度，在内存里为每个physical volume都维护了一张图片I 到needle之间的映射表。
当store machine接收到读取请求时，首先从内存映射表中找到相应的metadata， 然后通过offset从硬盘中读取到整个needle， 通过数据校验后返回。如果接收到的是上传请求，会把组织好的needle追加到所有对应的physical volume文件中，并且更新内存里的映射表。如果是删除操作的话，我们注意到下图中有个Flags标志位其实就是用来标记是否是删除的状态，这样一来就很简单，直接在这个位置标记好，系统会在后面执行compaction 操作回收这些空间。
讲到这里，一个正常流程的存储过程已经很清楚了。这时候我们就需要考虑分布式系统一个必不可少的特性：容错性。当一个 store machine 宕机的时候，理论上我们可以读取所有的 physical volume 来重新构建内存映射表，但这就需要从磁盘重新读取 TB 级别的数据，显然是非常耗时和不高效的。为了解决这个问题，每个 store machine 为每个 physical volume 都维护了一个索引文件。这个索引文件类似于游戏中的存档点 (checkpoint)，它的结构和 physical volume 文件类似，保存了查找每个 needle 所需的属性。为了性能，索引文件是异步更新的（写的时候异步更新，删的时候压根不会更新），这就会带来一个问题：索引文件有可能不是最新的。之前我们提到过，physical volume 文件是一个 append-only 的文件，索引文件也是。所以我们只需要在重启 store machine 的时候，从后向前扫描 physical volume 文件找到那几个没有被索引的文件，加到索引里去就行了。对于被删除的文件，在真正读取完整 needle 数据的时候，通过检查删除标志位来更新内存映射表。
Cache
我们之前提到可以使用 CDN 来缓解系统压力，但它无法很好地解决非热点图片的问题，并且如果 CDN 节点出现故障的话，没有 Cache 这一层会对底层的存储系统 Store 产生巨大的压力。Cache 组件主要缓存了最近上传的图片，它的概念很简单，实际上是一个分布式 hash table，通过图片的 ID 为 key 可以找到对应的数据。Cache 接收从 CDN 或者浏览器直接发来的 HTTP 请求，但只有在以下两个条件都满足的情况下才会缓存图片：
1) 请求来自用户浏览器而不是来自 CDN
2) 请求的 store machine 是可写的
这听上去有些费解，条件 1 的原因是如果一个请求在 CDN 缓存中 miss 其实也会在 Cache 中 miss (如果一张图片成为热门的话，那也能在 CDN 找到)，条件 2 的原因则是避免让可写的 store machine 进行大量读操作，因为图片通常在刚刚上传后会被大量读取，文件系统通常在只读或者只写而不是既读又写的时候性能比较好。
如果没有 Cache 的话，可写的 store machine 将会同时处理写操作以及大量的读操作，会导致性能的急剧下降。
Directory
现在我们只剩下 Directory 组件没有讲了。除了之前我们提到的存储了 physical volume 到 logical volume 的映射关系以及图片 ID 到 logical physical 的映射关系，它还提供负载均衡服务以及为每个操作选择具体的 volume (因为写操作的对象是 logical volume，读操作的对象是 physical volume), 它还决定了一个请求是被 CDN 处理还是被 Cache 处理。Directory 还可以标记逻辑卷的状态，在运维需要或者空间满了的时候可以标记为只读状态。当往 Store 加新机器的时候，这些机器就会标记成可写的，只有可写的机器才能接受图片上传请求。这里有一个细节需要注意，图片 ID 到 logical physical 的映射表肯定无法存放在单机内存，文章中也没有交代具体实现。我们猜想可以使用 MySQL 分片集群和加上 Memcached 集群来实现。总的来讲，Directory 实际上根据 metadata，然后结合各种策略，实现了整个系统的调度器。
总结
本文描述了 Haystack 图片存储系统的主要脉络，当然还有许多细节没有提到，比如整个系统的容错机制，如何实现批量写操作等等。经过这几年的发展，我们相信 Haystack 肯定也进行了更多的优化，现在一些开源的分布式存储系统也被应用到实际的生产系统中，比如淘宝的 TFS，MooseFS 等等。我们会在后续的文章中比较这些系统之间的异同，总结出解决其中典型问题的通用方法。
本文作者：张陈丞（点融黑帮），点融 social 团队高级工程师，对很多技术领域都有兴趣，目前专注于分布式系统和机器学习。
