データベースはなぜ、どのようにして分散されるのでしょうか?

[[414284]]

データベース分野でチューリング賞を受賞したジム・グレイ氏はかつてこう言いました。「すべてのストレージ システムは、最終的にはデータベース システムへと進化するでしょう。」

数十年にわたる進化を経て、分散データベースは近年急速に発展しました。国内外で多くの分散データベースのスタートアップ企業が登場しています。分散データベースが普及したのはなぜでしょうか?コンピュータの歴史の中で、何百ものデータベース システムが存在してきました。分散データベースはなぜ必要なのでしょうか?

分散データベースに移行する理由

データベース開発の歴史をたどり、分散データベースがなぜ登場したのかを見てみましょう。

1960年代: 最初のデータベース

1961 年、チャールズ・バックマンらが最初のコンピュータ データベース管理システム (DBMS) を設計しました。このネットワーク モデル データベースは IDS (Integrated Data Store) と呼ばれていました。その後まもなく、1968 年に IBM は階層モデル データベース IMS (Information Management System) を開発しました。どちらのデータベースも実験的な先駆者です。

ネットワーク モデルであれ階層モデルであれ、初期のデータベースは非常に使いにくく、今日私たちが慣れている機能の多くは備えていませんでした。

SQL はもちろんテーブルもありません。

データは大まかに格納されており、クエリを実行するにはポインターを介してデータ構造全体を走査する必要があります。

論理層と物理層は分離されておらず、独立したスキーマは存在しません。属性を追加するには、すべてのデータを再ロードしてから転送する必要があります。

元のデータベースはデータを独立して保存せず、抽象化もされていなかったため、開発者はそれを使用するために多大な労力を費やす必要がありました。

1970年代: リレーショナル データベース

1970 年代、IBM の研究者である Edgar Frank Codd は、周囲のプログラマーが毎日、クエリの処理、スキーマの変更、データの保存方法の検討に多くの時間を費やしていることに気づき、今日知られているリレーショナル モデルを作成しました。

リレーショナル モデルが確立された後、IBM は、SQL とトランザクションを実装した最初の DBMS である有名な System R に関する特別な研究を開始しました。 System R の設計は、その後のさまざまなデータベースに良い影響を与えました。

リレーショナル モデルは、クエリとデータ ストレージ間の密接な結合を排除します。クエリはストレージから独立しており、データベースはバックグラウンドで自由に最適化できます。プログラマーは、その背後にあるストレージ方法を知る必要はなく、SQL を介してデータベースと対話するだけでよいため、開発者にとって非常に使いやすいです。

Oracle は 1978 年にリリースされ、商用データベースの火付け役となりました。

20世紀後半: 成熟

その後数十年にわたり、データベースは成長期に入り、徐々に成熟していきました。初期の階層モデルやネットワークモデルは消滅し、リレーショナルデータベースが主流になりました。 SQL はデータベースの標準クエリ言語となり、現在でも使用されています。

データベースの商用化がますます進み、PostgreSQLやMySQLなどのオープンソースデータベースも登場し始めています。大規模な商用データベースは非常に高価であるため、一部のインターネット企業は代替手段として MySQL などのオープンソース データベースを使い始めています。

2000年代: NoSQL

21 世紀の初めにインターネットが繁栄し、突然多くの企業がより多くのユーザーをサポートする必要があり、24 時間 365 日サービスを実行する必要が生じました。このため、インターネット企業は複数のコンピューターにデータを複製し、分割する必要がありました。

シャードストレージとは、特定のキーワードに従ってテーブルを複数のシャードに分割することです。たとえば、年ごとに分割すると、2000 年のデータは最初のマシンに保存され、2001 年のデータは 2 番目のマシンに保存されます。これは通常、データベース管理者によって実行されます。同時に、アプリケーションがコードを変更したり認識したりすることなくシャード データを読み書きできるようにするには、これらのシャードの前にミドルウェアを配置して、アプリケーションの元の SQL をシャーディングをサポートする SQL に変換する必要があります。下の図の通りです。

もちろん、このタイプのソリューションには次のような欠点もあります。

• クロスシャードトランザクションはサポートされていません。
• リシャーディングは難しく、データベース管理者にとっては悪夢になる可能性があります。

Google などの企業は、より多くのユーザーにサービスを提供するために、より大規模なアプリケーションを構築する必要があるため、どんな犠牲を払ってでもスケーラビリティを実現するために、このようにデータベースを分割しています。これらはすべてスケーラビリティの追求です。

