Emerging communication and storage embrace Low-Density Parity-Check (LDPC) codes to fully exploit their physical channels. FPGA (Field-Programmable Gate Array) is widely employed to fast prototype and accelerate the LDPC decoding with high complexity. For varying channel conditions, the FGPA decoder is desired to elastically stop iteration when meeting success condition, avoiding conservatively performing a predefined and large number of iterations. However, the dynamical-execution algorithms with adjustable parameters generally are challenging for scalable decoder structure preferred to deterministic execution logic. To overcome the problem, this paper presents an elastic and scalable HLS-based FPGA LDPC decoder architecture with early-termination to achieve high throughput and flexibility. To this end, eLDPC first provides a universal operation, fully leveraging the features of HLS to efficiently implement optimized small-scale hardware units for low-level data-update operations. Second, eLDPC presents a decoding-iteration pipeline that adds a termination-check stage to terminate the following iteration for current codeword decoding. eLDPC also presents an HLS-enhanced approach to address memory access conflicts associated with the DU pipeline. Further, eLDPC extends the number of DU decoding-iteration pipelines within a single stream to decode multiple codewords in parallel. Third, eLDPC designs elastic and independent multiple decoding streams by using FIFO queues to decouple Input, Output, and a decoding unit (DU) with variable iterations while avoiding the potential blockage of the queueing. We implement and evaluate eLDPC on a Xilinx U55C. Experiments show that eLDPC outperforms recent decoders by up to 5× with the same parameter and achieves the actual decoding throughput of up to 49.5 Gbps with high scalability and flexibility.

Cloud block storage (CBS) provides virtual disks with block-level accessibility. The petabyte-scale CBS systems maintain trillions of block-mapping key-value entries as metadata to track the storage location of each virtual block. Although SSD-based KV stores have been widely adopted in cloud systems for their high efficiency and durability, current SSD-based schemes face significant challenges in achieving deterministic access latency for latency-sensitive metadata services. Our experimental observations indicate that the substantial long-tail latency is primarily caused by (1) I/O blocking due to internal tasks of SSDs including modern Zone Namespace SSDs; and (2) additional disk I/Os when querying high-level indexes across memory and SSDs under memory-constrained environments. In this article, we propose an SSD-based SIndex to store trillions of block-mapping entries for latency-critical cloud block storage, which performs comprehensive latency optimization across storage I/O scheduling and high-level indexing. To prevent long-tail I/Os while avoiding intrusive device modifications, SIndex introduces an inter-SSD I/O scheduling mechanism based on read/write separation and SSD state transitions, which mitigates latency fluctuations induced by garbage collection on conventional SSDs and zone operations on Zone Namespace SSDs. Additionally, SIndex employs opportunistic I/O speculation and a concurrent request balancing mechanism to reduce read disturbance and I/O contention. To query the storage location of targeted block-mapping entries with bounded latency, SIndex proposes a memory-efficient high-level index incorporates with a static data layout, preventing time-consuming disk lookups by keeping the index in memory. We evaluate the SIndex prototype using a variety of benchmarks and real-world traces on commodity SSDs. The results demonstrate that SIndex outperforms RocksDB and other approaches by up to 11.4× in tail latency, keeping the 99.99th-percentile latency below 400 μs.

Training deep learning models is computationally demanding and data-intensive. Existing approaches utilize local SSDs within training servers to cache datasets, thereby accelerating data loading during model training. However, we experimentally observe that data loading remains a performance bottleneck when randomly retrieving small-sized sample files on SSDs. In this paper, we introduce LCache, a log-structured dataset caching mechanism designed to fully leverage the I/O capabilities of SSDs and reduce I/O-induced training stalls. LCache determines the randomized dataset access order by extracting the pseudo-random seed from the training frameworks. It then aggregates small-sized sample files into larger chunks and stores them in a log file on SSDs, thus enabling sequential I/O requests on data retrieval and improving data loading throughput. Further-more, LCache proposes a real-time log reordering mechanism that strategically schedules cached data to organize logs across different epochs, which enhances cache utilization and minimizes data retrieval from low-performance remote storage systems. Additionally, LCache incorporates an MetaIndex to enable rapid log traversal and querying. We evaluate LCache with various real-world DL models and datasets. LCache outperforms the native PyTorch Dataloader and NoPFS by up to 9.4x and 7.8x in throughput,. respectively,

Modern data-intensive applications such as large language models already outrun affordable DRAM. Page swapping to fast SSDs or network-attached memory adds capacity, but existing operating system policies often struggle when an application's working set shifts, causing costly page faults and degrading performance. Meanwhile, many applications iterate over large data objects in regular loops, which is favorable for optimization. But existing eviction and prefetch policies largely miss this opportunity, because they rely on short-term recency and reactive prefetching, leading to memory thrashing and massive uncovered faults. This paper proposes Repo, a novel swap policy that identifies and exploits intrinsic loops in modern applications. Repo utilizes PEBS-based sampling and clustering for rapid and accurate delineation of loop elements, confirms loops reliably using stable load/store counts, and crucially, coordinates eviction and prefetching proactively. Experiments on real applications show that Repo reduces page faults by up to 98 % and execution time by as much as 78 % relative to state-of-the-art baselines.

Graph Neural Networks (GNNs) have become inevitable tools for extracting knowledge from massive topological structure data. However, experimental observation shows that existing GNN training frameworks exhibit low efficiency when performing memory-access-intensive data preparation stage upon CPU and computation-intensive model training stage upon GPU. This is largely due to data dependency restriction between the two stages and sequential execution of computation in training iterations. Based on these observations, this paper proposes HeteroGNN, an efficient GNN training framework, to maximize parallelism of GNN training upon heterogeneous CPU-GPU architecture. Specifically, HeteroGNN first proposes a data-dependency-aware stage division policy, which divides the two stages to six phases to offer inter-stage parallelism. Further, HeteroGNN establishes a fine-grained computation partition schema, which actively partitions typical GNN computing operations into multiple schedulable tasks suitable for CPU and GPU. Finally, HeteroGNN designs an adaptive task scheduler, which adaptively schedules the tasks upon six phases to maximize GPU efficiency. Experiment results demonstrate that HeteroGNN speeds up end-to-end training time up to 1.29× comparing to state-of-the-art GNN framework, PiPAD, and 1.30× to 2.06× comparing to DGL and PyG.

Modern solid-state drives (SSDs) continue to boost storage density and I/O bandwidth at the cost of flash-access I/O latency, especially for write, hence they prevalently deploy a build-in buffer to absorb incoming writes. However, when the buffer is used up, the applications suffer from a sudden and long performance decline, i.e., buffer-exhausted degradation (BED). To holistically understand BED and recovery, we design an automated testing toolset (SSDTest) to measure six commodity NVMe SSDs and find: (1) the occurrence of the BED strictly relies on the written-data amount, (2) BED dramatically increases I/O latency of SSDs, especially write and read-after-write, (3) BED can be conditionally reduced and recovered only after a period of idle time, and (4) a read without preceding writes is largely immune to BED, but prolongs the required idle time to recover the available buffer. Furthermore, we build a black-box SSD buffer-recovery model to quantitatively characterize the idleness-recovery behaviors and design an SSD BED predictor to make BED occurrence and buffer recovery predictable. Leveraging this model, we further design an Active Idleness I/O Scheduler (AIS) with small-sized auxiliary storage to actively regulate the I/O idle-intervals to maximize the internal buffer recovery of SSD. AIS adaptively steers incoming data to the auxiliary storage to (1) strategically keep SSD idle to reduce the occurrence of BED and (2) mitigate the tail latency of SSDs caused by read-after-writes during BED. We perform extensive evaluations under a variety of workloads. The results show that AIS improves average, 99th, 99.9th, and 99.99th-percentile latencies of SSDs by up to 29.3%, 37.3%, 78.7%, and 67.2% respectively, with up to 512MB auxiliary storage.

Compute eXpress Link (CXL) based Solid-State Drives (CXL-SSDs), such as the Samsung CMM-H model, promise to offer CXL.mem memory and CXL.io block dual-mode interfaces. Nonetheless, whether and how cloud applications with diverse and varying access patterns benefit from such dual-mode CXL-SSD remains an open question for academia and industry.

Training large deep learning models is extremely computationally intensive and time-consuming; therefore, it relies on checkpointing mechanisms to save snapshots promptly, ensuring rapid recovery from a myriad of failures. Existing checkpointing approaches save snapshots to either CPU memory or storage, overlooking their aggregated I/O capability. In this paper, we propose a heterogeneous multi-path checkpointing mechanism, ParaCkpt, to make full use of both PCle-bandwidth and I/O capability of memory and storage to accelerate check-pointing. ParaCkpt first identifies multiple paths for GPUs to CPU memory, local and remote storages, and determines their available bandwidths. Then, ParaCkpt strategically partitions the training model states into a set of path-based shards and drains them from GPUs to the memory and storage in parallel. Moreover, ParaCkpt employs a two-stage persistence strategy to flush in-memory shards to local SSDs in the background, and then stores local shards using compression to remote storage. Finally, ParaCkpt maintains global snapshots distributed across memory and storage, enabling rapid recovery via the multi-path way. We evaluate ParaCkpt with various real-world deep learning models. ParaCkpt outperforms native Pytorch and state-of-the-art asynchronous checkpointing approaches by up to 96 x and 2.3 x in throughput, respectively.

QC-LDPC (Quasi Cyclic Low-Density Parity-Check) codes, as a regular block-based code, have been preva-lently adopted in communication and storage fields to ensure high reliability and bandwidth of data channels. However, existing Field-Programmable Gate Array (FPGA) QC-LDPC encoders designed by RTL experts are generally dedicated to specialized LDPC codes and hardware platforms without flexibility and scalability. Recently, High-Level Synthesis (HLS) was introduced to compile a high-level encoding logic into Register Transfer Level (RTL) implementations, which are low performance and hardware efficiency due to the overlarge HLS-to-RTL design space, especially for large-scale FPGA hardware. This paper proposes a highly modularized and efficient FPGA QC-LDPC encoder, HEncoder, to fully leverage HLS to achieve high bandwidth, flexibility in both code parameters, and hardware efficiency. Firstly, HEncode presents an efficient Encode Block (EB) fully exploiting the FPGA LUT characteristic. Second, HEncode designs a low-level subword-encoding pipeline using multiple EBs and subword-parallel Encode Units (EU). Third, HEncoder designs an encode module with a pipelined data stream consecutively passing Input, EU array, and Output to balance bandwidths of accessing and encoding words. Finally, HEncode develops a design space analyzer to automatically determine the encoder parameters under constrained conditions to achieve high bandwidth. We implemented and evaluated HEncode on the Xilinx U50. The results show that compared to existing encoders, HEncode gains an increase of approximately 154.5× in the peak throughput and about 5.89 × in hardware efficiency to achieve the encoding throughput of 922.66 Gbps.

The Solid State Drives (SSD) based key-value stores face significant challenges in achieving deterministic access latency. We experimentally observe the long-tail latency is mainly caused by I/O blocking induced by SSD’s internal tasks. In this paper, we propose an SSD-based SIndex to store hundreds of billions of block-mapping entries for the latency-critical cloud block storage. To hide the latency fluctuations induced by garbage collection and buffer flushing, SIndex proposes an inter-SSD I/O scheduling based on read/write separation and SSD state transition, while adopting opportunistic request speculation and balancing mechanism to mitigate read disturbance and I/O contention. Moreover, SIndex introduces a write-staging buffer cache and a two-stage sync mechanism to preferentially buffer updated data before synchronizing them to SSDs. We evaluate the SIndex prototype with a variety of benchmarks and real-world traces on commodity SSDs. SIndex is demonstrated to outperform RocksDB and other approaches by up to 11.2 × in tail latency without affecting the throughput performance.

Our extensive experiments reveal that existing key-value stores (KVSs) achieve high performance at the expense of a huge memory footprint that is often impractical or unacceptable. Even with the emerging ultra-fast byte-addressable persistent memory (PM), KVSs fall far short of delivering the high performance promised by PM's superior I/O bandwidth. To find the root causes and bridge the huge performance/memory-footprint gap, we revisit the architectural features of two representative indexing mechanisms (single-stage and multi-stage) and propose a three-stage KVS called FluidKV. FluidKV effectively consolidates these indexes by fast and seamlessly running incoming key-value request stream from the write-concurrent frontend stage to the memory-efficient backend stage across an intermediate stage. FluidKV also designs important enabling techniques, such as thread-exclusive logging, PM-friendly KV-block structures, and dual-grained indexes, to fully utilize both parallel-processing and high-bandwidth capabilities of ultra-fast storage hardware while reducing the overhead. We implemented a FluidKV prototype and evaluated it under a variety of workloads. The results show that FluidKV outperforms the state-of-the-art PM-aware KVSs, including ListDB and FlatStore with different indexes, by up to 9× and 3.9× in write and read throughput respectively, while cutting up to 90% of the DRAM footprint.

