kawasin73のブログ

技術記事とかいろんなことをかくブログです

Go で昇格可能な RWMutex を実装した

Go Database 作ったもの

順番は守りましょう。どうも、かわしんです。トランザクションを実装中です。

さて、先日トランザクションの並行制御アルゴリズムである「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 を探しても使えそうなライブラリはなかったので自作しました。

github.com

今回はこのライブラリの紹介です。

欲しかったもの

欲しかった機能は以下の通りです。

既存のライブラリ

一応 Go におけるロックの実装を調べたので、既存のライブラリがなぜ使えなかったのかを列挙していきます。

世の中に必要なコンポーネントがないからと、プロダクトを作るのを諦めたり、仕様を捻じ曲げたりするのは嫌いなので、自作しました。

実装

ロックの仕組みと実装方法

Go でのロックの仕組みはこの動画がわかりやすいです。

www.youtube.com

Mutex は以下の 2 段階に分けてロックが取られています。

  1. アトミックな操作による spin lock
  2. 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 のアドベントカレンダー になると思いますが。

  1. Support S2PL concurrency control · kawasin73/txngo@e0e41a0 · GitHub↩

  2. txngo/main.go at e0e41a015ffb532572888755bdefcc310a709aa9 · kawasin73/txngo · GitHub↩

  3. Go : Mutex は channel の 4 倍速い - kawasin73のブログ↩

Go : Mutex は channel の 4 倍速い

Go

速ければ速いほど良い。どうもかわしんです。トランザクションを実装中です。

トランザクションの並行処理で S2PL (Strict Two Phase Lock) を Go で実装しようとしているのですが、どうしても昇格可能な Reader Writer Mutex が必要になり、Github にいい実装がなかったので自分で実装しようとしています。

さて、独自の Mutex を実装するにあたり goroutine 同士の待ち合わせは何かを使って実現する必要がありますが、Go には sync.Mutex とチャネルがあります。

どちらとも、ロックしてアンロックするということができます。振る舞いは同じです。

振る舞いが同じとなればどちらが速いかが重要となります。

ということで実験してみました。

実験

環境は以下の通りです。

ベンチマークコード

以下を適当に 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 ではない

Database

トランザクションは慎重に。どうも、かわしんです。今トランザクションを実装しています。

タイトルは釣りです。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 を同時に１行ずつ実行します。

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 文を工夫する

１つは 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 で登壇しました

参加記 Python

プログラマーあるある、なにかと独自のミニ言語を作りがち。どうも、かわしんです。

昨日、11 月 16 日に開催された WEBエンジニア勉強会 #15 の LT 10 分枠で「ネストした JSON を CSV に自動変換する Python ライブラリを作った」というタイトルで登壇してきました。

スライドは以下です。

ネストした JSON を CSV に自動変換する Pythonライブラリを作った - Google スライド

発表の内容自体は、以前の記事の中身をわかりやすく解説しました。

kawasin73.hatenablog.com

個人的には、この発表では Step 1 ~ 6 に分けて段階的に JSON から CSV へ変換する文法を育てていくところが見どころです。

他の方の発表では、javascript の HTTP クライアント axios を Typescript の世界で型安全にするために、規約づけされた型定義ファイルから axios ラッパーを生成するツール「aspida」が面白いなと思いました。

VS Code での補完が効くことで開発効率が上がりそうです。また、ただのツールにはとどまらず、型定義ファイルとそのラッパーを npm パッケージとして @aspida/<domain> などのように公開することで Typescript での @types/<domain> のような世界を作り上げる野望をぶち上げており、その世界観に感動しました。

発表スライドが公開されていないのが残念ですが（スライドを見ないとあの感動は伝わらないと思う）、Github リポジトリは以下です。某大手の内部で採用されているらしいので乗っかってみるのもいいと思います。

github.com

あと、独自のフルスクラッチ javascript View ライブラリ「Ma_gician（仮）」の発表も面白かったです。Yet Another Vue.js なのかなという印象を受けましたが、とにかくコーディング量を減らすための独自構文を HTML タグに埋め込むことで少量のコードで Vue.js と同じことができるらしいです。

また、他のライブラリからの乗り換えも最小限でコストでできるような工夫もされているらしく、ひしひしと野心を感じました。まだ、リリースはされておらず絶賛開発中で、正式名称やコードは公開されてませんが、今後に期待です。

作者の方 の記事を読むと、外部依存なし、パフォーマンスを妥協しないなど、僕の好きな感じだったので注目していきたいと思います。

docs.google.com

最後に発表中のツイートを引用して筆をおきたいと思います。

メモリアロケーションに対する罪悪感

ポエム Go Python

いつも心に省メモリ。どうも、かわしんです。今日はメモリアロケーションについてのポエムを綴ります。さらっと流してください。

ちなみに、ここでいう省メモリとはメモリサイズだけの話ではありません。

メモリをアロケート（確保）するとき、あなたはどんな感情を抱くだろうか？おそらく何も感じない人がほとんどだろう。というかメモリをアロケートしたことにすら気づいていないのかもしれない。

僕はメモリをアロケートするたびに心が痛む。本当はアロケートしなくてもいいのではないか、別のところでまとめてアロケートした方がいいのではないか？色々悩んだ結果、苦渋の選択としてメモリをアロケートするのだ。

メモリアロケーションのコストとは何か

僕がなんとなくメモリアロケーションに罪悪感を覚え始めた時、僕はメモリアロケーションのことを何も知らなかった。大きなメモリを確保するほどコスト（確保に必要な計算時間）が大きくなると思っていたし、不必要にメモリアロケーションを恐れていた。

メモリアロケーションを正しく恐れることができるようになったのは、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++ に似てるなと思った。

