Chord DHash Ivy: Building Principled Distributed Frameworks

0
0
1846 days ago, 856 views
PowerPoint PPT Presentation
What is a P2P framework?. A conveyed framework architecture:No unified controlNodes are symmetric in functionLarge number of temperamental nodesEnabled by innovation upgrades. . . . . . . . . . . Hub. Hub. Hub. Hub. Hub. Web. The guarantee of P2P processing. High limit through parallelism:Many disksMany system connectionsMany CPUsReliability:Many replicasGeographic distributionAutomat

Presentation Transcript

Slide 1

Chord+DHash+Ivy: Building Principled Peer-to-Peer Systems Robert Morris rtm@lcs.mit.edu Joint work with F. Kaashoek, D. Karger, I. Stoica, H. Balakrishnan, F. Dabek, T. Gil, B. Chen, and A. Muthitacharoen

Slide 2

What is a P2P framework? Hub Node A disseminated framework design: No brought together control Nodes are symmetric in capacity Large number of problematic hubs Enabled by innovation changes Internet Node

Slide 3

The guarantee of P2P processing High limit through parallelism: Many plates Many system associations Many CPUs Reliability: Many copies Geographic dispersion Automatic setup Useful out in the open and exclusive settings

Slide 4

… . hub Distributed hash table (DHT) (Ivy) Distributed application information get (key) put(key, information) (DHash) Distributed hash table lookup(key) hub IP address (Chord) Lookup benefit Application might be disseminated over numerous hubs DHT circulates information stockpiling over numerous hubs

Slide 5

A DHT has a decent interface Put(key, esteem) and get(key)  esteem Call a key/esteem combine a "piece" API underpins an extensive variety of utilizations DHT forces no structure/which means on keys Key/esteem sets are tenacious and worldwide Can store enters in other DHT qualities And along these lines assemble complex information structures

Slide 6

A DHT makes a decent shared foundation Many applications can share one DHT benefit Much as applications share the Internet Eases sending of new applications Pools assets from numerous members Efficient because of factual multiplexing Fault-tolerant because of geographic dispersion

Slide 7

Many late DHT-based ventures File sharing [CFS, OceanStore, PAST, … ] Web reserve [Squirrel, ..] Backup store [Pastiche] Censor-safe stores [Eternity, FreeNet,..] DB inquiry and ordering [Hellerstein, … ] Event warning [Scribe] Naming frameworks [ChordDNS, Twine, ..] Communication primitives [I3, … ] Common string: information is area autonomous

Slide 8

The query issue N 2 N 1 N 3 Put (Key="title" Value=file information… ) Internet ? Customer Publisher Get(key="title") N 4 N 6 N 5 At the heart of all DHTs

Slide 9

Centralized query (Napster) N 2 N 1 SetLoc("title", N4) N 3 Client DB N 4 Publisher@ Lookup("title") Key="title" Value=file information… N 8 N 9 N 7 N 6 Simple, yet O( N ) state and a solitary purpose of disappointment

Slide 10

Flooded questions (Gnutella) N 2 N 1 Lookup("title") N 3 Client N 4 Publisher@ Key="title" Value=file information… N 6 N 8 N 7 N 9 Robust, however most pessimistic scenario O( N ) messages per query

Slide 11

Routed inquiries (Freenet, Chord, and so on.) N 2 N 1 N 3 Client N 4 Lookup("title") Publisher Key="title" Value=file information… N 6 N 8 N 7 N 9

Slide 12

Chord query calculation properties Interface: lookup(key)  IP address Efficient: O(log N) messages per query N is the aggregate number of servers Scalable: O(log N) state per hub Robust: survives gigantic disappointments Simple to break down

Slide 13

Chord IDs Key identifier = SHA-1(key) Node identifier = SHA-1(IP address) SHA-1 appropriates both consistently How to guide key IDs to hub IDs?

Slide 14

Chord Hashes a Key to its Successor Key ID Node ID N10 K5, K10 K100 N100 Circular ID Space N32 K11, K30 K65, K70 N80 N60 K33, K40, K52 Successor: hub with next most noteworthy ID

Slide 15

Basic Lookup N5 N10 N110 "Where is key 50?" N20 N99 "Key 50 is At N60" N32 N40 N80 N60 Lookups discover the ID's forerunner Correct if successors are right

Slide 16

Successor Lists Ensure Robust Lookup 10, 20, 32 N5 20, 32, 40 N10 5, 10, 20 N110 32, 40, 60 N20 110, 5, 10 N99 40, 60, 80 N32 N40 60, 80, 99, 110, 5 N80 N60 80, 99, 110 Each hub recalls r successors Lookup can skirt dead hubs to discover squares

Slide 17

Chord "Finger Table" Accelerates Lookups ½ ¼ 1/8 1/16 1/32 1/64 1/128 N80

Slide 18

Chord queries take O(log N) jumps N5 N10 N110 K19 N20 N99 N32 Lookup(K19) N80 N60

Slide 19

Simulation Results: ½ log 2 (N) Average Messages per Lookup Number of Nodes Error bars check 1 st and 99 th percentiles

Slide 20

DHash Properties Builds key/esteem stockpiling on Chord Replicates hinders for accessibility Caches obstructs for load adjust Authenticates piece substance

Slide 21

DHash Replicates obstructs at r successors N5 N10 N110 N20 N99 Block 17 N40 N50 N80 N68 N60 Replicas are anything but difficult to discover if successor comes up short Hashed hub IDs guarantee free disappointment

Slide 22

