きっとあなたは理解していないでしょう: 分散ストレージ システムにおける強力なデータ一貫性の課題

Google が Spanner の論文を発表して以来、データベースのスケーラビリティ問題を解決するために、国内外で関連するデータベース製品やサービスが立ち上げられています。 ByteDance は、膨大なデータ保存のニーズに直面した際にも、関連する技術的ソリューションを採用しました。この共有では、このようなシステムを構築するときに遭遇した問題、解決策、および技術の進化について紹介します。

1. 背景

インターネット製品には多くの種類のデータがあり、データの種類によって、ストレージ システムの一貫性、可用性、スケーラビリティに対する要件が異なります。たとえば、財務データやアカウント関連データには一貫性に対する要件が比較的高く、いいねなどのソーシャルデータには可用性に対する要件が比較的高くなります。

オブジェクト ストレージのインデックス レイヤー データなど、一貫性、スケーラビリティ、可用性に対する要件が高い大規模なメタデータ ストレージ シナリオもあります。これには、強力なデータ一貫性を確保しながら、基盤となるストレージ システムに優れたスケーラビリティが求められます。データ モデルに関しては、関係性などの一部のデータについては KV モデルで十分です。ウォレットやアカウントなどの一部のデータについては、テーブルなどのより豊富なデータ モデルが必要になる場合があります。

分散ストレージ システムでデータをパーティション分割する方法には、一般的にハッシュ パーティション分割と範囲パーティション分割の 2 つがあります。ハッシュ パーティション分割では、各データのハッシュ値を計算し、それを論理パーティションにマッピングしてから、別のマッピング レイヤーを通じて論理パーティションを特定のマシンにマッピングします。多くのデータベース ミドルウェアとキャッシュ ミドルウェアがこれを実行します。この方法の利点は、データの書き込み時にホットスポットがほとんど発生しないことです。欠点は、元々連続していたデータがハッシュ化されて異なるパーティションに分散された後、無秩序になってしまうことです。したがって、データの範囲をスキャンする必要がある場合は、すべてのパーティションをスキャンする必要があります。

これに対して、範囲パーティション分割では、データが範囲ごとにパーティション分割され、連続したデータは一緒に保存されます。必要に応じて隣接するパーティションを結合したり、パーティションを真ん中で切って 2 つに分割したりできます。業界の典型的なシステムは HBase のようなものです。このパーティショニング方法の欠点は次のとおりです。1. すべてのリクエストが最後のシャードにヒットし、最後のシャードがボトルネックになるため、追加書き込み処理には適していません。利点は、ホットスポットの問題に対処しやすくなることです。パーティションが過熱した場合、パーティションを分割して他のアイドル状態のマシンに移行できます。

実際の業務利用の観点から、強力なデータ一貫性を提供することで、業務にかかる負担を大幅に軽減できます。さらに、範囲パーティション分割はより豊富なアクセス モードをサポートし、より柔軟に使用できます。これらの考慮事項に基づいて、C++ の Range パーティションに基づく強力な一貫性を持つ KV ストレージ システム ByteKV を開発し、その上にテーブル インターフェイスのレイヤーをカプセル化して、より豊富なデータ モデルを提供しました。

2. アーキテクチャの紹介

1. システムコンポーネント

システム全体は主に、SQLProxy、KVProxy、KVClient、KVMaster、PartitionServer の 5 つのコンポーネントに分かれています。このうち、SQLProxy は SQL リクエストへのアクセスに使用され、KVProxy は KV リクエストへのアクセスに使用されます。どちらも KVClient を介してクラスターにアクセスします。 KVClient は、KVMaster および PartitionServer との対話を担当します。 KVClient は、KVMaster からグローバル タイムスタンプやレプリカの場所などの情報を取得し、対応する PartitionServer にアクセスしてデータの読み取りと書き込みを行います。 PartitionServer はユーザー データの保存を担当し、KVMaster は PartitionServer 間でクラスター全体のデータをスケジュールする役割を担います。

クラスター内のデータは、範囲に応じて多数のパーティションに分割されます。各パーティションには複数のコピーがあり、コピー間の一貫性は Raft によって保証されます。これらのレプリカはすべての PartitionServer に分散されます。各 PartitionServer にはパーティションの複数のコピーが保存されます。 KVMaster は、すべてのレプリカを各 PartitionServer に均等に配置する役割を担います。

各 PartitionServer は、独自に保存されているレプリカの情報を KVMaster に定期的に報告し、KVMaster がグローバルなレプリカの場所情報を持つようにします。 SDK 要求を受信すると、プロキシは KVMaster にアクセスしてレプリカの場所情報を取得し、要求を特定の PartitionServer にルーティングします。同時に、プロキシはレプリカの位置情報の一部をキャッシュし、その後の迅速なアクセスを可能にします。レプリカは PartitionServer 間でスケジュールされるため、プロキシによってキャッシュされた情報は古くなっている可能性があります。このとき、PartitionServer がレプリカの場所が変更されたことをプロキシに応答すると、プロキシは KVMaster にレプリカの場所情報を再度要求します。

2. 階層構造

上図はByteKVの階層構造を示しています。

インターフェース レイヤーは、ユーザーに KV SDK と SQL SDK を提供します。 KV SDK はシンプルな KV インターフェイスを提供し、SQL SDK はさまざまなビジネスのニーズを満たすより豊富な SQL インターフェイスを提供します。

トランザクション レイヤーは、グローバルに一貫したスナップショット分離レベル (スナップショット分離) を提供し、グローバル タイムスタンプと 2 フェーズ コミットを通じてトランザクションの ACID プロパティを保証します。

弾性スケーリング レイヤーは、パーティションの自動分割とマージ、および KVMaster のさまざまなスケジューリング戦略を通じて強力な水平拡張機能を提供し、さまざまな段階でのビジネスのリソース要件に適応できます。

一貫性プロトコル層は、自社開発の ByteRaft コンポーネントを通じて強力なデータ一貫性を確保し、さまざまなリソース配分状況に適応するためのさまざまな展開ソリューションを提供します。

ストレージ エンジン レイヤーでは、業界で成熟したソリューションである RocksDB を使用して、初期段階での迅速な反復のニーズに対応します。システムの将来の進化のニーズに合わせて、独自の専用ストレージ エンジン BlockDB を設計しました。

スペース管理レイヤーは、システムのストレージ スペースの管理を担当します。データは物理マシンのローカル ディスクに保存することも、他の共有ストレージに接続して統合管理することもできます。

3. 外部インターフェース

1. KVインターフェース

ByteKV は、名前空間とテーブルという 2 つの抽象化レイヤーを提供します。名前空間には複数のテーブルを含めることができます。特にテーブルの場合、単一のレコードに対する Put、Delete、および Get セマンティクスをサポートします。 Put は CAS セマンティクスをサポートします。つまり、現在のキーが存在しない場合にのみレコードを書き込む、現在のレコードが特定のバージョンである場合にのみレコードを書き込むなど、特定の条件が満たされた場合にのみレコードが書き込まれます。また、TTL セマンティクスもサポートします。削除も同様です。

これらの基本インターフェイスに加えて、複数のレコードに対するアトミック書き込みインターフェイスである WriteBatch、分散一貫性スナップショット読み取りである MultiGet、非トランザクション書き込みである MultiWrite、データの範囲をスキャンする Scan などの高度なインターフェイスも提供します。 WriteBatch はアトミック性の保証を提供できます。つまり、すべての書き込みがすべて成功するか、すべて失敗するかのいずれかになりますが、MultiWrite はアトミック性の保証を提供しないため、可能な限り多くの書き込みのみが成功します。

MultiGet は、分散一貫性スナップショット読み取りセマンティクスを提供します。MultiGet は、他のコミットされたトランザクションの部分的な変更を読み取りません。スキャンは、一貫性のあるスナップショット読み取りのセマンティクスも実装し、プレフィックス スキャンやリバース スキャンなどの機能をサポートします。

2. テーブルインターフェース

