대용량 데이터 중복 제거 ‐ bitmap, Bloom filter - low-hill/Knowledge GitHub Wiki

BitMap

BitMap은 하나의 bit로 요소를 표시하고 그 값은 0 또는 1일 수 있고 메모리 공간을 줄일 수 있다.

  • 예) 1, 4, 6을 BitMap으로 저장하면 다음과 같다. image
  • BitMap은 중복 제거 및 정렬에 적합하고 Bloom filter는 비트맵 기반으로 구현된다. 그러나 비트맵은 0과 1만 표현하고 다른 숫자를 저장할 수 없어 true 혹은 false 판별하는 상황에 적합합니다.

BitMap은 값 범위가 작을 때 적합하고 값 범위가 너무 크면 BitMap의 저장 공간도 커져서 BloomFilter를 사용하는 것이 더 적합하다.

BloomFilter

BloomFilter는 어떤 값이 집합에 속해 있는지 여부를 신속하게 검색하는 데 사용되는 자료 구조이다. 기본 원리는 여러 해시 함수를 사용하여 여러 비트로 매핑하고 이를 1로 설정하는 것이다. 저장된 데이터에 비트가 모두 1로 설정되어 있으면 값이 요소에 존재할 수 있다. BloomFilter는 값이 존재하지 않는지 정확하게 판단할 수 있지만 hash collision으로 값이 존재 할 수 도 있다고 판단할 수 있다.(없는 값을 있다고 판단 될 수 있음). 이러한 문제는 hash collision을 줄이고 더 많은 hash function 추가 및 bitmap을 늘려 정확도를 높일 수 있다. image

원리

  • 초기화
    • BloomFilter 초기화 시 집합의 크기(vector size)와 fpp를 지정해야 한다. BloomFilter 내부에는 하나의 비트 배열과 여러 해시 함수가 포함되어 있으며 각 해시 함수로 해쉬 값을 생성한다.
  • 값 추가
    • 추가하려는 값은 여러 해시 함수를 거쳐 해시 값이 생성되고, (해당 해시값 = 비트 배열의 index)인 비트 배열[index]가 1로 설정 된다.(인덱스 값이 이미 1로 설정되어 있으면 다시 설정할 필요가 없다.)
  • 값이 존재하는지 확인
    • 해쉬 함수를 거쳐 생성된 인덱스 값이 1로 설정되어 있으면 값이 존재 할 수 있다고 판단

다이어그램을 통한 상세 설명(삽입 및 조회 과정)

(a): 시퀀스 삽입

  1. 시퀀스 "ACCGTAG": 이 시퀀스가 우리의 집합에 있는지 확인하고자 한다고 가정해봅시다.

  2. k-mers: 위 시퀀스는 "k-mers"라고 불리는 더 작은 부분들로 나뉩니다 (chunks or fragments과 유사). 예를 들어, "ACCG", "CCGT", "CGTA", "GTAG"로 분해됩니다.

  3. 해싱: 각 k-mers는 여러 개의 해시 함수를 통과합니다. 이 해시 함수들은 k-mers를 비트 배열의 특정 위치에 매핑합니다.

  4. 비트 설정: 각 k-mers에 대해, 비트 배열의 해당 비트들이 1로 설정됩니다. 비트 배열은 처음에 모두 0이지만, k-mers를 추가함에 따라 해당되는 비트들이 1로 변경됩니다.

(b): 시퀀스 조회

  1. k-mers: a의 k-mers과정과 마찬가지로, 이 시퀀스도 k-mers로 분해됩니다 (예: "CGTA", "GTAT").

  2. 비트 확인: k-mers들을 해싱하고 비트 배열의 비트들을 확인합니다:

  • 모든 비트가 1로 설정되어 있다면 ("CGTA"의 경우처럼), 이는 시퀀스가 집합에 있을 수 있음을 시사합니다.
  • 단 하나의 비트라도 0이라면 ("GTAT"의 경우처럼), 이는 시퀀스가 확실히 집합에 없다는 것을 의미합니다. image

