Towards Flash-based Enterprise Databases

Sep. 22nd, 2008
Sang-Won Lee
Sungkyunkwan University,
University Korea

Toward Flash-based Enterprise Databases

1

SKKU VLDB Lab.

SKKU VLDB Lab.


Research Directions−

Vision: “Flash is disk, disk is tape, and tape is dead.”(by Jim
Gray)

−

Strategy: “Do only what only you can do.”(by E. W. Dijkstra)−

Research Goal: “Database systems on flash memory” pioneer

Recent Achievements−

FAST: One of the most efficient FTL mechanisms (ACM
Transactions on Embedded Computing Systems, 2007)−

IPL: An innovative database storage scheme on flash memory(ACM SIGMOD 2007)−

A Case for Flash Memory SSD in Enterprise Database
Applications (ACM SIGMOD 2008)

Toward Flash-based Enterprise Databases

2

SKKU VLDB Lab.

Flash-based
Flash based Database Research: Motivations

Toward Flash-based Enterprise Databases

3

SKKU VLDB Lab.

Real Motivations

SCI, SCI, SCI, …

Toward Flash-based Enterprise Databases

4

SKKU VLDB Lab.

The VERY Real Motivations


Rule of the game in storage market is changing

Hardware: Dr.
Dr Masuoka,
Masuoka Samsung,Samsung Toshiba
Toshiba, ..

Hwang’s Law vs. Moore’s Law



SW: OS, File System, FTL, DBMS, …

Toward Flash-based Enterprise Databases

5

SKKU VLDB Lab.

Flash Memory Market


Mobile phone, digital camera, iPod, MP3 etc ( 1 ~ 10 G)−

PC, Laptop : over 10G−

Flash already wins over harddisk

2008: the war begins

Enterprise server storage: 100G ~ 100T−2009 ~ 2010?

−

In my opinion, flash is more attractive in enterprise rather thanPC / Labtop market

Toward Flash-based Enterprise Databases

6

SKKU VLDB Lab.

Flash Memory Solid State Disk (SSD)

Provides a block
block-device
device interface identical to a hard disk, butuses flash memory as a storage medium
50 years championhiVSA new challenger!

Identical
Interface

Toward Flash-based Enterprise Databases

7

SKKU VLDB Lab.

A Quick Intro to Flash Memory

Flash Organization

Toward Flash-based Enterprise Databases

9

SKKU VLDB Lab.

Flash Performance: Chip Level

Flash characteristics−

Erase-before-write ( No in-place update)−

Asymmetric read/write speed−

No mechanical latencyyToward Flash-based Enterprise Databases

10

SKKU VLDB Lab.

Sequential Append-only Writes
vs. Random
R dOverwrites
Oit

E.g. 2K page write: new write vs. overwrite in a naïve way

Data Blocks:
block mapping

Free Blocks

Toward Flash-based Enterprise Databases11

New write: 0.2ms

Overwrite−

63 2K-reads = 6.3ms

−

63 2K
2K-writes
it = 1212.6ms6−

1 2K-write = 0.2ms−

1 erase = 1.5ms−

Total = 20.6ms

SKKU VLDB Lab.

Flash Performance: SSD Level(Source: Jim Gray’s slide)

Toward Flash-based Enterprise Databases

12

SKKU VLDB Lab.

NAND FlashSSD Architecture

Toward Flash-based Enterprise Databases

13

SKKU VLDB Lab.

Flash Translation Layer ( FTL )

A software layer that makes flash memory appear to thesystem like a disk drive−

Address mapping:pp g logicalgsector <-> pphysicalysector−Garbage collection−

Power-offPower
off recovery−

Wear leveling and bad block management−….

Toward Flash-based Enterprise Databases

14

SKKU VLDB Lab.

Flash SSD Block Diagram

e.g. Samsung SSD – somewhat old model

Pata/
Sata/
Scsi/
….

More
Powerful
CPU,
Bi
BiggerSDRAM

Toward Flash-based Enterprise Databases

Parallelism /Interleaving
for Large Bandwidth
15

SKKU VLDB Lab.

