Distributed Membership Protocol : HyParView 프로토콜

Distributed System
2025. 2. 15.

들어가기 전

이 글은 다음 포스팅을 참고하여 공부하며 작성한 글입니다. erlang으로 구현된 학습용 코드는 이곳에서 확인할 수 있습니다.

1. 시작

이전 게시글에서 간단하고 직관적인 멤버쉽 프로토콜인 SWIM을 공부했다. 그러나 초기 SWIM 프로토콜은 Full Membership을 유지하기 때문에 규모가 큰 클러스터로의 확장은 상대적으로 제한된다. 이번 글에서는 HyParView(Hybrid Partial View) 프로토콜을 다룬다. HyParView 프로토콜은 규모가 큰 클러스터에서도 경량화 된 방식으로 잘 동작하는 멤버쉽 프로토콜이다.

2. 직관적으로 바라보기

HyParView에 대한 직관을 가질 수 있도록 일상 생활을 예로 들어보자. 우리는 노드를 사람, 클러스터를 사람의 무리라고 치환할 수 있다. 그렇다면 아래 설명이 가능하다.

클러스터는 사람들이 모이는 모임이다.
소수의 동료로만 구성된 그룹이 있다면, 그룹 내에서 누구나 쉽게 대화에 참여할 수 있고, 대화를 이해할 수 있다.
다수의 동료로 구성된 그룹이 있다면, 모든 참가자가 같은 내용을 이해하는데 많은 시간이 필요하다. 또한, 거리가 멀어질수록 대화하기 어려워진다.

이 비유를 통해 HyPerView 알고리즘을 두 개의 원으로 이루어진 관계로 치환할 수 있다.

Active view (Inner Circle)
- 비유 : 실제로 활발하게 대화를 나누는 그룹임.
- 알고리즘 관계 : 각 노드는 서로에 대한 연결을 유지한다.
- HyParView에서 Active View에 있는 활성 노드들을 Neighbors라고 한다.
Passive View (Outer Circle)
- 비유 : 전화번호부에 저장된 사람들이지만, 지금은 연락을 하지 않는 사람들.
- 알고리즘 관계 : Passive View에 있는 노드는 이후에 Active View로 이동 가능한 노드임.

Active View가 있는데 왜 Passive View는 유지해야하는 것일까? Passive View는 일반적으로 보충 풀의 역할을 한다. 그렇다면 Active View에 보충이 필요한 시나리오는 어떤 것이 있을까? 아래를 참고하자.

활성 피어가 shut down 되어서 나의 Active View에서 제거된다. 그러면 Active View에 한 자리가 남을 것인데, Passive View의 피어를 Active View로 Promote 할 수 있다.
활성 피어가 '우선순위가 높은 Join' 요청을 수용하기 위해 자신의 Active View에 여분의 자리가 필요한 경우. 이 때, 상대방은 나에게 Disconnect 요청을 보낼 것이다. 이 때 나의 Active View에서 상대방을 제거하고, 다시 Passive View에 넣을 수 있다.

이런 개념을 가지고 HyParView의 Active View, Passive View의 요구 사항을 간략히 정리해보자.

한 노드는 다른 노드의 Active View, Passive View 둘 중에 하나에만 존재할 수 있다. (구현의 단순화를 위해서. 실제로는 둘다 존재해도 됨.)
어떤 노드의 Active View + Passive View를 해도, 그것은 클러스터의 일부를 가리킨다.
Active View / Passive View는 각각의 상한값을 가진다.
- Active View : log(N) + 1 (여기서 N은 클러스터 전체 노드 개수)
- Passive View : Active View * 6
Active View / Passive View는 제한된 사이즈 크기를 가지기 때문에 새로운 노드가 View에 들어오려고 하는 경우, 해당 View에서 기존 Peer를 제거해야한다.
Active View 밖의 멤버와 메세지를 주고 받기 위해서는 활성 연결된 Peer들이 체이닝 방식으로 메세지를 전파해서 소통한다. (이것은 클러스터 멤버십의 역할이 아님, 가십 프로토콜등을 이용)

Active View 사이즈가 log(N)으로 설정된 것은 클러스터의 확장을 위해서다. log(N)인 경우, 클러스터 사이즈가 급격히 커지더라도 Active View 사이즈는 급격히 증가하지 않는다. 그러면 내가 통신하고 있는 멤버 수가 적은 상태로 유지되기 때문에 네트워크가 커져도 관리 오버헤드가 급격히 증가하지 않는다.

동작하는 방법에 대한 그림 설명

1. 새로운 멤버가 Active에 Join하는 경우

노드가 Join하려고 할 때, Join 요청을 보낸다.
Join 요청을 받은 노드는 Forward Join 메세지를 TTL과 함께 자신이 알고 있는 Active View 노드에 전송한다.
TTL이 0이 되는 시점에 메세지를 받은 노드는 전달받은 노드를 자신의 Active View에 추가한다.

이 때, TTL이 클수록 Join 요청을 받은 노드에 멀리 떨어진 노드가 메세지를 수신하고, Active View에 추가할 가능성이 높아진다.

위 이미지는 연속적으로 동작하는 모습을 보여준다.

2. 새로운 멤버가 Join하면서, Active View Limit을 초과한 경우.

