Fine grain synchronization for database replay

CROSS-REFERENCE TO RELATED APPLICATIONS

0001This application claims priority to <patcit id="pcit0001" dnum="US77532210A" dnum-type="L"><text>U.S. Application No. 12/775,322 filed May 6, 2010</text></patcit> entitled "Fine Grain Synchronization For Database Replay". This application is related to: (1) <patcit id="pcit0002" dnum="US85327106P" dnum-type="L"><text>U.S. Pat. App. No. 60/853,271</text></patcit>, entitled "Database Workload Capture And Replay Architecture," filed Oct. 20, 2006; (2) <patcit id="pcit0003" dnum="US80012207A" dnum-type="L"><text>U.S. Pat. App. No. 11/800,122</text></patcit>, entitled "Database Workload Capture And Replay Architecture," filed May 3, 2007; (3) <patcit id="pcit0004" dnum="US80024007A" dnum-type="L"><text>U.S. Pat. App. No. 11/800,240</text></patcit>, entitled "Database Workload Replay Remapping Infrastructure," filed May 3, 2007; (4) <patcit id="pcit0005" dnum="US80023807A" dnum-type="L"><text>U.S. Pat. App. No. 11/800,238</text></patcit>, entitled "Transactionally Consistent Database Workload Replay," filed May 3, 2007; (5) <patcit id="pcit0006" dnum="US80022407A" dnum-type="L"><text>U.S. Pat. App. No. 11/800,224</text></patcit>, entitled "Client-Driven Functionally Equivalent Database Replay," filed May 3, 2007; (6) <patcit id="pcit0007" dnum="US80023907A" dnum-type="L"><text>U.S. Pat. App. No. 11/800,239</text></patcit>, entitled "Capturing Database Workload While Preserving Original Transactional And Concurrency Characteristics For Replay," filed May 3, 2007. Collectively, these six related applications are referred to as the "Workload Capture and Replay" applications.

FIELD OF THE INVENTION

0002The present invention relates to capturing a workload in one database system and replaying that workload in another database system.

BACKGROUND

DATABASE SYSTEMS

0003A database management system ("DBMS") manages a database. A database management system may comprise one or more database servers. A database comprises database data and metadata that is stored on a persistent memory mechanism, such as a set of hard disks. Metadata defines database objects, such as relational tables, table columns, view, and triggers.

0004Database applications and clients interact with a database server by submitting to the database server commands that cause the database server to perform operations on data stored in a database by executing the commands against the database. A database command may be in the form of a database statement that conforms to a database language. A language for expressing database requests is the Structured Query Language (SQL). There are many different versions of SQL, some versions are standard and some proprietary, and there are a variety of extensions. SQL data definition language ("DDL") instructions are issued to a database server to create or configure database objects, such as tables, views, or complex data types. SQL/XML is a common extension of SQL used when manipulating XML data in an object-relational database. Although the examples are described based on Oracle's SQL, the techniques provided herein are not restricted to any particular version of SQL or to any particular form of database command.

TESTING AND VALIDATING A DATABASE SYSTEM

0005Large business-critical applications are complex and experience highly varying load and usage patterns. These applications are expected to provide certain service guarantees in terms of response time, throughput, uptime, and availability. At times, it may be desirable to change a system that includes such applications. Such a change might involve upgrading the system's database server or modifying a configuration, for example. However, before any change is made to a production system, extensive testing and validation should be performed in a test system. In order to be confident that a change will not cause problems (e.g., errors or performance issues) in the production system once that change is introduced into the production system, a system tester should try to expose the test system to a workload that is very similar to the workload that the production system would actually experience in a real world environment.

0006Many other approaches have not been able to replicate a real production workload in a test system. According to one approach, a set of test scripts is written to test commonly executed code paths. Although this approach can be useful for performing regression testing and functional testing, this approach does not mimic a production workload. This approach usually stresses the testing system only to a very minimal extent.

0007Under another approach, human users are asked to use the test system as though the test system were a production system. However, this approach is very random and nondeterministic. This approach often fails to reproduce the load patterns that would be experienced in an actual production environment.

DATABASE WORKLOAD CAPTURE AND REPLAY

0008Under a Database Workload Capture and Replay architecture developed by Oracle, Inc., as described in the Workload Capture and Replay applications, a test database system is exposed to a workload in the same commit order that the production database system originally processed the workload. However, the test database system may take more or less time to process some transactions than the production database system. Because the order of transactions is strictly preserved, the test system may unnecessarily wait for some transactions to complete before processing other transactions. Strictly preserving the order of transactions may be sub-optimal for the test system.

0009On the other hand, allowing the test system to process the transactions out of order may cause the test data maintained by the test system to diverge from the production data as it was maintained in the production system. In other words, a transaction executed out of order by a test system may no longer read or modify the data that was read or modified by a same or similar transaction in the production system, resulting in a test workload that is misrepresentative of the production workload. Also, a transaction executed out of order may cause the test system to break by, for example, reading or modifying data that does not yet exist.

