プライマリーキー(primary key)はシーケンシャルな値で良いと思うよ

Tech

を読んでの感想です。「シーケンスナンバーをPKにする」以外の項目については言及しませんが、言及しないことは正当性や妥当性を保証していることにはならないです。

InnoDB(MySQL)を想定してます。が、原理は割と一般的なので他のDBでも適用できることが多いと思います。

追記:一般的とは分散でないような"普通の"RDBMSを想定してましたが、分散システム(distributed systemないしreplicated system)のような場合では話が違います。

なぜシーケンシャルな値がよいか

端的にいうと書き込み操作時にバッファープール(baffuer pool)に読み混む必要のあるページが少なくて済むからです。その結果書き込み操作時にバッファープールにページが存在する可能性が高くレイテンシー的に有利になる可能性が高いです。

バッファープール、ページ、btreeなど具体的にイメージできない人にとっては難しいとは思いますが、軽く説明しておきます。多くのRDBMSはディスクIOの遅さをカバーするため直接ファイルを読み書きするわけではなく、必ずバッファープールに読み出してから操作を行います。これはwrite時もread時も同じです。ページというのはざっくり言ってバッファープールに読み混む単位であり、btreeのノードもページ上で表現されています。だからバッファープール上にページが存在しない場合、一旦ディスクから読み混まなくてはならないため操作に時間がかかるようになります*1。

InnoDBではレコードはプライマリーキーをキーとしてbtreeを構築してますので、ざっくり言ってinsert=btree上のノードを辿って適切なページにデータをおくということです。

バッファープールはメモリ上に構築されています。メモリはディスクに比べたら容量は少ないので、すべてのページをバッファープールに載せることはいずれ難しくなります。こうなるとバッファープール上に読み混まれたページは何かしらのポリシーによって入れ換えが行われ、不要なページはバッファープール上から追い出され必要なページが読み込まれます。InnoDBの場合はそのポリシーはLRU(の亜種)です。重要なことはbtree全部をバッファープールに乗せられない場合使用頻度の高いページはバッファープールに載っている可能性が高く、使用頻度が低いページは追い出されている可能性が高いということです。時間的局所性(temporal locality)といわれる性質です。

以上を踏まえてシーケンシャルな値かランダムな値どちらが良いかを考えると、ランダムな値の場合ランダムですので原理的にすべてのノードがバッファープール上に必要になります。すべてのページの使用頻度が同じくらいなので局所性がない状態です。どのページも同じ確率でバッファープールから追い出されていきます。すると書き込みの際、必要なページの内のどれかはバッファープールにない状態が普通になりますから、ディスクとのIOが必要になる可能性が高いのでレイテンシ的に不利になります。

シーケンシャルな値の場合は書き込みに必要なノードは1経路のみですから全体をバッファプール上に保持しておく必要はなく、ページがバッファープール上に存在することが大いに期待できます。書き込みと同時にページ全体(に近い範囲)を読み混むようなselect文が走っている環境であっても置き換えポリシーはLRUですので定期的な書き込みがあればバッファープールにのっていることが期待できます。

ページのラッチ(latch)

ページへの操作は競合状態を避けるためラッチ処理が行われます。同時実行制御です。InnoDBの場合MTR(mini transaction)という名前になっています*2。ですから1ページに複数の書き込み操作を同時に行う場合は実質的に1つずつしか実行されないので、異なる複数のページに書き込みを行い同時に実行できる場合と比べて確かに遅くなります。

話はそれますが結構一般的な問題ではあることから各RDBMS最適化の実装が入っています。

つまり局所的には件の記事に書かれている説明は正しいですが、実際的にはバッファープールが載っているかどうかの方が支配的であるため一見正しそうに見えて多くの場合ではバッファープールの事情を優先した方がパフォーマンス的には有利になるでしょう。

場合による

(自分の経験した)典型的なユースケースの場合、シーケンシャルな値の方が良いと思ってますが、すべては場合によります。「ページのラッチの差が重要である」かつ「データ量は多くないのでバッファープールにページがのりきる」という場面もありえないわけでもないです。そういうユースケースやテーブル設計は想像できますし想像できると言うことはありうるということでしょう*3。またアプリケーションの事情は常に正*4だと思っているので、アプリケーションの事情でプライマリーキーを選択しなければならない場合もあるかと思います。特に歴史的経緯があるならばなおさらです。遅いことがプロダクトの価値を毀損していないのであれば、DB的には正しくなくても周りとの一貫性を優先した方がプロダクト全体に良い影響があることはざらにあります。

