Direct lookup for identifying duplicate data in a data deduplication system

Various embodiments for identifying data in a data deduplication system, by a processor device, are provided. In one embodiment, a method comprises efficiently identifying duplicate data in the data deduplication system by identifying fingerprint matches using a direct inter-region fingerprint lookup to search for the fingerprint matches in at least one of a plurality of metadata regions, the direct inter-region fingerprint lookup supplementing a central fingerprint index.

BACKGROUND OF THE INVENTION

Field of the Invention

The present invention relates in general computing systems, and more particularly to, various embodiments for identifying duplicate data in data deduplication systems in computing storage environments.

Description of the Related Art

Today with modern technology, large volumes of data are storable on disk drives; these drives can exist as a solo entity, or as part of a broader make up within a larger storage environment. Often times when writing to even the smallest environment, single drives, duplicate data is written. These duplicated contents can then be DE-duplicated using standard deduplication techniques so long as specific metrics are met.

SUMMARY OF THE INVENTION

Various embodiments for identifying data in a data deduplication system, by a processor device, are provided. In one embodiment, a method comprises efficiently identifying duplicate data in the data deduplication system by identifying fingerprint matches using a direct inter-region fingerprint lookup to search for the fingerprint matches in at least one of a plurality of metadata regions, the direct inter-region fingerprint lookup supplementing a central fingerprint index.

In addition to the foregoing exemplary embodiment, various other system and computer program product embodiments are provided and supply related advantages. The foregoing summary has been provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter. The claimed subject matter is not limited to implementations that solve any or all disadvantages noted in the background.

DETAILED DESCRIPTION OF THE DRAWINGS

Data deduplication is a highly important and vibrant field in computing storage systems. Data deduplication refers to the reduction and/or elimination of redundant data. In data deduplication, a data object, which may be a file, a data stream, or some other form of data, is broken down into one or more parts called chunks or blocks. 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. The goal of a data deduplication system is to store a single copy of duplicated data, and the challenges in achieving this goal are efficiently finding the duplicate data patterns in a typically large repository, and storing the data patterns in a storage efficient deduplicated form. A significant challenge in deduplication storage systems is scaling to support very large repositories of data. Such large repositories can reach sizes of Petabytes (1 Petabyte=250bytes) or more. Deduplication storage systems supporting such repository sizes, must provide efficient processing for finding duplicate data patterns within the repositories, where efficiency is measured in resource consumption for achieving deduplication (resources may be CPU cycles, RAM storage, persistent storage, networking, etc.).

With the continued advancement of computer processors and memory, data storage space has begun to lag behind. While storage space has indeed increased, the demands on the existing space have increased dramatically as well. This increase in demands has resulted in new avenues being explored to better utilize the given storage at hand. Data deduplication is one of those avenues. Modern data deduplication users can achieve 10, sometimes up to 20, (or even greater) times the original storage capacity. In other words, the same user, with the benefit of deduplication technology, essentially has the capacity of ten storage units where the user originally had one, without any additional space or power requirements.

The concept of deduplication techniques is to replace duplicate data across a storage system with pointers to a single instance of the data, and hence reduce an overall storage requirement. The design of such a deduplication system requires handling several challenges. Firstly, duplicate data should be identified across potentially very large amounts of data. Once duplicates are found, the system must be able to maintain data in a format containing cross references over the entire system. Often times, this format is a metadata format.

Duplicates are typically identified by the holding of a large index of data chunks that have already appeared in the system (chunks can be of varying sizes). Typically, the index contains fingerprints of chunks representing the data itself, such that the fingerprint is usually a hash value of the actual data in the chunk. Finding repeating fingerprints amounts to identifying repeating chunks of data. The complication is that for a large storage system, the amount of fingerprints may grow to become extraordinarily large, and keeping a full index in memory is simply not feasible. This is especially troublesome in a distributed storage system (where such an index is accessible by several nodes). Rather, systems keep a smaller index in memory and are either content to miss out on potential deduplication opportunities or resort to supplementary mechanisms that make up for the limited in-random access memory (RAM) index.

It should be noted that keeping an entire index on various media, such as disk (be it flash or hard disk drive (HDD)), is scalable in terms of sheer index size, however has a profound time performance impact. Since the index consists of mostly random hashes, it is typically accessed randomly and hence is not susceptible to standard caching techniques.

