分享一下关于Linux服务器开发中相关数据去重的做

1. 海量数据去重的Hash

1.1 背景

● 在使用word文档时，word如何判断某个单词是否拼写正确？

● 网络爬虫程序，怎么让它不去爬相同的url页面？

● 垃圾邮件（短信）过滤算法如何设计？

● 公安办案时，如何判断某嫌疑人是否在网逃名单中？

● 缓存穿透问题如何解决？

描述缓存场景，为了减轻落盘数据库（mysql）的访问压力，在server端与mysql之间加入一层缓冲数据层（用来存放热点数据）；

缓存穿透发生的场景是server端向数据库请求数据时，缓存数据库（redis）和落盘数据库（mysql）都不包含该数据，数据请求压力全部涌向落盘数据库（mysql）。

数据请求步骤：如上图2的描述；

发送原因：黑客利用漏洞伪造数据攻击或者内部业务bug重复大量请求不存在的数据；

解决方法：如上图3的描述；

1.2 需求

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

1.3 set和map

c++标准库（STL）中的set和map结构都是采用红黑树实现的，它增删改查的时间复杂度是o(log2n );

图结构示例：

对于严格平衡二叉搜索树（AVL），100w条数据组成的红黑树，只需要比较20次就能找到该值；对于10亿条数据只需要比较30次就能找到该数据；也就是查找次数跟树的高度是一致的；

对于红黑树来说平衡的黑节点高度，所以研究次数需要考虑树的高度差，最好情况某条树链路全是黑节点，假设此时高度为h1，最差情况某条树链路全是黑红节点间隔，那么此时树高度为2*h1；

在红黑树中每一个节点都存储key和val字段，key是用来做比较的字段；红黑树并没有要求key字段唯一，在set和map实现过程中限制了key字段唯一。我们来看nginx的红黑树实现：

//这个是截取nginx的红⿊树的实现，这段代码是insert操作中的⼀部分，执⾏完这个函数还
需要检测插⼊节点后是否平衡（主要是看他的⽗节点是否也是红⾊节点）
//调⽤ngx_rbtree_insert_value时，temp传的参数为红⿊树的根节点，node传的参数为
待插⼊的节点
voidngx_rbtree_insert_value(ngx_rbtree_node_t*temp,ngx_rbtree_node_t
*node,
{
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号节点应该在哪个位置？如果我们要实现插⼊存在
的节点变成修改操作，该怎么改上⾯的函数
voidngx_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;
}
/