A Tiny, Static, Full-Text Search Engine using Rust and WebAssembly

2019-10-17

Rust와 WebAssembly로 만드는 작고 정적인 전문 검색 엔진

정적 웹사이트에 추가해서 사용할 수 있는 기본적인 검색 모듈을 만들었습니다. 용량이 아주 작고( gzip으로 압축하면 50~100kB) Hugo, Zola, Jekyll에서 작동합니다. 지원하는 기능은 완전한 단어 검색뿐입니다. 왼쪽의 검색창에서 데모를 사용해 보세요. 코드는 Github에 있습니다.

정적 사이트 생성기는 정말 멋집니다. 성능을 희생하지 않으면서 동적인 콘텐츠를 제공해 두 세계의 장점을 결합하니까요.

지난 몇 년 동안 이 블로그는 Jekyll, Cobalt, 그리고 최근에는 Zola로 운영해 왔습니다.

하지만 늘 아쉬웠던 점은 정적 웹사이트에 정작 “정적” 검색 엔진은 함께 제공되지 않는다는 사실이었습니다. 대신 사람들은 Google 맞춤 검색, Algolia 같은 외부 검색 엔진, 또는 lunr.js나 elasticlunr 같은 순수 JavaScript 기반 솔루션을 사용합니다.

대부분의 사이트에서는 이 방법들이 잘 작동하지만, 이것이 최종적인 해답이라는 느낌은 들지 않았습니다.

Google에 의존성을 하나 더 추가하고 싶지도 않았습니다. 지연 시간을 늘리고 독점적인 stand-alone 웹 백엔드인 Algolia를 사용하고 싶지도 않았고요.

반대로 JavaScript를 많이 사용하는 웹사이트도 그다지 좋아하지 않습니다. 예를 들어 lunr이 생성하는 검색 인덱스만 해도 수 메가바이트에 달할 수 있습니다. 오늘날의 대역폭 기준으로 봐도 지나치게 호사스럽습니다. 게다가 JavaScript를 파싱하는 데는 여전히 시간이 걸립니다.

다른 정적 콘텐츠와 함께 배포할 수 있는 단순하고, 가볍고, 독립적인 검색 기능을 원했습니다.

결국 블로그에 검색 기능을 아예 추가하지 않았습니다. 글이 점점 많아지면서 관련 콘텐츠를 찾기가 갈수록 어려워진다는 점을 생각하면 아쉬운 일입니다.

아이디어

몇 년 전인 2013년에 Bloom 필터를 사용해 전문 검색 엔진 작성하기라는 글을 읽었는데, 정말 큰 깨달음을 얻었습니다.

아이디어는 간단했습니다. 내 블로그의 모든 글을 생성기에 통과시켜 ✨Bloom 필터✨라는 이 마법 같은 자료 구조를 사용해 작고 독립적인 검색 인덱스를 만드는 것입니다.

잠깐, Bloom 필터가 뭔가요?

Bloom 필터는 어떤 원소가 집합에 포함되어 있는지 확인할 때 공간을 효율적으로 사용하는 방법입니다.

핵심은 원소 자체를 저장하지 않는다는 것입니다. 대신 이전에 저장된 적이 있다는 사실을 어느 정도 확신할 수 있도록 기억합니다. 여기서는 특정 오류율을 감수하고 어떤 단어가 글에 포함되어 있는지 말해 줄 수 있습니다.

Bloom 필터는 원본 입력 대신 모든 입력값의 ‘지문’(여러 해시값)을 저장합니다. 그 결과 메모리 사용량이 작은 자료 구조가 됩니다. 다음은 ‘hello’를 입력값으로 사용한 예입니다.

다음은 각 글의 Bloom 필터를 생성하는 원문 글의 Python 코드입니다(Stavros Korokithakis 제공).

filters = {}
for name, words in split_posts.items():
  filters[name] = BloomFilter(capacity=len(words), error_rate=0.1)
  for word in words:
    filters[name].add(word)

