数据存储系统、数据存储装置及其管理方法

摘要

一种数据存储装置的管理方法，包括以下步骤：根据多个先前存取指令获得多个相关性规则；根据这些相关性规则建立多个查找表；接收当前存取指令，并且判断当前存取指令是否对应这些查找表的至少其中之一以从对应的查找表获得当前存取指令的实体地址；根据这些相关性规则预测后续存取指令所需要对应的查找表，并预先建立这些被预测的查找表。本发明还提出一种数据存储系统与数据存储装置，可实施上述的管理方法。

说明书

技术领域

本发明涉及一种数据存取技术，且特别涉及一种数据存储系统、数据存储装置及其管理方法。

背景技术

近年来，各式配备存储装置的电子装置已被消费者普遍应用在日常生活中，而且随着存储容量的需求增加，快速且大容量可供读写的非易失性存储器成为十分受欢迎的产品，这些产品大多以快闪存储器来存储数据。

由于快闪存储器的读写特性，快闪存储器会具有逻辑-实体地址查找表，其用来纪录逻辑区块地址(Logical Block Address，LBA)与实体区块地址(Physical BlockAddress，PBA)之间的映射关系。通过查找表找出存取指令的逻辑地址实际在快闪存储器中的区块地址，才有办法正确地存取数据。然而，因为存储容量与成本的限制无法将所有的PBA与LBA的映射关系都记录下来。如果存取指令的目标不在查找表所记录的范围内，系统需要移除现有的查找表并且根据目标的存取地址重新建立查找表，因此降低快闪存储器的存取效率。

发明内容

有鉴于此，本发明提供一种数据存储系统、数据存储装置及其管理方法，能够减少重建数据存储装置所需要的逻辑-实体地址查找表次数，增加数据存储装置所需要的逻辑-实体地址查找表的命中率(hit rate)，进而提升数据存储装置的效能。

本发明的实施例提出一种数据存储装置包括存储器阵列、预测单元以及查找表管理单元。预测单元用以根据多个先前存取指令进行相关性规则分析后而获得多个存取位置之间的多个相关性规则。查找表管理单元用以根据这些相关性规则管理多个查找表，其中查找表管理单元判断当前存取指令是否对应这些查找表的至少其中之一以从对应的查找表获得当前存取指令在存储器阵列的实体地址，若不存在可对应的查找表则需建立可对应的查找表，并且根据这些相关性规则预测后续存取指令所对应的查找表，以及预先建立这些查找表。

本发明的实施例提出一种数据存储系统，包括主机与数据存储装置。主机包括运算装置，其中运算装置根据多个先前存取指令进行相关性规则分析后获得多个相关性规则。数据存储装置电性连接主机且包括输入输出接口、存储器阵列与查找表管理单元。数据存储装置通过输入输出接口从主机接收这些相关性规则以及当前存取指令。查找表管理单元用以根据这些相关性规则管理多个查找表，其中查找表管理单元判断当前存取指令是否对应这些查找表的至少其中之一以从对应的查找表获得当前存取指令在存储器阵列的实体地址，若不存在可对应的查找表则需建立可对应的查找表，并且根据这些相关性规则预测后续存取指令所对应的查找表，以及预先建立这些查找表。

本发明的实施例提出一种数据存储装置的管理方法，包括以下步骤：根据多个先前存取指令获得多个相关性规则；根据这些相关性规则建立多个查找表；接收当前存取指令，并且判断当前存取指令是否对应这些查找表的至少其中之一以从对应的查找表获得当前存取指令的实体地址；若不存在可对应的查找表则需建立可对应的查找表，并且根据这些相关性规则预测后续存取指令所对应的查找表，以及预先建立这些查找表。

基于上述，本发明提供一种数据存储系统、数据存储装置及其管理方法，通过分析数据存储装置的存取历史以获得先前存取位置之间的相关性规则，并根据相关性规则建立查找表甚至进一步根据相关性规则预测接下来可能的存取位置并相应地预备好查找表，如此一来，可以提高查找表对应的命中率，减少重新建立查找表的次数，进而提升数据存取的效能。

附图说明

包含附图以便进一步理解本发明，且附图并入本说明书中并构成本说明书的一部分。附图说明本发明的实施例，并与描述一起用于解释本发明的原理。

图1是根据本发明的一实施例的数据存储装置的功能方块图；

图2是根据本发明的一实施例的数据存储装置的逻辑地址的分段方式示意图；

图3是根据本发明的一实施例的相关性规则分析的过程示意图；

图4是根据本发明的另一实施例的数据存储系统的功能方块图；

