State Machine Replication, and Why You Should Care with Doug Patti

Contextual Shift in Engineering

• Doug Patti transitioned from building Node.js/Ruby web frameworks at startups to distributed systems at Jane Street.
• Jane Street systems historically operate on a "trading day" cycle (start up, operate, shut down) rather than 24/7 continuous rollouts.
• This model is evolving toward 24/7 operations, increasing the demand for continuous availability.
• A key divergence from web development is the near-absence of database interactions; Jane Street systems rarely rely on traditional databases.

Concord System Overview

• Purpose: Built to manage bilateral relationships with clients, shifting the firm from pure exchange trading to acting as a service provider.
• Role: Functions as both an exchange-like infrastructure and a liquidity provider for direct client trading.
• Requirements: High reliability, low latency, uptime, and strict regulatory audit trails.
• Architecture: Based on a "replicated state machine" model where processes process messages one at a time in a deterministic order.
• Protocol: Uses the FIX protocol with sequence numbers to handle re-synchronization after disconnections or crashes.
• Reliability Mechanism:
  • Relies on a transaction log to allow systems to restart and replay messages from the beginning of the day to recover exact state.
  • Utilizes UDP multicast for high-speed dissemination of the transaction log across the network.
  • Implements a dedicated "sequencer" process to stamp messages with timestamps and sequence numbers, establishing a single canonical order.
  • Uses a retransmission service to fill gaps caused by dropped UDP packets.
• Failure Handling: If the sequencer fails, the system halts; a backup sequencer is manually promoted to take over.
• Performance Metrics:
  • Handles transaction logs exceeding 400 GB per trading day.
  • Processes baseline rates of 100,000+ messages per second, spiking 3-5x on busy days.
  • Sequencer round-trip latency measures 8–12 microseconds.
• Design Trade-offs:
  • Scalability: Limited by a single choke point (the sequencer), but sufficient given the finite nature of the trading data volume.
  • Testability: Inversion of control (applications wait to be asked what to send) forces explicit state management, enabling precise simulation of race conditions.
  • Composability: Deterministic state machines allow code to be run in multiple processes without inter-process communication, as they all arrive at the same state given the same inputs.
• Limitations:
  • Versioning: Highly brittle; the entire system relies on a single global message type, making backward/forward compatibility difficult without a negotiation phase.
  • Overhead: High management cost for new instances due to dedicated hardware, config management, and networking requirements.
  • Performance Sensitivity: Every process must see every message, requiring constant optimization of message filtering and allocation-free OCaml code.

ARIA System Evolution

• Goal: Created to address Concord's brittleness and high overhead, serving as a general-purpose infrastructure for internal teams.
• Architecture:
  • Runs as a shared, centrally managed service with a proxy layer for users.
  • Introduces a hierarchical "topic" namespace allowing users to publish to and subscribe from specific subtrees.
  • Maintains a global canonical ordering across all topics to ensure deterministic replay, contrasting with systems like Kafka where ordering is only guaranteed per-shard.
• Key Features:
  • Filtering: Proxies filter messages so users only process relevant streams, reducing the load on light-weight clients.
  • Protocol Flexibility: Users can define their own message formats and versions per topic, though global ordering is preserved.
  • Permissioning: Write permissions are managed; read permissions are currently "best effort" trust-based, though the team is developing stricter controls.
  • Configuration: Allows dynamic configuration updates to be published as messages on the stream itself.
• Current Status:
  • In production across multiple regions with a small set of "high touch flow" Client Facing Tech teams.
  • Used for managing new types of orders and automating human-in-the-loop workflows.
• Identified Gaps & Future Work:
  • Rate Limiting: Currently missing; a single client can flood the system with messages, impacting internal sequencer performance.
  • Snapshots: Missing capability to skip replaying messages from the start of the day; currently exploring a model where clients build their own snapshot servers tailored to their state needs.
  • Scaling: Plans to optimize internal byte shuffling and add rate limiting to handle higher bandwidth requirements from future users.

Engineering Culture & Patterns

• Inversion of Control: Applications do not push messages but are polled on what to send next, preventing hidden state and infinite loops.
• Common Pitfalls: Developers may get stuck in infinite loops if they fail to update internal state after proposing a message.
• Abstractions: The team builds libraries (e.g., pipes) to enforce correct patterns and prevent anti-patterns.
• Adoption Strategy: Initial rollout restricted to nearby teams to manage complexity and acculturation before broader firm-wide evangelism.