1CS 525 Advanced Distributed SystemsSpring 2010Indranil Gupta (Indy)Distributed Monitoring March 30, 2010All Slides © IGAcknowledgments: Steve Ko, Jin Liang, Ahmed Khurshid,Abdullah Al-Nayee m2Distributed Applications run over Many EnvironmentsThe InternetGnutella peer to peer systemPlanetLabGrids, Datacenters,Cloud ComputingDistributed applications•Large scale1000’s of nodes•Unreliablenodes and network •Churnednode join, leave, failure3Management and Monitoring of Distributed ApplicationsMonitoring of nodes, system-wide or per-node• Many applications can benefit from this, e.g.,– DNS, cooperative caching, CDN, streaming, etc., on PlanetLab– Web hosting in server farms, data centers, Grid computations, etc.• A new and important problem direction for next decade – [CRA03], [NSF WG 05], [IBM, HP, Google, Amazon]• Goal more end-to-end than cluster or network management • Today typically constitutes 33% of TCO of distributed infrastructures– Will only get worse with consolidation of data centers, and expansion and use of PlanetLab4What do sysadmins want?• Two types of Monitoring Problems: I. Instant (on-demand) Queries across node population, requiring up-to-date answers– {average, max, min, top-k, bottom-k, histogram etc.} – for {CPU util, RAM util, disk space util, app. characteristics, etc.}– E.g., max CPU, top-5 CPU, avg RAM, etc.II. Long-term Monitoring of node contribution – availability, bandwidth, computation power, disk spaceRequirements:• Low bandwidth– For instant queries, since infrequent– For long-term monitoring, since node investment• Low memory and computation• Scalability• Addresses failures and churn• Good performance and response5Existing Solutions: Bird’s Eye ViewCENTRALIZEDDECENTRALIZEDDecentralizedoverlaysInstant QueriesLong-term monitoring6Existing Monitoring Solutions• Centralized/Infrastructure-based• Decentralized7Existing Monitoring Solutions• Centralized/Infrastructure-based: user scripts, CoMon, Tivoli, Condor, server+backend, etc.– Efficient and enable long-term monitoring1. Provide stale answers to instant queries (data collection throttled due to scale)– CoMON collection: 5 min intervals– HP OpenView: 6 hours to collect data from 6000 servers!2. Often require infrastructure to be maintained– No in-network aggregation– Could scale better• Decentralized8Existing Monitoring Solutions• Centralized/Infrastructure-based• Decentralized: Astrolabe, Ganglia, SWORD, Plush, SDIMS, etc.– Nodes organized in an overlay graph, where nodes maintain neighbors according to overlay rules, • E.g., distributed hash tables (DHTs) – Pastry-based• E.g., hierarchy - Astrolabe– Can answer instant queries but need to be maintained all the time• Nodes spend resources on maintaining peers according to overlay rules => Complex failure repair– Churn => node needs to change its neighbors to satisfy overlay rules– Can you do a quick and dirty overlay, without maintenance?9Another Bird’s Eye View9(Data)Scale(Attributeand churn)DynamismCentralized(e.g., DB)Scalingcentralized(e.g., Replicated DB) Static(e.g., attr:CPU type)Dynamic(e.g., attr: CPU util.)Centralized(e.g., DB)Decentralized10MON: Instant Queries for Distributed System Management11MON Query Language1. select avg(<resource>) [where <condition>]2. select top k <resource> [where <condition>]3. select histo(<resource>) [where <condition>]4. select <resource list> [where <condition>]5. select grep(<keyword>, <file>) [where <condition>]6. select run(<shell command>) [where <condition>]7. count and depth: number of nodes in, and tree-depth of, overlay8. push <file>• <resource> = either – system metric(s), e.g., CPU, RAM, disk, or – application-based metrics, e.g., average neighbor delay (p2p streaming), number of neighbors (partitionability of overlay), etc.• <condition> = any boolean expression over the system resources– E.g., CPU > 5012MON: Management Overlay NetworksSupports• Instant queries– Need instaneous answers– Inconsistency ok• push software updates• Basic Idea: Ephemeral overlays1. For each query, build an overlay on-demand2. Use overlay to complete query3. Do not maintain on-demand overlay?n1n2n3n4n5n613Why On-Demand?Maintained overlays, e.g., DHT-based overlays• maintenance bandwidth• complex failure repairOn-demand approach is:• Simple• Light-weight• Suited to management– Sporadic usage– Amenable to overlay reuseMaintained Overlays, e.g., DHT-basedOn-demand overlaysDistributed System ManagementOverlay ConstructionMembership Management•Management Commands•On-demand overlay construction•Each node maintains a small list of neighborsMON Architecture14Membership by Gossip• Partial membership list at each node (asymmetric)• Contains random few other nodes; fixed in size (log(N))• Periodic membership exchange [SCAMP01] [SWIM02] [TMAN04] [CYCLON06]– Measure delay – Detect failure: use age (last heard from time) to eliminate old entries -O(log(N)) time for spreading failure information [EGHKK03, DGHIL85]• Weakly consistent – may contain stale entriesn1n2n3n4n5n6noden4n5IP:Port128.X.X.X:6020192.X.X.X:6020RTT9020n6 64.X.X.X:6020 30Membership list at node n315On-demand trees: Randomized Algorithms• Simple algorithm (randk)– Each node randomly selects k children from its membership list– Each child acts recursively• Improved Algorithm (twostage)– Membership augmented with list of “nearby” nodes• Nearby nodes discovered via gossip– Two stage construction of tree• First h hops – select random children• After h hops – select local children• DAG construction: similar to tree• Weakly consistent membership list is ok– Retry prospective children– Or settle for fewer than k children 16Tree Building Examplen1n2n3n4n5n6(k=2)17Software Push• Receiver-driven, multi-parent download• DAG structure helps: bandwidth, latency, failure-resilience18Tree Construction PerformancePlanetLab slice of 330 hostsMedian response time isless than 1.5 seconds95% responses in less than2 seconds97% coverageBandwidth=10 Bps10 s gossip intervalk=5 children19Software Push BandwidthDAG median bandwidthabout same as treeBut DAG faster overalldue to replicationPlanetLab slice of 330 hosts20Comparison with DHT TreeScribe/SDIMS trees built over Pastry DHT. In a PlanetLab slice with 115 nodes.Pastry takes about twice as long to answer queries, does not ensure coverage when there are
View Full Document
Unlocking...