なぜ、タイムスタンプは、順序を決めるのに適していないのか
複数のノードにまたがる複数のイベントの順序を決めたいとする。
その時に、イベントが起きた瞬間のタイムスタンプを各ノードで取るとする。これが悪手であるという風に一般的に言われているだろう。
では、なぜ、これが悪手なのか。
理由は、それぞれのノード間でクロックがずれている可能性があるからだ。（クロック速度は温度によって変わる。また、NTPによる同期を行っても失敗したり、ネットワークが輻輳していると誤差が生まれる）
二人の利用者u1とu2が、t1とt2(t1<t2)にデータを書き込んだとする。
この時に、u1が書き込んだノードn1がu2が書き込んだノードn2よりも時刻が進んでいたとしたら、本来u1の方が早く書き込んだのに、u2の方が先に書き込んだように見えるかもしれない。
そうすると、データベースであれば、トランザクションの順序が入れ替わってしまうかもしれない。「タイムスタンプを使い、順序を決定するのは適していない」というふうに考えられてきた理由である。
信頼区間という考え方を導入する
とはいえ、直感的にもノード間の時刻のずれはそれほど大きいものではない。t2-t1が、それぞれのノードの時刻のずれよりも小さければ多少時刻にズレがあったとしても順序は変わらないのである。
この時刻のズレの幅が一定以下、例えば10ms以下であるとわかっているのであれば、t2-t1の時刻の差が10ms以上あればその順序は確かなものであると言える。この考え方が、信頼区間という考え方で、イベントが起こったクロックを点で見るのではなく、時刻の幅で見るという考え方である。
「例えば10ms以下であるとわかっているのであれば」と先ほど述べたが、普通はこれがわからない。NTPサーバーとの時刻同期などがあれば、常識的な幅に収まるだろうと仮定することはできるが、実際にそれ以下であると示すのは難しい。
しかし、Google Spanner の True Time APIは、このt2-t1の時刻の差を返すことができるAPIだ。各ノード同士がローカルで持つ自国の信頼区間(最も進んでいる時計と、最も遅れている時計の時刻の両方)をレポートできるのだ。
詳細については、2012年に発表された以下の論文に記されている。
https://storage.googleapis.com/pub-tools-public-publication-data/pdf/65b514eda12d025585183a641b5a9e096a3c4be5.pdf
MVCC
多くのリレーショナルデータベースでは、書き込みをブロックせずに読み取りを行う方法(なおかつ、Snapshot Isolationを実現する方法)として、MVCCが取り入れられている。
MVCCでは、トランザクションのコミットとの正確な順序が求められるため、タイムスタンプとして正しい値を提供する必要がある。
単一のマシンで動くデータベースでは、それは問題にならない。というのも、ローカルクロックで一貫した時刻を提供できるためだ。
一方で、分散型DBにおいてMVCCを実現するには、正しいタイムスタンプが必要になる。
AWSでも、2023年11月に、物理時間に対して、マイクロ秒単位で時刻同期を取ることができるEC2インスタンスについてアナウンスがあった。Time Sync サービスの誤差がさらに小さくなったというものだ。
信頼区間と精度の高い時刻同期を用いれば、これまでは不適切とされていた、物理時間をシステム設計に組み込むことができるだ。
つまり、言い換えれば、サーバー間の時刻の差分を小さくすることができればできるほど、待ち時間が短くなるので、並列度をあげられるということだ。信頼区間という考え方を用いる限り、タイムスタンプを使って正しく順序をつけるということは可能である。問題は、並列度が挙げられるかどうかというところだ。
より実時間に近い値を取ることができればできるほど、並列度を上げられるということだ。
DynamoDBでも、トランザクションの順序を決定するのに、絶対時間を用いたアプローチをとっている。以下のPresentationの中で示されている。
https://www.usenix.org/conference/atc23/presentation/idziorek
Time to Live を絶対時間で設定できるか
TTLは、主にデータベースやネットワークなどで利用されてきた。
DNSキャッシュにおいても、各エントリにTTLが関連するように設定されている。これは、ローカルDNSのキャッシュをどの程度の期間保持するかという設定項目だ。
どんな時だって、TTLの設定方法は、300(s)のような値が入っていた。言いたいことは、カウントアップしていくような相対時間がTTLに入力されていたということだ。
DNSサーバーとキャッシュクライアントでは、全く異なる別のマシンです。別のマシンにおいて、絶対時間を比較することはこれまで話してきたような理由で危険であるからだ。
一方で、相対時間では、それぞれのクライアントで抱える多くのアイテムに対してTTLが切れていないかチェックする必要がある。
TTLに絶対時間を定義することができれば、最初からそれを考える必要がなく、よりシンプルに今の時刻がTTLを過ぎているかどうかだけを見ることができるようになる。
EC2のアップデートによって、これからは絶対時間でTTLを設定することができる時代が来るかもしれない。そうすれば、よりシンプルな実装で、TTLを実現することができるようになるだろう。
リーダー選挙アルゴリズムのリースについて
排他制御アルゴリズムにおいて、非常によく使われるのはロックである。
ロックは、一つのプロセスがリソースをロックすると、他のプロセスはそのリソースに対してアクセスできない。他のプロセスはロックを獲得するまで待機する。
このリソース ロックは、ロックしているクライアント プロセスによって明示的にロックが解放されるまで他のプロセスは待機し続ける。そうすると、クライアントの失敗やデッドロック、バグによってロックのリリースを怠った場合などに、他のプロセスは待機させ続けられるわけである。
この課題を解決するためにリースという考え方が登場した。
リースには、TTLがある。TTLがあるリーダー選出のような仕組みである。リーダーは、リソースにアクセスする権限を一時的に得ることができるような仕組みなのだ。これによって、他のプロセスが待機し続けられてしまうという問題を解決した。
しかし、Lease という仕組みは、Lease を提供する単一のDBと、 Leaseを実行するプロセスが別のマシンである場合、それらのクロックが同じ速度で進むという前提のもとに設計されている。
リースプロバイダーの方が、早く時が進んでしまう場合には、一つ目のクライアントがまだリースを保有していると思っているうちに、次のクライアントがリースを取得する可能性がある。これでは競合してしまう。
これを避けるために、リースプロバイダーが、次のクライアントにリースを渡す前にバッファを設けるとしたらどうだろうか。これによって、先ほど述べた問題は解決される。しかし、クライアントが一時的に停止してしまったり、リセットされてしまったりして、リースを保持していると勘違いしてしまう可能性もある。
もしも、リースが保有する時間を絶対時間で表したとしたら、宣言的に同期を取りやすくなるのではないだろうか。
絶対時間の何がいいのか
これまでの相対時間での定義というのは、「時間が経過するのを待つ」必要があった。
つまり、時間の経過を待てないクライアントや時間の経過が早すぎたり遅すぎたりするクライアントがいれば、この常識が壊れてしまう可能性がある。
一方、絶対時間というのは、宣言的である。この宣言的ということは、(信頼区間内であれば)その時間になれば、どのクライアントにとっても時間が経過したということだ。
そのために、絶対時間を用いたアプローチは時計が正確であれば優れた点を多く持っている。
ただし、絶対時間を用いたアプローチには課題も多くある。
例えば、時刻を取得した時のクロックとその次のクロックは別のクロックであることだ。極端な話、この時点では、特定の処理はある時刻よりも後であることしか保証できない。
DynamoDB では、トランザクションの順序づけに絶対時間を用いているという話をしたが、
https://www.usenix.org/system/files/atc23-idziorek.pdf
こちらの論文の、3.2 Timestamp Ordering では、クロック同期エラーが出た時にどのように動作するべきかについても議論されている。DynamoDBでは、それでも分離レベルSERIALIZABLEを提供することができると記されている。ただ、その場合には当然パフォーマンスと信頼性が落ちることが懸念されている。要するに、クロック同期エラー時には、パフォーマンスが低下することがあっても、分離レベルの低下を招くことはないように安全側に倒すような実装をしているということである。
これは、時刻同期の信頼性に関わる部分であり、このテーマでも議論をする必要があることも押さえておく必要があるだろう。