Go で昇格可能な RWMutex を実装した
順番は守りましょう。どうも、かわしんです。トランザクションを実装中です。
さて、先日トランザクションの並行制御アルゴリズムである「S2PL (Strict Two Phase Lock)」を実装した 1 のですが、Read オペレーションでは Read Lock を取った後にすぐに解放していました。2 しかし、よくよく考えると 2PL はロックを解放した後にロックを取得することを禁じているため(だからこそ 2 phase なのですが)、実装が間違っていました。
つまり、Read Lock して Read した値はロックを保持し続け、Write するときにロックを Write Lock に昇格させる必要がありました。
この振る舞いを実現するためには、昇格に対応した Read Write Lock の仕組みが必要になります。
Go には sync.RWMutex
という goroutine に対応した便利な Read Write Lock の仕組みが用意されていますが、昇格には対応していません。Github を探しても使えそうなライブラリはなかったので自作しました。
今回はこのライブラリの紹介です。
欲しかったもの
欲しかった機能は以下の通りです。
- Read (shared) Lock と Write (exclusive) Lock の仕組み
- Read Lock から Write Lock への昇格 (Upgrade)
- Upgrade をする時はデッドロックする可能性が高いため、デッドロックを回避する仕組み
- シンプルで速い実装
既存のライブラリ
一応 Go におけるロックの実装を調べたので、既存のライブラリがなぜ使えなかったのかを列挙していきます。
- GitHub - tilinna/rumutex: A Go (golang) implementation of an upgradable RW lock.
- 昇格可能な R/W Lock を提供。
- 内部実装は
sync.RWMutex
を利用。Upgrade()
するときはアトミックにフラグを立てて競合していないことを確認してからRUnlock() -> Lock()
をしている。 Upgrade()
ではアトミックなフラグ操作ですでにUpgrade()
していることがわかったらreturn false
して関数を抜けてしまう。待たない。- ダメなところ
Lock()
がない。Write Lock をする時はRLock() -> Upgrade()
しか方法が用意されていないUpgrade()
は競合した時にすぐに関数を抜けるので、Write Lock 同士を待ち合わせることができない 。トランザクションで使えない。
- GitHub - laynelee/rwlock: read write lock that supports try lock for golang
- Try Lock が可能な R/W Lock を提供。
- 内部実装はチャネルを利用。
- ダメなところ
- チャネルによるロックは遅い 3
- 昇格はできない
- GitHub - subchen/go-trylock: TryLock support on read-write lock for Golang
- タイムアウト + Try Lock ができる R/W Lock を提供。
- 内部実装はチャネルを利用。
- ブロードキャストにチャネルの
close()
を利用している。また close したチャネルを入れ替えるためにsync.Mutex
も利用している。 - ダメなところ
- チャネルによるロックは遅い [^3]
- 昇格はできない
- GitHub - BurntSushi/locker: A simple Golang package for conveniently using named read/write locks. Useful for synchronizing access to session based storage in web applications.
- ただ key によって Mutex をルーティングをするだけ
世の中に必要なコンポーネントがないからと、プロダクトを作るのを諦めたり、仕様を捻じ曲げたりするのは嫌いなので、自作しました。
実装
ロックの仕組みと実装方法
Go でのロックの仕組みはこの動画がわかりやすいです。
Mutex は以下の 2 段階に分けてロックが取られています。
- アトミックな操作による spin lock
- goroutine を停止させてキューに詰めて待つ
sync.Mutex
で後者の goroutine 同士の待ち合わせの処理は runtime
の API である runtime_SemacquireMutex()
でおこなっているようですが、これは標準ライブラリである sync
にだけ公開されているため、実質 goroutine 同士のプリミティブな待ち合わせ処理を僕たち一般の開発者が利用することはできません。
そこで、sync.Mutex
や sync.RWMutex
といった標準ライブラリの Mutex コンポーネントを利用して実装することにしました。
注意すること
ここで昇格可能な Read Write Lock の振る舞いとして注意しておくべきことを紹介します。
1 つ目は、Lock() は Upgrade() を妨げない ということです。Upgrade()
を sync.RWMutex
で愚直に実装しようとすると RUnlock()
した後に Lock()
をすることになると思います。
func (m *UMutex) Upgrade() {
m.rwmu.RUnlock()
m.rwmu.Lock()
}
しかしこの時、別の goroutine が Lock()
をして既に取得されている Read Lock が解除されるのを待っているとすると、Upgrade()
の RUnlock()
でロックが横取りされてしまいます。ロックを横取りされないように実装する必要があります。順番は守りましょう。
2 つ目は、複数が同時に Upgrade() するとデッドロックしてしまう ということです。Upgrade()
は自身以外の全てが Read Lock を手放すまで待ち合わせます。しかし、複数が Upgrade()
するということはお互いに Read Lock を手放さないため Dead Lock してしまいます。
品質の低いプロダクトであるなら Dead Lock するようなクエリを発行するユーザの責任だとして、goroutine がリークしようがお構いなしなのかもしれませんが、使い勝手は非常に悪くなります。そのため、デッドロックする場合はタイムアウトや Dead Lock の検出をして自動で失敗させるなどの Developer Friendly な振る舞いをすることが望まれます。
実際のコード
実装はそんなに難しくなくて 51 行とシンプルです。 コミットログをたどるとわかりますが、ちょうど 1 時間で実装していました。(実装開始時の設計では順番抜かしがあることが発覚して途中で設計をやり直しているので時間がかかりました)
前述の注意する点ですが、
- Lock の横取り問題は
UMutex.u
の個数を確認して Upgrade 中であればロックを解放してリトライするようにして解決しました。 - デッドロック問題は、
UMutex.u
をアトミックに操作して同時に Upgrade している個数を管理して、既に Upgrade 待ちをしている場合はデッドロックを検出して Upgrade を失敗させることで解決しました。
短いので実際のコードも貼り付けておきます。参考までに。
package umutex import ( "sync" "sync/atomic" ) // UMutex is simple implementation of Upgradable RWMutex. type UMutex struct { rwmu sync.RWMutex u int32 } // RLock locks shared for multi reader. func (m *UMutex) RLock() { m.rwmu.RLock() } // RUnlock unlocks reader lock. func (m *UMutex) RUnlock() { m.rwmu.RUnlock() } // Lock locks exclusively for single writer. func (m *UMutex) Lock() { lock: m.rwmu.Lock() if atomic.LoadInt32(&m.u) > 0 { // Upgrade is given priority to Lock, retry lock. m.rwmu.Unlock() goto lock } } // Unlock unlocks writer lock. func (m *UMutex) Unlock() { m.rwmu.Unlock() } // Upgrade converts reader lock to writer lock and returns success (true) or dead-lock (false). // If Upgrade by multi reader locker at same time then dead-lock. // Upgrade is given priority to Lock. func (m *UMutex) Upgrade() bool { success := atomic.AddInt32(&m.u, 1) == 1 if success { m.rwmu.RUnlock() m.rwmu.Lock() } atomic.AddInt32(&m.u, -1) return success }
まとめ
これで昇格可能な Read Write Mutex の Go の実装ができました。次回はとうとうトランザクションを実装します。多分 Go 2 のアドベントカレンダー になると思いますが。
Go : Mutex は channel の 4 倍速い
速ければ速いほど良い。どうもかわしんです。トランザクションを実装中です。
トランザクションの並行処理で S2PL (Strict Two Phase Lock) を Go で実装しようとしているのですが、どうしても昇格可能な Reader Writer Mutex が必要になり、Github にいい実装がなかったので自分で実装しようとしています。
さて、独自の Mutex を実装するにあたり goroutine 同士の待ち合わせは何かを使って実現する必要がありますが、Go には sync.Mutex
とチャネルがあります。
どちらとも、ロックしてアンロックするということができます。振る舞いは同じです。
振る舞いが同じとなればどちらが速いかが重要となります。
ということで実験してみました。
実験
環境は以下の通りです。
- OS : macOS 10.14.6
- Hardware : Macbook Pro 13-inch 2018
- CPU : 2.7 GHz Intel Core i7, 4 core
- Go : 1.13.4
ベンチマークコード
以下を適当に main_test.go
としておきます。
package main import ( "sync" "testing" ) func BenchmarkMutex(b *testing.B) { var mu sync.Mutex var n int for i := 0; i < b.N; i++ { mu.Lock() n++ mu.Unlock() } } func BenchmarkChan(b *testing.B) { ch := make(chan struct{}, 1) var n int for i := 0; i < b.N; i++ { ch <- struct{}{} n++ <-ch } } func BenchmarkMultiMutex(b *testing.B) { var mu sync.Mutex var n int var wg sync.WaitGroup wg.Add(10) for j := 0; j < 10; j++ { go func() { for i := 0; i < b.N; i++ { mu.Lock() n++ mu.Unlock() } wg.Done() }() } wg.Wait() } func BenchmarkMultiChan(b *testing.B) { ch := make(chan struct{}, 1) var n int var wg sync.WaitGroup wg.Add(10) for j := 0; j < 10; j++ { go func() { for i := 0; i < b.N; i++ { ch <- struct{}{} n++ <-ch } wg.Done() }() } wg.Wait() }
BenchmarkMulti****()
は、10 の goroutine で同時に動かすものです。
結果
GOMAXPROCS=1
でおこなったものがこれです。
$ GOMAXPROCS=1 GO111MODULE=off go test -bench . goos: darwin goarch: amd64 BenchmarkMutex 100000000 10.4 ns/op BenchmarkChan 28564992 40.5 ns/op BenchmarkMultiMutex 9439315 126 ns/op BenchmarkMultiChan 1000000 1189 ns/op PASS ok _/Users/kawasin73/work/sample-go/rwlock 4.808s
普通のマルチスレッドでおこなったものがこれです。
$ GO111MODULE=off go test -bench . goos: darwin goarch: amd64 BenchmarkMutex-8 100000000 10.7 ns/op BenchmarkChan-8 27600146 42.3 ns/op BenchmarkMultiMutex-8 2536651 494 ns/op BenchmarkMultiChan-8 736453 1710 ns/op PASS ok _/Users/kawasin73/work/sample-go/rwlock 5.307s
まとめ
sync.Mutex
の方がチャネルよりだいたい 4 倍速いです。チャネルは内部でロックを取った上でごにょごにょやっているので遅いのは当たり前です。
また、シングルスレッドにするとスレッド同士の待ち合わせが無くなったりシングルスレッド用の最適化があるのかどうかはわかりませんが、速くなります。速くなるというよりは、マルチスレッドで動かすと遅くなるという表現の方が理解しやすそうですが。
シンプルな昇格可能な RWMutex
を作る分には sync.Mutex
を使う方向でできそうです。
ただ、タイムアウトをさせようとすると Go では必ずチャネルを使わないといけなくなりそうなのが残念です。
MySQL は Rigorous ではない
トランザクションは慎重に。どうも、かわしんです。今トランザクションを実装しています。
タイトルは釣りです。MySQL のデフォルトのトランザクション分離レベルである REPEATABLE READ
での話です。後、確かめた訳ではないですが MySQL に限った話ではないです。
さて、トランザクションの用語に Strictness (ST) と Rigorous (RG) というものがあります。詳しくはこの記事を読むとヒントになるかもしれません。
トランザクションの Strictness と Rigorousness の定義を再確認する - ぱと隊長日誌
これら2つの違いはあるトランザクションがあるレコードを Read した時に、Strictness は別のトランザクションでも そのレコードに Write できる のに対して、Rigorous は Read したトランザクションが Commit か Abort するまで Write がブロックされる かの違いです。Rigorous の方が Strictness よりも厳密です。
つまり 2PL の文脈でいえば、内部的に取得した Read Lock を Commit/Abort 前に解放するかどうかの違いになります。
今回はこれを実際の MySQL で試して確認し、実際のアプリケーションでのユースケースで気をつけるべきところを紹介します。
実験をしてみる
今回試したのは、MySQL 8.0.15 です。Docker で動かしています。
テーブルは以下の構造で、1つだけレコードを追加しています。
CREATE TABLE hoge ( id INT NOT NULL, value INT NOT NULL default 0, PRIMARY KEY (id) ); INSERT INTO hoge (id, value) VALUES (1, 1);
2 つのコネクションを作成しそれぞれでトランザクションを作って id = 1
のレコードの value
をカウントアップする実験をしていきます。
操作は全て mysql クライアントコマンドで行っています。
普通に値を更新して Rigorous でないことを確かめる
2 つのコネクションからそれぞれ以下の SQL を同時に1行ずつ実行します。
BEGIN; SELECT * FROM hoge WHERE id = 1; UPDATE hoge SET value = 2 WHERE id = 1; SELECT * FROM hoge WHERE id = 1; COMMIT;
片方で BEGIN
した後にもう片方で BEGIN
をして ... と行った具合です。
まず、両方のトランザクションで id = 1
の value
は 1 であるとわかります。
mysql> SELECT * FROM hoge WHERE id = 1; +----+-------+ | id | value | +----+-------+ | 1 | 1 | +----+-------+ 1 row in set (0.00 sec)
そこで両方のトランザクションでその値に 1
を加えた 2
を更新します。
mysql> UPDATE hoge SET value = 2 WHERE id = 1; Query OK, 1 row affected (0.00 sec) Rows matched: 1 Changed: 1 Warnings: 0 mysql> SELECT * FROM hoge WHERE id = 1; +----+-------+ | id | value | +----+-------+ | 1 | 2 | +----+-------+ 1 row in set (0.00 sec)
片方のトランザクションはこのように更新に成功します。少なくとも SELECT
したトランザクションがある中で UPDATE
が成功しているため、Rigorous ではない ということがわかります。
更新のブロッキングと奇妙な挙動
さて、片方のトランザクションですが、ブロックされレスポンスが返ってきません。
そして、更新に成功したトランザクションを COMMIT
するとブロックされたトランザクションが動き始めます。
mysql> UPDATE hoge SET value = 2 WHERE id = 1; Query OK, 0 rows affected (7.08 sec) Rows matched: 1 Changed: 0 Warnings: 0 mysql> SELECT * FROM hoge WHERE id = 1; +----+-------+ | id | value | +----+-------+ | 1 | 1 | +----+-------+ 1 row in set (0.00 sec)
しかし、値の更新に失敗 します。Changed: 0
となっていることからも更新に失敗していることがわかります。
ここで別の値(例えば 3
とか)に更新すると更新に成功します。
なぜ同じ値だと更新に失敗して違う値だと更新に成功するのかがよくわかりません 。両方成功していいはずです。
これはあくまでも僕の想像ですが、同じ値に更新するということは前の値に対して同じ相対的な操作(この場合はカウントアップ)を行っている可能性が高いです。そのため、意図せぬ競合状態によるデータの不整合が発生している可能性が高く、そのバグに利用者が気付きやすくするためにあえて更新を失敗させているのではないかと思いました。
もしカウントアップなどの相対的な操作ではなく、両方ともその値にするという絶対的な操作であった場合でも更新に失敗しても最終的な値はその値になっているため、データが壊れるということはなくデメリットは小さいです。
こういう利用者のミスに優しい MySQL の親切設計なのではないかと推察しました。
逆に、片方では +1
して片方では +2
するみたいなユースケースでは更新に失敗しないため注意が必要です。
正しくカウントアップを成功させる
SELECT
した値に操作をして UPDATE
しても更新に失敗することがわかりました。ではどうすれば正しく値のカウントアップができるのでしょうか?
方法は2つあります。
- ロックをとる
UPDATE
文を工夫する
1つは SELECT
するときに ロックをとる 方法です。MySQL では、SELECT
文の末尾に FOR UPDATE
をつけることでロックを取得できます。ロックを取得したトランザクションが Commit/Abort するまで別のトランザクションのロックはブロックされ、ロックを獲得できた時には更新された値を取得することができます。
SELECT * FROM hoge WHERE id = 1 FOR UPDATE;
もう1つは UPDATE
文を工夫する というものです。値の相対的な操作がカウントアップなど単純な場合は、value = value + 1
とすると相対的な操作がされて更新されます。
UPDATE hoge SET value = value + 1 WHERE id = 1;
別のトランザクションで更新された値に対して加算が行われるため、MySQL の REPEATABLE READ のトランザクション分離レベルであっても、以下のように 1
と SELECT
された値に 1
を足したら 3
になったみたいな一見直感に反する結果になります。
mysql> BEGIN; Query OK, 0 rows affected (0.00 sec) mysql> SELECT * FROM hoge WHERE id = 1; +----+-------+ | id | value | +----+-------+ | 1 | 1 | +----+-------+ 1 row in set (0.00 sec) mysql> UPDATE hoge SET value = value + 1 WHERE id = 1; Query OK, 1 row affected (1.16 sec) Rows matched: 1 Changed: 1 Warnings: 0 mysql> SELECT * FROM hoge WHERE id = 1; +----+-------+ | id | value | +----+-------+ | 1 | 3 | +----+-------+ 1 row in set (0.00 sec) mysql> COMMIT; Query OK, 0 rows affected (0.00 sec)
SERIALIZABLE ではどうなるか
MySQL は Rigorous ではないと大見得を切ってしまいましたが、MySQL でもトランザクション分離レベルを SERIALIZABLE
にすると Rigorous になります。
SET SESSION TRANSACTION ISOLATION LEVEL SERIALIZABLE;
2 つのトランザクションで SELECT
した上で UPDATE
するとブロックされて処理が返ってきません。
そのあとに両方のトランザクションで UPDATE
するとデッドロックしてしまいます。
mysql> UPDATE hoge SET value = 14 WHERE id = 1; ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction
SERIALIZABLE
は厳密にはなりますが速度が遅くなってしまうため大量の処理を捌くには向いていないです。
まとめ
MySQL の Rigorous の挙動を調べるために色々脱線しましたがまとめると以下のようになります。
- MySQL のデフォルトのトランザクション分離レベルである
REPEATABLE READ
では Rigorous ではない- ただし同じ値に対して同じ操作をしたと思われる場合は親切にも MySQL は更新を失敗させる
- 相対的な値の操作をする場合は
SELECT ~~ FOR UPDATE
してロックをとるか、UPDATE ~~ value = value = 1
と SQL 内に相対的な操作を記述する。 SERIALIZABLE
は Rigorous になるが遅いし、容易にデッドロックする
アプリケーションのユースケースとしては、ポイントの加算など値の相対的な操作をすることはよくあると思います。
その際は必ずロックを取るか SQL 内に相対的な操作を記述することでエラーのない整合性の取れたデータ更新ができるようになります。
WEBエンジニア勉強会 #15 で登壇しました
プログラマーあるある、なにかと独自のミニ言語を作りがち。どうも、かわしんです。
昨日、11 月 16 日に開催された WEBエンジニア勉強会 #15 の LT 10 分枠で「ネストした JSON を CSV に自動変換する Python ライブラリを作った」というタイトルで登壇してきました。
スライドは以下です。
ネストした JSON を CSV に自動変換する Pythonライブラリを作った - Google スライド
発表の内容自体は、以前の記事の中身をわかりやすく解説しました。
個人的には、この発表では Step 1 ~ 6 に分けて段階的に JSON から CSV へ変換する文法を育てていくところが見どころです。
他の方の発表では、javascript の HTTP クライアント axios を Typescript の世界で型安全にするために、規約づけされた型定義ファイルから axios ラッパーを生成するツール「aspida」が面白いなと思いました。
VS Code での補完が効くことで開発効率が上がりそうです。また、ただのツールにはとどまらず、型定義ファイルとそのラッパーを npm パッケージとして @aspida/<domain>
などのように公開することで Typescript での @types/<domain>
のような世界を作り上げる野望をぶち上げており、その世界観に感動しました。
発表スライドが公開されていないのが残念ですが(スライドを見ないとあの感動は伝わらないと思う)、Github リポジトリは以下です。某大手の内部で採用されているらしいので乗っかってみるのもいいと思います。
あと、独自のフルスクラッチ javascript View ライブラリ「Ma_gician(仮)」の発表も面白かったです。Yet Another Vue.js なのかなという印象を受けましたが、とにかくコーディング量を減らすための独自構文を HTML タグに埋め込むことで少量のコードで Vue.js と同じことができるらしいです。
また、他のライブラリからの乗り換えも最小限でコストでできるような工夫もされているらしく、ひしひしと野心を感じました。まだ、リリースはされておらず絶賛開発中で、正式名称やコードは公開されてませんが、今後に期待です。
作者の方 の記事を読むと、外部依存なし、パフォーマンスを妥協しないなど、僕の好きな感じだったので注目していきたいと思います。
最後に発表中のツイートを引用して筆をおきたいと思います。
4人目。「ネストした JSON を CSV に自動変換する Python ライブラリを作った」 #WEM15
— Motohashi Tsuyoshi (@t_mozza) 2019年11月15日
アリの飼育! 子供の頃やったなぁ〜 #WEM15
— OSCA (@engineer_osca) 2019年11月15日
つづいてかわしんさん。つよつよの学生さんだ…! #WEM15
— いわしまん@AWS入門中 (@iwasiman) 2019年11月15日
おっさんもそれなりにいる勉強会なのに、勇気出して大学生が登壇してくれてる、嬉しい、ありがたい。 #WEM15
— OSCA (@engineer_osca) 2019年11月15日
データサイエンス業界ではJSONよりCSVが好まれるそうです #WEM15
— Motohashi Tsuyoshi (@t_mozza) 2019年11月15日
csvとjsonの変換って汎用的なもの考えるとほんと難しいよね。。。 #WEM15
— the.arc (@arc_candy) 2019年11月15日
CSVはエンプラ開発だとよく出てきますw あーたしかに長さの違う配列のJSONは大変そう...😇 #WEM15
— いわしまん@AWS入門中 (@iwasiman) 2019年11月15日
長さの異なる配列を含むJSONは読み取る側が不便なので、配列を展開する #WEM15
— Motohashi Tsuyoshi (@t_mozza) 2019年11月15日
どんどん複雑化してきて見てて面白いww #WEM15
— the.arc (@arc_candy) 2019年11月15日
すごい、僕だったら「いやいや、データ構造違いすぎるから、無理にCSVにすんのやめましょう」とか言っちゃいそうw #WEM15
— OSCA (@engineer_osca) 2019年11月15日
複雑化しすぎて、CSV諦めてJSONつかいたくなる・・・
— ih6190@長岡 (@ihirhs) 2019年11月15日
これがJSONの良さですよとか言って#WEM15
長さの異なる配列を複数含むJSONは穴を空ける。
— Motohashi Tsuyoshi (@t_mozza) 2019年11月15日
ネストした長さの異なる配列を含むJSONはインデックス番号を付ける。
汎用的に対応するのって大変だなあ #WEM15
カンマ以外のセパレータを使って無理やり配列を詰め込みたくなるw #WEM15
— つの (@wasi_wasimaru) 2019年11月15日
csvを構造的なjsonに変換するのも辛いよなぁ
— the.arc (@arc_candy) 2019年11月15日
#WEM15
サンプルからメタデータ生成するの良いですね。DBスキーマを生成する仕組みもたまに見かけるし、こういうの開発者は欲してると思う #WEM15
— Motohashi Tsuyoshi (@t_mozza) 2019年11月15日
サンプルを食わせるとメタデータを生成してくれる関数も作ったという、実利的な仕組み紹介でした。 #WEM15
— いわしまん@AWS入門中 (@iwasiman) 2019年11月15日
JSON を CSV に変換する考え方が新鮮でした! アイディアのストックにします。あざっしたー
— 悉生 游漩 (@StewEucen) 2019年11月15日
メモリアロケーションに対する罪悪感
いつも心に省メモリ。どうも、かわしんです。今日はメモリアロケーションについてのポエムを綴ります。さらっと流してください。
ちなみに、ここでいう省メモリとはメモリサイズだけの話ではありません。
メモリをアロケート(確保)するとき、あなたはどんな感情を抱くだろうか?おそらく何も感じない人がほとんどだろう。というかメモリをアロケートしたことにすら気づいていないのかもしれない。
僕はメモリをアロケートするたびに心が痛む。本当はアロケートしなくてもいいのではないか、別のところでまとめてアロケートした方がいいのではないか?色々悩んだ結果、苦渋の選択としてメモリをアロケートするのだ。
メモリアロケーションのコストとは何か
僕がなんとなくメモリアロケーションに罪悪感を覚え始めた時、僕はメモリアロケーションのことを何も知らなかった。大きなメモリを確保するほどコスト(確保に必要な計算時間)が大きくなると思っていたし、不必要にメモリアロケーションを恐れていた。
メモリアロケーションを正しく恐れることができるようになったのは、malloc の仕組みを勉強した時だった。
ご存知のとおりメモリには 2 種類ある。スタック(stack)とヒープ(heap)だ。
まず、スタックのメモリ確保のコストはほぼない と言っていい。コンパイル時に関数ごとに確保されるサイズが確定し、関数が実行される時にスタックポインタの値をそのサイズだけずらすことでスタックメモリが確保される(スタック領域はアドレスの大きい方から小さい方に拡張されるのでスタックポインタは減算される)。実行時のコストはスタックポインタを減らす 1 命令だけだ。また、関数から抜ける時にスタックポインタが元に戻ることで自動的にスタック領域のメモリは解放される。
一方で、一般に(少なくとも僕のなかで)「メモリアロケーション」と呼ばれて恐れられるのは ヒープ領域の確保 だ。ヒープは実行時にサイズが決まるような構造のために利用される。実行前のコンパイル時にサイズが決まるのであればコストの小さなスタックやグローバル領域のメモリを使えばいい。自動で拡張される配列(vector)とかユーザからの接続のたびに確保されるコネクションコンテキストとか、文字列の操作のためにも使われたりする。
C 言語においてヒープ領域のメモリアロケーションは malloc
という関数によって行われる。他の言語でもおそらく似たような仕組みでアロケートされると思う。malloc
は指定されたサイズのメモリを確保して返すだけの関数だが、その実装は様々な種類があり有名なものだと tcmalloc
とか jemalloc
とか glibc の malloc
とかがある。1 それぞれマルチスレッド環境で速くしたりとか、より無駄になる領域が少なくなるようにとか、シンプルに速いだとか色々頑張っているらしい。が、どれも基本的な考え方は同じっぽい。
ここでは詳しくは説明しないので ガチャピン先生の malloc 動画 2 を観て勉強してほしい。すごくわかりやすくて面白い。ちなみにこの中で唐突に現れる「ご冗談でしょう、ファインマンさん」の元ネタを知らなかったので「ご冗談でしょう、ファインマンさん」という本を上下巻買って読んだが、理科と数学が好きな少年だった自分にはすごく刺さったのでこちらも是非読んでみてほしい。
さて、malloc の中では一般に大きなメモリに対しては mmap を使い、4KB までの小さなメモリについては 8, 16, 32, ... バイトとメモリサイズのクラスごとに free list がありそこに未使用のメモリがずらっと並んでいてその先頭のものを使用して返す。サイズクラスごとの free list の一覧は配列になっており、要求されるサイズから一撃でインデックス番号経由で引いてくることができるので速い。
つまり、大きすぎないメモリについては理論的にはアロケートするサイズによって計算時間は変わらない。多分。もしかしたらサイズによっては free list が枯渇しがちで余計なオーバーヘッドがあったりするのかもしれないけど、そこは勘弁してほしい。
これが malloc の中身を勉強して知った興味深い事実だった。 メモリアロケーションのコストとして気にすべきはサイズではなく回数 だったのだ。
メモリアロケーションに対する罪悪感の正体
メモリアロケーションの回数が多くなればプログラムは遅くなる。また、メモリアロケーションの回数が多いということは解放し忘れるバグによるリークの可能性も高くなる。さらにメモリアロケーションは失敗することがある。物理メモリが枯渇した時にはもちろん確保できない。メモリアロケーションに失敗した場合のエラーハンドリングを各所で行うことになり実装が肥大化する。
そう、メモリアロケーションにはデメリットしかない。それゆえに僕はメモリアロケーションに罪悪感を感じるのだ。
世の関数に告ぐ。勝手にメモリアロケーションするな、渡すから
僕は普段 Go をよく使うのだが、昔はこんな関数をよく作ってしまっていた。
func (item *Item) BuildMsg() []byte { buf := make([]byte, 100) // item を buf に書き込んでいく // ... return buf }
いい感じにオブジェクト指向で書いてやったぜ、ふふんとか思っていた。
これには 2 つ問題がある。1 つは複数のメッセージバイト列を結合する時に 無駄なメモリコピー が発生することだ。BuildMsg()
によって生成されたバイト列を結合先のバイト列にコピーする必要がある。多分、これだけではピンとこないと思うので、後述の正解例をみて比較してほしい。
2 つめは、複数回メッセージを生成する時に都度メモリアロケーションが発生することだ。定期的に item
の中身を書き換えてメッセージを書き出してハートビートを送るみたいなユースケースが考えられる。
ではどうすればいいのか。それはメモリは外部から渡して書き込んでもらうのだ。そうすれば全体でのメモリアロケーションはたったの 1 回で済む。また、メモリコピーも最小限で済む。
func (item *Item) BuildMsg(buf []byte) int { // item を buf に書き込んでいく // ... // 書き込んだサイズを返す return n } buf := make([]byte, 1024) // 複数回メッセージを送る時にバッファを使いまわしてアロケーションをしない for { // 複数のメッセージを結合する場合でもメモリコピーはメッセージを作成する 1 回だけ n := item1.BuildMsg(buf) nn := item2.BuildMsg(buf[n:]) n += nn conn.Write(buf[:n]) time.Sleep(time.Second) item1.id++ item2.id++ }
関数内でメモリをアロケートしてそれを返すという処理を書いているときは、一度立ち止まって外でメモリを確保して渡せないか考え直してみるといいかもしれない。
プログラミング言語によるメモリアロケーションへの態度の違い
よく使われる大抵の言語には GC (ガベージコレクション)が搭載されていることが多い。これは参照の消えたメモリを自動で解放してくれる便利な仕組みだが、同時に我々からメモリアロケーションの存在を見えにくくして、罪悪感を薄れさせている。そして無秩序にメモリをアロケートしてしまう。
C 言語ではメモリアロケーションをする時には必ず malloc()
関数を呼び出すため、プログラムを書く我々ははっきりとメモリアロケーションの存在を認識 する。
一方で GC のある言語では文法の裏にメモリアロケーションが隠蔽される。いろんなところでメモリを確保してどこかで紛失しても GC が後処理をしてくれるからメモリアロケーションを意識する必要はないのだ。しかし、GC のある言語でもメモリは確実にアロケートされている。そして、そのアロケーションには malloc()
と同様コストがかかっている。
Go は GC のある言語だが、C に似た言語であるためか少しはメモリアロケーションを意識できる。可変長配列(Go では slice という)の確保は make()
というビルトイン関数を使う。また構造体の確保では new()
というビルトイン関数を使うこともできる(僕はあまり使わないが)。これらの関数を使う時、我々はメモリアロケーションの存在をはっきりと認識することができる。実際は、構造体をポインタ化したり関数の外部に渡したりする場合はスタックに確保されそうな書き方でもヒープに確保されてしまうのだが、明示的にヒープに確保する文法があるというのはわかりやすくて良い 。
そんな Go 言語だが メモリの枯渇は全く考慮されていない 。malloc()
関数はメモリの確保に失敗した場合 NULL
を返す。しかし、Go の make()
はメモリの確保に失敗した場合例外を発生させプロセスは死ぬ。recover()
すればエラーハンドリングすることもできるが、メモリの枯渇は Go にとっては例外であり想定されるエラーではないのだ。メモリが安くなりじゃぶじゃぶ使えるようなこのご時世では、メモリ枯渇を心配するくらいなら金の力で解決しろということなのだろう。
Go はまだメモリアロケーションを意識できるが、大抵の GC 付きの言語はメモリアロケーションのコストを考慮しない。
例えばファイルの読み込みの場合、Go では n, err := file.Read(buf)
と外で確保したメモリを渡して書き込んでもらう。C 言語でも同様だ。しかし、Python や Ruby では file.read()
とすると関数内部で必要なサイズのメモリが確保されてバイト列が返される。勝手に関数の中でメモリアロケーションをする、そういう言語なのだ。そもそもアロケーションコストを意識するほど速い言語ではないからだと思えば妥当である。こういう言語ではメモリ管理のことなどは考えずに機能を実現することに主眼を置いてプログラミングするべきなのかもしれない。
メモリ管理とプログラミング言語と言ったら Rust のことも紹介しなくてはならない。が、ここで紹介するには分量が多いので、Rust の教科書 の「4.8. 所有権」「4.9. 参照と借用」「4.10. ライフタイム」を読むと Rust のメモリ管理を理解できると思う。個人的な感想としては、C++ に似てるなと思った。
プログラミング言語がせっかくメモリ管理を隠蔽してくれているのにわざわざメモリアロケーションのことを意識する必要はあるのか?と思われるかもしれない。そういうあなたにはこの記事を読んでほしい。要約すると「まともなプログラムを書くためには抽象化によって隠蔽された内部を知らざるを得ない」ということだ。
プログラムの目的とメモリアロケーション
世の中のプログラムには 2 種類あると思っている。
- やりたいことを実現させる( 振る舞いや機能が重視される )プログラム
- やりたいことを実現した上でより速く、効率的に、たくさんのユーザに対して動く( 性能が重視される )プログラム
この 2 つだ。
前者は、1回限りの書き捨てのスクリプトだったり、アクセスの少ない Web サービスやプロトタイプだったりする。
後者は大量のユーザに利用されるサービスであったり、シビアな環境で使われるアプリであったり、たくさんのエンジニアに利用されるライブラリやミドルウェア、OS などの低レイヤーであったりする。
この対比は去年書いた 作る人と使う人 - kawasin73のブログ に似ているような気もする。どちらが偉いとかそういうものではない。僕も両方とも書く。
前者ではメモリアロケーションなどの性能を気にすることはない。1 回しか使わないのだから最適化する実装コストに合わない。なんならメモリリークしてもいい。最適化で悩んでいる暇があったら次の仕事や機能に取り掛かる回転の速さが求められる。
後者ではメモリ設計が重要である。性能に直に響いてくる。メモリはまとめてアロケートするなどメモリアロケーションの回数を少なくするように設計をする必要がある。
問題は性能が重視されるプログラムであっても最初は機能が重視されて作られるということだ。早すぎる最適化は悪であり、最適化はいつも後でするべきだ。
しかし、いつどこでメモリをアロケートするかというメモリ設計はプログラムの根幹であり、後で変更するには困難を伴う。性能が重視される可能性のあるプログラムを書くときは 少なくとも最初に大雑把なメモリ設計をしてから雑に書き始める ということをしないと、後で痛い目にあうことになる。
どうメモリを設計するのか
メモリ設計とは、どこでメモリを確保して、どのコンポーネントがメモリを保持して、どこでメモリを解放するか を設計することである。
メモリ設計にはいくつかのパターンがあり、この「省メモリプログラミング」という本に詳しく書いてあるので見てみるといいかもしれない。
省メモリプログラミング―メモリ制限のあるシステムのためのソフトウェアパターン集 (Software patterns series)
この本の第 5 章「Memory Allocation:メモリ割り当て」では以下の 7 種類のメモリ設計方法が紹介されている。
- Fixed Allocation:固定アロケーション
- Variable Allocation:可変アロケーション
- Memory Discard:メモリの一括破棄
- Pooled Allocation:プールアロケーション
- Compaction:コンパクション
- Reference Counting:参照カウント
- Garbage Collection:ガベージコレクション
この章の要約は僕の Github issue にまとめてある。
まとめ
怪文書感満載なのは承知の上だが、これを読んで少しはメモリアロケーションに思いを馳せる人が増えれば幸いである。
本当にメモリを扱うためにはキャッシュのことも考えないといけないのはわかってはいるが、まだ僕はよく理解できていないので書いていない。そのうち勉強したい。
ネストした JSON を CSV に自動変換する Python ライブラリを作った
プログラマーあるある、なにかと独自のミニ言語を作りがち。どうも、かわしんです。どうしても簡潔にやりたいことを表現するためにミニ言語つくりがちですよね。JSON で構文作ると長いし。
さて、ACES Inc. という東大の松尾研究室発の AI ベンチャーがあるのですが、そこの創業者メンバーと学科の同期だったので最近お手伝いしながらアーキテクチャ設計をしたり Python をゴリゴリ書いたりしています。ちなみに僕はディープラーニングも機械学習もしてないです。
その中で推論結果が dict
と list
を組み合わせたデータ構造で返ってくるのですが、それを JSON と CSV の両方で保存したいという仕様がありました。JSON への変換は json.dumps()
を使えば一発なので自明ですが、CSV への変換は list
が含まれた時にそれをどのように展開するかが自明ではありません。
推論アルゴリズムはたくさんあってそれごとに CSV への変換コードを書くのは効率的でないので、CSV へ自動で変換するライブラリを実装しました。
特徴としては、以下のようなものが挙げられます。
例としては以下のような感じです。これで大体の使い方を感じ取ってください。
import io from nested_csv import NestedDictWriter data = [ {"hello": {"world": "value0"}, "list": [[1,2,3], [4,5,6]], "fixed": [1,2]}, {"hello": {"world": "value1"}, "list": [[7,8], [10,11]], "fixed": [3,4]}, ] fieldnames = ['hello.world', 'list[id]', 'list[][id]', 'list[][]', 'fixed[1]'] file = io.StringIO() w = NestedDictWriter(file, fieldnames) w.writeheader() w.writerows(data) file.seek(0) file.read() # hello.world,list[id],list[][id],list[][],fixed[1] # value0,0,0,1,2 # value0,0,1,2,2 # value0,0,2,3,2 # value0,1,0,4,2 # value0,1,1,5,2 # value0,1,2,6,2 # value1,0,0,7,4 # value1,0,1,8,4 # value1,1,0,10,4 # value1,1,1,11,4
既存のライブラリ
まず、Python には標準の csv パッケージがあります。csv パッケージには csv.writer
と csv.DictWriter
が用意されています。
csv — CSV File Reading and Writing — Python 3.8.0 documentation
csv.writer
は各行を writerow()
メソッドにデータのリストを渡すことで出力します。リストの各要素が各列の要素に対応します。
csv.DictWriter
は辞書のキーの一覧のリスト(fieldnames
)を渡して初期化し、各行を writerow()
メソッドにデータの辞書(dict
)を渡すことで出力します。各列の順序は初期化時に渡したキーのリストの順序になります。
しかし、残念ながら csv.DictWriter
はネストした辞書形式に対応していません。そこでネストしたデータ構造に対応しているものを Github で探すと、あるにはあるのですがネストした辞書をフラットな辞書に変換する程度のことしかしていなくて、辞書に含まれた リストの対応 が考慮されていません。
そこでネストした辞書にも辞書に含まれたリストにも対応する CSV 変換パッケージを作ることにしました。
nested_csv パッケージ
インターフェイスとしては、csv パッケージの csv.DictWriter
を踏襲して __init__()
writerow()
writerows()
writeheader()
を同じような引数体系にしました。ただし、csv.DictWriter
は継承するのではなく内部にインスタンスを持って利用し、ネストしたデータ構造をフラットな辞書形式に変換して csv.DictWriter.writerow()
に渡すという方針にしました。
一番の特徴としてはネストしたリストに対応するということです。ネストしたリストをどのように出力するかはかなり悩みましたが、 POSIX 原理主義過激派 の方が書かれた JSON をシェルスクリプトでパースする以下の記事の考え方を参考にして、SQL でいう OUTER JOIN
のような形で 1 つのデータを複数行に展開 するようにしました。
jq、xmllintコマンドさようなら。俺はパイプが好きだから - Qiita
リストを扱うために、[]
と [id]
と [<number>]
の 3 つの文法を導入しました。詳しい文法の中身は後述します。
また、データの型をリスト fieldnames
にして初期化するわけですが、いちいちこの fieldnames
を自分の手で設定するのは面倒臭いです。ここは自動化できるため generate_fieldnames()
という関数を用意して実際のデータを 1 つ渡すと構造を解析して自動で fieldnames
を生成するようにしました。
あと、Python 3.5
3.6
3.7
で正しく動くことを確認しています。また、全て標準パッケージ で実装されているので余計なライブラリのインストールは必要ありません。
fieldnames の記法
generate_fieldnames()
を利用すれば自動で fieldnames
を生成できますが、以下の2つの場合には CSV への変換フォーマットを設定する必要があります。
これらに当てはまる時は、fieldnames
となる文字列のリストを指定する必要があります。その記法は以下の通りです。
オブジェクトのキー
- オブジェクトの各キーは、
.
(ドット)区切りで指定する
JSON : {"a": {"b": 1, "c": 2}} fieldnames : ["a.b", "a.c"] --- CSV --- 1,2
要素数の固定された配列
- 要素数の固定された配列は、
[<index>]
で指定する
JSON : {"a": [1,2], "b": [0]} fieldnames : ["a[0]", "a[1]", "b[0]"] --- CSV --- 1,2,0
要素数の不定な配列
- 要素数の不定な配列は、
[]
で指定する[]
の配列の要素は CSV での複数の行に展開されて表示される- 1 つのフィールドに複数の
[]
を指定することもでき、その場合はそれぞれの全ての組み合わせが CSV の行に展開される - 複数のフィールド間で配列の位置の整合性を取る必要がある。以下の例はエラーになる
"a[]"
+"a.b"
: 配列表現とキー表現で不整合"a[]"
+"b.c[]"
: 配列が異なる階層にある場合(CSV への展開が論理的にできないため)"a[][]"
+"b[].c[]"
: 配列が異なる階層にある場合(全ての配列が同じ階層である必要がある)
- 異なるフィールドで同じ階層に配列がある場合は、それらのフィールドの中で最長の配列の長さの回数 CSV に展開される。その際短い配列の中身は `` (空文字)として出力される
JSON : {"a": [[{"x": 1}], [{"x": 2}, {"x": 3}]], "b": [4, 5, 6], "c": [[7, 8, 9]]} fieldnames : ["a[][].x", "b[]", "c[][]"] --- csv --- 1,4,7 ,4,8 ,4,9 2,5, 3,5, ,5, ,6, ,6, ,6,
要素数の不定な配列のインデックス番号
[]
で指定した配列の順序を[id]
で出力することができる- ただし、前項の
[]
で登録されていない配列に対する[id]
を指定することはできない - また、前項の
[]
と整合性の取れない[id]
を指定することはできない
- ただし、前項の
JSON: {"a": [[1,2,3], [4,5]} fieldnames : ["a[id]", "a[][id]", "a[][]"] --- csv --- 0,0,1 0,1,2 0,2,3 1,0,4 1,1,5 1,2,
工夫した点
工夫した点は 3 点あります。
1 点目は、内部での型情報の構造の持ち方です。fieldnames
はインスタンスの初期化時にコンパイルされて、構造の整合性のチェックを行った上で writerow()
で参照しやすいような形に変換されます。これによって複数回呼ばれる writerow()
で素早く CSV を出力できるようにしています。
そのためにリストのためのデータ構造が 摩訶不思議なもの になってしまいました。全部タプルとリストでデータ構造を作ったからで適切な名前をつければマシになるとは思いますが、辞書とかクラスとかはなんかパフォーマンスが悪くなりそうなので使ってません。
2 点目は、複数ネストしたリストの展開です。リストが何段ネストするかはわからないため、可変の深さの for 文を実装する必要があります。これ、スタックとか使って自力で実装するのめんどくさいなと思ってましたが、Python には itertools.product
という便利な Util 関数があり、これを使って実現できました。
3 点目は、必要のない展開処理をスキップするようにしたことです。可変長のリストが含まれる場合は、シンプルな辞書の値は複数行に渡って同じものが出力されます。また、ネストしたリストを出力する場合も深いリストを出力している間は浅いリストの値は変わりません。そのため、複数の出力行に渡って 値のキャッシュ current
を持っておき、更新するリストの値だけを変更して無駄な代入をスキップするようにしました。
最後に
機械学習の分野では依然として CSV ファイルでの出力が好まれる現場があるそうです。複雑な構造の JSON から CSV に変換するのって結構悩みがちですが、このパッケージを使えば楽に自動で変換することができるので、ぜひ使っていただきたいです。
また、将来への TODO として、CSV を読み取る NestedDictReader
も作れればいいかなという野望もあります。
以前 Twilter を作った時も独自のフィルター言語を策定して実装しましたが、こういう単一目的に特化した小さな文法って結構便利なんですよね・・・。
Twitter をフィルタリングする Twilter を作った - kawasin73のブログ
現場からは以上です。
GitHub Actions Meetup Tokyo β で登壇しました。
先頭を 駆くる者には 落とし穴 ハマっては埋め ハマっては埋め
どうも、かわしんです。昨日サイボウズ株式会社で開催された「GitHub Actions Meetup Tokyo β」という非公式の Github Actions の勉強会で LT をしてきました。
発表スライドはこれです。
内容としては Github Actions のダメなところをディスるというものでしたが、会場に到着すると非公式のイベントなのに Github の中の人がいらっしゃっるというアクシデントがあり、平謝りしながら発表をすることになりました。
発表した内容は以前のこの記事の内容です。
Github Actions の一番のセキュリティ的な問題点として、バージョンを Git タグで指定しているため 3rd Party の Action が差し替えられる危険性があることを指摘しましたが、フィードバックでコミットハッシュを指定すれば差し替えられることはないということを聞きました。確かにその通りなので、fork せずにコミットハッシュを直に設定することでしのいでいこうと思います。
また、初めての試みとして一首詠んでから LT を始め、最後に一首詠んで締めてみましたがなかなかウケが良かったのがよかったです。
最後に発表中のツイートを引用して筆をおきたいと思います。
いきなり一句詠む大学生がきた #githubactions
— miyata (@miyajan) 2019年10月16日
感極まって一首 #githubactions
— 戸田広 (@hiroshitoda) 2019年10月16日
disがくるぞ...!! #githubactions
— 戸田広 (@hiroshitoda) 2019年10月16日
npmはsecretsで.npmrcに入れるだけだからGithubActionsでも問題なく出来る#GithubActions
— Naturalclar(Jesse K.) (@natural_clar) 2019年10月16日
アクションの差し替え問題は commit SHA 指定すれば安全なんじゃないかな。タグやブランチ指定は危険という認識。 #githubactions
— miyata (@miyajan) 2019年10月16日
3rd party の GitHub Action は僕は怖くて使えないなぁ(GitHub API が自由に使えてしまうので) #githubactions
— ドッグ (@Linda_pp) 2019年10月16日
面白そう #githubactions #エア参加
— ぱいん🍍 (@pineapplecandy) 2019年10月16日
3rd party actionはforkして自前のリポジトリにしよう #githubactions
— 戸田広 (@hiroshitoda) 2019年10月16日
そうね。なので3rd Party Actionは基本的にバージョン番号じゃなくてコミットハッシュ値指定で使うのがよさそう。 #githubactions
— Hideki Igarashi (@ganta0087) 2019年10月16日
サードパーティの扱い、むずかC#githubactions
— Shoma Okamoto (@shmokmt) 2019年10月16日
セマンティクスバージョニングは publish する側ががんばらないといけないのめんどいですよね。よいアクションができて定型化されると嬉しい。 #githubactions
— miyata (@miyajan) 2019年10月16日
jobs.<job_id>.services は実行コマンドを注入できない、設定ファイルの注入もできない、何か細かいことやりたければ継承したDockerイメージを独自に作って使おう #githubactions
— 戸田広 (@hiroshitoda) 2019年10月16日
serviceにDockerfile指定できないのかな #githubactions
— Shinya Sakemoto @技術書典7(い17C) (@sakebook) 2019年10月16日
ここで一句よすぎる #githubactions
— はやぶさ (@haya14busa) 2019年10月16日
一句詠むのが素敵w #githubactions
— Hideki Igarashi (@ganta0087) 2019年10月16日
Docker hubに公開するところは、こちらもまだβですがGithub Package Registryを使えばGithubの中だけ完結できそう #githubactions
— Kenta.Kase (@Kesin11) 2019年10月16日