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 벤치마크와 임베디드 시스템 워크로드를 사용한 실험 결과는 이러한 비용 기반 선택이 플래시 메모리 기반 저장 장치의 성능을 향상시킬 수 있음을 보여준다. 아울러 이주/병합 연산이 조합된 각 주기마다 블록 재활용 비용을 최소화하는 이주/병합 순서의 거시적 최적화의 해를 발견하였으며, 실험 결과는 거시적 최적화가 단순 비용 기반 선택보다 플래시 메모리 기반 저장 장치의 성능을 더욱 향상시킬 수 있음을 보여준다.

SBBF: NAND 플래시 메모리 기반 B+-트리를 위한 공간 효율적인 버퍼 관리 기법

이기용,정연돈 한국차세대컴퓨팅학회 2011 한국차세대컴퓨팅학회 논문지 Vol.7 No.4

NAND 플래시 메모리는 스마트 폰, 휴대용 미디어 플레이어, 디지털 카메라, 노트북 등과 같은 다양한 모바일 장치의 저장 매체로서 사용이 점차 증대되고 있다. 플래시 메모리의 용량이 증가하면서, 플래시 메모리에서의 색인 구조의 사용도 점차 중요해지고 있다. B+-트리는 디스크 기반의 저장 시스템에서 가장 널리 쓰이는 인덱스 구조 중의 하나이다. 그러나 ‘쓰기 전 삭제’와 ‘비대칭적인 읽기/쓰기 속도’와 같은 플래시 메모리의 독특한 특성으로 인해, B+-트리 색인을 플래시 기반의 저장 시스템에 바로 적용하는 것은 심각한 쓰기 비용을 초래한다. 본 논문에서는 SBBF라 불리는, NAND 플래시 메모리에서의 B+-트리를 위한 공간 효율적인 버퍼 관리 기법을 제안한다. 제안 기법은 플래시 메모리로 보내지는 쓰기 요청의 수를 줄이기 위해, B+-트리의 변경 사항들을 버퍼에 저장한다. 기존 연구와 비교하여, 제안하는 방법은 버퍼 공간의 사용을 최적화하여 동일한 크기의 버퍼에 더 많은 변경 사항들을 저장할 수 있다. 이로 인해 플래시 메모리로 보내지는 쓰기 요청의 수를 크게 감소시킬 수 있다. 실제 데이터를 사용한 실험 결과를 통해, 제안 방법은 플래시 메모리로 보내지는 쓰기 요청의 수 측면에서 기존 방법에 비해 15% 이상의 성능 향상을 가져옴을 보인다. NAND flash memory is becoming widely used as storage media for various mobile devices such as smart phones, portable media players (PMPs), digital cameras, and laptops. As the capacity of flash memory increases, the use of index structures on flash memory becomes more important. The B+-tree is one of the most popular index structures used in disk-based storage systems. However, due to the unique characteristics of flash memory, such as erase-before-write, and asymmetric read/write speed, the direct application of B+-tree index structures to flash-based storage systems incurs excessive write overhead. In this paper, we propose a space-efficient buffer management scheme for B+-trees on NAND flash memory, called SBBF. The proposed scheme stores changes made to a B+-tree in the buffer to reduce the number of write requests to flash memory. Compared to previous work, the proposed scheme can store more changes in the same size buffer by optimizing the use of the buffer space. Consequently, the number of write requests to flash memory is significantly reduced. The experimental results with real workloads show that the proposed scheme outperforms previous work by over 15% in terms of the number of write requests to flash memory.

Dynamic Log Page Allocation Method for Flash Memory

송석일,길기정 한국정보기술학회 2011 JOURNAL OF ADVANCED INFORMATION TECHNOLOGY AND CON Vol.1 No.1

Due to advantages of NAND flash memory such as non-volatility, low access latency, low energy consumption, light weight, small size and shock resistance, it has become a better alternative over traditional magnetic disk drives, and has been widely used. Traditional DBMSs including mobile DBMSs may run on flash memory without any modification by using Flash Translation Layer (FTL), which emulates a random access block device to hide the characteristics of flash memory such as “erase-before-update”. However, most existing FTLs are optimized for file systems, not for DBMSs, and traditional DBMSs are not aware of them. Also, traditional DBMSs do not consider the characteristics of flash memory. In this paper, we propose a flash-conscious storage system for DBMSs that utilizes flash memory as a main storage medium, and carefully put the characteristics of flash memory into considerations. The proposed flash-conscious storage system exploits log records to avoid costly update operations. It is shown that the proposed storage system outperforms the state of the art flash-conscious DBMSs through the simulation.

ComboFTL: Improving performance and lifespan of MLC flash memory using SLC flash buffer

Im, S.,Shin, D. Elsevier 2010 JOURNAL OF SYSTEMS ARCHITECTURE - Vol.56 No.12

