# US 2014/0195492 A1 · Systems, methods, and apparatuses for fixing logical or physical corruption in databases using lsm trees

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

- Number: US 2014/0195492 A1
- Document ID: US20140195492A1
- Status: Published application
- Kind: A1
- Application number: 14/210,217
- Filed: 2014-03-13
- Published: 2014-07-10
- Earliest claimed: 2012-12-19
- Assignees: salesforce.com, inc.
- Inventors: Mark Wilding
- Web page: https://patentgrep.com/patent/US20140195492A1

## CPC

- G06F 11/1474: in transactions (updating of structured data in databases G06F16/23)
- G06F 11/1471: involving logging of persistent data for recovery
- G06F 16/215: Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F 2201/80: Database-specific techniques
- G06F 2201/805: Real-time
- G06F 2201/82: Solving problems relating to consistency
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

In accordance with disclosed embodiments, there are provided methods, systems, and apparatuses for fixing logical or physical corruption in databases using LSM trees including, for example, means for storing records in a LSM database at the host organization; processing transactions to the LSM database by writing the transactions into immutable extents for subsequent merge into the LSM database; recording a history of the transactions in a log; identifying corruption in at least one of the records of the LSM database represented within the immutable extents prior to use of the immutable extents in the LSM database; and correcting the identified corruption to the at least one of the records of the LSM database based at least in part on the recorded history of the transactions in the log during live operation of the LSM database. Other related embodiments are disclosed.

## Claims

### Claim 1

A method in a host organization having a processor and a memory therein, wherein the method comprises:
storing records in a LSM database at the host organization;
processing transactions to the LSM database by writing the transactions into immutable extents for subsequent merge into the LSM database;
recording a history of the transactions in a log;
identifying corruption in at least one of the records of the LSM database represented within the immutable extents prior to use of the immutable extents in the LSM database; and
correcting the identified corruption to the at least one of the records of the LSM database based at least in part on the recorded history of the transactions in the log during live operation of the LSM database.

### Claim 2 (depends on 1)

The method of claim 1, wherein correcting the identified corruption to the at least one of the records of the LSM database comprises at least one of:
restoring a modified record to a prior state;
deleting an erroneously inserted record;
restoring an erroneously deleted record; and
changing one or more field values of an erroneously modified record.

### Claim 3 (depends on 1)

The method of claim 1:
wherein the corruption constitutes logical corruption; and
wherein correcting the identified logical corruption to the at least one of the records of the LSM database comprises:
reading a stored record from the LSM database having a corresponding transaction pending merge processing within the immutable extents;
reading historical transaction data from the log;
generating a compensating transaction based on the compensating transaction data from the log and the stored record from the LSM database; and
sending the compensating transaction to the LSM database.

### Claim 4 (depends on 3)

The method of claim 3, wherein sending the compensating transaction to the LSM database comprises:
issuing the compensating transaction to the LSM database as a new transaction, wherein the new transaction is written to a transaction log of the LSM database when committed and remains within the transaction log until the LSM database generates a new top level extent through a flush of the transaction log to generate the new top level extent; and
wherein subsequent merge processing counteracts the corresponding transaction pending merge processing within the immutable extents for the stored record read from the LSM database.

### Claim 5 (depends on 1)

The method of claim 1:
wherein the corruption constitutes physical corruption within one of a top level extent at the top level of the LSM database or within a previously merged extent at a subordinate level of the LSM database; and
wherein correcting the identified physical corruption comprises one of:
(a) generating a new top level extent for the top level of the LSM database from the transaction logs and replacing the top level extent determined to have physical corruption with the new top level extent generated, or
(b) generating a new subordinate level extent by re-merging previously merged extents marked for deletion from the LSM tree but kept for redundancy and replacing the previously merged extent at a subordinate level determined to have physical corruption with the new subordinate level extent generated.

### Claim 6 (depends on 1)

The method of claim 1, wherein identifying corruption in at least one of the records of the LSM database comprises:
triggering error messages to users for any queries to the LSM database having the identified corruption within the query claim scope; and
maintaining availability and accessibility to the LSM database to database queries.

### Claim 7 (depends on 1)

The method of claim 1:
wherein the corruption constitutes logical corruption; and
wherein the method further comprises presenting a historical records view to a user interface based on the log, the historical records view displaying one or more records updated during a time range configurable at the user interface.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
receiving user input selecting one or more of the records updated during the time range; and
receiving user input specifying edits to rectify the logical corruption in the one or more records.

### Claim 9 (depends on 8)

The method of claim 8, wherein the user input specifying edits to rectify the logical corruption in the one or more records comprises user input specifying one or more of:
a selected record erroneously inserted into the LSM database to be deleted from the LSM database via a compensating delete transaction;
a selected record erroneously deleted from the LSM database to be restored to the LSM database via a compensating insert transaction;
a selected record erroneously modified within the LSM database to be reverted to a prior state via a compensating update transaction; and
a selected record erroneously modified within the LSM database to be updated to a new state via a compensating update transaction.

### Claim 10 (depends on 7)

The method of claim 7, further comprising:
presenting a preview of other records affected by a proposed compensating transaction to the user interface prior to proceeding with the proposed compensating transaction.

### Claim 11 (depends on 7)

The method of claim 7, further comprising:
storing an Organization Identifier (OrgID) and a User Identifier (UserID) within the recorded history of the transactions in the log, the OrgID and UserID identifying which organization and which user is associated with every transaction recorded; and
wherein presenting the historical records view to the user interface comprises restricting the historical records displayed based on an evaluation of the OrgID and the UserID stored in the log and access rights associated with a user of the user interface.

