Data Eng Wiki

Indexing the Data Lake for Online Point Queries

16 min read

Indexing the Data Lake for Online Point Queries

Author: Will Edwards (Spotify) | Source: engineering.atspotify.com | Published: 2026-07

한 줄 요약

병목은 이제 스토리지가 아니라 그 위의 쿼리 엔진이다 — 외부 인덱스가 키를 파일 위치에 직접 매핑하고 정밀한 ranged read로 필요한 바이트만 가져오면, 같은 Parquet 파일이 배치 분석과 대화형 point query를 동시에 서빙한다.

핵심 주장/내용

  • 문제 설정: 온라인 서비스(청취 이력을 쓰거나 보여주는 포털·개인화)는 사용자별 데이터를 대화형 속도로 조회·페이지네이션해야 하고, “작년 여름에 뭘 들었지?”에 답하는 AI 에이전트는 사용자 데이터를 빠르게 가져와 필터·집계하거나 로컬에서 SQL을 돌려 LLM 프롬프트용 컨텍스트를 만들어야 한다. 두 패턴이 같은 기저 프리미티브를 공유한다 — Bigtable·DynamoDB 같은 KV 스토어에 경제적으로 상주시키기엔 너무 큰 데이터셋에 대한 키 기반 빠른 point query
  • 병목이 이동했다: Spotify는 온라인 유스케이스용으로 페타바이트를 Bigtable에 두지만 엑사바이트가 GCS 데이터 레이크에 있다. 레이크 기저 스토리지는 빠르고 더 빨라지고 있다 — GCS가 요청당 30~100ms, S3 Express One Zone과 GCS Rapid Storage는 이제 한 자리수 밀리초. 병목은 점점 스토리지 레이어 자체가 아니라 그 위의 쿼리 엔진이다. Trino·BigQuery 같은 분산 SQL 엔진은 단일 row 조회에도 초 단위의 잡 스케줄링·쿼리 플래닝 오버헤드를 더한다. 분석 처리량용으로 설계되었지 대화형 point query용이 아니다
  • 표준 기법으로 후보를 줄이는 한계: 일별 파티션 안에서 키로 추가 파티셔닝하면 파일 이름만으로 특정 user ID가 그 파일에 있을 수 있는지 알 수 있다 — 일 1,000 버킷이면 후보가 90,000 → 90개로 준다. Bloom filter로 파일을 열지 않고 버리면 90개가 실제 활동한 12일치로 좁혀진다
    • 하지만 그 12개 파일은 여전히 읽어야 한다. 각 파일은 크고 한 사용자의 데이터를 찾으려면 의존적 read 체인이 필요하다 — footer 가져오기 → row group 메타데이터 파싱 → 키 컬럼 스캔으로 매칭 row 위치 찾기 → column·page index로 각 값 컬럼의 해당 페이지 찾기. 파일당·컬럼당 클라우드 스토리지로의 다중 왕복 의존 fetch이고 모든 왕복이 다른 동시 쿼리와 IOPS를 다툰다. 키 파티셔닝과 Bloom filter는 파일 선택을 돕지만 파일 안의 문제를 풀지 못한다
  • 의존적 read 체인이 근본 병목이고 모든 스토리지 티어에 적용된다: 각 링크가 레이턴시(다음이 시작하기 전 한 번의 왕복)와 대역폭(어디를 읽을지 알아내려고 읽는 바이트)을 소비한다. 클라우드 스토리지에서 링크당 수십 ms, 로컬 SSD에서 마이크로초, 메모리에서 나노초 — 절대값은 달라도 구조는 같다. 체인을 무너뜨려 의존적 read를 단일 사전계산 조회로 대체하면 어느 티어에서든 레이턴시와 대역폭을 모두 절약한다
  • RAP (Random Access Parquet): 스캔 대신 조회한다. 외부 인덱스가 각 키를 데이터가 있는 파일과 row 번호에 직접 매핑한다. 키가 주어지면 인덱스를 조회하고, 캐시된 파일 메타데이터로 row 번호를 페이지 위치로 해소하고, 필요한 페이지만 정확히 가져오는 ranged read를 발행한다. 인덱스 조회는 O(1)이고, 캐시된 페이지 매핑은 저지연 연산이며, 데이터 검색은 소수의 정밀한 ranged read다. 결정적으로 이 read들은 병렬 발행 가능하다 — 의존적 로드 체인이 없다
  • 외부 인덱스의 성질: 어떤 기존 Parquet 파일에서도 특별한 준비 없이 동작한다. 인덱스 빌더가 검색될 컬럼의 footer와 페이지 위치를 읽고, 키 컬럼을 스캔해 key→location 매핑을 만들고, 써낸다. 새 데이터가 오면 각 파이프라인 실행이 대응하는 인덱스 항목을 생성하고 인덱스는 기존 fragment를 수정하지 않고 append로 성장한다
    • multimap 구조 — 키 하나가 여러 파일·파티션에 항목을 가질 수 있다. 각 항목은 compact: key, file(dictionary 인코딩된 ordinal), row numbers, (선택) value count(페이지네이션 가능)
    • 대략 테라바이트를 인덱싱하면 기가바이트, 페타바이트면 테라바이트의 인덱스. 큰 인덱스는 hash bucketing으로 자연히 분산된다
    • Parquet 내장 PageIndex나 Bloom filter와 근본적으로 다르다 — 그것들은 확률적이고 스캔을 좁힐 뿐이지만 외부 인덱스는 결정적(definitive) 이다. 키가 주어지면 정확한 파일과 row를 반환해 스캔 자체를 제거한다
  • 외부 인덱스가 트레이드오프의 균형을 바꾼다: 리더가 파일을 만지기 전에 정확한 파일·row·컬럼을 안다. 따라서 파일 내 발견을 돕는 성질(세밀한 page index, 술어 skipping용 작은 페이지, pushdown용 dictionary 인코딩)은 덜 중요해지고, 최종 read를 최소화하는 성질(적은 왕복, 작은 fetch, 연속된 데이터)이 더 중요해진다
  • 최적화 3범주:
    • 키 데이터 집중 — 키로 정렬(같은 키의 모든 row가 파일 내 연속, 가능한 적은 페이지로 집중. 많은 파이프라인이 이미 정렬 출력을 만든다), co-grouping(각 키가 반복/중첩 컬럼에 값을 담아 한 번 나타나도록 스키마 구조화 — 정렬 순서에 의존하지 않고 파일·파티션당 키 하나의 row), 더 거친 파티셔닝(일별은 연 365 파일/키, 주별은 52 — 인덱스 항목·병렬 read·인덱스 크기가 모두 줄지만 배치 쿼리의 파티션 프루닝 세밀도와 트레이드오프)
    • 읽는 바이트 감소 — one page per key(writer가 키 경계에서 페이지를 flush해 압축 해제된 페이지 전체가 타겟 키에 속하므로 row 추출 불필요. 페이지 위치를 인덱스 항목에 직접 저장할 수 있어 별도 page index도 불필요하고 파일은 표준 Parquet으로 남는다. 키 경계마다 약 20바이트 헤더 오버헤드), ZSTD frame reset(one-page-per-key가 PageIndex를 부풀릴 때의 대안 — 관례적 페이지 크기를 유지하되 각 키의 row를 페이지 안의 별도 ZSTD frame으로 압축. 인덱스가 컬럼별 frame의 바이트 오프셋과 크기를 저장해 별도 page index 없이 데이터를 직접 주소 지정. 표준 리더에게는 페이지가 정상적으로 압축 해제되고(ZSTD frame은 단순 연결) RAP에게는 각 frame이 독립 주소 지정 가능. 대가는 frame 안의 값이 앞 frame 없이 해석 가능해야 해서 delta·run-length 인코딩이 배제되는 것), storage alignment(ZSTD skippable frame으로 키 사이를 패딩해 fetch를 스토리지 블록 경계에 정렬 — 경계를 걸치는 fetch는 두 블록을 읽어야 한다)
    • read 연산 수 감소 — 가장 큰 단일 승리: 표준 Parquet에서 N개 컬럼의 값을 가져오려면 N개의 병렬 read가 필요해 요청 용량을 N배 소비하고 키당 레이턴시를 분포의 꼬리로 밀어낸다
      • Blob·Variant — 랜덤 접근에 필요한 필드를 단일 컬럼(JSON, Protobuf, Parquet Variant)으로 저장하면 파일당 read 하나. 온라인 애플리케이션이 데이터를 개별 필드가 아니라 문서로 소비하는 방식과 자연스럽게 맞는다. 대가는 배치 분석이 blob 내부의 필드별 프루닝과 술어 pushdown을 잃는 것
      • 컬럼 interleaving — 여러 컬럼이 필요할 때 writer가 물리적으로 교차 배치(키1의 컬럼A, 키1의 컬럼B, 키2의 컬럼A…). ZSTD skippable frame이 컬럼 사이를 이어주어 각 컬럼이 유효한 압축 스트림으로 남고, 관례적 리더는 컬럼 A를 순차적으로 읽으며 압축 해제기가 skip frame 안의 컬럼 B 데이터를 조용히 건너뛴다. RAP 리더는 키의 모든 컬럼에 걸친 단일 연속 ranged read를 발행한다. 사실상 후방 호환성을 깨지 않고 선택된 컬럼 그룹의 레이아웃을 row-major로 pivot하는 것. 대가는 관례적 리더가 단일 interleave 컬럼을 읽을 때 다른 컬럼 데이터도 dead space로 읽어 단일 컬럼 스캔의 I/O 볼륨이 배가되는 것
      • covering index와 hoisted value — 인덱스 빌더가 빌드 시점에 모든 row를 방문하므로 작은 값은 인덱스 항목에 직접 hoist할 수 있다. 스토리지 read를 완전히 제거하는 covering index로 read 수를 0으로 만든다. 사전 계산 집계(키별 이벤트 수, 총 재생 시간, 카테고리 분해)로 확장되어 인덱스 조회 속도로 이용 가능하고, 인덱스 레벨에서의 술어 pushdown(스토리지 read 전에 항목을 필터링)도 가능해진다
  • secondary index: 데이터셋이 여러 조회 차원을 가질 수 있다(buyer_id와 seller_id 둘 다로 질의되는 거래 데이터셋). 같은 인덱스 항목 위에 차원마다 하나씩 여러 접근 구조를 만든다 — 해시 테이블은 O(1) 정확 조회, 정렬 인덱스는 범위 쿼리. secondary index 추가·제거는 서빙 레이어 결정이라 파이프라인 변경도 데이터 재작성도 없다. 파일 레이아웃은 정렬된 차원을 선호하고 secondary 조회는 더 많은 파일에 흩어질 수 있지만 리더가 인접 바이트 범위를 자동으로 coalesce한다. Z-ordering·Hilbert curve 같은 space-filling curve는 보완적 — 파일 레이아웃 레벨에서 secondary 차원의 지역성을 개선하고 secondary index는 접근 경로를 제공

