3GB SQLite → 10MB FST: 300배 메모리 절감, 핀란드어 사전 성능 혁신!
3GB SQLite 데이터베이스(Database)를 10MB FST(Finite State Transducer)로 대체하여 메모리 사용량 300배 절감
핀란드어 사전의 접두사 검색(Prefix Search)을 위해 FST를 활용, Trie의 한계를 극복
Rust를 사용하여 FST 구현, 성능 향상(Performance Improvement)과 배포 크기 감소 달성
SQLite FTS(Full Text Search)를 사용한 초기 구현의 단점과 FST 선택의 이유 설명
FST(Finite State Transducer)의 압축 원리
저자는 핀란드어 사전의 접두사 검색을 위해 FST를 활용하여 300배의 메모리 절감(Memory Reduction)을 달성했다. Trie는 접두사 공유(Prefix Sharing)를 통해 공간을 절약하지만, 접미사는 개별적으로 저장하는 반면, FST는 접미사 공유(Suffix Sharing)를 통해 압축률을 높인다. 특히 핀란드어처럼 다양한 어미 변화가 있는 언어에서 FST는 데이터 중복(Data Redundancy)을 효과적으로 제거하여 Trie보다 훨씬 작은 공간을 차지한다.
SQLite FTS(Full Text Search)의 한계와 FST 선택
초기 구현에서는 SQLite의 FTS를 사용하여 3GB의 데이터베이스를 사용했지만, 이는 배포 크기(Deployment Size)와 메모리 사용량(Memory Usage) 측면에서 비효율적이었다. FST는 정적 데이터(Static Data)에 최적화되어 런타임 시 데이터 로딩 오버헤드를 줄일 수 있다. 또한, FST는 Trie보다 압축률이 높아 메모리 제약(Memory Constraint)이 있는 환경에서 더 적합하다. 이러한 이유로 저자는 FST를 선택하여 성능을 개선했다.
Rust를 활용한 FST 구현
저자는 Rust를 사용하여 FST를 구현하여 성능(Performance)과 이식성(Portability)을 확보했다. Rust는 메모리 안전성(Memory Safety)과 성능을 모두 제공하며, 특히 리팩토링(Refactoring)과 유지보수(Maintenance) 측면에서 장점을 가진다. 또한, Rust는 정적 바이너리(Static Binary) 생성을 지원하여 배포를 간소화하고, 의존성 관리(Dependency Management)를 용이하게 한다. 이러한 특징은 FST 구현에 Rust를 선택한 주요 이유 중 하나이다.
개발 과정에서의 트레이드오프
저자는 초기 구현에서 SQLite FTS를 사용했지만, 이는 3GB의 데이터 다운로드(Data Download)를 필요로 했다. FST를 사용함으로써 메모리 사용량은 줄었지만, 구현에는 추가적인 시간과 노력이 필요했다. 저자는 빠른 프로토타입(Rapid Prototyping)을 위해 SQLite를 먼저 사용하고, 이후 Rust와 FST로 전환하는 반복적인 개발(Iterative Development) 방식을 선택했다. 이는 개발 과정에서 흔히 발생하는 트레이드오프(Trade-offs)를 보여주는 사례이다.
