A code over a finite alphabet is called locally recoverable (LRC) if every
symbol in the encoding is a function of a small number (at most $r$) other
symbols. We present a family of LRC codes that attain the maximum possible
value of the distance for a given locality parameter and code cardinality. The
codewords are obtained as evaluations of specially constructed polynomials over
a finite field, and reduce to a Reed-Solomon code if the locality parameter $r$
is set to be equal to the code dimension. The size of the code alphabet for
most parameters is only slightly greater than the code length. The recovery
procedure is performed by polynomial interpolation over $r$ points. We also
construct codes with several disjoint recovering sets for every symbol. This
construction enables the system to conduct several independent and simultaneous
recovery processes of a specific symbol by accessing different parts of the
codeword. This property enables high availability of frequently accessed data
("hot data").

本篇文章介绍了一种局部可恢复编码（LRC），其使用特殊构造的多项式在有限域上进行编码，并通过多项式插值进行局部恢复。此外，还构造出具有多个不相交恢复集的编码，从而实现对热数据的高可用性。

一类最优本地可恢复码族

A family of optimal locally recoverable codes

In order to scale economically, data centers are increasingly evolving their
data storage methods from the use of simple data replication to the use of more
powerful erasure codes, which provide the same level of reliability as
replication but at a significantly lower storage cost. In particular, it is
well known that Maximum-Distance-Separable (MDS) codes, such as Reed-Solomon
codes, provide the maximum storage efficiency. While the use of codes for
providing improved reliability in archival storage systems, where the data is
less frequently accessed (or so-called "cold data"), is well understood, the
role of codes in the storage of more frequently accessed and active "hot data",
where latency is the key metric, is less clear.
In this paper, we study data storage systems based on MDS codes through the
lens of queueing theory, and term this the "MDS queue." We analytically
characterize the (average) latency performance of MDS queues, for which we
present insightful scheduling policies that form upper and lower bounds to
performance, and are observed to be quite tight. Extensive simulations are also
provided and used to validate our theoretical analysis. We also employ the
framework of the MDS queue to analyse different methods of performing so-called
degraded reads (reading of partial data) in distributed data storage.

本文研究基于 MDS 码的数据存储系统，通过队列理论分析其表现，并提供上下界的调度策略。同时，利用 MDS 队列的框架分析了分布式数据存储中不同方法执行降级读取的情况。