Search

In distributed storage systems, an r-Locally Repairable Code (r-LRC) ensures that a failed symbol can be recovered by accessing at most r other symbols. Prakash et al. in (Proceedings of IEEE International Symposium on Information Theory, pp. 2776–2780, 2012) further introduced the concept of (r , δ) -LRC, where δ ≥ 2 , which can deal with the symbol failure in the presence of extra δ - 2 symbol failures still by accessing at most r other symbols. In particular, an r-LRC is just an (r, 2)-LRC. Luo and Ling in (Des Codes Cryptogr 90:1271–1287, 2022) obtained some alphabet-optimal r-LRCs concerning the Cadambe–Mazumdar bound from optimal linear codes constructed by special projective spaces. In this paper, we generalize the results of Luo and Ling in (Des Codes Cryptogr 90:1271–1287, 2022). Firstly, we generalize the result of constructing optimal linear codes to larger code length. In particular, we present the conditions for the constructed linear codes to qualify as Griesmer codes or distance-optimal codes. Secondly, we explore the locality of the constructed codes. The novelty of our work lies in establishing the locality as (r , δ) -locality and (r , δ) -locality with availability, in contrast to the previous literature that only considered r-locality. In addition, through the analysis combining the code parameters and the Cadambe–Mazumdar-like bound for (r , δ) -LRCs, we obtained some alphabet-optimal (r , δ) -LRCs and alphabet-optimal (r , δ) -LRCs with availability. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRCs), which can recover any symbol of a codeword by reading only a small number of other symbols, have been widely used in real-world distributed storage systems, such as Microsoft Azure Storage and Ceph Storage Cluster. Since binary linear LRCs can significantly reduce coding and decoding complexity, constructions of binary LRCs are of particular interest. The aim of this paper is to construct dimensional optimal binary LRCs with disjoint local repair groups. We introduce a method to connect intersection subspaces with binary LRCs and construct dimensional optimal binary linear LRCs with locality 2b (b ≽ 3) and minimum distance d ≽ 6 by employing intersection subspaces deduced from the direct sum. This method will sufficiently increase the number of possible repair groups of dimensional optimal LRCs, thus efficiently expanding the range of the construction parameters while keeping the largest code rates compared with all known binary linear LRCs with minimum distance d ≽ 6 and locality 2b. [ABSTRACT FROM AUTHOR]

Fractional Repetition (FR) codes break the data into smaller fragments and distribute these fragments across multiple storage nodes. This paper focuses on extension-based construction methods for obtaining new FR codes from existing FR codes. Additionally, it formulates a particular case of extension codes as an exact cover problem, enabling an algorithmic construction of FR codes. [ABSTRACT FROM AUTHOR]

A locally repairable code (LRC) is a code that can recover any symbol of a codeword by reading at most r other symbols, denoted by r -LRC. In this paper, we study binary and ternary linear LRCs with disjoint repair groups and minimum distance d = 6. Using the intersection subspaces technique, we explicitly construct dimensional optimal LRCs. First, based on the intersection subspaces constructed by t -spread, a construction of binary LRCs is designed. Particularly, a class of binary linear LRCs with r = 11 is optimal in terms of achieving a sphere-packing type upper bound. Next, by using the Kronecker product of two matrices, two classes of dimensional optimal ternary LRCs with small locality (r = 3, 5) are presented. Compared to previous results, our construction is more flexible regarding code parameters. Finally, we also discuss the parameters of a code obtained by applying a shortening operation to our LRCs. We show that these shortened LRCs are also k -optimal. [ABSTRACT FROM AUTHOR]

Most of the data in large-scale storage clusters is erasure coded. At exascale, optimizing erasure codes for low storage overhead, efficient reconstruction, and easy deployment is of critical importance. Locally recoverable codes (LRCs) have deservedly gained central importance in this field, because they can balance many of these requirements. In our work, we study wide LRCs; LRCs with large number of blocks per stripe and low storage overhead. These codes are a natural next step for practitioners to unlock higher storage savings, but they come with their own challenges. Of particular interest is their reliability, since wider stripes are prone to more simultaneous failures. We conduct a practically minded analysis of several popular and novel LRCs. We find that wide LRC reliability is a subtle phenomenon that is sensitive to several design choices, some of which are overlooked by theoreticians, and others by practitioners. Based on these insights, we construct novel LRCs called Uniform Cauchy LRCs, which show excellent performance in simulations and a 33% improvement in reliability on unavailability events observed by a wide LRC deployed in a Google storage cluster. We also show that these codes are easy to deploy in a manner that improves their robustness to common maintenance events. Along the way, we also give a remarkably simple and novel construction of distance-optimal LRCs (other constructions are also known), which may be of interest to theory-minded readers. [ABSTRACT FROM AUTHOR]

This article describes the algorithm, implementation, and deployment experience of CacheSack, the admission algorithm for Google datacenter flash caches. CacheSack minimizes the dominant costs of Google’s datacenter flash caches: disk IO and flash footprint. CacheSack partitions cache traffic into disjoint categories, analyzes the observed cache benefit of each subset, and formulates a knapsack problem to assign the optimal admission policy to each subset. Prior to this work, Google datacenter flash cache admission policies were optimized manually, with most caches using the Lazy Adaptive Replacement Cache algorithm. Production experiments showed that CacheSack significantly outperforms the prior static admission policies for a 7.7% improvement of the total cost of ownership, as well as significant improvements in disk reads (9.5% reduction) and flash wearout (17.8% reduction). [ABSTRACT FROM AUTHOR]

