同時実行制御とSQLite3

同時実行制御

Intro

同時実行制御とは, 共有リソースにアクセスする複数のトランザクションを, いかに並列処理しつつ競合によるデータ破壊を回避するかを扱う分野である.
昨今のアプリケーションではクライアントが複数いることは珍しくない. 同時アクセスを許容せず, クライアントからの要求を直列的に処理できれば同時実行制御の課題は解決されるが, アプリケーションのレスポンスは極端に低下し使い物にならない.
パフォーマンスの低下を抑えるためにトランザクションを並列化し, かつリソースの整合性を保証しなければならないため, 同時実行制御を考える必要が出てくる.

Conflict

並列処理されるトランザクションの競合を制御しなかった場合の問題は主に4種類ある.
基本的にデータの一貫性は保証されない.

Dirty Read (w-r)

コミットされていないデータを別のトランザクションから参照できてしまう問題. トランザクションがロールバックされた場合に, 別のトランザクションから参照されていたデータはDirtyになる.

Lost Update / Overwrite (w-w)

別のトランザクションによる書き込みで, 更新したデータが上書きされてしまう問題.

Non-Repeatable Read / Fuzzy Read (r-w)

トランザクション内で別のトランザクションによるデータ更新が反映されてしまい, 同じレコードでも参照するたびに結果が変わる.

Phantom Read / Inconsistent Read (r-w)

同じトランザクション内でも, データの参照結果が増減する. 別のトランザクションによるデータ更新 or 削除が参照できることが原因で発生する.

Isolation

Isolationは分離性や隔離性, 独立性と訳される(本項では分離性とする). 分離性とはトランザクションを並列処理する中で, どこまでトランザクション同士の干渉を回避して読み取り一貫性を保証するかの度合いである.

Consistency and Isolation

分離レベルとはトランザクションの並列性/直列性の度合いを定義したものである. ACID特性の中でも分離性は柔軟解釈されている.
データベースソフトウェアでは分離レベルを選択できるものが多い. これは分離レベルの度合いにより拡張性や性能に大きな影響を与えるためである.

分離レベルは緩いほどパフォーマンスが向上する. 反対に厳しくするほどパフォーマンスは犠牲になる. ただし, 分離レベルを厳しくするほどデータの一貫性は保証されていく. 分離レベルには次のものがある.

1. Read Uncommitted
2. Read Committed
3. Monotonic View
4. Repeatable Read
5. Serializability

Serializabilityは特定のリソースに対するアクセスを同時に1つのトランザクションしか実行させない形式, つまり各トランザクションが完全に直列実行されるため, トランザクションは交差することなく完全に分離される. Serializabilityは最も厳しい分離レベルである. このレベルは同時実行制御に関係する多くの問題が解決されるため一貫性の面においては理想的なレベルであるが, トランザクションが直列化することによりパフォーマンスを大きく損なうため多くの場合採用するに至らない.

少なくない数のクライアントを抱えているアプリケーションやリアルタイム性を求められるアプリケーションの場合, Serializability分離レベルを選択するのは現実的ではない¹.
"では, パフォーマンスを向上しよう"という話になり, トランザクションを並列化させる方向に進んでいく. つまり同時実行制御を考える必要が出てくる.

• トランザクションの並列化を促進する程, パフォーマンスは向上する.
• トランザクションの直列化を促進する程, パフォーマンスは低下する.

ただし,

• トランザクションの並列化を促進する程, 同時実行制御は複雑になる.
• トランザクションの直列化を促進する程, 同時実行制御は単純になる.

Isolation Levels

トランザクションの代表的な分離レベル(ANSI/ISO表記)を次に記載する.
データ一貫性を保証するために全ての分離レベルではDirty Writeを回避する必要がある. 分離レベルが緩い(より並列化させる)ほど同時実行制御は複雑化しデータ破壊のリスクが高まる.

Read Uncommitted

他のトランザクションによるコミット前データの読み込みを許容する分離レベル. トランザクションは極めて並列に実行されるためパフォーマンスは高い. ただし, この分離レベルではDirty Writeは回避されるもののDirty Read, Fuzzy Read, Phantom Read, Lost Updateなど様々な問題が発生するため, 競合が発生する状況下ではデータ破壊の可能性も高くなる.

Read Committed

コミット済みデータが読み込まれることを保証する分離レベル. ただし, トランザクションの途中でも他のトランザクションがコミットしたデータが読み込まれる.
この分離レベルではDirty Readを回避できるが Fuzzy Read, Phantom Read, Lost Updateは回避できない.

Repeatable Read

