Transcript ODS_Chapter6

Performance of
Distributed Systems
1.
2.
3.
4.
5.
Performance Metrics
Measurements
Performance Modeling
Dimensioning
Optimization
Design of Distributed Software
Performance Metrics
Process n1
Process 2
Process 1
Request
Response
•
Response Times
•
Throughput
Design of Distributed Software
Process n4
Process 2
Process 1
1. Performance
Metrics
Process n2
Process 2
Process 1
Process n3
Process 2
Process 1
2
Performance Metrics

Response Time


1. Performance
Metrics
as a function of the number of simultaneous requests
Throughput

=max number of simultaneous requests per second
Average
Variance
Worst case
Best case
Design of Distributed Software
3
Response Time
1. Performance
Metrics
Average
Response
Time
Maximum
response
time
throughput
Offset
response
time
Number of
simultaneous
requests
Design of Distributed Software
4
Response Time
1. Performance
Metrics
client
server
Composed of :
 Tsubm : submission time (+ marshalling) 1 client / 1 server
 Tforw : forward transmission time
 Twait : time spent in queue before a serving thread can be created
 Tproc, invoc : dispatch request + create thread from thread pool +
demarshalling

Tproc : server processing time
 Tproc, ret : return processing times (marshalling)
 Tbackw: backward transmission time
 Trec : reception time (+ demarshalling)
Design of Distributed Software
5
Response Time
r = Object.invoke (…);
1. Performance
Metrics
Tsubm
Tforw
Twait
Tproc, invoc
response time
Tproc
Tproc, ret
Trec
client
Design of Distributed Software
Tbackw
server
6
Tforw, Tbackw
1. Performance
Metrics

Is the required time for sending all packets or
frames to the destination host
 Packet/frame delay is the sum of delays on each
subnetwork link traversed by the packet/frame
link delay
packet delay
Design of Distributed Software
7
Link Delay
1. Performance
Metrics
To:
Via:
Y
Z
Output 2
Output 3
Z
Propagation delay
Y
Transmission delay
Processing delay
Design of Distributed Software
Queuing delay
8
Link Delay Components

Processing delay


Delay between the time the packet/frame is assigned to a queue
for transmission and the time it starts being transmitted
Transmission delay


Delay between the time the packet/frame is correctly received at
the head node of the link and the time the packet is assigned to an
outgoing link queue for transmission
Queuing delay


1. Performance
Metrics
Delay between the times that the first and last bits of the
packet/frame are transmitted
Propagation delay

Delay between the time the last bit is transmitted at the head node
of the link and the time the last bit is received at the tail node
Design of Distributed Software
9
Twait
1. Performance
Metrics
Server
Process
Tproc, invoc
+
Tproc
+
Tproc, ret
Twait = time spent in queue before a serving thread can be created
Cfr modelling packet queuing and transmission time
Important term in the response time
Design of Distributed Software
10
Performance of
Distributed Systems
1.
2.
3.
4.
5.
Performance Metrics
Measurements
Performance Modeling
Dimensioning
Optimization
Design of Distributed Software
Measurements

2. Measurements
Time measurements


C, Java function invocations (cfr gettimeofday)
better option: read register from processor
#define RTSC(x) __asm__ __volatile__ ( "rdtsc" \ :"=a" (((unsigned
long*)&x)[0]), \ "=d" (((unsigned long*)&x)[1]))
main(){
long long t1,t2;
RTSC(t1);
RTSC(t2);
printf("RTSC took: %Ld cycles.\n", t2-t1);
RTSC =
Read Time
StampCounter
RTSC(t1); sleep(1); RTSC(t2);
printf("The CPU clock is %Ld MHz.\n", t2-t1);
}

store time values in RAM: no disc access during measurements
Design of Distributed Software
12
Measurements

Network measurements



2. Measurements
TCPdump
Ethereal
Load measurements

Top, gTop library
T
1
n(t )dt

T 0

Load average =

