Access balancing in storage systems by labeling partial Steiner systems
Access balancing in storage systems by labeling partial Steiner systems
复制标题
DOI：
10.1109/isit44484.2020.9174154
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Yeow Meng Chee;C. Colbourn;Hoang Dau;Ryan Gabrys;A. Ling;Dylan Lusi;O. Milenkovic
中科院分区：
文献类型：
--
作者：
Yeow Meng Chee;C. Colbourn;Hoang Dau;Ryan Gabrys;A. Ling;Dylan Lusi;O. Milenkovic
Storage architectures ranging from minimum bandwidth regenerating encoded distributed storage systems to declustered-parity RAIDs can employ dense partial Steiner systems to support fast reads, writes, and recovery of failed storage units. To enhance performance, popularities of the data items should be taken into account to make frequencies of accesses to storage units as uniform as possible. A combinatorial model ranks items by popularity and assigns data items to elements in a dense partial Steiner system so that the sums of ranks of the elements in each block are as equal as possible. By developing necessary conditions in terms of independent sets, we demonstrate that certain Steiner systems must have a much larger difference between the largest and smallest block sums than is dictated by an elementary lower bound. In contrast, we also show that certain dense partial S(t,t+1,v)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S(t,t+1,v)$$\end{document} designs can be labeled to realize the elementary lower bound. Furthermore, we prove that for every admissible order v, there is a Steiner triple system (S(2, 3, v)) whose largest difference in block sums is within an additive constant of the lower bound.
Storage architectures ranging from minimum bandwidth regenerating encoded distributed storage systems to declustered-parity RAIDs can employ dense partial Steiner systems to support fast reads, writes, and recovery of failed storage units. To enhance performance, popularities of the data items should be taken into account to make frequencies of accesses to storage units as uniform as possible. A combinatorial model ranks items by popularity and assigns data items to elements in a dense partial Steiner system so that the sums of ranks of the elements in each block are as equal as possible. By developing necessary conditions in terms of independent sets, we demonstrate that certain Steiner systems must have a much larger difference between the largest and smallest block sums than is dictated by an elementary lower bound. In contrast, we also show that certain dense partial S(t,t+1,v)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S(t,t+1,v)$$\end{document} designs can be labeled to realize the elementary lower bound. Furthermore, we prove that for every admissible order v, there is a Steiner triple system (S(2, 3, v)) whose largest difference in block sums is within an additive constant of the lower bound.