Explaining The Concept of Pages in OS vs DB

The aim of this page📝 is to explain the confusing concept of “pages” across different computing contexts and clarify why this term means different things in operating systems versus database systems. Tried to read https://www.cs.umb.edu/~poneil/lsmtree.pdf over the weekend and kind of failed; the heavy dependence of algorithms on hardware specifics (speed of disk reads based on hard-drive technology of the day) was stunning for me as a newcomer.

Some notes from my conversation with an LLM below.

Investigation of Pages: A Dangerous Homonym For non-CS folk

Operating System Pages vs Storage Blocks Pages in operating systems refer to fixed-size units used by virtual memory management systems. They’re typically 4KB in size. They represent the smallest unit the Memory Management Unit (MMU) can manage for virtual-to-physical address translation. Blocks in storage are fixed-size units used by storage devices and file systems. Typical sizes are 512 bytes, 4KB, or 8KB. They represent the smallest unit a disk can read or write. Pages and blocks serve different purposes but are related. Blocks handle storage I/O granularity at the disk/SSD level. Pages handle memory management granularity at the RAM/virtual memory level. Modern systems often use the same 4KB size for alignment benefits.

The Page Cache: Where Concepts Intersect The page cache is also called filesystem cache or buffer cache. It’s a software cache in RAM that stores disk blocks in memory pages. It acts as a bridge between storage and memory hierarchies. The cache hierarchy places the page cache within RAM, not below it. The hierarchy flows: CPU registers → L1 Cache → L2 Cache → L3 Cache → RAM (including page cache) → Disk/SSD. Hardware caches (L1/L2/L3) sit between CPU and RAM. The page cache caches disk data within RAM itself.

Historical Context Virtual memory pages came first in the 1960s. Systems like Atlas Computer (1962) and Multics (1965) established “page” as the fundamental unit of virtual memory management. This happened before databases adopted the terminology. Database systems borrowed the “page” concept in the 1970s-1980s. They used it to organize their disk data. This created a parallel terminology. Database “pages” refer to disk storage units rather than memory units. The choice was made for conceptual similarity and alignment benefits with OS page sizes.

Database Pages: A Different Meaning In database literature like the LSM-tree paper, the Five Minute Rule discusses keeping “pages in memory buffer space.” The term “page” here refers to disk pages (storage units) being cached in memory buffers (RAM). It does not refer to OS virtual memory pages. The economic tradeoff is between RAM cost to cache a disk page versus the cost of disk I/O. SQLite implements database-specific pages as part of its storage engine. It organizes database files into fixed-size pages. The default is 4KB, configurable from 512 bytes to 64KB. Different page types exist: B-tree pages, overflow pages, and freelist pages. All are implemented in SQLite’s own code independent of OS pages.

Alternative Approaches ClickHouse’s MergeTree family uses a different approach. It uses “parts” instead of pages as the storage unit. Each insert creates a new part on disk. Background merges combine parts LSM-tree style. Columnar storage keeps one file per column within parts. The pattern across database engines shows each implements its own disk organization matching their workload. SQLite uses page-based B-trees for random access OLTP workloads. ClickHouse uses column-oriented parts with merges for analytical queries and compression.

How the Layers Work Together The layering works as follows: Application → Database Engine (with DB-specific abstractions like pages/parts/extents) → Operating System (with OS abstractions like filesystem blocks/OS pages) → Hardware (Disk/SSD). The OS simply sees database files as regular files with reads/writes. Modern systems use matching sizes. Database page sizes often align with OS page/block sizes (4KB) for efficiency. But conceptually database “pages” remain about disk organization. OS “pages” handle memory management. This alignment enables efficient swapping when OS pages move between RAM and disk.

Reading Database Literature When encountering “page” in database literature, it typically means a disk storage page. The database’s storage engine manages it. It’s not an OS virtual memory page. Recognizing this dangerous homonym is essential to avoid confusion.

Key Takeaways

• OS pages are memory management units (typically 4KB) handled by the MMU for virtual-to-physical address translation Storage blocks are disk I/O units (512 bytes to 8KB) representing the smallest unit a disk can read or write
• The page cache sits within RAM and bridges storage and memory by caching disk blocks in memory pages Virtual memory pages originated in the 1960s with Atlas Computer and Multics before databases existed
• Database systems adopted “page” terminology in the 1970s-1980s to describe disk storage organization units Database pages are conceptually different from OS pages despite often using the same 4KB size
• SQLite uses fixed-size database pages (default 4KB) with B-tree, overflow, and freelist page types ClickHouse uses “parts” instead of pages, with LSM-tree style merges and columnar storage per part
• The Five Minute Rule in database literature refers to disk pages cached in RAM, not OS virtual memory pages Database engines implement their own disk organization independent of OS abstractions
• The system layers flow: Application → Database Engine → Operating System → Hardware Modern alignment of database and OS page sizes (4KB) improves efficiency but doesn’t change their conceptual differences
• Reading database papers requires recognizing “page” as a dangerous homonym with context-dependent meaning

LINKS

• https://www.cs.umb.edu/~poneil/lsmtree.pdf
• https://www.vldb.org/pvldb/vol17/p3731-schulze.pdf