error_rate 덕분에 메모리 사용량은 매우 작습니다. 오탐(false positive)을 무시해도 될 만큼만 허용하기 때문입니다.

홈페이지에도 이런 기능을 넣어야겠다는 생각이 바로 들었습니다. Bloom 필터와 검색 엔진을 브라우저에 직접 제공하는 것입니다. 드디어 백엔드 없이 작고 정적인 검색 기능을 가질 수 있겠다는 생각이 들었습니다!

골칫거리

하지만 곧 환상이 깨졌습니다.

생성된 Bloom 필터를 어떻게 묶고 최소화할지, 하물며 클라이언트에서 어떻게 실행할지 전혀 몰랐습니다. 원문 글에서는 이 문제를 짧게 언급합니다.

클라이언트 측에 Bloom 필터 알고리즘을 구현해야 합니다. 아마 역색인 검색 알고리즘보다 그리 길지는 않겠지만, 그래도 조금 더 복잡할 것입니다.

이 일을 해낼 만큼 JavaScript 실력에 자신이 없었습니다. 2013년 당시 NPM은 고작 세 살이었고 WebPack도 막 한 살이 된 때라, 기존 솔루션을 어디서 찾아야 할지도 몰랐습니다.

다음에 무엇을 해야 할지 몰랐던 탓에 이 아이디어는 실현되지 못한 꿈으로 남았습니다.

새로운 희망

5년 뒤인 2018년, 웹은 완전히 다른 곳이 되어 있었습니다. 번들러는 어디에나 쓰였고 Node 생태계는 번성하고 있었습니다. 특히 작고 정적인 검색 엔진에 대한 제 꿈을 되살린 것이 하나 있었는데, 바로 WebAssembly였습니다.

WebAssembly(줄여서 Wasm)는 스택 기반 가상 머신을 위한 이진 명령어 형식입니다. Wasm은 C/C++/Rust 같은 고급 언어를 컴파일하기 위한 이식 가능한 대상으로 설계되었으며, 클라이언트와 서버 애플리케이션을 웹에 배포할 수 있게 해 줍니다. [출처]

덕분에 익숙한 언어로 클라이언트 측 코드를 작성할 수 있었습니다. 바로 Rust입니다! 🎉

2018년 1월에 만든 프로토타입으로 여정을 시작했습니다. 위에서 본 Python 버전을 그대로 포팅한 수준이었습니다.

let mut filters = HashMap::new();
for (name, words) in articles {
  let mut filter = BloomFilter::with_rate(0.1, words.len() as u32);
  for word in words {
    filter.insert(&word);
  }
  filters.insert(name, filter);
}

각 글의 Bloom 필터를 만드는 데는 성공했지만, 웹에 어떻게 패키징해야 할지는 여전히 전혀 알 수 없었습니다. 그러다 2018년 2월에 wasm-pack이 등장했습니다.

이런, Rust 코드를 여러분의 브라우저에 배포해 버렸습니다.

이제 퍼즐의 모든 조각이 모였습니다.

Rust: 익숙하게 사용할 수 있는 언어
wasm-pack: WebAssembly 모듈용 번들러
개념 증명 역할을 하는 작동하는 프로토타입

이 페이지 왼쪽에 보이는 검색창이 그 결과물입니다. WebAssembly(즉, RAW 스택)를 사용해 전부 Rust로 실행됩니다. 원한다면 지금 사용해 보세요.

그 과정에서 장애물도 꽤 많았습니다.

Bloom 필터 크레이트

Bloom 필터를 구현한 Rust 라이브러리(크레이트)를 몇 가지 살펴봤습니다.

처음에는 jedisct1의 rust-bloom-filter를 사용해 봤지만, 타입에 Serialize/Deserialize가 구현되어 있지 않았습니다. 그래서 생성한 Bloom 필터를 바이너리 안에 저장하고 클라이언트 측에서 불러올 수 없었습니다.

