Compute Express Link (CXL) has emerged as a pivotal interconnect for memory expansion. Despite its potential, the performance implications of CXL across devices, latency regimes, processors, and workloads remain underexplored. We present Melody, a framework for systematic characterization and analysis of CXL memory performance. Melody builds on an extensive evaluation spanning 265 workloads, 4 real CXL devices, 7 latency levels, and 5 CPU platforms. Melody yields many insights: workload sensitivity to sub-μs CXL latencies (140-410ns), the first disclosure of CXL tail latencies, CPU tolerance to CXL latencies, a novel approach (SPA) for pinpointing CXL bottlenecks, and CPU prefetcher inefficiencies under CXL.

In LSM-based KV stores, typically deployed on systems with DRAM-SSD storage, compaction degrades write performance and SSD endurance due to significant write amplification. To address this issue, recent proposals have mostly focused on redesigning the structure of LSM trees. In this paper, we observe the prevalence of data blocks that are are simply read and written back without being altered during the LSM-tree compaction process, which we refer to as Unchanged Data Blocks (UDBs). These UDBs are source of unnecessary write amplification leading to performance degradation and shortening of SSD lifetime. To address this duplication issue, we propose a remapping-based compaction method, which we call RemapCom. RemapCom considers the identification and retention by designing a lightweight state machine to track the status of the KV items in each data block as well as designing a UDB retention strategy to prevent data blocks from being split due to adjacent intersecting blocks. We implement a prototype of RemapCom on LevelDB by providing two primitives for the remapping. Compared to the state-of-the-art, evaluation results demonstrate that RemapCom can reduce the write amplification by up to 53%.

Thanks to the advance of device scaling technologies, the capacity of SSDs is rapidly increasing. Such increase, however, comes at the cost of a huge index table requiring large DRAM. To provide reasonable performance with less DRAM, various index structures exploiting locality and regularity of I/O references have been proposed. However, they provide deteriorated performance depending on I/O patterns and storage fragmentation. This paper proposes a novel approximate index structure, called AppL, which combines memory-efficient approximate indices and an LSM-tree that has an append-only and sorted nature. AppL reduces the index size to 6-8-bits per entry, which is considerably smaller than the typical index structures requiring 32-64-bits, and maintains such high memory efficiency irrespective of locality and fragmentation. By alleviating memory pressure, AppL achieves 33.6-72.4% shorter read latency and 28.4%-83.4% higher I/O throughput than state-of-the-art techniques.

Serverless computing platforms have become popular in cloud computing environments due to several advantages such as elasticity and flexibility of using cloud resources and statelessness of serverless functions. In this paper, we explore integrating a GPU cluster management framework for multitenant Deep Learning (DL) training with serverless computing technologies. We propose a novel framework, FEDeS (Fair, Efficient, and Reliable Multi-tenant Deep Learning Training with Serverless Computing), where the training process of a DL model is converted to chained serverless functions. Leveraging the independent execution of serverless functions, we propose gang-relaxed scheduling, which enables elastic and flexible GPU allocation to each DL job. We also present resource allocation policies with generalized$\alpha$-fairness, which controls the tradeoff between fairness and efficiency by adjusting the$\alpha$value, and devise a fine-grained fault tolerance method for DL training jobs. Experimental results using various DL models such as BERT and GPT on real workload traces show the benefits of using a serverless platform, including efficiency, fairness, and reliability.

Many datasets in real life are complex and dynamic, that is, their key densities are varied over the whole key space and their key distributions change over time. It is challenging for an index structure to efficiently support all key operations for data management, in particular, search, insert, and scan, for such dynamic datasets. In this article, we present DyTIS (Dynamic dataset Targeted Index Structure), an index that targets dynamic datasets. DyTIS, although based on the structure of Extendible hashing, leverages the CDF of the key distribution of a dataset, and learns and adjusts its structure as the dataset grows. The key novelty behind DyTIS is to group keys by the natural key order and maintain keys in sorted order in each bucket to support scan operations within a hash index. We also define what we refer to as a dynamic dataset and propose a means to quantify its dynamic characteristics. Our experimental results show that DyTIS provides higher performance than the state-of-the-art learned index for the dynamic datasets considered. We also analyze the effects of the dynamic characteristics of datasets, including sequential datasets, as well as the effect of multiple threads on the performance of the indexes.

In real life, the ratio of write and read operations of key-value (KV) store workloads usually changes over time. In this paper, we present a Dynamic wOrkload Pattern Aware LSM-based KV store (DOPA-DB), which supports dynamic compaction strategies depending on the workload pattern. In particular, DOPA-DB is a tiered LSM-based KV store with multiple key ranges, which enables varying compaction sizes. For write-intensive workloads, DOPA-DB can minimize write stalls while minimizing compaction overhead, and for read-intensive workloads, it can aggressively perform compaction to reduce the number of file accesses. Our preliminary experimental results show the potential benefits of dynamic compaction and provide insight into research directions for dynamic compaction strategies.

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

Many datasets in real life are complex and dynamic, that is, their key densities are varied over the whole key space and their key distributions change over time. It is challenging for an index structure to efficiently support all key operations for data management, in particular, search, insert, and scan, for such dynamic datasets. In this paper, we present DyTIS (Dynamic dataset Targeted Index Structure), an index that targets dynamic datasets. DyTIS, though based on the structure of Extendible hashing, leverages the CDF of the key distribution of a dataset, and learns and adjusts its structure as the dataset grows. The key novelty behind DyTIS is to group keys by the natural key order and maintain keys in sorted order in each bucket to support scan operations within a hash index. We also define what we refer to as a dynamic dataset and propose a means to quantify its dynamic characteristics. Our experimental results show that DyTIS provides higher performance than the state-of-the-art learned index for the dynamic datasets considered.

