Data Eng Wiki

wal3 - A Write-Ahead Log for Chroma Built on Object Storage

18 min read

wal3: A Write-Ahead Log for Chroma, Built on Object Storage

Author: Chroma Engineering | Source: trychroma.com/engineering | Published: 2026

한 줄 요약

S3의 conditional write가 30년 된 lock-free 큐 알고리즘을 오브젝트 스토리지에서 가능하게 했고, 여기에 order-agnostic 체크섬(setsum)을 더해 시스템을 두 번 — 기능을 위해 한 번, 검증을 위해 한 번 — 만든 것이 “만들지 말라”는 통념을 거스르고 자신 있게 출시하게 해줬다.

핵심 주장/내용

  • 철학 — 두 개의 현실: 소프트웨어 엔지니어는 코드를 쓰는 게 아니라 평행 현실을 구성한다. 하나는 시스템이 작동하는 현실(바이트가 디스크에서 사용자로 밀리초 안에 흐른다), 다른 하나는 그 시스템에 대한 우리의 픽션(볼 수 있는 것과 외부 효과). 픽션은 초·분 단위의 인간 스케일로 제시된다. wal3는 두 현실에 동시에 존재하도록 만들었다 — 데이터를 오브젝트 스토리지에 durable하게 저장할 뿐 아니라 그것을 올바르게 하고 있다는 지속적 증명을 유지한다
  • 오브젝트 스토리지에 대한 근본 베팅: durability(Amazon이 정량화한 99.999999999%. 하지만 훨씬 더 가능성 높은 것은 운영자 실수이고, 오브젝트 스토리지에 베팅하고 delete 경로를 신중히 감사함으로써 durability에 부정적 영향을 주는 운영자 실수 가능성을 줄인다), 운영 단순성(관리할 디스크가 없다. Chroma의 모든 파괴적 연산이 여전히 사용 중인 데이터를 실수로 지우지 않도록 가드된다), 컬렉션 확장성(disjoint 경로에 로그를 다중화해 컬렉션 수에서 확장. scalable commutativity rule에 따라 두 컬렉션이 데이터를 공유하지 않으면 확장 가능한 구현이 존재하고, 오브젝트 스토리지에서는 컬렉션이 다른 prefix를 가질 때 자연히 그 구현으로 번역된다)
  • 요구사항과 기존 해법이 부족한 이유:
    • 핵심 요구 — durability(로그에서 읽을 수 있게 되기 전에는 쓰기가 ack되지 않아야 하고, ack된 쓰기는 garbage collection으로 지워질 때까지 읽을 수 있어야 한다. 메모리 GC처럼 로그 GC도 도달 불가능한 데이터만 제거해야 한다), 가용성(로그가 오프라인이면 그 로그가 뒷받침하는 컬렉션이 오프라인), 컬렉션 수에서의 확장성(중앙 집중 로그는 새 고객을 받는 능력을 본질적으로 제한하므로 불충분. 컬렉션이 원자성과 스케일링의 단위이므로 그 속성을 로그에 매핑해야 하고, 이상적으로는 각 컬렉션이 read/write 처리량 스케일링 단위로 기능하는 전용 로그를 갖는 것), 오픈소스
    • 추가 고려 — 운영 단순성(stateless 프로세스를 오브젝트 스토리지에 겨누기만. Kubernetes persistent state와 그에 따르는 두통 관리 불필요), Rust로 작성(모든 것이 같은 언어에 있으면 다른 언어의 중복 구현 마찰이 사라져 개발 속도가 난다), 유지보수를 위해 구축(코드를 채택하면 소유하게 된다. 확장하고 다룰 수 있어야 빠르게 움직이면서 깨뜨리지 않는다. 인프라를 소유하지 않으면 소유한 시스템과 그 위에 만드는 시스템 사이의 impedance mismatch를 우회하느라 타협하게 된다), 안전성 보장(시스템이 안전 속성을 유지하고 있다는 능동적이고 지속적인 증명을 원한다. wal3에서는 로그의 durable 상태에 대한 체크섬 형태)
    • Kafka — 로컬 디스크로 durability를 제공하고 그로 인한 실패 모드를 극복하려 복제로 가용성을 보장한다. 어느 정도 durability를 주지만 운영자가 디스크 fleet을 돌봐야 하고, 그것이 오브젝트 스토리지에서 오는 운영 단순성 이득을 크게 훼손한다. Kafka에서 확장 단위는 topic인데 topic은 대체로 클러스터에 묶여 있고, 실무에서 Kafka로 만드는 대부분의 사람이 위에 자명하지 않은 shim 레이어(topic 간 마이그레이션, topic 관리, 일반 확장성 관심사)를 둔다
    • WarpStream — 오브젝트 스토리지 위의 disk-less Kafka 호환 구현으로 wal3와 가장 직접 비교 가능하다. 훌륭한 엔지니어링이지만 오픈소스가 아니라 그 이유만으로 고려할 수 없었다. WarpStream 팀은 Kafka를 충실히 재현했고, wal3는 비교하면 Kafka 기능 대부분을 지원하지 않는다 — prefix 아래 로그에서 read·append·trim만. 이 단순함이 구현 면에서 유리하게 작용하지만, 이 글로 wal3를 WarpStream과 비교 평가한다면 그 제약이 유스케이스에 영향을 주는지 신중히 평가해야 한다
    • CDC — SQL DB 위의 CDC로 데이터를 쓰고 순서대로 적용하는 프로세스로 쓰기 이력을 roll up할 수 있지만, 확장하려면 컬렉션당 독립 스트림이 필요하고 Chroma가 기반하는 프리미티브 중 어느 것에도 CDC 시스템이 없어서 처음부터 만들어야 한다
    • 셋 다 확장성 요구를 지원하지 않는다. 각 컬렉션이 자기 독립 갱신 스트림을 요구하는데 이 시스템들은 per-collection 확장성을 제공하는 대신 여러 인스턴스에 컬렉션을 수동으로 샤딩하게 만들 것이다. 그러려면 라우팅 레이어, failover 메커니즘, 마이그레이션 전략이 필요하다
  • S3의 새 기능이 30년 된 알고리즘을 연다: Amazon이 eventual → strong consistency 이후 가장 실질적인 변화를 만들었다 — conditional writes(2024년 11월). writer가 “이 파일을 덮어쓰지 마라” 또는 “이 파일이 특정 이전 digest와 정확히 일치할 때만 덮어써라” 라고 명시할 수 있게 한다. 애플리케이션이 추가 메커니즘 없이 오브젝트 스토리지에서 직접 조율할 수 있게 되고, 파일을 읽고 동시 쓰기가 없을 때만 쓰는 read-modify-write가 가능해진다. 다르게 말하면 이 기능이 오브젝트 스토리지 위에 원자적 lock-free 자료구조를 만드는 것을 가능하게 한다
    • 억지가 아니다: 메모리에 적용되는 같은 알고리즘이 오브젝트 스토리지에 적용될 수 있다. Jeff Bezos가 S3를 명세할 때 인터넷을 위한 malloc을 원했다. S3가 인터넷의 malloc이라면 conditional write는 포인터가 풍부한 구조를 구성하고 변형하는 데 쓸 수 있다. S3 키는 불투명한 가변 크기 메모리 영역을 가리키는 불투명한 가변 크기 포인터다. “if-none-match”가 메모리 영역의 원자적 할당·초기화를, “if-match”가 정확히 일치할 때만 덮어쓰는 일종의 compare-and-swap을 가능하게 한다
    • lock-free 큐: 표준 단일 연결 리스트를 유지한다. 갱신 알고리즘은 단순하다 — header의 포인터를 로드해 새 노드의 next에 저장하고, head의 포인터를 로드한 기존 값에서 새 노드 주소로 compare-and-swap해 원자적으로 링크한다. 락이 있는 것처럼 동시 prepend를 지원하되 락이 없다
    • 오브젝트 스토리지 세계에는 파일밖에 없으므로 연결 리스트 노드에 파일 하나(fragment), header에 파일 하나(manifest)를 쓴다. 메모리에서 노드를 할당할 자리에 존재하지 않을 때만 파일을 넣고(if-none-match), manifest 전체 내용에 대한 if-match로 새 노드를 참조하도록 원자적으로 갱신한다. 새 맥락의 같은 알고리즘
  • setsum — 전통 체크섬을 넘어서: 목표는 fn checksum(Log) -> Digest를 만들고 매 갱신 후 digest를 유지하는 것인데, 로그 인터페이스가 append와 trim만 노출하되 그것들이 빨라야 한다. 핵심 요구 — 로그의 모든 내용에 대한 암호학적 digest 제공, 내용 추가 시 전체 로그 digest를 O(1)에 재계산, GC 시 전체 로그 digest를 O(1)에 재계산
    • append·trim에서 O(1)로 갱신되는 체크섬을 만들기 위해 로그의 단조성을 활용한다 — 쓰기는 항상 끝으로 가고 garbage는 항상 처음에서 수집된다. GC된 prefix의 digest + 라이브 데이터의 digest가 전체 데이터의 digest와 일치해야 한다
    • setsum = 결합적·교환적 체크섬으로 문자열에 대한 표준 multi-set 연산을 상수 시간에 제공한다. 체크섬이 fn checksum(String) -> Digest라면 setsum은 fn setsum([String]) -> Digest이고 digest 자체에 대한 multi-set 연산 도구를 동반한다. digest가 입력의 집합 성질을 보존한다 — union(digest({A}), digest({B}))가 출력에서 digest({A, B})와 동등하되 계산 복잡도는 크게 다르다. 집합 addition·union·removal·difference를 digest에 대해 상수 시간에, 단일 원소 digest 생성을 원소 크기에 비례해 지원
    • 표준화된 setsum 구현이 있으면 누구든 로그 데이터의 digest와 GC된 데이터의 digest를 제공할 수 있고, 누가 계산하든 그 합이 전체 데이터의 digest와 같아야 한다. 서로 다른 바이너리 — 다른 구현이나 그냥 다른 릴리스 — 에서 프로세스를 여러 번 돌려 최소한 서로 동의하는지 확인할 수 있다. 구현이 독립적이면 신뢰성 이득을 얻는데, 서로 다른 구현이 같은 버그를 보일 가능성이 극도로 낮기 때문
  • GC가 데이터를 잃기 가장 위험한 곳: 불변·append-only 스토리지 기반 시스템에서 정의상 데이터를 지우는 곳이 하나뿐이면 그곳이 데이터를 잃을 곳이다. 모든 의도적 데이터 손실을 한 곳에 집중시키면 거기가 데이터 손실 버그가 사는 곳이다
    • 실제로 버그를 잡았다 — CI에서 반복적으로, 그다음 staging에서 덜 반복적으로. 가장 illustrative한 버그는 무해했지만 교육적이었다: idempotent garbage collection이 실패하곤 했다. A, B, C에서 A, B 시퀀스를 GC하는 것은 A, B가 이전에 GC되었더라도 허용되어야 한다. setsum 구성이 이것을 코드 버그로 플래그했는데 idempotent 제거를 깔끔히 탐지하지 않고 있었기 때문이다. GC가 제거한 데이터와 manifest에 남은 데이터를 더해도 전체 데이터의 예상 합이 되지 않았다
    • 핵심은 이것이다: setsum은 데이터에 대해 아무 말도 하지 않고 데이터는 setsum에 대해 아무 말도 하지 않지만, 함께 있으면 확신을 확립한다. 항상 일치하는 setsum을 유지하는 것이 가장 위험한 GC 컴포넌트를 포함해 wal3를 출시하게 해준 운영적 확신을 개발 과정에 주었다

