Fly.io 분산 시스템 챌린지(Maelstrom) 기록-3

#3: Broadcast(https://fly.io/dist-sys/3a, https://fly.io/dist-sys/3b)

N개의 노드로 이뤄진 클러스터 환경에서 gossip을 이용해 노드 간 데이터를 동기화하는 챌린지다.

gossip을 전송하기 위해 각 노드는 자신의 인접 노드를 관리한다. (partial membership)

네트워크 단절(partition) 상황은 발생하지 않는다는 전제가 있으므로, gossip 처리 시 오류가 발생하는 경우는 고려하지 않았다.

 

RPC(클라이언트 요청)는 3가지 유형이 존재한다.

1. broadcast

message 저장 요청이다. 클라이언트는 한 노드에만 요청하므로, 클러스터 내 노드가 모두 인지하기 위해선 gossip을 전파해야 한다.

인접한 노드와 gossip을 주고 받는데, 동일한 메세지 ID를 계속해서 주고받지 않도록 중복 방어 처리가 필요하다.

 

2. read

현재 노드가 저장하고 있는 message id 목록을 조회하는 요청이다. 모든 노드가 동일한 message id 목록을 보유하고 있는지 확인할 때 사용된다.

 

3. topology

클러스터의 topology 정보를 제공해주는 요청이다. 각 노드는 partial membership을 관리하고, gossip 전송 시점에 자신이 알고있는 노드에만 전파해주면 된다.

노드간 통신을 위해 멀티 스레드를 사용했고, topology 요청이 여러번 있을 것 같아 volatile로 관리했지만 처음에 1번만 요청된다.

private volatile List<String> neighbors;
...
List<String> newMembership = new ArrayList<>();
for (JsonNode adj : adjacent) {
    newMembership.add(adj.asText());
}
// swap
this.neighbors = newMembership;

 

결과 확인(3a: 단일 노드 환경)

# single node
./maelstrom test -w broadcast \
--bin run.sh \
--node-count 1 \
--time-limit 20 \
--rate 10

# expected
Everything looks good! ヽ(‘ー`)ノ

 

결과 확인(3b: 다중 노드 환경)

# multi node
./maelstrom test -w broadcast \
--bin run.sh \
--node-count 5 \
--time-limit 20 \
--rate 10

# expected
Everything looks good! ヽ(‘ー`)ノ

 

 

 

#3: Fault Tolerant Broadcast(https://fly.io/dist-sys/3c)

--nemesis partition

테스트 실행 시점에 위 옵션을 넣어주면 네트워크 분할(partition) 상황을 클러스터에 주입해준다.

네트워크 분할이 발생해 노드 간 통신(gossip)이 불가능한 경우 어떻게 처리해줘야 할까?

 

내가 생각한 방법은 두 가지 정도인데,

1. 재시도

gossip 요청에 실패한 경우 단순 재시도하는 방식이다. 재시도 횟수 제한, 부하 분산을 위한 jitter 혹은 exponential backoff 처리가 있으면 더 좋겠지만 해당 문제에서는 단순하게 재시도만 수행해도 문제없다.

 

2. hinted handoff

통신이 불가능한 노드에 전송될 요청을 현재 노드가 보유하고 있다가, 장애 해소 시점에 요청을 전송해 동기화를 수행하는 방법이다. 노드의 로컬에 handoff를 저장한 뒤 별도의 스케줄러가 일정 주기마다 요청을 전송해주면 되는데, 네트워크 분할이 정상화되는 시점과 스케줄러가 동작하는 시점의 불일치때문에 테스트가 실패할 가능성이 있다. 다만 maelstrom에서 모든 요청을 전송하고 난 뒤 검증 전 대기하는 시간을 갖기 때문에, 주기(interval)를 적절히 조절한다면 성공할 것이다.

 

결과 확인(3c: Fault Injection)

./maelstrom test -w broadcast \
--bin run.sh \
--node-count 5 \
--time-limit 20 \
--rate 10 \
--nemesis partition

