블룸필터 (BloomFilter, 대규모 시스템에서 값에 중복이 있는지 확인하는 방법)
배경
개발하면서 이미 존재하는 값인지(중복된 값이 있는지)를 확인하는 기능은 굉장히 흔히 볼 수 있다.
회원 가입 기능에서 유니크(unique)한 값으로 쓰이는 식별자 즉, ID 중복 검사 같은 것이 그 예다.
🤔 사실 뭐 복잡할 게 있나? 싶은 마음이 든다.
중/소규모 애플리케이션에서는 데이터베이스에 적당히 인덱스를 만들고 조회 쿼리만 잘하면 존재하는지 여부 정도는 금방 나오기 때문이다. (심지어 PK는 자동으로 인덱스가 생성되어있다!)
하다 못해 개발을 조금이라도 해본 사람이라면 선형적으로 하나하나 전체를 탐색하는 것이 느리기 때문에 해시 테이블, Set, Map, B-Tree, … 같은 자료구조를 사용한다는 것을 알고 있다.
하지만 대규모 시스템에서는 값이 존재하는지 확인하는 방법에 대한 고민이 필요하다.
구글에서 구글 계정 중복 검사를 한다고 생각해보자.
전 세계 인구가 몇 명이며 한 사람 당 만들 수 있는 계정은 또 몇 개일까?
중복 검사는 둘 째치고 구글 계정 자체를 저장하는데도 어마어마하게 큰 공간이 필요할 것이다. (문자열이라 용량도 많이 차지할 것이다.)
지금은 대용량 데이터를 저장하는 게 주제가 아니니 수 십, 수 백억 개의 계정은 어찌 됐든 저장했다 치자.
다시 조회로 돌아와서, 저장한 대용량 데이터를 조회하는데 위에서 언급한 자료구조로 해결한다고 하면 어떨까?
HashMap을 만들어 메모리에 올려놓고 검사할 때마다 조회를 한다? 그러면 메모리가 엄청나게 모자랄 것이다.
계정뿐만 아니라 이런 중복 검사가 필요한 경우 (식별자 역할을 갖는 도메인 속성(필드))가 얼마나 많을 것인가를 생각해보면 왜 대규모 시스템에서 값이 존재하는지 확인하는 방법을 고민해야 하는지 공감할 수 있을 것이다.
이러한 대용량 데이터에서 중복 검사를 빠르게 하면서 메모리 공간 문제를 해결할 수 있는 것이 블룸필터(Bloom Filter)다.
블룸필터
블룸필터 위키 정의를 살짝 수정하면 “어떤 값(value)이 집합에 속하는지 여부를 검사하는 필터 역할의 확률적 자료 구조”다.
눈여겨볼 것은 확률적인 자료 구조라는 것이다.
개발은 트레이드오프의 연속이다. (알아서 잘 깔끔하면서도 빠르고 정확하게 모든 요구사항을 만족하며 처리되는 기술은 없다.)
공간적 이득을 보는 대신 확률적인 결과(약간의 손해)를 갖는 자료 구조를 택한 것이다.
무슨 얘기냐면 어떤 값이 블룸필터를 거쳐서 중복이 있는지 판단할 때 “거짓 긍정”(False Positive = 실제로는 값이 존재하지 않지만 중복된 값이 있다고 판단하는 경우)이 발생할 수 있는 것이다.
대신 “거짓 부정”(실제로는 값이 있는데 중복이 아니라고 판단하는 경우)은 발생하지 않는 특징이 있다.
구조와 원리를 살펴보면서 왜 이런 일이 발생하는지 그리고 이런 특징이 어떤 사례에서 유의미하게 쓰이는지 알아보려고 한다.
원리
원리는 간단하다.
- 각기 다른 해시 함수 N개를 준비한다. (최소 3개 이상)
- 블룸 필터는 실제 값을 저장하지 않으므로 두 가지 케이스로 구분한다. (저장은 안 하고 boolean 배열을 사용한다.)
- 값(V)을 등록하는 경우
- 앞서 준비한 해시 함수 N개에 값(V)을 각각 해시하여 나온 결과(h1(V), h2(V), h3(V), …)를 불룸필터 비트 배열에 비트 값을 1(true)로 지정한다.
- 값이 존재하는지 찾는 경우
- 앞서 준비한 해시 함수 N개에 값(V)을 각각 해시하여 나온 결과(h1(V), h2(V), h3(V), …)를 계산하고 이에 대응되는 블룸필터 비트 배열의 비트 값이 모두 1로 표시되어 있으면 중복되는 값이
있을 수 있는 것이고, 단 하나라도 비트값이 0인 게 있으면 중복되는 값이 존재하지 않음을 보장한다.
- 앞서 준비한 해시 함수 N개에 값(V)을 각각 해시하여 나온 결과(h1(V), h2(V), h3(V), …)를 계산하고 이에 대응되는 블룸필터 비트 배열의 비트 값이 모두 1로 표시되어 있으면 중복되는 값이
- 값(V)을 등록하는 경우
이게 전부다.
확률적?! (있을 수 있다고 한 이유)
해시 함수는 충돌이 있을 수 있기 때문이다.
예를 들어 해시 함수 “h(x) = x % 7” 이라는 게 있을 때 아래 같이 값 12와 값 5의 결과가 같다.
- 12 % 7 = 5 → h(12) = b[5] = true;
- 5 % 7 =5 → h(5) = b[5] = true;
값 12를 블룸필터에 등록하여 비트 배열(b)의 5번째 공간(b[5])에 비트 값을 1로 설정했을 때, 값 5가 중복으로 존재하니?라고 조회했을 때 대응되는 비트 배열 위치는 b[5]이기 때문에 실제로 5는 등록된 적이 없지만, 블룸필터는 중복이 있을 수 있다고 판단한 것이다.
그렇기 때문에 해시 함수는 한 개가 아니다.
여러 개의 해시 함수가 있으면 전부 충돌해야만 “거짓 긍정”으로 판단하기에 해시 함수를 다양하게 두어야 충돌 확률을 낮출 수 있다.
해시 함수를 많이 두더라도 입력하고 검증해야 할 데이터의 양이 많을수록 충돌 확률이 늘어난다.
예시와 같이 7로 나눈 나머지는 0~6까지 총 7개의 비트만 사용하므로 충돌 확률이 높다.
데이터 양에 따라 해시 함수도 여러 개를 두고, 해시 함수 결과로 나타낼 비트 배열의 크기도 늘려야 할 것이다.
(공간과 해시 충돌 최적화를 위한 계산식이 위키 같은데 있으나 개발하는 입장에서는 굳이 수식까지 보지 않고 이 정도까지 이해하면 될 것 같아 생략한다. https://hur.st/bloomfilter/ ← 여기서 필요한 충돌 확률을 만들기 위한 해시 함수의 개수, 데이터 크기 등을 조절해보면서 최적화해볼 수 있다.)
최적화되지 않으면 주의해야 할 것은 데이터의 양이 너무 많아서 블룸필터 비트 배열을 전부 1로 만들어버리는 경우가 있다.
이 경우에는 모든 검사 대상 값에 중복이 있다고 리턴할 것이라 비트 배열의 상태를 확인해야 한다.
혹시 매번 학습(?)시켜야 되나요?
메모리에 있다고 그래서 프로세스를 껐다 킬 때마다 대용량 데이터를 다시 입력(학습)시켜야 하나? 이런 생각을 했다면 조금 더 생각을 해보자.
비트 배열 자체를 저장해놓으면 해결된다.
해시 함수 N개가 바뀌지 않는다는 전제하에 수 십억 건의 데이터를 열심히 블룸필터의 해시 함수를 돌려서 만들어 놓은 비트 배열을 재사용하면 된다.
활용 사례
Redis, HBase, … 등에서 사용되고 있다고 하는데 그게 중요한 게 아니라 개발자가 어떻게 활용할 수 있는지 알아본다.
기본적으로 크게 두 가지의 경우에서 활용할 수 있다.
- 데이터가 너무 많아서 RDB나 해시 테이블로는 해결이 안 되는 경우
- 거짓-긍정이 사용되어도 무방한 경우
구글 계정 회원 가입 같은 경우에는 실제로 ‘jeongpro’ 라는 아이디가 없어도 중복된다!라고 사용자에게 리턴해줘도 큰 문제가 없다. (거짓-긍정해도 무방)
그러나 사업자등록번호 같은 것은 실제로 중복되지 않는데 중복된다라고 하면 문제가 생길 수 있다.
그렇기 때문에 거짓-긍정이 가능한 경우에 적용해야 한다.
1. 빅데이터 범위 줄이기
출처 > https://meetup.toast.com/posts/192
빅데이터에서 특정 조건을 추출하는 경우에 데이터의 양이 너무 많으면 1차적으로 범위를 줄여주는데 블룸필터가 사용될 수 있다.
예를 들어 사용자 이력 중에 ‘페이코’ 사용자 목록을 뽑아서 데이터를 처리하고 싶은 경우에는 아래와 같이 플로우를 타면 효율적이다.
- 페이코 사용자 데이터를 가지고 블룸필터 생성
- 이 필터를 사용해서 사용자 이력 데이터 중 확실히 페이코 사용자가 아닌 것들 필터링 (무의미한 데이터 필터링)
- 필터링된 데이터에서 거짓-긍정에 의해서 페이코 사용자가 아닌 데이터만 거르는 방식으로 데이터 범위 축소
2. 특정 데이터 필터
배치 데이터 전처리기 느낌 말고 단순 애플리케이션 서비스에서도 활용 가능하다.
예를 들어서 크롬(Chrome) 브라우저에서 블랙리스트 URL(다크 사이트?)을 관리한다고 하면 URL을 입력했을 때 페이지 로드 전 블룸필터를 이용해볼 수 있다.
- 주기적으로 새로 생겨난 다크 사이트 URL 블룸필터에 입력하여 생성
- 사용자가 URL 입력 시, 블룸필터로 블랙리스트 빠르게 검사 가능 (안전한 사이트지만 안전하지 않은 사이트로 분류될 수 있음)
- 거짓 긍정에 의해서 분류된 것들은 추후 화이트 리스트로 관리할 수도 있음 (구글이 이렇게 한다는 건 아님)
결론
앞서 대규모 시스템에서 데이터 중복 검사가 왜 필요한지를 살펴봤고 활용 사례들을 살펴보면서 어떤 케이스에 적용해보면 좋을지도 인사이트를 얻어갈 수 있게 되었다.
당장 대규모 시스템에서 운영하지는 않더라도 유사한 문제가 발생하면 고민해볼 수 있는 아이디어 리스트에 하나 채웠다고 생각하면 좋을 것 같다.
참고자료 :