对象存储面面观之Haystack

英文中有句谚语叫做“Find a needle in haystack”，对应中文的“大海捞针”。Facebook将自己的图片存储系统称为Haystack，也非常形象的暗示了其所面对的挑战和目标场景。

场景与目标

正如上面的谚语所暗示的那样，Haystack面对的是海量的社交图片，具有特殊的数据场景：

海量；
一次写，多次读，从不修改，很少删除；
长尾效应：社交图片特有的，会有大量访问历史旧数据的请求，这个特点对大多数系统中针对热数据的各种优化提出了很大的挑战。

Haystack并不是一个通用、完美的存储系统，而是针对这个特殊的场景的非常简单高效的实现。其设计目标为：高吞吐低延迟、良好容错、高性价比、简单。

关键思路

传统的存储方式很自然的将每个图片当做一个文件存储在文件系统上，这种做法会给每次图片访问带来至少三次磁盘操作：

读取目录元信息到内存
读取inode到内存
读取真正的数据

这种额外的磁盘消耗在面对海量图片时变了尤为严重，极大的限制了整个系统吞吐量。自然的，我们寄希望于我们熟悉的缓存来降低多余的磁盘操作，大多数情况下这种做法总是奏效的，但这次，社交图片的长尾效应摧毁了这种幻想。大量的元信息使得没有办法将所有的元数据都加载到内存，继而频繁的对冷数据的访问使得缓存的作用大大降低。

所以Haystack的关键思路就变成：

降低单个图片的元信息量，使得将全部元信息加载到内存成为可能，从而避免读取元信息时的磁盘操作。

这个显著降低元信息数量的方法就是：将多个图片合并成一个大文件

设计实现

structure

首先通过Haystack最关键的查找逻辑来了解其结构。如上图所示，用户请求会先通过Web Server从HayStack Directory中获得指定图片的URL，这个URL结构如下：

http://⟨CDN⟩/⟨Cache⟩/⟨Machine id⟩/⟨Logical volume, Photo⟩

可以看出，DIrectory通过URL告诉客户端，应该去哪个CDN或者Cache中取获取指定的图片，这个图片位置是由机器id，逻辑卷编号加图片id共同标识的。如果幸运，用户可以从CDN或Cache中直接获得需要的图片，否则，Cache会首先从HayStack Store中获得这个图片数据。这里Haystack有三个重要的角色：

1, Haystack Directory

顾名思义，Directory担负了类似于操作系统中目录的元信息映射及管理作用：

维护logical volume到physical volume的映射关系：physical volume即是我们上面锁提到的存储多个图片的大文件，通常100G。Haystack又将多个physical volume一起管理，同时写入，称为logical volume。所以可以认为physical volunme是logical volume的存储副本，这里采取3副本。
logical volume之间的负载均衡
决定经过CDN还是Haystack Cache
发现readonly 的logical volume：容量达到上限的volume会被标记为readonly，不再接受写请求。

2, Haystack Cache

Cache简单的缓存访问过的图片数据。这里有两个智慧的缓存策略使得Cache更好的完成使命：

仅缓存来自用户的请求图片，而不是CDN：Cache和CDN其实是完成类似的缓存功能，来自CDN的请求，我们已经很确定的知道其一定会被CDN Cache。
仅缓存从可写Store中读取的图片，而不是Readonly的Strore：这个是因为Haystack认为，磁盘的性能限制主要来自同时对读写请求的服务，而Readonly Store本身的顺序读瓶颈不大。

至于为什么穿过CDN的请求不直接访问HayStore，个人猜想是为了逻辑的一致，同时避免直接暴露Haystack Store。

3, Haystack Store

我们知道，为了减少整体的元信息，Haystack将多个图片合并到一个大文件中：

Imgur

那么每个图片就是Haystack文件中的一个Needle了。Store机器内存中维护从volume id和图片名称到其对应的Needle位置及长度的映射关系。从而将读取图片的操作变成一次内存查找和一次磁盘读取。从上图可以看出，Needle中还记录了其他有用的信息，Cookie用特殊的创建时指定串来避免网络攻击，Alternate Key标识同一个图片的不同尺寸，Flags指明当前Needle的图片是否已经被删除。Store支持的基本功能如下：

Read

用户提供volume id、key 、Alternate key、cookie
从内存中查找对应的文件中的Needle offset size
从硬盘中读取needle

Write

上传的图片被直接Append到文件的末尾
不能直接支持修改操作
图片的修改时会Append新的Needle，如果被Append到同一个Volume，则Store通过offset来判断哪个是有效的Needle（Offset的大的那个），无效的一个会在之后的定时Compaction任务中被删除。

Delete

在内存和Needle中同时标记为Deleted，空间回收同样依赖之后的定时Compaction任务。

Index

为了方便启动时从文件中恢复内存中的映射关系，Store会将映射关系的快照记录在index文件中，由于index文件是异步写的，就带来了可能得不一致问题：

图片存在但index文件中没有记录：启动时，首先将Store中没有记录到index的图片信息记录到index（index中最后一个记录offset之后的）
图片被删除，但index文件中没有记录：将index加载之后会检查对应的delete flag，如果已经被delete，则修改内存和index记录

Compaction

从上面可以看出，被删除的图片只是被标记为删除，缺仍然占用宝贵的存储资源，同样的情况也发生在修改操作带来的图片重复。为了解决这个问题，释放多余空间，Haystack引入了Compaction操作。Compaction操作遍历整个文件，检查标记并将仍然有效的Needle拷贝到新的文件中去，整个过程中仍然可以接受读写请求，直到Compaction操作到达文件末尾，此时交换两个文件并删除旧的。

可以看出Haystack采取了很直接的方法来回收空间，从而给写入和修改带来较好的性能，而这种做法之所以奏效也是建立在其所面对的图片场景的：新的社交图片很少被删除。

故障处理

Haystack的故障处理非常的简单暴力，检测程序会不断的检查所有的Store中volume是否能正确读写，一旦发现异常，便需要人工接入进行处理，甚至数据拷贝。

总结

Haystack针对海量的社交图片存储设计了高效的存储服务，这里总结其设计关键点如下：

元信息及内容数据分离
小文件合并成大文件减少元信息数量

参考

论文：Finding a needle in Haystack: Facebook’s photo storage