NAND 플래시 메모리 저장 장치에서 블록 재활용 기법의 비용 기반 최적화

이종민(Jongmin Lee),김성훈(Sunghoon Kim),안성준(Seongjun Ahn),이동희(Donghee Lee),노삼혁(Sam H. Noh) 한국정보과학회 2007 정보과학회 컴퓨팅의 실제 논문지 Vol.13 No.7

Flash memory based storage has been used in various mobile systems and now is to be used in Laptop computers in the name of Solid State Disk. The Flash memory has not only merits in terms of weight, shock resistance, and power consumption but also limitations like erasebefore-write property. To overcome these limitations, Flash memory based storage requires special address mapping software called FTL(Flash-memory Translation Layer), which often performs merge operation for block recycling. In order to reduce block recycling cost in NAND Flash memory based storage, we introduce another block recycling scheme which we call migration. As a result, the FTL can select either merge or migration depending on their costs for each block recycling. Experimental results with Postmark benchmark and embedded system workload show that this cost-based selection of migration/merge operation improves the performance of Flash memory based storage. Also, we present a solution of macroscopic optimal migration/merge sequence that minimizes a block recycling cost for each migration/merge combination period. Experimental results show that the performance of Flash memory based storage can be more improved by the macroscopic optimization than the simple cost-based selection. 이동기기의 저장 장치로 사용되는 플래시 메모리는 이제 SSD(Solid State Disk) 형태로 노트북 컴퓨터까지 그 적용 범위가 확대되고 있다. 이러한 플래시 메모리는 무게, 내충격성, 전력 소비량 면에서 장점을 가지고 있지만, erase-before-write 속성과 같은 단점도 가진다. 이러한 단점을 극복하기 위하여 플래시 메모리 기반 저장 장치는 FTL(Flash-memory Translation Layer)이라는 특별한 주소 사상소프트웨어를 필요로 하며, FTL은 종종 블록을 재활용하기 위하여 병합 연산을 수행해야 한다. NAND 플래시 메모리 기반 저장 장치에서 블록 재활용 비용을 줄이기 위해 본 논문에서는 이주 연산이라는 또 다른 블록 재활용 기법을 도입하였으며, FTL은 블록 재활용시 이주와 병합 연산 중에서 비용이 적게 드는 연산을 선택하도록 하였다. Postmark 벤치마크와 임베디드 시스템 워크로드를 사용한 실험 결과는 이러한 비용 기반 선택이 플래시 메모리 기반 저장 장치의 성능을 향상시킬 수 있음을 보여준다. 아울러 이주/병합 연산이 조합된 각 주기마다 블록 재활용 비용을 최소화하는 이주/병합 순서의 거시적 최적화의 해를 발견하였으며, 실험 결과는 거시적 최적화가 단순 비용 기반 선택보다 플래시 메모리 기반 저장 장치의 성능을 더욱 향상시킬 수 있음을 보여준다.

카운팅 블룸필터를 활용한 FAST FTL 로그영역 탐색성능 개선

강운학(WoonHak Kang),이상원(SangWon Lee) 한국정보과학회 2011 정보과학회논문지 : 데이타베이스 Vol.38 No.3

