この記事の主な研究は、一貫性のあるアルゴリズムコードです。
一貫したハッシュアルゴリズムは、1997年にMITによって提案されました（0を参照）。設計の目標は、インターネットのホットポットの問題を解決することであり、その当初の意図はcarに非常に似ていました。一貫したハッシュは、CARPが使用する単純なハッシュアルゴリズムによって引き起こされる問題を修正し、DHTをP2P環境で真に適用できるようにします。
一貫したハッシュは、ハッシュアルゴリズムが動的に変化するキャッシュ環境で満たすべき4つの適応条件を提案します。
バランスとは、すべてのキャッシュスペースを利用できるように、ハッシュの結果を可能な限りすべてのキャッシュに分散できることを意味します。多くのハッシュアルゴリズムがこの状態を満たすことができます。
単調性とは、一部のコンテンツがハッシュを介して対応するキャッシュにディスパッチされている場合、および新しいキャッシュがシステムに追加された場合を指します。ハッシュの結果は、古いキャッシュコレクションの他のバッファーにマッピングすることなく、元の割り当てられたコンテンツを新しいキャッシュにマッピングできるようにする必要があります。
単純なハッシュアルゴリズムは、最も単純な線形ハッシュなど、単調性の要件を満たすことができないことがよくあります。
x→ax + b mod（p）
上記の式では、Pはすべてのキャッシュのサイズを表します。キャッシュサイズが（P1からP2に）変化すると、元のハッシュ結果がすべて変化し、単調性の要件を満たしていないことを確認することは難しくありません。
ハッシュ結果の変化により、キャッシュスペースが変化すると、すべてのマッピング関係をシステムで更新する必要があることを意味します。 P2Pシステムでは、キャッシュの変更は、ピアがシステムを結合または退出することに相当します。この状況は、P2Pシステムで頻繁に発生し、巨大なコンピューティングと伝送負荷をもたらします。単調さでは、ハッシュアルゴリズムがこの状況を回避できることが必要です。
分散環境では、ターミナルはすべてのキャッシュを見ることはないかもしれませんが、それらの一部しか見ることができません。端末がハッシュプロセスを介してキャッシュにコンテンツをマッピングしたい場合、異なる端子で見られるキャッシュ範囲が異なる可能性があるため、ハッシュの結果は一貫していません。最終結果は、同じコンテンツが異なる端子によって異なるキャッシュ領域にマッピングされることです。この状況は、同じコンテンツを異なるバッファーに保存し、システムストレージの効率を低下させるため、明らかに避けるべきです。分散の定義は、上記の状況の重症度です。優れたハッシュアルゴリズムは、分散を最小限に抑えるために、可能な限り矛盾を避けることができるはずです。
負荷の問題は、実際には別の観点から地方分権化の問題を検討することです。異なる端子は、同じコンテンツを異なるバッファーにマッピングする可能性があるため、特定のバッファーの場合、異なるユーザーによって異なるコンテンツにマッピングされる場合があります。分散と同様に、この状況を避ける必要があるため、適切なハッシュアルゴリズムはバッファー負荷を最小限に抑えることができるはずです。
表面上、一貫したハッシュは分散バッファリングの問題をターゲットにしていますが、P2Pシステムのピアとしてバッファリングを考えると、さまざまな共有リソース（データ、ファイル、メディアストリームなど）としてマッピングされたコンテンツを考えると、2つが実際に同じ問題を説明していることがわかります。
一貫したハッシュアルゴリズムでは、各ノード（P2Pシステムのピアに対応）には、ランダムに割り当てられたIDがあります。コンテンツをノードにマッピングすると、コンテンツとノードのIDのキーワードを使用して一貫したハッシュ操作が実行され、キー値が取得されます。一貫したハッシュには、キー値とノードIDが同じ範囲であることが必要です。最も単純なキー値とIDは、0000から9999の整数セットなど、1次元になります。
キー値に基づいてコンテンツを保存する場合、コンテンツは、IDがキー値に最も近いIDでノードに保存されます。たとえば、キー値が1001の場合、システムにIDS 1000、1010、1100のノードがあり、コンテンツは1000ノードにマッピングされます。
クエリに必要なルートを構築するには、一貫性のあるハッシュでは、各ノードがアップリンクノードの位置情報（IPアドレス）を保存する必要があります（ID値は独自のノードの中で最小よりも大きくなります）。ノードがコンテンツを見つける必要がある場合、コンテンツのキー値に基づいてアップリンクまたはダウンリンクノードへのクエリリクエストを開始することを決定できます。クエリ要求を受信するノードが要求されたターゲットがあることを見つけた場合、クエリリクエストを開始するノードに直接確認を返すことができます。独自の範囲に属していないことがわかった場合、リクエストをアップリンク/ダウンリンクノードに転送できます。
上記のルーティング情報を維持するために、ノードがシステムを結合/終了する場合、隣接するノードはルーティング情報をタイムリーに更新する必要があります。これには、ノードが直接接続されたダウンリンクノードの位置情報を保存するだけでなく、特定の深さ（N-HOP）で間接的なダウンリンクノード情報を把握し、ノードリストを動的に維持する必要があります。ノードがシステムを終了すると、そのアップリンクノードは最も近いダウンリンクノードに直接接続しようとします。接続が成功した後、新しいダウンリンクノードからダウンリンクノードリストを取得し、独自のノードリストを更新します。同様に、新しいノードがシステムに追加されたら、最初に独自のIDに従ってダウンリンクノードを見つけてダウンリンクノードリストを取得し、アップリンクノードにダウンリンクノードリストを変更して、ルーティング関係を復元します。
話し合う
一貫したハッシュは、基本的にP2P環境で最も重要な問題を解決します - 動的ネットワークトポロジにストレージとルーティングを配布する方法。各ノードは、隣接する少数のノードの情報を保持する必要があり、ノードがシステムを結合/終了する場合、少数の関連ノードのみがトポロジのメンテナンスに参加します。これはすべて、一貫したハッシュを最初の実用的なDHTアルゴリズムにします。
ただし、一貫したハッシュのルーティングアルゴリズムにはまだ欠点があります。クエリプロセス中、クエリメッセージはo（n）ステップ（o（n）はnとの比例関係を示し、nはクエリノードに到達する前にシステム内のノードの総数を表します）を通過する必要があります。システムが非常に大きい場合、ノードの数が100万を超えている可能性があり、そのようなクエリ効率を使用するニーズを満たすのは明らかに困難であると想像することは難しくありません。別の観点から、たとえユーザーが長い遅延を許容できる場合でも、クエリプロセス中に生成される大量のメッセージは、ネットワークに不必要な負荷をもたらします。
パッケージherotrix; import java.util.collection; import java.util.sortedmap; import java.util.treemap; public class consedenthash <t> {// hash algorithm private final hashfunction; treemap <integer、t>（）; public consimenthash（hashfunction hashfunction、int numberofreplicas、collection <t> nodes）{this.hashfunction = hashfunction; this.numberofReplicas = numberofReplicas; for（t node：nodes）{add（node）;}} public void add（t node）{for（int i = 0; i <number ofreplicas; i ++）{circle.put（hashfunctring（）hashfunctring（hashfunctring（）+i）、node）;}} public void requid（t node） i ++）{circle.remove（hashfunction.hash（node.tostring（）+i））;}} // key algorithm public t get（object key）{if（circle.isempty（））{return null;} // hash値inth hash = hash（key） if（！circle.containskey（hash））{sortedmap <integer、t> tailmap = circle.tailmap（hash）; hash = tailmap.isempty（）？ circle.firstkey（）：tailmap.firstkey（）;} return circle.get（hash）;}}}上記は、Java言語の一貫したハッシュアルゴリズム学習ノート（コード例）に関するこの記事の内容全体です。私はそれが誰にでも役立つことを願っています。興味のある友人は、このサイトの他の関連トピックを引き続き参照できます。欠点がある場合は、それを指摘するためにメッセージを残してください。このサイトへのご支援をありがとうございました！