By decoupling compute and memory resources into independent pools that are provisioned and managed separately, disaggregated memory (DM) is promising to break the scaling constraints for memory systems and improve resource utilization. However, it also comes with a new challenge to design a high-performance hashing index to manage the vast memory pool with weak computing power. In this paper, we reconsider this problem and find that existing hashing indexes for DM still experience two fundamental yet unresolved limitations: (i) amplifying traffic under high insertion concurrency, and (ii) introducing significantly high insertion latency, stemming mainly from the directory synchronization and item relocation in resizing process. We resolve the above limitations by designing Pulse, a finegrained hierarchical hashing index for DM. Pulse comprises the following three design primitives. It proposes a multi-level index structure, which breaks the conventional flat directory into multiple sub-directories that are organized hierarchically, achieving fine-grained directory synchronization. Pulse also maintains a small portion of hashed keys in the memory pool, which aids in item relocation during resizing, thereby reducing resizing traffic and promising system stability. Pulse finally exploits operation parallelism by tailoring the doorbell batching mechanism with selective signaling. We conduct extensive experiments using a variety of benchmarks, showing that Pulse can improve$3.46 \times$of the throughput and reduce 76.3% of the tail latency compared to state-of-the-art hashing indexes.

Memory failures in large-scale production environments pose critical threats to system reliability and service availability. While existing studies have conducted in-depth analyses of the temporal and spatial correlations of memory errors, differences in characteristics across architectures remain largely unexplored. To uncover these overlooked correlations, this paper conducts an extensive analysis of over 130,000 DDR4 DIMMs collected from large-scale heterogeneous production clusters over a nine-month period. Through systematic spatial and temporal analysis across two Intel x86 architectures and four major DRAM vendors, we uncover five new findings and propose a novel twostage training strategy. This strategy addresses sample quality issues by applying temporal weighting to positive samples and adaptive reweighting to negative samples. It also incorporates comprehensive multi-dimensional feature engineering, covering static, spatial, temporal, and micro-level characteristics. Finally, it integrates dual-driven sampling strategies and adaptive prediction timing to balance prediction accuracy and operational efficiency. Extensive evaluation shows that our CatBoost-based model achieves F1-scores of 49.9% on Intel x86v5 and 57.6% on Intel x86v6, substantially outperforming existing methods. This cross-architecture validation demonstrates the robustness and generalization of our approach across different hardware platforms. To the best of our knowledge, our work presents the first large-scale cross-architecture analysis of memory error patterns and provides new insights for production-scale memory failure prediction systems.

Erasure-coded storage systems adopt multiple redundancy levels to balance reliability and storage efficiency under changing workloads. However, transitioning data across different redundancy configurations incurs high network overhead due to data relocation and parity recomputation, especially under successive transitions. Existing approaches are typically optimized for fixed parameters and lack flexibility and scalability. This article presents FlexRT , a flexible and efficient redundancy transitioning framework for erasure-coded systems. FlexRT employs a linear-hashing–based stripe placement that decouples stripe layout from coding parameters, enabling zero data relocation across successive transitions. To minimize parity update overhead, FlexRT binds encoding coefficients to physical nodes instead of logical stripe positions, allowing parity to be incrementally updated even when data blocks are reorganized. In addition, a greedy sub-stripe decomposition and matching algorithm maximizes parity reuse and reduces the amount of data involved in recomputation, transforming redundancy transitioning into an efficient split-and-merge process. We implement FlexRT in a C++ prototype and evaluate it through large-scale simulations and Alibaba Cloud experiments. Results show that FlexRT reduces transitioning traffic by 86.0%–94.1% and shortens transition time by 79.4%–89.2% compared with state-of-the-art schemes, while completely eliminating data relocation.

Modern data-intensive applications increasingly demand efficient and scalable file systems that can operate across distributed and cross-domain environments. However, existing file systems are inefficient in metadata management, synchronization efficiency, and system scalability under high-concurrency and metadata-intensive workloads in cross-domain environments. To address these challenges, this article introduces CrossFS (CFS), a cross-domain distributed file system that enhances consistency guarantees and metadata indexing. Specifically, CFS leverages conflict-free replicated data types (CRDTs) to synchronize metadata, achieving strong eventual consistency with minimal synchronization overhead, even across network partitions. Furthermore, CFS employs a Hybrid Tree indexing structure, tailored for distributed environments, which optimizes metadata operations by reducing query latency by up to 33.4% and write amplification by 30.7%. Additionally, CFS achieves adaptive caching strategies and a hybrid synchronization model that effectively balances consistency latency with data availability. Extensive evaluations show that CFS outperforms CephFS and GlusterFS, achieving up to 33.9% higher metadata throughput, 36% lower latency, and 42% better data operation efficiency.

Erasure coding plays a crucial role in distributed storage systems to provide fault tolerance at a low storage cost. Conventional erasure coding schemes determine data placement based on stripes. However, placing data into stripes can incur non-negligible performance overheads that will manifest in emerging fast in-memory storage systems, making conventional erasure coding schemes suboptimal in such scenarios. Aiming to eliminate such overheads, we present Nos , a stripeless placement scheme for erasure-coded distributed in-memory storage. It lets each node independently replicate data to other nodes and encode received data replicas into parities with XOR. Thus, it avoids the overheads caused by stripes. To enable failure recovery, Nos uses a combinatoric structure called symmetric balanced incomplete block design (SBIBD) to decide primary-to-backup node affinities during replication. Atop Nos , we further build Nostor , a distributed in-memory key-value store. We also achieve high availability and efficient foreground serving simultaneously with Hotness-aware Two-phase Reconstruction ( HR ). Evaluations demonstrate that Nostor achieves 1.61× to 2.60× throughputs compared to Cocytus , PQ , and Split with similar or lower latencies than these stripe-based erasure coding baselines. Equipped with HR , Nostor + HR also achieves 46.7% P999 foreground latency reduction during node repair.

KVM is the dominant VM hypervisor on Linux, and relies on QEMU to realize the backends of the virtio family of devices such as virtio-blk. However, KVM/QEMU-based paravirtualization prolongs the guest I/O path with multiple context switches. As fast NVMe storage devices have been widely used, the software overhead becomes non-negligible. To shorten the I/O path, virtio-blk’s variations, vhost-kernel-blk and vhost-user-blk, respectively perform all guest I/O processing in kernel and user spaces. Unfortunately, they essentially forsake the collaboration between KVM and QEMU, sacrifice important QEMU features including live migration, snapshots, and flexible image format support. This article presents EXO, an extension of virtio-blk for efficient KVM/QEMU-based storage paravirtualization. The insight is that no matter how complex the QEMU backend’s processing is, to handle a guest I/O request, the host storage stack only needs to know the request’s guest-to-host address mapping. Therefore, we preserve the original slow I/O path of virtio-blk as a fallback, and leverage eBPF to introduce an in-kernel fast path that directly queries the address mapping without switching to the user-space backend processing. Extensive evaluation shows that EXO achieves similar or even higher performance compared to the variations (vhost-kernel-blk/vhost-user-blk) of virtio-blk, while preserving virtio-blk’s flexibility, safety, and compatibility.

High-bandwidth memory (HBM) is regarded as a promising technology for fundamentally overcoming the memory wall. It stacks up multiple DRAM dies vertically to dramatically improve the memory access bandwidth. However, this architecture also comes with more severe reliability issues, since HBM not only inherits error patterns of the conventional DRAM, but also introduces new error causes. In this article, we conduct the first systematical study on HBM errors, which cover over 460 million error events collected from 19 data centers and span over two years of deployment under a variety of services. Through error analyses and methodology validations, we confirm that the HBM exhibits different error patterns from conventional DRAM, in terms of spatial locality, temporal correlation, and sensor metrics which make empirical prediction models for DRAM error prediction ineffective for HBM. We design and implement Calchas , a hierarchical failure prediction framework for HBM based on our findings, which integrate spatial, temporal, and sensor information from various device levels to predict upcoming failures. The results demonstrate the feasibility of failure prediction across hierarchical levels.

Non-volatile memory (NVM) opens up new opportunities to resolve scaling restrictions of main memory, yet it is still hindered by the write disturbance (WD) problem. The WD problem mistakenly transforms the values of NVM cells, hence seriously deteriorating memory reliability and downgrading access performance. Existing studies mainly mitigate the WD problem via encoding WD-prone data patterns under in-place updates, yet we find that when turning to out-of-place updates, they can gain the potential to reduce more WD errors. We present LearnWD, an approach that mitigates the WD problem in NVM via coupling machine learning with out-of-place updates. LearnWD first employs clustering algorithms to classify the stale data based on the error proneness. To perform a write operation, LearnWD carefully examines the aggressivity of new data and the error proneness of stale data, so as to speculatively minimize the resulting WD errors. We conduct extensive experiments using 15 real-world datasets with different data types, showing that LearnWD can assist a variety of data encoding schemes to further reduce 19.5% of WD errors, shorten 10.1% of write latency, and extend 22.2% of write endurance.

