컴팩션

컴팩션은 쌓인 저장 파일 여럿을 다시 읽어 새 파일로 합치는 일입니다. 합치면서 같은 키의 옛 값과 지움 표시를 걷어냅니다. 파일 수가 줄고, 죽은 데이터가 물고 있던 자리가 돌아옵니다.

상세

냉장고에 반찬통이 쌓입니다. 한 번에 다 꺼낼 수는 없어서, 상에 늘어놓을 만큼만 골라 꺼내 같은 반찬을 한 통에 몰아 담고 오래된 통은 버립니다. 그러는 사이 새 반찬통이 또 들어오고, 몰아 담은 통도 도로 냉장고로 들어가 다음번에 다시 꺼내집니다.

컴팩션은 저장소가 쌓아 둔 정렬 파일 여럿을 읽어 새 정렬 파일로 다시 쓰는 동작입니다. 이런 저장소는 갱신을 제자리에서 하지 않습니다. 같은 키를 다시 써도 옛 값이 있던 자리를 고치지 않고, 새 파일에 새 값을 덧붙입니다. 그래서 한 키의 값이 여러 파일에 흩어져 남습니다. 컴팩션은 그 흩어진 것을 한자리로 모으는 일입니다.

동작이 성립하려면 세 가지가 정해져야 합니다. 언제 시작할지, 어느 파일을 고를지, 무엇을 버릴지입니다. 이 셋을 묶어 정한 것을 컴팩션 전략이라고 부릅니다.

flowchart TD
    A[쓰기] --> B[메모리 버퍼]
    B -->|가득 차면 내려보낸다| C[정렬 파일이 쌓인다]
    C -->|조건이 맞으면| D[골라서 읽고 합친다]
    D --> E[새 정렬 파일]
    E --> C

새 쓰기는 메모리 버퍼에 모였다가 파일 하나로 내려갑니다. 그 파일이 쌓이면 컴팩션이 몇 개를 골라 읽고 새 파일로 다시 씁니다. 합치는 동안에도 저장소는 새 쓰기를 계속 받습니다. 결과 파일은 다시 같은 더미에 들어가므로, 이 과정은 저장소가 도는 내내 되풀이됩니다.

버리는 것은 두 가지입니다. 한 키에 값이 여러 벌 있으면 최신 것만 남기고 나머지를 버립니다. 지움은 값을 즉시 없애는 대신 지움 표시를 새로 써서 남깁니다. 이 표시도 정리 대상입니다. 다만 표시는 아무 때나 못 버립니다. 아직 정리되지 않은 옛 값이 다른 파일에 남아 있으면, 표시를 먼저 버리는 순간 지운 값이 되살아납니다. 그래서 그 키의 더 오래된 값이 어디에도 없다는 것이 확인될 때만 표시를 함께 버립니다.

배경

값을 제자리에서 고치는 저장 방식은 쓰기 한 번에 디스크의 여기저기를 찾아가야 합니다. 로그 구조 저장소는 그 대신 새로 들어온 것을 메모리에 모았다가 통째로 새 파일로 내려보냅니다. 쓰기는 이어붙이기가 되지만, 대가로 같은 키의 옛 값이 파일마다 남고 파일 수가 계속 늘어납니다. 읽기는 그 파일들을 뒤져야 하고, 지운 데이터도 자리를 계속 차지합니다.

그래서 앞단의 쓰기와 별개로, 뒤에서 파일을 모아 다시 쓰는 일이 따로 필요해졌습니다. 읽을 때 뒤질 파일 수를 정해진 범위 안에 묶어 두고, 죽은 값이 물고 있던 자리를 되찾는 것이 그 일의 몫입니다.

이름은 나중에 붙었습니다. 1996년 LSM(Log-Structured Merge, 로그 구조 병합) 트리 논문은 이 절차를 컴팩션이라고 부르지 않았습니다. 메모리에 있는 C0 트리가 정해진 크기에 닿으면 그 일부를 잘라 디스크의 C1 트리에 합치는 과정을 rolling merge 라고 적었습니다. compaction 이라는 이름은 2006년 Bigtable 논문 5.4절의 제목으로 나옵니다. 그 절이 세 이름을 함께 정의합니다. 메모리 버퍼를 얼려 파일 하나로 내려보내는 minor compaction, 파일 몇 개와 메모리 버퍼를 읽어 새 파일 하나를 쓰는 merging compaction, 그리고 모든 파일을 정확히 하나로 다시 쓰는 major compaction 입니다.

