분산시스템(Distributed System) - 3(Broadcast)

Broadcast는 그룹 통신이다.

하나의 노드에서 메시지를 발송한다면 그룹안에 모든 노드들은 메시지를 받는다. 그리고 reliable하다 죽지않은 노드에게는 메시지 누락없이 전송된다.

 

그룹에 속한노드는 고정될수도 있고 다이나믹하게 변할수도있지만 노드의 추가 및 제거에는 정해진 원칙(mechanism)을 가질것이다.

그룹내의 하나의 노드가 죽어도 나머지는 계속 돌아간다.

메시지의 latency에 대하여 제한을 두지 않는다.

 

broadcast를 하기 위해 unicast인 네트워크에서 broadcast를 하기 위해 위의 그림처럼 인터넷과 어플리케이션 사이에 미들웨어로 구현을 할것이다.

 

먼저 어떻게 모든 노드에게 메시지를 보낼것인다에 대해서 생각해보자

첫번째(eager reliable broadcast) 단순하게 A노드가 메시지를 모든 노드에게 보낸다 메시지를 받은 B노드도 받은메시지를 모두에게 보낸다. 하지만 O(n * n) 의 형태가 되어 비효율적이다. 그리고 엄청난 네트워크의 자원을 필요로한다. 노드가 많아진다면 감당이 되지않을것이다.

좀더 단순한 방법으로 Gossip protocols가 있다. 소문이 퍼지듯이 하나의 노드가 주변의 불특정한 노드에게 메시지를 보내는 것이다.

하나의 노드가 메시지를 전송시 정해진 수의 랜덤한 노드에게 메시지를 보낸다. 위의 eager reliable broadcast와 비교하면 전체노드에서 메시지를 보내는 수가 현저하게 줄것이다. 하지만 완벽하게 모든 노드에게 메시지를 보낸다고 보장할수는 없다. 일부의 메시지를 받지 못하는 경우는 몇개의 수의 노드에 보내는지 어떤 노드를 선택하는지에 따라서 굉장히 작을것이다. 큰 효율의 이득을 얻기위해 trade off할 정도라고 생각한다.

 

이제 살아있는 모든노드들은 메시지를 받을수 있게되었다. 받은 메시지의 순서를 어떻게 보장을 해야할까?

 

 FIFO, Causal, Total order 3가지 알고리즘이 있다. 셋은 순서보장에 대하여 다르다.

 

FIFO broadcast

동일한 노드에서 나온 메시지 m1과 m2는 발송된 순서를 보장한다.

 

위의 이미지에서 보면 A에서 메시지 m1과 m3를 보낸다.  m1과 m3의 순서는 보장되나 m2와의 관계는 보장이 되지않는다. 그래서 세가지의 경우의 수가 나올수 있다.

A노드(m1, m2, m3)

• m1을 자기자신에게 보내고 B와 C에 전송한다
• 노드 B에서 보낸 m2가 도착한다.
• m3를 자기자신에게 보내고 B와 C에 전송한다.

B노드(m1, m3, m2)

• 노드 A로부터 m1을 받는다.
• 노드 A로부터 m3를 받는다.
• m2를 자기자신에게 보내고 B와 C에 전송한다.

C노드(m2, m1, m3)

• 노드 B로부터 m2를 받는다.
• 노드 A로부터 m1을 받는다.
• 노드 A로부터 m3를 받는다.

모든경우가 같겠지만 C노드가 m3를 먼저 받아도 buffer나 queue에 m3를 가지고 있다 m1이 온다면 m1을 C노드의 어플리케이션에 전달후 m3를 전달 할것이다.

 

같은 노드로 부터 오는 메시지는 어떻게 구분하고 순서를 보장할수 있는것일까

FIFO broadcast 알고리즘은 기본적으로 세가지를 가진다 메시지를 보낸수(sendSeq), 받은 수(delivered), 버퍼(buffer) 메시지를 가진다.

