쿠쿠 필터

쿠쿠 필터 (Cuckoo Filter)

쿠쿠 필터(Cuckoo filter)는 Bloom filter처럼 요소가 집합에 존재하는지 확인하는 확률적 데이터 구조예요. Redis Open Source에서 매우 빠르고 공간 효율적인 방식으로 존재 여부를 확인할 수 있게 해주면서, 삭제(deletion)도 허용하고 어떤 시나리오에서는 Bloom보다 더 나은 성능을 보여줘요.

출처: Redis 공식 문서 — cuckoo-filter

사용 사례 (Use cases)

"이 할인 코드/쿠폰이 이미 사용됐는가?"라는 질문에 답해요.

모든 할인 코드/쿠폰으로 채워진 Cuckoo filter를 사용해요. 시도할 때마다 입력된 코드가 필터에 대해 확인돼요.

  • 없다면 쿠폰이 유효하지 않아요.
  • 있다면 쿠폰이 유효할 수 있어요. 메인 데이터베이스를 확인해요. 유효하다면 used로 Cuckoo filter에서 제거해요.

참고: 이 두 경우 외에도 Cuckoo filter는 모든 Bloom filter 사용 사례에서 아주 잘 동작해요.

예시 (Examples)

초기 용량 1,000개 항목으로 빈 쿠쿠 필터를 만들고, 항목을 추가하고, 존재를 확인하고, 제거하는 방법을 배워볼게요. CF.ADD 명령은 필터가 없으면 새로 만들 수 있지만, 여러분의 필요에 최적의 크기로 만들어지지 않을 수 있어요. 선호하는 용량으로 필터를 설정하려면 CF.RESERVE 명령을 쓰는 게 좋아요.

복잡도:

  • CF.RESERVE: O(1)
  • CF.ADD: O(k + i)
  • CF.EXISTS: O(k)
  • CF.DEL: O(k)

Redis CLI

> CF.RESERVE bikes:models 1000
OK
> CF.ADD bikes:models "Smoky Mountain Striker"
(integer) 1
> CF.EXISTS bikes:models "Smoky Mountain Striker"
(integer) 1
> CF.EXISTS bikes:models "Terrible Bike Name"
(integer) 0
> CF.DEL bikes:models "Smoky Mountain Striker"
(integer) 1

C#

bool res1 = db.CF().Reserve("bikes:models", 1000000);
Console.WriteLine(res1);    // >>> True

bool res2 = db.CF().Add("bikes:models", "Smoky Mountain Striker");
Console.WriteLine(res2);    // >>> True

bool res3 = db.CF().Exists("bikes:models", "Smoky Mountain Striker");
Console.WriteLine(res3);    // >>> True

bool res4 = db.CF().Exists("bikes:models", "Terrible Bike Name");
Console.WriteLine(res4);    // >>> False

bool res5 = db.CF().Del("bikes:models", "Smoky Mountain Striker");
Console.WriteLine(res5);    // >>> True

Go

res1, err := rdb.CFReserve(ctx, "bikes:models", 1000000).Result()

if err != nil {
    panic(err)
}

fmt.Println(res1) // >>> OK

res2, err := rdb.CFAdd(ctx, "bikes:models", "Smoky Mountain Striker").Result()

if err != nil {
    panic(err)
}

fmt.Println(res2) // >>> true

res3, err := rdb.CFExists(ctx, "bikes:models", "Smoky Mountain Striker").Result()

if err != nil {
    panic(err)
}

fmt.Println(res3) // >>> true

res4, err := rdb.CFExists(ctx, "bikes:models", "Terrible Bike Name").Result()

if err != nil {
    panic(err)
}

fmt.Println(res4) // >>> false

res5, err := rdb.CFDel(ctx, "bikes:models", "Smoky Mountain Striker").Result()

if err != nil {
    panic(err)
}

fmt.Println(res5) // >>> true

Java (Synchronous - Jedis)

String res1 = jedis.cfReserve("bikes:models", 1000000);
System.out.println(res1); // >>> OK

boolean res2 = jedis.cfAdd("bikes:models", "Smoky Mountain Striker");
System.out.println(res2); // >>> True

boolean res3 = jedis.cfExists("bikes:models", "Smoky Mountain Striker");
System.out.println(res3); // >>> True

boolean res4 = jedis.cfExists("bikes:models", "Terrible Bike Name");
System.out.println(res4); // >>> False

boolean res5 = jedis.cfDel("bikes:models", "Smoky Mountain Striker");
System.out.println(res5); // >>> True

JavaScript (Node.js)

const res1 = await client.cf.reserve('bikes:models', 1000000);
console.log(res1);  // >>> OK

const res2 = await client.cf.add('bikes:models', 'Smoky Mountain Striker');
console.log(res2);  // >>> true

const res3 = await client.cf.exists('bikes:models', 'Smoky Mountain Striker');
console.log(res3);  // >>> true

const res4 = await client.cf.exists('bikes:models', 'Terrible Bike Name');
console.log(res4);  // >>> false

