sdyuki-devel

2009-12-26

RDBに代わるスケーラブルなデータモデルの必要性 20:14

このあたりの内容を卒業研究にする予定で、中間報告書まで書いたけど、整理と裏付けが全然追いつかなくて卒論なんて書けそうにないので、とりあえずテキトーにブログに書いておくなど。


データストアには、状態を永続化して共有する機能と、データモデル(状態を操作する意味論)を規定する機能の、2つの機能がある。この2つの機能を、より使いやすく、より高速に、よりスケーラブルに提供することが求められる。そうでないとシステム全体が成り立たない。


冗長化とか負荷分散とか、ハードの質に頼らない高性能なシステムを構築したいときは、「状態を持たないようにする」のが定石になる。同じ状態を2台のホストで同期し続けたり、状態を分割しながら整合性を保ち続けるのは、非常に難しい。このため、状態は共有データストアに保存しておくのがもっとも簡単で、現実的な解になる。


MVCアーキテクチャにおけるViewとControllerはModelの上に成り立っており、そのModelの実装は、データストアの機能に依存するところが大きい。データストアがアトミックな操作を一切サポートしていなければ、いくらModelでがんばっても、高速なトランザクションを実現するのは難しい。データの検索や絞り込みについても同じで、データの物理的な分布を知らないアプリケーションがいくらがんばっても、高速な実装は難しい。


従来は「高級」なデータモデルを保ったまま、状態を共有する機能を高めてきたが、ここにきて困ったことに、物理的な限界が見えてきてしまった。

…と言うと正しくないかも知れない。物理的な限界には達していないのだが、(高級なデータモデルを保ったまま、状態を共有する機能を高めるのは、高級なデータモデルを諦めることに比べて)コスト的に高くなってしまう、と言う方が正確かも知れない。

@frsyuki データモデルが関係代数などが規定する論理的な構造、サーバへの保存はストレージのモデルで物理的な構造。この2つの組み合わせでいいのでは。

http://twitter.com/masayh/status/6654253395


経済原理はこの意味では、論理か物理かのいずれを優先するかを選ぶといえます。保守による長期的コスト低下より、短期開発による売り上げの増大や開発コスト低下を選んだのでしょう。

http://twitter.com/masayh/status/6655773843


同様にコスト低下はクラウドを生みだして、サーバ集約やスケールによる物理レベルでの解決も併用するようになった。これは理性レベルでの生産性、保守性だけでの追及では飽き足らなくなった貪欲な経済原理の進展を意味します。

http://twitter.com/masayh/status/6655822982


ここで言うデータモデルの「高級」さとは、「アトミックに更新できる単位が大きい」ことを意味している。

アトミックに更新できるとは、あるデータを書き換えるときに、すべて更新されるか、まったく更新されないかの、どちらかにしかならない、ということである。一部のデータだけが更新されたような中途半端な状態にはならない。


例えばRDBMSはとても高級なデータモデルを提供していて、すべてのデータをアトミックに更新できる(アトミックに更新できる単位が全データ)。どこのデータを選んできても、アトミックに更新できる。

この特性がどれだけ重要かは、あまり理解できていないが、普段RDBMSを使っている方々にしてみれば当然のことの様に重要なのではないかーと予想している。


一方でKVS(key-value store)はとても貧弱なデータモデルしか提供していなくて、1つのデータしかアトミックに更新できない(アトミックに更新できる単位がvalue)。あるvalueを更新するとき、そのvalueの前半の数バイトだけ更新されたような中途半端な状態にはならないが、複数のvalueをアトミックに更新することはできない。


なぜ今になってkey-valueなる貧弱なデータモデルが(一部で)流行し始めたかと言えば、アトミックに更新できる単位を限定した方が、スケーラブルな実装が作りやすいのである。


ここで、CAP定理という(誤解されやすくて誤用しやすい)法則がある。

複数のサーバの分割して保存されたデータを、必ず Atomic に更新できるように保証しようとすると、応答を返せなくなってサービスが止まってしまうことがあるので、サービスの可用性を向上させるには、Atomic に更新するデータは複数のサーバーに分割しないようにするか、Atomic に更新することを諦めるしかない(と読めたけど違うかも)。


そこで、CAPのどれを捨てるかと言う議論がある。


例えば、複数のデータを更新するときに、Atomicでなくても良いとすれば(CAPのCを捨てる)、Availability と Partition Tolerance を満足できる。つまり、一応は複数のデータを非同期に(Atomicでなく)更新できる特性を保ちながら、いつでも高速に応答できて、複数のサーバーにデータを分割してスケールアウトできる。

