Patent ID: 12242727

In the drawings, like reference numbers generally indicate identical or similar elements. Additionally, generally, the left-most digit(s) of a reference number identifies the drawing in which the reference number first appears.

DETAILED DESCRIPTION

Provided herein are system, apparatus, device, method and/or computer program product embodiments, and/or combinations and sub-combinations thereof, for providing lock-free read access to data structures using garbage collection.

As described above, because other threads may be ongoing (e.g., parallel threads), the first portion of the memory may not be able to be immediately freed. If the memory manager (responsible for freeing memory) is unaware of all of the ongoing threads in the database system, the memory manager cannot determine when the first portion of the memory can be freed. Meanwhile, locking can be required to ensure only proper data is read on the data structure. However, performance bottlenecks and problems may be produced due to locking.

Therefore, a technological solution is needed to provide a lock-free read access to data structures. The technological solution in the present disclosure can provide a lock-free read access to data structures using garbage collection. The first portion of the memory cannot be freed immediately. Instead the first portion of the memory can be attached to a garbage collection system that ensures that the first portion of the memory is freed far enough in the future so that no parallel thread might still operate on the data.

FIG.1illustrates an example system100implementing mechanisms for providing lock-free read access to data structures using garbage collection, according to some embodiments of the disclosure. The example system100is provided for the purpose of illustration only and does not limit the disclosed embodiments.

The example system100includes, but is not limited to, a client device102, a server system104and a network106. The server system104includes one or more server devices108. In one example, a user can interact with the client device102. In an example context, the user can include a user who interacts with an application that is hosted by the server system104.

In some examples, the client device102can communicate with one or more of the server devices108over the network106. In some examples, the client device102can include any appropriate type of computing device such as a desktop computer, a laptop computer, a handheld computer, a tablet computer, a personal digital assistant (PDA), a cellular telephone, a network appliance, a camera, a smart phone, an enhanced general packet radio service (EGPRS) mobile phone, a media player, a navigation device, an email device, a game console, or an appropriate combination of any two or more of these devices or other data processing devices.

In some implementations, the network106can include a large computer network, such as a local area network (LAN), a wide area network (WAN), the Internet, a cellular network, a telephone network (e.g., PSTN) or an appropriate combination thereof connecting any number of communication devices, mobile computing devices, fixed computing devices and server systems.

In some implementations, each server device108includes at least one server and at least one data store. In the example ofFIG.1, the server devices108are intended to represent various forms of servers including, but not limited to a web server, an application server, a proxy server, a network server, and/or a server pool. In general, server systems accept requests for application services and provides such services to any number of client devices (e.g., the client device102) over the network106.

In accordance with implementations of the present disclosure, the server system104can host a database system that stores data. In some examples, the database system can store data in one or more data structures. In some examples, the one or more data structures can include a vector and/or a hashmap. In some examples, the client device102can interact with the database system to access data stored therein. For example, the client device102can interact with the database system to read data from, delete data from, add data to, and/or modify data within one or more data structures. It is contemplated that other devices, such as server systems, can interact with the database system over the network106.

An example database system can include an in-memory database. In some examples, an in-memory database is a database management system that uses main memory for data storage. In some examples, main memory includes random access memory (RAM) that communicates with one or more processors (e.g., central processing units (CPUs)), over a memory bus. An-memory database can be contrasted with database management systems that employ a disk storage mechanism. In some examples, in-memory databases are faster than disk storage databases, because internal optimization algorithms can be simpler and execute fewer CPU instructions (e.g., require reduced CPU consumption). In some examples, accessing data in an in-memory database eliminates seek time when querying the data, which provides faster and more predictable performance than disk-storage databases. An example in-memory database system includes SAP HANA provided by SAP SE of Walldorf, Germany.

As introduced above, implementations of the present disclosure are directed to provide a lock-free read access to data structures using garbage collection. More particularly, implementations of the present disclosure are directed to maintaining pendency of a clean-up entry (that can be executed to free memory) until any parallel threads are executed.

FIG.2Adepicts an example conceptual architecture200in accordance with implementations of the present disclosure. The example conceptual architecture is provided for the purpose of illustration only and does not limit the disclosed embodiments.

The conceptual architecture200includes a database system201that receives transaction data204. In some examples, the transaction data204can indicate a transaction that is to be performed by the database system201. In the depicted example, the database system201includes a first data structure202and a second data structure208, a transaction manager206and a clean-up manager214.

In some examples, each of the first data structure202and the second data structure208can include a vector or a hash map. In some examples, a vector can include a sequence container to store a list of elements and not index based. Vector can be dynamic and a size of the vector can increase with insertion of elements. A vector can use contiguous storage locations for the elements. The elements can also be accessed using offsets on pointers to the elements. In some examples, a hash map is a data structure that maps keys to values. A hash map can use a hash function to compute an index into an array of buckets or slots, from which the corresponding value can be found.

