CPU computations and I/O operations are fundamental to data storage systems. Storage systems conduct computations with their user threads, such as sorting data for orderliness. They handle I/Os through system calls (syscalls) including file write, read, and fsync, which the OS’s kernel threads perform with storage devices.

Databases widely adopt the technique of logging for durability and consistency, while it introduces severe performance overhead. Efforts to mitigate the logging overhead include optimizing the fsync syscall and using preallocated log files with fdatasync to persist necessary data only. Additionally, hardware advancements like power loss protection (PLP) in modern solid-state drives (SSDs) have reduced the time cost for each I/O operation at the hardware level. Yet, logging I/Os still bottleneck many databases like OceanBase due to the traversal through multiple software layers that jointly impose a significant software tax. In this paper, we find that preal-location establishes a log file's stable structure, minimizing the likelihood of space reallocations and permission changes. Leveraging this, we propose Éxitos, which reorganizes the in-memory offset-to-block mapping per log file for quick lookups and creates a direct I/O path from database to SSD, bypassing most of the software layers. Implemented with eBPF on an NVMe SSD, Éxitos improves the performance of OceanBase by up to 2.3× with write-intensive workloads.

CPU frequency scaling is widely employed to dynamically adjust the speed and voltage of CPU cores in real time, aiming to achieve both high performance and power efficiency. Prior work indicates that variations in CPU frequency can leak information about the workload being processed. We find that the performance of I/O requests---such as file I/Os on a fast storage device---is affected by runtime changes in CPU frequency and, in turn, reflects the behavior of the ongoing workload. Accordingly, we develop IOLeak, a new side channel based on CPU frequency scaling that does not require direct access to the CPU frequency. We first construct an IOLeak covert channel by detecting I/O latency online for secretive communication, both in noisy and noise-free environments. Next, we leverage IOLeak to launch stealthy attacks, such as extracting cryptographic keys and fingerprinting websites, and confirm that IOLeak successfully leaks information through file I/Os.

Today, hardware accelerators are being deployed in cloud and edge computing to serve DNN inference jobs that multiple tenants keep issuing. The use of heterogeneous multi-core accelerator systems has been considered. The intricate nature of one such system and the dynamicity of multi-tenant jobs over time yet make the scheduling a complex problem. In this paper, we study layer fusion techniques and propose a new scheduling algorithm named Lucas. Lucas aims to maximally meet the Quality of Service (QoS) requirements for all tenants when mapping their inference jobs onto heterogeneous accelerators. After breaking DNN layers into fine-grained units, Lucas online decides whether to perform multi-core layer fusion, single-core layer fusion, or layer-by-layer execution regarding factors such as the memory bandwidth consumption, the layers awaiting execution, and the cost of layer fusion. Evaluation shows that, compared to state-of-the-art schedulers, Lucas achieves significantly higher Service Level Agreement (SLA) compliance across various workloads.

The ever-increasing demand for matrix multiplication in artificial intelligence (AI) and generic computing emphasizes the necessity of efficient computing power accommodating both floating-point (FP) and quantized integer (QINT). While state-of-the-art bit-sparsity-aware acceleration techniques have demonstrated impressive performance and efficiency in neural networks through software-driven methods such as pruning and quantization, these approaches are not always feasible in typical generic computing scenarios. In this paper, we propose Bit-Cigma, a hardware-centric architecture that leverages bit-sparsity to accelerate generic matrix multiplication. Bit-Cigma features (1) CCSD encoding, an optimized on-chip sparsification technique based on canonical signed digit (CSD) representation; (2) segmented dot product, a multi-stage exponent matching technique for long FP vectors; and (3) the versatility to efficiently process both FP and QINT data types. CCSD encoding halves the cost of CSD encoding while achieving optimal bit-sparsity, and segmented dot product improves both accuracy and throughput. Bit-Cigma cores are implemented using 65 nm technology at 1 GHz, demonstrating substantial gains in performance and efficiency for both FP and QINT configurations. Compared to state-of-the-art Bitlet, Bit-Cigma achieves 3.2$\boldsymbol{\times}$performance, 6.1$\boldsymbol{\times}$area efficiency, and 15.3$\boldsymbol{\times}$energy efficiency when processing FP32 data while ensuring zero computing error.

