Roblox가 머신 러닝으로 최적화된 블룸 필터를 활용해 Spark 조인 쿼리 비용을 절감하는 방법

요약

매일 Roblox에서는 7천만 명의 사용자가 수백만 개의 체험 콘텐츠와 상호작용하며, 분기당 총 160억 시간의 이용 시간을 기록합니다. 이러한 상호작용은 페타바이트 규모의 데이터 레이크를 생성하며, 이 데이터는 분석 및 머신러닝(ML) 목적으로 보강됩니다. 데이터 레이크 내 팩트 테이블과 차원 테이블을 조인하는 작업은 많은 자원을 소모하므로, 이를 최적화하고 데이터 이동량을 줄이기 위해 우리는 ML을 활용한 지능형 데이터 구조인 학습형 블룸 필터[1]를 도입했습니다. 이 필터들은 데이터의 존재 여부를 예측함으로써 조인 대상 데이터를 대폭 줄여 효율성을 높이고 비용을 절감합니다. 또한 이 과정에서 모델 아키텍처를 개선하여, 처리 시 메모리 및 CPU 사용량을 줄이고 운영 안정성을 높이는 데 있어 상당한 이점을 입증했습니다.

서론

저희 데이터 레이크에서는 효율적인 액세스를 위해 팩트 테이블과 데이터 큐브가 시간별로 파티셔닝되어 있는 반면, 차원 테이블에는 이러한 파티셔닝이 없어 업데이트 시 팩트 테이블과 조인하는 데 많은 리소스가 소요됩니다. 조인의 키 스페이스는 조인 대상인 팩트 테이블의 시간 파티셔닝에 의해 결정됩니다. 해당 시간 분할에 존재하는 차원 엔티티는 전체 차원 데이터셋에 존재하는 엔티티의 작은 부분집합에 불과합니다. 그 결과, 이러한 조인 과정에서 셔플링되는 차원 데이터의 대부분은 결국 버려지게 됩니다. 이 과정을 최적화하고 불필요한 셔플링을 줄이기 위해 고유 조인 키에 블룸 필터를 적용하는 방안을 고려했으나, 필터 크기와 메모리 사용량 문제에 직면했습니다.

이를 해결하기 위해, 낮은 오탐률을 유지하면서 블룸 필터 크기를 줄여주는 머신러닝 기반 솔루션인 '학습형 블룸 필터(Learned Bloom Filters)'를 탐구했습니다. 이 혁신은 계산 비용을 줄이고 시스템 안정성을 향상시켜 조인 작업의 효율성을 높입니다. 다음 도식은 분산 컴퓨팅 환경에서 기존 방식과 최적화된 조인 프로세스를 보여줍니다.

학습형 블룸 필터를 활용한 조인 효율성 향상

팩트 테이블과 차원 테이블 간의 조인을 최적화하기 위해 학습형 블룸 필터 구현 방식을 채택했습니다. 팩트 테이블에 존재하는 키를 기반으로 인덱스를 구축한 후, 조인 연산 전에 차원 데이터를 사전 필터링하기 위해 해당 인덱스를 적용했습니다. 

기존 블룸 필터에서 학습형 블룸 필터로의 진화

기존 블룸 필터는 효율적이지만, 목표 오탐률을 달성하기 위해 이를 로드해야 하는 각 워커 노드당 15~25%의 추가 메모리를 소모합니다. 그러나 학습형 블룸 필터를 활용함으로써 동일한 오탐률을 유지하면서도 인덱스 크기를 상당히 줄일 수 있었습니다. 이는 블룸 필터를 이진 분류 문제로 변환했기 때문입니다. 양(positive) 레이블은 인덱스에 값이 존재함을 나타내고, 음(negative) 레이블은 존재하지 않음을 의미합니다.

머신러닝 모델을 도입함으로써 값에 대한 초기 검사가 용이해졌으며, 이어서 오탐지를 제거하기 위한 백업 블룸 필터가 작동합니다. 인덱스 크기가 줄어든 것은 모델의 압축된 표현 방식과 백업 블룸 필터에 필요한 키 수가 감소했기 때문입니다. 이는 기존의 블룸 필터 접근 방식과 차별화되는 점입니다. 

본 연구의 일환으로, 우리는 학습형 블룸 필터 접근법을 평가하기 위한 두 가지 지표, 즉 인덱스의 최종 직렬화 객체 크기와 조인 쿼리 실행 중의 CPU 사용량을 정립했다. 

구현 과제 해결

초기 과제는 팩트 테이블에 차원 테이블 키가 거의 없는, 편향이 심한 훈련 데이터셋을 처리하는 것이었습니다. 이를 분석한 결과, 테이블 간 키 중 약 3분의 1이 중복되는 것을 확인했습니다. 이를 해결하기 위해 샌드위치 학습형 블룸 필터(Sandwich Learned Bloom Filter) 접근법[2]을 활용했습니다. 이 방법은 초기 전통적인 블룸 필터를 통합하여 팩트 테이블에 누락된 대부분의 키를 제거함으로써 데이터셋 분포를 재조정하고, 데이터셋에서 부정 샘플을 효과적으로 제거합니다. 그 후, 초기 블룸 필터에 포함된 키와 오탐(false positives)만 "학습된 오라클(learned oracle)"이라고도 불리는 ML 모델로 전달되었습니다. 이 접근 방식은 학습된 오라클을 위한 균형 잡힌 훈련 데이터셋을 생성하여 편향 문제를 효과적으로 해결했습니다.

