윈도우즈 파일 시스템에서 플래시 메모리의 FTL(Flash Translation Layer) 알고리즘 성능 분석 박원주* , 유현석 , 박성환 , 김도윤 , 박상원 한국외국어대학교 정보통신공학과 {wjpark*, hsyoo, shpark, dykim, swpark }@islab.hufs.ac.kr

플래시 메모리 휴대용 저장장치로 각광받고 있는 플래시 메모리는 쓰기 전 소거연산을 해야하는 물리적인 특성을 가진다. 읽기, 쓰기, 소거연산은 FTL알고리즘의 특성에 따라 성능이 좌우된다. 현재의 FTL알고리즘 별 특성을 파악하고 비교, 분석한다. 플래시메모리가 디스크를 대체할 경우 FTL알고리즘의 성능을 분석해본다. PSN/PBN File System FTL Control RAM Table Flash Memory LSN PSN/ PBN FTL Algorithm

실험방법 가상디스크에서 발생하는 I/O를 I/O 캡쳐 필터드라이버를 이용하여 로그파일로 생성, 로그파일로 시뮬레이팅을 실시함. File Copy & Delete Program Simulating Program User Mode 수행 Kernel Mode Disk Driver diskio.log에서 Log를 읽어서 수행 diskiomo Driver Drive C Drive E diskio.log 디스크 100M 바이트 파일 MP3 150M 바이트, 평균 4.7M 바이트, 1500회 JPG 150M 바이트, 평균 240K 바이트, 1500×19회 방법 무작위로 파일을 선택하여 복사 및 삭제 복사 및 삭제 연산 비율을 1:1로 함 단일 및 다중 프로세스 환경에서 추출

알고리즘 별 특성 Mitsubishi(MSBS) M-Systems(FMAX) Lexar Media(LM) … 3 1 2 LBN - PBN - Ram Table PBN spare area data area Block Mitsubishi(MSBS) M-Systems(FMAX) … 3 1 2 LBN - PBN - Ram Table PBN Block 복사 Block 단순 / 복합 PBN Block 이동 Block … 3 1 2 F T LBN - PBN - Ram Table Moved - Lexar Media(LM) Log Block Scheme : BAST (Block Associative Sector Translation) PBN Block Log Block … 3 1 2 LBN - PBN - Ram Table Log LSN - Log Block Table Data Table Log Block Scheme : FAST (Fill Associative Sector Translation) PBN Random Log Block Sequence Log Block … 3 1 2 LBN - PBN - Ram-Table 7 Log LSN - LSN - Random Log Block Table 5 Log LBN - Block Table Sector Table Data Table

로그블록을 순차쓰기용과 임의 쓰기용으로 구분 알고리즘 특성 비교표 Algorithm Mitsubishi M –Systems Lexar Media Log Block Scheme FAST 데이터 in place 맵핑 Block Hybrid 덮어 쓰기 out of place ->out of place in place & out of place 특징 블록내의 Spare area를 사용 각 블록당 1:1로 복사 블록을 논리적인 블록 중 하나를 이동 블록으로 사용 한 블록에 로그블록 하나를 할당 로그블록을 순차쓰기용과 임의 쓰기용으로 구분 실험 결과 비교표 단위 I/O (100개) 평균 표준편차 읽기 쓰기 소거 소요시간 Mitsu bishi 147214 20549 629 330688 28633 3226 161 60288 M-Systems 64077 21801 647 257466 10271 3454 162 44215 Lexar Media 35083 33520 739 316291 5492 5238 158 51723 Log Block Scheme 22887 23089 384 208719 2900 2965 64 27306 FAST 23144 22365 376 203358 3121 3013 70 28403 읽기/쓰기/소거 = 횟수 , 소요시간 = 읽기:쓰기:소거를 1:7:63비율로 계산 (NAND 플래시 메모리 계열 소요시간)

