CN102012849B - Flash memory-based database restoring method - Google Patents

Abstract

The invention relates to a method for restoring a database based on flash memory, which is characterized in that it includes a memory, a flash memory, a checkpoint management module, a system startup module and a system shutdown module, and the memory stores data page buffer, log Buffer and log area summary; the log area, data area, page table and bit map used to identify the allocation of flash memory space are stored in the flash memory; the checkpoint management module sets up checkpoints in the log area; the system startup module needs to Scan the log area and merge the obtained logs and data; when the system shutdown module starts, it needs to insert a series of logs in the log area, and perform a series of operations at the same time to complete the system shutdown; the log buffer records a part of the log, and flushes the log written to flash memory. The invention can reduce the erasing of the flash memory and give full play to the advantages of the flash memory. The invention can be widely used in the recovery of system database.

Description

A method of database recovery based on flash memory

technical field

The invention relates to a method for restoring a database, in particular to a method for restoring a database based on flash memory.

Background technique

With the widespread use of flash memory, more and more data is stored on flash memory devices. Flash memory data management has become a new research field. The flash memory-based database technology is facing great challenges, which has attracted more and more attention from the industry. If the existing database technology designed for disk storage devices is directly run on the flash memory, the reading speed in query processing is only increased by 1 to 10 times, and the writing speed is only increased by 1 to 3 times. In fact, the read and write speed of flash memory is on the order of microseconds, which is about 100 times that of disk. It can be seen that if the existing traditional disk-oriented database system runs directly on the flash memory, it cannot fully utilize the high-speed read and write bandwidth of the flash memory compared with the disk, and the excellent read and write performance of the flash memory is greatly reduced. The reason for this is the huge difference in the physical characteristics of flash and disk. For example, when updating data on flash memory, because flash memory uses pages as read-write units and the entire block must be erased before overwriting, even if a small part of the data in a page is updated, in order to support the in-place update mode of the existing database, It is also necessary to read all the data of the block where the page is located into the memory, then modify the data of the page, then erase the entire block, and finally write the data of the entire block in the memory back to the flash memory. This greatly reduces the update performance, resulting in a sharp decline in the update performance of the database, and the transaction throughput of the system has not been improved as it should.

The recovery method of the system database generally consists of two parts. One is to retain enough information for fault recovery during normal transaction processing; the other is to take measures after a fault occurs to restore the database to a consistent state and maintain The state of the transaction's atomicity and durability. These two aspects are closely related, and the type and degree of information maintained determine the type and cost of steps to be taken after the failure occurs. Similarly, the type and cost of the operation after the failure also determines the size of the extra overhead during the normal processing of the transaction. The existing database recovery methods are as follows: (1) The log-based recovery technology is widely used in disk. This approach yields many different approaches to logging and recovery, with many different commit protocols guiding the logging and recovery process. Under different protocols, the log record design, log/data buffer management, checkpoint mechanism, log record and recovery process are very different. (2) Shadow pages are another well-known transaction recovery technology that does not require explicit rollback operations. The main idea of shadow page technology is to adopt the update mode of remote update, and maintain two page tables in the life cycle of the transaction: the current page table (Current Page Table) and the shadow page table (Shadow Page Table). When the transaction starts, the two page tables are identical. The shadow page table never changes during transaction execution, and the transaction writes the updated new address of the database into the current page table. When the transaction is committed, the current page table is written into the non-volatile memory, and an atomic operation is used to replace the current page table and the shadow page table, so the current page table becomes the shadow page table, and the next transaction is executed. If the current page table is lost when the system crashes, the database can use the shadow page table to recover. (3) All kinds of system software (such as database management system) and application software based on the operating system need to use interfaces such as transactions to deal with various failures and deal with recovery from disasters. If a transaction (Transaction) interface can be provided at the file system level, it will greatly reduce the redundancy cost paid by the software on it to deal with system failures individually.

