AI 요약
ScopeDB의 근사 중복 카운트 기능 구현을 계기로 Apache DataSketches의 Rust 포팅 프로젝트(datasketches-rust)에 참여한 저자가, HLL보다 공간 효율적인 CPC(CpcSketch) 알고리즘을 Rust로 포팅한 경험을 다룹니다. CPC는 Kevin J. Lang이 2017년 논문에서 제안한 알고리즘으로, 버킷별 최댓값만 유지하는 HLL과 달리 K×64 비트 행렬 전체를 유지해 통계적 효율을 높입니다. 포팅 과정에서 소스 코드에 하드코딩된 23개의 정적 허프만 인코딩 테이블, 16개의 슬라이딩 윈도우 열 순열, 23세트의 19차 다항식 보정 계수 등 매직 룩업 테이블들을 발견하고 이를 역공학한 과정을 설명합니다.
핵심 포인트
- CPC는 직렬화 시 희소 PairTable, 8비트 슬라이딩 윈도우, 길이 제한 허프만 코딩, 열 순열을 조합해 동일 정확도에서 HLL 대비 저장 공간을 30~40% 절감
- 저자는 1월 말 CpcSketch를 datasketches-rust(PR-75)로 포팅해 ScopeDB에 적용, 6개월 이상 프로덕션에서 안정적으로 운영
- 포팅 중 23개 허프만 테이블, 16개 열 순열, 23세트 다항식 보정 계수, 4개 경험적 신뢰도 테이블 등 하드코딩된 매직 넘버들을 발견
- Apache DataSketches 커뮤니티가 공식 Rust 포팅에 관심을 보여 작년 말부터 datasketches-rust 초기 릴리스 개발 시작
향후 전망
- Rust 생태계에서 검증된 스케치 알고리즘 구현이 확산되며 ScopeDB 같은 Rust 기반 데이터 시스템의 근사 집계 기능이 강화될 전망
- 하드코딩된 매직 테이블의 역공학·문서화 작업이 오픈소스 포팅의 유지보수성과 감사 가능성을 높이는 사례로 자리매김
