DEV Community: Syed Anzar

Why Increasing Database Connections Makes Queries Slower: Process Overhead, Little’s Law, and Pool Sizing Math

Syed Anzar — Fri, 09 Oct 2026 12:34:25 +0000

When an application experiences traffic spikes and database latency rises, the instinctive reaction for many engineering teams is simple:

"Our queries are queuing up. Let's increase max_connections on PostgreSQL from 100 to 1,000 and bump our ORM connection pool size."

Within minutes of deploying that change, query latency explodes from 5ms to 4,000ms. Database CPU utilization hits 100%, memory usage spikes, and application pods start crashing with connection timeout errors.

Adding database connections under heavy load does not increase concurrency. In most production systems, it triggers a catastrophic collapse in throughput.

Here is what actually happens inside the Linux kernel, PostgreSQL's process table, and hardware CPU caches when you over-allocate database connections, alongside the exact math to size your pools correctly.

1. The Hardware Reality: CPU Cores Can Only Execute One Thing at a Time

A common misconception among developers is that an active connection represents concurrent query execution.

An 8-core CPU can only execute 8 instructions at any given nanosecond. If your database server has 8 physical cores and receives 500 active queries across 500 open connections, exactly 8 queries are being evaluated by the CPU. The remaining 492 queries are sitting in OS run queues waiting for CPU time slices.

       500 Client Connections
                 │
                 ▼
┌───────────────────────────────────┐
│     OS Thread / Process Queue     │
│   (492 Backends Waiting / Blocked) │
└─────────────────┬─────────────────┘
                  │ Context Switch Storm
                  ▼
         [ 8 Physical Cores ]
   (Evaluating 8 Queries at a Time)

When the operating system scheduler attempts to juggle hundreds of runnable processes across a handful of physical cores, it enters a state known as context-switching thrashing:

State Preservation Overhead: For every context switch, the kernel must save CPU register states, stack pointers, and program counters to memory, then restore the state of the incoming process.
Translation Lookaside Buffer (TLB) Invalidation: Because PostgreSQL uses separate processes rather than lightweight threads, switching between backend processes forces the CPU to switch page directory tables, invalidating the TLB cache.
L1/L2/L3 Cache Eviction: Query execution engines rely heavily on CPU caches for parse trees, index root pages, and sort buffers. Constant process switching flushes the cache lines, forcing the CPU to fetch data repeatedly from slower system RAM.

At 500+ active connections on an 8-core machine, the CPU spends more clock cycles managing process scheduling and cache misses than executing SQL logic.

2. The PostgreSQL Process-per-Connection Architecture

Unlike MySQL (which assigns a lightweight thread to each connection) or Redis (which uses an asynchronous event loop), PostgreSQL uses a process-per-connection model.

When a client establishes a connection, the PostgreSQL supervisor daemon (postmaster) invokes the fork() system call to spawn an independent OS process:

postgres: user database 10.0.1.25(54322) SELECT

This architectural choice offers immense memory isolation and fault tolerance (a crashing worker cannot corrupt other backends), but it imposes severe per-connection costs.

               ┌────────────────────────┐
               │   Postmaster Daemon    │
               └───────────┬────────────┘
                           │ fork()
            ┌──────────────┼──────────────┐
            ▼              ▼              ▼
     ┌─────────────┐┌─────────────┐┌─────────────┐
     │ Backend #1  ││ Backend #2  ││ Backend #N  │
     │ Private RSS ││ Private RSS ││ Private RSS │
     │  5-10 MB    ││  5-10 MB    ││  5-10 MB    │
     └──────┬──────┘└──────┬──────┘└──────┬──────┘
            │              │              │
            └──────────────┼──────────────┘
                           ▼
     ┌───────────────────────────────────────────┐
     │          Shared Memory Segment            │
     │  (shared_buffers, ProcArray, WAL Buffers) │
     └───────────────────────────────────────────┘

A. Private Memory (RSS) Footprint

Every PostgreSQL backend process maintains its own private address space:

Base Process Memory: Between 5 MB and 10 MB of RSS for process stacks, catalog caches, and local memory contexts.
work_mem Dynamic Allocation: The work_mem setting (default 4 MB) is allocated per sort or hash operation node in a query plan, not per connection. A complex query performing two joins, an aggregation, and an ORDER BY can allocate 4 separate work_mem chunks:

$$\text{Query Memory} = 4 \times 4\,\text{MB} = 16\,\text{MB}$$

If 300 active connections execute similar reporting or join queries concurrently:

$$\text{Total Memory Demand} = 300 \times 16\,\text{MB} = 4.8\,\text{GB}$$

This memory is allocated outside shared_buffers. When combined with base RSS, unconstrained connection counts quickly trigger the Linux Out-Of-Memory (OOM) Killer, terminating the PostgreSQL master process.

B. Shared Memory Contention: The `ProcArrayLock` Bottleneck

To provide Multi-Version Concurrency Control (MVCC) snapshot isolation, PostgreSQL backends must track the status of all active transactions.

This tracking happens in a central shared-memory structure called ProcArray (an array of PGPROC structures). Whenever any transaction begins, commits, or aborts, it must acquire an exclusive or shared lock on ProcArrayLock.

With 20 connections, acquiring ProcArrayLock is instantaneous. With 1,000 connections, hundreds of CPU cores and threads spend thousands of clock cycles spinning on futexes and spinlocks just trying to register transaction snapshots.

3. The Queueing Math: Little's Law

Queueing theory proves why adding connections slows down your database. Little's Law defines the mathematical relationship between concurrency, throughput, and latency in any stable system:

$$L = \lambda \times W$$

Where:

$L$ = Average number of concurrent requests in the system.
$\lambda$ = System throughput (arrival rate in queries per second).
$W$ = Average time spent processing each query (latency in seconds).

Let us apply real numbers. Suppose your API requires your database to process 2,000 queries per second (QPS), and your database indexes are well-tuned such that the average query takes 5 milliseconds (0.005s):

$$L = 2000 \times 0.005 = 10$$

You only need 10 concurrent connections to sustain a throughput of 2,000 QPS.

Incoming: 2,000 QPS ──▶ [ 10 Active DB Connections ] ──▶ Completed in 5ms

What Happens When You Add 200 Connections?

If your database hardware can only execute 10 queries concurrently without CPU contention, opening 200 connections does not increase $\lambda$ (throughput). The physical disk and CPU remain bounded.

Instead, the extra connections increase $W$ (latency) because queries spend time waiting in OS run queues and lock barriers:

$$W = \frac{L}{\lambda} = \frac{200}{2000} = 0.100\,\text{seconds} = 100\,\text{ms}$$

By opening 200 connections to solve a perceived capacity problem, query latency increases by 20x (from 5ms to 100ms) with zero gain in throughput.

4. The Canonical Connection Pool Formula

The PostgreSQL development team and the authors of HikariCP established an empirical formula for optimal database connection pool sizing:

$$\text{Pool Size} = (\text{Core Count} \times 2) + \text{Effective Spindle Count}$$

Let us break down each term:

$\text{Core Count} \times 2$: When one query briefly stalls waiting for a page fault or synchronous disk I/O, the operating system can seamlessly switch the CPU core to execute a second active query without idle CPU bubbles.
$\text{Effective Spindle Count}$: In traditional spinning disks (HDDs), each physical spindle could seek independently. On modern NVMe SSDs where active working sets are cached in RAM or shared_buffers, effective spindle count is 1 (or approaching 0 for 100% in-memory datasets).

Practical Calculation

For a standard cloud instance with an 8-core CPU running on NVMe storage:

$$\text{Optimal Pool Size} = (8 \times 2) + 1 = 17\,\text{connections}$$

Hardware Specs       Formula Calculation        Optimal Connections
───────────────────────────────────────────────────────────────────
4 CPU Cores, SSD     (4 * 2) + 1                9 Connections
8 CPU Cores, SSD     (8 * 2) + 1                17 Connections
16 CPU Cores, SSD    (16 * 2) + 1               33 Connections
32 CPU Cores, SSD    (32 * 2) + 1               65 Connections

Running benchmarks (such as pgbench) on an 8-core server shows that throughput peaks between 16 and 25 connections. Pushing connections beyond 100 causes throughput to drop steeply while response latency rises exponentially.

5. The Kubernetes Multi-Pod Multiplication Mistake

In containerized microservices architectures, default connection settings cause accidental database overload.

Consider a standard setup:

10 Kubernetes application pods running Spring Boot, Node.js, or Go.
Default ORM / pool config: maximumPoolSize = 20.

10 Pods x 20 Connections/Pod = 200 Total Connections to PostgreSQL

When traffic spikes and Kubernetes Horizontal Pod Autoscaler (HPA) scales the deployment from 10 pods to 30 pods, the connection count surges to 600 connections. The database crashes precisely when user demand is highest.

       [ Pod 1 (20) ]
       [ Pod 2 (20) ] ──▶ Total: 200 to 600 Connections ──▶ [ 8-Core Postgres ]
       [ Pod N (20) ]                                        (Overloaded & Crashing)

The Correct Formula for Distributed Pods

To prevent pool bloat across multiple application instances, allocate connection quotas proportionally:

$$\text{Pool Per Pod} = \max\left(2, \; \left\lfloor \frac{\text{Target DB Connections}}{\text{Number of Pods}} \right\rfloor\right)$$

If your 16-core database supports a target pool of 34 connections across 10 application pods:

$$\text{Pool Per Pod} = \left\lfloor \frac{34}{10} \right\rfloor = 3\,\text{connections per pod}$$

Each pod needs only 3 to 4 connections if queries are fast and transactions are short.

6. Client Pools vs Middleware Proxies (PgBouncer)

When you have hundreds of microservices, serverless functions (like AWS Lambda), or edge workers, dividing 20 connections across 500 callers is impossible.

This is where connection pooling layers differ:

┌───────────────────────────────────────────────────────────────┐
│                    Connection Management                      │
├───────────────────────────────┬───────────────────────────────┤
│ Client-Side Pooling           │ Middleware Proxy Pooling      │
│ (HikariCP, pgxpool, Prisma)   │ (PgBouncer, Odyssey, Pgpool)  │
├───────────────────────────────┼───────────────────────────────┤
│ Operates inside app process   │ Standalone proxy server       │
│ Cannot coordinate across pods │ Centralized queueing for all  │
│ High idle connection overhead │ Ultra-lightweight (2KB / conn)│
│ Best for fixed monorepos      │ Mandatory for serverless/K8s  │
└───────────────────────────────┴───────────────────────────────┘

Why PgBouncer in Transaction Mode Solves the Problem

PgBouncer acts as a lightweight proxy between your application fleet and PostgreSQL. Built on a single-threaded asynchronous epoll event loop, PgBouncer can maintain 10,000 idle client connections with negligible memory usage (~2 KB per connection).

In Transaction Pooling Mode (pool_mode = transaction):

A client connects to PgBouncer. PgBouncer accepts the TCP connection immediately.
No PostgreSQL backend process is assigned while the client is idle (e.g., executing application business logic or external API calls).
The moment the client issues BEGIN or a standalone SQL query, PgBouncer binds an active PostgreSQL server connection from its small pool of 20 backends.
As soon as the client issues COMMIT or ROLLBACK, PgBouncer reclaims the PostgreSQL backend and hands it to another waiting client.

[ 10,000 Client Apps / Lambdas ]
              │ (Lightweight TCP, 2 KB RAM each)
              ▼
    [ PgBouncer (pool_mode=transaction) ]
              │ (Strictly 20 Server Connections)
              ▼
    [ PostgreSQL (8-Core Server) ]

Transaction Pooling Incompatibilities to Watch Out For

Because transaction pooling reassigns the underlying PostgreSQL connection after every transaction, session-scoped features will not persist across transactions:

Session Variables: SET TIME ZONE or SET search_path will affect whichever backend process ran the command, leaking state to subsequent clients. Use SET LOCAL within transaction blocks instead.
LISTEN / NOTIFY: Requires a dedicated long-lived connection (pool_mode = session).
Prepared Statements: Historically broken in transaction pooling. Since PgBouncer 1.21+, you can enable protocol-level prepared statement tracking by configuring:

;; pgbouncer.ini
max_prepared_statements = 200

7. Diagnosing Connection Health in Production

To inspect how connections are behaving on your PostgreSQL instance, run this diagnostic query:

SELECT 
    state,
    count(*) AS connection_count,
    round(avg(extract(epoch from (now() - state_change))), 2) AS avg_seconds_in_state,
    round(max(extract(epoch from (now() - state_change))), 2) AS max_seconds_in_state
FROM pg_stat_activity
WHERE pid <> pg_backend_pid()
GROUP BY state
ORDER BY connection_count DESC;

How to Interpret the Output:

idle in transaction (Danger): Application code opened a transaction (BEGIN), executed a query, and stalled waiting for HTTP calls or internal processing before issuing COMMIT. This holds locks and blocks VACUUM cleanup.
idle (Waste): Connections are established and sitting unused. If idle connections exceed 80% of max_connections, lower your application pool sizes or introduce PgBouncer.
active (Executing): If active connections consistently exceed (CPU Cores * 2), queries are waiting on locks, slow disk scans, or missing indexes.

8. Summary: Senior Engineer Sizing Rules

When designing connection architectures:

Keep database pools small: A pool size of (Cores * 2) + 1 maximizes CPU cache efficiency and minimizes scheduling thrashing.
Queue in the application, not the database: Let application threads or connection poolers hold waiting requests in memory rather than forcing PostgreSQL to fork heavy processes.
Guard against pod scaling: Ensure (Pods * Pool Size) never exceeds your database core limit.
Use PgBouncer for high concurrency: If your architecture requires hundreds of client connections (microservices, serverless), place PgBouncer in front of PostgreSQL in transaction pooling mode.
Keep transactions short: Never perform network I/O, file operations, or heavy computational tasks inside an open database transaction block.

Why UPDATE Is Secretly an INSERT: How Postgres MVCC, xmin/xmax, and Table Bloat Actually Work

Syed Anzar — Fri, 09 Oct 2026 04:59:50 +0000

When you run an UPDATE statement in PostgreSQL, your intuition tells you something simple happens: the database finds the row on disk, seeks to the modified column, and overwrites the old bytes with the new values.

UPDATE users SET status = 'active' WHERE id = 42;

If Postgres actually worked this way, concurrent reads would crash, transactions would read half-written dirty bytes, and rollbacks would require expensive undo operations.

Postgres never modifies a row in place during an UPDATE.

Instead, Postgres performs an INSERT followed by a soft DELETE. It writes a completely new physical copy of the row, leaves the old row untouched on disk, marks the old row as expired, and links them together.

Understanding this mechanism (Multi-Version Concurrency Control, or MVCC) is the key to understanding why write-heavy Postgres databases experience massive table bloat, why secondary indexes suddenly degrade, and how Postgres engineers designed Heap-Only Tuples (HOT) to survive it.

Let us look beneath the SQL layer into the physical 8KB page layout, tuple headers, and transaction visibility rules.

1. Physical Storage: Inside the 8KB Heap Page

To see what happens during an update, you first need to see how Postgres stores data on disk.

Postgres tables are divided into physical 8KB blocks called pages (or buffers in shared memory). Each page is organized from the outside in:

+-----------------------------------------------------------------------+
| PageHeaderData (24 bytes)                                             |
| pd_lsn | pd_flags | pd_lower | pd_upper | pd_special ...              |
+-----------------------------------------------------------------------+
| ItemId (Line Pointers array: 4 bytes each, grows DOWNWARDS)           |
| [Line Pointer 1] -> offset to Tuple 1                                 |
| [Line Pointer 2] -> offset to Tuple 2                                 |
|                    | (Free Space Gap) |                               |
|                    v                  v                               |
+-----------------------------------------------------------------------+
| Heap Tuples (Actual Row Data: grows UPWARDS from the bottom)          |
|                                                                       |
| [Tuple 2 Payload + Header (23 bytes)]                                 |
| [Tuple 1 Payload + Header (23 bytes)]                                 |
+-----------------------------------------------------------------------+

Every physical tuple on a page has a 23-byte header (HeapTupleHeaderData) containing hidden metadata columns:

t_xmin: The Transaction ID (XID) of the transaction that created/inserted this row version.
t_xmax: The Transaction ID of the transaction that deleted or updated this row version (0 if the row is still live and un-deleted).
t_ctid: The physical location (page_number, line_pointer_index) of this tuple or the newer version tuple if updated.
t_infomask / t_infomask2: Bit flags indicating transaction commit status and Heap-Only Tuple properties.

2. The Step-by-Step Trace of an UPDATE

Let us trace what happens under the hood when Transaction 105 updates row 1 on page 0.

Initial State: A Fresh Insert (Transaction 100)

When row 1 is originally inserted by Transaction 100 at page 0, line pointer 1:

Physical Address: ctid = (0, 1)
xmin: 100
xmax: 0
data: { id: 42, name: 'Alice', status: 'pending' }

Any transaction running concurrently checks xmin (100 is committed) and xmax (0 means not deleted), so it reads the row.

The UPDATE Executes (Transaction 105)

When Transaction 105 executes UPDATE users SET status = 'active' WHERE id = 42:

Step 1: Write New Tuple (Physical Address: ctid (0, 2))
------------------------------------------------------
xmin: 105
xmax: 0
data: { id: 42, name: 'Alice', status: 'active' }

Step 2: Expire Old Tuple (Physical Address: ctid (0, 1))
------------------------------------------------------
xmin: 100
xmax: 105               <-- Marked deleted by Tx 105!
t_ctid: (0, 2)          <-- Points forward to the replacement version!
data: { id: 42, name: 'Alice', status: 'pending' }

+-----------------------------------------------------------------------+
| PAGE 0                                                                |
|                                                                       |
| Line Pointer 1 ---------> [Tuple 1: xmin=100, xmax=105, ctid=(0,2)]   |
|                                   | (Forward Pointer)                 |
|                                   v                                   |
| Line Pointer 2 ---------> [Tuple 2: xmin=105, xmax=0,   ctid=(0,2)]   |
+-----------------------------------------------------------------------+

Notice what just happened:

Tuple 1 was not overwritten. Its xmax was updated to 105, and its t_ctid was updated to point to (0, 2).
Tuple 2 was written as a fresh row at line pointer 2 with xmin = 105.
Both tuples now exist simultaneously on the physical disk page.

3. How MVCC Solves Concurrency Without Read Locks

Why go through this trouble instead of modifying bytes in place?

Because readers never block writers, and writers never block readers.

Consider two concurrent transactions:

Transaction 102 (Started earlier, long-running report):
When Tx 102 queries users WHERE id = 42, its snapshot rule says: "Ignore changes from any transaction ID >= 102."
It inspects Tuple 1:
- xmin is 100 (committed before 102: visible).
- xmax is 105 (committed after 102 started: invisible deletion). Tx 102 reads Tuple 1 (status: 'pending') cleanly without taking a single shared read lock on the row.
Transaction 108 (Started after 105 commits):
Its snapshot rule says: "Transaction 105 is committed."
It inspects Tuple 1:
- xmax is 105 (committed: Tuple 1 is dead). It follows the forward pointer t_ctid = (0, 2) to Tuple 2:
- xmin is 105 (committed: visible).
- xmax is 0 (live). Tx 108 reads Tuple 2 (status: 'active').

No locks, no mutexes, no dirty reads, and no rollbacks. If Transaction 105 aborts, Postgres simply marks Tx 105 as aborted in the pg_xact commit log status map. Tuple 2 becomes instantly invisible to everyone, and Tuple 1 becomes visible again. Zero rollback log application needed.

4. The Hidden Tax: The Secondary Index Disaster

The MVCC design is brilliant for concurrency, but it introduces a severe architectural problem with database indexes.

In PostgreSQL, secondary indexes (B-Trees, GIN, GiST) do not point to a primary key or clustered table structure (unlike MySQL InnoDB). In Postgres, all indexes store direct physical pointers (ctid) to heap tuples.

If your users table has 5 indexes (e.g. on email, created_at, org_id, last_login, and status):

Before UPDATE:
Index on email       -------> ctid (0, 1)
Index on created_at  -------> ctid (0, 1)
Index on org_id      -------> ctid (0, 1)
Index on last_login  -------> ctid (0, 1)
Index on status      -------> ctid (0, 1)

