⑴ 分布式系統常用的一致性演算法有哪些
在做伺服器負載均衡時候可供選擇的負載均衡的演算法有很多，包括： 輪循演算法（Round Robin）、哈希演算法（HASH）、最少連接演算法（Least Connection）、響應速度演算法（Response Time）、加權法（Weighted ）等。其中哈希演算法是最為常用的演算法. 典型的應用場景是： 有N台伺服器提供緩存服務，需要對伺服器進行負載均衡，將請求平均分發到每台伺服器上，每台機器負責1/N的服務。 常用的演算法是對hash結果取余數 (hash() mod N)：對機器編號從0到N-1，按照自定義的hash()演算法，對每個請求的hash()值按N取模，得到余數i，然後將請求分發到編號為i的機器。但這樣的演算法方法存在致命問題，如果某一台機器宕機，那麼應該落在該機器的請求就無法得到正確的處理，這時需要將當掉的伺服器從演算法從去除，此時候會有(N-1)/N的伺服器的緩存數據需要重新進行計算；如果新增一台機器，會有N /(N+1)的伺服器的緩存數據需要進行重新計算。對於系統而言，這通常是不可接受的顛簸（因為這意味著大量緩存的失效或者數據需要轉移）。那麼，如何設計一個負載均衡策略，使得受到影響的請求盡可能的少呢？ 在Memcached、Key-Value Store、Bittorrent DHT、LVS中都採用了Consistent Hashing演算法，可以說Consistent Hashing 是分布式系統負載均衡的首選演算法。 1、Consistent Hashing演算法描述 下面以Memcached中的Consisten Hashing演算法為例說明。 由於hash演算法結果一般為unsigned int型，因此對於hash函數的結果應該均勻分布在[0,232-1]間，如果我們把一個圓環用232 個點來進行均勻切割，首先按照hash(key)函數算出伺服器（節點）的哈希值， 並將其分布到0～232的圓上。 用同樣的hash(key)函數求出需要存儲數據的鍵的哈希值，並映射到圓上。然後從數據映射到的位置開始順時針查找，將數據保存到找到的第一個伺服器（節點）上。 Consistent Hashing原理示意圖 新增一個節點的時候，只有在圓環上新增節點逆時針方向的第一個節點的數據會受到影響。刪除一個節點的時候，只有在圓環上原來刪除節點順時針方向的第一個節點的數據會受到影響，因此通過Consistent Hashing很好地解決了負載均衡中由於新增節點、刪除節點引起的hash值顛簸問題。 Consistent Hashing添加伺服器示意圖 虛擬節點（virtual nodes）：之所以要引進虛擬節點是因為在伺服器（節點）數較少的情況下（例如只有3台伺服器），通過hash(key)算出節點的哈希值在圓環上並不是均勻分布的（稀疏的），仍然會出現各節點負載不均衡的問題。虛擬節點可以認為是實際節點的復製品（replicas），本質上與實際節點實際上是一樣的（key並不相同）。引入虛擬節點後，通過將每個實際的伺服器（節點）數按照一定的比例(例如200倍)擴大後並計算其hash(key)值以均勻分布到圓環上。在進行負載均衡時候，落到虛擬節點的哈希值實際就落到了實際的節點上。由於所有的實際節點是按照相同的比例復製成虛擬節點的，因此解決了節點數較少的情況下哈希值在圓環上均勻分布的問題。 虛擬節點對Consistent Hashing結果的影響 從上圖可以看出，在節點數為10個的情況下，每個實際節點的虛擬節點數為實際節點的100-200倍的時候，結果還是很均衡的。 第3段中有這些文字：「但這樣的演算法方法存在致命問題，如果某一台機器宕機，那麼應該落在該機器的請求就無法得到正確的處理，這時需要將當掉的伺服器從演算法從去除，此時候會有(N-1)/N的伺服器的緩存數據需要重新進行計算；」 為何是 (N-1)/N 呢？解釋如下： 比如有 3 台機器，hash值 1-6 在這3台上的分布就是： host 1: 1 4 host 2: 2 5 host 3: 3 6 如果掛掉一台，只剩兩台，模數取 2 ，那麼分布情況就變成： host 1: 1 3 5 host 2: 2 4 6 可以看到，還在數據位置不變的只有2個： 1，2，位置發生改變的有4個，占共6個數據的比率是 4/6 = 2/3這樣的話，受影響的數據太多了，勢必太多的數據需要重新從 DB 載入到 cache 中，嚴重影響性能 【consistent hashing 的辦法】 上面提到的 hash 取模，模數取的比較小，一般是負載的數量，而 consistent hashing 的本質是將模數取的比較大，為 2的32次方減1，即一個最大的 32 位整數。然後，就可以從容的安排數據導向了，那個圖還是挺直觀的。 以下部分為一致性哈希演算法的一種PHP實現。點擊下載
⑵ 常用的緩存技術
第一章 常用的緩存技術
1、常見的兩種緩存
本地緩存：不需要序列化，速度快，緩存的數量與大小受限於本機內存
分布式緩存：需要序列化，速度相較於本地緩存較慢，但是理論上緩存的數量與大小無限（因為緩存機器可以不斷擴展）
2、本地緩存
Google guava cache：當下最好用的本地緩存
Ehcache：spring默認集成的一個緩存，以spring cache的底層緩存實現類形式去操作緩存的話，非常方便，但是欠缺靈活，如果想要靈活使用，還是要單獨使用Ehcache
Oscache：最經典簡單的頁面緩存
3、分布式緩存
memcached：分布式緩存的標配
Redis：新一代的分布式緩存，有替代memcached的趨勢
3.1、memcached
經典的一致性hash演算法
基於slab的內存模型有效防止內存碎片的產生（但同時也需要估計好啟動參數，否則會浪費很多的內存）
集群中機器之間互不通信（相較於Jboss cache等集群中機器之間的相互通信的緩存，速度更快<--因為少了同步更新緩存的開銷，且更適合於大型分布式系統中使用）
使用方便（這一點是相較於Redis在構建客戶端的時候而言的，盡管redis的使用也不困難）
很專一（專做緩存，這一點也是相較於Redis而言的）
3.2、Redis
可以存儲復雜的數據結構（5種）
strings-->即簡單的key-value，就是memcached可以存儲的唯一的一種形式，接下來的四種是memcached不能直接存儲的四種格式（當然理論上可以先將下面的一些數據結構中的東西封裝成對象，然後存入memcached，但是不推薦將大對象存入memcached，因為memcached的單一value的最大存儲為1M，可能即使採用了壓縮演算法也不夠，即使夠，可能存取的效率也不高，而redis的value最大為1G）
hashs-->看做hashTable
lists-->看做LinkedList
sets-->看做hashSet，事實上底層是一個hashTable
sorted sets-->底層是一個skipList
有兩種方式可以對緩存數據進行持久化
RDB
AOF
事件調度
發布訂閱等
4、集成緩存
專指spring cache，spring cache自己繼承了ehcache作為了緩存的實現類，我們也可以使用guava cache、memcached、redis自己來實現spring cache的底層。當然，spring cache可以根據實現類來將緩存存在本地還是存在遠程機器上。
5、頁面緩存
在使用jsp的時候，我們會將一些復雜的頁面使用Oscache進行頁面緩存，使用非常簡單，就是幾個標簽的事兒；但是，現在一般的企業，前台都會使用velocity、freemaker這兩種模板引擎，本身速度就已經很快了，頁面緩存使用的也就很少了。
總結：
在實際生產中，我們通常會使用guava cache做本地緩存+redis做分布式緩存+spring cache就集成緩存（底層使用redis來實現）的形式
guava cache使用在更快的獲取緩存數據，同時緩存的數據量並不大的情況
spring cache集成緩存是為了簡單便捷的去使用緩存（以註解的方式即可），使用redis做其實現類是為了可以存更多的數據在機器上
redis緩存單獨使用是為了彌補spring cache集成緩存的不靈活
就我個人而言，如果需要使用分布式緩存，那麼首先redis是必選的，因為在實際開發中，我們會緩存各種各樣的數據類型，在使用了redis的同時，memcached就完全可以舍棄了，但是現在還有很多公司在同時使用memcached和redis兩種緩存。
⑶ memcached 一致性hash 用的多嗎
memcache 是一個分布式的緩存系統，但是本身沒有提供集群功能，在大型應用的情況下容易成為瓶頸。但是客戶端這個時候可以自由擴展，分兩階段實現。第一階段：key 要先根據一定的演算法映射到一台memcache伺服器。第二階段從伺服器中取出緩存的值。...
⑷ 一致性hash演算法是什麼
一致性哈希演算法是在1997年由麻省理工學院提出的一種分布式哈希（DHT）演算法。其設計目標是為了解決網際網路中的熱點（Hot spot)問題，初衷和CARP十分類似。
一致性Hash是一種特殊的Hash演算法，由於其均衡性、持久性的映射特點，被廣泛的應用於負載均衡領域，如nginx和memcached都採用了一致性Hash來作為集群負載均衡的方案。
一致性哈希演算法的目標是，當K個請求key發起請求時。後台增減節點，只會引起K/N的key發生重新映射。即一致性哈希演算法，在後台節點穩定時，同一key的每次請求映射到的節點是一樣的。而當後台節點增減時，該演算法盡量將K個key映射到與之前相同的節點上。
優點
可擴展性。一致性哈希演算法保證了增加或減少伺服器時，數據存儲的改變最少，相比傳統哈希演算法大大節省了數據移動的開銷。
更好地適應數據的快速增長。採用一致性哈希演算法分布數據，當數據不斷增長時，部分虛擬節點中可能包含很多數據、造成數據在虛擬節點上分布不均衡，此時可以將包含數據多的虛擬節點分裂，這種分裂僅僅是將原有的虛擬節點一分為二、不需要對全部的數據進行重新哈希和劃分。
虛擬節點分裂後，如果物理伺服器的負載仍然不均衡，只需在伺服器之間調整部分虛擬節點的存儲分布。這樣可以隨數據的增長而動態的擴展物理伺服器的數量，且代價遠比傳統哈希演算法重新分布所有數據要小很多。
以上內容參考：網路-一致性哈希
⑸ 分布式緩存中，哈希取余分區和一致性哈希分區有什麼區別
環割法（一致性 hash）環割法的原理如下：
1. 初始化的時候生成分片數量 X × 環割數量 N 的固定方式編號的字元串，例如 SHARD-1-NODE-1，並計算所有 X×N 個字元串的所有 hash 值。
2. 將所有計算出來的 hash 值放到一個排序的 Map 中，並將其中的所有元素進行排序。
3. 輸入字元串的時候計算輸入字元串的 hash 值，查看 hash 值介於哪兩個元素之間，取小於 hash 值的那個元素對應的分片為數據的分片。
數據比較
下面將通過測試對環割法和跳躍法的性能及均衡性進行對比，說明 DBLE 為何使用跳躍法代替了環割法。
數據源：現場數據 350595 條
測試經過：
1. 通過各自的測試方法執行對於測試數據的分片任務。
2. 測試方法：記錄分片結果的方差；記錄從開始分片至分片結束的時間；記錄分片結果與平均數的最大差值。
3. 由於在求模法 PartitionByString 的方法中要求分片的數量是 1024 的因數，所以測試過程只能使用 2 的指數形式進行測試，並在 PartitionByString 方法進行測試的時候不對於 MAC 地址進行截斷，取全量長度進行測試。
⑹ memcache 一致性hash 為什麼 2的32
因為一致性hash演算法是來做伺服器的負載均衡，而伺服器的IP地址是32位，所以是2^32-1次方的數值空間
⑺ 用一致性hash做分布式，如果其中一台緩存down了，怎麼辦
環割法（一致性 hash）環割法的原理如下：
1. 初始化的時候生成分片數量 X × 環割數量 N 的固定方式編號的字元串，例如 SHARD-1-NODE-1，並計算所有 X×N 個字元串的所有 hash 值。
2. 將所有計算出來的 hash 值放到一個排序的 Map 中，並將其中的所有元素進行排序。
3. 輸入字元串的時候計算輸入字元串的 hash 值，查看 hash 值介於哪兩個元素之間，取小於 hash 值的那個元素對應的分片為數據的分片。
數據比較
下面將通過測試對環割法和跳躍法的性能及均衡性進行對比，說明 DBLE 為何使用跳躍法代替了環割法。
數據源：現場數據 350595 條
測試經過：
1. 通過各自的測試方法執行對於測試數據的分片任務。
2. 測試方法：記錄分片結果的方差；記錄從開始分片至分片結束的時間；記錄分片結果與平均數的最大差值。
3. 由於在求模法 PartitionByString 的方法中要求分片的數量是 1024 的因數，所以測試過程只能使用 2 的指數形式進行測試，並在 PartitionByString 方法進行測試的時候不對於 MAC 地址進行截斷，取全量長度進行測試。
⑻ chcahe 如何保證分布式緩存數據一致性
VPLEX的技術核心是「分布式緩存一致性」，下圖則是「分布式緩存一致性」技術的工作機制示意：正是因為這項核心技術優勢，使得VPLEX方案和目前所有廠商的虛擬化方案截然不同，並能夠實現異地的數據中心整合。對跨數據中心的所有負載實現跨引擎的平攤或者實時遷移，來自任何一個主機的I/O請求可以通過任何一個引擎得到響應。
緩存一致性的記錄目錄使用少量的元數據，記錄下哪個數據塊屬於哪個引擎更新的，以及在何時更新過，並通過4K大小的數據塊告訴在集群中的所有其他的引擎。在整個過程中實際發生的溝通過程，遠遠比實際上正在更新數據塊少很多。
分布式緩存一致性數據流示意圖：上方是一個目錄，記錄下左側的主機讀取緩存A的操作，並分發給所有引擎，右側主機需要讀取該數據塊時，會先通過目錄查詢，確定該數據塊所屬的引擎位置，讀取請求會直接發送給引擎，並直接從數據塊所在的緩存上讀取。
當一個讀請求進入時，VPLEX會自動檢查目錄，查找該數據塊所屬的引擎，一旦確定該數據塊所屬的引擎位置，讀的請求會直接發送給該引擎。一旦一個寫入動作完成，並且目錄表被修改，這時另一個讀請求從另一個引擎過來，VPLEX會檢查目錄，並且直接從該引擎的緩存上讀取。如果該數據仍然在緩存上，則完全沒必要去磁碟上讀取。
如上圖，來自圖中左側主機的操作，由Cache A服務，會記錄一個更新狀態，並分發給所有所有引擎知道。如果讀取的需求來自最右側的伺服器，首先通過目錄查詢。通過這種技術可以實現所有引擎一致性工作，而且這個技術不僅可以跨引擎還可以跨VPLEX集群，而VPLEX集群可以跨區域，因此緩存一致性也可以跨區域部署。
分布式緩存一致性技術使VPLEX相比傳統的虛擬化方案擁有更高的性能和可靠性，並實現異地數據中心的虛擬化整合
對傳統的虛擬化架構來說，如果虛擬化的I/O集群中有一個節點壞了，那麼性能就會降低一半，而且實際情況降低不止一半。因為壞了一個節點，這個節點緩存一般會被寫進去。因為沒有緩存，操作會直接寫到硬碟里。如果圖中中心這個節點壞掉，那主機所有的可用性都沒有了。而VPLEX如果有一個引擎或者一個控制器壞掉了，那這個引擎的負載會均攤到其他活動引擎上。這樣總體來講用戶可以維持可預知性能，性能降低也不那麼明顯。