目次
はじめに
本記事は、Kademlia解説と実装 2です。今回はJavaScriptを用いてKademliaの実装を行っていきます。次回は今回作成したプログラムを元に、ブラウザで動作するサンプルプログラムを作成して動作確認をしていきます。
本記事で作成したプログラムはhttps://github.com/shinyoshiaki/kademlia-with-webrtcにアップロードされています。
本記事は、過去にコンセンサス・ベイスが主宰していたオンラインサロンの記事です。記事は2017年~2018年にかけて執筆されたため、一部は、既に古くなっている可能性があります。あらかじめご了承ください。
関連する記事
Kademliaの解説と実装 1
Kademliaの解説と実装 3
使用技術
今回使用する主なライブラリを以下に示します。
| 名前 | 説明 |
| Socket.io | リアルタイム通信 |
| WebRTC | ブラウザ用のリアルタイム通信 |
| simple-datachannel | 上記のWebRTCのラッパー |
| sha1 | sha1ハッシュ関数のライブラリ |
実装の解説
ソースコードのファイル構成
今回のプログラムのファイル構成を以下に示します。
.
├── cli
│ ├── server.js
│ ├── setup.js
│ └── wrap.js
├── constants
│ ├── format.js
│ └── type.js
├── kad
│ ├── Kademlia.js
│ ├── KApp.js
│ ├── KConst.js
│ ├── KResponder.js
│ ├── KUtil.js
│ └── sample.js
├── lib
│ └── util.js
└── node
└── PortalNode.js
Kadディレクトリ以下がKademliaのコード群です。Kademlia.jsがKademliaの制御クラスでKconst.jsが定数の定義、KResponder.jsは通信の制御、KUtilはKademliaで必要な処理を行う関数群となっています。
ノードID
sha1というライブラリと乱数を用いてノードIDを生成し、これから作るKademliaのクラスに渡します。
/src/node/PotalNode
this.nodeId = sha1(Math.random().toString());
this.kad = new Kademlia(this.nodeId);経路表
「this.f.~」となっている箇所はKUtilの関数を呼び出しているところです。
経路表の構築をaddPeer(peer)という関数で行っています。新しく追加されるpeerをk-buckets中の正しい位置に配置していく仕組みとなっています。
/src/kad/Kademlia
addknode(peer) {
//略
if (!this.f.isNodeExist(peer.nodeId)) {
//自分のノードIDと追加するノードIDの距離
const num = this.f.distance(this.nodeId, peer.nodeId);
//kbucketsの該当する距離のkbucketを呼び出す
const kbucket = this.kbuckets[num];
//該当するkbucketに新しいピアを加える
kbucket.push(peer);
//略
}
}
プロトコル
Kademliaの4つのプロトコルを実装していきます。
ping
pingを送信する側のコードを以下に示します。
/src/kad/Kademlia
ping(peer) {
return new Promise((resolve, reject) => {
console.log("ping", peer.nodeId);
//10秒以内にpingのフラグが立てば成功
const timeout = setTimeout(() => {
console.log("ping fail", peer.nodeId);
peer.isDisconnected = true;
this.f.cleanDiscon();
this.callback.onPeerDisconnect(this.kbuckets);
reject("ping timeout");
}, 10 * 1000);
//ping完了時のコールバック
this.callback.onPingArr[peer.nodeId] = () => {
console.log("ping success");
clearTimeout(timeout);
resolve(true);
};
//自分のノードIDを含める
const sendData = { target: peer.nodeId };
//pingを送る
peer.send(networkFormat(this.nodeId, def.PING, sendData), "kad");
});
}
受け取る側のコードを以下に示します。
/src/kad/KResponder
responder[def.PING] = network => {
const data = network.data;
if (data.target === k.nodeId) {
console.log("ping received");
//ノードIDからピアを取得
const peer = this.k.f.getPeerFromnodeId(network.nodeId);
const sendData = { target: network.nodeId };
peer.send(networkFormat(k.nodeId, def.PONG, sendData), "kad");
}
};
pongというメッセージを送り返します。
pingを送った送信元が送り返されたpongを受け取るコードを以下に示します。
/src/kad/KResponder
responder[def.PONG] = network => {
const data = network.data;
if (data.target === k.nodeId) {
console.log("pong received", network.nodeId);
//pingのコールバック
this.k.callback.onPingArr[network.nodeId]();
}
};
store
storeの関数のコードを以下に示します。
/src/kad/Kademlia
async store(sender, key, value) {
//自分に一番近いピアを取得
const peer = this.f.getCloseEstPeer(key);
console.log(def.STORE, "next", peer.nodeId, "target", key);
//取得したピアにping
const result = await this.ping(peer).catch(console.log);
if (result) {
//storeを送る
peer.send(this.storeFormat(sender, key, value), "kad");
console.log("store done", this.storeFormat(sender, key, value));
} else {
console.log("store failed");
}
}
storeを受け取るコードを以下に示します。
/src/kad/KResponder.js
responder[def.STORE] = network => {
console.log("on store", network.nodeId);
const data = network.data;
//自分と送信元の距離
const mine = k.f.distance(k.nodeId, data.key);
//自分のkbuckets中で送信元に一番近い距離
const close = k.f.getCloseEstDist(data.key);
if (mine > close) {
console.log("store transfer", "\ndata", data);
//storeし直す
k.store(data.sender, data.key, data.value);
} else {
console.log("store arrived", mine, close, "\ndata", data);
//受け取る
this.k.keyValueList[sha1(data.value)] = data.value;
}
//略
};
findnode
処理の流れは問い合わせ元をA、問い合わせ先をBとするとA→B→Aの順番になります
問い合わせ元のfindnode関数のコードを以下に示します。
/src/kad/Kademlia
async findNode(targetId, peer) {
console.log("findnode");
//接続確認
const result = await this.ping(peer).catch(console.log);
if (result) {
console.log("findnode", targetId);
this.state.findNode = targetId;
const sendData = { targetKey: targetId };
//送る
peer.send(networkFormat(this.nodeId, def.FINDNODE, sendData), "kad");
}
}
問い合わせ先のコードを以下に示します。
/src/kad/KResponder.js
responder[def.FINDNODE] = network => {
console.log("on findnode", network.nodeId);
const data = network.data;
//要求されたキーに近い複数のキーを送る
const sendData = { closeIDs: k.f.getCloseIDs(data.targetKey) };
if (this.k.f.getPeerFromnodeId(network.nodeId)) {
console.log("sendback findnode");
//送り返す
this.k.f
.getPeerFromnodeId(network.nodeId)
.send(networkFormat(k.nodeId, def.FINDNODE_R, sendData), "kad");
}
};
返答を受ける問い合わせ元のコードを以下に示します。
/src/kad/KResponder.js
responder[def.FINDNODE_R] = async network => {
const data = network.data;
//返ってきた複数のID
const ids = data.closeIDs;
console.log("on findnode-r", ids);
//複数の非同期処理をまとめて実行する
Promise.all(
ids.map(async target => {
if (target !== this.k.nodeId && !this.k.f.isNodeExist(target)) {
//IDが接続されていないものなら接続する
await this.k.offer(target, network.nodeId).catch(console.log);
}
//ノードIDが見つかったらコールバック
if (this.k.state.findNode === target) {
this.k.callback.onFindNode();
}
})
);
//初期動作のfindnodeでなければ
if (k.state.findNode !== k.nodeId) {
console.log("not found");
//ノードIDが見つからなければ
if (!ids.includes(k.state.findNode)) {
//問い合わせ先を除外
const close = k.f.getCloseEstPeer(k.state.findNode, {
excludeId: network.nodeId
});
console.log("findnode-r keep find node", k.state.findNode);
//再探索
k.findNode(k.state.findNode, close);
}
}
};
findvalue
処理の流れは問い合わせ元をA、問い合わせ先をBとするとA→B→Aの順番になります。
問い合わせ元のfindvalue関数のコードを以下に示します。
/src/kad/Kademlia
findValue(key, cb = () => {}) {
this.callback.onFindValue = cb;
//keyに近いピアを取得
const peers = this.f.getClosePeers(key);
for (let peer in peers) {
//findvalueの実体
this.doFindvalue(peer);
}
}
async doFindvalue(peer) {
const result = await this.ping(peer).catch(console.log);
if (result) {
//送る
peer.send(
networkFormat(this.nodeId, def.FINDVALUE, {
targetKey: key
}),
"kad"
);
}
}
問い合わせ先のコードを以下に示します。
/src/kad/KResponder.js
responder[def.FINDVALUE] = network => {
console.log("on findvalue", network.nodeId);
const data = network.data;
//ターゲットのキーを持っていたら
if (Object.keys(k.keyValueList).includes(data.targetKey)) {
const value = k.keyValueList[data.targetKey];
const peer = k.f.getPeerFromnodeId(network.nodeId);
//キーが見つかったというメッセージを返す
peer.send(
networkFormat(this.k.nodeId, def.FINDVALUE_R, {
find: true,
value: value
}),
"kad"
);
} else {
//キーに最も近いピア
const ids = k.f.getCloseEstIdsList;
k.f.getPeerFromnodeId(network.nodeId).send(
networkFormat(k.nodeId, def.FINDVALUE_R, {
find: false,
ids: ids,
targetNode: data.targetNode,
targetKey: data.targetKey,
to: network.nodeId
}),
"kad"
);
}
};
返答を受ける問い合わせ元のコードを以下に示します。
/src/kad/KResponder.js
responder[def.FINDVALUE_R] = network => {
const data = network.data;
//valueを発見していれば
if (data.find) {
this.k.callback.onFindValue(data.value);
} else if (data.to === k.nodeId) {
console.log(def.FINDVALUE_R, "re find");
//発見できていなければ候補に対して再探索
for (let id in data.ids) {
const peer = this.k.f.getPeerFromnodeId(id);
k.doFindvalue(peer);
}
}
};
ノードの管理
経路表の更新
経路表の更新は何らかの通信を受け取った際に行われます。経路表の更新を行う関数maintainを以下に示します。
/src/kad/Kademlia
async maintain(network) {
const inx = this.f.distance(this.nodeId, network.nodeId);
const kbucket = this.kbuckets[inx];
//送信元が該当するk-bucketの中にあった場合
//そのノードをk-bucketの末尾に移す
kbucket.forEach((peer, i) => {
if (peer.nodeId === network.nodeId) {
console.log("maintain", "Moves it to the tail of the list");
kbucket.splice(i, 1);
kbucket.push(peer);
return 0;
}
});
//k-bucketがすでに満杯な場合、
//そのk-bucket中の先頭のノードがオンラインなら先頭のノードを残す
if (kbucket.length > this.k) {
console.log("maintain", "bucket fulled", network.nodeId);
const result = await this.ping(kbucket[0]).catch(console.log);
if (!result) {
kbucket.splice(0, 1);
}
}
}
ノードの新規参加
/src/kad/Kademlia
findNewPeer() {
if (this.f.getKbucketNum() < this.k) {
//自身のノードIDをkeyとしてFIND_NODE
this.findNode(this.nodeId, peer);
} else {
console.log("kbucket ready", this.f.getKbucketNum());
}
}
まとめ、次回予告
今回はKademliaの実装を行いました。次回ではブラウザ上でKademliaの接続状況を可視化できるツールを作成して今回作成したKademliaの動作確認を行っていきます。
参考資料
首藤一幸(2004)「Kademlia」
http://www.shudo.net/article/20040727-Kademlia/shudo-Kademlia.pdf
Petar Maymounkov and David Mazières(2009) “Kademlia: A Peertopeer Information System Based on the XOR Metric”
https://sicstus.sics.se/~amir/files/download/p2p/kademlia.pdf
Ikuta, Masahito(2008)「10分で解るKademliaと+α」
