<<  Content-Based Image Retrieval using the Bag-of-Words Concept   >>
Object Based Disk: the key to intelligent I/O
Object Based Disk: the key to intelligent I/O
Why are we interested
Why are we interested
I/O is considered the weak link in systems architecture
I/O is considered the weak link in systems architecture
Issues
Issues
Operating System
Operating System
Data evolution
Data evolution
In short
In short
The advantage of object based design is
The advantage of object based design is
SQL object is good choice
SQL object is good choice
Researchers in Intelligent Disks are motivated by
Researchers in Intelligent Disks are motivated by
Consider a disk farm
Consider a disk farm
But where do we place the intelligence
But where do we place the intelligence
Disk basics
Disk basics
To access a random block
To access a random block
Design Goals
Design Goals
Access strategies
Access strategies
Optimum Block Size
Optimum Block Size
Select name, address,salary where salary >22K
Select name, address,salary where salary >22K
Data Utility
Data Utility
Consider the travels of an inchworm
Consider the travels of an inchworm
Travels of an inchworm
Travels of an inchworm
Travels of an inchworm
Travels of an inchworm
Locality of Reference
Locality of Reference
Preservation of Logical Topology
Preservation of Logical Topology
Observations:
Observations:
Treating disk as 2D space
Treating disk as 2D space
The disk is 3 dimensional
The disk is 3 dimensional
Consider the first cylinder of the set
Consider the first cylinder of the set
Examining a single cylinder
Examining a single cylinder
which has tracks and sectors
which has tracks and sectors
track for each head
track for each head
track read
track read
diagonal (sector block) read
diagonal (sector block) read
sector block shadow
sector block shadow
Unwrap a cylinder
Unwrap a cylinder
2 dimensional space: hd x sector
2 dimensional space: hd x sector
track read or sector block read
track read or sector block read
Physical Sector Block Organization
Physical Sector Block Organization
Logical Sector Block Organization
Logical Sector Block Organization
record structure
record structure
modified best fit algorithm
modified best fit algorithm
modified best fit algorithm
modified best fit algorithm
SQL Decomposition
SQL Decomposition
Comparison Results
Comparison Results
Prototype
Prototype
Data particulars
Data particulars
Test Runs
Test Runs
Results
Results
Benchmark Analysis
Benchmark Analysis
Wisconsin results
Wisconsin results
Average time within class
Average time within class
TPC Q6
TPC Q6
But what about indexes
But what about indexes
The S curve
The S curve
Index vs Exhaustive Scan
Index vs Exhaustive Scan
Penalty for wrong guess is less
Penalty for wrong guess is less
Index Strategy
Index Strategy
Intelligent I/O Processor
Intelligent I/O Processor
I/O ops are atomic to the cylinder
I/O ops are atomic to the cylinder
IOP Characteristics
IOP Characteristics
Parallel Architecture
Parallel Architecture
Comments
Comments
Summary
Summary
Challenge and future work
Challenge and future work

: . : George Gorbatenko. : .ppt. zip-: 242 .

...

.ppt
1 Object Based Disk: the key to intelligent I/O

Object Based Disk: the key to intelligent I/O

George Gorbatenko Data Machine International St Paul, MN 55115 gorby@ece.umn.edu

Sept 23, 2002

1

2 Why are we interested

Why are we interested

faster transportable more accessible cheaper facilitates holistic design improve reliability

Sept 23, 2002

DMI

2

3 I/O is considered the weak link in systems architecture

I/O is considered the weak link in systems architecture

I/O problem memory wall bottle neck

Sept 23, 2002

DMI

3

4 Issues

Issues

randomness is painful mechanical time vs electronic time ratio of times is about 200:1 operating system obscures the disk

Sept 23, 2002

DMI

4

5 Operating System

Operating System

seamless view of space legacy of data storage goes back to punched card accommodates all applications

Sept 23, 2002

DMI

5

6 Data evolution

Data evolution

tape reflected a 80 column card image disk reflected tape

