Distributed Systems Design

COMP 6231
Introduction
Lecture 1

Essam Mansour

1
2
 Course Staff
Instructor: Dr. Essam Mansour
- Email: [Link]@[Link]
- Instructor’s Website: [Link]
- Office hours: by appointment
You should arrange for a meeting via email
Teaching Assistant:
Essam
- Omij Mangukiya [Link]@[Link]
- Waleed Afandi [Link]@[Link]

3
Omij Waleed
Teaching Style
• I like interaction in class
• I like to ask questions
• I like to be asked questions

• I like to know (and memorize) your names J

• I like to give practical assignments and projects

• I like to learn …

4
 Course Textbook
Textbook:

Distributed Systems, 3rd ed, by Tannenbaum and Van Steen, Prentice

Hall 2018
• All lectures will be prepared from this book.

• The book is available at the moodle.

• plus some other material, we may need.

5
 Course Outline
• Introduction (today Part 1)
- What, why, why not?
- Basics

• Distributed Architectures

• Interprocess Communication
- RPCs, RMI, message- and stream-oriented communication

• Processes and their scheduling

- Thread/process scheduling, code/process migration, virtualization

• Naming and location management

- Entities, addresses, access points
6
 Course Outline
• Canonical problems and solutions
- Mutual exclusion, leader election, clock synchronization, …

• Resource sharing, replication and consistency

- DFS, consistency issues, caching and replication

• Fault-tolerance

• Security in distributed Systems

• Distributed middleware

• Advanced topics: web, cloud computing, green computing, big data, multimedia,
and mobile systems
7
 Course Grading

Type # Weight
Project 1 30%
Exams 2 45%
Assignments 5 25%

Table 1: Breakdown of the main activities involved in the

course.

8
 Course Grading
Project: 30% of your final score.
- Each team consists of 3 to 4 students.
- Each team will learn one of the following systems:
- Pregel, GraphLab, PowerGraph, Cassandra, Couchbase, MongoDB, or
Elasticsearch. You can propose a parallel system to develop.
- Discuss the concepts of distributed systems in the chosen system.
- Use a real dataset of at least one GB, the larger the better, and
- Demo the capabilities of the chosen system.

- The deliverables of the project are:

Demo 15% of the final grade
Presentation 10% of the final grade
Report 5% of the final grade
9
 Course Grading
Assignments:
- 25% towards your final score
- 4 programming assignments

ID Topic Weight Release Date Due Date

1 Socket 5% Fri Sept 22 Sun Oct 08

2 Multithreading & 9% Fri Oct 06 Sun Oct 29

MPI
3 Docker 5% Fri Oct 27 Sun Nov 12

4 SPARK Map- 6% Fri Nov 10 Sun Nov 26

Reduce

10
… and now

11
Data Becoming Critical to Our Lives

Health Science
Domains
Education of Data
Work

Environment Finance

… and more

12
We Live in a World of Data…

13
What Do We Do With Data?

Store Share

Access Process

…. and
Encrypt more!

We want to do these seamlessly...

14
 How to Store and Process Data at Scale?

• A system can be scaled:

• Either vertically (or up) ü
• Can be achieved by hardware upgrades (e.g., faster CPU, more
memory, and/or larger disk)

• And/Or horizontally (or out)

• Can be achieved by adding more machines

15
 Vertical Scaling
• Caveat: Individual computers can still suffer from limited resources
with respect to the scale of today’s problems
The image part with relationship ID
1. Caches and Memory: rId8 was not found in the file.

L1
16-32 KB/Core, 4-5 cycles
Cache

L2 Cache 128-256 KB/Core, 12-15 cycles

L3 Cache 512KB- 2 MB/Core, 30-50 cycles

Main Memory 8GB- 128GB, 300+ cycles

16
 Vertical Scaling
• Caveat: Individual computers can still suffer from limited resources
with respect to the scale of today’s problems

2. Processors:
§ Moore’s law still holds

§ Chip Multiprocessors (CMPs) are now available

P P P P
P L1 L1 L1 L1
L1
Interconnect
L2
L2 Cache

A single Processor Chip

17
A CMP
 Vertical Scaling
• Caveat: Individual computers can still suffer from limited resources
with respect to the scale of today’s problems

2. Processors:
§ But up until a few years ago, CPU speed grew at the rate of 55%
annually, while the memory speed grew at the rate of only 7%

Processor-Memory speed gap

M

18
 Vertical Scaling
• Caveat: Individual computers can still suffer from limited resources
with respect to the scale of today’s problems

2. Processors:
§ But up until a few years ago, CPU speed grew at the rate of 55%
annually, while the memory speed grew at the rate of only 7%

§ Even if 100s or 1000s of cores are placed on a CMP, it is a challenge

to deliver input data to these cores fast enough for processing
 Vertical Scaling

