Theta 스케치로 근사 계산하기

Theta 스케치로 근사 계산하기 (Approximations with Theta sketches)

Apache Druid는 클릭스트림(clickstream)의 실시간 수집, 스트리밍, 인터랙티브 시각화를 지원해요. 클릭스트림 분석에서 흔한 문제는 방문자나 세션 같은 고유(unique) 항목을 세는 거예요. 일반적으로 고유 카운트는 숫자를 집계한다고 더해지지 않기 때문에 모든 상세(detail) 데이터를 스캔해야 해요.

출처: 문서

본문

대규모 데이터셋에서 카운트와 집합 연산의 문제 (The problem with counts and set operations on large data sets)

TV 프로그램의 에피소드를 시청한 방문자 수에 관심이 있다고 상상해 볼게요. 특정 날에 첫 번째 에피소드를 시청한 고유 방문자가 1000명, 두 번째 에피소드를 시청한 방문자가 800명이었다고 해요. 더 탐구하고 싶은 추세가 있을 수 있어요. 예를 들어:

  • 두 에피소드를 모두 시청한 방문자는 몇 명인가요?
  • 에피소드 중 최소 하나를 시청한 방문자는 몇 명인가요?
  • 에피소드 1을 시청했지만 에피소드 2는 시청하지 않은 방문자는 몇 명인가요?

이런 질문에 집계된 숫자만 보고는 답할 방법이 없어요. 상세 데이터로 돌아가 모든 단일 행을 스캔해야 해요. 데이터 볼륨이 충분히 크면 아주 오래 걸릴 수 있으므로, 인터랙티브한 데이터 탐색이 불가능해져요.

추가로 짜증나는 점은 고유 카운트가 rollup과 잘 맞지 않는다는 거예요. 이 예시에서는 15분 간격, 쇼, 에피소드당 데이터 행이 하나씩만 있으면 좋을 텐데요. 어차피 개별 사용자 ID에는 관심이 없고 고유 카운트만 관심 있으니까요.

매번 상세 데이터를 계산하지 않게 하는 방법이 있지 않을까? 심지어 rollup도 가능하게? 그 해답이 바로 Theta sketches예요.

집합 연산과 함께 빠른 근사를 위한 Theta sketches 사용하기 (Use Theta sketches for fast approximation with set operations)

Theta sketches를 사용하면 스케치를 만드는 데 쓴 값들의 고유 카운트에 대한 빠른 근사 추정치를 얻을 수 있어요. Theta sketches는 알려진 오차 분포로 대규모 데이터의 근사 분석을 가능하게 하는 확률적 데이터 구조(probabilistic data structure)예요. Druid의 구현은 Apache DataSketches 라이브러리에 기반해요.

Theta sketches를 설명하는 속성은 다음과 같아요:

  • 다른 스케치들처럼 Theta sketches는 병합 가능(mergeable)해요. 즉 rolled up 데이터로 작업하고 다양한 시간 구간에 걸쳐 스케치를 병합할 수 있어요. 따라서 Druid의 rollup 기능을 활용할 수 있어요.
  • Druid에서 지원하는 스케치 중에서 특별히 Theta sketches는 집합 연산(set operations)을 지원해요. 데이터 하위 집합에 대한 두 Theta sketch가 주어지면 두 하위 집합의 합집합(union), 교집합(intersection), 집합 차(set difference)를 계산할 수 있어요. 이를 통해 예시에서 특정 에피소드 조합을 시청한 방문자 수 같은 질문에 답할 수 있어요.

이 튜토리얼에서는 다음 방법을 배울 거예요:

  • 수집 시점에 입력 데이터로부터 Theta sketches를 만드는 방법.
  • Theta sketches에 대해 고유 카운트와 집합 연산 쿼리를 실행해 앞서 제기한 질문들을 탐구하는 방법.

사전 준비 (Prerequisites)

진행하기 전에 단일 머신 퀵스타트 (single-machine quickstart)에 설명된 대로 Druid를 다운로드하고 로컬 머신에서 실행 중이어야 해요. Druid 클러스터에 데이터를 로드할 필요는 없어요.

Tutorial: Loading a file과 Tutorial: Querying data를 완료했으면 도움이 돼요.

샘플 데이터 (Sample data)

이 튜토리얼은 다음 데이터로 작업해요:

  • date: 타임스탬프. 여기서는 그냥 날짜지만, 앞서 언급했듯 실제 환경에서는 더 세밀한 granularity가 말이 되요.
  • uid: 사용자 ID
  • show: TV 프로그램 이름
  • episode: 에피소드 식별자
