Supporting concurrent updates to a database page

A method for supporting concurrent updates to a database page may include providing shared access to the database page. A first update may be performed with respect to a first record in the database page. A second update may be performed with respect to a second record in the database page. The first update and the second update may be performed concurrently while the shared access to the database page is being provided. The method may also include synchronizing the first update and the second update.

BACKGROUND

A relational database is a collection of data items organized as a set of formally described tables from which data can be accessed. A relational database management system (which may be referred to herein simply as a database system) facilitates access to a relational database by receiving queries from users, applications, or other entities, executing such queries against the relational database to produce a results dataset, and returning the results dataset to the entities that submitted the queries. The queries may be represented using Structured Query Language (SQL) or another suitable database query language.

The fundamental unit of storage in a database system is typically referred to as a database page (or simply a page). The disk space allocated to a data file in a database is logically divided into database pages, which may be numbered contiguously from 0 to N. Disk input/output operations are typically performed at the database page level. In other words, a database system typically reads or writes whole database pages.

Database pages may be updated by threads. In this context, the term “thread” refers to a unit of execution within a computing system. A thread may be the smallest sequence of programmed instructions that can be managed independently for scheduling purposes. Multiple threads can exist within one process, executing concurrently and sharing resources such as memory.

In the context of a relational database, the term “transaction” refers to a unit of work performed against a database that may be treated in a coherent and reliable way independent of other transactions. A database transaction should be atomic, consistent, isolated, and durable. Atomicity means that each transaction is treated as a single unit that either succeeds completely or fails completely. Consistency ensures that a transaction can only bring the database from one valid state to another. Isolation ensures that concurrent execution of transactions leaves the database in the same state that would have been obtained if the transactions were executed sequentially. Durability means that once a transaction has been committed, it will remain committed even in the event of a system failure (e.g., a power outage or crash). Database practitioners often refer to these properties of database transactions using the acronym ACID.

If a system failure affects the operation of a database system, it is generally desirable to recover the database and return to normal operation as quickly as possible. Recovery algorithms have been developed for this purpose. One family of recovery algorithms is known as Algorithms for Recovery and Isolation Exploiting Semantics (ARIES).

One aspect of ARIES algorithms is write-ahead logging. With write-ahead logging, any change to a database page is first recorded in a transaction log, and the transaction log is written to stable storage before changes to the database page are written to disk. Log entries are sequentially ordered with log sequence numbers.

To facilitate write-ahead logging, a database page that is going to be updated may first be read into a buffer. The desired updates may be recorded in the transaction log. The updates may then be made to the copy of the database page in the buffer. Finally, the copy of the database page in the buffer may be flushed back to disk (i.e., written to storage).

Another aspect of ARIES algorithms is dirty page tracking. Dirty page tracking involves keeping track of which database pages are “dirty.” In the context of a database system that utilizes write-ahead logging, a dirty page is a database page that has been updated in the buffer but not yet flushed back to disk.

DETAILED DESCRIPTION

In a database system that uses write-ahead logging techniques, a thread that is going to update a database page typically reserves exclusive access to the database page. For example, the thread may obtain an exclusive latch (or an update latch) for the database page. The purpose of reserving exclusive access is to synchronize the update with other updates that may be performed with respect to the database page while also allowing reads in parallel. In this context, the term “synchronize” refers to one or more operations that may be performed to ensure the integrity of updates that are made to a database. Synchronization makes it possible to serialize the log records and updates to the database page. Synchronization may be performed in relation to updates that are part of the same transaction. Thus, reserving exclusive access to perform an update may help ensure that the update can be safely performed and recovered in the event of a system failure.

One problem with obtaining exclusive access to a database page is that a thread may perform a large number of operations while exclusive access is maintained. This may adversely affect the transaction throughput because many other threads might be contending to obtain exclusive access to the database page. The time that these other threads spend waiting to obtain exclusive access to the database page is essentially wasted.

