Data replication using deduplication and synchronized hash tables

A system comprising:

• one or more processors;
• and
• a memory comprising code stored thereon that, when executed by at least a first of the one or more processors, performs a method of processing write operations comprising:
• receiving, at a first data storage array, a first write operation that writes first data to a first device of the first data storage array, wherein the first device is a first logical device that has storage provisioned from at least one non-volatile storage device of the first data storage array and that is configured for replication on a second device, wherein the second device is a second logical device of a second data storage array and the second logical device has storage provisioned from at least one non-volatile storage device of the second data storage array;
• performing first processing that determines whether the first data written by the first write operation is a duplicate of an existing entry in a first hash table of the first data storage array;
• responsive to determining the first data written by the first write operation is a duplicate of an existing entry in the first hash table, performing second processing comprising:
• preparing a final buffer including information used by the second data storage array in replicating the first write operation on the second device of the second data storage array, wherein the existing entry is included in a list of one or more entries associated with a first hash index of the first hash table, wherein the final buffer includes first metadata identifying the existing entry of the first hash table that is a duplicate of the first data of the first write operation, wherein the first metadata of the final buffer includes a first collision value denoting a position of the existing entry in the list of one or more entries associated with the first hash index;
• responsive to determining the first data written by the first write operation is unique and is not a duplicate of an existing entry in the first hash table, performing third processing comprising:
• inserting, into the first hash table, a first new entry that stores the first data written by the first write operation, wherein the first new entry is included in the list of one or more entries associated with the first hash index;
• and
• preparing the final buffer including information used by the second data storage array in replicating the first write operation on the second device of the second data storage array, wherein the final buffer includes second metadata used by the second data storage array in creating another new entry in a second hash table on the second data storage array, wherein the another new entry corresponds to the first new entry of the first hash table of the first data storage array, wherein the second metadata of the final buffer includes a second collision value denoting a position of the first new entry in the list;
• transmitting the final buffer from the first data storage array to the second data storage array;
• and
• determining that the first hash table is full whereby each hash index of the first hash table is associated with at least one entry such that a any next unique data block specified by a received write operation will result in a hash collision in the first hash table for a hash index generated from the next unique data block, thereby requiring a new entry for the next unique data block being associated with the hash index;
• responsive to determining the first hash table is full, removing a set of one or more entries from the first hash table wherein each entry of the set has an associated count that is less than other associated counts of other entries of the first hash table not included in the set, where the associated count for said each entry of the first hash table denotes a number of times stored data associated with said each entry has been detected as a duplicate;
• and
• updating the second hash table to remove a corresponding entry for each entry of the first hash table removed by said removing.

A computer readable medium comprising code stored thereon that performs a method of processing write operations comprising:

• receiving, at a first data storage array, a first write operation that writes first data to a first device of the first data storage array, wherein the first device is a first logical device that has storage provisioned from at least one non-volatile storage device of the first data storage array and that is configured for replication on a second device, wherein the second device is a second logical device of a second data storage array and the second logical device has storage provisioned from at least one non-volatile storage device of the second data storage array;
• performing first processing that determines whether the first data written by the first write operation is a duplicate of an existing entry in a first hash table of the first data storage array;
• responsive to determining the first data written by the first write operation is a duplicate of an existing entry in the first hash table, performing second processing comprising:
• preparing a final buffer including information used by the second data storage array in replicating the first write operation on the second device of the second data storage array, wherein the existing entry is included in a list of one or more entries associated with a first hash index of the first hash table, wherein the final buffer includes first metadata identifying the existing entry of the first hash table that is a duplicate of the first data of the first write operation, wherein the first metadata of the final buffer includes a first collision value denoting a position of the existing entry in the list of one or more entries associated with the first hash index;
• responsive to determining the first data written by the first write operation is unique and is not a duplicate of an existing entry in the first hash table, performing third processing comprising:
• inserting, into the first hash table, a first new entry that stores the first data written by the first write operation, wherein the first new entry is included in the list of one or more entries associated with the first hash index;
• and
• preparing the final buffer including information used by the second data storage array in replicating the first write operation on the second device of the second data storage array, wherein the final buffer includes second metadata used by the second data storage array in creating another new entry in a second hash table on the second data storage array, wherein the another new entry corresponds to the first new entry of the first hash table of the first data storage array, wherein the second metadata of the final buffer includes a second collision value denoting a position of the first new entry in the list;
• transmitting the final buffer from the first data storage array to the second data storage array;
• and
• determining that the first hash table is full whereby each hash index of the first hash table is associated with at least one entry such that a next unique data block specified by a received write operation will result in a hash collision in the first hash table for a hash index generated from the next unique data block, thereby requiring a new entry for the next unique data block being associated with the hash index;
• responsive to determining the first hash table is full, removing a set of one or more entries from the first hash table wherein each entry of the set has an associated count that is less than other associated counts of other entries of the first hash table not included in the set, where the associated count for said each entry of the first hash table denotes a number of times stored data associated with said each entry has been detected as a duplicate;
• and
• updating the second hash table to remove a corresponding entry for each entry of the first hash table removed by said removing.