지난 글 마무리에서 예고한 대로 이번 글에서는 Bloom filter를 알아보려고 합니다. LSM 트리 글에서 SSTable마다 붙여 둔다고 한 줄로 넘긴 그 필터를, 이번에는 비트 배열부터 봅니다.
1. min/max가 못 거르는 조회
1-1. 범위는 통계로 거른다
이 시리즈 앞쪽의 Parquet 글에서 Row Group마다 min, max 통계가 붙는다고 했습니다. WHERE age > 50이라면 max가 35인 Row Group은 열어 볼 필요가 없습니다. 이것이 Predicate Pushdown이었습니다.
이 방식은 범위를 거르는 데 강합니다. 반대로 점 조회에는 약합니다.
Row Group 1: user_id min=1 max=1,000,000
Row Group 2: user_id min=3 max=999,998
Row Group 3: user_id min=5 max=1,000,000
WHERE user_id = 424242
→ 세 Row Group 모두 범위 안에 들어감 → 하나도 못 건너뜀user_id가 정렬되지 않은 채 섞여 있으면 Row Group마다 min과 max가 전체 범위를 덮습니다. 424242가 실제로는 Row Group 2에만 있어도, 통계만 보고는 셋 다 열어야 합니다.
1-2. 점 조회는 "있나 없나"만 알면 된다
점 조회가 알고 싶은 것은 범위가 아니라 이 값이 이 파일 안에 있느냐입니다. 그 질문 하나에, 아주 적은 메모리로 답하는 구조가 Bloom filter입니다. 해시는 값이 같은지만 알려 주고 순서를 버리기 때문에 BETWEEN 같은 범위 조건에는 쓸 수 없습니다. 범위 조건은 1-1절의 min/max 통계가 그대로 맡습니다.
2. 비트 배열과 해시 함수 몇 개
2-1. 넣기
Bloom filter는 m비트짜리 배열 하나와 해시 함수 k개로 이루어집니다. 처음에는 모든 비트가 0입니다. 값을 하나 넣을 때마다 k개의 해시 함수로 위치를 k개 뽑아 그 자리를 1로 칠합니다.
m = 16, k = 3으로 가정해 보겠습니다.
초기 0000 0000 0000 0000
"Alice" 넣기: h1=2, h2=7, h3=12
0010 0001 0000 1000
"Bob" 넣기: h1=5, h2=7, h3=14
0010 0101 0000 1010
↑ 7번은 이미 1 (겹쳐도 그대로 1)배열에는 값 자체가 저장되지 않습니다. 몇 개의 비트가 켜졌다는 흔적만 남습니다. 그래서 값이 수억 개여도 필터 크기는 비트 수로 정해집니다.
2-2. 조회
조회할 때도 같은 해시 함수 k개로 위치를 뽑아 그 비트를 봅니다.
"Carol" 조회: h1=2, h2=5, h3=9
→ 9번이 0 → 확실히 없음
"Dave" 조회: h1=2, h2=7, h3=14
→ 셋 다 1 → 있을 수도 있음
(실제로는 Alice와 Bob이 칠해 둔 자리. 오탐)결과는 두 가지뿐입니다.
- 하나라도 0이면 확실히 없습니다. 그 값을 넣었다면 그 자리가 반드시 1이어야 하기 때문입니다
- 전부 1이면 있을 수도 있습니다. 다른 값들이 우연히 같은 자리를 다 칠해 뒀을 수 있습니다
즉 거짓 음성(있는데 없다고 답함)은 없고, 거짓 양성(없는데 있다고 답함)만 있습니다. Broder와 Mitzenmacher의 서베이 논문은 이 성질을 "no false negatives"라고 부릅니다. 오탐이 나도 결과가 틀리지는 않습니다. "있을 수도"라는 답을 믿고 실제 데이터를 열어 봤다가 없으면 지나갈 뿐이고, 디스크 읽기가 한 번 늘어나는 것이 비용의 전부입니다.
2-3. 삭제
값을 빼려면 그 값의 k개 비트를 0으로 되돌려야 할 것 같지만, 그러면 안 됩니다. 위 예시에서 Alice를 지우려고 7번을 0으로 만들면, 같은 자리를 쓰던 Bob까지 조회에서 "확실히 없음"이 됩니다. 거짓 음성이 생기는 순간 Bloom filter의 유일한 보장이 깨집니다.
삭제가 필요하면 비트 대신 작은 카운터를 두는 Counting Bloom filter를 씁니다. 넣을 때 더하고 뺄 때 빼는 방식이고, 서베이 논문은 Fan 등의 연구를 인용해 카운터당 4비트면 충분하다고 씁니다. 비트 하나 자리를 4비트 카운터가 차지하는 셈입니다.
3. 오탐률은 비트 수가 정한다
3-1. 공식
원소 n개를 m비트 배열에 해시 k개로 넣었을 때 오탐률은 대략 이렇습니다.
p ≈ (1 − e^(−kn/m))^km/n(원소 하나당 비트 수)이 클수록 오탐률이 내려갑니다. 해시 함수 개수 k는 너무 적으면 각 원소가 남기는 흔적이 약하고, 너무 많으면 배열이 금방 1로 차서 둘 다 오탐이 늘어납니다. 가장 좋은 지점은 k = (m/n) · ln 2이고, 그때 오탐률은 약 0.6185^(m/n)입니다.
3-2. 10비트면 1%쯤
원소당 10비트를 쓰면 이론값은 0.6185^10 ≈ 0.82%입니다. 실무에서 흔히 말하는 "10비트에 1%"가 여기서 나옵니다. 구현마다 숫자가 조금씩 다릅니다.
해시 함수와 블록 배치 방식이 달라서 같은 10비트라도 결과가 갈립니다. 대략 원소당 10비트, 오탐률 1% 안팎으로 기억하면 충분합니다.
3-3. 비트를 늘린다고 계속 좋아지지 않는다
비트를 두 배로 늘리면 오탐률은 제곱으로 줄어듭니다. 숫자로는 좋아 보이지만, 1%를 0.01%로 내려도 줄어드는 디스크 읽기는 전체의 1% 남짓입니다. RocksDB 위키는 이것을 diminishing returns라고 하고, 9.9비트로 이미 100비트를 썼을 때 효과의 99%를 얻는다고 합니다.
반대로 비용은 그대로 늘어납니다. Bloom filter 공간은 거의 전부 메모리에 올라갑니다. 키가 수십억 개인 DB에서 원소당 10비트와 20비트의 차이는 메모리 수 GB입니다.
4. RocksDB 안의 Bloom filter
4-1. 파일마다 하나씩
LSM 트리에서 키 하나를 찾으려면 memtable부터 마지막 레벨까지 여러 SSTable을 뒤져야 합니다. SSTable마다 Bloom filter가 있으면 대부분의 파일은 필터만 보고 건너뜁니다. 읽기 증폭을 막는 장치라 LSM에서는 사실상 필수입니다.
RocksDB는 기본적으로 키 전체의 해시를 필터에 넣습니다(whole_key_filtering). 그래서 이 필터는 Get처럼 찾을 키 전체를 아는 조회에만 듣습니다.
4-2. 버전별 필터 형식
RocksDB 필터는 버전에 따라 형식이 크게 달라졌습니다.
block-based filter는 키-값 2KB 단위마다 필터를 따로 두는 방식이었고, full filter는 SST 파일 하나에 필터 하나를 둡니다. 위키는 예전 구현이 오탐률 0.1%보다 좋아지지 못했던 반면, 새 구현은 키당 16비트로 0.1% 아래까지 내려간다고 적습니다.
Ribbon filter는 같은 오탐률을 더 적은 공간으로 내는 대안입니다. 위키에 따르면 1% 오탐률에 Bloom이 키당 약 9.9비트를 쓸 때 Ribbon은 약 7비트로, Bloom 대비 공간을 30%쯤 아끼는 대신 필터를 만드는 CPU가 3~4배 듭니다. 메모리가 빠듯하고 쓰기 CPU가 남는 쪽이라면 Ribbon이 유리합니다.
오래된 RocksDB 기반 시스템을 7.4 이후로 올릴 때는 block-based 필터로 만든 SST가 남아 있는지 먼저 확인해야 합니다. 데이터는 그대로 읽히지만 그 필터는 읽지 못해 조회 성능이 떨어지고, 위키는 이 경우 full compaction으로 필터를 새로 만들라고 안내합니다.
4-3. Prefix bloom은 조건이 붙는다
키 전체 해시 대신 키의 앞부분(prefix) 해시를 필터에 넣을 수도 있습니다. prefix_extractor를 설정하면 user:42: 같은 prefix 안에서 seek할 때도 필터로 파일을 건너뜁니다. LSM 글에서 RocksDB가 접두사 범위 스캔을 보완한다고 한 장치가 prefix bloom입니다.
다만 Prefix Seek 위키에 따르면 prefix bloom은 특정 prefix 안을 읽을 때만 쓸 수 있습니다. prefix를 넘어가는 범위를 읽으면서 prefix bloom을 켜 두면 RocksDB는 에러 없이 정의되지 않은 결과를 돌려줄 수 있습니다. 그래서 total_order_seek=true로 필터를 무시하게 하거나, 위키가 권하는 auto_prefix_mode를 쓰는 편이 안전합니다.
4-4. 마지막 레벨은 필터를 생략할 수 있다
optimize_filters_for_hits(기본 false)를 켜면 마지막 레벨의 필터를 저장하지 않습니다. 찾는 키가 대부분 실제로 존재하는 워크로드라면, 마지막 레벨에 도달한 조회는 어차피 데이터를 읽게 되니 필터가 도움이 안 됩니다. 데이터 대부분이 마지막 레벨에 있으므로 필터 메모리를 크게 줄일 수 있습니다.
5. 다른 곳의 Bloom filter
5-1. Parquet
Parquet은 format 2.7.0에서 Bloom filter를 스펙에 넣었습니다. 방식은 Split Block Bloom Filter로, 256비트 블록 여러 개로 나눠 두고 값 하나는 블록 하나 안에서만 비트를 칠합니다. 스펙은 이 블록 구조를 Putze 등의 캐시 효율 Bloom filter 논문에서 가져왔다고 적습니다. 해시는 xxHash(XXH64)를 씁니다.
Row Group마다 컬럼 단위로 붙기 때문에, 1장의 WHERE user_id = 424242처럼 min/max가 못 거르는 조회를 Bloom filter가 거릅니다. 다만 Parquet 필터는 쓰는 쪽에서 켜야 만들어집니다.
5-2. Iceberg
Iceberg 테이블은 테이블 속성으로 Parquet Bloom filter를 켭니다.
write.parquet.bloom-filter-enabled.column.user_id = true
write.parquet.bloom-filter-fpp.column.user_id = 0.01 (기본)
write.parquet.bloom-filter-max-bytes = 1048576 (기본)컬럼마다 명시해야 하고 기본은 꺼져 있습니다. 필터는 Iceberg 메타데이터가 아니라 Parquet 파일 안에 들어갑니다.
5-3. Cassandra와 PostgreSQL
Cassandra도 LSM 기반이라 SSTable마다 Bloom filter를 둡니다. 테이블 옵션 bloom_filter_fp_chance로 오탐률을 정하고, Cassandra 5.0 문서 기준 기본값은 0.01입니다.
PostgreSQL에는 contrib 확장으로 bloom 인덱스가 있습니다. 컬럼이 많은 테이블에서 쿼리가 임의의 컬럼 조합을 =로 걸 때 쓰라고 문서가 설명합니다. 컬럼 조합마다 B-tree를 만드는 대신 인덱스 하나로 버티는 용도이고, 연산자는 =만 지원합니다.
5-4. Spark 런타임 Bloom filter join
조인 글에서 본 shuffle 조인에도 Bloom filter가 들어갑니다. Spark 3.3부터, 조인의 한쪽에 선택도 높은 조건이 걸려 있으면 그쪽 조인 키로 Bloom filter를 만들어 반대편에 미리 적용하고, 짝이 없을 행을 셔플 전에 걸러 냅니다.
spark.sql.optimizer.runtime.bloomFilter.enabled
3.3: 기본 false
3.4+: 기본 true참고로 BigQuery는 Bloom filter를 사용자 설정으로 노출하지 않습니다. 내부에서 쓰는지는 공식 문서로 확인되지 않습니다.
마무리
키 하나를 찾으려고 SSTable 열 개를 뒤질 일을, Bloom filter는 원소당 10비트 남짓한 메모리로 한두 개로 줄입니다. 헛걸음은 1% 안팎이고, 범위 조회에는 쓸 수 없습니다. 찾는 키가 대부분 실제로 있는 워크로드라면 마지막 레벨에서는 그 10비트도 아깝고, 4-4절의 optimize_filters_for_hits가 그 계산에서 나온 옵션입니다.
다음 글에서는 1장에서 본 문제로 돌아가겠습니다. min/max 통계가 왜 정렬 없이는 거의 쓸모가 없는지, 그리고 Z-order 같은 다중 컬럼 정렬이 그것을 어떻게 살리는지까지 뜯어보겠습니다.