一种时间敏感的SSD和HDD高效混合存储模型

基于闪存的固态硬盘(Solid State Driver,SSD)已成为目前广泛使用的一种持久存储设备.但是由于闪存不对称的I/O特性以及价格因素,SSD还不能完全取代传统硬盘(Hard Disk Driver,HDD).因此,由SSD和HDD组成的混合存储系统逐步成为目前研究的重点.文中针对SSD和HDD混合存储问题,提出了一个时间敏感的混合存储模型用来有效地利用SSD.该模型把SSD和HDD作为同级的存储设备,结合数据页的访问次数以及访问热度实现对页面的准确分类和分配,即将读倾向负载的hot页面分配到SSD存储,写倾向负载的页面或者cold页面分配到HDD存储,从而利用SSD和HDD不对称的I/O特性来降低系统总的I/O延迟.作者分别在基于高端SSD和中端SSD的混合存储系统上实现了提出的混合存储模型,并进行了性能评测.实验结果显示,作者提出的模型可以实现对数据页更准确的分类,可以有效地降低页面迁移代价,在较少的SSD存储条件下取得了显著的性能提升.     

混合结构数据库中基于页迁移的存储分层算法

为了有效地利用固态盘读速快以及磁盘低存储成本的特点,在磁盘和固态盘共存的混合存储结构模型下,设计并实现了一种基于页迁移思想的存储分层算法(SZA)。不同于NUMA的迁移代价计算方法,该算法按照迁移代价选择相应的存储介质,并且对不同工作负载的数据进行迁移。实验结果显示,算法有效地提升了数据库系统的I/O性能,同时大幅度地减少了对闪存的擦写次数。     

一种基于闪存的缓冲区管理算法

在大多数以磁盘为存储系统的操作系统中,缓冲区管理算法只考虑到了数据访问的命中率。然而,闪存的写操作代价远远大于读操作代价。为了提高闪存性能,本文提出的O CFLRU（Optimal CFLRU）算法对于CFLRU（Clean First LRU）算法做了优化。该算法用一种页 块混合的数据结构来分别管理缓冲区中的干净页面和脏的数据页面聚簇。当缓冲区空间不够时,优先置换干净页面,再置换出脏的数据页聚簇,从而减少了写回的次数和随机写带来的擦除次数,提高了闪存的性能。     

FClock:一种面向SSD的自适应缓冲区管理算法

现有的各种基于闪存的缓冲区管理算法针对闪存读写代价的不对称性进行改进,实际中既存在同一闪存读写代价的不对称性问题,也存在不同闪存不对称性之间的巨大差异性问题,而后者一直没有得到足够的重视.文章提出一种基于闪存硬盘(SSD)的自适应缓冲区管理算法FClock,FClock将数据页组织为两个环形数据结构(CC和DC),分别用于存储缓冲区中的只读数据页和已修改数据页.当需要选择置换页时,FClock使用基于代价的启发式来选择置换页,可在未修改的数据页和已修改的数据页之间进行公平的选择,适用于不同种类的SSD.针对数据库、虚存和文件系统中数据页访问存在高相关性的特点,提出基于"平均命中距离"的访问计数方法来调整数据页的访问频率.基于不同SSD和不同存取模式的实验结果说明,FClock的综合性能优于已有方法.     

基于免疫安全存储设备IBSSD的研究与实现

基于智能磁盘的安全存储设备是当前安全存储系统研究的热点问题.为解决现有安全存储设备I/O性能低的问题,引入人工免疫算法,实现高效的访问控制模块.首先给出基于免疫安全存储设备的结构,以及基于免疫访问控制模块中主要元素的定义,针对存储设备的特点,设计了差异选择算法和混合检测算法.实现了基于免疫访问控制的原型系统,验证了系统能高效地识别非法数据访问请求.修改开源存储区域网系统-Lustre中智能磁盘模块的代码,构建基于免疫安全存储设备的原型系统,测试了I/O性能.结果验证了基于免疫安全存储设备的I/O损失较小,能构成较高性能的安全存储系统.     

