Skip to content

Instantly share code, notes, and snippets.

@taiyow

taiyow/erlang-knowledge.md

Last active December 3, 2019 01:08
Show Gist options
  • Save taiyow/96e94e28f0f64cb3eeb15adf6cd7e3ea to your computer and use it in GitHub Desktop.
Save taiyow/96e94e28f0f64cb3eeb15adf6cd7e3ea to your computer and use it in GitHub Desktop.
Download ZIP
Erlang Knowledge
Raw
erlang-knowledge.md

Erlang/OTP 関連で読んだ/観た資料のリスト

何を読んで何を知ってどう思ったかをすぐに忘れてしまうので、資料を書いていく場所。

方針は:

  • 読んだ/観た順番に先頭に追加していく
  • 一般に公開されていない資料については記載しない
  • どんな資料かを1行だけ書き、資料の目的/想定対象がわかれば記載
  • 自分が新しく知った点を書く

書いた人: Erlangのプログラムをときどき書いていて、性能改善とか分散システムに興味がある Erlang 初心者

「これは必読」「これを読まずに偉そうなこと言うな」という資料をご存知でしたら、コメント等でご教授いただけると嬉しいです。

Comparison of Erlang Runtime System and Java Virtual Machine

  • http://ds.cs.ut.ee/courses/course-files/To303nis%20Pool%20.pdf
  • 著者: Tõnis Pool
  • 読んだ日: 2019-12-02
  • 内容: Java VM (Oracle が開発している hotspot) と Erlang VM である BEAM の比較紹介
  • Erlang 側の話は The BEAM Book に書いてあることがほとんどだが、短かくまとまっていてわかりやすく、記憶の呼びおこしにも良かった

詳細

  • メモリ
    • JVMのスタックとヒープは全スレッドで共有、BEAMは軽量プロセスごとに独立
    • ヒープはどちらも世代別管理で、世代別GC
    • BEAMはプロセスごとにGCをするのでストップザワールドが無い
    • BEAMでは短命なプロセスはGCが走ることなく死ぬ(だから綺麗といいたい?)
  • 並列性
    • 共有領域へのアクセスは、JVMはロックが明示に必要
    • "The burden of guaranteeing correct access to shared variables lies on the programmer"
    • Erlangはメッセージパッシングで「ロックを高レベルで抽象化」した (この表現すごくしっくり来た)
    • Akka が JVM の上で同様の抽象化をしてるから、JVM のエコシステムに乗れるので良い
  • メッセージパッシング (に1節置くぐらい注目している)
    • BEAM は過去に、全データコピーではなくポイント形式のメッセージパッシングも実験していた
    • が、マルチスレッド対応が入ったらその実装がぶっこわれて取り除かれた (そうなの…)
    • そもそも別ノードで実行する場合、ポインタ共有できないし
  • スレッドと軽量プロセス
    • 軽量プロセスのいつもの解説、reductionとかも
    • （スケジューラ間のマイグレーションの方針も書いてあってなにげに深いところまで解説してくれている）
    • 64bitマシン上での確保スタックは、Erlangのプロセスは2.5KBだが、Javaのスレッドは1024KB (!!)
    • Akkaを使うときは、アクターがブロックするとOSスレッド全体をブロックしてしまうのでAkkaの原則を守る必要がある
  • JIT
    • BEAMJIT に期待
  • "Erlang accidentally has the right properties to exploit multi-core architectures - not by design but by accident"
    • Joe Armstrong
  • 参考文献多数
    • erlang-question ML の回答などもある

Using Rust to Scale Elixir for 11 Million Concurrent Users

詳細

  • MapSet → 速そうだけど、順序が不定なので要件外
  • List を使う → 25万のリストの末尾に追加すると170msかかるので遅過ぎる
  • ordsets → 25万にもう1つ追加すると 27ms、速くなったけどまだ十分ではない
  • SkipList → 小さな ordsets を複数使う。Cellとして管理。25万項目への追加で 5ms
    • ただし別のワーストケースで19msに遅延 (Cell溢れが連鎖した場合)
    • 溢れが連鎖しないようにCell分割を導入して、最悪値でも640usに短縮
  • Rust の NIF にしたら速いのでは? → PoC の最悪値で 2.85us
    • Rust で SortedSet 作ったら Elixir の List に比べて4万倍以上

名言「CSが過去60年に渡って、ソートのアルゴリズムとデータ構造を最適化してきた」

Understanding Erlang Kernel | Code BEAM SF 19

  • https://www.youtube.com/watch?v=wC5oR3Zm6I0
  • 発表者: Boshan Sun at ArcBlock (ブロックチェーン関連の開発会社?)
  • 観た日: 2019-04-13
  • 内容: Erlang カーネルの内部データや挙動の説明、特にshellでのライブデモをメインに

