Data Eng Wiki

Compaction Maps

11 min read

Compaction Maps

Author: Chris Douglas | Source: cdouglas.github.io | Published: 2026-08-28 (ACM SIGMOD/PODS 2026, FORMATS workshop)

한 줄 요약

Compaction은 논리적으로 noop인데도 옛 레이아웃을 참조하는 동시 트랜잭션을 무효화해 재실행을 강요하는데, 옛 레이아웃 → 새 레이아웃 position 매핑을 기록한 작은 자료구조(compaction map) 하나로 재실행 없이 conflict를 수리해 수 분을 수십~수백 밀리초로 줄인다.

핵심 주장/내용

  • 문제: 업데이트가 테이블 상태뿐 아니라 레이아웃에도 의존한다: 테이블 포맷은 기저 스토어의 오브젝트 사이 직접 참조를 저장한다. write amplification을 줄이려 대부분의 포맷이 delta update로 기존 스냅샷을 패치하게 허용하고, reader는 checkpoint에 delta를 병합해 스냅샷 상태를 계산한다
    • Iceberg에서 position delete vector가 특정 오브젝트의 행을 논리적 위치로 tombstone한다. 가 base.parquet의 행을 업데이트하면 base.parquet을 참조하는 position delete vector와 새 오브젝트 delta-i.parquet을 쓴다. 겹치는 행을 업데이트하는 후속 는 base.parquet과 delta-i.parquet 둘 다에 대한 position delete vector를 쓴다
    • 핵심: 업데이트는 테이블의 상태뿐 아니라 그 레이아웃에도 의존한다. 트랜잭션이 특정 오브젝트와 오프셋을 참조한다
    • Iceberg v2는 position delete vector를 Parquet 파일로, v3는 Puffin 포맷의 Roaring bitmap으로 인코딩한다. 성능 특성은 다르지만 기저 문제는 같다 — 레이아웃 변경이 옛 레이아웃 오브젝트에 대한 참조를 무효화한다
  • 왜 compaction이 필요하고 왜 conflict를 일으키나: delta commit이 reader에 병합 비용을 부과해 쿼리 레이턴시를 최대 2~3배 올린다. 이 오버헤드를 피하려 테이블 포맷은 주기적으로 모든 live 행을 새 오브젝트 집합으로 병합해 compact한다
    • 논리적으로 compaction은 테이블의 행을 재조직하는 noop 트랜잭션이지만, 옛 레이아웃을 참조하는 동시 트랜잭션과 충돌한다. 동시 트랜잭션의 delta commit은 테이블의 같은 행을 참조하지만 position delete vector의 referent가 새 레이아웃에 존재하지 않는다
    • 대칭적으로, compaction이 도는 동안 커밋된 트랜잭션이 그 결과를 무효화할 수 있다 — 그 트랜잭션의 deletion vector가 compaction이 준비한 스냅샷에서 생략한 오브젝트를 참조하므로 compaction이 그 트랜잭션의 successor가 될 수 없다
  • 재실행의 악순환: 대부분의 레이아웃 conflict에 대한 해법은 재실행이고, 그것은 같은 데이터에 대해 같은 작업을 반복하는 것이다
    • 지속적 쓰기 하에서 실패한 compaction이 backlog로 쌓여 운영자를 더 작고 더 빈번한 compaction 쪽으로 밀어낸다. 그런데 각 compaction이 동시 트랜잭션과 충돌하는 새 커밋이므로 SLO가 있는 단순한 워크로드조차 튜닝이 어려워진다 — 테이블에 데이터를 적재하는 단일 writer 하나조차 compaction에 방해받아 데드라인을 놓칠 수 있다
    • 필요한 유지보수와 워크로드 튜닝 사이의 긴장이 프로덕션 테이블의 실제 문제다
  • 해법: 재실행 대신 rebase: compaction이 스냅샷의 모든 live 행을 보존하는 논리적 noop이므로, 옛 레이아웃에 대해 실행된 어떤 successor 트랜잭션도 compaction이 보존하는 데이터의 부분집합에 의존한다. 따라서 remapping이 건전(sound)하다
    • 과제는 트랜잭션 변경을 compact된 레이아웃 위로 rebase해 같은 논리 상태를 보존하는 새 successor를 만드는 것이고, 트랜잭션과 compaction 중 무엇이 먼저 커밋하든 대칭적이다
    • delta update의 rebase는 저렴하다: 새로 삽입된 행은 변하지 않고, 오직 (압축된) position delete vector만 옛 레이아웃을 참조한다. tombstone된 행의 위치만 찾을 수 있으면 position delete vector를 새 레이아웃을 가리키도록 다시 쓸 수 있다
    • compaction은 레이아웃 간 매핑을 만들지만 그것을 기록하지 않는다. compaction map이 바로 그 기록 — 옛 레이아웃의 position을 새 레이아웃으로 매핑하는 remapping 함수의 파라미터
    • compaction 하나가 여러 트랜잭션을 새 레이아웃 위로 rebase할 수 있다. 논리적으로 compaction은 과거 테이블 상태에 대한 항등 연산이므로 그 상태의 새 레이아웃과 충돌하는 트랜잭션 시퀀스를 rebase하는 것이 유효하다. 마찬가지로 트랜잭션이 compaction 체인과 commute할 수 있고, 구현이 remapping을 앞으로 “carry”해 compaction map 사이 의존성을 피한다. 다른 트랜잭션과의 진짜 conflict는 여전히 트랜잭션 엔진이 해결해야 한다
  • 구현: Iceberg 관례에 따라 프로토타입 compaction map을 Avro 파일로 인코딩. compaction은 보통 긴 행 run을 옮기므로 대부분의 remapping 함수를 기술하는 데 아주 적은 상태만 필요하다
    • 맵은 소스 레이아웃에서 새 위치로 재배치된 region — run — 을 저장한다. run 안에서의 행 위치가 compaction에서 보존되므로 새 위치는 tgt_start + (pos - src_start) 로 계산된다
    • compaction이 커밋될 때 manifest list에 맵 참조를 저장한다. 이것이 SERIALIZABLE 트랜잭션을 위한 플래그 역할도 한다 — compaction이 논리 스냅샷을 바꾸지 않았으므로 compaction이 도입한 read conflict를 무시할 수 있다
    • remapping 전략 선택: run 수 과 position 수 가 다양하므로 런타임에 만나는 것에 따라 policy가 알고리즘을 고른다. 무관한 run을 걸러낸 뒤 range lookup 또는 정렬된 position을 run과 한 패스로 merge. merge는 run이 position보다 압도적으로 많을 때, 그리고 둘 다 크고 맵이 dense할 때 이긴다. range lookup은 sparse한 맵에서, 그리고 수백만 position이어도 run 수가 작을 때 이긴다
    • 다만 전략 선택이 naive/static 대비 자릿수 speedup처럼 들리게 하지만 실무에서 차이는 거의 유의하지 않다 — remapping 레이턴시는 대개 remapping 알고리즘이 아니라 I/O에 지배된다

