System Design Toolbox – Comprehensive Guide

(Document 1)
1. Databases & Storage Technologies

Relational Databases (SQL – e.g. PostgreSQL, MySQL)

Relational databases organize data into tables (rows and columns) with fixed schemas and support
powerful SQL queries (including JOIN operations to combine data from multiple tables). They ensure ACID
properties – Atomicity, Consistency, Isolation, Durability – which guarantee reliable transactions even in
failures 1 . For example, atomicity means a money transfer updating two accounts is all-or-nothing, and
durability ensures once it commits, it won’t be lost even if the server crashes.

Use cases: financial and banking systems, e-commerce orders, and other applications needing strong
consistency and complex querying (e.g. multi-table joins). ACID compliance makes relational DBs ideal when
data integrity is paramount 2 .

Indexing: Relational DBs use indexes (typically B-tree indexes) on columns to speed up lookups and range
scans. For instance, creating an index on email in a users table makes searching by email much faster. B-
tree indexes maintain sorted data for efficient retrieval 3 4 . They are optimal for range queries (e.g. find
IDs between 100 and 200) and frequent updates. Other index types include hash indexes (for exact
lookups) and bitmap indexes (for low-cardinality columns in analytic queries) 5 . Full-text search in
relational DBs is supported via inverted indexes that map words to document locations, similar to search
engines 6 .

Scaling: By default, SQL databases run on a single node (vertical scaling). To scale out, one can use read
replicas for read-heavy workloads or implement sharding (horizontal partitioning) to distribute data across
multiple servers. Sharding strategies include splitting data by ranges (e.g. ID ranges) or hashing a key – see
Partitioning below for details. For example, a large user table might be sharded by user ID range into
multiple databases (users 1–1k on shard A, 1001–2000 on shard B, etc.). However, sharding relational data
can be complex due to joins and multi-shard transactions, so it’s usually a last resort after vertical scaling
and caching.

Transactions: Relational DBs support multi-statement transactions. Below is a simple transaction example
in pseudo-SQL, transferring money between two accounts:

BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;

1
 -- The transfer will only persist if both updates succeed
COMMIT;

This ensures consistency – partial updates won’t be visible if an error occurs; either both updates apply or
none (atomicity).

Sharding strategies: If a single SQL instance can’t handle the load, data may be partitioned. Common
strategies are: - Range sharding: each shard holds a continuous range of values (e.g. users with IDs 1–1000
on shard 1, 1001–2000 on shard 2) 7 . This preserves locality for range queries but may cause hot spots if
data is uneven (e.g. recent IDs all on one shard). - Hash sharding: a hash function on a key (like user ID)
distributes rows evenly across shards 8 . This balances load but can make range queries harder (since
adjacent keys might be on different shards). - Directory/zone sharding: predefined lists or categories route to
shards (e.g. users by region or country) 9 . For example, EU customers on one shard and US on another –
useful for geo-based partitioning. - Consistent hashing: a special hashing that makes adding/removing
shards easier by minimizing data movement 10 . Data keys and shard identifiers are placed on a hash ring;
each key goes to the nearest shard on the ring. If a shard is added or removed, only a subset of keys
reroute (see Partitioning in section 2 for more).

Key-Value Stores (e.g. Redis, Memcached, Amazon DynamoDB)

Key-value stores are the simplest databases – they function like giant hash tables or dictionaries: clients
provide a key and get back an associated value. These systems are optimized for constant-time gets and
puts by key, making them extremely fast (often in-memory). For example, Redis and Memcached keep data
in memory for low-latency access (sub-millisecond), which is why they’re commonly used for caching
frequently accessed data. DynamoDB is a cloud key-value store that durably stores data across SSDs and
scales automatically; it sacrifices some query flexibility for throughput and reliability.

Characteristics: Key-value stores don’t enforce a schema or relationships between data. The value could be
any blob (string, JSON, etc.), and the system doesn’t inspect it – you can’t query “inside” the value without
retrieving it. This makes them limited in query capabilities (no complex conditions or joins) but extremely
scalable for simple access patterns 11 . If you need to fetch an item and know its key, key-value stores
excel; but if you need to filter or search by value fields, you typically need a different approach or maintain
secondary indexes in your application.

Use cases: - Caching and session storage: e.g. store user session data or page HTML fragments in Redis
with keys like "session:{userid}" for quick retrieval, instead of hitting a database. - Configuration
and feature flags: a centralized config that apps can quickly look up. - Low-latency read/write for simple
data: e.g. a gaming leaderboard where score is stored under player ID. - DynamoDB specifically is used for
web-scale applications needing massive throughput and auto-scaling (it’s eventually consistent by default
and can be configured for strong consistency on reads). It’s often used when a fully managed, highly
available key-value store is needed.

Example – using Redis as a cache: Suppose we want to cache user profiles to reduce database load. On
login, we set SET user:1234 "{name:'Alice', age:30, ...}" in Redis. Next time,
GET user:1234 returns the JSON from memory. If it’s a miss, we fetch from the DB and then populate
the cache (cache-aside pattern). Memcached would be similar (though it only offers a simple key->value in-
memory store without persistence or rich data types). DynamoDB usage is slightly different (it’s persistent

2
and accessed via API calls), but still you specify a key to read or write an item (which can be a JSON
document).

Performance: Key-value stores are designed for O(1) lookups and updates. Redis in particular can handle
hundreds of thousands of ops/sec on a single node. Memcached is often used purely for caching ephemeral
data (it’s in-memory and not persistent). Redis offers more features (persistence options, replication, pub/
sub, data structures like lists and sets). DynamoDB and similar cloud KV stores scale horizontally by
partitioning keys (each item’s key is hashed to a partition; it’s essentially a big distributed hash table). A risk
in key-value systems is hot keys – if one key is read or written extremely often, that partition or node can
become a bottleneck (see Hot Key Mitigation in section 3).

Document Stores (NoSQL – e.g. MongoDB, Couchbase)

Document databases store data as documents, typically in JSON or similar formats (MongoDB uses a binary
JSON called BSON). Each document is a self-contained data structure with some unique key (like an _id in
MongoDB). Unlike relational rows, each document can have a flexible schema – fields can vary between
documents, and new fields can be added on the fly without altering a global schema 12 . This schema
flexibility is great for evolving requirements or heterogeneous data.

For example, consider a user profile document in MongoDB:

{
"_id": "user_1234",
"name": "Alice",
"age": 30,
"address": {"city": "Paris", "zip": "75001"},
"preferences": ["music", "travel"],
"allergies": ["peanuts"]
}

Another user might have a different structure (maybe an extra "favorite_color" field or no allergies).
The database doesn’t require all docs to have the same fields.

Querying: Document stores allow queries on the content of documents (not just by key). For instance, you
can query for all users with age > 25 or all users whose [Link] = "Paris" . They support
secondary indexes on document fields to make such queries efficient 13 . Unlike key-value stores, you can
filter and aggregate data by fields inside the JSON. Many document DBs also provide an aggregation
framework for grouping and computing stats.

Use cases: Content management systems, user profiles, event logs – any scenario where data is naturally
hierarchical or varies in structure. Documents often represent self-contained entities that would otherwise
require joining multiple tables in SQL. For example, an e-commerce order can be a single document
containing customer info, an array of item line objects, timestamps, etc., rather than normalizing into
separate tables.

3
Strengths: - Flexible schema: easy to adjust to changing data models. - Natural data modeling: store
data in a form similar to how applications use it (e.g. an object graph). - Denormalization for
performance: you can embed related data within a document to avoid join operations (e.g. store an array
of comments inside a blog post document). - Scalability: Many document DBs (MongoDB, Couchbase) can
distribute data across multiple nodes (sharding) to handle large data volumes.

Trade-offs: - Lacks complex joins across collections – if you need multi-document ACID transactions,
support is limited (MongoDB in recent versions supports multi-document transactions, but it’s not as heavy-
duty as an SQL transaction scenario). - Potential data duplication (since you might embed data instead of
normalizing) and consistency issues if the same piece of data is copied in many documents.

Example query (MongoDB): To find all users over 25 in MongoDB, one could do:

[Link]({ age: { $gt: 25 } })

MongoDB would allow an index on the age field to speed this up. Document stores often also allow full-
text search and geospatial queries on fields with specialized indexes, making them versatile.

Wide-Column Stores (e.g. Apache Cassandra, HBase)

Wide-column stores (also known as column-family databases) organize data into rows and dynamic
columns, but unlike relational tables, each row can have a variable number of columns and new columns
can be added per row on the fly 14 . Data is grouped into column families. Think of a column family as a
container of rows, where each row has a primary key and can have many columns (key-value pairs) under
that row, which are often sparsely populated. This model comes from Google’s Bigtable design.

For example, in a wide-column DB you might have a column family SensorReadings where the row key is
a sensor ID, and each column under that row is a timestamp with a value:

Row Key: sensor_ABC123

2023-10-01T10:00: value=65
2023-10-01T10:01: value=67
2023-10-01T10:02: value=66
... (each timestamp as a column name)

This single row can have millions of columns (one per time entry). Another sensor row might have a
completely different set of timestamps (columns).

Characteristics: - Optimized for writing large sequential data and range reads of rows. They are append-
friendly – new data often just adds new columns or new rows. - The data model is schema-optional: you
define families but not all columns upfront. Each row can add columns as needed. - Excellent at scale-out:
Cassandra, for instance, is designed to run on clusters of tens or hundreds of nodes with no single point of
failure. Data is automatically partitioned (by hashing the row key) and replicated across nodes.

4
Consistency model: Many wide-column stores prioritize availability and partition tolerance (AP in CAP
terms). Cassandra famously offers tunable consistency – you can configure on each query how many
replicas must agree (quorum) to consider a read or write successful. By default, Cassandra is eventually
consistent (a write may not immediately be on all replicas, but will synchronize in the background) and
highly available (it does not require all replicas to be up to accept writes).

Use cases: - Time-series data (metrics, logs): as shown in the sensor example, storing time-indexed values
per entity is very efficient. - Event logging and analytics: e.g. user activity events keyed by userID, with
columns for each event timestamp. - High-write throughput scenarios: Cassandra can ingest a huge
volume of writes per second across cluster nodes (it uses an LSM-tree storage engine to optimize writes and
sequential IO). - Geo-distributed databases: Cassandra and similar allow replication across data centers
and can serve globally distributed applications with local replicas for low latency.

Query patterns: Typically, you query by row key (must know the key or do a range scan on keys) and
optionally a column range. They are not suited for arbitrary ad-hoc queries on any field – you design your
schema and keys around your access patterns. For example, Cassandra requires queries to include the
partition key; you can’t filter by an unindexed column without scanning all data. This often means
denormalizing or duplicating data under multiple keys for different query needs.

Example – Cassandra table: Defining a table in Cassandra’s CQL (SQL-like) might look like:

CREATE TABLE SensorReadings (

sensor_id text,
ts timestamp,
value double,
PRIMARY KEY (sensor_id, ts)
) WITH CLUSTERING ORDER BY (ts DESC);

Here sensor_id is the partition (row) key, ts is a clustering key (columns within the row sorted by ts). A
query might fetch recent readings for a sensor:

SELECT ts, value FROM SensorReadings

WHERE sensor_id = 'ABC123' AND ts >= '2023-10-01' AND ts < '2023-10-02';

This would efficiently retrieve a time-slice of one sensor’s data. Cassandra would only touch the partition for
'ABC123' rather than scanning the whole dataset.

Scalability: Wide-column stores shine in scaling both data volume and throughput. Cassandra, for instance,
has a masterless architecture – each node is equal, and data is spread via consistent hashing. If a node fails,
others take over serving its data (due to replication) 15 . HBase uses a master/regionserver model on top of
Hadoop HDFS for storage – it can scale but has a single master for metadata. Both systems can handle
billions of rows and high write loads, making them suitable for big data scenarios.

5
Graph Databases (e.g. Neo4j, JanusGraph)

Graph databases are tailored for data with complex relationships. They store data as nodes (vertices) and
edges between nodes, where both nodes and edges can have properties 16 . This structure directly
represents graphs (like social networks, recommendation networks, knowledge graphs) and allows for
efficient traversal of relationships.

Example: Nodes might represent entities like Person or Product . Edges represent relationships: Alice --
friend--> Bob, or Alice --purchased--> Item123. Each edge can have a type and possibly attributes (e.g. an
edge likes could have a property since: 2020 ).

Querying: Graph DBs allow queries that traverse the graph, such as “find friends of friends of Alice” or “find
users who bought the same products as Bob.” These multi-hop traversals are where graph DBs excel – they
can retrieve connected data in one query without heavy join logic. For instance, a Cypher query (Neo4j’s
language) to find friends-of-friends:

MATCH (p:Person {name: "Alice"})-[:FRIEND]->(friend)-[:FRIEND]->(fof)

RETURN DISTINCT [Link];

This would quickly find all people two hops away from Alice in the friendship graph.

Use cases: - Social networks: modeling users, friendships, follows, likes. Graph DBs can easily answer
questions like mutual friends, recommendation of friends, shortest path between people. -
Recommendations: e.g. a movie recommendation system where you have users, movies, and edges like
user watched movie, user likes genre, movie in genre. One could traverse “Alice -> watched -> [Movies] -> other
users who watched those -> other movies they watched -> recommend those movies to Alice.” - Fraud
detection: find rings of transactions or common identities – e.g. detect if multiple accounts share info or
have cycles of money transfers 17 . - Network/IT configuration: model network devices and connections,
query impact of a node failure. - Hierarchy or dependency data: organizational charts, package
dependency graphs, etc.

Advantages: Graph queries that would be join-intensive in SQL or hard to precompute become
straightforward. The performance remains good even as relationship complexity grows, because graph DBs
use index-free adjacency – each node directly links to its neighbors in storage. So traversing edges is fast
(essentially pointer hops).

Scaling: Many graph databases are optimized for fast traversal on a single machine (Neo4j keeps a lot in
memory). Distributed graph databases exist (JanusGraph can sit atop Cassandra or Google Cloud Bigtable
to distribute storage; it often uses TinkerPop/Gremlin as a query interface), but distributed traversals can be
challenging. Usually, graph DBs are chosen for problems that fit in memory or can be partitioned in a way
that most traversals are local.

Graph query languages: Common ones include Cypher (Neo4j), Gremlin (Apache TinkerPop, used by
JanusGraph), and the emerging standard GQL. These allow expressive patterns like path matching, variable
length traversals (“find nodes within 4 hops”), etc.

6
Time-Series Databases (e.g. InfluxDB, TimescaleDB)

Time-series databases are optimized for handling sequences of measurements over time. They treat time
as a primary axis and are designed for appending data (writes) and time-range queries. Key features
often include: efficient storage for high-volume data (with compression), downsampling and retention
policies (to aggregate or expire old data), and fast retrieval of recent vs. historical data.

InfluxDB: A popular open-source time-series DB. Data in Influx is organized into measurements, tags, and
fields. For example, you might have a measurement cpu_usage with tags like host=webserver1,
region=us-east and a field value=55 . A data point also has a timestamp. InfluxDB’s line protocol for
writing data looks like:

cpu_usage,host=webserver1,region=us-east value=55.0 1696368000000000000

(This writes a value 55.0 at the given Unix nanosecond timestamp for host=webserver1). InfluxDB
automatically indexes the time and tags for queries like “max cpu_usage per host in last 1h”.

TimescaleDB: This is implemented as an extension on PostgreSQL, turning it into a time-series database. It

provides hypertables which automatically partition data by time (and optionally another key, like device id).
You interact with it using standard SQL (with added time-series functions). For example, you can create a
hypertable for a readings table and Timescale will automatically chunk it by time ranges for efficiency.

Use cases: - Metrics and monitoring: server metrics (CPU, memory usage), application performance
metrics, DevOps monitoring (e.g. Prometheus stores time-series). - IoT sensor data: readings from sensors
(temperature, humidity, etc.) typically time-indexed. - Financial data: stock prices, crypto trades, where
high volumes of tick data need to be stored and queried by time. - Event logging: though logs are
unstructured, time-series DBs or log databases (like Elasticsearch, Splunk) treat timestamp as a primary
field for slicing data.

Optimizations: Time-series DBs often have: - Compression: Adjacent time points often don’t differ much,
so storage engines compress data (Facebook’s Gorilla paper describes time-series compression used in
their systems, for example). - Retention: Automatically dropping or downsampling old data. E.g. keep 1-
second granularity for 7 days, then aggregate to 1-minute points for older data to save space. - Batch
ingestion: Accepting large bursts of data efficiently. They often encourage sending points in batches rather
than one at a time for throughput. - Efficient rollups: Functions like MEAN, MAX over intervals are
common, so DBs optimize those.

Query example: In InfluxDB’s SQL-like query language:

SELECT mean(value)
FROM cpu_usage
WHERE region = 'us-east' AND time >= now() - 1h
GROUP BY time(1m), host;

7
This would compute 1-minute average CPU usage per host over the last hour. Timescale would allow a
similar query with standard SQL using time_bucket('1 minute', timestamp) to group timestamps.

Time-series databases ensure that querying recent data (which might reside in memory or in the latest
partitions) is very fast, and they can also efficiently scan historical partitions if needed. They can handle out-
of-order writes too, but generally data arrives roughly in time order.

Search Engines (Full-text Search – e.g. Elasticsearch, Apache Solr)

Search engines like Elasticsearch and Solr specialize in full-text search and analytics on text or semi-
structured data. They index data using an inverted index, which maps terms to the documents that contain
them 18 . This allows extremely fast keyword searches, relevance scoring, and text-specific queries (like
fuzzy matching, prefix queries, etc.) that are not feasible in traditional databases.

Data model: You typically index documents (like JSON objects) into an index (similar to a table). Each field
can be tokenized for search. For example, indexing an article document:

{
"id": 123,
"title": "Elasticsearch Basics",
"content": "Elasticsearch is a distributed search engine based on Lucene...",
"tags": ["search", "database", "Lucene"]
}

The engine will break text fields into terms (applying analyzers for lowercasing, removing stopwords, etc.),
and build an inverted index: e.g. map “elasticsearch” -> {doc 123, positions...}, “search” -> {doc 123, ...}, etc.

Querying: Search engines support a query language or JSON DSL. A query might be “find documents where
content contains ‘distributed search engine’ near each other and tag is database”. They rank results by
relevance (e.g. TF-IDF or BM25 scoring). They also support structured filters (like numeric ranges, dates) and
aggregations (faceted counts, histograms) on fields.

Features: - Free text search: e.g. match all docs containing certain words, with ranking by frequency and
rarity of terms. - Phrase search: find exact phrases or proximity matches. - Autocomplete suggestions: via
prefix indexing or specialized structures like a trie or n-grams. - Faceted navigation: counts of results by
category (e.g. show how many results per tag or per date range). - Geospatial search: find points within a
radius, etc. - Did-you-mean suggestions, highlighting, etc.

Elasticsearch is built on Apache Lucene. It’s distributed and stores data in shards (each shard is a Lucene
index). It provides a JSON-based REST API. Solr is also built on Lucene and offers similar capabilities,
historically with an XML/HTTP interface and strong customization.

Scaling: These engines scale by sharding the index and replicating shards. A large corpus is split across
multiple nodes. Queries are distributed to relevant shards and results merged. They’re designed for high
read volumes and can index a lot of data, but keep in mind they often have higher storage overhead
(because of indexes) and need memory for caching frequent queries and keeping indexes hot.

8
Use cases: - Website search: e.g. searching products on an e-commerce site by name, description, filtering
by facets like category, price range. - Log analytics: ELK Stack (Elasticsearch, Logstash, Kibana) is commonly
used to ingest and search logs. Logs are text, and you want to search error messages, aggregate by fields
(like status code). - Document search: indexing documents (PDFs, articles) to search their content. -
Autocomplete and suggestions in applications.

Example query (Elasticsearch): A JSON DSL query to find documents with “distributed” and “search engine”
in the content field might look like:

GET /articles/_search
{
"query": {
"match_phrase": { "content": "distributed search engine" }
},
"filter": {
"term": { "tags": "database" }
}
}

This would return articles whose content contains that exact phrase, filtered to those tagged “database”,
sorted by relevance (which in phrase query includes proximity).

Elasticsearch also supports aggregations, e.g. getting a histogram of counts by tag or date in the search
results.

Search engines often complement databases: you might store data in a DB for transactions, but index a
subset of fields in Elasticsearch for powerful text search and analytics. The results can include relevance
scores, etc., which a DB query wouldn’t easily provide.

Blob/Object Storage (e.g. Amazon S3, Google Cloud Storage, HDFS)

Object storage is designed for storing and retrieving large binary objects (files, images, videos, backups,
etc.) in a scalable, cost-effective way. Unlike block storage or file systems, object stores treat each file as an
independent object with metadata and a key (often a path or unique ID).