テーブル インターフェイスは、KV に基づくより豊富な単一テーブル操作セマンティクスを提供します。ユーザーは、基本的な Insert、Update、Delete、Select SQL ステートメントを使用してデータの読み取りと書き込みを行うことができ、クエリでフィルタリング (Where/Having)、並べ替え (OrderBy)、グループ化 (GroupBy)、集計 (Count/Max/Min/Avg) などの句を使用できます。同時に、ユーザーのビジネスロジック実装を容易にするために、SDK 側で ORM ライブラリも提供しています。

4. 主要技術

1. 自社開発のByteRaft

分散システムであるため、災害復旧機能は不可欠です。冗長コピーは災害から回復するための最も効果的な方法ですが、複数のコピー間の一貫性の問題が伴います。

ByteKVは、複数のレプリカ間の一貫性を維持するために、基礎となるレプリケーションアルゴリズムとしてRaft[1]を使用します。 ByteKV は Range シャーディングを使用するため、各シャードは Raft レプリケーション グループに対応し、クラスター内には多数の Raft グループが存在します。 Raft グループ間のリソース利用関係を整理および調整することは、高性能なストレージ システムを実現するために不可欠です。同時に、Raft アルゴリズムの正しい実装に基づいて、上位層に対する柔軟な技術サポートにより、設計の難易度を効果的に低減できます。そこで、当社は業界の優れた実装に基づいて C++ Multi-Raft アルゴリズム ライブラリ ByteRaft を開発しました。

ログのレプリケーションは、Raft アルゴリズムの最も基本的な機能です。 ByteKV はすべてのユーザー書き込み操作を RedoLog にエンコードし、Raft リーダーを通じてすべてのレプリカに同期します。各レプリカは、同じシーケンスで RedoLog を再生することにより一貫性を保証します。 ByteKV を提供するマシンは、ハードウェア障害や停電などによりクラッシュする場合があります。クラスター内にレプリカの大多数がまだ生きている限り、Raft アルゴリズムは短時間で自動的に選挙を開始し、サービスを提供する新しいリーダーを選択できます。最も重要なのは、ByteKV レプリカ スケジューリングの基本的なサポートを提供する Raft アルゴリズムによって、動的なメンバーシップの変更もサポートされていることです。 ByteKV の KVMaster は、クラスター内のさまざまなマシンのリソース使用率に関する統計を収集し、レプリカを追加および削除することでデータの移行と負荷分散を実現します。さらに、KVMaster は定期的にマシンの状態をチェックし、長期間ダウンしているレプリカを元のレプリケーション グループから削除します。

ByteRaft は、オリジナルの Raft アルゴリズムに基づいて多くのエンジニアリングの最適化を行いました。異なる Raft グループ間でリソース利用を効果的に統合する方法が、効果的な Multi-Raft アルゴリズムを実装するための鍵となります。 ByteRaft は、さまざまな IO 操作パス上のリクエストをマージし、小粒度の IO リクエストを大きなブロックのリクエストにマージして、オーバーヘッドを単一の Raft グループと同じにします。同時に、複数の Raft グループを水平方向に拡張して、CPU コンピューティングと IO 帯域幅のリソースを最大限に活用できます。 ByteRaft ネットワークはパイプライン モードを採用しています。ネットワークが妨害されない限り、ログのレプリケーションは最大容量で実行されます。同時に、ByteRaft には、ネットワークと RPC フレームワークがデータ パケットの順序を保証しないという問題を解決するための、順序外キューが組み込まれています。 ByteRaft は、これから使用されるすべてのログをメモリ内に保持します。この機能により、不要な IO オーバーヘッドが大幅に削減され、同期の遅延も短縮されます。

ByteRaft はコンセンサス アルゴリズム ライブラリであるだけでなく、さまざまなシナリオへの迅速なアクセスを容易にする完全なソリューション セットも提供します。そのため、ByteKV で使用されるだけでなく、Byte 内の複数のストレージ システムでも使用されます。

上記の機能に加えて、ByteRaft は他のエンタープライズ シナリオに対する技術サポートも提供します。

1) 学習者

データ同期はストレージ システムに不可欠な機能です。 ByteKV は、トランザクション粒度の高いデータ サブスクリプション ソリューションを提供します。このソリューションにより、トランザクションが送信された順序でデータ サブスクリプションが生成されることが保証されますが、必然的にスケーラビリティが制限されます。 ByteRaft では、一部のシナリオにおけるデータ同期では、このような強力なログ順序の保証は必要ありません。このため、ByteRaft は学習者サポートを提供します。 Learner に基づいて、キー順に複製する緩い同期コンポーネントを設計しました。

同時に、学習者はログの提出に参加しないという特徴により、新しいメンバーは学習者として Raft グループに参加し、ログのギャップが大きくない場合に通常のフォロワーに昇格することができます。このプロセスにより、クラスターの可用性を低下させることなく、KVMaster のスケジューリング プロセスをスムーズにすることができます。

2) 証人

Byte 内では、ByteKV の主な展開シナリオは 3 つのセンターと 5 つのレプリカです。これにより、単一のコンピュータ ルームに障害が発生した場合でも、クラスターは引き続きサービスを提供できるようになります。ただし、この方法では多数のマシンが必要になります。さらに、一部のビジネス シナリオでは、2 つのコンピュータ ルームでの展開しか提供できません。したがって、クラスターの可用性を低下させることなくコストを削減するソリューションが必要です。 Witness は投票のみを行い、データを保存しないメンバーであるため、必要なマシン リソースが少なくて済むため、ByteRaft は Witness 機能を提供します。

Witness を使用すると、従来の 5 つのレプリカの展開シナリオで 1 つのレプリカを Witness に置き換えることができるため、可用性を低下させることなくマシン リソースを節約できます。コンピュータ ルームが 2 つしかない他のシナリオでは、サードパーティのクラウド サービスを少量レンタルし、Witness を展開して、3 つのセンターと 5 つのレプリカに相当する災害復旧機能を提供することもできます。より極端なシナリオ、たとえば企業にプライマリ データ センターとバックアップ データ センターがある場合、Witness を追加することでプライマリ データ センターとバックアップ データ センターの過半数の分散を変更できます。プライマリ データ センターとバックアップ データ センターが分離されている場合、少数のデータ センターは Witness を削除してクォーラム数を減らし、サービスを復元できます。

2. ストレージエンジン

1) ロックスDB

現在のほとんどのストレージ システムと同様に、RocksDB もスタンドアロン ストレージ エンジンとして使用します。一般的なストレージ エンジンとして、RocksDB は優れたパフォーマンスと安定性を提供します。 RocksDB は、基本的な読み取りおよび書き込みインターフェースの提供に加えて、さまざまなビジネス シナリオに対応するためのさまざまなオプションと機能も提供します。しかし、実際の運用では、RocksDB をうまく使用するのは簡単なことではありません。そこで、ここでいくつかの経験を共有します。

①テーブルプロパティ

テーブル プロパティは、頻繁に使用する機能です。 RocksDB 自体はいくつかの組み込み SST 統計を提供し、フラッシュ/コンパクション中に統計を収集するためのユーザー定義のテーブル プロパティ コレクターをサポートします。具体的には、テーブル プロパティを使用して次の問題を解決します。

