(3.237.178.91) 您好!臺灣時間:2021/03/07 14:42
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林志庭
研究生(外文):Chih-Ting Lin
論文名稱:階層式布隆過濾器之敏感性分析
論文名稱(外文):Sensitivity Analysis of Hierarchical Bloom Filter Arrays
指導教授:劉邦鋒
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊網路與多媒體研究所
學門:電算機學門
學類:網路學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:英文
論文頁數:22
中文關鍵詞:元數據管理布隆過濾器分散式檔案系統效能分析選擇準則
外文關鍵詞:Metadata managamentBloom filterdistributed file systemsperformance analysisselection criteria
相關次數:
  • 被引用被引用:0
  • 點閱點閱:143
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
我們針對了兩個十分有效率的元數據管理方法提出了一種選擇準則,這兩種元數據管理方法分別為單純式布隆過濾器與階層式布隆過濾器。我們提出的選擇準則可以幫助我們知道對於不同種類的檔案存取形式,哪一種元數據管理方法可以有較好的效能表現。我們提出的選擇準則除了分析兩種方法個別的理論效能表現,並且將我們分析的理論效能表現與實際的檔案系統效能做比較。我們利用模擬的方式測量真實檔案系統效能,由其所測量的結果顯示,我們對於兩種元數據管理方法的理論效能分析,都與真實的分散式系統效能十分相近。


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.

Certification i
Acknowledgement ii
Chinese Abstract iii
Abstract iv
1 Introduction 1
1.1 Distributed File System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Metadata Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Bloom Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Related Works 5
2.1 No Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Subtree Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Static Subtree Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.2 Dynamic subtree partitioning . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 File Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3.1 Pure hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3.2 Bloom filter based approaches . . . . . . . . . . . . . . . . . . . . . . . 7
3 System Architecture 9
3.1 Pure Bloom filter arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Hierarchical Bloom filter arrays . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4 Sensitivity Analysis 11
4.1 False-positive Rate of Bloom Filter . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 Theoretical Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2.1 Theoretical hit rate of pure Bloom filter array method . . . . . . . . . . . 12
4.2.2 Theoretical hit rate of hierarchical Bloom filter array method . . . . . . . 14
4.3 Performance Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.4 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.4.1 Pure Bloom Filter Array Simulator . . . . . . . . . . . . . . . . . . . . 16
4.4.2 Hierarchical Bloom Filter Array Simulator . . . . . . . . . . . . . . . . 17
5 Conclusions and FutureWork 19
Bibliography 20

