DB 성능의 병목, 문자열(String) 처리를 위한 FSST 딥다이브

엔지니어링을 하다 보면 ‘아, 이건 좀 아닌데’ 싶으면서도 어쩔 수 없이 타협하는 순간들이 있습니다. 데이터베이스 스키마를 짤 때가 대표적이죠.

솔직히 고백해 봅시다. 여러분도 UUID를 TEXT 컬럼에 박아 넣은 적 있지 않나요? 혹은 Enum으로 관리해야 할 상태 값들을 귀찮아서 그냥 문자열로 저장한 적은요? 저도 그랬습니다. 우리 모두 유죄입니다.

문제는 이런 ‘편의성’이 시스템 규모가 커지면 비용 으로 돌아온다는 점입니다. 최근 Snowflake의 리포트에 따르면, 실제 분석 워크로드에서 가장 많이 사용되고, 필터링 조건에 가장 빈번하게 걸리는 데이터 타입이 바로 String 이라고 합니다. 전체 데이터의 50%가 문자열이라니, 실로 엄청난 비중이죠.

오늘은 최근 CedarDB 팀이 공개한 FSST(Fast Static Symbol Table) 기반의 문자열 압축 기술을 깊게 파보려 합니다. 단순히 디스크 용량을 아끼는 수준이 아니라, 쿼리 엔진의 성능 한계를 어떻게 돌파하려는지 엔지니어의 관점에서 뜯어보겠습니다.

왜 문자열 압축에 목숨을 걸어야 할까?

“요즘 스토리지 싼데 굳이 압축을?”이라고 생각하신다면, 데이터베이스의 본질을 놓치고 있는 겁니다. Thomas Neumann 교수님의 명언을 빌리자면, DB에서 압축의 제1목적은 저장 공간 절약이 아니라 쿼리 성능 향상 입니다.

  • Memory Bandwidth: 데이터가 작아지면 한 번의 메모리 버스 사이클에 더 많은 데이터를 CPU로 실어 나를 수 있습니다.
  • Cache Locality: 압축된 데이터가 CPU L1/L2 캐시에 쏙 들어가는 순간, 성능은 10배 이상 뜁니다.

즉, 문자열을 효율적으로 다룬다는 건 단순히 S3 비용을 아끼는 게 아니라, 전체 시스템의 Latency 를 줄이는 핵심 키(Key)라는 뜻입니다.

기존 방식의 한계: Dictionary Compression

대부분의 현대적 컬럼형 DB(Columnar DB)들은 Dictionary Compression 을 사용합니다. 중복되는 문자열을 별도 사전(Dictionary)으로 빼고, 실제 데이터에는 정수형 ID(Offset)만 저장하는 방식이죠.

이 방식은 훌륭합니다. SELECT * FROM logs WHERE status = 'ERROR' 같은 쿼리를 날리면, 엔진은 'ERROR' 문자열을 비교하는 게 아니라 정수 비교(Integer Comparison)를 수행합니다. 심지어 SIMD를 태우기도 좋죠.

하지만 치명적인 단점이 있습니다:

  1. High Cardinality: URL이나 UUID처럼 중복도가 낮은 데이터는 사전 크기가 원본 데이터만큼 커집니다.
  2. Random Access: 사전 자체가 너무 커지면 캐시 히트율이 박살 납니다.

Game Changer: FSST (Fast Static Symbol Table)

여기서 등장하는 것이 FSST 입니다. 원래 논문으로 발표되었던 기술인데, CedarDB나 DuckDB 같은 최신 엔진들이 이를 적극적으로 도입하고 있습니다.

작동 원리

FSST의 핵심은 데이터 내에서 자주 등장하는 패턴(Substring)을 찾아 1바이트 코드로 치환 하는 것입니다. 이를 ‘Symbol’이라고 부르는데, 최대 8바이트 길이의 문자열을 1바이트로 줄여버립니다.

예를 들어 https:// 라는 문자열이 자주 등장한다면, 이걸 통째로 0x01 같은 1바이트 코드로 매핑하는 식입니다. 여기서 중요한 엔지니어링 포인트는 다음과 같습니다:

  • Static Table: 심볼 테이블을 한 번 만들면 변하지 않습니다. (Immutable)
  • L1 Cache Friendly: 최대 255개의 심볼만 사용합니다. 왜냐고요? 이 테이블이 CPU L1 캐시에 통째로 들어가야 하거든요. 여기서 오는 속도 향상이 어마어마합니다.
  • Escape Code: 255번째 코드는 Escape 용도로 남겨둡니다. 심볼에 없는 문자가 나오면 그대로 출력하기 위함이죠.

