저는 서버 없이 작동하는 시맨틱 검색 (semantic search)을 원했습니다. "작은 서버"가 아니라, 서버가 아예 없는 것 말입니다. 벡터, 인덱스, 그리고 쿼리가 모두 브라우저 탭 안에 존재하며, 기기 외부로 아무것도 나가지 않고 오프라인으로 작동하는 방식입니다. 계획은 지루하지만 확실한 방법이었습니다. Rust로 작성된 빠른 코어를 WebAssembly (Wasm)로 컴파일하고, 이를 일반적인 JavaScript API로 감싸는 것이었습니다. 이는 실제로 출시된 모든 WebAssembly 앱의 공통된 패턴입니다.

그 후 바로 사용할 수 있는 Rust HNSW 크레이트 (crate)를 찾아보았지만, 성숙한 라이브러리들은 모두 wasm32-unknown-unknown으로의 컴파일을 거부했습니다. 그들은 rayon, mmap-rs, 또는 num_cpus에 강하게 의존하고 있었습니다. 서버에서는 합리적인 선택이지만, 스레드를 포크(fork)할 수 없고, 메모리 맵(memory-map)할 파일이 없으며, 개수를 셀 CPU가 없는 브라우저 환경에서는 넘을 수 없는 벽이었습니다. 그래서 직접 만들었습니다. ferrovec는 그 결과물입니다. 다른 것들이 들어갈 수 없는 곳에 들어갈 수 있다는 점이 존재 이유인, 매우 작고 의존성이 적은 근사 최근접 이웃 (approximate-nearest-neighbor) 인덱스입니다.

그것은 무엇인가

ferrovec는 직접 구현한 HNSW 벡터 인덱스입니다. 이는 Pinecone, Weaviate, Qdrant의 기반이 되는 것과 동일한 근사 최근접 이웃 (approximate-nearest-neighbor) 알고리즘인 Hierarchical Navigable Small World를 의미합니다. 이 프로젝트는 두 레지스트리에 모두 0.3.1 버전으로 올라갔습니다. Rust 코어는 crates.io에, 전체 브라우저 패키지는 npm에 등록되었습니다. 설계 제약 조건은 의도적으로 매우 엄격하게 설정되었습니다:

• 초경량 (Featherweight). Rust 코어의 유일한 의존성(dependencies)은 serde와 postcard뿐입니다. WASM 빌드 크기는 gzipped 기준 약 33 KB로 보고되었습니다.

• unsafe 사용 제한. 검증된 단 하나의 SIMD 커널을 제외하고는 unsafe를 사용하지 않습니다. 크레이트(crate) 전체에 #![deny(unsafe_code)]가 적용되어 있으며, 유일한 예외는 범위가 지정되고 안전성 주석이 달린 SIMD128 경로입니다.

• 시스템 난수 미사용. 결정론적인 시드 기반의 splitmix64 PRNG(의사 난수 생성기)를 사용하므로 의존성 트리 내에 getrandom이 없습니다. 이것이 바로 별도의 심(shim) 없이 wasm32-unknown-unknown 타겟에서 실행될 수 있는 핵심 이유입니다.

• 점진적(Incremental) 및 이식성. Upsert 방식의 삽입, 툼스톤(tombstoning) 방식의 삭제, 그리고 버전화된 헤더를 포함한 컴팩트한 바이너리 포맷을 지원합니다. 동일한 바이트를 네이티브 환경이나 브라우저에서 그대로 다시 로드할 수 있습니다.

ferrovec 코어 — wasm32로 컴파일됨
serde
postcard
의존성 2개, 총합

• gzipped 기준 약 33 KB의 WASM 빌드 크기 보고 · 전체 ANN(근사 최근접 이웃) 엔진

성숙한 HNSW 크레이트들이 사용하는 것 — 하지만 브라우저에서는 실행할 수 없는 것
rayon
mmap-rs
num_cpus
✗ wasm32 백엔드 없음

