빠른 정규식 검색: Agent 도구를 위한 텍스트 인덱싱

작성 Vicent Marti분류:연구

시간은 평평한 원입니다. 1973년에 grep의 첫 버전이 출시되었을 때, 이는 파일시스템의 텍스트 파일에서 정규식과 일치하는 내용을 찾는 기본 유틸리티였습니다. 세월이 흐르며 개발자 도구가 발전하자, grep은 점차 더 특화된 도구들에 자리를 내주게 되었습니다. 처음에는 ctags 같은 대략적인 구문 인덱스가 등장했습니다. 이후에는 많은 개발자가 특정 프로그래밍 언어에 특화된 IDE로 옮겨 갔고, 이런 IDE는 코드를 파싱해 구문 인덱스를 만들고 여기에 타입 수준 정보까지 더해, 코드베이스를 매우 효율적으로 탐색할 수 있게 해주었습니다. 그리고 마침내 이것이 Language Server Protocol (LSP)로 표준화되면서, 이런 인덱스는 신구를 막론한 모든 텍스트 편집기로 확산되었습니다. 그러던 중 LSP가 막 표준으로 자리 잡아가던 시점에 에이전트 기반 코딩이 등장했고, 놀랍게도 에이전트는 grep을 정말 좋아합니다.

Agent의 컨텍스트를 수집하는 최첨단 기법은 이 외에도 있습니다. 저희는 이전에 여러 작업에서 시맨틱 인덱스를 사용하면 Agent 성능을 얼마나 개선할 수 있는지 이야기한 적이 있습니다. 하지만 특정 질의는 모델이 정규식 검색으로만 해결할 수 있습니다. 즉, 그사이 이 분야가 조금 발전하긴 했어도 다시 1973년으로 돌아가야 한다는 뜻입니다.

저희를 포함해 대부분의 Agent 하니스는 검색 도구를 제공할 때 기본적으로 ripgrep을 사용합니다. 이것은 Andrew Gallant가 개발한 독립 실행형 프로그램으로, 고전적인 grep의 대안이면서도 더 합리적인 기본 설정을 제공하고(예: 어떤 파일을 무시할지), 성능도 훨씬 뛰어납니다. ripgrep은 악명 높을 만큼 빠른데, 이는 Andrew가 정규식 매칭 속도에 대해 오랜 시간 깊이 고민해 왔기 때문입니다.

하지만 ripgrep이 파일 내용을 아무리 빠르게 매칭할 수 있어도, 한 가지 심각한 한계가 있습니다. 바로 모든 파일의 내용을 대상으로 매칭해야 한다는 점입니다. 작은 프로젝트에서는 괜찮지만, Cursor 사용자들 가운데 특히 대규모 Enterprise 고객은 아주 거대한 모노레포에서 작업합니다. 정말 고통스러울 만큼 큽니다. 저희는 15초가 넘게 걸리는 rg 호출을 일상적으로 보고 있으며, 이는 코드를 작성하는 Agent를 사용자가 적극적으로 상호작용하며 안내하는 워크플로를 크게 지연시킵니다.

정규식 매칭은 이제 에이전트 기반 개발의 핵심 요소가 되었고, 저희는 이를 명시적으로 겨냥하는 것이 중요하다고 생각합니다. 전통적인 IDE가 Go To Definition 같은 작업을 위해 로컬에 구문 인덱스를 만들듯이, 저희도 현대의 Agent가 텍스트를 찾을 때 수행하는 핵심 작업을 위한 인덱스를 만들고 있습니다.

고전적인 알고리즘

정규식 매칭 속도를 높이기 위해 텍스트 데이터를 인덱싱하는 아이디어는 결코 새로운 것이 아닙니다. 이 개념은 1993년 Zobel, Moffat, Sacks-Davis가 발표한 "Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files"라는 논문에서 처음 소개되었습니다. 이들은 n-gram(_n_개의 문자로 이루어진 문자열 조각)을 사용해 역인덱스를 만들고, 정규식을 인덱스에서 조회할 수 있는 n-gram 트리로 분해하는 휴리스틱을 제시합니다.

이 개념을 어디선가 들어본 적이 있다면, 아마 그 논문보다는 Google Code Search가 종료된 직후인 2012년에 Russ Cox가 게시한 블로그 글 때문일 가능성이 큽니다. 이후 개발된 거의 모든 다른 인덱싱 방식에도 이 개념이 적용되므로, 이런 인덱스의 기본 구성 요소를 빠르게 다시 살펴보겠습니다.

역색인