CedarDB의 영리한 전략: Dict-FSST

이 글을 읽으며 “그럼 모든 문자열을 FSST로 압축하면 되겠네?”라고 생각하셨다면, 반은 맞고 반은 틀렸습니다. 압축률은 좋겠지만, 검색(Filtering) 할 때마다 매번 압축을 풀어야 한다면 CPU가 녹아내릴 겁니다.

CedarDB는 여기서 Dictionary와 FSST를 결합(Hybrid) 하는 영리한 선택을 했습니다.

  1. Dictionary 구축: 먼저 중복 데이터를 제거하여 사전을 만듭니다.
  2. Dictionary 압축: 그 사전 자체를 FSST로 압축 합니다.
  3. 쿼리 실행: WHERE url = '...' 같은 조건이 들어오면, 검색어만 압축해서 사전의 정수 키(Key)를 찾습니다(Binary Search). 실제 데이터 스캔은 여전히 빠른 정수 비교로 처리합니다.

이 방식은 DuckDB의 DICT_FSST와 유사한데, 현시점에서 문자열 처리를 위한 가장 진보된 형태의 아키텍처라고 봅니다.

벤치마크: 냉정한 현실과 Trade-off

엔지니어로서 가장 흥미로웠던 부분은 벤치마크 결과 해석입니다. 세상에 공짜 점심은 없다는 걸 명확히 보여줍니다.

1. Storage Size (압승)

TPC-H 데이터셋 기준, 전체 스토리지 사이즈가 40% 이상 감소 했습니다. 문자열 데이터만 놓고 보면 60% 가까이 줄어듭니다. I/O 비용이 비싼 클라우드 환경에서는 이것만으로도 도입할 가치가 충분합니다.

2. Cold Run (압승)

디스크에서 데이터를 처음 읽어올 때(Cold Run), 쿼리 속도가 40%까지 향상 됩니다. 디스크 I/O가 병목인 상황에서 읽어야 할 데이터 양 자체가 줄어드니 당연한 결과입니다.

3. Hot Run (패배?)

문제는 데이터가 이미 메모리에 올라와 있는 Hot Run 상황입니다. 일부 쿼리(단순 스캔이나 LIKE 연산)에서는 오히려 2.8배 느려졌습니다.

이유는 명확합니다. 메모리 대역폭보다 압축 해제(Decompression) 연산 비용 이 더 비싸기 때문입니다. 특히 FSST는 Dictionary 방식보다 압축 해제에 CPU 사이클을 더 많이 먹습니다. “Physics(물리 법칙)는 이길 수 없다”는 저자의 말에 격하게 공감합니다.

결론: 그래서 써야 할까?

CedarDB 팀은 “FSST 압축으로 40% 이상의 공간 이득이 있을 때만 적용” 하도록 페널티 로직을 넣었다고 합니다. 아주 실용적인 접근입니다.

제 생각은 이렇습니다:

  1. I/O Bound 워크로드라면 무조건 이득입니다. 로그 분석, 대용량 텍스트 처리 등에서는 고민할 필요가 없습니다.
  2. 메모리 중심의 초고속 연산이 필요하다면 조심해야 합니다. 빈번하게 전체 스캔을 하거나 LIKE 검색을 난사하는 경우라면 CPU 오버헤드가 병목이 될 수 있습니다.

문자열 처리는 DB 엔진 개발자들에게 영원한 숙제와 같습니다. 하지만 FSST와 Dictionary를 결합하는 방식은 현재 우리가 가진 하드웨어 특성(느린 디스크, 빠른 캐시, 제한된 메모리 대역폭)을 아주 잘 활용한 Best Practice 에 가깝습니다.

앞으로 여러분이 사용하는 DB가 TEXT 컬럼을 어떻게 저장하는지 한 번쯤 EXPLAIN을 떠보시길 권합니다. 그 속에 숨겨진 엔지니어링의 정수를 발견하는 재미가 쏠쏠할 겁니다.