[번역] Redis Cluster Specification: (5) Configuration handling, propagation, and failovers

원문: https://redis.io/topics/cluster-spec

Cluster current epoch

레디스 클러스터는 Raft 알고리즘의 **term과 유사한 개념을 사용한다. 레디스 클러스터에서 이 용어는 대신 epoch라고 하며, 이벤트에 대한 증분 버전을 부여하기 위해서 사용된다. 여러 노드에서 충돌하는 정보를 제공하면, 또 다른 노드는 어떤 상태가 가장 최신인지를 알 수 있게 된다.

currentEpoch는 64비트의 부호없는 수이다.

노드 생성 시, 모든 레디스 클러스터 노드는 마스터와 리플리카 모두 currentEpoch를 0으로 설정한다.

다른 노드에게서 패킷을 받을 때마다, 만약 전송하는 노드(클러스터 메시지 헤더의 일부분의)의 epoch가 로컬 노드의 epoch보다 크다면, currentEpoch는 전송하는 노드의 epoch로 업데이트된다.

이러한 의미론(semantics)으로 인해, 결국 모든 노드는 클러스터 내에서 가장 큰 currentEpoch에 대해서 합의할 것이다.

이 정보는 클러스터의 상태가 변경되고, 노드가 어떤 액션을 취하기 위해서 동의를 구할 때 사용이 된다.

현재 이것은 다음 섹션에서 설명된대로 리플리카의 승격동안에만 발생하고 있다. 기본적으로 epoch는 클러스터에 대한 논리적인 시계(clock)이고, 주어진 정보는 더 작은 epoch를 가진 것을 이기게 한다.

Configuration epoch

모든 마스터는 항상 자신이 담당하는 슬롯의 셋에 대한 비트맵과 함께 configEpoch를 핑/퐁 패킷으로 전파한다.

노드가 생성될 때, 마스터 노드 내에서 configEpoch는 0으로 설정된다.

새로운 configEpoch는 리플리카의 승격중에 생성된다. 장애난 마스터를 대체하려는 리플리카는 epoch를 증가시키고, 과반 수의 마스터로부터 권한을 받으려고 시도한다. 승인이 된다면, 새로운 유니크한 configEpoch가 만들어지고, 리플리카는 이 새로운 configEpoch를 이용해서 마스터로 전환된다.

다음 섹션에서 설명하는대로, 서로 다른 노드가 일치하지 않는 구성 정보를 주장할 때(네트워크 파티션과 노드 장애 때문에 발생할지도 모르는 상태), configEpoch는 이러한 충돌을 해결하는데 도움이 된다.

리플리카 노드는 또한 configEpoch 핑/퐁 패킷으로 전파하는데, 리플리카의 경우 이 필드는 자신의 마스터와 가장 마지막으로 패킷을 교환한 시간의 configEpoch를 나타낸다. 이것은 리플리카가 업데이트가 필요한 오래된 구성 정보를 가지고 있을 때, 다른 인스턴스가 이를 발견할 수 있게 한다 (마스터 노드는 오래된 구성 정보를 가진 리플리카에게 투표하지 않을 것이다).

어떤 알려진(known) 노드에 대해 configEpoch가 바뀔 때마다, 이러한 정보를 받은 모든 노드들은 nodes.conf 파일에 이를 영구적으로 저장한다. 또한, currentEpoch 값에 대해서도 동일한 일이 발생한다. 이 2가지 변수는 어떤 노드가 작업을 계속하기 전에 업데이트 될 때, 디스크로의 저장과 fsync-ed가 보장된다.

페일오버 동안에 단순한 알고리즘을 이용해서 만들어지는 configEpoch 값은 새롭고, 증분된 값이고, 유니크한 것이 보장돤다.

Replica election and promotion

리플리카 선거와 승격은 리플리카 노드에 의해서 진행되며, 마스터 노드들은 리플리카 노드가 승격하는 것에 대해서 투표함으로써 이를 돕는다.
리플리카의 선거는 마스터가 되려고 하는 전제 조건을 가진, 적어도 하나 이상의 리플리카 노드의 관점에서, 자신의 마스터 노드가 FAIL상태일 때 발생한다.

리플리카가 자신을 마스터로 승격시키기 위해서, 선거를 시작하고 승리할 필요가 있다. 주어진 마스터에 대한 모든 리플리카들은 마스터가 FAIL 상태이면, 선거를 시작할 수 있지만, 오직 하나의 리플리카가 선거에서 승리하고, 자신을 마스터로 승격시킬 것이다.

다음의 조건이 충족되면, 리플리카는 선거를 시작한다.

• 리플리카의 마스터가 FAIL 상태이다.
• 마스터는 하나 이상의 슬롯을 서빙한다.
• 리플리카 리플리케이션 링크가 마스터로부터 정해진 시간보다 더 오랜 시간동안 끊긴 상태이고, 승격된 리플리카의 데이터가 적당히 최근의 데이터를 유지한다. 이 시간은 유저가 변경할 수 있다.

선출되기 위한 리플라카의 첫 단계는 currentEpoch 카운터를 증가시키고, 마스터 인스턴스들에 투표를 요청하는 것이다.

