小文件合并存储问题

LOSF(lots of small files）问题是很多互联网企业都会遇到的, 文本、图片、音乐是典型的小文件应用场景，比如58同城、淘宝网、虾米网、汽车之家等网站都是有海量小文件存储需求的。

小文件存储问题集中表现在如下几个方面：

1. 小文件太多，单机无法存储 2. 小文件的存取性能 3. 小文件的高效备份与恢复

对于问题1，主要是借助分布式技术来解决，单机存储不了，就将数据分散存储到多台机器，并通过在软件层做封装提供统一的存储接口，使得存储服务的使用者不需要关心数据是如何存储、存储在哪里的。

对于问题2，以磁盘为存储介质的单机文件系统（如ext4、xfs等），文件都是以目录树结构来组织的，当文件数很多时，目录内的文件数会很多、目录层次也会变深，使得路径查找（sys_open）是非常影响性能的，一次路径名查找可能需要多次磁盘IO。

对于问题3，小文件的备份与恢复实际上还是LOSF问题，因为小文件访问存在性能问题，那么其备份与恢复肯定也是效率极低的，通常问题1、2解决了，这个问题也就迎刃而解。

TFS（Taobao File System)是淘宝解决海量小文件存储自主研发的分布式文件系统，通过将数据分布到多个存储节点来解决问题1、通过将多个小文件打包存储到大文件（block）以及扁平化的目录结构来解决问题2、通过block多副本以及按block复制的方式来解决问题3。

本文重点探讨多个小文件存储到大文件的问题，除TFS外，、等针对小文件也有类似的解决方案。把小文件存储到大文件，要解决如何存、如何取得问题。目前比较典型的解决方案是，存储时将小文件追加到block的尾部，并为小文件建立索引用于快速定位；在访问时，先根据索引来获取文件在block内的offset和size，然后从block读取文件数据；关键的问题是索引该如何存储？

为方便说明问题，约定用于存储多个小文件的大文件称作一个block，通常64MB大小，block内部存储的每个文件由一个fileid标识。

方案一

索引文件不持久化存储，在内存里组织为hash表（或顺序表，如果能接受二分查找的性能）；存储时将文件追加到block尾部后，将文件在block内部的offset以及文件size信息，插入到hash表中；访问该文件时，先根据文件的id在hash表中定位文件的offset和size，然后在block对应位置读取文件数据，由于hash表是全内存化的，访问文件只需一次IO。

这种方案的优点在于，每次存储文件时，只需要一次IO操作，不会出现索引与block实际文件数据不一致大情况；缺点在于，索引只存在于内存，当服务重启时，index信息需要根据block的数据来重建，,这就要求文件在block中存储时，必须存储一些额外的头信息，比如magicnum，使得block的文件具有自描述能力，在每次启动时，通过扫描block数据来生成index。

以2T磁盘、64MB block为例，磁盘上会有约30000个block；假设扫描一个block需要1s，那么启动时间约为500min * 0.8（磁盘使用率80%）= 400min，显然，每次启动时扫描block来生成index的开销是不可接受的。

方案二

在方案一的基础上，每个block对应一个index文件，写文件时先将文件数据追加到block的尾部，然后将文件的index插入到内存hash表，最后将文件的index追加到index文件；在存储服务重启时，每个block根据其index文件来快速建立内存hash表。

上述方案解决了索引重建的问题，但其每次写文件需要两次IO，写文件的延时就高了。为了降低写的延时，facebook在里使用了一种折中的方案。文件写入时，往block追加文件数据时同步刷盘，然后将记录插入到内存hash表，接下来追加index记录时，发送完追加请求就认为写文件成功，即index并不立即刷盘，这样写的延时缩短到一次IO。

文件index异步追加，可能导致一个问题，文件在block里存在，但在index文件里没有这个文件的记录，在根据index文件重建内存hash表时，hash表就是不完整的，导致部分文件访问不到。haystack通过在重建时，从block尾部开始扫描，找出所有可能缺失index的文件，并生成index追加到index文件。（因为文件在block和index里顺序相同，缺失index的文件一定是在block尾部的一批）

方案三

方案二中index的数据实际上是存在两份的，一份是内存hash表里的，一份是index文件里的，因为linux的页缓存机制，文件里的index也是可能cache在内存里，所以方案二对内存的利用不是最优的，可以考虑将index文件和index内存hash表合二为一，将index文件本身以hash表的方式组织，直接使用mmap将index文件映射到内存。

通过将index文件和内存hash表合二为一，操作内存index即为操作index文件，管理index会方便不少。为了解决hash冲突问题，每个index条目需要额外增加一个next字段用于连接冲突链。

这种方案还存在hash扩展的问题，当block内存储的小文件数量很多时，按照预估的hash桶数（预估值通常不会太大，太大会有很多空间浪费），可能会导致冲突链很长，这时要提高hash查找的效率就必须扩展桶的数量，如果使用方案一，扩展只会导致额外的内存拷贝，而在这个方案里，则会导致整个index文件重写，会产生IO操作。

转载请注明转自Yun Notes，原文链接：小文件合并存储问题