Go에서 효율적인 캐시를 위한 Bloom 필터 구현

캐시 설계에서 우리는 종종 까다로운 문제에 직면합니다. 많은 수의 "유효하지 않은 쿼리"가 데이터베이스에 엄청난 압력을 가합니다. 예를 들어, 사용자가 존재하지 않는 데이터를 요청할 때 일반적으로 데이터베이스를 쿼리하여 "찾을 수 없음"을 반환합니다. 이러한 요청이 많으면 데이터베이스는 이러한 의미 없는 쿼리를 처리하느라 바빠져 시스템 성능에 영향을 미칩니다. 그렇다면 쿼리하기 전에 데이터가 "존재할 수 있는지" 미리 알 수 있는 방법이 있을까요? 여기서 Bloom 필터가 작동합니다.

기존 캐시 시나리오의 문제점

다음 시나리오를 상상해 보십시오.

• 우리 시스템에는 **캐시 레이어(Redis)**와 **데이터베이스 레이어(MySQL)**가 있습니다.
• 사용자가 일부 데이터를 요청하면 먼저 캐시를 확인합니다. 캐시 적중이면 결과를 직접 반환합니다.
• 데이터가 캐시에 없으면 데이터베이스를 쿼리합니다. 데이터베이스에도 없으면 사용자에게 "찾을 수 없음"을 반환합니다.

언뜻 보기에 이 디자인은 합리적으로 보입니다. 그러나 실제로는 많은 수의 유효하지 않은 쿼리가 발생할 수 있습니다.

User requests data with ID=99999999
    -> Not found in cache
    -> Query database for ID=99999999
    -> Database returns: not found

사용자가 존재하지 않는 데이터를 반복적으로 요청하면 다음과 같은 결과가 발생합니다.

• 캐시가 작동하지 않음: 모든 요청이 데이터베이스를 쿼리하여 캐시 계층이 무의미해집니다.
• 과도한 데이터베이스 로드: 수많은 유효하지 않은 요청으로 인해 데이터베이스 응답 속도가 느려집니다.

일반적인 최적화 방법은 유효하지 않은 쿼리를 미리 필터링하여 이미 존재하지 않는 것으로 알고 있는 데이터를 데이터베이스를 쿼리하지 않고 즉시 반환하는 것입니다. 이것이 바로 Bloom 필터가 빛을 발하는 곳입니다.

Bloom 필터란 무엇입니까?

Bloom 필터는 효율적인 집합 구성원 쿼리 알고리즘입니다. 값이 존재할 수 있는지 또는 확실히 존재하지 않는지를 빠르게 확인할 수 있습니다. 간단히 말해서:

• Bloom 필터가 "존재하지 않음"을 알려주면 실제로 존재하지 않으므로 데이터베이스를 쿼리할 필요 없이 즉시 오류를 반환할 수 있습니다.
• Bloom 필터가 "존재할 수 있음"을 알려주면 데이터베이스를 쿼리하여 확인합니다.

Bloom 필터의 기본 논리는 간단합니다.

• 여러 해시 함수를 사용하여 데이터를 고정 크기 비트 배열에 매핑합니다.
• 쿼리할 때 대상 데이터에 대해 동일한 해시를 계산하고 해당 비트가 모두 1로 설정되어 있는지 확인합니다.
• 해당 비트 중 하나라도 0이면 데이터는 확실히 존재하지 않습니다.
• 모든 비트가 1이면 데이터가 존재할 수 있습니다(특정 오탐지율 포함).

장점:

• 메모리 절약 - 기존 해시 테이블보다 공간을 적게 차지합니다.
• 빠른 쿼리 - 시간 복잡도가 O(1)에 가깝습니다.
• 효율적인 필터링 - 데이터베이스 압력을 줄입니다.

단점:

• 오탐지 가능성(그러나 해시 함수 수를 조정하여 오탐지율을 줄일 수 있습니다).
• 데이터를 삭제할 수 없음(일반적으로 빅 데이터 스트림 또는 캐시 시나리오에 사용됨).

Bloom 필터의 데이터 구조

Bloom 필터의 핵심 데이터 구조는 두 가지 구성 요소입니다.

