가십

여러 대의 노드가 서로 아는 것을 조금씩 옮겨 담아 결국 모두가 같은 것을 알게 만드는 전파 방식입니다. 모든 것을 아는 조정자를 가운데 두지 않습니다. 노드 하나가 주기적으로 상대를 무작위로 골라 자기가 아는 상태를 보냅니다. 받은 쪽이 그것을 또 남에게 옮기면서 소문처럼 번집니다.

상세

가십이 실어 나르는 것은 쓰는 자리마다 다릅니다. Xerox PARC 의 Demers 외 「Epidemic Algorithms for Replicated Database Maintenance」는 여러 사이트에 복제된 데이터베이스의 갱신을 퍼뜨려 복제본들을 일관성 쪽으로 끌고 가는 무작위 알고리즘들을 다룹니다. Apache Cassandra 공식 문서는 가십을 클러스터 부트스트래핑 정보를 퍼뜨리는 방법이라고 적습니다. 엔드포인트 멤버십, 노드 사이 네트워크 프로토콜 버전 같은 것입니다. Cassandra 에서 노드는 자기 상태만 보내지 않습니다. 자기가 아는 다른 노드의 상태까지 함께 보냅니다.

이 상태에는 (generation, version) 짝으로 된 벡터 시계가 붙습니다. generation 은 단조 증가하는 타임스탬프입니다. version 은 대략 1초마다 오르는 논리 시계입니다. 가십 메시지에 실려 온 논리 시계만 들여다보면 낡은 클러스터 상태를 무시할 수 있습니다.

감염이라는 어휘

이름은 병이 번지는 모양에서 왔습니다. 같은 논문은 역학 문헌의 어휘를 그대로 가져다 씁니다. 갱신을 남에게 나눠 줄 뜻이 있는 사이트를 그 갱신에 대해 감염된 사이트라고 부릅니다. 아직 갱신을 못 받은 사이트는 감염될 수 있는 사이트입니다. 갱신을 받았지만 더는 나눠 주지 않는 사이트는 제거된 사이트입니다.

SWIM(Scalable Weakly-consistent Infection-style Process Group Membership, 확장 가능한 약한 일관성 감염형 프로세스 그룹 멤버십) 논문도 같은 자리에 섭니다. 정보가 퍼지는 모양이 사회에서 소문이 퍼지는 모양, 또는 인구 집단에서 전염병이 퍼지는 모양과 닮았다고 적습니다. 그래서 감염형 전파라고 부릅니다. 감염형, 에피데믹, 가십형은 그 논문 안에서 같은 것을 가리키는 세 이름입니다.

원 논문이 가른 세 방식

Demers 외의 같은 논문은 갱신을 나르는 방법 셋을 갈라 이름 붙입니다.

직접 우편은 시의적절하고 꽤 효율적입니다. 다만 사이트가 다른 사이트 전부를 늘 알지는 못합니다. 우편이 유실되기도 합니다. 그래서 완전히 믿을 만하지는 않다고 논문은 적습니다. 반-엔트로피는 지극히 믿을 만합니다. 대신 데이터베이스 내용을 들여다봐야 해서 너무 자주 돌릴 수는 없습니다. 루머 몬거링의 회차는 반-엔트로피의 회차보다 잦을 수 있습니다. 사이트마다 드는 자원이 적기 때문입니다.

셋 가운데 반-엔트로피와 루머 몬거링이 감염 과정의 예라고 논문은 못 박습니다. 이 둘에는 감염 이론의 결과를 그대로 적용할 수 있습니다.

장애 감지와 전파의 분리

SWIM 논문은 멤버십 프로토콜이 하는 두 일을 갈라 놓았습니다. 장애를 감지하는 일과 멤버십 갱신을 퍼뜨리는 일입니다. 전통적인 하트비트 프로토콜은 이 둘을 한 덩어리로 다룹니다. 갈라 놓은 결과가 감염형 전파라고 논문은 적습니다.

HashiCorp Consul 공식 문서는 Serf 를 가십 프로토콜이라고 부릅니다. Consul 이 데이터센터 운영에 그것을 구현해 쓴다고 적습니다. 멤버십을 관리하고 클러스터에 메시지를 방송하는 자리입니다. Consul 은 가십 풀 두 종류를 씁니다. LAN(Local Area Network, 근거리 통신망) 가십 풀은 기본으로 켜져 있습니다. 데이터센터 하나 안의 모든 노드와 통신해 멤버십 정보를 나눕니다. WAN(Wide Area Network, 광역 통신망) 가십 풀은 주 데이터센터와 하나 이상의 부 데이터센터 사이로 에이전트 가십을 넓힙니다.

교환 순서

정상 왕복 하나를 SWIM 으로 끝까지 그립니다. 다른 갈래는 이 왕복이 어디에서 달라지는지로 붙입니다.

