Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Implementing a Distributed Process Registry on ...

Implementing a Distributed Process Registry on Riak Core

NYC Erlang Factory Lite 2013

Christopher Meiklejohn

September 14, 2013
Tweet

More Decks by Christopher Meiklejohn

Other Decks in Programming

Transcript

  1. Eventual consistency is a consistency model used in distributed computing

    that informally guarantees that, if no new updates are made to a given data item, eventually all accesses to that item will return the last updated value. “Eventual Consistency”, Wikipedia Saturday, September 14, 13
  2. Our approaches tolerate partial failures by emphasizing simple composition mechanisms

    that promote fault containment, and by translating possible partial failure modes into engineering mechanisms that provide smoothly degrading functionality rather than lack of availability of the service as a whole. “Harvest, Yield, and Scalable Tolerant Systems”, Fox and Brewer Saturday, September 14, 13
  3. [ [{1, a}], [] ] [ [{1, a}, {2, b}],

    [] ] Saturday, September 14, 13
  4. [ [{1, a}], [] ] [ [{1, a}, {2, b}],

    [] ] [ [{1, a}, {2, b}], [{1, a}] ] Saturday, September 14, 13
  5. [ [{1, a}], [] ] [ [{1, a}, {2, b}],

    [] ] [ [{1, a}, {2, b}], [{1, a}] ] [ [{1, a}, {2, b}], [{1, a}] ] Saturday, September 14, 13
  6. [ [{1, a}], [] ] [ [{1, a}], [] ]

    Saturday, September 14, 13
  7. [ [{1, a}], [] ] [ [{1, a}], [] ]

    [ [{1, a}, {2, b}], [] ] Saturday, September 14, 13
  8. [ [{1, a}], [] ] [ [{1, a}], [] ]

    [ [{1, a}, {2, b}], [] ] [ [{1, a}], [{1, a}] ] Saturday, September 14, 13
  9. [ [{1, a}], [] ] [ [{1, a}], [] ]

    [ [{1, a}, {2, b}], [] ] [ [{1, a}], [{1, a}] ] [ [{1, a}, {2, b}], [{1, a}] ] Saturday, September 14, 13
  10. [ [{1, a}], [] ] [ [{1, a}], [] ]

    Saturday, September 14, 13
  11. [ [{1, a}], [] ] [ [{1, a}], [] ]

    [ [{1, a}], [{1, a}] ] [ [{1, a}], [{1, a}] ] Saturday, September 14, 13
  12. [ [{1, a}], [] ] [ [{1, a}], [] ]

    [ [{1, a}], [{1, a}] ] [ [{1, a}], [{1, a}] ] [ [{1, a}, {2, a}], [{1, a}] ] Saturday, September 14, 13
  13. [ [{1, a}], [] ] [ [{1, a}], [] ]

    [ [{1, a}], [{1, a}] ] [ [{1, a}], [{1, a}] ] [ [{1, a}, {2, a}], [{1, a}] ] [ [{1, a}, {2, a}], [{1, a}] ] Saturday, September 14, 13
  14. %% @doc Respond to a join request. handle_command({join, {ReqId, _},

    Group, Pid}, _Sender, #state{groups=Groups0, partition=Partition}=State) -> %% Find existing list of Pids, and add object to it. Pids0 = pids(Groups0, Group, riak_dt_vvorset:new()), Pids = riak_dt_vvorset:update({add, Pid}, Partition, Pids0), %% Store back into the dict. Groups = dict:store(Group, Pids, Groups0), %% Return updated groups. {reply, {ok, ReqId}, State#state{groups=Groups}}; %% @doc Return pids from the dict. -spec pids(dict(), atom(), term()) -> term(). pids(Groups, Group, Default) -> case dict:find(Group, Groups) of {ok, Object} -> Object; _ -> Default end. riak_pg/src/riak_pg_memberships_vnode.erl Saturday, September 14, 13
  15. %% @doc Respond to a leave request. handle_command({leave, {ReqId, _},

    Group, Pid}, _Sender, #state{groups=Groups0, partition=Partition}=State) -> %% Find existing list of Pids, and remove object from it. Pids0 = pids(Groups0, Group, riak_dt_vvorset:new()), Pids = riak_dt_vvorset:update({remove, Pid}, Partition, Pids0), %% Store back into the dict. Groups = dict:store(Group, Pids, Groups0), %% Return updated groups. {reply, {ok, ReqId}, State#state{groups=Groups}}; %% @doc Return pids from the dict. -spec pids(dict(), atom(), term()) -> term(). pids(Groups, Group, Default) -> case dict:find(Group, Groups) of {ok, Object} -> Object; _ -> Default end. riak_pg/src/riak_pg_memberships_vnode.erl Saturday, September 14, 13
  16. %% @doc Execute the request. execute(timeout, #state{preflist=Preflist, req_id=ReqId, coordinator=Coordinator, group=Group,

    pid=Pid}=State) -> riak_pg_memberships_vnode:join(Preflist, {ReqId, Coordinator}, Group, Pid), {next_state, waiting, State}. %% @doc Attempt to write to every single node responsible for this %% group. waiting({ok, ReqId}, #state{responses=Responses0, from=From}=State0) -> Responses = Responses0 + 1, State = State0#state{responses=Responses}, case Responses =:= ?W of true -> From ! {ReqId, ok}, {stop, normal, State}; false -> {next_state, waiting, State} end. riak_pg/src/riak_pg_memberships_vnode.erl Saturday, September 14, 13
  17. %% @doc Pull a unique list of memberships from replicas,

    and %% relay the message to it. waiting({ok, _ReqId, IndexNode, Reply}, #state{from=From, req_id=ReqId, num_responses=NumResponses0, replies=Replies0}=State0) -> NumResponses = NumResponses0 + 1, Replies = [{IndexNode, Reply}|Replies0], State = State0#state{num_responses=NumResponses, replies=Replies}, case NumResponses =:= ?R of true -> Pids = riak_dt_vvorset:value(merge(Replies)), From ! {ReqId, ok, Pids}, case NumResponses =:= ?N of true -> {next_state, finalize, State, 0}; false -> {next_state, waiting_n, State} end; false -> {next_state, waiting, State} end. riak_pg/src/riak_pg_members_fsm.erl Saturday, September 14, 13
  18. %% @doc Perform merge of replicas. merge(Replies) -> lists:foldl(fun({_, Pids},

    Acc) -> riak_dt_vvorset:merge(Pids, Acc) end, riak_dt_vvorset:new(), Replies). riak_pg/src/riak_pg_members_fsm.erl Saturday, September 14, 13
  19. %% @doc Wait for the remainder of responses from replicas.

    waiting_n({ok, _ReqId, IndexNode, Reply}, #state{num_responses=NumResponses0, replies=Replies0}=State0) -> NumResponses = NumResponses0 + 1, Replies = [{IndexNode, Reply}|Replies0], State = State0#state{num_responses=NumResponses, replies=Replies}, case NumResponses =:= ?N of true -> {next_state, finalize, State, 0}; false -> {next_state, waiting_n, State} end. riak_pg/src/riak_pg_members_fsm.erl Saturday, September 14, 13
  20. %% @doc Perform read repair. finalize(timeout, #state{replies=Replies}=State) -> Merged =

    merge(Replies), Pruned = prune(Merged), ok = repair(Replies, State#state{pids=Pruned}), {stop, normal, State}. %% @doc If the node is connected, and the process is not alive, prune %% it. prune_pid(Pid) when is_pid(Pid) -> lists:member(node(Pid), nodes()) andalso (is_process_alive(Pid) =:= false). %% @doc Based on connected nodes, prune out processes that no longer %% exist. prune(Set) -> Pids0 = riak_dt_vvorset:value(Set), lists:foldl(fun(Pid, Pids) -> case prune_pid(Pid) of true -> riak_dt_vvorset:update({remove, Pid}, none, Pids); false -> Pids end end, Set, Pids0). riak_pg/src/riak_pg_members_fsm.erl Saturday, September 14, 13