Dubbo 負荷分散戦略コンシステントハッシュ

この記事では、主にコンシステント ハッシュ アルゴリズムの原理とデータ スキューの問題について説明し、次にデータ スキューの問題を解決する方法を紹介し、最後に Dubbo でのコンシステント ハッシュ アルゴリズムの使用を分析します。この記事を通じて、コンシステント ハッシュ アルゴリズムの原理と、このアルゴリズムの問​​題点と解決策を理解することができます。

1. 負荷分散

以下はダボ公式サイトからの引用です:

LoadBalance は中国語で負荷分散を意味します。その役割は、ネットワーク要求やその他の形式の負荷を異なるマシンに「均等に分散」することです。クラスター内の一部のサーバーが過負荷になり、他のサーバーがアイドル状態になる状況を回避します。負荷分散により、各サーバーは自身の処理能力に適した負荷を得ることができます。トラフィックを高負荷サーバーに転送しながら、リソースの無駄も回避できるので、一石二鳥です。負荷分散は、ソフトウェア負荷分散とハードウェア負荷分散に分けられます。日常の開発では、ハードウェアの負荷分散に触れることは一般的に困難です。ただし、Nginx などのソフトウェア負荷分散は引き続き利用可能です。 Dubbo には、負荷分散の概念とそれに応じた実装もあります。

Dubbo は、いくつかのサービス プロバイダーに過負荷がかかるのを避けるために、サービス コンシューマーの呼び出し要求を分散する必要があります。サービス プロバイダーが過負荷状態になっているため、一部の要求がタイムアウトする可能性があります。そのため、各サービスプロバイダーへの負荷を分散させる必要があります。 Dubbo は、重み付けランダム アルゴリズムに基づく RandomLoadBalance、最もアクティブでない呼び出し番号アルゴリズムに基づく LeastActiveLoadBalance、ハッシュ一貫性に基づく ConsistentHashLoadBalance、および重み付けポーリング アルゴリズムに基づく RoundRobinLoadBalance の 4 つの負荷分散実装を提供します。これらの負荷分散アルゴリズムのコードはそれほど長くはありませんが、理解するのは簡単ではありません。これらのアルゴリズムの原理をある程度理解している必要があります。

2. ハッシュアルゴリズム

図1 ハッシュアルゴリズムを使用しないリクエスト

上記のように、サーバー 0、1、2 のすべてがユーザー情報を保存していると仮定すると、特定のユーザー情報を取得する必要がある場合、ユーザー情報がどのサーバーに保存されているかわからないため、サーバー 0、1、2 を個別に照会する必要があります。この方法でデータを取得する効率は極めて低いです。

このようなシナリオでは、ハッシュ アルゴリズムを導入できます。

図2 ハッシュアルゴリズム導入後のリクエスト

上記のシナリオと同じですが、前提として、各サーバーは特定のハッシュ アルゴリズムに従ってユーザー情報を保存します。したがって、ユーザー情報を取得するときは、同じハッシュアルゴリズムを使用するだけです。

ユーザー番号 100 のユーザー情報を照会するとします。特定のハッシュ アルゴリズム (ここでは userId mod n、つまり 100 mod 3) を実行すると、結果は 1 になります。したがって、ユーザー番号 100 からのリクエストは、最終的にサーバー番号 1 によって受信され、処理されます。

これにより、無効なクエリの問題が解決されます。

しかし、そのような計画はどのような問題をもたらすのでしょうか?

容量を拡張または縮小すると、大量のデータが移行されます。少なくとも 50% のデータが影響を受けます。

図3 サーバーの追加

問題を説明するために、サーバー 3 を追加します。サーバーの数 n が 3 から 4 に増加します。ユーザー番号100のユーザー情報を照会すると、100 mod 4の結果は0になります。このとき、リクエストはサーバー 0 によって受信されます。

• サーバーの数が 3 の場合、ユーザー番号 100 からのリクエストはサーバー番号 1 によって処理されます。
• サーバーの数が 4 の場合、ユーザー番号 100 からの要求はサーバー番号 0 によって処理されます。

そのため、サーバーの台数が増減すると、必然的に大量のデータ移行が必要になります。

上記のハッシュ アルゴリズムの利点は、シンプルで使いやすいことであり、ほとんどのデータベースおよびテーブル シャーディング ルールはこのアプローチを採用しています。通常、パーティションの数はデータの量に基づいて事前に見積もられます。

