2. MergeTree: How Data Lands on Disk

불변 part, granule, 희소 index, 그리고 merge가 하는 일

  • Haram Lee
  • 2026-10-15
  • studies / Topics / ClickHouse
#clickhouse #database #data-engineering

2.1 Parts and Merges

MergeTree table은 불변인 part들의 모음이다. INSERT가 한 번 들어올 때마다 그 행들로 part 하나가 새로 생긴다. part는 자기 내용을 해석하는 데 필요한 메타데이터를 스스로 담고 있어서, 중앙 카탈로그를 따로 조회하지 않아도 읽을 수 있다.

INSERT마다 part가 생기면 part 수가 금방 늘어난다. 그래서 background merge가 작은 part 여러 개를 큰 part 하나로 계속 합친다. part 안의 행은 table의 primary key 순서로 정렬돼 있다. 그래서 이 작업은 이미 정렬된 목록 여러 개를 하나로 모으는 k-way merge sort가 된다. 기본 설정에서는 part가 150GB에 이를 때까지 합친다.

flowchart LR
  p1["part 1"] --> m1["part 1_3"]
  p2["part 2"] --> m1
  p3["part 3"] --> m1
  p4["part 4"] --> m2["part 4_5"]
  p5["part 5"] --> m2

합쳐진 원본 part는 바로 지우지 않는다. 먼저 inactive로 표시하고, 그 part를 읽고 있는 쿼리가 모두 끝나 reference count가 0이 되면 그때 지운다. 그래서 merge가 진행 중이어도 이미 시작한 쿼리는 영향을 받지 않는다.

2.2 Synchronous and Asynchronous Inserts

INSERT 방식은 두 가지다.

synchronous insert에서는 INSERT 문 하나가 곧 part 하나다. merge 부담을 줄이려면 클라이언트가 행을 모아서 보내야 하고, 논문은 한 번에 2만 행 정도를 예로 든다. 문제는 클라이언트가 행을 모으는 동안 기다리는 시간이다. 실시간 분석이라면 이 지연만큼 데이터가 늦게 보인다.

asynchronous insert에서는 행을 묶는 일을 서버가 대신한다. 여러 클라이언트가 보낸 작은 INSERT를 서버가 버퍼에 모았다가, 버퍼 크기가 기준을 넘거나 시간이 다 되면 part 하나로 쓴다. 수천 개의 모니터링 에이전트가 조금씩 이벤트를 보내는 observability 환경을 염두에 둔 모드다. Kafka producer가 메시지를 batch로 묶어 보내는 것과 같은 발상을 서버 쪽에서 구현한 셈이다.

2.3 How It Differs from LSM Trees

MergeTree는 LSM tree에서 아이디어를 가져왔지만, 세 가지가 다르다.

첫째, level 계층이 없다. 일반적인 LSM 구현은 part를 level로 나누고 같은 level끼리만 합친다. ClickHouse는 모든 part를 동등하게 보고 아무 part나 골라 합친다.

둘째, write-ahead log가 없다. 많은 LSM 저장소는 쓰기를 먼저 log에 남기고 memtable에 모았다가 flush한다. ClickHouse는 INSERT를 곧바로 디스크의 part로 쓴다.

셋째, tombstone이 없다. level이 없으니 part 사이에 “어느 쪽이 더 나중에 쓰였는가"를 따질 순서도 없다. LSM tree는 나중에 쓴 삭제 표시가 이전 값을 가리는 방식으로 삭제를 처리하는데, ClickHouse는 이 방식을 쓸 수 없다. 그래서 수정과 삭제에 별도의 장치가 필요하다. 이 부분은 4장에서 다시 본다.

2.4 Inside a Part

part는 디스크에서 디렉터리 하나다. 그 안에 컬럼마다 파일이 하나씩 있다. 다만 10MB보다 작은 part는 읽기와 쓰기의 지역성을 높이려고 모든 컬럼을 파일 하나에 이어 붙여 저장한다.

part 안의 행은 논리적으로 8,192행씩 granule로 나뉜다. granule은 scan과 index 조회가 다루는 가장 작은 단위다. 그러나 실제 디스크 읽기와 쓰기는 granule이 아니라 block 단위로 한다. block은 이웃한 granule 여러 개를 묶은 것으로, 기본 크기는 약 1MB다. 같은 1MB에 들어가는 granule 수는 컬럼의 타입과 값 분포에 따라 달라진다.

