More Web Proxy on the site http://driver.im/

research-article

Approximate Code: A Cost-Effective Erasure Coding Framework for Tiered Video Storage in Cloud Systems

Authors:

Jianfeng ZhangAuthors Info & Claims

ICPP '19: Proceedings of the 48th International Conference on Parallel Processing

Article No.: 95, Pages 1 - 10

https://doi.org/10.1145/3337821.3337869

Published: 05 August 2019 Publication History

Abstract

Nowadays massive video data are stored in cloud storage systems, which are generated by various applications such as autonomous driving, news media, security monitoring, etc. Meanwhile, erasure coding is a popular technique in cloud storage to provide both high reliability and low monetary cost, where triple disk failure tolerant arrays (3DFTs) is a typical choice. Therefore, how to minimize the storage cost of video data in 3DFTs is a challenge for cloud storage systems. Although there are several solutions like approximate storage technique, they cannot guarantee low storage cost and high data reliability concurrently.

To address this challenge, in this paper, we propose Approximate Code, which is an erasure coding framework for tiered video storage in cloud systems. The key idea of Approximate Code is distinguishing the important and unimportant data with different capabilities of fault tolerance. On one hand, for important data, Approximate Code provides triple parities to ensure high reliability. On the other hand, single/double parities are applied for unimportant data, which can save the storage cost and accelerate the recovery process. To demonstrate the effectiveness of Approximate Code, we conduct several experiments in Hadoop systems. The results show that, compared to traditional 3DFTs using various erasure codes such as RS, LRC, STAR and TIP-Code, Approximate Code reduces the number of parities by up to 55%, saves the storage cost by up to 20.8% and increase the recovery speed by up to 4.7X when double nodes fail.

References

[1]

Sami Abu-El-Haija, Nisarg Kothari, Joonseok Lee, Paul Natsev, George Toderici, Balakrishnan Varadarajan, and Sudheendra Vijayanarasimhan. 2016. Youtube-8m: A large-scale video classification benchmark. arXiv preprint arXiv:1609.08675 (2016).

[2]

Ignacio Bermudez, Stefano Traverso, Marco Mellia, and Maurizio Munafo. 2013. Exploring the cloud from passive measurements: The Amazon AWS case. In 2013 Proceedings IEEE INFOCOM. IEEE, 230--234.

[3]

Mario Blaum, Jim Brady, Jehoshua Bruck, and Jai Menon. 1995. EVENODD: An efficient scheme for tolerating double disk failures in RAID architectures. IEEE Transactions on computers 44, 2 (1995), 192--202.

Digital Library

[4]

Mario Blaum and Ron Roth. 1999. On Lowest Density MDS Codes. IEEE Transactions on Information Theory 45, 1 (1999), 46--59.

Digital Library

[5]

Johannes Bloemer, Malik Kalfane, Richard Karp, Marek Karpinski, Michael Luby, and David Zuckerman. 1995. An XOR-based Erasure-Resilient coding scheme. Technical Report TR-95-048. International Computer Science Institute.

[6]

Brad Calder, Ju Wang, Aaron Ogus, Niranjan Nilakantan, Arild Skjolsvold, Sam McKelvie, Yikang Xu, Shashwat Srivastav, Jiesheng Wu, Huseyin Simitci, et al. 2011. Windows Azure Storage: a highly available cloud storage service with strong consistency. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles. ACM, 143--157.

Digital Library

[7]

Yuval Cassuto and Jehoshua Bruck. 2009. Cyclic Lowest Density MDS Array Codes. IEEE Transactions on Information Theory 55, 4 (2009), 1721--1729.

Digital Library

[8]

Peter Corbett, Bob English, Atul Goel, Tomislav Grcanac, Steven Kleiman, James Leong, and Sunitha Sankar. 2004. Row-Diagonal Parity for Double Disk Failure Correction. In Proc. of the USENIX FAST'04. San Francisco, CA.

Digital Library

[9]

Peter Corbett and Atul Goel. 2011. Triple parity technique for enabling efficient recovery from triple failures in a storage array. US Patent 8,015,472.

