Catalog of Patterns of Distributed Systems

23 November 2023

Distributed systems provide a particular challenge to program. They often require us to have multiple copies of data, which need to keep synchronized. Yet we cannot rely on processing nodes working reliably, and network delays can easily lead to inconsistencies. Despite this, many organizations rely on a range of core distributed software handling data storage, messaging, system management, and compute capability. These systems face common problems which they solve with similar solutions.

In 2020 I began collecting these solutions as patterns, publishing them on this site as I developed them. In 2023 these were published in the book Patterns of Distributed Systems. On this site I now have short summaries of each pattern, with deep links to the relevant chapters for the online eBook publication on oreilly.com (marked on this page with ).

Clock-Bound Wait  link to chapter on oreilly.com

Wait to cover the uncertainty in time across cluster nodes before reading and writing values so that values can be correctly ordered across cluster nodes.

Consistent Core  link to chapter on oreilly.com

Maintain a smaller cluster providing stronger consistency to allow the large data cluster to coordinate server activities without implementing quorum-based algorithms.

Emergent Leader  link to chapter on oreilly.com

Order cluster nodes based on their age within the cluster to allow nodes to select a leader without running an explicit election.

Fixed Partitions  link to chapter on oreilly.com

Keep the number of partitions fixed to keep the mapping of data to partition unchanged when the size of a cluster changes.

Follower Reads  link to chapter on oreilly.com

Serve read requests from followers to achieve better throughput and lower latency

Generation Clock  link to chapter on oreilly.com

A monotonically increasing number indicating the generation of the server.

Gossip Dissemination  link to chapter on oreilly.com

Use a random selection of nodes to pass on information to ensure it reaches all the nodes in the cluster without flooding the network

HeartBeat  link to chapter on oreilly.com

Show a server is available by periodically sending a message to all the other servers.

High-Water Mark  link to chapter on oreilly.com

An index in the write-ahead log showing the last successful replication.

Hybrid Clock  link to chapter on oreilly.com

Use a combination of system timestamp and logical timestamp to have versions as date and time, which can be ordered

Idempotent Receiver  link to chapter on oreilly.com

Identify requests from clients uniquely so you can ignore duplicate requests when client retries

Key-Range Partitions  link to chapter on oreilly.com

Partition data in sorted key ranges to efficiently handle range queries.

Lamport Clock  link to chapter on oreilly.com

Use logical timestamps as a version for a value to allow ordering of values across servers

Leader and Followers  link to chapter on oreilly.com

Have a single server to coordinate replication across a set of servers.

Lease  link to chapter on oreilly.com

Use time-bound leases for cluster nodes to coordinate their activities.

Low-Water Mark  link to chapter on oreilly.com

An index in the write-ahead log showing which portion of the log can be discarded.

Majority Quorum  link to chapter on oreilly.com

Avoid two groups of servers making independent decisions by requiring majority for taking every decision.

Paxos  link to chapter on oreilly.com

Use two consensus building phases to reach safe consensus even when nodes disconnect

Replicated Log  link to chapter on oreilly.com

Keep the state of multiple nodes synchronized by using a write-ahead log that is replicated to all the cluster nodes.

Request Batch  link to chapter on oreilly.com

Combine multiple requests to optimally utilise the network

Request Pipeline  link to chapter on oreilly.com

Improve latency by sending multiple requests on the connection without waiting for the response of the previous requests.

Request Waiting List  link to chapter on oreilly.com

Track client requests which require responses after the criteria to respond is met based on responses from other cluster nodes.

Segmented Log  link to chapter on oreilly.com

Split log into multiple smaller files instead of a single large file for easier operations.

Single-Socket Channel  link to chapter on oreilly.com

Maintain the order of the requests sent to a server by using a single TCP connection

Singular Update Queue  link to chapter on oreilly.com

Use a single thread to process requests asynchronously to maintain order without blocking the caller.

State Watch  link to chapter on oreilly.com

Notify clients when specific values change on the server

Two-Phase Commit  link to chapter on oreilly.com

Update resources on multiple nodes in one atomic operation

Version Vector  link to chapter on oreilly.com

Maintain a list of counters, one per cluster node, to detect concurrent updates

Versioned Value  link to chapter on oreilly.com

Store every update to a value with a new version, to allow reading historical values.

Write-Ahead Log  link to chapter on oreilly.com

Provide durability guarantee without the storage data structures to be flushed to disk, by persisting every state change as a command to the append only log.