Bloom Filter가 LSM Tree의 불필요한 디스크 조회를 줄이는 방식

데이터베이스 성능의 숨은 공신 블룸 필터와 LSM 트리

현대적인 데이터베이스 시스템, 특히 카산드라(Cassandra), 락스디비(RocksDB), 레벨디비(LevelDB)와 같은 시스템들은 대량의 데이터를 효율적으로 쓰기 위해 LSM 트리(Log Structured Merge Tree) 구조를 채택합니다. LSM 트리는 데이터를 메모리에 먼저 쌓아두었다가 순차적으로 디스크에 기록하는 방식 덕분에 쓰기 성능이 매우 뛰어납니다. 하지만 쓰기가 빠르다는 장점 뒤에는 읽기 성능에 대한 고민이 따릅니다. 특정 데이터를 찾으려고 할 때, 데이터가 여러 파일로 나뉘어 저장되어 있다면 최악의 경우 모든 파일을 뒤져야 하기 때문입니다. 이때 등장하는 구원투수가 바로 블룸 필터입니다.

LSM 트리에서 발생하는 읽기 문제

LSM 트리는 데이터를 여러 개의 계층(Level)으로 나누어 관리합니다. 새로운 데이터는 메모리(MemTable)에 저장되고, 메모리가 가득 차면 디스크(SSTable)로 내려보내집니다. 시간이 흐를수록 디스크에는 수많은 SSTable 파일이 생성됩니다. 만약 사용자가 특정 키(Key)를 가진 데이터를 요청했는데 그 데이터가 메모리에 없다면, 데이터베이스는 디스크에 있는 수많은 파일을 하나하나 열어보며 해당 키가 있는지 확인해야 합니다. 이를 흔히 읽기 증폭(Read Amplification)이라고 부르며, 디스크 I/O를 유발하여 시스템 전체 성능을 급격히 떨어뜨리는 원인이 됩니다.

블룸 필터가 작동하는 원리

블룸 필터는 특정 원소가 집합에 속해 있는지 검사하는 확률적 자료구조입니다. 핵심은 데이터의 실제 값을 저장하는 것이 아니라, 데이터의 존재 여부를 아주 적은 메모리 공간만 사용하여 빠르게 판단한다는 점입니다. 블룸 필터의 동작 과정을 이해하기 쉽게 설명하면 다음과 같습니다.

• 비트 배열 생성: 초기에 모든 비트가 0으로 설정된 큰 비트 배열을 준비합니다.

• 해시 함수 활용: 여러 개의 해시 함수를 사용하여 입력된 키를 비트 배열 내의 여러 위치에 매핑합니다.
• 값 기록: 데이터를 추가할 때, 각 해시 함수가 가리키는 위치의 비트를 1로 변경합니다.
• 존재 여부 확인: 특정 데이터를 찾을 때, 해당 데이터의 해시 값들이 가리키는 위치의 비트가 모두 1인지 확인합니다.

만약 하나라도 0인 비트가 있다면, 그 데이터는 해당 파일에 100% 존재하지 않는다는 확신을 얻을 수 있습니다. 반대로 모든 비트가 1이라면, 데이터가 존재할 가능성이 높다고 판단합니다.

블룸 필터의 독특한 특성

블룸 필터는 ‘거짓 부정(False Negative)’이 절대 발생하지 않는다는 강력한 장점이 있습니다. 즉, 블룸 필터가 없다고 하면 정말로 없는 것입니다. 하지만 ‘거짓 긍정(False Positive)’은 발생할 수 있습니다. 즉, 실제로는 없는데 블룸 필터가 있다고 잘못 판단하는 경우가 생길 수 있습니다. 하지만 이는 데이터베이스 성능 관점에서 큰 문제가 되지 않습니다. 데이터가 있다고 잘못 판단하면 기껏해야 디스크를 한 번 더 읽으면 그만이기 때문입니다. 블룸 필터의 진정한 가치는 데이터가 없는 수많은 경우를 미리 걸러내어 불필요한 디스크 조회를 원천 차단하는 데 있습니다.

실생활에서의 활용 예시

블룸 필터는 데이터베이스 내부뿐만 아니라 우리가 매일 사용하는 다양한 서비스의 기반 기술로 활용되고 있습니다.

• 웹 브라우저의 악성 사이트 차단: 브라우저는 수억 개의 악성 URL 목록을 모두 메모리에 올릴 수 없습니다. 대신 블룸 필터를 사용하여 방문하려는 사이트가 악성 사이트 목록에 포함되어 있는지 빠르게 검사합니다. 목록에 없으면 안전하다고 판단하고, 의심되는 경우에만 정밀 검사를 수행합니다.

• 콘텐츠 추천 시스템: 사용자가 이미 본 콘텐츠를 중복해서 추천하지 않도록, 이전에 본 항목들을 블룸 필터로 관리하여 추천 알고리즘의 효율성을 높입니다.
• 네트워크 라우터: 패킷이 차단 리스트에 있는지 확인하여 보안 검사를 수행할 때 초고속 처리를 위해 블룸 필터를 사용합니다.

흔한 오해와 사실 관계

블룸 필터에 대해 흔히 오해하는 부분들을 정리해 보았습니다.

