Patent Description:
<CIT> discloses a data processing framework that polls for files using a listener, controls the workflow using event driven logic, processes financial transactions using payment management functions, and creates a business to business trading partner network. A payment management computer identifies a universal identifier for each entity of the trading partner network and forms relationships and hierarchies. Metadata describes the format, validation and relationships for a variety of financial account data.

It is the object of the present invention to provide an improved method and system for determining inconsistency of data files in a distributed database system.

Methods, systems, apparatuses, and computer-readable storage mediums described herein are configured to detect data inconsistencies with respect to a table of a database and identify the cause of such data inconsistencies. In an analytical database system, the data is usually column-oriented, compressed and stored in chunks/files/rowgroups/partitions (referred herein as "data files"). The logical data within these data files is immutable and the system only allows the creation and dropping of an entire data file. The techniques described herein generally consist of two phases. In the first phase, lineage events/logs are emitted across different components of the distributed system that operate (creates/drops/removes) on the data files. In the second phase, a consistency checking engine analyzes these events and detects the inconsistencies.

In case of a lineage event validation failure, the following conclusions can be made immediately (a) there is a database corruption; (b) the operation and the component responsible for the corruption; (c) the time of the corruption; and/or (d) determine, by analyzing the remaining lineage events, whether the corrupted data has propagated to more data files to establish the overall extent of the corruption.

Determining the answers to these questions is critical to plan the mitigation course and determine the following: (a) determining the correct time to restore the customer database that avoids corruptions and minimize the data loss; (b) determine the type of wrong results experienced by the customer after corruption (e.g., determine whether it was a data loss or duplicate data; and/or (c) determine whether the corruption is repairable (that is, whether it is possible to recover all the customer data before and after the corruption is repairable (that is, whether it is possible to recover all the customer data before and after the corruption event).

In case of repairable corruption, a repair task may auto correct the corruption. The lineage event has enough data to facilitate creation of a compensating repair task corresponding to the operation that caused the corruption. In software as a service (SaaS) setting, the techniques described herein may be used by the service provider to provide integration guarantees for the database by periodically checking the database consistency.

Further features and advantages, as well as the structure and operation of various example embodiments, are described in detail below with reference to the accompanying drawings. It is noted that the example implementations are not limited to the specific embodiments described herein. Such example embodiments are presented herein for illustrative purposes only. Additional implementations will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein.

The accompanying drawings, which are incorporated herein and form a part of the specification, illustrate example embodiments of the present application and, together with the description, further serve to explain the principles of the example embodiments and to enable a person skilled in the pertinent art to make and use the example embodiments.

The features and advantages of the implementations described herein will become more apparent from the detailed description set forth below when taken in conjunction with the drawings, in which like reference characters identify corresponding elements throughout.

The present specification and accompanying drawings disclose numerous example implementations. The scope of the present application is not limited to the disclosed implementations, but also encompasses combinations of the disclosed implementations, as well as modifications to the disclosed implementations. References in the specification to "one implementation," "an implementation," "an example embodiment," "example implementation," or the like, indicate that the implementation described may include a particular feature, structure, or characteristic, but every implementation may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same implementation. Further, when a particular feature, structure, or characteristic is described in connection with an implementation, it is submitted that it is within the knowledge of persons skilled in the relevant art(s) to implement such feature, structure, or characteristic in connection with other implementations whether or not explicitly described.

In the discussion, unless otherwise stated, adjectives such as "substantially" and "about" modifying a condition or relationship characteristic of a feature or features of an implementation of the disclosure, should be understood to mean that the condition or characteristic is defined to within tolerances that are acceptable for operation of the implementation for an application for which it is intended.

Numerous example embodiments are described as follows. Implementations are described throughout this document, and any type of implementation may be included under any section/subsection. Furthermore, implementations disclosed in any section/subsection may be combined with any other implementations described in the same section/subsection and/or a different section/subsection in any manner.

Embodiments described herein are directed to detecting data inconsistencies with respect to a database and identifying the cause of such data inconsistencies. There are certain assumptions that are made about the database system which includes: most of the data is stored in immutable data files, data files could be created, copied, dropped (soft deleted) or deleted by different components in the distributed system, there is a global version/timestamp associated with each operation. These are reasonable assumptions for most distributed analytical database systems. The techniques described herein consists of two phases. During the first phase, lineage events are emitted from different components of the distributed system that operate on the data files. During the second phase, a consistency checking engine analyzes these events and detects the inconsistencies. The lineage event forms the record of the operation done on the data file and includes the following information a) the unique file identifiers (IDs) for data files that are input for the operation, b) the unique file IDs of the data files produced by the operation, c) type of the operation, d) the transaction version of the operation, e) the actor or the component, f) the time of the operation and/or g) the status of operation i.e., whether it was committed or not. Whenever a consistency check operation is initiated, the lineage event records are first ordered by their transaction version. Two sets are maintained while processing each event: a valid set, which tracks the data file IDs that should be visible until the currently processed event, and an invalid set, which tracks the data files IDs that should not be visible. Iteration is done over each event, starting from the event with lowest version and validating whether the input data file IDs belong to either the valid or invalid set based on the operation type. Post validation, the inputs and/or outputs of the operation are added to either the valid or invalid sets based on the side effect of the operation. Any contradiction observed during this validation process indicates a potential corruption. The consistency checking engine may evaluate the events periodically or on demand by including all the events up to a certain time in the past.

The foregoing techniques checks the integrity of the database and assists in understanding the root cause in case of a corruption. Moreover, it provides the timeline for the corruption and whether it is repairable or not. These properties are very valuable as they allow determining the right time to restore the customer's database or right set of actions to repair the corruption. In case of repairable corruption, the correct compensating repair actions may be applied. Still further, the foregoing techniques advantageously improves the integrity of the data maintained by the database, and therefore, ensures that applications accessing the database operate on the correct data. Lastly, the availability of the database is improved, as hardware and/or software failures that are normally attributed to data inconsistencies is reduced.

For example, <FIG> shows a block diagram of an example network-based computing system <NUM> configured to determine data inconsistencies in a database, according to an example embodiment. As shown in <FIG>, system <NUM> includes a plurality of clusters 102A, 102B and 102N and a storage cluster <NUM>. Each of clusters 102A, 102B and 102N and storage cluster <NUM> are communicatively coupled to each other via network <NUM>. Network <NUM> may comprise one or more networks such as local area networks (LANs), wide area networks (WANs), enterprise networks, the Internet, etc., and may include one or more of wired and/or wireless portions.

Clusters 102A, 102B and 102N and/or storage cluster <NUM> may form a network-accessible server set (e.g., a cloud-based environment). Each of clusters 102A, 102B and 102N may comprise a group of one or more nodes (also referred to as compute nodes) and/or a group of one or more storage nodes. For example, as shown in <FIG>, cluster 102A includes nodes 108A-108N, cluster 102B includes nodes 112A-112N, and cluster 102N includes nodes 114A-114N. Each of nodes 108A-108N, 112A-112N and/or 114A-114N are accessible via network <NUM> (e.g., in a "cloud-based" embodiment) to build, deploy, and manage applications and services. Storage cluster <NUM> comprises one or more storage nodes 110A-110N. Each of storage node(s) 110A-110N comprises a plurality of physical storage disks that are accessible via network <NUM> and is configured to store data associated with the applications and services managed by nodes 108A-108N, 112A-112N, and/or 114A-114N.

As shown in <FIG>, storage node(s) 110A-110N comprise data sets 122A-122N, respectively. Each of data sets 122A-122N include databases and/or the like, in embodiments, which may be very large data sets such as for "Big Data" analytics and/or data warehousing. It is contemplated herein that one or more of data sets 122A-122N are to the order of petabytes, or more, in embodiments. Data sets 122A-122N may include a plurality of data files. The data files may comprise structured, relational data, organized as rows of tables, having columns for the data. Examples of data files include, but are not limited to, a database file, a chunk, a group of one or more rows of the table (i.e., a rowgroup), partitions, etc.).

