CN113190468B

CN113190468B - 一种l2p表压缩方法、装置、设备及可读存储介质

Info

Publication number: CN113190468B
Application number: CN202110429711.0A
Authority: CN
Inventors: 张博
Original assignee: Shandong Yingxin Computer Technology Co Ltd
Current assignee: Shandong Yingxin Computer Technology Co Ltd
Priority date: 2021-04-21
Filing date: 2021-04-21
Publication date: 2022-11-25
Anticipated expiration: 2041-04-21
Also published as: CN113190468A

Abstract

本申请公开了一种L2P表压缩方法、装置、设备及可读存储介质。本申请将L2P表划分为多个分表后，预估了各个分表的压缩效果，只有压缩效果较好时，才对相应分表进行压缩，压缩效果不好时保留相应分表中的具体表项，最后合并分表压缩结果和未压缩分表得到整个L2P表的压缩结果，这样基于L2P表中的具体表项分区域确定压缩与否，可以避免产生无效的压缩操作，还可以保证已实施的压缩操作的有效性，因此具有更高的压缩效率，还可以降低压缩时间，提高L2P表传输效率。相应地，本申请提供的一种L2P表压缩装置、设备及可读存储介质，也同样具有上述技术效果。

Description

一种L2P表压缩方法、装置、设备及可读存储介质

技术领域

本申请涉及计算机技术领域，特别涉及一种L2P表压缩方法、装置、设备及可读存储介质。

背景技术

通常，固态硬盘中的L2P表(Logical To Physical Table)较大，当开发人员需要进行数据分析或者验证人员想要检查L2P表是否正确时，有需求要将L2P表从固态硬盘传输到主机中。

由于L2P表较大，导致传输时间较长。现有技术一般使用通用的LZ、霍夫曼等压缩算法压缩L2P表后进行传输，但这些算法的压缩率有限且计算量较大，导致压缩耗时，传输效率可能还不如直接传输原L2P表。

因此，如何在压缩L2P表时避免产生无效的压缩操作，是本领域技术人员需要解决的问题。

发明内容

有鉴于此，本申请的目的在于提供一种L2P表压缩方法、装置、设备及可读存储介质，以在压缩L2P表时避免产生无效的压缩操作。其具体方案如下：

第一方面，本申请提供了一种L2P表压缩方法，包括：

获取L2P表，并将所述L2P表划分为多个分表；

估算每个分表的压缩指标值；

将压缩指标值大于指标阈值的分表确定为未压缩分表，并将所述未压缩分表对应的索引段以及所述未压缩分表中存储的各个PBA记录为第一结果；

将压缩指标值不大于所述指标阈值的分表确定为压缩分表，并为所述压缩分表选择对应的距离函数；利用所述距离函数计算所述压缩分表的PBA特征值，以及所述压缩分表中存储的每个PBA与所述PBA特征值的距离值；将所述距离函数、所述PBA特征值、所述距离值以及所述压缩分表包括的PBA个数记录为第二结果；

合并所述第一结果和所述第二结果，得到所述L2P表的压缩结果。

优选地，所述将所述L2P表划分为多个分表，包括：

读取所述L2P表对应的所有索引，并确定每个索引的写属性；其中，各个索引为连续排列的LBA，且与所述L2P表中存储的PBA一一对应；所述写属性为随机写或连续写；

若排列位置相邻的两个索引的写属性相同，则划分所述两个索引至同一分组，否则，划分所述两个索引至不同分组，以得到顺序排列的多个分组；

基于各个分组将所述L2P表划分为多个分表。

优选地，所述基于各个分组将所述L2P表划分为多个分表，包括：

将所述顺序排列的多个分组切分为包括固定分组个数的多个片段；

针对所述L2P表，以一个片段划分一个分表，得到多个分表；

或

针对所述L2P表，以一个分组划分一个分表，得到多个分表。

优选地，所述将所述L2P表划分为多个分表，包括：

确定由多个顺序排列的LBA缩略图组成的图序列；所述多个顺序排列的LBA缩略图均分所述L2P表对应的固态硬盘中的所有LBA；

读取所述图序列中各个LBA缩略图的写属性；所述写属性为随机写或连续写；

将所述图序列中排列位置相邻且写属性相同的LBA缩略图进行合并，以更新所述图序列；

针对所述L2P表，以更新后的所述图序列中的一个LBA缩略图划分一个分表，得到多个分表。

优选地，所述图序列中各个LBA缩略图的写属性基于写操作实时更新，更新过程包括：

若所述图序列包括的任一个LBA缩略图中的LBA发生写操作，则判断所述写操作的写属性与该LBA缩略图当前的写属性是否一致；

若是，则不更新该LBA缩略图的写属性；

若否，则更新该LBA缩略图的写属性。

优选地，所述更新该LBA缩略图的写属性，包括：

利用随机函数计算随机数，若所述随机数为预设更新标识，则执行所述更新该LBA缩略图的写属性的步骤；否则，不更新该LBA缩略图的写属性。

优选地，所述将所述L2P表划分为多个分表，包括：

读取所述L2P表对应的所有索引；其中，各个索引为连续排列的LBA，且与所述L2P表中存储的PBA一一对应；

