TL;DR

  • Firestore Watch의 QueryMatcher는 문서 변경을 전체 처리하는 대신 활성 쿼리의 인덱스 범위와 대조해, 대규모 실시간 쿼리의 일치 항목을 효율적으로 찾는 엔진임.
  • 초기에는 Google Search용 쿼리 일치 라이브러리를 재사용했지만, 프로토콜 버퍼 변환에 따른 CPU 부담과 후처리 오버헤드가 병목이 됨.
  • 새 엔진은 AVL 트리 기반 구간 트리(interval tree)와 필드 트라이(trie)를 결합해 실제 쿼리와 관련된 인덱스 항목만 계산함.
  • IN 및 OR 쿼리는 쿼리를 이접 정규형(DNF)으로 변환하고, 각 절을 해당 인덱스의 구간 트리에 등록해 처리함.
  • 섀도 모드(shadow mode)로 기존 엔진과 결과를 대조한 뒤 배포했으며, 기억에 따르면 읽기 측 지연 시간과 처리량이 각각 10배 넘게 개선됨.

배경

  • VLDB 2026에 「The Live Database: Firestore’s Scalable and Consistent Realtime Queries」 논문이 발표됐으며, Firestore 팀은 내부적으로 Firestore Watch 시스템이라 부르는 내용을 소개함.
  • Google 재직 중 참여한 시스템 가운데 가장 흥미로운 작업 중 하나였으며, 가장 크게 기여한 부분은 4.3절에 설명된 쿼리 일치 엔진 QueryMatcher임. Jonny Dimond와 함께 작업함.

초기 아키텍처

  • Firestore 출시 당시에는 자체 쿼리 일치 엔진 대신, 비슷한 목적을 가진 기존 Google 쿼리 일치 라이브러리를 재사용함. 해당 라이브러리는 Google Search의 전문 검색 쿼리 일치용으로 만들어진 것임.
  • 라이브러리 자체는 맡은 작업에는 훌륭했지만 Firestore에 꼭 맞는 선택은 아니었음.
  • 초기 구현은 Firestore에서 들어오는 문서 변경을 검색 라이브러리의 문서 형식으로 변환했음. 라이브러리 인터페이스에 맞추려고 Firestore 프로토(proto)를 검색 라이브러리의 프로토로 변환해 재사용함.
  • 출시 시점에는 쿼리 일치 기능을 빠르게 구축할 수 있다는 큰 이점이 있었지만, 실제 운영에서 몇 가지 심각한 문제가 발생함.
  • 확장성 병목이 됨. 프로토 변환이 CPU 시간의 큰 부분을 차지했으며, 문서가 크고 깊게 중첩돼도 활성 쿼리가 숫자 필드 하나만 살펴보는 경우 전체 문서를 처리해야 했음.
  • 후처리 오버헤드가 발생함. Firestore의 인덱스 및 쿼리 의미를 정확히 반영하려면 상당한 후처리가 필요했음. 검색 라이브러리는 훌륭했지만 Firestore용으로 설계되지는 않았음.

핵심 발상

  • 출시 당시 Firestore의 핵심 전제는 쿼리 비용이 결과 집합의 크기에 따라 확장된다는 점이었음. 모든 쿼리는 인덱스를 기반으로 하며, Watch가 지원하는 쿼리는 각각 하나의 인덱스 스캔에 명확히 대응하고 이접 쿼리는 여러 스캔에 대응함.
  • 기존 쿼리 엔진은 인덱스 범위를 스캔해 일치하는 항목을 찾음. 이를 뒤집어 클라이언트가 등록한 여러 인덱스 범위를 두고 문서 변경이 들어올 때 해당 변경과 일치하는 범위를 효율적으로 찾는 방식이 제안됨.
  • 이 작업에는 구간 트리(interval tree)가 적합함. 구간의 하한을 기준으로 트리를 정렬하고 각 노드에 해당 하위 트리의 최댓값을 저장함. 이 최댓값을 이용해 입력값이 범위 밖에 있는 하위 트리를 즉시 건너뛰므로, 로그 시간 안에 일치 항목을 찾고 탐색 공간을 효율적으로 줄일 수 있음.

