# 3GB SQLite 데이터베이스를 10MB FST(유한 상태 변환기) 바이너리로 교체하기

> Clean Markdown view of GeekNews topic #29379. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=29379](https://news.hada.io/topic?id=29379)
- GeekNews Markdown: [https://news.hada.io/topic/29379.md](https://news.hada.io/topic/29379.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2026-05-11T15:02:24+09:00
- Updated: 2026-05-11T15:02:24+09:00
- Original source: [til.andrew-quinn.me](https://til.andrew-quinn.me/posts/replacing-a-3-gb-sqlite-database-with-a-7-mb-fst-finite-state-trandsucer-binary/)
- Points: 1
- Comments: 1

## Topic Body

- **Taskusanakirja**는 입력 중 접두사 검색을 제공하는 핀란드어-영어 사전임
- 핀란드어 굴절형 확장으로 항목이 **4천만~6천만 개**까지 늘어 트라이가 한계에 닿음
- 임시 **SQLite FTS** 해법은 빨랐지만 최초 3GB 다운로드가 필요했음
- Rust 기반 **FST**가 SQLite 데이터를 약 10MB 바이너리로 줄여 300배 절감함
- FST는 접두사와 **접미사**를 함께 공유해 반복 굴절 패턴에 잘 맞음

---

### Taskusanakirja의 검색 구조와 초기 한계
- [Taskusanakirja](https://taskusanakirja.com/), 줄여서 `tsk`는 **핀란드어-영어 사전**이며, 입력하는 동안 점진적으로 검색되는 기능을 제공함
- 이 기능은 기본적으로 [접두사 검색](https://en.wikipedia.org/wiki/Trie) 문제이며, 자동완성용 접두사 검색의 정석적 해법은 [트라이](https://www.baeldung.com/cs/tries-prefix-trees) 구현이었음
- 첫 구현은 **Go**로 작성됐고, 전체 프로그램을 하나의 `.exe`, 하나의 `.app`, 또는 하나의 정적 링크 바이너리로 배포하는 것이 초기 설계 목표였음
- 중간 6자리 규모의 단어 수에서 일부 단일 자리 퍼센트에 해당하는 항목까지 모두 매칭하지 않도록, 처음 50개 또는 100개 정도의 결과만 반환하고 1·2·3글자 조합을 메모이제이션함
- 이 방식으로 약 **60MB** 공간 안에 기본 최적화를 적용한 트라이를 넣을 수 있었고, 1년간 개인적으로 많이 사용해도 체감 지연이 없었음

### 핀란드어 굴절 데이터가 만든 규모 문제
- 핀란드어는 [교착어](https://en.wikipedia.org/wiki/Agglutinative_language)라서, 하나의 기본 단어가 모든 조합을 고려하면 **100개가 넘는 어미**를 가질 수 있음
- 조합은 규칙적이지 않으며, 매우 규칙화된 핀란드어 표기법은 실제 화자가 말하는 형태를 글에 그대로 반영하게 만들어 기본 단어가 어미와 결합하며 늘어나고, 이동하고, 변형됨
- 초급 학습자는 “`Opiskelijassammekin on leijonan sydän`” 같은 문장에서 특정 단어에 막히기 쉬우며, `tsk`는 단어를 올바른 경계에서 나누도록 돕는 정보도 담으려 했음
- 언어학적으로 이런 변형은 [자음 교체](https://en.wikipedia.org/wiki/Consonant_gradation)와 [모음 조화](https://en.wikipedia.org/wiki/Vowel_harmony)에 해당하며, 핀란드어는 둘을 동시에 사용함
- 예를 들어 `katu`는 “street”를 뜻하지만, 소유격은 `katun`이 아니라 `kadun`이며, 닫힌 음절 때문에 `t`가 `d`로 약화됨
- 이 구조를 **15개 격**, 2개 복수, 6개 소유 접미사, 불확정 수의 접어까지 곱하면, 순진한 트라이는 `-ssa-mme-kin`처럼 수천 개 단어가 공유하는 끝부분의 비용을 나눠 가질 수 없음
- 약 **40만 개 항목**은 트라이로 약 50MB RAM에 유지할 수 있었지만, 같은 방식은 4천만~6천만 개 항목으로 확장되지 않았음
- 임시 해법으로 굴절형을 별도의 **SQLite FTS** 데이터베이스에 넣고 필요할 때 검색하게 했으며, 체감 지연 없이 동작했지만 최초 1회 **3GB 다운로드**가 필요했음

### Rust와 FST로 바꾼 결과
- 9개월 뒤 Rust로 다시 시도하면서, 3GB SQLite 데이터베이스에서 데이터를 꺼내 **FST**로 압축하는 최소 Rust 프로그램을 작성함
- 계기는 [BurntSushi aka Andrew Gallant](https://github.com/BurntSushi)의 글 [Index 1,600,000,000 Keys with Automata and Rust](https://burntsushi.net/transducers/)였으며, 유한 상태 기계가 문자열의 정렬된 집합이나 맵을 작고 빠르게 표현할 수 있다는 점이 핵심이었음
- 결과 바이너리는 약 **10MB**가 되었고, 3GB SQLite 데이터베이스 대비 약 300배 공간을 절감함
- 이 용도는 [fst crate](https://docs.rs/fst/)에도 특히 잘 맞았는데, 고도로 교착적인 언어의 굴절형과 활용형을 원래 정의로 되돌려 매핑하는 문제였기 때문임
- 트라이는 **접두사**를 압축하지만, FST는 접두사와 **접미사**를 모두 압축함
- 핀란드어 사전 말뭉치에는 매우 자주 반복되는 인기 접미사가 소수 존재하므로, 접미사 공유가 큰 효과를 냄
- 데이터는 실행 중 변경되지 않는 **정적 데이터**라서, `fst`의 가장 큰 약점을 피할 수 있었음

### FST가 트라이보다 작아진 이유
- FST를 트라이보다 자연어 데이터에서 훨씬 작게 만드는 핵심은 **접미사 공유**임
- 트라이는 `kadun`과 `kaduille`가 앞의 세 노드를 공유하는 식으로 접두사를 공유하지만, 서로 다른 접미사 경로는 각각 별도로 저장함
- [최소 비순환 결정적 유한 상태 오토마톤](https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton)은 구조적으로 동일한 두 하위 트리를 병합함
- 10만 개 단어가 같은 12개 정도의 굴절 패턴으로 끝나는 말뭉치에서는, 이 병합이 큰 메모리 절감으로 이어짐
- 이 사례의 핵심 휴리스틱은 즉석에서 만든 범용 데이터베이스를, 정확히 필요한 일만 수행하는 작고 정적인 특수 자료구조로 교체해 **300배 메모리 절감**을 얻는 것임

### 임시 SQLite 해법이 남긴 역할과 배포 크기
- 9개월 전의 SQLite 선택은 “좋은 것을 못 하는 것”보다 “나쁘지만 쉬운 것”을 택한 결과였고, 실제로 동작했음
- SQLite의 B-tree와 [Full Text Search extension](https://www.sqlite.org/fts5.html)을 이해하고 있었기 때문에 당시에는 빠르게 실험 가능한 해법이었음
- 같은 FTS 확장은 `tsk v2.0.0` 알파에 없는 덜 쓰이는 일부 기능에도 쓰였지만, 현재의 메모리 풋프린트를 해친다면 완전히 제거될 가능성이 있음
- `v2`의 Pro 버전은 모든 것을 포함해 약 **20MB**로 잡히고 있으며, 이는 `v1` 무료 버전보다 3배 작음
- `tsk`는 원래 TUI Go 프로그램으로 시작했고, 이전의 `fzf` 기반 프로토타입 `finstem`에서 발전했으며, [the highest-ROI program I’ve written so far](https://til.andrew-quinn.me/posts/the-highest-personal-roi-program-i-have-written-so-far/)와 연결됨
- `taskusanakirja`는 핀란드어로 “pocket dictionary”를 뜻하며, 낡은 노트북에도 들어가지 않으면 포켓 사전이 아니라 컴파일되는 오래된 Oxford 사전에 가깝다는 기준이 유지됨
- “문제를 두 번 풀어도 괜찮다”는 반복되는 형태가 있으며, 기존의 더 나은 구현을 찾아야 한다는 죄책감에 멈추기보다 몇 개의 바퀴를 직접 다시 만들어야 실제 경계에 더 빨리 닿을 수 있다는 관점이 담김
- 이 관점은 [Caplanian view](https://www.betonit.ai/p/how_people_gethtml)의 “연습”과 연결되며, [Do Ten Times as Much](https://www.betonit.ai/p/do-ten-times-as-much)가 불편하지만 작동하는 조언으로 제시됨

## Comments



### Comment 57216

- Author: neo
- Created: 2026-05-11T15:02:24+09:00
- Points: 1

###### [Lobste.rs 의견들](https://lobste.rs/s/xb2edj/replacing_3_gb_sqlite_database_with_10_mb) 
- 글 자체도 흥미롭고, **잘 맞는 도구**를 잘 맞는 작업에 적용해 **한 자릿수 규모 개선**을 얻는 모습이 좋았지만, 본문보다 마지막 각주가 더 인상적이었음  
  지금 만드는 도구가 이미 30~40년 전에 누군가 더 잘 구현해 둔 것일지 모른다는 죄책감 때문에 멈춰 서는 고민을 정확히 짚고 있음. 하지만 그건 함정이고, 바퀴를 몇 개는 다시 만들어 봐야 바퀴 만들기의 경계까지 갈 수 있다는 말이 와닿음. 대부분의 분야에서는 네다섯 개면 충분하고, 수학이나 컴퓨터과학처럼 엄밀한 분야도 스무세 개 정도면 될 수 있으며, 그렇게 직접 다시 만들며 던지는 질문이 단순한 공부보다 훨씬 빨리 진짜 최전선으로 데려다준다는 주장임
  - 본문에서 중요한 관련 포인트는 **SQLite DB로 만든 비효율적 무차별 대입 구현**도 기준 구현으로서 가치가 있었다는 점임  
    일단 무언가가 동작하는 참조 구현이 있었기 때문에, 그것을 대체할 효율적인 구현을 만들기 쉬워졌음
  - 지금 겪는 문제와 딱 맞음. 내 문제 공간에 최적화된 걸 만들고 싶지만, 일반화된 문제는 이미 풀렸다는 걸 알아서 멈춰 있었음  
    그런데 기존 해법들을 보면 내가 필요 없는 짐이 많이 붙어 있음. 경험상 내 아이디어를 밀어붙일 가치가 있다는 걸 알면서도 뭔가 놓치고 있는 게 아닐까 계속 생각했는데, 이걸 읽고 그냥 해보기로 함. 실패해도 그 과정에서 배울 게 있음

- 아주 멋짐. [Compressing Icelandic name declension patterns into a 3.27 kB trie](https://alexharri.com/blog/icelandic-name-declension-trie)가 떠올랐음

- Scrabble 봇을 구현하다가 **DAWG(Directed Acyclic Word Graph)** 라는 관련 자료구조를 알게 됐고, 그 용도로는 꽤 흔한 듯함  
  `fst` 크레이트와의 주된 차이는 각 단어를 고유한 정수에 매핑하지 않는다는 점으로 보임. 비슷하게 크기가 크게 줄고 성능도 엄청나게 좋아졌음. Scrabble 봇은 기본적으로 `..cat..` 같은 간단한 정규식에 맞는 단어로 전체 사전을 걸러야 하는데, 실제로는 현재 보드에서 가능한 모든 간단한 정규식을 처리해야 함. 1분쯤 기다리던 작업이 체감 불가능한 지연으로 줄었음
  - Appel과 Jacobson의 1988년 **DAWG 논문**이 [얼마 전](https://lobste.rs/s/v23clg/world_s_fastest_scrabble_program_1988)에도 올라왔고 [이전에도](https://lobste.rs/s/jl3vna/world_s_fastest_scrabble_program_1988) 공유된 적 있음

- 링크된 글도 읽을 만함: https://burntsushi.net/transducers/

- `fst`는 [`srgn`의 독일어 지원](https://github.com/alexpovel/srgn/tree/71ee60854fbec71bd90c5f3ef1df6263c37851d8#german)에도 결국 쓰게 된 도구이고, [Andrew가 직접 추천](https://users.rust-lang.org/t/fast-string-lookup-in-a-single-str-containing-millions-of-unevenly-sized-substrings/98040/7)해 준 뒤였음  
  공통 접두사와 접미사를 압축하는 같은 문제 공간이고, 정말 잘 동작함. 또 CLI 도구라 **시작 비용 최소화**도 필요했는데, `fst` 크레이트는 [제로카피 로딩](https://github.com/alexpovel/srgn/blob/71ee60854fbec71bd90c5f3ef1df6263c37851d8/src/actions/german/driver.rs#L467-L473)을 지원해서 런타임 오버헤드가 없음. FST는 컴파일 시점에 만들어짐

- 정말 멋지고, **독일어와 영어**에도 이런 게 있으면 좋겠음. 독일어 합성어는 아직도 나를 자주 헷갈리게 함