낸드 플래시 메모리(NAND flash memory)를 사용한 저장장치는 빠른 읽기/쓰기 성능, 저 전력, 충격에 강한 장점들로 인해 사용영역을 넓혀가고 있다. 지금까지 제안된 많은 FTL 기법 중에서, FAST는 논리적 페이지와 물리적 페이지 사이의 완전연관성을 사용하여 로그영역을 관리함으로써, 임의쓰기 성능이 아주 우수한 것으로 알려져 있다. 그러나 모든 읽기/쓰기/병합 연산마다 해당 페이지의 최신 버전이 로그영역에 존재하는지 먼저 확인해야 하는 부담이 있다. Flash SSD(Solid State Disk)를 포함해서, 낸드플래시 메모리 기반의 저장장치가 대용량화함에 따라, 쓰기버퍼 역할을 하는 FAST의 로그영역도 증가하게 될 것이며, 사상테이블에 대한 스캔 방식의 로그 영역 검색은 확장성에 문제가 있다. 본 논문에서는, FAST 로그영역에 대한 탐색비용을 획기적으로 개선하는 확장성 있는 검색기법으로, 카운팅 블룸필터를 응용하는 방식을 제시한다. 제안한 기법은 플래시메모리 컨트롤러와 같이 메모리 사용량이 제한된 환경에서, 주어진 데이터페이지의 최신 버전이 FAST 로그영역에 존재하는지를 아주 빨리 결정할 수 있다. 성능평가 결과, 제안한 기법이 비트맵 대비 30% 메모리만을 사용하고도 평균 80% 탐색을 회피할 수 있었다. 카운팅 블룸필터가 높은 회피율과 낮은 긍정오류를 보이기 때문에, FAST의 로그영역 탐색에 아주 효과적임을 알 수 있다. NAND flash memory storage devices has been widely adopted in many applications, due to its good characteristics. Unlike hard disk drive, however, flash memory does not allow in-place update so that a block should be erased before a page of the block is overwritten. Several FTL algorithms have been proposed during the past decade, among them, FAST scheme is popular for its random write performance because of its full associativity between logical data pages and physical flash pages in log blocks (called log area). However, on every read/write/merge operations, FAST should check whether the most recent version of a page exists in log blocks. But, even though the mapping table resides in SRAM, this full scan of the mapping table for checking the existence of the up-to-date page in the log block is not any more trivial as the size of flash-based storage grows exponentially and thus the number of log blocks should accordingly increase for reasonable random write performance. As a scalable search scheme for log area, this paper applies the counting bloom filters to efficiently check whether the recent copy of a page exist in the log area of FAST scheme. To be specific, with a very small footprint of memory, which is very common in resource-limited flash memory controllers, the counting bloom filter can quickly determine a recent version of the given data page does not reside in log area when it does not have its recent copy in log area. The performance evaluation shows that our scheme can improve the search cost of log area by more than 80% with only exploit 30% of memory compare to bitmap scheme.

참조 패턴에 따라 페이지 및 블록 사상 영역의 크기를 조절하는 Janus-FTL

권훈기(Hunki Kwon),김은삼(Eunsam Kim),최종무(Jongmoo Choi),이동희(Donghee Lee),노삼혁(Sam H. Noh) 한국정보과학회 2009 정보과학회 컴퓨팅의 실제 논문지 Vol.15 No.12

본 논문에서는 참조 패턴에 따라 페이지 사상정책과 블록 사상 정책을 선택적으로 사용하는 Janus-FTL을 제안한다. 일반적으로 플래시 메모리의 특성에 따르면, 순차 참조의 경우 블록 사상 FTL이 적당하고, 비 순차적인 참조의 경우 페이지 사상 FTL이 적당하다. 따라서 실용적인 FTL은 데이터의 특성에 따라 플래시 메모리 블록을 블록 사상 또는 페이지 사상 정책으로 선택적으로 사용하면서, 블록 사상 영역과 페이지 사상 영역의 크기를 참조 패턴에 따라 효율적으로 변화하여 할당하는 관리 기법이 필요하다. 본 논문에서는 저장된 데이터가 블록 사상 영역에서 페이지 사상 영역으로 이동하는 퓨전(Fusion) 연산과 반대로 이동하는 디퓨전(Defusion) 연산을 통해, 블록 사상과 페이지 사상 기법을 동시에 활용하는 Janus-FTL을 설명한다. 또한 Janus-FTL을 구현하여 성능을 측정하였으며, 성능 측정 결과에 따르면 기존의 FTL에 비해 최대 50%의 우수한 성능을 보였다. Naturally, block mapping FTL works well for sequential writes while page mapping FTL does well for random writes. To exploit their advantages, a practical FTL should be able to selectively apply a suitable scheme between page and block mappings for each write pattern. To meet that requirement, we propose a hybrid mapping FTL, which we call Janus-FTL, that distributes data to either block or page mapping areas. Also, we propose the fusion operation to relocate the data from block mapping area to page mapping area and the defusion operation to relocate the data from page mapping area to block mapping area. And experimental results of Janus-FTL show performance improvement of maximum 50% than other hybrid mapping FTLs.

RAID 기반 플래시 저장장치를 위한 수명 인지 신뢰성 향상 기법

이세환(Sehwan Lee),이빛나(Bitna Lee),고건(Kern Koh),반효경(Hyokyung Bahn) 한국정보과학회 2011 정보과학회논문지 : 시스템 및 이론 Vol.38 No.4

