Method and system for data deduplication based on load information associated with different phases in a data deduplication pipeline

According to some embodiment, a backup storage system receives, by a first phase of a data deduplication pipeline, a request from a client for reading or writing a data segment associated with a data stream stored in or to a storage system. In response to the request, the system retrieves, by the first phase, load parameters associated with a second phase in the data deduplication pipeline. For each of the load parameters associated with the second phase, the system determines, by the first phase, whether the load parameter has exceeded a load threshold associated with the second phase. The system throttles, by the first phase, performance of a specific job in the data deduplication pipeline by the second phase in response to a determination that at least one of the load parameters associated with the second job phase has exceeded the load threshold associated with the second phase.

FIELD OF THE INVENTION

Embodiments of the present invention relate generally to data storage systems. More particularly, embodiments of the invention relate to method and system for data deduplication based on load information associated with different phases in a data deduplication pipeline.

BACKGROUND

Backup storage systems traditionally have been designed and optimized such that data is stored and restored from the backup storage systems in a sequential manner. Modern backup technologies, such as VM Instant Access/Instant Restore from EMC and changed block tracking (CBT), however do not access data sequentially. Instead, such modern backup technologies may access data randomly. To provide better performance for random input/output (IO) workloads, backup storage systems have largely been retrofitted and tuned for random IO, e.g., read/write, processing.

Furthermore, a file system with support for improving random IO workloads in the backup storage systems would issue additional number of IO requests. On the other hand, sequential IO workloads are processed serially in order to achieve good locality. As such, random IO workloads may generate more IO loads on a particular backup storage system as opposed to the sequential TO workloads. This may lead to imbalance of performance for different types of TO workloads and may result in a client timing out.

With respect to a data deduplication system, a data stream may pass through different stages of execution (e.g., data segmentation, fingerprint calculation, fingerprint verification, compression/decompression, etc.). Complicating matters, some data segments (e.g., duplicate data segments) may not pass through the same stages of execution as other data segments (e.g., non-duplicate data segments), thereby generating different loads on the data deduplication system. This creates complications in understanding the loads on the system and predicting a timeout of a client.

DETAILED DESCRIPTION

According to one aspect of the invention, a storage service engine and/or deduplication storage engine of a storage system may maintain load information for each phase or module in a data deduplication pipeline, and load thresholds associated with the particular phase. For example, the storage service engine and/or deduplication storage engine may keep track of a queue depth and latency associated with a phase or module (e.g., protocol module, chunking module, fingerprint module, fingerprint verification module, and compressor/decompressor module) in the data deduplication pipeline. The load thresholds, for example, may include queue depth thresholds (at phase and system levels), latency thresholds (at phase and system levels). In one aspect, the storage system receives, by a first phase of a data deduplication pipeline, a request from a client for reading or writing a data segment associated with a data stream stored in or to a storage system. In response to the request, the system retrieves, by the first phase, load parameters associated with a second phase in the data deduplication pipeline. For each of the load parameters associated with the second phase, the system determines, by the first phase, whether the load parameter has exceeded a load threshold associated with the second phase. The system throttles, by the first phase, performance of a specific job in the data deduplication pipeline by the second phase in response to a determination that at least one of the load parameters associated with the second job phase has exceeded the load threshold associated with the second phase.

According to another aspect of the invention, in response to a determination that none of the load parameters associated with the second phase has exceeded the load threshold associated with the second phase, the storage system enqueues an entry into a job queue corresponding to the second phase, where the entry commands the performance the specific job in the data deduplication pipeline by the second phase.

According to another aspect of the invention, the storage system retrieves, by the second phase, a plurality of load parameters associated with a third phase. For each of the load parameters associated with the third phase, the storage system determines, by the second phase, whether the load parameter has exceeded a load threshold associated with the third phase. The storage system throttles, by the second phase, performance of a specific job in the data deduplication pipeline by the third phase in response to a determination that at least one of the load parameters associated with the third phase has exceeded the load threshold associated with the third phase.

