pring

Information about pring

Published on February 11, 2008

Author: Simeone

Source: authorstream.com

Content

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

Related presentations


Other presentations created by Simeone

Introduction to Design Pattern
14. 02. 2008
0 views

Introduction to Design Pattern

Erikson and Horney
15. 01. 2008
0 views

Erikson and Horney

Sudden Illnesses 9
14. 01. 2008
0 views

Sudden Illnesses 9

Customer loyalty presentaion
15. 03. 2008
0 views

Customer loyalty presentaion

topic5 ravi
10. 01. 2008
0 views

topic5 ravi

cloning
15. 01. 2008
0 views

cloning

aecma
16. 01. 2008
0 views

aecma

Tox Made Simple
18. 01. 2008
0 views

Tox Made Simple

NEO YOUNG CREATIVE AWARD 2007
04. 02. 2008
0 views

NEO YOUNG CREATIVE AWARD 2007

GLJ Mobile Logistics121207
04. 02. 2008
0 views

GLJ Mobile Logistics121207

CohenLevesque
07. 02. 2008
0 views

CohenLevesque

Ancient Cosmetic toxicology
10. 01. 2008
0 views

Ancient Cosmetic toxicology

1stReviewppt
25. 01. 2008
0 views

1stReviewppt

newsfile469 1
28. 01. 2008
0 views

newsfile469 1

15 Comets
16. 01. 2008
0 views

15 Comets

imci c slides
25. 02. 2008
0 views

imci c slides

Friday
28. 02. 2008
0 views

Friday

delta 2
09. 01. 2008
0 views

delta 2

Safetyprogram
05. 03. 2008
0 views

Safetyprogram

2 20071224184840
11. 03. 2008
0 views

2 20071224184840

websearch
19. 03. 2008
0 views

websearch

schreffler hopkins
21. 03. 2008
0 views

schreffler hopkins

CKtrain green
15. 01. 2008
0 views

CKtrain green

era2
03. 04. 2008
0 views

era2

mother100703
09. 01. 2008
0 views

mother100703

dahlbom
21. 01. 2008
0 views

dahlbom

Comics and Mangas
18. 02. 2008
0 views

Comics and Mangas

AMC Online Trip Listings
06. 02. 2008
0 views

AMC Online Trip Listings

CPZvezda Brus
22. 01. 2008
0 views

CPZvezda Brus