べき集べからず集というのは「もっとも効果的にテクノロジーを使うために知らなければならない全体の20%」*5だと思っているので、べき集べからず集に対してアーキテクチャを説明して「議論は単純化はできない、場合による」と言ったところで求められているものとは違うわけで、あんまり効果的ではないと思っています。なので本心では「場合による」が正しいと思ってますが、あえて言い切るのであれば、「プライマリーキーはシーケンシャルな値を使え」です。

この議論はもう何回もされている

www.percona.com

これは2007年です。その後も定期的に話題にでる話なので探せばいくらでも出てきます*6。ちなみに議論の軸としてはシーケンシャルな値がいいのかと同時にサイズについての議論も盛んです。ただもうほとんど決着はついていてその結果がMySQLの(第2引数含めた)UUID_TO_BIN()対応だと思います。

*1:バッファープールに存在する=キャッシュが効いていて速くなっていると捉えることもできますが。自分はどちらかと言えばバッファープールに存在する状態がノーマルな状態だと思ってます。表現の問題なのでどちらでも良いですが

*2:PostgreSQLはLightweight Lock

*3:仮にあったとして自分だったらプライマリーキーにプレフィックスつけて擬似的にシャーディングすると思いますが、ふわふわした架空の要件に対して解決法提示してもしょうがないなという気持ちです

*4:というか人間含めたプロダクト全体のより上位の事情

*5:CAREER SKILLSの言葉

*6:「percona uuid」で検索しただけで4つくらいある

2021-05-30

dotfile棚卸し2021

自分はdotfileのリポジトリをpublicにできない側の人間だと受け入れる
alias g=git みたいなありがちだけど使ったことのないエイリアス消す
逆に alias c='code' とかは使うし c. の打ち間違いがめちゃくちゃ多いから alias c.='code .' 設定する
gitのエイリアスも大体使ってないので消す。 open = !gh repo view -w -b $(git symbolic-ref --short HEAD) 入れる
シンボリックリンク貼るスクリプトは自作を止めてthoughtbot/rcmに乗り換える。rcmでできないことはやらない
Windows用のファイルは一旦諦める。なくなったら辛いものだけ手動でバックアップ作っておく
promptのカスタマイズはStarshipにする。できないことはやらない
Karabiner-Elements、iTerm2、Alfredの設定もgitで管理する
tmuxのステータスの右側一切見てないので set-option -g status-right "[#h][%m/%d %H:%M:%S#[default]]" くらいにする。多分次回は消してる
fzfとpecoを併用してたけどfzfに一本化する
tmux popupかっこいいのでfzfの選択画面に設定する
ghq.root をデフォルトの ~/ghq にする
zsh completionの管理がだるいので見なかったことにする。brewが良い感じにしてくれたり自前でどうにかしないといけなかったりしてめんどくさい
zsh_historyのバックアップをLaunchAgentsで設定する。ヒストリーないと生産性5割くらい下がるような生き方してる
brewでzsh入れるの止めてシステムデフォルトのやつ入れる

ターミナル環境にそこまでこだわりないのでなるべくデフォルトで過ごしたいけど無理にデフォルトに寄せるほどこだわりもない。VS Codeのターミナルで生活したいと思う一方、一本化もできないのでiTerm2使ってる。定期的にBash移行したいと思ってたけどMacOSのデフォルトがzshになってしまったのでモチベーションなくなった。

それはそうとなんか昔ほどこだわりdotfileをご紹介みたいなエントリが流れてこない。

2021-05-15

MySQLとPostgreSQLの述語ロックについて

MySQLはともかくPostgreSQLはあまり詳しくないのだが、PostgreSQLの述語ロック(Predicate Locks)が気になったので調べた。

述語ロック

一般的にロックには粒度とモードという概念がある。前者はレコードロックとかテーブルロックとかロックの範囲に関わるもので、後者は排他ロックだとか共有ロックだとか両立性に関わるものである。述語ロックは前者に属する概念であると理解している。

述語ロックがなにの役に立つのか？それはファントムの防止である。粒度ロック(典型的にはレコードロックとテーブルロック)が存在するシステムにおいて2相ロック:Two-Phase Lock(2PL)に従ってレコードロックしているだけでは、ファントムのようなAnomalyが防止できることは保証できない。リレーショナルデータベース入門には「SQLのSERIALIZABLEという隔離性水準は、2PLに加えて、述語ロックをかけて幽霊現象の発生を抑えるところまで求めた水準である」と書いてある。