• 비트 배열: 특정 값이 존재하는지 기록하는 데 사용됩니다. 모든 비트는 0으로 초기화됩니다.
• 여러 해시 함수: 데이터에 해당하는 비트 위치를 계산하는 데 사용됩니다.

예:

"Leap" 삽입; 해시 계산 후 비트 배열에서 2, 5, 8, 9 위치에 매핑됩니다.
Index:   0  1  2  3  4  5  6  7  8  9
Value:   0  0  1  0  0  1  0  0  1  1

"Leap" 쿼리 시:

• "Leap"에 대한 해시를 계산하고 2, 5, 8, 9 위치가 모두 1인 것을 확인하여 존재할 수 있음을 나타냅니다.
• "cell"에 대한 해시를 계산하고 일부 비트가 0인 것을 확인하여 즉시 "존재하지 않음"으로 반환됩니다.

Go에서 Bloom 필터 구현

다음은 Go를 사용한 Bloom 필터 구현입니다.

• BloomFilter 구조체.
• 예상 요소 수와 허용 가능한 오탐지율을 기반으로 최적의 비트 배열 크기(m)와 해시 함수 수(k)를 자동으로 계산하는 생성자 NewBloomFilter.
• m과 k를 직접 지정할 수 있는 생성자 NewBloomFilterWithMK.
• 요소를 추가하는 Add 메서드.
• 요소가 존재할 수 있는지 확인하는 MightContain 메서드(오탐지가 있을 수 있지만 거짓 음성은 절대 없음).
• 이중 해싱을 사용하여 k 해시 값을 생성하는 내부 getHashes 메서드. 여기서는 FNV-1a 해시 알고리즘의 두 가지 변형을 기본 해시로 사용합니다.

Bloom 필터 구조

package main

import (
  "fmt"
  "hash/fnv"
)

// Bloom filter struct
type BloomFilter struct {
  m    uint64 // Size of bit array (number of bits)
  k    uint64 // Number of hash functions
  bits []byte // Bit array
}

// Create a Bloom filter
func NewBloomFilter(expectedN uint64, falsePositiveRate float64) *BloomFilter {
  m, k := estimateParameters(expectedN, falsePositiveRate)
  if m == 0 || k == 0 {
    panic("Invalid parameters for Bloom filter: m or k is zero")
  }
  return NewBloomFilterWithMK(m, k)
}

// estimateParameters calculates the optimal m and k based on the expected number of elements n and the false positive rate p
// m = - (n * ln(p)) / (ln(2))^2
// k = (m / n) * ln(2)
func estimateParameters(n uint64, p float64) (m uint64, k uint64) {
  if n == 0 || p <= 0 || p >= 1 {
    return 1000, 10
  }
  mFloat := -(float64(n) * math.Log(p)) / (math.Ln2 * math.Ln2)
  kFloat := (mFloat / float64(n)) * math.Ln2

  m = uint64(math.Ceil(mFloat))
  k = uint64(math.Ceil(kFloat))

  if k < 1 {
    k = 1
  }
  return
}

// NewBloomFilterWithMK creates a Bloom filter using the specified m and k
func NewBloomFilterWithMK(m, k uint64) *BloomFilter {
  if m == 0 || k == 0 {
    panic("Invalid parameters for Bloom filter: m or k is zero")
  }
  numBytes := (m + 7) / 8
  return &BloomFilter{
    m:    m,
    k:    k,
    bits: make([]byte, numBytes),
  }
}

// getHashes uses double hashing to generate k hash values for the data
func (bf *BloomFilter) getHashes(data []byte) []uint64 {
  hashes := make([]uint64, bf.k)

  // Use two different versions (or seeds) of FNV-1a as base hash functions
  h1 := fnv.New64()
  h1.Write(data)
  hash1Val := h1.Sum64()

  h2 := fnv.New64a()
  h2.Write(data)
  hash2Val := h2.Sum64()

  for i := uint64(0); i < bf.k; i++ {
    if hash2Val == 0 && i > 0 {
      hash2Val = 1
    }
    hashes[i] = (hash1Val + i*hash2Val) % bf.m
  }
  return hashes
}

데이터 삽입