Cache prefetching technology has become the mainstream data access optimization strategy in the Industrial Intelligent Systems (IIS) and the data centers. However, the rapidly increasing of unstructured data generates massive pairwise access relationships. Therefore, researchers have to make a choice between spatial locality and temporal locality to ensure an acceptable computational complexity. We propose cache‐transaction‐based data grouping model (CTDGM) to solve the problems described above by optimizing the feature representation method and grouping efficiency. First, we provide the definition of the cache transaction and propose the method for extracting the cache transaction feature (CTF). Second, we design a data chunking algorithm based on CTF and spatiotemporal locality to optimize the relationship calculation efficiency. Third, we propose CTDGM by constructing a relation graph that groups data into independent groups according to the strength of the data access relation. Based on the results of the experiment, compared with the state‐of‐the‐art and traditional methods, our algorithm achieves an average increase in the cache hit rate of 5%–20% on the MSR, VDI‐LUN, and KC data set, which in turn reduces the number of data I/O accesses by 30%–60%. [ABSTRACT FROM AUTHOR]

Erasure codes are essential for providing efficient resilience against node failures in distributed storage. Typically, an $[n, k]$ erasure code encodes $k$ symbols into $n$ symbols which are then stored in different nodes. Recent work by Kadekodi et al. shows that the failure rates of storage nodes vary significantly over time, and that changing the rate of the code (via a change in $n$ and $k$) in response to such variations provides substantial storage space savings. However, the resource overhead of re-encoding the already encoded data is prohibitively high. We present a new theoretical framework formalizing code conversion—the process of converting data encoded with an $[n^{ I}, k^{ I}]$ code into data encoded with an $[{n^{ F}}, {k^{ F}}]$ code while maintaining desired decodability properties. We then introduce convertible codes, a new class of codes that allow for code conversions in a resource-efficient manner. This paper begins the study on convertible codes by focusing on linear MDS codes and the access cost of conversion. We derive a lower bound on the access cost of conversion and present an explicit optimal construction matching this bound for an important subclass of conversions. Additionally, we propose constructions with low field-size requirement for a broad subset of parameters. Our results show that it is possible to achieve code conversions with significantly less resources than the default approach of re-encoding for a wide range of parameters. [ABSTRACT FROM AUTHOR]

We consider the setting of a distributed storage system where a single file is subdivided into smaller fragments of same size which are then replicated with a common replication factor across servers of identical cache size. An incoming file download request is sent to all the servers, and the download is completed whenever the request gathers all the fragments. At each server, we are interested in determining the set of fragments to be stored, and the sequence in which fragments should be accessed, such that the mean file download time for a request is minimized. We model the fragment download time as an exponential random variable independent and identically distributed for all fragments across all servers, and show that the mean file download time can be lower bounded in terms of the expected number of useful servers summed over all distinct fragment downloads. We present deterministic storage schemes that attempt to maximize the number of useful servers. We show that finding the optimal sequence of accessing the fragments is a Markov decision problem, whose complexity grows exponentially with the number of fragments. We propose heuristic algorithms that determine the sequence of access to the fragments which are empirically shown to perform well. [ABSTRACT FROM AUTHOR]

Erasure codes have been widely considered as a promising solution to enhance data reliability at low storage costs. However, in modern geo-distributed storage systems, erasure codes may incur high data access latency as they require data retrieval from multiple remote storage nodes. This hinders the extensive application of erasure codes to data-intensive applications. This paper proposes novel caching schemes to achieve low latency in distributed coded storage systems. Assuming that future data popularity and network latency information are available, an offline caching scheme is proposed to explore the optimal caching solution for low latency. The proposed scheme categorizes all feasible caching decisions into a set of cache partitions, and then obtains the optimal caching decision through market clearing price for each cache partition. Furthermore, guided by the optimal scheme, an online caching scheme is proposed according to the measured data popularity and network latency information in real time, without the need to completely override the existing caching decisions. Both theoretical analysis and experiment results demonstrate that the online scheme can approximate the offline optimal scheme well with dramatically reduced computation complexity. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRCs) are important for distributed storage systems due to their efficient repairing ability of the failed storage nodes. A $q$ -ary optimal $(n,k,r)$ -LRC is an $[n,k,d]$ linear code over $\mathbb {F}_{q}$ such that every code symbol has locality $r$ , and the minimum distance attains the well-known Singleton-like bound. In this paper, we study the maximal code length, code constructions and weight distributions of $q$ -ary optimal LRCs with locality 2 and distance 5, which are of both practical and theoretical interest. Firstly, it is proved that when the code dimension is even or odd, corresponding maximal code lengths of such $q$ -ary optimal LRCs are $3 \cdot \lfloor \frac {q+1}{3} \rfloor $ and $3 \cdot \left \lfloor{ \frac {q-1}{3} }\right \rfloor +5$ , respectively. Up to the equivalence of linear codes, we propose constructions of all the possible $q$ -ary optimal LRCs with locality 2, distance 5 and maximal code length. Then, by characterizing the weight type hierarchy of codewords, we show that the weight distribution of any $q$ -ary optimal LRC with locality 2, distance 5 and even code dimension can be uniquely determined and explicit expression of the weight distribution is given. Moreover, it is shown that all $q$ -ary optimal LRCs with locality 2, distance 5 and even code dimension are maximally recoverable. [ABSTRACT FROM AUTHOR]

In most storage systems, the storage nodes store data on a local filesystem. Thus, unless they have a dedicated caching layer, they benefit from the usual filesystem cache in the host's free memory. However, in erasure-coded storage systems, caching is effective only if all the systematic fragments corresponding to an object are in the cache. In this work, we propose a new caching policy adapting traditional methods to erasure-coded storage systems. The main idea of our solution is to cache a full object rather than fragments object. A simulation-based evaluation showed that our full replica solution is able to improve the cache hit ratio and reduce the cache waste ratio compared to the traditional caching method. Moreover, experimental evaluation has been conducted. It indicates that our implementation not only validates the previous results but also shows that cache hits on full replicas have a better request response time. [ABSTRACT FROM AUTHOR]