몇 가지 다른 것을 시도한 끝에 직렬화를 지원하는 cuckoofilter 크레이트를 찾았습니다. 동작 방식은 Bloom 필터와 비슷하지만, 차이점이 궁금하다면 이 요약문을 참고하세요.

사용 방법은 다음과 같습니다.

let mut cf = cuckoofilter::new();

// Add data to the filter
let value: &str = "hello world";
let success = cf.add(value)?;

// Lookup if data was added before
let success = cf.contains(value);
// success ==> true

cuckoo 필터를 사용해 블로그의 글 10개에 대한 필터를 묶었을 때 출력 크기를 확인해 보겠습니다.

~/C/p/tinysearch ❯❯❯ l storage
Permissions Size User    Date Modified Name
.rw-r--r--   44k mendler 24 Mar 15:42  storage

44kB면 나쁘지 않아 보입니다. 하지만 이것은 Rust 바이너리로 직렬화한 글 10개의 cuckoo 필터일 뿐입니다. 여기에 검색 기능과 보조 코드를 추가해야 합니다. vanilla wasm-pack을 사용하면 클라이언트 측 코드의 전체 크기는 216kB에 달합니다. 너무 큽니다.

바이너리 크기 줄이기

처음 프로토타입의 결과가 216kB로 나온 뒤, 바이너리 크기를 줄일 방법을 몇 가지 찾았습니다.

첫 번째 방법은 johnthagen이 알려 준 Rust 바이너리 크기 최소화 방법을 따르는 것입니다.

Cargo.toml에 옵션을 몇 가지 설정하면 바이트를 꽤 줄일 수 있습니다.

"opt-level = 'z'" => 249665 bytes
"lto = true"      => 202516 bytes
"opt-level = 's'" => 195950 bytes

opt-level을 s로 설정하면 크기와 속도를 맞바꾸게 됩니다. 하지만 지금은 어쨌든 최소 크기가 우선입니다. 다운로드 크기가 작아지면 성능도 좋아지니까요.

다음으로 작은 .wasm 코드 크기를 만들어 내는 대체 Rust 할당자인 wee_alloc을 사용해 볼 수 있습니다.

처음에 크기가 동적으로 정해지는 메모리를 몇 차례 할당한 뒤, 추가 할당 없이 무거운 작업을 수행하는 코드를 대상으로 합니다. 이런 경우에도 할당자가 필요하지만, 작은 코드 크기를 위해 할당 성능을 기꺼이 포기할 수 있습니다.

바로 우리가 원하는 것입니다. 사용해 봅시다!

"wee_alloc and nightly" => 187560 bytes

바이너리에서 다시 4%를 줄였습니다.

호기심이 생겨 codegen-units를 1로 설정해 보았습니다. 코드 생성에 단일 스레드만 사용한다는 뜻입니다. 놀랍게도 바이너리 크기가 조금 더 작아졌습니다.

"codegen-units = 1" => 183294 bytes

그러다 binaryen이라는 Wasm 최적화 도구가 있다는 것을 알게 되었습니다. macOS에서는 homebrew로 설치할 수 있습니다.

brew install binaryen

이 도구는 wasm-opt이라는 바이너리를 제공하며, 이를 사용하자 크기가 다시 15% 줄었습니다.

"wasm-opt -Oz" => 154413 bytes

그다음 DOM에 바인딩할 필요가 없으므로 web-sys를 제거했습니다. 결과는 152858 bytes였습니다.

Wasm 바이너리의 코드 크기를 프로파일링하는 twiggy라는 도구도 있습니다. 다음과 같은 결과가 출력됩니다.

twiggy top -n 20 pkg/tinysearch_bg.wasm
 Shallow Bytes │ Shallow % │ Item
─────────────┼───────────┼────────────────────────────────
         79256 ┊    44.37% ┊ data[0]
         13886 ┊     7.77% ┊ "function names" subsection
          7289 ┊     4.08% ┊ data[1]
          6888 ┊     3.86% ┊ core::fmt::float::float_to_decimal_common_shortest::hdd201d50dffd0509
          6080 ┊     3.40% ┊ core::fmt::float::float_to_decimal_common_exact::hcb5f56a54ebe7361
          5972 ┊     3.34% ┊ std::sync::once::Once::call_once::{{closure}}::ha520deb2caa7e231
          5869 ┊     3.29% ┊ search

