Cloud Spanner のロックについて

この記事では Cloud Spanner の並行性制御が何であるのか、結果として何を実現しているのかを見てから具体的なロックの実際の挙動について追っていく。
なお分散システムとしての話はあまりないので期待しないように。

この記事では実際の挙動を確認しながら書いているつもりだが、 2021年3月現在の挙動がサイレントに変わることもあることには注意してほしい。

理論寄りのところはまだ Transaction Information Systems を買っただけで入り口までしか見ていないので正しいのかは分からないが、叩き台として今の認識を書いていく。特に理解しなくてはロックの挙動が分からないわけではないので読み飛ばしても良い。

TL;DR

• Cloud Spanner はロックフリーな Read-Only Transction と、堅実にロックを行う Read-Write Transaction の2つのアクセスパスを持ち、 ROMV と呼ばれる方式に最も近い。
• その他技術との組み合わせの結果として分散システムでありながら Serializability と Linearizability を兼ね揃えた理論上最も強い一貫性を実現しており、 Google はそれを External Consistency と呼んでいる。
• ロック周りの挙動については Lock Statistics がリリースされたことで観測しやすくなった。
  • それぞれ conflict する対象が異なる4種類のロックが存在する。
  • 各オペレーションは範囲と列の組み合わせに対して異なるロックタイプのロックを取得する。
  • ロックが conflict した時は優先度によって wait するか abort させる wound-wait でデッドロックを回避する。
    • 優先度はどちらのトランザクションの最初のオペレーションが速いかと、リトライをしているかによって決まる。
• LOCK_RANGE_SCANNED はクエリの時点で先に Exclusive lock を取得することで、 write-after-read のトランザクション同士が conflict を繰り返すようなケースでのリトライを避けるのに使える。

Changelog

• 2022年7月5日: Transaction Tag について追記した。

Cloud Spanner の並行性制御は何なのか

データベーストランザクションは並行実行されることが一般的であり、並行に実行されたとしても何らかの一貫性規則に従った正しい動作をするように保証する並行性制御が行われる。
細部について触れる前に、 Cloud Spanner の並行性制御が何であるのかについて見ていく。

公式ドキュメントでは、 multi-version concurrency control(MVCC) を自称しているが、論文紹介: An empirical evaluation of in-memory multi-version concurrency control の要約でも書かれている通り、MVCC という言葉は「マルチバージョンで実装する」という意味しか持たず、 MVCC の具体的な実装は全く異なるものが複数ある。それぞれ大きく性質が異なるのでまずは具体的に何なのかを確認する。

Cloud Spanner の並行性制御は下記の組み合わせとして説明されている。

• Read-Write Transaction は S2PL(Strict 2 Phased Lock)で Read/Write 共に悲観的ロックをして、 Commit Timestamp ごとに新しいバージョンの値を書き込む。
  • Read-Write Transaction 内の Read ではコミット済の最新のバージョンの値以外が読まれることはない。
• Read-Only Transaction は Read-Write Transaction が書いた過去のバージョンをロックフリーで読む。
  • 過去のバージョンは version GC されるまでは読める。Point-in-time Recovery にも使われる。

プロダクトである Cloud Spanner としてのドキュメントや Spanner としての論文等を含め公式には言及はないが、この組み合わせは ROMV(Read-Only Multiversion protocol) と呼ばれる MVCC の一種と一致することが指摘されている。

https://twitter.com/kumagi/status/812625000284852224

ROMV というアイデアの原典となる論文は1982年か1985年までは遡れるようだがパブリックアクセスではないため、 ROMV の解説が含まれるテキスト Transaction Information Systems(Weikum 本) の "5.5.4 A Multiversion Protocol for Read-Only Transactions" を確認したところ、 update(read-only) transaction と read-only transaction の解説が Spanner のそれらとほぼ一致するため同一であると考えて良いと思われる。何が書いてあるかはこの本を元にした輪読会のメモや講義資料などでも確認できる。（なお、2PL を使う MVCC としてより有名な MV2PL もあるが、 ROMV と違い read-only transaction かどうかで処理を分けるということはせず、 read-write 両方行う transaction でも multiversion から読みつつ Serializability を保証するので異なるという認識。）

• https://scrapbox.io/nikezono/Transactional_Information_Systems_Chapter_5読み会
• https://db.in.tum.de/teaching/ss16/transactions/pdf/chapter5.pdf

ROMV に関する興味深い記述として、この本では

It does so by exploiting versioning only for read-only transactions, thus “picking the low-hanging fruit” in the sense that, say, 10 percent of the complexity of multiversion protocols is sufficient to achieve, say, 90 percent of the benefit.

