기술 요약: 산술 가변 로그로그 (Arithmetic Variable LogLog, AVLL)

문제 정의

카디널리티 추정(Cardinality estimation)—제한된 메모리를 사용하여 데이터 스트림 내의 고유 요소 수를 계산하는 작업—은 메모리 사용량과 추정 정확도 사이의 근본적인 트레이드오프를 요구한다. HyperLogLog(HLL)가 오랫동안 실질적인 골드 표준 역할을 해왔으나, 최근 ExaLogLog와 같은 발전된 방식들은 넓은 가변 폭 레지스터와 최대 가능도 추정(Maximum Likelihood Estimation)을 사용하여 레지스터당 정보 밀도를 높임으로써 메모리-분산 경계를 확장했다. 그러나 이러한 접근 방식은 레지스터당 비트 수가 적어 관측값의 통계적 독립성을 제한하는 경우가 많다. 반대로, DynamicLogLog(DLL)와 같은 구조적 압축 방식은 레지스터 밀도는 높이지만, 역사적으로 풍부한 추정기만큼 레지스터당 정보 깊이를 갖추지 못했다. 과제는 고정된 메모리 예산 하에서 독립적인 레지스터 수를 최대화하는 것이 더 나은지, 아니면 레지스터당 정보를 최대화하는 것이 더 나은지를 결정하는 것이다.

방법론

본 논문은 산술 인코딩과 혼합형 추정 파이프라인을 통해 레지스터 밀도를 우선시하는 새로운 추정기인 **산술 가변 로그로그(AVLL)**를 소개한다.

1. 산술 레지스터 인코딩

고정 폭 비트 슬롯(예: 6비트 또는 8비트 레지스터)을 사용하는 전통적인 LogLog 변형들과 달리, AVLL은 base-56 산술 인코딩을 채택한다.

• 상태 공간: 각 레지스터는 NLZ(Leading Zeros, 앞자리 0의 개수) 지수와 2비트 sub-NLZ 히스토리 패턴을 포함하여 56개의 서로 다른 상태를 인코딩한다.
• 패킹: $56^{11} < 2^{64}$이므로, AVLL은 11개의 레지스터를 단일 64비트 워드에 패킹하여 낭비되는 비트 없이 구현한다. 이는 레지스터 폭이 약 5.82비트임을 의미한다.
• 비교: 2 KB 메모리 예산에서 AVLL은 2,816개의 레지스터를 저장하는 반면, ExaLogLog(32비트 레지스터 사용 시)는 512개만을 저장한다. 이는 5.5배의 레지스터 수 우위를 제공한다.
• 접근: 레지스터 접근에는 64비트 부호 없는 나눗셈 및 나머지 연산(Long.divideUnsigned, Long.remainderUnsigned)이 필요하며, 이는 고정 폭 비트 마스킹보다 계산 비용이 높지만, 추정기의 조기 종료(early exit) 메커니즘에 의해 상쇄된다.

2. 아키텍처 및 스케일링

• 공유 지수 (Global Floor): AVLL은 DynamicLogLog와 유사하게 전역 플로어(globalNLZ)에 대한 상대적 NLZ 값을 저장한다. 이를 통해 메모리 비용을 $O(B \times \log \log C)$가 아닌 $O(B + \log \log C)$로 스케일링할 수 있으며, 이는 최대 표현 가능한 카디널리티를 레지스터 폭으로부터 효과적으로 분리한다.
• 조기 종료 (Early Exit): 현재 전역 플로어보다 낮은 해시 값을 가진 요소는 레지스터 메모리에 접근하기 전에 즉시 거부된다. 높은 카디널리티에서는 이 과정에서 99% 이상의 요소가 거부되어 메모리 대역폭 사용량을 획기적으로 줄인다.
• 병합 지원: AVLL은 레지스터를 언패킹하고, 비트맵 표현에 대한 비트 단위 OR 연산을 수행한 뒤 다시 패킹하는 방식으로 레지스터 단위 병합을 지원한다.

3. HLDLC 추정기

AVLL은 전체 카디널리티 범위에서 편향(bias)을 최소화하도록 설계된 4개 구성 요소의 혼합 프레임워크인 Hybrid Layered DLC (HLDLC) 추정기를 사용한다.

• LDLC (Layered DLC): 저-중간 카디널리티를 위한 DLC(Dynamic Linear Counting)와 SBS(State Bias Sum)의 혼합, 그리고 고카디널티를 위한 HC(History Counting)의 결합이다.
• Hybrid+2: SBS와 Mean+H(새로운 히스토리 교정 조화 평균)의 혼합이다.
• 블렌딩 전략: 최종 추정치는 LDLC와 Hybrid+2의 50/50 혼합이며, 이 보완적인 편향 상쇄를 통해 단일 구성 요소보다 낮은 오차를 달이트한다.
• 구성 요소:
  • SBS: 저카디널리티 추정을 위해 특정 2비트 히스토리 패턴을 활용한다.
  • DLC: 전이 아티팩트(transition artifacts)를 제거한 계층 인식형 Linear Counting의 확장형이다.
  • HC: 티어 경계에서의 히스토리 비트를 사용하여 고카디널리티를 추정한다.
  • Mean+H: sub-NLZ 히스토리 패턴에 의해 교정된 조화 평균 추정기이다.
