“キャッシュ”が新しいRAMとなる

これはDefrag 2014の講演内容です。

Screen Shot 2014-11-11 at 3.37.03 PM

テクノロジに長く従事することの(数少ない)利点の1つは、いくつもの技術サイクルの始めから終わりまでを見ることができるということです。いかにしてブレークスルーが実際に広まるかを見られるのです。サイクルの曲線の一部分しか見なければ、全体を正確に測り知るのは難しいでしょう。短期間で起きた進歩を見過ごしてしまうか、長期間で起こる進歩を見届けられないかのどちらかです。驚くべきことは世の中の事象がいかに速く変化するかではなく、その変化に呼応するエンジニアリングの変革がいかに遅いかということです。画像は、1891年に発明された、電話回線を自動で接続するストロージャー式自動交換機です。

Screen Shot 2014-11-11 at 3.37.53 PM

1951年、デジタル交換機の最先端において、典型的な中央電話交換局はビクトリア期の特大サイズでした。ストロージャー式自動交換機は、通信中の全ての電話の信号を扱っていました。

その時代から見れば、これが最先端を行くハイテクでした。当然、今の私たちから見れば、これが世界最大のスチームパンク的な設備と言えます。

Screen Shot 2014-11-11 at 3.42.16 PM

このことにに対して優越感を感じるのはおそらく間違いでしょう。集積回路が発明されてから65年が経ちましたが、いまだに私たちの周りには数十億と存在し、ブンブン回りながら、カチカチと音を鳴らし、そして壊れてもいきます。交換機が完全なるソリッドステートコンピューティングへ移行をしている最前線に私たちがいられるのは今だけです。

最もワクワクする技術変革は、新型のモデルがようやく実現可能になったとき、または従来の制約が外れたときです。どちらも今まさに、私たちの業界で起きています。

Screen Shot 2014-11-11 at 3.42.40 PM

分散コンピューティングは、ソフトウェア全体を通じて、主要なプログラミングモデルになってきています。いわゆる“中央処理装置(CPU)”はもはや中央にはなく、装置ですらありません。CPUはデータの山を這う多くの虫の1匹に過ぎず、最後の砦となるのはデータベースです。

Screen Shot 2014-11-11 at 3.43.37 PM

一方で、RAMとハードドライブのストレージ間のレイテンシの差は重要ではなくなってきています。30年来、データベースのパフォーマンスは、RAMにあるランダムデータにアクセスするのに要する時間と、ハードドライブにアクセスするのにかかる時間との巨大な差異が重要な問題でした。今や全てのデータをRAMに保存するので、つらい思いをすることはなくなりました。Bツリーを使って、mmapを呼び出して、それでおしまい、では終わりません。まだ解き明かすべき真のメモリネイティブな設計への示唆はたくさんあります。

この2つの潮流は、アプリケーションを考え、設計し、構築する、全く新しい方法を生み出しています。私たちのここまでの軌跡、現状、そして将来の展望について少しお話ししましょう。

Screen Shot 2014-11-11 at 3.44.15 PM

その昔、アーキテクチャ図内の全てのコンポーネントは、それぞれ定冠詞がありました。各コンポーネントは別々の機能を果たし、“the”データベース、“the”Webサーバ、といったように、一つの部屋の中で繰り広げられるドラマの登場人物のようなものでした。ちなみに、“クラウド”という用語が生まれたのもここからです。フワフワした雲が外部WANを表す標準的なシンボルであり、その詳細については気にする必要がありませんでした。

Screen Shot 2014-11-11 at 3.45.10 PM

分散コンピューティングはあっさりと主流になりました。複数台の同一アプリケーションサーバは“ロードバランサ”の背後に隠され、仕事量は多かれ少なかれ均等に分散されていました。負荷分散させることだけが、多くの哲学的問題を回避する、確固としたアーキテクチャでした。システムが拡張するに従い、コンポーネントが包囲をし始め、最終的には“the”データベースを取り囲むことになりました。サーバは1台しかなく、高速なディスクと、より速いCPUを備えた特別なデータベースサーバにお金をかけるのは普通のことである、と私たちは自分たちに言い聞かせました。ハードウェアベンダーは当然喜びました。

Screen Shot 2014-11-11 at 3.45.42 PM