Multi-level cell (MLC) flash memory has lower bit cost compared to single-level cell (SLC) flash memory. However, there are several obstacles to the wide use of MLC flash memory, including slow write performance and shorter lifespan. To improve the performance and lifespan of MLC flash memory, we propose an FTL (flash translation layer) for MLC flash memory, called ComboFTL. By exploiting the SLC mode of MLC flash memory, ComboFTL manages a small SLC region for hot data and a large MLC region for cold data. To provide the performance and lifespan similar to those of SLC flash memory, ComboFTL identifies the hotness/coldness of data effectively. It can also adjust its several policies based on workload changes. Our experimental results showed that ComboFTL improves the write performance and lifespan of MLC flash memory significantly.

A comprehensive study of energy efficiency and performance of flash-based SSD

Park, S.,Kim, Y.,Urgaonkar, B.,Lee, J.,Seo, E. Elsevier 2011 JOURNAL OF SYSTEMS ARCHITECTURE - Vol.57 No.4

Use of flash memory as a storage medium is becoming popular in diverse computing environments. However, because of differences in interface, flash memory requires a hard-disk-emulation layer, called FTL (flash translation layer). Although the FTL enables flash memory storages to replace conventional hard disks, it induces significant computational and space overhead. Despite the low power consumption of flash memory, this overhead leads to significant power consumption in an overall storage system. In this paper, we analyze the characteristics of flash-based storage devices from the viewpoint of power consumption and energy efficiency by using various methodologies. First, we utilize simulation to investigate the interior operation of flash-based storage of flash-based storages. Subsequently, we measure the performance and energy efficiency of commodity flash-based SSDs by using microbenchmarks to identify the block-device level characteristics and macrobenchmarks to reveal their filesystem level characteristics.

Hardware Platforms for Flash Memory/NVRAM Software Development

Eyee Hyun Nam,Ki Seok Choi,Jin-yong Choi,Hang Jun Min,Sang Lyul Min 한국정보과학회 2009 Journal of Computing Science and Engineering Vol.3 No.3

Flash memory is increasingly being used in a wide range of storage applications because of its low power consumption, low access latency, small form factor, and high shock resistance. However, the current platforms for flash memory software development do not meet the everincreasing requirements of flash memory applications. This paper presents three different hardware platforms for flash memory/NVRAM (non-volatile RAM) software development that overcome the limitations of the current platforms. The three platforms target different types of host system and provide various features that facilitate the development and verification of flash memory/NVRAM software. In this paper, we also demonstrate the usefulness of the three platforms by implementing three different types of storage system (one for each platform) based on them.

NAND 플래시 메모리 기반 B+ 트리에서 페이지 매핑 로그를 이용한 색인 관리 기법

김선환(Seon Hwan Kim),곽종욱(Jong Wook Kwak) 한국컴퓨터정보학회 2015 韓國컴퓨터情報學會論文誌 Vol.20 No.5

낸드 플래시 메모리는 저전력, 빠른 접근 속도, 저렴한 가격 등의 특징을 가지고 있어 저장장치로 널리 사용되고 있다. 하지만 낸드 플래시 메모리는 제자리 덮어쓰기가 지원되지 않아 기존의 하드 디스크 기반 응용 프로그램을 구동하기 위해서는 FTL(Flash Translation Layer)이 필요하다. FTL은 주소 매핑, 가비지 컬렉션, 마모도 균등화 작업 등을 포함하고 있어 저사양 임베디드 장치에 구현하기에는 메모리와 연산에 대한 비용이 많이 든다. 그래서 이런 장치들을 위해 낸드 플래시 메모리에 최적화된 색인 자료구조들이 연구되고 있다. 연구된 방법들은 쓰기에 소요되는 시간을 줄여 성능을 향상시켰지만 레코드 탐색에 소요되는 시간이 증가된다는 단점을 가지고 있다. 레코드 탐색시간을 증가시키지 않고 쓰기 횟수를 줄이기 위해 본 논문에서는 페이지 매핑 로그 테이블을 이용한 색인 관리 기법을 제안한다. 낸드 플래시 메모리의 단점인 제자리 덮어쓰기 불가로 인해 발생하는 페이지 쓰기 횟수를 줄이기 위해 매핑 로그 테이블은 B+ 트리에서 변경된 노드 페이지 주소를 저장하고 레코드 검색 시 이를 이용한다. 실험 평가를 통해 제안된 기법은 다른 기법들과 비교 시 레코드 탐색에서 발생하는 페이지 읽기 횟수를 최대 약 61% 줄였으며, 레코드 삽입에서 페이지 쓰기 횟수를 최대 약 31% 줄일 수 있었다. NAND flash memory has being used for storage systems widely, because it has good features which are low-price, low-power and fast access speed. However, NAND flash memory has an in-place update problem, and therefore it needs FTL(flash translation layer) to run for applications based on hard disk storage. The FTL includes complex functions, such as address mapping, garbage collection, wear leveling and so on. Futhermore, implementation of the FTL on low-power embedded systems is difficult due to its memory requirements and operation overhead. Accordingly, many index data structures for NAND flash memory have being studied for the embedded systems. Overall performances of the index data structures are enhanced by a decreasing of page write counts, whereas it has increased page read counts, as a side effect. Therefore, we propose an index management method using a page mapping log table in B?-Tree based on NAND flash memory to decrease page write counts and not to increase page read counts. The page mapping log table registers page address information of changed index node and then it is exploited when retrieving records. In our experiment, the proposed method reduces the page read counts about 61% at maximum and the page write counts about 31% at maximum, compared to the related studies of index data structures.

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

