(57)【要約】  不揮発性メモリにおいてデータを永続化するストレージ管理コンピューティング・デバイス、方法及び非一時的なコンピュータ読み取り可能な媒体は、少なくとも1つのストレージ・サーバーにおいて不揮発性メモリに関する複数のノードを含むデータ・ストレージ構造を維持することを含む。アップデートにおいて受信したキーが、データ・ストレージ構造の複数のノードの何れかにおける既存のキーに合致する場合が判定される。判定が合致を示す場合、データ・ストレージ構造の複数のノードの何れかにおける既存のキーであって受信したキーに合致するキーから伸びるベクトルのスロットに挿入するアップデートが提供される。
2017527909.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも1つのプロセッサ；及び
前記少なくとも1つのプロセッサに結合される少なくとも1つのメモリ；
を有するストレージ管理コンピューティング・デバイスであって：
前記プロセッサは、前記少なくとも1つのメモリに含まれる保存されたプログラムされた命令を実行するように構成され、
前記プロセッサは：
少なくとも1つのストレージ・サーバーにおいて不揮発性メモリに関する複数のノードを含むデータ・ストレージ構造を維持し；
アップデートにおいて受信したキーが、前記データ・ストレージ構造の複数のノードの何れかにおける既存のキーに合致する場合を判定し；及び
前記の判定が合致を示す場合、前記データ・ストレージ構造の複数のノードの何れかにおける既存のキーであって前記受信したキーに合致するキーから伸びるベクトルのスロットに挿入するアップデートを提供する；
ように構成される、ストレージ管理コンピューティング・デバイス。
【請求項２】
前記挿入するアップデートを提供することは、1つ以上のプログラムされた命令が、前記データ・ストレージ構造の複数のノードの何れにおいても追加的な右シフトを要しないアップデートを提供することを含む、請求項1に記載のストレージ管理コンピューティング・デバイス。
【請求項３】
前記メモリに結合されるプロセッサは：
前記データ・ストレージ構造の複数のノードの何れかにおける既存のキーであって前記受信したキーに合致するキーから伸びるベクトルが一杯である場合、別のベクトルの追加をトリガするために；
前記メモリに含まれる保存された1つ以上のプログラムされた命令を実行するように構成される、請求項1に記載のストレージ管理コンピューティング・デバイス。
【請求項４】
前記データ・ストレージ構造は、最新のコンシステント・バージョンを維持するマルチ・バージョン・データ・ストレージ構造を含む、請求項1に記載のストレージ管理コンピューティング・デバイス。
【請求項５】
前記最新のコンシステント・バージョンは、前記データ・ストレージ構造の複数のノードの何れかにおける既存のキーから伸びるベクトルのスロットにおいて、少なくとも受信したキーを有する、請求項4に記載のストレージ管理コンピューティング・デバイス。
【請求項６】
前記データ・ストレージ構造は、B+treeデータ・ストレージ構造を有する、請求項1に記載のストレージ管理コンピューティング・デバイス。
【請求項７】
前記メモリに結合されるプロセッサは：
前記の判定が前記受信したキーは既存の何れのキーとも異なることを示す場合、前記データ・ストレージ構造の複数のノードの何れかにおけるスロットへ挿入するためのアップデートを提供するために；
前記メモリに含まれる保存された1つ以上のプログラムされた命令を実行するように構成される、請求項1に記載のストレージ管理コンピューティング・デバイス。
【請求項８】
不揮発性メモリにおいてデータを永続化する方法であって：
ストレージ管理コンピューティング・デバイスが、少なくとも1つのストレージ・サーバーにおいて不揮発性メモリに関する複数のノードを含むデータ・ストレージ構造を維持するステップ；
アップデートにおいて受信したキーが、前記データ・ストレージ構造の複数のノードの何れかにおける既存のキーに合致する場合を、前記ストレージ管理コンピューティング・デバイスが判定するステップ；及び
前記の判定が合致を示す場合、前記データ・ストレージ構造の複数のノードの何れかにおける既存のキーであって前記受信したキーに合致するキーから伸びるベクトルのスロットに挿入するアップデートを、前記ストレージ管理コンピューティング・デバイスが提供するステップ；
を有する方法。
【請求項９】
前記挿入するアップデートを提供することは、前記データ・ストレージ構造の複数のノードの何れにおいても追加的な右シフトを要しないアップデートを提供することを含む、請求項8に記載の方法。
【請求項１０】
前記データ・ストレージ構造の複数のノードの何れかにおける既存のキーであって前記受信したキーに合致するキーから伸びるベクトルが一杯である場合、別のベクトルの追加を、前記ストレージ管理コンピューティング・デバイスがトリガするステップを有する請求項8に記載の方法。
【請求項１１】
前記データ・ストレージ構造は、最新のコンシステント・バージョンを維持するマルチ・バージョン・データ・ストレージ構造を含む、請求項8に記載の方法。
【請求項１２】
前記最新のコンシステント・バージョンは、前記データ・ストレージ構造の複数のノードの何れかにおける既存のキーから伸びるベクトルのスロットにおいて、少なくとも受信したキーを有する、請求項11に記載の方法。
【請求項１３】
前記データ・ストレージ構造は、B+treeデータ・ストレージ構造を有する、請求項8に記載の方法。
【請求項１４】
前記の判定が前記受信したキーは既存の何れのキーとも異なることを示す場合、前記データ・ストレージ構造の複数のノードの何れかにおけるスロットへ挿入するためのアップデートを、前記ストレージ管理コンピューティング・デバイスが提供するステップを有する請求項8に記載の方法。
【請求項１５】
不揮発性メモリにおいてデータを永続化するための命令を保存した非一時的なコンピュータ読み取り可能な媒体であって、前記命令は、マシンにより実行可能なコードを含み、プロセッサにより実行されると、前記プロセッサにステップを実行させ、前記ステップは：
少なくとも1つのストレージ・サーバーにおいて不揮発性メモリに関する複数のノードを含むデータ・ストレージ構造を維持するステップ；
アップデートにおいて受信したキーが、前記データ・ストレージ構造の複数のノードの何れかにおける既存のキーに合致する場合を判定するステップ；及び
前記の判定が合致を示す場合、前記データ・ストレージ構造の複数のノードの何れかにおける既存のキーであって前記受信したキーに合致するキーから伸びるベクトルのスロットに挿入するアップデートを提供するステップ；
を有する、媒体。
【請求項１６】
前記挿入するアップデートを提供することは、前記データ・ストレージ構造の複数のノードの何れにおいても追加的な右シフトを要しないアップデートを提供することを含む、請求項15に記載の媒体。
【請求項１７】
前記データ・ストレージ構造の複数のノードの何れかにおける既存のキーであって前記受信したキーに合致するキーから伸びるベクトルが一杯である場合、別のベクトルの追加をトリガするステップを有する請求項15に記載の媒体。
【請求項１８】
前記データ・ストレージ構造は、最新のコンシステント・バージョンを維持するマルチ・バージョン・データ・ストレージ構造を含む、請求項15に記載の媒体。
【請求項１９】
前記最新のコンシステント・バージョンは、前記データ・ストレージ構造の複数のノードの何れかにおける既存のキーから伸びるベクトルのスロットにおいて、少なくとも受信したキーを有する、請求項18に記載の媒体。
【請求項２０】
前記データ・ストレージ構造は、B+treeデータ・ストレージ構造を有する、請求項15に記載の媒体。
【請求項２１】
前記の判定が前記受信したキーは既存の何れのキーとも異なることを示す場合、前記データ・ストレージ構造の複数のノードの何れかにおけるスロットへ挿入するためのアップデートを提供するステップを有する請求項15に記載の媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は一般にパーシステント・ストレージのための方法及びデバイスに関連し、特に、高速アップデート及び瞬時リカバリに関する不揮発性メモリにおけるデータの永続化のための方法及びデバイス等に関連する。
【背景技術】
【０００２】
近い将来、ストレージ・クラス・メモリ(storage  class  memories：SCM)とも呼ばれる不揮発性メモリ(NVM)は、プロセッサに隣接するメモリ・バスにおけるデュアル・インライン・メモリ・モジュール(a  dual  in-line  memory  module：DIMM)の形態で利用可能になり、そのSCMは、ダイナミック・ランダム・アクセス・メモリ(DRMA)より低いギガビット(GB)当たりのコストを有し、且つ、DRAMに匹敵するパフォーマンスを有する。NVMは、プロセッサからのロード及びストア命令を介してアクセスされることが可能であるので、ストア命令によるNVMへの如何なる書き込みも、実行直後にデータをパーシステント(永続的)にする。その結果、プロセッサにより処理されるデータ構造は、本来の形式で維持されることが可能であり、ディスク・パーシステンシー(disk  persistency)の場合に行われるようなデータ変換の必要性を排除する。これに対して、例えば、ディスク・パーシステンシーの場合、データは、書き込みを発行する前にディスク・フォーマットに変換される(例えば、シリアル化される)必要がある。
【０００３】
NVMに関するデータ構造をパーシステント化することは、DRAMのような速度でパーシステンシーを提供することを含む幾つもの利点を有し、DRAMのような速度とは、ソリッド・ステート・ドライブ(SSD)におけるデータを永続的にするための数十マイクロ秒、或いは、ハード・ディスク・ドライブ(HDD)におけるデータを永続的にするための数ミリ秒とは異なり、ナノ秒である。その結果、NVMにおけるデータのパーシステント化は、SSDにおけるものより数百倍速く、HDDにおけるものよりも数千倍速く達成されることが可能である。
【０００４】
更に、NVMにおけるデータ構造のパーシステント化は、データを永続化させるために1回の書き込みしか必要としないことに起因して、ログ・レス永続性(log-less  durability)を提供し、これは現在のパーシステンシー・アーキテクチャで2回の書き込みが必要とされていることと相違し、すなわち、従来のアーキテクチャでは、1つは持続的な媒体に書き込みを記録するためであり、1つはイン・メモリ揮発性状態を更新するためである。その結果、NVMにおけるデータ構造のパーシステント化は、シングル・レイヤ・ストアを有するログ・レス永続性方式を提供し、これは遅延及びスペース・オーバーヘッドを節約する。
【０００５】
更に、NVMにおけるデータ構造のパーシステント化は、NVMへの書き込み後データは速やかに永続的になるので、瞬間的なリカバリをもたらす。不具合が生じた場合、リカバリは、データ構造を再初期化し、何らかの部分的な更新(partial  updates)を戻すことを含む。データがNVMで永続的である場合、ログの再生(又はリプレイ)は必要とされないので、リカバリは1秒以内に実行可能である。
【０００６】
従って、上述したように、NVMにおいてデータ構造をパーシステント化する利点は多いが、そのようにすることは自明なことではなく、それ自体固有の問題を提起する。特に、NVMにおけるデータ構造をパーシステント化することに関し、アプリケーション書き込み順序をどのようにして維持するかを含む幾つかの問題が解決されなければならない。NVMに関するアプリケーション書き込み順序を維持することは自明なことではなく、なぜなら、プロセッサは、アプリケーション順序とは異なる順序で、NVMに対するキャッシュ内の修正されたデータを退去させることが可能だからである。その結果、修正されたデータが退けられる一方、システム・クラッシュは、NVMのデータを、データを破壊するおそれがあるインコンシステントな状態に置き去りにしてしまう。この問題は、キャッシュを退去させるようにプロセッサに明示的に通知するキャッシュ・ライン・フラッシュ(CLFLUSH)命令、及び、NVMのデータ構造に対するポインタが更新される前にメモリ・バリアを設定するストア・フェンス(SFENCE)命令を利用することにより、解決される。
【０００７】
NVMのデータ構造のパーシステント化に付随する別の問題は、一貫性又はコンシステンシー(consistency)のために、部分的な更新を戻すことに付随する。キャッシュは揮発性であり、NVMに到る前に、修正されたデータを維持する。大規模な更新(又はアップデート)がトランザクションで実行されることを要する場合、電力障害は、NVMを部分的な更新のまま置き去りにするかもしれない。これらの部分的な更新は、何らかの更なる更新が適用される前に、戻される必要がある。
【０００８】
この問題は、変更の履歴を知ることにより解決され、それにより、障害が生じた差異に、リカバリは、変更を検査し、部分的な更新を元に戻すことを含む。この部分的な更新問題を解決する技術は、持続性の媒体に対してログをとり、不具合が生じた場合にそのログに基づいて再生すること、或いは、マルチ・バージョン・データ構造のような変更の履歴を維持するデータ構造を利用することを含む。マルチ・バージョン・データ構造を利用することは、ログ・レスであることの本来的な利点を有する。
【０００９】
NVMにおけるパーシステント・インデックス構造を維持するために、揮発性ビー・プラス・ツリー(B+Tree)データ・ストレージ構造が使用されることが可能である。不都合なことに、NVMにおけるこの種のパーシステント・インデックス構造に付随して問題が存在する。この種のデータ構造の場合、書き込み又は挿入の速度は、64バイトより多いデータに対して10(usec)であり、これは、必要とされる既存のB+Treeデータ・ストレージ構造における進行する並べ替え(ソーティング)に起因する。特に、それぞれの新たな書き込み又は挿入は、右シフト、すなわちインサート・ソートを生じさせ、リーフ・ノードでは、右シフトされたデータを永続化するため、及び、NVMにおけるデータ構造の所望の永続性及び一貫性を達成するために、追加的なCLFLUSH命令の実行を必要とするが、これは、望まれない遅延を招いてしまう。更に、B+Treeデータ・ストレージ構造に関し、同じキーに対する複数のアップデートが必要とされる場合、データ構造の所望の持続性及び一貫性を達成するために、ライト・アンプリフィケーション(write  amplification)が更にプロナウンス(pronounce)される。
【００１０】
この点に関する具体例が、図4に示される従来のマルチ・バージョンB+Treeデータ・ストレージ構造に関して示されている。この例では、(1,9)というキー/バリュー(又は値)のペアを、マルチ・バージョンB+Treeデータ・ストレージ構造のノードの最新のコンシステント・バージョン3(ccv=3)に挿入(又はインサート)するために、(12,8)，(8,3)及び(5,1)というキー/バリューのペアがそれぞれ右シフトされ、(1,9)というキー/バリューのペアが挿入され、最終的に、ノードの最新のコンシステント・バージョン4(ccv=4)を形成している。
【００１１】
次に、(1,4)というキー/バリューのペアを挿入する際、既存のノードのスロットは全て一杯(full)であるので、2つの新たなリーフ・ノードが形成されなければならない。2つの新たなリーフ・ノードが形成されると、(12,8)及び(8,3)というキー/バリューのペアは、新たなリーフ・ノードのうちの一方に対して右シフトされ、(5,1)というキー/バリューのペアは、(1,4)という新たなキー/バリューのペアがそのリーフ・ノードに挿入される前に、新たな他方のリーフ・ノードにおいて右シフトされる必要がある。従って、この例に示されるように、既存のノードのキー/バリューのペア(1,9)のうちの既存のキーに合致するキーを有する(1,4)というキー/バリューのペアの挿入は、このアップデートを達成するために、プロナウンスされるライト・アンプリフィケーションを有する。
【発明の概要】
【００１２】
ストレージ管理コンピューティング・デバイスは、少なくとも1つのプロセッサに結合される少なくとも1つのメモリを含み、プロセッサは、少なくとも1つのメモリに含まれる保存されたプログラムされた命令を実行し、少なくとも1つのストレージ・サーバーにおいて不揮発性メモリに関する複数のノードを含むデータ・ストレージ構造を維持するように構成される。アップデートにおいて受信したキーが、データ・ストレージ構造の複数のノードの何れかにおける既存のキーに合致する場合が判定される。判定が合致を示す場合、データ・ストレージ構造の複数のノードの何れかにおける既存のキーであって受信したキーに合致するキーから伸びるベクトルのスロットに挿入するアップデートが提供される。
【００１３】
不揮発性メモリにおいてデータを永続化する方法は、ストレージ管理コンピューティング・デバイスが、少なくとも1つのストレージ・サーバーにおいて不揮発性メモリに関する複数のノードを含むデータ・ストレージ構造を維持することを含む。アップデートにおいて受信したキーが、データ・ストレージ構造の複数のノードの何れかにおける既存のキーに合致する場合が、ストレージ管理コンピューティング・デバイスにより判定される。判定が合致を示す場合、データ・ストレージ構造の複数のノードの何れかにおける既存のキーであって受信したキーに合致するキーから伸びるベクトルのスロットに挿入するアップデートが、ストレージ管理コンピューティング・デバイスにより提供される。
【００１４】
非一時的なコンピュータ読み取り可能な媒体は、不揮発性メモリにおいてデータを永続化するための命令を保存し、命令は、マシンにより実行可能なコードを含み、プロセッサにより実行されると、プロセッサにステップを実行させ、ステップは、少なくとも1つのストレージ・サーバーにおいて不揮発性メモリに関する複数のノードを含むデータ・ストレージ構造を維持することを含む。アップデートにおいて受信したキーが、データ・ストレージ構造の複数のノードの何れかにおける既存のキーに合致する場合が、判定される。判定が合致を示す場合、データ・ストレージ構造の複数のノードの何れかにおける既存のキーであって受信したキーに合致するキーから伸びるベクトルのスロットに挿入するアップデートが提供される。
【００１５】
本技術は、高速アップデート及び瞬時リカバリのために不揮発性メモリのデータを永続化する方法、非一時的なコンピュータ読み込み可能媒体、及び、デバイスを提供する。本技術によれば、リーフ・ノードは、同じキーに対するアップデートについては縦に(vertically)成長し、固有のキーについてのみ横に(horizontally)成長するように形成される。ベクトルに対するアップデートは単独の挿入(又はインサート)の中で実行されるので、従来の実現手段と比較して、右シフトがゼロであり、右シフトが無いことはライト・アンプリフィケーションを劇的に減らす。更に、本技術によれば、ロード及びストア・メモリ命令を利用して、本来の形式で(すなわち、如何なる変換もせずに)、NVMのB+Treeデータ・ストレージ構造において、データを永続化することが可能である。更に、本技術は、例えば1ないし百万の範囲に及ぶアップデートのような複数のアップデートに対するインデックス・データ・ストレージ構造レイアウトを最適化し、その最適化は、従来の既存のシステムに対して、書き込みの遅延を4倍、及び、読み込みの遅延を2倍改善する。更に、本技術は、マルチ・バージョン・データ・ストレージ構造を利用して、スナップショット(すなわち、アプリケーション・コンシステント・ビュー又はアプリケーション一貫性維持)を取得し、新たに追加されるベクトルとともにログ・レス・リカバリ機構を提供する。
【図面の簡単な説明】
【００１６】
【図１】高速アップデート及び瞬時リカバリのための不揮発性メモリにおけるデータを永続化するストレージ管理コンピューティング・デバイスの環境例のブロック図。
【図２】図1に示されるストレージ管理コンピューティング・デバイスの一例についてのブロック図。
【図３】高速アップデート及び瞬時リカバリのための不揮発性メモリにおけるデータを永続化する方法のフローチャートを示す図。
【図４】従来のマルチ・バージョンB+treeデータ・ストレージ構造における様々なアップデート形式を示す図。
【図５】本願実施例によるベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造におけるアップデートを示す図。
【図６】書き込み遅延に関し、本実施例によるベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造による改善を示すグラフ(従来の既存のシステムを4倍上回る)。
【図７】読み込み遅延に関し、本実施例によるベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造による改善を示すグラフ(従来の既存のシステムを2倍上回る)。
【発明を実施するための形態】
【００１７】
図1及び図2には、不揮発性メモリ(NVM)ストレージ管理コンピューティング・デバイス12の一例によるネットワーク環境10が示されており、そのデバイスは高速アップデート及び瞬時リカバリのために不揮発性メモリにおけるデータを永続化する。環境例10は、NVMストレージ管理コンピューティング・デバイス12、クライアント・コンピューティング・デバイス14(1)-14(n)、NVMストレージ・デバイス16、及び、ダイナミック・ランダム・アクセス・メモリ(DRAM)ストレージ・デバイス17を含んでいるが、環境例10は、他のタイプ及び/又は異なる個数のシステム、デバイス、コンポーネント及び/又はエレメントを他のコンフィギュレーションにおいて含むことが可能である。この実施例は多数の利点を提供し、その利点は、高速アップデート及び瞬時リカバリのために不揮発性メモリにおけるデータを永続化する方法、不揮発性コンピュータ読み取り可能媒体及びデバイスを提供することを含む。
【００１８】
クライアント・コンピューティング・デバイス14(1)-14(n)は通信ネットワーク18を介してNVMストレージ管理コンピューティング・デバイス12と通信を行い、NVMストレージ管理コンピューティング・デバイス12は、別の通信ネットワークを介して、NVMストレージ・デバイス16及びダイナミック・ランダム・アクセス・メモリ(DRAM)ストレージ・デバイス17と通信を行う。一例として、通信ネットワーク18及び20は、相互接続、ローカル・エリア・ネットワーク(LAN)、ワイド・エリア・ネットワーク(WAN)、及び/又は、それらの組み合わせであるとすることが可能であるが、他のタイプ及び/又は他の個数の通信ネットワークが使用されてもよい。
【００１９】
この例におけるクライアント・コンピューティング・デバイス14(1)-14(n)の各々は、プロセッサ、メモリ、通信インターフェース、入力デバイス及びディスプレイ・デバイスを含むことが可能であり、それらはバス又は他のリンクで互いに結合されるが、クライアント・コンピューティング・デバイス14(1)-14(n)の各々は他のタイプ及び他の個数のコンポーネントを有することが可能である。クライアント・コンピューティング・デバイス14(1)-14(n)は、インターフェースを提供するインターフェース・アプリケーションを実行させ、そのインターフェースは、例えばNVMストレージ管理コンピューティング・デバイス12によりホストされるアプリケーションとの間でデータを送受信するためのものである。クライアント・コンピューティング・デバイス14(1)-14(n)の各々は、例えば、従来のパーソナル・コンピュータ(PC)、ワークステーション、スマート・フォン、或いは、他のプロセシング及び/又はコンピューティング・システムであってもよい。
【００２０】
NVMストレージ・デバイス16及びDRAMストレージ・デバイス17は、この例では、NVMストレージ管理コンピューティング・デバイス12からの様々なリード及びライト・リクエスト(例えば、本実施例で説明及び記述されるようなデータを書き込む又は保存するためのリクエスト)を受信して応答する。NVMストレージ・デバイス16及びDRAMストレージ・デバイス17の各々は、プロセッサ、メモリ及び通信インターフェースを含むことが可能であり、それらはバス又は他のリンクにより互いに結合されているが、NVMストレージ・デバイス16及びDRAMストレージ・デバイス17の各々は他のタイプ及び他の個数のコンポーネントを含むことが可能である。一例として、NVMストレージ・デバイス16は任意のタイプの不揮発性パーシステント・ストレージを含むことが可能であり、DRAMストレージ・デバイス17は、従来の磁気的又は光学的なディスク、或いは、ブロック形式のアーキテクチャでデータを保存することに適したものを含むことが可能である。
【００２１】
NVMストレージ管理コンピューティング・デバイス12は、NVMストレージ・デバイス16及びDRAMストレージ・デバイス17にアクセスし、それらを利用してデータを保存及び永続化するために、クライアント・コンピューティング・デバイス14(1)-14(n)により使用されることが可能であるが、他のタイプ及び/又は他の個数のストレージ管理コンピューティング・デバイスが使用されることも可能である。更に具体的に図2を参照すると、例示的なNVMストレージ管理コンピューティング・デバイス12のブロック図が示されている。この例では、NVMストレージ管理コンピューティング・デバイス12は、プロセッサ22、メモリ24及び通信インターフェース26を、バス28又は他のリンクで互いに結合された形式で含むが、他の個数及び他のタイプのデバイスが使用されることも可能である。
【００２２】
NVMストレージ管理コンピューティング・デバイス12におけるプロセッサ22は、本実施例により記述及び説明されるように、本発明の1つ以上の側面に関する保存された命令のプログラムを実行するが、プロセッサ22は他の個数及び他のタイプのプログラムされた命令を実行することも可能である。NVMストレージ管理コンピューティング・デバイス12におけるプロセッサ22は、例えば、1つ以上のセントラル・プロセシング・ユニット又は1つ以上のプロセシング・コアを有する汎用プロセッサを含んでよい。
【００２３】
NVMストレージ管理コンピューティング・デバイス12におけるメモリ24は、本願で記述及び説明されるように、本発明の1つ以上の側面に関するプログラムされた命令を保存するが、プログラムされる命令のうちの全部又は一部が別の場所に保存され及び/又は実行されることも可能である。例えば、ダイナミックRAM(DRAM)のようなランダム・アクセス・メモリ(RAM)又は他のコンピュータ読み取り可能な媒体を含む多種多様なタイプのメモリ・ストレージ・デバイスが使用可能であり、その媒体は、プロセッサ22に結合される磁気的、光学的又はその他の読み込み及び/又は書き込みシステムから読み込まれる及び/又はそれらにより書き込まれる。この例では、メモリ24はキャッシュ30を含むが、メモリは、他のタイプ及び/又は他の個数のデータ・ストレージ、モジュール及び/又は他のプログラムされた命令を含むことが可能である。
【００２４】
NVMストレージ管理コンピューティング・デバイス12の通信インターフェース26は、クライアント・コンピューティング・デバイス14(1)-14(n)とストレージ・デバイス16(1)-16(2)との間で通信を行うために使用され、これらのデバイスは全て通信ネットワーク18及び20により互いに結合されているが、他のデバイス及びエレメントに対する他のタイプ及び個数のコネクション及びコンフィギュレーションとともに、他のタイプ及び個数の通信ネットワーク又はシステムが使用されることも可能である。単なる一例として、1つ以上の通信ネットワーク18及び20は、HTTP(hypertext  transfer  protocol)及び/又はHTTPS(secure  HTTP  (HTTPS))を含むTCP/IPオーバー・イーサーネット及び業界標準プロトコルを利用することが可能であるが、他のタイプ及び個数の通信ネットワークが使用されることが可能であり、その通信ネットワークの各々は各自自身の通信プロトコルを有している。
【００２５】
NVMストレージ管理コンピューティング・デバイス12、クライアント・コンピューティング・デバイス14(1)-14(n)、NVMストレージ・デバイス16及びDRAMストレージ・デバイス17の具体例が本明細書に記述されているが、本願で説明される具体例のデバイス及び/又はシステムは、例示を目的としているに過ぎず、具体例を実現するために使用される多くの様々な特定のハードウェア及びソフトウェアが使用可能であり、そのような可能性は関連する技術分野における当業者に認められるであろう。更に、2つ以上のコンピューティング・システム又はデバイスは、何らかの実施例における何らかの1つのシステムと置換されることが可能である。
【００２６】
実施例は、非一時的なコンピュータ読み取り可能な媒体として実現されてもよく、本願で説明されるように、実施例により記述及び説明される本技術の1つ以上の側面に関し、媒体はそこに命令を保存しており、命令は、NVMストレージ管理コンピューティング・デバイス12のプロセッサ22により実行されると、本明細書に記述及び説明される方法例の実現に必要なステップの実行を、プロセッサ22に行わせる。
【００２７】
図1-3及び5-7に関連して、高速アップデート及び瞬時リカバリのために不揮発性メモリのデータを永続化する方法例が説明される。具体的に図3を参照すると、ステップ100において、NVMストレージ管理コンピューティング・デバイス12は、1つ以上のベクトルをサポートするベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造を維持するが、1つ以上のベクトルをサポートする他のタイプ及び/又は個数のデータ・ストレージ構造が使用されてもよい。
【００２８】
ステップ102において、NVMストレージ管理コンピューティング・デバイス12は、NVMストレージ・デバイス16で永続化されるように、クライアント・コンピューティング・デバイス14(1)-14(n)のうちの1つから、キー/バリューのペアを有するアップデートを受信するが、アップデートは、他のロケーションにおえる不揮発性メモリに対して永続化されることも可能である。更に、この特定の実施例では、何れかのクライアント・コンピューティング・デバイス14(1)-14(n)からのアップデートは書き込みリクエストであるが、NVMストレージ管理コンピューティング・デバイス12は、例えば読み込みリクエストのような他のタイプ及び/又は個数のリクエストをクライアント・コンピューティング・デバイス14(1)-14(n)から受信することも可能であり、その読み込みリクエストは後述する図7のグラフに示されるように本技術により効率的に処理されるものである。
【００２９】
ステップ104において、NVMストレージ管理コンピューティング・デバイス12は、何れかのクライアント・コンピューティング・デバイス14(1)-14(n)からのアップデートにおけるキー/バリューのペアのうちの受信されたキーが、ベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造における何れかのノードにおける既存のキーに合致する場合を判定する。図4に関連して背景技術で言及された具体例に続いて、以下、ベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造の具体例に関する本技術が説明され、(1,4)というキー/バリューのペアを有するアップデートが、何れかのクライアント・コンピューティング・デバイス14(1)-14(n)から受信される場合において、キー/バリューのペア(1,9)のうちのキー1との一致が発見される。ステップ104において、NVMストレージ管理コンピューティング・デバイス12は、何れかのクライアント・コンピューティング・デバイス14(1)-14(n)からのアップデートにおけるキー/バリューのペアのうちの受信したキーが、ベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造における何れかのノードにおける既存のキーに合致することを確認し、ステップ106への「Y」の分岐が選択される。
【００３０】
ステップ106において、NVMストレージ管理コンピューティング・デバイス12は、単独のオペレーションとともに、ノードのうちの合致する既存のキー配下の縦ベクトル(vertical  vector)に追加されるように、ベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造に対する既存のキーに合致する、受信したキーのキー/バリューのペアを有するアップデートを提供するが、他のタイプ及び/又は個数のベクトル又は他の構造が、合致する既存のキーに関連する他の方向(又はオリエンテーション)で使用されることが可能である。この例では、受信したキーのキー/バリューのペアを有するアップデートは、若番順(youngest  first)方式を利用して、ノードのうちの合致する既存のキーの配下に伸びる縦ベクトルに追加されるように提供され、即ち、ベクトルは下から満たされ、最も若い値へのアクセスは0(1)オペレーションであるが、例えば単なる一例として、老番順(oldest  first)のような他のアプローチが使用されることも可能である。老番順方式が使用される場合、ベクトルは順方向に満たされ、この例の場合、最も若い値へのアクセスはO(n)オペレーションである。従って、例えば若番順又は老番順のような何れのアプローチが使用されるかに依存して、ベクトルにおける特定の値を探す時間(長)は異なる。例えば、若番順方式が使用される場合、ベクトルのうち最も若い値を探すことが最も速く、最も古い値を探すことは最も遅れる。例えば、老番順が使用される場合、ベクトルのうち最も若い値を探すことは最も遅れ、最も古い値を探すことは最も速い。一例として、図5では、(1,4)というキー/バリューのペアが、ベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造のノードにおける合致した既存のキー1の配下に伸びる縦ベクトルに追加されるように提供されるが、老番順方式のような他のアプローチが使用されることも可能である。
【００３１】
ステップ108において、NVMストレージ管理コンピューティング・デバイス12は、NVMストレージ・デバイス16のベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造のノードにおける既存のキーの下にあるベクトルが、一杯であるか否かを判定する(その既存のキーは、受信したキーに合致するキーである)。ステップ108において、NVMストレージ管理コンピューティング・デバイス12が、受信したキーに合致する既存のキーの配下にあるベクトルは一杯であると判定すると、ステップ110に至る「Y」の分岐が選択される。
【００３２】
ステップ110において、データ・ストレージ構造の複数のノードのうちの何れかの中にある既存のキーであって受信したキーに合致するキーから派生するベクトルが一杯である場合、NVMストレージ管理コンピューティング・デバイス12は、NVMストレージ・デバイス16のベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造のノードに、別のベクトルを追加することをトリガする。具体例として、図5では、既存のキー1の配下に先ず示されるベクトルは一杯になっておらず、9の値がノードの最終コンシステント・バージョン4(ccv=4)の一部として示され、4の値がノードの最終コンシステント・バージョン5(ccv=5)の一部として示されている。しかしながら、そのベクトルが一杯であった場合、別のベクトルが、ノードの既存のキー1の配下への追加のためにトリガされ、例示の目的でその追加ベクトルが図5に示されている。
【００３３】
再びステップ108において、NVMストレージ管理コンピューティング・デバイス12が、受信したキーに合致する既存のキー配下のベクトルが一杯でないと判定すると、ステップ112に至る「N」の分岐が選択される。ステップ112では、ベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造における既存のキーであって受信したキーに合致するキーの配下にあるベクトルに、受信したアップデートのキー/バリューのペアにおけるバリューが追加される。更に、この例では、ベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造は、ベクトルに何らかの値を含むそのノードに関して最新の現在のコンシステント・バージョンを維持する。一例として、図5では、(1,4)というキー/バリューのペアのうちのバリュー(又は値)4が、ベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造のノードにおける合致する既存のキー配下の縦ベクトルに追加される。更に、図5の例に示されるように、既存のキー配下のベクトルにおけるバリュー4は、ベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造のノードの最新のコンシステント・バージョン5(ccv=5)の一部として維持される。
【００３４】
再びステップ104において、NVMストレージ管理コンピューティング・デバイス12が、何れかのクライアント・コンピューティング・デバイス14(1)-14(n)からのアップデートにおけるキー/バリューのペアで受信したキーは、ベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造における何れかのノードにある既存のキーに合致しないと判定した場合、すなわちそのキーは特有である場合、ステップ114に至る「N」の分岐が選択される。ステップ114において、NVMストレージ管理コンピューティング・デバイス12は、ベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造のノードへの挿入のために、キー/バリューのペアにおいて受信したキーを提供する。
【００３５】
単なる一例として、図5において、最新のコンシステント・バージョン4(ccv=4)に関する例示のノードは一杯であったので、仮に、受信したアップデートが(2,7)というキー/バリューのペアを有していたとすると、受信したキー及び既存のキーの間に一致は存在しない。そして、ノードは一杯であり、合致するキーは存在しないので、2つのリーフ・ノードが形成される。次に、(12,8)及び(8,3)というキー・バリュー・ペア(複数)は一方のリーフ・ノードに関して右シフトされ、キー・バリュー・ペア(5,1)は、キー・バリュー・ペア(2,7)をキー1及び5の間に挿入する前に、他方のリーフ・ノードにおいて右シフトされる。
【００３６】
従って、本願の実施例とともに例示及び説明されるように、本技術は、高速アップデート及び瞬時リカバリのために不揮発性メモリのデータを永続化する方法、非一時的なコンピュータ読み込み可能媒体、及び、デバイスを提供する。本技術によれば、リーフ・ノードは、同じキーに対するアップデートについては縦に成長し、固有のキーについてのみ横に成長するように形成される。ベクトルに対するアップデートは単独の挿入(又はインサート)の中で実行されるので、従来の実現手段と比較して、右シフトがゼロであり、右シフトが無いことはライト・アンプリフィケーションを劇的に減らす。更に、本技術によれば、ロード及びストア・メモリ命令を利用して、本来の形式で(すなわち、如何なる変換もせずに)、NVMのB+Treeデータ・ストレージ構造において、データを永続化することが可能である。
【００３７】
更に、本技術は、例えば1ないし百万の範囲に及ぶアップデートのような複数のアップデートに対するインデックス・データ構造レイアウトを最適化し、それにより、書き込みの挿入は基礎的なパーシステントMVDSより4倍速くなり、読み込みは基礎的なパーシステントMVDSより2倍速くなる。単なる一例として、本実施例によるベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造により、書き込み遅延(又はレイテンシ)に関して従来の既存のシステムを4倍上回る改善を示すグラフが、図6に示されている。更に、単なる一例として、本実施例によるベクトル化されたマルチ・バージョンB+treeデータ・ストレージ構造により、読み込み遅延(又はレイテンシ)に関して従来の既存のシステムを2倍上回る改善を示すグラフが、図7に示されている。
【００３８】
更に、本技術は、マルチ・バージョン・データ構造を活用及び拡張し、スナップショット(すなわち、アプリケーション・コンシステント・ビュー)を提供し、ログ・レス・リカバリ機構を提供するように、ベクトルを含める。本実施例によりデータがNVMで永続化される場合、ログ・リプレイは必要とされないので、リカバリは1秒以内で実行されることが可能である。
【００３９】
以上、本発明の基本概念を説明してきたが、上記の詳細な開示は、単なる一例として提示されるように意図されており、限定ではないことが、当業者にとって明らかであろう。本願で明示的には言及されていないが、様々な代替、改善及び修正が存在し、それらは当業者に把握される。これらの代替、改善及び修正は、本願により示されており、本発明の精神及び目的の範囲内に属する。更に、シーケンス又はエレメントを処理する説明された順序、或いは、数や文字を利用すること又はその他の指定は、請求項におけるプロセスを、その請求項で指定されるもの以外の何らかの順序に限定するようには意図されていない。本発明は特許請求の範囲及びその均等物によってのみ規定される。
【図１】
2017527909.tif 000003
【図２】
2017527909.tif 000004
【図３】
2017527909.tif 000005
【図４】
2017527909.tif 000006
【図５】
2017527909.tif 000007
【図６】
2017527909.tif 000008
【図７】
2017527909.tif 000009
【国際調査報告】
2017527909.tif 000010
2017527909.tif 000011
2017527909.tif 000012