distributed systems

Bilingual

The First Idempotency Key
2 months ago
- The author investigates the first instance of idempotency keys, unique identifiers that ensure duplicate API messages are ignored.
- Claude AI initially claimed Stripe introduced idempotency keys around 2011, but later retracted, noting Stripe popularized the header circa 2015.
- Earlier concepts include Amazon EC2's ClientToken and the 2005 POST Once Exactly specification using unique POST URLs.
- Transport-level standards like OASIS ebXML and WS-ReliableMessaging also aimed at exactly-once processing via message deduplication.
- The earliest electronic example found is from Birrell and Nelson's 1984 paper on RPC at Xerox PARC, which used a call identifier to eliminate duplicate packets.
- Historical precursors like Incan quipu and tally sticks are mentioned but excluded as they don't involve electronic computers.
Consensus Board Game
2 months ago
- Consensus is fundamentally based on simple majority voting, but can get stuck with split votes (e.g., two red, two blue, one green).
- To resolve split votes, a leader is designated to choose a color while others approve, though the leader may be unavailable.
- The solution involves multiple concurrent votes with rotating leaders across a 2D board of columns, where each column operates independently.
- A board is invalid if different columns achieve majorities for different colors; the safety condition requires that any two columns with majorities agree on the same color.
- Players must choose colors that don't conflict with columns to the left, ensuring consistency by assuming fair play and committing majorities to abstain in earlier columns.
- The final decision rule is to pick the rightmost possible color, as other participants' past choices guarantee conflicts have been resolved through prior abstentions.
<antirez>
2 months ago
- Queues enable splitting a computation into scheduling and execution, using producers (put tasks) and consumers/workers (execute tasks).
- At-most-once delivery acknowledges messages before processing, risking message loss if the worker fails.
- At-least-once delivery acknowledges after processing, allowing multiple deliveries but preferred in practice for avoiding data loss.
- At-least-once systems benefit from eventually consistent data structures (e.g., CRDTs) rather than strong consistency, improving performance and partition tolerance.
- Practical queue features include single-worker delivery windows, best-effort duplicate avoidance, FIFO ordering, and auto-cleanup.
- Redis-based queue implementations can leverage independent Redis nodes to build a distributed queue with high performance and scalability.
- The author is designing a Redis-based queue system to provide these guarantees and plans to share progress soon.
<antirez>
2 months ago
- Redis Cluster development started in March 2011, but took nearly 4 years to reach its first Release Candidate (3.0.0-rc1) due to early missteps and shifting priorities.
- The project was initially rushed because scaling was seen as critical, but Redis itself was too immature, leading to repeated pauses to focus on more fundamental features like persistence, replication, and latency.
- The author lacked distributed programming knowledge at the start, resulting in a flawed initial design that was later redesigned after studying the basics.
- Redis Cluster provides data sharding with online resharding and failover, but offers only eventual consistency and limited availability during partitions—it is neither a CP nor an AP system.
- To mitigate divergence, the minority partition becomes unavailable, replication and client replies are sent together, and the least diverging slave is chosen for failover.
- The design sacrifices theoretical guarantees for practical benefits: low overhead, full Redis API support, and no limits on data structure sizes.
- The release candidate is a minimum viable product meant to gain adoption, with future improvements planned: multi-datacenter support, better write safety, automatic node balancing, and a caching mode.
- The author emphasizes that it's time to ship the current version and iterate based on user feedback, rather than delaying further for perfect features.
<antirez>
2 months ago
- Disque is a new message broker system developed by antirez (Salvatore Sanfilippo), the creator of Redis, as a side project.
- It originated from the observation that many developers use Redis as a message queue, despite Redis not being optimized for immutable messages.
- Disque aims to fill the gap between overly simple and overly complex message brokers, offering a 'Redis of messaging' with a low barrier to entry.
- The system guarantees at-least-once delivery by default, with optional at-most-once semantics per message, using acknowledgments and automatic retries.
- Disque is a distributed, AP (available and partition-tolerant) system that scales horizontally, even for single-queue scenarios.
- It sacrifices strict message ordering in favor of best-effort FIFO ordering, using a wall-clock timestamp and incremental ID.
- Durability is achieved through synchronous replication across nodes, with optional AOF persistence for upgrades or mass reboots.
- Disque supports delayed jobs, named queues, consumer blocking, and transactional message posting with configurable replication.
- The codebase is a fork of Redis with Redis-specific parts removed, allowing Disque to diverge as needed while reusing Redis's networking and protocol infrastructure.
- Currently, most features are implemented (except AOF persistence), and the source code is available on GitHub.
Distributed System Is Slower Than a Laptop
3 months ago
- A 2015 paper showed single-threaded laptop outperformed distributed systems on large-scale graph processing tasks.
- Many distributed systems fail to beat a single competent thread even with hundreds of cores, leading to high COST (Configuration that Outperforms a Single Thread).
- Companies pay millions for distributed systems when simpler, cheaper single-machine solutions suffice and perform better.
- Hardware improvements have made single servers extremely powerful, but distributed-by-default reflexes persist without justification.
- Distributed systems often introduce unnecessary complexity, higher costs (compute, engineering, incidents), and slower performance.
- Frameworks, career incentives, vendor pricing, and misconceptions about scaling drive unnecessary distribution.
- Legitimate reasons for distribution include data size, availability needs, geographic latency, and organizational partitioning.
- Building a single-machine baseline before adopting distributed architectures can save costs and improve design decisions.
Cloudflare Meerkat - Globally distributed consensus
3 months ago
- Cloudflare needs a distributed consensus service for global control-plane state management, ensuring strong consistency and availability despite network unpredictability.
- Raft-based systems suffer in wide-area networks due to leader dependency and timeout issues, leading to availability problems during leader failures or network degradation.
- Meerkat is Cloudflare's new consensus service using the QuePaxa algorithm, allowing all replicas to perform writes without timeouts, improving fault tolerance and availability.
- Meerkat guarantees linearizability for applications like a key-value store, ensuring all reads see prior writes even across distributed replicas, using a consensus log to synchronize events.
- QuePaxa provides higher availability than Raft by eliminating required leaders, avoiding leader election delays, and handling concurrent proposals constructively in unreliable networks.
- Meerkat has latency limitations due to consensus round-trips but optimizes performance through batching, replica placement control, and optional stale reads for non-critical data.
- The service is experimental and internal-only for now, designed for infrequently written control-plane data, with future blog posts planned on its implementation and verification.
Postgres transactions are a distributed systems superpower
3 months ago
- Workflows and application data can be co-located in the same Postgres database, enabling updates in the same transaction to simplify fault tolerance.
- Co-location allows transactional steps to achieve exactly-once execution semantics by combining database updates and checkpoints in a single transaction, eliminating the need for external idempotency logic.
- A transactional workflow outbox pattern can be implemented within the same database using user-defined functions to ensure atomic updates and notifications, reducing operational complexity compared to separate systems.
- DBOS provides tools for building scalable, reliable systems with Postgres-backed durable execution.
Lunatic: An Erlang-inspired runtime for WebAssembly
3 months ago
- Lunatic is an open-source WebAssembly runtime inspired by Erlang.
- It provides isolated, lightweight processes for high concurrency and fault tolerance.
- Features include performance through JIT-compiled Wasm, security via capability limits, and distributed clustering.
- Applications are portable across architectures and OSes, compiled once to WebAssembly.
- Supervision trees enable monitoring and recovery of failing processes.

distributed systems

The First Idempotency Key

Consensus Board Game

<antirez>

<antirez>

<antirez>

Distributed System Is Slower Than a Laptop

Cloudflare Meerkat - Globally distributed consensus

Postgres transactions are a distributed systems superpower

Lunatic: An Erlang-inspired runtime for WebAssembly