주요 수치 / 사실

  • 청취 이력만으로 수십억 사용자가 수천 개의 큰 일별 파일에 걸쳐 있고 여름은 약 90일. 일 1,000 파일이면 90,000개 개별 Parquet 파일 — 온라인 유스케이스의 합리적 시간·컴퓨트 예산 안에 각각을 조금씩이라도 읽는 것조차 금지적
  • 이 최적화들을 합치면 point query를 몇 킬로바이트의 단일 ranged read로 줄이거나 스토리지 read를 아예 제거할 수 있다
  • 핵심 성질은 RAP가 이미 레이크에 있는 같은 Parquet 파일에서 동작한다는 것. BigQuery가 주간 집계 리포트를 위해 스캔하는 파일이 AI 에이전트가 컨텍스트 검색을 위해 읽는 바로 그 파일이다. 복사도, ETL도, 두 번째 스토리지 청구서도 없다
  • 어떤 데이터를 온라인으로 서빙할 수 있는지의 경제학이 바뀐다: 오늘날 팀은 GB당 비용이 우선순위를 강제하기 때문에 KV 스토어에 무엇을 둘지 어려운 선택을 한다. RAP에서는 point query 비용이 클라우드 스토리지 read 비용으로 떨어진다. 히스토리 데이터, 롱테일 엔티티, 저트래픽 피처가 모두 대화형 접근에 실현 가능해진다. AI 에이전트가 컨텍스트를 KV 스토어가 담은 것으로 제한할 필요 없이 레이크 전체 폭에 걸쳐 몇 달, 몇 년을 되짚을 수 있다
  • 데이터 레이크는 더 이상 배치 전용이 아니다. 같은 스토리지가 분석과 대화형 워크로드를 모두 서빙한다 — 하나의 데이터셋, 두 개의 접근 패턴

관련 위키

Source: 원문 보기

그래프 뷰

백링크