FTL 중 FAST 기법 정리

멤버십 초기에 FTL에 관련된 과제를 하면서 보았던 FTL 기법 중 FAST에 관련된 것들을 잊어버리기 전에 정리해두고자 한다.

FAST는 FAST의 저자들이 BAST라고 이름붙인 기법의 원리와 문제점을 설명하고 이를 해결하기 위해
완전연관섹터변환(Fully Associative Sector Translation) 방식을 사용하는 것을 말한다. 즉,
BAST에서는 임의쓰기가 동시에 발생할 때 여러 논리블록에 대한 로그블록이 경쟁상태에서 모든 섹터가 사용되지 않고 합병되는
문제점이 있는데 이를 해결하기 위해 각 로그블록의 활용률을 최대한 높임으로써 각 로그블록이 블록 전체의 섹터가 모두 사용된
이후에 소거되도록 한다.

이를 위해서 최초 쓰기 연산시에는 해당 자리에 섹터 데이터를 기록하고, 덮어쓰기 연산시에 아래의 조건들을 검사하여 적절한 연산을 수행한다.

조건 1. (start_lsn mod 32 = 0) & (lbn = (start_lsn div 32) !∈ rw_lbn_set)
조건 2. (lbn = sw_lbn) & (start_lsn mod 32 = sw_sec_num)
조건 3. (lbn = sw_lbn) & (start_lsn mod 32 > sw_sec_num)
조건 4. (lbn = sw_lbn) & (start_lsn mod 32 < sw_sec_num)
조건 5. 조건 1, 2, 3, 4를 모두 만족하지 않는 경우

위의 1~4까지의 조건들은 모두 순차쓰기용 로그블록에 쓰여지는 경우의 조건들이다. rw_set_of_lbn은 임의쓰기용 로그블록
그룹에 기록된 섹터들의 논리블록들의 주소 정보이고, sw_lbn는 순치쓰기용 로그블록에 현재 쓰여지고 있는 논리블록 주소,
그리고 sw_sec_num은 논리 블록에 대해 순차적으로 쓰여진 섹터의 수이다.

조건 1의 경우 순차쓰기용 로그블록의 첫번째 섹터에 기록된다. 이 때, 순차쓰기용 로그블록에 이미 다른 섹터들이 저장되어 있다면 그 블록과 원본 데이터 블록간의 합병 연산이 발생하여 순차쓰기용 로그블록을 소거한 후 기록된다.

조건 2의 경우 순차쓰기용 로그블록에 기록된 데이터의 다음 위치에 추가(append)할 수 있는 쓰기연산이다. 순차쓰기용 로그블록의 모든 섹터가 순차적으로 다 기록된 경우 교환 연산을 한다.

조건 3의 경우 순차쓰기용 로그블록에 연이어쓰여지지는 않지만 기록할 수 있는 쓰기 연산이다. 이 때, 그 중간 섹터가 채워질 확률이 낮기 때문에 합병 연산을 수행한다. 이 때 비어있는 섹터들만 쓰기연산을 수행하여 교환연산을 수행하면 데이터 블록만 한번 소거하면 된다.

조건 4의 경우 순차쓰기용 로그블록에 이미 기록되어 있는 섹터들 중 일부분에 대해서 덮어쓰기가 발생하는 쓰기연산이다. 이 때는 데이터 블록과 로그 블록간의 합병 연산이 수행된다.

조건 5의 경우 임의쓰기용 로그블록에 기록하며, 기록할 위치는 로그블록에 마지막으로 기록한 위치 바로 다음이 된다. 만약, 로그
블록 그룹에 더 이상의 빈 섹터가 없으면 첫 번째 로그블록에 대해 합병 연산을 수행하여 공간을 확보한다. 합병 연산 수행시에는
원형 큐 방식으로 시작 로그 블록을 합병 연산의 대상으로 삼는데, 그 로그 블록에 쓰여진 섹터들의 논리 블록의 개수만큼
합병연산이 발생한다. 이 때 로그블록에서 최신 섹터를 찾아 이 최신 섹터의 내용을 예비블록에 기록하고 데이터 블록으로부터 나머지
최신 섹터를 복사한다. 로그블록에서 최신 섹터를 찾을 때는 큐의 마지막부터 역탐색(backward search)를 수행하고,
합병 연산의 대상이 아닌 역탐색으로 찾은 최신 섹터를 포함하는 로그블록에서 섹터를 복사하고 해당 섹터 번호를 사상테이블에서
-1로 설정하여 무효화(invalid)시켜 그 로그블록이 나중에 합병연산의 대상이 되었을 때 무시하도록 한다.