BAST (2021-02-17)

3. 로그 블록을 기반으로한 FTL 설계

우리의 목표는 매핑을 위해 필요한 SRAM의 크기를 제한하면서 작은 크기의 쓰기와 긴 순차적인 쓰기를 모두 효율적으로 처리하는 것 -> 로그 블록(페이지 수준 관리 블록)을 도입하면서 달성

정전 후에도 저장된 데이터의 일관성을 보장해야 함 -> 전용 블록인 map 블록에서 single atomic write(세세하게 쓰겠다라는 의미로 해석하면 될듯) 형태로 매핑 정보의 업데이트를 수행

 

 

 

3.A The Log Block

우리의 계획은 대부분의 블록을 블록 수준에서 관리하고(일반적인 데이터를 보유하는 데이터 블록),

적은 수의 고정 블록은 더 미세한 페이지 수준으로 관리(로그 블록)

 

로그 블록은 데이터 블록에 대한 작은 크기의 쓰기를 위한 임시 저장소로 사용

데이터 블록의 페이지 업데이트가 요청되면 로그 블록은 미리 지워진 자유 블록 풀에서 할당되고, 로그 블록의 첫 번째 페이지에서부터 업데이트가 점진적으로 수행

해당 페이지가 사실상 오버헤드 없이 작성되므로 예비 영역에 대한 쓰기는 동시에 수행이 가능하다.

 

 

로그 블록 체계에서 읽기 요청의 경우, 요청된 페이지가 있는지 확인하기 위해 로그 블록을 확인해야함

요청된 페이지가 로그 블록에 있는 경우, 해당 페이지를 데이터 블록에 음영 처리(덮어씌우는 것처럼 보이게 한다는 뜻인듯)되어 호스트 시스템에 제공

 

검사 프로세스를 효율적으로 수행하기 위해 SRAM의 각 로그 블록에 대한 페이지 수준 매핑 테이블을 유지해야 함

해당 테이블은 시스템 시작 시 로그 블록의 각 페이지 예비 영역에 저장된 논리적 주소를 스캔하여 구성되며, 최신 페이지를 가리키도록 모든 쓰기에 업데이트 됨

로그 블록에서 논리 페이지가 여러 번 업데이트된 페이지는 마지막 페이지에서 뒤로 로그 블록을 스캔하면 최신 복사본이 포함된 페이지를 식별할 수 있음 -> 별도의 처리가 필요하지 않음

 

 

 

3.B 합병 방법 (Merge Operation)

로그 블록이 데이터 블록에 할당되면, 로그 블록의 모든 페이지가 소모될 때까지 별도의 작업 없이 데이터 블록에 대한 쓰기 요청을 수행

모든 페이지가 소모되면 로그 블록을 해당 데이터 블록과 병합한 후 회수

 

 

자유 블록 풀에서 지워진 블록을 할당한 다음, 페이지가 존재하는 경우에는 로그 블록에서, 그렇지 않으면 데이터 블록에서 각 페이지를 최신 페이지로 채운다. (그림 a)

 

모든 페이지를 복사한 후, 새로운 블록이 데이터 블록이 되고, 이전 데이터 블록과 로그 블록은 자유 블록 풀로 돌아가 지우기 작업을 기다림

 

병합 작업을 수행하기 위해서는 n개의 페이지 읽기 작업, n개의 페이지 쓰기 작업, 2개의 블록 지우기 작업(로그 블록, 이전 데이터 블록)이 필요 (n = 블록당 페이지 수)

자유 블록 1개를 사용하면서 2개의 자유 블록을 만들어, 2개의 지우기 작업당 1개의 자유 블록을 생성하는 효율성 제공

 

 

한 번의 지우기 작업당 하나의 사용 가능한 블록을 생성하는 것이 이상적인 상황

블록의 모든 페이지가 첫 번째 논리 페이지부터 마지막 논리 페이지까지 순차적으로 기록될 때 발생

이 경우 로그 블록을 데이터 블록으로 만들고, 기존의 데이터 블록을 자유 블록 풀로 되돌려 병합 작업 간소화 가능

단순화된 버전의 병합 작업을 스위치 작업이라고 부름 (그림 b)

 

 

대체 블록 방식도 유사한 작업이 가능하지만, 대체 블록 체계의 병합 작업은 각 페이지의 배치 제한으로 인해 많은 페이지가 사용되지 않은 채로 남을 수 있기 때문에, 과도한 삭제를 초래 (그림 c)

--> M-systems의 대체 블록은 남김없이 쓰는거 같던데..?

 

 

우리 병합 작업은 로그 구조 파일 시스템에서 사용하는 클리닝 메커니즘과 유사 (그림 d)

