什么是缓存穿透:
所谓缓存穿透,就是我们的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)中的set和map结构都是采⽤红⿊树实现的,它增删改查的时间复杂度是 log2为底N的对数。
对于严格平衡⼆叉搜索树(AVL),100w条数据组成的红⿊树,只需要⽐较20次就能找到该值;对于
10亿条数据只需要⽐较30次就能找到该数据;也就是查找次数跟树的⾼度是⼀致的;
对于红⿊树来说平衡的是⿊节点⾼度,所以研究⽐较次数需要考虑树的⾼度差,最好情况某条树链
路全是⿊节点,假设此时⾼度为h1,最差情况某条树链路全是⿊红节点间隔,那么此时树⾼度为
2*h1;
在红⿊树中每⼀个节点都存储key和val字段,key是⽤来做⽐较的字段;红⿊树并没有要求key字段
唯⼀,在set和map实现过程中限制了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); }
另外set和map的关键区别是set不存储val字段;
优点:存储效率⾼,访问速度⾼效;
缺点:对于数据量⼤且查询字符串⽐较⻓且查询字符串相似时将会是噩梦;
unordered_map
c++标准库(STL)中的unordered_map<string, bool>是采⽤hashtable实现的;
构成:数组+hash函数;
它是将字符串通过hash函数⽣成⼀个整数再映射到数组当中;它增删改查的时间复杂度是o(1);
图结构示例:
hash函数的作⽤:避免插⼊的时候字符串的⽐较;hash函数计算出来的值通过对数组⻓度的取模
能随机分布在数组当中;
hash函数⼀般返回的是64位整数,将多个⼤数映射到⼀个⼩数组中,必然会产⽣冲突;
如何选取hash函数?
1. 选取计算速度快;
2. 哈希相似字符串能保持强随机分布性(防碰撞);
murmurhash1,murmurhash2,murmurhash3,siphash(redis6.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中节点存储了key和val,hashtable并没有要求key的⼤⼩顺序,我们同样可以修
改代码让插⼊存在的数据变成修改操作;
优点:访问速度更快;不需要进⾏字符串⽐较;
缺点:需要引⼊策略避免冲突,存储效率不⾼;空间换时间;
总结
红⿊树和hashtable都不能解决海量数据问题,它们都需要存储具体字符串,如果数据量⼤,提供
不了⼏百G的内存;所以需要尝试探寻不存储key的⽅案,并且拥有hashtable的优点(不需要⽐较
字符串);
布隆过滤器
定义:布隆过滤器是⼀种概率型数据结构,它的特点是⾼效的插⼊和查询,能明确告知某个字符串
⼀定不存在或者可能存在;布隆过滤器相⽐传统的查询结构(例如:hash,set,map等数据结构)更加⾼效,占⽤空间更⼩;但是其缺点是它返回的结果是概率性的,也就是说结果存在误差的,虽然这个误差是可控的;同时它不⽀持删除操作;
组成:位图(bit数组)+ n个hash函数
原理:当⼀个元素加⼊位图时,通过k个hash函数将这个元素映射到位图的k个点,并把它们置为
1;当检索时,再通过k个hash函数运算检测位图的k个点是否都为1;如果有不为1的点,那么认为
不存在;如果全部为1,则可能存在(存在误差);
在位图中每个槽位只有两种状态(0或者1),⼀个槽位被设置为1状态,但不明确它被设置了多少
次;也就是不知道被多少个str1哈希映射以及是被哪个hash函数映射过来的;所以不⽀持删除操
作;
在实际应⽤过程中,布隆过滤器该如何使⽤?要选择多少个hash函数,要分配多少空间的位图,存储多少元素?另外如何控制假阳率(布隆过滤器能明确⼀定不存在,不能明确⼀定存在,那么存在的判断是有误差的,假阳率就是错误判断存在的概率)?
n -- 布隆过滤器中元素的个数,如上图 只有str1和str2 两个元素 那么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
四个值的关系:
在实际应⽤中,我们确定n和p,通过上⾯的计算算出m和k;也可以在⽹站上选取合适的值:
已知k,如何选择k个hash函数?
// 采⽤⼀个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