論文メモ Weighted Voting for Replicated Data

November 19, 2020

1979年に発表されたレプリケーション管理のクオーラムモデルのアルゴリズムの論文で、以前紹介したようにAmazon AuroraDynamoで採用されている。 ファイルの読み込みや書き込みのトランザクションは、複製されたファイルのもつ票を集め、所定の数、クオーラムを越えたときのみ実行される。 これにより、読み込み、書き込みの線形の一貫性が保証され、実行中のトランザクションが高々一つであるかのように見せかけられる。

票の総数を\(v\), 読み込みと書き込みに必要な票をそれぞれ\(r, w\)とする。 \(r+w>v\)のとき、どの読み込みクオーラムと書き込みクオーラムの組み合わせにも空でない共通部分が存在し、任意の読み込みが最新の書き込みを参照することを保証する。 複製された各ファイルは、ファイルのもつ票数のほかに版番号をもち、番号で最新状態か判断する。

また、\(r<w\)とすることで、最新のファイルに新しい書き込みが実行されるように保証できる。 文献によっては、\(r<w\)ではなく\(\frac{v}{2}<w\) とされているものもある。これは

$$ \begin{align} r + w &> v\\
2w&> v\\
w&>\frac{v}{2}\\
\end{align} $$

となるため最初の条件と一緒に考えると同じ意味になる。

読み込みと書き込みの間には、信頼性と処理性能において、トレードオフがあり、\(r, w\)の値で調整することができる。 \(w\)を減少させると書き込みの信頼性と処理性能が上がり、\(r\)を減少させると読込の信頼性と処理性能が上がる。