노드 D는 Join 요청을 받는다. 그러나 현재 노드 D의 Active View는 2개이고, 새로운 노드 C를 추가하기 위해서 자신의 Active View에서 임의의 노드를 하나 제거해야한다.
이 때 노드 D는 랜덤으로 노드 A를 선택해서 Disconnect 메세지를 보낸 후 TCP 연결을 끊는다. 그리고 노드 A를 Passive View에 넣는다. 한편 노드 C에게 Neighbor 메세지를 전송하고, 노드 B에는 Forward Join 메세지를 전송한다.
A는 Disconnect 메세지를 수신한 후, 노드 D를 자신의 Active View에서 제거한다. 그러나 노드 D가 죽은 것은 아니기 때문에 노드 A-D는 서로를 Passive View에 추가한다.
한편 Forward 메세지를 받은 노드 B는 노드 C를 자신의 Active View에 추가하려한다. 그러나 B의 Active View의 용량이 가득 찼기 때문에 임의로 선택된 노드 D를 자신의 Active View에서 제거한다. 이를 위해 노드 B -> 노드 D로 Disconnect 메세지를 날린 후 TCP 연결을 끊는다. 그리고 노드 B는 노드 C에게 Neighbor 메세지를 전송한다.

새로운 노드가 추가되었다는 메세지를 받았을 때, 자신의 Active View가 Full인 상태라면 Active View에서 임의의 노드를 선택해서 Active View에서 제거, Passive View에 추가하고 상대방에게 Disconnect 메세지를 보내는 형태로 동작한다.

연속된 동작은 위와 같다.

3. 한 노드가 Shuffle 할 때.

노드 A는 Active View와 Passive View에서 각각 몇 개의 노드를 뽑아서, 그 노드 정보를 담은 셔플 메세지를 생성한다.
노드 A는 Active View 중 1개를 무작위로 뽑아서 TTL과 함께 셔플 메세지를 전송한다.
셔플 메세지의 TTL이 0이 되는 시점에 셔플 메세지를 받은 노드는 셔플 메세지에 포함된 노드 정보를 자신의 Passive View에 추가한다. 그리고 자신의 Passive View에서 몇몇 노드를 랜덤으로 뽑아서 Shuffle Reply 메세지를 만들고, 최초로 셔플 메세지를 발송한 노드에게 직접 응답한다.
Shuffle Reply 메세지를 받은 노드는 메세지의 담긴 노드들 정보를 확인하고, 자신의 Passive View에 추가한다. (이때, View 용량이 가득찼다면 제거 후 넣는다)

이렇게 Shuffle - Shuffle Reply 메세지의 전송을 통해서 자신과 직접적으로 연결되지 않은 노드들에게도 내가 알고 있는 Passive View 정보를 전송할 수 있게 된다. Shuffle / Shuffle Reply 메세지는 그 메세지를 생성하는 노드가 알고 있는 Active View + Passive View의 정보가 일부 담기게 되고, 그 메세지를 받은 노드들은 Shuffle / Shuffle Reply 메세지에 담긴 노드들의 정보를 자신의 Passive View에 업데이트한다.

물론 Shuffle / Shuffle Reply로 전달된 노드 정보가 항상 최신화 된 정보라는 보장은 없다. 그러나 아래 경우를 가정해보면, 확률적으로는 이 과정을 통해 최신화 된 정보로 수렴할 것이라는 것을 알 수 있다. 예를 들어 아래 경우를 고려해보자.

HyParView 클러스터에서 어떤 노드 A가 죽었다. 이 노드가 죽으면, TCP Connection이 끊어진다. TCP Connection이 끊어지면 즉시 다른 노드들의 Active View에서 제거될 것이다. 그러나 Passive View에서는 여전히 제거되지 않을 것이다. 그러나 기존의 Active View가 Passive View로 내려가는 과정에서 A는 점차 모든 노드들의 Passive View에서 없어질 것이다.

또한 각 노드는 자신의 Active View에서 죽은 노드를 제거하면서 Active View에 한 자리가 남게된다. 이때, 각 노드의 Passive View에서 Active View로 Promote 되는 노드도 생기게 된다.

위와 같은 경우를 고려해보면, 어떤 이유로든 제거된 노드는 각 노드의 Active View, Passive View에서 발견되기 어려워진다. 그렇다면 Shuffle에서 메세지가 언급되는 비중이 점차 줄어들 것이다. 궁극적으로는 Shuffle / Shuffle Reply 메세지를 통해서 전달되는 메세지들은 '최신화'된 메세지가 될 것이다.

연속된 동작으로 살펴보면 위와 같다.

4. 구현 전 메세지 정리

클러스터 내에서는 노드끼리 다음 메세지를 주고 받으면서 클러스터 내에서 멤버를 계속 유지한다.

Join - Neighbor (새롭게 클러스터에 조인)
- Join : 클러스터에 가입하고 싶은 노드가 '나를 당신의 Active View에 넣어주세요.'라는 의미.
- Neighbor : Join 메세지를 받은 노드는 메세지를 보낸 노드를 Active View에 추가하고, 메세지를 보낸 노드에게 응답하는 메세지. '당신은 내 Active View에 들어왔습니다. 당신도 나를 Active View에 넣어주세요' 라는 의미다.
Join - Forward - Disconnect (새롭게 클러스터에 조인한 노드를 전파하기 위한 것)
- Forward
  - Join 메세지를 받은 노드는 해당 노드가 새롭게 클러스터에 들어온 것을 알리기 위해 Forward 메세지를 만든다.
  - Forward 메세지는 Active View를 따라 전파된다.
  - Forward 메세지를 받은 노드들은 새롭게 클러스터에 합류한 노드를 자신의 Passive View에 넣을 수 있다. (이후, 필요하다면 Active View로 승격시킬 수 있다)
  - TTL이 0이 된 Forward 메세지를 받은 노드는 새롭게 클러스터에 합류한 노드를 자신의 Active View에 넣어야 한다.
