FAST '24 Key-Value Systems Session
MiDAS: Minimizing Write Amplification in Log-Structured Systems through Adaptive Group Number and Size Configuration
Seonggyun Oh, Jeeyun Kim, and Soyoung Han, DGIST;
Jaeho Kim, Gyeongsang National University; Sungjin Lee, DGIST;
Sam H. Noh, Virginia Tech
https://www.usenix.org/conference/fast24/presentation/oh
prior stage of MiDAS
= Lightweight data lifetime classification using migration counts to improve performance and lifetime of flash-based SSDs
https://dl.acm.org/doi/10.1145/3476886.3477520
MiDAS에 대해 background 와 motivation, 개념 위주로 정리
MiDAS가 적용되는 환경 = Log-structured system
traditional한 storage system
random access 방식으로 데이터를 저장하고 업데이트함
필요할 경우 위치를 지정해서 데이터를 overwrite 덮어쓰기 할 수 있음
io 성능이 스토리지 디바이스의 물리적인 특성의 영향을 받게 됨 (디스크 회전 속도 등)
overwrite 하므로 fragmentation 데이터 파편화 문제 , write amplification 쓰기 증폭 문제 발생
로그 구조 시스템
새 데이터를 저장할 때 기존 데이터를 수정하지 않고 새 위치에 순차적으로 추가하며 변경 사항을 기록함 = append only write
공간이 부족해질 수 있으므로 나중에 정리하는 과정 필요 = compaction , garbage collection
쓰기 성능 향상 , 덮어쓰기 최소화로 스토리지 디바이스 수명 증가
덮어쓰지 않고 수정하려면 기존 데이터를 invalid 데이터로 바꾸고 새로운 페이지에 수정한 데이터를 추가해주어야 함
invalid 데이터가 많아지면 필요한 데이터만 남기고 invalid 데이터들을 블록 단위로 묶어서 삭제한 후 다시 사용할 수 있도록 정리해주는 GC를 수행해야함
로그 구조 시스템은 gc 수행이 필수적이지만 addtional writes로 인해 gc 오버헤드 발생
그럼에도 로그 구조 시스템을 쓰는 이유는 최신 스토리지 디바이스에서 효과적이기 때문
특정 데이터에 대한 overwrite를 지원하지 않는 ssd, nand flash memory는 페이지 단위로 기록하고 블록 단위로 지움
덮어쓰기를 방지해서 write amplification 문제를 줄이고 수명을 늘림
최신 스토리지 기술이 빠른 쓰기를 요하므로 데이터베이스, 파일 시스템, 스토리지 펌웨어 등을 위해 로그 구조 시스템을 사용하기도 하며 최신 변경 사항이 로그로 남아있어서 크래시 리커버리와 데이터 정합성 유지하기 쉬움
다만 삭제한 공간이 남아서 fragmentation이 발생하기도 함. 파편화를 해결하기 위해 compaction 압축을 수행함
데이터가 여러 로그에 분산되어 있어서 읽을 때 서치 코스트가 증가하는 문제는 bloom filter나 indexing으로 완화함
삭제된 데이터를 정리하기 위해 가비지 컬렉션이 필요하기 때문에 효율적인 GC 알고리즘을 사용함
MiDAS가 해결하고자 한 문제
- 로그 구조 시스템에서 발생하는 쓰기 증폭 문제
쓰기 성능 향상을 위해 사용하는 로그 구조 시스템에서 GC 비용이 매우 크다는 단점이 있음
GC로 인해 쓰기 증폭이 크게 발생하는 것은 WAF 값으로 확인할 수 있고
WAF는 ssd에 기록된 총 데이터 양을 사용자가 기록한 양으로 나누어 알 수 있으며
WAF가 높으면 ssd 수명이 줄고 성능이 저하됨
선행 연구 조사
- 롸잇 앰플리피케이션 감소를 위한 접근법 1. victim selection policy
GC를 수행할 떄 어느 블록을 먼저 제거할지 결정하는 방법
fifo 가장 오래된 블록
greedy 가장 적은 valid data를 가진 블록
cost benefit 블록의 age와 valid data 비율을 고려해서 선택
- 롸잇 앰플리피케이션 감소를 위한 접근법 2. data placement policy
수명이 유사한 블록 그룹화해서 GC시 데이터 이동 최소화
https://dev-charlotte.tistory.com/220
The Importance of Data Placement Policies in Reducing Write Amplification Caused by Garbage Collection (GC로 인한 쓰기 증
waf 감소를 위해서는 gc 최적화도 중요하지만 가장 중요한 것은 데이터 플레이스먼트 정책! 데이터 배치 정책의 핵심은 비슷한 인벨리드 타임의 데이터 블록끼리 그룹핑하는 것이다데이터 블록
dev-charlotte.tistory.com
MiDAS가 문제 해결을 위해 도입한 방법
- adaptive group configuration (num ber of group, group 1 size)
- hot block isolation
- markov chain based analytical model = MCAM (가장 낮은 WAF를 보장하는 그룹 구성을 선택)
- UID update interval distribution 기반 예측 모델 (데이터 블록 업데이트 간격 분석으로 각 블록이 얼마나 오래 유지될지 예측하고 비슷한 수명 가진 블록끼리 그룹화)