Crowdly

Image failed to load: RulesForServers

Im Raft-Paper die Regeln für die einzelnen Rollen der Server folgendermaßen definiert worden:

Im Java Code der Raft-grpc Implementierung ist folgende Funktion vorhanden:

    private void startElection() {
        if (suspended || state == NodeState.LEADER) {
            return;
        }
        // Pre-vote phase: Check if election would be successful before disrupting cluster
        log.info("Starting pre-vote phase for node {}", config.getNodeId());
        boolean preVoteSuccessful = performPreVote();
        if (!preVoteSuccessful) {
            log.info("Pre-vote failed for node {}, not starting actual election", config.getNodeId());
            startElectionTimer();
            return;
        }
        log.info("Pre-vote successful! Starting actual election...");
        logEvent(RaftEvent.EventType.STATE_CHANGE,
            "FOLLOWER → CANDIDATE");
        state = NodeState.CANDIDATE;
        currentTerm.incrementAndGet();
        logEvent(RaftEvent.EventType.TERM_INCREASED,
            "Term increased to " + currentTerm.get());
        votedFor = config.getNodeId();
        currentLeader = null;
        // Persist state change (CRITICAL for Raft safety - must persist before sending RequestVote RPCs)
        persistenceService.saveState(config.getNodeId(), currentTerm.get(), votedFor);
        int votesReceived = 1;
        int votesNeeded = (stubs.size() + 2) / 2; 
        log.info("Node {} starting election for term {}", config.getNodeId(), currentTerm.get());
        logEvent(RaftEvent.EventType.ELECTION_START,
            "Starting election, need " + votesNeeded + " votes");
        int lastLogIndex = getLastLogIndex();
        int lastLogTerm = getLogTermAt(lastLogIndex);
        VoteRequest voteRequest = VoteRequest.newBuilder()
            .setTerm(currentTerm.get())
            .setCandidateId(config.getNodeId())
            .setLastLogIndex(lastLogIndex)
            .setLastLogTerm(lastLogTerm)
            .build();
        for (Map.Entry<String, RaftServiceGrpc.RaftServiceBlockingStub> entry : stubs.entrySet()) {
            try {
                VoteResponse response = entry.getValue().requestVote(voteRequest);
                if (response.getTerm() > currentTerm.get()) {
                    becomeFollower(response.getTerm());
                    return;
                }
                if (response.getVoteGranted()) {
                    votesReceived++;
                    log.info("Received vote from {} ({}/{})", entry.getKey(), votesReceived, votesNeeded);
                    logEvent(RaftEvent.EventType.VOTE_GRANTED,
                        "Vote granted from " + entry.getKey() + " (" + votesReceived + "/" + votesNeeded + ")");
                } else {
                    logEvent(RaftEvent.EventType.VOTE_DENIED,
                        "Vote denied from " + entry.getKey());
                }
            } catch (Exception e) {
                log.warn("Failed to request vote from {}: {}", entry.getKey(), e.getMessage());
            }
        }
        if (votesReceived >= votesNeeded && state == NodeState.CANDIDATE) {
            logEvent(RaftEvent.EventType.ELECTION_WON,
                "Won election with " + votesReceived + " votes");
            becomeLeader();
        } else {
            log.info("Election failed. Votes received: {}, needed: {}", votesReceived, votesNeeded);
            logEvent(RaftEvent.EventType.ELECTION_LOST,
                "Lost election: " + votesReceived + "/" + votesNeeded + " votes");
            startElectionTimer();
        }
    }

Welche Aussagen treffen dabei zu?

Bei größerem Term wird der Status korrekt geändert.

Bei der korrekten Anzahl an Votes wird der Candidate zum Leader.

Der Reset des ElectionTimers findet nicht statt.

Die wichtigen Schritte (Inkrement von Term, Selbstwahl, Reset von ElectionTimer), bevor die RequestVotes ausgesendet werden, sind korrekt implementiert.

Image failed to load: RequestVote

Im Raft-Paper ist die RPC Funktion RequestVote folgendermaßen definiert worden:

Im Java Code der Raft-grpc Implementierung ist die Funktion so implementiert worden:

public VoteResponse handleVoteRequest(VoteRequest request) {
        log.info("Received vote request from {} for term {}", request.getCandidateId(), request.getTerm());
        // Deny votes when suspended
        if (suspended) {
            log.info("Denying vote request - node is suspended");
            return VoteResponse.newBuilder()
                .setTerm(currentTerm.get())
                .setVoteGranted(false)
                .build();
        }
        if (request.getTerm() > currentTerm.get()) {
            becomeFollower(request.getTerm());
        }
        boolean voteGranted = false;
        if (request.getTerm() < currentTerm.get()) {
            voteGranted = false;
            logEvent(RaftEvent.EventType.VOTE_DENIED, 
                "Denied vote to " + request.getCandidateId() + " (stale term " + request.getTerm() + ")");
        } else if (votedFor == null || votedFor.equals(request.getCandidateId())) {
            int lastLogIndex = getLastLogIndex();
            int lastLogTerm = getLogTermAt(lastLogIndex);
            boolean logUpToDate = request.getLastLogTerm() > lastLogTerm ||
                (request.getLastLogTerm() == lastLogTerm && request.getLastLogIndex() >= lastLogIndex);
            if (logUpToDate) {
                votedFor = request.getCandidateId();
                voteGranted = true;
                lastHeartbeat = System.currentTimeMillis();
                // Persist vote (CRITICAL for Raft safety - must persist before responding)
                persistenceService.saveState(config.getNodeId(), currentTerm.get(), votedFor);
                startElectionTimer();
                log.info("Voted for {}", request.getCandidateId());
                logEvent(RaftEvent.EventType.VOTE_GRANTED, 
                    "Granted vote to " + request.getCandidateId() + " for term " + request.getTerm());
            } else {
                logEvent(RaftEvent.EventType.VOTE_DENIED, 
                    "Denied vote to " + request.getCandidateId() + " (log not up-to-date)");
            }
        } else {
            logEvent(RaftEvent.EventType.VOTE_DENIED, 
                "Denied vote to " + request.getCandidateId() + " (already voted for " + votedFor + ")");
        }
        return VoteResponse.newBuilder()
            .setTerm(currentTerm.get())
            .setVoteGranted(voteGranted)
            .build();
    }
    private void startElectionTimer() {
        if (electionTask != null) {
            electionTask.cancel(false);
        }
        int timeout = ThreadLocalRandom.current().nextInt(ELECTION_TIMEOUT_MIN, ELECTION_TIMEOUT_MAX);
        electionTask = scheduler.schedule(this::startElection, timeout, TimeUnit.MILLISECONDS);
        log.debug("Election timer started: {}ms", timeout);
    }

Mit den folgenden gRPC Messages:

message VoteRequest {
  int32 term = 1;
  string candidateId = 2;
  int32 lastLogIndex = 3;
  int32 lastLogTerm = 4;
}
message VoteResponse {
  int32 term = 1;
  bool voteGranted = 2;
}

Welche Aussagen treffen dabei zu?

Wenn der RaftNode noch keine Abstimmung getätigt hat und der replicatedLog des Candidate aktuell oder größer ist, wird zugestimmt.

Die Überprüfung des Terms ist korrekt und es werden keine kleineren Terms akzeptiert.

Der electionTimer ist nicht notwendig und wird auch nicht im Raft-Paper beschrieben.

Wenn der electionTimer abgelaufen ist, wechselt der Node selbst in den Candidate Zustand.

Die Überprüfung des Terms ist noch nicht richtig implementiert.

VoteRequest und VoteResponse enthalten nicht die geforderten Argumente.

Image failed to load: AppendEntries

Im Raft-Paper ist die RPC Funktion AppendEntries folgendermaßen definiert worden:

Im Java Code der Raft-grpc Implementierung ist die Funktion so implementiert worden:

    public AppendEntriesResponse handleAppendEntries(AppendEntriesRequest request) {
        // Reject AppendEntries when suspended
        if (suspended) {
            log.debug("Rejecting AppendEntries - node is suspended");
            return AppendEntriesResponse.newBuilder()
                .setTerm(currentTerm.get())
                .setSuccess(false)
                .build();
        }
        lastHeartbeat = System.currentTimeMillis();
        if (request.getTerm() > currentTerm.get()) {
            becomeFollower(request.getTerm());
        }
        if (request.getTerm() < currentTerm.get()) {
            return AppendEntriesResponse.newBuilder()
                .setTerm(currentTerm.get())
                .setSuccess(false)
                .build();
        }
        if (state != NodeState.FOLLOWER) {
            becomeFollower(request.getTerm());
        }
        currentLeader = request.getLeaderId();
        startElectionTimer();
        if (request.getEntriesCount() == 0) {
            logEvent(RaftEvent.EventType.HEARTBEAT_RECEIVED, 
                "Heartbeat from leader " + request.getLeaderId());
        }
        // Check prevLogIndex/prevLogTerm consistency (logical indices)
        int prevLogIndex = request.getPrevLogIndex();
        if (prevLogIndex >= 0) {
            // Check if we have the entry at prevLogIndex
            int prevLogTerm = getLogTermAt(prevLogIndex);
            if (prevLogTerm == 0 || prevLogTerm != request.getPrevLogTerm()) {
                log.debug("Log consistency check failed at index {}: expected term {}, got {}", 
                         prevLogIndex, request.getPrevLogTerm(), prevLogTerm);
                return AppendEntriesResponse.newBuilder()
                    .setTerm(currentTerm.get())
                    .setSuccess(false)
                    .build();
            }
        }
        // Process new entries (logical indices)
        int newEntryLogicalIndex = prevLogIndex + 1;
        int entriesAdded = 0;
        List<LogEntry> entriesToPersist = new ArrayList<>();
        for (GrpcLogEntry entry : request.getEntriesList()) {
            int physicalIndex = logicalToPhysical(newEntryLogicalIndex);
            // Check for conflicts
            if (physicalIndex >= 0 && physicalIndex < raftLog.size()) {
                if (raftLog.get(physicalIndex).getTerm() != entry.getTerm()) {
                    // Conflict detected - delete conflicting entries
                    synchronized (raftLog) {
                        raftLog.subList(physicalIndex, raftLog.size()).clear();
                        // Persist log deletion (CRITICAL for consistency)
                        persistenceService.deleteLogEntriesFrom(config.getNodeId(), newEntryLogicalIndex);
                    }
                }
            }
            // Append if we don't have this entry
            physicalIndex = logicalToPhysical(newEntryLogicalIndex);
            if (physicalIndex >= raftLog.size()) {
                // Convert gRPC entry back to internal LogEntry
                LogEntry logEntry = convertFromGrpcLogEntry(entry);
                synchronized (raftLog) {
                    raftLog.add(logEntry);
                }
                entriesToPersist.add(logEntry);
                entriesAdded++;
            }
            newEntryLogicalIndex++;
        }
        // Persist all new entries in batch (CRITICAL for durability)
        if (!entriesToPersist.isEmpty()) {
            int startLogicalIndex = prevLogIndex + 1;
            persistenceService.appendLogEntries(config.getNodeId(), startLogicalIndex, entriesToPersist);
        }
        if (entriesAdded > 0) {
            logEvent(RaftEvent.EventType.LOG_REPLICATED, 
                "Replicated " + entriesAdded + " entries from leader " + request.getLeaderId());
        }
        // Update commit index based on leader's commit index (logical indices)
        if (request.getLeaderCommit() > commitIndex.get()) {
            commitIndex.set(Math.min(request.getLeaderCommit(), getLastLogIndex()));
            applyCommittedEntries();
        }
        return AppendEntriesResponse.newBuilder()
            .setTerm(currentTerm.get())
            .setSuccess(true)
            .setMatchIndex(getLastLogIndex())  // Logical index of last entry
            .build();
    }

Mit den folgenden gRPC Messages:

message AppendEntriesRequest {
  int32 term = 1;
  string leaderId = 2;
  int32 prevLogIndex = 3;
  int32 prevLogTerm = 4;
  repeated GrpcLogEntry entries = 5;
  int32 leaderCommit = 6;
}
message AppendEntriesResponse {
  int32 term = 1;
  bool success = 2;
  int32 matchIndex = 3;
}

