kawasin73のブログ

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

golang.tokyo #28 で登壇して賞品をいただきました

Go 参加記

限りある時間を大切に。どうも、かわしんです。情報洪水の現世をスマートに生きていきましょう。

さて、去る 12 月 4 日に開催された 「golang.tokyo #28 ~年末だよ！Go大忘年会&LT大会！~」 で LT をしてきました。

golangtokyo.connpass.com

発表資料はこれです。

半年前に作った Twilter の話で、なぜ作ったのかと工夫したフィルターの仕組みについて解説しました。

内容としては以前の記事の内容を濃縮した感じです。

kawasin73.hatenablog.com

この LT 大会では最後に参加者全員で投票してよかった LT を決める時間があり、その中で第4位に選んでいただきました。

1位から賞品を選んでいったのですが、僕が一番欲しかった「Go 言語による並行処理」のオライリー本をいただくことができました。ありがとうございます。

f:id:kawasin73:20191214161253j:plain

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

Go でトランザクションをフルスクラッチで実装した

Go Database 作ったもの

一歩ずつ一歩ずつ前へ進んでいく、確実に。どうも、かわしんです。

到底 1 記事に収まるような内容ではなく長いので、トランザクションの作り方に興味のない方は途中の「なぜ Go なのか」まで読んでいただければ嬉しいです。

この記事は、Go2 Advent Calendar 2019 の 7 日目と セキュリティキャンプ 修了生進捗 #seccamp OB/OG Advent Calendar 2019 の 7 日目を兼用しています。

さて、僕の興味は必要になったライブラリやミドルウェアなどを自作して、作りたいプロダクトを完成させることです。必要なコンポーネントがないからといってプロダクトを作るのを諦めたり妥協したりはしたくありません。

多くのアプリケーションではデータベースは重要なコンポーネントです。大抵のアプリケーションは MySQL や Postgres、Redis など既存のデータベースシステムで対応することができますが、既存のデータベースシステムでは対応できないような場合に備えてデータベースシステムを作れる力をつけておきたいと思っていました。

そこで、今回はデータベースシステムを作る前哨戦として トランザクション を実装します。出来上がったものはこちらです。

github.com

僕は、今年の セキュリティ・ネクストキャンプ に参加したのですが、同時開催されていたセキュリティキャンプのデータベースゼミの講師である 星野さん にお願いして講座で利用された教科書をいただき、キャンプが終わってからその教科書を参考に設計と実装を行いました。

どんなトランザクションを作るのか

トランザクションとは ACID を満たして複数のデータの書き込みや読み込みをできるようにする仕組みだと僕は認識しています。

ACID は、A (Atomicity : 不可分性)、C (Consistency : 一貫性) 、I (Isolation : 独立性)、D (Durability : 永続性) ですね。

ここでは詳しくは説明しないので、以下の資料を読むといいかと思います。

qiita.com

マジモンのトランザクションをガチ実装するのは初心者の僕には大変なので、実装しやすいように色々制約をつけたトランザクションを作ります。

  • KVS (Key Value Store) にする
    • シンプルな操作 INSERT UPDATE READ DELETE COMMIT ABORT の操作だけに対応します。SQL などはありません。
  • 範囲検索はしない
    • インデックスの実装をサボるために範囲検索はスコープ外としています。（あと、S2PL でも助けられます）
  • インメモリデータベースとする
    • 全てのデータはメモリに載る前提です。それより大きなデータには対応しません。
    • Buffer Pool などをサボることができます。(あと、undo ログをサポートしなくてもよくなります)
  • non-deterministic DBMS を想定します
    • deterministic DBMS とはあらかじめトランザクションの処理内容がわかっているものです。例えばストアドプロシージャとかでしょうか。
    • 逆に non-deterministic ではトランザクション内で次にどの処理命令がくるかがわかりません。いつ COMMIT されるのか ABORT されるのかもわかりません。普通はこちらが使われてると思います。
    • non-deterministic DBMS ではトランザクションは ACID の I を担保するために頑張る必要があります。
  • WAL を使う
    • Write Ahead Log の略です。データベースに対する何らかの更新（Write）を行う前にその操作の内容をログとして追記し、更新が反映する途中でプロセスが死んだ場合でもその更新を再開したりロールバックできるようにして、ACID の A と D を実現するための仕組みです。
    • ログは COMMIT ログが永続化された変更は永続化されたとして確定し、プロセスが死んで再開された後に復旧されます（Crash Recovery）。
    • COMMIT ログが永続化される前にプロセスが死んだ場合は WAL ログに書かれた更新の内容は失敗したとして破棄されたり書き戻されたりします。
    • つまり、WAL に COMMIT ログが書かれて初めてクライアントにトランザクションの更新が成功したと返信することができます。
    • 参考 : バッファ管理とWAL - Qiita
    • ログには undo ログと redo ログの 2 種類がありますが、今回は redo ログのみを使います。
  • チェックポイントの作成は起動時と終了時のみ
    • トランザクションが動いているときにチェックポイントを書き出すのはややこしいので今回はサボります。
    • プロセスの終了が遅くなってしまいますが許容します。

