Evernote Synchronization via EDAMを読みました

Documentation - Evernote Developersの「Synchronization spec」の文書です。こういうWebサービスとクライアントアプリがいて、データ同期をとるようなアルゴリズムって、別に難しいことはないような気もしますが、一方で綺麗に書くためのベストプラクティスってなかなか見つからないような気がします。まあ力技でなんとかなるとも思いますが、それはそれとして上手くやる方法をずっと探していました。例えばgitとかちょっと機能が豊富すぎるし、Unisonとかそれはまたちょっと違うし。

こないだ気づいたのですが、Evernoteってローカルなキャッシュが存在することがかなり前提のサービスですよね。で、APIのドキュメントを見てみたらそんな感じのドキュメントがありました、という話。今となってみれば、けっこう当たり前の話ですよねーという感じだったので、一年くらい読むのが遅かったと思う……

1. EDAM Overview

EDAMっていうのは、Evernote Data Access and Managementの略。Thriftを使ってるよーとかそういう話。

APIには2種類あって、ユーザーの認証をするやつと、ノートとかのデータの管理をするやつに分けて考えるよーとか。そりゃそうでしょうから、ちょっと良いや。

2. EDAM Synchronization Overview

まずは、Evernoteの同期について以下のような要求があるよ、という宣言。

  1. クライアント・サーバーモデルでやる。サーバーは常にアカウントの情報をぜんぶ知っている。
  2. クライアントのデータベースについて物理的な構造を仮定しない。
  3. 全部の同期とインクリメンタルな同期の両方をサポートすること。同期のたびにデータベースを全部送受信するのは認められない。
  4. 同期は不安定なネットワークを介してであったとしても、バカみたいな量のデータを再送することはない。これは、最初の同期に関しても同じ。
  5. 同期はEvernoteのサービスをロックしない。

どれも当然だよねー。1はちょっとしたチョイスかな。

で、どうやるかというと「state based replication」という方法を使う。中央のデータセンターはただのデータストアで、そこからクライアントにデータを送信する。これは、IMAPとかMS Exchangeでやっているのと似たような方法だ！

そうなのか！(IMAPはともかく、Exchangeとか知らんわ)

Evernoteのサーバは個々のクライアントの状況をトラックしない。また、ログを取っておいて、それをもとにreplicationするようなこともしない。

どうやるかというと、アカウント毎のUSN(Update Sequence Number)というのを、個々のオブジェクト(ノートとか)について付けておいて、それで更新の順番を保存する。USNは、新しいアカウントごとに1から始まって、create/modify/deleteの度に増えていく。あとサーバーは、あるアカウントのオブジェクトで最大のUSNというのも覚えておく。このUSNを使うことで、ある時点以降のオブジェクトの更新とかを取り出すことができる。

上記の要求の3-5から、ちょっと複雑な状況が考えられる。データをクライアントに送信しているあいだに変更されるということがある。ネットワークは遅いかもしれないし、途中で切れるかもしれないから。

これは困った！

あとは、コンフリクトが発生した場合は、クライアントの側でその解消を行うと書いてあるね。同期をスケーラブルにするためらしいけど、ちょっと良くわからない。コンフリクトの解消をサーバでやるのは大変なのか。(良く考えてないのでわからない。)

で、同期はこんな感じ、という話になる。

  1. 前回の同期以降の変更を取得する
  2. クライアントのデータを更新する
  3. 同期されていないデータを送信する
  4. 次回の同期のためサーバーの状況を取得する

多分4番目のステップがポイントで、同期中の変更をこれでトラックすることになるんだと思う。

あとはクライアントはローカルに同期が必要かどうかのdirtyフラグを持っておく必要があるよーとかそういう話。さらにフルシンクも(例え論理的にはインクリメンタルに更新できるとしても)できるようになっているべきだとかそういう話。

3. Synchronization pseudo-code

まず、サーバ側とクライアント側で、2つずつ変数がある。

サーバ側

  • updateCount
  • fullSyncBefore

fullSyncBeforeというのは、なんかサーバーのトラブルの際などに、クライアントのUSNが信頼できない状態になった場合に、クライアントにある時点よりも前のデータを再送信するための時刻。

クライアント

  • lastUpdateCount
  • lastSyncTime

lastSyncTimeの使い道が一瞬よくわからないけど、これはfullSyncBeforeと組合せて使う。

認証の話とかは良いので置いておこう。

同期の流れ
  1. 始めての同期だったらフルシンクする
  2. そうでなかったら、同期の状態をまず取得する。そして場合わけ
    1. lastSyncTimeがfullSyncBeforeより前の場合は、フルシンクする
    2. updateCountとlastUpdateCountが同じ場合は、サーバの変更がないので、データの送信に行く
    3. それ以外の場合は、インクリメンタルシンクをやる
フルシンク

まあ普通に同期する。

オブジェクトにはGUIDがあってそれで識別するよーって書いてあるので、GUIDと言うくらいなので、てっきりクライアントで生成するのかとおもって、なんて恐しい！とか一瞬思ったんだけど、GUIDはサーバで生成するらしい。なんだそりゃ。そのまま整数のIDを使うのと違って、推測が困難になるだろうから、いろいろと使い易いのかもしれないけど。

コンフリクトは、オブジェクトのUSNとサーバのUSNで検出する。

  • サーバとクライアントのUSNが同じで、クライアントにdirtyが付いていない場合→同期されている
  • サーバとクライアントのUSNが同じで、クライアントにdirtyが付いている場合→あとで送信する
  • サーバのUSNが進んでいて、クライアントにdirtyがついていない場合→クライアントを更新する
  • サーバのUSNが進んでいて、クライアントにdirtyが付いている場合→コンフリクトなので、解消できないかがんばってから、ダメな場合はユーザーに報告

クライアントのUSNが進んでいる場合はどうするんだろう。そういうケースは、本当に深刻なデータの喪失だから、ごめんなさいするのかな。

インクリメンタルシンク

USNが進んでいるものだけシンクする。

変更の送信

dirtyが付いているものを送信するんだけど、送信後にUSNをチェックする。USNがlastUpdateCount+1の場合はOK。USN>lastUpdateCount+1の場合は、送信中に誰かがさらに変更したので、変更の送信後にインクリメンタルシンクしないといけない。

あと、シンクから送信までの間にデータが変更された場合は、conflictとして通知されるので、クライアントの責任で解消しておくこと。

これ以降

4と5にシーケンス図が書いてあって、6はLinked Notebooksの話。もういいや。

まとめというかなんというか

なんというか、普通に普通のことをやってる感じでした。

ユビレジでどうやっているかの話は、また今度します。