Patent ID: 12242463

While embodiments are described herein by way of example for several embodiments and illustrative drawings, those skilled in the art will recognize that embodiments are not limited to the embodiments or drawings described. It should be understood, that the drawings and detailed description thereto are not intended to limit embodiments to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description or the claims. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include,” “including,” and “includes” mean including, but not limited to.

It will also be understood that, although the terms first, second, etc. may be used herein to describe various elements, these elements should not be limited by these terms. These terms are only used to distinguish one element from another. For example, a first contact could be termed a second contact, and, similarly, a second contact could be termed a first contact, without departing from the scope of the present invention. The first contact and the second contact are both contacts, but they are not the same contact.

DETAILED DESCRIPTION OF EMBODIMENTS

Generally described, the present disclosure relates to embodiments of a transactional database system that implements transactions over data objects stored in a strongly consistent object storage system. In some embodiments, the database system may present the data as tables (e.g. tables accessible via Structured Query Language or SQL), and the data objects stored in the object storage system may be data files that correspond different portions of the tables (e.g. rows or columns of the tables). In some embodiments, the object storage system may organize the data objects in a hierarchical structure (e.g. a file directory structure). In some embodiments, the object storage system is a third-party system that is managed and executed independently from the transactional database system.

In some embodiments, when a transaction is initiated, the transactional database system makes a private copy of data objects that are used by the transaction in the object storage system. Reads and writes of the transaction will be performed on the private copy. When the transaction is to be committed, the transactional database system checks whether the committed state of the data objects has changed outside the transaction since the transaction began. If not, the database system updates metadata object(s) associated with the data objects to refer to the private copy as the currently committed state of the data objects. On the other hand, if the committed state of any data objects has changed during the transaction (e.g. modified by an intervening writer), the private copy is abandoned and the transaction is rolled back and/or retried.

Advantageously, by making a copy of data used by the transaction, the transactional database system reduces use of mutually exclusive locks on the data objects. For some types of object storage systems, such locking is not possible through their APIs. The described transactional database system only requires a small number of operations of the underlying data storage system (e.g. API calls to copy and update data objects), so that the transactional database system can be easily ported across different types of data storage systems. Additionally, in some embodiments, the described transactional model is implemented within the hierarchical storage structure of the data objects, so that the database system is able to enforce transactional isolation at any level of the database schema (e.g. one or more tables, one or more table rows, or one or more table columns). The transactional database system can be adapted for a wide variety of data storage models or database schemas.

As will be appreciated by those skilled in the art, the features of the disclosed transactional database system are designed to solve technical problems rooted in the computer field, and are not intended to capture any human mental and pen-and-paper processes, basic methods of organizing human activity, pure mathematical processes and formulas, and/or conventional business practices. These features and advantages of the transactional database system are described in further detail below, in connection with the figures.

FIG.1illustrates an embodiment of a transactional database system that implements data transactions over an object storage system, according to some embodiments.

As shown, the figure depicts a transactional database system100. The transactional database system100may be implemented on one or more computer systems to store and manage data for database clients. The transactional database system100implements a database interface110that allows clients to read and write data stored in the database system. In some embodiments, the database interface110may also be used by users to perform various administrative tasks, such as to change the data schema of a database or configure a data management process such as data backup or replication. In some embodiments, the database system100is a multi-tenant system that manages database instances on behalf of many different clients. In some embodiments, the database system110is a SQL database system that presents data in tables and allows users to query and update table data using SQL.

As shown, the database interface110of the database system may be used to receive client transactions105. A transaction may be received as an ad hoc client request, or in some embodiments, stored as a database object within the database and invoked on demand. A particular transaction may specify a series of data read and write operations on data items in the database, to be performed together as an atomic operation. For example, the updates in the transaction will be performed in an all-or-nothing fashion. Also, all operations of the transaction should occur at a single logical point in time, so that data used by the transaction does not change during the execution of the transaction. When a transaction completes successfully, all of its updates should be committed so that the changes are made visible to all clients of the database. At any time before the transaction commits, the transaction may be rolled back so that all updates performed by the transaction are discarded.