A number of works and methods exist to deploy a layered strategy for handling an index. The first layer is generally a cache in RAM and a second layer on a slower media. The idea is to minimize the lookups to the slower layer by prefetching fingerprints that may be relevant to RAM, and performing a first look up in the RAM cache. This prefetching is locality based—once a new fingerprint has been found in the index, the RAM fingerprints that appeared together with the fingerprint in the past (neighboring fingerprints) are analyzed, hoping they will yield increased cache hits (matches).

Each of these methods hold a central cache for all lookups. This has an inefficiency in a distributed storage system that handles multiple parallel input sources that are not necessarily related to one another, yet all perform lookups in the same central cache. Moreover, populating the cache may at times be a heavy task, especially in a distributed system where the cache is spread across several nodes.

Accordingly, the illustrated embodiments provide mechanisms for improving deduplication efficiency and speed. These mechanisms are especially advantageous in a large scale distributed storage environment with limited memory, although one of ordinary skill would recognize the mechanisms provided herein may be beneficial for a wide variety of storage systems. In one embodiment, a direct inter-region fingerprint lookup is implemented to supplement a central fingerprint index. The direct lookup mechanism is region dependent, such that each region connects only to the regions that are most relevant to it. The direct lookup may serve as a primary fingerprint search mechanism before accessing the standard index lookup mechanism.

The targeted environment is that of a large primary storage system that receives multiple reads and writes, typically of varying sizes (unlike backup streams that handle solely long sequential writes), although, as aforementioned, may be suitable for a wide body of storage environments. In this manner, data typically has strong locality properties that may be of benefit—namely, the evidence that repeated data tends to appear in batches. Another such property of large and distributed data stores is the case of each region managing its metadata separately. This will provide further benefit as will be described.

The illustrated embodiments provide a mechanism building on existing regional metadata structures to avoid extra effort of populating central indexes, and thus achieve improved deduplication speed. There are several benefits to this mechanism, including: 1. The standard index is considerably smaller making the mechanisms of the present invention very scalable; 2. Repopulation of the index with neighboring fingerprints is not required; 3. Duplicated data may be found even if an owning region's hashes have been evicted from the fingerprint index, since a regional connection still exists; and 4. Fragmentation in the data layout is reduced caused by the main index pointing to multiple regions in a scattered fashion. Other benefits will be discussed.

Turning first toFIG. 1, exemplary architecture10of a computing system environment is depicted. Architecture10may, in one embodiment, be implemented at least as part of a system for effecting mechanisms of the present invention. The computer system10includes central processing unit (CPU)12, which is connected to communication port18and memory device16. The communication port18is in communication with a communication network20. The communication network20and storage network may be configured to be in communication with server (hosts)24and storage systems, which may include storage devices14. The storage systems may include hard disk drive (HDD) devices, solid-state devices (SSD) etc., which may be configured in a redundant array of independent disks (RAID). The operations as described below may be executed on storage device(s)14, located in system10or elsewhere and may have multiple memory devices16working independently and/or in conjunction with other CPU devices12. Memory device16may include such memory as electrically erasable programmable read only memory (EEPROM) or a host of related devices. Memory device16and storage devices14are connected to CPU12via a signal-bearing medium. In addition, CPU12is connected through communication port18to a communication network20, having an attached plurality of additional computer host systems24. In addition, memory device16and the CPU12may be embedded and included in each component of the computing system10. Each storage system may also include separate and/or distinct memory devices16and CPU12that work in conjunction or as a separate memory device16and/or CPU12.

FIG. 2is an exemplary block diagram200showing a hardware structure of a data storage and deduplication system that may be used in the overall context of repository management in data deduplication systems. Host computers210,220,225, are shown, each acting as a central processing unit for performing data processing as part of a data storage system200. The cluster hosts/nodes (physical or virtual devices),210,220, and225may be one or more new physical devices or logical devices to accomplish the purposes of the present invention in the data storage system200. In one embodiment, by way of example only, a data storage system200may be implemented as IBM® ProtecTIER® deduplication system TS7650G™, although one of ordinary skill in the art will recognize that a variety of deduplication hardware and software, separately or in combination, may be utilized to implement the data deduplication functionality according to aspects of the illustrated embodiments.