The present disclosure is generally related to techniques for supporting concurrent updates to a database page. In accordance with the present disclosure, a thread that is going to update a database page may, under some circumstances, reserve shared access to the database page instead of reserving exclusive access. This enables multiple threads to be able to concurrently update the database page. Synchronization may be performed using an alternative approach other than reserving exclusive access. For example, instead of reserving exclusive access to the database page that is going to be updated, a thread may reserve exclusive access to another database element (e.g., another database page) that corresponds to the particular record that is going to be updated in the database page. Functions that ensure atomicity may be used for the kinds of operations that are typically performed to facilitate recovery, such as generating log records and managing dirty page tracking.

FIG. 1illustrates an example of a database system100that is configured to support concurrent updates to a database page104in accordance with the present disclosure. In this example, it will be assumed that multiple threads108a-bare going to perform updates116a-bwith respect to records106a-bin the database page104. With known approaches, these updates116a-bwould be performed serially. In accordance with the present disclosure, however, these updates116a-bmay be performed in parallel.

With known approaches, a thread that updates a database page reserves exclusive access to the database page. In accordance with the present disclosure, however, the threads108a-bthat are going to update the database page104may reserve shared access to the database page104instead of reserving exclusive access. Synchronization may then be performed using an alternative approach other than reserving exclusive access. For instance, instead of reserving exclusive access to the database page104, the threads108a-bmay reserve exclusive access to other database elements102a-bthat correspond to the particular records106a-bin the database page104that are going to be updated.

In the depicted example, the first thread108ais going to update a first record106ain the database page104. The first record106amay correspond to a first database element102a, such that having exclusive access to the first database element102amay protect the integrity of any updates that are made to the first record106a. In other words, if the first thread108aobtains exclusive access to the first database element102a, it may be unlikely (or, in some cases, impossible) that another thread would update the first record106ain the database page104as long as the first thread108amaintains exclusive access to the first database element102a.

In this kind of scenario, the first thread108amay obtain exclusive access to the first database element102aand shared access to the database page104, so that other threads may also have shared access to the database page104. This would allow, for example, the second thread108bto perform an update116bwith respect to a second record106bin the database page104at the same time that the first thread108aperforms an update116awith respect to the first record106a.

In some implementations, the first thread108amay obtain an exclusive latch110afor the first database element102aand a shared latch112afor the database page104. Similarly, the second thread108bmay obtain an exclusive latch110bfor the second database element102band a shared latch112bfor the database page104.

In this context, the term “latch” refers to a representation of an intent to utilize a database resource. A latch may be obtained by a thread with respect to a particular resource (e.g., a database page). If a thread obtains an exclusive latch with respect to a particular resource, then no other thread is able to use that resource while the exclusive latch is active. An exclusive latch may be used to protect the integrity of updates that are being made to records, so that the updates are not compromised (e.g., overwritten) by other updates that are being performed concurrently. Another type of latch is a shared latch. If a thread obtains a shared latch with respect to a resource, this does not prevent other threads from also using that resource in parallel.

The updates116a-bto the database page104may be structured so that the updates116a-bdo not result in cascading operations (e.g., page split, merge) being performed with respect to the database page104. For example, the updates116a-bmay be structured so that they do not cause any of the records106a-bin the database page104to be moved to another database page (or any records from another database page to be moved to the database page104). This helps ensure the integrity of the updates116a-bwithout providing exclusive access to either of the threads108a-b. In some implementations, the records106a-bwithin the database page104may have a fixed size. This is not required, however, and in alternative implementations the records106a-bmay have a variable size.

The database system100may be configured to implement one or more algorithms that facilitate recovery in the event of system failure. Such algorithms typically assume that when a thread is updating a database page, the thread has exclusive access to that database page. In a database system100where multiple threads108a-bcan simultaneously have shared access to a database page104and perform updates116a-bwith respect to that database page104, the recovery algorithm(s) may need to be modified in order to function properly. These modifications may be related to generating log records114a-bin a transaction log144and managing data structure(s)122for dirty page tracking. Some specific examples of modifications to the recovery algorithm(s) will be discussed below.

