Modern LSM-based KV stores reduce read amplification with two in-memory caches, namely a table cache for metadata such as index and Bloom-filter blocks, and a data cache for value blocks. These caches draw from a shared memory budget and are jointly exercised on the read path, so the metadata-data split is inherently coupled and end-to-end read latency can be non-monotonic in the allocation. Allocating more memory to one cache may improve its hit rate but evict blocks from the other, yielding hard-to-predict performance especially under dynamic workloads. Most systems therefore rely on fixed, ratio-based heuristics, which can be far from optimal. We present CoCache, a cooperative cache-management framework that continuously tunes the metadata-data cache split. CoCache combines lightweight online hotness tracking with a unified latency model that captures the coupled impact of metadata and data caching on the read path. Using these signals, CoCache efficiently searches candidate splits and applies the one with the lowest predicted latency, then re-optimizes as access patterns shift. We implement CoCache in RocksDB and evaluate it on synthetic, benchmark, and production-derived workloads. Compared to state-of-the-art baselines, CoCache improves cache hit rates by up to 1.56 ×, increases read throughput by up to 1.43 ×, and reduces read latency by up to 31.2%.

Modern distributed storage systems increasingly employ Locally Repairable Codes (LRCs) to provide reliable, low-cost data storage with high repair efficiency. However, the presence of stragglers, i.e., nodes that unpredictably slow down, can significantly impact access latency. Traditional approaches for handling stragglers, such as detection, blacklisting, or speculative execution, are often insufficient for efficient straggler tolerance. In this paper, we show how an in-memory caching strategy coupled with LRCs can bypass stragglers without relying on precise straggler detection. We propose LocalityCache, a novel in-memory caching mechanism designed for LRC-coded distributed storage systems, which effectively mitigates the impact of stragglers by caching local parity blocks. We provide theoretical guarantees for LocalityCache and show that caching local parity blocks minimizes the likelihood of encountering stragglers. Additionally, we devise optimized workflows for write, read, and repair operations under LocalityCache to ensure system efficiency. We implement LocalityCache in a distributed key–value store prototype atop Redis. Our extensive testbed evaluations show that LocalityCache can significantly reduce read latency of the baselines by up to 73.6% in the presence of stragglers.

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

Federated learning (FL), as a newly-developing technique, brings the advantage of organizing multiple participants to learn together, while avoiding the leakage of their privacy information. Contract theory provides an effective incentive mechanism to encourage participants to participate in FL. Existing contract-based incentive mechanisms consider participants’ types but ignore the different contributions of participants within the same type during the training.This paper first introduces a metric, reputation, to evaluate the contribution of participants in each iteration, and then proposes a hybrid contract mechanism consisting of a short-term contract and a long-term contract. Only the participants with reputations higher than a pre-defined threshold can sign the long-term contract. We formulate the solution of the long-term contract mechanism as an optimization problem with constraints. We further simplify the constraints of the long-term contract optimization problem, and theoretically analyze the correctness of the simplification to greatly reduce its computational complexity. We prove that the model owner achieves more profit with the hybrid contract mechanism. Simulations with the MNIST dataset show that the long-term contract improves the model accuracy by at least 5% compared with the existing contracts. Furthermore, compared with the short-term contract, participants signing the long-term contract are granted more rewards.

Many key-value storage systems employ LSM-tree-based architectures, which often suffer from significant read and write amplification issues that can substantially impact overall performance. While existing solutions mitigate amplification through key-value separation or relaxed ordering, they retain deep hierarchical structures that perpetuate scalability bottlenecks. We present Split-LSM-Tree, a novel storage engine that dynamically partitions monolithic LSM-trees into a forest of capacity-bounded subtrees when thresholds are breached. Our design introduces three key innovations: (1) An adaptive splitting trigger mechanism that initiates partitioning based on storage pressure and performance degradation; (2) A non-blocking splitting algorithm enabling seamless subtree migration; and (3) I/O optimizations preserving foreground operation continuity. Our experiments show that compared to the widely deployed LevelDB and RocksDB, Split-LSM-Tree reduces write amplification by$\mathbf{2 5. 7} \boldsymbol{\%}$and$\mathbf{1 8. 1 \%}$respectively, while achieving$\mathbf{2. 9} \times$and$\mathbf{2. 4} \times$higher write throughput.

Current distributed file systems manage metadata through a flattened metadata service, which requires accessing metadata across multiple metadata servers. To improve performance, file systems use client-side cache to reduce frequent server access and employ a lease mechanism to maintain client metadata cache consistency. However, the lease mechanism blocks metadata updates and requires periodic renewal of cache entries. To address these challenges, we propose Double-Metadata-Cache, an efficient two-layer metadata caching architecture. This solution incorporates two key designs: a validity period-based lazy update mechanism to maintain client metadata cache consistency, a segmented caching strategy uses hot prefixes to reduce accesses to metadata servers. Experimental results show that Double-Metadata-Cache achieves higher performance in high-proportion metadata operations such as creation and stat. Moreover, as the file depth increases, it reduces path resolution latency by 50 % compared to the client-side caching strategy.

Random walks on graphs are essential for various applications such as network analysis, recommendation systems, and graph embedding. However, existing frameworks for random walks face challenges in efficiently managing and updating walkers. These challenges arise from inefficient walker updating due to the subgraph-based iterative updating strategy, which makes walkers update only one step per iteration, and the high management and storage costs associated with the walker array-based management strategy. This paper presents a novel cache-efficient random walk framework called PTWalker, which sets out to have the majority of walkers updated at least two steps per iteration. This is achieved through an alternating dual-subgraph walk updating scheme, which involves dividing the graph into two sets of subgraphs with maximized edge cuts between them. These subgraph sets are then loaded into the cache for walk updating in an alternating manner, prompting most walkers to transition to the other subgraph set and update additional steps. Besides, a thread-level walker pool management strategy is designed to reduce management and storage costs for walkers. Experimental results demonstrate that PTWalker outperforms state-of-the-art random walk systems, achieving a speedup ranging from 0.18 × to 8.65 ×.

Large Language Models have transformed numerous domains with their exceptional capabilities. However, their training processes are inherently prone to failures due to the massive scale of training clusters, involving thousands to tens of thousands of GPUs and requiring several months of uninterrupted computation. Checkpointing serves as a critical mechanism for ensuring fault tolerance. However, the substantial size of LLM checkpoints, attributed to their vast number of parameters, poses significant challenges in terms of time and storage overheads. While existing approaches offer partial solutions, they remain inadequate in addressing the unique demands and complexities of LLM training at scale. To this end, we propose Amber, a novel LLM training framework that significantly improves checkpointing speed and storage efficiency by leveraging selective incremental checkpointing, a technique that selectively checkpoints significant parameter updates while omitting minor changes. We implement Amber atop PyTorch, a widely adopted deep learning framework, and demonstrate that Amber achieves up to 10–155 × faster checkpointing compared to state-of-the-art full checkpointing methods across models of varying scales on a single GPU, while maintaining storage overhead below 3%.

Evolving graph processing has become a critical component in various applications and is gaining increasing attention. However, existing evolving graph systems suffer from cache contention and workload imbalance between threads, which leads to poor scalability and performance degradation on modern multi-core computers.

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

In-memory cache systems such as Redis provide low-latency and high-performance data access for modern internet services. However, in large-scale Redis systems, the workloads show strong skewness and varied locality, which degrades system performance and incurs low CPU utilization. Though there are many approaches toward load imbalance, the two-layered architecture of Redis makes its workload skewness show special characteristics. Redis first maps data into data groups, which is calledGroup Mapping. Then the data groups are distributed to instances by Instance Mapping.Under Redis's layered architecture, it gives rise to a small number of hot-spot instances with very limited hot data groups, as well as a large number of remaining cold instances. To improve Redis's performance and CPU utilization, it entails the accurate identification of instance and data group hotness, and handling hot data groups and cold instances. We propose HPUCache+ to address the hot-spot problem via hotness identification, hot data copying, and cold instance merging. HPUCache+ accurately and dynamically detects instance and data group hotness based on multiple resources and workload characteristics at low cost. It enables access to multiple data copies by dynamically updating the cached mapping in Redis client, achieving high user access performance with Redis client compatibility, while providing highly self-definable service level agreement. It also proposes an asynchronous instance merging strategy based on disk snapshots and temporal caches, which separates the massive data movement from the critical user access path to achieve high-performance instance merging. We implement HPUCache+ into Redis. Experiments show that, compared to the native Redis design, HPUCache+ achieves up to 2.3$\times$and 3.5$\times$throughput gains, 11.3$\times$and 14.3$\times$CPU utilization gains, respectively. It also achieves up to 50% less CPU and 75% less memory consumption compared to the state-of-the-art approach Anna.

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

To scale out the massive metadata access, the Ceph distributed file system (CephFS) adopts a dynamic subtree partitioning method, splitting the hierarchical namespace and distributing subtrees across multiple metadata servers. However, this method suffers from a severe imbalance problem that may result in poor performance due to its inaccurate imbalance prediction, ignorance of workload characteristics, and unnecessary/invalid migration activities. To eliminate these inefficiencies, we propose Lunule, a novel CephFS metadata load balancer, which employs an imbalance factor model for accurately determining when to trigger re-balance and tolerate unharmful imbalanced situations. Lunule further adopts a workload-aware migration planner to appropriately select subtree migration candidates. Finally, we extend Lunule to Lunule + , which models metadata accesses into matrices, and employs matrix-based formulas for more accurate load prediction and re-balance decision. Compared to baselines, Lunule achieves better load balance, increases the metadata throughput by up to 315.8%, and shortens the tail job completion time by up to 64.6% for five real-world workloads and their mixture, respectively. Besides, Lunule is capable of handling the metadata cluster expansion and the workload growth, and scales linearly on a 16-node cluster. Compared to Lunule, Lunule + achieves up to 64.96% better metadata load balance, and 13.53-86.09% higher throughput.

Existing in-memory graph storage systems that rely on DRAM have scalability issues because of the limited capacity and volatile nature of DRAM. The emerging persistent memory (PMEM) offers us a chance to solve these issues through its larger capacity and non-volatile characteristics. However, simply adapting existing DRAM-based graph storage systems to PMEM would result in inefficient PMEM stores and accesses, including high read and write amplification to PMEM, imbalanced work division for PMEM accesses, and costly remote PMEM access across NUMA nodes. These issues severely limit the performance of large graph processing. In this article, we aim at achieving scalable and high-performance graph processing in PMEM. We first propose an XPLine-friendly graph storage model that uses vertex-centric graph buffering, hierarchical vertex buffer managing, and in-place vertex block merging to optimize PMEM graph storage. Furthermore, we develop a scalable graph processing model that leverages multi-threaded work dividing and NUMA-friendly graph accessing to optimize PMEM graph accesses. Based on these techniques, we implement XPGraph , a PMEM-based graph storage system for large-scale evolving graphs, and several variants for different system settings. Our experiments demonstrate that XPGraph surpasses the state-of-the-art in-memory graph storage system on a PMEM-based system by 3.07× to 4.99× in update performance and up to 5.87× in query performance, and performs much better in highly parallel multi-threaded scenarios.

Distributed graph analysis usually partitions a large graph into multiple small-sized subgraphs and distributes them into a cluster of machines for computing. Therefore, graph partitioning plays a crucial role in distributed graph analysis. However, the widely used existing graph partitioning schemes balance only in one dimension (number of edges or vertices) or incur a large number of edge cuts, so they degrade the performance of distributed graph analysis. In this article, we propose a novel graph partition scheme BPart and two enhanced algorithms BPart-C and BPart-S to achieve a balanced partition for both vertices and edges, and also reduce the number of edge cuts. Besides, we also propose a neighbor-aware caching scheme to further reduce the number of edge cuts so as to improve the efficiency of distributed graph analysis. Our experimental results show that BPart-C and BPart-S can achieve a better balance in both dimensions (the number of vertices and edges), and meanwhile reducing the number of edge cuts, compared to multiple existing graph partitioning algorithms, i.e., Chunk-V, Chunk-E, Fennel, and Hash. We also integrate these partitioning algorithms into two popular distributed graph systems, KnightKing and Gemini, to validate their impact on graph analysis efficiency. Results show that both BPart-C and BPart-S can significantly reduce the total running time of various graph applications by up to 60% and 70%, respectively. In addition, the neighbor-aware caching scheme can further improve the performance by up to 24%.

Gradient compression is a promising approach to alleviating the communication bottleneck in data parallel deep neural network (DNN) training by significantly reducing the data volume of gradients for synchronization. While gradient compression is being actively adopted by the industry (e.g., Facebook and AWS), our study reveals that there are two critical but often overlooked challenges: 1) inefficient coordination between compression and communication during gradient synchronization incurs substantial overheads, and 2) developing, optimizing, and integrating gradient compression algorithms into DNN systems imposes heavy burdens on DNN practitioners, and ad-hoc compression implementations often yield surprisingly poor system performance. In this paper, we propose a compression-aware gradient synchronization architecture,CaSync, which relies on flexible composition of basic computing and communication primitives. It is general and compatible with any gradient compression algorithms and gradient synchronization strategies and enables high-performance computation-communication pipelining. We further introduce a gradient compression toolkit,CompLL, to enable efficient development and automated integration of on-GPU compression algorithms into DNN systems with little programming burden. Lastly, we build a compression-aware DNN training frameworkHiPresswithCaSyncandCompLL.HiPressis open-sourced and runs on mainstream DNN systems such as MXNet, TensorFlow, and PyTorch. Evaluation via a 16-node cluster with 128 NVIDIA V100 GPUs and a 100 Gbps network shows thatHiPressimproves the training speed over current compression-enabled systems (e.g., BytePS-onebit, Ring-DGC and PyTorch-PowerSGD) by 9.8%-69.5% across six popular DNN models.

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

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

Large-scale storage systems increasingly adopt era-sure coding for low-cost reliable storage by storing stripes of data and parity blocks. To further achieve higher storage savings with performance guarantees, enterprises and academia explore wide stripes with locally repairable codes (LRCs). However, how to efficiently generate wide LRC stripes remains a non-trivial issue. Current approaches on stripe merging provide a starting point for merging narrow LRC stripes into wide LRC stripes, but they lack flexibility in the number of stripes being merged and the stripe width of the wide LRC stripes being formed. In this paper, we propose staged stripe merging for wide stripe generation in LRCs, by allowing a flexible number of narrow LRC stripes to be gradually merged into a wide stripe in multiple stages with optimality guarantees. In particular, we design an optimal data placement scheme for a group of narrow LRC stripes to be merged, such that it provably minimizes the cross-cluster network traffic for stripe merging across each stage, while maintaining the repair efficiency of LRCs. We implement the optimal data placement scheme for two production LRC constructions in a distributed storage prototype. Evaluation shows that our optimal data placement scheme significantly reduces the stripe merging time compared with several baselines.

Large-scale storage systems increasingly deploy erasure coding to provide high-reliability and low-cost data storage. To achieve further storage savings while maintaining repair efficiency, enterprises and academia explore wide stripes using locally repairable codes (LRCs) and several constructions are proposed. However, we find that these wide stripe LRCs neglect the file access information within the stripe, which matters as these LRCs assign uniform local group sizes while a wide stripe comprises many files with non-uniform or skewed access frequencies. Consequently, the repair efficiency is compromised. To this end, we design a novel wide stripe LRC construction called non-uniform LRC by fully considering the skewed file accesses in a wide stripe. Our non-uniform LRC assigns small group sizes for hot files in the stripe to achieve low repair cost and large group sizes for cold files to realize low storage overhead. It performs well under general coding parameters, adapts to irregular file sizes, provides high fault tolerance, and can be flexibly deployed to various data placements in real-world clustered storage systems. We implement our non-uniform LRC in a distributed storage prototype. Evaluations show that it greatly reduces the degraded read time and improves the node repair rate compared with the state-of-the-art wide stripe LRCs.

