50年後、Two-Phase Lockingは最善なのか？
(concurrencyfreaks.blogspot.com)- 1976年に公開された Two-Phase Locking(2PL) は、直列化可能性よりも強い Opacity を提供するが、約50年が経った現在でも読み取りのスケーラビリティと進行保証に限界が残っている
- 単純なロック取得・解放ルールで複数レコードのトランザクションを処理しながら 強い分離レベル を提供するため、商用トランザクションDBや並行データ構造で今なお広く使われている
- 伝統的な 2PL は相互排他ロックのため、読み取り同士でも競合しうるうえ、reader-writer lock を使っても二分探索木のルートのように読み取りが集中する箇所では read-indicator の競合 が発生する
- 2PLSF は reader ごとの表示をキャッシュラインに分散し、読み取りロック取得時の競合を減らし、競合したトランザクションに対してのみ中央の原子的カウンタの fetch_and_add() を適用する
- No-Wait、Deadlock-detection、Wait-Or-Die といった 2PL の派生方式は live-lock やスケーラビリティの問題を残しており、2PLSF は読み取りスケーラビリティと starvation-free なトランザクション の両立を狙った改良版である
2PL が今も重要な理由
- Two-Phase Locking(2PL) は直列化可能性（Serializability）を提供した最初期の汎用並行性制御の一つであり、実際にはそれより強い分離レベルである Opacity を提供する
- 2PL は Jim Gray とその共同研究者による論文 で 1976 年に公開され、発想自体はそれ以前から存在していた可能性もあるため、ほぼ 50 年の歴史を持つ手法 として扱われる
- 汎用並行性制御とは、複数のオブジェクト、レコード、タプルなどのデータ項目に対して all-or-nothing の意味論を持つトランザクションを可能にするアルゴリズムを指す
- 2PL の長所は単純さと強い分離性にある
- レコードを読み書きする前に、そのレコードを保護するロックを先に取得する
- トランザクションが終わるまで取得したロックを保持することで、一貫した観測を作り出せる
単純な規則が生む分離性
- 2PL ではトランザクション中の各アクセスごとにロックを取得し、これ以上アクセスがないと分かるトランザクション終了時点で全ロックを解放する
- 終了時点ではアクセスしたデータのロックがすべて保持されているため、そのトランザクションに対する 線形化ポイント（linearization point） が生じる
- 50 年前には、レコードアクセスが終わった後にすぐロックを解放してもよいと考えるデータベース研究者も多かったが、そのような並行性制御は直列化可能ではない
- よく知られた商用トランザクションデータベースは 2PL または T/O、MVCC との組み合わせ を使っている
- 並行データ構造の分野では linearizability がほぼ標準であり、複数ノードに一貫して書き込むには通常、書き込みアクセスに対して 2PL のような方式が必要になる
- 例外は lock-free データ構造だが、正しい lock-free 実装は難しいことが強調される
2PL のボトルネック: 読み取りスケーラビリティと live-lock
- 2PL の大きな弱点は 読み取りスケーラビリティの低さ と live-lock に関する進行保証 にある
- 古典的な 2PL は相互排他ロックを前提に設計されているため、2 つのスレッドが同じレコードを読むだけでも競合し、一方または両方が abort して再開始する可能性がある
- reader-writer lock に置き換えれば読み取り同士の競合は減るが、ロックコストとメモリ使用量は増える
- 相互排他ロックは、ロック済み/解放済みの状態を表す 1ビット で実装できる
- reader-writer lock では、このビットに加えて現在読み取りモードでロックを持つ reader 数を数えるカウンタが必要になる
- たとえば 7 ビットのカウンタなら最大 128 スレッドを表現でき、各ロックは 1 バイトで済む
- データベースに数十億のレコードがあれば、ロックだけで数十億バイトが必要になる
- さらに大きな問題はカウンタ競合である
- read-non-disjoint なワークロードでは、多数の読み取りが同じデータに集中する
- 二分探索木のルートノードは、すべての操作が下位ノードへ進む前に必ず読まれる代表例である
- 2PL ではルートアクセスのたびにロック取得が必要であり、reader-writer lock を使ってもルートノードのロックに激しい競合が生じる
既存アプローチとスケーラブルな read-indicator
- TLRW は Dave Dice と Nir Shavit が SPAA 2010 で提案した手法で、reader-writer lock を使って相互排他ロックより性能を高めたが、楽観的並行性制御ほど高速ではない
- TLRW と同様に、各読み取りアクセスが reader-writer lock の単一変数に競合する実装を Rank-based Relaxed AVL 二分探索木に適用すると、書き込みトランザクションでも読み取りトランザクションでも、ほとんどスケーラビリティが頭打ちになる
- read-indicator の競合 は、スケーラブルな read-indicator によって緩和できる
- 好ましい方式は、各 reader が到着と離脱を別々のキャッシュラインに記録する reader-writer lock である
- 読み取りロック取得時には競合がなくなる
- 書き込みロックを取得するスレッドは、許可可否を確認するためにすべてのキャッシュラインを走査しなければならず、書き込みロック取得コストは増大する
- NUMA Aware reader-writer locks は、この手法を用いた reader-writer lock アルゴリズムを扱っている
- 3 つの reader-writer lock アルゴリズムのうち 2 つは高いスケーラビリティを持つが、starvation-free ではない
2PLSF の reader-writer lock 設計
- Two-Phase Locking Starvation-Free(2PLSF) は、読み取りロック取得で高いスケーラビリティを持ち、追加の性質も備えた reader-writer lock で実装された並行性制御である
- 2PLSF の reader-writer lock は、read-lock のためにスレッドごとに 1 ビットを予約する
- それらのビットは専用のキャッシュライン上に配置される
- 隣接するロックの read-indicator ビットとともに配置される
- NUMA-aware reader-writer lock の論文と同様に、コストは書き込みロック取得側へ移される
- 書き込みロックでは複数のキャッシュラインを走査する必要がある
- これは魔法のような解決策ではなく、トレードオフ である
- このトレードオフが有用なのは、多くのワークロードが read-heavy であり、write-intensive なワークロードであってもレコード探索段階などでかなりの時間を読み取りアクセスに費やすからである
- 改良された reader-writer lock を使えば、read-non-disjoint なワークロードでも 2PL をスケールさせられるが、live-lock の問題は別途解決する必要がある
2PL の派生方式が残す進行保証の問題
- 古典的な 2PL には、競合処理の方法に応じて No-Wait、Deadlock-detection、Wait-Or-Die といった代表的派生がある
-
No-Wait
- 競合が発生すると、自分のトランザクションまたは相手のトランザクションを abort して再試行する
- 再試行は即時に行うことも、指数バックオフで後から行うこともできる
- レコード A の後に B を更新しようとするトランザクションと、B の後に A を更新しようとするトランザクションが継続的に衝突すると、どちらも commit できないまま abort-restart を繰り返し、live-lock progress に陥りうる
-
Deadlock-detection
- ロック上で待機中のスレッド一覧を保持し、サイクル、すなわちデッドロックを検出する
- reader-writer lock では各 reader が自分のリストを持つ必要があり、各リストを保護する相互排他ロックも必要になる
- read-lock モードでロックを取る際にすべての reader リストを走査しなければならず、コストが高い
- 理論上は starvation-free を実現できるかもしれないが、starvation-free なロックが必要であり、公開されている高スケーラビリティかつ starvation-free な reader-writer lock が存在しない点で目的と衝突する
- reader ごとにリストを置くとメモリ使用量も大きくなりうる
-
Wait-Or-Die
- すべてのトランザクションに順序を与え、ロック競合時にトランザクションのタイムスタンプとロック所有者のタイムスタンプを比較して待機するか abort するかを決める
- 相互排他ロックでは所有者をロック内部に一意なスレッド識別子として保存できるため、うまく機能する
- reader-writer lock で同じ方式を使うには、reader ごとに thread-id が必要になる
- 256 スレッドをサポートするには、8 ビット × 256 = 256バイト が reader-writer lock ごとに必要となる
中央原子カウンタのボトルネックと 2PLSF の違い
- Wait-Or-Die におけるさらに大きな障害は、すべてのトランザクションが一意のトランザクション ID を持たなければならない点である
- たとえば中央の原子変数から fetch_and_add() で番号を取得して順序を作れる
- 最新 CPU の多くでは、競合のある原子変数に対して秒間 4000 万回を超える fetch_and_add() を実行するのは難しい
- Visa の 1 日あたり約 6 億 6000 万トランザクションと比べれば多く見えるかもしれない
- しかし in-memory DBMS や並行データ構造では十分に大きいとは限らない
- あるテストマシンでは、秒間 2000 万回の fetch_and_add() を超えるのが難しかった
- この fetch_and_add() は書き込みトランザクションだけでなく、読み取りトランザクションを含むすべてのトランザクションに必要であるため、スケーラビリティを制限する
- TL2 は、読み取りトランザクションでは原子的な fetch_and_add() を行わず、楽観的読み取りを実行する
- 読み取りトランザクションでは数億 tps までスケールできる
- 一方、Wait-Or-Die ベースの 2PL は 40M tps/sec を超えられない
- 2PLSF は競合に入ったトランザクションだけに順序付けを行う
- 中央原子変数で fetch_and_add() を実行するトランザクション数が減る
- 競合のないトランザクションは 40M tps の高原に縛られない
- たとえば、競合なしで 200M tps が流れ、競合中の 40M tps だけが fetch_and_add() の限界に縛られる可能性がある
- このアルゴリズムは starvation-freedom を提供する
資料と最終評価
- 2PLSF アルゴリズム自体の詳細には踏み込まないが、starvation-free なアルゴリズムとしては比較的単純だと評価されている
- 参考資料として論文とソースコードが提供されている
- 2PLSF は ACM 論文 にもつながっており、Pedro Ramalhete、Andreia、Pascal Felber が作ったアルゴリズムとして紹介される
- 2PLSF の目標は、2PL が本来最初から備えているべきだった性質に近い
- 読み取りが重なる read-non-disjoint な状況でもよくスケールする
- blocking progress の最も高い形である starvation-free なトランザクション を提供する
- 一部の競合状況でもスケーラビリティを持ちうる
- 2PLSF は完璧ではないが、競合解決の面では TL2 より優れていると評価され、従来の 2PL との差は、つるはしと削岩機ほどの違いにたとえられる
1件のコメント
Hacker News のコメント
分散マイクロサービスアーキテクチャで複数のデータストアを同期したり「一貫した」状態に保ったりするには、業界のベストプラクティスは何なのか気になります
数日前、「settled timestamp」で不整合の問題を解こうとしてみました。エラー報告がないまま時間が経てば有効な保存/コミットとみなす、マルチバージョン方式に近いものです。2フェーズコミットで言えば、2つ目のフェーズが時間になっているようなものです
他のサーバーの時計を監視し、更新されなければそのサーバーの settled timestamp を信頼しない、という方式です。各更新ごとに応答を待たず、次の timestamp 区間を待つだけでよいので、多数のサーバーへ一貫性をスケールさせることを意図していました
ランダムな更新をやり取りする10個のスレッドで非決定性をテストする、マルチスレッド・マルチプロセシングの Python コードを作りました: https://replit.com/@Chronological/InconsistencySimulation#ma...
このシミュレーションでは、読み取りは全サーバーが報告した timestamp 全体の最小値で、10秒後に各スレッドへカウンター値を尋ねると、たまに全員が同じ値を返しますが、かなり頻繁に split-brain 状態になります
分散システムでは wall clock timestamp が順序決定に適しておらず、論理時計やベクトル時計を使うべきだという点は理解しています
どの時点であっても、シミュレーションが全員同じ数値を報告するようにできればよいのですが。Bloomlang は eventual consistency において、遅れて到着した値が結果に影響して線形化可能でなくなる問題を解決しようとしています
特に、一貫性を保ちながらスケールさせることに関心がありますが、かなり難しい問題に見えます
複数のシステムが中央ジャーナルへ順番に書き込み、ジャーナルはキー・バリューストアのようにリクエストを受け付けます。そのジャーナルがすべてのノードへ複製され、ノードはジャーナルを読んで要求された複雑なロジックを実行します
Kubernetes が etcd を使っているので、強い一貫性を持つキー・バリューストアとしてはかなりよくスケールします
「複数のデータストア」と言っているので、異種データがあり、CockroachDB のような選択肢ではないと仮定しています
初心者なら自作するのは危険です。https://aphyr.com/ はテストの基準のような資料で、教育用としても優れています。Jepsen で分散システムをテストできますが、Kyle が堅牢だと示したデータストアを使うほうがよいでしょう
これらの技術に詳しいわけではありませんが、データベースを学んだとき、SSI は将来の「より良い」2フェーズロックのように紹介されていました。SSI が 2PLSF とどう違うのか、なぜここで言及されていないのか気になります
ただし分散効果に関しては、依然としてロックや2フェーズトランザクションなどが必要です。個人的には代替というより、相互に補完する機能に近いと見ています
メモリ内データ構造なら自然ですが、外部データベースや他の共有外部リソースを扱うなら、もっと良い方法があるかもしれません
多くの場合、リクエストをバッチ処理して、外部リソースにはより低い同時実行性、より大きなペイロードでアクセスできます。そのリソースがバッチをうまく処理できるなら、必要な同時実行性とロックは大幅に減ります
たとえば Postgres を使っているなら接続数が減り、複雑さを増す PgBouncer を追加しなくて済むかもしれません
ただし、リクエストのバッチ化は多くのプログラミング言語にあまり向いていません。Go のチャネルや Elixir のプロセスのように高い並行性に最適化された言語ならうまくできますが、すべてをスレッドで処理する言語では苦痛になりえます
HTTPS にアップグレードできないサイトでは警告が表示され、両方をサポートするサイトはすぐに HTTPS 版へ移動します
それに、HTTP リンクが優れた並行性アルゴリズムに関するものなら、それでも読むでしょう
fetch_and_addが必要なのでしょうか？そもそもトランザクション IDが必要なのかも疑問です目標は、衝突時に誰が待ち、誰が死ぬかを互いに合意できるよう、アクティブなトランザクションの間に任意だが一貫した順序を設けることのように聞こえる。それならスレッド ID を使ってはいけないのだろうか？
ランダムな数値でも可能かもしれない。同値を「死」として扱えば、最悪の場合は両方のトランザクションが不要に中断され、新しいランダム数でリトライするだけだ
言及されてはいないが、長時間実行されるトランザクションが短いトランザクションによって飢餓状態にならないよう、古いトランザクションを優先しようとしているように思える。たとえば長いトランザクション 1 つが平均して短いトランザクション 3 つと衝突し、各衝突で勝者が実質的にランダムだとすると、長いトランザクションが 3 回すべて勝ってコミットできる確率は 1/8 にすぎない
しかし飢餓を防ぐために、毎回古いトランザクションを優先する必要はなく、ほとんどの場合で十分だ。特に、ほんの少しだけ古い程度ならなおさらだ
したがって、スレッド間のクロック誤差や他の不正確さがあっても、timestamp や cycle counter のようなものはうまく動作し得る。同値はスレッド ID で解消するか、やはり両方とも中断させればよい
このケースや他の多くのケースにうまく合う
2 フェーズコミットは Paxos と比較できる対象で、どちらも合意プロトコルの範疇に入る
2 フェーズロックは並行性制御メカニズム
最初のロックメッセージが消えたとき、失われたのが応答メッセージではないとどうやって分かるのか、という問題だ
単純なケースなら GitHub や Dropbox のように、そのまま進めて後で衝突を処理すればよい。データベースなら幸運を祈るしかないし、銀行ならなおさらだ
読み取り専用トランザクションでは、TL2 はグローバルバージョンをサンプリングした後、すべての読み取りについてローカルバージョンがサンプリングしたバージョン以下であることを確認すればよい
そうだとすると、グラフがなぜ線形未満なのか、TL2 が他の STM 実装ほど速くない理由が分かりにくい
たとえば通常、作業が 1000 個、ハードウェアスレッドが 10〜100 個あるとしよう
1000 個の作業のソート済みリストを 1 つ作り、各スレッドごとにそのコピーを作ったうえで、毎回コピーの順序をランダム化する
そうすれば各スレッドは自分のリストを読み、作業を実行した後、非ブロッキングなマルチスレッドキューとして実装された 1 つのリストを購読すればよい
最悪の場合、いくつかのスレッドがある作業を繰り返し実行することがある
この方式なら アトミック操作は最大 1000 倍までスケールし得る