사전 블룸 필터
자료구조

블룸 필터

gabury1

블룸 필터는 어떤 값이 집합 안에 있는지를 아주 적은 메모리로 물어보는 자료구조입니다. 비트를 늘어놓은 배열 하나가 전부입니다. 답은 두 갈래로만 나옵니다. 확실히 없거나, 아마 있거나.

쉽고 빠른 이해

블룸 필터는 어떤 값이 집합에 있는지를 아주 적은 메모리로 물어보는 자료구조입니다. 값 자체를 저장하지 않고 비트 배열 하나만 둡니다. 예를 들어 RocksDB 는 파일마다 이 배열을 하나씩 붙여 없는 값을 찾으러 디스크를 읽는 일을 건너뜁니다.

왜 이렇게 하나. 집합이 아주 크면 값을 전부 저장해 두고 하나씩 대조하는 데 시간과 메모리가 많이 듭니다. 디스크까지 매번 읽어야 하면 그 비용이 더 커집니다. 비트 몇 개로 답을 낼 수 있으면 그 확인을 대부분 건너뛸 수 있습니다.

어떻게 도나.

  1. 값을 넣을 때 해시 함수 여러 개로 비트 배열 안의 자리(비트 주소) 여러 개를 뽑아 그 자리를 1 로 세웁니다
  2. 값을 물을 때도 같은 방식으로 비트 주소를 뽑아 전부 1 인지 봅니다
  3. 하나라도 0 이면 확실히 없는 것이고, 전부 1 이면 아마 있는 것입니다

대가. 답이 틀릴 수 있습니다 — 없는 값을 있다고 잘못 답하는 일이 생깁니다(그 반대는 없습니다). 그리고 한 번 세운 비트는 누가 세웠는지가 안 남아서, 담긴 값을 다시 꺼내거나 목록으로 훑거나 하나만 지울 수 없습니다.

상세

블룸 필터는 비트 배열 하나와 서로 다른 해시 함수 여러 개로 집합의 멤버십(어떤 값이 그 집합 안에 있는지)을 판정하는 자료구조입니다. Burton Bloom 이 1970년 논문에서 내놓았습니다. 논문은 해시 영역을 칸으로 나누는 기존 방식 — 항목마다 저장할 칸을 따로 하나씩 두는 재래식 해싱 — 에서 완전히 벗어난다고 적습니다. 해시 영역을 0 부터 n-1 까지 주소가 붙은 n 개의 낱낱 비트로 봅니다.

절차는 둘입니다. 넣기와 묻기. 원 논문은 집합에 넣는 값을 메시지라고 부릅니다 — 이 문서도 원 논문을 옮기는 대목에서는 그 말을 그대로 씁니다.

  • 처음에 해시 영역의 모든 비트를 0 으로 둡니다
  • 저장할 메시지마다 서로 다른 비트 주소 d 개를 해시로 뽑습니다. a1, a2, …, ad 입니다
  • 그 d 개의 비트를 전부 1 로 세웁니다
  • 새 메시지를 시험할 때도 저장할 때와 같은 방식으로 비트 주소 d 개를 뽑습니다
  • d 개가 전부 1 이면 그 메시지를 받아들입니다(집합에 있다고 판정합니다). 하나라도 0 이면 물리칩니다(없다고 판정합니다)

d 가 3 인 필터입니다. 메시지마다 주소를 세 개씩 뽑습니다. 메시지 x 와 메시지 w 를 넣으면 비트 배열은 이렇게 갈립니다.

flowchart TD
    subgraph ARR["비트 배열 · 주소 0~7"]
        direction TD
        A0["주소 0<br/>0"] --- A1["주소 1<br/>1 · x"] --- A2["주소 2<br/>1 · w"] --- A3["주소 3<br/>0"] --- A4["주소 4<br/>1 · x·w"] --- A5["주소 5<br/>0"] --- A6["주소 6<br/>1 · x"] --- A7["주소 7<br/>1 · w"]
    end

이 상태에서 두 메시지를 묻습니다. 메시지 y 는 주소 1 · 3 · 6 을 봅니다 — 값은 1, 0, 1 이고 3 번이 0 이라 확실히 없다고 답합니다. 메시지 z 는 주소 2 · 4 · 6 을 봅니다 — 값은 1, 1, 1 로 전부 1 이라 아마 있다고 답합니다.

거짓 양성과 거짓 음성