In accordance with an embodiment, data sets 122A-122N are part of the same database that is distributed among storage node(s) 110A-110N. In accordance with such an embodiment, each of the data files may be immutable (i.e., the data files are not modifiable). Any requested modifications to a given data file are recorded and/or stored as a separate data file, where a copy of the data file (for which a modification is requested) is generated and the modifications are applied to the copy.

In an embodiment, one or more of clusters 102A, 102B and 102N and/or storage node(s) 110A-110N may be co-located (e.g., housed in one or more nearby buildings with associated components such as backup power supplies, redundant data communications, environmental controls, etc.) to form a datacenter, or may be arranged in other manners. Accordingly, in an embodiment, one or more of clusters 102A, 102B and 102N and/or storage node(s) 110A-110N may be a datacenter in a distributed collection of datacenters.

Each of node(s) 108A-108N, 112A-112N and 114A-114N may comprise one or more server computers, server systems, and/or computing devices. Each of node(s) 108A-108N, 112A-112N and 114A-114N may be configured to execute one or more software applications (or "applications") and/or services and/or manage hardware resources (e.g., processors, memory, etc.), which may be utilized by users (e.g., customers) of the network-accessible server set. Node(s) 108A-108N, 112A-112N and 114A-114N may also be configured for specific uses. For example, as shown in <FIG>, node 108A may be configured to execute a database server application <NUM> and node 108N may be configured to execute a data consistency engine <NUM>. It is noted that instances of database server application <NUM> and/or data consistency engine <NUM> may be executing on other node(s) (e.g., node(s) 108B-108N, node(s) 112A-112N, and/or node(s) 114A-114N) in lieu of or in addition to nodes 102A and 108N, respectively. It is further noted that data consistency engine <NUM> may be incorporated in another application, such as database server application <NUM>.

Node 108A (or any other node executing an instance of database server application <NUM>) may be a control node configured to act as the query endpoint for incoming queries, to produce a distributed plan for an incoming query, and to divide work for query processing among one or more of compute nodes 108B-108N, nodes 112A-112N, and nodes 114A-114N. That is, according to embodiments, node 108A is configured to transform an incoming query into a set of queries that are run against each distribution of a data set in parallel via one or more of nodes 108B-108N, nodes 112A-112N, and nodes 114A-114N.

Database server application <NUM> may be any database server application, including, but not limited to Microsoft® Azure SQL Database™ published by Microsoft® Corporation of Redmond, Washington. Database server application <NUM> is configured to execute statements to create, modify, and delete one or more data files of tables of data, indexes, and relationships in data set(s) 122A-122N, e.g., based on an incoming query.

Queries may be user-initiated or automatically generated by one or more background processes. Such queries may be configured to add data file(s), copy data file(s), merge data file(s) into a larger data file, re-organize (or re-cluster) data file(s) (e.g., based on a commonality of data file(s)) within a particular set of data files, delete data file(s) (e.g., via a garbage collection process that deletes unwanted or obsolete data), etc..

Over time, data file(s) of data sets 122A-122N may become corrupt or inconsistent due to hardware issues, software bugs, faults, etc. Data consistency engine <NUM> is configured to detect whether a data inconsistency exists with respect to data file(s) of a table maintained by data sets 122A-122N and identify one or more database operations and/or the initiator of such operation(s) that caused the data inconsistency. For instance, data consistency engine <NUM> may periodically obtain all lineage event records associated with a particular table maintained by data sets 122A-122N and order them by transaction version. Each event record includes information about a particular operation performed with respect to data file(s) of the table. The information for a particular operation may include a transaction version, an operation type, a set of input data file identifiers (identifiers of data files inputted or acted on by the operation), a set of output data file identifiers (identifiers of data files outputted by the operation), an actor (or source) of the operation, the time of operation and an operation status.

For each event record, data consistency engine <NUM> determines whether the operation associated therewith was successful or unsuccessful based on the operation status associated with the event record or by looking up the status of the transaction version. In response to a determination that the operation associated with the event record was successful, any data file identifier in the set of output data file identifiers associated with the event record are designated as being part of a valid data file set. Data files identified as being part of the valid data file represent data files on which subsequent operations may operate (i.e., such data files are valid/visible within the database). Data consistency engine <NUM> also designates any data file identifier included in the set of input data file identifiers associated with the event record that is already included in the valid data file set as being part of an invalid data file set. That is, data file identifiers that are already included in the valid data file set are moved to the invalid data file set. Data files identified as being part of the invalid data file represent data files that should no longer be used by subsequent operations. Such data files should be eventually deleted at some point, for example, by a garbage collection process.

In response to a determination that the operation was unsuccessful (e.g., the operation has failed), data consistency engine <NUM> designates any data file identifier in the set of output data file identifiers associated with the event record as being part of the invalid data file set.

After designating data file identifiers for a particular event record as being part of a valid data file set or an invalid data file, data consistency engine <NUM> determines whether a data consistency exists with respect to the table based on analysis of a subsequent event records in the ordered sequence that follows the particular event record. In particular, data consistency engine <NUM> selects a data consistency rule based on the operation and applies the selected data consistency rule to the current valid data file set, the current invalid data file set, and the set of input data file identifiers and/or set of output data file identifiers of the subsequent event record. The selected data consistency rule is configured to determine whether a data inconsistency exists based on its application to the current valid data file set, the current invalid data file set, and the set of input data file identifiers and/or set of output data file identifiers of the subsequent event record.

In response to determining that a data inconsistency exists, data consistency engine <NUM> may automatically perform a remediation of the data inconsistency if it is repairable. For example, data consistency engine <NUM> cause a data file that was inadvertently deleted to be recovered, e.g., restoring the data files marked for deletion if they are not garbage collected yet. In another example, data consistency engine <NUM> may cause a problematic data file from a data set of data sets 122A-122N in which it is included to be removed (or deleted), for example, to ensure that a data file created by a failed operation is not carried forward as an input to subsequent operations. In yet another example, data consistency <NUM> may cause one or more operations to be rolled back to a point before the data inconsistency occurred.

<FIG> depicts a block diagram of a system <NUM> for obtaining event records in accordance with an example embodiment. As shown in <FIG>, system <NUM> comprises a database application <NUM>, a data consistency engine <NUM>, a data store <NUM>, a node <NUM>, a node <NUM>, and a node <NUM>. Database application <NUM> is an example of database application <NUM>, as described above with reference to <FIG>. Data consistency engine <NUM> is an example of data consistency engine <NUM>, as described above with reference to <FIG>. Nodes <NUM>, <NUM>, and <NUM> are examples of any of nodes 108A-108N, nodes 112A-112N, or nodes 114A-114N. Database application <NUM> and data consistency engine <NUM> may execute on one or more of nodes 108A-108N, nodes 112A-112N, or nodes 114A-114N.