Following a conventional design principle that pays more fast-CPU-cycles for fewer slow-I/Os, popular software storage architecture Linux Multiple-Disk (MD) for parity-based RAID (e.g., RAID5 and RAID6) assigns one or more centralized worker threads to efficiently process all user requests based on multi-stage asynchronous control and global data structures, successfully exploiting characteristics of slow devices, e.g., Hard Disk Drives (HDDs). However, we observe that, with high-performance NVMe-based Solid State Drives (SSDs), even the recently added multi-worker processing mode in MD achieves only limited performance gain because of the severe lock contentions under intensive write workloads. In this paper, we propose a novel stripe-threaded RAID architecture, StRAID, assigning a dedicated worker thread for each stripe-write (one-for-one model) to sufficiently exploit high parallelism inherent among RAID stripes, multi-core processors, and SSDs. For the notoriously performance-punishing partial-stripe writes that induce extra read and write I/Os, StRAID presents a two-stage stripe write mechanism and a two-dimensional multi-log SSD buffer. All writes first are opportunistically batched in memory, and then are written into the primary RAID for aggregated full-stripe writes or conditionally redirected to the buffer for partial-stripe writes. These buffered data are strategically reclaimed to the primary RAID. We evaluate a StRAID prototype with a variety of benchmarks and real-world traces. StRAID is demonstrated to outperform MD by up to 5.8 times in write throughput.

RAID (Redundant Array of Independent Disks) has been widely used to enhance read and write performance of existing storage systems. Existing software RAID do not fully utilize write performance of Serial interface SSDs (Solid State Drive). The most popular software RAID currently is Linux Multiple-Disks (MD), and the latest software RAID is StRAID. We observe that both of these software RAID methods lead to thread contention in multi-threaded mode, especially when applied to Serial interface SSDs. Multiple threads writing to same address can limit write performance. In this paper, we propose a stripe-queued and stripe-threaded merging I/O strategy. First, SSRAID segregates write requests across different stripes using a set of stripe-queues and stripe-threads to prevent interference between them. As a result, write thread contention in SSRAID is eliminated, allowing stripe-threads to maintain the highest efficiency of parallelism. Secondly, SSRAID can merge write requests from the same stripe-queue multiple times through stripe-thread, effectively reducing the number of additional write I/Os. Finally, SSRAID presents a stage buffer based on data merging. During partial stripe-write, write-induced read I/Os on the SSD are transformed into direct access to the stage buffer, effectively reducing write-induced read I/Os. Compared to StRAID, SSRAID improves average sequential write throughput by 86% and reduces average sequential write latency by 61% in the optimal case.

High-Level Synthesis (HLS) translates high-level behavior-description to Register-Transfer Level (RTL) implemen-tation in modern Field-Programmable Gate Arrays (FPGAs), accelerating domain-specific hardware developments. Low-Density Parity-Check (LDPC), as a powerful error-correction code family, has been widely implemented in hardware for building a reliable data channel over a noisy physical channel in communication and storage applications. Leveraging HLS to fast prototype high-performance LDPC decoder is intriguing with high scalability and low hardware-dependence, but generally is sub-optimal due to the lack of accurate and precise behavior descriptions in HLS to characterize iteration- and circuit-level implementation details. This paper proposes an HLS-based QC-LDPC decoder with scalable throughput by precisely refining the LDPC behavior descriptions, R-LDPC for short. To this end, R-LDPC first adopts an HLS-based LDPC decoder microarchitecture with a module-level pipeline. Second, R-LDPC offers a multi-instance-sharing one (MSO) description to explicitly define shared parts and non-shared parts for an array of check-node updating-units (CNU), eliminating redundant function modules and addressing circuits. Third, R-LDPC designs efficient single-stage and multi-stage shifters to eliminate unnecessary bit-selection circuits. Finally, R-LDPC provides invalid-element aware loop scheduling before the compile phase to avoid some unnecessary stalls at runtime. We implement an R-LDPC decoder, compared to the original HLS-based implementation, R-LDPC reduces the hardware con-sumption up to 56%, the latency up to 67%, and the decoding throughput up to 300%. Furthermore, R-LDPC is adapted to different scales, LDPC standards, and code rates, and can achieve 9.9Gbps decoding throughput in Xilinx U50.

Non-Volatile Memory (NVM) with persistency and near-DRAM performance has been commonly used as first-level fast storage atop Solid-State Drives (SSDs) and Hard Disk Drives (HDDs), constituting classic hierarchy architecture to achieve high cost-performance. However, such NVM/SSD tiered storage overuses primary NVM with limited actual performance and under-utilizes secondary SSD with increasing bandwidth. Besides, NVM and SSD exhibit distinguished I/O characteristics, but are complementary for different I/O patterns. This motivates us to design a superior hybrid storage to fully exploit NVM and SSD simultaneously. In this paper, we propose UHS, an Ultra-fast Hybrid Storage consolidating NVM and SSD to reap their own merits with key enabled techniques. First, UHS builds a uniform yet heterogenous block-level storage view for the upper applications, e.g., file systems or key-value stores. UHS provides static address-mapping to explicitly partition the global block-space into coarse-grain NVM-zones and SSD-zones, which mainly serve the metadata and file data respectively. Second, UHS presents a fine-grain request-level NVM buffer to dynamically absorb small file-writes in runtime and then migrates them to the SSDs in the background. Third, UHS designs I/O-affinity write allocation and hash-based buffer indexing to trade off write gain and read cost of the NVM-buffer. Finally, UHS designs a multi-thread I/O model to take full advantage of parallelism in both NVM and SSD. We implement UHS and evaluate it under a variety of workloads. The experiments show that UHS outperforms SSD, NVM, Bcache-writeback (representative hierarchy storage), and Device-Mapper (state-of-the-art hybrid storage) up to 8X, 1.5X, 3.5X, and 6X respectively.

LDPC (Low-Density Parity-Check) codes have become a cornerstone of transforming a noise-filled physical channel into a reliable and high-performance data channel in communication and storage systems. FPGA (Field-Programmable Gate Array) based LDPC hardware, especially for decoding with high complexity, is essential to realizing the high-bandwidth channel prototypes. HLS (High-Level Synthesis) is introduced to speed up the FPGA development of LDPC hardware by automatically compiling high-level abstract behavioral descriptions into RTL-level implementations, but often sub-optimally due to lacking effective low-level descriptions. To overcome this problem, this paper proposes an HLS-friendly QC-LDPC FPGA decoder architecture, HF-LDPC, that employs HLS not only to precisely characterize high-level behaviors but also to effectively optimize low-level RTL implementation, thus achieving both high throughput and flexibility. First, HF-LDPC designs a multi-unit framework with a balanced I/O-computing dataflow to adaptively match code parameters with FPGA configurations. Second, HF-LDPC presents a novel fine-grained task-level pipeline with interleaved updating to eliminate stalls due to data interdependence within each updating task. HF-LDPC also presents several HLS-enhanced approaches. We implement and evaluate HF-LDPC on Xilinx U50, which demonstrates that HF-LDPC outperforms existing implementations by 4× to 84× with the same parameter and linearly scales to up to 116 Gbps actual decoding throughput with high hardware efficiency.

The parameters of deep learning (DL) have ballooned from millions to trillions over the past decade, thus cannot be fully placed in a limited GPU memory. Existing works offload the parameter-update stage of training DL model to CPU, thus leveraging CPU capability and memory to support training large-scale model. However, the stage running upon CPU could block its following stage running upon GPU, thus wasting expensive GPU-cycles. We first analyze the dataflow and workflow of DL training, and find that the backward stage and the parameter-update stage can be parallelized upon GPU and CPU respectively. To this end, we present a DL-training scheduling framework, CoTrain, to allocate a compute task and its corresponding data into GPU and CPU and to parallelize them effectively at coarse-grain and fine-grain way. Particularly, the fine-grained task-partition scheme allocates a portion of parameter-update stage to GPU according to data-reuse-distance, thus largely avoiding idleness of both GPU and CPU while reducing data movement between GPU and CPU. We build and evaluate CoTrain atop PyTorch under representative models. The results show that compared to the state-of-the-art ZeRO-Offload, CoTrain achieves 30.4% improvement in the training throughput while increasing model-size by up to 7% without changing the training semantics.

Existing key-value stores (KVSs) based on log-structured merge-tree (LSM-tree) have been broadly deployed in practice to leverage characteristics of conventional block storage via file system, but lack effective exploitation for emerging byte-addressed persistent memory (PM). We reveal that these KVSs running upon existing PM-aware File systems cause inefficient PM I/O behaviors, including 1) numerous page faults, 2) I/O misaligned with cacheline, and 3) bandwidth wastage of concurrent I/O threads. To make full use of PM without major modification for existing LSM-based KVSs, this paper proposes PMLDS, a direct managed storage for LSM-tree-based KVSs directly running upon PM. PMLDS acts as a unified I/O layer to handle all requests from KVS to PM. PMLDS designs an LSM-tree-aware data layout to directly map the KVS’s persistent objects to the storage slots with fixed location and size, thus simplifying and replacing the file system’s functionality with a minor modification. To improve I/O efficiency, PMLDS further presents three key techniques: 1) pre-allocating reusable data slots to avoid page faults, 2) forcing cacheline-alignment for small requests, and 3) scheduling asynchronous I/O threads to harness PM’s limited parallelism. We implement PMLDS and evaluate it with popular RocksDB under a variety of workloads. The results show that compared to representative PM-aware file systems such as Ext4-DAX, XFS-DAX, NOVA, and WineFS, PMLDS improves the write performance of RocksDB by up to 2.1 × while reducing the read latency by 20%~50%.

Erasure codes are widely deployed in modern storage systems, leading to frequent usage of their encoding/decoding operations. The encoding/decoding process for erasure codes is generally carried out using the parity-check matrix approach. However, this approach is serial and computationally expensive, mainly due to dealing with matrix operations, which results in low encoding/decoding performance. These drawbacks are particularly evident for newer erasure codes, including SD and LRC codes. To address these limitations, this article introduces the Partitioned and Parallel Matrix ( PPM ) algorithm. This algorithm partitions the parity-check matrix, parallelizes encoding/decoding operations, and optimizes calculation sequence to facilitate fast encoding/decoding of these codes. Furthermore, we present a generalized PPM ( gPPM ) algorithm that surpasses PPM in performance by employing fine-grained dynamic matrix calculation sequence selection. Unlike PPM, gPPM is also applicable to erasure codes such as RS code. Experimental results demonstrate that PPM improves the encoding/decoding speed of SD and LRC codes by up to 210.81%. Besides, gPPM achieves up to 102.41% improvement over PPM and 32.25% improvement over RS regarding encoding/decoding speed.

Emerging persistent memory (PM) with fast per-sistence and byte-addressability physically shares the memory channel with DRAM-based main memory. We experimentally uncover that the throughput of application accessing DRAM collapses when multiple threads access PM due to head-of-line blockage in the memory controller within CPU. To address this problem, we design a PM-Accessing Thread Scheduling (PATS) mechanism that is guided by a contention model, to adaptively tune the maximum number of contention-free concurrent PM-threads. Experimental results show that even with 14 concurrent threads accessing PM, PATS is able to allow only up to 8% decrease in the DRAM-throughput of the front-end applications (e.g., Memcached), gaining 1.5x PM-throughput speedup over the default configuration.

Attempts to improve the performance of key-value stores (KVS) by replacing the slow Hard Disk Drives (HDDs) with much faster Solid-State Drives (SSDs) have consistently fallen short of the performance gains implied by the large speed gap between SSDs and HDDs, especially for small KV items. We experimentally and holistically explore the root causes of performance inefficiency of existing LSM-tree based KVSs running on powerful modern hardware with multicore processors and fast SSDs. Our findings reveal that the global write-ahead-logging (WAL) and index-updating (MemTable) can become bottlenecks that are as fundamental and severe as the commonly known LSM-tree compaction bottleneck, under both the single-threaded and multi-threaded execution environments.

Parity-based RAID suffering from partial-stripe write-penalty has to introduce write buffer to fast absorb and merge incoming writes, and then flush them to RAID array in batch. However, we experimentally observe that the popular buffering mechanism as Linux RAID journal and partial parity logging (PPL) becomes a bottleneck for ultra-fast SSD-based RAID, and we further uncover that the centralized log-buffer model is the prime cause.

Erasure-coded archival converts the redundancy mechanism of low access-frequency data from replication to erasure coding for balancing access performance and storage efficiency. A variety of pipelined schemes are designed to speed up the archival operation, however they neglect such three factors as heterogeneous network, under-utilization of replica resources and tight coupling with underlying platforms which restrict or even negate the performance gains. In this paper, we propose Archpipe, a fast and flexible pipelined erasure-coded archival scheme. It exhibits three distinct features: 1) heterogeneous network awareness, for a single-pipelined construction, sufficient-bandwidth links are given high scheduling priority to avoid network congestion, while considering locality to reducing network transmissions; 2) parallel encoding, the unused replica resources are exploited to adaptively construct multiple pipelines for each stripe based on the single-pipelined algorithm, thereby enabling parity blocks to be encoded in parallel; 3) loose coupling, it does not rely on specific block placement policies and stripe construction algorithms. Experimental results indicate that, Archpipe can be seamlessly integrated with common distributed storage systems, and it improves the erasure-coded archival performance by 3.6 ∼ 4.7× and 1.3 ∼ 2.6× in on-disk and in-memory scenarios, respectively.