오해 1: 블룸 필터는 데이터를 저장한다

블룸 필터는 데이터 그 자체를 저장하지 않습니다. 데이터의 지문(Fingerprint)만을 비트 형태로 저장할 뿐입니다. 따라서 블룸 필터만 가지고는 원래의 데이터를 복구할 수 없습니다.

오해 2: 블룸 필터가 긍정이라고 하면 무조건 데이터가 있다

앞서 설명했듯이 블룸 필터는 거짓 긍정이 발생할 수 있습니다. 시스템은 블룸 필터가 ‘있음’이라고 응답하더라도 실제 파일에 데이터가 있는지 최종적으로 확인하는 과정을 거쳐야 합니다.

오해 3: 블룸 필터는 무조건 크면 클수록 좋다

비트 배열이 클수록 거짓 긍정 확률은 낮아지지만, 메모리 사용량은 증가합니다. 가용 메모리와 요구되는 정확도 사이에서 최적의 균형점을 찾는 것이 중요합니다.

비용 효율적인 활용과 최적화 팁

데이터베이스 엔지니어들이 블룸 필터를 설계할 때 고려하는 몇 가지 실용적인 팁을 소개합니다.

• 해시 함수의 개수 조절: 해시 함수의 개수가 너무 적으면 충돌이 잦아지고, 너무 많으면 연산 비용이 늘어납니다. 보통 전체 비트 크기와 예상 데이터 개수를 바탕으로 최적의 해시 함수 개수를 계산합니다.

• 메모리 상주 전략: 블룸 필터는 디스크 I/O를 줄이기 위해 사용하는 도구입니다. 따라서 블룸 필터 자체는 반드시 메모리에 상주시켜야 합니다. 디스크에서 블룸 필터를 읽어와야 한다면 그 자체가 또 다른 I/O 비용이 되어 의미가 퇴색됩니다.
• 필터의 계층화: 데이터가 쌓이는 속도가 빠르다면 블룸 필터도 주기적으로 다시 생성하거나 교체해야 합니다. LSM 트리의 각 레벨마다 별도의 블룸 필터를 적용하여 데이터가 어느 파일에 있는지 더욱 정교하게 추적할 수 있습니다.

전문가의 관점: 왜 블룸 필터인가

많은 전문가들은 블룸 필터를 ‘성능과 비용의 타협점’이라고 부릅니다. 완벽한 인덱스를 구축하려면 거대한 B-Tree를 메모리에 올려야 하는데, 이는 엄청난 메모리 비용을 발생시킵니다. 반면 블룸 필터는 수 메가바이트의 메모리만으로도 수십 기가바이트의 디스크 읽기를 방어할 수 있습니다. 특히 클라우드 환경에서 디스크 I/O 비용은 서비스 단가와 직결됩니다. 따라서 블룸 필터를 적절히 튜닝하는 것만으로도 서비스의 운영 비용을 획기적으로 줄이고 사용자 응답 속도를 크게 개선할 수 있습니다.

자주 묻는 질문과 답변

Q: 블룸 필터의 크기를 동적으로 늘릴 수 있나요?

기본적인 블룸 필터는 한번 생성되면 크기 변경이 어렵습니다. 하지만 이를 개선한 ‘확장 가능한 블룸 필터(Scalable Bloom Filter)’ 기술이 존재합니다. 데이터가 많아지면 새로운 필터를 추가로 생성하여 연결하는 방식을 사용합니다.

Q: 데이터 삭제는 어떻게 처리하나요?

일반적인 블룸 필터는 삭제 기능을 지원하지 않습니다. 비트를 0으로 되돌리면 다른 데이터의 존재 여부까지 함께 삭제될 위험이 있기 때문입니다. 이를 해결하기 위해 각 슬롯에 카운터를 두는 ‘카운팅 블룸 필터(Counting Bloom Filter)’를 사용하기도 하지만, 메모리 사용량이 늘어난다는 단점이 있습니다. LSM 트리에서는 삭제를 ‘툼스톤(Tombstone)’이라는 특별한 마커를 기록하는 방식으로 처리합니다.

Q: 어떤 해시 함수를 사용하는 것이 좋은가요?

성능과 균등 분포를 위해 MurmurHash나 CityHash와 같은 비암호화 해시 함수를 주로 사용합니다. 이들은 속도가 매우 빠르면서도 데이터 충돌을 최소화하는 특성을 가지고 있어 블룸 필터 구현에 최적입니다.

데이터베이스 운영자를 위한 조언

데이터베이스의 성능이 저하되고 있다면 가장 먼저 살펴봐야 할 지표 중 하나가 바로 블룸 필터의 적중률(Hit Rate)입니다. 만약 블룸 필터가 제대로 작동하지 않아 불필요한 디스크 읽기가 반복되고 있다면, 블룸 필터 설정을 변경하거나 시스템의 데이터를 재구성(Compaction)하여 효율을 높여야 합니다. 블룸 필터는 눈에 보이지 않지만, 데이터베이스 시스템이 방대한 양의 데이터를 처리할 수 있게 만드는 핵심 엔진입니다. 이 작은 기술적 선택이 서비스 전체의 확장성과 안정성을 결정짓는다는 점을 기억하십시오.