• 当社のシステムでは、Range を使用してデータを分割します。範囲のデータ サイズが特定のしきい値を超えると、範囲は分割されます。これには、分割ポイントをどのように選択するかという問題が関係します。簡単な方法は、この範囲内のデータをスキャンし、データ サイズに基づいて分割ポイントとして中間点を見つけることですが、これにより大きな IO オーバーヘッドが発生します。したがって、テーブル プロパティ コレクターを通じてデータをサンプリングし、特定の数のデータ項目またはサイズごとにサンプリング ポイントを記録します。次に、分割するときに、これらのサンプリング ポイントに基づいて分割ポイントを推定するだけで済みます。
• マルチバージョン データのヒューリスティック ガベージ コレクションのプロセスも、テーブル プロパティのサンプリングを通じて実装されます。ストレージ エンジンでは、1 つのユーザー データが 1 つ以上の異なるバージョンのデータに対応する場合があります。テーブル プロパティ コレクターでバージョン データ エントリの数とユーザー データ エントリの数を収集しました。ガベージ コレクション プロセス中に、範囲のバージョン データ項目の数がユーザー データ項目の数とほぼ同じである場合、ほとんどのユーザー データには 1 つのバージョンしかないと想定し、この範囲のガベージ コレクションをスキップすることを選択できます。複数のバージョンを考慮することに加えて、ガベージ コレクションでは TTL の問題も考慮する必要があります。では、データをスキャンせずに、範囲に期限切れの TTL データが含まれているかどうかをどのように確認するのでしょうか?また、テーブル プロパティ コレクターでは、各データの有効期限を計算し、有効期限が異なるデータの数をパーセンテージとして記録します。次に、ガベージ コレクション プロセス中に、タイムスタンプが与えられると、特定の範囲に期限切れのデータがどれだけ含まれているかを推定できます。
• RocksDB には、圧縮の優先順位など、さまざまなビジネス シナリオに応じて圧縮戦略を調整できるパラメーターがいくつか用意されていますが、実際にはビジネスの種類は多様であり、単一の構成セットですべてのシナリオに対応することは困難です。現時点では、統計情報に基づいて圧縮に実際に「介入」することができます。たとえば、一部のデータ間隔では削除操作が頻繁に行われることが多く、その結果、多数の墓石が残ってしまいます。これらの墓石をクイック圧縮で削除できない場合、読み取りパフォーマンスに大きな影響が及び、対応するスペースを解放できなくなります。この問題に対処するために、上位層での統計情報（ゴミデータの割合など）に基づいて、迅速に検出し、プロアクティブに圧縮をトリガーして、タイムリーに処理します。

②遭遇した問題と解決策

上記の使用法に加えて、RocksDB を使用する際に遭遇する可能性のある落とし穴と解決策をいくつか紹介します。

• 削除されるデータがどんどん増えたり、大量のデータを削除したのに長い間スペースが解放されないといった問題に遭遇したことはありませんか? RocksDB の削除操作では、実際には墓石マーカーのみが書き込まれ、このマーカーは最下層に圧縮された場合にのみ破棄できることがわかっています。したがって、ここでの問題は、レイヤーが多すぎるか、各レイヤー間の拡大率が不合理であるため、上位レイヤーのトゥームストーンが下位レイヤーにプッシュされないことであると考えられます。この時点で、問題を解決するために level_compaction_dynamic_level_bytes パラメータをオンにすることを検討できます。
• イテレータのジッターによって発生するロングテール問題に遭遇したことがありますか?これは、イテレータが解放されるときにクリーンアップ作業を実行する必要があるためである可能性があります。解決するには、avoid_unnecessary_blocking_io をオンにしてみてください。
• 取り込みファイルによってジッター問題が発生したことはありませんか?ファイルの取り込みプロセス中、RocksDB は書き込みをブロックするため、ファイルの取り込みの一部のステップに長い時間がかかる場合は、明らかなジッターが発生します。たとえば、取り込みの SST ファイルが memtable と重複している場合、最初に memtable をフラッシュする必要があり、このプロセス中にデータを書き込むことはできません。したがって、このジッターの問題を回避するには、まず取り込むファイルが memtable と重複しているかどうかを判断します。その場合は、取り込み前にフラッシュし、フラッシュが完了した後に取り込みを実行します。このとき、取り込み前のフラッシュによって書き込みがブロックされないため、ジッターの問題は回避されます。
• あるレイヤーのファイルが次のレイヤーの 10,000 個のファイルで圧縮される状況に遭遇したことはありませんか?圧縮によってファイルを生成する場合、RocksDB は、将来の過剰な圧縮の問題を回避するために、このファイルと次のレイヤーの間にどの程度の重複があるかを事前に決定します。ただし、この判断は範囲削除には有効ではないため、範囲は非常に広いが実際のデータは非常に少ないファイルが生成される可能性があります。その後、このファイルを次のレベルに圧縮すると、多くのファイルが関係することになります。この圧縮には数時間かかる場合があり、その間にすべてのファイルを解放することはできず、ディスクがすぐにいっぱいになります。範囲削除が必要なシナリオは非常に限られているため、現在、範囲削除を、範囲のファイル削除 + スキャン + 削除の方法に置き換えています。この方法は範囲削除よりもコストがかかりますが、より制御可能です。圧縮フィルターによってさらなる最適化を実現できますが、実装は比較的複雑であるため、まだ検討していません。

スペースが限られているため、上記では誰もが遭遇する可能性のある問題と解決策の一部のみを取り上げています。これらはテクニックを使うというよりは「無力な行為」に近い。 RocksDB の実装方法に起因して多くの問題が発生するため、この方法でしか使用できません。 RocksDB を最適化しても、ローカルな調整しか行えません。結局のところ、RocksDB は汎用ストレージ エンジンであり、当社のシステム専用ではありません。そこで、システム全体の将来的な進化のニーズを考慮し、専用のストレージエンジン BlockDB を設計しました。

2) ブロックDB

① 機能要件

BlockDB が解決する必要がある中核的な要件は、データ シャーディングです。各ストレージ ノードには、数千または数万のデータ シャードが保存されます。現在、これらの単一ノードのすべてのシャードは RocksDB インスタンスに保存されています。この保管方法には次の欠点があります。

• 異なるデータ シャードのリソース使用を分離することはできません。これは、マルチテナントをサポートする上で特に重要です。
• 異なるデータ シャードのアクセス パターンを最適化することは不可能です。たとえば、一部のシャードでは書き込みよりも読み取りが多く、他のシャードでは読み取りよりも書き込みが多くなります。この場合、前者には読み取りに適した圧縮戦略を採用し、後者には書き込みに適した圧縮戦略を採用します。ただし、RocksDB インスタンスでは 1 つの戦略しか選択できません。
• 異なるデータ シャードに対する操作は、簡単に相互に影響を与える可能性があります。データ シャードに対する一部の操作では、RocksDB でのグローバル ロックが必要です (上記の取り込みファイルなど)。データ シャードの数が増えるほど、ロックの競争が激しくなり、ロングテールの問題に簡単につながる可能性があります。
• 異なるデータ シャードを混在させて保存すると、異なるビジネスのデータ シャードがプレフィックスによって区別されるため、不要な書き込み増幅が発生します。異なるデータ シャードのプレフィックスは大きく異なるため、書き込まれるデータの範囲は比較的離散的になります。圧縮プロセス中は、重複するデータが多数発生します。

RocksDB の列ファミリはある程度のデータセグメント化機能を提供できますが、数万のデータシャードには対応できません。さらに、データ シャーディングでは、シャード間の分割や結合などの特別な操作をサポートする必要があります。そのため、BlockDB はまずデータ シャーディングをサポートし、その後、データ シャーディングの上にリソース制御や適応型圧縮などの機能を追加します。

データシャーディングに加えて、トランザクションのオーバーヘッドも削減したいと考えています。トランザクション データを保存する現在の方法は、RocksDB のマルチバージョンの上に別のマルチバージョンのレイヤーを追加することと同じです。 RocksDB はシーケンスを使用して内部的にデータの異なるバージョンを区別し、圧縮中にスナップショット シーケンスに基づいて目に見えないガベージ データをクリアします。私たちのトランザクションは、RocksDB のタイムスタンプを使用してユーザー データのさまざまなバージョンを区別し、GC を使用してユーザーには見えないガベージ データをリサイクルします。両者のロジックは非常に似ており、現在のストレージ方法には明らかにある程度の冗長性があります。したがって、トランザクション ロジックの一部を BlockDB にプッシュすることで、一方では冗長性を削減し、他方ではエンジン層でのさらなる最適化を容易にすることができます。

マルチバージョン同時実行制御を使用するストレージ システムには共通の問題点があります。それは、頻繁な更新操作によってユーザー データのバージョンが多数生成されることです。範囲検索を実行する場合、各ユーザー データのすべてのバージョンをスキャンする必要があり、読み取りパフォーマンスに大きな影響を与えます。実際、ほとんどの読み取り要求では最新バージョンのデータのみが読み取られます。ストレージ層で新バージョンと旧バージョンを分離すると、これらの読み取り要求のパフォーマンスを大幅に向上できます。したがって、この問題は BlockDB でも設計されています。

