• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学

• 高性能计算 • 上一篇    下一篇

基于权重堆排序的NAND Flash静态磨损均衡机制

刘彦,徐骥龙,祝磊   

  1. (湖南大学信息科学与工程学院,湖南 长沙 410082)
  • 收稿日期:2018-08-20 修回日期:2018-10-15 出版日期:2019-02-25 发布日期:2019-02-25
  • 基金资助:

    国家自然科学基金(61872135,61300037);湖南省自然科学基金(2018JJ2066)

A NAND Flash static wear leveling
mechanism based on weighted heap sort

LIU Yan,XU Jilong,ZHU Lei   

  1. (College of Computer Science and Electronic Engineering,Hunan University,Changsha 410082,China)
  • Received:2018-08-20 Revised:2018-10-15 Online:2019-02-25 Published:2019-02-25

摘要:

磨损均衡机制作为闪存转换层的基础机制之一,其主要功能是延长闪存块使用寿命和提高存储数据的可靠性。现有的磨损均衡机制着重于减少闪存块的擦除次数,忽略了在磨损均衡操作过程中选择擦除脏块的不合理所带来的不必要数据迁移开销,从而影响了固态硬盘的整体读写性能。针对该问题,提出了一种基于权重堆排序的 NAND Flash静态磨损均衡机制WHWL。首先,提出一种基于页数据访问频率和块擦除次数的权重的热度计算方法,有效地提高擦除次数少(冷块)且数据访问频率低(冷数据)的目标块命中率,避免了多余的数据迁移操作;其次,提出了一种基于权重的堆排序目标块选择算法,以加快目标块的筛选。实验结果表明,与现有的PWL和BET算法相比,在使用相同映射机制的条件下,WHWL能够分别提升固态硬盘寿命1.28、5.83倍,数据迁移次数也有明显的降低。

关键词: 权重, 堆排序, NAND Flash, 磨损均衡

Abstract:

As one of the basic mechanisms of the flash translation layer, the wear leveling mechanism is a software algorithm that is applied to extend the life of the flash disk and improve the reliability of stored data. However, existing wear leveling mechanisms are too aggressive to balance the erasure counts of the entire flash memory and ignore the unnecessary data migration overhead due to the unreasonable selection of victim blocks during wear leveling operations, thereby affecting the overall read and write performance of the solid state disk. To solve this problem, we firstly propose a NAND Flash static wear leveling mechanism based on weighted heap sort, namely WHWL. We introduce a weight calculation method based on page data access frequency and the weight of erase counts of the block, which can effectively improve the hit rate of the target blocks with a small number of erases (cold blocks) and a low frequency of data access (cold data), and avoid redundant data migration operations. Secondly, we also propose a victim block selection algorithm based on weighted heap sort to speed up the selection of victim blocks. Experimental results show that compared with the existing PWL and BET algorithms, using the same mapping mechanism, the WHWL can increase the life span of solid state disks by 1.28 and 5.83 times, and also greatly decrease the number of migrations.
 

Key words: weight, heap sort, NAND Flash, wear leveling