As shown, to execute a transaction, the database system100implements a transaction initiation step120and a transaction completion step130. During the transaction initiation step120, a data object determination operation122is performed to determine what data objects154in an underlying object storage system140will be accessed (e.g. read or written) by the transaction. The data objects that will be accessed by the transaction may be referred to as the scope of the transaction. The transaction scope may be determined by the database system based on the code of the transaction. In some embodiments, the client may explicitly specify the scope of a transaction in a “prepare transaction” request.

In some embodiments, the database system may allow clients to specify the granularity level for transaction scoping. For example, a user may specify that when a transaction reads or writes a data item, the transaction will be provided an isolated view (e.g. a private copy160) of the entire table that contains the data item. As another example, a transaction may be provided a copy of just a single shard or partition of the table that contains the item. The isolation or granularity level of transactions may be defined via configuration settings. In some embodiments, the granularity level of transactions may be defined at the schema level (e.g. for a particular tenant, database, or table). In some embodiments, the level of transactions may be defined for individual transactions, or even individual data access operations within a transaction.

Once the transaction scope of the transaction is determined, a data object copying operation124is performed to make a private copy126of all data objects in the transaction scope, in the object storage system140. For example, as shown, a copy160of data objects154aand154bis made for transaction T1. In this example, the copy160includes data objects164aand164b, which are initially copies of data objects154aand154b. As another example, a copy162may be made as part of the initiation of transaction T2, and includes data objects164dand164e, which are copies of existing data objects154dand154e. The copies160and162may be private to their respective transactions T1and T2, so they can only be read and written by their respective transactions.

In some embodiments, the object storage system140may be a system that is separately managed and executed from the transaction database system100. For example, the object storage system may be one or more file servers remote from the transactional database system100, or a cloud-based object storage service provided by a multi-tenant infrastructure provider service such as AWS or AZURE. The object storage system140may provide a programmatic interface such as an API to receive defined requests from the database system100, such as requests126to copy one or more data objects154aand154b.

As shown, in some embodiments, the data objects154a-ein the object storage system140may be stored in a hierarchical data structure150. The hierarchical data structure150may group data objects154a-ein various object groupings152a-d, possibly in a tree structure. In some embodiments, the hierarchical data structure150may be the directory tree structure of a file system, and each object grouping152a-dmay be a directory in the directory tree structure. The transactional database system100may organize data in a database in a layout scheme using the hierarchical structure. For example, in an embodiment, each client or tenant of the database system may be assigned a tenant directory. Under a tenant directory, each database (or schema) may have a separate database directory. Under a database directory, each table in the database may have a separate table directory. Under a table directory, each portion, shard, or partition of the table may have its own directory. In some embodiments, only the leaf level directory in the hierarchical data structure will store the actual data objects165a-e, which may be stored specially formatted data files. Accordingly, each data object154in the hierarchical data structure150may be uniquely addressable in the object storage system by a file path such as [Tenant]/[Database]/[Table]/[Shard]/[FileName]. In some embodiments, all private copies of a data object file are stored as individual files in the same directory as the data object file, using a file name that identifies the transaction.

As discussed, after a transaction is initiated120, all reads and writes of the transaction are performed on its private copy160of the data. Once the transaction is ready to commit its changes, the transaction completion step130is performed. As shown, the completion step130will first perform a conflict detection operation132to see if the committed state of data objects within the transaction scope (e.g. data objects154aand154bfor transaction T1) has changed outside the transaction while the transaction was executing. For example, such a change may occur if another transaction successfully committed a newer version of data object154aor154bduring the pendency of transaction T1. Depending on the embodiment, the conflict detection132may be made based on the contents of one or more metadata objects170maintained in the object storage system140or the native file metadata of the data objects (e.g. the file update timestamps and/or filenames).

If a conflict is detected (e.g. the committed state of some data object within transaction scope has changed), the transaction will be rolled back via a rollback operation134. The rollback operation134will abandon138the private copy160of the transaction so that the private copy cannot be included in the committed state of any of the data objects. In some embodiments, the rollback134may cause the associated private copy (e.g. copy160) to be immediately deleted. In other embodiments, the abandoned copy may be marked for later deletion.

