Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Pyramid Codes: Flexible Schemes to Trade Space for Access Efficiency in Reliable Data Storage Systems

Cheng Huang, Minghua Chen, and Jin Li

Abstract

We describe flexible schemes to explore the tradeoffs between storage space and access efficiency in reliable data storage systems. Aiming at this goal, two fundamentally different classes of codes are introduced under the same naming umbrella – Pyramid Codes. The basic Pyramid Codes are simply derived from any existing codes (preferably MDS codes [18]), and thus all existing work on optimizing encoding/decoding directly apply. The generalized Pyramid Codes are radically advanced new codes, which can further improve reliability and/or access efficiency upon the basic Pyramid Codes. Moreover, we define a necessary condition for any failure pattern to be recoverable and show the generalized Pyramid Codes are optimal under the condition. To our best knowledge, this is the first work to define such a condition and the generalized Pyramid Codes are the only known non-MDS codes with such optimal property.

Details

Publication typeTechReport
NumberMSR-TR-2007-25
Pages14
InstitutionMicrosoft Research
PublisherMicrosoft
> Publications > Pyramid Codes: Flexible Schemes to Trade Space for Access Efficiency in Reliable Data Storage Systems