Class: StrokeDB::ChunkedSkiplist

Inherits:
Object
  • Object
show all
Defined in:
lib/strokedb/data_structures/chunked_skiplist.rb

Overview

ChunkedSkiplist (CS) implements a distributed, concurrently accessible skiplist using SimpleSkiplist (SL) as building blocks. Each instance contains a single instance of SimpleSkiplist. Higher-level CS store references to lower-level SL as SL “data”. Lowest-level CS contains actual data.

Regular state of the chunks (square brackets denote references): 

               ______        ___________________      
             /        \    /                     \
HEAD -> C1[ C2, C3 ], C2[ C4, C5 ], C3[ C6, C7 ], C4[data], ...

> __/

Initial state is a single lowest-level chunk:

HEAD -> C1[data]

When higher-level node is inserted, new skiplist is created. Old skiplist is moved to a new chunk, current chunk uppers its level.

ASYNCHRONOUS CONCURRENT INSERT

SKiplists, by their nature, allow you to concurrently insert and delete nodes. However, very little number of nodes must be locked during update. In our implementation, we lock a whole chunk if it is modified. Higher-level chunks are modified rarely, so they are not locked most of the time. Different chunks could be updated concurrently. Read-only concurrent access is always possible no matter what nodes are

locked for modification.

ChunkedSkiplist has an API for asynchronous data access useful for cöoperative multitasking, but it is also thread-safe for preemtive multitasking, which is kinda nice feature, but is not to be evaluated in a real-world applications.

Chunked #find

Find may return an actual data or a reference to lower-level chunk. It is a networking wrapper business to do interpret the result of #find.

Insert is harder =) When new node level is higher than data chunk level we have to insert into proxy chunk and create all the levels of proxy chunks down to the data chunk. If node level is low, we just insert node into appropriate data chunk. The hard part about it are locking issues during insertion.

Constant Summary collapse

DEFAULT_MAXLEVEL = 
7
DEFAULT_PROBABILITY = 
1/Math::E

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(lo_level = nil, hi_level = nil, probability = nil, container = nil) ⇒ ChunkedSkiplist

Returns a new instance of ChunkedSkiplist.



56
57
58
59
60
61
62
 
# File 'lib/strokedb/data_structures/chunked_skiplist.rb', line 56

def initialize(lo_level = nil, hi_level = nil, probability = nil, container = nil)
  @lo_level = lo_level || 0
  @hi_level = hi_level || DEFAULT_MAXLEVEL
  @probability = probability || DEFAULT_PROBABILITY
  @container = container || SimpleSkiplist.new(nil, 
                         :maxlevel => @hi_level + 1, :probability => @probability)
end

Instance Attribute Details

#container ⇒ Object

Returns the value of attribute container.



51
52
53
 
# File 'lib/strokedb/data_structures/chunked_skiplist.rb', line 51

def container
  @container
end

#hi_level ⇒ Object

Returns the value of attribute hi_level.



51
52
53
 
# File 'lib/strokedb/data_structures/chunked_skiplist.rb', line 51

def hi_level
  @hi_level
end

#lo_level ⇒ Object

Returns the value of attribute lo_level.



51
52
53
 
# File 'lib/strokedb/data_structures/chunked_skiplist.rb', line 51

def lo_level
  @lo_level
end

#probability ⇒ Object

Returns the value of attribute probability.



51
52
53
 
# File 'lib/strokedb/data_structures/chunked_skiplist.rb', line 51

def probability
  @probability
end

Instance Method Details

#find(key) ⇒ Object

Finds reference to another chunk (if proxy) or an actual data.



101
102
103
 
# File 'lib/strokedb/data_structures/chunked_skiplist.rb', line 101

def find(key)
  proxy? ? @container.find_nearest(key) : @container.find(key)
end

#generate_chain(key, value, size, start_level) ⇒ Object 



95
96
97
 
# File 'lib/strokedb/data_structures/chunked_skiplist.rb', line 95

def generate_chain(key, value, size, start_level)
  
end

#insert(key, value, __level = nil) ⇒ Object

Insertion cases:

                             |
[ levels 16..23 ]         |  |
[ levels 08..15 ]      |  |  |
[ levels 00..07 ]   |  |  |  | 
                    A  B  C  D

A - insert in a lower-level chunk
B - insert in a 08..15-levels chunk, create new 0..7-level chunk
C - insert in a 16..23-levels chunk, create new chunks of levels 
    0..7 and 8..15.
D - create new 24..31-levels chunk with reference to previous head.



85
86
87
 
# File 'lib/strokedb/data_structures/chunked_skiplist.rb', line 85

def insert(key, value, __level = nil)
  @container.insert(key, value, __level)
end

#promote_level(key, level, size) ⇒ Object

Create new chunk, move local skiplist there, create new skiplist here and insert



91
92
93
 
# File 'lib/strokedb/data_structures/chunked_skiplist.rb', line 91

def promote_level(key, level, size)
  
end

#proxy? ⇒ Boolean

If chunk is not a lowest-level list, then it contains references to other chunks. Hence, it is a “proxy”.

Returns:

  • (Boolean) 


67
68
69
 
# File 'lib/strokedb/data_structures/chunked_skiplist.rb', line 67

def proxy?
  @lo_level > 0
end

#random_level ⇒ Object

Generates random level of arbitrary size. In other words, it actually contains an infinite loop.



107
108
109
110
111
112
 
# File 'lib/strokedb/data_structures/chunked_skiplist.rb', line 107

def random_level
  p = @probability
	l = 1
	l += 1 while rand < p
	return l
end