sendSeq는 해당노드에서 메시지를 보낼때마다 +1 을한다.  delivered는 모든노드의 보낸수를 기록하고있다. buffer는 이전메시지보다 먼저오게 되면 머무는 곳이다.

i번째 노드에서 sendSeq를 +1를 하고 메시지를 전송한다.

메시지를 받은곳은 sendSeq와 delivered[i]를 비교하여 바로 받을수 있는 메시지면 받고 delivered를 업데이트한다.

중간에 받아야될 메시지가 있다면 buffer에 두고 이전 메시지를 기다린다. 메시지가 올 때마다 체크하여 적당한 순서가 되면 어플리케이션에 전달한다.

 

Causal broadcast

앞서 나온 FIFO보다 좀더 순서를 보장해주는 알고리즘이다. FIFO가 같은 노드에서 나온 메시지만 순서를 보장한다면 Causal은 노드 상관없이 happened before인 경우 순서를 보장한다.

(*happens before란 정확한 순서를 가진 이벤트의 관계를 말한다 ex) 노드 A에서 노드 B로 메시지를 전송한경우 노드A에서 메시지를 보낸 이벤트와 노드B에서 메시지를 받은 이벤트는 A happens before B relation을 가진다.)

 

위의 경우를 보면 FIFO와 다르게 두가지 경우만 가능하다. m1 과 m2 그리고 m1과 m3는 happened before 관계이다. 그래서 m2 와 m3의 순서만 바뀐경우만 존재 할수 있다.

 

각 노드는 FIFO처럼 sendSeq, delivered, buffer로 구성되어있다. 다른점은 메시지를 보낼때 메시지를 보낼때 delivered값을 Deps라는 값으로 추가해서 보낸다. 이때 delivered의 해당노드에 해당하는 값을 sendSeq와 같게 수정한다. 이를 이용하여 메시지를 보낼때 해당 노드가 다른 노드로부터 받은 메시지수의 값이 있고 이것과 다른 메시지의 sendSeq를 비교하여 happened before의 관계를 알수있다. 받는 노드는 메시지를 버퍼로 보낸뒤 어플리케이션으로 보낼차례가 있는지 검색하고 있다면 보낸다.

가장 철저하게 순서를 보장해주는 total-order-broadcast가 남아있다. total-order-broadcast를 이용하면 분산시스템에 존재하는 모든 노드는 같은 순서로 메시지를 받게 된다.

 

위의 그림처럼 여러 경우의 수가 나올수가 있다. 하지만 모든 노드가 같은 순서로 메시지를 받는다. 

두개의 그림에서 보면 순서를 보장하기 위해 causal broadcast처럼 버퍼에서 메시지를 저장하고 있다 순서가 되면 전송을 하고 있다. 1번에서는 A노드에 m3가 바로 전송되지않고 m2가 온뒤에 전송되는 모습을 볼수있다. 

여기에 FIFO까지 추가 된 형태인 FIFO-total-order-broadcast도 있다. 모든 노드가 같은 메시지의 순서를 가지면서 같은 노드에서 나온 메시지는 순서가 보장된다.

 

total-order-broadcast를 구현하기 위해서는 리더 노드가 필요하다. broadcast 메시지는 리더에게 전송이 되고 리더는 FIFO-broadcast 알고리즘을 이용하여 다른 노드에게 전달을 한다. 하나의 리더가 문제가 생기면 전체 시스템에 문제가 생길수있는 SPOF(single point of failure)가 된다. 그리고 이것을 서포트하기 위한 방법이 어렵다.

 

이 경우에 대해서는 뒤에 Consensus에 다룰것이다.

 

 

포스트의 모든 이미지는

https://www.youtube.com/channel/UClB4KPy5LkJj1t3SgYVtMOQ/videos 와 Introduction to Reliable and Secure Distributed Second Edition에 있다.