一方で、たまにデータがロックされっぱなしになって応答を返すのに時間がかかるような状況になっても良いとすれば(CAPのAを捨てる)、分散トランザクションなどを使って、Atomic と Partition Tolerance を同時に保証できる。

あるいは、データを複数のサーバーに分割してスケールしなくても良いとすれば(CAPのPを捨てる)、データをすべて1台のサーバーにまとめて Atomic と Availability を同時に保証できる。


…が、詳しくは前の参考文献にお任せして、分かりやすい観点だと、Atomic に更新可能な範囲を広くすると、その範囲では(物理法則的に)スケールアウトできないんだーというのがポイントだと思う。

つまり、スケールアウトが必要なら、すべてのデータをAtomicに更新できるというRDBMSのデータモデルに代わる、新しいモデルを考える必要がある。RDBに代わるスケーラブルなデータモデルが必要だ。


ときに、本当にスケールアウトする必要があるのか、という話がある。根本的だけど、実はここが一番紛糾しているんじゃないかと思う。

「クラウド」はマルチテナントシステムなシステムで、1つの企業だけで使う物ではない。だから1つに企業にとっては、スケールアウトする必要は無いとも言える。しかし「クラウド」がアノ価格で使えるのは、スケールアウトするシステムがあるからだろう。クラウドの価格が魅力的に映るのであれば、ウチにはスケールアウトは必要ないとは言えないハズだ。

それは規模の経済性が働いているからアノ価格になるのであって、巨大企業でもない組織が、ちまちまとスケールアウトするシステムを作っても意味がない、という話もあるだろう。しかし技術的に巨大企業に依存してしまうのは、また別の問題があると思う。


今はまだ、その新しいデータモデルが確立されていない時期だと思うので、そのあたりの知見を独占されずに収集しておくという意味でも、データモデルについてはよく考えておきたいところ。


データを分割して分散しなきゃならんねぇと考え始めると、次にそのデータを扱って何か処理を行いたいときに、「データを移動させるよりプログラムを移動させた方が速い」という話が出てくる。そこでMapReduceが出てきたりする(分散データストアのデータモデルは、それ以前の話になる)。分散されたデータの保存と処理も合わせて、分散システム全体を統合して考えられるようなデータモデルを確立できないかなぁ、と思う。

kazuki-aranamikazuki-aranami 2009/12/27 09:16 こんにちはこんにちは!!


分散システム全体を俯瞰して、どのようなアーキテクチャーを採用すれば、
スケーラブルなWebシステムが構築できるのか、という問いかけにはいくつか
解決策が提案されています。


Key-Value型データストアが、より柔軟なデータモデルを持てるようにする
ためには、id:kazunori_279 さんの提唱する「Smalltable」があります。


また、CAP定理に関しても手前味噌ですが、アプリケーションサーバーの
レイヤーで「分散キャッシュ」を用いることで、ある程度この問題を解決
することができると考えています。


詳しくは、下記のエントリーをご覧下さい。



スティルハウスの書庫 BigtableとSmalltable
http://d.hatena.ne.jp/kazunori_279/20091214/1260790814


Googleがスケールする理由は分散キャッシュ!?
http://d.hatena.ne.jp/kazuki-aranami/20091019/1255963688


ACID特性とBASE特性、CAP定理を打破するには?そして、複雑なクエリーへの解
http://d.hatena.ne.jp/kazuki-aranami/20091027/1256635161


分散キャッシュの世界を知る (Oracle Coherence、JBoss Cache)
http://d.hatena.ne.jp/kazuki-aranami/20091020/1256030402

viverviver 2009/12/27 16:42 Smalltableはキャッシュ階層ですねぇ。データとデータを使うプログラムの間の「距離」が遠くなるほどキャッシュは効果的になりますが、「Googleのサーバー」と「クライアント」の間にはインターネット回線があって遅延が大きいので、キャッシュは相当に効くでしょう。いいアーキテクチャだと思います。

それから『Smalltableは、Datastoreが保持するすべてのデータのうち、そのユーザーが常時使用するデータのみ保持するサブセット』のように、(アトミックに更新可能な)データを分割しているのがポイントですね。分割できればスケールする。分割できなければスケールしない。『ローカルのデータが大きくなると遅くなる』

SQLが使えるのがやっぱり嬉しいのであれば、分散データストアで最初からSQLを使えればいいんじゃないかという気がしますね。これはBigtableのデータモデルだと、ちょっと足りない。Row->Columns->Valueでは1階層足りなくて、Partition->Row->Column->value(つまりPartition->RDBMS)が必要。

