Wide-Area Cooperative Storage with CFSDesign GoalsCFS SummaryClient-server interfaceServer StructureCFS file system structureDHash/Chord InterfaceDHash Uses Other Nodes to Locate BlocksStoring BlocksReplicate blocks at r successorsLookups find replicasFirst Live Successor Manages ReplicasDHash Copies to Caches Along Lookup PathVirtual Nodes Allow HeterogeneityExperiment (12 nodes)! (pre-planetlab)CFS Fetch Time for 1MB FileDistribution of Fetch Times for 1MBCFS Fetch Time vs. Whole File TCPRobustness vs. FailuresRevisit AssumptionsBW for Redundancy MaintenanceBW for Redundancy Maintenance IIPeer DynamicsNeed Too Much BW to Maintain RedundancyProposal #1Proposal #2Proposal #3Appendix: Chord Hashes a Block ID to its SuccessorAppendix: Basic LookupAppendix: Successor Lists Ensure Robust LookupAppendix: Chord Finger Table Allows O(log N) LookupsWide-Area Cooperative Storage with CFSPresented by Hakim WeatherspoonCS294-4: Peer-to-Peer SystemsSlides liberally borrowed from the SOSP 2001 CFS presentationAnd High Availability, Scalable Storage, Dynamic Peer Networks: Pick Two by Rodrigo Rodrigues, Charles Blake and Barbara Liskov presented at HotOS 2003By Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, *Ion StoicaMIT and *BerkeleynodenodenodenodeInternetnodeP2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:2Design Goals•Spread storage burden evenly (Avoid hot spots)•Tolerate unreliable participants•Fetch speed comparable to whole-file TCP•Avoid O(#participants) algorithms–Centralized mechanisms [Napster], broadcasts [Gnutella]•Simplicity –Does simplicity imply provable correctness?•More precisely, could you build CFS correctly?–What about performance?•CFS attempts to solve these challenges–Does it?P2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:3CFS Summary•CFS provides peer-to-peer r/o storage•Structure: DHash and Chord•Claims efficient, robust, and load-balanced–Does CFS achieve any of these qualities?•It uses block-level distribution•The prototype is as fast as whole-file TCP•Storage promise Redundancy promise data must move as members leave! lower bound on bandwidth usageP2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:4Client-server interface•Files have unique names•Files are read-only (single writer, many readers)•Publishers split files into blocks and place blocks into a hash table.•Clients check files for authenticity [SFSRO]FS Client serverInsert file fLookup file fInsert blockLookup blocknodeservernodeP2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:5Server Structure• DHash stores, balances, replicates, caches blocks• DHash uses Chord [SIGCOMM 2001] to locate blocks•Why blocks instead of files?•easier load balance (remember complexity of PAST)DHashChordNode 1 Node 2DHashChordP2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:6CFS file system structure•The root-block is identified by a public key–signed by corresponding private key•Other blocks identified by hash of their contents•What is wrong with this organization?–Path of blocks from data-block to root-block modified for every update. –This is okay because system is read-only.root-blockpublic keysignatureH(D)directoryblockDH(F)inodeblockFdata blockB1data blockB2H(B2)H(B1)P2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:7DHash/Chord Interface•lookup() returns list with node IDs closer in ID space to block ID–Sorted, closest firstserverDHashChordLookup(blockID) List of <node-ID, IP address>finger table with <node IDs, IP address>P2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:8DHash Uses Other Nodes to Locate BlocksN40N10N5N20N110N99N80N50N60N68Lookup(BlockID=45)1.2.3.P2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:9Storing Blocks•Long-term blocks are stored for a fixed time–Publishers need to refresh periodically•Cache uses LRU disk:cache Long-term block storageP2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:10Replicate blocks at r successorsN40N10N5N20N110N99N80N60N50Block17N68• r = 2 log N• Node IDs are SHA-1 of IP Address• Ensures independent replica failureP2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:11Lookups find replicasN40N10N5N20N110N99N80N60N50Block17N681.3.2.4.Lookup(BlockID=17)RPCs:1. Lookup step2. Get successor list3. Failed block fetch4. Block fetchP2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:12First Live Successor Manages ReplicasN40N10N5N20N110N99N80N60N50Block17N68Copy of17•Node can locally determine that it is the first live successorP2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:13DHash Copies to Caches Along Lookup PathN40N10N5N20N110N99N80N60Lookup(BlockID=45)N50N681.2.3.4.RPCs:1. Chord lookup2. Chord lookup3. Block fetch4. Send to cacheP2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:14Virtual Nodes Allow Heterogeneity•Hosts may differ in disk/net capacity•Hosts may advertise multiple IDs–Chosen as SHA-1(IP Address, index)–Each ID represents a “virtual node”•Host load proportional to # v.n.’s•Manually controlled•Sybil attach!Node AN60N10 N101Node BN5P2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:15Experiment (12 nodes)!(pre-planetlab)•One virtual node per host•8Kbyte blocks•RPCs use UDPCA-T1CCIArosUtahCMUTo vu.nlLulea.seMITMA-CableCiscoCornellNYUOR-DSLTo vu.nl lulea.se ucl.ukTo kaist.kr, .ve•Caching turned off•Proximity routing turned offP2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:16CFS Fetch Time for 1MB File• Average over the 12 hosts• No replication, no caching; 8 KByte blocksFetch Time (Seconds)Prefetch Window (KBytes)P2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:17Distribution of Fetch Times for 1MBFraction of FetchesTime (Seconds)8 Kbyte Prefetch24 Kbyte Prefetch40 Kbyte PrefetchP2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:18CFS Fetch Time vs. Whole File TCPFraction of FetchesTime (Seconds)40 Kbyte PrefetchWhole File TCPP2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:19Robustness vs. FailuresFailed Lookups (Fraction)Failed Nodes (Fraction)(1/2)6 is 0.016Six replicasper block;P2P Systems 2003 ©2003 Hakim Weatherspoon/UC Berkeley CFS:20Revisit Assumptions • P2P Purist Ideals–Cooperation, Symmetry, Decentralized•How realistic are these assumptions?•In what domains are they valid?FastestFlakySlowerFlakySlowFasterStableFast Slowtest10
View Full Document
Unlocking...