Graph neural networks (GNNs) gain wide popularity. Large graphs with high-dimensional features become common and training GNNs on them is non-trivial on an ordinary machine. Given a gigantic graph, even sample-based GNN training cannot work efficiently, since it is difficult to keep the graph’s entire data in memory during the training process. Leveraging a solid-state drive (SSD) or other storage devices to extend the memory space has been studied in training GNNs. Memory and I/Os are hence critical for effectual disk-based training. We find that state-of-the-art (SoTA) disk-based GNN training systems severely suffer from issues like the memory contention between a graph’s topological and feature data, and severe I/O congestion upon loading data from SSD for training. We accordingly develop GNNDrive. GNNDrive 1) minimizes the memory footprint with holistic buffer management across sampling and extracting, and 2) avoids I/O congestion through a strategy of asynchronous feature extraction. It also avoids costly data preparation on the critical path and makes the most of software and hardware resources. Experiments show that GNNDrive achieves superior performance. For example, when training with the Papers100M dataset and GraphSAGE model, GNNDrive is faster than SoTA PyG+, Ginex, and MariusGNN by 16.9 ×, 2.6 ×, and 2.7 ×, respectively.

Persistent memory (pmem) products bring the persistence domain up to the memory level. Intel recently introduced the eADR feature that guarantees to flush data buffered in CPU cache to pmem on a power outage, thereby making the CPU cache a transient persistence domain . Researchers have explored how to enable the atomic durability for applications’ in-pmem data. In this article, we exploit the eADR-supported CPU cache to do so. A modified cache line, until written back to pmem, is a natural redo log copy of the in-pmem data. However, a write-back due to cache replacement or eADR on a crash overwrites the original copy. We accordingly developed Hercules, a hardware logging design for the transaction-level atomic durability, with supportive components installed in CPU cache, memory controller (MC), and pmem. When a transaction commits, Hercules commits on-chip its data staying in cache lines. For cache lines evicted before the commit, Hercules asks the MC to redirect and persist them into in-pmem log entries and commits them off-chip upon committing the transaction. Hercules lazily conducts pmem writes only for cache replacements at runtime. On a crash, Hercules saves metadata and data for active transactions into pmem for recovery. Experiments show that, by using CPU cache for both buffering and logging, Hercules yields much higher throughput and incurs significantly fewer pmem writes than state-of-the-art designs.

Computer architecture keeps evolving to support the byte-addressable non-volatile memory (NVM). Researchers have tailored the prevalent B+-tree with NVM, crafting a history of utilizing architectural supports to gain both high performance and crash consistency. The latest architecture-level changes for NVM, e.g., the eADR, motivate us to further explore architectural implications in the design and implementation of in-NVM B+-tree. Our quantitative study finds that eADR makes the cache misses impact increasingly on an in-NVM B+-tree's performance. We hence propose Conan for the conflict-aware node allocation based on theoretical justifications. Conan decomposes the virtual addresses of B+-tree nodes regarding a VIPT cache and intentionally places them into different cache sets. Experiments show that Conan evidently reduces cache conflicts and boosts the performance of state-of-the-art in-NVM B+-tree.

Applications memory-map file data stored in the persistent memory and expect both high performance and fail-ure atomicity. State-of-the-art NOVA and Libnvmmio guarantee failure atomicity but yield inferior performance. They enforce data staying fresh and intact at the mapped addresses by continually updating the data there, thereby incurring severe write amplifications. They also lack the adaptability to dynamic workloads and entail housekeeping overheads with complex designs. We hence propose Acumen with a group of reflection pages managed for a mapped file. Using a simplistic bitmap to track fine-grained data slices, Acumen makes a reflection page and a mapped file page pair to alternately carry updates to achieve failure atomicity. Only on receiving a read request will it deploy valid data from reflection pages into target mapped file pages. The cost of deployment is amortized over subsequent read requests. Experiments show that Acumen significantly outperforms NOVA and Libnvmmio with consistently higher performance in serving a variety of workloads.

Write-ahead logging (WAL) is widely utilized to ensure data’s integrity for data storage systems. Modified data is firstly written to a WAL file. Then data is persistently flushed to original home location for in-place update. These two steps are referred to as commit and checkpoint. In this paper, we take SQLite in the WAL mode to study the impact of checkpoint. Once 1,000 pages accumulate in the WAL file, SQLite checkpoints them to the database file with fsync. Such a periodical checkpoint fashion causes substantial spikes to the user-facing latency of inserting or updating data over time. Also, the fixed checkpoint frequency of every 1,000 pages does not consider the runtime write/read access pattern. We propose an algorithm named Walack. Walack conducts fsync asynchronously for each checkpoint. By observing write and read requests, it online adjusts the checkpoint frequency. These two strategies jointly enable Walack to gain both high performance and space efficiency. Experiments show that Walack reduces the user-facing tail latency by up to 92.3% for write requests, with both average write and read performances retained.

