Course All lectures for JA purposes - Lecture: シャーディング: 裏側

2.1 シャーディングして N 倍遅くする方法は?

次のように、ちょうど N 回シャードして速度を落とすことができます。

docs00...docs15 リクエストを並列ではなく順番に送信します。
単純なクエリでは、 key 、 WHERE something=234 ではなく選択を行います。

この場合、シリアル化された部分 (シリアル) は 1% や 5% ではなく、最新のデータベースでは約 20% を占めます。非常に効率的なバイナリプロトコルを使用してデータベースにアクセスするか、ダイナミックライブラリとして Python スクリプトにリンクすると、シリアル化された部分の 50% を取得することもできます。

単純なリクエストの残りの処理時間は、リクエストの解析、プランの準備などの並列化できない操作によって占められます。つまり、レコードを読み込まないと速度が低下します。

たとえば、PHP プログラミング言語 (非同期プロセスの起動はあまり得意ではありません) で慣例的に行われているように、データを 16 のテーブルに分割して順次実行すると、速度は 16 倍遅くなります。そしておそらく、ネットワークの往復も追加されるため、さらに多くなるでしょう。

突然ですが、シャーディングを行う場合、プログラミング言語の選択が重要になります。

プログラミング言語の選択について思い出してください。クエリをデータベース (または検索サーバー) に順番に送信する場合、高速化はどこから来るのでしょうか? むしろ、減速が起こるでしょう。

2.2 セミオートについて

高度な情報技術は、場所によっては民族的恐怖を引き起こします。たとえば、MySQL には初期状態では特定のバージョンへのシャーディングが実装されていませんでしたが、戦闘で使用されるデータベースのサイズは法外な値まで増大します。

個々の DBA に直面して人類は何年も苦しんできており、何も根拠のない不適切なシャーディングソリューションをいくつか作成しています。その後、ProxySQL (MariaDB/Spider、PG/pg_shard/Citus など) と呼ばれる、多かれ少なかれまともなシャーディングソリューションが作成されます。これはまさにこのしみのよく知られた例です。

もちろん、ProxySQL は全体として、ルーティングなどのオープンソース向けの本格的なエンタープライズクラスのソリューションです。しかし、解決すべきタスクの 1 つはデータベースのシャーディングであり、データベース自体は人間の方法ではシャーディングできません。ご覧のとおり、「シャード = 16」スイッチはありません。アプリケーション内の各リクエストを書き直す必要があり、各リクエストはあちこちに大量にあります。あるいは、アプリケーションとデータベースの間に次のような中間層を置く必要があります。 ... SELECT * FROM ドキュメント? はい、16 個の小さな SELECT * FROM server1.document1、SELECT * FROM server2.document2 に分割する必要があります。このサーバーにはそのようなログイン/パスワードを使用し、このサーバーには別のログイン/パスワードを使用します。誰かが答えなかった場合は...」など。まさにこれは中間ブロッチによって実現できます。これらはすべてのデータベースよりも若干少ないです。PostgreSQLの場合、私が理解している限り、

それぞれの特定のパッチの構成は個別の大きなトピックであり、1 つのレポートに収まらないため、基本的な概念についてのみ説明します。バズ理論について少し話しましょう。

2.3 完全な自動化?

この文字F()でのシャーディングの場合にハイになる理論全体は、基本原則は常にほぼ同じです: shard_id = F(object)。

シャーディング - それは一体何ですか? 20 億件 (または 64 件) のレコードがあります。それらをいくつかの部分に分割したいと思います。予期せぬ質問が生じます - どのようにして? どのような原則に従って、20 億レコード (または 64) を利用可能な 16 台のサーバーに分散すべきでしょうか?

私たちの潜在的な数学者は、最終的には、各ドキュメント (オブジェクト、行など) に対して、それをどの部分に配置するかを決定する何らかの魔法の関数が常に存在することを示唆する必要があります。

計算をさらに詳しく見てみると、この関数は常にオブジェクト自体 (行自体) だけでなく、シャードの総数などの外部設定にも依存します。各オブジェクトの配置場所を指示する必要がある関数は、システム内のサーバーの数を超える値を返すことはできません。そして、関数は少し異なります。

shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...).

ただし、個々の関数の詳細についてはこれ以上掘り下げず、魔法の関数 F () がどのようなものであるかについてのみ説明します。

2.4 F()とは何ですか?

彼らは、さまざまなさまざまな実装メカニズムを思いつくことができます。サンプルの概要:

F = rand() % nums_shards
F = somehash(object.id) % num_shards
F = object.date % num_shards
F = object.user_id % num_shards
...
F = shard_table [ somehash() |… object.date |… ]