투표는 리플리카가 클러스터의 모든 마스터 노드에게 FAILOVER_AUTH_REQUEST 패킷을 전파함으로써 요청된다. 그리고 나서 최대 NODE_TIMEOUT의 2배의 시간동안 응답이 도착하기를 기다린다 (언제나 최소 2초동안).

마스터가 어떤 리플리카에 대해서 FAILOVER_AUTH_ACK로 긍정적인 응답함으로써 투표하면, 동일한 마스터의 또 다른 리플리카에 대해서는 NODE_TIMEOUT * 2의 시간 동안은 더 이상 투표할 수 없다. 이 시간동안에 동일한 마스터에 대한 다른 권한 요청에 대해서는 응답할 수 없다. 이것은 안정성을 보장하기 위해서 필요한 것은 아니지만, 여러 리플리카가 동시에 선출되는 것(심지어 configEpoch가 다르더라도)을 방지하는 것에는 유용하며, 보통은 필요하지 않다.

리플리카는 투표 요청이 전송되었을 때, currentEpoch 값보다 작은 에포크를 가진 AUTH_ACK 응답들은 폐기한다. 이것은 이전 선거를 위해 만들어진 투표는 계산되지 않는다는 것을 보장한다.

리플리카가 과반 수의 마스터로부터 ACK 응답을 받으면, 선거에서 승리하게 된다.
그렇지 않고 NODE_TIMEOUT의 2배(언제나 최소 2초)의 시간내에 과반수로부터 도달하지 않았다면, 이 선거는 취소되고 새로운 선거가 NODE_TIMEOUT * 4(그리고 언제나 최소 4초) 이후에 다시 시도될 것이다.

Replica rank

마스터 노드가 FAIL상태가 되자마자, 리플리카는 선거를 시도하기 전에 짧은 시간동안 기다린다. 이러한 지연 시간은 다음과 같이 계산된다.

DELAY = 500 milliseconds + random delay between 0 and 500 milliseconds +
        REPLICA_RANK * 1000 milliseconds.

이 고정된 지연 시간은 FAIL 상태가 클러스터 전체에 전파될 때까지 기다리게 하는데, 그렇지 않으면 다른 마스터들이 아직 FAIL상태를 인식하지 못하고 투표를 거부하는 동안에, 리플리카는 선출되려고 시도할지도 모른다.

랜덤한 지연 시간은 리플리카를 비동기화하기 위해서 사용되고, 그래서 동시에 선거를 시작하지 않을 것이다.

REPLICA_RANK는 마스터에서 처리한 리플리케이션 데이터의 양과 관련된 이 리플리카의 순위이다. 리플리카는 마스터가 실패하고 있는 상태일 때, (최선의) 순위를 결정하기 위해서 메시지를 교환한다.
가장 최신의 리플리케이션 오프셋을 가진 리플리카는 0순위이고, 두 번째로 최신인 것은 1순위 등이다. 이러한 방식으로 가장 최신의 리플리카는 다른 리플리카들보다 먼저 선거를 시도할 수 있다.

랭킹의 순서는 엄격하게 강제되지 않는다. 만약 더 높은 순위의 리플리카가 선출에 실패했다면, 다른 노드들이 곧바로 시도할 것이다.

리플리카가 선거에서 승리하면, 유니크하고, 증분된 새로운 configEpoch값을 획득하며, 이 값은 기존의 어떤 다른 마스터의 것보다도 높은 값이다. 그리고 핑/퐁 패킷으로 자신을 마스터로 알리기 시작한다.

다른 노드들의 재구성의 속도를 높이기 위해서, 퐁 패킷은 클러스터의 모든 노드에게 광범위하게 전파된다. 현재 연결할 수 없는 노드들은 핑/퐁 패킷을 다른 노드들로부터 받을 때 재구성되거나, 하트비트 패킷을 통해서 발행되는 정보가 오래된 것으로 감지되면 다른 노드로부터 UPDATE 패킷을 수신하게 될 것이다.

다른 노드들은 동일한 슬롯들을 이전(old) 마스터가 처리했지만, 더 큰 configEpoch 값을 가지는 새로운 마스터를 발견할 것이고, 자신의 구성을 업그레이드할 것이다. 이전 마스터의 리플리카들(또는 클러스터에 다시 합류하면서 페일오버된 마스터)은 구성을 업그레이드할 뿐만 아니라, 새로운 마스터를 복제하도록 재구성될 것이다.

Masters reply to replica vote request

이전 섹션에서는 리플리카가 선출되기 위해 시도하는 방법에 대해서 이야기했다. 이번 섹션에서는 지정된 리플리카에 대해서 투표를 요청받는 마스터의 관점에서 무슨 일이 발생하는지를 설명할 것이다.

마스터는 리플리카로부터 FAILOVER_AUTH_REQUEST 요청의 형식으로 투표 요청을 수신한다.

투표가 승인되기 위해서 다음의 조건들이 충족될 필요가 있다.