Fail-slow is a failure mode that exists in various components such as disks, SSDs, CPUs, memory, and networks, manifested as decreased performance but not causing crashes. We investigated the manifestation of fail-slow in HBM systems and proposed a fault detection framework based on a light regression model. It can detect potential fail-slow faults while HBM devices are undergoing factory testing. In our small-scale simulation tests, we found a fail-slow phenomenon in one single HBM device. In addition, We assemble a large-scale HBM log dataset from our production traces, based on which we provide root cause analysis on fail-slow HBM devices covering a variety of ill-implemented scheduling, hardware defects, and environmental factors. We have released the dataset to the public for further study.

Erasure coding provides fault tolerance in a storage-efficient manner, yet it introduces a high repair penalty. We uncover via trace-driven experiments that the substantial repair traffic in erasure coding is prone to entangling with the foreground traffic, thereby slowing down repair progress and downgrading service quality. We present ChameleonEC, a general mechanism that can assist a variety of erasure codes in realizing low-interference repair. ChameleonEC comprises the following design techniques: (i) repair task assignment, which decomposes a repair plan into multiple repair tasks and makes them coexist harmoniously with the foreground traffic, so as to saturate unoccupied bandwidth and avoid bandwidth contentions; (ii) repair path establishment, which orchestrates elastic transmission routings over the dispatched repair tasks to instruct the repair; and (iii) straggler-aware re-scheduling, which timely re-tunes task transmissions and repair plans to bypass unexpected stragglers emerging in repair. We conduct extensive experiments on Amazon EC2, showing that ChameleonEC can accelerate the repair by 4.9–498.2% for various erasure codes under different real-world traces. ChameleonEC can also speed up the repair process by 25.4–73.5% under the storage-bottlenecked scenarios.

In-memory key-value (KV) caching bridges the performance gap between high-performance networks and disk devices. However, prior in-memory KV caching systems either consider large objects or introduce additional memory overhead. In this paper, we conduct a systematic analysis over 56 production traces, and make three observations: (i) small objects dominate the traces and data accesses are highly skewed; (ii) the hotness of objects keeps stable across days; and (iii) the multi-get operation that retrieves multiple objects from the same node incurs much shorter tail latency than purely using the single-get operation.

GPU Direct Storage (GDS) plays a vital role in GPU-based training and inference systems, leveraging Peer-to-Peer Direct Memory Access (P2P-DMA) to establish a direct data transfer path between the GPU and the storage device. The direct I/O path reduces GPU storage access latency and CPU overhead, thus improving the efficiency of data transfer. Currently, however, GDS employs a phony buffer in the host memory to interact with the Linux kernel, which results in suboptimal I/O performance, extra resource consumption, and high deployment complexity.

Persistent memory (PMem) brings new design considerations in realizing high-performance and scalable hashing indexes. We uncover that existing hashing indexes for PMem still suffer from traffic amplification and memory inefficiency. We present MetoHash, a memory-efficient and traffic-optimized hashing index on hybrid PMem-DRAM memories. MetoHash proposes a three-layer index structure spanning across CPU caches, DRAM, and PMem for data management. It aggregates the incoming key-value items in CPU caches for fast inserts, which are then arranged in DRAM and flushed to PMem, to eliminate traffic amplification. MetoHash also uses fingerprinting to reduce unnecessary probings over PMem and removes duplicate items during bucket relocations. We implement MetoHash on PMem with persistent and volatile CPU caches, and show that compared to state-of-the-art hashing indexes for PMem, MetoHash improves the throughput by 86.1–257.6% under various workloads.

Erasure coding is an effective technique for guaranteeing data reliability for storage systems, yet it incurs a high repair penalty with amplified repair traffic. The repair becomes more intricate in clustered storage systems with the bandwidth diversity property. We present TPRepair , a T ree-based P ipelined Repair approach, aiming to expedite the overall repair process with the tailored pipelined repair procedure. TPRepair first prioritizes selecting racks with the current minimum load to participate in the repair process. It subsequently formulates tree-based links, tailored to align seamlessly with the pipelined repair procedure. TPRepair further designs an optimization algorithm to reduce the bottleneck load when repairing multiple chunks. Large-scale simulations demonstrate that TPRepair can increase 13.8%–41.3% of the balance ratio without amplifying cross-rack traffic. Meanwhile, Alibaba Cloud ECS experiments indicate that TPRepair can increase repair throughput by 11.3% to 72.9%.

Erasure coding has been extensively deployed in today’s commodity HPC systems against unexpected failures. To adapt to the varying access characteristics and reliability demands, storage clusters have to perform redundancy transitioning via tuning the coding parameters, which unfortunately gives rise to substantial transitioning traffic. We present ElasticEC, a fast and elastic redundancy transitioning approach for erasure-coded clusters. ElasticEC first minimizes the transitioning traffic via proposing a relocation-aware stripe reorganization mechanism and a collecting-and-encoding algorithm. It further heuristically balances the transitioning traffic across nodes. We implement ElasticEC in Hadoop HDFS and conduct extensive experiments on a real-world cloud storage cluster, showing that ElasticEC can reduce 71.1-92.6% of the transitioning traffic and shorten 65.9-90.7% of the transitioning time.

Erasure coding is a known redundancy technique that has been popularly deployed in modern storage systems to protect against failures. By introducing a small portion of coded redundancy into data storage, erasure coding is shown to provide higher reliability guarantees than replication under the same storage overhead. Despite its storage efficiency, erasure coding incurs high-performance overhead in repair and updates, and its reliability also depends on the amount of redundancy. How to resolve the tensions among storage efficiency, performance, and reliability has been the major research direction in the literature for decades. In this article, we present an in-depth survey of the past, present, and future of erasure coding in storage systems. We conduct our survey from a systems perspective, with an emphasis on how erasure coding is deployed in practical storage systems. Specifically, we first review the use of erasure coding in storage systems from both academia and industry and state the challenges of deploying erasure coding in practice. We then review the topics of erasure coding in three aspects: (i) new erasure code constructions, (ii) algorithmic techniques for efficient erasure coding operations, and (iii) erasure coding for emerging architectures. Finally, we provide future research directions for erasure coding.

This paper presents Zoned UFS (ZUFS), an innovative approach to address the inherent challenges in traditional Universal Flash Storage (UFS) systems in mobile devices. ZUFS integrates Zoned Namespaces (ZNS) with the UFS framework, aiming to optimize storage efficiency, reduce latency variations, and enhance endurance. We introduced key innovations, including a dual data path design and a host-based Flash Translation Layer (FTL), specifically designed to reduce overprovisioning and address the Write Amplification Factor (WAF) issues common in Triple-Level Cell (TLC) NAND technology. Through comprehensive experiments, ZUFS demonstrates significant improvements in storage performance, including reduced tail latency and better capacity utilization, compared to conventional UFS-based systems. The findings indicate that ZUFS not only offers a viable solution to current storage limitations in mobile platforms but also sets a new direction for future advancements in mobile storage technology.

Non-volatile memory (NVM) opens up new opportunities to resolve scaling restrictions of main memory, yet it is still hindered by the write disturbance (WD) problem. The WD problem mistakenly transforms the values of NVM cells, hence seriously deteriorating memory reliability and downgrading access performance. Existing studies mainly mitigate the WD problem via encoding WD-prone data patterns under in-place updates, yet we find that when turning to out-of-place updates, they can gain the potential to reduce more WD errors. We present LearnWD, an approach that mitigates the WD problem in NVM via coupling machine learning with out-of-place updates. LearnWD first employs clustering algorithms to classify the stale data based on the error proneness. To perform a write operation, LearnWD carefully examines the aggressivity of new data and the error proneness of stale data, so as to speculatively minimize the resulting WD errors. We conduct extensive experiments using 15 real-world data sets with different data types, showing that LearnWD can assist a variety of data encoding schemes to further reduce 20.1% of WD errors, shorten 11.0% of write latency, and extend 21.9% of write endurance.

With the development of NAND flash memories’ bit density and stacking technologies, while storage capacity keeps increasing, the issue of reliability becomes increasingly prominent. Low-density parity check (LDPC) code, as a robust error-correcting code, is extensively employed in flash memory. However, when the RBER is prohibitively high, LDPC decoding would introduce long latency. To study how LDPC performs on the latest 3D NAND flash memory, we conduct a comprehensive analysis of LDPC decoding performance using both the theoretically derived threshold voltage distribution model obtained through modeling (Modeling-based method) and the actual voltage distribution collected from on-chip data through testing (Ideal case). Based on LDPC decoding results under various interference conditions, we summarize four findings that can help us gain a better understanding of the characteristics of LDPC decoding in 3D NAND flash memory. Following our characterization, we identify the differences in LDPC decoding performance between the Modeling-based method and the Ideal case. Due to the accuracy of initial probability information, the threshold voltage distribution derived through modeling deviates by certain degrees from the actual threshold voltage distribution. This leads to a performance gap between using the threshold voltage distribution derived from the Modeling-based method and the actual distribution. By observing the abnormal behaviors in the decoding with the Modeling-based method, we introduce an Offsetted Read Voltage (ΔRV) method for optimizing LDPC decoding performance by offsetting the reading voltage in each layer of a flash block. The evaluation results show that our ΔRV method enhances the decoding performance of LDPC on the Modeling-based method by reducing the total number of sensing levels needed for LDPC decoding by 0.67% to 18.92% for different interference conditions on average, under the P/E cycles from 3,000 to 7,000.