Integrating cyber, physical, and social spaces together, cyber-physical-social systems (CPSS) bring more conveniences to humans. For practical applications and user convenience, it is essential that the Big Data produced in CPSS be stored in the distributed storage systems of CPSS. In this paper, we study the fault tolerance scheme for distributed storage systems of CPSS, and propose a framework that can recover multiple failed nodes simultaneously. Considering the reliability of storage nodes in distributed storage systems, the research on locally repairable codes has mostly focused on repairing failed nodes within each repair group. However, when entire repair groups have failed, existing locally repairable codes cannot repair more than one failed group. In this paper, local codes with cooperative repair that can recover more than one failed group are proposed. Specifically, the proposed local codes are constructed based on minimum storage regenerating (MSR) codes, and have an interleaving structure among the local codes, so that the parity symbols of any local code can be generated from the MSR codes in its two adjacent local codes. Taking advantage of this property, more than one failed local group can be repaired cooperatively by their adjacent local groups with lower repair locality. Furthermore, the key parameters of local codes with cooperative repair are derived. Theoretical analysis and simulation results show that, compared with previous codes with local regeneration, our codes have higher bandwidth overhead when repairing failed nodes, but advantages in storage overhead and repair locality either for repair of a single failed node or one failed local group. Moreover for a single failed local group, local codes with cooperative repair achieve almost the same tradeoff curve of storage overhead and bandwidth overhead as MSR-local codes and minimum bandwidth regenerating local (MBR-local) codes.

Distributed systems operate under storage access and download service uncertainty. We consider two access models. In one, a user can access each storage node with a fixed probability, and in the other, a user can access any fixed-size subset of nodes. We consider two download service models. In the first (small file) model, the time to transmit file data is negligible compared to the overall average download time. In the second (large file) model, the download time scales with the amount of downloaded data. The performance metric is the system’s service rate. For a fixed redundancy level, the systems’ service rate depends on the allocation of coded chunks over the storage nodes. Since finding the general optimal allocation is prohibitively hard, we consider quasi-uniform allocations, where coded content is equally spread among a subset of nodes. The question we address asks what the size of this subset (spreading) should be. We show that concentrating the coded content to a minimum-size subset is universally optimal for the small file model. However, for the large file model, the optimal spreading depends on the system parameters. These conclusions hold for both access models. [ABSTRACT FROM AUTHOR]

In recent years, the rapidly increasing amounts of data created and processed through the internet resulted in distributed storage systems employing erasure coding based schemes. Aiming to balance the tradeoff between data recovery for correlated failures and efficient encoding and decoding, distributed storage systems employing maximally recoverable codes came up. Unifying a number of topologies considered both in theory and practice, Gopalan et al. [15] initiated the study of maximally recoverable codes for grid-like topologies. In this paper, we focus on the maximally recoverable codes that instantiate grid-like topologies T m × n (1 , b , 0) . To characterize the property of codes for these topologies, we introduce the notion of pseudo-parity check matrix. Then, using the Combinatorial Nullstellensatz, we establish the new upper bound on the field size needed for achieving the maximal recoverability in topologies T m × n (1 , b , 0) . By relating the problem to generalized Sidon sets in F q , we obtain a polynomial lower bound on the field size for maximally recoverable codes that instantiate topologies T m × n (1 , 2 , 0) . Moreover, using hypergraph independent set approach, we further improve our general upper bound for topologies T 4 × n (1 , 2 , 0) and T 3 × n (1 , 3 , 0) . [ABSTRACT FROM AUTHOR]

Codes with availability allow us to access any code symbol simultaneously t times using t disjoint recovery sets in distributed data storage. Codes with availability that are studied in the literature provide availability for individual code symbols in the codeword. In this letter, we consider a new class of codes with availability. These codes provide availability t for subsets of code symbols called multi-symbol sets. For these codes, an upper-bound on the minimum Hamming distance is derived. A construction for optimal codes with information multi-symbol availability is given. The optimal codes with multi-symbol availability allow us to access more symbols locally with the same locality, when compared to optimal codes with individual code symbol availability. [ABSTRACT FROM AUTHOR]

At present, the research on locally repairable codes (LRCs) in distributed storage systems indicates that, it is relatively easy to construct binary LRCs (BLRCs) with the optimal minimum distance, but under the condition of minimum distance upper bound, it remains difficult to construct the BLRCs with the optimal code rate. In order to solve the problem, BLRCs with optimal minimum distance and optimal code rate are constructed in this letter. The constructed linear codes are BLRCs with locality and availability of information symbols, and each repair group has only one parity symbol. Specifically, the method of block group design is adopted to construct the BLRCs with optimal minimum distance and optimal code rate of locality r = 2 or availability t = 2. Compared with the BLRCs proposed by W. Song et al, the BLRCs constructed in this letter perform better in code length and code rate. Furthermore, using the method of identity matrix transformation, BLRCs with optimal minimum distance and optimal code rate for availability t = 2 are also constructed. Compared with the existing BLRCs based on graph construction, this construction has the same characteristics of minimum distance and code rate. [ABSTRACT FROM AUTHOR]

We propose repair pipelining, a technique that speeds up the repair performance in general erasure-coded storage. By carefully scheduling the repair of failed data in small-size units across storage nodes in a pipelined manner, repair pipelining reduces the single-block repair time to approximately the same as the normal read time for a single block in homogeneous environments. We further design different extensions of repair pipelining algorithms for heterogeneous environments and multi-block repair operations. We implement a repair pipelining prototype, called ECPipe, and integrate it as a middleware system into two versions of Hadoop Distributed File System (HDFS) (namely, HDFS-RAID and HDFS-3) as well as Quantcast File System. Experiments on a local testbed and Amazon EC2 show that repair pipelining significantly improves the performance of degraded reads and full-node recovery over existing repair techniques. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRCs) are a class of erasure codes that are widely used in distributed storage systems, which allow for efficient recovery of data in the case of node failures or data loss. In 2014, Tamo and Barg introduced Reed-Solomon-like (RS-like) Singleton-optimal (r , δ) -LRCs based on polynomial evaluation. These constructions rely on the existence of so-called good polynomial that is constant on each of some pairwise disjoint subsets of F q. In this paper, we extend the aforementioned constructions of RS-like LRCs and propose new constructions of (r , δ) -LRCs whose code length can be larger. These new (r , δ) -LRCs are all distance-optimal, namely, they attain an upper bound on the minimum distance that will be established in this paper. This bound is sharper than the Singleton-type bound in some cases owing to the extra conditions, it coincides with the Singleton-type bound for certain cases. Combining our constructions with known explicit good polynomials of special forms, we can get various explicit Singleton-optimal (r , δ) -LRCs with new parameters, whose code lengths are all larger than that constructed by the RS-like (r , δ) -LRCs introduced by Tamo and Barg. Note that the code length of classical RS codes and RS-like LRCs are both bounded by the field size. We explicitly construct the Singleton-optimal (r , δ) -LRCs with length n = q − 1 + δ for any positive integers r , δ ≥ 2 and (r + δ − 1) | (q − 1). We also show the existence of Singleton-optimal (r , δ) -LRCs with length q + δ over F q = F p a (a ≥ 3) provided p 2 | (r + δ − 1) , (r + δ − 1) | p a − 1 and p | δ. When δ is proportional to q , they are asymptotically longer than that constructed via elliptic curves whose length is at most q + 2 q. Besides, they allow more flexibility on the values of r and δ. [ABSTRACT FROM AUTHOR]

