Architecture and Implementation of DBMS - Storage: Disks and Files

Flashcards covering database architecture, storage hierarchy, magnetic disk mechanics, RAID configurations, solid-state drives, buffer management algorithms, and physical page layout models.

In the memory hierarchy illustrated below, what are the layers from top to bottom, and how do their capacity and latency characteristics compare?

From top to bottom: CPU (with registers, capacity: bytes, latency: $< 1\,ns$), caches (kilo-/megabytes, $< 10\,ns$), main memory (gigabytes, $70\text{--}100\,ns$), hard disks (terabytes, $3\text{--}10\,ms$), and tape library (petabytes, latency varies). Moving downward, memory becomes larger and cheaper, but slower.

In the magnetic disk geometry diagram shown below, what do the structures labeled 'track', 'sector', and 'block' represent?

A track is a concentric ring on the platter; a sector is a geometric angular slice across tracks; and a block is the intersection of a track and a sector, representing the unit of data the system reads and writes at a time.

What three components determine the total access time to read or write a data block on a magnetic disk?

Access time is given by the formula $t = t_s + t_r + t_{tr}$, where $t_s$ is seek time (moving the disk arms to the requested track), $t_r$ is rotational delay (waiting for the block to rotate under the head), and $t_{tr}$ is transfer time (reading or writing the block data).

Why is sequential I/O significantly faster than random I/O on magnetic disks, and what rule of thumb applies to full table scans?

Sequential I/O incurs seek time and rotational delay only once rather than for every single block (e.g., reading $1000$ blocks of $8\,KB$ takes $\approx 12.72\,s$ randomly vs. $\approx 95.7\,ms$ sequentially). Consequently, if a query accesses at least $\approx 1\%$ of a file, reading the entire file sequentially is faster than random access.

What are track skewing, SPTF request scheduling, and zoning in magnetic disk systems?

Track skewing offsets sector $0$ across adjacent tracks to prevent rotational delay during multi-track sequential scans. SPTF (Shortest Positioning Time First) schedules requests requiring the smallest arm movement. Zoning places more sectors on larger outer tracks than on smaller inner tracks to optimize storage density.

How do the historical improvement rates of hard disk latency, throughput, and capacity compare?

Hard disk latency has improved marginally at only $\approx 10\%$ per year, whereas throughput (transfer rates) and storage capacity have grown by $\approx 50\%$ per year. This divergence causes the relative performance penalty of random access to worsen over time.

How did the top-performing DB2 9.5 on AIX system in the TPC-C benchmark achieve high I/O throughput?

It leveraged massive parallelism using $10{,}992$ disk drives ($73.4\,GB$ each at $15{,}000\,rpm$) plus $8$ internal SCSI drives, interconnected via $68 \times 4\,Gbit$ Fibre Channel adapters to process $6$ million transactions per minute.

What RAID level is illustrated below, and what are its characteristics regarding parallelism and reliability?

RAID 0 (disk striping without parity). It distributes data blocks across disks (e.g., blocks $1, 4, 7$ on disk 1; $2, 5, 8$ on disk 2; etc.) to achieve full I/O parallelism, but suffers from high failure risk ($3\times$ the failure risk of a single disk for 3 disks) with no fault tolerance.

What are the performance and fault-tolerance properties of RAID 1 (disk mirroring)?

RAID 1 replicates data across multiple disks. It provides I/O parallelism for read operations only and improves fault tolerance by allowing the system to survive the failure of one disk without data loss.

What RAID configuration is depicted below, and how does it achieve fault tolerance?

RAID 5 (disk striping with distributed parity). It distributes data and parity blocks across all disks, providing high I/O parallelism and single-disk fault tolerance without requiring a dedicated parity disk.

How does the floating gate flash memory cell shown below store non-volatile data?

A fully isolated floating gate is placed between the control gate and the source/drain channel. High voltage forces electrons onto or off the floating gate via the tunnel effect; the trapped charge shifts the threshold voltage ($V_{th}$) of the transistor, which is measured to read logical state '$0$' or '$1$'.

What are the key technical challenges of NAND flash memory regarding writes and endurance?

Pages cannot be updated in place and must be erased in whole blocks before rewriting (causing write amplification). Repeated high-voltage programming cycles degrade the thin isolation layer, limiting cell endurance to $10^4 \sim 10^5$ writes.

Based on the comparison shown below, how do solid-state drives (SSDs) differ from magnetic disks in read versus write latencies?

SSDs provide very low-latency random read access compared to magnetic disks. However, random writes on SSDs are significantly slower because target pages must undergo block-based erasure before new data can be written.

What physical mechanism allows Phase-Change Memory (PCM / PCRAM) to store binary data?

PCM utilizes chalcogenide material that toggles between a crystalline phase (low electrical resistance and high optical reflectivity) and an amorphous phase (high electrical resistance and low optical reflectivity) through thermal 'SET' and 'RESET' electrical current pulses.

What core characteristics define Storage-Class Memory (SCM)?

SCM combines non-volatility (data persistence like disks/SSDs) with the high access speed and fine-grained byte-level addressability of traditional RAM.

What is a Storage Area Network (SAN), and how does it interface with a DBMS?

A SAN provides block-based network storage over high-speed interconnects, abstracting underlying physical disks or RAID arrays to present virtual logical drives directly to the DBMS (unlike file-based network protocols like NFS or CIFS).

What are the primary responsibilities of the Disk Space Manager?

It abstracts low-level hardware details, exposes a page abstraction ($4\text{--}64\,KB$) to higher DBMS layers, maintains the mapping of page numbers to physical locations (e.g., OS file offsets, cylinder/track/sector, or tape offsets), and tracks free versus allocated pages.

Why is a bitmap preferred over a linked list for free space management when sequential access is required?

A bitmap uses one bit per page ($0$ for allocated, $1$ for free), allowing the disk space manager to quickly scan for and allocate contiguous sequences of free pages, which are essential for fast sequential I/O.

What is the role of the Buffer Manager and the buffer pool in a DBMS?

The buffer manager mediates between external storage and main memory by managing a dedicated memory area called the buffer pool. It loads requested disk pages into memory frames and uses a replacement policy to evict pages when the pool becomes full.

How do the pin() and unpin() operations operate within the Buffer Manager interface?

pin(pageno) loads the requested page into a buffer frame if not already present, increments its pinCount, and returns the frame address. unpin(pageno, dirty) decrements pinCount and sets the page's dirty flag to true if modified, making it evictable once pinCount reaches $0$.

Why does the Buffer Manager require both a pinCount and a dirty bit for each frame?

The pinCount prevents pages actively being used ($\text{pinCount} > 0$) from being evicted. The dirty bit records whether a page has been modified, avoiding redundant disk writes during eviction if the page was only read.

How do the LRU, LRU-k, and MRU buffer replacement policies determine which frame to evict?

LRU evicts the page whose latest unpin() call was longest ago. LRU-k evicts based on the $k$-th latest unpin() to resist pollution from one-time scans. MRU evicts the page unpinned most recently, which is optimal for sequential loops over large tables.

Why do relational database management systems avoid relying on operating system virtual memory and file caching?

DBMS engines possess exact awareness of query access patterns (enabling prefetching and page fixing/hating), require strict write ordering for transaction logging and recovery, and must avoid performance degradation caused by double buffering or OS paging.

What are the trade-offs between implementing a heap file as a linked list of pages versus a page directory?

A linked list is simple to implement but causes most partially filled pages to sit in the free list, requiring sequential scans to find adequate space. A page directory (space map) introduces slight memory overhead but enables fast searches for pages matching exact space requirements.

How do Best Fit, First Fit, and Next Fit algorithms allocate page space for a new record?

Best Fit places the record in the page that leaves the least unused space (minimizes fragmentation but requires a full scan). First Fit chooses the first page with sufficient space. Next Fit resumes searching from the previous cursor position to avoid repeatedly checking full pages at the start.

How does a slotted page layout manage record storage and maintain stable Record Identifiers (RIDs)?

A Record Identifier is defined as $\langle pageno, slotno \rangle$. A slot directory at the front of the page tracks pointers to records that grow inward from the end of the page; records can be reorganized or moved within the page without altering their external RID.

What is interpreted storage for sparse columns, and why is it used?

Interpreted storage stores non-null values alongside explicit column IDs (e.g., $\langle \text{Column ID}, \text{Value} \rangle$) rather than reserving fixed offsets for every attribute, drastically conserving space in schemas with many optional or sparse attributes.

How do NSM, DSM, and PAX page layouts differ in how they store relational table attributes?

NSM (row-store) stores complete tuples contiguously on a page. DSM (column-store) stores individual attribute values contiguously across dedicated column pages. PAX (Partition Attributes Across) divides each page into mini-pages, storing columns contiguously within the page to boost CPU cache performance while preserving row locality.