주요 수치 / 사실

  • remapping 레이턴시: v3(Roaring bitmap) 수십~수백 ms, v2(Parquet) ~2초 — 재실행의 수 분과 비교
  • 측정한 가장 큰 값에서 v3 position delete vector를 읽고 remap하고 쓰는 평균 총 레이턴시 293~463 ms (클라우드 제공자에 따라)
  • 맵 크기: run 10개에 2.6 KiB, run 10,000개에 8.9 KiB
  • delta commit이 쿼리 레이턴시를 최대 2~3배 증가
  • v2 position delete 파일 쓰기가 v3보다 비싸다 (비용 대부분이 Parquet 파일 인코딩·쓰기), 그래도 재실행보다 자릿수 빠르다
  • 구현은 Apache Iceberg 1.10.1 기반, v2·v3 테이블 모두 지원 (cdouglas/iceberg@cmpmap)
  • bulk bitmap 구성 최적화가 latency 감소분 중 12~24 ms만 설명 — I/O 대 remapping의 상대적 중요도를 보여준다
  • 착안 출처는 LSM 트리용 REMIX 인덱스 — SSTable 병합 경로를 기록해 reader마다 같은 비교를 반복하지 않고 iterator를 전환하게 한다. REMIX의 “anchor key”를 compaction map에 더하면 유사한 역할을 할 수 있고, compaction은 옛 checkpoint가 GC될 때까지 스토리지를 회수하지 않으므로 compaction을 수행하는 대신 맵만 만들면 스토리지 비용의 일부로 read 성능 일부를 회복할 수도 있다
  • 확장 방향: deduplication(논리적 noop은 아니지만 중복에 둔감한 트랜잭션에는 문제 모양이 같다 — dedup map), mostly-sorted 테이블 재정렬(최근 데이터만 정렬 안 되어 있으면 맵이 관리 가능한 크기), Apache Hudi의 reclustering(Hudi는 position delete vector를 쓰지 않아 compaction이 레이아웃 conflict를 만들지 않지만, 키를 file group으로 clustering하므로 recluster는 유사하게 충돌한다)
  • z-order·재정렬 compaction은 프로토타입 미지원 — 최악의 경우 맵이 행마다 엔트리를 갖고, compact된 데이터에서 재실행하는 것이 때로 더 싸다 (애초에 그것이 compaction의 동기였다)

관련 위키

Source: 원문 보기

그래프 뷰

백링크