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

6 hours ago 2

Taskusanakirja의 검색 구조와 초기 한계

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

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

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

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

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