The MDS Queue: Analysing Latency Performance of Codes and Redundant Requests
The MDS Queue: Analysing Latency Performance of Codes and Redundant Requests
复制标题
MDS 队列：分析代码和冗余请求的延迟性能
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
K. Ramchandran
中科院分区：
文献类型：
--
作者：
Nihar B. Shah;Kangwook Lee;K. Ramchandran
为了经济地扩展，数据中心越来越多地将其数据存储方法从使用简单的数据复制发展到使用更强大的擦除码，擦除码以显著更低的存储成本提供与基于复制的方法相同的可靠性水平。特别地，众所周知，最大距离可分离（MDS）码，例如里德-所罗门码，提供最大存储效率。虽然在档案存储系统中使用代码来提供改进的可靠性是很好理解的，在档案存储系统中，数据被不太频繁地访问（或所谓的“冷数据”），但是代码在更频繁地访问和活动的“热数据”的存储中的作用不太清楚，在档案存储系统中，延迟是关键度量。本文从排队论的透镜研究了基于MDS码的数据存储系统，称之为“MDS排队”。我们分析MDS队列的延迟性能，我们提出了有见地的调度政策，形成性能的上限和下限，并表明他们是相当紧张的。还提供了使用Monte Carlo方法的广泛模拟，并用于验证我们的理论分析。作为一个侧记，我们的下限分析方法的基础上，所谓的MDS保留（t）队列，代表了一个优雅的实用方案，需要维护相当小的状态，取决于参数t，比成熟的MDS队列（对应于t =∞），并可能在实际系统中的独立利益。与基于复制的系统的比较表明，代码提供了一个上级的延迟性能（高达70%）比复制。本文的第二部分考虑了一种（潜在地）减少数据中心延迟的替代方法，即发送冗余请求。在这里，请求被发送到比所需更多的服务器，并且当任何必要数量的服务器完成服务时被视为已服务。最近的几项工作提供了经验证据的好处冗余请求在各种设置，在本文中，我们的目标是分析的情况下，冗余请求实际上可以帮助的特点。我们表明，在MDS队列模型（指数服务时间和可忽略不计的成本取消作业），在基于复制的系统中，平均延迟严格减少更多的冗余请求，并在一般MDS代码，平均延迟最小化时，请求发送到所有服务器。据我们所知，这些是证明发送冗余请求的好处的第一个分析结果。
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 MaximumDistance-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 latency performance of MDS queues, for which we present insightful scheduling policies that form upper and lower bounds to performance, and show that they are quite tight. Extensive simulations using Monte Carlo 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 =∞), and may be of independent interest in practical systems. Comparisons with replication-based systems reveal that codes provide a superior latency-performance (by up to 70%) than replication. The second part of the paper considers an alternative method of (potentially) reducing latency in data centers, that of sending redundant requests. Here, a request is sent to more servers than required, and is deemed served when any requisite number of servers complete service. Several recent works provide empirical evidence of the benefits of redundant requests in various settings, and in this paper, we aim to analytically characterize the situations when can redundant requests actually help. We show that under the MDS queue model (with exponential service times and negligible costs of cancelling jobs), in a replication-based system, the average latency strictly reduces with more redundancy in the requests, and that under a general MDS code, the average latency is minimized when requests are sent to all servers. To the best of our knowledge, these are the first analytical results that prove the benefits of sending redundant requests.