第一回のコラムでクラウドコンピューティングの本質とは、どのような技術によって実現されているかではなく、コンピュータシステムの利便性如何であると主張した。これは利便性の向上というサービス特性を実現する事が目的であり、技術はその目的のための手段でしかないという事であるが、何も技術を軽視している訳ではない。経営判断、事業戦略としてはまず目的ありきである事を強調したかっただけである。技術がなければ目的であるサービス特性は実現できず、目的が明確でなければどんな技術であっても導入、適用のしようが無い。目的と技術は表裏一体であり、どちらが欠けてもITビジネスは成立しないのである。

去る2010年6月9日(水)、Interop 2010会場である幕張メッセ会議棟の一室にて、Interop Cloud　Computing　Competition(以後ICCC)が開催された。ICCCは奈良先端科学技術大学院大学の門林雄基准教授が実行委員長を勤め、学生から社会人までを対象としたクラウド関連技術コンテストである。今年、第2回目を迎えるこのコンペティションは高校生、大学生、大学院生といった若手技術者が多くエントリーする傾向があり、昨年開催された第1回のグランプリは筑波大学4年生(当時)の古橋氏を中心としたチームえとらぼのkumofsであった。このkumofsはその後オープンソースとして公開され、さくらインターネットやニコニコ動画のドワンゴなど、多くの民間企業で検証され実用化されつつある。

今年第2回のグランプリでは、またもや社会人ではなく東京工業大学大学院の長尾氏、鈴木氏によるHIBIKIプロジェクトであり、特別賞も電気通信大学の堀内氏、小西氏等によるmyCloudが受賞した。グランプリを取ったHIBIKIはkumofsと同じく分散型キーバリューストア技術の一種で、従来型のChord-DHT空間に対し、新たに物理ロケーションを考慮したグループ属性(ラベル)を加えたものである。LFRT(Labeled Flexible Routing Table)という長尾氏独自のルーティングアルゴリズムによって、DHTの広域性を維持したままKVS的なゼロホップ探索を可能とし、高効率なP2Pネットワークを実現するという発明である。


さて、ここまで読み進めた時点で、既に本コラムにアレルギーを感じてしまったクラウド事業関連の経営陣、事業責任者は少なくないのではないだろうか。先日、現在クラウドサービスを強力に展開している某企業の方と話しをする機会があった。彼はそのクラウドサービスを担う事業部の所属では無いが、クラウド関連技術に対する造詣は深く、DHT(Distributed Hash Table)やKVS(Key Value Store)といったクラウドコンピューティングに利用されている技術の話題になった。ひとしきり議論を経た後、彼はなぜか溜息をつき、「実は、うちのクラウド事業部長はMapReduceとかDynamoとかを知らないのだ。もちろんHadoopとKaiもね。」と嘆いた。

先に言った様に目的と技術が揃わなければビジネスが成立しない。クラウドビジネス責任者が、その成立用件の一方について、全く知識と理解を持ち合わせずに、事業を牽引し推進していく事ができるのであろうか。その某事業部長のために簡単に要約すると、MapReduceはGoogleの検索用インデックスを作成するための分散処理プラットフォームである。従来の分散処理と異なる部分は、前処理と後処理という二つの処理がそれぞれ独立して実行可能な用途に最適化されており、クロールしたHTMLドキュメント中の文章を形態素解析によって単語に分割し抽出するのがMap前処理、その分割された単語の数をカウントするのがReduce後処理である。検索サイトがクロールするドキュメントはそれこそ数千万から数億ページにも達するため、ページ単位で別々の処理インスタンスが同時並行処理できるように開発されたシステムだ。そしてHadoopはこのMapReduceのオープンソース版である。またDynamoはAmazon社が開発した分散型のキーバリューストアで、Amazonの通販サイトやAWSのS3ストレージシステムとして利用されている。KaiはDynamoのオープンソース版である。が、しかし、この程度の情報はネット上で検索するだけで得られる。それさえも行なっていないということは、元々クラウドビジネスに興味が無いのではないのか？

もし、読者諸兄の中で技術者でも専門家でもないが、クラウドビジネスに興味がある、もしくは検討しているというのであれば、今回、試しにKVSとDHT、そしてそれら両方の長所を兼ね備えたLFRTについて、そのイメージだけでも理解してみる事に挑戦してみようではないか。残念ながらLFRTについては、まだ長尾氏から論文が発表されて間もなく、当然検索サイトで探してみてもほとんど詳しい情報は得られない。HIBIKIのLFRTに関しては長尾氏のブログとICCCでの発表資料程度しか手掛かりがないが、その乏しい情報から筆者が理解したLFRTのアルゴリズムを解説してみたい。

まず、手元に英和辞書(書籍)をお持ちではないだろうか。無ければ無くても構わないが、あれば手にとってほしい。辞書の小口を見ると左上から右下に掛けてアルファベット順につめかけが付いているだろう。英単語を調べる場合、まず単語の先頭文字に一致するつめかけページを開き、つぎに二文字目、三番目と順番に文字が一致する記載を後のページに向かって探すということを繰り返す。

ここで特別な辞書を想像してみる。この辞書のAのつめかけページ(A項目の先頭ページ)を開くと、その見開きページにはAからZまでのつめかけページ番号のリストがある。同様に、各アルファベットのつめかけページには自身を含む全アルファベットのつめかけページのリストがある。Tigerという単語検索をGから始める場合、まずGのつめかけページを開き、Tのつめかけページを調べる。すると、Tはp200という事がわかる。すると200ページにとんで、そこからTigerを探して「虎」という日本語翻訳を得る。このように全てのつめかけページが、他の全てのつめかけページ情報を持ち、それによって単語の意味を引くというアルゴリズムがKVSである。つめかけページがノード、ページ番号がノードID、もしくはアドレスで、英単語がキー、その日本訳がヴァリューに相当する。

常に各つめかけページが他の全てのつめかけページ番号を持つKVSでは、仮にアルファベット文字数(ノード数の事)が極端に増えた場合、見開きページサイズから溢れる問題が発生する。実際にアルファベットが26文字を超える事は無いが、この辞書がいずれギリシア文字やロシア文字までも網羅する事になるかもしれない。このような時、全てのアルファベットのつめかけページ番号を保持するのではなく、部分的なページ番号だけを持たせるだけで全てのアルファベットを検索しようというのがDHTである。DHTには幾つかのアルゴリズムがあるが、ここでは環状空間を利用したChordを例にして説明する。

各つめかけページのリストは全てのアルファベットを含まず、部分的なアルファベットのリストだけを載せる。その規則は、自分から見て近い部分は密に、遠くなるに従い疎にする。図2で示すように、Ａから見て、2^{n -1} 番目のアルファベットだけをピックアップし、そのアルファベットのページ番号だけをリストに記載する。

Aのつめかけページ

KVSでの例と同じようにAから初めてTigerの日本語訳を引いてみよう。図2から解るようにAのつめかけページにはTのつめかけページ番号が無い。そこで、Tの前方にあり、一番近いアルファベットのつめかけページを調べる。この場合、Aが知っているページ番号でTの前方で一番近いアルファベットはPである。そこで、Pのつめかけページであるp160を開いてみた。しかし、PのつめかけページにもTのページ番号が無い。そこで、Pが知っているTの前方で一番近いアルファベットSのつめかけページを開く。するとSのつめかけページにはTのつめかけページ番号があり、p200となっている。これで無事にTのつめかけページにたどり着き、そこからTigerを引く事ができた。KVSに比べると、目的とするつめかけページ、すなわちノードへ到達するまでに何度かの繰り返し問い合わせを必要とするが、各ノードが知らなければならないノード情報は極端に少なくて済む。これは裏を返せばノード数が数万に及ぶ大規模なネットワークにも対応できるという事である。