넣은 메시지는 자기 비트 d 개를 스스로 1 로 세웠고, 그 비트는 다시 0 으로 돌아가지 않습니다. 그래서 넣은 것을 없다고 답하는 일 — 거짓 음성 — 은 일어나지 않습니다. 반대는 일어납니다. 넣은 적 없는 메시지도 자기 비트 d 개가 다른 메시지들이 세워둔 1 로 우연히 전부 덮일 수 있습니다. 이때는 없는 것을 있다고 답하는데, 이것을 거짓 양성이라고 부릅니다. 블룸 필터는 거짓 양성만 냅니다.

훑기와 지우기의 제약

배열에 남는 것은 비트뿐입니다. 무엇이 그 비트를 세웠는지는 어디에도 적히지 않습니다. 그래서 담긴 것을 다시 꺼내거나 목록으로 훑을 수 없습니다. 지우기도 안 됩니다. 비트 하나를 0 으로 되돌리면 그 비트를 함께 쓰던 다른 메시지까지 없는 것이 되어 거짓 음성이 생깁니다. 이 두 제약을 각각 뚫으려는 시도가 갈래 절의 변종들입니다.

복잡도

삽입과 조회는 해시 함수 개수 d 에만 비례하고, 원소 수가 아무리 늘어도 시간과 공간은 그대로입니다. 대신 늘어나는 것은 거짓 양성 비율입니다 — 이것이 이 자료구조가 맞바꾼 자리입니다.

세는 대상을 먼저 밝힙니다. n 은 해시 영역의 비트 개수입니다. d 는 메시지 하나에 뽑는 비트 주소의 개수, 곧 해시 함수의 개수입니다. 원소 수는 지금까지 넣은 메시지의 개수입니다. 아래 표의 "d 에 비례"는 원 논문이 잰 시간 단위를 따릅니다 — 비트 주소 하나를 계산하고 그 비트를 읽어 확인하는 것 하나가 한 단위입니다. 블룸 필터에서 그 확인은 비트 내용이 1 인지 보는 것뿐입니다.

연산 평균 최악 왜 그 값인가
넣기 d 에 비례 d 에 비례 비트 주소 d 개를 뽑아 d 개를 세웁니다. 원소 수와 무관합니다
묻기 · 있다고 답할 때 d 에 비례 d 에 비례 d 개를 전부 확인해야 1 인지 알 수 있습니다
묻기 · 없다고 답할 때 d 보다 적습니다 d 에 비례 0 인 비트를 만나는 순간 물립니다
공간 n 비트 n 비트 해시 영역 자체가 전부입니다. 원소도 해시값도 따로 저장하지 않습니다

d 와 기대 오류 비율

원 논문은 어느 지점까지는 d 가 클수록 기대 오류 비율이 작아진다고 적습니다. 그 지점이 수확 체감이 시작되는 자리입니다. d 를 1 늘리는 것이 해시 영역에서 1 인 비트의 비율을 너무 크게 키우는 순간입니다. 비트가 1 로 빽빽해질수록 넣은 적 없는 메시지의 d 개 비트가 우연히 전부 1 로 덮일 확률이 올라갑니다.

그래서 주어진 해시 영역 크기 n 에 대해 도달할 수 있는 기대 오류 비율(실제로 나오는 오류의 비율)의 최솟값이 있습니다. 원 논문은 이 성질 때문에 블룸 필터가 오류 없이는 동작할 수 없다고 적습니다. 앞서 말한, 항목마다 칸을 하나씩 두는 기존 방식은 다릅니다 — 허용 오류 비율(미리 정해 두는 오류 기준)을 아주 작게 잡도록 고치면 실제로 오류 없이 동작할 수 있습니다. 블룸 필터에는 그 길이 없습니다.

최악이 오는 조건

시간 쪽 최악은 얕습니다. 어느 경우에도 비트 d 개를 넘게 만지지 않습니다. 실무에서 아픈 최악은 답의 품질 쪽에 있습니다. 넣은 원소 수에 견주어 n 이 모자라면 비트가 1 로 차오르고, 그러면 묻는 것마다 아마 있다고 답하기 시작합니다. 시간 복잡도는 그대로인 채 필터가 거르는 일을 그만두는 상태입니다.

예시

실제로 어떤 값을 넣어 부르는지 두 구현의 설정 한 벌씩을 봅니다. 어느 시스템이 왜 이를 채택했는지는 사용처 절에서 다룹니다.

RocksDB 의 NewBloomFilterPolicy

C++
NewBloomFilterPolicy(10, false));
my_cf_options.table_factory.reset(rocksdb::NewBlockBasedTableFactory(table_options));