플래시 메모리 기반 저장 장치는 저전력 고성능의 장점과 더불어 용량이 점차 증가하면서, 서버 시스템에 이르기까지 채용될 것으로 전망되고 있다. 그와 함께 플래시 메모리의 신뢰성 문제 역시 점차 중요해지고 있다. 각 플래시 블록에 허용된 쓰기/삭제 횟수는 제한되어 있으며, 특히 MLC 플래시 메모리의 경우는 그 횟수가 10,000회 이하이다. 또한 플래시 메모리의 쓰기/삭제 횟수가 증가함에 따라 비트에러 발생률이 급격하게 증가한다. 이러한 문제를 해결하기 위해, 본 논문에서는 RAID 기반의 플래시 저장장치를 위한 수명 기반 신뢰성 관리 기법을 제안한다. 첫째, 제안하는 기법은 쓰기/삭제 횟수 증가에 따라 플래시 메모리의 에러 발생률이 함께 증가하는 문제를 해결하기 위하여 스트라이핑 그룹의 크기를 동적으로 관리한다. 둘째, 제안하는 기법은 플래시 메모리의 특성을 고려한 로그 블록 FTL 기법을 이용한다. 이것은 데이터 영역과 로그 영역이 서로 다른 쓰기 패턴을 갖는 특징을 활용하여 각 영역에 대하여 서로 다른 신뢰성 정책을 적용하는 것이다. 셋째, 제안하는 기법은 임시로 패리티 블록을 저장하는 소량의 SCM을 사용한다. 이는 빈번한 패리티 업데이트가 즉시 플래시 메모리에 적용되지 않도록 함으로써 플래시 메모리의 수명을 연장시킨다. 실험 결과에서 제안하는 기법은 기존의 RAID-5에 비해 적은 공간 오버헤드와 높은 신뢰성을 보이면서 입출력 성능은 패리티 블록을 사용하지 않는 RAID-0과 대등한 성능을 보였다. Due to the ever-growing capacity of flash memory along with its good properties such as low-power consumption and high performance, flash-based SSDs (solid state disks) are anticipated to be used in the storage of high-end server systems. However, the reliability problem of flash devices is becoming increasingly serious. The number of P/E (program/erase) cycles allowed to each flash block is too small, especially less than 10,000 for MLC (multi-level cell) flash memory. Furthermore, the bit error rate of flash memory becomes rapidly high as the number of P/E cycles increases. To relieve these problems, we present a lifespan-aware reliability scheme, which adopts RAID technologies together with ECCs (error correction codes). First, our scheme dynamically manages the size of striping group to cope with the increasing error rates of flash memory as the number of P/E cycles increases. Second, we use a device-aware log block mapping scheme, which uses different reliability policies for data blocks and log blocks by taking advantage of the characteristics of each block type. Third, we use small amount of storage class memory (SCM) to save parity blocks temporarily. By absorbing frequent updates of parity into SCM, we can extend the lifespan of flash memory. Simulation experiments show that our scheme obtains high reliability with minimum space overhead as well as improved I/O performances compared to traditional RAID-5.

고성능 대용량 플래시 메모리 저장장치의 효과적인 매핑정보 캐싱을 위한 적응적 매핑정보 관리기법

이용주(Yongju Lee),김현우(Hyunwoo Kim),김희정(Huijeong Kim),허태영(Taeyeong Huh),정상혁(Sanghyuk Jung),송용호(Yong Ho Song) 대한전자공학회 2013 전자공학회논문지 Vol.50 No.3

모바일 디바이스, PC, 서버 형 워크스테이션 시스템에서 널리 사용되고 있는 낸드 플래시 메모리는 기존의 하드 디스크에 비해 저 전력 소비, 높은 성능, 랜덤 접근 가능 등의 장점을 갖는 반면, 덮어쓰기가 불가능하여 데이터를 쓰기 전에는 항상 삭제 연산을 필요로 하는 구조적 약점을 지니고 있다. 이를 극복하기 위해 낸드 플래시 메모리의 제어기는 FTL을 사용하여 디바이스 내부 연산을 변형시킨다. 하지만 고성능 대용량 낸드 플래시 메모리 저장장치의 사용이 증가됨에 따라, 제한된 DRAM 크기에 비해 매핑 알고리즘에서 사용되는 매핑 테이블의 크기가 증가하는 문제가 발생한다. 본 논문은 이러한 DRAM의 용량 부족 문제를 해결하기 위해, 페이지 매핑 기법을 바탕으로한 적응적 매핑정보 캐싱 기법을 제안한다. 적응적 매핑정보 캐싱 알고리즘은 다양한 워크로드 분석을 기반으로 낸드 플래시 접근을 최소한으로 하는 매핑정보 캐싱 방식을 사용한다. 트레이스 기반 시뮬레이터를 통해 실험한 결과, 본 논문에서 제시하는 적응적 매핑정보 캐싱 알고리즘은 기존의 고정 매핑정보 캐싱 알고리즘에 비해 최소 7%에서 최대 70%의 성능향상을 보임을 확인할 수 있었다. NAND flash memory has been widely used as a storage medium in mobile devices, PCs, and workstations due to its advantages such as low power consumption, high performance, and random accessability compared to a hard disk drive. However, NAND flash cannot support in-place update so that it is mandatory to erase the entire block before overwriting the corresponding page. In order to overcome this drawback, flash storages need a software support, named Flash Translation Layer. However, as the high performance mass NAND flash memory is getting widely used, the size of mapping tables is increasing more than the limited DRAM size. In this paper, we propose an adaptive mapping information caching algorithm based on page mapping to solve this DRAM space shortage problem. Our algorithm uses a mapping information caching scheme which minimize the flash memory access frequency based on the analysis of several workloads. The experimental results show that the proposed algorithm can increase the performance by up to 70% comparing with the previous mapping information caching algorithm.