とも書かれており、 ROMV は他の MVCC ベースのアルゴリズムの10%の複雑さで90%のメリットを得られる手法であるとしている。

Spanner は ROMV を採用しているという前提で Spanner の論文にかかれている技術を見ると、私には下記のように見えた。

• Commit Wait は Commit が終わるまでロックを解放しない S2PL をタイムスタンプに誤差がある分散環境向けに拡張したものとして見ることができる。
  • TrueTime API を使った Commit Wait によって 2PC による atomic commit が必要な複数のシャード、更には Paxos による複数のデータセンター間でのレプリケーションを伴う分散環境でも ROMV に使える External Consistent な Commit Timestamp を割り当てる。
• 目を引くことが多い原子時計や GPS といったハードウェアは TrueTime API の誤差を小さくして Commit Wait の時間を短くして性能を向上するためのもの。

つまり、 Spanner は全く新しいものというよりは、ある程度古典的ですらある ROMV を分散環境で成り立つようにし、性能をできるだけ向上させたものであるという認識をした。

実用上どう関わってくるかというと、過去のバージョンを信用できるものにするための Read-Write Transaction は S2PL を使ったガチガチの悲観的ロックであり、かなり保守的なものとなる。

• 他のデータベースでは存在するような SERIALIZABLE よりも弱い分離レベルのようなロック対象の緩和は許されていない。
• S2PL に更に Commit Wait があるため、ロックは必要なだけ長く保持される。

これらはロックフリーな Read-Only Transaction をどのレプリカでも処理できるようにするために必要なコストであるため、可能な限り Read-Only Transaction を使いつつ、 Read-Write Transaction が必要な場合は可能な限り対象を少なく、時間を短くするようにすることが好ましいと考えられる。

Cloud Spanner の best practices to reduce lock contention として説明されているベストプラクティスに含まれるものを要約すると下記のようになるが、まさにこれらの使い分けについて解説していると言える。

• 可能な限り Read-Only Transaction を使う。
• Read-Write Transaction ではフルテーブルスキャンをしない。
• ロックはできるだけ短くする。
• 大きな Read-Write Transaction よりも細かい単位に分割される Partitioned DML を使う。
• 可能なら全て Read-Write Transaction の中で読むのではなく、先行する Read-Only Transaction を使うことで Read-Write Transaction によるロックを減らす。
• その他スキーマ設計のベストプラクティスに従う。

Cloud Spanner の一貫性

上に書いた並行性制御の結果として Cloud Spanner が実現している一貫性保証を Google は External Consistency と呼んでいる。

• https://cloud.google.com/spanner/docs/true-time-external-consistency?hl=en
  ドキュメント等では External Consistency は下記の2つの性質を兼ね揃えたものとして説明される。

• Isolation(ACID の I) を完全に行い、直列に実行した時と同じ結果となる Serializability

  • 順序は並び替えて良いため、リアルタイム性は要求しない。

• Consistency で最も強く、リアルタイム性を持つ Linearizability

  • 元々マルチオペレーション、マルチオブジェクトな ACID トランザクションではなくシングルオペレーション、シングルオブジェクトに対して定義されている。
  • https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf

しかし、この意味で使われている場面は Spanner 以前には見つけられていない。というのも

• Serializability と Linearizability を兼ねた意味で使われている言葉としては Strict Serializability, PL-SS, Strict 1SR, Strong 1SR) の方が使われる。
• 1981年に定義された External Consistency は1990年に定義された Linearizability よりも古く、比較可能な形で定義されていない。

ようで、これは各所で疑問を持たれている。

• https://qiita.com/kumagi/items/3867862c6be65328f89c#external-consistency
• https://cs.stackexchange.com/questions/71003/external-consistency-vs-linearizability
• https://stackoverflow.com/questions/60365103/differences-between-strict-serializable-and-external-consistency

この混乱についての現時点での私の理解としては下記のようなものになった。

• 外部から観測可能な Commit Timestamp や Read Timestamp などのタイムスタンプが現れる Spanner 及びサービスとしての Cloud Spanner の性質を説明するのに都合が良いため、 Google はこの意味で使っている。
  • 元々 External Consistency は「後から実行が始まったトランザクションは先に実行されたトランザクションよりも大きいタイムスタンプを持つ」とタイムスタンプを使って「トランザクションに対するリアルタイム性」について述べている。
• カテゴリとしては Strict Serializability よりも弱くも強くもなく、同じものとして認識して良い。

この特性は実用上は下記のような意味を持つ。