제가 보기에는 바이너리에서 가장 큰 부분을 차지하는 것은 글의 원시 데이터 섹션입니다. 그다음은 함수 헤더와 부동소수점을 10진수로 변환하는 보조 함수입니다. 아마 역직렬화 과정에서 들어온 것 같습니다.

마지막으로 wasm-snip도 사용해 봤습니다. 이 도구는 WebAssembly 함수의 본문을 다음과 같이 unreachable로 바꿔 줍니다. 하지만 코드 크기는 줄어들지 않았습니다.

wasm-snip --snip-rust-fmt-code --snip-rust-panicking-code -o pkg/tinysearch_bg_snip.wasm pkg/tinysearch_bg_opt.wasm

cuckoo 필터의 매개변수를 조금 조정하고 글에서 불용어를 제거한 결과, 최종 크기는 121kB(gzip 압축 시 51kB)가 되었습니다. 웹에서 이미지 하나의 평균 크기가 약 900kB라는 점을 생각하면 나쁘지 않습니다. 게다가 검색 기능은 사용자가 검색창을 클릭할 때만 로드됩니다.

업데이트

최근에 프로젝트를 cuckoofilter에서 XOR 필터로 옮겼습니다. 기본적으로 serde 직렬화를 지원하는 훌륭한 xorf 프로젝트를 사용했는데, 덕분에 커스텀 코드를 상당 부분 제거할 수 있었습니다.

그 결과 페이로드 크기를 다시 20~25% 줄일 수 있었습니다. 이제 제 블로그의 크기는 99kB(gzip 압축 시 49kB)까지 내려갔습니다. 🎉

새 버전은 이미 crates.io에 공개되어 있으니, 원한다면 사용해 보세요.

프런트엔드 및 접착 코드

wasm-pack은 Wasm과 통신하는 JavaScript 코드를 자동으로 생성합니다.

검색 UI에는 w3schools의 JavaScript와 CSS 일부를 수정해 사용했습니다. 키보드도 지원합니다! 사용자가 검색어를 입력하면 각 글의 cuckoo 필터를 순회하면서 단어가 일치하는지 확인합니다. 결과는 일치한 단어 수로 점수를 매깁니다. 이 부분을 추가해 준 사랑하는 동료 Jorge Luis Betancourt에게 감사드립니다.

(재미있는 사실: 이 애니메이션의 크기는 압축하지 않은 Wasm 검색 기능 자체의 크기와 거의 같습니다.)

주의할 점

일치하는 것은 완전한 단어뿐입니다. 접두사 검색도 추가하고 싶지만, 시도해 보니 바이너리가 너무 커졌습니다.

사용법

Wasm 파일을 만드는 독립 실행형 바이너리의 이름은 tinysearch입니다. 입력으로 JSON 파일의 경로 하나를 받습니다.

tinysearch path/to/corpus.json

이 corpus.json에는 색인으로 만들 텍스트가 들어 있습니다. 형식은 매우 간단합니다.

[
  {
    "title": "Article 1",
    "url": "https://example.com/article1",
    "body": "This is the body of article 1."
  },
  {
    "title": "Article 2",
    "url": "https://example.com/article2",
    "body": "This is the body of article 2."
  }
]

이 JSON 파일은 어떤 정적 사이트 생성기로든 만들 수 있습니다. 다음은 제가 Zola용으로 만든 버전입니다.

{% set section = get_section(path="_index.md") %}

[
  {%- for post in section.pages -%}
    {% if not post.draft %}
      {
        "title": {{ post.title | striptags | json_encode | safe }},
        "url": {{ post.permalink | json_encode | safe }},
        "body": {{ post.content | striptags | json_encode | safe }}
      }
      {% if not loop.last %},{% endif %}
    {% endif %}
  {%- endfor -%}
]

