Fast skip list purge

Patent metadata

Field	Value
Publication number	US-11625386-B2
Application number	US-202117162794-A
Country	US
Kind code	B2
Filing date	Jan 29, 2021
Priority date	Jan 29, 2021
Publication date	Apr 11, 2023
Grant date	Apr 11, 2023

Abstract

Techniques are disclosed relating to efficiently managing skip list data structures. In some embodiments, a computing system stores a skip list including a plurality of key-value records that include one or more pointers to others of the plurality of key-value records. The computing system scans the plurality of key-value records in key order to identify key-value records to be purged from the skip list. The scanning includes maintaining a list of key-value records that include pointers that point to key-value records that have not yet been scanned by the scanning. In response to identifying a key-value record for purging, the computing system purges the key-value record by substituting the pointers included the key-value records of the list with pointers included in the key-value record being purged.

First claim

What is claimed is:

1. A non-transitory computer readable medium having program instructions stored thereon that are capable of causing a computing system to implement operations comprising:
storing a skip list including a plurality of key-value records that include one or more pointers to others of the plurality of key-value records;
scanning the plurality of key-value records in key order to identify key-value records to be purged from the skip list, wherein the scanning includes:
maintaining a list of key-value records that include pointers that point to key-value records that have not yet been scanned by the scanning; and

in response to identifying a key-value record for purging, purging the key-value record by substituting the pointers included in the key-value records of the list with pointers included in the key-value record being purged.

2. The computer readable medium of claim 1 , wherein the operations further comprise:
inserting the key-value record into the skip list in response to a request to perform a database transaction associated with the key-value record; and
in response to the database transaction committing and the key-value record being stored in a persistent storage of a database, setting a flag in the key-value record to indicate that the key-value record is authorized to be purged; and
wherein the scanning includes identifying the key-value record for purging based on the set flag.

3. The computer readable medium of claim 1 , wherein the scanning includes:
determining that a pointer of a first key-value record included in the list points to a second key-value record that has now been scanned;
in response to the determining:
replacing the first key-value record in the list with the second key-value record; and
preventing relocation of the second key-value record within memory while the second key-value is included in the list.

4. The computer readable medium of claim 1 , wherein the operations further comprise:
inserting one or more key-value records into the skip list while the scanning is being performed.

5. The computer readable medium of claim 4 , wherein the operations further comprise:
in response to identifying the key-value record for purging, performing a verification of the list of key-value records, wherein the verification includes:
determining whether the pointers included in the key-value records of the list point to the key-value record for purging.

6. The computer readable medium of claim 5 , wherein the operations further comprise:
in response to determining that the inserting has caused one or more pointers included in the key-value records of the list to not point to the key-value record for purging, delaying the purging of the key-value record until a subsequent scanning is performed.

7. The computer readable medium of claim 5 , wherein the verification includes:
acquiring latches to prevent modification of the key-value records by processes other than a process performing the scanning; and
maintaining acquisition of the latches until after the substituting of the pointers included the key-value records of the list with pointers included in the key-value record being purged.

8. The computer readable medium of claim 1 , wherein the operations further comprise:
prior to the scanning of the plurality of key-value records in key order:
walking down the skip list to identify a subset of the plurality of key-value records;
based on the key-value records in the identified subset, dividing the skip list into sections; and
assigning the sections to a plurality of threads executable to scan the sections in parallel.

9. The computer readable medium of claim 8 , wherein the operations further comprise:
receiving, by one of the plurality of threads, an assigned section for scanning;
scanning, by the thread, the assigned section, wherein scanning the assigned section includes maintaining, for the assigned section, a list of key-value records with unresolved pointers; and
in response to identifying a key-value record for purging in the assigned section, the thread uses the list of key-value records for the assigned section to purge the key-value record in the assigned section.

10. The computer readable medium of claim 1 , wherein a first of the plurality of key-value records in the skip list points to a second of the plurality of key-value records in the skip list by including a first pointer that points to a bucket in a hash table, wherein the bucket includes a second pointer to the second key-value record.

11. A method, comprising:
storing, by a computing system, a skip list that maintains an ordering of keys for key-value records of a database;
identifying, by the computing system, key-value records to be purged from the skip list, including:
scanning through the skip list in key order to determine whether ones of the key-value records include an indication that purging is permitted;
recording unresolved pointers of key-value records in the skip list, wherein the unresolved pointers point to ones of the key-value records that have yet to be scanned by the scanning; and

in response to identifying a key-value record to be purged, the computing system purging the key-value record by replacing ones of the unresolved pointers with pointers included in the key-value record being purged.

12. The method of claim 11 , further comprising:
prior to the scanning, the computing system traversing a top portion of the skip list to determine divisions of the skip list for parallel scanning; and
assigning, by the computing system, the divisions to a plurality of threads executable to scan the divisions in parallel with one another.

13. The method of claim 11 , further comprising:
during the scanning, the computing system inserting one or more key-value records into the skip list; and
in response to identifying the key-value record to be purged, the computing system verifying that the ones of the unresolved pointers still point to the key-value record to be purged after inserting the one or more key-value records.

14. The method of claim 13 , further comprising:
in response to determining that, at least, one of the unresolved pointers no longer points to the key-value record to be purged, delaying the purging of the key-value record until a subsequent scanning of the skip list is performed.

15. The method of claim 11 , wherein the skip list maintains the ordering of keys for key-value records of database transactions awaiting commitment by the database.

16. A non-transitory computer readable medium having program instructions stored thereon that are capable of causing a computing system to implement operations comprising:
maintaining a skip list that preserves an ordering of keys for a plurality of key-value records;
dividing the skip list into sections, wherein the sections are identified by traversing a top portion of the skip list to identify ones of the key-value records to be used as boundaries of the sections; and
assigning the sections to a plurality of threads, each being executable in parallel to scan an assigned section of the skip list in key order to identify key-value records for purging from the skip list.

17. The computer readable medium of claim 16 , wherein the operations further comprise:
maintaining, by a first of the plurality of threads, a list of unresolved pointers for the section assigned to the first thread, wherein the unresolved pointers are pointers included in key-value records scanned by the first thread that point to key-value records that have not yet been scanned by th

Assignees

• Salesforce Com Inc

Inventors

• Helland Patrick James
• Mace James E
• Manchale Sridhar Akshay

Classifications

• G06F16/2255

  Hash tables · CPC title

• G06F16/2308 Primary

  Concurrency control (transaction processing G06F9/466) · CPC title

• G06F16/2365 Primary

  Ensuring data consistency and integrity · CPC title