大規(guī)模分布式文件系統(tǒng)元數(shù)據(jù)管理系統(tǒng)設(shè)計(jì)

1、大規(guī)模分布式文件系統(tǒng)元數(shù)據(jù)管理系統(tǒng)設(shè)計(jì)案例背景大規(guī)模文件系統(tǒng)的現(xiàn)狀和挑戰(zhàn)SlimFS:元數(shù)據(jù)本地存儲(chǔ)引擎In()xFS: 分布式元數(shù)據(jù)管理服務(wù)案例總結(jié)2現(xiàn)代文件系統(tǒng)的現(xiàn)狀和挑戰(zhàn)云計(jì)算和超級(jí)計(jì)算機(jī)對(duì)存儲(chǔ)系統(tǒng)的可擴(kuò)展性有巨大需求Amazon S3: 2013年就有2 )億個(gè)對(duì)象企業(yè)集群和超算集群: 有大華小文件25%40% files 4K文件系統(tǒng)上的業(yè)務(wù)成多樣性互聯(lián)網(wǎng)用戶數(shù)據(jù)的離線批華分析機(jī)器學(xué)習(xí)和數(shù)值計(jì)算的迭代分析交互性強(qiáng)的及時(shí)數(shù)據(jù)分析 December 164現(xiàn)代存儲(chǔ)系統(tǒng)的發(fā)展趨勢(shì)單個(gè)存儲(chǔ)硬件設(shè)備的容華持續(xù)增大幾TB的固態(tài)硬盤和硬盤中位數(shù)文件大小: 普通臺(tái)式機(jī)4KB, 數(shù)據(jù)集群128KB單個(gè)

2、存儲(chǔ)設(shè)備可能存有幾億文件固態(tài)硬盤的廣泛使用更快的隨機(jī)讀有寫壽命的限制其他存儲(chǔ)設(shè)備：NVRAM, SMR HDD分布式元數(shù)據(jù)管理系統(tǒng)的需求傳統(tǒng)分布式文件系統(tǒng)對(duì)元數(shù)據(jù)管理并沒有很好的伸縮性支持單個(gè)服務(wù)器管理元數(shù)據(jù)(e.g. Lustre/HDFS)用簡化的對(duì)象空間 (e.g. Amazon S3)對(duì)文件系統(tǒng)樹進(jìn)行靜態(tài)劃分 (e.g. Fed. HDFS/Lustre 2.4)沒有針對(duì)固態(tài)硬盤進(jìn)行設(shè)計(jì)DataseDrvaetraseDrvaetarserverDataDataDataDataseDrvaetraseDrvaetraseDrvaetraseDrvaetraseDrvaetarserve

3、rseDrvaetarserverseDrvaetarserverseDrvaetarserver客端數(shù)據(jù)訪問路徑: (read, write)元數(shù)據(jù)訪問路徑: (stat, chmod, etc.) metadata)應(yīng)用應(yīng)用5解決方案：IndexFS & SlimFS單節(jié)點(diǎn)元數(shù)據(jù)服務(wù)需要可擴(kuò)展性好，自動(dòng)負(fù)載均衡的元數(shù)據(jù)管理系統(tǒng)IndexFS：中間件系統(tǒng)能對(duì)已有的文件系統(tǒng)提供元數(shù)據(jù)管理利用已有分布式文件系統(tǒng)作2對(duì)象存儲(chǔ)從而提供額外的小文件和元數(shù)據(jù)的管理SlimFS：快速本地元數(shù)據(jù)存儲(chǔ)引擎IndexFSmetadataserverIndexFSmetadata serverIndexFS元數(shù)據(jù)