②パフォーマンス要件

BlockDB は機能要件に加えて、高性能 SSD (NVMe など) のランダム IO 特性をさらに活用してコストを削減したいと考えています。 RocksDB データはファイル単位で保存されるため、圧縮の最小単位もファイルになります。ファイルが次のレイヤーと重複していない場合、圧縮により追加の IO オーバーヘッドを発生させることなく、ファイルを直接次のレイヤーに移動できます。ファイルが小さければ、次のレイヤーと重なる可能性も小さくなり、ファイルを直接再利用できる可能性も高くなると考えられます。

ただし、実際の使用では、ファイルが多すぎるとファイル システムに悪影響を与えるため、ファイルを特に小さく設定することはできません。この考えに基づいて、BlockDB ではデータをブロックに分割して保存しており、ブロックの粒度は 128 KB など、ファイルよりもはるかに小さくなっています。ここでのブロックは SST ファイル内のブロックと比較できますが、SST ファイル内のブロックは分割されているため、これらのブロックは個別に再利用できます。ただし、ブロックに格納すると、同じ範囲内のデータがディスク上のさまざまな場所に分散され、スキャン中に大量のランダム読み取りが必要になるため、範囲スキャンには適さない可能性があります。ただし、実際のテストでは、ブロック サイズが小さすぎず、非同期 IO が最適化されている限り、ランダム読み取りでもディスクのパフォーマンスを十分に発揮できます。

さらに、ディスク パフォーマンスをさらに最大化し、ファイル システムのオーバーヘッドを削減するために、BlockDB はブロック ストレージ用のブロック システムも設計しました。ブロック システムは軽量ファイル システムに似ていますが、データをブロック単位で保存します。ブロック システムは、既存のファイル システムに基づいて実装することも、ベア ディスク上に直接実装することもできます。この設計は、将来の SPDK へのアクセスと IO パスのさらなる最適化のための優れた基盤を提供します。

3. 分散トランザクション

インターフェースを紹介する際に、分散一貫性スナップショット読み取りを満たす ByteKV のアトミック WriteBatch と MultiGet について説明しました。 WriteBatch は、バッチ内のすべての変更が成功または失敗することを意味し、部分的な成功や部分的な失敗は発生しません。 MultiGet は、コミットされた他のトランザクションからの部分的なデータが読み取られないことを意味します。

ByteKV は通常、分散トランザクションを実装するために次のテクノロジを使用します。

• クラスターは、グローバルに増加する論理クロックを提供します。このモジュールを通じて各読み取りおよび書き込み要求にタイムスタンプが割り当てられ、それによってすべての要求にグローバルな順序が割り当てられます。
• キーが更新されるたびにシステム内に新しいバージョンが生成され、新しい書き込みが古い読み取りスナップショットに影響を与えないようにします。
• 書き込み要求プロセスに 2 フェーズ コミットを導入すると、書き込みを整然とアトミックにコミットできるようになります。

1) グローバルタイミングサービス

すべてのイベントを順序付けると、分散システムにおける多くの問題が簡素化されることは間違いありません。また、さまざまなシステムで、さまざまな物理クロック、論理クロック、ハイブリッド論理クロックが選択されることもよくあります。 ByteKV は、パフォーマンス、安定性、実装の難しさを考慮し、クラスター内のすべての読み取りおよび書き込みモジュールが使用するグローバルな増分タイムスタンプ割り当てを提供するインターフェイスを KVMaster サービスに実装します。このインターフェースにより、出力タイムスタンプがグローバルに一意かつ増分的であることが保証されます。

私たちがこのアーキテクチャを採用したのは、次のような理由からです。

• クロック分配ロジックは非常にシンプルで、スタンドアロンモジュールで提供しても安定した遅延と十分なスループットが得られます。
• Raft プロトコルを使用すると、クロック分配モジュールの高可用性を実現でき、単一のマシンの障害がシステム内の単一障害点になることは決してありません。

具体的な実装に関しては、クロックの安定性、効率性、使いやすさを確保するために、いくつかのエンジニアリングの取り組みと最適化も行いました。

• 同じクライアントのクロック ロジックがバッチ処理されるため、RPC の数を効果的に削減できます。
• クロック配布では、他の RPC 要求からの干渉を避けるために、独立した TCP ソケットを使用する必要があります。
• クロック配布では、アトミック操作を使用してロックの使用を完全に回避します。
• クロックは実際の物理時間にできるだけ近い値にする必要があります。これは、いくつかの問題をデバッグするのに非常に役立ちます。

2) 複数のバージョン

ほとんどすべての最新のデータベース システムは、トランザクション同時実行制御メカニズムの一部としてマルチバージョン メカニズムを使用しており、ByteKV も例外ではありません。複数バージョンの利点は、読み取りと書き込みが互いにブロックされないことです。行への書き込みごとに新しいバージョンが作成されますが、読み取りでは通常、既存のバージョンが読み取られます。論理データの構成は次のとおりです。

特定のバージョンの検索を容易にするために、同じキーの複数のバージョンが継続的に一緒に保存されます。クエリのオーバーヘッドを削減するために、バージョンは降順で並べ替えられます。

エンコードされたデータが希望の順序でソートできることを保証するために、RocksDBキーにはメモリ比較可能なエンコード[2]を使用します。 RocksDB の比較関数をカスタマイズしない理由は次のとおりです。

• キー サイズの比較はエンジンの読み取りと書き込みで非常に頻繁に発生し、デフォルトの memcmp はパフォーマンスに非常に優しいです。
• RocksDB への特別な依存を減らし、アーキテクチャの柔軟性を向上させます。
• 同じキーの複数のバージョンが継続的に蓄積され、その結果スペースが無限に拡張されるのを回避するために、ByteKV には、古いバージョンと削除対象としてマークされたデータを定期的にクリーンアップするバックグラウンド タスクがあります。前回の記事では、ストレージ エンジンの章で少し紹介しました。

3) 2相コミット

ByteKV は 2 フェーズ コミットを使用して分散トランザクションを実装します。一般的な考え方としては、プロセス全体が 2 つの段階に分かれています。最初の段階は準備段階と呼ばれ、コーディネーターが参加者に準備要求を送信する責任があり、参加者は要求に応答してリソースを割り当て、事前コミットします (事前コミットされたデータを書き込み意図と呼びます)。最初のステージのすべての参加者が正常に実行された後、コーディネーターは 2 番目のステージであるコミット ステージを開始します。このステージでは、コーディネーターがトランザクションをコミットし、すべての参加者にコミット コマンドを送信します。参加者はリクエストに応答した後、書き込み意図を実際のデータに変換します。

ByteKV では、コーディネーターは KVClient であり、参加者はすべて PartitionServers です。次に、原子性と分離性の観点から、ByteKV の分散トランザクション実装の詳細を見てみましょう。

①まず、トランザクションのアトミック性が外部から見えるようにするにはどうすればよいでしょうか。

この問題の本質は、永続的なトランザクション状態が必要であることであり、トランザクション状態はアトミックに変更できます。業界には多くのソリューションが存在します。 ByteKV が採用している方法は、トランザクション ステータスを通常のデータとして扱い、内部テーブルに別途保存することです。このテーブルをトランザクション ステータス テーブルと呼びます。他のビジネス データと同様に、複数のマシンに分散して保存されます。トランザクション ステータス テーブルには、次の情報が含まれます。

• トランザクション ステータス: トランザクションの開始、コミット、ロールバックなどが含まれます。トランザクション状態自体は KV であるため、アトミック性を簡単に実現できます。
• トランザクション バージョン番号: トランザクションがコミットされると、グローバル増分クロックから取得されたタイムスタンプが、トランザクションによって変更されたすべてのキーにエンコードされます。
• トランザクション TTL: トランザクションのタイムアウト期間。主に、トランザクションがスタックしてリソースを占有する問題を解決します。他のトランザクションがこのトランザクションによって変更されたリソースにアクセスすると、トランザクションがタイムアウトしていることがわかった場合、トランザクションを強制的に殺すことができます。

