(57)【要約】  キー−バリュー・ストアは、分散型でかつ耐障害性のある態様でデータへのカラム指向アクセスを提供する。データはデータ・ストアに挿入される、そしてデータは高いレートでデータ・ストアからランダムにまたはシーケンシャルに読み出される。テーブルのキーは順序付けられていて、そしてテーブル全体はキー範囲に分割されている。各キー範囲は、パーティションと呼ばれるキー範囲にそれ自身が分割されているテーブルによって、扱われる。パーティションも、セグメントに分割されている。より小さいさらにより小さいキー範囲へのこのような再帰的分割は、並列性を提供する。最も高いレベルで、タブレット上の操作は、異なるノードに分散される。下位レベルで、異なるスレッドは、個々のセグメント上の操作を扱う。大規模な再構成操作は個々のセグメント上の操作に分解することが出来るので、より大きなオブジェクト上の大域ロックを、操作全体に渡って保持する必要は無い。【選択図】なし
2015534685.tif 000002
【特許請求の範囲】
【請求項１】
分散型でかつ耐障害性のある態様でデータへのカラム指向アクセスのためのコンピュータの実施方法であって、
データが挿入されるデータ・ストアを提供するステップを備え、かつそのデータ・ストアから、データが、高いレートで、ランダムにまたはシーケンシャルに、以下のステップ、  少なくとも１つのテーブルに対してキー−バリュー・ストアにおけるキーを順序付け、かつ当該テーブルを完全にキー範囲に分割するステップ、
少なくとも一つのパーティションを備えるキー範囲に分割される当該キー範囲テーブルによって、各キー範囲を扱うステップ、
最も高いレベルで、テーブル上の操作を異なるノードに分布させるステップ、
より低いレベルで、個々のパーティションまたはパーティションの部分上の操作を扱うために異なるスレッドを使用するステップ、
大規模な再構成操作を、個々のパーティションまたはパーティションの部分の操作に分解するステップ、
により、取り出される方法。
【請求項２】
更に、再構成の間に行われるアクセスおよび更新を可能にするリダイレクション・リンクを用いるステップを備え、前記タブレット・レベルでの再構成が、サービスの中断無しに達成される、請求項１に記載の方法。
【請求項３】
更に、当該キー−バリュー・ストアを当該データ・ストアのファイル・システムに密に統合するステップを備え、標準ファイル・システム操作が、当該キー−バリュー・ストア・テーブルに直接実行される、請求項１に記載の方法。
【請求項４】
当該標準ファイル・システム操作が、スナップショットおよびミラーの何れかを備える、請求項３に記載の方法。
【請求項５】
更に、ログをレプレイする必要無しにテーブルを開くステップを備える、請求項１に記載の方法。
【請求項６】
更に、回復操作を実行すること無く読出し専用テーブルを開くステップを備える、請求項１に記載の方法。
【請求項７】
更に、操作を当該データ・ストアのファイル・システムと同期させるステップを備え、テーブル・スナップショットが、直接使用可能である、請求項１に記載の方法。
【請求項８】
分散型でかつ耐障害性のある態様でデータへのカラム指向アクセスのためのコンピュータの実施方法であって、
テーブルをタブレットおよびパーティションに累進的に分解するステップと、
共通キー−バリュー・データベース操作の上位版を実施するステップとを備え、
カラム指向パフォーマンスが、スキーマ有りまたは無しで、ネスト状のデータ構造を収容すると考えられるデータに提供される、
方法。
【請求項９】
更に、前記同じテーブル上に異なるアプリケーション・ライブラリとの異なるインタフェースをエミュレートするステップを備える、請求項８に記載の方法。
【請求項１０】
当該キーの何れか並びにメモリ内の持続的な常駐、固体ディスク上のストレッジ、及びハードディスク上のストレッジの何れかのデータを独立して設定するステップと、パフォーマンス対カラム・ファミリ当たりのコストを調整するステップとを、
備える、請求項８に記載の方法。
【請求項１１】
当該分解するステップが、更に、
当該テーブルのキー空間を再帰的に分割するステップを備え、
当該テーブルが、タブレットを含み、それらのそれぞれには可能なキーの特定範囲が割り当てられていて、
各タブレットが、キー・サブ範囲に対するパーティションを収容し、
各パーティションまたはパーティションの部分が、単一の能動的に更新されたバケットを有し、
キー・バリューの各サブ・サブ範囲に対し１つのバケットが存在し、そして、
バケットのサイズが限定されると、新規なバケットが割り当てられ、そして前記以前のバケットが流出される、
請求項８に記載の方法。
【請求項１２】
非常に大きなクラスタおよび複数のクラスタのいずれかに渡って、当該タブレットを分布させるステップと、
あるノードで稼働するファイル・システム・プロセスによって、各タブレットを扱うステップと、
対応するファイル・システム・プロセスのネイティブ・コンポーネントによって、タブレット上の全ての操作を扱うステップとを、
更に、備える、請求項１１に記載の方法。
【請求項１３】
長時間に渡る操作の間、２つのタブレットが１つとして機能することを可能にするリダイレクト・リンクを使用するステップを、
更に、備える、請求項８に記載の方法。
【請求項１４】
スプリット操作のためのリダイレクト・ポインタを確立するステップと、
新規なタブレット構造を作成するステップと、
元のタブレット構造から当該新規なタブレット構造に２つのパーティションをコピーするステップとを
更に、備え、
既に移動したパーティションによってカバーされる範囲内のキーに対する当該元のタブレット構造内の検索が、当該元のタブレット構造から当該新規なタブレット構造に当該リダイレクト・ポインタをフォローすることによって、発見される、
請求項１３に記載の方法。
【請求項１５】
当該リダイレクト・リンクが、マージまたはスプリットが進行中であることを示す示度を提供するステップと、
当該リダイレクト・リンクが、スプリットの間、２つのタブレットが１つとして機能することを可能にするステップとを、
備え、
全ての操作が、スプリットが進行中であるという示度無しで進む、
請求項１３に記載の方法。
【請求項１６】
当該マージを生き残ったタブレット内にバケットを割り当てることによって、タブレットのマージを実行するステップと、
セグメント・マップを、当該生き残ったタブレットにコピーするステップとを、
備え、
当該リダイレクト・ポインタが、前記マージ操作の間、前記２つのタブレットを１つにみなし、そして、
当該マージ操作が行われるときに、当該リダイレクト・リンクが除去され、そして当該生き残ったタブレットが、２つのタブレットの完了したマージである、
請求項１３に記載の方法。
【請求項１７】
元のタブレットの量を増加させて新規なタブレット・コピーにミラー化させる累進的なコピーを実行することによって、タブレットのスプリット・アルゴリズムを実行するステップを、
更に、備える、請求項８に記載の方法。
【請求項１８】
当該タブレット・スプリット・アルゴリズムが、更に、
ミラー化された範囲、コピー・ウィンドウおよびペンディング・コピー領域を提供するステップと、
当該元のタブレットへの更新を、当該ミラー化された範囲内にパーティション・マップを有する当該新規なタブレット・コピーにミラー化するステップと、
コピーが進む間に、当該コピー・ウインドウの更新を制止するステップと、
当該コピーが完了した後、当該コピー・ウィンドウ領域を当該ミラー化された範囲に加えるステップとを、
備え、
更新が当該ミラー化された様式で進み、
当該ペンディング・コピーにおいて、当該元のタブレットに対する更新が、当該新規なタブレット・コピーにミラー化されない、
請求項１７に記載の方法。
【請求項１９】
当該コピー操作の間、当該元のタブレット・キー範囲を分割するステップを、更に、備え、
第一の部分が、当該元のタブレットに残存するキーから構成されるコピーされていない範囲を備え、
コピーされるキーが、
すでにコピーされているキーから構成されている当該ミラー化された範囲、
現在コピーされつつあるキーから構成されている当該コピー・ウィンドウ、および
カーソル範囲の後でキーに関連するデータから構成される当該ペンディング・コピー領域
を備える３つの部分に分割されている、
請求項１８に記載の方法。
【請求項２０】
当該コピーされていない範囲のキーに対し、全ての更新を当該元のタブレットのみに適用するステップと、
当該ミラー化された範囲のキーに対し、当該元のタブレットによって受信された全ての更新を当該新規なタブレット・コピーに送り、かつ両方の更新が適用された後に承認を戻すステップと、
当該コピー・ウィンドウのキーに対し、当該コピー・ウィンドウ内の当該キーおよびデータがコピーされている間に、全ての更新を制止するステップとを、
備え、
当該コピー・ウィンドウが、ペンディング範囲からキーの新規なセットに移動されると即座に、当該更新が、解除され、
当該更新が解除されるときに、以前当該コピー・ウィンドウにあったキーが、今や、当該ミラー化された範囲にあり、そして当該更新が、当該元のタブレットおよび当該新規なコピー・タブレットの両方に適用され、
当該ペンディング範囲において、全ての更新が、当該元のタブレットに適用される、
請求項１９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明はコンピュータ・ファイル・システムに関する。特に、本願発明は、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は、操作と、実行中のファイル・システムとを容易に同期させることができないので、この変異は必要である。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
このようなシステムの更なる関心は、書き込まれた物理的情報の実際量が、書き込もうとした論理的量の何倍にもなる、フラッシュメモリおよびソリッド・ステート・ドライブ(SSD)に関連した望ましくない現象であるライト・アンプリフィケーション(WA:Write Amplification)である。フラッシュメモリは、再書込みを可能とする前に消去されなければならないので、これらの操作を実行するプロセスは、ユーザ・データおよびメタデータを二回以上移動させる(または再書込みする)結果になる。この増倍効果は、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に示されるコンポーネントにアクセスすることが出来るかを示すブロック略図である。
【図３】潜在的に何十または何百テラバイト(TB)のデータを含むテーブルを、どのようにして、各々が最高数ギガバイト(GB)までのデータを含む多くのタブレットに分解することが出来るかを示す階層的なダイアグラムである。
【図４】テーブルiノードの詳細な構造を示すブロック略図である。
【図５】タブレットの内部構造を示すブロック略図である。
【図６】リダイレクト・リンクを、どのように、使用して、テーブル・スプリットまたはマージのような長時間にわたる操作の間、２つのタブレットを1つとして機能させるかを示すブロック略図である。
【図７】ミラー化された範囲、コピー・ウィンドウおよび保留状態のコピー領域を使用する交互のコピー・アルゴリズムを示すブロック略図である。
【図８】セグメント・マップの内部構造を示すブロック略図である。
【図９】セグメントの内部構造を示すブロック略図である。
【図１０】ストレッジ・プール・オフセットからフラッシュ・ストレッジへのマッピングを示すブロック略図である。
【図１１】単一のセグメントのジェネレーション1および2のマージを示すブロック略図である。
【図１２】リダイレクト・リンクを使用して、マージまたはスプリットのような実行時間が長い操作の間に、２つのセグメント・マップを実質的にマージするために、セグメント・マップの構造を示すブロック略図である。
【図１３】本願明細書に開示される何れかの方法をマシンに実行させる命令のセットを実行することができるコンピュータ・システムの具体例のマシンを表すブロック略図である。
【発明を実施するための形態】
【００１７】
コンポーネント間の通信
図1は、各々が、稼働しているMapR FSまたはMFSプロセス103, 104を有する２台のコンピュータまたはノード101、102を示す。図1において、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転送を可能にする。MapR DBクライアント201によって使用される共用メモリ・インタフェース203と同等なものを実装して、同じノード上のMFSプロセス103と通信するために、このようなRDMAインタフェースを使用することが出来る。これは、異なるノード102上のMapR DBクライアント204が、あたかもそれが同じノードにあるかのようにして、可能な限りほとんど同じレートで通信することを可能にする。
【００２３】
テーブルのテーブル、パーティションおよびセグメントへの再帰的分割
図３において、再帰的分割が、テーブルのキー空間に実行される。テーブルには、それぞれに可能なキーの特定範囲が割り当てられているタブレットが収容されている。各タブレットには、キーのサブ範囲に対するパーティションが収容されている。各パーティションは、単一の能動的に更新されたバケットと多くのセグメント（キー・バリューの各サブ・サブ範囲に対し1つ）を有する。バケットのサイズが限定されると、新規なバケットが割り当てられ、かつこの以前のバケットは、セグメントに流出される。部分的に流出されたバケットは、それらが完全に流出されるまで作動しているので、この流出の間、サービスのロスはない。
【００２４】
テーブルからタブレットへそしてパーティションからセグメントへの広いファンアウト、および再帰的な分割に単一の層を使用することは、MapR DBのライト・アンプリフィケーションを、データベースの更新当たり約4.5のディスク書込みに限定する。これは、LevelDBに対し更新当たりほぼ20の書込みとは対照的である。Hbaseの場合、ライト・アンプリフィケーションは低いが、結果的に、長い圧縮と時折起こる遅延が生じがちである。
【００２５】
したがって、図３は、何十または何百テラバイト(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ノード番号を収容する通常のiノード参照でありかつ標準のMapR FS操作を使用して導出される。
【００３２】
タブレット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に移動されていて、これは、最終的に、元のテーブル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号の優先権を主張する。そして、これらの出願は、それぞれ、全体が参照によって本願明細書に組み込まれている。
【図１】
2015534685.tif 000003
【図２】
2015534685.tif 000004
【図３】
2015534685.tif 000005
【図４】
2015534685.tif 000006
【図５】
2015534685.tif 000007
【図６】
2015534685.tif 000008
【図７】
2015534685.tif 000009
【図８】
2015534685.tif 000010
【図９】
2015534685.tif 000011
【図１０】
2015534685.tif 000012
【図１１】
2015534685.tif 000013
【図１２】
2015534685.tif 000014
【図１３】
2015534685.tif 000015
【国際調査報告】
2015534685.tif 000016
2015534685.tif 000017
2015534685.tif 000018