차이점은 우리 체계가 로그 블록의 페이지를 로그 블록의 페이지를 동일한 데이터 블록의 것으로 제한하고, 병합 작업의 효율성은 로그 블록의 유효한 페이지 수와 무관하다는 점

 

반대로 로그 구조 파일 시스템은, 지우기 작업 중인 블록의 유효한 페이지를 재배치하기 위해 빈 블록의 일부를 소비하기 때문에, 효율성은 유효한 페이지 수와 반비례하며, 활용도에 따라 달라짐

 

 

C. The Map block

병합 작업과 스위치 작업 모두 데이터 블록의 매핑을 변경하기 때문에 매핑 정보를 업데이트 해야함

 

이전 체계에서는 매핑 정보가 연결된 예비 영역의 각 페이지 블록에 논리적 주소 태그 형태로 저장

기본적으로 이러한 태그는 물리-논리 역번역 정보를 제공하며, 기존의 논리-물리 매핑 테이블로 재구성 해야 한다.

이를 위해서 플래시 메모리 전체 공간을 스캔하여, 모든 페이지 블록에 있는 논리적 주소 태그를 수집해야 하는데, NAND형 플래시 메모리에서 몇 바이트의 읽기는 사실상 페이지 읽기와 거의 동일한 비용이 드는 경우 시간과 전력이 많이 소모됨, 매핑 테이블은 일반적으로 SRAM 전체에 있어야 한다.

--> Per 블록 메소드 이야기인듯..

 

 

제안된 체계에서, 매핑 테이블은 더 빠른 시작 및 요구 시 즉시 가져오기를 가능하게 하기 위해서 map 블록이라는 전용 블록에 저장

map 블록은 각 페이지가 매핑 테이블의 증분 업데이트를 저장하도록 로그 블록과 유사한 페이지 수준으로 구성

매핑 테이블의 map 디렉토리(라고 부르는 맵)은 SRAM으로 유지되며, 맵 블록에 저장된 매핑 테이블의 각 부분을 찾는데 사용됨

--> 맵 디렉토리가 테이블을 의미하는 것?

해당 설정은 플래시 메모리에 저장된 매핑 테이블에 대한 업데이트가 제대로 수행될 수 없으므로, 모든 업데이트에서 매핑 테이블의 맵이 변경된다는 점을 제외하고는 기존의 2단계 페이지 테이블 구조와 유사

--> ?? 2단계 페이지 테이블 구조는 뭐임?

 

 

그림 3은 병합 작업 전후의 매핑 테이블을 내용을 보여줌

매핑 테이블 또한 로그 블록과 사용 가능한 블록을 매핑하기도 하지만, 스토리지 시스템 컨트롤러의 가상 주소 공간에만 표시되며, 호스트의 논리적 주소 공간에는 투명하다.

--> ??

병합 작업에는 3개의 블록(데이터 블록, 로그 블록, 사용 가능 한 블록)이 포함되므로 3개의 매핑 테이블 항목을 업데이트를 해야함

 

 

매핑 테이블의 업데이트로 맵 블록의 페이지가 사용되기 때문에 사용 가능한 페이지는 결국 모두 소모 -> 사용된 맵 블록을 회수하는 메커니즘이 필요

단순성을 위해 라운드 로빈 방식(round-robin manner)으로 맵 블록을 사용하고, 현재 사용되는 맵 블록의 다음 부분은 현재 지도 블록이 소진 되기 전에 지움

지우기 작업은 다음 맵 블록에 있는 유효한 페이지(맵 디렉토리에서 항복이 가리키는 페이지)를 현재 맵 블록으로 복사하고 복사 중인 페이지의 맵 디렉토리 항목을 업데이트하며 다음 지도 블록을 지움

 

※ 라운드 로빈 스케줄링(Round Robin Scheduling, RR)은 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum)로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘이다.
보통 시간 단위는 10 ms ~ 100 ms 정도이다. 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 된다. 문맥 전환의 오버헤드가 큰 반면, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리하다.

 

 

맵 디렉토리는 처음에 모든 페이지가 위치할 때까지 마지막으로 사용된 블록(사용 가능한 페이지를 포함하는 블록)에서 고정된 위치의 맵 블록을 역순으로 스캔하여 구성

프로세스를 단순화하기 위해 맵 디렉토리는 룸이 있는 경우 로그 블록 및 자유 블록에 대한 맵과 함께 매핑 테이블에 포함

 

 

맵 디렉토리가 구성되면 주소 변환은 기존의 2단계 페이지 테이블의 경우와 유사하게 수행될 수 있음