Jekyll 버전도 상당히 비슷할 것이라고 확신합니다. 여기서 시작해 보세요. 여러분의 정적 사이트 생성기에서 작동하는 것을 만들었다면 제게 알려 주세요.

관찰한 점

아직은 완전히 개척되지 않은 분야입니다. 불안정한 기능, nightly Rust, 거의 매일 낡아 가는 문서가 기다리고 있습니다.
머리를 단단히 굴려야 합니다!
좋은 아이디어를 제품으로 만드는 일은 상당히 많은 작업을 필요로 합니다. 사용 편의성, 범용성, 유지 보수성, 문서화 등 많은 요소에 신경 써야 합니다.
Rust는 사용하지 않는 코드를 제거하는 데 매우 뛰어나므로, 대개 사용하지 않는 기능의 비용까지 치르지는 않습니다. 그래도 Wasm 바이너리에 추가하는 의존성에는 매우 보수적인 태도를 권합니다. 필요하지 않은 기능을 추가하고 그로 인해 바이너리 크기가 커지기 쉽기 때문입니다. 예를 들어 테스트 중에는 StructOpt를 사용했고, 명령줄 인자를 파싱하는 main() 함수도 있었습니다. Wasm에는 필요하지 않은 코드였기에 나중에 제거했습니다.
모든 사람이 Rust 코드를 작성하고 싶어 하는 것은 아니라는 점을 이해합니다. 시작하기가 복잡한 언어이긴 하지만, 멋진 점은 거의 모든 다른 언어도 사용할 수 있다는 것입니다. 예를 들어 Go 코드를 작성해 Wasm으로 변환할 수도 있고, PHP나 Haskell을 선호할 수도 있습니다. 이미 많은 언어가 지원됩니다.
WebAssembly를 장난감 기술로 치부하는 사람도 많습니다. 하지만 사실은 정반대입니다. 제 생각에 WebAssembly는 웹과 그 너머를 위한 제품을 만드는 방식을 혁신할 것입니다. 불과 2년 전만 해도 매우 어려웠던 일이 이제는 쉬워졌습니다. 어떤 언어로 작성한 코드든 모든 브라우저에 배포할 수 있게 된 것입니다. 앞으로가 정말 기대됩니다.
회사 웹사이트에 사용할 독립 실행형 자체 호스팅 검색 인덱스를 찾고 있다면 sonic을 확인해 보세요. 대안으로 stork도 살펴보세요.

사용해 보세요!

tinysearch의 코드는 Github에 있습니다.

다음과 같은 제한 사항에 유의하세요.

완전한 단어만 검색합니다. 검색어 제안은 없습니다. 접두사 검색을 지원하면 바이너리 크기가 Mentos와 Diet Coke처럼 폭발적으로 커지기 때문입니다.
모든 글의 검색 인덱스를 하나의 정적 바이너리에 묶기 때문에 작거나 중간 규모의 웹사이트에서만 사용하는 것을 권장합니다. 글 하나당 압축하지 않은 상태로 약 4kB 정도가 추가된다고 보면 됩니다.
현재는 컴파일 시간이 끔찍할 정도로 깁니다(제 컴퓨터에서는 새로 설치한 뒤 약 1.5분). 인덱스를 다시 만들 때마다 Rust 크레이트를 처음부터 컴파일하기 때문입니다.
업데이트: CephalonRho가 PR #13에서 훌륭한 작업을 해 준 덕분에 이 문제는 대부분 해결되었습니다. 다시 한번 감사드립니다!

최종 Wasm 코드는 검색 서버와 주고받는 왕복 통신을 없앴기 때문에 번개처럼 빠릅니다. 즉각적인 피드백을 받다 보니 글을 검색한다기보다 목록을 필터링하는 느낌에 가깝습니다. 완전히 오프라인으로도 작동하므로 앱에 함께 넣고 싶을 때 유용할 수 있습니다.