3

小さなネットワークでいくつかのノードとキーをすばやく検索するために、Chord プロトコルを実装しようとしています。私が理解できないのは... Chordは、ノードとキーを円の上に配置するように考慮しています。また、それらの配置は、SHA-1 ハッシュ関数を適用して取得したハッシュ値によって決定されます。これらの値をどのように操作すればよいですか? それらを文字列として作成し、de9f2c7f d25e1b3a fad3e85a 0bd17d9b 100db4b3それを考慮して比較し"a" < "b" is trueますか？またはどのように？キーが別のキーの前か後かを知るにはどうすればよいですか?

4

2 に答える 2

1

キースペースはリングであるため、1 つの値が別の値よりも大きいとは言えません。リングを逆にすると、その逆になるからです。値が範囲内にあるかどうかを言うことができます。Chord DHT では、各サーバーは、その前のサーバーとの間の値の範囲内のキーを担当します。

ハッシュ値に文字列を使用しないことをお勧めします。この関数を分散システムに使用するべきではありませんが、hashCode新しいノードを追加するときにハッシュ キーを計算する必要があります。代わりに、ハッシュをBigIntegersに変換してみることができます。

于 2013-06-24T09:43:09.877 に答える
0

sha1 ハッシュは文字列ではありませんが、非常に長い 16 進数です。そうしないとネイティブの 160 ビット数値型が必要になるため、文字列として格納されることがよくあります。それらは 5 つの 32 ビットの 16 進数として構築され、しばしば一緒に「連結」されます。

sha1 文字列を数値として使用することは難しくありませんが、そのような大きな数値を処理できるライブラリ (BigInt や bcmath など) が必要です。これらのライブラリは、ペンと紙を使用して足し算、掛け算、割り算などを行うときのように、文字列内の数値を一度に 1 列ずつ右から左に計算することによって機能します。通常は、次のような一般的な計算を行うための関数があります。よく比較などを行い、多くの場合、文字列を引数として取ります。また、16 進数から 10 進数に変換する必要があるときはいつでも、大きな数値を変換する関数を使用するようにしてください。そうしないと、160 ビットの 16 進数が 64 ビットの 10 進数の浮動小数点数などに丸められ、その精度のほとんどが失われる可能性があります。

より多い/より少ない比較は、和音と数字の範囲で使用されますが、[64, 2] などの範囲を可能にする「ラップ」するようにモジュロを使用して使用します。実際の式は

find_successor(fingers[k] = n + 2^(k-1) mod(2^160))

ここで、「n」はノードの sha1 で、「k」はフィンガー番号です。

'n' は 16 進数で、'k' と 'mod(160^2)' は通常 10 進数であるため、ここで BigInt 16 進数から BigInt 10 進数が必要になります。

プログラミング フレームワークでこれらの var を 16 進数として作成できる場合でも、160 は特に 10 進数 (文字通り 1 60 ビットを意味する) であり、さらに、'mod(160^2)' を視覚化せずに脳を包み込むことは、すでに十分に困難です。 16 進数として。「k」などを hex に変換するのではなく、「n」を dec に変換してから、BigInt ライブラリを使用して比較を含む計算を行います。

于 2013-11-07T13:38:21.087 に答える