在所有索引中确定当前未分组索引，若当前未分组索引不为空，则选择当前未分组索引中的第一个索引对应的PBA作为参考值；

分别计算所述参考值与排列在所述第一个索引后的每个索引对应的PBA的距离值，获得距离值序列；

将所述距离值序列中的第一个距离值作为待对比值；

对比所述待对比值与距离阈值的大小；

若所述待对比值小于所述距离阈值，则将所述待对比值对应的索引与所述第一个索引划分至同一分组，将所述待对比值更新为所述距离值序列中的下一个距离值后，执行所述对比所述待对比值与距离阈值的大小的步骤；

若所述待对比值不小于所述距离阈值，则执行所述在所有索引中确定当前未分组索引的步骤；

若当前未分组索引为空，则针对所述L2P表，以一个分组划分一个分表，得到多个分表。

优选地，所述执行所述在所有索引中确定当前未分组索引的步骤之前，还包括：

若当前分组中的索引个数超过个数阈值，则执行所述在所有索引中确定当前未分组索引的步骤；否则，将所述待对比值对应的索引与所述第一个索引划分至同一分组，将所述待对比值更新为所述距离值序列中的下一个距离值后，执行所述对比所述待对比值与距离阈值的大小的步骤。

优选地，所述估算每个分表的压缩指标值，包括：

基于各个分表中存储的PBA计算差异度，并将所述差异度作为所述压缩指标值。

优选地，所述利用所述距离函数计算所述压缩分表的PBA特征值，包括：

利用所述距离函数分别计算所述压缩分表中的第一个PBA与其他PBA的距离值；

倒序或正序排列所有距离值，以取所有距离值中的中位数作为所述PBA特征值。

第二方面，本申请提供了一种L2P表压缩装置，包括：

划分模块，用于获取L2P表，并将所述L2P表划分为多个分表；

估算模块，用于估算每个分表的压缩指标值；

不压缩模块，用于将压缩指标值大于指标阈值的分表确定为未压缩分表，并将所述未压缩分表对应的索引段以及所述未压缩分表中存储的各个PBA记录为第一结果；

压缩模块，用于将压缩指标值不大于所述指标阈值的分表确定为压缩分表，并为所述压缩分表选择对应的距离函数；利用所述距离函数计算所述压缩分表的PBA特征值，以及所述压缩分表中存储的每个PBA与所述PBA特征值的距离值；将所述距离函数、所述PBA特征值、所述距离值以及所述压缩分表包括的PBA个数记录为第二结果；

合并模块，用于合并所述第一结果和所述第二结果，得到所述L2P表的压缩结果。

第三方面，本申请提供了一种电子设备，包括：

存储器，用于存储计算机程序；

处理器，用于执行所述计算机程序，以实现前述公开的L2P表压缩方法。

第四方面，本申请提供了一种可读存储介质，用于保存计算机程序，其中，所述计算机程序被处理器执行时实现前述公开的L2P表压缩方法。

通过以上方案可知，本申请提供了一种L2P表压缩方法，包括：获取L2P表，并将所述L2P表划分为多个分表；估算每个分表的压缩指标值；将压缩指标值大于指标阈值的分表确定为未压缩分表，并将所述未压缩分表对应的索引段以及所述未压缩分表中存储的各个PBA记录为第一结果；将压缩指标值不大于所述指标阈值的分表确定为压缩分表，并为所述压缩分表选择对应的距离函数；利用所述距离函数计算所述压缩分表的PBA特征值，以及所述压缩分表中存储的每个PBA与所述PBA特征值的距离值；将所述距离函数、所述PBA特征值、所述距离值以及所述压缩分表包括的PBA个数记录为第二结果；合并所述第一结果和所述第二结果，得到所述L2P表的压缩结果。

可见，本申请将L2P表划分为多个分表，然后估算每个分表的压缩指标值，基于压缩指标值大小将所有分表分为两类：未压缩分表(压缩效果不好)和压缩分表(压缩效果较好)。针对未压缩分表，将未压缩分表对应的索引段以及未压缩分表中存储的各个PBA记录为第一结果(即保留该分表中的具体表项)；针对压缩分表，为压缩分表选择对应的距离函数；利用距离函数计算压缩分表的PBA特征值，以及压缩分表中存储的每个PBA与PBA特征值的距离值；将距离函数、PBA特征值、距离值以及压缩分表包括的PBA个数记录为第二结果。最后合并压缩分表的压缩结果和未压缩分表本身为整个L2P表的压缩结果。可见，本申请将L2P表划分为多个分表后，预估了各个分表的压缩效果，只有压缩效果较好时，才对相应分表进行压缩，压缩效果不好时保留相应分表中的具体表项，最后合并分表压缩结果和未压缩分表得到整个L2P表的压缩结果，这样基于L2P表中的具体表项分区域确定压缩与否，可以避免产生无效的压缩操作，还可以保证已实施的压缩操作的有效性，因此具有更高的压缩效率，还可以降低压缩时间，提高L2P表传输效率。