この目的のために、これらの企業はリレーショナル モデル、トランザクション、およびデータ一貫性の保証を放棄した NoSQL も開発しました (一部の NoSQL は結果的一貫性のみを保証します)。

前述したように、1970 年代に、エドガー・フランク・コッドは開発者の精神的負担を軽減するためにリレーショナル データベースを設計しました。 NoSQL はアプリケーションに必要なスケーラビリティを解決しましたが、それは過去に戻ってしまったようです。プログラマーは、NoSQL 機能が不十分であるという問題に直面する必要があります。つまり、Jim Gray 氏が言ったように、「すべてのストレージ システムは最終的にデータベース システムへと進化する」ということです。

2010年代: 分散データベース

分散データベースを構築する理由は何ですか?これまでの開発分析から、既存のデータベース ソリューションが開発者と管理者に過度の負担をかけていることは明らかです。新しい大規模プロジェクトを開始する場合、単一のデータベースを選択すると将来のスケーラビリティが犠牲になり、NoSQL を選択すると開発者に問題解決の余分な負担がかかり、トランザクションなどの優れた機能がサポートされない可能性があります。

分散データベースは、両方の利点を組み合わせて、両方の長所を兼ね備えたシステムを構築しようとします。つまり、完全なリレーショナル モデルをサポートしながら、高いスケーラビリティと可用性を実現できます。分散データベースは、多くの場合、NewSQL または分散 SQL と呼ばれます。呼び名に関係なく、複数のマシンで実行されるデータベースを指します。

これは、NoSQL がまったく役に立たないということではありません。実際、NoSQL で多くの成功したシステムが構築されていますが、NoSQL ははるかに困難です。 Google の分散データベース Spanner の論文には次のような一文があります。

常にトランザクション不足を念頭にコーディングするよりも、ボトルネックが発生したときにトランザクションの過剰使用によるパフォーマンスの問題にアプリケーション プログラマが対処する方がよいと私たちは考えています。

翻訳: 「開発者に常にトランザクション不足を念頭に置いたコードを書くように求めるよりも、トランザクションの過剰な使用によって生じるパフォーマンスの問題をアプリケーション開発者が解決できるようにした方がよいと考えています。」

つまり、トランザクションがパフォーマンスに影響を与えるかどうかはビジネス開発者が考慮する必要があり、データベースとしては、さまざまなアプリケーションの共通のニーズを満たすトランザクション メカニズムを提供する必要があります。

Spanner の論文が発表された後、CockroachDB、TiDB、YugabyteDB、そして最近オープンソースとなった OceanBase など、多くの優れたオープンソース分散データベースが登場し始めました。

データベースの歴史を振り返ると、分散データベースがなぜ登場したのかがわかります。ここで、分散データベースを実装する方法に焦点を当てる必要があります。

分散データベースの実装方法

1. 私たちが注力する分散データベース:
2. データがマシン間でどのように分散されるか。
3. データレプリカの一貫性を維持する方法。
4. SQL をサポートする方法。

分散トランザクションを実装する方法。

もちろん、この記事では分散データベースの単純な原理について簡単に説明するだけであり、詳細についてはあまり触れません。より深く学びたい方は、ソースコードの勉強に加え、著者の公式アカウントや、著者が下半期に出版する本に注目すると良いでしょう。

データ配信

NewSQL と NoSQL のデータ分布は似ています。両者とも、すべてのデータを 1 台のマシンに保存するのは適切ではなく、シャードに保存する必要があると考えています。そこで次の点を考慮してください。

破片をどうやって分割するのでしょうか?

特定のデータを見つけるにはどうすればいいですか?

シャーディングには、ハッシュと範囲という 2 つの主なアプローチがあります。

ハッシュ シャーディングは、ハッシュ関数を使用してキーワードのハッシュ値を計算し、ハッシュ値に基づいてデータを保存する場所を決定します。これの利点は、データを簡単に見つけられることです。データがどのマシンに保存されているかを知るには、ハッシュ関数を実行するだけで済みます。しかし、欠点も非常に明白です。ハッシュ関数はランダムなので、データは範囲クエリをサポートしません。

範囲シャーディングとは、データの保存場所を特定の範囲に従って分割することを指します。たとえば、データは最初の文字に従って AZ から 26 個のパーティションに分割されます。このシャーディング方法は、範囲クエリに非常に便利です。欠点は、データがどのノードにあるかを知るために通常はキーワードをクエリする必要があり、パフォーマンスが低下するように見えることですが、範囲はほとんど変更されないため、範囲情報をキャッシュするのは簡単です。

