erlang - ets dets

ets (erlang term storage) 與 dets (disk ets) 是用來負責大量 Erlang Term 的儲存機制。兩個都是提供大量的 key-value 尋找表，ETS 放記憶體, DETS 放 disk，都可被數個 process 共享，ETS 與 DETS 是 key-value 結構，只是 erlang tuples 的集合。

存在 ETS 表內的資料，是短暫的 transient，當 ETS 被 disposed，資料就會被刪除，而 DETS 內的資料是永續 persistent 的，即使erlang crash，資料也不會受損，在啟動 DETS 時，會自動檢查資料一致性 consistency，如果資料有問題，就會試圖維修，因為所有表格都要被檢查，這個動作會花上一些時間，但系統 crash 之前的最後一筆資料可能會遺失。

當系統 crash 而需要重置時，DETS 就會需要花上一些時間，才能將啟動的程序做完。

如果 APP 以 erlang 原生的機制：nondestructive assignment 與 pure erlang data structure 實作時，發現有實作的困難，而且需要高效率處理大量的資料，就可以使用 ETS。

ETS 並不是用 erlang 實作的，內部也跟普通的 erlang 物件不一樣，而且 ETS 並沒有 garbage collection 的機制，不會因為 gc 而影響效率。

基本操作

1. 建立新 table 或開啟舊 table
   ets:new 或 dets:open_file
2. 對某個 table 插入 tuple/tuple list
   insert(Tablename, X) ，其中 X 是一個 tuple/tuple list
3. 對某個 table 查詢，以取得 tuple list
   lookup(TableName, Key) ，回傳符合 Key 的 tuple list
4. 銷毀一個 table
   ets:delete(TableId) 或 dets:close(TableId)

table 型別

基本型別有兩種(1) set: key 不可重複 (2) bag: 允許數個 tuple(值組) 有相同的 key

set 或 bag 都有兩種變形, 所以有四種表格

1. set：所有的 key 都不一樣
2. ordered set：tuple 會根據 key 值被排序
3. bag：key 可以重複
4. duplicate bag：key 跟 tuple 都可以重複

-module(ets_test).
-export([start/0]).

start() ->
    lists:foreach(fun test_ets/1,
                  [set, ordered_set, bag, duplicate_bag]).

test_ets(Mode) ->
    TableId = ets:new(test, [Mode]),
    ets:insert(TableId, {a,1}),
    ets:insert(TableId, {b,2}),
    ets:insert(TableId, {a,1}),
    ets:insert(TableId, {a,3}),
    List = ets:tab2list(TableId),
    io:format("~-13w  => ~p~n", [Mode, List]),
    ets:delete(TableId).

測試

1> ets_test:start().
set            => [{b,2},{a,3}]
ordered_set    => [{a,3},{b,2}]
bag            => [{b,2},{a,1},{a,3}]
duplicate_bag  => [{b,2},{a,1},{a,1},{a,3}]
ok

ETS 表格的效率考量

在系統內部，ETS 表格是用 hash 表格呈現的(ordered set 例外, 內部使用的是平衡二元樹)，這表示使用 set，空間有浪費，而使用 ordered set，時間有浪費。

插入 set，耗費的時間是固定的，插入ordered set，表格內的項目越多，花的時間越多。

bag 每次有新的元素加入，都要比對是否重複，如果相同 key 的值組很多，就會很耗時間，而 duplicate bag 插入資料所花的時間就比較短。

ETS 的 owner 是建立它的行程，行程死亡或呼叫 ets:delete，表格就會被刪除。

ETS 不是 gc 處理的對象，即使有大量資料存在 ETS 裡面，也不會因為 garbage collection 影響效率。

當一個 tuple 插入到ETS表，代表此 tuple 的所有資料結構從行程堆疊被複製到 ETS 表。進行 lookup 時，結果的 tuple 會從 ETS 複製到行程的堆疊 & heap，除了 binary 資料之外的所有資料結構都是這樣。