Sept 23, 2002

DMI

6

7 In short

In short

nothing much has changed data format-wise since the 1930s we are pretty much dealing with records in a linear format, one record after the next

Sept 23, 2002

DMI

7

8 The advantage of object based design is

The advantage of object based design is

encapsulate the data define the application subset dont have the operating system getting in the way

Sept 23, 2002

DMI

8

9 SQL object is good choice

SQL object is good choice

broad user base de facto standard for data bases high enough to exploit the power in the I/O yesterdays CPU in todays disk (controller) aggregate compute power exceeds the host

Sept 23, 2002

DMI

9

10 Researchers in Intelligent Disks are motivated by

Researchers in Intelligent Disks are motivated by

exploiting the latent processing potential filtering data in place

Sept 23, 2002

DMI

10

11 Consider a disk farm

Consider a disk farm

Sept 23, 2002

DMI

11

12 But where do we place the intelligence

But where do we place the intelligence

host I/O controller disk

Sept 23, 2002

DMI

12

13 Disk basics

Disk basics

many platters (ea fixed head) 10 many concentric tracks / platter 10k each track holds many sectors 100 Total number of 512 byte sectors 10M ____ disk capacity: 5GB

Sept 23, 2002

DMI

13

14 To access a random block

To access a random block

seek to track 10-15 us wait for block to roll around 4 5 us read block 80 us hence 200:1

Sept 23, 2002

DMI

14

15 Design Goals

Design Goals

synchronous operation next data you want is beneath head process data in place (filter) touch the min amount of data for what you touch you pay in time and space exploit locality amortize random access read over large data block

Sept 23, 2002

DMI

15

16 Access strategies

Access strategies

Amortize the (inefficient) access over large block of data Make sure the data has utility

Sept 23, 2002

DMI

16

17 Optimum Block Size

Optimum Block Size

Sept 23, 2002

DMI

17

18 Select name, address,salary where salary >22K

Select name, address,salary where salary >22K

Sept 23, 2002

DMI

18

19 Data Utility

Data Utility

Sept 23, 2002

DMI

19

20 Consider the travels of an inchworm

Consider the travels of an inchworm

A1 B1 C1 D1 E1 A2 B2 C2 D2 E2 A3 B3 C3 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5

Sept 23, 2002

DMI

20

21 Travels of an inchworm

Travels of an inchworm

A1 B1 C1 D1 E1 A2 B2 C2 D2 E2 A3 B3 C3 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5

Sept 23, 2002

DMI

21

22 Travels of an inchworm

Travels of an inchworm

A1 B1 C1 D1 E1 A2 B2 C2 D2 E2 A3 B3 C3 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5

Sept 23, 2002

DMI

22

23 Locality of Reference

Locality of Reference

A1 B1 C1 D1 E1 A2 B2 C2 D2 E2 A3 B3 C3 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 (a) Logical view of two dimensional table. A1 B1 C1 D1 E1 A2 B2 C2 D2 E2 A3 B3 C3 D3 (b) Row ordered mapping (physical). A1 A2 A3 A4 A5B1 B2 B3 B4 B5 C1 C2 C3 C4 (c) Column ordered mapping (physical)

Sept 23, 2002

DMI

23

24 Preservation of Logical Topology

Preservation of Logical Topology

To preserve the logical topology of n dimensional logical data space, the physical space must at least be of like dimension. - for a 2D table (rows and columns) we need to view disk as two dimensional

Sept 23, 2002

DMI

24

25 Observations:

Observations:

SQL can be decomposed in two operations select - favored by column order extract favored by row order granular access permits touching min data map data so as to preserve topology when going from logical to physical medium reading a tracks worth of data appears reasonable

Sept 23, 2002

DMI

25

26 Treating disk as 2D space

Treating disk as 2D space

data objects are 2D spaces solves design boundaries disk is basically a 3D medium cylinder-track-sector

Sept 23, 2002

DMI

26

27 The disk is 3 dimensional

The disk is 3 dimensional