In some examples, the transaction manager206can be informed of transactions that are to be performed in the database system201. For example, the transaction data204can indicate a transaction associated with first data structure202and/or second data structure208, and the transaction manager206can be informed of execution of the transaction on first data structure202and/or second data structure208. Example transactions can include reading data from, writing data to, deleting data from, and modifying data within first data structure202and/or second data structure208.

In some examples, the transaction manager206can coordinate transactions that are to be performed in the database system201. Example transactions can include a first transaction, such as reading data from, writing data to, deleting data from, and modifying data within first data structure202. Example transactions can include a second transaction, such as reading data from, writing data to, deleting data from, and modifying data within second data structure208. In some examples, the transaction data204can indicate the first transaction associated with first data structure202and the second transaction associated with second data structure208. The transaction manager206can coordinate an order to perform the first transaction or the second transaction. For example, the transaction manager206can determine that the first transaction can be executed prior to an execution of the second transaction. Alternatively or in addition, the transaction manager206can determine that the first transaction can be executed subsequent to an execution of the second transaction.

In some examples, a database abstraction layer (e.g., a SQL layer) (not shown inFIG.2) coordinates communication between an application (e.g., executing on an application server), and the database system201. In some examples, the database abstraction layer analyzes an incoming statement (e.g., insert, update, delete, select), and forwards it to the first data structure202and/or second data structure208. When forwarding transactions, the transaction manager206is involved in assigning, for example, a transaction identifier, timestamps, and the like.

In some examples, when a transaction is completed, the transaction is assigned a commit timestamp (commitTS) upon completion (committal) of the transaction, and a read timestamp (readTS) when the transaction starts. In some examples, the readTS is equal to the highest previously assigned commitTS. Logically, this means that a transaction may see all operations, which have been committed before the transaction starts. The readTS can be seen as the snapshot of the data that a transaction may see. A minimum readTS (minReadTS) is also provided, and is the lowest readTS of all running transactions (parallel transactions) in the system. The transaction manager206can be continuously aware of the minReadTS.

In some examples, every data object in the database is assigned a commitTS, which is equal to the commitTS of the transaction that created the object. For example, when an element is inserted to the first data structure202, the first data structure202can be assigned the commitTS of the transaction that was executed to insert the element, upon completion of the transaction (e.g., after the transaction commits).

FIG.2Billustrates a block diagram of an example data structure, according to some embodiments. The example data structure is provided for the purpose of illustration only and does not limit the disclosed embodiments.FIG.2Bmay be described with regard to elements ofFIGS.1and2A.

As shown inFIG.2B, first data structure202includes a first data structure202A and a first data structure202B. In some examples, the first data structure202A can include a vector or list with four elements. As described above, a vector can use contiguous storage locations for the elements. In some examples, first data structure202A can use main memory for data storage, as described with reference toFIG.1. For example, a first portion of a memory for data storage, such as associated with server system104, may be allocated for first data structure202A.

In some examples, when inserting data into first data structure202A in a write transaction or a thread to write, a size of the vector can increase with insertion of elements. For example, first data structure202A can grow in size and be modified to first data structure202B. When inserting data into first data structure202A, the first portion of the memory may be checked based on a capacity. When the first portion of the memory may be determined to be full, a second portion of the memory, such as different from the first portion of the memory may need to be allocated when the vector grows.

Data in first data structure202A or the first portion of the memory may be duplicated and transferred to first data structure202B or the second portion of the memory. Subsequently, new data can be inserted to first data structure202B or the second portion of the memory. For example, the vector or list with four elements in first data structure202A may be duplicated and transferred to first data structure202B or the second portion of the memory. Subsequently, a fifth elements can be inserted to an unused space of the second portion of the memory. The first portion of the memory may be freed or data in the first portion of the memory may be deleted.

If there may be parallel transactions or threads accessing the data meanwhile, the first portion of the memory may be not freed immediately. Instead the first portion of the memory can be attached to a garbage collection system that ensures that the first portion of the memory is freed far enough in the future so that no parallel transaction or thread might still operate on the data. Garbage collection can be described as automatic memory management, in which a computer-implemented memory manager (also referred to as a garbage collector), such as the clean-up manager214, reclaims memory occupied by data that is no longer in use by a system, such as the database system201.

In some examples, another transaction or thread (e.g., a read transaction or a thread to read) may be executing in parallel to the write transaction or the thread to write, and may require access to the data in first data structure202A or the first portion of the memory. Consequently, the clean-up manager cannot delete the data in first data structure202A or the first portion of the memory upon completion of the write transaction, and must wait until a future point in time (e.g., when any and all parallel transactions needing access to the data have completed).