FIG. 2illustrates an example of a method200for supporting concurrent updates116a-bto a database page104. The method200will be described in relation to the database system100shown inFIG. 1. The method200shows how the first thread108amay update the first record106ain the database page104in a way that other threads (e.g., the second thread108b) may simultaneously update other records (e.g., the second record106b) in the database page104.

In the depicted method200, some of the operations202a,204a,206a,208amay be performed by the first thread108a, while other operations202b,204b,206b,208amay be performed by the second thread108b. The first thread108amay perform the operations202a,204a,206a,208ain parallel with the second thread108bperforming the operations202b,204b,206b,208a. The other operation210in the method200may be performed collectively by both of the threads108a-bworking together and/or by one or more other components of the database system100.

In accordance with the method200, a first thread108athat is going to update a first record106ain a database page104may obtain202aexclusive access to a first database element102acorresponding to the first record106a. For example, the first thread108amay obtain an exclusive latch110afor the first database element102a. Obtaining202aexclusive access to the first database element102amay prevent any other threads from updating the first database element102aas long as the first thread108ahas exclusive access to the first database element102a. Obtaining202aexclusive access to the first database element102amay also make it unlikely (or, in some cases, impossible) for any other thread to update the first record106ain the database page104as long as the first thread108ahas exclusive access to the first database element102a.

The first thread108amay also obtain204ashared access to the database page104. For example, the first thread108amay obtain a shared latch112afor the database page104. Having shared access to the database page104does not prevent other threads (such as the second thread108b) from simultaneously updating the database page104.

A second thread108bthat is going to update a second record106bin the database page104may obtain202bexclusive access to a second database element102bcorresponding to the second record106b. For example, the second thread108bmay obtain an exclusive latch110bfor the second database element102b. The second thread108bmay also obtain204bshared access to the database page104. For example, the second thread108bmay obtain a shared latch112bfor the database page104. These operations202b,204bmay be performed in parallel to the similar operations202a,204aperformed by the first thread108a.

To facilitate recovery in the event of system failure, the first thread108amay generate206aa first log record114afor the update116ato the first record106a. Similarly, the second thread108bmay generate206ba second log record114bfor the update116bto the second record106b. The log records114a-bmay be stored in a transaction log144.

The first thread108amay perform208aan update116awith respect to the first record106ain the database page104, and the second thread108bmay perform208ban update116bwith respect to the second record106bin the database page104. These updates116a-bmay be performed in parallel with one another.

The database system100may also manage210dirty page synchronization. This may involve creating and maintaining one or more data structure(s)122that facilitate dirty page tracking. Some additional examples of how dirty page synchronization may be managed210will be provided below.

FIG. 3illustrates another example of a database system300that is configured to support concurrent updates to a database page304in accordance with the present disclosure. The database system300inFIG. 3is similar in some respects to the database system100inFIG. 1. For example, multiple threads308a-bmay concurrently perform updates316a-bto records306a-bin a database page304. To synchronize these updates316a-bwithout reserving exclusive access to the database page304, the threads308a-bmay reserve exclusive access to database elements302a-bcorresponding to the records306a-bthat are going to be updated. For example, a first thread308athat is going to update a first record306ain the database page304may obtain an exclusive latch310afor a first database element302acorresponding to the first record306a. Similarly, a second thread308bthat is going to update a second record306bin the database page304may obtain an exclusive latch310bfor a second database element302bcorresponding to the second record306b. The threads308a-bmay obtain shared latches312a-bfor the database page304that includes the records306a-bto be updated.

The database system300may be configured to use write-ahead logging techniques. As a result, the database page304that is going to be updated may be read from storage into a buffer342. Log records314a-bfor the desired updates316a-bmay be generated and stored in a transaction log344. The updates316a-bmay then be made to the database page304in the buffer342. After the updates316a-b(and other operations related to facilitating recovery in the event of system failure) have been performed, the database page304may be flushed to disk (or in other words, written to storage).

