JP6011421B2 - ストレージシステム、情報処理装置の制御プログラム及びストレージシステムの制御方法 - Google Patents

Description

本発明は、ストレージシステム、情報処理装置の制御プログラム及びストレージシステムに関する。

センサ情報や各種ログなどを対象に実時間分析処理（ＲＴＡＰ(REAL TIME ANALYTICAL PROCESSING))の市場が拡大しており、その入力となる時系列データの効率的な蓄積・利用が重要になっている。時系列データの情報収集解析サービスをクラウド上で行う場合、多数のセンサ、多数のログの入力が束ねられ、膨大なデータ列を蓄積し、全データまたは部分系列が必要に応じて再生される。

このように、収集された各情報を同時に記録したり、記録した各情報を同時に再生する技術の１つとして、例えば、ｎ個（ｎは２以上の自然数）の記憶装置を並列に動作させてｍチャンネル（ｍは２以上ｎ以下の自然数）の同時記録再生を行う記録再生装置がある。記録再生装置は、ｍチャンネルのストリームデータを分離してｋ個（ｋはｍ以上ｎ以下の自然数）の画像単位のブロックに分割し、各チャンネルの分割したブロックをｎ個の記憶装置に割り振って順番に記録する。

特開２００１−１４８８３２号公報

上述した記録再生装置において、ストリームを構成するデータをｎ分割し、ｎ個の記録手段に記録することは述べられているが、具体的にどのように分割するのか不明である。また、当該記録再生装置は、複数のディスクを組み合わせて１台の仮想ディスクとして使用するディスクアレイ技術、特に、ＲＡＩＤ−０（ストライピング）との差異が明確でない。また、当該記録再生装置においては、分割したデータの読み出しの高速化については考慮されていない。

本発明では、一側面として、格納部に格納された時系列データの読み出しの高速化を図る技術を提供する。

ストレージシステムは、データ格納部、区間格納部、検索部、読出部を含む。データ格納部は、時系列のデータが分割されたデータを示す分割データを格納する。区間格納部は、分割データを識別する識別情報と、分割データの開始時刻及び終了時刻を示す区間の情報とを関連付けた情報を格納する。検索部は、第１の時刻を取得し、区間格納部から、第１の時刻と第１の時刻を所定時間経過した第２の時刻との間の区間に重複する区間の検索を行い、検索を行った区間に対する分割データの識別情報を取得する。読出部は、データ格納部から、取得した識別情報に対応する分割データを取得し、取得した分割データを時刻順に読み出す。

本発明によれば、一側面として、格納部に格納された時系列データの読み出しの高速化を図ることができる。

本実施形態におけるストレージシステムの一例を示す。 本実施形態におけるストリームデータの一例を示す。 本実施形態におけるストリームデータの蓄積に関するストリームストレージシステムの一例を示す。 本実施形態におけるストレージプロキシの初期化処理に関するブロック図である。 本実施形態におけるストレージプロキシの書き込み・掃出し処理に関するブロック図である。 本実施形態におけるメタデータサーバのブロック図である。 本実施形態における区間管理表の一例を示す。 本実施形態におけるストリームデータの再生に関するストリームストレージシステムの一例を示す。 本実施形態における再生クライアントのブロック図である。 本実施形態における再生シーケンスの一例を示す。 本実施形態における再生クライアントによる再生のための問合せフローの一例を示す。 本実施形態におけるマージツリーの一例を示す。 本実施形態におけるマージツリーの節点構造の一例を示す。 本実施形態におけるマージツリーからのイベントブロックの読み出し処理フローの一例を示す。 本実施形態における、遅延状態フラグが「遅延あり」としてマージツリーに追加されている節点について、イベントブロックの読み出しが完了した場合の処理フローの一例を示す。 本実施形態におけるメタデータサーバの区間検索処理フローの一例を示す。 図１６のＳ４３の詳細フローの一例を示す。 図１７のＳ５４の詳細フローの一例を示す。 図１７のＳ５８の詳細フローの一例を示す。 本実施形態における「次の開始時刻」の決定方法について説明するための図である。 本実施形態における「次の開始時刻」の決定する処理フローの一例を示す。 本実施形態に係るプログラムを実行するコンピュータのハードウェア環境の構成ブロック図である。

ＲＴＡＰ向けストレージには、インメモリデータベース（Ｉｎ−Ｍｅｍｏｒｙ Ｄａｔａｂａｓｅ）やカラム指向ＤＢ（Ｄａｔａｂａｓｅ）が使用されている。特にカラム指向ＤＢは、注目しているデータのカラムを読み出すことで高速読み出しができる点を利用して、データストリームの高速再生に用いられる場合がある。しかし、大量に蓄積したデータを丸ごと高速に再生するといった、ストリーム処理に特化したストレージ製品は今のところまだ見られない。

データストリーム処理実行環境は、クラウドのように利用ハードウェア量をオンデマンドで変更できる環境での活用を念頭に、その時々の利用可能リソースに見合った並列度で処理ができるようにしている。蓄積データにおいても、この特徴を活かすためには、その時々のリソースに見合った並列度で蓄積・再生できることが必要になる。

ストリームデータは時間的に一列に並んだデータ列である。この時間的な順序を保存するため、ファイルに追記する場合、書き込みが逐次化されてしまい、ストレージの書き込み性能に制約される。複数のディスク（ｎ台）を束ねて使用するＲＡＩＤ（Redundant Arrays of Inexpensive Disks）技術は、ディスク単体の書き込み速度のｎ倍を実現するものである。しかし、ストリームデータの流量の変化によって必要な資源量（例えば、ディスク量）を動的に変化させることはできない。

ストリームデータの流量が増大した場合には、負荷分散器（ロードバランサ）で受け口となるサーバを増やすことが考えられる。そこで、負荷分散器と組み合わせた場合において、データの受け口が別々のサーバとなった場合にもストリームデータが適切に蓄積できることが求められる。また、蓄積技術と対となる技術として、蓄積形態に応じたデータの再構成技術が必要である。

また、全データをメモリ上に一括して配置し、ストリーム順に整列させることは、莫大なシステムリソース（メモリ、ＣＰＵパワー）を必要とするため現実的ではない。したがって、ストリームの一部分を成すデータを増加的に再構成して整列させることで、現実的なシステムリソースの元でデータを出力していくことが必要である。

上記ストリームの一部分を成すデータを増加的に再構成して整列させる処理を高速に行うことも求められる。
そこで、本実施形態では、格納部に格納された時系列データの読み出しの高速化を図ることができるストレージシステムを提供する。

図１は、本実施形態におけるストレージシステムの一例を示す。ストレージシステム１は、データ格納部２、区間格納部３、検索部４、読出部５を含む。
データ格納部２は、時系列のデータが分割されたデータを示す分割データを格納する。データ格納部２の一例として、ストレージノード１６が挙げられる。

区間格納部３は、分割データを識別する識別情報と、分割データの開始時刻及び終了時刻を示す区間の情報とを関連付けた情報を格納する。区間格納部３の一例として、区間管理表４４が挙げられる。

検索部４は、第１の時刻を取得し、区間格納部３から、第１の時刻と第１の時刻を所定時間経過した第２の時刻との間の区間に重複する区間の検索を行い、検索を行った区間に対する分割データの識別情報を取得する。検索部４の一例として、メタデータサーバ１５が挙げられる。

読出部５は、データ格納部２から、取得した識別情報に対応する分割データを取得し、取得した分割データを時刻順に読み出す。読出部５の一例として、再生クライアント５０が挙げられる。
このように構成することにより、格納部に格納された時系列データの読み出しの高速化を図ることができる。

検索部４は、重複する区間に含まれない分割データであって第２の時刻より遅く、終了時刻以前の分割データのうち、最も早い開始時刻を取得し、取得した開始時刻を用いて、次の検索を行う。
このように構成することにより、並列処理を実現することができる。
読出部５は、データ格納部２からの取得が完了した分割データのうち、最も早い開始時刻に対応する識別情報で特定される分割データを読み出す。

このように構成することにより、より開始時間の早い分割データから順に読出しを行うことができる。
ストレージシステム１は、さらに、負荷分散アルゴリズムを用いて、時系列のデータを振り分ける振分部を含む。このように構成することにより、大流量のストリームデータを分散して並列に格納することができるので、ストリームデータの蓄積処理の高速化を図ることができる。

