米アマゾンCTOのワーナー・ヴォーゲルス（Werner Vogels）氏は自身のブログのなかで、同社の分散システム「Dyanamo」の技術的概要を明かしている。公開された文書によれば、アマゾンは年末のプレゼントシーズンのピーク時には数千万人の顧客を数万台のサーバでさばいているという。常時、数百万セッションを維持し、たった1日で300万ユーザーが何かを購入する。1つのWebページを表示するのに平均して150程度の関連サービスがSOAベースの分散システム上で呼ばれるが、一定時間以内にページを表示するために、個々のサービスは数百ミリ秒以内にレスポンスを返す仕様になっている。

　この巨大で実用的なシステムを実現するために、アマゾンは長年考察と技術開発投資を続けてきた。同社のストレージサービス「Amazon S3」のベースともなっているというDynamoでは、従来のRDBMSで常識だった「データの完全な一貫性」を保証することよりも「いつでも必ずデータを書き込める」というレスポンスを優先したアプローチを採用している。システム全体でデータの一貫性を完全に保証しようとすると、ある一定以上の規模やパーティションで分けられたネットワークにはスケールしなくなる。代わりに一貫性を少し犠牲にすることで、Dynamoでは可用性を大幅に上げているという。これは、いつでもカートに商品を入れられるようにという同社サービスの特性から来る要請というが、地球規模のクラウド・コンピューティングでは今後広く使われていく手法なのかもしれない。

　ヴォーゲルス氏はDynamoの特徴を「zero-hop DHT」（ホップ数ゼロの分散ハッシュテーブル）とも述べている。DynamoではFreenetやGnutellaのような古いP2Pネットワークと異なり、あらかじめ参加しているピアが分かっている「構造化されたP2P」を使っている。すべてのピアは完全なハッシュデータを持っていて、必要なサービスやデータを提供するピアに対して、他のピアを経由することなくダイレクトにアクセスできる。そのため、実行速度はネットワーク規模に無関係に一定以下に抑えられるのだという。

　こうした高度なアルゴリズムやアイデアは、アカデミズムの世界でも多く議論されているが、実際に稼働しているシステムを持つのがアマゾンの強みだろう。”
http://www.atmarkit.co.jp/news/analysis/200711/26/platform.html

Amazon BASE

基本的な API は memcached プロトコルに以下の２つを追加するイメージです

index-name は sort 済みのデータの固まりを識別するためのものです。

get_sorted(index-name, key1, key2, limit, order) => sorted list of values
put_sorted(index-name, key, value) => undef

1ノードのみのプロトタイプは手元で動いているので、id:viver さんに教えていただいた、Skip Graph の論文を熟読して分散バージョンを開発中です。

””
　では、どうすればいいのか？　MySQL や PostgreSQL を使った RDBMS sharding でも、動的なノード追加（と無停止での負荷の再分散）を実現したい。というのが、今回コードを書き始めた動機でした。それが Pacific です。
””

　分散 KVS が RDBMS sharding に対して優れている要素としては、事前の分割設計が不要で、動的なノード追加（とそれにともなう負荷の再分散）が容易、といった点が挙げられると思います。一方で、Kai や Kumofs のような最近の実装では eventually consistent でこそ無くなってきているものの、ハッシュベースの分散 KVS は、レンジクエリができなかったり (例: 最新５件の日記を表示)、トランザクションがないためアプリケーションプログラムが複雑になったりするという問題を抱えています。

hBaseはBigTableのオープンソースクローンです。Web検索エンジンを開発しているPowerset社のエンジニアが主導して開発しており、Hadoopと同じくJavaで記述されています。hBaseはHadoopに依存しており、実際のデータはHDFS上に安全に保存されます。昔のバージョンのソースコードはHadoopに同梱されていましたが、現在は分かれているので気をつけてください。

　以下にhBaseの情報が掲載されているURLを集めてみました。

• hBaseの公式サイト
• hBaseの公式Wiki
• hBaseのインストール方法
• hBaseのアーキテクチャ&使用方法