A locally repairable code (LRC) is a [n, k, d] linear code with length n, dimension k, minimum distance d and locality r, which means that every code symbol can be repaired by at most r other symbols. LRCs have become an important candidate in distributed storage systems due to their relatively low I/O cost. An LRC is said to be optimal if its minimum distance meets one of the Singleton-like bounds. This paper considers the optimal constructions of LRCs with locality r = 1 and r = k - 1, which involves three types: r-local LRCs, (r, δ)-LRCs and LRCs with t-availability. Specifically, we first prove that the existence of an optimal LRC with locality r = 1 is equivalent to that of an MDS code with certain parameters. Thus we can completely characterize the three types of optimal LRCs with r = 1 based on some known constructions of MDS codes. Near MDS codes is a special class of sub-optimal linear code whose minimum distance d = n - k and the i-th generalized Hamming weight achieves the generalized Singleton bound for 2 ≤ i ≤ k. For r = k - 1, we have established the connections between optimal r-local LRCs/ LRCs with t-availability and near MDS codes. Such connections can help to construct optimal LRCs with r = k - 1 from some known classes of near MDS codes.

Locally recoverable codes (LRCs) play a significant role in distributed and cloud storage systems. The key ingredient for constructing such optimal LRCs is to characterize the parity-check matrix for LRCs. In this letter based on the parity-check matrix for generalized Reed-Solomon codes we mainly present new constructions of optimal $(r,\delta )$ -locally recoverable codes with unbounded lengths in terms of the properties of the Vandermonde matrices, of which the parameters contain the known ones.

In the Distributed Storage Systems (DSSs), the encoded fraction of information is stored in a distributed fashion on different chunk servers. Recently a new paradigm of Fractional Repetition (FR) codes has been introduced, in which, encoded data information is stored on distributed servers using an encoding involving a Maximum Distance Separable (MDS) code and a Repetition code. In this work, we have considered FR codes with asymmetric parameters known as Generalized Fractional Repetition (GFR) codes. We have shown that any GFR code is equivalent to a hypergraph. Using the correspondence, the properties and the bounds of a hypergraph are directly mapped to the associated GFR code. In general, using the correspondence, the necessary and sufficient conditions for the existence of a GFR code is obtained. It is also shown that any GFR code associated with a linear hypergraph is universally good, and any locally repairable GFR code is associated with a class of non-linear hypergraph. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRCs) with (r, t)-locality have received considerable attention in recent years, since they are able to solve common problems in distributed storage systems such as repairing multiple node failures and managing hot data. Constructing LRCs with excellent parameters becomes an interesting research subject in distributed storage systems and coding theory. In this paper, we present two constructions of LRCs with information (r, t)-locality based on linear algebra and partial geometry, respectively. Both constructions generate LRCs with new parameters which are optimal with respect to the bound proposed by Rawat et al. (IEEE Trans Inf Theory 62(8):4481–4493, 2016). [ABSTRACT FROM AUTHOR]

Distributed storage systems are known to be susceptible to long response time, and higher latency leads to a reduction in customers satisfaction. An elegant solution to reduce latency in such systems is through two methods - having redundancy in contents at the storage nodes, and adding a cache close to end-users. Redundancy could be added using an erasure code because of its high resiliency with low storage overhead. It is important to quantify the performance of distributed storage systems in the presence of redundancy and caching, which is the focus of this work. This paper proposes a framework for quantifying and jointly optimizing mean and tail latency in erasure-coded storage systems with edge-caching capabilities. A novel caching policy for caching contents in erasure-coded storage systems, called time-to-live (TTLCache), is proposed. Using TTLCache policy and probabilistic server-selection techniques, bounds for mean latency and latency tail probability (LTP) are characterized. A convex combination of both metrics is optimized over the choices of probabilistic scheduling and TTLCache parameters using an efficient algorithm. In all tested cases, the experimental results show the superiority of our approach as compared to the state of the other algorithms and some competitive baselines. Implementation in a real cloud environment is further used to validate the results. [ABSTRACT FROM AUTHOR]

Distributed storage systems can provide reliable service of data storage. Lots of scenarios, such as data center, P2P network are all applications of distributed storage systems. There are mainly three storage schemes for distributed storage systems, including replication, erasure codes and regenerating codes. With the same storage space, more reliable data storage is assured by erasure codes than replication. However, replication can save more repair bandwidth (i.e., the communication cost for node repair) than erasure codes. To ensure both high reliability and low repair bandwidth, regenerating codes are intensively investigated. In practical systems, the communication between two nodes may be restricted by physical factors or economic considerations, such as transmission distance or network traffic. In this paper, we propose a novel model considering the connectivity limitations in ring networks. Each node can only connect to or communicate with its neighbors within a given range. Inspired by the concept of regenerating codes, we investigate the theoretical necessary condition for all possible storage codes. Then, a tradeoff between storage space and repair bandwidth is derived by analyzing the information flow graph of our model. Two interesting points on the tradeoff curve are further investigated, corresponding to the ring minimum-storage-regenerating (rMSR) codes, and the ring minimum-bandwidth-regenerating (rMBR) codes. Besides, two types of code constructions are presented. (i) For both rMSR and rMBR codes, we provide code constructions under exact repair models. (ii) Under functional repair models, we derive the size of the coding finite field, based on which the algorithm in can be applied to construct the corresponding codes. And finally, the superiority of our codes is validated by both theoretical and simulation results. Simulations show that our codes outperform baseline schemes, and the reduction on repair bandwidth can be up to 66% of the original data size. [ABSTRACT FROM AUTHOR]

