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

4. 사례 연구

4.1 Mitsubishi

미쓰비시 알고리즘은 블록 매핑을 기반으로 함

목표 - 섹터 매핑의 한계 극복

  1) Map Table에 필요한 대용량 스토리지

  2) 전원이 켜졌을 때 Map Table 구축 비용의 높은 오버헤드 극복

 

하나의 논리 블록은 하나의 물리 블록과 1:1로 매핑

 

기존 블록 매핑 기술에 비교하여, 미쓰비시는 space sector(공간 섹터) 개념을 제안

-> 물리 블록을 일반 섹터 영역과 공간 섹터 영역으로 구성

 

논리 블록이 m개의 섹터로 이루어져 있는 경우, 물리 블록은 m개의 섹터와 n개의 추가 공간 섹터로 구성

-> 물리 섹터 오프셋과 논리 섹터 오프셋은 일반 섹터 영역에서 동일, 공간 섹터의 오프셋은 동일할 필요 없음

 

위 예시에서 물리적 블록이 두 개의 일반 섹터와 공간 섹터로 구성되어 있음을 가정

write(0, A) 쓰기 요청을 처리할 때, 논리 블록 번호(0 == 0/2)와 논리 페이지 오프셋(0 == 0%2)가 계산되고, 블록 레벨 매핑 테이블에서 물리 블록 번호(9)를 얻음

 

pbn 9의 물리 페이지 오프셋이 초기에는 비어 있기 때문에, data A는 pbn 9의 첫번째 섹터 위치에 기록 된다.

추가 쓰기 작업은 동일한 방법으로 수행

 

write(0, G) 쓰기 요청을 처리할 때, pbn 9의 물리적 페이지 오프셋 0이 이미 사용되었기 때문에, 첫 번째 공간 섹터 영역에 기록, 이때 논리 섹터 번호(0)을 플래시 메모리의 예비 영역에 저장

==> 처음 쓰기 작업은 일반 섹터 영역 해당 오프셋에, 일반 섹터 영역이 사용 중이면 공간 섹터에 쓰고 논리 섹터 번호를 예비 영역에 작성 

 

기본 블록 매핑 기법에서 write(0, G)는 복사 및 지우기 작업을 발생 시킴

 

논리 섹터 번호 0을 읽을 때 플래시 메모리의 예비 영역을 검색하여 최신 버전을 찾을 수 있음

 

 

프로세스 재편성 과정

FTL은 사용 가능한 블록을 가져오고, 이전 물리적 블록에서 새 블록으로 유효한 섹터를 복사

논리/물리 변환 테이블의 내용을 알맞게 변환

원래 물리 블록의 섹터가 새 블록으로 전송이 완료되면, 원래 블록을 지우고 사용 가능한 블록 목록으로 돌아감

미쓰비시 체계는 재편성을 위해 항상 최소한 하나의 빈 블록을 유지한다.

 

미쓰비시 체계는 매핑 정보에 대해서 Map Block 방법을 사용함

변환 테이블의 크기는 블록 매핑을 기반이기 때문에 상대적으로 작다.

 

 

 

 

4.2. M-systems

M-systems는 플래시 메모리 관리 시스템을 위해 ANAND와 FMAX 알고리즘을 제안한다.

기본적으로 이들 기술은 블록 매핑 기법에 기초하지만, 기본 블록 매핑 기법에 비교하여, 그들의 체계에서는 하나의 논리 블록이 둘 이상의 물리 블록에 매핑할 수 있다.

 

ANAND의 기본 구조는 FMAX와 비슷하기 때문에 논문에서는 FMAX만 설명함

 

FMAX에서 하나의 논리 블록은 주 블록(primary block)과 대체 블록(replacement block), 두 개의 물리 블록에 매핑될 수 있다.

논리 섹터 오프셋은 주 블록의 물리 섹터 오프셋과 동일하지만,

논리 섹터 오프셋과 대체 블록의 논리 섹터 오프셋은 다를 수 있음

위 예시에서는 물리적 블록이 4개의 섹터로 구성되어 있다고 가정

write(4, A)를 처리할 때, 논리 블록 번호(1 == 4/4)와 논리 페이지 오프셋(0 == 4%4)를 계산하고 블록 레벨 매핑 테이블을 사용하여 물리 블록 번호(10)을 얻는다.

pbn 10의 물리 페이지 오프셋 0이 초기에 비워져 있는 경우, data A는 pbn 10의 첫 번째 섹터 위치에 기록

추가 쓰기 작업은 동일한 방법으로 수행

 

write(8, G) 쓰기 요청 시, pbn 12는 이미 사용중이기 때문에, 쓰기 요청은 두 번째 물리 블록인 pbn 9에서 행해진다.

두 번째 물리 블록에 사용 가능한 섹터가 없는 경우 복사 및 지우기 작업이 수행

 

FMAX는 블록별 메소드를 사용하여 매핑 정보를 저장함

FMAX는 RAM 테이블을 관리하여 논리 블록을 두 개의 물리 블록에 매핑

-> 기본 블록 매핑에 비해 더 많은 RAM 크기가 필요

 

 

 

 

4.3. SSR

SSR은 하이브리드 주소 매핑 체계를 사용

SSR은 논리 섹터 번호에서 논리 블록 번호를 결정할 때, 두 가지 해시 함수를 제공함

 

lsn = 논리 섹터 번호

ns = 블록의 섹터 수

 

H1(lsn) = lsn/ns = lbn

