謝辞：この記事は前職での知見を改めて記事に起こしているものです。このあたりのロジックが同期に実際どう使われたのかは @ainame のスライドを参照ください。
https://speakerdeck.com/ainame/jia-zu-arubamumitene-kai-fa-feng-jing-number-realm-jp
注意：ここでいう差分同期はクライアントがローカルのデータを編集できる双方向同期ではなく、単に更新された情報を全てクライアント側に落としてくるための片方向同期のことです。
問題提起
アプリ用のAPIなどにおいて、任意のタイミングで更新されるデータをローカルに保存する「同期」のようなものを実装しなくてはならなくなったとき、大量のデータを一度に落とすことができないのと、通信量・負荷の削減のために下記のような対策を入れることになるかと思います。
- 前回同期完了以降に更新されたデータのみ取得
- 一度に取得する件数を制限
片方であればWHEREやLIMIT書けば済みますが、両方やろうとすると正しく動作させるためには工夫が必要なのでまとめます。
前提として、更新日時が古い方から新しい方へ順番に返却していくことになります。
| id | updated_at |
|---|---|
| 101 | 2016-01-23 14:15:16 |
| 102 | 2016-01-23 14:15:16 |
| 103 | 2016-01-23 14:15:16 |
| 104 | 2016-01-23 14:15:16 |
| 105 | 2016-01-23 14:15:16 |
| 106 | 2016-01-23 14:15:16 |
| 107 | 2016-01-23 14:15:16 |
| 108 | 2016-01-23 14:15:16 |
| 109 | 2016-01-23 15:00:00 |
| 110 | 2016-01-23 15:00:00 |
| 111 | 2016-01-23 15:00:00 |
例えばこんな更新日時が重なっているテーブルがあったとして、更新日時古い順に5件ずつページングしたとします。最初のクエリで101..105が返ってきます。次に返ることが期待されるのは106..109です。
（実際の場合は、user_idなどがカラムとして存在し、それがWHERE句に含まれていると思われます。）
うまくいかないパターン例
page=2のようにページ番号で指定
SELECT * FROM test_table ORDER BY updated_at, id LIMIT 5, 5;
ページングの途中で101の要素が更新されて102..109,101という順番になったとき、102番から数えて6件目から10件目は107-101なので、106番のレコードが返却されず宙に浮いてしまいます。
同期済みデータの更新日時の値を指定
SELECT * FROM test_table WHERE updated_at > "2016-01-23 14:15:16" ORDER BY updated_at, id LIMIT 5;
ページング中にレコードが更新されてもページの位置が変化しないので、一見うまくいきます。しかし、上のテーブルで2016-01-23 14:15:16をページングのキーとして使ってしまうと、日付が重複していない109以降しか返却されず、安全対策のつもりでWHERE updated_at >= ?とした場合再び101から返却されてしまい無限ループとなります。
じゃあどうする
更新日時とIDで指定（課題あり）
日時重複の問題を解決するために、同じ日時内ではidもページングします。2ページ目をリクエストするときにupdated_atとidの両方を渡して、下記のようなクエリを投げれるようにします。
最後のレコードがid: 105, updated_at: "2016-01-23 14:15:16"のとき
SELECT * FROM test_table
WHERE (updated_at = "2016-01-23 14:15:16" AND id > 105)
OR updated_at > "2016-01-23 14:15:16" ORDER BY updated_at, id LIMIT 5;
MySQLのInnoDBではid（正確にはPrimary Key）が自動的にセカンダリインデックスに含まれるので、updated_atを最後のカラムにしたインデックスが貼ってあり、クエリ内のASC、DESCが揃っていれば追加のソートは発生しないはずです。絞り込みにuser_id等がある場合は、(user_id, updated_at)のような形でインデックスを張りましょう。
弱点：ロック処理が直感的でない
上記はすべてDBにCOMMITされる順番がupdated_atの順番と一致していることを前提としています。例えば、同期処理が実行中にupdated_atが10:00:01のレコードまで舐めたあと、ロックなどの都合で遅れて更新されたレコードのupdated_atが10:00:00になったとすると、そのレコードは同期の対象外になってしまいます。
コンマ数秒の話でありめったに起きないはず（最悪気づいたタイミングで最初から同期すれば解決）ですが、それが致命的な結果になる場合は、updated_atの順番がCOMMITの順番と確実に一致するように（未来の方向にしか進まないように）、updated_atカラムに対して更新ロックを掛ける必要があります。
updated_atはupdateやsaveを叩いた瞬間のSQLが発行される直前に更新されるので、少なくともそれをトランザクションで囲って直前にupdate_atのインデックス上にロックが取れるクエリを投げます。
SELECT MAX(updated_at) FROM test_table FOR UPDATE;
FOR UPDATEつきのクエリをLocking Readといい、他のトランザクションからFOR UPDATEで同じ行を参照しようとすると先行するトランザクションが完了するまでロックで待たされます。Railsの場合はクエリの途中で.lockと書くとFOR UPDATEが発行されます（注：find_or_create_by系を使った場合を除く）。
ただこのMAXは何に使うわけでもないのであまり本質的ではない感じです。
Update Sequence Numberで指定（本命）
そもそもクエリやロックが面倒な理由は、updated_atという時刻情報に更新の順番の意味も同時に持たせたことが原因です。そこで、更新順序を単なる番号で管理すれば、idとかupdated_atとか変なロックに悩む必要はありません。ただし、カラムを追加する必要があるので大きなテーブルの場合は変更コストが高いです。
EvernoteのEDAMという同期アルゴリズムでは、Update Sequence Number (USN)という概念が登場します。これは同期対象のグループ、例えばユーザ=user_idごとに1つ管理される番号で、同期対象のレコードを更新するたびにインクリメントされ、更新されるレコードには現在のUSN値が書き込まれます。USNを使うと、最後に同期したときのUSNの最大値より大きいものをすべて取得するだけで同期完了するのでシンプルです。EDAM自体をやろうとするとしんどいけどUSNだけならカラム1つ追加＋クエリ変更ですみます。
クエリ例
あらかじめ、usnというカラムを追加しインデックスを張っておきます（user_idなどの絞り込みがある場合は、usnを最後にした複合インデックスを張ります。USNの性質上、UNIQUEでもよさそうです）。
更新処理をトランザクションで囲い、更新の前にまず現在のUSN値を次のようなクエリで（前述のLocking Readで）取得します。
SELECT MAX(usn) FROM test_table FOR UPDATE;
これで1000が取れてきたとすると、次の更新の際に1を足して1001を書き込みます。
UPDATE test_table SET body_text = "...", usn = 1001 WHERE id = 101;
COMMITするまでの間、USN値取得クエリはロックされるので、例え何らかのタイムラグがあってもUSNはDB上で必ず増えていく値になります。
同期の方は、素直なクエリでページングまで実装できます。最後に同期リクエストで返却されたUSNの最大値が1000だったとすると下記のクエリを叩きます。
SELECT * FROM test_table WHERE usn > 1000 LIMIT 5;
これを返却結果が0件になるまで繰り返せば同期完了です・・！
結論
- 新規のデータベース作ってる or 件数そんなに多くない → USN方式
- 既存テーブル件数多すぎ、確実に同期されないとまずい → ロック付きで更新日時＋ID方式
- まぁ同期失敗して歯抜けしてもリセットできるし大したことない → ロックは任意で更新日時＋ID方式
おまけ：cursor
APIに対してidとかupdated_atとかusnとかをバラバラと渡すこともできますが、前職ではクライアント側で考えるべきことが増えないよう、BASE64エンコードしたJSON的なデータを、cursorというひとかたまりのデータで扱っていました。これだとURLクエリに与える値が1つで済んでシンプルです（/notes?cursor=...）。
詳しくはスライドを・・ https://speakerdeck.com/ainame/jia-zu-arubamumitene-kai-fa-feng-jing-number-realm-jp