카운트-민 스케치
카운트-민 스케치 (Count-min sketch)
Count-min sketch(CMS)는 데이터 스트림에서 요소의 빈도(frequency)를 추정하는 확률적 데이터 구조예요. Redis Open Source 안에서 이벤트/요소의 빈도를 추정할 수 있게 해주죠. 이 페이지에서는 CMS의 원리, 사용 사례, 크기 설정 방법을 설명해 드릴게요.
Count-Min Sketch란 (What is a Count-Min Sketch)
Count-Min Sketch는 충돌(collision) 때문에 일부 이벤트를 과대 집계(over-counting)하는 대가로 아선형(sub-linear) 공간을 사용해요. 이벤트/요소의 스트림을 소비하면서 그 빈도의 추정 카운터를 유지하죠.
매우 중요한 점은, Count-Min sketch에서 나온 결과 중 특정 임계값(error_rate에 의해 결정됨)보다 낮은 것은 무시해야 하며 종종 0으로 근사해야 한다는 거예요. 즉, Count-Min sketch는 스트림에서 요소의 빈도를 세는 데이터 구조이긴 한데, 높은 카운트에만 유용해요. 매우 낮은 카운트는 잡음(noise)으로 무시해야 하죠.
사용 사례 (Use cases)
제품 (Product - 소매, 온라인 상점)
"특정 제품의 (특정 날짜) 판매량은 얼마였나?"라는 질문에 답해요.
기간(일)마다 Count-Min sketch를 하나씩 만들어요. 모든 제품 판매가 CMS에 들어가요. CMS는 판매에 가장 많이 기여한 제품에 대해 합리적으로 정확한 결과를 제공해요. 총 판매에서 낮은 비율을 차지하는 제품은 무시돼요.
예시 (Examples)
오류율 0.1%(0.001)와 확실성 99.8%(0.998)를 선택한다고 가정해 볼게요. 이는 오류 확률 0.2%(0.002)를 의미해요. 스케치는 추가한 모든 요소의 총 카운트의 0.1% 이내로 오류를 유지하려고 노력해요. 오류가 이를 초과할 확률이 0.2% 있어요 — 임계값 아래의 요소가 그 위의 요소와 겹치는 경우처럼요. CMS에 항목을 몇 개 추가하고 빈도를 평가할 때, 이렇게 작은 표본에서는 충돌이 드물다는 점을 기억하세요. 다른 확률적 데이터 구조에서도 마찬가지예요.
Count-min sketch 연산: CMS.INITBYPROB로 스케치를 만들고, CMS.INCRBY로 요소 카운트를 증가시키며, CMS.QUERY로 빈도를 추정하고, CMS.INFO로 스케치 속성을 확인해요 — 데이터 스트림에서 요소 빈도를 추정해야 할 때 쓰죠.
res1 = r.cms().initbyprob("bikes:profit", 0.001, 0.002)
print(res1) # >>> True
res2 = r.cms().incrby("bikes:profit", ["Smoky Mountain Striker"], [100])
print(res2) # >>> [100]
res3 = r.cms().incrby("bikes:profit", ["Rocky Mountain Racer", "Cloudy City Cruiser"], [200, 150])
print(res3) # >>> [200, 150]
res4 = r.cms().query("bikes:profit", "Smoky Mountain Striker")
print(res4) # >>> [100]
res5 = r.cms().info("bikes:profit")
print(res5.width, res5.depth, res5.count) # >>> 2000 9 450
const res1 = await client.cms.initByProb('bikes:profit', 0.001, 0.002);
console.log(res1); // >>> OK
const res2 = await client.cms.incrBy('bikes:profit', { item: 'Smoky Mountain Striker', incrementBy: 100 });
console.log(res2); // >>> [100]
const res3 = await client.cms.incrBy('bikes:profit', [{ item: 'Rocky Mountain Racer', incrementBy: 200 }, { item: 'Cloudy City Cruiser', incrementBy: 150 }]);
console.log(res3); // >>> [200, 150]
const res4 = await client.cms.query('bikes:profit', 'Smoky Mountain Striker');
console.log(res4); // >>> [100]
const res5 = await client.cms.info('bikes:profit');
console.log(res5.width, res5.depth, res5.count); // >>> 2000 9 450
String res1 = jedis.cmsInitByProb("bikes:profit", 0.001d, 0.002d);
System.out.println(res1); // >>> OK
long res2 = jedis.cmsIncrBy("bikes:profit", "Smoky Mountain Striker", 100L);
System.out.println(res2); // >>> 100
List<Long> res3 = jedis.cmsIncrBy("bikes:profit", new HashMap<String, Long>() {{ put("Rocky Mountain Racer", 200L); put("Cloudy City Cruiser", 150L); }});
System.out.println(res3); // >>> [200, 150]
List<Long> res4 = jedis.cmsQuery("bikes:profit", "Smoky Mountain Striker");
System.out.println(res4); // >>> [100]
Map<String, Object> res5 = jedis.cmsInfo("bikes:profit");
System.out.println(res5.get("width") + " " + res5.get("depth") + " " + res5.get("count")); // >>> 2000 9 450
res1, err := rdb.CMSInitByProb(ctx, "bikes:profit", 0.001, 0.002).Result()
if err != nil {
panic(err)
}
fmt.Println(res1) // >>> OK
res2, err := rdb.CMSIncrBy(ctx, "bikes:profit", "Smoky Mountain Striker", 100).Result()
if err != nil {
panic(err)
}
fmt.Println(res2) // >>> [100]
res3, err := rdb.CMSIncrBy(ctx, "bikes:profit", "Rocky Mountain Racer", 200, "Cloudy City Cruiser", 150).Result()
if err != nil {
panic(err)
}
fmt.Println(res3) // >>> [200 150]
res4, err := rdb.CMSQuery(ctx, "bikes:profit", "Smoky Mountain Striker").Result()
if err != nil {
panic(err)
}
fmt.Println(res4) // >>> [100]
res5, err := rdb.CMSInfo(ctx, "bikes:profit").Result()
if err != nil {
panic(err)
}
fmt.Printf("Width: %v, Depth: %v, Count: %v", res5.Width, res5.Depth, res5.Count) // >>> Width: 2000, Depth: 9, Count: 450
bool res1 = db.CMS().InitByProb("bikes:profit", 0.001, 0.002);
Console.WriteLine(res1); // >>> True
long res2 = db.CMS().IncrBy("bikes:profit", "Smoky Mountain Striker", 100);
Console.WriteLine(res2); // >>> 100
long[] res3 = db.CMS().IncrBy("bikes:profit", [new("Rocky Mountain Racer", 200), new("Cloudy City Cruiser", 150)]);
Console.WriteLine(string.Join(", ", res3)); // >>> 200, 150
long[] res4 = db.CMS().Query("bikes:profit", new RedisValue[] { "Smoky Mountain Striker" });
Console.WriteLine(string.Join(", ", res4)); // >>> 100
CmsInformation res5 = db.CMS().Info("bikes:profit");
Console.WriteLine($"Width: {res5.Width}, Depth: {res5.Depth}, Count: {res5.Count}"); // >>> Width: 2000, Depth: 9, Count: 450
C#-Sync (NRedisStack) Quick-Start
$res1 = $r->cmsinitbyprob('bikes:profit', 0.001, 0.002);
echo $res1 . PHP_EOL; // >>> OK
$res2 = $r->cmsincrby('bikes:profit', 'Smoky Mountain Striker', 100);
echo json_encode($res2) . PHP_EOL; // >>> [100]
$res3 = $r->cmsincrby('bikes:profit', 'Rocky Mountain Racer', 200, 'Cloudy City Cruiser', 150);
echo json_encode($res3) . PHP_EOL; // >>> [200,150]
$res4 = $r->cmsquery('bikes:profit', 'Smoky Mountain Striker');
echo json_encode($res4) . PHP_EOL; // >>> [100]
$res5 = $r->cmsinfo('bikes:profit');
echo $res5['width'] . ' ' . $res5['depth'] . ' ' . $res5['count'] . PHP_EOL; // >>> 2000 9 450
예시 1 (Example 1)
각각의 카운트가 약 500인 1000개 요소의 균등(uniform) 분포를 가정해 보면 임계값은 500이 돼요:
threshold = error * total_count = 0.001 * (1000*500) = 500
이것은 CMS가 균등하게 분포된 스트림의 빈도를 세는 데는 어쩌면 최선의 데이터 구조가 아닐 수 있음을 보여줘요. 오류를 0.01%로 줄여볼게요:
threshold = error * total_count = 0.0001 * (1000*500) = 100
이 임계값은 좀 더 수용 가능해 보이지만, 더 큰 스케치 너비 w = 2/error = 20 000이 필요하고 결과적으로 더 많은 메모리가 필요해요.
예시 2 (Example 2)
또 다른 예시로 정상(gaussian) 분포를 상상해 볼게요. 1000개 요소가 있고, 그중 800개가 합산 카운트 400K(평균 카운트 500)이고, 200개 요소는 합산 카운트 1.6M(평균 카운트 8000)로 훨씬 높아 "헤비 히터(heavy hitters, elephant flow)"라고 불러요. 1000개 요소 모두로 스케치를 "채운" 후의 임계값은:
threshold = error * total_count = 0.001 * 2M = 2000
이 임계값은 두 평균 카운트 500과 8000 사이에 안전하게 위치하므로, 처음 선택한 오류율은 이 경우에 잘 작동할 거예요.
크기 설정 (Sizing)
Count-Min sketch는 여러 면에서 Bloom filter와 비슷하지만, 크기 설정은 상당히 더 복잡해요. 초기화 명령은 두 개의 크기 파라미터만 받지만, 사용 가능한 스케치를 원한다면 이것들을 철저히 이해해야 해요.
CMS.INITBYPROB key error probability
1. 오류 (Error)
error 파라미터는 스케치의 너비 w를 결정하고, probability는 해시 함수 수(깊이 d)를 결정해요. 우리가 선택한 오류율은 스케치 결과를 신뢰할 수 있는 임계값을 결정해요. 상관관계는:
threshold = error * total_count
또는
error = threshold/total_count
여기서 total_count는 CMS.INFO 명령 결과의 count 키에서 얻을 수 있는 모든 요소 카운트의 합이며, 물론 동적이에요 — 스케치의 매 증가마다 변해요. 생성 시점에는 total_count 비율을 스케치에서 예상하는 평균 카운트와 평균 요소 수의 곱으로 근사할 수 있어요.
임계값은 필터의 총 카운트의 함수이기 때문에 카운트가 커지면 임계값도 커진다는 점을 기억하는 게 중요해요. 하지만 총 카운트를 알면 항상 임계값을 동적으로 계산할 수 있어요. 결과가 그 아래라면 버릴 수 있죠.
2. 확률 (Probability)
이 데이터 구조에서 probability는 임계값보다 낮은 카운트를 가진 요소가 모든 스케치/깊이에서 임계값보다 높은 카운트를 가진 요소와 충돌하여, 자신의 값 대신 자주 발생하는 요소의 최소 카운트(min-count)를 반환할 확률을 나타내요.
성능 (Performance)
CMS에서 요소를 추가, 업데이트, 조회하는 것은 시간 복잡도 O(1)이에요.