▲

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

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

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 다운로드가 필요했음

Rust와 FST로 바꾼 결과

  • 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가 트라이보다 작아진 이유

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

임시 SQLite 해법이 남긴 역할과 배포 크기

  • 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가 불편하지만 작동하는 조언으로 제시됨

함께 보면 좋은 글 β

▲
GN⁺ 5시간전  [-]
Lobste.rs 의견들

  • 글 자체도 흥미롭고, 잘 맞는 도구를 잘 맞는 작업에 적용해 한 자릿수 규모 개선을 얻는 모습이 좋았지만, 본문보다 마지막 각주가 더 인상적이었음
    지금 만드는 도구가 이미 30~40년 전에 누군가 더 잘 구현해 둔 것일지 모른다는 죄책감 때문에 멈춰 서는 고민을 정확히 짚고 있음. 하지만 그건 함정이고, 바퀴를 몇 개는 다시 만들어 봐야 바퀴 만들기의 경계까지 갈 수 있다는 말이 와닿음. 대부분의 분야에서는 네다섯 개면 충분하고, 수학이나 컴퓨터과학처럼 엄밀한 분야도 스무세 개 정도면 될 수 있으며, 그렇게 직접 다시 만들며 던지는 질문이 단순한 공부보다 훨씬 빨리 진짜 최전선으로 데려다준다는 주장임

    • 본문에서 중요한 관련 포인트는 SQLite DB로 만든 비효율적 무차별 대입 구현도 기준 구현으로서 가치가 있었다는 점임
      일단 무언가가 동작하는 참조 구현이 있었기 때문에, 그것을 대체할 효율적인 구현을 만들기 쉬워졌음
    • 지금 겪는 문제와 딱 맞음. 내 문제 공간에 최적화된 걸 만들고 싶지만, 일반화된 문제는 이미 풀렸다는 걸 알아서 멈춰 있었음
      그런데 기존 해법들을 보면 내가 필요 없는 짐이 많이 붙어 있음. 경험상 내 아이디어를 밀어붙일 가치가 있다는 걸 알면서도 뭔가 놓치고 있는 게 아닐까 계속 생각했는데, 이걸 읽고 그냥 해보기로 함. 실패해도 그 과정에서 배울 게 있음

  • 아주 멋짐. Compressing Icelandic name declension patterns into a 3.27 kB trie가 떠올랐음

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

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

  • fst는 srgn의 독일어 지원에도 결국 쓰게 된 도구이고, Andrew가 직접 추천해 준 뒤였음
    공통 접두사와 접미사를 압축하는 같은 문제 공간이고, 정말 잘 동작함. 또 CLI 도구라 시작 비용 최소화도 필요했는데, fst 크레이트는 제로카피 로딩을 지원해서 런타임 오버헤드가 없음. FST는 컴파일 시점에 만들어짐

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

답변달기