Web Caching with Consistent Hashing =================================== Why do we want to cache web pages? 1. reduce load on server 2. reduce network congestion 3. reduce network bandwidth consumption 4. improve fetch latency (avoid long roundtrips) 5. improve availability What simplifying assumptions can we make? Web pages are read-only (excludes database transactions, queries, etc.) Web pages are static (excludes all dynamic pages) Consistency requirements are lax (doesn't work for data with many updates) To understand the advantages and placement of caches, draw a picture of the Internet: a collection of automous subsystems (AS) connecting browser and server (clusters). what are example ASes? AT&T, Sprint, UUnet, NYU (12), MIT (3) each AS owns part of the IP address space how are packets routed from client to server? through a series of ASes that peer peering relationships are political/economical/strategic deals BGP is used to set up the routing tables between ASes what are the potential bottlenecks in the Internet? 1. client to ISP (modem line) 2. ISP to backbone AS (if different) 3. internal AS 4. peering points 5. AS to server (server is often at a hosting service) Where can we place caches? 1. right before server cluster in customer rack (doesn't help with 2, 3, 4) 2. right before the server cluster but within AS reduce load on servers reduce load on network link between AS and server might improve availability 3. cluster of caches on the edge of an AS reduces internal load on network might improve client fetch latency substantially improves availability helps only clients whose packets go over that AS doesn't deal with spikes in load 4. cooperative cache across multiple ASes doesn't help with client to AS bottleneck potential for dealing with spikes. 5. customer premise improves everything for that customer and for the customer's AS How do we get a request to the cache? 1. manual proxy settings (5) 2. transparent proxy (1, 3, 5) 3. have a single "marked" IP address for a server and catch at edge (3) 4. advertise "marked" names (DNS or URL) and redirect redirection can be based on load, content, ... 5. modify browser, advertise multiple caches, and client selects (3 and 4) client might measure How to locate a cache item in a cluster of caches? 0. it always local (caches in cluster don't cooperate) - duplicate cached data 1. primary plus multicast other caches are secondary to primary, perhaps through a tree 2. directory-based schemes (centralized or distributed) perhaps distributed scheme using a tree changing number of servers 3. hashing + direct access - changing number of servers changing the hash function can result all objects to end up in different caches 4. consistent hashing (topic of paper) Consistent hashing assumptions: many caches, some down some up, all with equal access cost many clients with different views of the live caches hash function that takes URLs and outputs a number of 0 ... M URLs and caches are mapped to points on a circle 0 ... M How to do lookup? First cache that succeeds hash(U) has document How to add cache? Move objects that are "closest" on circle to new cache note: map cache on multiple points of circle for uniform distribution of URLs to caches result: each URL is in a small number of caches Ideal implementation: hash runs at client Can run your own redirection proxy (like lab 3), aware of cache - won't work with existing web users, no good incremental deployment story Can download javascript into your browser to determine practical implementation: virtual caches through DNS for example, a456.proxycache3.com a456 is mapped to an IP address Hot pages Very hot page might overload server it is mapped to Ideally want load spread around more servers Partial solution: detect popular hash buckets If a456 is very popular, map it to all caches Locality a456.proxycache3.com -- 3 represents geographic region Evaluation What should be goals? "Theorem 2.1" Balance - In any given view, URLs distributed evenly over machines Load - Over changing views, no machine gets too many URLs Spread - Any given URL not stored at too many caches (duplicate data) E2E goals: Should give lower latency than raw server or other cache systems Should reduce load on servers compared to other cache systems Should not reduce reliability Evidence: Fig 2 & 3: Latency looks good Section 2.4: Load looks good in table fault-tolerance ok in text (25% incresae in pairs when 5/80 down) Spread & hot spot tolerance less evaluation, but mechanism sounds plausible * Akamai Example URLs: http://a1516.g.akamai.net/f/1516/1052/2h/www.1800flowers.com/800f_assets/images/flowers/images/shop/catalog/1120t.jpg http://a1516.g.akamai.net/f/1516/1052/2h/www.1800flowers.com/800f_assets/images/flowers/images/shop/catalog/3153t.jpg http://a1472.g.akamaitech.net/f/1472/124/60m/images.ebags.com/images/products/6468_sq85.jpg http://a1512.g.akamaitech.net/f/1512/124/30m/images.ebags.com/img/Spring_Catalog_mini.gif - 1512 is hash bucket for URL - 124 is probably billing code for customer - 2h / 60m / 30m is expiration time for cache (so web server can control it) akamai.net. 78432 NS ZA.AKAMAITECH.NET. ... akamai.net. 78432 NS ZH.AKAMAITECH.NET. g.akamai.net. 1800 NS n0g.akamai.net. ... g.akamai.net. 3600 NS n8g.akamai.net. A records for n?g.akamai.net different on different z?.akamaitech.net machines. * Chord Now, say you want to build a gigantic hash table So big each machine only knows about a small fraction of other machines So big that nodes come and go all the time--nodes owned by many people Napster approach--centralized server coordinates, can be shut down Gnutella approach--ad-hoc configuration, broadcast queries Better approach--use consistent hashing Give each node a particular ID (e.g., randomly chosen) Have a rule for assigning keys to nodes based on node/key ID key X goes on node with nearest successor ID to X That node stores data for X (e.g., napster index data, not necessarily mp3 file) Now how, given X, do we find the node storing it? Need to know about some machines But no one can have exact view of 1,000,000 machines coming & going Idea: Each node tracks some small number of other nodes (e.g., log N) May not know who has X, but I know someone with better info than me So query, e.g., log N other nodes to find successor of X Routing table state: Finger table Successor pointers