• いわゆる ACID トランザクションであり、 Isolation として最も強い Serializability を満たす。
  • 全ての Anomaly は発生しない。 Cloud Spanner を使って様々な Anomaly に立ち向かう という記事では実際に検証している。
• トランザクションは全て Read-Write Transaction の Commit Timestamp と Read-Only Transaction の Read Timestamp の一瞬で実行されたかのように順序付けられる。

Cloud Spanner のロックについて

ここまで並行性制御とそれにより実現された性質について述べてきたが、ここからはボトムアップでロックに関わる挙動を確認していく。

検証方法

#utation に伴う lock は commit のタイミングまで取得されず、 mutation 同士の conflict は観測することが難しい。よって、 Read/ExecuteSql から Commit までの間に他のトランザクションの Commit を行うことで、 狙って conflict を発生させることができる。

観測手段として Lock Statistics と RPC の観察を組み合わせて行った。

Lock Statistics

• https://cloud.google.com/spanner/docs/introspection/lock-statistics?hl=en
• https://cloud.google.com/blog/topics/developers-practitioners/lock-statistics-diagnose-performance-issues-in-cloud-spanner

Cloud Spanner は発生した Conflict が起こった最初のキーを使って集約された統計値を SPANNER_SYS.LOCK_STATS_TOP_{MINUTE,10MINUTE,HOUR} テーブル（実行計画を見ると実体はビューのようだが）で提供している。

LOCK_STATS_TOP_* テーブルは下記の値を持つ。

column	desc
INTERVAL_END	集計期間の終わり。LOCK_STATS_TOP_MINUTE ならこれから [INTERVAL_END - 1m, INTERVAL_END) のウィンドウが1つの row として集計される。
ROW_RANGE_START_KEY	BYTES 型だが、 conflict したロック範囲の始めのキーの文字列表現がそのまま入っているためキャストすると読むことができる。
LOCK_WAIT_SECONDS	ロックで発生した wait(単位は秒) の合計
SAMPLE_LOCK_REQUESTS	ROW_RANGE_START_KEY に対するロックの詳細を以下のフィールドとして持つ ARRAY<STRUCT>。
SAMPLE_LOCK_REQUESTS[].column	conflict した列の名前(table.column 形式)
SAMPLE_LOCK_REQUESTS[].lock_mode	column に対して要求したロック
SAMPLE_LOCK_REQUESTS[].transaction_tag	ロックを要求したトランザクションに設定された transaction tag

このテーブルは stats であり LOCK_WAIT_SECONDS は合計、 SAMPLE_LOCK_REQUESTS はそのキーに関わる全ての conflict が発生した列へのロックから20件のみが記録されている。個々の conflict を確認するためのものではないが、集計期間で1件だけ conflict を起こすことで特定の conflict のみの値を確認することが可能。例えば SPANNER_SYS.LOCK_STATS_TOP_MINUTE は1分ごとに ROW_RANGE_START_KEY で集約された値となるため、前後1分のウェイトを入れることで確実に1回の conflict における値を確認することができる。

(追記)Transaction Tag

2021年10月から Transaction Tag を設定した値が SAMPLE_LOCK_REQUESTS[].transaction_tag として得られるようになったため、それぞれどのトランザクションが conflict を起こしているのかを lock stats から確認できるようになった。observability を高めることができるため、アプリケーション内のコード内に存在するそれぞれの Read Write Transaction に対応するトランザクションタグを設定すると良い。

https://cloud.google.com/spanner/docs/introspection/troubleshooting-with-tags?hl=en#limitations

The length of a tag string is limited to 50 characters. Strings that exceed this limit are truncated.

現在 Transaction Tag には50文字までの制限があるため、色々な情報から複雑なタグ文字列を自動生成することには限界があることに注意すること。

https://cloud.google.com/spanner/docs/introspection/transaction-statistics?hl=en

When you assign a TRANSACTION_TAG, statistics for transactions that have the same tag string are grouped in a single row in transaction statistics table. The set of all columns that are written by the transactions are added to the WRITE_CONSTRUCTIVE_COLUMNS field and the set of all columns that are read are added to the READ_COLUMNS field.

Transaction Tag は Lock Stats テーブルだけでなく、 Transaction Stats テーブルにも Transaction Tag が同一のトランザクションは全て Transaction Stats 上で1行にまとめられるという形で影響を与える。タグを設定しないよりも情報量が減ることを避けるには、コード上異なるトランザクションに緩く共通するタグを付けるのではなくユニークなタグを付けるようにすることが好ましいと考えられる。

RPC の観察

gRPC interceptor によるタイミングの可視化

