Slide 7 - Data Storage - V2

Storage, Data Organization, and Buffering: Storage Technologies

• Key areas include storage technologies and memory hierarchy, non-volatile storage, page data access, row and column stores and buffer management.

Volatile vs. Non-Volatile Storage Media

• Volatile storage loses data when power is disconnected, while non-volatile retains data.
• Volatile storage uses byte-addressable access with retrieval of one byte or cache lines. Non-volatile storage uses page/block-addressable access. NVM is byte addressable storage.
• Volatile storage is faster with nano-second speeds, while non-volatile is slower at micro/milli-seconds.
• Volatile is more expensive, but smaller in capacity versus non-volatile. Examples include CPU registers, cache memory, and DRAM. Non-volatile examples are spinning hard disks, SSDs, NVM and PM.
• Volatile access is random and sequential, with the same read/write latency, while non-volatile Sequential access is typically faster.
• NVM read latency is 4x faster than write. SSD read latency is 12x faster than write, and HD has symmetric latency.

Various Storage Technologies

• Cache, DRAM, NVM, SSD, and HD.
• Cache has the fastest read and write latency at 1-15 ns. HD is slowest with 1-10 ms.
• CPU registers, L1, L2 and L3 also have different read latencies. L1 cache is 1ns, L2 is 5ns and L3 is 15ns.
• Cache and DRAM are volatile, while NVM, SSD and HD are non-volatile.
• All are byte addressable except SSD and HD, which use Block/Page addressing.
• Capacity increases from Cache (10's KB - 10's MB) to HD (TBs). DRAMS range from GBs-TBs and NVM/SSD support TBs.

Communication Overhead on Disk Storage

• Hard disks and Network Attached HD.
• Both use Milliseconds for access latency, but the Network Attached HD are 50s (Varies with size).
• Both are non-volatile and use Block/Page addressing and supports TBs.

Communication Overhead on Memory Storage

• DRAM and Network Attached DRAM uses nanoseconds and microseconds respectively. DRAM has 50ns and Network Attached DRAM is 10Ms.
• Volatility and addressability are the same, but DRAM bandwidth caps out in the GBs-TBs range, while Network Attached DRAM is TBs.

Memory Hierarchy

• Highest capacity is Archival Storage/tapes, then Network Storage, then Disk Storage and Solid-State Disks.
• Main Memory, Cache Memory and CPU registers are placed at the bottom. Price and Speed also increase from the top to the bottom.
• Archival, Network and Disk storage use page-oriented access while Solid-State Disks uses Non-Volatile access.
• Main and Cache memory use mini-block access using cache lines, while CPU registers use byte-oriented access.

Non-Volatile Storage: Spinning Hard Disks

• Spinning hard and solid-state drives use Disks and non-volatile storage. Volatile buffers are used, and access is page based.
• Seek time is the time to move heads and is around 10 ms.
• Rotational delay is the time to rotate around the spindle is around 10 ms.
• Transmission delay is to transfer a block of data at around 1ms.
• Each disk page has a disk block id.
• Block Read(disk block id) transmits the corresponding disk page from the disk to the memory buffers.
• Write(Block, disk block id) Transmits the data Block from the memory buffers into the disk page corresponding to the given disk block id.
• Disk Block Identifier gets mapped into Cylinder (or Track) Number, Platter Number, Sector Number.
• Retrieving disk page is dependent on on the current location of the disk head, and the location of the requested page. Involves mechanical movement and hence is relatively slow
• Seek Time has the Head move to the corresponding cylinder number, wait until head is on top of the correct Sector Number in Rotational Delay. Once head is at the right cylinder, right sector, direct and give the signal to the head responsible or the block's Platter Number is Transmission Time
• The Data Placement Problem involves placing data blocks on disk to minimize file read time using p platters, s sectors per track. One consideration is storing d₁ in Cylinder c₁, Platter p₁, Sector S₁
• The ideal data write pattern is d2→ C1, P2, S1 (Seek Time = 0, Rotational Delay = 0)
• Page prefetching retrieves pages before being requested, which may save time. It can be a wasted effort if the page is not requested.
• Good data placement will result in lower retrieval cost of a page.
• Multi-tenant databases can make data placement work difficult, because requests for pages from multiple files will be interleaved.

Non-Volatile Storage: Flash Memory and Solid-State Drives

