Title: Theory / Important / CS / Algo / Database / Database System Concept 6 - McGraw Hill+27{ / 3 Storage
Tags: examplesSwitchExample1 hasSeenConjDef récupéré

Question: Given some unit of storage, data storage system is characterized by
Answer: speed of access
Page: 429
Chapter: 10
Section: 1
Answer2: cost
Answer3: reliability

Name: Cache
Definition: fastest and most costly form of storage
Page: 429
Chapter: 10
Section: 1

Name: Main memory
Definition: The storage medium used for data that are available to be operated on. (I.e. without having to read them from disk)
Page: 429
Chapter: 10
Section: 1

Name: Flash memory
Definition: Non volatile
Page: 430
Chapter: 10
Section: 1
Definition2: Less expansive than main memory
Conjdef: A memory

Name: Magnetic-disk storage
Definition: long term storage,
Page: 430
Chapter: 10
Section: 1
Definition2: Less expansive than flash
Conjdef: A memory

Name: Optical storage
Definition: Data stored optically on a disk, read by a laser
Page: 430
Chapter: 10
Section: 1

Name: Tape storage
Definition: Memory mainly for backup and archival data
Page: 431
Chapter: 10
Section: 1
Definition2: Cheaper than disk
Conjdef: All of
Definition3: Much slower than disk

Name: Sequential access storage
Definition: A storage where the data must be read in some precise order
Page: 431
Chapter: 10
Section: 1

Name: Direct access storage
Definition: A storage where any data can be accessed quickly
Page: 431
Chapter: 10
Section: 1

Name: Primary storage
Definition: Fastest storage media
Page: 431
Chapter: 10
Section: 1
Example: Cache, main memory

Name: Secondary storage
Page: 431
Chapter: 10
Section: 1
Example: magnetic disk
Name2: Online storage

Name: A volatile storage
Definition: A storage loosing its content when the power to the device is removed
Page: 431
Chapter: 10
Section: 1

Name: A nonvolatile storage
Definition: A storage keeping its content when the power to the device is removed
Page: 431
Chapter: 10
Section: 1

Name: Tertiary storage
Definition: Least expensive, least powerful, and cheapest media storage
Page: 431
Chapter: 10
Section: 1
Example: magnetic tape
Name2: offline storage
Example2: optical-disk jukeboxes

Name: Volatile storage
Definition: Storage losing its content when electricy is removed
Page: 431
Chapter: 10
Section: 1

Name: Platter
Definition: usually from 50 to 10 k tracks.
Page: 433
Chapter: 10
Section: 2

Name: Arm
Definition: What moves each read-write head
Page: 433
Chapter: 10
Section: 2
Context: Hard drive

Name: Arm assembly
Page: 433
Chapter: 10
Section: 2
Context: Hard drive

Name: Cylinder
Definition: A set of track at the same position on each disk
Page: 433
Chapter: 10
Section: 2
Context: Hard drive

Name: Read-write head
Definition: stores information on a sector magnetically as reversals
of the direction of magnetization of the magnetic material.
Page: 433
Chapter: 10
Section: 2
Context: Hard drive

Name: Rotation
Page: 433
Chapter: 10
Section: 2
Context: Hard drive

Name: Sector
Definition: smallest unit of information that can be read from or written to the disk
Page: 433
Chapter: 10
Section: 2
Context: Hard drive
Definition2: Usually 512 bytes

Name: Spindle
Page: 433
Chapter: 10
Section: 2

Name: Tracks
Definition: A set of sectors
Page: 433
Chapter: 10
Section: 2

Question: The number of platter by disk is
Answer: Usually from 1 to 10
Page: 433
Chapter: 10
Section: 2

Question: What happen if a read-write head touch a disk
Answer: The data of the disk is erased
Page: 433
Chapter: 10
Section: 2

Name: A disk controller
Definition: interfaces between the computer system and the actual hardware of the disk drive. In the disk drive unit
Page: 434
Chapter: 10
Section: 2

Name: Checksum
Definition: The result of a function, applied to some data. Allowing to check whether a data has been corrupted between writting it and reading it
Page: 434
Chapter: 10
Section: 2
Context: Disk

Name: Remapping of bad sectors
Definition: The fact that, if a sector is corrupted (detected at formatting or writting), then another sector is used when this broken sector is called
Page: 434
Chapter: 10
Section: 2
Context: Disk

Name: serial ATA
Page: 434
Chapter: 10
Section: 2
Context: Disk
Abbreviation: SATA
Typ: An interface for connecting disks to computers

Name: Parallel ATA
Page: 434
Chapter: 10
Section: 2
Context: Disk
Abbreviation: PATA
DefType: An interface for connecting disks to computers

Name: Serial attached SCCI
Page: 434
Chapter: 10
Section: 2
Context: Disk
Abbreviation: SAS
DefType: An interface for connecting disks to computers

Name: small-computer-system interconnect
Typ: An interface for connecting disks to computers
Page: 434
Section: 2
Chapter: 10
Denoted by: SCSI
Context: Disk

Name: storage area network
Definition: large numbers of disks are connected by a high-speed network to a number of server computers
Page: 434
Chapter: 10
Section: 2
Context: Disk
Abbreviation: SAN

Name: redundant arrays of independent disks
Definition: Give the server a logical view of a very large and very reliade disk, using multiple ones
Page: 435
Chapter: 10
Section: 2
Context: Disk
Abbreviation: RAID

Name: Network attached storage
Definition: provides a file system interface using networked file system protocols such as NFS or CIFS
Page: 435
Chapter: 10
Section: 2
Context: Disk
Abbreviation: NAS

Name: RAID0
Definition: Raid which split data evenly accross two or more disks, without redundancy nor fault tolerance
Page: https://en.wikipedia.org/wiki/Standard_RAID_levels
Name2: stripe set
Name3: striped volume

Name: RAID1
Definition: Having multiple disks which are each exact copy of the other. It offers no more space than a single disk, and no speed improval
Page: https://en.wikipedia.org/wiki/Standard_RAID_levels

Name: RAID2
Definition: Sprites data at bit level and use Hamming code for error correction. Does not allow multiple access, but increase speed when access is done to a single location.
Page: https://en.wikipedia.org/wiki/Standard_RAID_levels
Context: RAID
Extra: Not used anymore in practice

Name: RAID3
Definition: Stripes data at byte level and a parity disk. Does not allow multiple access, but increase speed for access in a single location. Not used anymore.
Page: https://en.wikipedia.org/wiki/Standard_RAID_levels

Name: RAID4
Definition: Sprites data at block level and a parity disk. Good performance of random read, bad for random write because each write needs access to parity disk
Page: https://en.wikipedia.org/wiki/Standard_RAID_levels

Name: RAID5
Definition: block-level striping. With \(n\) disks of size \(s\), it has \(s*(n-1)\) space. Each disks are divided into \(n\) parts, and the \(i\)-th disk contains the parity bit of all \(i\)-th parts
Page: https://en.wikipedia.org/wiki/Standard_RAID_levels

Name: RAID6
Definition: Any form of raid allowing to read data even with 2 disks failures
Page: https://en.wikipedia.org/wiki/Standard_RAID_levels

Name: Access time
Definition: time from when a read or write request is issued to when
data transfer begins
Page: 435
Chapter: 10
Section: 2.2

Name: Accessing data
Definition: reading or writting data
Page: 435
Chapter: 10
Section: 2.2

Name: seek time
Definition: Time to reposition the arm
Page: 435
Chapter: 10
Section: 2.2
Context: hard drive
Intuition: 2 to 30 milliseconds

Name: average seek time
Definition: average of the seek times, measured over a
sequence of (uniformly distributed) random requests
Page: 435
Chapter: 10
Section: 2.2
Context: hard drive
Intuition: one third of worst-case seek time

Name: rotational latency
time
Definition: the time spent waiting for the
sector to be accessed to appear under the head (after head has reached the desired track)
Page: 435
Chapter: 10
Section: 2.2
Context: hard drive
Intuition: 90 to 250 rotations per second

Name: average latency
time
Definition: average of the rotational latency times, measured over a sequence of (uniformly distributed) random requests
Page: 435
Chapter: 10
Section: 2.2
Context: hard drive
Extra: "rotational" is not in the name for some reason. Check?

Name: Data-transfer rate
Definition: the rate at which data can be retrieved from or stored to the disk.
Page: 435
Chapter: 10
Section: 2.2
Context: hard drive

Name: Mean time to failure
Definition: the amount of time that, on average, we can expect the
system to run continuously without any failure
Page: 435
Chapter: 10
Section: 2.2
Context: hard drive
Abbreviation: MTTF

Name: Block
Definition: a logical unit consisting of a fixed number of contiguous sectors
Page: 435, 451
Chapter: 10
Section: 2.3
Context: hard drive

Name: Page
Definition: same as block in HDD
Page: 435
Chapter: 10
Section: 2.3
Context: hard drive
Definition2: some other form of unit of memory for flash drive

Name: Sequential access pattern
Definition: successive requests are for successive block numbers, which are on the same track, or on
adjacent tracks
Page: 435
Chapter: 10
Section: 2.3
Context: hard drive

Name: Random access pattern
Definition: successive requests are for blocks
that are randomly located on disk
Page: 435
Chapter: 10
Section: 2.3
Context: hard drive

Name: Buffering
Definition: Blocks that are read from disk are stored temporarily in an in-memory buffer, to satisfy future requests
Page: 437
Chapter: 10
Section: 2.3
Context: hard drive

Name: Read-ahead
Definition: When a disk block is accessed, consecutive blocks from the same
track are read into an in-memory buffer even if there is no pending request
for the blocks
Page: 437
Chapter: 10
Section: 2.3
Context: hard drive
Intuition: In the case of sequential access, such read-ahead ensures that
many blocks are already in memory when they are requested, and minimizes the time wasted in disk seeks and rotational latency per block read.

Name: Scheduling
Definition: Deciding to access data in an order distinct from the request order to optimize average latency
Page: 437
Chapter: 10
Section: 2.3
Context: hard drive

Name: Disk-arm scheduling
Definition: A scheduling algorithm based on the disk arm position principally
Page: 437
Chapter: 10
Section: 2.3
Context: hard drive

Page: 437
Implementation: The arm move in the same direction as long as they are request justifying it, and change direction only once it can satisfy no more request without changing its direction
Section: 2.3
Chapter: 10
Name: elevator algorithm
Context: hard drive
Typ: Disk-arm scheduling
Intuition: an elevator goes as high as it is asked to go, no higher, and do not halt to go down until it is as high as possible. Then he goes down following the same logic

Name: an extent
Definition: Multiple consecutive blocks allocated to a single file
Page: 438
Chapter: 10
Section: 2.3
Context: hard drive, File organization

Name: A fragmented file
Definition: A file saved on non-consecutive blocks
Page: 438
Chapter: 10
Section: 2.3
Context: hard drive, File organization

Name: Nonvolatile write buffer
Definition: A buffer that do not loose memory in case of error, in which you can enqueue everything that will need to be written, and write it in disk when it's more efficient
Page: 438
Chapter: 10
Section: 2.3
Context: hard drive, File organization

Name: Nonvolatile random-access memory
Definition: Some RAM that do not loose memory when the system turn off
Page: 438
Chapter: 10
Section: 2.3
Context: hard drive, File organization
Abbreviation: NVRAM

Name: Log disk
Definition: A disk on which you write sequentially all write instruction. Actually executing the write instruction alter, when relevant.
Page: 439
Chapter: 10
Section: 2.3
Context: hard drive, File organization
Intuition: The log are consecutive write, so quite faster than random access write

Name: Journaling file system
Definition: File systems that support log disk
Page: 439
Chapter: 10
Section: 2.3
Context: hard drive, File organization

Question: Techniques to improve the speed of access to blocks
Answer: Buffering.
Page: 439
Chapter: 10
Section: 2.3
Context: hard drive
Answer2: Read-ahead.
Answer3: Scheduling.
Answer4: File organization
Answer5: Nonvolatile write buffers
Answer6: Log disk

Name: erase block
Definition: A block of data that can be erased together
Page: 440
Chapter: 10
Section: 2.3
Context: flash drive

Name: translation table
Definition: A table that maps logical page to physical page
Page: 440
Chapter: 10
Section: 2.3
Context: flash drive

Question: How does a flash drive write to a block b
Answer: It find the physical page p associated to the logical block b
It read the page content c of b,
It do the change in c, leading to c'
It write c' in a free physical page p'
It update the translation table to state that b goes to p'
it marks p as being free
Page: 440
Chapter: 10
Section: 2.3
Context: flash drive

Name: Cold data
Definition: Data that are rarely updated
Page: 440
Chapter: 10
Section: 2.3
Context: flash drive

Name: Hot data
Definition: Data that are often updated
Page: 440
Chapter: 10
Section: 2.3
Context: flash drive

Name: wear leveling
Definition: Principles of evenly distributing ease operations across physical blocks
Page: 440
Chapter: 10
Section: 2.3
Context: flash drive

Name: flash translation layer
Definition: System translating flash drive to let be used the same way as a hard drive
Page: 440
Chapter: 10
Section: 2.3
Context: flash drive

Name: Hybrid disk drive
Definition: hard-disk systems that combine magnetic storage
with a smaller amount of flash memory, which is used as a cache for frequently accessed data
Page: 440
Chapter: 10
Section: 2.3
Context: flash drive

Name: Redundancy
Definition: Extra data that serves to avoid loss in case of failure of a disk
Page: 441
Chapter: 10
Section: 3.1
Context: data storage
Example: Mirrorring

Name: Mirroring
Definition: Making multiple copy of data on multiple disk
Page: 441
Chapter: 10
Section: 3.1
Context: data storage
Name2: Shadowing

Name: stripping data
Definition: Splitting a file across multiple disk
Page: 442
Chapter: 10
Section: 3.1
Context: data storage
Intuition: faster access, as each disk can read in parallel

Name: bit-level stripping
Definition: Splitting a file at the bit-level. For each byte, the first bit in disk 0, second on disk 1 and so on
Page: 442
Chapter: 10
Section: 3.1
Context: data storage

Name: block-level stripping
Definition: Splitting a file at the block-level
Page: 442
Chapter: 10
Section: 3.1
Context: data storage
Counterexample: database where a row/column is always saved in the same disk

Question: What to take into consideration to choose a raid level
Answer: Monetary cost of extra disk-storage requirements.
Page: 447
Chapter: 10
Section: 3.
Context: data storage
Answer2: Performance requirements in terms of number of I/O operations.
Answer3: Performance when a disk has failed.
Answer4: Performance during rebuild (that is, while the data in a failed disk are being  rebuilt on a new disk).

Name: Rebuild performance
Definition: The performance of the database while RAID is being rebuilt
Page: 447
Chapter: 10
Section: 3.
Context: RAID

Name: Software RAID
Definition: A RAID implementation requiring no hardware change
Page: 448
Chapter: 10
Section: 3.5
Context: RAID

Name: Hardware RAID
Definition: A RAID implementation using a specialized hardware
Page: 448
Chapter: 10
Section: 3.5
Context: RAID

Name: latent failure
Definition: Failing to read data that was properly written
Page: 448
Chapter: 10
Section: 3.5
Context: RAID
Name2: bit rot

Name: Scrubbing
Definition: when disks are idle, every sector of every disk
is read, and if any sector is found to be unreadable, the data are recovered from
the remaining disks in the RAID organization, and the sector is written back
Page: 448
Chapter: 10
Section: 3.5
Context: RAID

Name: Hot swapping
Definition: Replacing a disk by another one without having to turn off the machine
Page: 449
Chapter: 10
Section: 3.5
Context: RAID

Name: Jukeboxe
Definition: devices that store a large number of optical disks (up to several
hundred) and load them automatically on demand to one of a small number of
drives (usually 1 to 10)
Page: 450
Chapter: 10
Section: 3.5
Context: data storage

Question: How to store data that don't fit in a single memory block (e.g. image)
Answer: Store this data separately (as a file) and store in a database a pointer to the data
Page: 452
Chapter: 10
Section: 5
Context: database storage

Question: Usual assumption about record in memory
Answer: Each record is saved in a unique block
Page: 452
Chapter: 10
Section: 5
Context: database storage

Question: Let's assume each record has size S. What are the issues if you save the i-th record at position \(i\times S\)
Answer: Some record will cross block
Page: 452
Chapter: 10
Section: 5
Context: database storage
Answer2: It becomes hard to delete data

Question: How to avoid record crossing block
Answer: Allow only \(\frac{\text{record size}}{\text{block size}}\) record by block
Page: 452
Chapter: 10
Section: 5
Context: database storage

Question: Assume the i-th record is saved at position \(i\times{\text{record size}}\).
How to deal with deleting record
Answer: Move last record in place of the deleted record
Page: 452
Chapter: 10
Section: 5
Context: database storage
Answer2: keep a list of deleted record and use this space to insert new record

Question: When can records have different size in a file
Answer: Storage of multiple record types in a file.
Page: 454
Chapter: 10
Section: 5
Context: database storage
Answer2: Record types that allow variable lengths for one or more fields.
Answer3: Record types that allow repeating fields, such as arrays or multisets.

Name: null bitmap
Definition: a bitmap of the columns whose value is null
Page: 456
Chapter: 10
Section: 5
Context: database storage

Name: slotted page structure
Definition: Encoding of variable length data, where each entry has a pointer to its block, and the block header give a pointer to the actual location in the block. In each block, all record are saved one after the other, indepandently of its size
Page: 456
Chapter: 10
Section: 5
Context: database storage

Question: Classical organization of records in a file
Answer: Heap file organization
Page: 456
Chapter: 10
Section: 6
Context: database storage
Answer2: sequential file organization
Answer3: Hashing file organization

Name: heap file organization
Definition: Any record can be placed anywhere in the file where
there is space for the record. There is no ordering of records. Typically, there
is a single file for each relation.
Page: 456
Chapter: 10
Section: 6
Context: database storage

Name: Sequential file organization
Definition: Records are stored in sequential order, according to the value of a “search key” of each record. Each record have a pointer to the next. Regularly they get reorganized so that they are in order in the file
Page: 456
Chapter: 10
Section: 6
Context: database storage

Name: Hashing file organization
Definition: A hash function is computed on some attribute
of each record. The result of the hash function specifies in which block of the file the record should be placed
Page: 456
Chapter: 10
Section: 6
Context: database storage

Name: multitable clustering file organization
Definition: records of several different relations
are stored in the same file; further, related records of the different relations are
stored on the same block
Page: 456, 461
Chapter: 10
Section: 6
Context: database storage

Name: Search key
Typ: any attribute or set of attributes
Page: 458
Section: 6.1
Chapter: 10
Context: database