Erasure coding has been demonstrated as a storage-efficient means against failures, yet its tunability remains a challenging issue in data centers, which is prone to induce substantial cross-cluster traffic. In this article, we presentClusterRT, a cluster-aware redundancy transitioning approach that can dynamically tailor the redundancy degree of erasure coding in data centers.ClusterRTformulates the data relocation as the maximum flow problem to reduce cross-cluster data transfers. It then designs a parity-coordinated update algorithm, which gathers the parity chunks within the same cluster and leverages encoding dependency to further decrease the cross-cluster update traffic.ClusterRTfinally rotates the parity chunks to balance the cross-cluster transitioning traffic across the data center. Large-scale simulation and Alibaba Cloud ECS experiments show thatClusterRTreduces 94.0% to 96.2% of transitioning traffic and reduces 70.4% to 88.4% of transitioning time.

The write disturbance (WD) problem is becoming increasingly severe in PCM due to the continuous scaling down of memory technology. Previous studies have attempted to transform WD-vulnerable data patterns of the new data to alleviate the WD problem. However, through a wide spectrum of real-world benchmarks, we have discovered that simply transforming WD-vulnerable data patterns does not proportionally reduce (or may even increase) WD errors. To address this issue, we present ResEnc, a RESET-aware data encoding scheme that reduces RESET operations to mitigate the WD problem in both wordlines and bitlines for PCM. It dynamically establishes a mask word for each block for data encoding and adaptively selects an appropriate encoding granularity based on the diverse write patterns. ResEnc finally reassigns the mask words of unchanged blocks to changed blocks for exploring a further reduction of WD errors. Extensive experiments show that ResEnc can reduce 16.8-87.0% of WD errors, shorten 5.6-39.6% of write latency, and save 7.0-43.1% of write energy for PCM.

Vehicular edge computing (VEC) enables vehicles to perform computation-intensive and delay-sensitive tasks through task offloading. Previous works either focused on task offloading based on vehicle-to-infrastructure (V2I) mode or assumed the existence of sufficient spectrum resources. However, given the exponential increase in the number of vehicles, it is essential to explore the influence of both spectrum scarcity and inter-vehicle cooperation on VEC network performance. In this paper, we investigate a joint spectrum sharing and task offloading scheme to minimize the total completion delay of tasks. Differing from previous works, our scheme incorporates task offloading based on vehicle-to-vehicle (V2V) and V2I modes while enabling V2V links to share the uplink spectrum of V2I links. To solve the formulated non-convex mixed-integer nonlinear programming problem, we propose a distributed and iterative algorithm based on the coalition formation game (CFG). Specifically, we formulate spectrum sharing and task offloading problems as many-to-one matching games with externalities and obtain the sub-channel allocation and server selection policies using the CFG approach, whose stability and convergence are analyzed. On this basis, power control and offloading ratio policies are derived using dual decomposition and quadratically constrained quadratic programming, respectively. Numerical results show that the proposed scheme reduces the total completion delay by an average of$65.31\%$,$51.22\%$, and$29.97\%$, respectively, compared to three baseline schemes under varying numbers of task vehicles.

Modern distributed key-value (KV) stores increasingly adopt erasure coding to reliably store data. To adapt to the changing demands on access performance and reliability requirements, distributed KV stores perform redundancy transitioning by tuning the redundancy schemes with different coding parameters. However, redundancy transitioning incurs extensive network I/Os, which impair the performance of distributed KV stores. We propose a new family of erasure codes, called Elastic Reed-Solomon (ERS) codes, whose primary goal is to mitigate network I/Os in redundancy transitioning. ERS codes eliminate data block relocation, while limiting network I/Os for parity block updates via the new co-design of encoding matrix construction and data placement. ERS codes achieve such gains in both forward and backward transitioning scenarios. We realize ERS codes in a distributed KV store prototype based on Memcached, and show via testbed experiments in both local and cloud environments that ERS codes significantly reduce the latency of redundancy transitioning compared with state-of-the-arts.

As the data volume continues to grow exponentially, there is an increasing demand for large storage system capacity. Data compression techniques effectively reduce the volume of written data, enhancing space efficiency. As a result, many modern SSDs have already incorporated data compression capabilities. However, data compression introduces additional processing overhead in critical I/O paths, potentially affecting system performance. Currently, most compression solutions in flash-based storage systems employ fixed compression algorithms for all incoming data without leveraging differences among various data access patterns. This leads to sub-optimal compression efficiency. This article proposes a data-type-aware Flash Translation Layer (DAFTL) scheme to maximize space efficiency without compromising system performance. First, we propose an I/O behavior prediction method to forecast future access on specific data. Then, DAFTL matches data types with distinct I/O behaviors to compression algorithms of varying intensities, achieving an optimal balance between performance and space efficiency. Specifically, it employs higher-intensity compression algorithms for less frequently accessed data to maximize space efficiency. For frequently accessed data, it utilizes lower-intensity but faster compression algorithms to maintain system performance. Finally, an improved compact compression method is proposed to effectively eliminate page fragmentation and further enhance space efficiency. Extensive evaluations using a variety of real-world workloads, as well as the workloads with real data we collected on our platforms, demonstrate that DAFTL achieves more data reductions than other approaches. When compared to the state-of-the-art compression schemes, DAFTL reduces the total number of pages written to the SSD by an average of 8%, 21.3%, and 25.6% for data with high, medium, and low compressibility, respectively. In the case of workloads with real data, DAFTL achieves an average reduction of 10.4% in the total number of pages written to SSD. Furthermore, DAFTL exhibits comparable or even improved read and write performance compared to other solutions.

By providing non-volatility with DRAM-comparable performance, the emerging persistent memory (PMem) is propelling new key-value (KV) store designs. The recently released Intel Optane DC PMem now shifts the persistent boundary from memory up to CPU caches, which further eliminates the needs of cacheline flush instructions used in extensive KV stores. However, we uncover via testbed experiments that this change can even degrade the performance of existing KV stores once directly deploying them atop the new generation of the Optane PMem, stemming mainly from the mismatch of access granularities and heavy software designs.In this paper, we present CacheKV, the first KV store built atop persistent CPU caches. CacheKV allocates per-core sub-MemTable in CPU caches with a lazy index update mechanism, so as to fast absorb incoming writes. It then proposes a copy-based flush mechanism to convert small-sized cacheline evictions into large-sized flushes to suppress the write amplification. CacheKV finally accelerates read operations via periodically compacting the sub-skiplists. Extensive testbed experiments show that CacheKV improves the write throughput by 19.5× on average in the write-dominated environment without compromising the read performance, when compared to the state-of-the-art KV stores for the PMem.

Erasure coding has been extensively deployed in today's data centers to tackle prevalent failures, yet it is prone to substantial cross-rack traffic for parity updates. In this article, we propose a new rack-coordinated update mechanism to suppress the cross-rack update traffic, which comprises two successive phases: a delta-collecting phase that collects data delta chunks, and another selective parity update phase that renews the parity chunks based on the update pattern and parity layout. We further design${\sf RackCU}$, an optimal rack-coordinated update solution that achieves the theoretical lower bound of the cross-rack update traffic. We also perform reliability analysis, demonstrating that${\sf RackCU}$can attain a lower data loss probability via shortening the update procedure. We conduct extensive evaluations, in terms of large-scale simulation and real-world data center experiments. We show that${\sf RackCU}$can reduce 16.5-77.1% of the cross-rack update traffic and hence improve 24.9-772.0% of the update throughput.

We explore machine learning for accurately predicting imminent disk failures and hence providing proactive fault tolerance for modern large-scale storage systems. Current disk failure prediction approaches are mostly offline and assume that the disk logs required for training learning models are available a priori. However, disk logs are often continuously generated as an evolving data stream, in which the statistical patterns vary over time (also known as concept drift). Such a challenge motivates the need of online techniques that perform training and prediction on the incoming stream of disk logs in real time, while being adaptive to concept drift. We first measure and demonstrate the existence of concept drift on various disk models in production. Motivated by our study, we designStreamDFP, a general stream mining framework for disk failure prediction with concept-drift adaptation based on three key techniques, namely online labeling, concept-drift-aware training, and general prediction, with a primary objective of supporting various machine learning algorithms. We extendStreamDFPto support online transfer learning for minority disk models with concept-drift adaptation. Our evaluation shows thatStreamDFPimproves the prediction accuracy significantly compared to without concept-drift adaptation under various settings, and achieves reasonably high stream processing performance.

