基于闪存的数据缓存关键技术研究

Flash disks are considered as important alternatives to conventional magnetic disks because of their distinguished feature, such as being small, lightweight and no mechanical delay etc. However, flashed based data management techniques are still far from ideality. In the long future, there will be many flashed based storage system that are constructed in terms of the unique requirements of various applications. In all these systems, buffer is one of the most fundamental components, and any substantial progress in buffer replacement algorithms will affect the entire modern computational stack. Although researchers have proposed many flash-aware buffer replacement algorithms, their assumption is that the cost of random read operation is neglectable compared with that of random write operation, which does not consistent with the actuality. In fact, besides the fact that the cost of random read operation is less than that of random write operation, a more important thing is that there exists huge discrepancy to the ratio of write cost to read cost on different flash disks. In this project, we focus on making improvements on the key technologies related to buffer management for flash-based system, include buffer management strategy against single-storage media, multi-types of storage media, and the data placement in hybrid storage system. This research can discover the adaptive replacement strategies, algorithms and models in flash based storage systems, which has important theoretical significance and application value.

虽然闪存以其小巧、轻便、无机械延迟等特点被认为有望替代磁盘作为未来的二级存储设备，但是基于闪存的数据管理技术远未发展成熟。在未来相当长一段时间内，根据不同应用的特点和要求，实际中将出现各种基于闪存的存储系统。在这些系统中，缓冲区是其核心组件，缓冲区置换算法的高效与否直接决定了系统的效率。虽然研究者已经提出了各种基于闪存的缓冲区置换策略，但其基本假设是闪存的随机读代价远小于随机写代价。这一假设和实际不符，实际中不但单一闪存存在读写代价不对称的问题，而且不同型号闪存读写不对称的程度之间存在巨大差异性。本课题基于这一背景，重点研究基于闪存的缓冲区管理中涉及的关键技术问题，包括单介质、多介质、多级缓冲区管理机制以及混合式系统中的数据放置策略。本项目的研究有助于系统阐明在各种基于闪存的存储系统中的自适应置换策略、相关算法及模型，具有重要的理论意义和应用价值。

本项目重点研究基于闪存的缓冲区数据组织策略和数据页置换策略。通过三年的研究工作，完成了计划内容，建立了基于闪存的存储模型，针对不同应用环境和存储配置的情况，提出了高效的数据组织结构，以及能够兼顾各种应用要求的自适应缓冲区置换策略。在绿色计算方面，提出并设计了一种基于闪存的自适应缓冲区数据页组织结构，提出基于置换代价的数据页置换策略和相应的AFC置换算法。AFC通过减少读写操作的能耗来降低系统耗电量，这和已有的磁盘休眠调度算法及用SSD取代磁盘并不矛盾，且具有互补性，可有效降低存储子系统的耗电量，进而降低系统的总能耗。在缓冲区置换方面，提出自适应的缓冲区数据组织结构和优化的平均命中距离（AHD）的定义，并设计了合理的计算命中距离的起始位置以及确定平均命中距离的上界，最后设计了常量时间的平均命中距离计算方法。该方法不仅能够在不同的存取模式间进行自适应的调整，而且与以往的算法相比，能够在不同的闪存硬盘上获得很好的性能。在集合交集求解方面，提出新的探查元素选择方法和探查顺序，提出新的基于关键距离和分布均匀度的探查方法。可有效提升信息检索、搜索引擎及数据库系统中集合交集操作的效率，增强系统的整体性能。在符号网络社区发现方面，提出基于节点相似度和参与度的符号网络社区发现算法CD-SNNSP。在基于数据图的压缩方面，提出了高效的传递规约算法，提出了线性时间的等价规约算法。该方法具有线性空间复杂度，显著提升了算法在时间和空间方面的扩展性，可以处理大规模数据图。