We propose Sage, a system for uncertain network analysis. Algorithms for uncertain network analysis require large amounts of memory and computing resources as they sample a large number of network instances and run analysis on them. Sage makes uncertain network analysis simple and efficient. By extending the edge-centric programming model, Sage makes writing sampling-based analysis algorithms as simple as writing conventional graph algorithms in Pregel-like systems. Moreover, Sage proposes four optimization techniques, namely, deterministic sampling, hybrid gathering, schedule-aware caching, and copy-on-write attributes, that exploit common properties of uncertain network analysis. Extensive evaluation of Sage with eight algorithms on six real-world networks shows that the four optimizations in Sage jointly improve performance by up to 13.9X and on average 2.7X.

No abstract available.

No abstract available.

No abstract available.

Various transactional systems use out-of-place up-dates such as logging or copy-on-write mechanisms to update data in a failure-atomic manner. Such out-of-place update methods double the I/O traffic due to back-up copies in the database layer and quadruple the I/O traffic due to the file system journaling. In mobile systems, transaction sizes of mobile apps are known to be tiny and transactions run at low concurrency. For such mobile transactions, legacy out-of-place update methods such as WAL are sub-optimal. In this work, we propose a crash consistent in-place update logging method - doubleheader logging (DHL) for SQLite. DHL prevents previous consistent records from being lost by performing a copy-on-write inside the database page and co-locating the metadata-only journal information within the page. This is done, in turn, with minimal sacrifice to page utilization. DHL is similar to when journaling is disabled, in the sense that it incurs almost no additional overhead in terms of both I/O and computation. Our experimental results show that DHL outperforms other logging methods such as out-of-place update write-ahead logging (WAL) and in-place update multi-version B-tree (MVBT).

The advent of persistent memory (PM) into our everyday computing environment is now imminent. New programming models and algorithms based on these models are being developed for such systems. However, current models require programs to be rewritten with persistence related primitives such as clflush and clwb or at least recompiled so that persistent mechanisms can be automatically inserted. This is a burden to program developers. Furthermore, executing legacy programs as-is can lead to application and system inconsistencies as unexpected faults occur. In this article, we propose µSnap, an operating system support that is based on checkpointing that allows legacy applications to be executed as-is without compromising consistency in systems that deploy PM. We implement a prototype of µSnap in the Linux kernel version 4.3.3, and measure and quantify the effect of µSnap for a wide range of applications. We find that µSnap incurs overhead for application execution compared to applications run without any notion of persistency, but that the overhead can be controlled to be minimal by appropriately setting the checkpointing interval. We argue that the benefit for paying this small cost can be tremendous in the sense that one can transparently guarantee the consistency of all legacy software written under the traditional programming model.

No abstract available.

This paper presents iDO, a compiler-directed approach to failure atomicity with nonvolatile memory. Unlike most prior work, which instruments each store of persistent data for redo or undo logging, the iDO compiler identifies idempotent instruction sequences, whose re-execution is guaranteed to be side-effect-free, thereby eliminating the need to log every persistent store. Using an extension of prior work on JUSTDO logging, the compiler then arranges, during recovery from failure, to back up each thread to the beginning of the current idempotent region and re-execute to the end of the current failure-atomic section. This extension transforms JUSTDO logging from a technique of value only on hypothetical future machines with nonvolatile caches into a technique that also significantly outperforms state-of-the art lock-based persistence mechanisms on current hardware during normal execution, while preserving very fast recovery times.

No abstract available.

The slotted-page structure is a database page format commonly used for managing variable-length records. In this work, we develop a novel "failure-atomic slotted page structure" for persistent memory that leverages byte addressability and durability of persistent memory to minimize redundant write operations used to maintain consistency in traditional database systems. Failure-atomic slotted paging consists of two key elements: (i) in-place commit per page using hardware transactional memory and (ii) slot header logging that logs the commit mark of each page. The proposed scheme is implemented in SQLite and compared against NVWAL, the current state-of-the-art scheme. Our performance study shows that our failure-atomic slotted paging shows optimal performance for database transactions that insert a single record. For transactions that touch more than one database page, our proposed slot-header logging scheme minimizes the logging overhead by avoiding duplicating pages and logging only the metadata of the dirty pages. Overall, we find that our failure-atomic slotted-page management scheme reduces database logging overhead to 1/6 and improves query response time by up to 33% compared to NVWAL.

The advent of Persistent Memory (PM), which is anticipated to have byte-addressable access latency in par with DRAM and yet nonvolatile, has stepped up interest in using PM as storage. Hence, PM storage targeted file systems are being developed under the premise that legacy file systems are suboptimal on memory bus attached PM-based storage. However, many years of time and effort are ingrained in legacy file systems that are now time-tested and mature. Simply scrapping them altogether may be unwarranted. In this paper, we look into how we can leverage the maturity ingrained in legacy file systems to the fullest, while, at the same time, reaping the high performance offered by PM. To this end, we first go through a thorough analysis of legacy Ext4 file systems, and compare it with NOVA, PMFS, and Ext4 with DAX extension, which are new PM file systems available in Linux. Based on these analyses, we then propose the Persistent Memory Adaptation Layer (PMAL) module that is lightweight (roughly 180 LoC) and can easily be integrated into legacy file systems to take advantage of PM storage. Using Ext4, we show that the performance of PMAL integrated Ext4 is in par with PM file systems for the Filebench and key-value store benchmarks.

