Computer Science ›› 2017, Vol. 44 ›› Issue (6): 36-42.doi: 10.11896/j.issn.1002-137X.2017.06.006

Previous Articles     Next Articles

Optimizing Small XOR-based Non-systematic Erasure Codes

JIN Xing-tong, LI Peng, WANG Gang, LIU Xiao-guang and LI Zhong-wei   

  • Online:2018-11-13 Published:2018-11-13

Abstract: With the development of storage systems,the rapid rise of cloud storage has met the storing problem of highly increased data quantity.However,now the single cloud storage is facing the risks of data confidentiality,security,availability and vendor lock-in.To solve the above problems,we can construct the multi-cloud storage system with the private protecting ability through using privacy protecting code(PPC),which is an erasure code based on the XOR ope-ration.This paper mainly analyzed the optimization coding algorithm on the PPC to improve the performance of encoding operations.First,we designed an algorithm to search the optimal XOR scheduling sequence to reduce the XOR times in encoding.Because the encoding/decoding calculation of the PPC can be expressed as the multiplication of generator matrix (0/1 matrix) and data vectors,it can be observed visually that the computation is proportional to the number of 1 of the generator matrix.And based on the optimal scheduling order,we can get better performance.The searching result can be used to construct the multi-cloud storage system.Second,we can use the AVX2 technique of SIMD parallel optimization to improve the encoding performance based on the optimization schedule.Through the experiment,the performance of encoding based on the optimization schedule improves by 34.8%,and after being further optimized by SIMD technique,the performance improves 107.1%.

Key words: PPC,Encoding optimization,SIMD optimization,Data security,Erasure codes,Non-systematic codes

[1] ZHOU A Y.Data intensive computing-challenges of data mana-gement techniques[J].Communications of CCF,2009,5(7):50-53.
[2] Google Drive [EB/OL].[2016-07-09].https://en.wikipedia.org/wiki/Google_Drive.
[3] Dropbox (service) [EB/OL].[2016-07-09].https://en.wikipedia.org/wiki/Dropbox_(service).
[4] Amazon Simple Storage Service(S3) [EB/0L].[2016-07-09].https://aws.amazon.com/ s3.
[5] Microsoft Azure[EB/OL].[2016-07-09].https://en.wikipe-dia.org/wiki/Microsoft_Azure.
[6] A survey called “Data Breach Investigations Report” in 2015 by Verizon[EB/OL].[2016-07-09].http://www.freebuf.com/news/64183.html.
[7] BESSANI A,CORREIA M,QUARESMA B,et al.DepSky:dependable and secure storage in a cloud-of-clouds[J].ACM Transactions on Storage (TOS),2013,9(4):12.
[8] ABU-LIBDEH H,PRINCEHOUSE L,WEATHERSPOON H.RACS:a case for cloud storage diversity[C]∥Proceedings of the 1st ACM Symposium on Cloud Computing.ACM,2010:229-240.
[9] BOWERS K D,JUELS A,OPREA A.HAIL:a high-availability and integrity layer for cloud storage[C]∥Proceedings of the 16th ACM Conference on Computer and Communications Secu-rity.ACM,2009:187-198.
[10] SHEN L,FENG S,SUN J,et al.CloudS:A Multi-cloud Storage System with Multi-level Security[C]∥International Conference on Algorithms and Architectures for Parallel Processing.Sprin-ger International Publishing,2015:703-716.
[11] MENON J,BRUCK J,BRADY J,et al.EVENODD:An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures[J].IEEE Transactions on Computers,1995,4(2):192-202.
[12] CORBETT P,ENGLISH B,GOEL A,et al.Row-diagonal parity for double disk failure correction[C]∥Proceedings of the 3rd USENIX Symposium on File and Storage Technologies (FAST’04).2004:1-14.
[13] XU L,BRUCK J.X-Code:MDS Array Codes with Optimal Encoding[J].IEEE Transactions on Information Theory,1999,45(1):272-276.
[14] CHAO J,HONG J,DAN F,et al.P-Code:A new RAID-6 code with optimal properties[C]∥23rd International Conference on Supercomputing.New York,June 2009.
[15] HUANG C,XU L.STAR:An Efficient Coding Scheme for Correcting Triple Storage Node Failures[J].IEEE Transactions on Computers,2007,7(7):889-901.
[16] LIN S,WANG G,STONES D S,et al.T-Code:3-Erasure Longest Lowest-Density MDS Codes[J].IEEE Journal on Selected Areas in Communications,2010,8(2):289-296.
[17] AUTHORS U.WEAVER codes:highly fault tolerant erasurecodes for storage systems[C]∥ Fast 05 Conference on File & Storage Technologies,2005:16.
[18] PLANK J S,SCHUMAN C D,ROBISON B D.Heuristics foroptimizing matrix-based erasure codes for fault-tolerant storage systems[J].IEEE/IFIP International Conference on Dependable Systems & Networks Annual,2012,2(12):1-12.
[19] SIMD[EB/OL].[2016-07-09].https://en.wikipedia.org/w/in-dex.php?title=SIMD&oldid=726575429.
[20] PLANK J S.A tutorial on Reed-Solomon coding for fault-tole-rance in RAID-like systems[J].Softw.,Pract.Exper.,1997,7(9):995-1012.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!