More and more data are stored in cloud storage, which brings two major challenges. First, the modified files in the cloud should be quickly synchronized to ensure data consistency, e.g., delta synchronization (sync) achieves efficient cloud sync by synchronizing only the updated part of the file. Second, the huge data in the cloud needs to be deduplicated and encrypted, e.g., Message-Locked Encryption (MLE) implements data deduplication by encrypting the content among different users. However, when combined, a few updates in the content can cause large sync traffic amplification for both keys and ciphertext in the MLE-based cloud storage, significantly degrading the cloud sync efficiency. A feature-based encryption sync scheme, FeatureSync, is proposed to address the delta amplification problem. However, with further improvement of the network bandwidth, the performance of FeatureSync stagnates. In our preliminary experimental evaluations, we find that the bottleneck of the computational overhead in the high-bandwidth network environments is the main bottleneck in FeatureSync. In this article, we propose an enhanced feature-based encryption sync scheme FASTSync to optimize the performance of FeatureSync in high-bandwidth network environments. The performance evaluations on a lightweight prototype implementation of FASTSync show that FASTSync reduces the cloud sync time by 70.3% and the encryption time by 37.3%, on average, compared with FeatureSync.

3D flash memory relaxes the scaling constraints but unfortunately arouses the tedious garbage collection (GC) problem. We identify via an in-depth analysis that the root cause is the intra-channel relocation in conventional GC operations. We present ParaGC, an approach that strives to speed up the GC process via fully exploiting the inter-channel parallelism of 3D flash memory. ParaGC builds on two elementary designs: (i) relocation arrangement, which carefully determines the relocation traffic that each channel affords; and (ii) page assignment, which dispatches pages based on the access characteristic and the channel busyness. We implement ParaGC and conduct extensive experiments with ten real-world traces, showing that ParaGC can reduce 20.2-41.3% of the read latency, 24.3-38.8% of the write latency, and 51.5-75.8% of the GC latency.

For Internet and cloud computing service providers, running massive geo-distributed data centers incurs prodigious electricity cost and water consumption as well as carbon emission rooted in electricity generation. Thus, it is critical significant for providers to lower down the operation cost of data centers. In this article, we investigate the problem of energy management for geo-distributed data centers with renewable resources and energy storages. We aim to minimize the long-term operation cost including electricity cost, water consumption, and carbon emission by leveraging the spatiotemporal diversity of these system states. To this end, we first formulate the cost minimization problem as a stochastic optimization problem, then we adopt the Lyapunov optimization technique to design a close-to-optimal online algorithm which only needs the current system information and achieves a delicate tradeoff between system cost and performance of delay tolerant workloads. To reduce the computational complexity and unnecessary communication, we further propose a distributed algorithm based on the distributed computing framework alternating direction method of multipliers (ADMM), which enables each data center to make their own control decisions. Based on the real-world traces and extensive simulations, we demonstrate the effectiveness of our proposed algorithms.

In this paper, we consider an online decision problem, where a decision maker has an option to buy a discount plan for his/her regular expenses. The discount plan costs an immediate upfront charge plus a commitment charge per time slot. Upon expiration, the discount period can be extended if the decision maker continues paying the commitment charge, or be canceled if he or she decides not to pay the commitment charge anymore. We investigate online algorithms for the decision maker to decide when to buy the discount plan and when to cancel it without the knowledge of his/her future expenses, aiming at minimizing the overall cost. The problem is an extension of the classic Bahncard Problem, which is applicable for a wide range of online decision scenarios. We propose a novel deterministic online algorithm which can achieve a closed-form competitive ratio upper bounded by 4. We further propose a randomized online algorithm with a smaller competitive ratio and two variants tailored for average-case inputs and time-varying parameters, respectively. Lastly, we evaluate our algorithms against state-of-the-art online benchmark algorithms in two real-world scenarios.

Erasure coding offers a storage-efficient redundancy mechanism for maintaining data availability guarantees in large-scale storage clusters, yet it also incurs high performance overhead in failure repair. Recent developments in accurate disk failure prediction allow soon-to-fail (STF) nodes to be repaired in advance, thereby opening new opportunities for accelerating failure repair in erasure-coded storage. To this end, we present a fast proactive repair solution called${{\sf FastPR}}$, which carefully couples two repair methods, namely migration (i.e., relocating the chunks of an STF node) and reconstruction (i.e., decoding the chunks of an STF node through erasure coding), so as to fully parallelize the repair operation across the storage cluster.${{\sf FastPR}}$solves a bipartite maximum matching problem and schedules both migration and reconstruction in a parallel fashion. We show that${{\sf FastPR}}$significantly reduces the repair time over the baseline repair approaches for both Reed-Solomon codes and Azure's Local Reconstruction Codes via mathematical analysis, large-scale simulation, and Amazon EC2 experiments.

How to improve the repair performance of erasure-coded storage is a critical issue for maintaining high reliability of modern large-scale storage systems. Locally repairable codes (LRC) are one popular family of repair-efficient erasure codes that mitigate the repair bandwidth and are deployed in practice. To adapt to the changing demands of access efficiency and fault tolerance, modern storage systems also conduct frequent scaling operations on erasure-coded data. In this article, we analyze the optimal trade-off between the repair and scaling performance of LRC in clustered storage systems. Specifically, we focus on two optimal repair-scaling trade-offs, and design placement strategies that operate along the two optimal repair-scaling trade-off curves subject to the fault tolerance constraints. We prototype and evaluate our placement strategies on a LAN testbed, and show that they outperform the conventional placement schemes in repair and scaling operations.

Process-in-Memory (PIM) based accelerator becomes one of the best solutions for the execution of convolution neural networks (CNN). Resistive random access memory (ReRAM) is a classic type of non-volatile random-access memory, which is very suitable for implementing PIM architectures. However, existing ReRAM-based accelerators mainly consider to improve the calculation efficiency, but ignore the fact that the digital-analog signal conversion process spends a lot of energy and executing time. In this paper, we propose a novel ReRAM-based accelerator named Receptive-Field and Switch-Matrices based CNN Accelerator (RFSM). In RFSM, we first propose a receptive-field based convolution strategy to analyze the data relationships, and then gives a dynamic and configurable crossbar combination method to reduce the digital-analog conversion operations. The evaluation result shows that, compared to existing works, RFSM gains up to 6.7x higher speedup and 7.1x lower energy consumption.

3D flash memory removes scaling limitations of planar flash memory, yet it is still plagued by the tedious GC process due to the “big block problem”. In this paper, we propose SpeedupGC, a framework that incorporates the characteristics of data updates into existing sub-block erase designs. The main idea of SpeedupGC is to guide the hotly-updated data to the blocks that are about to be erased, so as to speculatively produce more invalid pages and suppress the relocation overhead. We conduct extensive trace-driven experiments, showing that SpeedupGC can averagely reduce 64.7% of the GC latency, 21.8% of the read latency, 17.7% of the write latency, and 11.5% of the write amplification when compared to state-of-the-art designs.

Non-Volatile Memories (NVMs) have shown tremendous potential to be the next generation of main memory, yet they are still seriously hampered by the high write latency and limited endurance. In this paper, we first unveil via realworld benchmark analysis that the words within the same cache line showcase a high degree of similarity. We therefore present SimiEncode, a low-overhead and effective Similarity-based Encoding approach. SimiEncode relieves writes to NVMs by (1) generating a mask word with minimized differences to the words within a cache line, (2) encoding each word with the associated mask word by simple XOR operations, and (3) writing a single tag bit to indicate the resulting zero word after encoding. Our prototype implementation of SimiEncode and extensive evaluations driven by 15 state-of-the-art benchmarks demonstrate that, compared with existing approaches, SimiEncode significantly prolongs the lifetime and improves the performance. Importantly, SimiEncode is orthogonal to and can be easily incorporated into existing bit flipping optimizations.

As increasingly prevalent, more and more data are stored in the cloud storage, which brings us two major challenges. First, the modified files in the cloud should be quickly synchronized (sync) to ensure data consistency, e.g., delta sync achieves efficient cloud sync by synchronizing only the updated part of the file. Second, the huge data in the cloud needs to be deduplicated and encrypted, e.g., message-locked encryption (MLE) implements data deduplication by encrypting the content between different users. However, when both are combined, few updates in the content can cause large sync traffic amplification for both keys and ciphertext in the MLE-based cloud storage, which significantly degrading the cloud sync efficiency. In this paper, we propose an feature-based encryption sync scheme FeatureSync to improve the performance of synchronizing multiple encrypted files by merging several files before synchronizing. The performance evaluations on a lightweight prototype implementation of FeatureSync show that FeatureSync reduces the cloud sync time by 72.6% and the cloud sync traffic by 78.5% on average, compared with the state-of-the-art sync schemes.

Erasure coding has been extensively deployed in today's data centers to tackle prevalent failures, yet it is prone to give rise to substantial cross-rack traffic for parity update. In this paper, we propose a new rack-coordinated update mechanism to suppress the cross-rack update traffic, which comprises two successive phases: a delta-collecting phase that collects data delta chunks, and another selective parity update phase that renews the parity chunks based on the update pattern and parity layout. We further design RackCU, an optimal rack-coordinated update solution that achieves the theoretical lower bound of the cross-rack update traffic. We finally conduct extensive evaluations, in terms of large-scale simulation and real-world data center experiments, showing that RackCU can reduce 22.1%-75.1% of the cross-rack update traffic and hence improve 34.2%-292.6% of the update throughput.