역색인은 검색 엔진의 핵심 데이터 구조입니다. 인덱싱할 문서 집합이 있으면, 각 문서를 토큰으로 나누어 역색인을 만듭니다. 이를 토큰화라고 하며, 방법은 매우 다양합니다. 이 예시에서는 가장 단순한 방식인 개별 단어를 토큰으로 사용하겠습니다. 이렇게 만들어진 토큰은 사전 같은 데이터 구조의 키가 되고, 값은 각 토큰이 등장하는 모든 문서의 목록이 됩니다. 이 목록은 일반적으로 _포스팅 리스트_라고 하는데, 각 문서가 숫자 값, 즉 "posting"으로 고유하게 식별되기 때문입니다. 하나 이상의 토큰을 검색하면 해당 포스팅 리스트를 불러오고, 포스팅 리스트가 여러 개라면 모두에 공통으로 나타나는 문서를 찾기 위해 이들의 교집합을 구합니다.

1. Documents

Edit documents to see how the index updates. Click to select and view terms.

Hover or tap a term to trace the same index entry.

D0
thecuriouscatsatbythewindowwatchingthelightdriftacrosstheroom
D1
D2
D3
2. Inverted Index

Each term maps to documents containing it. Hover or tap to inspect one entry at a time.

across
D0D1D2
and
D2D3
bat
D3
black
D2
by
D0D1D2D3
cat
D0D2
cautious
D1
curious
D0
drift
D0
fall
D1
in
D3
light
D0D1D2D3
rat
D1
room
D0D1D2D3
sat
D0D1D2D3
small
D3
the
D0D1D2D3
watched
D2D3
watching
D0D1
window
D0D1D2D3
20 unique terms from 4 documents
3. Search

Search for terms to find matching documents.

Try cat, the, or ran.

이 설계는 (여기에 많은 복잡성이 덧붙긴 했지만) 오늘날 대부분의 검색 엔진의 기반입니다. 하지만 이런 검색 엔진은 _자연어_를 대상으로 하고, 우리가 하려는 것은 정규식을 검색해 소스 코드에 매칭하는 일입니다. 그래서 이 방식은 그다지 잘 맞지 않습니다.

토큰화를 아주 정교하게 설계하면 여기서도 어느 정도 쓸 만한 것을 만들 수는 있습니다. 각 프로그래밍 언어의 문법을 이해하고, 소스 코드의 식별자를 잘게 나누는 식이죠. 하지만 이를 제대로 구현하기는 매우 어렵습니다. GitHub 초창기에는 Code Search 기능이 실제로 이런 방식으로 동작했습니다. 프로그래밍 언어를 위한 매우 복잡한 토크나이저와 아주 큰 ElasticSearch 클러스터를 사용했죠. 하지만 결과는 좋지 않았고, 사람들의 평가도 매우 나빴습니다. 식별자를 검색하는 것은 가능했지만(어느 정도는), 정규식 매칭은 할 수 없었습니다. 그러려면 더 나은 토큰화 방식이 필요합니다.

트라이그램 분해

소스 코드를 단순하게 토큰화하는 방식은 정규 표현식을 매칭하는 데 유용하지 않습니다. 문서를 더 기본적인 단위로 나눠야 합니다. 전통적인 알고리즘은 트라이그램을 선택합니다. 즉, 토큰은 입력 문자열에서 서로 겹치는 3문자 구간 하나하나입니다.

왜 3글자일까요? 이 트라이그램들을 역색인의 키로 저장할 것이기 때문입니다. 바이그램(2글자 조각)을 선택하면 인덱스의 키 수는 최대 64k로 매우 적어지지만, 각 키의 포스팅 리스트가 너무 커져 효율적으로 다루기 어렵습니다. 반대로 쿼드그램(4글자 조각)을 사용하면 포스팅 리스트는 매우 작아져서 좋지만, 역색인의 키 수가 수십억 개에 달해 이것 역시 다루기 어렵습니다.

따라서 트라이그램은 꽤 괜찮은 절충안입니다. 덕분에 문서를 인덱싱할 때의 토큰화는 매우 단순해집니다. 인덱싱 중인 문서에서 서로 겹치는 모든 3문자 시퀀스를 추출해, 이를 역색인의 토큰으로 사용하면 됩니다.

실제 복잡성은 정규 표현식을 인덱스와 매칭할 수 있도록 토큰화할 때 발생합니다. 정규 표현식에는 문법 이 있으므로, 이를 파싱한 뒤 실제로 텍스트를 나타내는 표현식 구간에서 어떤 트라이그램을 추출할 수 있는지 판단하기 위해 휴리스틱을 사용해야 합니다.

