在分佈式哈希表中,您可以將節點構建爲一個環,其中環中的每個節點都知道環中至少有一個其他節點(以保持連接)。爲了使環更具容錯性,請確保每個節點都具有關於環中多個其他節點的知識,以便在某些節點崩潰時仍能夠連接。在DHT術語中,這被稱爲「後代名單」。當使用唯一ID和一些穩定協議在環中構造節點時,可以通過在環中路由來查找負責某個密鑰的節點,從而執行密鑰查找。
如何同步條目添加?
如果你不想複製,分散式共識的弱版本就足夠了,那就是每個節點都有其唯一的ID,並且他們知道環結構,這可以通過週期性的穩定協議,如在Chord中:http://nms.lcs.mit.edu/papers/chord.pdf
穩定協議使每個節點週期性地與其後繼者進行通信,以查看它是否是環中的真正後繼者,或者如果新節點已經加入環之間或者該後繼者已經崩潰並且戒指必須更新。由於沒有使用複製,爲了執行一致的插入,環足夠穩定,因此對等方可以將插入路由到正確的節點,將節點插入到其存儲中。每個項目只能由DHT中的單個節點保存,無需複製。
這種穩定過程可以給你非常好的概率,即環總是穩定的,並且可以最小化不一致性,但它不能保證強一致性,當節點加入或離開時環可能暫時不穩定。在不一致期間,可能會發生數據丟失,重複,覆蓋等問題。
如果您的應用程序需要很強的一致性,DHT不是最好的架構,那麼在DHT中實現這種一致性將會非常複雜。首先,您需要複製,並且您還需要在穩定化協議中添加大量的ACK和同步,例如對每個插入使用2PC協議或paxos協議以確保每個副本都獲得新值。
如何找到根? 如何確保每個人都有一個共享的根?
通常DHT與某些查找服務(集中式)相關聯,其中包含節點的IP/ID和服務中新節點的註冊。該服務還可以確保每個新節點都獲得唯一的ID。由於此服務僅管理標識和簡單查找,因此不會承受任何高負載或崩潰風險,因此可以在不影響容錯的情況下進行集中式設置,但當然也可以分發查找服務,以及合併他們用像Paxos這樣的共識協議。