Systems, methods, and apparatuses for fixing logical or physical corruption in databases using LSM trees

• US 9,875,164 B2
• Filed: 02/22/2017
• Issued: 01/23/2018
• Est. Priority Date: 12/19/2012
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Wilding, Mark
• Primary Examiner(s): VO, TRUONG V
• Application Number:
  US15/438,961
• Publication Number:
  US 20170161159A1
• Time in Patent Office: 335 Days
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064

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

1. A method in a host infrastructure having a processor and a memory therein, wherein the method comprises:

causing records to be stored in a log-structured merge (LSM) storage;

writing transactions to a transaction log and then flushing at least a portion of the transaction log to cause the at least the portion of the transaction log to be stored into one or more extents in the LSM storage, wherein the transactions are updates to, deletions of, or creation of records;

writing, upon receiving an identification of corruption in at least one of the transactions or the records of the LSM storage, a compensating transaction to the transaction log, wherein the compensating transaction data is usable to restore the at least one of the corrupted transactions or the corrupted records; and

flushing the compensating transaction into a newest top level extent in the LSM storage.

2. The method of claim 1, wherein the flushing does not replace any previously-existing pre-merge extent.

3. The method of claim 1, wherein the flushing further comprises applying the compensating transaction via an application program interface.

4. The method of claim 1, further comprising notifying a user when the causing the records to be stored is an extraordinary transaction.

5. The method of claim 4, wherein the causing the records to be stored is an extraordinary transaction when at least one of:

one or more edits to the records are made outside of normal business hours;

the one or more edits to the records originate from a location which does not match prior usage;

the one or more edits to the records originate from a location which does not match expected usage;

the one or more edits to the records originate from an IP address which does not match prior usage;

or

the one or more edits to the records originate from an IP address which does not match expected usage.

6. The method of claim 1, further comprising identifying corruption in at least one of the records of the LSM storage by triggering error messages to users for any queries to the LSM storage having a corrupted transaction or a corrupted record within the scope of the query.

7. The method of claim 1, wherein the corruption constitutes logical corruption;

and further comprising presenting a historical records view to a user interface based on the transaction log, the historical records view displaying one or more corrupted records updated during a time range configurable at the user interface.

8. The method of claim 7, further comprising:

receiving a first user input selecting one or more of the corrupted records updated during the time range; and

receiving a second user input specifying one or more edits to rectify the logical corruption in the one or more corrupted records.

9. 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.

10. 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 transaction log, the OrgID and UserID identifying which infrastructure 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 based on access rights associated with a user of the user interface.

11. The method of claim 7, further comprising:

receiving a selection from the user interface specifying one of the displayed corrupted records updated during the time range;

presenting a record editor to the user interface having the corrupted record corresponding to the selection populated therein;

receiving user input to the fields of the corrupted record corresponding to the selection from the record editor at the user interface; and

generating a compensating transaction for the corrupted record corresponding to the selection using the user input to the fields of the record.

12. The method of claim 1, wherein the host infrastructure implements the method via computing architecture of the host infrastructure including at least the processor and the memory, a user interface operates at a user client device located remotely from the host infrastructure and communicatively interfaces with the host infrastructure via a public Internet, and the host infrastructure operates as a cloud-based service provider to the user client device.

13. The method of claim 1, wherein the host infrastructure provides a multi-tenant database system via the LSM storage and the computing architecture of the host infrastructure, the multi-tenant database system has elements of hardware and software which are shared by a plurality of separate and distinct customer infrastructures, and each of the separate and distinct customer infrastructures is remotely located from the host infrastructure.

14. The method of claim 1, further comprising identifying corruption in at least one of the records of the LSM storage by identifying logical corruption in response to user input at a logical corruption user interface, the user input indicating that a selected record is to be corrected via a compensating transaction.

15. Non-transitory computer readable storage media having instructions stored thereon which, when executed by a processor in a host infrastructure, cause the host infrastructure to perform operations, comprising:

causing records to be stored in a log-structured merge (LSM) storage;

writing transactions to a transaction log and then flushing at least a portion of the transaction log to cause the at least the portion of the transaction log to be stored into one or more extents in the LSM storage, wherein the transactions are updates to, deletions of, or creation of records;

writing, upon receiving an identification of corruption in at least one of the transactions or the records of the LSM storage, a compensating transaction to the transaction log, wherein the compensating transaction data is usable to restore the at least one of the corrupted transactions or the corrupted records; and

flushing the compensating transaction into a newest top level extent in the LSM storage.

16. The non-transitory computer readable storage media of claim 15, wherein the flushing does not replace any previously-existing pre-merge extent.

17. The non-transitory computer readable storage media of claim 15, wherein the flushing further comprises applying the compensating transaction via an application program interface.

18. The non-transitory computer readable storage media of claim 15, wherein the instructions cause the processor to perform further operations comprising:

notifying a user when the causing the records to be stored is an extraordinary transaction.

19. The non-transitory computer readable storage media of claim 18, wherein the causing the records to be stored is an extraordinary transaction when at least one of:

one or more edits to the records are made outside of normal business hours;

the one or more edits to the records originate from a location which does not match prior usage;

the one or more edits to the records originate from a location which does not match expected usage;

the one or more edits to the records originate from an IP address which does not match prior usage;

or

the one or more edits to the records originate from an IP address which does not match expected usage.

20. The non-transitory computer readable storage media of claim 15, wherein the instructions cause the processor to perform further operations comprising:

identifying corruption in at least one of the records of the LSM storage by triggering error messages to users for any queries to the LSM storage having a corrupted transaction or a corrupted record within the scope of the query.

21. The non-transitory computer readable storage media of claim 15, wherein the corruption constitutes logical corruption;

and further comprising presenting a historical records view to a user interface based on the transaction log, the historical records view displaying one or more corrupted records updated during a time range configurable at the user interface.

22. The non-transitory computer readable storage media of claim 21, wherein the instructions cause the processor to perform further operations comprising:

receiving a first user input selecting one or more of the corrupted records updated during the time range; and

receiving a second user input specifying one or more edits to rectify the logical corruption in the one or more corrupted records.

23. The non-transitory computer readable storage media of claim 21, wherein the instructions cause the processor to perform further operations 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.

24. The non-transitory computer readable storage media of claim 21, wherein the instructions cause the processor to perform further operations comprising:

storing an Organization Identifier (OrgID) and a User Identifier (UserID) within the recorded history of the transactions in the transaction log, the OrgID and UserID identifying which infrastructure and which user is associated with every transaction recorded,

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 based on access rights associated with a user of the user interface.

25. The non-transitory computer readable storage media of claim 21, wherein the instructions cause the processor to perform further operations comprising:

receiving a selection from the user interface specifying one of the displayed corrupted records updated during the time range;

presenting a record editor to the user interface having the corrupted record corresponding to the selection populated therein;

receiving user input to the fields of the corrupted record corresponding to the selection from the record editor at the user interface; and

generating a compensating transaction for the corrupted record corresponding to the selection using the user input to the fields of the record.

26. The non-transitory computer readable storage media of claim 15, wherein the host infrastructure implements the method via computing architecture of the host infrastructure including at least the processor and the memory, a user interface operates at a user client device located remotely from the host infrastructure and communicatively interfaces with the host infrastructure via a public Internet, and the host infrastructure operates as a cloud-based service provider to the user client device.

27. The non-transitory computer readable storage media of claim 15, wherein the host infrastructure provides a multi-tenant database system via the LSM storage and the computing architecture of the host infrastructure, the multi-tenant database system has elements of hardware and software which are shared by a plurality of separate and distinct customer infrastructures, and each of the separate and distinct customer infrastructures is remotely located from the host infrastructure.

28. The non-transitory computer readable storage media of claim 15, wherein the instructions cause the processor to perform further operations comprising:

identifying corruption in at least one of the records of the LSM storage by identifying logical corruption in response to user input at a logical corruption user interface, the user input indicating a selected record is to be corrected via a compensating transaction.

29. A system, comprising:

a log-structured merge (LSM) storage configured to store records;

a query interface configured to write transactions to a transaction log and then flush at least a portion of the transaction log to cause the at least the portion of the transaction log to be stored into one or more extents in the LSM storage, wherein the transactions are updates to, deletions of, or creation of records;

a transaction log configured to record a history of the transactions;

a logical corruption locator configured to locate logical corruption in at least one of the transactions or the records of the LSM storage; and

a logical corruption editor configured to;

write, upon receiving an identification of corruption in at least one of the transactions or the records of the LSM storage, a compensating transaction to the transaction log, wherein the compensating transaction data is usable to restore the at least one of the corrupted transactions or the corrupted records; and

flush the compensating transaction into a newest top level extent in the LSM storage.

30. The system of claim 29, further comprising a historical record viewer engine configured to present, based on the transaction log, a historical records view via a user interface, wherein the historical records view displays one or more records updated during a time range configurable at the user interface.

31. The system of claim 30, further comprising a logical corruption user interface engine configured to:

receive a first user input selecting one or more of the corrupted records updated during the time range; and

receive a second user input specifying edits to rectify the logical corruption in the one or more corrupted records.

32. The system of claim 29, further comprising a user interface configured to:

operate at a user client device, wherein the user client device is located remotely from the system; and

communicatively interface with the system via a public Internet,

wherein the system is configured to operate at a host infrastructure as a cloud-based service provider to the user client device, and the cloud-based service provider is configured to host customer data within a multi-tenant database system at the host infrastructure on behalf of the user.