確率過程に従ったリクエスト機能の実装

# 確立過程のプログラミング
## 背景
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$は以下の指数分布に従う。
```math
f(x;\lambda) = \lambda e^{-\lambda x}\  (0\ for\ x<0)
```
ここで、$\lambda$は単位時間あたりのイベント発生回数である。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3636063/5d44906b-7cbf-7447-a5d4-3593545bcb21.png)
(https://ja.wikipedia.org/wiki/指数分布)
目的は、この指数分布の値をランダムに取得することである。このためには、**指数分布のパーセンタイル点を求めれば良い**ので、指数分布の累積分布関数を取得する。
```math
\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}
}
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3636063/aafe58d1-d1db-b339-b090-e3f6dce759dd.png)
(https://ja.wikipedia.org/wiki/指数分布)
このグラフの縦軸は、次のイベントまでの時間間隔$x$である確率を表す。よって、この累積分布関数の逆関数を取得すれば、一様乱数を指数分布に変換できる。
```math
F^{-1}(x;\lambda)=\frac{-\log (1-x)}{\lambda}
```


## 実装
実装上は、StochasticProcessインターフェースを利用して実装を具象クラスに任せることで、さまざまな確率過程モデルに従ったインターバルを取得できるようにする。
```Java:StocichastucProcess
public interface StochasticProcess {
    long nextIntervalInMilliSecond();
}
```
```java:PoissonProcess
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
    }
}
```
```java:FixedIntervalProcess
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;
    }
}
```
このようにしておくことで、今後新たな分布に従ったリクエストを行いたいときには、このインターフェースを実装する形で具象クラスを作れば、新しい分布を簡単に追加可能になる。

# 参考
https://compneuro-julia.github.io/neuron-model/isi.html

https://data-science.gr.jp/theory/tpd_exponential_distribution.html