Sept 23, 2002

DMI

27

28 Consider the first cylinder of the set

Consider the first cylinder of the set

Sept 23, 2002

DMI

28

29 Examining a single cylinder

Examining a single cylinder

Sept 23, 2002

DMI

29

30 which has tracks and sectors

which has tracks and sectors

Sept 23, 2002

DMI

30

31 track for each head

track for each head

Sept 23, 2002

DMI

31

32 track read

track read

Sept 23, 2002

DMI

32

33 diagonal (sector block) read

diagonal (sector block) read

Sept 23, 2002

DMI

33

34 sector block shadow

sector block shadow

Sept 23, 2002

DMI

34

35 Unwrap a cylinder

Unwrap a cylinder

Sept 23, 2002

DMI

35

36 2 dimensional space: hd x sector

2 dimensional space: hd x sector

Sept 23, 2002

DMI

36

37 track read or sector block read

track read or sector block read

Sept 23, 2002

DMI

37

38 Physical Sector Block Organization

Physical Sector Block Organization

Physical sector (512)

Logical sector size (lss)

Sept 23, 2002

DMI

38

39 Logical Sector Block Organization

Logical Sector Block Organization

Physical sector (512)

Logical sector size (lss)

Sept 23, 2002

DMI

39

40 record structure

record structure