Training GNNs over large graphs faces a severe data processing bottleneck, involving both sampling and feature loading. To tackle this issue, we introduce F 2 CGT, a fast GNN training system incorporating feature compression. To avoid potential accuracy degradation, we propose a two-level, hybrid feature compression approach that applies different compression methods to various graph nodes. This differentiated choice strikes a balance between rounding errors, compression ratios, model accuracy loss, and preprocessing costs. Our theoretical analysis proves that this approach offers convergence and comparable model accuracy as the conventional training without feature compression. Additionally, we also co-design the on-GPU cache sub-system with compression-enabled training within F 2 CGT. The new cache sub-system, driven by a cost model, runs new cache policies to carefully choose graph nodes with high access frequencies, and well partitions the spare GPU memory for various types of graph data, for improving cache hit rates. Finally, extensive evaluation of F 2 CGT on two popular GNN models and four datasets, including three large public datasets, demonstrates that F 2 CGT achieves a compression ratio of up to 128 and provides GNN training speedups of 1.23-2.56× and 3.58--71.46× for single-machine and distributed training, respectively, with up to 32 GPUs and marginal accuracy loss.

Memory deduplication effectively relieves the memory space bottleneck by removing duplicate pages, especially in virtualized systems in which virtual machines run the same OS and similar applications. However, due to the non-uniform access latencies in NUMA architectures, memory deduplication poses a trade-off between memory savings and access performance: global deduplication across NUMA nodes realizes high memory savings, but leads to frequent cross-node remote access after deduplication and results in performance degradations. In contrast, local deduplication avoids remote access, but limits deduplication effectiveness. We design AdaptMD, an adaptive memory deduplication system that addresses the space-performance trade-off in NUMA architectures. AdaptMD leverages hotness awareness to globally deduplicate only cold pages to reduce remote access. It also migrates similar applications to the same NUMA node to allow local deduplication without remote access. We further make AdaptMD readily configurable to address various deployment scenarios. Experiments show that AdaptMD achieves high memory savings as in global deduplication, while achieving similar access performance as in local deduplication.

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.

Data-intensive applications executing on NVM-based storage systems experience serious bottlenecks when moving data between DRAM and NVM. We advocate for the use of the long-existing but recently neglected on-chip DMA to expedite data movement with three contributions. First, we explore new latency-oriented optimization directions, driven by a comprehensive DMA study, to design a high-performance DMA module, which significantly lowers the I/O size threshold to observe benefits. Second, we propose a new data movement engine, Fastmove , that coordinates the use of the DMA along with the CPU with DDIO-aware strategies, judicious scheduling, and load splitting such that the DMA’s limitations are compensated, and the overall gains are maximized. Finally, with a general kernel-based design, simple APIs, and DAX file system integration, Fastmove allows applications to transparently exploit the DMA and its new features without code change. We run three data-intensive applications MySQL, GraphWalker, and Filebench atop NOVA , ext4-DAX , and XFS-DAX , with standard benchmarks like TPC-C, and popular graph algorithms like PageRank. Across single- and multi-socket settings, compared to the conventional CPU-only NVM accesses, Fastmove introduces to TPC-C with MySQL 1.13–2.16× speedups of peak throughput, reduces the average latency by 17.7–60.8%, and saves 37.1–68.9% CPU usage spent in data movement. It also shortens the execution time of graph algorithms with GraphWalker by 39.7–53.4%, and introduces 1.01–1.48× throughput speedups for Filebench.

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

The recent emergence of commodity persistent memory (PM) hardware has altered the landscape of the storage hierarchy. It brings multi-fold benefits to database systems, with its large capacity, low latency, byte addressability, and persistence. However, PM has not been incorporated into the popular disaggregated architecture of cloud-native databases.

There is a fundamental tension between metadata scalability and POSIX semantics within distributed file systems. The bottleneck lies in the coordination, mainly locking, used for ensuring strong metadata consistency, namely, atomicity and isolation. CFS is a scalable, fully POSIX-compliant distributed file system that eliminates the metadata management bottleneck via pruning the scope of critical sections for reduced locking overhead. First, CFS adopts a tiered metadata organization to scale file attributes and the remaining namespace hierarchies independently with appropriate partitioning and indexing methods, eliminating cross-shard distributed coordination. Second, it further scales up the single metadata shard performance by single-shard atomic primitives, shortening the metadata requests' lifespan and removing spurious conflicts. Third, CFS drops the metadata proxy layer but employs the light-weight, scalable client-side metadata resolving. CFS has been running in the production environment of Baidu AI Cloud for three years. Our evaluation with a 50-node cluster and microbenchmarks shows that CFS simultaneously improves the throughput of baselines like HopsFS and InfiniFS by 1.76--75.82× and 1.22--4.10×, and reduces their average latency by up to 91.71% and 54.54%, respectively. Under cases with higher contention and larger directories, CFS' throughput benefits expand by one order of magnitude. For three real-world workloads with data accesses, CFS introduces 1.62--2.55× end-to-end throughput speedups and 35.06--62.47% tail latency reductions over InfiniFS.

Caching is crucial for accelerating data access, employed as a ubiquitous design in modern systems at many parts of computer systems. With increasing core count, and shrinking latency gap between cache and modern storage devices, hit-path scalability becomes increasingly critical. However, existing production in-memory caches often use list-based management with promotion on each cache hit, which requires extensive locking and poses a significant overhead for scaling beyond a few cores. Moreover, existing techniques for improving scalability either (1) only focus on the indexing structure and do not improve cache management scalability, or (2) sacrifice efficiency or miss-path scalability.

It remains challenging to train billion-scale DNN models on a single modern multi-GPU server due to the GPU memory wall. Unfortunately, existing memory-saving techniques such as GPU-CPU swap, recomputation, and ZeRO-Series come at the price of extra computation, communication overhead, or limited memory reduction.We present MPress, a new single-server multi-GPU system that breaks the GPU memory wall of billion-scale model training while minimizing extra cost. MPress first discusses the trade-offs of various memory-saving techniques and offers a holistic solution, which alternatively chooses the inter-operator parallelism with low cross-GPU communication traffics, and combines with recomputation and swap, to balance training performance and sustained model sizes. Additionally, MPress employs a novel, fast D2D swap technique, which simultaneously utilizes multiple high-bandwidth NVLink to swap tensors to light-load GPUs, based on a key observation that inter-operator parallel training may result in imbalanced GPU memory utilization and spare memory space from least used devices plus the high-end interconnects among them have the opportunity to support low-overhead swapping. Finally, we integrate MPress with PipeDream and DAPPLE, two representative inter-operator parallel training systems. Experimental results with two popular DNN models, Bert, and GPT, on two modern GPU servers from the DGX-1 and DGX-2 generation, equipped with 8 V100 or A100 cards, respectively, demonstrate that MPress significantly improves the training throughput over ZeRO-Series with the identical memory reduction, while being able to train larger models than the recomputation baseline.

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

As a fundamental tool for graph analysis, random walk receives extensive attention in both industry and academia. For computing massive random walks, recent works show that GPUs provide a good option to accelerate the performance. However, due to the limited memory space of modern GPUs, it is infeasible to have both the graph data and walk index fully reside in GPU memory when running large-scale random walks. Thus, it necessitates an out-of-GPU-memory design, but this inevitably induces large amounts of CPU-GPU data transmission traffic and thus hinders the overall performance. In this paper, we develop LightTraffic, which optimizes the data transmission between CPU and GPU memory under the constraint of GPU memory capacity with various system designs, including a memory-efficient scheme for partition-based management and multiple scheduling techniques. LightTraffic is a fully out-of-GPU-memory design, so it supports running large-scale random walks on GPUs. Experiments on our prototype show that LightTraffic outperforms various state-of-the-art CPU-based in-memory systems which also support large-scale random walks. For example, compared to the CPU-based systems FlashMob and ThunderRW, which are highly optimized for random walks, LightTraffic achieves 1.7−5.0× and 1.4 − 12.8× performance speedup, respectively. It also achieves up to an order of magnitude speedup when compared to the GPU-based system Subway which also supports large-scale random walks with an out-of-GPU-memory design for graph data.

To utilize various resources efficiently, cloud data centers usually deploy Latency-Critical (LC) and Best-Effort (BE) applications as containers in their physical machines by assigning higher priorities for LC jobs to use the resources. Due to the increase on the workload, it needs evicting some BE jobs to deprive more resources for LC jobs to meet the Quality of Service (QoS) requirements of LC jobs. Under dynamic workload settings, the frequent BE job eviction results in significant throughput degradation. To this end, we propose a novel Cost-AwaRe Eviction strategy, CARE, which takes into account both the recalculation cost and the remaining time cost of each BE job. CARE fully exploits the two types of different costs of BE jobs and chooses a BE job with the lowest overhead for eviction under different resource demands of LC jobs. Furthermore, CARE improves the throughput of BE jobs without affecting the performance of LC jobs. We prototype and implement CARE atop Kubernetes. Experimental results show that CARE achieves up to 1.70 × throughput gain compared to state-of-the-arts while its negative impact on the performance of LC jobs is negligible.

CephFS represents a prominent distributed file system that utilizes directory fragment migration to achieve improved runtime balance. However, its imprecise imbalance model and subtree selection algorithms can result in suboptimal performance. Our prior work, Lunule, enhances CephFS by introducing an imbalance factor model and a workload-aware load estimation policy. Nevertheless, Lunule’s built-in workload-aware planner still relies on a unified formula with adjustable coefficients, representing a one-size-fits-all approach. In this study, we introduce MUSE, a novel and user-friendly programmable interface that specifically focuses on subtree migration planning. MUSE effectively separates the complex and challenging task of evaluating subtree loads for different workloads, enabling designers to manipulate expected loads in the subsequent epoch. This facilitates the selection of appropriate subtrees for migration and opens up possibilities for implementing true isolated workloadaware policies. Through the utilization of two small Lua scripts, we demonstrate that MUSE achieves comparable load balancing effects and performance to CephFS and Lunule in workloads characterized by temporal and spatial locality.

Erasure coding is increasingly deployed in modern clustered storage systems to provide low-cost reliable storage. In particular, Locally Repairable Codes (LRCs) are a popular family of repair-efficient erasure codes that receive wide deployment in practice. In this paper, we analyze the storage process formulated as a data partitioning phase plus a node selection phase for LRCs in clustered storage systems. We show that the conventional flat partitioning and random partitioning incur significant cross-cluster repair traffic, while the random node selection causes storage and network imbalance. To this end, we design a new storage scheme composed of an optimal partitioning strategy and an enhanced node selection strategy for LRCs. Our partitioning strategy minimizes the cross-cluster repair traffic by dividing each group of blocks into the minimum number of clusters and further compactly placing the blocks. Our node selection strategy improves load balance by choosing less-loaded clusters and nodes to store blocks with potential higher access frequency at higher priority. We implement our storage scheme on a key-value store prototype atop Memcached. Evaluation on a LAN testbed shows that our scheme greatly improves the repair performance and load balance ratio compared to the baseline.

Containerized deployment of microservices has been becoming prevalent, as it provides flexible deployment and elastic resource configuration. For high concurrency and fault tolerance, multiple container replicas are often deployed for each microservice component, but this may induce heavy cross-machine traffic and degrades the performance of microservice applications. Traffic localization tries to put containers with heavy communication traffic on the same machine to reduce cross-machine traffic. However, it is still very common to have the containers with heavy traffic on different machines, especially under multi-replica deployment, due to the insufficient resources of a physical machine. To this end, we develop a network-aware scheduling system OptTraffic, which realizes optimized traffic scheduling for containerized microservices. OptTraffic estimates the traffic between each pair of containers in a lightweight manner by combining a simple math calculation with coarse-grained monitoring, then it proposes an efficient traffic allocation algorithm and leverages dynamic scheduling with multiple optimizations to minimize the cross-machine traffic without sacrificing resource usage balance. Experiments show that under multi-replica deployment, OptTraffic can save up to 47% of the network bandwidth, while reducing the P99 latency by 28%-45%, compared to Kubernetes and existing traffic localization designs for real-world microservice applications.

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

Large pages are widely supported in modern hardware and OSes to reduce the overhead of TLB misses. However, memory deduplication can be inefficient with large pages, leading to low memory utilization. To simultaneously enjoy the benefits of high performance by accessing memory with large pages (e.g., 2 MB pages) and high deduplication rate by managing memory with base pages (e.g., 4 KB pages), we proposeSmartMemoryDeduplciation (SmartMD), which is an adaptive and efficient memory management scheme via mixed pages. Specifically, we propose lightweight schemes to periodically monitor pages’ access frequency and repetition rate, and present an adaptive conversion scheme to selectively split or reconstruct large pages. We further optimize SmartMD by developing SmartMD$^{+}$, which dynamically adjusts the page scanning cycle by monitoring the TLB miss cost, and reconstructs the split large pages in an on-demand way so as to reduce the CPU overhead of SmartMD. We further implement a prototype system and conduct extensive experiments with various workloads under different system settings. Experiment results show that SmartMD and SmartMD$^{+}$can simultaneously achieve high access performance similar to systems using large pages, and achieve a deduplication rate similar to that applying aggressive deduplication scheme (i.e., KSM) on base pages.

In clouds and data centers, GPU servers with multiple GPUs are widely deployed. Current state-of-the-art GPU scheduling policies are “static” in assigning applications to different GPUs. These policies usually ignore the dynamics of the GPU utilization and are often inaccurate in estimating resource demand before assigning/running applications, so there is a large opportunity to further balance the loads and improve GPU utilization. Based on CUDA (Compute Unified Device Architecture), we develop a runtime system called DCUDA which supports“dynamic”scheduling of running applications between multiple GPUs. In particular, DCUDA takes into consideration multidimensional resources, including computing cores, memory usage, and energy consumption. It first provides a real-time and lightweight method to accurately monitor the resource demand of applications and GPU utilization. Furthermore, it provides a universal migration facility to migrate“running applications”between GPUs with negligible overhead. More importantly, DCUDA transparently supports all CUDA applications without changing their source code. Experiments with our prototype system show that DCUDA can reduce 78.3% of overloaded time of GPUs on average. As a result, for different workloads consisting of a wide range of applications we studied, DCUDA can reduce the average execution time of general applications by up to 42.1%, and even up to 67% for memory-intensive tasks. Besides, DCUDA also reduces 13.3% of energy in light-load scenarios.

Random walk is widely applied to sample large-scale graphs due to its simplicity of implementation and solid theoretical foundations of bias analysis. However, its computational efficiency is heavily limited by theslow convergencerate (a.k.a. long burn-in period). To address this issue, we propose a common neighbor aware random walk framework called CNARW, which leverages weighted walking by differentiating the next-hop candidate nodes to speed up the convergence. Specifically, CNARW takes into consideration the common neighbors between previously visited nodes and next-hop candidate nodes in each walking step. Based on CNARW, we further develop two efficient “unbiased sampling” schemes, and we also design two variant algorithms which can reduce sampling cost and speed up the convergence. Experimental results on real-world network datasets show that our approach converges remarkably faster than the state-of-the-art random walk sampling algorithms; and to achieve the same estimation accuracy, our approach reduces the query cost significantly. Last, we use two case studies to demonstrate the effectiveness of our sampling framework in solving large-scale graph analysis tasks.

Persistent key-value (KV) stores are mainly designed based on the Log-Structured Merge-tree (LSM-tree), yet they suffer from large read and write amplifications, especially when KV stores grow in size. Existing design optimizations for LSM-tree-based KV stores often make certain trade-offs and fail to simultaneously improve both the read and write performance on large KV stores without sacrificing scan performance. We design UniKV, which unifies the key design ideas of hash indexing and the LSM-tree in a single system. Specifically, UniKV leverages data locality to differentiate the indexing management of KV pairs. It also develops multiple techniques (e.g., merge with partial KV separation, dynamic range partitioning) to tackle the issues caused by unifying the indexing techniques, so as to simultaneously improve the performance in reads and writes. Furthermore, it proposes a parallel optimization scheme to manage partitions in parallel and develops multiple strategies to optimize the scan performance. Experiments show that UniKV significantly outperforms several state-of-the-art KV stores (e.g., LevelDB, RocksDB, PebblesDB and Titan) in overall throughput under read-write mixed workloads.

