면접에서 자주 등장하는 질문 중 하나가 대용량 데이터 처리와 관련된 내용입니다. 특히, 특정 데이터가 집합에 속하는지 여부를 빠르게 확인해야 하는 상황에서 어떤 자료구조를 사용할 것인지 묻는 질문은 개발자의 문제 해결 능력과 데이터 구조에 대한 깊은 이해를 엿볼 수 있는 중요한 기회죠. 저 역시 한 프로젝트에서 이 문제에 직면했고, 깊이 파고들면서 블룸 필터(Bloom Filter)라는 흥미로운 자료구조를 만나게 되었습니다.
이번 글에서는 제가 직접 겪었던 경험을 바탕으로, 블룸 필터의 확률적 원리를 파헤치고, 해시 함수와 비트 배열이 어떻게 멤버십 검사를 수행하는지 그 내부 동작을 상세히 설명해 드리겠습니다. 특히, 취업이나 이직을 준비하는 예비 개발자분들이 면접 질문에 자신감을 갖고 답할 수 있도록, 실무 관점에서의 활용법과 트레이드오프까지 함께 다루어 보겠습니다.
📑 목차
Image by NoName_13 on Pixabay
서비스 확장과 함께 찾아온 대용량 데이터 멤버십 검사 문제
제가 참여했던 한 백엔드 프로젝트는 사용자들의 특정 활동을 추적하고, 불필요한 중복 요청을 걸러내는 기능이 핵심이었습니다. 예를 들어, 사용자가 특정 콘텐츠를 이미 조회했는지, 혹은 특정 작업을 이미 수행했는지 등을 서버 자원을 효율적으로 사용하면서 빠르게 확인해야 했습니다. 서비스 초기에는 사용자 수가 많지 않아 단순히 인메모리 해시 테이블(In-memory Hash Table), 즉 자바의 HashSet이나 파이썬의 set을 사용해 처리했습니다. 특정 ID가 이미 존재하는지 확인하고, 없다면 추가하는 방식이었죠.
// 초기 구현 (Java 예시)
Set<String> processedIds = new HashSet<>();
public boolean processItem(String itemId) {
if (processedIds.contains(itemId)) {
System.out.println("Item " + itemId + " already processed. Skipping.");
return false;
}
processedIds.add(itemId);
System.out.println("Processing item " + itemId);
// 실제 처리 로직...
return true;
}
하지만 서비스가 성장하면서 하루에도 수억 건의 새로운 ID가 유입되기 시작했습니다. 처음에는 10만 개, 100만 개 수준이던 processedIds의 크기가 수천만 개를 넘어 수억 개에 육박하게 된 것이죠. 이때부터 문제가 발생하기 시작했습니다.
- 메모리 부족(OOM) 현상: 수억 개의 문자열 ID를 해시 테이블에 그대로 저장하니, 서버의 메모리 사용량이 급증했습니다. 결국 OOM(Out Of Memory) 에러가 발생하여 서비스가 불안정해지는 사태가 벌어졌습니다.
- 잦은 GC(Garbage Collection) 발생: 메모리 사용량이 높아지니 JVM의 가비지 컬렉터가 자주 동작하게 되었고, 이로 인해 애플리케이션의 응답 속도가 현저히 느려지는 현상도 나타났습니다.
- 디스크 I/O 또는 네트워크 오버헤드: 인메모리 저장이 불가능해지자, 대안으로 데이터베이스나 분산 캐시(예: Redis)를 고려했습니다. 하지만 수억 건의
EXISTS쿼리나GET요청은 디스크 I/O 또는 네트워크 왕복 시간으로 인해 성능 병목을 유발할 것이 명확했습니다.
저는 이 문제를 해결하기 위해 메모리 효율적이면서도 빠른 멤버십 검사가 가능한 새로운 방법을 찾아야 했습니다. 면접에서 이런 상황을 가정하고 "어떻게 해결하시겠습니까?"라는 질문을 받는다면, 여러분은 어떤 대답을 하실 건가요? 저의 선택은 블룸 필터였습니다.
왜 기존 방식은 한계에 부딪혔을까?
문제를 해결하기 전에, 기존 방식이 왜 대용량 데이터에서 한계에 부딪혔는지 원인을 정확히 분석하는 것이 중요합니다.
해시 테이블의 메모리 사용량
해시 테이블(Hash Table)은 O(1)에 가까운 평균 시간 복잡도로 멤버십 검사를 수행할 수 있는 훌륭한 자료구조입니다. 하지만 그 장점 뒤에는 상당한 메모리 사용량이라는 단점이 숨어 있습니다. 예를 들어, 자바의 String 객체 하나를 저장한다고 가정해봅시다. 단순히 문자열 자체의 바이트 외에도, String 객체의 오버헤드(객체 헤더, 길이 정보 등)와 HashMap 또는 HashSet의 엔트리 객체 오버헤드(해시 값, 다음 엔트리 포인터 등)가 추가로 필요합니다. 만약 ID가 UUID와 같은 36바이트 문자열이라면, 실제 저장되는 데이터 크기는 수백 바이트를 넘어설 수 있습니다. 수억 개의 객체가 이런 식으로 저장된다면, 수십 GB의 메모리를 차지하는 것은 순식간입니다. 이 비용은 서비스 확장과 함께 감당하기 어려워집니다.
정확성 vs 효율성: 트레이드오프의 필요성
기존 방식들은 100%의 정확성을 보장합니다. 즉, 해시 테이블에 없는 데이터는 절대 있다고 판단하지 않고, 있는 데이터는 반드시 있다고 판단합니다. 이는 대부분의 애플리케이션에서 필수적인 요구사항입니다. 그러나 "이 ID가 이전에 처리된 적이 있는가?"와 같은 질문에 대해 "아마도 그렇다"는 대답으로도 충분한 경우가 있습니다. 특히, "절대 아니다"라고 말하는 것에 더 큰 가치를 두는 시나리오가 존재하죠. 예를 들어, 스팸 메일 필터링이나 캐시 미스를 줄이는 용도로는 약간의 오탐(False Positive)을 허용하면서도 압도적인 메모리 효율성과 속도를 얻는 것이 훨씬 유리할 수 있습니다. 이러한 상황에서 우리는 확률적 자료구조를 고려해볼 필요가 있습니다.
Image by yusufk53 on Pixabay
블룸 필터: 확률적 멤버십 검사의 구원투수
이러한 문제 분석을 통해 저는 블룸 필터(Bloom Filter)를 도입하기로 결정했습니다. 블룸 필터는 다음과 같은 특성을 가진 확률적 자료구조입니다.
- 어떤 요소가 집합에 있다고 판단하면, 실제로 있을 수도 있고 없을 수도 있습니다 (False Positive 가능성).
- 어떤 요소가 집합에 없다고 판단하면, 그 요소는 집합에 100% 없습니다 (False Negative는 절대 발생하지 않음).
이러한 특성 덕분에 블룸 필터는 적은 메모리 공간으로 빠른 멤버십 검사를 수행할 수 있습니다. 제가 직면했던 중복 요청 필터링 문제에서, "이미 처리된 적이 없다"고 판단하면 무조건 처리하고, "이미 처리된 적이 있다"고 판단하면 일단 스킵한 후, 나중에 데이터베이스에서 최종 확인하는 방식으로 오탐의 영향을 최소화할 수 있었습니다.
블룸 필터의 내부 동작 원리
블룸 필터는 놀랍도록 간단한 두 가지 핵심 요소로 구성됩니다.
- 비트 배열(Bit Array):
m개의 비트(0 또는 1)로 이루어진 배열입니다. 모든 비트는 초기에 0으로 설정됩니다. - 독립적인 해시 함수(Hash Functions):
k개의 서로 다른 해시 함수입니다. 각 해시 함수는 입력값을 받아0부터m-1사이의 인덱스를 반환합니다.
요소 추가 (Add)
어떤 요소 x를 블룸 필터에 추가할 때는 다음 단계를 거칩니다.
x를k개의 해시 함수 각각에 통과시킵니다.- 각 해시 함수는
m비트 배열 내의 특정 인덱스(예:h_1(x),h_2(x), ...,h_k(x))를 반환합니다. - 해당하는
k개의 비트 배열 인덱스를 모두 1로 설정합니다.
예를 들어, m=10 비트 배열과 k=3개의 해시 함수가 있다고 가정해봅시다. 요소 "apple"을 추가했을 때, 해시 함수들이 인덱스 1, 4, 8을 반환한다면, 비트 배열의 1, 4, 8번째 비트를 1로 만듭니다.
초기 비트 배열: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
"apple" 추가:
h_1("apple") -> 1
h_2("apple") -> 4
h_3("apple") -> 8
결과 비트 배열: [0, 1, 0, 0, 1, 0, 0, 0, 1, 0]
멤버십 검사 (Contains)
어떤 요소 y가 블룸 필터에 있는지 검사할 때는 다음 단계를 거칩니다.
y를k개의 해시 함수 각각에 통과시킵니다.- 각 해시 함수는
m비트 배열 내의 특정 인덱스(예:h_1(y),h_2(y), ...,h_k(y))를 반환합니다. - 해당하는
k개의 비트 배열 인덱스를 모두 확인합니다. - 만약 모든 비트가 1이라면,
y는 "아마도 집합에 있다"고 판단합니다. - 만약 하나라도 0인 비트가 있다면,
y는 "확실히 집합에 없다"고 판단합니다.
위의 예시에서 "apple"을 다시 검사하면, 1, 4, 8번째 비트가 모두 1이므로 "아마도 있다"고 나옵니다. 만약 "banana"를 검사했을 때 해시 함수들이 2, 5, 8을 반환했는데, 2번 비트가 0이라면, "banana"는 확실히 없다고 판단하는 것이죠.
비트 배열: [0, 1, 0, 0, 1, 0, 0, 0, 1, 0]
"banana" 검사:
h_1("banana") -> 2
h_2("banana") -> 5
h_3("banana") -> 8
결과: 2번 비트 (0), 5번 비트 (1), 8번 비트 (1)
하나라도 0이므로 "banana"는 확실히 없다.
오탐(False Positive)의 원리
블룸 필터의 오탐(False Positive)은 다른 요소들을 추가하는 과정에서 우연히 특정 요소 y의 모든 해시 인덱스에 해당하는 비트들이 모두 1로 설정될 때 발생합니다. 즉, y가 실제로 추가된 적이 없는데도, 다른 요소들의 해시 충돌로 인해 y의 모든 비트가 1이 되는 경우입니다. 이 확률은 블룸 필터의 크기(m), 예상되는 요소의 수(n), 그리고 해시 함수의 수(k)에 의해 결정됩니다.
블룸 필터의 파라미터 선택: m과 k
블룸 필터를 설계할 때 가장 중요한 것은 비트 배열의 크기(m)와 해시 함수의 개수(k)를 결정하는 것입니다. 이 두 값은 예상되는 요소의 수(n)와 허용 가능한 오탐 확률(p)에 따라 달라집니다.
m(비트 배열의 크기):n개의 요소를 저장하고p의 오탐 확률을 유지하기 위해 필요한 최소 비트 수입니다.m이 커질수록 오탐 확률은 낮아지지만, 메모리 사용량은 증가합니다.k(해시 함수의 개수):k가 최적의 값을 가질 때 오탐 확률이 최소화됩니다.k가 너무 작으면 비트가 너무 적게 설정되어 오탐이 많아지고, 너무 크면 너무 많은 비트가 설정되어 비트 배열이 빨리 포화되어 오탐이 많아집니다.
최적의 k와 m은 다음과 같은 공식으로 계산할 수 있습니다.
- 최적의
k = (m / n) * ln(2) - 필요한
m = - (n * ln(p)) / (ln(2)^2)
예를 들어, n = 1억(10^8) 개의 요소를 저장하고 p = 0.01 (1%)의 오탐 확률을 허용한다고 가정해봅시다.
n = 10^8
p = 0.01
m = - (10^8 * ln(0.01)) / (ln(2)^2)
~ - (10^8 * -4.605) / (0.693^2)
~ (4.605 * 10^8) / 0.480
~ 9.59 * 10^8 비트
// 바이트로 변환 (1바이트 = 8비트)
9.59 * 10^8 비트 / 8 비트/바이트 ~ 1.2 * 10^8 바이트 ~ 120 MB
k = (m / n) * ln(2)
~ (9.59 * 10^8 / 10^8) * 0.693
~ 9.59 * 0.693
~ 6.6 해시 함수 (정수로 올림하여 7개)
따라서 1억 개의 요소를 1% 오탐 확률로 처리하려면 약 120MB의 메모리와 7개의 해시 함수가 필요합니다. 이는 수십 GB가 필요했던 해시 테이블과 비교하면 엄청난 메모리 절약입니다. 면접에서 이런 수치를 직접 제시하며 블룸 필터의 효율성을 설명할 수 있다면, 면접관에게 깊은 인상을 줄 수 있을 것입니다.
Image by geralt on Pixabay
실제 적용과 얻은 교훈
프로젝트에 블룸 필터를 적용하는 과정은 순조로웠습니다. 저는 이미 구현되어 있는 오픈소스 블룸 필터 라이브러리(예: Guava의 BloomFilter)를 활용하여 빠르게 프로토타입을 만들고 테스트를 진행했습니다. 테스트 결과, 예상했던 대로 메모리 사용량이 획기적으로 줄어들었고, 멤버십 검사 속도 역시 수 밀리초 이내로 매우 빨랐습니다.
물론, 오탐 확률이 존재하기 때문에 오탐이 발생했을 때의 처리 로직을 신중하게 설계해야 했습니다. 저희 프로젝트에서는 블룸 필터에서 "있음"으로 판단된 경우, 한 번 더 데이터베이스에서 최종 확인하는 단계를 추가하여 False Positive로 인한 문제를 방지했습니다. 즉, 블룸 필터는 "1차 필터링" 역할로 사용하고, 100% 정확성이 필요한 경우에는 "2차 검증" 단계를 거치도록 한 것이죠.
블룸 필터 vs 해시 테이블: 선택의 기준
이 경험을 통해 저는 데이터 구조 선택의 중요성과 트레이드오프의 본질을 다시 한번 깨달았습니다. 아래 표는 블룸 필터와 해시 테이블의 주요 특징을 비교한 것입니다.
| 특징 | 블룸 필터 (Bloom Filter) | 해시 테이블 (Hash Table) |
|---|---|---|
| 주요 용도 | 대규모 데이터셋의 멤버십 검사 (존재 여부 확인) | 키-값 저장 및 멤버십 검사 |
| 메모리 효율성 | 매우 높음 (비트 단위 저장, 요소 자체를 저장하지 않음) | 낮음 (요소 자체와 오버헤드 저장) |
| 검사 속도 | 매우 빠름 (k번의 해시 연산 및 비트 배열 접근) |
매우 빠름 (평균 O(1) 해시 연산 및 배열 접근) |
| 정확성 | 확률적 (False Positive 가능, False Negative 없음) | 100% 정확 (False Positive/Negative 없음) |
| 요소 삭제 | 불가능 (비트 0으로 되돌리기 어려움) | 가능 |
| 주요 활용 사례 | 캐시 미스 방지, 스팸 필터링, 네트워크 라우팅, 데이터베이스 쿼리 최적화, 중복 URL/ID 필터링 | 일반적인 키-값 저장, 빠른 탐색이 필요한 모든 곳 |
블룸 필터는 다음과 같은 상황에서 빛을 발합니다.
- 메모리 제약이 심하고, 대규모 데이터의 존재 여부만 빠르게 확인하고 싶을 때.
- 약간의 오탐(False Positive)을 허용할 수 있거나, 오탐이 발생했을 때 추가적인 검증 단계를 통해 처리할 수 있을 때.
- 데이터를 삭제할 필요가 없거나, 주기적으로 전체를 초기화해도 괜찮을 때.
반면, 100%의 정확성이 필수적이거나, 데이터 자체를 저장하고 관리해야 하며, 요소 삭제 기능이 필요하다면 해시 테이블이나 다른 자료구조가 더 적합합니다.
마무리하며: 개발자의 무기고에 블룸 필터를 추가하자
이번 경험을 통해 블룸 필터가 단순히 이론적인 자료구조가 아니라, 실제 대규모 시스템에서 발생하는 문제를 해결하는 강력한 도구임을 직접 확인할 수 있었습니다. 특히, 제한된 자원 속에서 최적의 성능을 끌어내야 하는 백엔드 개발자에게는 필수적인 지식이라고 생각합니다.
면접에서 "대규모 중복 검사를 어떻게 처리할 것인가?"와 같은 질문을 받는다면, 단순히 해시 테이블이나 데이터베이스를 언급하는 것을 넘어, 블룸 필터와 같은 확률적 자료구조를 언급하고 그 장단점, 트레이드오프를 설명할 수 있다면 여러분의 깊이 있는 지식을 어필할 수 있을 것입니다. 블룸 필터의 확률적 원리, 해시 함수와 비트 배열의 조합, 그리고 오탐 발생 메커니즘을 이해하는 것은 여러분의 문제 해결 능력을 한 단계 끌어올리는 중요한 계기가 될 것입니다.
여러분의 개발 무기고에 블룸 필터를 추가하고, 다음 번 대용량 데이터 문제에 직면했을 때 주저 없이 꺼내어 활용해 보시길 바랍니다.
혹시 블룸 필터를 적용했던 다른 사례나, 블룸 필터에 대해 궁금한 점이 있다면 댓글로 자유롭게 남겨주세요! 함께 이야기 나누고 싶습니다.