More than 5 years have passed since last update.

Erlangで書かれた自作ライブラリ群の紹介

Erlang

Last updated at 2015-01-28Posted at 2014-12-13

この場を借りて、以下の条件に合致する自作ライブラリ群の紹介をさせて貰います。

Erlangで記述されている
一年以内に更新があった
ある程度汎用性が高い
ある程度(最低限)ステーブル
rebarの構成に準拠

※ 諸事情で準備時間があまりとれなかったため、今回は本当に軽い紹介だけで、あまり有益な情報はないです...

hash_ring

https://github.com/sile/hash_ring
コンシテントハッシュ法の実装ライブラリ
現状備えている機能
- ノードの追加・削除
- 特定のキーに対するプライマリノードの検索や優先順位に基づくノードの畳み込み
- 各ノードの重み付け
- ハッシュアルゴリズムや仮想ノード数の指定

実装上の特徴

Pure-Erlang and No-ETS
- 副作用なし
仮想ノード群を保持するためにタプルを使っている
- ノード数が100で、個々の仮想ノード数が256なら、約2.5万要素のタプルができる
- ノードの追加は重い(巨大なタプルの更新が必要)が、検索は効率的
  - タプル内の要素はソートされており、二分探索が可能
  - 実際には、(ハッシュ関数の性質上)仮想ノード群の分布が一様だという仮定のもと、より効率的な探索を行っている
    - TODO: この辺りの詳細は別途どこかで
- メモリ消費量も(Pure-Erlangでは)最小限に近い

実行例

%%%
%%% 基本的な使い方
%%%
%% ハッシュリングの作成
> Nodes = lists:map(fun hash_ring_node:make/1, [a,b,c,d,e]).
[{hash_ring_node,a,a,1},
 {hash_ring_node,b,b,1},
 {hash_ring_node,c,c,1},
 {hash_ring_node,d,d,1},
 {hash_ring_node,e,e,1}]
> Ring0 = hash_ring:make(Nodes).

%% キーを担当するノードを検索する
> hash_ring:find_node(key_1, Ring0).
{ok,{hash_ring_node,c,c,1}}

%% ノードの削除 (and 再検索)
> hash_ring:find_node(key_1, hash_ring:remove_nodes([c], Ring0)).
{ok,{hash_ring_node,b,b,1}}


%%%
%%% 処理性能目安
%%%
%% 構築: ノード数=100
> {Time1, Ring1} = timer:tc(fun() -> hash_ring:make(lists:map(fun hash_ring_node:make/1, lists:seq(1, 100))) end).
> Time1 / 1000000. % 秒単位に変換
0.144733  % 0.144秒

%% 検索: 検索回数=10万回
> Keys = lists:seq(1, 100000).
> {Time2, _} = timer:tc(fun () -> lists:foreach(fun (Key) -> hash_ring:find_node(Key, Ring1) end, Keys) end).
> Time2 / 1000000.
0.399199  % 0.399秒 (25万/秒)


%%%
%%% バラつき度目安
%%%
> lists:sort(
    dict:to_list(
      lists:foldl(fun (K, Acc) -> dict:update_counter(K, 1, Acc) end,
                  dict:new(),
                  [begin {ok, N} = hash_ring:find_node(Key, Ring1), hash_ring_node:get_key(N) end || Key <- Keys]))).
[{1,1068},  % おおよそ均等？
 {2,923},
 {3,942},
 {4,1006},
 {5,1084},
 {6,928},
 {7,969},
 {8,1031},
 {9,954},
 {10,995},
 {11,962},
 {12,1009},
 {13,974},
 {14,975},
 {15,1032},
 {16,997},
 {17,1030},
 {18,1012},
 {19,994},
 {20,953},
 {21,1038},
 {22,955},
 {23,1033},
 {24,959},
 {25,950},
 {26,1019},
 {27,980},
 {28,...},
 {...}|...]

hashtrie

https://github.com/sile/hashtrie
多言語で云うハッシュマップ的なデータ構造 (ハッシュ関数 + トライ木)
もともとはHash Array Mapped Trieに影響を受けて実装
ベンチマーク性能はそこそこ良かった
- ただし標準ライブラリに含まれているdictやgb_treesに比べて劇的に高速、という程でもないので、わざわざ使う必要性はあまりないかもしれない