두 번째 과제는 모델 아키텍처와 훈련 특징량에 초점을 맞췄습니다. 피싱 URL의 고전적인 문제[1]와 달리, 우리의 조인 키(대부분의 경우 사용자/경험에 대한 고유 식별자)는 본질적으로 정보가 풍부하지 않았습니다. 이에 따라 우리는 차원 엔티티가 팩트 테이블에 존재하는지 예측하는 데 도움이 될 수 있는 잠재적 모델 특징량으로 차원 속성을 탐구하게 되었습니다. 예를 들어, 특정 언어의 경험에 대한 사용자 세션 정보를 포함하는 팩트 테이블을 생각해 보십시오. 사용자 차원의 지리적 위치나 언어 선호도 속성은 개별 사용자가 팩트 테이블에 존재하는지 여부를 판단하는 좋은 지표가 될 것입니다.

세 번째 과제인 추론 지연 시간(inference latency)을 해결하려면 오탐(false negatives)을 최소화하면서도 신속한 응답을 제공하는 모델이 필요했습니다. 이러한 핵심 지표에 대해 그라디언트 부스팅 트리(gradient-boosted tree) 모델이 최적의 선택이었으며, 정확도와 속도의 균형을 맞추기 위해 해당 모델의 특징 집합을 정리했습니다.

학습된 블룸 필터를 사용한 업데이트된 조인 쿼리는 다음과 같습니다:

결과

다음은 데이터 레이크에서 학습형 블룸 필터를 활용한 실험 결과입니다. 우리는 서로 다른 데이터 특성을 가진 5개의 프로덕션 워크로드에 이를 통합했습니다. 이 워크로드에서 가장 많은 연산 자원을 소모하는 부분은 팩트 테이블과 차원 테이블 간의 조인입니다. 팩트 테이블의 키 공간은 차원 테이블의 약 30% 수준입니다. 먼저, 최종 직렬화 객체 크기 측면에서 학습형 블룸 필터가 기존 블룸 필터보다 어떻게 더 우수한 성능을 보였는지 논의하겠습니다. 다음으로, 워크로드 처리 파이프라인에 학습형 블룸 필터를 통합하여 관찰된 성능 개선 사항을 보여드리겠습니다.

학습형 블룸 필터 크기 비교

아래에서 볼 수 있듯이, 주어진 오탐지율(false positive rate)을 기준으로 볼 때, 학습형 블룸 필터의 두 가지 변형은 기존 블룸 필터에 비해 전체 객체 크기를 17~42% 줄였습니다.

또한, 그라디언트 부스팅 트리 기반 모델에서 더 작은 특징 집합을 사용함으로써, 추론 속도를 높이는 동시에 최적화 성능의 손실은 미미한 수준에 그쳤습니다.

블룸 필터 사용 결과 분석 

이 섹션에서는 여러 지표를 통해 블룸 필터 기반 조인의 성능을 일반 조인의 성능과 비교합니다. 

아래 표는 학습형 블룸 필터를 사용한 경우와 사용하지 않은 경우의 워크로드 성능을 비교합니다. 총 오탐지 확률이 1%인 학습형 블룸 필터를 사용하여 두 조인 유형 모두 동일한 클러스터 구성을 유지한 상태에서 아래와 같은 비교 결과를 보여줍니다. 

첫째, 블룸 필터 구현이 일반 조인보다 CPU 사용 시간 측면에서 최대 60% 더 우수한 성능을 보인다는 사실을 확인했습니다. 학습형 블룸 필터 접근 방식의 경우, 블룸 필터를 평가하는 데 추가적인 연산 시간이 소요되어 스캔 단계의 CPU 사용량이 증가했습니다. 그러나 이 단계에서 수행된 사전 필터링 덕분에 셔플링되는 데이터의 크기가 줄어들었고, 이는 후속 단계의 CPU 사용량을 줄여 결과적으로 총 CPU 사용 시간을 감소시키는 데 기여했습니다.

둘째, 학습형 블룸 필터는 일반 조인에 비해 총 데이터 크기가 약 80% 적고, 기록되는 총 셔플 바이트 수도 약 80% 적습니다. 이는 아래에서 논의하듯이 더 안정적인 조인 성능으로 이어집니다. 

또한 실험 대상이었던 다른 프로덕션 워크로드에서도 리소스 사용량이 감소하는 것을 확인했습니다. 5개 워크로드 전체를 대상으로 2주 동안 측정한 결과, 학습형 블룸 필터 방식은 모델 훈련 및 인덱스 생성을 포함한 평균 일일 비용을 25% 절감했습니다.

조인 수행 시 셔플되는 데이터 양이 감소함에 따라, 분석 파이프라인의 운영 비용을 대폭 절감하는 동시에 안정성을 높일 수 있었습니다. 다음 차트는 실험 대상이었던 5가지 워크로드에 대해 2주 동안 일반 조인 워크로드와 학습된 블룸 필터 기반 워크로드의 실행 시간(실시간) 변동성(변동계수 사용)을 보여줍니다. 학습형 블룸 필터를 사용한 실행은 더 안정적이었으며(소요 시간이 더 일관적이었음), 이는 이를 더 저렴한 일시적이고 신뢰도가 낮은 컴퓨팅 리소스로 이전할 가능성을 열어줍니다. 

참고 문헌

[1] T. Kraska, A. Beutel, E. H. Chi, J. Dean, 및 N. Polyzotis. 학습된 인덱스 구조의 필요성. 《https://arxiv.org/abs/1712.01208》, 2017.

[2] M. Mitzenmacher. 샌드위치 기법을 이용한 학습형 블룸 필터 최적화. 

https://arxiv.org/abs/1803.01474, 2018.

¹2023년 6월 30일 종료된 3개월 기준

²2023년 6월 30일 종료된 3개월 기준