相应地，本申请提供的一种L2P表压缩装置、设备及可读存储介质，也同样具有上述技术效果。

附图说明

为了更清楚地说明本申请实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本申请的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。

图1为本申请公开的第一种L2P表压缩方法流程图；

图2为本申请公开的第二种L2P表压缩方法流程图；

图3为本申请公开的一种L2P表压缩装置示意图；

图4为本申请公开的一种电子设备示意图。

具体实施方式

下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。

目前，现有技术一般使用通用的LZ、霍夫曼等压缩算法压缩L2P表后进行传输，但这些算法的压缩率有限且计算量较大，导致压缩耗时，传输效率可能还不如直接传输原L2P表。为此，本申请提供了一种L2P表压缩方案，能够在压缩L2P表时避免产生无效的压缩操作，还可以保证已实施的压缩操作的有效性，具有更高的压缩效率。

在介绍本申请之前，对本申请涉及的相关技术进行如下介绍。

一般地，固态硬盘出厂时，其中预设有L2P表，但表中没有记录内容。在固态硬盘的使用过程中，L2P表会陆续记录内容。

固态硬盘(SSD)是一种用来存储数据的设备。固态硬盘由控制器，存储介质(NAND)等模块组成。控制器是一种硬件设备，一般是由专用芯片(ASIC)实现。在控制器上运行的Firmware是一种软件程序。因此固态硬盘中软件与硬件相互配合。控制器中运行Firmware(一种嵌入式软件)进行资源的控制，即：对存储介质中的数据进行存储调度，维护NAND等设备。

固态硬盘可以与主机进行通信，主机将存储请求发给固态硬盘，并且将要存储的数据发给固态硬盘，固态硬盘获得请求后，将数据存储至NAND介质中。

NAND介质具有不可复写的特性，即在擦除前，如果一个地址被写过，则不能再次重新写入，直到擦除为止。但是由于数据是按照页写入，而擦除按照块擦除，因此不能将上次写入的位置上的数据擦除进行再次写入，故需要由Firmware维护一个表。当有新的数据写入时，根据算法分配一个新的空闲NAND地址(即PBA，全称为Physics Block Address)，将用户数据写入这个空闲地址，然后记录该NAND地址至L2P表，同时记录该NAND地址对应的逻辑地址(LBA，全称为Logical Block Address)作为该NAND地址的索引。其中，作为索引的逻辑地址连续排列。

参见图1所示，本申请实施例公开了第一种L2P表压缩方法，包括：

S101、获取L2P表，并将L2P表划分为多个分表。

L2P表一般存在于固态硬盘中，因此可以从固态硬盘获取L2P表。划分分表的方式可以有多种，但任一种划分方式均能够划分L2P表中的表项分布，从而实现基于表项分布划分L2P表的目的。具体的划分方式将在下文进行介绍。

其中，L2P表中记录的是各个物理地址(PBA，全称为Physics Block Address)，而每个物理地址所的索引为相应的逻辑地址，物理地址与逻辑地址一一对应。所有逻辑地址连续排列，但L2P表中记录的各个物理地址可能连续，也可能不连续。

S102、估算每个分表的压缩指标值。

在本实施例中，估算每个分表的压缩指标值是为了确定：每个分表的压缩效果的好坏。若分表的压缩指标值较大，则表明压缩效果不好；若分表的压缩指标值较小，则表明压缩效果较好。因此本实施例依据压缩指标值大小将所有分表分为压缩分表(即需要压缩的分表)和未压缩分表(即不用压缩的分表)。

压缩分表经过压缩后，其分表大小将远小于压缩前的大小。而未压缩分表经过压缩后，其分表大小可能和压缩前的大小无异，甚至可能大于压缩前的大小，故对未压缩分表进行的压缩操作可以认为是无效的压缩操作，本实施例能够避免产生此类压缩操作。

压缩指标值(Compression ratio)用于描述压缩文件的效果，其相当于压缩率。压缩率是文件压缩后的大小与压缩前的大小之比，例如：把100m的文件压缩后是90m，压缩率为90/100*100％＝90％，压缩率一般是越小越好。

在一种具体实施方式中，估算每个分表的压缩指标值，包括：基于各个分表中存储的PBA计算差异度，并将差异度作为压缩指标值。

S103、将压缩指标值大于指标阈值的分表确定为未压缩分表，并将未压缩分表对应的索引段以及未压缩分表中存储的各个PBA记录为第一结果。

针对不用压缩的未压缩分表，保留其本身即可，具体可以记录相应的索引段(即该分表中记录的各个PBA所对应的LBA)，表中的具体内容(即各个PBA)等。

S104、将压缩指标值不大于指标阈值的分表确定为压缩分表，并为压缩分表选择对应的距离函数；利用距离函数计算压缩分表的PBA特征值，以及压缩分表中存储的每个PBA与PBA特征值的距离值；将距离函数、PBA特征值、距离值以及压缩分表包括的PBA个数记录为第二结果。

