这是一个创建于 1071 天前的主题，其中的信息可能已经有所发展或是发生改变。
背景
- 需要提供一个接口用来查询数据在不在表里面(只需知道是否存在就行，不需要额外数据)，每天的并发量是 300w 左右。
- 接口和数据库都是采用的 md5 作为 key, 允许数据实际存在但是返回不存在，但是数据不存在的信息必须是准确的(跟布隆过滤器误报的场景刚好相反)。
- 数据表有一亿行左右。
问题
- 不加缓存，直接查数据库。查询压力是不是过大了点？
- 用 redis 缓存存在数据的 md5 ，后续查询压力会逐渐落到 redis 上，用 set 类型是否是开销最小的？
- 跟布隆过滤器误报场景相反的数据结构？
 |
1
colatin 2021-12-03 17:58:06 +08:00  1
“ 允许数据实际存在但是返回不存在，但是数据不存在的信息必须是准确的”这个需求是矛盾的。
|
 |
2
noobmaster OP @colatin 是的，把自己绕进去了。
|
|
3
noobmaster OP @colatin 所以就是必须以某种形式保存最多 1 亿个 md5 ，只是用什么形式成本和效率有比较好平衡
|
 |
4
moliliang 2021-12-03 18:09:55 +08:00 1
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 |
 |
5
WriteCloser 2021-12-03 18:15:30 +08:00 1
我用我并不是很好的数据算了下
|
|
6
WriteCloser 2021-12-03 18:20:05 +08:00
32 位 = 2.75 Byte = 0.00275 KB = 0.000002685546875 mb = 0.000000002622604 G * 1 亿 = 0.2G 如果不接受假阳性硬放好像问题不大，不知道是不是这样
|
|
7
noobmaster OP @moliliang 布隆过滤器是 “存在的不一定存在”，实现不了“存在的一定存在”吧。
反过来去思考，要求存在这个信息是准确的话，不存在的信息就也是精确的了。 看起来是必须保存这 1 亿个 md5 的完整信息了😳 |
|
8
noobmaster OP 存 redis 的话，set 应该是最合适的数据类型了吧。
|
 |
9
zeni123 2021-12-03 19:12:22 +08:00
@colatin 并不矛盾
数据不存在 => 一定返回 false 返回 true => 数据一定 存在 返回 false => 数据有可能存在有可能不存在 数据存在 => 有可能返回 true 有可能返回 false 逻辑是自洽的 |
|
10
zeni123 2021-12-03 19:17:33 +08:00
@colatin 他可能是说 "允许数据实际存在但是返回不存在，但是数据不存在的 (时候所返回的) 信息必须是准确的”这个需求是矛盾的" , 这就能对得上和布隆过滤器相反的那段描述
|
 |
11
zhoudaiyu 2021-12-03 19:30:36 +08:00
bitmap ？
|
|
12
zeni123 2021-12-03 19:34:39 +08:00
@moliliang
布隆过滤器的保证的是 数据 存在 的时候返回的信息是正确的 这样的话可以把所有 存在 的数据放到过滤器里面。 楼主要求的是数据 不存在 的时候返回的信息是正确的，也就是说要把所有 不存在 的数据放到过滤器里面...这样的数据有无穷多 |
|
13
zeni123 2021-12-03 19:42:57 +08:00
@noobmaster 看来是真的需要存下所有的信息了，要不你还要发明新布隆过滤器算法
|
 |
14
rrfeng 2021-12-03 19:53:35 +08:00
bloom filter 返回无是可信的，返回有是不可信的。
|
 |
15
matrix1010 2021-12-03 19:53:40 +08:00
并发 300w 可不是小数目。建议你先说一下实际场景，这张表存的是什么，为什么会有这么高的并发
|
|
16
rrfeng 2021-12-03 19:54:10 +08:00
1 亿其实不大，数据库索引做好完全扛得住……
|
|
17
zeni123 2021-12-03 19:54:45 +08:00
|
|
18
noobmaster OP @matrix1010 300w 每天是比较极端的情况，正常应该是百万以下。因为原始数据比较多，所以需要过滤掉已经存在的数据，但是为了避免遗漏所以不存在是必须返回 false 。
|
|
19
matrix1010 2021-12-03 20:02:24 +08:00
@noobmaster 我确定一下你说 300w 并发是指同时处理 300 万个请求还是 1 天总共 300 万个?
|
 |