　採用実績はこちらをご覧下さい。開発を主導しているYahoo!はもちろんのこと、Facebookでも実際に使用されています。特にログ解析目的での使用が多いようです。

　Hadoopに関する情報は以下の場所から得られます。現在日本語での情報はほとんどありません。

• 公式HP
• 公式Wiki
• インストール方法（1ノード）
• インストール方法（複数ノード）
• Hadoop DFS の目標＆特徴
• Hadoop DFS のアーキテクチャ
• Hadoop MapReduce チュートリアル

1.3 BigTable

　BigTableはGoogle File System上に構成されたスケーラブルな分散データベースです。Google File Systemは巨大なファイルを扱うのに特化されていますが、小さいファイルの大量の読み書きには向いていません。しかしWebページなどの情報を扱うには、構造化された小さいデータに対してデータベース的にアクセスしたいという要求があります。BigTableはそのような要求を満たすために作られた分散データベースです。

　BigTableでは大規模なデータを保存するために、テーブルを複数の行で構成される「タブレット」という単位に分割します。各タブレットは異なるサーバーに分散して配置され、データサイズ増大への対応と負荷分散が可能になります。

　またデータ圧縮を用いてディスクスペースを節約したり、メモリをうまく使うことでデータの参照や挿入を高速に行えたりするのも特徴です。データモデルも行・列で扱う既存のRDBMSとは異なっています。

1.2 MapReduce

　MapReduceは大規模なデータを大量のマシンで並列に処理するための分散計算フレームワークです。ウェブ検索のためのインデックス作成処理や、ログ解析、機械学習などの処理に利用されているようです。

図3 MapReduceの概念図

　MapReduceという名前は処理を「Mapフェーズ」と「Reduceフェーズ」という2段階のフェーズに分割することに由来します。Mapフェーズでは大量の情報を分解し、必要な情報を抜き出して出力します。ReduceフェーズではMapフェーズで抽出された情報を集約し、それに対して計算を行い結果を出力します。MapReduceの入出力はGFSからなされることが多いようです。

　Map、Reduceのそれぞれのフェーズでは他のマシンと通信することがないため、数万台のマシンに効率よくタスクを分配することができ、台数に比例する能力でデータを処理することができます。タスクを分配する際には、データを保持しているノードでそのデータを処理する計算を始める事で、余計なファイルの転送を防ぎます。またマシンが途中で故障して処理が中断した場合も、他のマシンで同じ処理を自動的に始めてくれるなど、耐障害性についても十分考慮されています。

1.1 Google File System

GFS（Google File System）は、大量のデータを大量のマシンで安全に保存するための分散ファイルシステムです。分散ファイルシステムというのは、複数のマシンのディスクを組み合わせて1つのファイルシステムとして見せる技術です。1つのディスクで保存しきれないような大量のデータを効率よく扱う際に非常に有効です。

図2 Google File Systemの概念図

GFSの特徴としては同じファイルを異なるマシンに重複して持たせることで、一部のマシンが故障してもファイルが失われないという点が挙げられます（冗長化）。Googleでは何万台ものサーバーが常時稼動しているので、1日に多くのマシンが壊れます。それに耐えられるような耐故障性の高い分散ファイルシステムを持つことは巨大データを扱う上で必須だったのではないかと思われます。

ただ、この流れは一朝一夕には起こらない。
先日マイクロソフトがクラウド上のデータベースである SQL Data Services の
アーキテクチャ変更を行ったのは、世の中の時間の流れに技術ロードマップを
あわせたためであり、Key Value的な要素を弱め、SQL互換のインタフェースを
より重視した実装となる予定だ。技術の普及には教育、運用、互換性保証などの
エコシステム全体に浸透させなければならない。ゴリ押しに技術で先行しても
疲弊するだけである。それでも世の中をがむしゃらに牽引する陣営がでてくれば
話は別だが、ロジカルには難しい判断だ。