Distributed Systems Principles and Paradigms
Maarten van Steen
VU Amsterdam, Dept. Computer Science steen@cs.vu.nl
Chapter 01: Introduction
Version: August 27, 2012
1 / 28
Introduction
1.1 Denition
Introduction
1.1 Denition
Distributed System: Denition
A distributed system is a collection of autonomous computing elements that appears to its users as a single coherent system Two aspects: (1) independent computing elements and (2) single system middleware.
Same interface everywhere Computer 1 Computer 2 Computer 3 Computer 4
Appl. A
Application B
Appl. C
Distributed-system layer (middleware) Local OS 1 Local OS 2 Local OS 3 Local OS 4
Network
2 / 28 2 / 28
Introduction
1.2 Goals
Introduction
1.2 Goals
Goals of Distributed Systems
Making resources available Distribution transparency Openness Scalability
3 / 28
3 / 28
Introduction
1.2 Goals
Introduction
1.2 Goals
Distribution transparency
Transp. Access Location Relocation Migration Replication Concurrency Failure Description Hide differences in data representation and how an object is accessed Hide where an object is located Hide that an object may be moved to another location while in use Hide that an object may move to another location Hide that an object is replicated Hide that an object may be shared by several independent users Hide the failure and recovery of an object
Note Distribution transparency is a nice a goal, but achieving it is a different story.
4 / 28 4 / 28
Introduction
1.2 Goals
Introduction
1.2 Goals
Degree of transparency
Observation Aiming at full distribution transparency may be too much: Users may be located in different continents Completely hiding failures of networks and nodes is (theoretically and practically) impossible You cannot distinguish a slow computer from a failing one You can never be sure that a server actually performed an operation before a crash Full transparency will cost performance, exposing distribution of the system Keeping Web caches exactly up-to-date with the master Immediately ushing write operations to disk for fault tolerance
5 / 28
5 / 28
Introduction
1.2 Goals
Introduction
1.2 Goals
Openness of distributed systems
Open distributed system Be able to interact with services from other open systems, irrespective of the underlying environment: Systems should conform to well-dened interfaces Systems should support portability of applications Systems should easily interoperate Achieving openness At least make the distributed system independent from heterogeneity of the underlying environment: Hardware Platforms Languages
6 / 28 6 / 28
Introduction
1.2 Goals
Introduction
1.2 Goals
Policies versus mechanisms
Implementing openness Requires support for different policies: What level of consistency do we require for client-cached data? Which operations do we allow downloaded code to perform? Which QoS requirements do we adjust in the face of varying bandwidth? What level of secrecy do we require for communication? Implementing openness Ideally, a distributed system provides only mechanisms: Allow (dynamic) setting of caching policies Support different levels of trust for mobile code Provide adjustable QoS parameters per data stream Offer different encryption algorithms
7 / 28 7 / 28
Introduction
1.2 Goals
Introduction
1.2 Goals
Scale in distributed systems
Observation Many developers of modern distributed system easily use the adjective scalable without making clear why their system actually scales. Scalability At least three components: Number of users and/or processes (size scalability) Maximum distance between nodes (geographical scalability) Number of administrative domains (administrative scalability) Observation Most systems account only, to a certain extent, for size scalability. The (non)solution: powerful servers. Today, the challenge lies in geographical and administrative scalability.
8 / 28 8 / 28
Introduction
1.2 Goals
Introduction
1.2 Goals
Techniques for scaling
Hide communication latencies Avoid waiting for responses; do something else: Make use of asynchronous communication Have separate handler for incoming response Problem: not every application ts this model
9 / 28
9 / 28
Introduction
1.2 Goals
Introduction
1.2 Goals
Techniques for scaling
Distribution Partition data and computations across multiple machines: Move computations to clients (Java applets) Decentralized naming services (DNS) Decentralized information systems (WWW)
10 / 28
10 / 28
Introduction
1.2 Goals
Introduction
1.2 Goals
Techniques for scaling
Replication/caching Make copies of data available at different machines: Replicated le servers and databases Mirrored Web sites Web caches (in browsers and proxies) File caching (at server and client)
11 / 28
11 / 28
Introduction
1.2 Goals
Introduction
1.2 Goals
Scaling The problem
Observation Applying scaling techniques is easy, except for one thing: Having multiple copies (cached or replicated), leads to inconsistencies: modifying one copy makes that copy different from the rest. Always keeping copies consistent and in a general way requires global synchronization on each modication. Global synchronization precludes large-scale solutions. Observation If we can tolerate inconsistencies, we may reduce the need for global synchronization, but tolerating inconsistencies is application dependent.
12 / 28 12 / 28
Introduction
1.2 Goals
Introduction
1.2 Goals
Developing distributed systems: Pitfalls
Observation Many distributed systems are needlessly complex caused by mistakes that required patching later on. There are many false assumptions: The network is reliable The network is secure The network is homogeneous The topology does not change Latency is zero Bandwidth is innite Transport cost is zero There is one administrator
13 / 28
13 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Types of distributed systems
Distributed computing systems Distributed information systems Distributed pervasive systems
14 / 28
14 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Distributed computing systems
Observation Many distributed systems are congured for High-Performance Computing Cluster Computing Essentially a group of high-end systems connected through a LAN: Homogeneous: same OS, near-identical hardware Single managing node
15 / 28
15 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Distributed computing systems
Master node Management application Parallel libs Local OS
Compute node Component of parallel application Local OS
Compute node Component of parallel application Local OS
Compute node Component of parallel application Local OS
Remote access network
Standard network High-speed network
16 / 28
16 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Distributed computing systems
Grid Computing The next step: lots of nodes from everywhere: Heterogeneous Dispersed across several organizations Can easily span a wide-area network Note To allow for collaborations, grids generally use virtual organizations. In essence, this is a grouping of users (or better: their IDs) that will allow for authorization on resource allocation.
17 / 28
17 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Distributed computing systems: Clouds
Software
aa Svc
Web services, multimedia, business apps Application Software framework (Java/Python/.Net) Storage (DB, File) Platforms Computation (VM), storage (block) Infrastructure CPU, memory, disk, bandwidth Hardware
Google Apps YouT ube Flickr
MS Azure
Amazon S3
Platform aa Svc
Amazon EC2
Infrastructure aa Svc
Datacenters
18 / 28
18 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Distributed computing systems: Clouds
Cloud computing Make a distinction between four layers: Hardware: Processors, routers, power and cooling systems. Customers normally never get to see these. Infrastructure: Deploys virtualization techniques. Evolves around allocating and managing virtual storage devices and virtual servers. Platform: Provides higher-level abstractions for storage and such. Example: Amazon S3 storage system offers an API for (locally created) les to be organized and stored in so-called buckets. Application: Actual applications, such as ofce suites (text processors, spreadsheet applications, presentation applications). Comparable to the suite of apps shipped with OSes.
19 / 28 19 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Distributed Information Systems
Observation The vast amount of distributed systems in use today are forms of traditional information systems, that now integrate legacy systems. Example: Transaction processing systems.
BEGIN TRANSACTION(server, transaction) READ(transaction, file-1, data) WRITE(transaction, file-2, data) newData := MODIFIED(data) IF WRONG(newData) THEN ABORT TRANSACTION(transaction) ELSE WRITE(transaction, file-2, newData) END TRANSACTION(transaction) END IF
Note Transactions form an atomic operation.
20 / 28 20 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Distributed information systems: Transactions
Model A transaction is a collection of operations on the state of an object (database, object composition, etc.) that satises the following properties (ACID) Atomicity: All operations either succeed, or all of them fail. When the transaction fails, the state of the object will remain unaffected by the transaction. Consistency: A transaction establishes a valid state transition. This does not exclude the possibility of invalid, intermediate states during the transactions execution. Isolation: Concurrent transactions do not interfere with each other. It appears to each transaction T that other transactions occur either before T , or after T , but never both. Durability: After the execution of a transaction, its effects are made permanent: changes to the state survive failures.
21 / 28 21 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Transaction processing monitor
Observation In many cases, the data involved in a transaction is distributed across several servers. A TP Monitor is responsible for coordinating the execution of a transaction
Server Reply Transaction Requests Request Client application Reply Reply TP monitor Reply Request Server Server Request
22 / 28
22 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Distr. info. systems: Enterprise application integration
Problem A TP monitor doesnt separate apps from their databases. Also needed are facilities for direct communication between apps.
Client application
Client application
Communication middleware
Server-side application
Server-side application
Server-side application
Remote Procedure Call (RPC) Message-Oriented Middleware (MOM)
23 / 28 23 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Distributed pervasive systems
Observation Emerging next-generation of distributed systems in which nodes are small, mobile, and often embedded in a larger system, characterized by the fact that the system naturally blends into the users environment. Three (overlapping) subtypes Ubiquitous computing systems: pervasive and continuously present, i.e., there is a continous interaction between system and user. Mobile computing systems: pervasive, but emphasis is on the fact that devices are inherently mobile. Sensor (and actuator) networks: pervasive, with emphasis on the actual (collaborative) sensing and actuation of the environment.
24 / 28 24 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Ubiquitous computing systems
Basic characteristics (Distribution) Devices are networked, distributed, and accessible in a transparent manner (Interaction) Interaction between users and devices is highly unobtrusive (Context awareness) The system is aware of a users context in order to optimize interaction (Autonomy) Devices operate autonomously without human intervention, and are thus highly self-managed (Intelligence) The system as a whole can handle a wide range of dynamic actions and interactions
25 / 28
25 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Mobile computing systems
Observation Mobile computing systems are generally a subclass of ubiquitous computing systems and meet all of the ve requirements. Typical characteristics Many different types of mobile divices: smart phones, remote controls, car equipment, and so on Wireless communication Devices may continuously change their location
setting up a route may be problematic, as routes can change frequently devices may easily be temporarily disconnected disruption-tolerant networks
26 / 28
26 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Sensor networks
Characteristics The nodes to which sensors are attached are: Many (10s-1000s) Simple (small memory/compute/communication capacity) Often battery-powered (or even battery-less)
27 / 28
27 / 28
Introduction
1.3 Types of distributed systems
Introduction
1.3 Types of distributed systems
Sensor networks as distributed systems
Sensor network Operator's site
Sensor data is sent directly to operator (a)
Each sensor can process and store data Operator's site Query
Sensor network
Sensors send only answers (b)
28 / 28 28 / 28
