《清华云计算课件-分布式计算.ppt》由会员分享，可在线阅读，更多相关《清华云计算课件-分布式计算.ppt（69页珍藏版）》请在三一办公上搜索。
1、Lecture 1 Introduction to Distributed Computing,Mass Data Processing Technology on Large Scale ClustersSummer,2007,Tsinghua University,All course material(slides,labs,etc)is licensed under the Creative Commons Attribution 2.5 License.Many thanks to Aaron Kimball&Sierra Michels-Slettvet for their ori
2、ginal version,1,Outline,2,Introduction to Distributed Systems,3,Computer Speedup,4,Moores Law:“The density of transistors on a chip doubles every 18 months,for the same cost”(1965),Image:Toms Hardware,Why slow down here?,Then,How to improve the performance?,Scope of Problems,5,Distributed Problems,R
3、endering multiple frames of high-quality animation,6,Image:DreamWorks Animation,Distributed Problems,Simulating several hundred or thousand characters,7,Happy Feet Kingdom Feature Productions;Lord of the Rings New Line Cinema,Distributed Problems,Indexing the web(Google)Simulating an Internet-sized
4、network for networking experiments(PlanetLab)Speeding up content delivery(Akamai),8,What is the key attribute that all these examples have in common?,PlanetLab,9,PlanetLab is a global research network that supports the development of new network services.,PlanetLab currently consists of 809 nodes at
5、 401 sites.,CDN-Akamai,10,Parallel vs.Distributed,Parallel computing can mean:Vector processing of data(SIMD)Multiple CPUs in a single computer(MIMD)Distributed computing is multiple CPUs across many computers(MIMD),11,A Brief History 1975-85,Parallel computing was favored in the early yearsPrimaril
6、y vector-based at firstGradually more thread-based parallelism was introduced,12,Cray 2 supercomputer(Wikipedia),A Brief History 1985-95,“Massively parallel architectures”start rising in prominenceMessage Passing Interface(MPI)and other libraries developedBandwidth was a big problem,13,A Brief Histo
7、ry 1995-Today,Cluster/grid architecture increasingly dominantSpecial node machines eschewed in favor of COTS technologiesWeb-wide cluster softwareCompanies like Google take this to the extreme(10,000 node clusters),14,Top 500,Architecture,15,Parallelization&Synchronization,16,Parallelization Idea,Pa
8、rallelization is“easy”if processing can be cleanly split into n units:,17,Parallelization Idea(2),18,In a parallel computation,we would like to have as many threads as we have processors.e.g.,a four-processor computer would be able to run four threads at the same time.,Parallelization Idea(3),19,Par
9、allelization Idea(4),20,Parallelization Pitfalls,But this model is too simple!How do we assign work units to worker threads?What if we have more work units than threads?How do we aggregate the results at the end?How do we know all the workers have finished?What if the work cannot be divided into com
10、pletely separate tasks?,21,What is the common theme of all of these problems?,Parallelization Pitfalls(2),Each of these problems represents a point at which multiple threads must communicate with one another,or access a shared resource.Golden rule:Any memory that can be used by multiple threads must
11、 have an associated synchronization system!,22,Whats Wrong With This?,23,Thread 1:void foo()x+;y=x;,Thread 2:void bar()y+;x+;,If the initial state is y=0,x=6,what happens after these threads finish running?,Multithreaded=Unpredictability,24,When we run a multithreaded program,we dont know what order
12、 threads run in,nor do we know when they will interrupt one another.,Thread 1:void foo()eax=memx;inc eax;memx=eax;ebx=memx;memy=ebx;,Thread 2:void bar()eax=memy;inc eax;memy=eax;eax=memx;inc eax;memx=eax;,Many things that look like“one step”operations actually take several steps under the hood:,Mult
13、ithreaded=Unpredictability,This applies to more than just integers:Pulling work units from a queueReporting work back to master unitTelling another thread that it can begin the“next phase”of processing All require synchronization!,25,Synchronization Primitives,A synchronization primitive is a specia
14、l shared variable that guarantees that it can only be accessed atomically.Hardware support guarantees that operations on synchronization primitives only ever take one step,26,Semaphores,A semaphore is a flag that can be raised or lowered in one stepSemaphores were flags that railroad engineers would
15、 use when entering a shared track,27,Only one side of the semaphore can ever be red!(Can both be green?),Semaphores,set()and reset()can be thought of as lock()and unlock()Calls to lock()when the semaphore is already locked cause the thread to block.Pitfalls:Must“bind”semaphores to particular objects
16、;must remember to unlock correctly,28,The“corrected”example,29,Thread 1:void foo()sem.lock();x+;y=x;sem.unlock();,Thread 2:void bar()sem.lock();y+;x+;sem.unlock();,Global var“Semaphore sem=new Semaphore();”guards access to x&y,Condition Variables,A condition variable notifies threads that a particul
17、ar condition has been met Inform another thread that a queue now contains elements to pull from(or that its empty request more elements!)Pitfall:What if nobodys listening?,30,The Final Example,31,Thread 1:void foo()sem.lock();x+;y=x;fooDone=true;sem.unlock();fooFinishedCV.notify();,Thread 2:void bar
18、()sem.lock();if(!fooDone)fooFinishedCV.wait(sem);y+;x+;sem.unlock();,Global vars:Semaphore sem=new Semaphore();ConditionVar fooFinishedCV=new ConditionVar();boolean fooDone=false;,Barriers,A barrier knows in advance how many threads it should wait for.Threads“register”with the barrier when they reac
19、h it,and fall asleep.Barrier wakes up all registered threads when total count is correctPitfall:What happens if a thread takes a long time?,32,Too Much Synchronization?Deadlock,33,Synchronization becomes even more complicated when multiple locks can be usedCan cause entire system to“get stuck”,Threa
20、d A:semaphore1.lock();semaphore2.lock();/*use data guarded by semaphores*/semaphore1.unlock();semaphore2.unlock();,Thread B:semaphore2.lock();semaphore1.lock();/*use data guarded by semaphores*/semaphore1.unlock();semaphore2.unlock();,(Image:RPI CSCI.4210 Operating Systems notes),The Moral:Be Carefu
21、l!,Synchronization is hardNeed to consider all possible shared stateMust keep locks organized and use them consistently and correctlyKnowing there are bugs may be tricky;fixing them can be even worse!Keeping shared state to a minimum reduces total system complexity,34,Fundamentals of Networking,35,S
22、ockets:The Internet=tubes?,A socket is the basic network interfaceProvides a two-way“pipe”abstraction between two applicationsClient creates a socket,and connects to the server,who receives a socket representing the other side,36,Ports,Within an IP address,a port is a sub-address identifying a liste
23、ning programAllows multiple clients to connect to a server at once,37,Example:Web Server(1/3),38,The server creates a listener socket attached to a specific port.80 is the agreed-upon port number for web traffic.,Example:Web Server(2/3),39,The client-side socket is still connected to a port,but the
24、OS chooses a random unused port numberWhen the client requests a URL(e.g.,“”),its OS uses a system called DNS to find its IP address.,Example:Web Server(3/3),40,Listener is ready for more incoming connections,while we process the current connection in parallel,Example:Web Server,41,What makes this w
25、ork?,Underneath the socket layer are several more protocolsMost important are TCP and IP(which are used hand-in-hand so often,theyre often spoken of as one protocol:TCP/IP),42,Even more low-level protocols handle how data is sent over Ethernet wires,or how bits are sent through the air using 802.11
26、wireless,IP:The Internet Protocol,Defines the addressing scheme for computers Encapsulates internal data in a“packet”Does not provide reliabilityJust includes enough information for the data to tell routers where to send it,43,TCP:Transmission Control Protocol,Built on top of IPIntroduces concept of
27、“connection”Provides reliability and ordering,44,Why is This Necessary?,Not actually tube-like“underneath the hood”Unlike phone system(circuit switched),the packet switched Internet uses many routes at once,45,Networking Issues,If a party to a socket disconnects,how much data did they receive?Did th
28、ey crash?Or did a machine in the middle?Can someone in the middle intercept/modify our data?Traffic congestion makes switch/router topology important for efficient throughput,46,Remote Procedure Calls(RPC),47,How RPC Doesnt Work,Regular client-server protocols involve sending data back and forth acc
29、ording to a shared state,48,Client:Server:HTTP/1.0 index.html GET 200 OK Length:2400(file data)HTTP/1.0 hello.gif GET 200 OK Length:81494,Remote Procedure Call,RPC servers will call arbitrary functions in dll,exe,with arguments passed over the network,and return values back over network,49,Client:Se
30、rver:foo.dll,bar(4,10,“hello”)“returned_string”foo.dll,baz(42)err:no such function,Possible Interfaces,RPC can be used with two basic interfaces:synchronous and asynchronousSynchronous RPC is a“remote function call”client blocks and waits for return valAsynchronous RPC is a“remote thread spawn”,50,S
31、ynchronous RPC,51,Asynchronous RPC,52,Asynchronous RPC 2:Callbacks,53,Wrapper Functions,Writing rpc_call(foo.dll,bar,arg0,arg1.)is poor formConfusing codeBreaks abstractionWrapper function makes code cleanerbar(arg0,arg1);/just write this;calls“stub”,54,More Design Considerations,Who can call RPC fu
32、nctions?Anybody?How do you handle multiple versions of a function?Need to marshal objectsHow do you handle error conditions?Numerous protocols:DCOM,CORBA,JRMI,55,Transaction Processing Systems,56,TPS:Definition,A system that handles transactions coming from several sources concurrentlyTransactions a
33、re“events that generate and modify data stored in an information system for later retrieval”*,57,*,Key Features of TPS:ACID,“ACID”is the acronym for the features a TPS must support:Atomicity A set of changes must all succeed or all failConsistency Changes to data must leave the data in a valid state
34、 when the full change set is appliedIsolation The effects of a transaction must not be visible until the entire transaction is completeDurability After a transaction has been committed successfully,the state change must be permanent.,58,Atomicity&Durability,What happens if we write half of a transac
35、tion to disk and the power goes out?,59,Logging:The Undo Buffer,Database writes to log the current values of all cells it is going to overwriteDatabase overwrites cells with new valuesDatabase marks log entry as committedIf db crashes during(2),we use the log to roll back the tables to prior state,6
36、0,Consistency:Data Types,Data entered in databases have rigorous data types associated with them,and explicit rangesDoes not protect against all errors(entering a date in the past is still a valid date,etc),but eliminates tedious programmer concerns,61,Consistency:Foreign Keys,Database designers dec
37、lare that fields are indices into the keys of another tableDatabase ensures that target key exists before allowing value in source field,62,Isolation,Using mutual-exclusion locks,we can prevent other processes from reading data we are in the process of writingWhen a database is prepared to commit a
38、set of changes,it locks any records it is going to update before making the changes,63,Faulty Locking,Locking alone does not ensure isolation!Changes to table A are visible before changes to table B this is not an isolated transaction,64,Two-Phase Locking,After a transaction has released any locks,i
39、t may not acquire any new locksEffect:The lock set owned by a transaction has a“growing”phase and a“shrinking”phase,65,Relationship to Distributed Comp,At the heart of a TPS is usually a large database serverSeveral distributed clients may connect to this server at points in timeDatabase may be spre
40、ad across multiple servers,but must still maintain ACID,66,Conclusions,Weve seen 3 layers that make up a distributed systemDesigning a large distributed system involves engineering tradeoffs at each of these levelsAppreciating subtle concerns at each level requires diving past the abstractions,but abstractions are still useful in general,67,Discussion,Distributed System Design,68,Thank You,Questions and Answers!,69,
