A survey of Flash Translation Layer (2021-02-07)

0. Abstract

플래시 메모리의 장점(비휘발성, 빠른 엑세스 속도, 충격 저항, 낮은 전력 소비량 등)으로 인해 임베디드 어플리케이션에 널리 사용되고 있음

하지만 쓰기 전 지우기(Erase-before-write) 등의 하드웨어적 특성으로 인해, FTL(Flash Translation Layer)와 같은 소프트웨어 계층이 요구된다.

이하 논문은 플래시 메모리용 최신 FTL 소프트웨어의 문제 정의, 알고리즘, 관련 연구 문제 논의, 각 FTL 알고리즘 구현을 기반으로 성능 분석

 

 

 

 

1. Introduction

플래시 메모리는 hard disk와 비교했을 때 비휘발성, 빠른 접근 속도, 데미지 저항, 낮은 전력 소비와 같은 강점으로
mmc, sd, 휴대폰 등에 사용되고 있다.
하지만 하드웨어의 특징으로 인해 flash memory의 데이터를 읽고 쓰기 위한 software module이 요구된다. -> FTL

flash memory의 특징 : erase-before-write 구조
memory에 읽고 쓰는 경우의 분배가 다른 경우, 전반전인 flash memory system의 심각한 성능 저하가 나타남

FTL 알고리즘의 고려사항 : storage performance, RAM memory requirements

전반적인 시스템 포퍼먼스는 쓰기 퍼포먼스에 중대한 영향을 받는다.
지우기가 읽고 쓰기보다 cost가 더 비싸다. -> 지우는 작업을 최소화해야 한다.
ram memory는 매핑 정보를 유지하는데 요구된다. 하지만 ram은 비싸다..

 

 

 

 

2. Problem definition & FTL functionalities

2.1 문제 정의

- 정의 1

Sector는 읽기 쓰기의 최소 단위

Block은 플래시 메모리의 지우기 단위, Sector가 모여서 만들어짐

 

- 정의 2

파일 시스템 계층은 플래시 메모리의 특정 주소에서 데이터를 읽거나 쓰기 위해, 논리 섹터 번호로 읽기 또는 쓰기 명령을 실행함

논리 섹터 번호는 FTL 계층의 매핑 알고리즘에 의해 플래시 메모리의 실제 물리적 섹터 수로 변환됨

-> n개의 물리적 섹터가 있는 경우, 상위 계층인 파일 시스템은 플래시 메모리를 m개의 논리 섹터로 구성된 블록 I/O 장치로 간주하고, 논리 섹터를 하나 이상의 물리적 섹터에 매핑해야 하기 때문에 m <= n(논리적 섹터 <= 물리적 섹터) 이다.

 

- 정의 3

플래시 메모리는 여러 블록으로 구성되며, 각 블록은 여러 섹터로 구성됨

프래시 메모리는 물리 섹터 위치에 이전에 작성된 데이터가 있는 경우, 새 데이터가 기존 데이터를 덮어쓰기 전에 블록 단위로 지워야 한다.

FTL은 파일 시스템에서 제공한 논리 섹터 번호로, 플래시 메모리에서 물리 섹터 번호를 생성한다.

 

 

 

2.2 FTL 기능

FTL은 아래의 기능을 무조건 제공해야 한다.

- 논리-물리 주소 매핑 : 파일 시스템에서 플래시 메모리의 물리 주소로 논리 주소를 변환하는 것

 

- 전원 꺼짐 복구 : FTL 작업 중 갑작스러운 전원 꺼짐 현상이 발생해도, FTL 데이터 구조를 보존하고 데이터 일관성을 보장해야함

 

- 분산 쓰기(Wear-leveling) : FTL은 메모리 블록을 최대한 고르게 마모할 수 있도록 하는 기능을 포함해야함

 

 

 

 

3. A taxonomy for FTL Algorithms

3.1 주소 매핑

3.1.1 Sector Mapping

섹터 매핑은 단순하고 직관적인 알고리즘

모든 논리 섹터는 해당 물리 섹터에 매핑

-> 파일 시스템에 m개의 논리 섹터가 인식될 때, 논리-물리 매핑 테이블 행의 크기는 m이다.

Fig 2에서 블록은 4 페이지로 구성되어 총 16개의 실제 페이지가 생성된다고 가정, 각 페이지는 데이터 섹터와 예비 영역(spare area)로 구성

16개의 논리 섹터가 있다고 가정할 경우, 매핑 테이블의 행 크기는 16(n <=m)

파일 시스템에 write(9, A) 명령이 실행 될 때, 매핑 테이블에 따라(lsn 9 -> psn 3) 데이터를 씀(psn 3에 이전에 기록된 데이터가 없는 경우)

 

이전에 쓴 데이터가 있는 경우 FTL은 빈 물리 섹터에 위치를 결정하고, 데이터를 쓰고, 매핑 테이블을 수정

 

빈 섹터가 존재하지 않는 경우 FTL은 플래시 메모리 내 제물 블록(victim block)을 선택하고, 제물 블록의 유용한 데이터를 예비 블록에 복사하고, 매핑 테이블을 업데이트 -> 제물 블록을 지우고 예비 블록으로 만듦

 

전원이 나간 후 매핑 테이블을 재생성하기 위해서, FTL은 매핑 테이블을 플래시 메모리에 저장하거나, 각 섹터 영역에 쓰기 작업 시 예비 영역에 논리 섹터 번호를 기록함

 

 

 

3.1.2 Block Mapping

섹터 매핑 알고리즘은 많은 양의 RAM을 요구하기 때문에, 블록 매핑 기반 FTL이 제안됨

논리 블록 내의 논리 섹터 오프셋이, 물리 블록 내의 물리 섹터 오프셋과 같다는 것

블록 매핑 체계에서 파일 시스템에 감지된 논리 블록이 m개 있다면, 논리-물리 매핑 테이블의 행 크기는 m이다.

논리 블록이 4개라고 가정하면, 매핑 테이블의 행의 개수는 4개이다.

파일 시스템이 write(9,A) 명령을 실행하면, FTL은 논리 블록 번호(9/4 -> 2)와 섹터 오프셋(9%4 -> 1)를 계산하고, 매핑 테이블을 통해 물리 블록 번호 1을 찾음

물리 섹터 오프셋은 논리 섹터 오프셋과 같기 때문에 물리 섹터 위치를 결정할 수 있음

 

논리 블록 번호 = (명령 위치 / 블록 개수(테이블 행크기))

섹터 오프셋 = (명령 위치 % 블록 개수(테이블 행크기))

논리 섹터 오프셋 == 물리 섹터 오프셋

 

블록 매핑 알고리즘은 섹터 매핑에 비해 적은 양의 매핑 정보를 필요로 하지만, 파일 시스템이 동일한 논리 섹터 번호로 쓰기 명령을 실행하는 경우 많은 복사 및 지우기 작업이 필요하기 때문에 성능이 크게 저하됨

전원이 꺼진 후 다시 복구를 위해 블록 레벨 매핑 정보를 플래시 메모리에 저장해야 함

 

 

 

3.1.3 Hybrid Mapping

섹터와 블록의 단점을 보완하기 위해, 하이브리드 매핑 방식이 도입됨

하이브리드 기술은 먼저 블록 매핑 기술을 사용하여 물리 블록을 얻고, 다음 섹터 매핑 기술을 통해 물리적 블록 내 사용 가능한 빈 섹터를 찾는 방식

파일 시스템이 write(9, A) 명령을 내리면 FTL은 논리 블록 번호(9/2 -> 1)을 계산한 다음 매핑 테이블에서 물리 블록 번호 1을 찾은 후, FTL은 업데이트를 위해 빈 섹터를 할당 (비어있는 순서대로)

예시에서는 논리 오프셋과, 물리 오프셋이 다르기 때문에(논리 물리 각각 1과 0), 논리 섹터 번호인 9가 반드시 저장된 페이지의 예비 영역에 기록되어야 한다.

매핑 테이블을 재구성하기 위해서 논리 섹터 번호뿐만 아니라 논리 블록 번호도 물리 블록의 예비 영역에 기록해야 한다.

 

플래시 메모리에서 데이터를 읽을 때, FTL은 먼저 지정된 논리 섹터 번호를 사용하여 매핑 테이블에서 물리적 블록 번호를 찾는다. 그리고 물리 블록의 예비 영역에서 논리적 섹터 번호를 읽어 요청된 데이터의 최신 값을 얻는다.

 

 

 

 

 

 

 

 

 

- 참고 문헌 - 

A survey of Flash Translation Layer

http://idke.ruc.edu.cn/people/dazhou/Papers/AsurveyFlash-JSA.pdf