ちょっと発言力のありそうな方がテクニカルに誤りを書かれていたので、ここでひっそりと訂正しておきたい。
The problem with Paxos-based algorithm is that replications are eventual consistent.
と、色付き文字で協調されて書かれている。このスライドで主張したいことの本筋ではないが、Spannerの性能がよいこととは関係がなく、Paxosなどのレプリケーションと、トランザクションとの関係で誤解を広めそうなので指摘しておきたい。辻マサカリと言って差し支えないだろう。
PaxosはStrongly consistentであることがMade Simpleの論文で証明されている（Strongly consistentが何かはまた別の機会にここに書こうと思う）。ちょっと長いが引用しておこう。
To learn that a value has been chosen, a learner must find out that a proposal has been accepted by a majority of acceptors. The obvious algorithm is to have each acceptor, whenever it accepts a proposal, respond to all
learners, sending them the proposal. This allows learners to find out about a chosen value as soon as possible, but it requires each acceptor to respond to each learner—a number of responses equal to the product of the number of acceptors and the number of learners.
ベタにいうと、Paxos-basedなレプリケーションでも過半数読まないと値は決まらないので、それに従ってる限り誤った値が読まれるということはない。
Eventual consistencyとは「古い値が読まれることがあっても、最終的には最新の値が読めるようになる」なので、これは真っ向から定義に反するわけだ。
ではPaxosの定義はともかく、Spannerにおける実装はどうなんだということになる。Twitterでは日本語で、似たような趣旨のことを書かれている。 SOの記事
Paxos algorithm in the context of distributed database transaction - Stack Overflow を引いて
というPaxosに伴うEventual Consistencyの問題をwrite処理にタイムスタンプを付けることで、あるレプリカが、クライアントが要求する時刻より新しいデータを返せるかを判断できるようにしたのがSpanner
と書かれている。上記の通りPaxosにはECの問題なんてないし、SOの記事にもそんなことは1ミリも書かれていないのだが、どうしてこういう誤解がされたのか、せっかくなのでSpannerの論文を当たってみよう。 2.1 の冒頭でレプリケーションとトランザクションについて語られている。
Unlike Bigtable, Spanner assigns timestamps to data, which is an important way in which Spanner is more like a multi-version database than a key-value store. A tablet’s state is stored in set of B-tree-like files and a write-ahead log, all on a distributed file system called Colossus (the successor to the Google File System [15]).
ここから分かるのは、Spannerではひとつの行にタイムスタンプで複数のバージョンを保持できるようにしているということだ。そしてWALがある。ということは、Tabletに対する更新はおそらくキー毎ではなく、Multi Paxosのように1Tabletにつき一つのWALを合意し続けるような作りであることが想像できる*1が…先を読んでみよう。
To support replication, each spanserver implements a single Paxos state machine on top of each tablet. (中略by引用者) Each state machine stores its metadata and log in its corresponding tablet. Our Paxos implementation supports long-lived leaders with time-based leader leases, whose length defaults to 10 seconds.
うむMulti-Paxosそのものだな。ちなMultiPaxosの特許は10年ほど前にMSがとっていて日本の特許公報でも見つけることができる。この書きっぷりからして思いっきり侵害していると思われるがそこは西海岸の論理でそんな野暮なことはしねーんだョ〜というのが垣間見えておもしろい。
Fig 2をみると分かるが、ここでのレプリケーションはデータセンター間のレプリケーションを指している。そしてちょっとあとに重要なことが書かれいている。
Our implementation of Paxos is pipelined, so as to improve Spanner’s throughput in the presence of WAN latencies; but writes are applied by Paxos in order (a fact on which we will depend in Section 4).
PaxosのWriteはパイプライン化してWAN超えても高速に送れるようになっている。で、Writeは必ず時間順に適用されると書いてある。TrueTimeを使っているからこんな芸当ができるんだね。で、勘違いされたのはすぐ次のここだと思われる
Writes must initiate the Paxos protocol at the leader; reads access state directly from the underlying
tablet at any replica that is sufficiently up-to-date. The set of replicas is collectively a Paxos group.
つまり、readsはPaxosをすっとばしてTabletに直接行くと書いてある。もとのPaxosにあるようなlearnerを通しての読み方ではなく、近くのデータセンターのTabletを直接読む...んだったら、そりゃあ間違った値が読めてしまっても仕方ない。しかしこれは上でも説明したようにEventual consistencyではない。sufficently up-to-dateな値を読んでも正しい値が読めるのは、たまたまSpannerでTrueTimeとそれに伴う並行性制御が適切に設計されているからである（4章で説明されているように）。
そもそもConsistencyというのはそのプロトコルが規定したR/Wの組み合わせパターンのそれぞれの結果のスペックであって、PaxosでもSpannerでもそういうスペックは規定してないのだからEventual consistencyと勝手に呼ぶのは間違っていて...Spannerの論文にもそんなことはどこにも書かれていないし…ﾌﾞﾂﾌﾞﾂﾌﾞﾂﾌﾞﾂ。
*1:ちなみにこれはRiakのStrong Consistencyでもやってるやーつ
