読み込み(検索)処理の方が圧倒的に多いと予想されるようなKVS的なプロセスを、Erlang/OTPでどうやって効率的に(スケールアップするように)実装するか。
少し前にlocalという、名前のスコープを限定可能なプロセス名管理用ライブラリを実装した時に採用した方法のメモ。

結論

結論を先に書いてしまうと名前付きのETSを使うのが良い。

ETSを名前付き(and access=protected)にしておくことで、テーブルの所有プロセスを経由せずに読み込み処理を行うことが可能となる。
そのため、複数クライアントプロセスから同時に要求が来た場合でも、それらが(メッセージパッシングを通して)直列化されることなく、並列的に処理されることが期待できる。
実際に、今回測定した範囲では、ETSを使うことで読み込み処理はコア数に対してほぼ線形にスケールしていた。

実装例と性能比較

以降は、実際にETSを使ったKVS的プロセスのサンプルコードを載せていく。
また、比較対象としてdictを用いた版の実装および性能測定結果も記載する。

実行環境

EC2のc3.8xlargeインスタンス(vCPU=32)を使用
- 16コア/32スレッド(おそらく)
OS: CentOS6.4-64bit
Erlang/OTP: 17.3, rpm

単体性能

まずはETSとdictの単体性能の比較から始める。

ETSのインターフェースをdictに合わせるために、以下のようなラッパーモジュールを用意。

ets_map.erl

-module(ets_map).

-export([new/0, store/3, find/2]). % dictに合わせた公開関数
-export([new/1]). % 名前付きテーブル生成用関数

%% @doc 名前なしテーブルを生成する (単体性能測定用)
-spec new() -> ets:tid().
new() ->
    ets:new(?MODULE, [set, protected, {read_concurrency, true}]).

%% @doc 名前付きターブルを生成する (サーバ性能測定用)
-spec new(Name::atom()) -> ets:tid().
new(Name) ->
    ets:new(Name, [named_table, set, protected, {read_concurrency, true}]).

-spec store(Key::term(), Value::term(), ets:tid()) -> ets:tid().
store(Key, Value, Map) ->
    true = ets:insert(Map, {Key, Value}),
    Map.

-spec find(Key::term(), ets:tid()) -> {ok, Value::term()} | error.
find(Key, Map) ->
    case ets:lookup(Map, Key) of
        [{_, Value}] -> {ok, Value};
        []           -> error
    end.

測定には、以下のモジュールを使用する。

bench_serial.erl

-module(bench_serial).

-export([bench/3]).
-export([find_loop/4]). % 後で参照したいので公開関数にしておく

%% @doc ベンチマーク関数
%%
%% 一秒間に何回読み込み(検索)処理を行えるかを返す
-spec bench(module(), non_neg_integer(), non_neg_integer()) -> ReadsPerSecond::non_neg_integer().
bench(Module, EntryCount, ReadCount) ->
    %% 最初に要素を登録しておく
    Map =
        lists:foldl(
          fun (I, Acc) -> Module:store(I, I, Acc) end,
          Module:new(),
          lists:seq(0, EntryCount - 1)),

    %% 読み込み性能を測定する
    {Elapsed, _} =
        timer:tc(
           fun () ->
                  find_loop(ReadCount, Module, Map, EntryCount)
           end),

    (ReadCount * 1000 * 1000) div Elapsed.

%% @doc 要素の検索処理を指定回数分だけ行う
-spec find_loop(non_neg_integer(), module(), term(), non_neg_integer()) -> ok.
find_loop(0, _, _, _) ->
    ok;
find_loop(Rest, Module, Map, Limit) ->
    I = Rest rem Limit,
    {ok, I} = Module:find(I, Map),
    find_loop(Rest - 1, Module, Map, Limit).

測定結果:

%% ets_map
> bench_serial:bench(ets_map, 1000, 10000000). % NOTE: 実行が終わっても生成されたETSテーブルは自動では回収されない
3377147 % 337万/sec

%% dict
> bench_serial:bench(dict, 1000, 10000000).
2326308 % 232万/sec

この環境では、ETSの方がdictよりも1.4倍程度の性能が出ていた。
ただし、EC2ではなくローカルのVM環境で試した場合には、逆にdictの方が若干性能が良かった。
また、この辺りの数値は測定方法や各種オプション(ex. dictをhipeコンパイルする)によっても変わってくるはずなので、この結果は「ETSの方が一般にdictよりも性能が良い」として捉えるよりも、あくまでも後続のプロセス化した際の性能測定に対する基準点として見てもらった方が良いと思われる。

KVSプロセスとして性能

次はdictおよびETSをKVSプロセス化した際の読み込み性能の比較。

実装

以下に、それぞれの実装を載せる。

dict_kvs.erl

%% dictを使ったKVS的サーバプロセス (必要最低限の実装)
-module(dict_kvs).

-export([start_link/0, store/3, find/2]).

-record(state, {map :: dict:dict()}).