리터럴 문자열을 트라이그램으로 분해하는 일은 간단합니다. 문서를 인덱싱할 때와 같은 알고리즘을 사용하기 때문입니다. 문자열에 포함된 모든 겹치는 트라이그램을 추출하면, 이 트라이그램을 모두 포함하는 문서는 해당 리터럴도 포함할 가능성이 높습니다(물론 반드시 그런 것은 아닙니다!). 교대는 각각 따로 분해되며, 그 결과 두 개의 분기가 생기고 매칭되려면 문서가 그중 하나 를 포함해야 합니다. 역색인에서는 이를 질의할 때 포스팅 리스트를 교집합하는 대신 합집합 합니다. 문자 클래스는 여러 트라이그램으로 분해될 수 있습니다. [rbc]at 같은 작은 클래스는 클래스의 각 요소마다 하나의 트라이그램을 만듭니다. 더 넓은 문자 클래스를 사용할 때는 그 경계를 가로지르는 트라이그램은 추출하지 않습니다.

//i
Regex Analysis
regex/MAX_FILE_SIZE/
maxax_x_f_fifililele_e_s_sisizize
└── seqMAX_FILE_SIZE
maxax_x_f_fifililele_e_s_sisizize
└── lit"MAX_FILE_SIZE"
maxax_x_f_fifililele_e_s_sisizize
Required (AND):
_fi_siax_e_sfilileizele_maxsizx_f

전체를 종합해 보면

이제 문서를 토큰화하는 올바른 방법이 트라이그램이라는 점, 인덱스를 구축할 때 문서를 어떻게 토큰화해야 하는지, 그리고 검색할 때 쿼리를 어떻게 토큰화해야 하는지를 모두 알게 되었습니다. 이 모든 요소를 합치면 일반 표현식을 매우 효율적으로 매칭할 수 있는 실제 검색 인덱스를 만들 수 있습니다. 임의의 정규 표현식을 트라이그램 집합으로 분해하고 역인덱스에서 관련된 포스팅 리스트를 모두 불러오면, 해당 정규 표현식과 잠재적으로 일치할 수 있는 문서 목록을 얻을 수 있습니다. 이 점은 중요합니다! 최종 결과 집합은 이렇게 추려진 잠재적 문서들을 실제로 모두 불러와, 정규 표현식을 "전통적인 방식으로" 직접 매칭해 봐야만 얻을 수 있습니다. 그래도 이렇게 문서 하위 집합을 먼저 추려 두면 전체 코드베이스를 파일별로 스캔하며 매칭하는 것보다 항상 더 빠릅니다.

1. Documents

Edit documents to see how the index updates. Click to select and view trigrams.

Hover or tap a trigram to trace the same index entry.

D0
thehe·e·c·cacatat·t·s·sasat
D1
D2
D3
2. Inverted Index

Each trigram maps to documents containing it. Hover or tap to inspect one entry at a time.

·ba
D3
·ca
D0D2
·ra
D1D2
·sa
D0D3
a·c
D2
at·
D0D1D2D3
bat
D3
cat
D0D2
e·b
D3
e·c
D0
e·r
D1
he·
D0D1D3
ran
D1D2
rat
D1
sat
D0D3
t·r
D1D2
t·s
D0D3
the
D0D1D3
18 unique trigrams from 4 documents
3. Search

Search using literal strings or regular expressions to see trigram decomposition.

Try cat, the rat, or the regex c[au]t.

이 설계는 여러모로 완전히 실용적입니다. google/codesearchsourcegraph/zoekt 같은 프로젝트는 트라이그램 역인덱스를 사용해 대규모 인덱스에서도 좋은 성능을 제공합니다(물론 모든 검색 엔진이 그렇듯, 그 위에 훨씬 더 많은 복잡성이 덧붙습니다). 하지만 여기에는 분명한 한계도 있습니다. 인덱스 크기가 작지 않고, 쿼리 시점의 분해에서는 반드시 절충이 필요합니다. 단순한 휴리스틱을 사용하면 쿼리가 몇 개의 트라이그램으로만 분해되고, 그 결과 매칭을 확인해야 할 잠재적 문서가 많이 남게 됩니다. 반대로 복잡한 휴리스틱을 사용하면 수십 개, 어쩌면 수백 개의 트라이그램이 나올 수 있고, 이들을 역인덱스에서 모두 불러오는 일이 처음부터 전부 검색하는 것만큼 느려질 수도 있습니다.

이보다 더 나은 방법이 있습니다.

접미사 배열: 잠시 다른 이야기

정규 표현식 검색을 위한 텍스트 데이터 인덱싱의 역사를 살펴보고 있으니, 잠시 다른 이야기로 넘어가 Nelson Elhage가 2015년에 자신의 livegrep 웹 서비스용으로 개발한 이 구현을 이야기해 보고자 합니다. 다른 대규모 업계 프로젝트와 비교하면 livegrep은 아주 작은 편입니다 —Linux 커널의 최신 버전만 인덱싱하기 때문입니다— 하지만 범위가 좁은 만큼 구현 방식도 다른 어떤 것과도 꽤 다르고, 그래서 매우 흥미롭고 이야기할 가치가 있습니다.

