Cloud Spanner におけるトランザクションの排他制御

はじめに

Cloud Spanner(以下、Spanner)は無制限にスケーリング可能で、強整合性を保証し、最大 99.999% の可用性を備えたGoogle Cloud のフルマネージド リレーショナル データベースです。

一般的なRDB製品とトランザクションの観点から比較すると、Spannerは外部整合性という強整合性よりも強いレベルでの同時実行制御を行う点が特徴です。Spanner は外部整合性に基づいて平列するトランザクションの実行制御を行うため、開発者が他のRDB製品のようにSELECT for UPDATEで明示的にロックをかけなくても、Spanner の内部の仕組みでデータの整合性を保証します。また、複数のトランザクションが並列している場合にデータにアクセスできるトランザクションを最大化させるため、Spannerは最小でセル単位でロックを取得するという特徴があります。

Spannerを使ったアプリケーションの設計を行う際には、上記のようなRDB製品との違いについて意識して設計することが必要です。

• テーブル定義や実行クエリと、取得されるロックの種類や範囲の関係
• トランザクションが平列で実行された場合のふるまい
• Select for Update のように開発者が意図的に排他コントロールしたい場合の設計

• ロック型読み取り / 書き込み
• 読み取り専用
• パーティション化 DML

本稿では基本的なデータ更新のユースケースで使用されるロック型読み取り・書き込みトランザクションを対象に調査しました。

Spannerのトランザクションの概要

• 外部整合性
• ロックモードと競合
• ロックの取得タイミング
• ロックの範囲
• ロック型読み取り・書き込みトランザクションにおける排他制御の仕組み

外部整合性

外部整合性を説明する前に、簡単にSpannerの内部アーキテクチャについて説明します。

Spanner はコンピューティングノードとストレージ部分で構成されており、複数のゾーンやリージョンにレプリケーションすることで高可用性を担保しています。
主キーの範囲によって分割されたスプリットはあるノードに紐づいて管理されるため、クライアントがトランザクションを発行した場合、複数ノードで分散して処理される可能性があります。

Spannerは、先述のように複数のサーバ（またはゾーン、リージョンなど）を横断してトランザクションが並列実行されている場合でも、システムはトランザクションが順次実行されているかのように振る舞い、複数のサーバ（またはゾーン、リージョンなど）間でのデータ整合性を確保します。これは、外部整合性と呼ばれ、ANSI/ISO SQL標準に定められたSERIALIZABLE（直列化可能性）よりも強力な整合性を保証してくれます。

• ダーティリード
• ノンリピータブルリード
• ファントムリード

ロックモードと競合

Spannerはロックの競合を利用してトランザクション間の排他制御を行います。
公式ドキュメントに記載があるように、4種類のロックモードがあります。

• ReaderShared
  • 読み込み時に取得する共有ロック
• WriteShared
  • 書き込み時に取得する共有ロック
• Exclusive
  • ReaderSharedロックが取得されたカラムに対して書き込みをした場合に取得される排他ロック
• WriteSharedTimestamp
  • Commitタイムスタンプを主キーに含むテーブルに対するレコード挿入時にのみ発生する共有ロック
    なお、WriteSharedTimestampはユースケースが限定されるため、本検証のスコープから外します。

ReaderShared / WriteShared / Exclusive ロックモード間の競合関係は下記表の通りです。
「競合する」ロックモード間では、後述するトランザクションの優先度やCommitタイミングによって、トランザクションのwaitやabort が発生する可能性があります。(詳細は後述)

ロック取得タイミング

ロックの取得タイミングは以下の通りです。WriteSharedロックやExclusiveロックはCommit時に取得されるのがポイントで、SpannerではOracleのようにSELECT for UPDATE で開発者が任意のタイミングで排他ロックを取得することは基本的にできません。^※

※ ヒント句 LOCK_SCANNED_RANGESを使用するとExclusive Lockを意図的に取得するため、劣後トランザクションを実行待ち状態にすることができます。着実に一つずつトランザクションを処理させることで、劣後トランザクションをCommit時にAbortされるよりも効率的な処理が実現可能です。ただし、あくまでヒント句のため、トランザクションの処理順番を厳密に制御する目的での使用は想定されていないようです。

ロック型読み取り・書き込みトランザクションにおける排他制御の仕組み