DHash Data Authentication Two sorts of DHash pieces: Content-hash: key = SHA-1(data) Public-key: key is an open key, information is marked by that key DHash servers confirm before tolerating Clients check aftereffect of get(key)

Slide 23

Ivy File System Properties Traditional document framework interface (nearly) Read/compose for various clients No focal parts Trusted administration from untrusted segments

Slide 24

Straw Man: Shared Structure Root Inode Standard meta-information in DHT pieces? Shouldn't something be said about locking amid redesigns? Requires 100% trust Directory Block File1 Inode File2 Inode File3 Inode File3 Data

Slide 25

Ivy Design Overview Log organized Avoids set up overhauls Each member composes just its own particular log Avoids simultaneous upgrades to DHT information Each member peruses all logs Private depictions for speed

Slide 26

Internet Ivy Software Structure DHT Node client Ivy Server App framework calls DHT Node NFS RPCs NFS Client DHT Node piece

Slide 27

One Participant's Ivy Log Record 1 Record 2 Record 3 Log Head Immutable substance hash DHT squares Mutable open key marked DHT piece Log-head contains DHT key of latest record Each record contains DHT key of past record

Slide 28

Ivy I-Numbers Every document has a one of a kind I-Number Log records contain I-Numbers Ivy returns I-Numbers to NFS customer NFS asks for contain I-Numbers In the NFS document handle

Slide 29

NFS/Ivy Communication Example Local NFS Client Local Ivy Server LOOKUP("d", I-Num=1000) I-Num=1000 CREATE("aaa", I-Num=1000) I-Num=9956 WRITE("hello", 0, I-Num=9956) OK reverberate hi > d/aaa LOOKUP finds the I-Number of catalog "d" CREATE makes document "aaa" in index "d" WRITE composes "hi" at balance 0 in record "aaa"

Slide 30

Log Records for File Creation Type: Create I-num: 9956 Type: Link Dir I-num: 1000 File I-num: 9956 Name: "aaa" Type: Write I-num: 9956 Offset: 0 Data: "hi" … Log Head A log record portrays a change to the document framework

Slide 31

Scanning an Ivy Log Type: Link Dir I-num: 1000 File I-num: 9956 Name: "aaa" Type: Link Dir I-num: 1000 File I-num: 9876 Name: "bbb" Type: Remove Dir I-num: 1000 Name: "aaa" An output takes after the log in reverse in time LOOKUP(name, dir I-num): last Link, however stop at Remove READDIR(dir I-num): amass Links, less Removes

Slide 32

Finding Other Logs: The View Block Log Head 1 View Block Pub Key 1 Pub Key 2 Pub Key 3 Log Head 2 Log Head 3 View piece is permanent (substance hash DHT square) View square's DHT key names the document framework Example:/ivy/37ae5ff901/aaa

Slide 33

Reading Multiple Logs 27 31 32 20 Log Head 1 26 27 28 29 30 Log Head 2 Problem: how to interleave log records? Red numbers show continuous of record creation But we can't depend on synchronized tickers

Slide 34

Vector Timestamps Encode Partial Order 27 31 32 20 Log Head 1 26 27 28 29 30 Log Head 2 Each log record contains vector of DHT keys One vector passage for every log Entry focuses to log's latest record

Slide 35

Snapshots Scanning the logs is moderate Each member keeps a private preview Log pointers as of depiction creation time Table of all I-hubs Each document's characteristics and substance Reflects every one of members' logs Participant upgrades intermittently from logs All previews share stockpiling in the DHT

Slide 36

Simultaneous Updates Ordinary document servers serialize all redesigns Ivy does not Most cases are not an issue: Simultaneous keeps in touch with a similar record Simultaneous production of various documents in same index Problem case: Unlink("a") and rename("a", "b") at same time Ivy accurately gives one and only produce a chance to results But it might return "achievement" status for both

Slide 37

Integrity Can assailant degenerate my documents? Not unless assailant is in my Ivy see What if a member turns sour? Others can overlook member's entire log Ignore sections after some date Ignore simply destructive records

Slide 38

Ivy Performance Half as quick as NFS on LAN and WAN Scalable w/# of members These outcomes were taken yesterday…

Slide 39

Ivy Server DHash Server App NFS Client Local Benchmark Configuration One log One DHash server Ivy+DHash all on one host

Slide 40

Ivy Local Performance on MAB Modified Andrew Benchmark times (seconds) NFS: customer – LAN – server 7 seconds doing open key marks, 3 in DHash

Slide 41

WAN Benchmark Details 4 DHash hubs at MIT, CMU, NYU, Cornell Round-trek times: 8, 14, 22 milliseconds No DHash replication 4 logs One dynamic essayist at MIT Whole-document read on open() Whole-record compose on close() NFS customer/server round-excursion time is 14 ms

Slide 42

Ivy WAN Performance 47 seconds getting log heads, 4 composing log head, 16 embeddings log records, 22 in crypto and CPU

Slide 43

Ivy Performance w/Many Logs MAB on 4-hub WAN One dynamic author Increasing expense because of developing vector timestamps

Slide 44

Related Work DHTs Pastry, CAN, Tapestry File frameworks LFS, Zebra, xFS Byzantine assention BFS, OceanStore, Farsite

Slide 45

Summary Exploring utilization of DHTs as a building square Put/get API is general Provides accessibility, validation Harnesses decentralized shared gatherings Case investigation of DHT utilize: Ivy Read/compose distributed document framework Trustable framework from untrusted pieces http://pdos.lcs.mit.edu/harmony

SPONSORS