Write amplification is a critical factor that limits the stable performance of flash-based storage systems. To reduce write amplification, this article presents a new technique that cooperatively manages data in flash storage and nonvolatile memory (NVM). Our scheme basically considers NVM as the cache of flash storage, but allows the original data in flash storage to be invalidated if there is a cached copy in NVM, which can temporarily serve as the original data. This scheme eliminates the copy-out operation for a substantial number of cached data, thereby enhancing garbage collection efficiency. Simulated results show that the proposed scheme reduces the copy-out overhead of garbage collection by 51.4% and decreases the standard deviation of response time by 35.4% on average. Measurement results obtained by implementing the proposed scheme in BlueDBM, 1 an open-source flash development platform developed by MIT, show that the proposed scheme reduces the execution time and increases IOPS by 2--21% and 3--18%, respectively, for the workloads that we considered. This article is an extended version of Lee et al. [2016], which was presented at the 32nd International Conference on Massive Data Storage Systems and Technology in 2016.

In cloud computing, multiple servers are consolidated into a physical machine in order to reduce the cost of deploying the servers. Guaranteeing the service level objective (SLO) of each server is one of the most important factors in a virtualization system. Particularly, isolating the I/O resources among VMs competing for a shared storage system is challenging. Recently, use of flash based Solid State Drives (SSDs) is being extended to enterprise systems. However, there are few studies for guaranteeing SLOs on such systems. In this paper, we empirically analyze the I/O behavior of a shared SSD. We show that performance SLOs of storage systems employing SSDs being shared by VMs or tasks are not satisfactory. We analyze and show that components of SSDs such as channels, DRAM buffer, and Native Command Queuing (NCQ) are the reasons behind this problem. Based on these analysis and observations, we propose two SSD-aware host level I/O schedulers that we call A+CFQ and H+BFQ, which are extensions of state-of-the-art I/O schedulers CFQ and BFQ, respectively. Through implementation and experiments on Linux, we show that the proposed I/O schedulers improve proportionality without sacrifice to performance.

As DRAM reaches its density limitation, various new memory technologies such as STT-RAM and PCM are emerging as contenders for next generation memory. As these new types of memory, which we refer to as New Memory (NM), are byte addressable and nonvolatile, they are anticipated to, partially or wholly, take on the role of main memory and storage. The goal of this study is to evaluate how the read/write latency gap between the DRAM and NM and the asymmetric read and write latency of NM will affect the performance of applications. To this end, using an in-house ARM based embedded system that allows us to individually adjust the read and write latency. First, we use controlled, synthetic workloads to evaluate the latency effects. The main finding here, among others, is that write latency has little effect on performance due to various hardware mechanisms employed in current cache hardware. We then run the Stream, LMbench and PARSEC 3.0 benchmarks that represent real life applications with various memory latency settings. We find that write latency has virtually no effect and the effect of read latency is limited only to applications with very low cache hit rates.

Write amplification is a critical factor that limits the stable performance of flash-based storage systems. To reduce write amplification, this paper presents a new technique that cooperatively manages data in flash storage and nonvolatile memory (NVM). Our scheme basically considers NVM as the cache of flash storage, but allows the original data in flash storage to be invalidated if there is a cached copy in NVM, which can temporarily serve as the original data. This scheme eliminates the copy-out operation for a substantial number of cached data, thereby enhancing garbage collection efficiency. Experimental results show that the proposed scheme reduces the copy-out overhead of garbage collection by 51.4% and decreases the standard deviation of response time by 35.4% on average.

This paper analyzes the host cache effectiveness in full virtualization, particularly associated with journaling of guests. We observe that the journal access of guests degrades cache performance largely due to the write-once access pattern and the frequent sync operations. To remedy this problem, we design and implement a novel caching policy, called PDC (Pollution Defensive Caching), that detects the journal accesses and prevents them from entering the host cache. The proposed PDC is implemented in QEMU-KVM 2.1 on Linux 4.14 and provides 3-32% performance improvement for various file and I/O benchmarks.

The move from SLC to MLC/TLC flash memory technology is increasing SSD capacity at lower cost, but at the cost of sacrificing reliability. An approach to remedy this loss is to employ the RAID architecture with the chips that comprise SSDs. However, using the traditional RAID approach may result in negative effects as the total number of writes is increased due to the parity updates. In this paper, we describe Elastic Striping and Anywhere Parity (eSAP)-RAID, a RAID scheme that allows flexible stripe sizes and parity placement. Using performance and lifetime models that we derive of SSDs employing RAID-5 and eSAP-RAID, we show that eSAP-RAID brings about significant performance and reliability benefits by reducing parity writes compared to RAID-5. We also implement these schemes in SSDs using DiskSim with SSD Extension and validate the models using realistic workloads. We also discuss policies such as dynamic stripe sizing and selective data protection that exploits the flexible nature of eSAP. We show that through such policies particular reliability enhancement goals can be met.