大型二元資料會存在獨立的 heap 儲存區域，此區域可被數個行程及 ETS表共享，「計算參考個數」的gc會管理個別的二元資料，當使用到此 binary 的行程和表格的總數量降為 0 時，此儲存區域會被回收。

換句話說：「含有大型二元資料」的訊息，成本很低。在 tuple 插入包含二元的資料到 ETS 表中，也很便宜。

原則：盡可能地使用二元，來表示字串&大型的無型別記憶體區塊。

建立 ETS表

呼叫 ets:new 的行程被認為是該 table 的 owner，如果 owner process 死亡，table 的空間就會自動被回收。

@spec ets:new(Name, [Opt]) -> TableId
    Name 是 atom
    [Opt]是選項清單
        set | ordered_set | bag | duplicate_bag
        private        -> 只有 owner 行程可以讀寫
        public        -> 只要知道 TableId 都可以讀寫此table
        protected    -> 只有 owner 行程可以讀寫，其他行程可以讀取資料
        named_table    -> 可使用 Name 作為後續的操作
        {keypos, K}    -> 把 K 當作 key的位置，正常狀況 K 為 1

        預設值    [set, protected, {keypos,1}]

public table 因任何行程都可以讀寫，使用者必須自己確定此 table 的讀寫有一致性，資料才不會亂掉。

最常使用的是 protected，因為只有 owner 行程可以改變 table 的資料，而所有行程都可以讀取資料，資料是共享的，成本幾乎為 0。

ets 範例: trigram

功能：寫一個探索程式，試圖預測某個字串是否為一個英文單字

方法：使用三個字母組成的序列 trigram，測試字串中所有連續字母的序列，是否符合「產生自大量英文字」的 trigram 集合

程式：從一個很大的英文字集合中，找出所有 trigram

1. 做一個 iterator，在英文字典中，取得所有 trigram
2. 建立 ETS，型別是集合 & 有序集合，代表所有的 trigram，建立一個集合包含所有的 trigram
3. 測量建立這些不同表格所需的時間
4. 測量存取這些不同表格所需要的時間
5. 根據量測結果，選取最佳者，並為它寫存取常式

-module(lib_trigrams).
-export([for_each_trigram_in_the_english_language/2,
         make_tables/0, timer_tests/0,
         open/0, close/1, is_word/2,
         how_many_trigrams/0, 
         make_ets_set/0, make_ets_ordered_set/0, make_mod_set/0,
         lookup_all_ets/2, lookup_all_set/2
        ]).
-import(lists, [reverse/1]).

% 測量產生 set, ordered set, 或使用 erlang sets 模組 所要花的時間，以及平均每個 trigram 耗用的位元組大小
make_tables() ->
    {Micro1, N} = timer:tc(?MODULE, how_many_trigrams, []),
    io:format("Counting - No of trigrams=~p time/trigram=~p~n",[N,Micro1/N]),

    {Micro2, Ntri} = timer:tc(?MODULE, make_ets_ordered_set, []),
    FileSize1 = filelib:file_size("trigramsOS.tab"),
    io:format("Ets ordered Set size=~p time/trigram=~p~n",[FileSize1/Ntri, 
                                                           Micro2/N]),

    {Micro3, _} = timer:tc(?MODULE, make_ets_set, []),
    FileSize2 = filelib:file_size("trigramsS.tab"),
    io:format("Ets set size=~p time/trigram=~p~n",[FileSize2/Ntri, Micro3/N]),

    {Micro4, _} = timer:tc(?MODULE, make_mod_set, []),
    FileSize3 = filelib:file_size("trigrams.set"),
    io:format("Module sets size=~p time/trigram=~p~n",[FileSize3/Ntri, Micro4/N]).

% 測量 lookup 每一個 trigram 所要花的平均時間
timer_tests() ->
    time_lookup_ets_set("Ets ordered Set", "trigramsOS.tab"),
    time_lookup_ets_set("Ets set", "trigramsS.tab"),
    time_lookup_module_sets().

