十分に枯れていてあまりトラブルになることは無いけれど、今後も使い続けられる技術なので、 その挙動を知っておくことに意味はあると思う。 NICの完全仮想化・準仮想化 おさらい。完全仮想化は、ゲスト自身が仮想環境で動作していることを認識できないような仮想化のこと。 ホストは、ゲストが利用するデバイスの挙動をすべて模倣する必要がある。 デバイスの模倣のために、大量のトラップが発生し、CPUがホスト側の処理に使われてしまう。 また、デバイスのエミュレーションをホスト側ユーザプロセスで行う場合には、 スケジューリング待ちによる遅延も発生してしまう。 一方、準仮想化では、ゲスト自身が仮想環境で動作していることを認識した上で、 ホストと協力してパフォーマンスを向上の図る。 virtio は準仮想化専用のデバイスドライバによって、仮想的なデバイスを操作する。 アーキテクチャ フロントエンドドライバとバックエンドドライバを、vringが繋ぐ構成になっている。 フロントエンドドライバ ゲスト側で動作する。ゲストOSが発行したIOをvringを経由して、バックエンドドライバへ送る。 バックエンドドライバ ホスト側で動作する。vring経由で受け取ったIOを、物理デバイスへ送る。 https://www.cs.cmu.edu/~412/lectures/Virtio_2015-10-14.pdf Virtio 仕様 SAMLやebXMLなどを標準化している団体 OASIS が Virtual I/O Device (VIRTIO) Version 1.1 として仕様をまとめている。 コールバックや各種データ構造の仕様を決めている。 Virtqueue 実際のIOを担当する部分で、ゲスト物理メモリの一部をホスト側と共有することで、 双方向での読み書きを実現できる。 また、双方向に通知を送るための仕組みも持っており、ホスト側へはMMIO経由で、 ゲスト側へは割り込みを使って通知を送る。 disable_cdやenable_cbといった関数で、割り込み抑制をもう一方へ伝えることができる。 例えば、ゲスト側ドライバで一定期間の間は割り込みが不要な場合には、 その旨を disable_cd でホスト側へ伝える。 通知を送る際には kick を呼ぶ。 struct virtqueue_ops { int (*add_buf)(struct virtqueue *vq, struct scatterlist sg[], unsigned int out_num, unsigned int in_num, void *data); void (*kick)(struct virtqueue *vq); void *(*get_buf)(struct virtqueue *vq, unsigned int *len); void (*disable_cb)(struct virtqueue *vq); bool (*enable_cb)(struct virtqueue *vq); }; https://elixir....

Ubiquiti Networks社のルータ EdgeRouter X （ER-X）を数年前に購入したものの放置したままだったので、 今回 L2 スイッチとして使ってみた。 ER-X上ではDebianベースのOSで動いているため、Prometheus用に Node exporter のような監視プログラムを使うことができる。 Prometheus自体はRaspberry Pi上で動かした。 ElastiFlowも動かしたかったが、Raspberry Piのスペックでは厳しそうだった。 Prometheus と Grafana の導入 Raspberry PiにPrometheusとGrafnaをインストールする。 Prometheusはメトリクスを収集するために、GrafanaはPrometheusで収集したメトリクスをウェブUIから確認するために使う。 wget -q -O - https://packages.grafana.com/gpg.key | sudo apt-key add - echo "deb https://packages.grafana.com/oss/deb stable main" | sudo tee /etc/apt/sources.list.d/grafana.list apt install prometheus grafana -y sudo systemctl start prometheus sudo systemctl start grafana-server Node exporter の導入 ER-XにNode exporterをインストールする。 CPU、メモリ、ディスク、ネットワークに関連するメトリクスを自動で収集してくれる。 curl -L https://github.com/prometheus/node_exporter/releases/download/v1.0.1/node_exporter-1.0.1.linux-mipsle.tar.gz -o node_exporter.tar.gz tar xf ./node_exporter.tar.gz sudo mv ....

提出したコード 文字列 $t$ が与えられるので、$t$ の循環左シフト後と循環右シフト後の文字列を等しくしたい。 $t$からいくつか文字を取り除いてこの条件を満たすときに、取り除く最小の文字数は？ $n$ を $t$ の文字列長として、その偶奇で分けて考える。 $n$ が奇数の場合 $t = t_1 t_2 t_3 t_4 t_5$ を例とする。 巡回左シフト $ t_2 t_3 t_4 t_5 t_1$ と巡回右シフト $t_5 t_1 t_2 t_3 t_4$ を等しくしたい。 つまり、すべての文字を等しくする必要がある。 $n$ が偶数の場合 $t = t_1 t_2 t_3 t_4$ を例とする。 巡回左シフト $t_2 t_3 t_4 t_1$ と巡回右シフト $t_4 t_1 t_2 t_3$ を等しくしたい。 つまり、偶数番目はすべて同じ文字であって、かつ奇数番目もすべて同じ文字でないといけない。 解法 いくつかの文字を取り除いた後の文字列の先頭2文字について全探索をする。 先頭2文字が同じ場合、先頭2文字$aa$の後に何文字か$a \dots a$が続けばよい。 違う場合は、先頭2文字$ab$の後に$ababab \dots ab$が続けばよい。