Nelson은 문제를 가장 기본적인 원리부터 접근했습니다. 이 검색 엔진은 역색인에 의존하지 않습니다. 대신 모든 소스 코드를 접미사 배열 안에 인덱싱합니다.

접미사 배열이라는 개념은 이름 그대로입니다. 문자열의 모든 접미사를 정렬한 배열입니다. 더 큰 문자열로 배열을 만들어 보면, 이 자료 구조가 빠르게 커진다는 것을 알 수 있습니다. 꽤 비용이 큰 인덱스처럼 보일 수 있고 실제로도 여러 면에서 그렇지만, 원본 문자열에 접근할 수 있다면 저장 공간은 아주 효과적으로 압축할 수 있습니다. 각 접미사의 시작 오프셋만 저장하면 되기 때문입니다.

검색할 코퍼스에 대한 접미사 배열을 구성하고 나면, 정규 표현식을 리터럴들로 분해해 정규 표현식 검색을 효율적으로 수행할 수 있습니다. 그러면 정규 표현식의 가능한 모든 일치 위치를 접미사 배열에 대한 이진 검색으로 찾아낼 수 있습니다.

예를 들어 짧은 문자열th 를 검색해 보면, 이진 검색이 문서에서 실제로 일치하는 모든 위치로 범위를 어떻게 좁혀 가는지 확인할 수 있습니다.

Search the Suffix Array

정규 표현식 문법의 더 복잡한 구조도 접미사 배열의 같은 성질을 활용해 매칭할 수 있습니다. 예를 들어 [a-z]와 같은 문자 범위를 매칭하고 있다면, 범위의 시작과 끝을 이진 검색해 배열 범위를 좁힐 수 있습니다. 그 두 끝점 사이의 내용은 반드시 그 범위와 일치합니다.

1. Input String

Enter a string to build its suffix array. Each position in the string defines a suffix.

Hover or tap a suffix row to see where that suffix starts in the string.

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
h
i
t
h
e
r
·
a
n
d
·
t
h
i
t
h
e
r
2. Suffix Array

All suffixes sorted lexicographically. The array stores only indices; suffixes are derived from the original string.

PosIndexSuffix
06·and·thither
110·thither
27and·thither
39d·thither
416er
54er·and·thither
615her
73her·and·thither
812hither
90hither·and·thither
1013ither
111ither·and·thither
128nd·thither
1317r
145r·and·thither
1514ther
162ther·and·thither
1711thither

여기서의 한계는 무엇일까요? 접미사 배열은 입력 문자열로부터 만들어져야 합니다. 이것은 큰 제약입니다. 큰 코드베이스(혹은 서로 다른 여러 코드베이스)를 인덱싱하려는 경우, 먼저 모든 내용을 하나의 문자열로 이어 붙인 다음 그로부터 접미사 배열을 구성해야 합니다. 접미사 배열 안에서 일치를 찾을 때는, 그 일치 위치를 해당 내용을 담고 있는 원본 파일에 매핑하기 위한 보조 자료 구조도 필요합니다. 감당할 수 없을 정도의 복잡성은 아니지만, 인덱스를 동적으로 업데이트하는 비용을 매우 크게 만듭니다. 이 방식은 확장하기가 매우 어렵습니다.

확률적 마스크를 활용한 Trigram 쿼리

이제 좀 더 전통적인 설계로 돌아가 보겠습니다. 여기 _Project Blackbird_를 위해 원래 GitHub에서 개발된 접근 방식이 있습니다. 이 프로젝트는 기존 Code Search 기능을 대체하는 것을 목표로 한 연구 프로젝트였습니다. 앞서 살펴봤듯이, 기존 검색은 소스 코드를 토큰화하는 방식으로 구현되어 정규 표현식과 일치시킬 수 없었습니다. 이 새로운 구현의 목표는 그것이 가능하도록 만드는 것이었습니다.

초기 버전에서는 키로 trigram을 사용하는 전통적인 역색인을 쓰려 했지만, 곧 용량 문제에 부딪혔습니다. GitHub에는 코드가 워낙 많아서, 이를 trigram으로 색인하면 posting list가 너무 커져 검색하기 어려웠습니다.

