分享一下關(guān)于Linux服務(wù)器開發(fā)中相關(guān)數(shù)據(jù)去重的做法

1. 海量數(shù)據(jù)去重的Hash

1.1 背景

● 在使用word文檔時(shí)，word如何判斷某個(gè)單詞是否拼寫正確？

● 網(wǎng)絡(luò)爬蟲程序，怎么讓它不去爬相同的url頁面？

● 垃圾郵件（短信）過濾算法如何設(shè)計(jì)？

● 公安辦案時(shí)，如何判斷某嫌疑人是否在網(wǎng)逃名單中？

● 緩存穿透問題如何解決？

描述緩存場(chǎng)景，為了減輕落盤數(shù)據(jù)庫（mysql）的訪問壓力，在server端與mysql之間加入一層緩沖數(shù)據(jù)層（用來存放熱點(diǎn)數(shù)據(jù)）；

緩存穿透發(fā)生的場(chǎng)景是server端向數(shù)據(jù)庫請(qǐng)求數(shù)據(jù)時(shí)，緩存數(shù)據(jù)庫（redis）和落盤數(shù)據(jù)庫（mysql）都不包含該數(shù)據(jù)，數(shù)據(jù)請(qǐng)求壓力全部涌向落盤數(shù)據(jù)庫（mysql）。

數(shù)據(jù)請(qǐng)求步驟：如上圖2的描述；

發(fā)送原因：黑客利用漏洞偽造數(shù)據(jù)攻擊或者內(nèi)部業(yè)務(wù)bug重復(fù)大量請(qǐng)求不存在的數(shù)據(jù)；

解決方法：如上圖3的描述；

1.2 需求

從海量數(shù)據(jù)中查詢某字符串是否存在

1.3 set和map

c++標(biāo)準(zhǔn)庫（STL）中的set和map結(jié)構(gòu)都是采用紅黑樹實(shí)現(xiàn)的，它增刪改查的時(shí)間復(fù)雜度是o(log2n );

圖結(jié)構(gòu)示例：

對(duì)于嚴(yán)格平衡二叉搜索樹（AVL），100w條數(shù)據(jù)組成的紅黑樹，只需要比較20次就能找到該值；對(duì)于10億條數(shù)據(jù)只需要比較30次就能找到該數(shù)據(jù)；也就是查找次數(shù)跟樹的高度是一致的；

對(duì)于紅黑樹來說平衡的黑節(jié)點(diǎn)高度，所以研究次數(shù)需要考慮樹的高度差，最好情況某條樹鏈路全是黑節(jié)點(diǎn)，假設(shè)此時(shí)高度為h1，最差情況某條樹鏈路全是黑紅節(jié)點(diǎn)間隔，那么此時(shí)樹高度為2*h1；

在紅黑樹中每一個(gè)節(jié)點(diǎn)都存儲(chǔ)key和val字段，key是用來做比較的字段；紅黑樹并沒有要求key字段唯一，在set和map實(shí)現(xiàn)過程中限制了key字段唯一。我們來看nginx的紅黑樹實(shí)現(xiàn)：

//這個(gè)是截取nginx的紅?樹的實(shí)現(xiàn)，這段代碼是insert操作中的?部分，執(zhí)?完這個(gè)函數(shù)還
需要檢測(cè)插?節(jié)點(diǎn)后是否平衡（主要是看他的?節(jié)點(diǎn)是否也是紅?節(jié)點(diǎn)）
//調(diào)?ngx_rbtree_insert_value時(shí)，temp傳的參數(shù)為紅?樹的根節(jié)點(diǎn)，node傳的參數(shù)為
待插?的節(jié)點(diǎn)
voidngx_rbtree_insert_value(ngx_rbtree_node_t*temp,ngx_rbtree_node_t
*node,
{
ngx_rbtree_node_t**p;
for(;;){
p=(node->keykey)?&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);
}
//不插?相同節(jié)點(diǎn)如果插?相同讓它變成修改操作此時(shí)紅?樹當(dāng)中就不會(huì)有相同的key了
定時(shí)器key時(shí)間戳
//如果我們插?key = 12，如上圖紅?樹，12號(hào)節(jié)點(diǎn)應(yīng)該在哪個(gè)位置？如果我們要實(shí)現(xiàn)插?存在
的節(jié)點(diǎn)變成修改操作，該怎么改上?的函數(shù)
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;
}
//}-------------add-------------
p=(node->keykey)?&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的關(guān)鍵區(qū)別是set不存儲(chǔ)val字段；