SSD based cache solutions are being widely utilized to improve performance in network storage systems. With a goal of providing a cost-effective, high performing SSD cache solution, we propose a new caching solution called SRC (SSD RAID as a Cache) for an array of commodity SSDs. In designing SRC, we borrow both the well-known RAID technique and the log-structured approach and adopt them into the cache layer. In so doing, we explore a wide variety of design choices such as flush issue frequency, write units, forming stripes without parity, and garbage collection through copying rather than destaging that become possible as we make use of RAID and a log-structured approach at the cache level. Using an implementation in Linux under the Device Mapper framework, we quantitatively present and analyze results of the design space options that we considered in our design. Our experiments using realistic workload traces show that SRC performs at least 2 times better in terms of throughput than existing open source solutions. We also consider cost-effectiveness of SRC with a variety of SSD products. In particular, we compare SRC configured with MLC and TLC SATA SSDs and a single high-end NVMe SSD. We find that SRC configured as RAID-5 with low-cost MLC and TLC SATA SSDs generally outperforms that configured with a single high-end SSD in terms of both performance and lifetime per dollars spent.

One characteristic of non-volatile memory (NVM) is that, even though it supports non-volatility, its retention capability is limited. To handle this issue, previous studies have focused on refreshing or advanced error correction code (ECC). In this paper, we take a different approach that makes use of the limited retention capability to our advantage. Specifically, we employ NVM as a file cache and devise a new scheme called amnesic cache management (ACM). The scheme is motivated by our observation that most data in a cache are evicted within a short time period after they have been entered into the cache, implying that they can be written with the relaxed retention capability. This retention relaxation can enhance the overall cache performance in terms of latency and energy since the data retention capability is proportional to the write latency. In addition, to prevent the retention relaxation from degrading the hit ratio, we estimate the future reference intervals based on the inter-reference gap (IRG) model and manage data adaptively. Experimental results with real-world workloads show that our scheme can reduce write latency by up to 40% (30% on average) and save energy consumption by up to 49% (37% on average) compared with the conventional LRU based cache management scheme.

As the market becomes competitive, SSD manufacturers are making use of multi-bit cell flash memory such as MLC and TLC chips in their SSDs. However, these chips have lower data retention period and endurance than SLC chips. With the reduced data retention period and endurance level, retention errors occur more frequently. One solution for these retention errors is to employ strong ECC to increase error correction strength. However, employing strong ECC may result in waste of resources during the early stages of flash memory lifetime as it has high reliability and data retention errors are rare during this period. The other solution is to employ data scrubbing that periodically refreshes data by reading and then writing the data to new locations after correcting errors through ECC. Though it is a viable solution for the retention error problem, data scrubbing hurts performance and lifetime of SSDs as it incurs extra read and write requests. Targeting data retention errors, we propose incremental redundancy (IR) that incrementally reinforces error correction capabilities when the data retention error rate exceeds a certain threshold. This extends the time before data scrubbing should occur, providing a grace period in which the block may be garbage collected. We develop mathematical analyses that project the lifetime and performance of IR as well as when using conventional data scrubbing. Through mathematical analyses and experiments with both synthetic and real workloads, we compare the lifetime and performance of the two schemes. Results suggest that IR can be a promising solution to overcome data retention errors of contemporary multi-bit cell flash memory. In particular, our study shows that IR can extend the maximum data retention period by 5 to 10 times. Additionally, we show that IR can reduce the write amplification factor by half under real workloads.

We present a new buddy system for memory allocation that we call the lazy iBuddy system. This system is motivated by two observations of the widely used lazy buddy system on multi-core systems. First, most memory requests are for single page frames. However, the lazy buddy algorithm used in Linux continuously splits and coalesces memory blocks for single page frame requests even though the lazy layer is employed. Second, on multi-core systems, responses to bursty memory requests are delayed by lock contention caused by concurrent accesses of the multi-cores. The lazy iBuddy system overcomes the first problem by managing each page frame individually and coalescing pages only when an allocation of multiple page frames is requested. We devise the lazy iBuddy algorithm so that single page frame allocation can be done in O(1). The second problem is alleviated by dividing main memory into multiple buddy spaces and applying a fine-grained locking mechanism. Performance evaluation results based on various workloads on the XEON 16core with 32 GB main memory show that the lazy iBuddy system can improve memory allocation/deallocation time by up to 47 percent with an average of 35 percent compared with the lazy buddy system for the various configurations that we considered.

As high performance NVM storage such as PCM and STT-RAM emerge, legacy software layers optimized for HDDs should be revisited. Specifically, as storage performance approaches DRAM performance, existing I/O mechanisms and software configurations should be reassessed. This paper explores the challenges and implications of using NVM storage with a broad range of experiments. We measure the performance of a system with NVM storage emulated by DRAM with proper timing parameters and compare it with that of HDD storage environments under various configurations. Our experimental results show that even with storage as fast as DRAM, the performance gain is not large for read operations as current I/O mechanisms do a good job of hiding the slow performance of HDD. To assess the potential benefit of fast storage media, we change various I/O configurations and perform experiments to quantify the effects of existing I/O mechanisms such as buffer caching, read-ahead, synchronous I/O, direct I/O, block I/O, and byte-addressable I/O on systems with NVM storage. We also investigate some unique performance characteristics of NVM in comparison with HDD by changing the number of accesses and the amount of data to be transferred. We anticipate that our results will provide directions in system software development in presence of ever faster storage devices.

