To reduce the high computation overhead induced by erasure coding, an effective way is to convert multiplications in finite fields intoXORs. However, the existing coding libraries adopt standard binaryXORand ignore the register efficiency, which inevitably induces too many extraLOADs/STOREsbetween registers and cache/memory, contributing to the main coding latency. From the view of register efficiency, we redesign the diagram of executingXORsand propose a new coding procedure, Coding with Adaptation to Registers (CAR), which keeps the temporal parities in registers until their constructions are completed. We further propose an enhanced coding procedure, CAR+, which further reduces the number ofLOADsby leveraging multiple registers. By integrating multiple optimizations into CAR and CAR+, we implement an erasure coding library, which increases the encoding throughput by up to 203.1% compared with the state-of-the-art erasure coding libraries.

In-memory KV stores have recently been migrated from traditional monolithic servers to disaggregated memory (DM) for higher resource utilization and elasticity. These works use replication-based schemes for fault tolerance, which can be replaced with erasure coding (EC) for space efficiency. However, existing EC schemes designed in KV stores on traditional monolithic architectures encounter performance constraints when directly implemented in DM due to the challenges in EC metadata management and consistent parity updating. This article proposes MetaEC, an erasure-coded KV store on DM with high efficiency and resilience. First, for organizing KV pairs to stripes, MetaEC logically forms data chunks and leverages lazy coding to remove the accumulating and coding latency from the critical path. Second, for efficient EC metadata management, MetaEC designs EC metadata structures based on accessing features, and employs a hybrid redundancy schema with deterministic distribution to provide fault tolerance with high storage efficiency. Third, for consistent parity updating, we design a parity updating protocol based on parity logging and co-design EC metadata structures to handle concurrent conflicts by allowing only concurrent reads or writes. Experimental results show that compared with the state-of-the-art replication-based KV stores on DM, MetaEC achieves up to 53.33% latency reduction, up to 31.01% throughput improvement, and 58.17% memory consumption savings.

Erasure coding is a common redundancy scheme for tolerating failures in storage systems. Compared with replication, erasure coding saves a large amount of storage space, but incurs heavy computation overhead and, is more time consuming. In this article, we accelerate the coding speed with three techniques. First, we propose an algorithm to search coding bitmatrices with fewer 1’s from Vandermonde and Cauchy matrices, and further optimize the coding bitmatrices by greedily reducing the number of 1’s in the bitmatrices. So we can find near-optimal coding bitmatrices with the number of 1’s only up to 1% more than the lower bound. Next, we redesign the process of building pointers and reuse the pointers to access data for coding, which obtains a better tradeoff between spatial locality and computation efficiency. Finally, we smartly decompose the coding procedure of wide stripes into multiple subprocedures, to improve spatial locality and reduce the number of XORs. Based on the proposed techniques, we implement an erasure coding library, Cerasure. Extensive experiments show that Cerasure significantly improves the coding throughput. Compared with the state-of-the-art erasure coding libraries, Zerasure and SLPEC, Cerasure increases the encoding throughput by up to 200.2%.

Erasure coding is a common redundancy scheme to provide higher reliability with much lower storage overhead compared to replication. It prevents data loss due to failures but induces high repair costs. As data volumes grow exponentially, wide stripes are proposed for extreme storage savings. Wide-stripe erasure codes face the challenges of higher repair costs for single and multiple failures. Our extensive analysis shows that existing repair-efficient erasure codes, such as locally repairable codes (LRCs) and minimum storage regenerating (MSR) codes, are insufficient to meet all the requirements of wide stripes: low storage overhead, low repair cost for both single and multiple failures, and high reliability. In this article, we explore an alternative code scheme, locally repairable with zigzag code (LRZC), which combines the advantages of LRCs and zigzag codes. LRZC divides data blocks and global parity blocks into evenly sized local groups, and generates two local parity blocks by a zigzag code in each group. Under the limit of storage overhead of wide stripes, LRZC reduces the repair cost for single and multiple failures and provides higher reliability compared with existing wide-stripe codes. Experiments show that LRZC reduces the repair cost of single and multiple failures by up to 41.9% and 41.7% compared with the state-of-the-art LRCs.

Maximum Distance Separable(MDS) codes can provide the optimal storage efficiency with the same fault tolerance. From the practical considerations, the systematic and optimal update properties of codes are crucial, where the former affects the workflow of read/write operations while the latter impacts the write amplification costs in update intensive scenarios. Moreover, the repair bandwidth, subpacketization level, and finite field size are three important performance metrics to evaluate the effectiveness of codes, which impact the network traffic, I/O performance and computational complexity, respectively. However, various code constructions with the optimal update property were devised to minimize repair bandwidth with high subpacketization levels or huge finite field sizes. While other constructions that reach a good trade-off among these three performance metrics always lack the optimal update property. In this paper, to address the above challenges of constructing practical MDS codes, we presentPermutation Transformation(PT) codesthat excel in the following respects: The systematic and optimal update properties can be both guaranteed; the code reaches nearly optimal repair bandwidth when repairing any single systematic node; the subpacketization level achieves a linear scale of the fault-tolerance capacity; the required size of the finite field to ensure the MDS property is small.

