Abstract:

With the popularity of erasure code technology, high data reliability and high spatial efficiency storage performance are gradually realized in distributed storage, but reducing tail delay is still a problem to be solved. Therefore, this paper proposes an algorithm framework to quantify and optimize the tail delay of erasure coding storage system. For any service time distribution and heterogeneous files, the upper bound of tail delay is derived. Then, an optimization model is proposed to minimize the weighted delay tail probability of all files placed on the server and the server selection of access request files, and its nonconvex characteristics are proved, so that an efficient alternative optimization algorithm can be used. In addition, by describing the asymptotic behavior of the tail of delay distribution, the tail index of service delay of arbitrary erasure code storage is mathematically quantified in closed form, and it is proved that the algorithm based on probability scheduling is（asymptotically） optimal. The experimental results show that the tail delay of erasure coding storage system is significantly reduced under the actual workload.

Key words: cloud storage, heterogeneous files, joint delay, tail probability, convex optimization

摘要：

随着擦除码技术的流行，分布式存储中高数据可靠性和高空间效率存储性能逐渐实现，但是降低尾部延迟仍然是一个有待解决的问题。为此，提出一种量化和优化擦除编码存储系统尾延迟的算法框架。对于任意服务时间分布和异构文件，推导给出尾部延迟上界。提出了一个优化模型，使得所有文件在服务器上放置的加权延迟尾概率和访问请求文件的服务器选择共同最小化，并证明了其非凸问题特性，以便采用一种高效的交替优化算法求解。此外，通过描述延迟分布尾部的渐近行为，以闭合形式对任意擦除编码存储的服务延迟的尾部指数进行数学量化，证明了基于概率调度的算法是（渐近）最优的。实验结果表明，在实际工作负载下擦除编码存储系统的尾部延迟显著降低。

关键词: 云存储, 异构文件, 联合延迟, 尾概率, 凸优化