time_lookup_ets_set(Type, File) ->
    % 以 ets:file2tab 將 檔案轉換為 table
    {ok, Tab} = ets:file2tab(File),
    % table 換成 list
    L = ets:tab2list(Tab),
    Size = length(L),
    % 開始測量 lookup 的總時間
    {M, _} = timer:tc(?MODULE, lookup_all_ets, [Tab, L]),
    io:format("~s lookup=~p micro seconds~n",[Type, M/Size]),
    ets:delete(Tab).

lookup_all_ets(Tab, L) ->
    lists:foreach(fun({K}) -> ets:lookup(Tab, K) end, L).

time_lookup_module_sets() ->
    % 讀取檔案，取得 Bin
    {ok, Bin} = file:read_file("trigrams.set"),
    % binary_to_term 換成 sets
    Set = binary_to_term(Bin),
    % sets:to_list 換成 list
    Keys = sets:to_list(Set),
    Size = length(Keys),
    % 開始測量 lookup 的總時間
    {M, _} = timer:tc(?MODULE, lookup_all_set, [Set, Keys]),
    io:format("Module set lookup=~p micro seconds~n",[M/Size]).

lookup_all_set(Set, L) ->
    lists:foreach(fun(Key) -> sets:is_element(Key, Set) end, L).

% 計算總共有幾個 trigrams
how_many_trigrams() ->
    F = fun(_, N) -> 1 + N  end,
    for_each_trigram_in_the_english_language(F, 0).

%% ==========================
% 利用 trigrams 建立 set, ordered set table
make_ets_ordered_set() -> make_a_set(ordered_set, "trigramsOS.tab").
make_ets_set()         -> make_a_set(set, "trigramsS.tab").

make_a_set(Type, FileName) ->
    % 建立 set 或 ordered set 的 table
    Tab = ets:new(table, [Type]),
    % 定義 fun，將 Str 轉換為 binary ，然後以 {Key} 形式的 tuple 存到 ets Tab 裡面
    F = fun(Str, _) -> ets:insert(Tab, {list_to_binary(Str)}) end,
    % 將 F 送入 for_each_trigram_in_the_english_language
    for_each_trigram_in_the_english_language(F, 0),
    % 把 Table 的資料，轉存到 Filename 檔案裡面
    % Dumps the table Tab to the file Filename
    ets:tab2file(Tab, FileName),

    % 查詢 Tab 的 size
    Size = ets:info(Tab, size),
    % 刪除 Tab
    ets:delete(Tab),
    % 把 Size 傳回去
    Size.

% 改用 sets 模組來存放 trigrams
make_mod_set() ->
    D = sets:new(),
    F = fun(Str, Set) -> sets:add_element(list_to_binary(Str),Set) end,
    D1 = for_each_trigram_in_the_english_language(F, D),
    % term_to_binary 把 sets 轉成 binary，然後再寫入到檔案中
    file:write_file("trigrams.set", [term_to_binary(D1)]).

%% ==========================
%% An iterator that iterates through all trigrams in the language
%%     將英文中每個 trigram 套用 fun F
%        F 是 fun(Str,A) -> A
%        Str 的範圍遍及語言中所有 trigram，A是 accumulator
%    使用 354984 個英文字產生 trigram

for_each_trigram_in_the_english_language(F, A0) ->
    {ok, Bin0} = file:read_file("354984si.ngl.gz"),
    % 以 zlib:gunzip 解壓縮
    Bin = zlib:gunzip(Bin0),
    scan_word_list(binary_to_list(Bin), F, A0).

scan_word_list([], _, A) ->
    A;
scan_word_list(L, F, A) ->
    {Word, L1} = get_next_word(L, []),
    % Word 就是 reverse([$\s|L])
    % 把 $\s 加到 Word 前面，就等於  $\s + L + $\s
    % 每個單字的前後刻意加上一個空白字元，在這裡刻意將空白字元當作正常的字母
    A1 = scan_trigrams([$\s|Word], F, A),
    % 處理完成，取得 $\s + L + $\s 的所有 trigram 後，再繼續處理下一個 word
    scan_word_list(L1, F, A1).