B+-tree has been an important index structure since the era of hard disks. The next-generation non-volatile memory (NVM) is striding into computer systems as a new tier as it incorporates both DRAM's byte-addressability and disk's persistency. Researchers and practitioners have considered building persistent memory by placing NVM on the memory bus for CPU to directly load and store data. As a result, cache-friendly data structures, such as the B+-tree, have been developed for NVM. State-of-the-art in-NVM B+-trees mainly focus on the optimization of write operations (insertion and deletion). How-ever, search is of paramount importance for B+-tree. Not only search-intensive workloads benefit from an optimized search, but insertion and deletion also rely on a preceding search operation to proceed. In this paper, we attentively study a sorted B+-tree node that spans over contiguous cache lines. Such cache lines exhibit a monotonically increasing trend and searching a target key across them can be accelerated by estimating a range the key falls into. To do so, we construct a probing Sentinel Array in which a sentinel stands for each cache line of B+-tree node. Checking the Sentinel Array avoids scanning unnecessary cache lines and hence significantly reduces cache misses for a search. A quantitative evaluation shows that using Sentinel Arrays boosts the search performance of state-of-the-art in-NVM B+-trees by up to 48.4 % while the cost of maintaining of Sentinel Array is low.

Solid-state drives (SSDs) are gaining popularity. Meanwhile, key-value stores built on log-structured merge-tree (LSM-tree) are widely deployed for data management. LSM-tree frequently calls syncs to persist newly-generated files for crash consistency. The blocking syncs are costly for performance. We revisit the necessity of syncs for LSM-tree. We find that Ext4 journaling embraces asynchronous commits to implicitly persist files. Hence, we design NobLSM that makes LSM-tree and Ext4 cooperate to substitute most syncs with non-blocking asynchronous commits, without losing consistency. Experiments show that NobLSM significantly outperforms state-of-the-art LSM-trees with higher throughput on an ordinary SSD.

Several B+-tree variants have been developed to exploit the byte-addressable non-volatile memory (NVM). We attentively investigate the properties of B+-tree and find that, a conventional B+-tree node is a linear structure in which key-value (KV) pairs are maintained from the zero offset of a node. These KV pairs are shifted in a unidirectional fashion for insertions and deletions. Inserting and deleting one KV pair may inflict a large amount of write amplifications due to shifting existing KV pairs. This badly impairs the performance of in-NVM B+-tree. In this article, we propose a novel circular design for B+-tree. With regard to NVM's byte-addressability, our Circ-Tree embraces tree nodes in a circular structure without a fixed base address, and bidirectionally shifts KV pairs for insertions and deletions to minimize write amplifications. We have implemented a prototype for Circ-Tree and conducted extensive experiments. Experimental results show that Circ-Tree significantly outperforms two state-of-the-art in-NVM B+-tree variants, i.e., NV-tree and FAST+FAIR, by up to 1.6× and 8.6×, respectively, in terms of write performance. The end-to-end comparison by running YCSB to KV stores built on NV-tree, FAST+FAIR, and Circ-Tree reveals that Circ-Tree yields up to 29.3 and 47.4 percent higher write performance, respectively, than NV-tree and FAST+FAIR.

The recent rise in complex Wi-Fi vulnerabilities, such as KRACK and Dragonslayer, indicates the critical need for effective Wi-Fi protocol testing tools. In this article, we conceptualize, design and implement a directed fuzzing methodology namedGreyhoundthat automatically tests the Wi-Fi client implementations against vulnerabilities such as crashes or non-compliant behaviors. Leveraging a holistic Wi-Fi protocol model,Greyhounddirects the fuzzer in specific states of target Wi-Fi client. By exchanging mutated packets with a Wi-Fi client,Greyhoundaims to induce the client to exhibit anomalous behaviors that badly deviate from Wi-Fi protocols. We have implementedGreyhoundand evaluated it on a variety of real-world Wi-Fi clients, including smartphone, Raspberry Pi, IoT device microcontrollers and a medical device. Our evaluation indicates thatGreyhoundnot only automatically discovers known vulnerabilities (including KRACK and Dragonslayer) that would require specialized verification otherwise, but, more importantly, it also has uncovered four new vulnerabilities in popular Wi-Fi client devices. All discovered vulnerabilities have been confirmed by manufacturers and they have been assigned three different common vulnerability exposure (CVE) IDs. We also win a bug bounty of 2,200 USD for discovering the security vulnerabilities. Furthermore, our evaluation with three existing Wi-Fi fuzz testing tools reveals that all such tools fail to discover any of the vulnerabilities (including crashes) uncovered byGreyhound. Last but not the least, we have deployedGreyhoundto test the Wi-Fi client implementation on automotive head units.Greyhoundautomatically discovers KRACK, Dragonslayer and other anomalies in these Wi-Fi implementations. Such a real world try-out justifies the necessity and efficacy ofGreyhound.