The database page304may be prepared for dirty page tracking in accordance with a recovery algorithm, such as an ARIES recovery algorithm. Both the first thread308aand the second thread308bmay attempt to set up one or more data structures322for tracking dirty pages. These attempts may be structured so that only one of the threads308a-bsuccessfully creates the data structure(s)322. In some implementations, the threads308a-bmay use one or more functions that ensure atomicity to set up the data structure(s)322. For example, the threads308a-bmay use one or more compare-and-swap operations to set up the data structure(s)322. In this context, the term “compare-and-swap” refers to an atomic instruction used in multithreading to achieve synchronization. In a compare-and-swap operation, the contents of a memory location are compared with a given value and, only if they are the same, the contents of that memory location are given a new value. This is done as a single atomic operation. The atomicity guarantees that the new value is calculated based on up-to-date information. In some implementations, the compare-and-swap operation(s) described herein may be performed using interlocked compare exchange (ICX) function(s).

For purposes of the present example, it will be assumed that the first thread308asuccessfully creates the dirty page tracking data structure(s)322and that the second thread308bfails. The second thread308buses the dirty page tracking data structure(s)322that were created by the first thread308a.

The first thread308amay generate a first log record314acorresponding to the update316athat will be performed with respect to the first record306a. The second thread308bmay generate a second log record314bcorresponding to the update316bthat will be performed with respect to the second record306b. The log sequence number (LSN)318aof the first log record314amay be different from the LSN318bof the second log record314b. For purposes of the present example, it will be assumed that the LSN318aof the first log record314ahas a value of L1, the LSN318bof the second log record314bhas a value of L2, and L2>L1.

As noted above, in currently known database systems, updates to a database page are performed serially so that only one update is performed at a time. In such database systems, when an update is performed, the LSN of the database page is set to the LSN of the log record that is created in connection with the update. Setting the LSN of the database page in this manner facilitates recovery from system failure. The present disclosure, however, makes it possible for a database system300to perform multiple updates316a-bconcurrently. To facilitate recovery operations in this type of database system300, the LSN324of the database page304may be set to the maximum of the LSNs318a-bof the log records314a-bassociated with the updates316a-bthat have been performed with respect to the database page304.

In the present example, the update316aperformed by the first thread308ais associated with a log record314ahaving an LSN318aof L1, and the update316bperformed by the second thread308bis associated with a log record314bhaving an LSN318bof L2, where L2>L1. Thus, in the present example, the LSN324of the database page304may be set to L2. The maximum value of the LSNs318a-bmay be determined using one or more compare-and-swap operations. In some implementations, the maximum value of the LSNs318a-bmay be determined using an interlocked maximum LSN operator, which may be built using interlocked compare exchange operators.

The database page304may be marked as “dirty” in the dirty page tracking data structure(s)322. A record326corresponding to the database page304may be created in the dirty page tracking data structure(s)322. This record326may include an LSN328, which may be referred to herein as a dirty page LSN328.

In currently known database systems, when an update is performed, the value of the dirty page LSN is set to the LSN of the log record that first updated the page in the current flush cycle (i.e., since the page was most recently flushed to disk). In a database system300in accordance with the present disclosure, however, multiple threads308a-bmay simultaneously perform updates316a-bwith respect to the database page304. In the presence of multiple concurrent threads308a-bthat are trying to dirty the database page304, the dirty page LSN328may be set to the minimum of the LSNs318a-bof the log records314a-bassociated with the updates316a-bthat dirtied the database page304. Thus, in the present example, the dirty page LSN328corresponding to the database page304may be set to L1.