一种基于磁盘介质的网络存储系统缓存

随着计算规模越来越大,网络存储系统应用领域越来越广泛,对网络存储系统I/O性能要求也越来越高.在存储系统高负载的情况下,采用低速介质在客户机和网络存储系统的I/O路径上作为数据缓存也变得具有实际的意义.设计并实现了一种基于磁盘介质的存储系统块一级的缓存原型D-Cache.采用两级结构对磁盘缓存进行管理,并提出了相应的基于块一级的两级缓存管理算法.该管理算法有效地解决了因磁盘介质响应速度慢而带来的磁盘缓存管理难题,并通过位图的使用消除了磁盘缓存写Miss时的Copy on Write开销.原型系统的测试结果表明,在存储服务器高负载的情况下,缓存系统能够有效地提高系统的整体性能.     

一种针对闪存的高效缓冲区置换算法

随着闪存容量的不断增长和闪存应用的日益广泛,针对闪存的缓冲区管理已成为一个迫切需要解决的问题.针对闪存的写代价显著高于读代价的特性,提出一种针对闪存的页面置换算法LEAC.LEAC根据页面的读写负载和闪存的读写代价差异对换出页面引起的预期闪存访问开销进行评估,优先换出预期访问开销最低的页.实验表明,LEAC可以显著降低闪存访问开销.     

一种海量数据分级存储系统TH-TS

随着数据存储规模的飞速增长,降低存储系统的总拥有成本,提高数据访问性能成为构建海量存储系统的关键.设计并实现了一个海量数据分级存储系统TH-TS(Tsinghua Tiered Storage),由多级存储设备构成一体化的数据存储环境.该系统提出了Cute Mig数据迁移方法:采用基于升级成本和升级收益的升级迁移策略和基于剩余空间的文件自适应降级选择策略,解决了传统on-demand迁移方法中迁移数据量大、访问性能不佳的问题.评测结果表明,TH-TS采用Cute Mig迁移方法的系统平均I/O响应时间比传统的LRU和GreedyDualSize方法分别降低了10%和39%左右,数据升级迁移量分别降低了32%和59%左右,降级迁移量分别降低了47%和66%左右.     

并行文件系统Lustre细粒度I/O性能优化

并行文件系统Lustre粗粒度I/O性能良好,细粒度I/O性能相对粗粒度I/O比较低下,因此优化细粒度I/O性能成为提高系统整体I/O性能的关键问题。在研究和分析了Lustre的I/O访问模式、细粒度I/O服务流程和页面替换算法等方面后,提出了细粒度优先（Fine Grained First,FGF）LRU算法。在OST端及Client端的页高速缓存中最大程度地保留细粒度I/O的页面,降低细粒度I/O引起的页面下沉速度,延长细粒度I/O页面在主存中的时间,进而减少对磁盘的访问次数,降低磁盘访问开销。通过对实验数据的对比和分析,验证了FGF-LRU算法的有效性。在不影响粗粒度I/O性能的情况下,提高了细粒度I/O性能,最终实现提高系统整体I/O性能。     

基于写数据页聚簇的固态硬盘缓冲算法

针对Flash写前需擦除,读写I／O开销不均衡等固有缺陷,研究面向闪存缓冲区管理,对提高基于Flash的固态硬盘（SolidState Disk,SSD）访问性能具有重要理论意义和应用价值．通过分析SSD关键技术及现有缓冲区管理算法,实现了一种适用于SSD的基于写数据页聚簇缓冲算法．文章中详细介绍了该算法关键技术及原理,并通过FlashSim仿真平台实现SSD写缓冲．基于仿真结果与传统缓冲算法性能比对,分析得出该缓冲算法可降低SSD随机写次数和SSD数据存储分散性,并提升SSD响应速度．     