本実施形態の一例では、大流量のストリームを捌くために以下の仕組みを前提とする。
負荷分散器（ロードバランサ）が存在し、ストリームのデータを複数の宛先ノードに分配する。

分配されたストリームのデータには、送信元の送信時刻、負荷分散器の受信時刻、送信時刻、または宛先ノードでの受信時刻のタイムスタンプの少なくとも１つが付けられる。また、本実施形態では、容量、性能を自在に拡縮できる分散オブジェクトストレージを用いる。

図２は、本実施形態におけるストリームデータの一例を示す。ストリームデータは、所定間隔で区切られた時系列のデータである。この区切られた各データ（イベント）は、タイムスタンプを含むヘッダと、データ本体を含む。なお、タイムスタンプは、イベントの通番で代用してもよい。また、ストリームデータには、ストリームを識別する情報（ストリーム名）が付与されている。

図３は、本実施形態におけるストリームデータの蓄積に関するストリームストレージシステムの一例を示す。ストリームストレージシステム１１は、負荷分散器１２、ストレージプロキシ１３、メタデータサーバ１５、ストレージノード１６を含む。

クライアント１０は、センサ等のデバイスである。クライアント１０は、負荷分散器１２とインターネット等の通信ネットワークを介して接続されている。負荷分散器１２は、各ストレージプロキシ１３と通信可能なように接続されている。各ストレージプロキシ１３は、メタデータサーバ１５と通信可能なように接続されている。各ストレージプロキシ１３は、各ストレージノード１６と通信可能なように接続されている。

負荷分散器１２は、クライアント１０に単一のＵＲＬ（Uniform Resource Locator）を見せつつ、クライアント１０からのアクセス要求を、負荷分散アルゴリズムを用いて、異なるストレージプロキシ１３に分散させる。ストレージプロキシ１３が１ノードだけの構成またはクライアント１０側で均等にストレージプロキシ１３をアクセスする場合、負荷分散器１２を省略することができる。負荷分散アルゴリズムとしては、ラウンドロビン方法、最小コネクション方法、最速レスポンス方法等を用いることができる。

ストレージノード１６は、分散オブジェクトストレージを構成するオブジェクトサーバに相当する情報処理装置である。ストレージプロキシ１３は、分散オブジェクトストレージを構成するプロキシサーバに相当するスレッド、プロセスまたは情報処理装置である。分散オブジェクトストレージとしては、例えば、Amazon S3（Amazon Simple Storage Service）やOpenStack Swiftがよく知られている。

ストレージプロキシ１３は、クライアント１０から送信されたデータ（イベント）を、一時的に、所定の容量保持する内部バッファメモリ領域１４を有する。ストレージプロキシ１３は、クライアント１０の要求を受信し、その要求に対する応答を返す。また、ストレージプロキシ１３は、クライアント１０から送信されたデータと、その格納する先のストレージノード１６との対応付けたテーブルを記憶装置に保持している。ストレージプロキシ１３は、１つのストリームに対して、１以上存在してもよい。

メタデータサーバ１５は、記録時の動的なストレージプロキシ１３の増減を吸収する機能、及びストリームデータに対して時刻を指定して再生する機能を有する。
ストレージノード１６は、データを格納する領域を有する情報処理装置である。

図４は、本実施形態におけるストレージプロキシの初期化処理に関するブロック図である。ストレージプロキシ１３は、１つのストリームに対して、１つでもよいし、複数存在してもよい。各ストレージプロキシ１３は、内部コンポーネント２１、ＡＰＩ（Application Program Interface）ディスパッチ部２２、初期化処理部２３、ユニーク名決定部２４を含む。ストレージプロキシ１３毎に、内部コンポーネント２１、ＡＰＩ（Application Program Interface）ディスパッチ部２２、初期化処理部２３、ユニーク名決定部２４は以下の処理を行う。

ＡＰＩディスパッチ部２２は、ストレージプロキシ１３が有する種々のＡＰＩを管理し、要求に応じてまたは所定のタイミング等でＡＰＩを呼び出す。内部コンポーネント２１は、ストレージプロキシ１３上で動作する、上位ミドルウェア側のコンポーネントであり、ストレージの初期化、ストリームの記録、再生において適切なＡＰＩを呼び出すものである。

初期化処理部２３は、ストリーム毎に、ＡＰＩディスパッチ部２２により初期化ＡＰＩが呼び出されることにより、内部バッファメモリ領域１４のうち、イベントを一時的に保持する領域をストリーム毎に初期化する。

内部バッファ管理部３１は、ストリーム名設定ＡＰＩにより読み出されると、受信したストリームデータからそのストリームのストリーム名を読み出し、内部バッファメモリ領域１４内のストリーム名格納領域に設定する。

また、初期化処理部２３は、内部バッファメモリ領域１４に格納された開始時刻、終了時刻を初期化する。また、初期化処理部２３は、内部バッファメモリ領域１４に格納されたイベントブロックについての通番（シーケンス番号）を“０”で初期化する。

初期化処理部２３は、ユニーク名決定部２４を呼び出す。ユニーク名決定部２４は、他のストレージプロキシ１３の名前と被らないユニークな名前を内部バッファメモリ領域１４内のユニーク名を格納する領域に格納する。このとき、ユニークな名前の設定には、以下の方法のいずれかを選択することができる。第１の方法として、メタデータサーバ１５が現在動作中の全てのストレージプロキシ１３の名前を管理する場合、各ストレージプロキシ１３は起動時にメタデータサーバ１５に名付けを要求する。メタデータサーバ１５は、ユニークな名前を生成し、その生成したユニーク名を返す。第２の方法として、ストレージプロキシ１３は、十分大きな桁数を持つ乱数によって、実用上ユニークと考えてよい名前を自ら設定してもよい。第３の方法として、ストレージプロキシ１３のＩＰ（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ）アドレスをユニーク名に用いてもよい。

図５は、本実施形態におけるストレージプロキシの書き込み・掃出し処理に関するブロック図である。ストレージプロキシ１３毎に、内部コンポーネント２１、ＡＰＩディスパッチ部２２、内部バッファ管理部３１、イベントブロック名生成部３２は以下の処理を行う。

内部バッファ管理部３１は、イベント受信時において、ＡＰＩディスパッチ部２２からイベント書き込みＡＰＩまたは掃出しＡＰＩが呼び出されることにより動作する。内部バッファ管理部３１は、イベント受信時において、負荷分散器１２からのストリームデータの書き込みを内部バッファメモリ領域１４にバッファリングし、適切なサイズのイベントブロックにパッキングする。イベントブロック長を大きくするとスループットは増大するが、書き込みに要する時間が長くなる。逆に、イベントブロック長を小さくすると、スループットが減少するが、書き込みに要する時間は短くなる。

内部バッファメモリ領域１４が空のときに、内部バッファメモリ領域１４へのイベントの書き込みを行う場合、内部バッファ管理部３１は、そのイベントのタイムスタンプを開始時刻と終了時刻に設定する。内部バッファメモリ領域１４に既にイベントが書き込まれているときに、イベントの書き込みを行う場合、内部バッファ管理部３１は、そのイベントのタイムスタンプを終了時刻に設定する。以下で述べる内部バッファの掃出しが行われると、内部バッファメモリ領域１４と開始・終了時刻情報は消去される。あるいは、開始時刻と終了時刻は掃出し時に一括して設定されることもできる。詳細は後述する。
イベントブロックへのパッキングと掃出しの仕方は以下の方法があり、仕様に応じて組み合わせることができる。

第１のパッキング・掃出し方法としては、イベントブロックの総データ量を予め固定しておき、イベントブロックの総データ量の上限を超える書き込みが来た場合に、内部バッファ管理部３１は、イベントブロックの掃き出しを行う方法がある。
第２のパッキング・掃出し方法としては、イベント数を予め固定しておき、イベント数の上限に達した場合に、内部バッファ管理部３１は、ブロックの掃出しを行う方法がある。
第３のパッキング・掃出し方法としては、イベントの滞在時間の上限を予め設定しておき、先頭のイベントの受信時間から上限の滞在時間が経過した場合に、内部バッファ管理部３１は、ブロックの掃出しを行う方法がある。
第４のパッキング・掃出し方法としては、外部のアプリケーションからＡＰＩを用いて明示的に掃出し要求が来た場合に、内部バッファ管理部３１は、イベントブロックの掃出しを行う方法がある。