RPC のタイミングを見ることでどの RPC の時点で conflict したかどうかを確認できる。
この記事で取り上げるシーケンス図は gRPC interceptor を使って、実際の RPC のタイミングをシーケンス図として出力することで、どの RPC の時点で conflict して wait が発生したかを可視化している。

Aborted になった RPC の message の収集

各 RPC は Aborted になった時の message として Lock Conflict の詳細を文字列で返す。

Transaction was aborted. It was wounded by a higher priority transaction due to conflict on keys in range [[0], [0]), column PRIMARY KEY in table tbl.

この文字列の中には衝突したキー範囲（開区間、閉区間の区別あり）とテーブル名、ロック対象の列名が含まれている。

• 統計値ではないため、その lock conflict の情報が直接得られる。
• Aborted の時にしか得られないため、 conflict の結果発生した wait は観測できない。
• ロック範囲の終端が得られ、閉区間・開区間のどちらかも確認できる。

Dead Lock Prevention(Wound-Wait)

一般的にデータベーストランザクションは細かい粒度で複数の対象をロックするため、ロックを要求した対象が既に他のトランザクションによってロックされていた場合には常に wait をするとお互いに wait するデッドロックが発生する危険がある。
Spanner では Wound-Wait というデッドロック回避アルゴリズムを採用している。このアルゴリズムはロックを要求した対象が既にロックされていた場合に、ロックを既に取得しているトランザクションとどちらが優先度が高いかでロックの解放を待つ(wait)か、 abort させてロックを奪う(wound)かのどちらかを選ぶことでお互いにロックすることを避ける。

優先度は

• Deadlock detection によるとトランザクションの最初のオペレーションが早い方が高い。
  • BeginTransaction がどちらが早いかは影響しない。
    • BeginTransaction は write pool に入っているトランザクションは予め発行されているため影響しない方が都合が良い。詳解 google-cloud-go/spanner — セッション管理編
      を参照。
• Retrying Aborted Transactions によると同じセッションの前のトランザクションが abort している場合は優先度が上がる。

優先度の実例

通常はオペレーションが先に行われたトランザクションが優先度が高くなる。

この例では、 Session2 の mutation を含む Commit は WriterShared lock を要求するため、 Session1 が ExecuteStreamingSql で取得した ReadShared lock と conflict する。
Session2 の最初のオペレーションである Commit は Session1 の最初のオペレーションの ExecuteStreamingSql よりも後なので Session2 の方が優先度が低く、 Commit して ReadShared lock が解放されるまで wait する。wait 時間はそのままレイテンシの悪化としてユーザに影響することが多い。

この wait 時間が主に lock stats の LOCK_WAIT_SECONDS として記録される。

ROW_RANGE_START_KEY	LOCK_WAIT_SECONDS	SAMPLE_LOCK_REQUESTS
tbl(0)	2.997452	[(tbl._exists, ReaderShared), (tbl._exists, WriterShared)]

何もロックを行わないとしても、最初のオペレーションが早い方が高い優先度を持つ。

この例では実際にロックを取得するオペレーションは上の例と全く同じ順序で行われているが、Session2 の Commit 時点で Session1 を abort させて、 Session2 が成功するという結果に変わる。 これは Session2 の SELECT 1 が最も先に実行されていることで Session2 の方が優先度が高くなったためである。一般的にクライアントライブラリは abort された read write transaction をリトライするように作られており成功するまで最初から処理をしなおすことになるので、 abort の発生もレイテンシの悪化としてユーザに影響することが多い。

wait ではなく abort させた(wound) 時でも lock stats には記録される。この際の LOCK_WAIT_SECONDS がどのからどこまでの時間を記録しているのかは現在まだ分かっていない。

ROW_RANGE_START_KEY	LOCK_WAIT_SECONDS	SAMPLE_LOCK_REQUESTS
tbl(0)	0.513268	[(tbl._exists, ReaderShared), (tbl._exists, WriterShared)]

このように最初のオペレーションの時間が主に優先度を決めるが、abort されたトランザクションの後は同じセッションのトランザクションの優先度が上がるという仕様がある。

Retrying Aborted Transactions より

When a transaction aborts, the application can choose to retry the whole transaction again. To maximize the chances of successfully committing the retry, the client should execute the retry in the same session as the original attempt. The original session's lock priority increases with each consecutive abort, meaning that each attempt has a slightly better chance of success than the previous.

同じ順序のオペレーションを含むトランザクション同士でも、前回トランザクションが abort されたセッションは優先度が上がって成功するようになったことが分かる。これにより、 abort とリトライを繰り返して処理が進まなくなることをある程度は避けられる。

