搜云库技术团队
第十五章 ETS和DETS:大数据的存储机制
Table of Contents
- 第十五章 ETS和DETS:大数据的存储机制
- 15.1 表的基本操作
- 创建和打开表
- 插入表
- 查找元组
- 释放表
- 15.2 表的类型
- set表
- ordered set表
- bag表
- duplicate bag表
- 代码示例
- 15.3 ETS表的效率考虑
- 15.4 创建ETS表
- 15.5 ETS程序示例
- 15.5.1 三字索引迭代器
- 15.5.2 构造表
- 15.5.3 构造表有多快
- 15.5.4 访问表有多快
- 15.5.5 胜出的是…
- 15.6 DETS
- 15.7 我们没有提及的部分
- 15.1 表的基本操作
第十五章 ETS和DETS:大数据的存储机制
ETS和DETS都提供”键-值”搜索表, 只不过ETS驻留在内存而DETS驻留在磁盘, 因此ETS高效但数据存储是临时的, DETS数据存储是持久的且节省内存但比较低效。
15.1 表的基本操作
创建和打开表
ets:new或dets:open_file
插入表
insert(TableName, X)
查找元组
lookup(TableName, Key)
释放表
ets:delete(TableId)或dets:close(TableId)
15.2 表的类型
set表
每个元组的键值不能相同
ordered set表
排序的set表
bag表
多个元组可以有相同的键值, 但不能有两个完全相同的元组
duplicate bag表
多个元组可以有相同的键值, 且同一个元组可以在表中出现多次
代码示例
-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
15.3 ETS表的效率考虑
set表保证键值不相同, 因此相对耗费空间;ordered_set保证了排序, 因此相对耗费时间。
因为bag表插入数据时需要比较是否存在相同的键值, 因此如果大量元组存在相同键值, 使用bag表将会非常低效。
ETS表隶属于创建它的进程, 随进程消亡而消亡, 因此无需考虑垃圾回收。
尽可能的使用二进制数据。
15.4 创建ETS表
创建ETS表的函数原型
@spec ets:new(Name, [Opt]) -> TableId
其中[Opt]的取值:
# 表类型
set | ordered_set | bag | duplicate_bag
# 权限
private 只有所有者进程可以读写
public 所有可以获取TableId的进程都可以读写
protected 所有可以获取TableId的进程都可以读, 但只有所有者进程可以写
# 命名
named_table 是否可以使用Name来操作表
# 指定键的位置
{keypos, K} 通常是第一个位置, 当需要存储记录时, 第一个位置是记录的名字, 因此需要指定键的位置
# 默认选项为[set, protected, {keypos, 1}]
15.5 ETS程序示例
15.5.1 三字索引迭代器
%% 从压缩文件中读取英文单词, 每个单词都使用F函数处理
for_each_trigram_in_the_english_language(F, A0) ->
{ok, Bin0} = file:read_file("354984si.ngl.gz"),
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, []),
A1 = scan_trigrams([$\s|Word], F, A),
scan_word_list(L1, F, A1).
%% 单词匹配, 遇到换行符则添加空格
get_next_word([$\r, $\n|T], L) ->{reverse([$\s|L]), T};
get_next_word([H|T], L) ->get_next_word(T, [H, L]);
get_next_word([], L) ->{reverse([$\s|L]), []}.
%% 创建三字索引
scan_trigrams([X, Y, Z], F, A) ->F([X, Y, Z], A);
scan_trigrams([X, Y, Z|T], F, A) ->
A1 = F([X, Y, Z], A),
scan_trigrams([Y, Z|T], F, A1);
scan_trigrams(_, _, A) ->A.
15.5.2 构造表
%% 分别创建两者类型的ets表
make_ets_ordered_set() ->make_a_set(ordered_set, "trigramsOS.tab").
make_ets_set() ->make_a_set(set, "trigramsS.tab").
%% 根据指定类型创建ets表, 导入数据后转成文件保存
make_a_set(Type, FileName) ->
Tab = ets:new(table, [Type]),
%% 声明遍历英文单词时所使用的函数
%% 这里将每个单词插入到ets表
F = fun(Str, _) ->ets:insert(Tab, {list_to_binary(Str)}) end,
for_each_trigram_in_the_english_language(F, 0),
%% 转换为文件, 获取记录数后在内存中删除ets表
ets:tab2file(Tab, FileName),
Size = ets:info(Tab, size),
ets:delete(Tab),
Size.
make_mod_set() ->
%% 使用sets存储单词
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),
file:write_file("trigrams.set", [term_to_binary(D1)]).
15.5.3 构造表有多快
%% 统计有多少个单词
how_many_trigrams() ->
%% 遇到一个单词就将累加器增加1
F = fun(_, N) ->1 + N end,
for_each_trigram_in_the_english_language(F, 0).
make_tables() ->
%% 统计有多少个三字索引
{Micro1, N} = timer:tc(?MODULE, how_many_trigrams, []),
io:format("Counting - No of trigrams=~p time/trigram=~p~n", [N, Micro1/N]),
%% 统计排序的ets表平均占用存储和时间
{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]),
%% 统计普通ets表平均占用存储和时间
{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]),
%% 统计使用set方式平均占用存储和时间
{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]).
运行结果:
1> c(lib_trigrams).
{ok,lib_trigrams}
2> lib_trigrams:make_tables().
Counting - No of trigrams=3357707 time/trigram=0.1504470163715893
Ets ordered Set size=19.029156153630503 time/trigram=0.6226862558287546
Ets set size=19.028408559947668 time/trigram=0.40671625010758833
Module sets size=9.433978132884777 time/trigram=1.728039700903027
ok
共有3 357 707个三字索引, 处理每个三字索引平均时间为0.15微秒;
ordered_set类型的ETS表平均每个三字索引占用19字节耗费0.62微秒;
普通类型的ETS表平均每个三字索引占用19字节耗费0.41微秒;
而使用Erlang的集合模块平均存储占用9字节耗费1.73微秒
15.5.4 访问表有多快
lookup_all_ets(Tab, L) ->
lists:foreach(fun({K}) ->ets:lookup(Tab, K) end, L).
time_lookup_module_sets() ->
%% 读取文件转成二进制数据
{ok, Bin} = file:read_file("trigrams.set"),
%% 二进制数据转成列表
Set = binary_to_term(Bin),
Keys = sets:to_list(Set),
Size = length(Keys),
{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).
运行结果:
1> lib_trigrams:timer_tests().
Ets ordered Set lookup=0.45313522100738246 micro seconds
Ets set lookup=0.1906363891225119 micro seconds
Module set lookup=0.31632557704887393 micro seconds
ok
15.5.5 胜出的是…
%% 查询某个字符串是否为单词
%% 表中存储时已经添加了空格, 因此这里要补全
is_word(Tab, Str) ->is_word1(Tab, "\s" ++ Str ++ "\s").
%% 查询符合[A, B, C]格式的字符串是否为单词
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.
%% 查询ETS表中是否存在此索引
is_this_a_trigram(Tab, X) ->
case ets:lookup(Tab, list_to_binary(X)) of
[] ->false;
_ ->true
end.
%% 找到与源码文件同目录下的数据文件并转换成ETS表
open() ->
{ok, I} = ets:file2tab(filename:dirname(code:which(?MODULE)) ++ "/trigramsS.tab"),
I.
close(Tab) ->ets:delete(Tab).
运行结果
1> Tab = lib_trigrams:open().
16402
2> lib_trigrams:is_word(Tab, "example").
true
15.6 DETS
如果在打开DETS文件后没有关闭, 则Erlang将自动进行修复, 而修复可能会耗费大量的时间, 因此应在使用完后关闭DETS文件。
打开一个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宏获取文件名作为TableName
case dets:open_file(?MODULE, [{file, File}]) of
{ok, ?MODULE} ->
case Bool of
true ->void;
%% 插入键为free, 值为1的记录, 用于统计表中记录的总数
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).
%% 将二进制格式的文件名插入到dets表
filename2index(FileName) when is_binary(FileName) ->
%% 插入前先查询文件名是否已经存在
case dets:lookup(?MODULE, FileName) of
[] ->
%% 不存在则先查询最大索引, 然后将索引-文件名, 文件名-索引, free-最大索引插入到dets表
[{_, 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;
[{_, Bin}] ->Bin
end.
test() ->
%% 每次测试都重建dets表
file:delete("./filenames.dets"),
open("./filenames.dets"),
%% 使用正则查找当前目录下的所有erl文件添加到dets表中
F = lib_files_find:files(".", ".*[.](erl).*$", true),
lists:foreach(fun(I) ->filename2index(list_to_binary(I)) end, F).
运行结果:
1> c(lib_filenames_dets).
{ok,lib_filenames_dets}
2> lib_filenames_dets:test().
dets opened:"./filenames.dets"
ok
3> lib_filenames_dets:index2filename(1).
<<"./lib_trigrams.erl">>
4> lib_filenames_dets:index2filename(2).
<<"./lib_files_find.erl">>
5> lib_filenames_dets:index2filename(3).
<<"./lib_filenames_dets.erl">>
6> lib_filenames_dets:index2filename(4).
<<"./ets_test.erl">>
7> lib_filenames_dets:filename2index(list_to_binary("./ets_test.erl")).
4
15.7 我们没有提及的部分
ETS和DETS的在线手册:
http://www.erlang.org/doc/man/ets.html
http://www.erlang.org/doc/man/dets.html
