(57)【特許請求の範囲】
【請求項１】
データフィードのソースによる再送信を必要としない前記データフィードからブロードキャストされたデータユニットを管理するための方法であって、
ネットワークの第１のノードにおいて、複数のデータユニットを含む前記データフィードの少なくとも一部を受信し、前記第１のノードにおいて前記データフィードからの第１のデータユニットに基づいて第１の結果を保存するステップと、
前記ネットワークの第２のノードにおいて、前記データフィードの少なくとも一部を受信し、前記第２のノードにおいて前記データフィードからのデータに基づいて結果を保存するステップであって、前記結果が、前記第１の結果、第２の結果、及び第３の結果を含み、前記第２の結果が第２のデータユニットに基づき、前記第３の結果が第３のデータユニットに基づき、前記第２のデータユニットが前記第１のデータユニットの後及び前記第３のデータユニットの前に受信されるステップと、
前記第１のノードにおいて前記データフィードの受信の中断を判定するステップと、
前記中断の前に前記第１のノードによって受信された最後のデータユニットと前記中断の後に前記第１のノードによって受信された最初のデータユニットとの間に広がる、前記中断の結果として前記第１のノードによって受信されていない抜かされたデータユニットに対応する、データの欠落の範囲を特定するステップと、
前記第２のノードによって保存された前記結果の少なくとも一部に対する要求を前記第１のノードから送信するステップであって、前記第２のノードによって保存された前記結果の少なくとも一部が前記データの欠落に対応する、ステップと
を含み、
前記データの欠落の範囲を特定するステップが、
前記第１のノードにおいて、前記中断の後、前記第３のデータユニットを受信すること、
前記第１のノードにおいて、前記第１のデータユニットが前記中断の前に受信された前記最後のデータユニットであることを判定すること、
前記第１のノードにおいて、前記第１のデータユニットと前記第３のデータユニットとの間に広がる前記データの欠落の存在を判定し、前記第１のデータユニット及び前記第３のデータユニットと関連するそれぞれのシーケンス番号又はタイムスタンプに基づき前記データの欠落の範囲を特定すること
とを含む、前記方法。
【請求項２】
中断を判定するステップの前に、第１のノードにおいてデータフィードのデータユニットを処理して前記第１のノードにおいて前記データユニットに対応する結果を保存し、第２のノードにおいて前記データフィードのデータユニットを処理して前記第２のノードにおいて前記データユニットに対応する結果を保存するステップをさらに含む請求項１に記載の方法。
【請求項３】
データユニットを処理して前記データユニットに対応する結果を保存するステップが、前記データユニットの表現を永続的に記憶するステップを含む請求項２に記載の方法。
【請求項４】
データユニットの表現が、前記データユニットのまったくそのままのコピーである請求項３に記載の方法。
【請求項５】
データユニットの表現が、前記データユニットの圧縮された表現である請求項３に記載の方法。
【請求項６】
第１のノードにおいて、データの欠落に対応する第２のノードによって保存された結果を受信し、前記第１のノードにおいて前記結果を保存するステップをさらに含む請求項１に記載の方法。
【請求項７】
第１のノードにおいて、データの欠落に対応する第２のノードによって保存された結果を受信し、前記第１のノードにおいて第２の結果を含む前記結果を保存するステップをさらに含む請求項１に記載の方法。
【請求項８】
第１のノードから要求を送信するステップの前に、複数のノードの中から第２のノードを選択するステップであって、前記複数のノードのすべてがデータフィードをストリーミングされている、ステップをさらに含む請求項１に記載の方法。
【請求項９】
第１のノードと通信するクライアントから要求を受信するステップをさらに含む請求項１に記載の方法。
【請求項１０】
クライアントからの要求が、前記要求に関連する１又は２以上のデータユニットを特定する請求項９に記載の方法。
【請求項１１】
クライアントからの要求によって特定されたデータユニットのうちの少なくとも１つがデータの欠落の中にあると判定したことに応答して、第２のノードによって保存された結果に対する要求を第１のノードから送信するステップをさらに含む請求項１０に記載の方法。
【請求項１２】
第２のノードによって保存された結果を受信した後、クライアントからの要求に応答するステップをさらに含む請求項９に記載の方法。
【請求項１３】
クライアントからの要求に応答して前記要求を第２のノードにリダイレクトするステップをさらに含む請求項９に記載の方法。
【請求項１４】
データフィードのソースによる再送信を必要としない前記データフィードからブロードキャストされたデータユニットを管理するための、コンピュータ可読媒体上に非一時的形態で記憶されるソフトウェアであって、
ネットワークの第１のノードに、複数のデータユニットを含む前記データフィードの少なくとも一部を受信させ、前記第１のノードにおいて前記データフィードからの第１のデータユニットに基づいて第１の結果を保存させることと、
前記ネットワークの第２のノードに前記データフィードを受信させ、前記第２のノードにおいて前記データフィードからのデータに基づいて結果を保存させることであって、前記結果が、前記第１の結果、第２の結果、及び第３の結果を含み、前記第２の結果が第２のデータユニットに基づき、前記第３の結果が第３のデータユニットに基づき、前記第２のデータユニットが前記第１のデータユニットの後及び前記第３のデータユニットの前に受信させることと、
前記第１のノードに前記データフィードの受信の中断を判定させることと、
前記第１のノードに、前記中断の前に前記第１のノードによって受信された最後のデータユニットと前記中断の後に前記第１のノードによって受信された最初のデータユニットとの間に広がる、前記中断の結果として前記第１のノードによって受信されていない抜かされたデータユニットに対応する、データの欠落の範囲を特定させることと、
前記第１のノードに、前記第２のノードによって保存された前記結果の少なくとも一部に対する要求を、前記データフィードの少なくとも一部をまた受信している前記第２のノードに送信させることであって、前記第２のノードによって保存された前記結果の少なくとも一部が前記データの欠落に対応する、送信させることとのための命令を含み、
前記第１のノードに前記データの欠落の範囲を特定させることが、前記第１のノードに
前記中断の後、前記第３のデータユニットを受信させ、
前記第１のデータユニットが、最後のデータユニットであると判定させ、
前記第１のデータユニットと前記第３のデータユニットとの間に広がる前記データの欠落の存在を判定し、前記第１のデータユニット及び前記第３のデータユニットに関連するそれぞれのシーケンス番号又はタイムスタンプに基づき前記データの欠落の範囲を特定させる、
前記ソフトウェア。
【請求項１５】
データフィードのソースによる再送信を必要としない前記データフィードからブロードキャストされたデータユニットを管理するためのシステムであって、
複数のノードを含み、少なくとも第１のノード及び第２のノードが、それぞれ、
複数のデータユニットを含む前記データフィードの少なくとも一部を受信し、前記第１のノードにおいて、前記データフィードからの第１のデータユニットに基づいて第１の結果を保存し、前記第２のノードにおいて、前記データフィードからのデータに基づいて結果を保存するように構成されたネットワークインターフェースであって、前記結果が、前記第１の結果、第２の結果、及び第３の結果を含み、前記第２の結果が第２のデータユニットに基づき、前記第３の結果が第３のデータユニットに基づき、前記第２のデータユニットが前記第１のデータユニットの後及び前記第３のデータユニットの前に受信される前記ネットワークインターフェースと、
前記データフィードを処理するように構成された処理回路であって、前記処理が、前記データフィードの受信の中断を判定すること、前記中断の前に前記ノードによって受信された最後のデータユニットと前記中断の後に前記ノードによって受信された最初のデータユニットとの間に広がる、前記中断の結果として前記第１のノードによって受信されていない抜かされたデータユニットに対応する、データの欠落の範囲を特定すること、及び前記第２のノードによって保存された結果の少なくとも一部に対する要求を前記第２のノードに送信することであって、前記第２のノードによって保存された前記結果の少なくとも一部が前記データの欠落に対応する、送信することを含む、前記処理回路とを含み、
前記データの欠落の範囲を特定することが、
前記第１のノードにおいて、前記中断の後、前記第３のデータユニットを受信すること、
前記第１のノードにおいて、前記第１のデータユニットがシーケンス番号又はタイムスタンプに関連した、前記中断の前に受信された最後のデータユニットであることを判定すること、
前記第１のノードにおいて、前記第１のデータユニットと前記第３のデータユニットとの間に広がる前記データの欠落の存在を判定し、前記第１のデータユニット及び前記第３のデータユニットに関連するそれぞれのシーケンス番号又はタイムスタンプに基づき前記データの欠落の範囲を特定すること
とを含む、前記システム。
【請求項１６】
データフィードのソースによる再送信を必要としない前記データフィードからブロードキャストされたデータユニットを管理するためのシステムであって、
複数のノードを含み、少なくとも第１のノード及び第２のノードが、それぞれ、
複数のデータユニットを含む前記データフィードの少なくとも一部を受信するための手段、前記第１のノードにおいて、前記データフィードからの第１のデータユニットに基づき第１の結果を保存するための手段、及び前記第２のノードにおいて、前記データフィードからのデータに基づき結果を保存するための手段であって、前記結果が、前記第１の結果、第２の結果及び第３の結果を含み、前記第２の結果が第２のデータユニットに基づき、前記第３の結果が第３のデータユニットに基づき、前記第２のデータユニットが前記第１のデータユニットの後及び前記第３のデータユニットの前に受信される前記手段と、
前記データフィードを処理するための手段であって、前記処理が、前記データフィードの受信の中断を判定すること、前記中断の前に前記ノードによって受信された最後のデータユニットと前記中断の後に前記ノードによって受信された最初のデータユニットとの間に広がる、前記中断の結果として前記第１のノードによって受信されていない抜かされたデータユニットに対応する、データの欠落の範囲を特定すること、及び前記第２のノードによって保存された前記結果の少なくとも一部に対する要求を前記第２のノードに送信することであって、前記第２のノードによって保存された前記結果の少なくとも一部が前記データの欠落に対応する、送信することを含む、前記手段とを含み、
前記データの欠落の範囲を特定することが、
前記第１のノードにおいて、前記中断の後、前記第３のデータユニットを受信すること、
前記第１のノードにおいて、前記第１のデータユニットが前記中断の前に受信された最後のデータユニットであることを判定すること、
前記第１のノードにおいて、前記第１のデータユニットと前記第３のデータユニットとの間に広がる前記データの欠落の存在を判定し、前記第１のデータユニット及び前記第３のデータユニットに関連するそれぞれのシーケンス番号又はタイムスタンプに基づき前記データの欠落の範囲を特定すること
とを含む、前記システム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、２０１３年８月７日に出願した「MANAGING DATA FEEDS」と題した米国特許出願第６１／８６３，０６２号明細書の優先権を主張するものである。
【０００２】
この説明は、データフィードを管理することに関する。
【背景技術】
【０００３】
データフィードは、明確に定義された順序を有し、実質的に定期的にその順序で順番に送信されるデータユニットのセットを提供する。データユニットは、ネットワーク内の複数のノードにブロードキャストされるようにネットワーク上で送信される。特定のデータソースは、順序付けられたデータユニットのリアルタイムでブロードキャストされるデータフィードを出力する。そのようなリアルタイムでブロードキャストされるデータフィードの例は、時系列（time series）である。このデータフィードは、例えば、連続する時間における商品の価格を含む。
【０００４】
ネットワークのノードは、データフィードをキャプチャし、そのデータフィードを記憶することができ、したがって、クライアントがデータの選択された部分を必要とするときにそのデータフィードをストレージから取り出し、そのデータフィードをクライアントに提供することができる。ノードがキャプチャされたデータを管理するときに満たさなければならない特定の要件がある。例えば、１組の要件は、データが常に利用可能でなければならないこと、及びいかなるデータも失われてはならないことである。
【０００５】
発生する不具合は、ノードがデータフィードの一部をキャプチャし、記憶することに失敗する可能性があることである。リアルタイムでデータフィードをブロードキャストするようにのみ（つまり、再送信しない）構成されるデータソースからのリアルタイムでブロードキャストされるデータフィードに、これが起こると、見つからないデータは、そのノード及びそのノードのクライアントから永久に失われる。
【０００６】
この失敗は、例えば、ノードがそのノードのネットワーク接続を一時的に喪失するためか、又はノードが動作不可能になるか若しくはバッファの容量を使い果たすためかのどちらかの理由で起こる。これが起こるとき、ノードは、データフィードのデータの一部をキャプチャし、記憶することに失敗する可能性がある。したがって、クライアントがデータフィードの特定の部分をノードに要求するとき、ノードがデータフィードからのデータをキャプチャし、記憶することができなかった時間にかかるようにその部分が発生する場合、ノードは、要求を満たすことができない。
【発明の概要】
【課題を解決するための手段】
【０００７】
一態様においては、概して、ソースからの再送信を必要としないソースからの中断されるデータフィードのデータユニット（例えば、データユニットの完全なセット）を受信するための方法が提供される。データフィードは、ネットワークの複数のノードに送信されている。各ノードは、データフィードの少なくとも一部のデータユニットを受信するためのネットワークインターフェースと、そのノードにおいて受信されたデータユニットに対応する結果を保存するためのデータストアとに接続された処理モジュールを含む。第１のノードが、１又は２以上のデータユニットが見つからないデータフィードの不完全なコピーをキャプチャし、２つの受信されたデータユニットの間の隔たりを特定する。第１のノードは、隔たりの範囲を特定し、隔たりに対応するデータユニットの要求を送信する。
【０００８】
別の態様においては、概して、データフィードのソースによる再送信を必要としないデータフィードからブロードキャストされたデータユニットを管理するための方法。方法は、ネットワークの第１のノードにおいて、複数のデータユニットを含むデータフィードの少なくとも一部を受信するステップと、ネットワークの第２のノードにおいて、データフィードの少なくとも一部を受信するステップと、第１のノードにおいてデータフィードの受信の中断を特定するステップと、中断の前に第１のノードによって受信された最後のデータユニットと中断の後に第１のノードによって受信された最初のデータユニットとの間に広がるデータの欠落の範囲を特定するステップと、第２のノードによって保存された結果の要求を第１のノードから送信するステップであって、第２のノードによって保存された結果がデータの欠落に対応する、ステップとを含む。
【０００９】
態様は、以下の特徴のうちの１又は２以上を有する可能性がある。
【００１０】
方法は、中断を特定するステップの前に、第１のノードにおいてデータフィードのデータユニットを処理して第１のノードにおいてデータユニットに対応する結果を保存し、第２のノードにおいてデータフィードのデータユニットを処理して第２のノードにおいてデータユニットに対応する結果を保存するステップをさらに含む。
【００１１】
データユニットを処理してデータユニットに対応する結果を保存するステップは、データユニットの表現を永続的に記憶するステップを含む。
【００１２】
最初のデータユニットの表現は、最初のデータユニットのまったくそのままのコピーである。
【００１３】
最初のデータユニットの表現は、最初のデータユニットの圧縮された表現である。
【００１４】
方法は、第１のノードにおいて、データの欠落に対応する第２のノードによって保存された結果を受信し、第１のノードにおいて結果を保存するステップをさらに含む。
【００１５】
方法は、第１のノードにおいて、第１のノードにおけるデータフィードからの第１のデータユニットに基づいて第１の結果を保存するステップ、第２のノードにおいて、第２のノードにおけるデータフィードからのデータに基づいて結果を保存するステップであって、結果が第１の結果、第２の結果、及び第３の結果を含み、第２の結果が第２のデータユニットに基づき、第３の結果が第３のデータユニットに基づき、第２のデータユニットが第１のデータユニットの後及び第３のデータユニットの前に受信される、ステップをさらに含む。データの欠落の範囲を特定するステップは、第１のノードにおいて、中断の後、第３のデータユニットを受信するステップと、第１のノードにおいて、第１のデータユニットが中断の前に受信された最後のデータユニットであることを特定するステップと、第１のノードにおいて、第１のデータユニットと第３のデータユニットとの間に広がるデータの欠落の存在を特定するステップとを含む。
【００１６】
方法は、第１のノードにおいて、データの欠落に対応する第２のノードによって保存された結果を受信し、第１のノードにおいて第２の結果を含む結果を保存するステップをさらに含む。
【００１７】
方法は、第１のノードから要求を送信するステップの前に、複数のノードの中から第２のノードを選択するステップであって、複数のノードのすべてがデータフィードをストリーミングされている、ステップをさらに含む。
【００１８】
方法は、第１のノードと通信するクライアントから要求を受信するステップをさらに含む。
【００１９】
クライアントからの要求は、要求に関連する１又は２以上のデータユニットを特定する。
【００２０】
方法は、クライアントからの要求によって特定されたデータユニットのうちの少なくとも１つがデータの欠落の中にあると判定したことに応答して、第２のノードによって保存された結果の要求を第１のノードから送信するステップをさらに含む。
【００２１】
方法は、第２のノードによって保存された結果を受信した後、クライアントからの要求に応答するステップをさらに含む。
【００２２】
方法は、クライアントからの要求に応答して要求を第２のノードにリダイレクトするステップをさらに含む。
【００２３】
別の態様においては、概して、データフィードのソースによる再送信を必要としないデータフィードからブロードキャストされたデータユニットを管理するためのソフトウェアが、コンピュータ可読媒体上に非一時的形態で記憶される。ソフトウェアは、ネットワークの第１のノードに、複数のデータユニットを含むデータフィードの少なくとも一部を受信させることと、ネットワークの第２のノードにデータフィードを受信させることと、第１のノードにデータフィードの受信の中断を特定させることと、第１のノードに、中断の前に第１のノードによって受信された最後のデータユニットと中断の後に第１のノードによって受信された最初のデータユニットとの間に広がるデータの欠落の範囲を特定させることと、第１のノードに、第２のノードによって保存された結果の要求をデータフィードの少なくとも一部をやはり受信していた第２のノードに送信させることであって、第２のノードによって保存された結果がデータの欠落に対応する、送信させることとのための命令を含む。
【００２４】
別の態様においては、概して、データフィードのソースによる再送信を必要としないデータフィードからブロードキャストされたデータユニットを管理するためのシステムが、複数のノードを含む。少なくとも第１のノード及び第２のノードは、それぞれ、複数のデータユニットを含むデータフィードの少なくとも一部を受信するように構成されたネットワークインターフェースと、データフィードを処理するように構成された少なくとも１つのプロセッサとを含む。処理は、データフィードの受信の中断を特定することと、中断の前にノードによって受信された最後のデータユニットと中断の後にノードによって受信された最初のデータユニットとの間に広がるデータの欠落の範囲を特定することと、別のノードによって保存された結果の要求を別のノードに送信することであって、別のノードによって保存された結果がデータの欠落に対応する、送信することとを含む。
【００２５】
別の態様においては、概して、データフィードのソースによる再送信を必要としないデータフィードからブロードキャストされたデータユニットを管理するためのシステムが、複数のノードを含む。少なくとも第１のノード及び第２のノードは、それぞれ、複数のデータユニットを含むデータフィードの少なくとも一部を受信するための手段と、データフィードを処理するための手段であって、処理が、データフィードの受信の中断を特定すること、中断の前にノードによって受信された最後のデータユニットと中断の後にノードによって受信された最初のデータユニットとの間に広がるデータの欠落の範囲を特定すること、及び別のノードによって保存された結果の要求を別のノードに送信することであって、別のノードによって保存された結果がデータの欠落に対応する、送信することを含む、手段とを含む。
【００２６】
態様は、以下の利点のうちの１又は２以上を含む可能性がある。
【００２７】
データフィードからデータを復元できないように失う確率を少なくする１つの方法は、複数の受信ノードのそれぞれがデータを同時に受信し、すべてが計画通りに動いているときにデータをキャプチャする複数の受信ノードを設けることである。データの一部をキャプチャすることに失敗し、したがって、データの要求された部分をクライアントに供給することができないノードが、クライアントを別のノードにリダイレクトすることができる。もちろん、そのノードはデータの要求された部分を提供することがやはりできないが、データを受信するノードが多くあるほど、データがそれらのノードのいずれによってもキャプチャされない可能性がより低くなることがあり得る。長期的に、各ノードは、いつかは、見つからないデータを生じる何らかの故障に見舞われる可能性が高い。したがって、いかなるさらなるステップも行われない場合、いつかは、いかなる単一のノードも、現在の時間から何らかの任意の以前の開始時間までのすべての期間にわたるデータの完全な組を持たなくなる可能性が高い。しかしながら、本明細書において説明される技術を用いれば、データが見つからないときを速やかに検出し、見つからないデータを正確に特定することが可能である。そして、この能力は、各ノードがそのノードのデータセット内のデータの欠落を検出し、見つからないデータによってデータの欠落を埋めるために必要とされるデータの要求をその他のノードに対して行うノードの自己治癒システムを提供するために使用され得る。
【００２８】
本発明のその他の特徴及び利点は、以下の説明及び請求項から明らかになるであろう。
【図面の簡単な説明】
【００２９】
【図１】ノードのセットがリアルタイムでブロードキャストされる、共通のデータフィードを同時に受信するネットワーク図である。
【図２】データの欠落した送信されるリアルタイムでブロードキャストされるデータフィード及び対応する記憶されるデータフィードの時間プロットを示す図である。
【図３】図１に示されたノードのセットからの典型的なノードの構造ブロック図である。
【図４】図１に示されたノードのセットの中の特定のノードによって実行される方法のフローチャートである。
【図５】１対のノードの間の通信を示す１対のタイムラインである。
【発明を実施するための形態】
【００３０】
データの管理のためのシステムが、ネットワーク１２に接続された複数のノード１０Ａ、１０Ｂ．．．１０Ｚを含む。通常動作中、ノード１０Ａ、１０Ｂ．．．１０Ｚのそれぞれは、データフィード１４が入手可能なネットワーク１２へのそれぞれの対応する接続１４Ａ、１４Ｂ．．．１４Ｚを介してデータフィード１４を同時に受信する。このデータフィード１４は、任意の２つのデータユニット１８、２０が与えられると２つのデータユニット１８、２０の間のデータの欠落２２を特定することが可能である特性を有する、図２に示される、順番に送信されるデータユニットのセットを含む。そのようなデータフィード１４の状況で、「データの欠落」は、例えば、データユニットに関する一連の暗黙的な又は明示的な識別子の間の隔たりに基づくなど、何らかの既知の方法で特定可能である、２つのデータユニットの間の欠落（つまり、埋められていない空間又は間隔）に対応する。
【００３１】
そのようなデータフィード１４の例は、データユニットのそれぞれがシーケンス番号又はタイムスタンプでタグ付けされるデータユニットのフィードである。１ずつ増える整数のシーケンス番号の場合、あるノードがデータユニットｍを受信し、次に続く受信されたデータユニットがデータユニットｍ＋ｋである場合、そのノードは、ｋ−１個の見つからないデータユニットがなければならないということだけでなく、それらの見つからないデータユニットがデータユニットｍ＋１からｍ＋ｋ−１までであったに違いないということも判定することができる。その他の場合は、データユニットが一定の時間間隔で期待される場合を含み、その場合、２つのデータユニット及び（例えば、関連するタイムスタンプからの）それらのデータユニットの関連する時間が与えられると、ノードは、データユニットが期待され、既知の一定の時間間隔に基づいてデータの欠落２２の範囲を計算することができる。
【００３２】
ノード１０Ａ、１０Ｂ．．．１０Ｚなどのネットワークのノードの例は、（複数のプロセッサコアを有する）中央演算処理装置（ＣＰＵ，central processing unit）、ＣＰＵのプロセッサコア、又はＦＰＧＡ、又はその他のプログラミング可能な若しくは専用の論理回路である、処理回路の制御の下にあるサーバなどのコンピューティングシステムである。処理回路は、潜在的に中間ネットワーク（例えば、ローカルエリアネットワーク（ＬＡＮ，local area network）及び／又は広域ネットワーク（ＷＡＮ，wide-area network））を介してネットワーク上で通信するためのネットワークインターフェースを含む。ここで、図３を参照すると、この例において、ノード１０Ａは、データフィード１４からの送信されたデータユニットのセットが記憶されたデータユニット２４のセットとして記憶されるデータストレージ２０を含むか、又はデータストレージ２０に接続される。データストレージ２０は、データユニットを永続的に記憶するように構成される場合、データユニット２４が、たとえ（電源の喪失などの）ノード１０Ａの動作の中断があったとしても、例えば、不揮発性ストレージ媒体を使用するデータストレージ２０によって、提供された通りに後で取り出されることを可能にする。場合によっては、記憶されたデータユニット２４のセットは、データフィード１４からの送信されたデータユニットのセットのコピーである。しかし、その他の場合、記憶されたデータユニット２４のセットは、データフィード１４からの送信されたデータユニットが処理されたもの（versions）を含む。例えば、記憶されたデータユニットは、送信されたデータユニットの圧縮されたものであることも、抽出された特定の関連する値及び／又は引きはがされた（stripped）特定のオーバーヘッド情報を有することもある。
【００３３】
記憶されたデータユニット２４のセットは送信されたデータユニットのセットと一致しないことがあり得る。例えば、これは、停電が原因でノード１０Ａが動かなくなる場合、又はネットワーク接続が中断される場合に起こり得る。これは、記憶されたデータユニット２４のセットの中の１又は２以上のデータの欠落２２を生じる結果となる。
【００３４】
そのようなデータの欠落２２の存在を検出するために、欠落ディテクタ２６が、記憶されたデータユニット２４のセットを調べる。欠落ディテクタ２６は、データ送信の特徴の情報（knowledge）に基づいて無理なく計算される任意の方法でそのようにして、データの欠落を検出する。例えば、欠落ディテクタ２６は、一定の間隔で、又は中断ディテクタ２８から中断を検出したことに応答してのどちらかで、記憶されたデータユニットのセットを調べる。
【００３５】
その他の場合、図１に示されるクライアント３０が、特定のデータを要求する可能性がある。クライアント３０は、ネットワーク１２の別のノードである可能性があり、又はたとえクライアントがネットワーク１２への一定の接続を持たないとしてもメッセージによってネットワーク１２のノードのいずれかと通信することができるデバイス若しくはシステム（例えば、ユーザのコンピュータシステム若しくは端末）である可能性がある。クライアント３０は、例えば、地理的な近さ又は現在の負荷に基づいてデータを要求すべき特定のノード１０Ａを選択する可能性がある。要求されたデータがデータの欠落にかかることが、起こり得る。そのような場合、クライアントの要求が、要求されたデータにデータの欠落２２がないことを確かめるためにクライアント３０によって要求されているデータを調べるように欠落ディテクタ２６をトリガする。要求されたデータに少なくとも１つのデータの欠落２２がある場合、ノード１０Ａは、以下でより詳細に説明されるように、データの欠落２２のデータユニットに対応する保存された結果をネットワーク１２の第２のノード１０Ｂに要求する。ノード１０Ａは、データの欠落２２が修復された後、クライアントの要求に応答する可能性があり、又はそのノード１０Ａにおけるデータの欠落２２が修復されている間、ネットワーク１２の別のノードにクライアントの要求をリダイレクトする可能性がある。
【００３６】
データの欠落を検出すると、欠落ディテクタ２６は、ノード間コミュニケータ３２に与えられる要求３０を組み立てる。要求３０は、任意の検出されたデータの欠落２２の指定を含む。そして、ノード間コミュニケータ３２が、要求を第２のノード１０Ｂに送信する。その第２のノード１０Ｂは、中断の結果として抜かされたデータユニットを含む記憶されたデータユニットのセットを有する可能性があり又は有さない可能性がある。第２のノード１０Ｂは、必要とされるデータを持っている場合、その必要とされるデータを第１のノード１０Ａに送り返す。そうでない場合、第２のノード１０Ｂは、やはり必要とされるデータを有する可能性があり又は有さない可能性がある第３のノード１０Ｃに要求を再送信する。この手順は、最終的にノードが必要とされるデータを有するまで継続する。
【００３７】
場合によっては、第２のノード１０Ｂが、必要とされるデータのすべてではないが一部を有する可能性がある。その場合、第２のノード１０Ｂは、その第２のノード１０Ｂが何を有するかを第１のノード１０Ａに送信し、残りに関する第３のノード１０Ｃへのメッセージを、残りが第３のノード１０Ｃにおいて利用可能である場合に残りを第１のノード１０Ａに送信する命令とともに組み立てる。この手順は、最終的にすべての見つからないデータが得られるまで継続する。
【００３８】
原則として、見つからないデータがノード１０Ａ〜１０Ｚの全体で発見され得ない可能性があり、その場合、ノード１０Ａは、クライアント３０にエラーを報告する。しかし、これは、可能性が非常に低い事態であるはずである。
【００３９】
データフィードを管理するための手順の例であるフローチャート４０を示す図４を参照する。通常動作（４２）中、ノード１０Ａが、データフィードを受信し、クライアントの要求に応答する。データフィードの受信の中断を特定すること（４４）に応じて、ノード１０Ａは、欠落修復手順を実行する。欠落ディテクタ２６は、データ内の中断前に受信された最後のデータユニットＸｍを特定することによってデータの欠落２２の範囲を特定する（４６）。そして、欠落ディテクタ２６は、データの取得の再開後に受信された最初のデータユニットＸｍ＋ｋを特定する。それから、欠落ディテクタ２６は、データユニットＸｍからＸｍ＋ｋ−１を特定する抜かされたデータの要求を組み立て、その要求を第２のノード１０Ｂに送信する（４８）ためにその要求をノード間コミュニケータ３２に与える。一部の実装形態においては、各ノードが、その他のノードの支援なしにデータフィードの受信の中断を判定する（４４）役割を担う。その他の実装形態において、データフィードの受信の中断を判定するステップ（４４）は、ネットワークのその他のノードによって容易にされ得る。例えば、マスターノードが、その他のノードによって使用されるデータストレージデバイスを周期的に検査し、記憶されたデータユニットのそれらのその他のノードのそれぞれの組内のデータの欠落を検出するように構成される可能性がある。そのとき、マスターノードは、ノードと通信して中断のそれらのノードの特定及び／又はそれらのノードのデータの欠落のそれらのノードの特定を助ける可能性がある。ノードがサーバである場合、マスターノードは、例えば、一群のサーバで実行される分散型の合意アルゴリズムでリーダーとして選ばれたサーバである可能性がある。
【００４０】
最終的に、第１のノード１０Ａは、抜かされたデータの一部又はすべてを、第２のノード１０Ｂか又は（例えば、第２のノード１０Ｂもデータユニットのいずれかを見つけられない場合）別のノード１０Ｚかのどちらかから受信する。ノード１０Ａは、抜かされたデータを用いてデータの欠落２２を修復する（５０）。抜かされたデータは、抜かされたデータをデータの欠落２２に書き込む欠落修復ユニット３６に与えられ、したがって、データの欠落２２の範囲を狭めるか、又は場合により、与えられた抜かされたデータの範囲によっては、データの欠落２２を完全になくす。そして、ノード１０Ａは、通常動作（４２）に戻る。
【００４１】
図５は、データの欠落が特定され、修復される例示的な筋書きにおけるアクション及びノード１０Ａとノード１０Ｂとの間の通信に関するタイムラインを示す。各ノードは、タイムラインの上から下に向かって時間が増すときにデータフィードを受信する。ノード１０Ａは、データユニットの受信が再開した後、データフィードの中断を判定する（５００）。ノード１０Ａは、データの欠落５０４の範囲を特定する（５０２）。ノード１０Ａは、要求を送信し（５０６）、それよりわずか後に、データの欠落５０４がノード１０Ａによって受信されたデータユニットに起きていなかったならば受信され、処理されたであろうデータユニットの範囲５１０に対応する保存された結果をノード１０Ｂから受信する（５０８）。
【００４２】
上述のデータフィードの管理手法は、例えば、好適なソフトウェア命令を実行するプログラミング可能なコンピューティングシステムを用いて実装される可能性があり、又はフィールドプログラマブルゲートアレイ（ＦＰＧＡ，field-programmable gate array）などの好適なハードウェアで、若しくは何らかの混成の形態で実装される可能性がある。例えば、プログラミングされる手法において、ソフトウェアは、それぞれが少なくとも１つのプロセッサ、（揮発性及び／又は不揮発性メモリ及び／又はストレージ要素を含む）少なくとも１つのデータストレージシステム、（少なくとも１つの入力デバイス又はポートを用いて入力を受け取るため、及び少なくとも１つの出力デバイス又はポートを用いて出力を与えるための）少なくとも１つのユーザインターフェースを含む（分散、クライアント／サーバ、又はグリッドなどのさまざまなアーキテクチャである可能性がある）１又は２以上のプログラミングされた又はプログラミング可能なコンピューティングシステムで実行される１又は２以上のコンピュータプログラムの手順を含み得る。ソフトウェアは、例えば、データフローグラフの設計、構成、及び実行に関連するサービスを提供するより大きなプログラムの１又は２以上のモジュールを含む可能性がある。プログラムのモジュール（例えば、データフローグラフの要素）は、データリポジトリに記憶されたデータモデルに準拠するデータ構造又はその他の編成されたデータとして実装され得る。
【００４３】
ソフトウェアは、ＣＤ−ＲＯＭ又は（例えば、汎用若しくは専用のコンピューティングシステム若しくはデバイスによって読み取り可能な）その他のコンピュータ可読媒体などの有形の非一時的媒体で提供されるか、或いはそのソフトウェアが実行されるコンピューティングシステムの有形の非一時的媒体にネットワークの通信媒体を介して配信される（例えば、伝播信号で符号化される）可能性がある。処理の一部又はすべては、専用のコンピュータで、又はコプロセッサ若しくはフィールドプログラマブルゲートアレイ（ＦＰＧＡ）若しくは専用の特定用途向け集積回路（ＡＳＩＣ，application-specific integrated circuit）などの専用のハードウェアを用いて実行される可能性がある。処理は、ソフトウェアによって指定された計算の異なる部分が異なる計算要素によって実行される分散された方法で実装される可能性がある。それぞれのそのようなコンピュータプログラムは、本明細書において説明された処理を実行するためにストレージデバイスの媒体がコンピュータによって読み取られるときにコンピュータを構成し、動作させるために、汎用又は専用のプログラミング可能なコンピュータによってアクセス可能なストレージデバイスのコンピュータ可読ストレージ媒体（例えば、ソリッドステートメモリ若しくは媒体、又は磁気式若しくは光学式媒体）に記憶されるか又はダウンロードされることが好ましい。本発明のシステムは、コンピュータプログラムで構成された有形の非一時的媒体として実装されると考えられる可能性もあり、そのように構成された媒体は、本明細書において説明された処理ステップのうちの１又は２以上を実行するために特定の予め定義された方法でコンピュータを動作させる。
【００４４】
本発明のいくつかの実施形態が、説明された。しかしながら、上述の説明は、添付の請求項の範囲によって画定される本発明の範囲を例示するように意図されており、限定するように意図されていないことを理解されたい。したがって、その他の実施形態も、添付の請求項の範囲内にある。例えば、本発明の範囲を逸脱することなくさまざまな修正がなされ得る。さらに、上述のステップの一部は、順序に依存しない可能性があり、したがって、説明された順序とは異なる順序で実行され得る。
【図１】
0006434021.tif 000002
【図２】
0006434021.tif 000003
【図３】
0006434021.tif 000004
【図４】
0006434021.tif 000005
【図５】
0006434021.tif 000006