In some examples, when a thread or transaction modifies data, it needs to obtain a lock that blocks other threads or transactions from modifying the same data structure. Usually, such write operations are quick. Readers are not required to be blocked at any time as the sequence of the modifying operations are done in a way that always allows reading. In order to allow reading at all times, the data structure needs to prepare the second piece of memory (here202B) entirely, and then atomically switch from202A to202B. This way, readers will either access202A or202B and always see consistent data within202A or202B. Of course parallel readers that access202A will not see the latest change. From a transactional point of view, this is legit as new data may only become visible to other transactions after data gets committed. If a thread reads the newly written memory202B, it will see the new data. Transactional visibility control needs to ensure that the entry is filtered and not included to the result set of queries etc.

As will be described with reference toFIG.3A, a clean-up entry may be logged in the transaction manager, and remain pending until a subsequent point in time. In some implementations, the clean-up entry is assigned a time that is based on a commitTS of a parallel transaction that is committed, in particular, the last parallel transaction. The time is compared to the most recently reported minReadTS. If the time is less than the most recently reported minReadTS, the clean-up entry is executed (e.g., by the memory manager). If the time is not less than the most recently reported minReadTS, the clean-up entry is attached to a next subsequent transaction. When a subsequent transaction that the clean-up entry is attached to commits, the time is again compared to the then most recently reported minReadTS, and the process continues until the clean-up entry is able to be executed.

As will be described with reference toFIG.3B, the clean-up of a clean-up entry can be triggered is when there is no other thread with readTS equal to the time assigned to the clean-up entry. In order to execute a clean-up entry, the time assigned to the clean-up entry can be compared with readTS of other threads.

FIG.2Cillustrates a block diagram of two example data structures, according to some embodiments. The example data structures are provided for the purpose of illustration only and does not limit the disclosed embodiments.FIG.2Cmay be described with regard to elements ofFIGS.1and2A.

As shown inFIG.2C, first data structure202includes a first data structure202A and a first data structure202B. Second data structure208includes a second data structure208A and a second data structure208B. First data structure202A includes a first vector or list with four elements. Second data structure208A includes a second vector or list with two elements.

In some examples, the second data structure208can be associated with the first data structure202based on contextual information. For example, the first data structure202A can include customer information, such as names of customers, in the database system201. The second data structure208A can include customer information, such as locations corresponding to the customers associated with the first data structure202A, in the database system201. The contextual information can indicate an order for performing a first read operation on the first data structure202and a second read operation on the second data structure208. In some examples, the contextual information can indicate an order for performing a first read operation on the first data structure202prior to a second read operation on the second data structure208. For example, the contextual information can indicate an order for performing the first read operation to read a name of a customer in the first data structure202prior to the second read operation to read a corresponding location of the customer in the second data structure208.

As described above, when inserting data into the first data structure202A in a first write transaction or a first thread to write, a size of the first vector can increase with insertion of elements. For example, first data structure202A can grow in size and be modified to first data structure202B. When inserting data into the first data structure202A, the first portion of the memory may be checked based on a capacity. When the first portion of the memory may be determined to be full, a second portion of the memory, such as different from the first portion of the memory may need to be allocated when the first vector grows. The first portion of the memory may be not freed immediately. Instead the first portion of the memory can be attached to a garbage collection system that ensures that the first portion of the memory is freed far enough in the future so that no parallel transaction or thread might still operate on the data. As shown inFIG.2C, when inserting “Martha” into the first data structure202A, the first data structure202A can grow in size and be modified to first data structure202B.

Similarly, when inserting data into the second data structure208A in a second write transaction or a second thread to write, a size of the second vector can increase with insertion of elements. For example, the second data structure208A can grow in size and be modified to the second data structure208B. When inserting data into the second data structure208A, the second portion of the memory may be checked based on a capacity. When the second portion of the memory may be determined to be full, a fourth portion of the memory, such as different from the second portion of the memory may need to be allocated when the second vector grows. The second portion of the memory may be not freed immediately. Instead the second portion of the memory can be attached to a garbage collection system that ensures that the second portion of the memory is freed far enough in the future so that no parallel transaction or thread might still operate on the data. As shown inFIG.2C, when inserting “Munich” into the second data structure208A, the second data structure208A can grow in size and be modified to second data structure208B.

