System, Method And Computer Program Product For Managing Caches

• US 20110218971A1
• Filed: 03/08/2010
• Published: 09/08/2011
• Est. Priority Date: 03/08/2010
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Cooper, Brian Frank
• Granted Patent: US 10,275,347 B2
• Time in Patent Office: Days
• US Class Current: 707/689
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 2212/465 Structured object, e.g. database record

Abstract

Methods, systems and computer program products are provided for managing at least one cache for a database. In one method, an operation record is inserted in an operations log for each write operation to the database. The operation record includes a Log Sequence Number (LSN). At least one cache is updated using operation records in the operations log. To update a cache, unapplied operations in the operations log for the cache are identified using an applied LSN associated with the cache. The applied LSN denotes an LSN of a last operation applied to the cache. The unapplied operations are then applied to the cache and the applied LSN is updated with an LSN corresponding to the last unapplied operation of the unapplied operations that were applied to the cache during updating the cache.

Claims

1. A method for managing at least one cache for a database, the method comprising:

inserting an operation record in an operations log for each write operation to the database, wherein the operation record comprises a Log Sequence Number (LSN); and

updating at least one cache, wherein updating a cache comprises;

identifying unapplied operations in the operations log for the cache using an applied LSN associated with the cache, wherein the applied LSN denotes an LSN of a last operation applied to the cache;

applying the unapplied operations to the cache; and

updating the applied LSN with an LSN corresponding to a last unapplied operation of the unapplied operations that were applied to the cache during updating the cache.

2. The method of claim 1, wherein inserting the operation record comprises:

finding a last LSN, wherein the last LSN is the LSN of the most recent operation record in the operations log;

assigning a next LSN to the operation record; and

adding the operation record to the operations log at the next LSN.

3. The method of claim 2 further comprising updating the last LSN to the next LSN.

4. The method of claim 1, wherein identifying the unapplied operations comprises checking whether a last LSN is greater than the applied LSN, wherein the last LSN is the LSN of the most recent operation record in the operations log.

5. The method of claim 1, wherein applying the unapplied operations comprises, for each operation record having LSN greater than the applied LSN:

accessing the operation record from the operations log;

checking whether a data item corresponding to the operation record is stored in the cache; and

when the data item is present in the cache, performing an action associated with the operation record on the data item stored in the cache.

6. The method of claim 5, wherein the action is one of drop, repair and redo.

7. The method of claim 1, further comprising renewing a lease on the applied LSN.

8. The method of claim 1 further comprising, for each access operation to the database for a data item, checking whether an active latch is present on the data item in the database.

9. The method of claim 8, wherein the access operation is a write operation, the method further comprising:

updating the data item in the database;

renewing the active latch, when the active latch is present; and

adding a latch to the data item, when the active latch is not present.

10. The method of claim 9 further comprising updating an expiration time for the latch.

11. The method of claim 8, wherein the access operation is a write operation, the method further comprising, when the active latch is present, delaying the write operation till the latch becomes inactive.

12. The method of claim 8, wherein the access operation is a read operation, the method further comprising issuing a failure message in response to the read operation when the active latch is present.

13. A system for managing at least one cache for a cache, the system comprising:

an insertion module configured to insert an operation record in an operations log for each write operation to the database, wherein the operation record comprises a Log Sequence Number (LSN); and

an update module, coupled to at least one cache, configured to;

identify unapplied operations in the operations log for each cache using an applied LSN associated with the cache, wherein the applied LSN denotes an LSN of a last operation applied to the cache;

apply the unapplied operations to the cache; and

update the applied LSN with an LSN of a last operation in the unapplied operations list of the unapplied operations that were applied to the cache during updating the cache.

14. The system of claim 13 further comprising a lease module configured to renew, for each cache, a lease on the applied LSN.

15. The system of claim 14, wherein the least module is further configured to trigger the update module for each cache on or before expiration of the lease for the cache.

16. The system of claim 13, further comprising a write consistency module configured to:

check, for each write operation to the database for a data item, whether an active latch is present on the data item in the database;

update the data item in the database;

add a latch to the data item when the active latch is not present; and

renew the latch when the active latch is present.

17. The system of claim 13, further comprising a read consistency module configured to:

check, for each read operation to the database for a data item, whether an active latch is present on the data item in the database; and

issue a failure message in response to the read operation, when the active latch is present.

18. The system of claim 13 further comprising a check pointing module configured to delete, from the operations log, one or more operation records that are older than a predefined duration.

19. A computer-readable storage medium encoded with computer-executable instructions for managing at least one cache for a database, the computer- executable instructions, when executed, operable to cause one or more processors to:

insert an operation record in an operations log for each write operation to the database, wherein the operation record comprises a Log Sequence Number (LSN); and

update at least one cache, wherein the computer program product further comprises computer executable instructions operable to cause the one or more processors to;

identify unapplied operations in the operations log for a cache using an applied LSN associated with the cache, wherein the applied LSN denotes an LSN of a last operation applied to the cache;

apply the unapplied operations to the cache; and

update the applied LSN with an LSN corresponding to a last unapplied operation of the unapplied operations that were applied to the cache during updating the cache.

20. The computer program product of claim 19 further comprising computer executable instructions operable to cause the one or more processors to:

find a last LSN, wherein the last LSN is the LSN of the most recent operation record in the operations log;

assign a next LSN to the operation record; and

add the operation record to the operations log.

21. The computer program product of claim 20 further comprising computer executable instructions operable to cause the one or more processors to update the last LSN to the next LSN.

22. The computer program product of claim 19 further comprising computer executable instructions operable to cause the one or more processors to check whether a last LSN is greater than the applied LSN, wherein the last LSN is the LSN of the most recent operation record in the operations log.

23. The computer program product of claim 19 further comprising computer executable instructions operable to cause the one or more processors to:

access an operation record from the operations log having LSN greater than the applied LSN;

check whether a data item corresponding to the operation record is stored in the cache; and

when the data item is present in the cache, perform an action associated with the operation record on the data item stored in the cache.

24. The computer program product of claim 19 further comprising computer executable instructions operable to cause the one or more processors to renew a lease on the applied LSN.

25. The computer program product of claim 19 further comprising computer executable instructions operable to cause the one or more processors to check, for each access operation to the database for a data item, whether an active latch is present on the data item in the database.

26. The computer program product of claim 25, wherein the access operation is a write operation, further comprising computer executable instructions operable to cause the one or more processors to:

update the data item in the database when the active latch is not present;

renew the active latch, when the active latch is present; and

add a latch to the data item, when the active latch is not present.

27. The computer program product of claim 26 further comprising computer executable instructions operable to cause the one or more processors to update an expiration time for the latch.

28. The computer program product of claim 25, wherein the access operation is a write operation, the computer program product further comprising computer executable instructions operable to cause the one or more processors to delay, when the active latch is present, the write operation till the latch becomes inactive.

29. The computer program product of claim 25, wherein the access operation is a read operation, further comprising computer executable instructions operable to cause the one or more processors to issuing a failure message in response to the read operation when the active latch is present.