text 
part/
├── event_time.bin
├── page.bin
└── lcp_ms.bin
     ├── block (압축, 약 1MB)
     │    ├── granule 0  (8,192행)
     │    └── granule 1
     └── block
          └── granule 2

block은 압축해서 저장한다. 기본 codec은 LZ4이고, 부동소수점에는 Gorilla나 FPC 같은 전용 codec을 지정할 수 있다. codec은 여러 개를 이어서 걸 수도 있다. 예를 들어 숫자 컬럼에 delta 인코딩을 먼저 걸어 값의 중복을 줄이고, 그 위에 무거운 압축을 걸고, 마지막으로 AES로 암호화할 수 있다.

압축된 block 안에서 특정 granule을 바로 찾아가려면 위치 정보가 필요하다. ClickHouse는 컬럼마다 mark라는 매핑을 둔다. mark는 granule 번호마다 그 granule을 담은 압축 block이 파일의 어디에서 시작하는지, 그리고 압축을 푼 block 안에서 granule이 어디에서 시작하는지를 기록한다.

컬럼 타입을 감싸는 장치도 두 가지 있다. LowCardinality(T)는 값을 정수 id로 바꾸는 dictionary 인코딩이고, 종류가 적은 문자열 컬럼의 저장량을 크게 줄인다. Nullable(T)는 NULL 여부를 담은 bitmap을 컬럼 옆에 붙인다.

2.5 The Primary Key Is a Sparse Index

ClickHouse의 primary key는 유일성 제약이 아니다. primary key 컬럼은 part 안에서 행을 정렬하는 순서를 정하고, 동시에 그 순서 위에 희소 index를 만든다.

희소하다는 것은 행마다 index 항목을 두지 않는다는 뜻이다. index에는 granule마다 첫 행의 key 값 하나만 들어간다. 그래서 index가 매우 작다. 논문의 예에서는 810만 행을 1,000개 항목으로 색인한다. 이 정도면 index를 통째로 메모리에 둘 수 있다.

flowchart LR
  idx["index<br/>10:00 · 10:01 · 10:02 · 10:03 · 10:04 · 10:06 · 10:07"] --> search["이진 탐색<br/>event_time >= 10:05"]
  search --> skip["앞쪽 granule 건너뜀"]
  search --> read["뒤쪽 granule만 읽음"]

WHERE event_time >= '10:05:00' 같은 조건이 오면 ClickHouse는 index를 이진 탐색해 조건을 만족할 수 있는 granule 범위를 찾고, 그 범위만 읽는다. index가 granule 단위라서 결과는 행 단위로 정확하지 않다. 경계에 걸친 granule은 통째로 읽고, 읽은 뒤에 필터로 다시 거른다.

이 탐색은 조건이 primary key의 앞쪽 컬럼에 걸려 있을 때 잘 동작한다. ClickHouse는 key 값의 범위를 왼쪽 컬럼부터 차례로 따져, 범위 안의 값이 조건을 모두 만족하는지, 모두 만족하지 않는지, 섞여 있는지를 판정한다. 섞여 있으면 범위를 잘게 나눠 다시 판정한다. 조건에 함수가 끼어 있어도 index를 쓸 수 있는 경우가 있다. toYear(k) = 2024는 k >= '2024-01-01' AND k < '2025-01-01'로 바꿔 index를 탈 수 있다. 함수의 단조성이나 역상을 엔진이 알고 있어서 가능한 변환이다.

2.6 Seeing Pruning Happen

직접 확인해 봤다. 로컬 docker로 ClickHouse 24.8을 띄우고, 합성 LCP 이벤트 520만 건을 넣었다. table은 ORDER BY (metric, page, event_time)이고 날짜로 partition을 나눴다. 그리고 최근 5분 조건으로 EXPLAIN indexes = 1을 실행했다.

text 
ReadFromMergeTree (web_perf_raw)
  MinMax      event_time           Granules: 190/636
  Partition   toDate(event_time)   Granules: 190/190
  PrimaryKey  metric, event_time   Granules: 30/190

전체 granule 636개 중 part별 min, max 값으로 거르자 190개가 남았고, primary key 탐색을 거치자 30개만 남았다. 실제로 읽은 행은 520만 행 중 238,650행이었다. 시간 조건 없이 전체를 읽은 쿼리의 22분의 1이다.

2.7 Other Ways to Skip Data

primary key는 table당 정렬 순서 하나뿐이다. 다른 컬럼으로 거르는 쿼리를 빠르게 하려면 다른 장치가 필요하다.