4、服務(wù)器SlimFS分布式化6案例背景SlimFS:元數(shù)據(jù)本地存儲(chǔ)引擎問題分析高效的內(nèi)存索引有效減少寫放大實(shí)驗(yàn)結(jié)果In()xFS: 分布式元數(shù)據(jù)存儲(chǔ)服務(wù)案例總結(jié)7文件系統(tǒng)元數(shù)據(jù)表單設(shè)計(jì)KeyValue1, a$ributes2, a$ributes3, a$ributes4, a$ributes5, a$ributesLexicographic orderhomebob思想：將元數(shù)據(jù)樹狀結(jié)構(gòu)轉(zhuǎn)化成2鍵值存儲(chǔ)(KV Store)關(guān)鍵字: ，文件名值域: inode 所有相關(guān)屬性(如文件大小，訪問時(shí)間，權(quán)限等）/03alice 21book5carol48使用基于LSM-Trees的KV存儲(chǔ)Log-

5、structured Merge Tree ONeil96 :(種寫優(yōu)化的B-Tree較小的寫放大, 較少的隨機(jī)寫，適合大容華磁盤和固態(tài)硬盤平均讀取延遲和傳統(tǒng)B-Tree相當(dāng)開源實(shí)現(xiàn)：LevelDB (Google),RocksDB (Facebook)5004003002001000CreateQuery (50%R+50%W)RenameDeleteThroughput (ops/ second)Ext4BtrfsXFSTableFS-FUSE使用LevelDB9 December 16背景：LSM Tree的存儲(chǔ)結(jié)構(gòu)(1 新插入的記錄首先存儲(chǔ)在內(nèi)存表CMemTable）和磁盤日志CLog

6、）中當(dāng)內(nèi)存表足夠大，將被轉(zhuǎn)化成SSTable順序?qū)懙降?層樹上通過使用內(nèi)存緩存和日志將隨機(jī)寫轉(zhuǎn)化成順序?qū)慙evel 0Level 1Level 2Compaction整理橾作Lookup橾 作.10 December 16Level 1Level 2Compaction整理橾作2限制讀取延遲，需要限制查詢SSTables的次數(shù):LSM-Tree維護(hù)(個(gè)指數(shù)分布的存儲(chǔ)結(jié)構(gòu)第k+1層的SSTable大小之和是第k層的 r 倍對(duì)于有N個(gè)記錄的LSM-Tree大概有O(logrN)Compaction操作將合并排序第k層的SSTables,然后存到第k+1層Level 0Lookup橾作.背景：LSM

7、 Tree的存儲(chǔ)結(jié)構(gòu)(2 11 December 16對(duì)索引的使用Block 012 December 16Block 1SSTable是(個(gè)存儲(chǔ)排序后的記錄的文件格式其中有文件塊索引用于對(duì)記錄進(jìn)行定位同時(shí)有布隆過濾器來避免無意義的查詢Block index 文件索引01N-1011101010000000111011011001101100001Block NGet 0001Get 0101YesNoBloom filter布隆 器元數(shù)據(jù)本地存儲(chǔ)的設(shè)計(jì)折衷啟發(fā)：需要新的方案能用較少的內(nèi)存達(dá)到好的讀寫性能根據(jù)文件系統(tǒng)的操作語義優(yōu)化數(shù)據(jù)索引用新的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)來減少寫放大內(nèi)存消耗放大寫放大13 D

8、ecember 16案例背景SlimFS:元數(shù)據(jù)本地存儲(chǔ)引擎問題分析高效的內(nèi)存索引有效減少寫放大實(shí)驗(yàn)結(jié)果In()xFS: 分布式元數(shù)據(jù)存儲(chǔ)服務(wù)案例總結(jié)14高效內(nèi)存索引15 December 16目標(biāo)設(shè)計(jì)空間利用率高的內(nèi)存索引來降低讀取延遲減少讀取尾延遲Multi-level cuckoo filter減少讀取平均延遲壓縮文件快索引: a three-level indexLSM-Tree中的尾延遲問題布隆過濾器的假陽性是的查詢需要讀多個(gè)SSTable假設(shè)有n層, 每層假陽性率是 那么總共的假陽性率是n * 多層意味著更大的尾延遲16 December 16L0L1Ln多層次Cuckoo過濾器(

9、MLCF)核心想法: 基于cuckoo filter Fan14將fingerprint和層次信息存儲(chǔ)在Cuckoo哈希表中Fingerprint(x):對(duì)于 = 0.1%, fingerprint大小213 bits, 小于布隆過濾器L0L1L2f(x1), 2f(x3), 1f(x2), 1Cuckoo hashing tablex2,x3x1SSTablesx417 December 16減少M(fèi)LCF中的假陽性率L18 December 160L1L2f(x1), 2f(x3), 1f(x2), 1Cuckoo hashing tablex4x2,x3x1用額外的二級(jí)表存儲(chǔ)這些沖突二級(jí)表

10、保存完整的key和層次信息當(dāng)插入(個(gè)新的key如果其fingerprint存在, 則將其存入二級(jí)表此方法只使用插入時(shí)需檢查重復(fù)性的操作SSTablesx4, 0Secondary hashing tableAssume f(x1) = f(x4)SSTable中的塊索引查找011101010000原始SSTable查詢過程:首先查找塊索引, 然后讀取相應(yīng)文件塊對(duì)塊索引進(jìn)行緩存來減少磁盤讀取塊索引越小越容易緩存01N-1Block index索引00011101101100110110000119 December 16高壓縮的塊索引20 December 16基于Entropy-Coded T

11、ries Lim12:對(duì)于純哈希的字段keys每個(gè)KV對(duì)只需要2.5 bit來映射其所在位置SlimFS的key由兩個(gè)哈希后的字段組成利用ECT 分別壓縮兩個(gè)字段只存儲(chǔ)其相應(yīng)的塊所在位置空間損耗降低到每個(gè)KV對(duì)只需要0.7bit比LevelDB的每個(gè)KV需要1 byte要小很多案例背景SlimFS:元數(shù)據(jù)本地存儲(chǔ)引擎問題分析高效的內(nèi)存索引有效減少寫放大實(shí)驗(yàn)結(jié)果In()xFS: 分布式元數(shù)據(jù)存儲(chǔ)服務(wù)案例總結(jié)21Stepped-Merge算法減少compaction整理操作來降低寫放大每層里面有多個(gè)自層Compaction整理操作合并多個(gè)子層到下(層減少了r倍寫 December 1622Leve

12、l 0Level 1Level 2.Compaction整理橾作.r sub-levelsLookup又橾作列模式的元數(shù)據(jù)表單Log file #1Log file #2Log file #n(, ptr)(, ptr)基于列的存儲(chǔ)模式CColumn Store）:記錄中的值部分直接存儲(chǔ)到非SSTable的日志文件中KV數(shù)據(jù)庫中只保存指向數(shù)據(jù)的指針Compaction整理操作,會(huì)整理數(shù)據(jù)延遲對(duì)刪除的元數(shù)據(jù)的整理只整理指KV StoreNo compaction23案例背景SlimFS:元數(shù)據(jù)本地存儲(chǔ)引擎現(xiàn)有解決方案和問題分析高效的內(nèi)存索引有效減少寫放大實(shí)驗(yàn)結(jié)果In()xFS: 分布式元數(shù)據(jù)存儲(chǔ)

13、服務(wù)案例總結(jié)24SlimFS 與現(xiàn)有方案的比較工作負(fù)載：隨機(jī)建立和訪問4億空文件比使用LevelDB的解決方案寫快4倍，讀快3.5倍優(yōu)化方法：高效內(nèi)存索引和減少寫放大40.0715.8611.1214.76051015202530354045Averae throuhput (KOP/s)File CreationsSlimFSRocksDBLevelDBHyperLevelDB1828140054058004008001200160020002400File StatsSlimFSRocksDBLevelDBHyperLevelDB25 December 16建立文件吞吐華26 Decemb

14、er 16讀取延遲27 December 16案例背景SlimFS:元數(shù)據(jù)本地存儲(chǔ)引擎In()xFS: 分布式元數(shù)據(jù)存儲(chǔ)服務(wù)元數(shù)據(jù)存儲(chǔ)服務(wù)架構(gòu)命名空間的劃分熱點(diǎn)減輕實(shí)驗(yàn)結(jié)果案例總結(jié)28IndexFS的系統(tǒng)設(shè)計(jì)框架使用其他分布式系(Lustre /HDFS) 作象存DataDataserverDataserverDataserverseDrvaetraDataDataDataseDrvaetarserverseDrvaetarserverseDrvaetarserverseDrvaetarserverMetadata ServerIndexFSclientAppsIndexFSclientApp

15、sIndexFS客戶端庫應(yīng)用元數(shù)據(jù)路徑(stat, open)數(shù)據(jù)路徑(read, write)IndexFSmetadata serverIndexFSmetadataIndexFS元數(shù)據(jù)服務(wù)器server數(shù)據(jù)路徑SlimFS29IndexFS 建立在已有的分布式文件系統(tǒng)上利用已有分布式文件系統(tǒng)作2對(duì)象存儲(chǔ)從而提供額外的小文件和元數(shù)據(jù)的管理文件系統(tǒng)樹分布策略1)book 5homebobalice 214carol/對(duì)文件系統(tǒng)樹進(jìn)行功能的劃分目錄元數(shù)據(jù)管理服務(wù)：所有目錄信息存在(個(gè)單機(jī)上，易于實(shí)現(xiàn)文件元數(shù)據(jù)和文件塊管理服務(wù)：分布式存儲(chǔ)在多臺(tái)機(jī)器上/ 0目管理服器3comic 6song文件管

16、理服器文件管理服器30文件系統(tǒng)樹分布策略2)當(dāng)目錄服務(wù)器需要進(jìn)行分布式存儲(chǔ)的時(shí)候在建立目錄時(shí)利用哈希算法的將其分配到(個(gè)服務(wù)器上讓目錄存儲(chǔ)能夠負(fù)載均衡homebob/ 03alice 214carol/034目管理服器031目管理服器11目管理服器22目管理服器3動(dòng)態(tài)劃分大目錄使用GIGA+ 算法進(jìn)行對(duì)目錄增華劃分 PaNl11當(dāng)目錄的文件數(shù)目增大，進(jìn)行二元?jiǎng)澐?，直至每個(gè)服務(wù)器都存有目錄 的(部分動(dòng)態(tài)負(fù)載均衡大目錄Binary split a large directoryServer1/big1/.P0/_b1_b4_b650%filesServer2/big1/.P1/_b2_b3_b55

17、0%files32解決服務(wù)器熱點(diǎn)問題所有查詢操作從根目錄開始路徑查詢需要訪問每個(gè)祖先目錄很容易造成某些服務(wù)器成2熱點(diǎn)解決方案：對(duì)很少變化的目錄信息進(jìn)行帶租約的緩存homebob/ 03alice 21carol4/04點(diǎn)目管理服器0目管理服器131目管理服器22目管理服器 333案例背景SlimFS:元數(shù)據(jù)本地存儲(chǔ)引擎In()xFS: 分布式元數(shù)據(jù)存儲(chǔ)服務(wù)元數(shù)據(jù)存儲(chǔ)服務(wù)架構(gòu)命名空間的劃分熱點(diǎn)減輕實(shí)驗(yàn)結(jié)果案例總結(jié)可擴(kuò)展性實(shí)驗(yàn): 空文件創(chuàng)建工作負(fù)載: 在(個(gè)目錄中創(chuàng)建大華文件使用PRObE Kodiak的128節(jié)點(diǎn)集群 (8-yr old LANL hardware)400200060080010

18、008128Aggregate file create throughput(K creates/sec)163264Cluster size (Number of servers)LinearIndexFS-PVFSPVFS-R35AM Disk比單節(jié)點(diǎn)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性能評(píng)測實(shí)驗(yàn)IndexFS 跑在有128個(gè)節(jié)點(diǎn)的PVFS集群所有元數(shù)據(jù)和文件通過SlimFS打包存儲(chǔ)在PVFS上工作負(fù)載:重播Linkedin的Trace：1 million ops per server預(yù)先建立好目錄，實(shí)驗(yàn)時(shí)只創(chuàng)建文件Trace中包含10M對(duì)象和130M操作操作分布: 90% reads, 10% mutation

20、s0.20.10Faction of TotalOperationsOpenReaddirMknodRenameFMkdirChmodRemove37實(shí)驗(yàn)結(jié)果: 吞吐華文件夾信息緩存減輕了減輕了熱點(diǎn)，消除了瓶頸10100100081664128吞吐華 (K ops/sec)32服務(wù)器個(gè)數(shù)IndexFS+Rate (r/(r+w) sec)PVFS+RAM DiskIndexFS+NoCache1.5x4x10 x案例技術(shù)總結(jié)SlimFS: 利用文件系統(tǒng)語義優(yōu)化元數(shù)據(jù)本地存儲(chǔ)使用高效的內(nèi)存索引加快讀取速度利用列存儲(chǔ)和Step-Merge算法減小寫放大IndexFS: 基于目錄對(duì)

21、文件命名空間進(jìn)行劃分先按照功能對(duì)文件系統(tǒng)樹進(jìn)行劃分隨機(jī)劃分目錄對(duì)小目錄進(jìn)行負(fù)載均衡使用可變租約對(duì)目錄信息進(jìn)行只讀緩存，消除熱點(diǎn)參考文獻(xiàn)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