Linuxのメモリ管理
コンピューター上では全ての処理がメモリにロードして実行される。
メモリ管理の仕組みについて書いてみる。
物理メモリと仮想メモリ
プログラムが実行されてプロセスが生成されると、カーネルは生成されたプロセスにメモリを割り当てる。カーネルによってプロセスごとに使用できるメモリ領域が割り当てられるが、プロセスは物理メモリに直接アクセスしているわけではなく、仮想メモリを通してアクセスしている。
cat /proc/${PID}/mapsで、指定したプロセスに割り当てられているメモリの仮想アドレスを確認できる。
カーネルから割り当てられた仮想メモリアドレスから物理メモリアドレスにアクセスする際は、ページテーブルという仮想メモリと物理メモリの対応表が使われている。ページテーブルはカーネルのメモリ領域にある。
仮想アドレス外のアドレスにアクセスすると「ページフォルトハンドラ」という処理が動き、カーネルはプロセスによるメモリアクセスが不正であることを検出して、「SIGSEGV」というシグナルを用いてプロセスに通知し、プロセスは強制終了される。
デマンドページング
プロセス生成時に、カーネルがプロセスに必要なメモリを物理メモリ上に確保して、ページテーブルに仮想アドレスと物理アドレスを紐付ける単純なメモリ割り当ての方法は、プロセスが割り当てられたメモリ全てを使わない可能性があり、メモリに無駄が生じる可能性がある。
そのため、プロセス生成時に仮想アドレスだけプロセスに割り当てて、物理アドレスは実際に仮想アドレスにアクセスされたタイミングで割り当てるデマンドページングというメモリ割り当て方法がある。
スワップ
メモリ使用量が増え続けると、メモリ管理システムは適当なプロセスを選んで強制終了することでメモリ領域を解放する。これをOOM（Out Of Memory） killerという。
このOOMに対する仕組みとして、ストレージデバイスの一部を一時的にメモリの代わりとして使うスワップという仕組みがある。
物理メモリが枯渇した際に使用中の物理メモリの一部をストレージデバイスに退避することによって空きメモリを作り出す。このメモリを退避する領域をスワップ領域、カーネルが使用中の物理メモリの一部をスワップ領域に退避させることをスワップアウトという。
物理メモリに空きが出てきたタイミングでスワップアウトしていたデータを物理メモリに戻す。これをスワップインという。
スワップは一見すると、メモリ量が物理メモリ＋スワップ領域になるため良いように思えるが、ストレージデバイスへのアクセス速度はメモリへのアクセス速度に比べてかなり遅いので避けた方が良い。
メモリが常に足りない場合はメモリアクセスのたびにスワップインとスワップアウトが繰り返されるスラッシングという状態になる。
スワップ領域の使用量は以下のコマンドで確認できる。
$ swapon --show NAME TYPE SIZE USED PRIO /swap.img file 2G 358.3M -2
仮想メモリ空間の詳細
仮想メモリ空間は大きく分けて4つのメモリ領域に分けて考えることができる。
アドレスが小さい領域にはプログラム自体とグローバル変数のような静的変数が置かれる。静的変数とは、プログラム中で使用する変数のうち、プログラムの開始から終了まで値が保持され続けるもの。
その先はカーネルから動的にもらうヒープと呼ばれるメモリ領域があり、アドレスが大きい領域にはスタックと呼ばれるメモリ領域がある。ヒープとスタックはお互いに向かってメモリを伸ばしていく。
コンパイル時点でサイズが決まるようなローカル変数などがスタック領域に確保される。しかしスタック領域だけでは動的に使用するメモリのサイズが変わる場合に最大サイズを確保しておかねばならずメモリの無駄が生じる。そこで、ヒープ領域がある。
ヒープ領域はアプリケーションが動的に確保する領域。C言語でmallocで確保する領域。コンパイル時点ではサイズが決まっていない場合によく使われる。ヒープ領域に積まれた変数はOSが自動的に判断し必要なときに確保して不要になったら解放してくれることがある（ガベージコレクション）
C言語ではローカル変数を定義するとスタックにメモリが確保され、mallocを使うとヒープにメモリが確保されるシンプルな仕組みなっている。
一方で、Goの場合はヒープに置くかスタックに置くかはコンパイラが判断する。ローカル変数として宣言しても、他の関数に渡したり、関数の返り値として返すような場合はヒープに置かれることが多い。
スタックとヒープどちらに確保されているのかを知りたい場合は、ビルド時に-gcflags -mを渡す。
package main
import "fmt"
func main() {
hogeStr := "hoge"
fmt.Println(hogeStr)
fugaStr := "fuga"
_ = hogeStr + fugaStr
}
❯ go build --gcflags -m tmp/main.go
# command-line-arguments
tmp/main.go:7:13: inlining call to fmt.Println
tmp/main.go:7:13: hogeStr escapes to heap
tmp/main.go:7:13: []interface {}{...} does not escape
tmp/main.go:10:14: hogeStr + fugaStr does not escape
<autogenerated>:1: .this does not escape
このようにhogeStrはヒープに確保され、hogeStr + fugaStrはスタックに確保されていることが分かる。
基本的にスタックの方が高速なので本来はスタックに確保しようとするが、変数の寿命が長くなる可能性がある場合はヒープに確保されることが多い。
プログラムの実行手順とLinux関連の用語について
Linux周りの概要について調べたことをだらだらと書いてみる。
コンピューターシステムの概要
まずコンピューターがプログラムを実行する流れ。
まず、プログラムを実行する。
プログラムのデータが格納されている補助記憶装置（ストレージデバイス）から主記憶装置（メインメモリ）にプログラムをロードして、CPUがメインメモリに格納されたプログラムの指示に従って動作する。
演算結果はメモリに戻され、必要に応じてストレージに戻される。
OS
OSがする仕事は大きく分けて2つある。
1つは、CPUやメモリ、ストレージなどの各種資源の管理。
もう1つは、外部入出力機能の管理である。外部入出力には単にファイルの読み書きやストレージの読み書きだけでなく、ネットワークやプロセス間通信も含まれる。
カーネル
CPUのカーネルモードで動作するOSの中核的な処理をまとめたプログラム。
プロセスはカーネルが提供する機能を使う場合は、システムコールを呼んでカーネルに処理を依頼する。
CPU
メモリにロードしたプログラムの命令に従って処理を進める装置。
カーネルの操作をするカーネルモードとユーザーモードの2つのモードがある。
メモリ
一時的に作業データを保存する記憶領域のこと。
システムコール
システムコールとは特権モードでOSの機能を呼ぶこと。プロセスからカーネルに送られる。 もしシステムコールがなければ、OSの機能を使えないので何もできない。
シグナル
カーネルからプロセスに対してイベントの発生を伝えるもの。
用途としては大きく分けて2つある。
1つは、プロセス間で通信する際に、カーネルがプロセスにシグナルを送信することで通信する。
もう1つは、システムで発生したイベントをシグナルとしてプロセスに送る。例えばControl+Cでデバイスからプロセスを止めるときなど。メモリ範囲外アクセスのエラーでCPUでエラーが発生→カーネルがシグナルを生成し、プロセスを止めるというのも一例。
CPUの動作と高速化
一般にコンピューターの各動作の所要時間の関係は、CPUの計算処理の所要時間 < メモリアクセスのレイテンシ < ストレージデバイスへのアクセスのレイテンシである。
キャッシュメモリ
レジスタ上での計算とメモリアクセスの所要時間の差を埋めるためにキャッシュメモリが利用される。
メモリからレジスタにデータを読み出す際はキャッシュメモリにデータを読み出した上で、同じデータをレジスタに読み出す。
ページキャッシュ
CPUからのメモリアクセスとCPUからストレージへのアクセスの所要時間の差を埋めるためにカーネルのページキャッシュが利用される。
ページキャッシュはストレージデバイス上のデータをメモリにキャッシュする。
カーネルはストレージデバイス上にあるファイルデータをプロセスに割り当てたメモリに直接コピーするのではなく、カーネルのメモリ上にあるページキャッシュという領域にコピーしてから、プロセスのメモリへコピーする。
ファイルシステム
Linuxではデバイスも含めほぼ全ての対象をファイルとして表現して操作する。
ファイルにはデータを保持する通常のファイルと、ファイルを保持するディレクトリ、デバイスをファイルとして表現したデバイスファイルの大きく分けて3種類がある。
各デバイスファイルは/dev配下に存在する。
ジャーナリング
データの不整合を防ぐ仕組みの1つ。
処理の一覧をファイルシステム内のジャーナル領域に書き出す。ジャーナル領域の内容に基づいてファイルシステムの内容を更新することで、途中で電源が落ちるなど処理が中断されても、再起動後にジャーナルログを最初から再生することでファイルシステムは整合性を保った状態になる。
procfs
システムに存在するプロセスについての情報を管理するファイルシステムで/procにマウントされる。
psコマンドやtopコマンドなどはprocfsの情報を可視化している。
/proc/${PID}/mapsはプロセスのメモリマップ（仮想メモリ）/proc/${PID}/statは指定したプロセスがこれまでに使用したCPU時間やメモリ量などを管理
その他のLinuxのしくみ
Unixドメインソケット
ソケットとは、アプリケーション層からトランスポート層を使うときのインターフェースで、プロセス間通信の1種。
UnixドメインソケットはPOSIX（UNIX系のOSに共通する機能についての規約）系OSで提供されている。Windowsにはないので注意。
Unixドメインソケットを使うことで、高速な通信が可能になる。TCPやUDPなどのソケット通信は外部のネットワークに繋がるインターフェースに接続するが、Unixドメインソケットはカーネル内部でしか使えない。ソケットファイル（.sock）によって通信する。
サーバーとNiginxなどのリバースプロキシ間の通信の高速化などに利用される。
パイプ
パイプはプロセス間の入出力を繋げる仕組み。
無名パイプ
無名パイプは、コマンド間の入出力を繋げる際に使う。
ps aux | grep go
パイプの前のコマンドの標準出力を後ろのコマンドの標準入力にする。前から後ろに一方行にデータが流れる。
名前付きパイプ
ファイルのように名前でアクセスできるFIFOの性質を持った双方向パイプ。
データを移動したい時などに利用することが多い。 一旦ファイルにデータを書き出す場合と比べて消費するストレージが小さくて済むなどのメリットがある。
スループットとレイテンシ
スループットは、単位時間あたりの仕事量で、高いほど良い。CPUのリソースを使っているほど高くなる（アイドル状態のCPUが少ないほど高くなる）
レイテンシは、処理の開始から終了までの経過時間で、短いほど良い。
スループットが高い状態だとレイテンシは長くなり、スループットが低い状態だとレイテンシは短くなるので、トレードオフの関係にある。
Goで深さ優先探索と幅優先探索
深さ優先探索と幅優先探索の概要
例えばニュースアプリでニュース一覧からとあるニュースを探しているとして、探し方は大きく分けて2つある。
（カテゴリタブとかはなくてニュースが羅列していて、そのニュースそれぞれが関連ニュースを複数保持している状態をイメージしてもらえれば良い）
深さ優先探索の概要
1つ目は、一覧にあるニュース記事から1つを選んで見て、その記事が探索している記事でなければそのニュース記事内の関連ニュース記事を1つ選んで見る。
その関連ニュース記事が探索している記事でなければ、さらにそのニュース記事内の関連ニュース記事を1つ選んで見る。
これを繰り返して、関連ニュース記事がなくなれば1つ前に探索した関連ニュース記事の中でまだ探索していない関連ニュース記事を探索する。
これを繰り返すと、一覧にあるニュース記事の全てを探索することができる。
このように深さ優先探索では、同列にある探索対象よりも探索の深さを優先して探索し、最深部まで探索してから1つ上の階層の同列にある探索対象を探索していく。
幅優先探索の概要
2つ目は、一覧にあるニュース記事から1つを選んで見て、その記事が探索している記事でなければ同列にあるニュース記事一覧からまだ探索していないニュース記事を1つ選んで見る。
これを繰り返して1階層目のニュース記事一覧を一通り探索すると、探索してきたニュース記事の関連ニュース記事を探索する（2階層目）。
まず1つ目に探索したニュース記事の関連ニュース記事を1通り探索する。次に2回目に探索したニュース記事の関連ニュース記事を1通り探索する。 これを繰り返し、ニュース記事全てを探索する。
このように幅優先探索では、同列にある探索対象を優先して、同列にある探索対象を探索し終わってから、1つ階層の下の探索対象を探索していく。
深さ優先探索
先ほどの木構造の図を見て分かるように、各ノードを親として見たときに子ノードを探索する処理が繰り返される。 そのため、これをコードで表現するためには、各ノードそれぞれに着目して、再帰関数を使って探索する処理を書けば良い。
問題
競プロの下記の問題をもとにコードを書いてみる。
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=ja
標準入力が与えられて島がいくつあるかを判定すれば良い。これは隣接している島を探索していって1セットとしてカウントして行けば良い。各区画ごとに注目して隣接している区画を探索してカウントしていけば良いので、深さ優先で探索していく。
解答
package main
import (
"fmt"
)
func main() {
data := make([][][]int, 0) // データセット
for {
var w, h int
fmt.Scan(&w, &h)
if w == 0 && h == 0 {
break
}
cc := make([][]int, h) // 1つのデータ
for i := 0; i < h; i++ {
c := make([]int, w)
for j := 0; j < w; j++ {
fmt.Scan(&c[j])
}
cc[i] = c
}
data = append(data, cc)
}
dataSetLen := len(data)
countList := make([]int, dataSetLen)
for i := 0; i < dataSetLen; i++ { // 各データセットについて
w := len(data[i][0])
h := len(data[i])
visited := make([][]bool, h) // 探索済みかどうかを格納する二重配列
for l := 0; l < h; l++ {
visited[l] = make([]bool, w)
}
var count int
for x := 0; x < w; x++ { // 全ての座標を探索
for y := 0; y < h; y++ {
// 座標(x,y)を起点にする島を探索して、探索した座標はvisitedにマーク
isIsland := dfs(data[i], visited, x, y, w, h)
if isIsland {
count++
}
}
}
countList[i] = count
}
for i := 0; i < len(data); i++ {
fmt.Println(countList[i])
}
}
func dfs(cc [][]int, visited [][]bool, baseX, baseY, w, h int) bool {
if visited[baseY][baseX] == true { // 探索済みの場合
return false
}
visited[baseY][baseX] = true
if cc[baseY][baseX] != 1 { // 陸じゃない場合
return false
}
// 8方向に移動
for dx := -1; dx <= 1; dx++ {
for dy := -1; dy <= 1; dy++ {
x := baseX + dx
y := baseY + dy
if x >= 0 && x < w && y >= 0 && y < h {
dfs(cc, visited, x, y, w, h)
}
}
}
return true
}
まず座標を1つ与えられた時に、隣接する島をvisitedにマークしていく再帰関数を定義する。
呼び出す側では、全ての座標を起点にそれぞれ探索していくが、重複計上を防ぐためにvisitedにマークしている場合はreturnする。
再帰関数がtrueで返ってくるときは島を1つ探索し終わった時なのでカウントをインクリメントする。
ポイント
ポイントは、①探索済みかどうかをマークするための配列を作成すること。②再帰関数で探索した箇所をマークしていくこと。③全ての座標を起点にして再帰関数を呼び出すこと。
幅優先探索
先ほどの木構造の図を見て分かるように、順番に各ノードを見ていくと同時に探索したノードは保存しておく必要がある。
これはキューを使えば実現できる。
問題
以下の問題をもとにコードを書いていく。
マス目を標準入力で与えられて、最短経路でゴールまで行くまでの手数を数え上げられれば良い。
解答
package main
import "fmt"
func main() {
var H, W int
fmt.Scan(&H, &W)
c := make([]string, H)
visited := make([][]int, H) // 対象とする座標に行き着くまでのcostを入れる二重配列
for i := 0; i < H; i++ {
var s string
fmt.Scan(&s)
c[i] = s
visited[i] = make([]int, W)
}
if string(c[0][0]) == "#" || string(c[H-1][W-1]) == "#" {
fmt.Println(-1)
return
}
var q queue
q.push(coordinate{
x: 1,
y: 1,
})
// 配列を-1で初期化
for i := 0; i < H; i++ {
for j := 0; j < W; j++ {
visited[i][j] = -1
}
}
visited[0][0] = 0 // スタートはcostは0
dxList := []coordinate{
{
x: 1,
y: 0,
},
{
x: 0,
y: 1,
},
{
x: -1,
y: 0,
},
{
x: 0,
y: -1,
},
}
for len(q.slice) > 0 {
cBefore := q.pop()
for i := 0; i < 4; i++ {
nextX := cBefore.x + dxList[i].x
nextY := cBefore.y + dxList[i].y
if 1 <= nextX && nextX <= W && 1 <= nextY && nextY <= H {
xIndex := nextX - 1
yIndex := nextY - 1
if string(c[yIndex][xIndex]) == "." && visited[yIndex][xIndex] == -1 {
visited[yIndex][xIndex] = visited[cBefore.y-1][cBefore.x-1] + 1
q.push(coordinate{
x: nextX,
y: nextY,
})
}
}
}
}
if visited[H-1][W-1] == -1 {
fmt.Println(-1)
return
}
var whiteCount int // 初期配置の白の数
for i := 0; i < H; i++ {
for j := 0; j < W; j++ {
if string(c[i][j]) == "." {
whiteCount++
}
}
}
minRouteWhiteCount := visited[H-1][W-1] + 1 // ゴールするための最短経路で使う白の数
fmt.Println(whiteCount - minRouteWhiteCount) // 初めにあった白の数から必要な分を引いた不要な白の数
}
type coordinate struct {
x int
y int
}
type queue struct {
slice []coordinate
}
func (q *queue) push(c coordinate) {
q.slice = append(q.slice, c)
}
func (q *queue) pop() coordinate {
c := q.slice[0]
q.slice = q.slice[1:]
return c
}
最短経路でゴールまで行くのに必要なコストが必要なので、今回は各区画までに到達するのに必要な最低コストを記録する二重配列を用意する。
スタートはコスト0で到達できることが自明なので、スタートの座標をキューに入れ、最短コストをvisitedに記録する。
スタートから探索していき、そこから+1のコストで探索できる座標を探して、既に最低コストで探索されていない場合は最短コストをvisitedに記録して、キューに入れておく。後ほどキューに入れたこの座標を基準にまたコスト+1で探索できる座標を探す。つまり、キューに値がある限りはループを回す。
こうして最短コストを記録していくと、ゴールを含む各座標にはそこに至るまでの最短コストが記録されている。最短ルートを辿るには、ゴールまでの最短コストからデクリメントして辿れる経路を辿れば良い。
ポイント
ポイントは、探索にかかるコストは1つ前の座標を探索するのにかかるコスト+1であること。②visitedには最低コストを記録するので、visitedが初期値（今回でいう-1）であればコストを記録するが、初期値以外の値が入っていれば、その値がその区画に到達するための最短コストなので記録をしないこと。
Goでbit演算
競プロでたまにbit全探索の問題に遭遇するけど、毎回どうやるんだっけってなってググっているのでまとめておく。
演算子について
&（AND）
「&（AND）」は2つのbitを比較してどちらも1なら1、どちらかが0の場合は0を返す。
例えば「100 & 101 = 100」
| （OR）
「|（OR）」は2つのbitを比較してどちらかが1なら1を返す。
例えば「100 | 101 = 101」
>> （右ビットシフト）
「>> （右ビットシフト）」はbitを右にずらす。意味的には2の-n乗することになる。
ずらしたことにより空いた部分には0が入り、桁数からはみ出た分は消す。このはみ出て消えることをオーバーフローと呼ぶ。
例えば「100 >> 1 = 010」
<< （左ビットシフト）
「<<（左ビットシフト）」はbitを左にずらす。意味的には2のn乗することになる。
例えば「101 << 1 = 1010」
Goでbit演算
package main
import "fmt"
func main() {
var a uint = 4 // 100
var b uint = 5 // 101
fmt.Printf("10進数: %d, 2進数: %b\n", a&b, a&b)
fmt.Printf("10進数: %d, 2進数: %b\n", a|b, a|b)
fmt.Printf("10進数: %d, 2進数: %b\n", a>>1, a>>1)
fmt.Printf("10進数: %d, 2進数: %b\n", b<<1, b<<1)
}
Goでbit全探索
以下の基本的な問題をもとに考えていく。
N個の文字列について、選ぶor選ばないの2通りがあるので、2N個のパターンがありこの全パターンを全探索したい。
全てのパターンをビットとして表したいので、0（全てを選ばないパターン）から2Nまでのビットを考える必要がある。
よってfor文で0から1<<uint64(N)の1つ手前まで（範囲指定で<にすればOK）のパターンを考える。
各桁についてbitが1かどうかを考えれば良いので、bitsに対して0からNまでの数を右シフトして1かどうかを判定していく。
&1をしているのはその桁数が1かどうかを判定するため。
for bits := 0; bits < (1 << uint64(N)); bits++ {
for i := 0; i < N; i++ {
if (bits>>uint64(i))&1 == 1 {
// 処理
}
}
}
ディスク使用率が100%になっていた時の動作確認と改善
Linuxの本を読んでいてとあるコマンドの動作確認してみよう〜と思って、VPSでapt-getしてみると、ディスク容量が足りずapt-getできなかった...その時の備忘録。
実行環境は以下です。
$ cat /etc/os-release NAME="Ubuntu" VERSION="20.04.2 LTS (Focal Fossa)" ID=ubuntu ID_LIKE=debian PRETTY_NAME="Ubuntu 20.04.2 LTS" VERSION_ID="20.04" HOME_URL="https://www.ubuntu.com/" SUPPORT_URL="https://help.ubuntu.com/" BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/" PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy" VERSION_CODENAME=focal UBUNTU_CODENAME=focal
CPUの状態とかVPSのストレージの容量などのスペックに関する情報も今回は大事そうなので、概要を貼っておく。
ストレージは30Gでメモリは512Mの1コア。
原因を調べる
まず出ていたエラーはこちら
$ sudo apt-get install sysstat -y Reading package lists... Error! E: Write error - write (28: No space left on device) E: IO Error saving source cache E: The package lists or status file could not be parsed or opened
No space left on deviceなるほど？と思ってググってみると、エラーメッセージからも分かるようにディスク容量が足りないっぽい。
監視しているGrafanaを見てみようとするも、こちらもerror while signing in userというエラーが出て、どうやらディスク容量が足りなくてログインできないらしい（やばすぎ）
この記事を参考に状況確認をしていく。
ディスク容量を確認してみると、確かに100%になっている。
df -h Filesystem Size Used Avail Use% Mounted on udev 196M 0 196M 0% /dev tmpfs 48M 7.8M 41M 17% /run /dev/vda2 30G 30G 0 100% / tmpfs 240M 0 240M 0% /dev/shm tmpfs 5.0M 0 5.0M 0% /run/lock tmpfs 240M 0 240M 0% /sys/fs/cgroup overlay 30G 30G 0 100% /var/lib/docker/overlay2/16732358870e1f380a4419b2b6f3ad96de63978c4db409f9d4101e1e548c3347/merged overlay 30G 30G 0 100% /var/lib/docker/overlay2/6c34794ad8d40cdae81f6786b3f358da1dfa6be67e303c4a0a33f624e58e6f33/merged overlay 30G 30G 0 100% /var/lib/docker/overlay2/cab37ca7d92d44cec7ac44e89e3586f66e5b45f1848f36a84caa466a738b3894/merged overlay 30G 30G 0 100% /var/lib/docker/overlay2/f077786c541e8b771b84f244c3df32824d1a8a4ac1a79a0d48d874ea3b5a67ea/merged overlay 30G 30G 0 100% /var/lib/docker/overlay2/046193df3aff249777c74c548e11a54aed88626e09e464b8069e6e06e10b3e6a/merged overlay 30G 30G 0 100% /var/lib/docker/overlay2/43950b4910e94cc1f29e7cebedf980c366621a4567318941409a355fbaf4cbe9/merged overlay 30G 30G 0 100% /var/lib/docker/overlay2/ee953ed406e774cd7d425ccbbf19d458cb1d96e9dfe63ce9a866e4b7bfc9b1f1/merged overlay 30G 30G 0 100% /var/lib/docker/overlay2/e292d887b9f781e9e40fd48c3bf49c3239c646b2b626cb95c4801fda335809e9/merged overlay 30G 30G 0 100% /var/lib/docker/overlay2/1b15663ad519a318e573dc885d62a9a10bdbcd879ea619b67d430061d5869e1c/merged overlay 30G 30G 0 100% /var/lib/docker/overlay2/0ad38b35d06e8fd47ecbec097453548f20dee51a46446eab6a408902ba4650e1/merged overlay 30G 30G 0 100% /var/lib/docker/overlay2/8adec6f6f1fde1674d3db066b63aa418fb082f3cc846bcd083575490c7193427/merged /dev/loop10 56M 56M 0 100% /snap/core18/2284 /dev/loop7 44M 44M 0 100% /snap/snapd/14978 /dev/loop4 68M 68M 0 100% /snap/lxd/22526 /dev/loop0 62M 62M 0 100% /snap/core20/1376 /dev/loop1 44M 44M 0 100% /snap/snapd/15177 /dev/loop2 56M 56M 0 100% /snap/core18/2344 /dev/loop6 68M 68M 0 100% /snap/lxd/22753 /dev/loop3 62M 62M 0 100% /snap/core20/1405
inodeの方は余裕がある。
$ df -i Filesystem Inodes IUsed IFree IUse% Mounted on udev 50094 445 49649 1% /dev tmpfs 61192 977 60215 2% /run /dev/vda2 1966080 255325 1710755 13% / tmpfs 61192 1 61191 1% /dev/shm tmpfs 61192 4 61188 1% /run/lock tmpfs 61192 18 61174 1% /sys/fs/cgroup overlay 1966080 255325 1710755 13% /var/lib/docker/overlay2/16732358870e1f380a4419b2b6f3ad96de63978c4db409f9d4101e1e548c3347/merged overlay 1966080 255325 1710755 13% /var/lib/docker/overlay2/6c34794ad8d40cdae81f6786b3f358da1dfa6be67e303c4a0a33f624e58e6f33/merged overlay 1966080 255325 1710755 13% /var/lib/docker/overlay2/cab37ca7d92d44cec7ac44e89e3586f66e5b45f1848f36a84caa466a738b3894/merged overlay 1966080 255325 1710755 13% /var/lib/docker/overlay2/f077786c541e8b771b84f244c3df32824d1a8a4ac1a79a0d48d874ea3b5a67ea/merged overlay 1966080 255325 1710755 13% /var/lib/docker/overlay2/046193df3aff249777c74c548e11a54aed88626e09e464b8069e6e06e10b3e6a/merged overlay 1966080 255325 1710755 13% /var/lib/docker/overlay2/43950b4910e94cc1f29e7cebedf980c366621a4567318941409a355fbaf4cbe9/merged overlay 1966080 255325 1710755 13% /var/lib/docker/overlay2/ee953ed406e774cd7d425ccbbf19d458cb1d96e9dfe63ce9a866e4b7bfc9b1f1/merged overlay 1966080 255325 1710755 13% /var/lib/docker/overlay2/e292d887b9f781e9e40fd48c3bf49c3239c646b2b626cb95c4801fda335809e9/merged overlay 1966080 255325 1710755 13% /var/lib/docker/overlay2/1b15663ad519a318e573dc885d62a9a10bdbcd879ea619b67d430061d5869e1c/merged overlay 1966080 255325 1710755 13% /var/lib/docker/overlay2/0ad38b35d06e8fd47ecbec097453548f20dee51a46446eab6a408902ba4650e1/merged overlay 1966080 255325 1710755 13% /var/lib/docker/overlay2/8adec6f6f1fde1674d3db066b63aa418fb082f3cc846bcd083575490c7193427/merged /dev/loop10 10847 10847 0 100% /snap/core18/2284 /dev/loop7 480 480 0 100% /snap/snapd/14978 /dev/loop4 799 799 0 100% /snap/lxd/22526 /dev/loop0 11777 11777 0 100% /snap/core20/1376 /dev/loop1 482 482 0 100% /snap/snapd/15177 /dev/loop2 10849 10849 0 100% /snap/core18/2344 /dev/loop6 802 802 0 100% /snap/lxd/22753 /dev/loop3 11778 11778 0 100% /snap/core20/1405
どこでディスクを食っているのか確認。
sudo du -sh /* 0 /bin 298M /boot 4.0K /cdrom 0 /dev 5.5M /etc 11M /home 0 /lib 0 /lib32 0 /lib64 0 /libx32 16K /lost+found 4.0K /media 4.0K /mnt 16K /opt du: cannot access '/proc/2809715/task/2809715/fd/4': No such file or directory du: cannot access '/proc/2809715/task/2809715/fdinfo/4': No such file or directory du: cannot access '/proc/2809715/fd/3': No such file or directory du: cannot access '/proc/2809715/fdinfo/3': No such file or directory 0 /proc 84K /root 7.8M /run 0 /sbin 1.5G /snap 4.0K /srv 2.1G /swap.img 0 /sys 264M /tmp 3.0G /usr 28G /var
/usrはライブラリ群が入っている。どうみても/varがやばそうなので追って確認してみる。
$ sudo du -sh /var/* [sudo] password for hysrtr: 824K /var/backups 98M /var/cache 4.0K /var/crash 27G /var/lib 4.0K /var/local 0 /var/lock 832M /var/log 4.0K /var/mail 4.0K /var/opt 0 /var/run 76K /var/snap 28K /var/spool 28K /var/tmp
もう1階層下。
$ sudo du -sh /var/lib/* 12K /var/lib/AccountsService 36K /var/lib/PackageKit 8.0K /var/lib/apport 139M /var/lib/apt 4.0K /var/lib/boltd 228K /var/lib/cloud 3.1M /var/lib/command-not-found 536K /var/lib/containerd 4.0K /var/lib/dbus 4.0K /var/lib/dhcp 26G /var/lib/docker 38M /var/lib/dpkg 900K /var/lib/fwupd 4.0K /var/lib/git 16K /var/lib/grub 16K /var/lib/initramfs-tools 4.0K /var/lib/landscape 8.0K /var/lib/logrotate 4.0K /var/lib/man-db 4.0K /var/lib/misc 4.0K /var/lib/ntp 4.0K /var/lib/os-prober 28K /var/lib/pam 4.0K /var/lib/plymouth 40K /var/lib/polkit-1 4.0K /var/lib/private 4.0K /var/lib/python 4.0K /var/lib/resolvconf 840M /var/lib/snapd 4.0K /var/lib/sntp 8.0K /var/lib/sudo 580K /var/lib/systemd 4.0K /var/lib/tpm 4.0K /var/lib/ubuntu-advantage 8.0K /var/lib/ubuntu-release-upgrader 108K /var/lib/ucf 4.0K /var/lib/unattended-upgrades 12K /var/lib/update-manager 20K /var/lib/update-notifier 608K /var/lib/usbutils 8.0K /var/lib/vim
26G /var/lib/docker
知ってた。だってコンテナ11個立ってるから。ということでdockerコンテナでストレージを食い潰していることが確認できた。
メトリクスを見る
まずデプロイされているサーバーはちゃんと応答するのか確認した。
サーバーの動作確認して、APIも叩けていて読み書きができているのは確認した。
ディスクを圧迫しているのは、とあるプロダクトでログを出力していて、promtailがLokiに送ってLokiが保存しているログがかなり溜まってきてディスクを圧迫し出したのかな〜と推測。
（ちゃんとログローテートしようね）
Grafanaが見れないので、ログファイルを直接tailコマンドで確認してみたけど、アクセスは全然ない...最終アクセスは2ヶ月前とか。
一応duコマンドでログファイルの容量を見てみる。
$ du -h 8.0K ./derror 356K ./logging/log 368K ./logging 8.0K ./dcontext 8.0K ./db 36K ./server/handler 12K ./server/model/mock_model 20K ./server/model 16K ./server/service/mock_service 56K ./server/service 120K ./server 8.0K ./utils/mock_utils 16K ./utils 12K ./http/middleware 8.0K ./http/response/mock_response 16K ./http/response 32K ./http 564K .
ログファイルが入っているlogging/logも容量的には小さいので、このプロダクトのログが原因ではなさそう。
貧弱だけどVPSのメトリクスを見てみる。
CPU使用率は確かに少しずつ上がっていて直近だと急増とは言わないまでも増えている。
特別リリースしているプロダクトがあるわけではないし、そんな顕著にアクセス数が増える要因はなさそう。
CPU使用率が上がっているのはログが溜まってきて、ログ出力する際のファイルへの書き込みだったりログファイルの読み込み処理が重たくなってきたのかな〜。
と思ったけど、そもそもログが増えていないので多分それもない...
一旦Nginxのログを見てみたいけど、コンテナに入るディスクすらない（笑）
$ docker exec -it nginx-proxy sh failed to create runc console socket: mkdir /tmp/pty342788273: no space left on device: unknown
freeコマンドでメモリの使用状況を確認する。
$ free -m
total used free shared buff/cache available
Mem: 478 282 10 4 185 172
Swap: 2047 587 1460
-mオプションでメガバイト単位で出力されている。メモリには余裕がありそう。
んじゃとりあえずいらないコンテナ落とそうと思ったけど、消せない。
$ docker-compose down [2811825] INTERNAL ERROR: cannot create temporary directory!
プロセスを切ろうと思ったけど、それも無理。
OCI runtime exec failed: write /tmp/runc-process177314135: no space left on device: unknown
こういうことにならないように監視してSlack通知とかできる仕組み作ろうってことね（学び）
/var/lib/docker/overlay2の肥大化
df -hコマンドの結果を再度見てみると、/var/lib/docker/overlay2配下がかなり肥大化している。
ググってみると対処法があるらしいので、やってみる。
ディスク容量の確保
$ sudo docker system prune WARNING! This will remove: - all stopped containers - all networks not used by at least one container - all dangling images - all dangling build cache Are you sure you want to continue? [y/N] y Deleted Networks: infecshotapi_loki infecshotapi_default Deleted Images: untagged: phpmyadmin/phpmyadmin@sha256:8911fb0cfef21dc9fb385ad02cc3254179cd7df87bab3d3a6fa04d1f0549463f deleted: sha256:72000eb04892657673456eb9e49a17c1a1c4f8bd248762e635a5a9a2d419b706 deleted: sha256:0aae68c037aa83cc840e9497099e34126c3267e89012e5ac9721dea08b57ef5d deleted: sha256:4d753ce77b2a8902763e263ce8e8f67734ce82b3711d4646e01269be4e667a99 deleted: sha256:04f56bb98a35279655735589da44e15ba58fe980ec110bbeba33ae3b7278fb51 deleted: sha256:831e6802a4050103c5100dc975758f691b8ef53ab91b7f18220febbfcadcf8d2 deleted: sha256:ce51a414c795e165e1812cec96f4272d5b7ca8aa46f7fa947cc4563740178465 deleted: sha256:659bb6c656b7ad3de6bc48b2a42eb52203a6d82bddc329b55ac3bb87d57fb41c deleted: sha256:08e5085476b5fe7cdcdde54c5eb8b57b0ffe3a8cbbbd3efc34379fae5cd0fe34 deleted: sha256:240444cca7a1c2258cf0040c92d0cc466ecd3ffd7bcc9c3c98ed1b163ab82b6f deleted: sha256:d6b236f42314993f24d1b6f26e18050ef697518c6f2a4b7819acd69c08531b5a deleted: sha256:59ec2d85a348f5f7c2927b57d3d60cbc7143427d84ad63e2f7678eb5940100d1 deleted: sha256:86fb957d5b48d7590796aca0c79c7a15d1a035c182ba3c1a5c03d5c8718907f9 deleted: sha256:0f79560001ca66b44b869333a059ac9f109f2cc2bfda3da5e0b9328ccf6f5876 deleted: sha256:d2b3415933888ae214a940917ef6ef3de81fbe6dc29a8700ad0971eb2af12437 deleted: sha256:9635b15bd71af78bd50d20f536c2f1b1295d44796cf8aa142fcb7f83a4705078 deleted: sha256:a966a3879737b38ba08d50017ceb96d0733ca61aa8be2a83ec6d7eb36c03385e deleted: sha256:3942e303af0d218de6c79079a0594913df200acab6c5790197dc24c766703340 deleted: sha256:95ad977108150f3b154a1ac2b9592bb2d02c281200af808951ae5c50b19e97e3 deleted: sha256:14a1ca976738392ffa2ae4e54934ba28ab9cb756e924ad9297a4795a4adbfdf6 Total reclaimed space: 477.2MB
お、500MBぐらい空きができた。
けどこれでは全然ディスク使用率は改善されていない。
やっぱり稼働しているコンテナを落としてoverlay削除するしかないかなぁ...
コンテナを落としてpruneして、再度dfコマンドでディスク使用率を確認
$ df -h Filesystem Size Used Avail Use% Mounted on udev 196M 0 196M 0% /dev tmpfs 48M 1.6M 47M 4% /run /dev/vda2 30G 7.5G 21G 27% / tmpfs 240M 0 240M 0% /dev/shm tmpfs 5.0M 0 5.0M 0% /run/lock tmpfs 240M 0 240M 0% /sys/fs/cgroup /dev/loop10 56M 56M 0 100% /snap/core18/2284 /dev/loop7 44M 44M 0 100% /snap/snapd/14978 /dev/loop4 68M 68M 0 100% /snap/lxd/22526 /dev/loop0 62M 62M 0 100% /snap/core20/1376 /dev/loop1 44M 44M 0 100% /snap/snapd/15177 /dev/loop2 56M 56M 0 100% /snap/core18/2344 /dev/loop6 68M 68M 0 100% /snap/lxd/22753 /dev/loop3 62M 62M 0 100% /snap/core20/1405
overlay自体の仕組みなどは結構難解だったのでまた別の機会にまとめようと思います。
参考
スライスの内部実装と挙動の確認
スライスの挙動でなんでこうなるんだ？と度々なるのでまとめてみる。
配列
まず配列について。
配列は長さを含めて型。
An array’s size is fixed; its length is part of its type ([4]int and [5]int are distinct, incompatible types).
長さ4の配列は以下のような感じで
var arr [4]int
メモリ内では、4つの整数値を順番に並べて表現される。
Goの配列は値であり、配列を格納した変数は配列全体を表す。（C言語では配列の最初の要素へのポインタ）
Go’s arrays are values. An array variable denotes the entire array; it is not a pointer to the first array element (as would be the case in C).
スライスの基本
スライスの定義
スライスは配列へのポインタと、長さと容量を持った値。
type slice struct {
array unsafe.Pointer
len int
cap int
}
スライスは内部配列のポインタを参照しているので、関数に渡すときは値渡しでもポインタ渡しでも書き換えが可能。
初期化
以下のような形で初期化することが多い。
s1 := make([]int, 0, 5) // 内部配列のサイズが5で値が入っていない（ように見える）スライス（内部配列には[0 0 0 0 0]で初期化されているはず） fmt.Println(s) // [] s2 := make([]int, 5) // 内部配列のサイズも値の入っているサイズも5のスライス fmt.Println(s) // [0 0 0 0 0]
インデックス操作
コロン:で区切ることでslicingすることができる。
例えば、b[1:4]はスライスbのインデックス 1 から 3（紛らわしいけど4は含まない） までの要素を含むスライスを作成する 。
s := []int{0, 1, 2, 3, 4}
s1 := s[1:4]
fmt.Println(s1, len(s1), cap(s1)) // [1 2 3] 3 4
容量は切り取ったスライスの先頭から参照している内部配列の容量までを数える。
The capacity is the number of elements in the underlying array (beginning at the element referred to by the slice pointer).
再度slicingすれば容量まで大きくすることができる。
s := []int{0, 1, 2, 3, 4}
s1 := s[1:4]
fmt.Println(s1, len(s1), cap(s1)) // [1 2 3] 3 4
s2 := s1[:cap(s1)]
fmt.Println(s2, len(s2), cap(s2)) // [1 2 3 4] 4 4
このようにslicingして値が一見見えなくても内部配列では値を保持しており、 GC されず値が残る場合がある。
かなりの要素数をslicingするようであれば注意したい。
Since the slice references the original array, as long as the slice is kept around the garbage collector can’t release the array
要素の追加
append()はそのスライスから見た末尾へ値を追加（末尾+1の位置を書き換え）しスライスの長さを更新する。
内部配列の長さが足りない場合は、まず新しく長さが倍の配列を用意してそこに既存の内部配列の値をコピーし、末尾へ値を追加したのち、その新しい配列を内部配列として参照するようにスライスが持つ配列へのポインタを貼り直して、スライスの長さと容量を更新する。
arr := make([]int, 0, 0) fmt.Println(arr, len(arr), cap(arr)) // [] 0 0 arr = append(arr, 0) fmt.Println(arr, len(arr), cap(arr)) // [0] 1 1 arr = append(arr, 1) fmt.Println(arr, len(arr), cap(arr)) // [0 1] 2 2 arr = append(arr, 2) fmt.Println(arr, len(arr), cap(arr)) // [0 1 2] 3 4 arr = append(arr, 3) fmt.Println(arr, len(arr), cap(arr)) // [0 1 2 3] 4 4 arr = append(arr, 4) fmt.Println(arr, len(arr), cap(arr)) // [0 1 2 3 4] 5 8
コードを見た感じ、容量が256以上だと単純に2倍確保するわけでは無さそう。
https://cs.opensource.google/go/go/+/master:src/runtime/slice.go;l=196
このようにappend時に容量オーバーしてしまうと、新しいメモリ領域をOSに要求して確保し、既存のデータを新しい領域にコピーする必要がある。
なるべくこのコストを減らすために、事前にmake()で必要十分量のメモリを確保しておく工夫が必要。
ケーススタディ
シャローコピー時の挙動
シャローコピーした場合は参照している内部配列は同じなので、コピー先はコピー元の影響を受ける（逆も然り）
ただしappendの際に容量オーバーで内部配列が変わると影響は受けなくなる。
a := []int{1, 2, 3}
b := a // シャローコピー（参照している内部配列は同じ）
fmt.Println(b) // [1 2 3]
a[0] = 111 // aとbは変数自体のメモリのアドレスは別だが、内部配列は同じなのでb[0]も111になる
fmt.Println(a) // [111 2 3]
fmt.Println(b) // [111 2 3]
a = append(a, 4) // 容量オーバーaの内部配列が変わるのでbには影響なし
fmt.Println(a) // [111 2 3 4]
fmt.Println(b) // [111 2 3]
コピー元のスライスにappendした時のコピー先の挙動
appendでは対象のスライスの長さしか更新されないので、コピー元のスライスにappendした場合、コピー先が同じ配列を参照していてもコピー先のスライスの長さは更新されていないので、コピー先からは追加された要素が見えない。
a := make([]int, 0, 4) a = append(a, 1, 2, 3) fmt.Println(a) // [1 2 3] b := a a[0] = 111 fmt.Println(a) // [111 2 3] fmt.Println(b) // [111 2 3] a = append(a, 4) // 容量に余裕があるのでaとbは同じ内部配列を参照するが、aのappendではbのスライスの長さは更新されないのでbからは追加された4が見えない fmt.Println(a) // [111 2 3 4] fmt.Println(b) // [111 2 3] fmt.Println(len(b), cap(b)) // 3 4
appendによる内部配列の書き換え
appendはスライスから見た末尾に値を追加するので、同じ内部配列を参照しているスライスから見ると書き換えられて見えることがある。
a := make([]int, 0, 4) a = append(a, 1, 2, 3) fmt.Println(a) // [1 2 3] b := a a = append(a, 4) // 内部配列に4を追加してaのスライスの長さを更新 fmt.Println(a) // [1 2 3 4] fmt.Println(b) // [1 2 3] b = append(b, 5) // bのスライスから見た末尾に5を追加（内部配列の4要素目に5を入れる）するので、内部配列の4要素目の4が5に書き換えられる fmt.Println(a) // [1 2 3 5] fmt.Println(b) // [1 2 3 5]
補足: シャローコピーとディープコピー
シャローコピー
単純に別の変数に代入するだけだとシャローコピーなので要素のアドレスは同じ。
シャローコピーは実体（データ）のコピーを行わないで、オブジェクトをコピーすること。
a := []int{1, 2, 3}
b := a // シャローコピー
fmt.Printf("a at %p, b at %p\n", &a, &b) // 変数自体のアドレスは当然異なる
fmt.Printf("a[0] at %p, b[0] at %p\n", &a[0], &b[0]) // 内部配列は同じなので要素のアドレスは同じ
ディープコピー
copy()を使ってディープコピーする。
a := []int{1, 2, 3}
b := make([]int, len(a))
copy(b, a) // aをbにコピー
fmt.Printf("a at %p, b at %p\n", &a, &b) // 変数自体のアドレスは当然異なる
fmt.Printf("a[0] at %p, b[0] at %p\n", &a[0], &b[0]) // 内部配列が別なので要素のアドレスは異なる
参考
fmt.ScanやbufioのScannerで標準入力を受け取る
競プロで標準入力を受け取るとき、行単位で受け取ったりスペース区切りで受け取ったりしたいけど、どうすれば良いんだっけってなったのでまとめておく。
fmt.Scan
結論、fmt.Scanで全て解決する。
Scan scans text read from standard input, storing successive space-separated values into successive arguments. Newlines count as space. It returns the number of items successfully scanned. If that is less than the number of arguments, err will report why.
スペース区切りで変数に格納するし、改行もスペースとして扱うらしい。
fmt.Scanの引数はポインタかScannerインターフェースでなければいけないらしいので注意。
All arguments to be scanned must be either pointers to basic types or implementations of the Scanner interface.
実行例はこんな感じ。
var s1, s2, s3 string
fmt.Scan(&s1, &s2, &s3)
fmt.Printf("Your input is %s %s %s\n", s1, s2, s3)
❯ go run cmd/main.go 1 2 3 Your input is 1 2 3 ❯ go run cmd/main.go 1 2 3 Your input is 1 2 3
可変長で標準入力を受けたければ、以下のような感じ。
var N int
fmt.Scan(&N)
a := make([]int, N)
for i := 0; i < N; i++ {
fmt.Scan(&a[i])
}
fmt.Println(a)
❯ go run tmp/main.go 3 1 2 3 [1 2 3]
fmt.Scanで困るパターン
便利なfmt.Scanだけど実は遅くて困る時がある。
実際にAtCoder Beginner Contest 246の C - Couponでは、1行で空白区切りの文字を最大で109個読み込む必要がある。
以下の画像のようにfmt.Scanで表順入力を受け取るかその他の高速な方法で受け取るかで実行速度や使用するメモリの量が変わる。
以下の問題でもfmt.Scanではタイムアウトしてしまう。
atcoder.jp
bufio.Scanner
そこで便利なのがbufioパッケージのScanner。
使い方は以下。初めに整数Nを受け取り、N個の空白区切りの整数を受け取るとする。
// ひとまず初期化
var scanner = bufio.NewScanner(os.Stdin)
func nextInt() int {
scanner.Scan() // トークンの読み込み
i, e := strconv.Atoi(scanner.Text()) // 読み込んだトークンをTextメソッドで取り出し
if e != nil {
panic(e)
}
return i
}
func main() {
var N int
fmt.Scan(&N)
scanner.Split(bufio.ScanWords) // 空白区切りで受け取るので引数にbufio.ScanwWordsを渡す
A := make([]int, N)
for i := 0; i < N; i++ {
A[i] = nextInt() // ScanメソッドやTextメソッドで読み込んで取り出して加工
}
