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%.

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.

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 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.

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%.

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.

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%.

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.

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.

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.

Random walk sampling is often used to conduct statistical estimation over graphs. This paper develops an algorithmic framework to reduce the mean square error of such statistical estimation. Our algorithmic framework is inspired by that the mean square error can be decomposed into a sum of the bias and variance of the estimator. More specifically, we apply the bootstrapping technique to design a bias reduction algorithm. Our bias reduction algorithm only utilizes a small number of valid sub-samples, which can reduce more bias of the estimator but may increase the variance of the estimator significantly. We use multiple parallel random walks to reduce this variance such that it can be reduced to arbitrarily small by deploying a sufficient number of random walks. We provide theoretical guarantees and computational complexity analysis of our proposed bias reduction algorithms. Also, the proposed bias reduction algorithm is generic and can be applied to optimize a large class of random walk sampling algorithms. Extensive experiments on four public datasets confirm the effectiveness and computational efficiency of our proposed algorithmic framework under the mean square metric and beyond.

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.

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.

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.

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.

Graphs are commonly used in various applications such as online social networks (OSNs), E-commerce systems and social recommender systems. Random walk sampling is often used to conduct statistical estimation over such graphs. This paper develops an algorithmic framework to reduce the mean square error of such statistical estimation. Our algorithmic framework is inspired by that the mean square error can be decomposed into a sum of the bias and variance of the estimator. More specifically, we apply the bootstrapping technique to design a bias reduction algorithm. A new feature of this bias reduction algorithm is that it allows the variance to increase whenever the bias can be further reduced. The increased variance may lead to a large mean square error of the estimator. We use multiple parallel random walks to reduce this variance such that it can be reduced to arbitrarily small by deploying a sufficient number of random walks. Our algorithmic framework enables one to attain different trade-offs between the sample complexity (i.e., number of parallel random walks) and the mean square error of the statistical estimation. Also, the proposed bias reduction algorithm is generic and can be applied to optimize a large class of random walk sampling algorithms. To demonstrate the versatility of the framework, we apply it to optimize the Metropolis random walk and simple random walk sampling. Extensive experiments confirm the effectiveness and efficiency of our proposed algorithmic framework.

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.

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.

Online product rating systems have become an indispensable component for numerous web services such as Amazon, eBay, Google Play Store, and TripAdvisor. One functionality of such systems is to uncover the product quality via product ratings (or reviews) contributed by consumers. However, a well-known psychological phenomenon called “ message-based persuasion ” lead to “ biased ” product ratings in a cascading manner (we call this the persuasion cascade ). This article investigates: (1) How does the persuasion cascade influence the product quality estimation accuracy? (2) Given a real-world product rating dataset, how to infer the persuasion cascade and analyze it to draw practical insights? We first develop a mathematical model to capture key factors of a persuasion cascade. We formulate a high-order Markov chain to characterize the opinion dynamics of a persuasion cascade and prove the convergence of opinions. We further bound the product quality estimation error for a class of rating aggregation rules including the averaging scoring rule, via the matrix perturbation theory and the Chernoff bound. We also design a maximum likelihood algorithm to infer parameters of the persuasion cascade. We conduct experiments on both synthetic data and real-world data from Amazon and TripAdvisor. Experiment results show that our inference algorithm has a high accuracy. Furthermore, persuasion cascades notably exist, but the average scoring rule has a small product quality estimation error under practical scenarios.

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.

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.

Feedback-based reputation systems are widely deployed in E-commerce systems. Evidence shows that earning a reputable label (for sellers of such systems) may take a substantial amount of time, and this implies a reduction of profit. We propose to enhance sellers’ reputation via price discounts. However, the challenges are as follows: (1) The demands from buyers depend on both the discount and reputation, and (2) the demands are unknown to the seller. To address these challenges, we first formulate a profit maximization problem via a semi-Markov decision process to explore the optimal tradeoffs in selecting price discounts. We prove the monotonicity of the optimal profit and optimal discount. Based on the monotonicity, we design a Q-learning with forward projection (QLFP) algorithm, which infers the optimal discount from historical transaction data. We prove that the QLFP algorithm convergences to the optimal policy. We conduct trace-driven simulations using a dataset from eBay to evaluate the QLFP algorithm. Evaluation results show that QLFP improves the profit by as high as 50% over both Q-learning and Speedy Q-learning. The QLFP algorithm also improves both the reputation and profit by as high as two times over the scheme of not providing any price discount.

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.