実行例

%% 構築
> Trie0 = hashtrie:new().
{hashtrie,0,64,0,
          {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]}}

%% 要素追加
> Trie1 = hashtrie:store(key, value, Trie0).
{hashtrie,1,64,0,
          {[],[],[],[],[],[],[],[],[],
           [{key,value}],
           [],[],[],[],[],[]}}.

%% 要素検索
> hashtrie:find(key, Trie1).
{ok,value}

> hashtrie:find(hogge, Trie1).
error

jsone

https://github.com/sile/jsone
かなり単機能なJsonライブラリ
Pure-Erlangで実装されたものの中では高速

実装上の特徴

もともとはテキスト形式のプロトコルのデコード処理を、Erlangのみでどこまで高速に実装できるかを試すために作成した
- jsone_decode.erlは類似のモジュールを実装したい場合のリファレンス実装的な位置づけ（にしたい）
主に以下の点に気をつけて実装されている
- デコード中のメモリ割当の最小化
- bin_opt_infoオプション付きでコンパイルした場合に出力される警告(バイナリ処理最適化関連)には可能な限り対応
- HiPEコンパイル時のエラー情報の欠落の緩和
最適化周りの詳細は以下の記事を参照
- Erlangコード最適化メモ: JSONデコード処理(1): まず基本形
- Erlangコード最適化メモ: JSONデコード処理(2): HiPEを使う
- Erlangコード最適化メモ: JSONデコード処理(3): JSON文字列パースの効率化
- TODO: CPS周り(bin_opt_info, HiPE時のエラー情報云々)

実行例

%% デコード
> jsone:decode(<<"[1,2,3]">>).
[1,2,3]

%% エンコード
> jsone:encode([1,2,3]).
<<"[1,2,3]">>

local

https://github.com/sile/local
プロセス名を管理するためのライブラリ
- erlang:register/2とは異なり、(アトム以外の)任意の名前を付与することが可能
- globalとは異なり名前のスコープはローカルノード限定
- プロセス名は、登録時に指定した名前管理プロセス毎に管理される
  - 特定の名前管理プロセスを、自分のアプリケーションの監視ツリーに組み込むことが容易
    - プロセス名のスコープをアプリケーションローカルに限定可能
- gen_server等経由で生成されるプロセスの名前({via, module(), Name})を管理するためにも利用可能
  - viaで参照されるモジュールに要求される右の関数群を備えている: register_name/2,unregister_name/1,whereis_name/1,send/2
gprocでいいという話もある

実装上の特徴

プロセス名管理サーバ(local_name_server.erl)は、名前とPIDの対応付けにETSを使っていて、検索要求に最適化されている
- namedおよびprotectedなテーブルを使うことで、検索時にプロセス間通信が発生しないようになっている
- read_concurrencyオプションにはtrueを指定
- この辺りの最適化の話の詳細は以前に書いた記事を参照のこと

実行例

$ make start

%% 名前管理サーバプロセスを起動
> local:start_name_server(sample_ns).
ok

> local:which_name_servers().
[sample_ns].

%% 名前登録
> self().
<0.33.0>

> local:register_name({sample_ns, hoge}, self()). % 名前は {名前管理サーバ名, プロセス名} の形式で指定する
yes

> local:register_name({sample_ns, [a,b,c]}, spawn(timer, sleep, [infinity])). % アトム以外のプロセス名も可
yes

%% 検索
> local:whereis_name({sample_ns, hoge}).
<0.33.0>

> local:whereis_name({sample_ns, fuga}).
undefined  % 未登録

%% 登録済みプロセス一覧を取得
> local:which_processes(sample_ns).
[{[a,b,c],<0.42.0},{hoge, <0.33.0>}].

> local:which_processes(sample_ns, ['_','_','_']). % パターン(ets:match_pattern/0)で絞り込むことも可
[{[a,b,c],<0.42.0>}]

%% 登録解除
> local:unregister_name({sample_ns, hoge}).
ok
> local:whereis_name({sample_ns, hoge}).
undefined