Rust 코어는 serde와 postcard 외에는 아무것도 의존하지 않으며, WASM 빌드 크기는 gzipped 기준 약 33 KB로 보고되었습니다. 성숙한 HNSW 크레이트들은 rayon, mmap-rs, 또는 num_cpus를 사용하지만, 이들 중 어느 것도 wasm32-unknown-unknown 백엔드를 지원하지 않기 때문에 브라우저에서 실행할 수 없습니다.

다음은 Rust 코어의 학습 곡선(learning curve) 전체입니다:

use ferrovec::{Hnsw, Metric, Config};

let mut index = Hnsw::new(4); // 4차원, 기본값은 Cosine
...

search 함수는 가장 가까운 것부터 Neighbor { id, distance } 값을 반환합니다. 세 가지 메트릭(metrics)을 사용할 수 있으며, 모두 _값이 작을수록 더 가깝다_는 방식으로 표현됩니다:

HNSW가 모든 벡터를 확인하지 않고 이웃을 찾는 방법

ANN (Approximate Nearest Neighbor) 인덱스가 빠른 이유는 쿼리(query)를 전체 데이터셋과 대조하여 점수를 매기지 않기 때문입니다. HNSW는 그래프의 계층 구조 (hierarchy of graphs)를 구축합니다. 최하위 레이어 (bottom layer)는 모든 노드를 보유하며, 이웃들과 밀접하게 연결되어 있습니다. 그 위의 각 레이어는 더 희소한 샘플 (sparser sample)로, 노드 수는 더 적고 이동 거리 (hops)는 더 깁니다. 이는 마치 로컬 도로 위에 쌓인 급행 차선 (express lane)과 같습니다. 검색은 최상단에서 시작하여, 해당 레이어에서 더 이상 가까워질 수 없을 때까지 쿼리를 향해 탐욕적 (greedily)으로 이동한 다음, 한 단계 아래 레이어로 내려가 이 과정을 반복합니다. 밀도가 높은 최하위 레이어에 도달할 때쯤이면 이미 올바른 이웃 지역 (neighborhood)에 도착해 있으므로, 소수의 로컬 비교 (local comparisons)만 남게 됩니다.

Layer 2 · sparse · entry
Layer 1
Layer 0 · every node · dense

enter here
nearest

쿼리는 희소한 최상단 레이어에서 진입하여 타겟을 향해 탐욕적으로 점프한 다음, 레이어를 하나씩 내려가 밀도가 높은 레이어 0에 도달하여 가장 가까운 이웃 (nearest neighbor)에 안착합니다. 전체 집합이 아니라 추적된 노드들만이 점수 계산 대상이 됩니다.

ferrovec의 핵심은 700줄이 채 되지 않는 단일 파일인 hnsw.rs입니다. 노드들은 레이어별 이웃 리스트를 보유하며, 후보 큐 (candidate queues)는 f32::total_cmp를 사용하여 거리순으로 정렬되므로 잘못된 NaN 값이 힙 (heap)을 망가뜨리는 일이 발생하지 않습니다. 사용자는 Config를 통해 그래프를 조정할 수 있습니다:

let index = Hnsw::with_config(128, Config {
 max_connections: 16, // M — 레이어당 노드별로 유지되는 이웃 수
 ef_construction: 200, // 구축 중 후보 리스트 (candidate-list) 크기
...

이 세 가지 조절 장치가 재현율 (recall) 대 속도 (speed)를 결정하는 전체 다이얼입니다. M과 ef 값이 커질수록 그래프가 더 조밀해지고 더 많은 후보를 검토하게 되며, 이는 더 나은 재현율을 의미하지만 더 많은 연산량을 요구합니다. 레이어 0은 최대 2 × M개의 연결을 허용하며, 이는 표준적인 HNSW 비대칭성 (asymmetry)을 따릅니다.

결정론 (Determinism)은 세부 사항이 아니라 기능입니다

대부분의 인덱스 라이브러리는 각 새로운 노드에 최상위 레이어를 할당하기 위해 운영체제의 난수 소스 (random source)를 사용합니다. 그 단 한 번의 호출이 브라우저 타겟을 위한 컴파일을 불가능하게 만듭니다. getrandom은 사용자가 직접 연결해야 하는 JavaScript 심 (shim) 없이는 wasm32-unknown-unknown 백엔드를 지원하지 않기 때문입니다. ferrovec은 Config::seed로부터 시드(seed)를 받는 자체 splitmix64 PRNG (의사 난수 생성기)를 탑재함으로써 이 문제 전체를 우회합니다. 의존성 트리 어디에도 getrandom은 존재하지 않습니다.

이로 인한 이점은 이식성보다 더 큽니다. 난수가 시드화되어 있기 때문에, 빌드는 재현 가능 (reproducible) 합니다. 동일한 시드와 동일한 순서로 동일한 벡터를 삽입하면, 여러분의 노트북과 사용자의 브라우저에서 바이트 단위로 일치하는 그래프를 얻을 수 있습니다. 이 속성이 바로 다음 기능을 정직하게 만들어 주는 핵심입니다.

삭제 (Removals), 툼스톤 (tombstones), 그리고 메모리 회수

탐색 가능한 그래프 (navigable graph)에서 노드를 삭제하는 것은 진정으로 까다로운 작업입니다. 노드를 뽑아내면 다른 노드들이 도달 가능성을 유지하기 위해 의존했던 경로가 끊어질 수 있기 때문입니다. ferrovec은 실용적인 방식을 취합니다. remove (그리고 기존 ID에 새로운 벡터를 upsert 하는 작업)는 노드를 단지 툼스톤 (tombstone, 논리적 삭제) 처리할 뿐입니다. 노드는 연결성을 위해 그래프에 남아 있지만, 모든 결과에서 필터링됩니다. 정확하면서도 비용이 저렴합니다. 문제는 빈번한 변경 (churn)이 발생하면 어떤 쿼리도 반환하지 않을 죽은 노드들로 인해 메모리가 서서히 증가한다는 점입니다.

따라서 살아있는 벡터들로만 인덱스를 제자리에서 재구축하는 compact 기능이 있으며, 여기서 결정론 (determinism)의 진가가 발휘됩니다. 재구축하기 전에 PRNG를 Config::seed로 되돌리기 때문에, 압축된 인덱스는 동일한 순서로 삽입된 동일한 생존자들을 새로 빌드한 것과 바이트 단위로 완전히 일치합니다.

index.remove("drop"); // 툼스톤 처리됨 — 여전히 메모리를 점유 중
index.compact(); // 살아있는 노드로만 재구축; PRNG가 시드로 되돌아감

...

compact() 호출 전 — 살아있는 노드 3개, 툼스톤 5개 (여전히 메모리 사용 중)

compact() 실행
PRNG가 시드로 되돌아감 → 생존자들을 새로 빌드한 것과 동일함

compact() 호출 후 — 살아있는 노드 3개, 메모리 회수됨

툼스톤 제거 · len()은 변경되지 않음

노드를 삭제하거나 업데이트(upserting)할 때 툼스톤(tombstone)만 삽입합니다 — 이는 그래프의 연결성을 유지하지만 메모리에 남아 있게 됩니다. compact()는 살아있는 노드들로만 다시 빌드하며, PRNG(의사 난수 생성기)를 시드(seed)로 되돌려 결과가 생존자들만으로 새로 빌드한 것과 동일하게 바이트 단위로 일치하도록 합니다. (표시된 수치는 예시입니다.)

동일한 바이트, 네이티브 또는 브라우저

지속성(Persistence)은 버전 정보가 포함된 헤더를 가진 컴팩트한 이진 형식(binary format)입니다 — 4개의 매직 바이트(magic bytes) FVEC, 그 다음 포맷 버전, 그 다음 페이로드(payload) 순서로 구성됩니다. to_bytes는 Vec<u8>를 반환하며, from_bytes는 이를 복구합니다. 버전 정보가 포함된 헤더를 사용하는 이유는 지루하지만 중요한 이유 때문입니다: 동일한 직렬화된 인덱스를 네이티브 환경 또는 브라우저에서 동일하게 다시 로드할 수 있으며, 향후 포맷이 변경되었을 때 조용히 잘못 읽히는 대신 이를 감지할 수 있습니다.

let bytes = index.to_bytes().unwrap(); // FVEC 헤더 + 페이로드
let restored = Hnsw::from_bytes(&bytes).unwrap();
// restored.search(...) == index.search(...)

F V E C
매직(magic) · 4 바이트

version = 1
u32 · 4 바이트

payload — postcard로 인코딩된 그래프
노드(nodes) · 레이어별 이웃(per-layer neighbors) · ID

버전 정보가 포함된 헤더 ⇒ 동일한 바이트를 네이티브 또는 브라우저에서 다시 로드할 수 있으며, 포맷 변경 시 잘못 읽히지 않고 감지됩니다.
직렬화된 인덱스는 4개의 매직 바이트인 FVEC로 시작하여, 32비트 포맷 버전, 그 다음 postcard로 인코딩된 페이로드가 이어집니다. 버전 정보가 포함된 헤더는 동일한 바이트를 네이티브 또는 브라우저에서 다시 로드할 수 있게 해주며, 향후 포맷 변경 시 조용히 잘못 읽히는 대신 이를 감지할 수 있게 해줍니다.

SIMD 커널, 그리고 unsafe가 허용되는 단 한 곳

거리(Distance) 계산은 ANN (Approximate Nearest Neighbor) 인덱스가 수행하는 모든 작업의 내부 루프이므로, 수동으로 최적화할 가치가 있는 유일한 부분입니다. ferrovec는 항상 사용 가능한 정확성 참조(correctness reference)로서 스칼라 dot 및 제곱-L2 (squared-L2) 함수를 유지합니다. wasm32 + simd128 환경에서는 공개 디스패치(public dispatch)가 네 개의 독립적인 레인(lane)에서 누적한 뒤 마지막에 이를 접는(fold) 수동 작성된 SIMD128 커널로 교체됩니다. 그리고 이 커널은 크레이트(crate) 내에서 unsafe 사용이 허용된 유일한 코드이며, 안전성 주석과 함께 범위가 지정된 #[allow(unsafe_code)] 하에 동작합니다. 그 외의 모든 코드는 크레이트 전역의 deny 설정 하에 관리됩니다.

4-레인 누적 방식은 엄격한 왼쪽에서 오른쪽 방향의 스칼라 합과 비트 단위로 일치하지는 않습니다. IEEE-754 표준 하에서 두 방식은 마지막 자리(last place)에서 몇 단위(unit) 정도 차이가 날 수 있습니다. 이 점이 우려될 수 있으므로, 이 크레이트는 이를 명확히 규정합니다. wasm 통합 테스트를 통해 search가 스칼라 브루트 포스(brute-force) 방식으로 병행 계산된 결과와 동일한 최근접 ID를 반환하는지 확인합니다. 미세한 ULP (Unit in the Last Place)의 흔들림이 승자를 바꾸지는 않습니다.

브라우저로의 진입

Rust 코어는 wasm-bindgen을 통해 FerrovecCore 클래스를 노출합니다. wasm-pack으로 빌드된 이 클래스는 저수준 인터페이스(low-level surface) 역할을 하며, 사용자는 Float32Array 형태로 직접 임베딩(embeddings)을 가져와야 합니다:

import { FerrovecCore } from "ferrovec";

const index = new FerrovecCore(384); // 384차원 벡터
...

이는 강력하지만 여전히 사용자가 직접 임베딩을 생성해야 한다는 요구사항이 있습니다. npm 패키지는 그 간극을 메워줍니다. wasm 코어 위에 transformers.js를 통한 자동 임베딩, 메인 스레드에서 실행되지 않도록 하는 전용 Web Worker, 그리고 OPFS (Origin Private File System) 지속성(persistence) 레이어를 쌓아 올렸으며, API는 단 세 줄로 압축됩니다:

import { Ferrovec } from "ferrovec";

const db = await Ferrovec.open("notes"); // 워커를 생성하고 모델을 로드합니다
...

텍스트를 입력하면 탭 내부에서 완전히 임베딩, 인덱싱 및 검색이 이루어집니다. 각 검색 결과(hit)는 원문 텍스트와 함께 값이 높을수록 더 가까운 것을 의미하는 코사인 유사도(cosine-similarity) score를 반환합니다. 이 코드 스니펫에는 네트워크 호출이 없으며, 그 반대편에 서버도 존재하지 않습니다.

새로고침 생존 — 그리고 두 번째 탭에서의 생존

기본적으로 인덱스는 Origin Private File System (OPFS)에 영구 저장되므로 페이지가 종료되어도 유지됩니다. 워커(Worker)는 FileSystemSyncAccessHandle을 통해 ferrovec/<name>/index.bin을 열며, 쓰기 작업은 약 250ms 간격으로 디바운스(debounced)된 전체 스냅샷(full snapshots) 방식으로 이루어집니다. 각 삽입(insert) 또는 삭제(remove)는 저장소를 더티(dirty) 상태로 표시하고 단일 write-truncate-flush 작업을 예약하며, close()는 제어권을 놓기 전 마지막 동기식 플러시(synchronous flush)를 강제합니다. 동기식 액세스(sync access)를 사용할 수 없는 경우(Node.js, 보안되지 않은 컨텍스트, 지원되지 않는 브라우저 등)에는 충돌하는 대신 조용히 인메모리(in-memory) 방식으로 전환됩니다.

insert / remove
mark dirty
debounce ~250 ms
write @ 0 · truncate · flush
close() ⇒ final synchronous flush

OPFS 영속성 — 전체 스냅샷 쓰기 경로

각 삽입 또는 삭제는 저장소를 더티(dirty) 상태로 표시하고 약 250ms 후에 단일 스냅샷 작업을 예약합니다(offset 0에서 쓰기, truncate, flush). 따라서 일시적인 쓰기 폭주(burst of writes)가 발생하더라도 여러 번의 디스크 쓰기 대신 단 한 번의 디스크 쓰기로 압축됩니다. close()는 잠금(lock)을 해제하기 전 마지막 동기식 플러시를 강제합니다.

그다음은 실제 사용 환경에서만 나타나는 문제가 있습니다. 사용자가 앱을 두 번째 탭에서 여는 경우입니다. 두 개의 워커가 하나의 OPFS 파일을 공유하게 됩니다. 초기 버전에서는 두 번째 탭이 조용히 자체적인 인메모리 복사본으로 포크(fork)되었고, 이로 인해 두 탭 사이의 데이터가 어긋나며 두 번째 탭의 쓰기 작업이 디스크에 도달하지 못하는 문제가 발생했습니다. 0.3.x 버전에서의 해결책은 분산 시스템(distributed-systems)의 적절한 해답인 단일 작성자 리더 선출 (single-writer leader election) 방식입니다.

Tab A — 리더 (leader)
Web Lock 보유
Engine + 인덱스 소유
OPFS 스냅샷 쓰기

OPFS · index.bin

Tab B — 팔로워 (follower)
로컬 인덱스 없음
리더에게 프록시(proxies)

Tab C — 팔로워 (follower)
로컬 인덱스 없음
리더에게 프록시(proxies)

BroadcastChannel · ferrovec-coord:notes

각 탭의 워커(worker)는 ferrovec-leader:라는 이름의 독점적인 Web Lock을 요청합니다. 승자가 OPFS 파일을 소유하며 유일한 엔진(engine)이 됩니다. 나머지 탭들은 팔로워(followers)가 되어 BroadcastChannel을 통해 삽입(insert)/쿼리(query)/삭제(remove) 호출을 리더(leader)에게 프록시(proxy)합니다. 단 하나의 권위 있는 인덱스(authoritative index)만 존재하므로, 어떤 탭도 데이터가 어긋나지 않습니다.