A Bloom Filter Based Scalable Data Integrity Check Tool for Large-Scale Dataset
Authors:
- Sisi XiongSXSisi Xiong
- Feiyi WangFWFeiyi Wang
- Qing CaoQCQing Cao
- 1 November 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 55-60
Abstract
Large scale HPC applications are becoming increasingly data intensive. At Oak Ridge Leadership Computing Facility (OLCF), we are observing the number of files curated under individual project are reaching as high as 200 millions and project data size is exceeding petabytes. These simulation datasets, once validated, often needs to be transferred to archival system for long term storage or shared with the rest of the research community. Ensuring the data integrity of the full dataset at this scale is paramount important but also a daunting task. This is especially true considering that most conventional tools are serial and file-based, unwieldy to use and/or can't scale to meet user's demand.To tackle this particular challenge, this paper presents the design, implementation and evaluation of a scalable parallel checksumming tool, fsum, which we developed at OLCF. It is built upon the principle of parallel tree walk and work-stealing pattern to maximize parallelism and is capable of generating a single, consistent signature for the entire dataset at extreme scale. We also applied a novel bloom-filter based technique in aggregating signatures to overcome the signature ordering requirement. Given the probabilistic nature of bloom filter, we provided a detailed error and trade-off analysis. Using multiple datasets from production environment, we demonstrated that our tool can efficiently handle both very large files as well as many small-file based datasets. Our preliminary test showed that on the same hardware, it outperforms conventional tool by as much as 4×. It also exhibited near-linear scaling properties when provisioned with more compute resources.Keywords
This publication has 9 references indexed in Scilit:
- Best Practices and Lessons Learned from Deploying and Operating Large-Scale Data-Centric Parallel File Systems2014
- Big data: A review2013
- On distributed file tree walk of parallel file systems2012
- An Efficient Parallel Algorithm for Skein Hash Functions2010
- Uncovering errors2009
- Load balancing using work-stealing for pipeline parallelism in emerging applications2009
- Ensuring data integrity in storage2005
- A Parallel Algorithm for Extending Cryptographic Hash FunctionsLecture Notes in Computer Science, 2001
- Protocols for Public Key Cryptosystems1980