内部バッファ管理部３１は、イベントブロック名生成部３２にイベントブロック名を問い合わせる。すると、イベントブロック名生成部３２は、イベントブロックにユニークな名前を付ける。ここで、イベントブロック名生成部３２は、イベントブロックの名前を付ける場合、内部バッファメモリ領域１４から、ストリーム名と、ストレージプロキシ自身のユニーク名と、イベントブロックについてのシーケンス番号とを読み出す。イベントブロック名生成部３２は、その読み出したストリーム名とユニーク名とシーケンス番号とを組にしたユニークな情報を、イベントブロック名とする。イベントブロック名生成部３２は、そのイベントブロック名を内部バッファ管理部３１に返信する。さらに、イベントブロック名生成部３２は、内部バッファメモリ領域１４に格納されているシーケンス番号をインクリメントする。

内部バッファ管理部３１は、データ転送要求を受けた場合には、イベントブロック名から定まるストレージノード１６に対して、イベントブロック名と内部バッファメモリ領域１４に保持していたイベントブロックを送信して、書き込みを依頼する。

内部バッファ管理部３１は、イベントブロックを構成するイベントデータの開始時刻と終了時刻を区間情報とし、内部バッファメモリ領域１４の開始時刻と終了時刻を更新する。内部バッファ管理部３１は、［区間情報、イベントブロック名］をメタデータサーバ１５に送信する。なお、再生時に、区間の開始と終了をイベント番号で指定する場合には、時刻をイベント番号に読み替えればよい。

図６は、本実施形態におけるメタデータサーバのブロック図である。メタデータサーバ１５は、受信・応答部４１、区間木検索部４２、区間木管理部４３、区間管理表４４を含む。区間木管理表４４は、ストリーム毎に管理されている。

受信・応答部４１は、ＬＡＮ（Local Area Network）を介して、再生クライアント５０からの要求を受信する。その要求に応じて、受信・応答部４１は、区間木検索部４２に対して、重なり区間の検索を要求したり、次の開始時刻の問い合わせをする。ここで、重なり区間とは、検索要求のあった時刻区間内（開始時刻〜終了時刻）にオーバラップするイベントブロックを含む区間をいう。受信・応答部４１は、その依頼結果を、要求に対する応答として再生クライアント５０に返信する。また、受信・応答部４１は、再生クライアント５０からの要求に応じて、区間の追加または削除を区間木管理部４３に要求する。

区間木検索部４２は、受信・応答部４１から送信された要求または問い合わせに含まれるストリーム名を取得し、そのストリーム名に対応する区間管理表４４を選択する。区間木検索部４２は、受信・応答部４１から送信された要求または問い合わせに応じて、その選択した区間管理表４４から、読み取り位置を指定したエントリのボディ情報（図７の「終了時刻」、「イベントブロック名」、「管理用データ構造」等の情報）を取得する。

区間木管理部４３は、受信・応答部４１から送信された要求に含まれるストリーム名を取得し、そのストリーム名に対応する区間管理表４４を選択する。区間木管理部４３は、受信・応答部４１から送信された要求に応じて、その選択した区間管理表４４にエントリの追加または管理データ構造の更新を行う。

図７は、本実施形態における区間管理表の一例を示す。区間木は、ストリーム毎に別々に管理される。区間木管理部４３は、時刻情報をキーとしてツリー構造で管理される区間管理表に「イベントブロック名」４４−４、「開始時刻」４４−２、「終了時刻」４４−３を登録して管理する。区間管理表４４の一例は、木構造の一種を採用したデータ構造で示される「区間木」である。区間管理表のエントリは、「レコード番号」４４−１、「開始時刻」４４−２、「終了時刻」４４−３、「イベントブロック名」４４−４、「管理用データ構造」４４−５を含む。

「管理用データ構造」４４−５は、区間管理を実現するアルゴリズムによって異なる。区間木が２色木（または赤黒木ともいう）の場合、「管理用データ構造」４４−５は、二値の色情報、左部分木用レコード番号、右部分木用レコード構造、親レコード番号、自分と左右部分木を含めた最少開始時刻、自分と左右部分木を含めた最大終了時刻を含む。

区間管理表４４に対する操作として、区間木管理部４３には区間の追加、削除操作が実装され、区間木検索部４２には区間の検索が実装されている。
区間の追加の場合には、区間木管理部４３は、（開始時刻、終了時刻、イベントブロック名）が与えられたときに、図７で示すエントリを追加し、かつ、区間木の管理データ構造が以下の二色木条件を満たすように設定する。二分探索木が以下の二色木条件を満たす場合、二色木となる。
（１）各節点は、赤または黒のどちらかである。
（２）葉（葉の値は空（ＮＩＬ）である）は全て黒である。
（３）ある接点が赤であれば、その子供は両方とも黒である。
（４）１つの節点からその子孫までのどの単純な経路も、同じ数だけ黒の節点を含む。

区間の削除の場合には、区間木管理部４３は、削除対象となるエントリのレコード番号が与えられたときに、他のエントリの管理データ構造について二色木条件を満たしつつ、指定されたエントリを削除する。
区間の検索の場合には、区間木検索部４２は、（開始時刻、終了時刻）が与えられたときに、区間木の管理データ構造から、この区間に重なる全ての区間情報（＝レコード番号のリスト）を求める。
区間検索に関する手続きについては、メタデータサーバ１５の検索処理で詳述する。なお、区間の追加と削除は、Ｏ（ｌｏｇ ｎ）（ここでｎは区間の総数）の実行時間で実行でき、区間の検索は、Ｏ（ｋｌｏｇ ｎ）（ここで、ｋは答えとなる区間の総数）の実行時間で実行できるため、区間の管理方法として望ましい。

次に、ストリームストレージシステム１１の再生処理について詳述する。
図８は、本実施形態におけるストリームデータの再生に関するストリームストレージシステムの一例を示す。ＣＥＰ（Complex Event Processing）エンジンは、ＲＴＡＰ処理の中核的なプログラムである。ＣＥＰエンジンまたはユーザアプリケーション等のアプリケーションプログラムは、ストリームストレージシステム１１に蓄積されたストリームデータを、ストリームストレージ１１のコンポーネントを通して取得する。このようにストリームデータを再生する情報処理装置を再生クライアント５０と称する。また、ＣＥＰエンジンまたはユーザアプリケーションプログラム等の外部アプリケーションプログラムを、以下、外部アプリと称する。これらの外部アプリは、再生クライアント５０上で動作する。

外部アプリがストリームを識別する情報を指定する。すると、再生クライアント５０は、所定のＡＰＩを用いて、その識別する情報に対応するストリームデータを、ストレージプロキシ１３を介して、各ストレージノード１６に分散されたストリームデータを特定することができる。

図９は、本実施形態における再生クライアントのブロック図である。再生クライアント５０を用いたストリーム再生処理は、次のようになる。外部アプリ５４は、再生クライアント５０に対し、再生すべきストリームデータのイベントの取得を要求する。このとき、外部アプリ５４は、再生クライアント５０のＡＰＩディスパッチ部５１により、ＡＰＩを呼び出して、再生すべきストリーム名、開始時刻、終了時刻を指定する。開始時刻と終了時刻は省略することができ、開始時刻と終了時刻を省略した場合には、ストリームの先頭データのタイムスタンプ、ストリームの最終データのタイムスタンプが代用される。

再生クライアント５０は、例えば、以下のようなＡＰＩを有しており、これらのＡＰＩを用いて外部アプリ５４が必要とするイベントを漏れなく取得することができる。
・再生する時刻の範囲（開始時刻と終了時刻）を設定するＡＰＩ
・指定した時刻区間内の全イベントを読み出したかをチェックするＡＰＩ
・ストリームの終端かどうかをチェックするＡＰＩ
・イベントを１つ取得するＡＰＩ
・ストリームの終端の時刻情報を更新するＡＰＩ（このＡＰＩはストリームが非同期に書き込まれている状況で有用である。）

これらのＡＰＩにより、マージツリー管理部５２が動作する。マージツリー管理部５２は、メタデータサーバ１５に対して、再生すべきストリームデータの重なり区間及び次の開始時刻を問い合わせる。メタデータ１５は、検索結果として、検索された重なり区間のリストと、次の開始時刻をマージツリー管理部５２に返信する。