구현

  • 성능 개선을 검증하기 위해 초기 버전을 구현함. C++ 템플릿으로 AVL 트리 기반 구간 트리를 작성했으며, 교과서에 나오는 자료 구조를 처음부터 직접 구현하는 방식을 택함.
  • 구간의 경계를 Firestore 값 공간, 인덱스 유형 및 의미 체계를 사용하는 인덱스 값 튜플로 구성된 인덱스 항목으로 변환함.
  • 인덱스 정의에 기반한 비교기를 제공해 오름차순·내림차순 등의 정렬 방향을 처리하고, 실제 인덱스 항목 및 Firestore 쿼리 실행기가 수행할 스캔과 일치시킴.
  • 이 구조를 적용하면 문서 변경마다 전체 프로토콜 버퍼를 처리하지 않고 필요한 인덱스 항목만 효율적으로 가져올 수 있음. 실제로 쿼리가 수신 대기 중인 부분만 다룸.

핵심 일치 알고리즘

  • 활성 쿼리의 인덱스 정의에 포함된 필드를 추적하고 들어오는 변경을 일치시키기 위해 필드 트라이(trie)를 구축함. Firestore의 의미 체계에서는 감시 가능한 모든 쿼리에 대해 쿼리 자체만으로 완벽한 인덱스를 결정적으로 계산할 수 있음.
  • 새 문서와 이전 문서 모두에 대해 문서의 필드 맵과 트라이의 키 사이의 교집합을 구해 일치 여부를 처리함. 두 트리를 함께 순회하고 일치하는 지점에서 하위 노드로 내려가는 방식임.
  • 트라이에서 일치 항목을 찾을 때마다 해당 필드 경로의 구간 트리를 검색해 문서 변경의 영향을 받는 쿼리가 있는지 확인함.
  • 문서 변경을 엔진에 전달하면 활성 쿼리가 있는 인덱스 항목만 지연 계산한 뒤 구간 트리에 넣어 영향을 받는 쿼리를 빠르게 찾음.
  • 이후 처리 파이프라인에서 알림을 내보내고, 쿼리 결과 집합에서 해당 문서가 생성·수정·삭제 중 무엇인지 계산함.

이접 쿼리 처리

  • 논문에는 포함되지 않은 세부 사항으로, IN 및 OR 쿼리도 작은 확장을 통해 자연스럽게 지원함.
  • IN 및 OR 쿼리를 이접 정규형(Disjunctive Normal Form, DNF)으로 변환해 각각의 이접 절로 나눔. 각 분기는 하나의 인덱스 스캔에 대응함.
  • 실제로는 드모르간 법칙(De Morgan’s Law)을 적용해 모든 OR 절을 WHERE 식의 최상위로 올리는 방식임.
  • 각 이접 절을 해당 인덱스 정의에 맞는 구간 트리에 삽입함. 들어오는 문서 변경이 트리들에 등록된 구간 가운데 하나와 맞닿으면 해당 쿼리가 일치한 것으로 판단하고 쿼리를 갱신함.

Perfy Gold

  • 구현한 기본 기능을 섀도 모드(shadow mode)로 배포해 새 쿼리 일치 파이프라인과 기존 파이프라인을 동시에 실행하고 결과가 일치하는지 확인함. 이 과정에서 성능도 검증함.
  • 이 방식은 당시 GitHub의 scientist 라이브러리에서 영감을 얻음.
  • 실시간 쿼리의 규모와 도입률이 크게 증가하기 시작하던 시점에 맞춰 배포됨.
  • Watch 시스템의 읽기 측에서 지연 시간이 빠르게 줄고 처리량이 증가함. 정확한 수치는 기억나지 않지만, 지연 시간과 처리량 모두 10배 넘게 개선된 것으로 기억하며 모니터링 그래프가 믿기 어려울 만큼 크게 변한 것으로 보였음.
  • 이 작업으로 Google이 뛰어난 성능 엔지니어링 작업에 주기적으로 수여하던 Gold Perfy 상을 받았으며, 프로젝트가 인정받은 큰 영예였음.

정리

  • 이 작업이 VLDB에 발표돼 다른 사람들이 배울 수 있게 된 점이 반가우며, 당시를 떠올리게 하는 경험임.
  • 쿼리 일치나 데이터베이스 내부 구조에 관심이 있다면 이메일로 더 이야기할 수 있음.