%%% external functions
-spec start_link() -> {ok, pid()}.
start_link() ->
    Pid = spawn_link(fun() -> loop(#state{map = dict:new()}) end),
    true = register(?MODULE, Pid),  % モジュール名 == プロセス名
    {ok, Pid}.

-spec store(term(), term(), pid()|atom()) -> ok.
store(Key, Value, Server) ->
    _ = Server ! {store, Key, Value},
    ok.

-spec find(term(), pid()|atom()) -> {ok, Value::term()} | error.
find(Key, Server) ->
    % メッセージパッシングを使って、サーバに値を問い合わせる
    Ref = make_ref(),
    _ = Server ! {find, self(), Ref, Key},
    receive
        {Ref, Result} -> Result
    end.

%%% internal functions
-spec loop(#state{}) -> no_return().
loop(State) ->
    receive
        {store, Key, Value} ->
            Map = dict:store(Key, Value, State#state.map),
            loop(State#state{map = Map});
        {find, From, Ref, Key} ->
            _ = From ! {Ref, dict:find(Key, State#state.map)},
            loop(State)
    end.

ets_kvs.erl

%% 名前付きETSを使ったKVS的サーバプロセス (必要最低限の実装)
-module(ets_kvs).

-export([start_link/0, store/3, find/2]).

-record(state, {map :: ets:tid()}).

%%% external functions
-spec start_link() -> {ok, pid()}.
start_link() ->
    Pid = spawn_link(fun() -> loop(#state{map = ets_map:new(?MODULE)}) end),
    true = register(?MODULE, Pid),  % モジュール名 == プロセス名
    {ok, Pid}.

-spec store(term(), term(), pid()|atom()) -> ok.
store(Key, Value, Server) ->
    _ = Server ! {store, Key, Value},
    ok.

-spec find(term(), pid()|atom()) -> {ok, Value::term()} | error.
find(Key, _Server) ->
    %% 検索時にはサーバプロセスに問い合わせることなく、直接ETSテーブルにアクセスする
    ets_map:find(Key, ?MODULE).

%%% internal functions
-spec loop(#state{}) -> no_return().
loop(State) ->
    receive
        {store, Key, Value} ->
            Map = ets_map:store(Key, Value, State#state.map),
            loop(State#state{map = Map}) % dict_kvsに合わせてmapフィールドの更新を行っている(実質的には意味はない)
    end.

測定コード

KVS的プロセスの読み込み(検索)性能測定用コード。
CPUコア数(スレッド数)に対するスケーラビリティを測定できるように、同時アクセスクライアント(プロセス)数が指定可能となっている。

bench_parallel.erl

-module(bench_parallel).

-export([bench/4]).

%% @doc ベンチマーク関数
%%
%% 一秒間に何回読み込み(検索)処理を行えるかを返す
-spec bench(module(), non_neg_integer(), non_neg_integer(), pos_integer()) -> ReadsPerSecond::non_neg_integer().
bench(Module, EntryCount, ReadCount, ClientCount) ->
    %% KVSプロセスの起動
    {ok, Pid} = Module:start_link(),

    %% 最初に要素を登録しておく
    ok = lists:foreach(
           fun (I) -> Module:store(I, I, Pid) end,
           lists:seq(0, EntryCount - 1)),
    _ = timer:sleep(10),

    %% 各クライアントプロセスが担当する読み込み処理の個数を計算する(端数の処理はいい加減)
    PerProcessReadCount = ReadCount div ClientCount,

    %% 読み込み性能を測定する
    {Elapsed, _} =
        timer:tc(
          fun () ->
                  %% クライアントプロセスを起動
                  ok = lists:foreach(
                         fun (_) ->
                                 spawn_monitor(bench_serial, find_loop,
                                               [PerProcessReadCount, Module, Module, EntryCount])
                         end,
                         lists:seq(1, ClientCount)),

                  %% 全てのクライアントの処理が終わるまで待機
                  wait_loop(ClientCount)
          end),

    %% KVSプロセスの停止
    _ = unlink(Pid),
    _ = exit(Pid, kill),

    (ReadCount * 1000 * 1000) div Elapsed.

-spec wait_loop(non_neg_integer()) -> ok.
wait_loop(0) -> ok;
wait_loop(N) ->
    receive
        {'DOWN', _, _, _, normal} -> wait_loop(N - 1)
    end.

測定結果

同時アクセスクライアント数を1から128まで変動させた場合の測定結果:

クライアント数	ets_kvs - 秒間検索数	ets_key - スケール率	dict_kvs - 秒間検索数	dict_kvs - スケール率
1	3,107,163/sec	1.00	433,303/sec	1.00
2	6,203,665/sec	2.00	404,905/sec	0.93
4	12,332,879/sec	3.97	518,766/sec	1.20
8	24,465,091/sec	7.87	602,455/sec	1.39
16	47,723,813/sec	15.36	614,692/sec	1.42
32	61,272,132/sec	19.72	619,699/sec	1.43
64	54,838,191/sec	17.65	626,231/sec	1.45
128	57,763,401/sec	18.59	638,042/sec	1.47

クラスアント数が1の場合の結果を、単体測定時のそれと比較してみると、ets_kvsの方はほとんど差異が見られないが、dict_kvsは間にメッセージパッシングが入ったことにより性能が五分の一程度に落ちてしまっていた。

またets_kvsはクライアント数の増加に応じて、(CPUのコア数の範囲で)良好にスケールしていた。

クライアント側が事前にテーブルの名前を知っていなければならない等の制限があって、必ずしも使い勝手は良くはないが、不特定多数のクライアントからの問い合わせ(READが多数)を処理する必要があるようなサーバプロセスでは、性能向上のために名前付きETSの使用を検討してみるのは悪くはなさそう。