KVSはノード探索ホップ数が基本的にゼロであるが、個々のノードが他の全てのノード情報を持つ必要があるため、大規模ネットワークには対応できない。逆にDHTは大規模ネットワークにも対応できるが、複数回のノード探索ホップが発生する。Chordの場合、そのホップ数はノード数 n の対数に比例するとされている。

ホップ数 = O(log n)

一般的に、おおよそ数十から数百ノードまでであればKVSを、数千から数十万ノードをカバーするにはDHTが適当であると考えられている。KVSもDHTもノードの識別は一意に定義されたノードIDによって行なわれる。一般的にはノードのMACアドレスやIPアドレスのようにネットワーク上でユニークな文字列をハッシュ化してIDとする。当然の事ながら、このハッシュ化されたIDはノードの物理的な位置情報と持たず、また位置関係も全く反映されていないため、探索に対してノード間位置関係を一切考慮しないという欠点がある。特にDHTの場合、膨大なノードをID空間に対して一様に配置するため、隣接するIDノードが物理的に近いという保障は全く無く、最悪の場合、地球の裏側である可能性もある。

ここで、前述の辞書の背表紙を外し、各アルファベットごとにバラバラに分断してアルファベット毎の小冊子にしてしまおう。そして図4のようにそれぞれの小冊子を3っつの部屋に分散して置く事にしよう。この時、それぞれのつめかけページ番号がどの部屋にあるのかだけは知っているものとする。

ここでAlex君がA冊子のある1号室からTigerを探し始めたとする。DHTによるTiger探索と同じくAlex君はPのつめかけページ番号を得る。そして、そのページ冊子は2号室にある事を知っているので、次に2号室にあるP冊子を見に行く。ついで、P冊子からS冊子が必要である事を知り、3号室のS冊子を調べ、T項目のページがP200である事を得て、1号室に戻って来る。結局T冊子はA冊子と同じ部屋にあったにもかかわらず、たどり着くまでに2号室、3号室と循環しなければならない。次に別のAndrew君がTigerを調べようとした場合、Andrew君はT冊子がA冊子と同じ部屋にあるとは知らないため、Alex君と同じように1号室、2号室、3号室とたどり、最終的に1号室に到達するのである。これは不親切だ。そこで、HIBIKIのLFRTアルゴリズムでは最初にTigerを探索したAlex君は、目的とする冊子が結局同じ部屋にあった場合、後々の人のためにそのTのページ番号をAのつめかけページに追加するのである。

するとAndrew君がAlex君の後にTigerを探索する場合、Tのページ番号はAのつめかけページにあるため、わざわざ2号室と3号室に向かわなくても、同じ部屋にあるT冊子を直接引いてTigerの意味を得る事ができる。

実際の環境ではこの部屋がデータセンタ、もしくはASに相当する。LFRTアルゴリズムを利用すると、一度検索したデータの物理ロケーションがたまたま同じグループ(データセンタやAS)であった場合、そのノード情報を自信の経路情報に追加し、次回以降のアクセスに対して、探索ホップを必要とせず、データセンタ間、もしくはAS間の探索トラフィックを劇的に低減する事が可能となる。

実際、筆者はこのLFRTに出会う事によって、クラウドシステムの利便性を損なうある大きな問題を解決できるアイディアが閃いた。残念ながら今はまだそのアイディアについて詳細をお話する事はできない。しかし、このように技術を知り、理解する事によって、今までに無い全く新しいサービスやITビジネスを生み出す事ができるのである。いや、技術を知らずして新たなビジネスを創生する事は不可能なのだ。

[ライブドア]経営者が抑えておくべきクラウド・コンピューティングの本質
[ライブドア]商流をも変化させるクラウドの底力――変化に耐えうる重要要素とは？

[ライブドア]クラウド時代に必要な技術と人材へ続く