针对需要压缩的压缩分表，执行S104进行压缩操作。其中，距离函数可以自定义，也可以从众多距离函数中选择一个。距离函数中可以定义：两个PBA距离的计算规则，计算规则如：两个PBA直接作差得到距离；或将两个PBA中的任一个PBA进行移位操作，然后用移位操作后的PBA与未移位操作的PBA作差得到距离；或两个PBA直接作差，对作差后的差值做除法得到距离。不同的压缩分表可以用相同的距离函数，也可以用不同的。

示例如下：假设两个PBA分别为：11000011、00101101，那么两个PBA直接作差即为：11000011-00101101或00101101-11000011。移位后作差可以为：将11000011右移1位得到：01100001，进而计算01100001-00101101或00101101-01100001。作差后做除法可以为：11000011-00101101＝10010110，然后用10010110除以某一个固定值(如10010110)，得到距离。由于PBA所包含的字段较复杂，因此实际应用时，应充分考虑PBA所包含的字段来制定合适的距离函数，上述两个PBA仅为示例。

在一种具体实施方式中，利用距离函数计算压缩分表的PBA特征值，包括：利用距离函数分别计算压缩分表中的第一个PBA与其他PBA的距离值；倒序或正序排列所有距离值，以取所有距离值中的中位数作为PBA特征值。

在S104中，压缩分表中存储的每个PBA与PBA特征值的距离值有多个，记录时可以使用霍夫曼编码或其他编码方式进行编码后再记录。

S105、合并第一结果和第二结果，得到L2P表的压缩结果。

压缩过的分表具有第二结果，未压缩过的分表具有第一结果，因此合并第一结果和第二结果即：记录所有分表的相应结果，将其看作L2P表的压缩结果。

在一种具体实施方式中，得到L2P表的压缩结果之后，还包括：利用LZ、霍夫曼等压缩算法对L2P表的压缩结果进行重复压缩，并传输重复压缩后的结果，以完成L2P表的传输。

可见，本实施例将L2P表划分为多个分表后，预估了各个分表的压缩效果，只有压缩效果较好时，才对相应分表进行压缩，压缩效果不好时保留相应分表中的具体表项，最后合并分表压缩结果和未压缩分表得到整个L2P表的压缩结果，这样基于L2P表中的具体表项分区域确定压缩与否，可以避免产生无效的压缩操作，还可以保证已实施的压缩操作的有效性，因此具有更高的压缩效率，还可以降低压缩时间，提高L2P表传输效率。

需要说明的是，划分分表的方式可以有多种，下述将介绍3种方式。下述3种方式任选其一即可。

第一种：按照写入模式(连续写或随机写)划分。具体包括以下步骤：

读取L2P表对应的所有索引，并确定每个索引的写属性；其中，各个索引为连续排列的LBA，且与L2P表中存储的PBA一一对应；写属性为随机写或连续写；

若排列位置相邻的两个索引的写属性相同，则划分两个索引至同一分组，否则，划分两个索引至不同分组，以得到顺序排列的多个分组；

基于各个分组将L2P表划分为多个分表。

在一种具体实施方式中，基于各个分组将L2P表划分为多个分表，包括：

将顺序排列的多个分组切分为包括固定分组个数的多个片段；

针对L2P表，以一个片段划分一个分表，得到多个分表；

或

针对L2P表，以一个分组划分一个分表，得到多个分表。

具体的，当一个地址上写入数据时，写入模式要么为连续写，要么为随机写。依据上述步骤可有如下示例：假设连续排列的LBA为：1、2、3、4、5、6，其中，1对应随机写，2对应连续写，3对应连续写，4对应连续写，5对应随机写，6对应连续写，那么可得到顺序排列的多个分组：分组A(包括1)；分组B(包括2、3、4)；分组C(包括5)，分组D(包括6)。至此，可以将一个分组看作一个分表，那么可得到4个分表(此方式得到的分表个数较多)。也可以设定固定分组个数，按照固定分组个数切分得到片段，将一个片段看作一个分表(此方式得到的分表个数较少)。例如：固定分组个数设定为2，那么分组A和分组B即为一个片段，分组C和分组D即为另一个片段，那么即可得到2个分表。

其中，也可以设定一个分表内允许出现的写入模式变化次数，然后按照该变化次数来对各个分组进行切分。例如设定一个分表内允许出现的写入模式变化次数为1，那么还是能得到：分组A和分组B为一个片段，分组C和分组D为另一个片段，得到2个分表。可见，设定一个分表内允许出现的写入模式变化次数，和设定包括固定分组个数的片段能够达到相同效果，都能减少分表的个数。

第二种：按照预设的LBA缩略图划分，具体包括以下步骤：

确定由多个顺序排列的LBA缩略图组成的图序列；多个顺序排列的LBA缩略图均分L2P表对应的固态硬盘中的所有LBA；

读取图序列中各个LBA缩略图的写属性；写属性为随机写或连续写；

将图序列中排列位置相邻且写属性相同的LBA缩略图进行合并，以更新图序列；

针对L2P表，以更新后的图序列中的一个LBA缩略图划分一个分表，得到多个分表。

在一种具体实施方式中，图序列中各个LBA缩略图的写属性基于写操作实时更新，更新过程包括：

若图序列包括的任一个LBA缩略图中的LBA发生写操作，则判断写操作的写属性与该LBA缩略图当前的写属性是否一致；