In this paper, we study sensing data collection of IoT devices in a sparse IoT-sensor network, using an energy-constrained Unmanned Aerial Vehicle (UAV), where the sensory data is stored in IoT devices while the IoT devices may or may not be within the transmission range of each other. We formulate two novel data collection problems to fully or partially collect data stored from IoT devices using the UAV, by finding a closed tour for the UAV that consists of hovering locations and the sojourn duration at each of the hovering locations such that the accumulative volume of data collected within the tour is maximized, subject to the energy capacity on the UAV, where the UAV consumes energy on both hovering for data collection and flying from one hovering location to another hovering location. To this end, we first propose a novel data collection framework that enables the UAV to collect sensory data from multiple IoT devices simultaneously if these IoT devices are within the coverage range of the UAV, through adopting the orthogonal frequency division multiple access (OFDMA) technique. We then formulate two data collection maximization problems to deal with full or partial data collection from IoT devices at each hovering location, and show that both defined problems are NP-hard. We instead devise approximation and heuristic algorithms for the problems. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrated that the proposed algorithms are promising.

Cloud block storage (CBS) serves as the fundamental infrastructure of modern cloud computing services like the cloud disk service. Large-scale cloud block storage usually adopts a layered architecture, including a forwarding layer with a cluster of proxy servers as proxies to provide cloud disk abstraction, and a unified distributed storage engine providing persisted data storage. However, as all I/O traffics go through the proxy servers in the forwarding layer, there may be a severe traffic imbalance between the proxy servers, which finally degrades the performance of cloud disks. To investigate the traffic imbalance problem in the forwarding layer, we first conduct an in-depth analysis on the workload traces of a large-scale cloud block storage system in production. We find that both the traffic of individual cloud disks and the consolidated traffic of cloud disks at proxy servers are highly skewed and fluctuate violently and frequently at a fine-grained time granularity, and thus causing severe traffic imbalance. To address the traffic imbalance issue, we then develop a low-cost migration algorithm, weighted partial migration (WPM), and conduct simulation analysis via trace replay to study its effectiveness. Experiments under real-world workloads show that for 84.3% of clusters, WPM can make the imbalance factor be smaller than 3 (i.e., the maximum traffic at a proxy server is within 3$\times$ of the median traffic), with a very small migration cost by migrating only 0.1% segments.

Distributed graph systems often leverage a cluster of machines by partitioning a large graph into multiple small-size subgraphs. Thus, graph partition usually has a significant impact on the performance of distributed graph systems. However, existing widely used partition schemes in practical graph systems can realize a good balance only in one dimension, e.g., either the number of vertices or the number of edges, and they may also incur lots of edge cuts. To address the problem, we develop BPart, which adopts a two-phase partition scheme to realize two-dimensional balance for both vertices and edges. Its core idea is to first partition the original graph into more small pieces than the cluster scale, and combine the partition to realize desired properties, then selectively combine the small pieces to construct larger subgraphs to generate two-dimensional balanced partition. We implement BPart into two open-source distributed graph systems, Gemini [58] and KnightKing [57]. Results show that BPart realizes good balance in both dimensions, and also significantly reduces the number of edge cuts. As a result, BPart reduces the total running time of various graph applications by 5% - 70%, compared to multiple existing partition schemes, e.g., Chunk-V, Chunk-E, Fennel, and Hash.

Modern clustered storage systems increasingly adopt erasure coding to realize reliable data storage at low storage redundancy. Locally Repairable Codes (LRC) are a family of practical erasure codes with high repair efficiency. Among various LRC constructions, Optimal-LRC is a recently proposed LRC approach that achieves the optimal Minimum Hamming Distance with low theoretical repair costs. In this paper, we consider the repair performance of Optimal-LRC in clustered storage systems. We show that the conventional flat data placement and random data placement incur substantial cross-cluster repair traffic, which impairs the repair performance. To this end, we design an optimal data placement scheme that provably minimizes the cross-cluster repair traffic, by carefully placing each group of blocks in Optimal-LRC into a minimum number of clusters subject to single-cluster fault tolerance. We implement our optimal data placement scheme on a key-value store prototype atop Memcached, and show via LAN testbed experiments that the optimal data placement significantly improves the repair performance compared to the conventional data placements.

Erasure coding is a storage-efficient redundancy scheme for modern clustered storage systems by storing stripes of data and parity blocks across the nodes of multiple clusters; in particular, locally repairable codes (LRC) continue to be one popular family of practical erasure codes that achieve high repair efficiency. To efficiently adapt to the dynamic requirements of access efficiency and reliability, storage systems often perform redundancy transitioning by tuning erasure coding parameters. In this paper, we apply a stripe merging approach for redundancy transitioning of LRC in clustered storage systems, by merging multiple LRC stripes to form a large LRC stripe with low storage redundancy. We show that the random placement of multiple LRC stripes that are being merged can lead to high cross-cluster transitioning bandwidth. To this end, we design an optimal data placement scheme that provably minimizes the cross-cluster traffic for stripe merging, by judiciously placing the blocks to be merged in the same cluster while maintaining the repair efficiency of LRC. We prototype and implement our optimal data placement scheme on a local cluster. Our evaluation shows that it significantly reduces the transitioning time by up to 43.2% compared to the baseline.

As one of the most popular in-memory cache systems, Redis provides low-latency and high-performance data access for modern internet services. However, in large-scale Redis systems, the access skewness and locality in storage workloads induce a small number of hot-spot instances with degraded system performance and massive cold instances with low CPU utilization. This paper proposes HPUCache to address the hot-spots via data copying and cold instances via instance merging. HPUCache fully utilizes the cached mapping in Redis client, and dynamically updates this mapping to enable access to the multiple data copies. Hence it can manage multiple copies achieving both Redis client compatibility and high user access performance. It also proposes an asynchronous instance merging strategy based on disk snapshots and temporal caches, which separates the massive data movement from the critical user access path to achieve high performance instance merging. We integrate HPUCache into Redis. Experiments under two types of workloads show that, compared to the native Redis design, HPUCache achieves 2.4× and 3.5× performance gains, 2× and 6× CPU utilization gains respectively.

Traditional in-memory graph storage systems have limited scalability due to the limited capacity and volatility of DRAM. Emerging persistent memory (PMEM), with large capacity and non-volatility, provides us an opportunity to realize the scalable and high-performance graph stores. However, directly moving existing DRAM-based graph storage systems to PMEM would cause serious PMEM access inefficiency issues, including high read and write amplification in PMEM and costly remote PMEM accesses across NUMA nodes, thus leading to the performance bottleneck. In this paper, we propose XPGraph, a PMEM-based graph storage system for managing large-scale evolving graphs, by developing an XPLine-friendly graph access model with vertex-centric graph buffering, hierarchical vertex buffer managing, and NUMA-friendly graph accessing. Experimental results show that XPGraph achieves 3.01× to 3.95× higher update performance and up to 4.46× higher query performance, compared with the state-of-the-art in-memory graph storage system implemented on a PMEM-based system.

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

In modern solid-state drives (SSDs), a flash translation layer (FTL) is the core engine performing the logical-to-physical address translations. However, the increasing capacity of SSDs requires a large DRAM space to hold the mapping table in a page-level FTL. Due to the limited size of built-in DRAM, existing FTL schemes selectively cache some active mapping entries in DRAM, while store the entire mapping table on flash. However, the low cache hit ratio introduced by the traditional mapping entry eviction policy degrades the access performance of SSDs. In this article, we propose a novel FTL, hot-clusterity FTL (HCFTL), to improve the hit ratio of cached mapping table (CMT) of SSDs with limited cache space. HCFTL clusters mapping entries, which are newly evicted from the cache, into dynamic translation pages (DTPs). Reading entries from DTPs will increase the CMT hit ratio due to spatial and temporal localities. Because the logical page numbers (LPNs) in a DTP are not consecutive, we introduce two different efficient index structures to speedup the lookup of mapping entries in DTPs. Furthermore, to make the DTP index highly accurate, we additionally allocate an auxiliary cache to buffer the mapping entries newly evicted from CMT, and produce dynamic pages with minimum difference between the maximal and the minimal LPNs of entries in those pages. Our experiments show that HCFTL can improve the CMT hit ratio by up to 41.1% and decrease the system response time by up to 33.3%, compared to baseline FTL schemes.

Understanding sign gestures is an essential step to helping individuals with hearing impaired. The existing works can only identify a small set of gestures accurately and the accuracy rate drops sharply with an increasing number of gestures. Because there are two challenges—a large number of similar gestures in sign language and the various signing speed of different people. Based on commercial smart bracelets, this article proposes a large-vocabulary sign language recognition system (which we call L-sign). First, we propose an entropy-based forward and backward matching algorithm to segment each gesture signal. Second, we design a gesture recognizer including a candidate gesture generator and semantic-based voter. The candidate gesture generator is aimed at providing candidate gesture designs based on a 3-branch convolutional neural network. The purpose of a semantic-based voter is to select the target gesture from candidate gestures by scoring, where the semantic distances between the last gesture in the current sentence and any candidate gestures is calculated, and a multilayer k-means algorithm is proposed to obtain a multilayer sign word structure to complete the scores of candidate gestures. Lastly, we deployed L-sign on the MYO bracelet. For 200 commonly used Chinese sign gestures, the experimental results show that the average accuracy rate was greater than 90%.

Traditional graph systems mainly use the iteration-based model, which iteratively loads graph blocks into memory for analysis so as to reduce random I/Os. However, this iteration-based model limits the efficiency and scalability of running random walk, which is a fundamental technique to analyze large graphs. In this article, we first propose a state-aware I/O model to improve the I/O efficiency of running random walk, then we develop a block-centric indexing and buffering scheme for managing walk data, and leverage an asynchronous walk updating strategy to improve random walk efficiency. We implement an I/O-efficient graph system, GraphWalker , which is efficient to handle very large disk-resident graphs and also scalable to run tens of billions of random walks with only a single commodity machine. Experiments show that GraphWalker can achieve more than an order of magnitude speedup when compared with DrunkardMob, which is tailored for random walks based on the classical graph system GraphChi, as well as two state-of-the-art single-machine graph systems, Graphene and GraFSoft. Furthermore, when compared with the most recent distributed system KnightKing, GraphWalker still achieves comparable performance with only a single machine, thereby making it a more cost-effective alternative.

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.

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

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

As applications are often allocated more memory than they actually used to cope with peak memory demand due to the workload dynamics in virtualized systems running multiple virtual machines, memory adjustment by reclaiming inactive memory in virtual machines is an effective way to enable memory overcommitment so as to reduce the cost. However, existing schemes are designed based on one-shot adjustment, which may reclaim a large size in a single operation, and they are unaware of both memory access dynamics and memory sensitivity of different applications, so they usually result in excessive reclamation and lead to severe performance slowdown. To address this issue, we propose PMA, a progressive memory adjustment scheme that takes into consideration both memory access dynamics and memory sensitivity and leverages virtual machine performance feedback to progressively reclaim inactive memory to avoid performance slowdown. Besides, PMA is designed based on ballooning (i.e., the balloon driver) so it preserves the good isolation between host and virtual machines for full virtualization systems. We also implement a prototype in host user space, and experiments show that PMA effectively limits the performance drop of memory overcommitment (e.g., the performance drop of every virtual machine is limited within 10% for up to 33% memory overcommitment), which is already very close to the optimal case of having enough memory, so PMA is efficient to enable memory overcommitment with performance guarantee in full virtualization systems.

For a decade, the Ceph distributed file system (CephFS) has been widely used to serve the ever-growing big data in many key fields ranging from Internet services to AI computing. To scale out the massive metadata access, CephFS adopts a dynamic subtree partitioning method, splitting the hierarchical namespace and distributing subtrees across multiple metadata servers. However, this method suffers from a severe imbalance problem that may result in poor performance due to its inaccurate imbalance prediction, ignorance of workload characteristics, and unnecessary/invalid migration activities. To eliminate these inefficiencies, we propose Lunule, a novel CephFS metadata load balancer, which employs an imbalance factor model for accurately determining when to trigger re-balance and tolerate benign imbalanced situations. Lunule further adopts a workload-aware migration planner to appropriately select subtree migration candidates. Compared to baselines, Lunule achieves better load balance, increases the metadata throughput by up to 315.8%, and shortens the tail job completion time by up to 64.6% for five real-world workloads and their mixture, respectively. Besides, Lunule is capable of handling the metadata cluster expansion and the client workload growth, and scales linearly on a cluster of 16 MDSs.

Gradient compression is a promising approach to alleviating the communication bottleneck in data parallel deep neural network (DNN) training by significantly reducing the data volume of gradients for synchronization. While gradient compression is being actively adopted by the industry (e.g., Facebook and AWS), our study reveals that there are two critical but often overlooked challenges: 1) inefficient coordination between compression and communication during gradient synchronization incurs substantial overheads, and 2) developing, optimizing, and integrating gradient compression algorithms into DNN systems imposes heavy burdens on DNN practitioners, and ad-hoc compression implementations often yield surprisingly poor system performance.

Summary Cache management policy plays a key role in offering low latency access to flash‐based SSDs. Most existing solutions including LRU and its successors only focus on improving the cache hit ratio, but rarely consider to reduce the waiting time of the eviction operation in the page‐level mapping FTLs. As the workloads spreading across internal chips of modern flash‐based SSDs are often highly imbalanced when workloads are write‐intensive, the time cost of evicting a dirty page from cache varies in a wide range. In this paper, we propose a novel eviction‐cost‐aware cache management policy, called ECR, to minimize the eviction cost in write‐dominant applications. ECR gives a higher probability to evict a page, which causes the shortest waiting time in the corresponding chip queue. To achieve this, we introduce a monitor module to keep track of states of all chip queues, and a multi‐LRU list structure to accelerate the selection of a victim chip and a target page in cache to perform an eviction. Our experimental results show that ECR can significantly reduce the average response time by as much as 59.55% and 44.84% compared to LRU and GCaR‐CFLRU, respectively, where GCaR‐CFLRU is the combination of state‐of‐the‐art algorithm GCaR and CFLRU.

Geo-replication is essential for providing low latency response and quality Internet services. However, designing fast and correct geo-replicated services is challenging due to the complex trade-off between performance and consistency semantics in optimizing the expensive cross-site coordination. State-of-the-art solutions rely on programmers to derive sufficient application-specific invariants and code specifications, which is both time-consuming and error-prone. In this paper, we propose an end-to-end geo-replication deployment framework AUTOGR (AUTOmated Geo-Replication) to free programmers from such label-intensive tasks. AutoGR enables the geo-replication features for non-replicated, serializable applications in an automated way with optimized performance and correct application semantics. Driven by a novel static analyzer RIGI, AUTOGR can extract application invariants by verifying whether their geo-replicated versions obey the serializable semantics of the non-replicated application. RIGI takes application codes as inputs and infers a set of side effects and path conditions possibly leading to consistency violations. RIGI employs the Z3 theorem prover to identify pairs of conflicting side effects and feed them to a geo-replication framework for automated across-site deployment. We evaluate AUTOGR by transforming four serializable and originally non-replicated DB-compliant applications to geo-replicated ones across 3 sites. Compared with state-of-the-art human-intervention-free automated approaches (e.g., strong consistency), AUTOGR reduces up to 61.8% latency and achieves up to 2.12X higher peak throughput. Compared with state-of-the-art approaches relying on a manual analysis (e.g., PoR), AUTOGR can quickly enable the geo-replication feature with zero human intervention while offering similarly low latency and high throughput.

Finding the set of most influential users in online social networks (OSNs) to trigger the largest influence cascade is meaningful, e.g., companies may leverage the “word-of-mouth” effect to trigger a large cascade of purchases by offering free samples/discounts to those most influential users. This task is usually modeled as an influence maximization problem, and it has been widely studied in the past decade. However, considering that users in OSNs may participate in various online activities, e.g., joining discussion groups and commenting on same pages or products, influence diffusion through online activities becomes even more significant. In this article, we study the impact of online activities by formulating social-activity networks which contain both users and online activities, and thus induce two types of weighted edges, i.e., edges between users and edges between users and activities. To address the computation challenge, we define an influence centrality via random walks, and use the Monte Carlo framework to efficiently estimate the centrality. Furthermore, we develop a greedy-based algorithm with novel optimizations to find the most influential users for node recommendation. Experiments on real-world datasets show that our approach is very computationally efficient under different influence models, and also achieves larger influence spread by considering online activities.

Wireless energy charging has emerged as a very promising technology for prolonging sensor lifetime in wireless rechargeable sensor networks (WRSNs). Existing studies focused mainly on the one-to-one charging scheme that a single sensor can be charged by a mobile charger at each time, this charging scheme however suffers from poor charging scalability and inefficiency. Recently, another charging scheme, the multi-node charging scheme that allows multiple sensors to be charged simultaneously by a mobile charger, becomes dominant, which can mitigate charging scalability and improve charging efficiency. However, most previous studies on this multi-node energy charging scheme focused on the use of a single mobile charger to charge multiple sensors simultaneously. For large scale WRSNs, it is insufficient to deploy only a single mobile charger to charge many lifetime-critical sensors, and consequently sensor expiration durations will increase dramatically. To charge many lifetime-critical sensors in large scale WRSNs as early as possible, it is inevitable to adopt multiple mobile chargers for sensor charging that can not only speed up sensor charging but also reduce expiration times of sensors. This however poses great challenges to fairly schedule the multiple mobile chargers such that the longest charging delay among sensors is minimized. One important constraint is that no sensor can be charged by more than one mobile charger at any time due to the fact that the sensor cannot receive any energy from either of the chargers or the overcharging will damage the recharging battery of the sensor. Thus, finding a closed charge tour for each of the multiple chargers such that the longest charging delay is minimized is crucial. In this paper we address the challenge by formulating a novel longest charging delay minimization problem. We first show that the problem is NP-hard. We then devise the very first approximation algorithm with a provable approximation ratio for the problem. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithm is promising, and outperforms existing algorithms in various settings.

With the rapid growth of congestion-sensitive and data-intensive applications, traditional settlement-free peering agreements with best-effort delivery often do not meet the QoS requirements of content providers (CPs). Meanwhile, Internet access providers (IAPs) feel that revenues from end-users are not sufficient to recoup the upgrade costs of network infrastructures. Consequently, some IAPs have begun to offer CPs a new type of peering agreement, called paid peering, under which they provide CPs with better data delivery quality for a fee. In this article, we model a network platform where an IAP makes decisions on the peering types offered to CPs and the prices charged to CPs and end-users. We study the optimal peering schemes for the IAP, i.e., to offer CPs both the paid and settlement-free peering to choose from or only one of them, as the objective is profit or welfare maximization. Our results show that 1) the IAP should always offer the paid and settlement-free peering under the profit-optimal and welfare-optimal schemes, respectively, 2) whether to simultaneously offer the other peering type is largely driven by the type of data traffic, e.g., text or video, and 3) regulators might want to encourage the IAP to allocate more network capacity to the settlement-free peering for increasing user welfare.

Key-value (KV) stores support many crucial applications and services. They perform fast in-memory processing but are still often limited by I/O performance. The recent emergence of high-speed commodity non-volatile memory express solid-state drives (NVMe SSDs) has propelled new KV system designs that take advantage of their ultra-low latency and high bandwidth. Meanwhile, to switch to entirely new data layouts and scale up entire databases to high-end SSDs requires considerable investment. As a compromise, we propose SpanDB, an LSM-tree-based KV store that adapts the popular RocksDB system to utilize selective deployment of high-speed SSDs . SpanDB allows users to host the bulk of their data on cheaper and larger SSDs (and even hard disc drives with certain workloads), while relocating write-ahead logs (WAL) and the top levels of the LSM-tree to a much smaller and faster NVMe SSD. To better utilize this fast disk, SpanDB provides high-speed, parallel WAL writes via SPDK, and enables asynchronous request processing to mitigate inter-thread synchronization overhead and work efficiently with polling-based I/O. To ease the live data migration between fast and slow disks, we introduce TopFS, a stripped-down file system providing familiar file interface wrappers on top of SPDK I/O. Our evaluation shows that SpanDB simultaneously improves RocksDB's throughput by up to 8.8 \times and reduces its latency by 9.5–58.3%. Compared with KVell, a system designed for high-end SSDs, SpanDB achieves 96–140% of its throughput, with a 2.3–21.6 \times lower latency, at a cheaper storage configuration.

Emerging graph neural networks (GNNs) have extended the successes of deep learning techniques against datasets like images and texts to more complex graph-structured data. By leveraging GPU accelerators, existing frameworks combine mini-batch and sampling for effective and efficient model training on large graphs. However, this setup faces a scalability issue since loading rich vertex features from CPU to GPU through a limited bandwidth link usually dominates the training cycle. In this article, we propose PaGraph, a novel, efficient data loader that supports general and efficient sampling-based GNN training on single-server with multi-GPU. PaGraph significantly reduces the data loading time by exploiting available GPU resources to keep frequently-accessed graph data with a cache. It also embodies a lightweight yet effective caching policy that takes into account graph structural information and data access patterns of sampling-based GNN training simultaneously. Furthermore, to scale out on multiple GPUs, PaGraph develops a fast GNN-computation-aware partition algorithm to avoid cross-partition access during data-parallel training and achieves better cache efficiency. Finally, it overlaps data loading and GNN computation for further hiding loading costs. Evaluations on two representative GNN models, GCN and GraphSAGE, using two sampling methods, Neighbor and Layer-wise, show that PaGraph could eliminate the data loading time from the GNN training pipeline, and achieve up to 4.8× performance speedup over the state-of-the-art baselines. Together with preprocessing optimization, PaGraph further delivers up to 16.0× end-to-end speedup.

Emerging graph neural networks (GNNs) have extended the successes of deep learning techniques against datasets like images and texts to more complex graph-structured data. By leveraging GPU accelerators, existing frameworks combine both mini-batch and sampling for effective and efficient model training on large graphs. However, this setup faces a scalability issue since loading rich vertices features from CPU to GPU through a limited bandwidth link usually dominates the training cycle. In this paper, we propose PaGraph, a system that supports general and efficient sampling-based GNN training on single-server with multi-GPU. PaGraph significantly reduces the data loading time by exploiting available GPU resources to keep frequently accessed graph data with a cache. It also embodies a lightweight yet effective caching policy that takes into account graph structural information and data access patterns of sampling-based GNN training simultaneously. Furthermore, to scale out on multiple GPUs, PaGraph develops a fast GNN-computation-aware partition algorithm to avoid cross-partition access during data parallel training and achieves better cache efficiency. Evaluations on two representative GNN models, GCN and GraphSAGE, show that PaGraph achieves up to 96.8% data loading time reductions and up to 4.8X performance speedup over the state-of-the-art baselines. Together with preprocessing optimization, PaGraph further delivers up to 16.0X end-to-end speedup.

Persistent key-value (KV) stores are mainly designed based on the Log-Structured Merge-tree (LSM-tree), which suffer from large read and write amplifications, especially when KV stores grow in size. Existing design optimizations for LSM-tree-based KV stores often make certain trade-offs and fail to simultaneously improve both the read and write performance on large KV stores without sacrificing scan performance. We design UniKV, which unifies the key design ideas of hash indexing and the LSM-tree in a single system. Specifically, UniKV leverages data locality to differentiate the indexing management of KV pairs. It also develops multiple techniques to tackle the issues caused by unifying the indexing techniques, so as to simultaneously improve the performance in reads, writes, and scans. Experiments show that UniKV significantly outperforms several state-of-the-art KV stores (e.g., LevelDB, RocksDB, HyperLevelDB, and PebblesDB) in overall throughput under read-write mixed workloads.

Erasure coding becomes increasingly popular in distributed storage systems (DSSes) for providing high reliability with low storage overhead. However, traditional random data placement causes massive cross-rack traffic and severely unbalanced load during failure recovery, degrading the recovery performance significantly. In addition, various erasure coding policies coexisting in a DSS exacerbates the above problem. In this paper, we propose PDL, a PBD-based Data Layout, to optimize failure recovery performance in DSSes. PDL is constructed based on Pairwise Balanced Design, a combinatorial design scheme with uniform mathematical properties, and thus presents a uniform data layout. Then we propose rPDL, a failure recovery scheme based on PDL. rPDL reduces cross-rack traffic effectively and provides nearly balanced cross-rack traffic distribution by uniformly choosing replacement nodes and retrieving determined available blocks to recover the lost blocks. We implemented PDL and rPDL in Hadoop 3.1.1. Compared with existing data layout of HDFS, experimental results show that rPDL reduces degraded read latency by an average of 62.83%, delivers 6.27× data recovery throughput, and provides evidently better support for front-end applications.

The ever-increasing demand of storage capacity and system performance leads to the scaling requirement in redundant arrays of independent disks (RAID)-structured storage systems. Existing approaches mainly focus on minimizing data migration in offline scenario, but not consider the user accesses issued by applications. However, in online scenario, the scaling I/Os and user I/Os usually interfere with each other, and result in significant performance degradation. Thus, it is of big significance to develop an efficient online scaling scheme to mitigate the impact of I/O interference. In this paper, we propose popularity-based online scaling (POS), which exploits workload locality by scaling storage zones with high popularity in a higher priority. POS can efficiently alleviate the interference between scaling I/Os and user I/Os, and it is also general enough to scale various RAID systems like RAID-0, RAID-5, and RAID-6. It can also be readily deployed atop various conventional RAID scaling approaches to improve their performance. To demonstrate the effectiveness of POS, we implement various conventional RAID scaling approaches, and also implement POS on top of these approaches for comparison. Extensive simulations with real-world workloads show that POS can efficiently reduce the response time of user requests and scaling I/Os, and also improves the sequentiality of data accesses.

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

In clouds and data centers, GPU servers which consist of multiple GPUs are widely deployed. Current state-of-the-art GPU scheduling algorithm are "static" in assigning applications to different GPUs. These algorithms usually ignore the dynamics of the GPU utilization and are often inaccurate in estimating resource demand before assigning/running applications, so there is a large opportunity to further load balance and to improve GPU utilization. Based on CUDA (Compute Unified Device Architecture), we develop a runtime system called DCUDA which supports "dynamic" scheduling of running applications between multiple GPUs. In particular, DCUDA provides a realtime and lightweight method to accurately monitor the resource demand of applications and GPU utilization. Furthermore, it provides a universal migration facility to migrate "running applications" between GPUs with negligible overhead. More importantly, DCUDA transparently supports all CUDA applications without changing their source codes. Experiments with our prototype system show that DCUDA can reduce 78.3% of overloaded time of GPUs on average. As a result, for different workloads consisting of a wide range applications we studied, DCUDA can reduce the average execution time of applications by up to 42.1%. Furthermore, DCUDA also reduces 13.3% energy in the light load scenario.

Docker containers are widely deployed to provide lightweight virtualization, and they have many desirable features such as ease of deployment and near bare-metal performance. However, both the performance and cache efficiency of containers are still limited by their storage drivers due to the coarse-grained copy-on-write operations, and the large amount of redundancy in both I/O requests and page cache. To improve I/O performance and cache efficiency of containers, we develop HP-Mapper, a high performance storage driver for Docker containers. HP-Mapper provides a two-level mapping strategy to support fine-grained copy-on-write with low overhead, and an efficient interception method to reduce redundant I/Os. Furthermore, it uses a novel cache management mechanism to reduce duplicate cached data. Experiment results with our prototype system show that HP-Mapper significantly reduces copy-on-write latency due to its finer-grained copy-on-write scheme. Moreover, HP-Mapper can also reduce 65.4% cache usage on average due to elimination of duplicated data. As a result, HP-Mapper improves the throughput of real-world workloads by up to 39.4%, and improves the startup speed of containers by 2.0x.

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

Wireless energy charging has emerged as a very promising technology for prolonging sensor lifetime in Wireless Rechargeable Sensor Networks (WRSNs). Existing studies focused mainly on the 'one-to-one' charging scheme that a sensor can be charged by a single mobile charger at each time, this charging scheme however suffers from poor charging scalability and inefficiency. Recently, another charging scheme - the 'multiple-to-one' charging scheme that allows multiple sensors to be charged simultaneously by a single charger, becomes dominant and can mitigate charging scalability and improve the charging efficiency. Most research studies on this latter scheme focused on the use of a mobile charger to charge multiple sensors simultaneously. However, for large scale WRSNs, it is insufficient to deploy just a single mobile charger to charge many lifetime-critical sensors, and consequently sensor expiration durations will increase dramatically. Instead, in order to charge as many as lifetime-critical sensors, the use of multiple mobile chargers for charging sensors can speed up sensor charging significantly, thereby reducing their expiration durations and improving the monitoring quality of WRSNs. However, this poses great challenges to schedule multiple mobile chargers for sensor charging at the same time such that the longest delay among the chargers is minimized due to multiple critical constraints. One such an important constraint in multiple mobile chargers is that each sensor cannot be charged by more than one mobile charger at each time; otherwise, the sensor cannot receive any energy from either of the chargers. In this paper we address this challenge by first formulating a novel longest delay minimization problem that is NP-hard. We then devise the very first approximation algorithm with a provable approximation ratio for the problem. We finally evaluate the performance of the proposed algorithm through experimental simulations. Simulation results demonstrate that the proposed algorithm is very promising, which outperforms the other heuristics in various settings.

Random walk is widely applied to sample large-scale graphs due to its simplicity of implementation and solid theoretical foundations of bias analysis. However, its computational efficiency is heavily limited by the slow convergence rate (a.k.a. long burn-in period). To address this issue, we propose a common neighbor aware random walk framework called CNARW, which leverages weighted walking by differentiating the next-hop candidate nodes to speed up the convergence. Specifically, CNARW takes into consideration the common neighbors between previously visited nodes and next-hop candidate nodes in each walking step. Based on CNARW, we further develop two efficient "unbiased sampling" schemes. Experimental results on real-world network datasets show that our approach converges remarkably faster than the state-of-the-art random walk sampling algorithms. Furthermore, to achieve the same estimation accuracy, our approach reduces the query cost (a measure of sampling budget) significantly. Lastly, we also use two case studies to demonstrate the effectiveness of our sampling framework in solving large-scale graph analysis tasks.

Due to individual unreliable commodity components, failures are common in large-scale distributed storage systems. Erasure codes are widely deployed in practical storage systems to provide fault tolerance with low storage overhead. However, the commonly used random data placement in storage systems based on erasure codes induces to heavy crossrack traffic, load imbalance, and random access, which slow down the recovery process upon failures. In this paper, with orthogonal arrays, we define a Deterministic Data Distribution (D3) of blocks to nodes and racks, and propose an efficient failure recovery approach based on D3. D3not only uniformly distributes data/parity blocks among storage servers, but also balances the repair traffic among racks and storage servers for failure recovery. Furthermore, D3also minimizes the cross-rack repair traffic for data layouts against a single rack failure and provides sequential access for failure recovery. We implement D3in Hadoop Distributed File System (HDFS) with a cluster of 28 machines. Our experiments show that D3significantly speeds up the failure recovery process compared with random data distribution, e.g., 2.21 times for (6, 3)-RS code in a system consisting of eight racks and three nodes in each rack.

In cloud computing, how to use limited hardware resources to meet the increasing demands has become a major issue. KSM (Kernel Same-page Merging) is a content-based page sharing mechanism used in Linux that merges equal memory pages, thereby significantly reducing memory usage and increasing the density of virtual machines or containers. However, KSM introduces a large overhead in CPU and memory bandwidth usage due to the use of red-black trees and content-based page comparison. To reduce the deduplication overhead, in this paper, we propose a new design called AMT-KSM, which leverages array mapped tries to realize lightweight memory deduplication. The basic idea is to divide each memory page into multiple segments and use the concatenated strings of the hash values of segments as indexed keys in the tries. By doing this, we can significantly reduce the time required for searching duplicate pages as well as the number of page comparisons. We conduct experiments to evaluate the performance of our design, and results show that compared with the conventional KSM, AMT-KSM can reduce up to 44.9% CPU usage and 31.6% memory bandwidth usage.

