코드 검색은 왜 어려운가

 (blog.val.town)
1P by GN⁺ | ★ favorite | 댓글 1개
  • Val Town 검색은 Postgres ILIKE 기반 부분 문자열 검색이라 순위화가 거의 없고, 여러 단어 쿼리도 약해 개선 요구가 많음
  • 자연어 검색의 불용어 제거, 어간 추출, 표제어 처리 같은 규칙은 코드의 변수명·함수명·토큰 경계를 망가뜨릴 수 있음
  • Postgres Full Text Search는 인프라를 단순하게 유지할 수 있지만, 이전 프로젝트에서 확장성 문제가 있었고 Val Town도 단일 노드 Postgres 한계를 시험 중임
  • 소프트 론치한 v2 검색은 pg_trgrm 기반 trigram 검색을 쓰지만, 정규식 검색과 달리 자유형 쿼리의 순위화는 원하는 수준으로 맞추기 어려움
  • Elasticsearch, Meilisearch, Zoekt, ParadeDB 같은 대안은 있으나 별도 인프라, 운영 부담, 호스팅 지원 여부가 선택의 제약으로 남아 있음

Val Town 검색이 막힌 지점

  • Val Town 검색은 현재 Postgres의 ILIKE를 사용함
    • 검색어가 코드 안에 포함되어 있으면 결과에 나타나는 부분 문자열 검색 방식임
    • 순위화는 거의 없고, 여러 단어 쿼리는 제대로 지원되지 않음
  • 더 나은 검색은 Val Town에서 가장 많이 요청된 기능 중 하나임
  • 개선 작업은 진행 중이지만, 아직 요구사항에 맞는 해법을 찾지 못함
  • 지금까지 확인한 조건은 다음과 같음
    • 주류 검색 솔루션은 자연어에 맞춰 설계됨
    • 코드 검색이 필요한 대기업은 자체 검색 시스템에 많은 시간과 비용을 투자함
    • Val Town은 이미 많은 데이터를 가지고 있어 잘 확장되는 해법이 필요함
    • 데이터베이스 확장 대신 별도 검색 서비스를 쓰면 인프라와 복잡도 측면의 절충이 중요해짐

자연어 검색 규칙이 코드에 맞지 않는 이유

  • 일반적인 전문 검색(FTS) 설정은 영어 같은 자연어를 대상으로 한 알고리듬을 기본 제공함
    • 불용어 제거: “the”, “it”처럼 너무 흔한 단어를 색인 전에 제거함
    • 어간 추출: “running”을 “run”으로 바꿔 “runs” 검색으로도 찾을 수 있게 함
    • 표제어 처리: “excellent” 검색이 “great”가 포함된 문서도 찾도록 동의어를 더 흔한 단어로 대체할 수 있음
  • 같은 규칙을 코드에 적용하면 의미가 어긋남
    • TypeScript에서 the는 불용어가 아니라 검색하고 싶은 유효한 변수명일 수 있음
    • 코드의 단어 경계는 자연어와 다름
    • 함수명에 어간 추출을 적용해도 의미 있는 결과를 기대하기 어려움
  • Postgres to_tsvector('english', ...)는 자연어 문장을 색인하면서 원문을 크게 바꿈
    • I am writing this example sentence는 'exampl':5 'sentenc':6 'write':3처럼 변환됨
  • 코드에서는 토큰화 문제가 더 두드러짐
    • function stringifyNumber(a: number): string { return a.toString() }가 'a.tostring':7 'function':1 'number':4 'return':6 'string':5 'stringifynumb':2처럼 색인됨
    • function 같은 단어는 남고, a.toString()은 .이 기본 단어 경계가 아니어서 두 토큰으로 나뉘지 않음

Postgres Full Text Search의 장단점

  • Postgres는 Full Text Search 확장을 제공하고, Val Town의 호스팅 제공자인 Render도 이를 지원함
  • Val Town은 지금까지 Postgres를 적극적으로 사용해 왔고, Postgres는 문서화와 호스팅 지원이 좋은 기술로 평가됨
  • 작은 팀에게는 인프라를 가능한 한 단순하게 유지하는 것이 중요해, Postgres로 해결할 수 있으면 Postgres를 쓰려는 유인이 큼
  • 다만 이전에 FTS를 사용한 프로젝트들은 성능과 확장성 문제를 겪음
    • Observable은 결국 Elasticsearch로 이동함
    • Val Town은 많은 vals를 가지고 있고, 단일 노드 Postgres 클러스터의 한계를 시험하고 있음
  • 코드 검색에 FTS를 성공적으로 쓴 사례를 찾기 어려워, 첫 번째 선택지로 쓰기보다는 예비안으로 남겨둔 상태임

