Pond – The Ocean Store PrototypeSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Questions?Pond – The Ocean Store PrototypePond – The Ocean Store PrototypePresented By Jon Hesscs294-4 Fall 2003Pond – The Ocean Store PrototypeOverview–Goals–Features–Design–Implementation–Experimental ResultsPond – The Ocean Store PrototypeGoals – A Distributed File System Offering–Incremental Scalability•More servers translates to more available data–Secure Sharing•Access Control–Long term durability•With high probability data should not be able to leave the systemPond – The Ocean Store PrototypeKey Features–Location Independent Routing•Tapestry–Byzantine Update Agreement•For management of the inner ring–Push based cache correction•Overlay locality aware multi-cast network–Continuous archiving•Erasure codesPond – The Ocean Store PrototypeDesign–Two tier network •Upper tier composed of well connected powerful servers–Serialize changes to data•Lower tier composed of user workstations–Cache data–Archive data–Read / Write dataPond – The Ocean Store PrototypeThe Data Object•Can be thought of as corresponding to a File•Is composed of immutable versions•Each version Is broken Into B-tree of blocks•Is referenced by an AGUID–Versions by VGUID–Blocks by BGUID•Can be conditionally operated onPond – The Ocean Store PrototypeData Object - AGUIDVersion – VGUID MD BGUIDIB IBPond – The Ocean Store PrototypeData Object - AGUIDVersion – VGUID MD BGUIDIB IBVersion - VGUIDMD BGUIDIBNewest VersionPrevious VersionPond – The Ocean Store Prototype•Retrieving Data–AGUID: secure hash of name and public key –Contact primary replica to find VGUID–From the VGUID retrieve BGUID’s–Copy the block data to the local system–Join the dissemination tree•Act as a cached copyPond – The Ocean Store Prototype•Controlling Data–Primary Replica•Publishes AGUID to VGUID mappings–Digitally signs•Enforces access control•Serializes writes•Pushes cache updates•Archives dataPond – The Ocean Store Prototype•Writing data–Send a request to the primary replica–Replica verifies credentials–Checks predicates–Creates new VGUID and then associates data–Pushes update down dissemination treePond – The Ocean Store PrototypeWriterPrimary ReplicaErasureArchive ServersCaching ReadersPond – The Ocean Store Prototype•Archiving Data With Erasure Codes–Divides data into N chunks–Encodes chunks to M erasure blocks–M > N–Any N of the M blocks is sufficient for reconstruction–Located by erasure block number and BGUID.–How does one know the BGUID? •The AGUID is unavailable?Pond – The Ocean Store Prototype•Primary Replica – The Inner Ring–Byzantine internal decisions–Decisions published with by public key•Each node has a fraction of the private key•Enough fractions to prove a Byzantine agreement was reached are required to sign a decisionPond – The Ocean Store Prototype•Inner Ring – Changing Nodes–Byzantine decision •Decides to elect•Decides Who to elect•Chooses the key set–Old keys are deleted•By Byzantine assumption, conspiring nodes do not have enough keys to publishPond – The Ocean Store Prototype•The Responsible Party–Publishes node statistics–Used to nominate nodes to inner ring–Has no say over the actions of the inner rings–There could be many of them–Being compromised would not destroy the networkPond – The Ocean Store Prototype•Implementation of the Pond Prototype–Pros•50,000 lines of Java•Event based between modules•Some modules are pluggable•Highly portable–Cons•Garbage collector ‘Stops The World’Pond – The Ocean Store PrototypeStorage Overhead–B-Tree dominates cost of small files–Convergence at 32KB–Erasure Codes add 4.8x storage penaltyPond – The Ocean Store PrototypeWrite Latency Components–For small updates•Computing the signature dominates–For large updates•Computing the erasure fragments dominateTests are local to minimize network’s effectPond – The Ocean Store PrototypeWrite Throughput–Increasing data size amortizes signature time–Approaches 8MB/s as block size grows–With archiving enabled•Performance peaks at 2.6MB/sPond – The Ocean Store PrototypePropagation Efficiency–As Replicas Increase•Network economy becomes more efficient–Less high RTT links are used–Tests are with 10, 20, and 50 replicas•This is 2%, 4% and 10%! of the network •Are these number likely to occur in practice?Pond – The Ocean Store PrototypeAndrew Benchmark–WAN•Read Performance–Up to 4.6x better•Write Performance–Up to 7.3x worse–LAN•Read Performance–From 2x to 3x worse•Write Performance–From 8x to 80x worseAre these tradeoffs acceptable?Pond – The Ocean Store
View Full Document
Unlocking...