Persistent key-value (KV) stores mostly build on the Log-Structured Merge (LSM) tree for high write performance, yet the LSM-tree suffers from the inherently high I/O amplification. KV separation mitigates I/O amplification by storing only keys in the LSM-tree and values in separate storage. However, the current KV separation design remains inefficient under update-intensive workloads due to its high garbage collection (GC) overhead in value storage. We propose HashKV, which aims for high update performance atop KV separation under update-intensive workloads. HashKV uses hash-based data grouping , which deterministically maps values to storage space to make both updates and GC efficient. We further relax the restriction of such deterministic mappings via simple but useful design extensions. We extensively evaluate various design aspects of HashKV. We show that HashKV achieves 4.6× update throughput and 53.4% less write traffic compared to the current KV separation design. In addition, we demonstrate that we can integrate the design of HashKV with state-of-the-art KV stores and improve their respective performance.

Metadata performance in distributed file systems (DFS) is critical, due to the following trends: (a) the growing size of modern storage systems is expected to exceed billions of files and most files are small; (b) over half of the file accesses are metadata operations. In this work, we present SMeta, a metadata prefetching method that is seamlessly integrated into DFS for easy-of-use and significantly scales the metadata performance. Previous prefetching proposals primarily focus on mining groups of files that tend to be accessed together from the access history. Nevertheless, our study discovered that these solutions likely miss a huge number of correlated files whose co-occurrence frequency is not high enough. Unlike access correlations, we take a novel and completely different approach to explore explicit data correlations by understanding the reference relationships between files encoded in some forms of hyperlinks, which naturally exist in many applications. To embrace this new concept, SMeta explores correlations upon files are written via a light-weight pattern matching algorithm, stores correlations in the reserved extended attributes of file metadata to avoid changes in DFS APIs, and collapses multiple I/O rounds for accessing metadata of the target file and its data-correlated files into one round. A cost-efficient adaptive feedback mechanism is introduced to improve prefetching accuracy. We implemented SMeta atop of Ceph and evaluated it using synthetic and real system workloads. Compared to baselines, SMeta provides better metadata performance in terms of latency, throughput and scalability.

Solid-state drives (SSDs) are susceptible to the limited number of program/erase (P/E) cycles and uncorrectable flash errors, and hence achieving high reliability of SSD storage systems is a critical issue. RAID provides a viable option for enhancing system reliability by distributing redundancy across a number of SSDs. However, the flash error rate of an SSD increases with the number of P/E cycles, and this time-varying nature complicates the reliability analysis of SSD RAID. In addition, there remains very limited formal analysis that quantifies the reliability dynamics of an SSD RAID array under general settings. To this end, we propose a new continuous time Markov chain (CTMC) model to characterize the reliability dynamics of SSD RAID over time under two general settings: (1) fault tolerance against a general number of device failures and (2) non-uniform workload. We validate the correctness of our CTMC model via trace-driven simulations. Based on our model, we further analyze the impact of different RAID parameters on the reliability dynamics of an SSD RAID array.

With the rapid growth of congestion-sensitive and data-intensive applications, traditional settlement-free peering agreements with best-effort delivery often do not meet the QoS requirements of content providers (CPs). Meanwhile, Internet access providers (IAPs) feel that revenues from end-users are not sufficient to recoup the upgrade costs of network infrastructures. Consequently, some IAPs have begun to offer CPs a new type of peering agreement, called paid peering, under which they provide CPs with better data delivery quality for a fee. In this paper, we model a network platform where an IAP makes decisions on the peering types offered to CPs and the prices charged to CPs and end-users. We study the optimal peering schemes for the IAP, i.e., to offer CPs both the paid and settlement-free peering to choose from or only one of them, as the objective is profit or welfare maximization. Our results show that 1) the IAP should always offer the paid and settlement-free peering under the profit-optimal and welfare-optimal schemes, respectively, 2) whether to simultaneously offer the other peering type is largely driven by the type of data traffic, e.g., text or video, and 3) regulators might want to encourage the IAP to allocate more network capacity to the settlement-free peering for increasing user welfare.

In the “network-as-a-service” paradigm, network operators have a strong need to know the metrics of critical paths running services to their users/tenants. However, it is usually prohibitive to directly measure the metrics of all such paths due to the measuring overhead. A practical solution is to use network tomography to infer the metrics of such paths based on observations from a small number of monitoring nodes. This problem is termed as path identifiability problem, a new problem that largely differs from existing link identifiability problems. we show that the new problem is harder than link identifiability problems, in the sense that fewer monitors are required for identifying the metrics of given paths than for identifying the metrics of links along the paths. To solve the problem, we develop sufficient and necessary conditions for the identifiability of a given set of interested paths, and design an efficient algorithm that deploys the minimum number of monitors. Experiments show a saving of up to 40% fewer monitors that guarantee the identifiability of a given set of paths.

Flash-based SSDs are usually equipped with an onboard cache to further improve system performance by smoothing the gap between the upper-level applications and lower-level flash chips. Since modern SSDs are usually composed of multiple flash chips, and the load of flash chips are significantly different, it is very meaningful to be aware of the chip load condition when designing a cache replacement algorithm. Nevertheless, existing cache replacement algorithms only consider to reduce the cache miss ratio so as to reduce the I/O requests to the underlying flash memory as much as possible, none of them considers the load condition of flash chips. In this paper, we propose a Load- aware Cache Replacement algorithm, called LCR, to improve the performance of flash-based SSDs. The basic idea is to give a higher priority to cache the blocks on overloaded flash chips. We evaluate the performance of our scheme by using a trace- driven simulator with multiple real-world workloads, and results show that compared with the most common algorithm LRU and the state-of-the-art algorithm GCaR, LCR reduces the average response time by as much as 39.2% and 12.3%, respectively.

As Internet applications have become more diverse in recent years, users having heavy demand for online video services are more willing to pay higher prices for better services than light users that mainly use e-mails and instant messages. This encourages the Internet service providers (ISPs) to explore service differentiation so as to optimize their profits and allocation of network resources. Much prior work has focused on the viability of network service differentiation by comparing with the case of a single-class service. However, the optimal service differentiation for an ISP subject to resource constraints has remained unsolved. In this paper, we establish an optimal control framework to derive the analytical solution to an ISP's optimal service differentiation, i.e., the optimal service qualities and associated prices. By analyzing the structures of the solution, we reveal how an ISP should adjust the service qualities and prices in order to meet varying capacity constraints and users' characteristics. We also obtain the conditions under which ISPs have strong incentives to implement service differentiation and whether regulators should encourage such practices.

Parity-based RAID poses a design trade-off issue for large-scale SSD storage systems: it improves reliability against SSD failures through redundancy, yet its parity updates incur extra I/Os and garbage collection operations, thereby degrading the endurance and performance of SSDs. We propose EPLOG, a storage layer that reduces parity traffic to SSDs, so as to provide endurance, reliability, and performance guarantees for SSD RAID arrays. EPLOG mitigates parity update overhead via elastic parity logging, which redirects parity traffic to separate log devices (to improve endurance and reliability) and eliminates the need of pre-reading data in parity computations (to improve performance). We design EPLOG as a user-level implementation that is fully compatible with commodity hardware and general erasure coding schemes. We evaluate EPLOG through reliability analysis and trace-driven testbed experiments. Compared to the Linux software RAID implementation, our experimental results show that our EPLOG prototype reduces the total write traffic to SSDs, reduces the number of garbage collection operations, and increases the I/O throughput. In addition, EPLOG significantly improves the I/O performance over the original parity logging design, and incurs low metadata overhead.

Disk failures are very common in modern storage systems due to the large number of inexpensive disks. As a result, it takes a long time to recover a failed disk due to its large capacity and limited I/O. To speed up the recovery process and maintain a high system reliability, we propose a hierarchical code architecture with erasure codes, OI-RAID, which consists of two layers of codes, outer layer code and inner layer code. Specifically, the outer layer code is deployed with disk grouping technique based on Balanced Incomplete Block Design (BIBD) or complete graph with skewed data layout to provide efficient parallel I/O of all disks for fast failure recovery, and the inner layer code is deployed within each group of disks to provide high reliability. As an example, we deploy RAID5 in both layers to achieve fault tolerance of at least three disk failures, which meets the requirement of data availability in practical systems, as well as much higher speed up ratio for disk failure recovery than existing approaches. Besides, OI-RAID also keeps the optimal data update complexity and incurs low storage overhead in practice.

Parity declustering is widely deployed in erasure coded storage systems so as to provide fast recovery and high data availability. However, to perform scaling on such RAIDs, it is necessary to preserve the parity declustered data layout so as to guarantee the RAID performance after scaling. Unfortunately, existing scaling algorithms fail to achieve this goal so they can not be applied for scaling RAIDs which have deployed parity declustering. To address this challenge, we develop an efficient scaling algorithm called PDS (Parity Declustering Scaling). In particular, we first employ an auxiliary Balanced Incomplete Block Design (BIBD) to define the data migrations during scaling so as to preserve parity declustered data layout, and then define the addressing algorithm in the scaled system based on the migrations. We provide theoretical proofs to show that PDS preserves the parity declustered data layout, which is the basis for scaling RAIDs with parity declustering, and also theoretically prove that PDS achieves the even distribution of data/parity blocks after scaling and requires only the minimal data migrations. To show the performance of PDS, we implement it in MD in Linux Kernel, and conduct experiments with real-world traces. Results show PDS can reduce 89.70% of data migration time and 24.44% of user response time during scaling on average, compared with the round-robin scheme.

Nowadays many clustered file systems adopt asynchronous encoding which transforms replicated data into erasure coding to maintain data availability with bounded storage overhead. Existing implementations of asynchronous encoding construct coding stripes with logically sequential data blocks, which suffers from heavy cross-rack traffic and necessitates data block redistribution. Recent work [12] solves this problem by carefully distributing replicated data blocks among racks at the time when they are being written, but it is not applicable to the cases when existing systems have different data layouts or the data layout changes. In this paper, we propose Dynamic Stripe Construction (DSC) to transform N-way replication to erasure coding. DSC does not induce to any cross-rack traffic for encoding, and it does not require data block redistribution after encoding. Besides, DSC is general enough to be applied to any existing CFSes with various erasure codes, and it can also be deployed on a distributed file system in a hot-plugging-in manner. To validate the effectiveness of DSC, we implement it on HDFS. Through extensive testbed experiments in a real storage cluster, we show that DSC can significantly increase the encoding throughput and reduce the foreground user response time over the traditional approach.

As Internet applications have become more diverse in recent years, users having heavy demand for online video services are more willing to pay higher prices for better services than light users that mainly use e-mails and instant messages. This encourages the Internet Service Providers (ISPs) to explore service differentiations so as to optimize their profits and allocation of network resources. Much prior work has focused on the viability of network service differentiation by comparing with the case of a single-class service. However, the optimal service differentiation for an ISP subject to resource constraints has remained unsolved. In this work, we establish an optimal control framework to derive the analytical solution to an ISP's optimal service differentiation, i.e., the optimal service qualities and associated prices. By analyzing the structures of the solution, we reveal how an ISP should adjust the service qualities and prices in order to meet varying capacity constraints and users' characteristics. We also obtain the conditions under which ISPs have strong incentives to implement service differentiation and whether regulators should encourage such practices.

Scaling is often carried out in modern RAID systems to meet the ever increasing demand of storage capacity and I/O performance. However, the scaling process of RAID-5 system is not trivial, due to its specific data/parity layout. Previous approaches of RAID-5 scaling require either migrating almost all data blocks in the system, or recalculating all or some of the parity blocks during scaling. This paper proposes a new RAID-5 scaling approach called ISM (Intra-Stripe Migration). With ISM, data migrations only happen within stripes, which means that the coding relationship among blocks remains the same. Therefore, the parity blocks do not need to be recalculated after data migration, which greatly reduces the I/O and computational costs. The properties of ISM approach can be summarized as follows: (1) it requires the minimum amount of data blocks to be migrated, (2) it supports data migration without recalculating parity blocks, and (3) it supports multiple successive scaling operations while keeping the above properties. The simulation results on DiskSim show that: (1) ISM reduces the scaling time from 47.91% to 87.01% and from 88.94% to 96.58% compared with GSR and ALV respectively in offline scaling, (2) under two real-world I/O traces, ISM also outperforms GSR by 64.15% to 87.30%, and ALV by 92.38% to 95.98% in scaling time, and (3) ISM maintains almost the same performance of data access with ALV and GSR after scaling.

Redundant array of independent disk (RAID) offers a good option to provide device-level fault tolerance for solid-state drives (SSDs). However, parity update with either read-modify-write or read-reconstruct-write may introduce a lot of extra I/Os and thus significantly degrades SSD RAID performance. To reduce the parity update cost, elastic striping chooses to reconstruct new stripes with only the newly updated data chunks instead of directly updating parity chunks. However, it necessitates an RAID-level garbage collection (GC) process, which may incur a very high cost due to the mixture of hot and cold data chunks. To address this problem, we follow the idea of elastic striping and propose a workload-aware scheme (WAS) to reduce the RAID-level GC cost so as to improve the performance and endurance of SSD RAID. In particular, we first develop a novel lightweight hot data identification scheme which requires only a very small computation time and memory cost, then propose a hotness-aware elastic striping approach to separately write data chunks with different hotness to different regions in SSD RAID. To evaluate the effectiveness and efficiency of our WAS, we implement a prototype system on RAID-5 and RAID-6 arrays composed of commercial SSDs. Experimental results show that compared to original elastic striping, our scheme reduces 30.0%-70.6% (and 23.9%-63.2%) of chunk writes under the RAID-5 (and RAID-6) settings, and also reduces the average response time by 60.9%-79.3% (and 56.8%-80.9%) for RAID-5 (and RAID-6), respectively. Besides, our scheme also improves the endurance and reliability of SSD RAID compared to original elastic striping.

Internet services are traditionally priced at flat rates; however, many Internet service providers (ISPs) have recently shifted towards two-part tariffs where a data cap is imposed to restrain data demand from heavy users.Although the two-part tariff could generally increase the revenue for ISPs and has been supported by the US FCC, the role of data cap and its optimal pricing structures are not well understood.In this article, we study the impact of data cap on the optimal two-part pricing schemes for congestion-prone service markets.We model users' demand and preferences over pricing and congestion alternatives and derive the market share and congestion of service providers under a market equilibrium.Based on the equilibrium model, we characterize the two-part structures of the revenue-and welfare-optimal pricing schemes.Our results reveal that 1) the data cap provides a mechanism for ISPs to transition from the flat-rate to pay-as-you-go type of schemes, 2) both the revenue and welfare objectives of the ISP will drive the optimal pricing towards usage-based schemes with diminishing data caps, and 3) the welfare-optimal tariff comprises lower fees than the revenue-optimal counterpart, suggesting that regulators might want to promote usage-based pricing but regulate the lump-sum and per-unit fees.

Parity-based RAID poses a design trade-off issue for large-scale SSD storage systems: it improves reliability against SSD failures through redundancy, yet its parity updates incur extra I/Os and garbage collection operations, thereby degrading the endurance and performance of SSDs. We propose EPLOG, a storage layer that reduces parity traffic to SSDs, so as to provide endurance, reliability, and performance guarantees for SSD RAID arrays. EPLOG mitigates parity update overhead via elastic parity logging, which redirects parity traffic to separate log devices (to improve endurance and reliability) and eliminates the need of pre-reading data in parity computations (to improve performance). We design EPLOG as a user-level implementation that is fully compatible with commodity hardware and general erasure coding schemes. We evaluate EPLOG through reliability analysis and trace-driven testbed experiments. Compared to the Linux software RAID implementation, our experimental results show that our EPLOG prototype reduces the total write traffic to SSDs, reduces the number of garbage collection operations, and increases the I/O throughput. In addition, EPLOG significantly improves the I/O performance over the original parity logging design, and incurs low metadata overhead.

A lot of inexpensive disks in modern storage systems induce frequent disk failures. It takes a long time to recover a failed disk due to its large capacity and limited I/O. This paper proposes a hierarchical architecture of erasure code, OI-RAID. OI-RAID consists of two layers of codes, outer layer code and inner layer code. The outer layer code is based on disk grouping and Balanced Incomplete Block Design (BIBD) with skewed data layout to provide efficient parallel I/O of all disks for failure recovery. Inner layer code is deployed within a group of disks. As an example, we deploy RAID5 in both layers and present detailed performance analysis. With RAID5 in both layers, OI-RAID tolerates at least three disk failures meeting practical data availability, and achieves much higher speed up of disk failure recovery than existing approaches, while keeping optimal data update complexity and practically low storage overhead.