With the advent of new flash-based memory technologies with ultra-low latency, directly applying inline data deduplication in flash-based storage devices can degrade the system performance since key deduplication operations lie on the shortened critical write path of such devices. To address the problem, we propose a Content-Aware Garbage Collection scheme (CAGC), which embeds the data deduplication into the data movement workflow of the Garbage Collection (GC) process in ultra-low latency flash-based SSDs. By parallelizing the operations of valid data pages migration, hash computing and flash block erase, the deduplication-induced performance overhead is alleviated and redundant page writes during the GC period are eliminated. To further reduce data writes and write amplification during GC, CAGC separates and stores data pages in different regions based on their reference counts. The performance evaluation of our CAGC prototype implemented in FlashSim shows that CAGC significantly reduces the number of flash blocks erased and data pages migrated during GC, leading to improved user I/O performance and reliability of ultra-low latency flash-based SSDs.

Erasure coding is a storage-efficient means to guarantee data reliability in today's commodity storage systems, yet its repair performance is seriously hindered by the substantial repair traffic. Repair in clustered storage systems is even complicated because of the scarcity of the cross-cluster bandwidth. We present${\sf ClusterSR}$, a cluster-aware scattered repair approach.${\sf ClusterSR}$minimizes the cross-cluster repair traffic by carefully choosing the clusters for reading and repairing chunks. It further balances the cross-cluster repair traffic by scheduling the repair of multiple chunks. Large-scale simulation and Alibaba Cloud ECS experiments show that${\sf ClusterSR}$can reduce 5.6-52.7 percent of the cross-cluster repair traffic and improve 14.4–68.8 percent of the repair throughput.

Mobile Edge Computing (MEC) brings abundant cloud resources to the edge of the network and provides great opportunities to improve user's quality of experience. While many recent studies have investigated the problem of computation offloading, service caching is also an important design topic of MEC. Service caching stores application-related databases or libraries in advance and enables corresponding user tasks to be offloaded. Due to the limited resources in the edge server, service caching decisions have to be made judiciously to maximize the system performance. In this paper, we study the problem of joint service caching, computation offloading, transmission and computing resource allocation in a general scenario of multiple users with multiple tasks. We aim to minimize the overall computation and delay costs for all users and formulate the optimization problem as a quadratically constrained quadratic program (QCQP) which is non-convex and NP-hard. To solve this challenging problem, we propose an efficiently approximate algorithm based on semidefinite relaxation (SDR) approach and alternating optimization which always computes a locally optimal solution. Moreover, we extend the study to the scenario where each user has a computation cost constraint. Simulation results show that our algorithm can minimize the system cost effectively by utilizing the available system resources.

Inline deduplication is a popular technique to effectively reduce the write traffic and improve the space efficiency for flash-based storage. However, it also introduces computing and memory overhead to generate and store the cryptographic hash (fingerprint). Along the advent of 3D XPoint and Z-NAND technologies with vastly improved latency and bandwidth, both the computing and memory overheads are becoming much more pronounced in deduplication-based flash storage with cryptographic hash functions in use. To address these problems, we propose an ECC (Error Correcting Code) assisted deduplication approach, called EaD, which exploits the ECC property and the asymmetric read-write performance characteristics of modern flash-based storage. EaD first identifies data similarity based on the fingerprints of data chunks represented by their ECC values, thus significantly reducing the costly cryptographic hash computing and alleviating the memory space overhead. Based on the identification results, similar data chunks and their ECCs are read from the flash to perform a byte-by-byte comparison in memory to definitively identify and remove redundant data chunks. Our experiments show that the EaD approach significantly reduces the I/O latency by an average of 1.92× and 1.86×, and reduces the memory consumption by an average of 35.0% and 21.9%, compared with the existing SHA- and sampling-based deduplication approaches, respectively.

We explore machine learning for accurately predicting imminent disk failures and hence providing proactive fault tolerance for modern storage systems. Current disk failure prediction approaches are mostly offline and assume that the disk logs required for training learning models are available a priori. However, in large-scale disk deployment, disk logs are often continuously generated as an evolving data stream, in which the statistical patterns vary over time (also known as concept drift). Such a challenge motivates the need of online techniques that perform training and prediction on the incoming stream of disk logs in real time, while being adaptive to concept drift.We present StreamDFP, a general stream mining framework for disk failure prediction with concept-drift adaptation. We start with a measurement study and demonstrate the existence of concept drift on various disk models based on the datasets from Backblaze and Alibaba Cloud. Motivated by our study, we design StreamDFP with three key techniques, namely (i) online labeling, (ii) concept-drift-aware training, and (iii) general prediction, with a primary objective of making StreamDFP support various machine learning algorithms as a general frame-work. Our evaluation shows that StreamDFP improves the prediction accuracy significantly compared to without concept-drift adaptation under various settings, and achieves reasonably high stream processing performance.

How to improve the repair performance of erasure-coded storage is a critical issue for maintaining high reliability of modern large-scale storage systems. Locally repairable codes (LRC) are one popular family of repair-efficient erasure codes that mitigate the repair bandwidth and are deployed in practice. To adapt to the changing demands of access efficiency and fault tolerance, modern storage systems also conduct frequent scaling operations on erasure-coded data. In this paper, we analyze the optimal trade-off between the repair and scaling performance of LRC in clustered storage systems. Specifically, we design placement strategies that operate along the optimal repair-scaling trade-off curve subject to the fault tolerance constraints. We prototype and evaluate our placement strategies on a LAN testbed, and show that they outperform the conventional placement scheme in repair and scaling operations.

RAID-6 is gradually replacing RAID-5 as the dominant form of disk arrays due to its capability of tolerating concurrent failures of any two disks, as well as the case of encountering an uncorrectable read error during recovery. Implementing a RAID-6 system relies on some erasure coding schemes, and so far the most representative solutions are EVENODD codes [1], RDP codes [2] and Liberation codes [3], none of which has emerged as a clear "all-around" winner. In this paper, we are interested in revealing the undiscovered potential of the Liberation codes, since these codes have the following attractive features: (a) they have the best update performance, (b) they have better scalability, and (c) they are open-sourced and publicly available, as well as the following drawbacks: fair encoding performance and, more importantly, relatively poor decoding performance. Specificly, we present novel optimal encoding and decoding algorithms for the Liberation codes by introducing an alternative, geometric presentation of these codes. The proposed algorithms completely eliminate redundant computations during the encoding and decoding procedures by extracting and reusing common expressions between the two types of parity constraints, and do not involve any matrix operations on which the original algorithms are based. Our experiment results show that compared with the original solution, the proposed encoding and decoding algorithms reduce the number of XOR's by up to 16 percent and 15 ~20 percent respectively, and the encoding and decoding throughputs are increased by 22.3 percent and at most 155 percent respectively. Moreover, the encoding complexity reaches the theoretical lower bound, while the decoding complexity is also very close to the theoretical lower bound.

Erasure coding is a storage-efficient means to guarantee data reliability in today's commodity storage systems, yet its repair performance is seriously hindered by the substantial repair traffic. Repair in clustered storage systems is even complicated because of the scarcity of the cross-cluster bandwidth. We present ClusterSR, a cluster-aware scattered repair approach. ClusterSR minimizes the cross-cluster repair traffic by carefully choosing the clusters for reading and repairing chunks. It further balances the cross-cluster repair traffic by scheduling the repair of multiple chunks. Large-scale simulation and Alibaba Cloud ECS experiments show that ClusterSR can reduce 6.7-52.7% of the cross-cluster repair traffic and improve 14.1-68.8% of the repair throughput.

Erasure codes are widely used in cloud storage systems, such as in Google File System and Windows Azure. However, most of existing erasure codes focus on homogeneous storage device, but ignore that heterogeneous devices are in majority in cloud storage system. In this paper, we propose a new erasure code framework termed Device Placement Aware Framework (DPAF), to integrate existing erasure codes to generate DPAF-Codes, in order to gain good performance on heterogeneous storage devices. The key insight is to detect the device performance to generate a series of coefficients, and use these coefficients to choose proper devices to construct DPAF-Codes. We utilize simulated annealing algorithm to optimize the selection process, in order to maintain the balance among devices by considering the coefficients. The experiment results show that, our proposed DPAF-Codes gain up to 70.3%, 48.7%, and 48.5% improvements on single failure recovery, normal read, and degraded read speed, compared to RS code and LRC code with different configurations.

Modern key-value (KV) stores increasingly adopt erasure coding to reliably store data. To adapt to the changing demands on access performance and reliability requirements, KV stores perform redundancy transitioning by tuning the redundancy schemes with different coding parameters. However, redundancy transitioning incurs extensive I/Os, which impair the performance of KV stores. We propose a new family of erasure codes, called Elastic Reed-Solomon (ERS) codes, whose primary goal is to mitigate I/Os in redundancy transitioning. ERS codes eliminate data block relocation, while limiting I/Os for parity block updates via the new co-design of encoding matrix construction and data placement. We realize ERS codes as a KV store atop Memcached, and show via LAN testbed experiments that ERS codes significantly reduce the latency of redundancy transitioning compared to state-of-the-arts.