Each of nodes <NUM>, <NUM>, and <NUM> may be configured to perform an operation with respect to data file(s) of a data set (e.g., data set(s) 122A-122N). Examples of operations include, but are not limited to, user-initiated operations (e.g., a load operation (e.g., that stores new data file(s) into a data set), a merge operation (that merges the contents of two or more data file(s) and stores the contents into a new data file), etc. or a background process, such as, but not limited to, a garbage collection process, a re-clustering process, a re-indexing process, etc..

Data store <NUM> may be any type of physical memory and/or storage device that is described herein, and/or as would be understood by a person of skill in the relevant art(s) having the benefit of this disclosure. Data store <NUM> may be included in and/or distributed among any of storage nodes 110A-110N or any memory or storage device maintained by node(s) of nodes 108A-108N, nodes 112A-112N, or nodes 114A-114N, as described above with reference to <FIG>.

As shown in <FIG>, database application <NUM> may comprise a transaction manager <NUM>. Transaction manager <NUM> is configured to coordinate the database operations to be performed by nodes <NUM>, <NUM>, and <NUM>. To perform an operation, a node may issue a request to transaction manager <NUM>. For example, node <NUM> may issue a request <NUM> to transaction manager, node <NUM> may issue a request <NUM>, and node <NUM> may issue a request <NUM>.

Responsive to receiving request <NUM>, transaction manager may issue a unique transaction version to node <NUM>, for example, via a response <NUM>. Responsive to receiving request <NUM>, transaction manager may issue a unique transaction version to node <NUM>, for example, via a response <NUM>. Responsive to receiving request <NUM>, transaction manager may issue a unique transaction version to node <NUM>, for example, via a response <NUM>. The transaction version provided to one of nodes <NUM>, <NUM>, and <NUM> may comprise a number or timestamp that uniquely identifies the transaction. For each subsequent request, the transaction version is incremented such that is greater than the previous transaction version.

Responsive to receiving response <NUM>, node <NUM> performs its operation with respect to the data set. After the operation is performed, node <NUM> attempts to commit the operation. Node <NUM> provides an indicator <NUM> to transaction manager <NUM> that specifies whether the commit was successful or whether it was unsuccessful.

Responsive to receiving response <NUM>, node <NUM> performs its operation with respect to the data set. After the operation is performed, node <NUM> attempts to commit the operation. Node <NUM> provides an indicator <NUM> to transaction manager <NUM> that specifies whether the operation was successfully committed or not.

Responsive to receiving response <NUM>, node <NUM> performs its operation with respect to the data set. After the operation is performed, node <NUM> attempts to commit the operation. Note <NUM> provides an indicator <NUM> to transaction manager <NUM> that specifies whether the operation was successfully committed or not.

After the operations performed by a respective node of nodes <NUM>, <NUM>, and <NUM> are finished (whether they completed successfully or unsuccessfully), the respective node may store information pertaining to the operation in data store <NUM> as an event record. For example, node <NUM> may store information <NUM> in data store <NUM> as a first event record, node <NUM> may store information <NUM> in data store <NUM> as a second event record, and node <NUM> may store information <NUM> in data store <NUM> as a third event record.

Examples of information <NUM> include, but are not limited to, the transaction version assigned to node <NUM>, an operation type (e.g., a merge operation, a load operation, a re-cluster operation, a garbage collection operation, etc.), a set of input data file identifier(s) that identify data file(s) acted on by the operation performed by node <NUM>, a set of output data file identifier(s) that identify data file(s) generated by the operation performed by node <NUM>, the time of the operation, an operation status (e.g., an indication as to whether the operation performed by node <NUM> completed successfully or unsuccessfully), and/or an actor or source of the operation (e.g., an identification of the node that issued the operation or an identifier of a user or application that issued the operation).

Examples of information <NUM> include, but are not limited to, the transaction version assigned to node <NUM>, an operation type (e.g., a merge operation, a load operation, a re-cluster operation, a garbage collection operation, etc.), a set of input data file identifier(s) that identify data file(s) acted on by the operation performed by node <NUM>, a set of output data file identifier(s) that identify data file(s) generated by the operation performed by node <NUM>, the time of the operation, and/or an operation status (e.g., an indication as to whether the operation performed by node <NUM> completed successfully or unsuccessfully).

Data consistency engine <NUM> is configured to obtain the event records (shown as event records <NUM>) for a given table from data store <NUM>. For example, data consistency engine <NUM> may be configured to periodically retrieve records <NUM> from data store <NUM>. Alternatively, event records <NUM> may be periodically pushed to data consistency engine <NUM>.

After retrieving event records <NUM>, data consistency engine <NUM> sorts event records <NUM> in sequential order based on the transaction version included in each of event records <NUM>. After sorting event records <NUM>, data consistency engine <NUM> determines whether a data inconsistency exits with respect to the table. Additional details regarding data inconsistency determination are described below.

It is noted that certain information included in event records <NUM> may not be provided by nodes <NUM>, <NUM>, and/or <NUM>. For example, the operation status may not be provided by nodes <NUM>, <NUM>, and/or <NUM>. In this example, to obtain the operation status, data consistency engine <NUM> may query transaction manager <NUM>, obtain the operation status therefrom, and incorporate the operation status into event records <NUM> obtained from data store <NUM>.

<FIG> depicts a plurality of event records <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> in accordance with an embodiment. Each of event records <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> comprises a plurality of fields. Each field stores a piece of information pertaining to an operation represented by the associated event record. For example, each of event records <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> may comprise an operation type field, an actor filed, an input data file identifier field, an output data file identifier field, a transaction version field, and an operation status field. The operation type field of a particular event record specifies the type of operation represented by the event record. The actor field of a particular event record specifies the actor or source of the operation represented by the event record. The input data file identifier field identifies the data file(s) acted on or utilized by the operation represented by the event record. The output data file identifier field identifies the data file(s) generated by the operation represented by the event record. The transaction version field specifies the transaction version associated with the operation represented by the event record. The operation status field identifies the operation status of the operation represented by the event record.

As shown in <FIG>, the operation type field of event record <NUM> specifies that the operation is a bulk load operation, the actor field of event record <NUM> specifies that the bulk load operation originated from a user transaction, the input data file identifier field of event record <NUM> specifies that no data file(s) were acted on by the bulk load operation, the output data file identifier field of event record <NUM> specifies that data files <NUM>, <NUM>, <NUM>, and <NUM> were generated by the bulk load operation, the transaction version field of event record <NUM> specifies that the transaction version of the bulk load operation is <NUM>, and the operation status field of event record <NUM> specifies that the bulk load operation was successful.

The operation type field of event record <NUM> specifies that the operation is a merge operation, the actor field of event record <NUM> specifies that the merge operation originated from a re-cluster process, the input data file identifier field of event record <NUM> specifies that data file <NUM> and <NUM> were acted on by the bulk load operation, the output data file identifier field of event record <NUM> specifies that data file <NUM> was generated by the merge operation (i.e., the contents of data files <NUM> and <NUM> were merged together and stored as newly-generated data file <NUM>), the transaction version field of event record <NUM> specifies that the transaction version of the merge operation is <NUM>, and the operation status field of event record <NUM> specifies that the merge operation was successful.

The operation type field of event record <NUM> specifies that the operation is a re-cluster operation, the actor field of event record <NUM> specifies that the re-cluster operation originated from a re-cluster process, the input data file identifier field of event record <NUM> specifies that data files <NUM> and <NUM> were acted on by the re-cluster operation, the output data file identifier field of event record <NUM> specifies that data files <NUM> and <NUM> were generated by the re-cluster operation (i.e., the contents data files <NUM> and <NUM> were re-organized into newly-generated data files <NUM> and <NUM>), the transaction version field of event record <NUM> specifies that the transaction version of the re-cluster operation is <NUM>, and the operation status field of event record <NUM> specifies that the re-cluster operation was successful.

The operation type field of event record <NUM> specifies that the operation is a merge operation, the actor field of event record <NUM> specifies that the re-cluster operation originated from a re-cluster process, the input data file identifier field of event record <NUM> specifies that data files <NUM> and <NUM> were acted on by the re-cluster operation, the output data file identifier field of event record <NUM> specifies that data file <NUM> was generated by the merge operation (i.e., the contents data files <NUM> and <NUM> were merged and stored into newly-generated data file <NUM>), the transaction version field of event record <NUM> specifies that the transaction version of the re-cluster operation is <NUM>, and the operation status field of event record <NUM> specifies that the merge operation was unsuccessful.

The operation type field of event record <NUM> specifies that the operation is a re-cluster operation, the actor field of event record <NUM> specifies that the re-cluster operation originated from a re-cluster process, the input data file identifier field of event record <NUM> specifies that data files <NUM> and <NUM> were acted on by the re-cluster operation, the output data file identifier field of event record <NUM> specifies that data file <NUM> was generated by the re-cluster operation (i.e., the contents data files <NUM> and <NUM> were re-organized into newly-generated data file <NUM>), the transaction version field of event record <NUM> specifies that the transaction version of the re-cluster operation is <NUM>, and the operation status field of event record <NUM> specifies that the re-cluster operation was successful.

The operation type field of event record <NUM> specifies that the operation is a garbage collection operation, the actor field of event record <NUM> specifies that the garbage collection operation originated from a garbage collection process, the input data file identifier field of event record <NUM> specifies that data file <NUM> was acted on by the garbage collection operation (i.e., data file <NUM> was deleted by the garbage collection process), the output data file identifier field of event record <NUM> specifies that no data files were generated by the garbage collection operation, the transaction version field of event record <NUM> specifies that the transaction version of the garbage collection operation is <NUM>, and the operation status field of event record <NUM> specifies that the garbage collection operation was successful.

As described above with reference to <FIG>, data consistency engine <NUM> may obtain event records <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> (e.g., from data store <NUM>) and sort event records <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> in sequential order based on the transaction versions specified in the transaction version fields. In the example shown in <FIG>, event records <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> have already been sorted in sequential order by data consistency engine <NUM>. As further described above, the operation status field may be populated by the node (e.g., node <NUM>, <NUM> or <NUM>) that provided the information provided to data store <NUM>, or alternatively, data consistency engine <NUM> may populate the operation status field by querying transaction manager <NUM> for the operation status of a particular operation. Data consistency engine <NUM> may specify the transaction version in the query, and transaction manager <NUM> may look up the operation status based on the transaction version.

Data consistency engine <NUM> may analyze each of event records <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> in sequential order. When analyzing a first event record of event records <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, data consistency engine <NUM> determines whether the input data file identifiers (specified in the input data file identifier field) or the output data file identifiers (specified in the output data file identifier field) are to be designated as being either in a valid data file set or an invalid data file set. For example, data consistency engine <NUM> may first determine whether the operation associated with the first event record was successful or unsuccessful based on the operation status specified in the operation status field of the first event record. In response to a determination that the operation associated with the event record was successful, any output data file identifier specified by the output data file identifier field of the event record are designated as being part of a valid data file set. Data files identified as being part of the valid data file represent data files on which subsequent operations may operate (i.e., such data files are valid within the database). Data consistency engine <NUM> also designates any input data file identifier specified by the input data file identifier field of the event record that is already included in the valid data file set as being part of an invalid data file set. That is, data file identifiers that are already included in the valid data file set are moved to the invalid data file set. Data files identified as being part of the invalid data file represent data files that should no longer be used by subsequent operations. Such data files should be eventually deleted at some point.

In response to a determination that the operation was unsuccessful (e.g., the operation failed), data consistency engine <NUM> designates any output data file identifier identified by the output data file identifier field of the event record as being part of the invalid data file set.

Data consistency engine <NUM> then analyzes the next event record in sequential order and selects and applies a data consistency rule based on the operation type of the next event record. Data consistency engine <NUM> determines whether a data inconsistency exists based on the application of the selected data consistency rule with respect to the valid data file set, the invalid data file set, and/or the information of the next event record.

Each operation type may be associated with a respective data inconsistency rule. For example, a bulk load operation may be associated with a first data inconsistency rule. The first data inconsistency rule may specify that the output data files identifiers of the event record associated with the bulk load operation should not be part of either the invalid data file set or the valid data file set before the bulk load operation takes place (i.e., the data files generated by the bulk load operation should be new data files that were not previously in the database). A garbage collection operation may be associated with a second data inconsistency rule. The second data inconsistency rule may specify that the input data file identifiers of the event record associated with the garbage collection operation should be part of the invalid data file set before the garbage collection process takes place (that is, the data files that were deleted by the garbage collection should no longer be valid in the database, and therefore, be designated as being part of the invalid data file set). The merge and re-cluster operations may be associated with a third data inconsistency rule. The third data inconsistency rule may specify that the input data file identifiers of the event record associated with the merge or re-cluster operation should be part of the valid data file set before the merge or re-cluster operation takes place. It is noted that data inconsistency engine <NUM> may utilize other rules for other types of operations and that the rules specified above are purely exemplary.

It is further noted that in certain embodiments, the event records maintained by data store <NUM> and data consistency engine <NUM> have a finite retention period or there is the possibility of missing events due to failures. The embodiments described herein may be extended to handle a partial set of event records by utilizing a different set of data inconsistency rules. The rules may be grouped into two types a strong rule and a weak rule. A strong rule would identify most types of inconsistencies but is ideal if a complete set of event records is maintained (e.g., there is no finite retention period or there are strong guarantees around the delivery of event records). A weak rule would miss certain inconsistencies but could be utilized with a partial set of event records. The first three data inconsistency rules described above are examples of strong rules.

A first example of a weak data inconsistency rule would be a rule that determines whether data files generated by aborted (or failed) operations and included in the invalid data file set are utilized by subsequent operations. If a subsequent operation utilizes such data files, then a data inconsistency with respect to such data files is determined.

A second example of a weak data inconsistency rule would be a rule that determines whether data files dropped (or deleted) by an operation and included in the invalid data file set are utilized by subsequent operation. If a subsequent operation utilizes such data files, then a data inconsistency with respect to such data files is determined.

A third example of a weak data inconsistency rule would be a rule that determines whether data files collected (or deleted) by a garbage collection are included in a valid data file set. If such data files are included in a valid data file set, then a data inconsistency exists with respect to such data files.

A fourth example of a weak data inconsistency rule would be a rule that determines whether data files utilized for a particular operation are included in an invalid data file set. If such data files are included in an invalid data file set, then a data inconsistency exists with respect to such data files.

Data consistency engine <NUM> may determine whether any of the input data file(s) or output data file(s) described above are inconsistent based on the application of such rules, which is performed iteratively through each of event records <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. It is noted that that data consistency engine <NUM> may apply such rules with respect to any number of event records.

<FIG> depicts a graph <NUM> depicting event records <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> and the dependencies therebetween in accordance with an example embodiment. <FIG> depicts a block diagram representing changes made to a valid data file set <NUM> and an invalid data file set <NUM> during data inconsistency analysis in accordance with an example embodiment. The analysis performed by data consistency engine <NUM> will now be described with reference to <FIG>. As shown in <FIG>, graph <NUM> comprises nodes 402A-402D, <NUM>, 406A, 406B, <NUM>, and <NUM>. Nodes 402A-402D are representative of output data files <NUM>-<NUM>, which are generated by the bulk load operation represented by event record <NUM>, as shown in <FIG>. Node <NUM> is representative of data file <NUM>. Data file <NUM> is generated as a result of merging the contents of data files <NUM> and <NUM> (represented by nodes 402A and 404B), as specified by event record <NUM>. Nodes 406A and 406B are representative of data files <NUM> and <NUM>. Data files <NUM> and <NUM> are generated as a result of the re-clustering operation performed with respect to data files <NUM> and <NUM>, as specified by event record <NUM>. Node <NUM> is generated as a result of merging the contents of data files <NUM> and <NUM> (represented by nodes <NUM> and 406A), as specified by event record <NUM>. Node <NUM> is representative of data file <NUM>, which is generated as a result of the re-clustering operation performed with respect to data files <NUM> and <NUM>, as specified by event record <NUM>.

As shown in <FIG>, valid data file set <NUM> and invalid data file set <NUM> are initially empty, although the examples described herein are not so limited. Data consistency engine <NUM> analyzes event record <NUM> and determines the operation type, e.g., by reading the operation type field of event record <NUM>. In this example, data consistency engine <NUM> determines that event record <NUM> is associated with a bulk load operation. As a result, data consistency engine <NUM> selects the first data consistency rule. Data consistency engine <NUM> applies the first data consistency rule with respect to event record <NUM> to determine whether data files <NUM>-<NUM> (specified in the output data file identifier field of event record <NUM>) are included in either valid data file set <NUM> or invalid data file set <NUM>. In this example, since both data sets <NUM> and <NUM> are empty, data consistency engine <NUM> determines that no data inconsistency exists.

Data consistency engine <NUM> also determines whether the bulk load operation of event record <NUM> was successful. For instance, data consistency engine <NUM> reads the operation status field of event record <NUM> and determines that the bulk load operation was successful. Data consistency engine <NUM> also reads the output data file identifier field of event record <NUM> to determine the data files generated by the bulk load operation (i.e., data files <NUM>-<NUM>). Data consistency engine <NUM> designates output data file identifiers <NUM>-<NUM> as being part of valid data file set <NUM>. As shown in <FIG>, data files <NUM>-<NUM> are now included in the valid data file set (shown as valid data file set <NUM>').

Next, data consistency engine <NUM> analyzes event record <NUM> and determines the operation type. In this example, data consistency engine <NUM> determines that event record <NUM> is associated with a merge operation. As a result, data consistency engine <NUM> selects the third data inconsistency rule. Data consistency engine <NUM> applies the third inconsistency rule with respect to event record <NUM> to determine whether data files <NUM> and <NUM> (as specified in the input data file identifier field of event record <NUM>) are included in valid data file set <NUM>'. In this example, since valid data file set <NUM>' comprises data file identifiers for data files <NUM> and <NUM>, data consistency engine <NUM> determines that no data inconsistency exists.

Data consistency engine <NUM> also determines whether the merge operation of event record <NUM> was successful. For instance, data consistency engine <NUM> reads the operation status field of event record <NUM> and determines that the merge operation was successful. As a result, data consistency engine <NUM> reads the input data file identifier field of event record <NUM> to determine the data file acted on by the merge operation (i.e., data file identifiers <NUM> and <NUM>). Data consistency engine <NUM> designates data file identifiers <NUM> and <NUM> as now being part of invalid data file set (shown as invalid data file set <NUM>"). Data consistency engine <NUM> also reads the output data file field of event record <NUM> to determine the data file(s) generated by the merge operation (i.e., data file <NUM>). Data consistency engine <NUM> designates data file identifier <NUM> as being part of the valid data file set (shown as valid data file set <NUM>").

Next, data consistency engine <NUM> analyzes event record <NUM> and determines the operation type. In this example, data consistency engine <NUM> determines that event record <NUM> is associated with a re-cluster operation. As a result, data consistency engine <NUM> selects the third data inconsistency rule. Data consistency engine <NUM> applies the third inconsistency rule with respect to event record <NUM> to determine whether data files <NUM> and <NUM> (as specified in the input data file identifier field of event record <NUM>) are included in valid data file set <NUM>". In this example, since valid data file set <NUM>" comprises data file identifiers for data files <NUM> and <NUM>, data consistency engine <NUM> determines that no data inconsistency exists.

Data consistency engine <NUM> also determines whether the re-cluster operation of event record <NUM> was successful. For instance, data consistency engine <NUM> reads the operation status field of event record <NUM> and determines that the re-cluster operation was successful. As a result, data consistency engine <NUM> reads the input data file identifier field of event record <NUM> to determine the data files acted on by the re-cluster operation (i.e., data file identifiers <NUM> and <NUM>). Data consistency engine <NUM> designates data file identifiers <NUM> and <NUM> as now being part of invalid data file set (shown as invalid data file set <NUM>‴). Data consistency engine <NUM> also reads the output data file field of event record <NUM> to determine the data file(s) generated by the merge operation (i.e., data files <NUM> and <NUM>). Data consistency engine <NUM> also designates data file identifiers <NUM> and <NUM> as being part of the valid data file set (shown as valid data file set <NUM>‴).

Next, data consistency engine <NUM> analyzes event record <NUM> and determines the operation type. In this example, data consistency engine <NUM> determines that event record <NUM> is associated with a merge operation. As a result, data consistency engine <NUM> selects the third data inconsistency rule. Data consistency engine <NUM> applies the third inconsistency rule with respect to event record <NUM> to determine whether data files <NUM> and <NUM> (as specified in the input data file identifier field of event record <NUM>) are included in valid data file set <NUM>'". In this example, since valid data file set <NUM>‴ comprises data file identifiers for data files <NUM> and <NUM>, data consistency engine <NUM> determines that no data inconsistency exists.

Data consistency engine <NUM> also determines whether the merge operation of event record <NUM> was successful. For instance, data consistency engine <NUM> reads the operation status field of event record <NUM> and determines that the re-cluster operation was unsuccessful. As a result, data consistency engine <NUM> reads the output data file identifier field of event record <NUM> to determine the data file generated (incorrectly) by the merge operation (i.e., data file identifier <NUM>). Data consistency engine <NUM> designates data file identifier <NUM> as being part of the invalid data file set (shown as invalid data file set <NUM>"").

Next, data consistency engine <NUM> analyzes event record <NUM> and determines the operation type. In this example, data consistency engine <NUM> determines that event record <NUM> is associated with a re-cluster operation. As a result, data consistency engine <NUM> selects the third data inconsistency rule. Data consistency engine <NUM> applies the third inconsistency rule with respect to event record <NUM> to determine whether data files <NUM> and <NUM> (as specified in the input data file identifier field of event record <NUM>) are included in valid data file set <NUM>"". In this example, since data file identifier <NUM> is included not included in valid data file set 412ʺʺ (and is instead included in invalid data file set <NUM>""), data consistency engine <NUM> determines that there is a data inconsistency with respect to data file <NUM>. Data consistency engine <NUM> also identifies the operation and/or actor that caused the inconsistency. For example, data consistency engine <NUM> may read the operation type and/or actor fields of the event record via which the inconsistency was detected (i.e., event record <NUM>) to identify the operation and/or actor that caused the inconsistency.

In response to finding such a data inconsistency, data consistency engine <NUM> may perform an operation to automatically remediate the data inconsistency. For example, data consistency engine <NUM> may send a request to transaction manager <NUM> that causes transaction manager <NUM> rollback the operations to a point before the merge operation represented by node <NUM> and/or causes data file <NUM> to be deleted after the merge operation is re-performed.

Accordingly, a consistency checking of data files represented by a table may be implemented in many ways. For example, <FIG> shows a flowchart <NUM> of a method for consistency checking of data files, in a distributed database system, that represent a table in accordance with an example embodiment. In an embodiment, flowchart <NUM> may be implemented by a system <NUM> shown in <FIG>, although the method is not limited to that implementation. Accordingly, flowchart <NUM> will be described with reference to <FIG>. As shown in <FIG>, system <NUM> comprises a data store <NUM> and a data consistency engine <NUM>. Data store <NUM> and data consistency engine <NUM> are examples of data store <NUM> and data consistency engine <NUM>, as respectively described above with reference to <FIG>. Data consistency engine <NUM> comprises an event record obtainer <NUM>, a data file set determiner <NUM>, a consistency checker <NUM>, a valid data file set <NUM>, an invalid data file set <NUM>, and data consistency rules <NUM>. Valid data file set <NUM> and invalid data file set <NUM> are examples of valid data file set <NUM> and invalid data file set <NUM>, as described above with reference to <FIG>. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the discussion regarding flowchart <NUM> and system <NUM> of <FIG>.

Flowchart <NUM> begins with step <NUM>. In step <NUM>, an ordered sequence of event records associated with table is obtained. Each event record in the ordered sequence includes information about a particular operation performed with respect to one or more of the data files, the information for the particular operation including a transaction version, an operation type, a set of input data file identifiers, a set of output data file identifiers, and an operation status. For example, with reference to <FIG>, event record obtainer <NUM> of data consistency engine <NUM> may obtain event records from data store <NUM>. The event records are provided to data file set determiner <NUM> and consistency checker <NUM>.

In accordance with one or more embodiments, the event records are obtained from the data store <NUM> as an unordered sequence, and the event records are organized in the ordered sequence based on the transaction versions associated therewith. For example, with reference to <FIG>, event record obtainer <NUM> may obtain the event records from data store <NUM> as an unordered sequence and organize the event records in the ordered sequence based on the transaction versions associated therewith.

The following steps <NUM>, <NUM>, and <NUM> are performed for each of one or more first event records in the ordered sequence in the order specified by the ordered sequence. At step <NUM>, a determination is made as to whether the operation associated with the first event record was successful or unsuccessful based on the operation status associated with the first event record. In the event that the operation was successful, flow continues to step <NUM>. Otherwise, flow continues to step <NUM>. For example, with reference to <FIG>, data file set determiner <NUM> determines whether the operation associated with the first event record was successful or unsuccessful based on the operation status associated with the first event record. For instance, data file set determiner <NUM> may read the operation status field of the first event record (as described above with reference to <FIG>) to determine whether the operation was successful or unsuccessful.

At step <NUM>, any data file identifier in the set of output data file identifiers associated with the first event record are designated as being part of a valid data file set. For example, with reference to <FIG>, data file set determiner <NUM> designates any data file identifier in the set of output data file identifiers associated with the first event record as being part of valid data file set <NUM>. For example, data file set determiner <NUM> may read the output data file identifier field of the first event record (as described above with reference to <FIG>) to determine whether an output data file identifier is included in the set. If any such output data file identifiers are included therein, data file set determiner <NUM> designates such output data file identifiers as being part of valid data file set <NUM>.

In accordance with one or more embodiments, in response to determining that the operation associated with the first event record was successful, any data file identifier in the set of input data file identifiers of the first event record, that is already included in the valid data file set, are re-designated as being part of the invalid data file set. For example, with reference to <FIG>, data file set determiner <NUM> determines whether any data file identifier in the set of input data file identifiers of the first event record are already included in valid data file set <NUM>. For example, data file set determiner <NUM> may read the input data file identifier field of the first event record (as described above with reference to <FIG>) to determine the input data file identifiers associated with the operation and compare such input data file identifiers to the identifiers included in valid data file set <NUM>. If such input data file identifiers are included in valid data file set <NUM>, data file set determiner <NUM> re-designates such input data file identifiers as being part of invalid data file <NUM> (i.e., such input data file identifiers are moved from valid data file set <NUM> to invalid data file set <NUM>).

At step <NUM>, any data file identifier in the set of output data file identifiers associated with the first event record are designated as being part of an invalid data file set. For example, with reference to <FIG>, data file set determiner <NUM> designates any data file identifier in the set of output data file identifiers associated with the first event record as being part of invalid data file set <NUM>. For example, data file set determiner <NUM> may read the output data file identifier field of the first event record (as described above with reference to <FIG>) and determine whether any output data file identifiers are specified therein. If such output data file identifiers are specified therein, data file set determiner <NUM> designates such output data file identifiers as being part of invalid data file set <NUM>.

The following step <NUM> is performed for a second event record in the ordered sequence that follows the one or more first records in the ordered sequence. At step <NUM>, a determination is made that a data inconsistency exists with respect to the table based on one or more of the valid data file set, the invalid data file set, and one or more of the set of input data file identifiers associated with the second event record and the set of output data file identifiers associated with the second event record. For example, with reference to <FIG>, consistency checker <NUM> may obtain the second event record from even record obtainer <NUM>. Consistency checker <NUM> determines that a data inconsistency exists with respect to the table based on valid data file set <NUM>, invalid data file set <NUM>, the set of input data file identifiers associated with the second event record, and/or the set of output data file identifiers associated with the second event record. Consistency checker <NUM> may determine the set of input data file identifiers and the set of output data file identifiers by reading the input data file identifier field and the output data input data file identifier field of the second event record. As will be described below with reference to <FIG>, consistency checker <NUM> determines that a data inconsistency exits with respect to the table based on an application of a data consistency rule of data consistency rules <NUM>.

<FIG> shows a flowchart <NUM> of a method for determining that a data inconsistency exists in accordance with an example embodiment. In an embodiment, flowchart <NUM> may be implemented by data consistency engine <NUM> shown in <FIG>, although the method is not limited to that implementation. Accordingly, flowchart <NUM> will be described with reference to <FIG>. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the discussion regarding flowchart <NUM> and system <NUM> of <FIG>.

Flowchart <NUM> begins with step <NUM>. At step <NUM>, based on the operation type of the operation associated with the second event record, a data consistency rule is selected from a plurality of data consistency rules. For example, with reference to <FIG>, consistency checker <NUM> may read the operation type field of the second event record (as described above with reference to <FIG>) and determines the operation type. Consistency checker <NUM> selects a data consistency rule from data consistency rules <NUM> that is associated with the operation type.

At step <NUM>, the selected data consistency rule is applied with respect to one or more of the valid data file set, the invalid data file set, and one or more of the set of input data file identifiers associated with the second event record and the set of output data file identifiers associated with the second event record. For example, with reference to <FIG>, data consistency checker <NUM> applies the selected data consistency rule with respect to valid data file set <NUM>, invalid data file set <NUM>, the set of input data file identifiers associated with the second event record and/or the set of output data file identifiers associated with the second event record. Consistency checker <NUM> may read the input data file identifier field and the output data file identifier field of the second event record to determine the set of input data file identifiers and the set of output data file identifiers.

At step <NUM>, based on the application of the selected data consistency rule, a determination is made as to whether a data inconsistency exists with respect to one or more data files identified by one or more of the set of input data file identifiers associated with the second event record or the set of output data file identifiers associated with the second event record. For example, with reference to <FIG>, consistency checker <NUM> determines whether a data inconsistency exits with respect to one or more data files identified by one or more of the set of input data file identifiers associated with the second event record or the set of output data file identifiers associated with the second event record.

At step <NUM>, in response to determining that a data inconsistency exists, an automatic remediation is performed with respect to the one or more data files identified by one or more of the set of input data file identifiers associated with the second event record or the set of output data file identifiers associated with the second event record. For example, with reference to <FIG>, consistency checker <NUM> performs an automatic remediation with respect to the one or more data files identified by one or more of the set of input data file identifiers associated with the second event record or the set of output data file identifiers associated with the second event record.

In accordance with one or more embodiments, the automatic remediation comprises one of recovering the one or more data files, identified by one or more of the set of input data file identifiers associated with the second event record or the set of output data file identifiers associated with the second event record, from a backup of the table; or removing the one or more data files, identified by one or more of the set of input data file identifiers associated with the second event record or the set of output data file identifiers associated with the second event record at least one of the first data file or the second data file, from the table. For example, with reference to <FIG>, consistency checker <NUM> may send a command to transaction manager <NUM> (as shown in <FIG>) that causes transaction manager <NUM> to issue a command that recovers the one or more data files, identified by one or more of the set of input data file identifiers associated with the second event record or the set of output data file identifiers associated with the second event record, from a backup of the table, or removes the one or more data files, identified by one or more of the set of input data file identifiers associated with the second event record or the set of output data file identifiers associated with the second event record at least one of the first data file or the second data file, from the table.

At step <NUM>, a determination is made as to whether a data consistency exists with respect to the table based on another event record. For example, with reference to <FIG>, consistency checker <NUM> may perform steps <NUM>, <NUM>, and <NUM> with respect to another event record in the ordered sequence that follows the second event record.

In accordance with one or more embodiments, the operation associated with the second event record is one of a merge operation configured to merge data files identified by the set of input data file identifiers associated with the second event record or a re-cluster operation configured to re-arrange data files identified by the set of input data file identifiers associated with the second event record. <FIG> shows a flowchart <NUM> of a method for determining that a data consistency exists based on a merge or re-cluster operation in accordance with an example embodiment. The method is performed in accordance with the data consistency rule selected as result of the operation being a merge operation. In an embodiment, flowchart <NUM> may be implemented by data consistency engine <NUM> shown in <FIG>, although the method is not limited to that implementation. Accordingly, flowchart <NUM> will be described with reference to <FIG>. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the discussion regarding flowchart <NUM> and system <NUM> of <FIG>.

Flowchart <NUM> begins with step <NUM>. At step <NUM>, a determination is made as to whether the data files identified by the set of input data file identifiers associated with the second event record are included the valid data file set. If a determination is made that the data files identified by the set of input data file identifiers associated with the second event record are included in the valid data file set, flow continues to step <NUM>. Otherwise (e.g., if the data files identified by the set of input data file identifiers are not included in the valid data file set or included in the invalid data file set), flow continues to step <NUM>. For example, with reference to <FIG>, consistency checker <NUM> may read the input data file identifier field of the second event record to determine the input data file identifiers for the data files. Consistency checker <NUM> may compare the determined input data file identifiers to the input data file identifiers included in valid data file set <NUM> to determine whether the data files identified by the set of input data file identifiers associated with the second event record are included valid data file set <NUM>.

At step <NUM>, a determination is made that no data inconsistency exists with respect to the data files identified by the set of input data file identifiers. For example, with reference to <FIG>, consistency checker <NUM> determines that no data inconsistency exists with respect to the data files identified by the set of input data file identifiers.

At step <NUM>, a determination is made that a data inconsistency exists with respect to the at least one of the data files identified by the set of input data file identifiers. For example, with reference to <FIG>, consistency checker <NUM> determines that a data inconsistency exists with respect to the at least one of the data files identified by the set of input data file identifiers.

In accordance with one or more embodiments, the operation associated with the second event record is a garbage collection operation configured to remove a data file, identified by the set of input data file identifiers associated with the second event record, from the table. <FIG> shows a flowchart <NUM> of a method for determining that a data consistency exists based on a garbage collection operation in accordance with an example embodiment. The method is performed in accordance with the data consistency rule selected as result of the operation being a garbage collection operation. In an embodiment, flowchart <NUM> may be implemented by data consistency engine <NUM> shown in <FIG>, although the method is not limited to that implementation. Accordingly, flowchart <NUM> will be described with reference to <FIG>. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the discussion regarding flowchart <NUM> and system <NUM> of <FIG>.

Flowchart <NUM> begins with step <NUM>. At step <NUM>, a determination is made as to whether the data file identified by the set of input data file identifiers associated with the second event record are included the invalid data file set. If a determination is made that the data file identified by the set of input data file identifiers associated with the second event record are included in the invalid data file set, flow continues to step <NUM>. Otherwise (e.g., if the data file identified by the set of input data file identifiers is not included in the invalid data file set or included in the valid data file set), flow continues to step <NUM>. For example, with reference to <FIG>, consistency checker <NUM> may read the input data file identifier field of the second event record to determine the input data file identifier for the data file. Consistency checker <NUM> may compare the determined input data file identifier to the input data file identifiers included in invalid data file set <NUM> to determine whether the data file identified by the set of input data file identifiers associated with the second event record is included invalid data file set <NUM>.

At step <NUM>, a determination is made that a data inconsistency exists with respect to the data file identified by the set of input data file identifiers associated with the second event record. For example, with reference to <FIG>, consistency checker <NUM> determines that a data inconsistency exists with respect to the data file identified by the set of input data file identifiers associated with the second event record.

In accordance with one or more embodiments, the operation associated with the second event record is a load operation configured to load a data file, identified by the set of output data file identifiers associated with the second event record, from the table. <FIG> shows a flowchart <NUM> of a method for determining that a data consistency exists based on a load operation in accordance with an example embodiment. The method is performed in accordance with the data consistency rule selected as result of the operation being a load operation. In an embodiment, flowchart <NUM> may be implemented by data consistency engine <NUM> shown in <FIG>, although the method is not limited to that implementation. Accordingly, flowchart <NUM> will be described with reference to <FIG>. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the discussion regarding flowchart <NUM> and system <NUM> of <FIG>.

Flowchart <NUM> begins with step <NUM>. At step <NUM>, a determination is made as to whether the data file identified by the set of output data file identifiers associated with the second event record is not included the valid data file set and not included in the invalid data file set. If a determination is made that the data file identified by the set of output data file identifiers associated with the second event record is not included in the valid data file set and not included in the invalid data file set, flow continues to step <NUM>. Otherwise (e.g., if the data file identified by the set of output data file identifiers is included in at least one of the valid data file set or the invalid data file set), flow continues to step <NUM>. For example, with reference to <FIG>, consistency checker <NUM> may read the output data file identifier field of the second event record to determine the output data file identifier for the data file. Consistency checker <NUM> may compare the determined output data file identifier to the output data file identifiers included in valid data file set <NUM> (if any) and invalid data file set <NUM> (if any) to determine whether the data file identified by the set of output data file identifiers associated with the second event record is not included valid data file set <NUM> and invalid data file set <NUM>.

At step <NUM>, a determination is made that no data inconsistency exists with respect to the data file identified by the set of output data file identifiers. For example, with reference to <FIG>, consistency checker <NUM> determines that no data inconsistency exists with respect to the data files identified by the set of output data file identifiers.

At step <NUM>, a determination is made that a data inconsistency exists with respect to the data file identified by the set of output data file identifiers associated with the second event record. For example, with reference to <FIG>, consistency checker <NUM> determines that a data inconsistency exists with respect to the data file identified by the set of output data file identifiers associated with the second event record.

In accordance with one or more embodiments, consistency checker <NUM> may utilize weak data inconsistency rules to determine whether a data consistency exists, for example, in situations in which, data store <NUM> has a finite retention period or there is a possibility of missing events due to failures. <FIG> shows a flowchart <NUM> of a method for determining that a data consistency utilizing various weak data inconsistency rules in accordance with an example embodiment. In an embodiment, flowchart <NUM> may be implemented by data consistency engine <NUM> shown in <FIG>, although the method is not limited to that implementation. Accordingly, flowchart <NUM> will be described with reference to <FIG>. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the discussion regarding flowchart <NUM> and system <NUM> of <FIG>.

Flowchart <NUM> begins with step <NUM>. At step <NUM>, a determination is made as to whether an operation utilizes a data file that was generated from a failed operation. In the event that it is determined that an operation utilizes a data file that was generated from a failed operation, flow continues to step <NUM>. Otherwise, flow continues with step <NUM>. For example, with reference to <FIG>, consistency checker <NUM> may utilize a weak data inconsistency rule of data consistency rules <NUM> that determines whether an operation utilizes a data file that was generated from a failed operation based on an analysis of event records received from event record obtainer <NUM> and valid data file set <NUM> and/or invalid data file set <NUM>.

At step <NUM>, a determination is made as to whether an operation utilizes a data file that was deleted by a previous operation. In the event that it is determined that an operation utilizes a data file that was deleted by a previous operation, flow continues to step <NUM>. Otherwise, flow continues with step <NUM>. For example, with reference to <FIG>, consistency checker <NUM> may utilize a weak data inconsistency rule of data consistency rules <NUM> that determines whether an operation utilizes a data file that was deleted by a previous operation based on an analysis of event records received from event record obtainer <NUM> and valid data file set <NUM> and/or invalid data file set <NUM>.

At step <NUM>, a determination is made as to whether the valid data set includes a data file that was deleted from a garbage collection operation. In the event that it is determined that the valid data set includes a data file that was deleted from a garbage collection operation, flow continues to step <NUM>. Otherwise, flow continues with step <NUM>. For example, with reference to <FIG>, consistency checker <NUM> may utilize a weak data inconsistency rule of data consistency rules <NUM> that determines whether valid data file set <NUM> includes a data file that was deleted from a garbage collection operation.

At step <NUM>, a determination is made as to whether a data file utilized for an operation is included in an invalid data file set. In the event that it is determined that a data file that was utilized for an operation is included in an invalid data file set, flow continues to step <NUM>. Otherwise, flow continues with step <NUM>. For example, with reference to <FIG>, consistency checker <NUM> may utilize a weak data inconsistency rule of data consistency rules <NUM> that determines whether a data file that was utilize for an operation is included in invalid data file set <NUM> based on analysis of event records received from event record obtainer <NUM> and invalid data file set <NUM>.

At step <NUM>, a determination is made that a data inconsistency exists. For example, with reference to <FIG>, consistency checker <NUM> determines that a data inconsistency exists.

At step <NUM>, a determination is made that a data inconsistency does not exist. For example, with reference to <FIG>, consistency checker <NUM> determines that a data inconsistency does not exist.

The systems and methods described above in reference to <FIG>, may be implemented in hardware, or hardware combined with one or both of software and/or firmware. For example, system <NUM> may be used to implement any of nodes 108A-10NB, 112A-112N, and/or 114A-114N, storage node(s) 110A-110N, database server application <NUM>, and data consistency engine <NUM> of <FIG>, database application <NUM>, transaction manager <NUM>, data store <NUM>, nodes <NUM>, <NUM>, <NUM>, and data consistency engine <NUM> of <FIG>, data consistency engine <NUM>, data store <NUM>, event record obtainer <NUM>, data file set determiner <NUM>, consistency checker <NUM>, and data consistency rules <NUM> of <FIG>, and/or any of the components respectively described therein, and/or each of the components described therein, and flowcharts <NUM>, <NUM>, <NUM>, <NUM> and/or <NUM> may be each implemented as computer program code/instructions configured to be executed in one or more processors and stored in a computer readable storage medium. Alternatively, any of nodes 108A-10NB, 112A-112N, and/or 114A-114N, storage node(s) 110A-110N, database server application <NUM>, and data consistency engine <NUM> of <FIG>, database application <NUM>, transaction manager <NUM>, data store <NUM>, nodes <NUM>, <NUM>, <NUM>, and data consistency engine <NUM> of <FIG>, data consistency engine <NUM>, data store <NUM>, event record obtainer <NUM>, data file set determiner <NUM>, consistency checker <NUM>, and data consistency rules <NUM> of <FIG>, and/or any of the components respectively described therein, and/or each of the components described therein, and flowcharts <NUM>, <NUM>, <NUM>, <NUM> and/or <NUM> may be implemented as hardware logic/electrical circuitry. In an embodiment, any of nodes 108A-10NB, 112A-112N, and/or 114A-114N, storage node(s) 110A-110N, database server application <NUM>, and data consistency engine <NUM> of <FIG>, database application <NUM>, transaction manager <NUM>, data store <NUM>, nodes <NUM>, <NUM>, <NUM>, and data consistency engine <NUM> of <FIG>, data consistency engine <NUM>, data store <NUM>, event record obtainer <NUM>, data file set determiner <NUM>, consistency checker <NUM>, and data consistency rules <NUM> of <FIG>, and/or any of the components respectively described therein, and/or each of the components described therein, and flowcharts <NUM>, <NUM>, <NUM>, <NUM> and/or <NUM> may be implemented in one or more SoCs (system on chip). An SoC may include an integrated circuit chip that includes one or more of a processor (e.g., a central processing unit (CPU), microcontroller, microprocessor, digital signal processor (DSP), etc.), memory, one or more communication interfaces, and/or further circuits, and may optionally execute received program code and/or include embedded firmware to perform functions.

<FIG> depicts an exemplary implementation of a computing device <NUM> in which embodiments may be implemented, including any of nodes 108A-10NB, 112A-112N, and/or 114A-114N, storage node(s) 110A-110N, database server application <NUM>, and data consistency engine <NUM> of <FIG>, database application <NUM>, transaction manager <NUM>, data store <NUM>, nodes <NUM>, <NUM>, <NUM>, and data consistency engine <NUM> of <FIG>, data consistency engine <NUM>, data store <NUM>, event record obtainer <NUM>, data file set determiner <NUM>, consistency checker <NUM>, and data consistency rules <NUM> of <FIG>, and/or any of the components respectively described therein, and/or each of the components described therein, and flowcharts <NUM>, <NUM>, <NUM>, <NUM> and/or <NUM>. The description of computing device <NUM> provided herein is provided for purposes of illustration, and is not intended to be limiting. Embodiments may be implemented in further types of computer systems, as would be known to persons skilled in the relevant art(s).

A number of program modules may be stored on the hard disk, magnetic disk, optical disk, ROM, or RAM. These programs include operating system <NUM>, one or more application programs <NUM>, other programs <NUM>, and program data <NUM>. Application programs <NUM> or other programs <NUM> may include, for example, computer program logic (e.g., computer program code or instructions) for implementing the systems described above, including the embodiments described above with reference to <FIG>.

Display screen <NUM> may display information, as well as being a user interface for receiving user commands and/or other information (e.g., by touch, finger gestures, a virtual keyboard, by providing a tap input (where a user lightly presses and quickly releases display screen <NUM>), by providing a "touch-and-hold" input (where a user touches and holds his finger (or touch instrument) on display screen <NUM> for a predetermined period of time), by providing touch input that exceeds a predetermined pressure threshold, etc.).

As used herein, the terms "computer program medium," "computer-readable medium," and "computer-readable storage medium" are used to generally refer to physical hardware media such as the hard disk associated with hard disk drive <NUM>, removable magnetic disk <NUM>, removable optical disk <NUM>, other physical hardware media such as RAMs, ROMs, flash memory cards, digital video disks, zip disks, MEMs, nanotechnology-based storage devices, and further types of physical/tangible hardware storage media (including system memory <NUM> of <FIG>). Communication media typically embodies computer-readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave. Embodiments are also directed to such communication media.

Claim 1:
A computer-implemented method for consistency checking of data files, in a distributed database system, that represent a table, comprising:
obtaining (<NUM>) an ordered sequence of event records (<NUM>) associated with the table, each event record in the ordered sequence including information about a particular operation performed with respect to one or more of the data files, the information for the particular operation including a transaction version, an operation type, a set of input data file identifiers, a set of output data file identifiers, and an operation status;
performing the following for each of one or more first event records in the ordered sequence, in the order specified by the ordered sequence:
determining (<NUM>) whether the operation associated with the first event record was successful or unsuccessful based on the operation status associated with the first event record;
in response to determining that the operation associated with the first event record was successful, designating (<NUM>) any data file identifier in the set of output data file identifiers associated with the first event record as being part of a valid data file set (<NUM>); and
in response to determining that the operation associated with the first event record was unsuccessful, designating (<NUM>) any data file identifier in the set of output data file identifiers associated with the first event record as being part of an invalid data file set (<NUM>); and
performing the following for a second event record in the ordered sequence that follows the one or more first records in the ordered sequence:
determining (<NUM>) that a data inconsistency exists with respect to the table based on one or more of the valid data file set, the invalid data file set, and one or more of the set of input data file identifiers associated with the second event record and the set of output data file identifiers associated with the second event record.