[논문]A Multi-Level Flash Translation Layer for Large Capacity Solid State Drives

Kim, Yong-Seok

doi:10.9708/jksci.2021.26.02.011

A Multi-Level Flash Translation Layer for Large Capacity Solid State Drives 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.26 no.2, 2021년, pp.11 - 18

Kim, Yong-Seok (Dept. of Computer Engineering, Kangwon National University)

초록
AI-Helper

SSD의 FTL에서는 호스트로부터 요청된 논리적 페이지 번호를 실제 기록된 플래시 메모리 페이지 번호로 매핑하는 작업을 한다. 매핑 정보를 관리하기 위해서 사용되는 RAM의 용량을 줄이는 것은 매우 중요하다. 기존의 요구기반 FTL에서는 매핑 정보도 플래시 메모리 페이지에 기록하고 그들의 주소만 RAM에 테이블로 관리하는 2단계 방법을 적용하였다. 그러나 SSD의 용량이 수십 테라바이트 수준으로 늘어나고 있으므로 이 방법만으로는 충분하지 않다. 본 논문에서는 소요되는 RAM의 용량을 획기적으로 줄이기 위해서 매핑 정보를 3단계로 관리하는 방법인 ML-FTL을 제안하고 그 성능을 평가하였다. 캐시를 적절히 활용함으로써 기존의 2단계 방법에 비해서 오버헤드가 늘어나는 정도가 미미하다는 것을 확인하였다.

Abstract ▼ AI-Helper

The flash translation layer(FTL) of SSD maps the logical page number requested from the host to the actual recorded flash memory page number. It is very important to reduce the amount of RAM used to manage the mapping information. In the existing demand-based FTLs, two-level method is applied in which mapping information is also recorded in flash memory pages and only their addresses are managed as a table in RAM. As the capacities of SSDs are growing to tens of terabytes, the amount of RAM for mapping table becomes too large. In this paper, ML-FTL was proposed as a method of managing mapping information in three levels to reduce the amount of RAM required drastically. From an evaluation, the increase in overhead was minimal compared to the conventional two-level method by properly utilizing cache.

주제어

표/그림 (11)

그림 Fig. 1. 2-Level Mapping Structure of DFTL
그림 Fig. 2. 3-Level Mapping Structure of ML-FTL
그림 Fig. 3. Determining PPN from LPN
그림 Fig. 4. DP Cache, TP cache and TPN Cache
그림 Fig. 5. Algorithm of Determining PPN from LPN
그림 Fig. 6. Algorithm of TP Cache Loading
그림 Fig. 7. Algorithm of DP Cache Loading
표 Table 1. Characteristics of UMass Traces
표 Table 2. Comparison of Overhead
그림 Fig. 8. Overhead According to the Number of DP Caches
그림 Fig. 9. Dividing Cache RAM for TP and DP

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

