Method and system for highly-parallel logging and recovery operation in main-memory transaction processing systems

A transaction processing system allowing logging updates and recovering from failure, comprising:

• a main memory for storing a database;
• one or more persistent log storage devices for storing log records;
• one or more persistent backup storage devices for storing a copy of the database in the main memory;
• means for generating a differential log record using Δt=bt−1 ⊕ bt where Δt is the differential log record generated for the t-th update on a database object b, bt−1 is the before-update image and bt is the after-update image, and ⊕ is the bit-wise XOR operation;
• and
• means for replaying the differential log records in an arbitrary order, independent of their generation order, by using the bit-wise XOR operations,
• wherein said means for replaying further comprises:
• means for redoing committed transactions using bs+p=bs ⊕ Δ(1) ⊕ Δ(2) . . . ⊕ Δ(p), wherein bs is the image of a database object b after s number of updates are reflected, bs+p is the image of b rolled forward from bs by p number of updates involved in committed transactions, and ⊕ is the bit-wise XOR operation, where the sequence of the differential log records applied, Δ(1) through Δ(p), is any possible arrangement of the set of sequentially-generated differential log records {Δs+1, . . . , Δs+p−1, Δs+p} in the order independent from the order of log creation;
• and
• means for undoing uncommitted transactions using bs−q=bs ⊕ Δ(1) ⊕ Δ(2) . . . ⊕ Δ(q), wherein bs is the image of a database object b after s number of updates are reflected, bs−q is the image of b rolled backward from bs by q number of updates involved in uncommitted transactions, and ⊕ is the bit-wise XOR operation, where the sequence of the differential log records applied, Δ(1) through Δ(q), is any possible arrangement of the set of sequentially-generated differential log records {Δs−q+1, Δs−q+2, . . . , Δs} in the order independent from the order of log creation.

A computer-readable storage medium that contains a program for logging updates and recovering from failure in a transaction-processing system having a main memory for storing a database, one or more persistent backup storage devices for storing a copy of the database in the main memory, and one or more persistent log storage devices for storing log records, where the program under the control of a CPU performs:

• generating differential log records by using Δt=bt−1 ⊕ bt, where Δt is the differential log record generated for the t-th update on a database object b, bt−1 is the before-update image and bt is the after-update image, and ⊕ is the bit-wise XOR operation;
• replaying the differential log records in an arbitrary order, independent of their generation order, by using the bit-wise XOR operations,
• wherein replaying the differential log records further comprises:
• redoing committed transactions using bs+p=bs ⊕ Δ(1) ⊕ Δ(2) . . . ⊕ Δ(p), wherein bs is the image of a database object b after s number of updates are reflected, bs+p is the image of b rolled forward from bs by p number of updates involved in committed transactions, and ⊕ is the bit-wise XOR operation, where the sequence of the differential log records applied, Δ(1) through Δ(p), is any possible arrangement of the set of sequentially-generated differential log records {Δs+1, . . . , Δs+p−1, Δs+p} in the order independent from the order of log creation;
• and
• undoing uncommitted transactions using bs−q=bs ⊕ Δ(1) ⊕ Δ(2) . . . ⊕ Δ(q), wherein bs is the image of a database object b after s number of updates are reflected, bs−q is the image of b rolled backward from bs by q number of updates involved in uncommitted transactions, and ⊕ is the bit-wise XOR operation, where the sequence of the differential log records applied, Δ(1) through Δ(q), is any possible arrangement of the set of sequentially-generated differential log records {Δs−q+1, Δs−q+2, . . . , Δs} in the order independent from the order of log creation.