デメリットは、ノードの拡張や縮小によりノード数が変わると、ノードのマッピング関係を再計算する必要があり、データの移行が発生することです。したがって、容量を拡張する場合、すべてのデータ マッピングが中断され、完全な移行が発生しないように、通常は容量を 2 倍にします。この方法では、データの 50% のみが移行されます。

3. 一貫性ハッシュアルゴリズム

** コンシステント ハッシュ アルゴリズムは、1997 年にマサチューセッツ工科大学の Karger 氏とその協力者によって提案されました。このアルゴリズムは、もともと大規模なキャッシュ システムの負荷分散に使用されていました。 ** 動作プロセスは次のとおりです。まず、IP またはその他の情報に基づいてキャッシュ ノードのハッシュが生成され、そのハッシュが [0, 232 - 1] リングに投影されます。クエリまたは書き込み要求があると、キャッシュ項目のキーに対してハッシュ値が生成されます。次に、ハッシュ値以上の最初のキャッシュ ノードを見つけ、このノードにキャッシュ アイテムを照会または書き込みます。現在のノードがダウンしている場合は、次にキャッシュをクエリまたは書き込むときに、キャッシュ項目のハッシュ値よりも大きい別のキャッシュ ノードを見つけることができます。一般的な効果は下の図に示されており、各キャッシュ ノードがリング上の位置を占めています。キャッシュ アイテムのキーのハッシュ値がキャッシュ ノードのハッシュ値より小さい場合、キャッシュ アイテムはキャッシュ ノードに保存されるか、キャッシュ ノードから読み取られます。たとえば、下の緑色の点に対応するキャッシュ項目は、cache-2 ノードに保存されます。 cache-3 がダウンしているため、そのノードに保存されるはずだったキャッシュ項目は、最終的に cache-4 ノードに保存されることになります。

図4 一貫性ハッシュアルゴリズム

一貫性ハッシュ アルゴリズムでは、ノードの追加またはノードのシャットダウンのいずれの場合でも、影響を受ける間隔は、サーバーの追加またはシャットダウン時にハッシュ リング空間で反時計回り方向に最初に検出されたサーバー間の間隔のみであり、他の間隔は影響を受けません。

しかし、一貫性のあるハッシュにも問題があります。

図5 データの偏り

この分散は、ノード数が少なく、サービス A がほとんどのリクエストを処理する場合に発生する可能性があります。この状況はデータスキューと呼ばれます。

では、データの偏りの問題をどのように解決すればよいのでしょうか?

仮想ノードに参加します。

まず、サーバーは必要に応じて複数の仮想ノードを持つことができます。サーバーに n 個の仮想ノードがあると仮定します。次にハッシュ値を計算するときは、IP + ポート + 番号の形式を使用してハッシュ値を計算できます。数字は0からnまでです。 IP + ポートは同じなので、これらの n 個のノードはすべて同じマシンを指します。

図6: 仮想ノードの紹介

仮想ノードを追加する前は、サーバー A がリクエストの大部分を処理していました。しかし、各サーバーに仮想ノード (A-1、B-1、C-1) があり、ハッシュ計算後に上図に示す位置になるものとします。すると、サーバAが負担したリクエストは、ある程度仮想ノードB-1とC-1に分散され（図の五芒星でマークされた部分）、実際にサーバBとCに分散されます。

一貫性ハッシュ アルゴリズムでは、仮想ノードを追加することでデータの偏りの問題を解決できます。

4. DUBBOにおけるコンシステントハッシュの応用

図7. Dubboの一貫性のあるハッシュリング

ここで、同じ色のノードは、Invoker1-1、Invoker1-2、...、Invoker1-160 など、同じサービス プロバイダーに属します。この目的は、仮想ノードを導入してリング上の Invoker を分散し、データの偏りの問題を回避することです。いわゆるデータスキューとは、ノードの分散が不十分なために多数のリクエストが同じノードに集中し、他のノードは少数のリクエストしか受信しない状況を指します。例えば：

図8 データスキュー問題

上記のように、リング上の Invoker-1 と Invoker-2 の分散が不均一なため、システム内の要求の 75% が Invoker-1 に送られ、要求の 25% のみが Invoker-2 に送られます。この問題の解決策は、仮想ノードを導入し、それを使用して各ノードの要求のバランスを取ることです。

