The MDS Queue. (arXiv:1211.5405v1 [cs.IT])

from cs.NI updates on

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-based methods 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” is less clear. In fact, a key question is: when the
performance metric is no longer data reliability but rather latency, do codes
even help?

In this paper, we answer this question in the affirmative by studying coded
data storage systems based on MDS codes through the lens of queueing theory,
and term this the “MDS queue.” We analytically characterize the latency
performance of MDS queues, and reveal its superior performance (up to 70%)
compared to that of currently used replication-based schemes. In our analysis
of MDS queues, we present insightful scheduling policies that form upper and
lower bounds to performance, and show that they are quite tight. Extensive
simulations of the MDS queue using Markov-Chain-Monte-Carlo (MCMC) methods are
also provided and used to validate our theoretical analysis. As a side note,
our lower-bound analytical method based on the so-called MDS-Reservation(t)
queue, represents an elegant practical scheme that requires the maintenance of
considerably smaller state, depending on the parameter t, than that of the
full-fledged MDS queue (which corresponds to t=infinity), and may be of
independent interest in practical systems.



Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s