Scaling inference for large language models is increasingly constrained by limited GPU memory, primarily due to the expanding intermediate states (KV caches) required for long-context generation and multi-user workloads. Once the KV cache exceeds the capacity of high-bandwidth memory, it must be offloaded to host memory and reloaded on demand, a workflow severely bottlenecked by the CPU–GPU interconnect, typically PCIe. Existing approaches exploiting offload KV caches to CPU memory and selectively reload partial segments for attention computation often underutilize CPU compute resources and suffer from accuracy degradation. We present Beyond, a drop-in runtime that integrates a smart offloading scheme to selectively identify and retain salient KV entries across continuous decoding sessions, together with a hybrid CPU–GPU attention mechanism for scalable inference. Beyond executes dense attention over recent KV entries stored in GPU memory while performing parallel, per-head sparse attention on salient contextual KV entries residing in CPU memory. The outputs are fused efficiently through a log-sum-exp scheme. During the bandwidth-constrained decoding phase, oversized KV caches are processed cooperatively by the aggregated CPU and GPU memory bandwidth, with only minimal PCIe data movement. Experiments across diverse models and workloads demonstrate that Beyond improves scalability, supports longer sequences and larger batch sizes, and outperforms existing sparse attention baselines in both efficiency and accuracy—all on commodity GPU hardware.

Identifying drug–target interactions (DTIs) is critical for discovery and repurposing. Existing deep models often ignore frequency-domain structure and rely on global pooling that dilutes binding-critical signals. We present TriPeakDTI, which couples adaptive frequency-domain analysis with a peak-guided attention mechanism. Using the discrete cosine transform (DCT), TriPeakDTI learns per-modality spectral weights for drugs and targets to capture multi-scale patterns—low frequencies for global conformations and high frequencies for local flexibility—during single-modal extraction. A bidirectional, peak-guided fusion module preserves token-level interaction evidence via peak detection, cross-modal alignment, and strength-aware aggregation, preventing information washout. Across three benchmark datasets, TriPeakDTI outperforms seven state-of-theart methods.

Accurate prediction of phage-host interactions remains a fundamental challenge that impedes the clinical deployment of phage therapy. Current graph neural network-based methods rely on superficial sequence features, failing to adequately integrate deep biological semantic information. In this work, we present DSHMGAT (Dual-Stream Hierarchical Mixed-Routing Graph Attention Network), a novel framework that incorporates agent-generated semantic embeddings to mitigate this semantic deficiency. By employing a ReAct-driven agent with function calling capabilities to access domain-specific databases, our approach reduces hallucinations inherent in biological LLM applications. DSHMGAT adopts a dualstream hierarchical graph neural network that simultaneously captures genomic sequences and biological semantic representations, enabling effective cross-modal information integration. Inspired by mixture-of-experts architectures, we develop a mixed-routing attention mechanism that improves learning flexibility through dynamic weight allocation between routing heads and shared heads. DSHMGAT achieves an AUC of 0.9486 on the benchmark dataset which outperforms established approaches in our comparative analysis. Ablation experiments reveal that the observed improvements can be attributed to the combined effects of multimodal fusion, cross-modal interaction and mixed-routing mechanism.

Traditional Database (DB) systems use a DB buffer, a page-based cache management system, to load data and indexes from block storage devices into byte-addressable main memory. However, this approach is inefficient in terms of space and I/O when key-value pair sizes are significantly smaller than the page size. Inserting a single key-value pair results in reading and writing an entire page, consuming a full page's worth of memory in the buffer. Moreover, the entire page is immediately loaded even when just a single key-value pair is inserted into the page. Also, an infrequently accessed page is likely to be evicted to disk before any subsequent accesses occur. We present TurboIndex, a hybrid cache management scheme that combines a record-based cache with the traditional pagebased cache to address these inefficiencies. TurboIndex first accumulates key-value pairs from cold pages in the record-based cache. It then identifies hot pages, those that are likely to benefit from page-based caching, and migrates them collectively from the record-based cache to the page-based cache. This strategy increases effective cache capacity without significantly increasing memory usage, while also improving performance by reducing disk I/O. TurboIndex achieves up to a$4.5 \times$improvement in pure write workloads and at least a$1.8 \times$gain on the write-heavy YCSBA benchmark.

Learned indexes have received significant attention for their potential to dramatically outperform traditional treebased indexes in both speed and space efficiency. Their core strength lies in using predictive models to estimate the position of a key within a sorted array. To handle complex key distributions and support frequent insertions in dynamic workloads, learned indexes typically organize multiple models hierarchically in a tree structure. These indexes perform best when a model can accurately predict a key's location. However, existing learned indexes often require traversing several models to reach the one responsible for a target key. Moreover, if the prediction is imprecise, an additional local search (the last-mile search) is needed. These overheads before and after model execution can significantly degrade performance, sometimes approaching that of conventional indexes like B+-trees. In this paper, we propose LASER, a new learned index design that tackles these inefficiencies by leveraging two common patterns in real-world workloads. First, LASER exploits key access locality, where some key ranges are more likely to be accessed. Second, it detects linear key distributions, enabling precise prediction without last-mile search. LASER adaptively promotes models covering long key ranges to the top of the model tree, reducing the number of model traversals. For key ranges with perfectly linear distributions, it employs models that guarantee a direct hit (on the exact key position), eliminating the need for further search. We implemented LASER and conducted extensive evaluations. The results show that LASER outperforms state-of-the-art learned indexes such as LIPP and ALEX, as well as traditional indexes, like ART, by up to 1.6 to 5.5 times.

Large Language Models (LLMs) for multi-turn conversations suffer from inefficiency: semantically similar queries across different user sessions trigger redundant computation and duplicate memory-intensive Key-Value (KV) caches. Existing optimizations such as prefix caching overlook semantic similarities, while typical semantic caches either ignore conversational context or are not integrated with low-level KV cache management. We propose SmartCache, a system-algorithm co-design framework that tackles this inefficiency by exploiting semantic query similarity across sessions. SmartCache leverages a Semantic Forest structure to hierarchically index conversational turns, enabling efficient retrieval and reuse of responses only when both the semantic query and conversational context match. To maintain accuracy during topic shifts, it leverages internal LLM attention scores—computed during standard prefill—to dynamically detect context changes with minimal computational overhead. Importantly, this semantic understanding is co-designed alongside the memory system: a novel two-level mapping enables transparent cross-session KV cache sharing for semantically equivalent states, complemented by a semantics-aware eviction policy that significantly improves memory utilization. This holistic approach significantly reduces redundant computations and optimizes GPU memory utilization. The evaluation demonstrates SmartCache's effectiveness across multiple benchmarks. On the CoQA and SQuAD datasets, SmartCache reduces KV cache memory usage by up to $59.1\%$ compared to prefix caching and $56.0\%$ over semantic caching, while cutting Time-to-First-Token (TTFT) by $78.0\%$ and $71.7\%$, respectively. It improves answer quality metrics, achieving $39.9\%$ higher F1 and $39.1\%$ higher ROUGE-L for Qwen-2.5-1.5B on CoQA. The Semantic-aware Tiered Eviction Policy (STEP) outperforms LRU/LFU by $29.9\%$ in reuse distance under skewed workloads.

LSM-tree-based key-value stores or KV stores are widely deployed in modern cloud storage systems thanks to high data storage efficiency and retrieval capabilities. The compaction process in the LSM-tree, however, results in severe performance bottlenecks, especially in scenarios involving large volumes of data. While key-value separation methods mitigate the performance bottlenecks caused by compaction, the existing methods do not fully address merge-sorting during compaction and expensive garbage collection (GC). We propose gParaKV, a GPGPU-empowered KV store with a KV separation mechanism, leveraging the GPGPU parallel technology to accelerate merge-sorting in compaction and GC. gParaKV embraces unique features like a GPGPU bitmap structure, parallel data marking, and a parallel GC mechanism. These critical components effectively curtail the overhead of merge-sorting and GC operations by virtue of parallel computing. We compare it with state-of-the-art KV stores (e.g., RocksDB, BlobDB, Wisckey, DiffKV, UniKV, and HPDK) under various workloads. The experimental results show that gParaKV can improve the write performance and GC efficiency compared to the existing key-value separation-based KV stores.

Log Structured Merge Tree (LSM-Tree) is the core data structure that powers many modern key-value storage engines for its high write throughput property. To enable high speed writes, LSM-Tree ingests updates in an out-of-place manner and organizes key-value items into multiple levels of exponentially increasing capacities. To service fast data access, LSM-Tree frequently performs compaction operation, where data between two consecutive levels is sort-merged and written down to the lower level in granularity of SSTable. This compaction operation is known to cause high write amplification, which is the main threat to the LSM-tree's design objective of achieving high write performance.

The NVMe Key Value (NVMe-KV) Command Set has been standardized to enable access to an NVMe device with a key rather than a block address and make an NVMe device a KV service provider. This new interface opens an exciting opportunity of offloading extensive data management chores to an external KV device and streamlining the KV-based data processing at the host. However, the interface itself may become a major performance bottleneck with small KV access and make the technology hard to be deployed in diverse application scenarios. In this paper we proposed a software-based facility, named SAKER, at the host side to remove or alleviate the performance bottleneck at the interface. SAKER, which was prototyped in an NVMe-KV SSD emulator, demonstrates that it can effectively keep the NVMe-KV interface from becoming the performance bottleneck even with small KV requests in most workloads.

Key-value stores (KV stores) anchored on log-structured merge trees (LSM-tree) provide much improved performance under write-intensive workloads but exhibit significant write amplification (WA). The tiering compaction strategy is widely adopted in KV stores to reduce the WA. However, there are three imminent issues in tiering-based KV stores. First, excessive levels in the LSM-tree structure result in high read and write amplification. Second, without key partitioning support, these KV stores increase write tail latency. Relying solely on a hash-based key partitioning scheme is insufficient, as it does not support range queries. Furthermore, a KV store with only a key range-based partitioning scheme overlooks the distribution of keys within the key space. Third, existing KV stores with level optimization can incur high costs. A common approach to reducing the number of LSM-tree levels is to increase the MemTable size. While this reduces the number of levels, it requires more memory, leading to higher costs. Therefore, it is crucial to balance the tradeoff between level optimization and monetary expenses. To address these issues, we propose a tiering-based key-value store, leveraging high-performance hierarchical data management. The key space of our proposed KV store is partitioned into m ultiple partitions based on key ranges, with an LSM- tree in each partition. We refer to this KV store as MTree in this article. MTree reduces the number of levels in the LSM-Tree structure close to one without increasing the monetary cost. In MTree, a hierarchical structure that combines the log and LSM-tree curtails the number of levels in the LSM-tree by accumulating the data in the log without increasing the cost. With the hierarchical structure in place, we devise a long- and short-term key density distribution-aware partitioning scheme for the key range. This scheme dynamically adjusts the size of partitioning, balancing data in the partition and storing most data in large-sized logs. Then, MTree reduces the number of levels in the LSM-tree, thereby optimizing the read/write amplification. The experimental results show that MTree limits the WA to as low as two. MTree enhances the random write throughput of the state-of-the-art KV stores by up to 6.9×.