[10]

Peter Deutsch. 1996. DEFLATE compressed data format specification version 1.3. Technical Report.

[11]

Gui Liang Feng, Robert Deng, Feng Bao, and J C Shen. 2005. New efficient MDS array codes for RAID Part I: Reed-Solomon-like codes for tolerating three disk failures. IEEE Trans. Comput. 54, 9 (2005), 1071--1080.

Digital Library

[12]

Junqing Gu, Chentao Wu, Xin Xie, Han Qiu, Jie Li, Minyi Guo, Xubin He, Yuanyuan Dong, and Yafei Zhao. 2019. Optimizing the Parity-Check Matrix for Efficient Decoding of RS-based Cloud Storage Systems. In The 32nd IEEE International Parallel & Distributed Processing Symposium (IPDPS 2019). IEEE.

[13]

Junqing Gu, Xin Xie, Han Qiu, Jie Li, Minyi Guo, and Xubin He. 2019. Optimizing the Parity-Check Matrix for Efficient Decoding of RS-based Cloud Storage Systems. In The 35th International Conference on Massive Storage Systems and Technology (MSST 2019). IEEE.

[14]

Qing Guo, Karin Strauss, Luis Ceze, and Henrique S Malvar. 2016. High-density image storage using approximate memory cells. In ACM SIGPLAN Notices, Vol. 51. ACM, 413--426.

Digital Library

[15]

James Hafner. 2005. WEAVER Codes: Highly Fault Tolerant Erasure Codes for Storage Systems. In Proceedings of the 4th USENIX Conference on File and Storage Technologies, Vol. 5. 16--16.

Digital Library

[16]

James Hafner. 2006. HoVer Erasure Codes For Disk Arrays. In Proceedings of the 5th USENIX Conference on File and Storage Technologies. 217--226.

Digital Library

[17]

Cheng Huang, Minghua Chen, and Jin Li. 2007. Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems. In Network Computing and Applications, 2007 NCA'07. Sixth IEEE International Symposium on. IEEE, 79--86.

[18]

Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin. 2012. Erasure coding in windows azure storage. In the 2012 USENIX Annual Technical Conference (USENIX ATC 12). 15--26.

Digital Library

[19]

Cheng Huang and Lihao Xu. 2008. STAR: An efficient coding scheme for correcting triple storage node failures. IEEE Trans. Comput. 57, 7 (2008), 889--901.

Digital Library

[20]

Djordje Jevdjic, Karin Strauss, Luis Ceze, and Henrique S Malvar. 2017. Approximate storage of compressed and encrypted videos. In ACM SIGARCH Computer Architecture News, Vol. 45. ACM, 361--373.

Digital Library

[21]

Yanbing Jiang, Chentao Wu, Jie Li, and Minyi Guo. 2016. BDR: A Balanced Data Redistribution scheme to accelerate the scaling process of XOR-based Triple Disk Failure Tolerant arrays. In 2016 IEEE 34th International Conference on Computer Design (ICCD). IEEE, 72--79.

[22]

Chao Jin, Hong Jiang, Dan Feng, and Lei Tian. 2009. P-Code: A new RAID-6 code with optimal properties. In Proc. of the ICS'09. Yorktown Heights, NY.

Digital Library

[23]

KR Krish, Ali Anwar, and Ali R Butt. 2014. hats: A heterogeneity-aware tiered storage for hadoop. In 2014 14th IEEE/ACM International Symposium on Cluster Cloud and Grid Computing. IEEE, 502--511.

Digital Library

[24]

Jai Menon. 1995. A performance comparison of RAID-5 and log-structured arrays. In Proceedings of the Fourth IEEE International Symposium on High Performance Distributed Computing. IEEE, 167--178.

Digital Library

[25]

Simone Meyer, Oliver Wang, Henning Zimmer, Max Grosse, and Alexander Sorkine-Hornung. 2015. Phase-based frame interpolation for video. In Proceedings of the IEEE conference on computer vision and pattern recognition. 1410--1418.

[26]

Simon Niklaus and Feng Liu. 2018. Context-aware synthesis for video frame interpolation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 1701--1710.

