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

[noobmaster]

背景

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

问题

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

[noobmaster]

@rrfeng 其实数据库硬抗也是能扛下的，只是不希望这个需求把数据库资源给占用太多。还是需要缓存在前面扛一扛

[noobmaster]

@matrix1010 一天

[solos]

分表再加一列整数 hash 就可以了吧 不行可以试试整数 hash 再加压缩位图 布隆过滤器其实就是 hash 加混用位图

[leeg810312]

@zeni123 你是不是说错了，布隆过滤器检查不存在是确定的，存在是可能性，而且填充元素越接近满时误判率越高，所以 1 楼说楼主需求有矛盾没有错。

@noobmaster MySQL 的话用只读副本就可以了，比缓存 1 亿数据更容易实现

[Doenake]

既然“允许数据实际存在但是返回不存在”，那所有情况都返回不存在不就解决了，也满足要求。

[securityCoding]

这个程度的 qps 用数据库扛就好了，按哈希策略单表拆成多表，md5 做一下前缀索引。

[rekulas]

每天的并发量是 300w 左右。。。
发帖人可能对目前的硬件性能有什么误解，一天才这么点峰值给你算高点 1 万 qps 够用了，只要硬件不太差轻轻松松就扛下了，完全不需要丢内存
甚至自己写个文本数据库都能 hold
而且你的峰值很低完全不用担心数据库太占资源的问题，建议用 m2 硬盘+rocksdb ，qps 轻轻松松上 10 万+而且对其他服务影响不大

[GrayXu]

bf 就是压缩了信息，所以会有 false positive 。建议重学 bf 原理

[eason1874]

哪有用天算 QPS 的，要是 300*10000/24/60/60 这么算，平均每秒才 35 ，放什么数据库都能行

QPS 每秒几千的，预留三五百 MB 内存，全部放 Redis 就够用了

放内存不够快再用布隆过滤器 > Redis > 数据库，过滤器大小设置合适，误报率很低，因为报不存在的就一定不存在，函数计算可以解决大部分请求，报存在的再查 Redis 和数据库是否真的存在，然后把准确结果缓存到 Redis

[lxyer1]

每天的并发量是 300w......

[moliliang]

@zeni123 可能要重新理解一下 布隆过滤器。。。

[zeni123]

@moliliang

你可以说一说怎么用布隆过滤器实现。

「存在的不一定存在，不存在的一定不存在」 这个描述过于笼统，会让你记错的。

「 X 存在的 ​Y 不一定存在，X 不存在的 Y 一定不存在」，你可以看一看这里的 X 和 Y 代表着什么， 把它们搞反了意思完全就不一样了。而你理解错了的原因也恰好在此。

[moliliang]

@zeni123
并不笼统啊，咋笼统了。

[zeni123]

@moliliang

因为不只有布隆过滤器可以被归纳为 「存在的不一定存在，不存在的一定不存在」 这个特性，还有别的数据结构。

可以举一个具体的例子

数据库里面有 1000 条数据，
你把这 1000 条数据加到布隆过滤器里,
你把这 1000 条数据加到 LRUCache 里,

你在你程序里面使用 LRUCache 和布隆过滤器里


下面的四个描述有两个是正确的，而 OP 要的恰好就不是布隆过滤器的那个。

1. 数据库里 存在的 LRUCache 里 不一定存在， 数据库里 不存在的 LRUCace 里 一定不存在
2. LRUCache 存在的 数据库里 不一定存在，LRUCace 不存在的 数据库里 一定不存在
3. 数据库里 存在的 布隆过滤器里 不一定存在， 数据库里 不存在的 布隆过滤器里 一定不存在
4. 布隆过滤器里 存在的 数据库里 不一定存在，布隆过滤器里 不存在的 数据库里 一定不存在


你很理解布隆过滤器，但是 OP 问的就不是这个。