Michael Luby
Roberto Padovani
Skip Abstract Section
Abstract
A liquid system provides durable object storage based on spreading redundantly generated data across a network of hundreds to thousands of potentially unreliable storage nodes. A liquid system uses a combination of a large code, lazy repair, and flow storage organization. We show that a liquid system can be operated to enable flexible and essentially optimal combinations of storage durability, storage overhead, repair bandwidth usage, and access performance.
- Backblaze. 2016. Hard Drive Data and Stats. Retrieved October 8, 2018, from https://www.backblaze.com/b2/hard-drive-test-data.html.Google Scholar
- M. Belshe, R. Peon, and M. Thomson (Eds.). 2015. Hypertext Transfer Protocol Version 2 (HTTP/2), RFC 7540. Retrieved on May 2015 from https://www.rfc-editor.org/info/rfc7540.Google Scholar
- R. Bhagwan, K. Tati, Y.-C. Cheng, S. Savage, and G. M. Voelker. 2004. Total recall: System support for automated availability management. In Symposium on Networked Systems Design and Implementation, Vol. 1. Google ScholarDigital Library
- J. Bloemer, M. Kalfane, M. Karpinski, R. Karp, M. Luby, and D. Zuckerman. 1995. An XOR-based erasure-resilient coding scheme. ICSI Technical Report, Article TR-95-048.Google Scholar
- B. Calder, J. Wang, A. Ogus, N. Nilakantan, A. Skjolsvold, S. McKelvie, Y. Xu, S. Srivastav, J. Wu, H. Simitci, J. Haridas, C. Uddaraju, H. Khatri, A. Edwards, V. Bedekar, S. Mainali, R. Abbasi, A. Agarwal, M. Fahim ul Haq, M. Ikram ul Haq, D. Bhardwaj, S. Dayanand, A. Adusumilli, M. McNett, S. Sankaran, K. Manivannan, and L. Rigas. 2011. Windows azure storage: A highly available cloud storage service with strong consistency. In Symposium on Operating System Principles. Google ScholarDigital Library
- Y. Chen, R. Griffith, D. Zats, A. D. Joseph, and R. Katz. 2012. Understanding TCP incast and its implications for big data workloads. University of California at Berkeley, Technical Report.Google Scholar
- Y. L. Chen, S. Mu, J. Li, C. Huang, J. Li, A. Ogus, and D. Phillips. 2017. Giza: Erasure coding objects across global data centers. In USENIX Annual Technical Conference. Google ScholarDigital Library
- A. Cidon, S. M. Rumble, R. Stutsman, S. Katti, J. Ousterhout, and M. Rosenblum. 2013. Copysets: Reducing the frequency of data loss in cloud storage. In USENIX Annual Technical Conference. Google ScholarDigital Library
- J. Cowling. 2016. Dropbox's Exabyte Storage System. Retrieved from https://code.facebook.com/posts/253562281667886/data-scale-june-2016-recap/.Google Scholar
- A. Dimakis. 2016. Online Wiki Bibliography for Distributed Storage Papers. Retrieved from http://storagewiki.ece.utexas.edu/.Google Scholar
- A. Dimakis, P. Godfrey, Y. Wu, M. Wainwright, and K. Ramchandran. 2007. Network coding for distributed storage systems. In IEEE Infocom. Google ScholarDigital Library
- A. Dimakis, P. Godfrey, Y. Wu, M. Wainwright, and K. Ramchandran. 2010. Network coding for distributed storage systems. IEEE Transactions on Information Theory 56, 9 (Sept. 2010), 4539--4551. Google ScholarDigital Library
- Sage A. Weil, Scott A. Brandt, Ethan L. Miller, Darrell D. E. Long, and Carlos Maltzahn. 2006. A scalable, high-performance distributed file system. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation (OSDI'06). USENIX Association, Berkeley, CA, 307--320. Google ScholarDigital Library
- D. Ford, F. Labelle, F. Popovici, M. Stokely, V. Truong, L. Barroso, C. Grimes, and S. Quinlan. 2010. Availability in globally distributed storage systems. In USENIX Symposium on Operating Systems Designs and Implementation, 1--7. Google ScholarDigital Library
- Google. 2018. Snappy: A fast Compressor/Decompressor. Retrieved October 9, 2018, from https://google.github.io/snappy/.Google Scholar
- P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin. 2012. On the locality of codeword symbols. IEEE Transactions on Information Theory 58, 11 (Nov. 2012), 6925--6934. Google ScholarDigital Library
- C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li, and S. Yekhanin. 2012. Erasure coding in windows azure storage. In USENIX Annual Technical Conference. Google ScholarDigital Library
- G. Joshi, Y. Liu, and E. Soljanin. 2012. Coding for fast content download. In Proceedings of the 50th Allerton Conference on Communication, Control, and Computing (Allerton) (Oct. 2012), 326--333.Google ScholarCross Ref
- J. Lacan, V. Roca, J. Peltotalo, and S. Peltotalo. 2009. Reed-Solomon Forward Error Correction (FEC) Schemes, RFC 5510. Retrieved on April 2009 from https://www.rfc-editor.org/info/rfc5510.Google Scholar
- R. Li, X. Li, P. P. C. Lee, and Q. Huang. 2017. Repair pipelining for erasure-coded storage. In USENIX Annual Technical Conference. Google ScholarDigital Library
- M. Luby. 2016. Capacity bounds for distributed storage. arXiv article, April 2018, arXiv:1610.03541v5.Google Scholar
- M. Luby, A. Shokrollahi, M. Watson, T. Stockhammer, and L. Minder. 2011. RaptorQ Forward Error Correction Scheme for Object Delivery, RFC 6330. Retrieved on August 2011 from https://www.rfc-editor.org/info/rfc6330.Google Scholar
- S. Muralidhar, W. Lloyd, S. Roy, C. Hill, E. Lin, W. Liu, S. Pan, S. Shankar, V. Sivakumar, L. Tang, and S. Kumar. 2014. Facebook’s warm BLOB storage system. USENIX Conference on Operating Systems Design and Implementation 11 (2014), 383--398. Google ScholarDigital Library
- K. V. Rashmi, P. Nakkiran, J. Wang, N. B. Shah, and K. Ramchandran. 2015. Having your cake and eating it too: Jointly optimal erasure codes for I/O, storage, and network-bandwidth. In 13th USENIX File and Storage Technologies (File and Storage Technologies (FAST’15)), Vol. 13. USENIX Association. Google ScholarDigital Library
- K. V. Rashmi, N. B. Shah, D. Gu, H. Kuang, D. Borthakur, and K. Ramchandran. 2014. A “Hitchhiker’s” guide to fast and efficient data reconstruction in erasure-coded data centers. In ACM Conference on SIGCOMM. Google ScholarDigital Library
- R. Recio, B. Metzler, P. Culley, J. Hilland, and D. Garcia. 2007. A Remote Direct Memory Access Protocol Specification, RFC 5040. Retrieved October 2007 from https://www.rfc-editor.org/info/rfc5040.Google Scholar
- L. Rizzo. 1997. Effective erasure codes for reliable computer communication protocols. ACM SIGCOMM Computer Communication Review 27, 2 (April 1997), 24--36. Google ScholarDigital Library
- R. Rodrigues and B. Liskov. 2005. High availability in DHTs: Erasure coding vs. replication. Peer-to-Peer Systems IV (2005), 226--239. Google ScholarDigital Library
- Samsung. 2016. SM863a Specification Sheet. Retrieved October 8, 2018, from http://www.samsung.com/semiconductor/minisite/ssd/product/enterprise/sm863a.html.Google Scholar
- M. Sathiamoorty, M. Asteris, D. Papailiopoulos, A. Dimakis, R. Vadali, S. Chen, and D. Borthakur. 2013. XORing elephants: Novel erasure codes for big data. Proceedings of the VLDB Endowment 6, 5 (2013), 325--336. Google ScholarDigital Library
- A. Shokrollahi and M. Luby. 2011. Raptor codes. Foundations and Trends in Communications and Information Theory 6, 3--4 (2011), 213--322. Google ScholarDigital Library
- M. Silberstein, L. Ganesh, Y. Wang, and M. Dahlin L. Alvisi. 2014. Lazy means smart: Reducing repair bandwidth costs in erasure-coded distributed storage. In International Conference on Systems and Storage, 1--7. Google ScholarDigital Library
- E. Sit, A. Haeberlen, F. Dabek, B. Chun, H. Weatherspoon, R. Morris, M. Kaashoek, and J. Kubiatowicz. 2006. Proactive replication for data durability. International Workshop on Peer-to-Peer Systems 5 (2006). http://iptps06.cs.ucsb.edu/papers/Sit-tempo.pdf.Google Scholar
- H. Weatherspoon and J. Kubiatowicz. 2002. Erasure coding vs. replication: A quantitative comparison. In Proceedings of the First International Workshop on Peer-to-Peer Systems (2002). 328--337. Google ScholarDigital Library
Index Terms
- Liquid Cloud Storage
Recommendations
IRON file systems
SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principlesCommodity file systems trust disks to either work or fail completely, yet modern disks exhibit more complex failure modes. We suggest a new fail-partial failure model for disks, which incorporates realistic localized faults such as latent sector errors ...
IRON file systems
SOSP '05Commodity file systems trust disks to either work or fail completely, yet modern disks exhibit more complex failure modes. We suggest a new fail-partial failure model for disks, which incorporates realistic localized faults such as latent sector errors ...
InPlaceKV: in-place update scheme for SSD-based KV storage systems under update-intensive Worklaods
AbstractModern key-value (KV) storage systems adopt append-only writes to update KV pairs with the out-of-place manner, because the performance of sequential accesses is much better than that of random accesses for HDDs. Compaction or GC operations will ...
Comments