50 %
50 %
Information about pring

Published on February 11, 2008

Author: Simeone


P-Ring: An Index Structure for Peer-to-Peer Systms :  P-Ring: An Index Structure for Peer-to-Peer Systms Adina Crainiceanu, Prakash Linga, Ashwin Machanavajjhala, Johannes Gehrke, and Jayavel Shanmugasundaram Cornell Technical Report, July 2004 P2P Query Support :  P2P Query Support Where are we (2004)? Support for exact match queries - lookup(key) Efficient routing and uniform load balancing in dynamic system Where do we want to go? Support for full-fledged distributed database Complex queries Semantic Guarantees The next step - Range Queries Return all items in the range (lb, ub] Efficiently query for all items in a range (lb, ub] Range Queries in Chord:  Range Queries in Chord Store data items using hash(name) “Strange Invitation” “Such Great Heights” “Summertime” “Sweet Jane” 2 12 23 29 37 54 61 How do we query for songs that start with the letter “S”? Order-Preserving Hashing:  Order-Preserving Hashing Store data items using name “Strange Invitation” “Such Great Heights” “Summertime” “Sweet Jane” AB... DD... KB... NA... PA... SW... Query for all songs that start with “S” Perform lookup for lower bound: lookup(”SA...”) Scan along Ring until upper bound is reached: (”SZ...”) XA... Problem: data items not uniformly distributed among peers P-Ring Goals:  P-Ring Goals P2P Index that supports both exact match and range queries Distribute data items uniformly among all peers Each peer stores between sf and 2sf items, for some storage factor sf Use explicit load-balancing operations Provide efficient routing on top of this skewed data distribution Bounded by logarithmic number of hops TODO: List other works P-Ring Architecture:  P-Ring Architecture Fault Tolerant Ring Provides connectivity of system uses Chord implementation Data Store - responsible for distributing items to peers Content Router - efficient message routing Replication Manager - uses successor pointers P2P Index - operations exposed to the user P-Ring Data Store:  P-Ring Data Store Peers divided into 2 sets, free peers and live peers Each live peer is responsible for some range and data items Free peers are not part of the Ring Overflow: When live peer has more than 2sf items, invites free peer into ring, splits its load Underflow: When live peer p has less than sf items, takes items from its successor If (p.itemCount + succ(p).itemCount > 2sf ), succ(p) gives up some of its range and items to p Otherwise: succ(p) gives up its entire range and becomes a free peer P-Ring - Split:  P-Ring - Split p1 p5 p4 p3 p2 (20,5] (10,15] (18,20] (15,18] (5,10] p5 is overfull Notifies free peer p to join ring p5 gives range (20,25] to p p (25,5] (20,25] P-Ring - Merge/Redistribute:  P-Ring - Merge/Redistribute p1 is underfull Sends merge request to p2 p2 sends range (10,12] to p1 p1 receives (10,12] p1 p5 p4 p3 p2 (20,5] (10,15] (18,20] (15,18] (5,10] (10,12] (12,15] (5,12] Managing Free Peers:  Managing Free Peers Require a reliable way of storing and finding free peers Each free peer p creates an artificial data item (⊥, p) To find free peer, do equality search for ⊥ Ensure that a free peer always exists when overflow occurs For N items and P peers, set sf =⎡N / P⎤ If every live peer has sf items, no free peers are left If every live peer has 2sf items, there are P / 2 free peers Peers can estimate N and P using gossip Managing Free Peers:  Managing Free Peers Free peers must be able to query the system Each free peer keeps a list of live peers Free peer forwards its queries through a live peer True Load Balancing:  True Load Balancing Previous scheme balances load among live peers Can we balance load among all peers? Free peers become helpers to live peers Live peers range divided into intervals, each with same number of items Each helper peer responsible for an interval Helper can answer queries Live peer is responsible for inserts and deletes, and redistributing interval ranges Helper Peers:  Helper Peers Each live peer is responsible for between sf and 2sf + ε items, distributed between itself and its helpers When live peer is overfull ( > 2sf items), Pick one helper to be new live peer Split range and helpers with new live peer When live peer is underfull (< sf items), Redistribute: take over range from a neighbor OR Merge: give up range and helpers to neighbor and become a helper Assigning Helpers:  Assigning Helpers Check in pool of non-helper free peers Steal a helper from another peer Use undefined mechanism to locate least-loaded helper P-Ring Content Router:  P-Ring Content Router Explicit load balancing = non-uniform node distribution Cannot create index based on keys Idea: index on node position 2 12 14 17 21 54 56 22 53 36 1 2 4 8 Hierarchical Ring (HR):  Hierarchical Ring (HR) Each peer stores d pointers at each level Level 1: first d immediate successors HR - Level 2:  HR - Level 2 For each peer, The first entry in level 2 is the last entry in level 1 Peer asks first entry at level 2 for its first level 2 entry E.g p1’s first level 2 entry is p3. p3’s first level 2 entry is p5. So, p1’s second level 2 entry is p5. HR - Level 3:  HR - Level 3 The first level 3 entry is the last level 2 entry Each peer learns its second level 3 entry by asking its own first level 3 entry for its level 3 entry Table is complete when last entry wraps around ring Routing:  Routing Each peer responsible for range = (id, succ(p).id] Range query at p1: (18, 25] First Hop: p3 Next Hop: p4 p4 returns items in (18, 20] p4 forwards query to p5 p5 returns items in (20, 25] Content Router Properties:  Content Router Properties Number of levels in Hierarchical Ring is log d (P) Space required at each peer is O(d logd(P)) Routing algorithm takes at most one hop at each level. Theorem: In a stable system of P peers with a consistent Hierarchical Ring, equality queries take at most ⎡logd(P)⎤hops. Content Router Performance:  Content Router Performance 4 node insertions/failures per second Compare number of hops needed for lookup for various stabilization frequencies Text Summary:  Summary P-Ring efficiently supports both exact match and single-dimensional range queries Load balancing guaranteed in presence of skewed data insertions and deletions Effect of joins, leaves, and failures? P-Ring is used as platform for developing protocols with strict semantics Guaranteeing Correctness and Availability in P2P Range Indices, Linga, et al. SIGMOD 2005