In a Private Information Retrieval (PIR) protocol, a user can download a file from a database without revealing the identity of the file to each individual server. A PIR protocol is called $t$ -private if the identity of the file remains concealed even if $t$ of the servers collude. Graph based replication is a simple technique, which is prevalent in both theory and practice, for achieving robustness in storage systems. In this technique each file is replicated on two or more storage servers, giving rise to a (hyper-)graph structure. In this paper we study private information retrieval protocols in graph based replication systems. The main interest of this work is understanding the collusion structures which emerge in the underlying graph. Our main contribution is a 2-replication scheme which guarantees perfect privacy from acyclic sets in the graph, and guarantees partial-privacy in the presence of cycles. Furthermore, by providing an upper bound, it is shown that the PIR rate of this scheme is at most a factor of two from its optimal value for regular graphs. Lastly, we extend our results to larger replication factors and to graph-based coding, a generalization of graph based replication that induces smaller storage overhead and larger PIR rate in many cases. [ABSTRACT FROM AUTHOR]

In distributed storage systems, file access efficiency has an important impact on the real-time nature of information forensics. As a popular approach to improve file accessing efficiency, prefetching model can fetches data before it is needed according to the file access pattern, which can reduce the I/O waiting time and increase the system concurrency. However, prefetching model needs to mine the degree of association between files to ensure the accuracy of prefetching. In the massive small file situation, the sheer volume of files poses a challenge to the efficiency and accuracy of relevance mining. In this paper, we propose a massive files prefetching model based on LSTM neural network with cache transaction strategy to improve file access efficiency. Firstly, we propose a file clustering algorithm based on temporal locality and spatial locality to reduce the computational complexity. Secondly, we propose a definition of cache transaction according to files occurrence in cache instead of time-offset distance based methods to extract file block feature accurately. Lastly, we innovatively propose a file access prediction algorithm based on LSTM neural network which predict the file that have high possibility to be accessed. Experiments show that compared with the traditional LRU and the plain grouping methods, the proposed model notably increase the cache hit rate and effectively reduces the I/O wait time. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRCs) were proposed to reduce the repair degree in distributed storage systems. In particular, LRCs with availability are highly desirable for distributed storage systems, since this kind of codes provide the mechanism of local repair for code symbols and parallel reading of hot data. In this paper, we propose four types of (n, k, r, t)q LRCs from combinatorial designs. We introduce several constructions of LRCs with strict availability and some constructions of distance-optimal LRCs with information-symbol locality. Most of our constructions in this paper are over F 2 , i.e., they are suitable for implementation. [ABSTRACT FROM AUTHOR]

The problem of exact-repair regenerating codes against eavesdropping attack is studied. The eavesdropping model we consider is that the eavesdropper has the capability to observe the data involved in the repair of a subset of $\ell $ nodes. An $(n,k,d,\ell)$ secure exact-repair regenerating code is an $(n,k,d)$ exact-repair regenerating code that is secure under this eavesdropping model. It has been shown that for some parameters $(n,k,d,\ell)$ , the associated optimal storage-bandwidth tradeoff curve, which has one corner point, can be determined. The focus of this paper is on characterizing such parameters. We establish a lower bound $\hat {\ell }$ on the number of wiretap nodes, and show that this bound is tight for the case $k = d = n-1$. [ABSTRACT FROM AUTHOR]

Distributed storage systems are known to be susceptible to long tails in response time. In modern online storage systems such as Bing, Facebook, and Amazon, the long tails of the service latency are of particular concern, with 99.9th percentile response times being orders of magnitude worse than the mean. As erasure codes emerge as a popular technique to achieve high data reliability in distributed storage while attaining space efficiency, taming tail latency still remains an open problem due to the lack of mathematical models for analyzing such systems. To this end, we propose a framework for quantifying and optimizing tail latency in erasure-coded storage systems. In particular, we derive upper bounds on tail latency in closed-form for arbitrary service time distribution and heterogeneous files. Based on the model, we formulate an optimization problem to jointly minimize weighted latency tail probability of all files over the placement of files on the servers, and the choice of servers to access the requested files. The non-convex problem is solved using an efficient, alternating optimization algorithm. Further, we mathematically quantify, in closed form, the tail index, i.e., the exponent at which latency tail probability diminishes to zero, of the service latency for arbitrary erasure-coded storage, by characterizing the asymptotic behavior of latency distribution tails. We further show that probabilistic scheduling-based algorithms are (asymptotically) optimal since they are able to achieve the exact tail index. Evaluation results show significant reduction of tail latency for erasure-coded storage systems with realistic workload. Based on the offline algorithm, an online version is developed and its superiority over the state-of-the-art algorithms, e.g., join-shortest-queue (JSQ), power-of-d [Pof(d))], least-load [LL(d)], is shown. Finally, a cloud storage system is implemented in a real cloud environment to show the superiority of our approach as compared to the considered baselines. [ABSTRACT FROM AUTHOR]

