快閃記憶體位址轉譯層(FTL)利用out-of-place的更新方法來隱藏erase-before-write特性以便在快閃記憶體上層模擬出區塊裝置介面。快閃記憶體位址轉譯層也需要保有映對表(mapping table)以作為邏輯位址和實體位址的轉譯。Fully Associative Sector Translation (FAST)是著名log buffer-based快閃記憶體轉譯層的其中一種並且採用混合式映對結構。FAST將log area分為一個循序寫入型log block和多個隨機寫入型log block來達到令人滿意的效能。容納隨機寫入的pages可以避免過早合併(merge) data block及增加回收dead block(指不包含live pages的block)的機率。然而，FAST在處理循序寫入資料的合併策略是沒有效率的，因為此合併策略使得能保留於log area的循序寫入型log block提早被合併。因此，我們提出名為MESOR的有效映對交換方法來減少FAST快閃記憶體位址轉譯層的合併動作及盡可能地善用循序寫入式log block內的閒置空間。MESOR亦可被應用至其他FAST-based快閃記憶體位址轉譯層(如HFTL)且改善它們的效能。實驗結果顯示MESOR可分別於FAST和HFTL中減少高達93%及66.8%的回收成本(cleaning cost)。

A Flash Translation Layer (FTL) hides the impact of the erase-before-write property with out-of-place update method in order to emulate a block device interface on top of flash memory. FTL also has to maintain a mapping table to help address translation from logical address to physical address. Fully Associative Sector Translation (FAST) is one of the well-known log buffer-based FTLs and adopts hybrid-mapped scheme. FAST achieves good performance by dividing the log area into a sequential write log block and random write log blocks. Accommodating the random write pages could avoid prematurely merging the data block and increase probability of reclaiming dead blocks which contains no live pages. However, we found that FAST is inefficient in handling the sequential write since the merging policy makes the sequential write log block be merged prematurely even though the sequential log block could be still kept in the log area. Thus, we proposed an effective mapping exchange method, called MESOR, to reduce merge operations in FAST FTL and utilize the free space of sequential write log block as best as it can. MESOR could also be applied to other FAST-based FTLs such as HFTL and improve their performances. Simulation results show that MESOR reduces FAST and HFTL in term of cleaning cost by up to 93% and 66.8%, respectively.

[1] Microsoft Corporation, SQLIOsim. http://support.microsoft.com/kb/231619.
[2] Samsung Electronics, "K9K4G08U0M 512M x 8 Bit NAND Flash Memory Data Sheet," 2005. http://www.datasheetcatalog.org/datasheets/700/389215_DS.pdf
[3] A. Ban, "Flash File Systems," U.S. Patent no.5,404,485, 1995.
[4] K. Bates and B. McNutt, (2007), OLTP I/O Traces. http://traces.cs.umass.edu/index.php/storage/storage
[5] M.-L. Chiang, P. C. H. Lee, and R.-C. Chang, "Using Data Clustering to Improve Cleaning Performance for Flash Memory," Softw. Pract. Exper., vol. 29, pp. 267-290, 1999.
[6] M.-L. Chiang, P. C. H. Lee, and R.-C. Chang, "Cleaning Policies in Mobile Computers Using Flash Memory," Journal of Systems and Software, vol. 48, pp. 213-231, 1999.
[7] W. Chin-Hsien and K. Tei-Wei, "An Adaptive Two-Level Management for the Flash Translation Layer in Embedded Systems," in Computer-Aided Design, 2006. ICCAD '06. IEEE/ACM International Conference on, pp. 601-606, 2006.
[8] A. Gupta, Y. Kim, and B. Urgaonkar, "DFTL: A Flash Translation Layer Employing Demand-based Selective Caching of Page-level Address Mappings," in ASPLOS '09: Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, New York, NY, USA, pp. 229-240, 2009.
[9] J.-W. Hsieh, T.-W. Kuo, and L.-P. Chang, "Efficient Identification of Hot Data for Flash Memory Storage Systems," Trans. Storage, vol. 2, pp. 22-40, 2006.
[10] L. Hyun-Seob, Y. Hyun-Sik, and L. Dong-Ho, "HFTL: Hybrid Flash Translation Layer Based on Hot Data Identification for Flash Memory," Consumer Electronics, IEEE Transactions on, vol. 55, pp. 2005-2011, 2009.
[11] K. Jesung, K. Jong Min, S. H. Noh, M. Sang Lyul, and C. Yookun, "A Space-Efficient Flash Translation Layer for CompactFlash Systems," Consumer Electronics, IEEE Transactions on, vol. 48, pp. 366-375, 2002.
[12] D. Jung, J.-U. Kang, H. Jo, J.-S. Kim, and J. Lee, "Superblock FTL: A Superblock-based Flash Translation Layer with a Hybrid Address Translation Scheme," ACM Trans. Embed. Comput. Syst., vol. 9, pp. 1-41, 2010.
[13] J. Katcher, Network Appliance, "PostMark: A New File System Benchmark," Oct. 1997.
[14] A. Kawaguchi, S. Nishioka, and H. Motoda, "A Flash-Memory Based File System," presented at the Proceedings of the 1995 USENIX Technical Conference, Jan. 1995.
[15] H. Kim, J.-H. Kim, S. Choi, H. Jung, and J. Jung, "A Page Padding Method for Fragmented Flash Storage," in Computational Science and Its Applications – ICCSA 2007. vol. 4705, O. Gervasi and M. Gavrilova, Eds., ed: Springer Berlin / Heidelberg, 2007, pp. 164-177.
[16] S.-W. Lee, et al., "A Log Buffer-Based Flash Translation Layer Using Fully-Associative Sector Translation," ACM Trans. Embed. Comput. Syst., vol. 6, p. 18, 2007.
[17] S. Lee, D. Shin, Y.-J. Kim, and J. Kim, "LAST: Locality-Aware Sector Translation for NAND Flash Memory-Based Storage Systems," SIGOPS Oper. Syst. Rev., vol. 42, pp. 36-42, 2008.
[18] S.-P. Lim, S.-W. Lee, and B. Moon, "FASTer FTL for Enterprise-Class Flash Memory SSDs," 2009.
[19] R. Mcdougall and J. Mauro, FileBench. http://www.solarisinternals.com/wiki/index.php/FileBench
[20] B.-W. Nam, G.-J. Na, and S.-W. Lee, "A Hybrid Flash Memory SSD Scheme for Enterprise Database Applications," in Web Conference (APWEB), 2010 12th International Asia-Pacific, pp. 39-44, 2010.
[21] C. Park, et al., "A Reconfigurable FTL (Flash Translation Layer) Architecture for NAND Flash-Based Applications," ACM Trans. Embed. Comput. Syst., vol. 7, pp. 1-23, 2008.
[22] L. Pei-Kuan, C. Mong-Ling, and C. Da-Wei, "Improving flash translation layer performance by supporting large superblocks," Consumer Electronics, IEEE Transactions on, vol. 56, pp. 642-650, 2010.
[23] P. Torelli, "The Microsoft Flash File System," Dr. Dobb's Journal, pp. 62-72, Feb. 1995.