シャーディング

1.1 シャーディングとは何ですか?

しつこくグーグルで検索すると、いわゆるパーティショニングといわゆるシャーディングの間にはかなり曖昧な境界があることがわかります。誰もが自分の好きなように、好きなように電話をかけます。水平パーティショニングとシャーディングを区別する人もいます。シャーディングはある種の水平分割であるという人もいます。

建国の父たちによって承認され、ISO によって認定されるような用語標準は 1 つも見つかりませんでした。個人的な内なる信念は次のようなものです。平均すると、分割は恣意的な方法で「ベースをばらばらに切断する」ことです。

• 垂直パーティション化- 列ごと。たとえば、60 列に数十億件のレコードが含まれる巨大なテーブルがあります。このような巨大なテーブルを 1 つ保持する代わりに、それぞれ 20 億レコードの巨大なテーブルを少なくとも 60 個保持します。これは列ベースではなく、垂直パーティション化です (用語の例として)。
• 水平分割- おそらくサーバー内で、行ごとにカットします。

ここで厄介なのは、水平パーティショニングとシャーディングの微妙な違いです。切り刻まれることはありますが、それが何であるかはわかりません。シャーディングと水平パーティショニングはほぼ同じものであるように感じられます。

シャーディングとは一般に、データベースまたはドキュメントのプロコレクションという観点から大きなテーブルが、データベースがなくてもドキュメント ストアがある場合はオブジェクトがオブジェクトごとに正確に分割されることです。つまり、20 億個のオブジェクトから、サイズに関係なくピースが選択されます。各オブジェクト内のオブジェクト自体は分割されず、別々の列にレイアウトされません。つまり、異なる場所にまとめてレイアウトされます。

用語には微妙な違いがあります。たとえば、比較的言えば、Postgres 開発者は、メイン テーブルが分割されているすべてのテーブルが同じスキーマ内にある場合が水平パーティショニングであり、異なるマシン上にある場合、これはすでにシャーディングであると言えます。

一般的な意味では、特定のデータベースや特定のデータ管理システムの用語に縛られることなく、シャーディングとは単に行ごと/ドキュメントごとなどをスライスするだけである、それだけであるという感覚があります。

典型的なことを強調します。これは、20 億のドキュメントを 20 のテーブルに分割し、それぞれのテーブルをより管理しやすくするためだけではなく、ドキュメントを多くのコア、多くのディスク、または多くの異なる物理サーバーまたは仮想サーバーに分散するために行っているという意味です。

1.2 分割できないものを分割する

これは、各シャード (データの各部分) が何度も複製されるようにするためであると理解されています。しかし、実際はそうではありません。

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

実際、このようなデータのスライスを実行すると、勇敢なラップトップ上の MySQL 上の 1 つの巨大な SQL テーブルから、1 台のラップトップ、単一のスキーマ、単一のデータベースなどを超えることなく 16 個の小さなテーブルが生成されます。 。等々。- 以上です。シャーディングはすでにあります。

その結果、次のような結果が得られます。

• 帯域幅が増加します。
• レイテンシは変化しません。つまり、この場合は、いわば各ワーカーまたはコンシューマが独自のレイテンシを取得します。さまざまなリクエストがほぼ同時に処理されます。
• またはその両方、およびもう 1 つ、そして高可用性 (レプリケーション)。

なぜ帯域幅があるのでしょうか? 場合によっては、1 つの上に収まらないデータ量が存在することがあります。場所は明確ではありませんが、収まりません。ディスク | サーバー | ...}。リソースが足りない、それだけです。この大規模なデータセットを操作するには、データセットを切り取る必要があります。

なぜレイテンシーが発生するのでしょうか? 1 つのコアで 20 億行のテーブルをスキャンする場合、20 コアで 20 のテーブルを並行してスキャンするよりも 20 倍遅くなります。単一リソースではデータの処理が遅すぎます。

なぜ高可用性なのか? または、両方を同時に実行するためにデータをカットし、同時に各シャードの複数のコピーを作成します。レプリケーションにより高可用性が確保されます。

1.3 簡単な例「手動で行う方法」

条件付きシャーディングは、32 個のドキュメントのテスト テーブル test.documents を使用して切り出し、このテーブルから 16 個のテスト テーブル (各 test.docs00、01、02、...、15 あたり約 2 個のドキュメント) を生成できます。

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

なぜですか？ID がどのように配布されるか先験的にわからないため、1 から 32 までの場合、それぞれちょうど 2 つのドキュメントが存在しますが、それ以外の場合は存在しません。

なぜここでそれを行うのか。16 個のテーブルを作成したら、必要なものを 16 個「取得」できます。何がヒットしたかに関係なく、これらのリソースを並列化できます。たとえば、十分なディスク領域がない場合は、これらのテーブルを別のディスクに分解することが合理的です。

残念ながら、これらはすべて無料ではありません。正規の SQL 標準 (長い間 SQL 標準を読み返していないので、長い間更新されていないのかもしれません) の場合、どの SQL サーバーに対しても使用できる公式の標準化された構文は存在しないのではないかと思います。 : 「SQL サーバー様、32 個のシャードを作成し、4 つのディスクに分割してください。ただし、個々の実装では、基本的に同じことを実行するための特定の構文が存在することがよくあります。PostgreSQL にはパーティショニングのメカニズムがあり、MySQL には MariaDB があり、Oracle はおそらくこれらすべてをずっと前に行っていました。