若是，则不更新该LBA缩略图的写属性；

若否，则更新该LBA缩略图的写属性。

在一种具体实施方式中，更新该LBA缩略图的写属性，包括：

利用随机函数计算随机数，若随机数为预设更新标识，则执行更新该LBA缩略图的写属性的步骤；否则，不更新该LBA缩略图的写属性。

需要说明的是，多个顺序排列的LBA缩略图在L2P表使用之前划分得到，也就是：在固态硬盘出厂时已有LBA缩略图。在固态硬盘使用之前，各个LBA缩略图的写属性为初始状态，此时可用任意字符表示，如：0。随着数据的写入，各个LBA缩略图的写属性随之变化。当需要传输L2P表时，可读取当前时刻下每个LBA缩略图的写属性，以便进行分表。

其中，各个LBA缩略图的写属性随数据写入变化的具体过程可参照下述示例。假设L2P表的所有索引为：1、2、3、4、5、6，按照每2个地址对应一个LBA缩略图，那么可得到2个LBA缩略图：图a(包括1、2)，图b(包括3、4)，图c(包括5、6)，设定图a、图b、图c的初始写属性为连续写。如果地址1上发生连续写，那么不用改变图a的写属性，如果地址2又发生随机写，那么可以直接将图a的写属性由连续写改变为随机写，使LBA缩略图写属性保持较高精度，即缩略图的敏感度较高。

但是，考虑到实际情况下，一个LBA缩略图中包括的LBA较多，若每次写属性变化都更改LBA缩略图的写属性，将会出现频繁更改的情况。为避免频繁更改，可以用一个随机函数来控制是否真的需要更改。例如：设定一个有1/100的概率输出为1，有99/100的概率输出为0的随机函数，同时设定输出为1(即预设更新标识)时更改写属性，那么当LBA缩略图中某一个LBA发生的写操作的写属性与该LBA缩略图当前的写属性不一致时，控制该函数输出随机数，若随机数为1，则更改LBA缩略图的写属性；否则，不更改LBA缩略图的写属性。其中，由于输出预设更新标识的概率较小，因此更改LBA缩略图写属性的概率也较小，故可避免频繁更改的情况，但精度可能有所降低。其中，可以控制随机函数输出预设更新标识的概率小于一个阈值，从而降低LBA缩略图写属性的变化频率，即降低缩略图的敏感度。

在上述示例的基础上，假设在某一时刻下需要压缩L2P表，且当前图a、图b、图c的写属性分别为：连续写、连续写、随机写，那么图a和图b就可以合并为一个，得到只有两个图的新图序列，之后将这两个图分别看作一个分表，从而得到两个分表。其中，图a、图b、图c组成原图序列。

其中，多个顺序排列的LBA缩略图可按照下述示例得到。假设初始状态的L2P表所对应的索引有1024个，每512个LBA切分为一个LBA缩略图，那么1024/512＝2个LBA缩略图。

第三种：按照实际压缩效果划分，具体包括以下步骤：

读取L2P表对应的所有索引；其中，各个索引为连续排列的LBA，且与L2P表中存储的PBA一一对应；

分别计算参考值与排列在第一个索引后的每个索引对应的PBA的距离值，获得距离值序列；

将距离值序列中的第一个距离值作为待对比值；

对比待对比值与距离阈值的大小；

若待对比值小于距离阈值，则将待对比值对应的索引与第一个索引划分至同一分组，将待对比值更新为距离值序列中的下一个距离值后，执行对比待对比值与距离阈值的大小的步骤；

若待对比值不小于距离阈值，则执行在所有索引中确定当前未分组索引的步骤；

若当前未分组索引为空，则针对L2P表，以一个分组划分一个分表，得到多个分表。

在一种具体实施方式中，执行在所有索引中确定当前未分组索引的步骤之前，还包括：

若当前分组中的索引个数超过个数阈值，则执行在所有索引中确定当前未分组索引的步骤；否则，将待对比值对应的索引与第一个索引划分至同一分组，将待对比值更新为距离值序列中的下一个距离值后，执行对比待对比值与距离阈值的大小的步骤。

以上述步骤为基础，可有如下示例：假设L2P表对应的所有索引为：ABCDEF，且L2P表中记录的PBA为：896537。其中，A映射B，B映射9，C映射6，其他各个索引与PBA的映射关系依次类推。

那么针对ABCDEF第一次分组，当前未分组索引即为ABCDEF，未分组索引不为空，所以选择A对应的8为参考值，之后计算8和9、8和6、8和5、8和3、8和7的距离值，得到-1、2、3、5、1这个距离值序列。将其中第一个距离值-1作为待对比值，对比-1和4(假设距离阈值为4)，此时-1小于4，那么-1对应的索引B能够和A为同一组，之后将距离值序列中的第二个距离值2作为待对比值，对比2和距离阈值4，如此循环……

当将距离值序列中的第四个距离值5作为待对比值，对比5和距离阈值4时，待对比值5不小于距离阈值4，所以5对应的E不能和A归为同一组，因此需要重新确定当前未分组索引。当前可以确定出当前未分组索引为E和F，此时E为当前未分组索引中的第一个索引，那么参考值为E对应的3，之后可按照上述过程执行，直至所有索引被分组。