FIG. 1is a block diagram illustrating a storage system according to one embodiment of the invention. Referring toFIG. 1, system100includes, but is not limited to, one or more client systems101-102communicatively coupled to storage system104over network103. Clients101-102may be any type of clients such as a host or server, a personal computer (e.g., desktops, laptops, and tablets), a “thin” client, a personal digital assistant (PDA), a Web enabled appliance, or a mobile phone (e.g., Smartphone), etc. Alternatively, any of clients101-102may be a primary storage system (e.g., local data center) that provides storage to other local clients, which may periodically back up the content stored therein to a backup storage system (e.g., a disaster recovery site or system), such as storage system104. Network103may be any type of networks such as a local area network (LAN), a wide area network (WAN) such as the Internet, a fiber network, a storage network, or a combination thereof, wired or wireless. Clients101-102may be in physical proximity or may be physically remote from one another. Storage system104may be located in proximity to one, both, or neither of clients101-102.

Storage system104may include or represent any type of servers or a cluster of one or more servers (e.g., cloud servers). For example, storage system104may be a storage server used for various different purposes, such as to provide multiple users or client systems with access to shared data and/or to back up (or restore) data (e.g., mission critical data). Storage system104may provide storage services to clients or users via a variety of access interfaces and/or protocols such as file-based access protocols and block-based access protocols. The file-based access protocols may include the network file system (NFS) protocol, common Internet file system (CIFS) protocol, and direct access file system protocol, etc. The block-based access protocols may include the small computer system interface (SCSI) protocols, Internet SCSI or iSCSI, and Fibre channel (FC) protocol, etc. Storage system104may further provide storage services via an object-based protocol and Hadoop distributed file system (HDFS) protocol.

In one embodiment, storage system104includes, but is not limited to, storage service engine106(also referred to as service logic, service module, or service unit, which may be implemented in software, hardware, or a combination thereof), optional deduplication logic107, and one or more storage units or devices108-109communicatively coupled to each other. Storage service engine106may represent any storage service related components configured or adapted to provide storage services (e.g., storage as a service) to a variety of clients using any of the access protocols set forth above. For example, storage service engine106may include directory manager114, content store115, segment store117, optional backup logic121, and optional restore logic122. Backup logic121is configured to receive and back up data from a client (e.g., clients101-102) and to store the backup data in any one or more of storage units108-109. Restore logic122is configured to retrieve and restore backup data from any one or more of storage units108-109back to a client (e.g., clients101-102). Directory manager114is configured to manage files stored in a file system of the storage system. Content store115may be configured to receive file segments requests from directory manager114and to retrieve the file segments from storage units108-109(via segment store117). Segment store117may be configured to store and retrieve deduplicated segments to and from storage units108-109. In another embodiment, segment store117includes deduplication storage engine107(not shown) and deduplicates file segments prior to storing the segments in storage units108-109.

Storage units108-109may be implemented locally (e.g., single node operating environment) or remotely (e.g., multi-node operating environment) via interconnect120, which may be a bus and/or a network (e.g., a storage network or a network similar to network103). Storage units108-109may include a single storage device such as a hard disk, a tape drive, a semiconductor memory, multiple storage devices such as a redundant array system (e.g., a redundant array of independent disks (RAID)), a system for storage such as a library system or network attached storage system, or any other appropriate storage device or system. Some of storage units108-109may be located locally or remotely accessible over a network.

In response to a data file to be stored in storage units108-109, according to one embodiment, deduplication storage engine or deduplication logic107is configured to segment the data file into multiple segments (also referred to as chunks) according to a variety of segmentation policies or rules. Deduplication storage engine107may be implemented as part of content store115and/or segment store117. Deduplication logic107may choose not to store a segment in a storage unit if the segment has been previously stored in the storage unit. In the event that deduplication logic107chooses not to store the segment in the storage unit, it stores metadata enabling the reconstruction of the file using the previously stored segment. As a result, segments of data files are stored in a deduplicated manner, either within each of storage units108-109or across at least some of storage units108-109. The metadata, such as metadata110-111, may be stored in at least some of storage units108-109, such that files can be accessed independent of another storage unit. Metadata of each storage unit includes enough information to provide access to the files it contains.