トランザクションステータステーブルの助けを借りて、第2フェーズでは、コーディネーターはトランザクションステータスを単純に変更して、トランザクションコミットとロールバック操作を完了するだけです。トランザクションステータスの変更が完了すると、クライアントは正常に応答できます。書き込み意図の提出およびクリーンアップ操作は非同期に実行されます。

2番目の質問は、トランザクション間の隔離と競合の解決を確保する方法です。

BYTEKVは、実行中のトランザクションを先着順でソートします。後のトランザクションは、以前のトランザクションが完了し、書き込みの意図がクリアされるまで、書き込み意図を読み取った後に待ちます。書き込みの意図は、リクエストを読むために表示されません。書き込み意図によって指されたトランザクションの準備時間が読み取りトランザクション時間よりも大きい場合、書き込み意図は無視されます。それ以外の場合、読み取り要求は、データが読み取り可能かどうかを知る前に、以前のトランザクションを完了またはロールバックするのを待つ必要があります。

取引がコミットされるのを待つことは、読み取り要求の遅延に影響する可能性があります。簡単な最適化方法は、Commest Timestameのコミットタイムスタンプを、読み取りトランザクションのタイムスタンプの後に移動することです。以前に書き込み意図について多くのことを話したことがあるので、トランザクション中にコミットされていないデータを他のトランザクションで読み取れないように、書き込み意図がエンコードされていますか？これも比較的簡単です。無限に書き込み意図のバージョン番号を設定するだけです。

上記の問題に加えて、分散トランザクションは断層許容の問題を解決する必要があります。ここでは、コーディネーターの失敗のシナリオについてのみ説明します。コーディネーターの障害後、取引はコミットされた状態またはコミットされていない状態にある可能性があります。一部のパーティションサーバーの書き込み意図は、コミットまたはクリーンアップされているか、まだそこに残っている可能性があります。

トランザクションがコミットされている場合、その後の読み取りワイトトランザクションが残りの書き込み意図に遭遇する場合、トランザクションステータステーブルのステータスに従って書き込み意図をコミットまたはクリアする以前のトランザクションが役立ちます。トランザクションがコミットされていない場合、その後のトランザクションは、以前のトランザクションタイムアウト（トランザクションTTL）の後にトランザクションステータスをロールバックに変更し、書き込み意図を非同期にクリーンアップします。

書き込み意図自体にはトランザクション関連の情報も含まれているため、参加者リストを書き込み意図に記録する場合、トランザクションコミットフラグをトランザクションステータスの原子変更からすべての書き込み意図の永続性に変更でき、それによりコミットの遅延が減少します。書き込み意図に遭遇する後続の操作は、参加者リストに基づいてトランザクションステータスを復元できます。

4.自動パーティションの分割とマージ

前述のように、BYTEKVは範囲パーティションを使用してスケーラビリティを提供します。この分割方法の1つの問題は、ビジネスが発展するにつれて、元のパーティション構造が新しいビジネスモデルに適していないことです。たとえば、ビジネスがホットスポットを書き込む場合、ホットスポットはあるパーティションから別のパーティションにドリフトする場合があります。この問題を解決するために、BYTEKVは自動分割関数を実装します。ユーザーの書き込みをサンプリングすることにより、データの量が特定のしきい値を超えると、範囲は中央の2つの新しい範囲に分割されます。スケジューリングと組み合わせた分割関数は、自動拡張機能を提供します。

BYTEKVによって実装された分割プロセスは比較的簡単です。範囲が分割条件に達したことがわかった場合、KVMasterに適用されて分割を実行し、新しいパーティションの関連するメタデータを取得し、範囲内で分割操作を実行します。分割コマンドは通常の操作と同じです。現在の範囲のラフトリーダーにログとして送られます。ログがコミットされると、状態マシンは、ログに掲載された情報に基づいて、新しいラフトレプリカを所定の位置に引き上げます。これらの新しいレプリカは、分割後にパーティションの半分を提供し、元のレプリカはパーティションの残りの半分を提供します。

多数のTTLや多数の書き込み型整形操作などの他のシナリオでは、多数のパーティションが自動的に分割されます。 TTLが期限切れになり、データがGCEDの場合、これらの分割パーティションは多数のデータフラグメントを形成します。各RAFTグループは少量のデータのみを提供します。これらの小さなパーティションは意味のないオーバーヘッドを引き起こし、それらのメタデータを維持することで、KVMasterの負担も増加します。この状況に対処するために、BYTEKVは自動マージ関数を実装して、隣接する間隔といくつかの小さな間隔をマージします。

マージプロセスは、分割よりも複雑です。マスターは、2つの隣接する間隔をスケジュールしてマージされ、マージ操作を開始します。上の図に示すように、このプロセスは2つのステップに分割されます。まず、左の間隔で同期ポイントを取得するために操作を開始し、右の間隔でマージ操作を開始します。正しい間隔が待ちます。現在のサーバーの左間隔の同期ポイントの前のデータが同期されている限り、左と右の間隔のメタデータを安全に変更してマージ操作を完了することができます。

5。ロードバランシング

ロードバランシングは、すべての分散システムに必要な重要な機能の1つです。負荷分散を達成できないシステムは、クラスターのコンピューティングとストレージリソースを完全に利用することに失敗するだけでなく、個々のノードの過度の負荷によって引き起こされるジッターにより、サービス品質にも影響します。優れた負荷分散戦略の設計は、2つの困難に直面します。第一に、最も基本的なディスクスペースだけでなく、CPU、IO、ネットワーク帯域幅、メモリスペースなども含まれる、バランスをとる必要がある多くのリソースディメンションがあります。第二に、バイテダンス内では、マシンの仕様は非常に多様です。同じクラスター内の異なるノードには、異なるCPU、ディスク、およびメモリがある場合があります。ロードバランス戦略を設計する際に、最初に単一次元の均質モデルのシナリオのみを考慮し、次に多次元の異種モデルに拡大する際に、段階的なアプローチを採用しました。戦略の進化を以下に説明します。

1）単一次元スケジューリング戦略

ディスクスペースの単一の次元を例として取り、すべてのノードのディスク容量がまったく同じであると仮定します。各ノードのディスクスペース使用は、このノード上のすべてのレプリカのデータ量の合計に等しくなります。すべてのレプリカを1つずつ割り当て、特定のノードに配置すると、レプリカ割り当てスキームが形成されます。各ノードのデータボリュームの分散値が最も低く、この状態を「絶対平衡」と呼ぶソリューションが必要です。

データが継続的に記述されているため、ノードのデータの量は変更され続けます。クラスターが常に「絶対バランス」状態を維持する場合、継続的にスケジュールする必要があります。これにより、多くのデータ移行が頭上になります。それだけでなく、特定の次元の絶対平衡は、他の次元の絶対平衡を利用できなくなります。コストと実現可能性の観点から、「十分な平衡」と呼ばれるより弱い平衡状態を定義します。一方では、平衡基準を緩和し、スケジューリングの感度を低下させ、データの変更が少量のスケジューリングを引き起こすことはありません。一方、複数の次元がこの弱い平衡状態を同時に達成することも可能になります。 「十分なバランス」の定義を直感的に表現するために、説明するために概略図を描きます。

• 各ノードは柱であり、柱の高さはそのデータボリュームです。すべてのノードは、高から低いまで順番に配置されます。
• すべてのノードの平均データボリュームを計算し、平均線と呼ばれる水平線を描画します
• 1つのアルファをそれぞれ高い水位値と低水位値に追加して減算します。アルファはSAVGの10％または20％を摂取することができ、これにより平衡の緊張が決定されます。水位値に応じて、高い水位と低水位ラインを引き出します。

ノードデータボリュームと3行の関係によれば、それらは4つの領域に分かれています。

• 高負荷エリア/アクティブ移動領域：ノードデータボリュームは高い水位値よりも高い
• 高いイコライゼーションゾーン/パッシブ移動ゾーン：ノードデータ量は高い水位値よりも低く、平均値よりも高い
• 低バランスゾーン/パッシブ移動ゾーン：ノードデータボリュームは低水位値よりも高く、平均値よりも低い
• 低負荷面積/アクティブ移動領域：ノードデータボリュームは低水位値よりも低い