QEMU/KVM上で https://github.com/kelseyhightower/kubernetes-the-hard-wayを試してみたので、ログを残しておく。 元々の文章では、GCPを前提としているが、今回は手元のQEMU/KVM上で構築した。 バージョン一覧 kubernetes-the-hard-way bf2850974e19c118d04fdc0809ce2ae8a0026a27 Kubernetes 1.12.0 containerd Container Runtime 1.2.0-rc.0 gVisor 50c283b9f56bb7200938d9e207355f05f79f0d17 CNI Container Networking 0.6.0 etcd v3.3.9 CoreDNS v1.2.2 1. 事前準備 VMイメージを取得して、起動するまで。 # VMイメージの準備 $ http_dir=http://ftp.jaist.ac.jp/pub/Linux/Fedora/releases/30/Cloud/x86_64/images $ wget $http_dir/Fedora-Cloud-Base-30-1.2.x86_64.qcow2 $ virt-customize -a /var/lib/libvirt/images/Fedora-Cloud-Base-30-1.2.x86_64.qcow2 \ --run-command 'yum remove cloud-init* -y' \ --root-password password:root $ cd /var/lib/libvirt/images/ $ for i in 0 1 2 ; do \ sudo cp ./Fedora-Cloud-Base-30-1.2.x86_64.qcow2 controller-$i.qcow2; \ sudo cp ./Fedora-Cloud-Base-30-1.2.x86_64.qcow2 worker-$i.qcow2; \ done # VM起動 $ for name in controller-0 controller-1 controller-2 worker-0 worker-1 worker-2 do sudo virt-install --name=$name --virt-type kvm --graphics none \ --disk /var/lib/libvirt/images/$name....

提出したコード 整数$a \ge 2$が与えられるので、$gcd(d_1+d_2,a)=1$を満たすような組$(d_1,d_2)$を求めたい。 ただし、$d_1 \ge 2$かつ$d_2 \ge 2$。 これを$n$個回繰り返す。 まず $a = {p_1}^{k_1} \cdot {p_2}^{k_2} \cdots {p_m}^{k_m}$ のように素因数分解を行う。 もし $m = 1$あるいは$a$が素数の場合には、答えは$(-1,-1)$。 $m \ge 2$の場合には、$(p_1, p_2 \cdot p_3 \cdots p_m)$が答えとなる。 なぜこれが答えでよいのか見ていく。 「$d_1 + d_2$がいかなる素因数$p_i$に対しても割り切れないこと」が言えればよい。 まず、「$d1 + d2$ が $p1$ で割り切れない」ことが正しいのか考えてみる。 $d1 \equiv 0, d2 \not \equiv 0 (mod \ p_1) $ より、$d1 + d2 \not \equiv 0 (mod \ p_1)$ となる。 続いて、「$d1 + d2$ は $p_i (2 \le i \le m)$ で割り切れない」ことが正しいのか考えてみる。 $d1 \not \equiv 0, d2 \equiv 0 (mod \ p_i) $ より、$d1 + d2 \not \equiv 0 (mod \ p_i)$ となる。...

提出したコード 木において「連結成分の数 = 頂点数 - 辺の数」で求められることに注目する。 直感的に、頂点が増えると連結成分の数が1増え、辺の数が増えると連結成分の数が1減るという感じで理解できる。 $f(L, R)$もこれで求められる。 $$ \begin{aligned} &f(L, R) \\ &= 区間[L \ R]に含まれる点の数 \\ &- 両端が区間[L \ R]に含まれる辺の数 \\ \end{aligned} $$ これをLとRの全通りで求めて総和をとればよい。 頂点数と辺の数はそれぞれ独立に求めていけばよい。 $$ \begin{aligned} &\sum_{L,R} f(L,R) \\ &= \sum_{L,R} 区間[L \ R]に含まれる頂点の数 \\ &- \sum_{L,R} 両端が区間[L \ R]に含まれる辺の数 \\ &= V - E \end{aligned} $$ 以下のように図示してみると、ある頂点$i$は全体で$(i+1)(N-i)$回現れるので、すべての$i$でこれの総和を取って$V$とすればよい。 同様にある辺$(u, v)$は全体で$(u+1)(N-v)$回現れるので、すべての辺について総和を取って$E$とする。 $V-E$が答えとなる。

