Database concurrency control through hash-bucket latching

A non-transitory computer readable medium having program instructions stored thereon that are capable of causing a computing system to implement operations comprising:

• receiving a first key-value pair for a first database transaction, wherein the first key-value pair includes a first value and a first key usable to locate the first value in persistent storage;
• storing the first key-value pair in a data structure for active database transactions, wherein the storing includes:
• indexing into a hash table of the data structure by applying a hash function to the first key of the first key-value pair to identify a hash bucket of the hash table corresponding to the first key;
• acquiring a latch associated with the identified hash bucket;
• and
• based on a state of the acquired latch, appending, to the hash bucket, a record specifying the first key of the first key-value pair, the first value of the first key-value pair, and a transaction identifier for the first database transaction, wherein the transaction identifier is specified by other records in the data structure to identify the other records as belonging to the same database transaction as the appended record;
• linking the appended record to another record in the data structure by including, in the other record, a pointer to the identified hash bucket;
• causing the first key-value pair and key-value pairs of the other records belonging to the same database transaction to be committed from the data structure to the persistent storage in response to the first database transaction being committed.

A non-transitory computer readable medium having program instructions stored thereon that are capable of causing a computing system to implement operations comprising:

• receiving a first request to read a first value of a first key-value pair associated with a database transaction;
• and
• reading the first value from a database structure that maintains data associated with active transactions of a database system, wherein the reading includes:
• identifying a hash bucket in a hash table by applying a hash function a first key of the first key-value pair to index into the hash table;
• determining a state of a latch that restricts access to a linked list appended to the hash bucket;
• and
• based on the state of the latch, accessing the linked list to read a record in the linked list that includes the first value, the first key, and a transaction identifier of the database transaction, wherein the transaction identifier is usable to identify other records in the database structure as belonging to the same database transaction as the record in the linked list;
• and
• in response to committing the database transaction, committing the first key-value pair and key-value pairs of the other records from the database structure to a persistent storage of the database system.

A non-transitory computer readable medium having program instructions stored thereon that are capable of causing a database system to implement operations comprising:

• determining to modify a record in a skip list that maintains an ordering of keys for key-value pairs stored in a data structure that maintains the key-value pairs for active database transactions, wherein the record is usable to identify a predecessor key or a successor key for a particular key of a key-value pair associated with a database transaction;
• based on the particular key of the key-value pair, indexing into a hash table of the data structure to identify a hash bucket of the hash table by applying a hash function to the particular key of the key-value pair;
• acquiring a latch in the hash bucket, wherein the latch restricts use of the hash bucket;
• modifying the record in response to acquiring the latch, wherein the record includes the particular key, a value of the key-value pair, and a transaction identifier of the database transaction, and wherein the transaction identifier is usable to identify other records in the data structure as belonging to the same database transaction as the modified record;
• and
• in response to committing the database transaction, committing the key-value pair and key-value pairs of the other records from the data structure to a persistent storage of the database system, wherein the particular key included in the record is usable by the database system to determine where to store the value of the key-value pair in the persistent storage.