階層式布隆過濾器之敏感性分析

Sensitivity Analysis of Hierarchical Bloom Filter Arrays

林志庭(Chih-Ting Lin)

指導教授 ： 劉邦鋒

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.03548

摘要

我們針對了兩個十分有效率的元數據管理方法提出了一種選擇準則，這兩種元數據管理方法分別為單純式布隆過濾器與階層式布隆過濾器。我們提出的選擇準則可以幫助我們知道對於不同種類的檔案存取形式，哪一種元數據管理方法可以有較好的效能表現。我們提出的選擇準則除了分析兩種方法個別的理論效能表現，並且將我們分析的理論效能表現與實際的檔案系統效能做比較。我們利用模擬的方式測量真實檔案系統效能，由其所測量的結果顯示，我們對於兩種元數據管理方法的理論效能分析，都與真實的分散式系統效能十分相近。

關鍵字

元數據管理 ； 布隆過濾器 ； 分散式檔案系統 ； 效能分析 ； 選擇準則

並列摘要

We propose a selection criteria of two efficient distributed metadata management schemes, pure Bloom filter arrays and hierarchical Bloom filter arrays. The selection criteria helps us to know which metadata management scheme can have better performance for the different file access patterns. The selection criteria not only analyzes the theoretical performance for both metadata management schemes, but also compares the theoretical results with the real file system workload. The simulation results indicate that our theoretical analysis results are close to the real distributed system performance.

並列關鍵字

Metadata managament ； Bloom filter ； distributed file systems ； performance analysis ； selection criteria

參考文獻

[1] R. Wolski, N. Spring, and C. Peterson. Implementing a performance forecasting system

USA, 1997. ACM.

[2] R. Pajarola. Cluster parallel rendering. In SIGGRAPH Asia ’08: ACM SIGGRAPH ASIA

[3] S. Ghemawat, H. Gobioff, and S. Leung. The google file system. In SOSP ’03: Proceedings

of the nineteenth ACM symposium on Operating systems principles, pages 29–43, New York,