Add a comment

Related presentations

Related pages

Spring - Die Küche liebt Spring

Spring bietet hochwertiges Kochgeschirr, Fondue und Raclette für den Haushalt und Buffet Systeme für die Gastronomie. Die Küche liebt Spring.
Read more

Pring Research

Subscribe to Martin's monthly InterMarket Review . A 34+ page monthly publication which will keep you current on the U ...
Read more

SPRING GemeindeFerienFestival, 17. bis 22. April 2017 ...

Das GemeindeFerienFestival Was ist SPRING? In der Woche nach Ostern treffen sich rund 3.500 Menschen und feiern fünf Tage miteinander und beschäftigen ...
Read more

Hier sollte eine Beschreibung angezeigt werden, diese Seite lässt dies jedoch nicht zu.
Read more

Pring´s KST von Martin J. Pring Erklärung – Technische ...

Pring´s KST von Martin J. Pring Erklärung – Technische AnalyseDer von Martin J. Pring entwickelte und nach ihm benannte „Pring’s KST“ steht für...
Read more


Spring helps development teams everywhere build simple, portable, fast and flexible JVM-based systems and applications.
Read more

Spring (Framework) – Wikipedia

Spring Dynamic Modules agiert als Brücke zwischen dem Spring-Framework und OSGi. Anwendungen auf Basis des Spring-Frameworks können hierdurch mit OSGi ...
Read more

Urban Dictionary: pring

(verb) A form of vertical movement, closely associated with trampolining & cheerleading (not gymnastics). Pring describes a conscious, bigger ...
Read more

Pring Research : Pring Products. DVD & Online Courses : Complete Technical Analysis Course Price: $399.95 ... Copyright© 1994-2016 Pring Research, Inc.
Read more | Online Druckerei Testsieger mit TÜV ...

Erstes TÜV-Zertifikat für die Branche Online Druck Testsieger für beste Produktqualität & Kundenservice Persönliche Beratung ☎ 0800-6022260.
Read more