たとえば、下の図に示すように、キーワードを [a で始まる、h で始まる)、[h で始まる、p で始まる)、[p で始まる、無限大) の 3 つの範囲に分割します。

下の図に示すように、これにより範囲クエリがより効率的になります。

最後に気になるのは、シャードのデータが大きすぎて設定したしきい値を超えた場合に、どのようにシャードを拡張するかということです。変換を実行する中間層があるため、これも簡単に実行できます。既存の範囲内のポイントを選択し、その範囲を 2 つに分割して 2 つのパーティションを取得するだけです。

下の図に示すように、pz のデータ量が閾値を超えると、負荷の圧迫を避けるために範囲を分割します。

明らかに、ここではトレードオフがあります。範囲しきい値を非常に大きく設定すると、マシン間でのデータの移動が遅くなり、障害が発生したマシンからデータを迅速に回復することが難しくなります。ただし、範囲しきい値を非常に小さく設定すると、中間変換レイヤーが急速に大きくなり、クエリのオーバーヘッドが増加し、データが頻繁に分割される可能性があります。一般的な範囲のしきい値は 64 MB ～ 128 MB です。 CockroachDB は 64 MB を使用し、TiDB のデフォルトのしきい値は 96 MB です。

データの一貫性

名前に「分散」という言葉が含まれるシステムは、当然ながらエラーを許容する必要があります。マシンに障害が発生した後にデータが完全に失われるのを防ぐため、通常、データは冗長ストレージとして複数のマシンにコピーされます。しかし、分散システムでは、リクエストが失われたり、マシンがクラッシュしたり、ネットワークが遅延したりする可能性があるため、冗長コピー内のどのデータが最新であるかを知る方法が必要です。

データを複製する最も一般的な方法は、マスター スレーブ同期 (またはコールド スタンバイ データを直接コピーする) であり、マスター ノードが更新操作をスレーブ ノードに同期します。ただし、これにより、データの不整合の問題が発生する可能性があります。同期更新操作が失われた場合はどうなりますか?スレーブノードが書き込みに失敗した場合はどうなりますか?場合によっては、これらのエラーによってデータが永久に損傷し、データベース管理者の介入が必要になることもあります。

一貫性を維持するには、多くの場合、パフォーマンスが犠牲になります (これについては後で説明します)。そのため、ほとんどの NoSQL では、最終的な一貫性のみを保証し、いくつかの競合処理スキームを通じてデータの不整合を解決します。

多くの名詞は説明されていません。わからない名詞が多くて、もっと知りたいという方は、ぜひ私の公式アカウントをフォローするか、今年後半に出版予定の新刊を楽しみにお待ちください。

既存のよく知られたデータ複製アルゴリズムには、よく耳にする Paxos、Raft、Zab、Viewstamped Replication などがあります。その中で、Google が本番環境のニーズを満たす Paxos アルゴリズムを実装するまでに数年かかりました。 Raft は新星です。これは、スタンフォード大学の博士課程の学生である Ongaro Diego 氏が Paxos をベースに設計した、より理解しやすいコンセンサス アルゴリズムです。 Raft は誕生以来、分散コンセンサスアルゴリズムの分野を席巻してきました。現在、Github で Raft のオープンソース実装を多数見つけることができます。信頼性の高いデータ複製を実現するために、それらをアプリケーションに複製します (実際にはこれを行わないでください)。

Raft は本当に使いやすいとは言えないかもしれませんが、一貫性のあるシステムを書くのがこれまで以上に簡単になりました。具体的なアルゴリズムの詳細についてはここでは説明しません。興味のある学生は、前回の記事「Raft コンセンサス アルゴリズムの詳細な分析」を読むことができます。

つまり、Raft アルゴリズムでは、半分以上のノードが正常に書き込みを行うだけで済みます。つまり、書き込み操作は成功したとみなされ、結果がクライアントに返されます。障害が発生した場合、Raft アルゴリズムはリーダーを再選出することができ、ノードの半分未満に障害が発生している限り、Raft は正常に動作します。

Raft アルゴリズムは信頼性の高いデータ複製を保証し、システムはノード障害の半分以下しか許容できません。

分散データベースでは、シャードはコンセンサス グループを使用してデータを複製します。特定の Raft コンセンサス グループは Raft グループと呼ばれ、Paxos コンセンサス グループは Paxos グループと呼ばれます。

TiDB公式サイトから写真を見つけました。 TiDB ではシャードをリージョンと呼びます。図に示すように、3 つのリージョンでデータを複製するために使用される 3 つの Raft グループがあります。

画像の著作権侵害