トランザクションで読み込んだデータはコミットするまで変更されないことを保証する分離レベル.
保証するのは読み込んだデータに対してのみであり, それ以外のレコード追加などは保証されないので範囲指定問合せによるPhantom Readは防げない.

Serializability

完全な一貫性を保証する分離レベル. 全てのトランザクションが直列に実行されているように見える特徴がある.

競合問題と分離レベルの関係をまとめる.

-	Dirty Read	Lost Update	Fuzzy Read	Phantom Read
READ UNCOMMITTED	発生する	発生する	発生する	発生する
READ COMMITTED	発生しない	発生する	発生する	発生する
REPEATABLE READ	発生しない	発生しない	発生しない	発生する
SERIALIZABLE	発生しない	発生しない	発生しない	発生しない

Exclusive control

Shared lock, Exclusive lock

トランザクションの競合が発生すると前述の競合問題が発生する. 競合を回避してデータの一貫性を保証するためには共有リソースへのアクセスを制限するロックメカニズムを導入して排他制御を促進する.

排他制御とは, 他のトランザクションから共有リソースへのアクセスを制限(ロック)するものである. ロックはトランザクションの完了まで保持されたあと解除され, 他のトランザクションはそれまで共有リソースへアクセスすることができない.

ロックは他のトランザクションのアクセスを制限するという特性から, パフォーマンスに大きく影響する. そのためロックにはいくつか形態があり, 用途によって使い分けられる. ロックの形態は大きく2つ存在する.

Shared lock - 共有ロック

トランザクションがデータを読み込む場合のロック方式. データが共有ロックされている間は他のトランザクションでもデータを読み込むことができるが, データを書き込むことはできない.

Exclusive lock - 排他ロック

トランザクションがデータを書き込む場合のロック方式. データが排他ロックされている間は, 他のトランザクションからデータを読み込むことも書き込むこともできない.

また, ロックするデータの範囲をロック粒度(またはロックレベル)という. ロックするデータの範囲にはテーブル全体, 行全体, 特定の列がある. ロック粒度の程度には一長一短がある.

• ロック粒度を小さくするとトランザクションの並列性が高くなる
• ロック粒度を小さくするとトランザクションの競合頻度は高くなる

また,

• ロック粒度を大きくするとトランザクションの並列性が低くなる
• ロック粒度を大きくするとトランザクションの競合頻度は低くなる

Pessimistic mechanism, Optimistic mechanism

ロックを取得する期間も重要である. トランザクションは競合を検知するとデータの一貫性を保証するためにロールバックを実行し, トランザクション処理をキャンセルする. ロックの期間を短くするのは大切だが, 短くし過ぎてロールバックが頻発するのは問題である.

• ロック取得の期間を長くすれば競合の排除を促進できる
• ロック取得の期間を短くすれば競合の排除は抑制される

また,

• ロック取得の期間を長くすると空振り(ロールバック)に終わる頻度は下がる
• ロック取得の期間を短くすると空振り(ロールバック)に終わる頻度が上がる

ただし,

• ロック取得の期間を長くすると別のトランザクションの待ち時間が延びる
• ロック取得の期間を短くすると別のトランザクションの待ち時間が縮まる

さらに,

• ロック取得の期間を長くするとデッドロックの発生確率が上がる
• ロック取得の期間を短くするとデッドロックの発生確率は下がる

ロックにはパフォーマンスの話題がつきもので, 最適なロックの粒度と期間を選択しないとパフォーマンスの低下を招く.

ロックを取得するタイミングには2通りに大別される. 悲観的ロック と 楽観的ロック である.
悲観的ロックはロックの期間を長くとる. 反対に, 楽観的ロックではロックの期間を短くとる. システムの特性にあわせてどちらの方式を採用するかを決める.

Pessimistic mechanism - 悲観的方式

排他制御において, "トランザクションは高頻度で競合する前提"で考えられた悲観的な方式. 主にロックで排他制御を実現する.
悲観的方式では, トランザクションがデータにアクセスし始めた時点からコミットまでロックを保持する. この間, 別のトランザクションがリソースにアクセスすることを制限する.
悲観的方式はトランザクションを直列処理するため, 排他制御の扱いは容易に映るが, デッドロックやパフォーマンスの面で注意が必要である.

Optimistic mechanism - 楽観的方式

排他制御において, "トランザクションは低頻度で競合する前提"で考えられた楽観的な方式. 主に競合検出で排他制御を実現する.
楽観的方式では, トランザクション中に別のトランザクションによるデータ更新がなかったかを検査(競合検出)してからコミットする. トランザクションが更新操作中でも別のトランザクションからの操作は制限されない. コミット時に競合検出された場合は当該トランザクションはロールバックされる.