In parity-based RAID arrays, to update a data chunk, the corresponding parity chunk(s) must be updated accordingly so as to keep data consistency and availability. To achieve this, either read-modify-write (RMW) or read-construct-write (RCW) could be used. Traditional parity update algorithm always selects the one requiring fewer pre-reads so as to reduce the total number of I/Os, but it may aggravate the skewness of I/O queues on disks, and thus degrades the system performance. In this paper, we propose a balanced parity update algorithm with queueing length awareness, BPU, which takes the number of pre-reads, the skewness of I/O queues on disks, and real-time workload into consideration when selecting RCW or RMW to update parity chunks. We implement a prototype system with BPU to evaluate its performance. Experimental results show that the length of I/O queues on disks in a RAID array may be highly skewed when using traditional parity update algorithm, and thus severely degrades the system performance. With BPU, we can reduce the average response time by up to 10%. We also study the performance of BPU under different system configurations, and provide multiple insights for adjusting the parameters of BPU so as to optimize its performance.

Key-value stores are widely used to provide much higher read and write throughput than traditional SQL databases. LSMT (log structure merge tree) based key-value store, as one type of key-value stores, is applied in many practical systems since it could eliminate random writes and provide good read performance at the same time. However, the data residing in disk needs compaction operations from time to time, which takes a large amount of I/O resources. Since disk access speed is much slower than DRAM and most data resides in disks, the compaction operation will significantly influence the system performance. In this paper, we propose a grouped level structure, which divides each level in LSMT into multiple groups. Also, we propose a new compaction method for the grouped level structure to reduce the compaction I/O overhead. Our experiments show that the grouped level structure saves about 55% to 78% I/O resource of compaction, so it improves the write throughput by 69% to 284%, but only reduces the read throughput by 5% to 9%. It improves the overall throughput by 30% to 69% with read dominated workloads of 25% write operations and 75% read operations.

Software-Defined Networking (SDN) has emerged as the paradigm of the next-generation networking through separating the data control plane from the data plane. The forwarding routing table at each of its switch nodes is usually implemented by expensive and power-hungry Ternary Content Addressable Memory (TCAM) that only has limited number of entries, and the bandwidth at each of its links is bounded too. Under this new network architecture, providing a quality service to users by admitting user requests to meet their resource demands is challenging, and very little attention has ever been paid in this regard. In this paper, we will study online unicast and multicast request admissions in SDNs with the aim to maximize the network throughput under both critical network resources and user bandwidth demand constraints, for which we first propose a novel model to characterize the usage costs of node and link resources. We then devise efficient online algorithms for unicast and multicast requests. We also analyze the competitive ratios of the proposed online algorithms, which are O(log n) and O(Kϵlog n) for unicasting and multicasting, respectively, where n is the network size, K is the maximum number of members in a multicast request, and ϵ is a constant with 0 <; e ≤ 1. We finally evaluate the proposed algorithms empirically through simulations. The simulation results demonstrate that the proposed algorithms are very promising.

In recent years, there is an increasing demand of big memory systems so to perform large scale data analytics. Since DRAM memories are expensive, some researchers are suggesting to use other memory systems such as non-volatile memory (NVM) technology to build large-memory computing systems. However, whether the NVM technology can be a viable alternative (either economically and technically) to DRAM remains an open question. To answer this question, it is important to consider how to design a memory system from a "system perspective",that is, incorporating different performance characteristics andprice ratios from hybrid memory devices. This paper presents an analytical model of a "hybrid page cache system" so to understand the diverse design space and performance impact of a hybrid cache system. We consider (1) various architectural choices, (2) design strategies, and (3) configuration of different memory devices. Using this model, we provide guidelines on how to design hybrid page cache to reach a good trade-off between high system throughput (in I/O per sec or IOPS) and fast cache reactivity which is defined by the time to fill the cache. We also show how one can configure the DRAM capacity and NVM capacity under a fixed budget. We pick PCM as an example for NVM and conduct numerical analysis. Our analysis indicates that incorporating PCM in a page cache system significantly improves the system performance, and it also shows larger benefit to allocate more PCM in page cache in some cases. Besides, for the common setting of performance-price ratio of PCM, "flat architecture" offers as a better choice, but "layered architecture" outperforms if PCM write performance can be significantly improved in the future.

Modern SSDs have been a competitive alternative to traditional hard disks because of higher random access performance, lower power consumption and less noise. Although SSDs usually have multiple channels with each channel connected to multiple chips to improve their performance with parallel channels and chips, some recent studies show that contentions among I/O requests make SSDs read performance degrade notoriously, even worse than random write performance. Meanwhile, MLC/TLC flash memory technology increases modern SSDs' capacity while sacrificing their reliability. So fault tolerance, such as chip-level RAID, is also a necessity for SSDs. We propose a Balanced Redirected Read (BRR), which redirects some read requests from busy chips to relatively idle chips by decoding target data chunks with the data/parity chunks in a parity group. We also design a new layout of RAID-5 in SSDs, which distributes adjacent chips to different parity groups such that the degrees of loads on different chips in a group are more likely different. So BRR has more chances to redirect read requests from busy chips to idle chips. Compared with the recently proposed Parallel Issue Queuing (PIQ) using reordering I/O requests technique, BRR schedules the requests among chips more balanced. We implement BRR atop a trace driven simulator, and extensive experiments with real-world workloads show that BRR reduces the waiting time of read requests over PIQ (FIFO) by as much as 38.4% (77.1%) and averagely 14.2% (23.8%), and BRR can also slightly improve write performance due to the improvement of read performance.

It is inevitable to scale RAID systems with the increasing demand of storage capacity and I/O throughput. When scaling RAID systems, we will always need to update parity to maintain the reliability of the storage systems. There are two schemes, read-modify-write (RMW) and read-reconstruct-write (RCW), to update parity. However most existing scaling approaches simply use RMW to update parity. While in many scenarios for existing scaling approaches, RCW performs better in terms of the number of scaling I/Os. In this paper, we propose an algorithm, called EPU, to analyze which of RCW and RMW is better for a scaling scenario and select the more efficient one to save the scaling I/Os. We apply EPU to online scaling scenarios and further use two optimizations, I/O overlap and access aggregation, to enhance the online scaling performance. Using Scale-CRS, one of the existing scaling approaches, as an example, we show via numerical studies that Scale-CRS+EPU reduces the amount of scaling I/Os over the traditional Scale-CRS in many scaling cases. To justify the online efficiency of EPU, we implement both Scale-CRS+EPU and Scale-CRS in a simulator with Disksim as a working module. Through extensive experiments, we show that Scale-CRS+EPU reduces the scaling time and the online response time of user requests over Scale-CRS.

Although the travel time is the most important information in road networks, many spatial queries, e.g.,$k$-nearest-neighbor ($k$-NN) and range queries, for location-based services (LBS) are only based on the network distance. This is because it is costly for an LBS provider to collect real-time traffic data from vehicles or roadside sensors to compute the travel time between two locations. With the advance of web mapping services, e.g., Google Maps, Microsoft Bing Maps, and MapQuest Maps, there is an invaluable opportunity for using such services for processing spatial queries based on the travel time. In this paper, we propose a server-sideSpatialMashupService (SMS) that enables the LBS provider to efficiently evaluate$k$-NN queries in road networks using the route information and travel time retrieved from an external web mapping service. Due to the high cost of retrieving such external information, the usage limits of web mapping services, and the large number of spatial queries, we optimize the SMS for a large number of$k$-NN queries. We first discuss how the SMS processes a single$k$-NN query using two optimizations, namely,direction sharingandparallel requesting. Then, we extend them to process multiple concurrent$k$-NN queries and design a performance tuning tool to provide a trade-off between the query response time and the number of external requests and more importantly, to prevent a starvation problem in the parallel requesting optimization for concurrent queries. We evaluate the performance of the proposed SMS using MapQuest Maps, a real road network, real and synthetic data sets. Experimental results show the efficiency and scalability of our optimizations designed for the SMS.

To guarantee high reliability, solid-state drive (SSD)-based storage systems require data redundancy schemes, e.g., redundant array of independent disks (RAID) schemes. Traditional RAID-5, RAID-6, and Reed-Solomon codes can tolerate one, two, and an arbitrary number of device failures, respectively. However, some SSDs under those redundant configurations may age much faster than others because of the high skewness and locality of workloads. The uneven aging rates may make some SSDs wear out very quickly and decrease the endurance of SSD-based RAID arrays. To address this problem, we first come up with a diagonal coding scheme (DCS) by distributing the updating dependencies evenly among devices to improve the system-level wear-leveling. DCS can efficiently improve the array endurance if requests are aligned with the stripe size, i.e., when data symbols in the same stripe receive the same number of writes, while the number could be different for different stripes. To relax the above assumption, we further propose an enhanced scheme, DCS+. With a buffer design, DCS+ can improve the wear-leveling among devices under general access patterns via triggering different responses to different kinds of requests. We conduct extensive trace-driven evaluations based on real-world workloads, and results show that our design efficiently enhances the endurance of SSD-based RAID arrays.

System scaling becomes essential and indispensable for distributed storage systems due to the explosive growth of data volume. Considering that fault-protection is a necessity in large-scale distributed storage systems, and Cauchy Reed-Solomon (CRS) codes are widely deployed to tolerate multiple simultaneous node failures, this paper studies the scaling problem of distributed storage systems with CRS codes. In particular, we formulate the scaling problem with an optimization model in which both the post-scaling encoding matrix and the data migration policy are assumed to be unknown in advance. To minimize the I/O overhead, we propose a three-phase optimization scaling scheme for CRS codes. Specifically, we first derive the optimal post-scaling encoding matrix under a given data migration policy, then optimize the data migration process using the selected post-scaling encoding matrix, and finally exploit the Maximum Distance Separable (MDS) property to further optimize the designed data migration process. Our scaling scheme requires minimal data movement while achieving uniform data distribution. Moreover, it requires to read fewer data blocks than conventional minimum data migration schemes, but still guarantees the minimum amount of migrated data. To validate the efficiency of our scheme, we implement it atop a networked file system. Extensive experiments show that our scaling scheme uses less scaling time than the basic scheme.

RAID provides a good option to provide device-level fault tolerance. Conventional RAID usually updates parities with read-modify-write or read-reconstruct-write, which may introduce a lot of extra I/Os and thus significantly degrade SSD RAID performance. The recently proposed elastic striping scheme reconstructs new stripes with updated new data chunks without updating old parity chunks. However, it necessitates RAID-level garbage collection which may incur a very high cost. In this paper, we propose a hotness-aware caching scheme to buffer incoming writes and categorize data chunks in buffers into multiple groups according to their hotness values. We then propose a grouping-based elastic striping scheme to separately write data chunks in different groups into SSDs. We deployed the proposed schemes on a RAID-5 array composed of eight commercial SSDs, and experimental results show that compared to elastic striping, our scheme reduces 26% -- 65% of chunk writes to SSDs, and also reduces the average response time by 17.2% -- 63.9%.

The ever-increasing demand of storage capability leads to scaling requirement in RAID-structured storage systems. Previous approaches to RAID scaling mainly focus on minimizing data migration, without considering the user-level application accesses. However, the mixed scaling I/Os and user accesses in practical systems will interfere with each other, which results in significant performance degradation of both the data migration time and the user response time. In this paper, we divide the whole storage space into multiple zones and measure the popularity (mainly using the metric of access frequency) of each zone. Based on the measured popularity, we propose an online scheme, namely Popularity-based Online Scaling (POS), to scale RAID-structured storage systems. The main idea of POS is to scale storage areas with high popularity first so as to better exploit workload locality. POS can efficiently alleviate the performance degradation of user response time and data migration time during the scaling process. It can be readily deployed atop various conventional RAID scaling approaches to improve their performance. To evaluate the performance of POS, we implement FastScale and FastScale with POS (POS-FS) in the same system. Through extensive benchmark studies on real-system workloads, we show that POS can efficiently reduce the response time to user requests and scaling I/Os and improve the sequentiality of data accesses.

Most sampling techniques for online social networks (OSNs) are based on a particular sampling method on a single graph, which is referred to as a statistic. However, various realizing methods on different graphs could possibly be used in the same OSN, and they may lead to different sampling efficiencies, i.e., asymptotic variances. To utilize multiple statistics for accurate measurements, we formulate a mixture sampling problem, through which we construct a mixture unbiased estimator which minimizes the asymptotic variance. Given fixed sampling budgets for different statistics, we derive the optimal weights to combine the individual estimators; given a fixed total budget, we show that a greedy allocation towards the most efficient statistic is optimal. In practice, the sampling efficiencies of statistics can be quite different for various targets and are unknown before sampling. To solve this problem, we design a two-stage framework which adaptively spends a partial budget to test different statistics and allocates the remaining budget to the inferred best statistic. We show that our two-stage framework is a generalization of 1) randomly choosing a statistic and 2) evenly allocating the total budget among all available statistics, and our adaptive algorithm achieves higher efficiency than these benchmark strategies in theory and experiment.

Modern distributed storage systems often deploy deduplication to remove content-level redundancy and hence improve storage efficiency. However, deduplication inevitably leads to unbalanced data placement across storage nodes, thereby degrading read performance. This paper studies the load balance problem in the setting of a reliable distributed deduplication storage system, which deploys deduplication for storage efficiency and erasure coding for reliability. We argue that in such a setting, it is generally challenging to find a data placement that simultaneously achieves both read balance and storage balance objectives. To this end, we formulate a combinatorial optimization problem, and propose a greedy, polynomial-time Even Data Placement (EDP) algorithm, which identifies a data placement that effectively achieves read balance while maintaining storage balance. We further extend our EDP algorithm to heterogeneous environments. We demonstrate the effectiveness of our EDP algorithm under real-world workloads using both extensive simulations and prototype testbed experiments. In particular, our testbed experiments show that our EDP algorithm reduces the file read time by 37.41% compared to the baseline round-robin placement, and the reduction can further reach 52.11% in a heterogeneous setting.

Solid-state drives (SSDs) necessitate garbage collection (GC) to erase data blocks and reclaim the space of invalidated data, and GC inevitably introduces additional writes due to data relocation. The performance of GC, which is quantified by cleaning cost or write amplification, is critical to the overall performance of SSDs. However, characterizing GC performance is complicated by the general implementations of GC algorithms and the complex data locality characteristics of real-world workloads. This paper presents a general analytical study to characterize the performance impact of data locality on a general family of GC algorithms. We develop probabilistic models to address two fundamental issues: (1) What is the impact of data locality on the performance of locality-oblivious GC? (2) How can data locality be leveraged to improve the performance in locality-aware GC? We further conduct extensive trace-driven simulations on real-world workloads to validate the findings of our models.

Internet services are traditionally priced at flat rates; however, many Internet service providers (ISPs) have recently shifted towards two-part tariffs where a data cap is imposed to restrain data demand from heavy users and usage over the data cap is charged based on a per-unit fee. Although the two-part tariff could generally increase the revenue for ISPs and has been supported by the FCC chairman, the role of data cap and its revenue-optimal and welfare-optimal pricing structures are not well understood. In this paper, we study the impact of data cap on the optimal two-part pricing schemes for congestion-prone service markets, e.g., broadband or cloud services. We model users' demand and preferences over pricing and congestion alternatives and derive the market share and congestion of service providers under a market equilibrium. Based on the equilibrium model, we characterize the two-part structures of the revenue-optimal and welfare-optimal pricing schemes. Our results reveal that 1) the data cap provides a mechanism for ISPs to transition from flat-rate to pay-as-you-go type of schemes, 2) with growing data demand and network capacity, the revenue-optimal pricing moves towards usage-based schemes with diminishing data caps, and 3) the structure of the welfare-optimal tariff comprises lower fees and data cap than those of the revenue-optimal counterpart, suggesting that regulators might want to promote usage-based pricing but regulate the per-unit fees. Our results could help providers design revenue-optimal pricing schemes and guide regulatory authorities to legislate desirable regulations.

