掌握聚合最新动态了解行业最新趋势
API接口,开发服务,免费咨询服务

Facebook Haystack: 小文件解决方案

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

背景:


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

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

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

FacebookHaystack简介:


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

Haystack的数据文件部分:



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

Haystack的索引文件部分:



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

面临的问题:


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

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

  • 1.存储服务器内存不会太大,一般为32G64G
  • 2.小文件对应的key大小难控制,一般选择文件内容的MD5SHA1作为该文件的key。

场景举例:

一台存储服务器有124T磁盘,内存为32GB左右。服务器上现需存储大小约为4K的头像、缩略图等文件,约为10亿个。文件的key使用MD5,加上offsetsize字段,平均一个小文件对应的索引信息占用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. 索引文件中offsetsize字段,通过512字节对齐,节省1个字节;并根据整个Haystack_plus数据文件实际大小计算offsetsize使用的字节数。

3. Haystack_plus的不同之处:


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


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


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

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


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

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

4. 索引搜索流程为:



5. 请求不存在的文件:

问题:

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

解决方法:

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


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

6. 前缀压缩,效果如何:


Facebook Haystack对内存消耗:

场景举例:  

文件(如:头像、缩略图等)大小4KkeyMD5

FacebookHaystack

  • key: 使用全量的key,为16字节。
  • offset, size:needle为追加写入,因此offsetsize大小固定offset8字节,size4字节。


Haystack_plus

  • key: 使用key的前4字节, 4字节。
  • offset: 根据Haystack_plus数据文件的地址空间计算字节数,并按512字节对齐,为 4字节。
  • size: 根据实际文件的大小计算字节数,并按512对齐,为1字节。


从上图可以看出在文件数量为10亿的情况下,使用FacabookHaystack消耗的内存超过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  layer index文件: 保存needle list在内存中的索引信息;

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

· attribute文件: 保存系统的属性信息(chunkSHA1)

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

  • 1)Haystack_plus数据文件被拆分为多个chunk组织,chunk1, chunk2chunk3 ….
  • 2)分成多个chunk的好处:

· 数据损坏时,不影响其它chunk的数据;

· 数据恢复时,只需恢复损坏的chunk

  • 3)每个chunkSHA1值存放在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%。

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


原文来自:SDK.cn

声明:所有来源为“聚合数据”的内容信息,未经本网许可,不得转载!如对内容有异议或投诉,请与我们联系。邮箱:marketing@think-land.com

0512-88869195
数 据 驱 动 未 来
Data Drives The Future