const res5 = await client.cf.del('bikes:models', 'Smoky Mountain Striker');
console.log(res5);  // >>> true

PHP

$res1 = $r->cfreserve('bikes:models', 1000000);
echo $res1 . PHP_EOL;
// >>> OK

$res2 = $r->cfadd('bikes:models', 'Smoky Mountain Striker');
echo $res2 . PHP_EOL;
// >>> 1

$res3 = $r->cfexists('bikes:models', 'Smoky Mountain Striker');
echo $res3 . PHP_EOL;
// >>> 1

$res4 = $r->cfexists('bikes:models', 'Terrible Bike Name');
echo $res4 . PHP_EOL;
// >>> 0

$res5 = $r->cfdel('bikes:models', 'Smoky Mountain Striker');
echo $res5 . PHP_EOL;
// >>> 1

Python

res1 = r.cf().reserve("bikes:models", 1000000)
print(res1)  # >>> True

res2 = r.cf().add("bikes:models", "Smoky Mountain Striker")
print(res2)  # >>> 1

res3 = r.cf().exists("bikes:models", "Smoky Mountain Striker")
print(res3)  # >>> 1

res4 = r.cf().exists("bikes:models", "Terrible Bike Name")
print(res4)  # >>> 0

res5 = r.cf().delete("bikes:models", "Smoky Mountain Striker")
print(res5)  # >>> 1

쿠쿠 필터 크기 설정 (Sizing Cuckoo filters)

쿠쿠 필터의 주요 파라미터와 특징은 다음과 같아요:

  • p 목표 거짓 긍정률(target false positive rate)
  • f 비트 단위 지문(fingerprint) 길이
  • α 채우기율/부하 계수 (0≤α≤1)
  • b 버킷당 항목 수
  • m 버킷 수
  • n 항목 수
  • C 항목당 평균 비트 수

쿠쿠 필터 버킷은 여러 항목을 담을 수 있다는 점(각 항목은 지문 하나를 저장)을 기억해 두세요.

결과적으로 항목의 "실제" 메모리 비용에는 지문 크기 외에 그 오버헤드도 포함돼야 해요. α가 부하 계수(지문 크기 / 총 필터 크기)이고 f가 항목의 비트 수라면, 분할 상환(amortised) 공간 비용은 f/α 비트예요.

새 필터를 초기화할 때 용량(capacity)과 버킷 크기(bucket size)를 선택해야 해요.

CF.RESERVE {key} {capacity} [BUCKETSIZE bucketSize] [MAXITERATIONS maxIterations]
[EXPANSION expansion]

용량 선택 (capacity)

쿠쿠 필터의 용량은 다음과 같이 계산돼요:

capacity = n*f/α

여기서 n은 필터에 있을 것으로 예상하는 요소 수, f는 8로 설정된 비트 단위 지문 길이, α는 채우기 계수(fill factor)예요. 그래서 필터 용량을 얻으려면 먼저 채우기 계수를 선택해야 해요. 채우기 계수는 데이터의 밀도와 물론 메모리를 결정해요. 용량은 다음 "2의 거듭제곱(2ⁿ)" 수로 올림(round up)돼요.

버킷 크기 선택 (BUCKETSIZE)

각 버킷의 항목 수예요. 더 높은 버킷 크기 값은 채우기율을 개선하지만 오류율도 높이고 성능은 약간 느려져요.

error_rate = (buckets * hash_functions)/2^fingerprint_size = (buckets*2)/256

예를 들어 버킷 크기 3은 2.34% 오류율과 80% 채우기율을, 버킷 크기 4는 3.12% 오류율과 95% 채우기율을 산출해요.

확장 계수 선택 (EXPANSION)

어느 시점에 스케일해야 할 것이라는 걸 알고 있다면 더 높은 expansion 값을 선택하는 게 좋아요. 기본값은 cf-expansion-factor예요. 확장 계수는 다음 "2의 거듭제곱(2ⁿ)" 수로 올림돼요.

최대 반복 횟수 선택 (MAXITERATIONS)

MAXITERATIONS는 들어오는 지문을 위한 슬롯을 찾으려는 시도 횟수를 결정해요. 필터가 가득 차면 높은 MAXITERATIONS 값은 삽입을 느리게 해요. 기본값은 cf-max-iterations예요.

흥미로운 사실 (Interesting facts)

  • 이전 서브필터의 미사용 용량은 가능할 때 자동으로 사용돼요.
  • 필터는 cf-max-expansions배까지 커질 수 있어요.
  • 필터 한도 안에 머물도록 재구축 대신 항목을 삭제할 수 있어요.
  • 같은 요소를 여러 번 추가하면 여러 항목이 생겨 필터를 채워요.

성능 (Performance)

쿠쿠 필터에 요소를 추가하는 것은 시간 복잡도 O(1)이에요. 마찬가지로 요소 확인과 삭제도 시간 복잡도 O(1)이에요.

학술 자료 (Academic sources)

더 알아보기 (Learn more)