ここまで Cloud Spanner の wound-wait の挙動について確認した。
結果として abort と wait のどちらが起こるかは優先度によるが、どちらもパフォーマンスに影響するため確認した場合は改善を検討すると良い。

追記: Deadlock with higher priority transaction について

ここまで見てきた Transaction was aborted. It was wounded by a higher priority transaction ではなく Deadlock with higher priority transaction のエラーでトランザクションが abort される場合がある。

例として下記のケースで発生する。

INTERVAL_END	ROW_RANGE_START_KEY	LOCK_WAIT_SECONDS	SAMPLE_LOCK_REQUESTS
2021-03-29T06:23:00Z	tbl(0)	6.010479	[(tbl._exists, ReaderShared), (tbl._exists, WriterShared), (tbl._exists, ReaderShared), (tbl._exists, WriterShared), (tbl.updated_at, ReaderShared), (tbl.updated_at, WriterShared), (tbl.updated_at, ReaderShared), (tbl.updated_at, WriterShared)]

（次のクエリと比較しやすいようにフィルタしていないが、 WHERE pk = 0 したときも同様の結果になる。）

上では2つの commit は同じ pk に対して InsertOrUpdate をしているが、別の pk を指定した場合だと下記のように通常の Transaction was aborted. It was wounded by a higher priority transaction となる。

INTERVAL_END	ROW_RANGE_START_KEY	LOCK_WAIT_SECONDS	SAMPLE_LOCK_REQUESTS
2021-03-29T05:32:00Z	tbl(0)	6.813928	[(tbl._exists, ReaderShared), (tbl._exists, WriterShared), (tbl.updated_at, ReaderShared), (tbl.updated_at, WriterShared)]
2021-03-29T05:32:00Z	tbl(1)	0.815834	[(tbl._exists, ReaderShared), (tbl._exists, WriterShared), (tbl.updated_at, ReaderShared), (tbl.updated_at, WriterShared)]

これらの例から Deadlock with higher priority transaction は Transaction was aborted. It was wounded by a higher priority transaction において wait しているキーと同じキーが原因で abort された場合の特殊なケースであり、同様に扱っても良いと考えられる。
Deadlock with higher priority transaction の方はどのキーが原因かがエラーメッセージからは確認できないという実務上の差があるため、どのキーが　conflict しているかは transaction stats を見て確認すると良い。
これらが高い頻度で起きる場合は後述の LOCK_SCANNED_RANGES=exclusive も検討する。

ロック種別について

複数種類のロックがあるという場合、 Multi-Reader のための共有ロックと、Single-Writer のための排他ロックの2種類を使う MRSW lock が身近だが、 Cloud Spanner ではロックが4種類存在する。それぞれの特徴を説明すると下記のようになる。

• 原則として Read と Write のみが衝突する
  • 特定の値への Read のためのロック同士は衝突せず共有可能(ReadShared lock)
  • 特定の値への Write のためのロック同士は衝突せず共有可能(WriteShared lock)
    • Read を伴わない wlind write が衝突しない。
• トランザクションが特定の値に対して Read と Write 両方をする場合は排他するためにロックアップグレードを行う(Exclusive lock)
• allow_commit_timestamp=true の列がキーとして指定された場合は同じ Commit Timestamp にならないように排他(WriterSharedTimestamp lock)

既に取得されているロック(granted)がある列に対してロックを要求(requested)した際に、ロックを取得できる(Compatible)か衝突(Conflict)するかを示した表が下記のようになる。

Requested＼Granted	No Lock	ReaderShared	WriterShared ※	WriterSharedTimestamp	Exclusive
ReaderShared	Compatible	Compatible	Coflict	Conflict	Conflict
WriterShared	Compatible	Conflict	Compatible	N/A	Conflict
WriterSharedTimestamp	Compatible	Conflict	N/A	Conflict	Conflict※
Exclusive	Compatible	Conflict	Conflict	Conflict ※	Conflict

※ 2020年3月現在、公式の Lock mode conflicts テーブル では Exclusive lock と WriterSharedTimestamp lock が conflict することはないため N/A としているが、あとで説明するようにクエリに LOCK_SCANNED_RANGES=exclusive ヒントを設定すると Exclusive lock を WriterSharedTimestamp lock を conflict させることができたのでこれが実際の挙動であると判断した。おそらくドキュメントは LOCK_SCANNED_RANGES ヒントについて考慮されていないと考えられる。

WriterSharedTimestamp lock

WriterSharedTimestamp lock はキーの一部として allow_commit_timestamp=true な列が含まれる時に現れる。

