リーダ選出: ring アルゴリズム
Raft Consensus Algorithm をみつけてリーダ選出とは、となったので調べてちょっと書いてみたメモ。なお、この記事では raft のことは書いてない。
リーダ選出とは
リーダ選出アルゴリズムとは、分散システム内で特別な役割を持ったノード(プロセス)を選出するためのアルゴリズムのこと。 リーダを決め、中央集権的にシステムを動かすことで、権限が分散している場合にくらべシステム内の一貫性を容易に保てる1。 たとえば、分散メモリがあるとすると、あるプロセスが分散メモリに値を書き込む際には、そのプロセスはロックを取ってから書き込みをしないとレースコンディションが発生する可能性がある。この時、一つのプロセスをリーダにし、そのプロセスが他のプロセスにロックを提供し、書き/読み込みをしたいプロセスがロックを取ってクリティカルコンディションに入ることで安全に分散メモリを操作できる。
ring アルゴリズム
ring 型のネットワークを考える。 ring型ネットワークとは、それぞれのプロセスが自分以外の2つのプロセスと結びついてる様なネットワーク。 要は以下の形をしたネットワーク。
CS 551: Synchronization, Token Ring Election Algorithm Exampleより
この記事での ring アルゴリズムは以下の話。wikipediaの分散システムのページを見てると、これは ring アルゴリズムの中でも Rings with unique IDs というやつっぽいのだけど、いまいち全体の世界観をつかめていないのでよくわかってない。
- アイデア : CS 551: Synchronization, A Token Ring Election Algorithm
- 図 : CS 551: Synchronization, Token Ring Election Algorithm Example
このアルゴリズムは election message を送るステップと coordinator message を送るステップの2つのステップに分かれる。
まず、現在のリーダが何かしらの理由 (通信不能になったり、プロセスが死んだり) で fail したところからリーダ選出が始まる。
リーダが fail したのを他のプロセスが検知して election message というメッセージを次のプロセスに送る。もし、次のプロセスが fail したリーダのプロセスだった場合はその次のプロセスに送る。
election message とは自分の id を追加した配列を含んでいるメッセージのこと。例えば、下の図の場合は P3 が自分の id である 3
というメッセージを、それを受け取った P5 は、受け取ったメッセージに自分の id である 5 を追加した 3,5
というメッセージを次のプロセス P0 に送る。
この 3
であったり、3,5
であったりを election message といっている。そして、election message が ring を一周して元のプロセス(図ではP3)に戻ってきたところで election message を送るステップは終了する。
CS 551: Synchronization, Token Ring Election Algorithm Exampleより
ここからが、次の coordinator message を送るプロセスになる。
election message が ring を一周して、最初にリーダの fail を検知したプロセスに戻ってきたとき、election message の中身は ringに所属しているプロセスのidが全て含まれている。この id の中から一番大きな値を選びだし、その id が次のリーダだということを他のプロセスに周知するメッセージが coordinator message になる。coordinator message が ring を一周して元のプロセスに戻ってきたところで coordinator message を送るステップも終了しリーダが決定する。
例えば下の図では、P3が最初にリーダの fail を検知したプロセスだとして、そこに返ってきた election message が 3,5,0,1,4
だとすると、この中から一番大きな数である 5 を次のリーダ(つまりプロセス P5 )とする。そこで P3 は 「次のリーダは P5 だ」というメッセージまた他のプロセスに送信する。このメッセージを coordinator message という。他のプロセスも自分の次のプロセスに「次のリーダは P5 だ」というメッセージをおくる。そして、P3 に戻ってきたところリーダ選出を終えて P5 がこのシステムのリーダとなる。
CS 551: Synchronization, Token Ring Election Algorithm Exampleより
作った
ring アルゴリズムを実装してみた。
ring アルゴリズム自体の実装は https://github.com/ganmacs/eve/blob/master/lib/eve/agent/ring.rb この辺にある。仕様的なものを見つけることができなかったので、上の図を見て気持ちを感じて実装した。
Linuxシステムプログラミング8章
Linuxシステムプログラミングの8章メモリ管理の雑なメモ。 下に行くほど雑になってそう。この本。
- 作者: Robert Love,ロバートラブ,千住治郎
- 出版社/メーカー: オライリージャパン
- 発売日: 2008/04/16
- メディア: 大型本
- 購入: 5人 クリック: 181回
- この商品を含むブログ (31件) を見る
プロセスアドレス空間
ページとページイン/アウト
- 仮想アドレス空間はページで構成される
- サイズはマシンによる 32だと4KB、64ビットマシンだと8KB
- ページには有効と無効という概念がある
- 有効なページは実際に対応する物理メモリ、またはディスク上のファイルがが存在する
- 無向なページはアクセスするとセグフォになる
- プログラムが物理メモリに存在せず二次記憶装置に存在するページにアクセスしようとすると、ページフォルトをMMUが発生させる
ページ共有とcopy-on-write
- (異なるプロセスの)異なる仮想アドレスから物理メモリ内のデータを共有できる
- 読み書き専用、読み取り専用どちらでも良い
- 書き込む処理は二種類ある
メモリ領域
動的メモリ割り当て
- 動的メモリは、コンパイル時ではなく実行時に割り当てるもの
- 実行時になるまで、実際のサイズなどはわからない
- cだと
malloc
で動的メモリ割り当て出来る- 成功すると、割り当てたメモリ領域の先頭アドレスを返す
配列割当
- 配列の割当には
calloc
をつかうmalloc
と違って0で初期化する
メモリ領域のサイズ変更
realloc
でメモリ領域のサイズを変更できる
動的メモリの解放
- 動的に割り当てたメモリは明示的に解放するまでプロセスアドレスの一部として存在し続ける
free
を使う- 開放しないとメモリリークする
- 解放後のメモリにアクセスしてはいけない(ダングリングポインタ)
アラインメント
- ハードウェアからみたメモリ領域とアドレスの関係
- データサイズの定数倍のメモリアドレスへ配置された変数を自然なアライメントという
- 32ビットの変数がメモリ上で4の倍数のアドレスに配置されているとき
アラインメントされたメモリの割当
- コンパイラとCライブラリがよしなに解決してくれる
- 32ビットシステムでは8バイト,64ビットだと16バイト境界にアライメントされる
posix_memalign
を使用すると、任意の倍数でアライメントされたsizeバイトの動的メモリを割り当てられる
他のアライメント問題
- 非標準の型
- 構造体のアライメントはメンバの最大サイズに合わせる
- 最大サイズを持つメンバが4バイト境界でアライメントされる32ビット整数なら、その構造体は4バイト以上のアライメント
- パディング(padding)が必要。
- char(1バイト)のあとにintのメンバ(4バイトでアライメントされる)がある場合、charの後ろに3倍とのパディングが必要
- 共用体のアライメントはメンバの最大サイズに合わす
- 配列アラインメントは要素に合わせる
- 構造体のアライメントはメンバの最大サイズに合わせる
- ポインタ
- 以下の例では、unsigned longは4 or 8バイト境界に割り当てられるのに、charはほぼ確実に1バイト
- そこで c をロードするとアラインメント違反
- 違反の結果はアーキテクチャ依存でクラッシュすることもある
char greeting[] = "Ahoy Matey"; char *c = greeting[1]; unsigned long badnews = *(unsigned long *) c;
データセグメントの管理(ヒープ領域)
- でたーセグメントを直接操作する関数はあるが、
malloc
などが使いやすく機能も豊富であるためほぼ使われていない brk
はデータセグメントの末尾(break point)を渡された場所を変更する
無名メモリマッピング
- 典型的な
malloc
はデータセグメントを2の累乗のサイズの領域が並んだ状態に分割し,要求されたサイズに最も近い領域を貸す- 直前の領域がフリーの場合はつなげて,一つの大きなフリー領域にする
- 戦闘だった場合は領域を縮めてカーネルに返す
- バディメモリ割り当てシステムという
- 内部フラグメンテーション - 要求されたメモリより大きなメモリ領域を返す問題
- 外部フラグメンテーション - サイズ分のメモリ領域があるにも関わらず,複数のメモリ領域に分断されている
領域Bと領域Aが隣接しており,領域Aがbreakpointに隣接している場合,Bを開放してもAが終わらない限り開放されない
巨大なメモリ割り当てをするとglibcはヒープを使用せす無名メモリマッピングをする
- ファイルを使わない
- 巨大で,0に初期化された領域を使用できる
- 本来のヒープの外にあるのでフラグメンテーションが発生しない
- メモリ領域はサイズ,アクセスパー密書の変更が可能
- 短所
- メモリのサイズがページングサイズの整数倍になる,要求サイズがページサイズより小さいと無駄な領域が発生する
- カーネルからのヒープ割当に比べてオーバヘッドが大きい
無名メモリマッピングの作成
munmap
システムコール(mmpa
に MAP_ANONYMOUSを指定しても行ける)
/dev/zero のマッピング
高度なメモリ割り当て
mallopt
を使用してカーネルパラメータを変更できる。
メモリ割り当てのデバッグ
メモリ割り当て統計情報
mallinfo
でメモリ割り当ての統計情報を得る
スタック上のメモリ割り当て
- スタックはプログラムのオート変数(automatic variable)を格納する場所
alloca
を使ってスタック上で動的にメモリ割り当てをする- メモリ領域はスタック上に取られる
- つまり、
alloca
を実行した関数がリターンしたら解放/破棄される -> freeしなくていいのでコードが簡潔に alloca
を関数コールのパラメータ内で使用すると、関数パラメータの用のスタック領域にメモリを割り当ててしまうため使用を避ける
スタック上へ文字列をコピー
- 文字列の一時的なコピー等に使える
- そのためのインターフェイスとして、
strdupa strndupa
がある
- そのためのインターフェイスとして、
メモリ割り当て方法の選択
- malloc
- 単純だが割り当てられたメモリがゼロクリアされていない
- calloc
- 配列の割当が容易でゼロクリアされてる、配列以外には使いづらい
- realloc
- メモリサイズを変更できる、ソレ以外使えない
- brk and sbrk
- ヒープを完全に制御できる、低位すぎるインターフェイス
- 無名メモリマッピング
- 共有可能、アクセスパーミッションもできる。サイズが大きいときにも使える。メモリが小さいと効率が落ちる
- posix_memalign
- 任意サイズの境界に従うメモリを割り当てる。移植性に難がある
- memalign and valloc
- alloca
- 高速なメモリ割り当て、解放不要、サイズの大きな割当には不向き。
- 可変サイズ配列
- allocaとほぼ同じ、スコープを抜けたときに解放される。配列に限り有効
メモリ操作
バイト設定
- memset(void *s,int c,size_t n) sのメモリ領域へcをnバイト分設定
バイト比較
- memcmp(s1,s2,n) s1の先頭からnバイトs2と比較
- 構造体は持つ内部にパディングを含むため正しく比較できない(パディングは不定値だから)
バイト移動
- memmove(dst,src,n) srcの先頭nバイトをdstへこぴー
- メモリ領域が重なっていない場合も正しく動く
- もともと重ならないとわかっている場合にはmemcpyを使用する
バイト検索
- memchrはメモリ領域内の指定されたバイトを検索する
メモリのロック
- linuxのカーネルは不要なページはスワップアウトして、必要に応じてスワップインするデマンドページングを使用している
- この操作は透過的に行われるのでアプリケーションは気にしなくて良い
- しかし意識したい場合もある
- 決定論
- 時間的な制約を持つアプリケーションではページフォルトしてディスクIOが発生して時間的制約を超過してしまう
- セキュリティ
- 機密情報がページアウトされてしまうと、暗号化されずディスクへ保存されてしまう
- 決定論
- 当然全体のパフォーマンスが落ちる可能性があるので気をつける
アドレス空間の一部をロック
- mlock(addr, len)でアドレスの範囲を指定して物理メモリ上にロックする
アドレス空間全体をロック
- mlockallで(カレントプロセスの)メモリ全体を物理メモリ上にロックする
メモリのアンロック
- munlock, munlockall
メモリの遅延割当
- カーネルへメモリの追加を要求すると,カーネルは実際には物理メモリを割り当てずに成功を返す(commit)
- 書き込んだ時点で初めて割り当てる(CoW)
- 遅延できる
- 実際に使用する分(割当要求分ではない)のみ物理メモリを使用する(ページ単位にする)
- コミットしたメモリサイズをシステムの持っているメモリよりも大きくすることが出来る。(overcommit)
オーバコミットとOOM
golang で Future を実現する
ここで言う Future オブジェクトとは、clojure の Future を使用して作成できるオブジェクトのようなものことをいう(結果をキャッシュしてないとかはあるけど、その辺は割愛している)。 つまり、何か処理を受け取りその処理を別 thread で実行するオブジェクトのことで、それを golang で作る。
シンプルな Future
とにかくブロックせずに、後から値を取り出せるようなオブジェクトを作成する場合は以下のようにする。
ジェネリクスがないので int に対する Future を書いた。NewFuture
の引数の f
がブロックするような重い処理をする。
クロージャ f
の戻り値を future (chan int)
にいれて、Get()
を使ってあとからその値を取っている。
type Future chan int func (f *Future) Get() int { return <-*f } func NewFuture(f func() int) *Future { c := make(Future) go func() { c <- f() }() return &c }
使い方は以下のようになる。
f := NewFuture(func() int { // a time-consuming code return 10 }) f.Get() // 10
Get()のブロックを回避
上の実装だと、Get()
したタイミングで NewFuture
に渡した処理が終わっていなかった場合そこでブロックしてしまう。
そこで、処理中 (pendding
) か終了 (filfilled
) かをブロックせずにわかるようなメソッドを持った Future オブジェクトは以下のようになる。
const ( Pending = iota Fulfilled = iota ) type Future struct { State int ch chan int } func (f *Future) Get() int { return <-f.ch } func NewFuture(fn func() int) *Future { f := Future{ State: Pending, ch: make(chan int), } go func() { ret := fn() f.State = Fulfilled f.ch <- ret }() return &f }
State
を使用すると渡され処理が完了しているかわかるので例えば、以下のように終了したか(fulfilled
)かどうかによって処理を変えられる。
f := NewFuture(func() int { // a time-consuming code return 10 }) if f.State == Fulfilled { f.Get() // 10 } else { // something code f.Get() // 10 }
感想
以上のように golang を使うと Future はシンプルに書けるので、無理に Future ライブラリを使うのではなくてその都度かんたんなものを作れば良さそうな気がした。
Go版retriable作った
使い方
一番シンプルな使い方。引数として渡されたクロージャが成功するまでリトライし続ける。 リトライ回数のデフォルトは3で、リトライ間隔は randomized exponential backoff アルゴリズムを使っている。簡単に言うと、CSMA/CD みたいにコリジョン(失敗)すると次に実行するまでの時間が徐々に長くなっていくアルゴリズム(をちょっと変形させたやつで、元ネタはここらしい google-http-java-client )。
retriable.Retry(func() error { // your code return nil })
リトライ回数を変更したい場合は Options を使う。 リトライ回数を5、最初のリトライ間隔を1秒に設定した例。
opt := retriable.Options{ retries: 5, interval: 1 * time.Second, } retriable.RetryWithOptions(func() error { // your code return nil }, opt)
処理全体にタイムアウトを設定することも出来る。 RetryWithOptionsに渡されたクロージャが5秒以上かかった場合にリトライするのをやめて、処理を返えす。
opt := retriable.Options{ timeout: 5 * time.Second, } retriable.RetryWithOptions(func() error { // your code return nil }, opt)
リトライ間隔がexponentialに増加するのではなく、一定にしたい場合はbackoffをConstantBackoffに変更する。
opt := retriable.Options{ backoff: backoff.NewConstantBackOff(1 * time.Second), } retriable.RetryWithOptions(func() error { // your code return nil }, opt)
まとめ
ご意見があればぜひ
Rust で LLVM やってみる
Rust と LLVM やってみたくなってやってる. llvm-sys という LLVM の Rust バインディングのライブラリを使って LLVM 動かしてみた話と自分用メモ.
きつねさんでもわかるLLVMを読んでからやるかと思ったが,5章以降はちょっと自分には合わなかったのでブログ探して、それをやりながら参照程度に狐さんを見るという作戦でいった.
環境設定
何とかして Rust を入れる. これを真似すればだいたい行ける.
気付いたらRustの環境構築がかなり楽になってた | κeenのHappy Hacκing Blog
後は LLVM を入れてpathを通す.
brew install llvm export PATH="`brew --prefix llvm`/bin:$PATH"
やったこと
- LLVM IR の雰囲気を知りたかったので幾つかサンプル書いてみた.
playground/rust/llvm-example at master · ganmacs/playground · GitHub
llvm*.rsは上の方に動かしたい擬似コードを書いてある. codegen*.rs は AST ができてる体でそれを LLVM IR に変換するコードをかいた.
ほとんど Rust かいた経験がないため,色々おかしいところがありそう. マクロかけるようにするかってところで気持ちが終わり,LLVMバックエンドにリプレイスとかやってる.
参考になったブログとコード
llvm の公式のサイト.実際 LLVM IR 書いてる(実際に書いてるのはRustのラッパーだけど)と使い方がわからず,ググると大抵これしかヒットしないので一生懸命これを読む.
Rust で llvm-sys.rs を使って 数字を出すところから phi 関数(というのがある) を使って if 式を作ることまでやってる.
Go 言語用のバインディングもあるようでそれを使って,加算するところまでやってる.序盤の説明が分かりやすかった.
LLVM の外観をつかむのには良かった. ただ,読み進めてるといきなり Pass の話をしだすので,LLVM IR について知りたい場合は序盤だけ読んで,後半は後で読むと良さそう.
LLVM のチュートリアルを Rust でやってる. この作者が作った iron-llvm という llvm-sys.rs をラップしたライブラリを使って LLVM を触っているのでいきなりこれを見ること混乱するかもしれない. 最初はむしろ iron-llvm のコードを読んで llvm-sys.rs の使い方の雰囲気をつかむのが良い.
きつねさんでもわかる LLVM のサンプルコードのリポジトリ.割りと大きめのコードなので実際に真似しやすい. 構文の定義( https://github.com/Kmotiko/DummyCCompiler/blob/master/dummyC_ebnf.txt )を読めばどんな言語かわかるので本の方は読まなくてもだいたい分かると思う.
emacsでコード読んでるときに「現在いる行が含まれたプルリク」に飛びたいを見れるようにした
これ見て hub browse -- commit/<commit-id>
でcommitに飛べることを知ったので、それを使って emacsでコード読んでるときに「現在いる行が含まれたプルリク」に飛びたいを見れるようにした。
このスクリプトも元ブログと一緒でプルリクのページではなくコミットページを開くところで終わってますが。
(defun open-github-commit () (interactive) (let* ((cmd1 "git blame -l -L %s,+1 %s | cut -d ' ' -f 1") (cmd2 "hub browse -- commit/%s") (zero "0000000000000000000000000000000000000000") (commit-id (shell-command-to-string (format cmd1 (line-number-at-pos) buffer-file-name)))) (if (string= zero commit-id) (message "This line is not commited") (shell-command (format cmd2 commit-id))))) (global-set-key (kbd "M-g o") 'open-github-commit)
hub browse -- commit/<commit-id> でいけるのか昔自分の書いた軟弱な正規表現を修正しなくて済みそう最高
— がんま (@ganmacs) 2017年2月9日
さよならgheに対応してないelisp君 GitHub - ganmacs/emacs-github-open: Open a commit url in github.com
Treasure Data インターンで最高の夏過ごしてきた #td_intern
8月1日から9月30日の間,Treasure Data Summer Intern 2016に参加していました. 他のインターン生2人からの強烈なプレッシャー (強烈なプレッシャー1,強烈なプレッシャー2)に負けたので僕もインターンブログを書きます.
tl;dr
すごいメンターの元 Fluentd の開発してると何故かめっちゃお金がもらえるインターンでとにかく最高
なにやってたの?
キュートなロゴ
Fluentd というソフトウェアの v0.14 向けの機能を,メンターの @tagomoris さんの元,開発しました.具体的に行ったことは以下のようになります(スライドからそのまま持ってきただけですが).
- 6 features
- 2 enhancements
- Optimizing multiple filter calls
- Add event size to options in a forward protocol
- Some small tasks
インターン期間は2ヶ月あったので,最初の1ヶ月は Fluentd の開発スタイルに慣れようということで小さめの機能(Counter API以外のタスク)をいくつかをやって,最後の1ヶ月で大きい機能(Counter API)を1つ をやりました.
一応雑に機能を紹介すると,
Counter API
マルチプロセスでfluentd動かしたとき,メトリクスとるのに使えるやつ
Data compression in buffer plugins and forward plugins
データを圧縮して操作できるようになり何かとリソースを節約できるやつ
New out_file plugin only for
secondary セクションのみで使えるシンプルな out_file
プラグイン
A CLI tool to read dumped event data
送信に失敗してダンプされた MessagePack形式のデータを読めるようなるやつ
Log rotation
Fluentd で log rotation できるようになるやつ
filter_with_time method in filter plugins
filter pluginで time をいじれるようにするやつ
Optimizing multiple filter calls
複数filter使用したときに高速化するやつ
Add event size to options in a forward protocol
eventのサイズつかって,内部の無駄な処理最適化するやつ
それぞれの説明を詳しく書いてもいいんですが長くなりすぎて誰も読まなくなると思うので,興味のある人は僕に会ったときにでも聞いてください(スライドを読んでもいいですが説明がアレ).
以下が最終発表スライドです.発表は英語でするはずだったんですが,僕のときだけUSの人たちがいなくて日本語で発表OKだったので,日本語が使えることに感謝しながら日本語で発表しました.
感想は?
まずは,Fluentd がいろいろ大変でした(語彙力).そもそも1回くらいしか Fluentd 使ったことなかったのでどうやって使われているか調べるところからはじまり,「あれ,これやばくない???」とか思いながらインターン初日を過ごしていました. @tagmorisさんのスライドにも書いてありますが,Rubyの黒魔術をふんだんに使って書かれていたので非常に読み応えがありました. コードを読む上で,Fluentd ソースコード完全解説 は参考になりました.結構古いので変わってしまったところもありますが,全体の流れを見るにはちょうどよかったです. キッっと睨んでるとわかってきたので大変なのは慣れることだなって感想になりました.
あとは,一番大きい機能の Counter API を merge まで持っていけなかったことが心残りです. 設計をしてレビューのフェーズで大量に時間を使ってしまったのがよくなかったなって感じです. 今の自分ができることと,できないことがはっきりしたのでそういう意味では良かったかなとおもっています.
前々から興味のあったミドルウェア開発を経験できたことは(しかもFluentdで,しかもTDで)とても幸運で,最高の経験だったと思っています. 開催されるかしらないですが,もし来年も開催されならとりあえず出してみると意外とインターン行けるかもしれないので,来年も学生の皆様はぜひ.
まとめ
特にまとめることもないですが,とても刺激的なインターンだったということが伝われば幸いです. 周りは全員超すごい人ばかりだったので,「(業務中自分の力の無さに)おちこんだりもしたけれど、私はげんきです。」という感じです. 社員のみなさん,同期の2人にはとてもお世話になりました.ありがとうございました.
付録1(愉快な仲間たち)
僕の他に2人,インターン同期がいました. 彼らが先に書いたブログがあって僕のより数倍いいのでそちらもぜひ.
@amay382 iPhone7とiOSのことをめちゃくちゃ煽る人(年下なのに優秀でつらい)
トレジャーデータでインターンしてた話 #td_intern - 水底
@takuti オタクかヤンキーかで言えばオタクの人(英語が引くほどうまい)
Treasure Dataインターンにみる機械学習のリアル #td_intern | takuti.me
2人とも機械学習(系?っていうの?あってる?)をやってたので,「インターンでは何やるの?」って聞いたんですけど,丁寧に教えてもらった割に何言ってるよくわからず「すごそう」くらいしか感想がなかったのできっとすごいんだろうなって思ってました.
付録2(食)
牡蠣が苦手だった僕も牡蠣が食べられるようになりました。
#td_intern 最高で具体的には苦手だった牡蠣が食べられるようになるくらい最高 https://t.co/K0BVQ8sfAN
— がんま (@ganmacs) 2016年9月30日
以下、 ログの重要性について真面目にディスカッションしていたときの図です!!!!