ユユユユユ

webエンジニアです

並行書き込みを検知する

 リーダーレスデータベースは書き込み時コンフリクトに対してひどく脆弱である。クオラムが満たされていても並行書き込みによるコンフリクトは起こりうるし、リードリペアの際にもコンフリクトしうる。さらには書き込み可用性を高めるためにクオラムをぞんざいに扱うというオプションも存在し、こうなると書き込み結果の不整合はどうしようもなく拡大する。

なにをもって並行とするかは認識論的にしか定義しえない

 並行とはそもそもなにか。任意のふたつのリクエストについて、客観的な立場からそれらが並行しているか直列であるかを言い当てることは原理的に不可能である。リクエストを発する主体が、異なる処理の結果を知った上で書き込みをおこなえばそれは直列であるし、知らずに書き込みをおこなえばそれは並行することになる。つまり認識の位相の問題であるわけである。

 こう言い換えることもできる。すなわち並行性とは時間によって定義されるものではない。物理的思考においてこれは正しいが、計算機的思考においてこれは成立しない。なぜならネットワークは無制限に遅延するものであるため、リクエストが送信した時刻やリクエストが処理された時刻を点として観察することにはなんの意味もないためである。

 その上で、並行関係を補足するためのアルゴリズムを考えてみよう。

並行関係を補足するためのアルゴリズム

 簡単のためにレプリカがひとつしかないとする。例えば、リクエストとレスポンスにバージョン番号を含めることで、「クライアントはどこまで知っているか?」を追跡することができるようにできる。

 これにより、書き込みリクエストとして送信されたデータを消失させてしまうことは常に避けられるようになる。その一方で、ひとつのバージョンに複数の値が含まれることが起こりえ、それをマージする必要も生じる。競合する値を union して返すのがもっともシンプルな実装になるが、その場合でも削除操作をどう記録するかを考慮する必要はある。削除フラグ( tombstone )を含めて union できるようなアルゴリズムを用意するのがよいだろう。

 この考え方を複数レプリカ間でのコンフリクト解消に拡張してみよう。同じようにデータのバージョン番号をリクエストとレスポンスに含めてやりとりする方針は有効である。ただしバージョン番号はレプリカごとに割り振られるものとして管理しなければならない。言い換えると、レプリカごとにバージョン管理ができていれば、あるノードから読み込んだ値を別のノードに書き込んだとしても、データの損失は発生しないということになる。この仕組みのことをバージョンベクターという1