マージツリー管理部５２は、ストレージプロキシ１３を介して、重なり区間のリストに基づいて、ストレージノード１６へイベントブロックの読み出し要求を行う。ストレージノード１６から読み出したイベントブロックは、ストレージプロキシ１３を介して、再生クライアント５０のマージツリー格納領域５３に格納される。マージツリーとは、二分木で形成されるデータ構造であって、ストレージノード１６から読み出したイベントブロックをその二分木の節点に追加し、時刻キー順に整列させていくためのツリー状のデータ構造を示す。本実施形態では、二分木の一例として、二色木を利用している。再生クライアント５０は、ストレージノード１６から読み出したイベントブロックをマージツリーの節点上に格納する。

マージツリー管理部５２は、マージツリー格納領域５３に格納されたマージツリーについて節点の追加、削除、節点の検索を行なったり、マージツリーからイベントの読み出しを行う。
まずは、イベントブロックの読み出しについて説明する。外部アプリ５４より再生の開始時刻と終了時刻が指定された場合、再生クライアント５０は、その指定された範囲の時刻区間を区切って段階的にストリームストレージシステム１１に問合せを行う。これについて、図１０を用いて説明する。

図１０は、本実施形態における再生シーケンスの一例を示す。再生クライアント５０は、メタデータサーバ１５に、負荷分散器１２、ストレージプロキシ１３を介して、再生すべきストリームデータの区間の検索を要求する（Ｓ１）。ここでは、再生クライアント５０は、再生の開始時刻と開始時刻からΔ時刻経過後の区間を入力として、メタデータサーバ１５に問い合わせる。

メタデータサーバ１５は、再生クライアント５０からの問い合わせに応じて、再生すべきストリームデータの区間検索処理を行う（Ｓ２）。ここでは、メタデータサーバ１５は、問合せのあった再生すべきストリームデータの時刻区間内にオーバラップする区間情報を持つイベントブロック集合（すなわち、重なり区間）を、再生クライアント５０に返答する。このとき、メタデータサーバ１５は「次の開始時刻」の情報を、その返答に含める。

再生クライアント５０は、メタデータサーバ１５からの応答を受信する。すると、再生クライアント５０は、その応答により得られたイベントブロック名を用いて、イベントブロックをストレージノード１６から読み出す（Ｓ３、Ｓ４）。複数のイベントブロックを読み出し、マージツリーに統合する処理（以下に詳述）は逐次に行ってもよいし、並列（非同期）に行ってもよい。

再生クライアント５０は、ストレージノード１６から読み出したイベントブロックをマージツリーに統合する（Ｓ５）。ここで、イベントブロックの読み出しと、マージツリーへのイベントブロックの追加とは、遅延実行を用いて非同期に行うことができる。遅延実行については、後述する。

再生クライアント５０は、メタデータサーバ１５への問合せに対する応答において得られた「次の開始時刻」を開始時刻に設定し、開始時刻が終了時刻に満たない場合は、メタデータサーバ１５に対して、さらに、再生すべきストリームデータの区間の検索を要求する（Ｓ１）。

図１１は、本実施形態における再生クライアントによる再生のための問合せフローの一例を示す。上述したように、外部アプリ５４は、再生クライアント５０のＡＰＩを呼び出して、再生すべきストリーム名、開始時刻、終了時刻を指定する。

再生クライアント５０は、開始時刻をパラメータSTART_TIMEに設定する（Ｓ１１）。START_TIME＜終了時刻である場合（Ｓ１２で「Ｙｅｓ」）、再生クライアント５０は、START_TIMEにΔ時刻を加算した時刻を、パラメータEND_TIMEに設定する（Ｓ１３）。ここで、Δは問い合わせのための最少時刻幅とする。

再生クライアント５０は、区間（START_TIME、END_TIME）について、メタデータサーバ１５に問合せをする（図１０のＳ１に対応する）。メタデータサーバ１５は、問合せのあった時刻区間内にオーバラップする区間情報を持つイベントブロックの名前の集合を、再生クライアント５０に返答する。このとき、メタデータサーバ１５は「次の開始時刻」の情報を返答に含める（図１０のＳ２に対応する）。再生クライアント５０は、メタデータサーバ１５からの応答を受信すると、イベントブロックの名前の集合を、パラメータRESULT_LISTに設定し、「次の開始時刻」をパラメータNEXT_START_TIMEに設定する（Ｓ１４）。「次の開始時刻」の決定方法については、図２０、図２１において後述する。

RESULT_LISTが空集合φでない場合（Ｓ１５で「Ｙｅｓ」）、再生クライアント５０は、RESULT_LISTから１つの要素（イベントブロック）を取り出し、パラメータBLOCK_NAMEに設定する。再生クライアント５０は、RESULT_LISTの残りの要素を、RESULT_LISTに設定する（Ｓ１６）。

再生クライアント５０は、ストレージノード１６から、BLOCK_NAMEに対応するイベントブロックを読み出す（図１０のＳ３に対応する。）。再生クライアント５０は、ストレージノード１６から、読み出したイベントブロックをパラメータBLOCKに設定する（Ｓ１７）。再生クライアント５０は、そのBLOCKをマージツリーに登録する（Ｓ１８）。

RESULT_LISTが空集合φになるまで、Ｓ１６〜Ｓ１８の処理を繰り返す。RESULT_LISTが空集合φになった場合（Ｓ１５で「Ｎｏ」）、再生クライアント５０は、NEXT_START_TIMEの値を、START_TIMEに設定し（Ｓ１９）、Ｓ１２の処理へ戻る。

START_TIME＜終了時刻の間、再生クライアント５０は、Ｓ１２〜Ｓ１９を繰り返す。START_TIME≧終了時刻となる場合（Ｓ１２）、再生クライアント５０は、イベントブロックの読み出し処理を終了する。

図１２の再生問合せ処理は、図１４の読み出し処理と非同期に実施すると再生開始時刻から再生終了時刻までの全ブロックをマージツリー、すなわち、メモリ上に保持することになる。そのため、データ量が莫大である場合にはシステムリソースを考慮したペースで当該再生問い合わせ処理を行うことが必要である。問合せのペースを調整する方法の一例として、読み出し処理で１ブロック分のデータを読み出したら、１ブロックをストレージノードから獲得するようにするものである。

次に、マージツリーからのイベントブロックの読み出しについて説明する。ストレージノード１６から読み出されたイベントブロックは、マージツリーという、図１２に示すようなデータ構造に合流される。図１２において、白色の四角はイベントブロックを示し、丸は時刻キーを示し、ハッチングされた四角は遅延読み出し中のイベントブロックを示す。マージツリーの節点は、図１３に示すようなデータ構造である。マージツリーの節点構造６１は、「時刻キー」、「遅延状態フラグ」、「イベントブロック内配列のインデックス」、「イベントブロック」のデータ項目（フィールド）を含む。以下では、節点内部のフィールドを「フィールド名」で表す。また、そのフィールドの型は明示していない場合、名前から容易に推測できるものになる。例えば、「イベントブロック」とは、節点上のイベントブロック・フィールドのことを表し、メモリ上に読み込まれたイベントブロックの実体への参照型になる。

マージツリーに新しい節点を追加する処理は、図１０及び図１１で説明したイベントブロックの読み出し処理において行われる。イベントブロックの読み出し後にマージツリーに節点を追加する場合には、再生クライアント５０は、以下のＡ１〜Ａ４を前提として節点を初期化する。
（Ａ１）時刻キーはブロックの先頭のイベントのタイムスタンプとする。
（Ａ２）「遅延状態フラグ」は「遅延なし」とする。
（Ａ３）「イベントブロック内配列のインデクス」は０（先頭）とする。
（図１１のイベントブロックの読み出しループの１回目の回転について特別扱いが必要で、インデックスは開始時刻と同じかそれ以降のタイムスタンプを持つイベントまで進めておく。）
（Ａ４）「イベントブロック」には読み出したイベントブロック実体の参照をセットする。

また、ブロックの読み出し完了前にマージツリーへの追加する場合には、再生クライアント５０は、以下の（Ｂ１）、（Ｂ２）のように処理する。
（Ｂ１）時刻キーは、メタデータサーバ１５から入手した区間情報のうちの開始時刻、とする。
（Ｂ２）「遅延状態フラグ」は「遅延あり」とする。

