Access balancing in storage systems by labeling partial Steiner systems
- PDF / 368,500 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 43 Downloads / 214 Views
Access balancing in storage systems by labeling partial Steiner systems Yeow Meng Chee1 · Charles J. Colbourn2 · Hoang Dau3 · Ryan Gabrys4 · Alan C. H. Ling5 · Dylan Lusi2 · Olgica Milenkovic4 Received: 28 December 2019 / Revised: 14 July 2020 / Accepted: 30 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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 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. Keywords Steiner system · Steiner triple system · Independent set · Access balancing Mathematics Subject Classification 05B07 · 05B40 · 68R05 · 94B60
1 Introduction Distributed storage systems [15,35], systems for batch coding [36], and multiserver private information retrieval systems [18] have each employed combinatorial designs for data placement, so that elements of the design are associated with data items and blocks with storage units. In these contexts, the most common types of designs employed are t-designs and t-
Communicated by M. Buratti. The work was supported by NSF Grants CCF 1816913 (CJC) and 1814298 (OM).
B
Charles J. Colbourn [email protected]
Extended author information available on the last page of the article
123
Y. M. Chee et al.
packings. A t-(v, k, λ) packing is a pair (X , B), where X , the point set, is a v-set and and B is a collection of k-subsets (blocks) of X such that every t-subset of X is contained in at most λ blocks. The packing is a t-(v, k, λ) design when every t-subset of X is a subset of exactly λ blocks. A t-(v, k, 1) design is a Steiner system, denoted by S(t, k, v). A 2-(v, 3, 1) design is a Steiner triple system of order v, denoted by STS(v). When λ = 1, a t-(v, k, 1) packing is also referred to as a partial S(t, k, v) or partial Steiner system. When data items are of the same size, and data is placed on storage units using a t-design, placement of data is uniform across the storage units. Indeed in t-(v, k, λ) design, every point λ(v−1 t−1 ) appears in exactly r = k−1 blocks; this is
Data Loading...