0010What is needed is a technique that allows a test system to process a workload in a manner that: (a) is not strictly tied to the order of execution by a production system; and (b) converges to a same or similar state of data as the production system and does not break when processing transactions in a different order than the production system.

0011The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.

0012<patcit id="pcit0008" dnum="US20090106219A1"><text>US 2009/0106219 A1</text></patcit> discloses techniques for ensuring, except in rare circumstances, that a database server executes a database command according to a query plan that has been verified to be optimal. When the database server receives a request to execute a database command, the database server may determine that an unverified plan is the best plan for satisfying the request. However, rather than risk the unknown behavior of the unverified plan, the database server instead satisfies the request according to a verified plan. Subsequently - for example as part of a scheduled job - the database server executes the unverified plan to determine performance statistics. Based at least on the performance statistics, the database server determines whether or not to verify the unverified plan.

0013The article "<nplcit id="ncit0001" npl-type="s"><text>Oracle database replay" by Leonidas Galanis et al., SIGMOD '08, pages 1159-1169</text></nplcit>, discloses a database replay technique that uses a transactional model to achieve end state consistency and result consistency. The transactional model assumes that every commit action affects every subsequent call. The article points out that this coarse transactional model may consider two captured calls dependent even if they are not. The article further mentions that is it possible to use a more refined transactional model for database replay that only considers true dependencies between captured calls.

0014The book "<nplcit id="ncit0002" npl-type="b"><text>Fundamentals of Database Systems" by Ramez Elmasri et al., Addison-Wesley, 2004, discloses on page 583</text></nplcit> that locking protocols are used in most commercial database management systems. The book further discloses, on page 586, a shared/exclusive locking scheme in which, <i>inter alia</i>, a transaction must obtain a write lock on a data item before the transaction performs any write operation on this data item.

SUMMARY

0015The present invention is defined by the independent claims. The dependent claims concern optional features of some embodiments of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

0016The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which: <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">FIG. 1</figref> is a block diagram that shows an example of a system in which workload that is submitted to a production database server is captured and replayed to a test database server, according to an embodiment described herein;</li><li><figref idref="f0002">FIGS. 2A</figref> and <figref idref="f0003">2B</figref> are tables showing information in a sample workload that is captured according to an embodiment described herein;</li><li><figref idref="f0004">FIGS. 3A</figref> and <figref idref="f0005">3B</figref> are dependency graphs constructed for a sample workload according to an embodiment described herein; and</li><li><figref idref="f0006">FIG. 4</figref> is a block diagram that illustrates a computer system upon which an embodiment described herein may be implemented.</li></ul>

DETAILED DESCRIPTION

0017In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

GENERAL OVERVIEW

0018According to one embodiment, a production database system executes one or more commands received from one or more clients. A workload describing the one or more commands is captured, and the captured workload includes object identifiers that identify database objects that were referenced directly or indirectly by the one or more commands that were executed by the production database system. The captured workload also includes an indication of whether the database objects were read or written when the production system executed the commands. A workload of captured object identifiers, captured indications of whether the objects were read and/or written, and captured database commands may be processed to determine that an object accessed when the production system executed a command may have been previously modified when the production system previously executed one or more other commands. During replay, a replay process on a test database system prevents execution of a command that accessed a previously modified object until the one or more other commands have been executed to complete one or more previous modifications to the object. The test database system may execute commands in a different order than the commands were originally executed in the production system even though one or more of the commands depend on one or more other commands. In one embodiment, although the commands are executed in a different order, the test data maintained in the test system does not diverge from the production data that was maintained in the production system.

0019One command may be said to be "dependent" upon another command when execution of the one command caused the production system to access an object that was previously at least potentially modified during execution of the other command. The dependency of one command to another command may be determined by processing a captured workload that identifies the objects accessed and/or modified during execution of the commands. Also, a command may be said to "access" an object if execution of the command by a database server potentially causes the database server to access the object. For example, execution of a command that references a view causes the database server to access a table upon which the view is based. In this manner, the command may be said to "access" the table or "use" the table since the database server, through execution of the command, is accessing or using the table. As another example, a command may be said to "access" a table if execution of the command causes the database server to obtain a lock on the table, even if the database server does not in fact access the table when executing the command.

0020The object identifiers may identify any type of database object in the database. In one embodiment, the object identifiers are table identifiers that identify tables. Table identifiers may be captured to identify the tables that were accessed and/or modified by a command. In a particular embodiment, those tables that were accessed and/or modified by a command may be identified from a cursor that stores information about the tables that were accessed and/or modified by the command. For example, the cursor may provide information that identifies the tables in which locks were required in order to execute the command. If a command reads or modifies a table, then the production database system may obtain a lock on the table in the process of executing the command. The lock may be one of many different types of locks (for example, a shared lock or an exclusive lock), and the type of lock obtained may provide information about whether the command accessed and/or modified the table. A command with an exclusive lock on an object is presumed to have modified the object. A command with a shared lock on an object may be presumed to have accessed the object without modifying it.

0021The workload may be used to determine that a second command depends on a first command. For example, a second command depends on a first command if, during production, the second command accesses an object that was previously modified by the first command. In response to determining that the second command depends on the first command, a workload processing system may store an indication that the second command should not be executed until after execution of the first command when the workload is replayed. For example, the indication may be used by a replay process on the test system to prevent the second command from being executed until after execution of the first command during replay. In one embodiment, the indication triggers the replay process to execute the second command after the first command has been executed during replay.

0022In one embodiment, a second command that depends on a first command is encountered by a replay process during a replay of the commands. The replay process determines that the first command has not yet been executed during the replay. In response to determining that the first command has not yet been executed, the replay process waits to execute the second command. In one embodiment, the replay process determines that the first command has not yet been executed by accessing a counter associated with a replay driver from which the first command is to be received. The counter records a count of a most recently executed command by the corresponding driver, or by a corresponding thread emulated by the driver. For example, the test database system may determine that the first command has not yet been executed when the first command is associated with a count that is greater than the count of the most recently executed command for that thread.

0023In one embodiment, the first command is received and executed by the test database system after the second command is received. The replay process determines that the first command has been executed and, in response, causes the second command to be executed on the test database system. In one embodiment, the replay process determines that the first command has been executed by accessing the count associated with a thread from which the first command is sent. For example, the replay process may determine that the first command has been executed when the first command is associated with a count that is less than or equal to the count of the most recently executed command from the thread. In one embodiment, the count for each thread stores only the count of the most recently executed command for that thread.

0024In one embodiment, information such as a dependency graph is stored to indicate that a second command that was executed in a production system depends on a first command that was previously executed in a production system. The dependency graph may be constructed based on the workload captured by the production system. In one embodiment, during replay, the second command is not executed by the test database system before the test database system has executed the first command. The dependency graph may be accessed to determine that the second command depends on the first command. In one embodiment, a replay process determines if the dependency is satisfied by determining if the first command has already been executed during replay. For example, a shared counter may be stored for each thread indicating a last executed command for the thread. The replay process may check the shared counter for a thread associated with the first command to determine whether the first command has been executed by the thread during replay. If the first command has not yet been executed during replay, then the dependency is not satisfied. In response to determining that the dependency is not satisfied, the replay process waits to execute the second command until the first command has been executed during replay. Other commands not directly or indirectly dependent upon the first command may be executed while waiting for the first command.

0025In one embodiment, the information used for synchronizing a replay of the commands does not include a time that the first or the second commands were executed in the production system. In other words, the commands may be synchronized based on a dependency graph alone without referencing a logical time that the commands were executed by the production system. A global ordering of replayed commands, including a global ordering of replayed commands to commit changes, does not need to be determined before the workload is replayed in the test system. The dependency graph may be constructed based on an ordering of commands and object identifiers accessed or modified by the commands. Once the dependency graph is constructed, the commands may be replayed in any order that satisfies the dependency graph. In one embodiment, an order that the commands are executed by the replay system is realized dynamically during replay based on data dependency information. In this manner, data dependency may be ensured during replay without requiring a global ordering of the commands to be replayed, whether or not those commands are to commit changes. In a particular embodiment, the dependency graph stores pairings of commands including a first command and a second command. During replay, the second command is not executed until the first command has been executed. When there is no direct or indirect data dependency between commands, they may be replayed in any order with respect to each other.

0026In one embodiment, an indirect dependency between commands does not need to be recorded in order to be enforced. For example, if a third command is from a same thread as an earlier second command, then the third command will follow the second command during replay regardless of whether a dependency is stored between the third command and the second command. In this manner, a dependency that specifies that both the third command and the second command are to be executed after a first command may be enforced by only specifying that the second command is to be executed after the first command.

CAPTURING WORKLOAD

0027A workload capture and replay architecture is described in the Workload Capture and Replay applications. These applications describe techniques for capturing a workload of a production system, processing the workload to prepare the workload for replay, replaying the workload on the test system, and monitoring the performance of the test system. The captured workload may include information about the initial state of a database and information that describes a set of calls or database commands made against the database. The captured workload may also include transactional data such as System Change Numbers (SCNs) that describe a relative time at which the calls were received, executed, or committed against the database. The initial state of the database, and the set of issued commands and their associated SCNs define the state of the database against which a given database command was executed.

0028The techniques described in the Workload Capture and Replay applications cause a test system to process the same workload in the same commit order as the production system. Techniques described herein allow a test system to process a workload in a manner that is not strictly tied to the order of execution by a production system. The techniques described herein for capturing, processing, replaying, and monitoring are not limited by those techniques provided in the Workload Capture and Replay applications.

0029<figref idref="f0001">FIG. 1</figref> is a block diagram that shows an example of a system in which workload that is submitted to a production database server is captured and replayed to a test database server. The example shown includes clients 104A-N, application servers 106A-N, a production database server 108, a production database 112, captured workload 114, replay drivers 116A-N, test database server 118, which includes a replay process for replaying commands received from replay drivers 116A-N, and test database 120. Production database server 108 includes capture processes 110A-N.

0030Clients 104A-N may be separate computers or separate processes that execute on the same computer. For example, in one embodiment, clients 104A-N are Internet browsers (e.g., Mozilla Firefox) that execute on separate computers that are communicatively coupled to the Internet. In one embodiment, clients 104A-N send requests to, and receive responses from, application servers 106A-N over the Internet.