FIG. 2is a block diagram of an example data deduplication architecture according to one embodiment of the invention. In some embodiments, data deduplication architecture200may be implemented within the storage system104ofFIG. 1, e.g., storage service engine106and/or the deduplication storage engine107ofFIG. 1. As shown inFIG. 2, data deduplication pipeline220may include multiple modules or phases that are configured to perform a specific IO workload or job, such as protocol module221, chunking module222, fingerprint module223, fingerprint verification module224, and compressor/decompressor module225.

Protocol module221may receive a request from a client (e.g., clients101-102) to perform input/output (TO) operations of a data segment associated with a data stream or file object, such as data streams211-213. For example, the protocol module221may parse or decode a request received from a particular client to identify the type of IO operation to be performed on a data stream or file object (e.g., read/write operation). In one embodiment, the protocol module221may get the inode representing a file object in order to obtain a content handle (CH) stored in the inode. In one embodiment, the protocol module221may obtain attributes from the inode to determine the subsequent operations that need to be performed on the file object (e.g., segmentation, fingerprinting, compression/decompression, etc.).

Chunking module222is configured to segment the data stream or file object into multiple segments (also referred to as chunks) according to a variety of segmentation policies or rules. In some embodiments, the chunks may be compressed or decompressed. In one embodiment, content store115may retrieve compressed data segments via segment store117from an identified container of a storage unit, decompresses, and returns the retrieved data segments to the client. In this case, the chunking module222may divide decompressed data segment retrieved by content store115into segments for storage. In one embodiment, when a client backs up data, data segments may be an incremental backup representing a difference between a first snapshot and a second snapshot of backups taken at different points in time. Snapshot is an image of an instance in time of a backup system. In this scenario, chunking module222may divide the difference or delta segments into segments for storage.

Fingerprint module223is configured to calculate and generate fingerprints for data segments. For example, fingerprint module223may invoke a fingerprinting algorithm to generate a set of fingerprints for data segments of a data stream or file object such that the fingerprints are mapped to the data stream or file object. That is, the fingerprints may be utilized to identify or locate the data stream or file object. In some embodiments, the fingerprinting algorithm may be a Rabin's algorithm or a hash function (e.g., cryptographic hash function).

Fingerprint verification module224is configured to search the fingerprints in order to detect duplicate data segments. For instance, if a data segment is a duplicate then such data segment will not be fingerprinted or stored to a storage unit (e.g., storage units108-109). However, if the data segment is not a duplicate then such data segment may be fingerprinted (e.g., via fingerprint module223) and stored to the storage unit.

Compressor/decompressor module225may compress the data segments prior to storing the data segments into a storage unit. Compressor/decompressor module225may also decompress data segments retrieved from a container of a storage unit prior to returning the retrieved data segments to the client.

Accordingly, referring toFIG. 2, load information207may be maintained via an information tracking module205, which may be implemented within storage service engine106and/or deduplication storage engine107, for each of the protocol module221, chunking module222, fingerprint module223, fingerprint verification module224, and compressor/decompressor module225. Load information207may include parameters such as queue depth and latency. Queue depth refers to a number of IO requests that is queued at a given time. Latency refers to a time for performing an IO workload or job by a particular module or phase within a data deduplication pipeline. In some embodiments, the information tracking module205may further maintain load thresholds209that may include queue depth thresholds (at module and system levels) and latency thresholds (at module and system levels) for each of the protocol module221, chunking module222, fingerprint module223, fingerprint verification module224, and compressor/decompressor module225. In some embodiments, load thresholds209may be dynamically updated by information tracking module205depending on several factors. For example, at the module level, queue depth threshold (i.e., maximum number of IO requests) may be increased and latency threshold (i.e., maximum time to perform a particular IO workload) may be decreased for a data stream that requires sequential IO workload (e.g., a sequential read) as the sequential IO workload imposes less system load. On the other hand, if a data stream requires a random IO workload (e.g., random read at different memory locations of a storage unit) then the queue depth threshold may be decreased and latency threshold may be increased as the random IO workload imposes a heavier system load. Furthermore, at the system level, queue depth threshold and latency threshold may be dynamically updated based on several resource instances, for example central processing unit (CPU) utilization, memory (e.g., random access memory and virtual memory usage), hard disk and solid state drives (e.g., free space), cache space (e.g., CPU cache), network throughput, etc. For example, if the storage system is operating with a heavy resource usage, then the queue depth threshold may be decreased and latency threshold may be increased to impose less system load on the storage system. Conversely, if the storage system is operating with a low resource usage, then the queue depth threshold may be increased and latency threshold may be decreased as the system can handle a heavier load.

