Scalar DB: Universal transaction manager
このブログ記事では、Scalar DBの概要とそこで用いられているトランザクションプロトコル「Consensus Commit」について説明します。（英語版はこちら）
Scalar DBの概要
Scalar DBは、高いスケーラビリティを有する分散トランザクションマネージャであり、以下の機能を持っています。
- ACIDトランザクション機能を持たないNoSQL等のデータベース上でACIDトランザクションを実現する。
- 複数のデータベースやサービス(マイクロサービス等)に跨る分散トランザクションを実現する。
アーキテクチャ
Scalar DBは下図のように、「Universal Transaction Manager」と「Database Abstraction Layer」、そして「Database Adapters」で構成されています。データベース(Database)は「Database Abstraction Layer」によって抽象化されているので、「Universal Transaction Manager」はどのデータベースを使っているかは意識しない構造になっています。「Database Adapters」を実際のデータベースに合わせて実装することで、そのデータベース上でACIDトランザクションを実行可能となります。現時点では、Cassandra、Amazon DynamoDB、Azure Cosmos DB、そしてJDBC (MySQL、 PostgreSQL、 Oracle Database、 Microsoft SQL Server、 Amazon Auroraをサポート)の実装があります。
データモデル
Scalar DBのデータモデルは、いわゆる多次元マップの構造になっています。1つのレコードは、パーティションキー(Partition key)とクラスタリングキー(Clustering key)があり、それに対して複数のカラム(Column)が保持されている構造になっています。1つのカラムの値は、パーティションキーとクラスタリングキー、そしてカラムの名前からユニークにマッピングされます。
(Partition key, Clustering key, Column name) -> Column Value
パーティションキーは文字通りパーティション(Partition)を特定するキーになっています。同じパーティションキーを持つレコードは同じパーティションに所属していることになります。そして、パーティション内のレコードはクラスタリングキーによってソートされて格納されています。
Scalar DBでは、データに対してget、scan、put、deleteのようなCRUD操作を行うことができます。getは1つのレコードを取得する操作で、scanは1つのパーティション内のレコードを、クラスタリングキーによるレンジスキャンをする操作で、putとdeleteはそれぞれレコードを追加/更新、削除する操作です。scanはあくまでも1つのパーティション内のレコードのレンジスキャンであり、パーティションをまたいだレンジスキャンはできないので注意が必要です。
このデータモデルにアクセスするためのインターフェースとしては、シンプルなCRUD APIの他にGraphQLを用いることもできます。また、SQLライクなインターフェースも現在開発中となっています。
Consensus Commitについて
Consensus Commitは、以下の論文で提案されているCherry Garciaというプロトコルを修正・拡張したものになっています。
https://ieeexplore.ieee.org/document/7113278
Consensus Commitでは、トランザクションはクライアント側でコーディネーションされるので、マスタ的な中央管理する役割が必要ありません。これにより、使用するデータベースのスケーラビリティやアベイラビリティ(可用性)を損なうことなくトランザクションを実行することができます。
Write Ahead Logging
Consensus Commitでは、トランザクションが操作する各レコードにWrite Ahead Loging (WAL)を分散させて配置しています。下図は、各レコードがどのように構成されているかを示しています。青い部分が、Consensus Commit が管理するWAL情報です。各レコードには、最後に書き込みを行ったトランザクションのトランザクションID(TxID)やバージョン(Version)、そしてレコードのトランザクションの状態(PREPARED、DELETED、COMMITTED)表すステータス情報(Status)が入ってます。さらに、1つ前のバージョンのアプリケーションデータとそのメタデータが入っています。これは、ロールバックする際に使われます。
それとは別に、トランザクション(TxID)ごとのステータス(COMMITTED、 ABORT)を持っているCoordinatorテーブルもあります。
トランザクションプロトコルについて
Consensus Commitは、同時実行制御方式としてはOCC(Optimistic Concurrency Control)であり、コミットプロトコルとしては2フェーズコミットに似たことをします。また、Lazy Recoveryと呼ばれる、トランザクションがクラッシュした際も、クラッシュしたトランザクションが書き込みをしたレコードを別のトランザクションが読み込んだときに発動するリカバリ処理を行います。
Consensus Commitのトランザクションプロトコルは以下のようになります。
- トランザクションをスタートし、新しいTxID割り当てます。データの読み込みに関しては、実際にデータベースから読み込みを行い、そのデータをローカルメモリ上のread setに格納しておきます。データの書き込みに関しては、この時点では実際にデータベースには書き込まず、ローカルメモリ上のwrite setに格納しておきます。
- データの読み書きが終了したら、Prepareフェーズに入ります。
2-1. 書き込みをする各レコードに対してコンディショナルアップデート(条件はVersion=<前Version>かつTxID=<前TxID>)で、StatusをPREPAREDに変更し、VersionとTxIDを新しいものにし、アプリケーションデータとWALの情報を書き込みます。
2-b. 全てのレコードに対してコンディショナルアップデートが成功した場合は、Prepareが成功したことになります。全てのレコードに対してコンディショナルアップデートが成功しなかった場合は、コンディショナルアップデートが成功したレコードをロールバックし、トランザクションをアボートさせます。 - Prepareが成功したら、Commitフェーズに入ります。
3-a. Coordinatorテーブルに、新TxIDのレコードをStatusをCOMMITTEDとしてコンディショナルアップデート(条件はそのTxIDのレコードが存在しなかったら)で入れます。
3-b. Coordinatorテーブルへの書き込みが成功したら、各レコードのStatusをコンディショナルアップデート(条件はStatus=PREPAREDかつTxID=<新TxID>)でCOMMITTEDに変更します。Coordinatorテーブルへの書き込みが失敗したら全てのレコードをロールバックします。
このプロトコルのポイントは、コンディショナルアップデートを使っている部分です。例えば、Prepareフェーズで各レコードへコンディショナルアップデートを行うことで、同時に同じレコードに対して書き込みを行うトランザクションが複数あったとしても、1つのトランザクションしか成功しないことになります。Coordinatorテーブルへの書き込みも同様に、トランザクションやLazy Recoveryから同時に書き込みを行おうとしてもどちらかしか成功しません。これにより、競合を防ぎ矛盾した状態になることを防ぐことができます。
トランザクションプロトコルについては、以下の資料も参考にしてください。
Lazy Recoveryについて
Lazy Recoveryは、トランザクション中にコミットされていない(StatusがCOMMITTEDでない)レコードを読み込んだときに発動します。
Lazy Recoveryの手順は以下になります。
- リカバリ対象のレコードのTxIDをもとに、Coordinatorテーブルを参照し、そのトランザクションのStatusを調べます。
- StatusがCOMMITTEDなら、ロールフォワードを実行し、トランザクションプロトコルの3–2と同様に、リカバリ対象のレコードのStatusをCOMMITTEDに変更します。
- StatusがABORTEDなら、ロールバックを実行し、WALの情報から前のバージョンへリカバリ対象のレコードのデータを切り戻します。
- CoordinatorテーブルにそのTxIDのレコードが存在しなかった場合は、
4-a. Coordinatorテーブルに、そのTxIDのレコードをStatusをABORTとしてコンディショナルアップデート(条件はそのTxIDのレコードが存在しなかったら)で入れます。
4-b. リカバリ対象のレコードに対してロールバックを実行し、WALの情報から前のバージョンへリカバリ対象のレコードのデータを切り戻します。
トランザクションプロトコルの1の最中にトランザクションがクラッシュした場合は、この時点では何もデータベースに書き込みを行っていないので何もする必要がありません。
トランザクションプロトコルの2で一部のレコードに対するコンディショナルアップデートが成功した後にトランザクションがクラッシュした場合は、リカバリ対象レコードが他のトランザクションによって読み込まれたときにLazy Recoveryが発動し、そのレコードはロールバックされ、クラッシュしたトランザクションはアボートされます。
トランザクションプロトコルの3-aで、Coordinatorテーブルに、新TxIDのレコードをそのStatusをCOMMITTEDとして入れた後でクラッシュした場合は、リカバリ対象レコードが他のトランザクションによって読み込まれたときにLazy Recoveryが発動し、ロールフォワードされます。
つまり、トランザクションの途中でクラッシュが発生し、中途半端な状態のレコードがあったとしてもLazy Recoveryによって、文字通りLazyにリカバリがされるという仕組みになっています。
分離レベルについて
Scalar DBでは、分離レベルとしてSnapshot Isolation(以下、SI)とSerializableをサポートしており、デフォルトではSIになっています。ただし、Scalar DBのSIはANSIで定義されているそれとは少し違っていて、SQL Server等で用いられているRCSI (Read Committed Snapshot Isolation)に近いものになっています。Scalar DBのSIでは、Write Skew anomalyやRead-Only Transaction anomalyのようにSIで通常発生するのanomalyの他に、Read Skew anomalyやPhantom anomalyも発生する可能性があります。Serializableでは、現在はExtra-writeとExtra-readという2つのアプローチが実装されており、それらを選択することができます。これらは、両方ともに、SIで起こりうるanomalyの原因であるanti-dependencyを避けるアプローチになっています。Extra-writeではreadをwriteに変換することでanti-dependencyを排除し、Extra-readではCommitフェーズでread setにあるデータを再度読み直し実際にanti-dependencyが発生しているかをチェックします。
まとめ
本記事では、Scalar DBの概要とScalar DBで用いられているトランザクションプロトコル「Consensus Commit」について説明しました。更にScalar DBの詳細について知りたい方は以下のドキュメント・スライドをご覧ください。