トランザクション間でロック範囲の競合が発生した場合、Spannerはトランザクションの優先度を比較して、優先度が低いトランザクションをAbortさせます。

SpannerのJavaやGoのクライアントライブラリには、Abort されたトランザクションの自動リトライ機能が備わっているため、これらのライブラリを使って実装していた場合は、AbortされたトランザクションはBEGIN TRANSACTION から再度実行されます。

トランザクションの優先度は、クエリを先に発行した時間が古いトランザクションが優先されるようです。(実機調査したところ、BEGIN TRANSACTION の発行時刻は関係なく、SELECT 1のようなクエリでも先に実行したトランザクションが優先される様子^※）

例えば、以下ようにトランザクションTR1とTR2が平列して実行された場合、最初にSELECT文を発行したTR1が優先トランザクションとなります。TR１とTR2が同じデータに対して操作していた場合でも、TR1はCommitするまで排他ロックをとらないためTR2のクエリも実行できます。 TR1がCommit時にWriteSharedロックやExclusiveロックを取得しCommitが成功後、TR2の操作がTR１の操作と競合していた場合にAbortされます。JavaやGoクライアントライブラリを使用している場合は、TR2は再度BEGIN TRANSACTIONから再実行されます。

※ GoのクライアントライブラリのドキュメントにはAbortされたトランザクションはリトライ時にわずかに優先順位が上がるという記載があるため、トランザクションの初回発行時間も優先順位の決定に関わるようです。

ロック範囲

公式ドキュメントに記載されているように、ロックの範囲については以下のように記載があります。

• Spanner のロック範囲は、レコードおよびカラムの粒度で実施されます。
• 読み取り / 書き込みトランザクション内で行検索を実行する場合は、セカンダリ インデックスを使用して、スキャンされる行の範囲を絞ります。

Spannerのロック範囲はセル単位が最小となり、クエリの検索条件によってはレコード単位やカラム単位でロックされます。テーブルロック用のステートメントは用意されていませんが、テーブル全体をスキャンする(抽出条件なしで SELECT * FROM TABLE する)場合は、テーブル全体に対してロックがかかります。

検証内容

本稿では以下の3つの検証を実施しました。

1. テーブル定義や実行クエリと、取得されるロックの種類や範囲の関係

以下のテーブル定義とクエリの組み合わせについて、ロック取得カラム/ロック行範囲の検証をしました。

• テーブル定義
  • 「セカンダリインデックス無しの場合」と「セカンダリインデックス有りの場合」の2通り。
• クエリ
  • SELECT, UPDATE, DELETE クエリ の検索条件
    • 「主キーで検索」、「セカンダリ インデックスで検索」、「ベーステーブル スキャンで検索(セカンダリインデックス を使用しない検索)」 の3通り。
  • UPDATE クエリ で更新するカラム
    • 「セカンダリインデックス に追加されたカラムを更新した場合」と、「セカンダリインデックスに追加されていないカラムを更新した場合」の2通り
  • INSERT クエリ

2. トランザクションが平列で実行された場合のふるまい

Spannerは外部整合性を担保するため、ANSI SQL で定義されている下記の現象については発生しません。下記を防ぐためにトランザクションがどのようなふるまいとなるかを確認します。

ダーティリード

• 他方のトランザクションで値を更新した場合に、Commit前に他のトランザクションから変更後の値が読み取られてしまうこと。

ノンリピータブルリード

• 同一トランザクション内で読み込み処理を複数回行った際に、別トランザクションによるデータの更新前後で読み込んだ値の内容が変わってしまうこと。

ファントムリード

• 同一トランザクション内で読み込み処理を複数回行った際に、別トランザクションによるデータの挿入や削除の前後で読み込んだ値の内容が変わってしまうこと。

また、並行したトランザクションで起こりうるアノマリーについて、Spannerで発生し得るダーティーライトについてもふるまいの確認を行います。

ダーティーライト

• 複数のトランザクションが同じエンティティを更新した後、あるトランザクションがロールバックした場合に戻すべき値が不明となった状態

その他のアノマリーに対してはこちらのブログにまとまってますので参照ください。

３．Select for Update のように開発者が意図的に排他コントロールしたい場合の設計方法

前述の通り、Spanner は優先トランザクションがCommit実行時にWrite Shared ロックや Exclusiveロックを取得するため、優先トランザクションがCommitされるまでの間、平列するトランザクションも処理を進めます。そのため、クエリ設計によっては、優先トランザクションと劣後トランザクションのCommitタイミングによって結果が変わる場合があります（検証結果の章で後述）。

上記を許容できない場合は、他のRDB製品であればSelect for Update により1トランザクションずつ順番に実行する実装ができますが、Spanner はSelect for Update できないため工夫が必要なため、Commitタイミングによって結果が変わるクエリについて1つ取り上げ、どのような工夫ができるかを考えました。

検証方法

Spanner CLI を使用して、平列するトランザクションを再現して検証しました。

使用したテーブル定義は以下です。

CREATE TABLE Singers (
SingerId   INT64 NOT NULL,
FirstName  STRING(1024),
LastName   STRING(1024),
LockColumn STRING(1024),
) PRIMARY KEY (SingerId);

検証条件にセカンダリインデックスを使用している場合は、以下のセカンダリインデックスを設定して検証してます。

CREATE index SingersByFirstLastName ON Singers(FirstName, LastName);

初期データとして以下を投入しました。

INSERT Into Singers(SingerId,FirstName,LastName,LockColumn) Values (1,'Marc','Richards','1');
INSERT Into Singers(SingerId,FirstName,LastName,LockColumn) Values (2,'Alice','Smith','2');
INSERT Into Singers(SingerId,FirstName,LastName,LockColumn) Values (3,'Alice','Trentor','3');

検証結果

1. テーブル定義や実行クエリと、取得されるロックの種類や範囲の関係

検証の結果を以下にまとめます。前述したように、Spannerのロックはセル単位になります。下記の表において、カラムロック範囲かつレコードロック範囲に属すセルがロックされます。
なお、表記については、以下のように省略しています。

• 表記例
  • select FirstName, LockColumn FROM Singers WHERE LastName=”Richards”; の場合
    • 被参照カラム： FirstName, LockColumn
    • 条件カラム：LastName
  • UPDATE Singers SET LockColumn=’1′ WHERE LastName=”Richards”;の場合、
    • 被更新カラム^※： LockColumn
      ※Spanner は主キーをUpdateできないため、主キーは被更新カラムになりません。
    • 条件カラム：LastName
  • CREATE セカンダリインデックス SingersByFirstLastName ON Singers(FirstName, LastName); の場合、
    • インデックスに追加されたカラム：FirstName, LastName
• ロック種別
  • RS: ReadSharedロック
  • WS: WriteSharedロック
    (RSとWSが同一セルにある場合は、Commit時にExclusiveLockに昇格することを意味します)

• 実行したクエリと、具体的にロックされたカラムは以下の通りです。
  セカンダリインデックス項目をUPDATEした場合やDELETEした場合は、クエリでは明示的に読み取り対象としていないカラムに対してもロックが取得されることがあるようです。（表の太字部）

2. トランザクションが平列で実行された場合のふるまい

以降では、２つのトランザクションであるTR1, TR2を使って各操作の挙動について詳細に見ていきます。
なお、使用する初期データは「1.テーブル定義や実行クエリと、取得されるロックの種類や範囲の関係」と同じものを使用します。

ダーティーリード

• 下記のように、TR1が更新をCommitしていない場合、TR2は更新前のデータを読み込みます。

ノンリピータブルリード

• TR1が優先トランザクションであるパターン１では、TR1でFirstNameのReadSharedLockを取得しているため、TR2の更新はTR1と競合します。TR2は優先トランザクションであるTR1のロックが外れるまでwait状態になりcommitできません。その結果、TR1はトランザクション内で一貫したデータを読み取ることができます。
• TR2が優先トランザクションであるパターン2では、TR2がCommit時にFirstNameのWriteSharedLockを取得してデータを更新します。TR2がCommit後にTR1が読取りを実行するとFirstNameカラムと競合するため、TR1はAbortされるためリピータブルリードは発生しません。

ファントムリード

• 下記のように、TR1で検索範囲に含まれるデータをTR2で挿入してCommitした場合、TR2はwait状態になりTR1のトランザクションが完了するまでcommitされないため、Spanner ではファントムリードが発生しません。TR2はTR1のCommit後にCommitされます。

ダーティーライト

• Spanner では、下記のようにUPDATEのみのTRが並列実行された場合、更新対象カラムはWriteLockのみ取得するため競合せず、劣後トランザクションもCommitされてしまいます。

• ダーティーライトを防止したい場合は、更新対象カラムを参照してReadSharedLockを取得してから更新することで、TR2がCommitされることを防ぎます。

３．Select for Update のように開発者が意図的に排他コントロールしたい場合の設計方法

例えば、Singresテーブルの特定の範囲のFirstNameをすべて同じ値に変更するトランザクション(TR1)と、その特定の範囲に含まれる新規レコードを挿入するトランザクション(TR2)が平列実行されており、TR2が優先トランザクションの場合を考えてみます。

以下のように、TR1が先にCommitするパターン2の場合、TR1、TR2完了後のテーブルは上記要件を満たすことができません。

パターン2で期待される挙動は以下の通りです。

• TR1がCommitするとTR2がCommitするまでWaitになる。
• TR2がCommit後、TR1はAbortされる。

上記のようになれば、TR1はAbort後にクライアントライブラリのリトライ機能を使って再実行されるため、最終的には特定の範囲のFirstNameをすべて同じ値に変更することができます。

このような制御を実現する1つの方法として、例えば、ロック用カラムをトランザクションの最初と最後に更新して意図的にcommit時に優先トランザクション排他ロックを取得するようにカラムAbortされるようなクエリ設計を行うことで、優先トランザクションがCommit後に劣後トランザクションをAbortさせることができます。

パターン1 (TR1が後にCommit)		パターン２ (TR1が先にCommit)
TR1	TR2	TR1	TR2
BEGIN;		BEGIN;
	BEGIN;		BEGIN;
	UPDATE Singers SET LockColumn=session_id WHERE LockColumn is null;		UPDATE Singers SET LockColumn=session_id WHERE LockColumn is null;
	INSERT Into Singers(SingerId,FirstName,LastName,LockColumn) Values (4,’David’,’Lomond’,’4′);		INSERT Into Singers(SingerId,FirstName,LastName,LockColumn) Values (4,’David’,’Lomond’,’4′);
	UPDATE Singers SET LockColumn=session_id WHERE LockColumn is null;		UPDATE Singers SET LockColumn=session_id WHERE LockColumn is null;
UPDATE Singers SET LockColumn=session_id WHERE LockColumn is null;		UPDATE Singers SET LockColumn=session_id WHERE LockColumn is null;
SELECT FirstName FROM Singers WHERE SingerId BETWEEN 1 AND 4;		SELECT SingerId FROM Singers WHERE SingerId BETWEEN 1 AND 4;
UPDATE Singers SET FirstName=’TR1′ WHERE SingerId BETWEEN 1 AND 6;		UPDATE Singers SET FirstName=’TR1′ WHERE SingerId BETWEEN 1 AND 4;
UPDATE Singers SET LockColumn=session_id WHERE LockColumn is null;		UPDATE Singers SET LockColumn=session_id WHERE LockColumn is null;
	commit → OK	commit → wait
commit →　ERROR: spanner: code = “Aborted”, desc = “Deadlock with higher priority transaction.”			commit→ OK
SELECT SingerId FROM Singers;		→ ERROR: spanner: code = “Aborted”, desc = “Deadlock with higher priority transaction.”
SELECT SingerId FROM Singers;		SELECT SingerId FROM Singers;
+————+ | FirstName | +————+ | Marc | | Alice | | Alice | | David | +————+		+————+ | FirstName | +————+ | Marc | | Alice | | Alice | | David | +————+

上記の方法はUpdate文を発行する必要があるためレスポンスは遅くなるのが難点ですが、劣後トランザクションは必ずAbortされるためデータの整合性を保つことができます。

トランザクションの最初と最後で発行するUpdate文の参照・更新範囲を調整することで、任意の範囲にCommit時に排他ロックをかけて平列トランザクションをWaitやAbortさせることができます。

まとめ

本稿では、Spanner の テーブル定義と各クエリ操作におけるロック範囲 とトランザクションが平列した場合における各トランザクションの挙動について調査しました。Spanner は他のRDBと比較してトランザクション周りに特徴があるため、トランザクション内でどのようにロックが取得されているのかを意識した設計をすることが重要と思います。