Efficient support of consistent cyclic search with read-copy-update

• US 7,814,082 B2
• Filed: 03/18/2008
• Issued: 10/12/2010
• Est. Priority Date: 03/08/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): EHICHIOYA, IRETE FRED
• Application Number:
  US12/050,559
• Publication Number:
  US 20080177742A1
• Time in Patent Office: 938 Days
• Field of Search: 707/609, 707/704, 707/705, 707/802, 710/200, 711/102, 711/104, 711/116, 711/138
• US Class Current: 707/704
• CPC Class Codes: G06F 16/2336 Pessimistic concurrency control approaches, e.g. locking or multiple versions without time stamps
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A method, system and computer program product for modifying data elements in a shared data element group that must be updated atomically for the benefit of readers requiring group integrity. A global generation number is associated with the data element group and each member receives a copy of this number when it is created. Each time an update is performed, the global generation number is incremented and the updated element'"'"'s copy of this number is set to the same value. For each updated data element, a link is maintained from the new version to the pre-update version thereof, either directly or using pointer-forwarding entities. When a search is initiated, the current global generation number is referenced at the commencement of the search. As data elements in the group are traversed, the reader traverses the links between new and old data element versions to find a version having a matching generation number, if any. Following the occurrence of a grace period in which all readers have passed through quiescent states, all old data element versions are freed.

Claims

1. A data processing system having one or more central processing units, a memory and a communication pathway between the one or more central processing units and the memory, said system being adapted to update a shared data element group in said memory while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, and comprising:

means for generating a new group data element;

means for assigning a new generation number to said new data element that is different than an existing global generation number associated with said data element group and which allows a reader of said data element group to determine whether said new data element is a correct version for said reader;

means for establishing a first version link from said new data element to a prior version thereof;

means for establishing a second version link from said prior version to said new data element;

means for linking said new data element into said data element group so that it is reachable by readers;

means for updating said global generation number associated with said data element group to correspond to said new generation number; and

means for freeing said prior version and said first and second version links following a grace period.

2. A system in accordance with claim 1 wherein said system is adapted to replace a group data element and to generate said new data element by copying said data element to be replaced.

3. A system in accordance with claim 1 wherein said system is adapted to delete a group data element and to generate said new data element by copying said data element to be deleted and setting a deletion flag in said new data element.

4. A system in accordance with claim 1 wherein said system is adapted to insert a new group data element such that said new data element has no prior versions.

5. A system in accordance with claim 1 wherein said system further includes means for generating a pointer-forwarding entity that points to said new data element, said pointer forwarding entity maintaining said version link on behalf of said new data element and further being used to link said new data element into said data element group.

6. A data processing system having one or more central processing units, a memory and a communication pathway between the one or more central processing units and the memory, said system being adapted to perform a search of a shared data element group that may be undergoing modification by the system the system of claim 1, and comprising:

means for assigning a current global generation number to said search;

means for determining, when referencing a data element in said data element group, whether said referenced data element is a correct version by comparing a generation number assigned to said referenced data element with said search generation number; and

means for searching for a correct version of said referenced data element as necessary.

7. A system in accordance with claim 6 wherein said system is adapted to accept said referenced data element for reading as a correct version if said data element generation number is equal to said search generation number.

8. A system in accordance with claim 6 wherein said system is adapted to search for a later version of said referenced data element if said data element generation number is less than said search generation number, and to use said referenced data element if a later version is not found.

9. A system in accordance with claim 6 wherein said system is adapted to search for a prior version of said referenced data element if said data element generation number is greater than said search generation number, and to deem said referenced data element to be a new insertion if there is no prior version.

10. A data processing system having one or more central processing units, a memory and a communication pathway between the one or more central processing units and the memory, said system being adapted to update a shared data element group in said memory while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, and comprising:

means for generating a pointer-forwarding entity that points to a data element in said data element group;

means for assigning a new generation number to said pointer-forwarding entity that is different than an existing global generation number associated with said data element group and which allows a reader of said data element group to determine whether said pointer-forwarding entity is a correct version for said reader;

means for establishing a first version link from said pointer-forwarding entity and a prior version thereof;