date,uid,show,episode
2022-05-19,alice,Game of Thrones,S1E1
2022-05-19,alice,Game of Thrones,S1E2
2022-05-19,alice,Game of Thrones,S1E1
2022-05-19,bob,Bridgerton,S1E1
2022-05-20,alice,Game of Thrones,S1E1
2022-05-20,carol,Bridgerton,S1E2
2022-05-20,dan,Bridgerton,S1E1
2022-05-21,alice,Game of Thrones,S1E1
2022-05-21,carol,Bridgerton,S1E1
2022-05-21,erin,Game of Thrones,S1E1
2022-05-21,alice,Bridgerton,S1E1
2022-05-22,bob,Game of Thrones,S1E1
2022-05-22,bob,Bridgerton,S1E1
2022-05-22,carol,Bridgerton,S1E2
2022-05-22,bob,Bridgerton,S1E1
2022-05-22,erin,Game of Thrones,S1E1
2022-05-22,erin,Bridgerton,S1E2
2022-05-23,erin,Game of Thrones,S1E1
2022-05-23,alice,Game of Thrones,S1E1

Theta sketches로 데이터 수집하기 (Ingest data using Theta sketches)

INSERT INTO 문과 EXTERN 함수를 사용해 샘플 데이터를 인라인으로 수집하면서 샘플 데이터셋을 로드해 볼게요. Druid 웹 콘솔 (Druid web console)에서 Query 뷰로 이동해 다음 쿼리를 실행해 주세요:

INSERT INTO "ts_tutorial"
WITH "source" AS (SELECT * FROM TABLE(
  EXTERN(
    '{"type":"inline","data":"date,uid,show,episode\n2022-05-19,alice,Game of Thrones,S1E1\n2022-05-19,alice,Game of Thrones,S1E2\n2022-05-19,alice,Game of Thrones,S1E1\n2022-05-19,bob,Bridgerton,S1E1\n2022-05-20,alice,Game of Thrones,S1E1\n2022-05-20,carol,Bridgerton,S1E2\n2022-05-20,dan,Bridgerton,S1E1\n2022-05-21,alice,Game of Thrones,S1E1\n2022-05-21,carol,Bridgerton,S1E1\n2022-05-21,erin,Game of Thrones,S1E1\n2022-05-21,alice,Bridgerton,S1E1\n2022-05-22,bob,Game of Thrones,S1E1\n2022-05-22,bob,Bridgerton,S1E1\n2022-05-22,carol,Bridgerton,S1E2\n2022-05-22,bob,Bridgerton,S1E1\n2022-05-22,erin,Game of Thrones,S1E1\n2022-05-22,erin,Bridgerton,S1E2\n2022-05-23,erin,Game of Thrones,S1E1\n2022-05-23,alice,Game of Thrones,S1E1"}',
    '{"type":"csv","findColumnsFromHeader":true}'
  ))
  EXTEND ("date" VARCHAR, "show" VARCHAR, "episode" VARCHAR, "uid" VARCHAR)
)
SELECT
  TIME_FLOOR(TIME_PARSE("date"), 'P1D') AS "__time",
  "show",
  "episode",
  COUNT(*) AS "count",
  DS_THETA("uid") AS "theta_uid"
FROM "source"
GROUP BY 1, 2, 3
PARTITIONED BY DAY

SELECT 문의 theta_uid 컬럼에 주목해 주세요. 수집 중 uid 컬럼에 thetaSketch aggregator를 정의해요. 이 시나리오에서는 개별 사용자 ID에 관심이 없고 고유 카운트만 관심 있어요. 대신 DS_THETA 함수로 uid 값들에 Theta sketches를 만들어요.

DS_THETA 에는 스케치의 정확도와 크기를 제어하는 선택적 두 번째 파라미터가 있어요.

GROUP BY 문은 같은 날 시청한 각 쇼의 각 에피소드에 대한 항목들을 그룹핑해요.

Theta sketch 컬럼 쿼리하기 (Query the Theta sketch column)

Theta sketch 컬럼에서 고유 카운트 추정치를 계산하는 단계는 다음과 같아요:

  • Druid SQL의 DS_THETA aggregator 함수를 통해 컬럼의 Theta sketches를 병합해요.
  • THETA_SKETCH_ESTIMATE 함수로 병합된 스케치에서 추정치를 가져와요.

1단계와 2단계 사이에 Set operations에서 보여 주는 것처럼 집합 함수를 적용할 수 있어요.

기본 카운팅 (Basic counting)

먼저 데이터가 Druid에서 어떻게 보이는지 확인해 볼게요. 쿼리 편집기에서 다음 SQL 문을 실행해 주세요:

SELECT * FROM ts_tutorial

theta_uid Theta sketch 컬럼은 Base64로 인코딩된 문자열로 나타나요. 그 뒤에는 비트맵이 숨어 있어요.

다음 쿼리는 THETA_SKETCH_ESTIMATE 를 사용해 사용자 ID의 고유 카운트를 계산하고 다른 dimensions로 그룹핑해요:

SELECT
  __time,
  "show",
  "episode",
  THETA_SKETCH_ESTIMATE(theta_uid) AS users