In recent years, several classes of codes have been introduced to provide some fault-tolerance and guarantee system reliability in distributed storage systems, among which locally repairable codes (LRCs for short) play an important role. However, most known constructions are over large fields with sizes close to the code length, which leads to the systems being computationally expensive. Due to this, binary LRCs are of interest in practice. In this paper, we focus on binary linear LRCs with disjoint repair groups. We first derive an explicit bound for the dimension k of such codes, which can be viewed as a generalization of the bounds given in [S. Goparaju and R. Calderbank, Proceedings of the IEEE International Symposium on Information Theory, 2014, pp. 676{680; A. Wang, Z. Zhang, and D. Lin, Proceedings of the IEEE International Symposium on Information Theory, 2017, pp. 2033{2037; and A. Zeh and E. Yaakobi, Proceedings of the IEEE Information Theory Workshop, 2015, pp. 1{5]. We also give several new constructions of binary LRCs with minimum distance d = 6 based on weakly independent sets and partial spreads, which are optimal with respect to our bound. In particular, for locality r 2 f2; 3g and minimum distance d = 6, we construct optimal binary linear LRCs with disjoint repair groups for almost all possible parameters. It should be emphasized that some subclasses of these newly constructed codes also attain a general bound of binary LRCs (without the assumption of disjoint repair groups). [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRCs) are introduced in distributed storage systems due to their low repair overhead. An LRC is called optimal if its minimum distance attains the Singleton-like upper bound. Chen et al. (2018) recently studied the constructions of optimal $(r, \delta)$ -LRCs with length $n \mid (q+1)$ and $(r+\delta -1) \mid n$ , where many classes of optimal cyclic constructions were obtained. In this paper, by employing constacyclic MDS codes, we construct seven classes of optimal $(r, \delta)$ -LRCs with new parameters. After adding these new optimal LRCs via constacyclic codes, we have completely obtained all optimal $(r, \delta)$ -LRCs with length $n \mid (q+1)$ and $(r+\delta -1) \mid n$ for all possible parameters for the completeness in the coding theory. It is worth noting that the optimal constacyclic LRCs with new parameters provide more alternatives to cyclic LRCs in the practical demands of distributed storage systems, where specific values of $n$ , $k$ , $r$ , and $\delta $ are required. Moreover, constacyclic LRCs also possess the encoding and decoding efficiency as cyclic LRCs. [ABSTRACT FROM AUTHOR]

In order to improve the reliability and repair efficiency of distributed storage systems, minimum bandwidth regenerating (MBR) codes based on cyclic variable fractional repetition (VFR) codes are constructed in this thesis, which can repair failed nodes accurately. Specifically, in order to consider the imbalance of data accessed by the users, cyclic VFR codes are constructed according to that data with different heat degrees are copied in different repetition degrees. Moreover, we divide the storage nodes into groups, and construct MBR codes based on cyclic VFR codes to improve the file download speed. Performance analysis and simulation results show that, the repair locality of a single node failure is always 2 when MBR codes based on cyclic VFR codes are adopted in distributed storage systems, which is obviously superior to the traditional MBR codes. Compared with RS codes and simple regenerating codes, the proposed MBR codes based on cyclic VFR codes have lower repair locality, repair complexity and bandwidth overhead, as well as higher repair efficiency. Moreover, relative to FR codes, the MBR codes based on cyclic VFR codes can be applicable to more storage systems. [ABSTRACT FROM AUTHOR]

Internet video traffic has been rapidly increasing and is further expected to increase with the emerging 5G applications, such as higher definition videos, the IoT, and augmented/virtual reality applications. As end users consume video in massive amounts and in an increasing number of ways, the content distribution network (CDN) should be efficiently managed to improve the system efficiency. The streaming service can include multiple caching tiers, at the distributed servers and the edge routers, and efficient content management at these locations affects the quality of experience (QoE) of the end users. In this paper, we propose a model for video streaming systems, typically composed of a centralized origin server, several CDN sites, and edge-caches located closer to the end user. We comprehensively consider different systems design factors, including the limited caching space at the CDN sites, allocation of CDN for a video request, choice of different ports (or paths) from the CDN and the central storage, bandwidth allocation, the edge-cache capacity, and the caching policy. We focus on minimizing a performance metric, stall duration tail probability (SDTP), and present a novel and efficient algorithm accounting for the multiple design flexibilities. The theoretical bounds with respect to the SDTP metric are also analyzed and presented. The implementation of a virtualized cloud system managed by Openstack demonstrates that the proposed algorithms can significantly improve the SDTP metric compared with the baseline strategies. [ABSTRACT FROM AUTHOR]

In wireless distributed storage systems, storage nodes are connected by wireless channels, which are broadcast in nature. This paper exploits this unique feature to design an efficient repair mechanism, called broadcast repair, for wireless distributed storage systems in the presence of multiple-node failures. Due to the broadcast nature of wireless transmission, we advocate a new measure on repair performance called repair-transmission bandwidth. In contrast to repair bandwidth, which measures the average number of packets downloaded by a newcomer to replace a failed node, repair-transmission bandwidth measures the average number of packets transmitted by helper nodes per failed node. The storage system we considered can undergo an unlimited number of repair rounds. We obtain an upper bound on the maximum file size that can be supported by a cut analysis of a finite graph. The achievability is shown by codes constructed over a refined information flow graph, which is unbounded. In addition, the optimal storage-bandwidth tradeoff is obtained. The performance of broadcast repair is compared both analytically and numerically with that of cooperative repair, the basic repair method for wired distributed storage systems with multiple-node failures. While cooperative repair is based on the idea of allowing newcomers to exchange packets, broadcast repair is based on the idea of allowing a helper to broadcast packets to all newcomers simultaneously. We show that broadcast repair outperforms cooperative repair, offering a better tradeoff between storage efficiency and repair-transmission bandwidth. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to construct pliable fractional repetition (FR) codes that are locally recoverable for distributed storage systems (DSSs). FR codes are integral in constructing a class of distributed storage codes with exact repair by transfer. Pliable FR codes are a new type of FR codes in which both the per-node storage and repetition degree can easily be adjusted simultaneously; thus, pliable FR codes are vital for DSSs in which parameters can dynamically change over time. However, the constructions of pliable FR codes with repair locality remain unknown. In addition, the tradeoffs between the code minimum distance of an FR code and its repair locality are not fully understood. To address these problems, this paper first presents general results regarding FR codes. Subsequently, this paper presents an improved Singleton-like bound for locally recoverable FR codes under an additional requirement that each node must be part of a local structure that, upon failure, allows it to be exactly recovered by a simple download process. Moreover, this paper proposes a construction of locally recoverable FR codes that can achieve the proposed Singleton-like bound; this construction is based on bipartite graphs with a given girth. In particular, this paper also proposes a general bipartite-graph-based approach to constructing optimal pliable FR codes with and without repair localities; in this approach, a new family of bipartite graphs, called matching-feasible graphs, is introduced. Finally, this paper proposes the explicit constructions of optimal pliable FR codes by using a family of matching-feasible graphs with arbitrary large girth. Notably, in addition to attaining a Singleton-like bound for FR codes, the explicit pliable FR codes are optimal locally recoverable FR codes from two perspectives of repair locality. The explicit pliable FR codes can also be used as FR batch codes to provide load balancing in DSSs. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRCs) are a class of codes which can recover from erasures by accessing a small number of erasure-free code symbols. The objective of this letter is to present a generic construction of ${q}$ -ary cyclic LRCs via cyclotomic polynomials over the finite filed ${\text F}_{{q}}$ , where ${q}$ is any prime power. Some properties of cyclotomic polynomials are employed to determine the dimension and minimum distance of the proposed LRCs. This idea was inspired by a recent construction by Kim and No where they used a special class of cyclotomic polynomials over ${\mathbb F}_{{2}}$ to generate binary cyclic LRCs. Our construction extends the earlier one and yields new optimal or almost optimal cyclic LRCs with respect to certain bounds. [ABSTRACT FROM AUTHOR]

Distributed storage systems, built on peer-to-peer networks, can provide large-scale data storage and high data reliability by redundancy. Data backup is the process to store data into a set of redundant storage nodes. Rapid completion of such a process is very critical to maintain system performance. In traditional data backup in distributed systems based on erasure codes, star-structured scheme is used, in which each redundant block is just sent to each target storage node from the source node directly, so the storage throughput and delay are limited by the bottleneck bandwidth, due to bandwidth heterogeneity. The recent "in-network" redundancy generation scheme uses locally repairable property of self-repairing codes to speed up data backup. However, such kind of code does not own maximum distance separable property, thus does not achieve optimal storage efficiency. We still lack a fast backup scheme in distributed systems based on general erasure coding. To this end, we proposed that instead of only focusing on bandwidths between the source node and target nodes, the bandwidths between target storage nodes should be fully taken into account. In our scheme, each redundant data block is divided into some parts according to different proportions and each part of the block is sent to the target storage node via other different storage nodes. The benefit is that spare bandwidths between target storage nodes are used to reduce backup time. We further show how this process can be modeled and derive a formula about the final backup time. We can achieve minimum backup time by solution for classical quadratic programming problem. We conduct both numerical analysis and experimental study. Our experiments shows, the delay reduces 59 %, compared with common star-structured scheme. Meanwhile, the throughput is increased significantly in backup process. [ABSTRACT FROM AUTHOR]

Distributed storage systems that deploy erasure codes can provide better features such as lower storage overhead and higher data reliability. In this paper, we focus on fractional repetition (FR) codes, which are a class of storage codes characterized by the features of uncoded exact repair and minimum repair bandwidth. We study the duality of FR codes and investigate the relationship between the supported file size of an FR code and its dual code. Based on the established relationship, we derive an improved dual bound on the supported file size of FR codes. We further show that FR codes constructed from t -designs are optimal when the size of the stored file is sufficiently large. Moreover, we present the tensor product technique for combining FR codes and elaborate on the file size hierarchy of resulting codes. [ABSTRACT FROM AUTHOR]

The study of regenerating codes has advanced tremendously in recent years. However, most known constructions require large field size and, hence, may be hard to implement in practice. By restructuring a code construction by Rashmi et al., we obtain two explicit families regenerating codes. These codes approach the cut-set bound as the reconstruction degree increases and may be realized over any given finite field if the file size is large enough. Essentially, these codes constitute a constructive proof that the cut-set bound does not imply a field size restriction, unlike some known bounds for ordinary linear codes. The first construction attains the cut-set bound at the MBR point asymptotically for all parameters, whereas the second one attains the cut-set bound at the MSR point asymptotically for low-rate parameters. Even though these codes require a large file size, this restriction is trivially satisfied in most conceivable distributed storage scenarios, that are the prominent motivation for regenerating codes. [ABSTRACT FROM AUTHOR]

The report presents an analysis of Big Data storage solutions in different directions. The purpose of this paper is to introduce the technology of Big Data storage, prospects of storage technologies, for example, the software DIRAC. The DIRAC is a software framework for distributed computing. The report considers popular storage technologies and lists their limitations. The main problems are the storage of large data, the lack of quality in the processing, scalability, the lack of rapid availability, the lack of implementation of intelligent data retrieval. Experimental computing tasks demand a wide range of requirements in terms of CPU usage, data access or memory consumption and unstable profile of resource use for a certain period. The DIRAC Data Management System (DMS), together with the DIRAC Storage Management System (SMS) provides the necessary functionality to execute and control all the activities related with data.

Despite their exceptional error-correcting properties, Reed–Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth. A naive repair approach would require for the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC’16) proposed a single erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. We extend the trace collection technique to cope with two and three erasures. [ABSTRACT FROM AUTHOR]

There is high demand for storage related services supporting scientists in their research activities. Those services are expected to provide not only capacity but also features allowing for more exible and cost efficient usage. Such features include easy multiplatform data access, long term data retention, support for performance and cost differentiating of SLA restricted data access. The paper presents a policy-based SLA storage management model for distributed data storage services. The model allows for automated management of distributed data aimed at QoS provisioning with no strict resource reservation. The problem of providing users with the required QoS requirements is complex, and therefore the model implements heuristic approach for solving it. The corresponding system architecture, metrics and methods for SLA focused storage management are developed and tested in a real, nationwide environment. [ABSTRACT FROM AUTHOR]

Piggybacking is an efficient framework to reduce the repair bandwidth of distributed storage systems, especially, when the systems meet the settings–maximum distance separable (MDS), high code rate, and a small number of substripes. Through an analysis on the repair ratio of a piggybacking construction, this paper reveals that the proportion $p_{p}$ of piggybacking protected stripes is the key to significantly decrease the repair bandwidth. Based on this analysis, this paper proposes a repair efficient coding under piggybacking framework (REPB) by considering various piggybacking protected stripes and MDS only protected stripes. The repair ratio of REPB tends to 0 and is close to theoretical cut-set bound, as the proportion $p_{p}$ is no longer fixed at 1/2. Furthermore, the proposed REPB codes enjoy low computational complexity in repair operation. [ABSTRACT FROM AUTHOR]

A linear block code with dimension $k$ , length $n$ , and minimum distance $d$ is called a locally repairable code (LRC) with locality $r$ , if it can retrieve any coded symbol by at most $r$ other coded symbols. LRCs have been recently proposed and used in practice in distributed storage systems, such as Windows Azure Storage and Facebook HDFS-RAID. Theoretical bounds on the maximum locality of LRCs ( $r$ ) have been established. The average locality of an LRC ( $\overline {r}$ ) directly affects the costly repair bandwidth, disk I/O, and the number of nodes involved in the repair process of a missing data block. There is a gap in the literature studying $\overline {r}$. In this paper, we establish a lower bound on $\overline {r}$ of arbitrary $(n,k,d)$ LRCs. Furthermore, we obtain a tight lower bound on $\overline {r}$ for a practical case where the code rate $(R=({k}/{n}))$ is greater than $(1-({1}/{\sqrt {n}}))^{2}$. Finally, we design three classes of LRCs that achieve the obtained bounds on $\overline {r}$. Comparing with the existing LRCs, our proposed codes improve the average locality without sacrificing such crucial parameters as the code rate or minimum distance. [ABSTRACT FROM AUTHOR]

A distributed storage system (DSS) is one of the most vital components of a cloud computing system used for storing and sharing big data among authorized users. A typical DSS consists of ${ n}$ storage nodes each with a storage capacity of ${\alpha }$ units of data such that the entire file stored on the DSS can be recovered by accessing any ${k < n}$ nodes. The objective of this paper is to construct fractional repetition (FR) codes with applications in DSSs. FR codes are the key to constructing a class of distributed storage codes with exact repair by transfer (i.e., upon failure, a failed storage node is exactly regenerated through simple downloading). A major drawback of existing FR codes is that they are insufficiently flexible to adapt adequately to system changes in DSSs. To address this problem, this paper introduces a new type of FR codes, called pliable FR codes, in which both the per-node storage ${\alpha }$ and repetition degree ${ \rho }$ can easily and simultaneously be adjusted. In addition, this paper presents several constructions of pliable FR codes and provides a relatively comprehensive analysis of the constructed pliable FR codes, which reveals the following versatile properties of the codes: 1) the transposed codes of the constructed codes are also pliable FR codes; 2) the constructed codes attain a tight upper bound on the file size with equality at least for ${1 \le k < \min (3, k' + 1)}$ , where ${k'}$ is the smallest value of ${k}$ such that ${k \alpha - (k - 1) > \frac {n - 1}{\rho - 1}}$ ; 3) the constructed codes also meet a Singleton-like bound on the minimum distance at least for ${1 \le k < 3}$ , which demonstrates their optimality; 4) the computational complexity necessary for determining the file size or the minimum distance of the constructed codes can be greatly reduced when it is hard to exactly determine them; and 5) the constructed codes can be used as fractional repetition batch codes to provide load balancing in DSSs, for which the batch size (i.e., the number of symbols that can be read in parallel) can be exactly determined. [ABSTRACT FROM AUTHOR]

