Data integrity and loss resistance in high performance and high capacity storage deduplication

Abstract

A memory system for utilizing a deduplication process may include a controller, a storage media, and a non-volatile RAM including a metadata journal and a metadata cache, the metadata cache including an address table and a fingerprinting table, and the metadata journal including a plurality of transactions indicating whether a transaction is successfully written on the storage media.

What is claimed is: 
     
       1. A memory system for utilizing a deduplication process, comprising:
 a controller; 
 a storage media; and 
 a non-volatile RAM including a metadata journal and a metadata cache; 
 wherein the metadata cache includes an address table and a fingerprinting table; 
 wherein the address table and the fingerprinting table are searched in parallel for incoming data chunks and are modified in parallel and in accordance with the searches, each incoming data chunk being categorized as one of new data, duplicate data and updated data, a select incoming data chunk being categorized as:
 new data when the select incoming data chunk is not identified in either the fingerprinting table or the address table, 
 duplicate data when a fingerprint for the select incoming data chunk is found in the fingerprinting table and either no logical address for the select incoming data chunk is found in the address table or a logical address for the select incoming data chunk is found in the address table in which case the logical address and the fingerprint map to a same physical address in the address and fingerprinting tables respectively, and 
 updated data when a logical address for the select incoming data chunk is found in the address table and either no fingerprint for the select incoming data chunk is found in the fingerprinting table or a fingerprint for the select incoming data chunk is found in the fingerprinting table in which case the fingerprint and the logical address do not map to a same physical address in the fingerprinting and address tables respectively; and 
 
 wherein the metadata journal includes a plurality of transactions that reflect modifications to the address table and the fingerprinting table, each of the plurality of transactions indicating a result of a deduplication process performed on a corresponding incoming data chunk including its categorization as one of new data, duplicate data or updated data. 
 
     
     
       2. The memory system of  claim 1 , wherein each of the plurality of transactions includes a commit portion. 
     
     
       3. The memory system of  claim 2 , wherein the commit portion includes a flag indicating that the corresponding transaction is successfully written on the storage media. 
     
     
       4. The memory system of  claim 1 , wherein the plurality of types of data includes data marked for garbage collection. 
     
     
       5. A method for utilizing a deduplication process, comprising:
 storing an address table and a fingerprinting table as a metadata cache on a non-volatile RAM; 
 performing searches on the address and fingerprinting tables in parallel for incoming data chunks; 
 categorizing each incoming data chunk as one of new data, duplicate data and updated data, a select incoming data chunk being categorized as:
 new data when the select incoming data chunk is not identified in either the fingerprinting table or the address table, 
 duplicate data when a fingerprint for the select incoming data chunk is found in the fingerprinting table and either no logical address for the select incoming data chunk is found in the address table or a logical address for the select incoming data chunk is found in the address table in which case the logical address and the fingerprint map to a same physical address in the address and fingerprinting tables respectively, and 
 updated data when a logical address for the select incoming data chunk is found in the address table and either no fingerprint for the select incoming data chunk is found in the fingerprinting table or a fingerprint for the select incoming data chunk is found in the fingerprinting table in which case the fingerprint and the logical address do not map to a same physical address in the fingerprinting and address tables respectively; 
 
 writing a transaction, among a plurality of transactions in a metadata journal, each transaction reflecting a modification to at least one of the address table and the fingerprinting table and indicating the result of a deduplication process performed on a corresponding incoming data chunk including its categorization as one of new data, duplicate data or updated data; and 
 updating, on the non-volatile RAM, the metadata journal, the address and fingerprinting tables being modified in parallel in accordance with the searches. 
 
     
     
       6. The method of  claim 5 , wherein each of the plurality of transactions includes a commit portion. 
     
     
       7. The method of  claim 6 , wherein the commit portion includes a flag indicating that the corresponding transaction is successfully written on the storage media. 
     
     
       8. The method of  claim 5 , wherein the plurality of types of data includes data marked for garbage collection. 
     
     
       9. An apparatus, comprising:
 a memory controller suitable for use in a non-volatile RAM including a metadata journal and a metadata cache; 
 wherein the metadata cache includes an address table and a fingerprinting table; 
 wherein the address table and the fingerprinting table are searched in parallel for incoming data chunks and are modified in parallel and in accordance with the searches, each incoming data chunk being categorized as one of new data, duplicate data and updated data, a select incoming data chunk being categorized as:
 new data when the select incoming data chunk is not identified in either the fingerprinting table or the address table, 
 duplicate data when a fingerprint for the select incoming data chunk is found in the fingerprinting table and either no logical address for the select incoming data chunk is found in the address table or a logical address for the select incoming data chunk is found in the address table in which case the logical address and the fingerprint map to a same physical address in the address and fingerprinting tables respectively, and 
 updated data when a logical address for the select incoming data chunk is found in the address table and either no fingerprint for the select incoming data chunk is found in the fingerprinting table or a fingerprint for the select incoming data chunk is found in the fingerprinting table in which case the fingerprint and the logical address do not map to a same physical address in the fingerprinting and address tables respectively; and 
 
 wherein the metadata journal includes a plurality of transactions that reflect modifications to the address table and the fingerprinting table, each of the plurality of transactions indicating a result of a deduplication process performed on a corresponding incoming data chunk including its categorization as one of new data, duplicate data or updated data. 
 
     
     
       10. The apparatus of  claim 9 , wherein each of the plurality of transactions includes a commit portion. 
     
     
       11. The apparatus of  claim 10 , wherein the commit portion includes a flag indicating that the corresponding transaction is successfully written on a storage media. 
     
     
       12. The apparatus of  claim 9 , wherein the plurality of types of data includes data marked for garbage collection.