Comment construire DHT dans Golang

DHT, ou table de hachage distribuée, est un protocole distribué utilisé pour mettre en œuvre le stockage distribué et l'informatique distribuée. Dans un environnement réseau peer-to-peer, DHT est particulièrement important car il peut servir de protocole de routage et de fonction clé pour organiser les données. Cet article explique comment implémenter DHT à l'aide du langage Golang.

1. Principe du DHT

L'algorithme de base utilisé par DHT est l'algorithme de table de hachage. DHT mappe respectivement les données et les nœuds dans un espace de hachage, et les valeurs de hachage des nœuds et des données déterminent leurs positions dans l'espace de hachage. Chaque nœud conserve sa propre valeur de hachage et la valeur de hachage de ses nœuds adjacents, formant ainsi un anneau de hachage.

Lorsqu'un nœud rejoint DHT, il doit contacter les nœuds connus, trouver la position à laquelle il doit appartenir sur l'anneau de hachage et devenir le nœud successeur de cette position. À ce stade, le nœud peut recevoir des demandes d'autres nœuds, stocker les données qui doivent être stockées à son propre emplacement et en même temps envoyer sa propre valeur de hachage et la valeur de hachage du nœud successeur au nœud connu. Lorsqu'un nœud quitte le DHT, il a besoin que ses nœuds successeurs se reconnectent pour assurer le fonctionnement normal du réseau DHT.

La position d'un nœud DHT dans l'anneau de hachage détermine non seulement sa position dans le réseau DHT, mais détermine également les données qu'il doit stocker et les requêtes qu'il doit traiter. Par exemple, lorsqu'un nœud a besoin de rechercher une valeur, il peut visiter les nœuds qui sont plus proches de cette valeur que dans l'anneau de hachage. Ces nœuds transmettent la demande étape par étape jusqu'à ce qu'un nœud soit trouvé qui stocke la valeur. De même, lorsqu'un nœud doit stocker une valeur, il doit la stocker sur un nœud plus proche de cette valeur que dans l'anneau de hachage.

2. Implémentation de DHT dans Golang

Il est très simple d'implémenter DHT dans Golang. Tout d’abord, nous devons utiliser une fonction de hachage pour convertir l’identité du nœud et des données en valeur de hachage. Golang fournit une variété de fonctions de hachage, notamment MD5, SHA-1, SHA-256, etc. Nous pouvons choisir n’importe lequel d’entre eux.

import (

"crypto/sha1"

)

func hash(data string) []byte {

h := sha1.New()
h.Write([]byte(data))
return h.Sum(nil)

}

Ensuite, nous devons définir un type de nœud pour stocker l'identité du nœud, la valeur de hachage et la valeur de hachage du nœud successeur.

type Node struct {

ID       string
Hash     []byte
Successor []byte

}

type DHT struct {

Nodes   map[string]*Node

}

La structure DHT contient une table de mappage de nœuds Nodes, qui stocke tous les nœuds connus. Nous pouvons utiliser map pour implémenter cette table de mappage.

Avant d'implémenter l'algorithme DHT, nous devons implémenter certaines fonctions auxiliaires, telles que trouver le nœud successeur correspondant à une valeur clé dans l'anneau de hachage, ajouter un nouveau nœud, etc.

func (dht *DHT) findSuccessor(key []byte) []byte {

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

}

func (dht DHT) addNode(node ​​​​Node) erreur {

if _, ok := dht.Nodes[node.ID]; ok {
    return errors.New("Node already exists")
}

dht.Nodes[node.ID] = node
dht.fixSuccessorList()
return nil

}

Dans findSuccessor fonction, nous parcourons la table de mappage de nœuds Nodes pour trouver un nœud successeur le plus proche de la clé de valeur de hachage donnée. Lorsque la clé est inférieure ou égale à la valeur de hachage du nœud ou que tous les nœuds ont été parcourus, la fonction renvoie le nœud successeur le plus proche. Dans la fonction addNode, nous vérifions d'abord si le nœud existe déjà dans la table de mappage de nœuds Nodes, et renvoyons une erreur s'il existe. Sinon, nous ajoutons le nouveau nœud à Nodes, puis appelons la fonction fixSuccessorList pour ajuster la liste des nœuds successeurs du nœud.

