はじめに

あるプログラムが同時にN process以上起動してほしくないという状況はよくあります。例えば、

cronで定期実行しているプログラムがバッチ突き抜けを起こして、同じプログラムが平行に走りだしてしまうと困るので、該当のプログラムの同時実行数がN <= 1であることを保証したい
平行で実行しても安全なように設計されているが、無制限に該当プログラムを起動してしまうとサーバーへの負荷が大きすぎるため、該当のプログラムの同時実行数が <= Nであることを保証したい

1のケースでは、N = 1のセマフォ (ロック) が必要です。これは、わざわざセマフォを利用せずともProc::PID::Fileのようなライブラリがあったりします (Proc::PID::FileはPerlのPackageですが、おそらくほかの言語にも似たようなものがあるでしょう)。ただし、こちらローカルのファイルシステムを利用しているので、別のサーバーで同じプログラムが同時に実行されることを防ぐことはできません。
2のケースではN >= 2の一般的なセマフォが必要です。セマフォは一般にプロセス間で共有可能であり、基本的にどの言語もセマフォを操作するためのインターフェイスを提供しているでしょう。ただし、セマフォの後片付けには注意する必要がありますし、やはりサーバーをまたいでの共有は難しいです。

さて、このようにサーバー間で共有できるセマフォが欲しくなるようなことが時々ありつつも、いざやろうとするとなかなか難しいものです。そこで、本稿ではこれを実現する方法について考えていきます。本稿で記載する内容は、まだ未検証の部分も多く筆者自身も実際に仕事の現場で使用しているわけではないということをご了承ください。

MySQLを使う

名前付きロックを使う

MySQLには名前付きのロックを確保できる機能[1]があるのでそれを使う。GET_LOCK(str, n)でstrという名前のロックが獲得できる。nはロック獲得のtimeout (sec) である (負の場合はtimeoutなし)。また、RELEASE_LOCK(str)で当該ロックを開放できる。名前付きロックは、ロックを獲得したセッションに所有され、当該セッション以外からはロックを解放できない。また、当該セッションが終了した際にもセッションが抱えているロックは全て解放される。

セマフォのサイズがN = 1であれば、上述の名前付きロックを使って簡単に実現できる。

GET_LOCK('name-sem', -1)
# critical section
RELEASE_LOCK('name-sem') # or EXIT(n)

RELEASE_LOCKを忘れたとしても、プロセスが終了した (MySQLとのセッションが破棄された) 時にロックが解放されるのでリソースの返却漏れが発生しないのはよい。

問題は、N >= 2のセマフォ。名前付きロックはセッション間で共有ロックできないので、セマフォのサイズ分の名前付きロックを用意するようにしてみる。

SEM_NAME := 'name-sem'
SEM_SZ := 5

SEM_PROCESS_LOCK := ""
SEM_WAIT_LOCK := "${SEM_NAME}-wait"

GET_LOCK($SEM_WAIT_LOCK, -1)

BUSY_WAIT:
  WHILE 1
    FOR i := 0; i < $SEM_SZ; i++
      SEM_PROCESS_LOCK = "${SEM_NAME}-${i}"

      IF GET_LOCK($SEM_PROCESS_LOCK, 0)
        RELEASE_LOCK($SEM_WAIT_LOCK)
        BREAK BUSY_WAIT
      END IF
    END FOR

    SLEEP(n) # n >= 0
  END WHILE

# critical section

RELEASE_LOCK($SEM_PROCESS_LOCK) # or EXIT(n)

セマフォ上で待機している最初のプロセスがbusy waitになるのがいまいち。2番目以降の待機プロセスは、$SEM_WAIT_LOCKでブロックされるので問題ない。また、複数のプロセスがGET_LOCKで同じ名前のロック上に待機している時、次にロックを取得できるプロセスは待機中のプロセスからランダムに選ばれるので特定のプロセスが飢餓に陥る可能性がある。良い点としては、途中でプロセスが突然死しても、名前付きロックは解放されるのでリソースの返却漏れが発生しない。

SLEEP / KILLによるプロセスの待機と再開[2]

ややトリッキーなやり方だが、以下のようなメリットが得られる。

busy waitが生じない
待機時間が長いプロセスを優先的に処理に回せる (飢餓が発生しない)
information_schema.processlistテーブルをみることで待機中のプロセスの数を簡単に確認できる

SEM_NAME := 'name-sem'
SEM_SZ := 5

SEM_PROCESS_LOCK := ""
SEM_CHECK_LOCK := "${SEM_NAME}-check"
SEM_LONG_SLEEP_QUERY := "SELECT RELEASE_LOCK('${SEM_CHECK_LOCK}'), SLEEP(10000000)"