- Disconnect
  - Join / Forward 메세지를 받고 자신의 Active View가 Full인 상태에서 새로운 노드를 추가해야할 때, Active View에서 임의의 노드를 하나 선택해 Active View에서 제거, Passive View에 추가한다. 이때, 상대방에게 Disconnect 메세지를 보내서 상대방도 Active View에서 제거하도록 요청한다.
Shuffle / Shuffle Reply (클러스터 정보의 최신화를 위한 메세지 교환)
- Shuffle
  - 내가 알고 있는 Active View / Passive View에서 노드 몇개를 뽑아서 Shuffle 메세지를 만들어서 TTL과 함께 Active Peer 1명에게 전송한다.
  - TTL이 0이 아닌 시점에 Shuffle 메세지를 받은 노드는 메세지를 자신의 Active View 중 1명에게만 포워딩한다.
  - TTL이 0인 시점에 Shuffle 메세지를 받은 노드는 메세지에 포함된 노드를 자신의 Passive View에 추가한다.
- Shuffle Reply
  - TTL이 0인 Shuffle 메세지를 받은 노드는 자신의 Passive View에서 노드 몇 개를 뽑아서 Shuffle Reply 메세지를 만들어 최초로 Shuffle 메세지를 발송한 노드에게 응답한다. (이것은 Shuffle - Shuffle Reply 메세지를 직접 주고 받았을 때, 서로가 Active View가 된다는 것을 의미하지는 않음)
  - Shuffle Reply 메세지를 받은 노드는 메세지에 포함된 노드 정보를 자신의 Passive View에 추가한다.

5. Join 구현

handle_cast({join, NewlyAddedPeerName}, State0) ->
  io:format("[~p] node ~p received join message. Newly Added PeerName ~p.~n", [self(), self(), NewlyAddedPeerName]),
  #?MODULE{config=Config, active_view=ActiveView0, reactor=Reactor} = State0,

  ActiveTTL = get_ttl(active_view, Config),
  ForwardMsg = forward_join_message(NewlyAddedPeerName, ActiveTTL),
  ActiveViewWithoutNewPeerList = get_node_pids(active_view, ActiveView0),
  send_messages_via_reactor(ActiveViewWithoutNewPeerList, ForwardMsg, Reactor),

  HighPriority = true,
  State1 = add_active(NewlyAddedPeerName, HighPriority, State0),

  {noreply, State1};

클러스터에 Join을 원하는 노드는 'Join' 메세지를 발송해야한다. 노드가 'Join' 메세지를 받으면 위 함수가 호출된다.

Active View TTL, 새로 추가된 노드 정보를 포함해 Forward 메세지를 생성한다.
자신의 Active View의 모든 노드에게 send_messages_via_reactor(...)를 통해서 Forward Message를 모두 전송한다.
자신의 Active View에 새로운 노드를 추가한다. 이때, High Priority를 인자로 전달한다. 이것은 Active View가 Full인 경우, 노드를임의로 제거하고 추가하라는 의미다.

일반적으로 모든 Active View에게 Forward Join 메세지를 전송하지는 않는다. 모든 Active View에 Forward Join을 하게 되면, 클러스터 내의 메세지 트래픽이 많이 발생할 수도 있기 때문이다.

add_active(PeerName, HighPriority, State0) ->
  #?MODULE{active_view=ActiveView0} = State0,

  IsThisMe = is_this_me(PeerName),
  DoesActiveViewAlreadyHas = maps:is_key(PeerName, ActiveView0),

  case IsThisMe orelse DoesActiveViewAlreadyHas of
    true  ->
      State0;
    false ->
      State1 = remove_active_if_full(State0),

      #?MODULE{active_view=ActiveView1, passive_view=PassiveView0, reactor=Reactor} = State1,
      ActiveView2 = maps:put(PeerName, get_node_pid(PeerName), ActiveView1),
      PassiveView1 = remove_passive(PeerName, PassiveView0),

      NeighborMsg = neighbor_message(HighPriority),

      ToPid = get_node_pid(PeerName),
      send_message_via_reactor(ToPid, NeighborMsg, Reactor),

      NeighborEvent = neighbor_event(up, PeerName),
      Reactor:notify(NeighborEvent),

      State1#?MODULE{active_view=ActiveView2, passive_view=PassiveView1}
  end.

이때 호출된 add_active(...) 함수의 구현은 다음과 같다.

만약 ActiveView가 Full이라면, remove_active_if_full(...)을 호출해서 Active View에서 Peer를 1명 제거한다. 이때, 제거된 Peer에게는 Disconnect 메세지가 전송된다.
새로 추가된 노드를 Active View에 추가하고, 새로 추가된 노드에게 Neighbor 메세지를 생성해서 전송한다.
이때, '새로 추가된 노드가 있다'는 이벤트를 알려주기 위해 NeighborEvent를 만들어서 notify(...) 한다. 이것은 주로 Gossip 프로토콜의 확장에 사용된다.

remove_active_if_full(State0) ->
  #?MODULE{active_view=ActiveView0} = State0,
  case is_active_view_full(State0) of
    false -> State0;
    true ->
      case pick_one_randomly(ActiveView0) of
        undefined -> State0;
        PickedPeerName -> remove_active(PickedPeerName, State0, true)
      end
  end.

remove_active(PeerName, State0, Respond) ->
  #?MODULE{active_view=ActiveView0, reactor=Reactor} = State0,

  DoesContainPeerInActive = maps:is_key(PeerName, ActiveView0),
  case DoesContainPeerInActive of
    false -> State0;
    true ->
      ActiveView1 = maps:remove(PeerName, ActiveView0),

      case Respond of
        true ->
          DisconnectMsg = disconnect_message(true, false),
          ToPid = get_node_pid(PeerName),
          send_message_via_reactor(ToPid, DisconnectMsg, Reactor);
        false ->
          ok
      end,
      % Disconnect TCP Socket.
      Reactor:disconnect(PeerName),

      NeighborEvent = neighbor_event(down, PeerName),
      Reactor:notify(NeighborEvent),

      State1 = add_passive(PeerName, State0),
      State1#?MODULE{active_view=ActiveView1}
  end.