詳細

  • demoで使ってる、shellを複数立ち上げて切り替えて使うの、すごい良さそう
  • PID の内部データは tag 付けされてるよ (感想: "The Beam Book" で出たやつだ!)
  • shell の 2つのモード: interactive, embedded
    • interactive では、未知のモジュール参照時にpathから検索して自動でloadしてくる
    • Elixirのshell (iex) も path を追加すれば Erlang から呼び出せる → ``'Elixir.IEx'` を実行
  • group_leaderの概念と挙動
    • 別nodeでspawnしたプロセスでio:formatを呼ぶと、呼び出し元で表示される (erlang:display なら表示されない)
    • デフォルトだと user プロセスが作られて、それが group_leader になる
    • <0.0.0> の init プロセスが、 user がいない場合には group_leader になってくれる
  • user_drv
    • process → user_drv → ttysl (TTY slave) IO処理

Process Signals in OTP-21 | Code BEAM SF 2019

詳細

  • プロセス間メッセージングに2種類あるという衝撃の話 (message と non-message signal
    • process_info/2 もプロセス間で通信している!
      • つまり、対象プロセスのメッセージキューが積み上がっていると、process_info の応答も遅くなっている
    • OTP-21 では middle_queue の導入と、signal 先に処理される仕組みで、改善された
  • OTP-20まで: メッセージキューは2種類の linked list で実装
    • external mailbox: 送る側が書き込む
    • internal mailbox: 受信側が読み込む
    • internal が空のときに受信側が exernal から internal に移す
  • OTP-21では: external -> middle -> internal の構成
    • middle に skip-list を用意して、signal だけ先に処理する
  • (感想: それ以外に monitor の仕組みの変化も解説していたけどあまり理解していない)

The Beam Book ("The Erlang Runtime System")

https://blog.stenmans.org/theBeamBook/

  • 読んだ日: 2019-01-30
  • 内容: Erlangの内部実装(スケジューラ、ロックメモリ管理、バイトコードなど)の解説
  • 対象読者: Erlangの内部実装を知ったり、VMクラッシュを読んだり、Erlangプログラムの性能改善をしたい人

詳細

  • スケジューラの解説はここではじめて見た
    • ready queue (run queue) はスケジューラプロセスごとに個別
    • プロセスの priority ごとに、 max 用、high 用、 normal と low 用の3本の ready queue
    • low プロセスは、schedule count を 8 に設定され、ready queue の先頭にくるたびにデクリメントする、つまり8回 ready queue を通過してはじめて処理される
      • (感想: てことは、low はスケジューラの負荷を増やすだけで、あまり効果が無くない？)
    • 負荷の均衡は2種類
      • Task Stealing: 自分の ready queue が無い時に、他の(自分より上のidを持つ)スケジューラの一番 priority が高いタスクを奪ってくる
        • 全体ではなく1つのスケジューラしか見ないので、必ずしも最高 priority のタスクが steal されるわけではない
        • (感想: 高い優先度のプロセスは steal されやすい? ということは、CPUキャッシュが破棄されやすい? それってどうなんだろう)
      • Migration: 全部の scheduler の ready queue を分散させる
        • 2000 x 2000 回の reduction のたびに発動
    • (感想: process が sleep する際の busy wait の話を読みたかったのだが、この文書には説明は無かった…)
  • メモリ管理も詳しく解説してあって嬉しい
    • プロセスにメッセージを送るにはそのプロセスのヒープの main lock を取る必要がある
      • ロックを取れたら、送信先プロセスのヒープに直接コピーするので、速いしalloc断片もできない
    • R19から導入した message_queue_data (MQD) では off_heap も指定可能
      • off_heap 時は、heap断片を新規に確保してそこに書く (これが m buf?)
      • m buf は GC 対象外
      • プロセスの mail lock を取得しないので、高負荷かつメッセージ受信が多いプロセスは off_heap にすると良い
      • ただし off_heap ではメモリ消費が大きい (memoryと実行速度のトレードオフ)
  • Erlang 内部でも Tagging してオブジェクトを管理している
    • Emacs や Ruby で採用している、オブジェクトのポインタの下位数bitを特殊なマークにつかうアレ
    • 下位2bitがタグで、種類によっては下位6bitまでを利用
  • 以前のVMのJAMはstack machineだったが、BEAMはregister machine
  • VMのコンテキストスイッチは preemtpion ではなく reduction counting
    • 「関数呼び出し」を1リダクションとして、一定数を超えたら処理をうつす
    • Erlangが関数型で、ループを末尾再帰で表現するためにできるワザ (長い処理は関数呼び出し回数も増える)
    • なので、重いbifを使ったり(term_to_binary)、NIF(C言語拡張)内で1msを超える処理をするとスケジューラが困る
  • メモリアロケータはアルゴリズムが異なるものが複数種類ある
    • Basic allocator (sys_alloc), Memory segment allocator (mseg_alloc), Binary allocator (binary_alloc), Driver allocator (driver_alloc), ...
      • 感想: これらのアロケータと、 memory/0 の出力の要素が、それぞれ対応しているのか?
      • sys_alloc は malloc(3) で確保。呼び出し回数を減らすためにある程度のパディングをする(デフォルトは0)。GC後も trim threshold までは free(3)を呼ばない(デフォルトは128KB)。なのでdefaultではメモリをOSに解放しない(感想:この説明あってるか?)
      • mseg_alloc は mmap(3) で確保。こちらも解放後に segment cache を持ち、すぐにはOSに返さない。defaultの segment cache 数は10。0..30 の間で変えられる(感想: これは、segmentのサイズごとに10個という意味か、全体で10個か、どっち?)
    • beam.smp 上では、スケジューラプロセスがそれぞれ自分のallocatorを持つ、つまりコア競合しない
  • GCは世代別コピー
    • GCの途中で、heap 上の term は new heap にコピーされ、最後に old heap が削除される
    • (感想: だからメモリのfragmentが解消される、ということ?)
    • 「世代別」なので、古い term の GC 回数は少なくなる
  • 未記入の章もあり(crash dumpとか)、追記が待たれる
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment