清華云計(jì)算課件-分布式計(jì)算

1、Lecture 1 Introduction to Distributed Computing,Mass Data Processing Technology on Large Scale Clusters Summer, 2007, Tsinghua University,All course material (slides, labs, etc) is licensed under the Creative Commons Attribution 2.5 License . Many thanks to Aaron Kimball Lord of the Rings New Line C

2、inema,Distributed Problems,Indexing the web (Google) Simulating an Internet-sized 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

3、the development of new network services.,PlanetLab currently consists of 809 nodes at 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 compute

4、rs (MIMD),11,A Brief History 1975-85,Parallel computing was favored in the early years Primarily vector-based at first Gradually more thread-based parallelism was introduced,12,Cray 2 supercomputer (Wikipedia),A Brief History 1985-95,“Massively parallel architectures” start rising in prominence Mess

5、age Passing Interface (MPI) and other libraries developed Bandwidth was a big problem,13,A Brief History 1995-Today,Cluster/grid architecture increasingly dominant Special node machines eschewed in favor of COTS technologies Web-wide cluster software Companies like Google take this to the extreme (1

6、0,000 node clusters),14,Top 500, Architecture,15,Parallelization 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 threads run i

7、n, 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

8、under the hood:,Multithreaded = Unpredictability,This applies to more than just integers: Pulling work units from a queue Reporting work back to master unit Telling another thread that it can begin the “next phase” of processing All require synchronization!,25,Synchronization Primitives,A synchroniz

9、ation primitive is a special 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 step Semaphores were flags

10、that railroad engineers would 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

11、“bind” semaphores to particular objects; 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 x+; y = x; fooD

12、one = true; sem.unlock(); fooFinishedCV.notify(); ,Thread 2: void bar() 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

13、 how many threads it should wait for. Threads “register” with the barrier when they reach it, and fall asleep. Barrier wakes up all registered threads when total count is correct Pitfall: What happens if a thread takes a long time?,32,Barrier,Too Much Synchronization? Deadlock,33,Synchronization bec

14、omes even more complicated when multiple locks can be used Can cause entire system to “get stuck”,Thread A: semaphore1.lock(); semaphore2.lock(); /* use data guarded by semaphores */ semaphore1.unlock(); semaphore2.unlock();,Thread B: semaphore2.lock(); semaphore1.lock(); /* use data guarded by sema

15、phores */ semaphore1.unlock(); semaphore2.unlock();,(Image: RPI CSCI.4210 Operating Systems notes),The Moral: Be Careful!,Synchronization is hard Need to consider all possible shared state Must keep locks organized and use them consistently and correctly Knowing there are bugs may be tricky; fixing

16、them can be even worse! Keeping shared state to a minimum reduces total system complexity,34,Fundamentals of Networking,35,Sockets: The Internet = tubes?,A socket is the basic network interface Provides a two-way “pipe” abstraction between two applications Client creates a socket, and connects to th

17、e server, who receives a socket representing the other side,36,Ports,Within an IP address, a port is a sub-address identifying a listening program Allows 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.

18、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 OS chooses a random unused port number When the client requests a URL (e.g., “”), its OS uses a system called DNS to find its IP address.,Example: Web Server (

19、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 work?,Underneath the socket layer are several more protocols Most important are TCP and IP (which are used hand-in-hand so often, theyre often spoken of

20、 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 wireless,IP: The Internet Protocol,Defines the addressing scheme for computers Encapsulates internal data in a “packet” Does not provide reliabili

21、ty Just includes enough information for the data to tell routers where to send it,43,TCP: Transmission Control Protocol,Built on top of IP Introduces concept of “connection” Provides reliability and ordering,44,Why is This Necessary?,Not actually tube-like “underneath the hood” Unlike phone system (

22、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 they crash? Or did a machine in the middle? Can someone in the middle intercept/modify our data? Traffic congestion makes switch/route

23、r 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 according 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 O

24、K 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: Server: foo.dll,bar(4, 10, “hello”) “returned_string” foo.dll,baz(42) err: no such function ,Possible Interfaces,RPC ca

25、n be used with two basic interfaces: synchronous and asynchronous Synchronous RPC is a “remote function call” client blocks and waits for return val Asynchronous RPC is a “remote thread spawn”,50,Synchronous RPC,51,Asynchronous RPC,52,Asynchronous RPC 2: Callbacks,53,Wrapper Functions,Writing rpc_ca

26、ll(foo.dll, bar, arg0, arg1.) is poor form Confusing code Breaks abstraction Wrapper function makes code cleaner bar(arg0, arg1); /just write this; calls “stub”,54,More Design Considerations,Who can call RPC functions? Anybody? How do you handle multiple versions of a function? Need to marshal objec

27、ts How 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 concurrently Transactions are “events that generate and modify data stored in an information system for lat

28、er retrieval”*,57,* /wiki/Transaction_Processing_System,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 fail Consistency Changes to data must leave the data in a valid state when the full ch

29、ange set is applied Isolation The effects of a transaction must not be visible until the entire transaction is complete Durability After a transaction has been committed successfully, the state change must be permanent.,58,Atomicity & Durability,What happens if we write half of a transaction to disk

30、 and the power goes out?,59,Logging: The Undo Buffer,Database writes to log the current values of all cells it is going to overwrite Database overwrites cells with new values Database marks log entry as committed If db crashes during (2), we use the log to roll back the tables to prior state,60,Cons

31、istency: Data Types,Data entered in databases have rigorous data types associated with them, and explicit ranges Does 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 declare that fields are indices into the keys of another table Database 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 writing When a datab