한 프로토콜 주기

길이 T 인 프로토콜 주기마다 노드 Mi 는 자기 멤버십 목록에서 멤버 하나를 무작위로 고릅니다. 고른 상대를 Mj 라고 합니다. Mi 는 Mj 에게 ping 을 보냅니다. 그리고 Mj 가 답할 ack 을 기다립니다.

미리 정한 시간 안에 ack 이 안 오면 Mi 는 Mj 를 간접으로 찔러 봅니다. Mi 는 멤버 k 개를 무작위로 골라 각각에게 ping-req 메시지를 보냅니다. 대상은 Mj 입니다. 이 k 개 가운데 고장 나지 않은 것들은 메시지를 받고 각자 Mj 에게 ping 을 보냅니다. Mj 에게서 ack 을 받으면 그것을 Mi 에게 전달합니다.

sequenceDiagram
    participant Mi
    participant Mj
    participant 중개자
    Mi->>Mj: ping
    Mj-->>Mi: ack
    Note over Mi,Mj: 시간 안에 ack 이 안 오면
    Mi->>중개자: ping-req 대상 Mj
    중개자->>Mj: ping
    중개자-->>Mi: 간접 ack

프로토콜 주기가 끝날 때 Mi 는 ack 을 하나라도 받았는지 봅니다. Mj 에게서 직접 받았거나 k 개 가운데 하나를 거쳐 간접으로 받았으면 됩니다. 하나도 없으면 Mi 는 자기 로컬 멤버십 목록에서 Mj 를 실패로 선언합니다. 그리고 이 갱신을 전파를 맡은 부품에 넘깁니다.

얹혀 가는 갱신

SWIM 의 확장판은 바깥의 멀티캐스트 수단을 아예 없앱니다. 대신 퍼뜨릴 정보를 장애 감지 프로토콜이 이미 만들고 있는 메시지에 얹어 보냅니다. ping, ping-req, ack 셋입니다. 전파 전용 메시지가 따로 돌지 않습니다.

살아 있음에서 고장까지

고장 나지 않은 멤버 Mj 가 다른 멤버 Mi 에게 실패로 잘못 감지될 수 있습니다. 이때 Mi 는 Mj 를 실패로 선언하지 않습니다. 대신 로컬 멤버십 목록에서 Mj 를 의심 멤버로 표시합니다. 그리고 Mi 가 Mj 를 의심한다는 메시지를 그룹에 퍼뜨립니다.

stateDiagram-v2
    [*] --> 살아있음
    살아있음 --> 의심: ack 이 안 온다
    의심 --> 살아있음: ping 성공 · alive
    의심 --> 고장: 시간 만료 · confirm
    고장 --> [*]

의심받는 멤버는 멤버십 목록에 그대로 남습니다. ping 대상을 고를 때도 고장 나지 않은 멤버와 비슷하게 취급됩니다. 어떤 멤버가 의심받는 Mj 에게 ping 을 성공시키면 앞서의 의심을 해제합니다. 그리고 Mj 가 살아 있다는 메시지를 퍼뜨립니다.

멤버십 목록의 의심 항목은 미리 정한 시간이 지나면 만료됩니다. 살아 있다는 메시지가 오기 전에 만료되면 Mi 는 Mj 를 고장으로 선언합니다. 로컬 멤버십 목록에서 떨어뜨립니다. 그리고 Mi 가 Mj 를 고장으로 선언한다는 메시지를 퍼뜨리기 시작합니다.

한 멤버가 사는 동안 의심받았다 풀렸다를 여러 번 되풀이할 수 있습니다. 그래서 그 여러 판을 구별할 식별자가 필요합니다. 그 자리를 incarnation number 가 맡습니다. 멤버 Mj 의 incarnation number 는 그룹에 들어올 때 0 입니다. 올릴 수 있는 것은 Mj 자신뿐입니다. 지금 판에서 자기가 의심받고 있다는 정보를 받으면 Mj 가 번호를 하나 올려 살아 있다는 메시지를 냅니다. suspect 메시지와 alive 메시지는 멤버 식별자와 함께 이 번호를 싣습니다. 로컬 멤버십 목록에 반영될 때 alive 는 suspect 를 덮습니다. confirm 은 그 둘을 다 덮습니다.

카산드라의 매초 한 회차

Apache Cassandra 는 노드마다 가십 작업을 각자 주기적으로 돌립니다. 클러스터의 모든 노드가 매초 네 가지를 합니다.

1. 로컬 노드의 하트비트 상태를 갱신합니다. 그것이 version 입니다. 그리고 클러스터 가십 엔드포인트 상태에 대한 자기 관점을 구성합니다.
2. 클러스터에서 다른 노드 하나를 무작위로 골라 가십 엔드포인트 상태를 교환합니다.
3. 닿지 않는 노드가 있으면 확률적으로 그 노드와도 가십을 시도합니다.
4. 두 번째 단계에서 씨앗 노드와 가십하지 않았으면 씨앗 노드와 가십합니다.

