Drew Koszewnikに聞く - 散在型キャッシュ Netflix Hollow

Netflixは，メタデータのキャッシュを目的としてJavaで開発された汎用キャッシュのHallowを発表した。

キャッシュは，データを集中的なストアに格納することでネットワークの遅延や帯域といった制限を克服するという，頻繁に使用されるテクニックである。頻繁に使用されるデータをローカルにキャッシュし，使用頻度の低いデータをデータストアに格納するようなデータのキャッシングを実現しようとして，開発者が苦労していることは少なくない。しかし，アクセスするすべてのデータをキャッシュするのであれば，実装ははるかに単純になる。Hollowは，データを複数のサーバに分散するのではなく，すべてのデータを各コンシューマに公開するアプローチを採用することによって，データ堅牢性のためのレプリケーションアルゴリズムの必要性を回避している。

Hollowの前身であるZeroでは，データをPOJO(Plain Old Java Object)として格納していたため，それがサイズ上の制限につながっていた。それに代えてHollowでは，固定長のコンパクトな，厳密に型指定されたエンコーディングをデータ表現として使用する。

InfoQは，同プロジェクトの主要なコントリビュータでNetflixの上級ソフトウェアエンジニアであるDrew Koszewnik氏から，詳細を聞くことができた。

InfoQ: 他のキャッシュシステム，例えばmemcachedとはどのように違うのでしょう？開発者がすでにキャッシュを使用している場合，どのような状況であれば，この新しいキャッシュへの移行を推奨できますか？

Drew Koszewnik:memcachedは優秀なソフトウェアです - NetflixでもEVCacheを開発して，多大なメリットを享受しています。Hollowで解決しようとしたキャッシュデータのサイズに関わる問題にも，ある程度は対応しています。一方でHollowは，特にサーバ群全体にわたってデータセット全体をレプリケーション可能な場合には，いくつかの問題をmemcachedよりも効率よく解決できます。私たちは，そのようなことの可能な状況が，ほとんどのエンジニアが思っていたよりも広範にあることに気付きました。メモリ上のデータセットの任意の部分に対するO(1)アクセスを確保しながら，データセットを圧縮する手段がHollowである，と考えて頂ければよいと思います。

memcachedの最大のメリットは，多数のインスタンスにわたってメモリをプールする分散型キャッシュシステムであることです。集中型であるHollowは，真の分散キャッシュシステムではないと言えるかも知れません。むしろ散在型キャッシュシステムと言った方がよいでしょう。分散(distributed)に対して，ここで散在(disseminated)という言葉を選んだのは，データセット全体のコピーが各コンシューマに複製されるという意味からです。

Hollowは，スループットの極めて高いキャッシュという，Netflixの要求を満たすために開発されました。Hollowの設計判断のほとんどは，根本的にこのニーズから生じています。すべてのコンシューマに全データセットを複製するということは，ネットワーク越しにデータを取得する必要がないということですので，データセットのどの部分にアクセスする場合でも，レイテンシは無視できるレベルになります。同時にHollowは，データセット全体にわたって，任意のデータをアクセスするために必要なCPUコストの削減を非常に重視しています。memcachedのように緩やかに型付けされたキー/バリューストアと比較した場合，厳密に型付けされた構造化データモデルを要求することによって，アクセスコストの問題への対処を一度行なえば，多くの異なるユースケースでそれが再利用されます。強く型付けされたシステムの構築を選択したことを受けて，データ構造を持つことのメリットを活用した，さまざまなツールを開発しました。その好例がhistoryとdiffツールです - データモデルが分かっているため，２つの状態における変更内容を正確に通知することが可能になりました。この情報を表現する目的で，有用性と汎用性の高いUI要素をいくつか開発しています。

