海量数据去重hash与布隆过滤器

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
简介: 海量数据去重hash与布隆过滤器

什么是缓存穿透:

所谓缓存穿透,就是我们的mysql和redis都没有这个数据。黑客可以利用这个漏洞导致mysql压力过大,如此一来将整个系统陷入瘫痪。   数据的读取是先访问redsi,如果redis有则直接返回。如果不存在就去访问mysql。如果mysql不存在,直接返回。如果mysql存在,将mysql存在的key写回给redis。下次在查询的时候直接从redis拿数据

解决方案:

1>

在redis端设置<key,null>键值对。以此避免访问mysql,缺点是<key,null>过多的话会占用过多内存。我们可以设置一个缓存过期,比如60ms,那么我们的redis就不会堆积过多的数据,当攻击停止之后我们的redis会将<key,null>全部释放掉.

2>

在server端存储一个布隆过滤器,将mysqlb包含的key放入布隆过滤器中,布隆过滤器能过滤掉一定不存在的数据。

需求: 从海量数据中查询某字符串是否存在:

c++标准库(STL)中的setmap结构都是采⽤红⿊树实现的,它增删改查的时间复杂度是 log2为底N的对数。

对于严格平衡⼆叉搜索树(AVL)100w条数据组成的红⿊树,只需要⽐较20就能找到该值;对于

10亿条数据只需要⽐较30就能找到该数据;也就是查找次数跟树的⾼度是⼀致的;

对于红⿊树来说平衡的是⿊节点⾼度,所以研究⽐较次数需要考虑树的⾼度差,最好情况某条树链

路全是⿊节点,假设此时⾼度为h1,最差情况某条树链路全是⿊红节点间隔,那么此时树⾼度为

2*h1;

在红⿊树中每⼀个节点都存储keyval字段,key是⽤来做⽐较的字段;红⿊树并没有要求key字段

唯⼀,在setmap实现过程中限制了key字段唯⼀。我们来看nginx的红⿊树实现:

// 这个是截取 nginx 的红⿊树的实现,这段代码是 insert 操作中的⼀部分,执⾏完这个函数还
需要检测插⼊节点后是否平衡(主要是看他的⽗节点是否也是红⾊节点)
// 调⽤ ngx_rbtree_insert_value 时,temp传的参数为 红⿊树的根节点,node传的参数为
待插⼊的节点
void ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t
*node,
 ngx_rbtree_node_t *sentinel) {
 ngx_rbtree_node_t **p;
 for ( ;; ) {
     p = (node->key < temp->key) ? &temp->left : &temp->right;// 这⾏很重要
     if (*p == sentinel) {
         break;
     }
     temp = *p;
 }
 *p = node;                               // 找到待插入节点的位置
 node->parent = temp;
 node->left = sentinel;
 node->right = sentinel;
 ngx_rbt_red(node);                      //着色
}
// 不插⼊相同节点 如果插⼊相同 让它变成修改操作 此时 红⿊树当中就不会有相同的key了
定时器 key 时间戳
// 如果我们插⼊key = 12,如上图红⿊树,12号节点应该在哪个位置? 如果我们要实现插⼊存在
的节点变成修改操作,该怎么改上⾯的函数
void ngx_rbtree_insert_value_ex(ngx_rbtree_node_t *temp, ngx_rbtree_node_t
*node,
 ngx_rbtree_node_t *sentinel) {
另外set和map的关键区别是set不存储val字段;
优点:存储效率⾼,访问速度⾼效;
缺点:对于数据量⼤且查询字符串⽐较⻓且查询字符串相似时将会是噩梦;
unordered_map
c++标准库(STL)中的unordered_map<string, bool>是采⽤hashtable实现的;
构成:数组+hash函数;
它是将字符串通过hash函数⽣成⼀个整数再映射到数组当中;它增删改查的时间复杂度是o(1);
图结构示例:
hash函数的作⽤:避免插⼊的时候字符串的⽐较;hash函数计算出来的值通过对数组⻓度的取模
能随机分布在数组当中;
hash函数⼀般返回的是64位整数,将多个⼤数映射到⼀个⼩数组中,必然会产⽣冲突;
如何选取hash函数?
1. 选取计算速度快;
2. 哈希相似字符串能保持强随机分布性(防碰撞);
 ngx_rbtree_node_t **p;
 for ( ;; ) {
// {-------------add-------------
     if (node->key == temp->key) {
     temp->value = node->value;
     return;
 }
// }-------------add-------------
 p = (node->key < temp->key) ? &temp->left : &temp->right;// 这⾏很重要
 if (*p == sentinel) {
 break;
 }
 temp = *p;
 }
 *p = node;
 node->parent = temp;
 node->left = sentinel;
 node->right = sentinel;
 ngx_rbt_red(node);
}

另外setmap的关键区别是set不存储val字段;

优点:存储效率⾼,访问速度⾼效;

缺点:对于数据量⼤且查询字符串⽐较⻓且查询字符串相似时将会是噩梦;

unordered_map

