Raft 합의 알고리즘

서버 한 대는 언젠가 죽는다. 그래서 중요한 데이터는 여러 대에 복제해 둔다. 그런데 여러 대가 동시에 값을 바꾸면 서로 내용이 어긋난다. 합의(consensus) 알고리즘은 여러 서버가 마치 한 대인 것처럼 똑같은 기록을 갖도록 맞춰 주는 규칙이다. Raft는 그중 가장 이해하기 쉽게 설계된 방식이다.

1. 리더 선출 — 직접 지켜보기

서버(노드) 5대가 원으로 놓여 있다. 각 노드에는 선거 타이머(파란 링)가 돌아간다. 리더의 하트비트를 받으면 타이머가 리셋되지만, 리더가 없어 타이머가 다 차면 그 노드는 후보(candidate)가 되어 투표를 요청한다. 과반수(3표)를 얻으면 리더가 된다.

2. 왜 타이머를 무작위로 돌릴까 — 스플릿 보트

모든 노드가 똑같은 시간에 타이머가 끝나면, 다 같이 후보가 되어 자기 자신에게 투표한다. 5명이 1표씩 나눠 가지면 아무도 과반수(3표)를 못 얻는다. 이를 표 분산(split vote)이라 한다. Raft는 각 노드의 선거 타이머를 150~300ms처럼 무작위 범위에서 뽑는다. 그러면 누군가 먼저 후보가 되어 남들이 타이머를 다 채우기 전에 표를 쓸어 담는다.

3. 로그 복제 — 결정을 같은 순서로 받아 적기

리더가 정해지면, 클라이언트의 명령(x=3, x=5 …)은 전부 리더에게 간다. 리더는 이를 자기 로그 끝에 붙이고 모든 follower에게 복사를 보낸다. 과반수가 로그에 적었다고 응답하면, 리더는 그 항목을 commit(확정) 하고 실제 값에 반영한다. 확정된 항목은 절대 바뀌거나 사라지지 않는다.

4. 세 가지 상태와 핵심 규칙

5. 의사코드 — follower가 투표를 결정하는 규칙

def on_request_vote(req):            # 후보가 보낸 표 요청
    if req.term < current_term:
        return Vote(current_term, granted=False)   # 낡은 후보 거절

    if req.term > current_term:          # 더 최신 term 발견
        current_term = req.term
        voted_for    = None              # 새 임기이므로 투표권 부활
        state        = FOLLOWER

    already_voted = voted_for not in (None, req.candidate_id)
    log_ok       = req.last_log_term >= my_last_log_term \
                   and req.last_log_index >= my_last_log_index

    if not already_voted and log_ok:
        voted_for = req.candidate_id
        reset_election_timer()          # 표를 줬으니 잠시 기다려 줌
        return Vote(current_term, granted=True)

    return Vote(current_term, granted=False)

log_ok 조건이 핵심이다. 자기 로그가 후보보다 더 최신이면 표를 주지 않는다. 덕분에 확정된 기록이 빠진 노드는 절대 리더가 될 수 없다.

6. 어디에 쓰이나