Storage and File Structureالتخزين وبنية الملفات

• Reliability covers data loss on power failure or system crash and physical failure of the storage device (slide 3).
• Main memory: fast access; capacities of up to a few gigabytes widely used currently; capacities have gone up and per-byte costs have decreased steadily and rapidly; volatile — contents are usually lost if a power failure or system crash occurs (slide 4).
• Flash memory: increasingly used as a replacement for magnetic disks for storing moderate amounts of data; writes are slow (few microseconds); widely used in embedded devices such as digital cameras, phones and USB keys (slide 5).

Slides 11–12

• Slide 11 labels the parts of the disk mechanism: spindle, track t, sector s, cylinder c, platter, read–write head, arm, arm assembly, rotation (the diagram is schematic and simplifies actual disk drives).
• Read-write head: positioned very close to the platter surface (almost touching it); reads or writes magnetically encoded information.
• Typical sectors per track: 500 to 1000 (inner tracks) to 1000 to 2000 (outer tracks).
• To read/write a sector: the disk arm swings to position the head on the right track; the platter spins continually and data is read/written as the sector passes under the head.
• Head-disk assemblies: multiple platters on a single spindle (1 to 5 usually), one head per platter, mounted on a common arm.

The disk controller (slide 13)

• Accepts high-level commands to read or write a sector, and moves the arm.
• Computes and attaches checksums to each sector to verify data is read back correctly.
• Ensures successful writing by reading back the sector after writing it.
• Performs remapping of bad sectors.

Slide 13

• Earlier generation disks were susceptible to head-crashes: metal-oxide coatings could disintegrate and damage all data on the disk; current disks are less susceptible, although individual sectors may get corrupted.
• If data is corrupted, with very high probability the stored checksum won't match the recomputed checksum.

• Slide 14 draws a disk controller on the system bus with four disks attached: multiple disks connected to a computer system through a controller.
• Controller functionality (checksum, bad sector remapping) is often carried out by individual disks, reducing load on the controller.
• Interface families: ATA (AT adaptor), SATA (Serial ATA), SCSI (Small Computer System Interconnect), SAS (Serial Attached SCSI); several variants of each (different speeds and capabilities).
• Disks are usually connected directly to the computer system (slide 15).

Slides 16–17

• Average seek time would be 1/3 of the worst case if all tracks had the same number of sectors, ignoring the time to start and stop arm movement.
• Rotational latency 4 to 11 ms on typical disks (5400 to 15000 r.p.m.).
• Multiple disks may share a controller, so the rate the controller can handle is also important: SATA 150 MB/sec, SATA-II 3Gb (300 MB/sec); Ultra 320 SCSI 320 MB/s, SAS 3 to 6 Gb/sec; Fiber Channel (FC2Gb or 4Gb) 256 to 512 MB/s.
• Probability of failure of new disks is quite low, corresponding to a "theoretical MTTF" of 500,000 to 1,200,000 hours for a new disk (slide 17).

• Block sizes range from 512 bytes to several kilobytes (slide 18).
• Elevator algorithm figure (slide 18): requests R6, R3, R1, R5, R2, R4 lie from the inner track to the outer track; the arm serves them sweeping toward the outer track, then back toward the inner track.
• Fragmentation: data inserted to/deleted from the file, or free blocks scattered so a new file has its blocks scattered — sequential access then means increased arm movement (slide 19).
• Non-volatile RAM: even if power fails, the data is safe and will be written to disk when power returns; the controller writes to disk when there are no other requests or a request has been pending for some time; database operations needing safe storage can continue without waiting (slide 20).
• A log disk is used exactly like nonvolatile RAM, with no need for special hardware (NV-RAM) (slide 20).

• Disk-arm scheduling (e.g., the elevator algorithm) orders pending accesses to minimize arm movement.
• Store related information on the same or nearby cylinders; fragmented files increase arm movement — defragment utilities help.
• Nonvolatile write buffers (battery-backed RAM or flash) make writes safe and fast; writes can be reordered.
• A log disk writes a sequential log of block updates — very fast since no seeks are required.
• Journaling file systems write in safe order; reordering without journaling risks corruption.

• Mirroring (shadowing): duplicate every disk; writes go to both, reads to either; data is lost only if a disk and its mirror both fail before repair — e.g., mean time to data loss of 500 × 10⁶ hours (57,000 years).
• Parallelism goals: load-balance small accesses (throughput) and parallelize large accesses (response time).
• Block-level striping: with n disks, block i goes to disk (i mod n) + 1. Bit-level striping (bit i of each byte to disk i) is not used much any more.

• Redundancy: store extra information that is not needed normally, but can be used in the event of failure of a disk to rebuild the lost information (slide 22).
• Mirroring: a logical disk consists of two physical disks; the combined-failure probability is very small except for dependent failure modes such as fire, building collapse or electrical power surges.
• Mean time to data loss depends on mean time to failure and mean time to repair: MTTF of 100,000 hours and mean time to repair of 10 hours give 500 × 10⁶ hours (57,000 years) for a mirrored pair (ignoring dependent failure modes).
• Bit-level striping: in an array of eight disks, each access can read data at eight times the rate of a single disk, but seek/access time is worse than for a single disk (slide 23).
• Block-level striping: requests for different blocks can run in parallel; a long sequence of blocks can use all disks in parallel (slide 23).
• RAID was originally a cost-effective alternative to large, expensive disks; today RAIDs are used for their higher reliability and bandwidth (slide 21).

• RAID levels: schemes to provide redundancy at lower cost by using disk striping combined with parity bits; different levels have differing cost, performance and reliability (slide 24).
• Slides 24–29 draw each level: (a) RAID 0 four disks; (b) RAID 1 four disks and four copies (C); (c) RAID 2 four disks and three parity disks (P); (d) RAID 3 four disks and one parity disk; (e) RAID 4 four disks and one parity disk; (f) RAID 5 five disks, each holding parity; (g) RAID 6 six disks with P and Q.
• RAID 3: faster data transfer than a single disk, but fewer I/Os per second since every disk participates in every I/O; subsumes level 2 (slide 26).
• RAID 4: higher I/O rates for independent block reads than level 3; high transfer rates for reads of multiple blocks; before writing a block, parity must be computed — from the old parity block, old and new value of the block (2 block reads + 2 block writes), or by recomputing from the new values of the blocks (more efficient for large sequential writes) (slide 27).
• RAID 5: higher I/O rates than level 4 — block writes occur in parallel if the blocks and their parity blocks are on different disks (slide 29).

• To recover a damaged disk/block in levels 3–5: compute the XOR of the corresponding bits/blocks of the other disks (including parity).
• Level 5 with 5 disks: the parity block of the nth set of blocks is on disk (n mod 5) + 1.

Rules (slides 30–31)

• RAID 0 only when data safety is not important.
• Levels 2 and 4 are never used — subsumed by 3 and 5. Level 3 is not used anymore. Level 6 is rarely used.
• Level 1: much better write performance than level 5 — level 5 needs at least 2 block reads + 2 block writes per block write; level 1 only 2 block writes. Preferred for high-update environments such as log disks.
• Level 5: preferred for applications with low update rate and large amounts of data; level 1 for all other applications.

• RAID 0 e.g. when data can be recovered quickly from other sources; level 3 is not used since bit-striping forces single block reads to access all disks; level 6 is rarely used since levels 1 and 5 offer adequate safety for most applications (slide 30).
• Level 1 had higher storage cost than level 5, but disk capacities grow rapidly (50%/year) while access times decreased much less (×3 in 10 years); I/O requirements have increased greatly (e.g. Web servers); when enough disks are bought for the I/O rate they often have spare capacity — so there is often no extra monetary cost for Level 1 (slide 31).

Hardware issues (slides 32–33)

• Software RAID: implemented entirely in software, with no special hardware support. Hardware RAID: special hardware; uses non-volatile RAM to record writes being executed (slide 32).
• Beware: power failure during write can result in a corrupted disk (e.g. after writing one block but before the second in a mirrored system); corrupted data must be detected when power is restored — recovery is like recovery from a failed disk; NV-RAM helps detect potentially corrupted blocks efficiently, otherwise all blocks must be read and compared with mirror/parity (slide 32).
• Latent failures can result in data loss even if only one disk fails; hot swapping is supported by some hardware RAID systems and reduces time to recovery; many systems keep spare disks online to replace failed disks immediately; redundant power supplies with battery backup and multiple controllers and interconnections guard against single points of failure (slide 33).

• A database is a collection of files; a file is a sequence of records; a record is a sequence of fields.
• Record i starts at byte n × (i − 1) (n = record size); records may cross blocks — so do not allow records to cross block boundaries.

• No pointers are stored in in-use records (slide 39).

Variable-length records (slide 40)

• Arise from multiple record types in a file, variable-length fields (varchar), and repeating fields.
• Variable-length attributes are stored as a fixed-size (offset, length), with the actual data after all fixed-length attributes.
• Null values are represented by a null-value bitmap.

Slotted page structure (slide 41)

• The header holds the number of record entries, the end of free space in the block, and the location and size of each record.
• Records can be moved within the page to stay contiguous; the header entry is updated.
• Pointers point to the record's entry in the header, not directly to the record — this indirection lets records move without breaking pointers.

• Slide 41 figure: a block header with # Entries, End of Free Space and a (size, location) entry per record; free space in the middle; records at the end of the block, each header entry pointing to its record.
• Attributes are stored in order; variable-length records arise from repeating fields used in some older data models (slide 40).
• This level of indirection allows records to be moved to prevent fragmentation of space inside a block, while supporting indirect pointers to the record (slide 41).

• Heap: typically there is a single file for each relation (slide 42).
• Sequential: suitable for applications that require sequential processing of the entire file; the records are ordered by a search-key (slide 43).
• Slide 43 draws the 12 instructor records in ID order, each pointing to the next; slide 44 inserts 32222 Verdi Music 48000 into an overflow block at the end and links it into the pointer chain.

Sequential file maintenance (slide 44)

• Deletion: use pointer chains.
• Insertion: insert at the right position if there is free space; otherwise in an overflow block; update the pointer chain.
• Reorganize the file from time to time to restore sequential order.

• A database file is partitioned into fixed-length blocks — units of both storage allocation and data transfer.
• The goal: minimize the number of block transfers by keeping as many blocks as possible in main memory.
• Buffer: the portion of main memory storing copies of disk blocks. Buffer manager: the subsystem that allocates buffer space.

• Programs call on the buffer manager when they need a block from disk (slide 50).
• The replaced block is written back to disk only if it was modified since the most recent time that it was written to/fetched from the disk (slide 50).

• Most operating systems replace the least recently used block (LRU) — the past pattern of references predicts future references.
• LRU can be a bad strategy for repeated scans of data, e.g., a nested-loops join (for each tuple of r, for each tuple of s …).
• A mixed strategy with hints from the query optimizer is preferable.

• Queries have well-defined access patterns (such as sequential scans), and a database system can use the information in a user's query to predict future references (slide 51).
• The nested loop of slide 51: for each tuple tr of r do / for each tuple ts of s do / if the tuples tr and ts match …
• The buffer manager can use statistical information regarding the probability that a request will reference a particular relation (slide 52).

• Keep data-dictionary blocks in the buffer (they are frequently accessed).
• Buffer managers support forced output of blocks for recovery.