Jonathan Stanton1Spring 2004 / Lecture 18Network IICS 184Peer to Peer: ChordDepartment of Computer ScienceGeorge Washington UniversityJonathan Stanton2Spring 2004 / Lecture 18• Chord, Peer to peer file systems and related topics.– http://www.pdos.lcs.mit.edu/Additional ResourcesJonathan Stanton3Spring 2004 / Lecture 18Peer to Peer data management• Problems to solve– Where to store data objects?– How to find servers?– How to locate a particular data record?– How to dynamically move data in response to failures?Jonathan Stanton4Spring 2004 / Lecture 18Data distribution• Dynamically replicate or move data to more secureand reliable hosts.• Objectives:– Move minimum possible amount of data– Small amount of resources for data tracking(avoid tables!)Jonathan Stanton5Spring 2004 / Lecture 18Scalable Distributed Directories• Goal:– Find an object within log(n) steps with no server storingmore then log(n) state.• Clearly each server must store at least 1/n of the dataobjects on average.• Maybe store more to make system fault-tolerant.Jonathan Stanton6Spring 2004 / Lecture 18Distributed Hashing — GeneralApproachObjectsNodes1. Map both objects and nodes into some topology (“id space”)Jonathan Stanton7Spring 2004 / Lecture 18Distributed Hashing — GeneralApproachObjectsNodes1. Map both objects and nodes into some topology (“id space”)2. Each node “owns” some neighborhood in the topology, has channel tosome neighborsJonathan Stanton8Spring 2004 / Lecture 18Distributed Hashing — GeneralApproachObjectsNodes1. Map both objects and nodes into some topology (“id space”)2. Each node “owns” some neighborhood in the topology, has channel tosome neighbors3. Topological structure lets query be routed to the “owner” of a givenpointJonathan Stanton9Spring 2004 / Lecture 18Consistent hashingN32N90N105K80K20K5Circular 7-bitID spaceKey 5Node 105A key is stored at its successor: node with next higher IDJonathan Stanton10Spring 2004 / Lecture 18Basic lookupN32N90N105N60N10N120K80“Where is key 80?”“N90 has K80”Jonathan Stanton11Spring 2004 / Lecture 18Simple lookup algorithmLookup(my-id, key-id)n = my successorif my-id < n < key-idcall Lookup(id) on node n // next hopelsereturn my successor // done• Correctness depends only on successorsJonathan Stanton12Spring 2004 / Lecture 18“Finger table” allowslog(N)-time lookupsN80__1/81/161/321/641/128Jonathan Stanton13Spring 2004 / Lecture 18Finger i points to successor ofn+2iN80__1/81/161/321/641/128112N120Jonathan Stanton14Spring 2004 / Lecture 18Lookup with fingersLookup(my-id, key-id)look in local finger table forhighest node n s.t. my-id < n < key-idif n existscall Lookup(id) on node n // next hopelsereturn my successor // doneJonathan Stanton15Spring 2004 / Lecture 18Lookups take O(log(N)) hopsN32N10N5N20N110N99N80N60Lookup(K19)K19Jonathan Stanton16Spring 2004 / Lecture 18Chord Insert and Delete ofnodes• Insert:– New node must initialize finger table• log(n) searches for 2k locations on cycle will solve this.– Current nodes must update finger table• Determined by new nodes finger table and predecessor pointers.• Delete:– Similar to insert.– Fault tolerance requires each node store k successorsinstead of 1.Jonathan Stanton17Spring 2004 / Lecture 18Nodes to Data• Finding a node that holds a key, does not solve theoriginal problem.• Need to find a (key,value) pair that identifies eitherthe data, or the location of the data.• Can hash keys and store value at host located at hashvalue.• Now when hosts join or leave, data values must bemoved (1/n) of the value each time.Jonathan Stanton18Spring 2004 / Lecture 18CFS Overview• CFS = Cooperative File System• Wants to address all peer-to-peer distributed filesystem problems• Has three layers– FS: a read-only file system interface to programs– DHash: a reliable distributed block storage– Chord: to find blocks• Data is published using a special applicationJonathan Stanton19Spring 2004 / Lecture 18• Provides distributed block store (oblivious to file systemsemantics)• DHash stores, balances, replicates, caches blocks• DHash uses Chord to locate blocks• Interaction to integrate lookup and searching for cached copiesof a blockDHashChordNode 1 Node 2DHashChordCFS ServerJonathan Stanton20Spring 2004 / Lecture 18D FB1B2Public keyRoot BlocksignatureDirectory BlockInode BlockData BlockData BlockH(D)H(F) H(B1)H(B2)• Format similar to UNIX V7 file system- Dhash blocks and Block Addresses• Block ID = SHA-1( Block’s content)• Root Block signed by publisher’s private key• Root Block’s ID = SHA-1(Publisher’s public key)• locating a block within a server is done by a RPC to the server whichlooks up a database and returns the block with the specified block ID.CFS File System StructureJonathan Stanton21Spring 2004 / Lecture 18Updates and Deletion• CFS stores two types of blocks:– content blocks– signed root blocks• A content block is accepted by a server if theSHA-1 hash of the block matches the key• A root block must be signed by a public keywhose SHA-1 hash matches the block’s CFS key• There is no delete operation– blocks simply expire after a given interval.– the publisher must update them to prevent removal.Jonathan Stanton22Spring 2004 / Lecture 18Replication• Each block is replicated on k servers• These servers are chosen amongst the r Chordsuccessors of a node (r ! k)– these servers are not likely to be close to each other in thereal network• A client fetches the entire list of servers that hold agiven block, then gets the block from the server withthe lowest latencyJonathan Stanton23Spring 2004 / Lecture 18N40N10N5N20N110N99N80N60N50Block17N6812Replicate blocks at rsuccessorsJonathan Stanton24Spring 2004 / Lecture 18Caching• Necessary to avoid hot spots on small files• Each node sets aside a fixed amount of disk storage for itscache• After a successful lookup, the client sends the block to becached to the nodes on the path traversed by the lookup• Since hops get shorter and shorter closer to the destination,lookups tend to visit the same set of servers closer to thedestination• LRU is the policy for replacementJonathan Stanton25Spring 2004 / Lecture 18N40N10N5N20N110N99N80N60Lookup(BlockID=45)N50N681.2.3.4.RPCs:1. Chord lookup2. Chord lookup3. Block fetch4. Send to cacheDhash Caching MechanismCaching followslookup path.Jonathan