갈래

축은 언제 어느 파일을 골라 합치느냐입니다. 합치는 절차 자체는 정렬된 파일 여럿을 병합하는 것으로 같습니다. 무엇을 언제 고르느냐가 갈리면 다시 쓰는 양과 읽을 때 뒤질 파일 수가 함께 갈립니다. RocksDB 위키는 컴팩션 알고리즘이 LSM 트리의 모양을 제약한다고 적습니다. 어느 정렬 런을 합칠 수 있는지, 그리고 읽기 한 번에 어느 정렬 런을 봐야 하는지를 컴팩션 알고리즘이 정한다는 뜻입니다.

leveled

레벨을 여러 층으로 두고 층마다 크기 상한을 둡니다. 레벨 하나가 정렬 런 하나이고, 아래 레벨은 위 레벨보다 몇 배씩 큽니다. 이 배수를 팬아웃이라고 부르기도 합니다. Ln 으로 들어가는 컴팩션은 Ln-1 의 데이터를 Ln 에 합칩니다. 이때 앞서 Ln 에 합쳐 둔 데이터를 다시 씁니다. 레벨 하나당 쓰기 증폭은 최악의 경우 팬아웃과 같지만 실제로는 그보다 작은 쪽으로 기우는 편이라고 RocksDB 위키는 적습니다. 원래 LSM 트리 논문의 컴팩션은 Ln-1 전부와 Ln 전부를 합치는 방식이었고, LevelDB 와 RocksDB 는 겹치는 범위만 골라 합칩니다.

flowchart TD
    L0["레벨 0 · 범위가 겹친다"] -->|파일 수가 기준에 닿으면| L1["레벨 1"]
    L1 -->|크기 상한을 넘으면| L2["레벨 2"]
    L2 -->|같은 규칙| Ln["레벨 n"]

발동 조건은 개수와 크기입니다. LevelDB 는 레벨 L 의 파일 크기 합이 상한을 넘으면 L 에서 파일 하나를 고르고, L+1 에서 그 범위와 겹치는 파일을 전부 골라 함께 합칩니다. 레벨 0 은 예외입니다. 레벨 0 의 파일끼리는 키 범위가 겹칠 수 있어서 대개 전부를 한꺼번에 집어 올립니다. RocksDB 는 여러 레벨이 동시에 조건을 만족할 때 레벨마다 점수를 매겨 제일 높은 레벨을 먼저 합칩니다. 0 이 아닌 레벨의 점수는 레벨 크기 합을 목표 크기로 나눈 값입니다. 레벨 0 의 점수는 파일 개수를 level0_file_num_compaction_trigger 로 나눈 값과 크기 합을 max_bytes_for_level_base 로 나눈 값 중 큰 쪽입니다.

tiered

크기가 비슷한 정렬 런을 여러 개 모아 두었다가 한꺼번에 합칩니다. 정렬 런의 개수가 기준 N 에 닿을 때만 컴팩션을 시작합니다. 고를 때는 제일 작은 파일에서 출발해, 지금까지 고른 크기보다 크지 않은 런을 하나씩 더 넣습니다. 한 레벨의 정렬 런을 모두 합쳐 다음 레벨의 새 정렬 런 하나를 만들고, 합쳐 넣는 쪽 레벨의 정렬 런은 읽지도 다시 쓰지도 않습니다. 그래서 레벨당 쓰기 증폭이 1 입니다.

같은 방식을 제품마다 다른 이름으로 부릅니다. 카산드라는 STCS(Size Tiered Compaction Strategy)라고 부르고 기본 전략으로 씁니다. 크기가 대략 비슷한 SSTable 을 합친다는 것이 그 전제입니다. RocksDB 는 코드에서 Universal 이라는 이름을 씁니다. ScyllaDB 의 ICS(Incremental Compaction Strategy)는 STCS 와 원리가 같고, 합치는 단위를 일정한 크기의 조각으로 끊습니다.

