いい加減なクオラム（sloppy quorum）を良い加減に説明する
意外と暑さが控えめになってきた8月上旬、皆様いかがお過ごしでしょうか。
今日は、みんな大好きデータ指向アプリケーションデザインの第5章レプリケーションより、いい加減なクオラム（sloppy quorum）について説明しようと思います。
理由としては、ここの内容が少しわかりにくいと感じたためです。また、日本語のネーミングがなんだかダサカワな感じで気に入ったからです。
まずはそもそものリーダーレスレプリケーション、クオラムの説明をして、いい加減なクオラムの内容を説明します。
リーダーレスレプリケーション
(*) レプリケーション
レプリケーションとは、他のノードに同じデータをコピーしておくことです。
（ノード：DBソフトウェアを実行している各マシンor仮想マシン）
そうすれば、仮にそのマシンが壊れてもコピー先のデータは生きているので可用性が高まります。
他にも、レプリケーションを地理的にバラバラなところに作ることでそれぞれの地域のユーザーからの読み取りレイテンシを下げたり、コピーをたくさん作ることで大量の読み取りアクセスの処理を分散させることでスループットを高めたりといった効果があります。
ちなみに、コピーを保存する各ノードのことを、レプリカと言います。
そんなナイスなレプリケーションですが、3つのアプローチが存在します。
シングルリーダー、マルチリーダー、リーダーレスです。今回は、このリーダーレスレプリケーションのお話です。
他のアルゴリズムには、レプリケーションを先導するリーダー（最初に書き込まれるノード）が存在しますが、リーダーレスレプリケーションには存在しません。
クライアントは、書き込みを複数のノードに送信します。そして、読み取りも複数のノードから平行に行います。
そして特徴的なのが、書き込みの際にバージョン情報を持たせておくことです。
こうすることで、もし書き込みがいくつか失敗しても、読み取りの際に1つでも更新に成功した（=バージョンが新しい）ノードから読み込めれば、正しい値を取得できます。
ちなみに、この書き込みや読み取りを誰が行うかは、実装によって異なります。
クライアント側が複数のノードに書き込みや読み取りを行う実装もありますし、コーディネータノードというノードが行う実装もあります。
Amazonの内部で使われているDynamoというデータストア（DynamoDBとはまた別）がこのリーダーレスレプリケーションを採用しているということで有名らしいです。
Dynamoについては、この方のブログや
AmazonのDynamoDB論文を眺めた | Takuya Kitazawa
実際のDynamoの論文（の和訳）など読むと理解が深まります。
Dynamo: Amazonの高可用性Key-value Store[和訳] · GitHub
クオラム
さて、このリーダーレスレプリケーションでは複数のノードに書き込みや読み取りが行われます。そのため、各ノードが個別に書き込みに成功したり失敗したりします。結局、処理全体としてはどういうことが起きるのかを見ていきましょう。
例えば、このようにx=1の値をx=2に上書きするようなレプリケーションを考えます。
今回の例では、読み取りが成功したレプリカ1,2は書き込みが失敗しています。そのため、実際はx=2を書き込んだはずですが、x=1が読み取られてしまいます。これは、処理全体としては誤った読み取りになってしまいますね。では、どういう場合なら、処理全体として読み取りが正しく行えると保証できるでしょうか？
ここで出てくるのがクオラムという考え方です。
レプリカ数をn、書き込みに成功したノード数をw、読み取りに成功したノード数をr個としたとき、
を満たすようにそれぞれの値を自身で決めます。
この時、
- 書き込みに成功した = w個以上のノードに書き込みが成功した
- 読み取りに成功した = r個以上のノードに読み取りが成功した
とみなします。このような書き込み、読み取りをクオラム書き込み、クオラム読み取りと呼びます。
このクオラム書き込み、クオラム読み取りでは、最新の書き込みが最低でも1つは読み取れることが保証されます。
なので、w個の書き込み成功したノードとr個の書き込み成功したノードの集合のベン図が、最低1つは交わるイメージです。
それでは、そのクオラムの具体例を見てみましょう。今、x=3の値をx=4に上書きしようとしています。
この例では、 と決めています。
を満たしているため、最新の成功した書き込みが最低でも1つは読み取れます。実際、レプリカ3はx=4と書き込みに成功していて、読み取りにも成功しています。
この時、（成功した読み取りのうち、2つがx=3で1つがx=4となっていて、どれを最終的な値として決めるんだ？）と思った方、ごもっともです。ここは何かしらの方法で、値を1つに決める必要があります。
例えば1つの方法として、書き込んだ値にバージョンを持っておく、という方法があります。
今回の例でいうと、x=3が書き込まれる前の状態なので、この状態をversion=1としましょう。その後、x=4が書き込まれたとき、version=2にします。
そうすると、読み取りが成功した3つは
[x=3, version=1] ,[x=3, version=1] ,[x=4, version=2]
となり、この中で一番versionが大きいものを選択すれば、正しい値を取得できますね。
このように、n, w, rの値を決めて、w,rの数だけ書き込み、読み取りが成功すれば処理全体を成功とするやり方がクオラムでした。
であれば、このクオラムの考え方を用いれば最強卍なのでしょうか。
ここからが、いよいよ分かりにくい「いい加減なクオラム」です。
いい加減なクオラム（sloppy quorum）
クオラムの考え方を用いれば、必ず1つは最新の書き込み成功したノードを読み取れました。
ただ、逆に言えば、w個の書き込み、r個の読み取りが成功しなければ、処理全体は失敗するわけです。
これは、可用性の面で問題になります。そこで出てくるのが、いい加減なクオラムです。
いい加減なクオラムを使うと、書き込みの可用性が上がります。具体例を見てみましょう。今回は、最初の具体例（誤った読み取りされてしまった例）を、いい加減なクオラムを使った場合どうなるかを見ていきます。少し複雑なので、3ステップに分けてみていきます。
STEP1. 書き込み
まずは書き込みです。レプリカ1~4は障害発生中でアクセスできません、そのため書き込みが失敗しています。
そして、いきなり右側に領域展開されたのは、レプリカとはまた別のノードたちです。いい加減なクオラムでは、n個のレプリカ以外にも書き込みを受け付けることができます。今回は別領域のノード2つに書き込みを試み成功しているため、w=3となり書き込み処理全体が成功となります。本来のレプリカの中であれば、書き込み成功したノード数は1でw=3を下回るため書き込み処理全体は失敗するはずですが、いい加減なクオラムにより成功となりました。これが、可用性向上といわれている所以です。
ただし、注意すべきは「wの数以上書き込みが成功すれば、書き込み処理全体として成功」というルールは引き続き適用される、ということです。別領域を使ったとしても、それは変わりません。
そのため、別領域のノードに書き込みに行ったが、別領域ノードが全て落ちていて書き込みが全て失敗した場合は、全体で成功した書き込みはレプリカ5の1つのままであるため、書き込み失敗となります。
STEP2. ヒント付きのハンドオフ
次は、ヒント付きのハンドオフです。一時的に書き込んでいた別領域のノードを本来のレプリカたちに転送します。
障害が起きていたレプリカ1~4のうち、レプリカ3,4は復旧したとします。その時、一時的な領域に保持していたx=2をレプリカ3,4に転送します。
こうすることで、n個のレプリカの中でw=3という条件が満たされたことになります。
また、ここでいう「ヒント」とは、「本来はどのノードに送られるべきだったか」という情報のことを指します。
STEP1で別領域のノードにx=2を書き込んだ際、じつはその値とともに「本当はレプリカ3に書き込む予定でした」という情報もメタデータとして持たせています。それをもとに、レプリカ3の状態を定期的に確認し、復旧が確認出来たらx=2をレプリカ3に転送します。
STEP3. 読み取り
最後は読み取りです。ここは別領域とは関係なく、n=5のレプリカを対象に読み取りします。別領域に読み取りに行くことはありません。
今度はレプリカ4,5が障害を起こして読み取りが失敗、レプリカ1~3の3つが成功したとします。r=3を満たしているので、読み取り処理全体も成功となります。レプリカ3を読み取っているので、最新のx=2という値を正しく読み取れていますね。（x=1が2つ、x=2が1つ読み取れていますが、先ほどの方法と同じくversionを付けて書き込んでいたため、最新のx=2を判別できたとします）
以上が、いい加減なクオラムの仕組みです。ただ、いい加減なだけあって、通常のクオラムでは起き得なかった問題が起きます。
いい加減なクオラムで起きる問題
別領域のノードに書き込めるとは言え、それは一時的な対応です。本来のレプリカはn個であり、読み取りもこのn個のレプリカを対象に行われます。そのため、ヒント付きのハンドオフが実施される前に読み取りが行われた場合、古い値を読み取ってしまう可能性があります。
例えば、先ほどのSTEP1が終わって（別領域のノード2つも含めて書き込みが成功した）すぐに、レプリカ3,4が復旧して、さらに読み取りも行われてしまった場合です。
ヒント付きのハンドオフが行われる前であるため、レプリカ3,4には古い値x=1が格納されています。この状態でレプリカ1~3で読み取りが成功すると、r=3以上のため読み取り処理全体として成功しますが、x=1が取得されてしまいます。
このように、いい加減なクオラムを使うと、障害発生/復旧タイミングによって古い値が読み取られてしまう可能性があるのです。
まとめ + ユースケース
リーダーレスレプリケーションでの書き込み、読み取りの方法として、クオラム書き込み/クオラム読み取りという手法がありました。
これは、を満たす書き込み、読み取りで、少なくとも1つは最新の値を読み取ることが保証されます。
ただ、その保証の裏返しとして、w個の書き込み、r個の読み込みが成功しないと失敗してしまいます。
一方で、いい加減なクオラムではn個のレプリカとは別の領域のノードを一時的に書き込みのノードとして利用できました。その後、一時的な書き込みのノードからn個のレプリカにヒント付きのハンドオフで転送します。
この方法を用いることで、書き込みの可用性は向上します。しかし、読み込みに最新の値が含まれる保証はありません。
上記を考慮してユースケースを考えてみます。
クオラムは値の正確性が必要な場合に使えそうです。例えば、オンラインショッピングでカートに入っている商品の一括購入など。「最後に削除した100万円のツボの削除処理がまだ反映されていなかったので購入しました」ということは避けなければなりません。
いい加減なクオラムは、書き込みの可用性が必要な時に使えそうです。例えば、twitterのTLの読み込みなど（使われているかは知りません）。「1秒前にAさんがつぶやいた「風呂なう」というツイートが読み込めていないため、TL全体の表示もエラーとなります」となってしまうと、ユーザー的には使いにくくなってしまいます。
以上、いい加減なクオラムの説明でした。
間違っているところなどありましたら、ぜひご指摘ください。
