こんにちは技術研究グループ・テクニカルディレクターの波多野です！ 普段は社内のインフラ、特にデータベース関連の技術的な問題を解決するのを仕事にしています。
弊社ではリレーショナル・データベースとしてはオープンソースの MySQL をとてもよく使っていますが、そんなオープンソースのデータベース界隈で最近よく目にするようになって来たのが 楽観的トランザクション(Optimistic Transaction) という技術です。今回はトランザクション処理の歴史的なところに触れながら、RocksDB に代表される楽観的トランザクションについて簡単に解説したいと思います
はじめに
MySQL を使っているとデフォルトでは REPEATABLE READ のトランザクション分離レベルになっていて、トランザクション内の SELECT は必要に応じて FOR UPDATE を付けて排他ロックし、同時実行しているトランザクションの Read をブロックしながら更新する、ということを開発者のみなさんはごく日常的に実行されていると思います。
近年では、クローズドソースでは Google Spanner 、オープンソースでは MySQL 互換の TiDB, PostgreSQL 互換の CockroachDB, Cassadra 互換にもなる YugabyteDB などSQL 実行可能な分散データベースと呼ばれるタイプのものが登場してきています。これら分散データベースの多くで登場する用語として、楽観的トランザクション (Optimisitc Transaction) と呼ばれる技術があります。
まず現行の MySQL のトランザクションの処理について、基本となる分離レベルから解説し、その後楽観的トランザクションとは何か、について解説してみたいと思います。
SQL のトランザクション分離レベルとは
関係演算を基盤にしたリレーショナルデータベース (RDB) へのクエリを簡単に記述するためのクエリ言語として IBM の System R 開発時に考案され、最初の商用 RDB 製品としてリリースされた Oracle に採用された古い歴史を持つのが SQL です。
実用性と容易さを重視した SQL ですが、多くのデータ処理を引き受けるというデータベースの特性から、実用では同時並行のトランザクション処理が必要になりました。更新を伴う並行処理をどう排他しながら行うか、という問題はとても複雑な処理になります。こうしたトランザクション処理の挙動が製品毎に違うと、利用者にとっては学習コストが高くなり不便であるため、ANSI によって標準化されたのがトランザクション分離レベルです。
４つの分離レベル
並行トランザクションをどう動かせばよいのかという手法が、当時はまだいろいろ産まれ競われていたという時代背景もあり、どう動くかというのを定義するのではなく、「起きて欲しくない現象を定義し、そのうちのどれが起きるのか」という方法によって４つの分離レベルに分類されました。
使われた「起きて欲しくない現象」と、それによる分類
- ダーティリード (Dirty Read) : あるトランザクション中で、他のトランザクションがまだ COMMIT していない更新を読めてしまうこと
- ノンリピータブルリード (Non Repeatable Read) : あるトランザクション中にあるデータが複数回読まれたが、他のトランザクションからの更新でその値が一貫していないこと
- ファントム (Phantom) : あるトランザクション中にあるデータの範囲が複数回読まれたが、他のトランザクションからの追加や削除で、読んだデータの個数自体が一貫していない
| 分離レベル | ダーティリード | ノンリピータブルリード | ファントム |
|---|---|---|---|
| SERIALIZABLE | なし | なし | なし |
| REPEATABLE READ | なし | なし | あり |
| READ COMMITED | なし | あり | あり |
| READ UNCOMMITED | あり | あり | あり |
分離レベルの課題
分離レベルは各種データベース製品がどれくらいのことが出来るのかを分類しようとした試みでしたが、残念ながら様々な問題を抱えています。
性能を犠牲にして最強の SERIALIZABLE を使ってもまだ考慮必要
SERIALIZABLE は３つの起きて欲しくない事象が全て起きないだけではなく、並行トランザクションが直列に実行されたときと同じ結果を保証する、という定義もあります。それでも実行順の保証はありません。
SERIALiZABLE は強く分離を行うために、事実上1個の処理だけが動くような排他制御が行われ性能が大きく損なわれますが、そうして性能を犠牲にしてもほぼ同時に開始されるトランザクションの実行順については、利用者側であるアプリ開発者によってトランザクションの実行順を把握管理する必要性が残ります
単一分離レベルで本質的に発生するロストアップデート
出来るだけ READ は許可しながら WRITE については一貫性を持たせたい、それによって同時実行可能な性能を上げたいという現実的なニーズを満たすために、実用的に使われているのが REPEATABLE READ や READ COMMMITED です。その一方で READ を許可しているために発生してしまうのがロストアップデートと呼ばれる事象です。
以下のような処理の同じトランザクション多数が REPEATABLE READ または READ COMMITED で同時に実行されている場合、その値は不定の状態になってしまいます。(記述されている SQL はあくまで概念です）
| クライアント1 | クライアント2 |
|---|---|
| START TRANSACTION | START TRANSACTION |
| SELECT col FROM table WHERE key=’val’ | SELECT col FROM table WHERE key=’val’ |
| 何かの処理結果がきまる @a | 何かの処理結果がきまる @b |
| UPDATE table SET col=col+@a WHERE key=’val’ | UPDATE table SET col=col+@b WHERE key=’val’ |
| COMMIT | COMMIT |
col は +(@a+@b) ではなく +@a または +@b だけになる可能性があり、値が失われるロストアップデートが発生します。
この現象を防ぐには
- 同時に実行することを阻害してしまうが、必要に応じて分離レベルを SERIALIZABLE に変更しながら使う
- トランザクション特定のデータに関しては他のトランザクションが読まない様に LOCK IN SHARED MODE や FOR UPDATE といったロックをかけ処理を待たせ合う
などの方法が使われます。
「データを読んで・何かして・データを書く」というのはデータ処理の本質であり、その本質でも同時に実行する場合には、 REPEATABLE READ または READ COMMITED の分離レベルを統一して使っているだけでは足りず、データの整合性を保つ責務の大部分はアプリ開発者に委ねられていると考えることが出来ます。
分離レベル混在からアプリ開発者によるロック制御へ
多くの RDB は実行時に分離レベルを選択する機能が備わっていて、適時調整することでロストアップデートを回避することも出来ます。しかしながら多数のトランザクションで適切な共有や排他を分離レベルの動的な変更で互いに行うというのは非常に困難で、この方法が採用されるケースは殆ど見なくなっていると思います。
代わりに一般的なのが、REPEATABLE READ または READ COMMITED をシステムで統一して固定で使い、アプリ開発者が LOCK IN SHARED MODE や FOR UPDATE といった共有や排他のロック制御を明示的に使って、ロストアップデートなどトランザクションの同時実行に関して発生する様々な問題を回避していく、という方法です。
こうした分離モデルに関する問題点は Microsoft Research の “A Critique of ANSI SQL Isolation Levels” 論文に詳しく記載されていますので深く学びたい方はぜひご参照ください
ロック制御で必要になる RDB 別の挙動の把握
オンライン・トランザクション処理 (OLTP) などの同時並行処理を RDB で行う場合には、アプリ開発者による明示的なロック制御が必要になります。一方、あるトランザクション分離レベルにおけるロック制御の挙動は標準化されておらず、データベースの内部実装の影響を強く受けます。
各 RDB 製品別、その分離レベル別で異なる挙動を把握しておくことが必要になりますので、ここでは MySQL に限定してその挙動についてまとめたいと思います
MySQL の REPEATABLE READ
MySQL はストレージエンジンの InnoDB 中心でトランザクション処理が行われていて REPEATABLE READ の分離レベルがデフォルトで使われています。
InnoDB のテーブルスペース内にはシステムテーブルスペースの一部としてロールバックセグメントと呼ばれるログ的なデータ構造が用意されていて、データの更新時の古い方のデータを、更新が COMMIT されるまで保持するようになっています。このようなデータ構造は Undo ログとも呼ばれて、トランザクションをロールバックさせたときにデータを戻すのに使われる他、COMMIT 済みの旧バージョンのデータへの Read をブロックせずに他のトランザクションに参照させるために使われています。
こうして Undo ログを使うことなどで更新中に旧バージョンをロック無しで Read させる手法のことを マルチバージョン・コンカレンシー・コントロール (MVCC) と言います。また MVCC で行っている、ある瞬間の旧バージョンを全て写し取ったかのような方法で同時アクセスを可能にする手法のことをスナップショット・アイソレーションとも言います。
そのスナップショットに対して Read することで矛盾なく Read が出来ることを一貫性読み取り (Consistent Read) と言います。
MySQL の REPEATABLE READ のトランザクション内でのロックのオプションの無い SELECT は一貫性読み取りになります。
最初の Read でタイミングを確定させたスナップショットを形づくり、以降はそのスナップショットのみを使って一貫性読み取りを行います。
FOR UPDATE や LOCK IN SHARE MODE が付いた SELECT や UPDATE など Read を伴う更新クエリはロック読み取り (Locking Read) と呼ばれます。
MySQL のロック読み取りはインデックスで特定行の条件が指定されている場合と、範囲が条件の場合とで挙動が異なります。
- インデックスで特定行が指定されてる場合：対象の行に対してのみ、指定されたロックを取得します
- 範囲が指定されている場合：ギャップロックやネクストキーロックを使って、他のトランザクションからの挿入をブロックします。
ギャップロックやネクストキーロックによって REPEATABLE READ レベルであってもファントムが発生しないのが MySQL の特徴です
MySQL の READ COMMITED
READ COMMITED の場合の一貫性読み取りは毎回新しくスナップショットを形成する方法で行われます。これにより他のトランザクションの COMMIT した更新を読んでしまうというノンリピータブルリードが発生します。
ロック読み取りもギャップロックを使わず該当行のロックを取得するのみとなります。これにより他のトランザクションからの範囲内への挿入を許すのでファントムが発生します。
マスターとスレーブでのレプリケーションにおいて SQL 文を複製する手法で行うとマスターとスレーブでのロック読み取りの結果が異なってしまう可能性があることなどから、READ COMMITED を使う場合の binglog フォーマットは更新行のデータそのものをスレーブに送る ROW フォーマットのみとなります
REPEATABLE READ と READ COMMITED のパフォーマンスの相違点
更新頻度の高いテーブルに対して、トランザクション内から一貫性読み取りを行い、そのトランザクションの他のクエリやアプリの処理で COMMIT までの時間が長い場合に、REPEATABLE READ によって最初のスナップショットを維持し COMMIT するまで大量の更新をロールバックセグメントで保持し続けますので MySQL のパフォーマンスが著しく低下してしまう現象があります
1台の MySQL でオンライントランザクション処理と集計分析的な処理と、ミックスしたワークロードで使う場合などには READ COMMITED が性能的に有利となるケースがあります。詳しくは Percona 社の記事の yakst 翻訳版 InnoDBの分離レベルによるMySQLのパフォーマンスへの影響 記事などをご参照ください。
RocksDB の楽観的トランザクション
Facebook では MySQL のストレージエンジンとして InnoDB ではなく RocksDB を使っている MyRocks を採用していたり、Google の Spanner を参考にオープンソースで新しく実装された大規模な分散データベース、TiDB, CockroachDB, YugabyteDB で使われるなど近年のデータベースのストレージエンジンとして活用されているのが RocksDB です。
InnoDB は B+ ツリーでインデックスを構成し、ロールバックセグメントの Undo ログを使ったスナップショットによる MVCC と、インデックスにおける行ロックを使ってトランザクションの同時実行を行っています。
RocksDB は LSM ツリーを採用したデータベースですが出来ることは InnoDB と似ており、トランザクション開始後にスナップショットのタイミングを設定し、以後の Read はそのスナップショットに対して行うことで REPEATABLE READ な処理を行っています。またトランザクション中の更新もロックを取得して行われます。
加えて RocksDB は、通常のトランザクションモードの他に 楽観的トランザクション (Optimistic Transaction) の機能が提供されています。
これはトランザクション内では更新であってもロックを使用せず、COMMIT 時に更新の衝突が起きていないか検査し、万が一同じデータに対して別の更新が行われている場合は COMMIT せずそのトランザクションはエラーとして終了するというものです。更新衝突によるエラーの処理は、アプリケーションまたは RocksDB を使っているデータベースの上位レイヤーに対応が委ねられます。これが楽観的トランザクションです。
同時更新の衝突が発生した場合にエラー応答するという処理方法は、MySQL の InnoDB クラスターのマルチマスターにおける同時更新でも使われていて一般的になりつつある手法です。データベースとして更新の待ち合わせ管理をしてくれないので違和感を覚える方もいるかもしれませんが、楽観的トランザクションは大量更新がありつつ相互に影響し合う可能性が低い場合に、更新衝突の対応責務をアプリなど上位で引き受けることで、大幅な性能の向上が見込まれるという利点があります。
これからも新しく出て来る大規模分散 RDB においては楽観的トランザクションが標準的なトランザクションの手法になっていく可能性もあり、今後も目が離せない技術になると思います。