それにもかかわらず、データベースのサポートなしで、標準の枠組み内でそれを手作業で行う場合、条件付きでデータ アクセスの複雑さを支払うことになります。単純な SELECT * FROM document WHERE id=123 がありましたが、現在は 16 x SELECT * FROM docsXX です。そして、キーごとにレコードを取得しようとすると良いでしょう。初期の範囲のレコードを取得しようとしている場合は、さらに興味深いことになります。ここで (強調しておきますが、私たちがいわば愚か者であり、標準の枠組み内に留まっているのであれば)、これら 16 個の SELECT * FROM の結果をアプリケーション内で結合する必要があります。

どのようなパフォーマンスの変化が期待できますか?

• 直感的に - 直線的です。
• 理論的には、アムダールの法則によりサブリニアです。
• 実際には、おそらくほぼ直線的ですが、そうではないかもしれません。

実は正解は不明です。シャーディング技術を賢く適用すると、アプリケーションのパフォーマンスが大幅に超線形に低下する可能性があり、DBA も白熱したポーカーで実行されるようになります。

これをどのように実現できるかを見てみましょう。設定を PostgreSQL shards=16 に設定しただけでは、自動的に起動するのは面白くないことは明らかです。シャーディングによる速度を 32 までに 16 回確実に遅くする方法を考えてみましょう。これは、これを回避する方法という観点からすると興味深いものです。

速度を上げたり下げたりする試みは、常に古典的な問題に遭遇します。古き良きアムダールの法則です。これは、どのようなリクエストにも完全な並列化はなく、常に何らかの一貫した部分があるというものです。

1.4 アムダールの法則

連載部分は必ずあります。

クエリ実行には、並列化される部分と並列化されない部分が常に存在します。完全に並列クエリであるように見えても、少なくとも、各シャードから受信した行からクライアントに送信する結果行のコレクションは常に存在し、常にシーケンシャルです。

必ず一貫した部分があります。それは小さい場合もあり、一般的な背景に対してまったく見えない場合もあり、巨大な場合もあり、したがって並列化に大きな影響を与えますが、常に存在します。

さらに、その影響力は変化しており、大幅に増大する可能性があります。たとえば、テーブルを 64 レコードから 4 レコードの 16 テーブルに削減する (賭け金を増やしましょう) とすると、この部分は変化します。もちろん、このような膨大な量のデータから判断すると、私たちは携帯電話と 2 MHz 86 プロセッサで作業しているため、同時に開いておくことができる十分なファイルがありません。どうやら、このような入力では、一度に 1 つのファイルを開くことになります。

• それは合計 = シリアル + パラレルでした。たとえば、並列は DB 内のすべての作業であり、シリアルは結果をクライアントに送信します。
• Total2 = Serial + Parallel/N + Xserialになりました。たとえば、全体の ORDER BY、Xserial>0 の場合。

この簡単な例では、Xserial が表示されることを示しています。シリアル化された部分が常に存在するという事実、およびデータを並行して処理しようとしているという事実に加えて、このデータ スライスを提供する追加の部分があります。大まかに言えば、次のものが必要になる場合があります。

• データベースの内部辞書でこれらの 16 のテーブルを検索します。
• ファイルを開く。
• メモリを割り当てる。
• メモリの割り当てを解除します。
• 結果をマージします。
• コア間で同期します。

一部の非同期エフェクトが依然として表示されます。それらは重要ではなく、合計時間の 10 億分の 1 を占める場合もありますが、常にゼロではなく、常に存在します。彼らの助けを借りて、シャーディング後にパフォーマンスが大幅に低下する可能性があります。

これはアムダールの法則に関する標準的な図です。ここで重要なことは、理想的には真っ直ぐで直線的に成長するはずの線が漸近線に達するということです。しかし、インターネットからのグラフは判読できないため、私の考えでは、数字を含むより視覚的な表を作成しました。

リクエスト処理に 5% しかかからないシリアル化された部分があるとします ( serial = 0.05 = 1 / 20 )。

直感的には、リクエスト処理の 1/20 しかかからないシリアル化された部分で、20 コアのリクエスト処理を並列化すると、約 20 倍、最悪の場合は 18 倍高速になるように思えます。

実際、数学は非情なものです。

ウォール = 0.05 + 0.95/コア数、スピードアップ = 1 / (0.05 + 0.95/コア数)

注意深く計算すると、シリアル化部分が 5% である場合、速度向上は 10 倍 (10.3) になり、理論上の理想と比較して 51% であることがわかります。

これまで取り組んでいたタスクに 20 コア (お好みであれば 20 ディスク) を使用したとしても、理論的には 20 倍を超える加速が得られることはありませんが、実際にはそれよりはるかに低くなります。さらに、並列数が増加すると、非効率が大幅に増加します。

直列化された作業の 1% のみが残り、99% が並列化されると、速度向上値は若干改善します。

完全な熱核クエリの場合、当然のことながら完了までに何時間もかかり、準備作業と結果の組み立てにはほとんど時間がかかりません (シリアル = 0.001) ので、すでに良好な効率が見られます。

100% ということはありえないことに注意してください。特に良好な場合には、たとえば 99.999% が表示されますが、正確に 100% であるわけではありません。