ノードが高負荷領域にある場合、レプリカを積極的に移行する必要があり、ターゲットノードは移行領域にあります。ノードが低荷重エリアにある場合、レプリカに積極的に移行する必要があり、ソースノードは移行領域です

すべてのノードが2つのイコライゼーションゾーンに配置されると、クラスターは「十分な均等化」状態に到達します。次の図は、「十分な均等化」状態です

2）多次元スケジューリング戦略

以前の単一次元スケジューリングに基づいて、多次元スケジューリングの目標は、クラスターが複数の次元で十分にバランスのとれた状態を同時にまたはできるだけ多くの状態にすることを可能にすることです。

まず、各ディメンションには、その平衡状態を表すために上記の概略図があり、n図がn寸法に存在することを想像しましょう。コピーが移行すると、すべての寸法の平衡状態が同時に変更されます。つまり、すべての図が変更されます。

すべての寸法がよりバランスが取れている（平衡面積のノードの数が大きくなる）、またはいくつかの寸法がよりバランスが取れている場合、次元の他の部分は変わらないままです（平衡領域のノードの数は変わらないままです）、この移行は良いスケジュールです。とにかく、すべての寸法がより不均衡になった場合（平衡面積のノードの数が少なくなります）、またはいくつかの寸法がより不均衡になり、次元の他の部分は変わらないままである場合、この移動は悪いスケジューリングです。

また、いくつかの次元がよりバランスが取れており、いくつかの次元がよりバランスが取れている場合、3番目のケースもあります。これは中立スケジューリングです。多くの場合、このニュートラルなスケジューリングは避けられません。たとえば、クラスターには2つのノードAとBのみがあり、Aはトラフィックが高く、Bにはデータボリュームが高くなります。レプリカをAからBに移動すると、トラフィックがよりバランスが取れており、データボリュームが不均衡になります。レプリカをBからAに移行することは反対です。

このニュートラルなスケジューリングを許可できるかどうかを判断するために、優先度の概念を導入し、各次元に独自の優先事項を与えます。よりバランスのとれた高光学的寸法のために、最適な寸法の平衡を犠牲にすることは受け入れられ、よりバランスのとれた低最適な寸法のために高光学寸法の平衡を犠牲にすることは受け入れられません。

交通量が多すぎると読み取りと書き込みの応答時間、したがってサービスの質に影響するため、トラフィックの優先順位がデータボリュームの優先度よりも高いため、AからBへの移行は許容できるため、トラフィックが高いため、前の例を考慮してください。ただし、例外があります。ノードBの残りのディスクスペースが0に近づいており、クラスター内の最小のレプリカでさえ収容できない場合、トラフィックの優先順位が良くても、レプリカをBに移行することは許可されてはなりません。このリソースの飽和状態を直感的に表現するために、概略図にハードリミットラインを追加します。

この図と併せて、多次元の負荷分散戦略は次のとおりです。

• 複数の寸法の優先順位別のソート、上記の単一次元スケジューリング戦略を最適な次元から低い最適な次元まで実装し、プロセスにわずかな変更のみを行います。
• SBESTに最も近いが、ソースノードのSBESTよりも小さいコピーは、候補の移行オブジェクトです。次の列のいずれかが発生すると、除外され、次のコピーが適切なコピーが見つかるまで候補オブジェクトとして選択されます。
• 移動後、ターゲットマシンはより高い最適な次元で高い水位を上回ります
• 移行後、ターゲットマシンは最適な次元の低下で厳しい制限を超えます
• ターゲットノードのソースノードで移行オブジェクトを選択できない場合、ターゲットノードで最初にランク付けされるノードが新しいターゲットノードとして使用され、上記のプロセスが繰り返されます
• すべてのターゲットノードのソースノードで移行オブジェクトがまだ選択されていない場合は、ソート付きリストからソースノードを削除し、上記のプロセスを繰り返します

3）異なる組織モデルのスケジューリング戦略

均一なモデルの場合、負荷の単位は各ノードで同じ割合のリソースを使用します。これらの負荷が使用する機械リソースの数を使用することなく、負荷値に基づいてのみスケジュールできますが、これは不均一なモデルでは当てはまりません。

たとえば、ディスクから1MBのデータを読み取ると、高性能サーバー上のIO帯域幅の1％とCPUサイクルの1％しか占有しませんが、IO帯域幅の5％と仮想マシンのCPUサイクルの3％を占める場合があります。パフォーマンスが異なるノードでは、同じ負荷が異なるリソース利用率を生成します。

以前のスケジューリング戦略を不均一なモデルシナリオに適用するには、まずリソースの利用によってスケジューリングにスケジューリングを変更します。データボリュームの場合、ディスクスペースの使用率に変更する必要があります。トラフィックについては、CPU使用率、IO使用率などに変更する必要があります。戦略を簡素化するには、メモリ、ディスクIO、ネットワークIOなどのすべての使用法をCPU使用に含めました。理由を説明する：

