Google Cloud Storage を使用した分散ロックはどのように実装されているのか？

次の記事を読んでどのように実装しているのだろうと疑問に思い調べた結果を残しておきます。

https://cloud.google.com/blog/ja/products/storage-data-transfer/implementing-leader-election-google-cloud-storage

以下、本文中では Google Cloud Storage を GCS と表記しています。

## 調査対象

軽く調べたところ冒頭の記事で紹介されていた [hashicorp/vault](https://github.com/hashicorp/vault) 内のパッケージ以外にも類似機能を提供している OSS があったのでそちらも調べてみました。

### mco-gh/gcslock

https://github.com/mco-gh/gcslock

Go で実装されたライブラリとコマンドですがシェルスクリプト実装も公開されています。

mco-gh/gcslock は GCS が備えている [世代番号と前提条件](https://cloud.google.com/storage/docs/generations-preconditions) の仕組み [^1] を利用して分散ロックを実現します。

- ロック時はリクエストヘッダに `x-goog-if-generation-match:0` を指定してファイル作成する。
  - これによりファイルが存在しない場合のみリクエストが成功する。
  - HTTP ステータスコード 200 (OK) が帰ってきたらロック成功とする。
  - ロック失敗した場合はバックオフを増やしながらリトライする。
- アンロック時はファイルを削除する。
  - HTTP ステータスコード 204 (No Content) が返ってきたらアンロック成功とする。
  - アンロック失敗した場合はバックオフを増やしながらリトライする。

README に記載されているのですがロックを獲得したクライアントが何らかの理由でアンロックしなかった場合はデッドロックになります。
[ライフサイクル管理](https://cloud.google.com/storage/docs/lifecycle) を利用することで自動アンロックできますが最低でも 1 日はロックされたままになってしまうので注意が必要です。

また、前述の世代番号と前提条件に制限事項として記載されているように経路上のリクエスト遅延やリトライによる重複で意図せずロックされる・アンロックされる可能性がゼロではありません。

### thinkingmachines/gcs-mutex-lock

https://github.com/thinkingmachines/gcs-mutex-lock

Python で実装されたライブラリです。

mco-gh/gcslock に触発されたとあり基本的な方針と課題は同じですが [gsutil コマンド](https://cloud.google.com/storage/docs/gsutil) を実行する実装になっています。

### TobyColeman/gcs-mutex-lock

https://github.com/TobyColeman/gcs-mutex-lock

TypeScript で実装されたライブラリです。

mco-gh/gcslock の移植版とあり基本的な方針と課題は同じですが [Google Cloud Storage: Node.js Client](https://www.npmjs.com/package/@google-cloud/storage) を使用する実装になっています。

### hashicorp/vault

https://github.com/hashicorp/vault

hashicorp/vault のプラグイン開発向けパッケージである [sdk](https://pkg.go.dev/github.com/hashicorp/vault/sdk) には [physical.Lock](https://pkg.go.dev/github.com/hashicorp/vault/sdk/physical#Lock) という interface が定義されており、 GCS を含む複数のバックエンド実装が用意されています。

- [Consul](https://pkg.go.dev/github.com/hashicorp/vault/physical/consul#ConsulLock)
- [DynamoDB](https://pkg.go.dev/github.com/hashicorp/vault/physical/dynamodb#DynamoDBLock)
- [Etcd](https://pkg.go.dev/github.com/hashicorp/vault/physical/etcd#EtcdLock)
- FoundationDB
- [GCS](https://pkg.go.dev/github.com/hashicorp/vault/physical/gcs#Lock)
- [MySQL](https://pkg.go.dev/github.com/hashicorp/vault/physical/mysql#MySQLHALock)
- [OCI Object Storage](https://pkg.go.dev/github.com/hashicorp/vault/physical/oci#Lock)
- [PostgreSQL](https://pkg.go.dev/github.com/hashicorp/vault/physical/postgresql#PostgreSQLLock)
- [Raft](https://pkg.go.dev/github.com/hashicorp/vault/physical/raft#RaftLock)
- [Spanner](https://pkg.go.dev/github.com/hashicorp/vault/physical/spanner#Lock)
- [ZooKeeper](https://pkg.go.dev/github.com/hashicorp/vault/physical/zookeeper#ZooKeeperHALock)

GCS による interface の実装 (以下、 `Lock` 構造体) は mco-gh/gcslock と同様に GCS が備えている世代番号と前提条件の仕組みを利用していますがファイル有無ではなくメタデータを読み書きすることでタイムアウトによるアンロック (他クライアントによるロック取得) を実現しています。

`Lock` 構造体は内部で goroutine を実行しておりロックを保持しているクライアントは定期的に JSON エンコードされた `LockRecord` 構造体をメタデータに書き込みます。
この際に世代番号と前提条件を使用することで他クライアントとの競合を回避しています。

メタデータに書き込まれた `LockRecord` 構造体にはユニーク ID と更新時刻が含まれています。
これは自分がロックを保持しているかどうかの判断やタイムアウトによるアンロックの判定に利用されています。

なお、冒頭の紹介記事にはメタデータにロック情報を格納することでコストを最適化しているとあるのですが [GCS の料金](https://cloud.google.com/storage/pricing) を見た限りではメタデータに対するオペレーションも同じ価格に見えました。

## まとめ

GCS による分散ロックは GCS が提供する次の特徴を活用して実装されていることがわかりました。

- [GCS に対する読み書きが強整合性 (Strong consistency) である](https://cloud.google.com/storage/docs/consistency)
- [世代番号と前提条件](https://cloud.google.com/storage/docs/generations-preconditions) の仕組み

実装は大きく 2 種類あります。

- create if not exists なロックファイル作成を利用する実装
  - 実装がシンプルで移植しやすい
  - 何らかの理由でアンロックされなかった場合はライフサイクル管理による削除を待たなければならない
- メタデータを利用してロックの所有者と有効期限を管理する実装
  - ライフサイクル管理による削除を待たずにアンロック (他クライアントによるロック取得) できる
  - クライアントの時計が大きくずれていると問題が起きる
  - 実装がやや複雑になる

[^1]: GCS には [オブジェクトバージョン管理](https://cloud.google.com/storage/docs/object-versioning) という仕組みがありますが、これを有効化しているかどうかに関係なくすべてのオブジェクトは世代番号を持っておりリクエスト時の条件として指定できるそうです。