Distributed storage systems provide large-scale data storage services, yet they are confronted with frequent node failures. To ensure data availability, a storage system often introduces data redundancy via replication or erasure coding. As erasure coding incurs significantly less redundancy overhead than replication under the same fault tolerance, it has been increasingly adopted in large-scale storage systems. In erasure-coded storage systems, degraded reads to temporarily unavailable data are very common, and hence boosting the performance of degraded reads becomes important. One challenge is that storage nodes tend to be heterogeneous with different storage capacities and I/O bandwidths. To this end, we propose FastDR, a system that addresses node heterogeneity and exploits I/O parallelism, so as to boost the performance of degraded reads to temporarily unavailable data. FastDR incorporates a greedy algorithm that seeks to reduce the data transfer cost of reading surviving data for degraded reads, while allowing the search of the efficient degraded read solution to be completed in a timely manner. We implement a FastDR prototype, and conduct extensive evaluation through simulation studies as well as testbed experiments on a Hadoop cluster with 10 storage nodes. We demonstrate that our FastDR achieves efficient degraded reads compared to existing approaches.

In wireless networks, getting the global knowledge of channel state information (CSI, e.g., channel gain or link loss probability) is always beneficial for the nodes to optimize the network design. However, the node usually only has the local CSI between itself and other nodes, and lacks the CSI between any pair of other nodes. To enable all the nodes to get the global CSI, in this paper, we propose a network-coded third-party information exchange scheme, with an emphasis on minimizing the total transmission cost for ( ) exchanging the CSI among the nodes. We show that for a network of N nodes, if and only if any k nodes (1 ≤ k <; N) send at least (2 : k) packets, a feasible solution exists for third-party information exchange. Formulating the problem of feasible and optimal solutions as an integer linear programming (ILP) problem, we compute the optimal number of packets that must be transmitted by every node. Guided by the necessary and sufficient condition, we construct two practical transmission schemes: fair load (FL) scheme and proportional load (PL) scheme. A deterministic encoding strategy based on XORs coding over GF(2) is further designed to guarantee that with FL or PL scheme, each node finally can decode the complete packets. It is shown that in two specific networks, these two schemes are optimal, achieving the minimum transmission cost. In more general networks, simulation results show that PL is still close to optimal with a high probability. Finally, a distributed transmission protocol is developed, which allows FL and PL schemes to be operated in a distributed and hence scalable manner.

System scaling becomes essential and indispensable for distributed storage systems due to the explosive growth of data volume. As fault-protection is also a necessity in large-scale distributed storage systems, and Cauchy Reed-Solomon (CRS) codes are widely deployed to tolerate multiple simultaneous node failures, this paper studies the scaling of distributed storage systems with CRS codes. In particular, we formulate the scaling problem with an optimization model in which both the post-scaling encoding matrix and the data migration policy are assumed to be unknown in advance. To minimize the I/O overhead for CRS scaling, we first derive the optimal post-scaling encoding matrix under a given data migration policy, and then optimize the data migration process using the selected postscaling encoding matrix. Our scaling scheme requires the minimal data movement while achieving uniform data distribution. To validate the efficiency of our scheme, we implement it atop a networked file system. Extensive experiments show that our scaling scheme reduces 7.94% to 58.87%, and 39.52% on average, of the scaling time over the basic scheme.

Solid-state drives (SSDs) have been widely deployed in large-scale storage systems. To guarantee high reliability for SSD-based storage systems, it still requires data redundancy schemes, e.g., RAID schemes. Traditional RAID-5 shows its benefits in load-balancing and I/O parallelism, and so it is still the first choice for enhancing the reliability of SSD RAID arrays. However, some SSDs under the RAID-5 configuration may age much faster than others because of the non-uniformity of workloads, which makes them be worn out very quickly and so decreases the endurance of SSD-based RAID arrays. To address this problem, we develop a diagonal coding scheme, DCS5, to improve the wear-leveling among devices in an SSD-based RAID-5 array. DCS5 can efficiently improve the array endurance if accesses are aligned with the stripe size, i.e., When data symbols in the same stripe receive the same number of writes, while the number could be different for different stripes. To relax the above assumption, we further propose an enhanced scheme which is called as DCS5+. DCS5+ can improve the wear-leveling among devices under general access patterns via triggering different responses to different kinds of requests. We conduct extensive trace-driven evaluations based on real-world workloads, and results show that our coding scheme efficiently enhances the endurance of SSD-based RAID-5 arrays.

In modern parallel storage systems (e.g., cloud storage and data centers), it is important to provide data availability guarantees against disk (or storage node) failures via redundancy coding schemes. One coding scheme is X-code, which is double-fault tolerant while achieving the optimal update complexity. When a disk/node fails, recovery must be carried out to reduce the possibility of data unavailability. We propose an X-code-based optimal recovery scheme called minimum-disk-read-recovery (MDRR), which minimizes the number of disk reads for single-disk failure recovery. We make several contributions. First, we show that MDRR provides optimal single-disk failure recovery and reduces about 25 percent of disk reads compared to the conventional recovery approach. Second, we prove that any optimal recovery scheme for X-code cannot balance disk reads among different disks within a single stripe in general cases. Third, we propose an efficient logical encoding scheme that issues balanced disk read in a group of stripes for any recovery algorithm (including the MDRR scheme). Finally, we implement our proposed recovery schemes and conduct extensive testbed experiments in a networked storage system prototype. Experiments indicate that MDRR reduces around 20 percent of recovery time of the conventional approach, showing that our theoretical findings are applicable in practice.

For chip multiprocessor systems (CMPs), the interference on shared resources such as on-chip caches typically leads to unbalanced progress among threads. Because of the inherent synchronization primitives, such as barriers and locks, cores running fast threads have to waste precious cycles to wait for cores with slow progress, which leads to performance and energy inefficiency. For the purpose of improving performance and reducing energy consumption, this paper proposes to adapt the cache coherence policy for threads according to their delay-tolerant levels. Specifically, this paper proposes Thread progrEss Aware Coherence Adaption (TEACA) which utilizes the thread progress information as hints for coherence adaption. TEACA dynamically utilize the memory system statistics to estimate the progress of threads. Based on the estimated thread progress information, TEACA categorizes threads into leader threads and laggard threads. The thread categorization decisions are then leveraged for efficient coherence adaption on CMP systems supporting hybrid coherence protocols. Experimental results show that, on a 64-core CMP system, TEACA outperforms directory protocol in application execution time and a recently proposed hybrid protocol in both application execution time and energy dissipation.

Network coding allows intermediate nodes to encode data packets to improve network throughput and robustness. However, it increases the propagation speed of polluted data packets if a malicious node injects fake data packets into the network, which degrades the bandwidth efficiency greatly and leads to incorrect decoding at sinks. In this paper, insights on new mathematical relations in linear network coding are presented and a key predistribution-based tag encoding scheme KEPTE is proposed, which enables all intermediate nodes and sinks to detect the correctness of the received data packets. Furthermore, the security of KEPTE with regard to pollution attack and tag pollution attack is quantitatively analyzed. The performance of KEPTE is competitive in terms of: low computational complexity; the ability that all intermediate nodes and sinks detect pollution attack; the ability that all intermediate nodes and sinks detect tag pollution attack; and high fault-tolerance ability. To the best of our knowledge, the existing key predistribution-based schemes aiming at pollution detection can only achieve at most three points as described above. Finally, discussions on the application of KEPTE to practical network coding are also presented.

Modern storage systems stripe redundant data across multiple nodes to provide availability guarantees against node failures. One form of data redundancy is based on XOR-based erasure codes, which use only XOR operations for encoding and decoding. In addition to tolerating failures, a storage system must also provide fast failure recovery to reduce the window of vulnerability. This work addresses the problem of speeding up the recovery of a single-node failure for general XOR-based erasure codes. We propose a replace recovery algorithm, which uses a hill-climbing technique to search for a fast recovery solution, such that the solution search can be completed within a short time period. We further extend the algorithm to adapt to the scenario where nodes have heterogeneous capabilities (e.g., processing power and transmission bandwidth). We implement our replace recovery algorithm atop a parallelized architecture to demonstrate its feasibility. We conduct experiments on a networked storage system testbed, and show that our replace recovery algorithm uses less recovery time than the conventional recovery approach.

With the rapid growth of data and the growing demand from users on the system performance, data availability has become the most important issue in large-scale storage systems. Due to the ability to provide space-optimal data redundancy to protect against node failures, erasure codes have seen widely deployment. To ensure data availability, it is crucial to recover node failures quickly. In this paper, we propose PHR, a pipelined heterogeneous recovery optimization for failure recovery in RAID-6 coded storage systems. Our PHR takes into account both I/O parallelism and node heterogeneity in practical storage systems, and returns an efficient recovery solution timely. We parallelize our PHR algorithm in a pipelined manner, so as to further improve failure recovery performance. With the quantitative simulation studies and extensive test bed experiments, we show our PHR significantly reduces recovery time and also user response time.

Spin-Torque Transfer RAM (STT-RAM) is a promising candidate for SRAM replacement because of its excellent features, such as fast read access, high density, low leakage power, and CMOS technology compatibility. However, wide adoption of STT-RAM as cache memories is impeded by its long write latency and high write power. Recent work proposed improving the write performance through relaxing the retention time of STT-RAM cells. The resultant volatile STT-RAM needs to be periodically refreshed to prevent data loss. When volatile STT-RAM is applied as the last-level cache (LLC) in chip multiprocessor (CMP) systems, frequent refresh operations could dissipate significant extra energy. In addition, refresh operations could severely conflict with normal read/write operations to degrade overall system performance. Therefore, minimizing the performance impact caused by refresh operations is crucial for the adoption of volatile STT-RAM. In this article, we propose Cache-Coherence-Enabled Adaptive Refresh (CCear) to minimize the number of refresh operations for volatile STT-RAM, adopted as the LLC for CMP systems. Specifically, CCear interacts with cache coherence protocol and cache management policy to minimize the number of refresh operations on volatile STT-RAM caches. Full-system simulation results show that CCear performs close to an ideal refresh policy with low overhead. Compared with state-of-the-art refresh policies, CCear simultaneously improves the system performance and reduces the energy consumption. Moreover, the performance of CCear could be further enhanced using small filter caches to accommodate the not-refreshed private STT-RAM blocks.

To efficiently archive and query data in wireless sensor networks (WSNs), distributed storage systems, and multisink schemes have been proposed recently. However, such distributed access cannot be fully supported and exploited by existing routing protocols in a large-scale WSN. In this paper, we will address this challenging issue and propose a distributed geographic $(K)$-anycast routing (GKAR) protocol for WSNs, which can efficiently route data from a source sensor to any $(K)$ destinations (e.g., storage nodes or sinks). To guarantee $(K)$-delivery, an iterative approach is adopted in GKAR where in each round, GKAR will determine not only the next hops at each node, but also a set of potential destinations for every next hop node to reach. Efficient algorithms are designed to determine the selection of the next hops and destination set division at each intermediate node. We analyze the complexity of GKAR in each round and we also theoretically analyze the expected number of rounds required to guarantee $(K)$-delivery. Simulation results demonstrate the superiority of the GKAP scheme in reducing the total duration and the communication overhead for finding $(K)$ destinations, by comparing with the existing schemes, e.g., $(K 1)$-anycast [10].

In this paper we investigate the network lifetime maximization problem in a delay-tolerant wireless sensor network with a mobile sink by exploiting a nontrivial tradeoff between the network lifetime and the data delivery delay. We formulate the problem as a joint optimization problem that consists of finding a trajectory for the mobile sink and designing an energy-efficient routing protocol to route sensing data to the sink, subject to the bounded delay on data delivery and the given potential sink location space. Due to NP-hardness of the problem, we then propose a novel optimization framework, which not only prolongs the network lifetime but also improves the other performance metrics including the network scalability, robustness, and the average delivery delay. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithm against other heuristics. The experimental results demonstrate that the proposed algorithm outperforms the others significantly in terms of network lifetime prolongation.

Modern distributed storage systems provide large-scale, fault-tolerant data storage. To reduce the probability of data unavailability, it is important to recover the lost data of any failed storage node efficiently. In practice, storage nodes are of heterogeneous types and have different transmission bandwidths. Thus, traditional recovery solutions that simply minimize the number of data blocks being read may no longer be optimal in a heterogeneous environment. We propose a cost-based heterogeneous recovery (CHR) algorithm for RAID-6-coded storage systems. We formulate the recovery problem as an optimization model in which storage nodes are associated with generic costs. We narrow down the solution space of the model to make it practically tractable, while still achieving the global optimal solution in most cases. We implement different recovery algorithms and conduct testbed experiments on a real networked storage system with heterogeneous storage devices. We show that our CHR algorithm reduces the total recovery time of existing recovery solutions in various scenarios.

A recent study shows that the throughput of wireless networks can be further improved via combining intra-and intersession network coding (I2NC). The main idea of I2NC is to protect against packet loss by introducing additional redundancy via intra-session coding. However, the amount of redundancy depends on the quality of overhearing links. The poorer an overhearing link is, the less fraction of information is overheard, which results in a potential increase of redundancy needed. While lower transmission rate promises better link quality, it also means lower throughput. Motivated by this, we study the impact of transmission rates on network throughput and formulate the rate selection into an optimization problem. Also, we investigate the flow partition for the inter-session coding. In other words, we consider which sessions would be grouped together through network coding to improve the throughput. We aim to design a joint rate and partition selection in a wireless star network, so as to maximize the network throughput. We prove that finding the optimal joint rate selection and flow partition is NP-hard. An efficient heuristic algorithm is proposed for the networks with heterogenous rates and sessions that can be grouped together for the inter-session network coding. Simulation results show that the proposed scheme achieves throughput gains of up to 185% as compared to what is gained with a rate-unaware I2NC scheme.

Modern storage systems stripe redundant data across multiple disks to provide availability guarantees against disk failures. One form of data redundancy is based on XOR-based erasure codes, which use only XOR operations for encoding and decoding. In addition to providing failure tolerance, a storage system must also provide fast failure recovery to avoid data unavailability. We consider the problem of speeding up the recovery of a single-disk failure for arbitrary XOR-based erasure codes. We address this problem from both theoretical and practical perspectives. We propose a replace recovery algorithm, which uses a hill-climbing technique to search for a fast recovery solution, such that the solution search can be completed within a short time period. We further implement our replace recovery algorithm atop a parallelized architecture to justify its practicality. We experiment our replace recovery algorithm and its parallelized implementation on a networked storage system testbed, and demonstrate that our replace recovery algorithm uses less recovery time than the conventional approach.

In this paper, we dynamically select the transmission rate and design wireless network coding to improve the quality of services such as delay for time critical applications. With low transmission rate, and hence longer transmission range, more packets may be encoded together, which increases the coding opportunity. However, low transmission rate may incur extra transmission delay, which is intolerable for time critical applications. We design a novel joint rate selection and wireless network coding (RSNC) scheme with delay constraint, so as to minimize the total number of packets that miss their deadlines at the destination nodes. We prove that the proposed problem is NP-hard, and propose a novel graph model and transmission metric which consider both the heterogenous transmission rates and the packet deadline constraints during the graph construction. Using the graph model, we mathematically formulate the problem and design an efficient algorithm to determine the transmission rate and coding strategy for each transmission. Finally, simulation results demonstrate the superiority of the RSNC scheme.

Abstract Sensor networks have been receiving significant attention due to their potential applications in environmental monitoring and surveillance domains. In this paper, we consider the design issue of sensor networks by placing a few powerful aggregate nodes into a dense sensor network such that the network lifetime is significantly prolonged when performing data gathering. Specifically, givenKaggregate nodes and a dense sensor network consisting ofnsensors withK≪n, the problem is to place theKaggregate nodes into the network such that the lifetime of the resulting network is maximized, subject to the distortion constraints that both the maximum transmission range of an aggregate node and the maximum transmission delay between an aggregate node and its covered sensor are met. This problem is a joint optimization problem of aggregate node placement and the communication structure, which is NP‐hard. In this paper, we first give a non‐linear programming solution for it. We then devise a novel heuristic algorithm. We finally conduct experiments by simulation to evaluate the performance of the proposed algorithm in terms of network lifetime. The experimental results show that the proposed algorithm outperforms a commonly used uniform placement schema — equal distance placement schema significantly. Copyright © 2010 John Wiley & Sons, Ltd.