In operation, when protocol module221receives a request to perform an IO operation of a data segment associated with a data stream (e.g., data streams211-213), the protocol module221may query or retrieve queue depth and latency parameters associated with the protocol module221from load information207. Subsequently, the protocol module221may perform comparisons of the retrieved queue depth and latency parameters to the queue depth thresholds and latency thresholds (at both module and system levels) associated with the protocol module221in load thresholds209. If the queue depth exceeds any of the queue depth thresholds (at module or system level) or if the latency exceeds any of the latency thresholds (at module or system level) associated with the protocol module221, then protocol module221may throttle performance of the workload of the protocol module221. That is, in one embodiment, the protocol module221may cease to enqueue or push an entry into protocol module job queue231, which includes a head232aand a tail232b, where each entry in the protocol module job queue231commands or triggers performance of the workload or job by the protocol module221. In some embodiments, the protocol module221may cease to enqueue the entry for a specific time period, or until none of the queue depth and latency thresholds is exceeded. In another embodiment, to throttle performance of the workload, the protocol module221may delay in sending a response or acknowledgement to the client to indicate that the request to perform the IO operation has been processed. In some embodiments, to throttle performance of the workload, the protocol module221may notify or inform the client about the heavy system load being imposed on the storage system so that the client may effectively throttle (e.g., sending the request to perform IO operations at a lower rate or stop/pause sending of the request) to avoid timing out of the system.

On the other hand, if none of the queue depth and latency thresholds is exceeded, the protocol module221may enqueue or push an entry into protocol module job queue231to perform its IO workload. In some embodiments, the protocol module221may enqueue the entry even if some or a subset of the queue depth and latency thresholds are exceeded.

Subsequently, the protocol module221may query a subsequent module, in this case the chunking module222, to determine whether the chunking module222is overloaded. For example, the protocol module221may retrieve queue depth and latency parameters associated with the chunking module222from load information207. Again, in a similar fashion, the protocol module221may perform comparisons of the retrieved queue depth and latency of the chunking module222to queue depth thresholds and latency thresholds associated with the chunking module222. If the queue depth or latency exceeds any of the queue depth thresholds or latency thresholds respectively, the protocol module221may throttle performance of the workload of the chunking module222. That is, in one embodiment, the protocol module221may cease to enqueue an entry into chunking module job queue233, which includes a head234aand a tail234b, where each entry in the chunking module job queue233triggers performance of the workload or job by the chunking module222. In some embodiments, the protocol module221may cease to enqueue the entry for a specific time period, or until none of the queue depth and latency thresholds is exceeded. In another embodiment, to throttle performance of the workload, the protocol module221may delay in sending a response or acknowledgement to the client to indicate that the IO request has been processed.

On the other hand, if none of the queue depth and latency thresholds is exceeded, the protocol module221may enqueue an entry into chunking module job queue233to perform the IO workload of the chunking module222. In some embodiments, the protocol module221may enqueue the entry even if some or a subset of the queue depth and latency thresholds are exceeded.

Subsequently, the chunking module222may query the fingerprint module223to determine whether the fingerprint module223is overloaded. The chunking module222may retrieve queue depth and latency parameters associated with the fingerprint module223from load information207. In this scenario, the chunking module222may perform comparisons of the retrieved queue depth and latency of the fingerprint module223to queue depth thresholds and latency thresholds associated with the fingerprint module223from load thresholds209. If the queue depth or latency exceeds any of the queue depth thresholds or latency thresholds respectively, the chunking module222may throttle performance of the IO workload of the fingerprint module223in a similar fashion as previously discussed. For example, in one embodiment, the chunking module222may cease to enqueue an entry into fingerprint module job queue235, which includes a head236aand a tail236b, where each entry in the fingerprint module job queue235triggers performance of the IO workload or job by the fingerprint module223. In some embodiments, the chunking module222may cease to enqueue the entry for a specific time period, or until none of the queue depth and latency thresholds is exceeded. In another embodiment, to throttle performance of the workload, the chunking module222may delay in sending a response or acknowledgement to the client to indicate that the IO request has been processed.