イベントブロックの読み出し後にマージツリーに節点を追加する場合及びブロックの読み出し完了前にマージツリーへの追加する場合のいずれも、時刻キーは設定されている。そのため、再生クライアント５０は、マージツリーの適切な位置に追加節点を配置することができる。

図１４は、本実施形態におけるマージツリーからのイベントブロックの読み出し処理フローの一例を示す。再生クライアント５０は、マージツリーの最小時刻をキーとする節点Ａを読み出し、かつ、接点Ａをマージツリーから削除する（Ｓ２１）。ここで、最小時刻が同じである節点が複数存在する場合、再生クライアント５０は、イベントブロックの名前から大小関係を決定する。イベントブロックの名前はユニークであることが保証されているので、名前の順序を定めれば、節点同士の大小関係は一意に定まる。

節点Ａについて、遅延状態フラグが「遅延あり」である場合（Ｓ２２で「Ｙｅｓ」）、遅延状態フラグが「遅延なし」に変更されるまで、再生クライアント５０は、その節点に対応するイベントブロックの読み出しを一時停止する（Ｓ２３）。ここで、節点Ａに対応するイベントブロックは、図１２に示すように、ストレージノード１６からの読み出し中なので、再生クライアント５０はその読み出しが完了するまで、節点Ａに対応するイベントブロックの読み出しを行わない。

遅延状態フラグが「遅延なし」である場合（Ｓ２２で「Ｙｅｓ」または、Ｓ２３の処理後）、再生クライアント５０は、節点Ａの「イベントブロック内配列のインデックス」の指しているイベントブロックを読み出す。再生クライアント５０は、このイベントブロックを出力ストリームに書き出す（Ｓ２４）。

再生クライアント５０は、節点Ａの「イベントブロック内配列のインデックス」を１増やす（Ｓ２５）。
「イベントブロック内配列のインデックス」が、イベントブロックのイベント数を越えた場合（Ｓ２６で「Ｙｅｓ」）、再生クライアント５０は、Ｓ２１の処理へ戻る。

「イベントブロック内配列のインデックス」が、イベントブロックのイベント数を越えていない場合（Ｓ２６で「Ｎｏ」）、再生クライアント５０は、次の処理を行う。すなわち、再生クライアント５０は、節点Ａの「イベントブロックのインデックス」の指しているイベントブロックのタイムスタンプＫを読み出す（Ｓ２７）。

再生クライアント５０は、読み出したタイムスタンプＫをキー、バリューを節点Ａ（更新後）とする節点をマージツリーに追加する（Ｓ２８）。
再生クライアント５０は、マージツリーが空でない間（Ｓ２９で「Ｎｏ」）、Ｓ２１〜Ｓ２８の処理を繰り返す。

遅延状態フラグが「遅延あり」としてマージツリーに追加されている節点について、イベントブロックの読み出しが完了した場合、再生クライアント５０は、図１５に示す処理を行う。すなわち、再生クライアント５０は、節点の遅延状態フラグ「遅延あり」を「遅延なし」に更新する（Ｓ３１）。

再生クライアント５０は、「イベントブロック内配列のインデックス」を０にする（Ｓ３２）。さらに、再生クライアント５０は、「イベントブロック」にイベントブロックへの参照を設定する（Ｓ３３）。

このように、再生クライアント５０は、ストレージノード１６からの読み出し中のイベントブロックについては、再生クライアント５０は読み出しが完了するまで読み出しをしない。一方で、再生クライアント５０は、読み出し完了のイベントブロックを、時刻のより早い方から順に読み出す。したがって、ストレージノード１６からの読み出し中のイベントブロックについて遅延が発生する。しかし、読み出し完了のイベントブロックの節点は、その遅延しているイベントブロックとは独立して、読み出されてマージツリーから削除されつつ、マージツリーへのイベントブロックの追加が行われる。このように、イベントブロックの読み出しと、マージツリーへのイベントブロックの追加とを非同期に行うことを遅延実行という。

次に、メタデータサーバ１５の区間木検索部４２による区間検索に関する処理について説明する。
図１６は、本実施形態におけるメタデータサーバの区間検索処理フローの一例を示す。区間木検索部４２は、受信・応答部４１からの要求または問い合わせに応じて、区間検索を行う。このとき、受信・応答部４１から区間木検索部４２へ、開始時刻ｓ、終了時刻ｅが渡される。

区間木検索部４２は、区間管理表４４からツリーのルートインデックスを検索し、ルートインデックスをインデックス変数ｖに設定する。また、区間木検索部４２は、インデックスリスト変数Ｌを初期化する（Ｓ４１）。

区間木検索部４２は、区間管理表４４を用いて、インデックス変数ｖの参照先が葉（ＮＩＬ）であるか否かを判定する。ここで、２色木において、葉は、値を持たない（ＮＩＬ）ノードである。インデックス変数ｖの参照先が葉（ＮＩＬ）である場合（Ｓ４２で「Ｙｅｓ」）、区間木検索部４２は、空のインデックスリスト変数Ｌを受信・応答部４１に返す。

インデックス変数ｖの参照先が葉（ＮＩＬ）でない場合（Ｓ４２で「Ｎｏ」）、区間木検索部４２は、関数serchAllFromNode(s, e, v)を呼び出して、全ノードを対象に検索し（Ｓ４３）、その検索結果を受信・応答部４１に返す。Ｓ４３の詳細については、図１７を用いて説明する。

図１７は、図１６のＳ４３の詳細フローの一例を示す。区間木検索部４２は、関数serchAllFromNode(s, e, v)に、開始時刻ｓ、終了時刻ｅ、インデックス変数ｖを渡す。区間木検索部４２は、インデックスリスト変数Ｌを初期化する（Ｓ５１）。

区間木検索部４２は、区間管理表４４から、インデックス変数ｖの参照先のエントリが区間［開始時刻ｓ，終了時刻ｅ］と重なるか否かを判定する（Ｓ５２）。インデックス変数ｖの参照先のエントリが区間［開始時刻ｓ，終了時刻ｅ］と重ならない場合（Ｓ５２で「Ｎｏ」）、Ｓ５４へ進む。

インデックス変数ｖの参照先のエントリが区間［開始時刻ｓ，終了時刻ｅ］と重なる場合（Ｓ５２で「Ｙｅｓ」）、区間木検索部４２は、インデックス変数ｖと、インデックスリスト変数Ｌとの和集合を、インデックスリスト変数Ｌに設定する（Ｓ５３）。

区間木検索部４２は、関数checkOverlapOnLeftSubtreeを呼び出して、インデックス変数ｖの左側のツリーが、区間［開始時刻ｓ，終了時刻ｅ］と重なるかをチェックする（Ｓ５４）。Ｓ５４の詳細については、図１８で説明する。インデックス変数ｖの左側が、区間［開始時刻ｓ，終了時刻ｅ］と重ならない場合（Ｓ５５で「Ｎｏ」）、区間木検索部４２は、Ｓ５８の処理へ進む。

インデックス変数ｖの左側が、区間［開始時刻ｓ，終了時刻ｅ］と重なる場合（Ｓ５５で「Ｙｅｓ」）、区間木検索部４２は、インデックス変数ｖの参照先エントリの左部分木インデックスを変数ｖＬに設定する（Ｓ５６）。

区間木検索部４２は、関数serchAllFromNodeを呼び出して、開始時刻ｓ、終了時刻ｅ、変数ｖＬを引き渡して、ノードを検索行い、インデックス変数ｖの参照先エントリの左部分木インデックスについて、図１７の検索処理を再帰的に行う。区間木検索部４２は、serchAllFromNode(s, e, vL)の結果と、インデックスリスト変数Ｌとの和集合を、インデックスリスト変数Ｌに設定する（Ｓ５７）。

区間木検索部４２は、インデックス変数ｖの右側が、区間［開始時刻ｓ，終了時刻ｅ］と重なるかをチェックする（Ｓ５８）。Ｓ５８の詳細については、図１９で説明する。インデックス変数ｖの右側が、区間［開始時刻ｓ，終了時刻ｅ］と重ならない場合（Ｓ５９で「Ｎｏ」）、区間木検索部４２は、本フローを終了する。

インデックス変数ｖの右側が、区間［開始時刻ｓ，終了時刻ｅ］と重なる場合（Ｓ５９で「Ｙｅｓ」）、区間木検索部４２は、インデックス変数ｖの参照先エントリの右部分木インデックスを変数ｖＲに設定する（Ｓ６０）。

