確立過程のプログラミング
背景
FaaSの研究目的で開発中のDistributed FaaSRunnerというソフトウェアに、特定のスループットに従ったアクセスをする機能を実装しようとしていた。このために、最初に考えたアプローチは、リクエストの直後に指定した期間プログラムを待機させる方法だった。
直面した課題
リクエストパターンは、以下の2つを実装しようと考えていた。
- 一定間隔でのリクエスト
- Poisson分布に従ったリクエスト
理由はわからないが、これまでの有名なLoad Testing Tools（JMeterなど）にはPoisson分布に従ったリクエスト機能は付いておらず、Poisson分布に関してはnoveltyの観点で実装が不可欠だった。
一定間隔でのリクエスト
一定間隔でのリクエスト、つまり固定インターバル(fixed interval)モードについては、リクエスト→固定長時間(i.e. 100ms)待機→リクエストを繰り返すことで実現できるため、待機時間を直接指定することで指定したスループットを実現することができた。
Poisson分布に従ったリクエスト
次に、Poisson分布に従ったリクエストを、待機時間を直接指定することで実現しようとした。例えば、$\lambda = 10 $(requests/sec)を指定したとする。このとき、待機時間は、$Poisson(\lambda = 10)$からサンプルを1度取り出し、その時の発生頻度に従った待機時間を計算し、その分だけ待機すれば良い。つまり、発生頻度が5 requests/secというサンプルを引いた場合、1(sec) / 5 = 200msを待機時間にすれば良い。
しかしながら、小さい$\lambda$に対しては、単位時間あたりの発生回数が0になるパターンが頻発する。このとき、次の待機時間は1 (sec) / 0となり、0割が発生してしまう。このため、Poisson分布の模倣に関しては待機時間を発生頻度から算出するアプローチは有効でないとわかった。
解決方法
待機時間を指定するのに、発生頻度から算出するのではなく、次のイベントまでの時間間隔の分布を求めれば0割の問題を回避できる。
Poisson分布に従うイベントでは、次のイベントまでの時間間隔$x$は以下の指数分布に従う。
f(x;\lambda) = \lambda e^{-\lambda x}\ (0\ for\ x<0)
ここで、$\lambda$は単位時間あたりのイベント発生回数である。
(https://ja.wikipedia.org/wiki/指数分布)
目的は、この指数分布の値をランダムに取得することである。このためには、指数分布のパーセンタイル点を求めれば良いので、指数分布の累積分布関数を取得する。
\displaylines{
\begin{align}
F(x;\lambda)=\int _{-\infty} ^{x} {f(t;\lambda)dt} &= \int _{-\infty} ^{x}\lambda e^{-\lambda t}dt\\
&= 1-e^{-\lambda x}
\end{align}
}
(https://ja.wikipedia.org/wiki/指数分布)
このグラフの縦軸は、次のイベントまでの時間間隔$x$である確率を表す。よって、この累積分布関数の逆関数を取得すれば、一様乱数を指数分布に変換できる。
F^{-1}(x;\lambda)=\frac{-\log (1-x)}{\lambda}
実装
実装上は、StochasticProcessインターフェースを利用して実装を具象クラスに任せることで、さまざまな確率過程モデルに従ったインターバルを取得できるようにする。
public interface StochasticProcess {
long nextIntervalInMilliSecond();
}
import java.util.Random;
public class PoissonProcess implements StochasticProcess {
private double requestPerSecond;
private Random random;
private final int MILLIS_IN_SECOND = 1000;
public PoissonProcess(double requestPerSecond) {
this.requestPerSecond = requestPerSecond;
this.random = new Random();
}
public long nextIntervalInMilliSecond() {
double randomValue = random.nextDouble();
double interval = -Math.log(1 - randomValue) / requestPerSecond;
return (long) (interval * MILLIS_IN_SECOND); // convert to milliseconds
}
}
public class FixedIntervalProcess implements StochasticProcess{
private int requestPerSecond;
private final int MILLIS_IN_SECOND = 1000;
public FixedIntervalProcess(int requestPerSecond) {
this.requestPerSecond = requestPerSecond;
}
@Override
public long nextIntervalInMilliSecond() {
return MILLIS_IN_SECOND / requestPerSecond;
}
}
このようにしておくことで、今後新たな分布に従ったリクエストを行いたいときには、このインターフェースを実装する形で具象クラスを作れば、新しい分布を簡単に追加可能になる。
参考