Phase change memory (PCM) has emerged as one of the most promising technologies to incorporate into the memory hierarchy of future computer systems. However, PCM has two critical weaknesses to substitute DRAM memory in its entirety. First, the number of write operations allowed to each PCM cell is limited. Second, write access time of PCM is about 6–10 times slower than that of DRAM. To cope with this situation, hybrid memory architectures that use a small amount of DRAM together with PCM have been suggested. In this paper, we present a new memory management technique for hybrid PCM and DRAM memory architecture that efficiently hides the slow write performance of PCM. Specifically, we aim to estimate future write references accurately and then absorb frequent memory writes into DRAM. To do this, we analyze the characteristics of memory write references and find two noticeable phenomena. First, using write history alone performs better than using both read and write history in estimating future write references. Second, the frequency characteristic is a better estimator than temporal locality in predicting future memory writes. Based on these two observations, we present a new page replacement algorithm called CLOCK-DWF (CLOCK with Dirty bits and Write Frequency) that significantly reduces the number of write operations that occur on PCM and also increases the lifespan of PCM memory.

Journaling techniques are widely used in modern file systems as they provide high reliability and fast recovery from system failures. However, it reduces the performance benefit of buffer caching as journaling accounts for a bulk of the storage writes in real system environments. To relieve this problem, we present a novel buffer cache architecture that subsumes the functionality of caching and journaling by making use of nonvolatile memory such as PCM or STT-MRAM. Specifically, our buffer cache supports what we call the in-place commit scheme. This scheme avoids logging, but still provides the same journaling effect by simply altering the state of the cached block to frozen. As a frozen block still provides the functionality of a cache block, we show that in-place commit does not degrade cache performance. We implement our scheme on Linux 2.6.38 and measure the throughput and execution time of the scheme with various file I/O benchmarks. The results show that our scheme improves the throughput and execution time by 89% and 34% on average, respectively, compared to the existing Linux buffer cache with ext4 without any loss of reliability.

We propose a novel kernel-level memory allocator, called M3 (M-cube, Multi-core Multi-bank Memory allocator), that has the following two features. First, it introduces and makes use of a notion of a memory container, which is defined as a unit of memory that comprises the minimum number of page frames that can cover all the banks of the memory organization, by exclusively assigning a container to a core so that each core achieves bank parallelism as much as possible. Second, it orchestrates page frame allocation so that pages that threads access are dispersed randomly across multiple banks so that each thread's access pattern is randomized. The development of M3 is based on a tool that we develop to fully understand the architectural characteristics of the underlying memory organization. Using an extension of this tool, we observe that the same application that accesses pages in a random manner outperforms one that accesses pages in a regular pattern such as sequential or same ordered accesses. This is because such randomized accesses reduces inter-thread access interference on the row-buffer in memory banks. We implement M3 in the Linux kernel version 2.6.32 on the Intel Xeon system that has 16 cores and 32GB DRAM. Performance evaluation with various workloads show that M3 improves the overall performance for memory intensive benchmarks by up to 85% with an average of about 40%.

While the move from SLC to MLC/TLC flash memory technology is increasing SSD capacity at lower cost, it is being done at the cost of sacrificing reliability. An approach to remedy this loss is to employ the RAID architecture with the chips that comprise SSDs. However, using the traditional RAID approach may result in negative effects as the total number of writes may increase due to the parity updates, consequently leading to increased P/E cycles and higher bit error rates. Using a technique that we call Elastic Striping and Anywhere Parity (eSAP), we develop eSAP-RAID, a RAID scheme that significantly reduces parity writes while providing reliability better than RAID-5. We derive performance and lifetime models of SSDs employing RAID-5 and eSAP-RAID that show the benefits of eSAP-RAID. We also implement these schemes in SSDs using DiskSim with SSD Extension and validate the models using realistic workloads. Our results show that eSAP-RAID improves reliability considerably, while limiting its wear. Specifically, the expected lifetime of eSAP-RAID employing SSDs may be as long as current ECC based SSDs, while its reliability level can be maintained at the level of the early stages of current ECC based SSDs throughout its entire lifetime.

As the market becomes more competitive, SSD manufacturers are moving from SLC (Single-Level Cell) to MLC (Multi-Level Cell) flash memory chips that store two bits per cell as building blocks for SSDs. Recently, TLC chips, which store three bits per cell, is being considered as a viable solution due to their low cost. However, performance and lifetime of TLC chips are considerably limited and thus, pure TLC-based SSDs may not be viable as a general storage device. In this paper, we propose a hybrid SSD solution, namely HySSD, where SLC and TLC chips are used together to form an SSD solution performing in par with SLC-based products. Based on an analytical model, we propose a near optimal data distribution scheme that distributes data among the SLC and TLC chips for a given workload such that performance or lifetime may be optimized. Experiments with two types of SSDs both based on DiskSim with SSD Extension show that the analytic model approach can dynamically adjust data distribution as workloads evolve to enhance performance or lifetime.

Recently, interest in incorporating Storage Class Memory (SCM), which blurs the distinction between memory and storage, into mainstream computing has been increasing rapidly. In this paper, we address the emerging questions regarding the use of SCM. Based on an embedded platform that employs FeRAM, a type of SCM, we present our findings. In summary, by introducing SCM, power efficiency improves while performance is degraded. We also show that such performance degradations may be removed with operating system level schemes that fully exploit the characteristics of SCM. Finally, we present permanent computing that supports lightweight system on/off capabilities by using SCM.

