Gossip 프로토콜이란?

소문과 전염병의 공통점은 뭘까?

바로 한번 시작하면 멈출 수 없다는 점이다

인류가 아직도 해결하지 못한 코로나 전염

2019년 11월 17일에 WHO가 팬데믹을 선포한 이후로 아직도 인류는 코로나와 싸우고 있다. 그만큼 한번 시작한 전염은 멈추기가 힘들다.

소문 또한 모두 비밀이라고 생각 하고 있지만 조금만 지나면 모두가 그 소문에 대해서 알고 있던 경험을 해본적이 있을 것이다.

코로나와 가십은 인간 사회에 많은 불행과 충돌을 가져다 주었지만, Distributed System에서는 정말 효과적으로 데이터를 퍼트리는 방법이 되었다

Multicast에 대해서는 링크를 참조하도록 하자

이 방법을 Gossip 혹은 Epidemic Multicast라고 한다.

Gossip Multicast들이 데이터를 퍼트리는 방법은 다음과 같다.

1. X개의 노드들을 Random하게 고른다
2. 고른 노드들에게 데이터를 전송하고 Gossip Muticast에 참여하게 한다.

한번 그림을 보면서 알아보자

Round 1.

하나의 노드에 데이터가 들어온다

Round 2.

소문을 들은(Multicast 데이터를 받은) Node에서,

X개의 (constant, 여기선 2) 다른 Node들을 고른후,

소문을 퍼트린다 (Multicast 데이터 전송)

Round 3.

Round 2 반복. 여기서 특징은 Random하게 고른 노드가 이미 Multicast를 받았는지 안받았는지를 고려하지 않는다 (UDP를 사용).

높은 확률로 Round 4에서 마지막 노드까지 데이터가 전달이 될 것을 예상할 수 있다.

1개의 첫 숙주 Node와 N개의 감염되지 않은 노드들이 있다고 하고,

변수 b는 노드들이 각 라운드에서 퍼트리는 노드들의 개수 라고 하자.

cLog(N) Round안에 (c는 constant) 감염된 노드들의 개수(Y)를 구하는 공식은 다음과 같다.

수학이 궁금하다면: https://courses.engr.illinois.edu/cs425/fa2020/L5.FA20.pdf의 17, 18, 29를 참조하도록 하자.

복잡한 수학은 흥미를 떨어뜨릴 수 있으므로 위 링크에서 확인 하도록 하자.

결국 요점은

1. 약 Log(N)의 시간안에 (낮은 Latency)
2. 거의 대부분의 노드들에게 데이터가 전송되며 (1 - 1 / (N ^ (cb - 2))
3. 노드들은 약 Log(N)의 Load만을 받게 된다.

물론 이 방법이 100% Failure Tolerant 한 방법은 아니다.

만약 Multicast 데이터를 갖고있는 모든 노드들이 한번에 동시에 Fail한다면 Multicast는 실패로 끝나게 된다.

하지만 한 Round라도 성공을 한다면 데이터가 퍼지는 현상을 걷잡을 수 없기에 (전세계가 노력함에도 불구하고 아직도 코로나가 정복되지 않은 부분을 생각해보자). Almost Failure Tolerant하다고 볼 수 있다.

O(log(N))의 Latency로 두 남자가 정보를 주고받는 풍경

결론: 말조심 코로나 조심합시다!

Distributed System에 관해서 쓰는 글들은 많은 부분들이 University of Illinois — Urbana-Champaign의 CS425 수업에서 가져 왔으며, 2020년 가을 수업을 진행한 교수인 Indranil Gupta에게 감사를 표한다. Lecture Slide는 https://courses.engr.illinois.edu/cs425/fa2020/lectures.html에서 찾아볼 수 있다.