Disaggregated memory (DM) separates compute and memory resources to build a huge memory pool. Erasure coding (EC) is expected to provide fault tolerance in DM with low memory cost. In DM with EC, objects are first coded in compute servers, then directly written to memory servers via high-speed networks like one-sided RDMA. However, as the one-sided RDMA latency goes down to the microsecond level, coding overhead degrades the performance in DM with EC. To enable efficient EC in DM, we thoroughly analyze the coding stack from the perspective of cache efficiency and RDMA transmission. We develop MicroEC, which optimizes the coding workflow by reusing the auxiliary coding data and coordinates the coding and RDMA transmission with an exponential pipeline, as well as carefully adjusting the coding and transmission threads to minimize the latency. We implement a prototype supporting common basic operations, such as write/read/degraded read/recovery. Experiments show that MicroEC reduces the write latency by up to 44.35% and 42.14% and achieves up to$1.80\times$and$1.73\times$write throughput, compared with the state-of-the-art DM systems with EC and 3-way replication for objects not smaller than 1 MB, respectively. For small objects, MicroEC also evidently reduces the variation of latency, e.g., it reduces the P99 latency of writing 1 KB objects by 27.81%.

Erasure coding is a common redundancy scheme for tolerating failures in storage systems. Compared with replication, erasure coding saves a large amount of storage space, but incurs heavy computation overhead and thus is more time-consuming. To this end, we design an algorithm to find a better parity coding matrix to reduce the number of XORs in coding based on Vandermonde matrices instead of Cauchy matrices. In addition, we optimize the coding process, to accelerate the computation speed of XOR and obtain a better tradeoff between spatial locality and computation efficiency. For wide stripes which becomes increasingly interesting, we propose to decompose the coding procedure into multiple subprocedures for better utilization of spatial locality. We integrate these methods into coding procedure and implement an erasure coding library, Cerasure. Extensive experiments show that Cerasure significantly improves the coding speed. Compared with the state-of-the-art erasure coding libraries, Zerasure and SLPEC, Cerasure increases the encoding throughput by up to 109.47%.

The property graph, as the most widely adopted graph data model, is utilized extensively in various graph systems. However, these systems encounter challenges with regards to high latency, particularly when it comes to graph analysis workloads. Conversely, graph analysis systems are geared towards simple graphs and have limited transactional workload support. There is a growing demand for a graph storage system that can efficiently handle both workloads on the property graph. In this paper, we propose TAG, a graph storage system that surpasses the performance of transactional graph systems and achieves comparable results to that of graph analysis systems. We introduce a novel hybrid architecture for graph storage, incorporating in-memory indexes to enhance graph topology queries and label-based pages to optimize access to the properties. Through experimental evaluations, we demonstrate the superiority of TAG over state-of-the-art graph databases.

Erasure coding becomes increasingly popular in distributed storage systems (DSSes) for providing high reliability with low storage overhead. However, traditional random data placement induces massive cross-rack traffic and severely imbalanced load during failure recovery, which degrades the recovery performance significantly. In addition, various erasure codes coexisting in a DSS exacerbates the above problems. In this paper, we propose PDL, a PBD-based Data Layout, to optimize failure recovery performance in DSSes. PDL is constructed based on Pairwise Balanced Design, a combinatorial design scheme with uniform mathematical properties, and thus presents a uniform data layout for mixed erasure codes. Then we propose rPDL, a failure recovery scheme based on PDL. rPDL reduces cross-rack traffic effectively and provides nearly balanced cross-rack traffic distribution by uniformly choosing replacement nodes and retrieving determined available blocks to recover the lost blocks. We implemented PDL and rPDL in Hadoop 3.1.1. Compared with the existing data layout and recovery scheme in HDFS, experimental results show that rPDL achieves much higher recovery throughput, 6.27x for single-node failures, 5.14x for multi-node failures and 1.48x for single-rack failures, respectively. It also reduces degraded read latency by 62.83%, and provides evidently better support to front-end applications in case of component failures.

Erasure coding (EC) has been commonly used to offer high data reliability with low storage cost. Upon failures, the lost blocks are recovered in batches. Due to the limited number of stripes, the data layout within a batch is non-uniform. Together with the random selection of source and replacement nodes for recovery tasks, the recovery workload among live nodes is skewed within a batch, which severely slows down failure recovery. To solve this problem, We present SelectiveEC, a new recovery task scheduling module that provides provable network traffic and recovery load balancing for large-scale EC-based storage systems. It relies on bipartite graphs to model the recovery traffic among live nodes. Then, it intelligently selects tasks to form batches and carefully determines where to read source blocks or to store recovered ones, using theories such as a perfect or maximum matching and$k$-regular spanning subgraph. SelectiveEC supports single-node failure and multi-node failure recovery, and can be deployed in both homogeneous and heterogeneous network environments. We implement SelectiveEC in HDFS, and evaluate its recovery performance in a local cluster of 18 nodes and AWS EC2 of 50 virtual machine instances. SelectiveEC increases the recovery throughput by up to$30.68\%$compared with state-of-the-art baselines in homogeneous network environments. It further achieves$1.32\times$recovery throughput and$1.23\times$benchmark throughput of HDFS on average in heterogeneous network environments, due to the straggler avoidance by the balanced scheduling.

