  Practical storage systems often adopt erasure codes to tolerate device
failures and sector failures, both of which are prevalent in the field.
However, traditional erasure codes employ device-level redundancy to protect
against sector failures, and hence incur significant space overhead. Recent
sector-disk (SD) codes are available only for limited configurations. By making
a relaxed but practical assumption, we construct a general family of erasure
codes called \emph{STAIR codes}, which efficiently and provably tolerate both
device and sector failures without any restriction on the size of a storage
array and the numbers of tolerable device failures and sector failures. We
propose the \emph{upstairs encoding} and \emph{downstairs encoding} methods,
which provide complementary performance advantages for different
configurations. We conduct extensive experiments on STAIR codes in terms of
space saving, encoding/decoding speed, and update cost. We demonstrate that
STAIR codes not only improve space efficiency over traditional erasure codes,
but also provide better computational efficiency than SD codes based on our
special code construction. Finally, we present analytical models that
characterize the reliability of STAIR codes, and show that the support of a
wider range of configurations by STAIR codes is critical for tolerating sector
failure bursts discovered in the field.