In order to reduce the energy dissipation in main memory of computer systems, phase change memory (PCM) has emerged as one of the most promising technologies to incorporate into the memory hierarchy. However, PCM has two critical weaknesses to substitute DRAM memory in its entirety. First, the number of write operations allowed to each PCM cell is limited. Second, write access time of PCM is about 6-10 times slower than that of DRAM. To cope with this situation, hybrid memory architectures that use a small amount of DRAM together with PCM memory have been suggested. In this paper, we present a new memory management technique for hybrid PCM and DRAM memory architecture that efficiently hides the slow write performance of PCM. Specifically, we aim to estimate future write references accurately and then absorb most memory writes into DRAM. To do this, we analyze the characteristics of memory write references and find two noticeable phenomena. First, using write history alone performs better than using both read and write history in estimating future write references. Second, the frequency characteristic is a better estimator than temporal locality but combining these two properties appropriately leads to even better results. Based on these two observations, we present a new page replacement algorithm called CLOCK-DWF (CLOCK with Dirty bits and Write Frequency) that significantly reduces the number of write operations that occur on PCM.

We explore the possibility of deploying storage class memory (SCM) into the I/O path as a file system metadata store and examine what effects it has on the performance of portable computing systems. In this regard, we develop a new flash memory-based file system that stores all metadata in SCM, while storing all file data in flash memory. In so doing, we make two contributions in this work. First, we present a model that analyzes the amount of SCM that is needed for specific flash memory storage capacity. Second, we present quantitative experimental results that show how much performance gains are possible by exploiting SCM in terms of I/O performance, energy efficiency and lifetime of the underlying flash memory. Compared to YAFFS, a popular flash memory-based file system, we show that system performance is improved by a maximum of around 320, 260, and 180% in terms of I/O performance, energy efficiency and lifetime of the Flash memory, respectively, for the realistic workloads that we considered.

NAND flash memory based storage such as SSDs is gaining popularity in commodity computer systems. Some low-end SSDs use the block mapping FTL (Flash Translation Layer) that is good for sequential write patterns but poor for random ones. On the other hand, high-end SSDs tend to use the page mapping FTL that is effective for random write patterns, but whose performance degrades after successive random writes. Designing an FTL that adapts to various workload patterns and provides long-term stable performance is a challenging issue. To resolve this issue, we propose a new FTL, which we call Janus-FTL, that provides a spectrum between the block and page mapping schemes. By adapting along the spectrum, Janus-FTL can provide long-term superior write performance for various workload patterns. We also present a cost model of Janus-FTL that shows the existence of the optimal point on the spectrum for a given workload. Our experimental results show the superiority of Janus-FTL, which adapts itself along the spectrum for a given workload, over state-of-the-art hybrid mapping FTLs and the pure page mapping FTL

Solid State Drives (SSDs) are now becoming a part of main stream computers. Even though disk scheduling algorithms and file systems of today have been optimized to exploit the characteristics of hard drives, relatively little attention has been paid to model and exploit the characteristics of SSDs. In this paper, we consider the use of SSDs from the file system standpoint. To do so, we derive a performance model for the SSDs. Based on this model, we devise a file system space allocation scheme, which we call Greedy-Space, for block or hybrid mapping SSDs. From the Postmark benchmark results, we observe substantial performance improvements when employing the Greedy-Space scheme in ext3 and Reiser file systems running on three SSDs available in the market.

Even though the Log-structured File System (LFS) has elegant concept for superior write performance, it suffers from cleaning overhead. Specifically, when file system utilization is high and the system is busy, write performance of LFS degenerates significantly. Also, cascading update of meta-data triggered by modification of file data decreases LFS performance further. To overcome the performance drawbacks of LFS, we propose two schemes, namely Slack Space Recycling (SSR) and Lazy Indirect Block Update (LIBU). The SSR scheme writes modified data to invalid areas of used segments when on-demand cleaning is inevitable to serve incoming write requests. Also, the LIBU scheme accumulates meta-data update in memory beyond multiple segment writes without compromising consistency so as to decrease total amount of writes. From various experimental results, we observe significant performance improvements when employing the SSR and LIBU schemes for a wide utilization range.

In embedded systems and laptops, flash memory storage such as SSDs (Solid State Drive) have been gaining popularity due to its low energy consumption and durability. As SSDs are flash memory based devices, their performance behavior differs from those of magnetic disks. However, little attention has been paid on how to exploit SSDs from the disk scheduling algorithm view point. In this paper, we first describe behaviors of SSDs that inspires us to design a new disk scheduler for the Linux operating system. Specifically, read service time is almost constant in an SSD while write service time is not. Moreover, appropriate grouping of write requests eliminates any ordering-related restrictions and also maximizes write performance. From these observations, we propose two disk schedulers: IRBW-FIFO and IRBW-FIFO-RP. Both schedulers arrange write requests into bundles of an appropriate size while read requests are independently scheduled. Then, the IRBW-FIFO scheduler provides complete FIFO ordering to each bundle of write requests and each individual read requests while the IRBW-FIFO-RP scheduler gives higher priority to read requests than the bundles of write requests. We implement these schedulers in Linux 2.6.23, and results of executing our set of benchmark programs shows that performance improvements of up to 17% compared to existing Linux disk schedulers are achieved.