A Network connection260may be a fibre channel fabric, a fibre channel point to point link, a fibre channel over ethernet fabric or point to point link, a FICON or ESCON I/O interface, any other I/O interface type, a wireless network, a wired network, a LAN, a WAN, heterogeneous, homogeneous, public (i.e. the Internet), private, or any combination thereof. The hosts,210,220, and225may be local or distributed among one or more locations and may be equipped with any type of fabric (or fabric channel) (not shown inFIG. 2) or network adapter260to the storage controller240, such as Fibre channel, FICON, ESCON, Ethernet, fiber optic, wireless, or coaxial adapters. Data storage system200is accordingly equipped with a suitable fabric (not shown inFIG. 2) or network adaptor260to communicate. Data storage system200is depicted inFIG. 2comprising storage controllers240and cluster hosts210,220, and225. The cluster hosts210,220, and225may include cluster nodes.

To facilitate a clearer understanding of the methods described herein, storage controller240is shown inFIG. 2as a single processing unit, including a microprocessor242, system memory243and nonvolatile storage (“NVS”)216. It is noted that in some embodiments, storage controller240is comprised of multiple processing units, each with their own processor complex and system memory, and interconnected by a dedicated network within data storage system200. Storage230(labeled as230a,230b, and230nherein) may be comprised of one or more storage devices, such as storage arrays, which are connected to storage controller240(by a storage network) with one or more cluster hosts210,220, and225connected to each storage controller240through network260.

In some embodiments, the devices included in storage230may be connected in a loop architecture. Storage controller240manages storage230and facilitates the processing of write and read requests intended for storage230. The system memory243of storage controller240stores program instructions and data, which the processor242may access for executing functions and method steps of the present invention for executing and managing storage230as described herein. In one embodiment, system memory243includes, is in association with, or is in communication with the operation software250for performing methods and operations described herein. As shown inFIG. 2, system memory243may also include or be in communication with a cache245for storage230, also referred to herein as a “cache memory,” for buffering “write data” and “read data,” which respectively refer to write/read requests and their associated data. In one embodiment, cache245is allocated in a device external to system memory243, yet remains accessible by microprocessor242and may serve to provide additional security against data loss, in addition to carrying out the operations as described herein.

In some embodiments, cache245is implemented with a volatile memory and non-volatile memory and coupled to microprocessor242via a local bus (not shown inFIG. 2) for enhanced performance of data storage system200. The NVS216included in data storage controller is accessible by microprocessor242and serves to provide additional support for operations and execution of the present invention as described in other figures. The NVS216, may also be referred to as a “persistent” cache, or “cache memory” and is implemented with nonvolatile memory that may or may not utilize external power to retain data stored therein. The NVS may be stored in and with the cache245for any purposes suited to accomplish the objectives of the present invention. In some embodiments, a backup power source (not shown inFIG. 2), such as a battery, supplies NVS216with sufficient power to retain the data stored therein in case of power loss to data storage system200. In certain embodiments, the capacity of NVS216is less than or equal to the total capacity of cache245.

Storage230may be physically comprised of one or more storage devices, such as storage arrays. A storage array is a logical grouping of individual storage devices, such as a hard disk. In certain embodiments, storage230is comprised of a JBOD (Just a Bunch of Disks) array or a RAID (Redundant Array of Independent Disks) array. A collection of physical storage arrays may be further combined to form a rank, which dissociates the physical storage from the logical configuration. The storage space in a rank may be allocated into logical volumes, which define the storage location specified in a write/read request.

In one embodiment, by way of example only, the storage system as shown inFIG. 2may include a logical volume, or simply “volume,” may have different kinds of allocations. Storage230a,230band230nare shown as ranks in data storage system200, and are referred to herein as rank230a,230band230n. Ranks may be local to data storage system200, or may be located at a physically remote location. In other words, a local storage controller may connect with a remote storage controller and manage storage at the remote location. Rank230ais shown configured with two entire volumes,234and236, as well as one partial volume232a.Rank230bis shown with another partial volume232b. Thus volume232is allocated across ranks230aand230b. Rank230nis shown as being fully allocated to volume238—that is, rank230nrefers to the entire physical storage for volume238. From the above examples, it will be appreciated that a rank may be configured to include one or more partial and/or entire volumes. Volumes and ranks may further be divided into so-called “tracks,” which represent a fixed block of storage. A track is therefore associated with a given volume and may be given a given rank.

The storage controller240may include a tracking module255, a storage utilization module258, and a reporting module270. The tracking module255, storage utilization module258and reporting module270may operate in conjunction with each and every component of the storage controller240, the hosts210,220,225, and storage devices230. The tracking module255, storage utilization module258and reporting module270may be structurally one complete module or may be associated and/or included with other individual modules. The tracking module255, storage utilization module258and reporting module270may also be located in the cache245or other components.