区間木検索部４２は、関数serchAllFromNodeを呼び出して、開始時刻ｓ、終了時刻ｅ、変数ｖＲを引き渡してノードを検索行い、インデックス変数ｖの参照先エントリの左部分木インデックスについて、図１７の検索処理を再帰的に行う。区間木検索部４２は、serchAllFromNode(s, e, vR)の結果と、インデックスリスト変数Ｌとの和集合を、インデックスリスト変数Ｌに設定する（Ｓ６１）。

図１８は、図１７のＳ５４の詳細フローの一例を示す。checkOverlapOnLeftSubtreeの呼び出し時には、インデックス変数ｖ, 開始時刻ｓ, 終了時刻ｅが引き渡される。
区間木検索部４２は、インデックス変数ｖの左部分木のインデックスを、インデックス変数ｐに設定する（Ｓ７１）。区間木検索部４２は、インデックス変数ｐの参照先が葉（ＮＩＬノード）か否かを判定する（Ｓ７２）。

インデックス変数ｐの参照先が葉（ＮＩＬノード）である場合（Ｓ７２で「Ｙｅｓ」）、区間木検索部４２は、次の処理を行う。すなわち、区間木検索部４２は、関数checkOverlapOnLeftSubtreeによる、インデックス変数ｖの左側は［開始時刻ｓ，終了時刻ｅ］と重なるかというチェック結果として、「ｆａｌｓｅ」を返す。

インデックス変数ｐの参照先が葉（ＮＩＬノード）でない場合（Ｓ７２で「Ｎｏ」）、区間木検索部４２は、インデックス変数ｐの参照先エントリの最大終了時刻を変数ｍａｘに設定し、インデックス変数ｐの参照先エントリの最小開始時刻を変数ｍｉｎに設定する（Ｓ７３）。

変数ｍｉｎ＞終了時刻ｅまたは開始時刻ｓ＞変数ｍａｘである場合（Ｓ７４で「Ｎｏ」）、区間木検索部４２は、次の処理を行う。すなわち、区間木検索部４２は、関数checkOverlapOnLeftSubtreeによる、インデックス変数ｖの左側は［開始時刻ｓ，終了時刻ｅ］と重なるかというチェック結果として、「ｆａｌｓｅ」を返す。

変数ｍｉｎ≦終了時刻ｅかつ開始時刻ｓ≦変数ｍａｘである場合（Ｓ７４で「Ｙｅｓ」）、次の処理を行う。すなわち、区間木検索部４２は、関数checkOverlapOnLeftSubtreeによる、インデックス変数ｖの左側は［開始時刻ｓ，終了時刻ｅ］と重なるかというチェック結果として、「Ｔｒｕｅ」を返す。

図１９は、図１７のＳ５８の詳細フローの一例を示す。関数checkOverlapOnRightSubtreeの呼び出し時には、インデックス変数ｖ, 開始時刻ｓ, 終了時刻ｅが引き渡される。

区間木検索部４２は、インデックス変数ｖの右部分木のインデックスを、インデックス変数ｐに設定する（Ｓ８１）。区間木検索部４２は、インデックス変数ｐの参照先が葉（ＮＩＬノード）か否かを判定する（Ｓ８２）。

インデックス変数ｐの参照先が葉（ＮＩＬノード）である場合（Ｓ８２で「Ｙｅｓ」）、区間木検索部４２は、次の処理を行う。すなわち、区間木検索部４２は、関数checkOverlapOnRightSubtreeによる、インデックス変数ｖの右側は［開始時刻ｓ，終了時刻ｅ］と重なるかというチェック結果として、「ｆａｌｓｅ」を返す。

インデックス変数ｐの参照先が葉（ＮＩＬノード）でない場合（Ｓ８２で「Ｎｏ」）、区間木検索部４２は、インデックス変数ｐの参照先エントリの最大終了時刻を変数ｍａｘに設定し、インデックス変数ｐの参照先エントリの最小開始時刻を変数ｍｉｎに設定する（Ｓ８３）。

変数ｍｉｎ＞終了時刻ｅまたは開始時刻ｓ＞変数ｍａｘである場合（Ｓ８４で「Ｎｏ」）、区間木検索部４２は、次の処理を行う。すなわち、区間木検索部４２は、関数checkOverlapOnRightSubtreeによる、インデックス変数ｖの右側は［開始時刻ｓ，終了時刻ｅ］と重なるかというチェック結果として、「ｆａｌｓｅ」を返す。

変数ｍｉｎ≦終了時刻ｅかつ開始時刻ｓ≦変数ｍａｘである場合（Ｓ８４で「Ｙｅｓ」）、次の処理を行う。すなわち、区間木検索部４２は、関数checkOverlapOnRightSubtreeによる、インデックス変数ｖの右側は［開始時刻ｓ，終了時刻ｅ］と重なるかというチェック結果として、「Ｔｒｕｅ」を返す。

次に、図１０のＳ２において、再生クライアント５０への応答に含めた「次の開始時刻」、具体的には、図１１のＳ１４において、決定した「次の開始時刻」の取得方法について、図２０、図２１を用いて説明する。

予め、再生クライアント５０がメタデータサーバ１５に（再生開始時刻、再生終了時刻）をパラメータとして含む問い合せメッセージを送信したとする。このとき、メタデータサーバ１５は、メッセージを受信したとき、そのメッセージが区間検索に関するものである場合、区間木検索部４２の実行を行う。

区間木検索部４２は、searchAllFromRoot（再生開始時刻、再生終了時刻）を実行し、その区間にオーバラップするエントリのインデックス一覧（リスト）を求める。区間木検索部４２は、そのインデックス一覧（リスト）から、各エントリの（ブロック名、開始時刻、終了時刻）の３つ組データを全エントリ分読み出し、３つ組みデータのリストＬ１を生成する。

区間木検索部４２は、searchMinAfter（再生終了時刻）を実行し、「次の開始時刻」を決定する。メタデータサーバ１５は、リストＬ１と、決定した「次の開始時刻」をペアとして、再生クライアント５０に返答する。

図２０は、本実施形態における「次の開始時刻」の決定方法について説明するための図である。図２０において、searchMinAfterは、「次の開始時刻」を返す関数である。横方向の太線７１，７２，７３，７４，７５は、イベントブロックを示す。

区間（START_TIME，START_TIME+Δ）にオーバラップするイベントブロックの集合をＳとする。集合Ｓに含まれないイベントブロックであって、開始時刻がSTART_TIME+Δより大きく、かつ問合せの終了時刻END_TIME以前のイベントブロックが存在するとき、このようなイベントブロックのうち最少の開始時刻を問合せの「次の開始時刻」として定義する。

「次の開始時刻」について、例えば、図２０の（１）問い合わせ区間を例に説明する。ここで、イベントブロック７１〜７５はいずれも、問合せの終了時刻END_TIME以前のイベントブロックであるとする。区間（START_TIME，START_TIME+Δ）にオーバラップするイベントブロックの集合Ｓは、イベントブロック７１，７２である。このとき、集合Ｓに含まれないイベントブロックであって、開始時刻がSTART_TIME+Δより大きく、かつ問合せの終了時刻END_TIME以前のイベントブロックは、イベントブロック７３〜７５である。このうち、最小の開始時刻を有するのはイベントブロック７３であるから、この最小の開始時刻が「次の開始時刻」と決定される。

このようにすることにより、「次の開始時刻」より前の時刻で問合せを行っても、集合Ｓのサブセットしか得られないため、問合せ回数を最適化することができる。

図２１は、本実施形態における「次の開始時刻」の決定する処理フローの一例を示す。区間木検索部４２は、区間管理表４４からツリーのルートインデックスを検索し、ルートインデックスをインデックス変数ｖに設定する。また、区間木検索部４２は、時刻変数ｔを“∞”で初期化する（Ｓ９１）。

区間木検索部４２は、区間管理表４４を用いて、インデックス変数ｖの参照先が葉（ＮＩＬ）であるか否かを判定する（Ｓ９２）。インデックス変数ｖの参照先が葉（ＮＩＬ）でない場合（Ｓ９２で「Ｎｏ」）、区間木検索部４２は、インデックス変数ｖの参照先のエントリの開始時刻を変数ｕに設定する（Ｓ９３）。