시간 창과 FIFO

고르는 기준을 크기가 아니라 시간에 두는 갈래입니다. 카산드라의 TWCS(Time Window Compaction Strategy)는 유효 기간이 붙어 있고 한 번 쓰면 거의 바뀌지 않는 시계열 데이터를 겨냥합니다. RocksDB 의 FIFO(First In First Out, 먼저 들어온 것이 먼저 나감) 방식은 합치는 대신 쓸모없어진 제일 오래된 파일을 버립니다. 캐시처럼 쓰는 데이터에 씁니다.

minor compaction 과 major compaction

같은 저장소 안에서도 컴팩션이 무엇을 대상으로 삼느냐가 갈립니다. 카산드라는 저절로 도는 것을 minor compaction, 노드의 모든 SSTable 을 대상으로 사람이 실행하는 것을 major compaction 이라고 부릅니다. HBase 의 minor compaction 은 서로 이웃한 작은 StoreFile 몇 개를 골라 하나로 다시 씁니다. 생길 수 있는 부작용 때문에 지움 표시와 기한이 지난 판은 걷어내지 않습니다. major compaction 의 결과는 스토어마다 StoreFile 하나이고, 이때 지움 표시와 최대 판 수를 함께 처리합니다. Bigtable 논문도 모든 파일을 정확히 하나로 다시 쓰는 것을 major compaction 이라고 적습니다.

대가

컴팩션은 이미 디스크에 잘 있는 데이터를 다시 읽고 다시 쓰는 일입니다. 사용자가 요청한 적 없는 입출력이라, 얻는 것과 내주는 것이 늘 같이 옵니다. 저장소 문서들은 그 값을 세 가지 증폭으로 갈라 적습니다. 쓰기 증폭은 한 번 쓴 데이터를 몇 번 다시 쓰게 되는지, 읽기 증폭은 한 번 읽을 때 몇 개의 파일을 뒤지게 되는지, 공간 증폭은 살아 있는 데이터에 견줘 디스크를 얼마나 더 쓰는지입니다.

세 가지를 한꺼번에 줄일 수는 없습니다. RocksDB 위키는 leveled 가 읽기 증폭과 쓰기 증폭을 대가로 공간 증폭을 최소화한다고 적습니다. tiered 는 반대로 읽기 증폭과 공간 증폭을 대가로 쓰기 증폭을 최소화합니다. tiered 쪽은 정렬 런의 최악 개수가 leveled 보다 훨씬 많아서, 읽을 때 입출력 비용이나 CPU(Central Processing Unit, 중앙처리장치) 비용이 더 들 수 있습니다. 큰 정렬 런은 블록 인덱스와 블룸 필터도 커지고, 합치는 데 시간이 오래 걸립니다.

쓰기 증폭의 크기는 방식이 정합니다. LevelDB 문서는 그 양을 수치로 적어 뒀습니다. 레벨 0 컴팩션은 레벨 0 에서 1MB 파일 네 개까지 읽고 최악의 경우 레벨 1 파일 전부인 10MB 를 읽어, 14MB 를 읽고 14MB 를 씁니다. 그 밖의 레벨에서는 2MB 파일 하나를 고릅니다. 최악의 경우 다음 레벨의 파일 12개쯤과 겹쳐서 26MB 를 읽고 26MB 를 씁니다. 디스크 입출력을 초당 100MB 로 잡으면 최악의 컴팩션 한 번이 약 0.5초입니다. ScyllaDB 문서는 LCS(Leveled Compaction Strategy)가 쓰기에서 입출력이 두 배로 든다고 적습니다. 그래서 새 데이터를 주로 쓰는 작업 부하에는 그만큼 좋지는 않다고 덧붙입니다.