%% local:name_server_child_spec/1は、監視ツリーに名前管理プロセスを登録する際の推奨ChildSpecを返す
> local:name_server_child_spec(sample_ns).            
{sample_ns,{local_name_server,start_link,[sample_ns]},
           permanent,5000,worker,
           [local_name_server]}

logi

https://github.com/sile/logi
ログ出力用のインタフェースライブラリ
- 論理的なログ出力内容(ログレベル, ログメッセージ)を指定するためのインタフェースだけを提供するのが目的
- ログの出力先やフォーマット処理等は、別ライブラリ(ex. logi_tty)に切り離されている
lagerを使っている時に、(少なくとも当時は)以下のような不満があったため独自に実装中
- ログの出力先やログレベル等を細かく制御することができない (VM上で一つのlagerインスタンスしか保持できない)
  - アクセスログとアプリケーションログで出力先や出力フォーマットを分けたい
  - ライブラリ毎にログの出力先を分けたい
    - かつ、ログの出力先等は、ライブラリの利用者側から指定したい
  - 特定のライブラリやプロセスだけログ出力レベルを変更したい
- ログファイルの命名形式が固定 (ex. "日時-ファイル名" といったような独自の形式を使用することが困難)
- ログメッセージに共通ヘッダを付けるためのサポートが不十分
  - メタデータ機能を使えば実現できなくはないが、作り込みが必要
  - またスコープがプロセスに固定なので、例えばgen_eventのハンドラ毎に異なるヘッダを設定することはできない
- 外部ライブラリでもロガーを気軽に利用可能にしたい
  - サーバよりのライブラリを実装している場合は、ログ出力を行いたくなる時がある
  - lagerは単一リポジトリに結構何でも入っているためサイズが大きく、更新頻度もそこそこ高い
    - そのためライブラリがlagerに依存してしまうと、それを利用しているアプリケーション側でlagerのバージョン衝突が発生する危険性がある
  - ログ出力のインタフェース部分だけを切り出し、かつ、その部分を十分にしっかりと設計しておけば、logi本体の更新はほぼなくせるはず（と期待）
現時点では、まだまだ完成度が高くないので、lagerを使うのが無難

使用例

erl -pa ebin /path/to/logi_tty/ebin

> applicatoin:ensure_all_started(logi_tty).
{ok, [logi, logi_tty]}

> logi:info("hello"). % まだ何も表示されない
logi_default_logger

> logi_tty:install(info). % infoレベル以上のログは、端末に出力されるようにバックエンドを登録
ok

> logi:info("hello"). % 表示される
2014-12-14 03:24:24.310 [info] nonode@nohost <0.33.0> undefined:0 [] hello
logi_default_logger

> logi:debug("hello"). % infoレベル以下は表示されない
logi_default_logger

%% ヘッダ設定
> logi:set_headers([{key1, val1},{key2,val2}]).
> logi:info("hello").
2014-12-14 03:25:24.410 [info] nonode@nohost <0.33.0> undefined:0 [key1=val1,key2=val2] hello
logi_defaul_logger

%%% ログ出力先の変更
> logi:start_logger(hoge_logger). % 別のロガーを起動 (logi_default_loggerは最初に自動で起動している)
ok

> logi:which_loggers().
[hoge_logger,logi_default_logger]

> logi:info(hoge_logger, "hello", []). % 出力先ロガーを指定して実行: まだ何も表示されない
hoge_logger

> logi_tty:install(hoge_logger, debug). % debugレベルでバックエンドを登録
ok

> logi:debug(hoge_logger, "hello", []). % こっちはdebugレベルでも出力される
2014-12-14 03:29:16.868 [debug] nonode@nohost <0.54.0> undefined:0 [] hello
hoge_logger

proxy

https://github.com/sile/proxy
呼び出し元プロセスと実プロセスの間に、中継プロセスをおいて、様々なフック処理を挟み込めるようにするためのライブラリ
- 今のところは、主に実プロセスの生存管理周りの共通処理を括り出すために使用することが多い
  - 細やかな and 呼び出し元プロセスに透過的な再起動管理 (proxy_restart.erl)
  - 実プロセスの開始時刻および停止時刻の指定 (proxy_lifetime.erl)
