数日前の出来事 ヒドラ会議。 JUG.ru グループのメンバーは、夢の講演者 (レスリー ランポート! クリフ クリック! マーティン クレップマン!) を招待し、分散システムとコンピューティングについて XNUMX 日間を費やしました。 Kontur はカンファレンスの XNUMX つのパートナーのうちの XNUMX 人でした。 私たちはブースで話したり、分散ストレージについて話したり、ビンゴをしたり、パズルを解いたりしました。

これは、テキストの著者による Kontur スタンドでのタスクの分析を含む投稿です。 誰がヒドラに乗っていましたか - これは楽しい経験を思い出す理由です、誰が乗っていませんでしたか - あなたの頭脳を伸ばすチャンスです 大きなO-表記。

フリップチャートをスライドに分解して自分の決定を書き留めた参加者もいました。 冗談ではありません。彼らは確認のためにこの紙の束を渡しました。

合計 XNUMX つのタスクがありました。

• 負荷分散のための重みによるレプリカの選択について
• インメモリデータベースに対するクエリ結果の並べ替えについて
• リングトポロジを備えた分散システムにおける状態転送について

タスク 1. ClusterClient

分散システムの N 個の重み付きレプリカから K 個を効率的に選択するためのアルゴリズムを提案する必要がありました。

あなたのチームは、N 個のノードからなる大規模分散クラスター用のクライアント ライブラリを開発する任務を負っています。 ライブラリは、ノードに関連付けられたさまざまなメタデータ (たとえば、待ち時間、4xx/5xx 応答速度など) を追跡し、それらに浮動小数点の重み W1..WN を割り当てます。 同時実行戦略をサポートするために、ライブラリは N 個のノードのうち K 個をランダムに選択できる必要があります。選択される確率はノードの重みに比例する必要があります。

ノードを効率的に選択するアルゴリズムを提案します。 ビッグ O 表記法を使用して計算の複雑さを推定します。

なんで全部英語なの？

なぜなら、この形態では会議の参加者が彼らと戦ったからであり、英語がヒドラの公用語だったからです。 タスクは次のようになりました。

紙と鉛筆を用意して、すぐにネタバレを開こうとしないでください 🙂

ソリューションの分析 (ビデオ)

5:53 からわずか 4 分間:

そして、フリップチャートを持った人たちが解決策を提案した方法は次のとおりです。

ソリューションの分析 (テキスト)

次の解決策が表面上にあります。すべてのレプリカの重みを合計し、0 からすべての重みの合計までの乱数を生成し、レプリカの重みの合計が 0 から (i-1) 番目までになるように i レプリカを選択します。は乱数より小さく、0 から i 番目までのレプリカの重みの合計はそれより大きくなります。 したがって、2 つのレプリカを選択することができ、次のレプリカを選択するには、選択したレプリカを考慮せずに手順全体を繰り返す必要があります。 このようなアルゴリズムを使用すると、XNUMX つのレプリカを選択する複雑さは O(N)、K 個のレプリカを選択する複雑さは O(N K) ~ O(NXNUMX) になります。

二次複雑性は悪いですが、改善することができます。 これを行うには、次のように構築します。 セグメントツリー 重みの合計の場合。 深さ lg N のツリーが取得されます。その葉にはレプリカの重みがあり、残りのノードには部分和がツリーのルートのすべての重みの合計まで存在します。 次に、0 からすべての重みの合計までの乱数を生成し、i 番目のレプリカを見つけてツリーから削除し、この手順を繰り返して残りのレプリカを見つけます。 このアルゴリズムを使用すると、ツリーを構築する複雑さは O(N)、i 番目のレプリカを見つけてツリーから削除する複雑さは O(lg N)、K 個のレプリカを選択する複雑さは O(N + K lg N) ~ O(N lg N) 。

線形対数複雑度は、特に K が大きい場合、二次関数複雑度よりも優れています。

それがこのアルゴリズムです コードで実装される プロジェクトの ClusterClient ライブラリ」イースト」。 (そこで、ツリーは O(N lg N) で構築されますが、これはアルゴリズムの最終的な複雑さには影響しません。)

タスク 2. ゼブラ

インデックスのない任意のフィールドによってメモリ内のドキュメントを効率的に並べ替えるためのアルゴリズムを提案する必要がありました。

あなたのチームは、シャード化されたメモリ内ドキュメント データベースを開発する任務を負っています。 一般的な作業負荷は、サイズ M (通常は N < 100 << M) のコレクションから、任意の (インデックスなし) 数値フィールドによって並べ替えられた上位 N 個のドキュメントを選択することです。 やや一般的ではないワークロードは、上位 S 個のドキュメント (S ～ N) をスキップした後に上位 N 個を選択することです。