c++标准库(STL)中的unordered_map<string, bool>是采⽤hashtable实现的;

构成:数组+hash函数;

它是将字符串通过hash函数⽣成⼀个整数再映射到数组当中;它增删改查的时间复杂度是o(1);

图结构示例:

 

hash函数的作⽤:避免插⼊的时候字符串的⽐较hash函数计算出来的值通过对数组⻓度的取模

随机分布在数组当中;

hash函数⼀般返回的是64位整数,将多个⼤数映射到⼀个⼩数组中,必然会产⽣冲突;

如何选取hash函数?

1. 选取计算速度快;

2. 哈希相似字符串能保持强随机分布性(防碰撞);

murmurhash1murmurhash2murmurhash3siphashredis6.0当中使⽤,rust等⼤多数

语⾔选⽤的hash算法来实现hashmap),cityhash都具备强随机分布性;测试地址如下:

https://github.com/aappleby/smhasher

负载因⼦:数组存储元素的个数/数组⻓度;负载因⼦越⼩,冲突越⼩;负载因⼦越⼤,冲突越⼤;

hash冲突解决⽅案:

链表法

引⼊链表来处理哈希冲突;也就是将冲突元素⽤链表链接起来;这也是常⽤的处理冲突的⽅式;但是可能出现⼀种极端情况,冲突元素⽐较多,该冲突链表过⻓,这个时候可以将这个链表转换为红⿊树;由原来链表时间复杂度o(n) 转换为红⿊树时间复杂度 ;那么判断该链表过⻓的依据是多少?可以采⽤超过256或者512(经验值)个节点的时候将链表结构转换为红⿊树结构;

开放寻址法

将所有的元素都存放在哈希表的数组中,不使⽤额外的数据结构;⼀般使⽤线性探查的思路解

决;

1. 当插⼊新元素的时,使⽤哈希函数在哈希表中定位元素位置;

2. 检查数组中该槽位索引是否存在元素。如果该槽位为空,则插⼊,否则3

3. 2 检测的槽位索引上加⼀定步⻓接着检查2

加⼀定步⻓分为以下⼏种:

1. i+1,i+2,i+3,i+4 ... i+n

2. i- ,i+ ,i- ,1+ ...

这两种都会导致同类hash聚集;也就是近似值它的hash值也近似,那么它的数组槽位也靠

近,形成hash聚集;第⼀种同类聚集冲突在前,第⼆种只是将聚集冲突延后;

另外还可以使⽤双重哈希来解决上⾯出现hash聚集现象:

       在.net HashTable类的hash函数Hk定义如下:

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) %

(hashsize – 1)))] % hashsize

在此(1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))) hashsize

互为素数(两数互为素数表示两者没有共同的质因⼦);

执⾏了hashsize 次探查后,哈希表中的每⼀个位置都有且只有⼀次被访问到,也就是

说,对于给定的key,对哈希表中的同⼀位置不会同时使⽤Hi Hj

  2. 具体原理:https://www.cnblogs.com/organic/p/6283476.html

同样的hashtable中节点存储了keyvalhashtable并没有要求key的⼤⼩顺序,我们同样可以修

改代码让插⼊存在的数据变成修改操作;

优点:访问速度更快;不需要进⾏字符串⽐较

缺点:需要引⼊策略避免冲突,存储效率不⾼;空间换时间;

       

 

总结

红⿊树和hashtable都不能解决海量数据问题,它们都需要存储具体字符串,如果数据量⼤,提供

不了⼏百G的内存;所以需要尝试探寻不存储key的⽅案,并且拥有hashtable的优点(不需要⽐较

字符串);

布隆过滤器

定义:布隆过滤器是⼀种概率型数据结构,它的特点是⾼效的插⼊和查询,能明确告知某个字符串

⼀定不存在或者可能存在;布隆过滤器相⽐传统的查询结构(例如:hashsetmap等数据结构)更加⾼效,占⽤空间更⼩;但是其缺点是它返回的结果是概率性的,也就是说结果存在误差的,虽然这个误差是可控的;同时它不⽀持删除操作

组成:位图(bit数组)+ nhash函数

 

原理:当⼀个元素加⼊位图时,通过khash函数将这个元素映射到位图的k个点,并把它们置为

1;当检索时,再通过khash函数运算检测位图的k个点是否都为1;如果有不为1的点,那么认为

不存在;如果全部为1,则可能存在(存在误差);

 

在位图中每个槽位只有两种状态(0或者1),⼀个槽位被设置为1状态,但不明确它被设置了多少

次;也就是不知道被多少个str1哈希映射以及是被哪个hash函数映射过来的;所以不⽀持删除操

作;

在实际应⽤过程中,布隆过滤器该如何使⽤?要选择多少个hash函数,要分配多少空间的位图,存储多少元素?另外如何控制假阳率(布隆过滤器能明确⼀定不存在,不能明确⼀定存在,那么存在的判断是有误差的,假阳率就是错误判断存在的概率)?

n -- 布隆过滤器中元素的个数,如上图 只有str1str2 两个元素 那么n=2

