ANALYSIS AND ESTIMATION OF THE TRIE MINIMUM LEVEL IN NON-HASH DEDUPLICATION SYSTEM

Subject of research. The paper deals with a method of restriction for the trie minimum level in non-hash data deduplication system. Method. The subject matter of the method lies in forcibly completing the trie to a specific minimum level. The proposed method makes it possible to increase performance of the process by reducing the number of collisions at the lower levels ofthe trie. The maximum theoretical performance growth corresponds to the share of collisions in the total number of data read operations from the storage medium. Proposed method application increases the metadata size to the amount of new structures containing one element. Main results. The results of the work have been proved by the data of computational experiment with non-has deduplication on 528 GB data set. The process analysis has shown that 99% of the execution time is taken to head positioning of hard-drives. The reason is a random distribution of the blocks on the storage medium. Application of the method of minimum level restriction for the trie in non-hash data deduplication system on the experimental data set gives the possibility to increase performance maximum by 16% and the increase of metadata size is 49%. The total amount of metadata is 34% less than with hash-based deduplication using the MD5 algorithm, and is 17% less than using Tiger192 algorithm. These results confirm the effectiveness of the proposed method. Practical relevance. The proposed method increases the performance of deduplication process by reducing the number of collisions in the trie construction. The results are of practical importance for professionals involved in the development of non-hash data deduplication methods.

1. Shcherbinin A. Resheniya po deduplikatsii dannykh. Storage News, 2008, no. 2 (35), pp. 2–7.

2. Chernyak L. Prosto o slozhnostyakh deduplikatsii [Easy about difficulties of deduplication]. Otkrytye Sistemy. SUBD, 2013, no. 3, pp. 54–55.

3. Meyer D.T, Bolosky W.J. A study of practical deduplication. ACM Transactions on Storage, 2012, vol. 7, no. 4, art. 14. doi: 10.1145/2078861.2078864

4. Meister D. Advanced Data Deduplication Techniques and their Application, PhD dissertation. Mainz, Johannes Gutenberg University, 2013, 230 p.

5. Bhagwat D., Eshghi K., Long D.D.E., Lillibridge M. Extreme binning: scalable, parallel deduplication for chunk-based file backup. Proc. 17th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, MASCOTS. London, UK, 2009, pp. 237–245. doi: 10.1109/MASCOT.2009.5366623

6. Kazakov V.G., Fedosin S.A., Plotnikova N.P. Sposob adaptivnoi deduplikatsii s primeneniem mnogourovnevogo indeksa razmeshcheniya kopiruemykh blokov dannykh [Method of adaptive deduplication with multilevel block indexing]. Fundamental'nye Issledovaniya, 2013, no. 8–6, pp. 1322– 1325.

7. Maddodi S., Attigeri G.V., Karunakar A.K. Data deduplication techniques and analysis. Proc. 3rd Int. Conf. on Emerging Trends in Engineering and Technology, ICETET 2010. Goa, India, 2010, pp. 664–668. doi: 10.1109/ICETET.2010.42

8. Orlando K., Bautista M.M., Mejia J.R.M., Langnor R.G. IBM ProtecTIER Implementation and Best Practices Guide. IBM Redbooks, 2014, 578 p.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License