提出したコード コンテスト後追加されたテストケース after_contest01.txt でコケた。 それ以外は自力で通ったので考察の詰めが甘かった。 まず、（A）答えが負となる場合と（B）答えが非負となる場合で場合分けをする。 （A）の場合には、絶対値の小さい順に貪欲にとればよい。（B）の場合を考えていく。まず、キューを2つ用意しておく。 非負な値を降順にソートしたもの（例：9 6 5 2 1 0 0） 負な値を昇順にソートしたもの（例：-8 -7 -3 2） 単純に、負数同士の積は正という性質を使う。 $K$が2個以上残っている場合には、2つのキューからそれぞれ2つの値を取り出して、大小比較をする。 例えば、$9 \cdot 6 = 54 < -8 \cdot -7 = 56$ であれば、負数のキューから2つ値を取り出せばよい。 一方で、非負なキューのほうが大きい場合には、非負のキューから1つ値を取り出せばよい。 繰り返しになるが、非負なキューから取り出す場合には、1つの値だけでよいことに注意する。 https://twitter.com/shirakia/status/1279773457413074944で例が言及されている。after_contest01.txtもこのケースに該当しそう。 そのあとは、非負なキューからとる場合は1つずつ、負なキューからとる場合は2つずつのペアとして、取り出していけばよい。 （B）の計算途中で、どうしても答えを正数にすることができない場合には、（A）の結果を答えとする。