優(yōu)點(diǎn)：存儲(chǔ)效率高，訪問速度高效；

缺點(diǎn)：對(duì)于數(shù)據(jù)量大且查詢字符串比較長(zhǎng)且查詢字符串相似時(shí)將會(huì)是噩夢(mèng)；

1.4 unordered_map

c++標(biāo)準(zhǔn)庫（STL）中的unordered_map是采?hashtable實(shí)現(xiàn)的；

構(gòu)成：數(shù)組+hash函數(shù)；

它是將字符串通過hash函數(shù)?成?個(gè)整數(shù)再映射到數(shù)組當(dāng)中；它增刪改查的時(shí)間復(fù)雜度是o(1);

圖結(jié)構(gòu)示例：

hash函數(shù)的作?：避免插入的時(shí)候字符串的?較；hash函數(shù)計(jì)算出來的值通過對(duì)數(shù)組?度的取模

能隨機(jī)分布在數(shù)組當(dāng)中；

hash函數(shù)?般返回的是64位整數(shù)，將多個(gè)?數(shù)映射到?個(gè)?數(shù)組中，必然會(huì)產(chǎn)?沖突；

如何選取hash函數(shù)？

選取計(jì)算速度快；

哈希相似字符串能保持強(qiáng)隨機(jī)分布性（防碰撞）；

murmurhash1，murmurhash2，murmurhash3，siphash（redis6.0當(dāng)中使?，rust等?多數(shù)語?選?的hash算法來實(shí)現(xiàn)hashmap），cityhash都具備強(qiáng)隨機(jī)分布性；測(cè)試地址如下：https://github.com/aappleby/smhasher

負(fù)載因?：數(shù)組存儲(chǔ)元素的個(gè)數(shù)/數(shù)組?度；負(fù)載因?越?，沖突越?；負(fù)載因?越?，沖突越?；

hash沖突解決?案：○ 鏈表法引?鏈表來處理哈希沖突；也就是將沖突元素?鏈表鏈接起來；這也是常?的處理沖突的?式；但是可能出現(xiàn)?種極端情況，沖突元素?較多，該沖突鏈表過?，這個(gè)時(shí)候可以將這個(gè)鏈表轉(zhuǎn)換為紅?樹；由原來鏈表時(shí)間復(fù)雜度 o(n) 轉(zhuǎn)換為紅?樹時(shí)間復(fù)雜度o(log2n) ；那么判斷該鏈表過?的依據(jù)是多少？可以采?超過256（經(jīng)驗(yàn)值）個(gè)節(jié)點(diǎn)的時(shí)候?qū)㈡湵斫Y(jié)構(gòu)轉(zhuǎn)換為紅?樹結(jié)構(gòu)；○ 開放尋址法將所有的元素都存放在哈希表的數(shù)組中，不使?額外的數(shù)據(jù)結(jié)構(gòu)；?般使?線性探查的思路解決；

當(dāng)插?新元素的時(shí)，使?哈希函數(shù)在哈希表中定位元素位置；

檢查數(shù)組中該槽位索引是否存在元素。如果該槽位為空，則插?，否則3；

在 2 檢測(cè)的槽位索引上加?定步?接著檢查2；加?定步?分為以下?種：

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

i-1^2^ ,i+2^2^ ,i-3^2^ ,1+4^2^ ...這兩種都會(huì)導(dǎo)致同類hash聚集；也就是近似值它的hash值也近似，那么它的數(shù)組槽位也靠近，形成hash聚集；第一種同類聚集沖突在前，第二種只是將聚集沖突延后；另外還可以使用雙重哈希來解決上面出現(xiàn)hash聚集現(xiàn)象：