When you update just one column (status):

The new row is written to ctid (0, 2).
If naive indexing applied, Postgres would have to insert a new index entry pointing to (0, 2) into all 5 indexes, even though email, created_at, org_id, and last_login never changed.

In a write-heavy database with 10 million rows and multiple indexes, updating a single column would trigger massive B-Tree write amplification, leaf page splits, and catastrophic disk I/O.

5. The Solution: Heap-Only Tuples (HOT)

To fix this index amplification, Postgres 8.3 introduced HOT (Heap-Only Tuples).

HOT allows Postgres to update a row without touching secondary indexes at all, provided two conditions are met:

No indexed column is modified: The UPDATE statement only changes columns that are not part of any index definition.
Space exists on the same page: The new tuple version fits inside the exact same 8KB physical page as the old tuple.

Index on email ------> Line Pointer 1 (LP_REDIRECT)
                             |
                             v
                       Line Pointer 2 ------> [Tuple 2 (status: 'active')]
                                              [Tuple 1 (Dead: status: 'pending')]

When HOT activates:

Postgres writes Tuple 2 to the same page.
Postgres turns Line Pointer 1 into an LP_REDIRECT stub pointing directly to Line Pointer 2 inside the page header.
Every secondary index continues pointing to Line Pointer 1 without any index modifications.
When an index scan traverses the B-Tree to Line Pointer 1, the engine follows the internal line pointer redirection directly to Tuple 2.

-- Check if your table is benefiting from HOT updates
SELECT 
    relname, 
    n_tup_upd AS total_updates, 
    n_tup_hot_upd AS hot_updates,
    ROUND((n_tup_hot_upd::numeric / NULLIF(n_tup_upd, 0)) * 100, 2) AS hot_ratio_pct
FROM pg_stat_user_tables
WHERE relname = 'users';

If your hot_ratio_pct is low (below 80% on update-heavy tables), you are paying a massive write penalty.

6. Inspecting the Physical Page with `pageinspect`

You can verify this physical behavior directly using the built-in Postgres pageinspect extension.

CREATE EXTENSION IF NOT EXISTS pageinspect;

-- Inspect line pointers and tuple headers on block 0 of users table
SELECT 
    lp, 
    lp_flags, 
    t_xmin, 
    t_xmax, 
    t_ctid, 
    t_infomask, 
    t_data 
FROM heap_page_items(get_raw_page('users', 0));

When you run this after an UPDATE, you will literally see two separate items on the page:

Item lp=1 with t_xmax = <txid> and t_ctid = (0, 2).
Item lp=2 with t_xmin = <txid> and t_xmax = 0.

7. Table Bloat and the Autovacuum Lifecycle

Because updates leave dead tuples behind, a table that processes 100,000 updates a day accumulates 100,000 dead rows.

The Role of VACUUM

When VACUUM runs:

It scans pages and identifies tuples whose xmax is older than the oldest active transaction snapshot.
It removes the dead tuple payload and marks the space on the 8KB page as available for future INSERT or UPDATE operations.
It updates the Free Space Map (_fsm fork) so new writes know where to find free slots.

The Bloat Trap: VACUUM Does Not Shrink File Size

Standard VACUUM frees space inside existing pages, but it never returns pages to the operating system filesystem.

If a table bloats from 1 GB to 20 GB during a bulk update batch, the disk file stays 20 GB forever unless:

Future inserts fill the empty slots inside the existing pages.
You run VACUUM FULL users or pg_repack, which creates a brand new copy of the table and swaps the physical relfilenode on disk.

+---------------------------------------------------------------+
| Disk File (20 GB on OS)                                       |
| [Page 0: 80% free] [Page 1: 90% free] ... [Page 2,500,000]    |
+---------------------------------------------------------------+

8. Senior Database Gotchas to Prevent MVCC Outages

1. The Long-Running Transaction Anchor

If a developer opens a BEGIN; session in psql or an analytics query runs for 4 hours, Postgres cannot vacuum any dead tuples created after that transaction started.
Autovacuum will skip dead tuples, leading to exponential table bloat and high disk consumption.

-- Find transactions holding back VACUUM cleanup
SELECT 
    pid, 
    usename, 
    state, 
    age(backend_xmin) as xmin_age, 
    query, 
    now() - xact_start as duration 
FROM pg_stat_activity 
WHERE backend_xmin IS NOT NULL 
ORDER BY age(backend_xmin) DESC;

2. Tuning Table `fillfactor` for HOT Updates

By default, Postgres packs 100% data into every 8KB page (fillfactor = 100). This leaves zero empty room for HOT updates on the same page, forcing every update to allocate a new page and update all secondary indexes.

For write-heavy tables with frequent updates, set fillfactor to 80-90%:

ALTER TABLE users SET (fillfactor = 80);
VACUUM FULL users; -- Rewrites the table with 20% free space per page

Now, 20% of every page is reserved specifically for in-page HOT updates, eliminating secondary index churn.

3. Autovacuum Cost Delay Throttling

Default PostgreSQL autovacuum settings are deliberately conservative (autovacuum_vacuum_cost_limit = 200). Under write load, dead tuples accumulate 10x faster than autovacuum can process them.
Tune autovacuum_vacuum_cost_limit to 1000 or 2000 on modern NVMe SSDs to allow vacuum workers to keep up with write streams.

Summary Mental Model

Operation	What Developers Assume	What Postgres Actually Does
`UPDATE`	Modifies bytes in place on disk	Writes a new row (`xmin`), marks old row dead (`xmax`), updates `t_ctid` pointer chain
`DELETE`	Erases bytes from disk	Sets `xmax = current_txid` in the tuple header (soft delete)
Concurrency	Read locks prevent dirty reads	Snapshot visibility check on `xmin`/`xmax` headers without read locks
Index Impact	No index changes if keys are untouched	All indexes get new entries unless HOT (Heap-Only Tuples) optimization triggers
`VACUUM`	Shrinks database file on disk	Reclaims internal page space for future writes; does not shrink OS file size

Understanding that an UPDATE is an INSERT changes how you design schema indexes, tune fillfactor, configure autovacuum, and manage transaction lifetimes in production.

How Linux Zero-Copy Actually Works: sendfile, DMA Scatter-Gather, and Page Cache Internals

Syed Anzar — Thu, 08 Oct 2026 12:33:31 +0000

When building high-throughput web servers, reverse proxies, or message brokers like Kafka and NGINX, you inevitably run into the term Zero-Copy.

Most developers understand the high-level pitch: Zero-copy transfers data from disk to network without wasting CPU cycles copying bytes into user space.

While that summary is accurate, it skips the actual engineering underneath:

Where do the copies actually happen in a traditional read() and write() loop?
How does the kernel send data it never copied into memory?
Why did HTTPS break zero-copy for nearly a decade, and how did the Linux kernel fix it?

Let's trace what happens inside the Linux kernel, CPU registers, page cache, and network interface card (NIC) when you move bytes with and without zero-copy.

1. The Hidden Tax of Traditional I/O (`read` + `write`)

Consider the standard way a beginner writes a static file server in C, Python, or Go:

char buffer[8192];
while ((bytes_read = read(file_fd, buffer, sizeof(buffer))) > 0) {
    write(socket_fd, buffer, bytes_read);
}

To transfer one chunk of data, the OS goes through 4 context switches and 4 data copies:

+-----------------------------------------------------------------------+
| USER SPACE                                                            |
|                           [ User Buffer ]                             |
|                             ^         |                               |
|                     CPU Copy|         |CPU Copy                       |
|                             |         v                               |
+-----------------------------|---------|-------------------------------+
| KERNEL SPACE                |         |                               |
|                     +-------+         +-------+                       |
|                     |                         |                       |
|                     v                         v                       |
|              [ Page Cache ]             [ Socket Buffer ]             |
|                     ^                         |                       |
|              DMA Copy|                         |DMA Copy               |
|                     |                         v                       |
|                  [ Disk ]                   [ NIC ]                   |
+-----------------------------------------------------------------------+

The Step-by-Step Breakdown

read() Syscall (User -> Kernel Switch 1): The CPU traps into kernel mode. The kernel issues a DMA (Direct Memory Access) request to read the file from storage into kernel page cache memory (Copy 1: Disk -> Page Cache).
Kernel -> User Copy (Switch 2): The CPU copies the raw bytes from the kernel page cache into the process's stack or heap buffer (Copy 2: Page Cache -> User Buffer). The syscall returns to userspace.
write() Syscall (User -> Kernel Switch 3): The process calls write(), trapping back into kernel mode. The CPU copies data from the user buffer into the kernel's socket send buffer (Copy 3: User Buffer -> Socket Buffer).
Socket -> NIC DMA (Switch 4): The kernel returns from write(). Asynchronously, the NIC engine reads the socket buffer via DMA and sends the packets across the physical wire (Copy 4: Socket Buffer -> NIC).

Why Is This Expensive?

The DMA copies (Disk to RAM, RAM to NIC) are handled by hardware controllers without consuming CPU cycles.

The real bottleneck is the 2 intermediate CPU copies across the kernel-userspace boundary. When serving gigabytes of data per second:

The CPU spends billions of clock cycles copying memory blocks (memcpy).
It saturates the system memory bus.
It evicts valuable hot data from the CPU L1, L2, and L3 caches to make room for transient network payloads.

2. Evolution Level 1: `mmap()` + `write()`

The first optimization historically attempted was memory-mapped I/O via mmap():

void *file_ptr = mmap(NULL, file_size, PROT_READ, MAP_SHARED, file_fd, 0);
write(socket_fd, file_ptr, file_size);

By mapping the kernel's page cache directly into the process's virtual address space, mmap() eliminates the copy into the user buffer:

Disk -> Page Cache (DMA)
Page Cache -> Socket Buffer (CPU Copy)
Socket Buffer -> NIC (DMA)

This cuts down CPU copies from 2 to 1.

The Hidden Trap: `SIGBUS` Crashes

If another process truncates or deletes the file while your thread is executing write(socket_fd, file_ptr, ...), accessing that memory address generates a SIGBUS (Bus Error) signal. Unless your application installs a custom signal handler, the process crashes instantly.

3. Evolution Level 2: `sendfile()` Without Hardware Support

Linux 2.2 introduced the sendfile() syscall:

#include <sys/sendfile.h>

ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);

sendfile() instructs the kernel to transfer count bytes directly from in_fd (a file) to out_fd (a network socket).

+-----------------------------------------------------------------------+
| USER SPACE                                                            |
|                      (No data enters userspace)                       |
+-----------------------------------------------------------------------+
| KERNEL SPACE                                                          |
|              [ Page Cache ] ---- CPU Copy ----> [ Socket Buffer ]     |
|                     ^                                  |              |
|              DMA Copy|                                  |DMA Copy      |
|                     |                                  v              |
|                  [ Disk ]                            [ NIC ]          |
+-----------------------------------------------------------------------+

Results:

Context switches dropped from 4 to 2 (only one syscall invocation).
Zero user-space memory allocations.
But on older kernels or basic hardware, there is still 1 CPU copy between the page cache and the socket buffer.

4. Evolution Level 3: True Zero-Copy (Scatter-Gather DMA)

Starting in Linux 2.4, the kernel introduced Scatter-Gather DMA support for network sockets (NETIF_F_SG).

When the network card supports scatter-gather, the CPU no longer copies file data into the socket buffer. Instead, the kernel only passes buffer descriptors (pointers and lengths) to the socket buffer:

+-----------------------------------------------------------------------+
| USER SPACE                                                            |
|                      (No data enters userspace)                       |
+-----------------------------------------------------------------------+
| KERNEL SPACE                                                          |
|              [ Page Cache (Physical RAM) ]                            |
|                     ^           |                                     |
|              DMA Copy           | Direct DMA Read                     |
|              from Disk          |                                     |
|                     |           v                                     |
|                  [ Disk ]    [ NIC ] <--- Packet Headers              |
|                                 ^                                     |
|                                 | DMA Read                            |
|                       [ Socket Buffer ]                               |
|                 (File Descriptors & Headers Only)                     |
+-----------------------------------------------------------------------+

How `struct sk_buff` Handles This Internally

Inside the kernel networking stack, every packet is represented by a struct sk_buff (socket buffer).

Instead of allocating contiguous memory to hold both the TCP/IP headers and the file payload, the kernel uses fragmented skb buffers (skb_shinfo):

struct skb_shared_info {
    /* ... */
    nr_frags;
    skb_frag_t frags[MAX_SKB_FRAGS];
};

Each skb_frag_t holds:

A pointer to the physical memory page (struct page *) in the Page Cache.
An offset inside that page.
The byte length.

When the packet is scheduled for transmission:

The kernel constructs the TCP/IP headers in memory.
The NIC's DMA engine receives a scatter-gather list:
- Descriptor 1: Read 54 bytes (TCP/IP headers) from kernel memory.
- Descriptor 2: Read 1460 bytes (file payload) directly from the page cache address.
The NIC controller gathers the memory regions over the PCIe bus and stitches them into a single Ethernet frame on the wire.

CPU copies performed: Exactly ZERO.

5. `splice()`: Zero-Copy Between Arbitrary File Descriptors

While sendfile() is designed specifically for streaming files to sockets, Linux 2.6.17 introduced splice() to support zero-copy streaming between arbitrary file descriptors (pipes, sockets, block devices):

#define _GNU_SOURCE
#include <fcntl.h>

ssize_t splice(int fd_in, loff_t *off_in, int fd_out, loff_t *off_out, 
               size_t len, unsigned int flags);

The Magic of Pipe Buffers (`struct pipe_buffer`)

splice() works using kernel pipe buffers (struct pipe_inode_info). A pipe buffer in Linux does not allocate memory for data bytes; it is a circular ring of page pointers:

struct pipe_buffer {
    struct page *page;
    unsigned int offset;
    unsigned int len;
    const struct pipe_buf_operations *ops;
    unsigned int flags;
};

When you splice from a socket into a pipe, the kernel pins the network incoming page into the ring buffer. When you splice from that pipe into a file or another socket, the kernel transfers ownership of those page pointers without copying a single byte.

6. The Modern HTTPS Problem: Why TLS Broke Zero-Copy

For years, zero-copy had a massive limitation: Encryption.

If your web server runs HTTPS, traditional OpenSSL or BoringSSL pipelines look like this:

Read encrypted/raw data into userspace.
Run AES-GCM encryption in user memory.
Call write() with the ciphertext.

Because encryption requires reading and modifying every single byte, sendfile() was useless for HTTPS. Web servers were forced back into the slow 4-switch, 2-copy path.

The Solution: kTLS (Kernel TLS)

Linux 4.13 introduced kTLS (Kernel TLS, via SO_TLS_TX / TCP_ULP):

/* Enable Kernel TLS User-Level Protocol on the TCP socket */
setsockopt(sock_fd, SOL_TCP, TCP_ULP, "tls", sizeof("tls"));

/* Provide the symmetric cipher keys (AES-GCM-128 / 256) negotiated in userspace */
setsockopt(sock_fd, SOL_TLS, TLS_TX, &crypto_info, sizeof(crypto_info));

Once kTLS is enabled:

The userspace library (such as OpenSSL or Rustls) completes the initial TLS 1.3 handshake.
The session encryption keys are handed off to the kernel socket options.
The application calls standard sendfile()!
The kernel encrypts the page cache buffers inline as they flow through the network stack, or offloads encryption entirely to SmartNICs with TLS hardware accelerators.

This restored zero-copy throughput for HTTPS static file delivery in modern NGINX, HAProxy, and Envoy deployments.

7. Zero-Copy Performance Summary

Mechanism	Syscalls Used	Context Switches	CPU Memory Copies	DMA Copies	TLS Compatible?
Traditional I/O	`read()` + `write()`	4	2	2	Yes (Userspace crypto)
Memory Mapped	`mmap()` + `write()`	4	1	2	Yes (Userspace crypto)
`sendfile()`	`sendfile()`	2	1 (0 with SG-DMA)	2	Only with kTLS
`splice()`	`splice()`	2	0	2	Only with kTLS
`MSG_ZEROCOPY`	`send(..., MSG_ZEROCOPY)`	2	0 (Page pinning)	1	App-dependent

8. Senior Engineer Gotchas to Keep in Mind

MSG_ZEROCOPY on small payloads is a trap: For payloads under 10-16 KB, standard send() is faster. MSG_ZEROCOPY on raw memory buffers requires the kernel to pin user pages (get_user_pages_fast), set up completion notifications on the socket error queue (sock_extended_err), and notify userspace via poll()/epoll(). The bookkeeping overhead easily exceeds the cost of a small memcpy.
File modification during transfer: If you modify a file in place while sendfile() is actively reading page cache pages, the client will receive corrupted, mixed data frames. Always use atomic file replacements (rename/symlinks) for live assets.
Dirty Page Flushing: Zero-copy does not bypass Linux caching rules. Data must exist in the kernel page cache; if pages are evicted under memory pressure, synchronous disk reads will stall the I/O thread.

Key Takeaway

Zero-copy is not about avoiding disk or network hardware transfers; it is about eliminating redundant CPU memory copies and context switches across the kernel-userspace boundary.

By passing page descriptors (struct page *) through struct sk_buff and leveraging NIC Scatter-Gather DMA, the Linux kernel lets hardware controllers stream data straight from disk cache to the wire while keeping your CPU caches clean and cool.

How Model Context Protocol (MCP) Actually Works: JSON-RPC 2.0, Stdio IPC, and Low-Level Tool Calling

Syed Anzar — Thu, 08 Oct 2026 05:16:58 +0000

How Model Context Protocol (MCP) Actually Works: JSON-RPC 2.0, Stdio IPC, and Low-Level Tool Calling

If you have used Claude Desktop, Cursor, or modern local coding agents recently, you have probably configured a claude_desktop_config.json file or launched an MCP server with npx -y @modelcontextprotocol/server-postgres.

On the surface, it looks almost magical: an LLM suddenly connects to your local SQLite database, reads your local files, and executes commands.

Most tutorials explain MCP like this:

"MCP is an open standard that lets AI models interact with tools and data sources."

That definition tells you what it does, not how it actually works under the hood.

What actually happens between the moment you type a prompt and the moment a local script executes on your machine? How does a stateless LLM communicate with a stateful local process? Why does standard output (stdout) have a strict protocol rule that breaks your server if you use print() or console.log()?

Let us trace the entire lifecycle: from file descriptor pipes and JSON-RPC 2.0 frames to capability negotiation and token overhead.

1. The Architectural Problem MCP Actually Solved

Before Anthropic open-sourced the Model Context Protocol in late 2024, the AI ecosystem was drowning in the M × N Integration Problem.

BEFORE MCP (M × N Custom Integrations):
[Claude]    ---> Custom Plugin API ---> [Postgres]
[ChatGPT]   ---> Actions Schema    ---> [GitHub]
[Cursor]    ---> Custom Extension  ---> [Slack]
[LangChain] ---> BaseTool Wrapper  ---> [Local Filesystem]

WITH MCP (1 Standard Protocol):
[Any Host / Agent]  <=== JSON-RPC 2.0 ===>  [Any MCP Server]
(Claude, Cursor,                           (DBs, APIs, Files,
 Hermes, LangChain)                         Git, Local CLI)

If you had 5 agent hosts and 20 tools, developers had to write and maintain 100 separate integration wrappers.

MCP borrowed the architectural playbook of Microsoft's Language Server Protocol (LSP). Instead of every code editor writing a custom parser for TypeScript, Python, and Rust, LSP created a single standard JSON-RPC protocol.

MCP is LSP for AI agents.

2. The Three Core Entities

An MCP architecture consists of three distinct participants:

┌──────────────────────────────────────────────────────────┐
│ HOST APPLICATION (e.g., Claude Desktop, Cursor, Hermes)   │
│                                                          │
│  ┌───────────────────────┐      ┌─────────────────────┐  │
│  │ User Interface / UX   │      │ LLM Inference Engine│  │
│  └───────────┬───────────┘      └──────────┬──────────┘  │
│              │                             │             │
│              ▼                             ▼             │
│  ┌────────────────────────────────────────────────────┐  │
│  │ MCP CLIENT (Protocol Controller & State Manager)   │  │
│  └──────────┬──────────────────────────────┬──────────┘  │
└─────────────┼──────────────────────────────┼─────────────┘
              │ (Stdio Pipe / FD 0 & 1)      │ (HTTP + SSE)
              ▼                              ▼