Traditional index structures build on homogeneous storage consisting of same-granularity blocks and maintain a map between logical offset and storage-blocks. Non-Volatile Memory (NVM) and Solid-State Drive have their own optimal I/O sizes. However, these homogeneous indexes cannot uniformly and efficiently manage hybrid NVM-SSD storage space with heterogenous blocks. This paper proposes a heterogeneous B+tree, referred as to HBtree, to index multi-granularity blocks for hybrid NVM-SSD storage. The indexing node of HBtree is same to B+tree with largest-granularity blocks. However, a part of leaves in the legacy B+tree are extended to index small granularity blocks. Therefore, HBtree has the low tree-height while indexing different granularity blocks simultaneously. We implement HBtree and evaluate it on hybrid NVM-SSD storage. Compared to legacy B+tree, HBtree improves insert and search performance by up to 4.54x and 1.96x respectively and improving space utilization by up to 3.49x.

The RAID-10 architecture has been widely deployed in commercial and industrial storage environments over the past two decades due to its high reliability, availability, and performance. However, during the recovery process of a single disk failure, which accounts for more than 99.75% of the disk failure scenarios, it is still at a high risk of data loss and suffers from a degradation of user I/O performance, which results from the severe interference between the user and recovery I/Os. Based on our observations and analyses, we find highly asymmetric disk bandwidth utilization and disk I/O interference during the recovery process of the RAID-10 systems under the single faulty-disk condition. Motivated by the fact that this asymmetry can be leveraged to significantly and simultaneously speed up the recovery and user I/O performances. As a result, we propose a novel asymmetric buffer cache management scheme, called A-Cache, to mitigate this asymmetry by allocating cache space asymmetrically between the disks that do not participate in the recovery process and those that do. To verify the effectiveness of the A-cache, we have integrated A-Cache into the popular cache algorithms LRU, named A-LRU. The evaluation of our prototype system demonstrates that A-LRU is able to significantly speed up the recovery speed and average user I/O latency under various typical configurations, compared to the original LRU, without any additional hardware cost.

Hybrid storage servers combining solid-state drives (SSDs) and hard-drive disks (HDDs) provide cost-effectiveness and μs-level responsiveness for applications. However, observations from cloud storage system Pangu manifest that HDDs are often underutilized while SSDs are overused, especially under intensive writes. It leads to fast wear-out and high tail latency to SSDs. On the other hand, our experimental study reveals that a series of sequential and continuous writes to HDDs exhibit a periodic, staircase-shaped pattern of write latency, i.e., low (e.g., 35 μs), middle (e.g., 55 μs), and high latency (e.g., 12 ms), resulting from buffered writes within HDD’s controller. It inspires us to explore and exploit the potential μs-level IO delay of HDDs to absorb excessive SSD writes without performance degradation. We first build an HDD writing model for describing the staircase behavior and design a profiling process to initialize and dynamically recalibrate the model parameters. Then, we propose a Buffer-Controlled Write approach (BCW) to proactively control buffered writes so that low- and mid-latency periods are scheduled with application data and high-latency periods are filled with padded data. Leveraging BCW, we design a mixed IO scheduler (MIOS) to adaptively steer incoming data to SSDs and HDDs. A multi-HDD scheduling is further designed to minimize HDD-write latency. We perform extensive evaluations under production workloads and benchmarks. The results show that MIOS removes up to 93% amount of data written to SSDs, reduces average and 99 th -percentile latencies of the hybrid server by 65% and 85%, respectively.

Ubiquitous cameras continuously produce enormous surveillance videos, largely challenging the capacity of video analytics and storage system. Although such videos are encoded and compressed by codecs to effectively reduce inter-/intra-frame redundancy at pixel level, they still consume massive storage space, thus being deleted periodically to recycle storage. To reduce hardware pressure in both efficient computation and long-term storage, we propose a video refining system, VRefine, merely retaining key contents for the surveillance videos to achieve a high storage efficiency and fast video analytics. VRefine further eliminates potential inter-/intra-frame content redundancy inherent in surveillance videos from the perspective of video analysis. Specifically, VRefine gradually reduces video size in three consecutive stages: removing all B frames and part of P frames (KStore), condensing the remainder frames based on motion vectors (CStore), and extracting object-semantics into a text database (SStore) using existing object detection models. We implement and evaluate VRefine. The experimental results show that compared with the raw surveillance video, VRefine can reduce 42.3%-94.3% storage size and shorten the analyzing time by 46.5%-95.8%, with a slight and controllable reduction in prediction accuracy (3.0%).

In recent years, the design of green datacenters and their enabling technologies, including renewable power managements, have gained a lot of attraction in both industry and academia. However, the maintenance and upgrade of the underlying server system over time (e.g., server replacement due to failures, capacity increases, or migrations), which make datacenters increasingly more heterogeneous in their key processing components (e.g., capacity and variety of processors, memory and storage devices), present a great challenge to optimal allocation of renewable power supply. In other words, the current heterogeneity-unaware power allocation policies have failed to achieve optimal performance given a limited and time varying renewable power supply. In this paper, we propose a dynamic power allocation framework called GreenHetero, which enables adaptive power allocation among heterogeneous servers in green datacenters to achieve the optimal performance when the renewable power varies. Specifically, the GreenHetero scheduler dynamically maintains and updates a performance-power database for each server configuration and workload type through lightweight profiling method. Based on the database and power prediction, the scheduler leverages a well-designed solver to determine the optimal power allocation ratio among heterogeneous servers at runtime. Finally, the power enforcer is used to implement the power source selections and the power allocation decisions. We build an experimental prototype to evaluate GreenHetero. The evaluation shows that our solution can improve the average performance by 1.2x-2.2x and the renewable power utilization by up to 2.7x under tens of representative datacenter workloads compared with the heterogeneity-unaware baseline scheduler.

The first commercial Non-Volatile Memory (NVM) (i.e., Intel Optane DC Persistent Memory) exhibits limited parallelism, especially for write operations, which is generally neglected by existing NVM-aware file systems. Besides, the concurrent control of file systems also limits their scalability on high-performance NVMs under mainstream multi-core architectures. To effectively exploit full parallelism inherent in both NVMs and multi-core processors to enhance the overall performance, this paper proposes a novel scalable persistent memory file system, called SPMFS. SPMFS first partitions global metadata structures of the file system into per-core structures to distribute load and relieve contention. Second, SPMFS presents a fine-grained range lock to support concurrent accesses upon a file. Finally, SPMFS designs a dedicated I/O thread pool to offer optimal parallelism inherent in underlying NVM regardless of varying user-threads. We implement an SPMFS prototype and evaluate it under a variety of workloads generated by IOtest, Filebench, FIO, and production traces from Alibaba Pangu. The experiments show that SPMFS provides better scalability, and achieves up to 2.37 × write throughput improvement over state-of-the-art kernel NVM-aware file systems (Ext4-DAX, NOVA, and PMFS) and user-space file systems (Strata and Libnvmmio), without sacrificing the read performance.

To satisfy high reliability accompanied by space efficiency requirements, erasure coding is elected to substitute replication as a redundancy mechanism of in-memory clusters. More often than not, the use of erasure coding is limited to read-intensive applications, in which data in erasure-coded clusters are rarely updated. The essential rationale is that update penalty incurred by parity-synchronizations makes long write latency compared with read latency counterpart.In this paper, we propose F-Write: a fast RDMA-supported write optimization scheme for erasure-coded in-memory clusters. It entails two distinct features: 1) an extended version of consistency protocol called Fast2PC is created. It directly modifies remote memory regions using one-sided WRITE verb provided by RDMA to implement the operations of transaction log, and records multiple transactions in the log to submit together, effectively curtailing network latency; 2) a speculative update approach is given to substitute immediate update. Aggregated undo transactions are handled speculatively to synchronize parity blocks in the background when parity blocks are needed. For multiple writes to an identical data block at different times-tamps, only the original and the latest data blocks are involved in calculating parity blocks, thus mitigating encoding latency. Experimental results indicate that F-Write has lower latency, higher throughput compared to the candidate write schemes. Moreover, the impact on recovery time is negligible. Specifically, under the update-intensive workloads, F-Write cuts down write latency by more than 61%, thereby boosting system throughput by a factor of at least 2.6x.

Emerging byte-addressable Non-volatile memories (NVM) are promising techniques as memory-like storage. Researchers have developed many NVM-aware file systems to exploit the benefits of NVM. However, many early file systems are usually evaluated based on DRAM-based simulations or emulations. Their experimental results cannot present the actual behaviors upon real NVM devices, since the devices do not perform like slow DRAMs as expected. In this paper, we provide a comprehensive empirical study of NVM-aware file systems on the first commercially available byte-addressable NVM (i.e., the Intel Optane DC Persistent Memory Module (PMM)). We evaluate and analyze the performance of the kernel-level file systems (XFS-DAX, Ext4-DAX, PMFS, and NOVA) and the user-space file systems (Strata and Libnvmmio) on PMM with various synthetic and real-world benchmarks (FIO, Filebench, FXmark, Redis, etc.). We also employ different file system configurations and different PMM configurations to evaluate their performance impact. We believe that the experimental results and performance analysis will provide implications for the developers of various applications and storage systems to reap the full characteristics of NVMs.

The application of product-level persistent memory (PM) presents a great opportunity for key-value stores. However, PM devices differ significantly from traditional block-based storage devices such as HDD and SSD in terms of IO characteristics and approaches. To reveal the adaptability of existing persistent key-value store on PM and to explore the potential optimization space of PM-based key-value stores, we migrate one of the most widely used persistent key-value store, RocksDB, to PM device and evaluated its performance. The results show that the performance of RocksDB is limited by the traditional IO stacks optimized for fast SSDs on PM devices. We then perform further experimental analysis on the IO methods of the two main files, log and SST, in RocksDB. Based on the results, we propose a set of optimized IO configurations for each of the two files. These configurations improve read and write performance of RocksDB by up to 3× and 2×, respectively, over the default configurations on an Intel Optane Persistent Memory.

Large-scale cloud storage systems use the logging mechanism to sequentially write data in an append-only manner. The write stream needs to be first appended and persisted into logging files, and then encoded with erasure coding (EC) in underlying storage. This introduces significant overhead to small write operations. To solve this problem, we propose EFLOG, a full-streaming storage framework that combines Logging and inter-log EC mechanisms. EFLOG evenly schedules front-end write streams across log files in each disk with append-only manner. In background, EFLOG determines unprotected logged data and seals them into ECblocks. Afterwards, EFLOG concurrently encodes data with multi-threads and stores parity data into parity disks. Results of our trace-driven evaluation show that, EFLOG can achieve up to 1.01GB/s write throughput with RS(4, 2) codes built upon 6 SSD disks.

Streaming graph analysis extracts timely insights from evolving graphs, and has gained increasing popularity. In current practice of streaming graph analysis, incoming updates are simply cached in a buffer, until being applied onto existing graph structure to construct a new snapshot. Graph algorithms then work on the new snapshot to produce up-to-date analysis result. Nevertheless, we find that for widely used monotonic graph algorithms, the analysis process can be accelerated by preprocessing buffered updates. To this end, we propose GraPU, a streaming graph analytics system for monotonic graph algorithms. Before applying updates, GraPU preprocesses buffered updates in three consecutive stages: 1) Components-based Classification first identifies the effective graph data that are actually affected by current updates, by classifying the vertices involved in buffered updates according to the predetermined connected components in underlying graph; 2) In-buffer Precomputation generates the safe and profitable intermediate values that can be later merged onto underlying graph to facilitate convergence on new snapshots, by precomputing the values of vertices involved in buffered updates; 3) Hub-vertices Division eliminates the vertex-level load imbalance for analysis on new snapshots, by automatically identifying the high-degree vertices involved in updates and efficiently distributing their high-cost computation over multiple machines. After buffered updates are applied, GraPU calculates vertex values in new snapshots using the subgraph-centric model. GraPU further presents Load-factors Guided Balancing to achieve load balance at subgraph-level, by reassigning some vertices and edges among subgraphs beforehand. Our experimental result shows that, GraPU outperforms state-of-the-art KineoGraph by up to 20.43x.

Nowadays, cloud providers embrace hybrid storage servers to reap both high IO performance of solid-state drives (SSDs) and low-cost of hard disk drives (HDDs). These hybrid storage servers generally employ SSDs as primary storage directly serving requests from front-end applications while using HDDs as the secondary storage to provide sufficient storage capacity.

Machine Learning and Data Mining (MLDM) applications, such as recommendation and topic modeling, generally represent their input data in bipartite graphs with two disjoint vertex-subsets connected only by edges between them. Despite the prevalence of bipartite graphs, existing graph partitioning frameworks have rarely sufficiently exploited their unique structures, especially the highly lopsided subset sizes and extremely skewed vertex degrees. As a result of poor partitioning quality, problems, particularly of high communication cost and severe workload imbalance, arise during subsequent computation over these bipartite graphs in distributed environments such as datacenters or HPC systems, significantly hampering the performance of MLDM applications.

Surveillance cameras are ubiquitous around us. Emerging full-feature object-detection models can analyze surveillance videos with high accuracy but consume much computation. Directly applying these models for practical scenarios with large-scale cameras is prohibitively expensive. This, however, is wasteful and unnecessary considering that user-defined anomalies occur rarely among these videos. Therefore, we propose FFS-VA, a multi-stage Fast Filtering Mechanism for Video Analytics, to make video analytics much cost-effective. FFS-VA filters out the frames without the user-defined events by two stream-specialized filters and a cheap full-function model, to reduce the number of frames reaching the full-feature model. FFS-VA presents a global feedback-queue approach to balance the processing speeds of different filters in intra-stream and inter-stream processes. FFS-VA designs a dynamic batch technique to achieve a trade-off between throughput and latency. FFS-VA can also efficiently scale to multiple GPUs. We evaluate FFS-VA against the state-of-the-art YOLOv3 under the same hardware and video workloads. The experimental results show that under a 12.88 percent target-object occurrence rate on two GPUs, FFS-VA can support up to 30 concurrent video streams (15× more than YOLOv3) in the online case, and obtain 10× speedup when offline analyzing a stream, with an accuracy loss of less than 2 percent.

