大规模分布式文件系统元数据管理系统设计

1、大规模分布式文件系统元数据管理系统设计案例背景大规模文件系统的现状和挑战SlimFS:元数据本地存储引擎In()xFS: 分布式元数据管理服务案例总结2现代文件系统的现状和挑战云计算和超级计算机对存储系统的可扩展性有巨大需求Amazon S3: 2013年就有2 )亿个对象企业集群和超算集群: 有大華小文件25%40% files 4K文件系统上的业务成多样性互联网用户数据的离线批華分析机器学习和数值计算的迭代分析交互性强的及时数据分析 December 164现代存储系统的发展趋势单个存储硬件设备的容華持续增大几TB的固态硬盘和硬盘中位数文件大小: 普通台式机4KB, 数据集群128KB单个

2、存储设备可能存有几亿文件固态硬盘的广泛使用更快的随机读有写寿命的限制其他存储设备：NVRAM, SMR HDD分布式元数据管理系统的需求传统分布式文件系统对元数据管理并没有很好的伸缩性支持单个服务器管理元数据(e.g. Lustre/HDFS)用简化的对象空间 (e.g. Amazon S3)对文件系统树进行静态划分 (e.g. Fed. HDFS/Lustre 2.4)没有针对固态硬盘进行设计DataseDrvaetraseDrvaetarserverDataDataDataDataseDrvaetraseDrvaetraseDrvaetraseDrvaetraseDrvaetarserve

3、rseDrvaetarserverseDrvaetarserverseDrvaetarserver客端数据访问路径: (read, write)元数据访问路径: (stat, chmod, etc.) metadata)应用应用5解决方案：IndexFS & SlimFS单节点元数据服务需要可扩展性好，自动负载均衡的元数据管理系统IndexFS：中间件系统能对已有的文件系统提供元数据管理利用已有分布式文件系统作2对象存储从而提供额外的小文件和元数据的管理SlimFS：快速本地元数据存储引擎IndexFSmetadataserverIndexFSmetadata serverIndexFS元数据