In some examples, subsequent to receiving a request to insert “Martha” into the first data structure202A, whether the inserting “Munich” into the second data structure208A is to be executed prior to inserting “Martha” into the first data structure202A can be determined, based on the contextual information. For example, “Munich” may be associated with a location of “Martha”. The inserting “Munich” into the second data structure208A can be determined to be executed prior to inserting “Martha” into the first data structure202A. As described above, the contextual information can indicate an order for performing the first read operation to read a name of a customer in the first data structure202A prior to the second read operation to read a corresponding location of the customer in the second data structure208A. In some examples, an order of the inserting “Munich” into the second data structure208A and the inserting “Martha” into the first data structure202A can be determined to be in reverse of the order for performing the first read operation to read a name of a customer (e.g., “Martha”) in the first data structure202A prior to the second read operation to read a corresponding location of the customer (“Munich”) in the second data structure208A. In another example, header information of an order is read before line item information is read. In this case, line item information needs to get written first, and then the header information. This way it is guaranteed that no parallel threads reads a header for which no line items exist yet.

Based on the determination to the inserting “Munich” into second data structure208A is to be executed prior to inserting “Martha” into first data structure202A, “Munich” can be inserted into the second data structure208A. The second data structure208A can grow in size and be modified to the second data structure208B. Subsequently, “Martha” can be inserted into the first data structure202A. The first data structure202A can grow in size and be modified to the first data structure202B.

In some examples, although the first data structure202A,202B and/or the second data structure208A,208B are depicted and described as vectors, the first data structure202A,202B and/or the second data structure208A,208B can include one or more hash maps.

FIG.3Adepicts an example transaction timeline300in accordance with implementations of the present disclosure. The example transaction timeline300is provided for the purpose of illustration only and does not limit the disclosed embodiments.FIG.3Amay be described with regard to elements ofFIGS.1and2A-2C.

A database transaction can be a sequence of Structured query language (SQL) statements that the database system treats as a unit. A transaction can bring the database from one consistent state to another. If a transaction is interrupted, then the database system returns the database to the state it was in before the transaction began.

The example transaction timeline300includes a first transaction (tx1), a second transaction (tx2), a third transaction (tx3), a fourth transaction (tx4), and a fifth transaction (tx5). In the depicted example, the third transaction begins and ends while the first transaction and the second transaction are being performed (e.g., before either the first transaction or the second transaction are committed). The fourth transaction begins after the third transaction is committed, and ends after both the first transaction and the second transaction are committed. The fifth transaction begins after the fourth transaction is committed.

In the example ofFIG.3A, the vertical lines with numerical markers (e.g., 10, 20, 65, 160) indicate instances where the transaction manager206has been informed. In some examples, the respective numerical values are the minReadTS values reported by the transaction manager206.

For purposes of illustration, the first transaction can be provided as a data insertion, which is assigned a readTS equal to 20. Consequently, the insertion can be stored to memory (e.g., in a slice memory block). The second transaction can be provided as a data selection (e.g., selecting all available data). Consequently, the selection may read all data that was committed before or with commitID=20 as this is the readTS for that transaction. It cannot yet read the data that is being inserted by the parallel transaction (the first transaction).

The third transaction can be provided as a data insertion, which is assigned a readTS equal to 30. Consequently, the data insertion can be stored to memory. The third transaction is committed, and is assigned a commitTS equal to 60. For example, the third transaction can include a data insertion to the first data structure202A. As described above, For example, the first data structure202A can grow in size and be modified to the first data structure202B. The first portion of the memory may need to be freed or data in the first portion of the memory may need to be deleted. The first portion of the memory can be attached to a garbage collection system that ensures that the first portion of the memory is freed far enough in the future so that no parallel transaction might still operate on the data.

Thus, a clean-up entry302can be entered to the transaction manager206, but does not yet have an indication as to when the clean-up entry302is to be performed by the clean-up manager214. In accordance with implementations of the present disclosure, and as described in further detail herein, the clean-up entry302can remain pending without a time indicator, irrespective of any ongoing or parallel transactions. The reason is that a point in time which is sufficiently far in the future when the clean-up entry302may be executed is unknown, due to the possible existence of unaware transactions. As described in further detail herein, implementations of the present disclosure enable such a point in time to be determined by taking another transaction that starts in the future (per transaction, their readTS are always known) and using its commitTS instead of the own commitTS.

Continuing with the example ofFIG.3A, the fourth transaction begins and is assigned a readTS equal to 65. The clean-up entry302is attached to the fourth transaction, as it is a newly started transaction. In accordance with the present disclosure, the fourth transaction is used to eventually determine a commitTS that is sufficiently far in the future, as mentioned as a pre-requisite before. In the example ofFIG.3A, at some point after the fourth transaction begins, the current minReadTS is equal to 20. This means that there is at least one non-committed transaction in the system having a readTS equal to 20.