실험 결과 NTFS JPG 소요 시간 누적 그래 프 NTFS JPG erase 횟수 누적 그래 프 FAT JPG 소요 시간 Mitsubishi M –Systems Lexar Media Log Block Scheme FAST ○ MSBS □ FMAX △ LM ＋ BAST × FAST NTFS JPG 소요 시간 누적 그래 프 NTFS JPG erase 횟수 누적 그래 프 FAT JPG 소요 시간 누적 그래 프 FAT JPG erase 횟수 누적 그래 프 NTFS MP3 소요 시간 누적 그래 프 NTFS MP3 erase 횟수 누적 그래 프

File System간 분석 응답시간에 따른 분석 FAT 과 NTFS의 비교 I/O 양에서 NTFS는 보안성 및 안정성 보장, 압축기능 등을 위해 FAT에 비해 더 많은 metadata를 가진다. 따라서 NTFS는 metadata에 대한 I/O가 많기 때문에 FAT보다 더 많은 양의 I/O가 발생. Lexar Media Algorithm & Log Block Scheme metadata에 대한 I/O가 적을수록 같은 block에 대한 overwrite가 줄어들기 때문에 moved block과 log block의 erase횟수가 크게 적어짐. 응답시간에 따른 분석 소요시간 평균 FAST < Log Block Scheme < M-Systems < Lexar Media < Mitsubishi 소요시간 표준편차 Log Block Scheme < FAST < M-Systems < Lexar Media < Mitsubishi Algorithm Log Block Scheme FAST merge 하나의 Log Block에 대해 한번의 merge 발생 하나의 Log Block에 대해 여러 번의 merge 발생 소요시간 표준편차 Log Block Scheme < FAST

파일 크기에 따른 분석 (1 = 좋음 , 2 = 보통 , 3 = 나쁨) 파일 종류 복사 / 삭제 비고 MP3 순차적인 쓰기가 많이 발생 JPG 평균 240K 바이트, 1500 ×19회 임의적인 쓰기가 많이 발생 메타데이터에 대한 쓰기가 많음 Algorithm 파일크기 비 고 大 小 Mitsubishi 3 파일크기에 거의 관계없이 일정한 성능을 보임 M-Systems 2 Lexar Media 항상 in place방식으로 대응하므로 파일 크기가 커지면 erase횟수가 크게 감소 Log Block Scheme 1 Log Block의 수가 고정적이므로 파일크기가 작아지면 erase횟수가 증가 FAST 순차적인 쓰기에 대해 in place로 대응하므로 파일 크기가 커지면 erase횟수가 감소 (1 = 좋음 , 2 = 보통 , 3 = 나쁨)

Algorithm 특성에 따른 비교 분석 Algorithm Lexar Media Mitsubishi 덮어쓰기 in place out of place read 횟수 Lexar Media << Mitsubishi write/erase Lexar Media > Mitsubishi 소요시간 Lexar Media < Mitsubishi Algorithm Log Block & FAST Others 맵핑 Hybrid Block read/erase Log Block & FAST << Others 비고 Log Block을 이용하여 효율적으로 Block을 사용 Algorithm M-Systems FAST Block 구분 단순 / 복합 Block Data / 순차쓰기용 Log /임의쓰기용 Log Block I/O 패턴 고려하지 않음 순차적/임의적 I/O예측 소요시간 M-Systems > FAST Algorithm Log Block Scheme FAST Log Block 구분 구분 없음 순차쓰기용 / 임의쓰기용 read Log Block Scheme < FAST write/erase/ 소요시간 Log Block Scheme > FAST

종합분석 전체적인 성능은 FAST방식이 가장 좋음. -> 하이브리드 맵핑을 하여 read/write양을 줄이고, 순차적/ 임의적인 I/O를 예측하여 가장 효과적으로 대응함. File System은 전체적인 성능에 저하를 주지 않으나 NTFS가 메타 데이터에 대한 I/O가 많기 때문에 전체적인 I/O양이 FAT에 비해 현저히 많음. -> Flash Memory에는 FAT방식의 File System을 사용하는 것이 좋음. 같은 양의 파일을 copy/delete 연산을 수행하였을 때 파일의 크기가 큰(MP3)경우가 작은 경우(JPG)보다 더 적은 소요시간과 erase횟수를 보임. -> 순차적인 write/overwrite에 대해 더 좋은 성능을 보임.