提出したコード 前提知識として、Nimというゲームであることを知っておくと良い。Nimには必勝法があり、すべての山の石の数 $A_i$ についてXORをとり、その結果が0以外であれば、その手番の人が最適な動きを取れば必ず勝つ。 必勝状態であるXOR != 0で手番が回ってきたとき、ある山からある数の石をうまく取り除くと、XOR = 0の状態に遷移できる。 逆に、XOR = 0の状態からは、どんな選び方をしても、必ずXOR != 0 の状態（必勝状態）に遷移してしまう。 ターンの経過に伴って石の数の合計は減っていくので、必ずゲームは終わる。 Grundy数というらしい。 これをふまえて、考察を進める。「1番目の山から0個以上$A_1$個未満の石を2番目の山に移すことで …」とあるので、先頭二つの山についてのみ考えればよいことがわかる。なので、これ以降$A=A_1$、$B=A_2$、$X = A_3 \oplus A_4 \oplus \cdots \oplus A_N$とする。また、“移す"という操作を$A$を$a$、$B$を$b$に変更すると言い換える。そうすると、以下の条件を満たしつつ、できるだけ$a$を大きくすればよい（“移す"石の数が最小）ということになる。 $$ a + b = A + B = S \ a \oplus b = X \ 1 \leq a \leq A \ $$ これは桁DPによって解くことができる。$dp_{i,j,k}$を、下から$i$桁目まで見たときの$a$の最大値とする。 ただし、一つ上の桁に対して繰り上がりがある場合は$j=1$、$i$桁目まで見たときに$a$が$A$を上回っていれば$k=1$とする。 50桁くらいまで見れば十分。 提出コードにコメントをつけておく。初期値は以下の通り。 rep(a, 2) { ull b = a ^ (X & 1); // b は a から決まる ull carry = a & b; ull _sum = a ^ b; if (_sum !...

KVM FORUM 2018 で発表されたTowards a more Scalable KVM Hypervisorについてのメモ。 [PATCH v8 0/4] KVM: X86: Add Paravirt TLB Shootdown ゲストOSはOSレベルの同期機構であるTLB shoot downやRCUの処理において、ホストOSのスケジューラの影響を受ける。ベアメタル環境であればすぐに完了する操作であっても、仮想環境上ではその遅延を無視することができなくなる。 TLB（Translatoin Lookaside buffer）は仮想メモリアドレスと物理メモリアドレスのマッピングをキャッシュするために使われる。あるCPUがそのマッピングを切り替えたとき、その以外のCPUでTLBをflushしなかればならない。これを TLB shoot down と呼ぶ。 モダンなOSでは、TLB shoot down はパフォーマンスクリティカルな箇所として位置づけされ、この処理によって遅延が発生しないようチューニングされている。TLBのflushはすぐさま完了するという前提で、IPI（Inter Processor Interrupt）で実装されている。Remote CPUのTLB flushの完了は busy wait で待っているため、ベアメタル環境とは相性が良い。一方で、仮想環境ではvCPUが別のゲストに横取りされたり、実行がブロックされたり、ということが起きるため、長時間にわたって busy wait が継続することになる。 この問題は、準仮想化TLB shoot down によって解決できる。準仮想化TLB shoot down では、動作していないvCPUに対する操作を遅延させておいて、次回そのvCPUが起動するときに、KVMがTLB flushを担当する。特にオーバコミットされた環境で顕著なパフォーマンス向上が見られる。 ゲストとホストどちらからも参照できるメモリ領域に「あるvCPUが preempt されたかどうか」を示すフラグを用意しておく。pv_mmu_ops.flush_tlb_others関数は、アクティブなvCPUに対してはIPI経由でTLB Flushの通知を送り、そうでないvCPUに対してはKVM_VCPU_FLUSH_TLBフラグを付与しておく。その後、KVMはKVM_VCPU_FLUSH_TLBフラグがついているvCPUを起動する際に、INVVPIDを発行する。VM数が増えるに従ってこのチューニングの効果が顕著に現れる。

一度Civilization VIを友人とやった結果、どうやらこのままだと勝てそうにもないので、ちょっと調べてみる。 このゲームは選択の連続なので、仕組みを知らずになあなあで進めてしまうと勝つのは難しそう。 あくまでも初心者が自分のために書いていくメモなのであしからず。 詳しく知りたい方は CIVILIZATION VI wiki を見てください。 まず、マップオプションから、グリッド、資源アイコン、算出アイコンを表示するよう設定しておく。 都市そのものを強化するリソースが、食料と生産力。食料を増やすことで人口が増え、生産力を増やすことで区域・建造物の生産につながる。生産力は、労働者が鉱山を作ることで得られる。ゴールド・科学力・文化力は、市場（商業ハブ区画）、図書館（キャンパス区画）、円形闘技場（劇場広場区画）から得られる。 序盤の戦闘に有利なアステカ、アメリカ、シュメール、ヌビア、ローマ、クリー、インカが、初心者に向いている。 初期配置に癖のあるヌビア、エジプト、マリ、ロシア、カナダ、イギリス、インドネシア、スペイン、ノルウェー、オランダ、フェニキア、マオリなどは難しい。また、宗教メインな文明や、特殊なプレイングが必要な文明も向いてない。 ドイツが扱いやすいそうに感じる。固有区域ハンザが単純に強い。区域はハンザ＞キャンパス＞商業ハブくらいで立てていく。 序盤は、斥候、労働者、戦士、開拓者で進めていく。 都市が川や湖に隣接していると住宅+3なのでよく吟味する。ユニットの中ではチャリオット（のちの戦車）、弓兵（のちの野戦砲）が強い。 丘陵地帯は生産力が強力なので、そこを狙って都市を作る。 都市を作った後は、市民管理で手動で人をどのタイルに配置するか決めることができるので、定期的に見直すと良い。 労働者はむやみに使わず、必要な時まで眠らせておけばよい。 市民+2の住宅が必要で、それを下回るとペナルティが発生して、都市の成長が妨げられる。 交易商は強力なので、作れるタイミングなら優先して作る。 太古の遺産はピラミッド、アポロン神殿が強い。 それ以降の時代では、ペトラ、コロッセオ、アルハンブラ宮殿、チチェン・イツァ、 グレート・ジンバブエ遺跡、紫禁城、ポタラ宮、アルセナーレ・ディ・ヴェネツィア、ビッグベンが強い。 戦争中は勝つまで兵の増強をやめない。相手も兵の生産に集中しているはずなので。 遠距離攻撃する場合は、移動力が1以上残っていれば攻撃可能なので、ヒットアウェイで戦う。 その他 最初期の探索は重要 都市で役割分担 都市数ペナルティがないので、単純に大量に都市を作ると強い 都市の人口は住宅数に制限されるため、食料よりも1人口あたりの生産力重視 3つの山岳があれば、キャンパス区画を作る 丘陵と鉱山で早期生産 遺産は奪う 高級資源は売りつける

提出したコード 解説を漁ってみると、どうやらアルファベットを適当に$K$回挿入したあとの 長さ$N+K$の文字列の中で、$S$の各文字の位置が固定されていると考えればうまくいくということだった。 そう考えると、あとは長さ$N+K$の文字列で$K$文字をどうやって挿入していくかだけを考えれば良い。 入力例1を使って考える。 S = “oof” N = len(“oof”) = 3 K = 5 例えば、位置1に’o’、位置3に’o’、位置5に’f’をおいてみる。 また、長さ$N+K$の文字列を先頭から見たときに"oof"がはじめて登場するのがこれらの位置ということにする（条件1）。 このとき、位置0には’o’以外の25種のアルファベットを挿入できる。 逆に、位置0に’o’を挿入するのは、条件1を満たさないのでダメ。 同様にして、位置2にも’o’以外の25種のアルファベットを挿入できる。 また、位置4にも’f’以外の25種のアルファベットを挿入できる。 位置6と7に関しては、特に制約がないので、26種のアルファベットを挿入できる。 まとめると、‘f’の位置$j$が$N-1 … N+K-1$まで移動したとき、 2つの’o’が取れる位置の組み合わせは${}_j C _{N-1}$ となる。 また、25種のアルファベットを挿入する位置は$j - (N-1) $個、 26種のアルファベットを挿入する位置は$(N+K-1)$個、となる。 つまり答えは$\sum_{j=N-1}^{N+K-1} {}_j C _{N-1} \cdot 25^{j-(N-1)} \cdot 26^{(N+K-1)-j}$となる。

提出したコード 解いた後の振り返りが大事だと思う。 2次元平面上で、スタート位置からゴール位置までの最短経路を求める。 ただし、平面上にはいくつかブロックがあり、そのセルは通れない。 さらに、一回の移動で、同一方向に$1 … K$の任意の個数のセルを進めることができる。 頂点は$(y, x, dir)$として、グラフを考えて、ダイクストラ法で最短経路を算出すればよい。 頂点$(y, x, dir)$からの遷移は以下の通り。 移動にかかるコストを$K$倍して考えるとよい。 方向を変えるときは、$K$で切り上げ。 $cost(y, x, new dir) \leftarrow ((cost(y, x, dir) + K -1) / K) * K$ 同方向に移動。$dir$は上下左右の4種類。$dx$、$dy$は方向ごとの差分。 $cost(y + dy, x + dx, dir) \leftarrow cost(y, x, dir) + 1$ 計算量は$O(HW log(HW))$かな。

EDPC を全部埋めた。 雑多なメモなので、きれいに解法をまとめたものではない。 W - intervals $dp_i$ を、いくつかのビットに1が立っているとき、最も右側にある1が$i$であるときの最終スコアとする。 ここで、$dp_i$は$ max_{j=0 … i-1} dp_j$ と $i$ 文字目を1にしたときに得られるスコアの和で求められる。 $block_i$を右端$r$が$i$であるブロックの集合として、 $dp_i$を計算する際に、 $i$文字目を1にしたときに得られるスコアとして $block_i$ を足しこむ。 $block_i$ は $i$ 未満の $dp$ にも影響するため、遅延セグメントツリーを使って、 影響する $dp$ に区間加算を行う。 最終的な答えは $max_{i=0 … N} dp_i$ となる。 はじめて、遅延セグメントツリーを使った。復習しておく。 Z - Frog 3 $dp_i$ を足場 $i$ に到達するまでの最小コストする。 初期値は $dp_0 = 0$。 まずは素直にDPの更新式を作ると以下のようになる。 $$ \begin{aligned} dp_i &= min_{j=0 … i-1} (dp_j + (h_j - h_i)^2 + C) \\ &= min_{j=0 … i-1} (dp_j + h_j^2 - 2 h_i h_j + h_i^2 + C) \\ &= min_{j=0 … i-1} (-2 h_i h_j + dp_j + h_j^2) + h_i^2 + C \\ \end{aligned} $$...

Linux Observability with BPFを読んだので、メモしておく。 今月、Brendan Gregg氏のBPF本も出るので、 それも読みたいな。 BPFを使うことで、カーネルのイベントをフックして安全にコードを実行できる そのコードがシステムを破壊したりクラッシュさせたりすることが無いよう、BPF側で検証してくれる カーネルモジュールと異なり、BPFプログラムはカーネル再コンパイルの必要がない BPFコードが検証された後、BPFバイトコードは機械命令にJITされる BPFプログラムは、bpf syscall によってBPF VMへとロードされる 2014年前半にAlexei Starovoitov氏がeBPFを導入した 過去のBPFでは2つの32bit registerのみが使えたが、eBPFでは10個の64bit registerまで使える 2014年6月にはeBPFはユーザスペースにも拡張された BPFプログラムタイプ：トレーシングとネットワーキングに大きく分類できる Socket Filter：カーネルに最初に入ったプログラムタイプ。観測目的のみ Kprobe：kprobe ハンドラとしてBPFプログラムを動かす。関数に入るときと出る時が、それぞれSEC(kprobe/sys_exec)とSEC(kretprobe/sys_exec)に対応する Tracepoint：事前にカーネル側で定義されたtracepointに対してBPFプログラムを動かす。/sys/kernel/debug/tracing/eventsで一覧を確認できる XDP：パケット着信時に、早い段階でBPFプログラムを動かす。 Perf：perf eventに対してBPFプログラムを動かす。perfがデータを吐き出す度にBPFプログラムが実行される Cgroup Socket：そのcgroup内のすべてのプロセスにアタッチされる Socket Option：Facebookはデータセンター内の接続において、RTOs（recovery time objectives）の制御に、これを使っている。 Socket Map：BPFでロードバランサを実装するときに使う。CilliumやFacebook Katranはこれを使っている。 BFP Vefirier CVE-2017-16995 のように、過去BFPをバイパスしてカーネルメモリをバイパスできる脆弱性があった DFSで、そのプログラムが終了すること、危険なコードパスが存在しないことを検証する 無限ループを弾くために、すべてのループを禁止している。ループ許可については、本書を書いている時点では、まだ提案の段階。 命令数は4096に制限されている bpf syscall の log_*を設定すれば、検証結果を確認できる BPFプログラムは tail calls によって、他のBPFプログラムを呼び出すことができる 呼び出し時にすべてのコンテキストは失われるので、何らかの方法で情報を共有する必要がある BPFマップ 直接bpf syscall でBPFマップを作成することができる bpf_map_createヘルパ関数を使うのが簡単 bpf_map_update_elem のシグネチャは、カーネル側bpf/bpf_helpers.hとユーザ側tools/lib/bpf/bpf.hで異なるので注意する エラー番号でsteerror(errno)で文字列にすると便利 bpf_map_get_next_keyはそのほかのヘルパ関数と違って、ユーザ側でのみ使えるので注意する array, hash, cgroup storage maps については、スピンロックがあるので、並行アクセス可能 array map は要素数だけ事前にメモリが確保されて、ゼロで初期化される。グローバルな変数確保のために使う？ LRUハッシュやLRM（Longest Prefix Match）Trie mapもある Linux 4....

Kubernetes完全ガイド を読んだので、メモを残しておく。 普段、意識していなかったコマンドや仕組みをまとめておく。 サイズの小さなイメージを作りたければ scratch や apline をベースにする ENTRYPOINT と CMD が設定されているときは、$ENTRYPOINT $CMD が実行されるようなイメージ マルチステージビルド：ビルド専用のコンテナでだけ処理を行い、成果物を実行専用コンテナにコピーすることが出来る CNCF ではプロジェクトの成熟度を「Graduated」「Incubating」「Sandbox」の3段階に設定している オンプレで構築する場合はAWS や GCP でのインスタンスサイズが目安になる Flannel：ノード間でオーバーレイネットワークを構成する Docker, Inc. が提供するkubernetes のプレイグラウンドがある kubernetes のリソースは大きくわけて5種類 Workloads, Discoverty &LB, Config & Storage, Cluser, Metadata 特に Metadata はクラスタ内で他のリソースを操作するためのリソース（HorizontalPodAutoscaler など） Deployment/CronJob > ReplicationController/ReplicaSet/DaemonSet/StatefulSet/Job > Pod という階層構造がある kubectl get all：ほぼすべてのリソースを一覧取得 Stateful Set：0番目の Pod が最初に作られ、最後に削除される kubeconfig clusters、users、contexts の3種類を設定（どれも複数登録可能） context や namespace の切り替えが冗長であれば、kubectx や kubens を使うと良いかも kube-ps1 を使うと cluster と namespace をプロンプトに出力できる source <(kubectl completion bash)などで zsh/bash の補完機能を使える コンウェイの法則：組織図と、マニフェストの管理方法やマイクロサービスのアーキテクチャが似ている kubectl scale：ReplicaSet, ReplicationController, Deployment, StatefulSet, Job, CronJob でスケーリング kubectl apply --prune：実行時にマニフェストから削除されたリソースを検知して、自動で削除 CI/CDでは、単純にこのコマンドを投げ続けるだけでよい kubectl apply --prune --all：クラスタ内に存在するすべてのマニフェストを読み込ませないと、漏れがあったリソースが消えてしまい危険 kubectl apply --prune -l system=a：基本的にラベルを指定しておく デバッグ kubectl cp：コンテナとローカルマシンの間でファイル転送 kubectl port-forward：コンテナとローカルマシンの間でポート転送 kubectl -v：デバッグ出力 サービスディスカバリ spec....

USB接続の無線LAN子機 TP-Link Archer T3U AC1300 を、Thinkpad X1 Carbon 2015（Fedora release 29 (Twenty Nine)、linux 5.3.6-100.fc29.x86_64）から使えるようにしたので手順を残しておく。 # 公式HPではドライバが配布されていなかったので rtl88x2bu を使った git clone https://github.com/cilynx/rtl88x2bu cd rtl88x2bu/ git rev-parse HEAD # 962cd6b1660d3dae996f0bde545f641372c28e12 VER=$(sed -n 's/\PACKAGE_VERSION="\(.*\)"/\1/p' dkms.conf) sudo rsync -rvhP ./ /usr/src/rtl88x2bu-${VER} # /usr/src/<module_name>_<module_version> に移動させて dkms で管理する sudo dkms add -m rtl88x2bu -v ${VER} sudo dkms build -m rtl88x2bu -v ${VER} sudo dkms install -m rtl88x2bu -v ${VER} sudo dkms status sudo modprobe 88x2bu 2種類の子機（オンボードの子機とTP-Linkの子機）を同一のネットワークにつなぐと、metric によって優先順位が決まる。 metric の値を見ると、オンボードの子機側を優先していた（値が小さい）ので入れ替えた。...

越後湯沢で開催された秋桜ハーフマラソンに参加してきた。 大会自体はすごいよかったけど、コースの半分あたりから胃の調子が悪くなり、 13kmでリタイヤという悔しい結果となった。 色々反省点があったので、記録として残しておく。 まず、そもそも食事のタイミングが悪かった。9時30分スタートで、8時あたりでおにぎりを食べた。 3時間前までに取るようにしたい。直前に口にいれるのであれば、ゼリー状のものにしたい。 6.7kmから15kmまで続く下り坂で飛ばしすぎた事も影響していると思う。 お腹が激しく上下して気持ち悪くなってしまった。 スタートから6.7kmまでの上り坂は走り方に気をつけていたが、それ以降については、なんとかなるだろうと考えていなかった。 加えて、腰にポーチを巻いていたので、お腹を圧迫していたのかもしれない。 塩飴を少量持っていただけなので、ポケットにいれておけば事足りていた。 前半の上下の坂でも貯金を作っておこうと、いつも以上に早めのペースで走っていたので、 バテてしまったんだろうな。 ただ、自分でリタイヤを決断できたのは唯一よかったことだった。 以前膝を故障してしまったときは、脚を引きずりながらも、無理して走っていて、 沿道で応援してくれた方からリタイヤを勧められた。 どうも消化不良な感じなので、どこかでリベンジしたい。

TCP技術入門を読んだので、 気になったところを雑多な感じだがメモしておく。まず前半部分。 ネットワークまわりの話は聞いたことはあるが、使わずに忘れてしまっていることが多い。 1章 TCP入門 伝送効率 Ethernetフレーム 1500 バイト、TCPヘッダが 60 バイト、IPヘッダが20バイトとする アプリケーションが使えるのは 1420 バイト Ethernetヘッダ 14 バイト、FCS（Frame Check Sequence）4バイトを考慮すると、伝送効率は$1420/(1500+18) \times 100=93.5 %$ UDP 実際にUDPがやっていることは、転送先へデータを送ることと、チェックサムの確認だけ TCPはユニキャストだが、UDPはユニキャストに加えて、マルチキャストとブロードキャストにも対応 シーケンス番号とタイムスタンプを追加したRTP（Real-time Transport Protocol）や、それに加えて再送機能も追加したRUDP（Reliable user Datagram Protocol）もある QUIC はUDPベースで、それを使ったHTTP/3（HTTP-over-QUIC）。コネクション確立とTLS確立を同時に実施。 TCP ACKのシーケンス番号は、次に受信したい番号。当該セグメントが届くまで、同じシーケンス番号を返送し続ける。 フロー制御：受信側のバッファ溢れを防ぐために、送信データ量を調整すること。TCPでは一度に送信可能なサイズをウィンドウと呼ぶ。特に、送信側がもつパラメータを swnd （send window）と表記する。対して、受信側はrwnd（recieve wndoe）。 TCP輻輳制御 Loss-based：データの消失から輻輳を判断 Delay-based：RTTから輻輳を判断 特定の用途向けプロトコル RUDP（Reliable User Datagram Protocol）：UDPベースで、シーケンス番号、ACK、再送、フロー制御を加えたもの DCCP（Datagram Congestion Control Protocol）：UDPにおける輻輳緩和が目的 2章 TCP/IPの変遷 ARPNETなどではネットワークが信頼性を担保していたが、TCP/IPは各ノードがその役割を担う Nagleアルゴリズム：TCP/IPの送出パケット数削減の方法。輻輳制御アルゴリズムのはしり Windows95（OSR2以降）にTCP/IPが搭載されたことが普及のきっかけになった IEEE 802.11ではMACレイヤーでCSMA/CAを採用 3章 TCPとデータ転送 MTUは、イーサネットは1500バイト、PPPoEでは1492バイト、ATMは9180バイト。ただ最近は任意に設定できる MSS（Maximum Segment Size）：TCPが区切る最大パケット長さ MTU（1500バイト）= IPヘッダ（20バイト）+ TCPヘッダ（20~60バイト）+ アプリケーションデータ（MSS以下） MSSは、TCPのペイロードのみ MTUは、TCPのペイロードからTCPヘッダやIPヘッダまで。Ethernetヘッダは含まない ACK（Acknoledgement Number）：確認応答番号。次に送ってほしいシーケンス番号 コントロールフラグ RST（Reset the connection）：コネクションを強制切断。使われていないポート番号に送るなど、異常があれば有効になる CWR（Congestion Window Reduced）：輻輳ウィンドウの減少を通知する。ECNとセットで使われる ECE（ECN echo）：輻輳が発生したら通知 ウィンドウ制御：一度に送信可能なウィンドウサイズ $swnd$ を調整 $swnd = min(rwnd, cwnd)$ フロー制御：受信側から送信側に送信量を通知して、調整する。受信側は、送信側へ受信可能なバッファ量$rnwd$を通知 輻輳制御：輻輳ウィンドウ $cwnd$ を調整 スロースタート 通信開始時点で、ACKを受け取るたびに $cwnd$ を1セグメントずつ増やしていく $cwnd = cwnd + mss$ 指数的に $cwnd$ が拡大 輻輳回避 スロースタートを行うと、再び再送が起きやすい 再送が起きた時の $cwnd$ の半分 $cwnd/2$を閾値として、それを越えた時は更新を緩やかにする $cwnd = cwnd + mss/cwnd$ RTTごとに線形に増える 高速リカバリー 輻輳のたびに、スロースタート→輻輳回避という挙動をするのは効率が悪い 重複ACKを契機とする Recoで採用 セグメントの消失 再送タイマーがタイムアウトした場合 重複ACKが一定数届いた場合

ABC #139 D - ModSum $p_1=N, p_2=1, p_3=2, … , p_N=N-1$ とすると、$m_1=0, m_2=1, m_3=2, … , m_N=N-1$ となる。 なので、答えは$1, 2, 3, …, N-1$の総和。 ABC #139 E - League $i$と$j$の試合を頂点$(i,j)$と表す。ただし、$i$と$j$をひっくり返したものは同一視する。 各頂点は、直前にすべき試合数$prev_{(i,j)}$と、その次に実行可能な試合の一覧$next_{(i,j)}$をもつ。 そして、$prev_{(i,j)} = 0$である試合を見つけるたびに、貪欲にその試合をしていくよう、シミュレーションする。 ここで、ある試合をするたびに、その次の頂点の$prev_{(p,q)}$をデクリメントすることに注意する。 ABC #139 F - Engines あらかじめ各ベクトルを偏角ソートしておき、 720度分になるようにそのベクトルをつなげておく（後々、楽になる）。 そうすると、この問題の答えは、連続したベクトルの和であることが分かる。 すべてのベクトルについて、以下の操作を行う。 あるベクトルを始まりとして、連続したベクトルを足していき、長さが最長となるものを見つける。 ABC #140 D - Fce Produces Unhappiness まず、幸福でない人に注目して、それをどれだけ減らせるかに注目する。 たとえば、$RLLLLRRRRRLLRRLLRRR$から幸福でない人を抜きだすと、$RL…….RL..RL…R$となる。 連続する人は同時に操作できるので、$RLRLRLR$と考えてよい。 そして、$RLRLRLR$ -> $RLRLR$ -> $RLR$ -> $RR$ -> （空）のように操作を繰り返せば良い。 ABC #140 E - Second Sum Nから1まで、順番に見ていく。 ある要素$i$について見た時、左右には$i+1, i+2, … , N$の要素が置かれていることになる。 右側に最大値がある場合と、左側に最大値がある場合、それぞれについて、組み合わせを計算して、 合算すればよい。最大値の位置については、setのlower_boundで見つけた。...

いくつかABCの問題を解いたけど、ブログに記録するのを忘れていた。 まとめて書いておく。 ABC #136 D - Gathering Children 一度RLの組に入ると抜け出せない。 偶数距離を移動させて、RLの組にくっ付ける。 ABC #136 E - Max GCD ソートしておいて、小さい値は0に、大きい値は答え$d$に近づける。 前と後の両方向から、累積和を求めておく。 ABC #136 F - Enclosed Points ある点$x$がふくまれるような矩形の数は、その上下左右の4つの領域からそれぞれいくつの点を選ぶかによって計算できる。領域ごとに含まれる点の数を$A, B, C, D$とする。 点$x$を含まない場合は、それぞれの領域から点を取るかどうかで16個に場合分けして考える 点$x$を含む場合は単純に$ABCD$ 領域ごとの点数の算出には、平面走査を使う。また、事前に座標は圧縮しておく必要がある。 ABC #137 D - Summer Vacation アルバイトはどれも一日で終るためコストは変わらず、単純に支払日だけが異なるだけ。 アルバイトを報酬の大きい順に見ていって、できるだけ後ろの日程から埋めていく。 ABC #137 E - Coins Respawn まず、DFSを使って、始点と終点どちらからも到達可能な頂点の集合$S$を求める。 あとはコストに$-1$を掛けて、ベルマンフォード法を適用して、最長経路を求める。 もし、集合$S$内の頂点が、閉路に含まれていたら、$-1$を返す。 単純に、ベルマンフォード法で閉路を見つけるだけでは不十分なことに注意する。 ABC #137 F - Polynomial Construction フェルマーの小定理を使う。頻出テクニックだと思うので、復習しておきたい。 $a = {0,0,…,0}$の$i$番目を1にした$a’ = {0,0,..,1,…,0}$を考える。 そうすると、$a$を使った$f$と、$a’$を使った$f’$は以下のような関係になる。 これをすべての1が立っている$i$について、計算すればよい。 $$ f’(x) = f(x) + (1- (x-i)^{P-1}) $$...