概要
複数のトランザクションが共通のリソースにアクセスする際に気をつけるものとしてデッドロックがあります。
例えばこのように一方はResource1, Resource2とロックしてアクセスし、もう一方はResource2, Resource1とロックしてアクセスする場合、うまく行けば両方とも成功しますが、
ロックのタイミングによっては一方がロックできず、またアンロックもできない状態（＝デッドロック）に陥ります。
このデッドロックの対策を紹介します。
対策
主に以下の３つありますが、今回はDeadlock Preventionを中心に紹介します。
- Deadlock Prevention
- Deadlock Avoidance
- Deadlock Detection
Deadlock Prevention
Deadlock Preventionはデッドロックの発生自体を防ぐというものです。
No-wait
No-waitロックしようとした際にロックできない場合、すぐに中断するスキームです。
一方が中断してUnlockされたので、もう一方はデッドロックに陥らず処理することができます。
シンプルなので自前で実装しやすいロジックです。
Wait-die
Wait-dieはトランザクション同士のタイムスタンプを比較することでUnlockされるまで待ったり、中断したりするスキームです。
このように
というロジックです。
Wound-wait
Wait-dieはトランザクション同士のタイムスタンプを比較することでUnlockされるまで待ったり、相手を中断させるスキームです。
このように
というロジックです。
Deadlock Avoidance
Deadlock Avoidanceはロックを取得する前にDeadlockが起こらない安全な状態であるかをチェックします。
有名なものとしてはBanker's algorithmがあります。
Deadlock Detection
Deadlock Detectionはデッドロックが発生すること自体は許容するが、発生したデッドロックを検知してRecovery algorithmを実行するというものです。
各RDBは何を採用しているか
MySQL
MySQLはDeadlock Detectionを採用しています。
MySQL :: MySQL 8.0 Reference Manual :: 15.7.5.2 Deadlock Detection
PostgreSQL
PostgreSQLもDeadlock Detectionを採用しているようです。
Deadlocks in PostgreSQL — by Igor Šarčević
Cloud Spanner
GCPのCloud SpannerはDeadlock Preventionのwound-waitを採用しています。
Transactions | Cloud Spanner | Google Cloud
まとめ
デッドロックとその対策について図示してまとめました。