このような制約がありつつも、マルチスレッドで ACID を守って正しく動くトランザクションを作ります。

どうやってトランザクションを作るのか

何を作る時でも同じですが、「まず遅くてもいいから正しく動くものを愚直に作り、それに最適化を施すことによって効率的に速く動くようにしていく」 という作り方が鉄則です。

今回は以下の３ステップに分けて実装していきます。

Step 1 は、Trivial Scheduler と呼ぶそうです。同時に1つのトランザクションしか動かないので排他制御も必要ありません。ただ、愚直に実装するのみです。ただし、今後はこの実装に積み重ねていくのでインターフェイスなどはちゃんと考えて、正しく振る舞うように実装します。

Step 2 では、複数のトランザクションが同時に動くので 並行制御 をする必要があります。並行制御アルゴリズムには様々なものがありますが、初心者向けとして S2PL (Strict Two Phase Lock) が教科書で勧められていたのでこれを採用します。

Step 3 では、Step 2 の実装をマルチスレッドで動くようにします。インデックスやデータストアや WAL などは同時にアクセスによるデータ競合を防ぐために 排他制御 をする必要が出てきます。

なぜ Go なのか

今回は Go で実装していくわけですが、その一番大きな理由は goroutine の存在です。

Step 2 の並行制御をするためには並行スケジューラが必要になります。しかし、goroutine は I/O と自動で連携したコルーチンであり、Go のランタイムに並行スケジューラが実装されているため、Go を使うことでこのトランザクションの中で一番大変と思われる 並行スケジューラの実装をサボる ことができるのです。

むしろ、並行スケジューラを実装しないでトランザクションの実装を勉強したと言えるのかどうか怪しいところではありますが、それは C や C++ で実装するときにやるので勘弁して欲しいです。今回はトランザクションの概観をざっくり知るために作っているので。

また、Step 3 でマルチスレッド化するわけですが、goroutine ベースで作るとランタイムが 自動でスレッド間で適切に分散してスケジューリング してくれます。正直あっけないくらい簡単にマルチスレッド対応できてしまいました。

また、Go はミドルウェアなどを プロトタイピングするのに向いている言語 だと思っています。

goroutine もそうですが、map やスライスなど必要なコンポーネントが言語自体や標準ライブラリに含まれていますし、GC がついているので雑にメモリを確保することができます。また、バイト列が []byte として柔軟に扱える上に、多くのインターフェイスで []byte を利用することが想定されている (io.Reader など) ため、ファイル操作やバイナリ処理をするようなミドルウェアの開発に向いています。さらに、そこそこ速いため速さを求められないようなプロダクトではそのままプロダクションで使えてしまいます。

トランザクションを作っていく！

ここでは順を追ってどうやって実装していったかを紹介していきます。全て main.go の１ファイルに収まる 1000 行に満たない小さな実装なので、ぜひコードを読んでみてください。それぞれのステップでブランチがきられています。

Step 1 : シングルスレッドで同時に１トランザクションのみが動く

GitHub - kawasin73/txngo at trivial_scheduler

まず Go で シングルスレッド を実現しなくてはなりません。Go は M:N 方式 (1, 2) で動くため厳密にシングルスレッドでは動きません。しかし、goroutine を実行する主体である processor を 1 つだけに限定すればシングルスレッドと同じように 1 つの goroutine のみが同時に動き、データ競合も発生しません。

// execute on single thread
runtime.GOMAXPROCS(1)

トランザクションは同時に1つしか動かないため入出力インターフェイスも1つだけで十分です。そこで、標準入出力 を使ってターミナルから柔軟にクエリを流し込めるようにしました。

さて、トランザクションは以下のような構成で実現しています。

f:id:kawasin73:20191206180322p:plain

起動時に CheckPoint ファイルから永続化されている 全てのデータが DB に読み込まれ ます。DB は map[string]Record で表されたハッシュマップで、キーからレコードを高速に引いてくることができ、インデックスの役割も兼ねています。

トランザクションの更新した変更は途中で ABORT されて変更が全て破棄される可能性があります。もし COMMIT される前に更新内容を DB に反映していた場合はその内容を元に戻す必要があります。さらに、今後複数トランザクションを同時に動かす時には、MVCC などを導入しないと確定していないデータを他のトランザクションに読まれてしまうダーティリードになってしまいます。