MEMS-based storage is foreseen as a promising storage media that provides high-bandwidth, low-power consumption, high-density, and low cost. Due to these versatile features, MEMS storage is anticipated to be used for a wide range of applications from storage for small handheld devices to high capacity mass storage servers. However, MEMS storage has vastly different physical characteristics compared to a traditional disk. First, MEMS storage has thousands of heads that can be activated simultaneously. Second, the media of MEMS storage is a square structure which is different from the platter structure of disks. This article presents a new request scheduling algorithm for MEMS storage called P-SPTF that makes use of the aforementioned characteristics. P-SPTF considers the parallelism of MEMS storage as well as the seek time of requests on the two dimensional square structure. We then present another algorithm called PA-SPTF that considers the aging factor so that starvation resistance is improved. Simulation studies show that PA-SPTF improves the performance of MEMS storage by up to 39.2% in terms of the average response time and 62.4% in terms of starvation resistance compared to the widely acknowledged SPTF algorithm. We also show that there exists a spectrum of scheduling algorithms that subsumes both the P-SPTF and PA-SPTF algorithms.

Flash memory storage has been widely used in various embedded systems such as digital cameras, MP3 players, cellular phones, and DMB devices and now it applies to PCs as a form of SSDs. Characteristics of Flash memory necessitate a software layer called FTL (Flash Translation Layer) that directs modified data to new places in Flash memory and maintains a mapping between a logical sector number to a physical page. We notice that this out-of-place update scheme of the FTL allows a low-overhead time-shifting between multiple versions of storage state. From this observation, we propose LTFTL (Lightweight Time-shift FTL) that provides not only multiple versions of storage state but also an open-ended interface to traverse them. This open-ended interface can be used to support fault-resilience schemes, transactions of various granularities, and user-friendly roll-back services. Experimental results from a prototype implementation show that the proposed LTFTL can (1) provide a low-overhead time-shift capability at the user level by maintaining multiple storage states and (2) enhance the reliability/survivability of Flash memory by allowing to roll back to a previous consistent storage state at the storage system level.

Flash memory is a storage medium that is becoming more and more popular. Though not yet fully embraced in traditional computing systems, Flash memory is prevalent in embedded systems, materialized as commodity appliances such as the digital camera and the MP3 player that we enjoy in our everyday lives. This paper considers an issue in file systems that use Flash memory as a storage medium and makes the following two contributions. First, we identify the cost of block cleaning as the key performance bottleneck for Flash memory analogous to the seek time in disk storage. We derive and define three performance parameters, namely, utilization, invalidity, and uniformity, from characteristics of Flash memory and present a formula for block cleaning cost based on these parameters. We show that, of these parameters, uniformity most strongly influences the cost of cleaning and that uniformity is a file system controllable parameter. This leads us to our second contribution, designing the modification-aware (MODA) page allocation scheme and analyzing how enhanced uniformity affects the block cleaning cost with various workloads. Real implementation experiments conducted on an embedded system show that the MODA scheme typically improves 20 to 30% in cleaning time compared to the traditional sequential allocation scheme that is used in YAFFS.

Non-volatile RAM (NVRAM) such as PRAM (Phase-change RAM), FeRAM (Ferroelectric RAM), and MRAM (Magnetoresistive RAM) has characteristics of both non-volatile storage and random access memory (RAM). These forms of NVRAM are currently being developed by major semiconductor companies and are expected to be an everyday component in the near future. The advent of NVRAM may possibly bring about drastic changes to the system software landscape. In this work, we develop a new Flash memory based file system that exploits NVRAM in order to improve system performance. Specifically, we discuss the initial design and implementation of a file system that stores all metadata in NVRAM, while storing all file data in Flash memory. In so doing, we make two contributions in this work. First, we present a model that analyzes the amount of NVRAM that is needed for specific Flash memory storage capacity. Experimentally, we verify that this model represents the exact NVRAM usage in the realistic environment. Second, we present quantitative experimental results that show how much performance gains are possible by exploiting NVRAM. Compared to YAFFS, a popular Flash memory based file system, we show that this file system requires only minimal time for mounting and that the execution time improves by a maximum of 600% and an average of 437% for the realistic workloads that we considered.

Flash memory has many merits such as light weight, shock resistance, and low power consumption, but also has limitations like the erase-before-write property. To overcome such limitations and to use it efficiently as storage media in mobile systems, Flash memory based storage systems require special address mapping software called the FTL (Flash-memory Translation Layer). Like cleaning in Log-structured file system (LFS), the FTL often performs a merge operation for block recycling and its efficiency affects the performance of the storage system. To reduce the block recycling costs in NAND Flash memory based storage, we introduce another block recycling scheme that we call migration. Our cost-models and experimental results show that cost-based selection of merge or migration for each block recycling can decrease block recycling costs and, therefore, improve performance of Flash memory based storage systems. Also, we derive the macroscopic optimal migration/merge sequence minimizing block recycling costs for each migration/merge combination period. Experimental results show that the performance of Flash memory based storage can be further improved by the macroscopic optimization than the simple cost-based selection.

MEMS-based storage is being developed as a new storage media. Due to its attractive features such as high-bandwidth, low-power consumption, and low cost, MEMS storage is anticipated to be used for a wide range of applications. However, MEMS storage has vastly different physical characteristics compared to a traditional disk. First, MEMS storage has thousands of heads that can be activated simultaneously. Second, the media of MEMS storage is a square structure which is different from the platter structure of disks. This paper presents a new request scheduling algorithm for MEMS storage that makes use of the aforementioned characteristics. This new algorithm considers the parallelism of MEMS storage as well as the seek time on the two dimensional square structure. We then extend this algorithm to consider the aging factor so that starvation resistance is improved. Simulation studies show that the proposed algorithms improve the performance of MEMS storage by up to 39.2% in terms of the average response time and 62.4% in terms of starvation resistance compared to the widely acknowledged SPTF (Shortest Positioning Time First) algorithm.

