Skip to content

Latest commit

 

History

History
78 lines (58 loc) · 3.08 KB

p3.md

File metadata and controls

78 lines (58 loc) · 3.08 KB
Raw

The SprayList: A Scalable Relaxed Priority Queue

  • Priority Queue with relaxed ordering semantics.
  • Functionally similar to conventional concurrent non-blocking SkipList appart from DeleteMin operation
  • DeleteMin done by spraying on SkipList, landing at height H, jumping across L length and decending D, until reaches the bottom where it tries to pick up the Node.
  • If failed for whatever reason (e.g. Node marked, contention or Node is a padding Node, retry spray.
  • Proved that high probabilities DeleteMin return an element among the first O(p log^3 p) where p is the number of threads.
  • Proved that high probabilities, DeleteMin will retrun in O(log^3 p) regardless of SkipList size.
  • unlike traditional SkipList that randomly starts at the left-most Node clashing on the first element of each level, SparyList allows Node to be skip ahead, reducing contention.

Algorithm

  • The idea is to have operation transverse the SkipList Nodes at a controlled random motion
  • Generally for a SkipList probablity of a Node appearing at a level l is 2^-l or 1/2^l`
  • each level is a LinkedList
  • levels are there so search resembles O(log) instead of O(n) like linked list
  • levels serves as lock-striding during contention
  • Node must present at most bottom layer
  • Node deleted are marked (pointer marking) and later removes through some means
  • Node are ordered typically left to right representing small to large respectively or whatever orderly semantics
  • search operation does clean up as well i.e. removing pointers / references of marked Nodes to their predecessor and successors.
  • if we Node being marked half way through, restart again (it means someone beats us to it)
  • insert of Node is done at random height
No Controlled Random Motion Description
1. Start at some Height (h)
2. At level (l) definied by height (h), jump forward a random number of steps
3. Transverse Nodes at that level
4. Decend a number of levels (d)
5. Repeat until reach the bottom most level Node
6. At the bottom find the actual Node
7. If successfully found, start deletion, else retry spray or become cleaner

Spray Parameters

Parameters Description
n number of elements
p number of threads accessing
H starting height H = log p + K
L Jump length L = M * log^3 p
D Level to decend D = max(1, log log p)

Se algorithm 1 in paper (section 2.2)

Padding

With spraying, highly unlikely to hit the first element, so fix this by padding 'padding' nodes.

Add K(p) dummy entries, if hit dummy entries, respray.

Cleaners

Each thread that reach the bottom before respray, do a low probability coin flip to turn into a cleaner. Probablity of thread becoming cleaner is 1/p.

Adapting

thread adjust p, under high collision, increase it otherwise lower it.

 [ ]             
 [ ]      [ ]       [ ]