0031Application servers 106A-N may be separate computers or separate processes that execute on the same computer. For example, in one embodiment, application servers 106A-N are web server-invoked processes that execute on separate servers that are communicatively coupled to the Internet. In one embodiment, application servers 106A-N receive requests from, and send responses to, clients 104A-N over the Internet. Each of application servers 106A-N may implement different functionality for responding to different types of requests from clients 104A-N.

0032In servicing requests from clients 104A-N, application servers 106A-N might need to retrieve data from and/or store data to a database. To accomplish this, in one embodiment, application servers 106A-N establish database sessions with production database server 108. Within these sessions, application servers 106A-N send database commands to production database server 108. Such database commands may include Structured Query Language (SQL) select statements, for example.

0033Production database server 108 executes these database commands relative to production database 112. As a result of the executing these database commands, production database server 108 may store data in, and/or retrieve data from, production database 112. Production database server 108 may execute two or more database commands in a transactional manner, so that none of the effects of the database commands in a single transaction are made permanent in production database 112 unless all of the effects of those database commands can be made permanent. Production database server 108 may return, to application servers 106A-N, data retrieved from production database 112 as a result of the execution of certain database commands (e.g., SQL select statements). Applications servers 106A-N may use such retrieved data in forming responses to clients 104A-N.

0034In one embodiment, production database server 108 includes capture processes 110A-N. Capture processes 110A-N may be implemented as separate concurrently executing processes or as concurrently executing threads of the same process, for example. In one embodiment, capture processes 110A-N collectively, transparently, and non-intrusively capture all workload that production database server 108 receives from external entities (e.g., application servers 106A-N and/or clients 104A-N).

0035As used herein, the term "workload" refers to discrete, independently meaningful units called "workload units". In one embodiment, each "workload unit" corresponds to a separate "user request" (e.g., a request originating from (a) one of clients 104A-N, (b) one of application servers 106A-N, or (c) some other process that is external to production database server 108). In one example, the workload includes information that describes one or more commands requested to be executed by the production database server, object identifiers of one or more database objects associated with the one or more commands, and an indication of whether the object identifiers were accessed and/or modified by the one or more commands.

0036In one embodiment, the information that describes one or more commands includes the actual text of the command, such as the SQL text of a SQL command. Alternately, the information that describes one or more commands may include command identifiers that identify one or more commands or one or more parts of the one or more commands. Optionally, the information that describes the commands may be stored in a binary or compressed format. The information that describes the commands may be stored in any format in any manner, and the commands may be used by a test database system to replay the commands that were originally executed on the production database system. In one embodiment, the commands stored in the captured workload require further processing in order to prepare the commands to be replayed on the test database system.

0037Capture processes 110A-N store and record this workload as captured workload 114. As a result, captured workload 114 may comprise workload that was captured during a specified interval of time, referred to herein as the "recording interval". In one embodiment, captured workload 114 represents actual real-world use of production database server 108, which use is not specifically for any testing purpose.

0038In one embodiment, capture processes 110A-N initially write captured workload to in-memory buffers. Data stored in these in-memory buffers is compressed and written out in batches to persistent storage. Because an I/O transaction involving persistent storage does not need to be performed after the capture of every individual workload unit, the impact of the workload capture on the performance of production database server 108 is reduced.

CAPTURING INFORMATION FOR DETERMINING DATA DEPENDENCY

0039Instead of strictly replaying a workload in the same commit order, techniques described herein make replay determinations based on whether one command depends on another command. In one such technique, a capture process captures information identifying objects that are accessed or modified by commands executed on the production system. The captured information may be part of the captured workload, or the captured information may be captured separately from the captured workload. The captured information may be any information that can be processed to determine that a particular command accessed one or more objects that were last modified by one or more other commands. In a specific form of this technique, the particular command is associated with: (a) a same object identifier as a commit command that committed one or more changes to the object, and (b) a relatively later execution time than the commit command. The particular command and the one or more other commands may be stored in a dependency graph. The replay process may read the commands and the dependency graph, and may wait to execute the particular command in the test database system until after one or more other commands, based on the dependency graph, are executed. Replay drivers may send commands threads corresponding to clients of the production system. A replay process on the test database system may replay commands until the replay process reaches a particular command that cannot yet be executed due to a data dependency between the particular command and a previous command from another thread. The replay process may then wait for the previous command from the other thread to be executed, and may then execute the particular command upon detection of this event.

0040The captured information may include any information that identifies a potential or probable data dependency between two commands. The captured information may include a timing element and a data element. For example, the captured information may include an SCN, an object identifier that identifies an object related to the two or more commands, and an indication of whether each of the two or more commands accessed and/or modified the object.