MLC 낸드 플래시 기반 저장장치의 쓰기 성능 개선을 위한 계층 교차적 최적화 기법

박지성(Jisung Park),이성진(Sungjin Lee),김지홍(Jihong Kim) Korean Institute of Information Scientists and Eng 2017 정보과학회논문지 Vol.44 No.11

The multi-leveling technique that stores multiple bits in a single memory cell has significantly improved the density of NAND flash memory along with shrinking processes. However, because of the side effects of the multi-leveling technique, the average write performance of MLC NAND flash memory is degraded more than twice that of SLC NAND flash memory. In this paper, we introduce existing cross-layer optimization techniques proposed to improve the performance of MLC NAND flash-based storages, and propose a new integration technique that overcomes the limitations of existing techniques by exploiting their complementarity. By fully exploiting the performance asymmetry in MLC NAND flash devices at the flash translation layer, the proposed technique can handle many write requests with the performance of SLC NAND flash devices, thus significantly improving the performance of NAND flash-based storages. Experimental results show that the proposed technique improves performance 39% on average over individual techniques.

SSD FTL의 캐시 메커니즘에 대한 심층 분석 및 개선

이형봉,정태윤 대한임베디드공학회 2020 대한임베디드공학회논문지 Vol.15 No.1

Recently, the capacity of SSD has been increasing rapidly due to the improvement of flash memory density. To take full advantage of these SSDs, first of all, FTL's prompt adaptation is necessary. The FTL is a translation layer existing in SSDs to overcome the drawback of the SSD that cannot be modified in place, and has garbage collection and caching functions in addition to the map table management function. In this study, we focus on caching function, compare and analyze the cache implementation methodologies, and propose improved methods. Typical cache implementations divide the cache into groups, manage and retrieve the caches in the group as a linked list. Thus, searches are made in the order of the linked list. In contrast, we propose a method of sequential searching using the search area group of a cache registered in the map table regardless of the linked list and cache group. Experimental results show that the proposed method has a 2.5 times improvement over the conventional method.

An Empirical Study of FTL Performance in Conjunction with File System Pursuing Data Integrity

DOH, In Hwan,SHIM, Myoung Sub,KIM, Eunsam,CHOI, Jongmoo,LEE, Donghee,NOH, Sam H. The Institute of Electronics, Information and Comm 2010 IEICE transactions on information and systems Vol.93 No.8

<P>Due to the detachability of Flash storage, which is a dominant portable storage, data integrity stored in Flash storages becomes an important issue. This study considers the performance of Flash Translation Layer (FTL) schemes embedded in Flash storages in conjunction with file system behavior that pursue high data integrity. To assure extreme data integrity, file systems synchronously write all file data to storage accompanying hot write references. In this study, we concentrate on the effect of hot write references on Flash storage, and we consider the effect of absorbing the hot write references via nonvolatile write cache on the performance of the FTL schemes in Flash storage. In so doing, we quantify the performance of typical FTL schemes for a realistic digital camera workload that contains hot write references through experiments on a real system environment. Results show that for the workload with hot write references FTL performance does not conform with previously reported studies. We also conclude that the impact of the underlying FTL schemes on the performance of Flash storage is dramatically reduced by absorbing the hot write references via nonvolatile write cache.</P>

실시간 시스템용 낸드 플래시 메모리를 위한 로그 버퍼 관리 기법

조현진(Hyunjin Cho),하병민(Byung Min Ha),신동군(Dongkun Shin),엄영익(Young Ik Eom) 한국정보과학회 2009 정보과학회논문지 : 시스템 및 이론 Vol.36 No.6

