Shared synchronized skip-list data structure and technique employing linearizable operations

• US 7,424,477 B1
• Filed: 09/03/2003
• Issued: 09/09/2008
• Est. Priority Date: 09/03/2003
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Martin, Paul A., Moir, Mark S., Steele, Guy L. Jr., Shavit, Nir N., Luchangco, Victor M., Heller, Steven K.
• Primary Examiner(s): Cottingham; John
• Assistant Examiner(s): Rayyan; Susan F
• Application Number:
  US10/653,828
• Time in Patent Office: 1,833 Days
• Field of Search: 707 1- 3, 707/8, 707100-102
• US Class Current: 1/1
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

A set of structures and techniques are described herein whereby an exemplary concurrent shared object, namely a shared skip list, can be implemented in a lock-free manner. Indeed, we have developed a number of interesting variants of a lock-free shared skip-list, including variants that may be employed to provide a lock-free shared dictionary. In some variants, a key-value dictionary is implemented.

Claims

1. A method of operating on a shared data structure that includes a representation of an ordered set of keys, the method comprising:

instantiating nodes of the shared data structure in memory, wherein plural levels of same direction referencing chains traverse respective subsets of the nodes in accordance with a key ordering relationship thereof, a first-level of the referencing chains traversing each node of the shared data structure and at least one other level of the referencing chains traversing less than all nodes of the shared data structure; and

operating on the shared data structure using insert-type and delete-type operations that are linearizable and lock-free for all concurrent executions thereof,

wherein the insert-type operation performs a synchronized update of pointers beginning at the first level thereof and continuing upward, and

wherein the delete-type operation performs a synchronized update of pointers beginning at a K^th level thereof and continuing downward to the first level.

2. The method of claim 1,

wherein the insert-type operation performs a synchronized update of pointers in accordance with a first succession of the levels;

and

wherein the delete-type operation performs a synchronized update of pointers in accordance with a second succession of the levels, the second succession opposing the first succession.

3. The method of claim 1, further comprising:

for a given one of the nodes instantiated, dynamically selecting a number of the plural, same-direction referencing chains that traverse the given node.

4. The method of claim 1, wherein the shared data structure implements a dictionary.

5. The method of claim 1, wherein values are associated with respective ones of the keys, the method further comprising:

as part of an execution of the insert-type operation introducing a value into the shared data structure; and

as part of an execution of the delete-type operation removing a value from the shared data structure the removed value corresponding to a search key.

6. The method of claim 5, wherein the correspondence includes a greater-than-or-equal-to key match criterion.

7. A computer readable shared memory storing encoding of a shared object, the encoding comprising:

plural nodes;

plural levels of same-direction referencing chains that traverse respective subsets of the nodes in accordance with a key ordering relationship thereof, a first of the referencing chains traversing each node of the shared data structure and a second of the referencing chains traversing less than all nodes of the shared data structure; and

a functional encoding of linearizable operations on the shared object, wherein the linearizable operations include both insert-type and remove-type operations and are lock-free for all concurrent executions thereof,

wherein the insert-type operation performs a synchronized update of pointers beginning at the first level thereof and continuing upward, and

wherein the delete-type operation performs a synchronized update of pointers beginning at a K^th level thereof and continuing downward to the first level.

8. The computer readable storage medium encoding of claim 7, wherein, on at least some executions, the insert-type introduces an additional node into at least one of the referencing chains.

9. The computer readable storage medium encoding of claim 7, wherein, on at least some executions, the delete-type operation excises a particular node from all referencing chains that traverse the particular node.

10. The computer readable storage medium encoding of claim 7, wherein the delete-type operation employs a greater-than-or-equal-to key match criterion.

11. The computer readable storage medium encoding of claim 7, wherein the shared object implements a shared skip-list-type data structure.

12. The computer readable storage medium encoding of claim 7, wherein the shared object implements a dictionary data structure.

13. In a computational system that employs a shared list-type data structure that includes plural nodes and plural levels of referencing chains that traverse respective ones of the nodes in accordance with an ordering thereof wherein a higher-level one of the referencing chains traverses no more than a subset of the nodes traversed by a lower-level one of the referencing chains, a method of facilitating lock-free concurrent operations on the shared list-type data structure, the method comprising:

deleting a node from the shared list-type data structure by excising the node from successive ones of the referencing chains, beginning with a highest-level one of the referencing chains that traverses the node and continuing through a lowest-level one of the referencing chains, wherein each such excision employs a linearizable synchronization operation to bridge the excised node and associate a dead pointer indication therewith; and

inserting a node into the shared list-type data structure by introducing the inserted node into one or more of the referencing chains, beginning with the lowest-level referencing chains and continuing through successive zero or more higher-level referencing chains.

14. The method of claim 13, wherein all concurrent executions of the deleting and the inserting are linearizable and lock-free.

15. The method of claim 13, wherein the dead pointer indication includes one of:

a self pointer;

a pointer to a dead node; and

a back pointer.

16. A method comprising:

defining a shared list-type data structure that includes plural nodes and plural levels of same direction referencing chains that traverse at least some of the nodes in accordance with an ordering thereof, wherein a higher-level one of the referencing chains traverses no more than a subset of the nodes traversed by a lower-level one of the referencing chains; and

inserting into, and deleting from, the shared list-type data structure, wherein all concurrent executions of the deleting and the inserting are linearizable and lock-free,

wherein the inserting comprises performing a synchronized update of pointers beginning at a first level and continuing upward, and

wherein the deleting comprises performing a synchronized update of pointers beginning at a K^th level and continuing downward to the first level.

17. An apparatus comprising:

a definition of a skip list instantiable in storage; and

lock-free means for coordinating concurrent and linearizable executions of both insert-type and delete-type operations on the skip list,

wherein the insert-type operation performs a synchronized update of pointers beginning at the first level thereof and continuing upward, and

a processor;

wherein the delete-type operation performs a synchronized update of pointers beginning at a K^th level thereof and continuing downward to the first level.

18. The apparatus of claim 17, further comprising:

the storage.

19. The apparatus of claim 17, further comprising:

plural processors, the insert-type and delete-type operations executable thereon.