0041In another technique, a production system captures commands and SCNs associated with the commands, using increasing SCNs as the commands are committed against a database. Commands with lower SCNs are associated with an earlier state of the database than commands with higher SCNs. In one example, an earlier database command commits a change to the database in the production system, and a later database command reads the database in the production system. The SCNs for the commands may be used to determine that the earlier command, with a lower SCN, was executed before the later command, with a higher SCN. In other words, the SCNs may be used to determine a relative timing element for two commands. In the example, the database did not reflect the change before the earlier command, but the database did reflect the change after the earlier command and before the later command.

0042A particular command may be replayed before other commands in the test system if, in the production system, the other commands did not previously modify an object that was accessed by the particular command. In the example above, the test system may replay the later command before the earlier command so long as the later command is not replayed before any commands that previously modified an object that was accessed by the later command. For example, even though a command to modify Table 1 may have been executed before a command to read or modify Table 2 in the production system, the command to read or modify Table 2 may be replayed before the command to modify Table 1 in the test system because executing the command to modify Table 1 does not affect the outcome of the command to read or modify Table 2.

0043On the other hand, the command to read or modify Table 2 may not be replayed before a command that previously modified Table 2 in the production system. Replaying the commands out of order may cause the state of the database as maintained by the test system to diverge from the state of the database as maintained by the production system.

0044According to the claimed invention, the data dependency determination is made, and the data dependency graph is constructed, based on information that identifies a potential or probable data dependency, wherein each database object is considered to have been previously at least potentially modified by another database command if execution of the other database command caused one or more database servers to obtain an exclusive lock on said database object. In a particular embodiment, cursor information from a transactional cursor associated with the command is used to determine object identifiers that were potentially accessed or modified by the command and an indication of whether those object identifiers were potentially modified or just potentially accessed. For example, a cursor may indicate that an exclusive lock was obtained on Table 1 and a non-exclusive or shared lock was obtained on Table 2 when processing the command. Based on the cursor information, the command can be said to have accessed and modified Table 1 and accessed Table 2 without making a modification to Table 2. In some cases, a command may obtain an exclusive lock on a table without actually modifying the table. The command is determined to have modified the table due to the exclusive lock that was obtained even if the command did not actually modify the table. In this manner, all potential data dependencies may be preserved by defining the logical data dependencies to include the actual data dependencies but without determining the actual data dependencies.

0045In one embodiment, the captured object identifiers represent objects that are actually referenced directly or indirectly in the commands. In one example, a command may directly reference a table, and an object identifier that identifies the table may be captured. In another example, a command that references a view may indirectly access a table referenced by the view. An object identifier that identifies the table is captured in order to ensure that the command referencing the view is executed against the proper state of the table referenced by the view. In one embodiment, both direct and indirect references to objects are reflected by the object identifiers associated with the locks.

0046<figref idref="f0002">FIGS. 2A</figref> and <figref idref="f0003">2B</figref> illustrate example workload information that may be captured from a production database system and processed to generate a dependency graph. As shown, the workload information is stored in a table, for example, a table stored on the computer system shown in <figref idref="f0006">FIG. 4</figref>. However, a person skilled in the art would understand that such information could be represented in a variety of other ways.

0047<figref idref="f0002">FIG. 2A</figref> shows calls as they were executed against a production database. Each commit changes the state of the production database and causes the SCN to increase. For example, the UPDATE T1 call from THREAD 1 does not affect the first READ T1 call from THREAD 2 because the UPDATE T1 call was not committed until after execution of the first READ T1 call from THREAD 2. However, the second and third READ T1 calls from THREAD 2 are affected by the UPDATE T1 call because they are executed after the UPDATE T1 call was committed. Based on the information displayed in <figref idref="f0002">FIG. 2A</figref>, it may be determined that the second and third READ T1 calls from THREAD 2 must wait for the commit call from THREAD 1. <figref idref="f0003">FIG. 2B</figref> shows another table that lists the example calls, the tables read by the calls, and the tables written by the calls. As shown, READ T1(2), and READ T1(4) both read table T1 and have SCNs after COMMIT(1), which modifies table T1.

PROCESSING AND REPLAYING WORKLOAD

0048The Workload Capture and Replay applications describe replaying the workload on the test system in the same commit order that the workload was processed by the production system, according to the SCNs captured from the production system. For example, a production system receiving calls from three clients would use three replay drivers to emulate the calls from the three clients on three threads. The calls replayed by all the replay drivers would be executed on the test system in the same global commit order as the calls were executed on the production system.

0049According to the techniques described herein, the global commit order of the calls in production does not have to be strictly preserved during replay. The replay ordering of the commands does not need to be determined before execution of the commands on the test system. Threads on replay drivers emulate the clients that initially submitted the commands that were executed on the production system. The commands from the different threads are submitted by the replay drivers to the test system during replay. The test system receives the commands and executes the commands in a manner that preserves the dependencies specified by the dependency graph. In this manner, the global order of execution is dynamically realized during playback based on the specified data dependencies.

0050In one embodiment, if a data dependency cannot be determined for a particular command, then a data dependency is stored that causes the particular command to wait for all commands previously executed before the particular command. In the same or another embodiment, a data dependency is stored that causes all commands previously executed after the particular command to wait for the particular command.