Microbial-disease association prediction has always been a frontier research direction in bioinformatics, which includes two tasks: predicting association relationships and association categories (Decrease, Increase). At present, The study methods based on statistical analysis rely heavily on biological prior knowledge, the traditional microbial experiments are time-consuming and costly. In this paper, we propose a novel model that predict microbe-disease association based on an enhanced relational graph convolutional network. Firstly, we construct a heterogeneous network containing microbial abundance changes and disease associations, microbial similarity, and disease similarity. Then, this paper proposes a feature difference enhancement module based on graph similarity, which aims to enhance the difference of feature representation between different association categories. It is fused with the relational graph convolutional network to form an enhanced relational graph convolutional network and complete feature coding work. Thus, the multi-category feature representation between nodes can be effectively extracted and the influence of edges on the graph structure can be considered. Finally, a neural network was used to complement nonlinear feature representation. The experimental results show that the proposed model can efficiently predict the association categories between microbial abundance changes and diseases.

Indexes in a database system can consume a large amount of memory. When they grow too large to be entirely held in the memory, selected portions of the indexes have to be unloaded to the secondary storage. There are a number of challenges in the design of an extensible index spanning memory and disk. First, the designs of in-memory portion and on-disk portion of the index must be decoupled so that the best choice for each device can be independently made. Second, selective unloading of in-memory portion to the disk must be carefully designed to maximize chance of memory access and to produce the most disk-friendly I/O access. Third, the strategy for index reloading from the disk and retaining in the memory must be optimized for the highest memory efficiency. In this paper, we proposed a memory-disk-spanning index design, named IndeXY, to effectively address the challenges. IndeXY distinguishes itself by being a framework that allows separate adoption of an in-memory index design and an on-disk data organization and access scheme that are deemed most efficient to its workloads. Instead of being just another one-size-fit-all index across memory and disk, the framework provides well-designed mechanisms and policies to integrate a selected in-memory index (Index X) and an on-disk index (Index Y) into one extensible index (IndeXY). We have implemented IndeXY with alternative in-memory indexes (ART tree or B+ tree) and alternative disk indexes (LSM tree or B+ tree). As an anecdotal example, experiments show that integrating the ART tree and an LSM tree in the framework can lead to a throughput improvement by as high as an 8.6X on a TPC-C workload over LeanStore that uses B+-tree indexes in the memory and disk, and can improve performance for almost all YCSB workloads.

When trained Large Language Models (LLMs) become available, it is desirable to carry out LLM inferences at the user end with limited resources. A common belief on LLM inference is that GPU is essentially the only meaningful processor as almost all computation is tensor multiplication that GPU excels in. However, this belief and its practice are challenged by the fact that GPU has insufficient memory and runs at a much slower speed due to constantly waiting for data to be loaded from the CPU memory via a slow PCIe bus. This makes the CPU a processor with meaningful computing power that can be leveraged to accelerate the inference.

The availability of diverse applications (apps) and the need to use many apps simultaneously have propelled users to constantly switch between apps in smartphones. For an instantaneous switch, these apps are often expected to stay in the memory. However, when a user opens more apps and memory pressure increases, Android kills background apps to relieve the memory pressure. When the user switches a killed app back to the foreground, the user experiences a laggy response that compromises his experience. To delay this killing under memory pressure for a smoother user experience, we proposeMemSaver, a low-cost approach for preemptively swapping selected pages of the background apps out of memory to avoid or postpone the killing of apps while ensuring their near-ideal switch time. MemSaver uses pages accessed during events similar to the switch and about the same app context for predicting the pages to be accessed in the next switch. Evaluations on OnePlus 9 Pro using representative apps show that up to 60% of app's memory (RSS) can be saved while maintaining the switch time within the acceptable range.

The emergence of persistent memory (PMem) is greatly impacting the design of commonly used data structures to obtain the full benefit from the new technology. Compared to the DRAM, PMem's larger capacity and lower cost make it an attractive alternative for hosting large data structures, such as indexes of in-memory databases, especially for those that require data persistency. However, simply using existing index structures in the PMem can be unexpectedly inefficient for three reasons. (1) Index accesses are composed of small writes and reads. (2) Each small write is required to come with expensive fence and flush operations. And (3) PMems usually prefer large accesses for high performance with their internal block-like access designs despite being byte-addressable. For example, Intel Optane DC PMem has a 256-byte access unit~(XPLine), leading to significant read/write amplification for small accesses. In this work we systematically study a series of techniques, including application-managed write-buffering, read-caching, and out-of-place updates and their synergistic effect on performance of some representative indexes (hash table, B+ tree, and skip list) designed for PMems. We then apply the knowledge obtained from this investigation into the design of a high-performance PMem index, named Spot-on tree (SPTree), that facilitates applications to selectively cache read-intensive components of an index and to buffer written data to index structure, while providing crash consistency and quick recovery upon crash. Compared to the state-of-art indexes, SPTree provides up to 2X and 4X higher write and read throughput, respectively.

Key-value (KV) stores based on log-structured merge tree (LSM-tree) have been extensively studied and deployed in major information technology infrastructures. Because this type of systems is catered for KV store accessing disks, a limited disk bandwidth increases the difficulty of serving online data requests. One solution involves using a large DRAM such that frequent KV pairs are buffered and accessed from the main memory – and this solution exposes a major design drawback of the KV store: its lack of support for integrated data management in memory and on disks. For example, data in the most popular LSM-tree implementation – RocksDB – may reside in a small write buffer (MemTable) that organizes KV pairs for disk writes, a buffer cache for disk blocks, a write-ahead log on the disk for data persistence, and in various LSM levels on the disk. Without the integrated management of indexes, data, and their persistence in a hierarchical memory/disk architecture, memory is under-utilized along with missed performance optimization opportunities. We propose a KV store, TrieKV, which holistically incorporates DRAM, persistent memory (PMem), and disk with certain desired features: (1) fast in-memory access, (2) accurate identification of hot/cold data at an adaptable granularity, (3) customized memory space allocation for minimized fragmentation, (4) hotness-aware data placement across the storage hierarchy, (5) in-place data persistence in the PMem, and (6) hotness-aware LSM-tree compaction. TrieKV employs a single, integrated trie-structured index for all KV pairs in memory, where access hotness can be consistently discovered. Accordingly, the KV placement is dynamically determined according to the hotness and persistence needs of the storage hierarchy spanning the DRAM, PMem, and solid-state drive. In the experiment, we demonstrate that the 99th latency of RocksDB and NoveLSM is 38x and 6x higher than that of TrieKV, respectively. In addition, TrieKV outperforms RocksDB and NoveLSM by a factor of 5.6 and 1.7in terms of throughput, respectively.

Today’s apps on a mobile device, such as a smartphone and a tablet, need to access various resources to deliver quality service to users’ satisfaction. These resources may include cameras, microphones, screens, processors, various specialized sensors, and data. In today’s client-server framework, resources accessible to an app are limited to those available in the device running the app, on the cloud, and likely in a few statically connected devices. However, there can be abundant resources on devices near the app-running one with desirable functionalities that can enable or empower the app’s new features and services, but cannot be easily accessed and leveraged. The NEOP (Neutron Operation Platform) framework is an app development and execution environment that removes the barrier across the devices. Heterogeneous IoT devices make the capabilities in their hardware and service software available after security and privacy authentication. An app is developed as a composition of capabilities distributed across various end devices and the cloud. Its constituent computing tasks can be dynamically created and scheduled. Different device capabilities can be selectively and dynamically recruited into the app for the optimal user experience. In this paper we describe example scenarios that motivate the next-generation app framework, the framework’s architecture, design principles, technical challenges, and details on its design and implementation. We also compare this work with related efforts on distributed mobile computing to highlight the unique contributions made by the NEOP platform.

Major efforts on the design of persistent hash table on a non-volatile byte-addressable memory focus on efficient support of crash consistency with fence/flush primitives as well on non-disruptive table rehashing operations. When a data entry in a hash bucket cannot be updated with one atomic write, out-of-place update, instead of in-place update, is required to avoid data corruption after a failure. This often causes extra fences/flushes. Meanwhile, when open addressing techniques, such as linear probing, are adopted for high load factor, the scope of search for a key can be large. Excessive use of fence/flush and extended key search paths are two major sources of performance degradation with hash tables in persistent memory.

We present a comprehensive and in-depth study of Intel Optane DC persistent memory (DCPMM). Our focus is on exploring the internal design of Optane's on-DIMM read-write buffering and its impacts on application-perceived performance, read and write amplifications, the overhead of different types of persists, and the tradeoffs between persistency models. While our measurements confirm the results of the existing profiling studies, we have new discoveries and offer new insights. Notably, we find that read and write are managed differently in separate on-DIMM read and write buffers. Comparable in size, the two buffers serve distinct purposes. The read buffer offers higher concurrency and effective on-DIMM prefetching, leading to high read bandwidth and superior sequential performance. However, it does not help hide media access latency. In contrast, the write buffer offers limited concurrency but is a critical stage in a pipeline that supports asynchronous write in the DDR-T protocol. Surprisingly, in addition to write coalescing, the write buffer delivers lower than read and consistent write latency regardless of the working set size, the type of write, the access pattern, or the persistency model. Furthermore, we discover that the mismatch between cacheline access granularity and the 3D-Xpoint media access granularity negatively impacts the effectiveness of CPU cache prefetching and leads to wasted persistent memory bandwidth.

The emergence of Intel's Optane DC persistent memory (Optane Pmem) draws much interest in building persistent key-value (KV) stores to take advantage of its high throughput and low latency. A major challenge in the efforts stems from the fact that Optane Pmem is essentially a hybrid storage device with two distinct properties. On one hand, it is a high-speed byte-addressable device similar to DRAM. On the other hand, the write to the Optane media is conducted at the unit of 256 bytes, much like a block storage device. Existing KV store designs for persistent memory do not take into account of the latter property, leading to high write amplification and constraining both write and read throughput. In the meantime, a direct re-use of a KV store design intended for block devices, such as LSM-based ones, would cause much higher read latency due to the former property.

