The English version of this article is available here.

現代のソフトウェアでは、データが同時に複数のプラットフォームに存在する必要がよくあります。代表的なユースケースは書類の共同編集やオフラインファーストアプリです。この問題をデータ同期と呼びましょう。

データ同期を解決しよう

最近開発しているアプリではオフラインでもデータが使いたいと決めました。フロント／バックのデータ同期を提供している第三者API、例えばFirebaseとMongoDB Atlas、はもちろんあります。でも、どれも好みのフレームワークがサポート外、または値段が高すぎます。自分で解決するしかありません。

実装方法を調べたところ、conflict-free replicated data types (CRDTs) を発見しました。CRDTとは、時間的に並んでいない更新を自動的に組み込むデータ構造のことです。ユーザからの更なる入力は一切要らないところが特徴です。この機能を実現するため、CRDTは普段データと一緒に追加のメタデータを維持します。

例えば、あるCRDTの実装は最終更新のタイムスタンプを保存します。更新が入る時、発生日時がそのタイムスタンプより未来の場合のみ当てはまります。遅れた更新が落とそられる可能性がありますが、それは「conflict-free」というところです。

もう少し汎用的な定義も考えられます。CRDTとは、イベントをランダムな順番で受け、イベントのメタデータを使ってソートし、最新の方を採用します。

でもソートはエッジケースがあります。２つのイベントの順番が同じの場合どうなりますか？

デジャヴ？

ちょっと待って。この問題は見たことがあるのでは？

ボードゲームで遊んでいるとしましょう。最初のプレーヤーは次のルールによって決まります。

1. 一番若いプレーヤーが最初。
2. 同じ年齢の場合、ゲームで遊んだ回数が多いプレーヤーが最初。
3. 同じ回数の場合、プレーヤー名が大きい方が最初。

プレーヤー名がユニークである前提と取れば、このルールは必ず最初のプレーヤーを指定します。（どうせランダムなUUIDを配ることができるのでユニークな名を前提にするのが安全です。）

ボードゲームで遊ぶ時、ゲームのステートはよくカードとトークン等で表します。しかし、ゲームが始まるまでは物理的なステートの表示がないため、ゲームはプレーヤーに保存されている情報に頼ります。

このボードゲームは簡単なCRDTのではないかと思います。最初のプレーヤーという単体の情報しか管理していません。ボードとカードの代わりに、更新の順番を定めるためのメタデータをプレーヤーの脳で保存しています。

最初のルールは誕生日でソートします。まさにタイムスタンプ順です。でも双子が遊ぶことだけでゲームが始まらないこともありません。更にルールがあって、そして最後に必ず順番を決めるルールが付いています。

CRDTはボードゲームと同様の対応ができます。要するに、ただのタイムスタンプではなくいくつかのルールのための「エンハンスドタイムスタンプ」を保存します。

Hybrid Logical Clocks

こういうエンハンスドタイムスタンプは種類がいくつかあります。その中、特によく使われているのはhybrid logical clock (HLC)というタイムスタンプです。

HLCはイベントの発生日時と共に、バージョン番号とユニークなノード名も保存しています。奇跡的な偶然ですがHLCは例のボードゲームと非常に似たルールで順位を決定します。

1. 後で来たイベントを選ぶ。
2. 同時の場合、バージョンが高い方を選ぶ。
3. バージョンが一致する場合、イベント名が大きい方を選ぶ。

ボードゲームと同じように、CRDTは複数のメタデータを保存し複数のルールを使うことで同時に発生したイベントに対応できます。

結論

HLCで実装されたCRDTを使用している本番システムは確実に存在します。そういうシステムをコンポーネントごとに理解することで、我々エンジニア達はもう少し上手くトレードオフが検討できるようになると思います。第三者サービスにするか、アプリに必要なたった１つの機能を直接に実装するか、判断力が身に付きます。

ちなみにHLCをデータ同期に使うためいくつかの実装の詳細がありますが、今回の記事の目標ではありません。興味のある方、最近DartでHLCを実装してライブラリーを公開しました。もっと詳しい説明はこのMartin Fowlerの記事を推薦します。