Gossip Protocol

Gossip Protocol

Gossip Protocol

가십 프로토콜이란 분산 환경에서 메시지를 전달하는 커뮤니케이션 방식의 하나이다.

외국에서는 바이러스가 퍼지는 방식으로 동작한다하여 Epidemic Protocol 과 동의어로 사용되기도 한다고 한다.

가십 커뮤니케이션 방식의 특징은 소문이 전파되어나가듯 Broadcast 해주는 마스터가 없이 각 노드가 주기적으로 TCP/UDP 기반으로 메타데이터를 주고받으면서 데이터를 전송하는 점에 있다.

각 노드들은 주기적으로 다른 노드의 Health Check 를 수행하고 통신하므로, 주기적으로 Peer to Peer (P2P) 의 통신으로 전달이 일어나며, 일반적으로 신뢰성은 보장하지 않는다.

다음 그림을 통해 일반적인 분산 환경에서의 싱크업 방식인 Mesh Broadcast 방식과의 차이점을 확인할 수 있다.

소문이 한번 시작하면 멈추지 않듯이, Gossip 프로토콜도 그러하다.

그림을 보면서 이해해보자.

Round 1 : 노드에 데이터가 들어온다.

Round 2 : 소문을 들은 (Multicast 데이터를 받은) 노드에서 X개의 다른 Node들을 고른 후, 소문을 퍼트린다.

Round 3 : Round 2를 반복한다.

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

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

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

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

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

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

결국 요점은

1. 약 Log(N)의 시간안에 (낮은 Latency)

2. 거의 대부분의 노드들에게 데이터가 전송되며 (1 - 1 / (N ^ (cb - 2))

3. 노드들은 약 Log(N)의 Load만을 받게 된다.

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

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

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

Almost Failure Tolerant하다고 볼 수 있다.