etcd - Raft Algorithm

Kubernetes에서 Cluster에 문제가 생겼을 경우 etcd를 백업해놓은 상태라면 원래 상태로 복구가 가능합니다.

반대로 etcd는 Kubernetes의 모든 상태 정보들을 담고 있기 때문에 etcd가 손상되었을 경우 Cluster를 활용할 수 없게 됩니다.

그렇기 때문에 etcd는 단일 환경에 구성하는 것이 아닌, 분산된 환경에 구성하는 것이 좋으며 분산된 환경에서 etcd를 운영할 때 분산된 etcd들이 정상적으로 동작하기 위한 방법을 마련해야 합니다.

etcd에서는 Raft Algorithm 알고리즘을 이용해 이를 해결했습니다.

Raft Algorithm은 voting과 log entry 복제라는 방식으로 동작합니다.

---

Replicated state machine과 Consensus Algorithm

분산된 환경에서 etcd가 동작할 경우, 여러 Server에서 CRUD가 발생하게됩니다.

etcd가 정상적으로 동작하기 위해서는 다른 Server들에서 이벤트가 발생하더라도 모든 Server의 etcd들이 동일한 데이터를 저장하고 있는것이 보장되어야 합니다.

이렇게 똑같은 데이터를 여러 서버에 계속해서 복사하는 방식을 Replicated state machine이라고 하며, Replicated state machine에 어떤 데이터를 복사할지를 결정하는 알고리즘을 Consensus Algorithm이라고 합니다.

Raft Algorithm은 Consensus Algorithm의 한 종류로 서로 다른 Server들이 모종의 방법으로 합의를 통해 상태를 공유하는 알고리즘입니다.

---

동작 방식

Replicated state machine의 핵심은 복제과정에서 발생할 수 있는 문제를 해결하기 위해 Consensus를 확보해야 한다는 것입니다.

Consensus를 확보하기 위해서는 몇가지 사항이 전제되어야 합니다.

1. 항상 올바른 결과를 리턴해야 함
2. 서버가 몇 대 다운되더라도 항상 응답해야 함
3. 네트워크 지연이 발생하더라도 로그의 일관성이 깨져서는 안됨
4. 모든 서버에 복제되지 않았더라도 조건을 만족하면 빠르게 요청에 응답해야 함

또한, Raft Algorithm의 동작 원리를 이해하기 위해서는 몇 가지 용어에 대한 이해가 필요합니다.

1. 쿼럼(Quorum)
   Quorum이란 정족수라는 의미로 etcd cluster가 의사 결정을 하기 위한 최소한의 서버 수를 의미합니다. etcd cluster는 분산된 etcd서버 들 중 Quorum의 숫자 만큼의 서버에 데이터의 복제가 일어나면 작업이 완료한 것으로 판단합니다.

2. 상태(State)
   State란 etcd cluster를 구성하는 Server들이 가지게 되는 일종의 역할입니다.
   모든 Server들은 Leader, Follower, Candidate라는 3개의 State중 하나가 됩니다.
   모든 Server들은 마지막으로 log가 저장된 위치(lastIndex) 값을 가지고 있습니다.
   이 때, Leader는 추가적으로 현재 etcd cluster의 Server들이 log를 저장할 다음 위치(nextIndex)값을 가지고 있습니다.
   etcd cluster의 변경 내역은 Leader를 통해서만 Follower에게 전달되어 반영됩니다.

3. 타이머(Timer)
   etcd의 Leader가 된 Server는 다른 모든 Server들에게 주기적으로 heartbeat를 전송해 Leader가 존재하고 있음을 알립니다.
   다른 Server들은 Leader가 존재하고 있을 때에는 Leader에게 다음에 log를 저장할 위치에 대한 nextIndex값을 받으며 동작합니다.
   만약, Leader가 존재하지 않게 되어 heartbeat가 전달되지 않을 경우 Server들은 새로운 Leader를 선출하기 위한 절차를 시작합니다.

---

1. 리더 선출(Leader election)

