Data compression method and apparatus

Patent metadata

Field	Value
Publication number	US-12373393-B2
Application number	US-202318475849-A
Country	US
Kind code	B2
Filing date	Sep 27, 2023
Priority date	Mar 30, 2021
Publication date	Jul 29, 2025
Grant date	Jul 29, 2025

Abstract

A data compression method includes providing one or more data block sets, where each data block set includes a plurality of data blocks with a same fingerprint; providing one or more compression groups based on a similarity degree between a plurality of data blocks included in each data block set, where one compression group includes a plurality of similar data blocks, the plurality of similar data blocks are a subset of data blocks included in the one or more data block sets, and a similarity degree between the plurality of similar data blocks meets a specific similarity condition; and compressing the plurality of similar data blocks included in the compression group.

First claim

What is claimed is:

1. A method comprising:
providing one or more data block sets;
generating one or more compression groups based on a similarity degree between a plurality of data blocks in each of the data block sets, wherein a compression group of the one or more compression groups comprises a plurality of similar data blocks in the one or more data block sets, wherein each of the similar data blocks has N data features that describe a data block from N dimensions, and wherein the similarity degree meets a similarity condition; and
compressing the plurality of similar data blocks comprised in the compression group;
wherein the similarity condition comprises that at least two of the similar data blocks share M data features of the N data features, wherein M is less than or equal to N, and wherein there is an association relationship between the plurality of similar data blocks in the compression group,
wherein the plurality of similar data blocks form a logic chain, wherein the association relationship is that two adjacent similar data blocks on the logic chain share P data features, and wherein P is greater than or equal to M and less than or equal to N, and
wherein compressing the plurality of similar data blocks comprised in the compression group comprises:
selecting for a data block on a child node in a tree relationship a data block on a parent node of the child node as a reference data block; and
performing delta compression on the child node data blocks based on the respective reference blocks to obtain compressed data.

2. The method of claim 1 , wherein the similarity condition further comprises that M is greater than a threshold.

3. The method of claim 1 , wherein a quantity of the plurality of similar data blocks is X, wherein the similarity condition comprises selecting X data blocks with a highest similarity degree from the one or more data block sets based on the N data features, and wherein X is an integer greater than or equal to 2.

4. The method of claim 1 , further comprising:
calculating a similar fingerprint of a to-be-compressed data block;
recording the to-be-compressed data block into a first data block set corresponding to a second data block that has the same fingerprint as the to-be-compressed data block, wherein the first data block set is one of the one or more data block sets;
determining, from the first data block set, a target data block that shares data features with the to-be-compressed data block;
determining a first compression group comprising the target data block; and
adding the to-be-compressed data block to the first compression group.

5. The method of claim 1 , further comprising generating metadata of the compressed data, wherein the metadata comprises location information of the plurality of similar data blocks, and wherein the metadata is for decompressing the compressed data.

6. The method of claim 1 , further comprising generating metadata of the compressed data, wherein the metadata comprises information about the reference data block during the delta compression and comprises location information of data from the delta compression on each similar data block, and wherein the metadata is for decompressing the compressed data.

7. An apparatus comprising:
a memory configured to store instructions; and
a processor coupled to the memory and configured to: provide one or more data block sets;
generate one or more compression groups based on a similarity degree between a plurality of data blocks in each of the data block sets, wherein a compression group of the one or more compression groups comprises a plurality of similar data blocks in the one or more data block sets, wherein each of the similar data blocks has N data features that describe a data block from N dimensions, and wherein the similarity degree meets a similarity condition; and
compress the plurality of similar data blocks comprised in the compression group,
wherein the similarity condition comprises that at least two of the similar data blocks share M data features of the N data features, wherein M is less than or equal to N, and wherein there is an association relationship between the plurality of similar data blocks in the compression group,
wherein the plurality of similar data blocks form a logic chain, wherein the association relationship is that two adjacent similar data blocks on the logic chain share P data features, and wherein P is greater than or equal to M and less than or equal to N, and
wherein compressing the plurality of similar data blocks comprised in the compression group comprises:
selecting for a data block on a child node in a tree relationship a data block on a parent node of the child node as a reference data block; and
performing delta compression on the child node data blocks based on the respective reference blocks to obtain compressed data.

8. The apparatus of claim 7 , wherein the similarity condition further comprises that M is greater than a threshold.

9. The apparatus of claim 7 , wherein a quantity of the plurality of similar data blocks is X, wherein the similarity condition comprises selecting X data blocks with a highest similarity degree from the one or more data block sets based on the N data features, and wherein X is an integer greater than or equal to 2.

10. The apparatus of claim 7 , wherein the processor is further configured to:
calculate a similar fingerprint of a to-be-compressed data block;
record the to-be-compressed data block into a first data block set corresponding to a second data block that has the same similar fingerprint as the to-be-compressed data block, wherein the first data block set is one of the one or more data block sets;
determine, from the first data block set, a target data block that shares data features with the to-be-compressed data block;
determine a first compression group comprising the target data block; and
add the to-be-compressed data block to the first compression group.

11. The apparatus of claim 7 , wherein the processor is further configured to generate metadata of the compressed data, wherein the metadata comprises location information of the plurality of similar data blocks, and wherein the metadata is for decompressing the compressed data.

12. The apparatus of claim 7 , wherein the processor is further configured to generate metadata of the compressed data, wherein the metadata comprises information about the reference data block during the delta compression and location information of data from the delta compression on each similar data block, and wherein the metadata is for decompressing the compressed data.

Assignees

• Huawei Tech Co Ltd

Inventors

• Liu Bang
• Zhu Kai
• Li Ke
• Yang Wen
• Shen Jianqiang

Classifications

• G06F3/0673

  Single storage device · CPC title

• G06F3/0641

  De-duplication techniques · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title

• H03M7/3091

  Data deduplication · CPC title

• H03M7/3077

  Sorting · CPC title