これは単にレコードをロックしていくだけではレコードとレコードの間への書き込みを阻止できないからである。したがってレコードロックのように、そのとき実在するレコードだけでなくレコードとレコードの間もロックできる必要がでてくる。ちなみにテーブルロックもこの条件に当てはまるが今度はパフォーマンスの問題が出てくるのでロックの粒度はなるべく小さくしたい。

レコードロックがwhere句に対応するレコードに対してロックをとっているのに対して、述語ロックはいわばwhere句そのものにロックをとるイメージである。つまりc = 2、3というレコードがあったとして where 1 <= c and c <= 5でロックをとろうと思ったとき、レコードロックは存在する2と4にしかロックをとらないが、述語ロックは1 <= c <= 5という範囲にロックをとることが求められる。

さて述語ロックについて重要な性質の一つに実装が困難なことがある。ロックの両立性を考えるとき述語ロックは<t, lock mode, predicate>のような組で考えることができる。tはトランザクションで同じトランザクション同士ならば両立する。lock modeは共有ロックか排他ロックか。predicate(述語)はwhere句だと思えば良い。異なる二つの述語が真になる集合に共通の要素があるかどうかを判定するのはSAT問題であるからこれを実装するのは容易ではない。述語が単純である場合は比較的簡単に実装できるらしいが、実際どういう述語=where句ならば現実的に実装できるのかは詳しくない。

したがって現実的には述語ロックではなく、もうすこし単純化した手法でレコード間へのロックを防ぐことになる。その実装がMySQLでいえば、あの有名なギャップロックである。ギャップロックは述語ロックより大きめの範囲をロックすることで処理を容易にしている。またMySQLの場合はネクストキーロックという仕組みでロックをとっている。解説はネット上にいくらでもあるのでそちらを参照して欲しい。MySQLのコードを読むとMySQLのロックの粒度やモードはtype_modeで表現されることがわかるが、ロックのtypeはtableとrecordしかない。では、ギャップはどのように表現しているのかというと、record typeに対してのフラグで表現されている。ネクストキーロックはレコードを識別子(レコードが定まればギャップが一意)にできるので、テーブルロックとレコードロックという2種類の粒度しかないロックテーブルの実装においてもフラグという形でギャップという概念を導入できるし、レコードロックのわずかな拡張でロッキングプロトコルを実装できる。と、理解している。

そういう事情があるのでPostgreSQLには述語ロックがあると聞いたとき、どうやって実装したのかが気になったという次第である。前述したとおり「述語が単純である場合比較的簡単に実装できるらしいがあまり詳しくない」というのがあったので、述語(where句)が単純な場合は完全な述語ロックが、そうでない場合はなにかしらの近似が実装されていることを期待した。

PostgreSQLの述語ロック

まずPostgreSQLの述語ロックはリソースに対するアクセス制限を課すような普通のロックではない。この辺はロック(というかロックマネジャー)の仕組みが一つしかないMySQLとは対照的だと思う。PostgreSQLの述語ロックはどちらかといえばトラッカーというイメージである。トランザクションが触った部分に対してマークをつけておきコミットするときに違反が起きてないかチェックする。いわゆる楽観的ロックの類いだと思っている。トランザクション中に読みこんだレコードがあればそれを表現する部分にSIReadLockを取得していきコミット前に矛盾がないかチェックし、abortかcommitかを決定していく。ロックマネジャーもMySQLのように1つしかないわけではなく、専用のロックマネージャーをメモリ上のハッシュテーブルとして持っている。

各トランザクションがどういうデータの触り方をしたらabortすべきかは長くなるので省く(ヒドい)が、述語ロックではrw-antidependenciesだけ防げれば良い(それ以外のデータ依存性については他の仕組みでカバーされている)。rw-antidependenciesだけ考慮すれば良いのでSIReadLockはあってSIWriteLockはない理由だろう。書き込みをマークする必要ない。

で、どのように述語ロックを表現するかというとこれは単純にレコードにマークするだけである。あとからきたトランザクションが競合するかどうかは単純にレコードの間かどうかで判定する。また読み混んだレコードすべてにマークをつけていくとメモリを使いすぎるのでマークをつけたレコードが多くなりすぎたらより大きい粒度へ昇格(escalation)していく。はじめはレコード、次にページ、次にテーブルというように。この辺の粒度を荒くしてパフォーマンスを上げる方法はネクストキーロックと同じものを感じる。max_pred_locks_per_pageなどのパラメータが昇格の閾値を決めるパラメータである。昇格によってロックの範囲が広くなればabortする必要のないトランザクションもabortすることになるがそれは諦めているっぽい。

結局最初のモチベーションは