Continuing with the example ofFIG.3A, the first transaction is committed and is assigned a commitTS equal to 100, and the second transaction is committed, and is assigned a commitTS equal to 120. Accordingly, the third transaction occurred and was committed, while the first transaction and the second transaction were executed in parallel. However, the clean-up entry302corresponding to the third transaction still remains pending, as the fourth transaction has not yet committed. Continuing with the example ofFIG.3A, at some point after the fourth transaction begins, the then-current minReadTS is equal to 65. This means that there is at least one non-committed transaction in the system having a readTS equal to 65. Thereafter, fourth transaction is committed and is assigned a commitTS equal to 150.

The clean-up entry302is assigned a time equal to the commitTS of the fourth transaction. This is independent from any other transactions running in parallel in the system. Even if the first or second transactions were still running, commitTS could be used as a time indicator. This is because clean-up is only executed based on the provided minReadTS, and the minReadTS would not be increased by the transaction manager206, if there were still transactions running. In the example ofFIG.3A, the clean-up entry302is assigned the time150(i.e., the commitTS of the fourth transaction), and is delegated to the clean-up manager214. The clean-up entry302, however, is not performed until the minReadTS reported to the transaction manager206exceeds the time assigned to the clean-up entry, and a next subsequent transaction is committed.

In the example ofFIG.3A, the fifth transaction is the next subsequent transaction. When a transaction starts, it checks the clean-up manager214for pending clean-up entries. If any exist—in this example clean-up entry302does exist—it is attached to the transaction. If, however, the next subsequent transaction is never committed, the clean-up entry is moved back to await attachment to another next subsequent transaction. In some examples, a transaction never commits, if the transaction is aborted. For example, if the fifth transaction is aborted, the clean-up entry302is moved back, and is attached to the next subsequent transaction (e.g., a sixth transaction, not depicted). The example ofFIG.3A, however, depicts a scenario, in which the fifth transaction is committed (e.g., is not aborted).

Continuing with the example ofFIG.3A, at some point after the fifth transaction begins, the then-current minReadTS is equal to 160. This means that there is at least one non-committed transaction in the system having a readTS equal to 160.

The fifth transaction is committed and is assigned a commitTS equal to 180. Because the clean-up entry302is attached to the fifth transaction, committal of the fifth transaction triggers a check between the time assigned to the clean-up entry302(e.g.,150), and the last minReadTS reported to the transaction manager206(e.g.,160). If the time assigned to the clean-up entry302is less than the last minReadTS reported to the transaction manager206, the clean-up entry302is executed by the clean-up manager214to remove the corresponding data from the first portion of the memory or to free-up the first portion of the memory. If the time assigned to the clean-up entry302is not less than the last minReadTS reported to the transaction manager206, the clean-up entry302is moved back, and is attached to the next subsequent transaction. In the example ofFIG.3, the time is less than the last-reported minReadTS, and the clean-up entry302is executed.

In some implementations, in order to execute a clean-up entry, the clean-up entry has to be attached to a transaction, and the only point in time when the clean-up of a clean-up entry is triggered is when that transaction commits. The pre-requisite is that the time of the clean-up entry is lower than the then-current minReadTS in the system. If this pre-requisite is not given or the transaction never commits, the clean-up entry is moved back to the clean-up manager where it awaits attachment to a subsequent transaction. In this manner, the clean-up does not occur at the earliest point in time when there are no transactions anymore that may see the data. In fact, the clean-up may be delayed significantly based on the workload in the system. As the amounts of data that are to be freed per clean-up entry are usually small, this delay is deemed acceptable, and normal for a garbage-collection system.

FIG.3Bdepicts an example timeline310in accordance with implementations of the present disclosure. The example timeline310is provided for the purpose of illustration only and does not limit the disclosed embodiments. It describes a cleanup mechanism for systems without a transaction manager.FIG.3Bmay be described with regard to elements ofFIGS.1and2A.

The example timeline310includes a first thread (t1), a second thread (t2), a third thread (t3), a fourth thread (t4), and a fifth thread (5). In the depicted example, the third thread begins and ends while the first thread and the second thread are being executed (e.g., before either the first thread or the second thread are executed). The fourth thread begins after the third thread is committed, and ends after both the first thread and the second thread are committed. The fifth thread begins after the fourth thread is committed.

In some examples, the threads in example timeline310may not be transaction based. A linked list of running threads may be maintained based on the beginning and the completion of the each thread. In some examples, a non-blocking linked list is an example of non-blocking data structures designed to implement a linked list in shared memory using synchronization primitives.

In the example ofFIG.3B, the vertical lines with numerical markers (e.g., 0, 1, 2, 3, 4, 5) indicate a time stamp (TS). In some examples, a read timestamp (readTS) can be assigned when each thread starts. The vertical lines with numerical markers (e.g., 0, 0, 0, 1, 4, 5) indicate the corresponding minReadTS values. A minimum readTS (minReadTS) can be the lowest readTS of all running threads (parallel threads) in the system.