Existing local file systems, designed to support a typical single-file access mode only, can lead to poor performance when accessing a batch of files, especially small files. This single-file mode essentially serializes accesses to batched files one by one, resulting in a large number of non-sequential, random, and often dependent I/Os between file data and metadata at the storage ends. Such access mode can further worsen the efficiency and performance of applications accessing massive files, such as data migration. We first experimentally analyze the root cause of such inefficiency in batch-file accesses. Then, we propose a novel batch-file access approach, referred to as BFO for its set of optimized Batch-File Operations , by developing novel BFOr and BFOw operations for fundamental read and write processes, respectively, using a two-phase access for metadata and data jointly. The BFO offers dedicated interfaces for batch-file accesses and additional processes integrated into existing file systems without modifying their structures and procedures. In addition, based on BFOr and BFOw, we also propose the novel batch-file migration BFOm to accelerate the data migration for massive small files. We implement a BFO prototype on ext4, one of the most popular file systems. Our evaluation results show that the batch-file read and write performances of BFO are consistently higher than those of the traditional approaches regardless of access patterns, data layouts, and storage media, under synthetic and real-world file sets. BFO improves the read performance by up to 22.4× and 1.8× with HDD and SSD, respectively, and it boosts the write performance by up to 111.4× and 2.9× with HDD and SSD, respectively. BFO also demonstrates consistent performance advantages for data migration in both local and remote situations.

Key-value (KV) stores based on multi-stage structures are widely deployed to organize massive amounts of easily searchable user data. However, current KV storage systems inevitably sacrifice at least one of the performance objectives, such as write, read, space efficiency etc., for the optimization of others. To understand the root cause of and ultimately remove such performance disparities among the representative existing KV stores, we analyze their enabling mechanisms and classify them into two fundamental models of data structures facilitating KV operations, namely, the multi-stage tree (MS-tree), and the multi-stage forest (MS-forest). We build SifrDB, a KV store on a novel split forest structure, that achieves the lowest write amplification across all workload patterns and minimizes space reservation for the compaction. To mitigate the read amplification inherent in MS-forest, we introduce a bloom filer mechanism based on Sorted String Tables (SSTs). Furthermore, we also present a highly efficient parallel search approach that fully exploits the access parallelism of modern flash-based storage devices to substantially boost the read performance. Evaluation results show that under both micro and YCSB benchmarks, SifrDB outperforms its closest competitors, i.e., the popular MS-forest implementations, making it a highly desirable choice for the modern KV stores.

Redundancy schemes are introduced to in-memory stores to provide fault tolerance. To achieve good trade-off between access performance and memory efficiency, it is appropriate to adopt replication and erasure coding to keep popular and unpopular data, respectively. Within such a hybrid-redundancy in-memory store, an issue of redundancy transition from replication to erasure coding (a.k.a., erasure-coded archival) should be addressed for unpopular in-memory datasets, since caching workloads exhibit long-tail distributions and most in-memory data are unpopular. If data replicas are distributed across nodes in randomly-selected racks, then subsequent data-block-replica retrieval for erasure-coded archival will create cross-rack traffic, and final parity-block relocation will cause extra cross-rack communications. In this article, we propose an encoding-oriented replica placement policy - ERP - by incorporating an interleaved declustering mechanism. We design two traffic-aware erasure-coded archival schemes -TEA-TL and TEA-SL - for ERP-powered in-memory stores by taking into account temporal locality and spatial locality, respectively. With ERP in place, both TEA-TL and TEA-SL schemes embrace the following three salient features: (i) they alleviate cross-rack traffic raised by retrieving required data-block replicas; (ii) they improve rack-level load balancing by distributing replicas via load-aware primary-rack-selection approach; and (iii) they mitigate block-relocation operations launched to sustain rack-level and node-level fault-tolerance. We conduct quantitative performance evaluations using the YCSB benchmark. The empirical results show that both TEA-TL and TEA-SL schemes not only bring forth lower cross-rack traffic than the four candidate encoding schemes, but also exhibit superb archival-throughput and rack-level-balancing performance. In particular, within a group of comparative tests using the baseline configurations, TEA-TL and TEA-SL accelerate archival throughput by at least 36.3 and 70.8 percent, respectively; both TEA-TL and TEA-SL schemes improve rack-level load-balancing by a factor of more than 1.45x relative to the four candidate encoding schemes.

TLC flash has three types of pages to accommodate the three bits in each TLC physical cell exhibiting very different program latencies. This paper proposes PA-SSD to effectively improve the overall performance by exploiting the dissimilarity of TLC pages on program latency throughout the write request handling workflow. The main idea behind PA-SSD is to coordinately allocate the same type of pages for sub-requests of any given user write request, to mitigate the potential program latency imbalance among the sub-requests, and to schedule sub-requests according to their page-types. We achieve the PA-SSD design goal by answering three key research questions: (1) how to properly determine page-type for each user write request? (2) how to actually allocate a physical page for each sub-request with an assigned page-type from (1)? (3) how to effectively schedule the sub-requests in the chips queues when their page-types are judiciously allocated from (2)? To answer the first question, we propose seven page-type specifying schemes to investigate their effects under different workloads. We answer the second question by redesigning the page allocation strategy in TLC SSD to uniformly and sequentially determine physical pages for allocation following the internal programming process of TLC flash. Lastly, a page-type aware scheduling policy is presented to reorder the sub-requests within chips' queues. Our experiments show that PA-SSD can accelerate both the write and read performance. Particularly, our proposed queue-depth based page-type specifying scheme improves write performance by 2.6 times and read performance by 1.5 times over the conventional TLC SSD.

In the era of 'dark silicon', modern data centers have to provision additional hardware resources to guarantee the Quality of Service (QoS) of applications in case of bursty workloads that typically occur in low frequency but high intensity. Fortunately, Computational Sprinting has proven to be an effective approach to boost the computing performance of many-core processor chips, which allows a chip to exceed its power and thermal limits temporarily by turning on all processor cores and absorbing the extra heat dissipation with novel phase-changing materials. Consequently, it offers a promising way to deal with these occasional workload bursts by unleashing the full potentials of hardware, avoiding deploying extra computing resources. In this work, we propose ESprint, a QoS-aware management system based on an effective feedback control mechanism for latency-critical applications in data centers. ESprint can perform computational sprinting by precisely scheduling core count, frequency levels, and sprinting duration, serving bursty workloads without QoS violation under the thermal constraint. Specifically, ESprint effectively predict load intensity in the next time interval, and further dynamically allocates appropriate computing resources to minimize actual power consumption. Our prototype-based evaluation results show that ESprint achieves up to 1.92x improvement on energy efficiency for typical workloads while ensuring QoS, over the non-sprinting strategy. We also explore the design space among energy efficiency, core count/frequency scaling techniques, workload characteristics, burst intensity, and QoS requirements, and draw several key insights to guide the effective use of computational sprinting in data centers.

Cloud providers like the Alibaba cloud routinely and widely employ hybrid storage nodes composed of solid-state drives (SSDs) and hard disk drives (HDDs), reaping their respective benefits: performance from SSD and capacity from HDD. These hybrid storage nodes generally write incoming data to its SSDs and then flush them to their HDD counterparts, referred to as the SSD Write Back (SWB) mode, thereby ensuring low write latency. When comprehensively analyzing real production workloads from Pangu, a large-scale storage platform underlying the Alibaba cloud, we find that (1) there exist many write dominated storage nodes (WSNs); however, (2) under the SWB mode, the SSDs of these WSNs suffer from severely high write intensity and long tail latency. To address these unique observed problems of WSNs, we present SSD Write Redirect (SWR), a runtime IO scheduling mechanism for WSNs. SWR judiciously and selectively forwards some or all SSD-writes to HDDs, adapting to runtime conditions. By effectively offloading the right amount of write IOs from overburdened SSDs to underutilized HDDs in WSNs, SWR is able to adequately alleviate the aforementioned problems suffered by WSNs. This significantly improves overall system performance and SSD endurance. Our trace-driven evaluation of SWR, through replaying production workload traces collected from the Alibaba cloud in our cloud testbed, shows that SWR decreases the average and 99til-percentile latencies of SSD-writes by up to 13% and 47% respectively, notably improving system performance. Meanwhile the amount of data written to SSDs is reduced by up to 70%, significantly improving SSD lifetime.

To address the write performance problem suffered by MLC/TLC flash, researchers have proposed hybrid SSD that aims to combine the strengths of SLC flash, used as the write-buffer zone for its superior write performance, and MLC/TLC flash, as the capacity zone for its high storage density. While leveraging SLC as a physical write-buffer zone is proven effective in traditional 2D hybrid SSDs, how to effectively incorporate SLC into a 3D-stacked TLC to form a hybrid SSD has not been studied to the best of our knowledge. Yet this is a timely and important performance issue for 3D-stacked TLC given its one-shot programming scheme that results in much worse write performance than the programming scheme in 2D TLC where pages are associated with different bits of a cell and programmed in sequence separately. We believe that naively adopting the two-physical-zone approach to 3D hybrid SSD will miss a great opportunity for performance optimization because it ignores the inherent four-level parallelism (channel/chip/die/plane) of the flash chip array. To this end, we propose in this paper an SLC and Parallelism Aware hybrid SSD (SPA-SSD) to take full advantages of SLC's superior write performance, the internal multi-level parallelism of SSD, and the high storage density of 3D-stacked TLC flash. Two novel techniques enable SPA-SSD to be highly effective: (1) Type-Parallelism Joint Page Allocation (TPJ-PA), which allocates pages for write transactions according to not only available SLC pages but also parallelism to maximize resource utilization within the hybrid SSD, and (2) Queue-length and Parallelism Constrained Data Migration (QPC-DM), which triggers data migration without degrading user write performance by analyzing the device queue length and available flash resources. To evaluate performance of SPA-SSD, a hybrid SSD simulator, called HybridSim, is developed based on MQSim. Experimental results on HybridSim show that TPJ-PA improves write throughput by 60%, while QPC-DM improves write throughput by up to 10 times. Besides, trace-driven experiments on HybridSSD demonstrate that SPA-SSD improves the write latency to the flash by up to two orders of magnitude over the state-of-the-art designs.

To achieve good trade-off between access performance and memory efficiency, it is appropriate to adopt replication and erasure coding to keep popular and unpopular in-memory datasets, respectively. An issue of redundancy transition from replication to erasure coding (a.k.a., erasure-coded archival) should be addressed for unpopular in-memory datasets, since caching workloads exhibit long-tail distributions and most in-memory data are unpopular.

Identifying key scenes in massive surveillance videos is extremely challenging because these scenes occur rarely while automotive identification using full-feature neural network (NN) models consumes immense computational resources. This paper proposes VScan, an efficient model-joint mechanism that adaptively schedules streams on a light-weight NN model and a full-feature NN model for analyzing videos concurrently. These two combined models with overlapped detectable objects are generic and well-developed. The former model fast scans videos to seek potential interest scenes. Only the streams with identified scenes are further analyzed by the latter model. We provide a model selection approach to select a light-weight model with an appropriate accuracy and high throughput. VScan further determines key parameters to correct predictions at runtime, thus guaranteeing the recall of target scenes. The full-feature model is responsible for ensuring output precision. To maintain a high hardware efficiency and utilization dynamically, VScan uses automatic sampling to reduce unnecessary computations, proposes stream scheduling to maximize hardware usage, and designs GPU scheduling to optimize the data processing flow. Experimental results show that benefitting from the model-joint mechanism and runtime scheduling optimizations, VScan significantly boosts the video processing throughput by up to 15x without key scene loss.

Existing local file systems, designed to support a typical single-file access pattern only, can lead to poor performance when accessing a batch of files, especially small files. This single-file pattern essentially serializes accesses to batched files one by one, resulting in a large number of non-sequential, random, and often dependent I/Os between file data and metadata at the storage ends. We first experimentally analyze the root cause of such inefficiency in batch-file accesses. Then, we propose a novel batch-file access approach, referred to as BFO for its set of optimized Batch-File Operations, by developing novel BFOr and BFOw operations for fundamental read and write processes respectively, using a two-phase access for metadata and data jointly. The BFO offers dedicated interfaces for batch-file accesses and additional processes integrated into existing file systems without modifying their structures and procedures. We implement a BFO prototype on ext4, one of the most popular file systems. Our evaluation results show that the batch-file read and write performances of BFO are consistently higher than those of the traditional approaches regardless of access patterns, data layouts, and storage media, with synthetic and real-world file sets. BFO improves the read performance by up to 22.4× and 1.8× with HDD and SSD respectively; and boosts the write performance by up to 111.4× and 2.9× with HDD and SSD respectively. BFO also demonstrates consistent performance advantages when applied to four representative applications, Linux cp, Tar, GridFTP, and Hadoop.