SEM_CHECK:
  WHILE 1
    GET_LOCK($SEM_CHECK_LOCK, -1)
    FOR i := 0; i < $SEM_SZ; i++
      SEM_PROCESS_LOCK = "${SEM_NAME}-${i}"

      IF GET_LOCK($SEM_PROCESS_LOCK, 0)
        RELEASE_LOCK($SEM_CHECK_LOCK)
        BREAK SEM_CHECK
      END IF
    END FOR

    $SEM_LONG_SLEEP_QUERY
  END WHILE

# critical section

GET_LOCK($SEM_CHECK_LOCK, -1)
RELEASE_LOCK($SEM_PROCESS_LOCK)
SEM_SLEEP_QUERY_ID := SELECT id FROM information_schema.processlist WHERE info = "${SEM_LONG_SLEEP_QUERY}" ORDER BY time DESC LIMIT 1
IF $SEM_SLEEP_QUERY_ID
  KILL QUERY $SEM_SLEEP_QUERY_ID
END IF
RELEASE_LOCK($SEM_CHECK_LOCK)

問題として、途中でプロセスが異常終了すると、待機中のプロセスを起こすことができなくなる。すなわち、セマフォは空いているのに待機しているプロセスが生じてしまうことになる。一応、待機プロセスはSleep時間を超えると、自発的にセマフォの空きをチェックするので、永遠に処理に入れないということはない。また、他の正常終了したプロセスによって起こされることも考えられる (待機時間が長いプロセスを優先して起こすので、飢餓にもならない)。
よりベターなのは、以下のような処理をプロセスの最初に入れて不整合があれば先に解消するようにすることであろう。

GET_LOCK($SEM_CHECK_LOCK, -1)
FOR i := 0; i < $SEM_SZ; i++
  SEM_PROCESS_LOCK := "${SEM_NAME}-${i}"
  IF GET_LOCK($SEM_PROCESS_LOCK, 0)
    SEM_SLEEP_QUERY_ID := SELECT id FROM information_schema.processlist WHERE info = "${SEM_LONG_SLEEP_QUERY}" ORDER BY time DESC LIMIT 1
    IF $SEM_SLEEP_QUERY_ID
      KILL QUERY $SEM_SLEEP_QUERY_ID
    END IF
  END IF
END FOR
RELEASE_ALL_LOCKS()

N = 1の時と比較して、かなり冗長な仕組みになってしまうのが悩みどころである。

Redisを使う[3]

Redisを使えばMySQLよりも、かなりシンプルにセマフォを実現できる。というのも、Redisの持つBLPOPというメソッドがセマフォの実現に最適だからである。BLPOPは、keyとして指定されたリストが空である限りブロックされ、空でなくなったタイミングで値が取り出させる。

SEM_NAME := "sem-name"
SEM_RESOURCES := "${SEM_RESOURCES}-resources"
SEM_SZ := 5

# init
IF NOT GETSET($SEM_NAME, $SEM_NAME)
  FOR i := 0; i < $SEM_SZ; i++
    RPUSH($SEM_RESOURCES, i)
  END FOR
END IF

SEM_RESOURCE_ID := BLPOP($SEM_RESOURCES, 0) # blocked if SEM_RESOURCES is empty

# critical section

RPUSH($SEM_RESOURCES, $SEM_RESOURCE_ID)

問題点は、リソースの返却漏れである。リソースの返却漏れが起こるとセマフォが縮小してしまう。これの対処療法としては、リソースにタイムアウトを設定する方法が考えられる。使用中のリソースのリストを保持しておき、新たなリソースが要求された際に、利用可能なリソースが無ければ、使用中リソースからタイムアウトしたリソースを返却漏れとみなして、利用可能なリソースリストに移せばよい。

おわりに

グローバルなロックであれば、MySQLのGET_LOCK / RELEASE_LOCKで簡単に実現できることが示唆できたが、一方でグローバルなセマフォは処理の複雑さやリソースの返却漏れという問題について、まだまだ改善の余地があるのではないかという結果になった。引き続き何かより良い方法がないか考えていきたい。

参考

[1] MySQL 5.7 Reference - Locking Functions
MySQLの名前付きロックに関するドキュメント
[2] 実践ハイパフォーマンスMySQL 第3版
"6.8.1 MySQLでキューテーブルを作成する"のセクションに名前付きロックやSLEEP / KILLによる同期のアイデアが記述されている
[3] redis-semaphore
Redisによるセマフォのgem

サーバー間で共有できるセマフォを実現したい