means for establishing a second version link from said prior version to said pointer-forwarding entity;

means for linking said pointer-forwarding entity into said data element group so that said data element pointed to by said pointer-forwarding entity is reachable by readers through said pointer-forwarding entity;

means for updating said global generation number associated with said data element group to correspond to said new generation number; and

means for freeing said prior version and said first and second version links following a grace period.

11. A computer program product for updating a shared data element group while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, comprising:

one or more data storage media;

means recorded on said data storage media for programming a data processing platform to operate as by;

generating a new group data element;

assigning a new generation number to said new data element that is different than an existing global generation number associated with said data element group and which allows a reader of said data element group to determine whether said new data element is a correct version for said reader;

establishing a first version link from said new data element to a prior version thereof;

establishing a second version link from said prior version to said new data element;

linking said new data element into said data element group so that it is reachable by readers;

updating said global generation number associated with said data element group to correspond to said new generation number; and

freeing said prior version and said first and second version links following a grace period.

12. A computer program product in accordance with claim 11 wherein said product is adapted to replace a group data element and to generate said new data element by copying said data element to be replaced.

13. A computer program product in accordance with claim 11 wherein said product is adapted to delete a group data element and to generate said new data element by copying said data element to be deleted and setting a deletion flag in said new data element.

14. A computer program product in accordance with claim 11 wherein said product is adapted to insert a new group data element such that said new data element has no prior versions.

15. A computer program product in accordance with claim 11 wherein said means recorded on said data storage media are further adapted to generate a pointer-forwarding entity that points to said new data element, said pointer forwarding entity maintaining said version link on behalf of said new data element and further being used to link said new data element into said data element group.

16. A computer program product for performing a search of a shared data element group that may be undergoing modification in accordance with the method of claim 11, comprising:

one or more data storage media;

means recorded on said data storage media for programming a data processing platform to operate as by;

assigning a current global generation number to said search;

when referencing a data element in said data element group, determining whether said referenced data element is a correct version by comparing a generation number assigned to said referenced data element with said search generation number; and

searching for a correct version of said referenced data element as necessary.

17. A computer program product in accordance with claim 16 wherein, if said data element generation number is equal to said search generation number, said referenced data element is accepted for reading as a correct version.

18. A computer program product in accordance with claim 16 wherein, if said data element generation number is less than said search generation number, a search is made for a later version of said referenced data element, and wherein said referenced data element is used if a later version is not found.

19. A computer program product in accordance with claim 16 wherein, if said data element generation number is greater than said search generation number, a search is made for a prior version of said referenced data element, and wherein said referenced data element is deemed to be a new insertion if there is no prior version.

20. A computer program product for updating a shared data element group while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, comprising:

one or more data storage media;

means recorded on said data storage media for programming a data processing platform to operate as by;

generating a pointer-forwarding entity that points to a data element in said data element group;

assigning a new generation number to said pointer-forwarding entity that is different than an existing global generation number associated with said data element group and which allows a reader of said data element group to determine whether said pointer-forwarding entity is valid for said reader;

establishing a first version link from said pointer-forwarding entity and a prior version thereof;

establishing a second version link from said prior version to said pointer-forwarding entity;

linking said pointer-forwarding entity into said data element group so that said data element pointed to by said pointer-forwarding entity is reachable by readers through said pointer-forwarding entity;

updating said global generation number associated with said data element group to correspond to said new generation number; and

freeing said prior version and said first and second version links following a grace period.

21. A computer program product for managing a shared data element group so as to allow updates thereof while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions, comprising:

one or more data storage media;

means recorded on said data storage media for programming a data processing platform to operate as by;

performing a first-phase update operation that preserves a consistent pre-update view of said data element group on behalf of pre-update readers and a consistent post-update view of the data element group on behalf of post-update readers;

providing means by which readers can locate all data elements of said data element group that belong to each of said pre-update and post-update views as readers search said data element group;

performing one or more read operations following said first-phase update operation in which one or more readers search said data element group with each reader referencing only data elements belonging to one of said pre-update and post-update views; and

performing a second-phase update operation following a grace period that frees said pre-update view of said data element group.