次のようなスキーマに対して insert を行った時の lock stats を見ることで、 WriterSharedTimestamp lock の実在が確認できる。

CREATE TABLE CommitTimestampKeyTable (
	pk TIMESTAMP OPTIONS (allow_commit_timestamp=true),
	col INT64,
) PRIMARY KEY (pk)

ROW_RANGE_START_KEY	SAMPLE_LOCK_REQUESTS
committimestampkeytable(294247-01-10 04:00:54.775807+00:00)	[(CommitTimestampKeyTable._exists, Exclusive), (CommitTimestampKeyTable._exists, WriterSharedTimestamp)]

294247-01-09T20:00:54.775807-08:00, 294247-01-10 04:00:54.775807+00:00 は spanner.commit_timestamp() に対応するプレースホルダーの値だと考えられる。

WriterSharedTimestamp lock が何故必要なのかについては、 commit timestamp はロックを全て取得してコミットを行うタイミングになって初めて確定するためロックの時点ではプレースホルダーであることが関係していると考えられる。例えば未来の未知な時間への insert 時に同じ commit timestamp の行が作られないようにするためには WriterShared lock のような共有ロックではなく排他ロックをする必要がある。Providing your own value for the commit timestamp column にあるように具体的なタイムスタンプ値をキーに指定して insert することもできるが未来は指定できないことも合わせて、実際の commit timestamp が確定した時にその値に対応する行が存在しないことを保証していると考えられる

mutation ごとのロックタイプ

Lock Statsistics やエラーメッセージからも分かるように、 Cloud Spanner のロックは特定のキー範囲に対して列ごとに取得され、一つの mutation であってもカラムごとに別の種類のロックを取得する。それぞれのオペレーションで各列にどのロックが取得されるのかを確認した結果を下記の表に示す。

primitive	range	key(_exists)	明示した非キー	その他非キー	備考
insert mutation	unique	Exclusive ※1	WriterShared	No Lock	insert 済の場合は失敗し、更新も行うので key は Exclusive
update mutation	unique	ReaderShared	WriterShared	No Lock	insert を伴わないが存在確認するので key は ReaderShared
insert_or_update mutation	unique	WriterShared ※1	WriterShared	No Lock	有無に限らず成功する blind write
replace mutation	unique	WriterShared ※1	WriterShared	WriterShared	interleave されている子も含めた行の全ての列の delete と insert_or_update の組み合わせの blind write
delete mutation	range	WriterShared ※1	WriterShared	WriterShared	有無に限らず成功する blind write, 列指定はなく全ての列が WriterShared lock される
read	range	ReaderShared	ReadShared	No Lock	存在確認が要るためか columns への指定の有無に関わらず 常に _exists を読む

これにより mutation であっても _exists を存在確認のために Exclusive lock しなければならない insert 同士は conflict し、 update 同士や insert_or_update 同士は conflict しないことが分かる。つまり、必ずしも read や query が先行しない mutation = blind write ではなく、 blind write できる部分とそうでない部分が混在することとなる。

このように列の粒度で異なるロックが取得されることは最大限にオペレーションが並行実行される余地を残しつつ、 conflict により External Consistency を保証することに寄与していると考えられる。

余談: blind write の理論的根拠に対する疑問

ところで、古典的には S2PL を使って Serializable を実現する場合、 write lock は排他となっていることが多く、 Spanner の論文でも blind write や WriterShared lock については特に触れられてはいない。

Aside: Locking in Spanner に

In Spanner, we are able to leverage the timestamps assigned to transactions to allow write locks to be shared in many cases.

と書かれておりタイムスタンプが付いていることが理由であるとされているので、 Read-Only Transaction だけでなく Read-Write Transaction においても MVCC の恩恵を受けていると考えられる。

kumagi さんの Advent Calendar の一連の記事などを読むと、通常 S2PL で作られるスケジュールは CSR(Conflict Serializability) であり、各所(1, 2)で

Blind writes appear in any schedule that is view serializable but not conflict seralizable.

のように CSR では blind write は許されないという旨の記述が出てくる。これができる理論的根拠についてはまだ確信が持てていないが Transaction Information Systems の 5.5.4 で

In fact, the ROMV protocol generates only schedules in the MCSR subclass

と書かれており、 ROMV も MCSR(Multiversion Conflict Serializability) の一部のスケジュールであるから CSR よりも広いスケジュールが許されることと関係があるのではないかと考えている。

参考: MCSR の conflict が r-w (read-write) だけなのはなぜなのか？

セカンダリインデックスに対するロック

