Pyramid Codes: Flexible Schemes to Trade Space for Access Efficiency in Reliable Data Storage Systems

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.