Containers have been widely used in various cloud platforms as they enable agile and elastic application deployment through their process-based virtualization and layered image system. However, different layers of a container image may contain substantial duplicate and unnecessary data, which slows down its deployment due to long image downloading time and increased burden on the image registry. To accelerate the deployment and reduce the size of the registry, we propose a new image format, named Gear image, that consists of two parts: a Gear index describing the structure of the image's file system and a set of files that are required when running an application. The Gear index is represented as a single-layer image compatible with the existing deployment framework. Containers can be launched by pulling a Gear index and on demand retrieving files pointed to by the index. Furthermore, the Gear image enables a file-level sharing mechanism, which helps remove duplicate data in the registry and avoid repeated downloading of identical files by a client. We implement a prototype of the container framework, named Gear, supporting the new image format. Evaluation shows that Gear saves 54 % storage capacity in the registry, speeds up container startup by up to${5\times}$, and reduces 84 % bandwidth demands.

Key-value (KV) stores have become a major storage infrastructure on which databases, file systems, and other data management systems are built. To support efficient indexing and range search, the key-value items must be sorted. However, this sorting process can be excessively expensive. In the KV systems adopting the popular Log-Structured Merge Tree (LSM) structure or its variants, the write volume can be amplified by tens of times due to its repeated internal merge-sorting operation.In this paper we propose a KV store design that leverages relatively stable key distributions to bound the write amplification by a number as low as 4.15 in practice. The key idea is, instead of incrementally sorting KV items in the LSM's hierarchical structure, it writes KV items right in place in an approximately sorted list, much like a bucket sort algorithm does. The design also makes it possible to keep most internal data reorganization operations off the critical path of read service. The so-called Write-in-place (Wip) scheme has been implemented with its source code publicly available. Experiment results show that WipDB improves write throughput by 3 to 8× (to around 1Mops/s on one Intel PCIe SSD) over state-of-the-art KV stores.

A block replacement algorithm keeps receiving attention on improvement of its hit ratio. Many replacement algorithms have been proposed, among which LIRS stands out with its consistently higher hit ratio across various workloads with low time and space overheads. However, there are still access patterns where LIRS produces sub-optimal hit ratio and has room for further improvement.

I/O deduplication is a key technique for improving storage systems' space and I/O efficiency. Among various deduplication techniques content-defined chunking (CDC) based deduplication is the most desired one for its high deduplication ratio. However, CDC is compute-intensive and time-consuming, and has been recognized as a major performance bottleneck of the CDC-based deduplication system.

In-memory data management systems, such as key-value stores, have become an essential infrastructure in today's big-data processing and cloud computing. They rely on efficient index structures to access data. While unordered indexes, such as hash tables, can perform point search with O(1) time, they cannot be used in many scenarios where range queries must be supported. Many ordered indexes, such as B+ tree and skip list, have a O(log N) lookup cost, where N is number of keys in an index. For an ordered index hosting billions of keys, it may take more than 30 key-comparisons in a lookup, which is an order of magnitude more expensive than that on a hash table. With availability of large memory and fast network in today's data centers, this O(log N) time is taking a heavy toll on applications that rely on ordered indexes.

CPU cache has been used to bridge the processor-memory performance gap to enable high-performance computing. As the cache is of limited capacity, for its maximum efficacy it should (1) avoid caching data that are less likely to be accessed and (2) identify and cache data that would otherwise cost a program multiple memory accesses to reach. Unfortunately, existing cache architectures are inadequate on these two efforts. First, to cost-effectively exploit the spatial locality, they adopt a relatively large and fixed-size cache line as the caching unit. Thus, much of the space in a cache line can be wasted when the data locality is weak. Second, for easy use, the cache is designed to be transparent to programs, which hinders programs from fully exploiting its performance potentials.

Docker containers have been increasingly adopted on various computing platforms to provide a lightweight virtualized execution environment. Compared to virtual machines, this technology can often reduce the launch time from a few minutes to less than 10 seconds, assuming the Docker image has been locally available. However, Docker images are highly customizable, and are mostly built at runtime from a remote base image by running instructions in a script (the Dockerfile). During the instruction execution, a large number of input files may have to be retrieved via the Internet. The image building may be an iterative process as one may need to repeatedly modify the Dockerfile until a desired image composition is received. In the process, every input file required by an instruction has to be remotely retrieved, even if it has been recently downloaded. This can make the process of building of an image and launching of a container unexpectedly slow. To address the issue, we propose a technique, named FastBuild, that maintains a local file cache to minimize the expensive file downloading. By non-intrusively intercepting remote file requests, and supplying files locally, FastBuild enables file caching in a manner transparent to image building. To further accelerate the image building, FastBuild overlaps operations of instructions' execution and writing intermediate image layers to the disk. We have implemented FastBuild. And experiments with images and Dockerfiles obtained from Docker Hub show that the system can improve building speed by up to 10 times, and reduce downloaded data by 72%.

Integrating the data deduplication function into Solid State Drives (SSDs) helps avoid writing duplicate contents to NAND flash chips, which will not only effectively reduce the number of Program/Erase (P/E) operations to extend the device's lifespan but also proportionally enlarge the effective capacity of SSD to improve the performance of its behind-the-scenes maintenance tasks such as wear-leveling (WL) and garbage-collection (GC). However, these benefits of deduplication come at a non-trivial computational cost incurred by the embedded SSD controller to compute cryptographic hashes. To address this overhead problem, some researchers have suggested replacing cryptographic hashes with error correction codes (ECCs) already embedded in the SSD chips to detect the duplicate contents. However, all existing attempts have ignored the impact of the data randomization (scrambler) module that is widely used in modern SSDs, thus making it impractical to directly integrate ECC-based deduplication into commercial SSDs. In this work, we revisit SSD's internal structure and propose the first deduplicatable SSD that can bypass the data scrambler module to enable the low-cost ECC-based data deduplication. Specifically, we propose two design solutions, one on the host side and the other on the device side, to enable ECC-based deduplication. Based on our approach, we can effectively exploit SSD's built-in ECC module to calculate the hash values of stored data for data deduplication. We have evaluated our SES-Dedup approach by replaying data traces in an SSD simulator and found that it can remove up to 30.8% redundant data with up to 17.0% write performance improvement over the baseline SSD.

Data deduplication has been widely used in storage systems to improve storage efficiency and I/O performance. In particular, content-defined variable-size chunking (CDC) is often used in data deduplication systems for its capability to detect and remove duplicate data in modified files. However, the CDC algorithm is very compute-intensive and inherently sequential. Efforts on accelerating it by segmenting a file and running the algorithm independently on each segment in parallel come at a cost of substantial degradation of deduplication ratio.

Superpages have long been used to mitigate address translation overhead in large-memory systems. However, superpages often preclude lightweight page migration, which is crucial for performance and energy efficiency in hybrid memory systems composed of DRAM and non-volatile memory (NVM). In this article, we propose a novel memory management mechanism called Rainbow to bridge this fundamental conflict between superpages and lightweight page migration. Rainbow manages NVM at the superpage granularity, and uses DRAM to cache frequently accessed (hot) small pages within each superpage. Correspondingly, Rainbow utilizes split TLBs to support different page sizes. By introducing an efficient hot page identification mechanism and a novel NVM-to-DRAM address remapping mechanism, Rainbow supports lightweight page migration without splintering superpages. Experiment results show that Rainbow can significantly reduce applications’ TLB misses by 99.9%, and improve application performance (in terms of IPC) by up to 2.9× (45.3% on average) when compared to a state-of-the-art memory migration policy without a superpage support.

I/O deduplication is an important technique for saving I/O bandwidth and storage space for storage systems. However, it requires a new level of address mapping, and consequently needs to maintain corresponding metadata. To meet requirements on data persistency and consistency, the metadata writing is likely to make deduplication operations much fatter, in terms of amount of additional writes on the critical I/O path, than one might expect. In this paper we propose to compress the data and insert metadata into data blocks to reduce metadata writes. Assuming that performance-critical data are usually compressible, we can mostly remove separate writes of metadata out of the critical path of servicing users' requests, and make I/O deduplication much thinner. Accordingly we name the scheme ThinDedup. In addition to metadata insertion, ThinDedup also uses persistency of data fingerprints to evade enforcement of write order between data and metadata. We have implemented ThinDedup in the Linux kernel as a device mapper target to provide block-level deduplication. Experimental results show, compared to existing deduplication schemes, ThinDedup achieves (much) higher (up to 3X) I/O throughput and lower latency (reduced by up to 88%) without compromising data persistency.

In a multi-tenant cloud environment, tenants are usually hosted by virtual machines. Cloud providers deploy multiple virtual machines on a physical server to better utilize physical resources including CPU, memory, and storage devices. SSDs are often used as an I/O cache shared among the tenants for large storage systems using hard disk drives (HDDs) as their main storage devices, which can receive much of SSD's performance benefit and HDD's cost advantage. A key challenge in the use of the shared cache is to ensure strong performance isolation and maintain its high utilization at the same time. However, conventional SSD cache management approaches cannot effectively address this challenge. In this paper, we propose OC-Cache, an open-channel SSD cache framework which utilizes SSD'd internal parallelism to adaptively allocate cache to tenants for both good performance isolation and high SSD utilization. In particular, OC-Cache uses a tenant's miss ratio curve to determine the amount of cache space allocation and where the allocation is (in dedicated or shared SSD channels) and dynamically manages cache space according to the workload characteristics. Experiments show that OC-Cache significantly reduces interference among tenants, and maintains high utilization of the SSD cache.

The Internet-of-Things (IoT) attracts great attention in the past few years. With millions of devices connected to the network, data are generated at an unprecedented speed and the data must be stored efficiently in the database to serve spatial queries. In existing spatial databases that use space-filling curves to organize the data, they store spatial data without considering on-road data distribution. This will introduce unnecessary computation and I/O cost in the service of users' queries about data on the roads. In this paper, we present a Road-Aware Spatial Mapping of data to the storage, or RASM for short, which can be applied in spatial databases for highly efficient storage and query services for moving objects. Usually, a space-filling curve, such as the Hilbert curve, is used to map data in a cell of a geographical area to a segment of linear storage space. However, in a road-network system where data are most distributed and queried along the roads, using a generic square cell as a mapping unit to aggregate data is in conflict with the data use pattern. In RASM, road segment, instead of the cell, is used as the unit of space mapping and data storage so that data requested in a road query can be stored together to enable efficient I/O. Furthermore, a substantial computation may be required to identify mapping units covered in a query in a geometric space. As RASM has grouped data in the road-segment units, one can efficiently found the units covered in a road query, which is usually concerned only about data on a few segments of roads. We implemented a prototype query-serving system using RASM to map data on road segments to a linear space enabled by LevelDB, a widely-used key-value store. Experiment results with real-world traffic data show that with RASM, the road query time can be reduced by up to 43%, and the I/O traffic can be reduced by up to 70%. In the meantime, other queries about geographical regions are well supported in RASM with minimal performance impacts.

