一致散列：環的數據結構保存在哪裏

Question

我們有N個緩存節點，它們在環中具有基本的一致散列。

問題：

1. 存儲在此環的數據結構：
   • 在每個節點的？
   • 部分在每個節點的範圍？
   • 在作爲負載平衡器的獨立機器上？
     
     
2. 當其他節點加入它發生在環什麼？

非常感謝。

Answer 1

我已經找到了問題的答案否1.

答1： 所有的方法都寫在我的博客： http://ivoroshilin.com/2013/07/15/distributed-caching-under-consistent-hashing/

上有想要保留幾個選項環的數據結構：

• 協調的中心點：專用機器保持一個環並作爲中央負載均衡器工作w它將請求路由到合適的節點。優點：非常簡單的實現。這將非常適合不具有少量節點和/或數據的動態系統。缺點：這種方法的一大缺點是可擴展性和可靠性。穩定的分佈式系統沒有單一的故障點。

• 沒有中心協調點 - 完全重複：每個節點都保留環的完整副本。適用於穩定的網絡。這個選項用於例如在亞馬遜迪納摩。 優點：查詢以一跳直接路由到相應的緩存服務器。 缺點：從環中加入/離開服務器需要通知/修改環中的所有緩存服務器。

• 沒有中心協調點 - 部分重複：每個節點都保留環的部分副本。這個選項是CHORD算法的直接實現。在DHT方面，每個緩存機器都有它的預設者和後繼者，當接收到一個查詢時，檢查它是否有密鑰。如果該機器上沒有這樣的密鑰，則使用映射函數來確定它的哪個鄰居（後繼者和預先考慮者）與該密鑰的距離最小。然後它將查詢轉發給其距離最近的鄰居。該過程一直持續到當前的緩存機器找到密鑰並將其發回。 優點：對於高度動態的更改，以前的選項不適合，因爲節點間閒聊的開銷很大。因此這個選項是在這種情況下的選擇。缺點：沒有直接的消息路由。將消息路由到環中目標節點的複雜度爲O（lg N）。