씨앗 노드는 운영자가 클러스터를 처음 부트스트랩할 때 지정합니다. 어떤 노드든 씨앗 노드가 될 수 있습니다. 씨앗 노드와 아닌 노드의 유일한 차이는 다른 씨앗 노드를 보지 않고도 링에 부트스트랩해 들어올 수 있다는 것입니다. 클러스터가 한 번 부트스트랩되고 나면 네 번째 단계 때문에 씨앗 노드가 가십의 핫스팟이 됩니다.

누가 먼저 보내나

반-엔트로피는 두 사이트가 차이를 해소하는 절차를 셋 중 하나로 표현할 수 있습니다. 원 논문이 붙인 이름은 push, pull, push-pull 입니다.

예시

Redis Cluster 의 클러스터 버스

Redis Cluster 의 모든 노드는 TCP(Transmission Control Protocol, 전송 제어 프로토콜) 버스와 이진 프로토콜로 이어져 있습니다. 이 통로의 이름이 Redis Cluster Bus 입니다. 노드마다 클러스터의 다른 모든 노드와 이 버스로 연결됩니다. 노드는 가십 프로토콜로 클러스터 정보를 퍼뜨립니다. 여기서 새 노드를 발견합니다. ping 패킷을 보내 다른 노드들이 제대로 도는지도 확인합니다. 특정 조건을 알리는 클러스터 메시지도 이 통로로 보냅니다.

오가는 것은 ping 과 pong 패킷입니다. 공통 헤더에 다음이 실린다고 Redis 공식 클러스터 명세는 적습니다.

ping 과 pong 패킷에는 가십 절이 따로 붙습니다. 이 절은 보내는 노드가 클러스터의 다른 노드들에 대해 무엇을 알고 있는지를 받는 쪽에 보여 줍니다. 가십 절에는 보내는 노드가 아는 노드 집합 가운데 무작위로 고른 몇 개의 정보만 들어갑니다. 언급되는 노드 수는 클러스터 크기에 비례합니다. 가십 절에 들어가는 노드마다 실리는 것은 셋입니다. 노드 ID, 노드의 IP(Internet Protocol, 인터넷 프로토콜) 주소와 포트, 노드 플래그입니다.

장애 표시는 두 단계입니다. 어떤 노드가 NODE_TIMEOUT 시간을 넘겨 닿지 않으면 다른 노드가 그 노드에 PFAIL 플래그를 답니다. PFAIL 플래그만으로는 복제본 승격을 일으킬 수 없습니다. 그것은 노드마다 다른 노드에 대해 갖는 로컬 정보일 뿐입니다. 노드가 다운된 것으로 취급되려면 PFAIL 조건이 FAIL 조건으로 올라가야 합니다.

HashiCorp memberlist 의 설정 손잡이

memberlist 는 가십과 탐사 동작을 설정 필드로 여는 Go 라이브러리입니다. 공식 패키지 문서가 필드마다 무엇을 정하는지 적어 둡니다.

GossipNodes 를 올리면 가십 메시지가 클러스터를 가로질러 더 신속하게 퍼진다고 같은 문서는 적습니다. 대가는 대역폭 증가입니다.

보장과 가정

결국 모두가 감지한다

SWIM 논문은 장애 감지 프로토콜을 재는 성질 넷을 세웁니다. 강한 완전성, 감지 속도, 정확성, 네트워크 메시지 부하입니다. 강한 완전성은 어떤 그룹 멤버의 크래시 실패든 고장 나지 않은 모든 멤버가 감지한다는 것입니다. 정확성은 장애 감지의 오탐 비율입니다.

가정은 무겁습니다. 비동기 네트워크 위에서 정확성과 강한 완전성을 둘 다 갖춘 장애 감지기를 만드는 것은 불가능하다고 증명돼 있습니다. 논문은 그 불가능성을 인용합니다. 전형적인 분산 응용은 강한 완전성이 늘 성립하는 데 기댑니다. 그래서 대부분의 장애 감지기는 그 성질을 보장하되 오탐 비율을 낮게 유지하려 애쓴다고 논문은 적습니다. SWIM 도 같은 길을 택합니다.

그래서 오탐은 사라지지 않습니다. 살아 있는 노드가 실패로 표시되는 일이 남습니다. 의심 절차가 그 선언을 늦추려고 놓인 자리입니다.

감지까지 걸리는 시간

기본 SWIM 장애 감지 프로토콜은 평균적으로 상수 개의 프로토콜 주기 안에 장애를 감지합니다. 각 프로세스 실패가 결국 다른 모든 고장 나지 않은 프로세스에서 감지되는 것도 보장됩니다. 이 성질의 이름이 최종적 강한 완전성입니다.

