Data storage method and system thereof

This non-provisional application claims priority under 35 U.S.C. § 119(a) on Patent Application No. 105102973 filed in Taiwan, R.O.C. on 2016 Jan. 29, the entire contents of which are hereby incorporated by reference.

The instant disclosure relates to a data storage method, in particular to a data storage method, which can be applied to a data storage system such as a hard disk.

In recent years, the development of non-volatile storage devices, such as a solid-state drive, has been flourishing. Since storage capacity, power consumption and integration of flash memory are better than a conventional hard dish drive, flash memory has become an ideal component as a storage device in electronic devices.

A conventional flash memory includes many storage blocks for storing data, and each storage block is composed of many storage pages. After the stored data in a flash memory have been updated several times, the old data, originally stored in the storage pages, may become invalid. In this situation, it is necessary to execute garbage collection to erase invalid data, in order to release the storage pages which are occupied by the invalid data. However, the storage pages can only be re-written once the storage block is entirely and successfully erased, and the time to erase a storage block is much longer than the time to write a storage page. For example, while it may take about 200 microseconds to write a storage page, it will take about 2 milliseconds to erase a storage block. The procedure of erasing a flash memory can greatly reduce read-write performance accordingly

Furthermore, before a storage block is to be erased, the valid data in the storage block must be moved to other storage pages in a flash memory so that the storage block can then be erased. Since each storage page in a flash memory can be read/written for a limited times, moving the data will result in extra read/write, i.e., increasing the times of read/write of a storage page, thereby reducing the lifetime of a flash memory.

In view of these, this instant disclosure provides a data storage method and a system thereof.

In one embodiment of the instant disclosure, a data storage system includes a hard disk and a processing unit. A hard disk includes a physical block, which includes a plurality of physical pages, which store a plurality of written data corresponding to a plurality of logical addresses. Each of the physical pages corresponds to a valid bit. And each of the physical pages with the valid bit corresponding to a first value is classified as a valid data page, or each of the physical pages with the valid bit corresponding to a second value is classified as an invalid data page. A processing unit allocates a first logical block and a second logical block, wherein the first logical block and the second logical block are mapped to the physical block. The first logical block includes a plurality of consecutive first logical pages and the second logical block includes a plurality of consecutive second logical pages. The first logical pages are used to store the logical addresses, which include a plurality of valid logical addresses, which are mapped to the valid data pages, and there is a one-to-one first mapping relationship between the valid logical addresses and the valid data pages. On executing garbage collection, the processing unit sequentially and consecutively stores the valid logical addresses in the second logical pages in the order of the second logical pages according to the valid bits. And the processing unit establishes a one-to-one second mapping relationship between the second logical pages and the valid data pages according to the first mapping relationship.

In an embodiment, a data storage method is used to store a plurality of written data in a plurality of physical pages in a physical block in a hard disk according to a plurality of logical addresses. Each of the physical pages corresponds to a valid bit. And each of the physical pages with the valid bit corresponding to a first value is classified as a valid data page, or each of the physical pages with the valid bit corresponding to a second value is classified as an invalid data page. The logical addresses include a plurality of valid logical addresses, which are mapped to the valid data pages, and there is a one-to-one first mapping relationship between the valid logical addresses and the valid data pages. The data storage method includes: allocating a first logical block and a second logical block, wherein the first logical block and the second logical block are mapped to the physical block, and the first logical block includes a plurality of consecutive first logical pages, which are used to store the logical addresses, and the second logical block includes a plurality of consecutive second logical pages; on executing garbage collection, sequentially and consecutively storing the valid logical addresses in the second logical pages in the order of the second logical pages according to the valid bits; and establishing a one-to-one second mapping relationship between the second logical pages and the valid data pages according to the first mapping relationship.

In summary, an embodiment of a data storage method and a system thereof according to the instant disclosure allocates two logical blocks, mapped to the same physical block, to store logical addresses, and on executing garbage collection, relocates the logical addresses stored in the first logical block to the second logical block to accomplish garbage collection without moving the written data in the physical block. Accordingly, the times of read-write to the physical pages are reduced and thereby the lifetime of the flash memory is increased.

The instant disclosure will become more fully understood from the detailed description given herein below for illustration only, and thus not limitative of the instant disclosure, wherein:

FIG. 1 is a functional block diagram of one embodiment of a data storage system according to the instant disclosure.

FIG. 2 is a functional block diagram of one embodiment of a first logical block, allocated by the processing unit in FIG. 1 .

