Hawkynt

LRC Pyramid Code

Hierarchical locally recoverable code with pyramid structure used in Microsoft Azure Storage. 12+2+2 configuration with local parity groups enabling fast single-failure recovery and global parity for multiple failures. Reduces I/O for repairs compared to Reed-Solomon while optimizing bandwidth versus reliability trade-off.

Properties

Property	Value
Category	Error Correction
Sub-category	Locally Recoverable Code
Security status	🎓 Educational Only
Complexity	Advanced
Inventor	Cheng Huang, Huseyin Simitci, Yikang Xu
Year	2012
Origin	🇺🇸 United States
Source	algorithms/ecc/lrc-pyramid-code.js

Security

Status: 🎓 Educational Only

Known vulnerabilities

Issue	Description	Mitigation
Limited Global Error Correction	With only 2 global parities, can only correct up to 2 erasures beyond local group capacity. Multiple failures in different groups may exceed correction capability.	—
Local Group Dependency	If both symbols in a local parity group fail along with the local parity, local recovery is impossible and requires global reconstruction.	—
Bandwidth Trade-off	While reducing I/O for single failures, still requires significant bandwidth for multiple concurrent failures affecting multiple local groups.	—

Documentation

• Erasure Coding in Windows Azure Storage (USENIX ATC 2012)
• Microsoft Research - Azure Storage Paper
• Pyramid Codes Paper (IEEE NCA 2007)

References

• USENIX ATC 2012 Full Paper
• Pyramid Codes (Huang, Chen, Li 2007)
• LRC Theory Paper
• GitHub Reference Implementation

Test vectors

6 vectors ship with this algorithm and run in the test suite. Byte values are hexadecimal.

Vector 1 — LRC Pyramid (12,2,2) all zeros

Field	Value
input	000000000000000000000000
expected	00000000000000000000000000000000

Vector 2 — LRC Pyramid (12,2,2) single data block in first local group

Field	Value
input	010000000000000000000000
expected	01000000000000000000000001000101

Vector 3 — LRC Pyramid (12,2,2) single data block in second local group

Field	Value
input	000000000000010000000000
expected	00000000000001000000000000010107

Vector 4 — LRC Pyramid (12,2,2) alternating pattern

Field	Value
input	010001000100010001000100
expected	01000100010001000100010001010002

Vector 5 — LRC Pyramid (12,2,2) full ones pattern

Field	Value
input	010101010101010101010101
expected	0101010101010101010101010000000c

Vector 6 — LRC Pyramid (12,2,2) mixed values testing local and global parities

Field	Value
input	0503070204060801090b0d0f
expected	0503070204060801090b0d0f01090806

---

← All algorithms

This site is open source. Improve this page.