プログラミング言語がせっかくメモリ管理を隠蔽してくれているのにわざわざメモリアロケーションのことを意識する必要はあるのか？と思われるかもしれない。そういうあなたにはこの記事を読んでほしい。要約すると「まともなプログラムを書くためには抽象化によって隠蔽された内部を知らざるを得ない」ということだ。

www.joelonsoftware.com

プログラムの目的とメモリアロケーション

世の中のプログラムには 2 種類あると思っている。

  • やりたいことを実現させる（ 振る舞いや機能が重視される ）プログラム
  • やりたいことを実現した上でより速く、効率的に、たくさんのユーザに対して動く（ 性能が重視される ）プログラム

この 2 つだ。

前者は、1回限りの書き捨てのスクリプトだったり、アクセスの少ない Web サービスやプロトタイプだったりする。

後者は大量のユーザに利用されるサービスであったり、シビアな環境で使われるアプリであったり、たくさんのエンジニアに利用されるライブラリやミドルウェア、OS などの低レイヤーであったりする。

この対比は去年書いた 作る人と使う人 - kawasin73のブログ に似ているような気もする。どちらが偉いとかそういうものではない。僕も両方とも書く。

前者ではメモリアロケーションなどの性能を気にすることはない。1 回しか使わないのだから最適化する実装コストに合わない。なんならメモリリークしてもいい。最適化で悩んでいる暇があったら次の仕事や機能に取り掛かる回転の速さが求められる。

後者ではメモリ設計が重要である。性能に直に響いてくる。メモリはまとめてアロケートするなどメモリアロケーションの回数を少なくするように設計をする必要がある。

問題は性能が重視されるプログラムであっても最初は機能が重視されて作られるということだ。早すぎる最適化は悪であり、最適化はいつも後でするべきだ。

しかし、いつどこでメモリをアロケートするかというメモリ設計はプログラムの根幹であり、後で変更するには困難を伴う。性能が重視される可能性のあるプログラムを書くときは 少なくとも最初に大雑把なメモリ設計をしてから雑に書き始める ということをしないと、後で痛い目にあうことになる。

どうメモリを設計するのか

メモリ設計とは、どこでメモリを確保して、どのコンポーネントがメモリを保持して、どこでメモリを解放するか を設計することである。

メモリ設計にはいくつかのパターンがあり、この「省メモリプログラミング」という本に詳しく書いてあるので見てみるといいかもしれない。

省メモリプログラミング―メモリ制限のあるシステムのためのソフトウェアパターン集 (Software patterns series)

この本の第 5 章「Memory Allocation：メモリ割り当て」では以下の 7 種類のメモリ設計方法が紹介されている。

この章の要約は僕の Github issue にまとめてある。

まとめ

怪文書感満載なのは承知の上だが、これを読んで少しはメモリアロケーションに思いを馳せる人が増えれば幸いである。

本当にメモリを扱うためにはキャッシュのことも考えないといけないのはわかってはいるが、まだ僕はよく理解できていないので書いていない。そのうち勉強したい。

  1. 昔調べた調査結果 メモリアロケーションにおけるフラグメンテーションへの対策 · Issue #14 · kawasin73/knowledge · GitHub↩

  2. スライドは Glibc malloc internal↩

ネストした JSON を CSV に自動変換する Python ライブラリを作った

作ったもの Python

プログラマーあるある、なにかと独自のミニ言語を作りがち。どうも、かわしんです。どうしても簡潔にやりたいことを表現するためにミニ言語つくりがちですよね。JSON で構文作ると長いし。

さて、ACES Inc. という東大の松尾研究室発の AI ベンチャーがあるのですが、そこの創業者メンバーと学科の同期だったので最近お手伝いしながらアーキテクチャ設計をしたり Python をゴリゴリ書いたりしています。ちなみに僕はディープラーニングも機械学習もしてないです。

その中で推論結果が dict と list を組み合わせたデータ構造で返ってくるのですが、それを JSON と CSV の両方で保存したいという仕様がありました。JSON への変換は json.dumps() を使えば一発なので自明ですが、CSV への変換は list が含まれた時にそれをどのように展開するかが自明ではありません。

推論アルゴリズムはたくさんあってそれごとに CSV への変換コードを書くのは効率的でないので、CSV へ自動で変換するライブラリを実装しました。

github.com

特徴としては、以下のようなものが挙げられます。

  • 配列を CSV の複数行に展開する
  • 展開された配列のインデックス番号の出力に対応
  • データ構造を解析して CSV の列情報 fieldnames を自動で生成

例としては以下のような感じです。これで大体の使い方を感じ取ってください。

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 パッケージ

github.com

インターフェイスとしては、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 への変換フォーマットを設定する必要があります。

  • 推論結果に配列が含まれる場合
    • 配列の要素数 0 要素の時に自動型生成がされない
  • 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 をしてきました。

gaugt.connpass.com

発表スライドはこれです。

内容としては Github Actions のダメなところをディスるというものでしたが、会場に到着すると非公式のイベントなのに Github の中の人がいらっしゃっるというアクシデントがあり、平謝りしながら発表をすることになりました。

発表した内容は以前のこの記事の内容です。

kawasin73.hatenablog.com

Github Actions の一番のセキュリティ的な問題点として、バージョンを Git タグで指定しているため 3rd Party の Action が差し替えられる危険性があることを指摘しましたが、フィードバックでコミットハッシュを指定すれば差し替えられることはないということを聞きました。確かにその通りなので、fork せずにコミットハッシュを直に設定することでしのいでいこうと思います。

また、初めての試みとして一首詠んでから LT を始め、最後に一首詠んで締めてみましたがなかなかウケが良かったのがよかったです。

最後に発表中のツイートを引用して筆をおきたいと思います。