1. 마스터는 주어진 에포크동안에 한 번만 투표하고, 오래된 에포크에 대한 투표는 거절한다. 모든 마스터는 lastVoteEpoch 필드를 가지고, 인증 요청 패킷 내의 currentEpoch가 lastVoteEpoch보다 크지 않는 한은 재투표하는 것은 거절할 것이다.
   마스터가 투표 요청에 긍정적으로 응답할 때, lastVoteEpoch는 그에 따라 업데이트되고, 안전하게 디스크로 저장된다.
2. 마스터는 리플리카의 마스터 노드가 FAIL로 플래그된 경우에만, 리플리카에 투표한다.
3. 마스터의 currentEpoch보다 더 작은 currentEpoch를 가진 인증 요청은 무시된다. 이러한 이유로 마스터 응답은 항상 인증 요청과 동일한 currentEpoch를 가진다. 만약, 동일한 리플리카가 currentEpoch를 증가시켜서 다시 투표를 요청한다면, 마스터로부터의 오래된 지연된 응답은 새로운 투표에서는 받아들여지지 않는 것이 보장된다.

3번 규칙을 사용하지 않음으로써 발생하는 이슈의 예:

마스터의 currentEpoch는 5이고, lastVoteEpoch는 1이다. (이것은 몇 번의 실패한 선거 후에 일어날 수 있다)

• 리플리카의 currentEpoch는 3이다.
• 리플리카는 epoch 4 (3+1)로 선거를 시도할 것이고, 마스터는 currentEpoch 5로 OK를 응답할 것이다. 하지만 응답은 지연된다.
• 리플리카는 이후에 epoch 5 (4+1)를 이용해서 다시 선거를 시도할 것이고, currentEpoch 5를 가진 지연된 응답이 리플리카에 도달하고, 유효한 것으로 받아들여진다.

4. 만약 어떤 마스터의 한 리플리카가 이미 투표되었다면, 다른 마스터들은 동일한 마스터의 리플리카에 대해서는 NODE_TIMEOUT * 2가 경과되기 전에는 투표하지 않는다. 동일한 에포크 내에서 두 개의 리플리카가 선거에서 승리할 수는 없기 때문에 이것이 엄격하게 요구되지는 않는다. 하지만, 실제로는 리플리카가 선출되면 다른 리플리카에 알리기 위한 충분한 시간을 확보할 수 있고, 또 다른 리플리카가 새로운 선거에서 승리하여 불필요한 두 번째 페일오버가 수행될 수 있는 가능성을 막을 수 있다.
5. 마스터는 어떤식으로든 최선의 리플리카를 선택하기 위해서 노력을 하지는 않는다. 만약 어떤 리플리카의 어떤 마스터가 FAIL 상태이고, (다른) 마스터는 현재의 조건에서 투표하지 않았다면, 찬성표가 부여된다. 최선의 리플리카는 다른 리플리카보다 먼저 선거를 시작하고 승리할 가능성이 높은데, 이것은 이전 섹션에서 설명한대로 더 높은 순위(higher rank) 덕분에 일반적으로는 더 일찍 투표 절차를 시작할 수 있기 때문이다.
6. 마스터가 지정된 리플리카에 대한 투표를 거절할 때, 부정적인 응답은 없으며, 요청은 단순히 무시된다.
7. 마스터는 리플리카가 소유를 주장하는 슬롯에 대해서, 마스터 테이블 내의 어떤 configEpoch보다 더 작은 configEpoch를 보내는 리플리카에는 투표하지 않는다. 리플리카는 자신의 마스터의 configEpoch와 마스터가 담당했던 슬롯의 비트맵을 보낸다는 것을 기억해야 한다. 이것은 투표를 요청하는 리플리카는 페일오버를 하기를 원하는 슬롯에 대한 구성(configEpoch)이 투표를 승인하는 마스터의 것과 같거나 또는 더 커야한다는 것을 의미한다.

Practical example of configuration epoch usefulness during partitions

이 섹션에서는 리플리카 프로모션 프로세스를 파티션에 더 잘 견디게 하기 위해 에포크 컨셉이 사용되는 방법을 설명한다.

• 마스터는 무기한으로 더 이상 접근 가능하지 않다. 마스터는 A, B, C 각각 3개의 리플리카를 가진다.
• 리플리카 A는 선거에서 승리하고, 마스터로 승격된다.
• 네트워크 파티션은 클러스터의 과반수에서 A를 사용할 수 없는 상태로 만든다.
• 리플리카 B는 선거에서 승리하고, 마스터로 승격된다.
• 파티션은 클러스터의 과반수에서 B를 사용할 수 없는 상태로 만든다.
• 이전 파티션이 해결되고, A가 다시 접근 가능해진다.

이 시점에 B는 다운되었고, A는 마스터 역할로 다시 사용이 가능해진다(실제로 UPDATE메시지는 즉시 재구성하지만, 여기서는 모든 UPDATE 메시지가 손실된 것으로 가정한다). 동시에, 리플리카 C는 B를 페일오버하기 위해서 선거를 시도할 것이다.

