【作者简介:陈闯,花名“战士雷欧”,白山云科技超级攻城狮。Linux内核、nginx模块、存储架构开发老司机,7年以上存储架构、设计及开发经验,先后就职于东软、中科曙光、新浪、美团,擅长独立进行Haystack、纠删码等各种项目研发,爱好不断降低IO、挑战冗余度底线。白山滑板车选手专业十级,会漂移,正积极备战方庄街道第6届动感滑板车运动会,家庭梦想是为爱妻赢得无硅油洗发水。】
当今互联网,数据呈现爆炸式增长,社交网络、移动通信、网络视频、电子商务等各种应用往往能产生亿级甚至十亿、百亿级的海量小文件。由于在元数据管理、访问性能、存储效率等方面面临巨大的挑战,海量小文件问题成为了业界公认的难题。
业界的一些知名互联网公司,也对海量小文件提出了解决方案,例如:著名的社交网站Facebook,存储了超过600亿张图片,专门推出了Haystack系统,针对海量小图片进行定制优化的存储。
白山云存储CWN-X,针对小文件问题,也推出独有的解决方案,我们称之为Haystack_plus。该系统提供高性能数据读写、数据快速恢复、定期重组合并等功能。
Facebook的Haystack对小文件的解决办法是合并小文件。将小文件数据依次追加到数据文件中,并且生成索引文件,通过索引来查找小文件在数据文件中的offset和size,对文件进行读取。
Haystack的数据文件,将每个小文件封装成一个needle,包含文件的key、size、data等数据信息。所有小文件按写入的先后顺序追加到数据文件中。
Haystack的索引文件保存每个needle的key,以及该needle在数据文件中的offset、size等信息。程序启动时会将索引加载到内存中,在内存中通过查找索引,来定位在数据文件中的偏移量和大小。
Facebook的Haystack特点是将文件的完整key都加载到内存中,进行文件定位。机器内存足够大的情况下,Facebook完整的8字节key可以全部加载到内存中。
但是现实环境下有两个主要问题:
场景举例:
一台存储服务器有12块4T磁盘,内存为32GB左右。服务器上现需存储大小约为4K的头像、缩略图等文件,约为10亿个。文件的key使用MD5,加上offset和size字段,平均一个小文件对应的索引信息占用28字节。
在这种情况下,索引占用内存接近30GB, 磁盘仅占用4TB。内存消耗近100%,磁盘消耗只有8%。所以索引优化是一个必须要解决的问题。
Haystack_plus的核心也由数据文件和索引文件组成。
与Facebook的Haystack类似,Haystack_plus将多个小文件写入到一个数据文件中,每个needle保存key, size, data等信息。
索引是我们主要优化的方向:
1. 索引文件只保存key的前四字节,而非完整的key;
2. 索引文件中的offset和size字段,通过512字节对齐,节省1个字节;并根据整个Haystack_plus数据文件实际大小计算offset和size使用的字节数。
数据文件中的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,第一次匹配未命中。
通过存放在needle header中的size,我们可以定位0x ab cd ef ac bb位置,匹配到正确needle,并将数据读取给用户。
问题:
我们应用折半查找算法在内存查找key ,时间复杂度为O(log(n)),其中n为needle数目。索引前缀相同时,需要在数据文件中继续查找。此时访问的文件不存在时,容易造成多次IO查找。
解决方法:
在内存中,将存在的文件映射到 bloom filter中。此时只需要通过快速搜索,就可以排除不存在的文件。
时间复杂度为 O(k), k为一个元素需要的bit位数。当k为9.6时,误报率为1%,如果k再增加4.8,误报率将降低为0.1%。
与Facebook Haystack对内存消耗:
场景举例:
文件(如:头像、缩略图等)大小4K,key为MD5
Facebook的Haystack:
Haystack_plus:
从上图可以看出在文件数量为10亿的情况下,使用Facabook的Haystack消耗的内存超过26G,使用Haystack_plus仅消耗9G多内存,内存使用降低了2/3。
10 亿 个4K小文件, 消耗内存超过9G。
Key占用4字节,Offset占用4字节,还需要再小一些。
下面介绍索引分层:
根据文件key的前缀,进行分层,相同的前缀为一层。
优化前的offset,偏移范围为整个Haystack_plus的数据文件的地址空间。
优化后,只需在数据文件中的层内进行偏移,根据最大的层地址空间可以计算所需字节数,
从上图可以看出,进行分层后,内存消耗从优化前的9G多,降低到4G多,节省了一半的内存消耗。
每台服务器上,我们将所有文件分成多个group,每个group创建一个Haystack_plus。系统对所有的Haystack_plus进行统一管理。
读、写、删除等操作,都会在系统中定位操作某个Haystack_plus,然后通过索引定位具体的needle,进行操作。
之前已经介绍过,所有needle顺序存放,索引做前缀压缩,并分层。
· chunk文件: 小文件的实际数据被拆分保存在固定数量的chunk数据文件中,默认为12个数据块;
· needle list文件: 保存每个needle的信息(如文件名、offset等);
· needle index 和 layer index文件: 保存needle list在内存中的索引信息;
· global version文件: 保存版本信息,创建新version时自动将新版本信息追加到该文件中;
· attribute文件: 保存系统的属性信息(如chunk的SHA1等);
· original filenames: 保存所有文件原始文件名。
· 数据损坏时,不影响其它chunk的数据;
· 数据恢复时,只需恢复损坏的chunk。
由于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文件等。
用户的文件将保存成三副本存放,因此Haystack_plus也会存放在3台不同的机器上。
当一个Haystack_plus的文件损坏时,会在副本机器上,查找是否有相同版本的Haystack_plus,如果版本相同,说明文件的内容都是一致,此时只需将要恢复的文件从副本机器下载下来,进行替换。
如果副本机器没有相同版本的Haystack_plus,但存在更高版本,那此时可以将该版本的整个Haystack_plus从副本机器上拷贝下来,进行替换。
如果前两种情况都不匹配,那就从另外两台副本机器上,将所有文件都读到本地上的hash目录下,并将未损坏的chunk中保存的文件也提取到hash目录下,用所有文件重新生成新版本的Haystack_plus。
在使用Haystack_plus后一段时间,我们发现小文件的整体性能有显著提高,RPS提升一倍多,机器的IO使用率减少了将近一倍。同时,因为优化了最小存储单元,碎片降低80%。
使用该系统我们可以为用户提供更快速地读写服务,并且节省了集群的资源消耗。
原文来自:SDK.cn
声明:所有来源为“聚合数据”的内容信息,未经本网许可,不得转载!如对内容有异议或投诉,请与我们联系。邮箱:marketing@think-land.com
通过企业关键词查询企业涉讼详情,如裁判文书、开庭公告、执行公告、失信公告、案件流程等等。
IP反查域名是通过IP查询相关联的域名信息的功能,它提供IP地址历史上绑定过的域名信息。
结合权威身份认证的精准人脸风险查询服务,提升人脸应用及身份认证生态的安全性。人脸风险情报库,覆盖范围广、准确性高,数据权威可靠。
全国城市和站点空气质量查询,污染物浓度及空气质量分指数、空气质量指数、首要污染物及空气质量级别、健康指引及建议采取的措施等。
输入手机号和拦截等级,查看是否是风险号码