基于数据关联度的垃圾回收方法、闪存及装置

摘要

本发明公开了一种基于数据关联度的垃圾回收方法、闪存及装置，涉及数据存储技术技术领域。其方法技术要点包括基于主控将数据写入储存块的次序生成时间戳表；基于时间戳表获取待垃圾回收的存储块对应次序的时间戳值；获取下一次序的时间戳值对应的存储块；基于物理映射表判断待垃圾回收的存储块的尾端数据和下一次序的存储块的首端数据是否连续；若是，对待垃圾回收的存储块和下一次序的存储块的首端数据执行垃圾回收；若否，仅将待垃圾回收的存储块执行垃圾回收，本发明具有提升垃圾回收后数据的连续性的优点。

说明书

技术领域

本发明涉及数据存储技术领域技术领域，更具体地说，它涉及一种基于数据关联度的垃圾回收方法、闪存及装置。

背景技术

由于储存块是由成百上千的闪存页组成的，而SSD中写入的最小单位是闪存页，而擦除的最小单位为储存块。因此当闪存在删除数据时，只要储存块中还存在其他有效的数据，就无法对储存块执行擦除的操作。从而这些应该被删除而无法擦除的数据，就被称为SSD中的垃圾。

垃圾回收（GC）是SSD的垃圾清理算法，其主要处理步骤为将存在垃圾的储存块内的有效数据搬移到一个GC操作块上。在搬移完毕后对储存块执行擦除的操作。

而现有的GC过程中，常常会出现GC操作块上的空间不足将存储待擦除的连续数据分开保存在两个不同的GC操作块上。而这样的一段连续的数据经过多次GC，可能分布在数十个不同的存储块上。

发明内容

针对现有的技术问题，本发明的第一目的在于提供一种基于数据关联度的垃圾回收方法，其具有提升垃圾回收后数据的连续性优点。

为实现上述目的，本发明提供了如下技术方案：一种基于数据关联度的垃圾回收方法，包括，

基于主控将数据写入储存块的次序生成时间戳表；

基于时间戳表获取待垃圾回收的存储块对应次序的时间戳值；

获取下一次序的时间戳值对应的存储块；

基于物理映射表判断待垃圾回收的存储块的尾端数据和下一次序的存储块的首端数据是否连续；

若是，对待垃圾回收的存储块和下一次序的存储块的首端数据执行垃圾回收；

若否，仅将待垃圾回收的存储块执行垃圾回收。

通过采用上述技术方案，当将一段连续的数据从主控写入到存储块内并将存储块内写满，则连续数据剩下来的部分会写到其他的存储块上；因此根据相邻存储块尾端和首端的数据之间可能是连续的数据；从而在这个基础上，在写入存储块时，生成时间戳表，能够对储存块写入的先后次序进行获取；而在上一次序的存储块和一下次序的存储块被物理映射表证实是连续的情况；将上一次序的存储块和一下次序的存储块连续的数据一同进行垃圾回收，因此垃圾回收的过程中上一次序的存储块和一下次序的存储块连续的数据至多需要两个存储块存储，甚至有可能只需要一个存储块存储，不会出现需要更多存储块存储的情况，因此在经过多次垃圾回收之后，连续数据分配至存储块的数量只能不变或者减小，不会出现连续数据被持续拆分到数十个GC操作块上的情况，具有提升垃圾回收后数据的连续性优点。

本发明进一步设置为：获取上一次序的时间戳值对应的存储块；

基于物理映射表判断待垃圾回收的存储块的首端数据和上一次序的存储块的尾端数据是否连续；

若是，获取垃圾回收后的存储块的物理地址，并将时间戳表上对应已执行垃圾回收存储块的时间戳值更新为对应垃圾回收后的存储块；

若否，将时间戳表上对应已执行垃圾回收存储块的时间戳值删除。

通过采用上述技术方案，当存储块是和上一次序的存储块之间存在连续关系的时候，通过修改时间戳表，能够保持时间戳表上数据的持续性，同时无需增加垃圾回收的数据量。

本发明进一步设置为：所述时间戳表记录有时间戳值和存储块的物理地址。

通过采用上述技术方案，通过物理地址能够获取到对应储存块，而通过时间戳值，能够获取存储块写入的次序；因此通过时间戳记录表在获得存储块地址的情况下获取存储块写入次序，在知道存储块写入次序的情况下，能够获取存储块的地址。