ソフトウェア エンジニアリングには特効薬はありません。コンセンサス アルゴリズムを使用する場合でも、メンバーシップの変更、範囲パーティションの変更、線形一貫性の実現など、多くの生成上の問題に対処する必要があります。これらの問題は克服されなければなりません。ただ、今はしっかりとした学術的サポートがあり、それをこのように再現するのが正しいのです。

SQL テーブルデータ KV ストレージ

KV ストレージの問題を解決した後も、KV 構造を使用してテーブル構造を保存する方法を見つける必要があります。通常、追加、削除、クエリ、変更は、次の 5 つの KV 操作に抽象化できます (さらに多い場合もありますが、基本的にはこれらです)。

 Get(キー)
 Put(キー、値)
 ConditionalPut(キー、値、式)
スキャン(開始キー、終了キー)
 Del(キー)

ここで説明する OLTP タイプの分散データベースはすべて行ベースです。 CockroachDB を例に挙げてみましょう。表には通常、行と列が含まれます。テーブルは次の構造に変換できます。

 /<テーブル>/<インデックス>/<キー>/<列> -> 値

読みやすくするために、フィールドを区切るにはスラッシュを使用します。 / / / この部分は、各テーブルに主キーが必要であることを示します。これはあまり直感的ではありません。たとえば、次のテーブル作成ステートメントの場合:

作成する 表テスト（
    id整数 主要な 鍵、
名前     VARCHAR 、
    価格FLOAT 、
 );

KV ストレージへの変換を図に示します。

もちろん、この保存方法では、float などのすべての型が文字列型に変換されます。

さらに、データベースは通常、いくつかの非主キー インデックスを作成します。これらは主に次の 2 つのカテゴリに分類されます。

• ユニークインデックス
• 非一意インデックス

ユニークインデックスは比較的単純です。値は一意なので、次のマッピングを使用できます。

 /<テーブル>/<インデックス>/<キー> -> 値

図に示すように:

非一意インデックスは、値が空であることを除いて主キーに似ています。図に示すように:

上記の表のデータの KV ルールはやや古くなっています。 CockroachDB の最新のマッピング ルールについては、CockroachDB SQL の構造化データ エンコーディングを参照してください。しかし、考え方は似ています。

もちろん、KV テーブル データを取得する方法は複数あります。 TiDB は次のルールに従ってマッピングします。

この方法では、各列を個別に保存しません。方法は同様であり、ここでは詳細は説明しません。 「TiDB の技術的な内部事情を理解するための 3 つの記事 - コンピューティングについて語る」を参照してください。

分散トランザクション

トランザクションについて話すときは、常に ACID について話します。分散トランザクションで確保するのが最も難しいのは、原子性と独立性です。分散システムでは、アトミック性には 2 フェーズ コミットなどのアトミック コミット プロトコルが必要ですが、分離は 2 フェーズ ロックまたはマルチバージョン同時実行制御 (MVCC) を通じて実現され、さまざまな分離レベルを実現できます。

すべての分散データベースは MVCC を実装しています。 Google Spanner はこれを実装するために TrueTime を設計しましたが、TrueTime はオープンソースではありません。 TiDB は Google Percolator をベースにしています。 Cockroach の分散トランザクションの実装は比較的複雑で、多くの新しい要素が含まれていますが、これについては後で詳しく説明します。

スペースの制約により、分散トランザクションについては以降の説明で重点的に取り上げることとし、ここでは詳しく説明しません。

結論

最後に、分散データベースの簡単なアーキテクチャを下図に示します。

オープンソースは人類に利益をもたらします。今日では、多くの優れたオープンソース分散データベースが登場しています。それらはすべて良い学習教材です。著者は、今後の記事で CockroachDB、TiDB、YugabyteDB、OceanBase の技術的な詳細を引き続き紹介する予定です。これらのオープンソース開発者に感謝します。

データベース分野でチューリング賞を受賞した学者は多くないことは特筆に値します。マスターは全部で 4 人います: チャールズ・バックマン、エドガー・フランク・コッド、ジム・グレイ、マイケル・ストーンブレーカーです。この記事では、最初の 3 つについて説明します。 2020年のチューリング賞を受賞したジェフリー・ウルマン氏は、データベース分野でも功績を残していますが、データベース分野ではなく、プログラミング言語分野（「ドラゴンブック」）での業績に対して受賞しました。学術分野、産業分野を問わず、分散＋データベースがさらに発展することを心から願っております！

この記事はWeChatの公開アカウント「Duo Ketang」から転載したものです。下のQRコードからフォローできます。この記事を転載する場合は、Duoketangの公式アカウントまでご連絡ください。