Luft:10초만에 10억 데이터를 쿼리하는 데이터스토어 개발기
NAVER Engineering | 김효준 - Luft:10초만에 10억 데이터를 쿼리하는 데이터스토어 개발기
tv.naver.com
Luft : 유저 행동 분석에 최적화된 실시간 OLAP 데이터스토어
- Fast : 5~10s 내로 수억 이벤트를 스캔해 Query 제공
- Real-Time : lambda Archtecture로 실시간 데이터 처리
- High Availability : 데이터는 샤딩 되고 S3에 저장됨
- Cloud Native : Cloud에 직접 연동되어 유연한 스케일링 및 확장
Luft 개발 배경
- 코호트 분석 기능을 도입해, 폭넓고 유용한 유저행동 분석 기능이 필요했음.
- 타겟 유저군은 자유자재로 설정될 수 있어야 함
- 설정하자마자 리포트가 즉시 보여져야 함
- Druid : 너무 느림, Pre-Aggregation 방식의 한계로 인해 복잡한 행동분석 쿼리가 불가능
- 데이터 웨어 하우스 : 비용 비효율적, SQL로 행동분석 쿼리는 가능, 하지만 너무 범용적이라 느리다.
- 즉, 이러한 단점들을 보완한 최적화된 데이터 스토어가 필요했다.
Luft 목표
- 코호트, 리텐션, 트렌드 분석 등을 10~15초 이내로 제공
- Druid와 비슷하거나 작은 규모 클러스터로 제공
Luft Architecture
- Go 언어를 사용, gRPC로 통신함
- 마스터 노드, 히스토리컬 노드, 리얼타임 노드로 분류
- Batch Layer, Speed Layer를 나누고, 결과를 합치는 방식으로 구현
Luft 데이터 분배 및 샤딩 순서
- 이벤트 데이터는 유저별로 파티셔닝된 채로 인덱싱됨 (사용자 행동 단위로 분류됨)
ex) 구매이벤트, 장바구니 이벤트, 설치 이벤트 - 이벤트 발생 시각 기준으로 한번 더 묶여, 파티션 단위로 만든다, 시계열 분석 쿼리에 최적화하기 위해 시각 기준을 사용
- 만들어진 파티션은 S3에 업로드되고, 히스토리컬 노드에 분배됨
- 분배된 파티션은 리얼타임 노드의 데이터와 합쳐져 나중에 마스터 노드에 의해 쿼리됨
Pre-Aggregation
- 정해진 Metric을 시간 단위별로 사전에 미리 계산한다.
- 쿼리 시엔 필요한 값만 선택해 합산(Roll-up)해서 결과를 빠르게 제공한다.
Pre-Aggregation 단점
- 정해진 종류의 한정된 분석만 가능
- High-Cardinal Shuffle에 취약
Shuffle을 최적화하는 방법
- 파티셔닝을 잘해서 Shuffle을 국소적으로 만들면 된다.
- 즉, User Id로 파티셔닝될 수 있는 스토리지를 찾자!
TrailDB ☆
- User ID 기반 파티셔닝에 최적화된 유일한 스토리지 포맷
- 인덱스가 없고, 무조건 풀스캔을 해야 한다.
- 동일한 쿼리 기준 Snowflake : 8.1s, Druid : 1.1s, TrailDB : 0.51s
TrailDB의 장점
- 98%의 충격적으로 높은 압축률을 가지고 있다.
- 높은 압축률로 인해 사이즈가 작아 Memory에 저장해 연산할 수 있다.
- 유저 이벤트 특성을 반영해 설계한 데이터 구조
TrailDB의 단점
- Immutability : 수정이 불가능하다.
- Simplicity : Full-featured DB가 아닌 LevelDB같은 스토리지 포맷에 가깝다.
Edge-Encoding : 이전 이벤트 대비 바뀐 칼럼만 넣는다. 어차피 대부분의 사용자 속성은 변하지 않으니깐.
아이디어 정리
- 공간 복잡도를 극한으로 최적화하면 낮은 시간 복잡도를 얻을 수 있다.
- Edge Encoding, Dict Encoding을 통한 중복 제거
- Rowstore에서 칼럼 순서는 상관없기 때문에, 최빈순으로 정렬해 Data Entropy를 줄임
- Immutability를 통해서 할 수 있는게 많아진다.
- 기존의 RDBMS에서 할 수 없던 극한의 압축률
- 시간 축으로 정렬해 저장해 Sequential I/O 속도 장점을 살림
- OLAP 데이터스토어기 때문에, 수정 용이성을 과감히 버릴 수 있었음
OLAP (Online Analytical Processing)
- 다차원적 정보에 직접 접근하여 대화식으로 정보를 분석하고 의사결정에 활용하는 과정
- OLTP에서 발생한 원시 데이터를 활용할 수 있도록 가공하고 분석하는 과정
- 우선 계산된 값들을 어떻게 저장하느냐에 따라 구분한다.
OLTP (Online transaction processing)
- 트랜잭션 지향 어플리케이션을 손쉽게 관리할 수 있도록 도와주는 정보 시스템
- 은행의 창구 업무나 항공사의 예약 업무 등이 전형적인 OLTP
Predicate Pushdown : 스토리지 레벨에 필터를 적용해 필요한 데이터만 읽는 기법
TrailDB의 한계
- TrailDB는 OR-AND 형식의 Equals (=) 쿼리만을 지원한다.
- TrailDB의 쿼리 엔진을 확장해 다양한 연산자 지원이 필요 : 추후 기능 확장에 제약사항
- Go로 파싱한 쿼리를 C언어로 가져오기 : 관리 포인트가 많이 늘어남
- Layer화 시킬 땐 Separation-of-Concern이 확실해야 한다.
LLVM JiT
- PostgreSQL에서 쿼리를 LLVM JiT으로 컴파일한다.
- IR 코드를 주면 즉시 최적화 및 컴파일해 실행할 수 있음.
새로운 JiT 쿼리 엔진의 구조
- Query > ParseQuery Generate Code (Go) > Compile (C/C++) > Scan Data (C/C++)
Computation Layer (연산 레이어) : 흩어진 데이터를 하나로 모음
LRMR (Less-Resilient MapReduce for Go.)
- Go를 위한 오픈소스 맵리듀스 프레임워크
LRMR의 디자인
- gRPC + Protobuf + etcd
- 익숙한 Spark의 디자인을 많이 차용
- Resiliency를 포기
Pull-based Event Stream : 컨슈머가 처리할 수 있는 양만 그때그때 요청하는 방법
샤드, 샤딩
- 샤드 = "히스토리컬 노드"
- 샤딩 : 파티션을 여러 히스토리컬 노드에 분배하는 과정
Luft 샤딩 버전
- v.1. Vanilla Sharding
- 새로운 파티션을 만들 때마다 Round-Robbin 방법으로 각 샤드에 분배
- v.2. Cost Function을 사용하기
- 목표 : 날짜 범위가 겹치지 않게 파티션을 분배하는 방법
- Cost Function을 세우고, Cost가 제일 낮은 노드에 자원을 배치함 (스케줄러의 구성과 비슷함)
- 분배할 파티션과 노드가 가진 파티션의 총합에서 파티션의 날짜가 가까울수록 코스트가 높게 설정
샤드의 가용성을 위한 개선 노력
- etcd로 샤드의 장애 상황을 관리 : Liveness Probe 패턴을 사용
- Cloud를 적용 : S3에 파티션을 저장하고, 필요한 것만 상황마다 로드
Luft의 목표
- 다양한 종류의 Query 지원
- Spark 지원
- Open Source
- TrailDB를 대체할 자체 칼럼스토어 구축
- 데이터 기반 데이터스토어 설계
- 유저 속성 기반 필터링
- SIMD와 멀티코드 최적화