With the ever increasing DRAM capacity in commodity computers, applications tend to store large amount of data in main memory for fast access. Accordingly, efficient traversal of index structures to locate requested data becomes crucial to their performance. The index data structures grow so large that only a fraction of them can be cached in the CPU cache. The CPU cache can leverage access locality to keep the most frequently used part of an index in it for fast access. However, the traversal on the index to a target data during a search for a data item can result in significant false temporal and spatial localities, which make CPU cache space substantially underutilized. In this paper we show that even for highly skewed accesses the index traversal incurs excessive cache misses leading to suboptimal data access performance. To address the issue, we introduce Search Lookaside Buffer (SLB) to selectively cache only the search results, instead of the index itself. SLB can be easily integrated with any index data structure to increase utilization of the limited CPU cache resource and improve throughput of search requests on a large data set. We integrate SLB with various index data structures and applications. Experiments show that SLB can improve throughput of the index data structures by up to an order of magnitude. Experiments with real-world key-value traces also show up to 73% throughput improvement on a hash table.

With increasing demands on high-performance and large-capacity SSDs in the enterprise-scale storage, the concern about the inefficient use of the DRAM space in SSDs rises, especially for those using page-level FTL (Flash Translation Layer). In such an FTL, the address mapping scheme allows a logical page address (LPA) to be mapped to any physical page address (PPA) in the disk. Though it provides flexible address management and minimizes internal data movements, it requires a large address mapping table whose size is proportional to the capacity of the disk. With the increase of SSD's capacity, the table can be too large to be held entirely in the DRAM buffer of the SSD, causing constantly accessing to the flash for the address translation. This performance penalty due to the buffer misses is particularly high with workloads of weak access locality and large working sets. In this paper, we propose a space- efficient page- level FTL using hash functions in the address translation, named Hash-based Page- level FTL, or HP-FTL in short, to address the concern. HP-FTL trades mapping flexibility with limited performance impact for high space efficiency allowing the entire table to fit in the buffer and eliminating translation misses. The experiment results show that HP-FTL can provide up to 2.6X throughput compared to DFTL, a representative page-level FTL, using the same amount of DRAM for buffering the table. Meanwhile, HP-FTL reduces the mapping table size to about 25% of the table space required by page- level mapping schemes, including DFTL, without having any buffer misses.

While flash-based SSDs have much higher access speed than hard disks, they have an Achilles heel, which is the service of write requests. Not only is writing slower than reading, but also it can incur expensive garbage collection operations and reduce SSDs' lifetime. The deduplication technique can help to avoid writing data objects whose contents have been on the disk. A typical object is the disk block, for which a block-level deduplication scheme can help identify duplicate ones and avoid their writing. For the technique to be effective, data written to the disk must not only be the same as those currently on the disk but also be block-aligned.

Substantially reduced lifetimes are becoming a critical issue in NAND flash memory with the advent of multi-level cell and triple-level cell flash memory. Researchers discovered that heating can cause worn-out NAND flash cells to become reusable and greatly extend the lifetime of flash memory cells. However, the heating process consumes a substantial amount of power, and some fundamental changes are required for existing NAND flash management techniques. In particular, all existing wear-leveling techniques are based on the principle of evenly distributing writes and erases. For self-healing NAND flash, this may cause NAND flash cells to be worn out in a short period of time. Moreover, frequently healing these cells may drain the energy quickly in battery-driven mobile devices, which is defined as the concentrated heating problem. In this paper, we propose a novel wear-leveling scheme called DHeating (Dispersed Heating) to address the problem. In DHeating, rather than evenly distributing writes and erases over a time period, write and erase operations are scheduled on a small number of flash memory cells at a time, so that these cells can be worn out and healed much earlier than other cells. In this way, we can avoid quick energy depletion caused by concentrated heating. In addition, the heating process takes several seconds and has become the new performance bottleneck. In order to address this issue, we propose a lazy heating repair scheme. The lazy heating repair scheme can ease the long time delays caused by the heating via delaying the heating operation and using the system idle time to repair. Furthermore, the flash memory's reliability becomes worse with the flash memory cells reaching the excepted worn-out time. We propose an early heating strategy to solve the reliability problem. With the extended lifetime provided by self-healing, we can trade some lifetimes for reliability. The idea is to start the healing process earlier than the expected worn-out time. We evaluate our scheme based on an embedded platform. The experimental results show that the proposed scheme can effectively prolong the consecutive heating time interval, alleviate the long time delays caused by the heating, and enhance the reliability for self-healing flash memory.

The in-memory cache system is a performance-critical layer in today's web server architectures. Memcached is one of the most effective, representative, and prevalent among such systems. An important problem is on its memory allocation. The default design does not make the best use of the memory. It is unable to adapt when the demand changes, a problem known as slab calcification. This paper introduces locality-aware memory allocation (LAMA), which addresses the problem by first analyzing the locality of Memcached's requests and then reassigning slabs to minimize the miss ratio or the average response time. By evaluating LAMA using various industry and academic workloads, the paper shows that LAMA outperforms existing techniques in the steady-state performance, the speed of convergence, and the ability to adapt to request pattern changes, and overcome slab calcification. The new solution is close to optimal, achieving over 98 percent of the theoretical potential. Furthermore, LAMA can also be adopted in resource partitioning to guarantee quality-of-service (QoS).

While key-value (KV) cache, such as memcached, dedicates a large volume of expensive memory to holding performance-critical data, it is important to improve memory efficiency, or to reduce cache miss ratio without adding more memory. As we find that optimizing replacement algorithms is of limited effect for this purpose, a promising approach is to use a compact data organization and data compression to increase effective cache size. However, this approach has the risk of degrading the cache's performance due to additional computation cost. A common perception is that a high-performance KV cache is not compatible with use of data compacting techniques.

In high-end data processing systems, such as databases, the execution concurrency level rises continuously since the introduction of multicore processors. This happens both on premises and in the cloud. For these systems, a buffer pool management of high scalability plays an important role on overall system performance. The scalability of buffer pool management is largely determined by its data replacement algorithm, which is a major component in the buffer pool management. It can seriously degrade the scalability if not designed and implemented properly. The root cause is its use of lock-protected data structures that incurs high contention with concurrent accesses. A common practice is to modify the replacement algorithm to reduce the contention on the lock(s), such as approximating the LRU replacement with the CLOCK algorithm or partitioning the data structures and using distributed locks. Unfortunately, the modification usually compromises the algorithm's hit ratio, a major performance goal. It may also involve significant effort on overhauling the original algorithm design and implementation. This paper provides a general solution to improve the scalability of a buffer pool management using any replacement algorithms for the data processing systems on physical on-premises machines and virtual machines in the cloud. Instead of making a difficult trade-off between the high hit ratio of a replacement algorithm and the low lock contention of its approximation, we design a system framework, called BP-Wrapper, that eliminates almost all lock contention without requiring any changes to an existing algorithm. In BP-Wrapper, we use a dynamic batching technique and a prefetching technique to reduce lock contention and to retain high hit ratio. The implementation of BP-Wrapper in PostgreSQL adds only about 300 lines of C code. It can increase the throughput by up to two folds compared with the replacement algorithms with lock contention when running TPC-C-like and TPC-W-like workloads.

Key-value caches, represented by Mem cached, play a critical role in data centers. Its efficacy can significantly impact users' perceived service time and back-end systems' workloads. A central issue in the in-memory cache's management is memory allocation, or how the limited space is distributed for storing key-value items of various sizes. When a cache is full, the allocation issue is how to conduct replacement operations on items of different sizes. To effectively address the issue, a practitioner must simultaneously consider three factors, which are access locality, item size, and miss penalty. Existing designs consider only one or two of the first two factors, and pay little attention on miss penalty. This inadequacy can substantially compromise utilization of cache space and request service time. In this paper we propose a Penalty Aware Memory Allocation scheme (PAMA) that takes all three factors into account. While the three different factors cannot be directly compared to each other in a quantitative manner, PAMA uses their impacts on service time to determine where a unit of memory space should be (de)allocated. The impacts are quantified as the decrease (or increase) of service time if a unit of space is allocated (or deal located). PAMA efficiently tracks access pattern and use of memory, and speculatively evaluates the impacts to enable penalty-aware memory allocation for KV caches. Our evaluation with real-world Mem cached workload traces demonstrates that PAMA can significantly reduce request service time compared to other representative KV cache management schemes.

Users store rapidly increasing amount of data into the cloud. Cloud storage service is often characterized as having a large data set and few deletes. Hosting the service on a conventional system consisting of servers of powerful CPUs and managed by either a key-value (KV) system or a file system is not efficient. First, as demand on storage capacity grows much faster than that on CPU power, existing server configurations can lead to CPU under-utilization and inadequate storage. Second, as data durability is of paramount importance and storage capacity can be limited, a data protection scheme relying on data replication is not space efficient. Third, because of the unique distribution of data object size (mostly a few KBytes), hard disks may suffer from unnecessarily high request rate (when data is stored as KV pairs and need constant re-organization) or too many random writes (when data is stored as relatively small files). In Baidu this inefficiency has become an urgent issue as data is uploaded into the storage at an increasingly high rate and both the user population and the system are rapidly expanding. To address this issue, we adopt a customized compact server design based on the ARM processors and replace three-copy replication for data protection with erasure coding to enable low-power and high-density storage. Furthermore, there is a huge number of objects stored in the system, such as those for photos, MP3 music, and documents, but their sizes do not allow efficient operations in the conventional KV systems. To this end we propose an innovative architecture separating metadata and data managements to enable efficient data coding and storage. The resulting production system, called Atlas, is a highly scalable, reliable, and cost-effective KV store supporting Baidu's cloud storage service.

The objective of maintaining a high efficiency for a shared storage system often has to be compromised with the enforcement of Service-level Agreement (SLA) on quality of service (QoS). From the perspective of I/O scheduling, I/O request service order optimized for disk efficiency can be substantially different from the order required for meeting QoS requirements. When QoS takes priority, the storage system has to serve requests with a sub-optimal efficiency. In this paper, we propose to relate QoS requirements specified for I/O requests to users' experiences. By assuming that only user-observable QoS is necessary for the system to fulfill, we relax QoS requirements on the storage system as long as such a relaxation is not noticeable to users. The relaxation produces a leeway critical for the I/O scheduler to improve disk efficiency. We implement a prototype system, named as intelliQoS, as a proof of concept. In the system the scheduler is allowed to schedule requests in its preferred order as long as the user does not sense any performance degradation through the outputs from the application. In this way the user can still experience the same service quality as required although individual requests' latency requirements can be missed for higher storage efficiency. Our experiments on Xen virtual machines (VMs) show that intelliQoS significantly improves system efficiency by up to 80% without violating user-observable QoS requirements.

