System and methods for storage data deduplication

One or more non-transitory computer-readable media storing instructions for managing data in a storage system, wherein the instructions, when executed by one or more processors, cause:

• receiving, from at least one writing entity, requests for a plurality of write operations;
• wherein the plurality of write operations are for writing a plurality of received blocks to storage;
• wherein each block of the plurality of received blocks is associated with a Logical Block Address (LBA);
• creating a sequence of clumps from the plurality of received blocks, wherein each clump comprises a group of blocks, and wherein a first clump includes a first group of blocks in which the LBAs of the blocks are not contiguous in LBA space, wherein creating the sequence of clumps comprises:
• compressing each of the plurality of received blocks;
• sorting the plurality of compressed blocks in LBA order;
• and
• packing groups of blocks into corresponding clumps;
• creating a data structure for storing LBA-to-clump mappings;
• for each block of the plurality of received blocks, storing a corresponding entry in the data structure;
• within each entry in the data structure, storing:
• the LBA that is associated with the received block to which the entry corresponds, and
• a reference tuple that includes a clump identifier for the clump that stores data for the corresponding LBA of the entry and a position of the block within the clump;
• and
• after creating the data structure, using entries in the data structure to determine the clumps that store data for the received blocks.

A system comprising one or more processors and one or more computer-readable media storing instructions that when executed cause the one or more processors to perform operations comprising:

• receiving, from at least one writing entity, requests for a plurality of write operations;
• wherein the plurality of write operations are for writing a plurality of received blocks to storage;
• wherein each block of the plurality of received blocks is associated with a Logical Block Address (LBA);
• creating a sequence of clumps from the plurality of received blocks, wherein each clump comprises a group of blocks, and wherein a first clump includes a first group of blocks in which the LBAs of the blocks are not contiguous in LBA space, wherein creating the sequence of clumps comprises:
• compressing each of the plurality of received blocks;
• sorting the plurality of compressed blocks in LBA order;
• and
• packing groups of blocks into corresponding clumps;
• creating a data structure for storing LBA-to-clump mappings;
• for each block of the plurality of received blocks, storing a corresponding entry in the data structure;
• within each entry in the data structure, storing:
• the LBA that is associated with the received block to which the entry corresponds, and
• a reference tuple that includes a clump identifier for the clump that stores data for the corresponding LBA of the entry and a position of the block within the clump;
• and
• after creating the data structure, using entries in the data structure to determine the clumps that store data for the received blocks.