On the other hand, if a conflict is not detected (e.g. the committed state of all data objects in the transaction scope did not change), a commit operation136is performed. The commit operation136causes the private copy (e.g. copy162) to be set139as the committed state for all data objects in the copy. In some embodiments, the setting139of the committed state of the data objects is performed by updating one or more metadata objects170in the object storage system140. The metadata object170may act as a pointer that points to a particular version of the data object (e.g. a particular data object file) as the latest committed state of the data object. In this example, the metadata object(s)170is updated so switch the pointer from data objects154dand154eto data objects164dand164e. The change of the pointer effectively results in a change in the committed state of the database. For example, all database access routines in the database system may understand the pointed-to version of the data object as the currently committed state of the data object. In some embodiments, the metadata objects may be implemented as metadata files in the same directory as associated data object files. In other embodiments, the database system may employ one or more global metadata files that implement pointers for many data objects in the object storage system. In some embodiments, an obsolete version of a data object (e.g. versions154dand156e) may be deleted immediately after the transaction completes. In other embodiments, the obsolete versions may be kept for later deletion or archival processes.

FIG.2illustrates an embodiment of the transactional database system that is implemented using data storage services provided by a multi-tenant infrastructure service provider network, according to some embodiments.

Multi-tenant infrastructure service provider network200may be a private or closed system or may be set up by an entity such as a company or a public sector organization to provide one or more computing infrastructure services (such as various types of cloud-based storage) accessible via the Internet and/or other networks to clients in their client networks270, in some embodiments. Service provider network200may be implemented in a single location or may include numerous data centers hosting various resource pools, such as collections of physical and/or virtualized computer servers, storage devices, networking equipment and the like, needed to implement and distribute the infrastructure and services offered by the provider network200. In some embodiments, provider network200may implement various computing infrastructure systems and/or resources230that are accessible via services, such as a virtual private cloud (VPC) service, one or more compute service(s), data storage service(s)210and220, data analytic service(s), machine learning service(s), as well as other types of auxiliary services.

In various embodiments, the components illustrated inFIG.2may be implemented directly within computer hardware, as instructions directly or indirectly executable by computer hardware (e.g., a microprocessor or computer system), or using a combination of these techniques. For example, the components ofFIG.2may be implemented by a system that includes a number of computing nodes (or simply, nodes), each of which may be similar to the computer system embodiment illustrated inFIG.8and described below. In various embodiments, the functionality of a given system or service component may be implemented by a particular node or may be distributed across several nodes. In some embodiments, a given node may implement the functionality of more than one service system component (e.g., more than one data store component).

The compute service(s) implemented by service provider network200offer instances, containers, and/or functions according to various configurations for client operations. A virtual compute instance may, for example, comprise one or more servers with a specified computational capacity (which may be specified by indicating the type and number of CPUs, the main memory size, and so on) and a specified software stack (e.g., a particular version of an operating system, which may in turn run on top of a hypervisor). A container may provide a virtual operating system or other operating environment for executing or implementing applications. A number of different types of computing devices may be used singly or in combination to implement the compute instances, containers, and/or functions of service provider network200in different embodiments, including general purpose or special purpose computer servers, storage devices, network devices and the like.