Data centers have been becoming public utilities to provide large-scale computing and storage services. The Total Cost of Ownership (TCO) models for such data centers are paramount to deeply understand their cost of investment and maintenance, the cost composition of internal components, and further cost optimization directions. Existing data center TCO models focus on either high-performance data centers or key subsystems such as IT facility, lacking of holistic analysis of the data centers designed for long-term data preservation. The long-term data centers can be built with different combinations of storage media such as HDDs, tapes, and optical discs. Meanwhile, during the long operation period, devices replacement and data migration are necessary and are not negligible in cost. In order to comprehensively and quantitatively understand the cost of long-term data preservations, we proposed LT-TCO, a TCO calculation model for data centers over time. LT-TCO simulates the construction and operation of a data center to calculate the expenditure of each year. It also introduces the cost of devices replacement and data migration during the long running period. Based on the storage media as optical discs, tapes, HDDs, and SSDs, LT-TCO evaluates the corresponding capital and operational expenditure under different developing rates. The simulation result shows that in long-term preservation, data migration cost takes more than 96% of the operational expenditure. And the TCO of optical disc data centers could be the least among four storage media.

Data updates have become an important issue in erasure-coded in-memory stores owing to the two-fold reasons: (i) a handful of data-intensive in-memory stores adopt erasure coding for ‘hot’ data and (ii) small writes in update-intensive in-memory workloads cause expensive updating overheads. After delving into prior updating schemes in erasure-coded storage clusters, we investigate the applicability of these schemes to erasure-coded in-memory stores. We propose a grouped-updating mechanism—GU—to handle small writes in in-memory stores. With GU in place, requests in an updating window are categorized into several updating groups, where multiple small updates in an updating group can be concurrently executed. Two GU updating procedures—GU-stripe and GU-node—are developed to schedule updates according to a stripe and a node holding an updated data block, respectively. Furthermore, we develop two hybrid-updating schemes—Hybrid−U[GU-stripe] and Hybrid−U[GU-node]—to process common writes (i.e. small and large writes) initiated by the GU-stripe- and GU-node-based updating schemes, respectively. Replaying an update-heavy workload generated by YCSB benchmark, we extensively evaluate the four non-GU-based updating schemes, five GU-stripe-based updating schemes, and five GU-node-based updating schemes. Our experiments demonstrate that the GU mechanism boosts updating performance of small writes for RS-coded in-memory stores in terms of updating time and updating traffic. In particular, for a (8, 6) RS-coded in-memory store, the GU-stripe- and GU-node-based updating schemes shortens the updating time of the non-GU-based counterparts by a factor of at least 2.08 and 2.66, respectively. Compared to a single GU-based updating scheme, a GU-based hybrid updating scheme achieves an optimal updating-time and updating-traffic performance.

Multilevel cell (MLC) states with lower threshold voltage endure less cell damage, lower retention error, and less current consumption. Based on these characteristics, it is opportunistic to strengthen MLC flash by introducing bit-flipping that reshapes state proportions on MLC pages. In this paper, we present a holistic study of bit-flipping schemes upon MLC flash in theory and practice. Specifically, we systematically investigate effective bit-flipping schemes and propose four new schemes on manipulating MLC states. We further design a generic implementation framework, named MLC bit-flipping framework, to implement bit-flipping schemes within solid state drives controllers, nicely integrating with existing system-level optimizations to further improve overall performance. The experimental results demonstrate that our proposed bit-flipping schemes standalone can reduce up to 28% cell damages and 53% retention errors. Our circuit-level simulation manifests that the bit-flipping latency on a page is less than 4 $\mu \text{s}$ when using 8K logic gates.

Computational Sprinting, which allows a chip to exceed its power and thermal limits temporarily by turning on all processor cores and absorbing the extra heat dissipation with certain phase-changing materials, has proven to be an effective way to boost the computing performance for bursty workloads. However, extra power available for sprinting is constrained by existing power distribution infrastructures. Using batteries alone to provide the additional power to achieve performance target not only limits the effectiveness of sprinting, but also negatively impacts the lifetime of the batteries. Leveraging renewable power supply in a green data center provides an opportunity to make full use of Computational Sprinting. However, the intermittent nature of renewable energy, along with limited cooling capacity, makes it very challenging. In this paper, we propose GreenSprint, a renewable energy driven approach that enables a data center to boost its computing performance efficiently by conducting computational sprinting under the intermittent and time-varying nature of renewable energy supply. Three basic strategies are designed to determine the core count and frequency level for sprinting based on current power supply. Furthermore, we propose a Hybrid strategy that combines reinforcement learning to dynamically determine the optimal server setting, targeting at both the power provision safety and the quality of service. In consideration of practical cooling conditions, we also present a thermal-aware sprinting strategy Hybrid-T. Finally, we build an experimental prototype to evaluate GreenSprint on a cluster of 10 servers with a simulated solar power generator. The results show that renewable energy by itself can sustain different duration lengths of sprinting when its supply is sufficient and can improve performance by up to 4.8x for representative interactive applications. We also show the effectiveness of core-count and frequency scaling in the presence of varied renewable power and limited battery energy.

Key-value stores are increasingly adopting LSM-trees as their enabling data structure in the backend block storage, and persisting their clustered data through a block manager, usually a file system. In general, a file system is expected to not only provide file/directory abstraction to organize data but also retain the key benefits of LSM-trees, namely, sequential and aggregated I/O patterns on the physical device. Unfortunately, our in-depth experimental analysis reveals that some of these benefits of LSM-trees can be completely negated by the underlying file level indexes from the perspectives of both data layout and I/O processing. As a result, the write performance of LSM-trees is kept at a level far below that promised by the sequential bandwidth offered by the storage devices. In this paper, we address this problem and propose LDS, an LSM-tree Direct Storage system that manages the storage space based on the LSM-tree objects and provides simplified consistency control by leveraging the copy-on-write nature of the LSM-tree structure, to fully reap the benefits of LSM-trees. Running LevelDB, a popular LSM-tree based key-value store, on LDS as a baseline, comparing that to LevelDB running on three representative file systems (ext4, f2fs, btrfs) with HDDs and SSDs, respectively, we evaluate and study the performance potentials of LSM-trees. Evaluation results show that the write throughputs of LevelDB can be improved by from 1.8× to 3× on HDDs, and from 1.3× to 2.5× on SSDs, by employing the LSM-tree friendly data layout of LDS.

Data deduplication has been widely introduced to effectively reduce storage requirement of virtual machine (VM) images running on VM servers in the virtualized cloud platforms. Nevertheless, the existing state-of-the-art deduplication for VM images approaches can not sufficiently exploit the potential of underlying hardware with consideration of the interference of deduplication on the foreground VM services, which could affect the quality of VM services. In this paper, we present HPDV, a highly parallel deduplication cluster for VM images, which well utilizes the parallelism to achieve high throughput with minimum interference on the foreground VM services. The main idea behind HPDV is to exploit idle CPU resource of VM servers to parallelize the compute-intensive chunking and fingerprinting, and to parallelize the I/O-intensive fingerprint indexing in the deduplication servers by dividing the globally shared fingerprint index into multiple independent sub-indexes according to the operating systems of VM images. To ensure the quality of VM services, a resource-aware scheduler is proposed to dynamically adjust the number of parallel chunking and fingerprinting threads according to the CPU utilization of VM servers. Our evaluation results demonstrate that compared to a state-of-the-art deduplication system for VM images called Light, HPDV achieves up to 67% deduplication throughput improvement.

Key-value (KV) stores based on multi-stage structures are widely deployed in the cloud to ingest massive amounts of easily searchable user data. However, current KV storage systems inevitably sacrifice at least one of the performance objectives, such as write, read, space efficiency etc., for the optimization of others. To understand the root cause of and ultimately remove such performance disparities among the representative existing KV stores, we analyze their enabling mechanisms and classify them into two models of data structures facilitating KV operations, namely, the multi-stage tree (MS-tree) as represented by LevelDB, and the multi-stage forest (MS-forest) as typified by the size-tiered compaction in Cassandra. We then build a KV store on a novel split MS-forest structure, called SifrDB, that achieves the lowest write amplification across all workload patterns and minimizes space reservation for the compaction. In addition, we design a highly efficient parallel search algorithm that fully exploits the access parallelism of modern flash-based storage devices to substantially boost the read performance. Evaluation results show that under both micro and YCSB benchmarks, SifrDB outperforms its closest competitors, i.e., the popular MS-forest implementations, making it a highly desirable choice for the modern large-dataset-driven KV stores.

Streaming graph analysis extracts timely insights from evolving graphs, and has gained increasing popularity. For current streaming graph analytics systems, incoming updates are simply cached in a buffer, until being applied onto existing graph structure to construct a new snapshot. Iterative graph algorithms then work on the new snapshot to produce up-to-date analysis result. Nevertheless, we find that for widely used monotonic graph algorithms, the buffered updates can be effectively preprocessed to achieve fast and accurate analysis on new snapshots.

Surveillance video cameras are ubiquitous around us. Full-feature object-detection models such as YOLOv2 can automatically analyze surveillance videos in real-time with high accuracy while consuming huge computational resources. Directly applying these models for practical scenarios with large-scale deployed cameras requires prohibitively expensive computation. This, however, is both wasteful and unnecessary considering the fact that the concerned anomalous events occur rarely among these massive volumes of video streams. Therefore, in this paper, we propose a Fast Filtering System for Video Analytics (FFS-VA), a pipelined multi-stage video analyzing system, to make video analytics much cost-effective. FFS-VA is designed to filter out vast but non-target-object frames by two prepositive stream-specialized filters and a small full-function tiny-YOLO model, to drastically reduce the number of video frames arriving at the full-feature model in the back-end. FFS-VA presents a global feedback-queue mechanism to balance the processing rates of different filters in both intra-stream and inter-stream processes. FFS-VA also designs a dynamic batch technique to achieve an adjustable trade-off between throughput and latency. FFS-VA reasonably distributes all tasks on CPUs and GPUs to fully exploit the underlying hardware resources. We implement a FFS-VA prototype and evaluate FFS-VA against the state-of-the-art YOLOv2 under the same hardware and representative video workloads. The experimental results show that under a 10% target-object occurrence rate on two GPUs, FFS-VA can support up to 30 concurrent video streams (7x more than YOLOv2) in the online case, and obtain 3x speedup when offline analyzing a stream, with an accuracy loss of less than 2%.

TLC flash has three types of pages to accommodate the three bits in each TLC physical cell exhibiting very different program latencies, LSB (fast), CSB (medium), and MSB (slow). Conventional TLC SSD designs on page allocation to write requests do not take page types and their latency difference into consideration, missing on an important opportunity to exploit the potentials of fast writes.

Computational Sprinting has proven to be an effective way to boost the computing performance for bursty workloads, which allows a chip to exceed its power and thermal limits temporarily by turning on all processor cores and absorbing the extra heat dissipation with certain phase-changing materials. However, extra power available for sprinting is constrained by existing power distribution infrastructures. Using batteries alone to provide the additional power to achieve performance target not only limits the effectiveness of sprinting, but also negatively impacts the lifetime of the batteries. Leveraging renewable power supply in a green data center provides an opportunity to exploit the maximal potential of Computational Sprinting. However, the intermittent nature of renewable energy makes it very challenging. In this paper, we propose GreenSprint, a renewable energy driven approach that enables a data center to boost its computing performance efficiently by conducting computational sprinting. We present four sprinting strategies to address the challenge imposed by the intermittent and time-varying nature of renewable energy supply. We build an experimental prototype to evaluate GreenSprint on a cluster of 10 servers with a simulated solar power generator. The results show that renewable energy by itself can sustain different duration lengths of sprinting when its supply is sufficient and can improve performance by up to 4.8x for representative interactive applications. We also show the effectiveness of core-count and frequency scaling in the presence of varied renewable power and limited battery energy.

The combination of the explosive growth in digital data and the demand to preserve much of these data in the long term has made it imperative to find a more cost-effective way than HDD arrays and a more easily accessible way than tape libraries to store massive amounts of data. While modern optical discs are capable of guaranteeing more than 50-year data preservation without media replacement, individual optical discs’ lack of the performance and capacity relative to HDDs or tapes has significantly limited their use in datacenters. This article presents a Rack-scale Optical disc library System, or ROS in short, which provides a PB-level total capacity and inline accessibility on thousands of optical discs built within a 42U Rack. A rotatable roller and robotic arm separating and fetching discs are designed to improve disc placement density and simplify the mechanical structure. A hierarchical storage system based on SSDs, hard disks, and optical discs is proposed to effectively hide the delay of mechanical operation. However, an optical library file system (OLFS) based on FUSE is proposed to schedule mechanical operation and organize data on the tiered storage with a POSIX user interface to provide an illusion of inline data accessibility. We further optimize OLFS by reducing unnecessary user/kernel context switches inheriting from legacy FUSE framework. We evaluate ROS on a few key performance metrics, including operation delays of the mechanical structure and software overhead in a prototype PB-level ROS system. The results show that ROS stacked on Samba and FUSE as network-attached storage (NAS) mode almost saturates the throughput provided by underlying samba via 10GbE network for external users, as well as in this scenario provides about 53ms file write and 15ms read latency, exhibiting its inline accessibility. Besides, ROS is able to effectively hide and virtualize internal complex operational behaviors and be easily deployable in datacenters.

