etcd와 Raft 구현 이해: Raft Log에 대한 심층 분석

소개

이 글에서는 Raft 합의 알고리즘의 로그를 시작으로 etcd의 Raft에서 Raft Log 모듈의 설계 및 구현을 소개하고 분석할 것입니다. 목표는 독자가 etcd의 Raft 구현을 더 잘 이해할 수 있도록 돕고 유사한 시나리오를 구현하기 위한 가능한 접근 방식을 제공하는 것입니다.

뗏목 통나무 개요

Raft 합의 알고리즘은 본질적으로 서버 클러스터 전체에서 동일한 방식으로 일련의 로그를 복제하는 것을 목표로 하는 복제된 상태 머신입니다. 이러한 로그를 통해 클러스터의 서버는 일관된 상태에 도달할 수 있습니다.

이 맥락에서 로그는 Raft Log를 참조합니다. 클러스터의 각 노드에는 일련의 로그 항목으로 구성된 자체 Raft 로그가 있습니다. 로그 항목에는 일반적으로 세 가지 필드가 포함됩니다.

• 색인: 로그 항목의 색인
• 용어: 로그 항목이 생성될 당시 리더의 용어
• 데이터: 로그 항목에 포함된 데이터로, 특정 명령 등이 될 수 있습니다.

Raft Log의 인덱스는 1부터 시작하며, 리더 노드만 Raft Log를 생성하고 Follower 노드에 복제할 수 있다는 점에 유의하는 것이 중요합니다.

로그 항목이 클러스터의 대부분의 노드(예: 2/3, 3/5, 4/7)에 지속적으로 저장되면 커밋된 것으로 간주됩니다.

로그 항목이 상태 머신에 적용되면 적용된 것으로 간주됩니다.

etcd의 래프트 구현 개요

etcd raft는 Go로 작성된 Raft 알고리즘 라이브러리로, etcd, Kubernetes, CockroachDB 등과 같은 시스템에서 널리 사용됩니다.

etcd raft의 주요 특징은 Raft 알고리즘의 핵심 부분만 구현한다는 것입니다. 사용자는 Raft 프로세스 자체와 관련된 네트워크 전송, 디스크 스토리지 및 기타 구성 요소를 구현해야 합니다(etcd는 기본 구현을 제공하지만).

etcd raft 라이브러리와의 상호작용은 다소 간단합니다. 유지해야 할 데이터와 다른 노드에 전송해야 하는 메시지를 알려줍니다. 귀하의 책임은 저장 및 네트워크 전송 프로세스를 처리하고 그에 따라 알리는 것입니다. 이러한 작업을 구현하는 방법에 대한 세부 사항에는 관심이 없습니다. 이는 단순히 귀하가 제출한 데이터를 처리하고 Raft 알고리즘을 기반으로 다음 단계를 알려줍니다.

etcd raft의 코드 구현에서 이 상호 작용 모델은 Go의 고유한 채널 기능과 완벽하게 결합되어 etcd raft 라이브러리를 정말 독특하게 만듭니다.

뗏목 로그를 구현하는 방법

로그 및 log_unstable

etcd raft에서 Raft Log의 주요 구현은 log.go 및 log_unstable.go 파일에 있으며 기본 구조는 raftLog 및 불안정합니다. 불안정한 구조도 raftLog 내의 필드입니다.

• raftLog는 Raft Log의 주요 로직을 담당합니다. 사용자에게 제공되는 Storage 인터페이스를 통해 노드의 로그 저장 상태에 접근할 수 있습니다.
• 불안정은 이름에서 알 수 있듯이 아직 지속되지 않은 로그 항목, 즉 커밋되지 않은 로그를 포함합니다.

etcd raft는 raftLog와 불안정함을 조화시켜 알고리즘 내에서 로그를 관리합니다.

raftLog 및 불안정 핵심분야

논의를 단순화하기 위해 이 문서에서는 etcd raft의 스냅샷 처리에 대해서는 다루지 않고 로그 항목 처리 논리에만 중점을 둡니다.

type raftLog struct {
    storage Storage
    unstable unstable
    committed uint64
    applying uint64
    applied uint64
}

raftLog 핵심 분야:

• 스토리지: 사용자가 구현한 스토리지 인터페이스로, 이미 지속된 로그 항목을 검색하는 데 사용됩니다.
• 불안정: 지속되지 않는 로그를 저장합니다. 예를 들어, 리더는 클라이언트로부터 요청을 받으면 해당 용어가 포함된 로그 항목을 생성하고 이를 불안정한 로그에 추가합니다.
• committed: Raft 문서에서는 commitIndex로 알려져 있으며, 마지막으로 커밋된 로그 항목의 인덱스를 나타냅니다.
• 적용 중: 현재 적용 중인 로그 항목의 가장 높은 인덱스입니다.
• applied: Raft 논문에서는 lastApplied라고 알려져 있으며 상태 머신에 적용된 로그 항목의 가장 높은 인덱스입니다.