構造化された方法でデータを完全にローカル保持するメリットのひとつは，データモデル設計時にデータの使われ方を正確に予測する必要がないことです。memcachedのようなシステムでは，コンシューマがデータを使用する方法について予め知っておかなくてはなりません -- 事前定義されたキーでのみクエリが可能だからです。Hollowでは，データを使用するチームがアクセスパターンを自由に設計できますから，プロデューサチームの作業が開発のボトルネックになることはありません。アクセスパターンとデータモデリングを切り離したことで，プロデューサ側が先入観で決めたインデックスを構築するのではなく，コンシューマによるインデクスの生成が可能になりました。

InfoQ: 読み取り専用データ，単一プロデューサ，複数コンシューマが前提なのしょうか？データの永続性についても詳しく説明して頂けますか？

Koszewnik: そうです，データは読み取り専用，プロデューサは単一，コンシューマは複数です。Hollowの持つ唯一の永続化メカニズムはブロブストア (blob store)で，これは単純なファイルストア - 例えばS3やNFS，さらにはFTPサーバでも可能です。コンシューマは起動時に，データストアにある最新のスナップショット全体を読み取って，データセットをメモリ内にブートストラップします。データセットは差分を適用することで，常にメモリ内で最新に保たれます。コンシューマが持つデータセットのインメモリコピーは短命(ephemeral)です - コンシューマが再起動した場合には，ブロブストアから再取得しなくてはなりません。

スナップショットブロブファイルのフォーマットは実際には単純で，メモリ上のレイアウトとほぼ同じ構造です。従って初期化は，ブロブの内容を直接メモリにコピーする処理が中心で，短時間で実行可能です。これによって，初期化時間を短くしているのです。

InfoQ: CAP定理に関しては，どのように対処されているのでしょう？例えば，ネットワークの接続上の問題が断続的に発生するような場合には，更新されないデータで作業することになるのでしょうか？

Koszewnik: Hollowは古典的な意味での分散データストアではないので，このようなケースでのCAP定理については，少し違う見方をしなくてはなりません。可用性や分断耐性(Partition Tolerance)の面で優れている反面，一貫性については妥協している，と言ってもよいでしょう。

コンシューマそれぞれがデータセット全体をRAMに持っているのですから，これ以上の可用性はありません -- 初期化されてしまえば，環境に関する問題の影響を受けることはないのです。分断耐性については -- そもそも分断という概念がありません。データはコンシューマ上にすべて存在するか，そうではないかのどちらかなのです。

一貫性については，さらに興味深いものがあります。Hollowのデータセット変更のタイムラインは，個別のデータ状態に分割される必要があります。それぞれが，ある特定の時間におけるデータの完全なスナップショットになるのです。このようなデータ状態が定期的に，通常は数分間隔で生成されます。ですから，データセットの伝搬遅延という面では，ある程度の許容範囲が必要になります。この問題を軽減する方法としては，例えばオーバーライドとして，緊急性の高い更新を独立したチャネルで送信することなどが可能です。

InfoQ: このキャッシュはすべてのデータではなく，おもに小規模なメタデータを扱うものだとは思いますが，ローカルサーバ上のリソースを使い果たしてしまった場合にはどうなるのでしょう？

Koszewnik: そのとおり，Hollowが中心的に扱うのは，小規模ないし中規模のデータセットです。TBやPBではなく，MBないしGBが目安になります。Hollowには規模が大き過ぎるとしてデータセットを除外する前に，JSONベースのドキュメントストアをアプローチとして検討してみてください。この方法であれば，1テラバイトをHollowに格納した場合の容量がはるかに小さくなります。Hollowの効率に優れたストレージと十分に調整されたデータモデルを組み合わせることで，巨大なデータセットを中規模にすることが可能になります。

GoogleのJeff Dean氏が教えてくれているように，システムは成長を前提として -- 10倍あるいは20倍になっても動作するように設計する必要があります。ただし100xのためのソリューションが，必ずしもxに最適であるとは限りません。ここでは，このルールを適用します。データセットの拡大に対してHollowでは，ヒープ使用量を詳細に分析するツールを提供することで，最適化対象の特定を可能にしています。このような指標を時間を掛けて比較することが，潜在的な問題の早期発見には有効なのです。特に，急激な直線的増加に対処する必要のある場合には，最適化の不十分なデータモデルの指標として，あるいは説明できない新たな成長軸の存在を示すものとして，この情報を利用できます。

