(57)【特許請求の範囲】
【請求項１】
分散型でかつ耐障害性のある態様でデータにカラム指向アクセスするためのコンピュータの実装方法であって、
データが挿入されるデータ・ストアを提供するステップを備え、かつ
前記データ・ストアからデータが、高いレートで、ランダムにまたはシーケンシャルに、次のステップａ）、ｂ）、ｃ）、ｄ）、ｅ）、
ａ）タブレットのキー空間を再帰的に分割することによって、テーブルをタブレットおよびパーティションに累進的に分解するステップであって、
当該テーブルが、可能なキーの特定範囲が各々に割当てられているタブレットを収容し、
各タブレットが、キーのサブ範囲に対するパーティションを収容し、
各パーティションまたはパーティションの部分が、能動的に更新された単一のバケットを有し、
キー・バリューの各サブ・サブ範囲に対して１つのバケットが存在し、そして
バケットが限定されたサイズになると、新規なバケットが割り当てられ、かつ以前のバケットが、流出される、
ステップ、
ｂ）最も高いレベルで、タブレットについての操作を異なるノードに分散させるステップ、
ｃ）より低いレベルで、異なるスレッドを使用して、個々のパーティションまたはパーティションの部分についての操作を扱うステップ、
ｄ）大規模な再構成操作を、個々のパーティションまたはパーティションの部分の操作に分解するステップ、
ｅ）リダイレクション・リンクを使用して、再構成の間にアクセスおよび更新が進行することを可能にするステップであって、タブレット・レベルでの再構成が、サービスの中断無しに達成される、ステップ、
により検索される、
コンピュータの実装方法。
【請求項２】
更に、キー−バリュー・ストアを当該データ・ストアのファイル・システムに密に統合するステップを備え、標準ファイル・システム操作が、キー−バリュー・ストア・テーブルに直接実行される、請求項１に記載の実装方法。
【請求項３】
当該標準ファイル・システム操作が、スナップショットおよびミラーの何れかを備える、請求項２に記載の実装方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明はコンピュータ・ファイル・システムに関する。特に、本願発明は、MapReduceシステムのためのテーブル・フォーマットに関する。
【背景技術】
【０００２】
Apache Hadoop(高可用性分散オブジェクト指向プラットホーム)は、データ集約型分散アプリケーションをサポートするオープンソース・ソフトウェア・フレームワークである。これは、コモディティ・ハードウェアの大きいクラスタに対するアプリケーションの実行をサポートする。Hadoopは、GoogleのMapReduceおよびGoogleファイル・システム(GFS)の論文から導出された。
【０００３】
Hadoopのフレームワークは、アプリケーションに信頼性およびデータ動作を透過的に提供する。Hadoopは、MapReduceというコンピュータのパラダイム（方法）を実装する。このアプリケーションは、多くの小さい作業のフラグメントに分割され、各フラグメントは、クラスタの如何なるノードにも実行させまたは再実行させることができる。加えて、これは、データをコンピュート・ノードにストアする分散ファイル・システムを提供し、これにより、クラスタに渡って非常に高い統合バンド幅が提供される。MapReduceおよびこの分散ファイル・システムは、両者とも、このフレームワークがノード障害を自動的に処理するように、設計されている。これは、アプリケーションが、何千もの計算が独立しているコンピュータおよびペタバイトのデータと共に働くことを可能にする。現在、Apache Hadoopプラットホームは、全体として、Hadoopカーネル、MapReduce、Hadoop分散ファイル・システム(HDFS)、およびApache Hive、Apache HBase、等を含む、数多くの関連したプロジェクトから構成されていると、一般には、考えられている。
【０００４】
Hadoopは、Javaプログラミング言語で書かれていて、かつ世界中の貢献者によって構築されかつ使用されているApacheのトップレベルのプロジェクトである。Hadoopおよびこれに関連したプロジェクト(例えば、Hive、HBase、Zookeeper、等) は、このエコシステムからの多くの貢献者を有する。Javaコードが最も一般的であるが、如何なるプログラム言語も、このシステムの「マップ（map）」部分および「リデュース(reduce)」部分を実装するために、ストリーミングで使用することができる。
【０００５】
HBaseは、GoogleのBigTableをモデルとして作られたオープン・ソースの、非リレーショナル分散型データベースであり、そしてJavaで書かれている。これは、Apacheソフトウエア・ファウンデーション（ASF）のApache Hadoopプロジェクトの一部として開発され、かつHDFS(Hadoop Distributed Filesystem)上で実行され、Hadoopに対しBigTableの様な機能を提供する。すなわち、これは、大量のスパース・データをストアする耐障害の方法を提供する。
【０００６】
HBaseは、圧縮、インメモリ操作、そしてカラム当たりベースのBloomフィルタを特徴とする。HBaseのテーブルは、Hadoopで実行されるMapReduceジョブの入出力として機能することが出来、かつJava APIのみならず、REST、AvroまたはThriftゲートウェイAPIによってもアクセスすることができる。しかしながら、HBaseには欠点がある。例えば、Hbaseテーブルのスナップショットを開くには、回復操作を実行することを必要とし、これは、潜在的にディスク構造の変異を必要とする。Hbaseは、操作と、実行中のファイル・システムとを容易に同期させることができないので、この変異が必要となる。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
このようなシステムの更なる関心は、ライト・アンプリフィケーション(WA:Write Amplification)の懸念である。これは、書き込まれた物理的情報の実際量が、書き込もうとした論理的量の何倍にもなる、フラッシュメモリおよびソリッド・ステート・ドライブ(SSD)に関連した望ましくない現象である。フラッシュメモリは、再書込みが可能となる前に消去されなければならないので、これらの操作を実行するプロセスは、ユーザ・データおよびメタデータを二回以上移動させる(または再書込みする)結果になる。この多重効果は、SSDの寿命に関して必要とされる書込の数を増加させ、これは、SSDが確実に作動する期間を短縮させてしまう。書込みが増加することは、フラッシュメモリに対するバンド幅も消費し、これは、主にSSDへのランダム書込みパフォーマンスを低下させてしまう。多くのファクタが、SSDのライト・アンプリフィケーションに影響を及ぼすが、それらのいくつかはユーザが制御することができるが、いくつかは、SSDへのデータ書込みおよびSSDの使用の直接の結果である。
【０００８】
Googleで書込まれる高速キー・バリュー・ストレッジ・ライブラリであるLevelDBのようなシステムは、ストリング・キーからストリング・バリューまで順序付けられたマッピングを提供する。しかしながら、LevelDBは、ブランチング・ファクタが制限されていてかつ深さが無制限であるので、ライト・アンプリフィケーションは、通常操作では20xに達する可能性がある。上述したHbaseは、細分割の数が固定されていてかつ小さく、そして書込み倍率は小さいが、必要な再構成操作が、非常に大きく、かつこれを並列して処理させることも、細分割させることもできない。このことは、書込みレートおよび更新レートを時には劇的に低下させる結果をもたらす。
【課題を解決するための手段】
【０００９】
MapR DBと呼ばれる本発明の実施態様は、分散型でかつ耐障害性のある態様でデータへのカラム指向アクセスを提供するキー・バリュー・ストアを備える。データはMapR DBに挿入させることが出来、そしてデータは、高いレートでMapR DBから、ランダムにもシーケンシャルにも検索することが出来る。
【００１０】
MapR DBの背後にある一般的なアイデアは、テーブルのキーが順序付けられていてかつテーブル全体がキー範囲に分割されていることである。各キー範囲は、それ自身がキー範囲に分割されているテーブルと呼ばれる構造によって扱われる。タブレットの各範囲は、パーティションと呼ばれる。パーティションも、セグメントに分割されている。
【００１１】
より小さい、かつさらにより小さいキー範囲への再帰的な分割は、いくつかの利点を有する。1つの利点は、並列性である。最上位のレベルでは、タブレットへの操作は、異なるノードに分散させることが出来る。下位レベルでは、異なるスレッドが、個々のセグメントへの操作を扱うことが出来る。加えて、より大きなオブジェクト上の大域ロックを、操作全体に渡って保持する必要が無いように、大規模な再構成操作を、個々のセグメントへの操作に分解することができる。逐次的に分割した複数レベルを有することによって、各セグメントのサイズを相対的に小さく保つことが出来るので、セグメントへの操作を瞬時に行うことが出来る。この結果、MapR DBは、常に、非常に短い時間周期内でリクエストを処理する。MapR DBが、再構成の間に、アクセスおよび更新が進行することを可能にするリダイレクション・リンクを使用するので、タブレット・レベルでの再構成は、サービスに中断を与えることなく行うことも出来る。
【００１２】
MapR DBは、また、MapRファイル・システムに密接に統合される。これを行うことは、特に、MapR DBテーブルに、直接、スナップショットおよびミラーのような、標準ファイル・システム操作を使用する能力を含む、多くの利点を有する。これの1つの利点は、ログをリプレイする必要無しにテーブルを開くことが出来、したがって、読取り専用テーブルを、如何なる回復操作も使用せずに開くことが出来ることである。これに対し、Hbaseテーブルのスナップショットを開くことは、回復操作を実行することを必要とし、これは、潜在的にこのオン・ディスク構造の変更を必要とする。Hbaseは、稼働中のファイル・システムと操作を容易に同期させることが出来ないので、この変更は必要である。これに対し、MapR DBは、稼働中のファイル・システムと操作を同期させることが出来、これが、テーブル・スナップショットが直接使用可能であることの理由である。
【００１３】
このようにテーブルをタブレット、パーティションおよびセグメントに累進的に分解することは、他のログ-構造化データベースでは見出せない特有の利点も有する。先ず、更新操作および次の再構成操作の間にデータ・ブロックをディスクに書込むおよび再書込しなければならない回数は、パフォーマンスを制限する主要なファクタである。ブランチング・ファクタが制限されていてかつ深さが無制限であるLevelDBのようなシステムでは、ライト・アンプリフィケーションは、通常操作の下で20xに達することがある。細分割のレベルの数が固定されていてかつ小さいHbaseのようなシステムに対しては、このライト・アンプリフィケーションは、小さいが、必要な再構成操作は非常に大きく、かつ並列して処理させることも、細分割させることもできない。これは、時折、結果として書込みレートおよび更新レートの劇的な低下をもたらす可能性がある。MapR DBは、テーブルを、累進的に、より小さいタブレット、パーティションおよびセグメントに慎重にかつ不均一に分解することによって、大きなライト・アンプリフィケーションも、長い再構成の遅延も、回避する。
【００１４】
MapR DBは、共通キー−バリュー・データベース操作の上位版も実装する。これは、MapR DBが、スキーマと共にまたはスキーマ無しで作動することと、ネスト状のデータ構造を含むように見えるデータに対しカラム指向のパフォーマンスを提供することを可能にする。異なるアプリケーション・ライブラリは、同じテーブルに異なるインタフェースをエミュレートすることが出来、これはシステム設計に高度な柔軟性を提供する。
【００１５】
MapR DBのキーおよびデータは、それぞれ、速度を最大にするために、常に、メモリ内に生きている、固体ディスクに存在させる、またはハードディスクに存在させるように、設定することができる。この柔軟性により、MapR DBには、カラム・ファミリ当たりのパフォーマンスとコストのトレードオフを調整する能力が与えられる。
【図面の簡単な説明】
【００１６】
【図１】各々が、稼働しているMapR FSまたはMFSプロセスを有する2台のコンピュータまたはノードを示すブロック略図である。
【図２】ローカルMapR DB APIを介してMFSプロセスと同じノードに共起されたクライアント・プロセスが、どのようにして、図1に示されるコンポーネントにアクセスすることが出来るかを示すブロック略図である。
【図３】潜在的に何10または何100テラバイト(TB)のデータを含むテーブルを、どのようにして、各々が最高2、3ギガバイト(GB)までのデータを含む多くのタブレットに分解することが出来るかを示す階層的なダイアグラムである。
【図４】テーブルiノードの詳細な構造を示すブロック略図である。
【図５】タブレットの内部構造を示すブロック略図である。
【図６】リダイレクト・リンクを、どのように、使用して、テーブルのスプリットまたはマージのような長時間にわたる操作の間、２つのタブレットを1つとして機能させるかを示すブロック略図である。
【図７】ミラー化された範囲、コピー・ウィンドウおよび保留状態のコピー領域を使用する交互のコピー・アルゴリズムを示すブロック略図である。
【図８】セグメント・マップの内部構造を示すブロック略図である。
【図９】セグメントの内部構造を示すブロック略図である。
【図１０】ストレッジ・プール・オフセットからフラッシュ・ストレッジへのマッピングを示すブロック略図である。
【図１１】単一のセグメントのジェネレーション1および2のマージを示すブロック略図である。
【図１２】リダイレクト・リンクを使用して、マージまたはスプリットのような実行時間が長い操作の間に、２つのセグメント・マップを実質的にマージするために、セグメント・マップの構造を示すブロック略図である。
【図１３】本願明細書に開示される何れかの方法をマシンに実行させる命令のセットを実行することができるコンピュータ・システムの具体例のマシンを表すブロック略図である。
【発明を実施するための形態】
【００１７】
コンポーネント間の通信
図１は、各々が、稼働しているMapR FSまたはMFSプロセス103, 104を有する２台のコンピュータまたはノード101、102を示す。図１において、MapR DB(MDB)プロセスは、MapRシステムのファイル・システム・スタックの一部である。これは、ローカルAPIを使用してファイル・システムのローカルMapRファイル・サーバ(MFS)コンポーネントと通信する、またはこれは、通常のファイル・クライアントAPIを使用してリモートMFSコンポーネントと通信することが出来る。これによって、MDBコンポーネントが、ローカルMFSコンポーネントと同じプロセスに、または所望の別のプロセスに存在することが可能となる。このMFSを有するMDBコンポーネントを同じプロセスに組み込むことは、より速い通信を可能にし、かつ結果として全体的性能をより高くする。
【００１８】
MFSプロセス103内には、MapR DB 105およびMFSプロパ107を含むいくつかのソフトウェア・コンポーネントが存在する。MapR DBコンポーネント105は、MFSローカルAPI 106を介して標準プロシージャ・コールを使用して、同じプロセス内のMFS 107と通信することが出来る。MapR DB 105は、リモート・プロシージャ・コール(RPC)インタフェース108を介して別のノード102上の別のMFSプロセス104内のMFSコンポーネント109と通信することも出来る。
【００１９】
MFS 107と共にMapR DB 105を単一のプロセス103に直接統合することは、この直接アクセスを有しないデータベースでは利用できない有効なパフォーマンスを可能にする。更に、MFSプロセス103に統合されているRPC 108の使用は、MapR DB 105が、RPC機構108の一部とすることができる如何なるセキュリティ機構も、使用することを可能にする。
【００２０】
図２は、MFSプロセス103と同じノード101で共起されたクライアント・プロセス201が、どのようにしてローカルMapR DB API 202を介して、図１に示されるコンポーネントにアクセスすることが出来るかを示す。図２において、Javaプロセスは、MDB APIを使用してファイル・システムのMDBコンポーネントと通信することが出来る。このJavaプロセスがMDBコンポーネントと同じノードで稼働しつつある場合、共用メモリを使用して、大きいオブジェクトを、直接、かつAPIを使用して可能となるであろう速度より速い速度で転送させることが出来る。
【００２１】
ローカルAPIは、大きいデータ・オブジェクトを、共用メモリ203を介してクライアント・プロセス201からMapR DB 105にパスさせ、その結果、実質的により高いスループットを実現することが可能になる。加えて、異なるノード102で稼働しているクライアント・プロセス204は、節間ネットワーク接続によりリクエストを送信するRPCベースのAPI 205を介して、元のノード101で稼働しているMapR DBコンポーネント105にアクセスすることが出来る。
【００２２】
Infinibandのようないくつかのネットワーク技術は、データが、第一ノード上の第一プロセスのメモリ画像から第二ノード上の第二プロセスのメモリにネットワーク・インタフェース自体によって転送される、いわゆるRDMA転送を可能にする。RDMAインタフェースを使用して、MapR DBクライアント201によって使用される共用メモリ・インタフェース203と同等なものを実装し、同じノード上のMFSプロセス103と通信することが出来る。これは、異なるノード102上のMapR DBクライアント204が、あたかもそれが同じノードにあるかのようにして、可能な限りほとんど同じレートで通信することを可能にする。
【００２３】
テーブルの、テーブル、パーティションおよびセグメントへの再帰的分割
図３において、再帰的分割が、テーブルのキー空間に実行される。テーブルには、可能なキーの特定範囲がそれぞれに割り当てられているタブレットが収容されている。各タブレットには、キーのサブ範囲に対するパーティションが収容されている。各パーティションは、能動的に更新された単一のバケットと多くのセグメント（キー・バリューの各サブ・サブ範囲に対し１バケット）を有する。バケットのサイズが限定されると、新規なバケットが割り当てられ、かつこの以前のバケットは、セグメントに流出される。部分的に流出されたバケットは、それらが完全に流出されるまで作動しているので、この流出の間、サービスのロスはない。
【００２４】
テーブルからタブレットへそしてパーティションからセグメントへの広いファンアウト、および再帰的な分割に単一の層を使用することは、MapR dBのライト・アンプリフィケーションを、データベースの更新当たり約4.5回のディスク書込みに限定する。これは、LevelDBでは更新当たりほぼ20回の書込みとなることとは対照的である。Hbaseの場合、ライト・アンプリフィケーションは低いが、長い圧縮とその結果時折起こる遅延が生じる。
【００２５】
したがって、図３は、何10または何100テラバイト(TB)のデータを潜在的に含むテーブル301を、どのようにして、（それぞれが、最高でも数ギガバイト(GB)のデータを含む）多くのタブレット302に分解することが出来るかを示す。タブレット302の数は、非常に大きく（おそらく何十万またはそれ以上に）することが出来る。このように非常に大きなタブレットの数は、これほど多くのタブレットをサポートすることができないHbaseおよびBig Tableのようなシステムとは異なる。非常に大きな数のタブレットを有することは、非常に大きな圧縮操作に掛かる通常のコストを必要とせずに達成されるMapR DBのライト・アンプリフィケーションが低いことの鍵である。タブレットは、潜在的に非常に大きいクラスタに渡って、または多重クラスタに渡って、分散させることが出来る。各タブレットは、図１および２に示されたいくつかのノードで稼働しているMFSプロセスによって扱われる。タブレットに対する全ての操作が、（MapR FSプロセスのネイティブ・コンポーネントである）MapR DBコンポーネントにより処理されるので、領域サーバまたはタブレット・サーバのような別個のプロセスは、不必要である。
【００２６】
タブレットは、いくつかのパーティション303に分割される。代表例として、タブレットのパーティションの数は、（この数は、増加させることも減少させることも出来るが）1タブレットにつき16〜20の範囲にある。パーティションのサイズは、数百メガバイト(MB)から1ギガバイト程度までに限定される。
【００２７】
各パーティションは、少数のバケット304および非常に大きな数のセグメント305を有する。データベースへの更新は、最初、バケットがおよそ32MBのサイズに至るまで、パーティションに対し現在作動中のバケットに、書込まれる。このポイントで、新規なバケットが割り当てられ、そしてこのシステムは、処理が続くに連れ、バックグラウンド内のさまざまなセグメントにバケットのコンテンツを分散させる。書込みロードが大きい間には、いくつかのバケットは、一度、セグメントに流出させることが出来る。各バケットのデータは、メモリ内のテーブルにも収容されているので、最近書き込まれたデータの読出しは、非常に瞬時に満足させることが出来る。
【００２８】
パーティション当たり潜在的には数千以上の多数のセグメントを、存在させることが出来る。各セグメントは、典型的には、約1MBのサイズに限定されているので、それは、ほぼ1回のディスク回転で読出しまたは書込みを行うことが出来る。より小さいセグメントであっても、読出しまたは書込みを行うためにディスク回転を必要とするが、より大きなセグメントは、読出しまたは書込みを行うために、複数の回転を必要とする。これは、およそ1MBのサイズを最適な中央値とする。
【００２９】
テーブルiノード構造の詳細
図４は、テーブルiノードの詳細な構造を示す。図４において、リンクは、テーブルiノード構造内のタブレット・マップからキー範囲に基づくタブレットに、張られている。このテーブルを定義するiノードは、カラム・スキーマ・データ、アクセス制御情報、およびこのテーブルに対して既に登録されているコプロセッサに関する情報を含む様々なメタデータを収容する。加えて、キー範囲を特定のテーブルに関係付けるマップがある。このタブレット・マップは、各タブレットに対して1つのキー・バリューを有する。キーの範囲は、タブレット・マップのこのキーの出発点（これは含まれる）からこのテーブル・マップの次のキーの終点（これは含まれない）までである。この最後のタブレットに対するキーのセットは、下限しか有さない。
【００３０】
図４に示されるように、このテーブルは、iノードの特別なタイプとしてストアされているので、これは、MapR FSによって提供されるキー・バリュー・ツリーにロバストのアトミック操作を使用することができる。図４には、図３からのテーブルiノード301が、カラム・ファミリ定義401、アクセス制御定義402、登録されたコプロセッサ403およびタブレット・マップ404を収容していることが、示されている。カラム・ファミリ定義401は、テーブルに対して定義されているカラム・ファミリを記述する。これらのカラム・ファミリ定義は、データが、どのようにして最終的にこのテーブルの下位レベル部分のセグメントにストアされるかを決定する。アクセス制御定義402は、さまざまなユーザおよびグループのメンバーにとって、どの操作が可能であるかを決定する。
【００３１】
本発明の一実施形態では、タブレット・マップ404は、MapR FS内にネイティブb-ツリーとして実装される。このキーをタブレット・マップで探索することによって、リクエストが、それらが参照するキーに従って、送られる。この探索操作により、このキー空間は、各々が下限（含む）から上限（含まない）までの範囲を有するハーフ・オープンのキー範囲405、406にスプリットされる。最後の範囲407は、下限しか有さない。バリューが挿入されるので、このタブレット・マップにおいて最も低いキーより低いキーを有するそれらのバリューが、最も低いバリューを更新するために用いられ、その結果このタブレット・マップにおいて最も低いバリューは、常に、この全体のテーブルにおける最も小さいキーに等しいかそれより小さくなる。タブレットへのポインタは、コンテナIDおよびiノード番号を収容しかつ標準のMapR FS操作を使用して導出される通常のiノード参照である。
【００３２】
タブレットiノード構造の詳細
図５は、タブレットの内部構造501を示す。図５において、タブレット構造は、バケットおよびセグメント・マップへのパーティション・マップ・リンクによって示される。各セグメント・マップは図示されるように多くのセグメントを収容しているので、このパーティション・マップの１つのパーティションは、１つの作動中のバケットと多くのセグメントから構成される。前に作動していたバケットは、このパーティションに関連するセグメントに流出されつつある間、保持されている。
【００３３】
この構造は、特別なiノードとしてMapR FS内にストアされる。このタブレットiノードのキー部分は、図４からのタブレット・マップ404がテーブル全体に対しこのキー空間を分割したのと類似した方法で、タブレットに対しこのキー範囲を分割するb-ツリー・マップである。キー範囲ごとに、１つ以上のバケット503、504（その１つはこのパーティションに対する現在のバケットである）への参照がある。他のキー範囲は、それら自身のバケット505、506を有する。
【００３４】
各キー範囲は、セグメント・マップ507、508、509への参照も有する。このパーティションの最後のキーに対するキー範囲は数式上限定されていないが、最後のバケット506および最後のセグメント・マップ509に関連したキーは、（図４において、テーブルiノード構造のタブレット・マップ404に定義されているように）タブレット501自体のキー範囲によって、通常、実際に、限定されている。
【００３５】
このタブレットは、それがテーブル・レベルから受信する操作を、正しいパーティションに送る。このポイントで、このセグメント・マップは、更に、どの処理が行われるかを定義するために用いられる。
【００３６】
図６は、リダイレクト・リンクをどのように用いて、２つのタブレットが、長時間にわたる操作(例えば、テーブルのスプリットまたはマージ)の間、1つのタブレットとして機能することが可能になるかを示す。図６では、リダイレクト・ポインタを使用して、パーティション・マップをスプリットまたはマージさせることができるタブレット構造が、示されている。図６は、進行中のスプリットを示す。このポイントで、リダイレクト・ポインタは既に確立されていて、新規なタブレット構造が既に作成されていて、そして２つのパーティション(n-1およびn)が、既に元のタブレット構造から新しいものにコピーされている。それにもかかわらず、すでに移動しているパーティションによってカバーされている範囲内のキーに対する元のテーブル内の検索は、元のタブレットから新しいタブレットへのリダイレクト・ポインタをフォローすることによって、依然として、発見することが出来る。
【００３７】
したがって、図６では、タブレット501、パーティション・マップ502、バケット503、504、505および関連するセグメント・マップ507、508は、図５に示されるものと同じである。しかしながら、バケット506およびセグメント・マップ509への参照は、新規なタブレットiノード601に既に移動されている。タブレットiノード601は、最終的に、元のテーブル501によって扱われるキー空間の最後の半分からの項目を収容する。バケットおよびセグメント・マップのいくつかの組合せが、どのように移動されたかまたは移動されていないかを説明するために、図５から明確性のため省略されていた付加されるバケット603及び604並びに関連するセグメント・マップ605、606が、図６には、示されている。
【００３８】
このようにバケットおよびセグメント・マップを新規なタブレット601にコピーすることは、新規なタブレットが完全に別のコンテナに置かれるので、単にポインタを調整するように単純ではない。タブレットiノードに対しこのバケットおよびセグメント・マップをローカルに保つためには、セグメント・マップのコンテンツを、実際に、この新規なタブレットiノードが位置するコンテナにコピーすることが望ましい。バケットのコンテンツをコピーすることは、新規なバケットをこの新規なコンテナに割り当て、かつ次いでこのセグメント・マップをコピーした後にそれらのセグメントへの古いバケットをフラッシュすることによって、回避することが出来る。  
【００３９】
このスプリット・プロセスの間、リダイレクト・リンクは、多重機能を果たす。先ず、これらは、マージまたはスプリットが進行中であることを示すインジケータを提供する。第二の機能は、２つのタブレットiノードがスプリットの間、1つのノードとして機能することを可能にし、その結果全ての操作が、スプリットが進行中であるという示度なしに進行することである。
【００４０】
タブレットのマージは、逆の場合を除き、同じ機構によって処理させることが出来る。この場合、バケットは、このマージで生き残るタブレットに割り当てられ、そしてセグメント・マップは、この生き残っているタブレットにコピーされる。このリダイレクト・ポインタは、基本的に、スプリットの間、同じ目的を果たす。つまり、これらは、このマージ操作の間、この２つのタブレットを1つのタブレットとみなす。このマージが行われると、このリダイレクト・リンクは除去することが可能となり、かつ生き残っているタブレットは、２つのタブレットの完全なマージとなっている。
【００４１】
テーブルの最初または最後でこのタブレットのスプリットを特別に扱うことは、キーをシーケンシャルに挿入するロードの下でパフォーマンスを容易にすることが出来る。通常、タブレットに対するキー空間は、結果として生じるタブレットがほぼ同じ量のデータを有するように、スプリットされる。しかしながら、このテーブルの何れかの端でタブレットをスプリットするときには、このタブレットを、データの大部分が２つの内の内側のタブレットに保持されように、スプリットすることは有利である。ランダムな挿入ロードに対しては、これは、しばしば、このキー範囲の各最後でタブレットを、理想的であるより少なくスプリットさせ、そしてしばしば、この端に隣接したタブレットを最適であるよりわずかに多くスプリットさせることになるが、テーブルが成長するにつれて、これらのエッジ効果は無視できるようになる。
【００４２】
しかしながら、シーケンシャルに上昇するまたは下降する挿入ロードに対し、端タブレットのアンバランスなスプリッティングは、タブレット・スプリッティングの率を10x以上低下させることによって、パフォーマンスを大幅に向上させることが出来る。データは頻繁にはコピーされないので、低下させたタブレット・スプリッティングは、システム全体のライト・アンプリフィケーションを減少させることになる。
【００４３】
代替タブレット・スプリッティング・アルゴリズム
タブレット・スプリッティングは、リダイレクト・ポインタなしで、別の方法で実装させることも出来る。この代替タブレット・スプリット・アルゴリズムでは、累進的なコピーは、新規なコピーにミラー化されつつある増大するソース・タブレットによってなされる。図７は、ミラー化されている範囲712、コピー・ウィンドウ713およびペンディング・コピー領域714を使用する代替コピー・アルゴリズムを示す。このミラー化された範囲において、元のタブレット501への更新は、パーティション・マップ716を有する新規なタブレット・コピー715にミラー化される。コピー・ウィンドウでは、コピーが進行する間、更新は制止されている。このコピーが完了したあと、このコピー・ウィンドウ領域は、ミラー化された範囲に追加され、そしてこの更新は、ミラー化された態様で続行する。このペンディング・コピーでは、元のタブレット501への更新は、新規なコピーにミラー化されない。
【００４４】
このコピー操作の間、元のタブレット・キー範囲は、図７に示されるように4つの範囲に分割される。第一部分は、元のタブレットに残存するキーから構成されていて、かつコピーされない範囲と呼ばれる。コピーされるこれらのキーは、3つの部分に分割される。これらは、すでにコピーされているそれらのキーを含む。これらは、ミラー化された範囲と呼ばれる。別の部分は、コピー・ウィンドウとして知られているキーの小さい範囲から構成される。これらのキーは、現在コピーされつつあるキーである。最後の部分は、カーソル範囲の後のキーに関連するデータから構成されていて、かつペンディング範囲と呼ばれる。
【００４５】
コピーされていない範囲のキーに対しては、全ての更新は、このタブレットの元のバージョンのみに適用される。ミラー化された範囲のキーには、元のタブレットが受信した全ての更新が、新しいタブレット・コピーに転送され、両方の更新が適用された後のみに承認が返される。コピー・ウィンドウのキーに対して、このコピー・ウィンドウのキーおよびデータがコピーされる間、全ての更新は阻止される。ウィンドウが、ペンディング範囲から新規なセットのキーに移動すると即座に、この更新は、解除され、そして通常通りに扱われる。これらの更新が解除されると、以前コピー・ウィンドウ内にあったこれらのキーは、今や、ミラー化された範囲にあるので、これらの更新は、元のコピーと新規なコピーの両方に適用されている。ペンディング範囲では、全ての更新は、元のコピーに適用されるだけである。
【００４６】
このコピーの間、全ての新しいデータ・オブジェクトは、MapR FSオーファネッジにおいて作成される。このコピーが終了すると、新規なタブレットへの参照が、このタブレット・マップに入れられる。このコピーの間の失敗により、この参照が挿入されない場合、オーファネッジ・メカニズムは、新しく作成されたオブジェクトへの全ての参照を直ちに除去する。これは、更新遅延が非常に短いタブレット・コピーおよびタブレット・マップへの明らかにアトミックな更新を作成する効果を有する。失敗が生じると、このテーブル構造への見える変化はなされず、そして全ての懸垂データ・オブジェクトは、透過的に、取り除かれる。
【００４７】
論理的に述べると、スプリットの間にタブレットのコンテンツの部分をコピーすることは、いくつかの方法で進めることができる。コピーすることは、最初または最後の何れかから開始することができ、かつ反対の端の方に進むことができる。コピーすることは、中央のあるポイントで開始しかついずれの端の方に進めることも出来る。
【００４８】
コピーすることをタブレットの中央で開始する場合、このコピー操作は完了させるかまたは完全に放棄させなければならない。従って、コピーは何れかの端から開始することが好ましい。前述したように、それらが、このテーブルの最初にあるか最後にあるかに従って、または更新のパターンのような他のファクタに基づいて、このスプリットの後のタブレットのサイズが等しくないように、このコピーの出発点を、設定することが出来る。
【００４９】
いずれの端から開始するコピーも、作業を失わずにいつでも終了させることが出来る。そして任意の数のファクタに基づいてこのコピーを終了することを選択することは、有益である。コピーすべきものには、最小または最大画分があるとすることができる。コピーするのを止めることを決める別の方法は、タブレットのコピーされた部分に適用されつつあるトランザクションの平均数が、臨界量に至るまで、コピーすることかもしれない。新規なコピーに行くトランザクションの数が、コピーする最大量(例えば、タブレットの90%)の制限と結合された古いコピーに行くトランザクションの数を超えるまで、コピーすると言う結合された戦略は、以前に記述した非対称スプリットを実装する一方法である。
【００５０】
セグメント・マップ構造の詳細
図８は、セグメント・マップの内部構造を示す。図８では、各セグメント・マップは、多くのセグメントを参照する。ハーフ・オープンのキー範囲は、各セグメントが含むエントリを定義する。テーブルおよびタブレットと同様に、MapR FS b-ツリーも、セグメント・マップ701自体を定義するように機能する。このセグメント・マップは、このセグメント・マップに対するキー範囲を、702および703のようなセグメントに対しハーフ・オープンの範囲に分割するために使用される。このセグメント・マップの最後のキーは、最後のセグメント704のための半分が制限されていないキー範囲を定義する。
【００５１】
セグメント構造の詳細
図９は、セグメントの内部構造を示す。図９では、一群のセグメントに対するバケットが一杯になるたびに、コンテンツは、ソートされ、かつ新ジェネレーションを形成するためにこれらのセグメントにコピーされる。時間とともに、ジェネレーションは、マージされる。セグメントが大き過ぎる場合、それはスプリットすることが出来る。セグメントをスプリットすることによりセグメント・マップが大き過ぎるものになる場合、以前に示したように、そのセグメント・マップは、スプリットさせることが出来る。
【００５２】
セグメント・マップをスプリットすることは、パーティション・マップのパーティションの数を増加させる。これは、このパーティション・マップを所望のものより大きくさせ、これにより、このパーティション・マップを含むタブレットのスプリットがトリガされる可能性がある。スプリットすることは、実際には、いくつかのジェネレーションを圧縮することによって行われる。圧縮の後、古いジェネレーションは、全ての係属中の操作が完了することを可能にするために、数十秒間保持される。
【００５３】
この圧縮の始めに、全ての書込みは、新しく圧縮されたジェネレーションの作動中のバケットにリダイレクトされるので、このペンディング操作のみ（これは、当然、短時間で成功または失敗する）を読出すことが出来る。
【００５４】
全てのジェネレーションを有する各セグメントは、スピル・マップ（spillmap）として知られている特別なiノードに収容されている。特別なiノードの使用は、アトミック性および失敗許容度特性が、MapRファイル・システムの容器構造から継承されることを可能にする。
【００５５】
したがって、パーティションのバケットが一杯になるたびに、新規なバケットが割当てられ、そしてこのバケットのコンテンツは、パーティションのセグメントの全てに流出される。このセグメントレベルで、これは、ジェネレーションとして知られている相関する一連のファイルを書込むことによって、行われる。このジェネレーションは、ジェネレーション・マップ・ファイル802、カラム・ファミリ・ファイル803、804、805およびBloomフィルタへの参照を収容するジェネレーション・ディスクリプタ801から構成される。このジェネレーション・マップ・ファイルは、カラム・ファミリ・ファイルのオフセットへのキーおよび参照を収容するマップを意味する。カラム・ファミリ・ファイル803、804、805は、タイムスタンプおよびキー・バリュー対のセットを有するデータエントリを収容する。このタイムスタンプは、必要に応じて、以前のデータ・バリューを保持することを可能にする。非常に大きなキーに対しては、実際のキー・バリューは、別々のファイルにストアされる。このテーブルの行が削除されると、特別なエントリがこのジェネレーション・マップに入れられ、タイムスタンプと共に削除することを表示する。
【００５６】
セグメント内の各ジェネレーションは、並列構造を有する。ジェネレーションは、結合させて、テーブル内のデート・バリューを除去することが出来る。全ての更新が、セグメントが見出されるパーティションに対するバケットに向けられるので、ジェネレーションの結合は、如何なる一つのセグメントに対しても1つの結合しか一度に行われない限り、ジェネレーションの更新については気にすることなく、実行することが出来る。この結合が完了すると、セグメント・マップは、アトミックに更新される。
【００５７】
このジェネレーション・マップおよび各カラム・ファミリが、最終的にMapR FS内に独立したファイル様オブジェクトとしてストアされるので、各々は、それらがメモリ内、固体ディスク(SSD)、または通常のディスクに保持されているかに応じて、別々に、制御させることが出来る。これは、このキーおよび各カラム・ファミリには、それぞれ、パフォーマンスを最適化するために、この点に関して独立処理を与えることが出来ることを意味する。
【００５８】
特別なKV-ストア操作
ファイルの改名は、ディレクトリ内のアトミック挿入および削除により構成させることが出来る。これを一般化させると、一度に、アトミックの態様でKV-ストア内における複数のファイルの作成、改名または除去が可能になる。既存ファイルを作成しかつ置換することが必要な場所、または複数のファイルを共に(または、例えば、カラム・ファイルのように共にではなく)作成しなければならない場所のように、複数の場所が存在するので、これは重要である。
【００５９】
ファイルは、リンクされていない状態で作成することが出来る。これらのファイルを書込む操作が失敗すると、これらは消滅する。この書込みが行われるときには、これらのファイルは、リンクされた状態にアトミックに更新されなければならず、かつバケット・ファイルの削除はアトミックでなければならない。
【００６０】
圧縮において、複数のジェネレーションは、共に扱い、かつ圧縮されたバージョンとアトミックに置換させることが出来る。この圧縮されたバージョンは、多くのファイルから構成され、そして古いバージョンは、多くのファイルを含むが、何時でも、１セットまたはその他のセットのみが存在しなければならない。この新規なファイルは、リンクされていない状態で作成され、そして現在生きている全てのファイルに対してアトミックにスワップされる。クラッシュまたはハングにおいて、このオーファネッジ・メカニズムは、ペンディング・ファイルの削除を扱う。これと同じ一般的な機構は、このツリーのより高いレベルにも適用することが出来る。
【００６１】
スナップショットおよび配置
テーブルは、ボリューム内にあるので、自由にスナップさせることが出来る。複数のテーブルを、ボリューム内に置き、一緒にスナップさせることも出来る。これにより、全てのデータ配置ポリシが、特に第一のコピーがローカルである場合を含めて、ボリュームをクラスタの部分にピン留めする能力に適用される。
【００６２】
非常に大きなキー
Bツリーは、最適で、かつ相対的に大きい、分岐ファクタを必要とする。極めて大きなキーは、これを満足しない。MapRでは、非常に大きなキーは、大きなキー・ファイル内に一緒にストアされる。このb-ツリーにストアされるものは、キーのオフセットである;このFIDは、既知である。8-バイトオフセットは、このキーの代役を務めることが出来る。
【００６３】
これは、２つのファクタにより、受け入れることができる。
【００６４】
第一に、このキーの最初の100バイト程度は、b-ツリーに直接ストアされていることから、これは、隣接するキーの違いがこのプレフィックスにおいて共通するので、多くの比較作業を可能にする。
【００６５】
第二に、大きなキーを比較することは、完全なキーに対してリンクをフォローすることに比較して、十分、価値がある。これは、短いキーと長いキーを同じb-ツリー内で混合することを可能にする。いくつかの限定された状況では、キーは、ソートされた順序でキー・ファイルに追加されているので、キー・ファイル内のオフセットは、確実にキーを順序付けるために使用することが出来る。
【００６６】
回避されるリードおよびライト・アンプリフィケーション
本発明の実施態様では、ライト・アンプリフィケーションを回避することが、当然であるとは限らない。特に、Hbaseでは、リード・アンプリフィケーションを回避することは困難である。全てのレベルでBloomフィルタを使用することは、リードおよびライト・アンプリフィケーションの両方を回避する。
【００６７】
固体ディスク上のデータ・ストレッジ
本願明細書において記述される本発明の実施態様は、固体ステート・ディスク(SSD)にデータ・ブロックをストアして、パフォーマンスを最適化することが出来る。他のシステムでは、通常、電力損失の後での高いパフォーマンスとデータのアクセス可能性との間でなさねばならぬ選択がある。高性能システムは、通常、ディスクブロックに対するキャッシュとして使用され、かつ所望のディスク・ブロックアドレスをSSDブロックアドレスに変換するインメモリマップに依存する。しかしながら、このインメモリマップは、大きいので、このマップをSSDデバイスに書込むことは、通常、実行不可能である。電源が失われると、インメモリデータ構造も失われ、このマップも失われる。  
【００６８】
これらのシステムに関する別の問題は、SSDが大きい場合、このインメモリ構造が非常に大きくなるということである。これは、結果的に、ページアドレス変換マップだけでメモリを過剰に使用することになる。この大きなインメモリマップを保持することの主要な代替例は、このマップをSSD自体に保持させることである。これは、通常、ブロックを発見するためにSSDへの数多くのアクセスを必要とし、これは、パフォーマンスが悪い結果をもたらす。
【００６９】
図１０において、ストレッジ・プール・オフセットからフラッシュ・ストレッジへのマッピングは、いくつかの機構によって行われる。各ページがフラッシュ・ストレッジに書込まれるとき、そのページに対するストレッジ・プール・オフセットが、ページマップ・ログと呼ばれるフラッシュの別の部分にも記録される。各ページは、このログ内に、対応するエントリを有するので、このページに対して外的に知られている参照しか、このログに書込む必要がない。最近書き込まれたページマッピングは、生きているページマップとして知られているメモリ内のハッシュ・テーブルにもストアされている。
【００７０】
この生きているページマップが特定の臨界サイズに到達すると、生きている新しいページマップが開始され、そしてしばらく後に、この生きている古いページマップは、スペースを確保するためにBloomフィルタに変換される。このページマップ・ログは、750のサイズ減少に対し、８Kページ当たり約12バイトを取る。この生きているページマップは、エントリ当たりほぼ1.5 *(12 + 6)バイトを占め、そして各Bloomフィルタは1マップエントリにつき約1バイトを占める。したがって、1TBのページ・ストアは、1.3GBのページマップ・ログを必要とする。生きているページマップが40MBに限定されている場合、それらは、フラッシュ・ドライブの総量130,000,000ページから1,500,000以上のエントリを保持する。各Bloomフィルタが、1.5MBを必要とするので、フラッシュ・ドライブ全体のシノプシスは、いくつかのページマップおよび残りの各々に対するBloomフィルタに対し約250MB(MB)未満の主メモリしか必要とされない。
【００７１】
特に、このインメモリ・ディレクトリは、ページマップ・ログを走査することによって、パワーアップして再構成させることが出来る。この走査は、数秒しかかからない。
1TB = 134,000,000ページ
40MBハッシュ・テーブル = 1,500,000ページ
134,000,000ページ = 89テーブルまたはBloomフィルタ
1.5MB = Bloomフィルタ
3 × ハッシュ・テーブル + 90 Bloomフィルタ = 120MB + 135MB = 255MB
【００７２】
したがって、本願明細書において記述される本発明の実施態様では、SSDストレッジは、２つの領域に分割される。これらの領域は、図１０においてページマップ・ログ901およびページブロック・ストレッジ902として示されている。ページマップ・ログ内には、このページブロック・ストレッジにおける各ページに対して、1つのエントリが存在する。このページマップ・ログ内のエントリは、ブロックアドレスの形態で書込まれつつあるブロックの元のアドレスを収容する。このブロックアドレスは、12バイトのサイズしかなく、これは8Kのブロックサイズよりはるかに小さい。
【００７３】
ブロックがページブロック・ストレッジ902に書込まれ、そしてそれらのアドレスがページマップ・ログ901に書込まれるので、アドレスからSSD内の位置へのマッピングは、生きているページマップ903として知られているインメモリテーブルにも、記録される。この生きているページマップ内にエントリを有するブロックに対し、SSD上のブロックの位置は、生きているページマップの単純なルックアップによって、このブロックのディスク・アドレスから決定させることが出来る。この生きているページマップが特定の最小サイズを超えると、このテーブルに対するキーであるアドレスが、ページBloomフィルタ904に記録される。このテーブル自体は、最終的に廃棄されるので、多くても数個の生きているページマップしか、メモリ内に完全に保たれることはない。
【００７４】
このSSD内のブロックへの大部分のアクセスは、まだ生きているページマップで発見することが出来る相対的に最近書き込まれたブロックに対するものである。他のブロックは、関心のあるアドレスを含むと思われるフィルタが発見されるまで、新しいものから古い順に各ページBloomフィルタをチェックすることによって、発見することが出来る。このBloomフィルタに対応するページマップ・ログの部分は、メモリに読込まれそして生きているページマップに再構成される。
【００７５】
このログ内の各エントリの位置は、12によって除算しかつこのブロックサイズを乗算することによって、SSDアドレスに変換させることが出来るので、これは、容易に行うことが出来る。このページマップ・ログは、750のサイズ減少に対し、8Kページ当たり約12バイトをとる。この生きているページマップは、エントリ当たりほぼ1.5 *(12 + 6)バイトを占め、そして各Bloomフィルタは、1マップエントリにつき約1バイトを占める。したがって、1TBのページ・ストアは、1.3GBのページマップ・ログを必要とする。生きているページマップが40MBに限定されている場合、それらは、フラッシュ・ドライブの総量130,000,000ページの1,500,000以上のエントリを保持する。各Bloomフィルタが1.5MBを必要とするので、フラッシュ・ドライブ全体のシノプシスは、いくつかのページマップおよび残りの各々のためのBloomフィルタに対して約250MB未満の主メモリしか必要とされない。
【００７６】
特に、生きているページマップのインメモリ・ディレクトリおよびBloomフィルタは、ページマップ・ログを走査することによって、パワーアップに再構成させることが出来る。この走査は、数秒しかかからない。SSD全体がブロックでほとんど満たされると、システムは、それらが保持されるべきであるか否かを見るために、このSSDの最初からブロックをチェックし始める。ファイル・システムによって既に上書きされたまたは廃棄されているブロックは、保持する必要はない。
【００７７】
また、これらのブロックが属するファイルのポリシにも依存しているので、回転するディスク上にブロックのコピーを保持することは、受け入れることができる。SSDを実質的に満たすためにはかなりの時間がかかるので、このようなブロックを回転するディスクに並列書込みすることは、このシステムがこのブロックの周辺に戻る時間後に完了するので、長い時間を要するであろう。保持する必要のないブロックは、全て、スキップさせることが出来る。残りの保持しなければならないブロックは、SSDの終端にコピーさせることが出来、これにより、SSDの第一セクションの使用が解放される。このプロセスは、新規な書込みのためのスペースを設けるために、保持されている古いブロックを連続的にコピーして、周期的に継続させることが出来る。
【００７８】
保持する必要があるブロックのみをコピーするこのパターンは、SSDが最初に一杯になるポイントから行われ、かつこのポイントから前方に継続する。MapRシステムにおけるSSDの主な目的が、キャッシュを介した書込みであるので、ほとんど全てのブロックは保持する必要はない。代替実装では、他の例ではコピーされたであろうブロックを、その場所に残しかつあたかも最近書込まれたかのように扱うことが出来る。高い保存率を有するほとんど満たされているSSD'sに対しては、コピーすることは、高オーバーヘッドを課すが、ほとんど不必要な古いページが、生きているページマップを満たしていないことを確かめる利点を奏する。
【００７９】
転送ポインタ
図１１は、単一セグメントのジェネレーション1および2のマージを示す。図１１において、セグメントのマージまたはスプリットの間、リダイレクト・ポインタ110、112が、２つのセグメントを実質的にマージするために使用されるので、一方へのアクセスは、他方のコンテンツも考察する。したがって、このリダイレクト・ポインタは、それが第二セグメントで発見されることを可能にするので、ジェネレーション2セグメント内でk7を探索することが、成功する結果となる。リダイレクト・ポインタは、アトミック操作を用いてセットされ、そしてセグメント・スプリットのような大きなスケール操作が一連の小さいステップとして安全に行われることを可能にする。
【００８０】
図１２は、リダイレクト・リンクを用いて、マージまたはスプリットのような実行時間が長い操作の間に、２つのセグメント・マップを実質的にマージすることができる、セグメント・マップの構造を示す。セグメント・マップが、定義された数のセグメントより多くのものを有するようになったときに、スプリットは発生する。セグメントをスプリットさせることは、パーティション内のセグメントの数を増加させる。これは、このパーティションが、パーティションのスプリットをトリガするであろう所望の数のセグメントより大きいセグメントを有すると言う結果をもたらすことを可能にするであろう。パーティションのスプリッティングは、同様に、タブレットのスプリットと言う結果をもたらすことも可能にするであろう。リダイレクト・ポインタ120、122を、これらのレベルの各々で使用して、これらのスプリットを、通常の操作を止めずに、一連の小さい操作として行うことも可能である。
【００８１】
コンピュータの実装
図１３は、マシンに本願明細書で開示した方法の何れか実行させる命令のセットを実施させることができるコンピュータ・システム1600の典型的な具体例における、マシンを表すブロック略図である。代替実施態様では、このマシンは、ネットワーク・ルータ、ネットワーク交換機、ネットワーク・ブリッジ、パーソナル携帯情報機器(PDA)、セルラ電話、ウェブ機器、または取るべきアクションを特定する一連の命令を実行するまたは送信することができる如何なるマシンも備えまたは含むことができる。
【００８２】
コンピュータ・システム1600は、バス1608を介して互いに通信する、プロセッサ1602、主メモリ1604およびスタティックメモリ1606を含む。コンピュータ・システム1600は、ディスプレイ・ユニット1610(例えば、液晶式表示装置(LCD))を更に含むことができる。このコンピュータ・システムは、英数字入力装置1612(例えば、キーボード)、カーソル制御デバイス1614(例えば、マウス)、ディスク駆動ユニット1616、信号生成デバイス1618（例えば、スピーカ）およびネットワーク・インターフェース・デバイス1628を含む。
【００８３】
ディスク駆動ユニット1616は、実行命令のセット、すなわち、以下に記述される方法の何れか１つまたは全てを実施するソフトウェア1626が、ストアされている機械読取り可能な媒体1624を含む。このソフトウェア1626が、完全にまたは少なくとも部分的に、主メモリ1604の範囲内および／またはプロセッサ1602の範囲内にあることも示されている。ソフトウェア1626は、更に、ネットワーク・インターフェース・デバイス1628によってネットワーク1630を通じて送信または受信させることができる。
【００８４】
上述したシステムに対して、異なる実施態様は、処理エンティティを実装するために、コンピュータが実行する命令の代わりに論理回路を使用する。速度、経費、工具費、等の分野におけるアプリケーションの特別な要請に基づいて、この論理回路は、特定用途向け集積回路(ASIC)を構築することによって、実装させることができる。このようなASICは、CMOS(相補型MOS)、TTL(トランジスタ・トランジスタ論理回路)、VLSI(非常に大きなシステム統合化)または別の適切な構造によって実装させることができる。他の変形例は、デジタル信号処理チップ(DSP)、(抵抗器、コンデンサ、ダイオード、誘導子およびトランジスタのような)個別回路、フィールド・プログラマブル・ゲート・アレイ(FPGA)、プログラム可能論理列(PLA)、プログラマブル・ロジック・デバイス(PLD)、等を含む。
【００８５】
コンピュータのCPUのような処理コアのいくつかの形で実行される、またはマシンまたはコンピュータ可読媒体またはそれの範囲内で実装しまたは実現される、ソフトウェア・プログラムまたはソフトウェア・モジュールとして、またはそれらをサポートするものとして、実施態様が、使用することができることは理解されるべきである。機械読取り可能な媒体は、マシン(例えば、コンピュータ) によって読み込み可能な形で、情報を格納または伝送するための如何なる機構も含む。例えば、機械可読媒体は、リード・オンリー・メモリ(ROM)、ランダム・アクセス・メモリ(RAM)、磁気ディスク格納媒体、光ストレッジ媒体、フラッシュ・メモリ・デバイス、伝達された信号の電気、光、音響等の形(例えば、搬送波、赤外線信号、デジタル信号等)、または情報を格納または伝送するのに適している他のタイプの如何なる媒体も、含む。
【００８６】
本発明が、好ましい実施例を参照して本願明細書において記述されているが、他のアプリケーションを、本発明の精神と範囲から逸脱することなく本願明細書において記載されるものと、置換することができることを、当業者は、直ちに理解するであろう。したがって、本発明は、以下に含まれる特許請求の範囲によってしか限定されるべきではない。
【００８７】
（関連出願についてのクロス・リファレンス）
本出願は、2013年9月16日に出願された米国特許出願、シリアル番号第14/028427号、および2012年9月18日に出願された、米国仮特許出願、シリアル番号第61/702,683号の優先権を主張する。そして、これらの出願は、それぞれ、全体が参照によって本願明細書に組み込まれている。
【図１】
0006046260.tif 000002
【図２】
0006046260.tif 000003
【図３】
0006046260.tif 000004
【図４】
0006046260.tif 000005
【図５】
0006046260.tif 000006
【図６】
0006046260.tif 000007
【図７】
0006046260.tif 000008
【図８】
0006046260.tif 000009
【図９】
0006046260.tif 000010
【図１０】
0006046260.tif 000011
【図１１】
0006046260.tif 000012
【図１２】
0006046260.tif 000013
【図１３】
0006046260.tif 000014