本发明进一步设置为：在主控写入数据至存储块并将存储块内数据写满时，主控在所述时间戳表记录存储块的物理地址并生成新的时间戳值。

通过采用上述技术方案，在存储块写满后，再在时间戳表中记录，保证了一个存储块一次仅对应一个时间戳值。

本发明进一步设置为：所述时间戳记录表的下一时间戳值由上一时间戳值增加定值后生成。

通过采用上述技术方案，时间戳值仅用于排序，下一时间戳值由上一时间戳值增加定值后生成，下一时间戳值必定大于上一时间戳值；那么只需比较时间戳值的大小就能够实现对时间戳值的排序。

本发明进一步设置为：判断待垃圾回收的存储块的尾端数据和下一次序的存储块的首端数据是否连续的方法包括：

获取垃圾回收的存储块末尾存储页的物理地址，并对照物理映射表获取对应的逻辑地址；

获取下一次序的存储块起始存储页的物理地址，并对照物理映射表获取对应的逻辑地址；

判断获取垃圾回收的存储块尾端数据和下一次序的存储块起始存储页的逻辑地址是否为连续地址；

若是则垃圾回收的存储块的尾端数据和下一次序的存储块的首端数据是连续。

通过采用上述技术方案，逻辑映射表记录了储存块的逻辑地址和物理地址，而连续的数据的逻辑地址是连续的。因此根据储存块的物理地址后，根据逻辑映射表获取逻辑地址，进行指定物理地址上逻辑地址是否连续的判定。

本发明的第二目的在于提供一种闪存，其具有提升垃圾回收后数据的连续性优点。

为实现上述目的，本发明提供了如下技术方案：一种闪存，包括指令，所述指令在计算机上运行时，使得计算机执行第一目的所述的方法。

本发明的第三目的在于提供一种装置，其具有提升垃圾回收后数据的连续性优点。

为实现上述目的，本发明提供了如下技术方案：一种装置，所述装置包括处理器和存储器；

所述存储器用于存储支持所述装置执行第一目的所述的方法的程序，以及

存储用于实现第一目的所述的方法所涉及的数据；

所述处理器被配置为用于执行所述存储器中存储的程序。与现有技术相比，本发明的有益效果是：

（1）添加时间戳信息，提升垃圾回收后数据的连续性；

（2）时间戳值采用递增的数值，写入和读取方便，不需要额外运算。

附图说明

图1为基于数据关联度的垃圾回收方法的流程示意图。

具体实施方式

下面结合附图和实施例，对本发明进行详细描述。

为了理解本方案，先对闪存的一些基本结构进行说明。目前通用的闪存介质一般划分为多个存储块（Block），每个存储块有多条字线（WL），一条字线（WL）包含一个或者多个存储页（Page），而存储页是闪存写入数据的基本单位。

主控为闪存内主控芯片的简称，主控本质是一台微处理器，具备CPU级别的运算能力，其具有执行固件代码的功能。

实施例，一种基于数据关联度的垃圾回收方法，如图1所示，包括：

S1、基于主控将数据写入储存块的次序生成时间戳表；

时间戳表为记录有时间戳值和存储块的物理地址。使得每一个时间戳值仅对应一个存储块的物理地址。

其中，主控通过存储块的物理地址能够查找到对应储存块；而通过时间戳值，能够获取存储块写入的次序。因此通过时间戳表在获得存储块的物理地址的情况下能够获取存储块代表写入次序的时间戳值，在获得存储块代表写入次序的时间戳值的情况下，能够获取存储块的物理地址。

具体的，时间戳值构成等差递增数列，下一时间戳值由上一时间戳值增加定值后生成。优选的，本方案内时间戳值采用2字节进行存储，且时间戳值的初始值为0，每记录一个储存块的物理地址，下一时间戳值的参数加1。因此初始的时间戳值为0X0000，初始时间戳的下一时间戳值为0X0001。

为了保证一个存储块仅对应一个时间戳值，主控仅在存储块上的存储页数据写满后，再在时间戳表中记录储存块的物理地址，并生成对应的时间戳值。

进一步的，时间戳表记录与闪存的指定存储块内。便于主控执行读写和擦除操作。

S2、基于时间戳表获取待垃圾回收的存储块对应次序的时间戳值；

进行垃圾回收时，主控会首先获得待垃圾回收的存储块的物理地址；并基于待垃圾回收的存储块的物理地址在时间戳表内检索，查找到对应的时间戳值；

S3、获取下一次序的时间戳值对应的存储块；

主控查找到对应待垃圾回收的存储块的时间戳值后，将获取的时间戳值加上指定值就获得了下一时间戳值，本实施中指定值为1。之后主控再基于时间戳表，获取对应下一时间戳值的存储块的物理地址，在闪存内找到下一次序的时间戳值对应的存储块。

S4、基于物理映射表判断待垃圾回收的存储块的尾端数据和下一次序的存储块的首端数据是否连续，若是则执行步骤S51，若否则执行步骤S52；

物理映射表内记录有存储块内存储页的物理地址，以及对应存储页的逻辑地址。

存储块的尾端数据为存储块末尾连续的数据，其存储在储存块末尾连续的若干的存储页上。首端数据为存储块起始连续的数据，其存储在储存块起始连续的若干的存储页上。当待垃圾回收的存储块的尾端数据和下一次序的存储块的首端数据是连续的，则必然有一段连续的数据被拆分在两个存储块上。

具体的，判断待垃圾回收的存储块的尾端数据和下一次序的存储块的首端数据是否连续的方法包括：

S41、获取垃圾回收的存储块末尾存储页的物理地址，并对照物理映射表获取对应的逻辑地址；

S42、获取下一次序的存储块起始存储页的物理地址，并对照物理映射表获取对应的逻辑地址；

S43、判断获取垃圾回收的存储块末尾存储页和下一次序的存储块起始存储页的逻辑地址是否为连续地址。

若是，则垃圾回收的存储块的尾端数据和下一次序的存储块的首端数据是连续。若否，垃圾回收的存储块的尾端数据和下一次序的存储块的首端数据不是连续的。

S51、对待垃圾回收的存储块和下一次序的存储块的首端数据执行垃圾回收；

存储块上首端数据的获取方式包括：主控获取存储块上起始存储页的逻辑地址，再获取和起始存储页的逻辑地址相连续的所有存储页。

S52、将待垃圾回收的存储块执行垃圾回收。

S6、获取上一次序的时间戳值对应的存储块；

主控查找到对应待垃圾回收的存储块的时间戳值后，将获取的时间戳值减去指定值就获得了上一时间戳值。之后主控再基于时间戳表，获取对应上一的时间戳值的存储块的物理地址，在闪存内找到上一次序的时间戳值对应的存储块。

S7、基于物理映射表判断待垃圾回收的存储块的首端数据和上一次序的存储块的尾端数据是否连续，若是则执行步骤S81，若否则执行步骤S82；

S71、获取垃圾回收的存储块起始存储页的物理地址，并对照物理映射表获取对应的逻辑地址；

S72、获取上一次序的存储块末尾存储页的物理地址，并对照物理映射表获取对应的逻辑地址；

S73、判断获取垃圾回收的存储块起始存储页和上一次序的存储块起始末尾存储页的逻辑地址是否为连续地址。

若是，则垃圾回收的存储块的首端数据和上一次序的存储块的尾端数据是连续。若否，垃圾回收的存储块的首端数据和下一次序的存储块的尾数据不是连续的。

S81、获取垃圾回收后的存储块的物理地址，并将时间戳表上对应已执行垃圾回收存储块的时间戳值更新为对应垃圾回收后的存储块；

S82、将时间戳表上对应已执行垃圾回收存储块的时间戳值删除。

本领域普通技术人员可以理解实现上述实施例的全部或部分步骤可以通过硬件来完成，也可以通过程序来指令相关的硬件完成，所述的程序可以存储于闪存中。

在上述实施例中，可以全部或部分地通过软件、硬件、固件或者其任意结合来实现。当使用软件实现时，可以全部或部分地以计算机程序产品的形式实现。所述计算机程序产品包括一个或多个计算机指令。在计算机上加载和执行所述计算机指令时，全部或部分地产生按照本发明实施例所述的流程或功能。所述计算机可以是通用计算机、专用计算机、计算机网络、或者其他可编程装置。计算机指令可以存储在计算机可读移动式存储设备中。

以上所述仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。