Access balancing in storage systems by labeling partial Steiner systems

摘要

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) designs can be labeled to realize the elementary lower bound. Furthermore, we prove that for every admissible orderv, 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.