┌──────────────────────────┐   ┌──────────────────────────┐
│ LOCAL MCP SERVER         │   │ REMOTE MCP SERVER        │
│ (sqlite, git, filesystem)│   │ (github, slack, db api)  │
└──────────────────────────┘   └──────────────────────────┘

Host: The user-facing application (Claude Desktop, Cursor, Hermes CLI). The host controls permissions, displays UI, and handles LLM model interactions.
Client: The internal protocol controller inside the host. A client maintains a strict 1:1 connection with each MCP server.
Server: An isolated program (local CLI or remote service) that exposes tools, data resources, and prompt templates through the protocol.

3. The Wire Protocol: JSON-RPC 2.0

Underneath the high-level SDKs (@modelcontextprotocol/sdk in TypeScript or mcp in Python), MCP communicates exclusively via JSON-RPC 2.0.

Every message transmitted over the wire falls into one of three structural types:

A. Request (Client to Server or Server to Client)

A request requires an explicit response. It carries a unique id to correlate asynchronous replies:

{
  "jsonrpc": "2.0",
  "id": 104,
  "method": "tools/call",
  "params": {
    "name": "query_database",
    "arguments": {
      "query": "SELECT id, email FROM users WHERE status = 'active' LIMIT 5;"
    }
  }
}

B. Response (Success or Error)

The receiver matches the incoming id and returns either a result payload or an error object:

{
  "jsonrpc": "2.0",
  "id": 104,
  "result": {
    "content": [
      {
        "type": "text",
        "text": "[{\"id\": 1, \"email\": \"alex@example.com\"}]"
      }
    ],
    "isError": false
  }
}

If an execution failure occurs, the server returns standard JSON-RPC error codes (such as -32600 for Invalid Request or -32601 for Method Not Found):

{
  "jsonrpc": "2.0",
  "id": 104,
  "error": {
    "code": -32602,
    "message": "Invalid params: 'query' field cannot be empty"
  }
}

C. Notification (One-Way Signaling)

Notifications never contain an id field and must not be answered. They are used for fire-and-forget events like logging or state updates:

{
  "jsonrpc": "2.0",
  "method": "notifications/tools/list_changed",
  "params": {}
}

4. Stdio Transport: File Descriptors and the Stderr Rule

When running an MCP server locally, the host starts the server as a child sub-process using standard Operating System process pipes.

HOST (Client Process)                      CHILD (MCP Server Process)
┌──────────────────────┐                   ┌────────────────────────┐
│                      │ ─── Stdin (FD 0) ──>│ JSON Parser Reader   │
│ Client Runtime       │                   │                        │
│                      │ <── Stdout (FD 1) ──│ JSON-RPC Serializer  │
│                      │                   │                        │
│ Log Collector / UI   │ <── Stderr (FD 2) ──│ Debug / Diagnostic   │
└──────────────────────┘                   └────────────────────────┘

This transport mechanism has critical engineering implications:

File Descriptor Roles

Standard Input (FD 0): The host writes newline-delimited (\n) JSON-RPC messages directly to the server's input stream.
Standard Output (FD 1): The server writes its newline-delimited JSON-RPC responses to stdout.
Standard Error (FD 2): Reserved strictly for human-readable logging and diagnostics.

The Most Common MCP Server Bug

If you write an MCP server in Python or Node.js and include a diagnostic print("Connected to DB") or console.log("Fetching data..."), your server will immediately crash.

Why? Standard print() in Python writes directly to stdout (FD 1).

When the host client's stream parser reads a raw string like "Connected to DB" instead of a valid JSON object, the JSON parser fails with a syntax error, drops the connection, and kills the session.

To log safely in an MCP server, you must explicitly redirect output to stderr (FD 2):

import sys

# CRASHES THE MCP CLIENT (Pollutes FD 1):
# print("Processing record...")

# SAFE: Directs log message to FD 2:
sys.stderr.write("[DEBUG] Processing record...\n")
sys.stderr.flush()

5. SSE Transport: Remote Execution Over HTTP

While stdio is ideal for local desktop environments, distributed microservices require network transport. MCP handles this via Server-Sent Events (SSE) over HTTP.

CLIENT (Host)                                 SERVER (Remote Endpoint)
   │                                                    │
   │ 1. GET /sse (Accept: text/event-stream)            │
   │───────────────────────────────────────────────────>│
   │                                                    │
   │ 2. HTTP 200 SSE Stream Opened                     │
   │    event: endpoint                                 │
   │    data: /messages?sessionId=a8f9-4b21             │
   │<───────────────────────────────────────────────────│
   │                                                    │
   │ 3. POST /messages?sessionId=a8f9-4b21 (JSON-RPC)   │
   │───────────────────────────────────────────────────>│
   │    HTTP 202 Accepted                               │
   │<───────────────────────────────────────────────────│
   │                                                    │
   │ 4. SSE Push (JSON-RPC Response)                    │
   │    event: message                                  │
   │    data: {"jsonrpc":"2.0","id":1,"result":{...}}   │
   │<───────────────────────────────────────────────────│

Why did MCP choose SSE + HTTP POST instead of WebSockets?

Firewall & Proxy Compatibility: SSE operates over plain HTTP/1.1 or HTTP/2 streams without requiring WebSocket upgrade handshakes that often get blocked in enterprise proxies.
Built-in Reconnection: Browsers and HTTP clients have native SSE reconnection semantics.
Separation of Upstream & Downstream: Heavy payloads sent via POST do not choke the incoming event stream.

6. The Protocol Lifecycle: Handshake to Execution

Before an LLM can invoke a single function, the client and server complete a 3-step initialization handshake.

CLIENT                                                   SERVER
  │                                                        │
  │ 1. Request: "initialize"                               │
  │    (Protocol Version + Client Capabilities)            │
  │───────────────────────────────────────────────────────>│
  │                                                        │
  │ 2. Response: Server Info & Capabilities                │
  │    (tools, resources, prompts, logging)                │
  │<───────────────────────────────────────────────────────│
  │                                                        │
  │ 3. Notification: "notifications/initialized"           │
  │───────────────────────────────────────────────────────>│
  │                                                        │
  │ 4. Request: "tools/list"                               │
  │───────────────────────────────────────────────────────>│
  │                                                        │
  │ 5. Response: Array of Tool Definitions (JSON Schema)   │
  │<───────────────────────────────────────────────────────│
  │                                                        │
  │           [Session is now Ready for Tool Calls]        │

Step 1: The `initialize` Request

The client starts by announcing its supported protocol version and capabilities:

{
  "jsonrpc": "2.0",
  "id": 1,
  "method": "initialize",
  "params": {
    "protocolVersion": "2024-11-05",
    "capabilities": {
      "roots": { "listChanged": true },
      "sampling": {}
    },
    "clientInfo": {
      "name": "hermes-agent",
      "version": "1.4.0"
    }
  }
}

Step 2: The Server Response

The server responds with its identity and the features it supports:

{
  "jsonrpc": "2.0",
  "id": 1,
  "result": {
    "protocolVersion": "2024-11-05",
    "capabilities": {
      "tools": { "listChanged": true },
      "resources": { "subscribe": true }
    },
    "serverInfo": {
      "name": "sqlite-query-engine",
      "version": "2.1.0"
    }
  }
}

Step 3: Acknowledgment

The client sends {"jsonrpc": "2.0", "method": "notifications/initialized"}. The connection state transitions from INITIALIZING to ACTIVE.

7. The Three MCP Primitives

MCP groups all capabilities into three distinct primitives:

Primitive	Controller	Dynamic?	Primary Use Case
Tools	Model-controlled	Yes (invoked by LLM)	Running queries, executing code, sending webhooks, modifying files
Resources	Application-controlled	Read-only / Subscribable	Providing system logs, database schemas, active file contents
Prompts	User-controlled	Parameterized templates	Predefined workflows, specialized role prompts, slash commands

How Tools Are Defined: JSON Schema Draft-07

When the client calls tools/list, the server returns an array of tool objects. Every argument must be defined using standard JSON Schema:

{
  "name": "calculate_mortgage",
  "description": "Calculates monthly amortization payments based on principal and APR.",
  "inputSchema": {
    "type": "object",
    "properties": {
      "principal": {
        "type": "number",
        "description": "Total loan amount in USD"
      },
      "annual_rate": {
        "type": "number",
        "description": "Annual interest rate as a decimal (e.g. 0.065 for 6.5%)"
      },
      "term_years": {
        "type": "integer",
        "description": "Loan duration in years"
      }
    },
    "required": ["principal", "annual_rate", "term_years"]
  }
}

The host client takes these raw JSON schemas and converts them into the specific function-calling format expected by the target LLM provider (Anthropic XML tools, OpenAI function tools, or Gemini declaration schemas).

8. What Happens During a Tool Call: End-to-End Execution Trace

Here is the exact trace of what happens when you ask an assistant: "Find all overdue invoices in SQLite."

1. USER: "Find all overdue invoices."
      │
      ▼
2. HOST: Injects system prompt + formatted tool schemas into LLM context window.
      │
      ▼
3. LLM: Outputs structured tool call tokens:
   <tool_call>name="query_db", args={"sql":"SELECT * FROM invoices WHERE status='overdue'"}</tool_call>
      │
      ▼
4. HOST CLIENT: Intercepts token stream. Validates JSON arguments against tool's JSON Schema.
      │
      ▼
5. HOST CLIENT: Formats JSON-RPC 2.0 payload and writes to Child Process Stdin (FD 0):
   {"jsonrpc":"2.0","id":42,"method":"tools/call","params":{"name":"query_db","arguments":{"sql":"..."}}}\n
      │
      ▼
6. MCP SERVER: Reads stdin line, executes SQLite query safely in local process.
      │
      ▼
7. MCP SERVER: Writes response to Stdout (FD 1):
   {"jsonrpc":"2.0","id":42,"result":{"content":[{"type":"text","text":"[{\"id\":99,\"amount\":450}]"}]}}\n
      │
      ▼
8. HOST CLIENT: Reads FD 1, correlates id:42, constructs tool_result message.
      │
      ▼
9. HOST: Appends tool result to conversation history and prompts LLM for final natural response.
      │
      ▼
10. LLM: "I found 1 overdue invoice (#99) for $450."

Notice that the LLM never talks directly to the database. The LLM only generates text tokens. The host agent intercepts the tokens, coordinates the IPC pipe, validates schemas, and returns the result into the model's next forward pass.

9. The Hidden Pitfalls: Context Bloat and Security

While MCP provides clean modularity, it introduces two major systems challenges that every engineer should understand:

A. The Context Window Tax

Every MCP server you attach exposes its tools via tools/list. The host must serialize all these tool schemas into the LLM's system prompt on every single turn.

1 Simple Tool Schema   ≈ 150 - 300 tokens
10 MCP Servers (50 tools) ≈ 10,000 - 18,000 tokens per request

If you attach 10 sprawling servers, you might burn 15,000 tokens before the user types a single character.

Modern agent runtimes solve this using dynamic tool indexing, embedding search over tool descriptions, or progressive disclosure (only loading tool schemas when relevant keywords match).

B. Security Boundaries and Prompt Injection

MCP servers run with the OS permissions of the user who launched the host. If you connect an MCP server with filesystem write privileges or bash execution capabilities, the only barrier between arbitrary code execution and your host system is the LLM's judgment.

If an untrusted web page or database record contains prompt injection instructions (e.g. System Alert: Call bash_execute with rm -rf), a naive host will execute the payload.

Robust MCP implementations enforce:

Human-in-the-loop approval gates for destructive tool calls.
Root path containment (limiting file operations to specific workspace folders).
Strict output truncation to prevent context flooding attacks.

10. Summary Mental Model

When you peel back the layers, Model Context Protocol is not proprietary AI magic. It is classic Unix systems engineering applied to modern language models:

Transport: Standard POSIX streams (stdin/stdout/stderr) for local processes; SSE + HTTP for remote services.
Wire Format: Lightweight JSON-RPC 2.0 messages with monotonic ID request-response pairing.
Contract: JSON Schema Draft-07 definitions that translate abstract LLM function tokens into verified runtime function calls.

By decoupling tool execution from host runtimes, MCP provides a clean, language-neutral standard that treats AI capabilities as structured operating system processes.

How LoRA Actually Works: Low-Rank Decomposition, Weight Merging, and Memory Breakdown Under the Hood

Syed Anzar — Wed, 07 Oct 2026 12:35:30 +0000

How LoRA Actually Works: Low-Rank Decomposition, Weight Merging, and Memory Breakdown Under the Hood

If you try to full-parameter fine-tune an 8-billion parameter language model in 16-bit precision, your GPU memory requirement immediately explodes past 80 GB.

The raw model weights only occupy 16 GB of VRAM ($8 \times 10^9 \text{ parameters} \times 2 \text{ bytes}$). Yet standard training crashes on a single 80 GB A100 or H100.

Where does the missing 64+ GB of VRAM go? And why can Low-Rank Adaptation (LoRA) reduce that memory footprint by over 70% while updating fewer than 0.1% of the parameters and retaining 99% of full fine-tuning performance?

Here is what actually happens mathematically, mechanically, and in physical GPU memory during LoRA fine-tuning and inference.

1. The Real Memory Culprit: Why Full Fine-Tuning Explodes

When training a neural network with the standard AdamW optimizer, model weights are only a tiny fraction of your memory consumption.

For every single trainable parameter, the system must track:

FP16 / BF16 Model Weights: 2 bytes
FP16 / BF16 Gradients: 2 bytes
FP32 Master Weights (for numerical stability): 4 bytes
FP32 First Momentum ($m_t$): 4 bytes
FP32 Second Momentum ($v_t$): 4 bytes

$$\text{Total Memory per Trainable Parameter} = 2 + 2 + 4 + 4 + 4 = 16 \text{ bytes}$$

+-------------------------------------------------------------+
| Full Parameter Training (16 bytes per parameter)            |
+-------------------------------------------------------------+
| Weights: 2B | Grads: 2B | Master: 4B | Mom1: 4B | Mom2: 4B  |
+-------------------------------------------------------------+

For an 8B parameter model:

Optimizer States: $8\text{B} \times 12 \text{ bytes} = 96 \text{ GB}$
Gradients: $8\text{B} \times 2 \text{ bytes} = 16 \text{ GB}$
Model Weights: $8\text{B} \times 2 \text{ bytes} = 16 \text{ GB}$
Baseline Total (before activation memory and KV cache): $\approx 128 \text{ GB}$

This is why full fine-tuning requires multi-GPU distributed clusters (DeepSpeed ZeRO or FSDP).

LoRA solves this problem at its root: by freezing the base weights, it eliminates optimizer states and gradients for 99.9% of the model.

2. The Intrinsic Rank Hypothesis

Why does freezing the model work?

A standard linear layer in a transformer computes:

$$h = W_0 x$$

where $W_0 \in \mathbb{R}^{d \times k}$, $x \in \mathbb{R}^{k}$, and $h \in \mathbb{R}^{d}$. For Llama 3 8B, the hidden dimension $d = 4096$. Each weight matrix has up to $4096 \times 4096 \approx 16.7\text{M}$ parameters with full mathematical rank 4096.

In 2021, Edward Hu et al. published the foundational hypothesis behind LoRA:

When adapting a pre-trained language model to a specific task or instruction format, the weight update matrix $\Delta W$ has an extremely low "intrinsic rank" ($r \ll d$).

The pre-trained model already knows syntax, world facts, and language logic. Fine-tuning is merely steering attention and adjusting feature selection. You do not need to update 16 million degrees of freedom per matrix; you only need to update a tiny subspace of dimension $r$ (typically $r = 8, 16, \text{ or } 32$).

3. The Math: Low-Rank Matrix Factorization

Instead of directly learning a full $d \times k$ matrix $\Delta W$, LoRA decomposes $\Delta W$ into the product of two small, low-rank matrices:

$$\Delta W = B \cdot A$$

where:

$A \in \mathbb{R}^{r \times k}$ (down-projection)
$B \in \mathbb{R}^{d \times r}$ (up-projection)
$r \ll \min(d, k)$

   Full Update Matrix ΔW (d × k)            LoRA Decomposition
   +---------------------------+       +-------+
   |                           |       |       |       +---------------------------+
 d |                           |   = d |   B   |   × r |             A             |
   |                           |       | (d×r) |       +---------------------------+
   +---------------------------+       +-------+                     k
                 k

The Parameter Reduction Math

Suppose $d = 4096, k = 4096$, and you choose rank $r = 16$:

Full matrix parameters: $4096 \times 4096 = 16,777,216$
Matrix A parameters: $16 \times 4096 = 65,536$
Matrix B parameters: $4096 \times 16 = 65,536$
Total LoRA parameters: $65,536 + 65,536 = 131,072$

$$\text{Reduction Factor} = \frac{16,777,216}{131,072} = 128\times \text{ fewer parameters (99.2% reduction)}$$

Multiply that across 32 transformer layers, and your trainable parameters drop from 8 billion down to ~20 million.

4. Initialization and the Scaling Factor $\alpha$

Two critical implementation details make LoRA stable and practical:

Detail A: Zero Initialization of Matrix B

How do you prevent random noise from wrecking the pre-trained model at the start of training?

Matrix $A$ is initialized with random Gaussian values $\mathcal{N}(0, \sigma^2)$ or Kaiming uniform.
Matrix $B$ is initialized to exact zeros ($B = 0$).

At step 0 of training:

$$\Delta W = B \cdot A = 0 \cdot A = 0$$

The adapter initially produces an exact zero vector. The model starts training with the exact output of the pre-trained base model, ensuring smooth and stable gradient descent.

Detail B: The Scaling Factor $\frac{\alpha}{r}$

The modified forward pass with LoRA includes a constant scaling multiplier $\frac{\alpha}{r}$:

$$h = W_0 x + \frac{\alpha}{r} (B \cdot A) x$$

$r$ is the chosen rank.
$\alpha$ is a constant scaling hyperparameter (usually set to $2r$ or equal to $r$).

Why does $\frac{\alpha}{r}$ exist?

When you experiment with different ranks (e.g., jumping from $r=8$ to $r=64$), the magnitude of the matrix multiplication $BAx$ naturally scales with $r$. The $\frac{\alpha}{r}$ term normalizes the magnitude of the adapter's update. This allows you to change the rank $r$ without needing to retune your learning rate from scratch.

5. Forward and Backward Pass: What the GPU Actually Computes

During training, the computation branches into two parallel paths:

                      Input x
                     /       \
                    /         \
    [Frozen Base Weight]    [Matrix A (r × k)]  (Down-project to r)
          W₀ x                     |
            |                 [Matrix B (d × r)]  (Up-project to d)
            |                      |
            |               Scale by (α / r)
            \                     /
             \                   /
              +------> (+) <----+
                        |
                     Output h

Forward Computation

Base branch: The input vector $x$ is multiplied by the frozen pre-trained weight $W_0 x$. (If using QLoRA, $W_0$ is dequantized from 4-bit NormalFloat to 16-bit float on the fly).
Adapter branch: The input vector $x$ is first multiplied by matrix $A$ (reducing the vector to size $r$), then multiplied by matrix $B$ (expanding back to dimension $d$), and multiplied by $\frac{\alpha}{r}$.
Combination: The outputs are summed together element-wise: $h = W_0 x + \frac{\alpha}{r} BAx$.

Backward Computation

During backpropagation:

Gradients $\frac{\partial \mathcal{L}}{\partial A}$ and $\frac{\partial \mathcal{L}}{\partial B}$ are calculated and stored in memory.
The optimizer updates only the small matrices $A$ and $B$.
No optimizer states are allocated for $W_0$. No gradients are saved for $W_0$.

6. Zero-Latency Serving: Weight Merging

One of the biggest advantages of LoRA over earlier adapter architectures (like Houlsby adapters or prompt tuning) is that LoRA introduces zero additional inference latency.

In production deployment, you do not keep two separate matrix multiplication branches in memory. Because matrix multiplication is distributive:

$$h = W_0 x + \Delta W x = (W_0 + \Delta W) x$$

Before exporting your model for deployment, you merge the adapter weights directly into the base weights with a single matrix addition:

$$W_{\text{serving}} = W_0 + \frac{\alpha}{r} (B \cdot A)$$

