Transcription
Chapter 1:Distributed Systems:What is a distributed system?Fall 2008Jussi Kangasharju
Course Goals and Content Distributed systems and their: Basic Mainconceptsissues, problems, and solutions Structuredand functionality Content: Distributedsystems (Tanenbaum, Ch. 1)- Architectures, goal, challenges- Where our solutions are applicable Synchronization: Replicas FaultTime, coordination, decision making (Ch. 5)and consistency (Ch. 6)tolerance (Ch. 7) Chapters refer to Tanenbaum bookKangasharju: Distributed SystemsOctober 23, 082
Course Material Tanenbaum, van Steen: Distributed Systems, Principlesand Paradigms; Prentice Hall 2002 Coulouris, Dollimore, Kindberg: Distributed Systems,Concepts and Design; Addison-Wesley 2005 Lecture slides on course website NOTsufficient by themselves Helpto see what parts in book are most relevantKangasharju: Distributed SystemsOctober 23, 083
Course Exams Normal way (recommended) Exercises,home exercises, course exam Grading: Exam48 points Exercises Homeexercises 6 points (3 exercises) Grading Need 5012 points ( 20 exercises, scaled to 0—12)based on 60 point maximum30 points to pass with minimum 16 points in exampoints will give a 5 Possible to take as separate examKangasharju: Distributed SystemsOctober 23, 084
Exercises Weekly exercises: Smallerassignments Home exercises 1study diary, 2 design exercises Duedates will be announced later Studydiary individual work DesignKangasharju: Distributed Systemsexercises can be done in groups of up to 3October 23, 085
People Jussi Kangasharju Lectures: OfficeMon 14-16 and Thu 10-12 in D122hour: Tue 12-13 or ask for appointment by email Mika Karlstedt Exercisegroups:- 1. Mika Karlstedt Tue 12-14 in C221 (in English)- 2. Mika Karlstedt Thu 12-14 in CK111 Homeexercises Officehour: During exercises or ask appointment by emailKangasharju: Distributed SystemsOctober 23, 086
Questions?Kangasharju: Distributed SystemsOctober 23, 087
Chapter Outline Defining distributed system Examples of distributed systems Why distribution? Goals and challenges of distributed systems Where is the borderline between a computer and adistributed system? Examples of distributed architecturesKangasharju: Distributed SystemsOctober 23, 088
Definition of a Distributed SystemA distributed system isa collection of independent computersthat appears to its usersas a single coherent system. or .as a single system.Kangasharju: Distributed SystemsOctober 23, 089
Examples of Distributed SystemsThe Internet: net of netsglobal access to “everybody”(data, service, otheractor; open ended) enormoussize (openintranetISPended) nosingle authority communicationbackbonetypes- interrogation,announcement,streamsatellite linkdesktop computer:server:network link:CoDoKi, Fig. 1.1- data, audio, videoFigure 1.1 A typical portion of the InternetKangasharju: Distributed SystemsOctober 23, 0810
Examples of Distributed SystemsIntranets ( CoDoKi, Fig. 1.2) a single authority protected access- a firewall- total isolation may be worldwide typical services:- infrastructure services:file service, nameservice- application servicesCoDoKi, Fig. 1.2Figure 1.2 A typical intranetKangasharju: Distributed SystemsOctober 23, 0811
Examples of Distributed SystemsMobile and ubiquitouscomputing ( CoDoKi Fig 1.3 ) Portable devices laptops handheld devices wearable devices devices embedded in appliances Mobile computing Location-aware computing Ubiquitous computing, pervasiveFigure 1.3 Portable and handheld devices in a distributed systemcomputingKangasharju: Distributed SystemsCoDoKi, Fig. 1.3October 23, 0812
Mobile Ad Hoc -NetworksProblems, e.g.:- reliable multicast- group managementKangasharju: Distributed SystemsMobile nodes come and goNo infrastructure- wireless data communication- multihop networking- long, nondeterministic dc delaysOctober 23, 0813
Resource Sharing and the Web Hardware resources (reducecosts) Data resources (sharedusage of information)http://www.google.com/search?q kindbergwww.google.comBrowsersWeb serversInternetwww.cdk3.nethttp://www.cdk3.net/ Service resources search engineswww.w3c.orgFile system ative working Service vs. server (node orprocess )Kangasharju: Distributed rotocolsCoDoKi, Fig. 1.4Mastering openness HTML URL HTTPFigure 1.4 Web servers and web browsersOctober 23, 0814
Examples of Distributed Systems, 4Distributed application one single “system” one or several autonomous subsystems a collection of processors parallel processing increased performance, reliability, faulttolerance partitioned or replicated data increased performance, reliability, fault toleranceDependable systems, grid systems, enterprise systemsKangasharju: Distributed SystemsOctober 23, 0815
Why Distribution?Sharing of information and servicesPossibility to add components improvesavailabilityreliability, fault toleranceperformancescalabilityFacts of life: history, geography, organizationKangasharju: Distributed SystemsOctober 23, 0816
Goals and challenges fordistributed systems
Goals Making resources accessible Distribution transparency Openness Scalability Security System design requirementsKangasharju: Distributed SystemsOctober 23, 0818
Challenges for Making Resources Accessible Naming Access control Security Availability Performance Mutual exclusion of users, fairness Consistency in some casesKangasharju: Distributed SystemsOctober 23, 0819
Challenges for Transparency The fundamental idea: a collection of independent,autonomous actors Transparency concealment of distribution user’s viewpoint: a single unified systemKangasharju: Distributed SystemsOctober 23, 0820
TransparenciesTransparencyDescriptionAccessHide differences in data representation and how a resource is accessedLocationHide where a resource is located (*)Hide that a resource may move to another location (*)Migration(the resource does not notice)Hide that a resource may be moved to another location (*)Relocationwhile in use (the others don’t notice)ReplicationHide that a resource is replicatedConcurrencyHide that a resource may be shared by several competitive usersFailureHide the failure and recovery of a resourcePersistenceHide whether a (software) resource is in memory or on disk(*) Notice the various meanings of ”location” : network address (several layers) ; geographical addressKangasharju: Distributed SystemsOctober 23, 0821
Challenges for Transparencies replications and migration cause need for ensuringconsistency and distributed decision-making failure modes concurrency heterogeneityKangasharju: Distributed SystemsOctober 23, 0822
Figure 2.10Omission and arbitrary failuresClass of failure Affects DescriptionFail-stopProcess Process halts and remains halted. Other processes maydetect this state.CrashProcess Process halts and remains halted. Other processes maynot be able to detect this state.OmissionChannel A message inserted in an outgoing message buffer neverarrives at the other end’s incoming message buffer.Send-omission Process A process completes send,but the message is not putin its outgoing message buffer.ReceiveProcess A message is put in a process’s incoming messagebuffer, but that process does not receive it.omissionArbitraryProcess orProcess/channel exhibits arbitrary behaviour: it may(Byzantine)channel send/transmit arbitrary messages at arbitrary times,commit omissions; a process may stop or take anincorrect step.Kangasharju: Distributed SystemsOctober 23, 0823
Figure 2.11Timing failuresClass of Failure annelKangasharju: Distributed SystemsDescriptionProcess’s local clock exceeds the bounds on itsrate of drift from real time.Process exceeds the bounds on the intervalbetween two steps.A message’s transmission takes longer than thestated bound.October 23, 0824
Failure Handling More components increased fault rate Increased possibilities more noredundancy more possibilities for fault tolerancecentralized control no fatal failure Issues Detecting Maskingfailuresfailures Recoveryfrom failures Toleratingfailures Redundancy New: partial failuresKangasharju: Distributed SystemsOctober 23, 0825
Concurrency Concurrency: Severalsimultaneous users integrity of data- mutual exclusion- synchronization- ext: transaction processing in data bases Replicateddata: consistency of information? Partitioneddata: how to determine the state of the system? Orderof messages? There is no global clock!Kangasharju: Distributed SystemsOctober 23, 0826
Consistency Maintenance Update . Replication . Cache . Failure . Clock . User interface .Kangasharju: Distributed Systems. consistencyOctober 23, 0827
Heterogeneity Heterogeneity of networks computerhardware operatingsystems programminglanguages implementationsof different developers Portability, interoperability Mobile code, adaptability (applets, agents) Middleware (CORBA etc) Degree of transparency? Latency? Location-basedservices?Kangasharju: Distributed SystemsOctober 23, 0828
Challenges for Openness Openness facilitates interoperability,portability, extensibility, adaptivity Activities addresses extensions:new components re-implementations(by independent providers) Supported by publicinterfaces standardizedKangasharju: Distributed Systemscommunication protocolsOctober 23, 0829
Challenges for Scalability Scalability The system will remain effective when there is a significant increase in numberof resources numberof users Thearchitecture and the implementation must allow it Thealgorithms must be efficient under the circumstances tobe expected Example:Kangasharju: Distributed Systemsthe InternetOctober 23, 0830
Challenges: Scalability (cont.) Controlling the cost of physical resources Controlling performance loss Preventing software resources running out Avoiding performance bottlenecks Mechanisms (implement functions) & Policies (how to usethe mechanisms) Scaling solutions asyncronouscommunication, decreased messaging (e.g.,forms) caching(all sorts of hierarchical memories: data is closer tothe user no wait / assumes rather stable data!) distributioni.e. partitioning of tasks or information (domains)(e.g., DNS)Kangasharju: Distributed SystemsOctober 23, 0831
Challenges for Security Security: confidentiality, integrity, availability Vulnerable components (Fig. 2.14) channels (links – end-to-end paths)processes (clients, servers, outsiders)CoDoKi, Fig. 2.14Copy of m Threats information leakageintegrity violationdenial of serviceillegitimate usageThe enemyProcess pmm’ProcessqCommunication channelFigure 2.14 The enemyCurrent issues:denial-of-service attacks, security of mobile code, information flow;open wireless ad-hoc environmentsKangasharju: Distributed SystemsOctober 23, 0832
Threats Threats to channels (Fig. 2.14) eavesdropping (data, tampering, replaying masquerading denial of serviceCoDoKi, Fig. 2.14Copy of mtraffic)The enemyProcess pm’ProcessqCommunication channel Threats to processes (Fig. 2.13) server:mclient’s identity; client: server’sFigure 2.14 The enemyidentity unauthorizedaccess (insecureaccess model) unauthorizedinformation flow(insecure flow model)Kangasharju: Distributed SystemsFigure 2.13 Objects and principalsOctober 23, 08CoDoKi, Fig. 2.1333
Defeating Security Threats Techniques cryptography authentication accesscontrol techniques- intranet: firewalls- services, objects: access control lists, capabilities Policies access latticecontrol modelsmodels informationflow models Leads to: secure channels, secure processes, controlledaccess, controlled flowsKangasharju: Distributed SystemsOctober 23, 0834
Environment challenges A distributed system: HW/ SW components in different nodes componentscommunicate (using messages) componentscoordinate actions (using messages) Distances between nodes vary intime: from msecs to weeks inspace: from mm’s to Mm’s independability Autonomous independent actors ( even independentfailures!)No global clockGlobal state information not possibleKangasharju: Distributed SystemsOctober 23, 0835
Challenges: Design Requirements Performance issues responsiveness throughput loadsharing, load balancing issue:algorithm vs. behavior Quality of service correctness reliability,(in nondeterministic environments)availability, fault tolerance security performance adaptabilityKangasharju: Distributed SystemsOctober 23, 0836
Where is the borderline between acomputer and distributed system?
Hardware Concepts Characteristics which affect the behavior of softwaresystems The platform . theindividual nodes (”computer”, ”processor”) communication organizationbetween two nodesof the system (network of nodes) . and its characteristics capacityof nodes capacity(throughput, delay) of communication links reliabilityof communication (and of the nodes) Which ways to distribute an application are feasibleKangasharju: Distributed SystemsOctober 23, 0838
Basic Organizations of a Node1.6Different basic organizations and memories in distributed computersystemsKangasharju: Distributed SystemsOctober 23, 0839
Multiprocessors (1)1.7A bus-based multiprocessor.Essential characteristics for software design fast and reliable communication (shared memory) cooperation at ”instruction level” possible bottleneck: memory (especially the ”hot spots”)Kangasharju: Distributed SystemsOctober 23, 0840
Multiprocessors (2)1.8a) A crossbar switchb) An omega switching networkA possible bottleneck: the switchKangasharju: Distributed SystemsOctober 23, 0841
Homogeneous Multicomputer Systems1-9a) Gridb) HypercubeA new design aspect: locality at the network levelKangasharju: Distributed SystemsOctober 23, 0842
General Multicomputer Systems Hardware: see Ch1 (internet etc.) Loosely connected systems nodes:autonomous communication: slow and vulnerablecooperation at ”service level” Application architectures multiprocessorsystems: parallel computation multicomputersystems: distributed systems (how are parallel, concurrent, and distributed systemsdifferent?)Kangasharju: Distributed SystemsOctober 23, 0843
Software ConceptsSystemDescriptionTightly-coupled operating system forDOSmultiprocessors and homogeneousmulticomputersMain GoalHide and managehardware resourcesLoosely-coupled operating system forOffer local services toheterogeneous multicomputers (LAN and WAN)remote clientsMiddle-Additional layer atop of NOS implementingProvide distributionwaregeneral-purpose servicestransparencyNOSDOS: Distributed OS; NOS: Network OSKangasharju: Distributed SystemsOctober 23, 0844
History of distributed systems RPC by Birel &Nelson -84 network operating systems, distributed operating systems,distributed computing environments in mid-1990;middleware referred to relational databases Distributed operating systems – ”single computer” Distributedprocess management- process lifecycle, inter-process communication, RPC,messaging Distributedresource management- resource reservation and locking, deadlock detection Distributedservices- distributed file systems, distributed memory, hierarchicalglobal namingKangasharju: Distributed SystemsOctober 23, 0845
History of distributed systems late 1990’s distribution middleware well-known generic,with distributed services supportsstandard transport protocols and provides standardAPI availablefor multiple hardware, protocol stacks, operatingsystems e.g.,DCE, COM, CORBA present middlewares for multimedia,realtime computing, telecom ecommerce,Kangasharju: Distributed Systemsadaptive / ubiquitous systemsOctober 23, 0846
Misconceptions tackled The network is reliable The network is secure The network is homogeneous The topology does not change Latency is zero Bandwith is infinite Transport cost is zero There is one administrator There is inherent, shared knowledgeKangasharju: Distributed SystemsOctober 23, 0847
Multicomputer Operating Systems (1)1.14General structure of a multicomputer operating systemKangasharju: Distributed SystemsOctober 23, 0848
Multicomputer Operating Systems (2)1.15Alternatives for blocking and buffering in message passing.Kangasharju: Distributed SystemsOctober 23, 0849
Distributed Shared Memory Systems (1)a)Pages of address spacedistributed among fourmachinesb)Situation after CPU 1references page 10c)Situation if page 10 isread only and replicationis usedKangasharju: Distributed SystemsOctober 23, 0850
Distributed Shared Memory Systems (2)1.18False sharing of a page between two independent processes.Kangasharju: Distributed SystemsOctober 23, 0851
Network Operating System (1)General structure of a network operating system.1-19Kangasharju: Distributed SystemsOctober 23, 0852
Network Operating System (2)1-20Two clients and a server in a network operating system.Kangasharju: Distributed SystemsOctober 23, 0853
Network Operating System (3)1.21Different clients may mount the servers in different places.Kangasharju: Distributed SystemsOctober 23, 0854
Software Layers Platform: computer & operating system & . Middleware: mask heterogeneity of lower levels(at least: provide a homogeneous “platform”) maskseparation of platform components- implement communication- implement sharing of resources Applications: e-mail, www-browsers, Kangasharju: Distributed SystemsOctober 23, 0855
Positioning Middleware1-22General structure of a distributed system as middleware.Kangasharju: Distributed SystemsOctober 23, 0856
Middleware Operations offered by middleware RMI,group communication, notification, replication, (SunRPC, CORBA, Java RMI, Microsoft DCOM, .) Services offered by middleware naming,security, transactions, persistent storage, Limitations ignoranceof special application-level requirementsEnd-to-end argument: Communication of application-level peers at both ends isrequired for reliabilityKangasharju: Distributed SystemsOctober 23, 0857
MiddlewareHost 1Host eware APIMiddleware APIMiddlewareMiddlewareOperating System APIOperating System APIcommunicationprocessingstorageOperating systemcommunicationprocessingstorageOperating systemnetworkKangasharju: Distributed SystemsOctober 23, 0858
MiddlewareMiddleware is a class of software technologies designed tohelp manage the complexity and heterogeneity inherent indistributed systems. It is defined as a layer of softwareabove the operating system but below the applicationprogram that provides a common programmingabstraction across a distributed system.Bakken 2001: Encyclopedia entryKangasharju: Distributed SystemsOctober 23, 0859
Middleware and Openness1.23In an open middleware-based distributed system, the protocols used byeach middleware layer should be the same, as well as the interfacesthey offer to applications.Kangasharju: Distributed SystemsOctober 23, 0860
Comparison between SystemsDistributed OSMiddleware-basedItemNetwork OSOSMultiproc.Multicomp.Degree of transparencyVery HighHighLowHighSame OS on all nodesYesYesNoNoNumber of copies of OS1NNNBasis for communicationShared memoryMessagesFilesModel specificResource managementGlobal, centralGlobal, distributedPer nodePer ClosedOpenOpenKangasharju: Distributed SystemsOctober 23, 0861
More examples on distributedsoftware architectures
Architectural Models Architectural models provide a high-level view of thedistribution of functionality between system componentsand the interaction relationships between them Architectural models define components(logical components deployed at physicalnodes) communication Criteria performance reliability scalability,Kangasharju: Distributed Systems.October 23, 0863
Client-Server Client-server model: CoDoKi, Fig. 2.2 Service provided by multipleservers: Fig. 2.3 Needed: name service trading/broker service browsing serviceFigure 2.2 Clients invoke individual servers CoDoKi, Fig. 2.2 Proxy servers and caches, Fig. 2.4CoDoKi, Fig. 2.4CoDoKi, Fig.Figure2.3 2.3 A service provided by multiple serversFigure 2.4Web proxy serverKangasharju: DistributedSystemsOctober 23, 0864
An Example Client and Server (1)The header.h file used by the client and server.Kangasharju: Distributed SystemsOctober 23, 0865
An Example Client and Server (2)A sample server.Kangasharju: Distributed SystemsOctober 23, 0866
An Example Client and Server (3)1-27 bA client using the server to copy a file.Kangasharju: Distributed SystemsOctober 23, 0867
Processing Level1-28The general organization of an Internet search engine into three different layersKangasharju: Distributed SystemsOctober 23, 0868
Multitiered Architectures (1)1-29Alternative client-server organizations.Kangasharju: Distributed SystemsOctober 23, 0869
Multitiered Architectures (2)Client - server: generalizationsrequestnode 1Anode 2Bnode 3replynode 4A client: node 1server: node 2B client: node 2server: node 3Kangasharju: Distributed Systemsthe concept is relatedto communicationnot to nodesOctober 23, 0870
Multitiered Architectures (3)1-30An example of a server acting as a client.Kangasharju: Distributed SystemsOctober 23, 0871
Variations on the Client-Server model Mobile codethe service is provided using a procedure executed by a process in the servernode downloaded to the client and executedlocally Fig. 2.6 push service: the initiator is the server Mobile agents “a running program” (code & data)travels needed: an agent platformKangasharju: Distributed SystemsCoDoKi, Fig. 2.6Figure 2.6 Web appletsOctober 23, 0872
Variations on the Client-Server model (cont.) Network computers “diskless workstations” needed code and data downloadedfor execution Thin clients “PC”: user interface server: execution of example: Unix X-11computations (Fig. 2.7)window systemCompute serverNetwork computer or PCThinClientnetworkApplicationProcessFigure 2.7 Thin clients and compute serversKangasharju: Distributed SystemsCoDoKi, Fig. 2.7October 23, 0873
Variations on the Client-Server model (cont.) Mobile devices andspontaneous networks,ad hoc networks (Fig.2.8) Needed easy connection to alocal networkeasy integration withlocal servicesgatewaylimited connectivitysecurity and privacy Discovery serviceAlarmserviceInternet Problems MusicserviceDiscoveryserviceHotel wirelessnetworkCameratwo interfaces:registration, lookupTV/PCLaptopPDAGuestsdevicesFigure 2.8 Spontaneous networking in a hotelKangasharju: Distributed SystemsOctober 23, 0874
Modern Architectures1-31An example of horizontal distribution of a Web service.Kangasharju: Distributed SystemsOctober 23, 0875
Other Architectures Andrews paradigms:filter: a generalization of producers andconsumersheartbeatprobe echo Peer to peerCoDoKi, Fig. 2.5Kangasharju: Distributed SystemsOctober 23, 0876
Chapter Summary Introduction into distributed systems Challenges and goals of distributing Examples of distributed systemsKangasharju: Distributed SystemsOctober 23, 0877
Course Goals and Content Distributed systems and their: Basic concepts Main issues, problems, and solutions Structured and functionality Content: Distributed systems (Tanenbaum, Ch. 1) - Architectures, goal, challenges - Where our solutions are applicable Synchronization: Time, coordination, decision making (Ch. 5)