Virtual block devices are widely used to provide block interface to virtual machines (VMs). A virtual block device manages an indirection mapping from the virtual address space presented to a VM, to a storage image hosted on file system or storage volume. This indirection is recorded as metadata on the image, also known as a lookup table, which needs to be immediately updated upon each space allocation on the image for data safety (also known as image growth). This growth is common as VM templates for large-scale deployments and snapshots for fast migration of VMs are heavily used. Though each table update involves only a few bytes of data, it demands a random write of an entire block. Furthermore, data consistency demands correct order of metadata and data writes be enforced, usually by inserting the FLUSH command between them. These metadata operations compromise virtual device's efficiency.

In the last several years hundreds of thousands of SSDs have been deployed in the data centers of Baidu, China's largest Internet search company. Currently only 40\% or less of the raw bandwidth of the flash memory in the SSDs is delivered by the storage system to the applications. Moreover, because of space over-provisioning in the SSD to accommodate non-sequential or random writes, and additionally, parity coding across flash channels, typically only 50-70\% of the raw capacity of a commodity SSD can be used for user data. Given the large scale of Baidu's data center, making the most effective use of its SSDs is of great importance. Specifically, we seek to maximize both bandwidth and usable capacity.

While Phase Change Memory (PCM) has emerged as one of most promising complements or even replacements of DRAM-based memory, it has only limited write endurance. Because of uneven write distribution, PCM is highly likely to have early failures, which can spread over the chip space and leave the entire chip unusable. Wear leveling is an indispensable technique to even out wear caused by the writes. However, because of process variation early failure cannot be fully avoided. State-of-the-art wear-leveling schemes, such as Start-Gap and Security Refresh, cease to function once even a single block failure occurs because their designs require persistent writ able address space for wear leveling operations. Existent solutions attempting to address the problem demand substantial OS supports, such as explicit space allocations and data migrations. The demand on substantial OS cooperation creates a barrier to widespread adoption of the PCM technique. While fault-tolerance techniques, such as FREE-p and zombie, that remap failed blocks to inaccessible but healthy space have the potential to address the wear-leveling issue by relocating data from failed blocks to healthy ones, they cannot work together with the wear-leveling schemes as data migration may change placement of relocated data. In this paper, we propose a framework, WL-Reviver, that allows any in-PCM wear-leveling scheme to keep delivering its designed leveling service even after failures occur in its working address space. The design is unique on two aspects: (1) it leverages the fault-tolerance techniques so that they can work together with the wear leveling schemes, and (2) it requires no OS supports additional to what're available to today's DRAM-based memory system. Furthermore, WL-Reviver is a lightweight framework of very low overhead. Our extensive experiments show that WLReviver can efficiently revive a wear-leveling scheme without compromising the scheme's wear-leveling effect.

Various key-value (KV) stores are widely employed for data management to support Internet services as they offer higher efficiency, scalability, and availability than relational database systems. The log-structured merge tree (LSM-tree) based KV stores have attracted growing attention because they can eliminate random writes and maintain acceptable read performance. Recently, as the price per unit capacity of NAND flash decreases, solid state disks (SSDs) have been extensively adopted in enterprise-scale data centers to provide high I/O bandwidth and low access latency. However, it is inefficient to naively combine LSM-tree-based KV stores with SSDs, as the high parallelism enabled within the SSD cannot be fully exploited. Current LSM-tree-based KV stores are designed without assuming SSD's multi-channel architecture.

This article consists of a collection of slides from the author's conference presentation on the special features, system design and architectures, processing capabilities, and targeted markets for Baidu's family of software defined accelerator products (SDA) for large scale deep neural network (DNN) systems.

When files are striped in a parallel I/O system, requests to the files are decomposed into a number of sub-requests that are distributed over multiple servers. If a request is not aligned with the striping pattern such decomposition can make the first and last sub-requests much smaller than the striping unit. Because hard-disk-based servers can be much less efficient in serving small requests than large ones, the system exhibits heterogeneity in serving sub-requests of different sizes, and the net throughput of the entire system can be severely degraded by the inefficiency of serving the smaller requests, or fragments. Because a request is not considered complete until its slowest sub-request is, the penalty is yet greater for synchronous requests. To make the situation even worse, the larger the request, or the more data servers the requested data is striped over, the larger the detrimental performance effect of serving fragments can be. This effect can become the Achilles' heel of a parallel I/O system performance seeking scalability with large sequential accesses. In this paper we propose iBridge, a scheme that uses solid-state drives to serve request fragments and thereby bridge the performance gap between serving fragments and serving large sub-requests. We have implemented iBridge in the PVFS file system. Our experimental results with representative MPI-IO benchmarks show that iBridge can significantly improve the I/O throughput of storage systems, especially for large requests with fragments.

With significant advantages in capacity, power consumption, and price, solid state disk (SSD) has good potential to be employed as an extension of DRAM (memory), such that applications with large working sets could run efficiently on a modestly configured system. While initial results reported in recent works show promising prospects for this use of SSD by incorporating it into the management of virtual memory, frequent writes from write-intensive programs could quickly wear out SSD, making the idea less practical. We propose a scheme, HybridSwap, that integrates a hard disk with an SSD for virtual memory management, synergistically achieving the advantages of both. In addition, HybridSwap can constrain performance loss caused by swapping according to user-specified QoS requirements.

Unlike in the consumer electronics and personal computing areas, in the HPC environment hard disks can hardly be replaced by SSDs. The reasons include hard disk's large capacity, very low price, and decent peak throughput. However, when latency dominates the I/O performance (e.g., when accessing random data), the hard disk's performance can be compromised. If the issue of high latency could be effectively solved, the HPC community would enjoy a large, affordable and fast storage without having to replace disks completely with expensive SSDs. In this paper, we propose an almost latency-free hard-disk dominated storage system called LiU for HPC. The key technique is leveraging limited amount of SSD storage for its low-latency access, and changing data layout in a hybrid storage hierarchy with low-latency SSD at the top and high-latency hard disk at the bottom. If a segment of data would be randomly accessed, we lift its top part (the head) up in the hierarchy to the SSD and leave the remaining part (the body) untouched on the disk. As a result, the latency of accessing this whole segment can be removed because access latency of the body can be hidden by the access time of the head on the SSD. Combined with the effect of prefetching a large segment, LiU (Lift it Up) can effectively remove disk access latency so disk's high peak throughput can now be fully exploited for data-intensive HPC applications. We have implemented a prototype of LiU in the PVFS parallel file system and evaluated it with representative MPI-IO micro benchmarks, including mpi-io-test, mpi-tile-io, and ior-mpi-io, and one macro-benchmark BTIO. Our experimental results show that LiU can effectively improve the I/O performance for HPC applications, with the throughput improvement ratio up to 5.8. Furthermore, LiU can bring much more benefits to sequential-I/O MPI applications when the applications are interfered by other workloads. For example, LiU improves the I/O throughput of mpi-io-test, which is under interference, by 1.1-3.4 times, while improving the same workload without interference by 15%.

While Phase Change Memory (PCM) holds a great promise as a complement or even replacement of DRAM-based memory and flash-based storage, it must effectively overcome its limit on write endurance to be a reliable device for an extended period of intensive use. The limited write endurance can lead to permanent stuck-at faults after a certain number of writes, which causes some memory cells permanently stuck at either '0' or '1'. State-of-the-art solutions apply a bit inversion technique on selected bit groups of a data block after its partitioning. The effectiveness of this approach hinges on how a data block is partitioned into bit groups. While all existing solutions can separate faults into different groups for error correction, they are inadequate on three fundamental capabilities desired for any partition scheme. First, it can maximize probability of successfully re-partitioning a block so that two faults currently in the same group are placed into two new groups. Second, it can partition a block into a small number of groups for space efficiency. Third, it should spread out faults across the groups as uniformly as possible, so that more faults can be accommodated within the same number of groups. A recovery solution with these capabilities can provide strong fault tolerance with minimal overhead.

Prefetching is an important technique for improving effective hard disk performance. A prefetcher seeks to accurately predict which data will be requested and load it ahead of the arrival of the corresponding requests. Current disk prefetch policies in major operating systems track access patterns at the level of file abstraction. While this is useful for exploiting application-level access patterns, for two reasons file-level prefetching cannot realize the full performance improvements achievable by prefetching. First, certain prefetch opportunities can only be detected by knowing the data layout on disk, such as the contiguous layout of file metadata or data from multiple files. Second, nonsequential access of disk data (requiring disk head movement) is much slower than sequential access, and the performance penalty for mis-prefetching a randomly located block, relative to that of a sequential block, is correspondingly greater.

Challenged by serious power and thermal constraints and limited by available instruction-level parallelism, processor designs have evolved to multi-core architectures. These architectures, many augmented with native simultaneous multithreading, are driving software developers to use multithreaded programs to exploit thread-level parallelism. While multithreading is well known to introduce concerns of data dependency and CPU load balance, less known is that the uncertainty of relative progress of thread execution can cause patterns of I/O requests, issued by different threads, to be effectively random and so significantly degrade hard-disk efficiency. This effect can severely offset the performance gains from parallel execution, especially for I/O-intensive programs. Retaining the benefits of multithreading while not losing I/O efficiency is an urgent and challenging problem. We propose a user-level scheme, iHarmonizer, to streamline the servicing of I/O requests from multiple threads in the Open MP programs. Specifically, we use the compiler to insert code into Open MP programs so that data usage can be transmitted at run time to a supporting run-time library that prefetches data in a disk friendly way and coordinates threads' execution according to the availability of their requested data. Transparent to the programmer, iHarmonizer makes a multithreaded program I/O efficient while maintaining the benefits of parallelism. Our experiments show that iHarmonizer can significantly speed up the execution of a representative set of I/O-intensive scientific benchmarks.