Once added, the adapter matrices $A$ and $B$ are discarded. The final serving model has the exact same architecture, tensor count, and latency as the original base model.

+-----------------------------------------------------------+
| Base Weights W₀           LoRA Weights (B × A)            |
| [ 4096 × 4096 ]     +     [ 4096 × 4096 ]                 |
+-----------------------------------------------------------+
                             ↓
+-----------------------------------------------------------+
| Merged Weights W_serving                                  |
| [ 4096 × 4096 ] → Standard inference speed, zero latency  |
+-----------------------------------------------------------+

If you need to switch tasks dynamically (multi-tenant serving), systems like S-LoRA or vLLM Multi-LoRA keep the base model frozen in VRAM and compute the small $BAx$ branch on the fly for distinct requests using custom batched GEMM kernels (like Punica).

7. A Minimal PyTorch Implementation from Scratch

To see how straightforward the mechanics are, here is a complete, working LoRA linear layer implemented in pure PyTorch:

import math
import torch
import torch.nn as nn

class LoRALinear(nn.Module):
    def __init__(
        self,
        in_features: int,
        out_features: int,
        r: int = 16,
        lora_alpha: float = 32.0,
        lora_dropout: float = 0.05
    ):
        super().__init__()
        # 1. Base pre-trained linear layer (frozen)
        self.base_layer = nn.Linear(in_features, out_features, bias=False)
        self.base_layer.weight.requires_grad = False

        self.r = r
        self.lora_alpha = lora_alpha
        self.scaling = lora_alpha / r

        if r > 0:
            # 2. Low-rank matrices A and B
            self.lora_A = nn.Parameter(torch.empty(r, in_features))
            self.lora_B = nn.Parameter(torch.empty(out_features, r))
            self.dropout = nn.Dropout(p=lora_dropout) if lora_dropout > 0 else nn.Identity()

            # 3. Initialization: Kaiming uniform for A, exact zeros for B
            nn.init.kaiming_uniform_(self.lora_A, a=math.sqrt(5))
            nn.init.zeros_(self.lora_B)

        self.merged = False

    def forward(self, x: torch.Tensor) -> torch.Tensor:
        if self.merged or self.r == 0:
            return self.base_layer(x)

        # Standard LoRA forward pass: W₀x + (α/r) * B(A(dropout(x)))
        base_out = self.base_layer(x)
        lora_out = (self.dropout(x) @ self.lora_A.T) @ self.lora_B.T * self.scaling
        return base_out + lora_out

    def merge(self):
        """Fold LoRA weights into base weights for zero-overhead serving."""
        if self.r > 0 and not self.merged:
            # Compute ΔW = (α/r) * B @ A
            delta_w = (self.lora_B @ self.lora_A) * self.scaling
            self.base_layer.weight.data += delta_w
            self.merged = True

    def unmerge(self):
        """Subtract LoRA weights to resume training or swap adapters."""
        if self.r > 0 and self.merged:
            delta_w = (self.lora_B @ self.lora_A) * self.scaling
            self.base_layer.weight.data -= delta_w
            self.merged = False

8. Memory Breakdown: Full Fine-Tuning vs LoRA vs QLoRA

Here is how the memory footprint compares on an 8-billion parameter model (batch size 2, sequence length 2048):

Component	Full Fine-Tuning (BF16)	LoRA ($r=16$, All Linears)	QLoRA (4-bit Base + LoRA)
Base Model Weights	16.0 GB (BF16)	16.0 GB (BF16)	4.5 GB (NF4)
Adapter Weights	N/A	0.08 GB (BF16)	0.08 GB (BF16)
Gradients	16.0 GB	0.08 GB	0.08 GB
Optimizer States (AdamW)	96.0 GB	0.48 GB	0.48 GB
Activations (w/ checkpointing)	~6.0 GB	~6.0 GB	~6.0 GB
Total VRAM Needed	~134 GB	~22.6 GB	~11.1 GB
Hardware Required	2x A100 (80GB)	1x RTX 3090 / 4090 (24GB)	1x RTX 3060 (12GB)

9. Four Common LoRA Mistakes Developers Make

1. Targeting Only Attention Projections ($q_proj, v_proj$)

The original 2021 LoRA paper demonstrated proof-of-concept results by attaching adapters only to Query and Value projections. However, multiple empirical studies (such as QLoRA by Dettmers et al.) prove that targeting all linear layers ($q, k, v, o$, as well as MLP layers $gate, up, down_proj$) yields significantly higher accuracy and expressive capacity, even with a smaller rank like $r=8$ or $r=16$.

2. Setting Alpha to Arbitrary Values

A common convention is setting $\alpha = 2 \times r$ or $\alpha = r$. If you double your rank $r$ from 16 to 32 but leave $\alpha$ unchanged at 32, you have inadvertently halved the effective learning rate of your adapter ($\frac{\alpha}{r}$ drops from 2.0 to 1.0). Keep your $\frac{\alpha}{r}$ ratio consistent when sweeping rank values.

3. Deploying Without Merging

If you are deploying a single specialized model in production, leaving LoRA as separate branches adds unnecessary kernel launches and memory bandwidth overhead. Always call .merge_and_unload() in Hugging Face PEFT or manually fold weights before saving your deployment artifact.

4. Overfitting with Excessively High Rank ($r > 64$)

Setting $r=128$ or $r=256$ rarely improves downstream task accuracy for instruction fine-tuning, but it drastically increases memory consumption and risk of catastrophic forgetting. For standard instruction tuning and classification, $r \in [8, 32]$ is almost always the empirical sweet spot.

Summary Mental Model

Full fine-tuning is expensive because AdamW optimizer states require 12 bytes per parameter on top of weights and gradients.
LoRA decomposes the weight update $\Delta W$ into two low-rank matrices $B \times A$, slashing trainable parameters and optimizer states by over 99%.
Initialization ($B=0$) ensures training starts identically to the pre-trained base model.
Serving requires zero extra latency because low-rank matrices fold directly into the base weights ($W_0 + \frac{\alpha}{r} BA$) via simple addition.

Why Write-Heavy Databases Use LSM-Trees: MemTables, SSTables, Bloom Filters, and Compaction Under the Hood

Syed Anzar — Wed, 07 Oct 2026 11:33:55 +0000

When building applications that ingest massive write streams (such as high-frequency telemetry, financial transaction logs, metrics collectors, or event queues), relational databases with standard B-Tree indexes eventually hit an I/O brick wall.

Even on ultra-fast NVMe SSDs, write throughput collapses, disk queues back up, and I/O latency spikes into hundreds of milliseconds.

To solve this exact bottleneck, modern distributed systems like RocksDB, Apache Cassandra, ScyllaDB, ClickHouse, TiKV, and BadgerDB abandoned B-Trees entirely. Instead, they run on a storage architecture called the Log-Structured Merge-Tree (LSM-Tree).

Here is what actually happens inside an LSM-Tree storage engine, why it turns expensive random disk writes into high-speed sequential streaming, and how it balances the brutal trade-offs between read, write, and space amplification.

The Root Problem: Why B-Trees Choke on Writes

To understand why LSM-Trees exist, you first have to see where classical B-Trees fail under heavy write loads.

In a traditional B-Tree (used by PostgreSQL, MySQL InnoDB, and SQLite), data is organized into fixed-size disk pages (typically 4KB, 8KB, or 16KB). When you insert a new record or update an existing row:

The database traverses the tree in memory to find the exact leaf page containing that key.
The page is modified in the buffer pool.
The page is marked dirty.
A background flush (or checkpoint process) writes the entire 8KB page back to its specific physical offset on disk.

Classical B-Tree (In-Place Updates):
[ Client PUT: key="user_912", val="active" (32 bytes) ]
                      │
                      ▼
