Data Eng Wiki

Puffin-Backed Vector Indexes

13 min read

Puffin-Backed Vector Indexes: Attaching ANN Indexes to Apache Iceberg Snapshots for Compute-Disaggregated Query Engines

Author: Artur Borycki (Teradata Advanced Research) | Source: arXiv:2606.04196 | Published: 2026

한 줄 요약

Iceberg가 통계·deletion vector용으로 만든 Puffin sidecar 파일이 십억 규모 DiskANN 그래프를 담기에 충분하고, snapshot summary로 바인딩하면 ANN 인덱스 관리가 표준 Iceberg 스냅샷 연산으로 환원되어 원자성·시간여행·멀티엔진 판독·orphan GC를 구현 비용 0으로 상속한다.

핵심 주장/내용

  • 긴장 관계에 있는 두 흐름: ① 분석 엔진이 compute-disaggregated 설계로 수렴 — 데이터는 오브젝트 스토리지의 불변 Parquet, 열린 테이블 포맷으로 조직, 데이터 이동 없이 추가·제거 가능한 stateless executor가 쿼리 ② 십억 규모 벡터 인덱스는 그 자체가 수십~수백 GB이고 빌드 비용과 리프레시 시맨틱이 만만치 않다
  • 기존 통합 경로가 깨뜨리는 4가지 속성: 별도 벡터 DB 운영, executor에 사설 인덱스 파일시스템 유지, 쿼리마다 인덱스 재구축 — 각각 최소 하나를 위반한다
    • stateless executor — 언제든 종료·교체 가능해야 함
    • single source of truth — 파생 상태(인덱스, 통계)가 계산 기준이 된 데이터 버전과 일관되어야 함
    • 멀티엔진 상호운용 — 파생 산출물이 이를 깨뜨리면 안 됨
    • 새 생명주기 없음 — 인덱스 생성·리프레시·삭제가 테이블 포맷의 트랜잭션 커밋·시간여행·GC를 재사용해야 함
  • Puffin이 이 넷을 이미 만족한다: 플랫 바이너리 컨테이너로, 각 blob이 불투명한 type 문자열, Iceberg field-ID 집합, 임의 property map, 바이트 페이로드를 갖는다. blob마다 독립 압축(zstd, lz4)되고 byte-range 요청으로 개별 주소 지정 가능(전체 다운로드가 비현실적인 대용량에서 결정적). 스냅샷에는 statistics-file summary property로 바인딩. 스냅샷을 읽는 엔진은 footer를 검사해 자기가 아는 타입의 blob만 선택적으로 읽고 모르는 타입은 에러 없이 무시한다
  • 왜 Vamana/DiskANN인가: ① SSD 상주 운영을 위해 설계됨 — 그래프 인접이 로컬 디스크에서 mmap되고 방문 노드(쿼리당 수백 개)만 RAM에 페이징. PQ와 결합하면 2.5억 벡터 샤드가 RAM ~4GB + SSD ~60GB에 편안히 들어가 현대 분석 executor 노드의 리소스 범위 안 ② 값싼 incremental insert를 지원 — 테이블이 지속적으로 append되는 lakehouse 사용례에 필수
  • 5가지 설계 원칙:
    1. executor 샤드당 blob 하나 — 전역 Vamana 그래프를 만들어 분할하는 대신 각 executor가 할당된 Parquet 파일 부분집합 위에 독립적 로컬 그래프를 만든다. 작은 recall 손실(exact rerank 단계로 부분 회복)을 대가로 빌드 시간이 executor 수에 선형 확장되고 probe 병렬성이 엔진의 기존 top-K fan-out/merge 기계에서 그냥 떨어진다
    2. snapshot에 묶인 인덱스 생명주기 — 인덱스 버전 = 스냅샷 버전. AS OF 시간여행 쿼리가 자동으로 맞는 인덱스 버전을 읽고, 동시 인덱스 빌드는 동시 데이터 쓰기를 중재하는 것과 같은 optimistic concurrency로 중재된다
    3. tiered probe placement — 모든 ANN 인덱스가 executor에 샤딩될 필요는 없다. 1만 파일 테이블의 file-level centroid 인덱스는 768차원에서 약 30MB이고 probe(1만 번 거리 계산)가 단일 스레드에서 1ms 미만이다. 이런 건 coordinator에서 직접 probe해 dispatch 전에 파일 목록을 pruned subset으로 교체하고, 임계(기본 100MB)를 넘는 것만 샤딩
    4. write path 재사용 — ANN 인덱스 빌드는 구조적으로 Parquet 대신 Puffin 파일을 만드는 INSERT-SELECT다. 기존 PlanFragment/TaskRunner 인프라로 dispatch하고, 빌드를 마무리하는 Iceberg 커밋은 summary property 하나만 추가한 같은 CommitToIceberg 호출
    5. manifest diff를 통한 incremental refresh — Iceberg가 이미 필요한 프리미티브를 제공한다. 두 스냅샷 ID를 주면 manifest diff가 추가·제거·불변 데이터 파일을 정확히 반환하므로 영향받은 샤드만 리프레시(추가 벡터는 Vamana 네이티브 incremental insert, 제거는 tombstone bitmap)
  • 분산 빌드 3단계: Stage 0 coordinator가 벡터의 약 1%를 샘플링해 k-means로 centroid codebook 학습(k = executor 수 × executor당 파티션 수) → Stage 1 각 executor가 할당 Parquet을 벡터 컬럼만 projection해 SSD 캐시로 받아 스트리밍 디코딩, 각 벡터를 최근접 centroid에 배정해 샤드 소유권 확인 후 Vamana 빌더에 투입, blob을 S3에 직접 write → Stage 2 coordinator가 샤드 blob 바이트만 받아 routing blob(centroid codebook + 커버된 파일 경로 집합)을 구성하고 Puffin을 조립해 REST 카탈로그로 커밋(데이터 파일이 바뀌지 않으므로 구조적으로 REPLACE 연산)
  • 분산 probe 3단계: Stage A 각 executor가 SSD 캐시에서 샤드 blob을 로드해 mmap 구조로 역직렬화, PQ codebook을 RAM에 올리고 Vamana greedy beam search 실행(후보 스코어링은 PQ 근사 거리, 최종 소량 rerank는 full precision, 쿼리당 5001000 노드 순회) → (file_path, row_group, row_offset, approx_distance) 튜플을 Arrow IPC로 방출 → Stage B coordinator가 min-heap으로 병합해 top K×oversample(보통 24배)을 고르고 파일·row-group 마스크를 dispatch, executor가 타겟 row group만 다운로드해 exact distance 계산 → Stage C streaming loser-tree merge
    • 이 (거친 probe → exact rerank → ordered merge) 패턴은 엔진이 일반 컬럼의 ORDER BY ... LIMIT을 bloom filter/zone-map pruning으로 처리하는 방식과 구조적으로 동일하다 — ANN 인덱스가 같은 기계에 슬롯인되고 새로 필요한 건 executor 측 Vamana probe 코드뿐
  • lazy tombstoning: Vamana 그래프에서 벡터를 완전히 제거하려면 그것을 이웃으로 가진 모든 노드를 패치하고 생긴 구멍을 다시 연결해야 해서 비싸다. 대신 샤드가 tombstone bitmap을 유지 — 삭제된 벡터는 연결성을 위해 그래프에 남아 탐색이 계속 작동하되 coordinator에 반환되기 전 후보 집합에서 필터된다. tombstone 비율이 20%를 넘는 샤드는 다음 유지보수 윈도우에 (전체 인덱스가 아니라) 그 샤드만 전체 재빌드 스케줄