更新対象のテーブルにセカンダリンデックスがある場合、テーブルだけでなくセカンダリインデックスも更新するため対応するロックが取られる。（TODO: 整理したい）

• ロックに現れるセカンダリインデックスの構造
  • _exists はセカンダリインデックスのキーとテーブルの主キーを構成する全ての列の情報を持つ。
  • STORING に指定された列は個別の列として保存される。
  • キーの一部ではなく STORING に指定されていない列はセカンダリインデックスには含まれない
• テーブルに行を新しく挿入する場合
  • 更新した行に対応するセカンダリインデックスのキー範囲がロックされる
  • _exists と STORING 列が WriterShared ロックされる。
• 既存の行の STORING 対象の列だけ更新する
  • セカンダリインデックスのロック範囲は更新するキー
  • _exists のロックタイプは ReadShared
  • 更新した列のロックタイプは WriteShared
• 既存の行のインデックスのキーに含まれる列を更新する
  • _exists と STORING 列のロックタイプは WriterShared
• 既存の行のインデックスキーでも STORING でもない列を更新する
  • セカンダリインデックスは更新されないのでロックされない。
• 既存の行を削除する
  • ロック範囲は削除対象のキー
  • セカンダリインデックスの全ての列のロックタイプは WriterShared

SQL クエリに対するロック

理論的には SQL クエリは集合ベースであるため、集合に含まれる行が増えるファントムを防止するためには行だけのロックでは不足しており WHERE 句に書かれた述語に対応する集合が変化しないことを保証する predicate lock のようなものが必要となる。predicate lock を評価することはコストが高いので、 Cloud Spanner だけでなく実際のデータベースでは近似としてのキー範囲に対するロックが使われる。

例えば、下記のクエリのロック範囲について考える。

SELECT SingerId
FROM Songs@{FORCE_INDEX=SongsBySongName}
WHERE SongName LIKE "The%z"

spanner-cli で確認した実行計画は下記のようになっている。

+----+-------------------------------------------------+
| ID | Query_Execution_Plan (EXPERIMENTAL)             |
+----+-------------------------------------------------+
| *0 | Distributed Union                               |
|  1 | +- Local Distributed Union                      |
|  2 |    +- Serialize Result                          |
| *3 |       +- FilterScan                             |
|  4 |          +- Index Scan (Index: SongsBySongName) |
+----+-------------------------------------------------+
Predicates(identified by ID):
 0: Split Range: (STARTS_WITH($SongName, 'The') AND ($SongName LIKE 'The%z'))
 3: Seek Condition: STARTS_WITH($SongName, 'The')
    Residual Condition: ($SongName LIKE 'The%z')

このクエリの述語は SongName LIKE "The%z" だが、実際のロックは Seek Condition である STARTS_WITH($SongName, 'The') を元に設定される。
集合としては ($SongName LIKE 'The%z') ⊂ STARTS_WITH($SongName, 'The') であり、 STARTS_WITH($SongName, 'The') は Seek Condition として使えるように、ロックするキーの範囲として使うのに都合が良いためである。

このクエリのロック範囲は実際にロックを conflict することで確認できる。@{LOCK_SCANNED_RANGES=exclusive} を使った範囲全体の Exclusive lock と conflict させた時のシーケンスと lock stats を示す。

INTERVAL_END	ROW_RANGE_START_KEY	LOCK_WAIT_SECONDS	SAMPLE_LOCK_REQUESTS
2021-03-10T09:44:00Z	_Index_SongsBySongName(The)	0.592508	[(_Index_SongsBySongName._exists, Exclusive), (_Index_SongsBySongName._exists, Exclusive)]

lock stats の方には conflict の最初のキーしか現れていないが、 RPC が abort された時に返ってくる range [[The], [Thf]), column PRIMARY KEY in table SongsBySongName から、 STARTS_WITH($SongName, 'The') の前方一致が [The] <= [$SongName] < [Thf] の区間になっていることが分かる。 $SongName LIKE 'The%z' の全ての値がこの区間に含まれるため、この区間をロックすることでファントムは防がれている。

なお、下記のクエリのように Seek Condition が存在しないフルスキャンの場合はキー範囲を狭めることができない。

EXPLAIN SELECT SingerId
FROM Songs@{FORCE_INDEX=SongsBySongName}
WHERE SongName LIKE "%z";

+----+------------------------------------------------------------------+
| ID | Query_Execution_Plan (EXPERIMENTAL)                              |
+----+------------------------------------------------------------------+
| *0 | Distributed Union                                                |
|  1 | +- Local Distributed Union                                       |
|  2 |    +- Serialize Result                                           |
| *3 |       +- FilterScan                                              |
|  4 |          +- Index Scan (Full scan: true, Index: SongsBySongName) |
+----+------------------------------------------------------------------+
Predicates(identified by ID):
 0: Split Range: ($SongName LIKE '%z')
 3: Residual Condition: ($SongName LIKE '%z')