RocksDB 위키는 이 설정이 키 하나당 약 10 비트의 공간을 쓰는 필터를 만든다고 적습니다. 많은 작업 부하에 잘 맞는 값이라고 적습니다. 키 하나당 비트 수는 1 에서 20 이상까지 연속으로 조절할 수 있습니다. 값을 올리면 DB::Get, 그리고 prefix bloom(키의 접두어만 걸러 보는 블룸 필터)을 쓰는 Seek 에 딸린 입출력과 CPU(Central Processing Unit, 중앙처리장치)와 블록 캐시 교체(캐시에 올라온 항목이 자주 밀려나고 다시 채워지는 것)가 줄어드는 이득이 있다고 적습니다.

같은 문서가 값과 거짓 양성률의 대응을 이렇게 적습니다. 오른쪽 「100 비트 대비 효과」 칸은, 키 하나당 100 비트를 쓰는 필터가 거짓 양성을 억누르는 힘을 100퍼센트로 놓았을 때 그 줄의 설정이 몇 퍼센트만큼 그 힘을 내는지를 나타냅니다. 이 칸의 값은 100 에서 거짓 양성률(퍼센트 숫자)을 뺀 것과 같습니다 — 거짓 양성률이 낮을수록 100 비트 필터에 그만큼 가까운 효과를 낸다는 뜻입니다.

키 하나당 비트 거짓 양성률 100 비트 대비 효과
1.5 50% 50%
2.9 25% 75%
4.9 10% 90%
9.9 1% 99%
15.5 0.1% 99.9%

PostgreSQL 의 bloom 인덱스

SQL
CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
       WITH (length=80, col1=2, col2=2, col3=4);

PostgreSQL 공식 문서의 예제입니다. 여기서 시그니처란 인덱스 대상 속성을 손실 있게 나타낸 비트열입니다 — 그래서 시그니처만으로는 거짓 양성을 보고할 수 있습니다. 시그니처 길이를 80 비트로 두고, 속성 i1 과 i2 를 각각 2 비트에, 속성 i3 을 4 비트에 대응시킨 인덱스가 만들어집니다. length 는 인덱스 항목 하나의 시그니처 길이입니다. 16 의 배수로 올림되고, 기본값은 80 비트, 최대는 4096 입니다. col1 부터 col32 까지는 인덱스 칼럼마다 만들어 낼 비트 수입니다. 기본값은 2 비트, 최대는 4095 입니다.

갈래

원래 필터가 못 하는 두 가지가 축입니다. 하나는 지우기, 하나는 나중에 늘리기입니다. 변종은 각각을 뚫으려고 무엇을 더 들고 있을지 정합니다.

카운팅 블룸 필터

Fan, Cao, Almeida, Broder 의 Summary Cache 논문이 내놓았습니다. 이 논문의 상황에서는 프록시 하나하나가 자기가 캐시한 문서를 나타내는 블룸 필터를 들고 있습니다. 그래서 집합의 변화를 지원해야 했습니다. 원 블룸 필터는 자리 하나에 비트 1 개를 두지만, 카운팅 블룸 필터는 자리 하나에 그 비트가 1 로 세워진 횟수를 세는 카운터를 둡니다. 앞서 상세에서 든 메시지 x 와 w 를 다시 넣으면, 둘 다 주소 4 를 세웠으므로 그 자리의 카운터만 2 가 되고 나머지 자리는 1 이거나 0 입니다.

flowchart TD
    subgraph BLOOM["블룸 필터 · 자리 하나 = 비트 1개"]
        direction TD
        A1["주소 1<br/>1 · x"] --- A2["주소 2<br/>1 · w"] --- A4["주소 4<br/>1 · x·w"] --- A6["주소 6<br/>1 · x"] --- A7["주소 7<br/>1 · w"]
    end
    subgraph COUNT["카운팅 블룸 필터 · 자리 하나 = 카운터"]
        direction TD
        B1["주소 1<br/>c=1 · x"] --- B2["주소 2<br/>c=1 · w"] --- B4["주소 4<br/>c=2 · x·w"] --- B6["주소 6<br/>c=1 · x"] --- B7["주소 7<br/>c=1 · w"]
    end

논문은 해시 함수를 k 개로 적습니다. 앞 절의 d 와 같은 것입니다. 카운터는 전부 0 에서 시작합니다. 이 논문은 넣는 값을 앞서 쓴 '메시지' 대신 '키'라고 부릅니다 — 키 a 를 넣거나 지울 때, a 를 각 해시 함수에 넣어 나온 비트 주소마다 그 자리 카운터를 올리거나 내립니다 (논문 표기로는 c(h1(a)) 부터 c(hk(a)) 까지입니다. c 는 카운터 값이고 h1…hk 는 해시 함수 k 개입니다). 카운트가 0 에서 1 이 되면 대응하는 비트를 켜고, 1 에서 0 이 되면 끕니다. 그래서 필터가 그 프록시가 캐시하고 있는 문서 목록을 언제나 정확히 반영합니다.