ここまでで背景知識は普及したので、次はソースコードの解析に入っていきます。次のように、ConsistentHashLoadBalance の doSelect メソッドから始めましょう。

 public class ConsistentHashLoadBalance extends AbstractLoadBalance { private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = new ConcurrentHashMap<String, ConsistentHashSelector<?>>(); @Override protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) { String methodName = RpcUtils.getMethodName(invocation); String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName; // 获取invokers 原始的hashcode int identityHashCode = System.identityHashCode(invokers); ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key); // 如果invokers 是一个新的List 对象，意味着服务提供者数量发生了变化，可能新增也可能减少了。 // 此时selector.identityHashCode != identityHashCode 条件成立if (selector == null || selector.identityHashCode != identityHashCode) { // 创建新的ConsistentHashSelector selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, identityHashCode)); selector = (ConsistentHashSelector<T>) selectors.get(key); } // 调用ConsistentHashSelector 的select 方法选择Invoker return selector.select(invocation); } private static final class ConsistentHashSelector<T> {...} }

前述のように、doSelect メソッドは主に、呼び出し元リストが変更されたかどうかを検出したり、ConsistentHashSelector を作成したりするなどの予備作業を実行します。これらのタスクが完了すると、ConsistentHashSelector の select メソッドが呼び出され、負荷分散ロジックが実行されます。 select メソッドを分析する前に、一貫性のあるハッシュ セレクター ConsistentHashSelector の初期化プロセスを次のように見てみましょう。

 private static final class ConsistentHashSelector<T> { // 使用TreeMap 存储Invoker 虚拟节点private final TreeMap<Long, Invoker<T>> virtualInvokers; private final int replicaNumber; private final int identityHashCode; private final int[] argumentIndex; ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) { this.virtualInvokers = new TreeMap<Long, Invoker<T>>(); this.identityHashCode = identityHashCode; URL url = invokers.get(0).getUrl(); // 获取虚拟节点数，默认为160 this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160); // 获取参与hash 计算的参数下标值，默认对第一个参数进行hash 运算String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, "hash.arguments", "0")); argumentIndex = new int[index.length]; for (int i = 0; i < index.length; i++) { argumentIndex[i] = Integer.parseInt(index[i]); } for (Invoker<T> invoker : invokers) { String address = invoker.getUrl().getAddress(); for (int i = 0; i < replicaNumber / 4; i++) { // 对address + i 进行md5 运算，得到一个长度为16的字节数组byte[] digest = md5(address + i); // 对digest 部分字节进行4次hash 运算，得到四个不同的long 型正整数for (int h = 0; h < 4; h++) { // h = 0 时，取digest 中下标为0 ~ 3 的4个字节进行位运算// h = 1 时，取digest 中下标为4 ~ 7 的4个字节进行位运算// h = 2, h = 3 时过程同上long m = hash(digest, h); // 将hash 到invoker 的映射关系存储到virtualInvokers 中， // virtualInvokers 需要提供高效的查询操作，因此选用TreeMap 作为存储结构virtualInvokers.put(m, invoker); } } } } }

ConsistentHashSelector のコンストラクターは、設定から仮想ノードの数やハッシュ計算に関係するパラメーターの添え字を取得するなど、一連の初期化ロジックを実行します。デフォルトでは、最初のパラメーターのみがハッシュに使用されます。 ConsistentHashLoadBalance の負荷分散ロジックはパラメータ値によってのみ影響を受け、同じパラメータ値を持つリクエストは同じサービス プロバイダーに割り当てられることに注意してください。 ConsistentHashLoadBalance は重みを考慮しないので、使用時には注意が必要です。

仮想ノードの数とパラメータインデックス構成を取得したら、次に仮想ノードのハッシュ値を計算して、仮想ノードを TreeMap に格納します。この時点で、ConsistentHashSelector の初期化は完了です。次に、select メソッドのロジックを見てみましょう。

 public Invoker<T> select(Invocation invocation) { // 将参数转为key String key = toKey(invocation.getArguments()); // 对参数key 进行md5 运算byte[] digest = md5(key); // 取digest 数组的前四个字节进行hash 运算，再将hash 值传给selectForKey 方法， // 寻找合适的Invoker return selectForKey(hash(digest, 0)); } private Invoker<T> selectForKey(long hash) { // 到TreeMap 中查找第一个节点值大于或等于当前hash 的Invoker Map.Entry<Long, Invoker<T>> entry = virtualInvokers.tailMap(hash, true).firstEntry(); // 如果hash 大于Invoker 在圆环上最大的位置，此时entry = null， // 需要将TreeMap 的头节点赋值给entry if (entry == null) { entry = virtualInvokers.firstEntry(); } // 返回Invoker return entry.getValue(); }

前述のように、選択プロセスは比較的簡単です。まず、パラメータに対して md5 およびハッシュ操作を実行してハッシュ値を取得します。次に、この値を取得して、TreeMap でターゲット Invoker を検索します。

これで ConsistentHashLoadBalance の分析は終了です。

ConsistentHashLoadBalance のソース コードを読む前に、まず背景知識を補足することをお勧めします。そうしないと、コード ロジックを理解するのが非常に難しくなります。

5. 応用シナリオ

• DNS 負荷分散 最も初期の負荷分散テクノロジは DNS を通じて実装されました。DNS では、複数のアドレスに同じ名前が設定されているため、この名前を照会するクライアントはアドレスの 1 つを取得し、異なるクライアントが異なるサーバーにアクセスして負荷分散の目的を達成できます。 DNS ロード バランシングはシンプルで効果的な方法ですが、サーバーを区別したり、サーバーの現在の動作状態を反映することはできません。
• プロキシ サーバー負荷分散では、プロキシ サーバーを使用してリクエストを内部サーバーに転送します。この高速化モードを使用すると、静的 Web ページのアクセス速度が明らかに向上します。ただし、負荷分散の目的を達成するために、プロキシ サーバーを使用してリクエストを複数のサーバーに均等に転送するテクノロジも検討できます。
• アドレス変換ゲートウェイ ロード バランシングは、ロード バランシング アドレス変換ゲートウェイをサポートします。これにより、外部 IP アドレスを複数の内部 IP アドレスにマッピングし、各 TCP 接続要求に対して内部アドレスの 1 つを動的に使用して、ロード バランシングの目的を達成できます。
• これら 3 つの負荷分散方法に加えて、一部のプロトコルは、HTTP プロトコルのリダイレクト機能など、負荷分散関連の機能を内部的にサポートしています。HTTP は、TCP 接続の最上位層で実行されます。
• NAT ロード バランシング NAT (ネットワーク アドレス変換) は、1 つの IP アドレスを別の IP アドレスに変換するだけです。これは通常、未登録の内部アドレスと、登録済みの合法的なインターネット IP アドレス間の変換に使用されます。これは、インターネット IP アドレスが不足しており、内部ネットワーク構造をネットワーク外部の誰にも知られたくないという状況を解決するのに適しています。
• リバース プロキシ ロード バランシング 一般的なプロキシ方式は、内部ネットワーク ユーザーの接続要求をプロキシしてインターネット上のサーバーにアクセスします。クライアントはプロキシ サーバーを指定し、元々インターネット上のサーバーに直接送信されていた接続要求をプロキシ サーバーに送信して処理する必要があります。リバースプロキシ方式とは、インターネット上の接続要求をプロキシサーバーで受け付け、内部ネットワーク上のサーバーに転送し、サーバーから取得した結果をインターネット上の接続要求元のクライアントに返す方式です。このとき、プロキシサーバーは外部からはサーバーのように見えます。リバース プロキシ負荷分散技術は、インターネットからの接続要求を内部ネットワーク上の複数のサーバーに動的に転送し、リバース プロキシ方式で処理することで、負荷分散の目的を実現します。
• ハイブリッド ロード バランシング 一部の大規模ネットワークでは、複数のサーバー クラスター内のハードウェア機器、規模、提供されるサービスなどの違いにより、各サーバー クラスターに最適なロード バランシング方法を使用することを検討し、その後、これらの複数のサーバー クラスターを再度ロード バランシングまたはクラスター化して、全体として外部にサービスを提供する (つまり、これらの複数のサーバー クラスターを新しいサーバー クラスターとして扱う) ことで、最高のパフォーマンスを実現できます。このアプローチはハイブリッド負荷分散と呼ばれます。この方法は、単一のバランシング デバイスのパフォーマンスが多数の接続要求のニーズを満たせない場合に使用されることがあります。

著者: 喬潔、JD Logistics

出典: JD Cloud 開発者コミュニティ