• 구현: 모든 교정 공식은 약 100개의 정적 상수로 하나의 Java 클래스에 내장되어 있어, 외부 테이블이나 런타임 의존성 없이 작동한다.

주요 기여

1. 산술 인코딩: 11개의 레지스터를 64비트 워드에 비트 낭비 없이 패킹함으로써 base-56 산술 인코딩의 실용성을 입증했다.
2. HLDLC 추정기: 반복적인 솔빙(ExaLogLog의 최대 가능도 접근 방식과 달리) 없이도 높은 정확도를 달성하는 4개 구성 요소의 혼합 추정기를 도입했다.
3. 기록적인 정확도: 1 KB에서 **1.63%의 폭 가중 평균 절대 오차(MAE)**를 달성하여, ExaLogLog(1.71%)를 4.7% 상회하는 성능을 보여주었다. 경험적 메모리-분산 곱(MVP)은 ~3.4로, ExaLogLog의 실질적 MVP(3.78) 및 이론적 최적값(3.67)보다 낮다(단, 논문은 이것이 증명된 이론적 한계가 아닌 경험적 관찰임을 명시한다).
4. 배포 속도: 캐시 압박이 있는 환경(수천 개의 동시 스케치)에서, AVLL은 조기 종료 메커니즘이 레지스터 접근 전 대부분의 요소를 필터링하기 때문에 ExaLogLog보다 2.7–4.5배 더 빠르다.
5. 무제한 카디널리티: 슬라이딩 플로어 아키텍처는 레지스터 폭에 의한 카디널리티 상한을 제거하여, 거의 일정한 메모리 오버헤드로 해시 폭 제한($2^{256}$ 등)까지 카디널리티를 지원한다.
6. 강건성: 비멱등적(non-idempotent) 티어 승격(tier promotion)을 사용함에도 불구하고, 저복잡도(높은 중복도) 데이터 분포에서도 성능 저하 없이 정확도를 유지한다.

실험 결과

• 정확도: AVLL은 고복잡도(모두 고유) 및 저복잡도(왜곡된 중복) 조건 모두에서 모든 테스트 메모리 지점(0.25 KB ~ 4 KB)에서 ExaLogLog 및 7개의 다른 추정기(HLL-TailCut4, UltraLogLog, Apache HLL4 포함)를 능가한다.
• 처리량:
  • ALU 제한 상황: 스케치가 캐시에 들어갈 때 AVLL은 ExaLogLog의 처리량(~14,681 vs 13,801 M adds/s)과 대등하다.
  • 메모리 대역폭 제한 상황: 극심한 캐시 압박(sim=4,096) 하에서, AVLL은 4,360 M adds/s를 달성하여 ExaLogLog의 1,609 M adds/s 대비 2.7배의 우위를 점한다.
  • 카디널리티 스케일링: 스트림 카디널리티가 5M에서 80M으로 증가함에 따라 AVLL의 처리량은 177% 증가하는 반면, ExaLogLog는 평탄하게 유지되어 고카디널리티에서 격차를 9.7배까지 벌린다.
• 메모리 효율성: AVLL은 현재까지 입증된 가장 낮은 경험적 MVP(~3.4)를 달성하여, ExaLogLog의 실질적 MVP(3.78)를 앞질렀다.

의의 및 주장

본 논문은 핵심 설계 원칙으로 **"밀도가 풍부함보다 낫다(Density beats richness)"**를 제시한다. LogLog 계열 추정기에서, 추정기가 단순한 인코딩으로부터 정보를 추출할 수 있을 만큼 정교하다면, 레지스터당 정보량을 극대화하는 것보다 독립적인 해시 관측(레지스터 수)을 최대화하는 것이 종종 더 나은 정확도를 제공한다는 것이다.

저자는 AVLL이 다음과 같은 이유로 새로운 최첨단(state of the art)임을 주장한다:

1. 산술 패킹과 혼합 추정기를 통해 고정 레지스터 방식(ExaLogLog)의 경험적 성능을 능가하며, ExaLogLog의 이론적 최적값보다 낮은 MVP를 달성했다.
2. 조기 종료를 활용해 메모리 대역폭 사용을 최소화함으로써 배포 시의 속도-정확도 트레이드오프 문제를 해결했다.
3. 고정 폭 레지스터 방식에 내재된 카디널리티 상한을 제거했다.

AVLL이 티어 승격으로 인해 엄격하게 멱등적(idempotent)이지 않으며, 레지스터 접근 시 나눗셈 오버헤드가 발생한다는 점을 인정한다. 그러나 저자는 조기 종료가 지배적인 고카디널리티 스트리밍 애플리케이션에서 이러한 제한 사항이 무시할 만한 수준이며, 정확도 이득이 다양한 데이터 분포에서 강건하다는 점을 강조한다. 구현체는 BBTools 제품군 내의 독립적인 Java 클래스로 제공된다.