変数ｕ＞入力時刻ｑの場合（Ｓ９４で「Ｎｏ」）、区間木検索部４２は、インデックス変数ｖの参照先エントリの右部分木インデックスをインデックス変数ｖに設定する（Ｓ９５）。

変数ｕ≦入力時刻ｑの場合（Ｓ９４で「Ｙｅｓ」）、区間木検索部４２は、インデックス変数ｖの参照先エントリの左部分木インデックスをインデックス変数ｖに設定する（Ｓ９６）。ここで、時刻変数ｔ＞変数ｕの場合（Ｓ９７で「Ｙｅｓ」）、区間木検索部４２は、変数ｕに設定されている開始時刻を時刻変数ｔに設定する（Ｓ９８）。

インデックス変数ｖの参照先が葉（ＮＩＬ）になるまで、Ｓ９３〜Ｓ９８の処理を繰り返す。インデックス変数ｖの参照先が葉（ＮＩＬ）になった場合（Ｓ９２で「Ｙｅｓ」）、区間木検索部４２は、時刻変数ｔを受信・応答部４１に返す。

図２２は、本実施形態に係るプログラムを実行するコンピュータのハードウェア環境の構成ブロック図である。コンピュータ８０は、負荷分散器１２、ストレージプロキシ１３、メタデータサーバ１５、ストレージノード１６、クライアント１０、再生クライアント５０である。コンピュータ８０は、ＣＰＵ８２、ＲＯＭ８３、ＲＡＭ８６、通信Ｉ／Ｆ８４、記憶装置８７、出力Ｉ／Ｆ８１、入力Ｉ／Ｆ８５、読み取り装置８８、バス８９、出力機器９１、入力機器９２によって構成されている。

ここで、ＣＰＵは、中央演算装置を示す。ＲＯＭは、リードオンリメモリを示す。ＲＡＭは、ランダムアクセスメモリを示す。Ｉ／Ｆは、インターフェースを示す。バス８９には、ＣＰＵ８２、ＲＯＭ８３、ＲＡＭ８６、通信Ｉ／Ｆ８４、記憶装置８７、出力Ｉ／Ｆ８１、入力Ｉ／Ｆ８５、及び読み取り装置８８が接続されている。読み取り装置８８は、可搬型記録媒体を読み出す装置である。出力機器９１は、出力Ｉ／Ｆ８１に接続されている。入力機器９２は、入力Ｉ／Ｆ８５に接続にされている。

記憶装置８７としては、ハードディスク、フラッシュメモリ、磁気ディスクなど様々な形式の記憶装置を使用することができる。記憶装置８７またはＲＯＭ８３には、本実施形態に係るプログラム等が格納されている。ストレージプロキシ１３の場合、記憶装置８７には、例えば、内部バッファメモリ領域１４がある。また、メタデータサーバ１５の場合、記憶装置８７またはＲＯＭ８３には、例えば、区間管理表４４が格納されている。ストレージノード１６の場合、記憶装置８７には、例えば、イベントブロックを格納する領域がある。再生クライアント５０の場合、記憶装置８７には、例えば、マージツリー格納領域５３がある。
ＣＰＵ８２は、記憶装置８７等に格納した上記実施形態で説明した処理を実現するプログラムを読み出し、当該プログラムを実行する。

上記実施形態で説明した処理を実現するプログラムは、プログラム提供者側から通信ネットワーク９０、および通信Ｉ／Ｆ８４を介して、例えば記憶装置８７に格納されてもよい。また、上記実施形態で説明した処理を実現するプログラムは、市販され、流通している可搬型記憶媒体に格納されていてもよい。この場合、この可搬型記憶媒体は読み取り装置８８にセットされて、ＣＰＵ８２によってそのプログラムが読み出されて、実行されてもよい。可搬型記憶媒体としてはＣＤ−ＲＯＭ、フレキシブルディスク、光ディスク、光磁気ディスク、ＩＣカード、ＵＳＢメモリ装置など様々な形式の記憶媒体を使用することができる。このような記憶媒体に格納されたプログラムが読み取り装置８８によって読み取られる。

また、入力機器９２には、キーボード、マウス、電子カメラ、ウェブカメラ、マイク、スキャナ、センサ、タブレットなどを用いることが可能である。また、出力機器９１には、ディスプレイ、プリンタ、スピーカなどを用いることが可能である。また、ネットワーク９０は、インターネット、ＬＡＮ、ＷＡＮ、専用線、有線、無線等の通信網であってよい。

本実施形態によれば、可変大流量のストリームデータを高速に蓄積・再生することができる。まず、以下のようにして、可変大流量のストリームデータを高速に蓄積することができる。ストリームは、負荷分散器１２によって複数のストレージプロキシ１３に分配される。したがって、負荷分散器１２はネットワークの性能限界までストリームのデータを捌くことができる。したがって、ストリームデータの蓄積は、ストレージノードの台数を十分に用意すれば負荷分散器のネットワーク性能限界まで達成できる。

また、ストレージプロキシ１３は、イベントブロックという塊にイベントデータをパックする。これによって、ストレージの最大スループットを達成できるサイズでストレージへの書き込みを行える。また、ストレージの書き込みは複数のストレージプロキシ１３によって並列して行えるため、ストレージノード１６の台数に比例する書き込み性能が得られる。すなわち、ストレージプロキシとストレージノードの台数はストリームの流量に応じて変化させることができる。

また、データを固めたイベントブロックがストレージ上のどこに存在しているかをメタデータサーバ１５によって管理することでストレージノード１６の台数が動的に拡縮することに対応している。メタデータサーバ１５の管理対象は、イベントブロック名と区間情報である。

次に、高速に再生する技術上の利点は以下の通りである。再生クライアント５０は、イベントブロックに分割されたデータから元のストリームを再構成することができる。再生に必要なイベントブロックは負荷分散器１２を通して獲得することで、ネットワークリソースを有効に利用することができる。

また、以下のようにして、時刻（または、イベント通番）が指定されたとき、その時刻（またはイベント通番）からストリームを再生することができる。具体的には、時刻が指定されたとき、その時刻のデータを含む可能性のあるイベントブロックの最小集合を求めることができる。

また、以下のようにして、再生に必要なシステムリソース量を適切に制御し、現実的なシステムリソースの元で再生処理を行うことができる。再生クライアント５０は、再生時間が長い場合には、再生時刻範囲にあるイベントブロックを一括して読み出すことは行わない。再生開始時刻からΔ時間分のイベントブロックを読み出し、少なくともΔ時間分のデータを保持するマージツリーを作る。マージツリーから部分ストリームを再構成し、再生する。次の時刻は、前の再生時刻＋Δ時間とするのではなく、「次の開始時刻」を区間木から決定される。これによって、Δが短い場合でも効率を落とさずに、次の部分ストリームを再構成できる。このように増加的（インクリメンタル）処理ができ、かつ、システムリソースに無駄がない点は新規かつ優位である。

また、本実施形態のマージツリーを用いることにより、ストレージノード１６からの読み出し中のイベントブロックについては、再生クライアント５０は読み出しが完了するまで読み出しをせず、読み出し完了のイベントブロックを次々と読み出す。このようにマージツリーを用いた読み出し処理は並列処理であり、処理の単位は節点からのデータの読み出しという極めて粒度の細かいものである点で高速性を実現することができる。したがって、ストリームデータの再生は、ストレージノードの並列読み出しにより高速化される。
なお、本発明は、以上に述べた実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の構成または実施形態を取ることができる。

