database - 什么 Erlang 数据结构用于有序集并可以进行查找？

Question

我正在解决一个问题，我需要记住我收到的事件的顺序，而且我还需要根据事件的 ID 查找事件。如果可能的话，如果没有第三方库，我如何在 Erlang 中有效地做到这一点？请注意，我有许多潜在的短暂 Actor ，每个 Actor 都有自己的事件(已经被认为是健忘症，但它需要表格的原子，如果我的 Actor 死了，表格会留下来)。

-record(event, {id, timestamp, type, data}).

Answer 1

根据对 Michael 的回答的评论中讨论的详细信息，非常简单可行的方法是在您的流程状态变量中创建一个元组，该元组将事件的顺序与事件的 K-V 存储。

考虑:

%%% Some type definitions so we know exactly what we're dealing with.
-type id()     :: term().
-type type()   :: atom().
-type data()   :: term().
-type ts()     :: calendar:datetime().
-type event()  :: {id(), ts(), type(), data()}.
-type events() :: dict:dict(id(), {type(), data(), ts()}).

% State record for the process.
% Should include whatever else the process deals with.
-record(s,
        {log    :: [id()],
         events :: event_store()}).

%%% Interface functions we will expose over this module.
-spec lookup(pid(), id()) -> {ok, event()} | error.
lookup(Pid, ID) ->
    gen_server:call(Pid, {lookup, ID}).

-spec latest(pid()) -> {ok, event()} | error.
latest(Pid) ->
    gen_server:call(Pid, get_latest).

-spec notify(pid(), event()) -> ok.
notify(Pid, Event) ->
    gen_server:cast(Pid, {new, Event}).

%%% gen_server handlers
handle_call({lookup, ID}, State#s{events = Events}) ->
    Result = find(ID, Events),
    {reply, Result, State};
handle_call(get_latest, State#s{log = [Last | _], events = Events}) ->
    Result = find(Last, Events),
    {reply, Result, State};
% ... and so on...

handle_cast({new, Event}, State) ->
    {ok, NewState} = catalog(Event, State),
    {noreply, NewState};
% ...

%%% Implementation functions
find(ID, Events) ->
    case dict:find(ID, Events) of
        {Type, Data, Timestamp} -> {ok, {ID, Timestamp, Type, Data}};
        Error                   -> Error
    end.

catalog({ID, Timestamp, Type, Data},
        State#s{log = Log, events = Events}) ->
    NewEvents = dict:store(ID, {Type, Data, Timestamp}, Events),
    NewLog = [ID | Log],
    {ok, State#s{log = NewLog, events = NewEvents}}.

这是一个完全直接的实现，隐藏了进程接口(interface)后面的数据结构细节。为什么我选择了一个字典？只是因为(很容易)。在不更好地了解您的要求的情况下，我真的没有理由在 gb_tree 等上选择字典而不是 map 。如果您的数据相对较小(要存储成百上千的东西)，这些结构之间的性能通常不会有明显差异。

重要的是你要清楚地识别这个过程应该响应什么消息，然后通过创建公开函数的接口(interface)强制自己在项目代码的其他地方坚持它em> 在这个模块上。在这之后，您可以将 dict 换成其他东西。如果您真的只需要最新的事件 ID 而永远不需要从序列日志中提取第 N 个事件，那么您可以放弃日志并只将最后一个事件的 ID 保留在记录中而不是列表中。

因此，首先让一些非常简单的东西像这样工作，然后确定它是否真的适合您的需要。如果没有，则对其进行调整。如果这暂时可行，就用它运行——不要过分关注性能或存储(直到你真的被迫这样做)。

如果您稍后发现您遇到了性能问题，请将 dict 和 list 换成其他东西——可能是 gb_tree 或 orddict 或 ETS 或其他。关键是让某些东西立即运行，以便您有一个基础来评估功能并在必要时运行基准测试。 (尽管如此，在绝大多数时间里，我发现无论我作为指定原型(prototype)开始做什么，结果都非常接近最终解决方案。 )