Byte-addressable non-volatile memory (NVM) is to reshape computer systems. Researchers have proposed crash-consistent in-NVM Bs+-trees with unsorted or sorted nodes to store key-value (KV) pairs. However, they still yield suboptimal performance: inserting a KV pair into a sorted node shifts numerous KV pairs that may cause multiple cache lines to be flushed, while to search a KV pair in an unsorted node is inefficient. In this paper, we propose Isle-Tree. Each cache line of Isle-Tree's leaf node is sorted while the node is unsorted. For most insertions/deletions, Isle-Tree flushes only one cache line of KV pairs. For searches, sorted cache lines help Isle-Tree avoid unnecessary comparisons. Experiments show that Isle-Tree yields high performance for all insertions, deletions and searches.

Summary Adversaries can compute the secret information of a program, such as the key for encryption routines, from side channels in the light of timing‐based and access‐based CPU cache behaviours. As a result, it is crucial to understand whether a program is vulnerable to side‐channel cache leakage or not. Yet how we can find out such a vulnerability in a program remains a problem. In this paper, we revisit this problem and contemplate a test‐generation methodology, which, in both timing‐based and access‐based dimensions, systematically discovers the cache side‐channel leakage of an arbitrary software program. At the core of our test‐generation framework is an algorithm that explores the program's input space and adapts at runtime according to observed cache performance in the executed tests. We have implemented our test generator for timing‐based and access‐based attack tests and evaluated it with open‐source subject programs, including ones from OPENSSL and Linux GDK libraries. Our extensive evaluation effectively discloses the vulnerabilities of these real‐world software to both timing‐based and access‐based cache attacks. We also empirically show that our test generator achieves higher and comparable effectiveness, respectively, in simulations and real hardware platforms with regard to revealing cache side‐channel leakage than do state‐of‐the‐art fuzz testing tools.

Modern file systems rely on the journaling mechanism to maintain crash consistency. The use of non-volatile memory (NVM) significantly improves the performance of journaling file systems. However, the superior performance of NVM will increase the likelihood of the journal filling up more often, thereby increasing the frequency of checkpointing. Together with the large amount of random checkpointing I/O found in most use cases, the checkpointing process becomes a new performance bottleneck. This paper proposes NV-Journaling, a strategy that reduces the frequency of checkpointing as well as reshapes the I/O pattern of checkpointing from one of random I/O to that which is more sequential I/O. NV-Journaling introduces fine-grained commits along with a cache-friendly NVM journaling layout that exploits the idiosyncrasies of NVM technology. Under this scheme, only the modified portion of a block, rather than the entire block, is written into the NVM journal device. Doing so significantly reduces checkpoint frequency and achieves better space utilization. NV-Journaling further reshapes the I/O pattern of checkpoint using a locality-aware checkpointing process. Checkpointed blocks are classified into hot and cold blocks. NV-Journaling maintains a hot block list to absorb repeated updates, and a cold bucket list to group blocks by their proximity on disk. When a checkpoint is required, cold buckets are selected such that blocks are sequentially flushed to the hard disk. We built a prototype of NV-Journaling by modifying the JBD2 layer in the Linux kernel and evaluated it using different workloads. Our experimental results show that NV-Journaling can improve performance by up to 4.3× compared to traditional journaling.

In recent years, the next-generation non-volatile memory (NVM) technologies have emerged with DRAM-like byte addressability and disk-like durability. Computer architects have proposed to use them to build persistent memory that blurs the conventional boundary between volatile memory and non-volatile storage. However, ARM processors, ones that are widely used in embedded computing systems, start providing architectural supports to utilize NVM since ARMv8. In this article, we consider tailoring B+-tree for NVM operated by a 64-bit ARMv8 processor. We first conduct an empirical study of performance overhead in writing and reading data for a B+-tree with an ARMv8 processor, including the time cost of cache line flushes and memory fences for crash consistency as well as the execution time of binary search compared to that of linear search. We hence identify the key weaknesses in the design of B+-tree with ARMv8 architecture. Accordingly, we develop a new B+-tree variant, namely, c rash r ecoverable A RMv8-oriented B +-tree (Crab-tree). To insert and delete data at runtime, Crab-tree selectively chooses one of two strategies, i.e., copy on write and shifting in place, depending on which one causes less consistency cost. Crab-tree regulates a strict execution order in both strategies and recovers the tree structure in case of crashes. To further improve the performance of Crab-tree, we employ three methods to reduce software overhead, cache misses, and consistency cost, respectively. We have implemented and evaluated Crab-tree in Raspberry Pi 3 Model B+ with emulated NVM. Experiments show that Crab-tree significantly outperforms state-of-the-art B+-trees designed for persistent memory by up to 2.2× and 3.7× in write and read performances, respectively, with both consistency and scalability achieved.