Modern high performance Chip Multiprocessor (CMP) systems rely on large on-chip cache hierarchy. As technology scales down, the leakage power of present SRAM based cache gradually dominates the on-chip power consumption, which can severely jeopardize system performance. The emerging nonvolatile Spin Transfer Torque RAM (STT-RAM) is a promising candidate for large on-chip cache because of the ultra low leakage power. However, the write operations on STT-RAM suffer from considerably higher energy as well as longer latency compared with SRAM which will make STT-RAM in trouble for write-intensive workloads. In this paper, we propose to integrate SRAM with STT-RAM to construct a novel hybrid cache architecture for CMPs. We also propose dedicated microarchitectural mechanisms to make the hybrid cache robust to workloads with different write patterns. Extensive simulation results demonstrate that the proposed hybrid scheme is adaptive to variations of workloads. Overall power consumption is reduced by 37.1% and performance is improved by 23.6% on average compared with SRAM based static NUCA under the same area configuration.

The current parallel storage systems use thousands of inexpensive disks to meet the storage requirement of applications. Data redundancy and/or coding are used to enhance data availability, for instance, Row-diagonal parity (RDP) and EVENODD codes, which are widely used in RAID-6 storage systems, provide data availability with up to two disk failures . To reduce the probability of data unavailability, whenever a single disk fails, disk recovery will be carried out. We find that the conventional recovery schemes of RDP and EVENODD codes for a single failed disk only use one parity disk. However, there are two parity disks in the system, and both can be used for single disk failure recovery. In this article, we propose a hybrid recovery approach that uses both parities for single disk failure recovery, and we design efficient recovery schemes for RDP code (RDOR-RDP) and EVENODD code (RDOR-EVENODD). Our recovery scheme has the following attractive properties: (1) “ read optimality ” in the sense that our scheme issues the smallest number of disk reads to recover a single failed disk and it reduces approximately 1/4 of disk reads compared with conventional schemes; (2) “ load balancing property ” in that all surviving disks will be subjected to the same (or almost the same) amount of additional workload in rebuilding the failed disk. We carry out performance evaluation to quantify the merits of RDOR-RDP and RDOR-EVENODD on some widely used disks with DiskSim. The offline experimental results show that RDOR-RDP and RDOR-EVENODD outperform the conventional recovery schemes of RDP and EVENODD codes in terms of total recovery time and recovery workload on individual surviving disk. However, the improvements are less than the theoretical value (approximately 25%), as RDOR-RDP and RDOR-EVENODD change the disk access pattern from purely sequential to a more random one compared with their conventional schemes.

According to data broadcast, we can satisfy multiple requests for the same data item in a broadcast tick. However, there is no significant breakthrough in performance improvement until recently that some studies proposed to use network coding in data broadcast. After broadcasting an encoded packet which encodes a number of data items, multiple clients can retrieve different requested data items in a broadcast tick. This not only utilizes bandwidth more efficiently, but also improves system performance. In this work, we propose a generalized encoding framework to incorporate network coding into data scheduling algorithms for on-demand broadcast. In the framework, data scheduling can be formulated as a weighted maximum clique problem in a graph where the weight of the clique is defined according to the performance objectives of the applications. Under the proposed framework, existing data scheduling algorithms for on-demand broadcast can be migrated into their corresponding coding versions while preserving their original criteria in scheduling data items. Our simulation results using a number of representative scheduling algorithms show that significant performance improvement can be achieved with coding.

Distributed storage systems provide reliable access to data through redundancy spread in network system. A key goal is to minimize bandwidth overhead to maintain the redundancy. This paper studies the flexible recovery from multiple node failures in distributed storage systems. Via a cut-based analysis of information flow graph, we obtain a lower bound of maintenance bandwidth for multi-loss flexible recovery (MFR). We also design a coding scheme based on MFR with maintenance bandwidth matching the lower bound. So the lower bound of maintenance bandwidth for multi-loss recovery is tight and the proposed recovery scheme is optimal.

Networks-on-Chips (NoCs) provides an efficient architectural paradigm as interconnect for state-of-the-art Chip Multi-processors (CMPs). With the increasing development of novel applications in NoCs, one-to-many (multicast) or one-to-all (broadcast) communications are becoming universal and indispensable. The performance constraint metrics, such as power consumption and network latency, are often stringent on NoC systems. Without multicast support, the performance of traditional NoCs will be significantly degraded by such communications. In this paper, we propose Latency-Aware Dual-Partition Multicast (LADPM) routing for mesh-based on-chip networks to reduce packet latency and balance network load. A detailed wormhole router design is also presented for the proposed LADPM scheme. LADPM scheme can adaptively make routing decision based on the distribution of the destination nodes of the multicast traffic. Experimental results, implemented under a cycle-accurate simulator, show that compared with the best known multicast scheme RPM, LADPM reduces Energy-Delay Product by 25.4% on average. More importantly, in heavy traffic load networks, LADPM is a scalable solution.

Modern storage systems use thousands of inexpensive disks to meet the storage requirement of applications. To enhance the data availability, some form of redundancy is used. For example, conventional RAID-5 systems provide data availability for single disk failure only, while recent advanced coding techniques such as row-diagonal parity (RDP) can provide data availability with up to two disk failures. To reduce the probability of data unavailability, whenever a single disk fails, disk recovery (or rebuild) will be carried out. We show that conventional recovery scheme of RDP code for a single disk failure is inefficient and suboptimal. In this paper, we propose an optimal and efficient disk recovery scheme, Row-Diagonal Optimal Recovery (RDOR), for single disk failure of RDP code that has the following properties: (1) it is read optimal in the sense that it issues the smallest number of disk reads to recover the failed disk; (2) it has the load balancing property that all surviving disks will be subjected to the same amount of additional workload in rebuilding the failed disk. We carefully explore the design state space and theoretically show the optimality of RDOR. We carry out performance evaluation to quantify the merits of RDOR on some widely used disks.

This paper studies the recovery from multiple node failures in distributed storage systems. We design a mutually cooperative recovery (MCR) mechanism for multiple node failures. Via a cut-based analysis of the information flow graph, we obtain a lower bound of maintenance bandwidth based on MCR. For MCR, we also propose a transmission scheme and design a linear network coding scheme based on (η, κ) strong-MDS code, which is a generalization of (η, κ) MDS code. We prove that the maintenance bandwidth based on our transmission and coding schemes matches the lower bound, so the lower bound is tight and the transmission scheme and coding scheme for MCR are optimal. We also give numerical comparisons of MCR with other redundancy recovery mechanisms in storage cost and maintenance bandwidth to show the advantage of MCR.

Service-oriented wireless sensor network (WSN) has been recently proposed as an architecture to rapidly develop applications in WSNs. In WSNs, a query task may require a set of services and may be carried out repetitively with a given frequency during its lifetime. A service composition solution shall be provided for each execution of such a persistent query task. Due to the energy saving strategy, some sensors may be scheduled to be in sleep mode periodically. Thus, a service composition solution may not always be valid during the lifetime of a persistent query. When a query task needs to be conducted over a new service composition solution, a routing update procedure is involved which consumes energy. In this paper, we study service composition design which minimizes the number of service composition solutions during the lifetime of a persistent query. We also aim to minimize the total service composition cost when the minimum number of required service composition solutions is derived. A greedy algorithm and a dynamic programming algorithm are proposed to complete these two objectives respectively. The optimality of both algorithms provides the service composition solutions for a persistent query with minimum energy consumption.

It is well known that network coding can enhance the performance of peer-to-peer (P2P) content distribution systems since it benefits block scheduling. In this paper, we introduce our P2P content distribution system "SmartCode" with sparse network coding on PlanetLab. SmartCode uses pre-checking to avoid linearly dependent blocks being transmitted. Under the same system architecture, we also implement two systems "Ecode" and "LRF". Ecode is also based on sparse network coding, but without pre-checking. LRF is BitTorrent- like, using local-rarest-first for block scheduling. We conduct extensive experiments to compare the performances among the three systems. Experimental results show that the distributing time of SmartCode is reduced by 11% on average and up to 19% compared with LRF, and by 7% on average and up to 16% compared with Ecode. We also conduct experiments to analyze robustness among the three systems under the assumption that peers join in and leave a content distribution session dynamically and the seed leave the session after it has transmitted a fixed percentage of blocks over the total blocks of the content. In dynamical cases, SmartCode outperforms evidently than Ecode and LRF in downloading time and the times of peers completing the downloading.

Reliable multicast in wireless networks has been well studied in the sense to solve the feedback implosion issue, which, however, can not reduce the number of retransmissions in order to recover all lost packets at receivers. Most recently, it has been proposed to use network coding for reliable multicast in wireless LANs to reduce the number of retransmissions. In this paper, we propose two new models to further reduce the number of retransmissions for reliable multicast. In the first model, each retransmission encoding decision is made according to the latest ldquowantedrdquo packet set at all receivers. Thus, the maximum number of receivers can potentially decode out one ldquowantedrdquo packet from each encoded retransmission packet. Such a model is referred to as dynamic multicast retransmission encoding (DMRE) model. This model is a memoryless model where a receiver will not buffer encoded retransmission packets for later use. In the second model, a receiver will buffer all received encoded retransmission packets and decode out their ldquowantedrdquo packets at the end of the retransmission batch. Such a model is referred to as cache-based multicast retransmission encoding(CMRE) model. The problem to minimize the number of retransmissions under both DMRE and CMRE models are NP-hard. Effective heuristic algorithms are proposed in this paper. We analyze the impact of packet delivery ratio on the gain of network coding. We derive the lower bound of the expected number of retransmissions using network coding, which provides the insights of the maximum potential gain using network coding in reliable multicast.

A wireless ad hoc network consists of mobile nodes that are powered by batteries. The limited battery lifetime imposes a severe constraint on the network performance, energy conservation in such a network thus is of paramount importance, and energy efficient operations are critical to prolong the lifetime of the network. All-to-all multicasting is one fundamental operation in wireless ad hoc networks, in this paper we focus on the design of energy efficient routing algorithms for this operation. Specifically, we consider the following minimum-energy all-to-all multicasting problem. Given an all-to-all multicast session consisting of a set of terminal nodes in a wireless ad hoc network, where the transmission power of each node is either fixed or adjustable, assume that each terminal node has a message to share with each other, the problem is to build a shared multicast tree spanning all terminal nodes such that the total energy consumption of realizing the all-to-all multicast session by the tree is minimized. We first show that this problem is NP-complete. We then devise approximation algorithms with guaranteed approximation ratios. We also provide a distributed implementation of the proposed algorithm. We finally conduct experiments by simulations to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the proposed algorithm significantly outperforms all the other known algorithms.

Recently, light-trail is becoming an appealing architecture for WDM networks which have been considered as promising backbone of the next generation network. Light-trail can inherently support multicast given its bus nature. In this paper, we study how to use the minimum number of light- trails to form a multicast tree for supporting the given multicast session. The problem for general light-trail WDM networks is proved to be NP-hard. Two auxiliary graphs will be proposed to transform the problem into minimum steiner tree problem that many effective algorithms can be applied. We then show that the same problem in light-trail WDM ring networks can be solved in polynomial time. The simulations show the effectiveness of our work.

Power control can help to reduce energy consumption in wireless networks, while the selfish power control of a link may affect the performance of the neighbors. This paper studies the impact of selfish power control on the stability in wireless networks where each link is under a throughput requirement. Employing the modulation scheme non-coherent frequency shift keying (NFSK), we prove that there is an optimal reception rate and a corresponding optimal transmission strategy to minimize the energy consumption for a link with fixed channel condition, and further present a transmission strategy selection algorithm for links with varying channel condition. A round-based repeated non-cooperative game is proposed, assuming that there is only one link which can adjust its transmission strategy in each unit time and the link always adopts the self-optimal strategy myopically. It is observed that this game cannot converge in some cases, since links are motivated to move transmission power from high interference durations to low interference ones. To bring the game into a steady state, a penalty function is introduced and the performance of various penalty functions is investigated. Simulation results show that heavier penalty leads to faster convergence, but has no effect on the energy consumption of the steady state.

This paper focuses on network coding based multirate multimedia streaming in directed networks and aims at maximizing the total layers received by all receivers, which directly determine the quality of video streaming. We consider the property of layered coding in video streaming and propose the layer separated network coding scheme (LSNC) for layered video streaming. Two algorithms OLSNC and SLSNC are proposed for LSNC based video streaming, where OLSNC achieves an optimal solution, while SLSNC is a polynomial time approximation algorithm. Simulation results show that LSNC is an efficient network coding scheme for multirate multimedia streaming, and the aggregated number of received layers of both OLSNC and SLSNC is very close to the theoretical upper bound in all configurations analyzed.

QoS provisioning in multi-hop IEEE 802.11 networks is very challenging due to the interference nature of wireless medium and the contention-based behavior among neighboring nodes. In such networks, one of the key questions for QoS support is: given a specific topology and traffic condition, how much bandwidth can be utilized along a path in the network without violating QoS demand of existing traffic? Considering that in general QoS-sensitive traffic has the well-controlled sending rate, one key observation is that the network unsaturated condition should be considered. Another observation is that, not only the interaction between the new traffic and the existing ones that can be sensed (by the new one), but also the interaction between the new traffic and the traffic that is hidden but can have influence upon the new one should be studied. Based upon the above observations, we propose an analytical model for multi-hop IEEE 802.11 networks to calculate how much bandwidth can be utilized along a path without violating the QoS requirements of existing traffic. A notion, "free channel time", which is the time allowed for a wireless link to transmit data, is introduced to analyze the path capacity. Simulation results demonstrate that our proposed analytical model can accurately predict the path capacity under various network conditions without breaking QoS demands of all existing traffic

we propose an analytical model for multi-hop IEEE 802.11 networks to calculate how much bandwidth can be utilized along a path without violating the QoS requirements of existing rate-controlled traffic flows. A notion, "free channel time", which is the time allowed for a wireless link to transmit data, is introduced to analyze the path capacity. To achieve the goal, the proposed model effectively characterizes the unsaturated traffic condition. It could also depict the interaction between the newly injected traffic and the hidden traffic that could have influence upon the new traffic. Simulation results demonstrate that our proposed analytical model can accurately predict the path capacity under various network conditions without breaking QoS demands of all existing traffic.

In this paper we study the problem of using the rate adaptation technique to achieve energy efficiency in an IEEE 802.11-based multi-hop network. Specifically, we formulate it as an optimization problem, i.e., minimizing the total transmission power over transmission data rates, subject to the traffic requirements of all the nodes in a multi-hop network. Interestingly, we can show that this problem is actually a well-known multiple-choice knapsack problem, which is proven to be an NP-hard problem. So, instead of finding an optimal solution, which is NP-hard, we seek a sub-optimal solution. Our key technique to attack this problem is distributed cooperative rate adaptation. Here, we promote node cooperation due to our observation that the inequality in non-cooperative channel contention among nodes caused by hidden terminal phenomenon in a multi-hop network tends to result in energy inefficiency. Under this design philosophy, we propose a distributed cooperative rate adaptation (CRA) scheme and prove that it converges. Simulation results show that our CRA scheme can reduce the power consumption up to 86% as compared to the existing (non-cooperative) algorithm.

With the proliferation of portable computing devices and ascending popularity of group-oriented computing, wireless ad hoc network multicasting remains a challenging research subject. While the virtual multicast backbone (VMB) structure is commonly used in current multicast protocols, this paper focuses on the construction of the optimal VMB with the fewest forwarding nodes to decrease overhead and cost, due to the scarce resource in ad hoc networks. Instead of the conventional Steiner tree model, the optimal shared VMB in ad hoc networks is modeled as the minimum Steiner dominating set (MSCDS) in unit-disk graphs (UDG), which is NP-hard. A performance evaluation of flooding for MSCDS is given and a one-hop algorithm is proposed with an approximation ratio of at most 10. To adapt various network scenarios, this paper further presents a fully distributed d-hop algorithm also with a constant approximation ratio, which organizes multicast nodes to form a hierarchical VMB. Based on the hierarchical structure, this paper proposes some approaches to maintain and update VMB, and gives a security framework to exclude malicious nodes from multicast groups. Simulation results show that the proposed algorithms perform very well.