SmithDB의 전문 검색 (Full Text Search): 객체 스토리지 (Object Storage)를 위한 역색인 (Inverted

개요 (Overview)

SmithDB는 기반 데이터가 객체 스토리지 (Object Storage)에 저장된 크고 깊게 중첩된 JSON 문서로 구성되어 있음에도 불구하고, 에이전트 트레이스 (agent traces)에 대해 중앙값 (P50) 지연 시간 400ms로 전문 검색 (full-text search) 및 JSON 필터링을 지원합니다.

전문 검색 (Full-text search)은 이미 잘 알려진 분야입니다. Lucene은 20년의 역사를 가지고 있으며, Tantivy와 Quickwit는 이미 검색 및 인덱싱 (indexing)을 객체 스토리지 (Object Storage)로 확장했습니다. 하지만 SmithDB에 텍스트 검색 기능을 구축할 때, 우리는 문제에 원칙부터 접근하기로 결정했습니다. 왜냐하면 검색 워크로드 (search workloads)를 위한 에이전트 트레이스 (agent traces) 인덱싱은 독특한 과제를 제시하기 때문입니다.

SmithDB는 검색에 대한 다른 접근 방식이 필요합니다

과제 1: 에이전트 트레이스의 독특한 데이터 특성

모든 LangSmith 이벤트는 전체 바이트의 압도적인 대다수를 차지하는 inputs 및 outputs 필드를 인코딩합니다. inputs 및 outputs의 페이로드 (payload) 크기가 1MB 이상인 경우가 흔하며, 일부는 압축되지 않은 상태에서 수백 메가바이트에 달하기도 합니다. 이러한 콘텐츠 컬럼 (content columns)은 식별자 (identity), 타임스탬프 (timestamp) 및 기타 메타데이터 (metadata) 컬럼보다 수십 배 더 큽니다.

또한, 원래의 SmithDB 블로그 포스트에서 언급했듯이, 에이전트 트레이스 (agent traces)와 관련된 페이로드 (payload) 크기는 시간이 지남에 따라 계속 증가합니다. 이는 LLM 컨텍스트 윈도우 (context window) 크기가 커지고 에이전트가 더 긴 시간 범위 (time horizons) 동안 실행됨에 따라 LLM이 더 많은 컨텍스트를 축적하게 되는 직접적인 결과입니다.

이러한 특성은 검색 인덱스 (search index)의 일반적인 경제성을 역전시킵니다. 전통적인 로그 엔진 (log engine)은 수십억 개의 작은 문서들을 인덱싱하므로, 인덱스 크기가 각 문서에 비해 작습니다. 반면 우리는 수십억 개의 거대한 문서들을 인덱싱하며, 여기서 문서 하나가 여러 개의 작은 로그 라인보다 더 많은 인덱스 데이터를 생성할 수 있습니다. 일반적으로 로그의 소스 대 인덱스 (source:index) 비율은 약 1:1.25입니다. 그러나 LangSmith의 에이전트 트레이스 (agent traces)의 경우, 평균 비율이 1:1.9에 더 가깝다는 것을 관찰했습니다. 이에 따라 네 가지 사항이 뒤따릅니다:

인덱스가 없는 콘텐츠 필터는 치명적으로 느립니다. "도구 출력이 타임아웃을 언급하는 실행(run) 찾기"와 같은 쿼리는 후보 범위 내의 모든 페이로드 (payload)를 스캔할 수 없습니다. 그렇지 않으면 단 세 개의 행을 반환하기 위해 수 기가바이트를 스캔해야 하기 때문입니다. 단어 빈도 (Term frequencies)는 지프의 법칙 (Zipfian distribution)을 따릅니다. 자연어 및 JSON 페이로드는 멱법칙 (power law)을 따릅니다. 즉, 소수의 토큰 ("agents", "import", "role", "type"과 같은 도처에 존재하는 키들)은 거의 모든 문서에 나타나는 반면, 나머지 긴 꼬리 (long tail)의 용어들은 한두 번만 나타납니다. 인덱스는 단 하나의 파일 내에서, 매우 넓은 범위의 단어 빈도에 걸쳐 컴팩트 (compact)하고 가지치기 (prunable)가 가능한 상태를 유지해야 합니다. 다양한 쿼리 모달리티 (query modalities)가 중요합니다. 사용자는 경로 (path) ("이 실행에 inputs.content.messages가 포함되어 있는가?"), 값 (value) ("...Alex를 언급하는 곳..."), 그리고 자유 텍스트 (free text) ("...어딘가에서 지연 시간 퇴보(latency regression)를 언급하는 곳...")를 통해 쿼리합니다.

역색인 (Inverted index)은 콘텐츠 쿼리가 전체 페이로드 스캔 (full payload scan)을 수행하는 것을 방지하며, 무겁고 왜곡되었으며 반정형적인 (semi-structured) 페이로드를 수용할 수 있어야 합니다.

과제 2: 객체 스토리지 (Object storage)

SmithDB는 모든 영구 데이터 (durable data)를 객체 스토리지 (object storage)에 보관하므로, 컴퓨팅 (compute)은 상대적으로 상태가 없는 (stateless) 상태를 유지하며, 로컬 디스크를 관리할 필요 없이 노드를 추가함으로써 시스템을 확장할 수 있습니다.

쿼리 비용은 대략 **(객체 스토리지에 발행된 요청 수) × (요청당 읽은 바이트 수)**에 비례합니다. 객체 스토리지에서는 다음과 같은 특성이 있습니다:

각 객체 스토리지 요청은 수십 밀리초에서 수백 밀리초의 지연 시간 (latency)을 수반합니다.
요청당 처리량 (throughput)이 크지 않으므로, 필요 여부를 알기 전에 대규모 포스팅 리스트 (postings list)나 포지션 리스트 (positions list)를 가져오는 작업은 쿼리 시간을 지배할 수 있습니다.

스토리지 레이아웃 (storage layout)부터 쿼리 실행에 이르기까지 SmithDB 역색인의 모든 측면은 이러한 제약 사항을 염두에 두고 설계되었습니다.

SmithDB 검색 쿼리 형태 (search query shapes)

역색인의 스토리지 레이아웃을 더 깊이 파고들기 전에, 인덱스가 처리해야 하는 주요 쿼리 패턴을 살펴보겠습니다. SmithDB의 쿼리 인터페이스는 세 가지 서술어 (predicate) 제품군으로 요약되며, 이들은 무엇과 매칭되는지, 그리고 어떤 패턴 구문 (pattern syntax)을 허용하는지에 따라 달라집니다.

첫 번째는 경로 존재 여부 (path existence) (json_key): 이 문서에 키 K가 포함되어 있는가? 예를 들어 json_key(inputs, "author.name")는 author.name을 언급하는 문서가 무엇인지 묻습니다. 경로 존재 여부는 키 경로 자체에 대한 LIKE 연산도 지원합니다: json_key(inputs, "author.%") 또는 json_key(inputs, "%.user_id")는 일급 쿼리 (first-class query)입니다. 패턴은 경로의 어느 곳에서나 (접두사, 접미사, 중간) 나타날 수 있습니다.
두 번째는 키 지정 값 (keyed value) (json_key_search): 키 K가 값 V와 일치하는 값을 가지고 있는가? json_key_search(inputs, "author.name", "Jane")가 표준 형태입니다. 쿼리는 단일 토큰(single token)이거나 다중 토큰 구문(multi-token phrase) (json_key_search(inputs, "title", "latency regression"))일 수 있으며, 구문 변형은 인접성 (adjacency)을 추가합니다: "latency regression"은 해당 단어들이 값 내의 아무 곳에나 있는 것이 아니라, 연속적으로 나타나는 문서만 매칭합니다.
세 번째는 전문 검색 (full-text search) (search): 인덱싱된 값 중 어떤 것이라도 Q와 일치하는가? search(error, "timeout")는 텍스트 컬럼을 직접 검색하며, search(inputs, "latency regression")는 경로에 관계없이 모든 JSON 값을 검색합니다.

요약하자면:

이후의 모든 섹션은 이 표를 참조합니다. "경로 전용 쿼리 (path-only query)"라고 하면 json_key를 의미하고, "키 지정 값 (keyed value)"은 json_key_search를 의미하며, "전문 검색 (full-text)"은 search를 의미합니다.

역색인 (Inverted Indexes) 개요

역색인 (Inverted Index)은 Lucene부터 Tantivy에 이르기까지 모든 검색 라이브러리의 동력이 되는 데이터 구조입니다. 이는 교과서 뒷면에 있는 색인 (index)과 같습니다. 모든 페이지를 읽는 대신, 용어를 한 번 찾아 해당 용어가 언급된 페이지로 바로 건너뛰는 방식입니다. SmithDB는 이 아이디어를 기반으로 하며, 객체 스토리지 (Object Storage)에 저장하는 대규모 에이전트 추적 (agent-trace) 페이로드에 최적화된 저장 레이아웃 (storage layout)을 전문적으로 설계합니다.

용어 (Terms), 포스팅 (Postings), 위치 (Positions)

역색인 구조는 세 가지 개념에 기반합니다:

용어 (term): 인덱싱하는 단위로, JSON 경로, 키 지정 값, 또는 텍스트 토큰 (token)입니다.
포스팅 (posting): 특정 용어를 포함하는 문서 ID들의 정렬된 집합입니다.
위치 (position): 문서 내에서 용어가 나타나는 위치이며, 이것이 구문 검색 (phrase search)을 가능하게 합니다.

텍스트를 기준으로 인덱싱된 5개의 트레이스 (trace)를 예로 들어보겠습니다:

doc 0: "langchain agents emit traces"
doc 1: "langsmith engine runs deep agents"
doc 2: "langchain deep agents workflow"
...

인덱스는 각 용어 (term)당 하나의 항목을 유지하며, 해당 용어가 언급된 문서들을 가리킵니다:

term posting list positions
────────── ────────────── ─────────────────────────
agents [0, 1, 2, 3] 0:[1] 1:[4] 2:[2] 3:[0]
...

각 용어는 하나의 딕셔너리 (dictionary) 항목입니다. 값을 찾아 포스팅 리스트 (posting list)를 읽으면 어떤 문서를 가져와야 하는지 정확히 알 수 있습니다. search("deep agents")와 같은 쿼리는

deep에 대한 포스팅 리스트

([1, 2, 3, 4])

와

agents에 대한 포스팅 리스트

([0, 1, 2, 3])

의 교집합을 구하여, 페이로드 스캔 (payload scan) 없이 [1, 2, 3]을 얻습니다.

위치 (positions) 컬럼은 문서별로 용어가 나타나는 토큰 오프셋 (token offset)을 기록합니다. 예를 들어 1:[0]은 문서 1의 위치 0을 의미합니다. 이것이 구문 검색 (phrase search)을 가능하게 하는 핵심입니다. search("langsmith engine")은 langsmith가 오프셋 0에 있고 engine이 오프셋 1에 있어 (0 + 1 == 1) 문서 1과 일치하지만, powers와 the가 그 사이에 있는 (langsmith는 1, engine은 4에 위치한) 문서 4와는 일치하지 않습니다.

Tantivy가 아닌 Vortex를 활용한 이유

Tantivy는 매우 뛰어난 검색 인덱싱 라이브러리이며, Rust에서 Lucene 스타일의 검색을 구현할 때 당연히 고려되는 기준점입니다. 우리는 이를 직접 채택할 수 있을지 검토하는 것부터 시작했습니다. 우리가 최종적으로 도달한 설계는 Tantivy에서 많은 영감을 받았지만, 몇 가지 제약 사항으로 인해 우리의 사용 사례 (use-case)에 직접 적용하기에는 부적합했습니다.

로컬 디스크가 아닌 객체 스토리지 (Object storage). Tantivy는 mmap을 중심으로 구축되었습니다.

; 모든 바이트가 마이크로초 단위의 거리에 있으며 무작위 I/O (Random I/O)가 사실상 비용이 들지 않습니다. 우리는 왕복 시간(round trip)이 약 100ms인 객체 스토리지 (Object storage)를 사용하고 있으며, 여기서 쿼리 지연 시간 (Query latency)을 결정하는 것은 CPU가 아니라 레이아웃 (Layout)과 병합 (Coalescing)입니다.

컬럼형 엔진 (Columnar engine)에 내장됨. SmithDB 쿼리는 Vortex 상의 Apache DataFusion을 통해 실행됩니다. 우리는 검색 (Search) 기능이 다른 모든 서술어 (Predicate)와 동일한 스캔 파이프라인 (Scan pipeline)을 통해 푸시다운 (Push down)되기를 원했습니다. 즉, 자체적인 세그먼트 모델 (Segment model)과 I/O 가정을 가진 별도의 병렬 쿼리 스택으로 실행되는 것을 원하지 않았습니다.

Vortex 행과 정렬된 문서 ID (Doc IDs). Tantivy의 라이터 (Writer)는 삽입 순서에 따라 세그먼트 로컬 문서 ID (Segment-local doc IDs)를 할당하고, 모든 병합 (Merge) 시에 이를 재번호 매기기 (Renumbering) 합니다. SmithDB는 인덱스가 해당 Vortex 데이터 파일(우리는 핵심 이벤트 데이터 파일로 Vortex를 사용합니다)의 행 위치 (Row positions)를 직접 가리켜야 합니다. 따라서 문서 ID는 곧 행 인덱스 (Row index)가 됩니다. 즉, 번역 테이블 (Translation table)도 필요 없고, 쿼리 시점에 조정해야 할 두 번째 식별자 (Identity)도 없으며, 데이터 파일의 행 순서를 따르는 병합 (Merge) 시에도 재매핑 (Remap)이 필요 없습니다. 또한, 우리의 컴팩션 (Compaction)은 행 위치를 재매핑하는데, 이는 이 블로그 포스트의 두 번째 파트에서 자세히 설명할 Tantivy의 인덱스 병합 (Index merge) 방식과 잘 맞지 않습니다.

SmithDB의 역색인 (Inverted index) 개발 여정

Vortex에 대한 간단한 입문

Vortex는 SmithDB가 객체 스토리지 (Object storage)를 위해 사용하는 확장 가능한 컬럼형 (Columnar) 파일 형식입니다. Parquet와 같은 고정된 형식과 달리, Vortex는 플러그형 인코딩 (Pluggable encodings)과 사용자 정의 파일 레이아웃 (Custom file layouts)을 허용하므로, 파일 형식을 포크 (Fork)하지 않고도 워크로드에 맞춰 압축 및 I/O 액세스 패턴을 최적화할 수 있습니다.

모든 읽기 작업은 통계 (Statistics)를 사용하여 전체 로우 그룹 (Row groups)을 가지치기 (Prune)하고, 살아남은 행들을 마스크 (Mask)로 필터링 (Filter)하며, 쿼리가 실제로 필요로 하는 컬럼 (Column)만을 투영 (Project)합니다.

Vortex 파일의 I/O 단위는 세그먼트 (segment), 즉 연속된 물리적 바이트 범위입니다. 객체 스토리지 (Object Storage)에서 왕복 시간 (round-trip)은 대략 100ms가 소요되므로, 쿼리 지연 시간 (latency)을 줄이기 위한 주요 수단은 요청 (request) 횟수를 최소화하는 것입니다. Vortex의 I/O 스케줄러 (scheduler)는 인접한 세그먼트 읽기를 하나의 요청으로 병합 (coalesce)하며, 최대 16MB 윈도우 (window) 내에서 1MB 간격 이내의 읽기들을 하나로 합칩니다. 이를 통해 인덱스 (index) 내의 순차적 액세스 (sequential access) 패턴이 매우 적은 수의 객체 스토리지 GET 요청으로 매핑됩니다.

우리의 (실패한) 첫 번째 시도

첫 번째 버전은 교과서적인 역색인 (inverted index)을 거의 그대로 옮겨온 것이었습니다. 두 개의 컬럼 (column) (경로를 위한 term_key와 토큰을 위한 term_value)을 사용하여 세 가지 쿼리 형태를 모두 처리할 수 있도록 설계했습니다: 경로 존재 여부 (path-existence) 확인 시 term_key를 읽고, 키 기반 검색 (keyed search) 시에는 두 컬럼 모두에서 포스팅 (postings)을 교차 (intersect)하며, 전체 텍스트 (full-text) 검색 시에는 term_value만으로 교차합니다. 포스팅 (postings)은 List<u32> 셀 (cell)로 저장되었고, 위치 정보 (positions)는 List<List<u32>>로 저장되었습니다.

우리는 Vortex의 기본 설정을 활용했습니다: 용어 (term) 컬럼에는 FSST 인코딩 (encoding)을, 포스팅 (postings)과 위치 정보 (positions)에는 비트팩 (bitpacked) 인코딩을 사용했으며, 쿼리 시점에 가지치기 (pruning)가 가능한 존드 스토리지 레이아웃 (zoned storage layout)을 채택했습니다. (구문 검색 (phrase search)에 필요한) 위치 정보 (positions)만 해도 다른 모든 컬럼보다 10배가량 더 컸기 때문에, 인덱스를 핵심 실행 데이터 (core run data)와 분리된 별도의 파일에 보관했습니다. 이를 통해 인덱스 구축 (construction) 및 병합 (merge) 과정을 핵심 쓰기 경로 (write path)로부터 분리할 수 있었습니다. Vortex의 API는 행 인덱스 (row indices)와 마스크 (mask)를 기반으로 작동하므로, 인덱스 필터링 (filtering)을 자연스럽게 구성된 형제 파일 (sibling file)에 위임할 수 있었습니다.

규모가 커지면서 세 가지 문제가 나타났습니다:

용어별 인코딩 제어 불가. Vortex는 용어별이 아닌 컬럼 전체에 대해 인코딩을 선택합니다. 따라서 단일 공통 토큰 (agent, langchain...

)는 청크 전체의 모든 용어에 대해 더 큰 비트 폭 (bit width)을 강제하여, 비트 패킹 (bitpacking) 효율을 저하시킵니다. 컬럼의 나머지 부분은 더 나쁜 캐시 동작 (cache behavior)과 더 큰 읽기 비용으로 그 대가를 치러야 했으며, 우리는 고빈도 용어에 대해서만 선택적으로 더 공격적인 비트 패킹을 적용할 수 있는 수단이 없었습니다.

고정 크기 로우 그룹 (Fixed-size row groups)은 용어 왜곡 (term skew)을 인지하지 못했습니다.
우리는 로우 그룹당 고정된 수의 용어를 배치했는데, 이는 단 하나의 고빈도 용어가 하나의 로우 그룹을 압축 후 100 MB를 넘기게 만드는 반면, 다른 로우 그룹은 몇 MB에 머물게 함을 의미했습니다. 쿼리 시점에는 이것이 하나의 거대한 객체 스토리지 GET 요청으로 이어졌고, 병합 (merge) 시점에는 거대한 인메모리 디코딩 (in-memory decode)으로 이어졌습니다.

병합 (Merge) 과정에서 위치 정보 (positions)를 재구성해야 했습니다.
두 세그먼트를 병합한다는 것은 전체 위치 정보인 List<List<u32>>를 디코딩하고, 내부 리스트들을 새로운 문서 순서로 재배열하며, 모든 외부 오프셋 (outer offset)을 다시 계산해야 함을 의미했습니다. 컴팩션 (compaction) 시 CPU 시간과 할당 (allocations)이 모두 급증했습니다. 바이트의 70% 이상이 위치 정보인 인덱스에서, 이는 지배적인 컴팩션 비용이었습니다.

두 번째 시도: V2 역색인 (Inverted index) 저장 레이아웃

우리의 v2 레이아웃은 조직 단위(unit of organization)를 "로우 그룹당 N개의 용어"에서 **바이트 예산 기반 로우 그룹 (byte-budgeted row group)**으로 변경하고, Vortex의 기본값에 직접 의존하는 대신 컬럼별 바이트 레이아웃을 직접 제어함으로써 v1의 세 가지 문제를 모두 해결합니다. 이 섹션의 나머지 부분에서는 새로운 조직 단위, 그 내부에 무엇이 들어있는지, 그리고 바이트 예산을 확보하기 위해 선택한 인코딩 방식에 대해 설명합니다.