주요 수치 / 사실

  • 구현: FlockDB(DuckDB를 노드별 실행 커널로 쓰는 분산 MPP 엔진) + Iceberg REST 카탈로그 + AIStor. 약 8,000줄의 신규 코드, 대부분이 그래프 빌더 자체. PuffinWriter는 약 200줄, 테이블 포맷 통합은 수백 줄
  • 10억 벡터, 768차원 기준 인덱스 크기: file-level centroid(1만 파일) ~30MB → coordinator, IVF-PQ(nlist=4096) ~16GB → 경계, HNSW(M=16) ~60GB → executor RAM, DiskANN/Vamana(R=64) ~250GB → executor SSD
  • 투영 쿼리 성능 (10억 벡터, top-100, executor 4대, oversampling 4배):
인덱스 없음Centroid (coord.)DiskANN (분산)
스캔 파일 수10,000~400~50
S3 읽기300 GB12 GB1.5 GB
cold-cache 레이턴시60–90s5–10s1–3s
warm-cache 레이턴시15–25s2–4s50–200ms
Recall@1001.000.85–0.950.95–0.99
  • 빌드: 10억 벡터를 executor 4대로 45~60분 (가장 느린 executor의 샤드 빌드가 지배). incremental insert는 768차원 AVX2에서 벡터당 약 200μs — 100만 벡터 배치를 4 executor로 나누면 각 25만 insert에 약 50초 컴퓨트이고 실제로는 그래프 변형이 아니라 새 Parquet의 S3 읽기 시간이 지배
  • 인덱스 저장 비용: 샤드 blob이 각 ~60GB(rerank용 full vector 제외) 또는 ~250GB(포함). 전체 Puffin이 240GB(lean)~1TB. 기저 벡터 데이터 300GB 대비 비슷하거나 다소 큼 — 그래프 기반 ANN의 표준적 트레이드오프
  • 한계 (저자가 정직하게 나열):
    • 업데이트 granularity가 스냅샷 — 벡터는 Iceberg 커밋과 독립적으로 검색 가능해질 수 없다. 스트리밍 인제스션의 엄격한 신선도 요구에서는 커밋 주기가 인덱스 신선도의 상한이 되고, 분당 수천 커밋은 결국 REST 카탈로그를 포화시킨다
    • recall이 샤드 간 데이터 분포에 의존 — 독립 샤드 설계는 centroid 기반 파티셔닝일 때 통계적으로 샤드당 클러스터 하나인 IVF와 동등. 쿼리 분포가 데이터 파티셔닝과 상관이 낮은 워크로드는 recall이 낮아지고, 아직 체계적으로 측정하지 않았다
    • probe 레이턴시 하한이 stage barrier로 정해진다 — 3단계 probe가 barrier 2개, 각 약 5~10ms. sub-10ms P50을 노리는 애플리케이션에는 과하고 단일 단계 로컬 인덱스가 더 적합
    • cold cache 성능은 S3 처리량이 상한. recall의 형식적 하한 보장 없음 — Vamana 자체의 경험적 recall은 문헌에 있지만 독립 샤드 조합은 분석되지 않았다
    • 동시 빌드/리프레시 충돌은 Iceberg optimistic concurrency에 의존 — 하나가 성공하고 다른 하나는 재시도. 현재 동시 리프레시를 coalesce하거나 큐잉하지 않아 백그라운드 리프레시와 사용자 리프레시가 겹치면 낭비된 작업이 생긴다
  • 패턴은 ANN 전용이 아니다 — 테이블 데이터에서 파생되고 스냅샷과 함께 버전되며 일부 엔진만 읽으면 되는 것은 무엇이든 Puffin 후보다: 학습된 인덱스·cardinality 모델(옵티마이저가 소비), materialized derived column(계산된 집계, 파생 임베딩, 비정규화 조인 컬럼을 가상 컬럼으로), 엔진 간 가속 공유. 저자는 ann-routing-v1, ann-vamana-graph-v1, ann-centroid-index-v1 세 blob 타입을 커뮤니티 표준 후보로 제안. Delta Lake의 deletion vector·statistics file, Hudi의 metadata table에도 깔끔히 전이된다
  • 더 넓은 관찰: 열린 테이블 포맷이 파생 데이터 생명주기를 공짜로 제공한다. Puffin이 테이블 통계용을 넘어 스냅샷 시맨틱에 묶인 범용 append-only key-value 스토어로 쓰이기 시작할 것으로 예상

관련 위키

Source: 원문 보기

그래프 뷰

백링크