공간은 두 갈래로 나갑니다. 죽은 값이 합쳐질 때까지 자리를 차지하고, 합치는 동안에는 입력 파일과 출력 파일이 함께 디스크에 있습니다. ScyllaDB 문서는 STCS 에서 덮어쓰기가 잦은 작업 부하일 때 한 티어 안에서 데이터가 네 배로 불어나 부담이 400% 에 이를 수 있다고 적습니다. 입력 SSTable 네 개와 출력 하나를 합쳐 지금 담고 있는 양의 다섯 배가 필요해지는 경우입니다. 같은 문서는 최악의 경우 디스크의 절반이 비어 있어야 컴팩션이 돌 수 있다고 적습니다. LCS 는 낡은 행이 낭비하는 공간이 최대 10% 이고, 컴팩션이 임시로 쓰는 자리도 작은 SSTable 크기의 10배 정도만 잡아 두면 된다고 적혀 있습니다. RocksDB 의 Universal 방식도 전체 컴팩션이 필요할 때 출력 크기가 입력과 비슷해서, 도는 동안 디스크 사용량이 일시적으로 두 배가 됩니다.

파라미터를 어느 쪽으로 돌려도 값이 붙습니다. HBase 문서는 minor compaction 의 대상 선정 비율을 예로 듭니다. 이 값을 1.4 처럼 올리면 더 큰 StoreFile 을 합치게 되어 쓰기 비용이 늘고, 대신 읽을 때 훑을 StoreFile 이 줄어듭니다. RocksDB 위키는 레벨 0 파일이 너무 많으면 대부분의 질의에서 읽기 성능을 해치므로 레벨 0 안에서 파일 몇 개를 미리 합치기도 한다고 적습니다. 이때 쓰기 증폭을 1 만큼 더 치릅니다. HBase 문서는 컴팩션 자체가 자원을 많이 쓰는 작업이고, 여러 요인에 따라 성능에 도움이 될 수도 해가 될 수도 있다고 적습니다.

컴팩션이 앞단 쓰기를 못 따라가면 저장소가 쓰기 자체를 늦춥니다. RocksDB 위키는 내려보내기나 컴팩션이 들어오는 쓰기 속도를 못 따라갈 때 쓰기를 늦추는 장치를 두었다고 적습니다. 그런 장치가 없으면, 하드웨어가 감당하는 양보다 더 많이 쓰는 동안 공간 증폭이 늘어납니다. 디스크가 바닥날 수 있습니다. 읽기 증폭도 늘어 읽기 성능이 크게 나빠집니다. 장치의 목적은 들어오는 쓰기를 저장소가 감당할 수 있는 속도까지 낮추는 것입니다.

지연이 걸릴 수 있는 조건은 세 가지라고 같은 문서는 적습니다. 내려보내기를 기다리는 메모리 버퍼가 max_write_buffer_number 에 닿으면 쓰기가 완전히 멈춥니다. max_write_buffer_number 가 3 보다 크면, 그보다 하나 적은 수에 닿는 시점부터 쓰기가 지연됩니다. 레벨 0 파일이 level0_slowdown_writes_trigger 에 닿으면 쓰기가 지연됩니다. level0_stop_writes_trigger 에 닿으면 완전히 멈춥니다. 컴팩션이 밀린 양이 soft_pending_compaction_bytes 에 닿으면 지연, hard_pending_compaction_bytes 에 닿으면 정지입니다.

조건이 걸리면 쓰기 속도가 delayed_write_rate 까지 내려갑니다. 밀린 양이 더 쌓이면 그보다 더 낮아질 수도 있습니다. 발동 기준은 열 패밀리마다 따로 잡히지만, 열 패밀리 하나가 그 기준에 닿으면 지연은 데이터베이스 전체에 걸립니다. 쓰기를 부른 스레드는 느려진 동안 한 번에 대개 1밀리초씩 자고 진행합니다. 완전히 멈춘 동안에는 기약 없이 막힐 수 있습니다. WriteOptions 의 no_slowdown 을 켜면 막히지 않는 대신 그 쓰기가 Status::Incomplete() 로 즉시 되돌아옵니다.

예시

RocksDB