4、服务器SlimFS分布式化6案例背景SlimFS:元数据本地存储引擎问题分析高效的内存索引有效减少写放大实验结果In()xFS: 分布式元数据存储服务案例总结7文件系统元数据表单设计KeyValue1, a$ributes2, a$ributes3, a$ributes4, a$ributes5, a$ributesLexicographic orderhomebob思想：将元数据树状结构转化成2键值存储(KV Store)关键字: ，文件名值域: inode 所有相关属性(如文件大小，访问时间，权限等）/03alice 21book5carol48使用基于LSM-Trees的KV存储Log-

5、structured Merge Tree ONeil96 :(种写优化的B-Tree较小的写放大, 较少的随机写，适合大容華磁盘和固态硬盘平均读取延迟和传统B-Tree相当开源实现：LevelDB (Google),RocksDB (Facebook)5004003002001000CreateQuery (50%R+50%W)RenameDeleteThroughput (ops/ second)Ext4BtrfsXFSTableFS-FUSE使用LevelDB9 December 16背景：LSM Tree的存储结构(1 新插入的记录首先存储在内存表CMemTable）和磁盘日志CLog

6、）中当内存表足够大，将被转化成SSTable顺序写到第0层树上通过使用内存缓存和日志将随机写转化成顺序写Level 0Level 1Level 2Compaction整理橾作Lookup橾 作.10 December 16Level 1Level 2Compaction整理橾作2限制读取延迟，需要限制查询SSTables的次数:LSM-Tree维护(个指数分布的存储结构第k+1层的SSTable大小之和是第k层的 r 倍对于有N个记录的LSM-Tree大概有O(logrN)Compaction操作将合并排序第k层的SSTables,然后存到第k+1层Level 0Lookup橾作.背景：LSM

7、 Tree的存储结构(2 11 December 16对索引的使用Block 012 December 16Block 1SSTable是(个存储排序后的记录的文件格式其中有文件块索引用于对记录进行定位同时有布隆过滤器来避免无意义的查询Block index 文件索引01N-1011101010000000111011011001101100001Block NGet 0001Get 0101YesNoBloom filter布隆 器元数据本地存储的设计折衷启发：需要新的方案能用较少的内存达到好的读写性能根据文件系统的操作语义优化数据索引用新的数据存储结构来减少写放大内存消耗放大写放大13 D

8、ecember 16案例背景SlimFS:元数据本地存储引擎问题分析高效的内存索引有效减少写放大实验结果In()xFS: 分布式元数据存储服务案例总结14高效内存索引15 December 16目标设计空间利用率高的内存索引来降低读取延迟减少读取尾延迟Multi-level cuckoo filter减少读取平均延迟压缩文件快索引: a three-level indexLSM-Tree中的尾延迟问题布隆过滤器的假阳性是的查询需要读多个SSTable假设有n层, 每层假阳性率是 那么总共的假阳性率是n * 多层意味着更大的尾延迟16 December 16L0L1Ln多层次Cuckoo过滤器(

9、MLCF)核心想法: 基于cuckoo filter Fan14将fingerprint和层次信息存储在Cuckoo哈希表中Fingerprint(x):对于 = 0.1%, fingerprint大小213 bits, 小于布隆过滤器L0L1L2f(x1), 2f(x3), 1f(x2), 1Cuckoo hashing tablex2,x3x1SSTablesx417 December 16减少MLCF中的假阳性率L18 December 160L1L2f(x1), 2f(x3), 1f(x2), 1Cuckoo hashing tablex4x2,x3x1用额外的二级表存储这些冲突二级表

10、保存完整的key和层次信息当插入(个新的key如果其fingerprint存在, 则将其存入二级表此方法只使用插入时需检查重复性的操作SSTablesx4, 0Secondary hashing tableAssume f(x1) = f(x4)SSTable中的块索引查找011101010000原始SSTable查询过程:首先查找块索引, 然后读取相应文件块对块索引进行缓存来减少磁盘读取块索引越小越容易缓存01N-1Block index索引00011101101100110110000119 December 16高压缩的块索引20 December 16基于Entropy-Coded T

11、ries Lim12:对于纯哈希的字段keys每个KV对只需要2.5 bit来映射其所在位置SlimFS的key由两个哈希后的字段组成利用ECT 分别压缩两个字段只存储其相应的块所在位置空间损耗降低到每个KV对只需要0.7bit比LevelDB的每个KV需要1 byte要小很多案例背景SlimFS:元数据本地存储引擎问题分析高效的内存索引有效减少写放大实验结果In()xFS: 分布式元数据存储服务案例总结21Stepped-Merge算法减少compaction整理操作来降低写放大每层里面有多个自层Compaction整理操作合并多个子层到下(层减少了r倍写 December 1622Leve

12、l 0Level 1Level 2.Compaction整理橾作.r sub-levelsLookup又橾作列模式的元数据表单Log file #1Log file #2Log file #n(, ptr)(, ptr)基于列的存储模式CColumn Store）:记录中的值部分直接存储到非SSTable的日志文件中KV数据库中只保存指向数据的指针Compaction整理操作,会整理数据延迟对删除的元数据的整理只整理指KV StoreNo compaction23案例背景SlimFS:元数据本地存储引擎现有解决方案和问题分析高效的内存索引有效减少写放大实验结果In()xFS: 分布式元数据存储

13、服务案例总结24SlimFS 与现有方案的比较工作负载：随机建立和访问4亿空文件比使用LevelDB的解决方案写快4倍，读快3.5倍优化方法：高效内存索引和减少写放大40.0715.8611.1214.76051015202530354045Averae throuhput (KOP/s)File CreationsSlimFSRocksDBLevelDBHyperLevelDB1828140054058004008001200160020002400File StatsSlimFSRocksDBLevelDBHyperLevelDB25 December 16建立文件吞吐華26 Decemb

14、er 16读取延迟27 December 16案例背景SlimFS:元数据本地存储引擎In()xFS: 分布式元数据存储服务元数据存储服务架构命名空间的划分热点减轻实验结果案例总结28IndexFS的系统设计框架使用其他分布式系(Lustre /HDFS) 作象存DataDataserverDataserverDataserverseDrvaetraDataDataDataseDrvaetarserverseDrvaetarserverseDrvaetarserverseDrvaetarserverMetadata ServerIndexFSclientAppsIndexFSclientApp

15、sIndexFS客户端库应用元数据路径(stat, open)数据路径(read, write)IndexFSmetadata serverIndexFSmetadataIndexFS元数据服务器server数据路径SlimFS29IndexFS 建立在已有的分布式文件系统上利用已有分布式文件系统作2对象存储从而提供额外的小文件和元数据的管理文件系统树分布策略1)book 5homebobalice 214carol/对文件系统树进行功能的划分目录元数据管理服务：所有目录信息存在(个单机上，易于实现文件元数据和文件块管理服务：分布式存储在多台机器上/ 0目管理服器3comic 6song文件管

16、理服器文件管理服器30文件系统树分布策略2)当目录服务器需要进行分布式存储的时候在建立目录时利用哈希算法的将其分配到(个服务器上让目录存储能够负载均衡homebob/ 03alice 214carol/034目管理服器031目管理服器11目管理服器22目管理服器3动态划分大目录使用GIGA+ 算法进行对目录增華划分 PaNl11当目录的文件数目增大，进行二元划分，直至每个服务器都存有目录 的(部分动态负载均衡大目录Binary split a large directoryServer1/big1/.P0/_b1_b4_b650%filesServer2/big1/.P1/_b2_b3_b55

17、0%files32解决服务器热点问题所有查询操作从根目录开始路径查询需要访问每个祖先目录很容易造成某些服务器成2热点解决方案：对很少变化的目录信息进行带租约的缓存homebob/ 03alice 21carol4/04点目管理服器0目管理服器131目管理服器22目管理服器 333案例背景SlimFS:元数据本地存储引擎In()xFS: 分布式元数据存储服务元数据存储服务架构命名空间的划分热点减轻实验结果案例总结可扩展性实验: 空文件创建工作负载: 在(个目录中创建大華文件使用PRObE Kodiak的128节点集群 (8-yr old LANL hardware)400200060080010

18、008128Aggregate file create throughput(K creates/sec)163264Cluster size (Number of servers)LinearIndexFS-PVFSPVFS-R35AM Disk比单节点HDFS & Lustre快100-450倍05505005,000mknodstatremoveThroughput (K ops/sec)IndexFS-Lustre (Total, 32 servers)IndexFS-Lustre (Per-server) Lustre (Single server)01101001,00010,00

19、0mknodstatremoveThroughput (K ops/sec)IndexFS-HDFS (Total, 128 servers) IndexFS-HDFS (Per-server)HDFS (Single server)3x450 x3x36100 x性能评测实验IndexFS 跑在有128个节点的PVFS集群所有元数据和文件通过SlimFS打包存储在PVFS上工作负载:重播Linkedin的Trace：1 million ops per server预先建立好目录，实验时只创建文件Trace中包含10M对象和130M操作操作分布: 90% reads, 10% mutation

20、s0.20.10Faction of TotalOperationsOpenReaddirMknodRenameFMkdirChmodRemove37实验结果: 吞吐華文件夹信息缓存减轻了减轻了热点，消除了瓶颈10100100081664128吞吐華 (K ops/sec)32服务器个数IndexFS+Rate (r/(r+w) sec)PVFS+RAM DiskIndexFS+NoCache1.5x4x10 x案例技术总结SlimFS: 利用文件系统语义优化元数据本地存储使用高效的内存索引加快读取速度利用列存储和Step-Merge算法减小写放大IndexFS: 基于目录对

21、文件命名空间进行划分先按照功能对文件系统树进行划分随机划分目录对小目录进行负载均衡使用可变租约对目录信息进行只读缓存，消除热点参考文献Ren14 IndexFS: Scaling File System Metadata Performance with Stateless Caching and Bulk Insertion. Kai Ren, Qing Zheng, Swapnil Patil and Garth Gibson. SC 2014Ren13 TableFS: Enhancing metadata efficiency in local file systems. Kai Re

22、n and Garth Gibson. USENIX ATC 2013Welch13 Optimizing a hybrid ssd/hdd hpc storage system based on file size distributions. Brent Welch and Geoffrey Noer.29th IEEE Conference on Massive Data Storage, 2013.Meister12 A Study on Data Deduplication in HPC Storage Systems. Dirk Meister, Jurgen Kaiser, Andre Brinkmann, Toni Cortes, Micha