A parallel system relies on both process scheduling and I/O scheduling for efficient use of resources, and a program's performance hinges on the resource on which it is bottlenecked. Existing process schedulers and I/O schedulers are independent. However, when the bottleneck is I/O, there is an opportunity to alleviate it via cooperation between the I/O and process schedulers: the service efficiency of I/O requests can be highly dependent on their issuance order, which in turn is heavily influenced by process scheduling. We propose a data-driven program execution mode in which process scheduling and request issuance are coordinated to facilitate effective I/O scheduling for high disk efficiency. Our implementation, Dual Par, uses process suspension and resumption, as well as pre-execution and prefetching techniques, to provide a pool of pre-sorted requests to the I/O scheduler. This data-driven execution mode is enabled when I/O is detected to be the bottleneck, otherwise the program runs in the normal computation-driven mode. Dual Par is implemented in the MPICH2 MPI-IO library for MPI programs to coordinate I/O service and process execution. Our experiments on a 120-node cluster using the PVFS2 file system show that Dual Par can increase system I/O throughput by 31% on average, compared to existing MPI-IO with or without using collective I/O.

The parallel data accesses inherent to large-scale data-intensive scientific computing require that data servers handle very high I/O concurrency. Concurrent requests from different processes or programs to hard disk can cause disk head thrashing between different disk regions, resulting in unacceptably low I/O performance. Current storage systems either rely on the disk scheduler at each data server, or use SSD as storage, to minimize this negative performance effect. However, the ability of the scheduler to alleviate this problem by scheduling requests in memory is limited by concerns such as long disk access times, and potential loss of dirty data with system failure. Meanwhile, SSD is too expensive to be widely used as the major storage device in the HPC environment. We propose iTransformer, a scheme that employs a small SSD to schedule requests for the data on disk. Being less space constrained than with more expensive DRAM, iTransformer can buffer larger amounts of dirty data before writing it back to the disk, or prefetch a larger volume of data in a batch into the SSD. In both cases high disk efficiency can be maintained even for concurrent requests. Furthermore, the scheme allows the scheduling of requests in the background to hide the cost of random disk access behind serving process requests. Finally, as a non-volatile memory, concerns about the quantity of dirty data are obviated. We have implemented iTransformer in the Linux kernel and tested it on a large cluster running PVFS2. Our experiments show that iTransformer can improve the I/O throughput of the cluster by 35% on average for MPI/IO benchmarks of various data access patterns.

Key-value stores are a vital component in many scale-out enterprises, including social networks, online retail, and risk analysis. Accordingly, they are receiving increased attention from the research community in an effort to improve their performance, scalability, reliability, cost, and power consumption. To be effective, such efforts require a detailed understanding of realistic key-value workloads. And yet little is known about these workloads outside of the companies that operate them. This paper aims to address this gap.

The solid-state disk (SSD) is becoming increasingly popular, especially among users whose workloads exhibit substantial random access patterns. As SSD competes with the hard disk, whose per-GB cost keeps dramatically falling, the SSD must retain its performance advantages even with low-cost configurations, such as those with a small built-in DRAM cache for mapping table and using MLC NAND. To this end, we need to make the limited cache space efficiently used to support fast logical-to-physical address translation in the flash translation layer (FTL) with minimal access of flash memory and minimal merge operations. Existing schemes usually require a large number of overhead accesses, either for accessing uncached entries of the mapping table or for the merge operation, and achieve suboptimal performance when the cache space is limited. In this paper we take into account spatial locality exhibited in the workloads to obtain a highly efficient FTL even with a relatively small cache, named as S-FTL. Specifically, we identify three access patterns related to spatial locality, including sequential writes, clustered access, and sparse writes. Accordingly we propose designs to take advantage of these patterns to reduce mapping table size, increase hit ratio for in-cache address translation, and minimize expensive writes to flash memory. We have conducted extensive trace-driven simulations to evaluate S-FTL and compared it with other state-of-the-art FTL schemes. Our experiments show that S-FTL can reduce accesses to the flash for address translation by up to 70% and reduce response time of SSD by up to 25%, compared with the state-of-the-art FTL strategies such as FAST and DFTL.

Currently the QoS requirements for disk-based storage systems are usually presented in the form of service-level agreement (SLA) to bound I/O measures such as latency and throughput of I/O requests. However, SLA is not an effective performance interface for users to specify their required I/O service quality for two major reasons. First, for users, it is difficult to determine appropriate latency and throughput bounds to ensure their application performance without resource over-provisioning. Second, for storage system administrators, it is a challenge to estimate a user's real resource demand because the specified SLA measures are not consistently correlated with the user's resource demand. This makes resource provisioning and scheduling less informative and could greatly reduce system efficiency. We propose the concept of reference storage system (RSS), which can be a storage system chosen by users and whose performance can be measured off-line and mimicked on-line, as a performance interface between applications and storage servers. By designating an RSS to represent I/O performance requirement, a user can expect the performance received from a shared storage server servicing his I/O workload is not worse than the performance received from the RSS servicing the same workload. The storage system is responsible for implementing the RSS interface. The key enabling techniques are a machine learning model that derives request-specific performance requirements and an RSS-centric scheduling that efficiently allocates resource among requests from different users. The proposed scheme, named as YouChoose, supports the user-chosen performance interface through efficiently implementing and migrating virtual storage devices in a host storage system. Our evaluation based on trace-driven simulations shows that YouChoose can precisely implement the RSS performance interface, achieve a strong performance assurance and isolation, and improve the efficiency of a consolidated storage system consisting of different types of storage devices.

While the performance of compute-bound applications can be effectively guaranteed with techniques such as space sharing or QoS-aware process scheduling, it remains a challenge to meet QoS requirements for end users of I/O-intensive applications using shared storage systems because of the difficulty of differentiating I/O services for different applications with individual quality requirements. Furthermore, it is difficult for end users to accurately specify performance goals to the storage system using I/O-related metrics such as request latency or throughput. As access patterns, request rates, and the system workload change in time, a fixed I/O performance goal, such as bounds on throughput or latency, can be expensive to achieve and may not provide performance guarantees such as bounded program execution time.

Currently the QoS requirements for storage systems are usually presented in the form of service-level agreement (SLA) to bound I/O measures such as latency and throughput of I/O requests. However, SLA is not an effective performance interface for users to specify their required I/O service quality for two major reasons. First, for users it is difficult to determine appropriate latency and throughput bounds to ensure their required application performance without resource over-provisioning. Second, for storage system administrators it is a challenge to estimate a user’s real resource demand because the specified SLA measures are not consistently correlated with the user’s resource demand. This makes resource provisioning and scheduling less informative and can greatly reduce system efficiency. We propose the concept of reference storage system (RSS), which can be a storage system chosen by users and whose performance can be measured offline and mimicked online, as a performance interface between applications and storage servers. By designating an RSS to represent I/O performance requirement, a user can expect the performance received from a shared storage server servicing his I/O workload is not worse than the performance received from the RSS servicing the same workload. The storage system is responsible for implementing the RSS interface. The key enabling techniques are a machine learning model that derives request-specific performance requirements and an RSS-centric scheduling that efficiently allocates resource among requests from different users. The proposed scheme, named as YouChoose , supports the user-chosen performance interface through efficiently implementing and migrating virtual storage devices in a host storage system. Our evaluation based on trace-driven simulations shows that YouChoose can precisely implement the RSS performance interface, achieve a strong performance assurance and isolation, and improve the efficiency of a consolidated storage system consisting of different types of storage devices.

As the number of I/O-intensive MPI programs becomes increasingly large, many efforts have been made to improve I/O performance, on both software and architecture sides. On the software side, researchers can optimize processes' access patterns, either individually (e.g., by using large and sequential requests in each process), or collectively (e.g., by using collective I/O). On the architecture side, files are striped over multiple I/O nodes for a high aggregate I/O throughput. However, a key weakness, the access interference on each I/O node, remains unaddressed in these efforts. When requests from multiple processes are served simultaneously by multiple I/O nodes, one I/O node has to concurrently serve requests from different processes. Usually the I/O node stores its data on the hard disks, and different process accesses different regions of a data set. When there are a burst of requests from multiple processes, requests from different processes to a disk compete with each other for its single disk head to access data. The disk efficiency can be significantly reduced due to frequent disk head seeks.

A cluster of data servers and a parallel file system are often used to provide high-throughput I/O service to parallel programs running on a compute cluster. To exploit I/O parallelism parallel file systems stripe file data across the data servers. While this practice is effective in serving asynchronous requests, it may break individual program's spatial locality, which can seriously degrade I/O performance when the data servers concurrently serve synchronous requests from multiple I/O-intensive programs. In this paper we propose a scheme, IOrchestrator, to improve I/O performance of multi-node storage systems by orchestrating I/O services among programs when such inter-data-server coordination is dynamically determined to be cost effective. We have implemented IOrchestrator in the PVFS2 parallel file system. Our experiments with representative parallel benchmarks show that IOrchestrator can significantly improve I/O performance-- by up to a factor of 2.5--delivered by a cluster of data servers servicing concurrently-running parallel programs. Notably, we have not observed any scenarios in which the use of IOrchestrator causes substantial performance degradation.

In a distributed environment, the utilization of file buffer caches in different clients may greatly vary. Cooperative caching has been proposed to increase cache utilization by coordinating the shared usage of distributed caches. It allows clients that would more greatly benefit from larger caches to forward data objects to peer clients with relatively underutilized caches. To support such coordination, global cache utilization must be dynamically evaluated. This, in turn, requires an effective analysis of application data access patterns. Existing coordination protocols are demonstrably suboptimal in this respect, exhibiting inefficient memory utilization and undue interference among clients. We propose a locality-aware cooperative caching protocol, called LAC, that is based on analysis and manipulation of data block reuse distance to effectively predict cache utilization and the probability of data reuse at each client. Using a dynamically adaptive synchronization technique, we keep local information up to date and consistently comparable across clients. The system is highly scalable in the sense that global coordination is achieved without centralized control. We have conducted thorough trace-driven simulation experiments to assess the performance differences between LAC and various existing protocols representative of the general class. Using a realistic and representative cost model, we show that the LAC protocol significantly and consistently outperforms existing cooperative caching protocols, demonstrating high and balanced utilization of caches across all clients. In our experiments, LAC reduces block access time by up to 36 percent, with an average of 31 percent, over the system without peer cache coordination, and reduces block access time by up to 22 percent, with an average of 13 percent, over the best performer of the existing protocols.

