Go to Qiita Advent Calendar 2024 Top
LoginSignup
11
10

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

ErlangAdvent Calendar 2014

Day 13
@sile

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

Last updated at Posted 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

実行例

%% 構築
> 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

実装上の特徴

実行例

%% デコード
> 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}]

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

11
10
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
11
10

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?