For purposes of illustration, the first thread can be provided as a data insertion, which is assigned a readTS equal to 0. Consequently, the insertion can be stored to memory (e.g., in a slice memory block). The second thread can be provided as a data selection (e.g., selecting all available data). Consequently, the selection may read all data that was committed before readTS for that thread. It cannot yet read the data that is being inserted by the parallel thread (the first thread).

The third thread can be provided as a data insertion, which is assigned a readTS equal to 0. Consequently, the data insertion can be stored to memory. The third thread is executed, and completed at TS=1. For example, the third thread can include a data insertion to write data to the first data structure202A. As described above, the first data structure202A can grow in size and be modified to the first data structure202B. The first portion of the memory may need to be freed or data in the first portion of the memory may need to be deleted. The first portion of the memory can be attached to a garbage collection system that ensures that the first portion of the memory is freed far enough in the future so that no parallel thread might still operate on the data.

Thus, a clean-up entry302can be entered to the clean-up manager214, but does not yet have an indication as to when the clean-up entry302is to be performed by the clean-up manager214. In accordance with implementations of the present disclosure, and as described in further detail herein, the clean-up entry302remains pending without a time indicator, irrespective of any ongoing or parallel threads. The reason is that a point in time which is sufficiently far in the future when the clean-up entry302may be executed is unknown, due to the possible existence of unaware threads. As described in further detail herein, implementations of the present disclosure enable such a point in time to be determined by taking another thread that starts in the future. The clean-up entry302is assigned a time equal to the current minReadTS+1, such as equal to 1 inFIG.3B.

Continuing with the example ofFIG.3Bthe fourth thread begins and is assigned a readTS equal to 1. Time of the clean-up entry302is compared with the readTS of the first thread, second thread and fourth thread. The clean-up entry302, however, is not performed until there is no other thread with readTS equal to the time assigned to the clean-up entry302. The fourth thread is executed, and completed at TS=4. The clean-up entry302, however, is performed upon the completion of the execution of the fourth thread, since there is no other thread with readTS equal to the time assigned to the clean-up entry302. The clean-up entry302is executed by the clean-up manager214to remove the corresponding data from the first portion of the memory or to free-up the first portion of the memory. In the example ofFIG.3B, the fifth transaction is the next subsequent transaction and is assigned a readTS equal to 4.

In some implementations, in order to execute a clean-up entry, the time assigned to the clean-up entry can be compared with readTS of other threads. The clean-up of a clean-up entry can be triggered is when there is no other threads with readTS equal to the time assigned to the clean-up entry302.

FIG.4illustrates an example method for providing lock-free read access to data structures using garbage collection, according to some embodiments. As a convenience and not a limitation,FIG.4may be described with regard to elements ofFIGS.1,2A-2C and3A-3B. Method400may represent the operation of a computing system (e.g., the database system201ofFIG.2A) for providing lock-free read access to data structures using garbage collection. But method400is not limited to the specific aspects depicted in those figures and other systems may be used to perform the method as will be understood by those skilled in the art. It is to be appreciated that not all operations may be needed, and the operations may not be performed in the same order as shown inFIG.4.

In step402, the database system201allocates a first portion of a memory corresponding to a first data structure of one or more data structures (e.g., the one or more data structures in the database system201). The first data structure (e.g., the first data structure202A) can comprise a size. The memory can include a memory associated with the server system104. As described above, the first data structure202A can use main memory for data storage, as described with reference toFIG.1.

In step404, the database system201performs a first operation associated with the first data structure. In some examples, the first operation can include a transaction or a thread.

Particularly, in step406, the database system201inserts first data to the first data structure. In step408, the database system201stores the first data in the first portion of the memory. In step410, the database system201receives a first request to insert second data to the first data structure. In step412, in response to the receiving the first request, the database system201determines whether an increase of the size is to be executed. As described above, when inserting data into first data structure202A (e.g., a vector), the first portion of the memory may be checked based on a capacity. When the first portion of the memory may be determined to be full, a second portion of the memory, such as different from the first portion of the memory may need to be allocated when the vector grows.

If no increase of the size to be executed is determined, the method400goes to415. In step415, the database system201inserts the second data to the first data structure.

If an increase of the size to be executed, the method400goes to414. In step414, the database system201inserts the second data to a modified first data structure.

Particularly, in step416, the database system201executes the increase of the size of the first data structure to generate the modified first data structure. As described above, first data structure202A can grow in size and be modified to first data structure202B.

In step418, the database system201allocates a second portion of the memory corresponding to the modified first data structure. The second portion the memory can be different from the first portion of the memory.

In step420, the database system201duplicates the first data from the first portion of the memory to the second portion of the memory.

In step422, the database system201stores the second data in the second portion of the memory.

In step424, the database system201executes garbage collection to free-up the first portion of the memory based on at least one parallel operation associated with the first data structure. As described above inFIG.2A, the database system201can include a transaction manager and a clean-up manager. In some examples, the database system201can determine a delete operation associated with the first portion of the memory. As described above inFIG.3A, in response to the delete operation, the database system201can insert a clean-up entry in the transaction manager. The transaction manager can delegate the clean-up entry to the clean-up manager. In some examples, the transaction manager can attach the clean-up entry to a subsequent transaction in order to determine and to assign a time to the clean-up entry that is used to subsequently trigger garbage collection. The time assigned to the clean-up entry can be associated with the at least one parallel operation. In some examples, the database system201can compare the time to a most-recent minimum read timestamp. The minimum read timestamps can be associated with start times of a plurality of transactions. The pendency of the clean-up entry can be maintained until the at least one parallel transaction is executed. In some examples, the database system201can determine whether the time is less than the most-recent minimum read timestamp. In some examples, the database system201, in response to determining whether the time is less than the most-recent minimum read timestamp, can generate a trigger to execute the clean-up entry to free-up the first portion of the memory.

In some examples, the transaction manager can attach the clean-up entry to a next subsequent transaction in response to determining that the time is not less than the most-recent minimum read timestamp.

In some examples, the most-recent minimum read timestamp can be a lowest read timestamp of all executing transactions in the database system.

In some examples, the time assigned to the clean-up entry can be equal to a commit timestamp of a last-committed parallel transaction.

Alternately or in addition, as described above inFIG.3B, the first operation may not be transaction based. As described above, in order to execute a clean-up entry, the time assigned to the clean-up entry can be compared with readTS of other threads. The clean-up of a clean-up entry can be triggered is when there is no other threads with readTS equal to the time assigned to the clean-up entry.

In some examples, as described with reference toFIG.2C, the database system201can perform a second operation associated with a second data structure (e.g., second data structure208A). The second data structure can be associated with the first data structure based on contextual information. In some examples, the database system201can receive a second request to insert third data to the second data structure. In some examples, the database system201can determine, based on the contextual information, whether the inserting the second data to the first data structure is to be executed subsequent to inserting the third data to the second data structure. In some examples, the database system201, based on the determination that the inserting the second data to the first data structure is to be executed subsequent to inserting the third data to the second data structure, inserting the third data to the second data structure prior to the inserting the second data to the first data structure, thereby providing the lock-free read access to the first data structure or the second data structure.

Various embodiments may be implemented, for example, using one or more well-known computer systems, such as computer system500shown inFIG.5. For example, database system201may be implemented using combinations or sub-combinations of computer system500. Also or alternatively, client device102, server system104may be implemented using combinations or sub-combinations of computer system500. Also or alternatively, one or more computer systems500may be used, for example, to implement any of the embodiments discussed herein, as well as combinations and sub-combinations thereof.

Computer system500may include one or more processors (also called central processing units, or CPUs), such as a processor504. Processor504may be connected to a communication infrastructure or bus506.

Computer system500may also include user input/output device(s)503, such as monitors, keyboards, pointing devices, etc., which may communicate with communication infrastructure506through user input/output interface(s)502.

One or more of processors504may be a graphics processing unit (GPU). In an embodiment, a GPU may be a processor that is a specialized electronic circuit designed to process mathematically intensive applications. The GPU may have a parallel structure that is efficient for parallel processing of large blocks of data, such as mathematically intensive data common to computer graphics applications, images, videos, etc.

Computer system500may also include a main or primary memory508, such as random access memory (RAM). Main memory508may include one or more levels of cache. Main memory508may have stored therein control logic (i.e., computer software) and/or data.

Computer system500may also include one or more secondary storage devices or memory510. Secondary memory510may include, for example, a hard disk drive512and/or a removable storage device or drive514. Removable storage drive514may be a floppy disk drive, a magnetic tape drive, a compact disk drive, an optical storage device, tape backup device, and/or any other storage device/drive.

Removable storage drive514may interact with a removable storage unit518. Removable storage unit518may include a computer usable or readable storage device having stored thereon computer software (control logic) and/or data. Removable storage unit518may be a floppy disk, magnetic tape, compact disk, DVD, optical storage disk, and/any other computer data storage device. Removable storage drive514may read from and/or write to removable storage unit518.