为避免出现随机扰动，也就是：避免出现零星一个或少量个索引占用一个组，可以设定如下条件：当出现待对比值不小于距离阈值的情况时，判断当前分组中的索引个数是否超过个数阈值，若是，则对剩下未分组的索引重新进行分组；若否，则将偶然出现的较大差值仍然划分至当前组，以避免零星一个或少量个索引占用一个组。

其中，该过程中的距离值的计算可以使用某一个距离函数。

参见图2所示，本申请实施例公开了一种L2P表压缩方案，该方案包括：确定分表、压缩字段和非压缩字段，按照压缩字段压缩相应区域并记录结果，按照非压缩字段记录结果。

L2P表是一个较大的表，一般有4G、8G、16G甚至更大，压缩前将L2P表分为多个分表，这样可按照每个分表中的表项分布来确定是否压缩，从而提升压缩效率。分表划分方式可参照上文的相关介绍。

针对需要压缩的分表设计压缩字段，包括：压缩标记、距离函数的表达式、PBA特征值、该PBA特征值与本分表内每个PBA的距离值。针对不需要压缩的分表设计非压缩字段，包括：非压缩标记、本区域的长度(索引段)、本分表的原始内容。

(1)用差异度作为压缩指标值，以确定哪些分表需要压缩，哪些分表不需要压缩。

如果一个分表内的PBA的差异性太大，那么压缩效果可能不好，压缩过程还会耗费CPU等资源，还不如不压缩，因此可以用差异度作为分表的压缩指标值。

其中，差异度用于表示一个分表内所有PBA的差异大小，故差异度可以是：方差、均方差、范数或信息熵等参数，具体使用哪种参数可以在计算复杂度和效果之间进行取舍。

例如：计算一个分表内所有PBA的范数：基于分表内的所有PBA制作直方图，然后计算每个直方图的概率的数学期望，作为这个分表的压缩指标值。计算一个分表内所有PBA的方差，将分表内的所有PBA的方差，作为这个分表内的压缩指标值。

如果一个分表的压缩指标值大于指标阈值，则选择不进行压缩，否则进行压缩。

(2)距离函数的定义。

由于相邻的LBA，往往会分配到相邻的物理地址上(这是由于Firmware以及用户写入模式导致的)，因此对于相邻的表项差异可能很小，因此记录表项之间的差值，就可以认为记录了表项本身。

但是物理地址的差异并不是单纯的做减法。由于一个物理地址可能包括channel(通道)、target(目标)、lun(卷)、Block(块)、Page(页)、dataframe(数据帧)等字段。因此相邻的物理地址，他们的差值并不一定是1。例如：两个相邻的物理地址A和B，A位于channel0，target0，lun0，block0，page0，dataframe3，B位于channel1，target0，lun0，block0，page0，dataframe0。可以看出，dataframe3的下一个位置是channel1的dataframe0，而不是dataframe4，因此直接作差值，可能会产生一个很大的数，不利于压缩，故可以将物理地址中的字段移位后再作差，或者定义其他的计算规则。当然，也可以直接作差。

其中，不管定义了何种计算规则，只需在记录距离函数时，描述相应计算规则在分表的压缩结果中即可。

距离函数就是表示两个PBA之间差值的函数。由于一个firmware可能在L2P表中实现不同种类的表项分布，因此为了让任意两个PBA之间的差值为1，可以设计多个距离函数。

距离函数可以根据相应分表中的表项分布来定义。若设计有多个距离函数，那么可以用不同序号进行区分。例如：1号表示第一种距离函数，2号表示第二种距离函数。这些序号由验证者和开发者了解即可(假设验证者和开发者已知每个距离函数的计算规则)。当然，也可以用表达式描述不同距离函数的计算规则。当然，也可以将上面两种方法结合起来，将压缩所需要的多个距离函数放在全局数据流的开始位置，再由每个分表内保存一个编号，以表示当前分表是用的哪个距离函数。不同分表所用的距离函数可以相同，也可以不同。

(3)PBA特征值的计算。

针对每个需要压缩的分表，使用对应的距离函数将该分表中的第一个PBA(以索引顺序确定PBA顺序)与其他PBA作差，然后对差值进行排序，取中位数对应的PBA作为当前分表的PBA特征值。以该方式计算PBA特征值，可以避免将该分表中偶然存在的噪声选择为PBA特征值。

需要说明的是，若一个分表内的PBA与PBA特征值的相关性太低，会导致该分表的压缩效果降低。

(4)压缩结果的生成。

针对已压缩的分表，记录压缩标记、距离函数的表达式、PBA特征值、该PBA特征值与本分表内每个PBA的距离值。针对未压缩的分表，记录非压缩标记、本区域的长度(索引段)、本分表的原始内容。将这些内容存储在数据流中。

通过上述，即可完成L2P表的压缩。需要解压时，按照数据流中记录的相关信息反向处理，即可恢复L2P表。

下面对本申请实施例提供的一种L2P表压缩装置进行介绍，下文描述的一种L2P表压缩装置与上文描述的一种L2P表压缩方法可以相互参照。

参见图3所示，本申请实施例公开了一种L2P表压缩装置，包括：

划分模块301，用于获取L2P表，并将L2P表划分为多个分表；

估算模块302，用于估算每个分表的压缩指标值；

不压缩模块303，用于将压缩指标值大于指标阈值的分表确定为未压缩分表，并将未压缩分表对应的索引段以及未压缩分表中存储的各个PBA记录为第一结果；

压缩模块304，用于将压缩指标值不大于指标阈值的分表确定为压缩分表，并为压缩分表选择对应的距离函数；利用距离函数计算压缩分表的PBA特征值，以及压缩分表中存储的每个PBA与PBA特征值的距离值；将距离函数、PBA特征值、距离值以及压缩分表包括的PBA个数记录为第二结果；

合并模块305，用于合并第一结果和第二结果，得到L2P表的压缩结果。

在一种具体实施方式中，划分模块包括：

第一读取单元，用于读取L2P表对应的所有索引，并确定每个索引的写属性；其中，各个索引为连续排列的LBA，且与L2P表中存储的PBA一一对应；写属性为随机写或连续写；

第一合并单元，用于若排列位置相邻的两个索引的写属性相同，则划分两个索引至同一分组，否则，划分两个索引至不同分组，以得到顺序排列的多个分组；

第一划分单元，用于基于各个分组将L2P表划分为多个分表。

在一种具体实施方式中，第一划分单元包括：

切分子单元，用于将顺序排列的多个分组切分为包括固定分组个数的多个片段；

第一划分子单元，用于针对L2P表，以一个片段划分一个分表，得到多个分表；

或

第二划分子单元，用于针对L2P表，以一个分组划分一个分表，得到多个分表。

在一种具体实施方式中，划分模块包括：

确定单元，用于确定由多个顺序排列的LBA缩略图组成的图序列；多个顺序排列的LBA缩略图均分L2P表对应的固态硬盘中的所有LBA；

第二读取单元，用于读取图序列中各个LBA缩略图的写属性；写属性为随机写或连续写；

第二合并单元，用于将图序列中排列位置相邻且写属性相同的LBA缩略图进行合并，以更新图序列；

第二划分单元，用于针对L2P表，以更新后的图序列中的一个LBA缩略图划分一个分表，得到多个分表。

在一种具体实施方式中，划分模块还包括更新单元，用于图序列中各个LBA缩略图的写属性基于写操作实时更新，更新单元包括：

判断子单元，用于若图序列包括的任一个LBA缩略图中的LBA发生写操作，则判断写操作的写属性与该LBA缩略图当前的写属性是否一致；

保持子单元，用于若是，则不更新该LBA缩略图的写属性；

更新子单元，用于若否，则更新该LBA缩略图的写属性。

在一种具体实施方式中，更新子单元具体用于：

在一种具体实施方式中，划分模块包括：

第三读取单元，用于读取L2P表对应的所有索引；其中，各个索引为连续排列的LBA，且与L2P表中存储的PBA一一对应；

选择单元，用于在所有索引中确定当前未分组索引，若当前未分组索引不为空，则选择当前未分组索引中的第一个索引对应的PBA作为参考值；

计算单元，用于分别计算参考值与排列在第一个索引后的每个索引对应的PBA的距离值，获得距离值序列；

对比单元，用于将距离值序列中的第一个距离值作为待对比值；对比待对比值与距离阈值的大小；

第一分组单元，用于若待对比值小于距离阈值，则将待对比值对应的索引与第一个索引划分至同一分组，将待对比值更新为距离值序列中的下一个距离值后，执行对比待对比值与距离阈值的大小的步骤；

执行单元，用于若待对比值不小于距离阈值，则执行在所有索引中确定当前未分组索引的步骤；

第三划分单元，用于若当前未分组索引为空，则针对L2P表，以一个分组划分一个分表，得到多个分表。

在一种具体实施方式中，划分模块还包括：

第二分组单元，用于若当前分组中的索引个数超过个数阈值，则执行在所有索引中确定当前未分组索引的步骤；否则，将待对比值对应的索引与第一个索引划分至同一分组，将待对比值更新为距离值序列中的下一个距离值后，执行对比待对比值与距离阈值的大小的步骤。

在一种具体实施方式中，估算模块具体用于：

基于各个分表中存储的PBA计算差异度，并将差异度作为压缩指标值。

在一种具体实施方式中，压缩模块具体用于：

利用距离函数分别计算压缩分表中的第一个PBA与其他PBA的距离值；

倒序或正序排列所有距离值，以取所有距离值中的中位数作为PBA特征值。

在一种具体实施方式中，还包括：

重复压缩模块，用于利用LZ、霍夫曼等压缩算法对L2P表的压缩结果进行重复压缩，并传输重复压缩后的结果，以完成L2P表的传输。

其中，关于本实施例中各个模块、单元更加具体的工作过程可以参考前述实施例中公开的相应内容，在此不再进行赘述。