플래시 메모리는 일관된 성능, 저전력 및 내구성 등의 특징으로 인해 실시간 시스템에 적합한 저장장치로 주목 받고 있다. 하지만 플래시 메모리는 무효화된 페이지의 가비지 컬렉션 수행을 위한 정체시간(blocking time)을 필요로 하는데, 기존의 플래시 메모리 관리 기법에서는 가비지 컬렉션을 위한 최대 정체 시간(worst case blocking time)과 최소 정체 시간(best case blocking time)의 차가 크다는 문제점이 있다. 본 논문에서는 KAST라 불리는 FTL(Flash Translation Layer)을 제안하며, 제안 시스템에서 사용자는 가비지 컬렉션에 따른 최대 정체 시간을 설정할 수 있도록 한다. 실험을 통해 KAST는 사용자가 설정한 시간 내 가비지 컬렉션을 완료하며, 기존 FTL 보다 10~15% 성능 향상을 보임을 확인한다. Flash memory is suitable for real time systems because of its consistent performance for random access, low power consumption and shock resistance. However, flash memory needs blocking time to perform a garbage collection to reclaim invalidated pages. Moreover, the worst-case garbage collection time is significantly longer than the best-case garbage collection time. In this paper, we propose a FTL (Flash Translation Layer) mapping scheme called KAST (K-Associative Sector Translation). In the KAST scheme, user can control the maximum association of the log block to limit the worst-case garbage collection time. Performance evaluation using simulation shows that not only KAST completes the garbage collection within the specified time but also provides about 10~15% better average performance than existing FTL schemes.

고성능 플래시 메모리 솔리드 스테이트 디스크

윤진혁(Jin Hyuk Yoon),남이현(Eyee Hyun Nam),성윤제(Yoon Jae Seong),김홍석(Hongseok Kim),민상렬(Sang Lyul Min),조유근(Yookun Cho) 한국정보과학회 2008 정보과학회 컴퓨팅의 실제 논문지 Vol.14 No.4

플래시 메모리는 전력 소모가 작고 충격과 진동에 강하며 크기가 작다는 특성 때문에 최근 노트북이나 UMPC(Ultra Mobile PC)와 같은 이동 컴퓨팅 시스템에서 하드디스크를 대체할 대용량 저장 매체로서 주목 받고 있다. 플래시 메모리에 기반한 저장 장치는 일반적으로 랜덤 읽기 성능이나 순차 읽기, 순차 쓰기 성능이 매우 좋은데 비해, 덮어쓰기가 불가능한 플래시 메모리의 물리적인 제약으로 인하여 소량의 랜덤 쓰기 성능은 떨어진다. 본 논문은 이 문제를 해결하기 위한 두 가지 중요한 특징을 갖는 SSD(Solid State Disk) 아키텍처를 제안하였다. 첫 번째로 비휘발성 이면서도 SRAM과 동일한 인터페이스로 덮어쓰기가 가능한 작은 크기의 FRAM(Ferroelectric RAM)을 NAND 플래시 메모리와 함께 사용하여 소량 쓰기 오버헤드를 최소화하였다. 두 번째, 호스트 쓰기 요청들도 소량 랜덤 쓰기와 대량 순차 쓰기로 분류하여 각각에 대해 최적의 쓰기 버퍼 관리 방법을 적용하였다. 평가 보드 상에서 SSD 프로토타입을 구현하고 PC 사용 환경의 워크로드에 기반한 벤치마크를 이용하여 성능을 평가해 본 결과 랜덤 패턴을 보이는 워크로드에서는 하드디스크나 기존의 상용 SSD들에 비해 처리율(throughput) 측면에서 3배 이상의 성능을 보였다. Flash memory has been attracting attention as the next mass storage media for mobile computing systems such as notebook computers and UMPC(Ultra Mobile PC)s due to its low power consumption, high shock and vibration resistance, and small size. A storage system with flash memory excels in random read, sequential read, and sequential write. However, it comes short in random write because of flash memory's physical inability to overwrite data, unless first erased. To overcome this shortcoming, we propose an SSD (Solid State Disk) architecture with two novel features. First, we utilize non-volatile FRAM (Ferroelectric RAM) in conjunction with NAND flash memory, and produce a synergy of FRAM's fast access speed and ability to overwrite, and NAND flash memory's low and affordable price. Second, the architecture categorizes host write requests into small random writes and large sequential writes, and processes them with two different buffer management, optimized for each type of write request. This scheme has been implemented into an SSD prototype and evaluated with a standard PC environment benchmark. The result reveals that our architecture outperforms conventional HDD and other commercial SSDs by more than three times in the throughput for random access workloads.