P P P P
10000 Suffer from
L1 L1 L1 L1 seconds (or limited scalability
3 hours) to
Interconnect
load data
L2 Cache
A Data Set
of 4 TBs

Memory

4 100MB/S IO Channels

20
 How to Store and Process Data at Scale?

• A system can be scaled:

• Either vertically (or up)
• Can be achieved by hardware upgrades (e.g., faster CPU, more
memory, and/or larger disk)

• And/Or horizontally (or out)

• Can be achieved by adding more machines ü

21
 Horizontal Scaling

P 100
P
Splits Only 3
L1 Machines L1
minutes to
L2 L2 load data

Memory Memory
A Data Set (data)
of 4 TBs

22
 Requirements
• But, this necessitates:
• A way to express the problem in terms of parallel processes and execute them
on different machines (Programming and Concurrency Models)

• A way to organize processes (Architectures)

• A way for distributed processes to exchange information (Communication

Paradigms)

• A way to locate and share resources (Naming Protocols)

23
 Requirements
• But, this necessitates:
• A way for distributed processes to cooperate, synchronize with one another,
and agree on shared values (Synchronization)

• A way to reduce latency, enhance reliability, and improve performance

(Caching, Replication, and Consistency)

• A way to enhance load scalability, reduce diversity across heterogeneous

systems, and provide a high degree of portability and flexibility
(Virtualization)

• A way to recover from partial failures (Fault Tolerance)

24
 Degree of Parallelism

DATA D A T A

Task Parallelism Data Parallelism

25
 So, What is a Distributed System?

A distributed system is:

One in which components

A collection of independent
located at networked
computers that appear to its
computers communicate and
users as a single coherent
coordinate their actions only
system
by passing messages

26
 Features
• Distributed Systems imply four main features:

1 Geographical Separation

2 No Common Physical Clock

3 No Common Physical Memory

4 Autonomy and Heterogeneity

27
 Parallel vs. Distributed Systems
• Distributed systems contrast with parallel systems, which entail:

1 Strong Coupling

2 A Common Physical Clock

I am not sure.
Can you verify that?

3 A Shared Physical Memory

4 Homogeneity
28
 Another Definition of a Distributed System
A distributed system:
- Multiple connected CPUs working together
- A collection of independent computers that appears to its users as a
single coherent system

Examples: parallel machines, networked machines

29
 Distributed System Models
• Cluster computing systems / Data centers
• LAN with a cluster of servers + storage
• Linux, Mosix, ..
• Used by distributed web servers, scientific applications, enterprise applications

• Grid computing systems

• Cluster of machines connected over a WAN
• SETI @ home

• WAN-based clusters / distributed data centers

• Google, Amazon, Facebook …

• Virtualization and data center

• Cloud Computing 30
 Emerging Models
• Distributed Pervasive Systems
• “smaller” nodes with networking capabilities
• Computing is “everywhere”

Mobile Devices
Computers

…and even appliances

Consumer Electronics Personal Monitors and

Sensors

We also want to access, share and process our data from all of
our devices, anytime, anywhere! 31
 Middleware-based Systems
General structure of a distributed system as middleware.

32
 Transparency in a Distributed System
Transparency Description

Access Hide differences in data representation and how a resource is accessed

Location Hide where a resource is located

Migration Hide that a resource may move to another location

Relocation Hide that a resource may be moved to another location while in use

Replication Hide that a resource may be replicated

Concurrency Hide that a resource may be shared by several competitive users

Failure Hide the failure and recovery of a resource

Persistence Hide whether a (software) resource is in memory or on disk

33
 Scalable Distributed System
Scalability Dimensions
- Size scalability:
- A system can be scalable with respect to its size,
- we can easily add more users and resources to the system without any noticeable
loss of performance.

- Geographical scalability:
- The users and resources may lie far apart,
- The fact that communication delays may be significant is hardly noticed.

- Administrative Scalability:
- Still be easily managed even if it spans many independent administrative
organizations. 34
 Scaling Techniques
• Principles for good decentralized algorithms
• No machine has complete state
• Make decision based on local information
• A single failure does not bring down the system
• No global clock

• Techniques
• Asynchronous communication
• Distribution
• Caching and replication

35
 Comparison between Systems
Distributed OS
Middleware-
Item Network OS
Multiproc. Multicomp. based OS

Degree of transparency Very High High Low High

Same OS on all nodes Yes Yes No No

Number of copies of OS 1 N N N

Basis for communication Shared memory Messages Files Model specific

Global,
Resource management Global, central Per node Per node
distributed

Scalability No Moderately Yes Varies

Openness Depends on OS Depends on OS Open Open 36

 A To-Do List
• Read Chapters 1, Introduction

• Attend the lab

• Start working in your first assignment

 Next Lecture
• Chapter 2: Architectures

Questions?

38