Distributed Computing CS 7210
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 7210 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 29 views. For similar materials see /class/234151/cs-7210-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Distributed Computing
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/02/15
Scalable Consistency Protocols for Distributed Services Mustaque Ahamad Rammohan Kordale Introduction target environment highly interactive distributed applications need to provide low latency access to dynamically changing shared state scalability along the lines of system load geographical distribution use of server replication client caching introduces problem of consistency Approaches Used 39 synchronization operations 39 does not scale well 39 weak consistency 39 shared state to be updated at multiple nodes 39 need for strong consistency 39 operations on shared objects should be serializable 39 do not permit lag in disseminating effects of updates Local Consistency strong consistency exible control over update dissemination nodes that update shared state NOT responsible for informing others node itself is responsible for taking local consistency actions to invalidate old copies of objects Advantages 39 access latencies lowered 39 number of client requests to servers server load decreased 39 both push and pull style dissemination 39 guarantee serialization yet allow for control over currency of cached copies LC Approach shared objects are stored at server nodes clients cache copies assumption server for an object remains xed global view external observer who can see updates immediately node view values cached at node contd Ideally node Viewl lC Ecurrent global View Synchronization costly nodes may not be interested in updates In LC node View can lag behind current global View A node39s View is locally consistent if Node39s Viewi C Global View If Node39s Viewi C Global View and Node39s Viewi1 C Global Viewk then Global Viewk is more recent than Global View Readers can be concurrent with writers Consistent Views 51 E2 3953 G4 ES P1 no my xt 11 11 Glmwiaw VH3 01 ym 5 K1 10 20 10 21 W000 my wtzo wy1 mm wtz1 Time r000 TCY 3911 x0 xw W 1 21 F2 PZ39S View D 39 A node39s View does not have to be a subset of the current View Invalidation Protocol Write Miss Copy of object has not been cached Write Fault Copy cached in nonexclusive mode server invalidates copies of an object on update returns exclusive access to client limited scalability because it involves communication with all nodes having copies of the object Invalidation Set Protocol single server maintains consistent node views by receiving information about what object copies have been overwritten all write missesfaults require communication with the server server keeps information on a per node basis about which objects need to be invalidated for a node object copies are invalidated only when a client communicates with the server ACTIONS AT CLIENT P rendMiss I ACTIONS AT SERVER access P 1 mass Lmverdkmsu P II 1 mm as sell mVaIldaLe lucal up uI glued ImlununiLaLt will mm owner mm m member nI invalSeL s L owneralnwnymlelcl mm read uwnm all IeLuluSeL umISeIh erIeMissm lnvdlSeLm w mne dermmun In wrileFauch empI returnllt I reLumSeL IImI A nup39 I I Iml meva lt I unalSel laervzrdng0wnru P clng0wner1 P Inmuum qudI Lupus u glued 1m owner e I lhaL m memben DI imalSeL meunniuu2 wIII culrenL mm MW Irwin s mwuenduwngmlem 7w er downgrade m m mm P Laddug I c n d quJ J Lu invalSe mmm lh m urn52 IVQISELII lnvdlSeLm w IeLumLlt 4 LurnSeLgt Figure 2 Invalidacioursct precocoI SLep Nudt P Nude P1 Rmam I m u P bmxm I uwuer 2 39y u P Lemme 5 owner 3 rm u PJ39s copy dawngrmled In mu m I m a Low downydded Lo m4me 5 W X I I r I Added La Arlydlselb s w39 1 Add 17 Remove L r y Added Lu Imsam P55 copy uI 1 invalidated 7 rm u P read old In 0139 y a m I P mad lateaL value of Object Lifetime Based Protocol related objects partitioned among multiple servers metadata associated with an object X having value V is called the lifetime of Xv lifetime interval Xvwt Xv39wt next writetime is unknown hence associate valid time with an object known lifetime interval Xvwt Xvvt 39 two copies Xv and yv39 belong to a consistent view if they have overlapping lifetimes 39 a set of copies belong to a consistent view if each pair of copies in the set has overlapping times 39 protocol uses vector clocks Clock Rules if operation writes V to X and the value V is read by another operation then the read must be ordered after the write if V and v39 are the values of X by two consecutive writes a read operation that reads the value v must be ordered before the second write 39 Rule 12 Pi completes an access with a locally cached copy Read VTi is not advanced Write VTi is incremented 39 Rule 2 Access at Pi results in read miss If another writer eXists server communicates with writer and downgrades its exclusive access 39 VTi update Xvwt VTi 39 Rule 3 Write faultmiss If another node has object cached downgrade 39 VTi update Xvwt Xvrt VTi Write Read and Valid Times 39 Write Time The value of VTi after the operation is completed 39 Read Time server maintains the read time for an object as follows 39 when Pi requests copy from server Xvrt updateXvrt VT 39 if X is currently cached in exclusive mode server updates Xvrt with owners copy as well as the owner now possesses a readonly copy 39 Valid time advanced on three occasions 39 locally cached objects updated to node39s clock value 39 when a server requests node for a copy node updates copy39s valid time with its clock value 39 server updates valid time of an object copy before returning it 39 Local consistency check invalidate all related objects whose valid times are less than the write time of X ACTIONS AT CLIENT NODE P I39cadMisst r Lservelaaccezsu read vr A Laccess readronl cachelnup V R v updanewr mm writeMiss r Same de nition for writhaulL y 1sex39veracces 1 wine incremeuq V R L P Laccess readrwn39Le l39uJE updaLer wt cachelnm m L VTJ LL t clnLAcccssv Laccess readronly m2 updatsumt VT remnu V71 cachelnm r r every object 9 in the cache 9 vi updategut VT p 1f 911 4 1 invalidate g m m m m upevmmn m m m who u m m H 39M mm 221 what ACTIONS AT t39s SERVER accessh mode VT R VTmm updaLeU Tmm VT if110wner self lt 1V xowuerc1nmccessm 39 VT 9 S 3 NH upd x m updaLem V l39Ul updateh 2 Vvaer if made reaxh IJ39l pdaLexrtquotTp Lowuer self r93 remmm n and g is not locally ownedi P2 m w VT2 upevahun m m 0 WM 9 2 2 2 WM m t2 t2 mu Hybrid Protocol 39 Obj eet lifetime based protocol can be more conservative than required 39 If X39s server is SX then SX maintains both the invalidation set and write read and valid times for each obj eet copy 39 For objects managed by SX invalidation based on set For others use obj eet lifetimes Performance and Evaluation 39 evaluation based on distributed filesystem 39 workloads Princeton and Toronto for system load and geographic distribution respectively 39 metrics measured cache misses server requests average response time 39 Princeton load difference between cache misses not too signi cant difference between server requests is significant 39 LC incurs 6 more processing overhead at the server per Client request 39 Toronto Invalidation protocol39s average response time is 39 worse than LC Landon Cox Christopher D Murray and Brian D Noble University of Michigan Ann Arbor Presented by Danesh Irani 1 Outline Motivation Goals Enabling Technologies Design Data Chunks File Meta Data Backup Deletion Finding redundancy Finding buddies Backup protocol Restoration Detecting Failure and Malice Preventing Greed Limitations Conclusion Motivation Backup is cumbersome and expensive Disks are getting cheaper File systems are on average only 53 full Daily update footprint is a small fraction of total file system A lot of data is generated and common across installations Goals Decentralized efficient cost free administration free system Peer to peer backup system Nodes may come and go Unreliable and untrusted possibly malicious Leverage common data where possible eg Windows Office Linux Open Office Preserve privacy Enabling Technologies Content Based Indexing minimizes storage overhead by finding redundant data across files files in a system or distinct files Peer to peer routing Use pastry a scalable self organizing routing and object location infrastructure for peer to peer applications 0 Sharing with Confidentiality Use convergent encryption for all on disk chunks Data Chunks Boundary regions identified using Rabin fingerprints Anchors Anchors divide file into smaller parts Chunks Chunks are immutable are purely content driven editing operations only change the chunks they touch and offsets of other chunks Chunks stored for local host andor remote host Data Chunks cont Chunking takes place when a file is closed after updatecreation oHc Chunk handle olc Chunk ID ch Encryption Key Complete set Chunk IDs on a node forms a signature File Meta Data Encrypted mutable and not chunked List of handles HC for the chunks comprising the file Reference count Plus the usual Ownership Permissions Creation and modification times Etc File Meta Data cont Stored to disk in a loglike format lime U lime UH timeli llmetii timeli2 limeti3 Metadata object corresponding to root is treated specially lts Hc is generated using a host specific passphrase Backup Deletion 0 Backup Request Remote hosts must supply public key with backup request If chunk exists add requesting host to owner list Local reference count is incremented 0 Delete Request Requests from remote hosts must be signed by secret key Check against public key When reference count O chunk is removed 10 Finding redundancy Signatures are large 20 bytes per chunk so approximately 13MB per GB Instead of sending a complete signature send a small random subset oftheir signatures called an abstract Evaluation shows that anything above a 1 sampling rate is great 11 Finding redundancy cont Z Nodel signature ode2 signatur name a H Ch N U1 5 N H U gt N a a Nodel abstract D aaa can all use 12 Finding buddies Nodes should have substantial overlap to reduce storage overhead Most buddies should be nearby to reduce global network load and improve restore performance One buddy must be located elsewhere to provide geographic diversity As a rule ofthumb maintain five buddies Finding buddies cont Uses two overlays to facilitate buddy discovery Network proximity Filesystem overlay NodeID is a hash of fully qualified domain name Pick a random NodelD and route a discovery request includes abstract Each node on the route computes its coverage and returns it Finding buddies cont Re probe using different first digit of NodelD is sufficient coverage not found Lighthouse sweep ooo i 221 i 0 If adequate set sti 39 not found Join 021 using coverage overlay Backup protocol Skeleton is a representation of a machine s current file system state Stored both on the machine and all of its backup buddies Snapshot a discreet backup event State necessary for new snapshot Add set Delete set Metadata list 16 Restoration Partial restores are straight forward Find chunks correspond to the restore request and obtain them from nearest buddy Full restore slightly more complicated When a node rejoins the network it keeps the same NodeID obtains its skeleton from a buddy Decrypts it with the key generated from a passphrase Since the root block contains the set of buddies in effect when it was replicated all state can be recovered Detecting failure and malice Employs a probabilistic mechanism to detect failure and malice Requests a random subset of chunks from the node s archive If buddy cannot produce this data or takes too long to respond the buddy is dropped 18 Detecting failure and malice cont Since buddies expect to be spot checked periodically ifthe buddy does not hear from a corresponding host for a long period of time assume host decommissioned or re installed Done conservatively incase a long lived failure is mistaken for a voluntary removal Preventing Greed 39 Greedy hOStS can consume EXCESS Storage 0 Three solutions Group backup clients based on resources consumed Cryptographic puzzles according to storage consumed Electronic currency atomicity in the exchange of backup state and currency Conclusion Enables automatic backup with no administrative costs 0 Requires only modest excess disk capacity among a set of cooperating peers Self organizing nature of two overlay networks used one organized by network distance other by data overlap obviates administrative intervention ddddddddddddddddddddddddCddddddddddddddddddddd suonsan o Wm Em 23 Few limitations 0 During lighthouse sweep coverage may not be symmetric A is a buddy for B but may not vice versa 0 Possibility of malicious nodes to misreport coverage drop files 100 10 1 01 001 0953mm mwaama D busmdo I seven E1 snooues lyemsel samm D speak sheep Dba ero Evaluation