위는 remove_active_if_full(...) 메서드의 세부 구현을 나타낸다. 하는 일을 정리하면 다음과 같다.

Active View가 Full인 경우, Active View에서 제거할 노드를 하나 선택한 다음에 그 정보를 파라메터로 넘기면서 remove_active(...)를 호출한다.
ActiveView에서 선택된 노드를 제거하고, Disconnect 메세지를 하나 만든다. 그리고 제거된 노드에게 DisConnect 메세지를 전송한다.
한 노드가 Active View에서 없어졌기 때문에 NeighborDown 이벤트를 만들어 notify(...)한다. 이것은 이후 Gossip 프로토콜과 연결되는 지점이 된다.
그리고 add_passive(...)를 호출해 Active View에서 제거된 노드를 Passive View에 추가해둔다.

Active View에서 제거된 노드를 Passive View에 추가하는 이유는 그 노드가 'ShutDown에 의해서' Active View에서 제거된 것이 아니기 때문이다. 아직까지 살아있는 노드이기 때문에 Active View에 자리가 생긴다면, Passive View에서 Promote해서 다시 Active View로 만들 수도 있음을 알려준다.

6. Neighbor 구현

handle_cast({{neighbor, HighPriority}, FromPid}, State0) ->
  io:format("[~p] node ~p received neighbor message. FromPid ~p and HighPriority ~p.~n", [self(), self(), FromPid, HighPriority]),
  State =
    case (HighPriority orelse is_active_view_full(State0)) of
      false -> State0;
      true ->
        FromNodeName = get_node_name_by_pid(FromPid),
        add_active(FromNodeName, HighPriority, State0)
    end,
  {noreply, State};

클러스터에 정상적으로 합류했다면, Join 요청의 결과로 'neighbor' 메세지를 받게 된다. 'neighbor' 메세지를 받았을 때 위 함수가 호출된다.

특정 노드로부터 HighPriority인 neighbor 요청을 받았다면, 자신의 Active View가 Full이라도 한 노드를 제거한 다음에 그 노드를 추가한다.

즉, 서로를 Active View에 등록해서 Connection을 맺어두겠다는 의미를 가진다.

7. Forward Join 구현

Join 메세지를 받은 노드는 자신의 Active View Peer들에게 Forward Join 메세지를 발송한다고 했다. 이번에는 Forward Join 메세지를 다루는 함수를 구현해야한다.

handle_cast({{forward_join, NewlyAddedPeerName, TTL}, FromPid}, State0) ->
  io:format("[~p] node ~p received forward_join message. Newly Added PeerName ~p and TTL ~p.~n", [self(), self(), NewlyAddedPeerName, TTL]),
  #?MODULE{active_view=ActiveView0, reactor=Reactor, config=Config} = State0,

  ShouldAddItToActiveRightNow = TTL =:= 0 orelse maps:size(ActiveView0) =:= 0,
  State =
    case ShouldAddItToActiveRightNow of
      true ->
        add_active(NewlyAddedPeerName, true, State0);

      false -> ...
    end,
  {noreply, State};

먼저 위 코드는 Forward Join 메세지를 받은 노드가 바로 자신의 Active View에 NewlyAddedPeer를 추가하는 경우를 다룬다.

Forward Join의 TTL이 0인 경우이거나, 현재 자신의 Active View에 아무도 없는 경우 새로 추가된 노드를 자신의 Active View에 바로 추가하도록 한다.

handle_cast({{forward_join, NewlyAddedPeerName, TTL}, FromPid}, State0) ->
  ...
  State =
    case ShouldAddItToActiveRightNow of
      true ->
         ...

      false ->
        PassiveViewTTL = get_ttl(passive_view, Config),
        StateWithNewlyAddedPassivePeer =
          case TTL =:= PassiveViewTTL of
            true ->
              add_passive(NewlyAddedPeerName, State0);
            false ->
              State0
          end,

        FromName = get_node_name_by_pid(FromPid),
        ActiveViewExceptFromNode =  maps:remove(FromName, ActiveView0),
        case pick_one_randomly(ActiveViewExceptFromNode) of
          % No node existed.
          undefined ->
            add_active(NewlyAddedPeerName, true, StateWithNewlyAddedPassivePeer);
          PickedNodeName ->
            NodePid = get_node_pid(PickedNodeName),
            ForwardJoinMsg = forward_join_message(NewlyAddedPeerName, TTL - 1),
            Reactor:send(NodePid, ForwardJoinMsg),
            StateWithNewlyAddedPassivePeer
        end
    end,
  {noreply, State};

위 코드는 새로 추가된 노드를 자신의 Active View에 바로 추가하지 않는 경우를 다룬다.

먼저 새로 추가된 노드를 자신의 Passive View에 추가한다. (필요한 경우 Active View로 승급할 수 있도록)
자신의 Active View 중에서 노드를 하나 뽑은 다음에 Forward Join 메세지를 하나 만들어서 전송한다. 이때, TTL을 1칸 줄인다.
- 여기서 방어 코드로 Active View에서 자기 자신을 제외했을 때 아무도 없는 경우를 고려하도록 했다.

요약해보면 Forward Join에서는 TTL이 0이거나 Active View가 없는 경우 바로 새로 추가된 노드를 자신의 Active View에 추가했다. 그렇지 않은 경우에는 Passive View에 해당 노드를 추가하고, 자신의 Active View 중 하나를 랜덤으로 뽑아 Forward Join 메세지를 전송했다.

