Apache DataSketches에서 사라진 Kevin J. Lang의 OCaml 코드 역공학하기

“ScopeDB는 근사 중복 카운팅을 위해 Cloudflare의 cardinality-estimator에서 시작해 Apache DataSketches의 Rust 포팅(datasketches-rust)으로 전환했으며, HLL보다 공간 효율적인 CpcSketch를 PR-75로 포팅해 6개월 이상 프로덕션에서 운영 중이다. CPC는 전체 K×64 비트 히트 행렬을 유지해 HLL보다 통계 효율이 높고, 직렬화 시 HLL 대비 저장 공간을 30~40% 절감한다. 포팅 과정에서 23개 정적 허프만 인코딩 테이블, 16개 슬라이딩 윈도 열 순열, 23세트의 19차 다항식 보정 계수 등 하드코딩된 매직 룩업 테이블을 발견했다.”

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 기반 데이터 시스템의 근사 집계 기능이 강화될 전망
  • 하드코딩된 매직 테이블의 역공학·문서화 작업이 오픈소스 포팅의 유지보수성과 감사 가능성을 높이는 사례로 자리매김
Share

이것도 읽어보세요

댓글

이 소식에 대한 의견을 자유롭게 남겨주세요.

댓글 (0)

불러오는 중...