If none of the queue depth and latency thresholds is exceeded, the chunking module222may enqueue or push an entry into fingerprint module job queue235to perform the IO workload of the fingerprint module223. In some embodiments, the chunking module222may enqueue the entry even if some or a subset of the queue depth and latency thresholds are exceeded.

Subsequently, the fingerprint module223may query the fingerprint verification module224to determine whether the fingerprint verification module224is overloaded. For example, the fingerprint module223may retrieve queue depth and latency parameters associated with the fingerprint verification module224from load information207. In this scenario, the fingerprint module223may perform comparisons of the retrieved queue depth and latency of the fingerprint verification module224to queue depth thresholds and latency thresholds associated with the fingerprint verification module224from load thresholds209. If the queue depth or latency exceeds any of the queue depth thresholds or latency thresholds respectively, the fingerprint module223may throttle performance of the IO workload of the fingerprint verification module224in a similar manner as previously discussed. For example, in one embodiment, the fingerprint module223may cease to enqueue an entry into fingerprint verification module job queue237, which includes a head238aand a tail238b, where each entry in the fingerprint verification module job queue237triggers performance of the IO workload or job by the fingerprint verification module224. In some embodiments, the fingerprint module223may cease to enqueue the entry for a specific time period, or until none of the queue depth and latency thresholds is exceeded. In another embodiment, to throttle performance of the workload, the fingerprint module223may delay in sending a response or acknowledgement to the client to indicate that the IO request has been processed.

If none of the queue depth and latency thresholds is exceeded, the fingerprint module223may enqueue or push an entry into fingerprint verification module job queue237to perform the IO workload of the fingerprint verification module224. In some embodiments, the fingerprint module223may enqueue the entry even if some or a subset of the queue depth and latency thresholds are exceeded.

Subsequently, the fingerprint verification module224may query the compressor/decompressor module225to determine whether the compressor/decompressor module225is overloaded. For example, the fingerprint verification module224may retrieve queue depth and latency parameters associated with the compressor/decompressor module225from load information207. In this scenario, the fingerprint verification module224may perform comparisons of the retrieved queue depth and latency of the compressor/decompressor module225to queue depth thresholds and latency thresholds associated with the compressor/decompressor module225from load thresholds209. If the queue depth or latency exceeds any of the queue depth thresholds or latency thresholds respectively, the fingerprint verification module224may throttle performance of the IO workload of the compressor/decompressor module225in a similar manner as previously discussed. For example, in one embodiment, the fingerprint verification module224may cease to enqueue an entry into compressor/decompressor module job queue239, which includes a head240aand a tail240b, where each entry in the compressor/decompressor module job queue239triggers performance of the IO workload or job by the compressor/decompressor module225. In some embodiments, the fingerprint verification module224may cease to enqueue the entry for a specific time period, or until none of the queue depth and latency thresholds is exceeded. In another embodiment, to throttle performance of the workload, the fingerprint verification module224may delay in sending a response or acknowledgement to the client to indicate that the IO request has been processed.

If none of the queue depth and latency thresholds is exceeded, the fingerprint verification module224may enqueue or push an entry into compressor/decompressor module job queue239to perform the IO workload of the compressor/decompressor module225. In some embodiments, the fingerprint verification module224may enqueue the entry even if some or a subset of the queue depth and latency thresholds are exceeded. In some embodiments, the queue depth threshold (at module or system level) may be 1000 IO requests.