この課題を解決するために トランザクションの更新した変更は Write Set に保存して、COMMIT された後に DB に書き戻す ようにします。

更新処理の中で以下のように key を処理しているのを不思議に思うかもしれません。これは引数で渡された文字列 key が別の文字列の一部であった時、key が DB に保存されることで元の文字列が GC されなくなってしまうことを防ぐためです。明示的に key 文字列のメモリを確保し直して、外部のメモリへの参照を発生させないようにしています。

// reallocate string
key = string(key)

READ ではトランザクション内での変更結果を読む必要があるため、まず Write Set を検査して、なかった場合に初めて DB を読みにいくようにします。READ での検索を高速にするために Write Set は map[string]RecordCache で表されたハッシュマップで実現します。レコードが削除された場合でも DB にはレコードはあるので Write Set に削除されたフラグを持った RecordCache を保持します。

COMMIT 時にトランザクションでの 更新履歴を全てログとして一度に WAL に書き出し ます。本当は更新時に逐一 WAL に書き出して COMMIT 時には COMMIT ログだけを永続化することが望ましいのですが、次のステップで複数のトランザクションから同時に WAL に更新ログを書き込むとログの順序が割り込まれてしまうため、一度に書き出すようにしました。（トランザクション ID を使えば解決しますが、ID の払い出しを考えたくなかったのでこの方法にしています。また、ABORT される内容を WAL に書かないのでちょっと効率的かなとか思ってます）

また、Write Set のハッシュマップでは更新した順番がわからないため、ログの履歴を保持するスライス Logs ([]RecordLog) を用意し、その内容を WAL に書き出します。

ABORT するときは、Write Set の中身と Logs をクリアするだけでトランザクションの変更内容は全て破棄されます。

プロセスの終了時に DB に保存された内容を全て CheckPoint ファイルに書き出します。しかし、ファイルの上書き中にプロセスが突然死すると元々の CheckPoint ファイルの内容が壊れてしまいます。そこで一時ファイルに内容を書き出した後に os.Rename() してアトミックにファイルを差し替えて CheckPoint ファイルを更新します。上書きされたファイルの内容は自動で削除されます。

CheckPoint ファイルへの書き出しが永続化されたら WAL ファイルの内容は全て必要なくなります。（WAL の中の全ての更新履歴が CheckPoint ファイルに反映されているため）そのため、WAL ファイルを os.Truncate() してクリアします。

起動時に WAL ファイルの中身があるときは前回のプロセスが異常終了したことを表します。（正常終了では必ず WAL ファイルはクリアされているため）そのときは Crash Recovery を行います。WAL ファイルの更新履歴を COMMIT ログがあるところまで再実行して CheckPoint ファイルの内容を更新します。

やっていることはこれだけです。これだけの処理をするだけで ACID を守ったトランザクションが出来上がってしまいます。

Step 2 : シングルスレッドで同時に複数のトランザクションが並行に動く

GitHub - kawasin73/txngo at S2PL-single-thread

まず、複数のトランザクションに同時にクエリを送信するために、インターフェイスは標準入出力の他に TCP コネクション をサポートするようにしました。telnet で接続すると標準入出力と同じやり取りを複数同時に行えるようになります。TCP コネクションごとにトランザクション実行主体が作成されます。

複数のトランザクションを並行に動かすために並行制御アルゴリズムである S2PL を導入します。トランザクションはそれぞれ goroutine のなかで並行に動いています。

S2PL とは Two Phase Lock を発展させたもので、あるレコードへの排他ロック（Write Lock）または共有ロック（Read Lock）の獲得を成長相のみで行い、トランザクションの完了（WAL への COMMIT ログの書き込み）後に排他ロックを解放するというものです。共有ロックはトランザクションの完了前に解放することが許されますが、排他ロック・共有ロックのどちらのロックも解放したあとは縮退相となりロックの獲得はできなくなります。

この S2PL を導入するためにそれぞれの操作に以下の処理を追加します。

  • READ するときは Read Lock を獲得
  • INSERT, UPDATE, DELETE をするときは Write Lock を獲得
  • COMMIT するときは以下の順番で処理
    1. 獲得した全ての Read Lock を解放
    2. WAL の書き込みと永続化
    3. Write Set の中身を DB に反映
    4. 獲得した全ての Write Lock を解放
    5. Write Set と Logs をクリア
  • ABORT するときは獲得した全ての Lock を解放

ここで１つ課題が発生します。READ したレコードを更新する場合 の処理は自明ではなく、明確に決める必要があります。

すでに Write Lock を獲得した後は READ をする場合でも更新処理をする場合でも新たにロックを取ることはありません。しかし、Read Lock を獲得した後に更新する場合はそれを Write Lock に変換する必要があります。

