[Apache Hudi] 동적 블룸 필터
Performance · 테이블 크기를 예측하기 어려울 때 파일을 효율적으로 건너뛰는 Apache Hudi의 동적 블룸 필터(Dynamic Bloom Filter) 5분 코드 분석
Apache Hudi 소개
Apache Hudi는 ACID 트랜잭션, 인덱싱 등 데이터베이스의 핵심 기능을 데이터 레이크에 제공하는 오픈소스 데이터 레이크하우스 플랫폼이다. 클라우드 스토리지 환경에서 페타바이트 규모의 데이터 Upsert 처리에 있어 탁월한 성능을 발휘하는 프레임워크다.
블룸 필터(Bloom Filter) 소개
블룸 필터는 특정 원소가 집합에 속하는지 여부를 검사하는 확률적 자료구조다. “이 항목이 현재 집합에 포함되어 있는가?”라는 질문에 대해 블룸 필터는 다음 두 가지 중 하나로 답한다.
No: 해당 항목은 집합에 절대 존재하지 않는다.
Maybe: 해당 항목이 존재할 가능성이 높지만, 실제 데이터와 대조하여 확인이 필요하다.
블룸 필터를 사용하면 거짓 양성(False Positive, ‘Maybe’인 경우)이 발생할 확률을 일부 감수하는 대신 메모리 사용량을 크게 줄일 수 있다. Bloom Filters page를 참고하면 시각적인 설명을 통해 보다 쉽게 이해할 수 있다.
Apache Hudi의 블룸 필터 활용 방식
Apache Hudi는 Upsert 작업 시 불필요한 파일을 건너뛰기 위해 블룸 필터를 활용한다. 새로운 레코드가 들어오면, Hudi는 해당 레코드가 이미 테이블에 존재하는지(Update) 아니면 새로운 레코드인지(Insert)를 판단해야 한다. 이때 모든 데이터 파일에서 레코드 키를 직접 조회하는 것은 과도한 I/O를 유발한다.
대신 Hudi는 데이터 파일의 메타데이터에 레코드 키에 대한 블룸 필터를 저장해 두고, 데이터를 실제로 읽기 전에 블룸 필터를 통해 레코드 존재 가능성을 먼저 확인한다. HoodieKeyLookupHandle 클래스가 이 과정을 담당한다.
apache/hudi:HoodieKeyLookupHandle.java#L80-L90
블룸 필터 확인 결과 레코드 키가 존재하지 않는다면(‘No’), 해당 파일은 안전하게 건너뛴다. 존재할 가능성이 있다면(‘Maybe’), 해당 키를 후보 리스트에 추가하여 이후 실제 데이터와 대조하는 검증 과정을 거친다.
mightContain 메서드는 키가 블룸 필터에 존재할 가능성이 있는지 테스트한다.
apache/hudi:HoodieDynamicBoundedBloomFilter.java#L102-L105
→ apache/hudi:InternalDynamicBloomFilter.java#L115-L128
→ apache/hudi:InternalBloomFilter.java#L153-L167
블룸 필터의 한계
일반적인 블룸 필터는 생성 시 용량을 미리 지정해야 한다는 근본적인 한계가 있다.
google/guava:BloomFilter.java#L411-L435
블룸 필터의 크기(할당할 비트 수와 해시 함수 수)를 최적화하려면, 테이블의 예상 레코드 수와 허용 가능한 거짓 양성률(False Positive Rate)을 미리 결정해야 한다.
google/guava:BloomFilter.java#L525-L554
만약 블룸 필터의 용량보다 더 많은 레코드가 삽입되면, 거짓 양성 확률이 급격히 증가하여 결국 불필요하게 많은 파일을 읽게 되는 결과를 초래한다. 일반적인 데이터 워크로드에서 테이블의 레코드 수를 정확히 예측하는 것은 거의 불가능에 가깝다. 그렇다고 필터 크기를 무작정 크게 잡으면 메모리와 저장 공간이 낭비된다.
데이터셋의 크기를 미리 알 수 없는 상황에서, 어떻게 하면 효과적이면서도 효율적인 블룸 필터를 구성할 수 있을까?
해결 접근 방식
Hudi는 필요에 따라 확장 가능한 블룸 필터 체인을 배열 형태로 관리하는 방식을 사용한다. 이 솔루션은 크게 두 단계로 동작한다:
성장 단계: 레코드 수가 현재 필터의 용량을 초과하면, 새로운 필터를 할당하여 체인에 연결한다. 각 필터는 초기에 설정된 거짓 양성률을 유지한다.
포화 단계: 레코드 수가 설정된 최대 용량에 도달하면 필터 확장을 멈추고, 기존 필터들에 라운드 로빈(Round-robin) 방식으로 레코드를 분산 기록한다. 거짓 양성률은 다소 증가할 수 있지만, 메모리 사용량을 예측 가능한 범위 내로 유지할 수 있다.
이러한 설계는 블룸 필터의 무제한 성장으로 인한 OOM(Out of Memory) 발생 위험을 피하는 대신 성능 저하를 선택하는 디자인을 반영한다.
구현 방식
InternalDynamicBloomFilter 초기화
InternalDynamicBloomFilter는 matrix라는 2차원 배열을 사용하며, 각 요소는 비트 벡터(Bit vector)를 포함하는 InternalBloomFilter 객체다. 초기화 시점에는 하나의 필터로 시작한다. 필터 확장 시 메모리 재할당 및 복사 비용을 제어하기 위해 ArrayList 대신 배열(Array)을 사용한다.
apache/hudi:InternalDynamicBloomFilter.java#L56-L75
nr(Number of Records per Filter): 각 필터의 용량이다. 이 값을 초과하면 새로운 필터가 생성된다.maxNr(Max Number of Records total): 모든 필터 용량의 총합으로, 동적 블룸 필터가 가질 수 있는 절대적인 레코드 수 상한선이다.
새 레코드 할당 로직
Hudi는 현재 필터의 용량과 전체 최대 레코드 수(maxNr)에 따라 새 레코드를 저장할 적절한 블룸 필터를 결정한다.
apache/hudi:InternalDynamicBloomFilter.java#L236-254
위 코드는 다음 세 가지 경우를 처리한다.
reachedMax == true: 이미 최대 용량에 도달한 상태. 이후 삽입되는 레코드는curMatrixIndex++ % matrix.length를 통해 기존 필터들에 순환적으로 분산 저장된다.현재 필터가 가득 찼지만, 확장이 가능한 경우:
null을 반환하여 호출자가 새로운 필터를 할당하도록 유도한다.(matrix.length * nr) < maxNr조건으로 확장 가능 여부를 확인한다.현재 필터에 여유가 있는 경우: 가장 최근에 추가된 필터인
matrix[matrix.length - 1]을 반환하여 계속 사용한다.
아래는 이 알고리즘의 상태 변화를 나타낸 다이어그램이다.
동적 블룸 필터에 레코드 키 추가
add() 메서드는 getActiveStandardBF()가 반환한 필터에 레코드 키를 추가한다.
apache/hudi:InternalDynamicBloomFilter.java#L77-L94
getActiveStandardBF()가 null을 반환하면 현재 필터가 가득 찼음을 의미하므로, addRow()를 호출하여 matrix에 새로운 필터를 추가한다.
apache/hudi:InternalDynamicBloomFilter.java#L210-218
모든 필터에서 키 존재 여부 확인
테이블에 특정 레코드가 존재하는지 확인하려면 matrix에 있는 모든 필터를 검사해야 한다. 그중 하나라도 true를 반환하면 해당 키가 존재할 가능성이 있다고 판단한다.
apache/hudi:InternalDynamicBloomFilter.java#L115-128
키 존재 여부 확인 시간은 필터 개수에 비례하여 증가하지만, 합리적인 상한선을 통해 파일을 건너뛰어 절약할 수 있는 I/O 이득이 훨씬 크다.
기본 구성 요소인 InternalBloomFilter
matrix의 열은 InternalBloomFilter 객체로, Apache Hadoop의 구현 방식과 비슷하다.
apache/hudi:InternalBloomFilter.java:L108-L120
키 해시 값의 비트를 bits 벡터의 각 값으로 저장한다.
apache/hudi:InternalBloomFilter.java#L122-L139
키의 존재 여부는 nbHash개의 비트 위치를 모두 확인하여 판단한다. add() 메서드는 키 추가 시 해당 비트들을 모두 1로 설정하므로, 검사 중 0인 비트가 하나라도 발견되면 해당 키는 확실히 존재하지 않음을 보장할 수 있다.
apache/hudi:InternalBloomFilter.java#L153-L167
핵심 설계 결정
시스템 중단보다 성능 저하 선택. 분산 시스템에서 메모리 사용량이 무한정 증가하면 OOM(Out of Memory)이 발생한다. Hudi는 시스템이 다운되는 것보다는 거짓 양성률이 높아져 I/O가 다소 증가하더라도 시스템이 계속 동작하는 쪽을 선택했다.
예측 가능한 쓰기 지연 시간(Write Latency) 유지. 일반적인 가변 크기 블룸 필터는 용량이 찰 때마다 기존 레코드를 모두 재해싱(Re-hashing)해야 하므로, 순간적으로 작업 시간이 길어질 수 있다. Hudi는 새로운 필터를 체인처럼 연결하는 방식을 사용하여 재해싱 비용을 없애고, 쓰기 성능을 일정하게 유지한다.
성능 저하의 균등 분산. 블룸 필터의 총 용량이 가득 찼을 때, 레코드 키를 라운드 로빈 방식으로 분산 저장한다. 만약 하나의 블룸 필터만 계속 채운다면 해당 필터는 곧 모든 비트가 1이 되어 항상 “Maybe”를 반환하게 되고, 사실상 필터로서의 기능을 상실한다. 라운드 로빈 방식은 모든 필터의 포화도를 비슷하게 유지하여, 거짓 양성률이 급격히 나빠지지 않고 점진적으로 증가하도록 돕는다.
동적 블룸 필터의 효과
동적 블룸 필터를 통해 Hudi는 데이터셋의 크기를 미리 정확히 알지 못해도 Upsert 작업 시 파일을 효율적으로 건너뛸 수 있다. 사용자가 블룸 필터 크기를 매번 튜닝할 필요 없이, 설정된 범위 내에서 필터가 데이터 양에 맞춰 자동으로 적응한다. 이는 Hudi가 다양한 페타바이트 규모의 테이블에서도 효율적인 인덱싱과 고성능 Upsert를 유지할 수 있는 비결 중 하나다.
주요 기여자
PR #976: [HUDI-106] Adding support for DynamicBloomFilter by @nsivabalan (Sivabalan Narayanan)
PR #9649: [HUDI-6826] Port BloomFilter classes from Hadoop library by @yihua (Y Ethan Guo)