(57)【要約】  データ集合を分散処理することが、分散処理システムを構成するための情報を受信することを含む。計算資源（１９０〜１９４）間で分散されるデータ要素のソース（１１０）及びデータ要素を処理するように構成されるワーカ（２４０）を含む第１のコンポーネント構成が形成される。各データ要素は、パーティション規則に従ってワーカのサブセットを識別するパーティション値を含む。第１の処理エポック内でデータ集合の第１の部分についてソースからデータ要素が受け付けられ、それらのデータ要素は第１の構成によってルーティングされる。データ集合の第１の部分を受け付けた後、第２の構成への構成の変更が開始される。一連の修正された構成へのコンポーネント構成間の一連の２回以上の遷移が行われ、修正された構成の最後のものは第２の構成に対応する。第２の処理エポック内で更なるデータ要素が第２の構成のソースから受け付けられる。
2019517065.tif 000002
【特許請求の範囲】
【請求項１】
データ集合を分散処理するための方法であって、
分散処理システムを構成するための情報を入力装置又はポート上で受信するステップであって、前記構成することは前記分散処理システムの第１のコンポーネント構成を形成することを含み、前記第１の構成は前記データ集合のデータ要素の複数のソース及び前記データ集合のデータ要素を処理するように構成される複数のワーカを含み、前記ソース及びワーカは複数の計算資源間で分散され、各データ要素は前記第１の構成のパーティション規則に従って前記第１の構成の前記複数のワーカのサブセットを識別するパーティション値を含む、受信するステップと、
少なくとも２つの処理エポック中に前記分散処理システム内でデータを処理するステップであって、
第１の処理エポック内で前記データ集合の第１の部分について前記ソースからデータ要素を受け付け、前記データ要素を前記第１の構成によってルーティングし、前記データ要素の少なくとも一部の処理を完了することであって、前記第１の部分の前記データ要素の残りは前記第１の構成のコンポーネントにおいて待ち行列に入ったままである、前記完了すること、
前記データ集合の第１の部分を受け付けた後、前記第１の構成から第２の構成への前記分散処理システムの構成の変更を開始すること、
構成の前記変更を開始した後、一連の修正されたコンポーネント構成への前記システムのコンポーネント構成間の一連の２回以上の遷移を行い、前記修正された構成のコンポーネント間でデータ要素を各遷移後に転送させることであって、前記修正された構成の最後のものは前記第２の構成に対応し、それにより前記第１の構成から前記第２の構成への遷移が完了する、前記転送させること、及び
前記第２の構成への遷移が完了した後、第２の処理エポック内で前記データ集合の更なるデータ要素を前記第２の構成の複数のソースから受け付けることを含む、処理するステップと
を含む、方法。
【請求項２】
前記複数の計算資源が通信リンクによって結合される複数のプロセッサを含む、請求項１に記載の方法。
【請求項３】
前記複数の計算資源が前記複数のプロセッサのそれぞれの上で実行される少なくとも１つの処理スレッドを含み、各計算資源が別個の処理スレッドに関連付けられる、請求項２に記載の方法。
【請求項４】
データ要素の各ソースが、前記ソースからデータ要素を受け付けるように構成されるパーティショナモジュールに結合され、各パーティショナは前記パーティション規則に従って識別されるワーカにデータ要素を導くための前記パーティション規則によって構成される、請求項１〜３の何れか一項に記載の方法。
【請求項５】
前記システムのコンポーネント構成間の前記一連の２回以上の遷移のうちの第１の遷移を行うことが、
前記パーティショナモジュールの動作を休止し、前記パーティショナモジュールにおける前記ソースからのデータ要素の受け付けを停止すること、
修正されたパーティション規則を用いて前記複数のパーティションモジュールを再構成すること、及び
前記修正されたパーティションで再構成されたパーティションモジュールにデータ要素を与えるために、ソースから受け付けられるデータ要素の少なくとも１つの待ち行列を結合すること
を含む、請求項４に記載の方法。
【請求項６】
各パーティショナモジュールが前記パーティショナモジュールに結合されるソースと同じ計算資源上にホストされ、前記ソースから前記パーティショナにデータ要素を渡すことがプロセッサ間通信を必要とすることなしに行われる、請求項４に記載の方法。
【請求項７】
前記複数のワーカが１つ又は複数のワーカを含み、前記１つ又は複数のワーカの各ワーカは、複数のパーティショナモジュールからデータ要素を受け付けるように構成されるアクセプタモジュールに結合される、請求項４又は６に記載の方法。
【請求項８】
前記システムのコンポーネント構成間の前記一連の２回以上の遷移のうちの第１の遷移を行うことが、
前記パーティショナモジュールの動作を休止し、前記パーティショナモジュールにおける前記ソースからのデータ要素の受け付けを停止すること、
前記複数のアクセプタモジュールの動作を休止すること、
修正されたパーティション規則を用いて前記複数のパーティションモジュールを再構成すること、及び
前記修正されたパーティションで再構成されたパーティションモジュールにデータ要素を与えるために、前記複数のアクセプタモジュールのうちの或るアクセプタモジュールの少なくとも１つの待ち行列を結合すること
を含む、請求項７に記載の方法。
【請求項９】
各アクセプタモジュールが前記アクセプタモジュールに結合されるワーカと同じ計算資源上にホストされ、前記アクセプタモジュールから前記ワーカにデータ要素を渡すことがプロセッサ間通信を必要とすることなしに行われる、請求項７又は８に記載の方法。
【請求項１０】
第１のパーティショナモジュールが第１のアクセプタモジュールと同じ計算資源上にホストされ、第２のアクセプタモジュールと異なる計算資源上にホストされ、前記データ要素をルーティングすることは、プロセッサ間通信を必要とすることなしに前記第１のパーティショナモジュールから前記第１のアクセプタモジュールにデータ要素を渡すことを含み、前記第２のアクセプタモジュールに渡すための前記データ要素のプロセッサ間通信の前に前記第１のパーティショナモジュールにおいてデータ要素を待ち行列に入れることを含む、請求項７〜９の何れか一項に記載の方法。
【請求項１１】
前記複数のワーカが１つ又は複数のワーカを含み、前記１つ又は複数のワーカの各ワーカは、複数のパーティショナモジュールからデータ要素を受け付けるように構成されるアクセプタモジュールに結合される、請求項１〜１０の何れか一項に記載の方法。
【請求項１２】
データ要素が前記パーティショナモジュールの何れか１つから先入れ先出し順序で受信される、請求項１１に記載の方法。
【請求項１３】
各データ要素がシリアライゼーション値を更に含み、前記第１の処理エポックの間、前記第１の構成を使用して処理することがシリアライゼーションポリシを実施し、それにより同じシリアライゼーション値を有する２つのデータ要素がワーカによって互いに同時に処理されることがない、請求項１〜１２の何れか一項に記載の方法。
【請求項１４】
前記複数のワーカが１つ又は複数のワーカを含み、前記１つ又は複数のワーカの各ワーカは、複数のパーティショナモジュールからデータ要素を受け付けるように構成されるアクセプタモジュールに結合され、前記アクセプタモジュールはシリアライゼーションポリシを実施するように構成され、それにより同じシリアライゼーション値を有する２つのデータ要素が前記アクセプタモジュールに結合されるワーカによって互いに同時に処理されることがない、請求項１３に記載の方法。
【請求項１５】
前記第１の処理エポック後且つ前記第２の処理エポック前に、修正された各構成による処理が前記シリアライゼーションポリシを実施し続ける、請求項１３又は１４に記載の方法。
【請求項１６】
前記第１の処理エポックの間、前記第１のコンポーネント構成を使用して処理することがパーティションポリシを実施し、それにより第１のデータソースから第１の順序で受け付けられる同じパーティション値を有する全てのデータ要素が、前記複数のワーカの同じサブセットに前記第１の順序で与えられる、請求項１〜１５の何れか一項に記載の方法。
【請求項１７】
前記第１の処理エポック後且つ前記第２の処理エポック前に、前記第１の処理エポック内で処理を完了しておらず且つ前記第１のデータソースから受け付けられる前記同じパーティション値を有する前記データの前記第１の部分のデータ要素が、前記第１の順序で前記同じワーカに与えられる、請求項１６に記載の方法。
【請求項１８】
前記データ要素の少なくとも一部が、前記修正された構成のコンポーネント間で転送される、請求項１７に記載の方法。
【請求項１９】
コンポーネントの前記第２の構成が、（ａ）パーティション規則、（ｂ）１組のソース、及び（ｃ）１組のワーカの少なくとも１つにおいて前記第１の構成と異なる、請求項１〜１８の何れか一項に記載の方法。
【請求項２０】
機械可読媒体上に非一時的形式で記憶される、データ集合を分散処理するためのソフトウェアであって、データ処理システムの１個又は複数個のプロセッサによって実行されるとき、
分散処理システムを構成するための情報を入力装置又はポート上で受信することであって、前記構成することは前記分散処理システムの第１のコンポーネント構成を形成することを含み、前記第１の構成は前記データ集合のデータ要素の複数のソース及び前記データ集合のデータ要素を処理するように構成される複数のワーカを含み、前記ソース及びワーカは複数の計算資源間で分散され、各データ要素は前記第１の構成のパーティション規則に従って前記第１の構成の前記複数のワーカのサブセットを識別するパーティション値を含む、前記受信すること、並びに
少なくとも２つの処理エポック中に前記分散処理システム内でデータを処理することであって、
第１の処理エポック内で前記データ集合の第１の部分について前記ソースからデータ要素を受け付け、前記データ要素を前記第１の構成によってルーティングし、前記データ要素の少なくとも一部の処理を完了することであって、前記第１の部分の前記データ要素の残りは前記第１の構成のコンポーネントにおいて待ち行列に入ったままである、前記完了すること、
前記データ集合の第１の部分を受け付けた後、前記第１の構成から第２の構成への前記分散処理システムの構成の変更を開始すること、
構成の前記変更を開始した後、一連の修正されたコンポーネント構成への前記システムのコンポーネント構成間の一連の２回以上の遷移を行い、前記修正された構成のコンポーネント間でデータ要素を各遷移後に転送させることであって、前記修正された構成の最後のものは前記第２の構成に対応し、それにより前記第１の構成から前記第２の構成への遷移が完了する、前記転送させること、及び
前記第２の構成への遷移が完了した後、第２の処理エポック内で前記データ集合の更なるデータ要素を前記第２の構成の複数のソースから受け付けることを含む、処理すること
を前記データ処理システムに行わせる命令を含む、ソフトウェア。
【請求項２１】
複数の処理エンジンを含み、第１のコンポーネント構成に従って前記処理エンジン間で分散されるコンポーネントの構成を実行するように、及び一連の修正されたコンポーネント構成への前記システムのコンポーネント構成間の一連の遷移によって第２のコンポーネント構成への遷移を可能にするように構成される分散処理システムであって、前記第１のコンポーネント構成が、
前記データ集合のデータ要素の複数のソース及び前記データ集合のデータ要素を処理するように構成される複数のワーカであって、前記ソース及びワーカは複数の処理エンジン間で分散され、各データ要素は前記第１の構成のパーティション規則に従って前記第１の構成の前記複数のワーカのサブセットを識別するパーティション値を含む、複数のソース及び複数のワーカと、
前記ソースからデータ要素を受け付けるようにそれぞれ構成される複数のパーティショナモジュールであって、各パーティショナは前記パーティション規則に従って識別されるワーカにデータ要素を導くための前記パーティション規則で構成される、複数のパーティショナモジュールと、
複数のパーティショナモジュールからデータ要素を受け付け、少なくとも１つのワーカにデータ要素を与えるようにそれぞれ構成される複数のアクセプタモジュールと
を含み、
前記システムが、一連の修正されたコンポーネント構成への前記システムのコンポーネント構成間の一連の２回以上の遷移を行うことによって前記第１の構成から前記第２の構成に変わるように構成され、前記修正された構成のコンポーネント間でデータ要素を各遷移後に転送させ、前記修正された構成の最後のものは前記第２の構成に対応し、それにより前記第１の構成から前記第２の構成への遷移が完了する、
分散処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は２０１６年５月１７日に出願された米国仮特許出願第６２／３３７，４２２号明細書の優先権を主張する。
【背景技術】
【０００２】
本発明は再構成可能な分散処理の手法に関し、より具体的には処理の場所の数の変化又はデータプロデューサ若しくはコンシューマの場所の数の変化に応じて再構成可能な分散処理の手法に関する。
【０００３】
１組のデータ要素の分散処理は、処理されるデータ部分に関する（例えばデータベースからの）データアクセス又は（例えばディスクファイルシステムからの）データ記憶をそれぞれ可能にする幾つかのデータ要素のプロデューサ（即ちそれぞれがデータ作成の場所である）、例えば様々なコンピュータサーバやマルチプロセッサシステム内の物理プロセッサや論理プロセッサを使用し得る。同様に、処理の結果はここでも１組のコンピュータサーバ又はプロセッサとすることができる幾つかのデータ消費（例えば処理、記憶、伝送）の場所に送信され得る。処理自体が様々な処理の場所に分散されても良く、例えば各場所は別個のコンピュータサーバやサーバ上のプロセッサ等の様々な物理資源、又はサーバ上のオペレーティングシステムプロセスやオペレーティングシステムプロセス内の処理スレッド等の論理資源に関連付けされている。処理を調整するための１つの手法は例えばグラフベースのデータフローアーキテクチャ内のプロデューサ、処理、及びコンシューマの場所の配置を決定することである。
【０００４】
本明細書で援用する分散処理のための１つの手法が、参考文献として、２０１６年３月３日に発表され「Ｅｘｅｃｕｔｉｎｇ  Ｇｒａｐｈ−Ｂａｓｅｄ  Ｐｒｏｇｒａｍ  Ｓｐｅｃｉｆｉｃａｔｉｏｎｓ」と題された米国特許出願公開第２０１６／００６２７７６号明細書に記載されている。このシステムの一態様は「ｆｏｒａｌｌ」操作の実装であり、ｆｏｒａｌｌ操作ではデータ集合の全てのデータ要素が集合の要素の厳密な順序付けを必ずしも必要とすることなく処理される。概して、データ要素のソースが幾つかの計算資源（例えばサーバ）にわたって分散され、データ要素の処理結果が幾つかの計算資源にわたって分散される。
【０００５】
一部の事例では、データ集合のデータ要素を処理することが要素の処理の順序付け及び／又は同時実行に対する制約を有さず、資源間の計算負荷及び／又は記憶負荷の分散が効率を考慮するのに大きな基となる。
【０００６】
他の事例では、２種類の制約のうちの一方又は両方が存在し得る。以下「パーティショニング制約」と呼ぶ第１の制約は、データ要素の特定のサブセットの厳密な順序付けを保つことに関係する。この制約を具体的に述べるために、各要素は「パーティションキー」フィールドを含むことができ、制約は（ａ）同じパーティションキー値を有し且つ（ｂ）データソースの同じ部分から（即ち同じ記憶装置又は同じサーバから）取得されるデータ要素について、処理の場所におけるデータ要素の到着順序がそのデータソースからデータ要素が取得される順序と同じであることが保証されることである。概して、処理の場所に到着するデータ要素の処理は同時に処理され得る。
【０００７】
以下「同時実行制約」と呼ぶ第２の制約は、処理の場所においてデータ要素の特定のサブセット内の要素の同時処理を防ぐことに関係する。この制約を具体的に述べるために、各要素は「同時実行キー」フィールドを含むことができ、制約は同じ同時実行キーを有する２つのデータ要素がその処理の場所において同時に処理されてはならないことである。
【０００８】
これらの制約のどちらもシステムによるデータ要素の処理の際に単独で適用される場合があり、又は処理に対して両方の制約が一緒に課せられる場合がある。一部の例では、同じ同時実行キー値を有する２つのデータ要素が同じパーティションキー値を有することが保証される（例えば同時実行キーはパーティションキーの「拡張」である）が、より一般的には、同時実行キー値はデータ要素のパーティションキー値から独立している。同時実行キーがパーティションキーの拡張である（又は同じ同時実行キーを有するデータ要素についてパーティションが別な具合に固有である）場合、同時実行の制約は同じ同時実行キーを有する２つのデータ要素がシステムの如何なる処理の場所においても同時に処理されないことを保証する。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】米国特許出願公開第２０１６／００６２７７６号明細書
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上記で明らかにしたパーティション制約及び／又は同時実行制約を満たすやり方でデータ集合の要素の「ｆｏｒａｌｌ」処理を１組の計算資源にわたって分散させるやり方を提供することが求められている。更にパーティション制約及びシーケンシング制約を満たし続けながら計算資源の再構成又は再割当てを可能にするように処理を分散させる方法が求められている。
【課題を解決するための手段】
【００１１】
一態様では、概してデータ集合を分散処理するための方法が、分散処理システムを構成するための情報を入力装置又はポート上で受信するステップを含み、分散処理システムを構成することは分散処理システムの第１のコンポーネント構成を形成することを含む。第１の構成は、データ集合のデータ要素の複数のソース及びデータ集合のデータ要素を処理するように構成される複数のワーカを含み、ソース及びワーカは複数の計算資源間で分散される。各データ要素は、第１のコンポーネント構成のパーティション規則に従って第１の構成の複数のワーカのサブセットを識別するパーティション値を含む。少なくとも２つの処理エポック中に分散処理システム内でデータが処理され、処理は以下のステップを含む。第１の処理エポック内でデータ集合の第１の部分についてソースからデータ要素が受け付けられ、それらのデータ要素は第１の構成によってルーティングされる。それらの第１の部分のデータ要素の少なくとも一部について処理が完了する一方、第１の部分のデータ要素の残り（即ち処理が完了したデータ要素以外）は第１の構成のコンポーネントにおいて待ち行列に入ったままである。データ集合の第１の部分を受け付けた後、第１の構成から第２の構成への分散処理システムの構成の変更が開始される。構成の変更が開始された後、一連の修正されたコンポーネント構成を形成するために、システムのコンポーネント構成間の一連の２回以上の遷移が行われる。各遷移後、修正された構成のコンポーネント間でデータ要素が転送される。修正された構成の最後のものは第２の構成に対応し、それにより第１の構成から第２の構成への遷移が完了する。第２の構成への遷移が完了した後、第２の処理エポック内でデータ集合の更なるデータ要素が第２の構成の複数のソースから受け付けられる。
【００１２】
態様は以下の特徴の１つ又は複数を含み得る。
【００１３】
複数の計算資源は通信リンクによって結合される複数のプロセッサを含む。
【００１４】
複数の計算資源は複数のプロセッサのそれぞれの上で実行される少なくとも１つの処理スレッドを含み、各計算資源は別個の処理スレッドに関連付けられる。
【００１５】
データ要素の各ソースは、ソースからデータ要素を受け付けるように構成されるパーティショナモジュールに結合され、各パーティショナはパーティション規則に従って識別されるワーカにデータ要素を導くためのパーティション規則によって構成される。
【００１６】
システムのコンポーネント構成間の一連の２回以上の遷移のうちの第１の遷移を行うことは、パーティショナモジュールの動作を休止し、パーティショナモジュールにおけるソースからのデータ要素の受け付けを停止すること、修正されたパーティション規則を用いて複数のパーティションモジュールを再構成すること、及び修正されたパーティションで再構成されたパーティションモジュールにデータ要素を与えるために、ソースから受け付けられるデータ要素の少なくとも１つの待ち行列を結合することを含む。
【００１７】
各パーティショナモジュールは前述のパーティショナモジュールに結合されるソースと同じ計算資源上にホストされ、前述のソースから前述のパーティショナにデータ要素を渡すことがプロセッサ間通信を必要とすることなしに行われる。
【００１８】
複数のワーカは１つ又は複数のワーカを含み、前述の１つ又は複数のワーカの各ワーカは、複数のパーティショナモジュールからデータ要素を受け付けるように構成されるアクセプタモジュールに結合される。
【００１９】
システムのコンポーネント構成間の一連の２回以上の遷移のうちの第１の遷移を行うことは、パーティショナモジュールの動作を休止し、パーティショナモジュールにおけるソースからのデータ要素の受け付けを停止すること、複数のアクセプタモジュールの動作を休止すること、修正されたパーティション規則を用いて複数のパーティションモジュールを再構成すること、及び修正されたパーティションで再構成されたパーティションモジュールにデータ要素を与えるために、複数のアクセプタモジュールのうちの或るアクセプタモジュールの少なくとも１つの待ち行列を結合することを含む。
【００２０】
各アクセプタモジュールは前述のアクセプタモジュールに結合されるワーカと同じ計算資源上にホストされ、前述のアクセプタモジュールから前述のワーカにデータ要素を渡すことがプロセッサ間通信を必要とすることなしに行われる。
【００２１】
第１のパーティショナモジュールは第１のアクセプタモジュールと同じ計算資源上にホストされ、第２のアクセプタモジュールと異なる計算資源上にホストされ、データ要素をルーティングすることは、プロセッサ間通信を必要とすることなしに第１のパーティショナモジュールから第１のアクセプタモジュールにデータ要素を渡すことを含み、第２のアクセプタモジュールに渡すための前述のデータ要素のプロセッサ間通信の前に第１のパーティショナモジュールにおいてデータ要素を待ち行列に入れることを含む。
【００２２】
複数のワーカは１つ又は複数のワーカを含み、前述の１つ又は複数のワーカの各ワーカは、複数のパーティショナモジュールからデータ要素を受け付けるように構成されるアクセプタモジュールに結合される。
【００２３】
データ要素は、パーティショナモジュールの何れか１つから先入れ先出し順序で受信される。
【００２４】
各データ要素はシリアライゼーション値を更に含み、第１の処理エポックの間、第１の構成を使用して処理することがシリアライゼーションポリシを実施し、それにより同じシリアライゼーション値を有する２つのデータ要素がワーカによって互いに同時に処理されることがない。
【００２５】
複数のワーカは１つ又は複数のワーカを含み、前述の１つ又は複数のワーカの各ワーカは、複数のパーティショナモジュールからデータ要素を受け付けるように構成されるアクセプタモジュールに結合され、アクセプタモジュールはシリアライゼーションポリシを実施するように構成され、それにより同じシリアライゼーション値を有する２つのデータ要素が前述のアクセプタモジュールに結合されるワーカによって互いに同時に処理されることがない。
【００２６】
第１の処理エポック後且つ第２の処理エポック前に、修正された各構成による処理がシリアライゼーションポリシを実施し続ける。
【００２７】
第１の処理エポックの間、第１のコンポーネント構成を使用して処理することがパーティションポリシを実施し、それにより第１のデータソースから第１の順序で受け付けられる同じパーティション値を有する全てのデータ要素が、複数のワーカの同じサブセットに第１の順序で与えられる。
【００２８】
第１の処理エポック後且つ第２の処理エポック前に、第１のエポック内で処理を完了しておらず且つ第１のデータソースから受け付けられる同じパーティション値を有するデータの第１の部分のデータ要素が、第１の順序で同じワーカに与えられる。
【００２９】
前述のデータ要素の少なくとも一部が、修正された構成のコンポーネント間で転送される。
【００３０】
第２のコンポーネント構成は、（ａ）パーティション規則、（ｂ）１組のソース、及び（ｃ）１組のワーカの少なくとも１つにおいて第１の構成と異なる。例えばパーティション規則は、パーティショニングを行うために使用されるマッピング又は形成されるパーティション数の何れか又は両方において異なることができ、１組のソースは使用されるソース数又は計算資源をホストするサーバ上のソースの配置の何れか又は両方において異なることができ、１組のワーカは使用されるワーカ数又は計算資源をホストするサーバ上のワーカの配置の何れか又は両方において異なることができる。
【００３１】
別の態様では、概して非一時的機械可読媒体上に記憶されるソフトウェアはその上に記憶される命令を含む。それらの命令は、データ処理システムの１個又は複数個のプロセッサによって実行されるとき、上記の方法の何れかの全てのステップをデータ処理システムに実行させる。
【００３２】
別の態様では、概して分散処理システムが複数の処理エンジンを含み、前述の処理エンジン間で分散されるコンポーネントの構成を実行するように構成される。システムは１つ又は複数のデータソースからのデータ要素の処理中に上記の方法の何れかの全てのステップを実行するように構成される。
【００３３】
態様は以下の利点の１つ又は複数を有し得る。
【００３４】
システムの全コンポーネントの完全な静止状態を必要とすることなしに、データ要素の集合の処理中にシステムのコンポーネントの再構成が行われ得る。かかる形態の結果は、全体的な効率又はスループットが他の手法よりも改善されることである。例えば処理されているデータ要素の特性に一致するように又は処理に適用可能な計算資源の特性に一致するように、利用可能な資源をより効率的に使用することに関係する理由を含め、再構成は様々な理由から開始され得る。
【００３５】
本発明の他の特徴及び利点は、以下の説明及び特許請求の範囲から明らかである。
【図面の簡単な説明】
【００３６】
【図１Ａ−１Ｃ】図１Ａは処理コンポーネントに関するパーティショングループ、アクセプトグループ、及びワークグループを含む分散処理構成のブロック図であり、図１Ｂは図１Ａの構成にアクセプトグループ及びワークグループを追加した分散処理構成のブロック図であり、図１Ｃは図１Ａの構成に対して或るホストから他のホストへコンポーネントを移行する分散処理構成のブロック図である。
【図２】パーティショングループ内のコンポーネント構成のブロック図である。
【図３】アクセプトグループ内のコンポーネント構成のブロック図である。
【図４】アクセプトグループの代替的構成のブロック図である。
【図５】ワークグループ内のコンポーネント構成のブロック図である。
【図６】ワークグループ内の代替的コンポーネント構成のブロック図である。
【図７】分散処理構成の例である。
【図８】分散処理構成の例である。
【図９】分散処理構成の例である。
【図１０】再構成手続きの流れ図である。
【図１１Ａ−Ｉ】図１Ａに対応する図１１Ａに示す初期構成から、図１１Ｂ〜図１１Ｈに示す中間構成を経た、図１Ｃに対応する図１１Ｉに示す最終構成までの一連の構成の説明図である。
【発明を実施するための形態】
【００３７】
図１Ａを参照すると、分散処理システムの分散処理構成１００が幾つかのソース１１０から、データ要素が処理されるか、又は消費される幾つかのワークグループ１４０にデータ集合のデータ要素を渡す。概して異なるデータ要素がパーティショニング規則に従って異なる宛先に渡されるように、ソース１１０からのデータ要素はパーティショニンググループ１２０を介して渡される。この構成では、同じパーティションキー値を有する要素が各パーティショニンググループ１２０から同じ宛先に渡される。概してこの構成の異なるパーティショングループ１２０は同じパーティション規則を使用し、そのことは同じパーティションキー値を有するデータ要素がパーティショングループによって同じ宛先に渡されることをもたらす。
【００３８】
パーティショニンググループ１２０はデータ要素をアクセプトグループ１３０に渡す。概してパーティショングループのそれぞれは同じパーティショニング規則を使用し、そのため或る特定のアクセプトグループがパーティショニング規則によって定められる特定の部分（即ち１組のバラバラなパーティションキー値）内にあるデータ集合の全ての要素を受信する。
【００３９】
各アクセプトグループ１３０は、自らに渡される要素に対して処理を行う１つ又は複数のワークグループ１４０に要素を渡す。概して各アクセプトグループ１３０及び各アクセプトグループ１３０が要素を渡すワークグループ１４０は同時実行制約を一緒に実施する。この構成では、概して同じ同時実行キー値を有する全てのデータ要素がパーティショニングループによって同じアクセプトグループ１３０にルーティングされ、その後、アクセプトグループ１３０及びアクセプトグループ１３０のワークグループ１４０は同じ同時実行キーを有する何れか２つの要素の同時処理を防ぐように動作する。
【００４０】
図１に示すコンポーネントは様々な計算資源にわたって概して分散されることを理解すべきである。図１の説明図では、別々の計算資源１９０〜１９５が示されている。資源１９０及び１９１はサーバコンピュータ上で実行されている異なる処理スレッドを表し、資源１９２及び１９３並びに資源１９４及び１９５は異なるサーバコンピュータ上の異なる処理スレッドを表す。従ってコンポーネント間の通信を表す一部のコンポーネント間リンクは単一のスレッド内の通信に対応し（例えばリンク１１１、１２１、１３１）、一部は単一のコンピュータ上の異なるスレッド間の通信を表し（例えばリンク１３２）、一部はサーバコンピュータ間の通信を表す（例えばリンク１２３）。
【００４１】
様々な計算資源に対する図１Ａに示すコンポーネントの割当ては全体的な「ｆｏｒａｌｌ」処理タスクの実行前に決定され得る。分散処理システムの１組のコンポーネント又は計算資源に対するコンポーネントの割当てが変わり得るときがある。例えば図１Ｂでは、更なるワークグループ１４０を有する第３のアクセプトグループ１３０が追加され得る。別の例として図１Ｃでは、サーバ（例えば処理スレッド１９２及び１９３）の１つからのコンポーネントが別のサーバ（例えばスレッド１９４及び１９５）に移行される。
【００４２】
図１Ａの構成から図１Ｂの構成に遷移するための１つのシナリオは、ワークグループの数を増やすことによって処理速度を上げることに関する。２つのアクセプトグループ１３０を用いてデータ要素がパーティショングループ１２０によって２つの部分にパーティショニングされるのに対し、アクセプトグループが３つある最終構成ではパーティショングループ１２０がデータ要素の三段パーティショニングを行うことを理解すべきである。二段パーティショニング構成から三段パーティショニング構成への遷移中に処理規則が違反されないことが重要である。図１Ａの構成から図１Ｃの構成への遷移シナリオは、異なる容量を有し得る異なるサーバを使用することである。
【００４３】
構成を変える１つの手法はソース１１０からの要素の提供を単純に停止し、ソース１１０とワークグループ１４０との間でどの要素も「飛行中（ｉｎ  ｆｌｉｇｈｔ）」ではないように、システムが全ての処理を完了するまで待つことであり得る。その後、パーティションキー制約による順序付け又は同時実行キー制約によるシーケンシングに違反する可能性なしに新たな構成が開始され得る。しかし、ソース１１０によって既に与えられている全ての要素が処理されるのを待つ間、計算資源が十分に利用されない可能性がある点でかかる手法は非効率的であり得る。代替的手法は、修正された各構成内で制約が満たされたままであり且つ計算資源が十分に利用されたままであるやり方で選択されるシステムの一連の一時的な修正されたコンポーネント構成を使用する。以下に記載する一実施形態では、図１Ａ及び図１Ｂに示すコンポーネントの特定のものが幾つかの構成コンポーネントとして実装され、一連の一時的構成はそれらの構成コンポーネント間で接続を変えることを含む。図１Ａに示す構成から図１Ｂに示す構成への変更や図１Ａに示す構成から図１Ｃに示す構成への変更等、構成の全体的な変更を実現するための遷移について説明する前に図２〜図６の中で構成コンポーネントについての説明を行う。これらの図面では、構成コンポーネントを示す図１Ａ〜図１Ｃのコンポーネントを参照のために破線で示し、それらの中の相互接続は実線である。
【００４４】
図２を参照し、パーティショングループ１２０は、データソース１１０からデータ経路１１１上でデータ要素を受け付ける先入れ先出し（ＦＩＦＯ）待ち行列２１１を含む。待ち行列２１１がＦＩＦＯなので、待ち行列の全体にわたってパーティショニング制約が維持される。パーティショナ２２０は、それを用いてパーティショナが（例えば内の又はパーティショナにとってアクセス可能なパーティション規則を表すデータ用のデータ記憶域に従って）構成されるパーティショニング規則を実装する。例えばパーティションキーが姓に対応する場合、パーティション規則は姓の最初の文字に従って部分を定めることができ、範囲「Ａ」〜「Ｈ」を第１の出力データ経路１２１上で、範囲「Ｉ」〜「Ｐ」を第２のデータ経路１２２によって、且つ範囲「Ｓ」〜「Ｚ」を第３のデータ経路上で渡すことができる。一部の例では、ハッシュ関数等の関数を組み込むマッピング等、データ経路に値をマップするためにパーティション規則が他のマッピング形式を使用しても良い。パーティショナ２２０を出るデータ経路は（１）同じ計算資源（例えばプロセッサ上の同じスレッド）上に留まるデータ経路１２１、（２）異なる計算資源（例えば異なるスレッド）上で実行されているコンポーネントへのデータ経路１２２であって、異なる計算資源はランタイム記憶域（例えば共用ダイナミックメモリ）をパーティショナ２２０の計算資源と共用する、データ経路１２２、及び（３）データ要素が異なる計算資源に渡される経路２２３であって、その異なる計算資源への通信はプロセッサ間通信（例えばデータネットワーク通信）を必要とする、経路２２３を含む様々な種類のものであり得る。パーティショナ２２０からのプロセッサ間通信を実装するために、パーティショングループ１２０はＦＩＦＯ待ち行列２２１、並びに例えば遠隔手続き呼出し（ＲＰＣ）メカニズムを使用し、受信したデータ要素をデータ経路１２３上で特定の遠隔計算資源に移動させることを担う通信コンポーネント２２２も含む。
【００４５】
図３を参照し、様々な種類のデータ経路、例えば上記のデータ経路１２１、１２２、及び１２３上でデータ要素を受信することができるＦＩＦＯ待ち行列２２６を使用するアクセプトグループ１３０Ａとして、アクセプトグループ１３０が第１の例として実装されている。一部の例では、例えば入力データ経路ごとに別々のＦＩＦＯ待ち行列を実装し、それらの待ち行列を順番に、例えばラウンドロビンポリシに従って供給することにより、何れか１つのデータ経路からのデータ要素が先入れ先出し順序で保たれることだけを必要とするように待ち行列２２６の先入れ先出しポリシが緩和されても良い。図３のアクセプトグループ１３０Ａは、処理用のデータ要素を複数のワークグループ１４０に与えることができるアクセプタ２３０も含む。例えばこのアクセプタは、データ経路１３１上で同じ計算資源（例えば同じスレッド）上の１つ又は複数のワークグループ１４０にデータ要素を送信することができ、且つ／又はデータ経路１３２上でこのアクセプタとランタイム記憶域を共用する異なる計算資源上の１つ又は複数のワークグループ１４０にデータ要素を送信することができる。図３に示す構成では、アクセプタが複数のワークグループ１４０による同時処理のために複数のデータ要素を送り出すことができる。従ってシリアライゼーションキーポリシを実装する実施形態では、２つのデータ要素が同時に処理される可能性があるため、ワークグループ１４０に２つのデータ要素を決して送り出さないことによってシリアライゼーションキー制約を実施するようにアクセプタが構成される。アクセプタは、内部又はアクセプタにとってアクセス可能なシーケンシング規則を表すデータ用のデータ記憶域に従って構成される。
【００４６】
図４を参照し、一部の構成ではアクセプトグループ１３０はアクセプトグループ１３０Ｂとして第２の例として実装され得る、入力データ経路１２１が１つだけしかなく且つ出力データ経路１３１が１つだけしかないとき単にデータ経路２３９を有する。かかるアクセプトグループ１３０Ｂがアクセプトグループ１３０Ｂの出力ワークグループ１４０と同じ計算資源に割り当てられ、且つアクセプトグループ１３０Ｂにデータ要素を与える単一のパーティショングループ１２０と同じ計算資源に割り当てられる場合、パーティショニング制約及びシーケンシング制約に違反する心配なしに、パーティショングループ１２０（即ちそのパーティショングループ内のパーティショナ２２０）がワークグループ１４０にデータ要素を直接与えることができる。
【００４７】
図５を参照し、一部の構成ではワークグループ１４０がワークグループ１４０Ａの第１の例として実装され得る。ＦＩＦＯ待ち行列２３１が１つ又は複数のパーティショングループにおいて生じるデータ要素を受信し、そのデータ要素の順序を（少なくとも各パーティショングループからのデータ要素内で）保つ。同じシリアライゼーションキー値を有する２つのデータ要素がシリアライザの下流にあり且つまだ完全に処理されていないことを防ぐために、シリアライザ２３２がデータ単位を遅らせることによってシリアライゼーションを実施する。シリアライザはデータ要素をＦＩＦＯ待ち行列２３６に渡し、ワーカ２４０が待ち行列２３６からのデータ要素の処理を順に開始し、概して複数のデータ要素を同時に処理する。この説明の文脈では「ワーカ」とは、自らが受信するデータ要素に対して作業（即ち計算機能、記憶機能、及び伝送機能のうちの１つ又は複数）を行うシステムのソフトウェア実装要素である。一部の事例では、ワーカによって行われる作業がワーカにとってアクセス可能なデータベースや他のデータ記憶構成内のデータの変化等の副作用を引き起こす。一部の実装形態では、ワーカ２４０が（例えばオペレーティングシステムプロセス、軽量プロセス、又はスレッドとして実装される）単一の実行スレッドを有し得る一方、他の実装形態ではワーカ２４０が互いを妨げない複数の実行スレッドを有する場合があり、システムが例えば差異スループット容量を有する様々な種類のワーカを有し得ることを理解すべきである。
【００４８】
図６を参照し、ワークグループ１４０の別の例であるワークグループ１４０Ｂは、図５に示す例と同様にＦＩＦＯ待ち行列２３６を含む。この例ではシリアライゼーション制約はなく、ワークグループの入力データ経路から自らのデータ要素を受信する待ち行列２３６からワーカ２４０がデータ要素を直接受信する。
【００４９】
概して、上記の構成コンポーネントを所与とし、幾つかの異なるトポロジカルパターンが良く見られる。これらの全ての例の中で認められる１つの重要な特性は、ソース１１０とワーカ２４０にデータ要素を与える待ち行列２３６との各対について、ソースからその待ち行列まで厳密に１つの経路があることである。経路に沿って待ち行列内のバッファリングがある場合、それはＦＩＦＯポリシによるものである。従って、そのソースによって与えられる同じパーティション内の全てのデータ要素がそのパーティション用の待ち行列において順に到着し、それによりパーティション制約が満たされることを保証する。
【００５０】
図７〜図９を参照し、上記で紹介した要素は様々なトポロジをサポートする。３つの例を以下で論じる。概してこれらのトポロジは１１個の層を有すると見なすことができ、各層はｆｏｒａｌｌレコード生成、ルーティング、シリアライゼーション、及び処理の特定の機能に充てられる。
【００５１】
これらのトポロジグラフの１つの重大な特性は、ソース１１０とアクセプトグループ１３０との任意の対の間に多くて１つの経路しかないことである。アクセプトされたグループの下流で並べ替えが明確に許可されていない限り、このことは同じソースから作り出され同じパーティション内で処理されるレコードが常に順に処理されることを確実にする。
【００５２】
図７を参照し、比較的大まかな事例では、他の複数のエンジンにわたって広がる多くのパーティションへとパーティショニングされる各エンジン７９０、７９３、７９６上の（各エンジンは複数の処理スレッド７９１、７９２、７９４、７９５、７９７、７９８を有する）多くのレコードソース１１０があり得る。ｆｏｒａｌｌトポロジに関与するエンジンはソース及びパーティショングループ、又はアクセプトグループ及びワーカグループ、又はその両方をホストすることができる。図７に示すコンポーネントは上記の図１〜図６の説明と一貫して番号を付けてある。処理スレッド７９５について図７に示すように、１つの留意点はワーカ２４０が１つの処理スレッド内の複数のワークグループ１４０間で共用され得ることである。
【００５３】
この１１層トポロジパターンの完全な普遍概念は全ての事例で必要という訳ではなく、そのため適用され得る様々な専門化及び最適化がある。図８を参照し、１つの共通パターンはシリアルファイル等の（スレッド７９１上の）非パーティションソース１１０からファンアウトしてクラスタ内で使用可能な全てのスレッド７９１、７９２、７９４、７９５、７９７、７９８にわたって処理を行うことである。
【００５４】
図９を参照し、別の共通使用事例はエンジン間のデータ移動を防ぐために整列されたパーティションを使用してデータを処理することである。この例ではエンジン７９０とエンジン７９３との間のデータ転送はないが、各エンジン上で複数の処理スレッドが利用されている。
【００５５】
上記で紹介したように、必要とされるデータ集合に対する処理、データソースの位置、及び使用可能な計算資源に従ってコンポーネント構成が実行前に決定され得る。ソースが使い果たされる（即ち自らの全てのデータ要素を提供する）とき、及びＥｎｄ−ｏｆ−Ｉｎｆｏｒｍａｔｉｏｎ（ＥＯＩ）要素がデータ経路によって伝搬され、それによりコンポーネントがシャットダウンされることが許可され、最終的にデータ要素の全ての処理が完了すると全てのコンポーネントをシャットダウンする。
【００５６】
上記で紹介したように、データ集合の処理中にコンポーネント構成を変えることが望ましい場合もある。かかる再構成のための様々な理由は、計算資源（例えばサーバコンピュータや処理スレッド等）を追加すること若しくは除去すること、又は特定のパーティショニング規則に起因する負荷の不均衡が認められ、負荷を均衡させるためにパーティショニング規則の変更を望むことによって促され得る。
【００５７】
構成が静的である時間中はデータ要素が正しくパーティショニングされ、パーティショニング制約を満たして順に処理される。構成が静的であるかかる期間をルーティングエポックと呼ぶ。或るルーティングエポックから別のルーティングエポックへの遷移は、データ要素が適切にパーティショニングされ処理されたままであるように一連の再構成として作用される。
【００５８】
上記で紹介したように、或るルーティングエポックから別のルーティングエポックへの遷移を行うための１つの手法は、ソースからのデータ要素の提供を実質的に停止し、全てのコンポーネントが実質的に静止状態になる（その時点でコンポーネントを再構成し、次のエポックを開始することができる）まで全ての経路沿いのｅｎｄ−ｏｆ−ｉｎｆｏｒｍａｔｉｏｎ要素を処理することである。しかし、かかる手法は遷移中に多くの計算資源を十分に利用しないままにしておくことが明白である。
【００５９】
より効率的な手法では、例えば構成内の個々のデータ経路のソース又は宛先が変更され、個々に静止状態にあるコンポーネント（例えば空の待ち行列やアイドル状態のワーカ等）が終了され又はコンピュータサーバ若しくはスレッド間で移動され、新たなコンポーネントが開始され既存の又は新たなデータ経路に接続される。
【００６０】
かかるシーケンシングの一例は、図１０の流れ図１０００に示す以下のステップを含む。
【００６１】
ステップ１．データ要素が処理されないように幾つかのコンポーネントを一時停止させる。具体的には、パーティショングループ１２０によって処理されている（即ち図２を参照し、待ち行列２１１から読み出されている如何なるデータ要素も出力データ経路１２１、１２２、又は２２３上に送られている）データ要素がないように全てのパーティショナ２２０を一時停止させる。通信コンポーネント２２２も一時停止させ、概してパーティショナ２２０と通信コンポーネント２２２との間の待ち行列２２１内に少なくとも幾らかのデータ要素を残す。アクセプタ２３０も一時停止させ、概して待ち行列２２６内にデータ要素を残す。シリアライザ２３２も一時停止させる。ワークグループ１４０のコンポーネントは動作し続ける。
【００６２】
ステップ２．上流の待ち行列の先頭に特定の待ち行列内のデータを再配置する。具体的には、データ要素が直ちに待ち行列から外れないようにパーティショナ２２０を一時停止したままの状態で、各待ち行列２２１のコンテンツを同じパーティショングループ１２０の対応する待ち行列２１１の先頭に入れる。同様に、各ワークグループ１４０のＦＩＦＯ待ち行列２３１及び待ち行列２３６のコンテンツを図４で１３０Ａと示す種類の上流のアクセプトグループ１３０の待ち行列２２６の先頭に入れ、又は上流のアクセプトグループ１３０が図５に示す種類１３０Ｂのものである場合はアクセプトグループ１３０から最初の下流の待ち行列の先頭に入れる。
【００６３】
ステップ３．ワークグループ１４０の処理を完了することを許可する。この時点で、パーティショングループ１２０の待ち行列２１１及びアクセプトグループ１３０の待ち行列２２６を除いて構成内で待ち行列に入っているデータ要素はない。
【００６４】
ステップ４．待ち状態のデータ要素を有する待ち行列２２６を保つ新たな構成に不要な任意のアクセプトグループ１３０又はワークグループ１４０を除去するように構成を変える。保たれる任意のアクセプトグループ１３０の待ち行列２２６をそのアクセプタ２３０から切断し、新たな空の待ち行列２２６をアクセプタ２３０に結び付ける。
【００６５】
ステップ５．待ち行列２１１のデータ要素を処理する前に又はソース１００からまだ読み出されていないデータ要素を処理する前に待ち行列２２６のデータ要素を処理する。アクセプトを処理する、待ち行列２２６のからのデータレコード、それらをパーティショナ２２０を通過させ、新たな構成に従って構成し、データレコードを新たな構成のアクセプトグループ１３０に送信するようにコンポーネントの一時的な３層構成を構築する。
【００６６】
ステップ６．古い待ち行列２２６のそれぞれの末尾にＥｎｄ−ｏｆ−Ｉｎｆｏｒｍａｔｉｏｎ（ＥＯＩ）マーカを挿入する。ステップ５で構築した一時的コンポーネントの一時停止が解除され、システムは一時的コンポーネントが非活性状態にあることを示すＥＯＩマーカを一時的コンポーネントが通すのを待つ。
【００６７】
ステップ７．この時点で、前のルーティングエポック内でパーティショニングされた既存のデータ要素の全てが新たなルーティングエポックのための正しいアクセプタグループ１３０内にある。ステップ５で構築した一時的コンポーネント並びに古い待ち行列２２６を除去する。
【００６８】
ステップ８．新たなエポックのためにパーティショングループ１２０の全てのパーティショナ２２０を構成する。
【００６９】
ステップ９．各待ち行列にＥＯＩマーカを加えることにより、（そのソース１００が使用されないので）新たなエポック内で使用されない前のエポックからの待ち行列２１１内のデータ要素を今度は処理し、（新たなパーティショニング規則に従って構成される）それらの待ち行列のためのパーティショナ２２０の一時停止が解除される。ＥＯＩマーカがそれらのパーティショングループの全てのコンポーネントを通過すると、「飛行中」の全てのデータレコードがその正しいアクセプタグループ１３０又はワークグループ１４０内にある。
【００７０】
ステップ１０．新たな構成内で使用しないソース１００及び対応するパーティショングループ１２０を除去する。
【００７１】
ステップ１１．新たな構成内に新たなソース１００及びパーティショングループを追加し接続する。
【００７２】
ステップ１２．新たな構成の全てのコンポーネントの一時停止を解除し、新たなエポックが開始する。
【００７３】
図１１Ａ〜図１１Ｉを参照し、上記の再構成手続きの一例を示す。図１１Ａを参照し、データソースにわたるｆｏｒａｌｌの実行が２つのエンジン７９０、７９３にわたって最初にパーティショニングされ、ソース１１０及びソース１１０のワークグループ１４０の１つを遷移させる必要がある。図１１Ａはルーティングエポック１中の最初のトポロジを示し、図１１Ｉはエンジン７９３の使用がエンジン７９６の使用で置換された所望のトポロジを示す。
【００７４】
図１１Ｂを参照し、ステップ１で図中の点線の輪郭によって示されているソース１１０、パーティショナ２２０、アクセプタ２３０、及びシリアライザ２３２を一時停止させる。図１１Ｂでは一時停止されたコンポーネントを点線の輪郭によって示す。図１１Ｃを参照し、ステップ２でレコードを待ち行列２２１（この例にはない）から待ち行列２１１の先頭に戻すと共に、ＦＩＦＯ待ち行列２３１、シリアライザ２３２、及び待ち行列２３６から待ち行列２２６の先頭に再び戻し、データ要素の順序を保つ。図１１Ｄを参照し、ステップ３でｆｏｒａｌｌがアイドル状態になると、プロセスのステップ４がトポロジグラフの後半を再構成することによってｆｏｒａｌｌトポロジの最初の変更を行う。
【００７５】
図１１Ｅを参照し、ステップ５は、新たなコンポーネントはパーティショナ７２０、待ち行列７２１、及び通信コンポーネント７２２を含むにより、古い待ち行列２２６からのデータ要素を新たなＦＩＦＯ待ち行列２３１内に再パーティショニングするためにトポロジ内に３つのレベルを一時的に追加する。
【００７６】
図１１Ｆを参照し、ステップ６で、トポロジのこの新たな部分を実行することはデータ要素を新たなＦＩＦＯ待ち行列２３１内に再パーティショニングする。この例ではエンジン１上のレコードはエンジン１上に留まるが、エンジン２上のレコードはエンジン３に移動する。概して、再パーティショニングは全対全であり得る。このことは様々なソースからのデータ要素がＦＩＦＯ待ち行列２３１内で混ざることを可能にするが、同じソースにおいて生じ且つ同じパーティショニングキーを有する全てのレコードが順序を保ち、その理由はそれらのレコードが同じ古いＦＩＦＯ待ち行列内に一緒にあったからである。同様に、異なる待ち行列内にあったデータ要素、再パーティショニング中に混ざるが、パーティション内の順序付け及びシリアライゼーションキーグループは保たれる。
【００７７】
図１１Ｇを参照し、ステップ７及びステップ８は一時的コンポーネント７２０、７２１、７２２を除去し、パーティショナ８２０、待ち行列８２１、及び通信コンポーネント８２２を含む新たなコンポーネントを使用して出てゆくソース１１０からのデータ要素を再パーティショニングするためにトポロジの前半を再構成する。図１１Ｈを参照し、遷移トポロジを実行することは、新たなルーティングエポックについてその正しいＦＩＦＯ待ち行列２３１へと出てゆく全ての待ち行列２１１からのレコードを移動させる。図１１Ｉに示すように、ステップ１０及び１１は新たなルーティングエポックのためにトポロジをその最終形態へと再構成する。データが再パーティショニングされ、順序付けが保たれ、トポロジが完全に遷移した状態で、ステップ１２は新たなルーティングエポック内で安全に実行を再開することができる。
【００７８】
データを待ち行列に入れること、或いはデータを待ち行列から待ち行列に移動することに言及する上記の説明では、かかる転送のソース及び宛先が単一のプロセス若しくはスレッドを用いる場合又はアドレス空間を共用するプロセス若しくはスレッド間のものである場合、移動はデータ要素を所定位置に残し、データ要素へのポインタを単に移動することによって実施され得ることを理解すべきである。同様に、待ち行列Ａのコンテンツを待ち行列Ｂの先頭に移動することについて記述する手続きでは、次いで待ち行列Ｂからの要素を処理することは一連の構成によって実施することができ、その構成の第１の構成では待ち行列Ａが自らの全ての要素を順に供給し、しまいには待ち行列Ａの全ての要素が使い果たされ、次いで第２の構成では待ち行列Ｂが自らの要素を順に提供する。
【００７９】
上記の手法は、例えば適切なソフトウェア命令を実行するプログラム可能計算システムを使用して実装することができ、書替え可能ゲートアレイ（ＦＰＧＡ）等の適切なハードウェアによって実装することができ、又は何らかの混成形式で実装することができる。例えばプログラムされた手法では、１つ又は複数のプログラムされた計算システム又はプログラム可能な計算システム（分散、クライアント／サーバ、又はグリッド等、様々なアーキテクチャのものであり得る）上で実行される１つ又は複数のコンピュータプログラム内の手続きをソフトウェアが含むことができ、かかる計算システムは少なくとも１個のプロセッサ、（揮発性及び／又は不揮発性のメモリ及び／又は記憶要素を含む）少なくとも１つのデータ記憶システム、（少なくとも１つの入力装置又はポートを使用して入力を受け付け、少なくとも１つの出力装置又はポートを使用して出力を行うための）少なくとも１つのユーザインタフェースをそれぞれ含む。ソフトウェアは、例えばデータフローグラフの設計、構成、及び実行に関係するサービスを提供するより大きいプログラムの１つ又は複数のモジュールを含み得る。プログラムのモジュール（例えばデータフローグラフの要素）は、データリポジトリ内に記憶されるデータモデルに従うデータ構造又は他の組織化されたデータとして実装され得る。
【００８０】
揮発性記憶媒体や不揮発性記憶媒体又は他の任意の非一時的媒体の中に具体化されるもの等、或る期間（例えばダイナミックＲＡＭ等のダイナミックメモリ装置のリフレッシュ期間の間の時間）にわたって媒体の物理的特性（例えば表面ピット及びランド、磁区、又は電荷）を使用してソフトウェアを非一時的な形式で記憶することができる。命令をロードすることに備えて、ソフトウェアは、（例えば汎用又は専用の計算システム又は計算装置によって読出し可能な）ＣＤ−ＲＯＭや他のコンピュータ可読媒体等の有形の非一時的媒体上に与えることができ、又はソフトウェアがそこで実行される計算システムの有形の非一時的媒体までネットワークの通信媒体上で届けられ得る（例えば伝搬信号内に符号化される）。処理の一部又は全てが専用コンピュータ上で、又はコプロセッサ、若しくは書替え可能ゲートアレイ（ＦＰＧＡ）、若しくは専用の特定用途向け集積回路（ＡＳＩＣ）等の専用ハードウェアを使用して実行され得る。処理は分散式に実装されても良く、その場合ソフトウェアによって指定される計算の異なる部分が異なる計算要素によって実行される。本明細書に記載した処理を実行するために記憶装置媒体がコンピュータによって読み出されるときコンピュータを構成し動作させるために、そのような各コンピュータプログラムは、好ましくは汎用又は専用のプログラム可能コンピュータによってアクセス可能な記憶装置のコンピュータ可読記憶媒体（例えばソリッドステートメモリ及び媒体、又は磁気媒体若しくは光学媒体）上に記憶され又はかかるコンピュータ可読記憶媒体にダウンロードされる。本発明のシステムは、コンピュータプログラムで構成される有形の非一時的媒体として実装されると考えられる場合もあり、そのように構成される媒体は本明細書に記載した処理ステップの１つ又は複数を実行するようにコンピュータを特定の且つ既定のやり方で動作させる。
【００８１】
本発明の幾つかの実施形態を説明してきた。それでもなお、上記の説明は添付の特許請求の範囲によって定める本発明の範囲を限定するのではなく例示することを目的としていることを理解すべきである。従って他の実施形態も以下の特許請求の範囲に含まれる。例えば本発明の範囲から逸脱することなしに様々な修正を加えることができる。加えて、上記のステップの一部は順序に依存しない場合があり、従って説明したのと異なる順序で実行することができる。
【図１Ａ】
2019517065.tif 000003
【図１Ｂ】
2019517065.tif 000004
【図１Ｃ】
2019517065.tif 000005
【図２】
2019517065.tif 000006
【図３】
2019517065.tif 000007
【図４】
2019517065.tif 000008
【図５】
2019517065.tif 000009
【図６】
2019517065.tif 000010
【図７】
2019517065.tif 000011
【図８】
2019517065.tif 000012
【図９】
2019517065.tif 000013
【図１０】
2019517065.tif 000014
【図１１Ａ】
2019517065.tif 000015
【図１１Ｂ】
2019517065.tif 000016
【図１１Ｃ】
2019517065.tif 000017
【図１１Ｄ】
2019517065.tif 000018
【図１１Ｅ】
2019517065.tif 000019
【図１１Ｆ】
2019517065.tif 000020
【図１１Ｇ】
2019517065.tif 000021
【図１１Ｈ】
2019517065.tif 000022
【図１１Ｉ】
2019517065.tif 000023
【国際調査報告】
2019517065.tif 000024
2019517065.tif 000025
2019517065.tif 000026