Distributed Systems Guide

A skill for researching and designing distributed systems, covering consensus algorithms, replication strategies, consistency models, fault tolerance, and performance analysis. Provides theoretical foundations and practical implementations relevant to systems research.

Consistency Models

Consistency Hierarchy

Strongest
  |  Linearizability (atomic, real-time ordering)
  |  Sequential consistency (program order respected)
  |  Causal consistency (causally related ops ordered)
  |  PRAM / FIFO consistency (per-process order)
  |  Eventual consistency (converges if updates stop)
Weakest

CAP Theorem and PACELC

The CAP theorem states that during a network partition, a distributed system must choose between consistency and availability:

System	Partition Behavior	Normal Behavior	Classification
ZooKeeper	Consistent (sacrifice A)	Low latency, consistent	CP / PC/EC
Cassandra	Available (sacrifice C)	Low latency, eventual	AP / PA/EL
Spanner	Consistent (sacrifice A)	Higher latency, consistent	CP / PC/EC
DynamoDB	Configurable per-read	Tunable consistency	AP or CP
CockroachDB	Consistent (sacrifice A)	Serializable	CP / PC/EC

Consensus Algorithms

Raft Implementation Sketch

from enum import Enum
from dataclasses import dataclass, field
import random

class NodeState(Enum):
    FOLLOWER = "follower"
    CANDIDATE = "candidate"
    LEADER = "leader"

@dataclass
class LogEntry:
    term: int
    index: int
    command: str

@dataclass
class RaftNode:
    """
    Simplified Raft consensus node for educational purposes.
    Implements leader election and log replication state machine.
    """
    node_id: str
    state: NodeState = NodeState.FOLLOWER
    current_term: int = 0
    voted_for: str = None
    log: list = field(default_factory=list)
    commit_index: int = 0
    last_applied: int = 0

    # Leader state
    next_index: dict = field(default_factory=dict)
    match_index: dict = field(default_factory=dict)

    def start_election(self, peers: list[str]) -> dict:
        """Transition to candidate and request votes."""
        self.state = NodeState.CANDIDATE
        self.current_term += 1
        self.voted_for = self.node_id

        last_log_index = len(self.log) - 1 if self.log else -1
        last_log_term = self.log[-1].term if self.log else 0

        return {
            "type": "RequestVote",
            "term": self.current_term,
            "candidate_id": self.node_id,
            "last_log_index": last_log_index,
            "last_log_term": last_log_term,
        }

    def handle_vote_request(self, term: int, candidate_id: str,
                              last_log_index: int,
                              last_log_term: int) -> dict:
        """Process a RequestVote RPC."""
        if term < self.current_term:
            return {"term": self.current_term, "vote_granted": False}

        if term > self.current_term:
            self.current_term = term
            self.state = NodeState.FOLLOWER
            self.voted_for = None

        # Check if candidate's log is at least as up-to-date
        my_last_term = self.log[-1].term if self.log else 0
        my_last_index = len(self.log) - 1 if self.log else -1

        log_ok = (last_log_term > my_last_term or
                  (last_log_term == my_last_term and
                   last_log_index >= my_last_index))

        vote_granted = (
            (self.voted_for is None or self.voted_for == candidate_id)
            and log_ok
        )

        if vote_granted:
            self.voted_for = candidate_id

        return {"term": self.current_term, "vote_granted": vote_granted}

    def append_entry(self, command: str) -> LogEntry:
        """Leader appends a new entry to its log."""
        entry = LogEntry(
            term=self.current_term,
            index=len(self.log),
            command=command,
        )
        self.log.append(entry)
        return entry