이 약속은 ping 대상이 고르게 흩어진다는 가정 위에 섭니다. 그룹 전체에 걸쳐 ping 대상이 병적으로 선택되면 첫 감지까지 큰 지연이 생길 수 있습니다. 극단적인 경우 실패한 프로세스가 어떤 고장 나지 않은 프로세스에게도 끝내 ping 대상으로 뽑히지 않을 수 있습니다. 그러면 이 지연은 유계가 아니게 됩니다.

논문이 내놓은 처방은 ping 대상을 무작위가 아니라 라운드로빈으로 고르는 것입니다. 그 자리에 붙은 이름이 시간 유계 강한 완전성입니다.

그룹이 커져도 늘지 않는 부담

SWIM 이 만드는 패킷은 그룹 크기와 무관하게 최대 135바이트입니다.

수렴의 강도가 갈래마다 다르다

반-엔트로피는 단순 감염 과정의 하나입니다. 단순 감염이 결국 전체 인구를 감염시킨다는 것은 감염 이론의 기본 결과라고 Demers 외의 논문은 적습니다. 우편이 갱신을 사이트 하나 너머로 퍼뜨리지 못하더라도 반-엔트로피가 결국 그것을 네트워크 전체에 나눠 줍니다. 대신 반-엔트로피는 데이터베이스 내용을 들여다봐야 합니다. 그래서 너무 자주 돌릴 수 없습니다.

루머 몬거링은 약속의 강도가 다릅니다. 갱신이 모든 사이트에 닿지 않을 어느 정도의 가능성이 있습니다. 감염이 끝났을 때 남은, 감염될 수 있는 사이트의 값을 논문은 잔여라고 부릅니다. 잔여는 작을수록 바라는 바라고 적습니다.

수치도 붙어 있습니다. 논문은 루머 몬거링의 한 변형을 식으로 풉니다. 그 식의 지배항은 감염될 수 있는 사이트가 k 가 커질수록 지수적으로 줄어드는 모양을 보입니다. 그래서 k 를 키우는 것이 거의 모두가 소문을 듣게 하는 효과적인 방법이라고 논문은 적습니다. 이 식이 시사하는 수치는 이렇습니다. k 가 1 이면 20퍼센트가 그 소문을 놓칩니다. k 가 2 면 6퍼센트만 놓칩니다.

로컬 판정과 전파의 경계

가십이 링 멤버십의 바탕을 이룹니다. 다만 노드가 살았는지 죽었는지에 대한 최종 판정은 장애 감지기가 내린다고 Apache Cassandra 공식 문서는 적습니다. 노드마다 파이 누적 장애 감지기의 변형을 돌립니다. 노드마다 상대 노드가 쓸 수 있는 상태인지를 독립적으로 계속 판단합니다. 이 판단은 주로 받은 하트비트 상태에 기댑니다. 어떤 노드에서 하트비트가 일정 시간 동안 오르지 않으면 장애 감지기가 그 노드를 유죄로 판정합니다. 그 시점부터 Cassandra 는 그 노드로 읽기를 라우팅하지 않습니다. 쓰기는 대개 힌트로 기록됩니다.

여기에 경계가 하나 있습니다. up 과 down 상태는 로컬 노드의 판정이고 가십으로 전파되지 않습니다. 가십으로 전파되는 것은 하트비트 상태입니다. 그리고 노드들은 실제 네트워크 채널로 서로에게 메시지를 성공적으로 보낼 수 있기 전까지는 서로를 up 으로 여기지 않습니다.

관련 항목

갱신을 퍼뜨리는 다른 방식

반-엔트로피 · 루머 몬거링 · 직접 우편

함께 쓰이는 복구·가용성 장치

머클 트리 · 힌티드 핸드오프 · 느슨한 정족수 · 힌트

장애 감지가 지키는 성질

강한 완전성 · 최종적 강한 완전성 · 시간 유계 강한 완전성 · 정확성 · 감지 속도 · 네트워크 메시지 부하 · 오탐

장애를 감지하는 수단

하트비트 · 장애 감지기 · 파이 누적 장애 감지기 · 라운드로빈

상태의 새로움을 가리는 눈금

벡터 시계 · 논리 시계 · 단조 시계 · 에포크 · incarnation number · 충돌 해소

클러스터를 이루는 구성 요소

노드 · 클러스터 · 씨앗 노드 · 엔드포인트 · 링 · 정족수 · 일관 해싱 · 해시 슬롯 · 분단

이것을 실제로 구현·채택한 제품과 프로토콜

SWIM · Serf · HashiCorp Consul · Apache Cassandra · Redis Cluster · Amazon Dynamo · memberlist