The byte-addressable non-volatile memory (NVM) promises persistent memory. Concretely, ARM processors have incorporated architectural supports to utilize NVM. In this paper, we consider tailoring the important B+-tree for NVM operated by a 64-bit ARMv8 processor. We first conduct an empirical study of performance overheads in writing and reading data for a B+-tree with an ARMv8 processor, including the time cost of cache line flushes and memory fences for crash consistency as well as the execution time of binary search compared to that of linear search. We hence identify the key weaknesses in the design of B+-tree with ARMv8 architecture. Accordingly, we develop a new B+-tree variant, namely, crash recoverable ARMv8-oriented B+-tree (Crab-tree). To insert and delete data at runtime, Crab-tree selectively chooses one of two strategies, i.e., copy on write and shifting in place, depending on which one causes less consistency cost to performance. Crab-tree regulates a strict execution order in both strategies and recovers the tree structure in case of crashes. We have evaluated Crab-tree in Raspberry Pi 3 Model B+ with emulated NVM. Experiments show that Crab-tree significantly outperforms state-of-the-art B+-trees designed for persistent memory by up to 2.6x and 3.2x in write and read performances, respectively, with both consistency and scalability achieved.

Byte-addressable non-volatile memories can be used with DRAM to build a hybrid memory system of volatile/non-volatile main memory (NVMM). NVMM file systems demand consistency techniques such as logging and copy-on-write to guarantee data consistency in case of system crashes. However, conventional consistency techniques may incur write amplification that severely degrades the file system performance. In this paper, we propose LAWN (logless, alternate writing for NVMM), a novel approach that achieves data consistency and significantly improves performance via reducing write amplification. Our evaluation reveals that LAWN boosts the performance of a state-of-the-art NVMM file system by up to 12.0×.

The necessity of intrusion detection system (IDS) is concrete for automobiles, and is particularly critical for unmanned, autonomous ones. However, limited work has been done to detect intrusions in an autonomous car while existing IDSs have limitations against strong adversaries. We hence consider the very nature of autonomous car and propose to utilize the road context to build a Road context-aware IDS (RAIDS). We hypothesize that given a computer-controlled car, the pattern and data of frames transmitted on the in-vehicle communication network should be relatively regular and obtainable when the car is cruising through continuous road contexts. Accordingly we design RAIDS and implement a preliminary prototype that discerns and identifies anomalous frames fabricated or suspended by adversaries. Evaluation results show that RAIDS effectively detects intrusions that are beyond the capabilities of state-of-the-art IDS.

The byte-addressable non-volatile memory (NVM) is a promising medium for data storage. NVM-oriented file systems have been designed to explore NVM's performance potential. Meanwhile, applications may write considerable duplicate data. For NVM, a removal of duplicate data can promote space efficiency, improve write endurance, and potentially improve the performance by avoidance of repeatedly writing the same data. However, we have observed severe performance degradations when implementing a state-of-the-art inline deduplication algorithm in an NVM-oriented file system. A quantitative analysis reveals that, with NVM, 1) the conventional way to manage deduplication metadata for block devices, particularly in light of consistency, is inefficient, and, 2) the performance with deduplication becomes more subject to fingerprint calculations. We hence propose a deduplication algorithm called NV-Dedup. NV-Dedup manages deduplication metadata in a fine-grained, CPU and NVM-favored way, and preserves the metadata consistency with a lightweight transactional scheme. It also does workload-adaptive fingerprinting based on an analytical model and a transition scheme among fingerprinting methods to reduce calculation penalties. We have built a prototype of NV-Dedup in the Persistent Memory File System (PMFS). Experiments show that, NV-Dedup not only substantially saves NVM space, but also boosts the performance of PMFS by up to 2.1x.

