https://code.facebook.com/posts/685565858139515/needle-in-a-haystack-efficient-storage-of-billions-of-photos/

http://www.sohu.com/a/112191770_222486

作者简介

陈闯，花名“战士雷欧”，白山云科技超级攻城狮。

Linux内核、nginx模块、存储架构开发老司机，7年以上存储架构、设计及开发经验，先后就职于东软、中科曙光、新浪、美团，擅长独立进行Haystack、纠删码等各种项目研发，爱好不断降低IO、挑战冗余度底线。白山滑板车选手专业十级，会漂移，正积极备战方庄街道第6届动感滑板车运动会，家庭梦想是为爱妻赢得无硅油洗发水。

正文

背景：

当今互联网，数据呈现爆炸式增长，社交网络、移动通信、网络视频、电子商务等各种应用往往能产生亿级甚至十亿、百亿级的海量小文件。由于在元数据管理、访问性能、存储效率等方面面临巨大的挑战，海量小文件问题成为了业界公认的难题。

业界的一些知名互联网公司，也对海量小文件提出了解决方案，例如：著名的社交网站Facebook，存储了超过600亿张图片，专门推出了Haystack系统，针对海量小图片进行定制优化的存储。

白山云存储CWN-X，针对小文件问题，也推出独有的解决方案，我们称之为Haystack_plus。该系统提供高性能数据读写、数据快速恢复、定期重组合并等功能。

Facebook的Haystack简介：

Facebook的Haystack对小文件的解决办法是合并小文件。将小文件数据依次追加到数据文件中，并且生成索引文件，通过索引来查找小文件在数据文件中的offset和size，对文件进行读取。

Haystack的数据文件部分：

Haystack的数据文件，将每个小文件封装成一个needle，包含文件的key、size、data等数据信息。所有小文件按写入的先后顺序追加到数据文件中。

Haystack的索引文件部分：

Haystack的索引文件保存每个needle的key，以及该needle在数据文件中的offset、size等信息。程序启动时会将索引加载到内存中，在内存中通过查找索引，来定位在数据文件中的偏移量和大小。

面临的问题:

Facebook的Haystack特点是将文件的完整key都加载到内存中，进行文件定位。机器内存足够大的情况下，Facebook完整的8字节key可以全部加载到内存中。

但是现实环境下有两个主要问题：

1.存储服务器内存不会太大，一般为32G至64G；

2.小文件对应的key大小难控制，一般选择文件内容的MD5或SHA1作为该文件的key。

场景举例：

一台存储服务器有12块4T磁盘，内存为32GB左右。

服务器上现需存储大小约为4K的头像、缩略图等文件，约为10亿个。

文件的key使用MD5，加上offset和size字段，平均一个小文件对应的索引信息占用28字节。

在这种情况下，索引占用内存接近30GB, 磁盘仅占用4TB。内存消耗近100%，磁盘消耗只有8%。

所以索引优化是一个必须要解决的问题。

Haystack_plus：

Haystack_plus的核心也由数据文件和索引文件组成。

1. Haystack_plus的数据文件：

与Facebook的Haystack类似，Haystack_plus将多个小文件写入到一个数据文件中，每个needle保存key, size, data等信息。

2. Haystack_plus的索引文件：

索引是我们主要优化的方向：

1. 索引文件只保存key的前四字节，而非完整的key；

2. 索引文件中的offset和size字段，通过512字节对齐，节省1个字节；并根据整个Haystack_plus数据文件实际大小计算offset和size使用的字节数。

3. Haystack_plus的不同之处：

数据文件中的needle按照key的字母顺序存放。

由于索引文件的key，只保存前四字节，如果小文件key的前四字节相同，不顺序存放，就无法找到key的具体位置。可能出现如下情况：

例如：用户读取的文件key是0x ab cd ef ac ee，但由于索引文件中的key只保存前四字节，只能匹配0x ab cd ef ac这个前缀，此时无法定位到具体要读取的offset。

我们可以通过needle顺序存放，来解决这个问题：

例如：用户读取文件的key是0x ab cd ef ac bb，匹配到0x ab cd ef ac这个前缀，此时offset指向0x ab cd ef ac aa这个needle，第一次匹配未命中。

通过存放在needleheader中的size，我们可以定位0x ab cdef ac bb位置，匹配到正确needle，并将数据读取给用户。

4. 索引搜索流程为：

5. 请求不存在的文件：

问题：

我们应用折半查找算法在内存查找key ，时间复杂度为O(log(n))，其中n为needle数目。索引前缀相同时，需要在数据文件中继续查找。此时访问的文件不存在时，容易造成多次IO查找。

解决方法：

在内存中，将存在的文件映射到 bloomfilter中。此时只需要通过快速搜索，就可以排除不存在的文件。

时间复杂度为 O(k)， k为一个元素需要的bit位数。当k为9.6时，误报率为1%，如果k再增加4.8，误报率将降低为0.1%。

6. 前缀压缩，效果如何：