주요 수치 / 사실

  • 프로토타입에서 Chroma 프로덕션 트래픽 서빙까지 4개월
  • setsum 적용에는 엔지니어링 규율이 필요하다 — 서로 얽힌 같은 코드의 두 병렬 구현을 개발해야 하고 하나의 변경이 다른 하나에 반영되어야 한다. 하나는 실제 로그 데이터를, 다른 하나는 setsum digest를 조작하며 나란히 돌아 정확성을 검증한다
  • 사실상 세 시스템을 만들었다 — 데이터 로그를 유지하는 것, 그 데이터의 digest를 유지하는 것, 그리고 그 두 반쪽이 어떻게 공존하는지 보여주는 관측성. 세 구현이 얽혀서 한 시스템의 움직임이 다른 시스템의 움직임과 일치한다. 시스템의 두 픽션이 시스템 자체에 embed할 만큼 저렴해서 시스템이 steady state에서 자기 검증적이 된다
  • 철학: 시스템은 실제 현실과 우리의 픽션적 이해 두 형태로 존재한다. 프로그래머에게 시스템의 현실은 픽션이다 — 볼 수 없고 SRE 관측성·모니터링 메커니즘으로만 관측할 수 있다. 시스템에게는 그 관측성이 픽션이다. 도구 문제든 측정 오차든, 지표·로그·trace로 제시된 픽션은 시스템을 닮았지만 결정적으로 시스템 자체가 아니다
    • 최고의 시스템은 두 번 만들어져야 함을 인식하고 — 기능을 위해 한 번, 검증을 위해 한 번 — 그것을 설계 안에 인코딩한다. 최고의 엔지니어는 눈에 씌워진 wool을 인식하고 자기가 만든 픽션에 눈멀지 않는다
  • 데이터베이스를 만들 때 그것이 정확하다고 믿는 것으로는 충분하지 않다. 뒤집히고 미끄러지고 발밑에서 악화되려는 비트들에 맞서 끊임없이 땅을 얻으려 싸우지 않는다면, 데이터베이스가 아니라 데이터베이스의 근사를 만들고 있는 것이다

관련 위키

Source: 원문 보기

그래프 뷰

백링크