The tracking module255, storage utilization module258and reporting module270may individually and/or collectively perform various aspects of the present invention as will be further described. For example, the tracking module255may perform tracking operations and related analytics in accordance with aspects of the illustrated embodiments. The storage utilization module258may also utilize analytics to determine physical or virtual storage capacities in view of deduplication functionality operational on particular storage devices. Finally, reporting module270may notify various portions of the data storage and deduplication system200about such various aspects as current capacity utilization, and so forth. As one of ordinary skill in the art will appreciate, the tracking module255, storage utilization module258, and reporting module270may make up only a subset of various functional and/or functionally responsible entities in the data storage and deduplication system200.

The storage controller240includes a control switch241for controlling the fiber channel protocol, transmission control protocol/internet protocol (TCP/IP), Ethernet protocol, or other such standard, to the host computers210,220,225, a microprocessor242for controlling all the storage controller240, a nonvolatile control memory243for storing a microprogram (operation software)250for controlling the operation of storage controller240, data for control, cache245for temporarily storing (buffering) data, and buffers244for assisting the cache245to read and write data, a control switch241for controlling a protocol to control data transfer to or from the storage devices230, the tracking module255, and the analytics module259, in which information may be set. Multiple buffers244may be implemented with the present invention to assist with the operations as described herein. In one embodiment, the cluster hosts/nodes,210,220,225and the storage controller240are connected through a network adaptor (this could be a fibre channel)260as an interface i.e., via at least one switch called “fabric.”

Turning now toFIG. 3, a flow chart diagram illustrating an exemplary method300for identifying duplicate data in data deduplication systems, among other aspects of the illustrated embodiments, is depicted. As aforementioned the method300may be performed in accordance with the present invention in any of the environments depicted inFIGS. 1-2, among others, in various embodiments. Of course, more or less operations than those specifically described inFIG. 3may be included in method300, as would be understood by one of skill in the art upon reading the present descriptions.

The method300begins (step302). Duplicate data is efficiently identified in a data deduplication system by identifying fingerprint matches using a direct inter-region fingerprint lookup to search for the fingerprint matches in at least one of a plurality of metadata regions, the direct inter-region fingerprint lookup supplementing a central fingerprint index (step304). The method ends (step306).

The mechanisms herein rely generally upon two components, comprising, a central fingerprint index, which is a global repository of fingerprints and serves a full cluster of nodes, and metadata regions, which provide metadata (including fingerprints) for a defined area of user space. For example, a metadata region may be defined to span 128 MB of user space.

The central fingerprint index may be accessed from any point in the system and indicates in which metadata region, if any, a fingerprint may be found. In this way, the index is essentially a fingerprint to owning metadata region lookup table. The central fingerprint index is always kept in memory and may greatly benefit from intelligent eviction processes provided herein.

Metadata regions are a division of user space into small areas (regions) that are swapped in and out of memory. This metadata serves deduplication in addition to other features that are likely to be provided by the storage system, such as compression and thin provisioning. A metadata region contains fingerprints for all data chunks written to the metadata region. The metadata region is responsible for the fingerprint it contains regarding reference creation, deletion, reference counting, and eventual deletion of the chunk and its fingerprint. Given the aforementioned infrastructure, it is possible for Region1to create a reference to Region2without needing the index.

Owing to aspects of the present invention, a direct inter-region fingerprint lookup provides a source for deduplication opportunity searches above and beyond the central fingerprint index described above. In one embodiment, each metadata region gains a dynamic ability to look for matching fingerprints in a subset of other metadata regions, where the set of metadata regions that each metadata region chooses to look may change according to an input/output operation (I/O) workload. This direct inter-region fingerprint lookup greatly expands the deduplication opportunities each metadata region can leverage with no extra metadata cost.

In one embodiment, each metadata region maintains a list of owner regions to which it has already created references to. This list is called the “active owners” list. Once a deduplication reference is created from a first metadata region to a second metadata region, via a hit (fingerprint match) in the index, the first metadata region adds the second metadata region to its active owners list. New writes to the first metadata region will then search for matching fingerprints in the metadata regions contained within the first metadata region's active owners list. Since deduplication (by fingerprint matches) tends to be in batches, there is a high probability that additional fingerprint matches will be found in one of the active owners. If fingerprint matches are not found within any of the metadata regions contained in the active owners, the central fingerprint index is then searched.

Using the direct inter-region fingerprint lookup algorithm, a vast majority of fingerprint matches are found by means of direct inter-region fingerprint lookup, and not by way of the central index lookup. The purpose of the index therefore becomes to provide a first fingerprint match to an owner region, and provide fingerprint matches for exceptional cases in which the deduplication is not localized to a particular metadata region. This is accomplished using a central fingerprint index that is considerably smaller than a standard index, thereby reducing memory requirements and improving scalability.

The functionality of the present invention avoids potential timing issues that may occur in a standard indexing/caching solution. In a traditional index, when a match occurs, the cache must be repopulated. During the repopulation process, potential matches may be missed before the repopulation has completed. Using the direct inter-region fingerprint lookup functionality, however, lookups are sent directly to the owning metadata region. The owning metadata region may delay a response if it must load fingerprints in to memory.

FIG. 4is a block diagram representing a plurality of metadata regions400illustrating the concepts described previously. Shown is Region A402, Region B404, Region C406, and Region D408. Region A shows on it's active owners list, active owners Region B404and Region D408. Likewise, Region C shows on it's active owners list, active owners Region B404and Region D408. Region B404and Region D408show no present active owners. This demonstrates that both Region A402and Region C406have found previous fingerprint matches within Region B404and Region D408.

Using the direct inter-region fingerprint lookup mechanism, Region A402(and similarly Region C406), when receiving a write operation, will first search for fingerprint matches within the metadata regions listed on their respective active owners lists before searching the central fingerprint index. In this example, Region B404and Region D408.

In one embodiment, when evicting an owner from a metadata region's active owners list, an eviction policy may be made reference to the eviction logic of the quality of the connection to each owner. For example, an active owner to which there are few references made via fingerprint matches will be evicted before an owner to which there are many references. This may be a predetermined threshold. Logic such as a most recently used, most frequently used, least recently used, or least frequently used lists may be implemented in determining this threshold.

In other embodiments, active owners may be removed from an active owners list if the list is full and a new active owner is being inserted. Additional eviction logic in accordance with the eviction policy based on missed matches to an owner may be used. Assuming Region B404is an active owner of Region A402, after unsuccessfully looking for fingerprint matches in Region B404several times as determined by a predetermined threshold, Region B404may be removed from the active owners list of Region A402.

In some embodiments, when an inter-region direct lookup request is sent to a metadata region that is not currently in memory, it may be decided by the requesting metadata region to either load or not load the metadata region to it's active owner list. If the region is not added to the active owners list, no resources are spent, and it is assumed that metadata region not being in memory indicates that there is no deduplication currently taking place to this metadata owner region. The decision to load or not to load a metadata region to the requesting metadata region's active owners list may be determined by a predetermined threshold of memory consumption and/or a predetermined threshold of central processing unit (CPU) consumption expected. Within an owning metadata region, fingerprints may be loaded in to memory selectively based on a popularity, memory consumption, and/or a CPU consumption. Again, this may be determined by a predetermined threshold of consumption expected.

Depending on the size of a user write, the write it is likely to contain several chunks. Therefore, in some embodiments, if none of the chunks' fingerprint matches were found by the direct inter-region fingerprint lookup, a lookup to the central fingerprint index will be performed. If all the fingerprint matches are found within a metadata owner region, no central metadata index lookup needs to be performed. If some fingerprint matches are found however some are not, both the direct inter-region fingerprint lookup and central fingerprint mechanisms are plausible. A predetermined threshold may be defined such that if a predetermined number of fingerprint matches are found by direct inter-region fingerprint lookup being below the threshold, a central fingerprint index lookup is initiated.

Continuing toFIG. 5, a flow chart diagram, illustrating an exemplary method500for identifying duplicate data in data deduplication systems is depicted in review of the illustrated embodiments, according to aspects of the present invention. The method500may be performed in accordance with the present invention in any of the environments depicted inFIGS. 1-2, among others, in various embodiments. Of course, more or less operations than those specifically described inFIG. 5may be included in method500, as would be understood by one of skill in the art upon reading the present descriptions.

Beginning at step502, metadata regions are defined, where each metadata region maintains an active owners list of owner regions in which references have been created, via fingerprint matches (step504). When a deduplication reference is created from a first region to a second region by the fingerprint matches, the first region then adds the second region to its active owners list (step506). New writes to the first region then search for matching fingerprints within the regions developed on the active owners list of the first region (step508). If a fingerprint match is not found from within the regions defined on the active owners list of the first region, a central fingerprint index is then searched (step510). The method ends (step512).