n(t) = number of processes ready for scheduling at time t
%CPU : The task's share of the CPU time since the last
screen update, expressed as a percentage of total CPU time per
processor.
Design of Distributed Software
13
Top
Design of Distributed Software
2. Measurements
14
Performance of
Distributed Systems
1. Performance Metrics
2. Measurements
3. Performance Modeling
3.1 Queuing Systems
3.2 Little’s Theorem
3.3 Poisson Processes
3.4 M/M/1 queues
Design
of Distributed
3.5 M/M/m
queuesSoftware
4. Dimensioning
5. Optimization
Performance Modeling

Predict behaviour of system



3. Performance
Modelling
Response times
Throughput
Goal:



Determine number of required threads
Number of required servers
Where to instantiate server processes ?

Most important metrics: Twait and Tproc

Need for Queuing system theory !
Design of Distributed Software
16
Queuing System (1)
3.1 Queueing
Systems

Customers (= requests) arrive at random times to
obtain service
 Service time (= processing delay) is the time to
fulfill a request
customer (= request)
queue
Design of Distributed Software
service (= request handling)
17
Queuing System (2)

Assume that we already know:



3.1 Queueing
Systems
Customer arrival rate
Customer service rate
We want to know:


Average number of customers in the system
Average delay per customer
average delay
customer arrival rate
average # of customers
Design of Distributed Software
customer service rate
18
Definition of Symbols (1)
3.1 Queueing
Systems

pn = Steady-state probability of having n
customers in the system
 l = Arrival rate (inverse of average interarrival
time)
 m = Service rate (inverse of average service time)
 N = Average number of customers in the system
Design of Distributed Software
19
Definition of Symbols (2)
3.1 Queueing
Systems

NQ = Average number of customers waiting in
queue
 T = Average customer time in the system
 W = Average customer waiting time in queue
(does not include service time)
 X = Average service time
Design of Distributed Software
20
Standard Notation of Queuing Systems (1)
3.1 Queueing
Systems
X/Y/Z/K
 X indicates the nature of the arrival process



M: Memoryless (= Poisson process, exponentially
distributed interarrival times)
G: General distribution of interarrival times
D: Deterministic interarrival times
Design of Distributed Software
21
Standard Notation of Queuing Systems (2)
3.1 Queueing
Systems
X/Y/Z/K
 Y indicates the probability distribution of the
service times



M: Exponential distribution of service times
G: General distribution of service times
D: Deterministic distribution of service times
Design of Distributed Software
22
Standard Notation of Queuing Systems (3)
3.1 Queueing
Systems
X/Y/Z/K
 Z indicates the number of servers
 K (optional) indicates the limit on the number of
customers in the system
 Examples:



M/M/1, M/M/m, M/M/∞, M/M/m/m
M/G/1, G/G/1
M/D/1, M/D/1/m
Design of Distributed Software
23
Little’s Theorem





3.2 Little’s
Theorem
N = Average number of customers
l = Arrival rate
T = Average customer time
N = lT
Holds for almost every queuing system that
reaches a steady-state
Express the natural idea that crowded systems
(large N) are associated with long customer
delays (large T) and reversely
Design of Distributed Software
24
Proof of Little’s Theorem (1)

3.2 Little’s
Theorem
Assumption:

# of customer
arrivals/departures

The system is initially empty
Customers depart from the system in the order they
arrive
a(t)
N(t)
delay T2
delay T1
b(t)
0
t
Design of Distributed Software
25
Proof of Little’s Theorem (2)
 N ( ) d  
t
a (t )
0
i 1
3.2 Little’s
Theorem
Ti
Dividing both expressions by t gives
1 t
1 a (t )
a (t ) i1 Ti
N ( ) d  i1 Ti 

t 0
t
t
a (t )
a (t )
Taking the limit as
t   gives
N  lT
Design of Distributed Software
26
Application of Little’s Theorem (1)





