デッドロック

口座ごとに鍵を分けたら、送金が止まった

鍵を口座ごとに持たせて、別々の口座なら並行に動けるようになりました。ところが送金は 2 つの口座を触ります。減らす側と増やす側の両方に鍵をかけないと、片方だけ減った途中の状態を他人に見せてしまうからです。

A から B へ送る処理は、A の鍵を取り、B の鍵を取り、それから残高を動かします。ちょうど同じ瞬間に、別のスレッドが B から A へ送っていたとします。

スレッド 1                        スレッド 2
A の鍵を取った                    B の鍵を取った
B の鍵が空くのを待つ  ←────────  B の鍵は 2 が持ったまま
A の鍵は 1 が持ったまま  ────────→  A の鍵が空くのを待つ

1 は B が空くまで動きません。2 は A が空くまで動きません。そして、どちらも待っている間は自分の鍵を手放しません。この 2 つは永久に再開しません。デッドロック です。

CPU 使用率は 0% のまま、例外もタイムアウトも出ず、ただリクエストが返らなくなります。しばらくすると、同じ口座に来た他のリクエストも同じ鍵の前に積み上がり、スレッドプールが枯れてサーバー全体が応答を止めます。

待ちの輪ができている

矢印にすると、待ちが輪になっています。

デッドロックの正体はこの輪です。裏を返せば、輪ができないようにさえすれば起きません。

取る順番を、全員でそろえる

輪ができたのは、1 が A から B の順で取り、2 が B から A の順で取ったからです。全員が同じ順序で取ると決めておけば、この形は作れなくなります。

def transfer(src, dst, amount):
    first, second = sorted([src, dst], key=lambda a: a.id)
    with first.lock:
        with second.lock:
            ...

口座 ID の小さいほうから取る、と決めました。B から A への送金でも、内部では A の鍵から取りにいきます。先に A を取れた側が必ず B も取れるので、2 つが向かい合うことがありません。

順序を決めきれない場面では、待ちに上限を設けます。lock.acquire(timeout=2) で取れなければ、持っている鍵をいったん全部返し、少し待ってやり直す。RDB がデッドロックを検出して片方のトランザクションをロールバックし、アプリに再試行させるのも同じ考え方です。

条件は 4 つあるが、潰すのは 1 つでよい

教科書では、相互排除・持ったまま待つ・横取りできない・待ちが循環する、の 4 つがすべて揃ったときにデッドロックが成立すると説明されます。順序の固定は 4 つ目を、タイムアウトは 3 つ目を潰しています。どれか 1 つ崩せば足ります。