ここではデータモデリングが極めて重要になります。データ構成の方法は，Hollowがデータセットの重複を排除し，圧縮を実現する上で大きく影響します。一般的な圧縮アルゴリズムがハフマンツリーによってデータ内のパターンを見つけ出すのに対して，Hollowではデータモデル内のレコード構造を使ってパターンを特定します。これにはある程度の事前情報が必要になりますが，Hollowが高度な圧縮を実現して，高スループットのランダムアクセスを維持する上では重要な部分なのです。

InfoQ: 圧縮アルゴリズムについてもう少し教えてください。POJOの使用を止めたのは，どのような理由からなのでしょう？

Koszewnik: Hollowは重複排除やエンコーディング，パッキングなど，さまざまな方法で圧縮を実現することで，Javaオブジェクトのオーバーヘッドを克服しています。重複排除の方法と範囲はおもにZenoから引き継いでいますが，POJOから離れることがなければ，エンコーディングやパッキング，そしてもちろんオブジェクトのオーバーヘッドの排除は適わなかったでしょう。

改めてパフォーマンスに着目すると，Hollowのデータセットにアクセスする時のCPUへの影響の最小化と，そのデータを表現する上で必要なヒープ容量の最小化を両立する方法が必要でした。そして最終的に，固定長のビット整列型データ表現にたどり着いたのです。 すべてのレコードにおいて，各フィールドは，正確にその最大値を表現するために必要なビット数のみを使用します。データ取得に必要なインストラクション数を最小化するために，アンアラインドメモリアクセス(unaligned memory access)などのテクニックを使用しています。このような最適化を積み上げるため，私たちはHollowを，x86-64アーキテクチャを前提として開発しました -- 現時点ではリトルエンディアンと，アンアラインド読み込みに対するペナルティのない(あるいは無視できる)ことが前提となっています。将来的に移植性を向上するためには，こういった最適化を選択可能にすることを考える必要があります。

InfoQ: Javaに関連して，２つの疑問があります。実装に(Go言語などではなく)Javaを使用すると決めた理由は何ですか？Java以外のアプリケーションでもHollowを利用可能でしょうか？

Koszewnik:Javaを使用することにしたのは，ビデオのメタデータを扱う直接的なコンシューマシステムがJavaベースの言語で開発されていたからです。Javaベース以外の言語からは，今のところHollowのメリットを直接的に利用することはできません。

InfoQ: 最後の質問です。HollowはAWSおよびS3専用でしょうか？ベンチマークやロードマップといったものは公開されていますか？

Koszewnik: いいえ，Hollowでは，生成されたブロブを実際にプロデューサからコンシューマに分配する上で，インフラストラクチャの提供や特定はしてはいません。クイックスタートガイドを読み始めた将来的なユーザは，まずAWS S3/DynamoDBベースのインフラストラクチャのプラグインを使って，実運用レベルに拡張可能なサンプルプロジェクトの構築を実習します。ですが，PublisherやAnnouncer，HollowBlobRetriever，HollowAnnouncementWatcherといったこれらのサンプルを，他のインフラストラクチャへの実装のガイドとして使用するのは，それほど難しいことではありません。

ベンチマークについては，データモデルによってさまざまな結果が出るため，提供を避けてきました。その結果が，いずれの方向に対しても誤解を招きかねないからです。POJOと比較した場合のトレードオフが，Hollowのレコードからデータをアクセスするという非常にわずかなペナルティと，ヒープフットプリントの削減という大きなメリットであると言えば十分でしょう。

厳格なロードマップはありません -- 個人的に取り組んでみたいことはいくつかありますが，プロジェクトが最大の改善を実現できる活動をする上では，特にユーザビリティに関して，コミュニティによる広い視点からのフィードバックを期待しています。

Hollowの利用方法については，githubサイトに詳細な情報がある。