图5是根据本发明的一实施例的数据存储装置的管理方法的流程图；

图6是根据本发明的另一实施例的数据存储装置的管理方法的流程图。

上述附图中，附图标记含义如下：

40：数据存储系统

100、400：数据存储装置；

110：存储器阵列；

120：存储器控制器；

130：查找表管理单元；

140：输入输出接口；

150：预测单元；

200：逻辑地址范围；

301～306：量化数据；

402：运算装置；

500、600：管理方法；

A～G：存储段；

H：主机；

S510～S570、S610～S640：步骤。

具体实施方式

现将详细地参考本发明的示范性实施例，示范性实施例的实例说明于附图中。只要有可能，相同元件符号在图式和描述中用来表示相同或相似部分。

图1是根据本发明的一实施例的数据存储装置的功能方块图。在本实施例中，数据存储装置100可以是一种NAND快闪存储器，但不限于此。数据存储装置100包括存储器阵列110、存储器控制器120、查找表管理单元130、输入输出接口140以及预测单元150。存储器阵列110包括排列为矩阵状的多个存储器单元(memory cells)。存储器控制器120基于来自输入输出接口140的存取指令而对存储器阵列110进行数据存取动作。输入输出接口140例如支持SATA、USB、PCIe、或SPI等接口协议。查找表管理单元130用以管理多个查找表(look-uptable，LUT)。这些查找表例如存储在存储器阵列110的备用区(Spare area)或高速缓冲存储器(Cache)中。通过这些查找表，查找表管理单元130将存取目标的逻辑地址转换成存储器阵列110的实体地址。具体而言，查找表管理单元130包括快闪存储器转换层(FlashTranslation Layer，FTL)，可以将逻辑区块地址(Logical Block Address，LBA)转换为实体区块地址(Physical Block Address，PBA)。存储器控制器120根据查找表管理单元130提供的实体地址将数据移进或移出被选中的存储器单元。

值得注意的是，本实施例的预测单元150可以分析数据存储装置100的存取历史。预测单元150收集存取历史中的多个存取指令(以下简称为先前存取指令)，并且根据这些先前存取指令获得多个相关性规则(Association Rules)。上述的相关性规反应存取目标之间的位置相关性。更具体而言，预测单元150会对这些先前存取指令进行量化(Quantization)处理以获得多个量化数据，并且对这些量化数据进行相关性规则分析(Association Rules Analysis)以获得这些相关性规则。查找表管理单元130根据预测单元150提供的相关性规则管理这些查找表。查找表管理单元130判断当前存取指令是否对应这些现有的查找表的至少其中之一以从对应的查找表获得当前存取指令在存储器阵列110的实体地址，并且根据对应的相关性规则预测未来接收的存取指令(简称后续存取指令)所对应的查找表。当现有查找表中没有任一查找表对应当前存取指令时，查找表管理单元130根据相关性规则建立对应当前存取指令的查找表以及预先建立被预测对应于后续存取指令的查找表。

在本实施例中，预测单元150以及查找表管理单元130可以通过硬件及/或软件的形式来实施，本发明不加以限制。在一实施例中，预测单元150或查找表管理单元130可为固件(Firmware)的形式、中间件(middleware)或是应用程式(Application，APP)的形式预先存储在数据存储装置100中，并且由存储器控制器120或处理器执行。

以下将举多个实施例以具体说明数据存储装置100的实施细节。

图2是根据本发明的一实施例的数据存储装置的逻辑地址的分段方式示意图，图3是根据本发明的一实施例的相关性规则分析的过程示意图。请参照图2，逻辑地址范围200以线性的方式呈现存储器阵列110的数据存储空间，存储器阵列110的逻辑地址范围200是通过量化处理后被标定区分为多个存储段，如图2显示的存储段A到存储段G。详细而言，存储段A包括逻辑地址范围200中的逻辑地址0x2000～0x2999的范围。存储段B包括逻辑地址0x3000～0x3999之间的范围。存储段C包括逻辑地址0x4000～0x4999之间的范围。存储段D包括逻辑地址0x5000～0x5999之间的范围。存储段E包括逻辑地址0x6000～0x6999之间的范围。存储段F包括逻辑地址0x7000～0x7999之间的范围。存储段G包括逻辑地址0x8000～0x8999之间的范围。

本发明不限制存储器阵列110的存储空间大小、存储段数目以及每个存储段包括的逻辑地址范围。另外，在本实施例中，存储器阵列110的数据存储空间是被等份划分成多个存储段A～G，亦即存储段A～G中的每个存储段的逻辑地址范围的长度相同，但在其他实施例中，存储器阵列110的数据存储空间通过量化处理后，被标定为多个存储段，这些存储段的地址范围的长度可以不相同。

数据存储装置100接收的每个存取指令包括存取目标的起始逻辑区块地址以及扇区长度(Sector length)，因此预测单元150可以根据量化处理后的存储段A～G来对存取指令进行对应转换，将存取目标的位置转换成对应的存储段。本实施例举8个先前存取指令cmd1～cmd8为例，下列的表一记录先前存取指令cmd1～cmd8的起始逻辑区块地址、扇区长度以及对应的存储段项目。举例来说，先前存取指令cmd1的存取目标的地址范围从0X2900到0X3000，对应到存储段A与存储段B；先前存取指令cmd2的存取目标的地址范围从0X5200到0X7200，同时对应至存储段D、存储段E与存储段F，以此类推，其余先前存取指令cmd3～cmd8所对应的存储段项目不再详述。

表一

预测单元150计数先前存取指令cmd1～cmd8对存储段A～G的存取次数，并根据存储段A～G的存取次数进行相关性规则分析。请参照图3，图3的量化数据301纪录先前存取指令cmd1～cmd8对存储段A～G的存取次数。由表一可知，先前存取指令cmd1、cmd4、cmd5与cmd7的存取范围都涉及存储段A与存储段B，存储段A与存储段B的存取次数都为4；先前存取指令cmd4、cmd5、cmd7与cmd8的存取范围都涉及存储段C，存储段C的存取次数是4；先前存取指令cmd2、cmd4、cmd5、cmd7与cmd8的存取范围都涉及存储段D，存储段D的存取次数是5；先前存取指令cmd2、cmd5、cmd6与cmd7的存取范围都涉及存储段E，存储段E的存取次数是4；先前存取指令cmd2、cmd3、cmd5与cmd6的存取范围都涉及存储段F，存储段F的存取次数是4；先前存取指令cmd3、cmd6的存取范围都涉及存储段G，存储段G的存取次数是2。在此，每个存储段的存取次数代表相关性规则分析中的支持度(support)。换句话说，量化数据301分别记录了先前存取指令cmd1～cmd8对每个存储段的支持度。预测单元150可根据最小支持度门槛来选择有用的量化数据。在本实施例中，设定最小支持度门槛为2，如果量化数据301有某一存储段的支持度小于最小支持度门槛，该存储段的量化数据会被视为相关性不足而被剔除，另一方面，支持度不小于最小支持度门槛的量化数据则会被保留。量化数据301就被完全保留下来。

接着，预测单元150类推量化数据302。量化数据302记录任二个存储段组合的支持度。举例来说，先前存取指令cmd1、cmd4、cmd5与cmd7的存取范围同时涉及存储段A与存储段B，存储段项目AB的支持度为4；先前存取指令cmd5与cmd7的存取范围同时涉及存储段A与存储段E，存储段项目AE的支持度为2；没有任何一个先前存取指令同时涉及存储段A与存储段G，因此存储段项目AG的支持度为0，以此类推，其余存储段组合的分析在此不再详述。

接着，由于量化数据302有部分存储段项目的支持度小于2，因此预测单元150将不合格的量化数据删除，以保留具有一定相关性的量化数据303。

接着，预测单元150类推量化数据304。量化数据304记录任3个存储段组合的支持度。举例来说，先前存取指令cmd4、cmd5与cmd7的存取范围涉及存储段A、存储段B与存储段C，存储段项目ABC的支持度为3；先前存取指令cmd5与cmd7的存取范围涉及存储段A、存储段B与存储段E，存储段项目ABE的支持度为2，以此类推。

接着，预测单元150类推量化数据305。量化数据305记录任4个存储段组合的支持度。举例来说，先前存取指令cmd4、cmd5与cmd7的存取范围涉及存储段A、存储段B、存储段C与存储段D，存储段项目ABCD的支持度为3；先前存取指令cmd5与cmd7的存取范围涉及存储段A、存储段B、存储段C、与存储段E，存储段项目ABCE的支持度为2，以此类推。

预测单元150继续产生量化数据306。量化数据305记录任5个存储段组合的支持度。至此，量化数据306只包括一个支持度为2的存储段项目ABCDE。预测单元150会类推所有存储段组合的支持度。

预测单元150进一步计算各存储段或各存储段组合之间的可信度(confidence)，并且根据最小可信度门槛决定一或多个相关性规则，以使查找表管理单元130根据上述的相关性规则预测后续存取指令所对应的查找表。可信度是各存储段或与存储段组合之间的支持度比值，当可信度大于或等于最小可信度门槛时，该相关性规则才会成立。

请参照上述图3的多个量化数据301～306，在此，设定最小可信度门槛为0.75。以下举数个范例作为说明。以存储段组合ABCD与存储段D为例，两者之间的可信度为1，大于最小可信度门槛，因此预测单元150建立存储段组成ABC与存储段D之间的相关性规则。换句话说，当数据存储装置100目前接收的存取指令(又称为当前存取指令)的存取范围涉及存储段A、存储段B与存储段C时，预测单元150预测下个可能的存取范围落在存储段D内。以存储段A以及存储段组合ABCD之间的相关性为例，可信度为0.75，刚好通过最小可信度门槛，预测单元150建立存储段A与存储段组合ABC之间的相关性规则。如果当前存取指令的存取范围落在存储段A内，预测单元150预测接下来可能的存取范围涉及存储段A、存储段B与存储段C三者。以存储段B以及存储段组合BCDE之间的相关性为例，可信度为0.5，未超过最小可信度门槛，预测单元150不会建立存储段B与存储段组合CDE之间的相关性规则。如果当前存取指令的存取范围落在存储段B内，预测单元150预测接下来可能的存取范围不会同时涉及存储段C、存储段D与存储段E三者。

查找表管理单元130根据预测单元150提供的相关性规则建立与当前存取指令具有相关性的多个查找表。具体来说，每一个查找表的映射(mapping)范围可以等于至少一存储段的逻辑地址范围。在本实施例中，每一个查找表的映射范围等于存储段A～G的其中之一的逻辑地址范围。在另一实施例中，查找表的映射范围也可以包括复数个存储段的逻辑地址范围。本发明并不限制查找表的映射范围。

以当前存取指令的存取目标落在存储段A内为例，查找表管理单元130判断当前存取指令是否命中(Hit)现有的查找表。如果命中，查找表管理单元130提供当前存取指令的实体地址给存储器控制器120，并且根据存储段A的相关性规则预测接下来可能的存取目标的位置是落在0x2000～0x4999的范围内(存储段A至存储段C)。查找表管理单元130进一步预备映射此存取范围的查找表。查找表管理单元130还可以更进一步根据存储段BCD的相关性规则或是根据存储段A的其他相关性规则，预测接下来其他可能的存取位置，并且预备好查找表，以此类推。简言之，查找表管理单元130会依序准备跟存储段A具有相关性或间接相关性的查找表，因此这些查找表彼此之间都具有相关性规则关系。

如果当前存取指令没有命中(Miss)现有的查找表，查找表管理单元130会建立可对应当前存取指令的查找表，还会根据相关性规则重新建立与当前存取指令具有相关性的多个查找表，新建立的多个查找表会包括被预测接下来会用到的查找表。简言之，在当前存取指令没有对应现有多个查找表的任一时，查找表管理单元130会根据相关性规则建立当前存取指令的所对应的查找表以及预先建立被预测对应于后续存取指令的查找表。

在本实施例中，当查找表的存储空间不足时，查找表管理单元130会根据相关性规则优先移除对应最小支持度的查找表或是与当前存取指令相关性最低的查找表。在一实施例中，存储段G的支持度最小，或者，当前存取指令的存取范围同时涉及存储段B与存储段C，而存储段G与组合存储段BC的相关性最低(甚至是不相关)，查找表管理单元130选择移除对应存储段G的查找表。

在本实施例中，预测单元150通过分析存取历史的多个先前存取指令获得存取位置之间相关性规则，查找表管理单元130根据相关性规则来管理查找表，甚至预备对应未来可能的存取位置的查找表，以提升数据存储装置100的存取效率。其中，本实施例还通过量化处理的方式来减轻相关性规则分析的运算负担。

图4是根据本发明的另一实施例的数据存储系统的功能方块图。数据存储系统40包括主机H与数据存储装置400。数据存储装置400可以是一种NAND快闪存储器，但不限于此。数据存储装置400与数据存储装置100相似，但可以不包括预测单元150。数据存储装置400通过输入输出接口140电性连接主机H，其中主机H包括运算装置402。

主机H发送存取指令至数据存储装置400以写入或读取数据，并且记录先前发送的存取指令。运算装置402可以执行如数据存储装置100的预测单元150的动作，根据多个先前存取指令获得多个相关性规则。运算装置402可以是中央处理单元(Central ProcessingUnit，CPU)、微处理器(Microprocessor)、数字信号处理器(Digital Signal Processor，DSP)、可编程控制器、专用集成电路(Application Specific Integrated Circuits，ASIC)、可编程逻辑设备(Programmable Logic Device，PLD)或其他类似装置或这些装置的组合，通过执行固件或软件来进行相关性规则分析。

数据存储装置400通过输入输出接口140从主机H接收这些相关性规则以及当前存取指令。查找表管理单元130会根据所接收的相关性规则管理多个查找表。查找表管理单元130可以判断当前存取指令是否对应现有查找表的至少其中之一以从对应的查找表获得当前存取指令在存储器阵列110的实体地址，并且根据相关性规则预测后续存取指令所对应的查找表。关于运算装置402如何获得存取位置之间的相关性规则以及查找表管理单元130如何管理查找表的实施细节可以参照上述实施例的说明，在此不再加以赘述。

在本实施例中，将相关性规则分析的执行动作交付给主机H的运算装置402，如此一来，可以降低数据存储装置400的运算需求。通过从主机H接收相关性规则，数据存储装置400还是具有预测未来可能用到的查找表并且提升存取命中率的效果。

图5是根据本发明的一实施例的数据存储装置的管理方法的流程图。管理方法500可适用于上述的数据存储装置100以及数据存储系统40。以下搭配上述实施例的元件符号说明管理方法500的步骤。

在步骤S510中，通过预测单元150或运算装置402来根据多个先前存取指令获得多个相关性规则。这些相关性规则会被提供至查找表管理单元130。接着，在步骤S520中，通过查找表管理单元130根据这些相关性规则建立多个查找表。接着，在步骤S530中，数据存储装置100或数据存储装置400接收当前存取指令。在步骤S540中，由查找表管理单元130判断当前存取指令是否对应现有查找表的至少其中之一。如果当前存取指令命中现有查找表，则进行步骤S550，查找表管理单元130根据相关性规则预测后续存取指令所对应的查找表。另外，进行步骤S570，由查找表管理单元130从对应的查找表获得当前存取指令的实体地址，并且由存储器控制器120根据当前存取指令的实体地址执行存取动作。如果当前存取指令未命中现有查找表，进行步骤S560，根据这些相关性规则建立对应当前存取指令的查找表以及预先建立被预测对应于后续存取指令的查找表。接着，在执行步骤S570，由查找表管理单元130从新建立的查找表获得当前存取指令的实体地址，并且由存储器控制器120根据当前存取指令的实体地址执行存取动作。

管理方法500的实施细节可由图1至图4的实施例获致足够的建议、教示或说明，在此不再赘述。

图6是根据本发明的另一实施例的数据存储装置的管理方法的流程图。管理方法600可适用于上述的数据存储装置100以及数据存储系统40。以下搭配上述实施例的元件符号说明管理方法600的步骤。

数据存储装置100或数据存储装置400装设在一电子装置上，以图4的主机H为例。在步骤S610中，主机H开机。在步骤S620中，确认是否存在至少一相关性规则。当主机H或数据存储装置100或400内已存储至少一相关性规则时，进行步骤S630，查找表管理单元130根据相关性规则优先建立对应最高支持度的查找表作为初始查找表，并根据相关性规则建立与初始查找表具有相关性的其他多个查找表。当多个查找表建立完成后，进行上述的步骤S540至步骤S570。当确认目前尚未建立任何相关性规则后，执行步骤S640，查找表管理单元130根据预设规则建立这些查找表并且由预测单元150开始记录数据存储装置100的存取历史或是由主机H开始记录数据存储装置400的存取历史，接续上述的步骤S570，直到收集到足够的先前存取指令，运算装置402或预测单元150根据存取历史的先前存取指令获得相关性规则。预设规则可以是出厂时的设定或者根据逻辑区块地址的顺序依序建立，本发明并不限制预设规则的制订方式。

关于S540至步骤S570的实施细节可参照上述的说明，在此不再赘述。

综上所述，本发明的上述实施例提出一种数据存储系统、一种数据存储装置以及一种数据存储装置的管理方法。通过分析数据存储装置的存取历史来获得先前的存取位置之间的相关性规则，并且根据相关性规则来建立查找表甚至预测接下来的存取范围以准备需要的查找表。如此一来，数据存储装置能够根据热数据来适应性的准备查找表，提升查找表可被对应的命中率，减少重建查找表的次数，进而提升存储装置的存取效能。

以上所述的具体实施例，对本发明的目的、技术方案和有益效果进行了进一步详细说明，应理解的是，以上所述仅为本发明的具体实施例而已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。