EFFICIENT ACCESS OF FLASH DATABASES

• US 20080263114A1
• Filed: 04/23/2007
• Published: 10/23/2008
• Est. Priority Date: 04/23/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nath, Suman K., Kansal, Aman
• Granted Patent: US 8,037,112 B2
• Time in Patent Office: Days
• US Class Current: 707/206
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Techniques for efficient access to flash databases are described. In one implementation, a method includes performing an operation on a flash database, supplementing at least one portion of a node translation table corresponding to at least one node involved in the operation, and semantically compressing at least one portion of the node translation table. The semantic compression includes discarding at least one log entry that is rendered obsolete by at least one subsequent log entry, and incrementing a version number of the log entries corresponding to the at least one portion of the node translation table. In further embodiments, discarding at least one log entry includes discarding at least one log entry that is at least one of opposed by or overruled by at least one subsequent log entry.

Claims

1. A method, comprising:

performing an operation on a database; and

semantically compressing at least one portion of a node translation table corresponding to at least one node involved in the operation, including;

discarding at least one log entry that is rendered obsolete by at least one subsequent log entry; and

incrementing a version number of the log entries corresponding to the at least one portion of the node translation table.

2. The method of claim 1, wherein discarding at least one log entry includes discarding at least one log entry that is overruled by at least one subsequent log entry.

3. The method of claim 1, wherein discarding at least one log entry includes discarding at least one log entry that is opposed by at least one subsequent log entry.

4. The method of claim 1, further comprising performing a log garbage collection on a sector when a fraction of discarded log entries in the sector is greater than or equal to a threshold value.

5. The method of claim 1, further comprising performing a log garbage collection including writing at least one fresh log entry to a log buffer, removing a sector address from the node translation table, and returning the sector to a storage manager.

6. The method of claim 5, further comprising flushing the at least one fresh log entry from the log buffer to a memory, and adding the at least one fresh log entry to the node translation table.

7. The method of claim 1, further comprising checkpointing at least one portion of the node translation table including replacing one or more sector addresses with one or more corresponding physical addresses, and storing the physical addresses.

8. A method, comprising:

performing an operation on a database; and

checkpointing at least one portion of a node translation table corresponding to at least one node involved in the operation, including;

replacing one or more sector addresses with one or more corresponding physical addresses; and

storing the physical addresses in a memory.

9. The method of claim 8, wherein checkpointing at least one portion of the node translation table further comprises:

if a garbage collection threshold is satisfied, performing a garbage collection including copying a content of a first page to a second location, and updating a corresponding portion of the node translation table with the second location.

10. The method of claim 9, wherein performing a garbage collection further includes erasing the first page.

11. The method of claim 8, further comprising supplementing at least one portion of the node translation table corresponding to at least one node involved in the operation, including appending a recent log entry to a list corresponding to the at least one node.

12. The method of claim 8, further comprising performing a rollback including loading the previously-checkpointed physical addresses into the node translation table in a memory.

13. The method of claim 12, wherein performing a rollback further includes:

creating new logical addresses in a logical storage at an active physical address and in the node translation table in a memory; and

placing the logical addresses in the restored node translation table in the memory.

14. The method of claim 8, further comprising semantically compressing at least one portion of the node translation table including:

discarding at least one log entry that is rendered obsolete by at least one subsequent log entry; and

incrementing a version number of the log entries corresponding to the at least one portion of the node translation table.

15. One or more computer readable media containing computer-readable instructions that, when executed, perform a method comprising:

semantically compressing at least one portion of a node translation table corresponding to at least one node involved in a database operation, the compressing including;

discarding at least one log entry that is rendered obsolete by at least one subsequent log entry; and

incrementing a version number of the log entries corresponding to the at least one portion of the node translation table.

16. The computer readable media of claim 15, wherein the method further comprises performing a log garbage collection on a sector when a fraction of discarded log entries in the sector is greater than or equal to a threshold value.

17. The computer readable media of claim 15, wherein the method further comprises checkpointing of at least one portion of the node translation table, wherein the checkpointing includes replacing one or more sector addresses with one or more corresponding physical addresses, and storing the physical addresses.

18. The computer readable media of claim 17, wherein the checkpointing further includes:

if a garbage collection threshold is satisfied, performing a garbage collection including copying a content of a first page to a second location, and updating a corresponding portion of the node translation table with the second location.

19. The computer readable media of claim 15, wherein the method further comprises communicating with a flash translation layer to provide a disk-like interface with a flash memory.

20. The computer readable media of claim 15, wherein the method further comprises communicating with the storage manager and with one or more database applications.