上記実施形態に関し、さらに以下の付記を開示する。
（付記１） 時系列のデータが分割されたデータを示す分割データを格納するデータ格納部と、
前記分割データを識別する識別情報と、前記分割データの開始時刻及び終了時刻を示す区間の情報とを関連付けた情報を格納する区間格納部と、
第１の時刻を取得し、前記区間格納部から、該第１の時刻と該第１の時刻を所定時間経過した第２の時刻との間の区間に重複する区間の検索を行い、該検索を行った該区間に対する前記分割データの識別情報を取得する検索部と、
前記データ格納部から、取得した前記識別情報に対応する前記分割データを取得し、取得した分割データを時刻順に読み出す読出部と、
を備えることを特徴とするストレージシステム。
（付記２） 前記検索部は、前記重複する区間に含まれない前記分割データであって前記第２の時刻より遅く、前記終了時刻以前の該分割データのうち、最も早い開始時刻を取得し、取得した該開始時刻を用いて、次の前記検索を行う
ことを特徴とする付記１に記載のストレージシステム。
（付記３） 前記読出部は、前記データ格納部からの取得が完了した前記分割データのうち、最も早い前記開始時刻に対応する前記識別情報で特定される前記分割データを読み出す
ことを特徴とする付記１または２に記載のストレージシステム。
（付記４） 前記ストレージシステムは、さらに、
負荷分散アルゴリズムを用いて、前記時系列のデータを振り分ける振分部
を備えることを特徴とする付記１〜３のうちいずれか１項に記載のストレージシステム。
（付記５） ストレージ装置に接続された情報処理装置の制御プログラムにおいて、
前記情報処理装置に、
第１の時刻を取得させ、
時系列のデータが分割されたデータを示す分割データを識別する識別情報と、前記分割データの開始時刻及び終了時刻を示す区間の情報とを関連付けた情報を格納する区間格納部から、該第１の時刻と該第１の時刻を所定時間経過した第２の時刻との間の区間に重複する区間の検索を要求させ、
前記要求に応じて、前記ストレージ装置が、前記区間格納部から、該第１の時刻と該第１の時刻を所定時間経過した第２の時刻との間の区間に重複する区間の検索を行った該区間に対する前記分割データの識別情報を取得させ、
前記分割データを格納するデータ格納部から、取得した前記識別情報に対応する前記分割データを取得し、取得した分割データを時刻順に読み出させることを特徴とする情報処理装置の制御プログラム。
（付記６） 前記検索を行った前記区間に対する前記分割データの識別情報を取得する場合、前記重複する区間に含まれない前記分割データであって前記第２の時刻より遅く、前記終了時刻以前の該分割データのうち、最も早い開始時刻を取得し、取得した該開始時刻を用いて、次の前記検索を行う
ことを特徴とする付記５に記載の検索プログラム。
（付記７） 前記取得した分割データを時刻順に読み出す場合、前記データ格納部からの取得が完了した前記分割データのうち、最も早い前記開始時刻に対応する前記識別情報で特定される前記分割データを読み出す
ことを特徴とする付記５または６に記載の検索プログラム。
（付記８） ストレージ装置と、前記ストレージ装置に接続された情報処理装置を有するストレージシステムの制御方法において、
前記情報処理装置が、第１の時刻を取得し、
前記情報処理装置が、時系列のデータが分割されたデータを示す分割データを識別する識別情報と、前記分割データの開始時刻及び終了時刻を示す区間の情報とを関連付けた情報を格納する区間格納部から、該第１の時刻と該第１の時刻を所定時間経過した第２の時刻との間の区間に重複する区間の検索を要求し、
前記要求に応じて、前記ストレージ装置が、前記区間格納部から、該第１の時刻と該第１の時刻を所定時間経過した第２の時刻との間の区間に重複する区間の検索を行った該区間に対する前記分割データの識別情報を応答し、
前記情報処理装置が、前記分割データを格納するデータ格納部から、取得した前記識別情報に対応する前記分割データを取得し、取得した分割データを時刻順に読み出すことを特徴とするストレージシステムの制御方法。
（付記９） 前記ストレージ装置は、前記検索を行った前記区間に対する前記分割データの識別情報を取得する場合、前記重複する区間に含まれない前記分割データであって前記第２の時刻より遅く、前記終了時刻以前の該分割データのうち、最も早い開始時刻を取得し、取得した該開始時刻を用いて、次の前記検索を行う
ことを特徴とする付記８に記載のストレージシステムの制御方法。
（付記１０） 前記情報処理装置は、前記取得した分割データを時刻順に読み出す場合、前記データ格納部からの取得が完了した前記分割データのうち、最も早い前記開始時刻に対応する前記識別情報で特定される前記分割データを読み出す
ことを特徴とする付記８または９に記載のストレージシステムの制御方法。
（付記１１） 前記ストレージシステムの制御方法において、
振分部は、負荷分散アルゴリズムを用いて、前記時系列のデータを振り分ける
を備えることを特徴とする付記８〜１０のうちいずれか１項に記載のストレージシステムの制御方法。

１ ストレージシステム
２ データ格納部
３ 区間格納部
４ 検索部
５ 読出部
１０ クライアント
１１ ストリームストレージシステム
１２ 負荷分散器
１３ ストレージプロキシ
１４ 内部バッファメモリ領域
１５ メタデータサーバ
１６ ストレージノード

Claims (5)

1. 時系列のデータが分割されたデータを示す分割データを格納するデータ格納部と、
   前記分割データを識別する識別情報と、前記分割データの開始時刻及び終了時刻を示す区間の情報とを関連付けた情報を格納する区間格納部と、
   第１の時刻を取得し、前記区間格納部から、該第１の時刻と該第１の時刻を所定時間経過した第２の時刻との間の区間に重複する区間の検索を行い、該検索を行った該区間に対する前記分割データの識別情報を取得する検索部と、
   前記データ格納部から、取得した前記識別情報に対応する前記分割データを取得し、取得した分割データを時刻順に読み出す読出部と、
   を備え、
   前記検索部は、前記重複する区間に含まれない前記分割データであって前記第２の時刻より遅く、前記終了時刻以前の該分割データのうち、最も早い開始時刻を取得し、取得した該開始時刻を用いて、次の前記検索を行う
   ことを特徴とするストレージシステム。
2. 前記読出部は、前記データ格納部からの取得が完了した前記分割データのうち、最も早い前記開始時刻に対応する前記識別情報で特定される前記分割データを読み出す
   ことを特徴とする請求項１に記載のストレージシステム。
3. 前記ストレージシステムは、さらに、
   負荷分散アルゴリズムを用いて、前記時系列のデータを振り分ける振分部
   を備えることを特徴とする請求項１または２に記載のストレージシステム。
4. ストレージ装置に接続された情報処理装置の制御プログラムにおいて、
   前記情報処理装置に、
   第１の時刻を取得させ、
   時系列のデータが分割されたデータを示す分割データを識別する識別情報と、前記分割データの開始時刻及び終了時刻を示す区間の情報とを関連付けた情報を格納する区間格納部から、該第１の時刻と該第１の時刻を所定時間経過した第２の時刻との間の区間に重複する区間の検索を要求させ、
   前記要求に応じて、前記ストレージ装置が、前記区間格納部から、該第１の時刻と該第１の時刻を所定時間経過した第２の時刻との間の区間に重複する区間の検索を行った該区間に対する前記分割データの識別情報を取得させ、
   前記分割データを格納するデータ格納部から、取得した前記識別情報に対応する前記分割データを取得し、取得した分割データを時刻順に読み出させ、
   前記検索を行った前記区間に対する前記分割データの識別情報の取得では、前記重複する区間に含まれない前記分割データであって前記第２の時刻より遅く、前記終了時刻以前の該分割データのうち、最も早い開始時刻を取得し、取得した該開始時刻を用いて、次の前記検索を行う
   ことを特徴とする情報処理装置の制御プログラム。
5. ストレージ装置と、前記ストレージ装置に接続された情報処理装置を有するストレージシステムの制御方法において、
   前記情報処理装置が、第１の時刻を取得し、
   前記情報処理装置が、時系列のデータが分割されたデータを示す分割データを識別する識別情報と、前記分割データの開始時刻及び終了時刻を示す区間の情報とを関連付けた情報を格納する区間格納部から、該第１の時刻と該第１の時刻を所定時間経過した第２の時刻との間の区間に重複する区間の検索を要求し、
   前記要求に応じて、前記ストレージ装置が、前記区間格納部から、該第１の時刻と該第１の時刻を所定時間経過した第２の時刻との間の区間に重複する区間の検索を行った該区間に対する前記分割データの識別情報を応答し、
   前記情報処理装置が、前記分割データを格納するデータ格納部から、取得した前記識別情報に対応する前記分割データを取得し、取得した分割データを時刻順に読み出し、
   前記ストレージ装置は、前記検索を行った前記区間に対する前記分割データの識別情報の応答において、前記重複する区間に含まれない前記分割データであって前記第２の時刻より遅く、前記終了時刻以前の該分割データのうち、最も早い開始時刻を取得し、取得した該開始時刻を用いて、次の前記検索を行う
   ことを特徴とするストレージシステムの制御方法。