興味深い事実 - すべてのデータを自然にランダムに分散させることができます - 次のレコードを任意のサーバー、任意のコア、任意のテーブルにスローします。これではあまり幸せはありませんが、うまくいきます。

再現可能な、または一貫性のあるハッシュ関数によってシャードしたり、何らかの属性によってシャードしたりする、もう少しインテリジェントな方法があります。それぞれの方法を見てみましょう。

F = ランド()

周囲にばら撒くというのはあまり正しい方法ではありません。問題の 1 つは、20 億件のレコードを 1,000 台のサーバーにランダムに分散させたため、レコードがどこにあるのかわからないということです。user_1 を引き出す必要がありますが、それがどこにあるのかわかりません。私たちは何千ものサーバーにアクセスしてすべてを分類しますが、これはどういうわけか非効率的です。

F = サムハッシュ()

大人の方法でユーザーを分散させましょう。user_id から再現可能なハッシュ関数を計算し、サーバーの数で割った余りを取り、すぐに目的のサーバーに接続します。

なぜこれを行うのでしょうか? そして、負荷が高く、1 つのサーバーに他に適合するものが何もないということです。それが当てはまれば、人生はとてもシンプルになるでしょう。

素晴らしいですね、状況はすでに改善されています。1 つのレコードを取得するには、事前に 1 つの既知のサーバーにアクセスします。しかし、キーの範囲がある場合、この範囲全体でキーのすべての値を調べ、制限内で、範囲内のキーと同じ数のシャードに移動するか、さらには各サーバー。もちろん状況は改善されましたが、すべてのリクエストが改善されたわけではありません。一部のクエリが影響を受けています。

自然なシャーディング (F = object.date % num_shards)

場合によっては、トラフィックの 95% と負荷の 95% が、何らかの自然なシャーディングを伴うリクエストであることがよくあります。たとえば、条件付きソーシャル分析クエリの 95% は過去 1 日、3 日、7 日間のデータのみに影響し、残りの 5% は過去数年間を参照します。ただし、リクエストの 95% は当然のことながら日付ごとにシャーディングされるため、システムユーザーの関心は過去数日間に集中します。

この場合、データを日付ごと (たとえば 1 日ごと) に分割し、ある日のレポートまたはその日のオブジェクトのリクエストに対する応答をこのシャードまでたどることができます。

生活は改善されています。私たちは現在、特定のオブジェクトの位置を知るだけでなく、その範囲についても知ることができます。日付の範囲ではなく、他の列の範囲を要求された場合は、当然のことながら、すべてのシャードを調べなければなりません。しかし、ゲームのルールによれば、そのようなリクエストは 5% しかありません。

すべてに対して理想的な解決策を思いついたように見えますが、次の 2 つの問題があります。

このソリューションは、リクエストの 95% が先週のみに関係するという特定のケースに合わせて調整されています。
リクエストの 95% は先週のものであるため、リクエストはすべて、先週これを処理する 1 つのシャードに分類されます。このシャードは溶解しますが、この間、他のシャードはすべてアイドル状態になります。同時に、それらを捨てることはできず、アーカイブデータも保存する必要があります。

これが悪いシャーディングスキームであるというわけではありません。ホットデータは遮断されていますが、最もホットなシャードで何かを行う必要があります。

この問題は、おふざけ、ジャンプ、湿布によって解決されます。つまり、燃えている現在の日のレプリカの数が増加し、この日が過去になりアーカイブに保存されると、レプリカの数が徐々に減少します。「魔法のハッシュ関数を間違った方法でクラスターにデータを分散させればよい」という理想的な解決策はありません。

2.5 支払うべき価格

形式的には、私たちは今「すべて」を知っていることを知っています。確かに、1 つの巨大な頭痛と 2 つの小さな頭痛はわかりません。

1. 単純な痛み: ひどく汚れている

これは教科書に載っている例ですが、戦闘ではほとんど起こらないのですが、突然起こります。

日付ありの例ですが、日付なしのみです。
意図しない不均一な（知覚可能な）分布。

彼らはシャーディングメカニズムを選択した、またはデータが変更されました、そしてもちろん、PM は要件を伝えませんでした (コードにエラーはなく、PM は常に要件を報告しません)。ひどく不均一になりました。つまり、基準を満たしていないのです。

捕まえるには、破片のサイズを確認する必要があります。シャードの 1 つが過熱するか、他のシャードよりも 100 倍大きくなった時点で問題が発生することは間違いありません。キーまたはシャーディング機能を交換するだけで解決できます。

これは単純な問題です。正直に言うと、人生でこれに遭遇する人は 100 人に 1 人もいないと思いますが、突然、少なくとも誰かが助けることになります。

2. 「無敵」の痛み: 集約、結合

あるテーブルの 10 億レコードと別のテーブルの 10 億レコードを結合する選択を行うにはどうすればよいでしょうか?

