耐用的頁級轉換多通道固太硬碟之自適性低成本的垃圾收集策略

Adaptive, Low-Cost Garbage Collection for Durable Page-Mapping Multichannel SSDs

劉宇洵(Yu-Syun Liu)

指導教授 ： 張立平

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2014年)

https://doi.org/10.6842/NCTU.2014.00864

摘要

近年來固態硬碟所搭載的隨機存取記憶體空間逐漸增大，因此將有足夠的空間實作頁級對映，可避免混合級對映在合併記錄區塊與資料區塊時所造成的負擔，增加寫入速度，降低磨損程度，使固態硬碟更加耐用。但許多針對頁級對映的快閃記憶體轉換層所設計的垃圾收集策略，通常在挑選垃圾收集策略的當選區塊時須要替每個實體區塊計算分數，或是在寫入資料時需要紀錄每個邏輯頁的寫入時間，又或者擁有某些參數，在不同的情況下，無法自動調適至最佳值，需要人為的設定。隨著固態硬碟的容量增大，虛要計算與記錄的項目增加，這類的方法無論在時間或空間上皆無法負荷。
Dual-greedy針對以上這些問題提出改良，以區塊為單位記錄須要的資訊，降低空間成本，且時間複雜度為常數，所有參數不需人為設定，可在執行時自動調整至最佳狀態，但是Dual-greedy在多通道架構下效能會降低，且沒有考慮到抹除平均的問題。因此我們提出一種新的頁級對映快閃記憶體轉換層，此研究的垃圾收集方法是基於Dual-greedy，但是針對多通道的架構提出改良，並且解決抹除平均的問題，使固態硬碟更加耐用。
此研究分為三個部分，第一是改善Dual-greedy在多通道時，單一通道內區塊數目變少，而使垃圾收集效率下降的問題。第二是利用簡單的資料結構，快速且有效的達到通道內各個實體區塊平均抹除，第三是針對多通道且動態綁定的架構時，使各通道耗損程度一致，平均各個通道剩餘使用期限的方法，延長固態硬碟的整體使用壽命。

關鍵字

固態硬碟 ； 快閃記憶體 ； 垃圾收集 ； 平均抹除

並列摘要

In recent years, random access memory equipped with SSDs are increasing, so there will be enough space for page-level mapping table. Page-level mapping flash translation layer can avoid the overhead caused by merge log block and data block when using hybrid-level mapping, so page-level mapping have higher write speed and lower degree of wear. But many of garbage collection policy design for page-level mapping flash translation layer, need to calculate scores for each physical block when they are selecting victims for garbage collection, or record time for each logical page when they are writing user data, or have some parameters in different situations can not automatically adapt to the optimum value, need for human setting. With solid-state hard disk capacity increases, these kind of approach become infeasible in terms of time or space overhead.
Dual-greedy proposed improvements for these problems, records block level information, reduce the cost of random access memory space. Time complexity of Dual-greedy is constant, and all parameters can automatically adjust to the best state in run time, without artificially setting. But Dual-greedy dose not consider the wear-leveling problem, and it's performance will decreases when implementing on multichannel architecture. Therefore, We propose an new page-level mapping flash translation, the methods of garbage collection policy is based on Dual Greedy, but improment performance for multi-channel architecture, and consider the problem of wear-leveling, make SSDs more duable.
This study have three parts. The first is to improve the Dual-greedy in a multi-channel architecture, solve the problem that the efficiency of garbage collection policy of Dual-greedy decreases when the number of blocks within a single channel becomes less. The second is using simple data structures, fast and effective balance each physical block erase count in a channel. And the third is for a multi-channel architecture with dynamic binding, balance the degree of wear for every channel, let the remaining life of each channel is consistent, extend the overall life of SSDs.

並列關鍵字

Solid State Disk ； flash memory ； garbage collection ； wear leveling

參考文獻

[2] M.-L. Chiang, P. C. H. Lee, and R.-C. Chang. Using data clustering to improve cleaning performance for Hash memory. SoftwarePractice and Experience, 29:267-290, 1999.

[3] Wen-Huei Lin and Li-Pin Chang. 2012. Dual Greedy: Adaptive Garbage Collection for Page-mapping Solidstate Disks. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE ’12). EDA Consortium, San Jose, CA, USA, 117–122.

[5] Li-Pin Chang, Tung-Yang Chou, and Li-Chun Huang. 2013. An Adaptive, Low-cost Wear-leveling Algorithm for Multichannel Solid-state Disks. ACM Trans. Embed. Comput. Syst. 13, 3, Article 55 (Dec. 2013), 26.

[6] Microsoft Research. SSD Extension for DiskSim Simulation Environment.

[7] S.-w. Lee, D.-1. Park, T.-S. Chung, D.-H. Lee, S. Park, and H.-1. Song. A log buffer-based Hash translation layer using fully-associative sector translation. ACM Trans. Embed. Comput. Syst., 6, luly 2007.