[27]

D. Patterson et al. 2008. A Case for Redundant Arrays of Inexpensive Disks (RAID). In Proc. of the SIGMOD'88.

Digital Library

[28]

J. Plank. 2008. A new minimum density RAID-6 code with a word size of eight. In Proc. of the IEEE NCA'08. Cambridge, MA.

Digital Library

[29]

J. Plank. 2008. The RAID-6 Liberation Codes. In Proc. of the USENIX FAST'08. San Jose, CA.

Digital Library

[30]

Irving S Reed and Gustave Solomon. 1960. Polynomial codes over certain finite fields. Journal of the society for industrial and applied mathematics 8, 2 (1960), 300--304.

[31]

Adrian Sampson, Jacob Nelson, Karin Strauss, and Luis Ceze. 2014. Approximate storage in solid-state memories. ACM Transactions on Computer Systems (TOCS) 32, 3 (2014), 9.

Digital Library

[32]

Maheswaran Sathiamoorthy, Megasthenis Asteris, Dimitris Papailiopoulos, Alexandros Dimakis, Ramkumar Vadali, Scott Chen, and Dhruba Borthakur. 2013. XORing elephants: Novel erasure codes for big data. In Proceedings of the VLDB Endowment, Vol. 6. VLDB Endowment, 325--336.

Digital Library

[33]

Zhirong Shen and Jiwu Shu. 2014. HV Code: An All-Around MDS Code to Improve Efficiency and Reliability of RAID-6 Systems. In Proc. of the IEEE/IFIP DSN'14. Atlanta, GA.

Digital Library

[34]

Dan Tang, Xiaojing Wang, Sheng Cao, and Zheng Chen. 2008. A New Class of Highly Fault Tolerant Erasure Code for the Disk Array. In Workshop on Power Electronics and Intelligent Transportation System, PEITS'08. IEEE, 578--581.

Digital Library

[35]

C. Tau and T. Wang. 2003. Efficient parity placement schemes for tolerating triple disk failures in RAID architectures. In Proc. of the AINA'03. Xi'an, China.

Digital Library

[36]

Aniruddha N Udipi, Naveen Muralimanohar, Rajeev Balsubramonian, Al Davis, and Norman P Jouppi. 2012. LOT-ECC: localized and tiered reliability mechanisms for commodity memory systems. In ACM SIGARCH Computer Architecture News, Vol. 40. IEEE Computer Society, 285--296.

Digital Library

[37]

Joost van Amersfoort, Wenzhe Shi, Alejandro Acosta, Francisco Massa, Johannes Totz, Zehan Wang, and Jose Caballero. 2017. Frame interpolation with multi-scale deep loss functions and generative adversarial networks. arXiv preprint arXiv:1711.06045 (2017).

[38]

Hui Wang and Peter Varman. 2014. Balancing Fairness and Efficiency in Tiered Storage Systems with Bottleneck-Aware Allocation. In Proceedings of the 12th USENIX Conference on File and Storage Technologies (FAST 14). 229--242.

Digital Library

[39]

Y. Wang, G. Li, and X. Zhong. 2012. Triple-Star: A Coding Scheme with Optimal Encoding Complexity for Tolerating Triple Disk Failures in RAID. International Journal of Innovative Computing, Information and Control 8, 3 (2012), 1731--1472.

[40]

Thomas Wiegand, Gary J Sullivan, Gisle Bjontegaard, and Ajay Luthra. 2003. Overview of the H. 264/AVC video coding standard. IEEE Transactions on circuits and systems for video technology 13, 7 (2003), 560--576.

Digital Library

[41]

Chentao Wu, Xubin He, Jizhong Han, Huailiang Tan, and Changsheng Xie. 2012. SDM: A stripe-based data migration scheme to improve the scalability of RAID-6. In 2012 IEEE International Conference on Cluster Computing. IEEE, 284--292.

Digital Library

[42]

Chentao Wu, Shenggang Wan, Xubin He, Qiang Cao, and Changsheng Xie. 2011. H-Code: A hybrid MDS array code to optimize partial stripe writes in RAID-6. 782--793.

