Categories
xacdo

가십 프로토콜

가십 프로토콜은 여러 노드들이 서로의 정보를 교환하는 방법 중 하나이다.

이런 방법으로 가장 쉬운 건 마스터 서버를 하나 둬서, 마스터에서 각각의 노드들을 모니터링하던가, 아니면 각 노드들이 마스터에 자신의 정보를 보내는 것이다. 근데 그러다가 마스터가 죽으면 어떻게 될까? 모든게 실패한다.

물론 애초에 마스터가 잘 안 죽게 만드는게 좋겠지만, 사람 일이 그렇듯이 어딘가 실수할 수도 있고 그래서 100% 안 죽을 수는 없을 것이다. 그럼 마스터를 여러 대 두면 설마 동시에 죽지는 않을테니 좀 덜 실패하지 않을까? 예를 들어 마스터 한대가 죽을 확률이 1%라면 두대가 동시에 죽을 확률은 0.01%, 세대가 동시에 죽을 확률은 0.0001%로 낮아질 것이다. (숫자는 대략적인 거니까 참고만 하세요)

그럼 마스터를 어떻게 여러 대 동시에 운영할 수 있을까? 가장 쉬운 방법은 마스터 중에 왕 마스터를 하나 뽑아서 그걸 일단 쓰고, 나머지는 복제본으로 계속 왕 마스터를 복제하고 있다가 왕이 죽으면 대체하는 것이다. 근데 혹시라도 그 왕을 대체하는 복제본조차도 깨지면 어떡할까? 그럼 그 다음 복제본으로 대체해야겠지만, 그 이전에 평소에 복제본이 깨지는지를 판단해서 미리 빼버리는게 낫지 않을까?

이쯤되면 아니 뭐 이렇게까지 장애를 줄여야 하나, 그냥 실패하고 말지 하는 생각이 든다. 하지만 그래도 실패하면 실패하는 동안 돈을 못 버니까, 그 동안 날릴 돈을 생각하며 좀 더 나아가보자. 왕 마스터가 일방적으로 내가 정확하다, 너희 복제본들은 당연히 나와 똑같을 것이라고 전제하고 독재하는 대신에, 마스터들끼리 동등하게 서로 감시하면서 나쁜 노드를 몰아내고 좋은 노드 중에서 왕을 뽑는게 어떨까? 이게 좀 더 민주적이라서 실패할 확률이 낮아질 것이다.

그럼 이런 합의(consensus)를 어떻게 이룰 것인가? n개의 마스터들이 항상 서로를 감시하려면 n * (n-1) 번 호출해야 할테니, 적어도 이것보다는 효율적이어야 할 것이다. 그런 알고리듬으로 Paxos가 있는데 이게 너무 복잡해서 조금 비효율적이지만 단순하게 만든 Raft도 있다.

그리고 이런 Paxos를 구현하려면 프로그램이 너무 커져서, 그냥 서버 프로그램보다 Paxos 프로그램 부분이 더 커지는 지경에 이른다. 그리고 생각해보면 Paxos 부분은 다들 똑같이 쓸테니까 따로 떼어내서 재활용하고, 또 이런 합의 부분만 원래 마스터 서버와 별도로 돌리면 더 실패할 확률이 낮아질 것이다. 그래서 Zookeeper라고 Paxos만 별도로 해주는 것도 있다. 예를 들어 Kafka라고 해서 작은 데이터를 쓰기만 엄청 쓸 때 쓰는 게 있는데, 이걸 멀티 마스터로 만들면 Kafka 3대, Zookeeper 3대 이렇게 구성할 수 있다. 이게 최소한이다.

근데 이런 합의 알고리듬은 느리다. 마스터들끼리 서로 엄청 감시하니까 보통 3개에서 7개 정도만 두고, 그 이상 만들면 너무 느려진다. 그래서 결국은 소수의 마스터들이 전체를 지배하는 원로원 체제인 것이다. 여담으로 그래서 Paxos가 그리스의 섬 이름이고, Raft는 거기서 뗏목을 타고 탈출하는 의미다. 하여튼 그래서 이 그리스 시대의 민주정에서 더 나아갈 수 없을까? 그 방법으로 가십 프로토콜이 있다.

가십을 검색하면 드라마 가십걸이 뜬다. 그 가십걸의 가십이 맞다. 발 없는 말이 천리 간다고, 뜬 소문도 사람들 사이에서 돌다 보면 어느새 모든 사람들이 알게 될 것이다. “케빈 베이컨의 6단계 법칙”에서도 사람들이 서로 아는 사이끼리 6단계만 거치면 세상 사람 모두를 다 알게 될 거라고 말하는데, 좀 허풍이 섞이긴 했지만 이 가십 프로토콜도 비슷한 원리다. 예를 들어 25000대 서버들이 15개 서버에 서로 전파한다면, 15^4=50625니까 4단계면 된다…는 뻥이고 실제로는 30단계는 가야 거의 다 도달한다. 출처: https://en.wikipedia.org/wiki/Gossip_protocol#Examples

물론 초반의 몇 단계 안에 대부분의 서버들에 도달하겠지만, 그럼 모든 서버에 언젠가 완전히 도달한다는 보장이 있을까? 이게 마치 UUID가 대체로 unique하다는 것과 비슷한데, 정말 아주 낮은 확률로 안 그럴수도 있겠지만 사실 우리가 일상적으로 쓸 때는 웬만하면 괜찮을 것이다. 그래서 이건 약간 느슨한 방법이고, 정말로 완전히 엄밀하게 따져서 하나도 틀리고 싶지 않다면 가십 프로토콜을 쓰면 안된다.

그래서 가십 프로토콜은 보통 서버들이 엄청 많을 때 이게 죽었나 살았나, 아니면 상태가 괜찮은가 아닌가 모니터링 용도로 쓴다. 그러면 중앙 서버에 트래픽이 안 몰리고, 서버들 간에 주고받는데 그렇게 네트워크 대역폭을 쓰는 것도 아니고, 정말 아주 낮은 확률로 정보를 못 받아도 그렇게 심각한 건 아니라서 괜찮다.

또 중앙 집중을 싫어하고 완전한 분산 시스템을 추구하는 비트코인 등의 암호 화폐에서 쓰는데, 이건 다른 방법이 없기 때문에 어쩔 수 없이 쓰는 거다.

물론 가십 프로토콜을 위에서 말한대로 그냥 flat하게 쓰면 비효율적이니까, 좀 더 효율적으로 쓰는 방법들이 있다. http://highscalability.com/blog/2011/11/14/using-gossip-protocols-for-failure-detection-monitoring-mess.html

그리고 제 모든 글에 암시적으로 해당하는 거지만, 제 글이 잘못되거나 보충할 부분이 있으면 댓글을 달아주시면 적극적으로 반영하겠습니다.

By xacdo

Kyungwoo Hyun

Leave a Reply

Your email address will not be published.