Carousel by Dropbox: スマホのメモリを利用した遅延の軽減

https://tech.dropbox.com/2014/08/building-carousel-part-ii-speeding-up-the-data-model/

1 comment | 4 points | by WazanovaNews 2年以上前 edited


Jshiike 2年以上前 edited | ▲upvoteする | link

4月に紹介した「Carousel by Dropbox: 遅延のない動きを実現する工夫」の続編として、今回は、写真のメタデータをメモリにキャッシュして遅延を減らす取り組みが紹介されています。

背景

写真閲覧アプリCarouselは、アプリを開いたら即座に写真をスクリーンに表示し、ユーザが履歴をたどって一番古い写真までスクロールバックしたとしてもスムーズな閲覧ができるように、写真のメタデータを利用している。

写真を10万枚以上保持するユーザもいて、ユーザのスクロールにあわせてディスクからメタデータを読み取る仕組みだけでは遅延を防げない。そこで、ディスクのキャッシュにあるメタデータをメモリに保存する方式を採用している。

このインメモリモデルとオンディスクモデルをうまく調和させるには、モデルのステートを変更しようとするスレッドに注意しなくてはいけない。例えば、ユーザの操作を反映するメインスレッド、サーバからファイルの変更を受取るスレッド、写真のアップロードなど様々なバックグランドタスクなど。また、ユーザが写真を閲覧できるタイミングが遅れるので、写真を大量にもつユーザの場合は、アプリの起動時に全てのメタデータをディスクから取り出すわけにはいかない。Nexus5など最近のAndroid端末は、写真あたり300バイトのメタデータを要し、写真5千枚分だけのメタデータをSQLiteから読み取るのに丸々1秒かかってしまう。

Data Loading in Smaller Data Sets

ここでは、スマホでのキャッシュ / データの読取り / 表示についての一般的な方法 & Dropboxにおける従来の問題回避策について紹介しています。

Androidでは、LoaderCursorを使う。

Dropboxモバイルアプリ(写真閲覧専用のCarouselを出す前からある基本アプリのことを指してるかと。)の写真タブでは、メタデータをSQLiteに保存し、SQLiteへのクエリをラップしたSQLiteCursorで読み取る。しかし、SQLiteが利用するインターフェースと、Cursorインターフェースはうまくかみ合ないという問題がある。

  • SQLiteはシングルスレッドライブラリで、SQLiteクエリの結果をCで読み取る際、クエリを実行し、データ接続にロックをかけたまま、クエリ結果の行を調べていく。
  • 一方、Cursorインターフェースはクエリ結果へ後からアクセスすることが可能なので、SQLiteCursorがやっているのは、Javaオブジェクトが、一定量のクエリ結果(デフォルトでは2MB)をキャッシュしつつ、SQLのクエリをレイジーに実行している。この方式の問題点としては、
    • 2MB以上のデータを扱わねばいけない場合、Cursorは、OFFSETクローズとあわせてクエリを再実行することで、次ページのデータを取得する。最初のクエリ実行と二回目の間にもしデータセットが変更になれば、うまく返すことができないデータ行がでるかもしれない。
    • クエリは、Cursorがデータを必要とする最初のタイミング(一般的には、moveToFirstrもしくはgetCountへの最初の呼び出しの際)で実行されるが、それはメインスレッドで起きるかもしれない。クエリをバックグランドスレッドで実行することで回避するとしても、二回目のクエリの実行は、最初に2MBを超えた時点になり、メインスレッドで起こる可能性がまたある。メインスレッドで2MBのディスクを読み出すことは数秒の遅延につながる。

iOSでは、SQLiteと直接やり取りするが、同じような問題に行き当たる。理由は、ネイティブでの実装は、リターンされる行数に制限がついたかたちで、一つのSQLクエリでデータを読み取るのが一般的だからである。

元々のDropboxのiOS/Androidアプリをつくった際は、写真タブをページで区切って遷移することにした。ディスクがメタデータを読むのをブロックすることによる遅延が許容できる範囲、約5千枚、にページサイズを制限することで、この問題を回避した。

Accumulator Model

Carouselの開発にあたっては、この5千枚問題を違ったかたちで解決する方法を模索。

viewをレンダリングするタイミングがきたら、viewにデータを素早くバインドできることさえ担保できれば、データをどうのような方式でディスクに保存していても関係ないことに注目した。

インメモリviewモデル、具体的には、レンダリング時にUIスレッドでクエリを走らせることができるくらい早いメタデータのインデックスをもつデータ構造を用意することにした。

このviewモデルを、iOSのcellForRowAtIndexPathやAndroidのAdapter.getViewのようなUIコールバックを実装するのに使う。

このデータ構造にアクセスする方式はiOSとAndroidで似ているので、ロジックをC++で実装することで、viewモデルを共有することができる。大きなデータモデルをJavaでなくC++で実装すると、大掛かりなガベージコレクタが実行されることによりAndroidアプリがぎくしゃくとした挙動をすることを防げる。

このviewモデルの実装にあたっては、パフォーマンス的に注意すべき点がある。

  • アップデートが早くなくてはいけない。リモートサーバにあるユーザのDropboxに(おそらくPCなど別のデバイスから)新しい写真が追加されたら、データセット全体を再読込みするのではなく、更新をすばやく反映できる必要がある。
  • ディスクからのメタデータの読取りをフルにブロックすることなく、最初のCarouselのviewを読込むことができるようにする必要がある。