Modeling the aging process of flash storage by leveraging semantic I/O

The major advantages of flash memory such as small physical size, no mechanical components, low power consumption, and high performance have made it likely to replace the magnetic disk drives in more and more systems. Many research efforts have been invested in employing flash memory to build high performance and large-scale storage systems for data-intensive applications. However, the endurance cycle of flash memory has become one of the most important challenges in further facilitating the flash memory based systems. This paper proposes to model the aging process of flash memory based storage systems constructed as a Redundant Array of Independent Disks (RAID) by leveraging the semantic I/O. The model attempts to strike a balance between the program/erase cycles and the rebuilding process of RAID. The analysis results demonstrate that a highly skewed data access pattern ages the flash memory based RAID with an arbitrary aging rate, and a properly chosen threshold of aging rate can prevent the system from aging with a uniform data access pattern. The analysis results in this paper provide useful insights for understanding and designing effective flash memory based storage systems.     

A hybrid filesystem for hard disk drives in tandem with flash memory

The traditional hard disk drive (HDD) is often a bottleneck in the overall performance of modern computer systems. With the development of solid state drives (SSD) based on flash memory, new possibilities are available to improve secondary storage performance. In this work, we propose a new hybrid SSD–HDD storage system and a selection of algorithms designed to assign pages across an HDD and an SSD to optimise I/O performance. The hybrid system combines the advantages of the SSD’s fast random seek speed with the sequential access speed and large storage capacity of the HDD to produce significantly improved performance in a variety of situations. We further improve performance by allowing concurrent access across the two types of storage devices. We show the drive assignment problem is NP-complete and accordingly propose effective heuristic solutions. Extensive experiments using both synthetic and real data sets show our system with a small SSD can outperform a striped dual HDD and remain competitive with a dual SSD.     

A workload-aware flash translation layer enhancing performance and lifespan of TLC/SLC dual-mode flash memory in embedded systems

Similar to traditional NAND flash memory, triple-level cell (TLC) flash memory is used as secondary storage to meet the fast growing demands on storage capacity. TLC flash memory exhibits attractive features such as shock resistance, high density, low cost, non-volatility and low access latency natures. However, TLC flash memory also has some extra limitations, such as write disturbance, low performances and very limited cycles compared to single-level cell (SLC) flash memory.In this paper, we propose a workload-aware flash translation layer, named Balloon-FTL, for the TLC/SLC dual-mode flash memory, to improve performance and lifespan of the system. We first build a workload identifier module with genetic algorithm to dynamically allocate TLC/SLC capacity based on different workloads, and produce the suitable data allocation to achieve a balanced write distribution in flash memory with low memory access cost. The basic idea is to classify metadata/userdata according to their access pattern, and allocate low-latency SLC and high-density TLC mode blocks for write-intensive metadata and a large quantities userdata, respectively. We then propose a special hybrid mapping strategy for the TLC/SLC dual-mode flash memory to improve the performance. Experimental results show that Balloon-FTL can effectively improve the performance and lifespan of the TLC/SLC dual-mode flash memory in embedded systems.     

一种闪存敏感的多级缓存管理方法

基于闪存的固态硬盘(solid state driver,简称SSD)已经广泛应用于各种移动设备、PC机和服务器.与磁盘相比,尽管SSD具有数据存取速度高、抗震、低功耗等优良特性,但SSD自身也存在读写不对称、价格昂贵等不利因素,这使得SSD 短期内不会完全取代磁盘.将SSD和磁盘组合构建混合系统,可以发挥不同的硬件特性,提升系统性能.基于 MLC 型 SSD 和 SLC 型 SSD 之间的特性差异,提出了一种闪存敏感的多级缓存管理策略——FAMC.FAMC将SSD用在内存和磁盘之间作扩展缓存,针对数据库系统、文件管理中数据访问的特点,有选择地将内存牺牲页缓存到不同类型的SSD.FAMC同时考虑写请求模式和负载类型对系统性能的影响,设计实现对SSD友好的数据管理策略.此外,FAMC基于不同的数据置换代价提出了适用于SSD的缓冲区管理算法.基于多级缓存存储系统对FAMC的性能进行了评测,实验结果表明,FAMC可以大幅度降低系统响应时间,减少磁盘I/O.     