블룸 필터의 특징

  • 매우 빠른 검색 속도: O(k) 시간 복잡도 (k는 사용된 해시 함수의 수)
  • 공간 효율성: 원본 데이터보다 훨씬 적은 메모리 사용
  • 존재 가능성:
    • (False Positive) 가능성: 존재하지 않는 원소를 존재한다고 잘못 판단할 수 있음
    • (no False Negative) 불가능: 존재하는 원소를 존재하지 않는다고 판단하는 경우는 없음

장단점

장점: 이진데이터를 저장하기 때문에 공간이 절약되고 데이터 삽입 및 검색이 빠르다 단점: 값이 존재 여부를 정확하게 판단 할 수 없고(fpp) 삭제가 어렵다(서로 다른 값들이 동일한 해시값으로 생성되어 동일한 배열 index를 공유할 수 있다.)

Guava로 구현된 코드는 하위와 같다.

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterExample {
    public static void main(String[] args) {
        // expectedInsertions  100，fpp 0.01
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), 100, 0.01);
        // 값 추가
        bloomFilter.put("value1");
        bloomFilter.put("value2");
        bloomFilter.put("value3");
        // 값 포함 여부 판단
        System.out.println(bloomFilter.mightContain("value1")); // true
        System.out.println(bloomFilter.mightContain("me"));  // false
    }
}

적용 사례

블룸 필터의 특성은 대규모 데이터셋에서 특히 유용합니다. 예를 들어, 웹 크롤러가 이미 방문한 URL을 추적하거나, 스팸 필터가 알려진 스팸 이메일 주소를 빠르게 확인하는 데 사용될 수 있습니다. 또한, 분산 시스템에서 네트워크 트래픽을 줄이기 위해 데이터의 존재 여부를 사전에 확인하는 데도 효과적으로 활용될 수 있습니다.

  • 웹 크롤러: BloomFilter를 사용하여 이미 크롤링된 웹 페이지를 필터링하여 중복 및 리소스 낭비를 방지.
  • 분산 시스템: BloomFilter를 사용하여 분산 캐시에 요소가 있는지 여부를 확인하여 모든 노드에서의 검색을 방지하고 네트워크 부하를 줄일 수 있다.
  • 스팸 필터링: 메일 주소가 스팸 목록에 있는지 확인하여 스팸을 필터링할 수 있다. 위 케이스 외에 캐시시스템 및 IP 및 핸드폰 차단 등에 사용된다.
  • Cache penetration

구체적인 사례로 알아보는 Bloom filter 적용

수십억 사용자 중 특정 사용자명의 존재 여부를 효율적으로 확인하는 방법

대규모 사용자 데이터베이스에서 특정 사용자명이 존재하는지 빠르고 효율적으로 확인하는 방법에 대해 비교하고 분석해보겠습니다. 사용자 이름의 확인하는 과정은 여러 가지 방법으로 접근할 수 있으며, 각 방법마다 장단점이 존재합니다. 이 글에서는 전통적인 데이터베이스 쿼리, Redis를 활용한 캐싱 전략, 그리고 블룸 필터를 이용한 최적화된 접근 방식의 세 가지 방법을 살펴보겠습니다.

방법 1: 데이터베이스 조회

사용자명의 존재 여부를 확인하는 가장 직접적인 방법은 데이터베이스를 조회하는 것입니다. 하지만 사용자 수가 수백만 또는 수십억 명으로 증가하면, 이 접근법은 비효율적이 될 수 있습니다. 다음은 주요 단점입니다:

  1. 높은 지연 시간: 대규모 데이터베이스를 쿼리할 때, 증가된 지연 시간으로 인해 성능이 저하될 수 있습니다. 각 쿼리는 애플리케이션과 데이터베이스 서버 간의 네트워크 통신을 수반하므로 지연이 발생합니다. 결과적으로, 사용자는 응답을 받기까지 더 오래 기다려야 할 수 있습니다.

  2. 데이터베이스 부하 증가: 사용자명의 고유성을 확인하기 위한 SELECT 쿼리는 CPU 사용량과 입출력(I/O) 작업을 포함합니다. 특히 피크 시간대에는 이로 인해 병목 현상이 발생할 수 있으며, 전체 시스템의 성능에 부정적인 영향을 미칠 수 있습니다.

  3. 확장성 문제: 데이터베이스는 동시 연결 수를 처리하는 데 한계가 있습니다. 사용자 등록이 증가함에 따라 데이터베이스는 이를 따라가는 데 어려움을 겪을 수 있으며, 이는 전반적인 성능 저하로 이어질 수 있습니다. 데이터베이스를 수직적으로 확장하는 것은 비용이 많이 들고 한계가 있습니다. 또한, 수평적 확장도 복잡성을 증가시키고 데이터 일관성 유지에 추가적인 과제를 제시합니다.