ようやくデータベースレプリケーションが手ごろになり、私たちは、ホットスペアのデータベースを追加することで良心を慰めました。そして、もはやSPOF(単一障害点)はなくなった、と自分たちに言い聞かせたのです。ほんのわずかな間でもそう思ったのは事実です。

ホットスペアはあまりにも魅力的で、待機状態のままにしておくことは当然出来ませんでした。経済アナリストは、稼働中の本番環境データに対して、本番環境に影響を及ぼすことなく、大量のクエリを走らせることができると気づきました。 すると“ホットスペア”と呼ばれたサーバは、本番環境のコピーとして常時使用され、ミッションクリティカルなものになりました。私たちは、スペアが必要になることがあれば非常時の間だけ切り替えて利用すればいいのだから問題ない、と自分たちに言い聞かせました。しかしこれは、車にスペアタイヤが必要になったらいつも他の車から盗めるので積んでおく必要がない、と言っているのと同じことでした。

Screen Shot 2014-11-11 at 3.46.59 PM

Brad Fitzpatrickが、メモリにデータをキャッシュするデーモンであるmemcachedを発表しました(名前が表すとおりです)。非常に実用的なソフトウェアで、当時の流行にのっとって言えば、分散ハッシュテーブルの簡易版のようなものでした。レプリケーション、シャーディング、ロードバランシング、シンプルな算術演算子など、多くの特徴がありました。私たちは、負荷がかかる大半は読み込みであると自分たちに言い聞かせていました。ではなぜ、データベースは何度も同じクエリを実行し、ディスクのスラッシングを起こすのでしょうか? 必要だったのは、大容量のRAMを積んだ、大量の小型サーバーでした。ハードウェアベンダーが喜んだのは言うまでもありません。

そこに・・・キャッシュ無効化のコードを書かないといけないかもしれませんが、難しいことではありません。そうですよね? 

Screen Shot 2014-11-11 at 3.47.06 PM

memcachedの設計に非常に長い道のりを歩んだという点は評価できます。ハードドライブのランダムI/Oパフォーマンスを、複数のRAMのランダムI/Oパフォーマンスに置き換えました。それでもさらに、データベースサーバは大きくなり、さらに稼働し続けました。私たちは、キャッシュに少なくとも作業データと同じくらいのRAM容量が必要である(そうでなければ非効率です)ということを理解し、さらに、キャッシュの整合性という耐え難い悩みの種にも気づきました。しかし、私たちは、これは“Webスケール”にかかったコストである、と自分たちに言い聞かせました。

Screen Shot 2014-11-11 at 3.47.12 PM

もっと気になるのは、アプリケーションが洗練され、気軽なものになって来ているということでした。ほとんどの場合、アクセスの度にデータベースへの書き込みは複数実行されていました。読み込みではなく、書き込みがボトルネックになってきたのです。こうして、私たちはとうとうデータベースのシャーディングに真剣に取り組むことにしました。Facebookは当初、ユーザデータを大学で振り分け、“ハーバード大学データベース”というようなコンセプトで長い間逃げ切っていました。Flickrもまた良い例です。PHPで手製のシャーディングシステムを作り、ユーザIDのハッシュ値によってデータベースを分割しました。memcachedがキーでシャーディングするのとほぼ同じ方法です。FlickrのTech Talkではテーブルを非正規化する必要性やコメント、メッセージ、お気に入りなどのオブジェクトを二重書き込みすることに関する素敵なヒントが述べられています。

それまでの全てを解決して無限にスケールするための代償としては、大した労力ではありません。そうですよね? 

Screen Shot 2014-11-11 at 3.47.18 PM

リレーショナルデータベースを手動でシャーディングする際の問題は、リレーショナルデータベースを保持しないということです。シャーディングを行うAPIは実際はクエリ言語になっています。運用におけるあなたの頭痛は解消されませんでしたし、筐体を超えてスキーマを変更するつらさは実際のところ悪化していきました。

多くの人はここで深呼吸をし、SQLの実装における全ての制約と難点をカタログ化します。そして何らかの理由でSQLのせいにしてしまうのです。NoSQLに先見性を見出した人たちとXMLデータベース難民があふれ、豪語しています。彼らは自動シャーディング、フレキシブルなスキーマ管理、何らかのレプリケーションなどを提言しました。当初はこの程度のものでしたが、自分で書くよりはつらくありません。

「自分で書くよりはつらくない」というのが、精一杯のセールスポイントである場合、必死の状況であることは分かりますね。