S3/GCS (cloud object stores): You store objects in buckets. Each object has a key (like "user-photos/
alice/[Link]" ). You can PUT objects (upload) and GET them (download) via APIs or HTTP. These
systems handle replication and durability behind the scenes (S3, for example, stores multiple copies across
availability zones). They can scale to massive sizes (petabytes and billions of objects) seamlessly. Object
storage is typically eventually consistent for listing and reads after writes (though some operations in S3
now have strong consistency for new object puts). Access latency is higher than local disk or database (tens
of milliseconds) but acceptable for files.

HDFS (Hadoop Distributed File System): This is more of a block storage distributed file system used in
Hadoop clusters. It stores files by splitting into blocks and replicating across a cluster. It’s optimized for
throughput of large files (e.g. scanning large dataset files in MapReduce jobs) rather than low-latency

9
access to small files. HDFS provides the foundation for big data processing engines (MapReduce, Spark,
etc.).

Use cases: - Storing user-generated content: photos, videos, attachments – e.g. when you upload a photo
to a service, it likely ends up in an S3 bucket. - Backups and archives: dumping database backups or logs
to object storage for durability. - Data lakes: raw data (like event logs, CSVs, JSON) stored in S3 or HDFS to
later be processed by big data/analytics tools. Cloud data warehouses (like Snowflake, BigQuery) and
Hadoop/Spark jobs will often read from and write to object storage. - Content delivery: object storage can
be fronted by a CDN to serve images, scripts, etc., to users.

Key features: - Durability: e.g. S3 is designed for 99.999999999% durability (11 nines) – losing data is
extremely unlikely due to replication. - Scalability: virtually unlimited namespace, handle concurrent
access, etc. - Metadata and lifecycle: tag objects with metadata, set lifecycle rules (e.g. auto-move to
colder storage or delete after X days). - No partial update: typically, to change an object you re-upload it
(though some systems allow range writes or append; S3 allows a multi-part upload but not in-place
modification). - Read-after-write: after uploading, you can generally read the object (S3 now guarantees
read-after-write consistency for new objects). Overwrites or deletes might take some time to reflect in
listings.

APIs: Access is usually via RESTful APIs. For example, with AWS SDK one can do:

s3.put_object(Bucket="mybucket", Key="path/to/[Link]", Body=data)

s3.get_object(Bucket="mybucket", Key="path/to/[Link]")

These operations store and retrieve the file. Permissions are managed via access control lists or bucket
policies.

Cost model: Object storage is cheap per GB and can store enormous data, but access costs can apply
(especially egress). It’s not meant for high IOPS on small data (for that, databases or block storage are
better).

Ledger/Immutable Stores (e.g. Event Store, Kafka (log-compacted topics))

These systems are designed to maintain an immutable, append-only log of events or records, ensuring a
reliable sequence that can serve as a system of record (audit log or ledger). The idea is that instead of
updating and mutating data in place, all changes are recorded as sequential events, which can be used to
reconstruct state and provide a transparent history.

Event Sourcing & EventStoreDB: In event sourcing architecture, each change to an application state is
stored as an event (e.g. “OrderPlaced”, “OrderShipped”) in an append-only store. The EventStore database
(by Greg Young) is a purpose-built DB for event sourcing that stores events in streams, each stream being
like a category or aggregate (for example, all events for Order #123). Events are immutable – once written,
they are never updated, only new events append. To get current state, you read and fold (aggregate) all
events for an entity. EventStore ensures ordering per stream and can atomically append events (so it
supports transactional writes of events). This is great for auditability because you have the full history. It can
also publish events to subscribers, enabling reactive systems.

10
Use cases: financial ledger systems (where every credit/debit entry is recorded and you need a trail), audit
logs, event-sourced applications where state changes must be replayable or retroactively analyzable, and
any scenario requiring immutable history (e.g. healthcare records where edits must be preserved, or
accounting systems where you never delete transactions but offset them with new transactions).

Kafka with log compaction: Apache Kafka is a distributed log (messaging system), but with log-
compacted topics it can act as a key-value store that retains at least the latest event for each key. Normally
Kafka topics keep messages for a retention time (e.g. 7 days) then delete. In a compacted topic, Kafka will
periodically purge older messages for the same key, keeping the latest (and optionally tombstone deletes).
This means if you treat each message as a new state for a key, the topic always has the latest state (plus any
newer updates) – effectively an immutable changelog for each key that clients can replay to reconstruct
state. For example, consider a topic “UserAccounts” keyed by userId: if user updated their profile 5 times,
the log keeps all 5 events initially, but compaction might remove the first 4, keeping the latest profile
update event. Consumers can still process the entire log to build state (they would get the latest event for
each user eventually).

Log compaction is useful for systems that need a durable state store with streaming updates: a new
consumer can boot, consume the compacted topic from beginning to get the latest state of all keys, and
then continue consuming new changes (much like reading a snapshot + tailing a log). Kafka’s approach
provides an eventually consistent state: all changes are in the log, and ultimately each key’s final state
remains.

Blockchain-like ledgers: Another example of immutable ledger is blockchains or systems like Amazon
QLDB, which keep a cryptographically verifiable transaction log (though those aren’t mentioned explicitly in
the list, they share the ledger concept).

Benefits of immutable log store: - Auditability: You have a record of every change. In contrast, in a
mutable DB if a value changes from X to Y you lose X (unless you manually audit log it). - Event replay: In
event sourcing, you can spin up new services that replay the event log to build derived views or debug past
incidents. - Decoupling via events: With Kafka, multiple consumers can independently use the event
stream for different purposes (one for caching, one for analytics, etc.) without impacting the primary
system.

Trade-offs: - Storage: The log grows indefinitely (though compaction or archiving can mitigate this). You
need strategies for trimming or snapshotting if state gets large. - Complexity: Consumers must derive
current state from events (either on-the-fly or by maintaining a read model). Also, schema evolution of
events must be handled. - Latency: Getting current state might require processing a stream of events
(though snapshots or compacted topics help by allowing jump to latest state).

Example – EventStore usage: If recording an account ledger, you might append events:

Account 123:
Deposited $100 (eventID 1)
Withdrew $30 (eventID 2)
Deposited $50 (eventID 3)

11
The current balance isn’t stored directly; it’s computed by summing events = $120. But you keep the full
trail. If a mistake occurs, you don’t erase an event; you append a correcting event. This way the ledger is
immutable.

Example – Kafka log compaction: You have a topic “UserEmail” keyed by username, value = email address.
Initially:

Key: alice, Value: alice@[Link] (offset 0)

Key: bob, Value: bob@[Link] (offset 1)
Key: alice, Value: alice@[Link] (offset 2) <-- Alice updated email

With compaction, eventually the record at offset 0 might be removed, because there’s a newer value for key
alice . The log retains:

alice -> alice@[Link]

bob -> bob@[Link]

plus any new messages. Thus any consumer reading from start will see the latest for each user (and
possibly intermediate ones until compaction kicks in). This illustrates how compaction provides an up-to-
date store with history.

2. Core Distributed Systems Concepts

CAP Theorem (Consistency, Availability, Partition Tolerance)

The CAP theorem states that in any distributed system, you can only strongly satisfy at most two out of
three properties: Consistency, Availability, and Partition Tolerance 19 . Here’s a breakdown: -
Consistency (C): All nodes see the same data at the same time – a read receives the most recent write. In
CAP terms, this usually means linearizable consistency: every read reflects the result of the latest write (if
it succeeded). If you write something, any subsequent read (on any node) should return that value
(assuming no new writes). It implies a single, up-to-date view of the data. - Availability (A): Every request
gets a non-error response (it may not be the most recent data, but the system responds). In other words,
the system is operation-focused: it will return something even in the face of some failures. No node waits
indefinitely – if a node is up, it should service reads/writes. - Partition Tolerance (P): The system continues
to operate despite network partitions – communication breaks between nodes. Partitions are virtually
inevitable in distributed systems (e.g. a network link fails, nodes can’t talk). Partition tolerance means the
cluster can still function (perhaps with degraded consistency or availability) when messages are lost or
delayed between parts of the system.

The trade-off: When a network partition occurs (nodes can’t all talk), you have to choose: - If you prioritize
Consistency (CP system), you may have to sacrifice Availability. For instance, some nodes might reject
requests or become read-only to ensure no inconsistent data. E.g. a CP database will refuse writes on a
minority side of a partition to keep data consistent, effectively being unavailable on that side. - If you
prioritize Availability (AP system), you will serve requests on all nodes, but risk returning stale or diverging
data (thus sacrificing immediate consistency). E.g. writes go through even if nodes are partitioned, leading

12
to possible conflicts that are reconciled later (eventual consistency). - Partition Tolerance is generally non-
negotiable for distributed systems – we assume partitions can happen, so any realistic system has to handle
them (thus CAP is often reframed as, under a partition, choose C or A).

CA (consistent & available, not partition-tolerant) systems are only possible if you assume no partitions
(which is not realistic in distributed environments, except within a single machine cluster). A single-node
database can be CA (no partition to consider), but in a distributed context, CA means the system might
completely stop or lose guarantees if a partition happens 20 . So in practice, systems are categorized as CP
or AP primarily: - CP (Consistency + Partition tolerance): e.g. traditional distributed SQL databases, or
systems like MongoDB configured with majority writes. If a partition happens, part of the system will shut
off or error rather than risk inconsistency (thus compromising availability during the partition) 21 .
Example: a strongly consistent replicated database will block writes if replicas can’t reach majority. - AP
(Availability + Partition tolerance): e.g. Cassandra, DynamoDB – they choose to stay up and accept
requests despite partitions, at the cost that different nodes might briefly have different views of the data
(inconsistency) 22 23 . These systems rely on eventual consistency to reconcile after the fact.

Note: CAP is a simplification – it doesn’t capture nuances like consistency models (linearizable vs
sequential vs causal), nor the fact you can have tunable trade-offs. But it’s a useful mental model.

Example scenario: Imagine a distributed key-value store with two nodes (A and B). Under normal
conditions, both have the same data. If network between A and B breaks (partition): - A CP approach might
allow one node (say A) to become leader and continue (consistency with itself), but B will refuse requests
(unavailable) until partition heals and data syncs. - An AP approach would allow both A and B to continue
serving reads/writes. They will diverge if writes happen on both. When the partition heals, there’s a conflict
resolution phase (e.g. last-write-wins or merging). During the partition, clients might have gotten stale data
depending on which node they hit.

In summary, CAP reminds system designers to decide what happens during network failures: ensure
consistency (but some users get errors/timeouts) or ensure availability (but users might see stale/
conflicting data). Well-known CAP choices: - Zookeeper/etcd: CP (they will not serve reads from minority
partition; require quorum). - Cassandra/Dynamo: AP (they always allow writes somewhere and reconcile
later). - MongoDB default: CP (needs primary available; in a partition, secondary won’t accept writes). -
Redis Cluster: Configurable, but by default prioritizes availability (will serve from any available master).

ACID vs BASE (Transaction Guarantees)

These acronyms contrast two philosophies for managing data consistency in databases:

ACID (found in relational/SQL databases): - Atomicity: Transactions are all-or-nothing. If any part of the
transaction fails, the entire transaction is rolled back as if it never happened. - Consistency: A transaction
brings the database from one valid state to another, maintaining invariants (e.g. no constraint violations).
Essentially, database rules (constraints, triggers) are preserved. - Isolation: Concurrent transactions don’t
interfere; it appears as if transactions execute sequentially (to varying degrees depending on isolation
level). This prevents race conditions like dirty reads. - Durability: Once a transaction is committed, its
changes persist, even if the system crashes immediately after. Usually achieved by writing to disk/
transaction log before acknowledging commit.

13
ACID provides strong guarantees – useful in systems where correctness is crucial (bank transfers, etc.).
ACID-compliant databases ensure strong consistency and typically synchronous replication if distributed
(at least to a quorum) to meet durability.

BASE (associated with many NoSQL systems): Stands for Basically Available, Soft state, Eventually
consistent 24 : - Basically Available: The system guarantees availability (per CAP, it will always respond). It
might return slightly stale data, but the system remains operational. - Soft state: The state of the system
may be in flux even without new input, due to asynchronous propagation. There isn’t a strict point-in-time
consistency across nodes – data can be temporarily inconsistent. - Eventually consistent: Given enough
time (and no new updates), the system will converge to a consistent state. That is, replicas will eventually
become consistent if the system quiesces 25 . There’s no guarantee when, but the expectation is that
inconsistencies resolve after some delay.

BASE is more of a mindset than a strict definition – it’s used to describe databases that give up ACID’s
immediate consistency for scalability and performance. BASE databases allow temporary inconsistency
but aim to not permanently violate constraints (they rely on convergence). They often use optimistic
approaches: accept writes quickly (availability) and resolve conflicts or propagate changes in the
background.

Key differences: - Consistency vs Availability: ACID tends to go with consistency first (within a transaction
and across the system state). BASE goes with availability (system responds even if not all replicas have
agreed). - When consistency is achieved: ACID – immediately at transaction commit (strong consistency).
BASE – eventually, some time after the transaction, when all updates propagate. - Complexity moved: ACID
– the database ensures consistency so the application can rely on the DB to enforce constraints/ordering.
BASE – the application or background processes might have to handle inconsistencies, retries, conflict
resolution. - Examples: A typical SQL database is ACID (e.g. MySQL/InnoDB, PostgreSQL). A typical NoSQL
like Cassandra or Riak is BASE – they might allow conflicting writes and use “last write wins” or vector clocks
to reconcile, achieving eventual consistency. MongoDB is somewhere in between (it can be ACID on a single
document or multi-doc with transactions, but historically was known for eventual consistency in some
scenarios like replica lag). - Performance/scalability: BASE systems often scale out more easily and handle
high write loads by relaxing the need for synchronous coordination on each transaction. ACID systems can
be scaled (NewSQL, etc.), but it’s challenging because coordination (for consistency) often becomes the
bottleneck.

Use case choices: If you’re building a bank ledger, ACID is non-negotiable (you cannot allow any
inconsistency or lost update in transactions). If you’re building a social media feed, BASE is acceptable – if
two friends see slightly different like counts for a minute, it’s okay; what matters is the system is always up
and eventually shows the accurate count. Many internet services opt for BASE and incorporate techniques
to reach consistency (like background reconciliation, or simply tolerating slight staleness as humanly
unnoticeable). Remember the CAP tie-in: BASE tends to correspond with AP systems (available under
partition, eventual consistency), whereas ACID (especially full serializability) tends to require CP
(consistency, may sacrifice availability on partition or heavy contention).

14
Replication (Synchronous, Asynchronous, Quorum-Based)

Replication means maintaining multiple copies of data on different nodes for redundancy and scalability.
There are several approaches, each with trade-offs in consistency and performance:

• Synchronous replication: The leader/primary node waits for replicas to acknowledge the write
before confirming to the client 26 . This ensures replicas are up-to-date at commit time (strong
consistency across replicas). If one replica is down or slow, the write is delayed or fails. Synchronous
replication guarantees zero data loss if the primary fails (since at least one replica has the data).
However, it increases write latency (must wait for network/disk on replicas) and reduces availability (if
replicas can’t keep up or a quorum isn’t reached, the system might stall writes). For example, in
PostgreSQL you can configure a standby as synchronous – each transaction commit will wait until
that standby confirms it wrote the WAL record to disk.

• Asynchronous replication: The primary returns success to the client without waiting for replicas 27
28 . Replicas get updates after the fact (with some delay). This yields fast writes and high availability

(primary doesn’t block on replica status), but if the primary crashes before replicas get the latest
data, that data is lost (potential inconsistency). Most MySQL replicas, for instance, are async by
default – the master sends binlog events to slaves, but doesn’t wait. In the event of master failure,
recent transactions not yet replicated are gone (potentially violating durability). Asynchronous is
common when you want to scale reads (read replicas that lag slightly) or in multi-region replication
where synchronous would be too slow.

• Semi-synchronous: A middle ground (often one replica must ack, others can be async). E.g. master
waits for at least one replica to ack (to ensure one extra copy) but not all. This reduces risk of loss to
at most one copy failure. In practice, MySQL offers semi-sync plugin (master waits for one slave ack).

• Quorum-based replication (leaderless or consensus-based): This is used in systems like

Cassandra or Dynamo, and also in distributed consensus algorithms (Raft, etc.). Instead of a single
leader waiting or not waiting, any node can accept writes, and a write is considered successful when
a quorum of nodes have received it 29 . For example, out of 3 replicas, require 2 (quorum) to ack a
write (W=2), and perhaps 2 to respond to a read (R=2). If W + R > N (here 2+2>3), you get strong
consistency on reads (the read will see at least one copy that has the latest write) 29 . This is the
Dynamo/Cassandra tunable consistency model: you can pick W and R . Quorum consensus is a
balance: higher durability than pure async (because multiple nodes must get the data) and still
availability (doesn’t need all nodes like fully sync). If some nodes are down, as long as quorum can be
reached, operations continue. It’s a kind of synchrony that tolerates some failures.

• Leader-follower vs leaderless: In a leader-follower (master-slave) model, one node is authoritative

for writes (the leader) and replicates to followers. This is simpler to ensure ordering and consistency
(all writes go through one serial sequence). Leaderless (Dynamo style) means clients or coordinators
can write to multiple replicas directly. This requires conflict resolution if two writes happened
concurrently on different replicas (like using vector clocks or last-write-wins). Leaderless with
quorums avoids a single point of failure for writes, but complexity moves to resolving concurrent
updates.

15
Failure handling: In replication, consider how failover happens: - If a master fails in leader-based
replication, one of the replicas must take over (possibly via an election or configuration). There’s often a
brief unavailability during leader election or failover. Synchronous replication can guarantee the new leader
has all data; async means some data might be lost (called failover lag). - Consensus protocols (Paxos/Raft)
effectively handle replication with built-in leader election and require quorums to make decisions, so they
ensure CP semantics (no split-brain but maybe temporary unavailability if not enough nodes).

Consistency levels: Many systems let you choose read/write consistency: - Strong (read-from-leader or
quorum): read sees latest committed data (at some performance cost). - Eventual: read from any replica,
which may be stale (but lower latency). - Monotonic reads: ensure a given client’s reads don’t go backwards
in time. - Read-your-writes: ensure a client, after writing, sees its write on subsequent reads (could be
achieved by reading your primary or sticky session).

Example in Cassandra: replication factor N=3. If you write with [Link] (which
means W=2 out of 3 must ack) and read with QUORUM (R=2), you have strong consistency (assuming no
more than one replica fails). If you instead write with ANY (just one replica or even hinted handoff) and
read ONE, you get eventual consistency (fast but possibly stale).

MySQL example: Master -> Slave (async replication). If master goes down, you can promote slave, but any
transactions that were on master but not yet on slave are lost (unless using sync binlog + semi-sync). To
avoid that, frameworks like Galera Cluster use synchronous replication between nodes (at cost of latency).

Summary: Replication improves read scalability and fault tolerance, but introduces the challenge of
keeping copies in sync: - Synchronous -> strong consistency, but slower and can reduce availability (if any
replica unreachable, writes halt). - Async -> fast and available, but risk of replication lag. Clients reading
from secondaries might see old data, and failover can lose last transactions. - Quorum -> in between, you
can tune how many replicas must confirm. It provides flexibility (you can even choose strong or eventual
per operation). - Quorum reads/writes example: Suppose N=5. W=3, R=3 (3 acks to write, 3 to read) =>
strong consistency if that’s met. If two nodes are down, a write (3/5) still works and a read (3/5) still works; if
3 nodes down, can’t meet quorum so operations fail (system sacrifices availability beyond certain failure
threshold). - Some systems (like Riak) even let you set those values per request or per bucket.

Sharding/Partitioning (Range, Hash, Consistent Hashing, Geo-Based)

Sharding (or data partitioning) means splitting a dataset across multiple databases or servers, so each one
handles only a portion of the data. This allows horizontal scaling – queries can be parallelized and each
machine holds a subset (thus more total storage and throughput).

Common strategies: - Range Sharding: Partition by value ranges on a key. For example, users A–M on shard
1, N–Z on shard 2; or dates 2020 on shard1, 2021 on shard2, etc. 7 . This is intuitive and good for range
queries (you can direct a query to specific shard(s) if you know the range). However, data might be uneven –
one range could be much larger or “hotter” (e.g. last names starting with S more common, or time-based
partitions where recent data gets all traffic). It may require rebalancing if one range outgrows others. Also,
a query that spans ranges might need to query multiple shards.

• Hash Sharding: Compute a hash of a key and assign it to a shard by taking hash(key) mod N (for
N shards) 8 . This evenly distributes entries by key (assuming good hash and enough keys),

16
 avoiding hot spots from sorted order. It’s great for uniform load distribution. The downside: you
lose locality – e.g. user 1 and user 2 might be on totally different shards, so range queries or
scanning adjacent keys don’t work without querying all shards. Also if N (number of shards) changes,
many keys need to move (unless using a more flexible scheme like consistent hashing).

• Consistent Hashing: A form of hash partitioning that minimizes data movement when scaling
shards 10 . Instead of mod N, consistent hashing uses a ring of hashes: each shard is assigned one
or more positions on a hash circle; each data key is hashed and placed on the ring; it belongs to the
next shard clockwise. If a shard is added or removed, only keys in adjacent ranges on the ring move,
not all keys. This is used by distributed caches (like Memcached clients, Cassandra’s partitioner, etc.)
to allow dynamic scaling. Consistent hashing also handles non-uniform shard capacities by giving
heavier nodes more positions on the ring. It tends to distribute data evenly but some randomness
means you might get a tiny amount of range co-locality – usually though, range queries still require
scatter-gather. It shines when your primary operation is point lookups and you plan to add/remove
nodes.

• Geo-based / Directory-based (List) Partitioning: You define explicit rules mapping keys to shards
via some lookup or list 9 . A “directory” is essentially a table that says “this key or group of keys ->
that shard”. Geo-partitioning is a common case: for instance, you route users to the nearest region’s
database (all EU customers on EU shard). This can reduce latency and comply with data residency
but means each shard holds a region’s data (which might be imbalanced or have different usage
patterns). Directory-based can be very flexible (arbitrary mapping), but the mapping itself could be a
single point of failure or slow if it doesn’t reside in app memory. Often, directory mapping is used on
top of consistent hashing for fine adjustments or for certain special keys.

• Composite Sharding: Combining strategies, e.g. first split by region, then within each region’s data
do hash partitioning to multiple servers 30 . This can address multiple dimensions (e.g. ensure data
is local to region, and balanced within region).

Rebalancing: When a shard becomes too large or hot, you may need to split it (for range) or add capacity
(for hash/consistent). Range sharding might involve splitting one range into two (requiring updating routing
logic for that range). In hash sharding if you add a shard, naive mod N requires moving almost everything;
consistent hashing requires moving some portion (roughly keys * (1/N_new - 1/N_old)). Some systems use
virtual shards or buckets – e.g. have 100 fixed logical partitions and assign those to servers; to add a
server, reassign some partitions to it (like how HBase regions or DynamoDB partitions work internally). This
limits movement to partition units.

Routing and discovery: Clients or a proxy need to know which shard to query. Some approaches: - Encode
shard in the key (e.g. user IDs with a prefix or range mapping). - Use a routing service or proxy (like a
custom middleware or something like API Gateway or Service that hides sharding). - In application code:
using a consistent hashing library or formula.

Joins and multi-shard operations: Sharding complicates joins and transactions. A join of data from two
shards means either the application or a coordinating service must gather data from both and combine
(distributed join). Similarly, a transaction that updates data on multiple shards isn’t straightforward – it may
need two-phase commit or decompose into eventually consistent operations. That’s why many system
designs try to shard by user or tenant such that most operations stay within one shard.

17
Examples: - MongoDB supports sharding: you choose a shard key and it uses ranges by default (with an
architecture of config servers + mongos router). - Cassandra automatically partitions by hash of primary
key (its partitioner), and uses consistent hashing under the hood. - HDFS/HBase: HBase tables are range-
partitioned by row key into “regions”. As data grows, regions split. - ElasticSearch shards indices by hash of
document id (with fixed number of shards chosen at index creation). - RDBMS manual sharding: e.g.
sharding by user ID modulo N – the app or a proxy prepends which database to use (like user 123 goes to
DB3). Systems like Vitess (for MySQL) help manage such sharding with a routing layer.

Geo-partition example: A social network might shard user data by country, so most local traffic hits the
local DB. But if you have cross-country interactions, you either accept cross-shard operations or replicate
some data globally.

In summary, sharding is key to scaling write-heavy or data-heavy workloads beyond one machine’s limits.
Choosing the right strategy depends on data distribution and query patterns: - If you primarily do lookups
by a key, hashing that key is easiest for balance. - If range queries are important (e.g. time-series scans), use
range partitioning by time or an ordered key. - If you have clear segments (tenants, regions), directory or
key-based sharding can isolate them. - If you expect to add/remove capacity often, consistent hashing or a
fixed-bucket approach saves headache in moving data.

Consensus: Paxos, Raft, ZAB

In distributed systems, consensus algorithms allow a set of nodes to agree on a value or sequence of
values even with failures. This is crucial for implementing a single authoritative result (like a consistent
transaction log, leader election, or state machine replication). Consensus is famously solved by algorithms
like Paxos, Raft, and ZAB: - Paxos: A family of protocols (classic Paxos, Multi-Paxos) developed by Leslie
Lamport. It’s proven to reach consensus (one value chosen) as long as a majority of nodes are functioning
and communicating. Paxos is robust but considered complex to understand and implement. Multi-Paxos
essentially optimizes repeated Paxos rounds by electing a stable leader to order a sequence of values
(commands). Paxos underlies systems like Google Chubby lock service and some databases. It guarantees
safety (never divergent decisions) and liveness if network conditions eventually stabilize. But in practice,
Paxos requires 2f+1 nodes to tolerate f failures, and if the leader fails, a new leader election (another Paxos
round) occurs.

• Raft: A consensus algorithm developed in 2013 with the goal of being easier to understand than
Paxos. Functionally, it solves the same problem as Multi-Paxos (log replication with a leader). Raft
explicitly codifies leader election, log replication, and safety. In Raft, one leader is elected (via
randomized timeouts; whoever times out first starts an election and collects votes). The leader
appends log entries and replicates to followers; followers ack them (similar to a synchronous
replication quorum). If the leader fails, a new election happens. Raft ensures that no two leaders
can commit conflicting logs (through its voting and log matching rules). It’s become popular in
implementations – e.g. etcd and Consul (key-value stores for configs in systems like Kubernetes and
HashiCorp stack) use Raft. Raft is often chosen for its clarity and has open-source libraries.

• ZAB (ZooKeeper Atomic Broadcast): This is the protocol used in Apache ZooKeeper (a coordination
service). ZAB is tailored for primary-backup systems with crash recovery. It has two phases: leader
election, then broadcast. It guarantees a total order broadcast of updates from a leader to
followers. If the leader dies, a new leader is elected that takes over broadcasting from the last

18
 consistent point. ZooKeeper uses this to provide a strongly consistent view (ZooKeeper’s guarantees:
linearizable writes, and reads from the quorum reflect latest writes if SYNC level, etc.). ZAB differs
slightly in how it handles recovery (it must synchronize state with followers on leader change). It’s
conceptually similar to Raft in using a leader to order updates.

All these algorithms require a majority (quorum) of nodes to make progress (they are CP in CAP sense). For
example, in a 5-node Raft cluster, at least 3 must agree to commit an entry. If too many nodes fail or there’s
a total partition split (no majority connected), the cluster can’t make decisions (to preserve safety).

Leader election: - Paxos doesn’t have a built-in leader concept, but Multi-Paxos optimizes by using a leader
(the node that continues to propose in successive instances). - Raft explicitly has one leader at a time. Only
the leader can propose log entries; others are followers. If followers don’t hear from leader (heartbeat) for a
timeout, they can start election. - ZAB also has a single leader that serializes updates.

Why consensus is hard: It must tolerate node crashes and message delays/reorderings yet avoid the
system ever committing two different values for the same slot (consistency) and still continue to make
progress when possible (availability in normal conditions). FLP impossibility results say you can’t guarantee
progress in an asynchronous network with failures, but these algorithms ensure safety and use timeouts
and assumptions for liveness.

Real-world usage: - ZooKeeper (which uses ZAB) is used for distributed coordination, naming,
configuration. Many systems use it for leader election (e.g. HBase masters coordinate via ZooKeeper). - etcd
(Raft) is core to Kubernetes for storing cluster state (leaders ensure updates to cluster state are consistent).
- Distributed SQL databases (Spanner, Yugabyte, CockroachDB) use consensus (often Paxos/Raft) to
replicate data shards. E.g. each data range in Cockroach is a Raft group with leader, so writes to that range
go through Raft consensus among replicas. - Kafka uses its own consensus-ish protocol for the controller
and uses ZooKeeper (in older versions; newer KRaft uses Raft). - Azure CosmosDB uses a Paxos-based
protocol for multi-region consistency (TLA+ specs were published). - Blockchain algorithms are a form of
consensus too (but usually under different trust assumptions, e.g. PBFT, proof-of-work, etc., beyond CAP-
style fail-stop model).

Paxos vs Raft differences (high-level): Both ultimately ensure a leader orders log entries. Raft’s novelty
was splitting the consensus problem to subproblems (leader election, log sync) in a way easier to teach. Raft
also ensures a strong leader: the leader’s log is always “most up-to-date” (due to election rules), whereas
Paxos doesn’t require that property for a leader (any candidate with a majority can be leader even if its log
is behind, but then it recovers missing entries via learning phase). The end results are similar: a consistent
replicated log.

ZAB specifics: It’s designed that during recovery (after a leader crash), it will not acknowledge new
transactions until a new leader has synced with a majority to the last transaction of the previous leader
(thus ensuring no gap). It has an epoch (ZXID) similar to Raft’s term and uses that to choose leader (highest
ZXID, etc.).

In summary, consensus algorithms are the backbone of fault-tolerant state machine replication: they
keep multiple nodes in sync so that even if some fail, the system as a whole behaves like a single reliable
node. They typically assume fail-stop (crash) failures (not malicious). Achieving consensus has a cost: e.g. it

19
requires multiple network round-trips and acknowledgments (higher latency) and more writes (to multiple
replicas). But for critical data like metadata, configs, or small but important state, it’s worth it.

Leader Election (ZooKeeper, Raft, Kubernetes)

Leader election is the process by which distributed systems select one node as the coordinator or primary
among peers. It often goes hand-in-hand with consensus but can sometimes be simpler if strong
consistency on data is not required.

In consensus protocols: Leader election is built-in (e.g. Raft as mentioned uses randomized timeouts;
Paxos/Multi-Paxos anoints a leader (distinguished proposer) via a phase 1 of Paxos; ZAB elects leader with
highest last transaction id). The leader then orchestrates things (like log replication). This ensures there’s a
single source of truth at a time, avoiding split-brain.

Using ZooKeeper for leader election: ZooKeeper is often used as a generic coordination service for leader
election. A common pattern: - All nodes in a cluster attempt to create an ephemeral znode (a special
ZooKeeper node that disappears if the session closes) under a known path, e.g. /app/leader . Only one
will succeed (ZooKeeper create is atomic). The one who succeeds becomes the leader. - Alternatively, a
better pattern: use ephemeral sequential znodes. All candidates create /app/leader/n_ with sequence
flag. ZooKeeper appends a sequence number to each. The node with the smallest sequence is the leader.
Others watch the next-smallest node; when the leader goes away (its znode is gone), the next in line detects
and becomes new leader. This avoids thundering herd on a single node watch and provides an ordered
queue of potential leaders. - ZooKeeper’s consistency (itself running ZAB consensus) ensures only one
leader is chosen at a time and all participants see a consistent view of who it is.

This approach is used in systems like Hadoop NameNode HA (active and standby name nodes coordinate
via ZooKeeper to decide which is active), HBase masters, etc. Essentially, ZooKeeper provides an out-of-the-
box election service.

Kubernetes leader election: In Kubernetes, many controllers/operators run with multiple replicas for high
availability, but only one should act as the leader at a time (others standby). They often use a built-in
feature: creating a Lease object (Coordination API) in Kubernetes. The controllers race to acquire the lease
(or update a field in it). Kubernetes client library implements a leader election by repeatedly trying to
update a lock object’s annotation with their identity; one wins and others wait, checking if the lock expires.
This is effectively leader election using the Kubernetes API (which internally is consistent via etcd/Raft).
Previously people also used ConfigMaps or Endpoints as lock objects.

Application-level leader election: You might also see simpler approaches: - Use a distributed lock with a
timeout – e.g. in Redis, use SETNX to claim a key like “lock:leader” with an expiry. If successful, you’re leader.
If not, wait and retry. Needs care (e.g. clock issues, renewal). - Use a database: e.g. an applications table
with a “leader” row, attempt to update it with your instance ID if currently null, using a WHERE clause to
only update if previous leader timestamp is stale. - These are more ad-hoc and less robust than something
like ZooKeeper which is built for it, but can work for simpler scenarios.

Leader responsibilities: Once elected, a leader might perform certain tasks exclusively: - For example, in a
primary-backup DB cluster, the leader handles all writes. - In a work queue system, the leader could assign
tasks to others. - In a cluster scheduling system (like one instance of your app should do cron jobs), the

20
leader does them. - In cluster management, the leader might monitor members and make decisions (like in
Kafka, the controller node is chosen via ZooKeeper; it manages partition leader assignments).

Handling leader failures: Usually a leader will renew its status periodically (heartbeat). If others don’t see
that (e.g. ephemeral znode gone, or lock expired), they trigger a new election. There is typically a short
interval where no leader is present (failover gap). Systems try to minimize this.

Raft leader elections occur via timeouts (if follower doesn’t hear from leader in, say, 150ms–300ms
randomized, it becomes candidate and solicits votes). Paxos doesn’t have a strict leader, but an
implementation might have a stable leader optimization.

Split-brain prevention: Leader election must ensure two leaders can’t think they are active at once
(especially in network partition). Usually requiring a quorum of nodes to agree on leader prevents split
brain. E.g. if cluster splits, only the side with majority can elect leader, the minority stands down. This is why
an odd number of nodes is often used (to avoid ties). In systems like ZooKeeper, if a minority partition is
isolated, those nodes will lose connection to ZK and thus drop any locks (stop being leader).

Example: HADR (High Availability) scenario: Suppose you have two nodes, A and B, and you use a third
node as a ZooKeeper or coordination. If A is leader and partition occurs between them, B can’t contact ZK
either (if ZK on A’s side) so B won’t assume leadership incorrectly. If A fully crashes, B will see that in ZK and
then obtain leadership.

In summary, leader election is all about choosing a single coordinator in a distributed environment and
re-electing a new one quickly if the leader fails, without ever having two acting leaders at the same time.
Tools like ZooKeeper greatly simplify it by providing a consistent view of membership and locks.

Eventual Consistency vs Strong Consistency

These terms describe the continuum of consistency models in distributed systems:

Strong Consistency: After an update is applied, every subsequent read (by any client, on any replica) will
see that update. In the strongest form (linearizability), it appears as if there is a single copy of the data and
every operation is instantaneous at some point in time. This is what you get in a single-node database or a
distributed system that sacrifices availability to preserve a single up-to-date state (e.g. consensus-based
replication). If you do a write and then immediately a read (to any replica), you will get your write (if it
succeeded). In other words, the system behaves like a single consistent system. Transactions in relational
DBs or strongly consistent key-value stores (like etcd) provide this.

Eventual Consistency: The system doesn’t guarantee immediate consistency across replicas, but if no new
updates occur, eventually all replicas will converge to the last updated value 31 . Reads might return stale
data in the interim. There’s no bound on how long “eventually” is, but practical systems aim for it to be short
(milliseconds or seconds). This model is used by many AP systems (Dynamo-style databases, DNS, caches).
It’s acceptable when the application can tolerate reading slightly old data or where data is updated in one
place and slight propagation delay doesn’t break things.

Between these extremes are models like read-your-writes, monotonic reads, causal consistency, etc.,
but eventual vs strong is a fundamental dichotomy: - Under strong consistency, if you write X=5 and get an

21
ACK, any read after will see X=5. - Under eventual consistency, after writing X=5 on one replica, another
replica might still return X=4 for a while until it gets the update. Eventually, it will see 5 once updates
propagate.

How eventual consistency is achieved: typically via async replication and background synchronization.
For example, in Dynamo-style, each replica that got the write will gossip it to others. If a read hits a replica
that hasn’t gotten the update, it returns stale data. But if you were to read after enough time or from
multiple replicas, you’d get the latest. Usually, systems incorporate merging or conflict resolution to
reconcile divergent updates (like last-write-wins timestamp or custom merge function). Eventual
consistency doesn’t guarantee how conflicts are resolved, just that if no further writes, eventually one value
will be agreed on.

Example: DNS is a classic eventually consistent system. You update an IP for a domain; due to cached DNS
records (with TTL), some clients around the world will still see the old IP until their cache expires. Eventually
all caches clear and everyone sees the new IP. During propagation, inconsistency exists (two clients may get
different answers). But eventually consistency is achieved (everyone converges to new IP).

Another example: Shopping cart microservice – say it uses eventual consistency between service replicas.
If you add an item to cart and immediately refresh on another device, you might not see it for a moment.
Soon though, the cart update replicates and it appears.

Strong consistency costs: requires coordination (like a transaction or replication ack). If the cluster is
partitioned or some nodes slow, it may have to stall to preserve consistency (hence CAP trade-off). Latency
is typically higher for writes (must replicate and confirm) and possibly for reads if they must check with a
primary or quorum.

Tunable consistency systems: Cassandra can be configured from eventual (read ONE, write ONE) to strong
(read+write quorum as discussed). Many cloud databases like Cosmos DB offer multiple consistency levels
(strong, bounded staleness, session, eventual etc.). “Session consistency” (read-your-writes) is a common
compromise: each user sees their own writes immediately (so from their perspective it’s consistent), but
different users might see each other’s with lag.

Monotonic reads: ensures if you saw a value once, you won’t later see an older value. Eventual consistency
alone doesn’t promise that without additional conditions – e.g. if you switch between two replicas, you
could read new data then stale from the other. Often frameworks try to give monotonic reads at least per
client.

Causal consistency: (one of strongest under eventual umbrella) if operation A causally precedes B, then
any process that sees B will also see A. Hard to implement globally without vector clocks, etc. Rare in
mainstream systems, but some distributed stores like Cosmos have a “consistent prefix” etc.

When eventual is fine: In systems where availability and partition tolerance are more important, or the
data updates are not critical to be immediately current. Social feeds, cached data, product catalogs (if
slightly stale for a bit, not the end of world), etc.

When strong is needed: Financial data (account balances), inventory count if overselling must be
prevented, etc., or when complexity of handling inconsistency in app is too high.

22
Consistency in practice in big systems: Many large systems combine both: e.g. strongly consistent for
crucial metadata or small core (like user account record), and eventually consistent for derived or less
critical data (like analytics, recommendations).

Wrap up analogy: Think of eventual consistency like sending out an update via snail mail to multiple offices
– eventually everyone updates their ledger, but in the meantime their ledgers differ. Strong consistency is
like a conference call – everyone hears the update at once before moving on. The former is more resilient to
a slow office (they’ll update whenever mail arrives, others continue working); the latter ensures no one is
out-of-sync but if someone’s phone is down, the meeting halts.

Idempotency (Retries & Deduplication)

Idempotency means performing an operation multiple times has the same effect as doing it once 32 . In
distributed systems, this is crucial for safely retrying operations without unintended side effects.

Why needed: Networks fail; clients or load balancers time out; servers crash mid-process. To improve
reliability, callers often retry requests. But what if the original actually succeeded on the server, and only
the acknowledgment was lost? A naive retry could perform the action twice. Idempotent operations guard
against that.

Examples of idempotent operations: - Setting a value: e.g. PUT /resource/123 { "status":

"shipped" } – you can send this request multiple times; the state ends as "shipped" once. It doesn’t
matter if it was already shipped. - Deleting a resource: DELETE /item/999 – deleting an already-deleted
item often returns a no-op (or 404). Deleting twice isn’t worse than deleting once. - Retrieving data: GETs
are inherently idempotent (and side-effect-free by spec). - Creating with a fixed identifier: e.g. if the client
chooses an ID or an idempotency token. If the same creation is submitted twice, the second can be
recognized as a duplicate and ignored.

Non-idempotent example: POST /order which charges a credit card and returns an order id. If the
client times out after clicking “Pay” and retries, two charges could occur if not protected, because each POST
might create a new order. Or POST /incrementCounter – calling it twice incorrectly increments twice.

Techniques to achieve idempotency: - Idempotency keys/tokens: The client generates a unique ID for
the operation (perhaps a UUID). On the server side, if a request with that idempotency key was already
processed, the server returns the same result and does not perform the action again 33 . This requires the
server to store history of processed keys for some time (like a cache of recent idempotency keys). - For
example, Stripe API uses an-Idempotency-Key header for safely retrying charges. If the client sends the
same key, Stripe knows not to duplicate the charge. - Natural idempotent endpoints: Use PUT instead of
POST where possible. PUT is defined to be idempotent (you are replacing or creating a resource at a URI).
E.g. PUT /users/alice with a full user record – send it 3 times, you still have Alice with that data (not 3
Alices). - At-least-once message processing: If a consumer gets the same message twice (possible in e.g.
Kafka if the consumer commits offset after processing or in SQS if a message isn’t acked in time window),
the consumer logic should handle it. Often this involves deduplicating by a unique message ID. For
example, if you have a “send email” message with ID 101 and you receive it, you check if you’ve processed
ID 101 before (store seen IDs or their effects) – if yes, skip sending again. - Database UPSERT or unique
constraints: If two duplicate writes come, having a unique key ensures the second fails or has no effect. For
instance, ensuring an order ID or payment token is unique in DB can avoid double insertion. Or use UPSERT

23
(update if exists) semantics. - Designing operations that are inherently idempotent: e.g. instead of “add
10 to balance” (non-idempotent if repeated), use “set balance to X” or “add operation identified by Y” where
Y is unique so it can be applied once.

Retries with exponential backoff and jitter (discussed later in Failure Handling) tie in: when you retry,
idempotency ensures that those retries won’t mess things up. You still limit retries to not spam indefinitely,
but at least you aren’t afraid to try a few times.

Idempotent HTTP methods: GET, PUT, DELETE, HEAD, OPTIONS, TRACE are supposed to be idempotent
(spec-wise). POST is not. But in practice, one can make POST calls idempotent via keys if designing an API.

Deduplication in messaging systems: - Kafka: has an “exactly once” feature where producers assign
sequence numbers per partition and brokers deduplicate if enabled (idempotent producer). Also consumers
can use transactional reads. But simpler: track message IDs. - SQS: offers deduplication for FIFO queues
using a MessageDeduplicationId (so you can resend a message and SQS ensures within a 5-minute window
duplicates are dropped). - In databases: a classic pattern is adding an idempotency_id column on a
table. For instance, if processing payments, include a unique transaction ID from the client or upstream; if
the same comes again, don’t insert a new row (or ignore the duplicate). Often implemented via unique
index so second insert fails (caught and treated as duplicate success).

When idempotency is needed: especially in distributed transactions or any multi-step processes that can
partially fail. If you can safely restart an operation, systems become much more robust. For example,
microservice A calls B to do something. If A times out, it can call B again – if B’s operation is idempotent, it
won’t create inconsistency by doing it twice.

Example: In an e-commerce, when an order is placed, multiple services might be notified (inventory,
payment, confirmation email). If the message to email service times out and gets resent, you don’t want
two emails. Having a message ID or using the order ID as key ensures the email service sends one email per
order.

Another example: A client calls “create user” and gets a network error, not sure if user was created. If the
API is idempotent (say the client used a unique username or an idempotency key), they can call again – if
user was created the first time, second call sees conflict (or just returns the same user record and 200 OK),
not create a duplicate user.

In summary, idempotency is a fundamental principle to make distributed actions safe to retry. Without it,
systems often either don’t retry (leading to potential failure if one call fails), or they retry and risk side
effects (like duplicate operations). Idempotent design allows at-least-once delivery and processing to
effectively yield exactly-once effect. It pushes complexity to deduplication either on server logic or using
unique tokens.

Backpressure & Flow Control (Streaming, Queues)

Backpressure is a mechanism to prevent overwhelming a system when producers (senders) produce faster
than consumers (receivers) can handle. In other words, it’s flow control: ensuring that data flows at a rate
the system can sustain, by signaling upstream to slow down or by buffering with limits.

24
In a pipeline of components (like in streaming data processing or network traffic): - Without backpressure:
If producer goes full speed and consumer is slow, queues grow, memory fills, latency increases, possibly
leading to crashes (or out-of-memory) or message loss. - With backpressure: The system applies brakes on
the producer or intermediate steps to match the slowest component’s pace.

Examples: - TCP flow control: The TCP protocol has built-in backpressure via the receiver’s window size. If
receiver’s buffer is full, it advertises a zero window, telling sender to pause sending. This prevents packet
loss and ensures the sender doesn’t overwhelm the receiver. - Reactive Streams (like RxJS, Reactor): They
allow a consumer to request a certain number of items from the publisher (this is pull-based backpressure).
The publisher won’t send more than requested. - Message queues: Some queues have max lengths. If the
consumer can’t catch up and the queue is full, producers might be blocked or new messages dropped or
sent to DLQ (like a leaky bucket approach). - Akka Streams: Use backpressure signals – each stage emits
demand upstream when it’s ready for more.

Backpressure strategies: - Blocking / synchronous: The producer blocks (waits) when the consumer is not
ready. E.g. a bounded queue with put() will block if full. - Dropping / shedding load: If queue is full, new
messages are dropped (and maybe an error is logged or a special counter incremented). This sacrifices data
for system survival – e.g. a monitoring system might drop some metrics if overwhelmed. - Buffering with
limits: A moderate-sized buffer can absorb small mismatches in rate, smoothing bursts. But it must have an
upper bound or eventually memory issues. - Throttle / slow down: Tell producer to slow generation rate.
For instance, a server might stop reading from a socket if its outgoing processing is backed up, which
implicitly slows the sender via TCP’s mechanism. - Windowed or token-based: Token bucket (discussed in
rate limiting) can be seen as a form of controlling throughput – not exactly backpressure but to moderate
sending rate.

Backpressure in streaming pipelines: Imagine a pipeline: Source -> Step1 -> Step2 -> Sink. If Sink is slow
(maybe writing to DB), Step2’s outputs will queue up if Step1 keeps feeding. With reactive backpressure,
Sink signals “I can take 1 at a time” so Step2 only pulls one when Sink ready, and Step1 only pulls from
Source when Step2 ready. This way, each stage processes at the pace of the slowest.

Queues and consumers: - In something like RabbitMQ, if consumers can’t keep up, the queue length
grows. If unbounded, memory grows too. One might apply a max length policy on the queue (discard
oldest messages or reject producers when full). - Or use publish rate limiting when queue backlog exceeds
a threshold (some brokers allow throttling producers or using credit-based flow control).

Backpressure vs load shedding: Backpressure ideally prevents overload by slowing input. Load shedding
(dropping) is a last resort when you prefer to lose some data than crash or lag infinitely.

Monitoring backpressure: Systems often monitor queue lengths, consumer lag (like Kafka consumer lag =
difference between produced and consumed offset), etc., to detect backpressure issues. If a metric shows
growing backlog, it’s a sign the consumer is too slow or stuck.

Adaptive throttling: In some systems, backpressure triggers a dynamic adjustment, e.g. if queue length >
X, throttle input 50%. Microservices might coordinate: if a downstream returns a “slow down” response or
uses HTTP 429, the upstream can pause or decrease requests.

25
Scenario example: A web server writing to a database – if DB is slow, one could implement backpressure by
having a fixed-size connection pool or semaphore. If all DB connections are busy, the web handler waits
(backpressure to incoming HTTP). If it can’t get a connection within a timeout, perhaps it rejects the request
(shed load). This prevents just queuing unlimited requests and timing everything out.

Another example: Kafka producers can configure [Link] requests. If brokers aren’t
acknowledging because brokers are slow, the producer library will block or buffer up to a limit, then either
block further sends or throw exceptions. This backpressures the application sending messages.

Without backpressure – danger: Known as a "producer overwhelm" or in streaming, a "fast producer,

slow consumer" problem, can lead to phenomena like out-of-memory, high GC, etc. This can cascade: if
one component thrashes, others might misbehave (e.g. if they rely on timely ack). It can even collapse a
system (like an overloaded queue might crash and lose all messages).

Reactive manifestos highlight backpressure as key for resilience in streaming. Some older systems like
early [Link] streams didn’t handle backpressure well by default, leading to memory bloat if a consumer
was slow (though Node streams introduced a pause() and resume() later to signal backpressure to
source).

Backpressure vs Rate Limiting: They are related – rate limiting (token bucket/leaky bucket in section 5)
often is implemented to prevent external clients from overwhelming a service. Backpressure is more
internal: once inside the system, between components or microservices, how we avoid internal overload by
propagating the "please slow down" signal upstream. Rate limit is a blunt front-door control (stop letting so
much in), while backpressure is dynamic and cooperative.

Flow control in distributed pipelines: Some distributed stream processors (Spark Streaming, Flink, etc.)
implement flow control to avoid source overwhelming (like Flink can slow the ingestion if sinks are
backlogged). Others rely on an underlying messaging system that buffers (Kafka backpressure is essentially
retention and consumer lag metrics).

In summary, backpressure is critical for stable systems – it matches throughput between producers and
consumers to the system’s capacity. It's far better to throttle input or queue moderately than to just let
things pile up until failure. A well-designed streaming/queuing system will incorporate backpressure signals
or controls. When designing microservice interactions, considering idempotency and retries is half the
story; the other half is ensuring that if one service is slower, others don’t drown it in requests – often
implemented via circuit breakers or client-side rate limiting, which ties in (discussed later in fault
tolerance).

26
3. Caching & Performance Techniques

Cache Types: Client-side, CDN, Application-level, Database Query Cache

Caching means storing frequently accessed data in a faster storage (memory typically) closer to the
consumer, to reduce repeated expensive operations. There are different layers/types of caches:

• Client-side cache: This is data cached on the end-user’s device. In web context, the browser cache is
a prime example – it stores images, scripts, and responses (per HTTP caching headers) so if the user
revisits a page or navigates, it can load resources from local cache instead of making a new request.
Also, single-page apps might cache API responses in memory or localStorage. Desktop or mobile
apps similarly may cache server data on disk (for offline use or performance). Client-side caching
reduces server load and network calls. It’s typically limited by the fact that it’s per user (doesn’t help
across users) and you trust the client to eventually refresh data when needed (controlled by TTLs or
cache invalidation hints).

• CDN/Edge cache: A Content Delivery Network is a distributed network of servers (edge nodes)
around the world that cache content closer to users. Static assets (images, CSS, JS, videos) and even
whole HTML pages (if cacheable) are served from CDN nodes after the first request populates them.
This massively reduces latency for users (edge node likely near them) and offloads traffic from the
origin server. CDNs follow HTTP caching headers (like Cache-Control max-age). They often
operate as reverse proxies: user requests go to CDN node; if not cached, the node fetches from
origin, then caches it for subsequent users. Edge caches can also be custom-built (like regional
caches your own servers). CDNs typically are good for static or publicly cacheable content. They can
also handle cache invalidation (purge when content updates).

• Application-level cache: This refers to caches in the app/mid-tier layer. Often using in-memory
stores like Redis or Memcached as a shared cache between application servers, or even in-process
caches (like using an LRU map inside the app). Application caches store expensive query results,
computations, or session data to avoid recomputation or database hits on each request. For
example, an app might cache user profiles in memory so that repeated lookups don’t query the DB
each time. Memcached is an in-memory key-value cache often used to store small chunks of data
(strings, objects) identified by keys. Redis can serve similarly (plus it has more features and data
structures). These caches are usually explicitly managed by the application: it decides when to put or
evict (or sets TTL). They can be cluster-wide (if using a central cache service) or per-node (in-process
caches which might lead to cache coherence issues if not shared).

• Database query cache: Some databases provide caching of query results. For instance, MySQL had
a query cache (now removed in newer versions due to complexity) that would store the result of a
SELECT query and if the same query (literal string) came again and the underlying table hadn’t
changed, it would return the cached result. Postgres doesn’t have a query cache by default, but the
OS filesystem cache serves a similar role by caching table pages in memory (so repeated queries
fetch from memory rather than disk). There are also query caches at application side: an app may
memoize certain queries. Additionally, systems like ORMs sometimes have second-level caches to
store entity data to avoid hitting the DB for the same object repeatedly. A DB query cache is
invalidated whenever data changes (to avoid stale reads). Application-level caches often effectively
serve as query caches when used to store DB results.

27
Comparison: - Client-side and CDN caches reduce network latency and offload traffic before it hits your
servers. They are mostly for static or rarely-changing content and are invalidated by content versioning or
short TTLs. - Application and DB caches reduce the load on the database or expensive backends by storing
results in faster storage (memory). They need careful invalidation or TTL strategies to avoid stale data if the
underlying data changes.

Cache hierarchy example (web app): A user requests a page: 1. Browser checks its cache (client-side) – if
fresh, uses it (fastest). 2. If miss, request goes to CDN – CDN might have the content cached from a previous
user (if public cacheable). If hit, CDN serves it (fast, from edge). 3. If CDN miss, goes to your application. The
app might query data from DB – but first it checks Redis cache for needed data (app-level cache). If hit, gets
data without querying DB. 4. If app-level miss, app queries the DB. The DB might retrieve from disk or its
buffer cache (OS cache). If it’s not in memory, goes to disk (slowest path). After getting data, app might
store the result in Redis for next time. 5. Response goes back, CDN might store it (if configured), browser
might store it per headers for user’s next time.

Each layer adds complexity but can drastically improve performance and scalability when used
appropriately.

Eviction Policies: LRU, LFU, FIFO, TTL-based

Caches have limited space, so they need policies to decide which items to evict (remove) when the cache is
full or entries expire. Common eviction policies: - LRU (Least Recently Used): Evict the item that hasn’t
been accessed in the longest time 34 . This works on the principle that recently used items are more likely
to be used again (temporal locality). LRU is simple and effective in many scenarios. E.g. an LRU cache of size
100 will throw out the item that was last accessed the furthest in the past when a new item comes in. Many
in-memory caches (like Guava cache in Java, Memcached roughly by slabs, Redis has an LRU option) use LRU
or approximations of it. - LFU (Least Frequently Used): Evict the item with the smallest access count (the
item that has been used the least often). This policy keeps frequently used items even if they haven’t been
used super recently, which can be better for items that are consistently popular (freq > recent). True LFU can
be harder to maintain because you need to keep frequency counts, and those counts might need decay (to
avoid items that were hot long ago still sticking around). Some caches implement an approximate LFU or a
combination (like Redis has an LFU mode where it keeps a counter per item with logarithmic decay over
time). - FIFO (First In First Out): Evict the oldest item (by insertion time) first, without regard to how often
or recently it was accessed. This is simple but often suboptimal because it doesn’t consider usage – a data
item could be added long ago but still be hot. - Random: (not listed, but sometimes used) – evict a random
item. Surprisingly, random eviction can perform okay in certain scenarios and is very simple to implement/
distribute, but LRU tends to outperform it when access patterns have locality. - TTL-based (Time-to-live):
Each item has an expiration time (TTL). When that time passes, the item is considered expired and can be
evicted (either actively or lazily on next access). TTL ensures that data doesn’t become too stale. It’s often
combined with other policies: e.g. Memcached uses TTLs per entry, and when memory is full it evicts the
oldest (LRU) among expired entries first, then among all if none expired. TTL ensures refresh of data after a
certain period even if not evicted by usage policy. - Adaptive or segmented policies: e.g. ARC (Adaptive
Replacement Cache), which tracks both recent and frequent items lists to better handle certain patterns,
or 2Q. These try to get the best of LRU and LFU. ARC can outperform LRU/LFU on certain workloads (it’s
used in some databases for buffer caches). - MRU (Least Recently Used’s opposite) is rarely used as a
primary policy but can be combined: e.g. an in-memory DB might evict most recently used if you suspect
a cyclic pattern (not common).

28
Why choose one vs another: - LRU is great for recency-based locality. Many workloads exhibit that (if you
accessed something recently, you might access it again soon – e.g. a user reloading their feed). - LFU is
good when certain items are extremely popular overall (like a celebrity profile might be fetched often – you
want it cached even if a bit old). - However, pure LFU can hold onto items that were popular historically but
no longer are (unless you decay counts). - FIFO might be used in special cases like streaming where you just
need a moving window of data. But generally, it doesn’t adapt to pattern changes. - TTL is often used
regardless of above, to ensure eventual refresh. E.g. cache user data with TTL 5 minutes – even if LRU would
keep it for an hour due to use, TTL forces refresh every 5 min to get updates from source (when strong
consistency is not needed but eventual update is). - Memory vs staleness trade-off: Without TTL, caches can
hold very stale data if underlying DB updated it unbeknownst to cache – that’s why sometimes TTL is
applied to cap staleness. Alternatively, applications do explicit invalidation on data changes (harder in
distributed systems).

Example: Redis eviction modes: Redis allows setting maxmemory and an eviction policy: volatile-lru
(LRU only among keys with TTL), allkeys-lru (LRU among all keys), allkeys-random , volatile-
TTL (evict the soonest-to-expire key), or noeviction (error on writes when full). This shows TTL
interplay: volatile-lru only evicts keys that had an explicit TTL set, which often means “less important”
or temporary data.

Cache hit vs miss effect: Good eviction policy maximizes hit ratio. E.g. in a web cache, LRU often works well
(users tend to revisit some set of pages). In a database buffer pool, access patterns might be more complex
(thus databases often implement sophisticated policies like ARC).

Pitfall – cache stampede: If everything TTLs at once (like all keys expire together), can cause many misses –
we’ll discuss under stampede but note TTL is usually staggered or with jitter to avoid synchronized expiry
(staggered expiration technique 34 ).

Write Strategies: Write-Through, Write-Around, Write-Back

These refer to how writes interact with the cache and the backing store (database):

• Write-Through: On data modification, write is applied to the cache and to the database (backing
store) at the same time (usually synchronously). The cache remains always up-to-date with the
source. Clients typically write to the cache (the cache then writes to DB, or application writes both).
For reads: data is in cache (fast). The benefit is simplicity in consistency – data in cache is never stale
because every write goes through cache and into DB. Downside: write latency includes writing to
cache and DB (slower than writing to DB alone), and the cache has to handle write load. Also, if the
cache is distributed, two writes (cache & DB) could increase overall system complexity. Example:
using Redis as a front for a DB – on an update, you SET in Redis and UPDATE the DB in one
transaction or step.

• Write-Around: The cache is bypassed on writes – you write directly to the database, and do not
update the cache. The idea is to avoid caching data that may not be read soon (maybe it's new or
seldom used). When a subsequent read happens, it will miss in cache (since not updated) and fetch
from DB, then cache it. Write-around can prevent cache churn from writes that aren’t read (especially
if you have heavy write workload but moderate reads). But downside: a freshly written data might be
immediately requested, and because it wasn’t put in cache, the first read is a miss and goes to DB (so

29
 higher read latency on first access). Also, if there's frequent writes on same data, the cache might
never hold it (keeps getting invalidated or bypassed), meaning reads always miss. Write-around is
simpler and often combined with eviction strategy: e.g. an item evicted from cache will be written to
DB (if changed) but on next read will be loaded.

• Write-Back (also called Write-Behind): Writes are made only to the cache, and considered
successful once in cache; the cache later asynchronously propagates changes to the database
(maybe batching multiple writes together). This can significantly speed up writes (low latency to ack,
since cache, often memory, is fast) and reduce DB load (multiple updates can be coalesced or written
once). However, it introduces risk: data in cache is now the source of truth until flushed. If the cache
node dies before flushing, you lose that write (unless the cache has its own persistence or replication
– e.g. a distributed cache can replicate to mitigate). Also, the DB is temporarily inconsistent (lagging
behind). If another system or process reads directly from DB (bypassing cache), it will get stale data.
So write-back is complex and typically used when eventual consistency to DB is acceptable or the
cache is robust enough (like an in-memory database). Example: Some NoSQL systems or custom
caches let you queue writes. Also disk hardware caches use write-back (they say “written” when data
in disk cache, flush to disk later for performance – with risk if power loss). Another example: a high-
throughput logging service might accumulate logs in cache and flush to disk periodically.

Use cases: - Write-Through: good when read cache always needs to have latest data and read throughput
is critical. Write penalty accepted. Many web app caches do this for simple scenarios: update both cache &
DB on changes (or even have DB triggers to invalidate/update cache). - Write-Around: perhaps for heavy
write, less read scenarios. E.g. sensor data being ingested (don’t thrash cache with every insert, just let
reads fetch from DB when needed). Or caching derived data where writes generate raw data but you only
cache queries. - Write-Back: when write performance is a bottleneck and you can tolerate eventual
propagation. It’s like using the cache as a primary store with DB as backup. Some systems with high write
volumes (like time-series ingestion) might use a write-back buffer to batch inserts to DB (improving
throughput). But careful – if the cache layer fails, can lose data. Usually needs an acknowledgement or
replication system for safety (like Kafka can be seen as a commit log cache with batched writes to DB by
consumers).

Interactions: - A write-through cache will also often be used with a TTL or some eviction to eventually
remove data (if not accessed) but since every write updates it, popular items stay fresh. - A write-back
cache should ideally have a mechanism on shutdown to flush pending writes (like draining queue).

Example: Memcached in practice is typically neither pure write-through nor write-back by itself – it's often
used with write-around or manual cache invalidation: - App writes to DB, then invalidates cache entry (so
next read will fetch new value from DB). That’s a form of write-around + explicit invalidate. Or - App writes
DB and updates cache (which is write-through effectively). Memcached doesn’t automatically write to DB, so
write-back would need a custom mechanism.

Example: Redis as primary store (with RDB/AOF persistence) can act like a write-back: app writes to
Redis (fast), Redis asynchronously persists to disk (AOF log or snapshot). If DB is just for backup, that’s
somewhat analogous to write-back caching where DB = persistent storage.

30
Hot Key Mitigation

A hot key is a cache key or data item that receives an extremely disproportionate amount of traffic. In
distributed caches or databases, this can cause load to become uneven – one server responsible for that
key gets slammed, possibly exceeding CPU/memory or causing high latency, while others sit idle. It’s also
known as the “celebrity problem” (like a celebrity user’s data being accessed by millions).

Techniques to mitigate hot keys:

• Add random suffix / key spreading: Instead of using a single key that maps to one cache node,
create multiple keys for essentially the same data and randomize accesses among them 35 . For
example, if normally cache key is item123 , you could actually use keys item123_1 ,
item123_2 , ..., item123_N for some small N (say 10), and when reading/writing, pick one at
random. This way, that item's load is spread across multiple cache nodes (assuming consistent
hashing distributes those keys to different servers). On a read miss, you might populate all variants
or just one – design varies. Essentially, you intentionally duplicate the data into multiple keys to load
balance the hotspot 36 . This sacrifices some cache space (multiple copies) but prevents one node
meltdown. It’s effective when read traffic massively outweighs write (so duplicating isn’t costly on
write). Memcached or Redis usage: when reading a hot key, app chooses a random suffix; when
writing/updating, maybe update all suffix variants. AWS mentions this for DynamoDB partitions –
adding a random number to partition key to spread writes 37 .

• Shard celebrity users/data explicitly: If a particular user or entity is extremely popular, treat its
data separately. E.g. store that user’s data on multiple shards or a bigger machine. For a timeline
service (like Twitter), a celebrity with millions of followers might get a specialized handling – instead
of pushing an update to millions of follower caches (impractical quickly), you might not cache their
updates the same way or use a fan-out-on-read approach for them. Another approach: partition the
followers among multiple shards so that requests for that user are split. The StackOverflow answer
we saw indicates Twitter does something akin to giving big accounts a separate timeline approach
38 39 – effectively, they don’t fully populate caches of all followers; instead on read, combine

data from a special store. In caching context, if one key is hot, you might decide to break the content
behind that key into multiple keys (like random suffix method) or give that key’s caching its own
dedicated resources. “Shard by user” often means route that celeb to a different cluster that can
handle it, or replicate their data across nodes for load-balanced reads.

• Request coalescing (single-flight): This addresses a specific stampede scenario: when a hot key
misses in cache (say it just expired or invalidated), dozens or thousands of clients might concurrently
hit the database for it. Request coalescing means when multiple requests come for the same key
and cache is miss/being filled, allow only one to fetch from DB and have the others wait and then
use that result 40 41 . Essentially, the cache or an intermediate layer locks the key (or uses a
promise) so that only one thread goes to origin, others “collapse” onto that one. This prevents cache
stampede (lots of DB hits for same key). Many caches or CDNs implement this: e.g. Varnish has
request coalescing (one backend fetch for simultaneous requests) 42 . Memcached itself doesn’t do
it, but your application can (via locks or using something like Golang singleflight or Caffeine cache in
Java). Nginx also has an addon (proxy_cache_lock) to do this. So while not exactly spreading load to
multiple nodes, it prevents an empty cache from suddenly thundering the DB due to a hot key.

31
 • Hierarchical caches: Use a two-level caching: e.g. each application server has a local in-memory
cache, and there’s a distributed cache as level 2. If a key is hot among one app instance’s users, they
might get it from their local cache quickly, reducing hitting even the distributed cache. Also, an
organization might have multiple cache layers: say an L1 cache on each server (small, fast) and L2 is
Redis cluster. This reduces contention on L2 if many requests from one node repeatedly ask for the
key (they’ll hit L1 after first). Another hierarchy: CDN as L1, origin cache (like a regional cache) as L2,
then DB. Hierarchical caches ensure requests are served at the highest (closest) level possible,
which alleviates load on lower levels.

• Real-time cache scaling/replication: If you detect a key is extremely hot, you could dynamically
replicate that key to multiple servers. Some cache systems might allow a read-through for that key
that replicates it widely. Or you can temporarily increase cache nodes (if partitioned by keyspace,
though consistent hashing normally places key on one node plus replicas, which might be fixed
number). Alternatively, scale up the node that holds the hot key (vertical scale) or ensure replication
factor such that at least reads can go to replica nodes.

• Alternative data partitioning: For databases with hot partitions (like a particular partition key in
DynamoDB that gets too many writes per second), the solution may be to add entropy to key (like
the random suffix) or redesign key schema to better distribute load. E.g. composite key including a
random number prefix. DynamoDB specifically suggests a technique: if a partition key is hot, add a
suffix 0-9 chosen randomly on writes and on reads do parallel 10 reads and merge 37 43 . This is
similar to cache random suffix but on the DB side.

Impact of hot keys: They can cause cache evictions (if the hot key constantly replaced maybe large data?),
lock contention if the cache uses locks per key, or simply saturate network or CPU on one node. In extreme
cases, a single hot key can make the cache useless because that node becomes unresponsive, leading to
misses for other keys too if that node also hosted them (in a distributed cache cluster, often each node
holds many keys – a hot key can cause issues beyond itself by saturating CPU or network on that node,
affecting other keys on same node).

Example scenario: Imagine a viral tweet – everyone is requesting the tweet data (tweet text, author info). If
cached under tweet:12345 on one node, that node gets hammered. Using key spreading, you could
store the tweet under tweet:12345:0 ... :9 . Clients request a random one (maybe chosen by hashing
user ID or something to keep consistency per user if necessary). Each of 10 nodes gets ~1/10th of traffic.
The tweet content rarely changes (immutable), so duplicate caching is fine. This is effective especially for
read-heavy and static content.

Another example: an online game might have a “global leaderboard” – that’s one key that everyone fetches.
It would be a hot key; above techniques apply.

Hierarchical Caches

(This was in hot key mitigation bullet list, but let’s clarify separately)

Hierarchical caching means having multiple layers of caches that feed each other: - Level 1 (L1) cache:
closest to the requester (could be in-process or on the same machine). Very low latency, but small capacity. -

32
Level 2 (L2) cache: next layer, maybe a distributed cache cluster. Higher latency (network hop) but much
larger capacity. - Possibly L3 etc (like a DB’s own cache or disk etc).

The idea is akin to CPU caches (L1, L2, L3) or memory/disk. Hierarchy exploits locality further: if one app
instance repeatedly needs a value, keeping it in its L1 means it doesn’t even ask L2. L2 is shared so that if
another instance needs data not in its L1, it can get from L2 instead of going to DB.

Also, in hierarchical, you reduce cross-node contention. Each node first checks its local memory. Only
misses go to the shared cache, reducing load on it. This can improve scalability.

However, coherence becomes an issue: when data updates, you might have to invalidate multiple layers.
Typically, on update you’d update L2 then either broadcast an invalidation to L1s or use time-based expiry
on L1 (short TTL).

CDN + origin example: Browser (L0) -> CDN (L1 edge) -> Origin Cache (L2, maybe a caching reverse proxy
or app memory) -> DB. Many web setups have multi-level caches.

In code: e.g. use a library cache (Guava) in application and Redis as second-level. The code on cache miss in
Guava calls Redis; on Redis miss calls DB. When setting, set both. This is used in some high performance
setups.

Summing up hot keys: The aim is to distribute load across nodes either by duplicating data or by
controlling request concurrency, to avoid one hotspot.

4. Messaging & Streaming

Message Queues: RabbitMQ, Amazon SQS (Task Queues, Async Jobs)

Message Queues provide asynchronous communication between components. Producers send messages
to a queue, and consumers receive them (usually in FIFO order, at least within priority). Key properties: -
One message is consumed by one consumer (in a work-queue scenario). It’s point-to-point
communication. - After consumption (and acknowledgement), the message is typically removed from the
queue. - Good for task distribution and decoupling: e.g. a web server enqueues a “send email” task, a
background worker process picks it up and sends the email. The web server doesn’t need to wait for email
sending (making the request faster) and can retry or handle failures asynchronously. - They often support
ACK/NACK: the consumer acknowledges when processed; if it fails or doesn’t ack within a timeout, the
message can be requeued (ensuring it eventually gets processed – at-least-once delivery). - They may also
allow ordering or priority of messages.

RabbitMQ: An open-source message broker implementing AMQP. It has the concept of exchanges and
queues. Producers send to an exchange (of type direct, fanout, topic, etc.), which routes messages to
queue(s) based on routing keys. It supports complex routing, persistent messages, transactions, etc. It
requires the broker to be running (it’s not distributed by default, though there’s clustering but not like
partitioning for high load horizontally in the same way as Kafka). - Good for traditional job queues, RPC
between services, etc. It’s known for ease of use in simple scenarios (one of the earliest easy brokers). -
RabbitMQ can push messages to consumers (the consumer opens a channel and broker sends as they

33
arrive). - It also has features like DLQ (Dead Letter Exchange) for messages that can’t be processed. - It
ensures order per queue (unless multiple consumers, then order per consumer might vary since tasks
distributed).

Amazon SQS: A fully managed queue service. Simpler model: producers send to an SQS queue, consumers
poll messages. SQS guarantees at-least-once delivery. It’s highly available and scalable automatically. Two
types: Standard (which might deliver messages out of order or duplicates) and FIFO queues (which preserve
order and no dupes but lower throughput). - Consumers typically long-poll for messages. - SQS has a
concept of visibility timeout: once a message is delivered to a consumer, it stays invisible for X seconds so
the consumer can process. If the consumer acks (i.e. deletes message) within that time, fine. If not, after
timeout, message becomes visible again for another consumer – so if consumer fails or takes too long,
another can get it. This is how at-least-once and redelivery works in SQS. - SQS can trigger events or be
polled. It doesn’t have direct push. - It also supports DLQ: you can configure that after N failed attempts
(message not deleted), it goes to a dead-letter queue for manual handling.

Use cases for message queues: - Task queues / background jobs: e.g. processing images, sending
emails, generating reports – tasks that don’t need to be done during the user’s request. - Buffering bursts:
If producers produce faster than consumer can handle (transiently), the queue buffers tasks. The consumer
works at its pace. E.g. logging events to process later, smoothing out spikes. - Load leveling: Multiple
consumers can concurrently take from queue to scale horizontally. E.g. 10 worker servers reading from one
queue. RabbitMQ or SQS will distribute messages among them roughly evenly. - Communication across
different systems or tech stacks: e.g. one service writes an event to a queue for another service (maybe
written in another language) to handle. If the second service is down, the queue holds the messages until
it’s up (improves fault tolerance). - They also support delayed jobs (execute not now but after X time) –
some systems have specific features or you implement with invisibility time or future timestamp.

Delivery semantics: - Typically at-least-once: risk of duplicate processing, so consumers should be

idempotent or use deduplication if needed. - Exactly-once is tricky – SQS FIFO tries using deduplication
window. RabbitMQ doesn’t guarantee exactly-once; consumer or app logic must handle duplicates if needed
(via message IDs). - At-most-once if you configure to auto-ack as soon as delivered (possible in RabbitMQ
but then if consumer dies mid processing, message lost).

Comparison with streaming (Kafka etc.): Traditional MQs (Rabbit, SQS) are often queue semantics – you
usually don’t replay messages once consumed. They are often used for commands or tasks rather than
events (though they can do events too via fanout). They excel at ensuring tasks get done by some worker,
then drop them. Streaming systems (Kafka) store events longer, allow multiple consumers (via consumer
groups and topics), and replay.

Log-based Streaming: Kafka, Pulsar, Kinesis (Event Sourcing, Pub/Sub)

Log-based streaming systems maintain a durable, append-only log of messages (events). Key differences
from classic MQ: - Messages are stored in order and can be replayed (e.g. a consumer can start from
beginning and read historical data). - Typically support multiple consumers reading the log independently
(with their own offsets), as opposed to messages disappearing after one consume. - High throughput by
writing to sequential log segments on disk (leveraging fast I/O). - Often distributed by partitioning the log
into multiple segments across brokers (for scalability), where each partition is an ordered log.

34
Apache Kafka: The archetype of a distributed commit log. It has topics divided into partitions. Producers
write to a topic (to a partition, often chosen by key’s hash or round-robin if none). The message gets
appended to end of that partition’s log and stored. Each consumer group consumes a topic partition
exclusively (one consumer per partition at a time in a group, but different groups can independently
consume same data – enabling fan-out). Kafka stores messages for a retention period (e.g. 7 days or size-
based) regardless of consumption. This means a slow consumer or new consumer can still get older
messages. - Ordering: Guaranteed per partition, not across partitions (so if a topic has 10 partitions, total
order not guaranteed, but all messages with same key go to same partition to preserve order for that key). -
Scaling: By partitions; more partitions = more concurrency but also maybe out-of-order globally. - Use
cases: event sourcing (store all events to reconstruct state), user activity stream, logging, metrics ingestion,
inter-service communication (with replay), commit logs for CDC (change data capture from DBs). - Kafka has
the concept of broker (server), producer, consumer, and consumer group (each group gets a separate
read – e.g. one group for search indexing, one for analytics, both reading all events). - It also can act like a
queue if you only have one consumer group – then each message is processed by one from the group (like
a work queue) but Kafka retains it for a while. - Delivery: Typically at-least-once. At-most-once possible by
committing offset before processing (risky). Exactly-once is possible in Kafka when using transactions
between producer and consumer commit (and to some sink) – complex but supported.

Apache Pulsar: Similar concept (topics with partitions), but architecture differs (brokers stateless, storage
handled by BookKeeper segments). It natively supports multiple subscription modes: exclusive, shared,
failover, etc. It also has the idea of geo-replication and tiered storage (older data offloaded). Pulsar is rising
in popularity as an alternative, offering some flexibility like multiple subscription types (e.g. one topic can
have multiple sub modes for different use cases, like one shared subscription for work-queue style, one
failover sub for others).

Amazon Kinesis: AWS’s managed streaming service. Similar to Kafka conceptually: data streams with
shards (like partitions), retention 1-7 days (extendable). Producers push events, consumers in a consumer
group read with an iterator (like either get records in order from each shard). Kinesis manages scaling by
increasing shard count. It is often used for streaming data in AWS (Lambda can subscribe to Kinesis, etc.).
Kinesis ensures at-least-once. It’s not as full-featured as Kafka (e.g. no concept of consumer groups server-
side, you have to manage checkpointing via Kinesis Client Library that uses DynamoDB to store offsets).

Why log-based for event sourcing/pub-sub: - Event sourcing: an application might treat Kafka as the
source of truth for events. Services can derive their own state by consuming the log. The log is durable so
new services or reprocessing can start from the beginning. - Pub/Sub: A producer writes an event (like “user
signed up”) and multiple consumers (like an email service, a analytics service) all get that event via separate
consumer groups. That’s publish-subscribe pattern but implemented as reading the persistent log rather
than ephemeral fan-out. Kafka effectively does pub-sub by having each consumer group get a copy of the
data (the data is stored once per partition, but offset tracking per group).

Differences from RabbitMQ: - Kafka doesn’t delete a message once consumed – it relies on time/size
retention. This allows replaying events or handling temporary outages more gracefully. - Rabbit ensures no
backlog beyond what’s unacked (unless you let queue grow), whereas Kafka expects consumers may be
behind and catch up when they can. - Kafka is designed for high throughput (linear writes to disk and
sequential reads, zero-copy transfer). You might see it handling hundreds of MB/s easily. - Message
ordering in Rabbit is queue global (if single queue). Kafka ordering limited to partition. For extremely high

35
scale topics, you may design keys to keep important ordering within partition (like per user). - Kafka
typically requires a bit more client logic (tracking offsets, etc.), often provided by libraries.

Real-time processing: Kafka is often paired with processing frameworks (Kafka Streams, Spark Streaming,
Flink, etc.) that consume from Kafka and produce results to sinks or new topics.

Event reprocessing: If a bug happened in consumer, since Kafka keeps the log, you can re-run consumer
from earlier offset after fix to reprocess historical events (which you can’t with a transient queue unless you
logged them somewhere).

Scaling consumption: Add more consumers (within a group) up to number of partitions, to parallelize.

Stream vs batch bridging: Tools like Kafka Connect can feed logs from DBs (CDC) to Kafka or from Kafka to
DBs, enabling integration pipelines. Pulsar and Kinesis similarly.

Examples of use: - Logging pipeline: e.g. website logs -> Kafka -> log processing -> stored in Hadoop or
Elasticsearch. - User activity: clicks, pageviews -> stream in Kafka -> real-time aggregation or
recommendations (like count trending items). - Microservice events: order service emits event “order
placed” -> inventory service consumes to update stock, shipping service consumes to schedule shipment,
etc. - Buffering telemetry: IoT sensors produce a lot of data; push to streaming service to handle bursts and
feed to downstream slowly.

Pub/Sub: Google Pub/Sub, Redis Streams

Publish/Subscribe is a pattern where messages published to a topic are delivered to all interested
subscribers. It’s a broadcast model (1-to-many), unlike queue (1-to-1).

Systems: - Google Cloud Pub/Sub: Fully managed service, conceptually similar to Kafka/Pulsar but more
abstracted. You have topics and subscriptions. Publishers send to a topic. Subscriptions can be of two types:
pull (subscriber pulls messages when ready) or push (Pub/Sub pushes via HTTP to subscriber endpoints).
Pub/Sub auto-scales and persists messages for a short time (7 days max). It ensures at-least-once delivery.
Order is not guaranteed globally (by default, messages might arrive out of order), but one can use ordering
keys to guarantee order for that key. It’s very convenient for event-driven architectures on GCP. Many
services integrate with it (Cloud Functions triggers, Dataflow, etc.). - Use case: event distribution, decoupling
microservices on GCP, integrating systems (like when X happens, many services may need to know). - It’s
truly pub/sub in that multiple subscriptions on same topic each get all messages (like Kafka’s multiple
consumer groups).

• Redis Streams (and Pub/Sub): Redis has two mechanisms:

• The older Redis Pub/Sub: very simple – you SUBSCRIBE to a channel and any PUBLISH to that
channel immediately pushes to all subscribers. This is not persistent: if nobody is subscribed,
message is lost; if a subscriber is offline, it misses messages. It’s like a real-time bus, no queuing.
• Redis Streams: introduced in Redis 5, it’s a log-based structure in Redis. It persists the stream data
(in memory, with optional disk persistence since it’s Redis). Consumers can form consumer groups,
which allow a message to be delivered to one consumer in the group (competing consumers, like a
queue semantics within group) but you can also have multiple groups for pub-sub effect (each group
gets all messages, akin to Kafka consumer groups). Redis Streams support acking and pending

36
 entries (so you can claim a message from a dead consumer). It’s basically a lightweight Kafka-like
stream inside Redis, good for moderate scale and simpler deployment (no brokers separate from
Redis).
• Use case: smaller scale streaming, or need streaming but already using Redis. It’s not as scalable as
Kafka but simpler for certain contexts (within one Redis node or cluster).

Fan-out vs Fan-in patterns: - Fan-out: one publisher, multiple consumers (pub-sub). E.g. a notification
event fanning out to many services. - Fan-in: multiple producers, one consumer (or one aggregator). E.g.
metrics from many sources all end up in one stream that one service processes – that’s like logs from 100
servers all go to one Kafka topic which a single consumer aggregates results from. It’s not exactly a special
pattern beyond “multiple senders, one queue”, but sometimes solved with message queues with multiple
producers.

Dead Letter Queues (DLQ): A DLQ is a secondary queue where messages go when they can’t be processed
by the consumer. For instance, if a message continually causes errors (e.g., bad format or triggers a bug)
and exceeds some retry limit, it’s moved aside to DLQ instead of retrying endlessly or losing it 44 . Then
devs can inspect DLQ later. RabbitMQ has DLX (dead letter exchange) where you set queue to send rejected
messages to an exchange bound to a DLQ. SQS allows configuring a DLQ with a threshold of receive
attempts. Pub/Sub can implement by having consumer on error publish to a “dead-letter topic”.

Retry & Backoff in messaging: - If a message processing fails transiently (e.g. network call in consumer
fails), you usually want to retry after a delay to allow system to recover. - Backoff: increasing the wait time
with each retry attempt (exponential backoff is common: 1s, 2s, 4s, ... plus some random jitter to avoid
sync). - Many frameworks do this on consumer side or on queue requeue. For example, if using AWS
Lambda with SQS, you could implement logic to requeue with delay. - Some messaging systems support
delayed requeue natively (RabbitMQ has per-message TTL or separate delay queue plugin, or use a “retry
queue” that delays messages via TTL then sends back). - If not, the consumer may catch exception and
instead of ack, requeue it manually with some delay (like in Rabbit, could publish to a delay exchange). -
Backoff prevents hammering a failing resource continuously (giving time for recovery, and spreading out
retries). - There’s often a max retries before DLQ.

Patterns in pub-sub systems: - Topic: basic pub-sub entity (like channel). - Filtering: Some systems allow
subscribers to filter by message attributes so they don’t get all messages. - Order: If strict ordering is
needed, sometimes you design to have one partition or use key-based routing so each key’s events are
ordered for each subscriber.

Comparison: - RabbitMQ can do pub-sub by using a fanout exchange or multiple bindings (one message
goes to multiple queues). But Rabbit doesn’t store messages long-term – once consumed by each queue, it’s
done. - Kafka naturally does pub-sub by consumer groups; it retains messages for a duration. New
subscriber group can even start late and read older messages if still retained. - Google Pub/Sub retains for
ack deadline or until acked (and up to some days if not acked), which is ephemeral but decently long to
allow resilient processing.

In summary, pub-sub decouples producers and multiple consumers, allowing broadcast of events.
Traditional enterprise pub-sub was JMS topics, etc. Modern cloud and streaming tools made it easier and
more scalable.

37
Patterns: Fan-out, Fan-in, Dead Letter Queues, Retry & Backoff

We already touched on these: - Fan-out: sending one message to many consumers (like pub-sub). Achieved
by multiple subscribers or by a broker duplicating to multiple queues. - Fan-in: multiple producers converge
to one point (queue or aggregator service). E.g., metrics from 100 servers fan-in to one analytics service. Or
MapReduce shuffle is a sort of fan-in of data from many mappers to one reducer. - DLQ: covered above –
separate channel for messages that failed processing N times 44 . Allows manual or out-of-band handling. -
Retry & Backoff: ensure robust processing by retrying transient failures with delays 45 . Combined with
idempotency to avoid side effects.

Additionally: - Request-Response with MQ: e.g. correlation ID pattern: you send a message requesting
work and include a reply queue reference; the consumer processes and sends a response to that reply
queue with a correlation ID so the requester knows which request it’s for. - Streaming patterns:
windowing, aggregation we might consider in context, but those are more processing patterns.

This covers section 4.

5. Networking & APIs

Protocols: REST, gRPC, GraphQL, WebSockets

These are different API or communication protocols:

• REST (Representational State Transfer): Not a protocol per se but an architectural style for web
services. Typically uses HTTP with resource-oriented URLs and standard methods (GET, POST, PUT,
DELETE, etc.). It leverages HTTP semantics (status codes, headers) and is stateless (each request
independent, containing all needed info like auth). Data is usually JSON (or XML) payloads. REST is
simple and widely used for client-server communication (like a mobile app to backend). It’s human-
readable and caches/proxies can work with it because GETs can be cached, etc. It doesn’t enforce a
strict schema beyond JSON structure, and each resource often has its own endpoints for different
operations (e.g. /users , /orders/123 ). Good for broad interoperability and quick integration.
Downsides: clients might need multiple calls to gather related data (over-fetching/under-fetching
issues), no built-in schema or type safety, and sometimes inconsistent designs if not carefully
standardized.

• gRPC: A high-performance RPC framework from Google. It uses Protocol Buffers for interface
definition and data serialization (binary, compact). Runs on top of HTTP/2 by default and supports
features like bidirectional streaming, multiplexing, flow control. gRPC defines a service contract with
methods (like a function call on a remote service) and message types. You generate client and server
code from .proto definitions. It’s great for microservice-to-microservice communication due to
efficiency and type safety. Also supports deadlines, metadata, etc. gRPC calls aren’t easily human-
readable (binary messages) and not directly browser-callable (though there’s gRPC-Web variant). It’s
strongly typed and version tolerant (proto messages can evolve). E.g. define rpc
GetUser(UserRequest) returns (UserResponse) and the stub code handles network details.
It often yields better performance than JSON/REST for heavy loads because of smaller payloads and
persistent connections. Also, streaming in gRPC (client, server, or bidi streams) allows building
efficient real-time or batched processing pipelines.

38
 • GraphQL: A query language for APIs originally by Facebook. Instead of multiple REST endpoints,
GraphQL exposes a single endpoint (/graphql) where clients send queries specifying exactly the data
they want, and the server returns JSON fulfilling that shape. GraphQL has a schema with types and
relationships. Clients can nest and select fields – solving over/under-fetching by allowing them to get
all needed data in one go, and only those fields. It also allows mutations (writes) with defined inputs.
GraphQL decouples the client’s data needs from specific endpoints: one query might retrieve a user
and their 5 latest posts and comments in one request. Benefits: fewer round trips, strongly typed
schema, flexibility to evolve API without versioning (just add fields). Downside: complexity on server
to resolve potentially expensive queries (need to prevent very large nested queries), caching is more
complex (HTTP caches can’t directly cache POST GraphQL easily; need caching at field or application
level). It’s excellent for client apps (like mobile or web) that need various data views – the client can
request what it needs. Tools exist to generate TypeScript types from schema, etc.

• WebSockets: A protocol that provides full-duplex persistent connection over a single TCP (starting
with an HTTP handshake, then upgrading). Once established, server and client can send data at will
in both directions. It’s used for real-time apps: chat, live updates, gaming events. Unlike REST/gRPC
which are request-response, WebSocket allows server to push messages asynchronously without
client polling. Data format is typically lightweight (maybe JSON or binary frames). Maintaining
WebSockets is stateful: servers must handle many open connections. It’s good for scenarios
requiring instant updates or push notifications (like stock tickers, collaborative apps). However,
WebSockets bypass HTTP semantics, so caching proxies, etc., not in play; also need to manage
scaling (sticky sessions or external pub-sub to broadcast messages to correct sockets across cluster).
There’s also fallback complexity if WebSockets not available (but nowadays broad support, or
alternatives like SSE – Server-Sent Events – one-way server push via HTTP).

When to use what: - REST: Great for standard CRUD APIs and when simplicity or broad client compatibility
(e.g. call from browser with fetch or mobile easily). Its ubiquity and statelessness are advantages. Usually
over HTTP/1.1 or 2 but each request separate logically. - gRPC: Best for internal service-to-service
communication where performance and type safety matter. Also great for languages where proto stub
generation fits well. Not for direct web browser calls (unless using gRPC-web which uses an adapter/proxy
because browsers can’t handle HTTP/2 trailers, etc). - GraphQL: When clients need flexible data queries and
to reduce number of calls. Often used in BFF (backend-for-frontend) patterns where a GraphQL server sits in
front of microservices to aggregate data. Many SaaS APIs (GitHub, Shopify) use GraphQL for the flexibility it
gives to API consumers. - WebSockets: When you need continuous bi-directional communication or server-
push in near real-time. Eg. Chat apps, real-time dashboards, collaborative editing (like Google Docs), online
games. If only server -> client push needed (not bi-directional), SSE can be simpler (just an HTTP stream of
events).

Combine usage: Some apps use GraphQL for queries but subscribe to events over WebSockets for real-
time updates (GraphQL has a concept of subscriptions often implemented via WebSockets). Or use REST for
core API and WebSockets for specific events.

HTTP/2 effect: gRPC heavily relies on HTTP/2 features. HTTP/2 also benefits REST by allowing multiplexing
multiple requests over one connection (so reduces head-of-line blocking and need for too many
connections). But REST still has overhead of repeated headers, etc., which HTTP/2 does compress via
HPACK. So gap between gRPC and REST narrowed a bit by HTTP/2, but gRPC’s binary protocol and codegen
still yields efficiency and convenience.

39
Backwards compatibility: - REST JSON often backward compatible if you only add new endpoints or ignore
unknown fields on clients. - gRPC (Protobuf) explicitly supports backward compatibility if you follow rules
(don’t reuse field numbers, etc). - GraphQL schemas can evolve by adding new fields (clients only ask for
what they need, so adding is non-breaking; removing or changing type is breaking though, typically they
mark deprecated first).

Load Balancing: Round Robin, Least Connections, Consistent Hashing

Load balancing distributes incoming requests across multiple servers to improve performance and
reliability. Algorithms:

• Round Robin: The load balancer cycles through servers in order: server1, server2, server3, then back
to server1, etc. This assumes each request is roughly equal cost. It’s simple and widely used. It can
be weighted round robin (some servers get a proportionally larger share if they have more capacity:
e.g. weight 2 means that server appears twice in rotation). Round robin at DNS level (DNS RR) also
used for simple balancing (though not adaptive). Downside: doesn’t account for current load or
differences in request complexity.

• Least Connections: The LB tracks how many active connections or requests each server currently
has, and directs new requests to the server with the fewest active connections. This assumes
number of connections correlates with load. It’s good for long-lived connections or varying load
scenarios where round robin might overload a slower server. Variation: Least Load (if LB can
measure CPU or etc., but usually LB only sees connection counts or response times). For example, if
one server is slower and requests accumulate, least-connections might naturally send less to it
because it has more outstanding. Many hardware LBs or Nginx, etc., support least_conn.

• Consistent Hashing: This is a technique to route requests based on a key (like client IP, session ID,
user ID) always to the same server (assuming servers are arranged in a hash ring). It’s often used for
session stickiness or in distributed caches. In load balancing context, “consistent hashing” means if
you want a particular client or request attribute consistently to go to the same server (useful when
caching is local to server or to avoid re-loading session). It’s also used when load balancer is
effectively partitioning clients. If a server is added or removed, consistent hashing ensures minimal
redistribution (the key space is divided by hash among servers). For example, hashing client IP mod
N (though consistent hash means if N changes, distribution changes minimally vs mod which
changes a lot). Another usage: for stateful protocols like WebSocket shards – route a particular topic
or key always to same server to not scatter related messages. Note: consistent hashing is more
about distribution than balancing perfectly – some servers might get more if keys aren’t uniform or if
node count not tuned, so typically it’s used when an even distribution is not the primary concern but
data locality is. Weighted consistent hashing exists to adjust for server capacity.

• IP Hash (simple hashing): For sticky sessions often simpler LBs use IP-hash: map a client IP to a
server by hash mod N (changes drastically if N changes, which is why consistent hashing is a better
approach for dynamic membership).

• Random: Another strategy is random choice (with or without weighting) – surprisingly effective in
large scale as well (e.g. power of two choices algorithm: pick 2 random servers, choose the one with
less load, which approximates least connections with much less overhead).

40
Where load balancing happens: - Client-side LB: e.g. gRPC stubs can do round robin between known
addresses. - DNS load balancing: e.g. multiple A records for a domain, clients pick one (often essentially
round robin or random by resolver). Rough control but no health check unless using special DNS like
Route53 health checks. - Hardware / Software LB: e.g. F5, Citrix ADC, or HAProxy, Nginx, Envoy acting as a
dedicated LB at network or application layer. - L4 vs L7 LB: - L4 (transport layer) LB (like AWS ELB in TCP
mode or some hardware) just directs connections (based on IP/port). It doesn’t inspect HTTP or do smart
routing by content, just balancing at connection level. - L7 (application layer) LB (like a proxy) can do HTTP
specific things: content-based routing (like path-based – /images goes to one cluster, /api to another),
cookie insertion for stickiness, TLS termination, etc. It can also do more complex algorithms using info in
headers.

Why needed: Ensure no single server overloaded, allow scaling horizontally, provide high availability (if one
server down, LB stops sending to it). LB often does health checks to remove dead nodes from rotation.

Weighted LB: Weighted round robin or least connections let you prefer beefier servers or temporarily drain
a server by reducing weight.

Consistent hashing example scenario: A stateful cache cluster with no central coordinator might have
clients use consistent hashing to decide which server holds a given key. Or a chat application where userID
determines which server has their session and you want all requests from that user pinned to that server.

Note on “session stickiness”: Another approach to stickiness is cookie-based: LB issues a cookie on first
visit linking to server, then next requests cookie ensures same server. But consistent hashing of something
like client IP (with caution if behind NAT many share IP) or session ID can also achieve stickiness without an
explicit cookie mechanism.

Because consistent hashing doesn’t aim to evenly balance (some keys might be uneven), sometimes
you combine with other means: e.g. use it only for caches where fairness is second to data locality.

In microservices, “service mesh” proxies (like Envoy via Istio) often do round robin or leastconn by default
for calls between service instances.

Rate Limiting: Token Bucket, Leaky Bucket, Sliding Window

Rate limiting is controlling how many requests/actions allowed in a given time. It’s important to prevent
abuse (DoS, brute force) or just to ensure fairness and stable service by capping usage per user or client.

Algorithms:

• Token Bucket: This algorithm has a “bucket” of tokens that refills at a constant rate (say r tokens per
second) up to a maximum capacity (the bucket size, b). Each request consumes a token. If a token is
available, request is allowed and a token removed. If bucket empty (no tokens), the request is denied
or queued until a token is available. Token bucket allows bursts up to the bucket size because tokens
accumulate when not used, then a burst of requests can use them. But long-term average won’t
exceed the refill rate. E.g., 5 tokens per second, bucket size 10: you can burst 10 requests at once
(emptying bucket), then new tokens come at 5/sec, so next requests have to wait to accumulate. This
is good when you want to allow short bursts (for better user experience) but enforce sustained rate.

41
 Many systems use token bucket (like Linux traffic control, or libraries like Guava RateLimiter
implement token bucket).

• Leaky Bucket: Often described as a queue that drains at a fixed rate. Imagine incoming requests
are poured into a bucket and they leak out at a steady rate. If influx exceeds outflow, the bucket
(queue) fills, and if it overflows, requests are dropped. This essentially smooths out bursts to a
steady outflow rate. It’s similar to token bucket in outcome but conceptually: leaky bucket as queue
means at constant interval a request is processed; any extra backlog sits in queue. If queue too long,
additional requests are dropped. Some descriptions of leaky bucket in networking say it enforces a
strict output rate (shaping traffic). In terms of decision: you could implement by recording the time
of last allowed request, etc., but it’s more used in traffic shaping hardware. For computing allowed/
disallowed, token bucket is more commonly described.

• Sliding Window: A technique to measure count of events in a rolling time window (like per second or
minute) and enforce a limit. A naive way: use discrete windows (like count requests per 1 minute
interval). But that can be unfair at boundary conditions (someone could hit near end of one minute
and then immediately at start of next, nearly doubling allowed actions in a sliding 60s period).
Sliding window approach often uses either a moving window (with two buckets for current and
previous partial window to calculate a weighted sum) or uses exact timestamps for each request to
evaluate how many in last window. A popular approach is fixed window counter for simplicity (with
potential bursts at edges) or sliding log (store timestamp of each request and remove those older
than window length). But storing all timestamps is heavy if high volume. Sliding window counter
(approximation): at time t, consider current window and previous window’s count with a weight
depending how far into current window we are. E.g., if limit 100/min, and 30 seconds into current
window, you might combine 50% of previous window’s count + current count. This smooths
boundaries. But more typically, implement either token bucket or a fixed window and accept minor
bursting at edges.

Implementations: - Simple fixed window: e.g. use Redis INCR on a key per user per minute and expire
every minute. If it exceeds threshold, block. - Token bucket: could be implemented by storing last
timestamp and tokens available. Each request, calculate new tokens = (now - last_timestamp) * rate, add to
bucket (cap at max), then if tokens >= 1, allow and decrement, else deny. This can be done with atomic
operations in Redis or in memory if single server per user. - Leaky bucket: can simulate with token bucket
by making token generation = desired output rate and bucket size = 1 (strict smoothing), or by queueing
requests internally.

Examples where used: - Rate limit API calls per API key or IP (to prevent overuse). - Protecting expensive
operations (only X logins per minute to avoid brute force). - Web scrapers throttle requests to not overload
sites.

Token vs Leaky difference: Token bucket allows saving up unused capacity for bursts (good for usability
e.g. user not active for a bit can do a quick burst). Leaky bucket tends to output at constant rate, smoothing
by queuing/dropping bursts. In practice, token bucket is popular because of burst allowance control (bucket
size).

Sliding window especially in user-facing contexts to ensure user cannot circumvent limit by aligning with
boundaries.

42
Distributed consideration: In microservices cluster, a centralized or distributed approach is needed to
count across all instances. Often done via Redis or a centralized service like Kong API gateway or cloud
providers (AWS API Gateway has built-in limit per API key). Or each instance has local token bucket and the
LB consistently sends a given user to same instance (not common unless sticky) – so usually external
coordination (like Redis counters) is used for consistent limiting.

Edge vs application limiting: Could do at CDN (like Cloudflare rate limiting), at LB, or in app. At edge, you
can cut off before hitting servers which is good for DoS protection (but less context of user if not known at
edge).

Example numeric: Suppose 100 requests per minute allowed. - With fixed windows, user could do 100 in
last 10 seconds of minute 1 and 100 in first 10 seconds of minute 2, totalling 200 in a 20s span, but still
under limit per minute windows. - With sliding window, you’d aim to avoid >100 in any contiguous 60s.

Precision vs performance: Counting every request precisely can be heavy if extreme throughput. Some
algorithms allow approximate counting (like using token bucket in a coarse interval or counter with small
timeslice segments).

API Gateway: Throttling, Authentication, Routing, Logging

An API Gateway is a server that sits between clients and microservices (or backend services) to provide a
single entry point. It often handles a variety of cross-cutting concerns: - Throttling/Rate-limiting: The
gateway can enforce rate limits (per API key, per IP, etc.) – preventing abuse as first line. - Authentication/
Authorization: It can verify identity (e.g. validate JWT tokens, API keys, OAuth tokens) before routing the
request, so internal services don’t need to duplicate auth logic. It might integrate with an identity provider.
E.g. API Gateway verifies a JWT’s signature and claims, then perhaps adds user info to headers for
downstream. - Routing: Map inbound request to correct service based on URL, request path, host, etc. e.g.
/api/users/* goes to user-service, /api/orders/* to order-service. Also can do version routing or
AB testing (some requests to v2 service). Gateways often allow rewriting paths, aggregating responses
(though heavy logic at gateway is often discouraged to keep it lean). - Logging and Monitoring: The
gateway can log all requests, statuses, times, for auditing and monitoring. It might push logs to an ELK
stack or CloudWatch. It could also collect metrics (requests count, latency, error rate per service). - Caching:
It might cache certain responses if they are common (especially for GET endpoints that allow caching). -
Transformation: Gateways (like Kong, Apigee) can transform requests or responses (e.g. convert formats,
or enforce schemas). - CORS handling: They can inject cross-origin headers if needed. - Security filtering:
Could block certain patterns, do input validation or prevent known attacks (simple WAF). - IP whitelisting/
blacklisting: e.g. only allow certain IP ranges for some APIs. - Serving static content or fallback: Some
API gateways can serve simple static responses or maintenance pages if backend down. - Circuit breaking
(though usually that’s in service mesh or client; but gateway might detect repeated failures to a service and
temporarily stop routing there, depending). - Request/response modifications: like adding standardized
headers (trace IDs, etc.), or redacting sensitive info from responses if needed for logs.

Why use an API gateway: - In microservices, rather than clients calling each service (which complicates
client with many endpoints, and each service must handle concerns like auth, rate limit), a gateway
centralizes these. It also hides internal topology (client doesn’t need to know there are 5 different services; it
sees one API). You can version or compose services behind gateway without impacting clients as much. -
You can offload heavy tasks (TLS termination, authentication, etc.) to the gateway, freeing microservices to

43
focus on core logic. - It can reduce number of requests: sometimes gateway can aggregate responses (like
BFF approach for mobile: one call to gateway returns data from multiple services in one payload to
minimize mobile round trips). However, heavy aggregation logic might belong in a BFF microservice rather
than generic gateway, depends on design.

Examples of API Gateways: Kong, Tyk, Apigee, Amazon API Gateway, Azure API Mgmt, Netflix Zuul (older,
replaced by Spring Cloud Gateway), Traefik (with plugins), etc. They often support plugin architecture for the
above features.

Difference from load balancer: LB directs traffic to multiple instances of same service to spread load,
whereas gateway usually routes by service (different endpoints to different services), and adds
management features (auth, logging). Sometimes they combine (like an Envoy proxy can act as both LB and
API gateway features in one).

Deployment: Could be a cluster of gateway instances behind a LB for itself, since it’s a single entry point
logically but needs to scale and be HA.

Throttling at gateway: e.g. define plan levels (free users 10 req/sec, premium 100 req/sec). The gateway
inspects API key or token claims to determine quota and enforces it (often by integration with a usage
counting service or internal counters as discussed in rate limiting).

Auth at gateway: e.g. if using OAuth2, clients might pass an access token in header, gateway verifies
signature and scopes, possibly doing introspection or JWKS lookup, and rejects if invalid (401/403) without
touching services. Some gateways can also do user login flows, but often for APIs it’s token-based.

Important: Gateway must be robust and secure since it’s internet-facing. It’s also a good choke point for
things like DDoS mitigation (stop at gateway rather than hitting each microservice).

Logging: Many gateways log every request including headers (except maybe sensitive ones after redaction),
which is vital for debugging or analytics.

API composition: Some advanced use cases: The gateway might make multiple backend calls and merge
results (like /dashboard endpoint calls 3 services behind scenes, merges JSON). This is entering BFF territory
(back end for front end, a custom gateway for a client type). Many modern architectures instead have either
an orchestration service or use GraphQL at gateway to allow the client to query multiple sources in one go.
It depends if you want the gateway to be “dumb” (just route/auth) or “smart” (composing responses). Both
exist in practice.

Example: A mobile app hits /api/v1/users/123 at gateway: - Gateway checks auth token, verifies user
123 is the caller or allowed scope. - It routes to user-service (internal URL). - It logs the request. - It enforces
limit e.g. that user hasn’t called this too often. - Perhaps caches the response if configured. - Maybe
transforms user-service’s JSON to ensure it matches public API schema if internal differs. - Returns to client,
adding any cross-cutting headers like trace-id, or CORS headers for web.

44
Service Mesh: Istio, Linkerd (Service-to-Service comms, retries, circuit breaking)

A Service Mesh is an infrastructure layer for managing service-to-service (east-west) communication in a

microservices architecture. Typically implemented via sidecar proxies (e.g. Envoy) injected alongside each
service instance. The mesh provides: - Service discovery & routing: It can automatically know what service
instances exist (through integration with Kubernetes or similar). So when Service A calls Service B, the
sidecar can intercept and route to an appropriate instance of B (with load balancing). - Uniform telemetry
& logging: Every call goes through sidecars, which can collect metrics (latency, request count, error count)
and logs at network level, without code change in services. - Security (mTLS): Mesh can encrypt service-to-
service traffic transparently. Each sidecar can handle TLS handshake and encryption so that services talk
over mTLS (mutual auth TLS). It manages certificates (likely through a control plane distributing certs) and
can enforce that only certain services can talk (authorization policies). - Retries & Timeouts: Instead of each
service implementing retry logic, the sidecar can automatically retry failed requests to other service (with
some policy, like at most 3 retries with backoff) 46 . It can also impose timeouts on requests (if service B
doesn’t respond in X seconds, sidecar aborts). - Circuit Breaking: The mesh can monitor failures to a
particular service instance or host. If many failures happen (or high latency), the sidecar can “open a circuit”
and stop sending requests to that instance for a period 47 46 . This prevents cascading failures (if one
service is down and making requests hang or error, the circuit break will quickly fail calls instead of waiting
and congesting). - Bulkheading at connection pool level: Not exactly in mesh, but by having proxies, you
can isolate connections such that issues with one service don’t exhaust resources needed to talk to others
(some service mesh allow separate pools). - Traffic control: Advanced routing like A/B testing, canary
releases – e.g. direct X% of traffic to a new version of a service, or route by user type to different service
versions. Istio supports routing rules for such scenarios. - Fault injection: For testing resilience, one can
configure mesh to deliberately delay or fail a certain percentage of requests to simulate failures (to test how
services handle it). - Simplified client code: Services just make plain HTTP/gRPC calls to a localhost or
cluster DNS; they don’t need to implement fancy resilience logic or discovery. The sidecar does heavy lifting.
- Observability: Service mesh often integrates with tracing (e.g. Envoy can tag headers with trace IDs),
metrics (Envoy exports Prometheus metrics), and logs, giving consistent observability across languages
because proxies handle it.

Istio: A popular service mesh for Kubernetes. Uses Envoy as sidecar proxy. It has a control plane (Istio Pilot,
etc.) that distributes config to proxies (like routes, policies). Istio can enforce policies, like RBAC at mesh
level (service A can or cannot call service B). - With Istio, you typically inject sidecars into each pod. All traffic
from a service goes through Envoy out, and inbound traffic to the service goes through Envoy in, so Envoy
can apply policies in both directions. - Istio config (via CRDs in K8s) allows declarative rules for traffic
splitting, timeouts, etc.

Linkerd: Another mesh, simpler design and focuses on ultralight proxies (recent version uses Rust micro-
proxy). It’s often praised for being simpler to operate than early Istio versions (which had complexity).
Linkerd also provides mTLS, load balancing, etc., but tries to be more out-of-the-box with less complex
config.

Circuit Breaking specifics: It’s often implemented by monitoring error rate or connection pool saturation.
E.g. “if 5 consecutive requests to service X failed, open circuit for 10 seconds (i.e., immediately fail calls to X
for 10 sec without trying). Then allow a trial request later to see if it’s back (half-open state)”. Envoy supports
outlier detection: if an instance has high error percentage, it can eject that instance from LB for a while.

45
Retries caution: Mesh-level retries help when ephemeral failures occur. But they must be tuned carefully to
not amplify traffic during an outage (thundering herd). Usually limited with backoff and a max count,
possibly jitter.

Why not just library (like Hystrix)?: The service mesh approach externalizes these concerns, making them
language-agnostic and uniform. Developers don’t have to implement these in each service code. It also
means changes to policy (like new timeout) can be done by updating mesh config rather than redeploying
services.

Service mesh and API gateway: They can coexist: gateway handles north-south (client to server) and mesh
handles east-west (server to server). Sometimes they overlap in function (like both can do auth, but maybe
gateway does external auth and mesh does internal service identity mTLS etc).

Example scenario with service mesh: - Service A calls B. It actually sends request to localhost:15000
(envoy) which encrypts and routes to one of B’s pods (to that pod’s envoy). B’s envoy receives, decrypts,
forwards to B. If B is slow or fails, A’s envoy might retry or circuit break. Meanwhile, both envoys log metrics:
A->B call latency, success flag, etc. If B’s one instance started failing a lot, envoys could avoid it. All of this
without A or B being aware. - Later, team wants to do canary of Service B v2 for 10% traffic. They update
Istio VirtualService config to route 10% of calls from A to B-v2 service. No code change needed.

Downsides: Complex to set up and manage (adds network hops, sidecar overhead, lots of config). Need to
ensure it’s tuned (improper config could cause too aggressive retries, etc.). But at scale, the consistency and
features are compelling.

6. Scalability & Reliability Techniques

Horizontal Scaling vs Vertical Scaling

Vertical scaling (scale-up): Adding more resources (CPU, RAM, disk, etc.) to a single machine to handle
more load. E.g. upgrading from a 4-core server to 16-core, or increasing DB instance memory so it can
cache more. Vertical scaling is often simpler (no changes to architecture needed, just a bigger box) but
limited by hardware ceilings and can be expensive at high end (diminishing returns). Also, a vertically scaled
system still has a single point of failure (if one giant server goes down, the service is down). And hardware
upgrades have limits (can't scale beyond maybe the largest instance a cloud offers).

Horizontal scaling (scale-out): Adding more machines/instances to distribute load. E.g. instead of one big
server, have 10 smaller servers behind a load balancer. This approach can theoretically scale almost
indefinitely by adding nodes (given stateless or partitionable workload). It's the primary method to achieve
very high scale (like web server farms, distributed databases, etc.). It requires architecture to handle
distribution: stateless app servers, data partitioning or replication for state, etc. Horizontal scaling improves
fault tolerance because if one out of N fails, others still work (assuming properly designed cluster). But
complexity increases: need load balancing, consistency handling for data, etc.

When to vertical vs horizontal: - Early on, vertical is often easier (just get a bigger DB server until you hit a
cost or performance wall). - Horizontal is necessary for large scale or high availability (because you want
multiple servers). - Some workloads are hard to split horizontally (e.g. a single query that needs entire

46
dataset might need vertical performance). But many web workloads are embarrassingly parallel (many
independent requests). - Real strategy often use vertical until not possible, then horizontal. E.g. scale DB
vertically until you start needing to shard or add replicas, because sharding adds complexity.

Example: A web application might run on one server initially. If traffic increases, you might vertically scale
(bigger AWS instance). But eventually, you deploy multiple instances behind an ELB – horizontally scaling
the web tier. Similarly, for DB: might vertical scale plus read replicas (which is a bit of horizontal for reads). If
even that saturates, you consider sharding the DB horizontally.

Scaling out pitfalls: need to manage session state (use sticky sessions or external session store if
previously it relied on memory), idempotency etc. Also data consistency if writing to multiple nodes.

Auto scaling: Many cloud systems allow automatically adding instances horizontally based on CPU or
queue depth metrics.

Vertical scaling limits: e.g. if you rely on doubling CPU for doubling throughput, at some point memory or
I/O might be bottleneck, and bigger machines are not only more expensive linearly, but sometimes
exponentially (the largest instances have a premium). Horizontal can use commodity hardware.

Resiliency: Horizontal gives you ability to do rolling updates, etc., whereas vertical (one box) requires
downtime for updates.

Illustration: - Vertical: one database handling 1000 TPS might be replaced with a bigger one to handle 2000
TPS. - Horizontal: break data or queries into pieces and use e.g. 2 database servers, each handling half the
requests or dataset (with a coordinator if necessary).

Usually for reliability, having multiple instances is key so that if one fails, others carry on – so horizontal
scaling often done for reliability as well (with some redundancy).

Multi-Region Strategies: Active-Active, Active-Passive, Replication Lag Handling

When deploying globally, multi-region (multiple data centers or cloud regions) improves latency for users
and provides disaster recovery if one region goes down.

Active-Active: Two or more regions are serving traffic simultaneously (all are “active”). Data is replicated
between them (could be synchronous or asynchronous, depending on need and distance). - Example: A
global web service might have an EU and US region, with users directed to the nearest. Both handle reads
and writes. This requires data consistency strategies because writes from different regions need to sync. -
Usually, active-active implies eventual consistency if far apart (since synchronous cross-Atlantic commits
would be high latency). For example, Cassandra or Dynamo setups have multiple region replicas and tune
consistency if needed (like quorum across regions if strongly needed, or local quorum for latency). -
Challenge: conflict resolution. If same data updated in two places at once, how to merge? Some systems
use last write wins or more complex CRDTs if needed. - If using active-active for databases, you might
partition by user geography (each region primarily writes its user’s data and asynchronously replicates
backup to others, so minimal conflict). - Active-active web serving is easier if most state is local or
partitioned, but globally shared state (like a global user account DB) is tricky to keep in sync in active-active.

47
Active-Passive (Primary-Standby): One region is primary, serving all traffic. Another region is idle or read-
only (passive), not serving external traffic. The passive is kept up-to-date via replication. If primary fails
(disaster or planned failover), the system fails over to the passive (which becomes active). - Example: A
database primary in US, replicated binlog to Europe standby. Europe not serving unless US fails, then the
DNS or config switches to EU as primary. - There is usually some downtime or at least a failover time to do
the switch (and risk of data loss if replication was asynchronous and not fully caught up). - Benefit: simpler
consistency (only one active write copy at a time, like traditional master-slave on geo scale). - Many cloud
DBs (like RDS cross-region replica) operate active-passive for DR. - Passive can often serve read-only traffic
(so you might use it for read queries local to that region to offload or for better latency on reads).

Replication Lag Handling: In multi-region replication (especially async), one has to deal with lag: - If using
asynchronous, a secondary region might be seconds behind. If failover occurs, some last transactions may
be missing (this is RPO – Recovery Point Objective, how much data loss accepted). You mitigate by trying to
have near-real-time replication or sync points. - For reads from standby: If you allow reading from a replica
in another region, it might return stale data. Possibly fine for some use cases (eventual consistency model),
but if not, you could use “read my writes” routing (like a user’s own writes go to primary or use session-
stickiness to region). - Some systems (like Spanner) solve lag by true global consensus (but with high latency
for writes, using TrueTime and multi-phase commits). - Solutions: * Accept eventual consistency (for say
global user profile updates, might not instantly appear in other region). * Or restrict certain actions to one
region (like an account is tied to a home region). * Use distributed consensus (like Zookeeper/etcd multi-
region with majority spanning region – not common due to latency). - If replication is asynchronous, on
failover you have to either accept lost writes or have a process to sync missing ones (maybe manually or
through logs).

Latency vs consistency trade-off: Active-active can reduce user latency by localizing traffic, but you have
to deal with data sync. Sometimes design flows to be region-isolated to minimize cross region calls (like
separate user base per region, or at least sticky).

Partitioning by region: One approach is to partition users/data by region (so most data is local). Then
active-active becomes easier since cross-region consistency needed only for shared data. E.g. a user’s
shopping cart kept in nearest region. If they travel or connect to another region, maybe they get forwarded
to home region or deal with higher latency occasionally for their data.

Active-active and CAP: When network partition between regions, if each region continues accepting writes,
consistency diverges (thus AP oriented). If you want CP globally, one region would have to stop (effectively
active-passive or cluster of regions with one leader region).

Active-Passive failover methods: - DNS failover (update DNS to point to passive region – can be slow due
to TTL). - Use anycast or some global LB that can detect region outage and shift traffic. - Application-level
with multi-region aware clients (like client has both endpoints and tries secondary if primary fails). - Cloud
systems have some automated (like AWS RDS can promote a cross-region replica to master via console or
API if primary region down).

Testing DR: If active-passive, you need to periodically test failover so you're confident it works (and have
backup of config and data).

48
Data considerations: If primary goes down and then back up after failover, you might have a split-brain or
double-master scenario. Usually, you treat old primary as read-only or discard changes, or carefully resync.

Active-active for reads only: Some do multi-region read (all active for read, one active for write – so read
scale out, writes centralized – common in e.g. a primary DB with globally distributed read replicas).

Example: A social network: - Could have multi-home timeline: each region stores local users’ posts. Cross-
regional follower might see delays or a combined feed from multiple sources. - Possibly uses event queues
to replicate posts to other regions' caches.

Finally: RTO (Recovery Time Objective – how quickly to failover) and RPO (how much data loss) are key
metrics: - Active-active yields RTO ~ zero (since other region is already serving at least its users) and RPO ~
small (depending how quickly data replicates). - Active-passive might have RTO minutes (to cutover) and
RPO seconds to minutes (depending on replication sync).

Event Sourcing + CQRS (Write log, read projections)

Event Sourcing: Storing the state of an application as a sequence of events rather than as current state.
The idea: every change (event) is appended to an event log. The current state is derived by replaying or
aggregating these events. The events are immutable and act as the source of truth.

• Example: Instead of storing account balance in a row, you store events: Deposit $100, Withdraw $30,
etc. To get balance, you sum them to get $70.
• Why: This provides a complete audit trail, makes it easy to reconstruct historical states or debug by
replaying events, and allows to derive different views from same events.
• Write operations become recording an event. No destructive updates. If something changes, you
add a new event (e.g. “EmailChanged” event rather than updating email field).
• The sequence of events forms an ordered log (which could be on Kafka or a DB table of events).
• Usually, event sourcing is combined with snapshots periodically, so you don’t always replay from
scratch (e.g. snapshot of account balance every 100 events to speed up recovery).
• It fits well with domains where history matters (finance, audit) or when you want to derive multiple
representations (statistics etc. from events).

CQRS (Command Query Responsibility Segregation): Pattern where writes (commands) and reads
(queries) are handled by separate models. Instead of a single model that you both update and query, you
decouple: - The write side handles commands (with possible complex validation, domain logic) and typically
updates the event log (in event sourcing scenario) or updates normalized state. - The read side has one or
more models (often denormalized, optimized for queries) that are updated from the write side’s events.
These read models (projections) can be tailored to specific query needs (like a view that combines data from
multiple aggregates for easy reading). - The key insight: the way you want to write data (in normalized,
consistent form focusing on business logic) can be different from how you want to query it (maybe joining
across aggregates, or retrieving a precomputed result). By segregating, you can optimize each. - Usually,
the write side emits events or uses some mechanism to notify the read side to update its view (like event
handlers). - For example, write side might store orders and items separately, but a read side projection
could maintain a ready-to-query “Order with Items” view table that is updated whenever an order or item
event happens.

49
Combining ES + CQRS: A common approach: writing yields events (Event Sourcing), and then those events
feed into building projections for queries (CQRS). - The event store is the source of truth for writes. - One
projection might be something akin to a traditional relational view or a NoSQL store that is easy to query
(like a pre-joined structure or a full-text index). - The read side can even be a different type of database
optimized for queries (like using a graph DB for relational queries or ElasticSearch for text search),
populated by events from write side.

Benefits: - Scalability: Read side can be scaled separately from writes. Many read replicas or specialized
read databases can serve queries, while write side is small and focused. - Performance: Each side
optimized: write side doesn’t worry about heavy join queries; read side doesn’t need to handle heavy
transactional updates. - Complex domains: Write side can enforce complex business rules in commands,
while read side is simplified for retrieval. - Event sourcing adds audit and the ability to add new read
models easily: If you want a new view, you just consume past events into a new projection store.

Challenges: - Complexity: It’s more complex to implement and reason about because data is eventually
consistent between write and read models (the read model updates slightly after events). - Lag: There’s a
propagation delay from writes to read views, which might be fractions of second to seconds. So a user
might commit a change and not see it immediately in a query if the projection hasn’t caught up (you may
need to handle that – maybe by updating UI optimistically). - Eventual consistency: Developers must
handle out-of-sync scenarios and ensure idempotent or exactly-once processing of events to build
projections properly. - Data volume: The event store can grow large (need archiving strategy). -
Debugging: More moving parts can be tricky to debug, though events help audit logic.

Example scenario: - Imagine a Shopping Cart system. With event sourcing, each action (AddItem,
RemoveItem) is an event. The write side when receiving a “AddItem” command would produce an
“ItemAdded(productId, qty)” event. - The read side might maintain a projection of current cart contents per
user in a fast lookup (like Redis or a SQL table with one row per cart item count). Each “ItemAdded” event
triggers updating that projection (increment item count, etc.). - When a user requests their cart, the read
model is immediately returned (no on-the-fly calculation of all events). - The order service could similarly
event source orders and the read side have an “OrderSummary” view combining order info and the items,
for quick display. - If an order is placed (cart -> order conversion), a sequence of events (OrderCreated,
ItemRemovedFromCart etc.) can update various read models: user’s cart now empty, user’s orders list
updated, inventory projection might reduce count, etc.

Projections updating often done via event handlers (like a consumer reads from event log and updates a
DB table). In frameworks, it might be automatic mapping or manually writing handlers.

Idempotency and ordering in event processing must be handled (to ensure exactly-once application to
projections, often by storing last processed event id or using a streaming system that assures at-least-once
plus your own dedup).

Tooling: Some libraries and frameworks (Axon, EventStore, etc.) support ES/CQRS patterns. But
conceptually you can roll it with any message queue or DB.

Why often paired: Because if you event source but still query by replaying events every time, that’s
impractical for user-facing queries. So you need snapshots or projections to query easily – which is
essentially CQRS (the query model is derived from events). Conversely, if doing pure CQRS without event

50
sourcing, you could have separate write and read DBs, but you then have to replicate changes somehow
(maybe via event notifications or DB triggers). If you’re already sending events, event sourcing formalizes
that and gives you a clear log of what changed.

Conclusion: This pattern is powerful for complex domains requiring audit logs and different views of data.
But it’s heavy for simple CRUD apps and not needed if eventual consistency and complexity overhead are
not justified. It's often used in financial apps, collaborative systems (where you need history of changes), or
systems with very distinct read/write usage where scaling read and writes separately is needed.

Database Indexing: B-tree, Inverted Index, Bitmap Index

Database indexing is about data structures that allow fast lookup of data by certain keys or patterns.

• B-tree index: The most common index type for relational databases (e.g. InnoDB uses B+Tree for
primary and secondary indexes). B-tree indexes maintain sorted order of keys and allow log-time
search. Ideal for exact lookups and range queries on that key (because the leaves are in sorted order,
scanning between two values is efficient). They are balanced trees, so depth is small. Supports
inserts, deletes relatively efficiently too. B-tree indexes can be unique or not. They can usually
support queries with =, <, >, >=, <= on the indexed column, and can also support sorting
results by that column cheaply. Multi-column B-tree indexes can be used for composite key lookups
(works for queries that use the leftmost prefix of the index columns). E.g. an index on (last_name,
first_name) can be used to search by last name, or last+first, but not by first name alone (because of
how composite ordering is).
• B+Tree (typical variant) stores all values in leaf nodes and has pointers (linked list) between leaves
for sequential scanning.
• B-tree indexes are not great for full string search within text, but good for prefix or exact matching
(like WHERE name LIKE 'Jo%' can use B-tree to find range of 'Jo' prefix).

• Most queries (point lookup, join by key, etc.) rely on B-tree indexes.

• Inverted index: Used primarily in full-text search engines (Elasticsearch, Solr, etc.) 18 and
sometimes in DBs for text columns (some DBs have a full-text index separate from normal B-tree).
An inverted index maps terms -> list of documents (or rows) containing those terms. Essentially a
dictionary of every word (after analysis) linking to the postings list of documents and positions. This
allows fast search for documents containing a word or phrase (by intersecting lists of multiple
words). For example, indexing text "the cat sat on the mat" would add entries: 'cat' -> {doc1,
position2}, 'mat' -> {doc1, position6}, etc. Then a query "cat AND mat" will fetch list for 'cat' and 'mat'
and find document common to both (doc1).

• Inverted indexes are optimized for read-heavy, complex text queries with boolean conditions,
phrases, scoring, etc.
• Not used for numeric range queries typically (though you could invert index numeric values or
ranges, but not common when B-tree better).
• In relational databases, something like Oracle Text or MySQL FULLTEXT uses inverted index under
the hood for textual columns.
• Also can be used for tags or arrays (to find which rows have a given element).
• They typically store additional info like term frequency for ranking (in search engine contexts).

51
 • Without inverted index, searching in text would require scanning all rows or using sequential
scanning, which is slow for large corpus.

• Bitmap index: Represents index data as bitmaps. Typically each distinct value in a column gets a
bitmap of length = number of rows (or row IDs range), where a bit is 1 if that row has that value, 0
otherwise 48 49 . For example, a Gender column (M/F) in 1 million rows: you would have 2 bitmaps
of length 1M, one marking all positions of 'M', one for 'F'. Queries like gender='M' become retrieving
the 'M' bitmap and quickly getting row positions. For low-cardinality columns, these bitmaps
compress well and operations like AND/OR on them are very fast via bit operations (bit AND, OR).

• Useful in data warehousing for queries that involve conditions on multiple low-cardinality columns.
E.g. a table with columns like Region (few possible values), Category (few values), etc., you can
combine conditions by bit arithmetic on bitmaps instead of doing multiple index lookups and
intersecting sets or joining.
• Bitmaps can accelerate counting queries as well (count of rows matching condition = count of bits
set).
• However, for high-cardinality (each value is rare or unique), a bitmap index would have almost as
many bitmaps as rows, which is inefficient (not space or time efficient). So they are recommended
for low distinct values (like boolean, enums, status codes).
• Also updates can be costly (need to update multiple bitmaps).
• Some systems use roaring bitmaps or compression to store them effectively.
• Oracle has bitmap indexes which are known to be useful in OLAP contexts where data is mostly read-
only and queries often combine multiple conditions (like WHERE region='US' AND gender='F'
AND ageGroup='30-39' etc. — each can be a bitmap and do quick bit operations).

• Not typically used in OLTP because of update overhead and because OLTP usually deals with high-
card columns (like user ID).

• Hash index: Not asked but an honorable mention: Some databases have hash indexes (like
PostgreSQL had them, but not widely used because a B-tree can serve most purposes). Hash index
maps key via hash to buckets. Very fast exact lookups, but cannot do range queries (since order is
lost). Useful for equality-only searches if implemented. E.g. MySQL Memory engine uses hash
indexes by default. But on disk, B-trees prevalent.

When to use what: - Use B-tree (the default) for most indexing needs on relational columns used in
equality or range filters, sorting, and for implementing primary key uniqueness. E.g. index on
"ORDER_DATE" for date range queries. - Use inverted indexes for full-text search or anywhere you need to
find records containing any of many words or values (like an array of tags where you want to query by tag). -
Use bitmap for low-cardinality columns in analytic queries (like data warehouses where you might filter by a
few categorical fields often).

Examples: - In a library DB: - B-tree index on ISBN for quick book lookup. - Inverted index on "description"
text to search books by content. - Bitmap index on "genre" if you have e.g. 10 genres and often filter by
genre and other attributes (so scanning combined bitmaps might be faster than index merges).

Index impact on write: All indexes slow down inserts/updates because they need maintenance. E.g.,
updating a field that is part of a B-tree index means repositioning in tree, etc.; updating an indexed text

52
field means updating the inverted index; updating a value in a bitmap index might flip bits in a big array
(some bitmaps might need splitting if heavy compression, etc.). So choose indexes that benefit queries
significantly to justify write cost.

Memory usage: Indexes take space. In-memory vs on-disk considerations: - B-tree often on disk (with
caching). - Inverted index can be large (but they compress terms and postings). - Bitmap indexes compress
well if data is sparse, but can be huge if not compressible (like unique values, not recommended).

Multi-column B-tree vs separate bitmaps: For multi-conditions, sometimes a multi-column B-tree can
handle combined conditions (like index on (A,B) helps WHERE A=x AND B=y both). But if queries often
come in various combinations, you might have multiple indexes and DB does index intersection (some DBs
can take two indexes results and intersect). Bitmap indexes particularly shine at intersecting multiple
conditions because bit operations are fast.

Software examples: - Oracle supports bitmaps and b-tree, plus has text indexing (inverted). - PostgreSQL:
B-tree, GiST/GIN for full-text (GIN is an inverted index for text or array fields). - Elasticsearch: pure inverted
indices for all fields (including numeric terms, but they also have column store for aggregations now). - Data
warehouses (like Sybase IQ, now SAP IQ) used bitmaps heavily for performance on large analytical queries.

Data Lake & OLAP: BigQuery, Snowflake, Presto

Data Lake: A storage repository that holds a vast amount of raw data in its native format, usually on a
distributed file store (like HDFS or cloud storage like S3/Google Cloud Storage) that is cheap and scalable.
The idea is to store all data (structured, semi-structured, unstructured) without upfront schema, and
process/interpret it as needed. It's often contrasted with a data warehouse (which imposes schema on
write, cleans and stores data in a structured way). Data lake is more schema-on-read – you apply a schema
when you query it.

• Typically built on Hadoop ecosystem originally (HDFS), now object storage is common because of
durability and infinite scale (like Amazon S3).
• Data can be of various types: logs, images, raw CSVs, JSON, etc.
• Purpose: to have a central reservoir of all enterprise data that can be used by various analytics or ML
tasks later.

But a data lake by itself isn't queryable in SQL without something to read the files. That's where engines like
Presto or Hive or Spark come in (to query the lake), or loading some of it into OLAP warehouses.

OLAP (Online Analytical Processing): Refers to systems optimized for analytical queries (complex queries
scanning large portions of data, aggregations, etc.), as opposed to OLTP (many small transactional queries,
point lookups/updates). - OLAP systems often use columnar storage (store columns separately, which
compresses well and you can skip irrelevant columns for queries, e.g. Parquet or ORC formats). - They might
distribute queries across nodes for parallel processing (MPP – Massively Parallel Processing). - They might
allow SQL but under the hood do large scans and distributed joins.

BigQuery (Google): A serverless data warehouse/analytics DB. You load or register data (often in columnar
format or in BigQuery storage), and you can run SQL queries that scan potentially billions of rows in
seconds. It separates storage and compute; behind the scenes uses columnar storage (Capacitor format)

53
and processes queries on Google's Dremel engine. BigQuery is fully managed – you don't worry about
servers, you pay by data scanned or flat rate. It's great for big data analysis, and can directly query data in
Google Cloud Storage too (external table approach or via federated query).

Snowflake: A cloud data warehouse that also separates compute and storage. Data is stored in compressed
columnar form in cloud storage, and compute clusters (virtual warehouses) can be spun up to run queries.
Snowflake handles management of metadata, optimization, etc. It supports standard SQL, and has features
like time travel (query data as of past time), cloning, etc. It's multi-cloud (AWS, Azure, GCP). Snowflake
architecture decouples compute clusters so multiple teams can query the same data concurrently on their
own clusters without contending for CPU, etc. It's ACID compliant for transactions within itself and can load
large amounts of data.

Presto (Trino): An open source distributed SQL query engine for big data (originally from Facebook). Presto
can query data from various sources including Hive data on HDFS (which is a typical data lake), S3, or even
relational DBs via connectors. It doesn’t have its own storage; it's a query engine that can sit on top of a
data lake. Presto is great for interactive queries (as opposed to batch like MapReduce or Spark), and it uses
memory heavily for speed. Trino is the continuation of Presto by some of original authors – it’s essentially
the same category. It allows you to join data from different sources too (like join a MySQL table with a Hive
table, though performance depends on pulling data).

How these relate: - BigQuery and Snowflake are data warehouses that often act as the centerpiece of an
analytic platform, sometimes fed by a data lake or ingest pipelines. They often store curated structured data
but can store raw semi-structured in their table formats (like Snowflake can have VARIANT type for JSON). -
Presto/Trino and similar engines (Hive, Spark SQL, Drill) often query data lake directly (like Parquet files on
S3 containing logs or raw events). They often require a metastore (like Hive Metastore or Glue Data Catalog)
that has table schema for files. So a company might have a "data lake" of Parquet files partitioned by date,
and use Presto or Spark to query them, perhaps summarizing into smaller sets or feeding into data science.

Columnar storage benefit in OLAP: If a query only needs few columns out of many (which is typical in
analytics, like "SELECT region, SUM(sales) FROM big_table GROUP BY region"), a columnar format will only
read the region and sales columns from disk. Also, values compress well (same data type down column).
And skipping is easier if applying filters on a column (store min/max per page to skip irrelevant pages if
values out of range).

In-memory vs on-disk: Presto does a lot in-memory processing, but reads from disk (HDFS or S3) for data.
BigQuery reads from BigQuery storage (which is actually separated but heavily optimized). Snowflake
caches data in SSD when queries are run but base is cloud storage.

Data Lake vs Data Warehouse: - Data lake for raw data (low cost storage, high quantity, unknown use
cases initially). Possibly messy, not all quality checked. - Data warehouse (like BigQuery/Snowflake) for
cleaned, structured data that is used for BI and known queries. More performance and management
features (security, concurrency). - Sometimes architecture: ingest raw -> store in data lake -> then ETL into
data warehouse for main usage. But the lines blur with powerful engines that can query raw directly or with
tools like Delta Lake (which add ACID to data lakes, e.g. on Parquet).

Example use case: - An e-commerce collects event logs (clicks, views) to S3 as raw JSON daily. They also
have customer and order data in structured form. - They register or ETL the logs into a BigQuery table

54
(possibly as partitioned by date). - Analysts use BigQuery to run SQL combining log data and order data to
find funnel conversion rates. - The raw logs remain in data lake. For some machine learning training, data
scientists might use Spark on the raw logs from S3, because they want full flexibility. - Snowflake or
BigQuery could also directly ingest and store that log data (with some transformation). - Presto could be
used by engineers for ad-hoc queries on data lake without loading it all into warehouse.

OLAP queries vs OLTP queries: - OLTP: "Get order by ID" or "Update user name" (targeted, index use, not
scanning whole table). - OLAP: "Sum of sales by region for last 5 years" (scans large portion or whole
dataset, heavy aggregate). - Therefore, OLAP systems use parallel processing and reading lots of data
sequentially (which is what columnar is good at, contiguous column reads, vectorized operations). - They
sacrifice point-query speed or frequent small updates (some like Snowflake best at batch loading or micro-
batch, but not single row updates repeatedly; though they support transactions, it's not as efficient for
heavy OLTP usage).

Presto advantage: It's open source and you can query multiple sources (like a federated query engine).
However, you must maintain the cluster (though companies offer it as service, e.g. Athena in AWS is Presto
under the hood for S3 queries, or Ahana cloud Presto).

BigQuery advantage: No infrastructure to manage, auto-scaling, but you pay per TB scanned unless flat
rate, so cost needs monitoring.

Snowflake advantage: High performance, separation of compute (so one team’s big query doesn’t slow
another’s, just spin separate warehouse), and ease of use (like semi-structured ingestion).

Trends: The integration of data lakes and warehouses ("lakehouse") is happening: e.g. Snowflake can query
external data on S3; Databricks (Spark-based) wants to provide SQL warehouse feel on lake data with Delta.
Presto and others bridging too. BigQuery can directly query files in Google Cloud Storage (with some speed
penalty vs internal storage).

Global ID Generation: Snowflake IDs, UUID, DB Sequence

Generating unique identifiers at scale across distributed systems: - Snowflake ID (Twitter Snowflake
algorithm): A 64-bit unique ID composed of time and other components 50 . Specifically, Twitter's
Snowflake (2010) format: 1 sign bit (unused, 0), 41 bits timestamp (ms since epoch), 10 bits machine ID (or
data center + worker), 12 bits sequence number (per machine per ms) 50 . This yields IDs that are globally
unique and roughly time-ordered (monotonic increasing per machine). In Snowflake, if sequence overflows
in the same millisecond, it waits to next ms. These IDs are often expressed as 64-bit integers (which can fit
in unsigned 64, or as a decimal string). They are very popular in distributed systems (used by Twitter,
Discord, Instagram, etc.) because: - No coordination needed to generate (each node can generate its own
set of IDs given a unique machine ID). - They are sort-of ordered by time, which can be useful for certain
queries or for sorting by ID to get chronological order. - They have plenty of capacity (often used from 2010
to ~ year 2080something before timestamp bits wrap). - Collisions are extremely unlikely given unique
machine bits and sequence.

55
Implementing requires each machine know its ID (ensuring no duplicates across machines). Systems like
snowflake often rely on config or a coordination service to assign machine IDs (like ZooKeeper).

• UUID (Universally Unique Identifier): A 128-bit value. Common types:

• UUIDv4: random 128-bit (with a few bits for version). Very easy: just random. Probability of collision
is astronomically low (2^128 possibilities). No need for coordination or time. Not ordered (completely
random).
• UUIDv1: includes time (60 bits of timestamp, 14 bits clock sequence) and MAC address of node (48
bits) 51 . These can be roughly ordered by time (though not strictly because of clock seq and
concurrency issues).
• UUIDv3/v5: name-based (hashing a namespace and name).
• Most usage is v4 (random).

Pros: easily generated anywhere (libraries in most languages). Unique enough for most uses. Cons: 128-bit
is large (storage overhead if used as key, e.g. index on DB), not great for sorting (random v4 shuffles insert
order, causing index fragmentation). Also not easily human-friendly (though base64 or hex can represent,
it's long).

Also, as keys in DB, random distribution can cause poor locality in B-tree (every insert at random place;
some DB sequence yields ascending which is better for B-tree insert pattern).

There are ordered UUIDs (like UUIDv1 or some DBs have functions to combine v1 timestamp with v4
randomness to get "UUIDv1.5" for order).

• Database Sequence / Auto-Increment: Many databases support a sequence (e.g. Oracle

SEQUENCE, PostgreSQL sequence, MySQL AUTO_INCREMENT) that produces sequential numbers
typically starting at 1 and incrementing by one for each new row. Pros:
• Simple, and yields small, ordered integers (good for indexing, caching).
• Maintains uniqueness easily within one database node.

Cons: - Not easily distributed: if you have multiple DB shards or multiple app nodes that need IDs without
centralized DB, a single sequence in one DB doesn't scale out well (calls to it become a bottleneck). - If using
a DB sequence on one node, all inserts funnel to that node for ID generation (though some scale sequences
by allocating ranges or stepping multiples). - It also can reveal info (like how many records inserted by
seeing the number, albeit that's minor).

Solutions for distributed sequence: * Partitioned approach: each node gets a block or range of IDs (like
Node1 uses IDs 1-1000, Node2 uses 1001-2000, etc. Could pre-allocate or dynamic). * Or each node uses a
different increment offset: e.g. Node1 uses 1,3,5,... Node2 uses 2,4,6,... (this would be an approach if you
know number of nodes and can assign different starting offset). * Or use something like a centralized
service that hands out IDs or ranges (like Twitter's Snowflake service was a network service that gave IDs to
clients).

• Combining aspects: Some use a hybrid: e.g. a 64-bit like Snowflake but maybe with fewer bits for
time and more bits for machine if needed. Another approach: 128-bit ULID (Universally Unique
Lexicographically Sortable ID) – essentially a base32 encoded ID with time component, intended to
be lexicographically ordered by time (for easier sorting).

56
 • Nano ID or other libs: Many languages have libraries for smaller base62 IDs.

Considerations: - Uniqueness vs Order vs Coordination: - If you need simple uniqueness in one system,
DB sequence is fine. - If you need uniqueness globally without central control and want ordering by time,
Snowflake or ULID is good. - If you just need uniqueness globally with no dependency, UUID v4 is easiest
but gives up ordering. - If IDs are used in URLs or public, sometimes shorter is nice (UUID is long). People
sometimes use base62 strings from an integer, etc. - Some systems use natural keys like e-mail but often
need an ID anyway for PK.

• Security: Predictability of sequences or time-based IDs might leak info or be guessable. Snowflake
IDs, if known, reveal timestamp (some decode them to get approximate creation time). If that's an
issue, random might be better.

• Scale: If generating thousands IDs per second, ensure approach can handle that:

• DB sequence might become hot row in DB (some DB handle sequences outside transaction logs
fairly well though).
• Snowflake algorithm can easily do many per ms as long as sequence bits are enough (2^12=4096 IDs
per node per ms by default).

• UUID v4 generation is just random number generation, which can handle high throughput in most
languages easily.

• Space: 128-bit keys double the storage vs 64-bit. For a large table, that matters (both storage and
index memory).

• Many with big data prefer 64-bit keys.

• Snowflake ID is 64-bit fits in an 8-byte integer (which is efficient).

Example use: - Twitter originally used Snowflake for tweet IDs (64-bit). All tweets sort by ID ~ chronological.
- Many databases often use an auto increment for primary key (like customer_id). - If microservices want to
generate IDs without central DB, they might implement Snowflake-like or use something like a distributed
ID service (e.g. Baidu's UidGenerator, or others like Instagram's snowflake adaptation). - For highly
distributed systems, sometimes they use a combination: e.g. prefix ID with a service or shard ID and a local
sequence.

Software tools: - Some cloud providers provide ID generation: e.g. some NoSQL like MongoDB have
ObjectId (12-byte which includes timestamp and host info). - Snowflake (the company) ironically is also the
name of the data warehouse, but here we mean Twitter's Snowflake algorithm for IDs. - Libraries for ULID
(26 char string, time-sortable). - Flake IDs by Boundary, Sonyflake etc are similar concept.

Conclusion: Use case example: - Suppose an order service runs on multiple data centers, you want each
new order to have a unique ID. If using DB sequence central, cross-DC calls slow. Instead, implement
Snowflake: assign each DC or each instance a unique ID portion, generate 64-bit. That yields globally unique
order IDs without central bottleneck. - If some older system just uses an incremental, you may have to
merge data from multiple sources – could cause collisions, so often they adopt a new combined approach
or do offsets.

57
Alright, now we've compiled content and citations across everything.

We should ensure citations are integrated. Let's review citations:

We have collected various references: - ACID definitions and difference from NoSQL eventual from [3]
AltexSoft: - ACID props at 1 and mention eventual consistency at 31 . - Key-value explanation from [3]
around L141-L145. - Document DB explanation [26†L223-L232]. - Graph DB [26†L315-L323]. - Wide column
[29†L392-L400]. - CAP theorem from IBM [31†L20-L27] & we incorporate [31†L99-L107] or [31†L100-L108]
for CP vs AP, and maybe [31†L111-L119] for CA theoretical (the CA not practical). - ACID vs BASE from
Macrometa [33†L80-L87] that acid vs base difference (we used [33†L80-L87]). - Quorum from ByteByteGo
[35†L169-L177]. - Sync vs async replication from Evidian: - [38†L281-L289] described sync vs async in one
chunk. - [38†L309-L317] covers asynchronous description. - Sharding algorithms from Tencent [41]: - Range
[41†L14-L20] - Hash [41†L21-L28] - List (geo) [41†L28-L36] - Consistent [41†L41-L47]. - Paxos & Raft mention
(we gave conceptual, and we could cite [42†L17-L20] the definition "allow cluster to agree even with
failures". - Idempotency from ByteByteGo [44] snippet or blog: - [44†L9-L17] "Idempotency is property that
same action multiple times yields same result". - ByteByteGo caching (hot key splitting) [5†L209-L217]. -
ByteByteGo stamping and TTL staggering [5†L88-L96]. - Request coalescing [24†L21-L29] and [24†L33-L41].
- Dead-letter from ByteByteGo [9†L37-L40]. - Service mesh mention Istio resilience [12†L354-L361] "Istio
includes retries, timeouts, circuit breaking." - B-tree vs others from GFG [45] or [45†L217-L224] differences
of indexing strategies (we might not direct quote; but we could cite [45†L217-L224] summarizing difference:
"Bitmap good for low cardinality, hash for exact, b-tree adaptability"). - Snowflake ID details from Wikipedia
[47†L146-L154].

Let's see if we missed any needed citation: Possibly for GraphQL or GRPC etc, but those are general
knowledge and not directly in references, fine to not cite since it's our explanation. The guidelines said to
cite connected sources when used. We have done that for key definitions and claims from those sources.

We should ensure we put the citations elegantly in text not after headings.

Now one more thing: The user asked for two documents – one long form (which we've done), and one
flashcard reference.

We should separate them clearly with headings.

We'll mark them as Document 1 and Document 2 as I planned, and likely the final output should be a single
Markdown that includes both.

We must ensure to follow the formatting guidelines (clear headings, short paragraphs).

We have created quite short paragraphs (some are maybe a bit long but manageable).

We should ensure each major category is under an H2 or so, and subtopics under H3.

We did: 1. to 10. as H2 with numbers in heading text (like "## 1. ...", not sure if good or should we exclude
number? The guidelines didn't explicitly forbid numbering. It's okay as we wrote, I think).

58
We just need to ensure the user instructions said "Today is ... The user is at ... (not relevant, just context).
Focus that formatting is good. We have headings and lists as needed.

We should now produce the final combined response with both documents.

Let's double-check the request end: "I want 2 documents in pdf format, ... GO in order, no need to prioritize,
pdf version should be fine."

So yes, they want two separate docs presumably. We'll produce them in one output separated by a big
heading or a clear marker.

We did "# System Design Toolbox – Comprehensive Guide (Document 1)" and "# System Design Toolbox –
Quick Reference (Document 2)".

The guidelines mention images and to embed citations for them if used. We didn't plan images due to
complexity/time and not needed for textual info.

They said no need to search images specifically, and it's fine.

We have a huge text already (covering everything comprehensively, which they said they want
comprehensiveness).

Now let's create the Quick Reference (Document 2).

We need to condense the info into flashcard style. Perhaps a bullet list of key points under each category or
something like that.

Approach for Quick Reference: - Possibly a list of terms with short definitions, maybe one to three lines
each, grouped by the categories.

We can use heading for category, then bullet points for items.

Alternatively, could be Q&A style, but flashcard might mean basically key points.

Let's do bullet points because easy to scan.

We can fit maybe 2-3 bullet points per subtopic capturing the essence and perhaps mention one example
each.

Given time, I'll do: - "Databases & Storage" as a main section (like "## Databases & Storage - Quick
Reference"). Then bullet lines: - Relational DB: definition and key features (ACID, use for structured data). -
Key-Value: definition, usage (cache, fast access). - etc.

We have to be careful to keep them concise (flashcards style should be maybe one or two sentences each
ideally). But can do short bullet points.

59
But the guidelines said combine bullet lists for grouped ideas, which fits.

Also guidelines said "preserve any citations" in the quick ref too if any new info included. But likely we won't
cite repeated basic definitions, as we already cited in detail above. But if we say something like "ACID: ...",
maybe we can cite the ACID line again. Or could skip citations if it's clearly known or from prior text.

Better to cite if in doubt. We'll reuse some citations if it flows. It's a quick reference, but still might be helpful
for them to see sources if needed.

Alright, I'll try to incorporate citations if any short phrase taken or to support key definitions (like ACID short
def or CAP short def maybe from references).

However, quick reference might not need heavy citations. I'll include a few just to maintain compliance but
not too many to clutter.

We should ensure at least the first document had comprehensive citations (we did that a lot).

Alright, I'll produce the final answer now with both docs.# System Design Toolbox – Quick Reference
(Document 2)

Databases & Storage Technologies

• Relational Databases (SQL) – Structured tables with rows/columns and strict schema. Support ACID
transactions for reliability (all-or-nothing and consistent updates) 1 . Use B-tree indexes on keys
for fast lookups. Great for joins and multi-row transactions (e.g. banking systems). Scale vertically or
via read replicas; sharding is possible but adds complexity.

• Key-Value Stores – Simple dictionary-like databases optimized for fast get/set by key. Examples:
Redis, Memcached, DynamoDB. Often in-memory for low latency (sub-millisecond). Ideal for
caching (session data, computed results) and simple lookups 11 . No complex query capabilities (no
secondary indexes or joins typically). Scale horizontally by hashing keys to nodes (e.g. consistent
hashing in a cluster).

• Document Stores (NoSQL) – Store semi-structured data as JSON documents. e.g. MongoDB,
Couchbase. Flexible schema – each document can have different fields 52 . Allow querying by fields
within the JSON (with indexes on those fields). Good for data that naturally aggregates (e.g. a single
entity's info in one JSON) and for evolving schemas. Provide eventual consistency (by default) and
high scalability; some support ACID on a single document. Use cases: content management, user
profiles (where each record may have varying attributes).

• Wide-Column Stores – Distributed NoSQL databases using column families (sparse tables where
rows can have varying columns). e.g. Cassandra, HBase. Optimized for high write throughput and
denormalized data access. Data is partitioned by a primary key (often using hashing for distribution).
Great for time-series and big data workloads (IoT readings, logs) due to fast sequential writes and
reads by key range. Trade-off: weaker support for ad-hoc queries (you query by primary key or do
full table scans) 14 . Provide tunable consistency (Cassandra offers configurable read/write quorum).

60
 • Graph Databases – Designed for data with complex relationships. Nodes and edges with properties
store entities and connections (e.g. Neo4j, JanusGraph). Efficient traversals for queries like shortest
path, friends-of-friends 16 . Use cases: social networks, recommendation systems, fraud detection
(any domain with many many-to-many relationships). Typically query via graph query languages
(Cypher, Gremlin). Often not horizontally scalable in general case (many use single-server or limited
clustering) – optimized for relationship-centric queries that are hard for relational DBs.

• Time-Series Databases – Specialized for timestamp-indexed data. e.g. InfluxDB, TimescaleDB.

Store metrics/events with a time key; optimized for appends and time-range queries. Often include
built-in compression, downsampling (rollups), and retention policies. TimescaleDB is built on
Postgres (uses hypertables/partitions for time). Use cases: monitoring metrics, sensor readings,
financial ticks. Provide fast aggregations over recent time windows and can automatically drop or
archive old data. Query via regular SQL (Timescale) or a custom SQL-like (InfluxQL).

• Search Engines – e.g. Elasticsearch, Apache Solr. Use inverted indexes for full-text search –
mapping terms to documents 18 . Support free-text queries, relevance ranking, and complex text
operators (fuzzy search, wildcards). Often used alongside databases to provide search functionality
(e.g. searching product descriptions). Also used for log analytics (e.g. ELK stack). They store data in a
denormalized index optimized for text queries and aggregations. Scale by sharding indices and
replicating (Elasticsearch distributes documents by ID hash to shards).

• Blob/Object Storage – e.g. AWS S3, Google Cloud Storage, HDFS. Store large unstructured files
(images, videos, backups) with high durability and scalability. Access via a key (filename or ID) – no
complex query, just retrieve object or list by prefix. Often used for data lakes (storing raw data files)
and serving static content. Not a database per se, but an important storage tier for big data.
Integrates with CDNs for delivery and with computing frameworks (e.g. Spark can read from S3).

• Ledger/Immutable Store – Systems for append-only logs or financial ledger data. e.g. Kafka (log-
compacted topics), Event Store, or blockchains/ledger DBs. Ensure immutability of records (no
updates/deletes, only appends) – useful for auditing and event sourcing. Kafka’s log compaction
keeps latest value per key while retaining history to a point 53 54 . Ledger databases ensure an
ordered, immutable sequence of transactions (with cryptographic verification in some cases). Use
cases: audit logs, financial transactions (where you never delete an entry but possibly add
compensating entries).

Core Distributed Systems Concepts

• CAP Theorem: In a network partition, a distributed system can choose either Consistency or
Availability (but not 100% both) while maintaining Partition tolerance 19 . Consistency = all nodes
see the same data at same time (e.g. reads return latest write) 55 . Availability = system always
responds (even if some data is stale) 56 . Partition tolerance = system continues working despite
network splits. CP systems (e.g. ZooKeeper, some databases in majority mode) prefer consistency
(might reject requests during partitions) 22 . AP systems (e.g. Cassandra, DynamoDB in default mode)
prefer availability (serve requests on reachable nodes, sync up later) 23 . No distributed system can
avoid partitions, so design for either AP or CP behavior when they occur. CA without partition
tolerance is essentially a single-node setup (or assumes no partitions) 20 .

61
• ACID vs BASE: Two philosophies for consistency. ACID (Atomicity, Consistency, Isolation, Durability)
is the traditional RDBMS guarantee – strict transactions, always leave data in a valid state (e.g. bank
transfers either complete fully or not at all) 1 . BASE (Basically Available, Soft state, Eventual
consistency) is used by many NoSQL systems – allow temporary inconsistency but aim for eventual
consistency 24 57 . BASE systems sacrifice ACID’s immediate consistency to get high availability
and partition tolerance. For example, an ACID DB will ensure you never read uncommitted data,
whereas a BASE store might return slightly stale data but is always up. Think ACID = bank ledger,
BASE = social media feed (where slight delay or inconsistency is acceptable). ACID tends to require
global locking or consensus for transactions; BASE often uses async replication and conflict
resolution later.

• Replication: Maintaining copies of data on multiple nodes.

• Synchronous replication – write is applied to primary and at least one replica before confirming
success 26 . Ensures strong consistency (all acknowledged writes are on multiple nodes) but at cost
of higher latency (must wait for replicas) and reduced availability (if replica isn’t responding, write
may block). Example: Galera Cluster for MySQL (writes to all nodes via group commit).
• Asynchronous replication – primary returns success once local write is done, and replicas apply update
later 28 . This improves latency and availability (primary doesn’t wait) but can lose data if primary
fails before replica catches up. Most read replicas in databases are async (possible replica lag).
• Quorum (majority) replication – a middle ground used in systems like Dynamo/Cassandra or Raft/
Paxos. Require a quorum of nodes (e.g. > N/2) to acknowledge a write for it to be considered
committed 29 . Similarly, reads might query a quorum. If read quorum + write quorum > N, you get
strong consistency (at least one up-to-date copy is read) 29 . This is tunable consistency: you can
choose (W,R) such that you prefer consistency or availability.

• Leader-based vs leaderless: Many systems have a single leader (primary) handling writes and
propagating to followers (simpler ordering, e.g. MySQL primary-secondary). Others like Cassandra
use leaderless with hinted handoff and quorum coordination (more decentralized, but need read
repair).

• Sharding/Partitioning: Splitting data into partitions so each node handles only a subset. Strategies:

• Range Sharding: each shard gets a continuous range of keys (e.g. users A-M on shard1, N-Z on
shard2) 58 . Preserves key order (good for range queries) but can lead to hotspot if data not uniform
(e.g. all recent timestamps on one shard).
• Hash Sharding: apply a hash to the key and assign to shards (even distribution) 8 . Removes order
locality (harder for range queries by key), but spreads load evenly assuming hash is good.
• Consistent Hashing: a form of hashing that eases adding/removing nodes 10 . Keys and nodes are
hashed to a ring; a key goes to the first node with hash >= key’s hash. Only a small portion of keys
remap when a node joins/leaves (minimizing data movement). Used in distributed caches (e.g.
Memcached clients, Cassandra partitioner).
• Geo-partitioning: shard by geographic region or some category (e.g. EU customers vs US customers)
9 so data is localized. Helps latency and compliance (GDPR), but if one shard gets much heavier

load (uneven distribution), it can be an issue.

• Composite sharding: combination (e.g. first by region, then hash within region to multiple nodes) 30 .

62
• Note: After sharding, need a strategy to route requests (e.g. a lookup service or compute shard from
key). Also, join queries across shards are complex (need scatter-gather).

• Consensus Algorithms (Paxos/Raft/ZAB): Ensure multiple nodes agree on a value or sequence of

operations (even with failures). Used for leader election and replicated state machines (e.g. etcd,
Zookeeper, database consensus).

• Paxos: The classic consensus algorithm (Robust but hard to implement from scratch). It operates in
rounds with a proposer, acceptors, etc., to agree on one value. Multi-Paxos runs continuously to
agree on a stream of values (with one leader coordinating proposals). Paxos guarantees safety (no
two nodes decide different values) and liveness if majority alive and network stable, but can be
complex to reason about.
• Raft: A newer (2014) algorithm aiming to be more understandable. Raft elects a leader explicitly and
that leader sequences log entries. Followers replicate the log and acknowledge. If leader fails,
followers hold an election (using randomized timeouts). Raft enforces that any leader has the most
up-to-date log (via voting rules). It’s easier to implement and used in etcd, Consul, and many
systems. It provides the same guarantees as Paxos (and is equivalent in fault tolerance). Raft’s
popularity in open source means many libraries exist.
• ZAB (ZooKeeper Atomic Broadcast): Used by Apache Zookeeper for consistency. It’s similar to
Paxos/Raft with a leader broadcasting proposals (transaction logs) to followers and requiring
acknowledgments from a majority before committing. It has two phases: leader election, then
atomic broadcast. ZAB ensures total order broadcast and is optimized for recovery (when a new
leader comes, it syncs with followers). ZooKeeper (which uses ZAB) is often used as an external
coordination service for building lock or config services requiring consensus.
• Use Cases: Leader election (e.g. selecting primary in a distributed DB), consistent metadata storage
(etcd stores service config and uses Raft to keep it consistent across nodes), global distributed
locking.

• Typically require 2F+1 nodes to tolerate F failures (majority quorum). If too many nodes fail or a split
happens where no majority can form, system halts (prefers consistency over availability).

• Leader Election: The process by which nodes choose a single leader/master among them. This
often uses consensus or an external coordinator:

• A straightforward method is using ZooKeeper: create an ephemeral sequential znode – whoever

gets the smallest sequence is leader 38 . If leader dies (its session expires, znode gone), next in line
becomes leader. ZooKeeper provides the ordering and failure detection.
• Raft has leader election built-in via heartbeats: if followers don’t hear from leader, they vote to elect
a new one with a higher term.
• Etcd uses Raft, so the elected leader handles client requests requiring consensus.
• Kubernetes uses leader election for some controllers (they try to acquire a lock object in API server –
only one will succeed and act as leader).
• Application level: If not using a coordinator, one can implement by e.g. trying to update a known
row or key (“I am leader”) with atomic compare-and-set – if you win, you’re leader. Or using Redis
SETNX for a lock key with an expiry as a rudimentary leader election (the one who successfully sets
becomes leader until key expires or they renew).

63
• Leader Lease: Often, leadership is taken with a TTL (lease) so that if leader goes silent, the lease
expires and others can take over to avoid stuck situation.
• Leader election is needed in distributed scheduling, primary-backup setups, or any case where
exactly one node should perform an action (to avoid conflicts). For example, electing a primary
database out of replicas, or a cluster coordinator for cron jobs.
• The leader should ideally announce or others should watch the coordination mechanism to know
who is leader. Clients can then send requests to the leader if required (like for a primary database).

• Failure modes: Two leaders (split-brain) must be avoided – consensus algorithms ensure no split-
brain as long as majority rule holds. Using TTL and heartbeats helps – if network partitions, ideally
only the side with majority continues as leader, the minority stands down (this is how ZK/etcd works).

• Eventual vs Strong Consistency:

• Strong consistency: After a write is done, any read (to any replica) will see that write (system
appears as a single up-to-date copy). This typically requires coordination – e.g. blocking reads until
data is replicated or using a single leader for reads/writes. It’s necessary when correctness is
paramount (bank accounts, inventory counts). Achieved in CP systems or ACID databases (reads are
up-to-date after commit).
• Eventual consistency: Updates propagate to replicas asynchronously; if no new updates happen, all
replicas will eventually have the last value 31 . In the meantime, reads might see stale data. No
guarantee of how long “eventually” is – usually “quickly, under normal conditions”. This is common in
AP systems: e.g. DNS data, caches – if you update, another client might still see old data until it
refreshes. If the system is quiescent, state converges.
• Trade-off: Eventual consistency allows high availability and partition tolerance (no need to
coordinate every write) at cost of sometimes serving old data. Many NoSQL DBs (Cassandra,
Dynamo) are eventually consistent by default (though can often tune to strong if needed by waiting
for quorums).
• Read-your-writes & other models: Some systems offer session consistency where after you write,
your subsequent reads (from any replica) will reflect it (by routing or tracking version). That’s a
middle ground, ensuring a client sees its own writes without guaranteeing globally immediate
visibility.
• Use cases: If slight inconsistency is okay (user profile change taking a few seconds to show to
themselves or others), eventual is fine. For things like account balance, strong is needed.
• Example: In Amazon’s Dynamo (eventually consistent), two users might read different values during
a partition. When partition heals, a merge (conflict resolution) happens (could be last-write-wins or
custom merge).

• Developer burden: With eventual consistency, you must handle conflicts and possibly stale reads in
logic (e.g. suppressing outdated updates).

• Idempotency: An operation is idempotent if performing it multiple times has the same effect as
doing it once 32 . This is critical in distributed systems because clients or middleware often retry
requests on failure (network issues, timeouts) – an idempotent operation can be safely retried
without side effects.

64
• Example: Charging a credit card is not idempotent by default (if you send charge twice, customer is
charged twice). But making an order retrieval request is idempotent (get same result each time) if no
state change.
• Techniques to achieve idempotency:
◦ Assign unique request IDs (idempotency keys) for mutating operations. The server stores
the outcome of that operation keyed by this ID. If it sees the same idempotency key again, it
returns the cached result instead of performing the action again 59 . This is how many
payment APIs ensure a duplicate charge request isn’t processed twice.
◦ Put logic in server to detect duplicates: e.g. if the same record insert comes in, ignore the
second.
◦ Design APIs with put/replace semantics instead of incremental changes: For instance,
PUT /resource/123 {state=X} can be retried – it will just set state to X every time
(idempotent). Whereas POST /resource/123/toggle would be non-idempotent (each call
flips state).
◦ Consumer de-duplication: For message processing, track processed message IDs (in
database or memory) so if the same message arrives again, you skip it.
• Why necessary: Distributed systems often do at-least-once delivery. For example, message queues
may redeliver, or an HTTP client with timeout might reissue a request not knowing if server acted.
Idempotent handling ensures such duplicates don’t cause inconsistent state (like double-inserting an
item).
• HTTP idempotence: GET, PUT, DELETE are supposed to be idempotent by spec (no side effects on
multiple calls), whereas POST is not (could create multiple resources).
• Idempotent Examples: “Create user” can be made idempotent by using the same username or
client-provided ID – the server can say “409 Conflict, already created” for the retry, which the client
treats as success (since the user exists). Increment operations are not idempotent (doing it twice
changes result); setting a value is (setting twice is same as once).

• Note: Idempotency is about effects – you may still return the same result on retries or a reference
to the already performed action.

• Backpressure & Flow Control: Mechanisms to prevent overwhelming a slow consumer or resource
by a fast producer. It’s applying back-pressure upstream so that the production rate matches
consumption rate.

• In streaming systems (or even microservice calls), if one component produces too quickly, queues
can build up, leading to high latency or OOM. Backpressure techniques:
◦ Blocking/Throttling: The producer will wait (or be slowed) when the consumer can’t keep up.
E.g. TCP’s windowing: if receiver buffer is full, it advertises a zero window, making the sender
pause sending 60 . In frameworks like Reactive Streams, the subscriber requests N items
from publisher (only produce that many).
◦ Bounded queues with drop policy: e.g. an internal queue is only size 1000; if it’s full, either
reject new messages (shed load) or drop oldest (leaky bucket approach). This prevents infinite
backlog at cost of losing some data. For instance, a logging system might drop logs if
consumer can’t catch up, to avoid crashing.
◦ Push back signals: In gRPC or HTTP/2, you might get errors like 503 or specific headers
indicating client should slow down.
◦ Application-level backpressure: e.g. a service noticing high CPU or queue length might stop
reading new requests (or send slower responses to signal).

65
 • Implementations: Many message queues allow setting max unacked messages. Streaming
platforms like Kafka rely on pull model (consumer controls how fast it reads). In Akka Streams or
RxJS, backpressure is built-in via demand signals.
• Without backpressure: you get uncontrolled queuing (leading to out-of-memory or massive
latency spikes) or overloaded nodes (thrashing). It’s known as the “fast producer/slow consumer”
problem.
• Monitoring for backpressure: Watch metrics like queue lengths, consumer lag (Kafka consumer lag
= difference between produced and consumed offset), request latency. If these grow, it hints
producers outpacing consumers.
• Adaptive backpressure: e.g. if queue length > X, throttle input (perhaps sleep, or dynamic rate
adjustment).
• Example: A web server reading from clients uses TCP backpressure automatically. But between
microservices via HTTP calls, the caller might overwhelm callee by sending many concurrent
requests. A solution is to limit concurrency (caller only keeps N requests in-flight) or use a queue on
callee with a limit + quick fail if full (so caller gets error and can retry or slow down).
• Goal: Keep system stable under load by either slowing producers or buffering appropriately. It
ties in with rate limiting and load shedding (discussed separately) – backpressure is more dynamic
feedback, whereas rate limiting is more static rule-based.

Caching & Performance Techniques

• Cache Types:
• Client-side cache: Data cached on the end-user side (browser cache, mobile app cache). Reduces
redundant network calls (e.g. static JS/CSS files cached via HTTP Cache-Control ). Also includes in-
app caches of data (like an app remembers user preferences to avoid re-fetch). Improves latency and
offline capability but only benefits that user.
• CDN / Edge cache: Global network of caches (Cloudflare, Akamai) that store content closer to users.
Great for static assets and content with broad sharing. Reduces latency and load on origin.
Configured via HTTP headers or CDN rules. Example: images, stylesheets served from nearest CDN
node.
• Application-level cache: Within or alongside the server application. Could be an in-memory cache in
the app process (e.g. an LRU map) or a distributed cache like Redis/Memcached. Stores results of
expensive operations or frequent DB queries. For instance, cache user profiles in memory so you
don’t query DB repeatedly. Needs eviction policy for memory limit. Risk: if data changes, cache can
become stale (need invalidation strategy).

• Database cache: Either an internal cache (most DBs cache recently used pages in RAM) or an external
query cache. Some DBs had query result cache (MySQL had query cache) – it returns cached result if
same query repeats. But maintaining that coherency is hard (invalidated on table write). Usually
application-level caching is preferred to DB query cache for flexibility. Another aspect: using replicas
as a cache for reads (not exact cache but alleviates primary).

• Cache Eviction Policies: When cache is full or entries expire, decide what to remove:

• LRU (Least Recently Used): Evict item that hasn’t been accessed for the longest time 34 . Assumes
recent items are more likely to be used again (good for temporal locality). Simple to implement via

66
 linked list tracking recency. Widely used (e.g. Memcached’s default, CPU caches at line level are
similar to LRU).
• LFU (Least Frequently Used): Evict item with smallest access count (the least popular) 48 . Keeps
frequently accessed items even if not recently used. Needs a frequency count per item (and maybe
aging mechanism to avoid stuck-on old popular items). Good for cases where some items are
consistently hot.
• FIFO (First-In First-Out): Evict oldest item by insertion time (ignores usage). Simple but can discard
items still in heavy use just because they were added earlier. Rarely ideal, but sometimes used in
special scenarios or combined with others.
• TTL-based (Time-to-Live): Each item has an expiration time. Evict items after certain duration
regardless of use. Ensures refresh of data (avoid stale indefinitely). Often used along with above
policies – e.g. Redis allows setting a TTL on keys; item is removed when TTL expires, or earlier if
memory needed (depending on policy configuration).
• Random: Randomly evict an entry. Surprisingly, in practice this can perform okay and is very simple
(and avoids worst-case patterns for LRU), but not optimal usually. Redis has a variant where it
samples a few random items and evicts the LRU among those (approximate LRU).
• Adaptive policies: e.g. ARC (Adaptive Replacement Cache) which balances recency and frequency by
having multiple lists. ARC can outperform vanilla LRU or LFU on certain mixed workloads.
• Note: The best policy may depend on access pattern. LRU is a good default for many. LFU might do
better if a small subset is very frequently used (so it won’t evict them even if a slight gap in use).

• Cache stampede mitigation via proactive eviction: (See later sections for more on stampede and
hot keys).

• Write Strategies (Cache & DB): How writes propagate through cache:

• Write-Through: On data update, write is done to cache and to the underlying datastore
simultaneously 26 . The cache always stays current. Read hits get latest data. Slows writes (since
must update two places on same request) but keeps data in cache fresh. E.g. updating a user’s info:
you update DB then immediately cache the new value (or do in reverse order for atomicity, but
essentially both places). Common approach: use cache as primary read store but still rely on DB for
persistence – on update, put new value in cache and DB.
• Write-Around: On write, update goes directly to DB, and cache is bypassed (not updated). The cache
entry for that data is either invalidated or allowed to expire. The next read will miss and fetch from
DB (then cache it) 45 . This avoids caching data that might not be read soon (saving cache space).
But downside: a read right after write will be a miss (stale until loaded). Good if writes are frequent
but reads rare for that data.
• Write-Back (Write-Behind): Write updates are made to cache only (quick), and asynchronously
persisted to DB after a delay or at intervals 28 . This yields fast writes and can batch multiple
updates to one DB write (improving throughput). But it’s risky: if the cache node dies before flushing,
data can be lost (need robust cache persistence or replication). Also, the database will lag behind,
which might confuse systems directly reading the DB. Use cases: analytics aggregates being cached
and flushed later, or scenarios where eventual persistence is acceptable. Systems like Redis with AOF
persistence can be seen as write-back (commands recorded and persisted asynchronously).
• Example: A cache-as-database system like Redis as primary store: application writes to Redis (fast),
and Redis asynchronously writes to disk (and/or a relational store) in background. Many modern
systems actually treat an in-memory store as source of truth and batch-sync to disk.

67
• Typically, write-through + eviction is common: on update, update DB and cache; on eviction, the
data still in DB. Write-back tends to be for specialized high-performance scenarios.
• Write-around is often used with caches like Memcached when you don’t want to thrash cache on
bulk writes (you let reads bring data lazily).

• Cache aside (Lazy loading) approach: not exactly in above terms but common: Application code
checks cache, if miss then fetch from DB and populate cache (and optionally on write, you update DB
then invalidate cache entry). This is effectively a form of write-around (on writes, you remove from
cache; on next read, cache will load updated data from DB). It keeps cache coherent at cost of one
extra DB read on first access after write. Many use this because it’s simple: DB is source of truth,
cache only has data when read at least once, and each update ensures stale data not served by
removing it from cache.

• Hot Key Mitigation: When a particular cache key becomes a hotspot (extremely high traffic), it can
overload one cache node. Techniques:

• Key Spreading (Random suffixes): Duplicate the cached value under N different keys and randomly
choose one on each access 36 . For example, instead of all users requesting popular-item key,
use popular-item:1 , popular-item:2 , ... :N . Distribute these keys across servers. This
spreads the read load among multiple nodes at cost of some inconsistency (if value updates, need to
update all N keys) and memory overhead (N copies). Useful for read-heavy mostly static content (like
a viral video metadata). Twitter used this for hot timelines – e.g. break a celebrity’s follower requests
across shards by adding a random number 36 .
• Shard by User or Attribute: If a small set of keys is hot because of many users, consider
partitioning those users or grouping requests. E.g. rather than one key for “celebrity’s tweets”,
maintain multiple keys each for a subset of followers. Each subset key gets part of traffic (similar to
above approach, just viewed differently).
• Request Coalescing: Prevent stampede on cache miss: if many requests ask for key X and X is
not in cache, let only one go fetch from DB while others wait, then all get the result 40 41 . This
ensures a thundering herd doesn’t hit the database. Many caches or CDNs implement this (called
cache locking or single flight). Without it, a cache miss for a popular key could result in hundreds of
DB queries in parallel. In code, one can use a mutex or "promise" to coordinate: first request triggers
DB fetch and locks the key, others subscribe to the result.
• Hierarchical Caching: Use layered caches: e.g. each app server has a small local cache (L1) and a
distributed cache is L2. A hot key will be served from local memory for repeated access on the same
machine, reducing hits to centralized cache. Also, a CDN in front of origin cache similarly splits load.
Hierarchy means fewer requests hitting the deepest layer. This mitigates hot key effect by spreading
across layers – e.g. if one key is popular globally, at least it might be cached in each region’s CDN
node (so origin sees less traffic).
• Real-time Scaling: If one cache node is overwhelmed by a hot key, auto-scale cache cluster (add
node and re-hash keys) or temporarily increase capacity for that key (maybe manually copy that key
to another node and direct some traffic there). Not always quick or easy though.
• Celebrity strategy (application-level): Sometimes not purely caching – e.g. Twitter doesn’t push
every tweet from a celebrity to all followers’ caches (which would create a hot fan-out). Instead they
might handle celebrity timelines differently (like fans pull directly or use separate infrastructure).
Designing separate code paths for outliers (“big keys”) can be effective.
• Tune TTL / refresh strategy: Hot keys might be set to longer TTL to avoid frequent re-computation
or DB fetch (with risk of slightly stale data, but better than hammering DB).

68
 • Monitoring & Alerts: Recognize hot key situations by monitoring cache keys QPS. Some caching
systems provide stats for top keys. If identified, one can pre-warm caches or route traffic
intelligently.

• Messaging & Streaming

(See next section for messaging patterns and streaming details bullet points.)

Messaging & Streaming

• Message Queues (RabbitMQ, SQS): Facilitate async, one-to-one message processing. Producers
send messages to a queue, a single consumer (in a group) receives each message (competing
consumers). Ensures asynchronous processing and load leveling (e.g. background job processing).
RabbitMQ – runs on-prem or cloud, supports complex routing via exchanges, acknowledgements (to
ensure at-least-once delivery), and features like DLQ. SQS – cloud queue service, simple FIFO or at-
least-once delivery, consumers poll for messages. Use cases: task queues (send email, generate
PDF), buffer spikes (queue up tasks if consumers busy), decouple services (order service enqueues
“ship order” message for warehouse service). Key patterns: ACK/NACK & retry – consumer
acknowledges on success, or message requeues on failure (with optional delay). This provides
reliability (no message lost, but possible duplicates). Generally messages are removed from queue
once processed (not persisted long-term).

• Log-Based Streaming (Kafka, Pulsar, Kinesis): Provide a durable append-only log of events,
supporting publish-subscribe and replay. Producers append events to a topic (which is partitioned
for scale). Consumers can read sequentially and maintain an offset – multiple consumers (or
consumer groups) can independently read the same stream. Kafka – widely used, stores events for a
retention period (e.g. 7 days) regardless of consumption, enabling re-read or late joiners 61 62 .
Consumers in a group get load-balanced partitions (each message goes to one consumer in the
group = competing consume), but different groups each get all messages (pub-sub). Great for event-
driven architectures, analytics pipelines (multiple downstream consumers can tap into the data).
Pulsar – similar but with separated compute/storage and multi-subscription modes. Kinesis –
managed stream on AWS, similar concept (shards ~ partitions). These systems often allow real-time
processing: e.g. use Kafka Streams or Flink to compute rolling aggregates as events flow. They
ensure ordering per partition and scale horizontally by partitioning keys. Use cases: user activity
events, log aggregation, metrics, trade events – any scenario to process streams and possibly replay
for new consumers (e.g. recompute something from history).

• Pub/Sub (Google Pub/Sub, Redis Streams): Pattern where messages are broadcast to multiple
subscribers. Many-to-many relationship. Google Cloud Pub/Sub – a managed service where
producers send to a topic, and multiple subscribers (via subscriptions) each get a copy of each
message (at-least-once delivery to each sub). Often used to fan out events to different services (e.g.
an “order placed” event goes to billing service and notification service, etc.). Redis Pub/Sub – built-in
but not persistent (subscriber must be online to get message). Redis Streams – persistent log
structure in Redis (acts like Kafka-lite), supports consumer groups (like competing consumers) and
retaining history. Pub/Sub ensures fan-out distribution. Use cases: notify multiple systems of an
event (e.g. user signup triggers welcome email service and analytics tracking). Also used for inter-

69
 component comms in microservices without coupling (each service just listens if interested). Ensure
designing idempotent subscribers because typically at-least-once (could get duplicates).

• Fan-Out & Fan-In Patterns:

• Fan-Out: One event triggers multiple parallel processes (classic pub-sub). For example, an image
upload event could fan-out to services generating thumbnails, scanning for viruses, updating
database, etc., all concurrently. Often implemented via pub/sub topics or multiple queues bound to
one exchange (in RabbitMQ, a fanout exchange duplicates message to all bound queues).
• Fan-In: Aggregating results from multiple sources. For example, a workflow where multiple tasks
compute parts and one aggregator service collects them. A concrete pattern is map-reduce –
mapper workers produce outputs to a common queue that a reducer consumes (fan-in into reducer).
Fan-in often needs a mechanism to know when all parts arrived (could use counters or a final
message indicating completion).

• Fan-in can also refer to many producers feeding one queue (e.g. logs from many servers all go to
one logging queue – “many in, one out”).

• Dead Letter Queues (DLQ): Special queues where messages that cannot be processed are routed
44 . E.g. if a message is malformed or fails processing a certain number of times, it’s sent to DLQ

instead of retrying forever. This prevents stuck messages blocking the main queue. Operators can
inspect DLQ to debug issues. Implementations: RabbitMQ can send messages to a DLX (Dead Letter
Exchange) after X rejections or expiration; SQS DLQ target for messages that exceed retry count.
Always monitor the DLQ – presence of messages indicates poison messages or system bugs.

• Retries & Exponential Backoff: When a message or request fails, often you retry, but doing so
immediately and aggressively can worsen issues (like hammering a down service). Exponential
backoff means wait progressively longer on each retry attempt (e.g. 1s, then 2s, then 4s, up to some
max) 45 . Jitter (random small addition to wait) is often added to avoid many clients retrying in sync
(thundering herd). For messaging: if consumer fails to process, it might not NACK immediately but
instead requeue with a delay (some queues support a visibility timeout or delay). For example, SQS
offers a Visibility Timeout and can move message to DLQ after N tries; if you set a visibility timeout
and don’t delete message, it reappears for retry after that time. In APIs: if an HTTP request to
external service fails or times out, client should retry after a delay (and perhaps increase delay on
each attempt, up to a limit). This improves resilience to transient errors while reducing load during
outages. Make sure operations are idempotent if you retry them (to avoid side effects). Also consider
circuit breaking: if many failures, stop retrying for a short time – integrated with backoff (discussed
in service mesh/circuit breaker).

• Messaging Order & Delivery Guarantees:

• Order: Some systems guarantee order (Kafka – per partition; RabbitMQ – per queue if one consumer
at a time). Others like SQS standard do not guarantee ordering (unless using FIFO queues).
• Delivery: At-least-once (most MQs – might get duplicates), at-most-once (if you choose not to retry
or use auto-ack, possible loss), exactly-once (hard, requires deduplication or transactions – e.g.
Kafka with idempotent producers + transactional consume can achieve effectively exactly-once from
producer to consumer processing).

70
 • Design consumers to handle duplicates (idempotency keys, etc.) especially if at-least-once. Use at-
most-once only if occasional loss is acceptable and it simplifies things.

Networking & APIs

• REST (HTTP/JSON APIs): Conventional web API style using HTTP verbs on resource URIs. Stateless:
each request carries auth and context; server doesn’t keep client state between calls. Uses standard
methods: GET (read), POST (create), PUT (create/replace), PATCH (partial update), DELETE (remove).
Responses usually JSON. Leverages HTTP features: caching (GET responses can be cached if so
headered), codes (200 OK, 404 Not Found, etc.), SSL/TLS for security. Easy to consume (every
language can do HTTP). Good for public APIs and microservice boundaries where simplicity and
interoperability matter. Downsides: multiple round-trips to fetch related data (under-fetching/over-
fetching issues), no strict schema (but can use OpenAPI/Swagger for documentation). Example:
GET /users/123 returns JSON of user 123; POST /orders with JSON creates an order. REST is
synchronous request-response over TCP (often HTTP/1.1 or 2). Idempotency: GET/PUT/DELETE
ideally idempotent, POST generally not. Identities often passed via tokens or API keys in headers
(e.g. Authorization: Bearer token).

• gRPC (Remote Procedure Calls over HTTP/2): A high-performance binary protocol from Google.
Clients call methods on a stub as if it’s local; underlying uses HTTP/2 and Protocol Buffers for
serialization. It's schema-driven – you define a .proto file with service methods and message
types, generating strongly-typed client/server code. Supports bidirectional streaming (client and
server can send a stream of messages) in addition to unary calls. Because it runs on HTTP/2, it
benefits from multiplexing (multiple concurrent calls on one connection) and compression. Very
efficient in both size and processing (binary vs JSON). Often used for microservice inter-service
communication in polyglot environments, where performance and type safety are desired. Not
directly browser-friendly (browsers don’t speak gRPC natively – need gRPC-Web which wraps in
HTTP/1.1 or uses a proxy). Example: a UserService with RPC GetUser(UserRequest) returns
(User) – the client calls [Link](req) and gets back a User object. gRPC also handles retries,
deadlines (you can set a timeout per call), and uses status codes distinct from HTTP (mapped via
trailers). It usually requires both client and server to use gRPC libraries (so it's great for controlled
environments – like all microservices with known languages).

• GraphQL (Query Language for APIs): A flexible query API where the client asks exactly for the data
it needs in a single request. GraphQL has a schema (types, queries, mutations) defined on server.
Clients send a query specifying fields (possibly nested) and server resolves and returns JSON of just
those fields. Reduces round-trips – e.g. client can get user and their orders in one go (instead of
multiple REST calls). Also solves over-fetching – client doesn’t get extra fields it doesn’t want.
GraphQL supports mutations (writes) and subscriptions (for pushes, often via WebSockets). It
requires a GraphQL server to resolve field requests (which might involve calls to databases or other
services). Benefits: strong typing (clients can validate queries against schema), good for rapid front-
end development (front-end can shape data requirements easily). Downsides: more complex server
implementation, caching is harder (since queries can vary – though you can cache at field resolver
level or use persisted queries). Also, one complex GraphQL query can be expensive (equivalent to
many SQL joins) – need to guard with query cost analysis or depth limiting to prevent abuse.
Example query:

71
 {
user(id: 123) {
name,
orders(limit: 5) {
id, total
}
}
}

returns:

{ "user": { "name": "Alice", "orders": [ {"id":1,"total":99}, ... ] } }

Allows rapid iterations on frontend without changing backend for each new combo. Many
companies use it to unify multiple microservice data sources behind one API. Usually operates over a
single HTTP endpoint (POST requests with query).

• WebSockets (Full-duplex Communication): A protocol that upgrades an HTTP connection to a

persistent bi-directional socket. Both client and server can send messages anytime, enabling real-
time interactions (no need for client polling). Used for chat apps, live notifications, collaborative apps
(e.g. Google Docs), gaming. After the initial handshake (HTTP Upgrade), it’s not HTTP anymore – it’s a
TCP channel that can carry text or binary frames. WebSocket messages can be defined in any format
(often JSON or protobuf, or custom). Because connection stays open, scaling WebSockets means
having many long-lived connections (need efficient event-loop servers, and often sticky sessions so
all messages for a client go to the node where their socket lives, unless using a pub-sub backbone to
broadcast to correct node). WebSockets excel where you need low-latency updates from server to
client (e.g. stock price updates). Also useful for client-to-server streaming of events (e.g. IoT device
sending sensor data continuously). Alternative server-push tech: Server-Sent Events (SSE) – simpler
one-way streaming over HTTP. But WebSocket is more flexible (bi-directional). Example: A trading
platform opens a WebSocket to server, server pushes price changes to client as they happen; client
can also send trade orders over same socket. Ensure heartbeats to detect disconnected clients.
WebSockets lack some of HTTP’s goodies (no built-in auth on every message – usually you
authenticate during handshake and then trust the connection). Typically, one would still use another
API (like REST/GraphQL) for initial data and WebSockets for dynamic updates.

• Load Balancing Algorithms:

• Round Robin: Distribute each new request to the next server in a list (cycle through). Simple and fair
if requests are similar in cost. Doesn’t account for current load differences. Often weighted round
robin is used (server A gets weight 2 – get two requests for every one request to weight1 server).
• Least Connections: Send traffic to the server with the fewest active connections (or requests) at that
moment. Assumes servers with fewer connections are less loaded. This adapts if some requests are
long-lived or some servers slower. Good for scenarios where load isn’t uniform per request. Requires
LB to track connections count or load metrics.

72
• Consistent Hashing: Use a hash of some attribute (e.g. client IP or session ID) to pick a server 10 .
Ensures the same client goes consistently to the same server (useful for session stickiness without
cookies, or caching locality – the request for a certain item always hash to the same backend that
might have it cached). If a server is added/removed, consistent hashing minimizes content re-
distribution (only some portion of keys remap). However, it can lead to uneven distribution if keys
aren’t uniform or if cluster size changes drastically (though hashing handles average distribution).
• Others: IP Hash (a form of consistent hashing on IP), Random (some LBs use random pick which in
large numbers gives even distribution, sometimes combined with least loaded of two random picks
= “power of two choices” which approximates least connections with much lower overhead).
Geographic LB (route to nearest region).
• LBs can operate at L4 (transport) or L7 (application). L4 LB (like AWS NLB or TCP round robin)
doesn’t look at HTTP – just spreads connections. L7 LB (like AWS ALB, Nginx, HAProxy in HTTP mode)
can do content-based routing (e.g. path-based: /images goes to one cluster, /api to another)
and smarter distribution but with slightly more overhead.
• Sticky Sessions: If using round robin but need session affinity, an LB can inject a cookie or use
consistent hashing on session ID such that a user’s requests go to the same server (to use in-
memory session). But modern practice is to use a shared session store so session stickiness isn’t
needed – allowing truly stateless scaling. Still, for certain caches or WebSocket, stickiness or
consistent hashing approach is needed.
• Resilience: LB also monitors health – it should stop sending to nodes that fail health checks (e.g.
HTTP 5xx or no response).

• In microservices, often a service mesh or intelligent client (like gRPC client can round-robin across
addresses) does load balancing as well.

• Rate Limiting: Controlling the rate of requests a client or API consumer can make, to prevent abuse
or ensure fairness. Usually expressed as requests per second or per minute. Algorithms:

• Token Bucket: Tokens added to a bucket at a fixed rate (say 5 tokens/sec up to bucket size 10) 63 .
Each request consumes a token; if bucket empty, request is denied (or queued until token available).
Allows bursts up to bucket capacity, then enforces steady rate 63 . This is commonly used because
it’s simple and allows small bursts while keeping long-term rate in check.
• Leaky Bucket: Conceptually, a fixed-rate outflow – like a queue that outputs at a constant rate.
Incoming requests enter the queue; if it’s full, they’re dropped. This smooths bursty traffic to a
uniform flow. Often token bucket and leaky bucket result in similar external behavior (token bucket
is easier to implement, leaky bucket gives more strict spacing).
• Fixed Window & Sliding Window Counters: Simpler approach: count requests in a time window
(e.g. per minute). Fixed window resets every minute – easy but allows bursts at boundary (could do 59
in end of one minute and 59 at start of next = 118 in 60-second span if limit 60/min). Sliding window
uses two windows or moving calculation to even that out – essentially measure rate over the last N
seconds continuously. Implementation might track timestamps of requests in a rolling log, or
maintain counters for current and previous window with weighting.
• Examples: “100 requests per user per minute” – after 100 requests in <60s, further requests are
throttled (HTTP 429 Too Many Requests). This can be implemented with a counter in Redis that
resets each minute, or a token bucket adding ~1.66 tokens/sec.
• Distributed rate limit: If you have multiple server instances, a centralized store (like Redis or a
dedicated rate-limit service) is used to track counts/tokens so that limits apply across all nodes. Or

73
 each node can enforce and the LB ensures stickiness for rate limiting key – but central coordination
is simpler.
• User vs IP vs API key: Rate limits often defined per API key or user account. IP limiting is coarse
(good for public APIs without auth to mitigate bot abuse). Authenticated APIs use per-key limits (e.g.
free tier 10 req/s, paid tier 50 req/s). Also global rate limits might protect backend (e.g. overall API
1000 req/s across all).
• Bucket capacity for burst: Without some burst allowance, clients with minor concurrency might
unfairly get limited. Token bucket’s capacity allows short burst then average.
• Leaky bucket in code: could be implemented as a queue with a timer draining it. But token bucket is
easier: track next allowed timestamp or current tokens.
• Sliding log: store timestamps of each request, drop ones older than window to compute current
rate; this is accurate but memory heavy if lots of requests (optimizations exist like approximate
counts).
• Nginx and others implement rate limit via token bucket (with leaking/dripping set by rate ).
• Excess handling: Usually respond with 429 Too Many Requests and maybe in header
Retry-After with seconds to wait. Clients should back off if receiving 429.

• Rate limiting protects against abuse (e.g. someone scraping or doing password brute force). Also
ensures one client doesn’t starve others on a multi-tenant API.

• API Gateway: A gateway sits at the edge of your system (between clients and backend services). It
aggregates and manages API calls:

• Throttling/Rate Limiting: Enforces global or per-client request limits (as described above) at the
gateway so that bad actors don’t overwhelm internal services 64 .
• Authentication & Authorization: Verifies credentials (API keys, OAuth tokens, JWT) and can reject
unauthorized calls up front. It might integrate with an identity provider. Also can do things like check
user roles and allow/disallow certain endpoints (basic authZ).
• Routing & Composition: Routes requests to appropriate microservice(s) based on URI or other info.
E.g. /api/users/* -> User Service, /api/orders/* -> Order Service. Can also combine
multiple service responses into one (though that borders on BFF pattern). For example, gateway
could on one endpoint call 3 services and merge data for convenience (though heavy logic in
gateway might be avoided in favor of dedicated aggregator service).
• Logging, Monitoring, Analytics: Gateway logs all requests, response codes, times. Can produce
metrics (QPS per endpoint, error rates) and feed into monitoring. Provides a single point to collect
API usage stats (like which endpoints are most used, which consumers use them).
• Caching: Gateway can cache responses for certain endpoints to reduce load on services (e.g. cache
static configuration data responses).
• Request/Response Transformation: Modify headers, URLs, or payloads. E.g. add a correlation ID
header, or convert between protocols (XML to JSON). Some gateways also do schema validation or
enforce policies (like payload size limits).
• Security Controls: Act as a WAF (Web Application Firewall) – blocking known malicious patterns (SQL
injection strings, etc.), enforcing HTTPS, CORS headers injection, and mitigating DoS (through
throttling or challenge).
• Cross-cutting concerns centralization: Developers of microservices can focus on core logic, while
gateway handles cross-cutting concerns (auth, monitoring, etc.) uniformly for all.
• Examples: Kong, Apigee, AWS API Gateway, Nginx (with lua or other plugins), Azure API Mgmt. They
often support plugin architecture for custom logic.

74
• Active vs passive gateway: Some use gateway pattern, others might let clients directly call services
with a service mesh handling some of these concerns. But for external clients, an API gateway is
common.
• Versioning & Routing: Gateway can route based on version (e.g. /v1/ vs /v2/ to different
service versions) or even do canary releases (some gateways can send X% of traffic to a new version).
• Integration: Many gateways can integrate with monetization (tracking usage per client for billing),
developer portals (for exposing docs, managing keys).

• Example Flow: Client calls GET [Link]/orders/123 with JWT token. Gateway
authenticates (checks JWT signature and claims). It rate-limits (ensures client hasn’t exceeded quota).
It then routes to Order Service (maybe as internal REST or gRPC). It waits, perhaps logs latency.
Order Service responds; gateway might strip some internal headers, add security headers like CSP or
CORS for client, and send response to client. Meanwhile, it logs request outcome to logging system.
If Order service was down, gateway could quickly return a friendly error or a cached response if
applicable.

• Service Mesh (Istio, Linkerd): Focuses on internal service-to-service communication management

using sidecar proxies (like Envoy) for each service instance. Key features:

• Service Discovery & Load Balancing: Each service call is intercepted by sidecar which knows the
healthy instances of target (via mesh control plane). It does client-side load balancing (often simple
round-robin or least-connections among service instances).
• mTLS (Mutual TLS) and Encryption: Mesh can encrypt all inter-service traffic and handle
certificates. Each service gets a sidecar that handles TLS handshake with others – ensuring all traffic
inside cluster is secure and authenticated (knowing which service is calling which via cert identity).
• Traffic Policies: Retries, timeouts, and circuit breakers at the proxy level. E.g. if service B is slow, A’s
sidecar can timeout requests after X seconds and optionally retry to another instance or just fail fast
47 . Circuit breaking: if many calls to service B fail, A’s sidecar can stop calling B for a cool-off

period (immediately fail calls instead of making useless attempts) 46 . This prevents cascading
failures – e.g. if B is down and A keeps blocking on calls, eventually A’s circuit breaker trips and calls
fail quickly, allowing A to perhaps degrade functionality instead of hanging.
• Observability: Mesh proxies emit metrics (like request counts, error counts, latency distributions)
and traces (each proxy can add tracing headers, so a distributed trace spans proxies to follow a call
chain). This gives uniform telemetry across languages (doesn’t matter if service in Go or Java – Envoy
proxy reports metrics).
• Traffic Shifting / Canary: Fine-grained control of routing between service versions. E.g. route 5% of
traffic to v2 of a service and 95% to v1 via sidecar rules, gradually shifting more if all goes well. Also
can do header-based routing (like if user=beta tester, go to v2).
• Fault Injection & Testing: You can configure proxies to deliberately inject faults (e.g. add 2s delay
for 5% of calls, or return 500 errors randomly) to test resiliency.
• Circuit Breaker specifics: Often implemented via outlier detection – e.g. Envoy can eject an
unhealthy instance from pool if consecutive failures exceed threshold, or if average latency too high.
That’s similar to an auto circuit-break for that instance.
• Difference from API Gateway: Mesh is primarily east-west (internal), Gateway is north-south (in/out
of cluster). Mesh works at request-level between services without requiring code changes, whereas
gateway is a singular entry point for external.
• Istio/Linkerd implementation: They inject a sidecar container with Envoy (for Istio) in each pod.
The app’s outbound calls are intercepted (via iptables) to Envoy, which then does service mesh logic

75
 and forwards to destination’s Envoy, which forwards to destination app. Control plane (Istio’s pilot
etc.) distributes configs and does service discovery (often pulling from Kubernetes service registry).
• Overhead: There’s some latency overhead per call (microservice call now goes through 2 proxies).
Generally small (milliseconds), but at huge scale can add up. Many consider it worth the features.
• Use cases: Large microservice deployments where consistent observability and reliability policies are
needed. Companies use it to avoid writing duplicate networking code (retries, auth) in each service –
mesh handles it declaratively.
• Example: Service A calls [Link] The call goes from A to A’s Envoy (localhost). Envoy
consults its cluster config, chooses an endpoint for B (and perhaps sees last 2 attempts failed so it
waits – circuit open). If okay, it dials B’s Envoy at chosen IP:port. B’s Envoy terminates TLS (if mTLS),
sees request is allowed (maybe checks service A is allowed to talk to B via policy), then passes to B.
Response comes back similarly. During this, Envoy measured that B took 800ms and gave HTTP 500,
and this is the 3rd such error – it can trip circuit so next calls from A to B fail instantly for a short
period. Envoy also reports metrics to Prometheus: A->B error count increased. Devs can see success
rate between A and B in dashboards. Meanwhile, they had deployed B v2, Istio rule sends 10% of A’s
traffic to B v2’s cluster. Envoy follows that rule to route some requests to new version.

Scalability & Reliability Techniques

• Horizontal vs Vertical Scaling:
• Vertical Scaling: Scale up – give a node more resources (CPU, RAM, SSD). E.g. move from a 4-core to
16-core database server. This can handle more load on a single instance. Simpler (no code change),
but has limits (max capacity of hardware) and often non-linear cost (very large instances cost
disproportionately more). Also a single point of failure remains (one big server).
• Horizontal Scaling: Scale out – add more nodes/instances and distribute load. E.g. 10 web servers
each handling part of traffic behind a load balancer. Allows virtually unlimited scaling by adding
commodity servers. Requires the system to be designed for distribution (statelessness or proper
data partitioning). More complex (need load balancing, data synchronization or sharding, etc.) but
essential for large scales. Horizontal scaling improves redundancy (if one node fails, others still
serve – no total outage, whereas a single big node failing = downtime).
• When to vertical: If workload can’t be easily distributed (e.g. some monolithic DB that doesn’t
shard), or simpler at small scale – often you “scale up” until you hit a performance/cost wall, then
scale out. Many start with vertical (one bigger DB) due to simplicity.
• When to horizontal: Web tiers and stateless services are easy to horizontal scale – use LB and add
instances for more throughput. Also required when data set or traffic far exceeds what one machine
can handle. Horizontal is the only option for web-scale systems (Google, etc.). Also for reliability –
multiple nodes across racks/regions avoid single point of failure.
• Both can be combined: e.g. scale up each node to a point and also have several of them (e.g. a
cluster of decent-sized servers, not either tiny many or one huge).
• Elastic scaling: In cloud, you can use auto-scaling horizontally – spin up/down VMs or containers
based on load (vertical scaling is slower – resizing VMs on the fly is possible but not as instant).
• Example: a website on one server (vertical: upgrade from 2x to 8x memory to handle more users).
Later, horizontal: deploy 4 servers, each behind LB, each maybe smaller than that big one but
combined power more. Database: initially one large DB machine, later perhaps cluster or sharded or
use read replicas horizontally for read scale.

76
• Challenges: Horizontal requires handling distributed state (sessions moved to shared store, not on
one server’s memory) and eventual consistency issues. Vertical may hit diminishing returns (e.g. CPU
might be half-utilized but memory is maxed – one resource becomes bottleneck).

• Multi-Region Strategies: Deploying system across geographically separated data centers:

• Active-Active: All regions active serving traffic. Data is replicated between regions (often
asynchronously). Users connect to nearest region (low latency). If one region fails, others still serve
(improved resilience). The difficulty is data consistency: if a user in EU updates data, a user in US
might read stale data until replication. Typically, active-active systems either accept eventual
consistency or partition users by region. For truly synchronized active-active, one might use
distributed databases (Spanner, etc.) that use atomic clock or consensus among regions – with
higher latencies. Many systems do active-active for reads but designate one region as primary for
writes of a specific record (to avoid conflict) – effectively partitioning by record. Example: DNS is often
active-active (multiple A records globally). Cloud providers global databases (like Cosmos DB with
multi-master) support multi-region writes with conflict resolution.
• Active-Passive (Active-Standby): One region active, others passive (standby). Standby has up-to-date
or near-up-to-date copy of data (via replication). It’s not serving normal traffic until failover. If
primary region goes down, a failover procedure promotes a standby to primary (DNS switch or
config change). During normal times, all writes go to one region (simpler consistency, ACID possible
in primary DB). Passive might be used for read-only queries or kept completely idle. E.g. use AWS
RDS primary in us-east, with a read-replica in eu-west as standby; if us-east fails, promote eu-west as
new primary.
◦ RPO (Recovery Point Objective) – how much data loss can occur: with async replication,
passive may lag by seconds; any primary writes in that window could be lost on failover (RPO
= a few seconds). With sync replication (if possible across regions), RPO ~ 0, but with cost of
latency.
◦ RTO (Recovery Time Objective) – how long to switch: could be seconds to minutes (automated
failover can be fast, but DNS propagation or manual steps can slow it).
• Replication Lag Handling: In any multi-region async replication, lag is a concern. Systems mitigate
by:
◦ If using active-passive, typically use nearly synchronous or small buffer replication and
monitor lag. Possibly stop accepting writes in primary if lag grows too much (to not get too
far behind).
◦ In active-active eventual, design such that slight lag is acceptable, or use conflict-free data
types (CRDTs) or last-write-wins on conflicts.
◦ Use read-after-write forwarding: e.g. after a user writes data in region A, if they travel to
region B soon, their reads might go to B’s region which is behind – you may need to detect
“this user’s last write was at A, ensure B has it (maybe by forcing read from A or waiting)”.
Some systems route user to “home region” always to avoid cross-region consistency issues.
◦ Conflict resolution: e.g. if two regions update same record simultaneously (active-active),
have rules (timestamp wins, or merge fields, or flag conflict for manual resolve).
• Latency trade-off: Active-active gives lowest local latency (writes happen nearest user, and reads
local). But then cross-region consistency is eventual, so global view is not always up-to-date. Active-
passive centralizes writes so consistency simpler, but remote users incur higher latency (if an EU
user’s writes must go to US, that’s ~100ms+).

77
• Networking: Usually use dedicated links or VPN between data centers for replication for security
and speed.
• DNS-based failover: often used for multi-region: e.g. users resolve [Link] to nearest region
(via Geo DNS). For active-passive failover, DNS switch can redirect to backup region’s IP on failure.
• Examples:
◦ Netflix: active-active across AWS regions for stateless services, but for data (like Cassandra)
they keep clusters per region with some cross-replication for certain key spaces, and they can
shift traffic using DNS.
◦ Banking: often active-passive (primary data center and a hot standby), because strong
consistency is needed and they’d rather failover manually to known consistent copy than risk
divergence.

• Testing: Must regularly test DR failover (simulate region outage) to ensure processes work and to
measure RTO.

• Event Sourcing + CQRS:

• Event Sourcing: Store state changes as a sequence of events (append-only log), rather than storing
the current state directly. The current state is derived by replaying the events. For instance, instead
of a “balance” field, store events: Deposited $100, Withdrew $30,... so you can always recompute
balance and have the audit trail of all transactions. Benefits: perfect audit/history, ability to
reconstruct past states (replay events up to time T), easier to implement complex undo or temporal
queries. It naturally produces a log that can feed other systems (since every state change is an
event). Drawbacks: reading current state requires replay (which can be mitigated with snapshots or
caching), and writing events requires careful design (events become immutable part of history, so
design your event schema for forward compatibility).
• CQRS (Command Query Responsibility Segregation): Split the system’s model into write side
(commands) and read side (queries), each optimized separately. The write side handles updates
(and in event sourcing, emits events). The read side has one or more projection models (could be
different databases or structures) built from those events or updates, optimized for reads (e.g.
denormalized views, precomputed aggregates). This means read queries don’t hit the write database
directly (which might be normalized or complex); instead they query a tailored data store. This
improves read performance and scalability, and also allows multiple different read projections for
different use cases from the same event stream. However, the read model is eventually consistent
with writes (there’s a propagation delay from events to updating the read model).
• Combining ES + CQRS: Very common – the system stores events (event sourcing) as the source of
truth. On each new event, it updates one or more read projections (could be via an async event
handler). For example, events “OrderCreated, ItemAdded, ItemAdded, OrderPlaced” might update a
relational view of orders or a caching system for quick retrieval. The command side might just store
those events in an event store (like an append-only DB or Kafka), and the query side could be a SQL
or NoSQL DB updated by listening to the event stream.
• Benefits: Scalability (reads can be scaled independently by duplicating read DBs or making multiple
different optimized structures), flexibility (you can add new read models if new requirements come –
consume the historical event log to build it). Also easier to evolve domain logic – events are facts that
never change, you can rebuild projections if logic changes.
• Example: In a retail system:
◦ Command (write) side: when an order is placed, create Order events (maybe an
“OrderCreated” event, then “InventoryReserved”, “OrderShipped”, etc.). These are stored.

78
 ◦ Read side: one projection might be an Order Summary table that has current status and
total, used for quick display on user’s order history page. Another projection might be a
Stock Level table for each product. These are updated by consuming the events (e.g.
InventoryReserved event decrements stock in Stock Level read model).
◦ Thus, the system never directly updates a “stock” field in place – it appends events and the
read model reflects it. If there’s a bug in stock calculation, you can replay all events to
recompute stock.
• Challenges: Complexity in design and mental model. The system is eventually consistent – e.g. right
after placing an order, the user’s query might not immediately show it until the event is processed
into the read DB (you often mitigate by designing UI to handle slight delays or by having the
command return the new data which UI can optimistically display).
• Idempotency & ordering: Event handlers must handle events exactly once (or be idempotent) – if
an event is applied twice to a read model, could double count. Usually use event IDs or sequence
numbers to ensure each processed once. Ordering of events by aggregate (entity) is important
(should apply in order).
• Storage: Event store can grow large; usually, you can snapshot state periodically to avoid replaying
from the beginning every time (e.g. save state every 100 events, then to rebuild aggregate, start
from last snapshot). But the event log is the record; snapshots are an optimization.
• CQRS without event sourcing: possible too (you might just have one write DB and then replicate its
changes to read replicas or views). Event sourcing pretty much implies CQRS (since you don’t use
events directly for querying, you have to derive state = that’s CQRS).

• Use cases: Complex domains where history is critical (finance, auditing), collaborative systems
(where you want to show event feeds), systems that have very different read and write access
patterns (lots of reads that can be optimized by denormalizing). Many modern microservices adopt
at least a form of CQRS by separating the concerns (e.g. one service handles commands, another
builds read model).

• Database Indexing:

• B-tree Index: Balanced tree structure (usually B+Tree) widely used in relational databases for
indexing columns 3 . Supports efficient lookup (O(log N)) by key and range scans in sorted order.
Good for equality and range queries (e.g. WHERE id = 5 or WHERE name BETWEEN 'A' and
'K' ). Most primary and secondary indexes in SQL DBs are B-trees. Example: an index on email in
users allows quick find by email (instead of full table scan). The tree nodes keep pointers such that
range queries can be satisfied by scanning leaf sequence. Note: B-tree performance degrades if the
data is huge and doesn’t fit in memory, but that’s mitigated by caches and the logarithmic growth
(even millions of rows might be 3-4 levels deep only). Maintained on insert/delete (can split or merge
nodes).
• Inverted Index: Index for full-text search (and also used for things like tags/arrays) 18 . Maps each
term -> list of documents (or rows) containing that term. For text, the document is often identified by
an ID and maybe positions if phrase queries needed. Allows queries like "find documents containing
'apple' and 'banana'" by retrieving the respective lists and intersecting. Also supports ranking (with
term frequency info). In relational context, an inverted index might be used for a TEXT column to
enable MATCH ... AGAINST queries (MySQL) or using a search engine alongside the DB. Example:
Searching a blog posts table for "database indexing" – an inverted index on content would have
entries "database" -> {post1, post3}, "indexing" -> {post2, post3,...}, intersection gives post3. These

79
 indexes are typically stored in specialized search systems (Lucene/Elasticsearch). They are not good
for numeric range queries (use B-tree or numeric index for that).
• Bitmap Index: Uses bit arrays to indicate which rows have a given value 65 66 . Suitable for
columns with low cardinality (few distinct values) in analytic databases. Example: a status field
with values {New, Processing, Done} – a bitmap index would have 3 bitmaps, each length = number
of rows; bit is 1 if row has that status. Then a query WHERE status = 'Done' AND region =
'US' can do a bitwise AND of the "Done" bitmap with the "US" bitmap (if region is also low-
cardinality) to get matching rows extremely fast. Bitmap indexes compress well (especially if data is
sorted by that column, runs of identical values compress). They shine in data warehousing
scenarios with lots of boolean or categorical filters combined – because bit operations are very fast
in CPU. Not ideal for high-cardinality (bitmaps would be mostly sparse, although compressed
bitmaps like Roaring can handle moderately high cardinality). Not great for columns that update
frequently either (changing bits in potentially large bitmaps). Oracle and some analytic DBs (like
Sybase IQ, now SAP IQ) heavily use bitmaps for multi-dimensional queries (OLAP).
• Hash Index: (Not in original list, but notable) – index keys via a hash table for equality lookup. O(1)
exact match. But not good for range since hash scatters order. Some DBs like Postgres have optional
hash indexes; MySQL Memory engine uses hash by default. Typically, B-tree is preferred because it
handles range and equality reasonably well. Hash indexes might be slightly faster for pure equality
on very large data or in memory.
• Index selection: Use B-tree for most things (primary keys, foreign keys, any column you filter or sort
on regularly). Use full-text (inverted) index for search-type queries on large text fields. Use bitmap
indexes in warehouses on low-cardinality columns often involved in filters (like gender, category,
boolean flags) – especially when queries often AND/OR those columns (because combining bitmaps
is efficient). Ensure to update statistics and choose indexes carefully to avoid slowing writes (each
index adds write overhead).
• Covering index: a composite index that “covers” a query (contains all needed columns as index keys
or included fields) so the DB can answer purely from the index without touching the main table.
• Index maintenance: On heavy write systems, too many indexes hurt performance (as each insert/
update must update indexes). Sometimes different indexing strategy is needed for OLTP vs OLAP
(some systems drop or disable indexes during bulk load to speed it up, then rebuild).
• Constraints: Primary key/unique constraints are enforced via indexes (to find quickly if a value
exists).
• NoSQL indexes: Many NoSQL have secondary index options, but often limited (e.g. MongoDB has B-
tree indexes on document fields, Elasticsearch is basically an inverted index store).
• Example benefit: A table of 1 million rows without an index – a query WHERE name='John' scans
all million (maybe tens of MB of I/O). With an index on name, perhaps only ~log2(1e6) ~ 20
comparisons plus a few IOs (or more likely it’s tree height ~3 and then a range of a few entries).
That’s orders of magnitude faster. Hence, proper indexing is one of the biggest performance boosts
in databases.

1 2 11 12 13 14 15 16 17 31 52 NoSQL Databases Visually Explained with Examples

[Link]

3 4 5 6 48 49 65 66 Difference Between Indexing Techniques in DBMS - GeeksforGeeks

[Link]

80
 7 8 9 10 30 58 63 What are the algorithms for data sharding? - Tencent Cloud
[Link]

18 Inverted index - Wikipedia

[Link]

19 20 21 22 23 53 54 55 56 What Is the CAP Theorem? | IBM

[Link]

24 25 57 What is a BASE Consistency Model?

[Link]

26 27 28 60 Synchronous replication vs asynchronous replication - Evidian

[Link]
asynchronous-replication/

29 How to Choose a Replication Strategy

[Link]

32 Mastering Idempotency: Building Reliable APIs

[Link]

33 59 REL04-BP04 Make mutating operations idempotent

[Link]

34 35 36 43 45 A Crash Course in Caching - Final Part - by Alex Xu

[Link]

37 Choosing the Right DynamoDB Partition Key | AWS Database Blog

[Link]

38 39 caching - Twitter fanout design - Stack Overflow

[Link]

40 41 42 Understanding Request Coalescing – [Link] Support Hub

[Link]

44 61 62 Messaging Patterns Explained: Pub-Sub, Queues, and Event Streams

[Link]

46 Enhancing Network Resilience with Istio on Amazon EKS - AWS

[Link]

47 What is Istio?
[Link]

50 Snowflake ID - Wikipedia
[Link]

51 Should We Rethink About IDs? A Deep Dive into "Snowflake IDs"

[Link]

64 Istio circuit breaker sending traffic to unhealthy Services

[Link]

81