p -- 假阳率,在0-1之间0.000000

m -- 位图所占空间

k -- hash函数的个数

公式如下:

n = ceil(m / (-k / log(1 - exp(log(p) / k))))

p = pow(1 - exp(-k / (m / n)), k)

m = ceil((n * log(p)) / log(1 / pow(2, log(2))));

k = round((m / n) * log(2));

假定我们选取这四个值为:

n = 4000

p = 0.000000001

m = 172532

k = 30

四个值的关系:

 

在实际应⽤中,我们确定np,通过上⾯的计算算出mk;也可以在⽹站上选取合适的值:

https://hur.st/bloomfilter

已知k,如何选择khash函数?

// 采⽤⼀个hash函数,给hash传不同的种⼦偏移值

// #define MIX_UINT64(v) ((uint32_t)((v>>32)^(v)))

uint64_t hash1 = MurmurHash2_x64(key, len, Seed);

uint64_t hash2 = MurmurHash2_x64(key, len, MIX_UINT64(hash1));

for(i = 0; i < k; i++) // k hash函数的个数

{

Pos[i] =(hash1 + i*hash2) % m; // m 是位图的⼤⼩

}

// 通过这种⽅式来模拟k hash函数 跟我们前⾯开放寻址法 双重hash是⼀样的思路

应⽤源码:http://gitlab.0voice.com/0voice/bloomfilter/tree/master

目录
相关文章
|
5月前
|
人工智能 自然语言处理 搜索推荐
AI智能导诊系统开发技术解析
智能导诊系统基于人工智能、大数据和医疗信息化技术,优化患者就医流程,提升资源匹配效率。其核心功能包括智能分诊、症状自评与风险评估及就医路径规划,通过自然语言处理、医学知识图谱、多模态交互等技术实现精准服务。系统可将门诊误挂率从23%降至6%,并显著提高急危重症识别效率,为患者提供全流程导航支持。
309 3
|
1月前
|
人工智能 缓存 JavaScript
SpringBoot 公共字段自动填充的6种方法
本文深入探讨了在Java开发中如何高效维护公共字段的多种解决方案。首先分析了手动设置公共字段带来的代码重复、维护成本高和易遗漏等问题,接着介绍了使用MyBatis-Plus自动填充、AOP统一处理等基础与进阶方案,实现字段自动赋值。文章还涵盖了多数据源适配、分布式ID生成、空指针防护、字段覆盖问题解决、性能优化以及操作日志追踪等生产环境中的最佳实践与避坑指南。最终通过方案组合使用,显著提升了开发效率与系统稳定性,为构建高质量企业级应用提供了有力支撑。
127 0
|
安全 关系型数据库 MySQL
Linux(CentOS6)安装MySQL5.6
Linux(CentOS 6)系统上安装MySQL 5.6版本的详细步骤,包括准备数据存放目录、创建用户、下载安装包、初始化数据库、配置服务脚本、设置环境变量等操作。
873 1
|
机器学习/深度学习 存储 人工智能
AI歌姬,C位出道,基于PaddleHub/Diffsinger实现音频歌声合成操作(Python3.10)
懂乐理的音乐专业人士可以通过写乐谱并通过乐器演奏来展示他们的音乐创意和构思,但不识谱的素人如果也想跨界玩儿音乐,那么门槛儿就有点高了。但随着人工智能技术的快速迭代,现在任何一个人都可以成为“创作型歌手”,即自主创作并且让AI进行演唱,极大地降低了音乐制作的门槛。 本次我们基于PaddleHub和Diffsinger实现音频歌声合成操作,魔改歌曲《学猫叫》。
AI歌姬,C位出道,基于PaddleHub/Diffsinger实现音频歌声合成操作(Python3.10)
|
11月前
|
资源调度 前端开发 JavaScript
Python学习二:Python包管理器pip
这篇文章介绍了Python包管理器pip的基本概念、基本操作、如何更改下载源为国内镜像以加速下载,以及如何指定安装包的位置。
413 0
Python学习二:Python包管理器pip
|
11月前
|
Java Maven Spring
SpringBoot日志整合
SpringBoot日志整合
183 2
|
数据可视化
RNAseq|构建预后模型后你还需要这些图,森林图,诺莫图,校准曲线,DCA决策曲线
RNAseq|构建预后模型后你还需要这些图,森林图,诺莫图,校准曲线,DCA决策曲线
535 0
|
资源调度 分布式计算 Hadoop
bigdata-09-Yarn原理与实战
bigdata-09-Yarn原理与实战
232 0
|
开发者 Windows
什么是DRM以及为何需要移除它?
数字版权管理(DRM)是一种用于保护数字内容的技术,它限制了用户对特定内容的使用和传播。DRM技术的目的是在保护知识产权的同时,防止非法复制和盗版。然而,有些人认为DRM限制了用户的合法权益,因此需要将其移除。
2682 1
|
Java API Maven
SpringBoot 调用外部接口的三种方式--学习总结
SpringBoot 调用外部接口的三种方式--学习总结
369 1