In the era of explosive data growth, RAID2.0 architecture with dozens or even hundreds of disks is commonly used to provide large capacity data storage. Due to limited resources, such as memory and CPU, the reconstruction for disk failures in RAID2.0 is executed in batches. Traditional random data placement and recovery scheme make the I/O access highly skewed within a batch, which slows down the reconstruction speed.

Due to individual unreliable commodity components, failures are common in large-scale distributed storage systems. Erasure codes are widely deployed in practical storage systems to provide fault tolerance with low storage overhead. However, random data distribution (RDD), commonly used in erasure-coded storage systems, induces heavy cross-rack traffic, load imbalance, and random access, which adversely affects failure recovery. In this article, with orthogonal arrays, we define a Deterministic Data Distribution (D3) to uniformly distribute data/parity blocks among nodes, and propose an efficient failure recovery approach based on D3, which minimizes the cross-rack repair traffic against a single node failure. Thanks to the uniformity of D3, the proposed recovery approach balances the repair traffic not only among nodes within a rack but also among racks. We implement D3over Reed-Solomon codes and Locally Repairable Codes in Hadoop Distributed File System (HDFS) with a cluster of 28 machines. Compared with RDD, our experiments show that D3 significantly speeds up the failure recovery up to 2.49 times for RS codes and 1.38 times for LRCs. Moreover, D3supports front-end applications better than RDD in both of normal and recovery states.

The increasing capacity of SSDs requires a large amount of built-in DRAM to hold the mapping information of logical-to-physical address translation. Due to the limited size of DRAM, existing FTL schemes selectively keep some active mapping entries in a Cached Mapping Table (CMT) in DRAM, while storing the entire mapping table on flash. To improve the CMT hit ratio with limited cache space on SSDs, in this paper, we propose a novel FTL, a hot-clusterity FTL (HCFTL) that clusters mapping entries recently evicted from the cache into dynamic translation pages (DTPs). Given the temporal localities that those hot entries are likely to be visited in near future, loading DTPs will increase the CMT hit ratio and thus improve the FTL performance. Furthermore, we introduce an index structure to speedup the lookup of mapping entries in DTPs. Our experiments show that HCFTL can improve the CMT hit ratio by up to 41.1% and decrease the system response time by up to 33.3%, compared to state-of-the-art FTL schemes.

The Sparse Vector Technique (SVT) is a fundamental technique for satisfying differential privacy and has the unique quality that one can output some query answers without apparently paying any privacy cost. SVT has been used in both the interactive setting, where one tries to answer a sequence of queries that are not known ahead of the time, and in the non-interactive setting, where all queries are known. Because of the potential savings on privacy budget, many variants for SVT have been proposed and employed in privacy-preserving data mining and publishing. However, most variants of SVT are actually not private. In this paper, we analyze these errors and identify the misunderstandings that likely contribute to them. We also propose a new version of SVT that provides better utility, and introduce an effective technique to improve the performance of SVT. These enhancements can be applied to improve utility in the interactive setting. Through both analytical and experimental comparisons, we show that, in the non-interactive setting (but not the interactive setting), the SVT technique is unnecessary, as it can be replaced by the Exponential Mechanism (EM) with better accuracy.

k -means clustering is a widely used clustering analysis technique in machine learning. In this article, we study the problem of differentially private k -means clustering. Several state-of-the-art methods follow the single-workload approach, which adapts an existing machine-learning algorithm by making each step private. However, most of them do not have satisfactory empirical performance. In this work, we develop techniques to analyze the empirical error behaviors of one of the state-of-the-art single-workload approaches, DPLloyd, which is a differentially private version of the Lloyd algorithm for k >-means clustering. Based on the analysis, we propose an improvement of DPLloyd. We also propose a new algorithm for k -means clustering from the perspective of the noninteractive approach, which publishes a synopsis of the input dataset and then runs k -means on synthetic data generated from the synopsis. We denote this approach by EUGkM. After analyzing the empirical error behaviors of EUGkM, we further propose a hybrid approach that combines our DPLloyd improvement and EUGkM. Results from extensive and systematic experiments support our analysis and demonstrate the effectiveness of the DPLloyd improvement, EUGkM, and the hybrid approach.

Graph data publishing under node-differential privacy (node-DP) is challenging due to the huge sensitivity of queries. However, since a node in graph data oftentimes represents a person, node-DP is necessary to achieve personal data protection. In this paper, we investigate the problem of publishing the degree distribution of a graph under node-DP by exploring the projection approach to reduce the sensitivity. We propose two approaches based on aggregation and cumulative histogram to publish the degree distribution. The experiments demonstrate that our approaches greatly reduce the error of approximating the true degree distribution and have significant improvement over existing works. We also present the introspective analysis for understanding the factors of publishing the degree distribution with node-DP.