与Facebook Haystack对内存消耗：

场景举例:

文件（如：头像、缩略图等）大小4K，key为MD5

Facebook的Haystack：

key: 使用全量的key，为16字节。

offset, size:needle为追加写入，因此offset和size大小固定，offset为8字节，size为4字节。

Haystack_plus：

key: 使用key的前4字节，为4字节。

offset: 根据Haystack_plus数据文件的地址空间计算字节数，并按512字节对齐，为 4字节。

size: 根据实际文件的大小计算字节数，并按512对齐，为1字节。

从上图可以看出在文件数量为10亿的情况下，使用Facabook的Haystack消耗的内存超过26G，使用Haystack_plus仅消耗9G多内存，内存使用降低了2/3。

7.索引优化根本就停不下来：

10 亿 个4K小文件，消耗内存超过9G。

Key占用4字节，Offset占用4字节，还需要再小一些。

下面介绍索引分层:

根据文件key的前缀，进行分层，相同的前缀为一层。

分层的好处：

(1)减少key的字节数：

通过分层，只保存一份重复的前缀，节省key的字节数。

(2)减少offset的字节数：

优化前的offset，偏移范围为整个Haystack_plus的数据文件的地址空间。

优化后，只需在数据文件中的层内进行偏移，根据最大的层地址空间可以计算所需字节数，

分层后的效果：

从上图可以看出，进行分层后，内存消耗从优化前的9G多，降低到4G多，节省了一半的内存消耗。

Haystack_plus整体架构：

1.Haystack_plus组织：

每台服务器上，我们将所有文件分成多个group，每个group创建一个Haystack_plus。系统对所有的Haystack_plus进行统一管理。

读、写、删除等操作，都会在系统中定位操作某个Haystack_plus，然后通过索引定位具体的needle，进行操作。

2.索引组织

之前已经介绍过，所有needle顺序存放，索引做前缀压缩，并分层。

3.文件组成：

chunk文件: 小文件的实际数据被拆分保存在固定数量的chunk数据文件中，默认为12个数据块；

needle list文件: 保存每个needle的信息(如文件名、offset等)；

needle index 和layerindex文件: 保存needle list在内存中的索引信息；

global version文件: 保存版本信息,创建新version时自动将新版本信息追加到该文件中；

attribute文件: 保存系统的属性信息(如chunk的SHA1等)；

original filenames: 保存所有文件原始文件名。

（1）Haystack_plus数据文件被拆分为多个chunk组织，chunk1,chunk2，chunk3 ….

（2）分成多个chunk的好处：

数据损坏时，不影响其它chunk的数据；

数据恢复时，只需恢复损坏的chunk。

（3）每个chunk的SHA1值存放在attribute文件中。

4.版本控制：

由于needle在数据文件中按key有序存放，为不影响其顺序，新上传的文件无法加入Haystack_plus，而是首先被保存到hash目录下，再通过定期自动合并方式，将新文件加入到Haystack_plus中。

合并时将从needle_list文件中读取所有needle信息，将删除的needle剔除，并加入新上传的文件，同时重新排序，生成chunk数据文件、索引文件等。

重新合并时将生成一个新版本Haystack_plus。版本名称是所有用户的文件名排序的SHA1值的前4字节。

每半个月系统自动进行一次hash目录检查，查看是否有新文件，并计算下所有文件名集合的SHA1，查看与当前版本号是否相同，不同时说明有新文件上传，系统将重新合并生成新的数据文件。

同时，系统允许在hash目录下超过指定的文件数时，再重新创建新版本，从而减少重新合并次数。

版本的控制记录在global_version文件中，每次创建一个新版本，版本号和对应的crc32将追加到global_version文件（crc32用于查看版本号是否损坏）。

每次生成新版本时，自动通知程序重新载入索引文件、attribute文件等。

5.数据恢复：

用户的文件将保存成三副本存放，因此Haystack_plus也会存放在3台不同的机器上。

恢复场景一:

当一个Haystack_plus的文件损坏时，会在副本机器上，查找是否有相同版本的Haystack_plus，如果版本相同，说明文件的内容都是一致，此时只需将要恢复的文件从副本机器下载下来，进行替换。

恢复场景二:

如果副本机器没有相同版本的Haystack_plus，但存在更高版本，那此时可以将该版本的整个Haystack_plus从副本机器上拷贝下来，进行替换。

恢复场景三:

如果前两种情况都不匹配，那就从另外两台副本机器上，将所有文件都读到本地上的hash目录下，并将未损坏的chunk中保存的文件也提取到hash目录下，用所有文件重新生成新版本的Haystack_plus。

Haystack_plus效果如何：

在使用Haystack_plus后一段时间，我们发现小文件的整体性能有显著提高，RPS提升一倍多，机器的IO使用率减少了将近一倍。同时，因为优化了最小存储单元，碎片降低80%。

使用该系统我们可以为用户提供更快速地读写服务，并且节省了集群的资源消耗