这是一个创建于 1918 天前的主题，其中的信息可能已经有所发展或是发生改变。
这种 Nosql 应该不叫“kv 库”了吧，应该叫做“v 库”了，因为不需要键值，只需要在千万级数据中查询某个特定值的存在，返回 bool 值即可，查询时间毫秒级
求推荐
 |
1
ClarkAbe 2019-09-18 15:53:17 +08:00 via Android
这叫 k 库吧.....直接用一个 map 替代就行有这个键就 true 没有就.....
|
 |
2
OakScript 2019-09-18 16:11:26 +08:00
布隆过滤器？
|
 |
3
sadfQED2 2019-09-18 16:12:32 +08:00 via Android
Redis 装布隆过滤器扩展应该就是你想要的了
|
 |
4
nicon 2019-09-18 16:13:27 +08:00
布隆过滤器
|
 |
5
lihongjie0209 2019-09-18 17:31:53 +08:00
首先排除布隆过滤器， 布隆过滤器是一个概率型数据结构， 无法简单的使用 bool 作为返回值， 除非你只用它来确认数据不存在。
|
 |
6
maemual 2019-09-18 17:33:47 +08:00
redis 存 kv，value 随意。。。。千万数量级不算多大，毫秒级不是问题
|
 |
7
YUyu101 2019-09-18 19:48:43 +08:00
kv 本来就无所谓 v，v 又不直接存在结构里，只是个指针嘛。
|
 |
8
luob 2019-09-18 20:01:28 +08:00 via iPhone
这应该叫 k 库不是 v 库……
直接存 k，v 全都为空就行了。 |
 |
9
0x000007b 2019-09-18 21:59:29 +08:00
@lihongjie0209 为啥，虽然 bloom 有误判率但功能上不是正好能完美实现嘛
|
|
10
lihongjie0209 2019-09-18 22:01:54 +08:00
@0x000007b #9 `只需要在千万级数据中查询某个特定值的存在` > 无法做到， 只能查询某个特定的值不存在
|
 |
11
ztcaoll222 2019-09-18 22:04:41 +08:00
@lihongjie0209 #10 能接受少量的误判率不就能证明存在吗
|
|
12
lihongjie0209 2019-09-18 22:07:53 +08:00
@ztcaoll222 #11 只能证明“可能”存在
|
|
13
ztcaoll222 2019-09-18 22:08:32 +08:00
@lihongjie0209 #12 对啊, 我不是说了接受误判率吗
|
|
14
lihongjie0209 2019-09-18 22:14:50 +08:00
@ztcaoll222 #13 存在是一个绝对的概念， 就是 100%， 没有一种 “存在” 的定义是“在一定概率下 100%”。
|
|
15
ztcaoll222 2019-09-18 22:21:01 +08:00
@lihongjie0209 #14 ? 你在说什么, "可能存在"这个词是错的啰 ?
这么纠结于存在这个定义, 不如问问楼主能否接受使用布隆过滤器这个方案 |
 |
16
dusu 2019-09-18 22:41:49 +08:00 via iPhone
能接受误差 Redis 的 HyperLogLog 可以解惑。存 2^64 个元素仅需 12K。
不能接受误差 Redis 的 bitmap 也是不错的选择。 前提是你输入的数据是整型 |
 |
17
fluorinedog 2019-09-19 00:09:36 +08:00 via Android
@dusu 什么鬼，hll 是用来计算 distinct value 的估计数量的，跟这需求不沾边。
bloom filter 平均一个元素占用几个 bit，不过确实是概率算法。 如果数据有范围，比如 N 个数据，出现在[0, 10N]区间里，其实 bitmap 就不错。 要保证精确的话，还是得 bloom filter 初筛，然后 kv 表查询。 |
|
18
dusu 2019-09-19 00:15:44 +08:00 via iPhone
@fluorinedog hll 要统计的时候直接把整型往里丢 数据涨了就代表集合里没有 没涨不就代表集合里没有么？
当然这不是原子操作，高并发下肯定有问题，主要是楼主也没有说要多大并发，只是要求毫秒级。 |
 |
19
aguesuka 2019-09-19 09:23:41 +08:00 via Android
千万级的数据用 rbtree 也是毫秒级的吧。只要内存够大
|
 |
20
realpg 2019-09-19 18:20:02 +08:00
直接 kv 库去 get 那个 key 不就好了
|
|
21
fluorinedog 2019-10-08 02:02:33 +08:00 via Android
@dusu 一口老血喷到屏幕上...
第一，hll 可以基于高并发的原子操作，你刚好说反了 第二，hll 是概率算法，在后期 hll 自己的数据结构起主导后，对于每个桶，要么不更新，要么一次更新增加 N 个元素。打个比方，hll 就像一个精确到 100 的倍数的 distinct value 统计函数，你用它来统计某个数是否在集合中的话，错误率是 99%好吧。 |
|
22
dusu 2019-10-08 22:52:14 +08:00
@fluorinedog 感谢老哥指导，小弟受教~之前确实理解错了
不过我觉得可以通过控制每个 hll 桶内元素的数量去解决误差？ 像类似于可能在 1w 或 10w 的数据集的时候误差比较小， 那么通可以过 id % 桶数量 找到对应 key 来减少误差， 个人想法哈，仅供讨论... |
|
23
fluorinedog 2019-10-10 16:02:16 +08:00 via iPad
@dusu 那 hll 就没有任何优势了。hll 本来就是用相对少量的定长内存统计大量的数据，但是当数据量很少时还不如 std::set 呢...
同时从信息论的角度来看，hll 平均每个元素不到 0.1 个 bit 时，必然无法完成集合的 exists 功能。作为对比，bloom filter 平均一个元素有几个 bit，已经基本压缩到极致了。 |
Select Language