Course contents
On this page
Memory and buffer management — extended reference
Original detailed coverage and citations accompanying the focused memory and buffer management lesson.
This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.
Part 2: Representing and locating data
Prerequisites: Lesson 08 and the preceding foundations.
Learning outcomes
- Trace a page from cache lookup through pinning, modification, writeback, and eviction.
- Explain how replacement, prefetching, and scan behavior interact with a working set.
- Compare buffer-pool ownership with page-cache, direct-I/O, and memory-mapped approaches.
A scan displaces the useful working set
A service’s transactional records usually fit comfortably in its cache. A reporting query scans a much larger table once. The next burst of ordinary lookups becomes slow because the scan replaced frequently used pages with pages unlikely to be reused soon. Total memory did not shrink. The replacement policy admitted the wrong data for the workload.
A buffer manager maps persistent pages or blocks into reusable memory frames. It decides how to locate a cached object, load a missing one, protect it while in use, choose an eviction victim, and write modified data safely. A cache is therefore not simply a dictionary plus an eviction list. It is part of the engine’s concurrency and recovery architecture.
Page identity and frame identity
A page has a persistent identity such as a file and page number. A frame is a reusable region of memory that can hold one page at a time. The mapping from page to frame changes over time. A caller must not retain a raw frame pointer after the buffer manager is permitted to reuse it for another page.
A pin records that a caller still depends on the frame’s contents. Eviction chooses only eligible frames. A latch or other structural protection controls concurrent access to the contents and metadata. A pin prevents reuse; it does not automatically make concurrent reads and writes safe. Those are different responsibilities.
fetch(page_id):
find or reserve a unique loading entry for page_id
if already resident:
pin frame
return frame
reserve an eligible frame
read page into reserved frame
validate page identity and integrity
publish resident mapping
return pinned frameThis conceptual path omits important recovery and synchronization detail, which must be supplied by a real implementation. The unique loading entry prevents two misses from independently loading the same page and publishing conflicting mappings. Failure during the read must wake waiters and release reservations rather than leaving a permanently loading entry.
Hits, misses, and average cost
A cache hit can still require hashing, metadata synchronization, pin management, and decompression. A miss adds storage access and possibly victim writeback. The average cost depends on both hit rate and the difference between hit and miss costs.
For illustrative hit rate 98%, hit cost 1 microsecond, and miss cost 200 microseconds, mean access cost is 0.98 × 1 + 0.02 × 200 = 4.98 microseconds. At 99% hits, the same model gives 2.99 microseconds. A one-percentage-point change in hit rate therefore produces a much larger percentage change in average access cost under these assumptions.
The model excludes queueing, correlated misses, and latency tails. A miss can also trigger several dependent reads, such as an index node followed by a data page. A high aggregate hit rate can hide poor behavior on the one request class that matters. Cache metrics should be broken down by object type, operation, and tenant where useful.
Replacement policy and admission policy
Least recently used, or LRU, evicts data not accessed recently. Its intuitive benefit is recency tracking. Its costs include metadata updates and vulnerability to scans that briefly touch many pages. Clock-like algorithms approximate recency with less per-access work. Frequency-aware or segmented policies can distinguish repeatedly useful data from one-time reads.
Admission is the decision to put an object into the cache at all. A streaming scan may bypass ordinary admission or enter a low-priority segment. This can preserve the transactional working set. The engine needs enough information to identify streaming access without incorrectly bypassing genuinely reusable data.
A replacement policy also interacts with concurrency. A single global recency list can become a hot structure under many cores. Sharding metadata reduces contention but can strand capacity or produce uneven replacement behavior. Sampling victims or using approximate counters can lower overhead while retaining safe ownership rules. Approximation is acceptable for performance hints; it is not acceptable for deciding whether a still-pinned frame can be overwritten.
Dirty pages and writeback
A dirty page contains changes not yet reflected in its persistent data-file representation. Evicting it may require writeback. Under a write-ahead-log design, the log information required to recover those changes must be durable before the page is written in a dependent state. Choosing a victim is therefore constrained by recovery ordering.
Foreground eviction that unexpectedly waits for a log flush and page write can produce large latency spikes. Background cleaning attempts to keep enough reusable capacity available before misses require it. Cleaning too aggressively can write the same hot page repeatedly, increasing device traffic. Cleaning too slowly creates bursts of forced work and long recovery or checkpoint pressure.
The buffer manager should track useful watermarks, dirty age, and available clean frames. A checkpoint may require a particular set of changes to become represented durably, but it need not mean pausing all work and flushing every page at once. The exact protocol depends on the engine’s recovery design. Lesson 24 explains why checkpoint semantics must be stated precisely.
Memory budgets extend beyond cached pages
A database’s memory use includes cached data, indexes, query operator state, transaction metadata, connections, output buffers, and background queues. Giving nearly all RAM to the buffer pool can starve a hash join or a replication backlog. Per-query memory limits can also multiply across simultaneous operators and workers.
Consider an illustrative server with 64 GiB available to its process. A 48 GiB buffer pool leaves 16 GiB for everything else. If 100 simultaneous queries each allocate two 64 MiB structures, operator state alone can reach 12.5 GiB. Connection and engine metadata can then exhaust the remainder. A configuration value described as “per operation” must be multiplied by actual concurrency and plan structure.
Memory reservation and admission can make these demands explicit. An operator that cannot reserve enough memory may choose an external algorithm or wait before starting. An engine that discovers the problem only after allocating can enter operating-system memory pressure or terminate. Controlled spilling is slower than an in-memory path but often better than an uncontrolled process failure.
Prefetch and overlapping I/O
Prefetch requests data before the consumer needs it. Sequential scans can predict upcoming pages and overlap storage access with processing. Index traversals with dependent addresses offer less opportunity. A query planner or execution engine can expose future access patterns that the lower-level cache cannot infer easily.
Too much prefetch consumes bandwidth, memory, and queue depth. If the query is cancelled or its predicate stops early, prefetched data may never be used. A shared device can delay transactional misses behind speculative scan reads. Prefetch should therefore be bounded and coordinated with priorities and cancellation.
Asynchronous I/O changes how waiting is represented. A worker can issue reads and resume other work rather than blocking a dedicated thread. The data dependency still exists: the operator cannot consume a missing page until the read completes. Buffers must remain reserved throughout the I/O, and completion must validate that ownership has not changed. Reusing a frame before an old read finishes can overwrite unrelated new data.
Operating-system caching and memory mapping
A database buffer pool can coexist with the operating-system page cache. This may duplicate data, but it can also provide a second reuse layer. The two managers use different information and compete for physical memory. Measurements should distinguish database cache misses from actual device reads.
Direct I/O gives the engine more responsibility for alignment, buffering, and I/O scheduling. Memory mapping represents page access through virtual-memory faults and mappings. Neither choice automatically removes page lifetime, fault handling, or persistence ordering. The system still needs a coherent response when the device fails or the process accesses data not currently resident.
A memory-mapped engine can appear simple at the API boundary while delegating replacement and fault timing to the operating system. A custom buffer pool can provide finer control while adding code and concurrency hazards. The right choice depends on portability, workload, operational control, and the engine’s need to coordinate caches with transaction state.
Shared cache and tenant interference
A multitenant service needs to decide whether all tenants compete in one cache, receive separate allocations, or share capacity under quotas. Strict partitioning protects tenants but can waste idle allocations. Complete sharing improves aggregate utilization while allowing one tenant to displace another’s working set.
A useful middle ground can reserve minimum capacity or admission budgets and allow controlled borrowing. The implementation still needs a policy for reclaiming borrowed space without causing sudden latency cliffs. Cache hit rate alone does not measure fairness: a tenant with a tiny hot dataset can be harmed severely by a small absolute eviction volume.
Background work also acts as a cache consumer. Compaction can read blocks that foreground queries rarely need. Replication or backup can stream through data. An engine should consider whether these paths use the same cache and admission policy. Otherwise maintenance changes the effective workload even when application traffic remains stable.
A miss has several competing owners
A lookup for page P can race with another lookup for P, an eviction choosing a victim, and a background cleaner writing that victim. A correct design assigns each frame states such as free, reserved, loading, resident, and evicting. The mapping table and frame state must agree on which page the frame represents. A reader cannot infer identity from the address of the frame alone.
Consider two simultaneous misses. Worker A reserves a mapping entry for P and begins loading it. Worker B discovers the loading entry and waits for its completion instead of independently publishing another frame for P. If A’s read fails, it records a failure state, wakes B, and releases resources under a defined protocol. If A simply disappears without cleaning up, the page can become permanently inaccessible despite healthy storage.
Now consider eviction. Before replacing page Q with P, the manager must prevent new pins on Q while verifying that existing pins have drained. Removing Q’s mapping and reusing its frame are coordinated state transitions. A reader that finds Q’s old mapping just before removal needs either to obtain a valid pin or retry after detecting the changed generation. This is a small example of the publication and reclamation problems later explored for concurrent indexes.
Asynchronous completion adds another race. An old read for Q may complete after cancellation. If its destination frame has already been reused for P, the completion can overwrite P’s bytes. The safe rule is that an in-progress I/O retains ownership of its destination until completion or a cancellation protocol establishes that no write can occur. An application deadline alone cannot establish that physical lifetime boundary.
Dirty flags need more than one bit of intuition
A cleaner begins writing a dirty page. While that I/O is in progress, another transaction changes the page again. If the cleaner blindly clears the dirty flag when its write completes, it can forget the later change. One solution records a modification generation or log position before copying the write image and clears the relevant dirty state only if no newer change requires persistence. Another creates a stable copy under appropriate protection and tracks subsequent modifications separately.
The cleaner also obeys write-ahead ordering. If the page image contains changes represented by log records through position L, the recovery protocol may require the log to be durable through L before the page image can become persistent. A completion of the page write cannot substitute for the missing log. Page-level checksums can detect corruption but do not reconstruct unlogged changes.
A dirty page is not necessarily an uncommitted page, and a clean page is not necessarily irrelevant to active transactions. A committed transaction may leave data pages dirty because its log already provides recovery. An uncommitted transaction’s changes may reach a data file under a recovery design that supports undo. Exact rules depend on the engine’s steal/no-steal and force/no-force choices. The buffer manager and transaction manager must share those rules explicitly.
Replacement policy has a CPU budget
An exact LRU cache moves an entry toward the recent end on every hit. At one million hits per second, that means one million policy updates per second in addition to pinning and lookup. A single shared list can become a synchronization hotspot. An approximation that occasionally chooses a suboptimal victim can still outperform exact LRU if it substantially reduces metadata traffic.
Clock-like policies inspect reference information as they search for a victim. A page recently touched can receive another chance. The approximation avoids a full ordered update on every access, but scanning many pinned or recently referenced frames can itself cost work. A heavily pinned cache can have plenty of nominal capacity and few immediately reusable frames. Monitoring resident bytes alone misses that distinction.
Sharded caches reduce shared metadata contention by assigning blocks to separate policy domains. A skewed workload can leave one shard under pressure while another retains cold data. Increasing the number of shards can therefore reduce both contention and effective pooling of free capacity. Policies can borrow or rebalance capacity, but the extra coordination should be evaluated against the original bottleneck.
The same principle applies to hit counters. Updating an exact global statistic on every access can contend on one cache line. Per-worker counters or batched updates preserve useful observability with less coordination, provided aggregation semantics are clear. Performance metadata can be approximate; the safety decision about a pin or frame generation cannot.
A concrete scan-pollution scenario
Assume a constructed 16 GiB cache contains a repeatedly used 12 GiB transactional working set. A report sequentially scans 200 GiB. If every scanned page receives the same admission and recency treatment as transactional pages, the report can replace most of the useful working set. When the next interactive burst arrives, many requests pay storage latency and contend for I/O with the continuing report.
A scan-resistant policy can admit pages into a small probationary region or bypass the main cache for clearly streaming access. A page touched again can be promoted. This preserves frequently reused pages while allowing the report to progress through bounded buffers. However, a scan that repeats frequently may actually be worth caching. Admission should reflect reuse evidence or execution hints rather than treating every large query as worthless.
Suppose a missed transactional page costs an extra 250 microseconds under light load. If pollution creates 100,000 additional misses, it introduces 25 CPU-independent seconds of aggregate miss residence under the simplified per-access sum. Those waits can overlap, so they do not imply the incident lasts 25 seconds. They still consume I/O capacity and increase in-flight state. Under saturation, queueing can make each miss cost more than the original 250 microseconds.
Choosing compressed and uncompressed cache boundaries
A cache can retain encoded blocks, decoded pages, or both. Compressed entries increase the number of logical bytes represented in a fixed memory budget, while hits may require decompression and temporary output. Uncompressed entries make repeated access cheaper but reduce coverage. The right boundary depends on reuse frequency, compression ratio, decode cost, and whether queries need an entire block.
For an illustrative block that is 64 KiB decoded and 16 KiB compressed, 1 GiB can retain approximately 16,384 decoded blocks or 65,536 compressed blocks before metadata. If decompression costs 20 microseconds and a physical miss costs 300 microseconds, a compressed hit may still be much cheaper than a device read. If the working set already fits decoded and requests are CPU-bound, compression could make the hot path worse.
Keeping both representations can waste capacity unless reuse justifies it. The operating-system cache can also retain compressed file bytes while the engine holds decoded pages, creating a useful two-level design or unintended duplication. Measure physical resident memory and device reads rather than assuming an engine cache miss always reaches storage. RocksDB’s documented block-cache choices provide a concrete example of explicit cache boundaries. RocksDB block cache
Bounded prefetch under cancellation and priority
A scan can request the next several pages while processing the current page. If I/O latency is 1 millisecond and processing consumes 100 microseconds per page, enough independent future work can overlap part of the latency. The needed window depends on throughput, queueing, and access pattern. Issuing the entire remaining scan at once is unnecessary and can monopolize memory and device queues.
A bounded prefetcher tracks outstanding bytes and stops when its budget is exhausted. Completion returns budget. Cancellation prevents new speculative reads, while already submitted operations retain their buffers until safe completion. Priority can favor interactive misses over speculative work. This is an application of backpressure within the storage engine rather than at a client connection.
A useful metric is useful-prefetch ratio: how much prefetched data was consumed before eviction or cancellation. High speculative throughput with little consumption is wasted work. Conversely, low hit rate on speculative buffers can be fine if each page is consumed once and retired intentionally. Metrics need to match the policy’s goal, not assume every memory path is a reuse cache.
Memory pressure can change the algorithm
A buffer manager should communicate pressure to execution rather than merely letting allocations fail. A hash aggregation can partition and spill aggregate state, reduce the number of concurrently resident partitions, or wait for a reservation. A query may choose a lower-memory plan before starting. A backup can reduce its read window. These responses trade latency and throughput in controlled ways while preserving process availability.
The reservation must cover peak simultaneous ownership, including transitions. A compactor writing new files may temporarily retain old files and output buffers. A hash join that repartitions can need input and output buffers at the same time. Ignoring transition peaks gives a budget that works in steady state and fails during the very recovery or spill operation meant to relieve pressure.
This makes memory management part of overload design. A service that uses all memory for cached data has no room for a reconnect burst, failover replay, or a large result. Headroom is a resource reserved for variation and recovery. Its required size follows from failure scenarios and retained state, rather than a universal fixed percentage.
Make the page lifecycle explicit
FREE -> RESERVED -> LOADING -> RESIDENT CLEAN
| pin/unpin controls eligibility
| modify under protection
v
RESIDENT DIRTY
| log ordering + stable write image
v
WRITEBACK IN PROGRESS
| completion, check newer changes
v
CLEAN or STILL DIRTY
| no pins, no incompatible I/O
v
EVICTING -> FREEThis is a conceptual state diagram rather than a required implementation enum. A page can be dirty and pinned at the same time; dirty status and pin status are different dimensions. A completed writeback can leave the page dirty when newer modifications arrived. Eviction eligibility therefore cannot be decided from a single clean/dirty bit.
A failure transition must release reservations and notify waiters. A validation error on a loaded page must not publish corrupt data as a successful resident hit. A generation or ownership rule prevents old asynchronous completions from affecting a recycled frame. These obligations remain even if the replacement policy itself is approximate or intentionally scan-resistant.
Case connection and design conclusion
RocksDB documents a block cache and associated memory-management choices. PostgreSQL exposes resource-consumption controls for its buffer and execution environment. These are examples of a shared principle rather than interchangeable settings: memory is divided among several responsibilities, and increasing one budget can reduce another’s headroom.
The engine designer should trace the full lifecycle of a page or block: reserve, load, validate, publish, pin, access, modify, unpin, clean, and evict. Correct lifetime management is essential even when replacement decisions are approximate. With that lifecycle established, Lesson 10 can build indexes whose nodes remain valid while readers traverse them and writers change their structure.