I O Scheduling based on Request Deadlines

CannyLSでは通常、一つのストレージインスタンスを対応するデバイス経由で操作することになる。 デバイスには、それに対して並行的に発行された未処理の操作要求群を格納するための要求キューが備わっている。デバイスは、このキューから優先度が高い順に要求を取り出して、順次対応する操作を実行していくことになるが、この「平行処理要求群の優先度付け」のことを I/Oスケジューリング と呼称している。

操作要求群の優先度付け

各操作要求にはデッドラインと呼ばれる、時間軸ベースの優先度が指定可能となっている。 デッドラインは対象要求が「いつまでに処理されて欲しいか」を指定するためのものであり、要求群はその時刻が早い順に、デバイスのキュー内で並べ替えられて処理されていくことになる。

順序保証

上述の通り、要求群はそのデッドラインに応じて実行順序が並び替えられることになるため、必ずしもその要求の発行順に処理されるとは限らない。

現状のCannyLSが提供する、同一デバイスに対して並行的に発行された操作群の実行順序に関する保証は以下の通りとなる:

• (a) 操作要求AおよびBが存在するとして、
• (b) デバイスが、Aからの要求をBからの要求よりも先に受信し、かつ、
• (c) AのデッドラインがBのデッドライン以下なら、
• (d) Aが指定した操作はBの操作よりも先に実行されること、が保証されている

なお「Aの要求発行が、Bの要求発行に対して因果的に先行している」なら(b)は確実に成立する。 "因果的に先行"の定義に関しては"Time, Clocks, and theOrdering of Events ina Distributed System"を参照のこと。

デッドラインの使用例

デッドラインが有用な例をいくつか挙げておく。

先読み

動画のストリーミング配信を考えてみる。 動画ファイルが一定サイズ毎に、lumpに区切られてCannyLSに格納されているとして、視聴者が動画の先頭から視聴を開始した場合の、動画ファイルに対するアクセスパターンは、次のようになる:

1. 動画ファイルの先頭部分を格納しているlumpを取得して、視聴開始に必要なデータを読み込む
2. 以降は、時間経過に応じて、その時に必要なデータが格納されているlumpを読み込みつつ、配信を行っていく

動画の場合には、そのビットレートを参照することで「未来の時刻Tに必要なデータがどれか」ということがかなり正確に予測可能となっている。そのため、次に必要となるデータを保持しているlumpの取得要求を、デッドラインにそれが実際に必要となる時刻を指定して事前に発行しておくことで先読みが可能となる。仮にデッドライン指定が無かったとしても、同様の先読みは可能ではあるが、その場合、同時に発行されたより優先度の高い要求群(e.g., 視聴開始用のデータ取得)の実行を阻害してしまう可能性がある。デッドライン指定があれば、先読み要求に関して「デバイスが混雑しているなら実際に必要になるまで実行を遅延」させ、逆に「デバイスが空いているなら早めに実行して活用効率を上げる」といった制御が可能となる。

書き込みよりも読み込みを優先

これも動画のストリーミング配信の例にして考えると、通常、動画ファイルの書き込みに比べて、読み込みの方がレイテンシに対する要求が高くなる（後者のレイテンシが長かったり、バラつきが大きかったりすると、最悪視聴時に動画の再生が途切れ途切れになってしまうため）。その場合、書き込み操作のデッドラインを長めに、読み込み操作のデッドラインを短めに設定しておけば、デバイスが忙しい場合には、後者の方が優先されるようになり、視聴体験が損なわれにくくなる。

バックグランドタスクの優先度を下げる

CannyLSの利用者側で、例えば、GCやコンパクション、スナップショット、データ移動、等のような処理を実行する必要がある場合には、それらの読み書き操作の優先度を下げておくことで、そういったバックグランドタスクの実行が、通常のユーザからの要求を処理速度を低下を招きにくくすることが可能となる。