学習
高速ベクトル探索

筏か否か？クラウドネイティブデータベースにおけるデータ一貫性のベストソリューション

May 16, 20221 分で読めます

PaxosやRaftのようなコンセンサスに基づくアルゴリズムが、なぜ銀の弾丸ではないのかを説明し、コンセンサスに基づくレプリケーションの解決策を提案する。

シリーズ全体を読む

この記事はAngela Niによって転記されています。

コンセンサス・ベースのレプリケーションは、多くのクラウド・ネイティブな分散データベースで広く採用されている戦略だ。しかし、これにはある欠点があり、決して特効薬ではない。

この投稿の目的は、まずクラウドネイティブ・分散データベースにおけるレプリケーション、一貫性、コンセンサスの概念を説明し、次にPaxosやRaftのようなコンセンサスベースのアルゴリズムが銀の弾丸ではない理由を明らかにし、最後にコンセンサスベースのレプリケーションに対する解決策を提案することである。

レプリケーション、一貫性、コンセンサスを理解する

PaxosとRaftの長所と短所を深く掘り下げ、最適なログレプリケーション戦略を提案する前に、まずレプリケーション、一貫性、コンセンサスの概念を理解する必要があります。

この記事では、主にインクリメンタルなデータ/ログの同期に焦点を当てていることに注意してください。従って、データ／ログのレプリケーションについて語る場合、履歴データではなく、増分データのレプリケーションのみを指す。

レプリケーション

レプリケーションとは、データの複数のコピーを作成し、異なるディスク、プロセス、マシン、クラスターなどに保存するプロセスであり、データの信頼性を高め、データクエリーを高速化することを目的としている。レプリケーションではデータが複数の場所にコピーされ保存されるため、ディスク障害や物理的なマシン障害、クラスタエラーからの復旧においてデータの信頼性が高まる。さらに、データの複製を複数作成することで、クエリを大幅に高速化し、分散データベースのパフォーマンスを向上させることができます。

レプリケーションには、同期/非同期レプリケーション、強力/完全一貫性レプリケーション、リーダー・フォロワー/分散レプリケーションなど、さまざまなモードがあります。レプリケーション・モードの選択はシステムの可用性と一貫性に影響を与える。したがって、有名なCAP定理で提案されているように、ネットワーク分割が避けられない場合、システムアーキテクトは一貫性と可用性のトレードオフを行う必要がある。

一貫性

つまり、分散データベースにおける一貫性とは、データの書き込みや読み出しの際に、全てのノードやレプリカが同じデータビューを持つことを保証する性質を指します。整合性レベルの完全なリストについては、ドキュメントを読んでください。

明確にするために、ここではACID（atomicity、consistency、isolation、durability）ではなく、CAP定理の一貫性について話しています。CAP定理における一貫性とは、システム内の各ノードが同じデータを持つことを指し、ACIDにおける一貫性とは、単一のノードがすべての潜在的なコミットに対して同じルールを強制することを指します。

一般に、OLTP（オンライントランザクション処理）データベースは、以下のことを保証するために、強力な一貫性または線形化可能性を必要とする：

各読み出しは、挿入された最新のデータにアクセスできる。
読み取り後に新しい値が返された場合、同じクライアントであろうと異なるクライアントであろうと、それに続くすべての読み取りは新しい値を返さなければならない。

リニアライザビリティの本質は、複数のデータレプリカの再利用性を保証することである。一旦新しい値が書き込まれたり読み込まれたりすると、その値が後で上書きされるまで、後続の読み取りはすべて新しい値を見ることができる。線形化可能性を提供する分散システムは、ユーザーが複数のレプリカを監視する手間を省くことができ、各操作の原子性と順序を保証することができる。

コンセンサス

コンセンサスという概念は、分散システムがスタンドアロンシステムと同じように動作することをユーザーが切望していることから、分散システムに導入された。

簡単に言うと、コンセンサスとは価値に関する一般的な合意である。例えば、SteveとFrankが何か食べようとした。スティーブはサンドイッチを食べることを提案した。フランクはスティーブの提案に同意し、二人ともサンドイッチを食べた。彼らはコンセンサスに達した。より具体的には、どちらかが提案した価値（サンドイッチ）が両者によって合意され、その価値に基づいて両者が行動を起こす。同様に、分散システムにおけるコンセンサスとは、あるプロセスがある値を提案すると、システム内の残りのすべてのプロセスがその値に同意し、その値に基づいて行動することを意味する。