// Insert data into the Bloom filter
func (bf *BloomFilter) Add(data []byte) {
  hashes := bf.getHashes(data)
  for _, h := range hashes {
    byteIndex := h / 8                     // Find the byte index
    bitOffset := h % 8                     // Find the bit offset within the byte
    bf.bits[byteIndex] |= (1 << bitOffset) // Set the corresponding position to 1
  }
}

데이터 쿼리

// Check whether data might exist
func (bf *BloomFilter) MightContain(data []byte) bool {
  hashes := bf.getHashes(data)
  for _, h := range hashes {
    byteIndex := h / 8
    bitOffset := h % 8
    if (bf.bits[byteIndex] & (1 << bitOffset)) == 0 {
      // If any bit corresponding to a hash is 0, the element definitely does not exist
      return false
    }
  }
  // If all bits corresponding to hashes are 1, the element might exist
  return true
}

Bloom 필터 재설정

// Reset clears the Bloom filter (sets all bits to 0)
func (bf *BloomFilter) Reset() {
  for i := range bf.bits {
    bf.bits[i] = 0
  }
}

테스트 코드

func main() {
  // Example: expect 1000 elements, false positive rate 1%
  expectedN := uint64(1000)
  falsePositiveRate := 0.01

  m, k := estimateParameters(expectedN, falsePositiveRate)
  fmt.Printf("Estimated parameters: m = %d, k = %d\n", m, k)

  bf := NewBloomFilter(expectedN, falsePositiveRate)
  // Or bf := NewBloomFilterWithMK(m, k)

  // Add some elements
  item1 := []byte("apple")
  item2 := []byte("banana")
  item3 := []byte("cherry")

  bf.Add(item1)
  bf.Add(item2)

  fmt.Printf("MightContain 'apple': %t\n", bf.MightContain(item1))           // true
  fmt.Printf("MightContain 'banana': %t\n", bf.MightContain(item2))          // true
  fmt.Printf("MightContain 'cherry': %t\n", bf.MightContain(item3))          // false (should be false, as it wasn't added)
  fmt.Printf("MightContain 'grape': %t\n", bf.MightContain([]byte("grape"))) // false (should also be false)

  bf.Reset()
  fmt.Println("After Reset:")
  fmt.Printf("MightContain 'apple': %t\n", bf.MightContain(item1)) // false
}

요약

Bloom 필터는 캐시 시스템에서 다음을 통해 도움을 줄 수 있습니다.

• 유효하지 않은 데이터베이스 쿼리 감소: 데이터베이스에 직접 액세스하지 않도록 먼저 데이터가 존재할 수 있는지 판단합니다.
• 저장 공간 절약: 해시 테이블보다 메모리를 적게 사용하여 대규모 데이터에 적합합니다.
• 쿼리 효율성 향상: 쿼리에 대한 O(1) 시간 복잡성, 전체 데이터 세트를 탐색할 필요가 없습니다.

Go를 사용하여 간단한 Bloom 필터를 구현하여 캐시 시나리오에 적용하여 데이터베이스 로드를 최적화했습니다.

---

Leapcell은 Go 프로젝트 호스팅을 위한 최고의 선택입니다.

Leapcell은 웹 호스팅, 비동기 작업 및 Redis를 위한 차세대 서버리스 플랫폼입니다.

다국어 지원

• Node.js, Python, Go 또는 Rust로 개발하십시오.

무료로 무제한 프로젝트 배포

• 사용량에 따라서만 지불하십시오. 요청도 없고 요금도 없습니다.

탁월한 비용 효율성

• 유휴 요금 없이 사용한 만큼만 지불하십시오.
• 예: $25는 평균 응답 시간 60ms에서 694만 건의 요청을 지원합니다.

간소화된 개발자 경험

• 간편한 설정을 위한 직관적인 UI.
• 완전 자동화된 CI/CD 파이프라인 및 GitOps 통합.
• 실행 가능한 통찰력을 위한 실시간 메트릭 및 로깅.

손쉬운 확장성 및 고성능

• 고도의 동시성을 쉽게 처리하기 위한 자동 확장.
• 운영 오버헤드가 없으므로 구축에만 집중하십시오.

설명서에서 더 자세히 알아보십시오!

X에서 팔로우하세요: @LeapcellHQ