悲観的方式と楽観的方式は一長一短であり, それだけで優劣をつけるものではなく要件にあって選択すべきものである.
リソースの更新リクエストが頻発すると予想されるシステムでは, 書き込みに最適化させたい場合が多い. このケースでは悲観的方式を選択できる.
リソースの参照リクエストが中心となるシステムでは読み込みに最適化させたい場合が多い. このケースでは楽観的ロックが選択できる.

一般的にRDBMSは書き込み操作に最適化されており, 悲観的方式が採用される².
一方, Webサーバは読み込み操作に最適化されており, レスポンス性を高めるために楽観的方式が採用されやすい.

SQLite3

SQLite3における同時実行制御関連の情報.

ロック粒度

DBMSによってはロックの粒度を行や列単位で指定できるものがある. ただし, SQLiteではデータベース全体のロック粒度しか選択できない.
SQLite.org - Appropriate Uses For SQLite ... High Concurrency

ロック状態

SQLiteは共有ロック, 排他ロックの仕組みを備えており, プロセスを跨いで同時実行されても適切に処理される.
SQLiteのトランザクションには複数のモードが存在し, 各モードや実行内容によって取得されるロック種別が変わる.

UNLOCKED
: 非ロック状態. どのプロセスも書き込み/読み込みしていないデータベースの初期状態.

SHARED
: データを書き込みを伴わずに読み込む場合に取得されるロック. 他のプロセスからの読み込みを許可するが書き込みは許可しない. SHAREDロックは複数のプロセスに保持させることができるため, 他のプロセスからの読み込みに対してオープンである.

RESERVED
: 将来データを書き込む予定だが現状読み込みしかされていない場合に取得されるロック. SHAREDロックとRESERVEDロックを共存させることができるが, RESERVEDロックはある時点で1つしか保持されない.

PENDING
: EXCLUSIVEロックを取得してデータの書き込みを実行しようとSHAREDロックの開放を待機する場合に取得されるロック. 全てのSHAREDロックが開放されるとEXCLUSIVEロックが取得される.

EXCLUSIVE
: データを書き込むために必要なロック. PENDINGロックからEXCLUSIVEロックに状態遷移するため, EXCLUSIVEロックが取得されているタイミングでは他のすべてのロックは解放されている. EXCLUSIVEと他のロックとを共存させることはできない.

See. SQLite.org - File Locking And Concurrency In SQLite Version 3

分離レベル

SQLiteにおける分離レベルはANSI/ISO SQL標準の表記とは異なっており, ロックを取得するタイミングに主眼を置いた表記となっている.

DEFERRED
: トランザクション開始時にはロックを取得せず, データの読み込み/書き込みをする時点までロック取得を延期する. そのため, BEGINステートメントによるトランザクション開始のみでは何のロックも取得されない. ロックの取得がBEGIN～データの読み込み/書き込みまで延期されるため, 別トランザクションによるデータ書き込みの割り込みが発生する可能性がある. (ANSI/ISO SQL標準では READ_COMMITTED に相当. )

IMMEDIATE
: トランザクション開始時にRESERVEDロックを取得する. BEGIN IMMEDIATEによりRESERVEDロックが取得されると, 他のデータベースコネクションはデータベースに書き込んだり, BEGIN IMMEDIATE or BEGIN EXCLUSIVEを実行することができなくなるが, データベースからの読み込みを継続することはできる. ( ANSI/ISO SQL標準では REPEATABLE_READ に相当. )

EXCLUSIVE
: トランザクション開始時にEXCLUSIVEロックを取得する. BEGIN EXCLUSIVEによりEXCLUSIVEロックが取得されると, READ_UNCOMMITTEDの接続を除いた全てのデータベースコネクションからデータを読み込むことができなくなる. データベースへの書き込みについては例外なくトランザクションの完了まで許可されない. ( ANSI/ISO SQL標準では SERIALIZABLE に相当. )

See. SQLite.org - BEGIN TRANSACTION
See. SQLite.org - PRAGMA read_uncommitted

Reference

InfoQ - Web開発者が知っておくべき八つの分離レベル

転用元: Yukiの枝折 - Android: 同時実行制御とSQLite3

以上.

1. eBayやAmazonといった巨大Webアプリケーションが楽観的で緩やかな一貫性保証の方が, 古くからの悲観的メカニズムより拡張性に富んでいることを証明した例もある ↩

2. Oracle Databaseには楽観的ロックのイメージが強いが, 悲観的ロックも指定できる ↩