20
2owe 2021-12-03 20:02:57 +08:00
300 0000 / (24 * 60 * 60) = 34.722222222
约 35 次 /秒，考虑波动，算峰值 100 次 /秒，实际要求大概一次查询不能超过 10ms 。 这个级别，多数数据存储都能满足。 |
|
21
noobmaster OP @rrfeng 其实数据库硬抗也是能扛下的，只是不希望这个需求把数据库资源给占用太多。还是需要缓存在前面扛一扛
|
|
22
noobmaster OP @matrix1010 一天
|
 |
23
solos 2021-12-03 20:22:17 +08:00
分表再加一列整数 hash 就可以了吧 不行可以试试整数 hash 再加压缩位图 布隆过滤器其实就是 hash 加混用位图
|
 |
24
leeg810312 2021-12-03 20:23:06 +08:00 via Android
@zeni123 你是不是说错了，布隆过滤器检查不存在是确定的，存在是可能性，而且填充元素越接近满时误判率越高，所以 1 楼说楼主需求有矛盾没有错。
@noobmaster MySQL 的话用只读副本就可以了，比缓存 1 亿数据更容易实现 |
 |
25
Doenake 2021-12-03 20:51:23 +08:00
既然“允许数据实际存在但是返回不存在”，那所有情况都返回不存在不就解决了，也满足要求。
|
 |
26
securityCoding 2021-12-03 21:07:50 +08:00 via Android
这个程度的 qps 用数据库扛就好了，按哈希策略单表拆成多表，md5 做一下前缀索引。
|
 |
27
rekulas 2021-12-03 22:59:43 +08:00
每天的并发量是 300w 左右。。。
发帖人可能对目前的硬件性能有什么误解，一天才这么点峰值给你算高点 1 万 qps 够用了，只要硬件不太差轻轻松松就扛下了，完全不需要丢内存 甚至自己写个文本数据库都能 hold 而且你的峰值很低完全不用担心数据库太占资源的问题，建议用 m2 硬盘+rocksdb ，qps 轻轻松松上 10 万+而且对其他服务影响不大 |
 |
28
GrayXu 2021-12-04 01:32:17 +08:00
bf 就是压缩了信息，所以会有 false positive 。建议重学 bf 原理
|
 |
29
eason1874 2021-12-04 08:09:08 +08:00
哪有用天算 QPS 的，要是 300*10000/24/60/60 这么算，平均每秒才 35 ，放什么数据库都能行
QPS 每秒几千的，预留三五百 MB 内存，全部放 Redis 就够用了 放内存不够快再用布隆过滤器 > Redis > 数据库，过滤器大小设置合适，误报率很低，因为报不存在的就一定不存在，函数计算可以解决大部分请求，报存在的再查 Redis 和数据库是否真的存在，然后把准确结果缓存到 Redis |
 |
30
lxyer1 2021-12-04 22:26:20 +08:00
每天的并发量是 300w......
|
|
32
zeni123 2021-12-07 04:03:24 +08:00
@moliliang
你可以说一说怎么用布隆过滤器实现。 「存在的不一定存在，不存在的一定不存在」 这个描述过于笼统，会让你记错的。 「 X 存在的 Y 不一定存在，X 不存在的 Y 一定不存在」，你可以看一看这里的 X 和 Y 代表着什么， 把它们搞反了意思完全就不一样了。而你理解错了的原因也恰好在此。 |
|
34
zeni123 2021-12-07 19:34:41 +08:00
@moliliang
因为不只有布隆过滤器可以被归纳为 「存在的不一定存在，不存在的一定不存在」 这个特性，还有别的数据结构。 可以举一个具体的例子 数据库里面有 1000 条数据， 你把这 1000 条数据加到布隆过滤器里, 你把这 1000 条数据加到 LRUCache 里, 你在你程序里面使用 LRUCache 和布隆过滤器里 下面的四个描述有两个是正确的，而 OP 要的恰好就不是布隆过滤器的那个。 1. 数据库里 存在的 LRUCache 里 不一定存在， 数据库里 不存在的 LRUCace 里 一定不存在 2. LRUCache 存在的 数据库里 不一定存在，LRUCace 不存在的 数据库里 一定不存在 3. 数据库里 存在的 布隆过滤器里 不一定存在， 数据库里 不存在的 布隆过滤器里 一定不存在 4. 布隆过滤器里 存在的 数据库里 不一定存在，布隆过滤器里 不存在的 数据库里 一定不存在 你很理解布隆过滤器，但是 OP 问的就不是这个。 |
Select Language