Windowless moving percentileをgoで実装してみる
Windowless moving percentileとは指数平滑移動平均(Exponential moving average)をベースにしたパーセンタイル値の予測方法で 名前の通り、windowlessということで、windowなしにパーセンタイルの予測が可能で、メモリ効率や計算効率が良い。 windowとは、固定サイズの直近の観測値を集めた配列で、その配列の長さは100より大きい値を選ぶことが多いそう。 それを必要としないということは、メモリに優しいことが分かる。
今回はこのWindowless moving percentileをgoで実装していく。
Windowless moving percentileはこの記事 にて説明が書かれている。 ここの記述をベースに実装する。
まずはexponential moving percentileを実装する
Windowless moving percentileの実装の前に、exponential moving percentile を実装する必要があるので まずはこれを実装する。
以下のようなコードになる。
type ExponentialMovingAverageState struct { r float64 average float64 count int32 count_min int32 } func NewExpMovingAvg(r float64) *ExponentialMovingAverageState { count_min := int32(math.Trunc(math.Ceil(1 / r))) return &ExponentialMovingAverageState{ r: r, count_min: count_min, } } func (s *ExponentialMovingAverageState) Sample(x float64) { var alpha float64 if s.count < s.count_min { s.count++ } if s.count >= s.count_min { alpha = s.r } else { alpha = 1 / float64(s.count) } s.average = alpha * x + (1-alpha)*s.average }
ユーザから渡された値 r
(0 < r <= 1)を使って
指数平滑移動平均を計算していくことになる。
この値は新しい観測値をどの程度重み付けするか、という値になる。
この値は windowless moving percentileでも使われる。
次はMoving varianceを計算する構造体を実装する
次はmoving varianceを計算する構造体を実装する。といいつつ、サンプル実装だと標準偏差も計算している謎の型になっている・・・。
ほぼサンプルのままなので 説明は省くがソースコードだけは書いておく。
type ExponentialMovingVarianceState struct { average *ExponentialMovingAverageState variance *ExponentialMovingAverageState stdev float64 normalized float64 } func NewExpMovingVariance(alphaAvg, alphaVar float64) *ExponentialMovingVarianceState { return &ExponentialMovingVarianceState{ average: NewExpMovingAvg(alphaAvg), variance: NewExpMovingAvg(alphaVar), } } func (s *ExponentialMovingVarianceState) Sample(x float64) { if s.average.count > 0 { s.variance.Sample(math.Pow(x - s.average.average, 2)) } s.average.Sample(x) s.stdev = math.Sqrt(s.variance.average) if s.stdev != 0 { s.normalized = (x - s.average.average) / s.stdev } }
Windowless moving percentileを実装してみる
ここで準備が整ったので 本命のWindowless moving percentile実装していく。
構造体の定義とその初期化関数としては以下のようになった。
type WindowlessMovingPercentileState struct { r float64 p float64 value float64 delta float64 deltaState *ExponentialMovingVarianceState count int32 } func NewWindowlessMovingPercentile(percentile float64, r, alphaAvg, alphaVar float64) *WindowlessMovingPercentileState { return &WindowlessMovingPercentileState{ r: r, p: percentile, delta: r, deltaState: NewExpMovingVariance(alphaAvg, alphaVar), } }
サンプル実装を参考に書いてみたところ、以下のような実装になった。
func (s *WindowlessMovingPercentileState) Sample(x float64) { if s.count < 2 { s.count++ } s.deltaState.Sample(x) // s.count >= 2 の場合のみ stdevの値が利用可能になるので guardを入れている if s.count >= 2 { s.delta = s.deltaState.stdev * s.r } if s.count == 1 { s.value = x } else if x < s.value { s.value = s.value - s.delta / s.p } else if x > s.value { s.value = s.value + s.delta / (1 - s.p) } }
特に難しいところはなさそうに見えますが コードを少し間違えていたりしてハマりました・・・。
というわけで単に写経してみたよって記事でした。
一応、Go playgroundに置いておきました。
まとめ
今回はWindowless moving percentileを実装してみた。 このアルゴリズムは Netflix/concurrency-limits の go実装である、go-concurrency-limits にリファレンスされているアルゴリズムである。 windowlessということで、windowなしにpercentileの計算が出来るので メモリに優しく並行性制御が出来るようになる。
漸化式の非対称性が気になるので もう少し遊んでみようかなと思っています。
終わり。
EC2インスタンスの秘密鍵の管理から開放される ssos (ssh-setup-over-ssm) をリリースした
EC2インスタンスに入りたい時ってたまにないですか?
EC2インスタンスのsshの秘密鍵の管理をどうしよう、とか EC2インスタンスのユーザの管理をどうしよう、とか悩みますよね。
今回リリースした、ssos (ssh-setup-over-ssm) を使えば EC2インスタンスを使いたい人が、自分でセットアップすることが出来るようになります。
このツールを使うに当たって必要なのは AWSのクレデンシャルのみです。EC2インスタンスの秘密鍵も必要ありません。 Systems Manager経由でSend Commandできるインスタンスであれば sshでログイン出来るようになります。
今回作ったssosのリポジトリはこちらです。
はじめに
対象のEC2インスタンスでターミナルを使うだけなら Systems Managerを使えば、確かに、sshを使わなくても ターミナルを使うことは出来ます。
しかし、scpをしたい、となった場合はどうでしょう。 ssh鍵を使わないと出来ないです(はずです)。 加えて通常ssh公開鍵を置くには、EC2の秘密鍵が必要です。 また、EC2の秘密鍵を使う場合、その秘密鍵を管理する方法に悩まされることになります。
今回リリースした、ssosでは、秘密鍵の管理に苦しまされることもなく EC2インスタンスを使いたい人が、自分でsshの公開鍵を配置して 自分でsshの設定をすることが出来るようになります。
使うにあたって必要なもの
必要なものは以下のものです。 ログインしたいEC2の秘密鍵は必要ありません。
ssosで出来ること
出来ることは至ってシンプルです。現状、以下の2つです。
- ユーザの作成
- SSHの公開鍵の設定
使い方は以下の通りです。
# ユーザの作成 ssos create-user -u masaya -i i-xxxxxxxxxxxxxxxx # ssh公開鍵の配置 ssos add-ssh-key -u masaya -i i-xxxxxxxxxxxxxxxx -k ~/.ssh/id_rsa.pub
インストール方法
インストールはGithub Releaseにリリースしているのでそちらからダウンロードして パスに入れてください。
# MacOS curl -L https://github.com/wreulicke/ssos/releases/download/v0.0.3/ssos_0.0.3_darwin_amd64 -o /usr/local/bin/ssos # Linux curl -L https://github.com/wreulicke/ssos/releases/download/v0.0.3/ssos_0.0.3_linux_amd64 -o /usr/local/bin/ssos # Windows curl -L https://github.com/wreulicke/ssos/releases/download/v0.0.3/ssos_0.0.3_windows_amd64.exe -o <path-directory>/ssos.exe
まとめ
もともと、ssh-over-ssm というbashスクリプトがあって 今回リリースしたssosのアイデアのほとんどはこれを参考にしています。
前々職や前職で悩まされていたEC2の秘密鍵の共有方法や EC2の公開鍵のセットアップの属人性を解決したいと思い、作りました。
また、今回作ったssosではAmazon Linux2をベースにprovisioning 方法を考えています。 そのため、他の環境では動かないかもしれません。
終わり。
追記: この記事書いてるときに見つけたけど
作ったユーザでsudoしようとしたら、パスワード要求されて泣いてる。
パスワードなしでsudo使えるようにユーザを作るようにしようと思います。
v0.0.2で対応しました。
Docker/KubernetesにおけるNode.js: ヒープサイズがcgroupのlimitを見て決められるようになるのは v12.7.0から
仕事で気になって調べたので書いておきます。
Node.jsは v12.7.0以降じゃないと
cgroupのmemory limitを見てくれません。
つまり、v12.7.0より前のバージョンのNode.jsでは、ヒープメモリの容量を設定するオプション `--max-old-space-size`を使う必要があります。
cgroupのmemory limitを見るようになったNodeのPRとしては、これです。
github.com
ちなみに、cgroupのlimitはKubernetesのresource limitsで
dockerとしては --memoryというオプションで設定可能です。