非同期レプリケーションで単調読み出し整合性を保つ

レプリケーション*1は分散トランザクションと紙一重で、複数のサーバに分散された複数のデータを同時に書き換えたい。

もしこれが同時でないと、クライアントによって異なるデータを読んでしまう可能性がある：

しかし実際には同時でなくても良い。サーバ2からデータを読み出される前に、サーバ２にデータを同期してしまえば「まったく問題ない」：

もう一点、サーバ１から新しいデータが読み出される前ならば、サーバ２から古いデータを読み込んでも「まったく問題ない」：

つまり、整合性のない（それぞれのサーバが異なるデータを持っている）状態が発生したとしても、それが観測されなければ、実質的にすべてのデータは同時に更新されたように見える。

そこで、次の２つのルールを設定する：

• ルール１：クライアントは、整合性がない状態を観測したら、すべてのクライアントが古いデータを読み出さなくなるまで、データを読み出さない
• ルール２：整合性のない状態は、整合性のある状態に自然に（神=人が手を加えなくても）収束していく

ルール１が保たれていれば、整合性のない状態でも新しいデータしか読み出されない。
ルール２が保たれていれば、データを読み出せない状態が無限に続かない。

ルール1の実装

N>R+Wを使う。

ルール２の実装

Paxosを使う。

*1:読み込みの負荷を分散させたい場合。耐障害性だけが問題の場合は話が違うかもしれない。