分散システムにおけるコンセンサス](https://assets.zilliz.com/3_908de88846.png)

コンセンサスに基づく複製

最も初期のコンセンサスベースのアルゴリズムは、1988年にviewstamped replicationとともに提案された。1989年、Leslie LamportはコンセンサスベースのアルゴリズムであるPaxosを提案した。

近年では、コンセンサスベースのアルゴリズムとして、Raftが広く普及している。CockroachDB、TiDB、OceanBaseなど、多くの主流NewSQLデータベースで採用されている。

注目すべきは、分散システムがコンセンサスベースのレプリケーションを採用していても、必ずしも線形化可能性をサポートしているとは限らないということです。しかし、線形化可能性はACID分散データベースを構築するための必須条件である。

データベースシステムを設計する際には、ログとステートマシンのコミット順序を考慮する必要がある。また、PaxosやRaftのリーダーリースを維持し、ネットワーク・パーティション下でのスプリットブレインを防ぐためには、特に注意が必要である。

Raftレプリケーション・ステートマシンの構造](https://assets.zilliz.com/1_f849748bc6.png)

長所と短所

実際、Raft、ZAB、Auroraのquorum-based log protocolはすべてPaxosのバリエーションである。コンセンサスベースのレプリケーションには以下のような利点がある：

1.1.コンセンサスに基づくレプリケーションは、CAP定理における一貫性とネットワーク分割により重点を置いているが、従来のリーダー・フォロワーレプリケーションと比較して、比較的優れた可用性を提供する。 2.Raftは、コンセンサスベースのアルゴリズムを大幅に簡素化した画期的なものである。オープンソースのRaftライブラリがGitHubに多数公開されている（例：sofa-jraft）。 3.コンセンサスベースのレプリケーションの性能は、ほとんどのアプリケーションとビジネスを満足させることができる。高性能のSSDとギガバイトのNIC（ネットワーク・インターフェース・カード）の普及により、複数のレプリカを同期させる負担が軽減され、PaxosとRaftアルゴリズムが業界の主流となっている。

誤解のひとつに、コンセンサスベースのレプリケーションは分散データベースでデータの一貫性を実現するための特効薬であるというものがあります。しかし、これは真実ではありません。コンセンサス・ベースのアルゴリズムが直面する可用性、複雑性、性能の課題が、完璧なソリューションであることを阻んでいる。

1.妥協された可用性最適化されたPaxosやRaftアルゴリズムは、リーダーレプリカに強く依存しており、グレイの障害に対抗する能力が弱い。コンセンサスに基づくレプリケーションでは、リーダーノードが長時間応答しない限り、新しいリーダーレプリカの選出は行われません。そのため、コンセンサスベースのレプリケーションでは、リーダーノードの動作が遅い場合や、スラッシングが発生した場合に対処することができません。

2.高い複雑性 PaxosとRaftをベースとした拡張アルゴリズムはすでに多数存在するが、Multi-RaftやParallel Raftの出現により、ログとステートマシン間の同期についてより多くの検討とテストが必要となった。

3.パフォーマンスの低下クラウドネイティブの時代には、データの信頼性と一貫性を確保するために、ローカルストレージはEBSやS3のような共有ストレージソリューションに取って代わられる。その結果、コンセンサスベースのレプリケーションは分散システムにとってもはや必須ではなくなった。さらに、コンセンサス・ベースのレプリケーションには、ソリューションとEBSの両方に複数のレプリカがあるため、データの冗長性の問題がつきまとう。

マルチデータセンターとマルチクラウドのレプリケーションでは、一貫性の追求は可用性だけでなくレイテンシも犠牲にし、結果としてパフォーマンスの低下を招く。したがって、ほとんどのアプリケーションにおいて、マルチデータセンターのディザスタ・トレランスのために線形化可能性は必須ではありません。

クラウドネイティブな分散データベースのためのログ複製戦略

RaftやPaxosのようなコンセンサスベースのアルゴリズムが、多くのOLTPデータベースで採用されている主流のアルゴリズムであることは否定できない。しかし、PacificAプロトコル、Socrates、Rocksetの例を見ると、トレンドが変わりつつあることがわかる。

クラウドネイティブな分散データベースに最適なソリューションには、2つの大原則がある。

1.サービスとしてのレプリケーション

データ同期専用の独立したマイクロサービスが必要である。同期モジュールとストレージモジュールは、もはや同じプロセス内で密結合されるべきではない。

例えば、Socratesはストレージ、ログ、コンピューティングを分離している。専用のログサービス（下図の中央のXLogサービス）が1つあります。

Socratesのアーキテクチャ](https://assets.zilliz.com/4_12b944a9ee.png)

XLogサービスは個別のサービスです。データの永続性は低遅延ストレージの助けを借りて達成される。Socratesのランディングゾーンは、3つのレプリカを高速に保持する。

ソクラテスのXLogサービス](https://assets.zilliz.com/5_1a8df840ef.png)

リーダーノードはログを非同期にログブローカに配信し、Xstoreにデータをフラッシュします。ローカルSSDキャッシュはデータの読み込みを高速化することができます。データのフラッシュが成功すると、ランディングゾーンのバッファをクリーニングすることができる。明らかに、すべてのログデータは、ランディングゾーン、ローカルSSD、XStoreの3つのレイヤーに分割されます。

2.ロシア人形の原理

システムを設計する1つの方法は、ロシア人形の原則に従うことである。各レイヤーは完全で、そのレイヤーが行うことに完全に適しているため、他のレイヤーをそのレイヤーの上や周りに構築することができる。

クラウドネイティブ・データベースを設計する際には、システム・アーキテクチャの複雑さを軽減するために、他のサードパーティ・サービスを巧みに活用する必要がある。

単一障害点を回避するためにPaxosを利用することはできないようだ。しかし、Chubby、Zk、etcdをベースに、リーダー選出をRaftやPaxosサービスに任せることで、ログのレプリケーションを大幅に簡素化することができる。

例えば、Rocksetのアーキテクチャは、ロシア人形の原理に従い、分散ログにKafka/Kineses、ストレージにS3、クエリのパフォーマンスを向上させるためにローカルのSSDキャッシュを使用している。

Rocksetアーキテクチャ](https://assets.zilliz.com/2_60ff48c582.png)

Milvusのアプローチ

Milvusにおける調整可能な一貫性は、実はコンセンサスベースのレプリケーションにおけるフォロワーリードに似ている。フォロワーリード機能とは、強い一貫性を前提に、フォロワーレプリカを使ってデータの読み込みタスクを引き受けることを指す。その目的は、クラスタのスループットを向上させ、リーダーの負荷を軽減することである。フォロワリード機能の背後にあるメカニズムは、最新のログのコミットインデックスを照会し、コミットインデックス内のすべてのデータがステートマシンに適用されるまで、クエリサービスを提供することである。

しかし、Milvusの設計はフォロワー戦略を採用していない。つまり、Milvusは、問い合わせ要求を受信するたびにコミットインデックスを問い合わせるわけではない。その代わりに、MilvusはFlinkのwatermarkのような機構を採用し、定期的にコミットインデックスの位置を問い合わせノードに通知する。このような機構を採用する理由は、Milvusのユーザは通常データの一貫性を強く要求しないためであり、システムの性能向上のためならデータの可視性の妥協を受け入れることができるからである。

また、Milvusは複数のマイクロサービスを採用し、ストレージとコンピューティングを分離している。Milvusアーキテクチャ](https://milvus.io/blog/deep-dive-1-milvus-architecture-overview.md#A-bare-bones-skeleton-of-the-Milvus-architecture)では、S3、MinIo、Azure Blobがストレージとして使用されている。

Milvusアーキテクチャ](https://assets.zilliz.com/6_a6f27e89f6.png)

要約

昨今、ログレプリケーションを個別のサービスとして提供するクラウドネイティブデータベースが増えている。そうすることで、読み取り専用のレプリカや異種レプリケーションを追加するコストを削減できる。複数のマイクロサービスを利用することで、従来のデータベースでは不可能だった、成熟したクラウドベースのインフラを迅速に利用することができる。個々のログサービスは、コンセンサスベースのレプリケーションに依存することもできるが、ロシア人形戦略に従って、PaxosやRaftとともに様々な一貫性プロトコルを採用し、線形化可能性を実現することもできる。

参考文献

Lamport L. Paxos made simple[J].ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001), 2001: 51-58.
Ongaro D, Ousterhout J. In search of an understandingable consensus algorithm[C]//2014 USENIX Annual Technical Conference (Usenix ATC 14).2014:305-319.
Oki B M, Liskov B H. Viewstamped replication：高可用性分散システムをサポートする新しい一次コピー方式[C]//Proceedings of the 7th annual ACM Symposium on Principles of Distributed Computing.1988: 8-17.
PacificA: ログベースの分散ストレージシステムにおけるレプリケーション[J].2008.
Verbitski A, Gupta A, Saha D, et al. Amazon aurora：i/os、コミット、メンバシップ変更の分散コンセンサスの回避について[C]//Proceedings of the 2018 International Conference on Management of Data.2018: 789-796.
Antonopoulos P, Budovski A, Diaconu C, et al：The new sql server in the cloud[C]//Proceedings of the 2019 International Conference on Management of Data.2019: 1743-1756.

article.updateAt

James Luan
James Luan is the VP of Engineering at Zilliz. With a master's degree in computer engineering from Cornell University, he has extensive experience as a Database Engineer at Oracle, Hedvig, and Alibaba Cloud. James played a crucial role in developing HBase, Alibaba Cloud's open-source database, and Lindorm, a self-developed NoSQL database. He is also a respected member of the Technical Advisory Committee of LF AI & Data Foundation, contributing his expertise to shaping the future of AI and data technologies.