CS 294-8 Distributed Load Balancing http://www.cs.berkeley.edu/~yelick/294Load BalancingSlide 3AgendaThe WebHot SpotsTemporary LoadsProxy Caches Balance LoadProxy CachingSlide 10Who Caches What?HashingProblem: Adding CachesProblem: Inconsistent ViewsSlide 15Slide 16Slide 17Slide 18Slide 19Consistent HashingSingle View PropertiesMultiple View PropertiesImplementationSlide 24Slide 25BalanceSmoothnessLow SpreadLow LoadFault ToleranceExperimental SetupPerformanceSummary of Consistent HashingConsistent Hashing for CachingRefinement: BW AdaptationRefinement: Hot PagesCache Tree ResultSlide 38Load Balancing SpectrumTask cost spectrumTask Dependency SpectrumTask Locality SpectrumMachine Heterogeneity SpectrumSpectrum of SolutionsApproachesStatic Load BalancingSemi-Static Load BalanceSelf-SchedulingWhen to Use Self-SchedulingVariations on Self-SchedulingV1: Fixed Chunk SizeV2: Guided Self-SchedulingV3: TaperingV4: Weighted FactoringV5: Distributed Task QueuesTheory of Distributed QueuesEngineering Distributed QueuesDiffusion-Based Load BalancingDiffusion-based load balancingDAG SchedulingHeterogeneous MachinesCS294, Yelick Load Balancing, p1CS 294-8Distributed Load Balancing http://www.cs.berkeley.edu/~yelick/294CS294, Yelick Load Balancing, p2Load Balancing•Problem: distribute items into buckets–Data to memory locations–Files to disks–Tasks to processors–Web pages to caches •Goal: even distribution•Slides stolen from Karger at MIT: http://theory.lcs.mit.edu/~kargerCS294, Yelick Load Balancing, p3Load BalancingEnormous and diverse literature on load balancing•Computer Science systems –operating systems–parallel computing–distributed computing•Computer Science theory•Operations research (IEOR)•Application domainsCS294, Yelick Load Balancing, p4Agenda•Overview•Load Balancing Data•Load Balancing Computation–(if there is time)CS294, Yelick Load Balancing, p5The WebCMUMITUSCCNNBrowers (clients)ServersUCBCS294, Yelick Load Balancing, p6Hot SpotsUCBBrowers (clients)ServersOceanStoreBANEIRAMTelegraphCS294, Yelick Load Balancing, p7Temporary Loads•For permanent loads, use bigger server•Must also deal with “flash crowds”–IBM chess match–Florida election tally•Inefficient to design for max load–Rarely attained–Much capacity wasted•Better to offload peak load elsewhereCS294, Yelick Load Balancing, p8Proxy Caches Balance LoadCMUMITUSCCNNBrowers (clients)ServersUCBOceanStoreBANEIRAMTelegraphCS294, Yelick Load Balancing, p9Proxy Caching•Old: server hit once for each browser•New: serve his once for each page•Adapts to changing access patternsCS294, Yelick Load Balancing, p10Proxy Caching•Every server can also be a cache•Incentives:–Provides a social good–Reduces load at sites you want to contact•Costs you little, if done right–Few accesses–Small amount of storage (times many servers)CS294, Yelick Load Balancing, p11Who Caches What?•Each cache should hold few items–Otherwise swamped by clients•Each item should be in few caches–Otherwise server swamped by caches–And cache invalidates/updates expensive•Browser must know right cache–Could ask for server to redirect–But server gets swamped by redirectsCS294, Yelick Load Balancing, p12Hashing•Simple and powerful load balancing•Constant time to find bucket for item•Example: map to n buckets. Pick a, b:y=ax+b (mod n)•Intuition: hash maps each itme to one random bucket–No bucket gets many itemsCS294, Yelick Load Balancing, p13Problem: Adding Caches•Suppose a new cache arrives•How to work it into has function?•Natural change: y = ax + b (mod n+1)•Problem: changes bucket for every item–Every cache will be flushed–Server swamped with new requests•Goal: when add bucket, few items moveCS294, Yelick Load Balancing, p14Problem: Inconsistent Views•Each client knows about a different set of caches: its view•View affects choice of cache for item•With many views, each cache will be asked for item•Item in all caches – swamps server•Goal: item in few caches despite viewsCS294, Yelick Load Balancing, p15Problem: Inconsistent Views0 1 2 3UCBax + b (mod 4) = 2cachesmy viewCS294, Yelick Load Balancing, p16Problem: Inconsistent Views0 31 2UCBax + b (mod 4) = 2cachesJoe’s viewCS294, Yelick Load Balancing, p17Problem: Inconsistent Views20 31UCBax + b (mod 4) = 2cachesSue’s viewCS294, Yelick Load Balancing, p18Problem: Inconsistent Views1 20 3UCBax + b (mod 4) = 2cachesMike’s viewCS294, Yelick Load Balancing, p19Problem: Inconsistent Views22 22UCBcachesCS294, Yelick Load Balancing, p20Consistent Hashing•A new kind of hash function•Maps any item to a bucket in my view•Computable in constant time, locally–1 standard hash function•Adding bucket to view takes log time–Logarithmic # of standard hash functions•Handle incremental and inconsistent viewsCS294, Yelick Load Balancing, p21Single View Properties•Balance: all buckets get roughly same number of items•Smooth: when a kth bucket is added, only a 1/k fraction of items move–And only from O(log n) servers–Minimum needed to preserve balanceCS294, Yelick Load Balancing, p22Multiple View Properties•Consider n views, each of an arbitrary constant fraction of the buckets•Load: number of items a bucket gets from all views is O(log n) times average–Despite views, load balanced•Spread: over all views, each item appears in O(log n) buckets–Despite views, few caches for each itemCS294, Yelick Load Balancing, p23Implementation•Use standard hash function H to map items and caches to unit circle•If H maps to [0..M], divide by MxY•Map each item to the closest cache (going clockwise)•A holds 1,2,3•B holds 4, 5AB21345CS294, Yelick Load Balancing, p24ImplementationCAB21345•To add a new cache–Hash the cache id–Move items that should be assigned to it•Items do not move between A and B•A holds 3•B holds 4, 5•C holds 1, 2CS294, Yelick Load Balancing, p25Implementation•Cache “points” stored in a pre-computed binary tree•Lookup for cached item requires:–Hash of item key (e.g., URL)–BST lookup of successor•Consistent hashing with n caches requires O(log n) time–An alternative that breaks the unit circle into equal-length intervals can make this constant timeCS294, Yelick Load Balancing, p26Balance•Cache points uniformly distributed by H•Each cache “owns” equal portion of the unit circle•Item position random by H•So each cache gets about
View Full Document
Unlocking...