除了布隆过滤还有哪些方法可以记录快速匹配一个值是否存在的需求

[noobmaster]

背景

1. 需要提供一个接口用来查询数据在不在表里面(只需知道是否存在就行，不需要额外数据)，每天的并发量是 300w 左右。
2. 接口和数据库都是采用的 md5 作为 key, 允许数据实际存在但是返回不存在，但是数据不存在的信息必须是准确的(跟布隆过滤器误报的场景刚好相反)。
3. 数据表有一亿行左右。

问题

1. 不加缓存，直接查数据库。查询压力是不是过大了点？
2. 用 redis 缓存存在数据的 md5 ，后续查询压力会逐渐落到 redis 上，用 set 类型是否是开销最小的？
3. 跟布隆过滤器误报场景相反的数据结构？

[colatin]

“ 允许数据实际存在但是返回不存在，但是数据不存在的信息必须是准确的”这个需求是矛盾的。

[noobmaster]

@colatin 是的，把自己绕进去了。

[noobmaster]

@colatin 所以就是必须以某种形式保存最多 1 亿个 md5 ，只是用什么形式成本和效率有比较好平衡

[moliliang]

1. 肯定大
2. md5 的数据 * 1 亿的大小，可以估算大概的内存占用，set 是可以满足需求的。
3. 布隆过滤器的特点是「存在的不一定存在，不存在的一定不存在」，所以如果你需求是：
「允许数据实际存在但是返回不存在」这个布隆过滤器是满足的、
「数据不存在的信息必须是准确」布隆过滤器也是符合你需求的。

所以是没有完全理解布隆过滤器的特点？

而且通常如果要精确的知道数据存在的话，可以使用布隆过滤器的「存在不一定存在」的特性，将它理解成「范围」，拿到范围之后，再做精确判断，因为通常这个时候，这个范围是很小的。

顺便给一篇我之前写的一篇文章，可能能帮到你： https://mozz.in/go/golang/%E6%95%B0%E6%8D%AE%E5%A4%84%E7%90%86/2021/04/21/big-data-filter.html

[WriteCloser]

我用我并不是很好的数据算了下

[WriteCloser]

32 位 = 2.75 Byte = 0.00275 KB = 0.000002685546875 mb = 0.000000002622604 G * 1 亿 = 0.2G 如果不接受假阳性硬放好像问题不大，不知道是不是这样

[noobmaster]

@moliliang 布隆过滤器是 “存在的不一定存在”，实现不了“存在的一定存在”吧。
反过来去思考，要求存在这个信息是准确的话，不存在的信息就也是精确的了。
看起来是必须保存这 1 亿个 md5 的完整信息了😳

[noobmaster]

存 redis 的话，set 应该是最合适的数据类型了吧。

[zeni123]

@colatin 并不矛盾

数据不存在 => 一定返回 false
返回 true => 数据一定 存在

返回 false => 数据有可能存在有可能不存在
数据存在 => 有可能返回 true 有可能返回 false


逻辑是自洽的

[zeni123]

@colatin 他可能是说 "允许数据实际存在但是返回不存在，但是数据不存在的 (时候所返回的) 信息必须是准确的”这个需求是矛盾的" , 这就能对得上和布隆过滤器相反的那段描述

[zhoudaiyu]

bitmap ？

[zeni123]

@moliliang
布隆过滤器的保证的是 数据 存在 的时候返回的信息是正确的 这样的话可以把所有 存在 的数据放到过滤器里面。

楼主要求的是数据 不存在 的时候返回的信息是正确的，也就是说要把所有 不存在 的数据放到过滤器里面...这样的数据有无穷多

[zeni123]

@noobmaster 看来是真的需要存下所有的信息了，要不你还要发明新布隆过滤器算法

[rrfeng]

bloom filter 返回无是可信的，返回有是不可信的。

[matrix1010]

并发 300w 可不是小数目。建议你先说一下实际场景，这张表存的是什么，为什么会有这么高的并发

[rrfeng]

1 亿其实不大，数据库索引做好完全扛得住……

[zeni123]

https://stackoverflow.com/questions/13263220/is-there-any-probabilistic-data-structure-that-gives-false-negatives-but-not-fal

[noobmaster]

@matrix1010 300w 每天是比较极端的情况，正常应该是百万以下。因为原始数据比较多，所以需要过滤掉已经存在的数据，但是为了避免遗漏所以不存在是必须返回 false 。

[matrix1010]

@noobmaster 我确定一下你说 300w 并发是指同时处理 300 万个请求还是 1 天总共 300 万个?

[2owe]

300 0000 / (24 * 60 * 60) = 34.722222222

约 35 次 /秒，考虑波动，算峰值 100 次 /秒，实际要求大概一次查询不能超过 10ms 。

这个级别，多数数据存储都能满足。