好素材网站,好看的网页设计公司,平台型网站建设方案,安阳汤阴县网站建设场景描述 小程序用户的openid作为最主要的业务查询字段#xff0c;在做了缓存设计之后仍有非常高频的查询#xff0c;通过埋点简单统计约在每日1000w次。 其中#xff1a;由于有新增用户原因#xff0c;导致请求的openid根本不存在MySQL数据库中#xff0c;这部分统计约占…场景描述 小程序用户的openid作为最主要的业务查询字段在做了缓存设计之后仍有非常高频的查询通过埋点简单统计约在每日1000w次。 其中由于有新增用户原因导致请求的openid根本不存在MySQL数据库中这部分统计约占30%左右也就是约300w次查询是浪费的。 假设openid的总量可能达到10亿级别 解决思路基于redis使用布隆过滤器
方案介绍
1. 布隆过滤器 布隆过滤器Bloom Filter 是一种数据结构其主要功能是判断某个元素是否出现在集合中。 它通过使用多个哈希函数将元素映射到一个位数组中并将对应位标记为1来实现对元素的判重。 如果一个元素在位数组中对应的位置上有一位为0那么该元素一定不存在于集合中 如果所有对应位都为1那么该元素可能存在于集合中。 具体来说 当要加入一个元素时使用多个不同的哈希函数对该元素进行哈希得到多个哈希值然后将这些哈希值对应的位数组上的位置置为1。 当查找一个元素时同样使用多个哈希函数进行哈希然后查看对应位置上的位 如果存在任意一位为0那么该元素不存在于集合中 如果所有位都为1那么该元素可能存在于集合中需要进一步确认。 但是布隆过滤器存在一定的误判率。 对于一个元素如果多个哈希函数将其映射到的位都已被标记为1则它可能被误判为存在于集合中即有一定的假阳性率 。 误判率取决于哈希函数的数量和位向量的长度。 2. 10亿数据如何做布隆过滤
· redis的bitmap Bitmap是一种Bit数组数据结构它的主要作用是储存0和1两个状态。 在Redis中Bitmap通过字符串来实现一个字符串可以存储超过2^32个元素所以一个bloom能存储的最大上限就是2^32个约42.9亿。占用的内存是512M 虽然单个bitmap最大可达到42亿但是算上误差率其实是不够的而且在redis中我们也应该尽量避免这种大key的使用 · 分片 范围划分将 32-bit 的范围 ([0, n)) 划分为 2^10 个桶每一个桶有一个 Container 来存放一个数值的低26位存储在存储和查询数值的时候将一个数值 k 划分为高 10 位(k % 2^10)和低 26 位(k mod 2^26)取高 10 位找到对应的桶然后在低 26 位存放在相应的 Container 中查询判断当查询一个数值 k 是否存在时我们只需要判断 k mod 2^26 是否存在于对应的 Container 中即可。 · 实现取高位和低位代码 取高位作桶,就是通过位运算向右移10位 将一个数的二进制位向左或向右移动特定的位数。向左移动相当于在该数的二进制表示中加上多个0向右移动相当于去掉多余的二进制位 $container $hash 10; 取低位作数据字段就是通过位运算取26位 它对两个数的每一个二进制位进行比较只有当两个数的对应二进制位都为1时结果才会将该位置设置为1否则设置为0 0x3FFFFFF是26位全1的二进制数的16进制表示方式 可以简单理解为就是截取了一个数的低26位 $index $hash 0x3FFFFFF; · go-zero的bloom介绍(core/bloom/bloom.go) // New create a Filter, store is the backed redis, key is the key for the bloom filter,
// bits is how many bits will be used, maps is how many hashes for each addition.
// best practices:
// elements - means how many actual elements
// when maps 14, formula: 0.7*(bits/maps), bits 20*elements, the error rate is 0.000067 1e-4
// for detailed error rate table, see http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
func New(store *redis.Redis, key string, bits uint) *Filter {return Filter{bits: bits,bitSet: newRedisBitSet(store, key, bits),}
} go-zero内置的bloom默认采用的hash次数是14元素预估需要使用的bitmap位数是20倍多元素数量错误率在0.000067左右 · Hash函数规划 已知元素总量为10亿分片数为2^101024那么每个分片元素数量为976562需要的bitmap长度是 20*976562 19531240也就是小于2^2533554432redis官网上介绍bitmap长度达到2^26-1大约需要8M内存那么总内存预估使用8G左右分散在集群的各个节点上 所以保留一定的弹性范围在使用go-zero自带的bloom时key根据2^10进行分片单个bloom的bits30000000
