(57)【要約】【課題】記録を処理するための方法、システム、及びコンピュータプログラムが開示される。【解決手段】記録は、記録セットに関連付けられる。記録セットは、１つ又は複数のプロセッサを含むプロセッサセットに関連付けられる。記録は、記録に関連付けられた記録セットに基づいて、処理のために、関連付けられたプロセッサセットにルーティングされる。記録は、プロセッサセット内のプロセッサ上で処理される。さらに、様々なローカライズされたアフィニティが確立されることが可能である。プロセスアフィニティは、サーバプロセスをプロセッサセットにリンクすることができる。キャッシュアフィニティは、データベースキャッシュをプロセッサセットにリンクすることができる。データアフィニティは、着信データをプロセッサセットにリンクすることができる。【選択図】図２
2020115367.tif 000002
【特許請求の範囲】
【請求項１】
複数のプロセッサ上でデータベース内の記録を処理する方法であって、前記複数のプロセッサは前記データベースに結合されており、前記複数のプロセッサは各々が少なくとも一つのプロセッサを含む物理的に分離された複数のプロセッサセットにグループ化されており、
前記方法は、
前記複数のプロセッサのうちの少なくとも１つのプロセッサ上で、各々が少なくとも一つの記録を含む複数の記録セットのうちの１つの対象記録セットに、各記録を関連付けるステップであり、前記対象記録セットは、各記録を識別するための記録番号Ｒを前記複数のプロセッサセットの数Ｎで除算した余りの値により識別され、前記余りの値は前記対象記録セットの識別子に等しく、各記録は、前記データベースの単一の部分で前記対象記録セットにのみ関連付けられている、当該関連付けるステップと、
前記複数のプロセッサのうちの少なくとも１つのプロセッサ上で、前記複数の記録セットの各々を、前記物理的に分離された複数のプロセッサセットのうち特定の１つの対象プロセッサセットに関連付けるステップと、
各記録を、前記関連付けられた記録セットに基づいて、それぞれの対象プロセッサセットに電子的にルーティングするステップと、
前記物理的に分離された複数のプロセッサセットによって前記記録を処理するステップと、
を備える方法。
【請求項２】
マルチプロセッサ環境において記録をデータベースに挿入する方法であって、
ルーティングノードにおいて、記録を受信するステップと、
前記ルーティングノードにおいて、各々が少なくとも一つの記録を含む複数の記録セットのうちの１つの対象記録セットに、各記録を、前記記録に含まれる識別用の記録番号および物理的に分離された複数のプロセッサセットの数に基づいて関連付けるステップであり、前記対象記録セットは、各記録を識別するための記録番号Ｒを前記複数のプロセッサセットの数Ｎで除算した余りの値により識別され、前記余りの値は前記対象記録セットの識別子に等しく、各記録は、前記データベースの単一の部分で前記対象記録セットにのみ関連付けられている、当該関連付けるステップと、
前記関連付けられた記録セットに基づいて前記記録を複数のプロセッサセットのうちの１つの対象プロセッサセットに電子的にルーティングするステップと、
前記プロセッサセットにおいて、一致する記録がないか前記データベースの一部分を探索するステップであって、前記データベースの前記一部分が前記プロセッサセットに関連付けられている、当該ステップと、
前記記録が前記データベースの前記一部分で見つけられない場合、前記記録を前記データベースの前記一部分に挿入するステップと、
を備える方法。
【請求項３】
前記複数のプロセッサセットの数Ｎは、２、３、４、６、８、１６のうち何れかである、
請求項１又は２に記載の方法。
【請求項４】
前記複数のプロセッサセットの数Ｎは、４から８までの間の値である、
請求項１又は２に記載の方法。
【請求項５】
前記方法は、
前記複数のプロセッサセットの各プロセッサセットのためのロギングキャッシュを作成するステップと、
それぞれのロギングキャッシュにおけるデータベーストランザクションをログするように、各プロセッサセット内の単一のプロセッサを割り当てるステップと、
をさらに備える、
請求項１又は２に記載の方法。
【請求項６】
前記方法は、
複数のサーバプロセスを作成するステップであって、各サーバプロセスが前記複数のプロセッサセットのうちの１つのプロセッサセットに関連付けられる、当該ステップと、
各サーバプロセスを１つの記録セットに関連付けるステップと、
をさらに備え、
各サーバプロセスが、前記関連付けられた記録セット内の記録を処理する、
請求項１又は２に記載の方法。
【請求項７】
前記方法は、
前記データベースを複数のＮ個のサブデータベースキャッシュに分割するステップと、
各サブデータベースキャッシュを前記複数のプロセッサセットの個々のプロセッサセットに関連付けるステップと、
をさらに備える請求項１又は２に記載の方法。
【請求項８】
各サブデータベースキャッシュは、関連付けられたプロセッサセットにローカルなメモリに常駐し、ここでの前記関連付けられたプロセッサセットに対する前記メモリのローカリティは、前記メモリと前記関連付けられたプロセッサセットとの間の電子距離を少なくとも根拠の一部として、決定される、
請求項７に記載の方法。
【請求項９】
各記録が、関連付けられる記録セット内の他の記録にのみ依存するように、前記各記録は前記記録セットに関連付けられる、
請求項１又は２に記載の方法。
【請求項１０】
各々が少なくとも一つのプロセッサを含む物理的に分離された複数のプロセッサセットにグループ化された複数のプロセッサを備えた装置であって、前記複数のプロセッサはデータベースに結合されており、前記プロセッサは前記データベース内の記録を処理するように構成されており、
前記装置は、
各々が少なくとも一つの記録を含む複数の記録セットのうちの１つの対象記録セットに、各記録を、前記記録に含まれる識別用の記録番号および前記物理的に分離された複数のプロセッサセットの数に基づいて関連付けるステップであり、前記対象記録セットは、各記録を識別するための記録番号Ｒを前記複数のプロセッサセットの数Ｎで除算した余りの値により識別され、前記余りの値は前記対象記録セットの識別子に等しく、各記録は、前記データベースの単一の部分で前記対象記録セットにのみ関連付けられている、当該関連付けるステップと、
前記複数の記録セットの各々を、前記物理的に分離された複数のプロセッサセットのうち１つの対象プロセッサセットに関連付けるステップと、
各記録を、前記関連付けられた対象記録セットに基づいて、それぞれの対象プロセッサセットに電子的にルーティングするステップと、
前記記録を処理するステップと、
を実行するように構成される装置。
【請求項１１】
ルーティングノード、及びデータベース内の記録を処理するように構成された複数のプロセッサセットにグループ化された複数のプロセッサを備える装置であって、
ルーティングノードにおいて、記録を受信し、
前記ルーティングノードにおいて、各々が少なくとも一つの記録を含む複数の記録セットのうちの１つの対象記録セットに、各記録を、前記記録に含まれる識別用の記録番号および物理的に分離された複数のプロセッサセットの数に基づいて関連付け、ここで、前記対象記録セットは、各記録を識別するための記録番号Ｒを前記複数のプロセッサセットの数Ｎで除算した余りの値により識別され、前記余りの値は前記対象記録セットの識別子に等しく、各記録は、前記データベースの単一の部分で前記対象記録セットにのみ関連付けられており、
前記関連付けられた記録セットに基づいて前記記録を前記複数のプロセッサセットのうちの１つの対象プロセッサセットに電子的にルーティングし、
前記プロセッサセットにおいて、一致する記録がないか前記プロセッサセットに関連付けられた前記データベースの一部分を探索し、
前記プロセッサセットにおいて、前記記録が前記データベースの前記一部分で見つけられない場合、前記記録を前記データベースの前記一部分に挿入する、
ように構成される装置。
【請求項１２】
前記複数のプロセッサセットの数Ｎは、２、３、４、６、８、１６のうち何れかである、
請求項１０又は１１に記載の装置。
【請求項１３】
前記複数のプロセッサセットの数Ｎは、４から８までの間の値である、
請求項１０又は１１に記載の装置。
【請求項１４】
前記装置は、
前記複数のプロセッサセットの各プロセッサセットのためのロギングキャッシュを作成し、
それぞれのロギングキャッシュにおけるデータベーストランザクションをログするように、各プロセッサセット内の単一のプロセッサを割り当てる、
ように、さらに構成される、
請求項１０又は１１に記載の装置。
【請求項１５】
前記装置は、
各サーバプロセスが前記複数のプロセッサセットのうちの１つのプロセッサセットに関連付けられる複数のサーバプロセスを作成し、
各サーバプロセスを記録セットに関連付ける、
ように、さらに構成され、
各サーバプロセスが前記関連付けられた記録セット内の記録を処理する、
請求項１０又は１１に記載の装置。
【請求項１６】
前記装置は、
前記データベースを複数のＮ個のサブデータベースキャッシュに分割し、
各サブデータベースキャッシュを前記複数のプロセッサセットの個々のプロセッサセットに関連付ける、
ように、さらに構成される請求項１０又は１１に記載の装置。
【請求項１７】
各サブデータベースキャッシュは、関連付けられたプロセッサセットにローカルなメモリに常駐し、ここでの前記関連付けられたプロセッサセットに対する前記メモリのローカリティは、前記メモリと前記関連付けられたプロセッサセットとの間の電子距離を少なくとも根拠の一部として、決定される、
請求項１６に記載の装置。
【請求項１８】
各記録が、関連付けられる記録セット内の他の記録にのみ依存するように、前記各記録は前記記録セットに関連付けられる、
請求項１０又は１１に記載の装置。
【請求項１９】
コンピュータに、
各々が少なくとも一つの記録を含む複数の記録セットのうちの１つの対象記録セットに、データベース内の各記録を、前記記録に含まれる識別用の記録番号および物理的に分離された複数のプロセッサセットの数に基づいて関連付ける手順であり、前記対象記録セットは、各記録を識別するための記録番号Ｒを前記複数のプロセッサセットの数Ｎで除算した余りの値により識別され、前記余りの値は前記対象記録セットの識別子に等しく、各記録は、前記データベースの単一の部分で前記対象記録セットにのみ関連付けられている、当該関連付ける手順と、
各記録を、前記対象記録セットに基づいて、各々が少なくとも一つのプロセッサを含む物理的に分離された複数のプロセッサセットのうち対象プロセッサセットそれぞれに電子的にルーティングする手順と、
前記記録を処理する手順と、
を実行させるように構成されるコード、を備えるコンピュータ可読非一時的記憶媒体。
【請求項２０】
コンピュータに、
ルーティングノードにおいて、記録を受信させる手順、
前記ルーティングノードにおいて、各々が少なくとも一つの記録を含む複数の記録セットのうちの１つの対象記録セットに、各記録を、前記記録に含まれる識別用の記録番号および物理的に分離された複数のプロセッサセットの数に基づいて関連付け、ここで、前記対象記録セットは、各記録を識別するための記録番号Ｒを前記複数のプロセッサセットの数Ｎで除算した余りの値により識別され、前記余りの値は前記対象記録セットの識別子に等しく、各記録は、データベースの単一の部分で前記対象記録セットにのみ関連付けられている、当該関連付けさせる手順、
前記関連付けられた記録セットに基づいて前記記録を複数のプロセッサセットのうちの１つのプロセッサセットにルーティングさせる手順、
前記プロセッサセットにおいて、一致する記録がないか前記プロセッサセットに関連付けられたデータベースの一部分を探索させる手順、および、
前記プロセッサセットにおいて、前記記録が前記データベースの前記一部分で見つけられない場合は前記記録を前記データベースの前記一部分に挿入させる手順、
を実行させるように構成されるコード、を備えるコンピュータ可読非一時的記憶媒体。
【請求項２１】
前記複数のプロセッサセットの数Ｎは、２、３、４、６、８、１６のうち何れかである、
請求項１９又は２０に記載のコンピュータ可読非一時的記憶媒体。
【請求項２２】
前記複数のプロセッサセットの数Ｎは、４から８までの間の値である、
請求項１９又は２０に記載のコンピュータ可読非一時的記憶媒体。
【請求項２３】
前記コンピュータ可読非一時的記憶媒体は、
コンピュータに、
前記複数のプロセッサセットの各プロセッサセットのためのロギングキャッシュを作成させる手順、および、
それぞれのロギングキャッシュにおけるデータベーストランザクションをログするように、各プロセッサセット内の単一のプロセッサを割り当てる手順、
を実行させることができるコード、をさらに備える、
請求項１９又は２０に記載のコンピュータ可読非一時的記憶媒体。
【請求項２４】
前記コンピュータ可読非一時的記憶媒体は、
コンピュータに、
各サーバプロセスが前記複数のプロセッサセットのうちの１つのプロセッサセットに関連付けられる複数のサーバプロセスを作成させる手順、および、
各サーバプロセスを１つの記録セットに関連付けさせる手順、
を実行させることができるコード、をさらに備え、
各サーバプロセスが、前記関連付けられた記録セット内の記録を処理する、
請求項１９又は２０に記載のコンピュータ可読非一時的記憶媒体。
【請求項２５】
前記コンピュータ可読非一時的記憶媒体は、
コンピュータに、
前記データベースを複数のＮ個のサブデータベースキャッシュに分割させる手順、および、
各サブデータベースキャッシュを前記複数のプロセッサセットの個々のプロセッサセットに関連付けさせる手順、
を実行させることができるコード、をさらに備える請求項１９又は２０に記載のコンピュータ可読非一時的記憶媒体。
【請求項２６】
各サブデータベースキャッシュは、関連付けられたプロセッサセットにローカルなメモリに常駐し、ここでの前記関連付けられたプロセッサセットに対する前記メモリのローカリティは、前記メモリと前記関連付けられたプロセッサセットとの間の電子距離を少なくとも根拠の一部として、決定される、
請求項２５に記載のコンピュータ可読非一時的記憶媒体。
【請求項２７】
各記録が、関連付けられる記録セット内の他の記録にのみ依存するように、前記各記録は前記記録セットに関連付けられる、
請求項１９又は２０に記載のコンピュータ可読非一時的記憶媒体。
【請求項２８】
複数のプロセッサ上でデータベース内の記録を処理するためのシステムであって、前記複数のプロセッサは前記データベースに結合されており、前記複数のプロセッサは各々が少なくとも一つのプロセッサを含む物理的に分離された複数のプロセッサセットにグループ化されており、
前記システムは、
前記複数のプロセッサのうちの少なくとも１つのプロセッサ上で、各々が少なくとも一つの記録を含む複数の記録セットのうちの１つの対象記録セットに、各記録を、前記記録に含まれる識別用の記録番号および物理的に分離された複数のプロセッサセットの数に基づいて関連付ける手段であり、前記対象記録セットは、各記録を識別するための記録番号Ｒを前記複数のプロセッサセットの数Ｎで除算した余りの値により識別され、前記余りの値は前記対象記録セットの識別子に等しく、各記録は、前記データベースの単一の部分で前記対象記録セットにのみ関連付けられている、当該関連付ける手段と、
前記複数のプロセッサのうちの少なくとも１つのプロセッサ上で、前記複数の記録セットの各々を、前記物理的に分離された複数のプロセッサセットのうち１つの対象プロセッサセットに関連付ける手段と、
各記録を、前記関連付けられた対象記録セットに基づいて、それぞれの対象プロセッサセットに電子的にルーティングする手段と、
前記複数のプロセッサセットによって前記記録を処理する手段と、
を備えるシステム。
【請求項２９】
物理的に分離された複数のプロセッサセットに結合されたデータベース内の記録を処理するシステムであって、
記録を受信する手段と、
各々が少なくとも一つの記録を含む複数の記録セットのうちの１つの対象記録セットに、各記録を、前記記録に含まれる識別用の記録番号および物理的に分離された複数のプロセッサセットの数に基づいて関連付ける手段であって、前記対象記録セットは、各記録を識別するための記録番号Ｒを前記複数のプロセッサセットの数Ｎで除算した余りの値により識別され、前記余りの値は前記対象記録セットの識別子に等しく、各記録は、前記データベースの単一の部分で前記対象記録セットにのみ関連付けられている、当該関連付ける手段と、
前記関連付けられた記録セットに基づいて前記記録を前記複数のプロセッサセットのうちの１つの対象プロセッサセットに電子的にルーティングする手段と、
前記プロセッサセットにおいて、一致する記録がないか前記プロセッサセットに関連付けられた前記データベースの一部分を探索する手段と、
前記プロセッサセットにおいて、前記記録が前記データベースの前記一部分で見つけられない場合、前記記録を前記データベースの前記一部分に挿入する手段と、
を備えるシステム。
【請求項３０】
前記複数のプロセッサセットの数Ｎは、２、３、４、６、８、１６のうち何れかである、
請求項２８又は２９に記載のシステム。
【請求項３１】
前記複数のプロセッサセットの数Ｎは、４から８までの間の値である、
請求項２８又は２９に記載のシステム。
【請求項３２】
前記システムは、
前記複数のプロセッサセットの各プロセッサセットのためのロギングキャッシュを作成するための手段と、
それぞれのロギングキャッシュにおけるデータベーストランザクションをログするように、各プロセッサセット内の単一のプロセッサを割り当てるための手段と、
をさらに備える、
請求項２８又は２９に記載のシステム。
【請求項３３】
前記システムは、
複数のサーバプロセスを作成するための手段であって、各サーバプロセスが前記複数のプロセッサセットのうちの１つのプロセッサセットに関連付けられる、当該手段と、
各サーバプロセスを１つの記録セットに関連付ける手段と、
をさらに備え、
各サーバプロセスが、前記関連付けられた記録セット内の記録を処理する、
請求項２８又は２９に記載のシステム。
【請求項３４】
前記システムは、
前記データベースを複数のＮ個のサブデータベースキャッシュに分割するための手段と、
各サブデータベースキャッシュを前記複数のプロセッサセットの個々のプロセッサセットに関連付けるための手段と、
をさらに備える請求項２８又は２９に記載のシステム。
【請求項３５】
各サブデータベースキャッシュは、関連付けられたプロセッサセットにローカルなメモリに常駐し、ここでの前記関連付けられたプロセッサセットに対する前記メモリのローカリティは、前記メモリと前記関連付けられたプロセッサセットとの間の電子距離を少なくとも根拠の一部として、決定される、
請求項３４に記載のシステム。
【請求項３６】
各記録が、関連付けられる記録セット内の他の記録にのみ依存するように、前記各記録は前記記録セットに関連付けられる、
請求項２８又は２９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
[0002]本開示は、一般に、マルチプロセッサコンピュータシステムに関し、より具体的には、マルチプロセッサコンピュータシステムにおいてデータをルーティングし処理するための方法及びシステムに関する。
【０００２】
［優先権の主張］
[0001]本出願は、２０１０年５月１７日に出願された米国仮特許出願第６１／３９５，７０４号、及び２０１１年４月８日に出願された米国特許出願第１３／０８３，３９６号の利益を主張するものであり、両方とも参照によりその全体が本明細書に組み込まれている。
【背景技術】
【０００３】
[0003]マルチプロセッサコンピュータシステムは、複数の並列プロセッサのコンカレント処理を可能にする。いくつかのアプリケーションは、マルチプロセッサコンピュータシステムにおいてプロセッサ間で効率よく並列化されることが可能である。例えば、いくつかのアプリケーションは、様々なタスクをスレッドと呼ばれるサブプロセスに分割することにより並列化されることが可能である。スレッドは、様々なデータに対する動作を同時に実行することができる。しかし、１つのスレッドは、別のスレッドの中間出力又は最終出力で動作する必要があるときもある。２つのスレッドは、他方のスレッドが情報を共有するのを待たなければならないことが多い場合は、高いデータ依存関係を有すると言われてもよい。逆に、他のスレッドからの情報を待つ必要がめったにない場合は、それらのスレッドは低いデータ依存関係を有すると言われてもよい。スレッド間に低いデータ依存関係を有するアプリケーションは、より長い期間より多くのデータを並列で処理することができるので望ましいことが多い。にもかかわらず、比較的多くのアプリケーションは、スレッド間に高いデータ依存関係を有する。これは、例えば、各データをデータセット内の他の各データと比較しなければならない場合に発生する可能性がある。したがって、データ依存関係が高い場合は、データセットのかなりの部分がメモリにアクセス可能である必要がある可能性がある。したがって、高いデータ依存関係を有する処理動作では、スレッド間でデータを伝送するプロセスは、計算をかなり遅らせる可能性がある。この遅延は、マルチプロセッサコンピュータシステムでは一般的であるように、各スレッドが物理的に別々のハードウェアノード上で動作している場合に激しくなることが多い。そのようなシステムでは、ノード間の入力／出力（ＩＯ）動作は、スループットとしても知られているシステムのデータ処理速度に対してかなりのボトルネックを引き起こす可能性があることが多い。メモリホップは、ローカルＣＰＵ／メモリセットにおいて不均一メモリアーキテクチャ（ＮＵＭＡ）を使用する１〜２ナノ秒ほどの小さいものから、様々なネットワークファブリックを介してストレージエリアネットワーク（ＳＡＮ）にアクセスする場合の数ミリ秒のものまである可能性がある。プロセッサはデータが配信されるのを待っている間はアイドルであることが多いので、スループットのボトルネックは、時間、エネルギー、及びメモリのかなりの無駄を表す可能性がある。
【０００４】
[0004]図１は、ネットワーク１３０によって相互に及び共用メモリ１４０に接続された複数のノード１２０を含むマルチプロセッサシステム１１０を示す。ノード１２０は、別々のメモリシステムを特徴とする論理的に個別の処理部品でもよい。いくつかの実装形態では、ノード１２０は、ローカルメモリストレージ機能及び処理機能を有するサーバなど、物理的に個別のシステムでもよい。図示されているシステム１１０では、Ｎ個のノード１２０がある。３個のノードしか示されていないが、ノード１２０はいくつあってもよい。各ノード１２０は、少なくとも１つのプロセッサ１５０及び１つのキャッシュ１６０を含む。１つのプロセッサ１５０しか示されていないが、各ノード１２０はプロセッサ１５０をいくつ含んでもよい。同様に、プロセッサ１５０はプロセッサコアをいくつ含んでもよい。プロセッサコアは、命令を独立して読み出し実行することができるプロセッサ１５０の部分を表す。したがって、１つの実施例では、２つのプロセッサコアが２つの処理スレッドを同時に実行することができる。いくつかの実装形態では、ノード１２０は、合計４個のプロセッサコアを含んでもよい。いくつかの実装形態では、ノード１２０は合計８個以上のプロセッサコアを含んでもよい。
【０００５】
[0005]マルチプロセッサシステム１１０などのマルチプロセッサシステムは、通常、大量のデータを処理する動作において使用される。例えば、２００７年に年間約２１２０億通を上回る最高物理的郵便量を扱った米国郵政公社は、大量データ処理の世界最大ユーザの１つである。各物理的郵便物は、自動装置上で複数回処理され、各自動イベントは、データスキャン記録を作成する。たとえ物理的郵便量が減少した場合でも、追加のトラッキングメトリック及び動作メトリックが郵便物ごとの郵便トラッキングスキャンの数を増大させてきた。したがって、毎日の郵便物のスキャン量は、４０億記録を超える可能性がある。これらの記録はそれぞれ、システム１１０などのマルチプロセッサシステムによって処理される。郵便記録が処理される場合、システムは何か月も経った数十億の前の記録と比較することにより重複記録を検出する。システムはまた、記憶容量に達した場合は、レポート作成及び他の同様のタスクのために郵便記録をクエリして、最も古い郵便記録を発見し除去する役割を担う。この実施例は、マルチプロセッサシステム１１０などのシステムにおいてデータ記録を効率よく処理する問題の大きさを示す。
【０００６】
[0006]マルチプロセッサシステムにおける処理は、行挿入動作を含んでもよい。従来、行挿入は、次のように実行されていた可能性がある。着信記録は、例えば負荷分散などの基準に基づいてノード１２０又は特定のプロセッサ１５０に並列でルーティングされる。例えば、１つの負荷分散法の下では、着信記録は、関連記録の位置のような要因を考慮することなく、ラウンドロビンベースで利用可能なプロセッサのセットから選ばれたプロセッサ１５０にルーティングされる。さらに、データベース挿入プロセスは、プロセッサ１５０上でスケジュールされる。次いで、プロセッサ１５０は、着信記録を受信するとすぐ、データベース内に記録がないか探索する。この探索はローカルキャッシュ１６０に記憶されていないデータにアクセスすることを必要とする可能性がある。そのような探索は、ストレージエリアネットワーク（ＳＡＮ）を含んでもよい。したがって、プロセッサ１５０は、必要なデータをリモートノード上に置き、そのデータを比較のためにネットワーク１３０を介してローカルノードに伝送する。いくつかの実装形態では、プロセッサ１５０は、着信記録をデータベース内の全ての記録と比較することができる。したがって、プロセッサ１５０は、かなりの量のデータをネットワーク１３０を介してローカルノードに伝送する。一致が見つけられなかった場合は、プロセッサ１５０は記録をデータベースに挿入する。
【０００７】
[0007]しかし、同時に、別のノード１２０上の別のプロセッサ１５０が異なる記録に対して同じタスクを同時に実行していることも推量される。したがって、２つのプロセッサ１５０が２つの一致する記録に対して動作して、同じメモリロケーションへの挿入を同時に試みることができるという可能性がある。これはレース状態と呼ばれてよく、次のように発生する可能性がある。最初に、第１のプロセッサが、第１の記録は一致を有しないと判定する。次に、第２のプロセッサが、第２の記録は一致を有しないと判定する。第１の記録及び第２の記録は一致してもしなくてもよいが、いずれもデータベースに首尾よく挿入されなかったことに留意されたい。続いて、第１のプロセッサは、第１の記録をデータベースに挿入する。最後に、すでに一致する記録がないと判定した第２のプロセッサが、第２の記録をデータベースに挿入する。レース状態によって同一の記録がデータベースに挿入されないことを保証するために、各プロセッサ１５０は、ロックなどの機構を介して挿入メモリロケーションへの排他的アクセス権を取得することができる。当技術分野ではいくつかの異なるロッキング機構が知られている。メモリロックを設定及び解除することは、それら自体、ネットワーク１３０を介してのデータ伝送を必要とする可能性がある。したがって、メモリブロックは、ロックされ、アンロックされ、比較的低速のネットワーク１３０を介して前後に伝送されるので、かなりの量の処理時間が浪費される可能性がある。
【０００８】
[0008]マルチプロセッサシステム１１０は、効率及び費用効果を改善するためにいくつかの技法を組み込むことができる。例えば、共用メモリ１４０は、階層的に構成されてもよい。階層型メモリ構成は、システム１１０が様々な性能及び費用特性を有するメモリ媒体の混合を利用することができるようにすることができる。したがって、システム１１０は、高優先順位のタスクのための少量のより高速の高価なメモリと他のタスクのための大量のより低速の安価なメモリとを同時に利用することができる。したがって、共用メモリ１４０は、複数の場所に分散されていてもよいいくつかの様々な記憶媒体と共に物理的に実装されてもよい。例えば、プロセッサ１５０は、めったに使用されないデータをストレージエリアネットワーク（ＳＡＮ、図示せず）において比較的安価で低速のディスクドライブ上に記憶することができる。同時に、共用メモリ１４０はまた、ノード１２０に部分的に分散されていてもよい。キャッシュ１６０は、共用メモリ１４０にデータのローカルコピー（キャッシュ）を入れてもよい。プロセッサ１５０は、データを比較的高速で高価なダイナミックランダムアクセスメモリ（ＤＲＡＭ、図示せず）にローカルにキャッシュすることができる。ＤＲＡＭは、処理モジュール上で他のプロセッサと共用されてもよい。通常、プロセッサ１５０は、より多くのデータを必要とする場合は、最初に、通常待ち時間が比較的短いローカルキャッシュ１６０の中を見る。例えば、ＤＲＡＭの待ち時間は、通常ナノ秒で測定される。見いだそうとするデータがローカルキャッシュにない場合は、メモリマネージャは、ネットワーク１３０を介してＳＡＮからデータを取り出さなければならない可能性がある。ＳＡＮは、遠く離れたところにある可能性があるので、メモリマネージャは、イーサネット（登録商標）などの比較的低速の相互接続を介してデータを要求しなければならない可能性がある。ＳＡＮ要求は、通常ミリ秒で測定する、ずっと長い待ち時間を有する。より低速の記憶媒体の追加の待ち時間と組み合わされた相互接続の相対速度は、データがローカルキャッシュで見つけられない（「キャッシュミス」の）場合は、かなりの性能低下を引き起こすことになることが多い。したがって、ほとんどのシステムは、頻繁にアクセスされる情報をローカルキャッシュに保持しようと試みる。
【０００９】
[0009]プロセスがシステム１１０などのマルチプロセッサコンピュータシステム上で動作する場合は、プロセスは通常次の利用可能なノード１２０上で動作するようにスケジュールされる。しかし、次の利用可能なノード１２０は、プロセスが最後に実行された同じノードでなくてもよい。前述のような階層型メモリモデルの下では、プロセスが最近アクセスしたデータは、プロセスが最後に実行されたノード上のキャッシュにある可能性がある。この傾向は、キャッシュの持続性と呼ばれてもよい。マルチプロセッサ環境においてキャッシュの持続性を利用するために、プロセスは、１つ又は複数のプロセッサへのアフィニティを割り当てられてもよい。そのようなアフィニティを与えられたプロセスは、いくつかのプロセッサ上で動作するように優先的にスケジュールされる。したがって、アフィニティ化されたプロセスは、そのローカルキャッシュに重要なプロセス情報をすでに有するプロセッサ上で動作する可能性がより大きい。しかし、アフィニティは、とりわけアプリケーションがスレッド間の高いデータ依存関係を有する場合は、キャッシュミスの問題を除去しない。キャッシュミスは、共用メモリ１４０がノード１２０に部分的に分散されているシステムに存続する可能性がある。そのようなシステムの一例は、ノード１２０に分散されている共用メモリ１４０間の整合性を維持するキャッシュコヒーレントシステムと呼ばれる。キャッシュコヒーレントシステムでは、例えば、アフィニティ化されたプロセッサは、着信データを別のノード１２０上で前に処理されたデータと比較するようにプログラムされてもよい。アフィニティ化されたプロセスはまた、そのデータを修正するようにプログラムされてもよい。メモリの整合性を維持するために、データは通常ノード１２０間で伝送される。したがって、たとえ処理されるべきデータの多くがローカルキャッシュ１６０に含まれている可能性があっても、ノード１２０間のデータ伝送は、高いデータ依存関係のために、それでもなおかなりのスループットのボトルネックを示す可能性がある。
【００１０】
[0010]通常、前述のようなＵＳＰＳメールシステムなどのシステムは、実用的な最速ハードウェアをすでに使用している。したがって、例えばより高速のネットワーク１３０に関してスループットのボトルネックを除去することは実行不可能である。同様に、ボトルネックはノード１２０間で発生するので、別のノードを追加することはスループットの所望の増大をもたらさない。同時に、着信データの伝送速度を低減することは、通常は実行可能な選択肢ではない。例えば、郵政公社が、コンピュータのボトルネックに対応するために、郵便又は関連報告を遅らせることは多分受け入れられない。そのようなシステムの中では、メモリのローカリティは、メモリの「電子距離」又は電子がメモリに到達するために電気経路を進まなければならない距離によって左右される。例えば、ローカルキャッシュ１６０にアクセスするプロセッサ１５０は、およそ数ミリメートルの「電子距離」を有してもよい。他方、別のノード１２０上にあるメモリに、又はＳＡＮを介してメモリにアクセスするプロセッサ１５０は、およそ数メートルの「電子距離」を有してもよい。したがって、システムアーキテクチャレベルでボトルネックを解決することが望ましい。この問題を解決しようと試みる場合、スループットの限界をリモートデータアクセスの必要に起因すると考えてきたものもある。しかし、本明細書に記載のシステム及び方法は、このリモートデータアクセスのボトルネックに予期しないやり方で対処することができる。
【発明の概要】
【００１１】
[0011]開発のシステム、方法、及びデバイスは、それぞれいくつかの態様を有し、それらのうちの単一の態様は、その望ましい属性に単独で責任を負うことはない。次に、本開示の範囲を限定することなく、本開示のより顕著な特徴が簡単に説明される。この説明を考慮した後には、とりわけ「発明を実施するための形態」という表題の節を読んだ後には、本開示の特徴が他の方法及び／又はデバイスより優れた利点をどのように提供するかが理解されるであろう。
【００１２】
[0012]一態様によれば、データベース内の記録を処理する方法が提供される。記録は、複数のプロセッサセットにグループ化された複数のプロセッサ上で処理される。本方法は、各記録を複数の記録セットのうちの１つの記録セットに関連付けるステップと、各記録セットを１つのプロセッサセットに関連付けるステップと、関連付けられた記録セットに基づいて記録をプロセッサセットにルーティングするステップと、プロセッサセットで記録を処理するステップとを含む。
【００１３】
[0013]他の態様によれば、装置が提供される。本装置は、複数のプロセッサセットにグループ化された複数のプロセッサを備える。プロセッサセットは、データベース内の記録を処理するように構成される。本装置は、各記録を複数の記録セットのうちの１つの記録セットに関連付け、各記録セットを１つのプロセッサセットに関連付け、関連付けられた記録セットに基づいて記録をプロセッサセットにルーティングし、記録を処理するように構成される。
【００１４】
[0014]他の態様によれば、コンピュータ可読非一時的記憶媒体が提供される。本コンピュータ可読非一時的記憶媒体は、コンピュータにデータベース内の各記録を複数の記録セットのうちの１つの記録セットに関連付けさせ、各記録セットを１つのプロセッサセットに関連付けさせ、関連付けられた記録セットに基づいて記録をプロセッサセットにルーティングさせ、記録を処理させることができるコードを備える。
【００１５】
[0015]他の態様によれば、マルチプロセッサ環境において記録をデータベースに挿入する方法が提供される。本方法は、ルーティングノードにおいて記録を受信するステップを含む。本方法は、ルーティングノードにおいて、記録を複数の記録セットのうちの１つの記録セットに関連付けるステップをさらに含む。本方法は、関連付けられた記録セットに基づいて記録を複数のプロセッサセットのうちの１つのプロセッサセットにルーティングするステップをさらに含む。本方法は、プロセッサセットにおいて、一致する記録がないかデータベースの一部分を探索するステップをさらに含む。データベースの一部分は、プロセッサセットに関連付けられる。本方法は、記録がデータベースの一部分で見つけられない場合は、記録をデータベースの一部分に挿入するステップをさらに含む。
【００１６】
[0016]他の態様によれば、装置が提供される。本装置は、ルーティングノード及び複数のプロセッサセットにグループ化された複数のプロセッサを備える。プロセッサセットは、データベース内の記録を処理するように構成される。本装置は、ルーティングノードにおいて、記録を受信するように構成される。本装置は、ルーティングノードにおいて、記録を複数の記録セットのうちの１つの記録セットに関連付けるようにさらに構成される。本装置は、関連付けられた記録セットに基づいて記録を複数のプロセッサセットのうちの１つのプロセッサセットにルーティングするようにさらに構成される。本装置は、プロセッサセットにおいて、一致する記録がないかデータベースの一部分を探索するようにさらに構成され、データベースの一部分はプロセッサセットに関連付けられる。本装置は、プロセッサセットにおいて、記録がデータベースの一部分で見つけられない場合は、記録をデータベースの一部分に挿入するようにさらに構成される。
【００１７】
[0017]他の態様によれば、コンピュータ可読非一時的記憶媒体が提供される。本コンピュータ可読非一時的記憶媒体は、コンピュータに、ルーティングノードにおいて、記録を受信させることができるコードを備える。コードはさらに、ルーティングノードにおいて、コンピュータに記録を複数の記録セットのうちの１つの記録セットに関連付けさせることができる。コードはさらに、コンピュータに関連付けられた記録セットに基づいて記録を複数のプロセッサセットのうちの１つのプロセッサセットにルーティングさせることができる。コードはさらに、コンピュータに、プロセッサセットにおいて、一致する記録がないかデータベースの一部分を探索させることができ、データベースの一部分はプロセッサセットに関連付けられる。コードはさらに、コンピュータに、プロセッサセットにおいて、記録がデータベースの一部分で見つけられない場合は、記録をデータベースの一部分に挿入させることができる。
【００１８】
[0018]一態様によれば、データベース内の記録を処理するためのシステムが提供される。記録は、複数のプロセッサセットにグループ化された複数のプロセッサ上で処理される。本システムは、各記録を複数の記録セットのうちの１つの記録セットに関連付けるための手段と、各記録を１つのプロセッサセットに関連付けるための手段と、関連付けられた記録セットに基づいて記録をプロセッサセットにルーティングするための手段と、記録をプロセッサセットで処理するための手段とを備える。
【図面の簡単な説明】
【００１９】
【図１】マルチプロセッサコンピュータシステムのブロック図である。
【図２】一実施形態によるデータを処理するように構成されたマルチプロセッサコンピュータシステムのブロック図である。
【図３】他の実施形態によるデータを処理するための方法の流れ図である。
【図４】他の実施形態による記録をデータベースに挿入するための方法の流れ図である。
【図５】他の実施形態によるデータ処理スループットを示すグラフである。
【発明を実施するための形態】
【００２０】
[0024]図１を参照すると、一実施形態では、本開示の特徴が実装されるマルチプロセッサコンピュータシステム１１０は、Ｏｒａｃｌｅ（登録商標）ＴｉｍｅｓＴｅｎ（５００  Ｏｒａｃｌｅ  Ｐａｒｋｗａｙ，Ｒｅｄｗｏｏｄ  Ｓｈｏｒｅｓ，ＣＡ９４０６５）インメモリデータベースを実行するＳＧＩ（登録商標）Ａｌｔｉｘ（登録商標）４７００（Ｓｉｌｉｃｏｎ  Ｇｒａｐｈｉｃｓ，Ｉｎｃ．，４６６００  Ｌａｎｄｉｎｇ  Ｐａｒｋｗａｙ，Ｆｒｅｍｏｎｔ，ＣＡ９４５３８）モジュラブレードプラットフォームを含む。他の実施形態では、本開示の特徴が実装されるマルチプロセッサコンピュータシステム１１０は、ＳＧＩ（登録商標）Ｕｌｔｒａ  Ｖｉｏｌｅｔ（登録商標）（Ｓｉｌｉｃｏｎ  Ｇｒａｐｈｉｃｓ，Ｉｎｃ．，４６６００  Ｌａｎｄｉｎｇ  Ｐａｒｋｗａｙ，Ｆｒｅｍｏｎｔ，ＣＡ９４５３８）を含む。プラットフォームは、ノード１２０をいくつ含んでもよい。各ノード１２０は、プロセッサ１５０をいくつ含んでもよい。一実施形態によれば、ノード１２０ごとに約１個から約３２個までの間のプロセッサ１５０がある。他の実施形態では、ノード１２０ごとに約４個から約８個までの間のプロセッサ１５０があり、より特定的にはノード１２０ごとに約４個のプロセッサ１５０がある。本明細書では特定のデータベース、アプリケーション、及びハードウェアに関連して様々な実施形態が説明されるが、本開示は様々な構成に適用可能であることを当業者は理解するであろう。
【００２１】
[0025]マルチプロセッサコンピュータシステム１１０は、記録を読み出し、それらの記録を行及び列を有するテーブルに構成されたデータベースに挿入するように構成されてもよい。一実施形態では、マルチプロセッサコンピュータシステム１１０は、着信記録を読み出し、データベースにおいて記録を探索し、記録がデータベースで見つけられない場合は記録をデータベースに挿入することにより行挿入を実行するように構成される。他の実施形態では、マルチプロセッサコンピュータシステム１１０は、エイジング期間より古い記録がないかデータベースを探索し、それらの記録を除去するようにさらに構成される。様々な実施形態では、エイジング期間は、約５日から約１４日までの間、より特定的には約５日から７日までの間、さらにより特定的には約５日である。代替実施形態では、マルチプロセッサコンピュータシステム１１０は、データベース内の記録数に対する制限を維持するために古い記録を除去するように構成される。他の実施形態では、マルチプロセッサコンピュータシステム１１０は、データベースのサイズに対する制限を維持するために古い記録を除去するように構成される。例えば、インメモリデータベース（ＩＭＤＢ）は、１８０日から６年までの間の分の記録を表す７．５ＴＢの記録を含んでもよい。
【００２２】
[0026]図２を参照すると、記録処理システム２００が示されている。記録処理システム２００は、例えば図１に関して上記で説明された行挿入プロセスなどのプログラムを実行する場合に必要とされる待ち時間の長いネットワーク動作の数を低減するように構成されてもよい。記録処理システム２００は、例えば図１に示されているマルチプロセッサコンピューティングシステム１１０などのマルチプロセッサコンピューティングシステムと共に実装されてもよい。
【００２３】
[0027]記録処理システム２００では、着信データ２１０は、そのプロセッサアフィニティを判定するためにアフィニティプロセス２２０によって解析される。アフィニティプロセス２２０は、着信データ２１０をＣＰＵアフィニティ層２３０に割り当てるのに役立つ。ＣＰＵアフィニティ層２３０は、図１に関して上記で説明されたようなノード１２０又はプロセッサ１５０に対応してもよい。アフィニティプロセス２２０は、例えば記録数などのデータのプロパティに基づいて、着信データ２１０をＣＰＵアフィニティ層２３０に割り当てることができる。一実施形態では、着信データ２１０は記録数を含み、アフィニティプロセス２２０は、記録数に対してモジュロＮ（Ｎはシステム内のＣＰＵアフィニティ層２３０の数）をとることにより、着信データ２１０をＣＰＵアフィニティ層２３０に割り当てる。他の実施形態では、アフィニティプロセス２２０は、例えば安全なハッシュアルゴリズム（ＳＨＡ）を使用することによりデータのハッシュに基づいて着信データ２１０を割り当てる。データベースキャッシュ２４０は、各ＣＰＵアフィニティ層２３０に関連付けられる。
【００２４】
[0028]アフィニティプロセス２２０が着信データ２１０をＣＰＵアフィニティ層２３０に割り当てる基準は、ＣＰＵアフィニティ層２３０に割り当てられた着信データ２１０の処理が同じＣＰＵアフィニティ層２３０に割り当てられた他のデータにしか依存しないように選ばれてもよい。言い換えれば、所与のＣＰＵアフィニティ層２３０に割り当てられた着信データ２１０は、ローカルに依存していると言われてもよい。したがって、着信データ２１０を処理するＣＰＵアフィニティ層２３０は、ローカルキャッシュにおいて必要とされる他のデータを見つける可能性がより大きい。例えば、一実施形態では、アプリケーションは、前述の行挿入プロセスでもよい。その実施形態では、データベースは、Ｎ個の部分に分割されてもよく、ここで、ＮはＣＰＵアフィニティ層２３０の数である。各データベース部分は、ＣＰＵアフィニティ層２３０に関連付けられる。したがって、データベースキャッシュ２４０は、対応するＣＰＵアフィニティ層２３０に関連付けられたデータベース部分からの記録しか含む必要がない。一実施形態では、データベースキャッシュ２４０は、関連付けられたデータベース部分を完全にキャッシュするのに十分大きい。したがって、データベースキャッシュ２４０が少なくとも関連付けられたデータベース部分と同じほど大きい実施形態では、ＣＰＵアフィニティ層２３０は、全ての必要なデータへの比較的短い待ち時間アクセスを有することができる。
【００２５】
[0029]さらに、待ち時間は、アフィニティ化プロセス中にアフィニティ層２３０におけるＣＰＵとデータベースキャッシュ２４０との間の「電子距離」を考慮することにより低減されることが可能である。例えば、ＣＰＵから（同じノード上の）「ローカル」メモリＤＩＭＭへのホップは、ＳＧＩ  Ａｌｔｉｘ４７００では、通常、１０ｎｓかかる。同じラックユニットにおけるブレード間のホップは、通常、２２ｎｓかかり、異なるラックにおけるブレード間のホップは、通常、３３ｎｓから２５６ｎｓまでの間かかる。ＮＵＭＡから追加のラックまでのホップは、通常、２５６ｎｓを超え、メモリが増えるにつれて幾何級数的に増える可能性がある。アフィニティプロセス２２０は、着信データ２１０がそれを処理するＣＰＵまでの短い「電子距離」を有するメモリロケーションにある可能性を増大させるためにこの「電子距離」を考慮に入れることができる。
【００２６】
[0030]着信データ２１０記録は、前述のように決定論的なやり方でデータベースに割り当てられてもよい。ＣＰＵアフィニティ層２３０は、ローカルデータベースキャッシュ２４０に記憶されているデータベース部分を探索する必要があるだけなので、ネットワークを介してリモートメモリにアクセスする必要がない。したがって、この実施例では、着信データ２１０記録は、データベース探索のためにアクセスされる任意の２つの記録が同じＣＰＵアフィニティ層２３０に割り当てられる点で、ローカルに従属的であるだけである。たとえＣＰＵアフィニティ層２３０がメモリロッキングを実行する必要があるとしても、ローカルメモリのロッキングは、ネットワーク伝送の必要がないので、リモートメモリのロッキングよりずっと速い可能性がある。記録処理システム２００を構成することができるやり方が図３に示されている。
【００２７】
[0031]図３は、一実施形態による、例えば図２に関して上記で説明された着信データ２１０などの着信データを処理する方法３００を示す。方法３００は、例えば、図１に関して上記で論じられたように、マルチプロセッサコンピュータシステム１１０上で実施されてもよい。最初に、ブロック３１０に関して、システム内のプロセッサがＮ個のプロセッサセットにグループ化される。したがって、各プロセッサセットは１つ又は複数のプロセッサを含む。各プロセッサセットは、例えば、図１に関して上記で説明されたノード１２０などのノードに対応してもよい。一実施形態では、各プロセッサセットは、図２に関して上記で説明されたＣＰＵアフィニティ層２３０に対応する。
【００２８】
[0032]続いてブロック３２０に進むと、データベースがＮ個の部分に分割される。各部分はサブデータベースでもよい。一実施形態によれば、各部分は単一のデータベース内のテーブルである。他の実施形態では、各サブデータベースは、せいぜい処理中にローカルに従属的であるデータを保持するように構成されてもよい。例えば、処理機能が列挿入である一実施形態では、偶数の記録数を有する全てのデータが単一のデータベースに割り当てられてもよい。一実施形態では、Ｎは約２から約１６までの間である。他の実施形態では、Ｎは約４から８までの間であり、より特定的には約６である。
【００２９】
[0033]ブロック３３０に移ると、Ｎ個のデータベースキャッシュが作成される。各データベースキャッシュは、１つのプロセッサセットに関連付けられる。一実施形態では、データベースキャッシュは、図２に関して上記で説明されたデータベースキャッシュ２４０に対応する。有利には、一実施形態では、データベースキャッシュは、全サブデータベースを記憶するのに十分に大きい。したがって、関連付けられたプロセッサセットは、キャッシュミスを経験するとしてもごくまれにしか経験しない。データベースキャッシュは、関連付けられているプロセッサセットにローカルなメモリにしか常駐しないように構成されてもよい。前述のように、ローカリティは、メモリとプロセッサとの間の「電子距離」に関して判定されることが可能である。したがって、データベースキャッシュは、アフィニティ化されたプロセッサへの短い「電子距離」を有する物理的メモリロケーションに割り当てられることが可能である。
【００３０】
[0034]同様に、ブロック３４０に関して、Ｎ個のロギングキャッシュが作成される。前述のデータベースキャッシュのように、各ロギングキャッシュは１つのプロセッサセットに関連付けられる。一実施形態では、プロセッサセット内の単一のプロセッサは、ロギングキャッシュへのデータベースロギングを実行するように割り当てられてもよい。その実施形態では、ロギングはローカルに行われるので、ロギングキャッシュミスを待っている間にローカルプロセスが止まる機会はより少ない。ロギングキャッシュは、関連付けられているプロセッサセットにローカルなメモリにしか常駐しないように構成されてもよい。前述のように、ローカリティは、メモリとプロセッサとの間の「電子距離」に関して判定されることが可能である。したがって、データベースキャッシュは、アフィニティ化されたプロセッサへの短い「電子距離」を有する物理的メモリロケーションに割り当てられることが可能である。
【００３１】
[0035]続いて、ブロック３５０に関して、プロセッサアフィニティがＭ個のサーバプロセスをＮ個のプロセッサセットに関連付けることにより作成される。様々な実施形態では、Ｍは、Ｎ、Ｎの倍数、又は何らかの他の関係に等しくてもよい。前述のように、そのようなアフィニティを与えられたプロセスは、いくつかのプロセッサ上で動作するように優先的にスケジュールされてもよい。一実施形態では、サーバプロセスは、着信データでのデータベース行挿入を実行するように構成される。サーバプロセスは、関連付けられたプロセッサセット上で動作するように優先的にスケジュールされるので、そのプロセスに関するデータ（プロセスコンテキストなど）が、プロセスが動作する時間の間に保存されるより大きな機会がある。一実施形態では、各サーバプロセスは、常に同じプロセッサセット上で動作する。したがって、プロセスは常に同じプロセッサセット上で動作するので、常に同じデータベースキャッシュ及び／又はロギングキャッシュを使用する。この構成はキャッシュミスの可能性をさらに低減することができる。
【００３２】
[0036]ブロック３６０に進むと、データがＮ個のデータセットに分割される。一実施形態では、データは、図２に関して上記で説明された着信データ２１０である。同様に、図２におけるアフィニティプロセス２２０に関して上記で論じられたように、データは、例えばデータに含まれている記録数のモジュロに基づいてセットに分割されてもよい。例えば、２つのプロセッサセットを有するマルチプロセッサコンピューティングシステムでは、偶数の記録数を含むデータは、第１のデータセットに割り当てられてもよく、奇数の記録数を含むデータは、第２のデータセットに割り当てられてもよい。各データセットは、１つのプロセッサセットに関連付けられる。前述のように、データは、ターゲットアプリケーションに関してデータセット間にほとんど又は全然従属関係がないデータセットに分割されてもよい。
【００３３】
[0037]次いで、ブロック３７０に関して、データは、関連付けられたプロセッサセットにルーティングされる。例えば、２つのプロセッサセットを有するマルチプロセッサコンピューティングシステムを含む一実施形態では、偶数の記録数を含むデータは、第１のプロセッサセットにルーティングされてもよく、奇数の記録数を含むデータは、第２のプロセッサセットにルーティングされてもよい。このようにして、データアフィニティが作成される。さらに、前述のサーバプロセス及びキャッシュアフィニティによって、各プロセッサセットはまた、少なくとも１つのサーバプロセス及びキャッシュに関連付けられる。したがって、サーバプロセスがデータベース行挿入を実行するように構成された諸実施形態では、サーバプロセスは、ローカルキャッシュからコンテキストを回復し、ローカルデータベースキャッシュだけを使用して関連サブデータベース上で行挿入を実行することができる可能性がある。したがって、キャッシュミスの可能性が低減され、データ処理スループットが向上する。
【００３４】
[0038]図４は、他の実施形態による記録をデータベースに挿入するための方法４００の流れ図である。例示されている流れ図は、図３に関して上記で論じられたように、Ｎ＝２で確立された処理環境を想定している。言い換えれば、利用可能なプロセッサは、２つのプロセッサセット、即ちプロセッサセット０及びプロセッサセット１に分割されている。同様に、記録データベースは、２つの部分、即ちデータベース部分０及びデータベース部分１に分割されている。さらに、２つのデータベースキャッシュ及び２つのロギングキャッシュがある。他の実施形態では、Ｎは、例えば、３、４、６、８、１６など、いかなる数でもよい。
【００３５】
[0039]ブロック４１０から開始すると、ルーティングユニットが記録を受信する。いくつかの実施形態では、記録は、郵便料金を認証するために使用される許可指示又は情報ベースの指示（ＩＢＩ）でもよい。ルーティングユニットは、ルーティング、要求に基づいて任意の利用可能なプロセッサ上で動作するようにスケジュールされたルーティングプロセス、又は任意の他の構成を処理するように割り当てられた単一のプロセッサでもよい。記録は、記録を２つ以上のセットに分離することができるようにする区別可能な特徴を有する。例示された実施形態では、記録は偶数又は奇数どちらかの数を含む。
【００３６】
[0040]続いてブロック４２０に進むと、記録は２つのデータセット、即ち偶数又は奇数のうちの１つに関連付けられる。記録数が偶数である場合は、偶数のデータセットに割り当てられ、記録数が奇数である場合は、奇数のデータセットに割り当てられる。上記で論じられたように、記録を記録セットに割り当てるには多くのやり方があることを当業者は理解するであろう。本明細書に記載され図３に例示されている偶数のデータセット及び奇数のデータセットは、簡単にするために選ばれた例である。各データセットは１つのプロセッサセットに関連付けられる。具体的には、偶数のデータセットはプロセッサセット０に関連付けられ、奇数のデータセットはプロセッサセット１に関連付けられる。
【００３７】
[0041]ブロック４３０及び４３５に移ると、記録はそのデータセットに関連付けられたプロセッサセットにルーティングユニットによってルーティングされる。具体的には、記録が偶数である場合は、記録はブロック４３０においてプロセッサセット０にルーティングされる。代替として、記録が奇数である場合は、記録はブロック４３５においてプロセッサセット１にルーティングされる。記録は、そのプロセッサセットの１つ又は複数のプロセッサにアフィニティ化されたプロセススレッドに記録を送信することにより、プロセッサセットにルーティングされてもよい。したがって、プロセスはプロセッサセット内の任意のプロセッサ上でスケジュールされてもよいが、記録は特定の関連付けられたプロセッサセットによって処理されるように保証されることが可能である。
【００３８】
[0042]続いて、ブロック４４０及び４４５において、記録を処理するように割り当てられた、関連付けられたプロセッサセットは、一致する記録がないか関連付けられたデータベース部分を探索する。具体的には、記録が偶数である場合は、プロセッサセット０上で動作しているプロセスは、ブロック４４０において、一致する記録がないかデータベース部分０を探索する。代替として、記録が奇数である場合は、プロセッサセット１上で動作しているプロセスは、ブロック４４５において、一致する記録がないかデータベース部分１を探索する。一実施形態では、一致する記録がないかデータベース部分を探索するステップは、データベース部分内の各行を読み出すサブステップと、その行内の記録数を着信記録と比較するサブステップとを含んでもよい。他の実施形態では、一致する記録がないかデータベース部分を探索することは、例えば二分探索などの他の知られている探索方式を含んでもよい。各記録は関連データベース部分への挿入のために関連プロセッサセットにルーティングされる記録セットに関連付けられるので、探索アルゴリズムは、データベース部分０には偶数の記録しか存在せず、データベース部分１には奇数の記録しか存在しないと仮定することができる。したがって、プロセッサセット０上で動作している探索アルゴリズムは、データベース部分０を探索するだけでよく、データベース部分１にアクセスする必要がない（逆も同様）。したがって、本明細書に記載の方法は、プロセッサセットがローカルメモリだけにアクセスすることにより、全てのプロセッサセットにわたって配置されている全てのデータベース部分を効率よく探索することができるようにする。
【００３９】
[0043]次に、ブロック４５０及び４５５において、記録が関連データベース部分にすでに存在するかどうかに応じて適切な動作が取られる。記録が存在する場合は、記録はブロック４６０において廃棄される。いくつかの実施形態では、記録はさらなる検討のためにフラグを立てられてもよい。例えば、記録が、一意であると予期される郵便料金認可を表す実施形態では、プロセスは、送信元コンピュータに未納郵便料金を示すネットワークメッセージを送信することができる。しかし、記録が関連データベース部分で見つけられない場合は、記録はブロック４７０及び４７５において関連データベースに挿入される。具体的には、記録が偶数である場合は、記録は、ブロック４７０においてデータベース部分０に挿入される。代替として、記録が奇数である場合は、記録は、ブロック４７５においてデータベース部分１に挿入される。多くのデータベースは行及び列に構成されているので、関連データベース部分への記録の挿入は、行挿入と呼ばれてもよい。行挿入は、全てローカルデータベースキャッシュ上で実行されることが可能なので、本明細書に記載の方法によって比較的迅速に実行されることが可能である。ローカルデータベースキャッシュがプロセッサセットに関連付けられた全データベース部分を保持するのに十分に大きい場合は、行挿入は、リモートロッキング、ネットワークトラフィックなどの必要なしに、実行されることが可能である。
【００４０】
[0044]図５は、前述のシステム及び方法の一実施形態を使用して達成されるデータベース行挿入スループットを示すグラフである。行挿入は、６個のデータベースキャッシュを有する６個のプロセッサセットを使用して実行された。プロセッサセットは、「ＴＲＰ１〜６」と表示される。各プロセッサセットは、４個のプロセッサを含んだ。各プロセッサセットはまた、３個のデータベース挿入スレッドに関連付けられ、各データベース挿入スレッドは、図４に関して上記で説明されたものと同様のプロセスを実行した。言い換えれば、各プロセッサセット内の４個のプロセッサのうちの３個は、本明細書に記載の行挿入方法の一実施形態を実行するソフトウェアを実行した。各プロセッサセット内の１つのプロセッサがデータベースロギングスレッドを実行した。
【００４１】
[0045]図５に示されているように、６個の線は、各プロセッサセットＴＲＰ１〜６によって１秒毎に実行された行挿入の数を表す。「合計」と表示された追加の線は、６個のプロセッサセットＴＲＰ１〜６全てにわたる１秒毎の累積行挿入を表す。グラフに示されているように、プロセッサセットは、１秒毎の行挿入の数の低下を引き起こした比較的少数のキャッシュミスに遭遇した。例えば、１５：０２：２７、１６：５２：３８、及び１７：０２：３９頃に、毎秒の合計行挿入に瞬間的降下がある。これらの瞬間的降下は、必要とされるデータがローカルノード上に存在しなかったので、プロセッサセットがネットワークトラフィックを待たなければならなかった時間、又は複数のローカル待ち時間を生じさせるノードにわたるホップを表す可能性がある。しかし、ほとんどの部分では、本明細書に記載の方法は、行挿入動作中にリモートデータにアクセスする必要を事実上なくしたので、各プロセッサセットのスループットはなだらかである。
【００４２】
[0046]上記のプロセス及び方法は、上記ではいくつかのステップを含むと記載され、特定の順序で記載されているが、これらのプロセス及び方法は、追加のステップを含んでもよく、又は記載されたステップのいくつかを省略してもよいことが理解されるべきである。さらに、プロセスのステップのそれぞれは、必ずしも記載されている順序で実行される必要はない。
【００４３】
[0047]上記の説明は、様々な実施形態に適用される本発明の新規特徴を示し、記述し、指摘してきたが、例示されたシステム又はプロセスの形態及び詳細における様々な省略、代替、並びに変更が本発明の趣旨から逸脱することなく当業者によって行われてもよいことが理解されるであろう。理解されるように、いくつかの特徴は他の特徴とは別に使用又は実行されてもよいので、本発明は、本明細書で説明された特徴及び利益の全てを提供するわけではない形態の範囲内で実施されてもよい。
【００４４】
[0048]本明細書で開示された諸実施形態に関連して説明された方法又はアルゴリズムのステップは、ハードウェア、プロセッサによって実行されるソフトウェアモジュール、又はこれら２つの組合せで直接実施されてもよい。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、取外し可能なディスク、ＣＤ−ＲＯＭ、又は当技術分野で知られている任意の他の形態の記憶媒体に常駐してもよい。例示的記憶媒体は、プロセッサが記憶媒体から情報を読み出し、記憶媒体に情報を書き込むことができるようにプロセッサに結合される。代替実施形態では、記憶媒体は、プロセッサに組み込まれていてもよい。プロセッサ及び記憶媒体は、ＡＳＩＣに常駐してもよい。ＡＳＩＣは、ユーザ端末に常駐してもよい。代替実施形態では、プロセッサ及び記憶媒体は、ユーザ端末に個別部品として常駐してもよい。
【図１】
2020115367.tif 000003
【図２】
2020115367.tif 000004
【図３】
2020115367.tif 000005
【図４】
2020115367.tif 000006
【図５】
2020115367.tif 000007
【外国語明細書】
2020115367000001.pdf