このクエリで同様の conflict を起こすと、下記のようになる。

It was wounded by a higher priority transaction due to conflict on keys in range [[<null>], [<end>]), column PRIMARY KEY in table SongsBySongName.

エラーメッセージから、全ての値よりも前にある NULL から全ての値よりも大きい <end> までと、テーブルやセカンダリインデックスの範囲全体に及ぶことが分かる。

ここまででも見たように、 Read-Write Transaction の中でクエリを発行しなければならない場合は、ロック範囲が広がりすぎないようにセカンダリインデックスの定義も合わせて検討する必要がある。ドキュメントの
Transaction - Locking の記述も引用する。

When performing row lookups inside a read-write transaction, use secondary indexes to limit the rows scanned to a smaller range. This causes Cloud Spanner to lock a fewer number of rows in the table, allowing concurrent modification to rows outside of the range.

なお、ロック範囲の決定についてはあまりドキュメント上の説明はないが、論文 Spanner: Becoming a SQL System の 4. QUERY RANGE EXTRACTION の中に、 Lock range extraction として触れられており、一連の静的、動的な range extraction の結果として実際の範囲が決まると考えられる。

Cloud Spanner の範囲ロックは MySQL 等のネクストキーロックのように行の有無に左右されるのではなく、スキャン対象となる範囲がロックされる。LIMIT の有無などにも影響されない。

なお、 DML は ExecuteSql RPC の時点で ReaderShared lock を取得し、 Commit の時点で更新対象に対して WriterShared lock を要求するという形となる。

LOCK_SCANNED_RANGES について

2020年12月 にステートメントヒントとして LOCK_SCANNED_RANGES が実装されている。これはクエリの時点で ReadShared lock ではなく Exclusive lock を要求するようにするヒントである。

Cloud Spanner always enforces serializability. Lock mode hints can affect which transactions wait or abort in contended workloads, but don't change the isolation level.

とあるように、Cloud Spanner では前述のデフォルトのロックの使い分けで常に Serializability を保証するため、これは他のデータベースにおける隔離レベルや SELECT FOR UPDATE のような性能と isolation のトレードオフをする機能とは異なる。

何に必要なのかというと、 wound-wait とリトライの起こり方をコントロールするために使う。通常は Commit のタイミングまで書き込みのロックは取られないので、 ReaderShared lock 同士では conflict せずに、 Commit のタイミングで Exclusive lock にアップグレードされるタイミングで abort が発生し、リトライが必要になる。

今回は DML の UPDATE 文を使ったインクリメントを例として見ていく。なお、 DML でなくても SELECT 文の後で mutation を行うなど、特定の値を読んだ後に書き込むような処理には一般的に当てはまる。

並行する UPDATE 文が、 ExecuteSql 実行の時点では abort も wait もなしに処理されているが、 Commit の時点で優先度が低い Session2 のトランザクションを abort していることが確認できる。最終的に両方の処理を成功させるには、 abort されたトランザクションは最初からリトライする必要がある。

リトライ前に行った処理は無駄になり、リトライのための backoff の wait 及び最初から処理をやり直すことから、レイテンシ、負荷の双方で不利となる。
上と同じ処理を LOCK_SCANNED_RANGES ヒントで Exclusive lock を取得するようにすると、次のようになる。

ExecuteSql の時点で優先度が低い Session2 が wait するようになり、 abort が発生しなくなったことが分かる。結果的にリトライも必要なくなり、処理が減って負荷が減ることや、レイテンシが改善することが期待できる。

なお、このような高い頻度での write-after-read が abort を繰り返すケース以外ではデフォルトである LOCK_SCANNED_RANGES=shared の方が先行する read を他の ReadShared lock と共有可能なままにできるのでどちらが良いのかはアクセスパターンによる。

LOCK_SCANNED_RANGES の説明によるとヒントでしかないので、 LOCK_SCANNED_RANGES による排他ロックは Cloud Spanner の外側の排他制御には使えない。例えば、リーダーに何かがあった場合など、任意のタイミングでトランザクションが既に abort されてロックが解放されているが、次のオペレーションまでクライアントは知り得ないというような場合があると考えられる。

TODO

• Foreign Key とロック
• Check Constraints とロック
• Deadlock with higher priority transaction と Transaction was aborted. It was wounded by a higher priority transaction の違い