Abstract:
Storage infrastructures and methods that generate hash values based on error correction codes. A system is provided that includes: a code retrieval system implemented on a host having logic for issuing a redundancy read command to a storage system to retrieve a redundancy code for an identified data block; and a hashing system implemented on the host for hashing the redundancy code to generate a hash value based on the redundancy code. A storage system is also provided that includes: a memory for storing data blocks and associated redundancy codes; and a controller having: an input/output for receiving a hash value read command for a specified data block from a host and returning a hash value; a decoding system that extracts a redundancy code associated with the specified data block; and an in-memory hashing system for computing a hash operation on the redundancy code.

Description:
CROSS REFERENCE TO RELATED APPLICATION 
       [0001]    This application claims priority to U.S. Provisional Patent Application Ser. No. 62/161,935, filed May 15, 2015, which is hereby incorporated herein as though fully set forth. 
     
    
     TECHNICAL FIELD 
       [0002]    The present invention relates to the field of data storage and processing, and particularly to providing low-cost data hashing and integrity checking services in computing systems. 
       BACKGROUND 
       [0003]    Data hashing is widely used in computing and storage systems for a variety of purposes, e.g., fast data addressing/locating, Bloom filter, data protection, and cryptography. A hash function can map data of arbitrary size to a fixed-size data block that typically has a much smaller size than the original data. There are a large number of hash functions, notably including various cyclic redundancy check (CRC) functions, checksums functions, and cryptographic hash functions. In current practice, a hash function carries out the hashing computation directly on the original data to obtain its hash value, and the hashing computation is typically realized by a host processor unit such as central processing unit (CPU). 
       SUMMARY 
       [0004]    For computing systems that demand data hashing for data being stored in their storage and/or memory devices, this presents a system and method that can largely reduce the computational cost of data hashing. In addition, this presents an in-memory data hashing implementation solution that can further reduce the host computational workload and reduce the data traffic across the storage-memory-CPU hierarchy. 
         [0005]    A first aspect discloses a storage infrastructure that generates hash values based on a coding redundancy, comprising: a code retrieval system implemented on a host having logic for issuing a redundancy read command to a storage system to retrieve a coding redundancy for an identified data block; and a hashing system implemented on the host for hashing the redundancy code to generate a hash value based on the coding redundancy. 
         [0006]    A second aspect discloses a storage system, comprising: a memory for storing data blocks and associated coding redundancy; and a controller having: an input/output for receiving a hash value read command for a specified data block from a host and returning a hash value; a decoding system that extracts a coding redundancy associated with the specified data block; and an in-memory hashing system for computing the hash value from a hash operation on the coding redundancy. 
         [0007]    A third aspect discloses a method for generating a hash value in a storage infrastructure based on a coding redundancy, comprising: issuing a redundancy read command from a host to a storage system to retrieve a coding redundancy for an identified data block; inputting the coding redundancy to the host for the identified data block; and hashing the coding redundancy on the host to generate a hash value based on the coding redundancy. 
         [0008]    A fourth aspect discloses a method for generating hash values in a storage system, comprising: providing a memory for storing data blocks and associated coding redundancy; receiving a hash value read command for a specified data block from a host; extracting a coding redundancy associated with the specified data block; computing a hash value from the coding redundancy; and returning a hash value. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]    The numerous advantages of the present invention may be better understood by those skilled in the art by reference to the accompanying figures in which: 
           [0010]      FIG. 1  illustrates the data flow of using coding redundancy based data hashing according to embodiments; 
           [0011]      FIG. 2  illustrates the operational flow when the host carries out the data hashing according to embodiments; 
           [0012]      FIG. 3  illustrates the operational flow when the data hashing is offloaded to the data storage devices and/or memory controller according to embodiments; 
           [0013]      FIG. 4  illustrates a storage infrastructure for implementing the process shown in  FIG. 2 ; and 
           [0014]      FIG. 5  illustrates a storage infrastructure for implementing the process shown in  FIG. 3 . 
       
    
    
     DETAILED DESCRIPTION 
       [0015]    Reference will now be made in detail to embodiments of the invention, examples of which are illustrated in the accompanying drawings. 
         [0016]    This described approach reduces the computational complexity of data hashing in computing systems. In current practice, given the original data chunk (i.e., data block) to be hashed, the hash function always directly applies the hashing computation onto the original data to obtain the corresponding hash value. In computing systems, the data being stored in data storage devices (such as hard disk drives and solid-state drives) and memory (such as DRAM) are typically protected by error correction coding (ECC) to ensure the data storage integrity and reliability. In essence, ECC encoding carries out a certain computation, which is typically much more complicated than data hashing, on the original data to generate some redundant data called coding redundancy. The coding redundancy is highly correlated with the original data, and the ECC decoding leverages such a strong data correlation to detect and correct errors. 
         [0017]    As illustrated in  FIG. 1 , original data  10  is first encoded with ECC encoding  12  to generate coding redundancy  14 . The coding redundancy  14  is then hashed with data hashing  16  to generate a hash value  18 . The described approach thus applies the data hashing computation  16  onto the coding redundancy  14  (e.g., an 8 byte value) of the original data, instead of the original data  10  (e.g., a 4K byte value), to obtain a hash value  18  for the original data  10 . Since the size of coding redundancy  14  is much less than the size of the original data  10  in typical data storage and memory devices (e.g., 8× less), the data hashing  16  computational complexity can be proportionally reduced. The hash function can remain the same as in current practice. 
         [0018]    In current practice, data storage systems carry out the ECC encoding/decoding internally, which is completely transparent to the host. For the data being stored in memory such as DRAM, the memory controller inside the host processor carries out the ECC encoding/decoding, and the operation is typically transparent to the other components in the host processor. Hence the coding redundancy is not accessible by the other components such as the CPU core. As a result, in current practice, the host processor (i.e., “host”) is not able to directly utilize hashing of redundancy codes to reduce the data hashing computational complexity. To address this issue, two solutions are presented. The first solution is to enhance the host-storage system interfaces in order to allow the host to directly retrieve the ECC coding redundancy from the storage system, i.e., data storage devices or on-chip memory controller. The second solution is to off-load the data hashing computation to the storage system. 
         [0019]    To allow the host to directly retrieve the ECC coding redundancy, the first approach enhances the host-storage interface by adding one or more new commands. Typically, each data block being stored in data storage devices and memory is associated with a unique identification (e.g., the address). In current practice, given the identification of the data being requested by the host, the storage devices and memory controller always send the original data back to the host. This approach adds a new command, referred to as “ECC redundancy read command,” that specifically requests the storage devices and memory controller to send the ECC coding redundancy, instead of the original data, back to the host. 
         [0020]      FIG. 2  illustrates the host command issue data flow. When a data process request is issued within the host, a determination is made at S 1  whether the request is for a data hashing operation. If the request is for data hashing, then the host issues an ECC redundancy read command at S 2  to the storage system. The ECC redundancy read command may for example include an address of an associated data block and an indicator (e.g., an n-bit value) to return a coding redundancy and not the actual data. Then at S 3 , the host receives the ECC coding redundancy from the storage system at S 3  and carries out a hashing computation on the ECC coding redundancy to obtain the hash value. If the request is not for hashing, the host issues a normal data read command at S 5 , receives the original data at S 6 , and carries out the corresponding data processing at S 7 . Thus, when the host needs to carry out data hashing, it issues the “ECC redundancy read command” instead of normal data read command, and carries out the hashing computation based upon the ECC coding redundancy of the data. 
         [0021]    The second approach is to offload the data hashing computation from the host to the storage system, which is referred to as in-memory data hashing. In this context, the host simply issues a command, referred to as “hash value read” command, to the data storage device or memory controller, and a hash value based on the ECC coding redundancy is returned. 
         [0022]      FIG. 3  shows the operational data flow inside data storage devices and memory controller for supporting in-memory data hashing. Upon receiving a “hash value read” command with the corresponding address of the data to be hashed from the host, the data storage device or memory controller reads the data from the storage media (e.g., flash memory chips, DRAM chips, etc.) at S 11 , carries out the ECC decoding to recover the coding redundancy at S 12 , and then carries out the hashing on the coding redundancy to obtain the hash value at S 13 . Once obtained, the hash value is sent back to the host. 
         [0023]      FIG. 4  depicts an infrastructure for carrying out the first process shown in  FIG. 2 . In this case, the host  20  includes an ECC retrieval system  24  that has an ECC read command generator  26  and a hashing system  28 . As noted, when a normal data read operation  30  is processed by the host  20 , the host  20  sends an address  34  to the storage system  22  for a data block  36 , and the data block  36  is returned. When an ECC read operation  32  is processed by host  20 , host  20  send an ECC redundancy read command to the storage system  22  and the coding redundancy (ECC  38 ) is returned. 
         [0024]    The hashing system  28  can then process the ECC  38  and generate a hash value (or signature) that it can use, e.g., to determine if the associated data block  36  exists in some other data center  40 , by performing a similar operations with data center  40  and comparing hash values. ECC retrieval system  24  may be implemented in software (e.g., with a software driver) to simplify the solution on the host  20 . The storage system  22  may utilize an ECC read command processor  50  that parses and processes the ECC read command to extract ECC  38 , e.g., by decoding an identified block of data to determine the ECC  38  using existing ECC coding/decoding infrastructure. 
         [0025]      FIG. 5  depicts an infrastructure for carrying out the second process shown in  FIG. 3 . In this case, the host  60  sends a “hash value read” command to storage system  62 , which includes a controller chip  68  (such as an integrated circuit chip, ASIC device, or other system) that includes an, I/O for receiving commands and outputting hash values, an ECC calculator for decoding data to generate redundancy coding and a hash calculator for performing a hash operation. Accordingly, in this embodiment, the controller chip  68  will read the data from memory, decode the ECC value, calculate the hash value based on the ECC value, and return the hash value to host  60 . 
         [0026]    The embodiments of the present disclosure are applicable to various types of storage devices without departing from the spirit and scope of the present disclosure. It is also contemplated that the term host may refer to various devices capable of sending read/write commands to the storage devices. It is understood that such devices may be referred to as processors, hosts, initiators, requesters or the like, without departing from the spirit and scope of the present disclosure. 
         [0027]    Aspects of the present invention are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by processing logic implemented in hardware and/or computer readable program instructions. For example, the processing logic in the storage system may be implemented with a field programmable gate array (FPGA) device, application specific integrated circuit (ASIC) device, a general purpose IC, or any other device. 
         [0028]    Computer readable program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. These computer readable program instructions may also be stored in a computer readable storage medium that can direct a computer, a programmable data processing apparatus, and/or other devices to function in a particular manner, such that the computer readable storage medium having instructions stored therein comprises an article of manufacture including instructions which implement aspects of the function/act specified in the flowchart and/or block diagram block or blocks. 
         [0029]    The flowcharts and block diagrams in the figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts or carry out combinations of special purpose hardware and computer instructions. 
         [0030]    The foregoing description of various aspects of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed, and obviously, many modifications and variations are possible. Such modifications and variations that may be apparent to an individual in the art are included within the scope of the invention as defined by the accompanying claims.