このようなクエリを効率的に実行するアルゴリズムを提案します。 平均的なケースと最悪のケースのシナリオでビッグ O 表記を使用して計算の複雑さを推定します。

ソリューションの分析 (ビデオ)

34:50から始まり、わずか6分間:

ソリューションの分析 (テキスト)

表面的なソリューション: すべてのドキュメントを並べ替えます (たとえば、 クイックソート)、N+S 個のドキュメントを取得します。 この場合、ソートの複雑さは平均して O(M lg M)、最悪でも O(M2) になります。

M 個の文書をすべてソートし、その一部だけを取り出すのは非効率であることは明らかです。 すべての文書をソートしないようにするには、アルゴリズムが適しています クイックセレクト、これにより、目的のドキュメントを N + S 個選択します (ドキュメントは任意のアルゴリズムで並べ替えることができます)。 この場合、複雑さは平均して O(M) に減少しますが、最悪の場合は同じままです。

ただし、アルゴリズムを使用すると、さらに効率的に実行できます。 バイナリ ヒープ ストリーミング。 この場合、最初の N+S ドキュメントが (ソート方向に応じて) min-heap または max-heap に追加され、次の各ドキュメントが現在の最小または最大ドキュメントを含むツリーのルートと比較されます。必要に応じてツリーに追加されます。 この場合、ツリーを常に再構築する必要がある最悪の場合の複雑さは O(M lg M) で、クイック選択の場合と同様、平均の複雑さは O(M) です。

ただし、実際には、ルート要素との XNUMX 回の比較後にヒープを再構築せずにほとんどのドキュメントを破棄できるため、ヒープ ストリーミングの方が効率的であることが判明しました。 このような並べ替えは、Kontur で開発および使用される Zebra メモリ内ドキュメント データベースに実装されています。

タスク 3. 状態の交換

状態をシフトするための最も効率的なアルゴリズムを提案する必要がありました。

あなたのチームは、N 個のノードからなる分散クラスター用の派手な状態交換メカニズムを開発する任務を負っています。 i 番目のノードの状態は (i+1) 番目のノードに転送され、N 番目のノードの状態は最初のノードに転送されます。 サポートされている唯一の操作は、XNUMX つのノードが状態をアトミックに交換する場合の状態交換です。 状態の交換には M ミリ秒かかることが知られています。 すべてのノードはいつでも単一の状態スワップに参加できます。

クラスター内のすべてのノードの状態を転送するにはどれくらい時間がかかりますか?

ソリューションの分析 (テキスト)

表面解法: 最初と XNUMX 番目の要素、次に XNUMX 番目と XNUMX 番目、次に XNUMX 番目と XNUMX 番目の要素の状態を交換します。 各交換の後、XNUMX つの要素の状態は目的の位置になります。 O(N) 個の順列を作成し、O(N M) 時間を費やす必要があります。

線形時間は長いため、要素の状態をペアで交換できます (最初の要素と XNUMX 番目の要素、XNUMX 番目の要素と XNUMX 番目の要素など)。 各状態の交換後、XNUMX つおきの要素が正しい位置に配置されます。 O(lg N) 個の順列を作成し、O(M lg N) 時間を費やす必要があります。

ただし、シフトを線形ではなく一定時間でさらに効率的に行うことも可能です。 これを行うには、最初のステップで、最初の要素の状態を最後の要素と交換し、2 番目の要素を最後から 1 番目の要素と交換する必要があります。 最後の要素の状態は正しい位置になります。 次に、XNUMX 番目の要素の状態を最後の要素と交換し、XNUMX 番目の要素と最後から XNUMX 番目の要素の状態を交換する必要があります。 このラウンドの交換の後、すべての要素の状態は正しい位置になります。 合計で O(XNUMXM) ~ O(XNUMX) 個の順列が存在します。

このような解決策は、回転が XNUMX つの軸対称の合成であることをまだ覚えている数学者にはまったく驚かないでしょう。 ちなみに、これは XNUMX つずつではなく、K < N 個の位置のシフトに対して自明に一般化されます。 (コメントに正確に書いてください。)

パズルは好きでしたか？ 他の解決策を知っていますか? コメントで共有してください。

最後にいくつかの役立つリンクを示します。

• についてもっと学ぶ インフラ整備 輪郭で
• 内部の記録を参照 レポート付きチラシ 分散システムについて
• 一連のビデオ講義を見る一般人にとっては珍しいアルゴリズム»
• 私たちの購読を購読してください テレグラムのチャンネル

出所： habr.com