How to improve the performance of single failure recovery has been an active research topic because of its prevalence in large-scale storage systems. We argue that when erasure coding is deployed in a clustered file system (CFS), existing single failure recovery designs are limited in different aspects: neglecting the bandwidth diversity property in a CFS architecture, targeting specific erasure code constructions, and no special treatment on load balancing during recovery. In this paper, we propose CAR, a cross-rack-aware recovery algorithm that is designed to improve the performance of single failure recovery of a CFS that employs Reed-Solomon codes for general fault tolerance. For each stripe, CAR finds a recovery solution that retrieves data from the minimum number of racks. It also reduces the amount of cross-rack repair traffic by performing intra-rack data aggregation prior to cross-rack transmission. Furthermore, by considering multi-stripe recovery, CAR balances the amount of cross-rack repair traffic across multiple racks. Evaluation results show that CAR can effectively reduce the amount of cross-rack repair traffic and the resulting recovery time.

The update performance in erasure-coded data centers is often bottlenecked by the constrained cross-rack bandwidth. We propose CAU, a cross-rack-aware update mechanism that aims to mitigate the cross-rack update traffic in erasure-coded data centers. CAU builds on three design elements: (i) selective parity updates, which select the appropriate parity update approach based on the update pattern and the data layout to reduce the cross-rack update traffic; (ii) data grouping, which relocates and groups updated data chunks in the same rack to further reduce the cross-rack update traffic; and (iii) interim replication, which stores a specified number of temporary replicas for each newly updated data chunk. We evaluate CAU via trace-driven analysis, local cluster experiments, and Amazon EC2 experiments. We show that CAU enhances state-of-the-arts by mitigating the cross-rack update traffic as well as maintaining high update performance in both local cluster and geo-distributed environments.

Erasure coding offers a storage-efficient redundancy mechanism for maintaining data availability guarantees in large-scale storage clusters, yet it also incurs high performance overhead in failure repair. Recent developments in accurate disk failure prediction allow soon-to-fail (STF) nodes to be repaired in advance, thereby opening new opportunities for accelerating failure repair in erasure-coded storage. To this end, we present a fast predictive repair solution called FastPR, which carefully couples two repair methods, namely migration (i.e., relocating the chunks of an STF node) and reconstruction (i.e., decoding the chunks of an STF node through erasure coding), so as to fully parallelize the repair operation across the storage cluster. FastPR solves a bipartite maximum matching problem and schedules both migration and reconstruction in a parallel fashion. We show that FastPR significantly reduces the repair time over the baseline repair approaches via mathematical analysis, large-scale simulation, and Amazon EC2 experiments.

With the rapid development of cloud computing, data centers are increasing in quantity and scale for large Internet service providers to provide global Internet services. The enormous operation cost of data centers attracts lots of researchers' attention and their huge energy consumption have brought great challenges to the sustainable development of green data centers. In this paper, we investigate the workload scheduling and energy management issues of geo- distributed data centers with renewable resources and energy storages. We formulate the minimization problem of operation cost including electricity cost, water consumption and carbon emission as a stochastic optimization problem. For minimizing the long-term operation cost, we adopt the Lyapunov optimization technique to design an online algorithm which achieves a delicate tradeoff between system cost and performance of delay tolerant workloads. Moreover, extensive simulation results show the correctness and effectiveness of proposed online algorithm based on the real-world traces.

This work studies an electric vehicles (EVs) loaded microgrid with renewable energy resources, energy storage system (ESS) and external power grid. The microgrid's energy management problem is formulated to maximize its daily average operation revenue and balance the supply and demand based on the system statistical information, i.e., electricity market price, renewable energy arrivals and EVs' charging characteristics. For online optimization, we develop a reinforcement learning (RL) based approach to smartly control the microgrid's ESS in real-time by considering future reward of an charging/discharging action. Moreover, to speed up the RL training stage, a prediction model using long short term memory (LSTM) networks is adopted to explore the system input traces for more accurate future reward counting in current learning process. The simulation results validate the superior performance of the proposed algorithm with comparison to the conventional online optimization version.

Stragglers (i.e., nodes with slow performance) are prevalent and incur performance instability in large-scale storage systems, yet it is challenging to detect stragglers in practice. We make a case by showing how erasure-coded caching provides robust straggler tolerance without relying on timely and accurate straggler detection, while incurring limited redundancy overhead in caching. We first analytically motivate that caching only parity blocks can achieve effective straggler tolerance. To this end, we present POCache, a parity-only caching design that provides robust straggler tolerance. To limit the erasure coding overhead, POCache slices blocks into smaller subblocks and parallelizes the coding operations at the subblock level. Also, it leverages a straggler-aware cache algorithm that takes into account both file access popularity and straggler estimation to decide which parity blocks should be cached. We implement a POCache prototype atop Hadoop 3.1 HDFS, while preserving the performance and functionalities of normal HDFS operations. Our extensive experiments on both local and Amazon EC2 clusters show that in the presence of stragglers, POCache can reduce the read latency by up to 87.9% compared to vanilla HDFS.

Mobile-edge computing (MEC) has evolved as a promising technology to alleviate the computing pressure of mobile devices by offloading computation tasks to MEC server. Energy management is challenging since the unpredictability of the energy harvesting (EH) and the quality of service (QoS). In this paper, we investigate the problem of power consumption in a multiuser MEC system with EH devices. The system power consumption, which includes the local execution power and the offloading transmission power, is designated as the main system performance index. First, we formulate the power consumption minimization problem with the battery queue stability and QoS constraints as a stochastic optimization programming, which is difficult to solve due to the time-coupling constraints. Then, we adopt the Lyapunov optimization approach to tackle the problem by reformulating it into a problem with relaxed queue stability constraints. We design an online algorithm based on the Lyapunov optimization method, which only uses current states of the mobile users and does not depend on the system statistic information. Furthermore, we propose a distributed algorithm based on the alternating direction method of multipliers to reduce the system computational complexity. We prove the optimality of the online algorithm and the distributed algorithm using rigorous theoretical analysis. Finally, we perform extensive trace-simulations to verify the theoretical results and evaluate the effectiveness of the proposed algorithms.

This paper proposes an online algorithm for energy storage management in networked microgrids (MGs) with co-generation based on the concept of quality-of-service in electricity (QoSE). The concept of networked MG with distributed renewable energy supply and co-generation makes power supply smarter for electricity/heat using, which has advantages of increasing power supply efficiency and reliability by coordinately scheduling the power supply in a networked way. The demands include quality usage of electricity load and heat. The networked MG central controller aims to minimize the operation cost and guarantee the outage probability of quality usage, i.e., QoSE, by scheduling electricity among renewable energy sources, energy storage systems, co-generation, and external utility market. We formulate the problem as a stochastic programming problem with QoSE and battery capacity constraints. By introducing the QoSE virtual queues and energy storage virtual queues, we transform the original problem into a problem that is applicable to employ the Lyapunov optimization technique. The proposed algorithm is an online algorithm with low complexity for practical implementation, and also provides several deterministic performance bounds. We perform extensive simulations to demonstrate the effectiveness of the proposed algorithm, which exhibits significant efficiency on operation cost reduction compared with an alternative benchmark solution.

Erasure coding has been extensively employed for data availability protection in production storage systems by maintaining a low degree of data redundancy. However, how to mitigate the parity update overhead of partial stripe writes in erasure-coded storage systems is still a critical concern. In this paper, we study this problem from two new perspectives: data correlation and stripe organization. We propose CASO, a correlation-aware stripe organization algorithm, which captures data correlation of a data access stream and uses the data correlation characteristics for stripe organization. It packs correlated data into a small number of stripes to reduce the incurred I/Os in partial stripe writes, and further organizes uncorrelated data into stripes to leverage the spatial locality in later access. We implement CASO over Reed-Solomon codes and Azure's Local Reconstruction Codes, and show via extensive tracedriven evaluation that CASO reduces up to 29.8 percent of parity updates and reduces the write time by up to 46.7 percent.

Energy consumption in the base stations (BSs) recently has aroused significant concerns especially when renewable power has been widely applied. In this paper, we jointly integrate power from the power grid and renewable energy to investigate energy management in the BSs with sleep- awake capability for cellular networks. In our system model, the BSs are equipped with two charging batteries operating at double timescales, exhibiting a more practical performance and heterogeneous energy storage capability. We formulate the energy management problem as a challenging nonlinear optimization problem because of the data randomness and the temporal coupling effect. We adopt Lyapunov optimization approach to tackle the problem by relaxing the battery constraints and reformulating the problem with virtual queues of the state of charge and the quality of service (QoS). We design an online algorithm with quick convergence speed and low complexity which avoids depending on statistics of system. We perform extensive simulations to verify the theoretical analysis.

Mobile-edge computing (MEC) has evolved as a promising technology to alleviate the computing pressure of mobile devices by offloading computation tasks to MEC server. Energy management is challenging since the unpredictability of the energy harvesting and the quality of service (QoS). In this paper, we investigate the problem of power consumption in a multi-user MEC system with energy harvesting (EH) devices. The system power consumption, which includes the local execution power and the offloading transmission power, is designated as the main system performance index. First, we formulate the power consumption minimization problem with the battery queue stability and QoS constraints as a stochastic optimization programming, which is difficult to solve due to the time-coupling constraints. Then, we adopt the Lyapunov optimization approach to tackle the problem by reformulating it into a problem with relaxed queue stability constraints.We design an online algorithm based on the Lyapunov optimization method, which only uses current states of the mobile users (MUs) and does not depend on the system statistic information. Moreover, we prove the optimality of the online algorithm using rigorous theoretical analysis. Finally, we perform extensive trace-simulations to verify the theoretical results and evaluate the effectiveness of the proposed algorithms.