Digital Library

[43]

Xin Xie, Chentao Wu, Junqing Gu, Han Qiu, Jie Li, Minyi Guo, Xuebin He, Yuanyuan Dong, and Yafei Zhao. 2019. AZ-Code: An Efficient Availability Zone Level Erasure Code to Provide High Fault Tolerance in Cloud Storage Systems. In The 35th International Conference on Massive Storage Systems and Technology (MSST 2019). IEEE.

[44]

Lihao Xu and Jehoshua Bruck. 1999. X-Code: MDS Array Codes with Optimal Encoding. IEEE Transactions on Information Theory 45, 1 (1999), 272--276.

Digital Library

[45]

Gong Zhang, Lawrence Chiu, Clem Dickey, Ling Liu, Paul Muench, and Sangeetha Seshadri. 2010. Automated lookahead data migration in SSD-enabled multi-tiered storage systems. In 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST). IEEE, 1--6.

Digital Library

[46]

Yongzhe Zhang, Chentao Wu, Jie Li, and Minyi Guo. 2015. PCM: A Parity-check Matrix Based Approach to Improve Decoding Performance of XOR-based Erasure Codes. In The 34th International Symposium on Reliable Distributed Systems (SRDS 2015). IEEE.

Digital Library

[47]

Yongzhe Zhang, Chentao Wu, Jie Li, and Minyi Guo. 2015. Tip-code: A three independent parity code to tolerate triple disk failures with optimal update complextiy. In 2015 45th Annual IEEE/IFIP International Conference on Dependable Systems and Networks. IEEE, 136--147.

Digital Library

[48]

Hengyu Zhao, Linuo Xue, Ping Chi, and Jishen Zhao. 2017. Approximate image storage with multi-level cell STT-MRAM main memory. In 2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). IEEE, 268--275.

Digital Library

[49]

Jacob Ziv and Abraham Lempel. 1977. A universal algorithm for sequential data compression. IEEE Transactions on information theory 23, 3 (1977), 337--343.

Digital Library

[50]

Jacob Ziv and Abraham Lempel. 1978. Compression of individual sequences via variable-rate coding. IEEE transactions on Information Theory 24, 5 (1978), 530--536.

Digital Library

Cited By

Khan AMatskin MProdan RBussler CRoman DSoylu A(2024)Cloud storage cost: a taxonomy and surveyWorld Wide Web10.1007/s11280-024-01273-427:4Online publication date: 24-May-2024
https://dl.acm.org/doi/10.1007/s11280-024-01273-4
Khan ANikolov NMatskin MProdan RBussler CRoman DSoylu A(2024)A Taxonomy for Cloud Storage CostManagement of Digital EcoSystems10.1007/978-3-031-51643-6_23(317-330)Online publication date: 2-Feb-2024
https://doi.org/10.1007/978-3-031-51643-6_23
Liu MPan LLiu S(2023)Cost Optimization for Cloud Storage from User Perspectives: Recent Advances, Taxonomy, and SurveyACM Computing Surveys10.1145/358288355:13s(1-37)Online publication date: 13-Jul-2023
https://dl.acm.org/doi/10.1145/3582883
Show More Cited By

Index Terms

Approximate Code: A Cost-Effective Erasure Coding Framework for Tiered Video Storage in Cloud Systems
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks
2. Information systems
  1. Information storage systems
    1. Storage architectures
      1. Distributed storage

Recommendations

RACS: a case for cloud storage diversity
SoCC '10: Proceedings of the 1st ACM symposium on Cloud computing

The increasing popularity of cloud storage is leading organizations to consider moving data out of their own data centers and into the cloud. However, success for cloud storage providers can present a significant risk to customers; namely, it becomes ...
Cost-Effective and Reliable Cloud Storage for Big Data
ASE BD&SI '15: Proceedings of the ASE BigData & SocialInformatics 2015