Welche Aussagen treffen dabei zu?

Der Commit Index wird automatisch auf den größeren Index vom Leader gesetzt.

Wenn die Elemente noch nicht im lokalen Log enthalten sind, werden diese hinzugefügt.

Die Überprüfung des Terms ist korrekt und es werden keine kleineren Terms akzeptiert.

Die Abfrage nach der Pausierung der Nodes ist hier sauber implementiert.

AppendEntriesRequest und AppendEntriesResponse enthalten die geforderten Argumente.

Die Überprüfung des Terms ist noch nicht richtig implementiert.

Consensus algorithms for practical systems typically have the following properties:

Consistency of the logs is always ensured. Faulty clocks and extreme message delays can, at worst, cause availability problems.

They are never returning an incorrect result under all non-Byzantine conditions, including network delays, partitions, and packet loss, duplication, and reordering.

As long as any majority of the servers are operational and can communicate with each other and with clients, they give proper answers. Thus, a typical cluster of five servers can tolerate the failure of any two servers. Servers are assumed to fail by stopping; they may later recover from state on stable storage and rejoin the cluster.

In the common case, a command can complete as soon as most of the cluster has responded to a single round of remote procedure calls.

Raft guarantees that each of these properties is true at all times.

at most one leader can be elected in a given term

if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index

if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index

if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms

a leader never overwrites or deletes entries in its log; it only appends new entries

Image failed to load: Replicated Log

Folgende replizierte Log Struktur ist aufgetreten:

Welche Aussagen stimmen?

Image failed to load: ReplicatedStateMachine

Welche Aussagen sind zutreffend?

The consensus module on a server receives commands from clients and adds them to its log. It communicates with the consensus modules on other servers to ensure that every log eventually contains the same requests in the same order, even if some servers fail.

Since the state machines are non-deterministic, each computes the same state and the same sequence of outputs.

Keeping the replicated log consistent is the job of the client algorithm.

Once commands are properly replicated, each server’s state machine processes them in log order, and the outputs are returned to clients. As a result, the servers appear to form a single, highly reliable state machine.

Replicated state machines are typically implemented using a replicated log. Each server stores a log containing a series of commands, which its state machine executes in order. Each log contains the same commands in the same order, so each state machine processes the same sequence of commands.

Replicated state machines are used to solve a variety of fault tolerance problems in distributed systems.

Keeping the replicated log consistent is the job of the consensus algorithm. The consensus module on a server receives commands from clients and adds them to its log.

It communicates with the consensus modules on other servers to ensure that every log eventually contains the same requests in the same order, even if some servers fail.

One of the requirements for Raft is that safety must not depend on timing: the system must not produce incorrect results just because some event happens more quickly or slowly than expected.

Which answers are correct?

The broadcast time should be an order of magnitude less than the election timeout so that leaders can reliably send the heartbeat messages required to keep followers from starting elections.

Leader election is the aspect of Raft where timing is most critical. Raft will be able to elect and maintain a steady leader as long as the system satisfies the following timing requirement:

electionTimeout ≪ broadcastTime ≪ Mean Time Between Failures

Leader election is the aspect of Raft where timing is most critical. Raft will be able to elect and maintain a steady leader as long as the system satisfies the following timing requirement:

broadcastTime ≪ Mean Time Between Failures ≪ electionTimeout

Raft’s RPCs typically require the recipient to persist information to stable storage, so the broadcast time may range from 5 ms to 200 ms, and it is independent of storage technology.

Leader election is the aspect of Raft where timing is most critical. Raft will be able to elect and maintain a steady leader as long as the system satisfies the following timing requirement:

broadcastTime ≪ electionTimeout ≪ Mean Time Between Failures

Welche Aussagen bzw. Definitionen treffen auf Kubernetes zu?

Kubernetes allows you to automatically mount a storage system of your choice, such as local storages and public cloud providers.

Kubernetes takes care of scaling and failover of applications and provides deployment patterns.

Kubernetes is managing containerized workloads and services, that facilitates both declarative configuration and automation.

Kubernetes orchestrates computing, networking, and storage infrastructure on behalf of user workloads.