How Cursor Indexes Codebases Fast

Cursor, 최근 연간 매출 3억 달러(약 4,000억 원)를 달성했다고 발표한 인기 AI IDE는 Merkle 트리를 사용해 코드를 빠르게 인덱싱합니다. 이 글에서는 Cursor의 구현 방식을 자세히 살펴봅니다.

Cursor의 구현을 살펴보기 전에, 먼저 Merkle 트리가 무엇인지 이해해봅시다.

Merkle 트리 간단 설명

Merkle 트리는 모든 "리프(leaf)" 노드가 데이터 블록의 암호화 해시로 라벨링되고, 모든 비-리프(non-leaf) 노드는 자식 노드들의 라벨(해시값)을 다시 해싱한 값으로 라벨링되는 트리 구조입니다. 이로 인해 어떤 수준에서든 변경 사항이 해시값을 비교함으로써 효율적으로 감지될 수 있는 계층적 구조가 만들어집니다.

이를 데이터의 지문 시스템으로 생각해볼 수 있습니다:

• 각 데이터 조각(예: 파일)은 고유한 지문(해시값)을 가집니다.
• 지문 쌍을 결합해 새로운 지문을 만듭니다.
• 이 과정을 반복해 마지막에는 하나의 마스터 지문(루트 해시)만 남게 됩니다.

루트 해시는 개별 데이터에 포함된 모든 내용을 요약하는 암호학적 약속(commitment) 역할을 합니다. 이 방식의 장점은, 데이터의 한 부분이라도 변경되면 그 위의 모든 지문이 바뀌고, 결국 루트 해시도 바뀐다는 점입니다.

Cursor가 Merkle 트리를 코드베이스 인덱싱에 활용하는 방법

Cursor는 Merkle 트리를 코드베이스 인덱싱 기능의 핵심 요소로 사용합니다. Cursor의 창립자와 보안 문서에 따르면, 그 방식은 다음과 같습니다:

1단계: 코드 청킹 및 처리

Cursor는 먼저 코드베이스 파일을 로컬에서 청킹(chunking)합니다. 코드를 의미론적으로 의미 있는 조각으로 분할한 뒤 처리가 시작됩니다.

2단계: Merkle 트리 생성 및 동기화

코드베이스 인덱싱이 활성화되면, Cursor는 에디터에서 열린 폴더를 스캔하고 모든 유효한 파일의 해시로 Merkle 트리를 계산합니다. 이 Merkle 트리는 Cursor의 보안 문서에 설명된 대로 Cursor 서버와 동기화됩니다.

3단계: 임베딩 생성

청크가 Cursor 서버로 전송된 후, OpenAI의 임베딩 API 또는 커스텀 임베딩 모델(확인은 불가)로 임베딩이 생성됩니다. 이 벡터 표현은 코드 청크의 의미론적 의미를 포착합니다.

4단계: 저장 및 인덱싱

임베딩과 시작/종료 라인 번호, 파일 경로 등의 메타데이터는 원격 벡터 데이터베이스(Turbopuffer)에 저장됩니다. 경로 기반 필터링을 가능하게 하면서도 프라이버시를 유지하기 위해, Cursor는 각 벡터에 난독화된 상대 파일 경로를 저장합니다. 중요한 점은, Cursor의 창립자에 따르면 "여러분의 코드는 데이터베이스에 저장되지 않습니다. 요청이 끝나면 사라집니다."

5단계: Merkle 트리를 이용한 주기적 업데이트

Cursor는 10분마다 해시 불일치를 확인하여, Merkle 트리를 사용해 어떤 파일이 변경되었는지 식별합니다. 변경된 파일만 업로드하면 되므로, Cursor의 보안 문서에 설명된 대로 대역폭 사용량이 크게 줄어듭니다. 이 부분이 Merkle 트리 구조의 가장 큰 가치—효율적인 증분 업데이트—를 제공합니다.

코드 청킹 전략

코드베이스 인덱싱의 효과는 코드 청킹 방식에 크게 좌우됩니다. 이전 설명에서는 청킹 방법을 자세히 다루지 않았지만, Cursor와 유사한 코드베이스 기능을 만드는 블로그 포스트에서 몇 가지 인사이트를 얻을 수 있습니다:

• 단순한 방법은 코드를 문자, 단어, 줄 단위로 분할하지만, 의미론적 경계를 놓치는 경우가 많아 임베딩 품질이 저하됩니다.
• 고정된 토큰 수로 코드를 분할할 수도 있지만, 이 경우 함수나 클래스 같은 코드 블록이 중간에 잘릴 수 있습니다.
• 더 효과적인 방법은 코드 구조를 이해하는 지능형 분할기를 사용하는 것입니다. 예를 들어, 재귀적 텍스트 분할기는 클래스 및 함수 정의와 같은 상위 구분자를 사용해 의미론적 경계에서 분할합니다.
• 더 우아한 해결책은 코드의 추상 구문 트리(AST) 구조에 따라 분할하는 것입니다. AST를 깊이 우선으로 순회하며, 토큰 한도 내에 들어맞는 하위 트리로 코드를 분할합니다. 너무 작은 청크가 생기는 것을 방지하기 위해, 형제 노드들을 토큰 한도 내에서 더 큰 청크로 병합합니다. tree-sitter와 같은 도구를 사용해 다양한 프로그래밍 언어의 AST 파싱이 가능합니다.

토큰에 대한 간단한 설명은 이 글을 참고하세요.

임베딩이 추론 시점에 어떻게 사용되는가

Cursor가 코드 임베딩을 생성하고 저장하는 방법을 살펴본 후, 자연스럽게 드는 질문은: 생성된 임베딩이 실제로 어떻게 사용되는가? 이 섹션에서는 임베딩이 실제로 어떻게 활용되는지 설명합니다.

의미론적 검색 및 컨텍스트 검색

Cursor의 AI 기능(예: 코드베이스에 질문하기, ⌘ Enter 사용 등)을 사용할 때 다음과 같은 과정이 진행됩니다:

• 쿼리 임베딩: Cursor는 질문이나 작업 중인 코드 컨텍스트에 대한 임베딩을 계산합니다.
• 벡터 유사도 검색: 이 쿼리 임베딩이 Turbopuffer(Cursor의 벡터 데이터베이스)로 전송되어, 쿼리와 의미론적으로 유사한 코드 청크를 최근접 이웃 검색으로 찾습니다.
• 로컬 파일 접근: Cursor 클라이언트는 결과를 받아오며, 여기에는 난독화된 파일 경로와 가장 관련성 높은 코드 청크의 라인 범위가 포함됩니다. 실제 코드 내용은 여전히 사용자의 컴퓨터에 남아 있으며, 로컬 파일에서 읽어옵니다.
• 컨텍스트 조립: 클라이언트는 이 관련 코드 청크를 로컬 파일에서 읽어 서버로 전송하여, LLM이 질문과 함께 처리할 수 있도록 합니다.
• 정보에 기반한 응답: LLM은 이제 코드베이스에서 가져온 필요한 컨텍스트를 바탕으로, 질문에 더 정보에 기반한 답변을 하거나 적절한 코드 완성을 생성할 수 있습니다.

이 임베딩 기반 검색은 다음을 가능하게 합니다:

• 맥락 기반 코드 생성: 새 코드를 작성할 때 Cursor는 기존 코드베이스의 유사 구현을 참조해 일관된 패턴과 스타일을 유지할 수 있습니다.
• 코드베이스 Q&A: 코드베이스에 대해 질문하면, 실제 코드에 기반한 답변을 받을 수 있습니다(일반적인 답변이 아님).
• 스마트 코드 완성: 코드 완성이 프로젝트의 특정 규칙과 패턴을 인식해 더 똑똑해집니다.
• 지능형 리팩토링: 코드 리팩토링 시, 시스템이 코드베이스 전반에서 유사한 변경이 필요한 모든 부분을 식별할 수 있습니다.

Cursor가 Merkle 트리를 사용하는 이유

이 중 많은 부분이 보안과 관련되어 있으며, Cursor의 보안 문서에서 확인할 수 있습니다.

1. 효율적인 증분 업데이트

Merkle 트리를 사용하면 Cursor는 마지막 동기화 이후 변경된 파일만 빠르게 식별할 수 있습니다. 전체 코드베이스를 다시 업로드하는 대신, 수정된 파일만 업로드하면 됩니다. 이는 대규모 코드베이스에서 전체를 다시 인덱싱하는 데 드는 대역폭과 처리 비용을 크게 줄여줍니다.

2. 데이터 무결성 검증