To determine the minimum of the LSNs318a-bof the log records314a-bassociated with the updates316a-bthat dirtied the database page304, all the threads308a-bthat have performed updates316a-bwith respect to the database page304(and which therefore have generated log records314a-b) should contribute to the computation of the dirty page LSN328. The minimum value of the LSNs318a-bthat dirtied the database page304may be determined using one or more compare-and-swap operations. In some implementations, the minimum value of the LSNs318a-bthat dirtied the database page304may be determined using an interlocked minimum LSN operator, which may be built using interlocked compare exchange operators.

Although the log records314a-bcorrespond to different database elements302a-b, the log records314a-bmay have the same previous page LSN320. In accordance with known recovery algorithms (e.g., ARIES recovery algorithms), when redo operations are performed with respect to log records, the LSN checks are very strict in order to detect missed flushes. As a result, the previous page LSN values are taken into account. In accordance with the present disclosure, however, the redo of the log records314a-bmay be performed starting from the dirty page LSN328without checking the previous page LSN320values, because it may not be possible to rely on the previous page LSN320values for purposes of redo operations. By redoing all of the log records314a-bstarting from the dirty page LSN328, it may be possible to guarantee that all of the operations that were logged before a system failure can still be performed even after the system failure.

FIG. 4illustrates a method400for supporting concurrent updates316a-bto a database page304in a database system300that uses write-ahead logging techniques. In addition to showing how multiple threads308a-bmay concurrently perform updates316a-bwith respect to a database page304, the method400also illustrates how recovery algorithms may be modified in order to accommodate shared access to the database page304.

In the depicted method400, some of the operations402a,404a,408a,410a,412a,420a,422amay be performed by the first thread308a, while other operations402b,404b,408b,410b,412b,420b,422bmay be performed by the second thread308b. The first thread308amay perform the operations402a,404a,408a,410a,412a,420a,422ain parallel with the second thread308bperforming the operations402b,404b,408b,410b,412b,420b,422b. The other operations406,414,416,418in the method400may be performed collectively by both of the threads308a-bworking together and/or by one or more other components of the database system300.

In accordance with the method400, a first thread308athat is going to update a first record306ain a database page304may obtain402aan exclusive latch310afor the first database element302a. The first thread308amay also obtain404aa shared latch312afor the database page304. In parallel with these operations402a,404abeing performed by the first thread308a, a second thread308bthat is going to update a second record306bin the database page304may obtain402ban exclusive latch310bfor the second database element302band obtain404ba shared latch312bfor the database page304.

Both the first thread308aand the second thread308bmay attempt406to create one or more data structures322for tracking dirty pages. The threads308a-bmay use one or more compare-and-swap operations to attempt to set up the data structure(s)322so that only one of the threads308a-bsuccessfully creates the data structure(s)322. In some implementations, the threads308a-bmay use one or more interlocked compare exchange (ICX) functions to attempt to set up the data structure(s)322. For purposes of the present example, it will be assumed that the first thread308asuccessfully creates408athe dirty page tracking data structure(s)322and that the second thread308bfails. The second thread308bthen uses408bthe dirty page tracking data structure(s)322that were created by the first thread308a.

The first thread308amay generate410aa first log record314acorresponding to the update316athat will be performed with respect to the first record306a. In this example, the LSN318aof the first log record314ahas a value of L1. The second thread308bmay generate410ba second log record314bcorresponding to the update316bthat will be performed with respect to the second record306b. In this example, the LSN318bof the second log record314bhas a value of L2, where L2>L1.

The first thread308amay perform412aan update316awith respect to the first record306ain the database page304, and the second thread308bmay perform412ban update316bwith respect to the second record306bin the database page304. The updates316a-bmay be performed in a way that ensures atomicity. In other words, the first thread308amay perform412athe update316awith respect to the first record306ain a way that does not interfere with other concurrent updates to the database page304(including the update316bperformed by the second thread308bwith respect to the second record306b). Similarly, the second thread308bmay perform412bthe update316bwith respect to the second record306bin a way that does not interfere with other concurrent updates to the database page304(including the update316aperformed by the first thread308awith respect to the first record306a). To ensure atomicity, one or more compare-and-swap operations may be used.