• メモリの場合、プロセスメモリ使用量の上限は構成項目を介して制御されます。展開中に、メモリの使用が物理メモリサイズを超えないようにします。残りの物理メモリはすべて、オペレーティングシステムのバッファー/キャッシュに使用され、実際に当社が使用できます。メモリサイズは、メムテーブルとブロックキャッシュのサイズに影響を与えることによりノードのパフォーマンスに影響し、この影響は最終的にCPUとIOの使用によって反映されます。したがって、CPUとIOの利用を調べると、メモリ使用量を含めることができます。
• ディスクIOの場合、IOの利用は最終的にCPUの使用率に反映されます (synclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclcl clclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclclcl
• CPUには3レベルのキャッシュとレジスタがあります。 CPUの使用率を考慮すると、それは全体として扱われ、キャッシュまたはレジスタの使用を個別に分析しません。メモリとディスクは、CPUの4番目と5レベルのキャッシュとして想像できます。メモリが小さく、ディスクioが遅いほど、CPUの使用率が高くなります。全体と見なすことができます。

不均一なスケジューリングが解決する必要がある2番目の問題は、リソース利用と負荷値の間の変換関係です。たとえば、ノードAとBのCPU使用率はそれぞれ50％と30％です。ノード上の各レプリカの読み取りおよび書き込みリクエストも既知です。ノードAからノードBに移行するために最適なレプリカを選択する方法AとBの間のCPU使用ギャップを最小化するには、各レプリカがノードAとBで生成するCPU使用率を計算する必要があります。

• 読み取りおよび書き込みリクエストのキーと値のサイズ
• キャッシュヒット率を読み取ります
• 更新のランダム化の程度、削除の割合

この情報に基づいて、各読み取りおよび書き込み要求はn標準トラフィックに変換されます。たとえば、1kb以内のリクエストは標準トラフィックであり、1〜2kbのリクエストは2つの標準トラフィックです。キャッシュにヒットするリクエストは標準トラフィックであり、キャッシュを欠いているリクエストは2標準トラフィックです。ノードの標準トラフィック値の合計を知ると、CPU使用率に基づいてノードの標準トラフィックに対応するCPU使用率を計算し、各ノードの各レプリカに対応するCPU使用率を計算できます。

要約すると、不均一なモデルスケジューリング戦略は、多次元スケジューリング戦略に基づいて次のように変更する必要があります。

• ノードは、負荷値ではなく、リソース利用によってソートされます
• 各レプリカの負荷値は、ソースノードのリソース利用率とターゲットノードのリソース使用率に変換する必要があります。不均一なモデルでは、同じレプリカのリソース利用率が大きく異なります。

4）その他のスケジューリング戦略

KVMasterには、「ロードバランシングスケジューラ」と呼ばれる上記のロードバランス戦略を実行するタイミングのタスクがありますが、ここでは説明しません。同時に、「レプリカ配置スケジューラ」と呼ばれる別のタイプのスケジューリングを実行するために使用される別のタイミングのタスクがあります。レプリカセキュリティレベル（データセンター/ラック/サーバー）、ノード例外検出などの基本的な戦略に加えて、次のスケジューリング戦略も実装します。

• ビジネス分離戦略：さまざまな名前空間/テーブルをさまざまなノードに保存できます。各名前空間/テーブルは、文字列タイプのタグを指定できます。各ノードは1つ以上のタグを指定できます。コピーが配置されている名前空間/テーブルのタグは、タグがノードのものと同じ場合にのみノードに配置できます。スケジューラは、タグ要件を満たさないコピーをスケジュールします。
• ホットスポット検出：特定のデータシャードのデータボリュームが特定のしきい値に達すると、分割も発生します。さらに、読み取りおよび書き込みトラフィックが平均値の倍数を超えると、分割が発生します。スプリットが発生すると、新しく生成されたシャードの1つ（左または右）のすべてのレプリカが他のノードに移動して、ノードがアクセスホットスポットになるのを防ぎます。
• フラグメント検出：データボリュームとデータシャードのトラフィックの読み取りと書き込みのトラフィックが平均値の特定の割合よりも少ない場合、隣接するシャードとマージされます。マージする前に、小さな破片のすべてのレプリカが隣接する破片があるノードに移動します。

5。テーブルレイヤー

前述のように、KVデータモデルは単純すぎて、複雑なビジネスシナリオのニーズを満たすことは困難です。例えば：

• 多くのフィールドとタイプがあります
• 異なるフィールド寸法の複雑な条件を照会する必要があります
• フィールドまたはクエリの寸法は、多くの場合、需要とともに変化します。

これらのシナリオのニーズを満たすには、より豊富なデータモデルが必要です。 KVレイヤーの上に、前述のSQLProxyによって実装されたテーブルレイヤーbytesqlを構築します。 BYTESQLは、構造化されたクエリ言語（SQL）を介した書き込みと読み取りをサポートし、BYTEKVのバッチ書き込み（WriteBatch）に基づいて混合読み取り操作をサポートするインタラクティブトランザクションを実装し、SnapShot読み取りインターフェイスを実装します。

1。表モデル

テーブルストレージモデルでは、データはデータベースとテーブルという2つの論理レベルに従って編成および保存されます。同じ物理クラスターで複数のデータベースを作成でき、各データベースで複数のテーブルを作成できます。テーブルのスキーマ定義には、次の要素が含まれています。

• データベース名、テーブル名、データレプリカの数などを含むテーブルの基本プロパティ。
• フィールド定義：フィールドの名前、タイプ、null値が許可されているかどうか、デフォルト値、その他の属性が含まれます。テーブルには、少なくとも1つのフィールドが含まれている必要があります。
• インデックス定義：インデックス名、インデックスに含まれるフィールドリスト、インデックスタイプ（プライマリキー、一意のキー、キーなど）が含まれます。テーブルには1つの主要なインデックスのみがあり、ユーザーはSQL実行パフォーマンスを改善するためにセカンダリインデックス（キーまたは一意のキータイプ）を追加することもできます。各インデックスは、単一フィールドインデックスまたはマルチフィールドジョイントインデックスにすることができます。

テーブル内の各行は、インデックスに従って複数のkVにエンコードされます。レコードはBYTEKVに保存され、各インデックスタイプはさまざまな方法でエンコードされます。プライマリキーの行には、テーブル内のすべてのフィールドの値が含まれていますが、セカンダリインデックスの行には、インデックスとプライマリキーを定義するフィールドのみが含まれます。各インデックスの特定のエンコード方法は次のとおりです。

主要な キー：pk_field1、pk_field2、... => non_pk_field1、non_pk_field2 ...  
個性的 キー：key_field1、key_field2、... => pk_field1、pk_field2 ...  
 Nonique Key ：key_field1、key_field2、...、pk_field1、pk_field2 ... =>

PK_FIELDは主キーを定義するフィールドである場合、Non_PK_Fieldはテーブルにプライマリキーを含まないフィールドであり、Key_Fieldはセカンダリインデックスを定義するフィールドです。 => KV層のキーと値の部分にそれぞれ対応する前後の内容。重要な部分のエンコードは、上記のメモリの比較可能なエンコードをまだ使用しているため、フィールドの自然な順序がエンコード後のバイト順序と同じであることを保証します。値部分は、プロトブフと同様の可変長エンコーディングメソッドを採用して、エンコードされたデータサイズを最小限に抑えます。 1バイトは、各フィールドのエンコードで使用され、値がnull値であるかどうかを識別します。

2。グローバルセカンダリインデックス

ユーザーは、多くの場合、非プリマリーキーフィールドをクエリ条件として使用する必要があります。これには、これらのフィールドにセカンダリインデックスを作成する必要があります。従来のシャーディングアーキテクチャ（MySQL Shard Clusterなど）では、テーブル内のフィールドをシャーディングキーとして使用するフィールドを選択し、テーブル全体を別のシャードにハッシュします。

異なるシャード間に効率的な分散トランザクションメカニズムがないため、各シャード内にセカンダリインデックスを作成する必要があります（つまり、ローカルセカンダリインデックス）。この解決策の問題は、クエリ条件にシャーディングキーが含まれていない場合、結果のマージのためにすべてのシャードをスキャンする必要があり、グローバルな一意性制約を実装できないことです。

この問題を解決するために、BYTESQLはグローバルなセカンダリインデックスを実装し、BYTEKVの異なるシャードの主要なキーデータとセカンダリインデックスデータを分散します。インデックスのレコードは、セカンダリインデックスのクエリ条件に基づいてのみ配置でき、対応するプライマリキーレコードをさらに見つけます。この方法は、結果合併のためにすべてのシャードをスキャンするオーバーヘッドを回避します。また、強力な水平スケーラビリティを備えた一意のキーを作成することにより、グローバルな一意性制約をサポートできます。

3。インタラクティブトランザクション

BYTESQLは、複数のレコードのBYTEKVとAtomic Write（WriteBatch）のマルチバージョン特性に基づいて、スナップショット分離レベル（スナップショット分離）をサポートする読み取りおよび書き込みトランザクションを実装します。基本的な実装のアイデアは次のとおりです。

• ユーザーが開始トランザクションコマンドを開始すると、BYTESQLはトランザクションの開始タイムスタンプとしてBYTEKVマスターからグローバルに一意のタイムスタンプを取得します（Start Timestamp）。開始タイムスタンプは、トランザクション内の一貫したスナップショット読み取りバージョンと、トランザクションコミット中の競合判断の両方として使用されます。
• トランザクション内のすべての書き込み操作は、bytesqlのローカル書き込みバッファーでキャッシュされており、各トランザクションには独自の書き込みバッファーインスタンスがあります。削除操作の場合は、書き込みバッファーに墓石タグを書き込みます。
• トランザクションのすべての読み取り操作は、最初に書き込みバッファーを読み取ります。書き込みバッファーにレコードがある場合、直接返されます（Tombstone Return Recordが書き込みバッファーに存在しない場合）。それ以外の場合は、BYTEKVのレコードを、開始タイムスタンプよりも小さいバージョン番号で読んでみてください。
• ユーザーがCommit Transactionコマンドを開始すると、BYTESQLはBYTEKVのWriteBatchインターフェイスを呼び出して、書き込みバッファーにキャッシュされたレコードを送信します。コミットは条件付きです。書き込みバッファーの各キーについて、コミットするときにタイムスタンプを開始するよりも大きなバージョンがないことを確認する必要があります。条件が保持されない場合、現在のトランザクションは中止する必要があります。この条件は、BYTEKV CASインターフェイスを介して実装されます。

上記のプロセスから、BYTESQLが楽観的なモードでトランザクション競合の検出を実装することがわかります。このモードは、書き込み競合率が高くないシナリオでは非常に効率的です。競合率が高い場合、トランザクションは頻繁に中止されます。

4。実行プロセスの最適化

BYTESQLはよりリッチなSQLクエリセマンティクスを提供しますが、KVモデルのGETや削除などの操作よりも単純なプットよりもオーバーヘッドを追加します。 SQLの挿入、更新、削除操作は、実際には読み取りファーストであり、書き込み第一プロセスです。更新を例にとると、最初にGET操作を使用してBYTEKVの古い値を読み取り、SQLの設定句に従って古い値の特定のフィールドを更新して新しい値を生成し、Put操作を使用してBYTEKVに新しい値を書き込みます。

いくつかのシナリオでは、一部のフィールドの値は、bytesql（自動プライマリキーなど、デフォルト/更新current_timestamp属性のある時間フィールドなど）で自動的に生成されるか、依存関係（set a = a+1など）に基づいて計算されます。ユーザーは、挿入、更新、または削除の直後に実際の変更データを取得する必要があり、操作を作成した後に選択操作を実行する必要があります。合計2つのGET操作と1つのPUT操作が必要です。実行効率を最適化するために、PostgreSQL/Oracle構文の返信セマンティクスがBYTESQLに実装されています：挿入/更新の新しい値または削除の古い値は同じクエリ要求で返され、単一のGet Overheadを節約します。

 Table1セットを更新します  count = count + 1ここで、 id> = 10返信id、 count ;

5.オンラインスキーマの変更

継続的な進化とビジネス要件の変化は、スキーマの変化の避けられない仕事につながりました。従来のデータベースの組み込みスキーマ変更スキームでは、一般に、オンラインアプリケーションには受け入れられないテーブルの読み取りおよび書き込み操作全体をブロックする必要があります。 BYTESQLはGoogle F1のオンラインスキーマ変更プラン[3]を使用し、オンラインの読み取りおよび書き込みリクエストは、変更プロセス中にブロックされません。

BYTESQLスキーマメタデータには、ライブラリとテーブルの定義が含まれており、これらのメタデータはBYTEKVに保存されています。 SQLProxyインスタンスはStatelessであり、各インスタンスはスキーマをBYTEKVからローカルまで定期的に同期し、クエリリクエストを解析および実行するために使用されます。

同時に、ユーザーが提出したスキーマ変更タスクのリスニングと実行を担当するクラスターには、専用のスキーマ変更ワーカーインスタンスがあります。 Schema Change Workerユーザースタディのスキーマ変更要求が聞こえたら、リクエストキューに配置され、順番に実行されます。このセクションでは、データの一貫性の例外の生成と解決の観点からスキーマ中間状態を導入する理由について説明します。正確さの詳細な証明については、元の論文を参照してください。

さまざまなSQLProxyインスタンスによるロードスキーマのタイミングは異なるため、複数のバージョンのスキーマが同時に使用される可能性が高いです。スキーマ変更プロセスが適切に処理されない場合、テーブル内のデータに矛盾が生じます。セカンダリインデックスの作成を例にとって、次の実行プロセスを検討してください。

• Schema Change Workerは、インデックスレコードをBYTEKVに入力し、メタデータを作成することを含むCreate Index Changeタスクを実行します。
• SQLProxyインスタンス1新しいインデックスを含むスキーマメタデータをロードします。
• SQLProxyインスタンス2は挿入要求を実行します。インデックスメタデータは例2にロードされていないため、挿入操作には新しいインデックスレコードへの書き込みは含まれていません。
• sqlproxyインスタンス2は削除要求を実行します。インデックスメタデータは例2にロードされていないため、削除操作には新しいインデックスレコードの削除が含まれていません。
• sqlproxyインスタンス2つの新しいインデックスを含むメタデータの負荷。

ステップ3と4はどちらも、セカンダリインデックスとプライマリキーインデックスデータの間に一貫性のない例外を引き起こします。ステップ3は、セカンダリインデックスレコードの損失を引き起こし（紛失しました）、ステップ4はセカンダリインデックスレコードの遺産（Lost Delete）を引き起こします。これらの例外の原因は、異なるsqlproxyインスタンスの負荷スキーマが異なる場合、それらが既に存在する場合、他の人はそうではないと考えている場合です。具体的には、ステップ2の挿入例は、インデックスが既に存在しているためであり、ライターはそれが存在しないと考えています。ステップ3の削除例外は、ライターがインデックスの存在を認識しているためですが、削除党は知覚しません。実際、更新操作は、上記の両方の例外を同時に引き起こす可能性があります。

Lost Writeの例外を解決するために、挿入されたデータの行ごとに、書き込みインスタンスが最初にそれを書く前に存在を知覚する必要があることを確認する必要があります。また、Lost Delete例外の場合、同じデータの行の削除されたインスタンスが、書かれたインスタンスよりもインデックスの存在をよりよく認識していることを確認する必要があります（書かれたインスタンスが最初にインデックスを検知し、削除インスタンスが削除され、インデックスが見逃され、失われた削除が発生する場合があります）。

ただし、さまざまなSQLProxyインスタンスの知覚された順序を書き込みインスタンスと削除インスタンスとして直接制御することはできません。代わりに間接的な方法を使用します。スキーマは、読み書きを制御する2つの中間状態を定義します。 Schema Change Workerは、最初にDeleteonly状態のスキーマメタデータを作成し、メタデータがすべてのインスタンスに同期された後、Writeonly状態のスキーマメタデータを書き込みます。 Deleteonly状態を知覚するインスタンスは、インデックスレコードのみを削除することができ、インデックスレコードに書き込むことはできません。 Writeonly状態を知覚するインスタンスは、インデックスレコードを削除および挿入できます。これにより、Lost Delete例外が解決します。

而对于Lost Write 异常，我们无法阻止尚未感知Schema WriteOnly 状态的实例写入数据(因为整个Schema 变更过程是在线的)，而是将填充索引记录的过程(原论文中称之为Reorg 操作)推迟到了WriteOnly 阶段之后执行，从而既填充了表中存量数据对应的索引记录，也填充了那些因为Lost Write 异常而缺失的索引记录。待填充操作完成后，就可以将Schema 元数据更新为对外可见的Public 状态了。

我们通过引入两个中间状态解决了Schema 变更过程中数据不一致的异常。这两个中间状态均是对ByteSQL 内部而言的，只有最终Public 状态的索引才能被用户看到。这里还有一个关键问题：如何在没有全局成员信息的环境中确保将Schema 状态同步到所有SQLProxy 实例中?解决方案是在Schema 中维护一个全局固定的Lease Time，每个SQLProxy 在Lease Time 到期前需要重新从ByteKV 中加载Schema 来续约。

Schema Change Worker 每次更新Schema 之后，需要等到所有SQLProxy 加载成功后才能进行下一次更新。这就需要保证两次更新Schema 的间隔需要大于一定时间。至于多长的间隔时间是安全的，有兴趣的读者可以详细阅读原论文[3]来得到答案。如果某个SQLProxy 因为某种原因无法在Lease Time 周期内加载Schema，则设置当前ByteSQL 实例为不可用状态，不再处理读写请求。

六、未来探讨

1、更多的一致性级别

在跨机房部署的场景里，总有部分请求需要跨机房获取事务时间戳，这会增加响应延迟;同时跨机房的网络环境不及机房内部稳定，跨机房网络的稳定性直接影响到集群的稳定性。实际上，部分业务场景并不需要强一致保证。在这些场景中，我们考虑引入混合逻辑时钟HLC[4]来替代原有的全局授时服务，将ByteKV 改造成支持因果一致性的系统。同时，我们可以将写入的时间戳作为同步口令返回给客户端，客户端在后续的请求中携带上同步口令，以传递业务上存在因果关系而存储系统无法识别的事件之间的happen-before 关系，即会话一致性。

此外，还有部分业务对延迟极其敏感，又有多数据中心访问的需求;而ByteKV 多机房部署场景下无法避免跨机房延迟。如果这部分业务只需要机房之间保持最终一致即可，我们可以进行机房间数据同步，实现类最终一致性的效果。

2、Cloud Native

随着CloudNative 的进一步发展，以无可匹敌之势深刻影响着现有的开发部署模型。ByteKV 也将进一步探索与CloudNative 的深入结合。探索基于Kubernetes 的auto deployment, auto scaling, auto healing。进一步提高资源的利用率，降低运维的成本，增强服务的易用性。提供一个更方便于CloudNative 用户使用的ByteKV。