0051Referring to <figref idref="f0001">FIG. 1</figref>, after capture processes 110A-N have stored workload in captured workload 114, captured workload 114 may undergo automated processing. This automated processing may be performed in a non-real-time manner. For example, after capture processes 110A-N have finished storing data in captured workload 114, processes external to production database server 108 may process captured workload 114. This processing may be performed while production database server 108 services further requests from application servers 106A-N. Thus, the processing of captured workload 114 may be performed without any interference with or impact on the operations of production database server 108. In one embodiment, processing the workload results in a dependency graph and a list of commands for each of replay drivers 116A-N.

0052In one embodiment, after captured workload 114 has undergone processing as discussed above, each of replay drivers 116A-N sends commands from the processed workload to test database server 118 in the same manner that the commands were sent to production database server 108 from a respective client of clients 104A-N or a respective application server of application servers 106A-N. Replay drivers 116A-N may be implemented as separate concurrently executing processes or as concurrently executing threads of the same process, for example. In one embodiment, replay drivers 116A-N send their respective commands to the test database server 118, which accesses a dependency graph to preserve dependency without requiring a global ordering of execution of the commands.

0053In one embodiment, each of replay drivers 116A-N can replay workload that was captured by multiple separate capture processes 110A-N. Therefore, in one embodiment there may be fewer replay drivers 116A-N than capture processes 110A-N. Each of replay drivers 1116A-N may be multi-threaded.

0054Test database server 118 may be different in one or more respects from production database server 108. For example, test database server 118 might be an upgraded version of production database server 108. For another example, test database server 118 might be the same brand and version of production database server 108, but test database server 118 might be configured differently (e.g., in one or more settings) from production database server 108. For yet another example, test database server 118 might be an entirely different brand of database server from production database server 108. Test database server 118 might execute on a machine that has different hardware than the hardware of the machine on which production database server 108 executes. Test database server 118 might execute in conjunction with a different operating system than the operating system in conjunction with which production database server 108 executes. The purpose of subjecting test database server 118 to the same workload as that to which production database server 108 was actually subjected may be to determine whether the difference between test database server 118 and production database server 108, and/or the difference in the environments in which those database servers execute, is a permissible or desirable difference.

0055Test database server 118 processes the commands that test database server 118 receives from replay drivers 116A-N. If the workload comprises database commands, then test database server 118 executes the database commands relative to test database 120. As a result of the executing these database commands, test database server 118 may store data in, and/or retrieve data from, test database 120. If the dependency graph specifies that a particular command is to wait for one or more other commands, then test database server 118 waits for the one or more other commands to be executed before executing the particular command to test database server 118. Test database server 118 executes commands from others of replay drivers 116A-N while test database server 118 waits for the one or more other commands to be executed. In response to executing the one or more other commands, test database server 118 detects that the particular command is waiting to be executed and causes the particular command to be executed. Test database server 118 may return, to replay drivers 116A-N, data retrieved from test database 120 as a result of the execution of certain database commands (e.g., SQL select statements).

0056In the embodiment illustrated in <figref idref="f0001">FIG. 1</figref>, there is one instance of the production database server and one instance of the test database server. However, in alternative embodiments, there may be multiple production database server instances, all of which perform database operations relative to production database 112. Additionally, in alternative embodiments, there may be multiple test database server instances, all of which perform database operations relative to test database 120. In one embodiment, the number of production database server instances differs from the number of test database server instances.

0057Test database 120 may be different in one or more respects from production database 112. For example, the manner in which logical relational database structures are physically laid out and stored on disk in test database 120 might differ from the manner in such logical relational database structures are physically laid out and stored on disk in production database 112. Thus, although the values present in the data that is stored in test database 120 will converge to the same as the data that is stored in production database 112, the manner in which those values are stored on disk may differ between the two databases. Additionally, the manner in which relational tables are partitioned in test database server 120 may differ from the manner in which corresponding relational tables are partitioned in production database 112. Additionally, indices that are (or are not) constructed for relational tables in test database 120 may differ from indices that are (or are not) constructed for corresponding relational tables in production database 112. The performance of test database server 118 and/or test database 120 may be evaluated to determine whether the difference between test system and the production system is a permissible or desirable difference.

0058The recording interval may begin at a time at which production database 112 is already in a certain state. For example, at the time that the recording interval begins, production database 112 might already contain one or more logical data structures (e.g., database tables, stored procedures, triggers, views, indices, etc.) which might already be populated with data. If test database 120 did not also contain these structures in the same state by the time that replay drivers 116A-N begin to "replay" captured workload 114 to test database server 118, then the execution of database commands within the replayed workload relative to test database 120 might produce errors. Therefore, in one embodiment, before replay drivers 116A-N begin to replay captured workload 114 to test database server 118, test database 120 is placed in the same logical state as production database 108. This may be accomplished by "backing up" production database 112 and performing a restore, from the resulting backup data, to test database 120, for example. In one embodiment, such a back up is performed at or shortly prior to the time that the original workload is going to be received at the production database 112. This essentially captures the pre-workload state of production database 112. Consequently, when the backup data is restored relative to test database 120, the state of test database 120 is highly similar to the state in which production database 112 existed prior to the receipt of the original workload.