Secondary memory510may include other means, devices, components, instrumentalities or other approaches for allowing computer programs and/or other instructions and/or data to be accessed by computer system500. Such means, devices, components, instrumentalities or other approaches may include, for example, a removable storage unit522and an interface520. Examples of the removable storage unit522and the interface520may include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an EPROM or PROM) and associated socket, a memory stick and USB or other port, a memory card and associated memory card slot, and/or any other removable storage unit and associated interface.

Computer system500may further include a communication or network interface524. Communication interface524may enable computer system500to communicate and interact with any combination of external devices, external networks, external entities, etc. (individually and collectively referenced by reference number528). For example, communication interface524may allow computer system500to communicate with external or remote devices528over communications path526, which may be wired and/or wireless (or a combination thereof), and which may include any combination of LANs, WANs, the Internet, etc. Control logic and/or data may be transmitted to and from computer system500via communication path526.

Computer system500may also be any of a personal digital assistant (PDA), desktop workstation, laptop or notebook computer, netbook, tablet, smart phone, smart watch or other wearable, appliance, part of the Internet-of-Things, and/or embedded system, to name a few non-limiting examples, or any combination thereof.

Computer system500may be a client or server, accessing or hosting any applications and/or data through any delivery paradigm, including but not limited to remote or distributed cloud computing solutions; local or on-premises software (“on-premise” cloud-based solutions); “as a service” models (e.g., content as a service (CaaS), digital content as a service (DCaaS), software as a service (SaaS), managed software as a service (MSaaS), platform as a service (PaaS), desktop as a service (DaaS), framework as a service (FaaS), backend as a service (BaaS), mobile backend as a service (MBaaS), infrastructure as a service (IaaS), etc.); and/or a hybrid model including any combination of the foregoing examples or other services or delivery paradigms.

Any applicable data structures, file formats, and schemas in computer system500may be derived from standards including but not limited to JavaScript Object Notation (JSON), Extensible Markup Language (XML), Yet Another Markup Language (YAML), Extensible Hypertext Markup Language (XHTML), Wireless Markup Language (WML), MessagePack, XML User Interface Language (XUL), or any other functionally similar representations alone or in combination. Alternatively, proprietary data structures, formats or schemas may be used, either exclusively or in combination with known or open standards.

In some embodiments, a tangible, non-transitory apparatus or article of manufacture comprising a tangible, non-transitory computer useable or readable medium having control logic (software) stored thereon may also be referred to herein as a computer program product or program storage device. This includes, but is not limited to, computer system500, main memory508, secondary memory510, and removable storage units518and522, as well as tangible articles of manufacture embodying any combination of the foregoing. Such control logic, when executed by one or more data processing devices (such as computer system500or processor(s)504), may cause such data processing devices to operate as described herein.

Based on the teachings contained in this disclosure, it will be apparent to persons skilled in the relevant art(s) how to make and use embodiments of this disclosure using data processing devices, computer systems and/or computer architectures other than that shown inFIG.5. In particular, embodiments can operate with software, hardware, and/or operating system implementations other than those described herein.

It is to be appreciated that the Detailed Description section, and not any other section, is intended to be used to interpret the claims. Other sections can set forth one or more but not all exemplary embodiments as contemplated by the inventor(s), and thus, are not intended to limit this disclosure or the appended claims in any way.

While this disclosure describes exemplary embodiments for exemplary fields and applications, it should be understood that the disclosure is not limited thereto. Other embodiments and modifications thereto are possible, and are within the scope and spirit of this disclosure. For example, and without limiting the generality of this paragraph, embodiments are not limited to the software, hardware, firmware, and/or entities illustrated in the figures and/or described herein. Further, embodiments (whether or not explicitly described herein) have significant utility to fields and applications beyond the examples described herein.

Embodiments have been described herein with the aid of functional building blocks illustrating the implementation of specified functions and relationships thereof. The boundaries of these functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternate boundaries can be defined as long as the specified functions and relationships (or equivalents thereof) are appropriately performed. Also, alternative embodiments can perform functional blocks, steps, operations, methods, etc. using orderings different than those described herein.

References herein to “one embodiment,” “an embodiment,” “an example embodiment,” or similar phrases, indicate that the embodiment described can include a particular feature, structure, or characteristic, but every embodiment can not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it would be within the knowledge of persons skilled in the relevant art(s) to incorporate such feature, structure, or characteristic into other embodiments whether or not explicitly mentioned or described herein. Additionally, some embodiments can be described using the expression “coupled” and “connected” along with their derivatives. These terms are not necessarily intended as synonyms for each other. For example, some embodiments can be described using the terms “connected” and/or “coupled” to indicate that two or more elements are in direct physical or electrical contact with each other. The term “coupled,” however, can also mean that two or more elements are not in direct contact with each other, but yet still co-operate or interact with each other.

The breadth and scope of this disclosure should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.