「すばやく」計算する方法... aaa と bbb の間の randcol はどこですか?
users_32shards JOIN Posts_1024 シャードを「賢く」行うにはどうすればよいですか?

短い答え: とんでもない、苦しみなさい!

最初のテーブルで 10 億のレコードを 1,000 台のサーバーに分散して高速に動作させ、2 番目のテーブルでも同じことを行った場合、当然、1,000 台から 1,000 台のサーバーがペアで相互に通信するはずです。100 万の接続はうまく機能しません。シャーディングに適合しないデータベース (検索、ストレージ、ドキュメントストア、または分散ファイルシステム) に対してリクエストを行うと、これらのリクエストの速度が大幅に低下します。

重要な点は、一部のリクエストは常に不成功に処理され、速度が低下するということです。それらの割合を最小限に抑えるように努めることが重要です。結果として、10 億×10 億のレコードと巨大な結合を行う必要はありません。巨大な共有テーブルに結合している小さなテーブルをすべてのノードに複製できる場合は、複製する必要があります。たとえば、結合が何らかの方法で実際にローカルである場合、ユーザーとその投稿を並べて配置し、同じ方法でシャード化し、すべての結合を同じマシン内で実行することが可能です。これを実行する必要があります。。

これは 3 日間の個別の講義コースなので、最後の地獄のような痛みとそれに対処するためのさまざまなアルゴリズムに進みましょう。

2.6. 複雑/長い痛み: リシャーディング

準備をしましょう。人生で初めてデータをシャーディングした場合、平均してさらに 5 回データをシャーディングすることになります。

構成するクラスターの数に関係なく、再シャーディングが必要になります。

あなたが非常に賢くて幸運であれば、少なくとも 1 回はオーバーシャーディングを行ってください。しかし、一度確信が持てると、ユーザーにとって 10 ユニットで十分であると考えた瞬間に、誰かが 30 ユニットのリクエストを書き、未知のリソースの 100 ユニットのリクエストを計画しているからです。破片だけでは決して十分ではありません。最初のシャーディングスキームでは、どのような場合でも、追加するサーバーの数を増やすか、何か別のことを行う必要があります。一般に、何らかの方法でデータを再パッケージ化する必要があります。

2 の累乗が適切であれば良いです。サーバーシャードは 16 個ありましたが、現在は 32 です。サーバーシャードが 17 だったら、23 (2 つのほぼ素数) になるとさらに楽しいです。データベースはどのようにしてそれを行うのでしょうか。もしかしたら、データベースには何らかの魔法が組み込まれているのでしょうか?

正解は、「いいえ、中には魔法などありません。彼らの中に地獄があるのです。」です。

次に、「手動で」何ができるかを考えますが、おそらく「自動機械として」理解できるでしょう。

額にその1。すべてを再配置する

すべてのオブジェクトについて、NewF(object) を考慮し、新しいシャードに移行します。

NewF()=OldF() が一致する可能性は低いです。

ほぼすべてをカバーしましょう。

おお。

20億件のレコードすべてを古いシャードから新しいシャードに転送するような地獄が起こらないことを願っています。この単純なアプローチは理解できます。17 台のマシンがあり、6 台のマシンがクラスタに追加され、20 億件のレコードが整理され、17 台のマシンから 23 台のマシンに移行されました。10年に1回ならできるかもしれない。しかし全体的には悪い動きだ。

額その2。半分を移転する

次の単純な改善 - そのような愚かな計画は放棄しましょう - 17 台の車両が 23 台にリシャーディングされることを禁止し、常に 16 台の車両を 32 台の車両にリシャーディングします。次に、理論によれば、データのちょうど半分をシフトする必要があり、実際にもこれを行うことができます。

すべてのオブジェクトについて、NewF(object) を考慮し、新しいシャードに移行します。

以前は厳密に 2^N でしたが、現在は厳密に 2^(N+1) シャードです。

NewF()=OldF() に一致する確率は 0.5 です。

データの50％程度を転送しましょう。

最適ですが、2 の累乗でのみ機能します。

原則として、車の数の 2 のべき乗に拘束されることを除いて、すべて問題ありません。奇妙なことに、この素朴なアプローチはうまくいく可能性があります。

この場合、2 の累乗によるクラスターの追加分割も最適であることに注意してください。いずれにせよ、16 台のマシンを 16 台のクラスターに追加すると、データの半分、つまりちょうど半分をシフトする必要があります。

さて、しかし人類は本当に他に何も発明しなかったのだろうか - という疑問は探究心から生じます。

もっと楽しいその3。一貫したハッシュ化

もちろん、ここでは一貫性のあるハッシュに関する丸が付いた図が必要です。

Google で「consistent hashing」と検索すると、必ず円が表示され、すべての結果に円が表示されます。