The LSN324of the database page304may be set414to the maximum of the LSNs318a-bof the log records314a-bassociated with the updates316a-bthat have been performed with respect to the database page304. In the present example, the LSN324of the database page304may be set414to L2.

The database page304may be marked416as “dirty” in the dirty page tracking data structure(s)322. The dirty page LSN328may be set418to the minimum of the LSNs318a-bof the log records314a-bassociated with the updates316a-bthat dirtied the database page304. Thus, in the present example, the dirty page LSN328corresponding to the database page304may be set to L1.

When the log records314a-bhave been generated410a-b, the updates316a-bhave been performed412a-b, the LSN324of the database page304has been set414, the database page304has been marked416as dirty in the dirty page tracking data structure(s)322, and the dirty page LSN328has been set418, the first thread308amay release420athe shared latch312afor the database page304and release422athe exclusive latch310afor the first database element302a. Similarly, the second thread308bmay release420bthe shared latch312bfor the database page304and release422bthe exclusive latch310bfor the second database element302b. At some point thereafter, the updates316a-bmay be flushed to disk.

FIG. 5illustrates another example of a database system500that is configured to support concurrent updates to a database page in accordance with the present disclosure. In the example shown inFIG. 5, the database page being updated is a page free space (PFS) page504.

A PFS page504is a special database page that may be used to hold metadata about other database pages. Each page within the database system500may have a record within a PFS page504. Although just one PFS page504is shown inFIG. 5, a database system may include multiple PFS pages. A PFS page504typically includes records for a relatively large number of different database pages (e.g., 8088 pages). Each record may be a fixed size (e.g., one byte). The record within a PFS page504that corresponds to a particular database page may include metadata about that database page, such as its allocation/deallocation status, its page usage status, whether the page has versions, whether the page has ghost records, whether the page is an IAM (Identity and Access Management) page, etc.

InFIG. 5, the PFS page504is shown with multiple records, including a first record506athat includes first metadata560acorresponding to a first database page502aand a second record506bthat includes second metadata560bcorresponding to a second database page502b. In accordance with the present disclosure, these records506a-bmay be updated in parallel.

If a first thread508aobtains exclusive access to the first database page502a, this may prevent another thread from updating the first record506ain the PFS page504aas long as the first thread508ahas exclusive access to the first database page502a. Thus, to facilitate parallel updating of the records506a-bin the PFS page504, the first thread508amay obtain exclusive access to the first database page502aand shared access to the PFS page504, so that other threads may also have shared access to the PFS page504. Similarly, the second thread508bmay obtain exclusive access to the second database page502band shared access to the PFS page504. This would allow both threads508a-bto concurrently perform updates516a-bwith respect to the records506a-bin the PFS page504.

In some implementations, the first thread508amay obtain an exclusive latch510afor the first database page502aand a shared latch512afor the PFS page504. The second thread508bmay obtain an exclusive latch510bfor the second database page502band a shared latch512bfor the PFS page504. Log records may be generated and dirty page tracking may be performed in a manner similar to the examples discussed previously.

FIGS. 6A-Billustrate another example of a database system600that is configured to support concurrent updates to a database page in accordance with the present disclosure. In the example shown inFIGS. 6A-B, the database page being updated corresponds to a node that is part of a B-tree representation of data. An example of a B-tree656is shown inFIG. 6A. The B-tree656includes a root node648, a plurality of branch nodes650a-b, and a plurality of leaf nodes652a-g.

Referring to both the B-tree656shown inFIG. 6Aand the database system600shown inFIG. 6B, suppose that a first thread608ais going to perform an update616awith respect to data corresponding to a first key654ain the leaf node652a, and a second thread608bis going to perform an update616bwith respect to data corresponding to a second key654bin the leaf node652a. In accordance with the present disclosure, these updates616a-bmay be performed simultaneously.

