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