8. Disconnect 구현

앞서서 자신의 Active Peer와 Active View 관계로 있고 싶지 않을 때 싶을 때, Disconnect 메세지를 보낸다고 했다. 아래 함수는 Disconnect 메세지를 Actor가 받았을 때, 실행되는 함수다.

handle_cast({{disconnect, PeerName, Alive, Response}, FromPid}, State0) ->
  io:format("[~p] node ~p received disconnect message. Disconnect PeerName ~p, Alive ~p, Response ~p FromPid ~p.~n",
    [self(), self(), PeerName, Alive, Response, FromPid]),

  #?MODULE{active_view=ActiveView0} = State0,
  HasActiveViewPeerInList = maps:is_key(PeerName, ActiveView0),

  State =
    case HasActiveViewPeerInList of
      false -> State0;
      true ->
        State1 = remove_active(PeerName, State0, Response),
        State2 = remove_passive_with_state(PeerName, State1),
        State3 = promote_to_active_if_can(State2),
        case Alive of
          false -> State3;
          true ->
            #?MODULE{passive_view=PassiveView0} = State3,
            PassiveView1 = maps:put(PeerName, get_node_pid(PeerName), PassiveView0),
            State3#?MODULE{passive_view=PassiveView1}
        end
    end,
  {noreply, State};

메세지를 받은 노드의 Active View에서 Sender(Disconnect 메세지를 보낸) 노드를 제거한다.
만약 Disconnect 메세지에 Alive가 True로 왔다면, 상대방 노드가 계속 살아있는 상태이므로 추후에 여유가 생겼을 때 Active View로 Promote 할 수 있도록 Passive View에 넣어둔다.

위 메세지까지 처리하는 함수를 구현했다면, 이제 Join을 해서 새로운 멤버를 클러스터로 넣고 그 사실을 전파하는 일련의 프로토콜을 구현한 셈이다. 이후는 resilience한 클러스터가 될 수 있도록 하는 Shuffle - Shuffle Reply 프로토콜도 구현해야한다.

9. Shuffle 메세지 구현

Shuffle 메세지를 주고 받는 과정에서 클러스터의 각 멤버가 가지고 있는 Passive View가 최신화 될 확률이 높아진다. Shutdown 된 노드라면 서서히 Passive View에서 언급되지 않을 것이기 때문에, 각 노드가 가진 Passive View는 유효한 노드들만으로 최신화 될 가능성이 높아진다. 이를 위해서 Shuffle 메세지를 구현해야한다.

handle_cast({do_shuffle}, State) ->
  io:format("[~p] node ~p received do_shuffle message. ~p try to shuffle and send shuffle message to other active.~n", [self(), self(), self()]),
  #?MODULE{config=Config} = State,
  #config{shuffle_interval=ShuffleInterval} = Config,
  schedule_shuffle(ShuffleInterval),

  shuffle(State),
  {noreply, State};

위 함수는 각 Actor에게 셔플 메세지를 만들고 전송하도록 하는 함수다. do_shuffle이라는 메세지를 만들고 schedule_shuffle(...) 함수에서 얼마 정도 기다린 후에 자기 자신에게 전송하도록 한다. 얼마 후에 Actor는 do_shuffle 메세지를 받게 되고, shuffle(...) 함수를 호출해서 다른 Active View에게 Shuffle 메세지를 보내도록 동작한다.

shuffle(State) ->
  #?MODULE{active_view=ActiveView0} = State,

  case pick_one_randomly(ActiveView0) of
    undefined -> ok;
    PickedNodeName ->
      #?MODULE{passive_view=PassiveView0, reactor=Reactor, config=Config} = State,

      ActiveView1 = maps:remove(PickedNodeName, ActiveView0),
      #config{shuffle_active_view_count=ActiveShuffleCount,
              shuffle_passive_view_count=PassiveShuffleCount,
              shuffle_ttl=ShuffleTTL} = Config,

      TakenActiveForShuffle = take_max_n(ActiveView1, ActiveShuffleCount),
      TakenPassiveForShuffle = take_max_n(PassiveView0, PassiveShuffleCount),

      ShuffleNode = TakenActiveForShuffle ++ TakenPassiveForShuffle,

      Me = get_node_name_by_pid(self()),
      ToPid = get_node_pid(PickedNodeName),
      ShuffleMsg = shuffle_message(Me, ShuffleNode, ShuffleTTL),
      send_message_via_reactor(ToPid, ShuffleMsg, Reactor),
      ok
  end.

위 shuffle(...) 함수에서는 자신이 알고 있는 노드들 중 몇 개의 노드를 뽑아서 Shuffle 메세지에 담고, 그 메세지를 다른 노드에게 발송하는 일을 한다. 여기서 이루어지는 작업을 순서대로 표현하면 다음과 같다.

먼저 자신의 Active View에서 Shuffle 메세지를 받을 노드 하나를 선택한다.
Active View, Passive View에서 최대 shuffle_xxx_view_count만큼의 노드를 선택해서 ShuffleNode 리스트를 만든다.
ShuffleNode 리스트를 포함한 Shuffle 메세지를 만들어서 다른 노드들에게 전송한다.

위 일련의 과정을 요약하면 do_shuffle 메세지를 받았을 때, 다음 do_shuffle을 예약함과 동시에 Shuffle 메세지를 만들어서 다른 노드에게 전송하는 것이다.