카운터 하나의 폭이 대가입니다. 논문은 카운트당 4 비트를 주면 실용적인 크기에서 초기 삽입 동안 넘칠 확률이 극히 작다고 적습니다. 그리고 카운트가 15 를 넘으면 그냥 15 에 머물게 둘 수 있다고 적습니다. 다만 그렇게 두면 삭제가 많이 쌓인 뒤에 0 이 되어서는 안 될 카운트가 0 이 되어 필터가 거짓 음성을 내는 상황으로 이어질 수 있습니다. 원소가 여러 번 담길 수 있는 집합인 다중집합을 담는 스펙트럴 블룸 필터도, 자리마다 값을 세는 이 비슷한 접근을 쓴다고 스케일러블 블룸 필터 논문이 적습니다.

스케일러블 블룸 필터

Almeida, Baquero, Preguiça, Hutchison 의 2007년 논문이 내놓았습니다. 뚫으려는 자리는 크기를 미리 정해야 한다는 것입니다. 필터 크기는 저장할 원소 수와 원하는 거짓 양성 확률에 근거해 앞서 정해야 하고, 거짓 양성 확률을 올리지 않고서는 여분의 원소를 더 넣을 수 없습니다. 그래서 최대 집합 크기를 보수적으로, 때로는 몇 자릿수나 크게 잡게 되고 공간을 그만큼 흘립니다.

방식은 필터를 여러 개 잇는 것입니다. 스케일러블 블룸 필터는 평범한 블룸 필터 하나 이상의 연속으로 이루어집니다. 채움 비율 한도 — 필터 하나에 넣은 원소 수가 그 필터 크기에 비해 정해둔 상한을 넘지 못하게 막아 둔 선 — 때문에 필터가 차면 새 필터를 하나 덧붙이는데, 뒤에 붙는 필터일수록 최대 오류 확률을 등비수열로 더 조여서 만듭니다.

flowchart TD
    subgraph F1["필터 1"]
        B1["비트 배열 · 최대 오류 확률"]
    end
    subgraph F2["필터 2"]
        B2["비트 배열 · 최대 오류 확률이 더 조여짐"]
    end
    subgraph F3["필터 3"]
        B3["비트 배열 · 최대 오류 확률이 한 번 더 조여짐"]
    end
    F1 -- "채움 비율 한도에 닿으면 덧붙인다" --> F2
    F2 -- "채움 비율 한도에 닿으면 덧붙인다" --> F3
    B1 ==>|"질의는 각 필터마다 확인한다"| B2
    B2 ==>|"질의는 각 필터마다 확인한다"| B3

질의는 각 필터마다 있는지 확인하는 식으로 합니다. 그래서 필터가 이론상 끝없이 늘어나는 경우(무한 급수)를 가정해도, 필터 열 전체를 거칠 때 하나라도 거짓 양성이 나올 합성 확률은 미리 정해 둔 거짓 양성 확률 안에 머무릅니다.

사용처

RocksDB 의 SSTable

RocksDB 는 데이터를 SSTable(Sorted String Table, 정렬된 키를 담은 불변 디스크 파일)에 담고 그 파일마다 필터를 붙입니다. 없는 키를 찾으러 디스크를 읽는 일을 건너뛰려고 고른 자리입니다. 위키는 임의의 키 집합에 알고리즘을 적용해 블룸 필터라는 비트 배열을 만들 수 있고, 임의의 키에 대해 이 비트 배열로 그 키가 집합에 있을 수 있는지 아니면 확실히 없는지를 판정할 수 있다고 적습니다. BlockBasedTableOptions::cache_index_and_filter_blocks 를 켜지 않으면 SSTable 이 닫히는 순간 필터가 메모리에서 내려갑니다. 켜면 블록 캐시에 필터가 남습니다. 6.15.0 판부터는 NewRibbonFilterPolicy 로 만드는 리본 필터라는, 그대로 바꿔 끼울 수 있는 대체물도 있습니다. 블룸 필터 공간, 그중에서도 메모리를 약 30% 아끼는 대신 필터에서 CPU 를 서너 배 쓴다고 적습니다.