Much previous work has been devoted to providing such transactional interfaces on disk file systems using copy-on-write and journaling techniques. However, due to the copy-on-write (copy-on-write) technology, the data originally stored in clusters on the disk will become very scattered data fragmentation. The read and write efficiency of discrete data on a mechanical device such as a disk is very low. To solve this problem, many works adopt checkpoint and regular cleaning mechanism to reorganize discrete data. Studies have shown that such reorganization overhead is so expensive that a transaction-enabled file system is not worth the cost. The physical characteristics of the flash memory are well suited to the requirements of the transaction file system, and it is a good choice to support the transaction interface on the flash file system. Transactional Flash (Tansactional Flash) provides a transactional interface on top of the flash file system, which uses per-page metadata and circle commit protocols to reduce the performance and space overhead of additional commit records. The main method is to connect the pages modified by each transaction with metadata pointers to form a circle. In this way, if the transaction is submitted normally, its new version will be in a circle. If a transaction is not submitted normally, its modified data pages cannot form a circle. The circle commit protocol provides a transaction interface at the file system level with a small overhead, but this interface is not perfect, and garbage collection, rollback, and system recovery also require complex logic support, and the overhead is relatively large.

Contents of the invention

In view of the above problems, the object of the present invention is to provide a flash memory-based database recovery method that can reduce the erasing operations on the flash memory and enable the flash memory to fully exert its high-efficiency read and write characteristics.

To achieve the above object, the present invention adopts the following technical solutions: a flash memory-based database recovery method, characterized in that: it includes a memory, a flash memory, a checkpoint management module, a system startup module and a system shutdown module, the A data page buffer, a log buffer, and a summary of the log area are stored in the memory; a log area, a data area, a page table, and a bitmap for identifying the allocation status of the flash memory space are stored in the flash memory; the checking The point management module sets up a checkpoint in the log area; when the system startup module starts, it needs to scan the log area, and merges the obtained log and data; when the system shutdown module starts, it needs to check in the log area A series of logs are inserted, and a series of operations are performed simultaneously to complete system shutdown; the log buffer records a part of the logs, and writes the logs to the flash memory.

The steps for setting up the checkpoint of the checkpoint management module are as follows: (1) insert a record <checkpoint number, active transaction list, start> in the log area to mark the beginning of this checkpoint; (2) wait for the active transaction list After all active transactions in it have been explicitly committed or withdrawn, insert another record <checkpoint number, end> into the log area, marking the normal end of the checkpoint.

The start-up process of described system start-up module is as follows: (1) check the afterbody of log area, judge whether there is the checkpoint end record <checkpoint numbering of sign normal shutdown, end> to exist; Check whether there is a committed or revoked transaction in the active transaction list of the point, if it exists, add a <transaction number, abandon> record at the end of the log area to explicitly cancel the transaction, and then insert a <checkpoint number, end> record to mark The end of the checkpoint; on the contrary, directly insert the <checkpoint number, end> record to mark the end of the checkpoint; (2) scan the log area and rebuild the log area summary in memory.

The step when described system shuts down module startup is as follows: (1) insert the record <checkpoint numbering, active transaction list, start> of mark checkpoint start>, start system shutdown operation; (2) sweep out the data of data page buffer into the data area of the flash memory, and add relevant log records to the log buffer; (3) sweep out the log records in the log area of the page table to the log area of the flash memory; (4) insert the record that marks the end of the checkpoint < Checkpoint number, end >.

The management of the data page buffer is to sweep out the data page according to the replacement algorithm when the data page buffer is full, and add a page table log record<transaction number, logical page address at the end of the log buffer , physical page address> record the mapping relationship between the logical address and the physical address of this page.

In the management of the log buffer, both the log buffer and the log area of the flash memory require sequential writing and sequential sweeping.

The step of searching page address in described page table is as follows: (1) search log buffer, judge whether to have successfully submitted transaction to have revised the logical page to be searched, if so, then return the physical address of recent successful submitted transaction identification; On the contrary, go to the next step; (2) search the log area summary, judge whether there is a logical page address to be searched, and return if so; otherwise, go to the next step; (3) search the log area, and judge whether there is a successfully submitted transaction to modify the pending page address; If there is a logical page to be searched, then return the physical address indicated by the recent successful submission transaction; otherwise, enter the next step; (4) search in the page table, return the page address, and end.

其中，S_f代表所述闪存的大小，S_p代表所述闪存中页面的大小，S_l代表页表日志记录的大小。When the log area is full, the page table and the log area are merged, and the size S _r of the log area will satisfy the following formula:

Wherein, S _f represents the size of the flash memory, S _p represents the size of the page in the flash memory, and S ₁ represents the size of the page table log record.

Because the present invention adopts the above technical scheme, it has the following advantages: 1. Since the present invention adopts a log structure based on flash memory, it fully utilizes the operating characteristics of flash memory in units of pages, while reducing the erasure of flash memory. Therefore, the transaction throughput rate of the system has been greatly improved, and the superior performance of flash memory has been fully utilized. 2. The present invention can adapt well to the physical characteristics of the flash memory due to the database recovery method based on the flash memory, and is superior to the traditional disk database recovery method in terms of recovery speed and data recovery. 3. The present invention does not change the traditional two-layer storage structure of memory and flash memory, and supports a complete transaction interface at the same time, its versatility is guaranteed, and it is beneficial to the rapid application of flash memory. 4. Since the present invention is based on the application of the disk file system, it can be conveniently run on the flash storage device. The invention can be widely used in the recovery of system database.

Description of drawings

Fig. 1 is the overall structural representation of the present invention;

FIG. 2 is a schematic diagram of a checkpoint establishment process in the checkpoint management module of the present invention;

Fig. 3 is a schematic diagram of the startup process of the system startup module of the present invention;

Fig. 4 is a schematic diagram of the start-up process of the system shutdown module of the present invention;

Fig. 5 is a schematic diagram of the process of searching the page address in the page table according to the present invention.

Detailed ways

The present invention will be described in detail below in conjunction with the accompanying drawings and embodiments.

The present invention adopts the update mode of remote update, and uses a page table to manage the free space on the flash memory. The new page table mapping address is not directly written into the page table, but is recorded in a log. The modification of the page table is atomic through the log method, so as to obtain the atomicity of the transaction.

As shown in Figure 1, the present invention includes a memory 1, a flash memory 2, a checkpoint management module 3, a system startup module 4 and a system shutdown module 5, wherein the memory 1 is stored with a data page buffer 6, a log Buffer 7 and log area summary 8; flash memory 2 stores log area 9, data area 10, page table 11 and bitmap 12 used to identify the space allocation status of flash memory 2; checkpoint management module 3 is mainly in log area 9 Set up a checkpoint in the checkpoint, that is, insert a checkpoint log, in order to complete the recovery operation more efficiently; the log area 9 needs to be scanned when the system startup module 4 starts, and the obtained log and data are merged; when the system shutdown module 5 starts, it needs to be in A series of logs are inserted in the log area 9, and a series of operations are performed simultaneously to complete the system shutdown; the log buffer 7 records a part of the logs, and then writes the logs to the flash memory 2 to achieve the purpose of permanent storage. The present invention searches according to the log content, and since the log content has a mapping relationship between the logical address and the physical address of the recorded data, the real location of the data can be found by searching the log.

The record of each page table 11 in the log area 9 is composed of two columns, the first column is the logical page address, and the second column is the physical page address corresponding to the logical page address, then the page table log records have the following two types :

(1) <transaction number, transaction status>;

(2) <transaction number, logical page address, physical page address>.

Wherein, the transaction number is an ID number of a transaction, which is a unique identifier of a transaction. The value of the transaction status can be "commit" or "abandon". A <transaction number, logical page address, physical page address> record converts a logical page address into a corresponding physical page address.

As shown in FIG. 2, in the above-mentioned embodiment, the checkpoint of the checkpoint management module 3 is used in the log area 9 to reduce the maintenance of the log area summary 8, and the page table log to be scanned when the page table 11 and the log area 9 are merged. number of records. When the system is shut down and the log area 9 is long enough, the checkpoint is inserted into the log area 9, and the checkpoint establishment steps are as follows:

(1) Insert a record <checkpoint number, active transaction list, start> into the log area 9 to mark the start of this checkpoint, where the checkpoint number is the unique identifier of this checkpoint, and the active transaction list contains List of active transaction ID numbers;

(2) After all active transactions in the active transaction list have been explicitly committed or withdrawn, insert another record <checkpoint number, end> into log area 9, marking the normal end of the checkpoint.

As shown in Figure 3, in above-mentioned each embodiment, when system start-up module 4 restarts, at first check whether shutting down last time is normal, whether this starting up restarts from a system crash, then do corresponding processing; Must scan at last Log area 9 rebuilds log area summary 8 in memory 1. The startup process of the system startup module 4 is as follows:

(1) Check the tail of the log area 9 to determine whether there is a checkpoint end record <checkpoint number, end> that marks a normal shutdown; if there is no such record, it means that the system restarted from a crash, and the last time must be completed The checkpoint process that has not been completed, that is, for those transactions that are in the active transaction list of the shutdown checkpoint but have not been explicitly committed or withdrawn when the crash occurs, add a log record < transaction number at the end of the log area 9 , give up> to explicitly cancel the transaction, and then insert the <checkpoint number, end> record to mark the end of the checkpoint; otherwise, if the transaction is explicitly committed or withdrawn when the crash occurs, directly insert the <checkpoint number, end > record to mark the end of the checkpoint;

(2) Scan the log area 9 and rebuild the log area summary 8 in memory.

As shown in FIG. 4 , in each of the above embodiments, when the system shutdown module 5 is started, all data in the data buffer 6 and the log buffer 7 are swept out to the data area 10 and the log area 9 on the flash memory 2 respectively. At the same time, a checkpoint is inserted into the end of log area 9 to mark this normal shutdown. The steps when the system shutdown module 5 starts are as follows:

(1) Insert the record <checkpoint number, active transaction list, start> that marks the start of the checkpoint to start the system shutdown operation;

(2) sweep out the data of data page buffer 6 in the data area 10 of flash memory 2, and add relevant log record in the log buffer 7;

(3) the log record of page table log area 9 is swept out in the log area 9 of flash memory 2;

(4) Insert a record <checkpoint number, end> marking the end of the checkpoint.

In the above steps, if the system fails to shut down abnormally, the checkpoint during normal shutdown will be incomplete, and no corresponding record indicating the normal end of the checkpoint will be found at the end of the log area 9 .

In the above-mentioned embodiments, the management of the data page buffer 6 is that when the data page buffer 6 is full and there is not enough space to eliminate the data page, the data page is swept out according to the replacement algorithm and added at the end of the log buffer 9. A page table log record <transaction number, logical page address, physical page address> records the mapping relationship between the logical address and the physical address of this page.

In the above-mentioned embodiments, in the management of the log buffer 7, both the log buffer 7 and the log area 9 of the flash memory 2 require sequential writing and sequential sweeping. For the log record <transaction number, abandonment> of the transaction, it is necessary to scan the log area 9 from the end to the beginning until the beginning of the last checkpoint, and update the page table address modified by the committed transaction in the log area summary 8.

As shown in FIG. 5 , in the above embodiments, when searching for a page address in the page table 11 , the entire page table log file must be scanned from beginning to end each time a logical page address is searched. If there are too many log records to be scanned, this search process may become a new bottleneck of the system. In order not to scan the entire log file every time, the frequently accessed page table address is buffered in the log area summary 8 of memory 1, that is, the log area summary 8 stores the most recently accessed page address. Therefore, the correct and timely physical page address of a logical page may exist in four places: the log buffer 7, the log area summary 8, the log area 9 or the page table 11. So the steps to find the page address in page table 11 are as follows:

(1) search the log buffer 7, and judge whether there is a successful submission transaction to modify the logical page to be searched, if there is, then return the physical address of the recent successful submission transaction identification; if not found, then enter the next step;

(2) Search log area summary 8, judge whether there is the logical page address to be searched, if have then return; If not found then enter next step;

(3) Search the log area 9, judge whether there is a successful submission transaction to modify the logical page to be searched, if there is, then return the physical address of the recent successful submission transaction representation; if not found, then enter the next step;

(4) Search in the page table 11, return the page address, and end.

In the above steps, since the log buffer 9 and the log area summary 8 are both in the memory 1, if the locality of access and the hit area of the log area summary 8 are not too bad, the page address lookup process can be performed in the first two Return after the step. In this way, the search process will be fast enough so as not to become a bottleneck of the system. Experimental analysis shows that as long as a small additional cost is spent, the hit rate of the summary 8 in the log area can reach more than 90%.

In the above embodiments, when the log area 9 is full, the page table 11 and the log area 9 will be merged to generate a new page table, and then the log area 9 will be erased to store the page table log records again. Regularly performing such a merging process can also reduce the number of page table logs in the log area 9 that need to be scanned when the log area digest 8 misses, and speed up the page address generation process. In order to prevent the log area 9 from reaching the erasure limit before the service life of the entire flash memory 2 and being scrapped, the size Sr of the log area 9 needs to satisfy the following formula:

${\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; \&Greater\; Equal;</span>\frac{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; f</span>}}}{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}}{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

Wherein, S _f identifies the size of the flash memory 2, S _p identifies the size of the page in the flash memory 2, and S _l identifies the size of the page table log record.

The merging process of the page table 11 and the log area 9 can also be carried out in the background, and the present invention adopts a mechanism similar to that in the shadow page and the flash memory translation layer: two versions of the page table 11, such as PT0 and PT1, are preserved when merging begins; then Keep PT0 unchanged during the merge process, merge PT1 and log area 9 in the background, and write the new page table to the original PT1 location. After the merge is successful, use an atomic operation to modify the pointer pointing to page table 11 to point to PT1 to make it a new page table. The valid page table; then erase log area 9, complete the merging process of page table 11 and log area 9. This can effectively ensure the atomicity after the merge.

Above-mentioned each embodiment is only for illustrating the present invention, and wherein each step all can be changed to some extent, all equivalent transformations and improvements carried out on the basis of the technical solution of the present invention, all should not be excluded outside the protection scope of the present invention .

Claims (5)

1. A database recovery method based on flash memory, characterized in that: it includes a memory, a flash memory, a checkpoint management module, a system startup module and a system shutdown module, stored in the memory with data page buffer, Summary of log buffer and log area; log area, data area, page table and bit map used to identify the allocation status of the flash memory space are stored in the flash memory; the checkpoint management module is set up in the log area check point; when the system startup module starts, it needs to scan the log area, and merge the obtained log and data; when the system shutdown module starts, it needs to insert a series of logs in the log area, and simultaneously perform a series of Operation to complete the system shutdown; the log buffer records a part of the log, and writes the log to the flash memory; The checkpoint establishment steps of the checkpoint management module are as follows; (1) insert a record <checkpoint number, active transaction list, start> in the log area to mark the beginning of this checkpoint; (2) wait for the active transaction list After all active transactions in it have been explicitly committed or revoked, insert another record <checkpoint number, end> into the log area, marking the normal end of the checkpoint; The start-up process of described system start-up module is as follows: (1) check the afterbody of log area, judge whether there is the checkpoint end record <checkpoint numbering of sign normal shutdown, end> to exist; Check whether there is a committed or revoked transaction in the active transaction list of the point, if it exists, add a <transaction number, abandon> record at the end of the log area to explicitly cancel the transaction, and then insert a <checkpoint number, end> record to mark The end of the checkpoint; on the contrary, directly insert the <checkpoint number, end> record to mark the end of the checkpoint; (2) scan the log area and rebuild the log area summary in memory; The step when described system shuts down module startup is as follows: (1) insert the record <checkpoint numbering, active transaction list, start> of mark checkpoint start>, start system shutdown operation; (2) sweep out the data of data page buffer into the data area of the flash memory, and add relevant log records to the log buffer; (3) sweep out the log records in the log area of the page table to the log area of the flash memory; (4) insert the record that marks the end of the checkpoint < Checkpoint number, end >. 2. a kind of database restoration method based on flash memory as claimed in claim 1, is characterized in that: the management of described data page buffer is when described data page buffer is full, sweeps out data page according to replacement algorithm, And add a page table log record <transaction number, logical page address, physical page address> at the tail of the log buffer to record the mapping relationship between the page logical address and the physical address. 3. a kind of database recovery method based on flash memory as claimed in claim 1, is characterized in that: in the management of described log buffer, the log area of described log buffer and flash memory all requires sequential writing and order to sweep out . 4. a kind of database recovery method based on flash memory as claimed in claim 1, is characterized in that: the step of searching page address in described page table is as follows: (1) Search the log buffer to determine whether the logical page to be searched has been modified by successfully submitting the transaction, and if so, return the physical address of the latest successfully submitted transaction identification; otherwise, enter the next step; (2) Search the summary of the log area, judge whether there is a logical page address to be searched, and return if there is; otherwise, enter the next step; (3) Search the log area to judge whether there is a successful submitted transaction to modify the logical page to be searched, if so, return the physical address indicated by the recent successful submitted transaction; otherwise, enter the next step; (4) Search in the page table, return the page address, and end. 5. a kind of database recovery method based on flash memory as claimed in claim 1 or 2, is characterized in that: when described log area is stored full, described page table and log area are merged, and the size S of described log area _r must satisfy the following formula: ${\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; \&Greater\; Equal;</span>\frac{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; f</span>}}}{{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; p</span>}}}{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; ,</span>$ Wherein, S _f represents the size of the flash memory, S _p represents the size of the page in the flash memory, and S ₁ represents the size of the page table log record.

Images