Data deduplication using CRC-seed differentiation between data and stubs

[0001] This application is a Continuation of U.S. patent application Ser. No. 12/730,400, filed on Mar. 24, 2010, the contents of which are incorporated herein by reference.

[0002] 1. Field of the Invention

[0003] The present invention relates in general to computers, and more particularly to apparatus, method and computer program product embodiments for replication of deduplicated data in a computing storage environment.

[0004] 2. Description of the Related Art

[0005] Data deduplication refers to the reduction and/or elimination of redundant data. In a data deduplication process, duplicate copies of data are reduced or eliminated, leaving a minimal amount of redundant copies, or a single copy of the data, respectively. Using deduplication processes provides a variety of benefits, such as reduction of required storage capacity and increased network bandwidth. Due to these and other benefits, deduplication has emerged in recent years as a highly important technological field in computing storage systems. Challenges to providing deduplication functionality include aspects such as efficiently finding duplicated data patterns in typically large storage repositories, and storing the data patterns in a deduplicated storage-efficient form.

[0006] Data deduplication offers the promise of a significant reduction of stored data by identifying repetitive storage of identical data. Once duplicate data is identified by deduplication algorithms (such as various Hash algorithms), the duplicate data is replaced by a stub that points to a parent copy of the data, thus greatly reducing the amount of data stored.

[0007] Since, as one of ordinary skill in the art will appreciate, a deduplication implementation may result in a large number of stubs in relation to actual data, it becomes important to establish a mechanism whereby the data stored pursuant to such deduplication mechanisms may be verified. To this extent, a need exists for mechanism to distinguish between such actual data and stub information when performing such verification, in order to improve overall accuracy and performance.

[0008] Accordingly, and in view of the foregoing, various embodiments for differentiating between data and stubs pointing to a parent copy of deduplicated data are provided. In one embodiment, by way of example only, a method of differentiation is provided. Undeduplicated data is stored with a checksum of an initial value as a first cyclic redundancy check (CRC) seed. A stub pointing to the parent copy of the deduplicated data is stored with an additional checksum of a differing, additional initial value as a second CRC seed.

[0009] In addition to the foregoing exemplary method embodiment, other exemplary system and computer product embodiments are provided and supply related advantages.

[0015] Turning now to FIG. 1, exemplary architecture 10 of data storage systems (e.g., virtual tape systems) in a computing environment is depicted. Architecture 10 provides storage services to local hosts 18 and 20, and replicate data to remote data storage systems as shown. A local storage system server 12 in communication with a storage device 14 is connected to local hosts 18 and 20 over a network including components such as Fibre channel switch 16. Fibre channel switch 16 is capable, for example, of executing commands (such as small computer systems interface (SCSI) commands) for tape devices. The skilled artisan will appreciate that architecture 10 may include a variety of storage components. For example, storage devices 14 may include conventional hard disk drive (HDD) devices, or may include solid state drive (SSD) devices.

[0016] Local storage system server 12 is connected over network 22 to a remote storage system server 24. Remote server 24 communicates with a locally connected disk storage device 26, and with locally connected hosts 30 and 32 via another network and network component 28 such as Fibre channel switch 28. Network 22 may include a variety of network topologies, such as a wide area network (WAN), a local area network (LAN), a storage area network (SAN), network attached storage (NAS), scaled-out network attached storage (SoNAS), and other configurations. Similarly, switches 16 and 28 may include other types of network devices. In an alternate embodiment, switches 16 and 28 are Ethernet switches, Fibre-Channel over Ethernet (FCoE) switches, or Infiniband Switches.

[0017] Architecture 10, as previously described, provides local storage services to local hosts, and provides replicate data to the remote data storage systems (as denoted by data replication functionality using arrow 34). As will be described, various embodiments of the present invention and claimed subject matter may be implemented on architectures such as architecture 10. For example, in one embodiment, the disk storage device 14 may be part of a deduplicated storage system, storing deduplicated data entities. The deduplicated data entities may then undergo a data replication process 34 whereby the deduplicated data entities are replicated on the remote disk storage device 26. One of ordinary skill in the art will appreciate that other system architectures may implement aspects of the present invention.