pg_trgrm 기반 v2 검색 실험

  • Val Town이 소프트 론치한 v2 검색 알고리듬은 Postgres의 pg_trgrm에 기반함
    • pg_trgrm은 Postgres에서 trigram 검색을 구현함
  • 코드 검색에서 trigram은 이미 성공 사례가 있음
    • Russ Cox의 2012년 글은 Google Code Search가 trigram 색인과 특수 정규식 구현을 사용한 사례를 다룸
    • GitHub의 새 코드 검색 시스템도 trigram 검색을 사용함
    • Sourcegraph는 Google에서 이어받은 trigram 기반 검색 도구를 보유함
  • Val Town의 Postgres pg_trgrm 접근은 Stephen Gutekanst의 Postgres 기반 로컬 저장소 색인 글에서 많은 영향을 받음
  • 구현은 검색 텍스트가 들어 있는 컬럼에 GIN 색인과 gin_trgm_ops를 적용함
  • pg_trgrm은 정규식 검색에는 좋은 해법이지만, Val Town의 대부분 검색처럼 더 자유로운 쿼리에는 잘 맞지 않음
    • 검색 순위화에는 word_similarity를 사용 중임
    • 합리적인 순위에 가깝게 알고리듬을 조정하는 일이 매우 어려움

검색 엔진 선택지와 운영 절충

  • 검토 대상에는 독립 실행형 검색 서비스와 Postgres 확장이 섞여 있음
    • Meilisearch: 독립 실행형, Rust, 41k 스타
    • Typesense: 독립 실행형, C++, 17k 스타
    • Zoekt: 독립 실행형, Go, 406 스타
    • ParadeDB: Postgres 확장, Rust, 3.2k 스타
    • Sonic: 독립 실행형, Rust, 19.4k 스타
  • 코드 전용 도구는 존재하지만, 대부분은 비공개임
    • GitHub 검색은 뛰어나지만, 전담 팀과 실제 시간 예산이 들어간 결과물임
  • Sourcegraph가 유지하는 Zoekt 포크는 흥미롭지만 매우 니치하고, 큰 신규 인프라 투자가 필요함
  • Elasticsearch는 결국 피할 수 없는 해법이 될 수 있음
    • 코드 전용 처리는 없지만 거의 무한히 커스터마이즈할 수 있음
    • Java 메모리 튜닝 학습, 애플리케이션에 첫 영구 디스크 스토리지 도입, 데이터의 추가 진실 공급원 관리가 부담임
    • Elasticsearch Cloud를 쓰면 유지보수 부담을 줄일 가능성이 있음
  • Meilisearch는 Elasticsearch 대안으로 유망해 보임
    • Rust 기반이라는 매력이 있음
    • 자체 비교 글에서는 확장성보다 지연 시간을 더 강조하는 듯하며, 인프라 부담이 더 낮을지는 확실하지 않음
  • ParadeDB는 Elasticsearch처럼 동작하지만 “그냥 Postgres”라는 점이 매력적임
    • 다만 Render에서는 아직 해당 확장을 사용할 수 없음

