Data Base Design Principles for Striping and Placement of

Data Base Design Principles for Striping and Placement of

Delay-Sensitive Data on Disks

Stavros Christodoulakis and Fenia Zioga*

Laboratory of Distributed Multimedia Information Systems and Applications (MU.S.I.C.),

Technical University of Crete (TUC)

e-mail: (stavros, fenia)@ced.tuc.gr

*work done in the context of the ESPRIT LTR Project HERMES (Foundations of High Performance Multimedia Information Management Systems), # 9141

Presentation Outline

Overview

Mathematical Tools

The Striping Performance Model

Disk Allocation for Striping Delay-Sensitive Objects

Grouping of Delay-Sensitive Objects across Two Striping Partitions

Summary

Overview

The Basic Striping Model

Partitioned vs. Unpartitioned Striping

Partitioning of Disks for Striping Two Delay-Sensitive Objects

Partitioning of Disks for Striping r Delay-Sensitive Objects

Grouping of Objects with Equal Consumption Rates into the same Striping Partitions

Grouping of Objects with Different Consumption Rates into the same Striping Partitions

Majorization Theory & Schur Functions

Majorization:

Then: holds if

Schur Functions:

if Schur convex& then

if Schur concave& then

Example:

f is a cost function and its argument is the vector of disk partition probabilities

f is Schur-concave. Let alternative disk partition probability vectorssuch that

Then, the cost function is maximized when partition probabilities are as uniform as possible

The Striping Performance Model

The Striping Model

The model enables comparisons among alternative designs of striping several objects

The model’s purpose is not analytic performance prediction

Parallel retrieval (fine-grained striping): appropriate for VCR operations, more robust in clock shifts, combines well with duplication [Gemmel96]

Assumptions

n identical disks for striping the objects

no bottleneck with network bandwidth, secondary storage buses, server/client buffer

retrieval requests like FF, RW, STOP, RESUME not studied (see [KYDONIA])

Placement & Retrieval of Striped Data

X: size of a round-block (or a stripe)

n stripe-units of size placed onto n disks in a round-robin fashion (disk load balancing)

k: #streams that are serviced in a round-robin scheduling within a service round

The Striping Performance Model (cont’d)

Hiccup-free Playback Condition:

Maximum #Concurrent Streams:

Capacity S(n) of an n disk partition: or

Minimum #disks to support k streams:
The Striping Performance Model (cont’d)

Impact of Striping Parameters on Performance

The Striping Performance Model (cont’d)

Impact of Striping Parameters on Performance (cont’d)

Data Prefetching in the Client

Achieves lower bandwidth requirement C’ from the server at real time

Achieves more concurrent streams S(n)

Introduces start-up delay in the playback

Requires storage at the client

Bandwidth Requirement:

Capacity:

The Striping Performance Model (cont’d)

Impact of Striping Parameters on Performance (cont’d)

Data Prefetching in the Client (cont’d)

Disk Allocation for Striping Two DS Objects

We seek the allocation accomplishing the maximum number of concurrent streams

Partitioned vs. Unpartitioned Striping

Fixed Access Probabilities

S(n) monotonically increasing and concave with respect to n

Partitioned striping accomplishes more concurrent streams compared to unpartitioned

Variable Access Probabilities

Unpartitioned striping may outperform paritioned striping when the object probabilities have a variance

Disk Allocation for Striping Two DS Objects (cont’d)

Allocation of Striping Partitions

Problem Definition: Let n₁ n₂:the #disks to stripe the 1^st and the 2^nd object.

Given:: access probabilities of the DS objects ()

C : consumption rate

B : round block size

Find
:

Problem Solution:

If no incoming requests are rejected the maximum #streams k₁ is when:

If some requests are rejected :

is Schur-concave with respect to

allocate as equal #disks as possible to the striping partitions

Disk Allocation for Striping Two DS Objects (cont’d)

Allocation of Striping Partitions (cont’d)

Allocation Algorithm: Optimal vs. Random allocations

(assumes )

Begin

If then

Allocate and

else

if then

allocate and

else

allocate and

End.

Disk Allocation for Striping r DS Objects (cont’d)

Allocation of Striping Partitions (cont’d)

Allocation Algorithm: (assumes )

If then

Allocate to each partition (i=1,..r)

else

for i=1 to r do

if then

allocate to the i^th partition

else

allocate to the remaining partitions (k=i,..r)

Next i
Grouping of DS Objects across Two Disk Partitions

Such grouping may be useful e.g.

When temporal variations are observed with object probabilities

When the storage space is limited

The grouping must achieve maximum number of concurrent streams
Objects with Equal Consumption Rates

Theorem: The function ,

gives the maximum #streams for two objects withstriped across two partitions

Theorem: F(p₁, p₂) is Schur concave with respect to

Conclusion: Grouping of objects must produce as equal cumulative probability of access as possible in the two partitions
Grouping of DS Objects across Two Disk Partitions (cont’d)
Objects with Different Consumption Rates

Given:

P_i: access probability of the i^th DS object, (i=1,..r)

C_{i ,}consumption rate of the i^th DS object, (i=1,..r)

n₁,n₂partition sizes

The optimal grouping must assign:

To the 1^st partition objects such that: =

To the 2^nd partition objects such that: =
Summary

The Striping Model

In our striping model the performance of striping is expressed as #concurrent streams supported

The performance of striping is affected by:

The number of striping disks but increase becomes less significant with more disks

The amount of buffer in the client

Prefetching in the client but at the expense of start-up delay and buffer overhead

Allocation of Striping Partitions

For fixed access probabilities of the objects, partitioned striping is more efficient than unpartitioned

When the system rejects clients, constructing equally sized partitions for striping the objects supports more clients simultaneously

For objects with equal bandwidth requirement, objects must be grouped so that the cumulative probabilities of the striping partitions are as equal as possible