# US 12,001,314 B2 · Transaction validator

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,001,314 B2
- Document ID: US12001314B2
- Status: Granted
- Kind: B2
- Application number: 17/666,693
- Filed: 2022-02-08
- Published: 2023-03-02
- Granted: 2024-06-04
- Earliest claimed: 2021-08-20
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: Adam Dickinson; James Corbett
- Web page: https://patentgrep.com/patent/US12001314B2

## CPC

- G06F 11/3612: {by runtime analysis (performance monitoring G06F11/3466)}
- G06F 9/466: {Transaction processing}
- G06F 11/3688: {for test execution, e.g. scheduling of test suites}
- G06F 11/3692: {for test results analysis}
- G06F 16/213: {with details for schema evolution support}
- G06F 16/2358: {Change logging, detection, and notification (replication G06F16/27)}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Randomized testing can be used to explore a set of possible transactions, schemas, and system states, including partionings, which can exist in a distributed database. The tests can be complementary to other system failure, performance, and version compatibility tests. Randomly generated transactions can be computed or evaluated at a transactor and compared to results derived from a transactor emulator.

## Claims

### Claim 1

A method to test a transactor in a distributed database, the method comprising:
generating a first transaction defining actions related to the distributed database;
transacting the first transaction at the transactor;
logging in a log information resulting from transacting the first transaction;
generating an equivalent transaction based on the information in the log;
transacting the equivalent transaction in a transactor emulator to generate transaction results; and
comparing the information resulting from transacting the first transaction and the transaction results from the equivalent transaction to verify the execution of the transaction by the transactor.

### Claim 2 (depends on 1)

The method of claim 1 wherein generating the first transaction or the equivalent transaction includes using a seed to generate the first transaction or the equivalent transaction.

### Claim 3 (depends on 2)

The method of claim 2 wherein the seed comprises a workid and operation number.

### Claim 4 (depends on 1)

The method of claim 1 wherein a timestamp is associated with logging the information resulting from transacting the first transaction.

### Claim 5 (depends on 1)

The method of claim 1 wherein a schema change is included in the first transaction.

### Claim 6 (depends on 5)

The method of claim 5 wherein transacting schema changes are logged in a second log.

### Claim 7 (depends on 1)

The method of claim 1 wherein the first transaction is represented in database mutation language.

### Claim 8 (depends on 1)

The method of claim 1 wherein a plurality of transactions are transacted by the transactor and a plurality of equivalent transactions are transacted by the transactor emulator.

### Claim 9 (depends on 8)

The method of claim 8 wherein the ordering of the processing the plurality of transactions is non-deterministic.

### Claim 10 (depends on 1)

The method of claim 1 further comprising injecting system faults into the first transaction during the transacting or generating of the first transaction.

### Claim 11 (depends on 10)

The method of claim 10 wherein the system faults can be any one of process crashes, file errors, corruptions, remote procedure call (RPC) delays, RPC errors, or unavailability of a server or datacenter.

### Claim 12 (depends on 1)

The method of claim 1 wherein comparison of the results requires an exact match for verification of the transactor.

### Claim 13 (depends on 1)

The method of claim 1 wherein multiple results from the transactor emulator can verify the transactor.

### Claim 14 (depends on 1)

The method of claim 1 wherein the transacting the equivalent transaction occurs on a stand-alone device.

### Claim 15 (depends on 1)

The method of claim 1 wherein transacting the equivalent transaction utilizes a database partition.

### Claim 16 (depends on 15)

The method of claim 15 wherein the database partition is based on the first transaction.

### Claim 17 (depends on 1)

The method of claim 1, wherein the first transaction is generated by the transactor or a transaction generator.

### Claim 18

A system comprising:
a network, the network including a distributed database on one or more nodes of the network;
a transactor configured to execute on one or more nodes of the network, wherein the transactor is further configured to:
generate a first transaction defining actions related to the distributed database;
process the first transaction; and
a computing device comprising a-one or more processors coupled to memory, wherein the computing device is configured to run a transactor emulator,
wherein the transactor emulator is configured to:
process an equivalent transaction,
compare information from resulting from processing the first transaction and transaction results from processing the equivalent transaction to verify the execution of the first transaction by the transactor.

### Claim 19 (depends on 18)

The system of claim 18 wherein the computing device is not a node of the network.

### Claim 20

One or more non-transitory computer readable medium containing instructions, the instructions when run configured to perform the steps of:
generating a first transaction defining actions related to the distributed database;
transacting the first transaction at a transactor;
logging in a log information resulting from transacting the first transaction;
generating an equivalent transaction based on the information in the log;
transacting the equivalent transaction in a transactor emulator to generate transaction results; and
comparing the information resulting from transacting the first transaction and the transaction results from the equivalent transaction to verify the execution of the transaction by the transactor.