Compressed representation of a transaction token

Patent metadata

Field	Value
Publication number	US-9805074-B2
Application number	US-201313760850-A
Country	US
Kind code	B2
Filing date	Feb 6, 2013
Priority date	Nov 28, 2012
Publication date	Oct 31, 2017
Grant date	Oct 31, 2017

Abstract

Methods, systems and computer-readable storage mediums encoded with computer programs executed by one or more processors for providing a compressed representation of a transaction token are disclosed. In an embodiment, a transaction token maintains statues of transaction to a database in a first data structure and a second data structure. The first data structure includes a plurality of identifiers respectively corresponding to the transactions to the database and a corresponding status of each identifier indicating whether a given transaction is open or closed, wherein the plurality of identifiers is maintained below a threshold number of identifiers. The second data structure includes a plurality of identifiers of transactions to the database beyond the threshold and whose status is open.

First claim

What is claimed is:

1. A method, comprising:
determining a transaction token that maintains statuses of transactions to a database in both a first data structure and a second data structure, wherein the first data structure and second data structure are organized differently and include different transaction identifiers corresponding to the transactions;
receiving an update to a status of a transaction to the database corresponding to a particular transaction identifier;
determining that the first data structure includes a plurality of transaction identifiers respectively corresponding to transactions of the database and stores a corresponding status of each transaction identifier indicating whether a given transaction is open or closed, wherein the plurality of transaction identifiers are maintained below a threshold number of identifiers, wherein the threshold number of identifiers indicates a number of recent transactions to the database;
determining that a plurality of transaction identifiers correspond to open transactions to the database beyond the threshold number of identifiers that were initiated before processing of the recent transactions based on their inclusion in the second data structure that only includes open transactions;
determining that the particular transaction identifier corresponding to the updated status does not exist in the first data structure or the second data structure of the transaction token;
adding the particular transaction identifier to the first data structure;
if the threshold number of identifiers of the first data structure, including the particular transaction identifier, is exceeded, moving one or more open transactions from the first data structure to the second data structure, such that the transactions of the first data structure is below the threshold number of identifiers;
receiving a request to perform a transaction on the database subsequent to receiving the updated status; and
providing, responsive to the request, an updated transaction token to the database including both the first data structure and the second data structure.

2. The method of claim 1 , wherein the database is a multi-version concurrency control (MVCC) database configured to maintain a plurality of data versions.

3. The method of claim 1 , wherein the first data structure is a BitVector data structure, and wherein the second data structure is one of a list or an array.

4. The method of claim 1 , wherein the first data structure includes an indication of a highest numbered identifier that has a closed status and a lowest numbered identifier that has an open status, and
wherein any numbered identifiers beyond the threshold number of identifiers that have an open status are stored in the second data structure.

5. The method of claim 4 , wherein the threshold number of identifiers indicates a maximum number of identifiers stored in the first data structure, and wherein each of the transactions is either a write transaction or a read transaction.

6. The method of claim 4 , wherein one or more identifiers greater than the highest numbered identifier that has a closed status have open statuses, and one or more identifiers lower than the lowest numbered identifier have closed statuses.

7. The method of claim 1 , wherein the providing comprises:
providing a local copy of the transaction token for use with performing the requested transaction.

8. The method of claim 1 , wherein the threshold number of identifiers indicates a timestamp indicator of which transactions are stored in the first data structure or the second data structure.

9. The method of claim 1 , wherein the receiving an updated status comprises:
receiving a request to access data of the database;
determining, based on the transaction token, which transactions are open and closed in the database; and
providing a local transaction token responsive to receiving the request, wherein the local transaction token is a copy of the transaction token,
wherein if the request is a write request, assigning the write request a new transaction identifier.

10. The method of claim 1 , wherein the updating comprises:
updating the first data structure with a new entry corresponding to the updated status;
determining that the first data structure has exceeded the threshold number of identifiers;
moving a smallest transaction identifier with an open status from the first data structure to the second data structure, wherein a smaller transaction identifier corresponds to an earlier date of a transaction relative to a larger transaction identifier, and wherein the smallest transaction identifier with the open status when stored in the second data structure is not stored with its status information.

11. The method of claim 1 wherein the transaction identifiers are assigned by a transaction manager that maintains the first data structure and the second data structure of the transaction token.

12. The method of claim 1 further comprising:
determining that a particular transaction identifier corresponds to a closed transaction based on the particular transaction identifier not existing in either the first data structure or the second data structure.

13. The method of claim 1 , wherein the plurality of transaction identifiers of the second data structure correspond to open transactions moved from the first data structure, wherein the second data structure does not include closed transactions.

14. The method of claim 1 , wherein the moving comprises:
removing status information from the one or more open transactions moved from the first data structure to the second data structure, wherein an open status for the moved transactions may be determined based upon their storage in the second data structure.

15. The method of claim 1 , further comprising:
changing the status of the particular transaction identifier in the first data structure from open to closed.

16. The method of claim 1 , further comprising:
receiving an update to a status of a second transaction corresponding to a second transaction identifier;
determining that the second transaction identifier is in the second data structure; and
removing the second transaction identifier from the second data structure.

17. A system, comprising:
a database operating on one or more processors, the database including multiple versions of data;
a global transaction token indicating which version of the data is accessed by a transaction, the global transaction token including both a first data structure and a second data structure, wherein the first data structure and second data structure are organized differently and include different transaction identifiers corresponding to the transactions;
and a transaction manager configured to:
receive an update to a status of a transaction to the database corresponding to a particular transaction identifier,
determine that the first data structure includes a plurality of transaction identifiers respectively corresponding to transactions of the database and stores a corresponding status of each transaction identifier indicating whether a given transaction is open or closed, wherein the plurality of transaction identifiers are maintained below a threshold number of identifiers, wherein the threshold number of identifiers indicates a number of recent transactions to the database,
determine that a plurality of transaction identifiers correspond to open transactions to the database beyond the threshold number of identifiers that were initiated before processing of the recent transactions based on their inclusion in

Assignees

• Lee Juchang
• Park Chang Gyoo
• Na Hyoungjun
• Kim Kyuhwan
• Sap Ag

Inventors

• Lee Juchang
• Park Chang Gyoo
• Na Hyoungjun
• Kim Kyuhwan

Classifications

• G06F17/30356

  Physics · mapped topic

• G06F17/30286

  Physics · mapped topic

• G06F17/30309 Primary

  Physics · mapped topic

• G06F16/2329 Primary

  using versioning · CPC title

• G06F16/20

  of structured data, e.g. relational data · CPC title