1. 과반 수의 마스터에게 C의 마스터가 실제로 다운상태이므로, C는 선거를 시도할 것이고, 성공할 것이다. 그리고 새로운 증분된 configEpoch 값을 획득할 것이다.
2. A는 그 해시 슬롯들의 마스터라고 주장할 수가 없는데, 왜냐하면 다른 노드들은 A가 제시하는 것과 비교해서 더 높은 configEpoch(B의 것)와 연결된 동일한 해시 슬롯을 이미 가지고 있기 때문이다.
3. 그래서 모든 노드는 해시 슬롯들을 C로 할당하기 위해 그들의 테이블을 업그레이드 할 것이고, 클러스터는 동작을 계속할 것이다.

다음 섹션에서 볼 수 있듯이, 클러스터에 다시 합류하는 오래된 노드는 일반적으로 구성 정보의 변경에 대해 가능한한 빠르게 통지를 받는데, 왜냐하면 다른 어떤 노드에게 핑을 보내자마자, 수신하는 노드는 보낸 노드가 오래된 정보를 가지고 있는 것을 알아차리고, UPDATE메시지를 보낼 것이기 때문이다.

Hash slots configuration propagation

레디스 클러스터의 중요한 부분은 어떤 클러스터 노드가 지정된 해시 슬롯의 집합을 서빙하고 있는지에 관한 정보를 전파하는데 사용되는 메커니즘이다. 이것은 새로운 클러스터를 시작하고, 리플리카가 장애난 마스터의 슬롯들을 서빙하도록 승격된 이후에 구성 정보를 업그레이드 하는 기능 모두에서 중요하다.

동일한 메커니즘은 일정 시간동안 파티션된 노드가 합리적인 방식으로 클러스터에 다시 합류할 수 있게 한다.

해시 슬롯의 구성 정보가 전파되는 2가지 방법이 있다.

1. 하트비트 메시지. 핑/퐁 패킷을 전송하는 노드는 항상 자신이 제공하는 해시 슬롯의 집합에 대한 정보(리플리카라면, 자신의 마스터의)를 추가한다.
2. UPDATE 메시지. 모든 하트비트 패킷 내에는 보내는 노드의 configEpoch와 제공하는 해시 슬롯의 집합에 관한 정보가 있고, 만약 하트비트 패킷을 수신하는 노드가 보내는 노드의 정보가 오래된 것을 알게 되면, 새로운 정보와 함께 패킷을 보내고, 오래된 노드가 정보를 업데이트 할 수 있도록 한다.

하트비트나 UPDATE 메시지의 수신자는 해시 슬롯과 노드를 맵핑하는 자신의 테이블을 업데이트하기 위해서 어떤 간단한 룰을 사용한다. 새로운 레디스 클러스터 노드가 만들어지면, 로컬의 해시 슬롯 테이블은 단순히 NULL 엔트리로 초기화되고, 그래서 각 해시 슬롯은 어떤 노드와도 바인딩되거나 연결되지 않는다. 이것은 다음과 유사하다.

0 -> NULL
1 -> NULL
2 -> NULL
...
16383 -> NULL

노드가 해시 슬롯 테이블 업데이트 하기 위한 첫 번째 룰은 다음과 같다.

Rule 1: 만약 해시 슬롯이 (NULL로 설정되어) 할당되지 않은 상태이고, 그것에 대해 어떤 노드가 소유를 주장한다면, 해시 슬롯 테이블을 수정하고, 소유를 주장하는 슬롯들을 연결시킨다.

그래서 A 노드로부터 configEpoch 값 3으로, 해시 슬롯 1과 2를 처리한다고 주장하는 하트비트 메시지를 받으면, 테이블은 다음과 같이 수정된다.

0 -> NULL
1 -> A [3]
2 -> A [3]
...
16383 -> NULL

새로운 클러스터가 생성되면, 시스템 관리자는 슬롯들을 각각의 해당하는 마스터 노드에만 수동으로(CLUSTER ADDSLOTS 커맨드를 이용하고, redis-cli 커맨드 라인 툴 또는 다른 방법으로) 할당할 필요가 있고, 이러한 정보는 클러스터 전체에 빠르게 전파된다.

그러나 이 룰은 충분하지 않다. 해시 슬롯 맵핑은 2가지 이벤트 동안에 바뀔 수 있다.

1. 리플리카는 페일오버 동안에 자신의 마스터를 대체한다.
2. 슬롯은 한 노드에서 다른 한 노드로 재분배된다.

이제 페일오버에 초점을 맞춰보자. 리플리카가 자신의 마스터를 페일오버하면, 마스터의 값보다 더 큰 것이 보장되는 새로운 configEpoch를 획득한다(그리고 일반적으로 이전에 생성된 다른 어떤 configEpoch보다 더 크다). 예를 들어, A노드의 리플리카인 B노드는 configEpoch 4를 가지고 A노드를 페일오버 할 수 있다. 하트비트 패킷을 보내기 시작하고 (처음에는 클러스터 전체에 대량으로), 다음의 2번째 룰 때문에 수신자는 자신의 해시 슬롯 테이블을 업데이트할 것이다.