可见，本实施例提供了一种L2P表压缩装置，该装置将L2P表划分为多个分表后，预估了各个分表的压缩效果，只有压缩效果较好时，才对相应分表进行压缩，压缩效果不好时保留相应分表中的具体表项，最后合并分表压缩结果和未压缩分表得到整个L2P表的压缩结果，这样基于L2P表中的具体表项分区域确定压缩与否，可以避免产生无效的压缩操作，还可以保证已实施的压缩操作的有效性，因此具有更高的压缩效率，还可以降低压缩时间，提高L2P表传输效率。

下面对本申请实施例提供的一种电子设备进行介绍，下文描述的一种电子设备与上文描述的一种L2P表压缩方法及装置可以相互参照。

参见图4所示，本申请实施例公开了一种电子设备，包括：

存储器401，用于保存计算机程序；

处理器402，用于执行所述计算机程序，以实现上述任意实施例公开的方法。

下面对本申请实施例提供的一种可读存储介质进行介绍，下文描述的一种可读存储介质与上文描述的一种L2P表压缩方法、装置及设备可以相互参照。

一种可读存储介质，用于保存计算机程序，其中，所述计算机程序被处理器执行时实现前述实施例公开的L2P表压缩方法。关于该方法的具体步骤可以参考前述实施例中公开的相应内容，在此不再进行赘述。

本申请涉及的“第一”、“第二”、“第三”、“第四”等(如果存在)是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的数据在适当情况下可以互换，以便这里描述的实施例能够以除了在这里图示或描述的内容以外的顺序实施。此外，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含，例如，包含了一系列步骤或单元的过程、方法或设备不必限于清楚地列出的那些步骤或单元，而是可包括没有清楚地列出的或对于这些过程、方法或设备固有的其它步骤或单元。

需要说明的是，在本申请中涉及“第一”、“第二”等的描述仅用于描述目的，而不能理解为指示或暗示其相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。另外，各个实施例之间的技术方案可以相互结合，但是必须是以本领域普通技术人员能够实现为基础，当技术方案的结合出现相互矛盾或无法实现时应当认为这种技术方案的结合不存在，也不在本申请要求的保护范围之内。

本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其它实施例的不同之处，各个实施例之间相同或相似部分互相参见即可。

结合本文中所公开的实施例描述的方法或算法的步骤可以直接用硬件、处理器执行的软件模块，或者二者的结合来实施。软件模块可以置于随机存储器(RAM)、内存、只读存储器(ROM)、电可编程ROM、电可擦除可编程ROM、寄存器、硬盘、可移动磁盘、CD-ROM、或技术领域内所公知的任意其它形式的可读存储介质中。

本文中应用了具体个例对本申请的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本申请的方法及其核心思想；同时，对于本领域的一般技术人员，依据本申请的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本申请的限制。

Claims

1.一种L2P表压缩方法，其特征在于，包括：

获取L2P表，并将所述L2P表划分为多个分表；

估算每个分表的压缩指标值；

合并所述第一结果和所述第二结果，得到所述L2P表的压缩结果；

所述将所述L2P表划分为多个分表，包括：

2.根据权利要求1所述的方法，其特征在于，所述将所述L2P表划分为多个分表，包括：

基于各个分组将所述L2P表划分为多个分表。

3.根据权利要求2所述的方法，其特征在于，所述基于各个分组将所述L2P表划分为多个分表，包括：

针对所述L2P表，以一个片段划分一个分表，得到多个分表；

或

针对所述L2P表，以一个分组划分一个分表，得到多个分表。

4.根据权利要求1所述的方法，其特征在于，所述图序列中各个LBA缩略图的写属性基于写操作实时更新，更新过程包括：

若是，则不更新该LBA缩略图的写属性；

若否，则更新该LBA缩略图的写属性。

5.根据权利要求4所述的方法，其特征在于，所述更新该LBA缩略图的写属性，包括：

6.根据权利要求1所述的方法，其特征在于，所述将所述L2P表划分为多个分表，包括：

将所述距离值序列中的第一个距离值作为待对比值；

对比所述待对比值与距离阈值的大小；

7.根据权利要求6所述的方法，其特征在于，所述执行所述在所有索引中确定当前未分组索引的步骤之前，还包括：

8.根据权利要求1至7任一项所述的方法，其特征在于，所述估算每个分表的压缩指标值，包括：

9.根据权利要求1至7任一项所述的方法，其特征在于，所述利用所述距离函数计算所述压缩分表的PBA特征值，包括：

10.一种L2P表压缩装置，其特征在于，包括：

划分模块，用于获取L2P表，并将所述L2P表划分为多个分表；

估算模块，用于估算每个分表的压缩指标值；

合并模块，用于合并所述第一结果和所述第二结果，得到所述L2P表的压缩结果；

其中，划分模块，具体包括：

11.一种电子设备，其特征在于，包括：

存储器，用于存储计算机程序；

处理器，用于执行所述计算机程序，以实现如权利要求1至9任一项所述的方法。

12.一种可读存储介质，其特征在于，用于保存计算机程序，其中，所述计算机程序被处理器执行时实现如权利要求1至9任一项所述的方法。