Raft Algorithm에서 etcd Cluster환경을 구성하는 Server들은 State를 가지게 됩니다.

State는 Leader, Follower, Candidate가 있습니다.

Leader는 etcd Cluster를 구성하는 Server들에게 주기적으로 heartbeat를 전송하여 Leader가 존재하고 있음을 알리며, Server들의 값은 Leader를 통해서만 변경됩니다.

Leader를 선출하는 방법은 아래와 같습니다.

1. Cluster 구성시 모든 Server들은 Follower상태, Term=0
2. 누구도 heartbeat를 보내지 않으면 Server 중 1대에서 election timeout 발생
3. election timeout이 발생한 Server는 State를 Candidate로 변경하고 Term값을 1증가시킨 뒤 다른 Server들에게 RequestVote RPC call을 보냄
4. Request Vote를 받은 서버는 자신이 가진 term정보와 log를 비교해서 candidate보다 자신의 것이 크다면 거절, 크지 않다면 OK 응답
5. Candidate는 자기 자신을 포함하여 다른 Server로 부터 받은 OK응답의 숫자가 Quorum과 같으면 Leader가 됨
6. Leader는 다른 서버에게 주기적으로 heartbeat를 보냄, 이 Append RPC call에는 Leader의 term과 log index정보가 들어있음
7. Leader가 아닌 서버는 Append RPC call을 받았을 때, 자신의 term보다 높은 값인지 확인 후 자신의 term값을 해당 값으로 업데이트

---

2. 로그 복제(Log replication)

etcd는 log replication을 통해 모든 etcd의 값을 동일하게 유지합니다.
동작 방식은 아래와 같습니다.

1. 각 서버는 자신이 가지고 있는 log의 lastIndex값을 가지고 있으며, Leader는 추가적으로 Follower들의 다음 log가 저장될 공간인 nextIndex값을 가지고 있음
2. 사용자로부터 log Append요청을 받은 Leader는 자신의 lastIndex다음 위치에 log를 기록하고 lastIndex값을 증가시킴
3. heartbeat 주기가 돌아오면 모든 Server에게 AppendEntry RPC call을 보내면서 Follower의 nextindex에 해당하는 log를 함께 보냄
4. Follower들은 log를 entry에 보관하고 잘 받았다는 응답을 Leader에 전송
5. Leader는 log를 잘 받았다고 응답한 숫자가 Quorum이 되면 Quorum 숫자만큼의 log replication이 일어났다고 판단하고 commit을 수행
6. 이때부터 etcd를 조회하면 commit된 값을 확인할 수 있음
7. Follower들은 Leader가 해당 log를 commit한 사실을 알게되면 각 서버의 entry에 보관중이던 log를 commit함

---

3. 리더 다운(Leader down)

etcd에서 기존에 Leader였던 Server에 문제가 생길 경우 다시 Leader를 선출합니다.

1. Leader가 다운되면 heartbeat이 전달되지 않으므로 Follower들 하나가 election timeout을 발생시키게되고 자신의 term값을 1 증가시키고 Candidate로 변경 후 RequestVote RPC call을 다른 Server들에게 전달
2. Follower들은 먼저 자신의 term값과 RequestVote를 통해 받은 Candidate의 term값을 비교

여기서 RequestVote RPC call을 전송한 Candidate의 term값과 log버전에 따라 해당 Candidate가 Leader가 될 수도, 되지 못할 수도 있습니다.

Leader가 될 수 있는 경우
3. Candidate의 term값이 자신보다 크고 log가 자신이 가진 log와 버전이 같거나 더 최신인 경우 OK 응답
4. OK 응답의 갯수가 Quorum과 같아지면 Leader로 선출

Leader가 될 수 없는 경우
3. Candidate의 값이 자신보다 작거나 log가 자신이 가진 것보다 오래된 버전이면 거절 응답
4. 거절 응답을 보낸 Server들 중 한대에서 election timeout발생하여 Candidate가 됨
5. Candidate가 된 Server는 RequestVote RPC call을 전송
6. OK 응답의 갯수가 Quorum과 같아지면 Leader로 선출

---