A new buffer replacement scheme, called DEAR (detection-based adaptive replacement), is presented for effective caching of disk blocks in the operating system. The proposed DEAR scheme automatically detects block reference patterns of applications and applies different replacement policies to different applications depending on the detected reference pattern. The detection is made by a periodic process and is based on the relationship between block attribute values, such as backward distance and frequency gathered in a period, and the forward distance observed in the next period. This paper also describes an implementation and performance measurement of the DEAR scheme in FreeBSD. The results from performance measurements of several real applications show that, compared with the LRU scheme, the proposed scheme reduces the number of disk I/Os by up to 51 percent, and the response time by up to 35 percent in the case of single application executions. For multiple application executions, the results show that the proposed scheme reduces the number of disk I/Os by up to 20 percent and the overall response time by up to 18 percent.

Efficient and effective buffering of disk blocks in main memory is critical for better file system performance due to a wide speed gap between main memory and hard disks. In such a buffering system, one of the most important design decisions is the block replacement policy that determines which disk block to replace when the buffer is full, In this paper, we show that there exists a spectrum of block replacement policies that subsumes the two seemingly unrelated and independent Least Recently Used (LRU) and Least Frequently Used (LFU) policies. The spectrum is called the LRFU (Least Recently/Frequently Used) policy and is formed by how much more weight we give to the recent history than to the older history. We also show that there is a spectrum of implementations of the LRFU that again subsumes the LRU and LFU implementations. This spectrum is again dictated by how much weight is given to recent and older histories and the time complexity of the implementations lies between O(1) (the time complexity of LRU) and O(log(2) n) (the time complexity of LFU), where n is the number of blocks in the buffer, Experimental results from trace-driven simulations show that the performance of the LRFU is at least competitive with that of previously known policies for the workloads we considered.

Two contributions are made in this paper. First, we show that system level characterization of file block references is inadequate for maximizing buffer cache performance. We show that a finer-grained characterization approach is needed. Though application level characterization methods have been proposed, this is the first attempt, to the best of our knowledge, to consider file level characterizations. We propose an Application/File-level Characterization (AFC) scheme where we detect on-line the reference characteristics at the application level and then at the file level, if necessary. The results of this characterization are used to employ appropriate replacement policies in the buffer cache to maximize performance. The second contribution is in proposing an efficient and fair buffer allocation scheme. Application or file level resource management is infeasible unless there exists an allocation scheme that is efficient and fair. We propose the ΔHIT allocation scheme that takes away a block from the application/file where the removal results in the smallest reduction in the number of expected buffer cache hits. Both the AFC and ΔHIT schemes are on-line schemes that detect and allocate as applications execute. Experiments using trace-driven simulations show that substantial performance improvements can be made. For single application executions the hit ratio increased an average of 13 percentage points compared to the LRU policy, with a maximum increase of 59 percentage points, while for multiple application executions, the increase is an average of 12 percentage points, with a maximum of 32 percentage points for the workloads considered.

A software RAID file system is defined as a system that distributes data redundantly across an array of disks attached to each of the workstations connected to a high-speed network. This configuration provides higher throughput and availability compared to conventional file systems. In this paper, we consider two specific issues, namely the distribution of data among the cluster (i.e. striping) and buffer caching for such an environment. Through simulation studies, we compare the performance of various striping methods and show that, for effective striping in software RAID file systems, we must take advantage of its flexible nature. Furthermore, for buffer caching, we show that conventional caching schemes that have been developed for distributed systems are insufficient, and that the ExODP (Exclusively Old Data and Parity) scheme, which is presented in this paper, overcomes the limitations of the previously proposed schemes.

AbstractÐEfficient and effective buffering of disk blocks in main memory is critical for better file system performance due to a wide speed gap between main memory and hard disks. In such a buffering system, one of the most important design decisions is the block replacement policy that determines which disk block to replace when the buffer is full. In this paper, we show that there exists a spectrum of block replacement policies that subsumes the two seemingly unrelated and independent Least Recently Used (LRU) and Least Frequently Used (LFU) policies. The spectrum is called the LRFU (Least Recently/Frequently Used) policy and is formed by how much more weight we give to the recent history than to the older history. We also show that there is a spectrum of implementations of the LRFU that again subsumes the LRU and LFU implementations. This spectrum is again dictated by how much weight is given to recent and older histories and the time complexity of the implementations lies between O(1) (the time complexity of LRU) and O…log 2 n† (the time complexity of LFU), where n is the number of blocks in the buffer. Experimental results from trace-driven simulations show that the performance of the LRFU is at least competitive with that of previously known policies for the workloads we considered. Index TermsÐBuffer cache, LFU, LRU, replacement policy, trace-driven simulation. 1

This paper proposes a prefetch-based disk buffer management algorithm, which we call W²R (Weighing/Waiting Room). Instead of using elaborate prefetching schemes to decide which block to prefetch and when, we simply follow the LRU-OBL (One Block Lookahead) approach and prefetch the logical next block along with the block that is being referenced. The basic difference is that the W²R algorithm logically partitions the buffer into two rooms, namely the Weighing Room and the Waiting Room. The referenced, hence fetched block is placed in the Weighing Room, while the prefetched logical next block is placed in the Waiting Room. By so doing, we alleviate some inherent deficiencies of blindly prefetching the logical next block of a referenced block. Specifically, a prefetched block that is never used may replace a possibly valuable block and a prefetched block, though referenced in the future, may replace a block that is used earlier than itself. Using the DB2 and OLTP traces, we show t...