PostgreSQL 의 인덱스 접근법

PostgreSQL 은 bloom 확장으로 블룸 필터에 기반한 인덱스 접근법을 제공합니다. 인덱스 생성 시점에 크기가 정해지는 시그니처로 맞지 않는 튜플을 빠르게 제외하려고 고른 자리입니다. 시그니처는 인덱스 대상 속성을 손실 있게 나타낸 것이라 거짓 양성을 보고할 수 있습니다. 그래서 인덱스 검색 결과는 언제나 원본 테이블 저장소(PostgreSQL 이 부르는 이름으로 힙)의 실제 속성 값으로 다시 확인해야 한다고 문서가 적습니다. 이 접근법은 유니크 인덱스를 지원하지 않고 NULL 값 검색도 지원하지 않습니다.

Apache Cassandra 의 읽기 경로

Cassandra 는 읽기 경로에서 디스크의 SSTable 과, 메모리의 memtable(아직 디스크에 쓰이지 않은 최근 쓰기를 담아 두는 메모리 내 자료구조)을 합칩니다. 요청된 파티션을 찾겠다고 SSTable 데이터 파일을 전부 확인하는 일을 피하려고 블룸 필터를 씁니다. 문서는 이 자료구조가 두 가지 상태 중 하나를 판정하게 해준다고 적습니다. 데이터가 주어진 파일에 확실히 없거나, 아마 있거나입니다. 블룸 필터는 데이터가 그 SSTable에 있다고 보장하지는 못합니다. 대신 메모리를 더 쓰게 해서 더 정확하게 만들 수 있습니다.

손잡이는 테이블 옵션 bloom_filter_fp_chance 입니다. 0 과 1 사이의 실수로 테이블마다 조절합니다. 기본값은 컴팩션(compaction, 여러 SSTable 을 합치고 오래된 값을 정리해 다시 쓰는 배경 작업) 전략 중 LeveledCompactionStrategy 를 쓰는 테이블이 0.1, 나머지가 0.01 입니다. 필터는 메모리에 있되 (자바 실행 환경이 관리하는 메모리 영역인) 힙 바깥에 놓입니다. 그래서 최대 힙 크기를 고를 때 블룸 필터를 셈에 넣지 않아야 한다고 문서가 적습니다 — 앞서 PostgreSQL 대목에서 나온 힙(원본 테이블 저장소)과는 다른 뜻입니다. 필터는 파일을 쓸 때 계산되어 SSTable 의 filter 컴포넌트로 디스크에 남습니다. ALTER TABLE 로 값을 바꾸면 디스크의 새 파일부터 새 값으로 쓰이고, 이미 있는 SSTable 은 컴팩션될 때까지 바뀌지 않습니다.

두 시스템 다 필터가 메모리 한 곳에만 있지 않습니다. 디스크의 원본과 메모리의 사본이 따로 있고, 둘이 언제 같아지는지가 시스템마다 다릅니다.

flowchart TD
    W(["Cassandra · SSTable 를<br/>쓰는 시점"])
    subgraph MEM["메모리"]
        direction TB
        RM["RocksDB · 블록 캐시<br/>cache_index_and_filter_blocks 를<br/>켰을 때만 상주"]
        CM["Cassandra · 힙 바깥 메모리"]
    end
    subgraph DISK["디스크"]
        direction TB
        RD["RocksDB · SSTable<br/>파일이 닫히면 필터가 내려간다"]
        CD["Cassandra · SSTable 의 filter 컴포넌트<br/>ALTER TABLE 후에도 컴팩션 전까지 옛 값 그대로"]
    end
    RD -. "열려 있는 동안 읽어 들인다" .-> RM
    W -. "계산해 둘 다에 남긴다" .-> CM
    W -. "계산해 둘 다에 남긴다" .-> CD

둥근 상자(쓰는 시점)는 자리가 아니라 순간입니다 — Cassandra 가 필터를 계산해 메모리와 디스크 양쪽에 동시에 남기는 그 시점을 가리킵니다.

관련 항목

이것이 속한 분류와 이루는 요소

자료구조 · 해시 함수

이것의 하위 종류

카운팅 블룸 필터 · 스케일러블 블룸 필터 · 스펙트럴 블룸 필터

이것을 실제로 채택하거나 대신하는 제품·기술

RocksDB · PostgreSQL · Apache Cassandra · 인덱스 · 리본 필터

이것이 저장되는 저장소와 값이 새로 계산되는 시점

SSTable · 블록 캐시 · memtable · 컴팩션

다른 이름: Bloom filter · 블룸필터