Merkle 트리 구조는 Cursor가 인덱싱 중인 파일이 서버에 저장된 것과 일치하는지 효율적으로 검증할 수 있게 해줍니다. 계층적 해시 구조 덕분에 전송 중 불일치나 데이터 손상을 쉽게 감지할 수 있습니다.

3. 최적화된 캐싱

Cursor는 청크의 해시로 인덱싱된 임베딩을 캐시에 저장해, 동일한 코드베이스를 두 번째로 인덱싱할 때 훨씬 빠르게 처리할 수 있습니다. 이는 여러 개발자가 같은 코드베이스에서 작업하는 팀에 특히 유용합니다.

4. 프라이버시 보호 인덱싱

민감한 파일 경로 정보를 보호하기 위해, Cursor는 경로를 '/'와 '.' 문자로 분할한 뒤 각 세그먼트를 클라이언트에 저장된 비밀키로 암호화해 난독화합니다. 이 방식은 디렉터리 계층 구조에 대한 일부 정보는 노출하지만, 대부분의 민감한 세부 정보는 숨깁니다.

5. Git 히스토리 통합

코드베이스 인덱싱이 Git 저장소에서 활성화되면, Cursor는 Git 히스토리도 인덱싱합니다. 커밋 SHA, 부모 정보, 난독화된 파일 이름을 저장합니다. 같은 Git 저장소와 팀에서 데이터를 공유할 수 있도록, 파일 이름 난독화에 사용되는 비밀키는 최근 커밋 내용의 해시에서 파생됩니다.

임베딩 모델과 고려사항

임베딩 모델의 선택은 코드 검색 및 이해의 품질에 큰 영향을 미칩니다. 일부 시스템은 [all-MiniLM-L6-v2(https://huggingface.co/sentence-transformers/all-MiniLM-L6-v2)와 같은 오픈소스 모델을 사용하지만, Cursor는 OpenAI의 임베딩 모델이나 코드에 특화된 커스텀 임베딩 모델을 사용할 가능성이 높습니다. 코드 임베딩에 특화된 모델로는 Microsoft의 unixcoder-base나 Voyage AI의 voyage-code-2 등이 의미론적 코드 이해에 적합합니다.

임베딩 과제는 임베딩 모델의 토큰 한도 때문에 더 복잡해집니다. 예를 들어, OpenAI의 text-embedding-3-small 모델은 토큰 한도가 8192입니다. 효과적인 청킹은 의미론적 의미를 유지하면서 토큰 한도 내에 들어맞게 도와줍니다.

핸드셰이크 프로세스

Cursor의 Merkle 트리 구현에서 핵심적인 부분은 동기화 중에 발생하는 핸드셰이크(handshake) 프로세스입니다. Cursor 애플리케이션의 로그를 보면, 코드베이스 인덱싱을 초기화할 때 "merkle client"를 생성하고 서버와 "startup handshake"를 수행합니다. 이 핸드셰이크는 로컬에서 계산된 Merkle 트리의 루트 해시를 서버로 전송하는 과정을 포함합니다. 이는 GitHub의 Issue #2209와 ssue #981에서 확인할 수 있습니다.

핸드셰이크 프로세스는 서버가 코드베이스의 어떤 부분을 동기화해야 하는지 결정할 수 있게 해줍니다. 핸드셰이크 로그에 따르면, Cursor는 코드베이스의 초기 해시를 계산해 서버로 전송하고, 서버는 이를 검증합니다(자세한 내용은 Issue #2209 참고).

기술적 구현 과제

Merkle 트리 방식은 많은 장점이 있지만, 구현상 어려움도 있습니다. Cursor의 인덱싱 기능은 종종 부하가 심해 많은 요청이 실패할 수 있습니다. 이로 인해 파일이 완전히 인덱싱될 때까지 여러 번 업로드해야 할 수 있습니다. 사용자는 Cursor의 보안 문서에 언급된 대로, 'repo42.cursor.sh'로의 네트워크 트래픽이 예상보다 많아지는 것을 경험할 수 있습니다.

또 다른 과제는 임베딩 보안과 관련이 있습니다. 학계 연구에 따르면, 일부 경우 임베딩을 역으로 추출하는 것이 가능합니다. 현재의 공격은 주로 임베딩 모델에 접근할 수 있고 짧은 문자열을 다루는 경우에 한정되지만, 만약 공격자가 Cursor의 벡터 데이터베이스에 접근한다면 저장된 임베딩에서 인덱싱된 코드베이스 정보를 추출할 위험이 있습니다.