projection은 같은 행을 다른 primary key로 정렬한 사본을 table 안에 두는 방법이다. optimizer가 예상 I/O를 비교해 원본과 projection 중 하나를 고른다. 그 대가로 INSERT와 merge 비용이 늘고 저장 공간을 더 쓴다. 또 projection은 기본적으로 새로 들어온 part에만 채워지므로, 기존 part까지 쓰려면 직접 materialize해야 한다.

skipping index는 projection보다 가벼운 대안이다. granule 여러 개를 묶은 단위마다 작은 요약을 저장해 두고, 요약만 보고 해당 묶음을 건너뛸지 판단한다. 요약의 종류는 세 가지다. min-max index는 묶음의 최솟값과 최댓값을 저장하며, 대략 정렬된 데이터에 잘 맞는다. set index는 묶음 안의 고유 값들을 저장하며, 같은 값이 한곳에 뭉쳐 있을 때 효과가 있다. bloom filter index는 행, 토큰, n-gram 단위로 만들 수 있어 문자열 검색에 쓰지만, 범위 조건이나 부정 조건에는 쓸 수 없다.

partition으로도 데이터를 거를 수 있다. ClickHouse는 partition마다 partition 식의 최솟값과 최댓값을 저장해 두고, 조건에 맞지 않는 partition을 통째로 건너뛴다.

2.8 Merges That Transform Data

merge는 part를 합치기만 하는 것이 아니라, 합치는 동안 데이터를 바꿀 수도 있다. 어떻게 바꿀지는 table engine이 정한다.

Replacing merge는 primary key가 같은 행 중 가장 최근에 들어온 것만 남긴다. 별도의 version 컬럼으로 남길 행을 정할 수도 있다. 자주 바뀌는 데이터를 갱신하거나 중복을 제거할 때 쓴다.

Aggregating merge는 key가 같은 행들을 하나로 합치면서, key가 아닌 컬럼에 담긴 부분 집계 상태를 합친다. 부분 집계 상태란 최종 결과가 아니라 결과를 낼 수 있는 중간값이다. avg()라면 합계와 개수 두 값이고, p75라면 t-digest 요약이다.

TTL merge는 오래된 데이터를 정리한다. 조건을 만족한 part를 S3 같은 싼 저장소로 옮기거나, 더 무거운 codec으로 다시 압축하거나, 지우거나, 집계해 줄인다.

sql 
CREATE TABLE tab (ts DateTime, msg String)
ENGINE = MergeTree PRIMARY KEY ts
TTL ts + INTERVAL 1 WEEK TO VOLUME 's3';

merge 시점의 변환에는 분명한 한계가 있다. merge가 언제 돌지 알 수 없으므로, 어느 순간에 조회하든 중복이나 덜 합쳐진 행이 남아 있을 수 있다. 결과를 확실히 보장해야 하면 SELECT ... FINAL로 쿼리 시점에 같은 변환을 한 번 더 해야 하고, 그만큼 조회가 느려진다.

Incremental Materialized Views

Aggregating merge가 가장 큰 효과를 내는 곳은 materialized view다. 많은 데이터베이스는 materialized view를 주기적으로 원본 전체에서 다시 계산한다. ClickHouse는 다르게 동작한다. 원본 table에 새 part가 들어올 때마다, 그 part의 행에 대해서만 변환 쿼리를 실행하고 결과를 view의 table에 넣는다.

flowchart LR
  part["새 part<br/>(INSERT된 행만)"] --> query["변환 쿼리<br/>quantileTDigestState"]
  query --> sa["상태 part A"]
  query --> sb["상태 part B"]
  sa --> merged["합친 상태<br/>(Aggregating merge)"]
  sb --> merged

변환 쿼리에서는 avg() 대신 avgState()처럼 -State 접미사를 붙인 집계 함수를 쓴다. 이 함수는 최종 값이 아니라 부분 상태를 돌려준다. view의 table은 AggregatingMergeTree라서 merge할 때마다 같은 key의 부분 상태를 합친다. 조회할 때는 avgMerge()처럼 -Merge 접미사를 붙인 함수로 남은 상태들을 마저 합쳐 최종 값을 낸다.

이 구조 덕분에 “최근 5분 p75"를 매번 원본 수십만 행에서 계산하지 않고, 미리 집계해 둔 상태 몇천 개만 합치면 된다. 5장에서 실제로 이 구조를 만들어 본다.

Discussion