Fractional repetition (FR) codes are introduced with the aim of facilitating node repairs in distributed storage systems, i.e., they enable uncoded exact repairs at the minimum bandwidth regenerating (MBR) point. In this letter, we investigate universally good FR (UGFR) codes, which can achieve the storage capacity of MBR codes. We show that UGFR codes are optimal with respect to a bound on the reconstruction degree, which is the number of nodes required for data retrieval. We also present a construction of UGFR codes by establishing a relation with regular packings. [ABSTRACT FROM PUBLISHER]

Our daily lives are getting more and more dependent on data centers and distributed storage systems in general, whether at the business or at the personal level. With the advent of fog computing, personal mobile devices in a given geographical area may also comprise a very dynamic distributed storage system. These paradigm changes call for the urgent need of devising efficient and reliable failure recovery mechanisms in dynamic scenarios where failures become more likely and nodes join and leave the network more frequently. Redundancy schemes in distributed storage systems have become essential for providing reliability given the fact of frequent node failures. In this work, we address the problem of multiple failure recovery with dynamic scenarios using the fractional repetition code as a redundancy scheme. The fractional repetition (FR) code is a class of regenerating codes that concatenates a maximum distance separable code (MDS) with an inner fractional repetition code where data is split into several blocks then replicated and multiple replicas of each block are stored on various system nodes. We formulate the problem as an integer linear programming problem and extend it to account for three dynamic scenarios of newly arriving blocks, nodes, and variable priority blocks allocation. The contribution of this paper is four-fold: i. we generate an optimized block distribution scheme that minimizes the total system repair cost of all dependent and independent multiple node failure scenarios; ii. we address the practical scenario of having newly arriving blocks and allocate those blocks to existing nodes without any modification to the original on-node block distribution; iii. we consider new-comer nodes and generate an updated optimized block distribution; iv. we consider optimized storage and recovery of blocks with varying priority using variable fractional repetition codes. The four problems are modeled using incidence matrices and solved heuristically. We present a range of results for our proposed algorithms in several scenarios to assess the effectiveness of the solution approaches that are shown to generate results close to optimal. [ABSTRACT FROM AUTHOR]