The update performance in erasure-coded data centers is often bottlenecked by the constrained cross-rack bandwidth. We propose CAU, a cross-rack-aware update mechanism that aims to mitigate the cross-rack update traffic in erasure-coded data centers. CAU builds on three design elements: (i) selective parity updates, which select the appropriate parity update approach based on the update pattern and the data layout to reduce the cross-rack update traffic; (ii) data grouping, which relocates and groups updated data chunks in the same rack to further reduce the cross-rack update traffic; and (iii) interim replication, which stores a temporary replica for each newly updated data chunk. We evaluate CAU via trace-driven analysis, local cluster experiments, and Amazon EC2 experiments. We show that CAU enhances state-of-the-arts by mitigating the cross-rack update traffic as well as maintaining high update performance in both local cluster and geo-distributed environments.

Modern storage systems adopt erasure coding to maintain fault tolerance with low storage redundancy. However, how to improve the performance of degraded reads in erasure-coded storage has been a critical issue. We revisit this problem from two different perspectives that are neglected by existing studies: data placement and encoding rules. To this end, we propose encoding-aware data placement (EDP), which mitigates the number of I/Os in degraded reads during a single failure for general XOR-based erasure codes. EDP carefully selects appropriate parity units to be generated by sequential data based on the encoding rules and establishes their generation orders. We further refine the data placement for optimizing the degraded reads to any two sequential data units. Trace-driven evaluation results show that EDP significantly reduces I/Os in degraded reads and hence shortens the read time.

Erasure coding has been extensively employed for data availability protection in production storage systems by maintaining a low degree of data redundancy. However, how to mitigate the parity update overhead of partial stripe writes in erasure-coded storage systems is still a critical concern. In this paper, we reconsider this problem from two new perspectives: data correlation and stripe organization, and propose CASO, a correlation-aware stripe organization algorithm. CASO captures data correlation of a data access stream. It packs correlated data into a small number of stripes to reduce the incurred I/Os in partial stripe writes, and further organizes uncorrelated data into stripes to leverage the spatial locality in later accesses. By differentiating correlated and uncorrelated data in stripe organization, we show via extensive trace-driven evaluation that CASO reduces up to 25.1% of parity updates and accelerates the write speed by up to 28.4%.

As reliability requirements are increasingly important in both clusters and data centers, RAID-6, which can tolerate any two concurrent disk failures, has been widely used in modern storage systems. However, most existing RAID-6 codes cannot provide satisfied performance on both degraded reads and partial stripe writes, which are important performance metrics in storage systems. To address these problems, in this paper we propose a new RAID-6 MDS erasure code called Short Code, in order to optimize the degraded reads and partial stripe writes. In Short Code, we propose a novel short horizontal parity chain, which assures that all disks contribute to degraded reads while the continuous data elements are more likely to share the same horizontal chain for optimizing degraded reads. On the other hand, Short Code distributes all diagonal parities among disks for optimizing partial stripe writes. The proposed Short Code not only owns the optimal storage efficiency, but also keeps the optimal complexity for both encoding/decoding computations and update operations. The experiments show that Short Code achieves much higher speed on degraded reads and partial stripe writes than other popular RAID-6 codes, and provide acceptable performance on single disk failure recoveries and normal reads. Specifically, compared to RDP code, Short Code provides 6.1 to 26.3 percent higher speed on degraded reads and 36.2 to 80.3 percent higher speed on partial stripe writes with the same number of disks.

Erasure coding provides an effective means for storage systems to protect against disk failures with low redundancy. One important objective for erasure-coded storage systems is to speed up single disk failure recovery. Previous approaches reduce the amount of read data for recovery by reading only a small subset of data. However, they often incur high disk seeks, which may negate the resulting recovery performance. We proposeSIOR, a seek-efficient I/O recovery algorithm for improving the performance of single disk failure recovery. SIOR carefully balances the trade-off between the amount of read data and the number of disk seeks by considering the data layout at the multi-stripe level. It then greedily determines the data to read for recovery using Tabu search. Experiments show that SIOR achieves similar performance to the brute-force enumeration method while keeping high search efficiency. Also, SIOR reduces$31.8\sim 65.1$percent of disk seeks during recovery and provides up to 150.0 percent recovery speed improvement, when compared to a state-of-the-art greedy recovery approach.

How to improve the performance of single failure recovery has been an active research topic because of its prevalence in large-scale storage systems. We argue that when erasure coding is deployed in a cluster file system (CFS), existing single failure recovery designs are limited in different aspects: neglecting the bandwidth diversity property in a CFS architecture, targeting specific erasure code constructions, and no special treatment on load balancing during recovery. In this paper, we reconsider the single failure recovery problem in a CFS setting, and propose CAR, a cross-rack-aware recovery algorithm. For each stripe, CAR finds a recovery solution that retrieves data from the minimum number of racks. It also reduces the amount of cross-rack repair traffic by performing intra-rack data aggregation prior to cross-rack transmission. Furthermore, by considering multi-stripe recovery, CAR balances the amount of cross-rack repair traffic across multiple racks. Evaluation results show that CAR can effectively reduce the amount of cross-rack repair traffic and the resulting recovery time.

Large-scale storage systems often face node failures that lead to data loss. Cooperative regeneration has been extensively studied to minimize the repair traffic of simultaneously reconstructing the lost data of multiple failed nodes. However, existing cooperative regeneration schemes assume that nodes are homogeneous. They do not consider how to minimize the general regenerating cost when taking into account node heterogeneity. This paper presents the first systematic study on enhancing conventional cooperation regeneration (CCR) schemes in a heterogeneous environment. We formulate cooperative regeneration as a cost-based routing optimization model, and propose a new cost-based heterogeneity-aware cooperative regeneration (HCR) framework. The main novelty of HCR is to decompose CCR schemes into two stages (i.e., expansion and aggregation) that can be opportunistically carried out by different nodes depending on their costs. To efficiently select the nodes for expansion execution without exhaustive enumeration, we design two greedy algorithms based on the hill-climbing technique. We also formulate the routing problem in the aggregation stage as a Steiner Tree Problem. Finally, we conduct extensive trace-driven simulations and show that HCR can reduce up to 75.4% transmission time of CCR. Also, we demonstrate that HCR remains robust even when the heterogeneity information is not accurately measured.

Erasure coding has been increasingly used by distributed storage systems to maintain fault tolerance with low storage redundancy. However, how to enhance the performance of degraded reads in erasure-coded storage has been a critical issue. We revisit this problem from two different perspectives that are neglected by existing studies: data placement and encoding rules. To this end, we propose an encoding-aware data placement (EDP) approach that aims to reduce the number of I/Os in degraded reads during a single failure for general XOR-based erasure codes. EDP carefully places sequential data based on the encoding rules of the given erasure code. Trace-driven evaluation results show that compared to two baseline data placement methods, EDP reduces up to 37.4% of read data on the most loaded disk and shortens up to 15.4% of read time.

The fast growing of data scale encourages the wide employment of data disks with large storage capacity. However, a mass of data disks' equipment will in turn increase the probability of data loss or damage, because of the appearance of various kinds of disk failures. To ensure the intactness of the hosted data, modern storage systems usually adopt erasure codes, which can recover the lost data by pre-storing a small amount of redundant information. As the most common case among all the recovery mechanisms, the single disk failure recovery has been receiving intensive attentions for the past few years. However, most of existing works still take the stripe-level recovery as their only consideration, and a considerable performance improvement on single failure disk reconstruction in the stack-level (i.e., a group of rotated stripes) is missed. To seize this potential improvement, in this paper we systematically study the problem of single failure recovery in the stack-level. We first propose two recovery mechanism based on greedy algorithm to seek for the near-optimal solution (BP-Scheme and STP-Scheme) for any erasure array code in stack level, and further design a rotated recovery algorithm (RR-Algorithm) to eliminate the size of required memory. Through a rigorous statistic analysis and intensive evaluation on a real system, the results show that BP-Scheme gains 3.4 to 38.9 percent (the average is 21.2 percent) higher recovery speed than Khan's Scheme and 3.4 to 34.8 percent (the average is 19.1 percent) higher recovery speed than Luo's U-Scheme, while STP-Scheme owns 3.4 to 46.9 percent (the average is 25.15 percent) and 3.4 to 41.1 percent (the average is 22.3 percent) higher recovery speed than Khan's Scheme and Luo's U-Scheme, respectively.