With the growing popularity of cloud storage, more and more diverse applications with diverse service level agreements (SLAs) are being accommodated into it. The quality of service (QoS) support for applications in a shared cloud storage becomes important. However, performance isolation, diverse performance requirements, especially harsh latency guarantees and high system utilization, are all challenging and desirable for QoS design. In this paper, we propose a service curve-based QoS algorithm to support latency guarantee applications, IOPS guarantee applications and best-effort applications at the same storage system, which not only provides a QoS guarantee for applications, but also pursues better system utilization. Three priority queues are exploited and different service curves are applied for different types of applications. I/O requests from different applications are scheduled and dispatched among the three queues according to their service curves and I/O urgency status, so that QoS requirements of all applications can be guaranteed on the shared storage system. Our experimental results show that our algorithm not only simultaneously guarantees the QoS targets of latency and throughput (IOPS), but also improves the utilization of storage resources.

Byte-addressable non-volatile memory (NVM) is going to reshape conventional computer systems. With advantages of low latency, byte-addressability, and non-volatility, NVM can be directly put on the memory bus to replace DRAM. As a result, both system and application softwares have to be adjusted to perceive the fact that the persistent layer moves up to the memory. However, most of the current in-memory data structures will be problematic with consistency issues if not well tuned with NVM. This article places emphasis on an important in-memory structure that is widely used in computer systems, i.e., the Red/Black-tree (RB-tree). Since it has a long and complicated update process, the RB-tree is prone to inconsistency problems with NVM. This article presents an NVM-compatible consistent RB-tree with a new technique named cascade-versioning . The proposed RB-tree (i) is all-time consistent and scalable and (ii) needs no recovery procedure after system crashes. Experiment results show that the RB-tree for NVM not only achieves the aim of consistency with insignificant spatial overhead but also yields comparable performance to an ordinary volatile RB-tree.

The byte-addressable non-volatile memory (NVM) is new promising storage medium. Compared to NAND flash memory, the next-generation NVM not only preserves the durability of stored data but has much shorter access latencies. An architect can utilize the fast and persistent NVM as an external disk cache. Regarding the system's crash consistency, a prevalent journaling file system needs to run atop an NVM disk cache. However, the performance is severely impaired by redundant efforts in achieving crash consistency in both file system and disk cache. Therefore, we propose a new mechanism called transactional NVM disk cache (Tinca). In brief, Tinca jointly guarantees consistency of file system and disk cache and removes the performance penalty of file system journaling with a lightweight transaction scheme. Evaluations confirm that Tinca significantly outperforms state-of-the-art design by up to 2.5X in local and cluster tests without causing any inconsistency issue.

Journaling file systems have been widely adopted to support applications that demand data consistency. However, we observed that the overhead of journaling can cause up to 48.2% performance drop under certain kinds of workloads. On the other hand, the emerging high-performance, byte-addressable Non-volatile Memory (NVM) has the potential to minimize such overhead by being used as the journal device. The traditional journaling mechanism based on block devices is nevertheless unsuitable for NVM due to the write amplification of metadata journal we observed. In this article, we propose a fine-grained metadata journal mechanism to fully utilize the low-latency byte-addressable NVM so that the overhead of journaling can be significantly reduced. Based on the observation that conventional block-based metadata journal contains up to 90% clean metadata that is unnecessary to be journalled, we design a fine-grained journal format for byte-addressable NVM which contains only modified metadata. Moreover, we redesign the process of transaction committing, checkpointing, and recovery in journaling file systems utilizing the new journal format. Therefore, thanks to the reduced amount of ordered writes for journals, the overhead of journaling can be reduced without compromising the file system consistency. To evaluate our fine-grained metadata journaling mechanism, we have implemented a journaling file system prototype based on Ext4 and JBD2 in Linux. Experimental results show that our NVM-based fine-grained metadata journaling is up to 15.8 × faster than the traditional approach under FileBench workloads.

Flash-based solid state drive (SSD) is now widely deployed to speed up data intensive applications. However, I/O amplifications caused by file system metadata and journaling shorten the lifetime of SSD. In this paper, a mechanism named Persistent In-memory Metadata Management (referred to as PIMM) is proposed to reduce I/O traffics to SSD by exploiting the persistency and byte-addressability of Non-volatile Memory (NVM). The PIMM decouples data and metadata access paths, putting data on SSD and metadata in NVM at runtime. Thus, metadata is accessed in byte-addressable manner via the memory bus and metadata I/O is eliminated because metadata in NVM is not flushed back to SSD anymore. The PIMM is prototyped on real NVDIMM platform. Extensive evaluations on implemented prototype show that the proposed PIMM reduces the block erase for SSD by up to 91% and improves performance for different workloads.