アイデア: 円の上にシャード識別子 (ハッシュ) を描き、その上にハッシュ化されたサーバー識別子をマークしましょう。サーバーを追加する必要がある場合、円上に新しい点を置き、それに近いことが判明したもの (そして、それに近いことが判明したもののみ) を再配置します。

シャードを追加するとき、すべてではなく 2 つの「隣接」だけを調べ、平均して 1/n だけシフトします。

シャードを削除するときは、削除されるシャードのみを確認し、シャードのみをシフトします。ある意味最適。

シャードを追加する際のトラフィックを最小限に抑えるという点では非常に効果的ですが、通常のデータバランシングという点ではまったく不快です。多数のマシンに分散するこれらすべてのオブジェクトをハッシュするとき、比較的不均等に処理するためです。円の周りの点の間隔は不均等であり、特定の各ノードの負荷は残りのノードと大きく異なる可能性があります。

この問題は、仮想ノードの最後の行によって解決されます。円上の各ノード、各サーバーは複数の点で示されます。サーバーやシャードなどを追加することで、いくつかのポイントが追加されます。何かを削除するたびに、それに応じていくつかのポイントが削除され、データの小さな部分がシフトされます。

私がこの空間について円で話しているのは、たとえばそのような計画が Cassandra の内部にあるからです。つまり、彼女がノード間でレコードを追跡し始めたとき、サークルがあなたに注目しており、おそらく承認していないことを知ってください。

ただし、最初の方法と比較すると、作業は改善されました。シャードを追加または削除するときに、すべてのレコードではなく一部のレコードだけを調べ、一部だけをシフトします。

注意してください。問題は、さらに改善できるかどうかです。また、シャードの読み込みの均一性も向上しますか? 彼らはそれが可能だと言います！

もっと楽しくその4。ランデブー/HRW

次の簡単なアイデア (教材は教育的なものなので、複雑なことは何もありません): shard_id = arg max hash(object_id, shard_id)。

なぜランデブーハッシュと呼ばれるのかはわかりませんが、最高ランダム重みと呼ばれる理由はわかります。次のように視覚化するのは非常に簡単です。

たとえば、16 個のシャードがあります。どこかに配置する必要があるオブジェクト (文字列) ごとに、シャード番号からオブジェクトに応じて 16 個のハッシュを計算します。最も高いハッシュ値を持つ人が勝ちます。

これはいわゆる HRW ハッシュ、別名ランデブーハッシュです。棒のように愚かですが、シャードの数を計算するスキームは、第一に、円よりも目に優しく、その一方で均一な負荷を与えます。

唯一のマイナス点は、新しいシャードを追加したことで状況が悪化したことです。新しいシャードを追加するときに、一部のハッシュが変更される可能性があり、すべてを確認する必要がある可能性があります。破片除去技術はあまり変わっていません。

もう 1 つの問題は、シャードの数が多いため計算量が重いことです。

もっと楽しいその5。その他のテクニック

興味深いことに、研究は止まっておらず、Google は毎年いくつかの新しい宇宙技術を発表しています。

ジャンプハッシュ - Google '2014。
マルチプローブ - Google '2015。
マグレブ - Google '2016。

このテーマに興味があれば、たくさんの論文を読むことができます。私がこのデータを提示するのは、問題はまだ解決されておらず、すべてのデータベースに実装できる超解決策は存在しないことを明確にするためです。今まで人々は論文を擁護してきた。

結論

ガリウスジュリアスシーザーの「分割して支配、支配して分割!」にちなんで名付けられたシャーディングと呼ばれる重要な基本テクニックがあります。データが 1 台のサーバーに収まらない場合は、20 台のサーバーに分割する必要があります。

ここまでのことを学べば、シャーディングしないほうが良いという印象を受けるはずです。シャーディングしない方が良いと判断した場合は、これが正しい感覚です。100 ドルでサーバーにメモリを追加でき、何もシャード化しないのであれば、そうすべきです。シャーディングすると、データを前後に転送し、どこにデータを積み重ねるかわからない複雑な分散システムが出現します。避けられるものなら避けなければなりません。

それを手動で行わない方が良いです。「ベース」(検索、DFS など) 自体がシャード化できる方が良いです。いずれにせよ、遅かれ早かれ高負荷が発生し、何らかの方法でデータを分割する必要があります。基地自体ができても、何も問題がないわけではありません。アルゴリズム原理主義について思い出してください。すべてが内部でどのように機能するかを理解する必要があります。

初めてシャーディングを設定するときは、F() を慎重に選択し、リクエストやネットワークなどについて考慮してください。ただし、準備をしてください。おそらく 2 回選択する必要があり、少なくとも 1 回はすべてをやり直す必要があります。