Efficiency and reliability are critical to the performance of big data computing. Hadoop is one of the most popular cloud platforms to support big data analysis. To improve data availability, the Hadoop distributed file system usually stores blocks of ...
Thou code: a triple-erasure-correcting horizontal code with optimal update complexity
Abstract
Taking advantage of consuming low storage resource, erasure codes have been widely adopted by various storage systems, e.g., HDFS, Ceph, and Microsoft Azure, to provide reliability. With the rapid expansion of data storage, it becomes increasingly ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICPP '19: Proceedings of the 48th International Conference on Parallel Processing

August 2019

1107 pages

ISBN:9781450362955

DOI:10.1145/3337821

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

University of Tsukuba: University of Tsukuba

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 August 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

ICPP 2019

ICPP 2019: 48th International Conference on Parallel Processing

August 5 - 8, 2019

Kyoto, Japan

Acceptance Rates

Overall Acceptance Rate 91 of 313 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
220
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Khan AMatskin MProdan RBussler CRoman DSoylu A(2024)Cloud storage cost: a taxonomy and surveyWorld Wide Web10.1007/s11280-024-01273-427:4Online publication date: 24-May-2024
https://dl.acm.org/doi/10.1007/s11280-024-01273-4
Khan ANikolov NMatskin MProdan RBussler CRoman DSoylu A(2024)A Taxonomy for Cloud Storage CostManagement of Digital EcoSystems10.1007/978-3-031-51643-6_23(317-330)Online publication date: 2-Feb-2024
https://doi.org/10.1007/978-3-031-51643-6_23
Liu MPan LLiu S(2023)Cost Optimization for Cloud Storage from User Perspectives: Recent Advances, Taxonomy, and SurveyACM Computing Surveys10.1145/358288355:13s(1-37)Online publication date: 13-Jul-2023
https://dl.acm.org/doi/10.1145/3582883
Chen JLi ZFang GHou YLi X(2023)A comprehensive repair scheme for distributed storage systemsComputer Networks10.1016/j.comnet.2023.109954235(109954)Online publication date: Nov-2023
https://doi.org/10.1016/j.comnet.2023.109954
Zhou AZhou NYi BZhu C(2023)A cost-efficient hybrid redundancy coding scheme for wireless storage systemsComputer Communications10.1016/j.comcom.2023.03.012203(226-237)Online publication date: Apr-2023
https://doi.org/10.1016/j.comcom.2023.03.012
Hu PGu YJia RWu CGuo MLi J(2022)PRM: An Efficient Partial Recovery Method to Accelerate Training Data Reconstruction for Distributed Deep Learning Applications in Cloud Storage Systems2022 IEEE/ACM 30th International Symposium on Quality of Service (IWQoS)10.1109/IWQoS54832.2022.9812919(1-10)Online publication date: 10-Jun-2022
https://doi.org/10.1109/IWQoS54832.2022.9812919
Darwich MIsmail YDarwich TBayoumi M(2022)Cost Minimization of Cloud Services for On-Demand Video StreamingSN Computer Science10.1007/s42979-022-01140-x3:3Online publication date: 19-Apr-2022
https://doi.org/10.1007/s42979-022-01140-x
Shen ZLin SShu JXie CHuang ZFu Y(2021)Cluster-Aware Scattered Repair in Erasure-Coded Storage: Design and AnalysisIEEE Transactions on Computers10.1109/TC.2020.302835370:11(1861-1874)Online publication date: 1-Nov-2021
https://doi.org/10.1109/TC.2020.3028353
Wang FGu SZhang QZhang NXiang W(2021)Cost Optimal Regenerating Codes Design for Satellite Clustered Distributed Storage System2021 IEEE/CIC International Conference on Communications in China (ICCC)10.1109/ICCC52777.2021.9580435(995-1000)Online publication date: 28-Jul-2021
https://doi.org/10.1109/ICCC52777.2021.9580435
Gu SWang FZhang QHuang TXiang W(2021)Global repair bandwidth cost optimization of generalized regenerating codes in clustered distributed storage systemsIET Communications10.1049/cmu2.1228915:19(2469-2481)Online publication date: 4-Oct-2021
https://doi.org/10.1049/cmu2.12289
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten