Method of storing data into flash memory in a DBMS-independent manner using the page-differential

• US 8,117,406 B2
• Filed: 07/23/2009
• Issued: 02/14/2012
• Est. Priority Date: 04/23/2009
• Status: Active Grant

• Current Assignee: Korea Advanced Institute of Science and Technology
• Original Assignee: Korea Advanced Institute of Science and Technology
• Inventors: Whang, Kyu-Young, Kim, Yi-Reun
• Primary Examiner(s): Elmore, Reba I.
• Application Number:
  US12/507,946
• Publication Number:
  US 20100241790A1
• Time in Patent Office: 936 Days
• Field of Search: 711/103, 711/154
• US Class Current: 711/154
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 16/1847 specifically adapted to static storage, e.g. adapted to flash memory or SSD
• CPC Class Codes: G06F 2212/7202 Allocation control and policies

Abstract

The present invention proposes an effective and efficient method of storing data called page-differential logging for flash-based storage systems. The primary characteristics of the invention are: (1) it writes only the page-differential that is defined as the difference between an original page in flash memory and an up-to-date page in memory; (2) it computes and writes the page-differential only when an updated page needs to be reflected into flash memory. When an updated page needs to be reflected into flash memory, the present invention stores the page into a base page and a differential page in flash memory. When a page is recreated from flash memory, it reads the base page and the differential page, and then, creates the page by merging the base page with its page-differential in the differential page. This invention significantly improves I/O performance of flash-based storage systems compared with existing page-based and log-based methods.

Claims

1. A method of storing data into the flash memory in a database management system (DBMS)-independent manner using the page-differential, comprising:

a writing step of storing a logical page into a base page and a differential page in the flash memory; and

a recreating step of reading the base page and the differential page, and creating a logical page by merging the base page with its differential in the differential page.

2. The method according to claim 1, wherein the writing step comprises:

a differential generating step of generating a differential by comparing the logical page with the base page in the flash memory;

a differential writing step of writing the generated differential into the differential write buffer; and

a buffer writing step of writing the content of the differential write buffer into the flash memory when the buffer is full.

3. The method according to claim 1, wherein the base page contains the whole logical page.

4. The method according to claim 1, wherein the differential page can contain differentials of multiple logical pages.

5. The method according to claim 1, wherein the differential is the difference between the base page in the flash memory and the logical page in the memory.

6. The method according to claim 1, wherein the writing step is performed only when an updated logical page needs to be reflected into the flash memory.

7. The method according to claim 1, wherein the writing step comprises:

a first step of reading the base page of the logical page from the flash memory;

a second step of generating the differential for the logical page by comparing the base page read at the first step with the logical page; and

a third step of removing an old differential for the logical page if the old differential resides in the differential write buffer, and writing the generated differential into the write buffer.

8. The method according to claim 7, wherein the third step is a step of, when the size of the differential is equal to or smaller than the free space of the differential write buffer, writing the generated differential into the write buffer.

9. The method according to claim 7, wherein the third step comprises the steps of, when the size of the differential is larger than the free space of the differential write buffer, but is equal to or smaller than that of one physical page, writing the content of the buffer into the flash memory, clearing the buffer, and writing the differential into the buffer.

10. The method according to claim 9, wherein the step of writing the content of the differential write buffer into the flash memory comprises the steps of:

writing the content of the buffer into a physical page that is newly allocated in the flash memory; and

updating the physical page mapping table and the valid differential count table.

11. The method according to claim 10, wherein the updating step comprises, for each differential in the differential write buffer, the steps of:

updating the physical page mapping table so that the differential page of the logical page to which the differential belongs is set to the new physical page;

when an old differential page of the logical page to which the differential belongs is not null, decreasing the count for the old differential page in the valid differential count table by 1; and

increasing the count for the new differential page in the valid differential count table by 1.

12. The method according to claim 11, further comprising, after the step of decreasing the count for the old differential page by 1, the step of setting the differential page to obsolete if the count for the old differential page becomes 0.

13. The method according to claim 7, wherein the third step comprises the steps of, when the size of the differential is larger than that of one physical page, discarding the generated differential and writing the logical page itself into the flash memory.

14. The method according to claim 13, wherein the step of writing the logical page comprises the steps of:

writing the logical page into a physical page that is newly allocated in the flash memory; and

updating a physical page mapping table and a valid differential count table.

15. The method according to claim 14, wherein the table updating step comprises the steps:

updating the physical page mapping table so that the base page and the differential page of the logical page are set to the new physical page and null, respectively;

when an old differential page of the logical page is not null, decreasing the count for the old differential page in the valid differential count table by 1; and

setting the old base page of the logical page to obsolete.

16. The method according to claim 15, further comprising, after the step of decreasing the count for the old differential page by 1, the step of setting the differential page to obsolete if the count for the old differential page becomes 0.

17. The method according to claim 1, wherein the recreating step comprises:

a first step of reading the base page of the logical page from the flash memory;

a second step of finding the differential of the logical page; and

a third step of creating a logical page by merging the base page read at the first step with the differential found at the second step, and returning the logical page as the result.

18. The method according to claim 17, wherein the second step is performed to find the differential of the logical page from the differential write buffer when the differential resides in the buffer.

19. The method according to claim 17, wherein the second step comprises the steps of, when the differential does not reside in the differential write buffer, reading the differential page of the logical page from the flash memory, and finding the differential from the differential page read.

20. The method according to claim 19, further comprising the step of, before the step of reading the differential page of the logical page, returning the base page read at the first step as the result if the differential page of the logical page does not exist in the flash memory.