H2(lsn) = lsn%ns = lbn

 

해시 함수 H1과 H2를 기반으로 하는 SSR 알고리즘은 각각 군집 모드(clustered mode), 산개 모드(scattered mode)

이전 FTL 알고리즘은 해시 함수 H1을 기반

위 예제는 실행 중인 클러스터 모드 예제

물리 블록은 4개의 섹터로 구성된다고 가정

write(5, A)를 처리할 때 논리 블록 번호(1 = 5/4)를 계산한 다음, 블록 레벨 매핑 테이블을 이용하여 물리 블록 번호(10)를 찾음

물리 페이지 오프셋 0이 처음에는 비어 있기 때문에, 데이터 A는 pbn 10의 첫 번째 섹터에 기록하고, 논리 섹터 번호(5)를 플래시 메모리의 예비 영역에 기록

SSR에서 논리 섹터 오프셋과 물리 섹터 오프셋은 동일할 필요가 없음 -> 플래시 메모리의 예비 영역에 논리 섹터 번호를 기록해야 함

추가 쓰기 작업이 동일한 방식으로 실행

 

읽기 작업이 수행될 때, 동일한 논리 섹터 번호를 가진 데이터 인스턴스가 둘 이상 있는 경우, 가장 최근의 데이터는 블록의 뒤에서 첫 번째 데이터

-> 예제에서 섹터 번호 9에 해당하는 유효 데이터는 pbn 11의 네 번째 데이터(H)

물리적 블록에 사용 가능한 섹터가 없는 경우 복사 및 지우기 작업이 미리 수행됨

 

 

 

 

4.4. Log block scheme

수많은 긴 순차적 쓰기와 적은 수의 랜덤 덮어쓰기 작업 접근 패턴을 효율적으로 처리하기 위한 체계

이러한 목적을 달성하기 위해 로그 블록 체계는, 대부분의 물리 블록을 블록 주소 지정 수준(데이터 블록)에 유지함

섹터 주소 지정 수준에서 소수의 고정 물리 블록(로그 블록)을 사용함

데이터 블록은 주로 긴 순차 쓰기를 위한 저장공간으로 사용되고, 로그 블록은 랜덤 덮어쓰기를 위해서 사용

 

섹터가 초기에 데이터 블록에 기록되면, 동일한 논리 섹터로 덮어쓰기 작업은 로그 블록 풀에서 할당된 로그 블록으로 전달

동일한 논리 섹터에 대한 덮어쓰기는 모두 로그 블록을 사용하여 처리

로그 블록에 사용 가능한 섹터가 없는 경우, 로그 블록의 데이터는 해당 데이터 블록의 데이터와 병합하고, 로그 블록은 나중에 덮어쓰기를 위해 로그 블록 풀로 반환

 

FTL 알고리즘이 덮어쓰기에 쓸 사용 가능한로그 블록을 찾지 못하는 경우, 먼저 사용 중인 로그 블록 중 희생 로그 블록(victim log block)을 선택하고, 희생 로그 블록의 데이터를 해당 데이터 블록과 병합

희생 로그 블록이 지워지고 현재 덮어쓰기에 할당

 

주소 매핑을 위해 로그 블록 체계는 RAM에서 데이터 블록을 위한 블록 매핑 테이블과, 로그 블록을 위한 섹터 매핑 테이블을 유지

이 예시는 물리 블록이 4개의 섹터로 구성되어 있다고 가정

write(4, A)를 처리할 때 논리 블록 번호(1 == 4/4)와 논리 페이지 오프셋(0 == 4%4)를 계산하고, 블록 레벨 매핑 테이블을 사용하여 물리적 블록 번호(10)를 얻음

pbn 10의 물리 페이지 오프셋 0이 처음에는 비어 있기 때문에, data A는 pbn 10의 첫 번째 섹터에 기록

 

write(4, C) 쓰기 요청이 들어오면, pbn 10의 물리적 페이지 오프셋 0이 이미 사용 중이기 때문에 pbn 20을 로그 블록으로 기록

논리 섹터 오프셋은 물리 섹터 오프셋과 동일할 필요가 없기 때문에 논리 섹터 번호가 플래시 메모리의 예비 영역에 기록

로그 블록의 경우 섹터 레벨 매핑 테이블이 그림 12처럼 따로 구성

 

 

로그 블록 체계에서 기본 맵 블록 방식(3.2.1)을 채택하여 매핑 정보를 관리

데이터 블록의 블록 매핑 표는 맵 블록 중 하나에 저장

맵 블록 풀에서 블록 매핑 테이블의 최신 버전을 얻기 위해서 맵 디렉토리는 RAM에 유지

전원이 꺼진 후 복구를 위해, 로그 블록에 대한 섹터 매핑 테이블이 업데이트 될 때마다, 맵 디렉토리 또한 특정 플래시 메모리 블록(체크포인트 블록)에 저장 

 

 

최근에는 FAST 및 STAFF 등 로그 체계를 일부 변형된 로그 체계가 제안

FAST 체계에서는 둘 이상의 논리 블록을 물리 블록에 매핑할 수 있으므로, 로그 블록의 공간 활용도가 향상됨

STAFF의 핵심 아이디어는 블록에 할당되고, 주소 매핑을 제어하는데 사용되는 상태를 도입하여, 지우기 작업을 최소화시키는 것이다.

 

 

 

 

 

 

- 참고 문헌 -

A survey of Flash Translation Layer

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