type unstable struct {
    entries []pb.Entry
    offset uint64
    offsetInProgress uint64
}

불안정 핵심분야:

• 항목: 메모리에 슬라이스로 저장되는 지속되지 않는 로그 항목입니다.
• 오프셋: 항목의 로그 항목을 뗏목 로그에 매핑하는 데 사용됩니다. 여기서 항목[i] = 뗏목 로그[i 오프셋]입니다.
• offsetInProgress: 현재 지속되고 있는 항목을 나타냅니다. 진행 중인 항목은 항목[:offsetInProgress-offset]으로 표시됩니다.

raftLog의 핵심 필드는 간단하며 Raft 논문의 구현과 쉽게 관련될 수 있습니다. 그러나 불안정한 필드는 더 추상적으로 보일 수 있습니다. 다음 예는 이러한 개념을 명확히 하는 데 도움을 주기 위한 것입니다.

Raft Log에 이미 5개의 로그 항목이 유지되어 있다고 가정합니다. 이제 3개의 로그 항목이 불안정하게 저장되어 있으며 이 3개의 로그 항목은 현재 유지되고 있습니다. 상황은 아래와 같습니다.

offset=6은 불안정한 항목의 위치 0, 1, 2에 있는 로그 항목이 실제 Raft Log의 위치 6(0 6), 7(1 6) 및 8(2 6)에 해당함을 나타냅니다. offsetInProgress=9를 사용하면 위치 0, 1, 2에 있는 세 개의 로그 항목을 포함하는 불안정한.entries[:9-6]가 모두 지속되고 있음을 알 수 있습니다.

Unstable에서 offset과 offsetInProgress를 사용하는 이유는 불안정은 모든 Raft Log 항목을 저장하지 않기 때문입니다.

상호작용할 시기

Raft 로그 처리 로직에만 초점을 맞추고 있으므로 여기서 "상호작용 시기"는 etcd raft가 사용자가 유지해야 하는 로그 항목을 전달하는 시기를 나타냅니다.

사용자 측

etcd raft는 주로 노드 인터페이스의 메소드를 통해 사용자와 상호작용합니다. Ready 메소드는 사용자가 etcd raft로부터 데이터나 명령을 수신할 수 있는 채널을 반환합니다.

type raftLog struct {
    storage Storage
    unstable unstable
    committed uint64
    applying uint64
    applied uint64
}

이 채널에서 받은 Ready 구조체에는 처리가 필요한 로그 항목, 다른 노드로 보내야 하는 메시지, 노드의 현재 상태 등이 포함되어 있습니다.

Raft Log에 대한 논의에서는 Entries 및 CommittedEntries 필드에만 집중하면 됩니다.

• 항목: 지속되어야 하는 로그 항목입니다. 이러한 항목이 유지되면 스토리지 인터페이스를 사용하여 검색할 수 있습니다.
• CommittedEntries: 상태 시스템에 적용해야 하는 로그 항목입니다.

type unstable struct {
    entries []pb.Entry
    offset uint64
    offsetInProgress uint64
}

Ready를 통해 전달된 로그, 메시지 및 기타 데이터를 처리한 후 Node 인터페이스의 Advance 메소드를 호출하여 etcd raft에 명령을 완료했음을 알리고 다음 Ready를 수신하고 처리할 수 있습니다.

etcd raft는 노드 성능을 어느 정도 향상시킬 수 있는 AsyncStorageWrites 옵션을 제공합니다. 그러나 여기서는 이 옵션을 고려하지 않습니다.

etcd 뗏목 측면

사용자 측에서는 수신된 Ready 구조체의 데이터를 처리하는 데 중점을 둡니다. etcd raft 측면에서는 Ready 구조체를 사용자에게 전달할 시기와 이후에 수행할 작업을 결정하는 데 중점을 둡니다.

다음 다이어그램에서는 이 프로세스와 관련된 주요 메서드를 요약했습니다. 이 다이어그램은 일반적인 메서드 호출 순서를 보여줍니다(이는 대략적인 호출 순서만을 나타냅니다).

전체 프로세스가 루프임을 알 수 있습니다. 여기서는 이러한 메소드의 일반적인 기능을 간략하게 설명하고 이후의 쓰기 흐름 분석에서는 이러한 메소드가 raftLog 및 불안정의 핵심 필드에서 어떻게 작동하는지 살펴보겠습니다.