Journaling file systems have been widely used where data consistency must be assured. However, we observed that the overhead of journaling can cause up to 48.2% performance drop under certain kinds of workloads. On the other hand, the emerging high-performance, byte-addressable Non-volatile Memory (NVM) has the potential to minimize such overhead by being used as the journal device. The traditional journaling mechanism based on block devices is nevertheless unsuitable for NVM due to the write amplification of metadata journal we observed. In this paper, we propose a fine-grained metadata journal mechanism to fully utilize the low-latency byte-addressable NVM so that the overhead of journaling can be significantly reduced. Based on the observation that conventional block-based metadata journal contains up to 90% clean metadata that is unnecessary to be journalled, we design a fine-grained journal format for byte-addressable NVM which contains only modified metadata. Moreover, we redesign the process of transaction committing, checkpointing and recovery in journaling file systems utilizing the new journal format. Therefore, thanks to the reduced amount of ordered writes to NVM, the overhead of journaling can be reduced without compromising the file system consistency. Experimental results show that our NVM-based fine-grained metadata journaling is up to 15.8× faster than the traditional approach under FileBench workloads.

NAND flash memory is widely used for the secondary storage of computer systems. Theflash translation layer(FTL) is the firmware that manages and operates a flash-based storage device. One of the FTL's modules manages the RAM buffer of the flash device. Now this RAM buffer is sufficient to be used for both address mapping and data buffering. As the fastest component of the flash layer interface, effective management of this buffer has a significant impact on the performance of data storage and access. This paper proposes a novel scheme calledTreeFTLfor this purpose. TreeFTL organizes address translation pages and data storage pages in atree-likestructure in the RAM buffer. The tree enables TreeFTL to adapt to the access behaviors of workloads by dynamically adjusting the partitions for address mapping and data buffering. Furthermore, TreeFTL employs alightweightmechanism to evict the least-recently-used victim pages when the need arises. Our experiments show that TreeFTL is able to spend 46.6 and 49.0 percent less service time over various workloads than two state-of-the-art algorithms, respectively, for a 64 MB RAM buffer.

The non-volatile memory (NVM) which can provide DRAM-like performance and disk-like persistency has the potential to build single-level systems by replacing both DRAM and disk. Keeping data consistency in such systems is non-trivial because memory writes may be reordered by CPU. Although ordered memory writes for achieving data consistency can be implemented using the memory fence and the CPU cache line flush instructions, they introduce a significant overhead (more than 10X slower in performance). In this paper, we focus on an important and common data structure, B$^+$Tree. Based on our quantitative analysis for consistent tree structures, we propose NV-Tree, a consistent, cache-optimized and workload-adaptive B$^+$Tree variant with significantly reduced consistency cost (up to 96 percent reduction in CPU cache line flush). To further optimize NV-Tree under various workloads, we propose a workload-adaptive scheme in which the sizes of individual nodes can be dynamically adjusted to improve the performance over time. We implement and evaluate NV-Tree and NV-Store, a key-value store based on NV-Tree, on an NVDIMM server. NV-Tree outperforms the state-of-art consistent tree structures by up to 12X under write-intensive workloads. NV-Store increases the throughput by up to 7.3X under YCSB workloads compared to Redis.

As building block for cloud storage, distributed file system uses underlying local file systems to manage objects. However, the underlying file system, which is limited by metadata and journaling I/O, significantly affects the performance of the distributed file system. This paper presents an NVM-based file system (referred to as NV-Booster) to accelerate object access for storage node. The NV-Booster leverages byte-addressability and persistency of nonvolatile memory (NVM) to speedup metadata accesses and file system journaling. With NV-Booster, metadata is kept in NVM and accessed in byte-addressable manner through memory bus, while object is stored on hard disk and accessed from I/O bus. In addition, proposed NV-Booster enables fast object search and mapping between object ID and on-disk location with an efficient in-memory namespace management. NV-Booster is implemented in kernel space with NVDIMM and has been extensively evaluated under various workloads. Our experiments show that NV-Booster improves Ceph performance up to 10X, compared to the Ceph with existing local file systems.

The advent of the byte-addressable, non-volatile memory (NVM) has initiated the design of new data management strategies to utilize it as the persistent memory (PM). One way to manage the PM is via an in-memory file system. The consistency of the in-memory file system may nevertheless be compromised from directly exposing the PM to the CPU, because data are likely to be flushed from the CPU cache to the PM in an order that is different from the order in which they have been programed to be. As a result, in spite of classic consistency mechanisms, such as journaling and Copy-on-Write, file systems for the PM have to seek support of cacheline flush and memory fence instructions, e.g., clflush and sfence, to achieve ordered writes. On the other hand, manipulating the PM as a consistent block device with conventional file systems is also doable. The pros and cons of two approaches, however, have not been thoroughly investigated yet. We hence do so with extensive evaluations and detailed analyses. Our aim of this paper is to inspire how the PM shall be managed, especially from the performance perspective.