FIG. 3 is a functional block diagram of one embodiment of a second logical block, allocated by the processing unit in FIG. 1 .

FIG. 4 is a flow chart of one embodiment of a data storage method according to the instant disclosure.

FIG. 1 is a functional block diagram of one embodiment of a data storage system according to the instant disclosure. FIG. 2 is a functional block diagram of one embodiment of a first logical block L 1 , allocated by the processing unit 2 in FIG. 1 . FIG. 3 is a functional block diagram of one embodiment of a second logical block L 2 , allocated by the processing unit 2 in FIG. 1 .

With reference to FIG. 1 through FIG. 3 , a data storage system includes a hard disk 1 and a processing unit 2 . The processing unit 2 is electrically connected to the hard disk 1 to control the read/write operation of the hard disk 1 . The hard disk 1 includes a plurality of physical blocks, and each physical block includes a plurality of physical pages. An example is illustrated in FIG. 1 through FIG. 3 , where the physical blocks in the hard disk 1 includes physical blocks 11 , 12 , and 13 , and the physical block 11 includes five physical pages 111 ˜ 115 . Herein, the processing unit 2 can store written data in the physical pages 111 ˜ 115 .

The physical pages 111 ˜ 115 correspond to valid bits V 1 ˜V 5 , respectively, which indicate whether the written data stored in physical pages 111 ˜ 115 are valid. If the written data stored in physical pages 111 ˜ 115 are the old data, that is, no longer in use, then the written data are indicated invalid. Therein, the valid bit V 1 , corresponding to the physical page 111 , indicates whether the written data stored in the physical page 111 are valid or invalid, and the valid bit V 2 , corresponding to the physical 112 , indicates whether the written data stored in the physical page 112 are valid or invalid, and so on, which will not be described in details herein. Therefore, depending on whether the valid bits V 1 ˜V 5 are a first value or a second value, the physical pages 111 ˜ 115 can be classified as a valid data page and an invalid data page. For example, assuming the first value “1” and the second value “0”, if the valid bit V 1 , corresponding to the physical page 111 , is “0”, the physical page 111 is indicated as an invalid data page; if the valid V 4 , corresponding to the physical page 114 m is “1”, the physical page 114 is indicated as a valid data page. In this way, the valid bits V 1 ˜V 5 can be used to indicate whether the physical pages 111 ˜ 115 include invalid data and further whether the space needs to be freed.

In this embodiment, each of the written data corresponds to a logical address, and each logical address is mapped to a corresponding page in the physical pages 111 ˜ 115 so that the processing unit 2 can store the written data in the corresponding pages 111 ˜ 115 according to the logical addresses. An example is illustrated in FIG. 2 , where four logical addresses are “10”, “20”, “30”, and “10”, respectively, and the four logical addresses are mapped to the physical pages 111 , 112 , 113 , and 114 respectively, so that the processing unit 2 can store the corresponding four written data in the physical pages 111 ˜ 114 according to the four logical addresses. Therein, the physical pages 111 and 114 are mapped to the same logical address “10”. Assuming the data are written in the physical page 114 later than into the physical page 111 , the physical page 111 will be an invalid data page, while the other physical pages 112 , 113 and 114 are still valid data pages. As such, logical addresses include valid logical addresses and invalid logical addresses, wherein the logical addresses mapped to valid data pages are valid logical addresses and the logical addresses mapped to invalid data pages are invalid logical addresses. Also, there is a one-to-one first mapping relationship between valid logical addresses and valid data pages. As illustrated in FIG. 2 , “10” stored in a first logical page L 11 is an invalid logical address, and “20”, “30”, and “40” stored in first logical pages L 12 ˜L 14 are valid logical addresses. The logical address “20” of the valid logical addresses is one-to-one mapped to the physical page 112 of the valid data pages, the logical address “30” of the valid logical addresses is one-to-one mapped to the physical page 113 of the valid data pages, and the logical address “10” of the valid logical addresses is one-to-one mapped to the physical page 114 of the valid data pages. In practice, the logical addresses can be virtual addresses from I/O devices.

FIG. 3 is a functional block diagram of one embodiment of a second logical block L 2 , allocated by the processing unit 2 in FIG. 1 . With reference to FIG. 2 and FIG. 3 , the processing unit 2 is used to allocate a first logical block L 1 and a second logical block L 2 , wherein the first logical block L 1 includes a plurality of consecutive first logical pages, the second logical block L 2 includes a plurality of consecutive second logical pages, and the first logical block L 1 and the second logical block L 2 are mapped to the same physical block in the hard disk 1 . As illustrated in FIG. 2 and FIG. 3 , the first logical block L 1 and the second logical block L 2 are both mapped to the physical block 11 , wherein the first logical block L 1 includes consecutive first logical pages L 11 ˜L 15 and the second logical block L 2 includes consecutive second logical pages L 21 ˜L 25 . In this embodiment, an example is illustrated in FIG. 2 and FIG. 3 , where the processing unit 2 allocates two logical blocks L 1 and L 2 to be mapped to the physical block 11 . However, the instant disclosure is limited thereto. The processing unit 2 can allocate a plurality of logical blocks to be mapped to a physical block in the hard disk 1 , and the processing unit 2 can allocate a plurality of logical blocks to be mapped to each of the physical blocks in the hard disk 1 . For example, the processing unit 2 can allocate four logical blocks to be mapped to the physical block 12 in the hard disk 1 and can allocate another three logical blocks to be mapped to the physical block 13 in the hard disk 1 so that a plurality of logical blocks are mapped to each of the physical blocks in the hard disk 1 .

The first logical block L 1 is used to store logical addresses, and on executing the write operation, the processing unit 2 sequentially stores the logical addresses, which correspond to the written data, respectively, in the first logical block L 1 . As illustrated in FIG. 2 , the first logical pages L 11 ˜L 14 include the first logical address “10”, “20”, “30” and “10” mentioned above, respectively, and the processing unit 2 write data in the corresponding physical pages 111 ˜ 114 according to the logical addresses stored in the first logical pages L 11 ˜L 14 . After a plurality of written data are stored in the physical block 11 of the hard disk 1 , once the available storage space is below a threshold value, the processing unit 2 will start to execute garbage collection to release the invalid data pages, which include the invalid data. First of all, the processing unit 2 sequentially and consecutively stores the valid logical addresses, according to the valid bits V 1 ˜V 5 , in the second logical pages L 21 ˜L 24 in the order of the second logical pages L 21 ˜L 24 . In details, as illustrated in FIG. 2 , the processing unit 2 decides whether the logical addresses of the first logical pages L 12 ˜L 14 are valid logical addresses, depending on the values of the valid bits V 1 ˜V 5 ; next, as illustrated in FIG. 3 , the processing unit 2 stores the valid logical address “20”, which is stored in the first logical page L 12 , in the second logical page L 21 and the processing unit 2 stores the valid logical address “30”, which is stored in the first logical page L 13 , in the second logical page L 22 , to which the second logical page L 21 is consecutive to; last, the processing unit 2 stores the valid logical address “10”, which is stored in the first logical page L 14 , in the second logical page L 23 , to which the second logical page L 22 is consecutive, by which garbage collection is accomplished. Therefore, compared to the first logical block L 1 , the second logical block L 2 does not include any logical address, which corresponds to an invalid data page, which makes the number of the blank pages in the logical block L 2 (such as the second logical pages L 24 and L 25 ) to be greater than the number of the blank pages in the logical block L 1 (such as the first logical page L 15 ). Thus, compared to the prior art, the processing unit 2 does not need to move the written data in the physical block 11 to accomplish garbage collection. Accordingly, the times of read-write to the physical pages are reduced and thereby the lifetime of the flash memory is increased.

In this embodiment, after the processing unit 2 moves the valid logical addresses “20”, “30” and “10” from the first logical block L 1 to the second logical block L 2 , the processing unit 2 establishes a one-to-one second mapping relationship between the second logical pages L 21 ˜L 23 and the valid data pages (i.e., the physical pages 112 , 113 , and 114 ), so that the second logical pages L 21 , L 22 and L 23 are respectively one-to-one mapped to the physical pages 112 , 113 and 114 and further the valid logical addresses “20”, “30”, and “10” can be mapped to the physical pages 112 , 113 and 114 , where the corresponding written data are previously stored.

In practice, the processing unit 2 can be implemented with a micro-processor, a micro-controller, or a central processing unit, and can be controlled by software or firmware. The processing unit 2 can also be an application-specific IC (ASIC). The processing unit 2 can allocate a first logical block L 1 and a second logical block L 2 in a cache memory, or RAMs, to store logical addresses.

In an embodiment, the processing unit 2 sequentially stores the logical addresses in the consecutive pages in the first logical block L 1 in the order of the first logical pages L 11 ˜L 15 . An example is illustrated in FIG. 2 , where the processing unit 2 first stores the logical address “10” in the first logical page L 11 , then the processing unit 2 stores the logical address “20” in the first logical page L 12 , to which the first logical page L 11 is consecutive, and then the processing unit 2 stores the logical address “30” in the first logical page L 13 , to which the first logical page L 12 is consecutive, and last, the processing unit 2 stores the logical address “10” in the first logical page L 14 , to which the first logical page L 13 is consecutive. Herein, after the four written data are stored in the physical block 11 in the hard disk 1 , the first logical block L 1 sequentially includes the four logical addresses in the order of the first logical pages L 11 ˜L 14 , wherein the four logical addresses are mapped to the valid data pages and the invalid data pages, respectively. Moreover, there is a one-to-one third mapping relationship between the first logical pages L 11 ˜L 15 and the physical pages 111 ˜ 115 , so that the first mapping relationship is established between the valid logical addresses, which are stored in the first logical pages L 11 ˜L 15 , and the valid data pages according to the third mapping relationship. For example, as illustrated in FIG. 2 , the first logical pages L 11 , L 12 , L 13 , L 14 , and L 15 are mapped to the physical pages 111 , 112 , 113 , 114 , and 115 , respectively. After the logical addresses “10”, “20”, “30” and “10” are stored in the logical pages L 11 , L 12 , L 13 , and L 14 , the valid logical addresses “20”, “30”, and “10” are one-to-one mapped to the valid data pages 112 , 113 , and 114 so that the first mapping relationship is established.

In an embodiment, after the processing unit 2 moves the logical addresses from the first logical block L 1 to the second logical block L 2 , the processing unit 2 establishes a one-to-one fourth mapping relationship between the blank pages in the second logical block L 2 and the invalid data pages in the physical page 111 . An example is illustrated in FIG. 3 , where the blank pages in the second logical block L 2 are the second logical pages L 24 and L 25 and the processing unit 2 establishes the fourth mapping relationship that the second logical L 24 and L 25 are mapped to the physical pages 111 and 115 , which are invalid data pages. Consequently, after garbage collection, the processing unit 2 can fill the logical addresses corresponding to another written data, such as the fifth and the sixth written data, into the second logical pages L 24 and L 25 so that the two written data can be stored in the corresponding physical pages 111 and 115 according to the fourth mapping relationship. Herein, whether the invalid data pages in the physical block 11 are consecutive or inconsecutive, the processing unit 2 can use them to store new written data by overwriting the original data after executing garbage collection.

In an embodiment, before the processing unit 2 executes any write operation, the third mapping relationship between the first logical block L 1 and the physical block 11 can be pre-stored in the hard disk 1 or any other circuits with storage capability, so that the processing unit 2 can store, according to the pre-stored third mapping relationship, the written data in the corresponding physical pages 111 ˜ 115 according to the page locations where the logical addresses are stored in the first logical block L 1 . After the processing unit 2 executes garbage collection for the first logical block L 1 , the processing unit 2 stores a fourth mapping relationship between the logical block L 2 and the physical block 11 to overwrite the stored third mapping relationship so that the another written data as mentioned above, such as the fifth and the sixth written data, can be stored in the corresponding physical pages 111 and 115 , according to the page locations where the corresponding logical addresses are stored in the second logical block L 2 . Herein, after executing garbage collection for the first logical block L 1 , the processing unit 2 will no longer use the first logical block L 1 and will map the logical addresses to the physical block 11 via the second logical block L 2 .

According to the second mapping relationship, the third mapping relationship, and the fourth mapping relationship, it can be known that the first logical pages L 11 ˜L 15 are one-to-one mapped to the physical pages 111 ˜ 115 , and the second logical pages L 21 ˜L 25 are one-to-one mapped to the physical pages 111 ˜ 115 , that is, the number of the first logical pages L 11 ˜L 15 is the same as the number of the physical pages 111 ˜ 115 , and the number of the second logical pages L 21 ˜L 25 is the same as the number of the physical pages 111 ˜ 115 . Herein, when the processing unit 2 allocates logical blocks which one-to-one corresponds to each physical block of the hard disk 1 , since the number of the logical pages of each logical block is the same as the number of the physical pages of each physical block, the processing unit 2 can use the number of the blank pages in the first logical block L 1 to determine whether the available storage space in the hard disk 1 has reached the threshold value, and to decide whether to execute garbage collection for the first logical block L 1 . In the same way, the processing unit 2 can use the number of the blank pages in the second logical block L 2 to determine whether the available storage space in the hard disk 1 has reached the threshold value, and to decide whether to execute garbage collection for the second logical block L 1 .

In an embodiment, to prevent the logical addresses from not being mapped to the physical block 11 due to power outage of an electronic device with a data storage system, before the processing unit 2 executes garbage collection, the processing unit 2 can store the first mapping relationship and the third mapping relationship in the hard disk 1 . In this way, the electronic device can access the first mapping relationship and the third mapping relationship from the hard disk 1 after the power is back on and the processing unit 2 can store the written data in the hard disk 1 according to the first mapping relationship and the third mapping relationship. Moreover, after executing garbage collection, the processing unit 2 can store the second mapping relationship and the fourth mapping relationship in the hard disk 1 , to prevent the logical addresses from not being mapped to the physical block 11 due to the power outage of the electronic device.

FIG. 4 is a flow chart of one embodiment of a data storage method according to the instant disclosure. With reference to FIG. 1 through FIG. 4 , the processing unit 2 allocates a first logical block L 1 and a second logical block L 2 (Step S 01 ). An example is illustrated in FIG. 2 and FIG. 3 , where the first logical block L 1 includes first logical pages L 11 ˜L 15 , the second logical block L 2 includes second logical pages L 21 ˜L 25 , and the first logical pages L 11 ˜L 15 and the second logical pages L 21 ˜L 25 are used to store the logical addresses corresponding to written data. Next, the processing unit 2 determines if garbage collection is needed for the hard disk 1 (Step S 02 ). When the available storage space of the hard disk 1 is smaller than or equal to a threshold value so that garbage collection is needed, the processing unit 2 sequentially and consecutively stores the valid logical addresses in the second logical pages L 21 ˜L 25 in the order of the second logical pages L 21 ˜L 25 according to the valid bits V 1 ˜V 5 (Step S 03 ) to accomplish garbage collection. At last, the processing unit 2 , according to the first mapping relationship between the valid logical addresses and the valid data pages, establishes a one-to-one second mapping relationship between the logical pages, including the logical addresses, in the second logical pages L 21 ˜L 25 and the valid data pages (Step S 04 ).

In an embodiment, before the processing unit executes any write operation, a data storage method further includes establishing a one-to-one third mapping relationship between the first logical pages L 11 ˜L 15 and the physical pages 111 ˜ 115 ; next, when the processing unit 2 executes write operation, the processing unit 2 sequentially and consecutively stores the logical addresses in the first logical pages L 11 ˜L 15 in the order of the first logical pages L 1 ˜L 15 so that the first mapping relationship is established between the valid logical address (i.e., the logical addresses stored in the first logical pages L 12 ˜L 14 ) and the valid data pages (i.e. the physical pages 112 ˜ 114 mentioned above) according to the third mapping relationship.

In an embodiment, after executing Step S 04 , the processing unit 2 establishes a one-to-one fourth mapping relationship between the blank pages in the second logical pages L 21 ˜L 25 (i.e. the second logical pages L 24 and L 25 ) and the invalid data pages (the physical pages 111 and 115 ) so that the fifth written data and the sixth written data can be stored in the physical pages 111 and 115 according to the logical addresses in the second logical pages L 24 and L 25 .

In an embodiment, before executing Step S 03 , the processing unit 2 stores the first mapping relationship and the third mapping relationship in the hard disk 1 to prevent the logical addresses from not being mapped to the physical pages 111 ˜ 115 due to the power outage of the data storage system. Similarly, after executing Step S 03 , the processing unit 2 stores the second mapping relationship and the fourth mapping relationship in the hard disk 1 to prevent the logical addresses from not being mapped to the physical pages 111 ˜ 115 due to the power outage of the data storage system.

In summary, an embodiment of a data storage method and a system thereof according to the instant disclosure stores logical addresses by allocating two logical blocks, mapped to the same physical block; and upon executing garbage collection, moves the logical addresses stored in the first logical block to the second logical blocks to accomplish garbage collection, without moving the written data in the physical blocks. Accordingly, the times of read-write to the physical pages are reduced and thereby the lifetime of the flash memory is increased.

While the instant disclosure has been described by the aforementioned embodiments, it is to be understood that the invention needs not be limited to the disclosed embodiments. For anyone skilled in the art, various modifications and variations within the spirit of the instant disclosure are covered under the scope of the instant disclosure. The covered scope of the instant disclosure is based on the appended claims.