FROM ts_tutorial

필터링된 메트릭 (Filtered metrics)

Druid는 filtered metrics를 사용할 수 있어요. 즉 쿼리의 SELECT 부분에 WHERE 절을 포함할 수 있어요.

Theta sketches의 경우 필터 절을 aggregator와 estimator 사이에 넣어야 해요.

예를 들어 Bridgerton 을 시청한 고유 사용자 총수를 쿼리해 볼게요:

SELECT APPROX_COUNT_DISTINCT_DS_THETA(theta_uid) FILTER(WHERE "show" = 'Bridgerton') AS users
FROM ts_tutorial

앞선 쿼리에서 APPROX_COUNT_DISTINCT_DS_THETA 은 다음처럼 DS_THETA 와 THETA_SKETCH_ESTIMATE 를 호출하는 것과 동일해요:

SELECT THETA_SKETCH_ESTIMATE(
         DS_THETA(theta_uid) FILTER(WHERE "show" = 'Bridgerton')
       ) AS users
FROM ts_tutorial

APPROX_COUNT_DISTINCT_DS_THETA 함수는 다음을 적용해요:

  • DS_THETA: Theta sketches 컬럼에서 새 Theta sketch를 만들어요.
  • THETA_SKETCH_ESTIMATE: DS_THETA 의 출력에서 고유 카운트 추정치를 계산해요.

필터 절이 집계 쿼리를 필터와 일치하는 행으로만 제한한다는 점에 주의해 주세요.

집합 연산 (Set operations)

aggregator에서 필터링하는 기능과 집합 연산을 함께 사용해서 마침내 서론의 질문에 답할 수 있어요.

Bridgerton의 두 에피소드를 모두 시청한 사용자는 몇 명인가요? THETA_SKETCH_INTERSECT 를 사용해 두 개(이상) 세그먼트의 교집합의 고유 카운트를 계산해 보세요:

SELECT THETA_SKETCH_ESTIMATE(
         THETA_SKETCH_INTERSECT(
           DS_THETA(theta_uid) FILTER(WHERE "show" = 'Bridgerton' AND "episode" = 'S1E1'),
           DS_THETA(theta_uid) FILTER(WHERE "show" = 'Bridgerton' AND "episode" = 'S1E2')
         )
       ) AS users
FROM ts_tutorial

역시 집합 함수가 aggregator와 estimator 사이에 끼워져 있어요.

마찬가지로 THETA_SKETCH_UNION 을 사용해 어떤 에피소드든 하나라도 시청한 방문자 수를 찾아볼게요:

SELECT THETA_SKETCH_ESTIMATE(
         THETA_SKETCH_UNION(
           DS_THETA(theta_uid) FILTER(WHERE "show" = 'Bridgerton' AND "episode" = 'S1E1'),
           DS_THETA(theta_uid) FILTER(WHERE "show" = 'Bridgerton' AND "episode" = 'S1E2')
         )
       ) AS users
FROM ts_tutorial

마지막으로 THETA_SKETCH_NOT 이 있는데, 두 개 이상 세그먼트의 집합 차를 계산해요. 결과는 Bridgerton 에피소드 1을 시청했지만 에피소드 2는 시청하지 않은 방문자 수를 설명해요.

SELECT THETA_SKETCH_ESTIMATE(
         THETA_SKETCH_NOT(
           DS_THETA(theta_uid) FILTER(WHERE "show" = 'Bridgerton' AND "episode" = 'S1E1'),
           DS_THETA(theta_uid) FILTER(WHERE "show" = 'Bridgerton' AND "episode" = 'S1E2')
         )
       ) AS users
FROM ts_tutorial

결론 (Conclusions)

  • 대규모 데이터셋에 대해 고유한 것들을 세는 것은 Apache Druid에서 Theta sketches로 할 수 있어요.
  • 이를 통해 rollup을 사용하고 개별 값은 버리면서 스케치의 통계적 근사치만 유지할 수 있어요.
  • Theta sketch 집합 연산으로 친화도 분석(affinity analysis)이 더 쉬워져요. 예를 들어 어떤 세그먼트들이 얼마나 상관되거나 겹치는지 같은 질문에 답할 수 있어요.

더 알아보기 (Learn more)

자세한 내용은 다음 주제를 참고해 주세요:

감사의 말 (Acknowledgments)

이 튜토리얼은 커뮤니티 멤버 Hellmar Becker의 블로그 게시물을 각색한 것이에요.

각주 (Footnotes)

왜 1시간이 아니라 15분일까요? 15분 간격은 시간과 정렬되지 않는 경우가 많은 국제 시간대에서 더 잘 작동해요. 예를 들어 인도는 30분, 네팔은 45분 어긋나 있어요. 15분 단위 집계를 쓰면 그런 시간대들에서도 시간별 합계를 얻을 수 있어요! ↩