컴팩션 방식은 열 패밀리 옵션 하나로 고릅니다. AdvancedColumnFamilyOptions::compaction_style 이 받는 값은 네 가지입니다. kCompactionStyleLevel 이 기본값이고 kCompactionStyleUniversal · kCompactionStyleFIFO · kCompactionStyleNone 이 나머지입니다. kCompactionStyleNone 을 고르면 컴팩션이 저절로 돌지 않고 CompactRange() 나 CompactFiles() 를 불러 손으로 돌려야 합니다.

발동 조건과 파일 크기는 따로 정합니다. ColumnFamilyOptions::level0_file_num_compaction_trigger 의 기본값은 4 입니다. 레벨 0 파일이 네 개가 되면 레벨 0 컴팩션이 시작되고, 음수를 넣으면 파일 개수로는 시작하지 않습니다. AdvancedColumnFamilyOptions::target_file_size_base 의 기본값은 64MB, target_file_size_multiplier 의 기본값은 1 입니다. 앞의 값이 레벨 1 의 파일 하나 크기이고, 뒤의 값을 레벨마다 곱해 아래 레벨의 파일 크기가 정해집니다. DBOptions::max_subcompactions 의 기본값은 1 입니다. 컴팩션 하나를 최대 몇 개로 쪼개 돌릴지를 정합니다.

Apache Cassandra

테이블을 만들 때 전략을 지정합니다.

CREATE TABLE timeline (
    userid uuid,
    posted_month int,
    posted_time uuid,
    body text,
    posted_by text,
    PRIMARY KEY (userid, posted_month, posted_time)
) WITH compaction = { 'class' : 'LeveledCompactionStrategy' };

class 는 최소한 적어야 하는 값입니다. 받는 이름은 SizeTieredCompactionStrategy · LeveledCompactionStrategy · TimeWindowCompactionStrategy 이고, 적지 않으면 SizeTieredCompactionStrategy 입니다. DateTieredCompactionStrategy 도 받지만 폐기 예정이라 TimeWindowCompactionStrategy 를 쓰라고 적혀 있습니다. 공통 옵션인 min_threshold 의 기본값은 4, max_threshold 의 기본값은 32 입니다. 컴팩션이 시작되기 전 SSTable 개수의 아래위 한계이고, LeveledCompactionStrategy 에서는 쓰이지 않습니다.

Apache HBase

hbase.hstore.compactionThreshold 는 컴팩션이 돌기 전에 대상이 되어야 하는 StoreFile 의 최소 개수입니다. 값을 비워 두면 코드 로직에 따라 3 이 됩니다. 2 로 두면 스토어에 StoreFile 이 두 개만 생겨도 minor compaction 이 돕니다. 문서는 그게 대체로 적절하지 않다고 적습니다. hbase.hstore.compaction.max 는 minor compaction 한 번에 고를 StoreFile 의 최대 개수입니다. hbase.hstore.compaction.ratio 는 최소 크기보다 큰 StoreFile 을 대상으로 삼을지 정하는 비율이고, 문서는 1.0 에서 1.4 사이를 권합니다. major compaction 사이의 간격은 기본값이 7일입니다. 값은 밀리초로 적습니다.

관련 항목

컴팩션을 이루는 구성 요소

정렬 런 · SSTable · StoreFile · 메모리 버퍼 · 블룸 필터 · 툼스톤(tombstone, 지움 표시)

컴팩션을 재는 지표

쓰기 증폭 · 읽기 증폭 · 공간 증폭 · 팬아웃

컴팩션이 갈리는 세부 유형

minor compaction · merging compaction · major compaction

컴팩션을 실제로 구현·채택한 저장소

RocksDB · LevelDB · 카산드라 · ScyllaDB · HBase · Bigtable

컴팩션의 하위 전략

STCS · LCS · TWCS · ICS · Universal Compaction(RocksDB 가 tiered 컴팩션을 부르는 이름) · FIFO

컴팩션과 이름이 겹치는 이웃

log compaction(카프카, 키마다 최신 값만 남기는 보존 정책) · memory compaction(리눅스 커널, 흩어진 페이지를 옮겨 연속 블록을 만드는 일)