trigram이 기대만큼 잘 맞지 않자, 다음 단계는 색인에 사용할 더 적절한 n-gram 크기를 찾는 것이었습니다. 이미 봤듯이 bigram은 너무 범위가 넓어 posting list가 감당하기 어려울 정도로 커지고, quadgram은 너무 구체적이어서 색인에 키가 지나치게 많아집니다. trigram은 그 둘 사이의 균형점이긴 하지만, 실제로 이상적인 크기는 오히려... 3.5-gram에 더 가깝습니다. 그렇다고 문자를 반으로 쪼갤 수는 없겠죠?

하지만 실제로는 그에 꽤 가까운 방법이 있습니다. 이 설계는 역색인의 키로 trigram을 사용하되, 해당 문서에서 그 trigram 뒤에 오는 "네 번째 문자"에 대한 추가 정보를 posting list에 덧붙이자는 제안입니다. 이를 위해 그 네 번째 문자를 추가 바이트로 그대로 저장할 수도 있겠지만, 그러면 사실상 색인이 quadgram 색인이 되어 버리고, 앞서 봤듯이 그런 색인은 저장하기엔 너무 큽니다. 그래서 대신 저장하는 것은 해당 trigram 뒤에 올 수 있는 모든 문자를 담은 bloom filter입니다.

1. Documents & Trigrams

Each trigram gets an 8-bit locMask (position mod 8) and nextMask (hash of each follow-up character).

Hover or tap a trigram to trace the same entry in the index.

D0
the@0he·@1e·f@2·fo@3fox@4
D1
D2
D3
2. Phrase-Aware Trigram Index

Each (trigram, doc) entry stores two 8-bit masks. Hover or tap to inspect one trigram at a time.

·ca
D1
loc00100000next00000100
D3
loc00001000next00010000
·fo
D0
loc00001000next00000001
·re
D1
loc00000010next00010000
·ru
D2
loc00001000next01000000
a·r
D1
loc00000001next00100000
car
D1
loc01000000next00000000
cat
D3
loc00010000next00000000
d·c
D1
loc00010000next00000010
e·c
D3
loc00000100next00000010
e·f
D0
loc00000100next10000000
ed·
D1
loc00001000next00001000
fox
D0
loc00010000next00000000
D2
loc00000001next00000001
he·
D0
loc00000010next01000000
D3
loc00000010next00001000
ox·
D2
loc00000010next00000100
red
D1
loc00000100next00000001
run
D2
loc00010000next00001000
the
D0
loc00000001next00000001
D3
loc00000001next00000001
uns
D2
loc00100000next00000000
x·r
D2
loc00000100next00100000
locMaskBit i is set when the trigram can start at position pos mod 8 = i.
nextMaskBits mark the hashed follow-up characters that can come right after the trigram.

bloom filter를 아주 크고 복잡한 데이터 구조라고 생각할 수도 있지만, 꼭 그럴 필요는 없습니다. bloom filter는 아주 적은 수의 비트로도 표현할 수 있습니다. 인코딩만 신중하게 하면 8비트 안에도 많은 정보를 담을 수 있습니다. posting당 단 2바이트만으로도, 전통적인 trigram 색인의 가장 큰 두 가지 문제를 우회할 수 있습니다.

각 trigram 뒤에 오는 문자를 담은 마스크가 있으면, 역색인은 trigram 키로 구축하면서도 쿼리는 quadgram으로 수행할 수 있습니다! 이렇게만 해도 단순한 trigram 색인보다 후보 문서 범위를 훨씬 더 좁힐 수 있습니다.

문서에서 trigram이 나타나는 오프셋을 담은 두 번째 보강 마스크는 trigram의 모호성 문제를 해결합니다. 문서에 두 trigram이 들어 있다고 해서 그것들이 실제로 서로 바로 붙어 있는 것은 아니며, 쿼리를 일치시키려면 바로 그 점이 중요합니다. 두 번째 trigram의 위치 마스크를 왼쪽으로 한 비트 이동한 뒤 첫 번째 trigram의 마스크와 비교하면, 둘이 실제로 인접해 있는지 확인할 수 있습니다. 특히 매우 흔한 trigram의 경우, 후보 문서 목록을 더 좁히는 데 이 방법은 매우 유용합니다.

물론 이 모든 정보는 확률적입니다. bloom filter에 저장된 다른 정보와 마찬가지로, 거짓 양성이 발생할 수 있습니다. 하지만 최종 일치는 텍스트 자체를 대상으로 결정론적으로 수행되므로, 여기서는 거짓 양성이 항상 허용됩니다. 목표는 색인을 사용해 실제로 스캔해야 하는 후보 문서 수를 최소화하는 것입니다.

