DHT oder Distributed Hash Table ist ein verteiltes Protokoll, das zur Implementierung verteilter Speicherung und verteilter Datenverarbeitung verwendet wird. In einer Peer-to-Peer-Netzwerkumgebung ist DHT besonders wichtig, da es als Routing-Protokoll und eine Schlüsselfunktion für die Organisation von Daten dienen kann. In diesem Artikel wird erläutert, wie DHT mithilfe der Golang-Sprache implementiert wird.
1. Das Prinzip von DHT
Der von DHT verwendete Kernalgorithmus ist der Hash-Tabellen-Algorithmus. DHT ordnet Daten und Knoten jeweils einem Hash-Raum zu, und die Hash-Werte von Knoten und Daten bestimmen ihre Position im Hash-Raum. Jeder Knoten verwaltet seinen eigenen Hash-Wert und den Hash-Wert seiner benachbarten Knoten und bildet so einen Hash-Ring.
Wenn ein Knoten DHT beitritt, muss er bekannte Knoten kontaktieren, die Position finden, zu der er im Hash-Ring gehören soll, und der Nachfolgeknoten dieser Position werden. Zu diesem Zeitpunkt kann der Knoten Anforderungen von anderen Knoten empfangen, die zu speichernden Daten an seinem eigenen Standort speichern und gleichzeitig seinen eigenen Hash-Wert und den Hash-Wert des Nachfolgeknotens an den bekannten Knoten senden. Wenn ein Knoten das DHT verlässt, muss er seine Nachfolgeknoten erneut verbinden, um den normalen Betrieb des DHT-Netzwerks sicherzustellen.
Die Position eines DHT-Knotens im Hash-Ring bestimmt nicht nur seine Position im DHT-Netzwerk, sondern auch, welche Daten er speichern und welche Anfragen er verarbeiten muss. Wenn ein Knoten beispielsweise einen Wert nachschlagen muss, kann er Knoten besuchen, die näher an diesem Wert liegen als im Hash-Ring. Diese Knoten leiten die Anfrage Schritt für Schritt weiter, bis ein Knoten gefunden wird, der den Wert speichert. Wenn ein Knoten einen Wert speichern muss, muss er ihn auf einem Knoten speichern, der näher an diesem Wert liegt als im Hash-Ring.
2. DHT in Golang implementieren
Es ist sehr einfach, DHT in Golang zu implementieren. Zuerst müssen wir eine Hash-Funktion verwenden, um die Identität des Knotens und der Daten in einen Hash-Wert umzuwandeln. Golang bietet eine Vielzahl von Hash-Funktionen, darunter MD5, SHA-1, SHA-256 usw. Wir können jede davon auswählen.
import (
"crypto/sha1"
)
func hash(data string) []byte {
h := sha1.New() h.Write([]byte(data)) return h.Sum(nil)
}
Als nächstes müssen wir einen Knotentyp definieren, um die Identität, den Hash-Wert und den Hash-Wert des Nachfolgeknotens zu speichern.
Typ Node-Struktur {
ID string Hash []byte Successor []byte
}
Typ DHT-Struktur {
Nodes map[string]*Node
}
Die DHT-Struktur enthält eine Knotenzuordnungstabelle Nodes, in der alle bekannten Knoten gespeichert sind. Wir können Map verwenden, um diese Zuordnungstabelle zu implementieren.
Bevor wir den DHT-Algorithmus implementieren, müssen wir einige Hilfsfunktionen implementieren, z. B. das Finden des Nachfolgerknotens, der einem Schlüsselwert im Hash-Ring entspricht, das Hinzufügen eines neuen Knotens usw. Im findSuccessor Funktion: Wir durchqueren die Knotenzuordnungstabelle Knoten, um einen Nachfolgerknoten zu finden, der dem angegebenen Hashwertschlüssel am nächsten liegt. Wenn der Schlüssel kleiner oder gleich dem Hashwert des Knotens ist oder alle Knoten durchlaufen wurden, gibt die Funktion den nächstgelegenen Nachfolgerknoten zurück. In der Funktion addNode prüfen wir zunächst, ob der Knoten bereits in der Knotenzuordnungstabelle Nodes vorhanden ist, und geben einen Fehler zurück, wenn er vorhanden ist. Andernfalls fügen wir den neuen Knoten zu „Nodes“ hinzu und rufen dann die Funktion „fixSuccessorList“ auf, um die Liste der Nachfolgerknoten des Knotens anzupassen.
func (dht *DHT) fixSuccessorList() {
for _, node := range dht.Nodes {
if bytes.Compare(key, node.Hash) == -1 || bytes.Equal(key, node.Hash) {
return node.Hash
}
}
return dht.Nodes[dht.minNode()].Hash}
In der fixSuccessorList-Funktion sortieren wir die Knotenzuordnungstabelle Nodes und legen dann den Vorgängerknoten und den Nachfolgerknoten für jeden Knoten fest. Der vorherige Knoten ist der Knoten vor dem aktuellen Knoten nach der Sortierung, und der nächste Knoten ist der Knoten nach dem aktuellen Knoten nach der Sortierung. Bitte beachten Sie, dass wir den %-Operator verwenden, um sicherzustellen, dass die Verbindung zur Knotenkarte kreisförmig ist. Endlich können wir den DHT-Algorithmus implementieren. Wenn ein Knoten einen Wert finden muss, sendet er eine Anfrage an seine Nachfolgeknoten. Verfügt der Nachfolgeknoten nicht über diesen Wert, leitet er die Anfrage an seinen Nachfolgeknoten weiter. Wenn ein Knoten einen Wert speichern muss, speichert er den Wert ebenfalls an seinem eigenen Speicherort und sendet seinen Hash und den Hash des Nachfolgeknotens an bekannte Knoten. Diese Knoten leiten die Anfrage Schritt für Schritt weiter, bis der Knoten gefunden wird, der den Wert speichert.
func (dht *DHT) findValue(key string) (string, error) {
if _, ok := dht.Nodes[node.ID]; ok {
return errors.New("Node already exists")
}
dht.Nodes[node.ID] = node
dht.fixSuccessorList()
return nil}
func (dht *DHT) storeValue(key, value string) error {
ids := make([]string, 0, len(dht.Nodes))
for id := range dht.Nodes {
ids = append(ids, id)
}
sort.Slice(ids, func(i, j int) bool {
return bytes.Compare(dht.Nodes[ids[i]].Hash, dht.Nodes[ids[j]].Hash) == -1
})
for i, id := range ids {
prev := ids[(i+len(ids)-1)%len(ids)]
next := ids[(i+1)%len(ids)]
dht.Nodes[id].Successor = dht.Nodes[next].Hash
dht.Nodes[id].Predecessor = dht.Nodes[prev].Hash
}}
in der findValue-Funktion , verwenden wir zunächst die Hash-Funktion, um den Schlüsselwert in einen Hash-Wert umzuwandeln und den Nachfolgerknoten zu finden, der dem Hash-Wert entspricht. Wenn der Nachfolgeknoten gleich dem Hashwert ist, haben wir den entsprechenden Wert gefunden und geben ihn zurück. Andernfalls senden wir eine Anfrage an den Nachfolgeknoten und rufen rekursiv die Funktion auf, die die Anfrage verarbeitet. In der StoreValue-Funktion verwenden wir die Hash-Funktion, um den Schlüsselwert in einen Hash-Wert umzuwandeln und den Nachfolgerknoten zu finden, der dem Hash-Wert entspricht. Wenn der Nachfolgeknoten dem Hashwert entspricht, speichern wir den Wert auf diesem Knoten und geben ihn zurück. Andernfalls senden wir eine Anfrage an den Nachfolgeknoten und rufen rekursiv die Funktion auf, die die Anfrage bearbeitet.
3. Zusammenfassung
In diesem Artikel wird erläutert, wie der DHT-Algorithmus mithilfe der Golang-Sprache implementiert wird. DHT ist ein Hash-Tabellen-basiertes verteiltes Protokoll, das zur Implementierung verteilter Speicherung und verteilter Datenverarbeitung verwendet wird. Dieser Artikel ermöglicht es uns, die Prinzipien und die Implementierung dieses Protokolls durch die Implementierung eines einfachen DHT-Algorithmus besser zu verstehen. DHT wird in vielen Bereichen häufig verwendet, beispielsweise beim Teilen von BitTorrent-Dateien, bei der Transaktionsüberprüfung von Kryptowährungen wie Bitcoin usw.
Das obige ist der detaillierte Inhalt vonWie man DHT in Golang erstellt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
