Devices, systems, and methods having high data deduplication and low read latencies

A memory system, comprising:

• a nonvolatile memory (NVM) including a data partition and an address indirection table (AIT) partition;
• a memory controller coupled to the NVM, and further comprising:
• a hash engine;
• a hash table;
• and
• circuitry configured to:
• divide a received data string to be written to the NVM into a plurality of data segments having an original sequence;
• rearrange the plurality of data segments according to a predetermined pattern into a rearranged sequence;
• perform a hash operation on the rearranged sequence to generate a hash value;
• perform a lookup of the hash table for the hash value;
• and
• when the hash value is not in the hash table the circuitry is further configured to:
• write the data string to a physical address in the NVM;
• enter the hash value of the rearranged sequence into the hash table;
• enter a pointer to the physical address into the hash table;
• and
• associate the pointer with the hash value;
• and
• when the hash value is in the hash table the circuitry is further configured to:
• retrieve a pointer associated with the hash value from the hash table;
• check a state of a deduplication (dedupe) bit referenced by the pointer, wherein when the state of the dedupe bit is “true” the circuitry, to deduplicate the rearranged sequence, is further configured to;
• write the original sequence to the NVM;
• and
• write and ordered sequence pointer with the original sequence in the NVM, where the ordered sequence pointer maps the original sequence to a physical address of an ordered sequence of data segments having the hash value of the rearranged sequence.

A computer-implemented method, comprising:

• receiving, at a memory controller, a write request with a data string from a host;
• dividing, using a deduplication engine in the memory controller, the data string into a plurality of data segments having an original sequence;
• rearranging, using the deduplication engine in the memory controller, the plurality of data segments according to a predetermined pattern to generate a rearranged sequence;
• performing a hash operation, using a hash engine in the memory controller, the rearranged sequence to generate a hash value;
• performing a lookup of a hash table in the hash engine for the hash value;
• and
• when the hash value is not in the hash table, and the method further comprises:
• writing, using the memory controller, the data string to a physical address in a nonvolatile memory (NVM);
• entering the hash value of the rearranged sequence into the hash table;
• entering a pointer to the physical address into the hash table;
• and
• associating the with the hash value;
• and
• when the hash value is in the hash table, and the method further comprises:
• retrieving a pointer associated with the hash value from the hash table;
• checking a state of a deduplication (dedupe) bit referenced by the pointer, wherein when the state of the dedupe bit is “true” the method, to deduplicate the rearranged sequence, further comprises:
• writing, using the memory controller, the original sequence to a nonvolatile memory (NVM);
• and
• writing, using the memory controller, an ordered sequence pointer with the original sequence in the NVM, where the ordered sequence pointer maps the original sequence to a physical address of an ordered sequence having the hash value of the rearranged sequence.