Metadata compression techniques

Patent metadata

Field	Value
Publication number	US-11163468-B2
Application number	US-201916458864-A
Country	US
Kind code	B2
Filing date	Jul 1, 2019
Priority date	Jul 1, 2019
Publication date	Nov 2, 2021
Grant date	Nov 2, 2021

Abstract

Techniques for processing metadata (MD) may include: determining, in accordance with one or more criteria, a plurality of MD blocks that are similar and expected to have matching corresponding portions of MD in at least some of the plurality of MD blocks; forming a MD superblock including the plurality of MD blocks; filtering the MD superblock and generating a filtered MD superblock, wherein said filtering includes rearranging content of the MD superblock so that a first plurality of MD portions that are similar are grouped together in the filtered MD superblock, wherein at least some of the first plurality of MD portions that are similar are expected to match; and compressing the filtered MD superblock and generating a compressed filtered MD superblock. Filtering may include performing a bitshuffle algorithm that includes performing a bitwise transpose of a matrix of the MD blocks in the MD superblock.

First claim

What is claimed is:

1. A method of processing metadata (MD) comprising:
determining, in accordance with one or more criteria, a plurality of MD blocks that are similar and expected to have matching corresponding portions of MD in at least some of the plurality of MD blocks;
forming a MD superblock including the plurality of MD blocks;
filtering the MD superblock and generating a filtered MD superblock, wherein said filtering includes rearranging content of the MD superblock so that a first plurality of MD portions that are similar are grouped together in the filtered MD superblock, wherein at least some of the first plurality of MD portions that are similar are expected to match; and
compressing the filtered MD superblock and generating a compressed filtered MD superblock, and wherein said filtering includes:
representing the plurality of MD blocks as a matrix, wherein a plurality of rows of the matrix correspond to the plurality of MD blocks and each of the plurality of rows corresponds to one of the plurality of MD blocks, wherein a plurality of columns of the matrix correspond to a total number of bit positions in each of the plurality of MD blocks.

2. The method of claim 1 , further comprising:
storing the compressed filtered MD superblock in a cache.

3. The method of claim 1 , wherein each of the first plurality of MD portions that are similar is included in one of the plurality of MD blocks.

4. The method of claim 3 , wherein each of the first plurality of MD portions that are similar is included in a same MD field in one of the plurality of MD blocks.

5. The method of claim 4 , wherein each of the plurality of MD blocks has a same defined structure including a plurality of MD fields, and wherein the same MD field is located at a same logical offset in each of the plurality of MD blocks.

6. The method of claim 1 , wherein the one or more criteria include spatial locality of user data associated with the plurality of MD blocks.

7. The method of claim 1 , wherein the one or more criteria include temporal locality of user data associated with the plurality of MD blocks.

8. The method of claim 1 , wherein the one or more criteria include spatial location of the plurality of MD blocks.

9. The method of claim 1 , wherein the one or more criteria include one or more characteristics of user data associated with the plurality of MD blocks.

10. The method of claim 9 , wherein the one or more characteristics include a number of differences between two user data portions of a same MD field described by two of the plurality of MD blocks.

11. The method of claim 1 , wherein each of the plurality of MD blocks includes a plurality of MD fields.

12. The method of claim 11 , wherein said filtering includes:
performing a bit-wise transpose of the matrix to obtain a transposed matrix.

13. The method of claim 12 , wherein the transposed matrix is the filtered MD superblock provided as an input to compression processing performed in said compressing.

14. A method of processing metadata (MD) comprising:
determining, in accordance with one or more criteria, a plurality of MD blocks that are similar and expected to have matching corresponding portions of MD in at least some of the plurality of MD blocks;
forming a MD superblock including the plurality of MD blocks;
filtering the MD superblock and generating a filtered MD superblock, wherein said filtering includes rearranging content of the MD superblock so that a first plurality of MD portions that are similar are grouped together in the filtered MD superblock, wherein at least some of the first plurality of MD portions that are similar are expected to match;
compressing the filtered MD superblock and generating a compressed filtered MD superblock;
storing the compressed filtered MD superblock in a cache;
receiving an I/O operation directed to a target location;
determining that a first MD block of the plurality of MD blocks is associated with the target location, wherein the target location is included in a logical address range of a logical device having corresponding metadata included in the first MD block;
processing the compressed filtered MD superblock to obtain the MD superblock; and
subsequent to said processing the compressed filtered MD superblock, obtaining the first MD block from the MD superblock and using the first MD block to service the I/O operation, and wherein said processing includes:
decompressing the compressed filtered MD superblock to obtain a decompressed filtered MD superblock; and
subsequent to said decompressing, reverse filtering the decompressed filtered MD superblock to obtain the MD superblock.

15. A system comprising:
at least one processor; and
a memory comprising code stored thereon that, when executed, performs a method of processing metadata (MD) comprising:
determining, in accordance with one or more criteria, a plurality of MD blocks that are similar and expected to have matching corresponding portions of MD in at least some of the plurality of MD blocks;
forming a MD superblock including the plurality of MD blocks;
filtering the MD superblock and generating a filtered MD superblock, wherein said filtering includes rearranging content of the MD superblock so that a first plurality of MD portions that are similar are grouped together in the filtered MD superblock, wherein at least some of the first plurality of MD portions that are similar are expected to match; and
compressing the filtered MD superblock and generating a compressed filtered MD superblock, and wherein said filtering includes:
representing the plurality of MD blocks as a matrix, wherein a plurality of rows of the matrix correspond to the plurality of MD blocks and each of the plurality of rows corresponds to one of the plurality of MD blocks, wherein a plurality of columns of the matrix correspond to a total number of bit positions in each of the plurality of MD blocks.

16. A non-transitory computer readable medium comprising code stored thereon that, when executed, performs a method of processing metadata (MD) comprising:
determining, in accordance with one or more criteria, a plurality of MD blocks that are similar and expected to have matching corresponding portions of MD in at least some of the plurality of MD blocks;
forming a MD superblock including the plurality of MD blocks;
filtering the MD superblock and generating a filtered MD superblock, wherein said filtering includes rearranging content of the MD superblock so that a first plurality of MD portions that are similar are grouped together in the filtered MD superblock, wherein at least some of the first plurality of MD portions that are similar are expected to match; and
compressing the filtered MD superblock and generating a compressed filtered MD superblock, and wherein said filtering includes:
representing the plurality of MD blocks as a matrix, wherein a plurality of rows of the matrix correspond to the plurality of MD blocks and each of the plurality of rows corresponds to one of the plurality of MD blocks, wherein a plurality of columns of the matrix correspond to a total number of bit positions in each of the plurality of MD blocks.

17. The non-transitory computer readable medium of claim 16 , wherein the method further comprises:
storing the compressed filtered MD superblock in a cache.

18. The non-transitory computer readable medium of claim 16 , wherein each of the first plurality of MD portions that are similar is included in one of the plurality of MD blocks.

19. The non-transitory omputer re

Assignees

• Emc Ip Holding Co Llc

Inventors

• O Mahony Aidan
• Duquette Jason J

Classifications

• G06F3/0679

  Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP] · CPC title

• G06F3/0656

  Data buffering arrangements · CPC title

• G06F2212/401

  Compressed data · CPC title

• G06F3/0626

  Reducing size or complexity of storage systems · CPC title

• G06F16/907

  Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually · CPC title