Rule 2: 만약 해시 슬롯이 이미 할당되어 있고, 알려진 노드가 현재 슬롯과 연결된 마스터의 configEpoch보다 더 큰 configEpoch를 이용해서 알리는 경우, 해시 슬롯은 새로운 노드로 다시 바인딩된다.

그래서 B노드로부터 configEpoch 4를 가지고 해시 슬롯 1과 2를 담당한다고 주장하는 메시지를 수신한 이후에, 수신하는 노드들은 다음과 같은 방법으로 테이블을 업데이트할 것이다.

0 -> NULL
1 -> B [4]
2 -> B [4]
...
16383 -> NULL

필연성(Liveness property): 두 번째 룰 때문에, 결국 클러스터 내의 모든 노드는 어떤 한 슬롯의 주인은 노드들 사이에서 가장 큰 configEpoch를 알려오는 노드라는 것에 동의할 것이다.

안전성(safety properties): 프로토콜이 절대로 받아들일 수 없는 상태로 들어가지 않음을 의미하며, 프로토콜이 더 이상 진전되지 않는 상태, 즉 어떠한 전송도 가능하지 않는 상태인 deadlock 이 없고, 프로토콜이 비생산적인 주기, 즉 같은 경로를 계속 반 복하는 경로를 가지고 같은 메시지의 교환이 유한의 개수만큼 또는 무한으로 행하여지 는 상태에 들어가지 않는 livelock이 없음을 의미한다.

필연성(liveness properties): 프로토콜이 궁극적으로 만족할 만한 상태로 들어감을 의미한다. 즉 각각의 도달할 수 있는 상태에서 어떤 다른 상태로 도달 가능하는 것을 의 미하며, 유한의 시간 내에 요구되는 서비스의 완료를 나타내며 종결하는 프로토콜인 경우 프로토콜이 항상 만족할 만한 최종상태에 도달함을 의미하며 주기적인 프로토콜 에 관련되며 프로토콜은 항상 초기상태에 도달하는 것을 의미한다.

https://yunkt.hatenablog.com/entry/2019/01/15/093830

레디스 클러스터에서 이러한 메커니즘을 last failover wins라고 부른다.

동일한 일은 리샤딩중에 발생할 수 있다. 해시 슬롯을 가져오는 노드는 해당 작업이 완료되면, 변경된 사항이 클러스터로 전파되는 것을 보장하기 위해서 configEpoch를 증분시킨다.

UPDATE messages, a closer look

이전 섹션을 염두해두면, UPDATE메시지가 동작하는 방법을 더 쉽게 알 수 있다. A노드는 일정 시간이후 클러스터에 다시 합류할 수도 있다. 그러면 A노드는 configEpoch 3으로 해시 슬롯 1과 2를 가지고 있다고 주장하는 하트비트 패킷을 보낼 것이다. 이 업데이트된 정보의 모든 수신자는 대신 동일한 해시 슬롯들이 더 큰 configEpoch를 가지는 B노드와 연결이 되어 있다는 것을 알 수 있다. 이 때문에 수신자들은 그 슬롯들에 대한 새로운 구성 정보와 함께 UPDATE 메시지를 A노드로 보낼 것이다. A노드는 위의 rule 2 때문에 자신의 구성 정보를 업데이트할 것이다.

How nodes rejoin the cluster

노드가 클러스터에 다시 합류할 때에도 동일한 기본 메커니즘이 사용된다. 위의 예를 이이서, A노드는 해시 슬롯 1과 2는 지금 B가 제공하고 있다는 것을 알아차릴 것이다. 이 2개가 A노드가 제공했었던 유일한 해시 슬롯이라고 가정하면, A가 제공하는 해시 슬롯의 수는 0이 된다! 그래서 A노드는 새로운 마스터의 리플리카로 재구성된다.

실제 규칙은 이것보다 조금 더 복잡하다. 일반적으로 A노드는 많은 시간이 지난 이후에 클러스터에 다시 합류할 수 있고, 그동안 원래 A에서 제공되었던 해시 슬롯들은 다른 여러 노드들에서 제공되고 있을 수도 있다. 예를 들어 해시 슬롯 1은 B, 해시 슬롯 2는 C에 의해서 제공될 수 있다.

그래서 실제로 레디스 클러스터 노드의 롤 변경 규칙은 어떤 마스터 노드가 자신의 마지막 해시 슬롯을 가져간 노드를 복제하고 리플리카가 되는 것으로 구성을 변경하는 것이다.

재구성하는 동안, 결국 제공되는 해시 슬롯의 수는 0으로 떨어지며, 이에 따라 노드가 재구성된다. 기본적으로 이것은 이전 마스터가 페일오버 이후 대체된 리플리카의 리플리카가 될 것이라는 것을 의미한다. 하지만 일반적인 형태에서는 규칙은 가능한 모든 케이스를 다룬다.

리플리카들은 정확히 동일하게 동작하는데, 이전 마스터의 마지막 해시 슬롯을 가져간 노드를 복제하도록 재구성된다.

Replica migration