つまるところ、Multidimensional Table形式のバックエンド + 分割されたRDB形式のフロントエンド という形のデータモデルがいいのではないか。これは良い感じです。

それにしても、楽観的ロックに基づいたキャッシュはイケてますねぇ。write-back cacheと言うか…Software Transactional Memory?
商用のイケてる分散キャッシュと、イケてないmemcachedの差はこのあたりにある気がします。

kazuki-aranamikazuki-aranami 2009/12/27 22:48 今後の展開としては、スケーラブルな分散システムの実現に必要な事柄、
つまりタネンバウム先生の「分散システム 原理とパラダイム」のような
学術的要素の高い世界を追求するアプローチがひとつ。


もうひとつのアプローチは、経営的な視点として、Hadoopに代表される
ソフトウェアを活用して、バッチ処理で非常に長時間を要している現状を
鑑みて、効率的なデータの活用(BI:ビジネスインテリジェンス)を
追求することではないかと思っています。


超並列リレーショナル・データベース Teradataデータベース
http://www.teradata-j.com/product/db/index.html

viverviver 2009/12/28 00:01 (特にこのあたりのシステム系の)学術的な追求は、単体では存在し得ないんじゃないかなぁ、というのが個人的な見解です(マユツバモノですがw
まず経営的な視点に立って、だんだん問題を分解していった結果として成り立つ、というか…。

しかし実際にビジネスしていないので、何が問題なのか知る機会が乏しいところにヒジョーに問題があると思っているのですが、なかなか難しいところです。

そこで、なるほど。バッチ処理の高速化、BI、あるいはデータマイニングあたりが、問題になっているんですね。

Teradataは…聞いたことが。最近楽天に導入されたようです。(あれROMAとfairyは?)
http://www.teradata-j.com/press/2009/20091020.html

しかし、これまた高そうですね…。SybaseやVerticaなどなど列指向型のデータベースは他にもあるようですが、どれも Oracle RAC 並に高そうです。
これらの安価な代替としてHadoopが期待されているようにも見えますが、特にHBaseのところが今後どうなっていくのか、要注目だと思っています。データストア部分の「垂直」方向のスケーラビリティによって、やれることがだいぶ変わってくるはず。

ここから分解して学術的も面白そうなことは、列指向DBや行指向Dから発展してきている垂直方向のスケーラビリティに関する技術と、分散KVSやMapReduceの方面からやってきた水平方向のスケーラビリティに関する技術の、整理と統合、より高い効率と信頼性の追求…でしょうか。
手始めにデータモデルの再編は分かりやすいところです。前に書いたのですが、key-valueでは垂直方向の効率が非常に悪い:http://d.hatena.ne.jp/sdyuki/20091116/1258350905

分散データストアの要素技術は既にコモディティ化しているので、この続きをやるなら、それを利用したビジネスか、実世界への適用と運用面の作り込み、あるいは垂直方向のスケーラビリティの統合あたりしかないという話もありますね。

私は今のところ、ビジネスや作り込みは不得意なので、新しい技術を取り入れる方をやりたい感じです。
ぃゃしかしビジネスもやっておかないと乖離してしまうなぁ…

kazuki-aranamikazuki-aranami 2009/12/28 00:57 >面白そうなことは、列指向DBや行指向DBから発展してきている
>垂直方向のスケーラビリティに関する技術と、分散KVSやMap
>Reduceの方面からやってきた水平方向のスケーラビリティに
>関する技術の、整理と統合、より高い効率と信頼性の追求ですね



まさにこれらの追求をしている最中ですね。


そうなるとnosql-jaの過去ログで、古橋さんが「Chubbyがスケーラ
ビリティと整合性のバランスをどのあたりで取っているのか
(例えばごくまれな不整合を許容してるとか?)も興味があります。
いずれにせよ、分散KVSには分散ロックサービス(悲観/楽観)も
必要だな〜と思います。」と述べています。


また、佐藤さんも「分散ロックサービスChubbyでロックしてるの
だろうと思います(実装方法は開示されてないので推測ですが)。
Chubbyがスケーラビリティと整合性のバランスをどのあたりで
取っているのか(例えばごくまれな不整合を許容してるとか?)
も興味があります。」と述べています。


Hadoop、HBase、そしてOSSになっていない、Chubbyについても
「楽観的ロックに基づいたキャッシュ」という考えをベースに
して、分散キャッシュ(Oracle Coherence、コーヒーたん)
あたりを研究することで、OSSのクローンが可能になるではないか、
と考えています。