TP 캐시는 8개를 적용하였다. ML-FTLe DP 캐시를 8개추가하고 TPN 캐시를 위해서 1KB의 RAM을 추가한 경우에대한 평가 결과이다. 표 2와같이 ML-FTL의 오버헤드는 TPC-FTL에 비해서 늘어나기는 하지만 읽기/쓰기를 처리하는 전체 소요 시간에 비하면 아주 미미하다.
본 논문에서는 대용량 SSD를 위한 FTL에 대한 것으로서 LPN을 PPN으로 매핑하는 방법에 대한 문제를 다룬다. 모든 LPN들에 대하여 매핑 정보를 SSD 내부의 RAM에기록해 둘수 있다면 문제는 간단하지만, 비현실적으로 큰용량의 RAM을 필요로 한다.
따라서 GDT를 저장하기 위해서 32M x 4B = 128MB의 RAM이 필요하다. 본 논문에서는 대용량 SSD에서 GDT를 위한 RAM 용량을획기적으로 줄이는 방법으로서 DFTL의 2단계를 확장한 3 단계 매핑 테이블을 제안하고 그 유용성을 검증한다. 3단계로 확장하면 GDT를 위한 RAM의 용량을 1/512로 대폭줄일 수 있고, 단계가 늘어남으로 인한 추가 오버헤드는캐시를 적절히 활용함으로써 매우 작은 수준으로 제한할수 있음을 확인하였다.
본 논문에서는 소요되는 RAM의 용량을 획기적으로 줄이기 위해서 매핑 정보를 3단계로 관리하는 방법인 ML-FTL을 제안하고 그 성능을 평가하였다. 또한 3단계로 확장하는데 따른 오버헤드를 줄이기 위해서 캐시를 관리하는 방법도 제안하였다.
RAM에는 캐시뿐만 아니라 매핑 체계의 최상단 정보도 기록하여야 한다. 본 논문에서는 캐시 용량을 줄이는 것과는 별개로 RAM에 기록할 최상단 매핑 정보를 획기적으로 줄임으로써 RAM의 용량을 줄이는 방법을 다룬다. 특히 수십 테라바이트 이상의 대용량 SSD가 보편화되고 있는 상황에서 RAM의 용량을 현실적으로 적용이 가능한 수준으로 대폭줄일 수 있게 한다.
AALRU는 호스트의 워크로드가 변함에 따라 캐시를 관리하는 방법도 적응적으로 변화시키는 방법을 제안하였다 [8]. 이러한 방안들의 목표는 가능한한 RAM의 소요량을줄이면서도 매핑 과정의 오버헤드를 줄이는 것이다. 호스트에서 요청한 데이터 페이지의 읽기/쓰기 작업에 소요되는 시간 이외에 매핑 정보를 플래시 메모리 페이지에 기록하거나 읽어오는 추가적인 작업에 소요되는 시간은 모두오버헤드에 해당한다.

가설 설정

LPN 과 PPNe 32비트(4바이트)라고 가정한다. 3단계로 구성되므로 LPNe GDT 인덱스, DP 인덱스, 그리고 TP 인덱스의 3부분으로 구분한다.

제안 방법

ML-FTL에서 발생하는 오버헤드에 대한 성능 평가를 하기 위해서 실제 시스템에서 수집한 트레이스 정보를활용하였다. UMass 트레이스는 이러한 목적으로 많이 사용되는 것인데 그 중에서 Financial 1과 WebSearch 1을사용하였다[9].
ML-FTL의성능을 평가하기 위해서 TPC-FTL과 비교하였다. 한 페이지의 크기가 1KB이므로 DP 하나에 256개의 TPN들이 기록되고, 따라서 GDT의 크기는 기존의 DFTL이나 TPC-FTL에 비해서 1/256로 대폭 줄어든다.
TP가기록된 페이지 번호 TPN을 결정하기 위해서 먼저 TPN 캐시에서 TPN을 검사한다. 여기에 없으면 DP 캐시를 검사하는데, LPN으로부터 얻은 DP의 Base 값을 활용한다.
순수 페이지 매핑방법으로 FTL을 구현하려면 LPN마다 대응되는 PPN을 RAM에 테이블 형태로 기록해야 하므로 소요되는 RAM의용량이 매우 방대하다. 기존의 요구기반 FTL에서는 RAM 의 용량을 줄이기 위해서 매핑 정보도 플래시 메모리 페이지에 TP로 기록하고 그 TP들의 주소만 RAM에 테이블로관리하는 2단계 방법을 적용하였다. 그러나 SSD의 용량이테라바이트 수준이 보편화되고 있으므로 TP들의 주소를기록하는 RAM의 용량도 지나치게 커진다.
제안하고 그 성능을 평가하였다. 또한 3단계로 확장하는데 따른 오버헤드를 줄이기 위해서 캐시를 관리하는 방법도 제안하였다. 매핑 정보는 제일 상단의 GDT, 중간 단의 DP, 그리고 하단의 TP로 구성된다.
한 페이지의 크기가 2KB 이고 그래서 한 페이지당 512개의 페이지 번호를 기록한다면 TP 인덱스와 DP 인덱스는 각각 9비트이고 나머지 상위 14비트가 GDT 인덱스이다. 먼저 LPN의 GDT 인덱스 부분을활용하여 GDT에서 DP가 기록된 페이지 번호 DPN을 확인하고 DP를 읽어온다. 이 DP에서 LPN의 DP 인덱스 부분을 활용하여 TP가 기록된 페이지 번호 TPN을 확인하고 TP를 읽어온다.
본 논문에서 제안하는 ML-FTL(Muti-Level FTL)은 기본적으로 그림 2와 같이 3단계로 구성된다. TP들의 페이지 주소인 TPN을 플래시 메모리에 DP(Directory Page) 로 기록하고 GDT에는 DP들의 페이지 주소(DPN: DP Number)를 기록한다.
먼저 LPN의 GDT 인덱스 부분을활용하여 GDT에서 DP가 기록된 페이지 번호 DPN을 확인하고 DP를 읽어온다. 이 DP에서 LPN의 DP 인덱스 부분을 활용하여 TP가 기록된 페이지 번호 TPN을 확인하고 TP를 읽어온다. 이 TP에서 LPN의 TP 인덱스 부분을 활용하여 데이터가 기록된 페이지 번호인 PPN을 확인한다.
이 DP에서 LPN의 DP 인덱스 부분을 활용하여 TP가 기록된 페이지 번호 TPN을 확인하고 TP를 읽어온다. 이 TP에서 LPN의 TP 인덱스 부분을 활용하여 데이터가 기록된 페이지 번호인 PPN을 확인한다.
그러나 WebSearch 1의 경우에는 17GB 정도에 그친다. 이 트레이스들을 활용하면서도 대규모 SSD에 대한 ML-FTL의 특성을 정확하게 보여주기 위해서 페이지의 크기에 1KB를 적용하여 시뮬레이션을 진행하였다. 페이지의 크기가 2KB이면 TP 하나에 PPN을 512개, DP 하나에 TPN을 512개 기록할 수 있고, 그러면 GDT의최대 인덱스가 Financial 1은 1300 정도밖에 되지 않고, WebSearch 1의 경우에는 고작 33 정도로 작다.
적절한 DP 캐시의 개수를 확인하기 위해서 TP 캐시의 개수를 8개로 고정하고 DP 캐시 개수에 따른 오버헤드 추이를 확인하였다. 그림 8와 같이 Financial 1의 경우에 8 개 까지는 오버헤드가 줄어들지만 그 이상은 효과가 별로 없다.
캐시를 위한 RAM의 용량이 정해져 있을 때 DP 캐시와 TP 캐시의 적절한 배분을 확인하기 위해서, TP와 DP를 위한 전체 캐시의 수를 16개로 고정하고 TP를 위한 캐시와 DP를 위한 캐시의 배분에 따른 오버헤드를 확인하였다. Financial 1은 그림 9과 같이 오버헤드가 가장 적은 경우는 DP를 위해서 7~10개, 나머지를 TP를 위해서 배분하는 경우이다.

대상 데이터

TP 캐시는 8개를 적용하였다. ML-FTLe DP 캐시를 8개추가하고 TPN 캐시를 위해서 1KB의 RAM을 추가한 경우에대한 평가 결과이다.

성능/효과

