CN112051971A - Data consolidation method, memory storage device, and memory control circuit unit - Google Patents
Data consolidation method, memory storage device, and memory control circuit unitDownload PDFInfo
- Publication number
- CN112051971A CN112051971ACN202010948313.5ACN202010948313ACN112051971ACN 112051971 ACN112051971 ACN 112051971ACN 202010948313 ACN202010948313 ACN 202010948313ACN 112051971 ACN112051971 ACN 112051971A
- Authority
- CN
- China
- Prior art keywords
- unit
- data
- entity
- mapping information
- physical
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Classifications
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
- G06F3/0614—Improving the reliability of storage systems
- G06F3/0616—Improving the reliability of storage systems in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0629—Configuration or reconfiguration of storage systems
- G06F3/0635—Configuration or reconfiguration of storage systems by changing the path, e.g. traffic rerouting, path reconfiguration
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0638—Organizing or formatting or addressing of data
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0653—Monitoring storage devices or systems
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
- G06F3/0671—In-line storage system
- G06F3/0673—Single storage device
- G06F3/0679—Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Human Computer Interaction (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Computer Networks & Wireless Communication (AREA)
- Techniques For Improving Reliability Of Storages (AREA)
Abstract
Description
Translated fromChinese技术领域technical field
本发明涉及一种快闪存储器技术，尤其涉及一种数据整并方法、存储器存储装置及存储器控制电路单元。The present invention relates to a flash memory technology, in particular to a data consolidation method, a memory storage device and a memory control circuit unit.
背景技术Background technique
数码相机、移动电话与MP3播放器在这几年来的成长十分迅速，使得消费者对存储媒体的需求也急速增加。由于可复写式非易失性存储器模块(rewritable non-volatilememory module)(例如，快闪存储器)具有数据非易失性、省电、体积小，以及无机械结构等特性，所以非常适合内建于上述所举例的各种可携式多媒体装置中。Digital cameras, mobile phones and MP3 players have grown rapidly over the past few years, resulting in a rapid increase in consumer demand for storage media. Because rewritable non-volatile memory modules (eg, flash memory) have the characteristics of data non-volatility, power saving, small size, and no mechanical structure, they are very suitable for built-in Among the various portable multimedia devices exemplified above.
当存储器存储装置出厂时，存储器存储装置中一部分的实体单元会被配置为多个闲置实体单元，以使用此些闲置实体单元来存储新数据。在使用一段时间后，存储器存储装置中的闲置实体单元的数目会逐渐减少。存储器存储装置可通过数据整并程序(或称为垃圾收集程序)将有效数据从多个来源节点复制到回收节点(亦称为目标节点)并抹除属于来源节点的实体单元以释放出新的闲置实体单元。When the memory storage device is shipped from the factory, a part of the physical units in the memory storage device are configured as a plurality of idle physical units, so as to use the idle physical units to store new data. After a period of use, the number of idle physical units in the memory storage device will gradually decrease. The memory storage device can copy valid data from multiple source nodes to a recycling node (also known as a target node) through a data consolidation process (or a garbage collector) and erase the physical units belonging to the source nodes to release new ones. Idle physical units.
一般来说，在数据整并程序中，会先对来源节点中存储有较少的有效数据的实体单元进行数据整并程序，以确保此些存储有较少的有效数据的实体单元中的有效数据皆能复制到回收节点。接着，再从来源节点中存储有较多的有效数据的实体单元中，将有效数据复制到回收节点的剩余空间。然而，选择作为来源节点的多个实体单元所映射的逻辑单元重复率越高，则在前述两个阶段的数据整并程序中，将会重复载入更多记载此些逻辑单元的管理信息(例如映射信息)的相同的表格，从而增加存储器存储装置的存取次数并导致存储器存储装置的整体效能下降。Generally speaking, in the data consolidation procedure, the data consolidation procedure is first performed on the entity units that store less valid data in the source node, so as to ensure the effective data in these entity units that store less valid data. All data can be copied to the recycling node. Next, the valid data is copied to the remaining space of the recycling node from the entity unit that stores more valid data in the source node. However, the higher the repetition rate of the logical units mapped by the multiple physical units selected as source nodes, the more management information ( such as mapping information), thereby increasing the number of accesses of the memory storage device and causing the overall performance of the memory storage device to decrease.
发明内容SUMMARY OF THE INVENTION
本发明提供一种数据整并方法、存储器存储装置及存储器控制电路单元，可改善上述问题，并有效减少在数据整并程序中对于存储器存储装置的存取次数。The present invention provides a data consolidation method, a memory storage device and a memory control circuit unit, which can improve the above problems and effectively reduce the number of accesses to the memory storage device in the data consolidation process.
本发明的范例实施例提供一种数据整并方法，其用于可复写式非易失性存储器模块，其中所述可复写式非易失性存储器模块包括多个实体单元。所述数据整并方法包括：从所述实体单元中选择至少一第一实体单元与至少一第二实体单元；从所述可复写式非易失性存储器模块中读取第一映射信息，其中所述第一映射信息包含所述至少一第一实体单元的映射信息与所述少一第二实体单元的映射信息；根据所述第一映射信息，将从所述至少一第一实体单元中收集的有效数据与从所述至少一第二实体单元中的收集的有效数据复制到所述实体单元中的至少一第三实体单元；以及当从所述至少一第二实体单元中复制到所述至少一第三实体单元的有效数据的数据量达到数据量门槛值时，停止从所述至少一第二实体单元中收集有效数据，且继续从所述至少一第一实体单元中收集有效数据。Exemplary embodiments of the present invention provide a data consolidation method for a rewritable non-volatile memory module, wherein the rewritable non-volatile memory module includes a plurality of physical units. The data consolidation method includes: selecting at least one first physical unit and at least one second physical unit from the physical units; reading first mapping information from the rewritable non-volatile memory module, wherein The first mapping information includes the mapping information of the at least one first physical unit and the mapping information of the at least one second physical unit; according to the first mapping information, from the at least one first physical unit The collected valid data and the collected valid data from the at least one second physical unit are copied to at least one third physical unit of the physical units; and when copied from the at least one second physical unit to all the physical units When the data volume of the valid data of the at least one third physical unit reaches the data volume threshold, stop collecting valid data from the at least one second physical unit, and continue to collect valid data from the at least one first physical unit .
在本发明的一范例实施例中，所述至少一第三实体单元的大小为目标数据量，且所述数据量门槛值为所述目标数据量减去所述至少一第一实体单元中的有效数据的总数据量所获得的剩余数据量。In an exemplary embodiment of the present invention, the size of the at least one third physical unit is a target data volume, and the data volume threshold value is the target data volume minus the at least one first physical unit in the The remaining amount of data obtained from the total amount of valid data.
在本发明的一范例实施例中，从所述至少一第一实体单元中收集的有效数据的第一数据量等于所述至少一第一实体单元中的有效数据的总数据量，从所述至少一第二实体单元中收集的有效数据的第二数据量小于所述至少一第二实体单元中的有效数据的总数据量。In an exemplary embodiment of the present invention, the first data volume of valid data collected from the at least one first physical unit is equal to the total data volume of valid data in the at least one first physical unit, from the The second data volume of the valid data collected in the at least one second physical unit is smaller than the total data volume of the valid data in the at least one second physical unit.
在本发明的一范例实施例中，所述第一数据量与所述第二数据量的总和为所述至少一第三实体单元的大小。In an exemplary embodiment of the present invention, the sum of the first data amount and the second data amount is the size of the at least one third physical unit.
在本发明的一范例实施例中，从所述可复写式非易失性存储器模块中读取所述第一映射信息之后的步骤包括：根据所述第一映射信息，识别所述至少一第一实体单元中的有效数据与所述至少一第二实体单元中的有效数据，每一所述至少一第一实体单元中的有效数据的数据量小于每一所述至少一第二实体单元中的有效数据的数据量。In an exemplary embodiment of the present invention, the step after reading the first mapping information from the rewritable non-volatile memory module includes: identifying the at least one first mapping information according to the first mapping information The valid data in one physical unit and the valid data in the at least one second physical unit, the data amount of the valid data in each of the at least one first physical unit is smaller than that in each of the at least one second physical unit The amount of valid data.
在本发明的一范例实施例中，当从所述至少一第二实体单元中复制到所述至少一第三实体单元的有效数据的数据量达到所述数据量门槛值时，停止从所述至少一第二实体单元中收集有效数据，且继续从所述至少一第一实体单元中收集有效数据的步骤包括：从所述可复写式非易失性存储器模块中读取第二映射信息，其中所述第二映射信息包含所述至少一第一实体单元的映射信息；以及根据所述第二映射信息，将从所述至少一第一实体单元中收集的有效数据复制到所述实体单元中的至少一第三实体单元。In an exemplary embodiment of the present invention, when the data volume of the valid data copied from the at least one second physical unit to the at least one third physical unit reaches the data volume threshold, stop copying from the at least one third physical unit. The step of collecting valid data from at least one second physical unit, and continuing to collect valid data from the at least one first physical unit includes: reading second mapping information from the rewritable non-volatile memory module, wherein the second mapping information includes mapping information of the at least one first physical unit; and according to the second mapping information, copying valid data collected from the at least one first physical unit to the physical unit at least one third entity unit in .
在本发明的一范例实施例中，其中第一表格映射信息反映所述至少一第一实体单元的映射信息记载于至少一第一逻辑至实体映射表，且第二表格映射信息反映所述至少一第二实体单元的映射信息记载于至少一第二逻辑至实体映射表，其中从所述可复写式非易失性存储器模块中读取所述第一映射信息的步骤包括：根据所述第一表格映射信息与所述第二表格映射信息读取所述第一映射信息，其中所述第一映射信息反映所述至少一第一逻辑至实体映射表与所述至少一第二逻辑至实体映射表之间的重叠信息。In an exemplary embodiment of the present invention, the mapping information of the first table reflects that the mapping information of the at least one first entity unit is recorded in at least one first logical-to-physical mapping table, and the mapping information of the second table reflects the at least one first physical unit. The mapping information of a second physical unit is recorded in at least one second logical-to-physical mapping table, wherein the step of reading the first mapping information from the rewritable non-volatile memory module includes: according to the first A table mapping information and the second table mapping information read the first mapping information, wherein the first mapping information reflects the at least one first logic-to-entity mapping table and the at least one second logic-to-entity mapping table Overlapping information between mapping tables.
本发明的范例实施例另提供一种存储器存储装置，其包括连接接口单元、可复写式非易失性存储器模块及存储器控制电路单元。所述连接接口单元用以连接至主机系统。所述可复写式非易失性存储器模块包括多个实体单元。所述存储器控制电路单元连接至所述连接接口单元与所述可复写式非易失性存储器模块。所述存储器控制电路单元用以从所述实体单元中选择至少一第一实体单元与至少一第二实体单元，所述第一映射信息包含所述至少一第一实体单元的映射信息与所述少一第二实体单元的映射信息。所述存储器控制电路单元还用以根据所述第一映射信息，将从所述至少一第一实体单元中收集的有效数据与从所述至少一第二实体单元中的收集的有效数据复制到所述实体单元中的至少一第三实体单元，以及所述存储器控制电路单元还用以当从所述至少一第二实体单元中复制到所述至少一第三实体单元的有效数据的数据量达到数据量门槛值时，停止从所述至少一第二实体单元中收集有效数据，且继续从所述至少一第一实体单元中收集有效数据。Exemplary embodiments of the present invention further provide a memory storage device, which includes a connection interface unit, a rewritable non-volatile memory module, and a memory control circuit unit. The connection interface unit is used for connecting to the host system. The rewritable non-volatile memory module includes a plurality of physical units. The memory control circuit unit is connected to the connection interface unit and the rewritable nonvolatile memory module. The memory control circuit unit is used for selecting at least one first physical unit and at least one second physical unit from the physical units, and the first mapping information includes the mapping information of the at least one first physical unit and the One less mapping information of the second entity unit. The memory control circuit unit is further configured to copy the valid data collected from the at least one first physical unit and the valid data collected from the at least one second physical unit to the first mapping information. At least one third physical unit in the physical units, and the memory control circuit unit is also used for the data amount of the valid data copied from the at least one second physical unit to the at least one third physical unit When the data volume threshold is reached, the collection of valid data from the at least one second physical unit is stopped, and the collection of valid data from the at least one first physical unit is continued.
在本发明的一范例实施例中，所述至少一第三实体单元的大小为目标数据量，且所述数据量门槛值为所述目标数据量减去所述至少一第一实体单元中的有效数据的总数据量所获得的剩余数据量。In an exemplary embodiment of the present invention, the size of the at least one third physical unit is a target data volume, and the data volume threshold value is the target data volume minus the at least one first physical unit in the The remaining amount of data obtained from the total amount of valid data.
在本发明的一范例实施例中，从所述至少一第一实体单元中收集的有效数据的第一数据量等于所述至少一第一实体单元中的有效数据的总数据量，从所述至少一第二实体单元中收集的有效数据的第二数据量小于所述至少一第二实体单元中的有效数据的总数据量。In an exemplary embodiment of the present invention, the first data volume of valid data collected from the at least one first physical unit is equal to the total data volume of valid data in the at least one first physical unit, from the The second data volume of the valid data collected in the at least one second physical unit is smaller than the total data volume of the valid data in the at least one second physical unit.
在本发明的一范例实施例中，所述第一数据量与所述第二数据量的总和为所述至少一第三实体单元的大小。In an exemplary embodiment of the present invention, the sum of the first data amount and the second data amount is the size of the at least one third physical unit.
在本发明的一范例实施例中，从所述可复写式非易失性存储器模块中读取所述第一映射信息之后的操作包括：根据所述第一映射信息，识别所述至少一第一实体单元中的有效数据与所述至少一第二实体单元中的有效数据，其中每一所述至少一第一实体单元中的有效数据的数据量小于每一所述至少一第二实体单元中的有效数据的数据量。In an exemplary embodiment of the present invention, the operation after reading the first mapping information from the rewritable non-volatile memory module includes: identifying the at least one first mapping information according to the first mapping information The valid data in a physical unit and the valid data in the at least one second physical unit, wherein the data amount of the valid data in each of the at least one first physical unit is smaller than that of each of the at least one second physical unit The amount of valid data in .
在本发明的一范例实施例中，当从所述至少一第二实体单元中复制到所述至少一第三实体单元的有效数据的数据量达到所述数据量门槛值时，停止从所述至少一第二实体单元中收集有效数据，且继续从所述至少一第一实体单元中收集有效数据的操作包括：从所述可复写式非易失性存储器模块中读取第二映射信息，其中所述第二映射信息包含所述至少一第一实体单元的映射信息；以及根据所述第二映射信息，将从所述至少一第一实体单元中收集的有效数据复制到所述实体单元中的至少一第三实体单元。In an exemplary embodiment of the present invention, when the data volume of the valid data copied from the at least one second physical unit to the at least one third physical unit reaches the data volume threshold, stop copying from the at least one third physical unit. The operation of collecting valid data from at least one second physical unit, and continuing to collect valid data from the at least one first physical unit includes: reading second mapping information from the rewritable non-volatile memory module, wherein the second mapping information includes mapping information of the at least one first physical unit; and according to the second mapping information, copying valid data collected from the at least one first physical unit to the physical unit at least one third entity unit in .
在本发明的一范例实施例中，第一表格映射信息反映所述至少一第一实体单元的映射信息记载于至少一第一逻辑至实体映射表，且第二表格映射信息反映所述至少一第二实体单元的映射信息记载于至少一第二逻辑至实体映射表，其中从所述可复写式非易失性存储器模块中读取所述第一映射信息的操作包括：根据所述第一表格映射信息与所述第二表格映射信息读取所述第一映射信息，其中所述第一映射信息反映所述至少一第一逻辑至实体映射表与所述至少一第二逻辑至实体映射表之间的重叠信息。In an exemplary embodiment of the present invention, the first table mapping information reflects that the mapping information of the at least one first entity unit is recorded in at least one first logical-to-physical mapping table, and the second table mapping information reflects the at least one The mapping information of the second physical unit is recorded in at least one second logical-to-physical mapping table, wherein the operation of reading the first mapping information from the rewritable non-volatile memory module includes: according to the first Table mapping information and the second table mapping information read the first mapping information, wherein the first mapping information reflects the at least one first logic-to-entity mapping table and the at least one second logic-to-entity mapping Overlapping information between tables.
本发明的范例实施例另提供一种存储器控制电路单元，其用于控制可复写式非易失性存储器模块。所述可复写式非易失性存储器模块包括多个实体单元。所述存储器控制电路单元包括主机接口、存储器接口及存储器管理电路。所述主机接口用以连接至主机系统。所述存储器接口用以连接至所述可复写式非易失性存储器模块。所述存储器管理电路连接至所述主机接口与所述存储器接口。所述存储器管理电路用以从所述可复写式非易失性存储器模块中读取第一映射信息，其中所述第一映射信息包含所述至少一第一实体单元的映射信息与所述少一第二实体单元的映射信息。所述存储器管理电路还用以根据所述第一映射信息，将从所述至少一第一实体单元中收集的有效数据与从所述至少一第二实体单元中的收集的有效数据复制到所述实体单元中的至少一第三实体单元，以及所述存储器管理电路还用以当从所述至少一第二实体单元中复制到所述至少一第三实体单元的有效数据的数据量达到数据量门槛值时，停止从所述至少一第二实体单元中收集有效数据，且继续从所述至少一第一实体单元中收集有效数据。Exemplary embodiments of the present invention further provide a memory control circuit unit for controlling a rewritable non-volatile memory module. The rewritable non-volatile memory module includes a plurality of physical units. The memory control circuit unit includes a host interface, a memory interface and a memory management circuit. The host interface is used to connect to a host system. The memory interface is used to connect to the rewritable non-volatile memory module. The memory management circuit is connected to the host interface and the memory interface. The memory management circuit is used for reading first mapping information from the rewritable non-volatile memory module, wherein the first mapping information includes the mapping information of the at least one first physical unit and the few A mapping information of the second entity unit. The memory management circuit is further configured to copy the valid data collected from the at least one first physical unit and the valid data collected from the at least one second physical unit to all the valid data according to the first mapping information. at least one third physical unit in the physical units, and the memory management circuit is further used for when the data amount of the valid data copied from the at least one second physical unit to the at least one third physical unit reaches the data When the threshold value is reached, the collection of valid data from the at least one second physical unit is stopped, and the collection of valid data from the at least one first physical unit is continued.
在本发明的一范例实施例中，所述至少一第三实体单元的大小为目标数据量，且所述数据量门槛值为所述目标数据量减去所述至少一第一实体单元中的有效数据的总数据量所获得的剩余数据量。In an exemplary embodiment of the present invention, the size of the at least one third physical unit is a target data volume, and the data volume threshold value is the target data volume minus the at least one first physical unit in the The remaining amount of data obtained from the total amount of valid data.
在本发明的一范例实施例中，从所述至少一第一实体单元中收集的有效数据的第一数据量等于所述至少一第一实体单元中的有效数据的总数据量，从所述至少一第二实体单元中收集的有效数据的第二数据量小于所述至少一第二实体单元中的有效数据的总数据量。In an exemplary embodiment of the present invention, the first data volume of valid data collected from the at least one first physical unit is equal to the total data volume of valid data in the at least one first physical unit, from the The second data volume of the valid data collected in the at least one second physical unit is smaller than the total data volume of the valid data in the at least one second physical unit.
在本发明的一范例实施例中，所述第一数据量与所述第二数据量的总和为所述至少一第三实体单元的大小。In an exemplary embodiment of the present invention, the sum of the first data amount and the second data amount is the size of the at least one third physical unit.
在本发明的一范例实施例中，从所述可复写式非易失性存储器模块中读取所述第一映射信息之后的操作包括：根据所述第一映射信息，识别所述至少一第一实体单元中的有效数据与所述至少一第二实体单元中的有效数据，其中每一所述至少一第一实体单元中的有效数据的数据量小于每一所述至少一第二实体单元中的有效数据的数据量。In an exemplary embodiment of the present invention, the operation after reading the first mapping information from the rewritable non-volatile memory module includes: identifying the at least one first mapping information according to the first mapping information The valid data in a physical unit and the valid data in the at least one second physical unit, wherein the data amount of the valid data in each of the at least one first physical unit is smaller than that of each of the at least one second physical unit The amount of valid data in .
在本发明的一范例实施例中，当从所述至少一第二实体单元中复制到所述至少一第三实体单元的有效数据的数据量达到所述数据量门槛值时，停止从所述至少一第二实体单元中收集有效数据，且继续从所述至少一第一实体单元中收集有效数据的操作包括：从所述可复写式非易失性存储器模块中读取第二映射信息，其中所述第二映射信息包含所述至少一第一实体单元的映射信息；以及根据所述第二映射信息，将从所述至少一第一实体单元中收集的有效数据复制到所述实体单元中的至少一第三实体单元。In an exemplary embodiment of the present invention, when the data volume of the valid data copied from the at least one second physical unit to the at least one third physical unit reaches the data volume threshold, stop copying from the at least one third physical unit. The operation of collecting valid data from at least one second physical unit, and continuing to collect valid data from the at least one first physical unit includes: reading second mapping information from the rewritable non-volatile memory module, wherein the second mapping information includes mapping information of the at least one first physical unit; and according to the second mapping information, copying valid data collected from the at least one first physical unit to the physical unit at least one third entity unit in .
在本发明的一范例实施例中，第一表格映射信息反映所述至少一第一实体单元的映射信息记载于至少一第一逻辑至实体映射表，且第二表格映射信息反映所述至少一第二实体单元的映射信息记载于至少一第二逻辑至实体映射表，其中从所述可复写式非易失性存储器模块中读取所述第一映射信息的操作包括：根据所述第一表格映射信息与所述第二表格映射信息读取所述第一映射信息，其中所述第一映射信息反映所述至少一第一逻辑至实体映射表与所述至少一第二逻辑至实体映射表之间的重叠信息。In an exemplary embodiment of the present invention, the first table mapping information reflects that the mapping information of the at least one first entity unit is recorded in at least one first logical-to-physical mapping table, and the second table mapping information reflects the at least one The mapping information of the second physical unit is recorded in at least one second logical-to-physical mapping table, wherein the operation of reading the first mapping information from the rewritable non-volatile memory module includes: according to the first Table mapping information and the second table mapping information read the first mapping information, wherein the first mapping information reflects the at least one first logic-to-entity mapping table and the at least one second logic-to-entity mapping Overlapping information between tables.
基于上述，存储器管理电路可利用至少一第一实体单元与至少一第二实体单元两者共用的映射信息，同时将至少一第一实体单元与至少一第二实体单元中的有效数据复制到回收节点的至少一第三实体单元，并且通过设置数据量门槛值来限制从来源节点中有效数据的数据量相对较多的至少一第二实体单元复制到回收节点的数据量，以避免数据整并操作中存取至少一第一实体单元与至少一第二实体单元所使用的逻辑至实体映射表被重复地读取。由此可有效地减少数据整并操作中存储器存储装置的存取次数，进而提升存储器存储装置的整体运作效能。Based on the above, the memory management circuit can use the mapping information shared by the at least one first physical unit and the at least one second physical unit, and at the same time copy the valid data in the at least one first physical unit and the at least one second physical unit to the recycling At least one third entity unit of the node, and by setting a data volume threshold value to limit the amount of data copied from at least one second entity unit with a relatively large amount of valid data in the source node to the recycling node, so as to avoid data consolidation The logic-to-physical mapping table used to access at least one first physical unit and at least one second physical unit during the operation is repeatedly read. Therefore, the access times of the memory storage device in the data consolidation operation can be effectively reduced, thereby improving the overall operation performance of the memory storage device.
为让本发明的上述特征和优点能更明显易懂，下文特举实施例，并配合附图作详细说明如下。In order to make the above-mentioned features and advantages of the present invention more obvious and easy to understand, the following embodiments are given and described in detail with the accompanying drawings as follows.
附图说明Description of drawings
包含附图以便进一步理解本发明，且附图并入本说明书中并构成本说明书的一部分。附图说明本发明的实施例，并与描述一起用于解释本发明的原理。The accompanying drawings are included to provide a further understanding of the present invention, and are incorporated in and constitute a part of this specification. The drawings illustrate embodiments of the invention and together with the description serve to explain the principles of the invention.
图1是根据本发明的一范例实施例所示出的主机系统、存储器存储装置及输入/输出(I/O)装置的示意图；1 is a schematic diagram of a host system, a memory storage device, and an input/output (I/O) device according to an exemplary embodiment of the present invention;
图2是根据本发明的另一范例实施例所示出的主机系统、存储器存储装置及I/O装置的示意图；2 is a schematic diagram of a host system, a memory storage device, and an I/O device according to another exemplary embodiment of the present invention;
图3是根据本发明的另一范例实施例所示出的主机系统与存储器存储装置的示意图；3 is a schematic diagram of a host system and a memory storage device according to another exemplary embodiment of the present invention;
图4是根据本发明的一范例实施例所示出的存储器存储装置的概要方块图；4 is a schematic block diagram of a memory storage device according to an exemplary embodiment of the present invention;
图5是根据本发明的一范例实施例所示出的存储器控制电路单元的概要方块图；5 is a schematic block diagram of a memory control circuit unit according to an exemplary embodiment of the present invention;
图6是根据本发明的一范例实施例所示出的管理可复写式非易失性存储器模块的示意图；FIG. 6 is a schematic diagram of managing a rewritable non-volatile memory module according to an exemplary embodiment of the present invention;
图7A至图7C是根据本发明的一范例实施例所示出的数据整并操作的示意图；7A to 7C are schematic diagrams illustrating a data consolidation operation according to an exemplary embodiment of the present invention;
图8是根据本发明的一范例实施例所示出的表格映射信息的示意图；8 is a schematic diagram of table mapping information according to an exemplary embodiment of the present invention;
图9A至图9B是根据本发明的一范例实施例所示出的根据映射信息获得逻辑至实体映射表的示意图；9A to 9B are schematic diagrams of obtaining a logic-to-entity mapping table according to mapping information according to an exemplary embodiment of the present invention;
图10A至图10B是根据传统的数据整并操作所示出的根据映射信息获得逻辑至实体映射表的示意图；10A to 10B are schematic diagrams illustrating obtaining a logic-to-entity mapping table according to mapping information according to a conventional data consolidation operation;
图11是根据本发明的一范例实施例所示出的数据整并方法的流程图。FIG. 11 is a flowchart of a data consolidation method according to an exemplary embodiment of the present invention.
附图标记说明Description of reference numerals
10、30：存储器存储装置；10, 30: memory storage device;
11、31：主机系统；11, 31: host system;
110：系统总线；110: system bus;
111：处理器；111: processor;
112：随机存取存储器；112: random access memory;
113：只读存储器；113: read-only memory;
114：数据传输接口；114: data transmission interface;
12：输入/输出(I/O)装置；12: Input/output (I/O) device;
20：主机板；20: motherboard;
201：U盘；201: U disk;
202：存储卡；202: memory card;
203：固态硬盘；203: SSD;
204：无线存储器存储装置；204: wireless memory storage device;
205：全球定位系统模块；205: GPS module;
206：网络接口卡；206: network interface card;
207：无线传输装置；207: wireless transmission device;
208：键盘；208: keyboard;
209：屏幕；209: screen;
210：喇叭；210: horn;
32：SD卡；32: SD card;
33：CF卡；33: CF card;
34：嵌入式存储装置；34: embedded storage device;
341：嵌入式多媒体卡；341: embedded multimedia card;
342：嵌入式多芯片封装存储装置；342: an embedded multi-chip package storage device;
402：连接接口单元；402: connect the interface unit;
404：存储器控制电路单元；404: memory control circuit unit;
406：可复写式非易失性存储器模块；406: rewritable non-volatile memory module;
502：存储器管理电路；502: memory management circuit;
504：主机接口；504: host interface;
506：存储器接口；506: memory interface;
508：错误检查与校正电路；508: Error checking and correction circuit;
510：缓冲存储器；510: buffer memory;
512：电源管理电路；512: power management circuit;
601：存储区；601: storage area;
602：替换区；602: replacement area;
603：系统区；603: system area;
610(0)～610(C)、710(0)～710(3)、720(0)、810(0)～810(1)：实体单元；610(0)～610(C), 710(0)～710(3), 720(0), 810(0)～810(1): entity units;
612(0)～612(D)：逻辑单元；612(0)～612(D): logic unit;
700A、700B：数据；700A, 700B: data;
701：来源节点；701: source node;
702：回收节点；702: recycling node;
801、802、910(0)～910(3)：表格映射信息；801, 802, 910(0)~910(3): table mapping information;
830：逻辑至实体映射表；830: logic to entity mapping table;
901、902、1001：映射信息；901, 902, 1001: mapping information;
90：逻辑模块；90: logic module;
S1101：步骤(从实体单元中选择至少一第一实体单元与至少一第二实体单元)；S1101: step (select at least one first entity unit and at least one second entity unit from entity units);
S1103：步骤(从所述可复写式非易失性存储器模块中读取第一映射信息，其中所述第一映射信息包含所述至少一第一实体单元的映射信息与所述少一第二实体单元的映射信息)；S1103: Step (read first mapping information from the rewritable non-volatile memory module, wherein the first mapping information includes the mapping information of the at least one first physical unit and the at least one second mapping information of the entity unit);
S1105：步骤(根据所述第一映射信息，将从所述至少一第一实体单元中收集的有效数据与从所述至少一第二实体单元中的收集的有效数据复制到所述实体单元中的至少一第三实体单元)；S1105: Step (according to the first mapping information, copy the valid data collected from the at least one first physical unit and the valid data collected from the at least one second physical unit to the physical unit at least one third entity unit);
S1107：步骤(当从所述至少一第二实体单元中复制到所述至少一第三实体单元的有效数据的数据量达到数据量门槛值时，停止从所述至少一第二实体单元中收集有效数据，且继续从所述至少一第一实体单元中收集有效数据)。S1107: Step (when the data volume of the valid data copied from the at least one second physical unit to the at least one third physical unit reaches a data volume threshold, stop collecting from the at least one second physical unit valid data, and continue to collect valid data from the at least one first physical unit).
具体实施方式Detailed ways
一般而言，存储器存储装置(亦称，存储器存储系统)包括可复写式非易失性存储器模块(rewritable non-volatile memory module)与控制器(亦称，控制电路)。通常存储器存储装置是与主机系统一起使用，以使主机系统可将数据写入至存储器存储装置或从存储器存储装置中读取数据。Generally, a memory storage device (also called a memory storage system) includes a rewritable non-volatile memory module and a controller (also called a control circuit). Typically a memory storage device is used with a host system so that the host system can write data to or read data from the memory storage device.
图1是根据本发明的一范例实施例所示出的主机系统、存储器存储装置及输入/输出(I/O)装置的示意图。图2是根据本发明的另一范例实施例所示出的主机系统、存储器存储装置及I/O装置的示意图。FIG. 1 is a schematic diagram of a host system, a memory storage device, and an input/output (I/O) device according to an exemplary embodiment of the present invention. FIG. 2 is a schematic diagram of a host system, a memory storage device, and an I/O device according to another exemplary embodiment of the present invention.
请参照图1与图2，主机系统11一般包括处理器111、随机存取存储器(randomaccess memory,RAM)112、只读存储器(read only memory,ROM)113及数据传输接口114。处理器111、随机存取存储器112、只读存储器113及数据传输接口114皆连接至系统总线(system bus)110。Referring to FIGS. 1 and 2 , the
在本范例实施例中，主机系统11是通过数据传输接口114与存储器存储装置10连接。例如，主机系统11可经由数据传输接口114将数据存储至存储器存储装置10或从存储器存储装置10中读取数据。此外，主机系统11是通过系统总线110与I/O装置12连接。例如，主机系统11可经由系统总线110将输出信号传送至I/O装置12或从I/O装置12接收输入信号。In this exemplary embodiment, the
在本范例实施例中，处理器111、随机存取存储器112、只读存储器113及数据传输接口114可设置在主机系统11的主机板20上。数据传输接口114的数目可以是一或多个。通过数据传输接口114，主机板20可以经由有线或无线方式连接至存储器存储装置10。存储器存储装置10可例如是U盘201、存储卡202、固态硬盘(Solid State Drive,SSD)203或无线存储器存储装置204。无线存储器存储装置204可例如是近距离无线通信(Near FieldCommunication,NFC)存储器存储装置、无线传真(WiFi)存储器存储装置、蓝牙(Bluetooth)存储器存储装置或低功耗蓝牙存储器存储装置(例如，iBeacon)等以各式无线通信技术为基础的存储器存储装置。此外，主机板20也可以通过系统总线110连接至全球定位系统(Global Positioning System,GPS)模块205、网络接口卡206、无线传输装置207、键盘208、屏幕209、喇叭210等各式I/O装置。例如，在一范例实施例中，主机板20可通过无线传输装置207存取无线存储器存储装置204。In this exemplary embodiment, the
在一范例实施例中，所提及的主机系统为可实质地与存储器存储装置配合以存储数据的任意系统。虽然在上述范例实施例中，主机系统是以电脑系统来作说明，然而，图3是根据本发明的另一范例实施例所示出的主机系统与存储器存储装置的示意图。请参照图3，在另一范例实施例中，主机系统31也可以是数码相机、摄像机、通信装置、音频播放器、视频播放器或平板电脑等系统，而存储器存储装置30可为其所使用的安全数字(SecureDigital,SD)卡32、小型快闪(Compact Flash,CF)卡33或嵌入式存储装置34等各式非易失性存储器存储装置。嵌入式存储装置34包括嵌入式多媒体卡(embedded Multi MediaCard,eMMC)341和/或嵌入式多芯片封装(embedded Multi Chip Package,eMCP)存储装置342等各类型将存储器模块直接连接于主机系统的基板上的嵌入式存储装置。In an example embodiment, reference to a host system is substantially any system that can cooperate with a memory storage device to store data. Although in the above exemplary embodiment, the host system is described as a computer system, FIG. 3 is a schematic diagram of a host system and a memory storage device according to another exemplary embodiment of the present invention. Referring to FIG. 3 , in another exemplary embodiment, the
图4是根据本发明的一范例实施例所示出的存储器存储装置的概要方块图。4 is a schematic block diagram of a memory storage device according to an exemplary embodiment of the present invention.
请参照图4，存储器存储装置10包括连接接口单元402、存储器控制电路单元404与可复写式非易失性存储器模块406。Referring to FIG. 4 , the
连接接口单元402用以将存储器存储装置10连接至主机系统11。存储器存储装置10可通过连接接口单元402与主机系统11通信。在本范例实施例中，连接接口单元402是相容于串行高级技术附件(Serial Advanced Technology Attachment,SATA)标准。然而，必须了解的是，本发明不限于此，连接接口单元402亦可以是符合并行高级技术附件(Parallel Advanced Technology Attachment,PATA)标准、电气和电子工程师协会(Institute of Electrical and Electronic Engineers,IEEE)1394标准、高速周边零件连接接口(Peripheral Component Interconnect Express,PCI Express)标准、通用串行总线(Universal Serial Bus,USB)标准、SD接口标准、超高速一代(Ultra High Speed-I,UHS-I)接口标准、超高速二代(Ultra High Speed-II,UHS-II)接口标准、存储棒(MemoryStick,MS)接口标准、MCP接口标准、MMC接口标准、eMMC接口标准、通用快闪存储器(Universal Flash Storage,UFS)接口标准、eMCP接口标准、CF接口标准、整合式驱动电子接口(Integrated Device Electronics,IDE)标准或其他适合的标准。连接接口单元402可与存储器控制电路单元404封装在一个芯片中，或者连接接口单元402是布设于一包含存储器控制电路单元404的芯片外。The
存储器控制电路单元404用以执行以硬件型式或固件型式实作的多个逻辑门或控制指令并且根据主机系统11的指令在可复写式非易失性存储器模块406中进行数据的写入、读取与抹除等运作。The memory
可复写式非易失性存储器模块406是连接至存储器控制电路单元404并且用以存储主机系统11所写入的数据。可复写式非易失性存储器模块406可以是单阶存储单元(Single Level Cell,SLC)NAND型快闪存储器模块(即，一个存储单元中可存储1个比特的快闪存储器模块)、多阶存储单元(Multi Level Cell,MLC)NAND型快闪存储器模块(即，一个存储单元中可存储2个比特的快闪存储器模块)、三阶存储单元(Triple Level Cell，TLC)NAND型快闪存储器模块(即，一个存储单元中可存储3个比特的快闪存储器模块)、四阶存储单元(Quad Level Cell，TLC)NAND型快闪存储器模块(即，一个存储单元中可存储4个比特的快闪存储器模块)、其他快闪存储器模块或其他具有相同特性的存储器模块。The rewritable
可复写式非易失性存储器模块406中的每一个存储单元是以电压(以下亦称为临界电压)的改变来存储一或多个比特。具体来说，每一个存储单元的控制栅极(controlgate)与通道之间有一个电荷捕捉层。通过施予一写入电压至控制栅极，可以改变电荷补捉层的电子量，进而改变存储单元的临界电压。此改变存储单元的临界电压的操作亦称为“把数据写入至存储单元”或“程序化(programming)存储单元”。随着临界电压的改变，可复写式非易失性存储器模块406中的每一个存储单元具有多个存储状态。通过施予读取电压可以判断一个存储单元是属于哪一个存储状态，藉此取得此存储单元所存储的一或多个比特。Each memory cell in the rewritable
在本范例实施例中，可复写式非易失性存储器模块406的存储单元可构成多个实体程序化单元，并且此些实体程序化单元可构成多个实体抹除单元。具体来说，同一条字线上的存储单元可组成一或多个实体程序化单元。若每一个存储单元可存储2个以上的比特，则同一条字线上的实体程序化单元可至少可被分类为下实体程序化单元与上实体程序化单元。例如，一存储单元的最低有效比特(Least Significant Bit，LSB)是属于下实体程序化单元，并且一存储单元的最高有效比特(Most Significant Bit，MSB)是属于上实体程序化单元。一般来说，在MLC NAND型快闪存储器中，下实体程序化单元的写入速度会大于上实体程序化单元的写入速度，和/或下实体程序化单元的可靠度是高于上实体程序化单元的可靠度。In this exemplary embodiment, the storage units of the rewritable
在本范例实施例中，实体程序化单元为程序化的最小单元。即，实体程序化单元为写入数据的最小单元。例如，实体程序化单元可为实体页面(page)或是实体扇(sector)。若实体程序化单元为实体页面，则此些实体程序化单元可包括数据比特区与冗余(redundancy)比特区。数据比特区包含多个实体扇，用以存储使用者数据，而冗余比特区用以存储系统数据(例如，错误更正码等管理数据)。在本范例实施例中，数据比特区包含32个实体扇，且一个实体扇的大小为512字节(byte,B)。然而，在其他范例实施例中，数据比特区中也可包含8个、16个或数目更多或更少的实体扇，并且每一个实体扇的大小也可以是更大或更小。另一方面，实体抹除单元为抹除的最小单位。亦即，每一实体抹除单元含有最小数目之一并被抹除的存储单元。例如，实体抹除单元为实体区块(block)。In this exemplary embodiment, the physical programming unit is the smallest unit of programming. That is, the physical programming unit is the smallest unit in which data is written. For example, the physical programming unit may be a physical page or a physical sector. If the physical programming unit is a physical page, the physical programming unit may include a data bit area and a redundancy bit area. The data bit area includes a plurality of physical sectors for storing user data, and the redundant bit area is used for storing system data (eg, management data such as error correction codes). In this exemplary embodiment, the data bit area includes 32 physical sectors, and the size of one physical sector is 512 bytes (byte, B). However, in other exemplary embodiments, the data bit region may also include 8, 16, or more or less physical sectors, and the size of each physical sector may also be larger or smaller. On the other hand, the physical erasing unit is the smallest unit of erasing. That is, each physical erase unit contains a minimum number of memory units that are erased. For example, the physical erasing unit is a physical block.
图5是根据本发明的一范例实施例所示出的存储器控制电路单元的概要方块图。FIG. 5 is a schematic block diagram of a memory control circuit unit according to an exemplary embodiment of the present invention.
请参照图5，存储器控制电路单元404包括存储器管理电路502、主机接口504及存储器接口506。Referring to FIG. 5 , the memory
存储器管理电路502用以控制存储器控制电路单元404的整体运作。具体来说，存储器管理电路502具有多个控制指令，并且在存储器存储装置10运作时，此些控制指令会被执行以进行数据的写入、读取与抹除等运作。以下说明存储器管理电路502的操作时，等同于说明存储器控制电路单元404的操作。The
在本范例实施例中，存储器管理电路502的控制指令是以固件型式来实作。例如，存储器管理电路502具有微处理器单元(未示出)与只读存储器(未示出)，并且此些控制指令是被烧录至此只读存储器中。当存储器存储装置10运作时，此些控制指令会由微处理器单元来执行以进行数据的写入、读取与抹除等运作。In this exemplary embodiment, the control commands of the
在另一范例实施例中，存储器管理电路502的控制指令亦可以程序码型式存储于可复写式非易失性存储器模块406的特定区域(例如，存储器模块中专用于存放系统数据的系统区)中。此外，存储器管理电路502具有微处理器单元(未示出)、只读存储器(未示出)及随机存取存储器(未示出)。特别是，此只读存储器具有开机码(boot code)，并且当存储器控制电路单元404被致能时，微处理器单元会先执行此开机码来将存储于可复写式非易失性存储器模块406中的控制指令载入至存储器管理电路502的随机存取存储器中。之后，微处理器单元会运转此些控制指令以进行数据的写入、读取与抹除等运作。In another exemplary embodiment, the control commands of the
此外，在另一范例实施例中，存储器管理电路502的控制指令亦可以一硬件型式来实作。例如，存储器管理电路502包括微控制器、存储单元管理电路、存储器写入电路、存储器读取电路、存储器抹除电路与数据处理电路。存储单元管理电路、存储器写入电路、存储器读取电路、存储器抹除电路与数据处理电路是连接至微控制器。存储单元管理电路用以管理可复写式非易失性存储器模块406的存储单元或存储单元群组。存储器写入电路用以对可复写式非易失性存储器模块406下达写入指令序列以将数据写入至可复写式非易失性存储器模块406中。存储器读取电路用以对可复写式非易失性存储器模块406下达读取指令序列以从可复写式非易失性存储器模块406中读取数据。存储器抹除电路用以对可复写式非易失性存储器模块406下达抹除指令序列以将数据从可复写式非易失性存储器模块406中抹除。数据处理电路用以处理欲写入至可复写式非易失性存储器模块406的数据以及从可复写式非易失性存储器模块406中读取的数据。写入指令序列、读取指令序列及抹除指令序列可各别包括一或多个程序码或指令码并且用以指示可复写式非易失性存储器模块406执行相对应的写入、读取及抹除等操作。在一范例实施例中，存储器管理电路502还可以下达其他类型的指令序列给可复写式非易失性存储器模块406以指示执行相对应的操作。In addition, in another exemplary embodiment, the control commands of the
主机接口504是连接至存储器管理电路502。存储器管理电路502可通过主机接口504与主机系统11通信。主机接口504可用以接收与识别主机系统11所传送的指令与数据。例如，主机系统11所传送的指令与数据可通过主机接口504来传送至存储器管理电路502。此外，存储器管理电路502可通过主机接口504将数据传送至主机系统11。在本范例实施例中，主机接口504是相容于SATA标准。然而，必须了解的是本发明不限于此，主机接口504亦可以是相容于PATA标准、IEEE 1394标准、PCI Express标准、USB标准、SD标准、UHS-I标准、UHS-II标准、MS标准、MMC标准、eMMC标准、UFS标准、CF标准、IDE标准或其他适合的数据传输标准。The
存储器接口506是连接至存储器管理电路502并且用以存取可复写式非易失性存储器模块406。也就是说，欲写入至可复写式非易失性存储器模块406的数据会经由存储器接口506转换为可复写式非易失性存储器模块406所能接受的格式。具体来说，若存储器管理电路502要存取可复写式非易失性存储器模块406，存储器接口506会传送对应的指令序列。例如，这些指令序列可包括指示写入数据的写入指令序列、指示读取数据的读取指令序列、指示抹除数据的抹除指令序列、以及用以指示各种存储器操作(例如，改变读取电压电平或执行垃圾回收操作等等)的相对应的指令序列。这些指令序列例如是由存储器管理电路502产生并且通过存储器接口506传送至可复写式非易失性存储器模块406。这些指令序列可包括一或多个信号，或是在总线上的数据。这些信号或数据可包括指令码或程序码。例如，在读取指令序列中，会包括读取的识别码、存储器地址等信息。The
在一范例实施例中，存储器控制电路单元404还包括错误检查与校正电路508、缓冲存储器510与电源管理电路512。In an exemplary embodiment, the memory
错误检查与校正电路508是连接至存储器管理电路502并且用以执行错误检查与校正操作以确保数据的正确性。具体来说，当存储器管理电路502从主机系统11中接收到写入指令时，错误检查与校正电路508会为对应此写入指令的数据产生对应的错误更正码(error correcting code,ECC)和/或错误检查码(error detecting code，EDC)，并且存储器管理电路502会将对应此写入指令的数据与对应的错误更正码和/或错误检查码写入至可复写式非易失性存储器模块406中。之后，当存储器管理电路502从可复写式非易失性存储器模块406中读取数据时会同时读取此数据对应的错误更正码和/或错误检查码，并且错误检查与校正电路508会依据此错误更正码和/或错误检查码对所读取的数据执行错误检查与校正操作。The error checking and
缓冲存储器510是连接至存储器管理电路502并且用以暂存来自于主机系统11的数据与指令或来自于可复写式非易失性存储器模块406的数据。电源管理电路512是连接至存储器管理电路502并且用以控制存储器存储装置10的电源。The
在一范例实施例中，图4的可复写式非易失性存储器模块406亦称为快闪(flash)存储器模块，存储器控制电路单元404亦称为用于控制快闪存储器模块的快闪存储器控制器，和/或图5的存储器管理电路502亦称为快闪存储器管理电路。In an exemplary embodiment, the rewritable
图6是根据本发明的一范例实施例所示出的管理可复写式非易失性存储器模块的示意图。FIG. 6 is a schematic diagram of managing a rewritable non-volatile memory module according to an exemplary embodiment of the present invention.
请参照图6，存储器管理电路502可将可复写式非易失性存储器模块406的实体单元610(0)～610(C)逻辑地分组至存储区601、闲置(spare)区602及系统区603。存储区601中的实体单元610(0)～610(A)存储有数据。例如，存储区601中的实体单元610(0)～610(A)可存储有效(valid)数据与无效(invalid)数据。闲置区602中的实体单元610(A+1)～610(B)尚未用来存储数据(例如有效数据)。系统区603中的实体单元610(B+1)～610(C)用以存储系统数据，例如逻辑至实体映射表、坏块管理表、装置型号或其他类型的管理数据。6, the
存储器管理电路502可从闲置区602的实体单元610(A+1)～610(B)中选择一个实体单元并且将来自主机系统11或来自存储区601中至少一实体单元的数据存储至所选的实体单元中。同时，所选的实体单元会被关联至存储区601。此外，在抹除存储区601中的某一个实体单元后，所抹除的实体单元会被重新关联至闲置区602。The
在本范例实施例中，属于存储区601的每一个实体单元亦称为非闲置(non-spare)实体单元，而属于闲置区602的每一个实体单元亦称为闲置实体单元。在本范例实施例中，一个实体单元是指一个实体抹除单元。然而，在另一范例实施例中，一个实体单元亦可以包含多个实体抹除单元。In this exemplary embodiment, each physical unit belonging to the
存储器管理电路502可配置逻辑单元612(0)～612(D)以映射存储区601中的实体单元610(0)～610(A)。在本范例实施例中，每一个逻辑单元是指一个逻辑地址。然而，在另一范例实施例中，一个逻辑单元也可以是指一个逻辑程序化单元、一个逻辑抹除单元或者由多个连续或不连续的逻辑地址组成。此外，逻辑单元612(0)～612(D)中的每一者可被映射至一或多个实体单元。须注意的是，存储器管理电路502可不配置映射至系统区603的逻辑单元，以防止存储于系统区603的系统数据被使用者修改。The
存储器管理电路502会将逻辑单元与实体单元之间的映射信息(亦称为逻辑至实体映射信息)记录于至少一逻辑至实体映射表。此映射信息可反映存储区601中的某一个实体单元与某一个逻辑单元之间的映射关系。逻辑至实体映射表是存储于系统区603的实体单元610(B+1)～610(C)中。存储器管理电路502可根据此逻辑至实体映射表来执行对于存储器存储装置10的数据存取操作。例如，存储器管理电路502可根据某一个逻辑至实体映射表获得存储区601中的某一个实体单元与某一个逻辑单元之间的映射关系。存储器管理电路502可根据此映射关系存取此实体单元。The
在本范例实施例中，有效数据是属于某一个逻辑单元的最新数据，而无效数据则不是属于任一个逻辑单元的最新数据。例如，若主机系统11将一笔新数据存储至某一逻辑单元而覆盖掉此逻辑单元原先存储的旧数据(即，更新属于此逻辑单元的数据)，则存储至存储区601中的此笔新数据即为属于此逻辑单元的最新数据并且会被标记为有效，而被覆盖掉的旧数据可能仍然存储在存储区601中但被标记为无效。In this exemplary embodiment, the valid data is the latest data belonging to a certain logic unit, and the invalid data is not the latest data belonging to any logic unit. For example, if the
在本范例实施例中，若属于某一逻辑单元的数据被更新，则此逻辑单元与存储有属于此逻辑单元的旧数据的实体单元之间的映射关系会被移除，并且此逻辑单元与存储有属于此逻辑单元的最新数据的实体单元之间的映射关系会被建立。然而，在另一范例实施例中，若属于某一逻辑单元的数据被更新，则此逻辑单元与存储有属于此逻辑单元的旧数据的实体单元之间的映射关系仍可被维持。In this exemplary embodiment, if data belonging to a logical unit is updated, the mapping relationship between the logical unit and the physical unit storing the old data belonging to the logical unit will be removed, and the logical unit and the physical unit will be removed. The mapping relationship between the entity units that store the latest data belonging to this logical unit will be established. However, in another exemplary embodiment, if the data belonging to a certain logic unit is updated, the mapping relationship between the logic unit and the physical unit storing the old data belonging to the logic unit can still be maintained.
当存储器存储装置10出厂时，属于闲置区602的实体单元的总数会是一个预设数目(例如，30)。在存储器存储装置10的运作中，越来越多的实体单元会被从闲置区602选择并且被关联至存储区601以存储数据(例如，来自主机系统11的使用者数据)。因此，属于闲置区602的实体单元的总数可随着存储器存储装置10的使用而逐渐减少。When the
在存储器存储装置10的运作中，存储器管理电路502可持续更新属于闲置区602的实体单元的总数。存储器管理电路502可根据闲置区602中实体单元的数目(即，闲置实体单元的总数)执行数据整并操作。例如，存储器管理电路502可判断属于闲置区602的实体单元的总数是否小于或等于一个门槛值(亦称为第一门槛值)。此第一门槛值例如是2或者更大的值(例如，10)，本发明不加以限制。若属于闲置区602的实体单元的总数小于或等于第一门槛值，存储器管理电路502可执行数据整并操作。在一范例实施例中，数据整并操作亦称为垃圾收集(garbage collection)操作。During the operation of the
在数据整并操作中，存储器管理电路502可从存储区601中选择至少一个实体单元作为来源节点。存储器管理电路502可将有效数据从所选择的实体单元(即来源节点)复制到作为回收节点的至少一个实体单元。用来存储所复制的有效数据的实体单元(即回收节点)是从闲置区602中选择并且会被关联至存储区601。若某一个实体单元所存储的有效数据皆已被复制至回收节点，则此实体单元可被抹除并且被关联至闲置区602。在一范例实施例中，将某一个实体单元从存储区601重新关联回闲置区602的操作(或抹除某一个实体单元的操作)亦称为释放一个闲置实体单元。通过执行数据整并操作，一或多个闲置实体单元会被释放并且使得属于闲置区602的实体单元的总数逐渐增加。In the data consolidation operation, the
在开始执行数据整并操作后，若属于闲置区602的实体单元符合一特定条件，数据整并操作可被停止。例如，存储器管理电路502可判断属于闲置区602的实体单元的总数是否大于或等于一个门槛值(以下亦称为第二门槛值)。例如，第二门槛值可以大于或等于第一门槛值。若属于闲置区602的实体单元的总数大于或等于第二门槛值，存储器管理电路502可停止数据整并操作。须注意的是，停止数据整并操作是指结束当前执行中的数据整并操作。在停止一个数据整并操作之后，若属于闲置区602的实体单元的总数再次小于或等于第一门槛值，则下一个数据整并操作可再次被执行，以释放新的闲置实体单元。After the data consolidation operation is started, if the physical units belonging to the
图7A至图7C是根据本发明的一范例实施例所示出的数据整并操作的示意图。7A to 7C are schematic diagrams illustrating a data consolidation operation according to an exemplary embodiment of the present invention.
请先参照图7A，在本发明范例实施例的数据整并操作中，存储器管理电路502会从可复写式非易失性存储器模块406中存储区601的实体单元中选择多个实体单元710(0)～710(3)作为来源节点701，以及从闲置区602的实体单元中选择实体单元720(0)(亦称为至少一第三实体单元720(0))作为回收节点702。特别是，在本范例实施例中，所选择的多个实体单元710(0)～710(3)包括来源节点701中有效数据的数据量相对较少的实体单元710(0)～710(2)(亦称为至少一第一实体单元710(0)～710(2))，与来源节点701中有效数据的数据量相对较多的实体单元710(3)(亦称为至少一第二实体单元710(3))。换言之，每一至少一第一实体单元710(0)～710(2)中的有效数据的数据量小于每一至少一第二实体单元710(3)中的有效数据的数据量。Referring first to FIG. 7A , in the data consolidation operation of the exemplary embodiment of the present invention, the
接着，存储器管理电路502会从可复写式非易失性存储器模块406中读取包含至少一第一实体单元710(0)～710(2)与至少一第二实体单元710(3)两者共用的映射信息(亦称为第一映射信息)，即，第一映射信息包含至少一第一实体单元710(0)～710(2)的映射信息与少一第二实体单元710(3)的映射信息。存储器管理电路502会根据此第一映射信息，识别至少一第一实体单元710(0)～710(2)中的有效数据与至少一第二实体单元710(3)中的有效数据，并指示从作为来源节点701的至少一第一实体单元710(0)～710(2)中与至少一第二实体单元710(3)中收集两者的有效数据700A，进而将有效数据700A暂存于缓冲存储器510。之后，存储器管理电路502可指示将有效数据700A写入至作为回收节点702的至少一第三实体单元720(0)。亦即，存储器管理电路502会将从来源节点701的至少一第一实体单元710(0)～710(2)中收集的有效数据与从来源节点701的至少一第二实体单元710(3)中的收集的有效数据复制到回收节点702的至少一第三实体单元720(0)。Next, the
在一范例实施例中，存储器管理电路502会在从来源节点701的至少一第二实体单元710(3)中复制到至少一第三实体单元720(0)的有效数据的数据量达到数据量门槛值时，停止从来源节点701的至少一第二实体单元710(3)中收集有效数据，且继续从来源节点701的至少一第一实体单元710(0)～710(2)中收集有效数据。具体而言，回收节点702的至少一第三实体单元720(0)的大小可容纳的数据量为一目标数据量，且所述数据量门槛值为目标数据量减去至少一第一实体单元710(0)～710(2)中的有效数据的总数据量所获得的剩余数据量。换言之，在本发明的数据整并的操作中，存储器管理电路502会在回收节点702的至少一第三实体单元720(0)预留足够的空间使至少一第一实体单元710(0)～710(2)中的有效数据皆能被复制到回收节点702，而至少一第二实体单元710(3)中仅具剩余数据量大小的有效数据会被复制到回收节点702。也就是说，在本发明范例实施例中，从至少一第一实体单元710(0)～710(2)中收集的有效数据的数据量(亦称为第一数据量)等于至少一第一实体单元710(0)～710(2)中的有效数据的总数据量，从至少一第二实体单元710(3)中收集的有效数据的数据量(亦称为第二数据量)小于至少一第二实体单元710(3)中的有效数据的总数据量，且第一数据量与第二数据量的总和为至少一第三实体单元的大小。In an exemplary embodiment, the
值得注意的是，在上述存储器管理电路502从可复写式非易失性存储器模块406中读取包含至少一第一实体单元710(0)～710(2)与至少一第二实体单元710(3)两者共用的第一映射信息的操作中，存储器管理电路502是根据至少一第一实体单元710(0)～710(2)的表格映射信息(亦称为第一表格映射信息)与至少一第二实体单元710(3)的表格映射信息(亦称为第二表格映射信息)获得所述第一映射信息。以下将参照图8来说明如何获得实体单元之间共同的映射信息。It is worth noting that the
图8是根据本发明的一范例实施例所示出的表格映射信息的示意图。FIG. 8 is a schematic diagram of table mapping information according to an exemplary embodiment of the present invention.
请参照图8，表格映射信息801对应于实体单元810(0)，且表格映射信息802对应于实体单元810(1)。逻辑至实体映射表830可存储于图6的系统区603。逻辑至实体映射表830包含逻辑至实体映射表TB1～TBM。逻辑至实体映射表TB1～TBM分别用以记录某一个编号范围内的至少一逻辑单元的逻辑至实体映射信息。Referring to FIG. 8, the
表格映射信息801可反映实体单元810(0)所映射的逻辑单元的逻辑至实体映射信息是存储于逻辑至实体映射表TB1～TBM的至少其中之一。表格映射信息802可反映实体单元810(1)所映射的逻辑单元的逻辑至实体映射信息是存储于逻辑至实体映射表TB1～TBM的至少其中之一。例如，表格映射信息801与802可皆具有比特b1～bM。比特bi的数值可为0或1，以反映逻辑至实体映射表TBi是否被使用。数值i介于1与M之间。The
在一范例实施例中，假设实体单元810(0)是映射至图6的逻辑单元612(1)与612(3)，则表格映射信息801中的比特b1与b3的数值可为1(其余比特可为0)，以反映逻辑单元612(1)与612(3)的逻辑至实体映射信息是记录于逻辑至实体映射表TB1与TB3。逻辑至实体映射表TB1与TB3可被载入至图5的缓冲存储器510以存取实体单元810(0)。此外，假设实体单元810(1)是映射至图6的逻辑单元612(1)、612(3)及612(8)，则表格映射信息802中的比特b1、b3及b8的数值可为1(其余比特可为0)，以反映逻辑单元612(1)、612(3)及612(8)的逻辑至实体映射信息是记录于逻辑至实体映射表TB1、TB3及TB8。逻辑至实体映射表TB1、TB3及TB8可被载入至缓冲存储器510以存取实体单元810(1)。In an exemplary embodiment, assuming that the physical unit 810(0) is mapped to the logical units 612(1) and 612(3) in FIG. 6 , the values of the bits b1 and b3 in the
在前述范例实施例中，表格映射信息801与802中的比特b1与b3皆为1，表示用于存取实体单元810(0)与810(1)的多个逻辑至实体映射表中逻辑至实体映射表TB1与TB3是重复的。当存取实体单元810(0)时，逻辑至实体映射表TB1与TB3可被载入至缓冲存储器510以查询相关映射信息。接着，若存取实体单元810(1)，则只需要再额外载入逻辑至实体映射表TB8。In the foregoing exemplary embodiment, the bits b1 and b3 in the
在图7A的范例实施例中，存储器管理电路502可根据对应于至少一第一实体单元710(0)～710(2)的第一表格映射信息与对应于至少一第二实体单元710(3)的第二表格映射信息获得第一映射信息。如图8中所述由于第一表格映射信息可反映至少一第一实体单元的映射信息记载于哪些逻辑至实体映射表(亦称为至少一第一逻辑至实体映射表)，且第二表格映射信息会反映至少一第二实体单元的映射信息记载于哪些逻辑至实体映射表(亦称为至少一第二逻辑至实体映射表)，因此通过第一表格映射信息与第二表格映射信息所获得的第一映射信息会反映至少一第一逻辑至实体映射表与至少一第二逻辑至实体映射表之间的重叠信息，而存储器管理电路502可根据此重叠信息读取至少一第一实体单元710(0)～710(2)与至少一第二实体单元710(3)所共同使用的逻辑至实体映射表。In the exemplary embodiment of FIG. 7A , the
图9A至图9B是根据本发明的一范例实施例所示出的根据映射信息获得逻辑至实体映射表的示意图。9A to 9B are schematic diagrams of obtaining a logic-to-entity mapping table according to mapping information according to an exemplary embodiment of the present invention.
以下将参照图7A～图7C与图9A～图9B，并以实例来更详细地说明本发明的数据整并操作。请参照图7A，在存储器管理电路502选择至少一第一实体单元710(0)～710(2)与至少一第二实体单元710(3)作为来源节点701的操作中，假设回收节点702的至少一第三实体单元720(0)的大小可容纳的数据量(即，目标数据量)为100％，且所选择的来源节点701的第一实体单元710(0)中的有效数据的数据量占目标数据量的20％，第一实体单元710(1)中的有效数据的数据量占目标数据量的20％，第一实体单元710(2)中的有效数据的数据量占目标数据量的37％，而第二实体单元710(3)中的有效数据的数据量占目标数据量的60％，其中每一至少一第一实体单元710(0)～710(2)中的有效数据的数据量小于每一至少一第二实体单元710(3)中的有效数据的数据量。The data consolidation operation of the present invention will be described in more detail below with reference to FIGS. 7A to 7C and FIGS. 9A to 9B with examples. Referring to FIG. 7A , in the operation of selecting at least one first physical unit 710(0)-710(2) and at least one second physical unit 710(3) as the
存储器管理电路502会从可复写式非易失性存储器模块406中读取包含至少一第一实体单元710(0)～710(2)与至少一第二实体单元710(3)两者共用的第一映射信息。请同时参照图7A与图9A，假设表格映射信息910(0)(亦称为第一表格映射信息910(0))是对应于第一实体单元710(0)、表格映射信息910(1)(亦称为第一表格映射信息910(1))是对应于第一实体单元710(1)、表格映射信息910(2)(亦称为第一表格映射信息910(2))是对应于第一实体单元710(2)，且表格映射信息910(3)(亦称为第二表格映射信息910(3))是对应于第二实体单元710(3)。表格映射信息910(0)～910(3)皆具有16个比特。第一表格映射信息910(0)中的比特b1～b5、b9、b11及b15～b16为1，其反映逻辑至实体映射表TB1～TB5、TB9、TB11及TB15～TB16可被查询以存取第一实体单元710(0)。第一表格映射信息910(1)中的比特b1～b5、b9及b16为1，其反映逻辑至实体映射表TB1～TB5、TB9及TB16可被查询以存取第一实体单元710(1)。第一表格映射信息910(2)中的比特b1～b2、b4～b6及b15为1，其反映逻辑至实体映射表TB1～TB2、TB4～TB6及TB15可被查询以存取第一实体单元710(2)。此外，第二表格映射信息910(3)中的比特b1～b6、b9、b11及b15～b16为1，其反映逻辑至实体映射表TB1～TB6、TB9、TB11及TB15～TB16可被查询以存取第二实体单元710(3)。通过逻辑模块90对表格映射信息910(0)～910(3)进行或(OR)运算后，至少一第一实体单元710(0)～710(2)与至少一第二实体单元710(3)两者共用的第一映射信息901可被获得，而存储器管理电路502可根据第一映射信息901载入至少一第一实体单元710(0)～710(2)与至少一第二实体单元710(3)两者共用的逻辑至实体映射表TB1～TB6、TB9、TB11及TB15～TB16。The
接着，存储器管理电路502即可根据第一映射信息901(或逻辑至实体映射表TB1～TB6、TB9、TB11及TB15～TB16)，将从来源节点701的至少一第一实体单元710(0)～710(2)与至少一第二实体单元710(3)中的收集的有效数据700A复制到回收节点702的至少一第三实体单元720(0)。在此，有效数据700A包括来自至少一第一实体单元710(0)～710(2)的有效数据与至少一第二实体单元710(3)的有效数据。Next, the
特别是，在本发明范例实施例中，当从来源节点701的至少一第二实体单元710(3)中复制到回收节点702的至少一第三实体单元720(0)的有效数据的数据量达到数据量门槛值时，存储器管理电路502会停止从至少一第二实体单元710(3)中收集有效数据，且继续从至少一第一实体单元710(0)～710(2)中收集有效数据。具体而言，数据量门槛值为目标数据量(即，至少一第三实体单元720(0)的大小可容纳的数据量)减去至少一第一实体单元710(0)～710(2)中的有效数据的总数据量所获得的剩余数据量。在此范例实施例中，剩余数据量为23％(即，100％-(20％+20％+37％)＝23％)，且存储器管理电路502会将此剩余数据量(即，23％)设为数据量门槛值。换言之，当从来源节点701的至少一第二实体单元710(3)中复制到回收节点702的至少一第三实体单元720(0)的有效数据的数据量占至少一第三实体单元720(0)的大小的23％时，即，相当于从至少一第二实体单元710(3)中复制到至少一第三实体单元720(0)的有效数据的数据量达到所述数据量门槛值。此时，存储器管理电路502将不再从至少一第二实体单元710(3)中收集有效数据。In particular, in the exemplary embodiment of the present invention, when the data volume of the valid data copied from the at least one second physical unit 710(3) of the
请参照图7B，在本发明范例实施例中，当从至少一第二实体单元710(3)中复制到至少一第三实体单元720(0)的有效数据的数据量达到数据量门槛值(即，23％)时，至少一第二实体单元710(3)中所剩的有效数据的数据量减少为占目标数据量的37％(即，60％-23％＝37％)。特别是，在此时间点，至少一第一实体单元710(0)～710(2)中部分的有效数据亦已复制到回收节点702的至少一第三实体单元720(0)中。例如，第一实体单元710(0)中所剩的有效数据的数据量减少为占目标数据量的10％、第一实体单元710(1)中所剩的有效数据的数据量减少为占目标数据量的10％，且第一实体单元710(2)中所剩的有效数据的数据量减少为占目标数据量的27％。Referring to FIG. 7B , in an exemplary embodiment of the present invention, when the data volume of valid data copied from at least one second physical unit 710(3) to at least one third physical unit 720(0) reaches the data volume threshold ( That is, 23%), the data amount of the remaining valid data in at least one second physical unit 710(3) is reduced to 37% of the target data amount (ie, 60%-23%=37%). In particular, at this point in time, part of the valid data in at least one first physical unit 710(0)-710(2) has also been copied to at least one third physical unit 720(0) in the
如上所述，当从至少一第二实体单元710(3)中复制到至少一第三实体单元720(0)的有效数据的数据量达到数据量门槛值(即，23％)时，存储器管理电路502会停止从至少一第二实体单元710(3)中收集有效数据，且继续从至少一第一实体单元710(0)～710(2)中收集有效数据。因此，如图7B所示，存储器管理电路502会仅以至少一第一实体单元710(0)～710(2)作为来源节点701，并从可复写式非易失性存储器模块406中读取仅对应至少一第一实体单元710(0)～710(2)的映射信息(亦称为第二映射信息)。As described above, when the data volume of the valid data copied from the at least one second physical unit 710(3) to the at least one third physical unit 720(0) reaches the data volume threshold (ie, 23%), the memory management The
请同时参照图7B与图9B，在存储器管理电路502从可复写式非易失性存储器模块406中读取仅对应至少一第一实体单元710(0)～710(2)的第二映射信息的操作中，由于至少一第一实体单元710(0)～710(2)中部分的有效数据已复制到回收节点702的至少一第三实体单元720(0)中。因此，至少一第一实体单元710(0)～710(2)的表格映射信息更新为如图9B所示的第一表格映射信息910(0)～910(2)。例如，更新的第一表格映射信息910(0)反映逻辑至实体映射表TB9、TB11及TB15～TB16可被查询以存取第一实体单元710(0)，更新的第一表格映射信息910(1)反映逻辑至实体映射表TB9及TB16可被查询以存取第一实体单元710(1)，以及更新的第一表格映射信息910(2)反映逻辑至实体映射表TB6及TB15可被查询以存取第一实体单元710(2)。类似地，存储器管理电路502可通过逻辑模块90对表格映射信息910(0)～910(3)进行或(OR)运算，以获得至少一第一实体单元710(0)～710(2)的第二映射信息902，而存储器管理电路502可根据第二映射信息902仅载入至少一第一实体单元710(0)～710(2)的逻辑至实体映射表TB6、TB9、TB11及TB15～TB16。由此可知，在至少一第二实体单元710(3)中复制到至少一第三实体单元720(0)的有效数据的数据量达到数据量门槛值之前，存储器管理电路502所需存取的逻辑至实体映射表的数量为10张(即，逻辑至实体映射表TB1～TB6、TB9、TB11及TB15～TB16)，而在至少一第二实体单元710(3)中复制到至少一第三实体单元720(0)的有效数据的数据量达到数据量门槛值之后，存储器管理电路502所需存取的逻辑至实体映射表的数量为5张(即，逻辑至实体映射表TB6、TB9、TB11及TB15～TB16)。Please refer to FIG. 7B and FIG. 9B at the same time, the
接着，存储器管理电路502即可根据第二映射信息902(或逻辑至实体映射表TB6、TB9、TB11及TB15～TB16)，将从来源节点701的至少一第一实体单元710(0)～710(2)中收集的有效数据700B复制到回收节点702的至少一第三实体单元720(0)。在此，有效数据700B包括来自至少一第一实体单元710(0)～710(2)的有效数据。Then, the
请参照图7A～图7C，在本发明的范例实施例中，由于数据量门槛值为回收节点702的至少一第三实体单元720(0)的大小可容纳的数据量(即，目标数据量)减去至少一第一实体单元710(0)～710(2)中的有效数据的总数据量所获得的剩余数据量，而至少一第三实体单元720(0)中对应剩余数据量的空间是用以存储至少一第二实体单元710(3)中的有效数据，因此至少一第三实体单元720(0)中对应剩余数据量以外的空间，刚好可存储至少一第一实体单元710(0)～710(2)中所有的有效数据。即，如图7A所示的第一实体单元710(0)中占目标数据量的20％的有效数据、第一实体单元710(1)中占目标数据量的20％的有效数据，及第一实体单元710(2)中占目标数据量的37％的有效数据，皆能如图7C所示被复制到回收节点702的至少一第三实体单元720(0)中。Referring to FIGS. 7A to 7C , in an exemplary embodiment of the present invention, since the data volume threshold value is the data volume that can be accommodated by the size of at least one third physical unit 720( 0 ) of the recycling node 702 (ie, the target data volume ) is the remaining data amount obtained by subtracting the total data amount of valid data in at least one first physical unit 710(0)-710(2), and the at least one third physical unit 720(0) corresponds to the remaining data amount The space is used to store the valid data in at least one second physical unit 710(3), so the space in at least one third physical unit 720(0) other than the corresponding remaining data amount can just store at least one first physical unit 710 (0) to all valid data in 710(2). That is, as shown in FIG. 7A, the valid data in the first physical unit 710(0) accounting for 20% of the target data volume, the valid data in the first physical unit 710(1) accounting for 20% of the target data volume, and the 37% of the valid data in a physical unit 710(2) can be copied to at least one third physical unit 720(0) of the
图10A至图10B是根据传统的数据整并操作所示出的根据映射信息获得逻辑至实体映射表的示意图。10A to 10B are schematic diagrams illustrating obtaining a logic-to-entity mapping table according to mapping information according to a conventional data consolidation operation.
以下将参照图7A与图10A～图10B，来说明传统的数据整并操作与本发明的数据整并操作的差异。在传统的数据整并操作中，存储器管理电路502会先对来源节点701中存储有较少的有效数据的实体单元710(0)～710(2)进行数据整并操作，以将此些存储有较少的有效数据的实体单元710(0)～710(2)中的有效数据皆复制到回收节点702的实体单元720(0)。接着，再从来源节点701的存储有较多的有效数据的实体单元710(3)中，将有效数据复制到回收节点702中实体单元720(0)的剩余空间。因此，如图10A所示，存储器管理电路502会先仅根据实体单元710(0)～710(2)的映射信息1001载入实体单元710(0)～710(2)的逻辑至实体映射表TB1～TB6、TB9、TB11及TB15～TB16，并根据此些逻辑至实体映射表TB1～TB6、TB9、TB11及TB15～TB16将实体单元710(0)～710(2)中的有效数据皆复制到回收节点702的实体单元720(0)。接着，存储器管理电路502会再根据存储有较多的有效数据的实体单元710(3)的映射信息910(3)载入实体单元710(3)的逻辑至实体映射表TB1～TB6、TB9、TB11及TB15～TB16，并根据此些逻辑至实体映射表TB1～TB6、TB9、TB11及TB15～TB16将实体单元710(3)中的有效数据复制到回收节点702中实体单元720(0)的剩余空间。由此可知，在存取存储有较少的有效数据的实体单元710(0)～710(2)时所需使用的逻辑至实体映射表与存取存储有较多的有效数据的实体单元710(3)时所需使用的逻辑至实体映射表皆为重复的逻辑至实体映射表的情况下，存储器管理电路502在传统的数据整并操作的两阶段操作中，所需存取的逻辑至实体映射表的数量各为10张(即，逻辑至实体映射表TB1～TB6、TB9、TB11及TB15～TB16)。然而，在本发明前述范例实施例中，在从实体单元710(3)中复制到回收节点702的实体单元720(0)的有效数据的数据量达到数据量门槛值之后，存储器管理电路502所需存取的逻辑至实体映射表的数量可减少为5张，相较于传统的数据整并操作所需存取的10张逻辑至实体映射表来得少。7A and FIG. 10A-FIG. 10B, the difference between the conventional data consolidation operation and the data consolidation operation of the present invention will be described below. In a conventional data consolidation operation, the
以下将假设存储器管理电路502执行一个循环的数据整并操作中可处理1000张的逻辑至实体映射表，来更详细地说明本发明的数据整并方法通过减少数据整并操作中需要载入的逻辑至实体映射表的数目，所达到的存储器存储装置的效能提升。请再参照图7A～图7C，在图7A中，假设存取至少一第一实体单元710(0)～710(2)中有效数据所需的逻辑至实体映射表为6000张，且存取至少一第二实体单元710(3)中有效数据所需的逻辑至实体映射表亦为此重复的6000张，因此，在存储器管理电路502从可复写式非易失性存储器模块406中读取包含至少一第一实体单元710(0)～710(2)与至少一第二实体单元710(3)两者共用的第一映射信息的操作中，所获得的至少一第一实体单元710(0)～710(2)与至少一第二实体单元710(3)两者共用的逻辑至实体映射的数目为6000张。接着，存储器管理电路502会根据此6000张逻辑至实体映射表，将从来源节点701的至少一第一实体单元710(0)～710(2)与至少一第二实体单元710(3)中的收集的有效数据700A复制到回收节点702的至少一第三实体单元720(0)。倘若在存储器管理电路502处理完3000张逻辑至实体映射表时，从来源节点701的至少一第二实体单元710(3)中复制到回收节点702的至少一第三实体单元720(0)的有效数据的数据量已达到数据量门槛值，则此时相当于存储器管理电路502执行了3次的数据整并操作，且仅剩下3000(6000-3000＝3000)张的逻辑至实体映射表需被处理。换言之，在图7B～图7C中，存储器管理电路502从可复写式非易失性存储器模块406中所读取的对应至少一第一实体单元710(0)～710(2)的逻辑至实体映射表为前述剩下的3000张，因此，存储器管理电路502仅再执行3次的数据整并操作即可将来源节点701的至少一第一实体单元710(0)～710(2)中所剩余的有效数据皆复制到回收节点702的至少一第三实体单元720(0)。也就是说，在本发明此范例实施例中，存储器管理电路502执行6次的数据整并操作，即可将来源节点701的至少一第一实体单元710(0)～710(2)中所有的有效数据复制至回收节点702的至少一第三实体单元720(0)，并且将至少一第二实体单元710(3)中的对应数据量门槛值的具剩余数据量的有效数据复制至回收节点702的至少一第三实体单元720(0)。In the following, it is assumed that the
反之，在传统的数据整并操作中，在前述假设的条件下，由于存储器管理电路502为了确保存储有较少的有效数据的实体单元710(0)～710(2)中的有效数据皆能复制到回收节点702的实体单元720(0)，因此存储器管理电路502会先仅对来源节点701中存储有较少的有效数据的实体单元710(0)～710(2)进行数据整并操作。亦即，存储器管理电路502会处理完对应实体单元710(0)～710(2)的6000张逻辑至实体映射表，以将至实体单元710(0)～710(2)中所有的有效数据皆复制到回收节点702的实体单元720(0)，并且此时相当于存储器管理电路502执行了6次的数据整并操作。之后，存储器管理电路502会再处理对应实体单元720(0)的6000张逻辑至实体映射表，以将实体单元710(3)中的有效数据复制到回收节点702中实体单元720(0)的剩余空间。此时，存储器管理电路502亦执行了6次的数据整并操作。也就是说，在传统的数据整并方法中，存储器管理电路502共执行了12次的数据整并操作。On the contrary, in the conventional data consolidation operation, under the aforementioned assumptions, since the
据此，通过本发明的数据整并操作中的设定数据量门槛值的机制，不仅可减少在数据整并操作中需要载入的逻辑至实体映射表的数目，在来源节点所对应的逻辑至实体映射表的数目庞大且重复率高的情况下，亦可减少存储器管理电路执行数据整并操作的次数。由此可有效减少对图4的可复写式非易失性存储器模块406的存取次数，更提升存储器存储装置的整体运作效能。Accordingly, through the mechanism of setting the data volume threshold value in the data consolidation operation of the present invention, not only the number of logic-to-entity mapping tables that need to be loaded in the data consolidation operation can be reduced, but also the logic corresponding to the source node can be reduced. In the case where the number of mapping tables to entities is huge and the repetition rate is high, the number of data consolidation operations performed by the memory management circuit can also be reduced. In this way, the number of accesses to the rewritable
图11是根据本发明的一范例实施例所示出的数据整并方法的流程图。请参照图11，在步骤S1101中，存储器管理电路502从实体单元中选择至少一第一实体单元与至少一第二实体单元。在步骤S1103中，存储器管理电路502从所述可复写式非易失性存储器模块中读取第一映射信息，其中所述第一映射信息包含所述至少一第一实体单元的映射信息与所述少一第二实体单元的映射信息。在步骤S1105中，存储器管理电路502根据所述第一映射信息，将从所述至少一第一实体单元中收集的有效数据与从所述至少一第二实体单元中的收集的有效数据复制到所述实体单元中的至少一第三实体单元。在步骤S1107中，当从所述至少一第二实体单元中复制到所述至少一第三实体单元的有效数据的数据量达到数据量门槛值时，存储器管理电路502停止从所述至少一第二实体单元中收集有效数据，且继续从所述至少一第一实体单元中收集有效数据。FIG. 11 is a flowchart of a data consolidation method according to an exemplary embodiment of the present invention. Referring to FIG. 11 , in step S1101 , the
然而，图11中各步骤已详细说明如上，在此便不再赘述。值得注意的是，图11中各步骤可以实作为多个程序码或是电路，本发明不加以限制。此外，图11的方法可以搭配以上范例实施例使用，也可以单独使用，本发明不加以限制。However, each step in FIG. 11 has been described in detail as above, and will not be repeated here. It should be noted that each step in FIG. 11 can be implemented as a plurality of program codes or circuits, which is not limited by the present invention. In addition, the method of FIG. 11 may be used in conjunction with the above exemplary embodiments, or may be used alone, which is not limited in the present invention.
综上所述，在本发明的范例实施例中，提出的数据整并方法、存储器存储装置与存储器控制电路单元，通过设置数据量门槛值来限制从来源节点中有效数据的数据量相对较多的实体单元复制到回收节点的数据量，使数据整并操作中存取来源节点所使用的逻辑至实体映射表不会被重复地读取。如此一来，数据整并操作中存储器存储装置的存取次数可被有效减少，进而延长存储器存储装置的使用寿命。特别是，在来源节点所对应的逻辑至实体映射表的数目庞大且重复率高的情况下，通过本发明的数据整并方法，可减少在数据整并操作中需要载入的逻辑至实体映射表的数目与存储器管理电路执行数据整并操作的次数，进而提升存储器存储装置的整体运作效能。To sum up, in the exemplary embodiments of the present invention, the proposed data consolidation method, memory storage device and memory control circuit unit limit the relatively large amount of valid data from the source node by setting the data amount threshold The amount of data copied from the entity unit to the recycling node, so that the logical-to-entity mapping table used to access the source node in the data consolidation operation will not be read repeatedly. In this way, the access times of the memory storage device during the data consolidation operation can be effectively reduced, thereby prolonging the service life of the memory storage device. In particular, when the number of logic-to-entity mapping tables corresponding to the source node is huge and the repetition rate is high, the data consolidation method of the present invention can reduce the logic-to-entity mapping that needs to be loaded in the data consolidation operation The number of tables and the number of times the memory management circuit performs data consolidation operations, thereby improving the overall operation performance of the memory storage device.
Claims (21)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010948313.5ACN112051971B (en) | 2020-09-10 | 2020-09-10 | Data integration method, memory storage device and memory control circuit unit |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010948313.5ACN112051971B (en) | 2020-09-10 | 2020-09-10 | Data integration method, memory storage device and memory control circuit unit |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN112051971Atrue CN112051971A (en) | 2020-12-08 |
| CN112051971B CN112051971B (en) | 2023-06-27 |
Family
ID=73609974
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202010948313.5AActiveCN112051971B (en) | 2020-09-10 | 2020-09-10 | Data integration method, memory storage device and memory control circuit unit |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN112051971B (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112799601A (en)* | 2021-02-24 | 2021-05-14 | 群联电子股份有限公司 | Efficient data combining method, memory storage device and control circuit unit |
| CN112925481A (en)* | 2021-03-09 | 2021-06-08 | 合肥兆芯电子有限公司 | Memory management method, memory storage device and memory control circuit unit |
Citations (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20150161039A1 (en)* | 2013-12-09 | 2015-06-11 | Phison Electronics Corp. | Data erasing method, memory control circuit unit and memory storage apparatus |
| CN106484307A (en)* | 2015-08-25 | 2017-03-08 | 群联电子股份有限公司 | Memory management method, memory control circuit unit and memory storage device |
| CN106708416A (en)* | 2015-11-13 | 2017-05-24 | 群联电子股份有限公司 | data reconstruction method and system and memory control circuit unit thereof |
| US9880742B2 (en)* | 2015-08-07 | 2018-01-30 | Phison Electronics Corp. | Valid data merging method, memory controller and memory storage apparatus |
| KR20190060528A (en)* | 2017-11-24 | 2019-06-03 | 삼성전자주식회사 | Method of managing data and storage device performing the same |
| CN110390985A (en)* | 2018-04-20 | 2019-10-29 | 群联电子股份有限公司 | Memory management method, memory storage device and memory control circuit unit |
| US10545700B2 (en)* | 2018-04-12 | 2020-01-28 | Phison Electronics Corp. | Memory management method, memory storage device and memory control circuit unit |
| US20200133844A1 (en)* | 2018-10-25 | 2020-04-30 | Phison Electronics Corp. | Data merge method, memory storage device and memory control circuit unit |
| TWI701552B (en)* | 2019-03-22 | 2020-08-11 | 群聯電子股份有限公司 | Memory control method, memory storage device and memory control circuit unit |
- 2020
- 2020-09-10CNCN202010948313.5Apatent/CN112051971B/enactiveActive
Patent Citations (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20150161039A1 (en)* | 2013-12-09 | 2015-06-11 | Phison Electronics Corp. | Data erasing method, memory control circuit unit and memory storage apparatus |
| US9880742B2 (en)* | 2015-08-07 | 2018-01-30 | Phison Electronics Corp. | Valid data merging method, memory controller and memory storage apparatus |
| CN106484307A (en)* | 2015-08-25 | 2017-03-08 | 群联电子股份有限公司 | Memory management method, memory control circuit unit and memory storage device |
| CN106708416A (en)* | 2015-11-13 | 2017-05-24 | 群联电子股份有限公司 | data reconstruction method and system and memory control circuit unit thereof |
| KR20190060528A (en)* | 2017-11-24 | 2019-06-03 | 삼성전자주식회사 | Method of managing data and storage device performing the same |
| US10545700B2 (en)* | 2018-04-12 | 2020-01-28 | Phison Electronics Corp. | Memory management method, memory storage device and memory control circuit unit |
| CN110390985A (en)* | 2018-04-20 | 2019-10-29 | 群联电子股份有限公司 | Memory management method, memory storage device and memory control circuit unit |
| US20200133844A1 (en)* | 2018-10-25 | 2020-04-30 | Phison Electronics Corp. | Data merge method, memory storage device and memory control circuit unit |
| TWI701552B (en)* | 2019-03-22 | 2020-08-11 | 群聯電子股份有限公司 | Memory control method, memory storage device and memory control circuit unit |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112799601A (en)* | 2021-02-24 | 2021-05-14 | 群联电子股份有限公司 | Efficient data combining method, memory storage device and control circuit unit |
| CN112799601B (en)* | 2021-02-24 | 2023-06-13 | 群联电子股份有限公司 | Effective data combination method, memory storage device and control circuit unit |
| CN112925481A (en)* | 2021-03-09 | 2021-06-08 | 合肥兆芯电子有限公司 | Memory management method, memory storage device and memory control circuit unit |
| CN112925481B (en)* | 2021-03-09 | 2024-04-05 | 合肥兆芯电子有限公司 | Memory management method, memory storage device and memory control circuit unit |
Also Published As
| Publication number | Publication date |
|---|---|
| CN112051971B (en) | 2023-06-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| TWI587135B (en) | Data storage method, memory storage device and memory control circuit unit | |
| TWI768764B (en) | Memory management method, memory storage device and memory control circuit unit | |
| CN110879793B (en) | Memory management method, memory storage device and memory control circuit unit | |
| CN111737165B (en) | Memory control method, memory storage device and memory control circuit unit | |
| TW202201229A (en) | Memory control method, memory storage device and memory control circuit unit | |
| CN110390985A (en) | Memory management method, memory storage device and memory control circuit unit | |
| TWI702496B (en) | Memory management method, memory storage device and memory control circuit unit | |
| CN112051971B (en) | Data integration method, memory storage device and memory control circuit unit | |
| TWI688956B (en) | Memory control method, memory storage device and memory control circuit unit | |
| TW202234227A (en) | Valid data merging method, memory storage device and memory control circuit unit | |
| CN111767005B (en) | Memory control method, memory storage device and memory control circuit unit | |
| TWI741779B (en) | Data merge method, memory storage device and memory control circuit unit | |
| CN112394883B (en) | Data merging method, memory storage device and memory control circuit unit | |
| CN112988076B (en) | Flash memory control method, storage device and controller | |
| TWI768738B (en) | Memory control method, memory storage device and memory control circuit unit | |
| CN116225329A (en) | Memory performance matching method, storage device and memory control circuit | |
| TWI724427B (en) | Data writing method, memory storage device and memory control circuit unit | |
| CN112445418B (en) | Memory control method, memory storage device and memory control circuit unit | |
| CN111813325A (en) | Memory control method, memory storage device, and memory control circuit unit | |
| US12366987B2 (en) | Memory management method, memory storage device and memory control circuit unit | |
| CN115145488B (en) | Partial erase management method, memory device and memory control circuit | |
| US11561719B2 (en) | Flash memory control method of re-programming memory cells before erase operations, flash memory storage device and flash memory controller | |
| TWI741870B (en) | Data merge method, memory storage device and memory control circuit unit | |
| CN112015327B (en) | Data writing method, memory storage device and memory control circuit unit | |
| CN108121663B (en) | Data storage method, memory storage device and memory control circuit unit |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |