❶ php的memcached分布式hash演算法,如何解決分布不均crc32這個演算法沒辦法把key值均勻的分布出去
memcached的總結和分布式一致性hash
當前很多大型的web系統為了減輕資料庫伺服器負載，會採用memchached作為緩存系統以提高響應速度。
目錄： （http://hounwang.com/lesson.html）
memchached簡介
hash
取模
一致性hash
虛擬節點
源碼解析
參考資料
1. memchached簡介
memcached是一個開源的高性能分布式內存對象緩存系統。
其實思想還是比較簡單的，實現包括server端（memcached開源項目一般只單指server端）和client端兩部分:
server端本質是一個in-memory key-value store，通過在內存中維護一個大的hashmap用來存儲小塊的任意數據，對外通過統一的簡單介面（memcached protocol）來提供操作。
client端是一個library，負責處理memcached protocol的網路通信細節，與memcached server通信，針對各種語言的不同實現分裝了易用的API實現了與不同語言平台的集成。
web系統則通過client庫來使用memcached進行對象緩存。
2. hash
memcached的分布式主要體現在client端，對於server端，僅僅是部署多個memcached server組成集群，每個server獨自維護自己的數據（互相之間沒有任何通信），通過daemon監聽埠等待client端的請求。
而在client端，通過一致的hash演算法，將要存儲的數據分布到某個特定的server上進行存儲，後續讀取查詢使用同樣的hash演算法即可定位。
client端可以採用各種hash演算法來定位server：
取模
最簡單的hash演算法
targetServer = serverList[hash(key) % serverList.size]
直接用key的hash值（計算key的hash值的方法可以自由選擇，比如演算法CRC32、MD5,甚至本地hash系統，如java的hashcode）模上server總數來定位目標server。這種演算法不僅簡單，而且具有不錯的隨機分布特性。
但是問題也很明顯，server總數不能輕易變化。因為如果增加/減少memcached server的數量，對原先存儲的所有key的後續查詢都將定位到別的server上，導致所有的cache都不能被命中而失效。
一致性hash
為了解決這個問題，需要採用一致性hash演算法（consistent hash）
相對於取模的演算法，一致性hash演算法除了計算key的hash值外，還會計算每個server對應的hash值，然後將這些hash值映射到一個有限的值域上（比如0~2^32）。通過尋找hash值大於hash(key)的最小server作為存儲該key數據的目標server。如果找不到，則直接把具有最小hash值的server作為目標server。
為了方便理解，可以把這個有限值域理解成一個環，值順時針遞增。
如上圖所示，集群中一共有5個memcached server，已通過server的hash值分布到環中。
如果現在有一個寫入cache的請求，首先計算x=hash(key)，映射到環中，然後從x順時針查找，把找到的第一個server作為目標server來存儲cache，如果超過了2^32仍然找不到，則命中第一個server。比如x的值介於A~B之間，那麼命中的server節點應該是B節點
可以看到，通過這種演算法，對於同一個key，存儲和後續的查詢都會定位到同一個memcached server上。
那麼它是怎麼解決增/刪server導致的cache不能命中的問題呢？
假設，現在增加一個server F，如下圖
此時，cache不能命中的問題仍然存在，但是只存在於B~F之間的位置（由C變成了F），其他位置（包括F~C）的cache的命中不受影響（刪除server的情況類似）。盡管仍然有cache不能命中的存在，但是相對於取模的方式已經大幅減少了不能命中的cache數量。
虛擬節點
但是，這種演算法相對於取模方式也有一個缺陷：當server數量很少時，很可能他們在環中的分布不是特別均勻，進而導致cache不能均勻分布到所有的server上。
如圖，一共有3台server – 1，2，4。命中4的幾率遠遠高於1和2。
為解決這個問題，需要使用虛擬節點的思想：為每個物理節點（server）在環上分配100～200個點，這樣環上的節點較多，就能抑制分布不均勻。
當為cache定位目標server時，如果定位到虛擬節點上，就表示cache真正的存儲位置是在該虛擬節點代表的實際物理server上。
另外，如果每個實際server的負載能力不同，可以賦予不同的權重，根據權重分配不同數量的虛擬節點。
// 採用有序map來模擬環
this.consistentBuckets = new TreeMap();
MessageDigest md5 = MD5.get();//用MD5來計算key和server的hash值
// 計算總權重
if ( this.totalWeight for ( int i = 0; i < this.weights.length; i++ )
this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];
} else if ( this.weights == null ) {
this.totalWeight = this.servers.length;
}
// 為每個server分配虛擬節點
for ( int i = 0; i < servers.length; i++ ) {
// 計算當前server的權重
int thisWeight = 1;
if ( this.weights != null && this.weights[i] != null )
thisWeight = this.weights[i];
// factor用來控制每個server分配的虛擬節點數量
// 權重都相同時，factor=40
// 權重不同時，factor=40*server總數*該server權重所佔的百分比
// 總的來說，權重越大，factor越大，可以分配越多的虛擬節點
double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );
for ( long j = 0; j < factor; j++ ) {
// 每個server有factor個hash值
// 使用server的域名或IP加上編號來計算hash值
// 比如server - "172.45.155.25:11111"就有factor個數據用來生成hash值：
// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor
byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );
// 每個hash值生成4個虛擬節點
for ( int h = 0 ; h < 4; h++ ) {
Long k =
((long)(d[3+h*4]&0xFF) << 24)
| ((long)(d[2+h*4]&0xFF) << 16)
| ((long)(d[1+h*4]&0xFF) << 8 )
| ((long)(d[0+h*4]&0xFF));
// 在環上保存節點
consistentBuckets.put( k, servers[i] );
}
}
// 每個server一共分配4*factor個虛擬節點
}
// 採用有序map來模擬環
this.consistentBuckets = new TreeMap();
MessageDigest md5 = MD5.get();//用MD5來計算key和server的hash值
// 計算總權重
if ( this.totalWeight for ( int i = 0; i < this.weights.length; i++ )
this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];
} else if ( this.weights == null ) {
this.totalWeight = this.servers.length;
}
// 為每個server分配虛擬節點
for ( int i = 0; i < servers.length; i++ ) {
// 計算當前server的權重
int thisWeight = 1;
if ( this.weights != null && this.weights[i] != null )
thisWeight = this.weights[i];
// factor用來控制每個server分配的虛擬節點數量
// 權重都相同時，factor=40
// 權重不同時，factor=40*server總數*該server權重所佔的百分比
// 總的來說，權重越大，factor越大，可以分配越多的虛擬節點
double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );
for ( long j = 0; j < factor; j++ ) {
// 每個server有factor個hash值
// 使用server的域名或IP加上編號來計算hash值
// 比如server - "172.45.155.25:11111"就有factor個數據用來生成hash值：
// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor
byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );
// 每個hash值生成4個虛擬節點
for ( int h = 0 ; h < 4; h++ ) {
Long k =
((long)(d[3+h*4]&0xFF) << 24)
| ((long)(d[2+h*4]&0xFF) << 16)
| ((long)(d[1+h*4]&0xFF) << 8 )
| ((long)(d[0+h*4]&0xFF));
// 在環上保存節點
consistentBuckets.put( k, servers[i] );
}
}
// 每個server一共分配4*factor個虛擬節點
}
// 用MD5來計算key的hash值
MessageDigest md5 = MD5.get();
md5.reset();
md5.update( key.getBytes() );
byte[] bKey = md5.digest();
// 取MD5值的低32位作為key的hash值
long hv = ((long)(bKey[3]&0xFF) << 24) | ((long)(bKey[2]&0xFF) << 16) | ((long)(bKey[1]&0xFF) << 8 ) | (long)(bKey[0]&0xFF);
// hv的tailMap的第一個虛擬節點對應的即是目標server
SortedMap tmap = this.consistentBuckets.tailMap( hv );
return ( tmap.isEmpty() ) ? this.consistentBuckets.firstKey() : tmap.firstKey();
更多問題到問題求助專區（http://bbs.hounwang.com/）
❷ 文本相似度之Sim_hash演算法
本文記錄的目的是方便自己學習和復習，有誤之處請諒解，歡迎指出。
最近項目有用到Sim_hash，做個簡單記錄。
Sim_hash是Google用來處理大量文本去重的演算法，屬於 局部敏感哈希（Locality Sensitive Hashing，LSH） ，LSH哈希能夠使兩篇只有小部分改動的文章編碼後哈希值具有相似性，既可用於去重，也可用於計算相似度。對於只有小部分改動的兩篇文章，在計算他們之間的相似度時，如果採用md5，兩篇文章的md5編碼值差異會非常大。但使用局部敏感哈希可以使相似的文章哈希編碼後聚集在一起，刪除符合閾值條件的文章，達到去重的效果。
一、演算法流程
1）分詞：對文本進行去停用詞、分詞，提取n個關鍵詞和關鍵詞的tf-idf權重來表徵文章。如下圖分詞及權重。
2）關鍵詞哈希編碼：每個關鍵詞通過hash函數生成固定位數二進制哈希。
3）權重編碼：二進制編碼中0調整為-1變為權重向量，與權重相乘。
4）權重編碼疊加：將所有權重編碼縱向求和，得到最終的文章權重。
5）二值化：按正數為1負數為0的規則將文章權重二值化。
6）漢明距離相似度：排除漢明距離小於閾值的文章，一般設置為3。漢明距離計算速度快，思路簡單，原理是計算兩個二值化編碼相同位置處的不同值的個數。
二、Sim_hash整體流程
需求： 來了一個相似文章推薦需求，需要推薦出與文章內容相似的數據，但又不能完全相似。利用目前庫中已有的POI標簽和POI權重數據，結合simhash演算法，計算出每個文章poi_sim_hash，計算距離
數據： 線上拉取10W文章數據
測試結果： 下圖為隨機抽樣的測試結果（第一條為查詢數據），基本 符合預期效果 。前期還可以使用 類目和發布時間 進行前置過濾，減少數據量。
❸ 百度主流相關性演算法有哪些你知道多少
一般是谷歌能走到哪一步，網路也會跟到哪一步。除了PR值的演算法，是基於李彥宏。 這里介紹的主流演算法是—— Simhash演算法 1、主流演算法——Simhash演算法 我們一般判斷文本與文本之間的相關性是很容易的。你演算法的效率，直接決定了你的使用性。 通過此演算法能夠了解網頁間的相關性對比和搜索引擎達到去重的效果。網路和谷歌都有基於此原理。這個大家可以網路一下具體解釋。 2、相關性演算法的對比程度 我們了解演算法，是為了獲得更多的權重。在應用上，我們主要在以下幾個方面。 第一：外鏈的有效性方面。比如，你是旅遊類站點，那麼你做的友鏈都是旅遊類。那麼有些企業站很難找到相關的。那麼可以找，本地的，同行業的。但是我們心裡清楚，相關性的總比不相關性的好。那麼找本地的、同行業的大家都沒有底，但是不管你是找同行業的還是本地的，其實沒有那麼大的影響。 第二，站內相關性。比如說內鏈，現在內鏈的列表都是隨機推薦的。隨機推薦的效果是最差的。隨機推薦的越多，質量就最低，也是網路這次演算法調整的內容之一，那麼那些網站是最多的？醫療站，幾乎是所有行業裡面最普遍的。隨機生成 這里，老師將會讓你徹底改變關於相關性的看法。一個是外鏈相關性方面，一個是內鏈相關性方面，一定要看仔細了。 3.外鏈方面的相關性方面 分兩個層次的應用。這里講兩個基礎的兩個概念，一個是谷歌PR值演算法和網路的超文本鏈接演算法，是怎麼來識別權威性的？我們在一個行業為什麼要進行權威性的識別？在任何團隊裡面都有自己的領袖，這個是一個自然現象。因為權威性的指導，能夠給信息帶來信用度。對信用的評級是有一定的層級的。因為搜索引擎是一個信息平台，那麼對信息就必須有一個權威性指導。所以搜索引擎就必須有兩個識別，一個是樞紐，一個是權威性。那麼什麼是樞紐？中心的意思。 權威性的建立，是有一些樞紐組成的。一個權威性站點，是接收了很多樞紐的指向的。樞紐是鏈接，但是鏈接不一定是樞紐。這個就是ICO標簽。如果你想成為權威性網站，那麼你要做的應該是不同行業的鏈接。如果你做的都是同行業的鏈接，你就成為不了權威性網站。 權威是指整個互聯網的權威，還是某個行業？權威可不可以跨行？旅遊行業的權威網站可不可以對酒店行業網站投票？我們所說的 高權重站點，針對的是行業，不是跨行業。 我們聽說一個高權重網站，我們都去發外鏈，以為可以帶來大量權重，其實錯了。他只能給他的那個行業的網站帶來權重。 樞紐鏈接是對不同的權威網站進行指向的。這個鏈接的導出頁面（樞紐），是對不同行業進行導向的。 如果你的網站都是同行業的，那麼你不是樞紐，也不可能稱為權威。做外鏈，請找樞紐 了解搜索引擎的相關性演算法了嗎？
❹ simhash如何進行文本查重
有1億個不重復的64位的01字元串，任意給出一個64位的01字元串f，如何快速從中找出與f漢明距離小於3的字元串？
大規模網頁的近似查重
主要翻譯自WWW07的Detecting Near-Duplicates for Web Crawling
WWW上存在大量內容近似相同的網頁，對搜索引擎而言，去除近似相同的網頁可以提高檢索效率、降低存儲開銷。
當爬蟲在抓取網頁時必須很快能在海量文本集中快速找出是否有重復的網頁。
論文主要2個貢獻：
1. 展示了simhash可以用以海量文本查重
2. 提出了一個在實際應用中可行的演算法。
兩篇文本相似度普遍的定義是比較向量化之後兩個詞袋中詞的交集程度，有cosine,jaccard等等
如果直接使用這種計算方式，時間空間復雜度都太高，因此有了simhash這種降維技術，
但是如何從傳統的向量相似度能用simhash來近似，論文沒提，應該是有很長一段推導要走的。
Simhash演算法
一篇文本提取出內容以後，經過基本的預處理，比如去除停詞，詞根還原，甚至chunking，最後可以得到一個向量。
對每一個term進行hash演算法轉換，得到長度f位的hash碼，每一位上1-0值進行正負權值轉換，例如f1位是1時，權值設為 +weight, fk位為0時，權值設為-weight。
講文本中所有的term轉換出的weight向量按f對應位累加最後得到一個f位的權值數組，位為正的置1，位為負的置0，那麼文本就轉變成一個f位的新1-0數組，也就是一個新的hash碼。
Simhash具有兩個「沖突的性質」：
1. 它是一個hash方法
2. 相似的文本具有相似的hash值，如果兩個文本的simhash越接近，也就是漢明距離越小，文本就越相似。
因此海量文本中查重的任務轉換位如何在海量simhash中快速確定是否存在漢明距離小的指紋。
也就是：在n個f-bit的指紋中，查詢漢明距離小於k的指紋。
在文章的實驗中（見最後），simhash採用64位的哈希函數。在80億網頁規模下漢明距離=3剛好合適。
因此任務的f-bit=64 , k=3 , n= 8*10^11
任務清晰，首先看一下兩種很直觀的方法：
1. 對輸入指紋，枚舉出所有漢明距離小於3的simhash指紋，對每個指紋在80億排序指紋中查詢。
（這種方法需要進行C（64，3）=41664次的simhash指紋，再為每個進行一次查詢）
2. 輸入指紋不變，對應集合相應位置變。也就是集合上任意3位組合的位置進行變化，實際上就是提前准備41664個排序可能，需要龐大的空間。輸入在這群集合並行去搜....
提出的方法介於兩者之間，合理的空間和時間的折中。
• 假設我們有一個已經排序的容量為2d，f-bit指紋集。看每個指紋的高d位。該高低位具有以下性質：盡管有很多的2d位組合存在，但高d位中有隻有少量重復的。
• 現在找一個接近於d的數字d』，由於整個表是排好序的，所以一趟搜索就能找出高d』位與目標指紋F相同的指紋集合f』。因為d』和d很接近，所以找出的集合f』也不會很大。
• 最後在集合f』中查找和F之間海明距離為k的指紋也就很快了。
• 總的思想：先要把檢索的集合縮小，然後在小集合中檢索f-d』位的海明距離
要是一時半會看不懂，那就從新回顧一下那兩種極端的辦法：
方法2，前61位上精確匹配，後面就不需要比較了
方法1，前0位上精確匹配，那就要在後面，也就是所有，上比較
那麼折中的想法是 前d- bits相同，留下3bit在(64-d)bit小范圍搜索，可行否?
d-bits的表示範圍有2^d，總量N個指紋，平均 每個表示後面只有N/(2^d)個
快速定位到前綴是d的位置以後，直接比較N/(2^k)個指紋。
如此只能保證前d位精確的那部分N/(2^d)指紋沒有遺漏漢明距離>3的
因此要保證64bits上所有部分都安全，全部才沒有遺漏。
方法2其實就是把所有的d=61 部分(也就是64選61)都包含了。
按照例子，80億網頁有2^34個，那麼理論上34位就能表示完80億不重復的指紋。
我們假設最前的34位的表示完了80億指紋，假設指紋在前30位是一樣的，那麼後面4位還可以表示24個，只需要逐一比較這16個指紋是否於待測指紋漢明距離小於3。
假設：對任意34位中的30位都可以這么做。
因此在一次完整的查找中，限定前q位精確匹配（假設這些指紋已經是q位有序的，可以採用二分查找，如果指紋量非常大，且分布均勻，甚至可以採用內插搜索），之後的2d-q個指紋剩下64-q位需要比較漢明距離小於3。
於是問題就轉變為如何切割64位的q。
將64位平分成若干份，例如4份ABCD，每份16位。
假設這些指紋已經按A部分排序好了，我們先按A的16位精確匹配到一個區間，這個區間的後BCD位檢查漢明距離是否小於3。
同樣的假設，其次我們按B的16位精確匹配到另一個區間，這個區間的所有指紋需要在ACD位上比較漢明距離是否小於3。
同理還有C和D
所以這里我們需要將全部的指紋T復制4份，T1 T2 T3 T4， T1按A排序，T2按B排序… 4份可以並行進行查詢，最後把結果合並。這樣即使最壞的情況：3個位分別落在其中3個區域ABC,ACD,BCD,ABD…都不會被漏掉。
只精確匹配16位，還需要逐一比較的指紋量依然龐大，可能達到2d-16個，我們也可以精確匹配更多的。
例如：將64位平分成4份ABCD，每份16位，在BCD的48位上，我們再分成4份，WXZY，每份12位，漢明距離的3位可以散落在任意三塊，那麼A與WXZY任意一份合起來做精確的28位…剩下3份用來檢查漢明距離。同理B，C，D也可以這樣，那麼T需要復制16次，ABCD與WXYZ的組合做精確匹配，每次精確匹配後還需要逐一比較的個數降低到2d-28個。不同的組合方式也就是時間和空間上的權衡。
最壞情況是其中3份可能有1位漢明距離差異為1。
演算法的描述如下：
1）先復制原表T為Tt份：T1,T2,….Tt
2）每個Ti都關聯一個pi和一個πi，其中pi是一個整數,πi是一個置換函數，負責把pi個bit位換到高位上。
3）應用置換函數πi到相應的Ti表上，然後對Ti進行排序
4）然後對每一個Ti和要匹配的指紋F、海明距離k做如下運算：
a) 然後使用F』的高pi位檢索，找出Ti中高pi位相同的集合
b) 在檢索出的集合中比較f-pi位，找出海明距離小於等於k的指紋
5）最後合並所有Ti中檢索出的結果
由於文本已經壓縮成8個位元組了，因此其實Simhash近似查重精度並不高：