본 논문에서는 대용량 SSD에서 GDT를 위한 RAM 용량을획기적으로 줄이는 방법으로서 DFTL의 2단계를 확장한 3 단계 매핑 테이블을 제안하고 그 유용성을 검증한다. 3단계로 확장하면 GDT를 위한 RAM의 용량을 1/512로 대폭줄일 수 있고, 단계가 늘어남으로 인한 추가 오버헤드는캐시를 적절히 활용함으로써 매우 작은 수준으로 제한할수 있음을 확인하였다.
캐시는 DP 캐시와 TP 캐시를 사용하고, 이와 별도로 최근에 사용한 TP 들에 대하여 플래시 페이지의 위치 정보를 캐시로 관리한다. UMass 트레이스를 적용하여 평가해본 결과 ML-FTL 은 기존의 요구기반의 FTL들에 비해서 RAM 소요량은 대폭 줄이면서도 오버헤드는 미미하게 늘어나는 것을 확인하였다. 캐시를 적용할 때 중간 단에 해당하는 DP 캐시에는 8개 정도만 사용하고 나머지는 모두 제일 하단에 해당하는 TP 캐시에 사용하는 것이 좋은 것도 확인하였다.
걸쳐있다. 따라서 DP 캐시와 별도로 최근에 사용된 TPN 들을 TPN 캐시에 보관함으로써 DP 캐시를 거치지 않고도 TPN을 확인할 수 있도록 한다. TPN 캐시의 각 항목은 TP 를 구분하는 Base와 플래시 메모리에 기록된 주소인 TPN 의 쌍으로 관리한다.
WebSearch 1은 한 번에 읽기/쓰기를 요청하는 크기가 매우 크기 때문에 공간적 지역성 효과가 커서 오버헤드가 Financial 1보다 훨씬 작게 나오는데, DP캐시 개수가 늘어나도 개선의 효과가 없지는 않지만 매우 미미하다. 따라서 DP 캐시의 개수는 8개 정도만 사용해도 충분한 것으로 나타났다. 물론 SSD의 용량, 페이지의 크기, 기타 플래시 메모리의 특성 값에 따라서 적절한 캐시의 개수에 차이가 있을 것이다.
WebSearch 1의 경우에는 DP 캐시가 3개 이상이면 큰 차이가 없다. 따라서 DP를 위해서 8개 정도를 배분하고 나머지는 모두 TP를 위해서 사용하는 것이 좋은 성과를 낼 수 있는 것으로 나타났다.
02% 정도 늘어나는 데에 그친다. 이렇게 ML-FTLe GDT를 위한 RAM의 크기를 TPC-FTL에서 비해서 1/256로 획기적으로 줄이면서도 오버헤드 증가는 매우 미미한 것을 확인하였다.
UMass 트레이스를 적용하여 평가해본 결과 ML-FTL 은 기존의 요구기반의 FTL들에 비해서 RAM 소요량은 대폭 줄이면서도 오버헤드는 미미하게 늘어나는 것을 확인하였다. 캐시를 적용할 때 중간 단에 해당하는 DP 캐시에는 8개 정도만 사용하고 나머지는 모두 제일 하단에 해당하는 TP 캐시에 사용하는 것이 좋은 것도 확인하였다.

참고문헌 (10)

A. Gupta, Y. Kim, and B. Urgaonkar, "DFTL: A flash translation layer employing demand-based selective caching of page-level address mappings," in Proc. 14th Int. Conf. Archit. Support Program. Languages Operating Syst., pp. 229-240, 2009.
S. Lee, et. al., "A log buffer based flash translation layer using fully associative sector translation," ACM Trans. Embedded Computing Sys. Vol. 6, No. 3, pp.1-27, 2007.
Y. Guan, et. al., "A Block-Level Log-Block Management Scheme for MLC NAND Flash Memory Storage Systems," IEEE Trans. on Computers, vol. 66, no. 9, pp. 1464-1477, Sep. 2017.

상세보기
F. Ni, et. al., "A Hash-Based Space-Efficient Page-Level FTL for Large-Capacity SSDs," 2017 International Conference on Networking, Architecture, and Storage (NAS), Shenzhen, 2017, pp. 1-6
S. Jiang, et. al., "S-ftl: An efficient address translation for flash memory by exploiting spatial locality," in Mass Storage Systems and Technologies (MSST), IEEE, 2011, pp. 1-12.
H.-P. Choi, Y.-S. Kim, "An Efficient Cache Management Scheme of Flash Translation Layer for Large Size Flash Memory Drives," Journal of The Korea Society of Computer and Information Vol. 20 No. 11, pp. 31-38, November 2015

원문보기 상세보기
H. Kim, D. Shin, Y. Jeong, and K. Kim, "Shrd: Improving spatial locality in flash storage accesses by sequentializing in host and randomizing in device," in Proceedings of the 15th USENIX Conference on File and Storage Technologies, Berkeley, USENIX Association, 2017.
Y. Yao, et. al., "An Advanced Adaptive Least Recently Used Buffer Management Algorithm for SSD," in IEEE Access, vol. 7, pp. 33494-33505, 2019,

상세보기
Storage Traces of UMass Trace Repository, http://traces.cs.umass.edu/index.php/Storage/Storage
Samsung, 1G x 8 bit - 2G x 8 bit- 4G x 8 bit NAND flash memory datasheet (K9XXG08UXA), https://www.scribd.com/document/ 7010323/Samsung-1G-x-8-Bit-2G-x-8-Bit-4G-x-8-Bit-NAND-Flash-Memory-Datasheet

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증