3.2 Little’s
Theorem
NQ = Average # of customers waiting in queue
W = Average customer waiting time in queue
NQ = lW
X = Average service time
r  Average # of packets under transmission
r = lX
r is called the utilization factor (= the proportion
of time that the line is busy transmitting a packet)
Design of Distributed Software
27
Performance of
Distributed Systems
1. Performance Metrics
2. Measurements
3. Performance Modeling
3.1 Queuing Systems
3.2 Little’s Theorem
3.3 Poisson Processes
3.4 M/M/1 queues
Design
of Distributed
3.5 M/M/m
queuesSoftware
4. Dimensioning
5. Optimization
Poisson Process
3.3 Poisson
Processes

A stochastic process A(t) (t > 0, A(t) >=0) is said
to be a Poisson process with rate l if
1. A(t) is a counting process that represents the
total number of arrivals in [0, t]
2. The numbers of arrivals that occur in disjoint
intervals are independent
3. The number of arrivals in any [t, t + ] is Poisson
distributed with parameter l
P{ A(t   )  A(t )  n}  e
Design of Distributed Software
l
(l ) n
, n  0,1,
n!
29
Properties of Poisson Process (1)

Interarrival times n are independent and
exponentially distributed with parameter l
P{n  s}  1  e

3.3 Poisson
Processes
 ls
, s0
The mean and variance of interarrival times n
are 1/l and 1/l^2, respectively
Design of Distributed Software
30
Properties of Poisson Process (2)

3.3 Poisson
Processes
If two or more independent Poisson processes
A1, ..., Ak are merged into a single process A = A1
+ A2 + ... + Ak, the process A is Poisson with a
rate equal to the sum of the rates of its
components
A1
Ai
l1
li
lk
merge
l  i1 li
k
A
Poisson process
Ak
independent Poisson processes
Design of Distributed Software
31
Properties of Poisson Process (3)

3.3 Poisson
Processes
If a Poisson process A is split into two other
processes A1 and A2 by randomly assigning
each arrival to A1 or A2, processes A1 and A2 are
Poisson
split randomly
with probability p
l1
A1
A
Poisson process
with probability (1-p)
l2
A2
Poisson processes
Design of Distributed Software
32
M/M/1 Queuing System
3.4 M/M/1 queues

A single queue with a single server
 Customers arrive according to a Poisson process
with rate l
 The probability distribution of the service time is
exponential with mean 1/m
single server
Poisson arrival
with arrival rate l
infinite buffer
Design of Distributed Software
Exponentially distributed service time
with service rate m
33
M/M/1 Queuing System: Results (1)

3.4 M/M/1 queues
Utilization factor (proportion of time the server is
busy)
l
r
m

Probability of n customers in the system
pn  r n (1  r )

Average number of customers in the system
N
Design of Distributed Software
r
1 r
34
M/M/1 Queuing System: Results (2)

3.4 M/M/1 queues
Average customer time in the system
N
1
T 
λ μλ

Average number of customers in queue
NQ  lW 

r
2
1 r
Average waiting time in queue
W T 
Design of Distributed Software
1
m

r
m l
35
M/M/m Queuing System
3.5 M/M/m queues

A single queue with m servers
 Customers arrive according to a Poisson process
with rate l
 The probability distribution of the service time is
exponential with mean 1/m
m servers
Poisson arrival
with arrival rate l
infinite buffer
Design of Distributed Software
1
Exponentially
distributed
service time
with rate m
m
36
M/M/m Queuing System: Results (1)

Ratio of arrival rate to maximal system service
rate
l
r

3.5 M/M/m queues
mm
Probability of n customers in the system







k
m
(mr ) 
m 1 ( mr )
p 0  k  0


k!
m!(1  r ) 
 (mr ) n
 p 0
n!
pn  
m m
m
r
 p0

m!
Design of Distributed Software
1

nm
nm
37
M/M/m Queuing System: Results (2)


3.5 M/M/m queues
Probability that an arriving customer has to wait
in queue (m customers or more in the system)
p 0(mr )m
PQ 
m!(1  r )
Average waiting time in queue of a customer
rPQ
W

l l (1  r )
NQ

Average number of customers in queue
rPQ
NQ  n 0 npm  n 
1 r