- proxyビヘイビアを実装することで任意のフック処理を挟むことが可能
まだ実験的 and もう一度くらい大幅にリファクタリングする予定

実行例

$ ./rebar shell

%% 実プロセスの起動時刻を指定する
> After = fun (Seconds) -> {Mega, Sec, Micro} = now(), {Mega, Sec + Seconds, Micro} end.

> proxy:spawn(erlang, apply,
              [fun (Start) -> io:format("~p hello: ~p sec\n", [self(), timer:now_diff(now(), Start) / 1000000]) end,
               [now()]], % 呼び出し時刻を渡す
             [{proxy_lifetime, [{start_time, After(5)}]}]).  % 五秒後に起動するように指定
<0.119.0> % 呼び出し元に返されるのはプロキシプロセスのPID
<0.121.0> hello: 5.001993 sec % 実プロセスは五秒後に起動

%% 再起動回数を指定する
> proxy:spawn(io, format, ["hello\n"],
              [{proxy_restart, [{max_restart, 3}]}]). % 三回までは再起動する
<0.122.0>
hello
hello
hello

%% プロキシプロセスは、受け取ったメッセージを実プロセスに転送する
> Pid = proxy:spawn(fun () -> receive Msg -> io:format("~p received: ~p\n", [self(), Msg]) end end, []).
> Pid ! hello.
<0.131.0> received: hello
hello

safeexec

https://github.com/sile/safeexec
外部コマンドの呼び出しを安全に行えるようにするためのライブラリ
- 呼び出し元プロセスが死んだ場合やerlang:close_port/1が呼ばれた場合には、外部コマンドも確実に終了する
- リーク防止
外部コマンドを起動するためのインタフェースはerlang:open_port/2とほぼ同様

実装上の特徴

呼び出し元のプロセスの終了を確実にハンドリングするために、呼び出し元プロセスと外部コマンドの間に、safeexecという名前のコマンドを挟んでいる
- 外部コマンドの起動を直接行なうのは、このsafeexecコマンド
  - そのため、一度のsafeexec:open_port/2呼び出しで、実際には二つの外部コマンドが起動することになる
- ソースコードはsrc/safeexec.c
- safeexecコマンドは、標準入力の状態を監視している
  - 標準入力 = 呼び出し元Erlangプロセスとのやりとりに使われるファイルディスクリプタ(の一つ)
  - 標準入力がEOF状態になったら、呼び出し元プロセスが終了したものと判断して、起動した外部コマンドを終了する(シグナルを送る)
- 状態の監視にepollを使っているため、Linux以外では動作しない

実行例

$ ./rebar shell

%%%
%%% erlang:open_port/2の場合の挙動
%%%
%% 適当に長い時間を指定して、sleepコマンドを起動
> Port0 = erlang:open_port({spawn_executable, "/bin/sleep"}, [{args, ["1000"]}]).
#Port<0.5076>

> erlang:port_info(Port0).
[{name,"/bin/sleep"},
 {links,[<0.39.0>]},
 {id,40608},
 {connected,<0.39.0>},
 {input,0},
 {output,0},
 {os_pid,11118}] % プロセスIDは'11118'

> io:format(os:cmd("ps | grep sleep")). 
11118 ?        00:00:00 sleep   % sleepは起動している
ok

%% ポート停止
> erlang:port_close(Port0).
true

> erlang:port_info(Port0).
undefined  % ポートは閉じている

> io:format(os:cmd("ps | grep sleep")).
11118 ?        00:00:00 sleep  % sleepは生存している
ok

%% 呼び出し元プロセス停止
> exit(kill).
** exception exit: kill

> io:format(os:cmd("ps | grep sleep")).
11118 ?        00:00:00 sleep  % まだsleepは生存している
ok

%% 仕方がないのでkillコマンドで停止
> os:cmd("kill 11118").
> io:format(os:cmd("ps | grep sleep")).
ok


%%%
%%% safeexec:open_port/2の場合の挙動
%%%
> Port1 = safeexec:open_port({spawn_executable, "/bin/sleep"}, [{args, ["1000"]}]). % 指定する引数は同様
#Port<0.5769>