TridentFS: a hybrid file system for non‐volatile RAM,flash memory and magnetic disk

A hybrid file system with high flexibility and performance, called Trident file system (TridentFS), is proposed to manage three types of storage with different performance characteristics, that is, Non‐Volatile RAM (NVRAM), flash memory and magnetic disk. Unlike previous NVRAM‐based hybrid file systems, novel techniques are used in TridentFS to improve the flexibility and performance. TridentFS is flexible by the support of various forms of flash memory and a wide range of NVRAM size. The former is achieved on the basis of the concept of stackable file systems, and the latter is achieved by allowing data eviction from the NVRAM. TridentFS achieves high performance by keeping hot data in the NVRAM and allowing data evicted from the NVRAM to be parallel distributed to the flash memory and disk. A data eviction policy is proposed to determine the data to be evicted from the NVRAM. Moreover, a data distribution algorithm is proposed to effectively leverage the parallelism between flash memory and disk during data distribution. TridentFS is implemented as a loadable module on Linux 2.6.29. The performance results show that it works well for both small‐sized and large‐sized NVRAM, and the proposed eviction policy outperforms LRU by 27%. Moreover, by effectively leveraging the parallelism between flash memory and disk, the proposed data distribution algorithm outperforms the RAID‐0 and a size‐based distribution method by up to 471.6% and 82.6%, respectively. By considering the data size and performance characteristics of the storage, the proposed data distribution algorithm outperforms the greedy algorithm by up to 15.5%. Copyright © 2014 John Wiley & Sons, Ltd.     

HybridPlan: a capacity planning technique for projecting storage requirements in hybrid storage systems

Economic forces, driven by the desire to introduce flash into the high-end storage market without changing existing software-base, have resulted in the emergence of solid-state drives (SSDs), flash packaged in HDD form factors and capable of working with device drivers and I/O buses designed for HDDs. Unlike the use of DRAM for caching or buffering, however, certain idiosyncrasies of NAND Flash-based solid-state drives (SSDs) make their integration into hard disk drive (HDD)-based storage systems nontrivial. Flash memory suffers from limits on its reliability, is an order of magnitude more expensive than the magnetic hard disk drives (HDDs), and can sometimes be as slow as the HDD (due to excessive garbage collection (GC) induced by high intensity of random writes). Given the complementary properties of HDDs and SSDs in terms of cost, performance, and lifetime, the current consensus among several storage experts is to view SSDs not as a replacement for HDD, but rather as a complementary device within the high-performance storage hierarchy. Thus, we design and evaluate such a hybrid storage system with HybridPlan that is an improved capacity planning technique to administrators with the overall goal of operating within cost-budgets. HybridPlan is able to find the most cost-effective hybrid storage configuration with different types of SSDs and HDDs     