Search the Phrase Index
Query trigrams:
e·f ·fo
Checking consecutive pair:"e·f" → "·fo"
AInverted Index Lookup
e·fD0
·foD0
Candidates (intersection):D0
Inspect one candidate:Tap a row to expand the full bit-mask walkthrough.
D0"the fox"
BAdjacency Filter (nextMask)
nextMask(e·f, D0):7654321010000000
hash(o) = bit 7Bit is set
CPosition Filter (locMask + rotation)
locMask(e·f):00000100
rotate left by 1:
rotated:00001000
locMask(·fo):00001000
AND:00001000Non-zero intersection
Likely match, verify with a full scan
Algorithm result:
D0
Actual matches (full scan for "e fo"):D0

이렇게 만들어진 색인은 매우 효율적이지만 큰 단점이 있습니다. Bloom filter는 포화될 수 있습니다. 이것은 bloom filter의 아쉬운 특성입니다. 업데이트는 가능하지만, 데이터를 너무 많이 추가하면 결국 필터의 모든 비트가 설정됩니다. 그리고 bloom filter가 포화되면 무엇이든 일치하게 되어, 결국 우리가 맨 처음 이야기했던 첫 번째 색인의 성능 수준으로 되돌아가게 됩니다.

이 색인은 저장 공간을 최소화하지만, 제자리에서 업데이트해야 할 때는 상당히 다루기 까다롭습니다.

Sparse N-grams: 더 똑똑한 트라이그램 선택

여기 또 하나의 아주 영리한 아이디어가 있습니다. ClickHouse의 정규 표현식 연산자나, 몇 년 전 GitHub에서 배포된 새 Code Search 기능에서 이 방식이 쓰이는 것을 보셨을 수도 있습니다. 이 기능은 실제로 정규 표현식 매칭도 지원합니다. 이름은 Sparse N-grams이며, 여러 방식 사이에서 아주 훌륭한 절충안입니다.

기존의 트라이그램 인덱스는 연속된 3문자 시퀀스를 모두 추출하지만, 이렇게 하면 중복이 아주 많이 생깁니다. 각 트라이그램의 문자가 인접한 트라이그램에도 반복해서 들어가기 때문입니다. 이 알고리즘에서는 길이가 제각각인 n-gram들을, 개수도 가변적으로 추출합니다.

물론 여기서 무작위 는 진짜 무작위일 수는 없습니다. 그렇게 되면 인덱스를 쿼리할 수 없기 때문입니다. 우리는 문서 안의 모든 문자 쌍에 "가중치"를 할당합니다. 이 가중치는 결정적이기만 하면 무엇이든 괜찮습니다(ClickHouse는 두 문자의 crc32 해시를 사용합니다). 그리고 sparse n-grams는 양 끝의 가중치가 내부에 포함된 모든 가중치보다 엄격하게 큰 모든 부분 문자열이 됩니다.

중요한 점은 sparse n-grams가 어떤 길이든 될 수 있다는 것입니다. 즉, 길이가 일정하지 않습니다. 또 경우에 따라 아주 많은 sparse n-grams가 생성될 수도 있습니다. 단순히 트라이그램만 추출할 때보다 더 많을 수도 있죠. 하지만 n-gram이 결정적으로 생성되기 때문에, 쿼리 시점에는 매우 중요한 최적화를 몇 가지 적용할 수 있습니다. 어떻게 가능한지 살펴보겠습니다.

이 알고리즘은 쉽게 이해할 수 있는 편이 아니므로, 직접 살펴보며 이해해 보겠습니다. 시각화에서 뒤로 앞으로 화살표를 사용해 단계별로 따라갈 수 있습니다.

입력에 대한 문자 분해도 위쪽에서, 각 문자 쌍에 부여된 무작위 가중치를 볼 수 있습니다. 이 가중치가 어떤 구간이 n-gram으로 추출될지를 결정합니다.

맨 아래 섹션에서는 입력 문자열에서 몇 개의 sparse n-grams가 추출되는지, 그리고 바이그램, 트라이그램, 쿼드그램을 사용했다면 각각 몇 개가 추출됐을지를 볼 수 있습니다. 그 차이가 얼마나 큰지 주목해 보세요. 실제로 우리는 아주 많은 sparse n-grams를 추출하고 있습니다!

그럼 이건 대체 무슨 의미일까요? 그냥 비효율적인 일을 하고 있는 걸까요? 꼭 그렇지는 않습니다. 우리는 인덱싱 시점에 높은 선행 비용을 치르는 대신, 쿼리 시점에 매우 빠른 쿼리를 얻습니다. 지금 보고 있는 build_all 알고리즘은 문서를 인덱싱할 때 사용하는 방식입니다. 이 방식은 입력에서 가능한 sparse n-grams를 모두 추출합니다. 하지만 쿼리할 때는 그럴 필요가 없다는 점에 주목하세요. 가중치는 무작위처럼 보이지만 결정적이기 때문에, 쿼리 시점에는 covering algorithm 을 사용해 인덱스에서 매칭하는 데 필요한 최소한의 n-grams만 생성할 수 있습니다.