레디스 클러스터는 시스템의 가용성을 향상 시키기 위해서 리플리카 마이그레이션(replica migration)이라고 부르는 개념을 구현한다. 이 이이디어는 마스터-리플리카 셋업의 클러스터내에서 마스터와 리플리카 사이의 맵핑이 고정된다면, 단일 노드의 장애가 여러 차례 발생할 때, 가용성은 시간이 지남에 따라 제한이 될 수 있다는 것을 의미한다.

예를 들어, 모든 마스터들이 각각 하나의 리플리카를 가지는 클러스터 내에서, 마스터나 리플리카 둘 중 하나에서만 장애가 나는 한은 계속해서 동작할 수 있지만, 동시에 둘다 실패한다면 동작할 수 없을 것이다. 하지만 시간이 지남에 따라서 누적될 수 있는, 하드웨어나 소프트웨어에 의해 발생하는 단일 노드의 개별적인 장애와 같은 실패의 케이스가 있다. 예를 들면 다음과 같다.

• 마스터 A는 단일 리플리카 A1을 가진다.
• 마스터 A가 실패한다. A1은 새로운 마스터로 승격된다.
• 3시간 이후, A1은 (A의 장애와 관련이 없는) 개별적인 방식으로 실패한다. A가 여전히 다운된 상태이므로, 승격이 가능한 다른 리플리카는 없다.

마스터와 리플리카 사이의 맵핑이 고정되어 있을 때, 위와 같은 시나리오에 대해서 클러스터를 더 잘 견디게 만들기 위한 유일한 방법은 모든 마스터에 리플리카를 더 추가하는 것이지만, 이것은 더 많은 레디스 인스턴스와 메모리 등으로 인해서 비용이 많이 든다.

대안으로는 클러스터를 비대칭으로 만들고, 클러스터 레이아웃이 시간에 따라 자동으로 변경되도록 하는 것이다. 예를 들어, 클러스터는 A, B, C 3개의 마스터 노드를 가지고 있다. A와 B는 각각 A1과 B1의 단일 리플리카만 가지고 있다. 하지만 마스터 C는 이와 다르게 C1과 C2, 2개의 리플리카를 가지고 있다.

리플리카 마이그레이션은 더 이상 보호되지 않는 마스터로 마이그레이션(migrate) 하기 위해 리플리카를 자동으로 재구성 프로세스이다. 리플리카 마이그레이션에서는 위에서 언급한 시나리오가 다음과 같이 바뀐다.

• 마스터 A가 실패한다. A1은 승격된다.
• C2는 A1의 리플리카로 마이그레이션되고, 그렇지 않으면 A1은 어떤 리플리카로도 지지해주지 않는다.
• 3시간 후에 A1도 실패한다.
• C2는 A1을 대체하기 위해서 마스터로 승격된다.
• 클러스터는 계속해서 동작할 수 있다.

Replica migration algorithm

마이그레이션 알고리즘은 어떠 형태의 합의도 사용하지 않는데, 레디스 클러스터에서 리플리카 레이아웃은 configEpoch와 일치하거나 또는 버전 관리가 필요한 클러스터 구성의 일부분이 아니기 때문이다. 대신 어떤 마스터가 보호되지 않을 때, 리플리카들이 대량으로 마이그레이션되는 것을 막기 위한 알고리즘을 사용한다. 이 알고리즘은 결국 (클러스터의 구성이 안정되면) 모든 마스터는 적어도 하나 이상의 리플리카에 의해서 보호될 것이라는 보장한다.

이것은 알고리즘이 동작하는 방법이다. 시작하기 전에, 이 문맥에서 좋은 리플리카(good replica)가 무엇인지 정의할 필요가 있다. 좋은 리플리카는 주어진 노드의 관점에서 FAIL 상태가 아닌 리플리카이다.

알고리즘의 실행은 좋은 리플리카(good replica)가 없는 단일 마스터가 적어도 하나 이상이 있다는 것을 발견한 모든 리플리카에서 촉발된다. 그러나 이러한 조건을 감지한 모든 리플리카에서 부분 집합(subset)만 움직여야 한다. 주어진 순간에 다른 노드의 실패에 대해 아주 약간 다른 관점을 가지는 다른 리플리카들을 제외하고, 실제로 이 부분 집합은 대부분 단일 리플리카이다.

움직이는 리플리카(action replica)는 가장 많은 수의 리플리카가 있는 마스터 내에서의 리플리카이고, FAIL 상태가 아니고, 가장 작은 노드 ID를 가진다.

따라서 예를 들어, 만약 리플리카를 각각 1개씩 가지는 10개의 마스터가 있고, 리플리카를 각각 5개씩 가지는 마스터가 있다고 할 때, 마이그레이션을 시도할 리플리카는 5개의 리플리카를 가지는 2개의 마스터 중에서 가장 작은 노드 ID를 가진 것이다. 합의가 사용되지 않는 것을 고려하면, 클러스터의 구성이 안정적이지 않을 때, 둘 이상의 리플리카가 스스로 실패 상태가 아닌 리플리카이고, 노드 ID가 가장 작다고 믿을 때, 경합 조건에 발생할 수 있다 (실제 이것이 발생할 가능성은 거의 없다). 만약, 이것이 발생하면, 그 결과로 복수의 리플리카가 동일한 마스터로 마이그레이션하지만, 이는 특별히 문제가 없다. 만약 양도하는 마스터가 리플리카가 없이 남게 되는 방식으로 경쟁이 발생하면, 클러스터가 다시 안정되자마자 알고리즘이 다시 실행되고, 리플리카는 원본 마스터로 다시 마이그레이션될 것이다.