Key-value stores are increasingly adopting LSM-trees as their enabling data structure in the backend storage, and persisting their clustered data through a file system. A file system is expected to not only provide file/directory abstraction to organize data but also retain the key benefits of LSM-trees, namely, sequential and aggregated I/O patterns on the physical device. Unfortunately, our in-depth experimental analysis reveals that some of these benefits of LSM-trees can be completely negated by the underlying file level indexes from the perspectives of both data layout and I/O processing. As a result, the write performance of LSM-trees is kept at a level far below that promised by the sequential bandwidth offered by the storage devices. In this paper, we address this problem and propose LDS, an LSM-tree based Direct Storage system that manages the storage space and provides simplified consistency control by exploiting the copy-on-write nature of the LSM-tree structure, so as to fully reap the benefits of LSM-trees.

The combination of the explosive growth in digital data and the need to preserve much of this data in the long term has made it an imperative to find a more cost-effective way than HDD arrays and more easily accessible way than tape libraries to store massive amounts of data. While modern optical discs are capable of guaranteeing more than 50-year data preservation without migration, individual optical disks' lack of the performance and capacity relative to HDDs or tapes has significantly limited their use in datacenters. This paper presents a Rack-scale Optical disc library System, or ROS in short, that provides a PB-level total capacity and inline accessibility on thousands of optical discs built within a 42U Rack. A rotatable roller and robotic arm separating and fetching the discs are designed to improve disc placement density and simplify the mechanical structure. A hierarchical storage system based on SSD, hard disks and optical discs are presented to hide the delay of mechanical operation. On the other hand, an optical library file system is proposed to schedule mechanical operation and organize data on the tiered storage with a POSIX user interface to provide an illusion of inline data accessibility. We evaluate ROS on a few key performance metrics including operation delays of the mechanical structure and software overhead in a prototype PB-level ROS system. The results show that ROS stacked on Samba and FUSE can provide almost 323MB/s read and 236MB/s write throughput, about 53ms file write and 15ms read latency via 10GbE network for external users, exhibiting its inline accessibility. Besides, ROS is able to effectively hide and virtualize internal complex operational behaviors and be easily deployable in datacenters.

Distributed graph processing frameworks attempt to eliminate workload imbalance among computing nodes. However, this expectation is generally challenged by underlying heterogeneous nodes and fluctuating graph workloads at runtime. This paper proposes Laro, a graph processing system using dynamic graph repartitioning that collects the actual processing times from all nodes, then reconstructs a vertices distribution with minimal migration costs in every iteration. We manifest that the Variation Coefficient of processing times is a critical metric to quantitatively characterize the workload imbalance among nodes at each iteration. Laro also presents a lazy repartitioning algorithm to improve migration efficiency. Laro has been implemented by extending GPS, a popular repartitioning-featured graph processing system. Our evaluation using real-world graphs shows that, by achieving more balanced workload distributions at runtime, Laro derives maximal speedup of 1.82x and 1.41x over the static Skewed Hash and the dynamic GPS respectively.

Deep learning has exhibited high accuracy and applicability in machine learning field recently, by consuming tremendous computational resources processing massive data. To improve the performance of deep learning, GPUs have been introduced to accelerate the training phase. The complex data processing infrastructure demands high-efficient collaboration among underlying hardware components, such as CPU, GPU, memory, and storage devices. Unfortunately, few work has presented a systematic analysis about the impact of hardware configurations on the overall performance of deep learning. In this paper, we aim to make an experimental study on a standalone system to evaluate how various hardware configurations affect the overall performance of deep learning. We conducted a series of experiments using varied configurations on storage devices, main memory, CPU, and GPU to observe the overall performance quantitatively. Based on analyzing these results, we found that the performance greatly relies on the hardware configurations. Specifically, the computation is still the primary bottleneck as double GPUs and triple GPUs shorten the execution time by 44% and 59% respectively. Besides, both CPU frequency and storage subsystem can significantly affect running time while the memory size has no obvious effect on the running time for training neural network models. We believe our experimental results can help shed light on further optimizing the performance of deep learning in computer systems.

Data-intensive applications are increasingly depending on in-memory stores to meet high-I/O-performance requirements. To be resilient to server failures and in turn achieve high availability, both replication and erasure codes are introduced to in-memory stores. Since erasure codes have an advantage of memory efficiency over replication, we focus our work on erasure-coded in-memory stores and investigate placement schemes to address the issue of workload fluctuation. To mitigate the I/O imbalanced incurred by workload skew and maximize the utilization of all nodes, we proposed a Workload-aware Placement Scheme called WPS for Reed-Solomon-coded in-memory stores. WPS accomplishes balanced I/Os as follows: it divides in-memory data blocks into multiple groups based on access characteristics (e.g., popularity), and classifies all nodes into several groups according to nodes' access performance (e.g., indicated by available bandwidth), and places or migrates high-access-popularity in-memory data blocks to high-performance nodes without violating the essential principle of fault tolerance. The comparative experiments indicate that WPS can significantly improve load balancing for RS-coded in-memory stores exhibiting workload popularity skew; meanwhile, WPS achieves comparable mean, median, and tail latencies relative to two candidate placement schemes.

Erasure coding has been gradually adopted by existing data-intensive in-memory stores for 'hot' data; small writes lead to expensive updating overheads in such in-memory stores characterized by update-heavy workloads. There is a pressing demand to address the issue of data updates for erasure-coded in-memory stores. We revisit existing updating schemes in erasure-coded storage clusters by investigating the applicability of these updating schemes to erasure-coded in- memory stores. After an intensive analysis, we propose a grouping-update mechanism - GU - to handle small writes in in-memory stores. With GU in place, requests in an updating window are categorized into several updating groups, where multiple small updates in the same stripe can be executed concurrently. Furthermore, we bring forward a hybrid-updating scheme - Hybrid-U - to minimize total updating I/Os over network under common writes (e.g., small and large writes). We evaluate four dedicated updating schemes, four GU- based updating schemes and Hybrid-U. Our experiments illustrate that GU-based updating schemes and Hybrid-U outperform the four dedicated updating schemes in terms of updating time.

In this paper, we propose GreenGear, the first heterogeneous strategy that incorporates wimpy servers into existing green data centers to dynamically deal with power mismatches. Our techniques exploit intelligent green power scheduling policies to provide efficiency-aware power management. We evaluate the GreenGear design on a prototype installed in a test-bed. Compared with a homogeneous server system, GreenGear is able to significantly increase the effective use of the renewable and battery power sources without the supplement of grid power, extending their runtime by 57%, lengthening the UPS lifetime by 2.04X, and improving renewable energy utilization by 51%.

Heterogeneous servers have long been introduced to improve energy efficiency in warehouse-scale computers(WSCs). However, running latency-critical web-services on heterogeneous servers is still challenging because the overheads of transition between such servers heavily impact overall benefits and performance. We propose Montgolfier, a runtime power management system based on a latency-aware feedback control mechanism. It consolidates wimpy and brawny servers into composite nodes to improve energy efficiency while ensuring QoS for latency-critical applications. Montgolfier effectively mitigates the effect of transition overhead between servers with dynamically load prediction and accurately provides thin-provisioned configurations in fine-grain manner for fluctuating loads. Our evaluation results show that Montgolfier reduces energy consumption by up to 34.9% without violating any QoS constraints.

In this paper, we propose Elastic-RAID, a new RAID architecture to achieve high performance and high reliability for large-scale distributed and parallel storage systems. The key idea behind Elastic-RAID is to smartly utilize the free space existing in parity-based disk arrays to store additional mirroring data. This additional mirroring data redundancy, when strategically and judiciously activated and exploited in a RAID system, enables improved system I/O performance, fault tolerance and recovery. Depending on the amount of free space available and whether the emphasis is on performance or reliability, the elasticity in Elastic-RAID is manifested in how each design objective is achieved. For the performance objective, Elastic-RAID improves small-write performance by writing original and mirroring data synchronously and leaving the costly parity update in the background at a later idle/lightly-loaded time. For the reliability objective, at least two concurrent disk failures can be tolerated when Elastic-RAID is employed in a RAID5 system that has 50 percent or more free space. Higher reliability is provided for important data when free space is less than 50 percent. To achieve the design goal of elasticity, we introduce a novel data layout and addressing scheme. Our extensive trace-driven evaluations on an Elastic-RAID prototype in the typical configurations of RAID5 show that Elastic-RAID boosts the small-write performance in the normal operational state by at least 40 percent, improves the user I/O performance in the reconstruction state by at least 30 percent and shortens the recovery time by at least 40 percent.

Erasure codes are widely deployed in storage systems and the encoding/decoding process is a common operation in erasure-coded systems. Parity-check matrix method is a general method employed in erasure codes to conduct encoding/decoding process. However, the process is serial and generates high computational cost in dealing with matrix operations, and hence, causes low encoding/decoding performance. Especially for some recently proposed erasure codes, including SD code, PMDS code, and LRC code, the disadvantages are more obvious. To address this issue, in this paper, we present an optimization algorithm, called Partitioned and Parallel Matrix (PPM) algorithm, to accelerate the encoding/decoding processes of these codes by partitioning the parity-check matrix, parallelizing the encoding/decoding operations, and optimizing the calculation sequence, so as to achieve the goal of fast encoding/decoding. Experimental results show that PPM can speed up the encoding/decoding process of these codes by up to 210.81%.

While there have been prior studies on underprovisioning the power distribution infrastructure for a grid-based datacenter, how to save grid capital investment by means of leveraging renewable energy to underprovision the grid power infrastructure in green datacenters remains largely an unexplored, open issue. Aggressively underprovisioning grid infrastructure can trigger power emergency in which simultaneous peak power draws across the datacenter exceed the tightly budgeted grid power capacity, leading to possible serious consequences including power shutdown. The resulting power emergency mandates a graceful reaction mechanism to sustain the power requirement to avoid power overdraw. While leveraging renewable energy in a green datacenter provides a possibility to prevent power overdraw during such a power emergency, the intermittent nature of renewable energy makes it a very challenging task because of the potentially unpredictable performance impact to individual applications. This paper addresses this issue by designing a novel renewable energy delivery infrastructure and considering performance consequences to individual applications of underprovisioning the grid power infrastructure in the presence of varied renewable power and limited battery's energy capacity in a datacenter. We build an experimental prototype to demonstrate such grid power underprovisioning on a cluster of 10 servers, with a simulated solar power generator. Using representative datacenter benchmarks to evaluate the effectiveness of the renewable solution in handling power emergencies, we show that renewable energy by itself can sustain different duration lengths of power emergency when its supply is sufficient. Batteries play an important role for performance boost when the supply of the renewable energy is insufficient. Our theoretical solution, in conjunction with workload migration, provides a seamless bridge across the whole spectrum of duration lengths of power emergency.

While inheriting from RAID-6 codes protecting data against two simultaneous disk failures, XOR-based RAID-6 codes are low computational complexity due to only using exclusive-or operations to encode and decode, and are extensively studied and employed in practical. But the potential parallelism of these codes have not yet been sufficiently explored. In this paper, we observe that for XOR-based RAID-6 coding procedures, calculations of parity check equations can be decomposed into pre-calculating and recursive resolution phases. Moreover, these pre-calculating phases of equations can execute in parallel to obtain intermediate blocks that are further used to recursively resolve all missing blocks in a specific sequence. Based on this observation, we present a parallel coding algorithm, called EOPC, for XOR-based RAID-6 codes with the z-turn property, where there exists at least one parity check equation having only one unavailable block under their fault tolerance. We further build EOPC based on two representative XOR-based RAID-6 codes-RDP code and P-Code, to evaluate the effectiveness of EOPC. Experiment results show that EOPC approach outperforms the corresponding serialized approach by more than 50% in encoding/ decoding throughput.

As hard disk failure rates are rarely improved and the reconstruction time for TB-level disks typically amounts to days, multiple concurrent disk/storage node failures in datacenter storage systems become common and frequent. As a result, the erasure coding schemes used in datacenters must meet the critical requirements of high fault tolerance, high storage efficiency, and fast fault recovery. In this paper, we introduce a new XOR-based non-MDS erasure code family with an ability of tolerating up to 12-disk/node failures, called PSG-Codes. The basic idea behind PSG-Codes is to partition disks into groups, and exploit short parity chains to generate parity units. Then, the parity chain is further shortened by varying the number of parity elements for each strip. We conduct a simulation-based study to search configuration parameter space of PSG-Codes, and prove that PSG-Codes can tolerate up to 12 disk/node failures. Compared with a well-known XOR-based non-MDS code, WEAVER codes, PSG-Codes have higher storage efficiency and lower reconstruction cost. Moreover, the storage efficiency and performance of PSG-Codes are also competitive with another stat-of-the-art GF-based non-MDS codes, LRC codes.

RAID-6 is widely applied to tolerate double concurrent disk failures in both disk arrays and storage clusters. Among numerous erasure codes developed to implement RAID-6, Maximum Distance Separable (MDS) Codes are highly popular. Owing to the limitation of parity generating schemes used in MDS codes, RAID-6-based storage systems suffer from unbalance I/Os and low reconstruction performance. Out of consideration for high performance and reliability, we propose a new class of XOR-based RAID-6 code (i.e. |$V^{2}$|-Code), which improves both load balancing and reconstruction performance of the MDS RAID-6 codes. |$V^{2}$|-Code, a very simple yet flexible Non-MDS vertical code, can be easily implemented and deployed in storage systems. |$V^{2}$|-Code's unique features include lowest density code, steady parity chain length and well-balanced computation. We perform theoretical analysis and empirical evaluation of the coding scheme by running a wide range of workload under various configurations. Experimental results show that |$V^{2}$|-Code outperforms four popular codes (i.e. EVENODD, RDP, X-Code and Code-M) in terms of load balancing and reconstruction time. In the single-disk-failure and double-disk-failure cases, |$V^{2}$|-Code can speed up the reconstruction time of X-Code by a factor of up to 3.31 and 1.79, respectively.

