UMass Amherst CS 677 - Last Class- Concurrency Control

Unformatted text preview:

Last Class: Concurrency ControlToday: Web cachingReplica PlacementWeb CachingConsistency IssuesPush-based ApproachPush-based ApproachesPull-based ApproachesPull-based Approach: Intelligent PollingPull-based ApproachA Hybrid Approach: LeasesPolicies for Leases DurationCooperative CachingHierarchical Proxy CachingLocating and Accessing DataCDN IssuesCS677: Distributed OSComputer ScienceLecture 14, page 1Last Class: Concurrency Control•Concurrency control–Two phase locks–Time stamps•Intro to Replication and ConsistencyCS677: Distributed OSComputer ScienceLecture 14, page 2Today: Web caching•Case Study: web caching as an illustrative example–Invalidate versus updates–Push versus Pull–Cooperation between replicasCS677: Distributed OSComputer ScienceLecture 14, page 3Replica Placement•Permanent replicas (mirroring)•Server-initiated replicas (push caching)•Client-initiated replicas (pull/client caching)CS677: Distributed OSComputer ScienceLecture 14, page 4Web Caching•Example of the web to illustrate caching and replication issues–Simpler model: clients are read-only, only server updates databrowserWeb ProxycacherequestresponserequestresponseWeb serverbrowserWeb serverrequestresponseCS677: Distributed OSComputer ScienceLecture 14, page 5Consistency Issues•Web pages tend to be updated over time–Some objects are static, others are dynamic–Different update frequencies (few minutes to few weeks)•How can a proxy cache maintain consistency of cached data?–Send invalidate or update–Push versus pullCS677: Distributed OSComputer ScienceLecture 14, page 6Push-based Approach•Server tracks all proxies that have requested objects•If a web page is modified, notify each proxy•Notification types–Indicate object has changed [invalidate]–Send new version of object [update]•How to decide between invalidate and updates?–Pros and cons?–One approach: send updates for more frequent objects, invalidate for restproxyWeb serverpushCS677: Distributed OSComputer ScienceLecture 14, page 7Push-based Approaches•Advantages–Provide tight consistency [minimal stale data]–Proxies can be passive•Disadvantages–Need to maintain state at the server •Recall that HTTP is stateless•Need mechanisms beyond HTTP–State may need to be maintained indefinitely•Not resilient to server crashesCS677: Distributed OSComputer ScienceLecture 14, page 8Pull-based Approaches•Proxy is entirely responsible for maintaining consistency•Proxy periodically polls the server to see if object has changed –Use if-modified-since HTTP messages•Key question: when should a proxy poll?–Server-assigned Time-to-Live (TTL) values•No guarantee if the object will change in the interimproxyWeb serverpollresponseCS677: Distributed OSComputer ScienceLecture 14, page 9Pull-based Approach: Intelligent Polling•Proxy can dynamically determine the refresh interval–Compute based on past observations•Start with a conservative refresh interval•Increase interval if object has not changed between two successive polls•Decrease interval if object is updated between two polls•Adaptive: No prior knowledge of object characteristics neededCS677: Distributed OSComputer ScienceLecture 14, page 10Pull-based Approach•Advantages–Implementation using HTTP (If-modified-Since)–Server remains stateless–Resilient to both server and proxy failures •Disadvantages–Weaker consistency guarantees (objects can change between two polls and proxy will contain stale data until next poll)•Strong consistency only if poll before every HTTP response–More sophisticated proxies required–High message overheadCS677: Distributed OSComputer ScienceLecture 14, page 11A Hybrid Approach: Leases•Lease: duration of time for which server agrees to notify proxy of modification•Issue lease on first request, send notification until expiry–Need to renew lease upon expiry•Smooth tradeoff between state and messages exchanged–Zero duration => polling, Infinite leases => server-push•Efficiency depends on the lease durationClient ProxyServerGet + lease reqReply + leasereadInvalidate/updateCS677: Distributed OSComputer ScienceLecture 14, page 12Policies for Leases Duration•Age-based lease –Based on bi-modal nature of object lifetimes–Larger the expected lifetime longer the lease•Renewal-frequency based–Based on skewed popularity–Proxy at which objects is popular gets longer lease•Server load based–Based on adaptively controlling the state space –Shorter leases during heavy loadCS677: Distributed OSComputer ScienceLecture 14, page 13Cooperative Caching•Caching infrastructure can have multiple web proxies–Proxies can be arranged in a hierarchy or other structures•Overlay network of proxies: content distribution network–Proxies can cooperate with one another •Answer client requests•Propagate server notificationsCS677: Distributed OSComputer ScienceLecture 14, page 14 Hierarchical Proxy CachingExamples: Squid, HarvestServerParentHTTPHTTPRead A1ICPICPICP2HTTP3ClientsLeaf CachesCS677: Distributed OSComputer ScienceLecture 14, page 15Locating and Accessing Data•Lookup is local•Hit at most 2 hops•Miss at most 2 hops (1 extra on wrong hint)Properties(A,X)Node XServer for BClientsCachesRead AGet ARead BGet BNode YMinimize cache hops on hit Do not slow down missesNode ZCS677: Distributed OSComputer ScienceLecture 14, page 16CDN Issues•Which proxy answers a client request?–Ideally the “closest” proxy–Akamai uses a DNS-based approach•Propagating notifications–Can use multicast or application level multicast to reduce overheads (in push-based approaches)•Active area of research–Numerous research papers


View Full Document

UMass Amherst CS 677 - Last Class- Concurrency Control

Download Last Class- Concurrency Control
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Last Class- Concurrency Control and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Last Class- Concurrency Control 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?