GC (Garbage Collection) 최적화 기법 (CAT, AutoStream, MiDA, SepBIT, MiDAS)

Garbage Collection을 최적화 시키는 방법 중 GC가 데이터를 이동시키는 과정에서 발생하는 쓰기 증폭 Write Amplification Factor WAF를 줄이기 위해 설계된 기법 다섯 가지의 주된 특징 비교

 

 

CAT

Mei-Ling Chiang and Ruei-Chuan Chang.

Cleaning Policies in Mobile Computers Using Flash Memory.

Journal of Systems and Software, 48(3):213–231, 1999.

 

AutoStream

Jingpei Yang, Rajinikanth Pandurangan, Changho Choi, and Vijay Balakrishnan. 

AutoStream: Automatic stream management for multi-streamed SSDs.

In Proceedings of the ACM International Systems and Storage Conference, pages 1–11, 2017.

 

MiDA

Hyunseung Park, Eunjae Lee, Jaeho Kim, and Sam H. Noh. 

Lightweight Data Lifetime Classification Using Migration Counts to Improve Performance and Lifetime of Flash-Based SSDs. 

In Proceedings of the ACM SIGOPS Asia-Pacific Workshop on Systems, pages 2533, 2021.

 

SepBIT

Qiuping Wang, Jinhong Li, Patrick P.C. Lee, Tao Ouyang, Chao Shi, and Lilong Huang.

Separating Data via Block Invalidation Time Inference for Write Amplification Reduction in Log-Structured Storage.

In Proceedings of the USENIX Conference on File and Storage Technologies, pages 429–444, 2022.

 

MiDAS

Seonggyun Oh, Jeeyun Kim, and Soyoung Han, DGIST; Jaeho Kim, Gyeongsang National University; Sungjin Lee, DGIST; Sam H. Noh, Virginia Tech.

MiDAS: Minimizing Write Amplification in Log-Structured Systems through Adaptive Group Number and Size Configuration.

In Proceedings of the 22nd USENIX Conference on File and Storage Technologies (FAST'24), 2024.

 

 

이 다섯 가지 기법은 모두 gc를 최적화하기 위한 전략이지만 데이터를 분류하는 방식과 gc를 수행하고 최적화시키는 방식은 조금씩 다르다. 

 

기법	핵심 개념	데이터 분류 방식	GC 최적화 방식	주요 특징
CAT (Cold and Active data separation)	데이터 변경 빈도를 기반으로 한 분리	Hot(자주 변경) / Cold(거의 변경되지 않음) 데이터를 분류	GC 시 Cold 블럭을 우선 삭제	Cold 블럭을 별도 관리하여 Hot 블럭의 불필요한 이동 방지
AutoStream	I/O 패턴을 기반으로 데이터 스트림 자동 분류	I/O 워크로드 패턴에 따라 스트림을 분리	동일 스트림 내에서만 GC 수행	스트림 간 데이터 혼합을 방지하여 GC 비용 절감
MiDA (Multi-group Data Allocation)	데이터의 예상 수명에 따른 그룹화	데이터의 수명을 기준으로 여러 그룹을 유지	동일한 수명의 데이터끼리 그룹화하여 GC 수행	유효 블럭 이동을 최소화하여 쓰기 증폭 감소
SepBIT (Separation-Based Block Identification)	데이터 변경 패턴 분석 기반 블럭 분리	데이터 변경 패턴을 분석하여 블럭을 분리	GC 시 변경 패턴이 유사한 블럭끼리 정리	GC 대상 블럭을 최적화하여 불필요한 쓰기 감소
MiDAS	체인형 그룹 구조 + HOT 그룹 활용	데이터의 연령(Age)과 변경 주기 기반으로 그룹 이동	체인 구조를 통해 유효 블럭을 연령별로 이동, HOT 그룹을 활용하여 고빈도 업데이트 데이터 분리	UID+MCAM 모델을 활용하여 최적 그룹 구성을 동적으로 탐색

 

 

1) CAT 

데이터 변경 빈도 기준. HOT / COLD

hot 잦은 변경이 있으니 gc할 때 유지, cold는 gc로 정리해야할 대상이니까 우선 삭제해서 hot의 불필요한 이동을 줄임

 

2) AutoStream

ssd의 io 워크로드 패턴 분석해서 데이터 스트림 분리

동일 패턴의 데이터끼리 그룹핑, 한 스트림 안에서만 gc

다른 유형 데이터의 혼합 방지

 

3) MiDA 

데이터의 예상 라이프스팬을 기반으로 여러 그룹 유지, 같은 그룹에서만 gc

벨리드 데이터 블록의 이동 최소화

 

4) SepBIT

데이터 변경 패턴 분석 후 변경 빈도 높은 데이터끼리, 낮은 데이터끼리

 

5) MiDAS

데이터 일정 나이 되면 다음 그룹으로 자동 이동 (체인형 그룹 구조)

hot 그룹 별도 관리