• HasReady: 이름에서 알 수 있듯이 사용자에게 전달해야 하는 Ready 구조체가 있는지 확인합니다. 예를 들어, 현재 지속되고 있지 않은 불안정 로그 항목이 지속되지 않는 경우 HasReady는 true를 반환합니다.
• readyWithoutAccept: HasReady가 true를 반환한 후 호출되는 이 메소드는 지속되어야 하는 로그 항목과 커밋된 것으로 표시된 로그 항목을 포함하여 사용자에게 반환될 Ready 구조체를 생성합니다.
• acceptReady: etcd raft가 ReadyWithoutAccept에 의해 생성된 Ready 구조체를 사용자에게 전달한 후에 호출됩니다. Ready에서 반환된 로그 항목을 지속 및 적용되는 과정으로 표시하고, 사용자가 Node.Advance를 호출할 때 호출되는 "콜백"을 생성하여 로그 항목을 지속 및 적용되는 것으로 표시합니다.
• Advance: 사용자가 Node.Advance를 호출한 후 acceptReady에서 생성된 “콜백”을 실행합니다.

커밋 및 적용을 정의하는 방법

여기서 고려해야 할 두 가지 중요한 사항이 있습니다.

1. 지속됨 ≠ 헌신됨

처음에 정의된 대로 로그 항목은 Raft 클러스터의 대다수 노드에 의해 유지된 경우에만 커밋된 것으로 간주됩니다. 따라서 etcd raft가 Ready를 통해 반환한 항목을 유지하더라도 해당 항목은 아직 커밋된 것으로 표시될 수 없습니다.

그러나 지속성 단계가 완료되었음을 etcd raft에 알리기 위해 Advance 메소드를 호출하면 etcd raft는 클러스터의 다른 노드 전체에서 지속성 상태를 평가하고 일부 로그 항목을 커밋된 것으로 표시합니다. 그런 다음 이러한 항목은 Ready 구조체의 CommittedEntries 필드를 통해 제공되므로 상태 머신에 적용할 수 있습니다.

따라서 etcd raft를 사용할 때 항목을 커밋으로 표시하는 시점은 내부적으로 관리되며 사용자는 지속성 전제 조건만 충족하면 됩니다.

내부적으로는 Raft 논문의 commitIndex에 해당하는 raftLog.committed를 업데이트하는 raftLog.commitTo 메소드를 호출하여 커밋을 수행합니다.

2. 약속 ≠ 적용

etcd raft 내에서 raftLog.commitTo 메소드가 호출된 후 raft.committed 인덱스까지의 로그 항목이 커밋된 것으로 간주됩니다. 그러나 lastApplied < index <= commitIndex가 아직 상태 시스템에 적용되지 않았습니다. etcd raft는 커밋되었지만 적용되지 않은 항목을 Ready의 CommittedEntries 필드에 반환하여 이를 상태 시스템에 적용할 수 있도록 합니다. Advance를 호출하면 etcd raft는 이러한 항목을 적용된 것으로 표시합니다.

항목을 적용됨으로 표시하는 시기도 etcd raft에서 내부적으로 처리됩니다. 사용자는 준비에서 커밋된 항목을 상태 시스템에 적용하기만 하면 됩니다.

또 다른 미묘한 점은 Raft에서는 리더만이 항목을 커밋할 수 있지만 모든 노드가 항목을 적용할 수 있다는 것입니다.

쓰기 요청 처리 흐름

여기에서는 쓰기 요청을 처리하는 etcd raft의 흐름을 분석하여 이전에 논의한 모든 개념을 연결하겠습니다.

초기 상태

보다 일반적인 시나리오를 논의하기 위해 이미 세 개의 로그 항목을 커밋하고 적용한 Raft Log부터 시작하겠습니다.

그림에서 녹색은 raftLog 필드와 Storage에 저장된 로그 항목을 나타내고, 빨간색은 불안정한 필드와 항목에 저장된 지속되지 않는 로그 항목을 나타냅니다.

3개의 로그 항목을 커밋하고 적용했으므로 커밋과 적용이 모두 3으로 설정됩니다. 적용 필드는 이전 애플리케이션에서 가장 높은 로그 항목의 인덱스를 보유하며 이 경우에도 3입니다.

이 시점에서는 요청이 시작되지 않았으므로 불안정한 항목이 비어 있습니다. Raft Log의 다음 로그 인덱스는 4이며 오프셋 4가 됩니다. 현재 지속되는 로그가 없으므로 offsetInProgress도 4로 설정됩니다.

요청 발행

