[k8s] etcd & Raft Algorithm (1)

etcd

쿠버네티스는 기반 스토리지(backing storage)로 etcd를 사용하고 있고, 모든 데이터가 etcd에 보관된다. 예를 들어, 쿠버네티스 클러스터에 노드가 몇 개 있고, 어떤 Pod가 어떤 노드에서 동작하고 있는지 등이 etcd에 기록된다.

 

etcd는 위와 이러한 정보를 key-value 형태로 저장한다. 만약 etcd가 다운되게 되면 쿠버네티스 클러스터는 제대로 동작하지 못하게 되기 때문에 높은 신뢰성을 제공해야 한다.

 

etcd는 Replicated State Machine(RSM)이다.

 

RSM은 서버들을 복사하고 복제된 서버와 클라이언트 간의 상호적용을 조율하는 것으로 장애 허용 서비스를 구현하는 일반적인 방법이다. RSM은 여러 노드에 동일한 상태 머신(State Machine)을 복제하여, 클라이언트 요청이 어떤 노드로 전달되든 동일한 결과를 얻게 한다. 이를 통해 시스템의 가용성과 내결함성을 높일 수 있다.

 

RSM은 command가 들어있는 log 단위로 데이터를 처리한다. 데이터의 write를 log append라고 부르며, Machine은 받은 log를 순서대로 처리한다. 하지만, 동일한 데이터를 여러 서버에 복제하기 때문에 발생하는 문제점 또한 존재한다.

 

안정적인 RSM을 구축하기 위해서는 데이터 복제 과정에서 발생할 수 있는 여러 가지 문제점을 해결하기 위해 컨센서스를 확보해야 한다. 컨센서스를 확보한다는 것은 RSM이 아래의 네 가지 속성을 만족한다는 것이다.

 

속성	설명
Safety	항상 올바른 결과를 리턴해야 합니다.
Available	서버가 몇 대 다운되더라도 항상 응답해야 합니다.
Independent from timing	네트워크 지연이 발생해도 로그의 일관성이 깨져서는 안됩니다.
Reactivity	모든 서버에 복제되지 않았더라도 조건을 만족하면 빠르게 요청에 응답해야 합니다.

 

쿠버네티스의 Control Plane Component인 etcd는 컨센서스를 확보하기 위해 Raft 알고리즘을 사용했다.

Raft Algorithm

Raft 알고리즘은 합의 알고리즘의 일종으로 여러 노드가 네트워크 지연, 노드 실패 등의 상황에서도 일관된 결정을 내릴 수 있도록 한다.

 

Raft 알고리즘을 설명하기 전에 기본적인 용어 3가지를 알아야 한다.

Quorum

Quorum이란 정족수, 라는 의미를 가지며 의사결정에 필요한 최소한의 서버 수를 의미한다. 예를 들어 RSM을 구성하는 서버의 숫자가 3대인 경우 Quorum 값은 2가 된다. etcd는 write 요청을 받았을 때, Quorum 숫자만큼의 서버에 데이터 복제가 발생하면 작업이 완료된 것으로 간주하고 다음 작업을 받아들일 수 있는 상태가 된다.

State

Etcd를 구성하는 서버는 State를 가지며 이는 Leader, Follower, Candidate 중 하나가 된다.

Timer

etcd의 Leader 서버는 다른 모든 서버에게 Heartbeat를 주기적으로 전송하여, Leader가 존재함을 알린다. 만약 Leader가 아닌 서버들이 일정 시간(Election Timeout) 동안 Heartbeat를 받지 못하게 되면 Leader가 없어졌다고 간주하고 다음 리더를 선출한다.

Leader Election

3개의 서버를 이용하여 etcd 클러스터를 구성했을 때, 각 서버는 Follower 상태이며 Term 값을 0으로 설정하고 동작을 시작한다.

 

최초로 초기화된 etcd 클러스터는 Leader가 존재하지 않기 때문에 누구도 Heartbeat를 보내지 않는다. 따라서 etcd 서버 중 한대에서 Election Timeout이 발생하게 되고, Timeout이 발생한 etcd 서버가 자신의 상태를 Candidate로 변경하고 Term을 1 증가 시킨다.

 

Candidate가 된 etcd 서버는 클러스터 내에 존재하는 다른 서버에 RequestVote RPC call을 보낸다. RequestVote RPC call을 받은 각 서버는 자신이 가진 Term 정보와 log를 비교하여 Candidate보다 자신의 것이 크다면 거절한다.

 

하지만 초기에는 Candidate의 Term 정보가 더 크기 때문에 해당 요청을 수락한다. Candidate 서버는 자기 자신을 포함하여 다른 서버로부터 받은 수락 응답이 Quorum과 동일하면 Leader로 선출된다.

 