결국 모든 마스터는 적어도 하나 이상의 리플리카에 의해서 보호된다. 하지만, 일반적인 동작은 단일 리플리카는 복수의 리플리카를 가진 마스터로부터 리플리카가 없는(orphaned) 마스터로 마이그레이션되는 것이다.

이 알고리즘은 사용자가 직접 설정할 수 있는 파라미터인 cluster-migration-barrier에 의해서 제어된다. 이것은 리플리카가 마이그레이션되기 전에, 마스터에 남아 있어야 하는 좋은 리플리카의 수를 의미한다. 예를 들어, 이 파라미터가 2로 설정되어 있다면, 리플리카는 오직 마스터가 동작하는 2개의 리플리카와 함께 남아있는 경우에만, 리플리카이 마이그레이션을 시도할 수 있다.

configEpoch conflicts resolution algorithm

페일오버동안에 리플리카의 승격을 통해서 새로운 configEpoch값이 만들어졌을 때, 이 값은 유니크한 것이 보장된다.

그러나 새로운 configEpoch값이 안전하지 않은 방식으로 만들어지는 2개의 고유한 이벤트가 있다. 이것은 로컬 노드의 currentEpoch 값을 증가시키고, 같은 시간에 충돌이 없기를 바랄 뿐이다. 두 이벤트는 시스템 관리자에 의해 만들어진다.

1. TAKOVER옵션이 있는 CLUSTER FAILOVER 커맨드는 접근 가능한 과반수 이상의 마스터 없이도 수동으로 리플리카 노드를 마스터로 승격시킬 수 있다. 이것은 예를 들어 멀티 데이터 센터의 구축에 유용하다.
2. 클러스터 리밸런싱을 위한 슬롯의 마이그레이션 또한 성능의 이유로 동의 없이, 로컬 노드 내에서 새로운 configEpoch를 만들어낸다.

특히, 수동 리샤딩동안에 해시 슬롯이 A노드에서 B노드로 마이그레이션될 때, 리샤딩 프로그램은 다른 노드의 동의를 요구하지 않고, (노드가 이미 가장 큰 configEpoch를 가진 노드가 아닌 경우에) 클러스터 내에서 찾은 가장 큰 에포크에 1을 더해서 B의 구성을 업그레이드할 것이다. 일반적으로 현실 세계의 리샤딩은 수백개의 해시 슬롯(특히 작은 클러스터의 경우)의 이동을 포함한다. 리샤딩동안, 이동된 해시 슬롯에 각각에 대해서 새로운 configEpoch를 만들어서 동의를 요구하는 것은 효율적이지 않다. 게다가 각각의 클러스터 노드에서는 새로운 구성 정보를 저장하기 위해 매번 fsync를 필요로 한다. 그 대신 수행되는 방식으로, 첫 번째 슬롯이 이동될 때에만 새로운 configEpoch가 필요하고, 이것은 프로덕션 환경에서 훨씬 더 효율적이다.

하지만 위의 2가지 케이스 때문에, (가능하지 않지만) 여러 노드가 동일한 configEpoch를 가지는 결과가 될 수도 있다. 시스템 관리자에 의해서 실행되는 리샤딩 작업과 (많은 불행이 더해져서) 동시에 발생한 페일오버가 충분히 빠르게 전파되지 않을 경우에는 currentEpoch 충돌이 발생할 수 있다.

게다가, 소프트웨어의 버그와 파일 시스템의 손상 역시 복수의 노드가 동일한 구성 에포크 값을 가지게 되는 것에 기여할 수도 있다.

마스터가 서로 다른 해시 슬롯을 제공할 때, 동일한 configEpoch는 문제가 없다. 마스터를 페일오버하는 리플리카가 유니크한 구성 에포크를 가지는 것이 더 중요하다.

즉, 수동 개입 또는 리샤딩은 클러스터의 구성을 서로 다른 방식으로 바꿀 수 있다. 레디스 클러스터의 주요 필연성(liveness property)은 슬롯의 구성은 항상 수렴되므로 모든 상황에서 모든 마스터 노드가 서로 다른 configEpoch를 가질 것을 요구한다.

이를 실시하기 위해서, 두 노드가 동일한 configEpoch로 완료되는 이벤트에서 충돌 해소 알고리즘(a conflict resolution algorithm)이 사용된다.

• IF 어떤 마스터 노드가 또 다른 마스터가 자신과 동일한 configEpoch를 알리고 있다는 것을 감지한다.
• AND IF 노드는 동일한 configEpoch를 주장하는 다른 노드에 비해서 사전적으로 더 작은 노드 ID를 가진다.
• THEN currentEpoch를 1 증가시키고, 그것을 새로운 configEpoch로 사용한다.

