同期の高速化について

Evernote から最新の情報をお届けします。便利な使い方のヒントや Evernote 関連のニュース、世界中の Evernote ユーザーの工夫や利用例などをご覧ください。

同期の高速化について

2014年 3月 7日 | Posted by EvernoteJapan in 最新情報・お知らせ, 開発者向け

私たちの同期への取り組みについては「Evernote の同期が4倍速くなりました」や、「Evernote for Windows アップデート: 画像の注釈機能と同期の高速化」でお伝えしてきました。この記事は開発者向けの内容でちょっと難しいのですが、Evernote がどんな仕組で動いているのかの一端を知っていただくことができると思います。

以前の状況

2007 年に同期プロトコルを設計した時は、ユーザアカウントの全コンテンツの検索や、前回の同期以降の変更部分の検索の際、クライアントが使用するネットワークリクエストの数を最小限に抑えたいと考えました。そこで、「さまざまな要素で構成され、反復もありうる Evernote のデータモデルの各オブジェクトに対して、アカウント固有のアップデートシーケンス番号 (USN) を使用して、オブジェクトの状態に基づいた、ロックを伴わない複製を行う」ことにしました。この方式では、クライアントが「新しい情報はありますか？」と尋ねるだけで、サーバがユーザの Note、Tag、Notebook、Resource の変更内容を通常 1 回の HTTPS レスポンスで返します。

この方式は通信プロトコルとしてはうまく機能してきましたが、この 6 年の間にこの実装が拡張性の問題を抱えるようになりました。2008 年 2 月には空っぽだった 2 組のシャードも、今では 400 組を超えるものに成長し、数十億のノートを管理しています。その結果、次に SyncChunk 構造体としてクライアントに渡すべきオブジェクトを 1 組探し出すだけでも、かなりの数の I/O 操作が必要になってしまいました。

従来の設計では、1 組のシャードは、15krpm の回転式ディスクで構成された RAID1 上に MySQL データベースを使って、約 10 万アカウントのメタデータを保存していました。オブジェクトタイプごとにテーブルを用意し、それぞれのテーブルに自動生成されたプライマリーキーとともにセカンダリインデックスを付加することで、対象となるユーザのエントリを USN 順に並んだ状態で抽出できるようになっていました。例として「notes」テーブルの構成を挙げます。