Screen Shot 2014-11-11 at 3.47.25 PM

通常のクライアントツールを使ったデータの操作や解析を諦めたということを考えると、NoSQLに移行することは、手動でシャーディングするよりもマシではありましたが、優れているとも言えませんでした。ビジネスマンによって書かれていたSQLクエリは、開発者によって管理されるレポート内の手書きコードへと変わっていきました。

バックアップや解析に使用していた“ホットスペア”のデータベースは、仕返しとばかりにHadoopファイルストアやHiveクエリといった形で復活しました。これが機能し、大部分においてはビジネスマンから干渉されなくなりました。一番の問題点は、これらのシステムにある運用上の煩雑さです。スペースシャトルのように、信頼性がありほぼメンテナンスが不要なシステムとして売り込まれましたが、結果的にものすごく細かな管理が必要だったのです。さらに、行き交うデータの取得も問題でした。1日に発生する遅延時間(!)は、それなりに良いものだと考えられていました。そして、このシステムは、ネットワークとディスクのI/Oバウンドを同時に管理するものでした。私たちは、これは、ビッグデータの段階に進むためには仕方のないことと自分たちに言い聞かせていたのです。
とにかく、これがGoogleが行っていることです。そうですよね?

Screen Shot 2014-11-11 at 3.47.32 PM

さまざまなNoSQLデータベースが成熟するにつれ、APIに不思議な現象が起きるようになりました。NoSQLがSQLのようになってきたのです。これは、SQLが関係集合論を直接的に実現するものだからであり、計算をごまかすことが困難だからです。

Screen Shot 2014-11-11 at 3.47.46 PM

Paul GrahamのLispに関する鼻持ちならないコメントを引用すると、group by、filter、joinを加えると、新しいクエリ言語を作ったことにはならず、それはひどいシンタックスやオプティマイザのない全く新しいSQLの方言を作ったに過ぎません。

なぜなら、私たちはSQLを避けた道を選択したので、ほとんどのシステムから極めて重要な、関係集合論で設計されたストレージエンジンとクエリオプティマイザが欠落しているのです。それらを後から追加すると、パフォーマンスに深刻な影響を及ぼします。正しいシステム(もしくは、RAMに常駐することで覆われたシステム)では、正常のレプリケーションのように他の部分が欠落してしまっています。

誰もが聞いたことのある、大きな成功を収めたWebスタートアップでは、この差を補うために“4つ”の異なるNoSQLを使用しています。

Screen Shot 2014-11-11 at 3.47.54 PM

“the”データベースや1000万ナノ秒のランダムシークタイムの世界に後戻りすることができないのは明らかです。
「すべてを解決する1つの確かなこと」を探すという、終わることのないハイプサイクルの裏では、痛点は別の新しい痛点が伴う賢いアプローチによって緩和されるという、興味深いパターンがあります。

Screen Shot 2014-11-11 at 3.48.01 PM

では、このごちゃごちゃした図に加える次の複雑な装置は何でしょう。シンプルにすることがトリックかもしれません。

例えばRAMです。データをキャッシュしたり計算したりするために、“データベース”サーバには多くのRAMを積んでいます。また、memcachedサーバにも大容量のRAMがあります。これらのシステムにあるRAMの合計は、少なくともあなたの作業用データセットのサイズに等しくなるはずです。そうでない場合は、キャッシュが不十分ということです。また、キャッシュのレイヤが100%効果的であるかどうか非常に疑問です。キャッシュに保存されたものの、削除される前に一度も読まれることのないデータをたくさん持っているということに私はお金をかけてもいいです。それらをトラッキングすらしていないことにもっとお金をかけてもいいでしょう。あなたが悪い人だと言っているのではありません。データをキャッシュすることは、その価値よりも問題となることが多いということです。

これらのコンポーネントが与えてくれる多くの機能は、構成が可能でお互いに補い合っていると言えます。もちろん、それぞれがより良く準備されていればですが。

Screen Shot 2014-11-11 at 3.48.07 PM

分散システムで、データは常にソリッドステートだと確立されれば、全てが簡素化されるという興味深い現象が起きます。普段はクエリ実行のときにのみに使用される“テンポラリ”のメモリデータ構造が、唯一のデータ構造になります。ランダムアクセスは大罪ではなくなり、一般的な過程となります。ページを分けたり、分散しなおしたり、データの局所性を気にする必要はないのです。

