还在使用 Jaeger/Sentry 吗？Uptrace 是一个 开源APM，它使用 OpenTelemetry 来监控应用程序并设置警报以通过电子邮件、Slack、Telegram 等方式接收通知。

Redis：布隆过滤器、库克过滤器、计数-最小值、Top-K

• RedisBloom
• 布隆过滤器 vs 库克过滤器
• 布隆过滤器和库克过滤器
• 计数-最小值草图
• Top-K

RedisBloom

RedisBloom 是一个 Redis 模块，它添加了对布隆过滤器和库克过滤器的支持，以及一个计数-最小值草图和一个 top-k。首先，您需要编译 RedisBloom 模块。

git clone --recursive https://github.com/RedisBloom/RedisBloom.git
cd redisbloom
make

然后在启动 Redis 实例时加载该模块。

/path/to/redis-server --loadmodule ./redisbloom.so

您可以在 GitHub 上找到以下示例的源代码。

布隆过滤器 vs 库克过滤器

布隆过滤器和库克过滤器是概率数据结构，它们报告一个项目是否被以前看到过（是集合的成员）。两种过滤器都使用哈希函数，并且由于哈希冲突可能会报告假阳性（但不会报告假阴性）。

来自 文档

布隆过滤器在插入项目时通常表现出更好的性能和可扩展性（因此，如果您经常将项目添加到数据集，那么布隆过滤器可能是理想的选择）。库克过滤器在检查操作时更快，并且还允许删除。

布隆过滤器也比库克过滤器小得多。

127.0.0.1:6379> BF.RESERVE bloom_key 0.1 100000
OK
127.0.0.1:6379> MEMORY USAGE bloom_key
(integer) 78080

127.0.0.1:6379> CF.RESERVE cf_key 100000
OK
127.0.0.1:6379> MEMORY USAGE cf_key
(integer) 131160

布隆过滤器和库克过滤器

您可以使用通用 Do 函数执行 Redis Bloom 命令，然后使用 Cmd 助手检索结果。

func bloomFilter(ctx context.Context, rdb *redis.Client) {
	inserted, err := rdb.Do(ctx, "BF.ADD", "bf_key", "item0").Bool()
	if err != nil {
		panic(err)
	}
	if inserted {
		fmt.Println("item0 was inserted")
	}

	for _, item := range []string{"item0", "item1"} {
		exists, err := rdb.Do(ctx, "BF.EXISTS", "bf_key", item).Bool()
		if err != nil {
			panic(err)
		}
		if exists {
			fmt.Printf("%s does exist\n", item)
		} else {
			fmt.Printf("%s does not exist\n", item)
		}
	}
}

库克 命令 看起来非常相似。

func cuckooFilter(ctx context.Context, rdb *redis.Client) {
	inserted, err := rdb.Do(ctx, "CF.ADDNX", "cf_key", "item0").Bool()
	if err != nil {
		panic(err)
	}
	if inserted {
		fmt.Println("item0 was inserted")
	} else {
		fmt.Println("item0 already exists")
	}

	for _, item := range []string{"item0", "item1"} {
		exists, err := rdb.Do(ctx, "CF.EXISTS", "cf_key", item).Bool()
		if err != nil {
			panic(err)
		}
		if exists {
			fmt.Printf("%s does exist\n", item)
		} else {
			fmt.Printf("%s does not exist\n", item)
		}
	}

	deleted, err := rdb.Do(ctx, "CF.DEL", "cf_key", "item0").Bool()
	if err != nil {
		panic(err)
	}
	if deleted {
		fmt.Println("item0 was deleted")
	}
}

计数-最小值草图

计数-最小值草图 是一个概率数据结构，用于使用哈希函数计算近似计数。由于哈希冲突，它可能会对某些项目进行过度计数。

func countMinSketch(ctx context.Context, rdb *redis.Client) {
	if err := rdb.Do(ctx, "CMS.INITBYPROB", "count_min", 0.001, 0.01).Err(); err != nil {
		panic(err)
	}

	items := []string{"item1", "item2", "item3", "item4", "item5"}
	counts := make(map[string]int, len(items))

	for i := 0; i < 10000; i++ {
		n := rand.Intn(len(items))
		item := items[n]

		if err := rdb.Do(ctx, "CMS.INCRBY", "count_min", item, 1).Err(); err != nil {
			panic(err)
		}
		counts[item]++
	}

	for item, count := range counts {
		ns, err := rdb.Do(ctx, "CMS.QUERY", "count_min", item).Int64Slice()
		if err != nil {
			panic(err)
		}
		fmt.Printf("%s: count-min=%d actual=%d\n", item, ns[0], count)
	}
}

Top-K

一个 top-k 维持一个包含 k 个最常出现的项目的列表。它使用概率计数器，可能会对某些项目进行低估。

func topK(ctx context.Context, rdb *redis.Client) {
	if err := rdb.Do(ctx, "TOPK.RESERVE", "top_items", 3).Err(); err != nil {
		panic(err)
	}

	counts := map[string]int{
		"item1": 1000,
		"item2": 2000,
		"item3": 3000,
		"item4": 4000,
		"item5": 5000,
		"item6": 6000,
	}

	for item, count := range counts {
		for i := 0; i < count; i++ {
			if err := rdb.Do(ctx, "TOPK.INCRBY", "top_items", item, 1).Err(); err != nil {
				panic(err)
			}
		}
	}

	items, err := rdb.Do(ctx, "TOPK.LIST", "top_items").StringSlice()
	if err != nil {
		panic(err)
	}

	for _, item := range items {
		ns, err := rdb.Do(ctx, "TOPK.COUNT", "top_items", item).Int64Slice()
		if err != nil {
			panic(err)
		}
		fmt.Printf("%s: top-k=%d actual=%d\n", item, ns[0], counts[item])
	}
}