Sparse N-Gram Algorithm

n-grams가 최소라는 점은 분명합니다. 인덱싱 시점에는 내부에 포함된 모든 가중치가 양 끝의 가중치보다 작을 때만 n-gram을 생성하기 때문입니다. 따라서 양 끝에 있는 sparse n-grams만 추출하면 되며 —모든 트라이그램을 추출할 때보다 훨씬 적은 수만으로도— 매우 높은 정확도로 후보 문서를 골라낼 수 있습니다.

Pseudo-random weights based on CRC32 hash
#1Position 0: Consider bigram "MA" with weight 5D552B1
MAX_FILE_SIZE
0123456789101112
TypeTotalDistribution
Sparse17
2-grams12
3-grams11
4-grams10

이보다 더 나은 방법이 있을까요? 네! 사실 훨씬 더 좋게 만들 수 있습니다. 지금까지는 알고리즘의 가중치 함수 예시로 crc32를 사용해 왔습니다. 하지만 결정적이기만 하다면 어떤 해시 함수라도 여기서는 사용할 수 있습니다. 아주 영리한 방식을 하나 골라 봅시다. 실제로 매우 드문 모든 문자 쌍에는 높은 가중치를 주고, 매우 자주 나타나는 모든 문자 쌍에는 낮은 가중치를 주는 해시 함수입니다.

이 해시 함수는 계산도 쉽습니다. 우리는 소스 코드를 인덱싱할 것이므로, 인터넷에서 몇 테라바이트 분량의 오픈소스 코드를 가져와 그 안에서 발견되는 모든 문자 쌍의 빈도표를 만들 수 있습니다. 그 빈도표가 바로 우리의 해시 함수입니다. 이를 알고리즘에 적용하면 어떤 일이 일어나는지 보세요. 이제 가장 높은 가중치는 가장 드물게 나타나는 문자 쌍에 부여되고, 그 결과 covering mode에서는 조회해야 하는 n-그램 수가 더욱 줄어들고, 일치할 가능성이 있는 문서 수도 함께 줄어듭니다.

포스팅 조회량을 최소화하는 이 접근 방식은 사용자 머신에서 효율적으로 쿼리할 수 있는 인덱스를 구축하기 위한 완벽한 출발점이 됩니다.

이 모든 것을, 여러분의 머신에서

정규 표현식 검색 속도를 높이기 위한 인덱스는 어딘가에 있어야 합니다. 지금까지 살펴본 설계는 모두 서버 측에 배포되었고, 앞서 이야기한 시맨틱 인덱스 역시 서버에서 관리되고 쿼리됩니다. 하지만 여기서는 다른 방향을 택했습니다. 인덱스를 사용자 머신에서 만들고, 사용자 머신에서 쿼리하는 것입니다.

이 인덱스를 로컬에 두는 것이 합리적인 이유는 여러 가지가 있습니다. 첫째, 인덱스는 정규 표현식을 매칭하는 데 필요한 요소 중 일부 일 뿐입니다. 인덱스는 정규 표현식이 일치할 가능성이 있는 문서의 범위를 좁혀 주지만, 결국에는 각 파일을 하나씩 직접 스캔해야 합니다. 이 과정을 서버에서 처리하려면 모든 파일을 동기화하거나, 클라이언트와 서버 사이에 비용이 큰 왕복 통신을 반복해야 합니다. 반면 클라이언트에서 처리하는 것은 간단하고, 데이터 저장과 관련된 보안 및 개인정보 보호 문제도 많이 피할 수 있습니다.

지연 시간도 이 기능에서는 매우 중요합니다. 저희 Composer 모델은 업계 최고 수준의 초당 토큰 수(TPS)를 제공하며, 더 똑똑하면서도 빠르게 만들기 위해 꾸준히 노력하고 있습니다. 모델이 끊임없이 사용하고, 그것도 자주 병렬로 수행하는 이처럼 중요한 작업에 네트워크 왕복까지 추가하면 마찰과 지연만 늘어날 뿐이고, Agents와 상호작용하는 경험에 대해 저희가 지향하는 방향과는 반대로 가게 됩니다.

시맨틱 인덱스와 달리, 정규 표현식 검색용 인덱스는 매우 최신 상태 를 유지해야 하며, 특히 모델이 자신이 방금 쓴 내용을 다시 읽는 상황에서는 더욱 그렇습니다. 시맨틱 인덱스는 지속적으로 업데이트할 필요가 없습니다. 파일이 수정된 후 해당 파일의 임베딩을 다시 계산하더라도, 새로운 임베딩이 다차원 공간에서 기존 위치를 크게 벗어나지는 않기 때문입니다. 우리가 수행하는 최근접 이웃 검색은 여전히 Agent를 올바른 방향으로 이끕니다. 하지만 에이전트가 특정 텍스트를 찾고 있는데 이를 발견하지 못하면, 자주 쓸데없는 곳을 헤매고 토큰을 낭비하게 되며, 애초에 성능 최적화를 하려던 목적 자체를 무너뜨리게 됩니다.

