Lecture 7: Fault Tolerance: Raft (2)

Raft Sync

다음과 같은 상황을 가정해봅시다

	10	11	12	13	14
S1	3
S2	3	3	4
S3(leader)	3	3	5	6

다음과 같은 상황에서 S3가 13번째 index에 값을 넣는 상황을 가정해보자

Follower로 Log요청을 할때 leader는 prevLogIndex(12)와 prevLogTerm(5)을 같이 보내준다

서버 S1,S2와 prevLogIndex(12)와 prevLogTerm(5)가 맞지 않기 때문에 두 서버가 거절한다

leader는 nextIndex를 업데이트 한다 => nextIndex[S1]=12, nextIndex[S2]=12 (1만큼 rollback)

 

다시 log를 요청할 때는 prevLogIndex(11)와 prevLogTerm(3)로 전달하며, 리더는 12번째 값과 13번째 인덱스 값을 같이 보내준다.

S2는 업데이트에 성공하며 S1은 거절한다 => nextIndex[S1]=11, nextIndex[S2]=14

	10	11	12	13	14
S1	3
S2	3	3	5	6
S3(leader)	3	3	5	6

** 왜 S2는 기존의 12번째 인덱스를 버려도 괜찮을까?

 => 12번째 인덱스는 majority vote을 받지 못한 인덱스 일 것이다. 실행은 리더가 하기 때문에 12번째 인덱스 실행이 되지 못했을 것이다

 

이 후 S1을 업데이트한다

	10	11	12	13	14
S1	3	3	5	6
S2	3	3	5	6
S3(leader)	3	3	5	6

 

 

Why not longest log as leader?

S1	5	6	7
S2	5	8
S3	5	8

 

1. S1이 리더, 6번쨰 term일때 crash and reboot (crash 됐는데 로그가 왜 쌓였는지는 잘 모르겠음 )

2. 7번쨰 term일때 crash and reboot

3. S2가 리더가 되고 S1 crashed, S2&S3 alive

- 전체 서버를 재기동하고 리더 선출시 단순히 로그 길이가 길다고 S1을 고르면 term8이 무시된다

>> election restriction : VOTE yes 'only if' higher term in last entry or same last entry and has higher log length

 

Fast Backup

nextIndex업데이트 시 한번에 한칸씩 업데이트하면 너무 느리다. (follower가 오랫동안 네트워크 단절되어있다가 돌아온 경우)

follower는 아래 3가지 파라미터를 반환하여 fast backup 한다 (아래 파라미터 3개를 어떻게 찾는지는 설명해주지 않음)

- XTerm:  term in the conflicting entry (if any)

  Leader  : 4 4 4

  Follower: 4 6 6 6

  >> nextIndex = 리더의 엔트리 중 XTerm(4)의 가장 큰 entry

- XIndex: index of first entry with that term (if any)

  Leader  : 4 5 5

  Follower: 4 6 6 6

  >> nextIndex = Xindex

- XLen: log length

  Leader  : 4 6 6 6

  Follower: 4

  >> nextIndex = XLen

 

Persistent

- 디스크에 저장할 값들 (리부트 시 필요한 항목)

Log : application의 상태를 저장하는 것이기 때문에 Log를 통해서 application 복구 가능

currentTerm : 

votedFor : 같은 term에 각각 다른 candidate에게 vote 방지

- 디스크 저장은 bottleneck 발생가능함에 주의

 >> batch로 저장 / SSD 쓰기

 

SnapShot

일반적으로 log entries가 application보다 사이즈가 크다

raft는 application에게 snapshot을 저장할지 물어본다

시스템 복구시 index 5까지 snapshot을 저장했다면 index 5부터 application복구를 진행한다

snapshot 생성 시 follower에게 snapshot과 current log를 보낸

 

Linearlizable

operation은 linearlizable하다

if) each READ sees most recent WRITE in order

non linear operation

다음과 같은 operation은 linear화 할수없다