[ Buffer Pool: Locates Page #4189 (8,192 bytes) ]
                      │ Modifies 32 bytes in memory
                      ▼
[ Disk: Overwrites Page #4189 at Random Offset 0x7FA0200 ]

This model is called In-Place Update (Update-in-Place). It is fast for reads because every key lives in exactly one predictable disk page. But for writes, it creates two major bottlenecks:

Massive Write Amplification (WA): If you modify a 50-byte record, the engine must write the entire 8KB/16KB page to disk. That is a 160x to 320x write amplification penalty at the storage layer.
Random I/O Thrashing: Even on modern NVMe drives, random writes force the Flash Translation Layer (FTL) to execute continuous garbage collection and block erases. Flash memory cannot overwrite bytes in place; it must erase entire NAND blocks (often 2MB to 8MB) to write updated 4KB pages.

Under sustained write ingestion of 50,000+ records per second, B-Tree engines spend almost all their I/O budget flushing scattered pages across random disk blocks.

The LSM-Tree Philosophy: "Never Modify Disk in Place"

First introduced by Patrick O'Neil, Edward O'Neil, and Gerhard Weikum in 1996, the LSM-Tree operates on one simple, radical principle:

All writes, updates, and deletes are strictly sequential appends to immutable files.

An LSM-Tree engine never seeks to a random file offset to update existing bytes. It accepts writes in memory, sorts them in batches, and streams them to disk sequentially.

To make this work without making reads impossibly slow, an LSM storage engine relies on four core components:

+──────────────────────────────────────────────────────────────+
│                       INCOMING WRITES                        │
+──────────────────────────────────────────────────────────────+
               │                                │
               ▼                                ▼
       +───────────────+               +────────────────+
       │ Write-Ahead   │ (Disk)        │ Active MemTable│ (RAM: SkipList)
       │ Log (WAL)     │ Append-Only   │ Sorted in-RAM  │
       +───────────────+               +────────────────+
                                                │
                                                ▼ (When Full: ~64MB)
                                       +────────────────+
                                       │ Immutable      │
                                       │ MemTable (RAM) │
                                       +────────────────+
                                                │
                                                ▼ (Background Flush)
================================================================
DISK STORAGE (Immutable SSTables)
================================================================
 Level 0 (L0):  [ SSTable 1 ]   [ SSTable 2 ]   [ SSTable 3 ]
                (Keys overlap across files)
                      │
                      ▼ Compaction (Multi-way Merge Sort)
 Level 1 (L1):  [ SSTable A ] ─── [ SSTable B ] ─── [ SSTable C ]
                (Keys strictly partitioned, non-overlapping)
                      │
                      ▼ Compaction
 Level 2 (L2):  [ SST 10 ] ────── [ SST 11 ] ────── [ SST 12 ] ...

Let us break down each component under the hood.

1. The Write-Ahead Log (WAL)

Because incoming writes are initially stored in RAM, a sudden power failure or OS crash would lose all uncommitted data.

To guarantee ACID durability (the "D" in ACID), the engine first appends the raw operation to an append-only disk log called the Write-Ahead Log (WAL) using sequential writes.

Sequential writes to disk do not require random seeks or NAND block reallocations. The OS writes data straight into page cache buffers and streams it out in contiguous chunks. This allows the WAL to achieve near-saturating disk bus bandwidth with sub-millisecond latency.

2. The MemTable (In-Memory Sorted Buffer)

Simultaneously with the WAL append, the key-value pair is inserted into an in-memory data structure called the MemTable.

Unlike a hash map, the MemTable must keep all keys sorted at all times. Most production engines (such as RocksDB and LevelDB) implement the MemTable as a SkipList.

Why a SkipList Instead of a Red-Black Tree?

A Red-Black Tree or AVL Tree requires pointer rebalancing and node rotations during insertions, which locks large portions of the tree and kills multi-threaded concurrency.

A SkipList uses probabilistic multi-level linked lists with lock-free atomic pointer swaps (CAS - Compare-And-Swap), allowing multiple writer and reader threads to operate concurrently without coarse-grained mutex contention:

Level 3: [10] ─────────────────────────────> [90] ──> NULL
Level 2: [10] ─────────────> [45] ─────────> [90] ──> NULL
Level 1: [10] ──> [25] ────> [45] ──> [60] ─> [90] ──> NULL
Level 0: [10] ──> [25] ─[30]─[45] ──> [60] ─> [90] ──> NULL

When the active MemTable reaches a configurable threshold (typically 64MB or 128MB via write_buffer_size), the engine:

Marks the active MemTable as Immutable (read-only).
Instantly allocates a fresh, empty MemTable to accept new incoming client writes without pausing traffic.
Spawns a background thread to flush the immutable MemTable to disk as an SSTable.

3. SSTables (Sorted String Tables)

An SSTable (Sorted String Table) is an immutable, ordered file on disk.

Because the MemTable was already sorted in memory, writing an SSTable to disk is a pure sequential stream (an O(N) linear write). Once written, an SSTable is never modified. It is read-only for its entire lifetime until it is eventually deleted during compaction.

An SSTable file is structured internally into distinct blocks:

+───────────────────────────────────────────────────────────────+
│ Data Block 0:  [ "alice": {...}, "bob": {...}, "carol": {...} ]│
├───────────────────────────────────────────────────────────────┤
│ Data Block 1:  [ "dave": {...}, "eve": {...}, "frank": {...} ] │
├───────────────────────────────────────────────────────────────┤
│ Data Block 2:  [ "grace": {...}, "heidi": {...}, "ivan": {...}│
├───────────────────────────────────────────────────────────────┤
│ Filter Block:  [ Bloom Filter Bit Array for all keys in SST ] │
├───────────────────────────────────────────────────────────────┤
│ Index Block:   [ "alice" -> Block 0 Offset,                   │
│                  "dave"  -> Block 1 Offset,                   │
│                  "grace" -> Block 2 Offset ]                  │
├───────────────────────────────────────────────────────────────┤
│ Footer:        [ Magic Number, Index Offset, Filter Offset ]  │
+───────────────────────────────────────────────────────────────+

Data Blocks: Fixed-size chunks (typically 4KB to 64KB, compressed with ZSTD or Snappy) containing sorted key-value entries.
Index Block: A directory mapping the start key of each data block to its exact byte offset inside the file.
Filter Block: In-memory Bloom filter bit array for zero-I/O membership checks.
Footer: Fixed-size trailer at the end of the file containing pointers to the Index and Filter blocks.

To read a key from an SSTable, the engine loads the Index Block, runs binary search on the keys (O(log N)), identifies the exact Data Block, and decompresses only that single block.

4. Bloom Filters: Preventing Disk Search Explosions

Because an LSM engine can have hundreds of SSTable files on disk, how does it avoid reading 100 files just to find out that a key does not exist?

This is solved by Bloom Filters stored in RAM.

A Bloom filter is a space-efficient probabilistic data structure. For every key added to an SSTable during flush:

The key is passed through $k$ independent hash functions.
The corresponding $k$ bit positions in a bit array are set to 1.

Key: "user_402"
Hash1("user_402") % 16 = 3  ──┐
Hash2("user_402") % 16 = 7  ──┼──> Set bits 3, 7, 12 to 1
Hash3("user_402") % 16 = 12 ──┘

Bit Array: [ 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 ]
                         ^               ^                       ^
                       Bit 3           Bit 7                   Bit 12

When looking up a key:

If any of the $k$ bit positions is 0, the key definitely does not exist in that SSTable. The database skips the file entirely with zero disk I/O.
If all bits are 1, the key might exist. The engine reads the SSTable index block.

With just 10 bits per key, a Bloom filter achieves a false positive rate under 1%. That means 99% of negative file lookups are eliminated in RAM before touching the disk.

The Complete Write and Read Paths

Now let us trace how PUT and GET operations traverse the engine.

The Write Path (Latency: Microseconds)

Client PUT(k, v) 
    │
    ├──> 1. Append record to Write-Ahead Log (Sequential Disk Append)
    │
    └──> 2. Insert into Active MemTable SkipList (In-Memory O(log N))
    │
    └──> 3. Return 200 OK to Client

The write is complete. No pages were searched, no disk blocks were rewritten, and no locks were held on tree nodes.

The Read Path (Hierarchical Traversal)

When a client requests GET(key):

Search Active MemTable: Check the in-memory SkipList. If found, return the value immediately (most recent write).
Search Immutable MemTables: Check any in-memory MemTables waiting to be flushed.
Search Level 0 SSTables: L0 files are direct dumps of MemTables, so their key ranges can overlap. The engine checks Bloom filters from newest to oldest L0 SSTable.
Search Level 1 to Level N SSTables: In Level 1 and beyond, key ranges within each level are strictly non-overlapping. The engine runs a binary search across level metadata to pick the single candidate SSTable, checks its Bloom filter, and reads the data block.

       GET("order_883")
              │
    [ Active MemTable ] ──── Found? ───> Return Value
              │ No
    [ Immutable MemTables ] ─ Found? ──> Return Value
              │ No
    [ Level 0 SSTables ] ─── Bloom Check ──> Match? ──> Read Block
              │ No
    [ Level 1 SSTables ] ─── Binary Search Files ──> Bloom Check ──> Read Block
              │ No
    [ Level 2..N SSTables ]

The Tombstone Paradox: Why Deletes Increase Disk Usage

How do you delete a record in a storage engine where disk files are immutable?

You cannot go back and erase bytes from an existing SSTable. Instead, the engine executes deletions by appending a new record with a special flag called a Tombstone:

Client: DELETE("user_104")
Engine: PUT("user_104", DELETED_TOMBSTONE_MARKER)

This leads to the Tombstone Paradox:

In an LSM-Tree, deleting a million rows immediately increases disk usage and consumes memory buffers.

When a read query searches for "user_104", it encounters the tombstone in the newest SSTable and returns None (Key Not Found).

The old values living in older SSTables are not physically removed until a background process called Compaction merges the levels.

Compaction: Merging the Levels and Paying the Debt

If writes keep appending SSTables indefinitely, three problems emerge:

Disk space fills up with obsolete versions of updated keys and expired tombstones.
Read performance degrades because queries must search through dozens of SSTables.
Level 0 file counts balloon.

To solve this, LSM engines run continuous background Compaction. Compaction reads multiple sorted SSTable files, merges them using an $O(N)$ Multi-Way Merge Sort, discards dead records, and outputs new, cleanly sorted, non-overlapping SSTable files.

SSTable 1: [ "apple": $1.00 (v1),  "banana": $0.50 (v1) ]
SSTable 2: [ "apple": $1.20 (v2),  "cherry": $2.00 (v1) ]
SSTable 3: [ "banana": TOMBSTONE,  "date":   $3.00 (v1) ]
                         │
                         ▼ Multi-way Merge Sort
Output SST: [ "apple": $1.20 (v2),  "cherry": $2.00 (v1),  "date": $3.00 (v1) ]
(Discarded old "apple" v1 and purged deleted "banana")

Production engines primarily use two compaction strategies:

1. Size-Tiered Compaction Strategy (STCS)

Common in Cassandra and ScyllaDB for append-only workloads.

When $N$ SSTables of similar size accumulate in a tier, the engine merges them into a single larger SSTable in the next tier.
Pros: Fast compaction with low CPU and write overhead.
Cons: High Space Amplification. Merging huge files requires up to 50% free disk space as temporary headroom.

2. Leveled Compaction Strategy (LCS)

Default in RocksDB, LevelDB, and TiKV.

Disk is split into levels ($L_0, L_1, L_2, \dots, L_k$), where each level is typically 10x larger than the previous level (e.g., $L_1 = 10\text{MB}, L_2 = 100\text{MB}, L_3 = 1\text{GB}, L_4 = 10\text{GB}$).
Within $L_1$ and above, key ranges are strictly partitioned across files so no two SSTables share overlapping keys.
When $L_1$ exceeds its capacity, an $L_1$ file is merged with all overlapping files in $L_2$.
Pros: Minimal space amplification (typically $< 1.1\text{x}$) and predictable read latencies.
Cons: High write amplification because data is rewritten across multiple levels as it ages.

The RUM Trade-Off: LSM-Trees vs B-Trees

In storage engine design, the RUM Conjecture states that you cannot optimize all three metrics simultaneously:

Read Amplification (RA): Number of bytes read from disk per logical byte requested.
Write Amplification (WA): Number of bytes written to disk per logical byte inserted.
Space Amplification (SA): Ratio of physical disk space used vs logical uncompressed data.

Metric                 B-Tree (InnoDB, Postgres)    LSM-Tree (RocksDB, Cassandra)
────────────────────────────────────────────────────────────────────────────────
Write Ingestion        Random I/O (Bottleneck)      Sequential Append (Fast)
Write Amplification    Very High (50x - 100x+)      Moderate to High (10x - 30x)
Point Read Latency     Predictable (1-3 page reads) Depends on Bloom filter / cache
Range Scan Speed       Fast (Traverse leaf links)   Requires Multi-Way Heap Merge
Space Overhead         High (Page internal fragmentation) Low (Dense sequential packing)
NAND Flash Wear        High (Random block rewrites) Low (Large sequential streams)

Practical Architectural Takeaways

Understanding the internal mechanics of LSM-Trees makes choosing and tuning databases straightforward:

Pick B-Trees (PostgreSQL, MySQL, SQLite) when your workload is read-dominant ($>80\%$ reads), requires complex SQL queries with arbitrary secondary indexes, or demands low-latency random point lookups without background compaction jitter.
Pick LSM-Trees (RocksDB, Cassandra, ClickHouse, TiKV) when your workload is write-intensive, deals with time-series or event ingestion, requires maximum storage compression density, or runs on distributed architectures where sequential appends simplify replication logs.
Beware Tombstone Bloat: If you run bulk delete operations on an LSM engine (like Cassandra or RocksDB), point reads scanning those key ranges will experience sudden latency spikes until compaction merges the tombstones away.
Tune MemTable Buffers: In high-throughput ingest services, increasing write_buffer_size and the number of background flush threads prevents write stalls when ingestion outpaces the disk flush rate.

By turning random in-place updates into structured sequential streams, LSM-Trees provide the high-throughput backbone that powers modern distributed infrastructure.

How SQLite WAL Mode Actually Works: The 3 Files, Shared Memory, and Lock-Free Reads

Syed Anzar — Tue, 06 Oct 2026 12:35:17 +0000

Every developer knows SQLite's default pitch: it is a lightweight, zero-configuration, single-file database engine embedded directly inside your application process.

For years, developers also repeated a persistent criticism: SQLite cannot handle concurrent access because any write locks the entire database.

If you use SQLite in its default configuration, that criticism is accurate. Under the legacy rollback journal mode, writing a single row acquires an exclusive lock on the database file, blocking every concurrent reader and writer until the transaction commits.

Enable Write-Ahead Logging (PRAGMA journal_mode = WAL;), and that locking behavior changes completely. Readers no longer block writers. Writers no longer block readers. A high-throughput web server can process thousands of concurrent read queries while a background worker continuously appends new records.

This concurrency does not happen through background magic. It relies on a coordinated three-file architecture, an in-memory hash table index, and snapshot isolation tracked through raw byte offsets.

Here is what actually happens under the hood when SQLite runs in WAL mode.

+-----------------------------------------------------------------------+
|                         SQLITE 3-FILE ECOSYSTEM                       |
|                                                                       |
|   +--------------------+  +--------------------+  +---------------+   |
|   |    database.db     |  |   database.db-wal  |  |database.db-shm|   |
|   |                    |  |                    |  |               |   |
|   | Base B-Tree pages  |  | Append-only log of |  | Shared memory |   |
|   | (Quiescent during  |  | newly written      |  | index (mmap)  |   |
|   | active writes)     |  | page frames        |  | Hash tables   |   |
|   +--------------------+  +--------------------+  +---------------+   |
|             ^                       ^                     ^           |
|             |                       |                     |           |
|      Base Page Reads         Delta Page Reads       Frame Lookup &    |
|      (Unmodified Pages)     (Committed Updates)     Reader Locks      |
+-----------------------------------------------------------------------+

1. The Flaw in the Rollback Journal

To understand why WAL mode exists, you have to look at the mechanism it replaced: the rollback journal.

In rollback journal mode (journal_mode = DELETE), SQLite achieves atomicity by writing the original, unmodified pages to a separate journal file before overwriting them in the main .db file.

ROLLBACK JOURNAL TRANSACTION LIFECYCLE:
1. Acquire EXCLUSIVE lock on database.db (blocks all readers).
2. Read original Page 42 from database.db.
3. Write original Page 42 to database.db-journal.
4. Overwrite Page 42 in database.db with new data.
5. Commit: Delete or truncate database.db-journal.
6. Release lock.

If the system crashes during step 4, the database on disk is corrupt. When SQLite reopens the file, it reads database.db-journal, copies the original pages back into database.db, and restores consistency.

This design has two major penalties:

Concurrency bottleneck: Writing requires modifying the main database file in-place. Readers cannot read from database.db while a write is underway without seeing torn or uncommitted pages.
Double write penalty: Every updated page is written to disk twice: once to the journal file and once to the main database file, with synchronous disk flushes (fsync) between steps.

WAL mode reverses this flow entirely.

2. The 3-File Architecture: `.db`, `.db-wal`, and `.db-shm`

When you switch a database to WAL mode, SQLite introduces two companion files in the same directory:

$ ls -l
-rw-r--r--  1 anzar anzar  409600 Oct  6 18:00 app.db
-rw-r--r--  1 anzar anzar   32768 Oct  6 18:00 app.db-shm
-rw-r--r--  1 anzar anzar  131584 Oct  6 18:00 app.db-wal

Each file serves a dedicated purpose:

`app.db` (The Main Database File)

Contains the base database state organized as standard B-Tree pages (typically 4096 bytes each). In WAL mode, this file is never modified during an active write transaction. It is only updated during a separate process called checkpointing.

`app.db-wal` (The Write-Ahead Log)

An append-only file containing the revised versions of modified database pages. When a transaction commits, new pages are written sequentially to the end of the WAL file. The main .db file remains completely untouched.

`app.db-shm` (The Shared Memory Index)

A volatile, memory-mapped index (mmap) that maps database page numbers to their corresponding frame offsets in the .db-wal file. Without this file, readers would have to scan the entire WAL file sequentially on every query.

+-------------------------------------------------------------------------+
|                  LOGICAL VS PHYSICAL TRANSACTION FLOW                   |
|                                                                         |
|  [WRITE TRANSACTION]                                                    |
|         │                                                               |
|         ├─► 1. Append Page 42 & Page 88 to app.db-wal                   |
|         ├─► 2. Update hash table in app.db-shm (Page 42 -> Frame 104)   |
|         └─► 3. Flush WAL to disk (fsync). app.db remains untouched.     |
|                                                                         |
|  [READ TRANSACTION]                                                     |
|         │                                                               |
|         ├─► 1. Read mxFrame snapshot boundary from app.db-shm           |
|         ├─► 2. Check hash table in app.db-shm for Page 42               |
|         ├─► 3. If found in WAL (Frame 104 <= mxFrame): Read from WAL   |
|         └─► 4. If NOT in WAL: Read base Page 42 from app.db             |
+-------------------------------------------------------------------------+

3. Anatomy of the WAL File: Headers and Frames

The .db-wal file starts with a 32-byte header followed by zero or more sequential frames. Each frame encapsulates exactly one modified database page.

The 32-Byte WAL Header

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Magic Number (0x377f0682 or 0x377f0683)                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       File Format Version (Currently 3007000)                 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Database Page Size (e.g. 4096 bytes)                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Checkpoint Sequence Number                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Salt-1 (Random 32-bit integer generated per reset)      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Salt-2 (Random 32-bit integer incremented per reset)    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Checksum-1 (Cumulative 32-bit checksum of header)       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Checksum-2 (Cumulative 32-bit checksum of header)       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Magic Number: Identifies WAL format and the endianness used for checksum calculation (0x377f0682 for big-endian checksums, 0x377f0683 for little-endian).
Page Size: Stored so the WAL parser knows the exact byte length of every trailing frame without querying the main database header.
Checkpoint Sequence Number: Increments each time the WAL file is checkpointed and restarted.
Salt values: Prevent stale frames from previous WAL iterations from being mistaken for valid transactions after a checkpoint reset.

The 24-Byte Frame Header and Payload

Every frame in the WAL file consists of a 24-byte frame header immediately followed by pageSize bytes of raw page data:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Page Number (Big-endian 32-bit integer)                 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Size of DB in Pages (Non-zero ONLY on commit frame)     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Salt-1 (Must match Salt-1 from WAL header)              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Salt-2 (Must match Salt-2 from WAL header)              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Checksum-1 (Rolling checksum including this frame)      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Checksum-2 (Rolling checksum including this frame)      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                   PAGE DATA (e.g. 4096 bytes)                 |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Notice the second field: Size of DB in Pages.

When a multi-page transaction writes 5 modified pages to the WAL, the first 4 frames have this field set to 0. The 5th frame (the commit frame) contains the total page count of the database.

If power fails while writing frame 3, the database engine ignores frames 1 through 3 on recovery because it never encounters a valid commit marker with matching checksums. Atomicity is guaranteed by appending a single integer to the last frame.

4. The Shared Memory Index (`.db-shm`): Why Readers Don't Scan the Log

If a WAL file contains 10,000 frames, how does a reader looking for Page 42 know which frame holds the newest version without scanning all 10,000 frames from disk?

That is the job of database.db-shm.

+--------------------------------------------------------------------+
|                    WAL-INDEX (.db-shm) ARCHITECTURE                |
|                                                                    |
|  +--------------------------------------------------------------+  |
|  | 136-Byte WAL-Index Header                                    |  |
|  | - mxFrame: 840 (Highest committed frame in WAL)              |  |
|  | - readMarks[8]: [120, 450, 840, 0xFFFFFFFF, ...]             |  |
|  | - Checksums & Salting metadata                               |  |
|  +--------------------------------------------------------------+  |
|  | Hash Table Block 0 (Frames 1 to 4062)                        |  |
|  |   [Page Number Index -> Frame Number Mapping]                |  |
|  +--------------------------------------------------------------+  |
|  | Hash Table Block 1 (Frames 4063 to 8158)                      |  |
|  +--------------------------------------------------------------+  |
+--------------------------------------------------------------------+

The WAL index file is structured into 32KB memory blocks:

The 136-Byte Header: Contains two identical copies of the index metadata (for atomic lock-free reads using memory barriers), the current mxFrame counter, and an array of 8 readMark slots.
Hash Tables: Each 32KB block indexes up to 4,062 frames using open-address linear probing.

Crucial Architectural Properties of `.db-shm`:

Volatile and Transient: The .db-shm file contains zero persistent database data. If it is deleted or the machine crashes, SQLite reconstructs it automatically by reading database.db-wal upon the next connection.
Native CPU Endianness: Unlike .db and .db-wal (which are strictly big-endian on disk for cross-platform portability), the .db-shm file is formatted in the host CPU's native byte order. This allows zero-cost dereferencing without endianness translation instructions.
Shared via OS Memory Mapping: All connections within the same OS access .db-shm using mmap(). Atomic CAS (Compare-And-Swap) operations and POSIX shared-memory advisory locks synchronize reader registration without system call overhead.

5. How Snapshot Isolation Works: Step-by-Step

Let us trace what happens when Reader A and Writer B interact simultaneously.

TIMELINE: CONCURRENT READ & WRITE IN WAL MODE

T1: [Reader A starts transaction]
    └─► Reads mxFrame = 100 from .db-shm.
    └─► Sets its readMark = 100 in .db-shm.
    └─► Snapshot boundary is now locked at Frame 100.

T2: [Writer B modifies Page 5 and commits]
    └─► Appends Page 5 as Frame 101 to .db-wal.
    └─► Updates hash table in .db-shm (Page 5 -> Frame 101).
    └─► Updates mxFrame in .db-shm to 101.

T3: [Reader A reads Page 5]
    └─► Looks up Page 5 in .db-shm hash table.
    └─► Finds Frame 101, but Reader A's max frame is 100 (101 > 100).
    └─► Reader A ignores Frame 101 and reads original Page 5 from app.db!

T4: [Reader C starts new transaction]
    └─► Reads mxFrame = 101 from .db-shm.
    └─► Reads Page 5 -> directly loads Frame 101 from app.db-wal!

The Read Algorithm (Page Resolution)

Whenever SQLite needs to read Page $P$ during a query:

SQLite checks the .db-shm hash table for Page $P$.
It searches for the highest frame number $F$ associated with $P$ such that $F \le \text{mxFrame}_{\text{reader}}$.
If found: SQLite reads Page $P$ directly from app.db-wal at byte offset: $$\text{Offset} = 32 + (F - 1) \times (24 + \text{pageSize}) + 24$$
If not found: SQLite reads Page $P$ from the main app.db file at byte offset: $$\text{Offset} = (P - 1) \times \text{pageSize}$$

Because Reader A ignores all frames numbered greater than 100, Writer B can write frames 101, 102, and 103 without locking or corrupting Reader A's view of the world.

6. Checkpointing: Moving Frames Back to the Main Database

Because writes only append to app.db-wal, the WAL file would grow indefinitely if left unchecked.

Checkpointing is the process of copying committed page frames from app.db-wal back into their corresponding locations in the base app.db file.

+--------------------------------------------------------------------------+
|                          CHECKPOINTING MECHANISM                         |
|                                                                          |
|   app.db-wal (Frames 1..1000)              app.db (Base Pages)           |
|  +---------------------------+            +----------------------------+ |
|  | Frame 1: Page 4  ───────┼───────────► | Offset: (4-1) * 4096       | |
|  | Frame 2: Page 12 ───────┼───────────► | Offset: (12-1) * 4096      | |
|  | Frame 3: Page 4  ───────┼───(Overwrites newest Page 4 to disk)      | |
|  +---------------------------+            +----------------------------+ |
|               │                                                          |
|               └─► Once backfilled past all active reader readMarks:      |
|                   Reset WAL header frame pointer back to 1.              |
+--------------------------------------------------------------------------+

SQLite supports 4 distinct checkpoint modes via sqlite3_wal_checkpoint_v2():

Mode	Behavior	Blocks Writers?	Blocks Readers?
`PASSIVE`	Backfills as many frames as possible up to the oldest active `readMark`. If an active reader is reading an old frame, it stops without waiting. Default mode used by auto-checkpoints.	No	No
`FULL`	Blocks new writers and waits for existing readers to finish, then backfills all frames to the main `.db` file.	Yes	No
`RESTART`	Like `FULL`, but also waits for all readers to clear so it can reset the WAL index to frame 1. Subsequent writes overwrite the WAL file from the beginning.	Yes	Yes (briefly)
`TRUNCATE`	Like `RESTART`, but additionally truncates the `app.db-wal` file on disk to 0 bytes.	Yes	Yes (briefly)

By default, SQLite triggers an automatic PASSIVE checkpoint whenever the WAL file reaches 1,000 frames (approx. 4MB with 4KB pages).

7. The Three Hidden Traps of SQLite WAL in Production

While WAL mode transforms SQLite into a high-performance concurrent engine, it introduces three operational edge cases that catch developers off guard.

Trap 1: The 10GB WAL Bloat (Checkpoint Starvation)

This is the most common SQLite production failure.

Because PASSIVE checkpointing cannot overwrite frames that are older than the oldest active reader's readMark, a single long-running read query or unclosed connection will stall all checkpoints.

[Active Long Reader]   ──► Holding readMark at Frame 50
[Incoming Writes]      ──► Append Frames 51 through 50,000 to .db-wal
[Auto-Checkpoint]      ──► Tries to run at Frame 1,000...
                           STOPS at Frame 50 because Reader is still active!
                           Result: .db-wal balloons to 500MB, 2GB, 10GB.

As the WAL file grows into gigabytes, every new read query suffers degraded cache locality and slower index traversals.

The Fix:

Keep read transactions short.
Set a busy timeout (busy_timeout = 5000;).
Monitor WAL size and periodically run explicit checkpoints:

import sqlite3

conn = sqlite3.connect("app.db")
# Run a PASSIVE or FULL checkpoint and check un-backfilled frame counts
# Returns (busy_status, log_frames, checkpointed_frames)
busy, log, ckpt = conn.execute("PRAGMA wal_checkpoint(PASSIVE);").fetchone()
if log - ckpt > 1000:
    print(f"Warning: {log - ckpt} uncheckpointed frames stalled by active readers!")

Trap 2: Network Filesystems (NFS / SMB / EBS Multi-Attach)

SQLite WAL mode does not work over network filesystems like NFS, SMB, or GlusterFS.

The .db-shm file relies on shared memory semantics (mmap memory synchronization and POSIX advisory locking within the kernel). Network filesystems do not support unified shared memory across separate client instances.

Attempting to run WAL mode on an NFS mount results in instant locking failures (SQLITE_IOERR_SHMOPEN) or silent data corruption.

Trap 3: Incomplete File Backups

In rollback journal mode, backing up database.db with a simple file copy utility (cp or rsync) while the database is idle yields a valid database.

In WAL mode, copying database.db alone leaves the newest committed transactions behind in database.db-wal. If you restore database.db without its companion .db-wal and .db-shm files, you restore an outdated snapshot.

The Fix: Never use filesystem file copy on an active WAL database. Always use the SQLite Online Backup API:

sqlite3 app.db ".backup 'backup.db'"

Summary Mental Model

Feature	Rollback Journal (`DELETE`)	Write-Ahead Log (`WAL`)
Write Strategy	Overwrite main `.db` in-place after journal copy	Append new frames to `.db-wal`
Readers vs Writers	Writers block readers; Readers block writers	Readers never block writers; Writers never block readers
Commit Overhead	2 disk writes + multiple fsyncs per commit	1 append write + 1 fsync per commit
Companion Files	Temporary `app.db-journal` during writes	Persistent `app.db-wal` and `app.db-shm`
Network FS Support	Supported with network locks	Unsupported (requires shared OS memory)
Concurrency Ceiling	1 active operation (Read OR Write)	N concurrent Readers + 1 serialized Writer

By understanding the division of labor between app.db, app.db-wal, and app.db-shm, you can comfortably run SQLite at thousands of queries per second without mysterious lock timeouts or runaway log growth.

How eBPF Actually Runs Inside the Linux Kernel: The Verifier, JIT, and BPF Maps

Syed Anzar — Tue, 06 Oct 2026 05:11:02 +0000

How eBPF Actually Runs Inside the Linux Kernel: The Verifier, JIT, and BPF Maps

If you ask most developers how eBPF works, you usually get one of two answers:

"It is a tiny virtual machine inside Linux, like a JVM for the kernel."
"It is a way to run custom C code in the kernel without writing a kernel module."

Both explanations miss the fundamental architecture.

eBPF does not run inside an interpreter loop at runtime, and it definitely does not allow arbitrary C execution. If you could execute arbitrary C in kernel space, a single null pointer dereference or off-by-one loop would panic your entire operating system.

Instead, eBPF is an in-kernel sandboxed execution engine governed by an unforgiving static verifier, compiled to native machine instructions via a Just-In-Time (JIT) compiler, and bridged to user space through lockless, memory-mapped data structures.

Here is the exact mechanical journey of an eBPF program: from user-space bytecode compilation, through the kernel's symbolic execution verifier, down to native CPU execution on kernel hooks.

1. The Virtual CPU: Registers and Calling Convention

Before touching the kernel, your high-level C or Rust code is compiled by LLVM/Clang targeting the bpf backend (clang -target bpf -O2).

The output is not x86 or ARM assembly. It is 64-bit eBPF bytecode designed around an idealized RISC register machine:

+-----------------------------------------------------------------------+
|                       eBPF Register Architecture                      |
+-----------------------------------------------------------------------+
|  Register  | Purpose                                                  |
+------------+----------------------------------------------------------+
|  R0        | Function return value & exit code to kernel hook         |
|  R1 - R5   | Function arguments passed to in-kernel BPF helpers       |
|  R6 - R9   | Callee-saved registers (preserved across helper calls)  |
|  R10       | Read-only frame pointer to 512-byte stack frame          |
+-----------------------------------------------------------------------+

Every eBPF instruction is fixed at 64 bits (8 bytes):

8-bit opcode: Operation type (ALU, memory load/store, branch jump).
4-bit destination register (dst_reg): Target register (0–10).
4-bit source register (src_reg): Source register (0–10).
16-bit offset: Signed offset for stack or memory addressing.
32-bit immediate (imm): Constant integer operand.

 0       7 8    11 12   15 16               31 32                     63
+---------+-------+-------+-------------------+-------------------------+
| Opcode  |  Dst  |  Src  |      Offset       |        Immediate        |
+---------+-------+-------+-------------------+-------------------------+

Unlike user-space programs that have megabytes of stack space, each eBPF program gets exactly 512 bytes of stack pointed to by R10. Attempting to allocate a large struct on the stack will fail before your code ever runs.

2. Loading Bytecode: The `bpf()` Syscall

When a user-space loader (written in Go with cilium/ebpf, Rust with aya, or C with libbpf) wants to load an eBPF program, it invokes the bpf() system call with the BPF_PROG_LOAD command:

union bpf_attr attr = {
    .prog_type = BPF_PROG_TYPE_KPROBE,
    .insns     = (uint64_t)bytecode_buffer,
    .insn_cnt  = instruction_count,
    .license   = (uint64_t)"GPL",
    .log_buf   = (uint64_t)verifier_log_buffer,
    .log_size  = 65536,
    .log_level = 1,
};

int prog_fd = syscall(SYS_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));

The kernel receives this bytecode buffer, but it does not execute it immediately. Instead, it hands the raw instruction stream over to kernel/bpf/verifier.c.

3. The Verifier: Symbolic Execution and Safety Proofs

The verifier is the security heart of eBPF. Its job is mathematically proving that your program cannot crash the kernel, dereference null pointers, read uninitialized memory, or loop infinitely.

The verification process runs in two distinct phases:

[ Bytecode Input ] 
       │
       ▼
┌────────────────────────────────────────┐
│  Phase 1: DAG & CFG Validation         │
│  - Detect unreachable instructions     │
│  - Check for uncontrolled loops / cycles│
└──────────────────┬─────────────────────┘
                   │ Pass
                   ▼
┌────────────────────────────────────────┐
│  Phase 2: Abstract Interpretation      │
│  - Simulate every execution path       │
│  - Track register states (R0-R10)      │
│  - Validate pointer types and offsets  │
│  - Enforce bounds & NULL checks        │
└──────────────────┬─────────────────────┘
                   │ Pass
                   ▼
[ JIT Compiler -> Native Machine Code ]

Phase 1: Control Flow Graph (CFG) Validation

The verifier parses the program into a Directed Acyclic Graph (DAG). It ensures:

The program has a clean entry point at instruction 0 and ends on a valid BPF_EXIT_INSN.
There is no unreachable dead code.
Loops are strictly bounded. Historically, all loops were forbidden. Modern kernels allow bounded loops, but the verifier must prove that the loop terminates within a fixed instruction budget (up to 1,000,000 processed instructions during simulation).

Phase 2: Abstract Interpretation (Register State Tracking)

Next, the verifier descends through every possible execution branch, simulating CPU execution instruction by instruction.

For every step, the verifier maintains a struct bpf_reg_state for all 11 registers. A register is never just a raw number; the kernel assigns it a strict type:

NOT_INIT: Register has not been written to yet. Reading it is an immediate failure.
SCALAR_VALUE: An integer whose possible minimum and maximum values are tracked via tnum (tristate numbers tracking known 0s, known 1s, and unknown bits).
PTR_TO_CTX: Pointer to the hook's context struct (for example, struct xdp_md or struct pt_regs).
PTR_TO_MAP_VALUE_OR_NULL: Pointer returned by a map lookup that might be valid or might be 0 (NULL).
PTR_TO_MAP_VALUE: A verified, non-null pointer to map memory.
PTR_TO_STACK: A pointer to the local 512-byte stack frame.

Why the Verifier Rejects Unchecked Pointers

Look at this common bug in C:

struct packet_stat *stat = bpf_map_lookup_elem(&stats_map, &key);
stat->packets += 1; // Crash if key does not exist!

When compiled to eBPF bytecode and evaluated:

bpf_map_lookup_elem() executes. The verifier marks R0 with the type PTR_TO_MAP_VALUE_OR_NULL.
The next instruction attempts a memory store: *(u64 *)(R0 + 0) += 1.
The verifier checks the type of R0. Because R0 is still PTR_TO_MAP_VALUE_OR_NULL (and not PTR_TO_MAP_VALUE), the verifier aborts with:

   R0 invalid mem access 'map_value_or_null'

To pass verification, you must write a conditional branch:

struct packet_stat *stat = bpf_map_lookup_elem(&stats_map, &key);
if (!stat) {
    return 0; // Branch A: R0 is NULL, exit safely
}
// Branch B: Verifier updates R0 type to PTR_TO_MAP_VALUE
stat->packets += 1; // Safe!

When the verifier evaluates the conditional jump if R0 == 0, it branches its simulation state:

On the true path: R0 is known to be 0.
On the false path: R0 is promoted to PTR_TO_MAP_VALUE with known valid memory boundaries. Only here is dereferencing permitted.

4. JIT Compilation: From Bytecode to Native Machine Instructions

Once the verifier approves the bytecode, interpreting it instruction-by-instruction on every packet or syscall would introduce unacceptable CPU overhead.

The kernel runs the verified bytecode through an architecture-specific Just-In-Time (JIT) compiler (arch/x86/net/bpf_jit_comp.c on x86-64):

+--------------------+      eBPF JIT      +--------------------+
| eBPF Bytecode      | ─────────────────> | Native x86-64      |
| r1 = *(u64*)(r1+0) |                    | mov 0x0(%rdi),%rdi |
| r0 = 0             |                    | xor %eax,%eax      |
| exit               |                    | ret                |
+--------------------+                    +--------------------+

The JIT compiler maps eBPF virtual registers directly to physical hardware registers:

R0 -> %rax
R1 -> %rdi
R2 -> %rsi
R3 -> %rdx
R10 -> %rbp (stack frame pointer)

Once compiled into machine code:

The memory page containing the generated instructions is allocated in kernel space.
The kernel marks the page as read-only and executable (PAGE_KERNEL_ROX).
Memory write permissions are permanently stripped from the page to prevent any privilege escalation or code-patching attacks.

5. Hook Attachment and Invocation

The compiled eBPF program exists in the kernel as an anonymous file descriptor (prog_fd). To run, it must attach to a kernel hook point.

                                  Linux Kernel Space
 ┌────────────────────────────────────────────────────────────────────────┐
 │                                                                        │
 │  Network Device Driver ───> [ XDP Hook ] ───> Native eBPF Machine Code │
 │                                                     │                  │
 │  Syscall Entry (e.g. execve) ─> [ Tracepoint ] ─────┤                  │
 │                                                     │                  │
 │  Kernel Function ─────────> [ Kprobe / Fentry ] ────┘                  │
 │                                                                        │
 └────────────────────────────────────────────────────────────────────────┘

Common hook attachment targets include:

XDP (eXpress Data Path): Runs inside the network network interface card (NIC) driver before the Linux network stack even allocates an sk_buff.
Tracepoints: Static trace locations defined in kernel source code (for example, sys_enter_execve).
Kprobes / Kretprobes: Dynamic insertion of breakpoints at arbitrary kernel function entries and returns.
LSM (Linux Security Module): Security hooks capable of blocking unauthorized file, process, or network operations before they execute.

When the hook triggers (for example, a packet arrives at the NIC):

The kernel prepares a context pointer (ctx) containing packet data or CPU register states.
The kernel places this pointer into register R1 (%rdi).
It performs a direct hardware call instruction (callq) to the JIT-compiled function address.
The eBPF function executes at full bare-metal CPU speed.
The return code left in R0 (%rax) tells the kernel what to do next: pass the packet (XDP_PASS), drop it (XDP_DROP), or redirect it (XDP_TX).

6. Zero-Overhead Communication: BPF Maps and Ring Buffers

eBPF programs cannot call printf(), write directly to disk files, or open arbitrary TCP connections. So how do they communicate telemetry and state to user-space applications?

They use BPF Maps: kernel-managed, lockless memory structures shared between kernel and user space.

┌────────────────────────────────────────────────────────┐
│                   User Space Application               │
│               (Go / Rust / C Monitoring Daemon)        │
└───────────────────────────▲────────────────────────────┘
                            │ mmap() / read()
                            │
┌───────────────────────────▼────────────────────────────┐
│                    BPF Ring Buffer                     │
│    [Header Page] [Data Memory Page 1] [Data Page 2]    │
└───────────────────────────▲────────────────────────────┘
                            │ bpf_ringbuf_submit()
                            │
┌───────────────────────────┴────────────────────────────┐
│                   eBPF Kernel Program                  │
│                (Attached to tracepoint)                │
└────────────────────────────────────────────────────────┘

The Old Approach: Perf Event Arrays

Historically, eBPF used BPF_MAP_TYPE_PERF_EVENT_ARRAY. This allocated a separate ring buffer for every individual CPU core.

The Problem: Memory had to be over-provisioned across all cores to prevent drops on busy cores, while idle cores wasted RAM. If one core experienced a sudden spike, events were dropped even if total memory was mostly free.

The Modern Standard: `BPF_MAP_TYPE_RINGBUF`

Introduced in Linux 5.8, the BPF Ring Buffer provides a single, lockless, multi-producer single-consumer queue shared across all CPU cores:

Kernel Side (Reservation and Submission):

   struct event *e = bpf_ringbuf_reserve(&events, sizeof(*e), 0);
   if (!e) {
       return 0; // Drop if buffer is saturated
   }
   e->pid = bpf_get_current_pid_tgid() >> 32;
   bpf_get_current_comm(&e->comm, sizeof(e->comm));
   bpf_ringbuf_submit(e, 0);

User Space Side (Zero-Copy Polling): The user-space daemon calls mmap() on the ring buffer file descriptor. It monitors the buffer via epoll() or a polling loop without issuing costly read() system calls for individual events.

This architecture enables millions of kernel events per second to stream into user space with negligible CPU overhead and zero memory copies.

7. The Mental Model: eBPF in Summary

To build an accurate mental model of eBPF:

Dimension	Loadable Kernel Module (LKM)	Traditional User-Space Agent	eBPF Program
Execution Location	Kernel space	User space	Kernel space
Safety Guarantee	None (Bug = Kernel Panic)	High (OS sandbox)	Absolute (Static verifier proof)
Execution Speed	Native CPU	Context-switch overhead	Native JIT-compiled CPU
Observability Depth	Complete access	Limited by syscalls	Raw tracepoints, XDP, and kprobes
Deployment Risk	Requires kernel recompilation/reboot	Easy to restart	Dynamic loading via `bpf()` syscall

eBPF is not a virtual machine running on top of Linux. It is a compiler-verified, JIT-accelerated extension pipeline that allows you to safely inject programmable logic directly into the Linux kernel runtime.

How Structured Outputs Actually Work: Grammar-Constrained Decoding and Logit Masking Under the Hood

Syed Anzar — Mon, 05 Oct 2026 15:33:43 +0000

When OpenAI launched response_format={"type": "json_schema", "strict": true} and open-source inference engines like vLLM, SGLang, and llama.cpp introduced grammar-constrained decoding, developer workflows changed overnight.

Before this, getting an LLM to reliably return valid JSON required prayers, complex system prompts ("You are a JSON generator. Do NOT include markdown code blocks"), and brittle retry loops wrapped around json.loads(). Even with fine-tuned models, a rogue comma or unescaped quote would inevitably crash downstream production pipelines.

Today, structured outputs are guaranteed to be 100% syntactically valid according to your exact JSON schema.

Most developers assume one of two things is happening behind the scenes:

The model was fine-tuned specifically to follow JSON schemas.
The API server runs a hidden while loop, catching syntax errors and asking the model to fix its mistakes.

Both assumptions are completely wrong.

In reality, the model never gets the chance to make a syntax error. The inference engine physically alters the model's output probabilities at every single token generation step.

Here is the exact systems mechanics of how grammar-constrained decoding and logit masking work under the hood.

1. The Normal Autoregressive Decoding Loop

To understand grammar constraints, we first need to look at how an LLM produces a single token during unconstrained text generation.

At decoding step $t$, the transformer processes the input context and KV cache, outputting a vector of unnormalized raw scores called logits across its entire vocabulary $V$:

Logits vector z: [z_1, z_2, z_3, ..., z_|V|]
Vocabulary size |V|: ~128,000 tokens (for Llama 3 / GPT-4)

In standard greedy or temperature-based sampling, these logits are passed through a Softmax function to convert them into a probability distribution:

$$P(w_i) = \frac{e^{z_i / T}}{\sum_{j=1}^{|V|} e^{z_j / T}}$$

The sampler draws a token $w_t$ based on these probabilities.

In unconstrained decoding, every token in the vocabulary has a non-zero probability. Even if there is only a 0.0001% chance of sampling a closing brace } right after a key name "username":, over billions of generated tokens, that failure will happen thousands of times in production.

2. Step 1: Compiling JSON Schema into a Formal Grammar State Machine

When you submit a JSON Schema or Pydantic model to an inference engine (such as vLLM's xgrammar, SGLang's outlines, or llama.cpp's GBNF engine), the engine does not feed the schema to the model weights. Instead, it compiles the schema into a formal grammar state machine on the host CPU or GPU.

[ JSON Schema / Pydantic Model ]
               │
               ▼
   [ Schema Compiler Engine ]
               │
               ▼
[ Pushdown Automaton (PDA) / DFA ]
  - States: Start, InKey, ColonExpected, InValue, CommaOrClose, etc.
  - Stack: Tracks nested object '{' and array '[' depth.

JSON is a Context-Free Grammar (CFG) because it supports arbitrarily nested arrays and objects ({"a": {"b": [1, 2]}}). A standard Deterministic Finite Automaton (DFA) cannot track arbitrary nesting depth because it has finite memory. Therefore, the engine compiles the schema into a Pushdown Automaton (PDA): a finite state machine equipped with a stack.

Let us trace a simple schema requiring an object with a string name and an integer age:

State 0 (Start): Only valid character is {.
State 1 (Expect Key): Only valid character sequence is "name".
State 2 (Expect Colon): Only valid character sequence is :.
State 3 (Expect String Value): Valid characters are ", followed by any valid JSON string characters, terminated by ".
State 4 (Expect Delimiter): Only valid character is ,.
State 5 (Expect Next Key): Only valid character sequence is "age".
State 6 (Expect Colon): Only valid character sequence is :.
State 7 (Expect Integer): Only valid characters are digits 0-9.
State 8 (Expect Close): Only valid character is }.
State 9 (End): Only valid token is the End-of-Sequence token (<|endoftext|>).

At every character in the output, the PDA knows precisely which next characters are legally allowed.

3. Step 2: The Tokenizer Vocabulary Problem

Here is the central challenge that makes grammar-constrained decoding difficult: Grammars operate on characters, but LLMs operate on tokens.

Modern tokenizers (like Byte-Pair Encoding / BPE) group multi-character sequences into single token IDs. In Llama 3's 128k vocabulary:

Token 1234 might represent "hello"
Token 5678 might represent ": true,"
Token 9012 might represent " 42 "
Token 3456 might represent ": {"

If the grammar is currently in State 2 (expecting a colon : followed by a space and a boolean), which of the 128,000 token IDs in the vocabulary are allowed?

To solve this without re-evaluating 128,000 strings on every step, inference engines pre-build a Vocabulary Prefix Trie.

                [Root]
               /      \
             """     "{"
             /   \      \
          "age"  "name"  ""user""
           /        \
       "": "      "": "

The Vocabulary Trie indexes every token in the model's vocabulary byte-by-byte.

When the grammar is at state $S_t$, the engine traverses the Trie against the current state of the Pushdown Automaton. A token ID is marked valid if and only if every character in the token's byte string represents a valid path in the grammar state machine.

4. Step 3: Runtime Logit Masking (The Mathematical Filter)

Once the engine determines the subset of valid tokens $V_{\text{valid}} \subseteq V$ for the current state $S_t$, it constructs a Logit Mask Vector $M \in \mathbb{R}^{|V|}$:

$$M_i = \begin{cases} 0 & \text{if } i \in V_{\text{valid}} \ -\infty & \text{if } i \notin V_{\text{valid}} \end{cases}$$

This mask is added directly to the raw logits vector $z$ output by the transformer forward pass before Softmax is computed:

$$\tilde{z} = z + M$$

$$\tilde{z}i = \begin{cases} z_i & \text{if } i \in V{\text{valid}} \ -\infty & \text{if } i \notin V_{\text{valid}} \end{cases}$$

Now, let us observe what happens when we calculate the Softmax probability for an invalid token $k \notin V_{\text{valid}}$:

$$P(w_k) = \frac{e^{\tilde{z}k}}{\sum{j=1}^{|V|} e^{\tilde{z}j}} = \frac{e^{-\infty}}{\sum{j=1}^{|V|} e^{\tilde{z}j}} = \frac{0}{\sum{j=1}^{|V|} e^{\tilde{z}_j}} = 0$$

Because $e^{-\infty} = 0$, the probability of every invalid token becomes mathematically zero.

When the sampler selects the next token, it is physically impossible to choose anything that violates the JSON schema. The model's learned knowledge and attention weights decide which valid token to pick, but the grammar defines the sandbox.

[ Transformer Forward Pass ] ──► Raw Logits: [ 4.2,  1.1,  8.7,  -0.5, ... ] (128k items)
                                                    │
[ Grammar State + Vocab Trie ] ─► Mask Vector: [ 0.0, -inf,  0.0,  -inf, ... ]
                                                    │
                                                    ▼
                                Masked Logits: [ 4.2, -inf,  8.7,  -inf, ... ]
                                                    │
                                                    ▼
                                           [ Softmax Sampling ]
                                                    │
                                                    ▼
                                         Guaranteed Valid Token

5. Step 4: Deterministic Jump Decoding (Token Fast-Forwarding)

Consider what happens when the model generates the key "is_admin".

According to our schema, the key name is fixed. The colon : is fixed. If the field is a boolean, the only allowed tokens are true or false.

Why execute heavy matrix multiplications across 70 billion parameters on an expensive GPU just to predict the characters ": " or the closing quote of a known key?

Modern constrained decoding engines implement Jump Decoding (also called Token Infill or Speculative Schema Fast-Forwarding):

At state $S_t$, the engine evaluates the set of valid next tokens $V_{\text{valid}}$.
If $|V_{\text{valid}}| = 1$ (there is exactly one legal token), or if the schema specifies a literal string constant, the engine skips the transformer forward pass completely.
It directly appends the known token to the output sequence, updates the KV cache, advances the grammar state machine, and continues to the next decision point.

Output: { "status": "active" }
          ▲       ▲▲        ▲▲
          │       ││        ││
Forward Pass?   NO (Fixed)  NO (Schema Key)  YES (Value Choice)  NO (Closing)

In structured extraction tasks where 40% to 60% of the output tokens are predictable schema scaffolding (keys, brackets, whitespace, punctuation), jump decoding can increase overall generation throughput by 2x to 3x compared to unconstrained decoding.

6. The Engineering Bottleneck: Masking Latency vs GPU Throughput

While logit masking sounds simple in theory, naive implementations create severe inference bottlenecks.

Consider high-throughput serving:

A batch of 64 requests generating tokens on an NVIDIA H100.
Vocabulary size: 128,000 tokens.
Each decode step takes ~8ms on GPU.
If evaluating the PDA and updating 128,000 logits in Python on the CPU takes 10ms per step, the GPU spends more time waiting for the CPU mask than doing tensor arithmetic!

How Modern Engines Solve This (vLLM xgrammar & SGLang):

Pre-allocated Bitset Lookup Tables: Rather than computing masks on the fly, static states (such as keywords, boolean branches, and punctuation) are precompiled into bitsets where each bit corresponds to a token ID in $V$.
Custom CUDA Logit-Masking Kernels: The bitset is copied to GPU memory once. A dedicated CUDA/Triton kernel applies the $-\infty$ mask in parallel across all 128k logits in less than 50 microseconds (0.05ms).
Adaptive Token Trie Pruning: High-frequency prefixes are cached in L1/L2 CPU cache, minimizing pointer chasing during grammar transitions.

7. Practical Gotchas Developers Must Know

Even though structured outputs guarantee syntax validity, they introduce real engineering trade-offs:

1. Model Distribution Distortion

When you force an LLM to follow a strict schema, you are truncating its natural probability distribution. If your schema forces the model to output a specific field order that conflicts with how it reasons (for example, asking for "final_answer" before "explanation"), the model cannot perform step-by-step reasoning. Always put reasoning or thought fields before categorical conclusions in your schemas.

2. The Unbounded String Trap

A schema with {"type": "string"} allows any sequence of characters inside quotes. The grammar engine will ensure the string opens and closes with ", but it cannot prevent the model from generating 4,000 tokens of repetitive text inside that string. Always use length constraints, enums, or regex patterns if you need bounded string outputs.

3. Schema Compilation Overhead

Compiling complex nested schemas with hundreds of union types (anyOf, oneOf) into a Pushdown Automaton can take 50ms to 500ms on the first request. Production systems solve this by precompiling and warming schema state machines at server startup rather than compiling per request.

Summary: The 4-Step Mental Model

Whenever you use Structured Outputs in production, remember what is really happening:

Schema to PDA: Your JSON schema is compiled into a Pushdown Automaton state machine with an explicit stack for tracking object/array nesting.
Vocab Trie Traversal: The tokenizer's vocabulary is matched against the automaton to find the exact subset of valid token IDs.
Logit Masking: Invalid token positions are overwritten with $-\infty$ before Softmax, reducing their sampling probability to exactly 0%.
Jump Decoding: Deterministic schema scaffolding (keys, colons, brackets) bypasses GPU computation entirely and injects directly into the KV cache.

Guaranteed JSON from LLMs is not magic prompt engineering; it is deterministic formal language theory controlling probabilistic token sampling.

What Actually Happens During Speculative Decoding in LLMs

Syed Anzar — Sun, 04 Oct 2026 13:09:36 +0000

What Actually Happens During Speculative Decoding in LLMs

Autoregressive language model generation is notoriously slow. When you run a 70-billion parameter model on an enterprise GPU, you might get 20 to 30 tokens per second.

The intuitive assumption is that the GPU compute cores are sweating under massive matrix multiplications. But if you profile the GPU during single-batch generation, you find the exact opposite: the GPU's compute cores are sitting 95% idle.

The true bottleneck is memory bandwidth. Speculative decoding is an inference optimization that exploits this hardware reality to double or triple token generation speed with zero loss in mathematical output quality.

Here is what actually happens inside the GPU, the transformer layers, and the sampling math during speculative decoding.

1. The Real Bottleneck: Memory Bandwidth vs Arithmetic Intensity

To understand why speculative decoding works, you first have to look at the GPU memory bus.

During autoregressive generation (decoding phase), an LLM generates tokens sequentially: one token per forward pass. To generate a single token for a batch size of 1:

The GPU must load every single weight parameter from High Bandwidth Memory (HBM / VRAM) into the on-chip SRAM / registers.
It performs a vector-matrix multiplication between the single input token embedding and the model weights.
It writes the updated Key-Value (KV) cache entry back to VRAM.

Let us do the concrete math for a 70B parameter model in FP16 running on an Nvidia H100 GPU:

Model size in VRAM: 70 billion parameters * 2 bytes = 140 GB.
H100 Memory Bandwidth: ~3,350 GB/s.
H100 Tensor Core Compute: ~1,979 TFLOPs (FP16).

Time spent streaming weights:

$$\text{Time}_{\text{memory}} = \frac{140\text{ GB}}{3,350\text{ GB/s}} \approx 41.8\text{ ms}$$

Time spent computing math:

Generating 1 token requires roughly $2 \times 70 \times 10^9 = 1.4 \times 10^{11}$ FLOPs.
$$\text{Time}_{\text{compute}} = \frac{1.4 \times 10^{11}\text{ FLOPs}}{1,979 \times 10^{12}\text{ FLOPs/s}} \approx 0.07\text{ ms}$$

The ratio is brutal: the GPU spends 41.8 ms loading weights from memory and only 0.07 ms doing arithmetic. The arithmetic intensity (FLOPs per byte transferred) is nearly 1, far below the GPU's saturation threshold (which is around 150 FLOPs/byte).

Traditional Autoregressive Decoding (Batch Size = 1):
[ Load 140 GB Weights ] ---> ( Compute 1 Token: 0.07 ms ) ===> Takes 41.8 ms
[ Load 140 GB Weights ] ---> ( Compute 1 Token: 0.07 ms ) ===> Takes 41.8 ms
[ Load 140 GB Weights ] ---> ( Compute 1 Token: 0.07 ms ) ===> Takes 41.8 ms
Result: 3 forward passes = ~125 ms for 3 tokens

2. The Core Insight: Parallel Verification is "Free"

What happens if, instead of 1 token, you feed 5 candidate tokens into the 70B target model simultaneously?

The model still loads the 140 GB weights from VRAM exactly once (41.8 ms). But now the Tensor Cores multiply a $[5 \times d]$ matrix against the weights instead of a $[1 \times d]$ vector.

The compute time rises from 0.07 ms to 0.35 ms, but both numbers are dwarfed by the 41.8 ms memory transfer time.

Evaluating 1 Token:  41.8 ms (memory) + 0.07 ms (compute) = 41.87 ms
Evaluating 5 Tokens: 41.8 ms (memory) + 0.35 ms (compute) = 42.15 ms

Verifying 5 tokens in parallel takes virtually the exact same wall-clock time as generating 1 token.

Speculative decoding exploits this asymmetry by splitting generation into two distinct roles:

A small, lightweight Draft Model guesses $K$ tokens sequentially at high speed.
The heavy Target Model verifies all $K$ tokens simultaneously in one parallel forward pass.

3. The Speculative Decoding Execution Loop

Here is the exact step-by-step pipeline executed on every speculative decoding iteration:

                  +-----------------------------------+
                  |  Prompt / Current Prefix Sequence  |
                  +-----------------+-----------------+
                                    |
                                    v
                  +-----------------------------------+
                  |      Draft Model (e.g. 1B)        |
                  |  Generates K tokens sequentially  |
                  |  Tokens: [x1, x2, x3, x4, x5]     |
                  +-----------------+-----------------+
                                    |
                                    v
                  +-----------------------------------+
                  |      Target Model (e.g. 70B)      |
                  |  Parallel Forward Pass on prefix  |
                  |  + all K speculative tokens       |
                  +-----------------+-----------------+
                                    |
                                    v
                  +-----------------------------------+
                  |    Speculative Rejection Sampler  |
                  |  Accepts x1, x2, x3               |
                  |  Rejects x4                       |
                  |  Samples corrected replacement x4'|
                  |  Discards x5                      |
                  +-----------------+-----------------+
                                    |
                                    v
                  +-----------------------------------+
                  |  Append Accepted Tokens to Prefix |
                  |  Total yield: 4 tokens in 1 step! |
                  +-------------------+---------------+

Step 1: The Draft Phase

A small model (such as a 1B parameter model paired with a 70B target) generates $K$ candidate tokens $(\hat{x}_1, \hat{x}_2, \dots, \hat{x}_K)$ autoregressively.

Because the draft model is tiny (only ~2 GB in FP16), streaming its weights takes under 0.6 ms per token. Generating 5 draft tokens takes roughly $5 \times 0.6\text{ ms} = 3.0\text{ ms}$.

For each generated token, the draft model records its predicted probability distribution $q(x)$.

Step 2: The Target Verification Phase

All $K$ draft tokens are appended to the input sequence and evaluated by the 70B target model in one single forward pass.

Because the attention mask allows each token at position $i$ to attend to all prior tokens, the target model produces the true output probability distributions $p_1(x), p_2(x), \dots, p_K(x)$ for all $K$ positions simultaneously.

Step 3: Speculative Sampling (Rejection & Correction)

We iterate through the draft tokens from $i = 1$ to $K$:

For token $\hat{x}_i$, compare target probability $p(\hat{x}_i)$ against draft probability $q(\hat{x}_i)$.
Draw a uniform random number $r \sim U[0, 1]$.
Acceptance Condition: If $r \le \min\left(1, \frac{p(\hat{x}_i)}{q(\hat{x}_i)}\right)$, accept token $\hat{x}_i$ and advance to $i+1$.
Rejection Condition: If the condition fails at position $j$, reject $\hat{x}j$. Sample a replacement token from the residual distribution: $$p'(x) = \frac{\max(0, p(x) - q(x))}{\sum{y} \max(0, p(y) - q(y))}$$ Immediately discard all subsequent draft tokens $(\hat{x}_{j+1}, \dots, \hat{x}_K)$, and conclude this iteration.
Bonus Token: If all $K$ tokens are accepted, sample one extra $(K+1)$-th token directly from the target model's final logits $p_{K+1}(x)$.

4. The Python Implementation

Here is a clean, dependency-free reference implementation of Leviathan & Chen's Speculative Sampling algorithm:

import numpy as np

def speculative_sample_step(draft_probs_list, target_probs_list, draft_tokens):
    """
    draft_probs_list: list of K numpy arrays, each shape (vocab_size,) representing q(x)
    target_probs_list: list of K+1 numpy arrays, each shape (vocab_size,) representing p(x)
    draft_tokens: list of K integers drafted by the small model

    Returns: list of accepted and sampled tokens
    """
    accepted_tokens = []
    K = len(draft_tokens)

    for i in range(K):
        token = draft_tokens[i]
        q_prob = draft_probs_list[i][token]
        p_prob = target_probs_list[i][token]

        # Calculate acceptance probability
        acceptance_threshold = min(1.0, p_prob / (q_prob + 1e-10))
        r = np.random.uniform(0.0, 1.0)

        if r <= acceptance_threshold:
            # Token accepted
            accepted_tokens.append(token)
        else:
            # Token rejected: sample from modified residual distribution
            residual = np.maximum(0.0, target_probs_list[i] - draft_probs_list[i])
            residual_sum = np.sum(residual)

            if residual_sum > 0:
                p_prime = residual / residual_sum
            else:
                p_prime = target_probs_list[i]

            replacement_token = int(np.random.choice(len(p_prime), p=p_prime))
            accepted_tokens.append(replacement_token)

            # Discard all remaining draft tokens
            return accepted_tokens

    # All K tokens were accepted! Sample bonus (K+1)-th token directly from target
    bonus_token = int(np.random.choice(
        len(target_probs_list[K]), 
        p=target_probs_list[K]
    ))
    accepted_tokens.append(bonus_token)
    return accepted_tokens

5. Why the Output Distribution is 100% Lossless

A common misconception among developers is that speculative decoding is an approximation or lossy distillation (like quantization or pruning).

It is mathematically exact. The probability of generating any sequence under speculative decoding is identical to generating directly from the large target model.

Here is the simple algebraic proof:

Let $x$ be the token candidate at position $i$. What is the total probability that token $x$ is emitted?

Probability $x$ was drafted and accepted:
$$P(\text{drafted } x) \times P(\text{accepted} \mid x) = q(x) \times \min\left(1, \frac{p(x)}{q(x)}\right) = \min(p(x), q(x))$$
Probability another token was rejected and $x$ was sampled from $p'(x)$:
The total rejection probability across all possible tokens is:
$$1 - \alpha = 1 - \sum_{y} \min(p(y), q(y)) = \sum_{y} (p(y) - \min(p(y), q(y))) = \sum_{y} \max(0, p(y) - q(y))$$

When rejection happens, the probability of choosing $x$ from the normalized residual is:
$$p'(x) = \frac{\max(0, p(x) - q(x))}{1 - \alpha}$$

Therefore, the joint probability of rejection and choosing $x$ is:
$$(1 - \alpha) \times \frac{\max(0, p(x) - q(x))}{1 - \alpha} = \max(0, p(x) - q(x)) = p(x) - \min(p(x), q(x))$$

Total Probability: $$\text{Total } P(x) = \min(p(x), q(x)) + [p(x) - \min(p(x), q(x))] = p(x)$$

The draft distribution $q(x)$ completely cancels out. Whether the draft model has 50% accuracy or 90% accuracy affects only speed, never correctness.

6. Modern Variants: Beyond Standalone Draft Models

While standalone draft models (like Llama-3-8B drafting for Llama-3-70B) work well, the open-source community and inference engines (vLLM, SGLang, llama.cpp) have developed even faster variations:

A. Medusa (Multi-Head Self-Speculative Decoding)

Instead of maintaining an entire second model in VRAM, Medusa attaches multiple lightweight feed-forward decoding heads to the target model's final hidden state. Head 1 predicts token $t+1$, Head 2 predicts token $t+2$, Head 3 predicts token $t+3$. This eliminates the draft model footprint entirely.

B. EAGLE (Extensible Autoregressive Generation)

Standard draft models operate on text tokens, losing the rich contextual embeddings computed by the target model. EAGLE passes the top-layer feature vectors of the target model into the draft head. This boosts token acceptance rates from ~60% to over 80-85%.

C. Tree-Based Attention (SpecInfer)

Linear drafting guesses a single path $[x_1, x_2, x_3]$. If $x_1$ is rejected, everything else is wasted. Tree attention constructs a tree of multiple speculative branches (e.g. top-2 candidates at each depth). The target model verifies all candidate branches in parallel using a custom 2D attention mask, guaranteeing a higher average accepted token yield per step.

Linear Speculation (Fragile):
[Root] -> x1 -> x2 -> x3 (If x1 fails, x2 and x3 are dead)

Tree Attention Speculation (Resilient):
               +--> x1a --> x2a
[Root] --------|
               +--> x1b --> x2b
(If x1a fails, x1b might still be accepted!)

7. When Speculative Decoding Fails (Production Gotchas)

Speculative decoding is not a magic bullet for every deployment. Here are the 4 scenarios where it actually hurts performance:

1. High Batch Sizes (Compute-Bound Saturation)

Speculative decoding relies on spare GPU compute. When serving hundreds of concurrent requests (batch size 32, 64, or 128), your GPU is already 100% compute-bound. Adding draft forward passes creates compute contention and reduces overall throughput. Speculative decoding shines primarily at batch sizes 1 to 8 (low-latency streaming).

2. High Temperature and Creative Entropy

When sampling with high temperature ($T > 1.0$) on highly creative tasks, the output entropy is high. The overlap $\alpha = \sum \min(p, q)$ shrinks dramatically, causing frequent early rejections. Speculative decoding works best on structured output, code generation, and deterministic reasoning ($T \le 0.7$).

3. Tokenizer and Vocabulary Mismatches

The draft model and target model must share the exact same tokenizer vocabulary and special token mappings. If token IDs do not map to identical string representations, the logits cannot be compared directly.

4. VRAM Overhead on Edge Devices

Running a draft model requires reserving additional GPU VRAM for its weights and its own separate KV cache. On memory-constrained GPUs (e.g. 16 GB or 24 GB consumer cards), this extra memory might push the target model into slower quantized formats or offload buffers.

Summary & Mental Model

The Problem: Single-token decoding is memory-bandwidth bound. 99% of GPU latency is spent streaming weights from VRAM to compute cores.
The Workaround: Evaluating $K$ tokens in parallel takes the same memory bandwidth time as evaluating 1 token.
The Execution: A tiny draft model quickly proposes $K$ tokens. The target model verifies all $K$ tokens in a single parallel forward pass.
The Guarantee: Leviathan's speculative sampling algorithm mathematically recovers the exact target model probability distribution with zero quality loss.
The Sweet Spot: Low batch sizes, low temperature, deterministic coding, and agent tool-calling loops.

Python 3.13 Free-Threading: What Actually Happens When the GIL Is Removed

Syed Anzar — Sun, 04 Oct 2026 06:40:13 +0000

For over thirty years, every Python developer learned the same hard rule: CPU-bound code in standard Python cannot scale across multiple CPU cores using threading. The Global Interpreter Lock (GIL) forced every thread to take turns executing bytecode, serialization was inevitable, and multi-core speedups required multiprocessing with heavy IPC serialization overhead.

Starting in Python 3.13, CPython introduced an experimental free-threaded build (python3.13t via PEP 703) where the GIL is completely disabled.

Turning off the GIL was not just removing a single lock. The GIL served as the safety blanket protecting Python's memory layout, reference counters, and internal dicts from data races. Removing it required re-engineering the foundational memory architecture of CPython.

Here is what actually happens under the hood when the GIL is removed.

1. The Core Problem: Why the GIL Existed in the First Place

Every Python object contains a header with two fundamental fields: a pointer to its type object (ob_type) and a reference counter (ob_refcnt).

In standard GIL builds, whenever you pass a variable or read a list element, CPython increments or decrements ob_refcnt using simple non-atomic CPU instructions:

// Standard CPython non-atomic refcount macro
#define Py_INCREF(op) (((PyObject*)(op))->ob_refcnt++)
#define Py_DECREF(op) \
    if (--((PyObject*)(op))->ob_refcnt == 0) _Py_Dealloc((PyObject*)(op))

Non-atomic instructions (++ and --) take multiple CPU cycles: load value into register, increment register, store back to memory. If two OS threads modify that counter simultaneously without synchronization, you hit race conditions, missed decrements, double frees, and memory corruption.

The GIL avoided this by guaranteeing that only one thread touched ob_refcnt at any given moment.

Simply replacing every refcount operation with atomic assembly instructions (LOCK XADD on x86) was tried in earlier experimental forks (like Larry Hastings' Gilectomy). The result: single-threaded Python code slowed down by 30% to 50% because atomic bus-locking instructions invalidate CPU L1/L2 caches and choke CPU pipelines.

To make free-threading viable, PEP 703 implemented Biased Reference Counting (BRC).

2. Biased Reference Counting (BRC): Fast-Path vs Shared-Path

Biased Reference Counting is built on a simple observation: in real-world programs, most objects are created and manipulated exclusively by the single thread that allocated them.

Instead of one global reference count, free-threaded CPython splits reference counting into two distinct paths:

Local Refcount (ob_ref_local): Managed exclusively by the thread that owns (created) the object.
Shared Refcount (ob_ref_shared): Managed atomically by any other thread accessing the object.

+-------------------------------------------------------------+
|                     Python Object Header                    |
+-------------------------------------------------------------+
|  ob_tid (Thread ID of Owner)                                |
|  ob_ref_local   (16-bit: Non-atomic fast updates by owner)  |
|  ob_ref_shared  (32-bit: Atomic atomic updates by peers)   |
|  ob_type        (Pointer to Type descriptor)                |
+-------------------------------------------------------------+

The Fast Path (Owner Thread)

When the owning thread increments or decrements an object's reference counter, it checks if current_thread_id == object->ob_tid. If true, it performs a plain, non-atomic addition to ob_ref_local. This costs zero bus locks and keeps single-thread execution fast.

The Slow Path (Foreign Threads)

When another thread references that same object, it cannot touch ob_ref_local. Instead, it issues an atomic operation on ob_ref_shared.

Merging and Deallocation

When does the object actually get freed?
The owning thread periodically merges ob_ref_shared into ob_ref_local. When ob_ref_local + (ob_ref_shared >> 2) == 0, the owning thread triggers deallocation. If a non-owning thread drops the final reference while the owning thread is idle, an evaluation interrupt (eval_breaker) signals the owning thread to process the deferred cleanup safely.

3. Immortal Objects: Stopping Cache-Line Bouncing

Some objects are read constantly by every single running thread: None, True, False, small integers (0 to 256), built-in exceptions, type definitions (int, str, list), and top-level function code objects.

If 16 parallel threads constantly run Py_INCREF(Py_None) and Py_DECREF(Py_None), atomic cache-line invalidation would destroy multi-core performance. CPU cores would spend more time invalidating each other's L1 cache lines than executing code.

CPython solves this with Immortalization (PEP 683, adapted for PEP 703).

In free-threaded builds, immortal objects have their refcount bitfield set to a special constant (_Py_IMMORTAL_REFCNT). The refcount macros check this bitfield:

static inline void _Py_INCREF_STAT(PyObject *op) {
    if (_Py_IsImmortal(op)) {
        return; // No-op: Zero memory writes, zero cache invalidation
    }
    // Proceed to biased reference counting...
}

Because immortal objects never modify memory during refcounting, thousands of threads can read None, interned strings, or module definitions concurrently with zero memory contention.

4. Goodbye pymalloc, Hello mimalloc

Standard CPython relies on pymalloc, an allocator optimized for small Python objects under 512 bytes. However, pymalloc is completely non-thread-safe and relies entirely on the GIL for synchronization.

Rather than bolting locks onto pymalloc (which would kill allocation speed), free-threaded Python 3.13 replaces it with Microsoft's mimalloc allocator.

Mimalloc brings critical architectural advantages:

Thread-Local Heaps: Each thread maintains its own allocation arenas. Allocating a new dictionary or string requires zero global locks.
Radix-Tree Page Lookups: Enables the Garbage Collector to find and traverse all Python objects directly through heap metadata, eliminating the need to maintain global doubly-linked lists across all objects.
QSBR (Quiescent-State Based Reclamation): Prevents use-after-free bugs when memory pages are returned to the operating system while other threads are finishing up reads.

5. Per-Object Critical Sections: Replacing the Global Lock

Without the GIL, what prevents two threads from mutating the same list or dict simultaneously and corrupting internal hash tables?

CPython 3.13 introduces Per-Object Critical Sections (Py_BEGIN_CRITICAL_SECTION).

Instead of locking the entire runtime, Python locks only the specific container being modified:

// Example: Modifying a list in free-threaded CPython
Py_BEGIN_CRITICAL_SECTION(list_obj);
// Exclusive lock on list_obj held here
list_append_internal(list_obj, item);
Py_END_CRITICAL_SECTION();

Automatic Deadlock Avoidance

What if Thread A locks List 1 and wants List 2, while Thread B locks List 2 and wants List 1?

CPython critical sections maintain a thread-local stack of active locks. If a thread attempts to acquire an object lock that is currently held by another thread, the runtime automatically suspends all active critical sections held by the waiting thread, releases their locks, yields, and re-acquires them in a strict ordered hierarchy before continuing.

6. What This Means for Python Developers

Running Python 3.13 free-threaded (python3.13t) delivers real CPU-bound concurrency:

import sys
from concurrent.futures import ThreadPoolExecutor

print(f"Free threading enabled: {sys._is_gil_enabled() == False}")

def cpu_heavy_task(n):
    return sum(i * i for i in range(n))

# In Python 3.13t, this runs in true parallel across all 8 CPU cores
with ThreadPoolExecutor(max_workers=8) as executor:
    results = list(executor.map(cpu_heavy_task, [10_000_000] * 8))

Key Takeaways

True Parallel Threads: CPU-bound tasks in standard Python threads now scale linearly with CPU core counts without multiprocessing IPC overhead.
Thread Safety Still Matters: Built-in containers are safe from memory crashes due to internal critical sections, but race conditions in application logic still require explicit locks (threading.Lock).
C-Extensions Need Adaptation: C extensions must be compiled specifically for the free-threaded ABI (python3.13t) to verify they don't rely on the legacy GIL for internal struct safety.

Python's transition to free-threading is one of the most substantial engineering feats in modern language runtimes, unlocking decades of untapped multi-core performance while maintaining the syntax and ergonomics developers rely on.

Why LLMs Run Out of VRAM: KV Cache Fragmentation and How PagedAttention Fixes It

Syed Anzar — Thu, 01 Oct 2026 12:34:22 +0000

You deploy a 13-billion parameter model quantized to 4-bit weights. The static model weights consume roughly 7.5 GB of VRAM. You put it on an NVIDIA RTX 4090 with 24 GB of memory, confident you have more than 16 GB of headroom for traffic.

Then you run a batch of 8 concurrent requests with 4,000-token context windows.

Within seconds, your server throws torch.cuda.OutOfMemoryError: CUDA out of memory or your throughput collapses from 80 tokens per second to single digits.

Where did those 16 gigabytes go?

Most developers assume GPU memory during inference is dominated by model weights. In reality, once an LLM starts serving concurrent users, the Key-Value (KV) Cache quickly swallows more memory than the model itself.

Even worse: in naive serving setups, up to 60% to 80% of that VRAM is pure waste, locked away by memory fragmentation.

Here is what is actually happening inside GPU memory during inference, why naive allocators fail, and how an idea borrowed from 1960s operating systems (PagedAttention) fixed it.

1. Why Transformers Need a KV Cache

To understand why memory explodes, look at how autoregressive token generation works.

Generating text is an iterative loop. When generating token $t$:

The token is embedded and passed through $N$ transformer layers.
In each self-attention layer, the model computes Query ($Q$), Key ($K$), and Value ($V$) projections.
Attention is calculated: $$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$
To compute the attention of the new token $t$ against all previous tokens $(1 \dots t-1)$, the model needs the $K$ and $V$ vectors of every previous token.

Step 1:  [Prompt: "The", "quick", "brown"]  -> Generates "fox"
Step 2:  ["The", "quick", "brown", "fox"]   -> Generates "jumps"
Step 3:  ["The", "quick", "brown", "fox", "jumps"] -> Generates "over"

Without caching, generating token 1,000 would require recomputing the Key and Value matrices for all 999 previous tokens across every single transformer layer. That would turn inference complexity into $O(n^2)$ compute.

To avoid this quadratic recalculation, inference engines store the $K$ and $V$ tensors of all previous tokens in GPU High-Bandwidth Memory (HBM). On every step, we only compute $Q$, $K$, and $V$ for the single new token, append its $K$ and $V$ to the cache, and calculate attention against the stored history.

Compute drops to $O(1)$ per step. But your memory requirement becomes dynamic and strictly increasing.

2. The Concrete Math of KV Cache Growth

How big is a KV cache in physical memory?

For every generated token, at every transformer layer, we must store two vectors ($K$ and $V$).

The exact formula for KV cache memory per token is:

$$\text{Bytes per Token} = 2 \times n_{\text{layers}} \times n_{\text{kv_heads}} \times d_{\text{head}} \times b$$

Where:

$2$ accounts for both the Key and Value tensors
$n_{\text{layers}}$ is the number of transformer layers
$n_{\text{kv_heads}}$ is the number of Key-Value attention heads
$d_{\text{head}}$ is the hidden dimension per head
$b$ is the precision in bytes (2 bytes for FP16/BF16, 1 byte for FP8)

Example 1: Multi-Head Attention (Llama-2-13B)

Layers ($n_{\text{layers}}$): 40
KV Heads ($n_{\text{kv_heads}}$): 40 (standard Multi-Head Attention)
Head Dimension ($d_{\text{head}}$): 128
Precision: 16-bit float (2 bytes)

$$\text{Bytes per Token} = 2 \times 40 \times 40 \times 128 \times 2 = 819,200 \text{ bytes} \approx 800\text{ KB per token}$$

For a single request processing a 4,096-token context:
$$4,096 \times 800\text{ KB} \approx 3.2\text{ GB per sequence}$$

If you serve 8 concurrent users at 4k context:
$$8 \times 3.2\text{ GB} = \mathbf{25.6\text{ GB of VRAM}}$$

The KV cache alone exceeds the total VRAM of an RTX 4090 before you even account for model weights or CUDA overhead.

Example 2: Grouped-Query Attention (Llama-3-8B)

Modern architectures use Grouped-Query Attention (GQA) where multiple query heads share a single KV head.

Layers: 32
KV Heads: 8 (sharing across 32 query heads)
Head Dimension: 128
Precision: 16-bit float (2 bytes)

$$\text{Bytes per Token} = 2 \times 32 \times 8 \times 128 \times 2 = 131,072 \text{ bytes} = 128\text{ KB per token}$$

At 4,096 tokens, one request takes 512 MB. A batch of 32 requests takes 16 GB.

3. The Real Culprit: Memory Fragmentation

If a request only needs 512 MB at 4k tokens, why did naive serving engines run out of memory with only a handful of short requests?

The problem lies in how standard PyTorch memory allocators manage dynamic tensors.

Standard attention kernels (like basic PyTorch MultiheadAttention or cuDNN) expect the Key and Value tensors of a sequence to be stored in contiguous virtual and physical memory.

Naive Allocator (Contiguous Slot per Sequence):
Request A: [Token 1][Token 2][Token 3] ... [Reserved Empty Space up to 4096]
Request B: [Token 1][Token 2] ............ [Reserved Empty Space up to 4096]

Because the inference engine cannot predict when a model will emit the <|endoftext|> token, it faces three severe structural inefficiencies:

1. Internal Fragmentation (Static Max-Length Reservation)

To prevent constant memory reallocation and costly CUDA memory copies as sequences grow, naive engines pre-allocate a contiguous memory buffer sized for max_model_len (e.g., 4,096 tokens).

If a user prompt only generates 350 tokens and terminates, the remaining 3,746 token slots (over 90% of the allocated buffer) sit completely unused, yet locked.

2. Reservation Waste (Future Slots)

Even if an engine attempts dynamic chunking, it must reserve memory for future tokens that have not arrived yet. That reserved memory cannot be assigned to other concurrent requests.

3. External Fragmentation

Requests finish at different times. As short requests finish and free their memory chunks, the GPU memory pool becomes a checkerboard of small, non-contiguous free memory holes.

Even if you have 8 GB of total free VRAM, if the largest contiguous block is only 200 MB, a new incoming request requiring a 500 MB contiguous buffer will immediately crash with an Out of Memory error.

In research published by UC Berkeley (Kwon et al., SOSP 2023), measurements showed that in traditional serving systems like FasterTransformer and Orca, only 20% to 40% of the allocated KV cache memory actually held useful token states. The remaining 60% to 80% was lost to fragmentation.

4. How PagedAttention Solves Fragmentation

Operating systems solved the exact same problem for system RAM in the 1960s with Virtual Memory Paging.

A process sees a continuous virtual address space ($0 \dots N$), but the OS kernel splits physical RAM into fixed-size 4 KB pages. A CPU Page Table maps each virtual page to any available non-contiguous physical memory frame.

PagedAttention (the core engine powering vLLM, SGLang, and modern inference backends) applies this exact concept to GPU VRAM.

Logical KV Cache (Sequence 0):
[Block 0: Tokens 0-15] -> [Block 1: Tokens 16-31] -> [Block 2: Tokens 32-47]
           │                         │                         │
           ▼                         ▼                         ▼
Physical GPU Memory (Non-contiguous):
[Physical Block 84]       [Physical Block 12]       [Physical Block 903]

How the Architecture Works:

Fixed-Size KV Blocks: The KV cache of a sequence is partitioned into fixed blocks of tokens (typically 16 or 32 tokens per block).
Centralized Physical Block Pool: At startup, vLLM pre-allocates all available GPU memory into a pool of physical blocks.
Block Tables: For each active sequence, the engine maintains a Block Table (analogous to an OS page table). The block table records the physical block ID where each logical block resides, along with how many slots in the latest block are filled.
On-Demand Allocation: When a request starts, the engine allocates only one physical block (16 tokens). As the model generates tokens 1 through 15, it writes into the existing block. When it hits token 16, the engine grabs another physical block from the pool and records its address in the Block Table.

The PagedAttention CUDA Kernel

Standard cuBLAS and FlashAttention kernels require contiguous memory pointers.

PagedAttention replaces the attention operation with a custom GPU kernel. During the decoding step, the kernel reads the query token $Q_i$, looks up the sequence's Block Table, and dynamically fetches $K$ and $V$ vectors directly from scattered physical memory addresses across GPU HBM during the matrix multiplication loop.

The Result:

Internal Fragmentation: Limited strictly to the last uncompleted block of a sequence (less than 4% memory waste with block size 16).
External Fragmentation: 0%. Any free block anywhere in memory can be assigned to any sequence immediately.
Effective Batch Size: Increases by 2x to 4x on the exact same hardware.

5. Superpowers of Paged Memory: Zero-Copy Forking

Because memory is managed through indirection (block tables pointing to physical blocks), PagedAttention unlocks memory optimizations that are impossible with contiguous arrays.

1. Parallel Sampling & Tree Search

Suppose you want the model to generate 4 candidate completions for the same prompt (e.g., beam search, voting, or speculative draft trees).

In naive systems, you must duplicate the prompt's KV cache 4 times in memory.

With PagedAttention, all 4 sequences point their block tables to the same physical prompt blocks. The physical blocks are marked with a reference count of 4.

Request Prompt (Tokens 0-31): Physical Block #7, Physical Block #14 (Ref Count = 2)

Branch A (Tokens 32-47) -> Writes to new Physical Block #89 (Private)
Branch B (Tokens 32-47) -> Writes to new Physical Block #102 (Private)

Only when a branch generates its first new token does the engine allocate a new private block for that specific branch (Copy-on-Write). Memory consumption for the prompt is reduced by 75%.

2. Automatic Prefix Caching

In agentic workflows, system prompts, tool schemas, and multi-turn conversation history are reused constantly across requests.

With prefix caching enabled, when a new request arrives containing a system prompt that matches a previously computed sequence, vLLM checks its hash table of physical blocks. If the tokens match, it skips the prefill compute phase entirely and simply maps the existing physical blocks into the new request's block table.

First-token latency (Time-to-First-Token) drops from hundreds of milliseconds to near zero, and VRAM usage for the shared prefix drops to 0 additional bytes.

6. Practical Tuning Guide for Production Inference

If you are running self-hosted LLMs using vLLM, SGLang, or Ollama, here is how to tune these memory parameters for maximum throughput:

1. Tune GPU Memory Utilization

By default, vLLM sets gpu_memory_utilization=0.90. This reserves 90% of total VRAM for model weights and the KV block pool, leaving 10% for PyTorch activation buffers and CUDA contexts.

# For dedicated serving nodes with fixed models, raise utilization to 0.95
vllm serve meta-llama/Llama-3.1-8B-Instruct \
  --gpu-memory-utilization 0.95 \
  --max-model-len 8192

If you experience random CUDA initialization crashes, lower it to 0.85.

2. Select the Right Block Size

The default block size in vLLM is 16.

Block size 16: Lowest internal fragmentation. Best for workloads with short, unpredictable outputs.
Block size 32: Better GPU memory coalescing and slightly higher arithmetic throughput on high-end GPUs (A100/H100), with slightly higher tail waste.

vllm serve meta-llama/Llama-3.1-8B-Instruct --block-size 32

3. Enable Prefix Caching for Multi-Turn Agents

If you run coding assistants, customer support bots, or agent loops that share large system prompts:

vllm serve meta-llama/Llama-3.1-8B-Instruct \
  --enable-prefix-caching

4. Enable FP8 KV Cache

If you are memory-bound rather than compute-bound, you can quantize the KV cache from FP16 (2 bytes) to FP8 (1 byte). This cuts your KV memory usage in half with negligible perplexity degradation.

vllm serve meta-llama/Llama-3.1-8B-Instruct \
  --kv-cache-dtype fp8

Summary: Contiguous vs Paged Attention

Feature	Naive Contiguous Allocation	PagedAttention (vLLM)
Memory Layout	Contiguous virtual & physical DRAM	Non-contiguous fixed-size blocks
Memory Waste	60% – 80% (Internal & External fragmentation)	< 4% (Last-block tail only)
Max Batch Size	Constrained by peak pre-allocation	Dynamic, maximizes hardware saturation
Prompt Sharing	Requires full memory duplication	Zero-copy pointer sharing (Copy-on-Write)
Prefix Caching	Complex tensor slicing & copying	Instant block hash lookup

The next time your local or production LLM runs out of VRAM, remember: the bottleneck is rarely just the model parameters. Understanding how the KV cache grows and how paging eliminates memory waste is the single most important lever for scaling LLM inference throughput.

DEV Community: Syed Anzar

Why Increasing Database Connections Makes Queries Slower: Process Overhead, Little’s Law, and Pool Sizing Math

1. The Hardware Reality: CPU Cores Can Only Execute One Thing at a Time

2. The PostgreSQL Process-per-Connection Architecture

A. Private Memory (RSS) Footprint

B. Shared Memory Contention: The ProcArrayLock Bottleneck

3. The Queueing Math: Little's Law

What Happens When You Add 200 Connections?

4. The Canonical Connection Pool Formula

Practical Calculation

5. The Kubernetes Multi-Pod Multiplication Mistake

The Correct Formula for Distributed Pods

6. Client Pools vs Middleware Proxies (PgBouncer)

Why PgBouncer in Transaction Mode Solves the Problem

Transaction Pooling Incompatibilities to Watch Out For

7. Diagnosing Connection Health in Production

How to Interpret the Output:

8. Summary: Senior Engineer Sizing Rules

Why UPDATE Is Secretly an INSERT: How Postgres MVCC, xmin/xmax, and Table Bloat Actually Work

1. Physical Storage: Inside the 8KB Heap Page

2. The Step-by-Step Trace of an UPDATE

Initial State: A Fresh Insert (Transaction 100)

The UPDATE Executes (Transaction 105)

3. How MVCC Solves Concurrency Without Read Locks

4. The Hidden Tax: The Secondary Index Disaster

5. The Solution: Heap-Only Tuples (HOT)

6. Inspecting the Physical Page with pageinspect

7. Table Bloat and the Autovacuum Lifecycle

The Role of VACUUM

The Bloat Trap: VACUUM Does Not Shrink File Size

8. Senior Database Gotchas to Prevent MVCC Outages

1. The Long-Running Transaction Anchor

2. Tuning Table fillfactor for HOT Updates

3. Autovacuum Cost Delay Throttling

Summary Mental Model

How Linux Zero-Copy Actually Works: sendfile, DMA Scatter-Gather, and Page Cache Internals

1. The Hidden Tax of Traditional I/O (read + write)

The Step-by-Step Breakdown

Why Is This Expensive?

2. Evolution Level 1: mmap() + write()

The Hidden Trap: SIGBUS Crashes

3. Evolution Level 2: sendfile() Without Hardware Support

4. Evolution Level 3: True Zero-Copy (Scatter-Gather DMA)

How struct sk_buff Handles This Internally

5. splice(): Zero-Copy Between Arbitrary File Descriptors

The Magic of Pipe Buffers (struct pipe_buffer)

6. The Modern HTTPS Problem: Why TLS Broke Zero-Copy

The Solution: kTLS (Kernel TLS)

7. Zero-Copy Performance Summary

8. Senior Engineer Gotchas to Keep in Mind

Key Takeaway

How Model Context Protocol (MCP) Actually Works: JSON-RPC 2.0, Stdio IPC, and Low-Level Tool Calling

How Model Context Protocol (MCP) Actually Works: JSON-RPC 2.0, Stdio IPC, and Low-Level Tool Calling

1. The Architectural Problem MCP Actually Solved

2. The Three Core Entities

3. The Wire Protocol: JSON-RPC 2.0

A. Request (Client to Server or Server to Client)

B. Response (Success or Error)

C. Notification (One-Way Signaling)

4. Stdio Transport: File Descriptors and the Stderr Rule

File Descriptor Roles

The Most Common MCP Server Bug

5. SSE Transport: Remote Execution Over HTTP

6. The Protocol Lifecycle: Handshake to Execution

Step 1: The initialize Request

Step 2: The Server Response

Step 3: Acknowledgment

7. The Three MCP Primitives

How Tools Are Defined: JSON Schema Draft-07

8. What Happens During a Tool Call: End-to-End Execution Trace

9. The Hidden Pitfalls: Context Bloat and Security

A. The Context Window Tax

B. Security Boundaries and Prompt Injection

10. Summary Mental Model

How LoRA Actually Works: Low-Rank Decomposition, Weight Merging, and Memory Breakdown Under the Hood

How LoRA Actually Works: Low-Rank Decomposition, Weight Merging, and Memory Breakdown Under the Hood

1. The Real Memory Culprit: Why Full Fine-Tuning Explodes

2. The Intrinsic Rank Hypothesis

3. The Math: Low-Rank Matrix Factorization

The Parameter Reduction Math

B. Shared Memory Contention: The `ProcArrayLock` Bottleneck

6. Inspecting the Physical Page with `pageinspect`

2. Tuning Table `fillfactor` for HOT Updates

1. The Hidden Tax of Traditional I/O (`read` + `write`)

2. Evolution Level 1: `mmap()` + `write()`

The Hidden Trap: `SIGBUS` Crashes

3. Evolution Level 2: `sendfile()` Without Hardware Support

How `struct sk_buff` Handles This Internally

5. `splice()`: Zero-Copy Between Arbitrary File Descriptors

The Magic of Pipe Buffers (`struct pipe_buffer`)

Step 1: The `initialize` Request

2. The 3-File Architecture: `.db`, `.db-wal`, and `.db-shm`

`app.db` (The Main Database File)

`app.db-wal` (The Write-Ahead Log)

`app.db-shm` (The Shared Memory Index)

4. The Shared Memory Index (`.db-shm`): Why Readers Don't Scan the Log

Crucial Architectural Properties of `.db-shm`:

2. Loading Bytecode: The `bpf()` Syscall

The Modern Standard: `BPF_MAP_TYPE_RINGBUF`