The increasing expansion of data scale leads to the widespread deployment of storage systems with larger capacity and further induces the climbing probability of data loss or damage. The Maximum Distance Separable (MDS) code in RAID-6, which tolerates the concurrent failures of any two disks with minimal storage requirement, is one of the best candidates to enhance the data reliability. However, most of the existing works in this literature are more inclined to be specialized and cannot provide a satisfied performance under an all-round evaluation. Aiming at this problem, we propose an all-round MDS code named Horizontal-Vertical Code (HV Code) by taking advantage of horizontal parity and vertical parity. HV Code achieves the perfect I/O balancing and optimizes the operation of partial stripe writes, while preserving the optimal encoding/decoding/update efficiency. Moreover, it owns a shorter parity chain which grants it a more efficient recovery for single disk failure. HV Code also behaves well on degraded read operation and accelerates the reconstruction of double disk failures by executing four recovery chains in parallel. The performance evaluation demonstrates that HV Code well balances the I/O distribution. HV Code also eliminates up to 32.2 percent I/O operations for partial stripe writes in read-modify-write mode, and reduces up to 28.9 percent I/O operations for partial stripe writes in reconstruct-write mode. Moreover, HV Code reduces 5.4~39.8 percent I/O operations per element for the single disk reconstruction, decreases 8.3~39.0 percent I/O operations for degraded read operations, and shortens 47.4~59.7 percent recovery time for double disk recovery.

Erasure codes tolerate disk failures by pre-storing a low degree of data redundancy, and have been commonly adopted in current storage systems. However, the attached requirement on data consistency exaggerates partial stripe write operations and thus seriously downgrades system performance. Previous works to optimize partial stripe writes are relatively limited, and a general mechanism is still absent. In this paper, we propose a Parity-Switched Data Placement (PDP) to optimize partial stripe writes for any XOR-coded storage system. PDP first reduces the write operations by arranging continuous data elements to join a common parity element's generation. To achieve a deeper optimization, PDP further explores the generation orders of parity elements and makes any two continuous data elements associate with a common parity element. Intensive evaluations show that for tested erasure codes, PDP reduces up to 31.9 percent of write operations and further increases the write speed by up to 59.8 percent when compared with two state-of-the-art data placement methods.

With the reliability requirements increasingly important, erasure codes have been widely used in today's cloud storage systems because they achieve both high reliability and low storage overhead. However, the performance for most existing erasure codes can be further improved on both normal reads to user's data without device failures and degraded reads under device failures, which are crucial in cloud storage systems. In this paper, we propose an erasure coding framework named EC-FRM to integrate existing codes in order to improve the read performance. The constructed code over EC-FRM named EC-FRM-Code, which keeps most of wonderful properties of the integrated code and achieves good performance on both normal reads and degraded reads. We transform Reed-Solomon code and LRC code to EC-FRM-RS and EC-FRM-LRC respectively, and then conduct a series of experiments to evaluate their read performance. The results show that EC-FRM-RS code gains 19.2% to 33.9% higher normal read speed and 9.1% to 9.9% higher degraded read speed than standard Reed-Solomon code, while EC-FRM-LRC code owns 23.5% to 46.9% higher normal read speed and 3.3% to 12.8% higher degraded read speed than standard LRC code.

Erasure coding provides an effective means for storage systems to protect against disk failures with low redundancy. One important objective for erasure-coded storage systems is to speed up single disk failure recovery. Previous studies reduce the amount of data read for recovery by reading only a small subset of data, but their approaches often incur high disk seeks, which may negate the resulting recovery performance. We propose SIOR, a seek-efficient I/O recovery algorithm for single disk failures. SIOR carefully balances the trade-off between the amount of data read and the number of disk seeks by considering the data layout at the multi-stripe level. It then greedily determines the data to read for recovery using Tabu search. Experiments show that SIOR achieves similar performance to the brute-force enumeration method while keeping high search efficiency. Also, SIOR reduces 31.8%~65.1% of disk seeks during recovery and provides up to 186.8% recovery speed improvement, when compared to a state-of-the-art greedy recovery approach.

The increasing expansion of data scale leads to the widespread deployment of storage systems with larger capacity and further induces the climbing probability of data loss or damage. The Maximum Distance Separable (MDS) code in RAID-6, which tolerates the concurrent failures of any two disks with minimal storage requirement, is one of the best candidates to enhance the data reliability. However, most of the existing works in this literature are more inclined to be specialized and cannot provide a satisfied performance under an all-round evaluation. Aiming at this problem, we propose an all-round MDS code named Horizontal-Vertical Code (HV Code) by taking advantage of horizontal parity and vertical parity. HV Code achieves the perfect I/O balancing and optimizes the operation of partial stripe writes to continuous data elements, while preserving the optimal encode/decode/update efficiency. Moreover, it owns a shorter parity chain which grants it a more efficient recovery for one disk failure. HV Code also behaves well for the degraded read operation and accelerates the process to reconstruct two disabled disks by executing four recovery chains in parallel. The performance evaluation demonstrates that HV Code well balances the I/O distribution and eliminates up to 27.6% and 32.4% I/O requests for partial stripe writes operation when compared with RDP Code and HDP Code. Moreover, compared to RDP Code, HDP Code, X-Code and H-Code, HV Code reduces up to 5.4%~39.8% I/O requests per element for the single disk reconstruction, decreases 6.6%~28.3% I/O requests for degraded read operations, and achieves the same efficiency of X-Code for double disk recovery by shortening 47.4%~59.7% recovery time compared with other three codes.

Cloud computing has become an increasingly popular service for data storage and processing. To keep users' data on the cloud from leaking to unauthorized users, probably including the cloud service providers, the data must be stored in an encrypted form. In the meantime, for data intended for sharing, an efficient access control must be provided. A common operation on the data is keyword search. Currently, search operation over encrypted search is performed at the cloud servers and access control for the in-cloud data is usually enforced by users. Separation of the two types of operations can lead to reduced efficiency and compromised privacy for users with a given set of access privileges to search over encrypted cloud data. In this paper, we study the problem of keyword search with access control over encrypted data in cloud computing. We first propose a scalable framework where user can use his attribute values and a search query to locally derive a search capability, and a file can be retrieved only when its keywords match the query and the user's attribute values can pass the policy check. Using this framework, we propose a novel scheme called KSAC. KSAC utilizes a recent cryptographic primitive called HPE to enforce fine-grained access control, perform multi-field query search, and support the derivation of the search capability. Intensive evaluations on real-world dataset are conducted to validate the applicability of the proposed scheme.

With the rapid development of cloud storage, data security in storage receives great attention and becomes the top concern to block the spread development of cloud service. In this paper, we systematically study the security researches in the storage systems. We first present the design criteria that are used to evaluate a secure storage system and summarize the widely adopted key technologies. Then, we further investigate the security research in cloud storage and conclude the new challenges in the cloud environment. Finally, we give a detailed comparison among the selected secure storage systems and draw the relationship between the key technologies and the design criteria.

Cloud computing cuts down large capital outlays in facilities purchase and eliminates complex system management for users. To protect data confidentiality in cloud utilization, sensitive data are usually stored in encrypted form, making traditional search service on plaintext inapplicable. Thus, enabling keyword search over encrypted data becomes a paramount urgency. Given massive data users with various search preferences, it becomes necessary to support preferred keyword search and output the data files in the order of the user's preference. In this paper, for the first time, we investigate the challenging problem of preferred keyword search over encrypted data (PSED). We first establish a set of privacy requirements and utilize the appearance frequency of each keyword to serve as its “weight”. A preference preprocessing mechanism is then explored to ensure that the search result will faithfully respect the user's preference and the Lagrange polynomial is introduced to express the user's preference formula. We further represent keyword weights of each file by using vectors, convert the preference polynomial into the vector form, and securely calculate their inner products to quantitatively characterize the relevance measure between data files and a query. Finally, an extensive performance evaluation demonstrates the proposed scheme can achieve acceptable efficiency.

MOTIVATION: Over-represented k-mers in non-coding genomic regions often lead to identification of potential transcriptional regulatory sites (TRS). This phenomenon has been employed by many algorithms to predict TRS in silico. Yet, the improvement of these algorithms should be based on deeper understanding of the enrichment feature. To obtain a general distributional profile of TRS in different regions of genomes as well as in different genomes, we here performed a systematic analysis on the over-representation of TRS in intergenic regions and gene upstream regions of yeasts and viral genomes, and the distributional pattern of TRS in intergenic and intron regions of the Drosophila genome. We also explored the way to evaluate the accuracy of TRS consensus sequences by measuring their enrichment. RESULTS: To measure enrichment, a statistical background model was introduced by comparing TRS frequency in certain regions of genome to either the frequency in the whole genome or the frequency in exon region. This model was applied to different classes of non-coding genomic regions in four genomes. Most of the TRS were observed to be over-represented in the intergenic regions of the Saccharomyces cerevisiae, Schizosaccharomyces pombe and Epstein-Barr virus (EBV) genomes. The enrichment of S.cerevisiae TRS in the 600 bp upstream region of genes was also significant. In Drosophila genome, TRS did not show enrichment in intergenic and intron regions when TRS frequency in the whole genome was taken as background, as we did in other genomes. However, when we took TRS frequency in exon region as background, over 70% TRS are over-represented in those two classes of non-coding regions. This fact indicates the existence of transcriptional regulatory signals in introns. The analysis of some S.cerevisiae TRS, which have inconsistent consensus sequences with different levels of enrichment in intergenic region, suggests the possibility of evaluating the accuracy of experimentally determined TRS by measuring their enrichment in non-coding genomic regions.