Opportunities in FlashFlash-based
based DBMS ResearchFlash-aware DBMS
(Storage, Indexing,
Buffer Mgmt.,
Query Processing … )Flash-aware
Applications

Flash-aware OSs/File Systems/Device Drivers

FTL
Flash Chips(SLC, MLC)

Toward Flash-based Enterprise Databases

16

SKKU VLDB Lab.

FAST:A Log Buffer based Flash Translation Layer
using Fully Associative Sector Translation

Sang-Won Lee, et al.
ACM Transactions
Tti
on Embedded
E b dd d C
Computingti S
Systems,t
July 2007

Seoul National University FTL:
H b id Mapping
HybridMi

Toward Flash-based Enterprise Databases

18

SKKU VLDB Lab.

Seoul National University FTL:
H b id Mapping
HybridMiData Blocks

Every 2K writes can be bufferedin 0.2 ms, not in 20.6 msWhen a llog blWhblock
k iis ffull,ll iit should
h ld
be merged−“Merge” operation

Free Blocks
Log Buffer Blocks:“W it buffers”“Writeb ff ”


based on “Locality”
Locality and “Log
Log Structured File System
System” idea

Toward Flash-based Enterprise Databases

19

SKKU VLDB Lab.

Associativity in CPU Cache
Directed mapping
Block
No.

vs. Fully associative mapping
0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7

Block
N
No.

Cache