typedef struct _record { char employee_no [8]; // employee number; field A char name [12]; // name; field B char address [24]; // address; field C char zip [5]; // zip code; field D char salary [6]; // salary; field E char doh [6]; // data of hire; field F char dept [3]; // department; field G char tbd [16]; // reserved for future use; field H } Record;

Sept 23, 2002

DMI

40

41 modified best fit algorithm

modified best fit algorithm

LSS = ceil (rec_len / num_hds) = ceil (64 /10) = 4n = 8 rec_space = LSS * num_hds = 80 bytes

LSS (8 bytes)

Sept 23, 2002

DMI

41

42 modified best fit algorithm

modified best fit algorithm

LSS (8 bytes)

B

C

D

G

E

F

Sept 23, 2002

DMI

42

A

typedef struct _record { char employee_no [8]; // field A char name [12]; // field B char address [24]; // field C char zip [5]; // field D char salary [6]; // field E char doh [6]; // field F char dept [3]; // field G char tbd [16]; // field H } Record;

43 SQL Decomposition

SQL Decomposition

Select records scan the salary field stores ordinal position in bit vector Extract records optimizer decides strategy (trk or sb read)

Sept 23, 2002

DMI

43

44 Comparison Results

Comparison Results

Sept 23, 2002

DMI

44

45 Prototype

Prototype

two 4 GB Seagate Baracudas 21 heads (29 zones) 40 KLOC skew = 5 sectors Solaris 2.51 OS emulated intelligence in IOP context sw every 60 ms

Sept 23, 2002

DMI

45

46 Data particulars

Data particulars

168 byte records LSS = 8 bytes 63 records per Sector Block 7,749 records per cylinder 3 fields (2 heads) involved in query 2 records extracted from disjoint blocks

Sept 23, 2002

DMI

46

47 Test Runs

Test Runs

write cyl worth data w/o optimizer write same with optimizer enabled scan cyl involving 3 col; extract 2 blks repeat operation (c)

Sept 23, 2002

DMI

47

48 Results

Results

Observed Calculated case (a) 2.5 sec 2.427 sec case (b) 196 ms 216 4 ms case (c) 51 ms 54.5 4ms case (d) 42 ms 37.6 4ms

Sept 23, 2002

DMI

48

49 Benchmark Analysis

Benchmark Analysis

3 Benchmarks selected - Wisconsin - Set Query - TPC D/H selected non-join cases reversed engineered the I/O detail

Sept 23, 2002

DMI

49

50 Wisconsin results

Wisconsin results

Sept 23, 2002

DMI

50

WISCONSIN BENCHMARK

1000

WIS

2D

100.0

Time ( seconds)

10.00

1.000

0.100

Q1

Q2

Q3

Q4

Q5

Benchmarks

51 Average time within class

Average time within class

Sept 23, 2002

DMI

51

AVERAGE TIME WITHIN CLASS

200

DB2

M204

180

2D

160

140

120

Average Time (seconds)

100

80

60

40

20

0

Q1

Q2A

Q3A

Q4A

Q5

Query Group

52 TPC Q6

TPC Q6

LINEAL block size 8,192 65,536 time (sec) 155 19.38 8.00 ratio FOM 0.009 0.05 5.47 ratio 2D lss (bytes) 8 4 time (sec) 1.95 1.59 1.23 ratio FOM 0.454 0.639 1.41 ratio FOM ratio 49.38 12.71 time ratio 79.52 12.22

Sept 23, 2002

DMI

52

53 But what about indexes

But what about indexes

Depending on selection rate, may make sense. useful when enforcing unique key SQL JOIN operation add noise to coherent system

Sept 23, 2002

DMI

53

54 The S curve

The S curve

Sept 23, 2002

DMI

54

EXTRACTION TIME vs SELECTION

25

DEL=1

20

DEL=2

DEL=4

DEL=8

DEL=16

15

Number of Spins

10

5

0

0.01%

0.10%

1.00%

10.0%

100%

Selection (percent)

55 Index vs Exhaustive Scan

Index vs Exhaustive Scan

Sept 23, 2002

DMI

55

COMPARISON: INDEX vs EXHAUSTIVE SCAN

seq X

rand X

iso X

2D seq

2D rand

Time to Extract Records from 1M Row Table (seconds)

Extraction Rate (expressed as percentage)

56 Penalty for wrong guess is less

Penalty for wrong guess is less

7 hours

3 seconds

Sept 23, 2002

DMI

56

COMPARISON: INDEX vs EXHAUSTIVE SCAN

seq X

rand X

iso X

2D seq

2D rand

Time to Extract Records from 1M Row Table (seconds)

Extraction Rate (expressed as percentage)

57 Index Strategy

Index Strategy

Use on unique fields consider for JOIN operations evaluate based on knowledge of data AVOID where no information is available about data - penalty is bounded

Sept 23, 2002

DMI

57

58 Intelligent I/O Processor

Intelligent I/O Processor

IOP

20 KC

200 MB/s

36 MB/s

Sept 23, 2002

DMI

58

59 I/O ops are atomic to the cylinder

I/O ops are atomic to the cylinder

Information contained in a clip spindle & cylinder number & LSS data number records scan info (selection criteria) command fields of interest (project) read/write/scan Data and bit (beta) vector returned

Sept 23, 2002

DMI

59

60 IOP Characteristics

IOP Characteristics

Manages own memory and - tracks are cached DSP is ideal building block - columns, vectors Has no semantic awareness of data offsets and widths Process data in real time RISC type - executes simple jobs quickly

Sept 23, 2002

DMI

60

61 Parallel Architecture

Parallel Architecture

10 MZ / .020 = 500 IOPs 500 IOPs => 4K spindles

HOST PROCESSOR

IOP 1

IOP 2

IOP 3

IOP n

Sept 23, 2002

DMI

61

62 Comments

Comments

Issue becomes being able to evenly distribute data DB vendors have to pass the info down Disk OEMs capacity vs intelligence Performance is scalable Evaluate performance of indexes in new light - could introduce noise in otherwise coherent system

Sept 23, 2002

DMI

62

63 Summary

Summary

Object Based Design permits local optimization with minimum compromise 2D mapping Synchronous disk Granular access is key Intelligent IOP (real time processing) For I/O limited applications significant performance gains are possible

Sept 23, 2002

DMI

63

64 Challenge and future work

Challenge and future work

Model a more rigorous system Explore other applications spatial scientific Integrate concept in a communication model add disk instrumentation define role for disk

Sept 23, 2002

DMI

64

http://900igr.net/prezentacija/anglijskij-jazyk/klass-sgate-232644.html
c

29