만약, 동일한 configEpoch를 가지는 어떤 노드의 집합이 있으면, 노드 ID가 가장 큰 것을 제외한 모든 노드는 앞으로 이동할 것이고, 무슨 일이 발생했는지에 관계없이 결국 모든 노드는 유니크한 configEpoch를 선택할 것이 보장된다.

이 메커니즘은 또한 redis-cli는 시작시에 CLUSTER SET-CONFIG-EPOCH를 사용하도록 하기 때문에, 새로운 클러스터가 생성된 이후에 모든 노드가 서로 다른 configEpoch로 시작하는 것을 보장한다(실제 이 메커니즘이 사용되지 않더라도). 그러나 어떤 이유로 노드가 잘못된 구성으로 남아있는 경우, 자동으로 해당 구성은 다른 구성 에포크로 업데이트될 것이다.

Node resets

노드는 다른 역할이나, 또는 다른 클러스터에서 재사용하기 위해서, 재시작없이 소프트웨어적으로 리셋할 수 있다. 이것은 일반적인 작업이나, 테스트, 클라우드 환경에서 주어진 노드를 다시 프로비저닝하고 다른 노드의 집합에 합류시켜, 클러스터를 확장하거나 새로 만드는 경우에 유용하다.

레디스 클러스터 노드는 CLUSTER RESET 커맨드를 이용해서 리셋된다. 이 커맨드는 2가지 형태로 제공된다.

• CLUSTER RESET SOFT
• CLUSTER RESET HARD

이 커맨드는 리셋시키려는 노드에 직접 전송해야 한다. 만약 리셋이 타입이 전달되지 않으면, 소프트 리셋이 수행된다.

다음은 리셋에 의해 수행되는 작업의 목록이다.

1. Soft and hard reset: 만약 노드가 리플리카라면, 마스터로 변경되고, 데이터셋은 모두 폐기된다. 노드가 마스터이고 커맨드를 가지고 있으면, 리셋 오퍼레이션은 중단된다.
2. Soft and hard reset: 모든 슬롯들이 해제되고, 메뉴얼 페일오버 상태도 리셋된다.
3. Soft and hard reset: 노드 테이블 내의 다른 모든 노드들은 삭제되고, 그래서 이 노드는 더 이상 다른 노드들을 알지 못한다.
4. Hard reset only: currentEpoch, configEpoch, lastVoteEpoch이 0으로 설정된다.
5. Hard reset only: 노드 ID는 새로운 랜덤 ID로 변경된다.

데이터 셋이 비어있지 않은 마스터 노드는 리셋될 수 없다(일반적으로 데이터를 다른 노드로 리샤딩하려고 하므로). 그러나, (적절하다고 생각되는) 특별한 조건 아래에서는
(예를 들어, 새로운 클러스터를 만들 목적으로 클러스터가 완전히 파괴된 경우 등), 리셋이 실행되기 전에 FLUSHALL이 반드시 실행되어야 한다.

Removing nodes from a cluster

(마스터 노드라면) 모든 데이터를 다른 노드로 리샤딩하고 노드를 셧다운 시킴으로써, 기존 클러스터에서 노드를 실질적으로 삭제하는 것은 가능하다. 그러나 다른 노드들은 여전히 이러한 노드의 ID와 주소를 기억할 것이고, 연결을 시도할 것이다.

이러한 이유로, 노드가 삭제될 때, 다른 모든 노드의 테이블에서도 해당 항목을 삭제할 것이다. 이것은 CLUSTER FORGET <node-id> 커맨드를 이용해서 수행된다.

이 커맨드는 2가지 일을 한다.

1. 노드 테이블에서 지정된 노드 ID를 삭제한다.
2. 동일한 노드 ID로 다시 추가되는 것을 막기 위해서 60초간 밴(ban)을 설정한다.

레디스 클러스터가 자동으로 노드를 발견하기 위해 가십을 사용하고, 그래서 A노드에서 X노드를 지우지만, B노드가 X노드에 관한 가십 메시지를 다시 A로 보내는 결과를 초래할 수 있기 때문에, 두 번째 오퍼레이션이 필요하다. 60초간의 밴(ban) 덕분에, 레디스 클러스터 관리 툴은 모든 노드에서 해당 노드를 삭제하기 위한 60초의 시간을 가지므로, 자동 검색(auto discovery)로 노드가 다시 추가되는 것을 방지할 수 있다.

자세한 내용은 CLUSTER FORGET 문서에서 확인할 수 있다.

Publish/Subscribe

레디스 클러스터에서 클라이언트는 모든 노드를 구독(subscribe)할 수 있고, 또한 다른 모든 노드로 발행(publish)할 수 있다. 클러스터는 발행된 메시지가 필요에 따라서 전달되도록 한다.

현재의 구현은 단순히 발행된 각각의 메시지를 모든 노드로 브로드캐스하지만, 어느 시점에서는 블룸 필터(Bloom filters)나 다른 알고리즘을 이용해서 최적화될 수 있다.