Fast skip list purge

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 the first thread; and

in response to identifying a key-value record in the assigned section for purging, the first thread replacing ones of the unresolved pointers with pointers included in the key-value record to be purged.

18. The computer readable medium of claim 17 , wherein the operations further comprise:

subsequent to the assigned sections being scanned by the plurality of threads:

accessing the key-value records used as boundaries of the sections to identify ones of the boundary key-value records for purging; and

in response to identifying a boundary key-value record for purging, traversing down the skip list to identify key-value records to be updated in response to the boundary key-value record being purged.

19. The computer readable medium of claim 16 , wherein the operations further comprising:

inserting key-value records into the skip list as database transactions corresponding to the inserted key-value records await commitment; and

in response to a database transaction corresponding to one of the inserted key-value records committing, setting a flag in the inserted key-value record to indicate that the inserted key-value record is permitted to be purged from the skip list.

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