0059The time interval during which replay drivers 116A-N replay captured workload 114 to test database server 118 may be completely non-overlapping and non-concurrent with the time interval during which capture processes 110A-N intercept and store that workload. For example, capture processes 110A-N might intercept and record captured workload 114 during a first time interval. Hours, days, or even weeks after the end of that first time interval, replay drivers 116A-N might replay captured workload 114 to test database server 118 during a second time interval that is not concurrent with any part of the first time interval.

0060In one embodiment, clients 104A-N and application servers 106A-N are not needed to replay captured workload 114 to test database server 118. Because replay drivers 116A-N handle the replaying of captured workload 114 to test database server 118, there is no need to duplicate clients 104A-N or application server 106A-N in the replay system. This advantageously saves resources.

0061<figref idref="f0004">FIGS. 3A</figref> and <figref idref="f0005">3B</figref> illustrate an example dependency graph that lists calls and calls to wait for. For example, information from <figref idref="f0002">FIGS. 2A</figref> and <figref idref="f0003">2B</figref> may be used to construct a dependency graph as illustrated in <figref idref="f0004">FIG. 3A</figref>, which specifies that the READ T1(2), READ T1(3), and READ T1(4) calls all wait on the COMMIT(1) call. As shown, the dependency graph is stored in a table, for example, a table stored on the computer system shown in <figref idref="f0006">FIG. 4</figref>. However, a person skilled in the art would understand that such information could be represented in a variety of other ways.

0062The dependency graph may be optimized by removing redundant information from the graph. For example, let the notation "B -> A" mean that call B waits for call A before being executed. If B->A and B->C, then the entry B->C may be removed from the graph if (1) C comes from the same thread as A and (2) C's call counter is less than A. In other words, if call A is sent after call C by the same thread, then it would be redundant to explicitly specify that call B is to wait for both calls A and C. In this case, waiting for call A implies also waiting for call C. In one embodiment the graph stores only B->A and not B->C.

0063As another example, assuming B->A and D->A, the entry D->A may be removed from the graph if (1) D comes from the same thread as B and (2) D's call counter is greater than B. In other words, if call D is sent after call B in the same thread, then it would be redundant to explicitly specify that call A is to be executed before both calls B and D. In this case, executing call A before call B implies also executing call A before call D. In one embodiment, the graph stores only B->A and not D->A.

0064As yet another example, the dependency B->A may be removed from the dependency graph if A and B are from the same thread because, in one embodiment, the order of execution of calls from the same thread is preserved.

0065As shown by comparing <figref idref="f0004">FIG. 3A</figref> and <figref idref="f0005">FIG. 3B</figref>, in the example, the READ T1(3) call is removed from the dependency graph because the READ T1(3) call appears in the same thread as the COMMIT(1) call and will be replayed after the COMMIT(1) call even without the use of the dependency graph. Also, the READ T1(4) call is removed from the dependency graph because the READ T1(4) call appears in the same thread as the READ T1(2) call and will be replayed after the READ T1(2) call even without use of the dependency graph. Using the dependency graph, the test database system will replay the READ T1(2) call after the COMMIT(1) call.

0066When executing the READ T1(2) call, the test database system uses the dependency graph to determine that READ T1(2) depends on COMMIT(1). Then, the test database system determines whether or not COMMIT(1) has already been replayed. If COMMIT(1) has not yet been replayed, the test database system waits to execute READ T1(2) until COMMIT(1) is replayed. The test database system may execute any or all of the READ T2, UPDATE T2, and COMMIT(2) calls from PROCESS 3 before the COMMIT(1) call even though these calls came after the COMMIT(1) call in the production system. Prior execution of these commands to modify table T2 does not affect execution of commands relating to table T1.

0067In one embodiment, each respective replay driver stores those commands that were submitted by the corresponding client in the production system. For example, the replay driver associated with THREAD 1 stores those commands that were submitted by the first thread in the production system, and the replay driver associated with THREAD 2 stores those commands that were submitted by the second thread in the production system. The test database server stores a portion of the dependency graph that specifies that READ T1(2) from THREAD 2 is to wait for COMMIT(1) from THREAD 1. When the test database system replays the commands, the test database system waits to execute the READ T1(2) command until COMMIT(1) has been executed.

MONITORING PERFORMANCE

0068The Workload Capture and Replay applications further describe monitoring the performance of the test system and making a determination of whether or not to replace the production system with the test system. For example, the determination to replace the production system with the test system may be made when the test system exhibits a good performance when processing the same workload as the production system. The techniques described herein do not require monitoring performance of the test system or the production system. If performance of either system is monitored, any known or later developed performance monitoring technique may be used in conjunction with the techniques described herein.

0069In one embodiment, the state of the test database is compared to the state of the production database to ensure that the state of the test database converges to the state of the production database. In the same or another embodiment, results of executing commands in the test environment may be compared to results of executing commands in the production environment. In yet another embodiment, the relative timing that commands were executed in the test system may be compared to the relative timing that commands were executed in the production system.