CREATE TABLE notes (
 id int UNSIGNED NOT NULL PRIMARY KEY,
 guid binary(16) NOT NULL,
 user_id int UNSIGNED NOT NULL,
 notebook_id int UNSIGNED NOT NULL,
 title varchar(255) NOT NULL,
 update_sequence_number int UNSIGNED NOT NULL,
...
 KEY user_id_usn_idx (user_id, update_sequence_number),
 UNIQUE guid_idx (guid)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

このテーブルには 3 つのキーがあり、1 つまたは複数のエントリを効率的に（対数時間で）見つけられます。しかし、実際の行データは、ディスク上でクラスタ化されており、プライマリキーの順に並べられています。セカンダリインデックス（例えば、上記の user_id）を使って複数行を検索する場合は、データベースがまずセカンダリインデックスを走査し、次にポインタに従って各行が実際に存在するディスクのページを見つける必要があります。

クライアントがサービスに「私のアカウントのオブジェクトのうち、USN が 8476 より大きいものを最大 100 件下さい」と要求すると、ユーザのシャードは、最大 9 個のテーブルを照会して当該エントリを見つけ、結果をマージしなければなりませんが、結果的に返されるエントリは、該当する USN の小さいものからわずか 100 件です。この処理は 1 つの巨大な SQL UNION 文によって実装されており、実行時には各テーブルのセカンダリインデックスである user_id を走査し、一致する行の最初のページを読み込むことになります。しかし、最悪の場合、1 件のリクエストに対応するために、不連続に並んで数千にわたるページをディスクから読み込まねばなりません。

これでは、I/O コストが膨大になり、クライアントへの応答が遅れてしまいます。さらに、個人間やビジネスアカウント内で共有されるノートブックが急増したことで、この問題はさらに深刻化しました。それらのノートブックに対してはクライアントから個別のクエリが実行するようになっていたからです。オペレーションチームはデータベースを回転式ディスクから SSD に移行することで時間を稼いでいましたが、根本的な問題解決にはソフトウェアの最適化が必要でした。

解決のカギとなるインデックス

同期を効率化するにあたって、SyncChunk に入れて返すべきデータを探すために多くのテーブルにアクセスしなければならないという状態から抜け出す必要がありました。共有ノートブックやビジネスノートブックの増加に対応するだけでなく、contentClass ごとの同期といった新しい機能を実装するためにも、1 つのテーブルに十分な情報を入れ、MySQL から Java ミドルレイヤへの不要なデータの移動を最小限に抑えたいと考えました。

クエリの後に返す行データより、エンティティテーブル（note、tag など）へのクエリによって得られる行のほうが多いという点に注目してみましょう。note と tag から 3 件のエントリを返すには、3 組の <note ID, USN> と 3 組の <tag ID, USN> のクエリを実行し、返すべきエントリを見つけるために結果を USN で並べ替えます。データベースとのやり取りは高コストなので、必要な行だけを読み取るために 1 行ずつクエリを実行するようにしましたが、かえってコストがかかることもあり得ます。また、エンティティテーブルの値のフィルタリングを MySQL にやらせると、多くの場合、追加でテーブルの結合も必要になります。

そこで、すべてのエンティティテーブルにインデックスを付けることとし、それらのインデックスを「sync index」という 1 つのテーブルにまとめることにしました。この 1 つのテーブルに対してクエリを実行することで、その後の読み出しの対象となる NoteStore エンティティのプライマリキーを特定できるという訳です。また、1 つのテーブルだけにアクセスすること、行データそれぞれがデータベース内の他の値とは独立であることから、MySQL が多くのエンティティを効率的に除外してくれます。

一人のユーザに関する、sync_index の行データが同期に必要な順序でディスク上にクラスタ化されるように、プライマリキーとして <user_id, USN> を選択しました。1 つのデータベースページを読み出すだけで、効率的に様々なフィルタリングを実行するために必要なエンティティを含む行データが得られるようになりました。1 回の I/O 操作でできるだけ多くの情報を処理できるように、行データはできるだけ小さく設計されています。各行に格納されるべき情報は以下の通りです。

Expunged（完全削除済み）ステータス: エンティティが特定の USN でサービスから完全削除されたかどうかを示します。
Active（アクティブ）ステータス: リンクされたノートブックを同期すると、inactive（非アクティブ）のノートを見えないようにします。ノートが inactive になった場合、「expunge（完全削除）」イベントを発生しますが、完全削除された GUID が SyncChunk 内に含まれない場合には、そのノートは無視されます。
エンティティタイプとオブジェクト ID: サービスエンティティにクエリを実行するには、ある行データが参照しているエンティティのタイプ（tag、note など）とオブジェクト ID を知る必要があります。エンティティのステータスは、active、inactive、expunged のいずれかです。サイズを小さくするため、エンティティのタイプ（タグ、ノートなど）にステータス（active、inactive、expunged など）を「修飾子」として加え、1 byte フィールド 1 個にまとめました。
エンティティを含むノートブックの ID: Evernote の権限の大部分は、ノートブックのレベルで付与されます。リンクされたノートブックやビジネスノートブックの同期の場合、このノートブック ID を使用すれば、ノートとリソースの大部分をそれらのテーブルにアクセスせずに除外できます。
コンテンツクラス: Evernote Hello や Food などのアプリケーションは、ノートに付与する固有の contentClass を定義しているので、共通のプレフィックスに一致するノートだけを同期することができます。スペースを節約するため、コンテンツクラス全体を保存するのではなく、最初の約 32 文字に一致する 32 ビットのハッシュを使用しています。

これらの情報でエンティティの「現在」の状態はカバーできますが、過去の履歴が必要になる場合もあります。アカウントのノートブックの一部にしかアクセスを許可されていない場合、ユーザがアクセス権限のあるノートブックからアクセス権限のないノートブックにノートが移動されると、同期時にサービスは「expunge」イベントを発生します。上記のエンティティタイプの修飾子の値として「moved」を追加し、sync_index は、この状態をレコードの「moved（移動）」として記録します。また、以前のノートブック ID を記録するフィールドを追加しました。

以前は認識していなかった新しい状態もあります。現在、Evernote のクライアントの多くは、ビジネスアカウントの同期の際、リンクされたノートブックを一度に 1 個ずつ同期します。クライアントは、今までリンクされたノートブックの同期に使ってきた、実績のある既存のコードロジックを再利用し、ノートブックへの「lost access（アクセス権限喪失）」を検出することができますが、ユーザが参加するビジネスノートブックの数に比例してサービスとのやり取りが増えることになります。そこで、sync_index に、ノートブックの内容を受け取るユーザごとに「lost access」の履歴を記録することにしました。これでサービスから「expunge」イベントを送信し、アクセス権限の喪失をクライアントに通知することができます。そして再度、エンティティタイプの修飾子を拡張して「lost access」を記録し、アクセス権限を失ったユーザの ID を記録する新しいフィールドを追加しました。これにより、Evernote のクライアントは、ビジネスに属する全ノートブックの同期を一度に行う方式に移行することになるでしょう。

結果的に、このテーブルの定義は次のようになりました。Null 許容フィールドは、値が Null の場合には 1 ビットしか占有しません。

CREATE TABLE IF NOT EXISTS sync_index (
 user_id int UNSIGNED NOT NULL,
 update_sequence_number int UNSIGNED NOT NULL,
 entry_type tinyint NOT NULL,
 notebook_id int UNSIGNED,
 grave_notebook_id int UNSIGNED,
 object_id int UNSIGNED,
 guid binary(16),
 content_class_hash int UNSIGNED,
 recipient_id int UNSIGNED DEFAULT NULL,
 service_updated TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL,
 PRIMARY KEY (user_id, update_sequence_number),
 KEY objectid_entrytype_idx (object_id, entry_type)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 ;

この記事を読まれているプログラマーの方は、「sync_index は各種サービスエンティティのテーブルから複製したものだが、これらのテーブルに格納されたデータの更新にともなって、sync_index の一貫性はどのように維持されるのだろう？」という疑問をお持ちかもしれません。答えは、Hibernate interceptor を使用することでした。サービスエンティティの変更はすべて、Hibernate 経由で行われます。私たちが作成した Interceptor コードは、非正規化とハッシュ化を行います。ノートの属性を変更すると、Interceptor はそれが contentClass かどうかを確認し、その結果に基づいて sync_index テーブルのノートとリソースの行データを更新します。ノートが別のノートブックに移動されると、Interceptor は、以前のノートブックに対応する新しい「moved」履歴を作成すべきかどうか、さらに、現行のノートブックに対応する履歴レコードを削除すべきかどうかを検証し、sync_index のすべてのノート行と、そのノートに関連するリソースの行のノートブック ID を更新します。これで、リンクされたノートブックやビジネスノートブックの同期の際にも、ノートブック ID に基づいた正しいフィルタリングができるようになります。共有されたノートブックのレコードを変更すると、「lost access」行が作成または削除されます。Evernote のエンジニアがサービス API のコードを書く時でさえ、これらすべての処理はバックグラウンドで行われます。彼らが何をすべきか考えなくても、これらの処理は自動的に起こるのです。

sync_index へのデータの読み込み

sync_index に新規エントリまたは更新エントリを適切に格納するコードが完成したので、次は、新しいクライアントが古いアカウントを同期できるように、過去 6 年間の履歴を sync_index に読み込む方法を見つけなければなりませんでした。ユーザへの悪影響や誤ったエントリの作成を伴わずにこれを行うことは、思ったよりも大変でしたが、数週間の試行錯誤の末、次の方法にたどり着きました。

sync_index に必要な列を出力するために、各テーブル（note、notebook など）に SELECT … INTO OUTFILE を実行します。
LOAD DATA INFILE を使用して、そのデータを sync_index に読み込みます。
各テーブルに戻り、手順 #1 と #2 の間に行われた変更によって古くなった挿入済みエントリを見つけます。それらのプライマリキーをディスクにダンプし、（小さい）テンポラリのテーブルに読み込みます。
MySQL の multi-table DELETE を使用して一時テーブルを sync_index に結合し、一致したものを削除します。

手順 #1 と #2 は、もっと明らかな INSERT … SELECT 文を使うより 3 倍以上速く、どの行に対するロックも行わないため、実行中のアプリケーションでタイムアウトが起こるのを防ぐことができました。手順 #3 と #4 でトランザクションを伴わない挿入の後処理を行いましたが、単純な DELETE が引き起こす大きなソーステーブルのロックを避けることができました。

効果の検証

効果の検証にはいくつかの方法が必要でした。まず、sync_index テーブルの値の正しさと同期の結果を検証するために、新しいユニットテストのフレームワークを開発しました。この一連のテストは、継続的に発生するインテグレーションビルドすべてに対して実行しました。ステージングのためのプラットフォームでは、システムのテストチームがリグレッションテストを繰り返し行いました。コードには、サービスエンティティを SyncChunk に追加する時に sync_index の行データをそのサービスエンティティに基づいて確認するなど、一貫性の確認をいくつか追加しました。また、最終結果の正しさを確認するために、以前の同期アルゴリズムと新しい同期アルゴリズムを同時に実行しました。最後に、この新しいテクノロジーをプロダクション環境に導入するために、インフラストラクチャの構築とサービス内容の設定を行いました。

2456 の個人ノートと、リンクされた 31 のビジネスノートブックの中に 2861 のノートを持つアカウントを対象に同期にかかる時間を計測したところ、sync_index を使用する新しい方法では、以前の方法より約 99% 速くなりました。

ユーザにとって分かりやすい改善は、個々の同期関数の処理時間の中央値に反映されます。例えば、次のグラフは、sync_index による変更前後で、1 つのシャードに対する getLinkedNotebookSyncChunk 呼び出しの応答時間の中央値がどのように変化したかを示しています。

ユーザが感じる同期時間の改善だけでなく、シャードの I/O 使用率と CPU 使用率も激減しました。次のグラフは、ある 8 コアのシャードのシステムの負荷平均を先週（青）と 11 月のある週（緑）で比較したものです。

ユーザによるデータのアップロードが増える中、この変更によりサーバに余裕が生まれ、将来の機能やアカウントの増大に対応できるようになります。

他にも、パフォーマンスをさらに改善するために最適化を進めていますが、ここまでは満足のいく改善結果を得られています。みなさんの思い出をすべて記録できるように、引き続き Evernote の拡張を進めてまいります。

※ 本記事は英語版ブログ記事の翻訳です。