Among redundant arrays of independent disks (RAID)-6 codes, maximum distance separable (MDS) based RAID-6 codes are popular because they have the optimal storage efficiency. Although vertical MDS codes exhibit better load balancing compared to horizontal MDS codes in partial stripes, an I/O unbalancing problem still exists in some vertical codes. To address this issue, we propose a novel efficient data layout, uniform P-code (UPC), to support highly balanced I/Os among P-coded disk arrays (i.e., PC). In UPC, the nonuniformly distributed information symbols in each parity chain of P-code are moved along their columns to other rows, thus enabling the parity chain to keep original parity relationships and tolerate double disk failures. The UPC scheme not only achieves optimal storage efficiency, computational complexity, and update complexity, but also supports better I/O balancing in the context of large-scale storage systems. We also conduct a performance study on reconstruction algorithms using an analytical model. Besides extensive theoretical analysis, comparative performance experiments are conducted by replaying real-world workloads under various configurations. Experimental results illustrate that our UPC scheme significantly outperforms the PC scheme in terms of average user response time. In particular, in the case of a 12-disk array, the UPC scheme can improve the access performance of the RAID-6 storage system by 29.9% compared to the PC scheme.

A key design goal of erasure-coded storage clusters is to minimize reconstruction time, which in turn leads to high reliability by reducing vulnerability window size. PULL-Rep and PULL-Sur are two existing reconstruction schemes based on PULL-type transmission, where a rebuilding node initiates reconstruction by sending a set of read requests to surviving nodes to retrieve surviving blocks. To eliminate the transmission bottleneck of replacement nodes in PULL-Rep and mitigate the extra overhead caused by noncontiguous disk access in PULL-Sur, we incorporate PUSH-type transmissions to node reconstruction, where the reconstruction procedure is divided into multiple tasks accomplished by surviving nodes in a pipelining manner. We also propose two PUSH-based reconstruction schemes (i.e., PUSH-Rep and PUSH-Sur), which can not only exploit the I/O parallelism of PULL-Sur, but also maintain sequential I/O accesses inherited from PULL-Rep. We build four reconstruction-time models to study the reconstruction process and estimate the reconstruction time of the four schemes in large-scale storage clusters. We implement a proof-of-concept prototype where the four reconstruction schemes are deployed and quantitatively evaluated. Experimental results show that the PUSH-based reconstruction schemes outperform the PULL-based counterparts. In a real-world (9,6)RS-coded storage cluster, PUSH-Rep speeds up the reconstruction time by a factor of 5.76 compared with PULL-Rep; PUSH-Sur accelerates the reconstruction by a factor of 1.85 relative to PULL-Sur.

Nowadays, while the storage requirement of virtual machine images generated in cloud infrastructures can be potentially reduced by the deduplication, considering their scale and intensity, the deduplication cluster is demanded. Therefore, in this paper we present SDVC, a scalable deduplication cluster for virtual machine images in cloud. SDVC offers both vertical and horizontal scalability. The horizontal scalability is supported by a three-party distributed infrastructure and a hash allocation algorithm. Meanwhile, categorized chunk tracer and buffer capture hot data. Furthermore, SDVC is vertical scalable by setting a suitable hot chunk buffer in virtual machine servers according to their resource usage, reducing chunk searching operations and relieving the workloads on dedup servers. Our experimental results based on a small scale cluster show that the deduplication throughput achieves up to 80% increase with the number of Dedup servers. Furthermore, only hundreds of Kbytes of categoried hot chunk buffer can provide almost 100% performance improvement.

To reduce the probability of data unavailability, it is extremely important to quickly recover failed data in a (k+r, k) erasure-coded storage cluster. In practice, storage nodes in a large-scale storage system have various network bandwidths and I/O capabilities, therefore, the heterogeneity of storage systems increases along with the growing scale. Both traditional recovery scheme and Fastest recovery scheme simply retrieve k surviving blocks from k surviving nodes, thereby resulting in low recovery performance in a heterogeneous storage cluster. In this paper, we propose a Load-aware Recovery Scheme (Lars) for heterogeneous RS-coded storage clusters. Lars not only takes into account both the heterogeneity and load of nodes, but also enables all surviving nodes to service reconstruction reads. The amount of surviving blocks retrieved by a surviving node depends on its load weight which is determined by both network bandwidth and I/O capacity. More blocks are fetched from faster nodes, and vice versa. The three recovery schemes are implemented on a 9-node heterogeneous RS-coded storage cluster, where a set of comparative experiments are conducted. The experimental results show that our Lars scheme outperforms the other two schemes by a factor of up to 1.58.

There exist numerous erasure codes for RAID-6, of which MDS codes are popular due to the optimal storage efficiency. Although vertical MDS codes have better load balancing compared to horizontal MDS codes, unbalancing problem still exists in some vertical codes, e.g., P-Code. To address this issue, we propose a novel efficient RAID-6 code to support highly balanced I/Os among disk arrays - Balanced P-Code. In Balanced P-Code, We move the unevenly distributed information symbols in each parity chain of P-Code along their columns to other rows, thus enabling the parity chain to keep original parity calculation relationships and tolerate double disk failures. The Balanced P-Code can not only achieve optimal storage efficiency, computational complexity and update complexity, but also support better I/O balancing in the context of large scale storage systems. Apart from extensive theoretical analysis, empirical evaluation are conducted by running a wide range of workloads under various configurations. Experimental results show that Balanced P-Code has better load balancing ratio. Especially, in both random mixed single read/write and random mixed continuous read/write cases, Balanced P-Code outperforms P-Code in terms of load balancing ratio by a factor of up to 2.64 and 2.3, respectively.

In today's large data centers, hundreds to thousands of nodes are deployed as storage clusters to provide cloud and big data storage service, where failures are not rare. Therefore, efficient data redundancy technologies are needed to ensure data availability and reliability. Compared to traditional technology based on replication, erasure codes which tolerate multiple failures provide availability and reliability at a much lower cost. However, those erasure-coded, particularly XOR-coded storage clusters, suffer from performance problem caused by degraded reads under concurrent node failures. With the traditional centralized decoding method, a large amount of extra data has to be transmitted over the network to service degraded reads. In particular, the degraded reads in XOR-coded stripes with concurrent failures result in notably high network traffic. To address this problem, we propose a novel decoding approach called Local Decoding First or LDF for short. Via exploiting decoding computational locality of XOR-coded storage clusters, LDF significantly reduces the required network traffic and hence reduces the access latency of degraded reads, thus improving I/O throughput. A prototype of LDF with two typical XOR codes has been implemented in the popular distributed file system HDFS on a storage cluster composed of 40 nodes. The experimental results show that LDF dramatically reduces the network traffic under concurrent node failures and thus improves both the I/O throughput and access latency.

I/O performance has been critical for large-scale distributed systems. Many approaches, including hint-based multilevel cache, have been proposed to smooth the gap between different levels. These solutions demote or promote cache blocks based on the latest history information, which is insufficient for applications where frequent demote and promote operations occur. In this paper, we propose a novel multilevel buffer cache using K-step hints (Hint-K) to improve the I/O performance of distributed systems. The basic idea is to promote a block from the lower level cache to the higher level(s) or demote a block vice versa based on the block's previous K-step promote or demote operations, which are referred to as K-step hints. If we make an analogy between Hint-K and LRU-K, then LRU-K keeps track of the times of last K references for blocks within a single cache level, while our Hint-K keeps track of the information of the last K movements (either demote or promote) of blocks among different cache levels. We develop our Hint-K algorithms and design a mathematical model that can efficiently describe the activeness of any block in any cache level. Simulation results show that Hint-K achieves better performance compared to the existing popular multilevel cache schemes such as PROMOTE, DEMOTE, and MQ under different I/O workloads.

RAID-6 is widely used to tolerate concurrent failures of any two disks in both disk arrays and storage clusters. Numerous erasure codes have been developed to implement RAID-6, of which MDS Codes are popular. Due to the limitation of parity generating schemes used in MDS codes, RAID-6-based storage systems suffer from low reconstruction performance. To address this issue, we propose a new class of XOR-based RAID-6 code (i.e., V2-Code), which delivers better reconstruction performance than the MDS RAID-6 code at low storage efficiency cost. V2-Code, a very simple yet flexible Non-MDS vertical code, can be easily implemented in storage systems. V2-Code's unique features include (1) lowest density, (2) steady length of parity chain, and (3) well balanced computation. We perform theoretical analysis and evaluation of the coding scheme under various configurations. The results show that V2-Code is a well-established RAID-6 code that outperforms both X-Code and Code-M in terms of reconstruction time. V2-Code can speed up the reconstruction time of X-Code by a factor of up to 3.31 and 1.79 under single disk failure and double disk failures, respectively.

The power consumption of a server is not linear to its activeness, i.e., a server with 10% load may still draw as much as 60% of its peak power, therefore, a significant amount of energy has been used to keep servers active even under very light or idle loads. The resulting effect has been increased low power-effectiveness in data centers which elevate ownership costs and put more pressure on rack and enclosure densities. This motivates us to design a scheme to dynamically dispatch load to achieve energy efficiency while maintaining the quality of service (QoS) by exploiting a fundamental characteristic of data centers: heterogeneity. In this work, we propose D-PALD to guarantee response time percentile while dynamically dispatch the workload among the servers to maximize the power efficiency in heterogeneous data centers. We develop a power efficiency model to characterize properties of servers while providing the percentile guarantee and also design a power aware load dispatching algorithm. Our experiments demonstrate that DPALD can save a significant amount of power without sacrificing user performance compared to the baseline power management algorithms.

The buffer cache plays an essential role in smoothing the gap between the upper level computational components and the lower level storage devices. A good buffer cache management scheme should be beneficial to not only the computational components, but also the storage components by reducing disk I/Os. Existing cache replacement algorithms are well optimized for disks in normal mode, but inefficient under faulty scenarios, such as a parity-based disk array with faulty disk(s). To address this issue, we propose a novel penalty-aware buffer cache replacement strategy, named Victim Disk(s) First (VDF) cache, to improve the reliability and performance of a storage system consisting of a buffer cache and disk arrays. VDF cache gives higher priority to cache the blocks on the faulty disks when the disk array fails, thus reducing the I/Os addressed directly to the faulty disks. To verify the effectiveness of the VDF cache, we have integrated VDF into the popular cache algorithms least frequently used (LFU) and least recently used (LRU), named VDF-LFU and VDF-LRU, respectively. We have conducted intensive simulations as well as a prototype implementation for disk arrays to tolerate one disk failure (RAID-5) and two disk failures (RAID-6). The simulation results have shown that VDF-LFU can reduce disk I/Os to surviving disks by up to 42.3 percent in RAID-5 and 50.7 percent in RAID-6, and VDF-LRU can reduce those by up to 36.2 percent in RAID-5 and 48.9 percent in RAID-6. Our measurement results also show that VDF-LFU can speed up the online recovery by up to 46.3 percent in RAID-5 and 47.2 percent in RAID-6 under spare-rebuilding mode, or improve the maximum system service rate by up to 47.7 percent in RAID-5 under degraded mode without a reconstruction workload. Similarly, VDF-LRU can speed up the online recovery by up to 34.6 percent in RAID-5 and 38.2 percent in RAID-6, or improve the system service rate by up to 28.4 percent in RAID-5.

Sequential prefetching schemes are widely employed in storage servers to mask disk latency and improve system throughput. However, existing schemes cannot benefit parallel disk systems as expected due to the fact that they ignore the distinct internal characteristics of the parallel disk system, in particular, data striping. Moreover, their aggressive prefetching pattern suffers from premature evictions and prolonged request latencies. In this paper, we propose a strip-oriented asynchronous prefetching (SoAP) technique, which is dedicated to the parallel disk system. It settles the above-mentioned problems by providing multiple novel features, e.g., enhanced prediction accuracy, adaptive prefetching strength, physical data layout awareness, and timely prefetching. To validate SoAP, we implement a prototype by modifying the software redundant arrays of inexpensive disks (RAID) under Linux. Experimental results demonstrate that SoAP can consistently offer improved average response time and throughput to the parallel disk system under non-random workloads compared with STEP, SP, ASP, and Linux-like SEQPs.

Continuous Data Protection (CDP) has become increasingly important as digitization continues. This paper presents a new architecture and an implementation of CDP in Linux kernel. The new architecture takes advantages of both traditional snapshot technology and recent Timely Recovery to Any Point-in-time (TRAP) architecture [CHECK END OF SENTENCE]. The idea is to periodically insert snapshots within the parity logs of changed data blocks in order to ensure fast and reliable data recovery in case of failures. A mathematical model is developed as a guide to designers to determine when and how to insert snapshots to optimize performance in terms of space usage and recovery time. Based on the mathematical model, we have designed and implemented a CDP module in the Linux system. Our implementation is at block level as a device driver that is capable of recovering data to any point-in-time in case of various failures. Extensive experiments have been carried out to show that the implementation is fairly robust and numerical results demonstrate that the implementation is efficient.