이 인덱스를 클라이언트로 가져오면 그에 따른 과제도 생깁니다. 디스크 데이터를 동기화하는 일은 복잡하고 비용이 많이 들 수 있지만, 실제로는 매우 효율적으로 처리하고 있습니다. 저희는 기반이 되는 Git 리포지토리의 커밋을 기준으로 인덱스 상태를 관리합니다. 사용자와 에이전트의 변경 사항은 그 위에 하나의 레이어로 저장됩니다. 덕분에 업데이트가 매우 빠르고, 시작 시 로드와 동기화도 매우 빠르게 이루어집니다.

에디터의 메모리 사용량을 최소화하기 위해, 저희는 인덱스를 두 개의 별도 파일에 저장합니다. 첫 번째 파일에는 인덱스의 모든 포스팅 리스트가 차례대로 들어 있으며, 생성 과정에서 이를 직접 디스크에 플러시합니다. 다른 파일에는 모든 n-gram의 해시와 postings 파일에서 해당 포스팅 리스트가 위치한 오프셋이 정렬된 테이블 형태로 들어 있습니다. 여기서 전체 n-gram을 저장하지 않고 해시만 저장해도 항상 안전합니다. 두 해시가 충돌하면 포스팅 리스트의 범위가 더 넓어질 수는 있지만(실제로는 극히 드문 경우입니다), 잘못된 결과를 반환하지는 않습니다. 또한 조회 테이블을 매우 조밀한 레이아웃으로 구성할 수 있습니다. 그런 다음 에디터 프로세스에서는 이 테이블만 mmap 하고, 이 테이블을 사용해 이진 검색으로 쿼리를 처리합니다. 검색 결과로 오프셋이 반환되면, postings 파일의 해당 오프셋 위치에서 직접 읽어 옵니다.

Hover or tap a lookup-table row to trace where its posting lives on disk.

Lookup Table (mmap)
hashoffset
0001290
0020ed14
00239b24
0026d840
002c7032
002daf80
002eaf50
002f8d64
002ff458
00330572
0036f086
03bd658
Postings File (disk)
@n-gramfiles
0MAX03
8AX_FI0
14FILE024
24LE_S03
32_SIZ05
40SIZE056
50conf12
58fig.1
64g.rs14
72main37
80ain.3
86util246

결론

저희는 자체 Composer 2와 같은 빠른 모델에 텍스트 검색 인덱스를 제공하면 Agent 워크플로에 확연한 질적 차이가 생긴다는 점을 확인했습니다. 이러한 효과는 규모가 큰 Enterprise 리포지토리에서 훨씬 더 두드러지는데, grep은 작업 중인 코드의 크기와 복잡도에 따라 지연 시간이 늘어나는 몇 안 되는 Agent 작업 중 하나이기 때문입니다. Composer 2로 실행되는 다음 예시 워크플로를 살펴보세요. 코드베이스 검색에 드는 시간을 아예 없애면 —특히 Agent가 버그를 조사할 때— 상당한 시간을 절약할 수 있고, 훨씬 더 효과적으로 반복 개선할 수 있습니다.

Toggle the mode, then hover or tap a segment to inspect its duration.

Investigation in chromiumRefactoring in chromiumInvestigation in cursorMinor feature in cursor0s30s60s90s120s150s180s210s240sThinkingGrepReadEdit

앞으로는 무엇이 나올까요? 아직은 아무도 모릅니다! Agent에 컨텍스트를 제공하는 방법을 둘러싼 흥미로운 발전이 많이 이루어지고 있고, 이 분야에는 저희를 포함해 많은 연구자들이 참여하고 있습니다. 저희는 시맨틱 인덱스를 포함한 현재 접근 방식의 성능을 계속 최적화하는 한편, Agent의 성능을 한층 더 끌어올릴 완전히 새로운 방법도 선보이기를 기대하고 있습니다. 동시에 정말 중요한 곳, 즉 Agent 기반 개발의 미래가 본격적으로 자리 잡고 있는 전 세계의 가장 대규모 리포지토리에서도 항상 활용할 수 있도록 보장할 것입니다.

분류: 연구

작성자: Vicent Marti

빠른 정규식 검색: Agent 도구를 위한 텍스트 인덱싱 · Cursor