CS 268: Lecture 21Outline for Today’s LectureA DHT in Operation: PeersA DHT in Operation: OverlayA DHT in Operation: put()Slide 6Slide 7A DHT in Operation: get()Slide 9Fundamental RequirementDHT GeometryMaking Sense of the MessThree Aspects of a DHT DesignTwo Fundamental PropertiesBasic InsightChord DHT has Ring GeometryChord Distance function captures RingNeighbor selection flexibility allowed by Ring GeometryRoute selection flexibility allowed by Ring GeometryGeometriesSummary of Flexibility AnalysisAnalysis of Static ResilienceDoes flexibility affect Static Resilience?Analysis of Overlay Path LatencyWhich is more effective, FNS or FRS?Does Geometry affect performance of FNS or FRS?Summary of ResultsConclusionDHT ApplicationsTwo Important DistinctionsPeers or InfrastructureLibrary or ServiceDHTs vs Unstructured P2PThree Classes of DHT ApplicationsRendezvous ApplicationsUsing DHT for RendezvousKey PointUsing DHTs for the WebSlide 39Storage ApplicationsExample: CFS (DHash over Chord)CFS Uses Tree of BlocksCFS Uses Self-authenticationMost Blocks are ImmutableAdding a File to a DirectoryData Availability via ReplicationFirst Live Successor Manages ReplicasExample: OceanStoreOceanStore Finding ReplicasSlide 50Example: Usenet over a DHTPosting a Usenet ArticleUsenetDHTUsenet ArchitectureUsenetDHT TradeoffUsenetDHT: potential savingsExample: Email (ePost)Slide 58“Routing” ApplicationsDHT-Based MulticastTree FormationMulticastMulticast JoinMulticast JoinSlide 65Multicast SendChallengesExample: Internet-Scale Query ProcessingPIERWhat’s the Fuss about DHTs?Distributed Systems Pre-InternetDistributed Systems Post-InternetProblems with Centralized Server FarmsThe DHT Community’s GoalThe StrategyHourglass AnalogyTwo Crucial Design DecisionsSlide 78DHT LayeringScenarios for DHT UsageScenario #1: Public InfrastructureThe DHT ApproachExamplesScenario #2: Scaling Enterprise AppsThe DHT approachSlide 86Scenario #3: Supporting Tiny AppsScenario #4: Super-ResilenceNot Just for Applications1CS 268: Lecture 21DHT Geometry and DHT Applications2Outline for Today’s LectureWhat is a DHT? (review)DHT GeometryThree classes of DHT applications (with examples):-rendezvous-storage-routingWhy DHTs?3K VK VK VK VK VK VK VK VK VK VK VA DHT in Operation: Peers4K VK VK VK VK VK VK VK VK VK VK VA DHT in Operation: Overlay5K VK VK VK VK VK VK VK VK VK VK VA DHT in Operation: put() put(K1,V1)6put(K1,V1)K VK VK VK VK VK VK VK VK VK VK VA DHT in Operation: put()7(K1,V1)K VK VK VK VK VK VK VK VK VK VK VA DHT in Operation: put()8get(K1)K VK VK VK VK VK VK VK VK VK VK VA DHT in Operation: get()9get(K1)K VK VK VK VK VK VK VK VK VK VK VA DHT in Operation: get()10Fundamental RequirementAll puts and gets for a particular key must end up at the same machine-Even in the presence of failures and new nodes (churn)This depends on the DHT routing algorithm (last time)-Must be robust and scalable11DHT Geometry12Making Sense of the MessThere are (too) many DHT routing algorithmsThey are very hard to compare-The basic idea drowning in idiosyncratic system details•one does caching, another doesn’t, etc.-Each is evaluated in terms of basic performance numbers•leads to “black-box” comparison of entire system, not of basic algorithmGoal: -Separate fundamental design choice from system details-Understand some basic differences between DHT routing schemes13Three Aspects of a DHT DesignGeometry: the basic graph structure-Tree, hypercube, ring, butterfly De BrujnDistance function: metric imposed on geometry-d(id1,id2) measures how far apart two identifiers areAlgorithm: rules for selection-neighbors-routes14Two Fundamental PropertiesFlexibility of neighbor selection: (FNS)-number of possible neighbors in a geometryFlexibility of route selection: (FRS)-average number of next-hop choices for all destinationsFine print:-select neighbors so that paths are still O(log N)-select routes so that each hop is closer (by metric) to destination15Basic InsightGeometry determines flexibilityFlexibility determines performance-FRS and FNS lead to shorter paths-FRS leads to more reliable paths16Chord DHT has Ring Geometry17Chord Distance function captures RingNodes are points on a clock-wise Ring d(id1, id2) = length of clock-wise arc between ids = (id2 – id1) mod N d(100, 111) = 300010110001101000111011118Neighbor selection flexibility allowed by Ring GeometryChord algorithm picks ith neighbor at 2i distanceA different algorithm picks ith neighbor from [2i , 2i+1)00010110001101000111011119Route selection flexibility allowed by Ring GeometryChord algorithm picks neighbor closest to destinationA different algorithm picks the best of alternate paths00010110001101000111011111020GeometriesGeometry AlgorithmRing Chord, SymphonyHypercube CANTree PlaxtonHybrid =Tree + RingTapestry, PastryXORd(id1, id2) = id1 XOR id2Kademlia21Summary of Flexibility AnalysisFlexibility Ordering of GeometriesNeighbors(FNS)Hypercube << Tree, XOR, Ring, Hybrid (logN) (2i-1) Routes(FRS)Tree << XOR, Hybrid < Hypercube < Ring (1) (logN/2) (logN/2) (logN)How relevant is flexibility for DHT routing performance?22Analysis of Static ResilienceTwo aspects of robust routingDynamic Recovery : how quickly routing state is recovered after failuresStatic Resilience : how well the network routes before recovery finishes-captures how quickly recovery algorithms need to work-depends on FRSEvaluation:Fail a fraction of nodes, without recovering any stateMetric: % Paths Failed23Does flexibility affect Static Resilience?Tree << XOR ≈ Hybrid < Hypercube < Ring Flexibility in Route Selection matters for Static Resilience0204060801000 10 20 30 40 50 60 70 80 90% Failed Nodes% Failed PathsRingHybridXORTreeHypercube24Analysis of Overlay Path LatencyGoal: Minimize end-to-end overlay path latency-not just the number of hopsBoth FNS and FRS can reduce latency-Tree has FNS, Hypercube has FRS, Ring & XOR have both Evaluation:Using Internet latency distributions (see paper)250204060801000 400 800 1200 1600 2000Latency (msec)CDFFNS RingPlain Ring FRS RingFNS + FRS RingWhich is more effective, FNS or FRS?Plain << FRS << FNS ≈ FNS+FRSNeighbor Selection is much better than Route Selection260204060801000 400 800 1200 1600 2000Latency (msec)CDFFNS RingFRS
View Full Document
Unlocking...