The approximation based programming paradigm is especially attractive for developing error-resilient applications, targeting low power embedded devices. It allows for program data to be computed and stored approximately for better energy efficiency. The duration of battery in the smartphones, tablets, etc. is generally more of a concern to users than an application's accuracy or fidelity beyond certain acceptable quality of service. Therefore, relaxing accuracy to improve energy efficiency is an attractive trade-off when permissible by the application's domain. Recent works suggest source code annotations and type qualifiers to facilitate safe approximate computation and data manipulation. It requires rewriting of programs or the availability of source codes for annotations. This may not be feasible as real-world applications tend to be large, with source code that is not readily available.

The write endurance of NAND flash memory adversely impacts the lifetime of flash devices. A flash cell is likely to wear out after undergoing excessive program/erase (P/E) flips. Wear leveling is hence employed to spread erase operations as evenly as possible. It is traditionally conducted by the flash translation layer (FTL), a management firmware residing in flash devices. In this paper, we shall propose a novel wear leveling algorithm involving the operating system (OS). We will show that our operating System-Assisted Wear leveling (SAW) algorithm can significantly improve the wear evenness. SAW takes advantage of OS's knowledge about files at a higher level of abstraction, and provides useful hints to the lower-level FTL to accommodate data. A prototype based on a file system and an FTL has been developed to verify the effectiveness of SAW. Experiments show that wear evenness can be improved by as much as 85.0% compared to the state-of-the-art FTL wear leveling schemes.

NAND flash memory is widely used for secondary storage today. The flash translation layer (FTL) is the embedded software that is responsible for managing and operating in flash storage system. One important module of the FTL performs RAM management. It is well-known to have a significant impact on flash storage system's performance. This paper proposes an efficient RAM management scheme called TreeFTL. As the name suggests, TreeFTL organizes address translation pages and data pages in RAM in a tree structure, through which it dynamically adapts to workloads by adjusting the partitions for address mapping and data buffering. TreeFTL also employs a lightweight mechanism to implement the least recently used (LRU) algorithm for RAM cache evictions. Experiments show that compared to the two latest schemes for RAM management in flash storage system, TreeFTL can reduce service time by 46.6% and 49.0% on average, respectively, with a 64MB RAM cache.

In NAND flash memory, wear leveling is employed to evenly distribute program/erase bit flips so as to prevent overall chip failure caused by excessive writes to certain hot spots of the chip. In this paper, we analyze latest wear leveling algorithms, and propose Observational Wear Leveling (OWL). OWL considers the temporal locality of write activities at runtime when blocks are allocated. It also transfers data between blocks of different ages. From our experiments, with minimal additional space and time overhead, OWL can improve wear evenness by as much as 29.9% and 43.2% compared to two state-of-the-art wear leveling algorithms, respectively.

Flash memory is widely utilized for secondary storage today. However, its further use is hindered by the lifetime issue, which is mainly impacted by wear leveling and bad block management (BBM). Besides initial bad blocks resulting from the manufacturing process, good blocks may eventually wear out due to the limited write endurance of flash cells, even with the best wear leveling strategy. Current BBM tracks both types of bad blocks, and keeps them away from regular use. However, when the amount of bad blocks exceeds a threshold, the entire chip is rendered non-functional. In this paper, we reconsider existing BBM, and propose a novel one that reuses worn-out blocks, utilizing them in wear leveling. Experimental results show that compared to a state-of-the-art wear leveling algorithm, our design can reduce worn-out blocks by 46.5% on average with at most 1.2% performance penalties.

Solid-state drives (SSDs) made of flash memory are widely utilized in enterprise servers nowadays. Internally, the management of flash memory resources is done by an embedded software known as the flash translation layer (FTL). One important function of the FTL is to map logical addresses issued by the operating system into physical flash addresses. The efficiency of this address mapping in the FTL directly impacts the performance of SSDs. In this paper, we propose a hybrid mapping FTL scheme, called Aggregated Data movement Augmenting Predictive Transfers (ADAPT). ADAPT observes access behaviors online to handle both sequential and random write requests efficiently. It also takes advantage of locality revealed in the history of recent accesses to avoid unnecessary data movements in the required merge process. More importantly, by these mechanisms, ADAPT can adapt to various workloads to achieve good performance. Experimental results show that ADAPT is as much as 35.4%, 44.2% and 23.5% faster than a state-of-the-art hybrid mapping scheme, a prevalent page-based mapping scheme, and a latest workload-adaptive mapping scheme, respectively, with a small increase in space requirement.