Online product rating systems have become an indispensable component for numerous web services such as Amazon, eBay, Google play store and TripAdvisor. One functionality of such systems is to uncover the product quality via product ratings (or reviews) contributed by consumers. However, a well-known psychological phenomenon called “messagebased persuasion” lead to “biased” product ratings in a cascading manner (we call this the persuasion cascade). This paper investigates: (1) How does the persuasion cascade influence the product quality estimation accuracy? (2) Given a real-world product rating dataset, how to infer the persuasion cascade and analyze it to draw practical insights? We first develop a mathematical model to capture key factors of a persuasion cascade. We formulate a high-order Markov chain to characterize the opinion dynamics of a persuasion cascade and prove the convergence of opinions. We further bound the product quality estimation error for a class of rating aggregation rules including the averaging scoring rule, via the matrix perturbation theory and the Chernoff bound. We also design a maximum likelihood algorithm to infer parameters of the persuasion cascade. We conduct experiments on the data from Amazon and TripAdvisor, and show that persuasion cascades notably exist, but the average scoring rule has a small product quality estimation error under practical scenarios.

Feedback-based reputation systems are widely deployed in E-commerce systems. Evidences showed that earning a reputable label (for sellers of such systems) may take a substantial amount of time and this implies a reduction of profit. We propose to enhance sellers’ reputation via price discounts. However, the challenges are: (1) The demands from buyers depend on both the discount and reputation; (2) The demands are unknown to the seller. To address these challenges, we first formulate a profit maximization problem via a semiMarkov decision process (SMDP) to explore the optimal trade-offs in selecting price discounts. We prove the monotonicity of the optimal profit and optimal discount. Based on the monotonicity, we design a QLFP (Q-learning with forward projection) algorithm, which infers the optimal discount from historical transaction data. We conduct experiments on a dataset from to show that our QLFP algorithm improves the profit by as high as 50% over both the classical Q-learning and speedy Q-learning algorithm. Our QLFP algorithm also improves the profit by as high as four times over the case of not providing any price discount.

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.

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.

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.

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.

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.

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.

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.

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.

Graphlets are induced subgraph patterns and have been frequently applied to characterize the local topology structures of graphs across various domains, e.g., online social networks (OSNs) and biological networks. Discovering and computing graphlet statistics are highly challenging. First, the massive size of real-world graphs makes the exact computation of graphlets extremely expensive. Secondly, the graph topology may not be readily available so one has to resort to web crawling using the available application programming interfaces (APIs). In this work, we propose a general and novel framework to estimate graphlet statistics of " any size. " Our framework is based on collecting samples through consecutive steps of random walks. We derive an analytical bound on the sample size (via the Chernoff-Hoeffding technique) to guarantee the convergence of our unbiased estimator. To further improve the accuracy, we introduce two novel optimization techniques to reduce the lower bound on the sample size. Experimental evaluations demonstrate that our methods outperform the state-of-the-art method up to an order of magnitude both in terms of accuracy and time cost.

Solid-state drives (SSDs) have been widely deployed in desktops and data centers. However, SSDs suffer from bit errors, and the bit error rate is time dependent since it increases as an SSD wears down. Traditional storage systems mainly use parity-based RAID to provide reliability guarantees by striping redundancy across multiple devices, but the effectiveness of traditional RAID schemes in SSDs remains debatable. In particular, an open problem is how different parity distributions over multiple devices influence the reliability of an SSD RAID array. That is, should we evenly distribute patsaverties as suggested by conventional wisdom, or unevenly distribute parties as recently proposed for SSD RAID? To address this fundamental problem, we propose the first analytical model to quantify the reliability dynamics of an SSD RAID array as it ages. Specifically, we develop a “non-homogeneous” continuous time Markov chain model, and derive the transient reliability solution. We validate our model via trace-driven simulation and conduct numerical analysis to analyze the reliability dynamics of SSD RAID arrays subject to different parity distributions, error rates, and SSD array configurations. Our model enables system practitioners to decide the appropriate parity distribution based on their reliability requirements.

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.

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.

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.

Viral marketing is becoming important due to the popularity of online social networks (OSNs). Companies may provide incentives (e.g., via free samples of a product) to a small group of users in an OSN, and these users provide recommendations to their friends, which eventually increases the overall sales of a given product. Nevertheless, this also opens a door for malicious behaviors: dishonest users may intentionally give misleading recommendations to their friends so as to distort the normal sales distribution. In this paper, we propose a detection framework to identify dishonest users in the OSNs. In particular, we present a set of fully distributed and randomized algorithms, and also quantify the performance of the algorithms by deriving probability of false positive, probability of false negative, and the distribution of number of detection rounds. Extensive simulations are also carried out to illustrate the impact of misleading recommendations and the effectiveness of our detection algorithms. The methodology we present here will enhance the security level of viral marketing in the OSNs.

Solid state drives (SSDs) have seen wide deployment in mobiles, desktops,and data centers due to their high I/O performance and low energy consumption. As SSDs write data out-of-place, garbage collection (GC) is required to erase and reclaim space with invalid data. However, GC poses additional writes that hinder the I/O performance, while SSD blocks can only endure a finite number of erasures. Thus, there is a performance-durability tradeoff on the design space of GC. To characterize the optimal tradeoff, this paper formulates an analytical model that explores the full optimal design space of any GC algorithm. We first present a stochastic Markov chain model that captures the I/O dynamics of large-scale SSDs, and adapt the mean-field approach to derive the asymptotic steady-state performance. We further prove the model convergence and generalize the model for all types of workload. Inspired by this model, we propose a randomized greedy algorithm (RGA) that can operate along the optimal tradeoff curve with a tunable parameter. Using trace-driven simulation on DiskSim with SSD add-ons, we demonstrate how RGA can be parameterized to realize the performance-durability tradeoff.

Solid-state drives (SSDs) have been widely deployed in desktops and data centers. However, SSDs suffer from bit errors, and the bit error rate is time dependent since it increases as an SSD wears down. Traditional storage systems mainly use parity-based RAID to provide reliability guarantees by striping redundancy across multiple devices, but the effectiveness of RAID in SSDs remains debatable as parity updates aggravate the wearing and bit error rates of SSDs. In particular, an open problem is that how different parity distributions over multiple devices, such as the even distribution suggested by conventional wisdom, or uneven distributions proposed in recent RAID schemes for SSDs, may influence the reliability of an SSD RAID array. To address this fundamental problem, we propose the first analytical model to quantify the reliability dynamics of an SSD RAID array. Specifically, we develop a "non-homogeneous" continuous time Markov chain model, and derive the transient reliability solution. We validate our model via trace-driven simulations and conduct numerical analysis to provide insights into the reliability dynamics of SSD RAID arrays under different parity distributions and subject to different bit error rates and array configurations. Designers can use our model to decide the appropriate parity distribution based on their reliability requirements.

Epidemic attack is a severe security problem in network-coding-enabled wireless mesh networks (WMNs). Malicious nodes can easily launch such form of attack to create an epidemic spreading of polluted packets and deplete network resources. The contribution of this work is to address such security problem. We allow the presence of "smartâ attackers, i.e., they can pretend to be legitimate nodes to probabilistically transmit valid packets so as to reduce the chance of being detected. We also address the case where attackers cooperatively inject polluted packets. We employ the time-based checksum and batch verification to determine the existence of polluted packets, then propose a set of fully "distributedâ and "randomizedâ detection algorithms so that each legitimate node in a WMN can identify its malicious neighbors and purge them for future communication. We provide formal analysis to quantify the performance of the algorithms. Furthermore, simulation and system prototyping are carried out to validate the theoretic analysis and show the effectiveness and efficiency of the detection algorithms.

We consider the following advertisement problem in online social networks (OSNs). Given a fixed advertisement investment, e.g., a number of free samples that can be given away to a small number of users, a company needs to determine the probability that users in the OSN will eventually purchase the product. In this paper, we model OSNs as scale-free graphs (either with or without high clustering coefficient). We employ various influence mechanisms that govern the influence spreading in such large-scale OSNs and use the local mean field (LMF) technique to analyze these online social networks wherein states of nodes can be changed by various influence mechanisms. We extend our model for advertising with multiple rating levels. Extensive simulations are carried out to validate our models, which can provide insight on designing efficient advertising strategies in online social networks.

Viral marketing is becoming important due to the popularity of online social networks (OSNs) and the fact that many users have integrated OSNs into their daily activities, e.g., they provide recommendations to their friends on the products they purchased, or they make decision based on received recommendations. Nevertheless, this also opens door for "shill attack": dishonest users may give wrong recommendations so as to distort the normal sales distribution. In this paper, we propose a detection mechanism to discover these dishonest users in OSNs. In particular, we present two fully distributed algorithms to detect attackers in both (1) the baseline shill attack and (2) the intelligent shill attack. We quantify the performance of our algorithms by deriving the probability of false positive, probability of false negative and distribution function of time needed to detect these dishonest users. Extensive simulations are carried to illustrate the impact of shill attack and the effectiveness of our detection algorithms. The methodology we present here will enhance the security level of viral marketing in OSNs.

Pollution attack is a severe security problem in network-coding enabled wireless mesh networks (WMNs). Under such form of attack, malicious nodes can easily create an epidemic spreading of polluted packets to deplete network resources. We address this security problem even when the attackers are "intelligent" in the sense that they may pretend to be legitimate nodes to probabilistically transmit valid packets so as to reduce the chance of being detected. We use the batch verification technique to determine the existence of polluted packets, and propose fully "distributed" and "randomized" detection algorithms to identify the attackers who inject polluted packets, and purge them for future communication. Formal analysis is provided to quantify performance measures of the algorithms, e.g., probability of false positive and probability of false negative, as well as the probability distribution of time needed to identify all malicious nodes. Simulation and system prototype are carried out to show the effectiveness and efficiency of the detection algorithms.