handle_cast({{shuffle, OriginNodeName, ReceivedShuffledNodes, TTL}, FromPid}, State0) ->
  io:format("[~p] node ~p received shuffle message. ~p try to update its passive view or send it to other active node.
  OriginNodeName ~p, TTL ~p~n", [self(), self(), self(), OriginNodeName, TTL]),
  State =
    case TTL =:= 0 of
      true ->
         ... % 아래에서 구현됨. 
      false ->
        #?MODULE{active_view=ActiveView0, reactor=Reactor} = State0,

        Me = get_node_name_by_pid(self()),
        ActiveView1 = maps:remove(OriginNodeName, ActiveView0),
        ActiveView2 = maps:remove(Me, ActiveView1),

        case pick_one_randomly(ActiveView2) of
          undefined ->
            State0;
          PickedNodeName ->
            ShuffleMsg = shuffle_message(OriginNodeName, ReceivedShuffledNodes, TTL - 1),
            ToPid = get_node_pid(PickedNodeName),

            send_message_via_reactor(ToPid, ShuffleMsg, Reactor),
            State0
        end
    end,
  {noreply, State};

노드가 Shuffle 메세지를 받으면, Shuffle 메세지를 처리하기 위해 위 함수가 실행된다. Shuffle 메세지의 TTL이 0인지 아닌지에 따라 실행해야 할 코드가 달라진다. 먼저 TTL이 0이 아닌 시점의 코드를 살펴보자.

자신의 Active View에서 Shuffle 메세지를 전달받을 노드를 하나 선택한다.
받은 Shuffle 메세지에서 TTL을 하나 감소시키고, 그 메세지를 위에서 선택된 노드에게 전송한다.

handle_cast({{shuffle, OriginNodeName, ReceivedShuffledNodes, TTL}, FromPid}, State0) ->
  io:format("[~p] node ~p received shuffle message. ~p try to update its passive view or send it to other active node.
  OriginNodeName ~p, TTL ~p~n", [self(), self(), self(), OriginNodeName, TTL]),
  State =
    case TTL =:= 0 of
      true ->
        #?MODULE{passive_view=PassiveView0, reactor=Reactor} = State0,
        PassiveView1 = maps:remove(OriginNodeName, PassiveView0),

        ShuffleNodeCount = length(ReceivedShuffledNodes),
        TakenShuffledNodeNameList = take_max_n(PassiveView1, ShuffleNodeCount),
        ShuffleReplyMsg = shuffle_reply_message(TakenShuffledNodeNameList),

        ToPid = get_node_pid(OriginNodeName),
        send_message_via_reactor(ToPid, ShuffleReplyMsg, Reactor),

        add_all_passive(State0, ReceivedShuffledNodes);
      false ->
        ... % 위에서 구현됨. 
        end
    end,
  {noreply, State};

이번에는 받은 Shuffle 메세지의 TTL이 0인 경우에 해야할 일을 살펴본다.

현재 자신의 Passive View에서 Shuffle 메세지에 포함된 Node 개수만큼 노드를 뽑아서 Shuffle Reply 메세지를 만든다.
최초로 Shuffle 메세지를 만들어서 발송한 'OriginNode'에게 Shuffle Reply 메세지를 발송한다.
받은 Shuffle 메세지에 포함된 노드들을 자신의 Passive View에 추가한다.

여기서 주목해야 할 부분은 Shuffle Reply를 응답하는 노드와 메세지를 받는 노드 사이에는 어떠한 관계도 정의되는 것이 없다는 것이다. Shuffle - Shuffle Reply 메세지를 주고 받는다고 해서 서로를 Active View에 추가하는 액션이 있지는 않다.

handle_cast({{shuffle_reply, ReceivedShuffledNodes}, _FromPid}, State0) ->
  io:format("[~p] node ~p received shuffle reply message. It put into its passive view.~n", [self(), self()]),
  State = add_all_passive(State0, ReceivedShuffledNodes),
  {noreply, State};

위 함수는 Shuffle Reply 메세지를 받았을 때, 실행되는 함수다. 하는 일을 살펴보자.

Shuffle reply 메세지에 포함된 ReceivedShuffledNodes를 자신의 Passive View에 추가한다

여기까지가 HyParView 프로토콜의 필요한 기초적인 프로토콜을 모두 코드로 옮긴 것이다.

10. 실행 결과 살펴보기

위에서 구성한 HyParView Node 코드를 이용해 erlang actor를 이용해 HyParView 클러스터 멤버쉽을 구축해보자. 실행할 시나리오는 아래와 같다.

main() ->
%%  process_flag(trap_exit, true),
  Config = #config{},

  hypar_view_node:start_link('A', Config),
  timer:sleep(1000),

  hypar_view_node:start_link('B', Config),
  timer:sleep(1000),

  hypar_view_node:start_link('C', Config),
  timer:sleep(1000),

  hypar_view_node:start_link('D', Config),
  timer:sleep(1000),

  hypar_view_node:start_link('E', Config),
  timer:sleep(1000),

  % Node 'A' puts Node 'B' into its active view.
  join('A', 'B'),

  % Node 'B' puts Node 'C' into its active view.
  join('B', 'C'),

  % Node 'B' puts Node 'D' into its active view.
  join('B', 'D'),

  % Node 'B' puts Node 'E' into its active view.
  join('B', 'E').

노드 A~E를 생성한다. (여기까지는 클러스터가 아닌 상태다)
join(...) 명령어를 이용해서 노드끼리 HyParView 클러스터에 가입하도록 한다.

여기서 join('B', 'C')는 노드 'C'를 노드 'B'의 Active View에 넣는 것을 의미한다. 위 코드를 실행하고 발생하는 로그를 살펴보자.

% 노드 A~E 초기화. 
[<0.101.0>] HyParView Node is initialized. NodeName: 'A', Pid: <0.101.0>
[<0.103.0>] HyParView Node is initialized. NodeName: 'B', Pid: <0.103.0>
[<0.104.0>] HyParView Node is initialized. NodeName: 'C', Pid: <0.104.0>
[<0.105.0>] HyParView Node is initialized. NodeName: 'D', Pid: <0.105.0>
[<0.106.0>] HyParView Node is initialized. NodeName: 'E', Pid: <0.106.0>

% 노드 B가 A의 Active View에 가입 요청.
[<0.101.0>] node <0.101.0> received api join message. try to join node 'B' to 'A''s active view.

% 노드 C가 B의 Active View에 가입 요청. 
[<0.103.0>] node <0.103.0> received api join message. try to join node 'C' to 'B''s active view.

% 노드 A는 노드 B로부터 Join 요청을 받음
[<0.101.0>] node <0.101.0> received join message. Newly Added PeerName 'B'.
...

% 노드 B는 노드 A로부터 neighbor 메세지를 받음. 노드 B - A는 서로를 Active View로 추가했음. 
[<0.103.0>] node <0.103.0> received neighbor message. FromPid <0.101.0> and HighPriority true.
...

노드 A에게 B가 가입했을 때의 관점에서는 이런 로그가 남게된다. 로그 A는 최초의 노드이기 때문에 Active View가 없어서 Forward Join할 상대가 없다. 따라서 노드 B로부터 Join 메세지를 받았을 때, Neighbor 메세지를 응답하는 것으로 초기 행동이 마무리 된다.

[<0.101.0>] HyParView Node is initialized. NodeName: 'A', Pid: <0.101.0>
[<0.103.0>] HyParView Node is initialized. NodeName: 'B', Pid: <0.103.0>
[<0.104.0>] HyParView Node is initialized. NodeName: 'C', Pid: <0.104.0>
[<0.105.0>] HyParView Node is initialized. NodeName: 'D', Pid: <0.105.0>
[<0.106.0>] HyParView Node is initialized. NodeName: 'E', Pid: <0.106.0>

...
[<0.103.0>] node <0.103.0> received api join message. try to join node 'C' to 'B''s active view.
...
[<0.103.0>] node <0.103.0> received api join message. try to join node 'D' to 'B''s active view.
[<0.103.0>] node <0.103.0> received api join message. try to join node 'E' to 'B''s active view.
[<0.103.0>] node <0.103.0> received join message. Newly Added PeerName 'C'.

...
[<0.104.0>] node <0.104.0> received neighbor message. FromPid <0.103.0> and HighPriority true.
[<0.103.0>] node <0.103.0> received join message. Newly Added PeerName 'D'.
[<0.103.0>] node <0.103.0> received join message. Newly Added PeerName 'E'.

% 노드 C는 노드 B로부터 'D'가 추가되었다는 forward_join 메세지를 받음. 
[<0.104.0>] node <0.104.0> received forward_join message. Newly Added PeerName 'D' and TTL 5.
[<0.105.0>] node <0.105.0> received neighbor message. FromPid <0.103.0> and HighPriority true.

% 노드 A는 노드 B로부터 'D'가 추가되었다는 foward_join 메세지를 받음.
[<0.101.0>] node <0.101.0> received forward_join message. Newly Added PeerName 'D' and TTL 5.
[<0.103.0>] node <0.103.0> received neighbor message. FromPid <0.104.0> and HighPriority true.
[<0.106.0>] node <0.106.0> received neighbor message. FromPid <0.103.0> and HighPriority true.
[<0.104.0>] node <0.104.0> received forward_join message. Newly Added PeerName 'E' and TTL 5.
[<0.105.0>] node <0.105.0> received forward_join message. Newly Added PeerName 'E' and TTL 5.
[<0.101.0>] node <0.101.0> received forward_join message. Newly Added PeerName 'E' and TTL 5.

노드 B에는 꽤 많은 노드들이 추가되려고 하기 때문에 노드 B 관련 로그는 제법 많이 남는다. 노드 B부터는 이미 Active View를 가지고 있기 때문에 이제 Forward Join이 가능해지게 된다. TTL 5짜리 Forward Join 메세지가 떠돌아다니게 되는데, 위 상황에서는 더 전파되지는 않는다. 왜냐하면 Forward Join 메세지를 보내는 노드, 자기 자신을 빼면 현재는 Active View 노드가 없는 상태이기 때문에 그렇다.

% 0.91.0 : Node A
% 0.93.0 : Node B
% 0.94.0 : Node C
% 0.95.0 : Node D
% 0.96.0 : Node E

% Node A는 shuffle을 실행함. 
[<0.91.0>] node <0.91.0> received do_shuffle message. <0.91.0> try to shuffle and send shuffle message to other active.

% Node B는 셔플 메세지를 받음. TTL = 2 -> 전송
[<0.93.0>] node <0.93.0> received shuffle message. <0.93.0> try to update its passive view or send it to other active node.
  OriginNodeName 'A', TTL 2
  
% Node E는 셔플 메세지를 받음. TTL = 1 -> 전송
[<0.96.0>] node <0.96.0> received shuffle message. <0.96.0> try to update its passive view or send it to other active node.
  OriginNodeName 'A', TTL 1

% Node B는 셔플 메세지를 받음. TTL = 0 -> 자기 자신에게 추가함. 
[<0.93.0>] node <0.93.0> received shuffle message. <0.93.0> try to update its passive view or send it to other active node.
  OriginNodeName 'A', TTL 0

% Node A는 Node B로부터 Shuffle Reply 메세지를 받음. -> 자기 자신의 Passive View에 추가함. 
[<0.91.0>] node <0.91.0> received shuffle reply message. It put into its passive view.
[<0.93.0>] node <0.93.0> received do_shuffle message. <0.93.0> try to shuffle and send shuffle message to other active.
[<0.95.0>] node <0.95.0> received shuffle message. <0.95.0> try to update its passive view or send it to other active node.
  OriginNodeName 'B', TTL 2
[<0.94.0>] node <0.94.0> received shuffle message. <0.94.0> try to update its passive view or send it to other active node.
  OriginNodeName 'B', TTL 1
[<0.95.0>] node <0.95.0> received shuffle message. <0.95.0> try to update its passive view or send it to other active node.
  OriginNodeName 'B', TTL 0
[<0.93.0>] node <0.93.0> received shuffle reply message. It put into its passive view.
[<0.94.0>] node <0.94.0> received do_shuffle message. <0.94.0> try to shuffle and send shuffle message to other active.
[<0.95.0>] node <0.95.0> received shuffle message. <0.95.0> try to update its passive view or send it to other active node.
  OriginNodeName 'C', TTL 2
[<0.93.0>] node <0.93.0> received shuffle message. <0.93.0> try to update its passive view or send it to other active node.
  OriginNodeName 'C', TTL 1
[<0.95.0>] node <0.95.0> received shuffle message. <0.95.0> try to update its passive view or send it to other active node.
  OriginNodeName 'C', TTL 0
[<0.94.0>] node <0.94.0> received shuffle reply message. It put into its passive view.

한편 do_shuffle - shuffle - shuffle_reply 메세지도 잘 동작하는 것을 확인할 수 있다. 위와 같이 Shuffle - Shuffle Reply 메세지를 활발하게 주고 받고 있는데 실제로 Passive View가 바뀌는지도 확인해봐야한다.

4> sys:get_state(<0.91.0>).
{hypar_view_node,'A',<0.91.0>,
                 #{'B' => <0.93.0>},
                 #{'C' => <0.94.0>},
                 {config,undefined,5,2,4,24,2,2,2,10000},
                 hypar_erl_reactor}
                 
 ...
 ...
 
 9> sys:get_state(<0.91.0>).
{hypar_view_node,'A',<0.91.0>,
                 #{'B' => <0.93.0>},
                 #{'C' => <0.94.0>,'E' => <0.96.0>},
                 {config,undefined,5,2,4,24,2,2,2,10000},
                 hypar_erl_reactor}

<0.91.0>은 노드 A의 PID이고, sys:get_state(...)를 이용해 상태를 확인할 수 있다. 이때, 노드 A의 Passive View에는 노드 'C'만 들어가있다. 얼마 간의 시간이 흐른 후에 다시 상태를 확인해보면 노드 A의 Passive View에 노드 'E'가 추가된 것을 확인할 수 있다. 이런 방식으로 HyParView 클러스터 멤버쉽에서 Passive View를 업데이트하는 과정을 살펴볼 수 있었다.

11. 요약

이번 포스팅에서는 클러스터 멤버쉽 프로토콜 중 하나인 HyParVIew Protocol을 공부하고, erlang으로 구현해보았다.

Full membership을 모두 포함하고 있던 SWIM 프로토콜은 클러스터 내의 노드가 많아질수록 클러스터 멤버쉽을 유지하기 위해 주고 받아야 할 메세지도 커지고, 저장해야 할 Local State도 커지기 때문에 대규모 클러스터로의 확장성은 상대적으로 떨어진다는 단점이 있었다.

반면 HyParView는 Partial View(부분 보기)라는 개념을 도입해 Active View라는 작은 규모의 Cluster끼리 서로 연결되게 하면서, 상대적으로 느슨한 결합을 가져간다. 이 덕분에 각 부분 클러스터에서 주고 받아야 할 메세지의 크기(멤버쉽 정보...)도 적어지고, 자기 자신이 기억해야 할 클러스터 State도 적어지기 때문에 수만 단위의 대규모 클러스터로의 확장이 가능하게 된다.

HyParView는 Active View와 Passive View로 나누어지는데, Active View는 TCP Connection을 맺고 있는 노드들로 볼 수 있다. Passive View는 노드의 IP 정도만 알고 있는 상태라고 보면 된다. 만약 Active View에서 누군가 떠나거나 셧다운이 되었을 때, 부분 클러스터가 고립되지 않도록 Passive View의 노드를 Active View로 올리는 형태로 클러스터의 안정성을 도모한다.

뿐만 아니라 각 노드가 가지고 있는 Passive View를 섞어주는 셔플 메세지를 주고 받으면서, Passive View 정보를 보다 최신화하며 HyParView 클러스터의 안정성을 도모한다.

HyParView 프로토콜은 각 노드 간의 물리적 네트워크(라우터 / 스위치 브릿지) 위에 논리적으로 Overlay 네트워크를 만들어둔 것이다. 논리적으로 구축된 네트워크 경로 위에서 메세지가 전파될 수 있도록 한다. 이때, 메세지의 전파 경로는 Gossip 프로토콜을 통해서 전파되게 된다.

또한 HyParView 프로토콜은 Split Brain 상에서 Data inconsistency는 해소해주지 않는다.

참고

https://www.bartoszsypytkowski.com/hyparview/

저작자표시 비영리 변경금지

'Distributed System' 카테고리의 다른 글

Distributed Consensus Algorithm : RAFT 합의 알고리즘 (0)	2025.03.09
Distributed Gossip Protocol : Plum tree 프로토콜 (0)	2025.02.14
Distributed Membership Protocol : SWIM 프로토콜 (0)	2025.01.31
분산 컴퓨팅 10. 벡터 시계와 스냅샷 찍기 (0)	2024.03.17
분산 컴퓨팅 3. 시간 동기화 문제와 논리적 시계 (램포트 시계) (0)	2024.03.17

만년 꼴지 공대생 세상 이야기