윤진혁(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.

플래시 메모리 기반 인덱스 구조에서 대리블록 이용한 가비지 컬렉션 기법

김선환(Seon Hwan Kim),곽종욱(Jong Wook Kwak) 한국컴퓨터정보학회 2015 韓國컴퓨터情報學會論文誌 Vol.20 No.6

낸드 플래시 메모리는 빠른 접근 시간과 저전력의 특성을 가지고 있어 저장장치로 많이 사용되고 있는 추세이다. 하지만 저사양의 임베디드 장치에서는 메모리 요구사항과 구현상의 복잡성으로 FTL을 적용하기에는 비용이 많이든다. 이러한 이유로 FTL을 구현하기 힘든 임베디드 장치에 적용할 수 있는 B+ 트리 연구들이 다수 제안되었다. 이런 연구들은 낸드 플래시 메모리에서 제자리 업데이트가 불가하다는 단점을 고려하여 삽입과 갱신의 성능을 최적화 하였다. 하지만 B+ 트리에 기존의 가비지 컬렉션 기법들을 적용하면 낸드 플래시 메모리의 페이지 위치를 변경하게 되고 B+ 트리의 재구성을 발생시켜 전체적인 성능을 저하시킨다. 이러한 문제를 해결하고자 본 논문에서는 낸드 플래시 메모리를 기반으로 하는 B+ 트리와 이와 유사한 인덱스 트리 구조에 적용할 수 있는 가비지 컬렉션 기법을 제안한다. 제안하는 가비지 컬렉션 기법은 블록 정보 테이블과 대리 블록을 이용하여 B+ 트리의 재구성을 발생시키지 않는다. 제안된 기법의 성능평가를 위해, 낸드 플래시 메모리가 장착된 실험 장치에 B+ 트리와 μ-Tree를 구현하고 제안된 기법을 적용하였다. 구현 결과 B+ 트리에서 제안된 기법이 GAGC(Greedy Algorithm Garbage Collection)보다 삽입된 키의 개수가 약 73% 많았으며, μ-Tree에서 제안된 기법이 GAGC보다 시간 오버헤드가 약 39% 적었다. Recently, NAND flash memories are used for storage devices because of fast access speed and low-power. However, applications of FTL on low power computing devices lead to heavy workloads which result in a memory requirement and an implementation overhead. Consequently, studies of B+-Tree on embedded devices without the FTL have been proposed. The studies of B+-Tree are optimized for performance of inserting and updating records, considering to disadvantages of the NAND flash memory that it can not support in-place update. However, if a general garbage collection method is applied to the previous studies of B+-Tree, a performance of the B+-Tree is reduced, because it generates a rearrangement of the B+-Tree by changing of page positions on the NAND flash memory. Therefor, we propose a novel garbage collection method which can apply to the B+-Tree based on the NAND flash memory without the FTL. The proposed garbage collection method does not generate a rearrangement of the B+-Tree by using a block information table and a proxy block. We implemented the B+-Tree and μ-Tree with the proposed garbage collection on physical devices with the NAND flash memory. In experiment results, the proposed garbage collection scheme compared to greedy algorithm garbage collection scheme increased the number of inserted keys by up to about 73% on B+-Tree and decreased elapsed time of garbage collection by up to about 39% on μ-Tree.

에러 분포의 비대칭성을 활용한 대용량 3D NAND 플래시 메모리의 신뢰성 최적화 기법

김명석 대한임베디드공학회 2023 대한임베디드공학회논문지 Vol.18 No.1

Recent advances in flash technologies, such as 3D processing and multileveling schemes, have successfully increased the flash capacity. Unfortunately, these technology advances significantly degrade flash’s reliability due to a smaller cell geometry and a finer-grained cell state control. In this paper, we propose an asymmetric BER-aware reliability optimization technique (aBARO), new flash optimization that improves the flash reliability. To this end, we first reveal that bit errors of 3D NAND flash memory are highly skewed among flash cell states. The proposed aBARO exploits the unique per-state error model in flash cell states by selecting the most error-prone flash states and by forming narrow threshold voltage distributions (for the selected states only). Furthermore, aBARO is applied only when the program time (tPROG) gets shorter when a flash cell becomes aging, thereby keeping the program latency of storage systems unchanged. Our experimental results with real 3D MLC and TLC flash devices show that aBARO can effectively improve flash reliability by mitigating a significant number of bit errors. In addition, aBARO can also reduce the read latency by 40%, on average, by suppressing the read retries.