在實際應用中，有很多需要将一個 Item 分布到多個 Bucket 中的場景：
将資料加載到記憶體中（Data --> Memory）
将檔案寫入到磁盤中（File --> Disk）
将任務配置設定到處理器（Task --> Processor）
将頁面加載到緩存中（Page --> Cache）
在這些場景中，我們的設計目标就是要将 Item 均勻地分布（Even Distribution）到不同的 Bucket 中，也就是負載均衡（Load Balancing）。
對于負載均衡中的負載，我們實際上會面對兩種情況：
持續性的負載（Permanent Loads）
臨時性的負載（Temporary Loads）
對于持續性的負載可以通過提高伺服器的能力或者通過添加強定數量的機器來分擔壓力。而臨時性的負載則是最難處理的，這需要系統的設計能夠抵禦突發的請求高峰。
對于處理臨時性的負載，通常我們會考慮使用緩存代理（Proxy Caching）技術，它使得對 Home 主機的通路模式由原先的每次浏覽均通路一次轉換到每個頁面僅通路一次。
在使用 Cache 機制時，會遇到多種情況：
如果某一個 Cache 持有了大量的 Items，則該 Cache 将被大量的客戶請求所淹沒。是以Cache 應該持有較少的 Items。
如果某一個 Item 會被大量的 Cache 所持有，則 Cache 對 Home 的請求将會成為壓力的來源。是以 Item 應該被放入到少量的 Cache 中。
如果請求方不知道正确的 Cache 位置，則需要 Server 端重定向，則重定向 Server 将成為瓶頸。是以請求方必須知道 Cache 的正确位置。
通常，使用 Hashing 技術可以提供簡單有效的負載均衡。Hashing 使得查找存放 Item 的 Bucket 的時間是 O(1)。但如果涉及到新增 Cache 或者移除 Cache 等操作，将會導緻所有 Item 重新 Hashing，已經存在的緩存内容将會失效。
例如，設 n 為 Cache 的數量，使用最簡單的 Linear Hashing 則有：
而當新增一個 Cache 時，Cache 的數量變為 n + 1：
而當移除一個 Cache 時，Cache 的數量變為 n - 1：
當所有的緩存都失效時，新的請求都會抵達 Home 主機，導緻 Home 主機崩潰。是以，在處理 Cache 的新增和移除時，較好的效果就是隻有少量的 Items 失效。
一緻性哈希（Consistent Hashing）将會從單視角和多視角來看待 Item 和 Bucket 的關系，這使得一緻性哈希會滿足一些特定的性質。
視角（View）的不一緻性（Inconsistent Views）将影響對 Cache 的選擇。從使用者視角（Client View）來看，每個 Client 隻了解一組不同的 Cache 集合。
如果 View 特别多，則同一個 Item 可以出現在每個 Cache 上，這樣 Home 将會被 Cache 的請求淹沒。是以，對于分散 Item 的設計目标是，不管有多少 View，Item 将僅存在于少數 Cache 上。
單視角性質（Single View Properties）
平衡（Balance）：所有的 Bucket 都可以擷取到大緻平均的 Item 數量。
平滑（Smooth）：當添加第 kth 個 Bucket 時，僅會影響所有 Items 中的 1/k 部分，并且僅影響 O(log n) 個伺服器。又稱為單調性（Monotonicity）。
多視角性質（Multiple View Properties）
假設有 n 個視角，每一個對應到所有 Buckets 的一個任意常量的部分。
負載（Load）：任意一個 Bucket 從所有 Views 中所獲得的 Items 的數量是 O(log n)，而無論有多少視角，來保證負載的平衡。
分散（Spread）：從所有 Views 來看，每一個 Item 将出現在 O(log n) 個 Buckets 中，而無論有多少視角，對于單一的 Item 都将出現在較少的 Buckets 中。
對所有的 Buckets 和 Items 應用相同的哈希函數 H，按照哈希值的順序把它們排列到一條線上，然後将距離 Bucket 最近的 Items 都放入該 Bucket 中。
另一種實作方式是把哈希值的最大值和最小值連接配接到一起，形成一個哈希環（Consistent Hashing Ring），按照順時針方向将 Items 放入 Bucket 中。
使用哈希函數 H 對 Item 進行計算後，需要找到合适的 Bucket 放入，此時可以選擇不同的算法，例如：
使用二分查找法為 O(log n)。
可以預先計算 Bucket 的哈希，使用額外的哈希表為 O(1)。
平衡（Balance）
如果哈希函數 H 可以将 Bucket 均勻地分布到線上，則每個 Bucket 都擁有線上均等的部分。
同樣哈希函數 H 将 Item 也均勻地分布到線上，這樣 Item 将等可能地分布到任意的 Bucket 中，所有 Bucket 都能獲得均等數量的 Items。
平滑（Smooth）
通常 Bucket 會捕獲離其最近的 Items。
當要添加第 kth 個 Bucket 時，使用同樣的哈希函數 H 将其添加到線上。
這樣，新的 Bucket 将捕獲離其最近的 Items。
我們發現，在這種條件下：
僅有 Items 總數的 1/k 部分會被影響到。
僅影響新的 Bucket 左右兩邊的 2 個 Buckets。
負載（Load）
一個 Bucket 将捕獲其附近的 Items，如果 Item 離它是最近的。但 Item 不可能總是離某一個 Bucket 是最近的，則任意一個 Bucket 都不可能捕獲特别多的 Items，是以負載是均衡的。
分散（Spread）
對于一個 Item，隻有真正離其最近的 Bucket 才會捕獲它。在每一個視角中，都隻會有一個離其最近的 Bucket，這樣對于單一的 Item 都将出現在較少的 Buckets 中。
如果使用的雜湊演算法 H 并不能保證絕對的平衡性，或者可使用的 Buckets 數量較少時，Items 可能無法被均勻地映射到 Buckets 上。為了解決這種問題，可以在哈希環中引入虛拟節點（Virtual Node）的政策。
虛拟節點（Virtual Node）是實際節點在哈希空間中的複制品（Replica）。一個實際節點可以對應若幹個虛拟節點，虛拟節點在哈希空間中使用同樣的哈希函數 H 計算哈希值并進行排列。
首先建構雜湊演算法的抽象。
向 ConsistentHash<T> 類中注入 IHashAlgorithm 的具體實作。
ConsistentHash<T> 類内實作哈希環，并可以指定虛拟節點的複制因子。
<a></a>
然後，我們就可以實作任意一個符合需求的雜湊演算法，比如如下的 MurmurHash2 算法。
這樣，我們就可以測試該 ConsistentHash<T> 的分布效果了。
上面代碼示例中向一緻性哈希環擷取給定的 10 個 Items 的順時針方向的節點，結果如下。
<a href="http://www.akamai.com/dl/technical_publications/ConsistenHashingandRandomTreesDistributedCachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf">Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web</a>
<a href="http://people.csail.mit.edu/karger/Talks/Hash/">Consistent Hashing: Load Balancing in a Changing World</a>
<a href="http://greg.brim.net/page/building_a_consistent_hashing_ring.html">Building a Consistent Hashing Ring</a>
<a href="http://www.datastax.com/documentation/cassandra/1.2/cassandra/architecture/architectureDataDistributeDistribute_c.html">How data is distributed across a cluster using virtual nodes in Cassandra</a>
<a href="http://www.datastax.com/dev/blog/virtual-nodes-in-cassandra-1-2">Virtual nodes in Cassandra 1.2</a>
<a href="http://blog.csdn.net/sparkliang/article/details/5279393">一緻性hash算法 - consistent hashing</a>
<a href="http://www.blogjava.net/hello-yun/archive/2012/10/10/389289.html">一緻性雜湊演算法與Java實作</a>
<a href="http://www.codeproject.com/Articles/56138/Consistent-hashing">Consistent hashing</a>
<a href="http://en.wikipedia.org/wiki/Consistent_hashing">Consistent hashing on Wikipedia</a>
<a href="http://www.cnblogs.com/xuxm2007/archive/2011/08/25/2153638.html">一緻性hash 之 [翻譯]Consistent Hash By Tom White</a>
<a href="http://my.huhoo.net/archives/2010/06/post_55.html">一緻性哈希簡單介紹</a>
<a href="http://blog.csdn.net/x15594/article/details/6270242">一緻性雜湊演算法（Consistent Hashing）</a>
<a href="http://www.jiacheo.org/blog/174">一緻性哈希</a>
<a href="http://blog.charlee.li/memcached-004/">memcached全面剖析--4. memcached的分布式算法</a>
<a href="http://www.tomkleinpeter.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/">Programmer’s Toolbox Part 3: Consistent Hashing</a>
<a href="http://docs.basho.com/riak/latest/theory/concepts/">Riak : a distributed key-value database</a>
<a href="http://doc.akka.io/docs/akka/snapshot/scala/routing.html">Akka's consistent hashing router</a>
<a href="http://docs.openstack.org/developer/swift/ring.html">Openstack Partitioned Consistent Hash Ring</a>
<a href="http://en.wikipedia.org/wiki/Linear_hashing">Linear hashing</a>
<a href="http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash">Fowler–Noll–Vo hash function</a>
<a href="http://en.wikipedia.org/wiki/Linear_congruential_generator">Linear Congruential Generator</a>
<a href="http://en.wikipedia.org/wiki/Lehmer_RNG">Lehmer Random Number Generator</a>
<a href="http://blog.huanghao.me/?p=14">一緻性hash算法簡介</a>
<a href="http://blog.yidooo.net/archives/consistent-hashing.html">一緻性Hash算法(Consistent Hashing)</a>
<a href="http://www.lanceyan.com/tech/arch/consistenthashing_and_solr.html">一緻性hash和solr千萬級資料分布式搜尋引擎中的應用</a>
<a href="http://blog.csdn.net/cywosp/article/details/23397179">每天進步一點點——五分鐘了解一緻性雜湊演算法(consistent hashing)</a>
<a href="http://ivoroshilin.com/2013/07/15/distributed-caching-under-consistent-hashing/">How automatic sharding works or consistent hashing under the hood</a>
<a href="http://code.google.com/p/consistent-hash/">Consistent hashing in C#</a>
<a href="http://surana.wordpress.com/2011/06/23/consistent-hashing-in-net/">Consistent Hashing in .NET</a>
<a href="http://landman-code.blogspot.com/2009/02/c-superfasthash-and-murmurhash2.html">C# SuperFastHash and MurmurHash2 implementations</a>
<a href="http://en.wikipedia.org/wiki/Chord_(peer-to-peer)">Chord (peer-to-peer)</a>
<a href="http://www.azillionmonkeys.com/qed/hash.html">Hash functions</a>
<a href="http://murmurhash.googlepages.com/statistics">MurmurHash2 Statistics</a>
本文轉自匠心十年部落格園部落格，原文連結：http://www.cnblogs.com/gaochundong/p/consistent_hashing.html，如需轉載請自行聯系原作者