kbirman ams03

50 %
50 %
Information about kbirman ams03

Published on October 30, 2007

Author: Nellwyn

Source: authorstream.com

Navigating in the Storm:  Navigating in the Storm Ken Birman, Robbert van Renesse, Werner Vogels Dept. of Computer Science Cornell University Autonomic Computing:  Autonomic Computing A challenge both technically but also from a business perspective Suppose someone came along with a major advance in autonomic technology Would we really adopt it? Most COTS platforms have their issues, yet “work” well enough “Killer app” for autonomic market? Lacking autonomic tools…:  Lacking autonomic tools… Web Services availability problems WS goal is to give instant response from legacy back-end systems that may run in batches “Web site not responding”… What to do? Grid applications may find it hard to track down appropriately configured nodes Issue is one of scale… arises with lots of nodes, not just a handful And the grid needs to administer itself Autonomic tools could solve such problems Why might such tools help?:  Why might such tools help? In these (and other new areas, such as sensor networks and large-scale data mining) applications are expected to Seek out appropriate resources Self-repair after disruption Do so automatically Match work load to available capacity We’re solving new problems with new tools, not trying to fix old, very complex problems Grid Computing example:  Grid Computing example Doctor Kildare works in the Cayuga Medical Center in Ithaca She does a CT scan on a patient with a head injury Wants to run a new generation of computationally intensive tools to assist her in the procedure to stabilize this patient Then may need to find a specialist who can consult on this situation Grid Computing example:  Grid Computing example In the past, Cayuga Medical needed a dedicated computer for this task With Grid Computing Should be able to grab resources on a farm (perhaps operated by IBM or some other company), run the application, get the results over the network Cayuga Medical spends far less money But need confidence in the solution To run “reliably” must…:  To run “reliably” must… Automatically find machines on which the right software is running, with the right revision level for this use Perhaps there are intermediate data sets that we need to access Perhaps that software, in turn, will need to use other services (like a specific database system) Communication latencies need to be low How could grid ever know enough about her application to solve such problems? Grid capability implied?:  Grid capability implied? The grid should have a way to Allow an application the grid has never seen before… … to “view” a pool of hardware in a new and application-specific way … that lets the application express a preference to run on appropriate nodes Sounds like a database problem Beyond basics…:  Beyond basics… We also need to sense and adapt if disruption occurs For example, a failure or a network problem… this are more common than one might think And need to “parameterize” the run based on the configuration we find We lack the right tools!:  We lack the right tools! Today, our applications navigate in the dark They lack a way to find things They lack a way to sense system state There are no rules for adaptation, if/when needed In effect: We are starting to build very big systems, yet doing so in the usual client-server manner This denies applications any information about system state, configuration, loads, etc Astrolabe:  Astrolabe Astrolabe is our information monitoring and replication architecture It has three components Mariner: a novel kind of “virtual database” Multicast: for faster “few to many” data transfer patterns Kelips: A fast “lookup” mechanism First focus on Mariner:  First focus on Mariner Mariner’s role is to track information residing at a vast number of sources Structured to look like a database Approach: “peer to peer gossip”. Basically, each machine has a piece of a jigsaw puzzle. Assemble it on the fly. Mariner in a single domain:  Mariner in a single domain Row can have many columns Total size should be k-bytes, not megabytes Configuration certificate determines what data is pulled into the table (and can change) 3.1 5.3 0.9 1.9 3.6 0.8 2.1 2.7 1.1 1.8 So how does it work? :  So how does it work? Each computer has Its own row Replicas of some objects (configuration certificate, other rows, etc) Periodically, but at a fixed rate, pick a friend “pseudo-randomly” and exchange states efficiently (bound the size of data exchanged) States converge exponentially rapidly. Loads are low and constant and protocol is robust against all sorts of disruptions! State Merge: Core of Mariner epidemic:  State Merge: Core of Mariner epidemic swift.cs.cornell.edu cardinal.cs.cornell.edu State Merge: Core of Mariner epidemic:  State Merge: Core of Mariner epidemic swift.cs.cornell.edu cardinal.cs.cornell.edu State Merge: Core of Mariner epidemic:  State Merge: Core of Mariner epidemic swift.cs.cornell.edu cardinal.cs.cornell.edu Observations:  Observations Merge protocol has constant cost One message sent, received (on avg) per unit time. The data changes slowly, so no need to run it quickly – we usually run it every five seconds or so Information spreads in O(log N) time But this assumes bounded region size In Mariner, we limit them to 50-100 rows Scaling up… and up…:  Scaling up… and up… With a stack of domains, we don’t want every system to “see” every domain Cost would be huge So instead, we’ll see a summary cardinal.cs.cornell.edu Build a hierarchy using a P2P protocol that “assembles the puzzle” without any servers:  Build a hierarchy using a P2P protocol that “assembles the puzzle” without any servers San Francisco New Jersey SQL query “summarizes” data Dynamically changing query output is visible system-wide (1) Query goes out… (2) Compute locally… (3) results flow to top level of the hierarchy:  (1) Query goes out… (2) Compute locally… (3) results flow to top level of the hierarchy San Francisco New Jersey 1 3 3 1 2 2 Hierarchy is virtual… data is replicated:  Hierarchy is virtual… data is replicated San Francisco New Jersey Hierarchy is virtual… data is replicated:  Hierarchy is virtual… data is replicated San Francisco New Jersey Mariner solves our problem!:  Mariner solves our problem! A flexible, user-programmable mechanism Where can I find a display device suitable for displaying these NMR test results? Are any specialists in epilepsy available to consult on this ER admission? Find 12 idle computers with copies of the NMR-3D package to which I can download a 20MB dataset rapidly Is there a free office where I could use a computer and a phone? Think of aggregation functions as small agents that look for information Data Mining:  Data Mining Quite a hot area, usually done by collecting information to a centralized node, then “querying” within that node Mariner is doing the comparable thing, but computing (query evaluation) occurs in a decentralized manner This is incredibly parallel, hence faster And more robust against disruption too! Aggregation and Hierarchy:  Aggregation and Hierarchy Nearby information Maintained in more detail, can query it directly Changes seen sooner Remote information summarized High quality aggregated data This also changes as information evolves Marioner summary:  Marioner summary Scalable: could support millions of machines Flexible: can easily extend domain hierarchy, define new columns or eliminate old ones. Adapts as conditions evolve. Secure: Uses keys for authentication and can even encrypt Handles firewalls gracefully, including issues of IP address re-use behind firewalls Performs well: updates propagate in seconds Cheap to run: tiny load, small memory impact Unlimited scalability!:  Unlimited scalability! Probabilistic gossip “routes around” congestion And probabilistic reliability model lets the system move on if a computer lags behind Results in: Constant communication costs Constant loads on links Steady behavior even under stress Bimodal Multicast:  Bimodal Multicast A second part of Astrolabe Mariner is for “all to all” information Bimodal multicast is a peer-to-peer scalable protocol for “few to many” patterns We pick the destinations using a Mariner aggregation function! Then can stream data to these recipients Protocol scales with constant costs and works even under extreme stress! Kelips:  Kelips Last in our set of tools A P2P “index” Put(“name”, value) Get(“name”) Kelips can do lookups with one RPC, is self-stabilizing after disruption Unlike Astrolabe, nodes can put varying amounts of data out there. New forms of computing:  New forms of computing Grid Computing Our tools could be key to building really reliable grid solutions Web Services We see these technologies as the answer to the “what’s going on?” dilemma Distributed large-scale sensor networks Astrolabe opportunity:  Astrolabe opportunity Autonomic computing … failed in the past because our applications operated in the dark … but now may be possible because for the first time, we can make system structure explicit and track it as it changes With appropriate support, opens door to a wave of new applications More information?:  More information? www.cs.cornell.edu/Info/Projects/Spinglass Or http://www.cs.cornell.edu/ken/astrolabe.pdf http://www.cs.cornell.edu/ken/bimodal.pdf

Add a comment

Related presentations