### Claim 12 (depends on 1)

The method of claim 1, further comprising:
receiving a selection from the user interface specifying one of the displayed records updated during the time range;
presenting a record editor to the user interface having the record corresponding to the selection populated therein;
receiving user input to the fields of the record corresponding to the selection from the record editor at the user interface; and
generating a compensating transaction for the record corresponding to the selection using the user input to the fields of the record.

### Claim 13 (depends on 1)

The method of claim 1:
wherein the host organization implements the method via computing architecture of the host organization including at least the processor and the memory;
wherein a user interface operates at a user client device remote from the host organization and communicatively interfaces with the host organization via a public Internet; and
wherein the host organization operates as a cloud based service provider to the user client device.

### Claim 14 (depends on 11)

The method of claim 11, wherein the host organization provides a multi-tenant database system via the LSM database and the computing architecture of the host organization, the multi-tenant database system having elements of hardware and software that are shared by a plurality of separate and distinct customer organizations, each of the separate and distinct customer organizations being remotely located from the host organization.

### Claim 15 (depends on 1)

The method of claim 1, wherein identifying corruption in at least one of the records of the LSM database comprises one of:
identifying physical corruption responsive to a physical corruption error triggered by the LSM database; and
identifying logical corruption responsive user input at a logical corruption user interface, the user input indicating a selected record is to be corrected via a compensating transaction.

### Claim 16

Non-transitory computer readable storage media having instructions stored thereon that, when executed by a processor in a host organization, the instructions cause the host organization to perform operations comprising:
storing records in a LSM database at the host organization;
processing transactions to the LSM database by writing the transactions into immutable extents for subsequent merge into the LSM database;
recording a history of the transactions in a log;
identifying corruption in at least one of the records of the LSM database represented within the immutable extents prior to use of the immutable extents in the LSM database; and
correcting the identified corruption to the at least one of the records of the LSM database based at least in part on the recorded history of the transactions in the log during live operation of the LSM database.

### Claim 17 (depends on 16)

The non-transitory computer readable storage media of claim 16, wherein correcting the identified corruption to the at least one of the records of the LSM database comprises at least one of:
restoring a modified record to a prior state;
deleting an erroneously inserted record;
restoring an erroneously deleted record; and
changing one or more field values of an erroneously modified record.

### Claim 18 (depends on 16)

The non-transitory computer readable storage media of claim 16:
wherein the corruption constitutes logical corruption; and
wherein correcting the identified logical corruption to the at least one of the records of the LSM database comprises:
reading a stored record from the LSM database having a corresponding transaction pending merge processing within the immutable extents;
reading historical transaction data from the log;
generating a compensating transaction based on the compensating transaction data from the log and the stored record from the LSM database; and
sending the compensating transaction to the LSM database.

### Claim 19 (depends on 16)

The non-transitory computer readable storage media of claim 16:
wherein the corruption constitutes logical corruption; and
wherein the instructions cause the processor to perform further operations comprising:
presenting a historical records view to a user interface based on the log, the historical records view displaying one or more records updated during a time range configurable at the user interface;
receiving user input selecting one or more of the records updated during the time range;
receiving user input specifying edits to rectify the logical corruption in the one or more records, wherein the user input specifies one or more of:
a selected record erroneously inserted into the LSM database to be deleted from the LSM database via a compensating delete transaction;
a selected record erroneously deleted from the LSM database to be restored to the LSM database via a compensating insert transaction;
a selected record erroneously modified within the LSM database to be reverted to a prior state via a compensating update transaction; and
a selected record erroneously modified within the LSM database to be updated to a new state via a compensating update transaction.

### Claim 20

A system comprising:
a processor and a memory to execute instructions at the system;
an LSM database to store records;
a query interface to process transactions to the LSM database by writing the transactions into immutable extents for subsequent merge into the LSM database;
a log to record a history of the transactions;
a logical corruption locator to identify logical corruption in at least one of the records of the LSM database represented within the immutable extents prior to use of the immutable extents in the LSM database; and
a logical corruption editor to correct the identified logical corruption to the records of the LSM database based at least in part on the recorded history of the transactions in the log during live operation of the LSM database.

### Claim 21 (depends on 20)

The system of claim 20, further comprising:
a historical record viewer engine to present a historical records view to a user interface based on the log, the historical records view to display one or more records updated during a time range configurable at the user interface.

### Claim 22 (depends on 21)

The system of claim 21, further comprising:
a logical corruption user interface engine to receive user input selecting one or more of the records updated during the time range; and
the logical corruption user interface engine to further receive user input specifying edits to rectify the logical corruption in the one or more records.

### Claim 23 (depends on 22)

The system of claim 22, further comprising:
a web-server to implement the historical record viewer engine and to receive the user input at the system from a client device operating at one of a plurality of customer organizations remote from the system;
wherein the plurality of customer organizations communicably interface with the system via a public Internet; and
wherein each customer organization is an entity selected from the group consisting of: a separate and distinct remote organization, an organizational group within the host organization, a business partner of the host organization, or a customer organization that subscribes to cloud computing services provided by the host organization.

### Claim 24 (depends on 20)

The system of claim 20:
wherein a user interface operates at a user client device remote from the system and communicatively interfaces with the system via a public Internet;
wherein the system operates at a host organization as a cloud based service provider to the user client device; and
wherein the cloud based service provider hosts the customer data within a multi-tenant database system at a host organization on behalf of the user.