[0018] The illustrated embodiments described, following, provide a novel approach for facilitating data verification in deduplication settings by differentiating between data and stubs pointing to the parent copy of deduplicated data. In one example, the mechanisms of the illustrated embodiments may be directed to deduplication storage systems that partition the stored deduplicated data into variable sized blocks and achieve storage efficiency, given prior identification of recurring data patterns (via any appropriate method), by repeated referencing of the deduplicated data blocks that contain portions of such recurring data patterns. Here again, however, other deduplication settings may incorporate various aspects of the present invention.

[0019] As will be seen throughout the following, the mechanisms of the present invention utilize differing cyclical redundancy check (CRC) seeds to assist in differentiating between actual data and stubs. One CRC seed is used in conjunction with the actual data, and another, numerically different CRC seed is used in conjunction with stubs. As one of ordinary skill in the art will appreciate, CRCs incorporate a method for error checking that detects errors in data segments, such as blocks. Unlike parity checks, the CRC can detect multiple data errors within the same data segment, and thus derive an error rate. CRC seeds are obtained by using an algorithm to generate a value (generally numerical) that is based on the underlying data segment. By using a separate CRC seed for actual data, and an additional CRC for stubs, both data and stubs may be later verified to determine if they are actual data or stubs. The mathematics behind the cyclical redundancy check is that the CRC polynomial creates a checksum and the initial value of that checksum is the CRC seed. Typically, this CRC seed is zero, 0000 (hex). However, the final result of the checksum may be offset by a nonzero CRC seed, such as FFFF (hex), which does not change the mathematical algorithm itself but does change the result of that mathematical algorithm. By using one CRC seed in conjunction with the actual data, and another, numerically different CRC seed in conjunction with stubs, data and stubs can be distinguished from one another based on the checksum stored with the data and stub and the calculated checksum given the choice of CRC seed.

[0020] Turning now to FIG. 2, an exemplary write process 100 incorporating aspects of the present invention is shown. Write process 100 begins at step 102 with a write operation of the data in question to storage. In step 104, following, a check is made whether the data is duplicate, via a Hash algorithm, for example. If the data is not duplicate, the data is stored in the storage (cache, tape, optical, hard disk, or flash memory) using a CRC of 0000 in step 106. However, if the data is duplicate, then only a stub (pointer) is stored and the CRC of that stub is a numerically different number, such as FFFF (hexadecimal) in step 108. The write process ends in step 110. In an alternate embodiment, the stub (pointer) is the digest (output) of the aforementioned Hash algorithm.

[0021] FIG. 3, following, depicts an exemplary read process 200, again in which various aspects of the present invention may be incorporated. Read process 200 begins at step 202 as shown. If in step 204 the information being read is assumed to be data, the CRC seed is assumed to be 0000 (hex) in step 206 and a CRC check of that data is made in step 210. However, if the information being read is assumed to be a stub, the CRC seed is assumed to be FFFF (hex) in step 208, and a check of that stub is made in step 210. If in step 212, the CRC check is affirmative, then the process continues in step 214, now with an understanding of what are data (undeduplicated data) and what is a stub pointing to the parent copy of deduplicated data. The process ends in step 220.

[0022] Returning to step 212, if the CRC check is negative, the process continues to step 216 where the CRC seeds are interchanged and the CRC check is performed again. Inventive step 216 makes the effort to identify data as data and stubs as stubs, as only one CRC seed is associated with data and a numerically different CRC seed is associated with stubs. This way, the IO process differentiates between data and stubs by changing the CRC seed but not the CRC polynomial itself. Returning again to step 212, if the re-performed CRC check on the interchanged CRC is affirmative, the process continues to step 214 as previously described, and the process ends at step 220.

[0023] In an alternative embodiment, a different CRC seed may be used for each type of deduplication algorithm (e.g., Hash algorithm) used in the deduplication process. For example, pointers associated with the Hash algorithm SHA-256 may be assigned a CRC seed of FFFF (hex), while stubs associated with the Hash algorithm SHA-512 may be assigned a different CRC seed of EEEE (hex), and stubs associated with the Hash algorithm MD5 may be assigned a CRC seed of DDDD (hex). In this manner, more than one HASH algorithm may be used in a storage system, and the stubs (pointers) could be correctly associated with the appropriate Hash algorithm. In still another alternative embodiment, a different CRC polynomial may be used for data and stubs.

