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

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

1.1 背景

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

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

● 垃圾郵件（短信）過濾算法如何設計？

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

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

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

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

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

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

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

1.2 需求

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

1.3 set和map

c++標準庫（STL）中的set和map結構都是采用紅黑樹實現(xiàn)的，它增刪改查的時間復雜度是o(log2n );

圖結構示例：

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

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

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

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

優(yōu)點：存儲效率高，訪問速度高效；

缺點：對于數(shù)據(jù)量大且查詢字符串比較長且查詢字符串相似時將會是噩夢；

1.4 unordered_map

c++標準庫（STL）中的unordered_map是采?hashtable實現(xiàn)的；

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

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

圖結構示例：

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

能隨機分布在數(shù)組當中；

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

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

選取計算速度快；

哈希相似字符串能保持強隨機分布性（防碰撞）；

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

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

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

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

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

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

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

i-1^2^ ,i+2^2^ ,i-3^2^ ,1+4^2^ ...這兩種都會導致同類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 互為素數(shù)（兩數(shù)互為素數(shù)表示兩者沒有共同的質因?）；執(zhí)?了 hashsize 次探查后，哈希表中的每?個位置都有且只有?次被訪問到，也就是說，對于給定的 key，對哈希表中的同?位置不會同時使? Hi 和 Hj；

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

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

缺點：需要引?策略避免沖突，存儲效率不?；空間換時間；

1.5 總結

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

2. 布隆過濾器

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

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

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

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

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

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

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

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

四個值的關系：

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

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

//采??個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

	

	



	審核編輯：劉清