上記の二つの要件を満たすには、部分的な(incremental)アップデートができるインターフェースが理想に思えたので、このインメモリviewモデルを “accumulator” と名付けた。

accumulatorはviewモデルを用意して、ユーザのデータに変更が起きる度にUIに渡す。タイムラインのviewが利用しているモデルは、かなりシンプルなトランザクションのインターフェース。

  • 1回のトランザクションで、一連の写真と紐づけられているイベントを追加、そして、commitを呼び出して終了。
  • commitが完了した時点で、accumulatorには、ユーザの写真コレクションが全部はないかもしれない。サーバもしくはディスク上のSQLiteキャッシュからストリーミングしている途中かも。
  • しかし、データモデルの整合性は保証された仕組み。閲覧できる写真は、それが紐づくべきイベント内でしっかり表示される。

このインターフェースのおかげで、上のアプリレイヤに複雑なことを追加せずに、データベースのトランザクションを開発 & 最適化してくることができた。活用するタイミングとしては、

  • アプリが最初にローンチした際、SQLiteからメモリにキャッシュしたメタデータを読込む
  • サーバから新しいメタデータをダウントードした際
  • バックアップをとるべき新しい写真をカメラロールが検知したとき

上記の三つの異なるコードパスがそれぞれ独立したスレッドで実行される。EventsAccumulatorトランザクションが起きるスレッドが同時に二つあってはいけない。トランザクション中は、各スレッドがEventsAccumulatorをロックするが、その間は、メモリ内のメタデータをaccumulatorにプッシュしている。

例えば、同期スレッドは、delta APIのようにサーバAPIへのコールを使っている。

  • このスレッドは、ディスクからのメタデータ読取っているスレッドがブロックされることなく、accumulatorがロックされる前に、ネットワークコールをして受取ったJSONをパースするというような、タイミングがものをいうようなタスクをこなすことができる。

  • もちろん、アプリが整合性のとれたviewを表現するために、上記の二つのスレッドの間に立って、ディスクへのアクセスをコーディネートしなくてはいけない。SQLiteからデータを読み取るスレッドは、同時に同期スレッドでwrite_delta_to_diskが実行されないようにするメタデータを読込みつつ、データベースにロックをかける。

Metadata Snapshots

メタデータのスナップショットを活用して、データ変更に対応する仕組み。

accumulatorに対応するスレッドが実行されている間に、UIが表示しなくてはいけないデータに変更がかかる可能性がある。

UIのコードが、いつデータが変更されると問題ないかをコントロールするために、commitがコールされる度に、データモデルのimmutableなスナップショットを用意する。

スナップショットを利用すると、UIはデータの更新にあたり、アトミックなモデルの交換ができる。一般的に、UIフレームワークがデータの更新をサポートするには、一般的には二つの方式がある。

  • 1. 新しいモデルのために、viewモデル全体を交換する(Android)
  • 2. 現在のviewモデルに部分的なアップデートをする(iOS)

部分的なアップデートの良い点は、データモデルへの変更(insert/delete)をアニメーションできることだが、スナップショットの差分を取ることでも、同様のことができる。

iOSとAndroidで共有のCarouselのコードは、viewモデルのスナップショットを用意して、1. の方式をサポートする。スナップショットは、写真の順番の絶対値と(event_index, index_within_event)の組み合わせにより、写真を調べることができる。

  • 新しいスナップショットを手に入れたら、iOSでは、[UITableView reloadData:]を呼び出し、新しいviewモデルを古いものと交換する。
  • Androidでは、スナップショットを各イベントの行インデックスを計算する薄いレイヤでラップし、ListAdapterのデータソースとして利用する。

Speedy Snapshots

最後に、パフォーマンスを考慮したスナップショットの実装について。

immutableなデータ構造はロジカルにはよくても、どう実装するかでmutableなものよりパフォーマンスがおちることがある。

一番シンプルな実装では、1件の変更でも、immutableなデータ構造全体をコピーしなくてはいけなくなる。

Carouselのスナップショットは、最初の実装では、時系列にソートされたarray構造。例えば、写真が5万枚あるユーザが写真を1枚タイムライン上で非表示にすると、array全体をコピーし、再度ソーティングするのに1秒近くもかかった。

そこで、写真はイベントごとにグループ化でき、変更は限られたイベント内で発生する傾向があることを利用して、スナップショットの構造を、イベントごとにポインタでつながった写真のarrayをもつかたちに変更した。(概念図

この方式により、1件の変更が起きると、該当するイベントの写真arrayを変更 & コピーさえすれば、残りイベント/写真arrayのペアには変更がないので、ポインタ情報をコピーするだけで、スナップショットをつくることができる。(概念図

スナップショット内でのデータの取得をスピードアップさせるために、もう一段階複雑にしてみる。オフセット計算をすることで、各イベントに含まれる先頭の写真の位置をイベントに持たせ、バイナリサーチで検索する。これにより、紐づいている写真arrayまで深く検索しなくても、どの絶対位置の写真がどのイベント内にあるかわかるようになる。

  • オフセット番号をイベントに付与した概念図
  • 写真データが1枚追加された後、以降のイベントのオフセット番号が更新される概念図

#dropbox #android #ios

Back