# expected
Everything looks good! ヽ(‘ー`)ノ

 

 

 

#3: Efficient Broadcast(https://fly.io/dist-sys/3d, https://fly.io/dist-sys/3e)

개인적으로는 3번 도전에서 가장 중요한 부분이라고 생각한다.

이번에는 네트워크가 매우 혼잡한 상황에서 다음 지표를 특정 수치까지 만족해야 한다.

1. msgs-per-op: 클라이언트의 broadcast 요청 한 번이 클러스터의 gossip을 발생시킨 개수를 의미한다.

2. Median latency(p50)

3. Maximum latency(p100)

 

어떻게 클러스터 내 모든 노드에 데이터가 동기화되면서 msgs-per-op 지표를 낮출 수 있을까?

1. Spanning Tree

클러스터 전체가 연결된 상태를 유지할 수 있는 최소한의 간선(멤버쉽)을 유지하는 방식이다.

25개의 노드가 존재하는 상황을 가정해보면, 1개의 요청이 24개의 gossip으로 증폭된다. 이 때 ack 메세지까지 고려한다면, 총 48개의 메세지가 증폭되므로 3d 챌린지의 요건에도 만족이 어렵다. 

또한 N-1개의 간선을 유지하기 위해 설정을 공유하는 단계가 필요한데, 이 과정이 꽤나 복잡하고 기본 topology 구성 자체가 나름 최소한의 연결로 돼있으므로 다른 방법을 고려하는 것이 좋을 것이다.

 

2. Batch

위에서 이야기했듯, 메세지 전파를 최소로 하더라도 48번의 메세지 교환이 발생한다는 것을 알 수 있다. 그렇다면 메세지마다 전송하지 않고 배치로 한번에 전송하는 방법은 어떨까?

배치가 flush되는 기준은 두 가지로 설정했는데, kafka의 batch.size, linger.ms와 동일하게 구성했다.

- threshold를 넘어선 경우

- timeout

 

메세지 당 gossip으로 측정한 msgs-per-op 지표가 80~81 정도이므로, threshold 는 최소 5~6 정도로 설정해주면 될 것이다.

:net {:all {:send-count 27484,
     :recv-count 27480,
     :msg-count 27484,
     :msgs-per-op 15.251943},
     ...

6 정도로 설정해주니 msgs-per-op 가 15로 줄었다.

다만 배치 전송을 하니 p50, p100이 폭발적으로 늘었다. (p50: 1.11s, p100: 27.58s)

 

3. Random Peer

1번에서 이야기했듯이, topology 메세지에는 중복 간선이 존재한다. 따라서 네트워크에 발행되는 메세지 개수가 N(노드 개수)보다 큰 데, 이를 줄이기 위해서 노드에서는 자신이 알고있는 멤버쉽에서 k개를 샘플링해 gossip을 전송하도록 할 수 있다. 클러스터 내 동기화가 잘 이뤄질 수 있도록 k와 ttl 값을 조정해 msgs-per-op 개수를 좀 더 줄여줄 수 있다. 개인적으로는 노드가 보유한 partial membership에 전부 전송하는 편이 p100 지표가 낮아 적용하지는 않았다.

 

 

지연(latency)을 줄이기 위해선 어떻게 처리해야 할까?

위 과정에서 msgs-per-op 지표와 latency는 tradeoff 관계임을 유추할 수 있는데, 배치 관련 설정을 조절해보면서 latency 를 낮춰보도록 하자.

내가 설정한 값은 다음과 같다.

설정	값
executor thread(스레드 풀 내 스레드 개수)	4
threshold(임계값: batch.size)	10
timeout(임계값2: linger.ms)	200ms
schedule interval(스케줄러 실행 간격)	50ms

 

 

결과 확인

./maelstrom test -w broadcast \
--bin run.sh \
--node-count 25 \
--time-limit 20 \
--rate 100 \
--latency 100

# result
# 1. msgs-per-op
 :net {:all {:send-count 24981,
             :recv-count 24948,
             :msg-count 24981,
             :msgs-per-op 13.94029},
       :clients {:send-count 3684, :recv-count 3684, :msg-count 3684},
       :servers {:send-count 21297,
                 :recv-count 21264,
                 :msg-count 21297,
                 :msgs-per-op 11.884486},
       :valid? true},
       
# 2. latency
:stable-latencies {0 0,
                   0.5 1053,
                   0.95 1526,
                   0.99 1707,
                   1 1954},

 

 

github: https://github.com/bidulgi69/maelstrom-challenge 

GitHub - bidulgi69/maelstrom-challenge: https://github.com/jepsen-io/maelstrom, https://fly.io/dist-sys