在.net HashTable類的hash函數(shù)Hk定義如下：Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize在此 (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))) 與 hashsize 互為素?cái)?shù)（兩數(shù)互為素?cái)?shù)表示兩者沒有共同的質(zhì)因?）；執(zhí)?了 hashsize 次探查后，哈希表中的每?個(gè)位置都有且只有?次被訪問到，也就是說，對(duì)于給定的 key，對(duì)哈希表中的同?位置不會(huì)同時(shí)使? Hi 和 Hj；

同樣的hashtable中節(jié)點(diǎn)存儲(chǔ)了key和val，hashtable并沒有要求key的??順序，我們同樣可以修改代碼讓插?存在的數(shù)據(jù)變成修改操作；

優(yōu)點(diǎn)：訪問速度更快；不需要進(jìn)行字符串比較；

缺點(diǎn)：需要引?策略避免沖突，存儲(chǔ)效率不?；空間換時(shí)間；

1.5 總結(jié)

紅?樹和hashtable都不能解決海量數(shù)據(jù)問題，它們都需要存儲(chǔ)具體字符串，如果數(shù)據(jù)量大，提供不了?百G的內(nèi)存；所以需要嘗試探尋不存儲(chǔ)key的?案，并且擁有hashtable的優(yōu)點(diǎn)（不需要?較字符串）；

2. 布隆過濾器

定義：布隆過濾器是?種概率型數(shù)據(jù)結(jié)構(gòu)，它的特點(diǎn)是?效的插入和查詢，能明確告知某個(gè)字符串?定不存在或者可能存在；

布隆過濾器相?傳統(tǒng)的查詢結(jié)構(gòu)（例如：hash，set，map等數(shù)據(jù)結(jié)構(gòu)）更加高效，占?空間更小；但是其缺點(diǎn)是它返回的結(jié)果是概率性的，也就是說結(jié)果存在誤差的，雖然這個(gè)誤差是可控的；同時(shí)它不支持刪除操作；

組成：位圖（bit數(shù)組）+ n個(gè)hash函數(shù)

原理：當(dāng)?個(gè)元素加?位圖時(shí)，通過k個(gè)hash函數(shù)將這個(gè)元素映射到位圖的k個(gè)點(diǎn)，并把它們置為1；當(dāng)檢索時(shí)，再通過k個(gè)hash函數(shù)運(yùn)算檢測(cè)位圖的k個(gè)點(diǎn)是否都為1；如果有不為1的點(diǎn)，那么認(rèn)為不存在；如果全部為1，則可能存在（存在誤差）；

在位圖中每個(gè)槽位只有兩種狀態(tài)（0或者1），?個(gè)槽位被設(shè)置為1狀態(tài)，但不明確它被設(shè)置了多少 次；也就是不知道被多少個(gè)str1哈希映射以及是被哪個(gè)hash函數(shù)映射過來的；所以不?持刪除操作；

在實(shí)際應(yīng)?過程中，布隆過濾器該如何使?？要選擇多少個(gè)hash函數(shù)，要分配多少空間的位圖，存儲(chǔ)多少元素？另外如何控制假陽率（布隆過濾器能明確?定不存在，不能明確?定存在，那么存在的判斷是有誤差的，假陽率就是錯(cuò)誤判斷存在的概率）？

n--布隆過濾器中元素的個(gè)數(shù)，如上圖只有str1和str2兩個(gè)元素那么n=2
p--假陽率，在0-1之間0.000000
m--位圖所占空間
k--hash函數(shù)的個(gè)數(shù)
公式如下：
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));

假定我們選取這四個(gè)值為：n = 4000p = 0.000000001m = 172532k = 30

四個(gè)值的關(guān)系：

在實(shí)際應(yīng)?中，我們確定n和p，通過上?的計(jì)算算出m和k；也可以在?站上選取合適的值：https://hur.st/bloomfilter

已知k，如何選擇k個(gè)hash函數(shù)？

//采??個(gè)hash函數(shù)，給hash傳不同的種?偏移值
//#defineMIX_UINT64(v)((uint32_t)((v>>32)^(v)))
uint64_thash1=MurmurHash2_x64(key,len,Seed);
uint64_thash2=MurmurHash2_x64(key,len,MIX_UINT64(hash1));
for(i=0;i

	

	



	審核編輯：劉清