問題分析

　　經由過程以上對話，列位是否可以猜到所有緩存穿透的緣故緣由呢？回覆之前我們先來看一下緩存計策的詳細代碼：

　　緩存辦事器IP=hash(key)%辦事器數目

　　這裏還要多說一句，key的取值可以按照詳細業務詳細設計。比如，我想要做負載平衡，key可覺得挪用方的辦事器IP；獲取用戶信息，key可覺得用戶ID......等等。

　　在辦事器數目不變的情形下，以上設計沒有問題。可是要曉得，軌範員的實際世界是淒涼的，獨一不變的就是業務不息在變。我本無法，只能靠手藝來改變這種狀態。

　　假設我們如今辦事器的數目爲10，當我們哀求key爲6的時辰，成效是4，如今我們添加一臺辦事器，辦事器數目變爲11，當再次哀求key爲6的辦事器的時辰，成效爲5。不難創造，不僅是key爲6的哀求，幾乎大局部的哀求成效都產生了變化，這就是我們要處理的問題，這也是我們設計分佈式緩存等近似場景時辰首要必要注意的問題。

　　我們終極的設計方針是，在辦事器數目變換的情形下：

　　儘量進步緩存的射中率（轉移的數據最少）；

　　緩存數據儘量均勻分配。

　　處理方案

　　經由過程以上的分析我們明白了，形成大量緩存失效的根柢緣故緣由是公式分母的變化，若是我們把分母保持不變，根基上可以減少大量數據被挪動

　　若是基於公式：緩存辦事器IP=hash(key)%辦事器數目，我們保持分母不變，根基上可以改善現有情形。我們選擇緩存辦事器的計策會變爲：

　　緩存辦事器IP=hash(key)%N （N爲常數）

　　N的數值選擇，可以按照詳細業務選擇一個滿足情形的值。比如：我們可以必定將來辦事器數目不會跨越100臺，那N完全可以設定爲100。那帶來的問題呢？

　　今朝的情形可以認爲辦事器編號是連續的，任何一個哀求都市射中一個辦事器，仍是以上作爲例子，我們辦事器如今無論是10仍是添加到11，key爲6的哀求老是能獲取到一臺辦事器信息，可是如今我們的計策公式分母爲100，若是辦事器數目爲11，key爲20的哀求成效爲20，編號爲20的辦事器是不存在的。

　　以上就是簡單哈希計策帶來的問題（簡單取餘的哈希計策可以籠統爲連續的數組元素，按照下標來訪謁的場景）。

　　爲體味決以上問題，業界早已有處理方案，那就是同等性哈希。

　　同等性哈希算法在1997年由麻省理工學院的Karger等人在處理分佈式Cache中提出的，設計方針是爲體味決因特網中的熱點(Hot spot)問題，初志和CARP非常近似。同等性哈希修改了CARP使用的簡單哈希算法帶來的問題，使得DHT可以在P2P情形中真正獲得應用。

　　同等性哈希詳細的特點，這裏不在詳細引見。至於處理問題的思緒這裏還要強調一下：

　　首先求出辦事器（節點）的哈希值，並將其設置裝備安排到環上，此環有2^32個節點。

　　接納同樣的編制求出存儲數據的鍵的哈希值，並映射到不異的圓上。

　　然後從數據映射到的位置起頭順時針查找，將數據保留到找到的第一個辦事器上。若是跨越2^32仍然找不各辦事器，就會保留到第一臺辦事器上。

　　當添加新的辦事器的時辰會產生什麼情形呢？

　　經由過程上圖我們可以創造產生變化的只需如黃色局部所示，刪除辦事器情形近似，同等性哈希恰是處理我們今朝問題的一種方案。

　　處理方案萬萬種，能處理問題即爲好。

　　優化方案

　　到今朝爲止方案都看似完滿，但實際是暴虐的。以上方案雖好，但還存在瑕疵。假設我們有3臺辦事器，抱負狀態下辦事器在哈希環上的分配如下圖：

　　可是實際往往是如許：

　　這就是所謂的哈希環偏斜。分佈不均勻在某些場景下會依次壓垮辦事器，實際消費情形必定要注意這個問題。爲體味決這個問題，假造節點應運而生。

　　如上圖，哈希環上不再是實際的辦事器信息，而是辦事器信息的映射信息，比如：ServerA-1,ServerA-2 都映射各辦事器A，在環上是辦事器A的一個覆成品。這種處理編制是把持數目來到達均勻分佈的目的，隨之必要的內存可能會略微大一點，算是空間換取設計的一種方案。

　　反思

　　1. 既然是哈希就會有哈希辯說，那多個辦事器節點的哈希值不異該怎樣辦呢？我們可以接納散列表尋址的方案：從當前位置順時針起頭查找空位置，直到找到一個空位置。若是未找到，那麼你的哈希環是不是該擴容了，或者你的分母參數是不是太小了呢？

　　2. 在實際的業務中，添加辦事器或者減少辦事器的把持要比查找辦事器少的多，所以我們存儲哈希環的數據構造的查找速度必定要快，詳細說來本質是：自哈希環的某個值起，能快速查找第一個不爲空的元素。

　　3. 網上良多引見假造哈希環節點個數爲2^32(2的32次方)，陳腐看法。莫非除了這個個數就不成以嗎？在我看來，這個數目完全必要這麼大，只需適宜我們的業務需求，滿足業務數據即可。

　　4. 同等性哈希用到的哈希函數，不止要保證鬥勁高的機能，還要保持哈希值的儘量均勻分佈，這也是一個工業級哈希函數的要求，一下代碼實例的哈希函數其實不是最佳的，有樂趣的同窗可以優化一下。

　　5. 有些說話自帶的GetHashCode編制應用於同等性哈希是有問題的，例如C#。軌範重啓之後統一個字符串的哈希值是變換的，所有必要一個加倍不變的字符串轉int的哈希算法。

　　同等性哈希處理的素詰責題是：不異的key經由過程不異的哈希函數，能精確路由到不異的方針——像我們日常平常用的數據庫分表計策、分庫計策、負載平衡、數據分片等都可以用同等性哈希來處理。