1. 맵 디렉토리는 필요한 매핑 테이블 항목이 포함된 페이지의 위치를 얻기 위해 호스트에서 논리 주소의 고차 비트(high-ordered bits) 사용하여 조회

2. 현재 페이지가 없는 경우(요청 시 가져오기), SRAM으로 가져온다.

--> ?? 몰긋음..

그런 다음 매핑 테이블 항목은 맵 디렉토리를 인덱싱하는데 사용되는 고차 비트와 블록 오프셋에 사용되는 저차 비트(low-ordered bits)를 잘라냄으로써 얻은 논리 주소 중간차 비트를 사용하여 가져온 페이지를 인덱싱하여 엑세스 할 수 있음

매핑 테이블 항목에 기록된 물리 블록 주소에 블록 오프셋을 추가하여 대상 페이지의 물리 주소를 얻음

 

 

 

3.D 호스트 요청의 원자성 (Atomicity of Host Requests)

CompactFalsh 시스템과 같은 플래시 메모리 기반 스토리지 서브시스템은 예기치 않은 정전 상황이 발생하더라도 일관된 상태를 유지해야함(디지털 카메라 사용자는 언제든지 디지털 카메라에서 CompactFlash를 제거할 수 있음)

-> 내부 데이터 구조의 일관성을 보장하는 것은 모든 FTL의 중요한 요건

 

제안된 체계에서, 메타 데이터 업데이트(매핑 테이블)는 단일 원자 쓰기 작업에서 수행

-> 예기치 않은 정전 때문에 맵 블록에 대한 쓰기 작업이 실패하는 경우에도 플래시 메모리에 저장된 메타 데이터가 항상 일관됨

 

쓰기 작업의 실패는 각 페이지 예비 영역에 저장된 ECC 코드를 확인하여 탐지 가능

-> ECC 오류가 있는 페이지를 단순히 무시하면, 중단된 쓰기 작업이 실행되기 전과 동일한 상태로 매핑 테이블을 재구성 가능

 

 

호스트로부터 모든 데이터가 완전히 수신될 때까지 매핑 정보의 업데이트를 지연시킴으로써, 호스트의 긴 순차적 쓰기 요청을 단일 원자 작업으로 처리할 수 있음

수신된 데이터는 사용 가능한 블록에 일시적으로 저장되며, 모든 데이터가 저장된 후 해당 매핑 테이블 항목을 업데이트하여 데이터 블록으로 동시에 전환

매핑 테이블의 업데이트는 호스트의 요청을 효과적으로 커밋하며, 이 수정을 통해서 성능이 저하되지는 않음

이 기능은 대용량 데이터 구조가 단일 원자 작업으로 업데이트 될 수 있기 때문에, 파일 시스템 수준의 일관성 관리를 단순화 하는데 유용

 

 

좀 더 신중하게 처리해야 하는 경우

1. 작은 크기의 쓰기가 로그 블록으로 전달되다가 중간에 중단되는 경우, 다시 시작한 후 호스트에서 부분 결과를 볼 수 있음

이 경우 로그 블록의 각 페이지에 쓰기 시퀀스의 끝을 알리는 비트를 도입하여 해결

-> 비트가 삭제된 로그 블록의 페이지는 비트가 설정된 페이지가 다음에 와야 유효한 것으로 간주

 

2. 호스트의 데이터를 버퍼링 하기 위해서 충분한 수의 자유 블록을 사용할 수 있어야 하며, 그렇지 않으면 원자성을 보장할 수 없음

이 경우 파일 시스템은 스토리지 시스템에서 오류 반환 또는 위험을 감수하도록 할 수 있음

 

3. 요청에 관련된 일련의 블록은 맵 조각(map fragment)의 경계를 넘어 확장될 수 있기 때문에, 커밋되기 전에 맵 블록에 대한 두 개의 순차적 쓰기가 필요로함

이 경우 위에서 설명한 것처럼 쓰기 시퀀스의 끝을 나타내는 유사한 비트 플래그를 사용하여 해결 가능

이 방법을 사용하면 더 높은 수준의 트랜젝션의 원자성은 하드 디스크 기반 스토리지 계층의 이전 접근 방식과 유사하게 구상이 가능함

 

 

 

 

 

 

- 참고 문헌 -

A SPACE-EFFICIENT FLASH TRANSLATION LAYER FOR COMPACTFLASH SYSTEMS

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.124.3802&rep=rep1&type=pdf

라운드 로빈 스케줄링

ko.wikipedia.org/wiki/%EB%9D%BC%EC%9A%B4%EB%93%9C_%EB%A1%9C%EB%B9%88_%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81