이제 Raft Log에 두 개의 로그 항목을 추가하라는 요청을 시작합니다.

그림과 같이 추가된 로그 항목은 불안정한 항목에 저장됩니다. 이 단계에서는 핵심 필드에 기록된 인덱스 값이 변경되지 않습니다.

준비됨

HasReady 메소드를 기억하시나요? HasReady는 지속되지 않는 로그 항목이 있는지 확인하고, 있으면 true를 반환합니다.

지속되지 않는 로그 항목이 있는지 확인하는 논리는 불안정한 항목[offsetInProgress-offset:]의 길이가 0보다 큰지 여부에 따라 결정됩니다. 분명히 우리의 경우에는 다음과 같습니다.

type raftLog struct {
    storage Storage
    unstable unstable
    committed uint64
    applying uint64
    applied uint64
}

지속되지 않는 로그 항목이 두 개 있으므로 HasReady가 true를 반환함을 나타냅니다.

준비없음수락

readyWithoutAccept의 목적은 사용자에게 반환될 Ready 구조체를 생성하는 것입니다. 지속되지 않는 두 개의 로그 항목이 있으므로 ReadyWithoutAccept는 반환된 Ready의 항목 필드에 이 두 개의 로그 항목을 포함합니다.

수락준비

acceptReady는 Ready 구조체가 사용자에게 전달된 후에 호출됩니다.

acceptReady는 지속되고 있는 로그 항목의 인덱스를 6으로 업데이트합니다. 즉, [4, 6) 범위 내의 로그 항목은 이제 지속되는 것으로 표시됩니다.

전진

사용자가 항목을 준비 상태로 유지한 후 Node.Advance를 호출하여 etcd raft에 알립니다. 그러면 etcd raft는 acceptReady에서 생성된 "콜백"을 실행할 수 있습니다.

이 "콜백"은 불안정한 항목에서 이미 지속된 로그 항목을 지운 다음 오프셋을 Storage.LastIndex 1(6)로 설정합니다.

로그 항목 커밋

이 두 로그 항목이 이미 Raft 클러스터의 대다수 노드에 의해 유지되었다고 가정하므로 이 두 로그 항목을 커밋된 것으로 표시할 수 있습니다.

준비됨

루프를 계속 진행하면서 HasReady는 커밋되었지만 아직 적용되지 않은 로그 항목이 있는지 감지하여 true를 반환합니다.

준비없음수락

readyWithoutAccept는 커밋되었지만 상태 시스템에 적용되지 않은 로그 항목(4, 5)이 포함된 Ready를 반환합니다.

이 항목은 왼쪽 열기, 오른쪽 닫기 간격으로 낮음, 높음 := 적용 1, 커밋 1로 계산됩니다.

수락준비

acceptReady는 Ready에서 반환된 로그 항목 [4, 5]를 상태 머신에 적용되는 것으로 표시합니다.

전진

사용자가 Node.Advance를 호출한 후 etcd raft는 "콜백"을 실행하고 5에 적용된 업데이트를 실행하여 인덱스 5 이전의 로그 항목이 모두 상태 머신에 적용되었음을 나타냅니다.

최종 상태

이렇게 하면 쓰기 요청 처리 흐름이 완료됩니다. 최종 상태는 아래와 같으며 초기 상태와 비교해 볼 수 있습니다.

요약

Raft Log의 개요부터 시작하여 기본 개념을 이해한 후 etcd raft 구현을 처음 살펴보았습니다. 그런 다음 etcd raft 내에서 Raft Log의 핵심 모듈을 더 자세히 살펴보고 중요한 질문을 고려했습니다. 마지막으로 쓰기 요청 흐름에 대한 완전한 분석을 통해 모든 것을 하나로 묶었습니다.

이 접근 방식이 etcd raft 구현을 명확하게 이해하고 Raft Log에 대한 자신만의 통찰력을 개발하는 데 도움이 되기를 바랍니다.

이 글을 마치겠습니다. 잘못된 점이나 궁금한 점이 있으면 언제든지 개인 메시지나 댓글을 남겨주세요.

그런데, raft-foiver는 내가 구현한 etcd raft의 단순화된 버전으로, Raft의 모든 핵심 로직을 유지하고 Raft 논문의 프로세스에 따라 최적화되었습니다. 앞으로 이 라이브러리를 소개하는 글을 따로 올리겠습니다. 관심이 있으시면 Star, Fork, PR로 편하게 보내주세요!

참조

• https://github.com/B1NARY-GR0UP/raft
• https://github.com/etcd-io/raft

위 내용은 etcd와 Raft 구현 이해: Raft Log에 대한 심층 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!