(57)【特許請求の範囲】
【請求項１】
ストリームデータが複数に断片化された断片化データを処理するサーバとしてのコンピュータを、
ＫＶＳ（Key Value Store）のＩＤ（Identifier）空間において前記ストリームデータの時系列に沿い、かつ、隣接して配置されるように、複数の前記断片化データの各々を、複数の前記サーバの各々に格納するデータ格納手段、
マスタとなる前記断片化データのレプリカを生成するレプリカ生成手段、として機能させ、
前記データ格納手段に、前記ＩＤ空間において、前記マスタを格納する前記サーバに隣接する前記サーバに、前記レプリカを格納させ、
複数の前記サーバのいずれかにアクセスがあった場合、自身の前記サーバに格納されており、時系列的に連続している前記マスタおよび前記レプリカを当該サーバに処理させる、
ための負荷分散プログラム。
【請求項２】
前記レプリカ生成手段に、前記マスタに対応する複数のレプリカを生成させ、
前記データ格納手段に、前記ＩＤ空間において、前記マスタを格納する前記サーバに連続的に隣接する前記サーバの各々に、前記複数のレプリカの各々を格納させる、
ことを特徴とする請求項１に記載の負荷分散プログラム。
【請求項３】
ストリームデータが複数に断片化された断片化データを処理するサーバであって、
ＫＶＳのＩＤ空間において前記ストリームデータの時系列に沿い、かつ、隣接して配置されるように、複数の前記断片化データの各々を複数の前記サーバの各々に格納するデータ格納部と、
マスタとなる前記断片化データのレプリカを生成するレプリカ生成部と、を備え、
前記データ格納部が、前記ＩＤ空間において、前記マスタを格納する前記サーバに隣接する前記サーバに、前記レプリカを格納し、
複数の前記サーバのいずれかにアクセスがあった場合、自身の前記サーバに格納されており、時系列的に連続している前記マスタおよび前記レプリカを処理する、
ことを特徴とするサーバ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストリームデータなどのメディアデータの分散処理の技術に関する。
【背景技術】
【０００２】
近年、ＨＴＴＰ（Hypertext Transfer Protocol）を利用したストリーミング配信が普及しており、ＭＰＥＧ（Moving Picture Experts Group）−ＤＡＳＨ（Dynamic Adaptive Streaming over HTTP）や、ＨＬＳ（HTTP Live Streaming）などの動画配信プロトコルが整備されている。これらのプロトコルによれば、ストリームデータを断片化し、断片化したストリームデータ（断片化ファイル）を時系列順に読み取って、ストリーム処理が行われる。
【０００３】
ストリーム処理においては、ストリームデータからさまざまな情報を抽出するための認識処理が重要である。認識処理では、１つの時間的フレーム（断片化ファイルに対応）に対して処理を行うために、過去のフレームに対して処理して得られた処理結果（認識処理の状態）が用いられる場合がある。認識処理では、例えば、一般的にＨＭＭ（Hidden Markov Model：隠れマルコフモデル）が用いられる。ＨＭＭにおける認識処理の状態とは、時系列的に直前までのフレームに対して認識処理を実行して得られた隠れ状態の最尤遷移系列の集合をいう。また、認識処理にて、所定の時系列的なフィードバック／フォワードを伴う処理を行ってもよい。
【０００４】
非特許文献１には、多数のサーバから構成されるクラスタシステムにて大規模分散処理を実行するためのアルゴリズムであるマップリデュース（MapReduce）について開示されている。例えば、認識処理を行うＡＰＬ（Application：アプリケーション）が動作するサーバの各々に、断片化ファイル振り分けて分散処理を行うことで、負荷分散されたストリーミング配信を実現することができる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Jeffrey Dean and Sanjay Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters”, COMMUNICATIONS OF THE ACM January 2008/Vol.51, No.1 (2008年)
【発明の概要】
【発明が解決しようとする課題】
【０００６】
クラスタシステムにてストリーム処理を行う場合、認識処理の状態をサーバ間でやり取りする必要がある。図１１には、ストリームデータを分割した断片化ファイル（ｍ０〜ｍ４）のいずれか１つを格納する５つのサーバにて、認識処理を行うＡＰＬを並行に動作させた場合の様子が示されている。ｍ０，ｍ１，ｍ２，ｍ３，ｍ４という順番は、時系列順に一致する。このｍ０，ｍ１，ｍ２，ｍ３，ｍ４という順番でストリーム処理が行われることに合わせて、認識処理の状態（図１１では「状態」と示す。）が他のサーバへ引き継がれる。しかし、認識処理の状態の引き継ぎが頻繁に行われると、ストリーム処理の処理時間が長期化してしまったり、認識処理の状態のデータ量が多い場合にはクラスタシステム内のネットワークを圧迫してしまったりする、という問題がある。断片化ファイル（ｍ０〜ｍ４）を１つの特定サーバに格納すれば（集中管理方式）、認識処理の状態の引き継ぎに起因する上記の問題を回避することはできる。しかし、このような方式は、特定サーバのメモリ容量を非常に圧迫してしまったり、クラスタシステムのスケーラビリティを損ねてしまったりすることになるため、採用できない。非特許文献１には、これらの問題について何ら言及していない。
【０００７】
そこで、本発明は、上記事情に鑑みて、分散処理を行うクラスタシステムのスケーラビリティを確保しつつ、ストリーム処理の処理時間を短縮させることを課題とする。
【課題を解決するための手段】
【０００８】
前記課題を解決するために、請求項１に記載の発明は、ストリームデータが複数に断片化された断片化データを処理するサーバとしてのコンピュータを、ＫＶＳ（Key Value Store）のＩＤ（Identifier）空間において前記ストリームデータの時系列に沿い、かつ、隣接して配置されるように、複数の前記断片化データの各々を複数の前記サーバの各々に格納するデータ格納手段、マスタとなる前記断片化データのレプリカを生成するレプリカ生成手段、として機能させ、前記データ格納手段に、前記ＩＤ空間において、前記マスタを格納する前記サーバに隣接する前記サーバに、前記レプリカを格納させ、複数の前記サーバのいずれかにアクセスがあった場合、自身の前記サーバに格納されており、時系列的に連続している前記マスタおよび前記レプリカを当該サーバに処理させる、ための負荷分散プログラムである。
【０００９】
また、請求項３に記載の発明は、ストリームデータが複数に断片化された断片化データを処理するサーバであって、ＫＶＳのＩＤ空間において前記ストリームデータの時系列に沿い、かつ、隣接して配置されるように、複数の前記断片化データの各々を複数の前記サーバの各々に格納するデータ格納部と、マスタとなる前記断片化データのレプリカを生成するレプリカ生成部と、を備え、前記データ格納部が、前記ＩＤ空間において、前記マスタを格納する前記サーバに隣接する前記サーバに、前記レプリカを格納し、複数の前記サーバのいずれかにアクセスがあった場合、自身の前記サーバに格納されており、時系列的に連続している前記マスタおよび前記レプリカを処理する、ことを特徴とする。
【００１０】
請求項１，３に記載の発明によれば、マスタとレプリカとを区別しなければ、時系列的にある程度連続した複数の断片化データを、複数のサーバの各々に格納することができる。サーバは、時系列的に連続した複数の断片化データに対しては、一括でストリーム処理を実行することができる。その際、認識処理の状態を他のサーバに渡す必要が無いため、認識処理の状態の頻繁な引き継ぎに起因して、ストリーム処理の処理時間が長期化することはない。また、認識処理の状態のデータ量が多い場合であっても、クラスタシステム内のネットワークをそれほど圧迫することもない。また、集中管理方式とは異なり、複数のサーバのいずれにアクセスがあったとしても、必要となる断片化データを格納していないサーバは、当該断片化データを格納している他のサーバに認識処理の状態を渡し、ストリーム処理を完了させることができる。つまり、レプリカの断片化ファイルが存在しているサーバであれば処理することが可能であるため、ボトルネックを回避できる。これらにより、クラスタシステムのスケーラビリティを損ねることはない。
したがって、分散処理を行うクラスタシステムのスケーラビリティを確保しつつ、ストリーム処理の処理時間を短縮させることができる。
【００１１】
また、請求項２に記載の発明は、請求項１に記載の負荷分散プログラムであって、前記レプリカ生成手段に、前記マスタに対応する複数のレプリカを生成させ、前記データ格納手段に、前記ＩＤ空間において、前記マスタを格納する前記サーバに連続的に隣接する前記サーバの各々に、前記複数のレプリカの各々を格納させる、ことを特徴とする。
【００１２】
請求項２に記載の発明によれば、冗長化数が増大するほど、複数のサーバの各々は、自身が格納するマスタに対して、時系列的に連続した複数の断片化データのレプリカを数多く格納することができる。よって、マスタとレプリカとを区別しなければ、より高い頻度で、一括でストリーム処理を実行することができ、認識処理の状態を他のサーバに渡す必要性を低減させることができる。
【発明の効果】
【００１３】
本発明によれば、分散処理を行うクラスタシステムのスケーラビリティを確保しつつ、ストリーム処理の処理時間を短縮させることができる。
【図面の簡単な説明】
【００１４】
【図１】本実施形態のクラスタシステムの例の概要図である。
【図２】クラスタシステムを構成するサーバの例の機能構成図である。
【図３】（ａ）は１次元ハッシュ空間の例の説明図、（ｂ）は各サーバに格納されたマスタおよびレプリカのいずれかである断片化ファイルの連続性についての説明図である。
【図４】（ａ）はサーバ１０−０に対しアクセスした場合のストリーム処理の説明図、（ｂ）はサーバ１０−２に対しアクセスした場合のストリーム処理の説明図である。
【図５】ＨＬＳにおけるメディアアップロード時に実行される処理の例を示すシーケンス図である。
【図６】ＨＬＳにおけるメディアアップロード時に実行される処理の例を示すシーケンス図である。
【図７】ＨＬＳにおけるメディアアップロード時に実行される処理の例を示すシーケンス図である。
【図８】ＨＬＳにおけるメディアダウンロード時に実行される処理の例を示すシーケンス図である。
【図９】ストリーム処理時に実行される処理の例を示すシーケンス図である。
【図１０】ストリーム処理時に実行される処理の例を示すシーケンス図である。
【図１１】認識処理の状態がサーバで頻繁に引き継がれる様子を示す図である。
【発明を実施するための形態】
【００１５】
本発明を実施するための形態（実施形態）について、図面を参照しながら詳細に説明する。
【００１６】
（全体構成）
図１に示すように、本実施形態のクラスタシステム１は、ストリーム処理を行う複数のサーバ１０−０〜１０−４を備えており、ネットワークを介して、クライアントＣと通信可能に接続されている。クラスタシステム１が備えるサーバの個数は、特に限定されない。
【００１７】
クライアントＣは、例えば、ストリーミング配信を行う配信端末、または、配信されるストリームデータを視聴するユーザのユーザ端末である。クライアントＣは、クラスタシステム１に対し、入力クエリを含む入力データを送信する。入力クエリは、例えば、データベースからデータを取得するための要求である。クラスタシステム１は、クライアントＣに対し、入力データに対応する出力データを送信する。
【００１８】
サーバ１０−０〜１０−４は、１つのストリームデータを時系列で複数に分割した断片化ファイル４０−０〜４０−４（断片化データ）のいずれかを、例えば、図１に示すように有している。図１中の「ｍ０」〜「ｍ４」は、断片化ファイル４０−０〜４０−４のファイル名である。断片化ファイル４０−０〜４０−４は、マスタ（原本）であり、本実施形態の図面では、実線で描く。「ｍ０」〜「ｍ４」は、ＫＶＳ（Key Value Store）システムにおける断片化ファイル４０−０〜４０−４（Value）のキー（Key）となる。ｍ０，ｍ１，ｍ２，ｍ３，ｍ４をこの順でつなぎ合わせたものは１つのストリームデータに相当する。断片化ファイル４０−０〜４０−４およびこれらのファイル名「ｍ０」〜「ｍ４」は、例えば、メディアアップロード時に、配信端末であるクライアントＣから送信される、断片化ファイルに関する入力データに含まれる。
【００１９】
クラスタシステム１において、マスタである断片化ファイル４０−０〜４０−４を冗長化して、レプリカとなる断片化ファイル４１−０〜４１−４が生成される（詳細は後記）。断片化ファイル４１−０〜４１−４の各々は、サーバ１０−０〜１０−４のいずれかに格納され、例えば、図１に示したように格納される。断片化ファイル４１−０〜４１−４にもファイル名「ｍ０」〜「ｍ４」が付され、本実施形態の図面では、破線で描く。
【００２０】
サーバ１０−０〜１０−４は、ストリームデータの断片化ファイルを指し示すインデックスファイル３０−０〜３０−３を有することができる。インデックスファイル３０−０〜３０−３は、例えば、図１に示すようにサーバ１０−０〜１０−３に格納されている。サーバ１０−４のように、インデックスファイルを有しないサーバが存在していてもよい。
【００２１】
インデックスファイル３０−２は、「ｍ０」〜「ｍ４」が付された断片化ファイル４０−０〜４０−４を指すインデックスを定めたファイルである。図１中の「ｍ」は、インデックスファイル３０−３のインデックスファイル名であり、例えば、断片化前のストリームデータの名称とすることができる。
インデックスファイル３０−３は、インデックスファイル３０−２（マスタ）を冗長化したインデックスファイル（レプリカ）である。
インデックスファイル３０−０は、「ｍ０」〜「ｍ４」からなるストリームデータとは異なるストリームデータの断片化ファイル（図示せず）を指すインデックスを定めたファイルである。図１中の「ｎ」は、インデックスファイル３０−０のインデックスファイル名である。
インデックスファイル３０−１は、インデックスファイル３０−０（マスタ）を冗長化したインデックスファイル（レプリカ）である。
【００２２】
ＡＰＬ２０−０〜２０−４は、ストリーム処理を実行するためのアプリケーションであり、サーバ１０−０〜１０−４の各々が備える。ＡＰＬ２０−０〜２０−４は、ストリームデータに対して認識処理を行い、認識処理の状態などである処理結果は、ＡＰＬ２０−０〜２０−４に記述される。また、ＡＰＬ２０−０〜２０−４は、例えば、メディアアップロード時に、配信端末であるクライアントＣから送信される、インデックスファイルに関する入力データに含まれるインデックスファイル名を用いて、インデックスファイル３０−０〜３０−３を作成することができる。
【００２３】
サーバ１０−０〜１０−４は、互いに連携して振分部Ｄを形成することができる。振分部Ｄは、クライアントＣからの入力データをサーバ１０−０〜１０−４のいずれかに振り分けて処理し、処理結果となる出力データをクライアントＣに送信する分散処理機構である。振分部Ｄは、例えば、ラウンドロビンによって入力データをサーバ１０−０〜１０−４のいずれかにランダムに振り分けるロードバランサ（図示せず）を備えることができる。また、入力データをロードバランサから受信したサーバ１０−０〜１０−４は、当該入力データが処理担当のデータであれば処理し、処理担当でなければ処理担当となる他のサーバ１０−０〜１０−４に転送する機能を有することができる（詳細は後記）。このような機能も振分部Ｄの一部を構成する。
【００２４】
（サーバの構成）
図２を参照してサーバの機能構成について説明する。ここでは、サーバ１０−０を例に説明する。
図２に示すように、サーバ１０−０は、処理部１１、通信部１２、および、記憶部１３を備える。
【００２５】
通信部１２は、通信回線を介して情報を送受信する通信インターフェースによって構成され、内部バスなどを介して処理部１１に接続されている。処理部１１は、振分部Ｄ（図１）のロードバランサを介してクライアントＣや、他のサーバ１０−１〜１０−４と、情報の送受信を行うことができる。
【００２６】
記憶部１３は、例えば、ハードディスク、フラッシュメモリ、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）などの記憶装置である。記憶部１３は、例えば、各サーバ１０−ｎ（ｎ：自然数）を一意に識別するサーバＩＤ（Identifier）、ストリームデータの断片化ファイルのマスタおよびレプリカ、インデックスファイル、ストリーム処理を行うためのＡＰＬを実現するプログラム（負荷分散プログラム）を記憶する。サーバ１０−ｎのサーバＩＤは、例えば、所定個の英数字列、ＩＰ（Internet Protocol）アドレス、または、ＭＡＣ（Media Access Control）アドレスとすることができる。
【００２７】
処理部１１は、サーバ１０−０が実行する処理の全体を司る。処理部１１は、例えば、記憶部１３が記憶するプログラムをＣＰＵ（Central Processing Unit）が記憶部１３のＲＡＭに展開して実行することによって実現される。処理部１１は、構文解析部１１１、サーバ決定部１１２、データ格納部１１３（データ格納手段）、および、レプリカ生成部１１４（レプリカ生成手段）と、いった機能部を備えており、ストリーム処理を行うためのＡＰＬと同等である。
【００２８】
構文解析部１１１は、通信部１２から入力データを取得し、入力データの内容を構文解析する。例えば、構文解析部１１１は、インデックスファイルまたは断片化ファイルに対する、取得要求（ＧＥＴ）、作成・置換要求（ＰＵＴ）などのメソッドのいずれであるかを解析することができる。また、取得要求（ＧＥＴ）については、さらに、ＫＶＳのKeyの完全一致検索、Keyの範囲検索、Valueの完全一致検索、Valueの範囲検索のいずれであるかを解析する。構文解析部１１１は、構文解析の解析結果を、サーバ決定部１１２に引き渡す。
【００２９】
サーバ決定部１１２は、構文解析部１１１の解析結果に基づいて、取得した入力データの振り分け先となるサーバを決定する。サーバ決定部１１２は、断片化ファイル４０−ｎ（ｎ：自然数）に関する入力データに含まれる断片化ファイル名、および、各サーバ１０−ｎのサーバＩＤの両者の対応付けを予め設定しておくことで、新たに取得した断片化ファイルをどのサーバに振り分けるべきかを決定することができる。
【００３０】
具体的な方法として、サーバ決定部１１２は、断片化ファイル名、および、サーバＩＤを、ＫＶＳのＩＤ空間上で順序が定義された特定の値に変換するための計算をすることができる。例えば、サーバ決定部１１２は、ハッシュ関数を用いて、断片化ファイル名のハッシュ値、および、サーバＩＤのハッシュ値を計算し、これらのハッシュ値を１次元ハッシュ空間に配置することができる。なお、断片化ファイル名については、断片化ファイル名そのものをハッシュ値とすることができ、ハッシュ関数を必要とせずに済ませることができる。
【００３１】
データ格納部１１３は、断片化ファイル４０−ｎの各々を、サーバ決定部１１２が決定したサーバ１０−ｎに格納する。データ格納部１１３は、断片化ファイル４０−ｎの格納先が当該データ格納部１１３を備えるサーバ１０−ｎでない場合には、通信部１２を介して、格納先となるサーバ１０−ｎに転送する。
【００３２】
レプリカ生成部１１４は、マスタとなる断片化ファイル４０−ｎのレプリカを生成する。レプリカ生成部１１４は、１つのマスタに対して、１つ以上のレプリカを生成することができる。また、レプリカ生成部１１４は、マスタとなる１つのインデックスファイルに対して、１つ以上のレプリカを生成することができる（図１参照）。また、レプリカ生成部１１４は、マスタとなる他の種類のファイル（例えば、後記する結果ファイル５０ａ（図９））に対して、１つ以上のレプリカを生成することができる。
【００３３】
図３（ａ）に示すように、サーバ決定部１１２が利用する１次元ハッシュ空間は、コンシステントハッシュ環として表現することができる。コンシステントハッシュ環上には、断片化ファイル名のハッシュ値、および、サーバＩＤのハッシュ値が配置される。コンシステントハッシュ環の時計回り方向は、ハッシュ値の昇順に一致する。
【００３４】
サーバ１０−０〜１０−３のサーバＩＤのハッシュ値は、コンシステントハッシュ環上の図３（ａ）に示す位置に配置されるとする（ハッシュ値の大小関係は、サーバ１０−０＜サーバ１０−１＜サーバ１０−２＜サーバ１０−３）。すると、コンシステントハッシュ環は、各サーバ１０−０〜１０−３によって所定長の円孤に区切られ、レンジ０〜３を形成することができる。
【００３５】
レンジ０は、サーバ１０−０のサーバＩＤのハッシュ値からサーバ１０−１のサーバＩＤのハッシュ値の直前のハッシュ値までのハッシュ値の範囲であり、サーバ１０−０の担当領域である。レンジ０に配置されるハッシュ値を持つデータは、サーバ１０−０に格納される。
レンジ１は、サーバ１０−１のサーバＩＤのハッシュ値からサーバ１０−２のサーバＩＤのハッシュ値の直前のハッシュ値までのハッシュ値の範囲であり、サーバ１０−１の担当領域である。レンジ１に配置されるハッシュ値を持つデータは、サーバ１０−１に格納される。
レンジ２は、サーバ１０−２のサーバＩＤのハッシュ値からサーバ１０−３のサーバＩＤのハッシュ値の直前のハッシュ値までのハッシュ値の範囲であり、サーバ１０−２の担当領域である。レンジ２に配置されるハッシュ値を持つデータは、サーバ１０−２に格納される。
レンジ３は、サーバ１０−３のサーバＩＤのハッシュ値からサーバ１０−０のサーバＩＤのハッシュ値の直前のハッシュ値までのハッシュ値の範囲であり、サーバ１０−３の担当領域である。レンジ３に配置されるハッシュ値を持つデータは、サーバ１０−３に格納される。
【００３６】
ここで、サーバ１０−０〜１０−３のデータ格納部１１３は、１つのストリームデータを時系列順にｍ０〜ｍ３に断片化した断片化ファイル４０−０〜４０−３の各々が、１次元ハッシュ空間（ＫＶＳのＩＤ空間）においてストリームデータの時系列に沿い、かつ、隣接して配置されるように、断片化ファイル４０−０〜４０−３の各々をサーバ１０−０〜１０−３の各々に格納する。つまり、ｍ０の断片化ファイル４０−０のハッシュ値（ｍ０とする）をレンジ０に配置することで断片化ファイル４０−０をサーバ１０−０に格納させた場合、ｍ０に続くｍ１の断片化ファイル４０−１のハッシュ値（ｍ１（＞ｍ０）とする）をレンジ０に連続するレンジ１に配置して断片化ファイル４０−１をサーバ１０−１に格納させる。そして、ｍ１に続くｍ２の断片化ファイル４０−２のハッシュ値（ｍ２（＞ｍ１）とする）をレンジ１に連続するレンジ２に配置して断片化ファイル４０−２をサーバ１０−２に格納させ、ｍ２に続くｍ３の断片化ファイル４０−３のハッシュ値（ｍ３（＞ｍ２）とする）をレンジ２に連続するレンジ３に配置して断片化ファイル４０−３をサーバ１０−３に格納させる。
【００３７】
上記のような格納形態をとるために、サーバ１０−０〜１０−３のＡＰＬ２０−０〜２０−３は、ｍ０〜ｍ３からなるストリームデータに対して作成したインデックスファイルに、断片化ファイル４０−０〜４０−３のハッシュ値（ｍ０〜ｍ３）をそれぞれ、レンジ０〜レンジ３に含めるように決定する。
【００３８】
サーバ１０−０〜１０−３のデータ格納部１１３は、自身のサーバの担当領域の断片化ファイルをクライアントＣから取得した場合には、そのまま記憶部１３に格納し、担当領域外の断片化ファイルを取得した場合には、通信部１２を介して担当領域を持つ他のサーバに転送する。
【００３９】
サーバ１０−０〜１０−３のレプリカ生成部１１４は、マスタとなる断片化ファイル４０−０〜４０−３のレプリカを生成する。ここでは、１つのマスタに対して２つのレプリカが生成される場合について説明する（冗長化数３）。なお、この説明は、４以上の冗長化数にもあてはまる。
【００４０】
図３（ａ）に示すように、サーバ１０−０は、レプリカ生成部１１４によって、自身の担当領域レンジ０内のハッシュ値（ｍ）を持つ断片化ファイル４０−０（マスタ。実線表示。）に対して、２つのレプリカ（破線表示）となる断片化ファイル４１−０、４２−０を生成する。ここで、サーバ１０−０のデータ格納部１１３は、サーバ１０−０に隣接するサーバ１０−１に、つまり、自身の担当領域レンジ０に連続するレンジ１を持つサーバ１０−１に、１つ目のレプリカとなる断片化ファイル４１−０を格納する。さらに、サーバ１０−０のデータ格納部１１３は、サーバ１０−１に隣接するサーバ１０−２に、つまり、自身の担当領域レンジ０に連続するレンジ１にさらに連続するレンジ２を持つサーバ１０−２に、２つ目のレプリカとなる断片化ファイル４２−０を格納する。
【００４１】
マスタとなる断片化ファイル４０−１〜４０−３についても、上記の断片化ファイル４０−０の場合と同様にして、レプリカとなる断片化ファイル４１−１〜４１−３、４２−１〜４２−３が生成される（図３（ａ）では図示を省略）。
サーバ１０−１のデータ格納部１１３は、サーバ１０−１に隣接するサーバ１０−２に、１つ目のレプリカとなる断片化ファイル４１−１を格納し、さらに、サーバ１０−２に隣接するサーバ１０−３に、２つ目のレプリカとなる断片化ファイル４２−１を格納する。
サーバ１０−２のデータ格納部１１３は、サーバ１０−２に隣接するサーバ１０−３に、１つ目のレプリカとなる断片化ファイル４１−２を格納し、さらに、サーバ１０−３に隣接するサーバ１０−０に、２つ目のレプリカとなる断片化ファイル４２−２を格納する。
サーバ１０−３のデータ格納部１１３は、サーバ１０−３に隣接するサーバ１０−０に、１つ目のレプリカとなる断片化ファイル４１−３を格納し、さらに、サーバ１０−０に隣接するサーバ１０−１に、２つ目のレプリカとなる断片化ファイル４２−３を格納する。
【００４２】
コンシステントハッシュ環を横直線にし、サーバ１０−０〜サーバ１０−３に断片化ファイル４０−０〜４０−３、４１−０〜４１−３、４２−０〜４２−３を格納した様子を図３（ｂ）に示す。例えば、サーバ１０−２は、ｍ２を持つマスタの断片化ファイル４０−２だけでなく、ｍ２の直前の値ｍ１を持つレプリカの断片化ファイル４１−１、および、ｍ１の直前の値ｍ０を持つレプリカの断片化ファイル４２−０も格納している。このことは、マスタとレプリカとの区別をしなければ、ｍ０，ｍ１，ｍ２といった時系列的に連続した３つの断片化ファイルに対して、１つのサーバ１０−２が一括にストリーム処理を実行することができることを意味する。
【００４３】
本来、断片化ファイルのレプリカはクラスタシステム１の耐障害性を向上させるために生成され、ストリーム処理を実行することは無い。これに対し、本発明では、断片化ファイルのレプリカに対するストリーム処理の実行を許可する。その結果、サーバ１０−２は、ｍ０，ｍ１，ｍ２といった時系列的に連続した３つの断片化ファイルに対して一括にストリーム処理を実行することができる。このような取り扱いは、他のサーバ１０−０，１０−１，１０−３にも適用する。図３（ｂ）には、一括にストリーム処理を実行することができる対象となる断片化ファイルの集合を点線の囲みで示している。
【００４４】
本実施形態のクラスタシステム１は、サーバ１０−０〜１０−３のいずれのサーバに対しアクセスがあった場合でも、ｍ０，ｍ１，ｍ２，ｍ３の断片化ファイルに対してこの順でストリーム処理を実行することができる。
【００４５】
例えば、図４（ａ）に示すように、サーバ１０−０に対しアクセスがあった場合、まず、サーバ１０−０が、ｍ０を持つマスタの断片化ファイル４０−０に対してストリーム処理を実行する。次に、ｍ１を持つ断片化ファイルのストリーム処理を実行する必要があるが、サーバ１０−０は、サーバ決定部１１２によって、このストリーム処理を実行するサーバとして、マスタおよびレプリカの区別をしなければｍ１，ｍ２，ｍ３を持つ断片化ファイルを記憶するサーバ１０−３を決定することができる。
【００４６】
サーバ１０−０のＡＰＬ２０−０は、断片化ファイル４０−０のストリーム処理を実行したときの認識処理の結果を、状態５０としてサーバ１０−３に渡す。サーバ１０−３は、サーバ１０−０から状態５０を引き継いだ後、ｍ１，ｍ２，ｍ３を持つ断片化ファイル４２−１，４１−２，４０−３に対して、この順でストリーム処理を実行する。図４（ａ）には、サーバ１０−０，１０−３間で、ｍ０，ｍ１，ｍ２，ｍ３の断片化ファイルに対して実行されたストリーム処理が白抜きの矢印で示されている。
【００４７】
上記のように、マスタとレプリカとを区別しなければ、１つのサーバが、時系列的に連続した断片化ファイルに対してストリーム処理を実行することができるので、認識処理の状態を他のサーバに引き継がせる回数を低減させることができる。従来では、複数の断片化ファイルに対して複数のサーバで分散処理を行う場合に、認識処理の状態が複数のサーバ間で頻繁に引き継がれていたため、ストリーム処理の処理時間が長期化してしまったり、認識処理の状態のデータ量が多い場合にはクラスタシステム内のネットワークを圧迫してしまったりする、という問題があった（図１１参照）。本実施形態では、このような問題を緩和することができる。
【００４８】
なお、例えば、ｍ０を持つマスタの断片化ファイル４０−０に対してストリーム処理を実行したサーバ１０−０のＡＰＬ２０−０は、状態５０をサーバ１０−１に渡すこともできる。しかし、この場合、状態５０を引き継いだサーバ１０−１は、ｍ２を持つ断片化ファイルを記憶していないため、ｍ１を持つマスタの断片化ファイル４０−０に対してストリーム処理を実行した後、ｍ２を持つ断片化ファイルを記憶する他のサーバ（１０−０，１０−２，１０−３）にさらに状態５０を渡す必要がある。また、ＡＰＬ２０−０は、状態５０をサーバ１０−２に渡すこともできる。しかし、この場合、状態５０を引き継いだサーバ１０−２は、ｍ３を持つ断片化ファイルを記憶していないため、ｍ１，ｍ２を持つ断片化ファイル４１−１，４０−２に対してストリーム処理を実行した後、ｍ３を持つ断片化ファイルを記憶する他のサーバ（１０−０，１０−１，１０−３）にさらに状態５０を渡す必要がある。このような状態５０の度重なる引き継ぎは、ストリーム処理の処理時間が長期化や、クラスタシステム内のネットワークの圧迫を招きやすいので、特段の事情がない限り、回避することが好ましい。
【００４９】
また、例えば、図４（ｂ）に示すように、サーバ１０−２に対しアクセスがあった場合、まず、サーバ１０−２が、ｍ０，ｍ１，ｍ２を持つ断片化ファイル４２−０、４１−１，４０−２に対してストリーム処理を、状態５０を他のサーバ渡すことなく一括で実行することができる。次に、ｍ３を持つ断片化ファイルを記憶していないサーバ１０−２は、サーバ決定部１１２によって、例えば、ｍ３を持つ断片化ファイルを記憶するサーバとして、サーバ１０−１を決定することができる。
【００５０】
サーバ１０−２のＡＰＬ２０−２は、ｍ０，ｍ１，ｍ２を持つ断片化ファイル４２−０、４１−１，４０−２のストリーム処理を実行したときの認識処理の結果を、状態５０としてサーバ１０−１に渡す。サーバ１０−１は、サーバ１０−２から状態５０を引き継いだ後、ｍ３を持つ断片化ファイル４２−３に対してストリーム処理を実行する。図４（ｂ）には、サーバ１０−２，１０−１間で、ｍ０，ｍ１，ｍ２，ｍ３の断片化ファイルに対して実行されたストリーム処理が白抜きの矢印で示されている。
【００５１】
図４（ａ）（ｂ）に示した手順と同様の手順に従って、サーバ１０−１に対しアクセスがあった場合、および、サーバ１０−３に対しアクセスがあった場合についても、状態５０の引き継ぎ回数を抑えながら、ｍ０，ｍ１，ｍ２，ｍ３の断片化ファイルに対してこの順でストリーム処理を実行することができる。このように、サーバ１０−０〜１０−３のすべてを稼働させて、状態５０の引き継ぎの回数を抑えたままで、ストリーム処理を実行することができるので、１つのストリームデータを処理する際に特定のサーバに負荷が集中してしまうという事態を解消することができる。
【００５２】
すでに説明した、１つの特定サーバに一通りの断片化ファイルを格納する集中管理方式では、１つのストリームデータのストリーム処理を実行するときのパイプラインの数は１（またはレプリカを生成している場合は冗長化数）に限定されてしまい、クラスタシステムのスケーラビリティが損なわれていた。これに対して、本実施形態のクラスタシステム１は、１つのストリームデータのストリーム処理を実行するときのパイプラインの数は、冗長化数×サーバ数に等しくなり、高いスケーラビリティを獲得することができる。
【００５３】
（処理）
次に、本実施形態のクラスタシステム１にて実行される処理について説明する。ここでは、動画配信プロトコルとして、ＨＬＳを用いた場合について説明するが、他の種類の動画配信プロトコルについても適用することができる。また、説明の便宜上、クラスタシステム１を構成するサーバの数は３とし、冗長化数は２とする（断片化ファイルの１つのマスタに対して生成するレプリカの数は１）。本実施形態の処理は、ＨＬＳにおけるメディアアップロード時（図５、図６、図７）、ＨＬＳにおけるメディアダウンロード時（図８）、ストリーム処理時（図９、図１０）の順に進行する。
なお、図５、図６、図７、図８、図９、図１０中のサーバ１０−０〜１０−２に含まれる振分部Ｄは、サーバごとに描かれているが、１つの機能部である。
【００５４】
＜ＨＬＳにおけるメディアアップロード時＞
図５〜図７を参照して、ＨＬＳにおけるメディアアップロード時の処理について説明する。図５〜図７の処理は、ステップＡ１から開始する。
図５のステップＡ１にて、クライアントＣ（ここでは、ストリーミング配信を行う配信端末）が、振分部Ｄに、“HTTP/GET m.m3u8?new=3”というリクエスト行を含む入力データを送信する。入力データの振分先は、振分部Ｄのロードバランサ（図示せず）によってランダムにサーバ１０−０に決定される。このリクエスト行は、インデックスファイル名ｍが付されたインデックスファイル（m.m3u8）をサーバ１０−０〜１０−２に要求する。このとき、“new=3”とあるので、このインデックスファイルに、３つの断片化ファイルの３つの断片化ファイル名が格納されることになる（１つのストリームデータを３つの断片化ファイルに断片化する）。
なお、上記の“HTTP/GET m.m3u8?new=3”というリクエスト行は、実際には所定のＵＲＩ（Uniform Resource Identifier）をさらに含んでいるが、説明の便宜上、本明細書では、そのＵＲＩの表記は省略して説明する。また、本明細書では、他のリクエスト行に関する説明をするが、そのリクエスト行においてもＵＲＩの表記は省略する。
【００５５】
ステップＡ２にて、振分部Ｄが、サーバ１０−０のＡＰＬ２０−０に、当該入力データを送信する。ＡＰＬ２０−０は、構文解析部１１１によって、入力データを構文解析し、入力データ中のリクエスト行のＵＲＩからインデックスファイル名ｍを抽出する。また、ＡＰＬ２０−０は、サーバ決定部１１２によって、抽出したインデックスファイル名ｍをＫＶＳのキーとして、該当サーバ（本処理では、サーバ１０−１とする。）に入力データを振り分けるように決定する。
【００５６】
ステップＡ３にて、サーバ１０−０のＡＰＬ２０−０が、振分部Ｄに、当該入力データを送信する。
ステップＡ４にて、振分部Ｄが、サーバ１０−１に、当該入力データを振り分けるように制御する。
【００５７】
ステップＡ５にて、振分部Ｄが、サーバ１０−１のＡＰＬ２０−１に、当該入力データを送信する。ＡＰＬ２０−１は、構文解析部１１１によって、入力データを構文解析し、インデックスファイル名ｍのインデックスファイルが既に存在するか否かを確認する。このとき、入力データのリクエスト行の“new=3”に基づいて、３つの断片化ファイル名が格納されるインデックスファイルが既に存在するか否かを確認する。インデックスファイル名ｍのインデックスファイルが既に存在する場合、以下のステップＡ６〜Ａ８が実行される。
【００５８】
もし、インデックスファイル名ｍのインデックスファイルが存在しない場合、インデックスファイル名ｍのインデックスファイルを新たに作成して、作成したインデックスファイルに３つの断片化ファイル名を新たに格納する。このとき、データ格納部１１３によって、新たな３つの断片化ファイル名が付される断片化ファイルの各々が、１次元ハッシュ空間においてストリームデータの時系列に沿い、かつ、隣接して配置され、サーバ１０−０〜１０−２の各々に格納可能となるように、新たな３つの断片化ファイル名がハッシュ値として決定される。この決定は、例えば、図３にて説明した、コンシステントハッシュ環を用いた方式に従う。本処理では、新たに作成されるインデックスファイル名ｍのインデックスファイル３０に格納される３つのハッシュ値を決定し、それに基づく断片化ファイル名も決定する。ここでは、ハッシュ値を0011.ts,1023.ts,4021.tsとする。但し、一般にハッシュ値からファイル名を算出（逆演算）することは困難なことが多いため、その場合はハッシュ値をそのままファイル名とする。なお、ハッシュ値からファイル名を算出（逆演算）することを困難とする事情が特にない場合には、ファイル名とハッシュ値とを一致させる必要はない。その場合、ファイル名からハッシュ値が計算される。説明の便宜上、ハッシュ値0011.ts,1023.ts,4021.tsの各々を、単に、0011,1023,4021と表記する場合があるが同じ意味である。また、以下の説明においては、ハッシュ値をファイル名として決定したものとする。この決定の後、以下のステップＡ９以降の処理が実行される。
【００５９】
ステップＡ６にて、サーバ１０−１のＡＰＬ２０−１が、振分部Ｄに、ステータスコード３０３（See Other）、および、既に存在しているインデックスファイル名ｍのインデックスファイル３０ａを送信する。
ステップＡ７にて、振分部Ｄが、サーバ１０−０に、当該ステータスコード３０３、および、当該インデックスファイル３０ａを振り分けるように制御する。
ステップＡ８にて、振分部Ｄが、クライアントＣに、当該ステータスコード３０３、および、当該インデックスファイル３０ａを送信する。クライアントＣは、リクエスト行内のインデックスファイル名ｍを別の名前に変えて、ステップＡ１から再実行する。
【００６０】
ステップＡ９にて、サーバ１０−１のＡＰＬ２０−１が、振分部Ｄに、ステータスコード２００（OK）、および、新たに作成したインデックスファイル名ｍのインデックスファイル３０を送信する。
ステップＡ１０にて、振分部Ｄが、サーバ１０−０に、当該ステータスコード２００、および、当該インデックスファイル３０を振り分けるように制御する。
ステップＡ１１にて、振分部Ｄが、クライアントＣに、当該ステータスコード２００、および、当該インデックスファイル３０を送信する。クライアントＣは、送信した入力データに対応する出力データとして当該インデックスファイル３０を取得することができる。
以下、ステップＡ１１にてクライアントＣが取得したインデックスファイル３０について説明を続ける。
【００６１】
図６に進み、ステップＡ１２にて、クライアントＣが、振分部Ｄに、例えば、“HTTP/PUT 0011.ts”というリクエスト行を含む入力データ、および、ファイル名としてのハッシュ値0011が付された断片化ファイル４０ａを送信する。入力データ、および、断片化ファイル４０ａの振分先は、振分部Ｄのロードバランサ（図示せず）によってランダムにサーバ１０−２に決定される。このリクエスト行は、ハッシュ値0011が付された断片化ファイル４０ａをサーバ１０−０〜１０−２のいずれかに格納するように要求する。
【００６２】
ステップＡ１３にて、振分部Ｄが、サーバ１０−２のＡＰＬ２０−２に、当該入力データ、および、当該断片化ファイル４０ａを送信する。ＡＰＬ２０−２は、構文解析部１１１によって、入力データを構文解析し、入力データ中のリクエスト行のＵＲＩから断片化ファイル名0011.tsを抽出する。また、ＡＰＬ２０−２は、サーバ決定部１１２によって、抽出した断片化ファイルのハッシュ値0011をＫＶＳのキーとして、該当サーバ（本処理では、サーバ１０−０とする。）に入力データを振り分けるように決定する。
【００６３】
ステップＡ１４にて、サーバ１０−２のＡＰＬ２０−２が、振分部Ｄに、当該入力データ、および、当該断片化ファイル４０ａを送信する。
ステップＡ１５にて、振分部Ｄが、サーバ１０−０に、当該入力データ、および、当該断片化ファイル４０ａを振り分けるように制御する。
【００６４】
ステップＡ１６にて、振分部Ｄが、サーバ１０−０のＡＰＬ２０−０に、当該入力データ、および、当該断片化ファイル４０ａを送信する。ＡＰＬ２０−０は、構文解析部１１１によって、入力データを構文解析し、当該断片化ファイル４０ａのハッシュ値0011がサーバ１０−０の１次元ハッシュ空間上のレンジ内にあることを確認する。ＡＰＬ２０−０は、データ格納部１１３によって、断片化ファイル４０ａのマスタをサーバ１０−０の記憶部１３に格納する。
【００６５】
ステップＡ１７にて、サーバ１０−０のＡＰＬ２０−０が、振分部Ｄに、断片化ファイル４０ａのレプリカを送信する。このとき、ＡＰＬ２０−０は、レプリカ生成部１１４によって、断片化ファイル４０ａのレプリカを生成し、データ格納部１１３によって、断片化ファイル４０ａのレプリカの送信先を、１次元ハッシュ空間において、断片化ファイル４０ａのマスタを格納するサーバ１０−０に隣接するサーバ１０−１と決定することができる。
【００６６】
ステップＡ１８にて、振分部Ｄが、サーバ１０−１のＡＰＬ２０−１に、当該断片化ファイル４０ａのレプリカを送信する。ＡＰＬ２０−１は、データ格納部１１３によって、断片化ファイル４０ａのレプリカ（後記で、符号４１ａで示す）をサーバ１０−１の記憶部１３に格納する。
【００６７】
ステップＡ１９にて、サーバ１０−１のＡＰＬ２０−１が、振分部Ｄに、当該断片化ファイル４０ａのレプリカの格納の完了通知を示す応答を送信する。
ステップＡ２０にて、振分部Ｄが、サーバ１０−０のＡＰＬ２０−０に、当該応答を送信する。
【００６８】
ステップＡ２１にて、サーバ１０−０のＡＰＬ２０−０が、振分部Ｄに、クライアントＣからの入力データに対して、当該断片化ファイル４０ａのマスタおよびレプリカの格納の完了通知を示すステータスコード２００（OK）を送信する。
ステップＡ２２にて、振分部Ｄが、クライアントＣに、当該ステータスコード２００（OK）を送信する。
【００６９】
図７に進み、ステップＡ２３にて、クライアントＣが、振分部Ｄに、“HTTP/PUT 1023.ts”というリクエスト行を含む入力データ、および、ファイル名としてのハッシュ値1023が付された断片化ファイル４０ｂを送信する。入力データ、および、断片化ファイル４０ｂの振分先は、振分部Ｄのロードバランサ（図示せず）によってランダムにサーバ１０−０に決定される。このリクエスト行は、ハッシュ値1023が付された断片化ファイル４０ｂをサーバ１０−０〜１０−２のいずれかに格納するように要求する。
【００７０】
断片化ファイル４０ｂに対する以降の処理の手順は、ステップＡ１３〜ステップＡ２２の手順と同様であるため説明を省略する。結果的には、断片化ファイル４０ｂのマスタは、サーバ１０−１に格納され、断片化ファイル４０ｂのレプリカ（後記で、符号４１ｂで示す）は、サーバ１０−２に格納される。
【００７１】
ステップＡ２４にて、クライアントＣが、振分部Ｄに、“HTTP/PUT 4021.ts”というリクエスト行を含む入力データ、および、ファイル名としてのハッシュ値4021が付された断片化ファイル４０ｃを送信する。入力データ、および、断片化ファイル４０ｃの振分先は、振分部Ｄのロードバランサ（図示せず）によってランダムにサーバ１０−１に決定される。このリクエスト行は、ハッシュ値4021が付された断片化ファイル４０ｃをサーバ１０−０〜１０−２のいずれかに格納するように要求する。
【００７２】
断片化ファイル４０ｃに対する以降の処理の手順は、ステップＡ１３〜ステップＡ２２の手順と同様であるため説明を省略する。結果的には、断片化ファイル４０ｃのマスタは、サーバ１０−２に格納され、断片化ファイル４０ｃのレプリカ（後記で、符号４１ｃで示す）は、サーバ１０−０に格納される。
【００７３】
ここで、断片化ファイル４０ａ，４０ｂ，４０ｃに加えてストリームがさらに続くことが無い場合には、図５〜図７によるＨＬＳにおけるメディアアップロード時の処理は終了する。一方、もし、断片化ファイル４０ａ，４０ｂ，４０ｃに加えてストリームがさらに続く場合、インデックスファイルを更新するために、以下のステップＡ２５〜ステップＡ３２の処理が実行される。
【００７４】
ステップＡ２５にて、クライアントＣ（ここでは、ストリーミング配信を行う配信端末）が、振分部Ｄに、“HTTP/GET m.m3u8?add=3”というリクエスト行を含む入力データを送信する。入力データの振分先は、振分部Ｄのロードバランサ（図示せず）によってランダムにサーバ１０−０に決定される。このリクエスト行は、インデックスファイル名ｍが付されたインデックスファイル（m.m3u8）をサーバ１０−０〜１０−２に要求する。このとき、“add=3”とあるので、このインデックスファイルに、さらに３つの断片化ファイルの３つの断片化ファイル名が追加で格納されることになる（１つのストリームデータを６つの断片化ファイルに断片化する）。
【００７５】
ステップＡ２６にて、振分部Ｄが、サーバ１０−０のＡＰＬ２０−０に、当該入力データを送信する。ＡＰＬ２０−０は、構文解析部１１１によって、入力データを構文解析し、入力データ中のリクエスト行のＵＲＩからインデックスファイル名ｍを抽出する。また、ＡＰＬ２０−０は、サーバ決定部１１２によって、抽出したインデックスファイル名ｍをＫＶＳのキーとして、該当サーバ（本処理では、サーバ１０−１とする。）に入力データを振り分けるように決定する。
【００７６】
ステップＡ２７にて、サーバ１０−０のＡＰＬ２０−０が、振分部Ｄに、当該入力データを送信する。
ステップＡ２８にて、振分部Ｄが、サーバ１０−１に、当該入力データを振り分けるように制御する。
【００７７】
ステップＡ２９にて、振分部Ｄが、サーバ１０−１のＡＰＬ２０−１に、当該入力データを送信する。ＡＰＬ２０−１は、構文解析部１１１によって、入力データを構文解析し、インデックスファイル名ｍのインデックスファイルが既に存在するか否かを確認する。ここでは、ステップＡ５にて新たに作成されたインデックスファイル３０の存在を確認することができる。
【００７８】
ＡＰＬ２０−１は、入力データのリクエスト行の“add=3”に基づいて、インデックスファイル３０に追加分の３つの断片化ファイル名を新たに格納する。このとき、データ格納部１１３によって、追加分の新たな３つの断片化ファイル名を含む計６つの断片化ファイル名が付される断片化ファイルの各々が、１次元ハッシュ空間においてストリームデータの時系列に沿い、かつ、隣接して配置され、サーバ１０−０〜１０−２の各々に格納可能となるように、追加分の新たな３つの断片化ファイル名がハッシュ値として決定される。この決定は、例えば、図３にて説明した、コンシステントハッシュ環を用いた方式に従う。なお、必要に応じて、追加分の新たな３つの断片化ファイル名の追加に伴い、既に作成した３つの断片化ファイル名を異なる名称に変更することもできる。本処理では、インデックスファイル名ｍのインデックスファイル３０に格納される追加分の３つのハッシュ値を決定し、それに基づく断片化ファイル名も決定する。ここでは、ハッシュ値を3178.ts,7429.ts,2871.tsとする。但し、一般にハッシュ値からファイル名を算出（逆演算）することは困難なことが多いため、その場合はハッシュ値をそのままファイル名とする。説明の便宜上、ハッシュ値3178.ts,7429.ts,2871.tsの各々を、単に、3178,7429,2871と表記する場合があるが同じ意味である。また、以下の説明においては、ハッシュ値をファイル名として決定したものとする。この決定の後、以下のステップＡ３０以降の処理が実行される。
【００７９】
ステップＡ３０にて、サーバ１０−１のＡＰＬ２０−１が、振分部Ｄに、ステータスコード２００（OK）、および、追加分の３つのハッシュ値を格納したインデックスファイル名ｍのインデックスファイル３０を送信する。
ステップＡ３１にて、振分部Ｄが、サーバ１０−０に、当該ステータスコード２００、および、当該インデックスファイル３０を振り分けるように制御する。
ステップＡ３２にて、振分部Ｄが、クライアントＣに、当該ステータスコード２００、および、当該インデックスファイル３０を送信する。クライアントＣは、送信した入力データに対応する出力データとして当該インデックスファイル３０を取得することができる。
【００８０】
その後、すでに説明したハッシュ値0011,1023,4021を持つ断片化ファイルをサーバ１０−０〜１０−２に格納するための手順と同様の手順で、ハッシュ値3178,7429,2871を持つ断片化ファイルが、サーバ１０−０〜１０−２のいずれかに格納される。
【００８１】
図５〜図７に示す、ＨＬＳにおけるメディアアップロード時の処理によれば、クライアントＣから送信される断片化ファイル４０ａ，４０ｂ，４０ｃのマスタおよびレプリカを、サーバ１０−０〜１０−２の各々に、ストリーム処理時の認識処理の状態の引き継ぎの回数が抑制されるように格納することができる。
なお、図５〜図７には示していないが、レプリカ生成部１１４によって、マスタとなるインデックスファイル３０のレプリカが生成され、例えば、インデックスファイル３０を記憶するサーバ１０−１とは異なるサーバ１０−０，１０−２のいずれかに記憶される。
また、本実施形態では、メソッドがＰＵＴであるリクエスト行を含む入力データについて説明した（ステップＡ１２（図６）、ステップＡ２３（図７）、ステップＡ２４（図７））が、ＰＵＴの代わりにＰＯＳＴを用いることができる。
【００８２】
＜ＨＬＳにおけるメディアダウンロード時＞
次に、図８を参照して、ＨＬＳにおけるメディアダウンロード時の処理について説明する。
なお、図５〜図７の処理によって、サーバ１０−０は、断片化ファイル名0011.tsが付され、マスタとなる断片化ファイル４０ａ、および、断片化ファイル名4021.tsが付され、レプリカとなる断片化ファイル４１ｃを格納している。
また、サーバ１０−１は、断片化ファイル名0011.tsが付され、レプリカとなる断片化ファイル４１ａ、および、断片化ファイル名1023.tsが付され、マスタとなる断片化ファイル４０ｂを格納している。
また、サーバ１０−２は、断片化ファイル名1023.tsが付され、レプリカとなる断片化ファイル４１ｂ、および、断片化ファイル名4021.tsが付され、マスタとなる断片化ファイル４０ｃを格納している。
また、図７のステップＡ２５〜ステップＡ３２の処理はなされず、インデックスファイル３０には、断片化ファイル名0011.ts,1023.ts,4021.tsの３つが格納されているとする。
図８の処理は、ステップＢ１から開始する。
【００８３】
ステップＢ１にて、クライアントＣ（ここでは、ストリームデータを視聴するユーザのユーザ端末）が、振分部Ｄに、“HTTP/GET m.m3u8”というリクエスト行を含む入力データを送信する。入力データの振分先は、振分部Ｄのロードバランサ（図示せず）によってランダムにサーバ１０−０に決定される。このリクエスト行は、インデックスファイル名ｍが付されたインデックスファイル（m.m3u8）をサーバ１０−０〜１０−２に要求する。
【００８４】
ステップＢ２にて、振分部Ｄが、サーバ１０−０のＡＰＬ２０−０に、当該入力データを送信する。ＡＰＬ２０−０は、構文解析部１１１によって、入力データを構文解析し、入力データ中のリクエスト行のＵＲＩからインデックスファイル名ｍを抽出する。また、ＡＰＬ２０−０は、サーバ決定部１１２によって、抽出したインデックスファイル名ｍをＫＶＳのキーとして、該当サーバ（本処理では、サーバ１０−１とする。）に入力データを振り分けるように決定する。
【００８５】
ステップＢ３にて、サーバ１０−０のＡＰＬ２０−０が、振分部Ｄに、当該入力データを送信する。
ステップＢ４にて、振分部Ｄが、サーバ１０−１に、当該入力データを振り分けるように制御する。
【００８６】
ステップＢ５にて、振分部Ｄが、サーバ１０−１のＡＰＬ２０−１に、当該入力データを送信する。ＡＰＬ２０−１は、構文解析部１１１によって、入力データを構文解析し、インデックスファイル名ｍのインデックスファイルが既に存在するか否かを確認する。ここでは、ステップＡ５（図５）にて新たに作成されたインデックスファイル３０の存在を確認することができる。
【００８７】
ステップＢ６にて、サーバ１０−１のＡＰＬ２０−１が、振分部Ｄに、ステータスコード２００（OK）、および、３つの断片化ファイル名を格納したインデックスファイル名ｍのインデックスファイル３０を送信する。
ステップＢ７にて、振分部Ｄが、サーバ１０−０に、当該ステータスコード２００、および、当該インデックスファイル３０を振り分けるように制御する。
ステップＢ８にて、振分部Ｄが、クライアントＣに、当該ステータスコード２００、および、当該インデックスファイル３０を送信する。クライアントＣは、送信した入力データに対応する出力データとして当該インデックスファイル３０を取得することができる。
以下、ステップＢ８にてクライアントＣが取得したインデックスファイル３０に基づいて、断片化ファイル４０ａ、４０ｂ、４０ｃの取得が実行される。
【００８８】
ステップＢ９にて、クライアントＣが、振分部Ｄに、“HTTP/GET 0011.ts”というリクエスト行を含む入力データを送信する。入力データの振分先は、振分部Ｄのロードバランサ（図示せず）によってランダムにサーバ１０−２に決定される。このリクエスト行は、ハッシュ値0011が付された断片化ファイル４０ａの取得を要求する。
【００８９】
ステップＢ１０にて、振分部Ｄが、サーバ１０−２のＡＰＬ２０−２に、当該入力データを送信する。ＡＰＬ２０−２は、構文解析部１１１によって、入力データを構文解析し、入力データ中のリクエスト行のＵＲＩから断片化ファイル名0011.tsを抽出する。また、ＡＰＬ２０−２は、サーバ決定部１１２によって、抽出した断片化ファイルのハッシュ値0011をＫＶＳのキーとして、該当サーバ（本処理では、サーバ１０−０とする。）に入力データを振り分けるように決定する。
【００９０】
ステップＢ１１にて、サーバ１０−２のＡＰＬ２０−２が、振分部Ｄに、当該入力データを送信する。
ステップＢ１２にて、振分部Ｄが、サーバ１０−０に、当該入力データを振り分けるように制御する。
【００９１】
ステップＢ１３にて、振分部Ｄが、サーバ１０−０のＡＰＬ２０−０に、当該入力データを送信する。ＡＰＬ２０−０は、構文解析部１１１によって、入力データを構文解析し、当該断片化ファイル４０ａのハッシュ値0011がサーバ１０−０の１次元ハッシュ空間上のレンジ内にあることを確認する。ＡＰＬ２０−０は、記憶部１３に格納されている断片化ファイル４０ａを取得する。
【００９２】
ステップＢ１４にて、サーバ１０−０のＡＰＬ２０−０が、振分部Ｄに、クライアントＣからの入力データに対して、当該断片化ファイル４０ａの取得の完了通知を示すステータスコード２００（OK）、および、当該断片化ファイル４０ａを送信する。
ステップＢ１５にて、振分部Ｄが、クライアントＣに、当該ステータスコード２００（OK）、および、当該断片化ファイル４０ａを送信する。
【００９３】
クライアントＣは、上記のステップＢ１〜ステップＢ１５の処理によって、断片化ファイル４０ａを取得することができる。
また、クライアントＣは、インデックスファイル３０に基づいて、ハッシュ値1023が付された断片化ファイル４０ｂ、および、ハッシュ値4021が付された断片化ファイル４０ｃについて、上記のステップＢ１〜ステップＢ１５の処理と同等の処理を繰り返す（図示は省略する）。結果的に、クライアントＣは、断片化ファイル４０ｂ、および、断片化ファイル４０ｃを取得することができる。
【００９４】
図８に示す、ＨＬＳにおけるメディアダウンロード時の処理によれば、クライアントＣであるユーザ端末は、視聴を所望するストリームデータの断片化ファイルを確実に取得することができる。
【００９５】
＜ストリーム処理時＞
次に、図９、図１０を参照して、ストリーム処理時の処理について説明する。
なお、図７のステップＡ２５〜ステップＡ３２の処理はなされず、インデックスファイル３０には、断片化ファイル名0011.ts,1023.ts,4021.tsの３つが格納されているとする。
図９、図１０の処理は、ステップＣ１から開始する。
【００９６】
図９のステップＣ１にて、クライアントＣ（ここでは、ストリームデータを視聴するユーザのユーザ端末）が、振分部Ｄに、“HTTP/GET m.m3u8?apl=a?result=b”というリクエスト行を含む入力データを送信する。入力データの振分先は、振分部Ｄのロードバランサ（図示せず）によってランダムにサーバ１０−０に決定される。このリクエスト行は、インデックスファイル名ｍが付されたインデックスファイル（m.m3u8）をサーバ１０−０〜１０−２に要求する。
このとき、“apl=a”とあるので、“a”という名称のアプリケーションを用いてストリーム処理を実行することになる。「“a”という名称のアプリケーション」は、サーバ１０−０〜１０−２が備えるＡＰＬ２０−０〜２０−２に等しい。
また、“result=b”とあるので、“b”という名称の結果ファイルに、断片化ファイルの時系列ごとのストリーム処理の処理結果を格納することになる。
【００９７】
ステップＣ２〜ステップＣ８の各々の処理は、既に説明したステップＢ２〜ステップＢ８の各々の処理と同等であるので説明を省略する。結果的には、クライアントＣは、送信した入力データに対応する出力データとして当該インデックスファイル３０を取得することができる。
【００９８】
振分部Ｄは、ストリームデータの時系列的に最初となる、0011が付された断片化ファイルを記憶するサーバを、断片化ファイルのマスタおよびレプリカを区別することなく選択する。本処理では、0011が付されたレプリカとなる断片化ファイル４１ａと、0011に連続する、1023が付されたマスタとなる断片化ファイル４０ｂと、を記憶するサーバ１０−１が有効にストリーム処理を実行することができる。このため、振分部Ｄは、サーバ１０−１を選択し、アクセスする。
【００９９】
ステップＣ９にて、振分部Ｄは、ＡＰＬ２０−１に、ストリーム処理要求を送信する。ＡＰＬ２０−１は、サーバ１０−１の記憶部１３に格納されている、0011が付されたレプリカとなる断片化ファイル４１ａと、0011に連続する、1023が付されたマスタとなる断片化ファイル４０ｂと、を読み出し、それらに対して連続的にストリーム処理を実行する。その結果、ＡＰＬ２０−１は、0011,1023に対応する連続した２つの期間におけるストリーム処理の処理結果、および、当該２つの期間における認識処理の状態を獲得する。
【０１００】
ステップＣ１０にて、ＡＰＬ２０−１は、振分部Ｄに、0011,1023に対応する連続した２つの期間における、ストリーム処理の処理結果を送信する。ストリーム処理の処理結果の振分先は、振分部Ｄのロードバランサ（図示せず）によってランダムにサーバ１０−２に決定される。
【０１０１】
ステップＣ１１にて、振分部Ｄは、サーバ１０−２のＡＰＬ２０−２に、当該ストリーム処理の処理結果を送信する。ＡＰＬ２０−２は、結果ファイル名ｂが付された結果ファイル５０ａに、当該ストリーム処理の処理結果を格納する。なお、ＡＰＬ２０−２は、振分部Ｄを介して、他のサーバ（本処理では、サーバ１０−０）に送信された、クライアントＣからの入力データを取得することができ、入力データのリクエスト行中の“result=b”を取得することができる。
【０１０２】
ステップＣ１２にて、サーバ１０−２のＡＰＬ２０−２は、振分部Ｄに、当該結果ファイル５０ａにストリーム処理の処理結果を格納したことを示す応答を送信する。
ステップＣ１３にて、振分部Ｄは、サーバ１０−１のＡＰＬ２０−１に、当該応答を送信する。
ステップＣ１４にて、サーバ１０−１のＡＰＬ２０−１は、振分部Ｄに、ストリーム処理要求に対する応答を送信する。
【０１０３】
振分部Ｄは、0011が付されたレプリカとなる断片化ファイル４１ａと、0011に連続する、1023が付されたマスタとなる断片化ファイル４０ｂとに対するストリーム処理要求の応答を受信すると、1023に続く4021が付された断片化ファイルを記憶するサーバを、断片化ファイルのマスタおよびレプリカを区別することなく選択する。本処理では、4021が付されたマスタとなる断片化ファイル４０ｃを記憶するサーバ１０−２が有効にストリーム処理を実行することができる。このため、振分部Ｄは、サーバ１０−２を選択し、アクセスする。
なお、4021が付されたレプリカとなる断片化ファイル４１ｃを記憶するサーバ１０−０を選択してもよいが、本処理では選択しない。
【０１０４】
図１０に進み、ステップＣ１５にて、振分部Ｄが、サーバ１０−１に、4021が付された断片化ファイルに対するストリーム処理要求、および、ステップＣ９にて獲得した認識処理の状態を振り分けるように制御する。
ステップＣ１６にて、振分部Ｄが、サーバ１０−２のＡＰＬ２０−２に当該ストリーム処理要求、および、当該認識処理の状態を送信する。ＡＰＬ２０−２は、サーバ１０−２の記憶部１３に格納されている4021が付されたマスタとなる断片化ファイル４０ｃを読み出し、振分部Ｄを介して受信した認識処理の状態に基づいて、ストリーム処理を実行する。その結果、ＡＰＬ２０−２は、4021に対応する期間におけるストリーム処理の処理結果、および、0011,1023,4021に対応する３つの期間における認識処理の状態を獲得する。
【０１０５】
ステップＣ１７にて、サーバ１０−２のＡＰＬ２０−２は、振分部Ｄに、4021に対応する期間におけるストリーム処理の処理結果、および、0011,1023,4021に対応する３つの期間における認識処理の状態を送信する。認識処理の状態の振分先は、結果ファイル名ｂが付された結果ファイル５０ａを有するサーバ１０−２に決定される。
【０１０６】
ステップＣ１８にて、振分部Ｄは、ＡＰＬ２０−２に、当該ストリーム処理の処理結果、および、当該認識処理の状態を送信する。ＡＰＬ２０−２は、結果ファイル名ｂが付された結果ファイル５０ａに、当該ストリーム処理の処理結果を追加的に格納する。
【０１０７】
ステップＣ１９にて、サーバ１０−２のＡＰＬ２０−２は、振分部Ｄに、当該結果ファイル５０ａにストリーム処理の処理結果を格納したことを示す応答を送信する。
ステップＣ２０にて、振分部Ｄが、サーバ１０−１に、4021が付された断片化ファイルに対するストリーム処理要求に対する応答を振り分けるように制御する。
【０１０８】
したがって、クラスタシステム１にて、0011,1023,4021が付された断片化ファイルからなるストリームデータ全体のストリーム処理が完了する。クラスタシステム１は、クライアントＣからストリームデータの処理結果を取得するための要求があるまで、待機する。
【０１０９】
ステップＣ２１にて、クライアントＣが、振分部Ｄに、“HTTP/GET result=b”というリクエスト行を含む入力データを送信する。入力データの振分先は、振分部Ｄのロードバランサ（図示せず）によってランダムにサーバ１０−０に決定される。このリクエスト行は、結果ファイル名ｂが付された結果ファイル５０ａをサーバ１０−０〜１０−２に要求する。
【０１１０】
ステップＣ２２にて、振分部Ｄが、サーバ１０−０のＡＰＬ２０−０に、当該入力データを送信する。ＡＰＬ２０−０は、構文解析部１１１によって、入力データを構文解析し、結果ファイル５０ａの取得要求があることを確認する。また、ＡＰＬ２０−０は、サーバ１０−０が結果ファイル５０ａを記憶していないことを確認する。
【０１１１】
ステップＣ２３にて、サーバ１０−０のＡＰＬ２０−０が、振分部Ｄに、当該入力データを送信する。
ステップＣ２４にて、振分部Ｄが、サーバ１０−２に、当該入力データをランダムに振り分けるように制御する。
【０１１２】
ステップＣ２５にて、振分部Ｄが、サーバ１０−２のＡＰＬ２０−２に、当該入力データを送信する。ＡＰＬ２０−２は、構文解析部１１１によって、入力データを構文解析し、結果ファイル５０ａの取得要求があることを確認する。また、ＡＰＬ２０−２は、サーバ１０−２が結果ファイル５０ａを記憶しているため、クライアントＣに結果ファイル５０ａを送信することを確認する。
【０１１３】
ステップＣ２６にて、サーバ１０−２のＡＰＬ２０−２が、振分部Ｄに、ステータスコード２００（OK）、および、結果ファイル名ｂが付された結果ファイル５０ａを送信する。
ステップＣ２７にて、振分部Ｄが、サーバ１０−０に、当該ステータスコード２００（OK）、および、当該結果ファイル名ｂが付された結果ファイル５０ａを振り分けるように制御する。
ステップＣ２８にて、振分部Ｄが、クライアントＣに、ステータスコード２００（OK）、および、結果ファイル名ｂが付された結果ファイル５０ａを送信する。
【０１１４】
図９、図１０に示す、ストリーム処理時によれば、事前に一通りの断片化ファイルを取得したクライアントＣは、結果ファイル５０ａも取得することで、ストリームデータを再生することができる。
【０１１５】
なお、図１０、図１１には示していないが、レプリカ生成部１１４によって、マスタとなる結果ファイル５０ａのレプリカが生成され、例えば、結果ファイル５０ａを記憶するサーバ１０−２とは異なるサーバ１０−０，１０−１のいずれかに記憶される。
【０１１６】
また、ステップＣ２８の処理の後、クラスタシステム１の振分部Ｄは、インデックスファイル名ｍが付されたインデックスファイル３０に、ストリーム処理がされていない断片化ファイルに付される追加分の断片化ファイル名（例えば、ステップＡ２５〜ステップＡ３２（図７）で説明した断片化ファイル名3178.ts,7429.ts,2871.ts）が含まれているか否かを確認することができる。含まれていた場合、対応する追加分の断片化ファイルに対して上記と同様の処理を実行することができる。追加分の断片化ファイル名が存在しない場合には、処理全体を終了する。
【０１１７】
（まとめ）
本実施形態によれば、マスタとレプリカとを区別しなければ、時系列的にある程度連続した複数の断片化ファイルを、複数のサーバの各々に格納することができる。サーバは、時系列的に連続した複数の断片化ファイルに対しては、一括でストリーム処理を実行することができる。その際、認識処理の状態を他のサーバに渡す必要が無いため、認識処理の状態の頻繁な引き継ぎに起因して、ストリーム処理の処理時間が長期化することはない。また、認識処理の状態のデータ量が多い場合であっても、クラスタシステム内のネットワークをそれほど圧迫することもない。また、集中管理方式とは異なり、複数のサーバのいずれにアクセスがあったとしても、必要となる断片化ファイルを格納していないサーバは、当該断片化ファイルを格納している他のサーバに認識処理の状態を渡し、ストリーム処理を完了させることができる。つまり、レプリカの断片化ファイルが存在しているサーバであれば処理することが可能であるため、ボトルネックを回避できる。これらにより、クラスタシステムのスケーラビリティを損ねることはない。
したがって、分散処理を行うクラスタシステムのスケーラビリティを確保しつつ、ストリーム処理の処理時間を短縮させることができる。
【０１１８】
また、冗長化数が増大するほど、複数のサーバの各々は、自身が格納するマスタに対して、時系列的に連続した複数の断片化ファイルのレプリカを数多く格納することができる。よって、マスタとレプリカとを区別しなければ、より高い頻度で、一括でストリーム処理を実行することができ、認識処理の状態を他のサーバに渡す必要性を低減させることができる。
【０１１９】
（変形例）
１次元ハッシュ空間において、十分な冗長化数を持たせることで、複数の断片化ファイルの各々を、ストリームデータの時系列には沿うようにするが、隣接はさせず離散的に配置されるように、複数の断片化ファイルの各々を複数のサーバの各々に格納することもできる。冗長化数が十分であるため、マスタとレプリカとを区別しなければ、時系列的にある程度連続した複数の断片化ファイルを、複数のサーバの各々に持たせることができ、一括のストリーム処理を実行させることができる。
【０１２０】
メディアストリームデータに限らず、XML（Extensible Markup Language）等のストリームデータについても本発明を適用することができる。
分散処理の方法は、コンシステントハッシュ環を用いたコンシステントハッシュ方に限られず、他の方法を適用することもできる。
【０１２１】
本実施形態で説明した種々の技術を適宜組み合わせた技術を実現することもできる。
本実施形態で説明したソフトウェアをハードウェアとして実現することもでき、ハードウェアをソフトウェアとして実現することもできる。
その他、ハードウェア、ソフトウェア、フローチャートなどについて、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【０１２２】
１      クラスタシステム
Ｃ      クライアント
Ｄ      振分部
１０−０〜１０−４  サーバ
２０−０〜２０−４  ＡＰＬ
３０−０〜３０−３  インデックスファイル
４０−０〜４０−４  （マスタとなる）断片化ファイル（断片化データ）
４１−０〜４１−４  （レプリカとなる）断片化ファイル（断片化データ）
４２−０〜４１−３  （レプリカとなる）断片化ファイル（断片化データ）
１１    処理部
１２    通信部
１３    記憶部
１１１  構文解析部
１１２  サーバ決定部
１１３  データ格納部（データ格納手段）
１１４  レプリカ生成部（レプリカ生成手段）
【図１】
0006408433.tif 000002
【図２】
0006408433.tif 000003
【図３】
0006408433.tif 000004
【図４】
0006408433.tif 000005
【図５】
0006408433.tif 000006
【図６】
0006408433.tif 000007
【図７】
0006408433.tif 000008
【図８】
0006408433.tif 000009
【図９】
0006408433.tif 000010
【図１０】
0006408433.tif 000011
【図１１】
0006408433.tif 000012