The log-structured merge-tree (LSM-tree)

 High-performance transaction system applications typically insert rows in a History table to provide an activity trace; at the same time the transaction system generates log records for purposes of system recovery. Both types of generated information can benefit from efficient indexing. An example in a well-known setting is the TPC-A benchmark application, modified to support efficient queries on the history for account activity for specific accounts. This requires an index by account-id on the fast-growing History table. Unfortunately, standard disk-based index structures such as the B-tree will effectively double the I/O cost of the transaction to maintain an index such as this in real time, increasing the total system cost up to fifty percent. Clearly a method for maintaining a real-time index at low cost is desirable. The log-structured merge-tree (LSM-tree) is a disk-based data structure designed to provide low-cost indexing for a file experiencing a high rate of record inserts (and deletes) over an extended period. The LSM-tree uses an algorithm that defers and batches index changes, cascading the changes from a memory-based component through one or more disk components in an efficient manner reminiscent of merge sort. During this process all index values are continuously accessible to retrievals (aside from very short locking periods), either through the memory component or one of the disk components. The algorithm has greatly reduced disk arm movements compared to a traditional access methods such as B-trees, and will improve cost-performance in domains where disk arm costs for inserts with traditional access methods overwhelm storage media costs. The LSM-tree approach also generalizes to operations other than insert and delete. However, indexed finds requiring immediate response will lose I/O efficiency in some cases, so the LSM-tree is most useful in applications where index inserts are more common than finds that retrieve the entries. This seems to be a common property for history tables and log files, for example. The conclusions of Sect. 6 compare the hybrid use of memory and disk components in the LSM-tree access method with the commonly understood advantage of the hybrid method to buffer disk pages in memory. Received July 6, 1992/April 11, 1995     

Vertical partitioning for flash and HDD database systems

Recent advances in flash memory technology have greatly enhanced the capability of flash memory to address the I/O bottleneck problem. Flash memory has exceptional I/O performance compared to the hard disk drive (HDD). The superiority of flash memory is especially visible when dealing with random read patterns. Even though the cost of flash memory is higher than that of HDD storage, the popularity of flash memory is increasing at such a pace that it is becoming a common addition to the average computer. Recently, flash memory has been made into larger devices called solid state drives (SSDs). Although these devices can offer capacities comparable to HDDs, they are considerably more expensive per byte.Our research aims to increase the I/O performance of database systems by using a small amount of flash memory alongside HDD storage. The system uses a fully vertically partitioned storage structure where each column is stored separately on either the HDD or SSD. Our approach is to assign the columns into the SSD which will benefit the most from the characteristics of flash memory. We prove this problem is NP-complete and propose an optimal dynamic programming solution and a faster greedy heuristic solution.A system simulator has been implemented and experiments show that the overall I/O costs can be greatly reduced using only a limited amount of flash memory. The results show the greedy heuristic solution performed similarly to the more expensive dynamic programming solution for the situations tested.     

Profit data caching and hybrid disk‐aware Completely Fair Queuing scheduling algorithms for hybrid disks

Recently, a hybrid disk drive that integrates a small amount of flash memory within a mechanical drive has received significant attention. The hybrid drive extends the storage hierarchy by using flash memory to cache data from the mechanical disk. Unfortunately, current caching architectures fail to fully exploit the potential of the hybrid drive. Furthermore, current disk input/output (I/O) schedulers are optimized for rotational mechanical disk drives and thus must be re‐targeted for the hybrid disk drive. In this paper, we propose a new data caching scheme, called Profit Caching, for hybrid drives. Profit Caching is a self‐optimizing caching algorithm. It considers and seamlessly integrates all possible data characteristics that impact the performance of hybrid drives, including read count, write count, sequentiality, randomness, and recency, to determine the caching policy. Moreover, we propose a hybrid disk‐aware Completely Fair Queuing (HA‐CFQ) scheduler to avoid unnecessary I/O anticipations of the CFQ scheduler. We have implemented Profit Caching and HA‐CFQ scheduler in the Linux kernel. Coupled with a trace‐driven simulator, we have also conducted detailed experiments under a variety of workloads. Experimental results show that Profit Caching provides significantly improved performance compared with the previous schemes. In particular, the throughput of Profit Caching outperforms previous Random Access First and FlashCache caching schemes by factors of up to 1.8 and 7.6, respectively. In addition, the HA‐CFQ scheduler reduces the total execution time of the CFQ scheduler by up to 1.74%. Finally, the experimental results show that the runtime overhead of Profit Caching is extremely insignificant and can be ignored. Copyright © 2014 John Wiley & Sons, Ltd.