Multi-granular data reduction for remote data replication
View Patent ↗Multi-granular deduplication is performed on I/O data received at a storage system as part of replicating the I/O data to another storage system. Deduplication may be performed in an iterative fashion, for example, on blocks and smaller and smaller sub-blocks of the I/O data. Deduplication may be performed on blocks and smaller sub-blocks by comparing each block or sub-block to preceding blocks or sub-blocks, respectively, in the I/O data to determine if there is a duplicate. If a duplicate block of sub-block is determined for a block or sub-block, the block or sub-block may be replaced in the I/O data with a reference to the duplicate block or sub-block in a deduplication header for the block. A metadata structure may indicate which blocks of the I/O data have had deduplication performed thereon. The replicating storage system may use the metadata structure and deduplication block headers to restore the I/O data.
1. A method of processing I/O data comprised of a plurality of blocks of data, the method comprising:
receiving an I/O request including the I/O data, wherein the I/O data is an I/O data payload of the I/O request, and wherein each block has a position in the I/O data payload;
determining that at least a first block of the plurality of blocks is not a duplicate of any other block of the plurality of blocks;
dividing the at least first block into a plurality of sub-blocks;
determining that at a first sub-block of the plurality of sub-blocks is a duplicate of a second sub-block of the plurality of sub-blocks; and
replacing the at least first sub-block with a reference to the second sub-block to produce deduplicated I/O data, wherein the reference is relative to a position of the second sub-block within the I/O data payload.
2. A method according to claim 1 , further comprising:
determining that at least a second block of the plurality of blocks is a duplicate of a third block of the plurality of blocks; and
replacing the at least second block with a reference to the third block.
3. A method according to claim 1 , further comprising:
determining that at least a second block of the plurality of blocks is a duplicate of a third block of the plurality of blocks; and
refraining from dividing the at least second block into a plurality of sub-blocks or determining whether any sub-blocks of the plurality of sub-blocks is a duplicate of any other sub-block of the plurality of sub-blocks.
4. A method according to claim 1 , wherein determining that the at least first block of the plurality of blocks is not a duplicate includes determining that two or more of the plurality of blocks is not a duplicate of any other block of the plurality of blocks, and
wherein dividing the at least first block into the plurality of sub-blocks includes dividing the two or more blocks into the plurality of sub-blocks.
5. A method according to claim 1 , further comprising:
creating a first data structure corresponding to the I/O data, the first data structure having a number of fields, each field representing a respective one of the blocks of the I/O data and indicating whether the respective block or any sub-block thereof has been replaced with a reference to a duplicate block or duplicate sub-block, respectively.
6. A method according to claim 5 , the method further comprising:
replicating the I/O data to a second storage system, including transmitting the deduplicated I/O data to the second storage system:
at the second storage system, restoring the I/O data from the deduplicated I/O data using the first data structure and one or more references to duplicate blocks and/or duplicate sub-blocks in the deduplicated I/O data.
7. A method according to claim 1 , wherein the I/O data is part of an I/O request received at a first storage system, the method further comprising;
replicating the I/O data to a second storage system, including transmitting the deduplicated I/O data to the second storage system.
8. A method according to claim 7 , further comprising:
compressing the deduplicated I/O data prior to transmitting the deduplicated I/O data to the second storage system such that transmitting the deduplicated I/O data includes transmitting the compressed deduplicated I/O data.
9. A method according to claim 1 , further comprising:
creating the reference to the second sub-block, wherein the reference includes an indication of a position of the second sub-block within the I/O data.
10. A method according to claim 1 , further comprising:
creating the reference to the second sub-block, wherein the reference includes a count of a number of sub-blocks within the first sub-block for which a duplicate sub-block within the I/O data is determined.
11. A data storage system in which I/O data received from a host is comprised of a plurality of blocks of data, the data storage system comprising:
one or more processors; and
a memory comprising code stored thereon that, when executed, performs a method comprising:
receiving an I/O request including the I/O data at the data storage system, wherein the I/O data is an I/O data payload of the I/O request, and wherein each block has a position in the I/O data payload;
determining that at least a first block of the plurality of blocks is not a duplicate of any other block of the plurality of blocks;
dividing the at least first block into a plurality of sub-blocks;
determining that at a first sub-block of the plurality of sub-blocks is a duplicate of a second sub-block of the plurality of sub-blocks; and
replacing the at least first sub-block in the I/O data with a reference to the second sub-block to produce deduplicated I/O data, wherein the reference is relative to a position of the second sub-block within the I/O data payload.
12. A data storage system according to claim 11 , wherein the method further comprises:
determining that at least a second block of the plurality of blocks is a duplicate of a third block of the plurality of blocks; and
replacing the at least second block with a reference to the third block.
13. A data storage system according to claim 11 , wherein the method further comprises:
determining that at least a second block of the plurality of blocks is a duplicate of a third block of the plurality of blocks; and
refraining from dividing the at least second block into a plurality of sub-blocks or determining whether any sub-blocks of the plurality of sub-blocks is a duplicate of any other sub-block of the plurality of sub-blocks.
14. A data storage system according to claim 11 , wherein the method further comprises:
creating a first data structure corresponding to the I/O data, the first data structure having a number of fields, each field representing a respective one of the blocks of the I/O data and indicating whether the respective block or any sub-block thereof has been replaced with a reference to a duplicate block or duplicate sub-block, respectively.
15. A data storage system according to claim 14 , and wherein the method further comprises:
replicating the I/O data to a second storage system, including transmitting the deduplicated I/O data to the second storage system:
at the second storage system, restoring the I/O data from the deduplicated I/O data using the first data structure and one or more references to duplicate blocks and/or duplicate sub-blocks in the deduplicated I/O data.
16. A non-transitory computer-readable medium having software stored thereon for a data storage system in which I/O data received from a host is comprised of a plurality of blocks of data, the software comprising:
executable code that receives an I/O request including the I/O data, wherein the I/O data is an I/O data payload of the I/O request, and wherein each block has a position in the I/O data payload;
executable code that determines that at least a first block of the plurality of blocks is not a duplicate of any other block of the plurality of blocks;
executable code that divides the at least first block into a plurality of sub-blocks;
executable code that determines that at a first sub-block of the plurality of sub-blocks is a duplicate of a second sub-block of the plurality of sub-blocks; and
executable code that replaces the at least first sub-block in the I/O data with a reference to the second sub-block to produce deduplicated I/O data, wherein the reference is relative to a position of the second sub-block within the I/O data payload.
17. A non-transitory computer-readable medium according to claim 16 , wherein the software further comprises:
executable code that determines that at least a second block of the plurality of blocks is a duplicate of a third block of the plurality of blocks; and
executable code that replaces the at least second block with a reference to the third block.
18. A non-transitory computer-readable medium according to claim 16 , wherein the software further comprises:
executable code that determines that at least a second block of the plurality of blocks is a duplicate of a third block of the plurality of blocks; and
executable code that refrains from dividing the at least second block into a plurality of sub-blocks or determining whether any sub-blocks of the plurality of sub-blocks is a duplicate of any other sub-block of the plurality of sub-blocks.
19. A non-transitory computer-readable medium according to claim 16 , wherein the software further comprises:
executable code that creates a first data structure corresponding to the I/O data, the first data structure having a number of fields, each field representing a respective one of the blocks of the I/O data and indicating whether the respective block or any sub-block thereof has been replaced with a reference to a duplicate block or duplicate sub-block, respectively.
20. A non-transitory computer-readable medium according to claim 19 , wherein the software further comprises:
executable code that replicates the I/O data to a second storage system, including transmitting the deduplicated I/O data to the second storage system such that, at the second storage system, the I/O data is restored from the deduplicated I/O data using the first data structure and one or more references to duplicate blocks and/or duplicate sub-blocks in the deduplicated I/O data.