Geometric Partitioning
- 26 October 2021
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles CD-ROM
Abstract
Erasure coding is widely used in building reliable distributed object storage systems despite its high repair cost. Regenerating codes are a special class of erasure codes, which are proposed to minimize the amount of data needed for repair. In this paper, we assess how optimal repair can help to improve object storage systems, and we find that regenerating codes present unique challenges: regenerating codes repair at the granularity of chunks instead of bytes, and the choice of chunk size leads to the tension between streamed degraded read time and repair throughput. To address this dilemma, we propose Geometric Partitioning, which partitions each object into a series of chunks with their sizes in a geometric sequence to obtain the benefits of both large and small chunk sizes. Geometric Partitioning helps regenerating codes to achieve 1.85x recovery performance of RS code while keeping degraded read time low.Keywords
Funding Information
- National Key Research & Development Program of China (2020YFC1522702)
- Natural Science Foundation of China (61877035)
This publication has 22 references indexed in Scilit:
- The Snowflake Elastic Data WarehousePublished by Association for Computing Machinery (ACM) ,2016
- Partial-parallel-repair (PPR)Published by Association for Computing Machinery (ACM) ,2016
- A high-rate MSR code with polynomial sub-packetization levelPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2015
- The quantcast file systemProceedings of the VLDB Endowment, 2013
- Simple regenerating codes: Network coding for cloud storagePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2012
- Building a database on S3Published by Association for Computing Machinery (ACM) ,2008
- The HP AutoRAID hierarchical storage systemACM Transactions on Computer Systems, 1996
- Disk file allocation based on the buddy systemACM Transactions on Computer Systems, 1987
- A fast storage allocatorCommunications of the ACM, 1965
- Polynomial Codes Over Certain Finite FieldsJournal of the Society for Industrial and Applied Mathematics, 1960