방법 2: Redis 캐시 솔루션

데이터베이스 쿼리의 성능 문제를 완화하기 위해 Redis와 같은 캐싱 계층을 도입할 수 있습니다. 이 방법은 사용자명을 Redis 해시 맵에 저장하여 더 빠른 확인을 가능하게 합니다.

Redis 캐시 접근 방식의 과제:

  1. 메모리 소비: Redis에 저장된 각 사용자명은 약 15바이트의 메모리를 소비합니다. 10억 개의 사용자명을 저장하려면 약 15GB의 메모리가 필요합니다. 이는 상당한 양의 메모리를 요구하며, 대규모 시스템에서는 비용과 리소스 관리 측면에서 중요한 고려사항이 됩니다.

  2. 확장성 문제: 데이터베이스 조회보다는 빠르지만, 대용량 데이터셋을 메모리에 저장하는 것은 여전히 비용이 많이 들 수 있습니다. 또한, 리소스 부족을 방지하기 위해 신중한 관리가 필요합니다. 데이터 크기가 증가함에 따라 메모리 용량을 지속적으로 확장해야 하며, 이는 하드웨어 비용 증가로 이어질 수 있습니다.

추가적인 고려사항:

  1. 데이터 일관성:
    Redis 캐시와 기본 데이터베이스 간의 동기화를 유지하는 것이 중요합니다. 이를 위해 적절한 캐시 무효화 전략이 필요합니다.
  2. 장애 복구:
    Redis 서버 장애 시 대비책을 마련해야 합니다. 예를 들어, Redis 클러스터 구성이나 백업 시스템 구축 등을 고려할 수 있습니다. 네트워크 오버헤드: Redis 서버와의 통신에도 일정 수준의 네트워크 지연이 발생할 수 있으므로, 이를 최소화하기 위한 전략이 필요할 수 있습니다. 이러한 과제들을 고려하여, Redis 캐시 솔루션은 중소규모 시스템에서는 효과적일 수 있지만, 대규모 시스템에서는 추가적인 최적화나 다른 접근 방식과의 조합이 필요할 수 있습니다.

방법 3: Bloom Filters 사용

이러한 문제를 해결하기 위해 우리는 '블룸 필터'라는 확률적 자료 구조를 사용할 수 있습니다. 블룸 필터는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 공간 효율적인 방법입니다.

요약

  1. 블룸 필터의 이점: 이 방법은 메모리 효율적이며, 어떤 항목이 집합에 있을 가능성을 빠르게 확인할 수 있습니다.
  2. 거짓 양성: 실제로는 집합에 없는 항목을 있다고 잘못 표시할 수 있습니다.
  3. 확실한 음성: 확인 결과 항목이 집합에 없다고 나오면, 이는 100% 정확합니다.

결론

블룸 필터를 사용하면 대규모 사용자 데이터베이스에서도 매우 빠르게 사용자명의 존재 여부를 확인할 수 있습니다. 거짓 양성의 가능성이 있지만, 이는 대부분의 경우 허용 가능한 수준입니다. 필요하다면 의심되는 경우에만 데이터베이스를 직접 조회하는 방식으로 보완할 수 있습니다. 이러한 기술은 사용자 경험을 크게 향상시키며, 특히 실시간 응답이 중요한 대규모 시스템에서 매우 유용합니다.

Reference

⚠️ **GitHub.com Fallback** ⚠️