With higher reliability requirements in clusters and data centers, RAID-6 has gained popularity due to its capability to tolerate concurrent failures of any two disks, which has been shown to be of increasing importance in large scale storage systems. Among various implementations of erasure codes in RAID-6, a typical set of codes known as Maximum Distance Separable (MDS) codes aim to offer data protection against disk failures with optimal storage efficiency. However, because of the limitation of horizontal parity or diagonal/anti-diagonal parities used in MDS codes, storage systems based on RAID-6 suffers from unbalanced I/O and thus low performance and reliability. To address this issue, in this paper, we propose a new parity called Horizontal-Diagonal Parity (HDP), which takes advantages of both horizontal and diagonal/anti-diagonal parities. The corresponding MDS code, called HDP code, distributes parity elements uniformly in each disk to balance the I/O workloads. HDP also achieves high reliability via speeding up the recovery under single or double disk failure. Our analysis shows that HDP provides better balanced I/O and higher reliability compared to other popular MDS codes.

RAID-6 is widely used to tolerate concurrent failures of any two disks to provide a higher level of reliability with the support of erasure codes. Among many implementations, one class of codes called Maximum Distance Separable (MDS) codes aims to offer data protection against disk failures with optimal storage efficiency. Typical MDS codes contain horizontal and vertical codes. Due to the horizontal parity, in the case of partial stripe write (refers to I/O operations that write new data or update data to a subset of disks in an array) in a row, horizontal codes may get less I/O operations in most cases, but suffer from unbalanced I/O distribution. They also have limitation on high single write complexity. Vertical codes improve single write complexity compared to horizontal codes, while they still suffer from poor performance in partial stripe writes. In this paper, we propose a new XOR-based MDS array code, named Hybrid Code (H-Code), which optimizes partial stripe writes for RAID-6 by taking advantages of both horizontal and vertical codes. H-Code is a solution for an array of (p+1) disks, where p is a prime number. Unlike other codes taking a dedicated anti-diagonal parity strip, H-Code uses a special anti-diagonal parity layout and distributes the anti-diagonal parity elements among disks in the array, which achieves a more balanced I/O distribution. On the other hand, the horizontal parity of H-Code ensures a partial stripe write to continuous data elements in a row share the same row parity chain, which can achieve optimal partial stripe write performance. Not only within a row but also within a stripe, H-Code offers optimal partial stripe write complexity to two continuous data elements and optimal partial stripe write performance among all MDS codes to the best of our knowledge. Specifically, compared to RDP and EVENODD codes, H-Code reduces I/O cost by up to 15.54% and 22.17%. Overall, H-code has optimal storage efficiency, optimal encoding/decoding computational complexity, optimal complexity of both single write and partial stripe write.

As the technique developing, some important problems in storage systems have been solved appropriately. A good example is the development of RAID-6 code techinque, the appear of it has greatly improved the reliability, availability of modern storage systems. Some best known vertical RAID-6 code like P-code and X-code has acquire optimal or near optimal performance in encoding, decoding and update. But they do not detailedly analysis the status of reconstruction with single-disk failure. In the status, there are many paths to perform reconstructing. But the path you choice will greatly affect the performance of whole storage system. Based the phenomenon found above, we present a fast and effcient scheme, Path Directed Recovery Scheme (PDRS for short), to find a optimal path to reconstruct single-disk failure in P-code and X-code. Using PDRS, we will acquire some benefits: (1) it can decrease the disk I/O complexity caused by reconstruction and therefore accelerating the speed of reconstruction, (2) it can balance the load on each disk, consequently can avoid the hot problem in a degree. We perform theoretical analysis and evaluation of the PDRS when applied in P-code with (p-1)-disk and X-code with p-disk. Our theoretical analysis shows that PDRS applied in P-code with (p-1)-disk can acquire up to 25% performance improvement. To verify the effectiveness of PDRS, we have conducted intenvice simulation. The simulation results shows that PDRS applied in P-code with (p-1)-disk can speedup the recovery duration by up to 23.6% under spare-rebuilding mode. Overall, PDRS is a efficient and useful recovery scheme that can applied to all of the vertical RAID-6 code.

The improvement for energy efficiency has been increasingly becoming a major consideration in server and data center design, especially for the power-hungry ones. Numerous studies have provided various new methods or proposals for the building of "green" server and data center, but this paper concentrates on how different configuration schemes in a server effect practical performance and power consumption for specific applications. It is completely necessary to obtain thin provisioning for the particular applications to meet performance requirements with minimal energy consumption. This paper evaluates the different hardware configurations' impact on energy consumption and performance for typical applications, hoping for offering evidences or clues to subsequent researches. The File Bench is used to generate four sever workloads and ZH-101 is employed to collect relevant real-time power consumptions. Our result shows that different workloads need different hardware configurations at the demands of both energy-efficiency and performance. And running multiple workloads on a reduced hardware configuration is a wise choice.

In this article, we propose a simple but powerful online availability upgrade mechanism, S upplementary P arity A ugmentations( SPA ), to address the availability issue in parity-based RAID systems. The basic idea of SPA is to store and update the supplementary parity units on one or a few newly augmented spare disks for online RAID systems in the operational mode, thus achieving the goals of improving the reconstruction performance while tolerating multiple disk failures and latent sector errors simultaneously. By applying the exclusive OR operations appropriately among supplementary parity, full parity, and data units, SPA can reconstruct the data on the failed disks with a fraction of the original overhead that is proportional to the supplementary parity coverage, thus significantly reducing the overhead of data regeneration and decreasing recovery time in parity-based RAID systems. Our extensive trace-driven simulation study shows that SPA can significantly improve the reconstruction performance of the RAID5 and RAID5+0 systems, at an acceptable performance overhead imposed in the operational mode. Moreover, our reliability analytical modeling and sequential Monte-Carlo simulation demonstrate that SPA is consistently more than double the MTTDL of the RAID5 system and improves the reliability of the RAID5+0 system noticeably.

In this paper, we present a novel coding scheme that can tolerate up to two-disk failures, satisfying the RAID-6 property. Our coding scheme, Code-M, is a non-MDS (Maximum Distance Separable, tolerating maximum failures with a given amount of redundancy) code that is optimized by trading rate for fast recovery times. Code-M is lowest density and its parity chain length is fixed at 2C − 1 for a given number of columns in a strip-set C. The rate of Code-M, or percentage of disk space occupied by non-parity data, is (C − 1)/C. We perform theoretical analysis and evaluation of the coding scheme under different configurations. Our theoretical analysis shows that Code-M has favorable reconstruction times compared to RDP, another well-established RAID-6 code. The quantitative comparisons of Code-M against RDP demonstrate recovery performance improvement by a factor of up to 5.18 under single disk failure and 2.8 under double failures using the same number of disks. Overall, Code-M is a RAID-6 type code supporting fast recovery with reduced I/O complexity.

I/O performance has been critical for large scale distributed systems. Many approaches, including hint-based multi-level cache, have been proposed to smooth the gap between different levels. These solutions demote or promote cache blocks based on the latest history information, which is insufficient for applications where frequent demote and promote operations occur. In this paper we propose a novel multi-level buffer cache using K-step hints (Hint-K) to improve the I/O performance of distributed systems. The basic idea is to promote a block from the lower level cache to the higher level or demote a block vice versa based on the block’s previous K-step promote or demote operations, which are referred to as K-step hints. If we make an analogy between Hint-K and LRU-K, LRU-K keeps track of the times of last K references for blocks within a single cache level, while our Hint-K keeps track of the information of the last K movements (either demote or promote) of blocks among different cache levels. We develop our Hint-K algorithm and design a mathematical model that can efficiently describe the activeness of any blocks in any cache level. Simulation results show that Hint-K achieves better performance compared to current popular multi-level cache schemes such as PROMOTE, DEMOTE, and MQ under different representative I/O workloads.

Considering a large part of node failures in a storage clusters cannot actually destroy data in disks and even some failed nodes can soon recover, a policy that deferring a reconstruction until recover during a certain time after a node failure can lessen unnecessary data rebuilding process is absolutely possible and favorable, but it also undoubtedly introduces a certain risk of data loss.

Redundant Arrays of Independent Disks RAID is a popular storage architecture with high performance and reliability. RAID-6 with a higher level of reliability based on MDS (Maximum Distance Separable) code is well studied, for its optimal storage efficiency. RAID-6 could offer continuous services in degraded mode, during the period of online failure recovery. However, the online recovery would bring a considerable I/O workflow to the storage system, that almost all the surviving data in the system need to be accessed. Due to the limitation of disk bandwidth, user response time would be significantly affected by the recovery workflow. In this paper, we examine the online recovery performance of two typical MDS RAID-6 codes RDP code and P-code. To our observation, P-code significiantly outperforms RDP in user response time and recovery duration during a single disk failure recovery. To our analysis, the difference comes from not only the parity layout but also the parity organization. Therefore, we propose a new categorization for existing MDS RAID-6 codes, based on the methodology of parity organization. By our approach, all the MDS RAID-6 codes could be categorized to Sym-codes with only one type of parity, and Asym-codes with at least two different types of parity.

Offering better performance for random access compared to conventional hard disks and providing larger capacity and lower cost than DRAM, NAND flash based SSDsare integrated in server storage hierarchy as a second tier of disk cache between DRAM and disks for caching more data from disks to meet the increasingly intensive I/O demands. Unfortunately, available hybrid storage architectures cannot fully exploit SSDs' potentials due to absorbing too much workload of disk tier, which results in excessive wear and performance degradation associated with internel garbage collection. In this paper, we propose RAF (Random Access First), an hybrid storage architecture that combines both of an SSD based disk cache and a disk drive subsystem. RAF focuses on extending the lifetime of SSD while improving system performance through providing priority to caching random-access data. In detail, RAF splits flash cache into read and write cache to service read/write requests respectively. Read cache only holds random-access data that are evicted from file cache to reduce flash wear and write hits. Write cache performs as a circular write-through log so as to improve system response time and simplify garbage collection. Similar to read cache, write cache only caches random-access data and flushes them to hard disks immediately. Note that, sequential access are serviced by hard disks directly to even the full workload between SSD and disk storage. RAF is implemented in Linux kernel 2.6.30.10. The results of experiments show that RAF can significantly reduce flash wear and improve performance compared with the state-of-art FlashCache architecture.

With the rapid development of vehicular sensor networks (VSNs) technology, the potential use of networked real-time control and automation is enormous and appealing. However, closed-loop control VSNs via the Internet are very difficult to implement practically because of their stochastic nature. One of the biggest challenges in VSNs is how to deal with sensor networks time delay and data loss. The authors investigate the potential of using the predictive control scheme for VSNs based on round-trip time (RTT) delay prediction to overcome the VSNs transmission delay and data loss. The predicted RTT delay is taken as the sampling interval reference for variable-period sampling approach. Modelling the time delay of networked control systems as a non-linear time series, the least mean square (LMS) filter algorithm is adopted to predict online the time delay induced in VSNs. The simulation results show that the LMS algorithm can achieve ideal efficacy if time delay has no variety abnormally. The predictive compensation strategy is proposed to reduce the detrimental effect of stochastic time delays induced by communication networks on control performance. The results of offline simulations via the Internet illustrate that the predictive control scheme based on RTT delay prediction has the potential to overcome the VSNs time delay and data loss.

Storage performance is critical in today's distributed stream-processing systems. One approach to improve the performance is to use hotspot attribute in object-based storage systems. This paper discusses hotspot classification and identification, and then presents an object hotspot prediction model (OHPM) to dynamically predict hotspots. Based on this model, we discuss an efficient hotspot caching strategy to improve the performance. To demonstrate the effectiveness of our proposed approach, we have developed a prototype of hotspot attribute-managed storage system (HASS) by extending object-based storage device (OSD) file system and iSCSI protocols. Experimental results show that the HASS improves the throughput by up to 62% and reduces the disk I/O by as much as 25% in our VoD tests by integrating our object hotspot prediction and cache approaches.

Cache plays an essential role in modern computer systems to smooth the performance gap between memory and CPU. Most existing cache replacement algorithms use three stacks: recency stack, frequency stack and history stack. The balance and design of those stacks is a key to achieve high hit ratio, thus improving the buffer cache efficiency. In this paper we propose a new cache replacement algorithm, adaptive dual LRU, or AD-LRU for short, to efficiently utilize the buffer cache pages. Instead of using one LRU stack, we use two LRU stacks: one LRU stack LR to catch the accesses of pages with low recency, and the other LRU stack HR to catch the accesses of pages with high recency. The idea is to adaptively adjust the sizes of the history stack, recency and frequency stacks, an overall buffer cache efficiency in terms of hit ratio will be improved. Simulations results show that AD-LRU demonstrates higher hit ratio compared to existing popular algorithms such as LRU, ARC, and LIRS.

Geographic Information System Grid integrates geographic information systems and Grid technology for data gathering, accessing, transmitting and service, in different I/O patterns, built upon massive storage systems. Existing non-standardized multi-source and multi-scale data lack spatial information sharing either internally or externally between organizations or departments, especially in national or global applications. HUSt is a massive storage system that was built at Wuhan National Laboratory for Optoelectronics, in China. There are heterogeneous storage areas in the system, including Object-based Storage System for the main data storing especially for the data searched frequently, Virtual Interface based Storage System for the data required at high transfer speed, and InfiniBand based SAN for high performance. HUSt is primarily meant for research on the organization and key technologies of storage systems for the next generation Internet. The goal is to unify network storage and construct a peta-byte storage system, which supports GIS Grid and applications.