Go には、sync.RWMutex という Read Lock と Write Lock が可能な Mutex コンポーネントがありますが、残念ながら Read Lock を Write Lock に変換する方法は提供していません。もし、Read Lock を解放して Write Lock を獲得し直すと別の goroutine で Write Lock 待ちしていたトランザクションにロックを横取りされてしまう可能性があります。

ここで僕が考えた解決策は以下の2つです。

前者は、標準ライブラリの sync.RWMutex だけで実現できるため簡単に実装できます。しかし、ユーザはトランザクション開始時に明示的に Read-Write か Read-Only であるかを宣言する必要があります。正直これは使い勝手が悪いです。そのくらい自動で判別してほしい。

処理パフォーマンスの高速化やデッドロックの回避を理由にしてこの手法を採用するのであればいいのですが、コンポーネント自作が難しいからという理由でユーザに不自由を押し付けることはしたくありません 。

そこで後者の昇格可能な RWMutex を自作する手法を選択して github.com/kawasin73/umutex を自作しました。詳しくは以下の記事で紹介しています。

kawasin73.hatenablog.com

昇格可能な RWMutex では、Read Lock を獲得した goroutine 同士が昇格しようとすると デッドロック を起こしてしまうという課題がありますが、この umutex ではデッドロックを検知する仕組みが備わっています。

f:id:kawasin73:20191206203651p:plain

ロックはレコードごとに獲得できるようにするために Locker というコンポーネントを追加しました。S2PL では範囲スキャンをした時にロックの穴あきによる予期せぬアクセスを防ぐため、範囲ロックを工夫しないといけないのですが、今回のトランザクションは範囲スキャンをサポートしていないのでシンプルな map[string]*lock で実現しています。レコードごとに複数の Read Lock が起こり得るため参照カウントを持ち不必要なロックオブジェクトを削除しています。

各トランザクションでは Write Set にあるレコードは全て Write Lock を獲得していることを表します。同様に Read Lock を獲得していることを表現するために Read Set も追加しました。

Step 1 では、更新内容は Logs と Write Set の両方に保存していましたが冗長であることに気づいたので、Write Set には Logs のインデックス番号だけを保存するように最適化しました。

COMMIT 処理でのログの書き込み中に他のトランザクションの COMMIT 処理が割り込まれるとデータが壊れてしまいます。goroutine は厳密なシングルスレッドではないため、goroutine が COMMIT 処理中にコンテキストスイッチを起こして別の goroutine の COMMIT 処理が割り込まれる可能性があります。3 そのため、COMMIT 処理全体を sync.Mutex によって排他制御するようにしました。

S2PL を導入するために昇格可能な RWMutex を実装するだけで、並行制御されたトランザクションが実装できてしまいました。goroutine の強力さのおかげです。

Step 3 : マルチスレッドで同時に複数のトランザクションが並行に動く

GitHub - kawasin73/txngo at S2PL-multi-thread

最終ステップとしてマルチスレッドで動かすために、runtime.GOMAXPROCS(1) を消します。

あとは、複数のスレッドから同時アクセスされそうな所に排他制御を導入するだけです。Locker と DB へのアクセスをするときに map の更新で競合する場合があるので sync.Mutex と sync.RWMutex で保護するようにしました。

まさかのマルチスレッド対応が一瞬で終わってしまいました。goroutine にのっかるだけで同じロジックでマルチスレッドで動くというのはすごいことです。

最後に

無事、マルチスレッドで動く S2PL で並行制御されたトランザクションを完成させることができました。こんなにあっさりできてしまったのは goroutine のおかげです。

ただ、最初に述べたように色々制約をつけてサボっているところが多いです。インデックスにデータ構造を適用したりとか、バッファプールを追加したりとか、チェックポイントの作成を定期的に行ったりとか、WAL をロックを取らずに書き込んだりとか色々改善の余地はあります。

しかし、Go はメモリが枯渇することを想定しない 4 言語である上に、メモリ管理が GC と密に結合しているのでメモリ枯渇への対応であるバッファプールを実装するのはちょっと辛いです。（[]byte から特定の型へ unsafe.Pointer などを使ってキャストしても GC の対象外となる）

次は、そういう改善点と並行スケジューラの実装を含めて柔軟な言語である C や C++ で実装してみたいと思っています。

最後になりますが、今回の試みはセキュリティキャンプで教科書を提供していただき、途中でレビューをしてくださった 星野さん のご協力なしには実現できないものでした。改めて感謝申し上げまして、この記事を終わりたいと思います。

  1. GoConで発表してきたのでついでにruntime以下の知識をまとめていく #golang - niconegoto Blog↩

  2. The Go scheduler - Morsing's blog↩

  3. goroutineがスイッチされるタイミング - Qiita↩

  4. メモリアロケーションに対する罪悪感 - 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↩