To facilitate concurrent updates616a-b, the threads608a-bmay access a database page604that corresponds to the leaf node652a. This database page604may be referred to herein as a leaf node database page604. The first thread608amay obtain exclusive access to the key654aand shared access to the leaf node database page604. For example, the first thread608amay obtain an exclusive latch610afor the key654aand a shared latch612afor the leaf node database page604that includes a record606acorresponding to the key654a. Similarly, the second thread608bmay obtain an exclusive latch610bfor the key654band a shared latch612bfor the leaf node database page604that includes a record606bcorresponding to the key654b. Log records may be generated and dirty page tracking may be performed in a manner similar to the examples discussed previously.

FIG. 7illustrates certain components that may be included within a computer system700. One or more computer systems700may be used to implement the various devices, components, and systems described herein.

The computer system700includes a processor701. The processor701may be a general purpose single- or multi-chip microprocessor (e.g., an Advanced RISC (Reduced Instruction Set Computer) Machine (ARM)), a special purpose microprocessor (e.g., a digital signal processor (DSP)), a microcontroller, a programmable gate array, etc. The processor701may be referred to as a central processing unit (CPU). Although just a single processor701is shown in the computer system700ofFIG. 7, in an alternative configuration, a combination of processors (e.g., an ARM and DSP) could be used.

The computer system700also includes memory703in electronic communication with the processor701. The memory703may be any electronic component capable of storing electronic information. For example, the memory703may be embodied as random access memory (RAM), read-only memory (ROM), magnetic disk storage media, optical storage media, flash memory devices in RAM, on-board memory included with the processor, erasable programmable read-only memory (EPROM), electrically erasable programmable read-only memory (EEPROM) memory, registers, and so forth, including combinations thereof.

Instructions705and data707may be stored in the memory703. The instructions705may be executable by the processor701to implement some or all of the functionality disclosed herein. Executing the instructions705may involve the use of the data707that is stored in the memory703. Any of the various examples of modules and components described herein may be implemented, partially or wholly, as instructions705stored in memory703and executed by the processor701. Any of the various examples of data described herein may be among the data707that is stored in memory703and used during execution of the instructions705by the processor701.

A computer system700may also include one or more communication interfaces709for communicating with other electronic devices. The communication interface(s)709may be based on wired communication technology, wireless communication technology, or both. Some examples of communication interfaces709include a Universal Serial Bus (USB), an Ethernet adapter, a wireless adapter that operates in accordance with an Institute of Electrical and Electronics Engineers (IEEE) 802.11 wireless communication protocol, a Bluetooth® wireless communication adapter, and an infrared (IR) communication port.

A computer system700may also include one or more input devices711and one or more output devices713. Some examples of input devices711include a keyboard, mouse, microphone, remote control device, button, joystick, trackball, touchpad, and lightpen. Some examples of output devices713include a speaker and a printer. One specific type of output device that is typically included in a computer system700is a display device715. Display devices715used with embodiments disclosed herein may utilize any suitable image projection technology, such as liquid crystal display (LCD), light-emitting diode (LED), gas plasma, electroluminescence, or the like. A display controller717may also be provided, for converting data707stored in the memory703into text, graphics, and/or moving images (as appropriate) shown on the display device715.

In accordance with an aspect of the present disclosure, a method for supporting concurrent updates to a database page is disclosed. The method may include providing shared access to the database page, performing a first update with respect to a first record in the database page, and performing a second update with respect to a second record in the database page. The first update and the second update may be performed concurrently while the shared access to the database page is being provided. The method may also include synchronizing the first update and the second update. In some implementations, neither the first update nor the second update may cause cascading operations to be performed with respect to the database page.

