SFS : Random Write Considered Harmful in Solid State Drives
Preview
-
SSD access
플래시 메모리 기반의 solid state driver (SSDs): HDD보다 성능, 전력 소비 측면에서의 기술적 개선
- sequential access: 이전의 I/O operation의 마지막 logical block address(LBA) 다음의 LBA부터 SSD 접근
- random access: FTL에 의해서 동적으로 블록 맵핑
-
- 플래시 메모리의 일종으로 SSD에 사용된다.
- NAND Flash Memory의 종류
- SLC (single-level cell): cell 당 1-byte 기록, 속도가 가장 빠르고 수명이 가장 길며, 가장 비싸다.
- MLC (multi-level cell): cell 당 2-byte 기록, SLC에 비해 속도가 느리고 수명이 짧지만 가격이 저렴하다. 현재 대부분의 SSD에서 사용한다.
- TLC (triple-level cell): cell 당 3-byte 기록, 속도가 가장 느리고, 수명이 가장 짧다. 주로 USB에 많이 사용된다.
- NAND Flash Memory의 page와 block
-
block: cell의 그룹
-
plane: block의 그룹
-
page: SSD를 read, write하는 최소 접근 단위
→ 2~16 KB, 대부분 SSD의 block은 128개 또는 256개 page를 가진다.
-
FTL(Flash Translation Layer)은 호스트의 LBA(Logical Block Address)와 드라이브의 PBA(Physical Block Address)를 맵핑해주는 SSD 컨트롤러의 컴포넌트이다.가장 최근의 드라이브는 Log Structure 파일 시스템과 같이 작동하는 “hybrid log-block mapping” 또는 그 파생 알고리즘을 구현하고 있다.이 알고리즘은 랜덤 쓰기를 시퀀셜 쓰기처럼 핸들링할 수 있도록 해준다.
- FTL의 구성 요소
- STL (sector translation layer): address mapping, garbage collection, wear leveling 담당
- BML (bad-block management layer): invalid page를 많이 가지고 있는 블록을 선택하고, valid page를 다른 블록에 복사한 후 해당 블록을 지우고 재사용할 수 있게 해줌
- LLD (low level driver): NAND flash를 사용하기 위한 드라이버
- FTL의 핵심기술
(a) wear leveling:
- 블록당 write 횟수를 모니터링하여 균등하게 수행될 수 있도록 분배
- 특정 블록에만 write되는 것을 방지하여 SSD의 수명을 연장 시킨다.
(b) garbage collection:
- 블록을 실제로 삭제하지 않고 marking해 둔 뒤, 적절한 시점에 일괄 삭제 처리하는 기술
- stale 상태의 페이지들이 erase작업을 거쳐 free페이지로 상태 전이하여 새로운 쓰기 데이터를 저장할 수 있도록 해주는 프로세스
- 효율적인 garbage collection을 위한 전략
- 빈번하게 변경되는 데이터를 핫데이터라고 하며, 그렇지 않은 데이터를 콜드 데이터라고 한다. 이 둘은 최대한 분리하여 페이지에 할당해야 효율적인 garbage collection을 할 수 있다.
- 핫데이터는 최대한 버퍼에 두고, SSD에 최소한으로 업데이트 하게 한다.
- 데이터를 모아서 한번에 삭제해야 한다.
- 효율적인 garbage collection을 위한 전략
(c) over provisioning:
- wear leveling, garbage collection을 작업하기 위한 여유 공간
-
- SSD의 동작 방식
-
page단위 read : 한번에 page보다 작은 크기의 데이터는 읽을 수 없다.
page보다 작은 데이터를 요청할 경우 필요한 데이터가 포함된 페이지를 통째로 읽은 다음 불필요한 데이터는 모두 버리고 요청한 데이터만 반환한다
-
page단위 write : page 단위로 write하기 때문에 page보다 작은 데이터를 쓰는 경우 write amplification 발생한다.
write amplification: 페이지 사이즈에 맞게 write하여 부가적인 write가 발생
-
read-modify-write: page는 overwrite될 수 없다. (in-place update 불가능)
데이터가 변경되면 페이지 내용은 내부 레지스터로 복사된 후 레지스터에서 변경디어 새로운 free 상태의 페이지로 기록되는 것 (read-modify-write) 원본 페이지는 stale로 마킹되고 erase되기 전까지 그 상태로 남게 된다.
-
write하기 전 반드시 erase : page는 overwrite될 수 없다. page는 free일 때만 쓰기 수행이 가능하며, 데이터 변경시 페이지 내용은 내부 레지스터로 복사된 후, 레지터에서 변경되어 새로운 free 상태의 페이지에 기록된다. 완전히 기록되면 해당 페이지는 stale 상태로 유지된다.
erase과정은 쓰기에 비해 많은 시간이 소요되기 때문에 쓰기 속도를 느리게 만든다.
-
block 단위 erase : page 들을 block으로 묶어서 수행, 한 번 stale상태가 된 페이지는 block 단위의 erase 작업을 거쳐 free 상태로 전이될 수 있다.
erase 명령은 SSD 컨트롤러가 free 공간 필요시 자동적으로 내부 명령을 통해 garbage collection을 실행하여 수행한다.
-
logical block mapping: 호스트 영역의 logical block address를 플래시 메모리의 physical block address로 변환하는 역할로 FTL이 mapping table을 사용하여 수행한다.
mapping table이 포괄하는 메모리의 용량을 넓히기 위해 블록(페이지 그룹) 단위로 mapping 수행 → write amplification 증가 → 비효율적
-
SSD의 random write 문제:
random write의 속도가 sequential write 속도보다 느리고, write할 떄마다 NAND block erase를 더 많이 발생시키기 때문에 SSD의 수명을 더 빠르게 줄인다.
→ 문제 해결을 위해 SSD를 위한 새로운 파일 시스템 SFS 제안
- random write가 느린 이유
-
SFS
- log-structured 접근 방식을 취해 SSD의 최대 write bandwidth를 활용한다.
- 파일 시스템 수준에서 발생하는 모든 random write를 SSD 수준에서 하나의 sequential write으로 바꾼다.
- 새로운 데이터 그룹핑 전략을 사용한다. 비슷한 업데이트 가능성을 가진 데이터 블록을 같은 세그먼트에서 할당한다.
- 본 논문에서는 리눅스 기반의 NILF2를 수정하여 SFS 프로토타입을 구현하고, 몇 가지의 워크로드를 이욯하여 최신의 파일 시스템들과 성능을 비교하였다. 실험 결과, ext4, btrfs에 비해 SFS는 SSD 내부에서 block erase 발생 횟수를 7.5배까지 감소시켰다.
1. Introduction
-
SSD는 물리적인 부분이 없기 때문에 access latency가 거의 없고, 일정한 랜덤 접근 속도 등 다양한 장점이 존재한다.
-
SSD의 두가지 문제점
-
limited lifespan
SSD는 overwrite가 안되기 때문에 write를 하려면 해당 페이지에 erase 작업을 수행하고 페이지를 free 상태로 만들어 주어야 한다. 한 페이지당 일정 이상의 erase작업을 수행하면 더 이상 사용할 수 없게 된다. 따라서 빈번한 write로 인한 erase는 SSD의 생명 주기를 짧게 만든다.
-
poor random write performance
랜덤 쓰기는 NAND 플래시 블록의 데이터 페이지가 내부 레지스터에 복사된 뒤 erase 작업을 수행하기 때문에 SSD의 내부 단편화가 발생하고 쓰기 수행 속도를 느리게 한다. 또한 랜덤 쓰기는 여러개의 블록에 해당 작업을 수행하기 때문에 erase를 더 많이 하게 하여 SSD의 수명을 더 짧게 만든다.
-
-
위의 문제를 해결하기 위해 다양한 연구가 진행되었다.
-
FTL (flash translation layer)
호스트의 LBA(Logical Block Address)와 드라이브의 PBA(Physical Block Address)를 맵핑해주는 SSD 컨트롤러의 컴포넌트이다.가장 최근의 드라이브는 Log Structure 파일 시스템과 같이 작동하는 “hybrid log-block mapping” 또는 그 파생 알고리즘을 구현하고 있다.이 알고리즘은 랜덤 쓰기를 시퀀셜 쓰기처럼 핸들링할 수 있도록 해준다.
-
separation of hot/cold data
빈번하게 변경되는 데이터를 핫데이터라고 하며, 그렇지 않은 데이터를 콜드 데이터라고 한다. 이 둘은 최대한 분리하여 페이지에 할당해야 효율적인 garbage collection을 할 수 있다
⇒ 위의 노력들은 파일 시스템이 요청하는 논리적 블록 주소 기반의 최적화 방식으로 오버라이트가 안되는 SSD에는 덜 효과적이다.
-
데이터베이스 시스템 측면
SSD의 성틍 특성을 고려하여 새로운 데이터베이스 저장 스키마 제안
⇒ 특정 application에서만 효과적인 기법이기 때문에 일반적인 application에는 적용할 수 없는 최적화 기법
-
-
contributions
-
SSD 기반 파일 시스템 설계 원리 제안
SSD의 성능 특성 활용 (random write가 느리다), 파일 블록 수준의 통계를 directly utilize
→ the unit size of random write requests becomes a multiple of a certain size 일 때, 랜덤 쓰기로 인한 오버헤드 사라짐
⇒ log-structured 접근을 사용
-
on writing data grouping scheme 제안
log-structured 방식에서 segment cleaning 오버헤드를 줄이기 위해 업데이트 가능성이 비슷한 파일 블록을 같은 segment에 할당한다.
⇒ iterative segment quantization 알고리즘 제안
: disk 전체의 hotness distribution을 고려하면서 grouping 기준을 결정하기 위한 알고리즘
⇒ cost-hotness policy for victim segment selection
: 업데이트 빈도가 비슷한 블록을 같은 세그먼트에 분배하여 segment cleaner가 live block이 가장 적은 segment를 victim으로 빠르게 선정할 수 있게 한다. 이로써 live block을 복사하는 오버헤드를 최소화하게 한다.
-
2. Background
2.1 Flash Memory and SSD Internals
- NAND flash memory
- basic building block of SSDs
- page 단위 read write
- block 단위 erase
- read 속도 > write 속도
- no in-place overwrite (overwrite하기 전 erase해야 함)
- single level cell : 대략 100K erase cycle
- multi level cell : 대략 10K erase cycle
- SSD
- host interface logic + array of NAND flash memories + SSD controller
- FTL (Flash translation layer)
-
SSD controller에 의해 작동한다.
-
logical block address 선열 배열을 호스트에게 보여준다.
-
LBA-PBA mapping table을 관리한다.
-
garbage collection 수행 : garbage collection은 virtual block이 가득 차거나 free page 개수가 부족한 경우에 수행되는 것으로 valid data를 새로운 공간에 복사하고 기존의 invalid data를 erase하여 physical page를 재사용한다.
-
wear-leveling: 각 블록마다 available한 write cycle를 equal 하게 사용하도록 보장하여 SSD의 수명을 늘리기 위한 알고리즘이다.
-
block level FTL은 garbage collection 오버헤드가 크다.
-
page level FTL은 garbage collection 오버헤드가 작다. 하지만 메모리를 page로 잘게 쪼개면 mapping table에 보관해야 하는 엔트리가 많아져서 테이블의 크기가 커진다.
-
block + page / hybrid level FTL: flash block들을 logically data block 과 log block으로 나눈다. data block은 block level mapping을 하고, log block은 page level mapping을 한다. data block은 일반적인 유저 데이터가 쓰여지는 블록으로 사용자에게 보여지는 저장 공간이고, log block은 사용자가 data block에 update를 요청한 경우 데이터가 쓰여지는 공간으로 사용자에게 보이지 않는 저장 공간이다.
전체적으로는 block-level mapping을 하면서 update 요청이 들어온 기존 데이터에 한해서 log block을 구성한다. 그러면 garbage collection을 할때 log block은 write하지 않고 erase를 할 수 있다. log block을 page-level mapping을 하는 이유는 각 page가 어떤 데이터에 대한 log인지 확인하는 작업을 수행하기 위한 것이다.
-
DFTL: 선택적으로 page-level mapping table의 엔트리를 caching하여 page-level mapping을 확장한다.
-
2.2 Imbalance between Random and Sequential Write Performance in SSDs
-
clustered page 단위로 read/write → 병행성을 최대한 활용 / clustered page 크기의 배수가 아닌 크기의 요청이 들어오면 추가적인 페이지 단위 read/write을 해야 하기 떄문에 성능이 저하된다.
-
random write는 FTL에서 garbage collection을 많이 수행하게 하여 성능을 저하시킨다.
-
hybrid FTL에서 random write는 log block과 data block의 연관성을 증가시키고, full merge를 발생시킨다.
-
page-level FTL에서는 block을 고르게 쪼개기 때문에 garbage collection이 유효한 데이터 복사를 하는 오버헤드가 크게 발생한다.
-
garbage collection 성능을 향상시키기 위한 방법
-
SSD는 NAND flash 메모리에 여러 개의 블록들을 clustered block으로 결합시킨다.
→ 여러 개의 physical block들을 parallel하게 erase하기 위해서
-
hybrid FTL에서 switch merge는 적은 오버헤드를 발생시킨다
-
page-level FTL에서 live page가 없는 빈 블록은 garbage collection의 victim으로 선택된다.
⇒ random write 성능이 sequential write 성능과 비슷해진다.
-
2.3 Skewness in I/O Workloads
**TPC-C: 온라인 트랙잭션 처리 시스템의 처리 성능 평가 벤치마크, 사용자와 데이터베이스간 트랙잭션을 싱행하는 완벽한 컴퓨팅 환경에서 분당 거래 (tpmC)로 측정한다.
대부분의 I/O는 일부 block에서 발생한다. (Pareto 법칙)
→ write frequency에 따라 block grouping
3. Design of SFS
3.1 SFS: Design for SSD-based File Systems of the 2010s
**TRIM command: 운영체제가 어느 블록의 데이터가 더 이상 사용되지 않고 내부적으로 삭제될 수 있는지를 SSD에 알려주는 명령
지금까지 SSDs와 파일시스템은 서로를 고려하지 않고 발전해왔다. TRIM 을 제외하고 두개의 계층은 logical block address 정보만을 가지고 read/write 연산을 통해서만 상호작용 했다. 이것은 두 계층의 최적의 성능을 내지 못하는 것으로 이를 개선하고자 SFS를 제안한다.
- Design principles of SFS
-
File block level statistics - Beyond LBA (logical block address)
- LBA allocation policy
-
in-place-update : 동일한 LBA에 dirty file block을 overwrite 한다.
→ 해당 LBA는 파일이 블록을 해제하기 전까지 파일 블록을 나타내게 된다.
ex) FAT32, ext4
-
no-overwrite : dirty file이 새로운 LBA에 write 된다.
→ scalability, reliability, manageability 향상 / file 블록 업데이터 요청 들어올 때마다 새로운 LBA를 받아야 한다.
⇒ 파일 블록의 hotness semantic이(빈번하게 사용되는 블록 패턴?) 스토리지 계층에 적용될 수 없다.
ex) btrfs, ZFS, WAFL
-
⇒ file block level에서 hotness 통계를 활용하는 file system을 제안한다.
- LBA allocation policy
-
Write bandwidth maximization by sequentialized writes to SSD
-
request size = clustered block size의 배수일 경우에 random write의 성능이 sequential write와 비슷해진다.
→ SFS는 log-structured approach를 사용
-
log-structured
: 어떤 data에 대한 write가 발생했을 경우 기존 data가 위치한 page를 업데이트하는 것이 아니라 별도의 공간 (segment)에 sequential 하게 업데이트를 수행하는 구조
-
read요청은 대부분 디스크를 거치지 않고 수행되기 때문에 I/O traffic 대부분이 write에서 발생한다고 가정한다. 그래서 모든 write 요청을 디스크에 로그 형식으로 순차적으로 기록하여 디스크의 seek time을 줄여 write 속도를 빠르게 한다.
모든 정보를 인덱스 정보를 가진 로그 형식으로 기록하여 효율적으로 read 수행할 수 있다.
순차적 로그 형식으로 요청 정보를 저장하기 위해선 많은 양의 연속된 공간이 지속적으로 확보되어야 한다. 따라서 디스크를 segment로 나누고 주기적으로 segment cleaner를 작동시켜 기존의 파일이 갱신되어 생긴 불필요한 데이터에 대하여 garbage collection을 수행하여 지속적으로 연속된 공간을 확보하는 전략을 사용한다.
-
-
raw SSD bandwidth를 최대한 활용하기 위해 SFS는 segment size를 clustered block size의 배수로 설정한다
→ random write의 성능과 상관 없이 sequential write 성능을 최대화할 수 있다.
-
-
Eager on writing data grouping for better bimodal segmentation
-
free segment가 부족할 경우, segment cleaner는 victim segment에서 live block들을 복사하여 free segment를 마련한다.
-
segment cleaning이 live block의 read/write를 포함하면 log-structured file system에 오버헤드가 생긴다.
→ hot data와 cold data를 분리하여 segment에 할당해야 한다.
(data가 처음 write되었을 때 hot/cold 구분하는 것 해결해야 할 과제)
→ hot segment 는 빠르게 invalidation되고, cold segment는 오래 live한다.
→ segment utilization distribution은 bimodal 형태를 띈다 (블록들 대부분 live block으로 full하거나 empty)
→ segment cleaning overhead 감소
⇒ SFS는 segment cleaning과 file block level 통계를 기반으로 on writing data를 구분하여 grouping을 하여 segment cleaning 오버헤드를 줄인다.
-
-
3.2 SFS Architecture
-
SFS의 core operations: segment writing, segment cleaning, reading, crash recovery
**SFS의 read는 log-structured file system과 비슷하기 때문에 본 논문에서 다루지 않음.
-
SFS의 데이터 update 가능성을 측정하여 각 file block, file, segment의 hotness를 정의한다.
-
segment cleaning
-
victim segment 선정
→cost-hotness policy 도입 in SFS
-
victim segment 에서 live block을 page cache에 read
-
victim segment 가 재사용가능 해진 free 상태임을 표시
-
segment writing 발생시킴
-
-
segment writing
-
block grouping을 위해 hotness criteria를 결정한다.
→ hot / warm / cold / read-only segment group
-
각 블록의 hotness를 계산하여 블록과 그룹의 hotness를 비교하여 근처의 유사한 그룹에 할당한다.
→ 비슷한 수준의 hotness를 가진 블록들은 같은 그룹에 속한다.
-
SFS는 항상 같은 그룹에 속한 블록들로 segment를 채운다.
→ segment가 가득 찰때까지 해당 그룹에 대한 segment writing은 지연된다.
⇒ 결과적으로 hotness가 비슷한 블록들로 segment를 구성하기 때문에 bimodal한 형태를 띄게 할 수 있다.
-
3.3 Measuring Hotness
-
skewness in I/O workload : frequently updated data → updated quickly
-
temporal locality in reference : recently updated data → change quickly
-
hotness = write count/age
-
block hotness = Hb
Wb = write counts CT= current time MTb= last modified time
** Wb= 0 인 경우 , block이 포함된 파일의 hotness로 정의
$$Hb = Wb / CT-MTb$$
-
file hotness = Hf
Wf = total number of block updates MTf = last modified time of the file
$$Hf = Wf / CT-MTf$$
-
segment hotness = Hs
: segment 내부의 live block들의 hotness의 평균
N = segment 내부의 block의 개수
SFS에서 ∑Wb와 ∑MTb는 segment가 생성될 때 segment usage meta data file에 저장되고 각 블록이 invalidate될때마다 그 값을 빼서 갱신한다.
$$Hs = ∑Wb / (N*CT-∑MTb)$$
-
3.4 Segment Quantization
-
segment cleaning의 효율성을 위해서 hotness에 따라 block을 그룹화하여 같은 segment에 분배해야 한다.
→ grouping criteria는 파일 시스템의 모든 블록의 hotness를 고려해야 한다.
→ iterative segment quantization을 제안한다.
-
segment quantization in SFS
-
파일시스템의 hotness 범위를 k개의 sub-range로 나눈다.
-
각 sub-range의 hotness를 quantized value로 계산한다.
- equi-height partitioning: 전체 hotness 범위를 여러 개의 그룹으로 똑같이 나누는 방식
- equi-width partitioning: 각 그룹이 동일한 개수의 segment를 가지게 나누는 방식
※ 대부분의 segment가 hot하지 않은 분배 결과는 fail
→ 정확하게 segment의 hotness distribution을 반영하고 적절히 quantize하기 위해서 iterative segment quantization algorithm 제안
-
-
iterative segment quantization
- segment를 k개의 group으로 나누고, iterative refinement approach를 통해 그룹의 center를 찾는다.
-
written segment의 수가 전체 그룹의 개수 k보다 작거나 같으면 임의로 선정한 segment hotness를 초기 Hg값으로 할당한다.
** Hgi = i 번째 그룹의 hotness
-
written segment 의 개수 > k
각 segment를 hotness가 가장 가까운 Group i 에 할당한다.
Hgi 를 계산한다.
-
Hgi 에 더 이상 변화가 없거나 최대 3번까지 2번 단계를 반복한다.
-
segment의 개수가 많아질수록 계산을 위한 오버헤드가 커지는 문제를 해결하기 위해 SFS는 Hgi를 메타데이터에 저장하고 파일시스템을 mount할때 함께 로드한다.
3.5 Segment Writing
-
group dirty block in the page cache → write the blocks group-wise in segment
-
segment writing 이 발생하는 case
(a) SFS가 주기적으로 매 5초마다 dirty block을 write하는 경우
(b) flush daemon이 page cache에 dirty page의 개수를 감소시키는 경우
(c) segment cleaning이 발생하는 경우
(d) fsync, sync가 발생하는 경우
**fsync: 지정된 파일과 관련된 모든 변경 자료를 디스크와 동기화
**sync: 모든 버퍼 내용 (데이터 + 메타데이터)을 디스크와 동기화
-
step of segment writing
-
segment quantization → 모든 그룹의 hotness가 업데이트 된다
-
모든 dirty block의 hotness가 계산되고 각 블록이 hotness가 가장 비슷한 그룹으로 할당된다.
→ SFS는 같은 그룹에 속한 블록들로만 segment를 채워서 hotness 정도가 비슷한 블록만 담고 있게 한다.
-
segment가 다 차면 write을 수행한다.
한 그룹에 속한 블록의 개수가 segment가 포함할 수 있는 블록의 개수보다 작은 경우에는 segment가 다 찰 때까지 블록 writing을 지연시킨다.
-
-
segment cleaning도 위와 같이 작동하기 때문에 새로운 데이터가 이미 오버라이트 됐지만 시스템이 crash하거나 갑자기 전원이 나가면 segment cleaning상의 not-yet-written 블록이 lost되는 위험이 있을 수 있다.
→ 이러한 data loss를 처리하기 위해 SFS에 도입된 기술
- least recently freed된 순서대로 segment를 할당하고 free segment 리스트를 관리하는 기법
- normal block에 쓰는 것이 not-yet-written 블록에 overwrite하게 하는지 확인하는 기법
-
동기화를 하거나 SFS가 check-point를 초기화하는 경우에는 segment가 다 차지 않아 지연된 block을 포함한 모든 dirty block은 group에 속한 블록의 개수와 상관없이 즉시 segment에 write된다.
→ best-effort approach :
가능한 많이 그룹별로 block write 하고 group과 상관없이 남은 블록을 write한다.
-
블록 관련 메타데이터 (MTb, Wb, MTf, Wf, ∑MTb, ∑Wb)를 업데이트 한다.
-
overwritten block의 liveness를 invalidate한다.
-
-
writing 프로세스 동안 파일 블록을 hotness에 따라 재배열하기 때문에 bimodal한 분배를 유지할 수 있다.
→ segment cleaning 오버헤드를 줄인다.
→ 거의 항상 sequential write 요청을 하게 한다.
3.6 Segment Cleaning: Cost-hotness policy
-
log-structured file system에서 segment cleaning policy
-
greedy policy: live block의 개수가 가장 작은 segment을 선택
→ live block 복사하는 오버헤드 최소화
⇒ segment cleaning 중에 data block의 hotness를 고려하지 않는다.
**실제로 cold data는 거의 수정되지 않기 때문에 hot data와 분리해두는 것은 segment cleaning에 매우 이득
-
cost-benefit policy: live block의 개수가 동일할 때 cold segment를 선택
segment 내의 각 블록의 마지막으로 수정된 시간으로 cold 정도를 측정한다. (update가능성)
-
cost-hotness policy (cost-benefit policy의 확장된 버전)
SFS에서 hotness는 segment의 update 가능성을 나타내는 것이니 때문에 segment age대신에 hotness를 사용한다.
따라서 SFS는 cost-hotness가 가장 큰 segment를 victim으로 선정한다.
-
cost-hotness = free space generated / cost * segment hotness
= (1-Us) / 2 * Us * Hs
**Us = segment utilization = segment의 live block 부분
계산을 위해 필요한 값들은 메타데이터로 저장되기 때문에 효율적이다.
-
-
-
SFS에서 segment cleaning은 disk utilization이 water-mark를 초과할 때 발생한다.
3.7 Crash Recovery
-
write연산 중에 system crash , sudden power off가 발생하면 파일 시스템에서 데이터를 잃을 수도 있다. 이러한 inconsistencies 문제를 회복하기 위해 SFS는 check-point 매커니즘을 사용한다.
-
check-point mechanism
: crash 발생 후 다시 마운트 할때, 파일 시스템은 마지마 check point 상태로 roll back하고, 다시 normal 방식으로 재개한다.
- check point는 모든 파일 시스템의 구조가 일관적이고 완전한 상태이다.
-
SFS에서의 check-point
-
모든 dirty data와 meta-data를 디스크에 write
-
disk의 고정된 location에 superblock을 업데이트
**superblock은 meta data의 루트 주소, 마지막 written segment 위치, time stamp를 가지고 있다.
SFS는 디스크 상의 두개의 분리된 physical block에 write하여 superblock의 atomic write를 보장한다. crash 이후에 다시 마운트를 하는 동안 SFS는 두개의 superblock을 모두 보고 time stamp를 비교하여 가장 최신의 superblock을 read한다.
- 빈번한 check-pointing은 crash로 인한 data loss를 최소화할 수 있지만 시스템 성능을 낮을 수 있다.
-
-
SFS의 check-pointing case
(a) 매 30초마다 check point만들기
(b) 20 segment 이상 write이 되었을 때
(c) 동기화가 수행되었을 때
(d) 파일 시스템 마운트가 해제되었을 때
4. Evaluation
4.1 Experimental Systems
-
Implementation
-
NILFS2를 기반으로 하며 block grouping과 cost-hotness segment cleaning을 지원하기 위해 in-memory와 on-disk meta data 구조를 개조했다.
<NILFS2>
-
scalable block mapping을 위해 b-tree를 사용한다.
-
연속적인 snapshot을 지원하기 위해 virtual-to-physical block translation in data address translation(DAT) 메타데이터 파일을 사용한다.
→ b-tree 기반 block mapping의 기술적 문제: meta data 업데이트 오버헤드가 크다. (단말 노드를 업데이트하는 것은 루트노드까지 영향을 미치고, DAT에 엔트리도 업데이트 해야 한다.)
-
-
기존의 파일 시스템은 random write는 엄청난 양의 meta data 업데이트를 수반한다.
→ meta data 업데이트 오버헤드를 줄이고 check-point 생성을 지원하기 위해 연속 스냅샷 기능을 차단하였다.
→ 대신 super block, inode file (IFILE), segment usage file (SUFILE), DAT file을 추가하였다.
-
SFS-specific field (meta data structure)
-
superblock에 각 그룹의 hotness Hg를 저장하고, 파일 시스템이 마운트될 때 로드한다.
-
IFILE에는 각 파일의 write횟수 Wf와 파일이 마지막으로 수정된 시간 MTf를 저장한다.
-
SUFILE에는 hotness 계산과 segment cleaning을 위한 정보가 저장된다.
: Us (segment내 live block의 비율), Hs (segment의 hotness , segment 내의 블록들의 hotness의 평균), ∑MTb(각 블록의 수정된 시간의 합)
-
DAT에는 Wb (각 블록의 write 횟수), MTb (블록이 마지막으로 수정된 시간)이 저장된다.
-
SFS에서 meta data file은 일반 파일과 동일하게 취급되기 때문에 cache될 수 있다.
-
-
SFS는 cost-hotness policy와 segment cleaning triggering policy를 구현했다.
-
-
Workloads
-
OLTP(온라인 트랜잭션 처리) database workload
using TPC-C benchmark
-
desktop workload
using RES (연구 그룹의 13의 데스크탑으로 구성된 시스템의 113일 작업량)
-
조작한 workload로 random write의 분배를 다르게 수행하였다
→ 균일한 random write가 SFS에서 최악의 성능을 보였다. (SFS는 block grouping을 하는 동안 workload의 skewness를 활용하기 때문)
-
write 성능을 극대화하기 위해 workload에서 write 요청은 단일 스레드에서 가능한 빠르게 replay 되었고, throughput은 application level에서 측정되었다.
-
다양한 디스크 사용률 (utilization)에서 SFS의 behavior를 측정하기 위헤 dummy block으로 SSD를 채웠다.
-
-
Write Cost
SFS에서 새로운 데이터를 write하기 위해서는 segment cleaner에 의해 새로운 segment가 생성되되어야 한다. segment cleaning은 clean되는 live block에 대한 추가적인 read/ write작업을 초래한다.
- segment cleaning의 I/O cost
- 새로운 데이터 write하는 cost
4.2 Effectiveness of SFS Techniques
-
SFS의 핵심 기술
→ 모두 write cost를 감소시키는 결과
-
writing block grouping
-
grouping을 할수록 write cost가 적어진다.
-
5개 이상의 그룹이 생기면 write cost의 감소 폭이 줄어든다.
-
-
iterative segment quantization
-
cost-hotness segment cleaning
-
4.3 Performance Evaluation
-
write cost and throughput
- log-structured file system (LFS)와 SFS 비교
- LFS: cost-benefit cleaning policy 사용 (live block의 개수가 동일할 때 cold segment를 victim으로 선정)
- throughput은 application level에서 측정되기 때문에 page cache로 인한 효과도 포함한 결과이다.
- 디스크 사용률이 증가할수록 SFS의 write cost 개선 정도는 더 커진다.
- 높은 update skewness를 보이는 경우, SFS는 write cost를 77.4%까지 감소시킨다.
- 균일한 random write로 skewness가 낮은 경우, SFS는 write cost를 27.9%까지 감소시킨다.
*** 단점: skewness가 적을 경우 SFS의 write cost 개선 정도가 낮다.
- log-structured file system (LFS)와 SFS 비교
-
segment utilization distribution
-
segment utilization = segment내의 live block 개수 / block 전체 개수
-
SFS는 지속적으로 hotness에 따라 data group을 재배열하여 bimodal distribution을 유지한다 (full이거나 empty이거나)
→ skewless한 workload 에서는 bimodal segment distribution을 보기 힘들다 .
→ bimodal distribution을 유지하면 segment cleaner가 live block의 개수가 가장 적은 segment를 victim으로 선정하는 것이 쉬워진다.
-
-
effects of SSD performance
: SFS가 SSDs의 성능 특성을 잘 개선시키는지 확인하였다.
- SFS는 random write 성능과 무관하게 수행한다.
- SFS는 sequential write성능이 충분히 좋은 경우에 SSD 성능을 향상시킨다.
-
comparison with other file systems
- SFS의 평균 throughput은 다른 파일시스템에 비해 1.5~1.6배 정도 높다.
- SFS에서 write amplification이 아주 낮게 나왔다. (segment에 블록이 다 찰때까지 write을 지연시키기 때문에?)
- SFS에서 block erase 횟수 (SSD의 수명 결정 요소)가 현저히 낮게 나왔다.
5. Related Work
5.1 FTL-level approach to improve random write performance
- hybrid FTL scheme - FAST, LAST 가 대표적
- FAST: log area의 flexible한 mapping으로 log area utilization을 높인다.
- LAST: FAST + random log block을 hot과 cold로 분리하여 full merge cost를 낮춘다.
- page-level FTL scheme - DAC, DFTL이 대표적
- DAC: 비슷한 write 빈도를 가진 데이터 블록들을 같은 logical group으로 클러스터링하여 garbage collection cost를 줄인다.
- DFTL: dynamic caching을 이용하여 page-level mapping table에 필요한 RAM size를 줄인다.
- FTL-level approach는 거의 logical block address에 의존하기 때문에 제약이 있다.
- 이러한 접근법은 파일 시스템이 no-overwrite block allocation policy를 적용하여 악화된다.
5.2 Disk-based log-structured file systems
-
HDD에서 log-structured file system을 최적화하기 위한 방법
-
hole plugging method
- victim segment에 live block을 hole에 오버라이트한다.
- hole: 다른 segment의 빈 공간 (몇 개의 invalid한 block을 가지고 있는 segment)
→ segment cleaning에서 live block copy cost 감소
- in-place가 가능한 스토리지에서만 사용 가능한 방법이다.
-
adaptive method
- cost-beneficial policy와 hole plugging cost를 각각 추정해 본다.
- 그리고 둘 중 비용이 적은 기법을 적용한다.
- cost model이 HDD의 성능 특성을 기반으로 한다.
-
WOLF
- data page의 업데이트 빈도에 따라 두 개의 다른 버퍼에 hot page, cold page를 분리한다.
- 두 개의 segment 를 디스크에 한 번에 write 한다.
- 이 기법은 hot page와 cold page가 적절히 절반 정도로 분리되어야 잘 작동한다.
-
hybrid approach
- logging for hot pages → 높은 write 성능
- overwrite for cold pages → segment cleaning cost 감소
- update policy를 결정하는 hot page ratio를 추정하는 것이 중요하다.
- adaptive method와 마찬가지고 HDD의 성능 특성을 기반으로 한다.
5.3 Flash-based log-structured file systems
-
in-place update가 안되는 flash memory 기반의 디바이스에서 file system을 위한 기법
- wear-leveling
- bad block management : FTL의 BML에서 수행 / invalid page를 많이 가지고 있는 블록을 선택 후, valid page를 다른 block에 복사하고 해당 블록을 삭제하고 재사용할 수 있도록 해주는 기법
-
JFFS2, YAFFS, UBIFS = flash-based file systems
segment-cleaning에서 turn-based selection algorithm을 사용한다.
: wear-leveling을 segment cleaning 프로세스에 통합시키는 것
- X turns: wear-leveling을 고려하지 않고 greedy policy를 사용하여 victim segment 선택
- Y turns: wear-leveling을 위해서 확률적으로 full valid segment를 victim으로 선택
6. Conclusion and Future Work
-
proposal of a next generation file system for SSD : SFS
-
log-structured approach를 취해서 SSD에서 random write를 sequential write로 변환 시켰다.
→ 성능 향상, 수명 증가
-
I/O workload의 skewness를 활용하여 파일 수준에서 hotness를 고려하여 on writing을 위한 grouping을 하였다.
→ iterative segment quantization algorithm & cost-hotness policy
-
-
SFS를 HDD에도 적용할 수 있는지 추구 연구할 것이다.
Pros and Cons
- 장점
- log-structured approach를 사용하여 random write를 sequential write로 수행할 수 있게 하여 성능을 향상시킨다.
- sequential write를 수행하게 하는 segment 의 크기를 clustered block size의 배수로 설정하여 SSD의 write성능을 최대한 활용한다.
- 각 파일 블록, 파일, 세그먼트의 hotness 정보를 활용하여 grouping을 하기 떄문에 segment의 블록 분배가 bimodal한 형태를 띄어 segment cleaning 오버헤드를 줄인다.
- segment quantization을 위한 관련 계산 정보를 메타데이터에 저장하여 해당 파일 시스템 마운트시에 함께 로드하기 때문에 계산으로 인한 처리 시간이 줄어든다.
- iterative segment quantization algorithm을 사용하여 segment hotness의 sub-range에 hotness distribution을 보다 정확하게 반영할 수 있다.
- 단점
- hotness의 skewness 정도가 작을 경우 wrtie cost 개선 정도가 낮다.
- segment가 다 찰 때까지 블록 write를 지연시키기 때문에 각 블록의 hotness 분포가 넓을 경우 일부 segment에 write starvation이 발생할 수 있다.
- SFS는 매 30초마다, 20개의 segment가 write되거나 동기화가 수행된 경우, 파일 시스템 마운트가 해제된 경우에 check-point를 생성하는데 빈번한 check-pointing은 시스템 성능을 낮출 수 있다.
- iterative segment quantizatioin algorithm에서 written segment의 수가 segment group의 개수보다 작은 경우 segment hotness를 임의의 값으로 할당하기 때문에 hotness distribution을 제대로 반영하지 않을 수 있다.
참조한 자료들은 키워드에 링크를 걸어두었습니다.
[SFS : Random Write Considered Harmful in Solid State Drives] 논문을 읽고 공부하면서 직접 정리한 내용이기 때문에 틀린 내용이 있을 수도 있음을 알려드립니다.
