Methods and apparatus for data processing using data compression, linked lists and de-duplication techniques

One or more non-transitory tangible media encoding logic that includes instructions for execution that when executed by a processor, is operable to perform operations comprising:

• receiving a request to store a current block of data at a particular logical block address;
• generating a hash value from the block of data to be stored and a hash function;
• compressing the block of data to be stored to generate a current compressed block of data having a first size;
• determining whether there is a previously stored hash value at the particular logical block address within a logical block address to hash value table;
• when it is determined that there is not a previously stored hash value at the particular logical block address, determining whether there is a previously stored physical block address linked list entry within a hash value to physical block address table at an index corresponding to the generated hash value;
• when it is determined that there is a physical block address linked list entry at the index corresponding to the generated hash value, determining whether the current block of data matches a previously stored block of data associated with the physical block address linked list entry at the index corresponding to the generated hash value;
• and
• when it is determined that the current block of data matches the previously stored block of data, updating the logical block address to hash value table to include a new entry at the particular logical block address and not storing the current compressed block of data.

A data processing apparatus comprising:

• at least one memory;
• at least one processor that executes instructions, wherein the processor and the memory cooperate such that the data processing apparatus is configured for:
• receiving a request to store a current block of data at a particular logical block address;
• generating a hash value from the block of data to be stored and a hash function;
• compressing the block of data to be stored to generate a current compressed block of data having a first size;
• determining whether there is a previously stored hash value at the particular logical block address within a logical block address to hash value table;
• when it is determined that there is not a previously stored hash value at the particular logical block address, determining whether there is a previously stored physical block address linked list entry within a hash value to physical block address table at an index corresponding to the generated hash value;
• when it is determined that there is a physical block address linked list entry at the index corresponding to the generated hash value, determining whether the current block of data matches a previously stored block of data associated with the physical block address linked list entry at the index corresponding to the generated hash value;
• and
• when it is determined that the current block of data matches the previously stored block of data, updating the logical block address to hash value table to include a new entry at the particular logical block address and not storing the current compressed block of data.