작은 팀이 검색 인프라를 고를 때의 부담

  • 코드 검색은 영어 검색보다 난도가 높음
  • 작은 팀은 인프라를 단순하게 유지하고, 개발 환경 설정을 쉽게 만들고, 데이터를 같은 곳에 두려는 유인이 있음
  • Val Town은 지속적인 관리가 필요한 선택지에 성급히 묶이지 않으려 함
  • 중대형 회사에 검색 “서비스”만 있는 것이 아니라 검색 “팀”이 있는 데는 이유가 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • Sourcegraph에 있는데, 대규모 처리는 당연히 필요하지만 제품에 코드 검색을 처음 넣는다면 처음부터 색인으로 시작하지 말고, 한계가 올 때까지 즉석 검색을 추천함
    처음 N개 결과만 찾으면 되는 경우에는 전체를 끝까지 훑지 않아도 결과 버퍼를 채울 수 있어서 생각보다 오래 버팀. 이런 걸 만드는 사람, Val Town 쪽 사람들과도 기꺼이 이야기해보고 싶음

    • 색인 검색이 필요해지면 Zoekt가 내가 찾은 최선의 방법임
      Sourcegraph가 예전에 Zoekt 유지보수를 맡아줬고, Livegrep과 Hound는 우리가 색인하려던 규모에서 여러 면으로 버거웠음. 오래되고 삐걱대던 OpenGrok 배포에서 Zoekt로 옮긴 뒤 색인 성능과 검색 성능/사용성 모두에서 차이가 컸음. Sourcegraph는 Zoekt가 제공하는 코드 검색 위에 훨씬 더 정교한 기능들을 얹고 있음
    • 색인 없이도 꽤 멀리 갈 수 있다는 점이 놀라웠음
      예를 들어 GritQL(https://github.com/getgrit/gritql)도 속도를 위해 결국 색인이 필요할 거라고 늘 생각했지만, 지금까지는 전부 즉석 검색만으로 꽤 버티고 있음
    • 여러 문제에 이 접근을 적용함. 상태를 가장 적게 두는 단순한 방식부터 하고, 속도를 위해 메모리 쪽으로 기울여야 한다는 걸 증명한 뒤에야 바꾸는 편임
      캐시가 없으면 올바르게 유지하기가 훨씬 단순함
    • 실제로 규모 있고 대표성 있는 작업 부하가 생긴 뒤라야 적절한 색인 방식을 고르기 훨씬 좋아짐
    • 시간형 데이터베이스를 만들던 누군가는 디스크 블록을 압축해두고 스트리밍으로 압축 해제하며 검색했음
      L2 캐시에 들어가는 것들은 정말 매우 빠르게 동작함

  • 코드 검색은 정말 어렵고, 좋은 코드 검색 플랫폼은 삶을 훨씬 편하게 해줌
    Google을 떠나게 된다면 내부 코드 검색이 가장 그리울 것 같음. blaze 대상 찾기, guice 바인딩 등 모든 작업 흐름과 너무 잘 통합돼 있어서, 없이는 일하는 모습을 상상하기 어려움. GitHub 검색을 쓸 때마다 그 가치를 더 크게 느끼는데, GitHub 검색이 나쁘다기보다 범용 코드 검색 플랫폼을 만드는 일이 본질적으로 훨씬 어렵기 때문임

    • 떠나게 되면 Google의 코드 검색 작업을 바탕으로 만든 Livegrep을 쓸 수 있음
      지금 개인적으로 쓰고 있지는 않지만 훌륭하고 대부분의 필요를 충족할 것 같음. https://github.com/livegrep/livegrep
    • guice 바인딩 계층 기능은 좋지만 UI는 더 나아질 수 있음
      검색창에서 바로 제공자나 사용 위치를 찾을 수 있으면 좋겠음

  • 기본적인 코드 검색 기술은 신입 개발자에게 명시적으로 잘 가르치지 않지만, 초기에 꼭 익혀야 하는 핵심 역량처럼 보임
    추천하는 흐름은 Ctrl+F처럼 어디서나 되는 검색을 익히고, 그다음 ripgrep(https://github.com/BurntSushi/ripgrep)으로 넘어가는 것임. 이건 선택사항이라기보다 정말 훌륭하고 발견하기 쉬운 도구이고, 터미널을 열어둬야 한다는 점도 초보자에게 오히려 좋음. 가능하면 강력한 명령줄 편집기 하나도 익히면 좋은데, 예전의 나는 Emacs를 권했겠지만 지금은 거의 어디에나 설치된 vim 기본판을 권함. 같은 창에서 grep하고 편집할 수 있기 때문임. 이어서 grep -r, grep -ri, grep -ril처럼 ripgrep이 기본으로 해주는 동작을 오래된 grep으로도 익히고, 마지막으로 ripgrep의 한계에 부딪히면 실제 색인 기반 전용 코드 검색 도구로 넘어가면 됨

    • VSCode의 검색 기능도 ripgrep을 사용하므로 좋은 출발점임
    • GitHub도 아직 클론하지 않은 저장소까지, 공개 저장소든 조직 저장소든 가로질러 코드 검색하기에 훌륭한 도구임
    • Git 저장소를 검색할 때 속도 말고 ripgrep이 git grep보다 어떤 장점이 있는지 궁금함

  • hound(https://github.com/hound-search/hound)가 언급되지 않은 게 놀라움
    이 분야의 오픈소스 해법 중 선두라고 생각했음. Wikimedia 인스턴스(https://codesearch.wmcloud.org/search/)를 써왔고 대체로 만족하고 있음

  • IDE와 개발자 도구를 만드는 사람들이 오래전부터 제대로 된 코드 검색을 하려면 컴파일러 플랫폼을 열어야 한다고 본 이유가 여기에 있음
    필요한 작업 상당수가 결국 컴파일러가 쓰는 내부 표현을 재구성하는 일이기 때문임. 좋은 코드 검색은 리팩터링 지원, 자동 완성, 흔한 IDE 기능들의 기반이기도 함. 물론 말처럼 쉽지는 않아서 컴파일러를 만드는 쪽에서는 도구가 뒷전인 경우가 많았고, JetBrains도 Kotlin 초기에 이 실수를 했으며 Kotlin 2.0에서 증분 컴파일 같은 지원을 쉽게 하려고 일부 바로잡는 중임. Rust 커뮤니티도 몇 년 전 IDE 친화성을 높이려는 큰 노력을 하며 같은 통찰을 얻었음. IBM은 예전 Eclipse에서 이걸 제대로 해냈고, 그 이후로는 잘 따라잡히지 않았음. IntelliJ는 2~3자릿수 정도 느려서 초 단위와 밀리초 단위 차이가 났음. Eclipse에는 문법 오류가 있어도 일부 컴파일 가능한 Java용 매우 빠른 증분 컴파일러가 있었고, IDE의 코드 표현이 그 컴파일러에 연결돼 있었음. 오타를 넣어 일부 코드를 깨면 코드베이스 전체에서 문제가 생긴 파일들이 즉시 빨간 밑줄로 표시되고, 오타를 고치면 지연 없이 사라졌음. 파일과 구문 트리 사이의 매핑이 있어야 가능한 일이고, Eclipse는 증분 컴파일러에 연결돼 있어서 그걸 해냈음. IntelliJ는 이걸 못 해서, 재빌드 전까지 정상/비정상 상태를 적극적으로 속이기도 하고 내부 상태가 디스크와 어긋나면 가짜 오류를 많이 보여줌. 실행하면 몇 초 동안 컴파일 지연이 있고, 그때서야 IDE가 실행 가능하다고 보여준 상태가 틀렸음을 알게 되는 경우가 있음. Eclipse에서는 컴파일러와 내부 상태를 공유했기 때문에 이 모든 게 즉각적이고 명확했음. 결점과 성가신 버그도 많았지만 그 기능은 그리움

    • 물론 Microsoft의 Roslyn(.NET 컴파일러)은 예외임
      https://willspeak.me/2021/11/24/red-green-syntax-trees-an-ov...
      https://ericlippert.com/2012/06/08/red-green-trees/
      Roslyn SDK로 도구를 만들어봤는데 정말 좋았음
    • Eclipse의 Java용 증분 컴파일러는 정말 대단하지만, Maven과 Gradle 같은 외부 빌드 시스템 통합과 여러 언어 지원이 더 나은 IntelliJ 쪽으로 결국 넘어가게 됐음
    • Eclipse에서는 여전히 즉각적이고 모호하지 않음
      많은 사람이 다른 IDE로 갈아타지 않는 주된 이유임

  • GitHub가 예전에는 a.toString()을 두 토큰으로 쪼개는 식으로 “고쳤던” 것 같은데, 그게 꽤 성가셨음
    GitHub가 IDE 같은 사용 위치 찾기를 강화하고는 있지만 아직 완벽하지 않아서, 놓친 사용처를 찾으려고 "foo.bar()" 같은 텍스트 검색을 하고 싶을 때가 있음. 그런데 이런 어간 처리 동작 때문에 foo와 bar가 따로 언급된 모든 위치까지 찾아 결과가 불어나버림

  • Zoekt를 대충 넘기는 게 이해되지 않음
    정확히 이 목적을 위해 만들어졌고, 다른 선택지보다 더 큰 새 인프라 부담도 아님. 서버도 단일 바이너리, 색인기도 단일 바이너리라 이보다 단순하기 어려움. Elasticsearch보다 Zoekt를 더 무서워할 이유가 없어 보임

  • 최근 본 코드 검색 접근 중 가장 흥미로운 것 중 하나는 septum임: https://github.com/pyjarrett/septum
    코드 검색을 제대로 만들 때 가장 어려운 부분은 적절한 양의 주변 문맥을 가져오는 일이라고 보는데, septum은 파일 단위로 이 문제를 풀려는 도구임. 또 언급되지 않아 놀란 것은 stack-graphs(https://github.com/github/stack-graphs)로, 코드베이스 전체의 기호 관계를 점진적으로 해석하려고 함. GitHub의 파일 간 정밀 색인을 구동하고 개념적으로도 타당하지만, 오픈소스 버전을 작동시키는 데는 어려움을 겪었음

  • Oracle에는 USER/ALL/DBA_SOURCE 뷰가 있고, 데이터베이스에 로드된 모든 PL/SQL(SQL/PSM) 코드가 거기에 나타남
    의도적으로 난독화하지 않았다면 모두 평문으로 보임. 소유자, 객체 이름, LINE[NUMBER], TEXT[VARCHAR2(4000)] 컬럼이 있고 저장된 소스 코드에 LIKE나 regexp_like()를 쓸 수 있음. EnterpriseDB가 Postgres 안에 이걸 구현했는지, 아니면 확장으로 제공되는지 궁금함. SQL/PSM 대부분이 어차피 Oracle에서 왔으니 당연히 바랄 만한 기능임. https://en.wikipedia.org/wiki/SQL/PSM

  • “GitHub 검색이 훌륭하다”고 했는데, 정말 그런가?
    대부분의 경우 거의 쓸모없게 느껴지고, 클론한 뒤 ripgrep을 쓰는 편이 훨씬 효율적임. 실제 검색보다는 UX가 끔찍한 게 문제일 수도 있음

답변달기