Design of Distributed Software
38
M/M/m Queuing System: Results (3)

Average customer time in the system
1

3.5 M/M/m queues
1
PQ
T  W  
m
m mm  l
Average number of customers in the system
rPQ
N  lT  mr 
1 r
Design of Distributed Software
39
Twait calculation
3.5 M/M/m queues
Average
Twait
m=2
m=1
m=8
m=4
0
Design of Distributed Software
1
load r

l/m.m
40
Performance of
Distributed Systems
1.
2.
3.
4.
5.
Performance Metrics
Measurements
Performance Modeling
Dimensioning
Optimization
Design of Distributed Software
Calculation of required threads
4. Dimensioning
m=2
Average
Twait
...
...
m=1
Desired
Average
Twait
m=4
m=8
0
1
2
Design of Distributed Software
4
Measured
l/m
8
l/m
42
Dimensioning
4. Dimensioning

Determine number of required threads
 Number of required servers
 Evaluation of clustering modes

i.e. how to best group process on the workstations
Design of Distributed Software
43
4. Dimensioning
Multiple Servers
CP = control performer
Example :
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
hierarchical control architecture
Design of Distributed Software
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
CP
flat control architecture
44
Multiple Servers
4. Dimensioning
CP
CP CP
CP CP
CP CP
CP CP
CP
CP
CP
CP CP
CP CP
CP CP
CP CP
CP CP
CP CP
CP
CP
CP CP
CP CP
CP CP
CP CP
CP CP
CP CP
Use of previous formulas :
flat architecture
1,E+05
100
s
hierarchical architecture
flat architecture
Flat
CP architecture with PCC
setup time (ms)
CP
architecture
hierarchical
architecture
IBM NwaysHierarchical
8265 ATM
switches
1,E+04
10
s SNMP/CORBA gateways
Setup-Time
CORBA Implementatie: Orbix 2.3
Solaris Ultra Sparc 5 werkstations (100 MBit/s Ethernet)
6 hierarchical layers
Theoretisch model (netwerk van wachtlijnen)
1s
1,E+03
100
ms
1,E+02
41
Design of Distributed Software
16
2
64
3
Number ofNSwitches
256
4
1024
5
45
Performance of
Distributed Systems
1.
2.
3.
4.
5.
Performance Metrics
Measurements
Performance Modeling
Dimensioning
Optimization
Design of Distributed Software
Resource Optimization

5. Resource
Optimization
Resource optimization




Determine where to start a new process
Based on current load of the workstations
Transparent for the users
Independent of Operation System of workstations
Need for Cluster management system
- MOSIX
- CORBA/J2EE Cluster Management System
Design of Distributed Software
47
Mosix cluster management platform
Mosix01:~$
5. Resource
Optimization
start_task
Linux Workstations
Mosix Cluster
Properties Mosix:
- Only for Linux
- No efficient communication between components
- Cluster can get overloaded when too many tasks
(no task management)
Design of Distributed Software
48
CORBA/J2EE cluster management platform
5. Resource
Optimization
start_task(task_info)
Software
Cluster management platform
Task mgmt
Linux Workstation
Properties
- Independent of operating system
Windows
NT/98/2000/XP
Solaris Workstation
- Task Management
- Efficient communication between components
- Sub-clusters possible
Design of Distributed Software
49
Architecture Cluster Management Platform
Taak
Management
Cluster
Coordinator
Software
Subcluster
Coordinator
Cluster Balancing
Coordinator
CORBA Clusterbeheerplatform
Balancing
Server
5. Resource
Optimization
Taakbeheer
Subcluster
Coordinator
Balancing
Server
UitvoeringsUitvoeringsExecutionServer
Server
Server
UitvoeringsUitvoeringsExecutionServer
Server
Server
UitvoeringsUitvoeringsExecutionServer
Server
Server
UitvoeringsUitvoeringsExecutionServer
Server
Server
Monitor
Monitor
Monitor
Monitor
Monitor
Monitor
Monitor
Monitor
Monitor
Monitor
Monitor
Monitor
Design of Distributed Software
50