布隆过滤器_nginx 配合布隆过滤器

使用场景：

• 在使⽤word⽂档时，word如何判断某个单词是否拼写正确？
• ⽹络爬⾍程序，怎么让它不去爬相同的url⻚⾯？允许有误差
• 垃圾邮件（短信）过滤算法如何设计？允许有误差
• 公安办案时，如何判断某嫌疑⼈是否在⽹逃名单中？控制误差 假阳率
• 缓存穿透问题如何解决？允许有误差

导致缓存穿透的原因：

redis,mysql都没有数据，黑客可以利用此漏洞导致mysql压力过大，如此以来整个系统将陷入瘫痪

---

访问mysql 读取步骤：

• 先访问redis，如存在，直接返回；如不存在走2；
• 访问mysql，如不存在，直接返回，如存在走3；
• 将mysql存在的key写回redis；

落地实现图

• 描述缓存场景，为了减轻落盘数据库（mysql）的访问压⼒，在server端与mysql之间加⼊⼀层缓冲数据层（⽤来存放热点数据）；
• 缓存穿透发⽣的场景是server端向数据库请求数据时，缓存数据库（redis）和落盘数据库（mysql）都不包含该数据，数据请求压⼒全部涌向落盘数据（mysql）
• 数据请求步骤：如上图 2 的描述；
• 发⽣原因：⿊客利⽤漏洞伪造数据攻击或者内部业务bug重复⼤量请求不存在的数据；
• 解决⽅法：如上图 3 的描述；
• 注：
  这种解决方案只适用于不要求数据严格一致性的情况，因为当后台线程在构建缓存的时候，其他的线程很有可能也在读取数据，这样就会访问到旧数据了。
  如果要严格保证数据一致的话，可以用互斥锁

互斥锁

原理：

• 互斥锁就是说，当key失效的时候，让一个线程读取数据并构建到缓存中，其他线程就先等待，直到缓存构建完后重新读取缓存即可。
• 采用互斥锁的方案也是有缺陷的，当缓存失效的时候，同一时间只有一个线程读数据库然后回写缓存，其他线程都处于阻塞状态。

缓存雪崩

缓存雪崩也是key失效后大量请求打到数据库的异常情况，不过，跟缓存击穿不同的是，缓存击穿因为指一个热点key失效导致的情况，而缓存雪崩是指缓存中大批量的数据同时过期，巨大的请求量直接落到db层，引起db压力过大甚至宕机，这也符合字面上的“雪崩”说法。

解决方案

• redis高可用
  这个思想的含义是，既然redis有可能挂掉，那我多增设几台redis，这样一台挂掉之后其他的还可以继续工作，其实就是搭建的集群。
• 限流降级
  这个解决方案的思想是，在缓存失效后，通过加锁或者队列来控制读数据库写缓存的线程数量。比如对某个key只允许一个线程查询数据和写缓存，其他线程等待。
• 数据预热
  数据加热的含义就是在正式部署之前，我先把可能的数据先预先访问一遍，这样部分可能大量访问的数据就会加载到缓存中。在即将发生大并发访问前手动触发加载缓存不同的key，设置不同的过期时间，让缓存失效的时间点尽量均匀。

set 和 map

c++标准库（STL）中的set和map结构都是采⽤红⿊树实现的，它增删改查的时间复杂度是O(log₂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)
{
    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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

另外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都具备强随机分布性；测试地址如下：
• 负载因⼦：数组存储元素的个数/数组⻓度；负载因⼦越⼩，冲突越⼩；负载因⼦越⼤，冲突越⼤；

hash冲突解决⽅案：

• 链表法
  引⼊链表来处理哈希冲突；也就是将冲突元素⽤链表链接起来；这也是常⽤的处理冲突的⽅式；但是可能出现⼀种极端情况，冲突元素⽐较多，该冲突链表过⻓，这个时候可以将这个链表转换为红⿊树；由原来链表时间复杂度 o(n) 转换为红⿊树时间复杂度 ；那么判断该链表过⻓的依据是多少？可以采⽤超过256（经验值）个节点的时候将链表结构转换为红⿊树结构；
• 开放寻址法
  将所有的元素都存放在哈希表的数组中，不使⽤额外的数据结构；⼀般使⽤线性探查的思路解
  决；
  *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；

同样的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§ / k))))
  p = pow(1 - exp(-k / (m / n)), k)
  m = ceil((n * log§) / 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；也可以在⽹站上选取合适的值：https://hur.st/bloomfilter
• 已知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 是位图的⼤⼩
}
1
2
3
4
5
6
7
8

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

布隆过滤器的优缺点

优点

• 节省空间：不需要存储数据本身，只需要存储数据对应hash比特位
• 时间复杂度低：基于哈希算法来查找元素，插入和查找的时间复杂度都为O(k)，k为哈希函数的个数

缺点

• 准确率有误：布隆过滤器判断存在，可能出现元素不在集合中；判断准确率取决于哈希函数的个数
• 不能删除元素：如果一个元素被删除，但是却不能从布隆过滤器中删除，这样进一步导致了不存在的元素也会显示1的情况。