In a high-end database system, the execution concurrency level rises continuously in a multiprocessor environment due to the increase in number of concurrent transactions and the introduction of multi-core processors. A new challenge for buffer management to address is to retain its scalability in responding to the highly concurrent data processing demands and environment. The page replacement algorithm, a major component in the buffer management, can seriously degrade the system's performance if the algorithm is not implemented in a scalable way. A lock-protected data structure is used in most replacement algorithms, where high contention is caused by concurrent accesses. A common practice is to modify a replacement algorithm to reduce the contention, such as to approximate the LRU replacement with the clock algorithm. Unfortunately, this type of modification usually hurts hit ratios of original algorithms. This problem may not exist or can be tolerated in an environment of low concurrency, thus has not been given enough attention for a long time. In this paper, instead of making a trade-off between the high hit ratio of a replacement algorithm and the low lock contention of its approximation, we propose a system framework, called BP-Wrapper, that (almost) eliminates lock contention for any replacement algorithm without requiring any changes to the algorithm. In BP-Wrapper, we use batching and prefetching techniques to reduce lock contention and to retain high hit ratio. The implementation of BP-Wrapper in PostgreSQL version 8.2 adds only about 300 lines of C code. It can increase the throughput up to two folds compared with the replacement algorithms with lock contention when running TPC-C-like and TPC-W-like workloads.

Collective I/O is a widely used technique to improve I/O performance in parallel computing. It can be implemented as a client-based or as a server-based scheme. The client-based implementation is more widely adopted in the MPIIO software such as ROMIO because of its independence from the storage system configuration and its greater portability. However, existing implementations of client-side collective I/O do not consider the actual pattern of file striping over multiple I/O nodes in the storage system. This can cause a large number of requests for non-sequential data at I/O nodes, substantially degrading I/O performance. Investigating a surprisingly high I/O throughput achieved when there is an accidental match between a particular request pattern and the data striping pattern on the I/O nodes, we reveal the resonance phenomenon as the cause. Exploiting readily available information on data striping from the metadata server in popular file systems such as PVFS2 and Lustre, we design a new collective I/O implementation technique, named as resonant I/O, that makes resonance a common case. Resonant I/O rearranges requests from multiple MPI processes according to the presumed data layout on the disks of I/O nodes so that non-sequential access of disk data can be turned into sequential access, significantly improving I/O performance without compromising the independence of a client-based implementation. We have implemented our design in ROMIO. Our experimental results on a small- and medium-scale cluster show that the scheme can increase I/O throughput for some commonly used parallel I/O benchmarks such as mpi-io-test and ior-mpi-io over the existing implementation of ROMIO by up to 157%, with no scenario demonstrating significantly decreased performance.

Flooding is a fundamental file search operation in unstructured peer-to-peer (P2P) file sharing systems, in which a peer starts the file search procedure by broadcasting a query to its neighbors, who continue to propagate it to their neighbors. This procedure repeats until a time-to-live (TTL) counter is decremented to 0. Flooding can seriously limit system scalability, because the number of redundant query messages grows exponentially during the message propagation. Our study shows that more than 70 percent of the generated messages are redundant in a flooding with a TTL of 7 in a moderately connected Gnutella network. Existing efforts to address this issue have been focused on limiting the use of the flooding operation. We propose a new flooding scheme, called LightFlood, with the objective of minimizing the number of redundant messages and retaining a similar message-propagating scope as that of the standard flooding. In the scheme, each peer keeps track of the connectivities of every immediate and next indirect neighbor peers, which can be acquired locally. LightFlood identifies the neighbor with the highest connectivity and uses the link to that neighbor to form a suboverlay within the existing P2P overlay. In LightFlood, flooding is divided into two stages. The first stage is a standard flooding with a limited number of TTL hops, where a message can spread to a sufficiently large scope with a small number of redundant messages. In the second stage, message propagating is only conducted along the suboverlay, significantly reducing the number of redundant messages. Our analysis and simulation experiments show that the LightFlood scheme provides a low-overhead broadcast facility that can be effectively used in P2P search. For example, compared with standard flooding with seven TTL hops, we show that LightFlood with an additional two to three hops can reduce up to 69 percent of the flooding messages and retain the same flooding scope. We believe that LightFlood can be widely used as a core mechanism for efficient message broadcasting in P2P systems due to its near-optimal performance.

Lustre is a parallel file system that presents high aggregated IO bandwidth by striping file extents across many storage devices. However, our experiments indicate excessively wide striping can cause performance degradation. Lustre supports an innovative file joining feature that joins files in place. To mitigate striping overhead and benefit collective IO, we propose two techniques: split writing and hierarchical striping. In split writing, a file is created as separate subfiles, each of which is striped to only a few storage devices. They are joined as a single file at the file close time. Hierarchical striping builds on top of split writing and orchestrates the span of subfiles in a hierarchical manner to avoid overlapping and achieve the appropriate coverage of storage devices. Together, these techniques can avoid the overhead associated with large stripe width, while still being able to combine bandwidth available from many storage devices. We have prototyped these techniques in the ROMIO implementation of MPI-IO. Experimental results indicate that split writing and hierarchical striping can significantly improve the performance of Lustre collective IO in terms of both data transfer and management operations. On a Lustre file system configured with 46 object storage targets, our implementation improves collective write performance of a 16-process job by as much as 220%.

State-of-the-art networked storage servers are equipped with increasingly powerful computing capability and large DRAM memory as storage caches. However, their contribution to the performance improvement of networked storage system has become increasingly limited. This is because the client-side memory sizes are also increasing, which reduces capacity misses in the client buffer caches as well as access locality in the storage servers, thus weakening the caching effectiveness of server storage caches. Proactive caching in storage servers is highly desirable to reduce cold misses in clients. We propose an effective way to improve the utilization of storage server resources through prefetching in storage servers for clients. In particular, our design well utilizes two unique strengths of networked storage servers which are not leveraged in existing storage server prefetching schemes. First, powerful storage servers have idle CPU cycles, under-utilized disk bandwidth, and abundant memory space, providing many opportunities for aggressive disk data prefetching. Second, the servers have the knowledge about high-latency operations in storage devices, such as disk head positioning, which enables efficient disk data prefetching based on an accurate cost-benefit analysis of prefetch operations. We present STEP - a Sequentiality and Thrashing dEtec- tion based Prefetching scheme, and its implementation with Linux Kernel 2.6.16. Our performance evaluation by replaying storage performance council (SPC) 's OLTP traces shows that server performance improvements are up to 94% with an average of 25%. Improvements with frequently used Unix applications are up to 53% with an average of 12%. Our experiments also show that STEP has little effect on workloads with random access patterns, such as SPC Web-search traces.

Extension of battery lifetime has always been a major issue for mobile computing. While more and more data are involved in mobile computing, energy consumption caused by I/O operations becomes increasingly large. In a pervasive computing environment, the requested data can be stored both on the local disk of a mobile computer by using the hoarding technique, and on the remote server, where data are accessible via wireless communication. Based on the current operational states of local disk (active or standby), the amount of data to be requested (small or large), and currently available wireless bandwidth (strong or weak reception), data access source can be adaptively selected to achieve maximum energy reduction. To this end, we propose a profile-based I/O management scheme, FlexFetch, that is aware of access history and adaptive to current access environment. Our simulation experiments driven by real-life traces demonstrate that the scheme can significantly reduce energy consumption in a mobile computer compared with existing representative schemes.

On-disk sequentiality of requested blocks, or their spatial locality, is critical to real disk performance where the throughput of access to sequentially-placed disk blocks can be an order of magnitude higher than that of access to randomly-placed blocks. Unfortunately, spatial locality of cached blocks is largely ignored, and only temporal locality is considered in current system buffer cache managements. Thus, disk performance for workloads without dominant sequential accesses can be seriously degraded. To address this problem, we propose a scheme called DULO ( DU al LO cality) which exploits both temporal and spatial localities in the buffer cache management. Leveraging the filtering effect of the buffer cache, DULO can influence the I/O request stream by making the requests passed to the disk more sequential, thus significantly increasing the effectiveness of I/O scheduling and prefetching for disk performance improvements. We have implemented a prototype of DULO in Linux 2.6.11. The implementation shows that DULO can significantly increases disk I/O throughput for real-world applications such as a Web server, TPC benchmark, file system benchmark, and scientific programs. It reduces their execution times by as much as 53%.

In a distributed environment the utilization of file buffer caches in different clients may vary greatly. Cooperative caching is used to increase cache utilization by coordinating the usage of distributed caches. Existing cooperative caching protocols mainly address organizational issues, paying little attention to exploiting locality of file access patterns. We propose a locality-aware cooperative caching protocol, called LAC, that is based on analysis and manipulation of data block reuse distance to effectively predict cache utilization and the probability of data reuse. Using a dynamically controlled synchronization technique, we make local information consistently comparable among clients. The system is highly scalable in the sense that global coordination is achieved without centralized control.

In a mobile computer the hard disk consumes a considerable amount of energy. Existing dynamic power management policies usually take conservative approaches to save disk energy, and disk energy consumption remains a serious issue. Meanwhile, the flash drive is becoming a must-have portable storage device for almost every laptop user on travel. In this paper, we propose to make another highly desired use of the flash drive --- saving disk energy. This is achieved by using the flash drive as a standby buffer for caching and prefetching disk data. Our design significantly extends disk idle times with careful and deliberate consideration of the particular characteristics of the flash drive. Trace-driven simulations show that up to 41% of disk energy can be saved with a relatively small amount of data written to the flash drive.

The paper proposes MESA (Multicoloring with Embedded Skewed Associativity), a novel cache indexing scheme that integrates dynamic page coloring with static skewed associativity to reduce conflicts in L2/L3 caches with a small degree of associativity. MESA associates multiple cache pages (colors) with each virtual memory page and uses two-level skewed associativity, first to map a page to a different color in each bank of the cache, and then to disperse the lines of a page across the banks and within the colors of the page. MESA is a multi-grained cache indexing scheme that combines the best of two worlds, page coloring and skewed associativity. We also propose a novel cache management scheme based on page remapping, which uses cache miss imbalance between colors in each bank as the metric to track conflicts and trigger remapping. We evaluate MESA using 24 benchmarks from multiple application domains and with various degrees of sensitivity to conflict misses, on both an in-order issue processor (using complete system simulation) and an out-of-order issue processor (using SimpleScalar). MESA outperforms skewed associativity, prime modulo hashing, and dynamic page coloring schemes proposed earlier. Compared to a 4-way associative cache, MESA can provide as much as 76% improvement in IPC.

We describe the software architecture, technical features, and performance of TICK (Transparent Incremental Checkpointer at Kernel level), a system-level checkpointer implemented as a kernel thread, specifi- cally designed to provide fault tolerance in Linux clusters. This implementation, based on the 2.6.11 Linux kernel, provides the essential functionality for transparent, highly responsive, and efficient fault tolerance based on full or incremental checkpointing at system level. TICK is completely user-transparent and does not require any changes to user code or system libraries; it is highly responsive: an interrupt, such as a timer interrupt, can trigger a checkpoint in as little as 2.5µs; and it supports incremental and full checkpoints with minimal overhead-less than 6% with full checkpointing to disk performed as frequently as once per minute.