Compute instances, containers, and/or functions may operate or implement a variety of different services, such as application server instances, general purpose or special-purpose operating systems, services that support various interpreted or compiled programming languages such as Ruby, Perl, Python, C, C++ and the like, or high-performance computing services) suitable for performing client applications, without for example requiring the client(s) to access an instance. Applications (or other software operated/implemented by a compute instance and may be specified by client(s), such as custom and/or off-the-shelf software.

Compute instance configurations may also include compute instances, containers, and/or functions with a general or specific purpose, such as computational workloads for compute intensive applications (e.g., high-traffic web applications, ad serving, batch processing, video encoding, distributed analytics, high-energy physics, genome analysis, and computational fluid dynamics), graphics intensive workloads (e.g., game streaming, 3D application streaming, server-side graphics workloads, rendering, financial modeling, and engineering design), memory intensive workloads (e.g., high performance databases, distributed memory caches, in-memory analytics, genome assembly and analysis), and storage optimized workloads (e.g., data warehousing and cluster file systems). Size of compute instances, containers, and/or functions, such as a particular number of virtual CPU cores, memory, cache, storage, as well as any other performance characteristic. Configurations of compute instances, containers, and/or functions may also include their location, in a particular data center, availability zone, geographic location, etc. and (in the case of reserved compute instances, containers, and/or functions) reservation term length.

As shown, the service provider network200may implement one or more network-based data storage service(s)210and220. These types of data storage services may be used to implement the object storage system140ofFIG.1. For example, the object storage service210may provide storage for arbitrary data objects or files, which can be accessed via a key-value access interface. A hierarchy of stored data objects may be maintained using an appropriate naming convention of the objects. The object storage service210may be a strongly consistent data storage service where acknowledged writes are immediately and globally visible to all data readers. As shown, in some embodiments, object storage service210may implement a variety of data and resource management features such as data availability212(e.g. data mirroring and automatic disaster recovery), long-term data archival214(e.g. archival of successive committed states of data objects), and resource management (e.g. automatic scaling of storage and request handling resources). Another example of an object storage system140is the volume hosting service220. This type of service220provides a block-based volume for clients, which may be used by clients to store a file system222. The volumes may be attached or mounted to various compute nodes (e.g. virtual machine instances) over a network and accessed by the compute nodes as local disks. The volume hosting service220may implement a host of data and resource management features for hosted volume data, similar to the object storage service210.

Generally speaking, the clients270of the service provider network200may encompass any type of client configurable to submit network-based requests to service provider network200via network(s)260. For example, a given client device may include a suitable version of a web browser, or may include a plug-in module or other type of code module that may execute as an extension to or within an execution environment provided by a web browser. Alternatively, a client270may encompass an application (or user interface thereof), a media application, an office application or any other application that may make use of resources in in service provider network200to implement various features, systems, or applications. (e.g., to store and/or access the data to implement various applications. In some embodiments, such an application may include sufficient protocol support (e.g., for a suitable version of Hypertext Transfer Protocol (HTTP)) for generating and processing network-based services requests without necessarily implementing full browser support for all types of network-based data. That is, a client270may be an application that interacts directly with service provider network200.

As shown in this example, the client270may comprise components of the transactional database system100ofFIG.1, including the database interface110, a transaction management layer250, and a data access layer240. The data access layer240may include a variety of adapters that adapt or translate API calls form the transaction management layer250to API calls that are specific to the underlying object storage system. In this manner, the transactional database system100can be configured to operate over many different types of underlying object stores without significant changes to the transaction management layer250. In this example, object storage service adapter242is used to connect to the object storage service210, and volume hosting service adapter244is used to connect to the volume hosting service220.

As shown, the clients270can convey network-based services requests to and receive responses from service provider network200via one or more networks260. In various embodiments, network(s)260may encompass any suitable combination of networking hardware and protocols necessary to establish network-based-based communications between clients270and service provider network200. For example, network260may generally encompass the various telecommunications networks and service providers that collectively implement the Internet. Network(s)260may also include private networks such as local area networks (LANs) or wide area networks (WANs) as well as public or private wireless networks. For example, a given client270and service provider network200may be respectively provisioned within enterprises having their own internal networks. In such an embodiment, network260may include the hardware (e.g., modems, routers, switches, load balancers, proxy servers, etc.) and software (e.g., protocol stacks, accounting software, firewall/security software, etc.) necessary to establish a networking link between given client270and the Internet as well as between the Internet and service provider network200. It is noted that in some embodiments, clients270may communicate with service provider network200using a private network rather than the public Internet.

While some functionalities are generally described herein with reference to a particular implementation of the transactional database system, other components or a combination of components may additionally or alternatively implement such functionalities. Other variations of implementing the described functionality are known to those skilled in the art, and thus not described in more detail herein.

FIG.3illustrates different types of data objects that may be used by the transactional database system, according to some embodiments. The data objects310,330,340,360, and370illustrated in the figure are embodiments of data objects154discussed in connection withFIG.1.

As shown, data object310comprises two tables, table A312and table B314. Depending on the data layout of the database system, data object310may be a single data file or two data files in a common directory. By grouping multiple tables in the same data object310, the transactional database system will treat the two tables as a single unit in terms of transaction isolation. For example, the two tables will share a committed state, so that a commit to either of the two tables will update the common committed state. This type of data object310may be useful for tables that are always updated together, such a parent-child table pair. As discussed, this arrangement may be specified by configuration. In some embodiments, by default, a data object will correspond to only one table.

As shown, data objects330and340correspond to different rows322of a table C320. In some embodiments, the transactional database system may partition a table into multiple data files according to rows, where each data file is a row group, partition, or shard. The partitioning may be done based on partition key attribute(s) of the rows, depending on the table schema. As shown, data object330includes multiple rows322a-cof the table, which may reside in a common data file or separate data files. Data object340includes just a single row322e. Single row data objects may be useful in situations where the particular row is heavily accessed by many transactions.

As shown, data objects360and370correspond to different columns352of a table D350. In some embodiments, the transactional database system may support columnar databases where the table is partitioned by column. Individual columns may correspond to individual data file(s). As shown, in this example, data object360includes multiple columns352b-d, and data object includes just a single column370. Each of these data objects may be a single committable unit in the transactional database system100.

FIG.4illustrates an embodiment of the transactional database system that stores transactional metadata of data objects in individual file directories associated with the data objects, according to some embodiments.

As shown in this example, the data objects440a-eare stored as files in a file directory structure410implemented by the object storage system140. Two directories420aand420bare shown. In this example, each directory420corresponds to a single data object, and stores a current committed state440aand440cof the data object as a file. In this example, the metadata files430aand430b, which are embodiments of the metadata objects170ofFIG.1, are stored in the same directory as their associated data object files. As discussed, these metadata files430act as pointers to refer to the file in the directory that represents the current committed state of the data object (here files440aand44c).

As shown, in this example, when a transaction T1is initiated, copies440band440dof the current committed state of the data objects are created in each directory. As discussed, these copies440band440dmay be private to transaction T1and used for data reads and writes during execution of transaction T1.

As shown, in some embodiments, the creation of transaction copies440band440dmay be performed using an atomic copy operation450. The atomic copy operation450may cause all copies for transaction T1to be created in a single logical point in time, so that both copies440band440dwill reflect the same global commit point of the database. This strategy thus ensures that transactions on the database are globally serializable. To implement the atomic copy operation450, the database system may maintain a database-level file that indicates whether any atomic copy operation is currently executing. If so, any other atomic copy operations will be queued or suspended until the currently execution copy operation is completed. In some embodiments, if an atomic copy operation is hung or fails unexpectedly, the database system will simply fail that transaction and allow other waiting copy operations to proceed. In some embodiments, to save time during the atomic copy operation, the database system may proactively make copies of certain data object files for use by transactions, so that the atomic copy operation does not actually need to perform the time-consuming copy step. The database system will take steps to ensure the proactive copies are consistent with the committed state of the data objects.

As shown, in some embodiments, the updating of the metadata file430, which may be performed at both the initiation and completion of the transaction, is performed using an atomic update operation460. The atomic update operation460ensures that all relevant metadata files430are performed in a single logical point in time, without intervening changes to the committed state of the database. The atomic update operation460may be implemented in much the same way as the atomic copy operation450.

Finally, in some embodiments, the database system may implement an asynchronous garbage collection process470for remove any abandoned copies440eleft by failed transactions. As discussed, in some embodiments, the deletion of these copies440emay not be performed as part of the transaction rollback process. Rather, the copies can be deleted by a later process such as the asynchronous garbage collection process470. The garbage collection470may be performed as a periodic background process, or in some embodiments, during periods of low activity.

FIG.5illustrates an example metadata file (e.g. metadata file430) used to store transactional metadata about one or more data objects, according to some embodiments.

As shown, in this example, the metadata file430is stored in a human-readable text form. In some embodiments, the metadata file430may be formatted as a JSON data structure. In other embodiments, the metadata file430may be encoded in other data formats.

In some embodiments, metadata file430may be used to keep the history of transactions that have been committed on the data object. As seen in this example, each commit to the data object generates a commit record510,520, and530in the metadata file. Each commit record indicates the name of the data object file that represents the state of the data object after a commit, as well as the time of the commit. In this example, the last commit record530in the metadata file points to the current committed state of the object.

In some embodiments, individual commit records in the metadata file may also indicate any transactions that arose for the data object. For example, commit records510shows two competing transactions512and514that arose during the period for that committed version, including the private copy of the data object for each transaction, the start time of each transaction, the writer process associated with the transaction, and the result (e.g. committed or rolled back) of each transaction. As shown, committed state510was advanced to the next committed state520by the successful completion transaction512. Losing transaction514was retried on committed state520to advance the data object to the next committed state530.

The transaction data stored in the metadata file430may be used in a number of ways. As one example, this data may be displayed via a management interface to show which transactions are currently operating on which data objects in the database. As another example, the data may be used by transaction writers or the database system itself to take actions against potential conflicts among transactions, such as to proactively resolve a conflict. As yet another example, the historical data may be analyzed to identify historical conflict patterns and recommend measures to mitigate conflicts in the future. In some embodiments, the database system may implement a periodic archival process to archive obsolete versions of data objects in the object storage system, and the archival process may also archive the historical data in the metadata file.

FIG.6illustrates example types of functionalities that may be exposed by a management interface and a configuration interface of the transactional database system, according to some embodiments. The management interface610and configuration interface640shown in the figure may be programmatic interfaces (e.g. APIs) or user interactive interfaces (e.g. GUIs). In some embodiments, interfaces610and640may be implemented as web-based interfaces that are displayed by web browsers.

As shown, in some embodiments, the management interface610may be used (e.g. by a database system administrator) to view transactions612currently active in the database and kill614a running transaction in the database. In some embodiments, active transactions may be displayed with information such as the data objects that are part of the transaction scope and the running time of the transactions. In some embodiments, the displayed information may also indicate any potential conflicts among currently active transactions.

In some embodiments, the transactional database system may implement a conflict logging and analysis component630, which will analyze conflict history632in the database (e.g. history data recorded in metadata file430ofFIG.3) to determine any conflict patterns or hotspots. A conflict hotspot may identify a particular transaction or group of transactions that is frequently causing conflicts in the database. Another type of conflict hotspot may identify one or more data objects that frequently cause conflicts. These detected conflict hotspots may be viewed620by database system administrators via the management interface.

Additionally, in some embodiments, the conflict analysis component630may generate hotspot mitigation recommendations622to administrators based on the conflict history data632. For example, if two transactions are frequently observed to conflict with each other, the analysis component may recommend that one of the transactions be scheduled for a different time or broken up into smaller transactions to reduce its transaction scope. As another example, if a data object is frequently the cause of conflicts, the analysis component may recommend that the data object be partitioned. In some embodiments, the database system may automatically perform these actions on its own based on the conclusions of the analysis component.

As shown, the configuration interface640may be used to receive configuration input642to control the operations and transaction processing behavior of the transaction database system. The received configuration input642may be stored as configuration settings644in a configuration repository.

In some embodiments, the configuration settings may specify various aspects of how the system processes transactions. For example, in some embodiments, the database system may warn a database client when the system detects a competing transaction with the client's requested transaction. A competing transaction may be detected based on tracked transaction metadata (e.g. metadata file430ofFIG.5). The warning may be generated when a client first initiates a transaction, or when the competing transaction appears after initiation of the client transaction.

In some embodiments, the configuration settings may specify that if a transaction fails due to a rollback, it will automatically be retried for a certain number of times. In some embodiments, this retry behavior may be configured on a per-transaction basis.

In some embodiments, the configuration settings may specify when a loser transaction rollback will occur. Depending on the setting, the rollback may occur when the loser transaction attempts to commit its private copy, or immediately when the winner transaction succeeds in committing its copy. The former option may be preferable in some cases where the transaction writer wishes to receive rollback notifications synchronously to better handle the rollback.

In some embodiments, the configuration settings may also specify conflict resolution options. For example, in some cases, transaction resolution may default to a “first finisher wins” setting, where the first transaction that commits its private copy will cause all competing transactions to roll back. Another conflict resolution option may implement starvation avoidance. In one implementation, if a particular transaction has been retried after a number of rollbacks, the database system will allow that transaction to succeed by failing all transactions that compete with the starved transaction. As yet another example, embodiments of the database system proactively select winning transactions based on different factors such as current contention level of impacted data objects, the expected execution time of the transaction, the determined transaction scope of the transaction, etc. As will be appreciated by those skilled in the art, a wide variety of conflict resolution strategies are possible in different embodiments of the database system.

FIG.7illustrates an example process to execute a transaction in the transactional database system (e.g. transaction database system100), according to some embodiments.

At operation710, the transactional database system manages transactions for a database. Data in the database is stored in an object storage system (e.g. object storage system140) as data objects (e.g. data objects154) organized in a hierarchical data structure (e.g. hierarchical data structure150. In some embodiments, the object storage system is a distinct system from the transactional database system, and may be operated remotely by a different operator (e.g. a multi-tenant infrastructure service provider). In some embodiments, the object storage system may be a distributed data storage system that provides strongly consistent writes. In some embodiments, the data objects154may be individual data files, and the hierarchical data structure may be a directory structure of a file system.

At operation720, a transaction that accesses a plurality of data items (e.g. reads and writes multiple data times) is initiated. As discussed, the database system may perform the transaction atomically, where all data updates succeed or fail together, and all data reads and writes are performed in a single logical point in time. As shown, operations730and740are performed as part of the transaction initiation720.

At operation730, the database system determines data object(s) that will be accessed by the transaction. Operation730may be performed based on the code of the transaction based on the reads and writes in the transaction. In some embodiments, the transaction code may include a prepare statement or clause that explicitly specifies what data will be accessed by the transaction. In some embodiments, the transaction scope is determined based on a specified level of granularity or data object isolation, which may be specified for the database, the table(s), or the transaction.

At operation740, a copy of the data object(s) that will be accessed by the transaction is created. The copy (e.g. copies160and162) is created in the object storage system and possibly in the same location as the source data object(s). The copy will be used as a private copy by the transaction to read and write data during execution of the transaction. In some embodiments, the copy may be performed via an atomic copy operation (e.g. atomic copy operation450).

At operation750, the transaction is completed, either as a successful commit of the transaction or a rollback. Operations760,770, and780are all performed as part of the transaction completion750.

At operation760, a determination is made whether the committed state of the data object(s) accessed by the transaction has changed outside the transaction (e.g. by another committed transaction), since the transaction began. In some embodiments, this check is made based on the contents of one or more metadata objects (e.g. metadata file430) or files stored in the object storage system. In some embodiments, the check may be made based on the native file metadata of the data object files.

If the committed state of the data object(s) has not changed, at operation770, the database system updates the metadata object(s) in the object storage system to refer to the transaction's private copy as the newly committed state of the data object(s). Upon this update, the committed state of the data object(s) will be officially updated and made visible to all subsequent database readers. In some embodiments, the update of metadata objects may be performed as an atomic update operation (e.g. atomic update operation460). After the committed state of the data object(s) has been updated, the database system generates a message (e.g. an acknowledgement to the client transaction request) indicating that the transaction has been successfully committed.

On the other hand, if the committed state of the data object(s) has not changed, at operation780, the database system abandons the transaction's private copy so that it is not referred to as the committed state of the data object(s). In some embodiments, the abandonment may cause the private copy to be deleted or marked for later deletion. The database system may then generate a message to indicate that the transaction has failed (and rolled back) due to a conflict. In some embodiments, a rolled back transaction may be automatically retried by the database system for up to a certain number of attempts.

FIG.8is a block diagram illustrating an example computer system that can be used to implement one or more portions of the transactional database system, according to some embodiments.

Computer system1000may include or be configured to access one or more nonvolatile computer-accessible media. In the illustrated embodiment, computer system1000includes one or more processors1010coupled to a system memory1020via an input/output (I/O) interface1030. Computer system1000further includes a network interface1040coupled to I/O interface1030.

In various embodiments, computer system1000may be a uniprocessor system including one processor1010, or a multiprocessor system including several processors1010(e.g., two, four, eight, or another suitable number). Processors1010may be any suitable processors capable of executing instructions. For example, in various embodiments, processors1010may be general-purpose or embedded processors implementing any of a variety of instruction set architectures (ISAs), such as the x86, PowerPC, SPARC, or MIPS ISAs, or any other suitable ISA. In multiprocessor systems, each of processors1010may commonly, but not necessarily, implement the same ISA.

System memory1020may be configured to store instructions and data accessible by processor(s)1010. In various embodiments, system memory1020may be implemented using any suitable memory technology, such as static random access memory (SRAM), synchronous dynamic RAM (SDRAM), nonvolatile/Flash-type memory, or any other type of memory. In the illustrated embodiment, program instructions and data implementing one or more desired functions, such as those methods, techniques, and data described above, are shown stored within system memory1020as code1025and data1035. As shown, in some embodiments, the program instructions memory1025may be used to implement one or more executable components such as the transactional database system100ofFIG.1. As shown, in some embodiments, the data memory1035may be used to store data such as the data object(s)154ofFIG.1.

In one embodiment, I/O interface1030may be configured to coordinate I/O traffic between processor1010, system memory1020, and any peripheral devices in the device, including network interface1040or other peripheral interfaces. In some embodiments, I/O interface1030may perform any necessary protocol, timing or other data transformations to convert data signals from one component (e.g., system memory1020) into a format suitable for use by another component (e.g., processor1010). In some embodiments, I/O interface1030may include support for devices attached through various types of peripheral buses, such as a variant of the Peripheral Component Interconnect (PCI) bus standard or the Universal Serial Bus (USB) standard, for example. In some embodiments, the function of I/O interface1030may be split into two or more separate components, such as a north bridge and a south bridge, for example. Also, in some embodiments some or all of the functionality of I/O interface1030, such as an interface to system memory1020, may be incorporated directly into processor1010.

Network interface1040may be configured to allow data to be exchanged between computer system1000and other devices1060attached to a network or networks1050, such as other computer systems or devices, such as routers and other computing devices, as illustrated inFIGS.1through8, for example. In various embodiments, network interface1040may support communication via any suitable wired or wireless general data networks, such as types of Ethernet network, for example. Additionally, network interface1040may support communication via telecommunications/telephony networks such as analog voice networks or digital fiber communications networks, via storage area networks such as Fibre Channel SANs, or via any other suitable type of network and/or protocol.

In some embodiments, system memory1020may be one embodiment of a computer-accessible medium configured to store program instructions and data as described above forFIGS.1through8for implementing embodiments of methods and apparatus for traffic analysis. However, in other embodiments, program instructions and/or data may be received, sent or stored upon different types of computer-accessible media. Generally speaking, a computer-accessible medium may include non-transitory storage media or memory media such as magnetic or optical media, e.g., disk or DVD/CD coupled to computer system1000via I/O interface1030. A non-transitory computer-accessible storage medium may also include any volatile or non-volatile media such as RAM (e.g. SDRAM, DDR SDRAM, RDRAM, SRAM, etc.), ROM, etc, that may be included in some embodiments of computer system1000as system memory1020or another type of memory. Further, a computer-accessible medium may include transmission media or signals such as electrical, electromagnetic, or digital signals, conveyed via a communication medium such as a network and/or a wireless link, such as may be implemented via network interface1040.

Although specific embodiments have been described above, these embodiments are not intended to limit the scope of the present disclosure, even where only a single embodiment is described with respect to a particular feature. Examples of features provided in the disclosure are intended to be illustrative rather than restrictive unless stated otherwise. The scope of the present disclosure includes any feature or combination of features disclosed herein (either explicitly or implicitly), or any generalization thereof, whether or not it mitigates any or all of the problems addressed herein. Accordingly, new claims may be formulated during prosecution of this application (or an application claiming priority thereto) to any such combination of features. In particular, with reference to the appended claims, features from dependent claims may be combined with those of the independent claims and features from respective independent claims may be combined in any appropriate manner and not merely in the specific combinations enumerated in the appended claims.

The methods described herein may be implemented in software, hardware, or a combination thereof, in different embodiments. In addition, the order of the blocks of the methods may be changed, and various elements may be added, reordered, combined, omitted, modified, etc. Various modifications and changes may be made as would be obvious to a person skilled in the art having the benefit of this disclosure. The various embodiments described herein are meant to be illustrative and not limiting. Many variations, modifications, additions, and improvements are possible. Accordingly, plural instances may be provided for components described herein as a single instance. Boundaries between various components, operations and data stores are somewhat arbitrary, and particular operations are illustrated in the context of specific illustrative configurations. Other allocations of functionality are envisioned and may fall within the scope of claims that follow. Finally, structures and functionality presented as discrete components in the example configurations may be implemented as a combined structure or component. These and other variations, modifications, additions, and improvements may fall within the scope of embodiments as defined in the claims that follow.