%% scan the word looking for \r\n
%% the second argument is the word (reversed) so it
%% has to be reversed when we find \r\n or run out of characters
% 取得下一行的單字
% 一個字元一個字元慢慢累加到 L，如果 pattern 吻合 [\r\n|T]，
% 就代表到該行行末，這時候就回傳 reverse([$\s|L])
% $\s 是一個空白字元，就等於把空白字元加到 L 前面，然後再 reverse 這個 list

get_next_word([$\r,$\n|T], L) -> {reverse([$\s|L]), T};
get_next_word([H|T], L)       -> get_next_word(T, [H|L]);
% 最後一行的 word 沒有行末的 $\r $\n，最後會是 []，因此就直接回傳 reverse([$\s|L])
get_next_word([], L)          -> {reverse([$\s|L]), []}.

% 三個字元的 list
scan_trigrams([X,Y,Z], F, A) ->
    F([X,Y,Z], A);
% 超過三個字元的 list
scan_trigrams([X,Y,Z|T], F, A) ->
    A1 = F([X,Y,Z], A),
    scan_trigrams([Y,Z|T], F, A1);
% 其他狀況的 list，就直接把 accumulator A 傳回去
scan_trigrams(_, _, A) ->
    A.

%% ==========================
%% access routines
%%   open() -> Table
%%   close(Table)
%%   is_word(Table, String) -> Bool

is_word(Tab, Str) -> is_word1(Tab, "\s" ++ Str ++ "\s").

is_word1(Tab, [_,_,_]=X) -> is_this_a_trigram(Tab, X);
is_word1(Tab, [A,B,C|D]) ->
    case is_this_a_trigram(Tab, [A,B,C]) of
        true  -> is_word1(Tab, [B,C|D]);
        false -> false
    end;
is_word1(_, _) ->
    false.

is_this_a_trigram(Tab, X) ->
    % 以  lookup 的方式，確認是不是在 字典產生的所有 trigram 裡面
    case ets:lookup(Tab, list_to_binary(X)) of
        [] -> false;
        _  -> true
    end.

open() ->
    % filename:dirname(code:which(?MODULE)) 可取得載入目前模組的目錄
    {ok, I} = ets:file2tab(filename:dirname(code:which(?MODULE)) 
                               ++ "/trigramsS.tab"),
    I.

close(Tab) -> ets:delete(Tab).

建立 table 要花的時間

測量產生 set, ordered set, 或使用 erlang sets 模組 所要花的時間，以及平均每個 trigram 耗用的位元組大小

1> lib_trigrams:make_tables().
Counting - No of trigrams=3357707 time/trigram=0.30437438406626904
Ets ordered Set size=19.029156153630503 time/trigram=1.0733515461593284
Ets set size=19.028408559947668 time/trigram=0.7421731556684368
Module sets size=9.433978132884777 time/trigram=2.5252352274930483
ok

總共有 3357707 個trigram，每個trigram處理了 0.3 sec。
在 ordered set，插入一個 trigram 要花 1.07 sec，耗用 19.029 bytes
在 set，插入一個 trigram 要花 0.74 sec，耗用 19.028 bytes
在 sets，插入一個 trigram 要花 2.52 sec，耗用 9.433 bytes

存取 table 要花的時間

2> lib_trigrams:timer_tests().
Ets ordered Set lookup=0.6541444724792076 micro seconds
Ets set lookup=0.37379684141669 micro seconds
Module set lookup=0.5606952621250351 micro seconds
ok

結果

ETS set 的效能最好

預測某個字串是否為一個英文單字

3> Table=lib_trigrams:open().
32784
4> lib_trigrams:is_word(Table, "test").
true
5> lib_trigrams:is_word(Table, "tess").
true
6> lib_trigrams:is_word(Table, "ess").
true
7> lib_trigrams:is_word(Table, "esx").
false
8> lib_trigrams:is_word(Table, "esxit").
false
9> lib_trigrams:close(Table).
true

DETS