0070The performance data may be used to determine whether or not to use a test database system as a production database system. For example, the test database system may be determined to exhibit good performance as compared to the production database system if the state of the test database converges to the state of the production database, if the test database system runs more efficiently or processes commands more quickly than the production database system.

HARDWARE OVERVIEW

0071According to one embodiment, the techniques described herein are implemented by one or more special-purpose computing devices. The special-purpose computing devices may be hard-wired to perform the techniques, or may include digital electronic devices such as one or more application-specific integrated circuits (ASICs) or field programmable gate arrays (FPGAs) that are persistently programmed to perform the techniques, or may include one or more general purpose hardware processors programmed to perform the techniques pursuant to program instructions in firmware, memory, other storage, or a combination. Such special-purpose computing devices may also combine custom hard-wired logic, ASICs, or FPGAs with custom programming to accomplish the techniques. The special-purpose computing devices may be desktop computer systems, portable computer systems, handheld devices, networking devices or any other device that incorporates hard-wired and/or program logic to implement the techniques.

0072For example, <figref idref="f0006">FIG. 4</figref> is a block diagram that illustrates a computer system 400 upon which techniques described herein may be implemented. Computer system 400 includes a bus 402 or other communication mechanism for communicating information, and a hardware processor 404 coupled with bus 402 for processing information. Hardware processor 404 may be, for example, a general purpose microprocessor.

0073Computer system 400 also includes a main memory 406, such as a random access memory (RAM) or other dynamic storage device, coupled to bus 402 for storing information and instructions to be executed by processor 404. Main memory 406 also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor 404. Such instructions, when stored in storage media accessible to processor 404, render computer system 400 into a special-purpose machine that is customized to perform the operations specified in the instructions.

0074Computer system 400 further includes a read only memory (ROM) 408 or other static storage device coupled to bus 402 for storing static information and instructions for processor 404. A storage device 410, such as a magnetic disk or optical disk, is provided and coupled to bus 402 for storing information and instructions.

0075Computer system 400 may be coupled via bus 402 to a display 412, such as a cathode ray tube (CRT), for displaying information to a computer user. An input device 414, including alphanumeric and other keys, is coupled to bus 402 for communicating information and command selections to processor 404. Another type of user input device is cursor control 416, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor 404 and for controlling cursor movement on display 412. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

0076Computer system 400 may implement the techniques described herein using customized hard-wired logic, one or more ASICs or FPGAs, firmware and/or program logic which in combination with the computer system causes or programs computer system 400 to be a special-purpose machine. According to one embodiment, the techniques herein are performed by computer system 400 in response to processor 404 executing one or more sequences of one or more instructions contained in main memory 406. Such instructions may be read into main memory 406 from another storage medium, such as storage device 410. Execution of the sequences of instructions contained in main memory 406 causes processor 404 to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions.

0077The term "storage media" as used herein refers to any media that store data and/or instructions that cause a machine to operation in a specific fashion. Such storage media may comprise non-volatile media and/or volatile media. Non-volatile media includes, for example, optical or magnetic disks, such as storage device 410. Volatile media includes dynamic memory, such as main memory 406. Common forms of storage media include, for example, a floppy disk, a flexible disk, hard disk, solid state drive, magnetic tape, or any other magnetic data storage medium, a CD-ROM, any other optical data storage medium, any physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, NVRAM, any other memory chip or cartridge.

0078Storage media is distinct from but may be used in conjunction with transmission media. Transmission media participates in transferring information between storage media. For example, transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus 402. Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications.

0079Various forms of media may be involved in carrying one or more sequences of one or more instructions to processor 404 for execution. For example, the instructions may initially be carried on a magnetic disk or solid state drive of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system 400 can receive the data on the telephone line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data on bus 402. Bus 402 carries the data to main memory 406, from which processor 404 retrieves and executes the instructions. The instructions received by main memory 406 may optionally be stored on storage device 410 either before or after execution by processor 404.

0080Computer system 400 also includes a communication interface 418 coupled to bus 402. Communication interface 418 provides a two-way data communication coupling to a network link 420 that is connected to a local network 422. For example, communication interface 418 may be an integrated services digital network (ISDN) card, cable modem, satellite modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface 418 may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface 418 sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

0081Network link 420 typically provides data communication through one or more networks to other data devices. For example, network link 420 may provide a connection through local network 422 to a host computer 424 or to data equipment operated by an Internet Service Provider (ISP) 426. ISP 426 in turn provides data communication services through the world wide packet data communication network now commonly referred to as the "Internet" 428. Local network 422 and Internet 428 both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link 420 and through communication interface 418, which carry the digital data to and from computer system 400, are example forms of transmission media.

0082Computer system 400 can send messages and receive data, including program code, through the network(s), network link 420 and communication interface 418. In the Internet example, a server 430 might transmit a requested code for an application program through Internet 428, ISP 426, local network 422 and communication interface 418.

0083The received code may be executed by processor 404 as it is received, and/or stored in storage device 410, or other non-volatile storage for later execution.

0084In the foregoing specification, embodiments of the invention have been described with reference to numerous specific details that may vary from implementation to implementation. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.