Screen Shot 2014-11-11 at 3.48.13 PM

これは良くできたシンプルなアーキテクチャです。ロードバランサがアプリケーションサーバを取り除くように、SQL“アグリゲータ”は、データの読み書きの調整といったごちゃごちゃした記述を取り除きます。これにより、安定したAPIの裏側でデータ配置のストラテジの最重要部分が保たれ、少ない混乱で両方に変更を加えることが可能になります。

Screen Shot 2014-11-11 at 3.48.24 PM

これですべて問題ないですね。ようやく、納得できる歴史の最終地点に到達しました。そうですよね?

Screen Shot 2014-11-11 at 3.48.30 PM

いつの時代に生きていようとも、コンピュータの技術水準に自己満足してしまってはいけません。いつでも何かしらのボトルネックはあるのですから。

Screen Shot 2014-11-11 at 3.48.35 PM

これは、比較的新しいデザインのAMDの“Barcelona”チップです。4つのコアがあり、表面の大部分はコアを取り囲むようにキャッシュとI/Oが配置されています。WalMartの周りに巨大な駐車場があるようなイメージです。Pentiumの時代では、ダイにキャッシュは15%ほどでした。コンピュータにおける第3世代、防音装置、革命とは、メモリと比較してどのくらい速いCPUであるかということです。この高価な基盤にキャッシュが置かれているのには、理由があります。

データベースパフォーマンスを左右する主な要因は、RAMとディスクにあるレイテンシの差にありました。現在では、CPUキャッシュとRAMにあるレイテンシの差は全く同じ種類の問題ではないと、みんな笑っています。しかし、同じ問題なのです。

Screen Shot 2014-11-11 at 3.48.44 PM

それは、実際には存在しないのに、共有メモリが存在すると振る舞っているようなものです。多くのコアと多くのRAMがあれば、必然的にいくつかのコアはRAMの一部の代わりになるでしょう。

Screen Shot 2014-11-11 at 3.48.53 PM

突き詰めて言えば、コンピュータができることは、記号を読み書きするという2つのことだけです。パフォーマンスは、コンピュータがどのくらいのデータを制御し、それがどこに配置されるのかという機能にあたります。満足のいくあり得るケースとしては、次々と止むことなく行き交うデータを一度だけ読み取り、それを素早く処理し、二度と同じことをする必要がないということです。GPUがこの良い例です。しかし、もっとも興味深い作業量は、こういったことではありません。

Screen Shot 2014-11-11 at 3.48.59 PM

追跡されるすべてのランダムポインタは、キャッシュミスとなります。同じ場所にあるメモリ(例えばwriteロック)でのすべての競合は、調整に大きな遅延を引き起こす原因になります。CPUのキャッシュヒットの割合が99%だったとしても(実際は違いますが)、RAM上で待機に費やす時間は、依然として重要です。
もしくは、こう考えてみてください。ディスクは新しいテープであり、RAMは新しいディスクあったとすれば、CPUキャッシュは新しいRAMであるということです。局所性は重要なのです。

Screen Shot 2014-11-11 at 3.49.05 PM

では、何がこの問題を解決しますか? どうやら、そこには昔ながらの根本的な矛盾があるようです。私たちが最適化するのはランダムアクセス、それともシリアルアクセス? パフォーマンスに不利な条件となるのは書き込み、それとも読み込み? 私たちはただじっと待っているだけで、ハードウェアにすべてを任せてしまう? 恐らくメモリスタや他のテクノロジが、これらを意味のないことにしていくのでしょう。難しいと思いますが。

良い知らせなのは、分散データベースの総物理アーキテクチャが安定してきていることです。データクライアントは、心臓部分や4つもしくは5つの異なるサブシステムの内部とやり取りする必要がなくなります。これはまだ完全ではなく、主流にもなっていません。主流になるにはまだ時間がかかります。

しかし、もし次のボトルネックが実はメモリの局所性にあるとしたら、その他は成熟していくでしょう。新しい技術革新は、データ構造やアルゴリズムになっていく傾向です。全てを修正するといった全面的なアーキテクチャの大変革が少しはあるかもしれません。運が良ければ、同じAPIが露出している中で、この先15年の間に注目されることなくSQLデータベースは速くなっていくでしょうし、効率も良くなっていくでしょう。

しかし、繰り返しますが、この業界に平穏な時などはないのです。