​

Systems Primer

Bits to disks to clouds

Why? ‘Full stack’ engineer?

​

Key Questions

​

​

​

1. Why a rich variety of DBs?
2. How to eval DBs for my data apps?

​

​

​

Goal: Gain intuition – What are Speed and Cost tradeoffs?

​

​

Basics

​

​

​

Basics

• INT32: 4 bytes, INT64: 8 bytes
• 2^10 = 1024, 2^20 ~= 1Million, 2^30 ~= 1 Billion (10^9), 2^40 ~= 1 Trillion (10^12)
• To store int32 records: 1 Million records = 4MB, 1 Billion records = 4 GB
• [Often use 1000 vs 1024, for quick approximations]

RAM – SSD/HDD Read/Writes

​

(aka ‘Paging’)

CPU – RAM Read/Writes

Bytes in RAM, SSDs, HDDs

IO

Systems

​

D-RAM

S-RAM

Hard Drives (HDD)

Flash/SSD/

Non-volatile mem (nvm)

Tape

L1, L2

Cache

MBs, 20 ns

GBs, 50-100 ns

1-10 TBs,

~10s microsecs

10s of TBs-PBs, 10s of msecs

Cost/bit

Speed

Volatile -- data lost when you turn off power

Non-Volatile

IO Blocks

For Efficiency

​

​

​

E.g., to store 1GB data, we partition the data, and store in IO Blocks

Data

(1 GB)

IO Blocks

‘Partition’ into IO blocks

IO Blocks

For Efficiency

​

​

​

Key Concepts

1. Data is stored in Blocks (aka “partitions”)
2. Sequential IO is 10x-100x+ faster than ‘many’ random IO
• E.g., 1 MB (located sequentially) versus 1 Million bytes in random locations
3. HDDs/SSDs copy sequential ‘big’ blocks of bytes to/from RAM

1 Package

1000 Packages

(1 Trailer)

3000 Packages

(3 Trailers)

‘M’ Trucks

​

1 Byte

64MB-Blocks

​

(64MBs of sequential, aka contiguous bytes

​

Nx64MB-Blocks

​

(‘N’ sequential 64MB-Blocks)

​

Set of ‘M’

Nx64MB-Blocks

​

IO Blocks

For Efficiency

​

​

​

E.g., to store 1GB data, we need 15.625 64MB-Blocks (= 1GB/64MB) in

• Sixteen 64MB-Blocks, (1x64MB = 64MB) OR
• Eight 2x64MB Blocks, (i.e, M = 8, N = 2), OR
• Four 4x64MB Blocks, OR Two 8x64MB Blocks, OR One 16x64B Block
• (OR some combo)

2x64MB

4x64MB

Data

(1 GB)

IO Blocks

Read,

Write

​

IO Blocks

​

​

​

Data stored in ‘M’

Nx64MB Blocks

// Read M Nx64MB-Blocks for Data

ReadData(M) For i:1…M Blocks

• ReadBlocks(startLocation[ith Block], N)

Read/Write Data into RAM

// Read N contiguous Blocks from startLocation

ReadBlocks(startLocation, N Blocks)

1. Access Block’s startLocation in IO device
2. Scan N Blocks in one efficient operation. That is
• Read N*64MB (or multiple) contiguous bytes to RAM

WriteBlocks is similar to ReadBlocks, except

2b. Write N*64MB (or multiple) contiguous bytes from RAM

​

Basic system numbers

​

​

​

Access Latency (secs) = Time to access Block’s start location

Scan Throughput (GB/sec) = Speed to Scan + Copy data to RAM

Note: Why are they different speeds?

• Digital (e.g. SSDs and RAM) vs Analog (e.g. HDD seeks)
• Distance from CPU (e.g. RAM is on same chip as CPU vs SSD)

IO Cost Model

​

​

​

100 + 64MB/100GB/s

= 100 + 640000 nsec

10 + 12800 microsec

10 + 640 millisec

1 + 12800 microsec

Total Time to ReadData =

AccessLatency * M + DataSize/ScanThroughput

​

Where

• DataSize = data size (in bytes)
• M = Number of non-contiguous Blocks
• AccessLatency = Time to access Block
• ScanThroughput = Speed to copy/scan to RAM

​

Example

​

Data size

​

​

​

Q1: What’s row size (i.e., size of each record)?

SID: int32 ⇒ 4 bytes

Student: char[100] ⇒ 100 bytes

Address: char[200] ⇒ 200 bytes

Bio: char[720] ⇒ 720 bytes ## Note: Picking so row size=1024

​

⇒ Each row is 1024 bytes

​

Q2: What’s table size

1. with 1000 student rows? 1000 * 1024 bytes = 1 MB
2. with 1M student rows? 1M * 1024 bytes = 1 GB
3. With 1B student rows? 1B * 1024 bytes = 1 TB

​

Example

​

Data speed

​

​

​

Q3: For 1 Billion student table of size 1TBs (stored in M=1)

​

[Recall Total Time to ReadData =

AccessLatency * M + DataSize/ScanThroughput ]

​

Example

​

Data speed

​

​

​

Q4: With 100 parallel machines? (100x RAM, 100x disks)

​

Example: Find a student, by scanning data

Find ‘Daffy’ from a DB of billion students (1 TB)

Design Choices

​

Storage Cost

​

Time

​

(AccessLatency) 10 msec * 1 Billion rows + (Scan) 1 TB /100 MBps

= 10^7 secs + 10^4 secs

~= 115 days

Number of 64MB-blocks = 1 TB/64MB = 15625

​

(AccessLatency) 10 msecs *15625 blocks + (Scan) 1 TB /100 MB-sec

= 10.15^4 secs ~= 3 hrs

In 2 weeks, we’ll see how to do this a lot faster (in msecs) with good Indexes (e.g, hashing)

Design1

Design2

Design3

Example: Find a student, by scanning data

Find ‘Daffy’ from a DB of billion students (1 TB)

Design Choices

​

Storage Cost

​

Time

​

(AccessLatency) 10 microsec * 1 Billion rows + (Scan) 1 TB /5GBps

= 10^4 secs + 200 secs

~= 1200 secs

Number of 64MB-blocks = 1 TB/64MB = 15625

​

(AccessLatency) 10 microsecs *15625 blocks + (Scan) 1 TB /5 GBps

= 10.15^4 secs

~= 200 secs

In 2 weeks, we’ll see how to do this a lot faster (in msecs) with good Indexes (e.g, hashing)

Design4

Design5

Clouds of machines

​

(Example datacenter

from 2:50 min)

​

​

​

Cloud DBs

​

[Optional]

​

​

​

​

​

Reference Snowflake [Jun’22]

(Google for full pricing calculators for BigQuery, RedShift, etc.)

Rough rule of thumb for data sizes

Ballpark Cloud DB costs

(*For popular Tables data.

Some apps use JSON (hierarchical data) in

nonSQL DBs – see later)

‘10-100x’ Lower costs in past 10 yrs.

Primary Driver? “db admin” team → Cloud management tools

​

In this Section

​

​

• Systems – Size, Cost, and Speeds of GB/TBs
• On RAM, HDDs/SSDs, clouds

​

• IO Cost model
• Simple IO model for Total Time (for RAM, SSD, HDD)
• Good estimate – Reality is a bit more complex to fully model (buses, cache hit rates, etc.)

​

​

• Examples analyzing system design choices

​

​

​