English에서 번역 • 원문 보기 어떤 데이터 구조를 사용하여 주어진 데이터셋에 엔티티가 속하는지 빠르게 판단할 수 있나요? 많은 사람들은 주저 없이 "해시테이블"이라고 답할 것입니다. 해시테이블은 여러 엔티티 그룹 내에서 엔티티에 접근할 때 잘 작동합니다: 읽기 연산의 평균 시간 복잡도가 일정합니다. 하지만 대규모 데이터셋을 다룰 때 해시테이블 사용은 비용이 꽤 많이 들 수 있습니다. 해시테이블은 데이터셋 내 모든 엔터티를 추적해야 하므로 공간 복잡도가 선형적입니다.
해시테이블보다 더 나은 대안이 있을까요? 물어보는 게 좋을 것 같습니다. 대답은 '예'입니다. 단, 정확도를 포기할 의향이 있다는 조건입니다. 이 글에서는 Bloom 필터를 소개하겠습니다. 이는 정확도가 떨어지는 대신 더 넓은 공간 복잡도를 가진 데이터셋에 속하는지 확인하는 Hashtable의 대안입니다.
블룸 필터란 무엇인가
블룸 필터는 항목이 집합에 속하는지 여부를 테스트하기 위한 공간 효율적인 확률적 데이터 구조입니다. Hashtable과 유사하게, Bloom Filter도 해싱을 사용합니다. 하지만 Hashtable과 달리, Bloom 필터는 추가된 항목을 저장하지 않습니다. 대신 추가된 항목에 대한 해시 값을 계산하고 그 값을 집합에 존재하는 것으로 표시합니다. 따라서 Hashtable보다 공간이 적어 공간 복잡도가 더 우수합니다.
하지만 여기서는 공간 효율성과 정확성 사이에서 절충관계를 하고 있습니다. 블룸 필터에 항목을 저장하지 않음으로써, 아이템이 집합에 속하는지 확실히 알 수 있는 능력도 잃게 되는데, 이는 해시테이블을 사용할 때 당연하게 여기는 부분입니다. 블룸 필터에 아이템이 존재하는지 알고 싶을 때는 해당 항목의 해시 값을 계산하고 해시 값이 블룸 필터에 존재하는지 확인합니다. 거짓 양성은 걱정해야 하지만 거짓 음성은 신경 쓰지 않습니다. 즉, 블룸 필터가 아이템이 집합에 속하지 않는다고 주장할 때, 그 주장의 정확성은 100%가 보장됩니다. 하지만 블룸 필터가 반대로 주장하는 것은 항상 옳지 않습니다.
블룸 필터를 언제 사용할까
앞서 언급했듯이, 정확성보다 공간 효율성(특히 오탐 없음)을 중시할 때 Bloom 필터는 Hashtable의 이상적인 대안입니다. 악성 URL 탐지기가 그 예입니다. 수백만 개의 악성 URL을 수집했다고 가정해 봅시다. 해시테이블로 악성 URL 탐지기를 만들었다면, 해시테이블 내 모든 악성 URL을 덤프해야 합니다. 조회가 느리고 URL이 많은 공간을 차지할 것입니다. 이 탐지기는 높은 정확도를 가지고 있습니다. 하지만 악성 URL 탐지기의 목적은 사용자를 악성 URL로부터 보호하는 것이기 때문에 반드시 정확할 필요는 없습니다. 탐지기가 악성 URL을 안전한 URL로 혼동하지 않는 한, 사용자가 실제로 열게 되는 URL을 다한 것입니다.
반면, Bloom Filter로 악성 URL 탐지기를 구축하면 공간 복잡성 측면에서 더 나은 성능을 얻을 수 있습니다. 또한 Bloom Filter는 안전하다고 표시된 모든 URL이 항상 안전하게 열도록 하여 사용자를 악성 URL로부터 보호할 수 있습니다. 유일한 단점은 악성 URL 탐지기가 이제 오탐에 시달리기 때문에 악성 URL이 안전할 수 있다는 점입니다. 이 단점은 공간 확보가 적고 탐지 속도가 빨라진다는 장점에 의해 상쇄됩니다.
거짓 양성 제거가 매우 중요한 경우에도 블룸 필터를 사용할 수 있습니다. 하지만 블룸 필터가 양성 결과를 반환한 후에는 중요한 단계를 추가해야 합니다. 양성이 위양성(음성의 위장)이 아닌지 확인하기 위해 원래 데이터 소스(데이터베이스 등)를 참고하여 양성 결과가 정확한지 확인합니다. 음성의 경우에도 같은 과정을 반복할 필요는 없으며, 모든 음성 결과는 정확히 확인됩니다.
이 글에서는 블룸 필터가 무엇인지, 어떻게 작동하는지, 그리고 언제 사용해야 하는지에 대해 다루었습니다. 블룸 필터는 해시테이블의 대안이지만, 두 사람 모두 각각 장단점이 있습니다. 다음에 어떤 필터를 사용할지 결정할 때 이 점을 꼭 염두에 두시기 바랍니다.