Although the LRU replacement algorithm has been widely used in buffer cache management, it is well-known for its inability to cope with access patterns with weak locality. Previously proposed algorithms to improve LRU greatly increase complexity and/or cannot provide consistently improved performance. Some of the algorithms only address LRU problems on certain specific and predefined cases. Motivated by the limitations of existing algorithms, we propose a general and efficient replacement algorithm, called Low Inter-reference Recency Set (LIRS). LIRS effectively addresses the limitations of LRU by using recency to evaluate Inter-Reference Recency (IRR) of accessed blocks for making a replacement decision. This is in contrast to what LRU does: directly using recency to predict the next reference time. Meanwhile, LIRS mostly retains the simple assumption adopted by LRU for predicting future block access behaviors. Conducting simulations with a variety of traces of different access patterns and with a wide range of cache sizes, we show that LIRS significantly outperforms LRU and outperforms other existing replacement algorithms in most cases. Furthermore, we show that the additional cost for implementing LIRS is trivial in comparison with that of LRU. We also show that the LIRS algorithm can be extended into a family of replacement algorithms, in which LRU is a special member.

The demand of delivering streaming media content in the Internet has become increasingly high for scientific, educational, and commercial applications. Three representative technologies have been developed for this purpose, each of which has its merits and serious limitations. Infrastructure-based CDNs with dedicated network bandwidths and powerful media replicas can provide high quality streaming services but at a high cost. Server-based proxies are cost-effective but not scalable due to the limited proxy capacity and its centralized control. Client-based P2P networks are scalable but do not guarantee high quality streaming service due to the transient nature of peers. To address these limitations, we present a novel and efficient design of a scalable and reliable media proxy system supported by P2P networks. This system is called PROP abbreviated from our technical theme of "collaborating and coordinating PROxy and its P2P clients". Our objective is to address both scalability and reliability issues of streaming media delivery in a cost-effective way. In the PROP system, the clients' machines in an intranet are self-organized into a structured P2P system to provide a large media storage and to actively participate in the streaming media delivery, where the proxy is also embedded as an important member to ensure quality of streaming service. The coordination and collaboration in the system are efficiently conducted by our P2P management structure and replacement policies. We have comparatively evaluated our system by trace-driven simulations with synthetic workloads and with a real-life workload trace extracted from the media server logs in an enterprise network. The results show that our design significantly improves the quality of media streaming and the system scalability.

In a large client/server cluster system, file blocks are cached in a multilevel storage hierarchy. Existing file block placement and replacement are either conducted on each level of the hierarchy independently, or by applying an LRU policy on more than one levels. One major limitation of these schemes is that hierarchical locality of file blocks with nonuniform strengths is ignored, resulting in many unnecessary block misses, or additional communication overhead. To address this issue, we propose a client-directed, coordinated file block placement and replacement protocol, where the nonuniform strengths of locality are dynamically identified on the client level to direct servers on placing or replacing file blocks accordingly on different levels of the buffer caches. In other words, the caching layout of the blocks in the hierarchy dynamically matches the locality of block accesses. The effectiveness of our proposed protocol comes from achieving the following three goals: (1) The multilevel cache retains the same hit rate as that of a single level cache whose size equals to the aggregate size of multilevel caches. (2) The nonuniform locality strengths of blocks are fully exploited and ranked to fit into the physical multilevel caches. (3) The communication overheads between caches are also reduced.

Summary form only given. A peer-to-peer (P2P) system is built upon an overlay network whose topology is independent of the underlying physical network. A well-routed message path in an overlay network with a small number of logical hops can result in a long delay and excessive traffic due to undesirably long distances in some physical links. We propose an effective method, called SAT-Match, to adoptively construct structured P2P overlay networks, aiming at significantly reducing the lookup routing latency. In this method, each joining peer is initially guided to find a physically close neighbor to connect with. After then, its overlay location is adoptively adjusted whenever a location mismatch is detected. The topology matching optimization in our method solely relies on local neighborhood information. Compared with existing topology matching methods, our method addresses their three limitations: (1) heavily relying on global information about the Internet by using landmark-based measurements, (2) lacking adaptation to frequent peer movement in a dynamic environment, such as mobile networks, and (3) insufficiently accurate in topology matching due to the lack of adaptive topology adjustment. We have evaluated our method in the content-addressable network (CAN), a representative structured P2P system with a strong tolerance to frequent peer arrivals/departures. Through intensive simulation experiments on large scale CAN overlays, we have shown the effectiveness of SAT-Match. Our method can achieve average logical/physical link latency reduction rate by up to 40%. It also outperforms "landmark binning", a method utilizing global information by up to 20%. Finally, combining with the landmark binning method, SAT-Match can achieve up to 60% latency reduction.

Effectively utilizing disk caches is critical for delivering and sharing data in data-grids considering the large sizes of requested files and excessively prolonged file transmission time. An essential component in the disk cache management is its replacement policy that determines which file(s) are least valuable and should be evicted to create space for incoming files. Though a large number of replacement algorithms for data objects of different sizes have been proposed recently in the domain of Web-caching and disk caching in data grids, they inherit the shortcomings of the LRU and LFU replacements in characterization access patterns. In order to address this limit, we propose a technique to measure relative file access locality strength - how soon a file is to be re-accessed before being evicted compared with other files. When we estimate the in-cache reaccess probability, we take the disk space consumed by accessed files as well as disk cache size into consideration. Using relative locality strength estimation, we are able to accurately rank the value of each file for being cached, and select the file(s) with least values for replacement. Our simulation results show that our proposed policy is the most effective one among existing policies in interpreting access patterns, and considering achieves performance improvement measured by hit ratios and byte hit ratios.

Searching efficiency is a decisive factor concerning scalability in large-scale peer-to-peer (P2P) file sharing systems. While flooding is the most commonly used and user-performance oriented method to broadcast query across unstructured P2P networks, it generates a large number of redundant messages. Our study shows that more than 70% of messages are redundant using flooding in a moderately connected network, which imposes an increasingly excessive burden on the underlying infrastructure, hindering the growth and scalability of P2P systems. To reduce the use of flooding as well as its associated overhead, we utilize access trails left by a standard flooding, which is a collection of P2P links used by non-redundant messages. Thus the multiple queries following the flooding can be broadcasted along the trail to achieve two goals: (1) The ability of flooding to achieve short response time is maintained; and (2) the cost of a broadcast is minimized. Though the trail can be partially damaged in an ad hoc system with frequent arrivals and departures of peers, we use repeated trail refreshings and additional trail links to make a trail consistently available for query broadcast. We call this trail-based technique FloodTrail. We have evaluated the performance of FloodTrail on P2P systems for Web contents sharing. Simulation results show that FloodTrail could reduce flooding traffic by up to 57%, while maintaining almost the same search coverage as that of flooding.

"Flooding" is a fundamental operation in unstructured peer-to-peer (P2P) file sharing systems, such as Gnutella. Although it is effective in content search, flooding is very inefficient because it results in a great amount of redundant messages. Our study shows that more than 70% of the generated messages are redundant for a flooding with a TTL of 7 in a moderately connected network. Existing efforts to address this problem have been focused on limiting the use of flooding operations. We propose LightFlood, an efficient flooding scheme, with the objective of minimizing the number of redundant messages and retaining the same message propagating scope as that of standard flooding. By constructing a tree-like suboverlay within the existing P2P overlay called FloodNet, the flooding operation in LightFlood is divided into two stages. In the first stage, a message is propagated by using the standard flooding scheme with three or four TTL hops, through which the message can be spread to a sufficiently large scope with a small number of redundant messages. In the second stage, the message propagating is only conducted across the FloodNet, significantly reducing the number of redundant messages. Our analysis and simulation results show that the LightFlood scheme provides a low overhead broadcasting facility that can be effectively used in P2P searching. Compared with standard flooding used in Gnutella, we show that the LightFlood scheme with an additional 2 to 3 hops can reduce up to more than 69% of flooding messages, and retain the same flooding scope

Although LRU replacement policy has been commonly used in the buffer cache management, it is well known for its inability to cope with access patterns with weak locality. Previous work, such as LRU-K and 2Q, attempts to enhance LRU capacity by making use of additional history information of previous block references other than only the recency information used in LRU. These algorithms greatly increase complexity and/or can not consistently provide performance improvement. Many recently proposed policies, such as UBM and SEQ, improve replacement performance by exploiting access regularities in references. They only address LRU problems on certain specific and well-defined cases such as access patterns like sequences and loops. Motivated by the limits of previous studies, we propose an efficient buffer cache replacement policy, called Low Inter-reference Recency Set (LIRS). LIRS effectively addresses the limits of LRU by using recency to evaluate Inter-Reference Recency (IRR) for making a replacement decision. This is in contrast to what LRU does: directly using recency to predict next reference timing. At the same time, LIRS almost retains the same simple assumption of LRU to predict future access behavior of blocks. Our objectives are to effectively address the limits of LRU for a general purpose, to retain the low overhead merit of LRU, and to outperform those replacement policies relying on the access regularity detections. Conducting simulations with a variety of traces and a wide range of cache sizes, we show that LIRS significantly outperforms LRU, and outperforms other existing replacement algorithms in most cases. Furthermore, we show that the additional cost for implementing LIRS is trivial in comparison with LRU.

Abstract Operating system designers attempt to keep high CPU utilization by maintaining an optimal multiprogramming level (MPL). Although running more processes makes it less likely to leave the CPU idle, too many processes adversely incur serious memory competition, and even introduce thrashing, which eventually lowers CPU utilization. A common practice to address the problem is to lower the MPL with the aid of process swapping out/in operations. This approach is expensive and is only used when the system begins serious thrashing. The objective of our study is to provide highly responsive and cost‐effective thrashing protection by adaptively conducting priority page replacement in a timely manner. We have designed a dynamic system Thrashing Protection Facility (TPF) in the system kernel. Once TPF detects system thrashing, one of the active processes will be identified for protection. The identified process will have a short period of privilege in which it does not contribute its least recently used (LRU) pages for removal so that the process can quickly establish its working set, improving the CPU utilization. With the support of TPF, thrashing can be eliminated in its early stage by adaptive page replacement, so that process swapping will be avoided or delayed until it is truly necessary. We have implemented TPF in a current and representative Linux kernel running on an Intel Pentium machine. Compared with the original Linux page replacement, we showthat TPF consistently and significantly reduces page faults and the execution time of each individual job in several groups of interacting SPEC CPU2000 programs. We also show that TPF introduces little additional overhead to program executions, and its implementation in Linux (or Unix) systems is straightforward. Copyright © 2002 John Wiley & Sons, Ltd.