func (dht *DHT) fixSuccessorList() {

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
}

}

Dans la fonction fixSuccessorList, nous trions les nœuds de la table de mappage de nœuds, puis définissons le nœud prédécesseur et le nœud successeur pour chaque nœud. Le nœud précédent est le nœud avant le nœud actuel après le tri, et le nœud suivant est le nœud après le nœud actuel après le tri. Veuillez noter que nous utilisons l'opérateur % pour garantir que la connexion à la carte de nœuds est circulaire.

Enfin, nous pouvons implémenter l'algorithme DHT. Lorsqu'un nœud a besoin de trouver une valeur, il envoie une requête à ses nœuds successeurs. Si le nœud successeur n'a pas cette valeur, il transmet la requête à son nœud successeur. De même, lorsqu'un nœud a besoin de stocker une valeur, il stockera la valeur à son propre emplacement et enverra son hachage et celui du nœud successeur aux nœuds connus. Ces nœuds transmettront la demande étape par étape jusqu'à ce que le nœud stockant la valeur soit trouvé.

func (dht *DHT) findValue(key string) (string, error) {

hash := hash(key)
successor := dht.findSuccessor(hash)

if bytes.Equal(successor, hash) {
    return dht.Nodes[string(successor)].Value, nil
}

addr := dht.getNodeAddr(successor)
conn, err := net.Dial("tcp", addr)
if err != nil {
    return "", err
}
defer conn.Close()

request := &FindValueRequest{Key: key}
response := &FindValueResponse{}
if err := sendRequest(conn, request); err != nil {
    return "", err
}
if err := receiveResponse(conn, response); err != nil {
    return "", err
}

if len(response.Value) == 0 {
    return "", errors.New("Key not found")
}
return response.Value, nil

}

func (dht *DHT) storeValue(key, value string) error {

hash := hash(key)
successor := dht.findSuccessor(hash)

if bytes.Equal(successor, hash) {
    dht.Nodes[string(hash)].Value = value
    return nil
}

addr := dht.getNodeAddr(successor)
conn, err := net.Dial("tcp", addr)
if err != nil {
    return err
}
defer conn.Close()

request := &StoreValueRequest{Key: key, Value: value}
response := &StoreValueResponse{}
if err := sendRequest(conn, request); err != nil {
    return err
}
if err := receiveResponse(conn, response); err != nil {
    return err
}

return nil

}

dans la fonction findValue , nous utilisons d'abord la fonction de hachage pour convertir la valeur clé en valeur de hachage et trouvons le nœud successeur correspondant à la valeur de hachage. Si le nœud successeur est égal à la valeur de hachage, nous avons trouvé la valeur correspondante et la renvoyons. Sinon, nous envoyons une requête au nœud successeur et appelons récursivement la fonction qui gère la requête. Dans la fonction storeValue, nous utilisons la fonction de hachage pour convertir la valeur clé en valeur de hachage et trouver le nœud successeur correspondant à la valeur de hachage. Si le nœud successeur est égal à la valeur de hachage, nous stockons la valeur sur ce nœud et la renvoyons. Sinon, nous envoyons une requête au nœud successeur et appelons récursivement la fonction qui gère la requête.

3.Résumé

Cet article présente comment implémenter l'algorithme DHT en utilisant le langage Golang. DHT est un protocole distribué basé sur une table de hachage utilisé pour implémenter le stockage distribué et l'informatique distribuée. Cet article nous permet de mieux comprendre les principes et la mise en œuvre de ce protocole en implémentant un algorithme DHT simple. Le DHT est largement utilisé dans de nombreux domaines, tels que le partage de fichiers BitTorrent, la vérification des transactions de cryptomonnaies comme le Bitcoin, etc.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!