288
scalable concurrent skip list
3
implementation with fine-grain locking distinguished by
a combination of simplicity and scalability. Figure 14-3 demonstrates the basic idea of
the skip list data structure. It is a multilayered linked list-like data structure where the
bottom layer is an ordered linked list. Each higher layer acts as an “express lane” for
the following lists and allows it to skip elements during lookup operations. An element
in layer i appears in layer i+1 with some fixed probability p (in our implementation p
= 1/2). That is, the frequency of nodes of a particular height decreases exponentially
with the height. Such properties allow it to achieve O(log n) average time complexity
for lookup, insert, and delete operations. O(log n) means the running time grows at
most proportional to “log n”. You can learn more about Big O notation on Wikipedia at
https://en.wikipedia.org/wiki/Big_O_notation
For the implementation of pmem::obj::concurrent_map, the find and insert
operations are thread-safe and can be called concurrently with other find and insert
operations without requiring additional synchronizations.
Find Operation
Because the find operation is non-modifying, it does not have to deal with data
consistency issues. The lookup operation for the target element always begins from the
topmost layer. The algorithm proceeds horizontally until the next element is greater
or equal to the target. Then it drops down vertically to the next lower list if it cannot
proceed on the current level. Figure 14-3 illustrates how the find operation works for the
element with key=9. The search starts from the highest level and immediately goes from
dummy head node to the node with key=4, skipping nodes with keys 1, 2, 3. On the node
with key=4, the search is dropped two layers down and goes to the node with key=8.
Then it drops one more layer down and proceeds to the desired node with key=9.
3
M. Herlihy, Y. Lev, V. Luchangco, N. Shavit. A provably correct scalable concurrent skip list. In
OPODIS ‘06: Proceedings of the 10th International Conference On Principles Of Distributed
Systems, 2006; https://www.cs.tau.ac.il/~shanir/nir-pubs-web/Papers/OPODIS2006-BA.
pdf.
Chapter 14 ConCurrenCy and persistent MeMory
scalable concurrent skip list
3
implementation with fine-grain locking distinguished by
a combination of simplicity and scalability. Figure 14-3 demonstrates the basic idea of
the skip list data structure. It is a multilayered linked list-like data structure where the
bottom layer is an ordered linked list. Each higher layer acts as an “express lane” for
the following lists and allows it to skip elements during lookup operations. An element
in layer i appears in layer i+1 with some fixed probability p (in our implementation p
= 1/2). That is, the frequency of nodes of a particular height decreases exponentially
with the height. Such properties allow it to achieve O(log n) average time complexity
for lookup, insert, and delete operations. O(log n) means the running time grows at
most proportional to “log n”. You can learn more about Big O notation on Wikipedia at
https://en.wikipedia.org/wiki/Big_O_notation
For the implementation of pmem::obj::concurrent_map, the find and insert
operations are thread-safe and can be called concurrently with other find and insert
operations without requiring additional synchronizations.
Find Operation
Because the find operation is non-modifying, it does not have to deal with data
consistency issues. The lookup operation for the target element always begins from the
topmost layer. The algorithm proceeds horizontally until the next element is greater
or equal to the target. Then it drops down vertically to the next lower list if it cannot
proceed on the current level. Figure 14-3 illustrates how the find operation works for the
element with key=9. The search starts from the highest level and immediately goes from
dummy head node to the node with key=4, skipping nodes with keys 1, 2, 3. On the node
with key=4, the search is dropped two layers down and goes to the node with key=8.
Then it drops one more layer down and proceeds to the desired node with key=9.
3
M. Herlihy, Y. Lev, V. Luchangco, N. Shavit. A provably correct scalable concurrent skip list. In
OPODIS ‘06: Proceedings of the 10th International Conference On Principles Of Distributed
Systems, 2006; https://www.cs.tau.ac.il/~shanir/nir-pubs-web/Papers/OPODIS2006-BA.
pdf.
Chapter 14 ConCurrenCy and persistent MeMory