[0024] The ability to distinguish data from its associated metadata is just as important as being able to distinguish data from its associated stub, as previously described. Accordingly, an additional adaptation to the foregoing exemplary embodiments is now presented. Pursuant to this adaptation, data is assigned a CRC seed of 0000 (hex) and the metadata associated with that data is assigned a different CRC seed, such as 9999 (hex). Distinguishing data from metadata is important, for example, for the new Linear Tape Open (LTO) Generation-5 partitioned tape cartridge, where metadata is stored in one partition of the LTO tape cartridge and data in the other partition of that LTO tape cartridge. This metadata can be associated with LTFS (Long Term File System), a recent product introduced by IBM®, which allows a tape cartridge to mimic a hard disk drive. An example of the use of LTFS would be the long-term archival storage of digital motion pictures from the entertainment industry, where the metadata would be used to point to actual scenes in the digital motion picture.

[0025] In other settings, this metadata can also be associated with DICOM (Digital Imaging and Communications in Medicine), where DICOM metadata is stored in one partition of the LTO tape cartridge and the medical images themselves stored in the other partition of the LTO tape cartridge. Examples of medical imaging include the storage of Magnetic Resonance Imaging (MRI), Computerized Axial Tomography (CAT) scans, echocardiogram video, x-ray images, and the like, where metadata is used to point to actual medical imagery. For both the LTFS and DICOM applications, as well as other possible implementations, the metadata of the desired data may be accessed first using a CRC seed reserved for metadata so that the host can be assured that metadata is being accessed over and above the location of the metadata in the partitioned LTO tape cartridge. Once the metadata is verified to be metadata via a CRC check as shown in FIG. 3, then the data associated with this metadata can be accessed from the data partition of LTO tape cartridge by using a CRC seed reserved for data.

[0026] Here, as before, various embodiments may feature the inclusion of differing CRC seeds corresponding to various types of metadata. Metadata corresponding to certain images, for example, may be assigned a first CRC seed, while metadata corresponding to video may be assigned an additional CRC seed. In one embodiment, CRC seeds differ between the types of video and images as well as the corresponding metadata, to further aide the differentiation between the medical data and the metadata identifying that medical data. For example, MRI metadata has a different CRC seed 1100 (hex) from the CRC seed used for MRI images 0011 (hex), CAT scan metadata has a different CRC seed 2200 (hex) from the CRC seed used for CAT scan images 0022 (hex), echocardiogram metadata has a different CRC seed 3300 (hex) from the CRC seed used for echocardiogram video 0033 (hex), and x-ray image metadata has a different CRC seed 4400 (hex) from the CRC seed used for x-ray image 0044 (hex).

[0027] FIG. 4 hereafter provides an example of a portion of the computer environment 10 depicted in FIG. 1 in which the mechanisms of the foregoing embodiments may be implemented. It should be appreciated, however, that FIG. 4 is only exemplary and is not intended to state or imply any limitation as to the particular architectures in which the exemplary aspects of the various embodiments may be implemented. Many modifications to the architecture depicted in FIG. 4 may be made without departing from the scope and spirit of the following description and claimed subject matter.

[0028] FIG. 4 illustrates a portion 300 of an exemplary computer environment that may be used to implement embodiments of the present invention. A computer 302 comprises a processor 304 and a memory 306, such as random access memory (RAM). In one embodiment, storage system server 12 (FIG. 1) may include components similar to those shown in computer 302. The computer 302 is operatively coupled to a display 319, which presents images such as windows to the user on a graphical user interface 318. The computer 302 may be coupled to other devices, such as a keyboard 316, a mouse device 320, a printer 328, etc. Of course, those skilled in the art will recognize that any combination of the above components, or any number of different components, peripherals, and other devices, may be used with the computer 302.

[0029] Generally, the computer 302 operates under control of an operating system (OS) 308 (e.g. z/OS, OS/2, LINUX, UNIX, AIX, WINDOWS, MAC OS) stored in the memory 306, and interfaces with the user to accept inputs and commands and to present results, for example through a graphical user interface (GUI) module 332. In one embodiment of the present invention, the OS 308 facilitates the backup mechanisms. Although the GUI module 332 is depicted as a separate module, the instructions performing the GUI functions can be resident or distributed in the operating system 308, the application program 310, or implemented with special purpose memory and processors. OS 308 includes a deduplication module 340 which may be adapted for carrying out various processes and mechanisms in the exemplary embodiments previously described. For example, the deduplication module 340 may be adapted for performing the aforementioned CRC checks, or storing the actual data or stubs along with particular CRCs, again as previously described.

[0030] Deduplication module 340 may be implemented in hardware, firmware, or a combination of hardware and firmware. In one embodiment, the deduplication module 340 may be embodied as an application specific integrated circuit (ASIC). As the skilled artisan will appreciate, functionality associated with the deduplication module 340 may also be embodied, along with the functionality associated with the processor 304, memory 306, and other components of computer 302, in a specialized ASIC known as a system on chip (SoC). Further, the functionality associated with the deduplication module (or again, other components of the computer 302) may be implemented as a field programmable gate array (FPGA).

[0031] As depicted in FIG. 4, the computer 302 includes a compiler 312 that allows an application program 310 written in a programming language such as COBOL, PL/1, C, C++, JAVA, ADA, BASIC, VISUAL BASIC or any other programming language to be translated into code that is readable by the processor 304. After completion, the computer program 310 accesses and manipulates data stored in the memory 306 of the computer 302 using the relationships and logic that was generated using the compiler 312. The computer 302 also optionally comprises an external data communication device 330 such as a modem, satellite link, Ethernet card, wireless link or other device for communicating with other computers, e.g. via the Internet or other network.

[0032] Data storage device 322 is a direct access storage device (DASD) 322, including one or more primary volumes holding a number of datasets. DASD 322 may include a number of storage media, such as hard disk drives (HDDs), tapes, and the like. Data storage device 336 may also include a number of storage media in similar fashion to device 322. The device 336 may be designated as a backup device 336 for holding backup versions of the number of datasets primarily stored on the device 322. As one of ordinary skill in the art will appreciate, devices 322 and 336 need not be located on the same machine. Devices 322 may be located in geographically different regions, and connected by a network link such as Ethernet. Devices 322 and 336 may include one or more volumes, with a corresponding volume table of contents (VTOC) for each volume.

[0033] In one embodiment, instructions implementing the operating system 308, the computer program 310, and the compiler 312 are tangibly embodied in a computer-readable medium, e.g., data storage device 320, which may include one or more fixed or removable data storage devices 324, such as a zip drive, floppy disk, hard drive, compact disc (CD), digital versatile disk (DVD), blu-ray disc (BD), digital tape, flash memory card, solid state drive, etc., which are generically represented as the storage device 324. Further, the operating system 308 and the computer program 310 comprise instructions which, when read and executed by the computer 302, cause the computer 302 to perform the steps necessary to implement and/or use the present invention. For example, the computer program 310 may comprise instructions for implementing the grid set manager, grid manager and repository manager previously described. Computer program 310 and/or operating system 308 instructions may also be tangibly embodied in the memory 306 and/or transmitted through or accessed by the data communication device 330. As such, the terms “article of manufacture,” “program storage device” and “computer program product” as may be used herein are intended to encompass a computer program accessible and/or operable from any computer readable device or media.

[0034] Embodiments of the present invention may include one or more associated software application programs 310 that include, for example, functions for managing a distributed computer system comprising a network of computing devices, such as a storage area network (SAN). Accordingly, processor 304 may comprise a storage management processor (SMP). The program 310 may operate within a single computer 302 or as part of a distributed computer system comprising a network of computing devices. The network may encompass one or more computers connected via a local area network and/or Internet connection (which may be public or secure, e.g. through a virtual private network (VPN) connection), or via a fibre channel SAN or other known network types as will be understood by those skilled in the art. (Note that a fibre channel SAN is typically used only for computers to communicate with storage systems, and not with each other.)

[0035] As will be appreciated by one of ordinary skill in the art, aspects of the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon.

[0036] Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a compact disc (CD), a digital versatile disk (DVD), a blu-ray disc (BD), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device.

[0037] Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wired, optical fiber cable, RF, etc., or any suitable combination of the foregoing. Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).

[0038] Aspects of the present invention have been described 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 computer program instructions. These computer 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.

[0039] These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks. The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

[0040] The flowchart and block diagrams in the above 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 code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, 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 combinations of special purpose hardware and computer instructions.

[0041] While one or more embodiments of the present invention have been illustrated in detail, the skilled artisan will appreciate that modifications and adaptations to those embodiments may be made without departing from the scope of the present invention as set forth in the following claims.