Leader가 된 서버는 클러스터의 다른 서버에게 Heartbeat를 보내는데, 이 Append RPC call에는 Leader의 Term과 보유한 log index 정보가 들어있다.

 

Leader가 아닌 서버는 Append RPC call을 받았을 때 자신의 Term보다 높은 Term을 가진 서버의 call 인지 확인하고, 자신의 Term을 받은 Term 값으로 업데이트한다.

Log Replication

각 서버는 자신이 가지고 있는 log의 lastIndex 값을 가지고 있으며 Leader는 여기에 추가로 Follower가 새로운 log를 써야 할 nextIndex를 알고 있다. 사용자로부터 log append 요청을 받은 Leader는 자신의 lastIndex 다음 위치에 로그를 기록하고 lastIndex 값을 증가시킨다.

 

그리고 다음 Heartbeat Interval이 도래하면 모든 서버에게 AppendEntry RPC call을 보내면서, Follower의 nextIndex에 해당하는 log를 함께 보낸다.

 

첫 번째 Follower(이하 F1)는 자신의 Entry(메모리)에 Leader로부터 받은 log를 기록했고 두 번째 Follower(이하 F2)는 아직 기록하지 못했다고 가정해보자.

 

F1은 log를 잘 받았다는 응답을 Leader에게 보내주게 되고, Leader는 F1의 nextIndex를 업데이트한다. F2가 아직 응답을 주지 않았지만, 자기 자신을 포함해서 Quorum 숫자만큼의 Log Replication이 일어났기 때문에 commit을 수행한다.

 

commit이란, log entry에 먼저 기록된 데이터를 서버마다 가지고 있는 db(파일시스템)에 write 하는 것을 의미한다. 만약 commit된 데이터가 x = 1이라는 데이터일 경우, 사용자가 etcd 클러스터에서 x를 read하면 1이 return 된다.

 

Follower들은 Leader가 특정 로그를 commit한 사실을 알게 되면, 각 서버의 Entry에 보관 중이던 log를 commit 합니다.

Leader Down

사용자의 write 요청에 따라 Quorum 숫자만큼 log의 복제와 commit이 완료된 이후, Leader가 다운된다면 etcd는 어떻게 동작할지 알아보자. Log Replication에서 다룬 상황 이후에 Leader 서버의 etcd 프로세스가 알 수 없는 이유로 다운되었다고 가정한다.

 

Follower들은 Leader로부터 Election Timeout 동안 Heartbeat를 받지 못하고, F2가 Timeout 됐다고 가정해보자. F2는 자신을 Candidate로 바꾸고 Term을 증가시킨 다음 RequestVote RPC call을 모든 서버에게 보낸다.

 

RequestVote RPC call에는 요청을 받은 Candidate가 Leader가 되어도 문제가 없는지 Follower가 판단할 수 있도록 Term과 index 정보가 들어있다. RequestVote를 받은 F1은 F2가 보내온 RequestVote RPC 데이터를 살펴본다.

 

일단 Term의 숫자는 하나 높긴 한데, F1이 가진 log가 F2보다 더 최신이기 때문에 F1는 F2의 RequestVote에 거절 응답을 보내고, F2는 leader로 선출되지 못한다.

 

이후 F1에서 다시 Election Timeout이 발생하면 F1은 F2와 Term이 같으며 더 최신의 log를 보유하고 있으므로 F2는 F1의 RequestVote RPC call에 OK 응답을 하고 F1은 새로운 Leader로 선출된다. F1이 Leader가 된 이후 보낸 첫 번째 Heartbeat(Append RPC)를 수신한 F2는 자신의 상태를 Follower로 변경한다

 

F1이 새로운 Leader가 된 상태에서 write 요청을 받게 되더라도 쿼럼 숫자만큼의 etcd 서버가 Running 중이므로 etcd 클러스터는 정상 동작한다.

Leader Back

F1이 새로운 Leader가 된 상태에서 구 Leader가 복구되면, F1에게 Heartbeat를 보내거나 F1으로부터 Heartbeat를 받을 텐데 lastIndex 값이 더 작고 Term도 낮으므로 자기 자신을 follower로 변경하고 Term 숫자를 높은 쪽에 맞춘다.

 

여기까지가 대략적인 etcd에 대한 기본 개념과 etcd에 적용된 Raft 알고리즘에 대한 설명이다. 다음 포스트에서는 etcd 클러스터가 동작 중인 가운데 etcd 서버를 추가/삭제 발생할 때 어떤 식으로 Raft 알고리즘이 적용되는지 알아보자.