> For the complete documentation index, see [llms.txt](https://gunkim.gitbook.io/undefined/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://gunkim.gitbook.io/undefined/compaction-strategies.md).

# compaction-strategies

### 배운 개념

* **컴팩션 병합(Merge)의 효율성**: 두 정렬된 파일의 맨 앞부분만 적은 메모리에 올려 비교하며 전진하는 **병합 정렬(Merge Sort)** 방식을 사용해 O(N)으로 대용량 파일도 가볍게 합침.
* **전략별 트레이드오프**:
  * **크기 기반(Size-tiered)**: 디스크에 쓰는 횟수가 적어 '쓰기 증폭'은 적지만, 병합 주기가 길어 과거 데이터가 오래 남아 '공간 증폭'이 심함.
  * **레벨 기반(Leveled)**: L0을 제외한 각 레벨(L1, L2, ...) 내의 모든 파일은 **키 범위가 절대 겹치지 않도록(Non-overlapping)** 제어됨. 윗 레벨과 지속적으로 병합하여 '쓰기 증폭'은 손해 보지만, 쓰레기 데이터를 즉시 버려 '공간 증폭'을 억제하고 읽기 성능을 최적화함 (RocksDB/LevelDB 실무 기본값).

### 깊이 있는 이해

* **읽기 성능 차이 원인**: 크기 계층은 같은 그룹 내 여러 파일들의 키 범위가 서로 겹치므로 특정 키를 찾기 위해 모든 파일을 다 뒤져야 함. 레벨 기반은 각 레벨마다 키 범위가 겹치지 않는 딱 하나의 파일만 타겟하여 탐색할 수 있어 읽기 효율이 뛰어남.
* **쓰기 증폭(WA)의 구체적 메커니즘**: 레벨 기반에서 키 범위 비중첩 설계를 고수하기 위해 윗 레벨에서 아래 레벨로 데이터를 밀어내릴 때(예: L1 -> L2), 하위 레벨의 겹치는 키 범위를 가진 기존 파일들을 전부 읽어 새로 병합 정렬하여 디스크에 써야 함. 10MB 데이터를 아래로 내릴 때 L2에 겹치는 데이터가 100MB 있으면 총 110MB를 디스크에 쓰는 비효율이 발생함.

> \[!WARNING] **헷갈린 점: 크기 계층의 중복 제거와 읽기 증폭** 크기 계층도 병합 컴팩션을 거치면 병합 파일 내에서 중복이 지워지지만, 컴팩션 단위가 파일 크기 기준이라 **같은 그룹 내 여러 파일끼리는 키 범위가 여전히 겹친다.** 따라서 완벽히 병합이 끝나기 전에는 같은 키의 서로 다른 버전들이 여러 파일에 흩어져 있을 수 있어 여전히 다중 탐색(읽기 증폭)이 필요함.

### 복습 체크

* [ ] 컴팩션 시 메모리 낭비 없이 대용량 파일을 합치는 알고리즘적 원리는 무엇인가?
* [ ] 크기 기반 전략과 레벨 기반 전략의 쓰기 증폭, 공간 증폭 측면의 장단점은?
* [ ] 레벨 기반 컴팩션에서 아래 레벨로 데이터를 내릴 때 쓰기 증폭이 크게 발생하는 구체적 원인은 무엇인가?
* [ ] 크기 계층 방식도 병합(컴팩션) 시 중복이 제거됨에도 불구하고, 검색 시 읽기 증폭이 큰 이유는 무엇인가?

\[\[lsm-tree]]


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://gunkim.gitbook.io/undefined/compaction-strategies.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.