golangでdhtをビルドする方法-Golang-php.cn

golangでdhtをビルドする方法

王林

リリース： 2023-05-14 19:00:07

オリジナル

487 人が閲覧しました

DHT (分散ハッシュテーブル) は、分散ストレージと分散コンピューティングを実装するために使用される分散プロトコルです。ピアツーピアネットワーク環境では、DHT はルーティングプロトコルとして機能し、データを整理するための重要な機能として機能するため、特に重要です。この記事ではGolang言語を使ってDHTを実装する方法を紹介します。

1. DHT の原理

DHT で使用されるコアアルゴリズムはハッシュテーブルアルゴリズムです。 DHT はデータとノードをそれぞれハッシュ空間にマッピングし、ノードとデータのハッシュ値によってハッシュ空間内での位置が決まります。各ノードは、自身のハッシュ値と隣接ノードのハッシュ値を維持し、ハッシュリングを形成します。

ノードが DHT に参加する場合、既知のノードに接続し、ハッシュリング上で属するべき位置を見つけ、その位置の後継ノードになる必要があります。このとき、ノードは他のノードからのリクエストを受信し、保存する必要のあるデータを自身の場所に保存すると同時に、自身のハッシュ値と後継ノードのハッシュ値を既知のノードに送信することができます。ノードが DHT から離れると、DHT ネットワークが正常に動作するように、後続ノードが再接続する必要があります。

ハッシュリング内の DHT ノードの位置は、DHT ネットワーク内での位置を決定するだけでなく、どのデータを保存する必要があるか、どのリクエストを処理する必要があるかも決定します。たとえば、ノードが値を検索する必要がある場合、ハッシュリング内よりもその値に近いノードにアクセスできます。これらのノードは、値を格納するノードが見つかるまで、リクエストを段階的に転送します。同様に、ノードが値を保存する必要がある場合、ハッシュリング内よりもその値に近いノードに値を保存する必要があります。

2. Golang での DHT の実装

Golang での DHT の実装は非常に簡単です。まず、ハッシュ関数を使用して、ノードとデータの ID をハッシュ値に変換する必要があります。 Golang は、MD5、SHA-1、SHA-256 などのさまざまなハッシュ関数を提供します。どれでも選ぶことができます。

import (

"crypto/sha1"

ログイン後にコピー

)

func hash(data string) []byte {

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

ログイン後にコピー

}

次に、Aノードの ID、ハッシュ値、および後続ノードのハッシュ値を保存するには、ノードタイプを定義する必要があります。

type Node struct {

ID       string
Hash     []byte
Successor []byte

ログイン後にコピー

}

type DHT struct {

Nodes   map[string]*Node

ログイン後にコピー

}

DHT 構造にはノードマッピングテーブルが含まれていますノード。既知のすべてのノードを格納します。マップを使用してこのマッピングテーブルを実装できます。

DHT アルゴリズムを実装する前に、ハッシュリング内のキー値に対応する後続ノードの検索、新しいノードの追加など、いくつかの補助機能を実装する必要があります。

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) エラー {

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

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

ログイン後にコピー

}

findSuccessor 関数では、ノードマッピングテーブル Nodes を走査して、指定されたハッシュ値キーに最も近い後続ノードを見つけます。キーがノードのハッシュ値以下であるか、すべてのノードが走査されている場合、関数は最も近い後続ノードを返します。 addNode 関数では、まずノードがノードマッピングテーブル Nodes にすでに存在するかどうかを確認し、存在する場合はエラーを返します。それ以外の場合は、新しいノードを Nodes に追加し、fixSuccessorList 関数を呼び出してノードの後続リストを調整します。

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
}

ログイン後にコピー

}

fixSuccessorList 関数では、ノードマッピングテーブル Nodes をソートし、先行ノードと後継ノード。 prev ノードはソート後の現在のノードの前のノードであり、next ノードはソート後の現在のノードの後のノードです。ノードマップへの接続が確実に循環するように % 演算子を使用していることに注意してください。

最後に、DHT アルゴリズムを実装できます。ノードは値を見つける必要がある場合、後続ノードにリクエストを送信します。後続ノードがこの値を持たない場合、要求は後続ノードに転送されます。同様に、ノードが値を保存する必要がある場合、その値を独自の場所に保存し、そのハッシュと後継ノードのハッシュを既知のノードに送信します。これらのノードは、値を格納しているノードが見つかるまで、リクエストを段階的に転送します。

func (dht *DHT) findValue(キー文字列) (文字列、エラー) {

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(キー、値文字列) 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

ログイン後にコピー

}

findValue 関数では、まずハッシュ関数を使用してキー値をハッシュ値に変換し、ハッシュ値に対応する後継ノードを見つけます。後続ノードがハッシュ値と等しい場合、対応する値が見つかり、それが返されます。それ以外の場合は、後続ノードにリクエストを送信し、そのリクエストを処理する関数を再帰的に呼び出します。 storeValue 関数では、ハッシュ関数を使用してキー値をハッシュ値に変換し、ハッシュ値に対応する後継ノードを見つけます。後続ノードがハッシュ値と等しい場合、その値をそのノードに保存して返します。それ以外の場合は、後続ノードにリクエストを送信し、そのリクエストを処理する関数を再帰的に呼び出します。

3. 概要

この記事では、Golang 言語を使用して DHT アルゴリズムを実装する方法を紹介します。 DHT は、分散ストレージと分散コンピューティングを実装するために使用されるハッシュテーブルベースの分散プロトコルです。この記事では、単純な DHT アルゴリズムを実装することで、このプロトコルの原理と実装をより深く理解することができます。 DHT は、BitTorrent ファイル共有、ビットコインなどの暗号通貨のトランザクション検証など、さまざまな分野で広く使用されています。

以上がgolangでdhtをビルドする方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。