[1] R. Wolski, N. Spring, and C. Peterson. Implementing a performance forecasting system
for metacomputing: the network weather service. In Supercomputing ’97: Proceedings of
the 1997 ACM/IEEE conference on Supercomputing (CDROM), pages 1–19, New York, NY,
USA, 1997. ACM.
[2] R. Pajarola. Cluster parallel rendering. In SIGGRAPH Asia ’08: ACM SIGGRAPH ASIA
2008 courses, pages 1–12, New York, NY, USA, 2008. ACM.
[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,
NY, USA, 2003. ACM.
[4] P. J. Braam. The lustre storage architecture, 2002.
[5] Blue gene/l. http://www.research.ibm.com/bluegene/.
[6] Nasa. http://www.nasa.gov/.
[7] D. Roselli, J. Lorch, and T. Anderson. A comparison of file system workloads. In ATEC ’00:
Proceedings of the annual conference on USENIX Annual Technical Conference, pages 4–4,
Berkeley, CA, USA, 2000. USENIX Association.
[8] B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communication
of ACM, 13(7):422–426, 1970.
[9] J. Wang. A survey of web caching schemes for the internet. SIGCOMM Comput. Commun.
Rev., 29(5):36–46, 1999.
[10] H. Song, S. Dharmapurikar, J. Turner, and J. Lockwood. Fast hash table lookup using extended
bloom filter: an aid to network processing. In SIGCOMM ’05: Proceedings of the
2005 conference on Applications, technologies, architectures, and protocols for computer
communications, pages 181–192, New York, NY, USA, 2005. ACM.
[11] M. Attig, S. Dharmapurikar, and J. Lockwood. Implementation results of bloom filters for
string matching. In FCCM ’04: Proceedings of the 12th Annual IEEE Symposium on Field-
Programmable Custom Computing Machines, pages 322–323, Washington, DC, USA, 2004.
IEEE Computer Society.
[12] Y. Zhu, H. Jiang, J. Wang, and F. Xian. Hba: Distributed metadata management for large
cluster-based storage systems. IEEE Trans. Parallel Distrib. Syst., 19(6):750–763, 2008.
[13] Y. Zhu, H. Jiang, and J.Wang. Hierarchical bloom filter arrays (hba): a novel, scalable metadata
management system for large cluster-based storage. In CLUSTER ’04: Proceedings of
the 2004 IEEE International Conference on Cluster Computing, pages 165–174, Washington,
DC, USA, 2004. IEEE Computer Society.
[14] M. K. McKusick, W. N. Joy, S. J. Leffler, and R. S. Fabry. A fast file system for unix. ACM
Trans. Comput. Syst., 2(3):181–197, 1984.
[15] M. Rosenblum and J. K. Ousterhout. The design and implementation of a log-structured file
system. ACM Trans. Comput. Syst., 10(1):26–52, 1992.
[16] P. H. Carns, III W. B. Ligon, R. B. Ross, and R. Thakur. Pvfs: a parallel file system for linux
clusters. In ALS’00: Proceedings of the 4th annual Linux Showcase & Conference, pages
28–28, Berkeley, CA, USA, 2000. USENIX Association.
[17] J. H. Morris, M. Satyanarayanan, M. H. Conner, J. H. Howard, D. S. Rosenthal, and F. D.
Smith. Andrew: a distributed personal computing environment. Commun. ACM, 29(3):184–
201, 1986.
[18] B. Pawlowski, C. Juszczak, P. Staubach, C. Smith, D. Lebel, and D. Hitz. Nfs version 3 -
design and implementation. In In Proceedings of the Summer USENIX Conference, pages
137–152, 1994.
[19] M. Satyanarayanan, J. J. Kistler, P. Kumar, M. E. Okasaki, E. H. Siegel, and D. C. Steere.
Coda: A highly available file system for a distributed workstation environment. IEEE Trans.
Comput., 39(4):447–459, 1990.
[20] B. Walker, Gerald R. English G. Popek, C. Kline, and G. Thiel. The locus distributed operating
system. In SOSP ’83: Proceedings of the ninth ACM symposium on Operating systems
principles, pages 49–70, New York, NY, USA, 1983. ACM.
[21] J. K. Ousterhout, A. R. Cherenson, F. Douglis, M. N. Nelson, and B. B. Welch. The sprite
network operating system. Computer, 21(2):23–36, 1988.
[22] S. A. Weil, K. T. Pollack, S. A. Brandt, and E. L. Miller. Dynamic metadata management
for petabyte-scale file systems. In SC ’04: Proceedings of the 2004 ACM/IEEE conference
on Supercomputing, page 4, Washington, DC, USA, 2004. IEEE Computer Society.
[23] P. F. Corbett and D. G. Feitelson. The vesta parallel file system. ACM Trans. Comput. Syst.,
14(3):225–264, 1996.
[24] P. Braam, M. Callahan, and P. Schwan. The intermezzo file system, 1999.
[25] E. L. Miller and R. H. Katz. Rama: an easy-to-use, high-performance parallel file system.
Parallel Comput., 23(4-5):419–446, 1997.
[26] O. Rodeh and A. Teperman. zfs ” a scalable distributed file system using object disks. InMSS
’03: Proceedings of the 20 th IEEE/11 th NASA Goddard Conference on Mass Storage Systems
and Technologies (MSS’03), page 207, Washington, DC, USA, 2003. IEEE Computer
Society.
[27] C. H. Staelin. High-performance file system design. PhD thesis, Princeton University, Princeton,
NJ, USA, 1992.
[28] V. Cate and T. Gross. Combining the concepts of compression and caching for a two-level
filesystem. In ASPLOS-IV: Proceedings of the fourth international conference on Architectural
support for programming languages and operating systems, pages 200–211, New York,
NY, USA, 1991. ACM.
[29] H. Tang and T. Yang. An efficient data location protocol for self.organizing storage clusters.
In SC ’03: Proceedings of the 2003 ACM/IEEE conference on Supercomputing, page 53,
Washington, DC, USA, 2003. IEEE Computer Society.
[30] R. Floyd. Short-term file reference patterns in a unix environment. Technical report, Computer
Science Dept., Univ. of Rochester, 1986.
[31] E. Riedel, M. Kallahalla, and R. Swaminathan. A framework for evaluating storage system
security. In FAST ’02: Proceedings of the 1st USENIX Conference on File and Storage
Technologies, page 2, Berkeley, CA, USA, 2002. USENIX Association.
[32] L. Fan, P. Cao, J. Almeida, and A. Z. Broder. Summary cache: a scalable wide-area web
cache sharing protocol. IEEE/ACM Trans. Netw., 8(3):281–293, 2000.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