Resource scheduler250is configured to assign the IO workload of each of the modules (e.g., protocol module221, chunking module222, fingerprint module223, fingerprint verification module224, and compressor/decompressor module225) to resources in order to complete the workload. For example, the resource scheduler250may dequeue or pop the head of each job queue (e.g., protocol module job queue231, chunking module job queue233, fingerprint module job queue235, fingerprint verification module job queue237, compressor/decompressor job queue239) to obtain the entry that triggers performance of a particular IO workload by a respective module. To carry out the workload, resource scheduler250assigns the IO workload performed by the respective module to system resources (e.g., CPU, memory, hard disk drive, solid state drive, etc.). In assigning the workload to resources, resource scheduler250may aim at one of several goals, for example, maximizing throughput and minimizing latency.

In some embodiments, to perform the mechanism as previously discussed with respect to each of the modules, each module may be tagged with a module name (e.g., “protocol”, “chunking”, “fingerprint”, “fingerprint verification”, “compressor/decompressor”) and a workload identification (e.g., a data stream identification). In addition, in various embodiments, performing the mechanism, as discussed above, may improve and provide effective resource utilization of the storage system, and avoid timing out of the system. It should be noted that while the data deduplication pipeline220includes five modules in the example architecture shown inFIG. 2, in various embodiments, the previously described mechanism may be performed for any number of modules in a data deduplication pipeline.

FIG. 3is a table of load information according to one embodiment of the invention. In some embodiments, table300may be implemented within load information207ofFIG. 2. The table300shown includes a protocol module column301, chunking module column303, fingerprint module column305, fingerprint verification module column307, and compressor/decompressor module column309. Each of data stream identification (ID)321-325is a reference to obtain queue depth and latency parameters for each of the module columns301-309. That is, the queue depth and latency values in a single row of the module columns301-309are mapped to a corresponding data stream ID in that row. As an example, if a module is tagged with data stream ID321and module name of “protocol module”, then the queue depth and latency would be retrieved at the row represented by data stream ID321and the column represented by protocol module column301. It should be appreciated that the order of stream ID rows321-325and module columns301-309presented inFIG. 3may be in any order and is not limited to the order shown inFIG. 3.

FIG. 4is a table of load thresholds according to one embodiment of the invention. In some embodiments, table400may be implemented within load thresholds209ofFIG. 2.

The table400shown includes a queue depth threshold (module level) column401, a latency threshold (module level) column403, a queue depth threshold (system level) column405, and a latency threshold (system level) column407. Each of module rows421-429is a reference to obtain threshold values from the columns401-407. That is, the threshold values in a single row of columns401-407are mapped to a corresponding module in that row. As an example, if chunking module row423is selected as a reference, then the threshold values at that row would be utilized for comparison (as previously discussed). It should be appreciated that the order of the module rows421-429and threshold columns401-407presented inFIG. 4may be in any order and is not limited to the order shown inFIG. 4.

FIG. 5is a flow diagram illustrating a method to perform data deduplication in a storage system according to one embodiment of the invention. Process500may be performed by processing logic that includes hardware (e.g. circuitry, dedicated logic, etc.), software (e.g., embodied on a non-transitory computer readable medium), or a combination thereof. For example, process500may be performed by storage system104ofFIG. 1(e.g., storage service engine106and/or deduplication storage engine107).

Referring toFIG. 5, at block501, processing logic receives, by a first phase (e.g., protocol phase or module), a request from a client for reading or writing a data segment associated with a data stream stored in or to the storage system. At block502, in response to the request, the processing logic retrieves, by the first phase, a plurality of load parameters (e.g., queue depth, latency) associated with a second phase (e.g., chunking phase). At block503, for each of the load parameters associated with the second phase, the processing logic determines, by the first phase, whether the load parameter has exceeded a load threshold associated with the second phase (e.g., queue depth thresholds (at phase and system levels), latency thresholds (at phase and system levels)). At block504, the processing logic throttles, by the first phase, performance of a specific job in a data deduplication pipeline by the second phase in response to a determination that at least one of the load parameters associated with the second job phase has exceeded the load threshold associated with the second phase.

Processing module/unit/logic1528, components and other features described herein can be implemented as discrete hardware components or integrated in the functionality of hardware components such as ASICS, FPGAs, DSPs or similar devices. In addition, processing module/unit/logic1528can be implemented as firmware or functional circuitry within hardware devices. Further, processing module/unit/logic1528can be implemented in any combination hardware devices and software components.