DETS 將 erlang tuple 儲存在 disk 裡面，檔案最大的體積為 2GB，必須先開啟才能使用，使用完畢也要關閉檔案。如果沒有正確關閉，下次開啟會自動修復，但會花費一些時間。

當一個 DETS 表被開啟，必須指定一個全域的名稱，如果兩個以上的本地行程用相同名稱 & 選項開啟一個 DETS，這些行程就會共享表格，此表格會一直開啟，直到所有行程把表格關閉/行程當機後，才真正地關閉。

範例：檔名索引

建立一個磁碟式表格，將檔案對應到整數，或反向對應：filename2index & index2filename。

建立一個 DETS表，在內部放入三個不同型別的值組 tuple

{free, N}
    N 是表格中的第一個自由的索引，當我們在表格中輸入一個新檔名，會被指定索引 N

{FileNameBin, K}
    FileNameBin(二元) 被指定索引 K

{K, FileNameBin}
    K (整數) 代表檔案 FilenameBin

注意每個新檔案的加入，如何在表格內加入兩個項目：
File -> Index
Index -> Filename

先寫一個程式，會開啟/關閉「儲存所有檔案名稱」的 DETS表

-module(lib_filenames_dets).
-export([open/1, close/0, test/0, filename2index/1, index2filename/1]).

open(File) ->
    io:format("dets opened:~p~n", [File]),
    Bool = filelib:is_file(File),
    % ?MODULE 會自動展開成 lib_filenames_dets，因為 DETS 必須要有一個唯一的 table 名稱
    % 而 模組名稱也是唯一的，所以就使用 ?MODULE 來當作 Table 名稱
    case dets:open_file(?MODULE, [{file, File}]) of
        % 開啟 dets，但以 filelib:is_file 判斷是不是新的檔案
        % 如果檔案原本不存在，就 insert 一個 {free,1} 來初始化這個 DETS
        {ok, ?MODULE} ->
            case Bool of
                true  -> void;
                false -> ok = dets:insert(?MODULE, {free,1})
            end,
            true;
        {error,_Reason} ->
            io:format("cannot open dets table~n"),
            exit(eDetsOpen)
    end.

close() -> dets:close(?MODULE).

% 為求高效率，檔名必須要是 binary
% 在 ETS, DETS 裡面，要習慣用 binary 來表示字串
%% 注意: 這裡可能會產生 race condition，在 dets:insert 被呼叫前，
%% 如果有兩個平行的 process 呼叫了 dets:lookup，filename2index將產生錯誤的結果
filename2index(FileName) when is_binary(FileName) ->
    case dets:lookup(?MODULE, FileName) of
        [] ->
            [{_,Free}] = dets:lookup(?MODULE, free),
            ok = dets:insert(?MODULE,
                             [{Free,FileName},{FileName,Free},{free,Free+1}]),
            Free;
        [{_,N}] ->
            N
    end.

% 將索引值換成檔名
index2filename(Index) when is_integer(Index) ->
    case dets:lookup(?MODULE, Index) of
        % 發生錯誤時，回傳 error
        []        -> error;
        [{_,Bin}] -> Bin
    end.

test() ->
    file:delete("./filenames.dets"),
    open("./filenames.dets"),
    F = lib_files_find:files(".", ".ebeam$", true),
    lists:foreach(fun(I) -> filename2index(list_to_binary(I)) end, F).

測試

1> lib_filenames_dets:test().
dets opened:"./filenames.dets"
ok

ETS 與 DETS 的其他功能

1. 根據 pattern 來取出或刪除物件
2. 在 ETS 與 DETS 之間做轉換，或是在 ETS 與磁碟檔案之間做轉換
3. 為一個 Table 找出 resource usage
4. traverse Table 內的元素
5. 修復破碎的 DETS table
6. 視覺化 Table

ETS 與 DETS 原本是設計用來實現 Mnesia 的，Mnesia 內部使用了 ETS 與 DETS Table，並把一些細節隱藏起來，提供了高階的功能。

參考

Erlang and OTP in Action
Programming Erlang: Software for a Concurrent World