The first update may be performed by a first thread and the second update may be performed by a second thread. The first thread and the second thread may obtain the shared access to the database page. To synchronize the first update and the second update, the first thread may obtain exclusive access to a first database element corresponding to the first record and the second thread may obtain exclusive access to a second database element corresponding to the second record. The first thread may obtain a first exclusive latch corresponding to a first database element, and a first shared latch corresponding to the database page. The second thread may obtain a second exclusive latch corresponding to a second database element, and a second shared latch corresponding to the database page.

The method may be performed by a database system that implements write-ahead logging. The method may further include using compare-and-swap operations to generate log records for the first update and the second update, and manage dirty page synchronization.

In some implementations, the database page may include a page free space (PFS) page. As another example, the database page may include a node that is part of a B-tree representation of data.

In accordance with another aspect of the present disclosure, a method for supporting concurrent updates to a database page in a database system that implements write-ahead logging is disclosed. In accordance with the method, a first thread may obtain exclusive access to a first database element that corresponds to a first record in the database page. A second thread may obtain exclusive access to a second database element that corresponds to a second record in the database page. The first thread may perform a first update with respect to the first record in the database page, and the second thread performing a second update with respect to the second record in the database page. The first update and the second update may be performed concurrently. Neither the first thread nor the second thread may have exclusive access to the database page.

In some implementations, the database page may include a page free space (PFS) page. The first record may include first metadata corresponding to a first database page. The second record may include second metadata corresponding to a second database page.

In some implementations, the database page may correspond to a node that is part of a B-tree representation of data. The first record may correspond to a first key of the node. The second record may correspond to a second key of the node.

The method may further include generating a first log record for the first update, generating a second log record for the second update, and setting a log sequence number of the database page to a maximum of the first log sequence number and the second log sequence number. The first log record may include a first log sequence number. The second log record may include a second log sequence number.

Both the first thread and the second thread may attempt to create a dirty page tracking data structure. Only one of the first thread or the second thread may successfully create the dirty page tracking data structure.

The method may further include creating at least one data structure for dirty page tracking, generating a first log record for the first update, and generating a second log record for the second update. The first log record may include a first log sequence number. The second log record may include a second log sequence number. The method may further include setting a dirty page log sequence number to a minimum of the first log sequence number and the second log sequence number.

In accordance with another aspect of the present disclosure, a system is disclosed for supporting concurrent updates to a database. The system may include one or more processors, memory in electronic communication with the one or more processors, and a database page stored in the memory. The database page may include a first record and a second record. Instructions may also be stored in the memory. The instructions may be executable by the one or more processors to provide shared access to the database page, perform a first update with respect to a first record in the database page, and perform a second update with respect to a second record in the database page. The first update and the second update may be performed concurrently while the shared access to the database page is being provided. The instructions may also be executable by the one or more processors to synchronize the first update and the second update.

In some implementations, the first update may be performed by a first thread. The second update may be performed by a second thread. Neither the first thread nor the second thread may have exclusive access to the database page.

The first update may be performed by a first thread and the second update may be performed by a second thread. The instructions may be additionally executable by the one or more processors to cause the first thread to obtain a first exclusive latch corresponding to a first database element, the first thread to obtain a first shared latch corresponding to the database page, the second thread to obtain a second exclusive latch corresponding to a second database element, and the second thread to obtain a second shared latch corresponding to the database page.

The instructions may be additionally executable by the one or more processors to generate a first log record for the first update and to generate a second log record for the second update. The first log record may include a first log sequence number. The second log record may include a second log sequence number. The instructions may be additionally executable by the one or more processors to set a log sequence number of the database page to a maximum of the first log sequence number and the second log sequence number.

The instructions may be additionally executable by the one or more processors to create at least one data structure for dirty page tracking, generate a first log record for the first update, and generate a second log record for the second update. The first log record may include a first log sequence number. The second log record may include a second log sequence number. The instructions may be additionally executable by the one or more processors to set a dirty page log sequence number to a minimum of the first log sequence number and the second log sequence number.

In some implementations, the database page may include a page free space (PFS) page. As another example, the database page may include a node that is part of a B-tree representation of data.