• Examples of flash memory include ROM, PROM, EPROM, EEPROM and Flash Memory.
• Flash Memory is 1999 (Toshiba): based on EEPROM technology, uses gates to store bits or bubble memory. EEPROM (late 1970s, early 1980's- Hughes and Intel): Electrically Erasable Programmable Read-only Memory and is User-modifiable ROM

Solid-State Drive (SSD)

• NV storage that persists data on solid-state flash memory. Replace traditional hard disk drives (HDDs) in computers performing the same basic functions as a hard disk drives.
• SSDs do not have mechanical moving parts like HDDs. They are faster than HDDs.
• SSDs use NAND Flash memory to store data with non-volatile NAND transistors. They are arrayed and stacked on circuit boards called 3D NAND. Stacks provide higher storage capacities as memory cells are stacked.
• A Single-level cell or SLC are the most expensive, but most durable. Adding levels of cells increase the storage capacity but reduces reliability.
• SSD Controller communicate between NAND Flash and input/output interface.
• Manages all the flash memory cells by telling them what memory to access or manipulate, and guarantees data distribution and garbage collection.

Solid-State Drive Controller Behavior

• There is garbage generated due to not writing in-place when the old block becomes garbage and needs to be collected. The blocks read into memory and are updated.
• 2.5-Inch SATA SSD (Internal SSD) uses Serial Advanced Technology for Old interface for SSDs andHDDs also use the SATA standard. These are compatible with HDDs of the same size.
• M.2 SATA SSD (External SSD) is similar to the 2.5-Inch HDDs that also use the SATA standard and are built into USB Thumb drives.
• M.2 NVMe SSD (mainly, internal) uses Non-Volatile Memory Express using PCI Express bandwidth (PCIe) and not SATA bandwidth. The PCle is a common high-speed connection interface on the motherboard which achieves huge performance improvement.

Solid-State Drive Sequential Performance

• SATA SSDs provide up to 0.5 GB/s for sequential reads and writes and is the slowest of the three types
• NVMe Gen3 SSDs range between 1.5GB/s - 3.5 GB/s.
• With At this speed, CPU begin to bottleneck not the storage
• NVMe Gen4 SSDs achieve 5.5GB/s - 7GB/s for sequential reads and writes.

Solid-State Drive Durability

• The standard unit of measurement for the maximum number of reads and writes to non-contiguous storage locations or IOPS.
• Data is stored in blocks and blocks are composed of pages. Pages or blocks must be erased first. This erasure is performed at the Block level rather than the Page level.
• If a block is erased, we can write one page at a time as long as we are writing on a blank page that has not been written into before after the most recent block erase, meaning pages can be read independently.
• Block erase time is slow and to improve erase time, when you update a page, the old page in a block is marked outdated in order for the updated page to be written into a new page out of place in another block.
• Blocks are not durable because writting/erasing causes the SSD to wear. They get damaged over time after a certain number of erases or writes.
• Most SSDs come with integrated "wear-leveling" technology, to Evenly distribute the wear out extends lifespan of device with Error Correction Code page.
• In Solid-state drives, the Erasure is before each data write, and they are subject to wearing out because reads are faster than writes.

Solid-State Drive Access Types

• Implementations can be either Raw Flash which directly handle the NAND flash drive using in-memory write buffers to postpone batch write operations with Apply logging techniques to decrease number of random writes.
• Another is is Flash Translation Layer (FTL-based), a software driver in the SSD controller Enforces an out-of-place policy with use Logical address mapping that Addresses wear leveling, Reclaims free space with Managed bad blocks.

Solid-State Drive FTL Management

• Main functions of FTL or address mapping, wear leveling, garbage collection and bad block management,.
• FTL implements an out-of-place update policy because Flash cells cannot be updated in-place so old pages are marked as invalid while the updated version is written to a new location. There are three mapping methods of doing this. Page-level, block-level, and hybrid.
• FTL uses in-memory buffering to buffer page updates reducing the number of page writes which reduces block erases. The in-memory approach could result in loss of data due to volatility.
• Out-of-place updates also results in out-of-date/invalid flash pages which triggers Garbage Collection.
• FTL runs asynchronous garbage collector to recycle out-of-date pages.
• FTL's wear leveling avoids premature aging by distributing block erasures uniformly across all of SSD
• the FTL handles defective blocks marking them as defective with the data copied to other blocks.
• Flash supports multiple packages per channel, multiple dies per package, and multiple planes per die enabling Channel, Package, Die level and Plane Parallelism.

Maximum Terabytes Written (TBW)

• As data is written into SSDs and read, its effectiveness steadily decreases with age, which is quantified as Maximum Terabytes Written (TBW) of an SSD.

Hard Drives vs Solid State Drives

• HD uses spinning magnetic platters, while SSD uses flash memory.
• HD capacities are 250GB to 20TB, vs. SSD's 128GB to 8TB & 30TB to 100TB SSDs.
• Speed for HDs are way down at 500 MB/s, while SSDs are up to 7000 MB/s. SSD<25-33% HD in terms of power consumption.
• HDs have better long term storage, with external HDs are more portable than internal HDs, while SSD are less reliable for the long term with external SSDs are more portable than internal SSDs.
• HDds are cheaper, starting at 24 for 500GB, vs. 55 dollars for SSD, but SSD offer better perofmrance with fast data retrieval and constant use and not not ideal for long term storage.

Tables and Directories

• Pages of a table can be accessed if No indexes are available or There is a linked list of disk pages.
• A Directory table contains the Table name that corresponds with the Head of linked list of pages.
• Each page has forward and backward pointers using the disk page ids, offering Sequential access
• Maintaining a two-level hierarchy uses directory pages.

Row vs Column Stores Intro

• Table data is stored one tuple at a time or row adheres to the same schema. Adds and rewrites are easy.
• Relational databases are mainly stored in row-major storage, storing data in row order on the storage media, easy
• Suited for mostly transactional Workloads (OLTP)
• To compute select sum(salary) from Employee, will access all the data in the Employee table but will access only the salary attribute from each record and will Need to access more data than needed.
• Column stores are in column major order with dat of a certain attribute like salary stored together. They can be compressed and are Suited for mostly reads analytics workloads(OLAP).
• With Column stores, queries will only touch the relevant data like average sale, but when inserting a tuple, will need to touch many locations.

Row and Column Stores

• Tuple attributes (rows) are stored together in same block.

• Uses suitable in transactional processing specific to a tuple like increase Mary's salary by 5% .

• Attributes of Mary's name and salary will be contiguous in storage.

• Column stores can have columns of attributes are stored together in the same block, and suitable for analytical processing on certain columns can be quickly compute average salaries. All salary attributes of the entire table will be contiguous in storage (fast).

Tuples Types

• Tuples can be of 2 types: fixed or variable length for all tuples in a table.

Tuple Identifiers (TID)

• How to Refer to a Tuple in a Table as Tuple Identifier or a Record Identifier.
• Used to physically locate tuple Data page id (of the page that contains the tuple), or the index or offset.
• Used in Foreign-key/ primary-key to avoid performing joins.
• TIDs are used in the leaf level of an index like B-tree.
• It must uniquely identif and potentially not change if Tuple data is updated.

Data Page Layout

• Fixed Length: There is keeping track of empty slots or using a linked list so it should not change TID and do compaction which change the TID. This may involved having pointers to previous/next page with a linear slot search.

• Variable Length: There is directory of the pages, if tuple moves in the page, no change but in directory changes. But this will take space in memory.

Problems in Handling Tuple Space

• For inserting a new tuple? Use Free Space Pointer and Free Space Size with constant Update of pointer with Update of Table.
• Handling Gaps after tuples are deleted, requires gaps be inserted or re-relocation inside same directory.
• What to do if there is a lot of data with many tuples. Can create two level entries for data and what happens if to sequential check entire database.
• So what is better for Free Space? Keep directory for tracking.

Heap Data Structures

• Maintain two doubly-linked lists of pages in the table. A separate List for without Data and with Data. Then if Tuple N Data is to insert search page of N.

Storing Attribute Values

• Having a Store Tuple is related to have Fixed Length in which case attribute must be fixed. Then we need to locate the offset at all attribute like Name, Position and etc. Or if is page it is not a good plan.
• In this case will have to store Data inside catalog and do some other functions and code to help. This will be stored into System Catalog.
• Now a Variable we use offset array for length, if = 0 is null

Tables and Index

• The system catalog maintains data about table such as the directory of the page as well as if index or unique.
• What to do if Tuple in a sort? Physical in data changes of existing. And then to avoid change then insert with Linked List.
• Table can be Entire is inside an index?
• Hash take tuple to a location then is B data search for data there for keys. If page splits tuples do not change.
• Tables with join are considered as a cluster.

Organizing, and buffering: System catalogs stores meta data about the tables in the database.

• System catalogs stores meta-data about the tables in the database. For every table it stores the directory for data-pages composing, How it's stored and its Schema including fixed/variables, plus whether there are primary or unique keys. Some data will exist in the offset

System Catalog Tables themselves are stored in the System Catalogs.

• Stored are Index type, table views, user view, encrypted passwords for rights the rights to which tables.

Attributes_Catalog_Table( ) with the relation_name, attribute_name, attribute_type, attribute_order_in_table.

Buffer Management

• Buffer management in the DBMS different because access is pre predictive instead of LRU in OS.

• Most accesses goes to relational operators.

• Data must loaded into Data Store for memory queries to operate. Target to reduce between Data store memory(Buffer Manager) increasing buffer hist reducing buffer misses.

• Dirty bit, copy in the page or that data store and Pincount of data.

Functions of the Buffer Manager are in the buffer not in the Provide a empty store. Is is needed not if the and that and has 2 page or more. Buffer Replacement can be set not. If or is dirty clean up clean.