[Redis] Bloom Filter

[Bloom Filter란]

Bloom Filter는 어떠한 값이 특정 데이터 집합에 속하는지를 판단하는데 사용하는 확률적 자료구조이다.
주로 데이터 집합의 크기가 매우 커서 데이터가 집합에 속해있는지 판단하는데 오래걸리는 경우 Bloom Filter를 사용한다.

  

그러나 언제나 정확한 값을 도출하지는 않는다. false nagative는 없으나 false positive가 발생할 수 있다.
즉, 집합에 속한것이 없는데 있다고 할 수는 있어도 있는걸 없다고 할일은 절대 없기 때문에
Bloom Filter에서 '이거 있어?'에 대한 대답은 '확실히 이건 없어요' 혹은 '있는거 같은데요'만 있다. '이거 있어요!'는 없다.
'있는거 같은데요'의 경우 확실히 있는지 알기위해서는 실제 데이터베이스에 접근하여 데이터 존재 여부를 정확히 판단하면 되므로 전체 시스템 구성에서 오류 발생률은 0%이다. (보통 Bloom Filter는 real DB 앞단에 구성되기때문)

  

Bloom Filter 말고도 Hash Table, AVL Tree, RB tree와 같은 오류 발생률 0%의 자료구조들도 있지만
Bloom Filter를 사용하는 이유는 바로 적은 메모리 사용을 통한 속도향상이다.
그러나 또 다른 특징중 하나는 데이터 집합에 원소를 삭제하는것이 불가능하다는 것이다.

  

Bloom Filter와 같은 용도에 삭제까지 가능한 자료구조가 있다.
바로 Cuckoo Filter라는 확률적 자료구조인데 성능에는 약간 차이가 있다.
Bloom Filter는 원소를 삽입 할 때 성능이 좋기 때문에 데이터 집합에 원소를 자주 추가하는 경우 사용하면 좋다.
반면 Cuckoo Filter는 데이터 조회가 더 빠르며 삭제도 가능하다.

[Bloom Filter 적용 사례]

- Chrome은 악성 URL을 확인하기위해 사용.
- Medium은 기사가 이미 유저에게 추천되었는지 확인하기위해 사용.
- Ethereum Blockchain 로그를 빠르게 찾기위해 사용.
- PostgreSQL과 Google Bigtable은 존재하지 않는 튜플 또는 컬럼을 찾는데 디스크 탐색을 줄이기 위해 사용.

[Redis에 Bloom Filter 설치]

Redis에서 BloomFilter는 기본적으로 내장된 자료구조가 아니다.

때문에 모듈을 redis server에 로드해서 사용해야한다.

RedisBloom 모듈의 소스코드를 다운받는다.

빌드하면 so 파일이 생성된다.

 /etc/redis/redis.conf 파일에 RedisBloom 모듈을 추가해준다.

서비스를 재시작한다.

RedisBloom 모듈은 여러 자료구조를 지원한다.

• Bloom Filter

• Cuckoo Filter

• Count-Min Sketch

• Top-K

[Bloom Filter 사용법]

• BF.RESERVE : 빈 key를 생성하며 false positive 발생률, 원소의 갯수 등 옵션을 설정할 수 있다.
  포맷 - BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion] [NONSCALING]

  key [필수] : 키 이름 설정  
  error_rate [필수] : false positive 발생률을 설정하며 인자 1을 100%로 기준삼아 0.1을 주면 10%이고 0.001을 주면 false positive 발생률 0.1%을 의미한다.  
  capacity [필수] : 최대 원소의 갯수를 설정하며 이 기준을 초과할 때 성능은 하락할 수 있다.  
  expansion [옵션] : 최대 원소의 갯수 초과시 몇개의 원소를 추가로 받을지 설정하는 옵션  
  NONSCALING [옵션] : 최대 원소의 갯수 초과시 추가 원소를 받지 않는다는 옵션  

  

  집합	false positive	최대 원소의 갯수	추가원소 허용
  BlackList	0.1%	50000	불가능
  WhiteList	1%	30000	5000

• BF.ADD : key에 원소를 추가하며 없는 key라면 생성후 추가한다.
  포맷 - BF.ADD {key} {item}

    key [필수] : 키 이름 설정
    item [필수] : 삽입 할 원소

  

• BF.MADD : BF.ADD와 같으며 다량의 원소를 한번에 추가할 수 있다.
  포맷 - BF.ADD {key} {item} [item] [item] [item]

• BF.INSERT : BF.RESERVE와 BF.ADD를 합친것과 같다.
  포맷 - BF.INSERT {key} [CAPACITY {cap}] [ERROR {error}] [EXPANSION {expansion}] [NOCREATE] [NONSCALING] ITEMS {item...}

    key [필수] : 키 이름 설정
    cap [옵션] : 최대 원소의 갯수를 설정하며 이 기준을 초과할 때 성능은 하락할 수 있다.
    error [옵션] : false positive 발생률을 설정하며 인자 1을 100%로 기준삼아 0.1을 주면 10%이고 0.001을 주면 false positive 발생률 0.1%을 의미한다.
    expansion [옵션] : 최대 원소의 갯수 초과시 몇개의 원소를 추가로 받을지 설정하는 옵션
    NOCREATE [옵션] : 키가 존재하지 않는경우 키를 생성하지 않는다는 옵션
    NONSCALING [옵션] : 최대 원소의 갯수 초과시 추가 원소를 받지 않는다는 옵션
    item [필수] : 삽입 할 원소

• BF.EXISTS : 데이터 집합안에 해당 원소가 들어있는지 확인한다.
  포맷 - BF.EXISTS {key} {item}

    key [필수] : 키 이름 설정
    item [필수] : 삽입 할 원소

  

  존재하는것 같으면 1, 존재하지 않으면 0을 반환

• BF.MEXISTS : BF.EXISTS와 같으며 다량의 원소를 한번에 조회할 수 있다.
  포맷 - BF.EXISTS {key} {item} [item] [item] [item

* https://github.com/RedisBloom/RedisBloom/blob/master/docs/Bloom_Commands.md