> erlang:port_info(Port1).
[{name,"/path/to/safeexec/priv/safeexec"}, % Erlangが直接起動するのはsafeexecコマンド
 {links,[<0.76.0>]},
 {id,46152},
 {connected,<0.76.0>},
 {input,0},
 {output,0},
 {os_pid,11282}] % プロセスIDは'11282'

> io:format(os:cmd("ps | grep -E 'safeexec|sleep'")).
11282 ?        00:00:00 safeexec
11283 ?        00:00:00 sleep     % sleepは、safeexecの子プロセスとして起動
ok

%% ポート停止
> erlang:port_close(Port1).
true

> io:format(os:cmd("ps | grep -E 'safeexec|sleep'")). % 外部コマンドも終了
ok

%% 呼び出し元プロセスが終了した場合
> safeexec:open_port({spawn_executable, "/bin/sleep"}, [{args, ["1000"]}]).
> io:format(os:cmd("ps | grep -E 'safeexec|sleep'")).                      
11339 ?        00:00:00 safeexec
11340 ?        00:00:00 sleep
ok

> exit(kill).
** exception exit: kill

> io:format(os:cmd("ps | grep -E 'safeexec|sleep'")). % 外部コマンドも終了
ok

splay_tree

https://github.com/sile/erl-splay-tree
スプレー木の実装ライブラリ
- スプレー木は、汎用的な辞書的なデータ構造としては、バランス木等に比べて性能が劣る(ベンチマーク結果)
- ただし、検索や更新のアクセスパターンが偏っている場合には、良好な性能を発揮するので意外と使い所がある
- 指定したキーの地点で木を分割可能なsplay_tree:split/2も便利 (gb_treesにもこの関数がほしい...)
  - 値の有効期限を管理するためのキュー(優先順位付きキュー)の実装などに向いている
    - 「基本的には末尾への要素追加が主」　and　「定期的に一定区間をまとめて取り出す(split/2)」、というアクセスパターン

実装上の特徴

基本的にはスプレー木の素直な実装（だと思っている）
splay_tree:size/1の実行時間は要素数に比例する
- 深い理由はないけど、少しでも性能を上げるために、あえて利用者側が管理可能な情報をデータ構造側が保持しないようにしてみた
- 今のところは、これであまり困ったことはない

使用例

$ ./rebar shell

%%%
%%% 基本的な使い方 (インタフェース的にはdictに近い)
%%%

%% 構築
> Tree0 = splay_tree:new().
nil

%% 要素追加
> Tree1 = splay_tree:store(key1, value1, Tree0).
{key1,value1}
> Tree2 = splay_tree:store(key2, value2, Tree1).
{key2,value2,{key1,value1},nil}

%% 要素検索
> {_, Tree3} = splay_tree:find(key1, Tree2).
{{ok,value1},{key1,value1,nil,{key2,value2}}} % スプレー木は検索時にも木の部分的なリバランシングが行われる

> Tree2 =/= Tree3.
tree

> splay_tree:lookup(key1, Tree3). % lookup/2を使うことで検索結果だけを取得することも可能だが、基本的には非推奨
{ok, value1}


%%%
%%% 優先順位付きキューとして使用する例
%%%
> Queue0 = splay_tree:from_list([{N, N} || N <- lists:seq(1, 10)]).          
{10,10,
 {9,9,
  {8,8,
   {7,7,
    {6,6,{5,5,{4,4,{3,3,{2,2,{1,1},nil},nil},nil},nil},nil},
    nil},
   nil},
  nil},
 nil}

%% take_smallest/1で先頭要素(= 優先順序が高い要素)を取り出せる
> {Front, Queue1} = splay_tree:take_smallest(Queue0), Front.
{ok,1,1}

%% split/2を使うことで任意の地点で分割可能
> {Queue2, Queue3} = splay_tree:split(4, Queue1).
> splay_tree:to_list(Queue2).
[{2,2},{3,3}]
> splay_tree:to_list(Queue3).
[{4,4},{5,5},{6,6},{7,7},{8,8},{9,9},{10,10}]

あらためて見返してみるとドキュメントが不足しているライブラリが多い...

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up