Mapping =(Block No.) mod(# of Blocks in Cache)

A Block can be placed
anywhere in the cache

MemoryBlock 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3NoNo.

(a) Associativity between memory and CPU cache

Toward Flash-based Enterprise Databases

20

SKKU VLDB Lab.

SNU FTL = BAST

BAST: Block Associative Sector Translation
0
1
2
3

Flash
Memoryy2

Original Data Blocks

Log Blocks =Cache for Writes(b) Log blocks: a cache for write operations
Sectors from one logical block
can be mapped only to one log block
0
1
2
3

3
1
0
1

Original Data Blocks

Log Blocks

Flash
Memory(c) Block associativity in log block scheme
Toward Flash-based Enterprise Databases

21

SKKU VLDB Lab.

Disadvantages of BAST

Data Blocks

What if there are many hot
blocks?
1.

Choose one victim log blocks

2.

Merge the victim block3.

Assign a new log block for the
new hot block

Free Blocks
Log Buffer Blocks:“Write buffers”

Toward Flash-based Enterprise Databases

22

SKKU VLDB Lab.

Disadvantages of BAST(2)

Low space utilization of victim blocks
Log block thrashingLoog block uttilization(%)

−

100
80
A
B
C

60
40
20
0
4

8

Toward Flash-based Enterprise Databases

1632# of Log blocks

23

64

SKKU VLDB Lab.

FAST


What if we take “Fully
Fully Associative Sector Translation
Translation” in log
buffer blocks?

Sectors from one logical block
can be mapped to any log block0

Flash
Memory1
23

Original Data Blocks

1
3
0
1

Log Blocks(d) Fully associativity b/w
logical sectors and log blocks

Toward Flash-based Enterprise Databases

24

SKKU VLDB Lab.

Sector Writes and Reads in FAST
Sectors from one logical block
can be mapped to any log block

Block
Mapping
Table

Flash
MemorySectorMapping
Table

Original Data Blocks

Log Blocks

Sector (over-)write−

Append the write sector in log blocks−

If theth logl blocks
bl k are ffull,ll1.

Merge a log block in FIFO manner2.

Get a free block and make it a new log block

Sector read−

Search the sector mapping table for the most recent sector−

If not found,found visit the original data blocks via block mapping table

Toward Flash-based Enterprise Databases

25

SKKU VLDB Lab.

Erase Count

Performance Evaluation
250000200000150000100000
50000
0
4

8

16

32

bas t
fas t
o-fas tDigital
Camera

bas t
f t
fas
o-fas t

LINUX

64

Eras
se Count# of Log blocks

20000
10000
0
4

8

16

32

64

# of Log blocks

Toward Flash-based Enterprise Databases

26

SKKU VLDB Lab.

Era
ase Count

Performance Evaluation(2)
25000
20000
15000
10000
5000
0

bas t
fas t
o-fas t
4

8

16

32

Symbian64

Eras e Count# of Log blocks

300000bas t
fas t
o-fas t200000100000RANDOM

0
4

8

16

32

64

# of Log blocks

Toward Flash-based Enterprise Databases

27

SKKU VLDB Lab.

DesignDi off Flash-Based
Fl h Bd DBMSDBMS:
An In-Page Logging Approach
SIGMOD 2007
Sang-Won Lee,g Moon ((Univ. of Arizona))
BongkiTraditional DBMS on Flash Memory: Problem
(FTL) + pure disk-based DBMS – traditional in-place update
Because of no update-in-place characteristics, most block write
results in a copy-back operation (> 20ms)−

SQL: Update / Insert / Delete
UpdateBufferMgr.

Page : 4KB
Block : 128KB
Dirty Block Write

Flash
MemoryData Block Area
Toward Flash-based Enterprise Databases

29

SKKU VLDB Lab.

In-pageInpage Logging: Basic Ideas

Traditional
In-Place Updatep* No in-place update
Log-Structured
Approach* No
N mechanicalh i l llatencyt* Fast Read Speed
In-Page Logging
Approach

Toward Flash-based Enterprise Databases

30

SKKU VLDB Lab.

In-pageInpage Logging: Basic Ideas(2)Database update and log in traditional DBMS architecture
SQL

Bufferpi

Log Buffer

pj

DB

LOG

pi
pj

Toward Flash-based Enterprise Databases

31

SKKU VLDB Lab.

In-pageInpage Logging: Basic Ideas(3)Write performance: 100x faster in best case
Update / Insert / Delete

update-in-place

Sector : 512B

physio-logical log

Page : 4KB

BufferMgr.
gBlock : 128KB

 1 sector write= 200 us

Flash
MemoryData Block Area
Toward Flash-based Enterprise Databases

32

SKKU VLDB Lab.

In-pageInpage Logging: Basic Ideas(4)


Read
−

When a page Pi is read in after replace-out
Re-apply the “physiological action”
against the original copy
(CPU overhead!)Pi
BufferMgr
Mgr.

Re-constructmost up-to-datein-memory copy
Read
 Original copy of Pi
 All log sectors in the flash block(IO overhead)
15 pages:

Flash
MemoryCriticisms: 2x slow read speed
 It still may
y be fast enoughg

log area (8K):
16 sectors
Toward Flash-based Enterprise Databases

 Locality of updates

33

SKKU VLDB Lab.

In-pageInpage Logging: Basic Ideas(5)Merge operation: new internal operation in IPL

up-to-date
15 data pages

Merge

A Physical
Flash
Block

log area (8K):
16 sectors

clean log area

Bold



Bnew

Merge policies: eager vs. lazy merge−

Refer to paper

Toward Flash-based Enterprise Databases

34

SKKU VLDB Lab.

IPL Simulation with TPC-C
TPC CPerformance trend with varying buffer sizes (1G.100u, 8KB
log area)

Toward Flash-based Enterprise Databases

35

SKKU VLDB Lab.

In-pageInpage Logging: The Unexplored Beauty
Traditional
In Place Update
In-Place* No in-place update
Log-Structured
Approach* No mechanical latency* Fast Read Speed
In-Page Logging
Approach* RedoRedo-based
based Log
New Recovery & CCpp
Approach
Toward Flash-based Enterprise Databases

36

SKKU VLDB Lab.

A Case for Flash Memory SSD
in Enterprise Database Applications

SIGMOD 2008
Sang-Won Lee, Bongki Moon, Chanik Park,
Jae-Myung
Jae
Myung Kim,
Kim Sang-Woo
Sang Woo Kim

Toward Flash-based Enterprise Databases

37

SKKU VLDB Lab.

Major I/Os in Database
SQL

Log Buffer
Buffer Cache

Data File

Access pattern: random Next challenge

Temporary

Undo(Rollback)

Tablespace

Data

Redo Log

Access pattern: “Append-only sequential writes, thenrandomdreads”d ”

Toward Flash-based Enterprise Databases

38

SKKU VLDB Lab.

Redo Log

Toward Flash-based Enterprise Databases

39

SKKU VLDB Lab.

Transaction Concept and Log

SQL

b i t
begin_transactiontiBufferselect statements;// readinsert/update/deletes;// update

Log Bufferpi

commit or rollback;DB
LOG

Toward Flash-based Enterprise Databases

40

SKKU VLDB Lab.

Transaction Concept and Log (2)
Tx1

Tx2

…

Tx N
Tx_N
Redo Log Buffer

SQL
BufferLog Buffer
Commitpi

DB
LOG

Redo Log File

512 Byte Block(include wastage)

Toward Flash-based Enterprise Databases

41

SKKU VLDB Lab.

Transaction Commit: Final Performance BottleneckTransaction response time = read / write + CPU + commit−

Negligible read / write time
9 Large buffer cache or main memory DBMS−

CPU time (dual core Intel CPU)
9 TPC
TPC-B:
B: 50 us
9 TPC-C: ~ 200 us−

Commit time = 8 ~ 10ms
9 Final performance bottleneck

Toward Flash-based Enterprise Databases

42

SKKU VLDB Lab.

TPS in TPC
TPC-B:
B: HDD vs. SSDTPS vs. CPU
3500

80%

CPU saturationknee point

3000

70%

60%
2500
50%

40%

CPU%

TPS

2000

1500
30%
1000
20%
500

10%

0

0%
vu1

vu5

vu10

vu15

S-SSD(CPU%)

vu20

vu25

HDD(CPU%)

Toward Flash-based Enterprise Databases

43

vu30

vu35

S-SSD(TPS)

vu40

vu45

vu50

HDD(TPS)SKKU VLDB Lab.

TPS in TPC
TPC-B:
B: HDD vs. SSD
CPU-boundCPUbound vs. IO-bound:
IO bound: 7200 vs. 10000 RPM SATA
5000
4500
4000
3500

TPS

3000
2500
2000
1500
1000
500
0
vu1
S‐SSD(Quad‐TPS)

vu5

vu10

vu15

10k SATA(Quad‐TPS)

vu20

vu25

vu30

7200 SATA(Quad‐TPS)

Toward Flash-based Enterprise Databases

44

vu35
S‐SSD(Dual‐TPS)

vu40

vu45

vu50

10k SATA(Dual‐TPS)

vu55

vu60

7200 SATA(Dual‐TPS)SKKU VLDB Lab.

Flash as Log DeviceCommunications of the ACM, July 2008−

“Flash memory storage” Adam Leventhal @ Sun

Toward Flash-based Enterprise Databases

45

SKKU VLDB Lab.

Rollback Segment

Toward Flash-based Enterprise Databases

46

SKKU VLDB Lab.

Undo Data in Oracle

Undo tablespace and rollback segments
Tx1 Tx2 …

Buffer Cache

Data File

Tx_N

Log Bufferpi

Temporary

Undo(Rollback)

Tablespace

Data

Toward Flash-based Enterprise Databases

47

Redo LogSKKU VLDB Lab.

Rollback Segment

C

…

B

100

A

50



t1
A

100

t0
A

200

t2

Rollback segment−

Stores undo(old) information−

T
Transaction
ti rollback;llb k MVCC



Each transaction is assigned to arollback segmentgin round-robinEach rollback segment is written in(almost) append-only mode−

Rollback segment
disk

Toward Flash-based Enterprise Databases48

Asynch mode by DBWR

For read consistency, the rollback
segments is randomly accessed

SKKU VLDB Lab.

Undo Area I/O Pattern (Write)
During TPC-C
TPC C run−(Semi-)Sequential write, then random read

Logicalal sector addresess (x1000)

800
700
600
500
400
300
200
100
0
0

100

200

300

400

500

600

Time (second)

Toward Flash-based Enterprise Databases

49

SKKU VLDB Lab.

Undo Area I/O Pattern (Read)

Full scan of a table while running TPC-C
TPC C

Toward Flash-based Enterprise Databases

50

SKKU VLDB Lab.

Temporary Tablespace

Toward Flash-based Enterprise Databases

51

SKKU VLDB Lab.

Temporary TablespaceIndex creation

Temporary tableS t / Sort
Sort
S t merge join
j iHash join

Toward Flash-based Enterprise Databases

52

SKKU VLDB Lab.

External Merge Sort


1st phase: run generation
2M (in(in-memory
memory sort)

200M
SourceData

100 runs

Main memory buffers
Disk

Disk


2nd p
phase: mergeg
INPUT 1...
Disk

INPUT 2...

OUTPUTINPUT 100

Main memory buffers

Toward Flash-based Enterprise Databases

53..
. DiskSKKU VLDB Lab.

IO Patterns in External Merge Sort


Sequential write, then random read

Toward Flash-based Enterprise Databases

54

SKKU VLDB Lab.

External Merge Sort


Experiment set up−

200M data
9 100B record
9 10B sort key−

I
In-memory
sortt area: 2M

Toward Flash-based Enterprise Databases

55

SKKU VLDB Lab.

External Merge Sort


Cluster−

Unit of IO in merge step

160

Disk
SSD



Change the cluster size−

2K ~ 128K

Optimal cluster size−

64K (hdd) vs. 2K (sdd)

Execution Ti
Time (sec)

140
120
100
80
60
40
20
2

16

32

48

64

80

96

112

Cluster Size in Merge Step (KB)

Implications
Toward Flash-based Enterprise Databases

56

SKKU VLDB Lab.

128

Hash Join
Original
Relation

OUTPUT
1

1

2

INPUT

...

Partitions

2

hashfunction

h

B-1

B-1
Disk

B main memory buffers

Disk

1. Partitioning (or building) phase

Partitionsof R & S

Join Result
Hash table for partition
Ri (k < B-1
B 1 pages))
hash
fn

h2
h2
Input buffer
for SiDisk

Outputbuffer

B main memory buffers

Disk

2. Probing (or matching) phaseToward Flash-based Enterprise Databases

57

SKKU VLDB Lab.

IO Patterns in Hash Join

Toward Flash-based Enterprise Databases

58

SKKU VLDB Lab.

FlashSSDs in Enterprise Databases

Toward Flash-based Enterprise Databases

59

SKKU VLDB Lab.

Next Challenges in Database
SQL

Log Buffer
Buffer Cache

Data File

Temporary

Undo(Rollback)

Tablespace

Data

Redo Log

Access pattern: random writes

Toward Flash-based Enterprise Databases

60

SKKU VLDB Lab.

Flash Perspectives from DB Community“There has been discussion of sea-changes in DBMS design arising fromnew storage technologies replacing disk
disk. Flash memory appears to be bothtechnologically viable and economically supported by a broad market. Flash
is the first new persistent storage medium to succeed in this regard in morethan three decades.” [Hellerstein, Stonebraker and Hamilton (2007)].

Flash is disk, disk is tape, and tape is dead.

Toward Flash-based Enterprise Databases

61

SKKU VLDB Lab.

Some DB Community Papers


DAMON 2008: from CPU to Storage in research−

Modeling the Performance of Algorithms on Flash Memory
Devices Ross, Kenneth−

Fast Scans and Joins using Flash Drives Shah, Mehul A.;
Stavros Harizopoulos; Janet L. Wiener; Goetz Graefe

VLDB 2008−

Flashing Up The Storage Layer, Ioannis Koltsidas (University of
Edinburgh), Stratis Viglas (University of Edinburgh)−

Online Maintenance of Very Large Random Samples on Flash
Storage Suman Nath (Microsoft Research), Phillip Gibbons (Intel
Research Pittsburgh
Research,Pittsburgh, USA)

Toward Flash-based Enterprise Databases

62

SKKU VLDB Lab.

Flash-based
Flash
based DBMS: Research Groups

Ken Ross @ Columbia



Sam Madden @ MIT

G f group @ HP
Graefe



HKUST



INRIA: PicoDBMS team−

PBFilter: Indexing Flash-Resident Data through Partitioned Summaries



MinesotaMicrosoft / Edinburg
g universityy ((VLDB 2008))

…

Toward Flash-based Enterprise Databases

63

SKKU VLDB Lab.

“If you wantt ttruly
l tot understandd t d something,thi
try to change it”

Kurt Lewin

Toward Flash-based Enterprise Databases

64

SKKU VLDB Lab.