Method and system for detecting compression ratio anomalies in data streams in a deduplication storage system

This disclosure provides system, methods, and media for identifying inadvertent compression or encryption in data streams from a client that land on a deduplication storage system. When one or more such abnormalities are detected, an alert message is generated to alert the administrator of the deduplication storage system so that corrective actions can be taken to prevent undesired consequences. According to an exemplary method, machine learning techniques are used to plot and smoothen global compression ratios and local compression ratios of historical backups from a client over a period of time. Then, a second derivative of each data point on the smoothened curves is taken and compared with a predetermined threshold to detect whether that the slope of the data point exceeds a threshold. A data point whose slope exceeds the threshold can be determined to be a data point corresponding to a backup that includes compression and/encryption.

FIELD OF THE INVENTION

Embodiments of the present invention relate generally to data storage systems. More particularly, embodiments of the invention relate to detecting abnormal patterns in compression in an incoming data stream to in a storage system.

BACKGROUND

A data storage system, such as the PowerProtect Data Manager (PPDM) from Dell EMC™, receives data from multiple clients, and stores the data in a deduplication storage system.

In such a storage system, data streams are to go through a deduplication process, which is a method of data compression to enable repeated data segments to point to a same segment on a disk in the deduplication storage system. However, if the data streams are encrypted or compressed, the deduplication would yield near zero data compression.

Typically, a data storage system may involve one or more client administrators and a deduplication system administrator, and the client administrators may not always be able to communicate encryption or compression changes in the data streams to the deduplication storage system administrator. For example, if the encryption or compression in the data steams is inadvertent or caused by ransomware, the client administers may not be aware of the encryption or compression in the data streams, and thus cannot notify the deduplication storage system administrator of the changes in the data streams.

As a result, the deduplication storage system may not detect the data encryption or compression in the data streams until days or weeks later through decreased compression ratios in the deduplication storage system, and thus would not be able to take timely actions to prevent associated undesired consequences, which include altered service level parameters (e.g., service level agreement, capacity utilization, and time to transmit the data to a remote site).

Thus, it would be desirable for the deduplication storage system to detect the compression and/or encryption in data streams so that appropriate corrective actions can be taken in time when the compression or encryption is inadvertent.

DETAILED DESCRIPTION

According to various embodiments, machine learning algorithms are used to monitor data streams as they land on a deduplication storage system to track anomalies in global compression ratios (i.e. deduplication ratios) and local compression ratios for each data stream of every client that has data to be backed up on the duplication storage system.

When one or more such abnormalities are detected, an alert message is generated to alert the administrator of the deduplication storage system so that corrective actions can be taken to prevent undesired consequences.

According to an exemplary method, machine learning techniques are used to plot and smoothen global compression ratios and local compression ratios over a period of time in the past from a particular client. Then, a second derivative of each data point on the smoothened curves is taken and compared with a predetermined threshold to detect whether that data point is an abnormality.

In one embodiment, an exemplary method includes retrieving global compression ratios of historical backups of a source system of a client and local compression ratios of the source system over a predetermined period of time; plotting a first curve using the global compression ratios and a second curve using the local compression ratios; and smoothening the first curve and the second curve using a predetermined smoothening algorithm to generate a first smoothened curve and a second smoothened curve. The method further includes finding a second derivative of each data point on each of the first smoothened curve and the second smoothened curve; and identifying one or more data points whose slopes exceed a predetermined threshold on the first smoothened curve and the second smoothened curve.

In one embodiment, the method further includes generating an alert message for an administrator of the client and/or an administrator of the deduplication storage system. The message for the administrator of the deduplication storage system can be displayed on a graphical user interface on the deduplication storage system. The alert messages can inform the client administrator or the deduplication storage system that a compression function or an encryption function has been enabled on the client.

In on embodiment, a variety of smoothening algorithms can be used to smoothen the compression ratio curves. The smoothening algorithms can include Savitzky-Golay filter, kernel density estimation, and quadratic planning (QP) spline optimization.

In one embodiment, the threshold value used to detect whether a data point on the smoothened curves is an abnormality is configurable. In one embodiment, the compression ratios used to plot the compression ratio curves are stored as part of the metadata of backups on the deduplication storage system, and can cover a particular period of time (e.g., 10 days).

The embodiments described above are not exhaustive of all aspects of the present invention. It is contemplated that the invention includes all embodiments that can be practiced from all suitable combinations of the various embodiments summarized above, and also those disclosed below.

Deduplication Storage System

FIG.1is a block diagram illustrating a deduplication storage system100according to one embodiment of the invention. The deduplication storage system100includes, but is not limited to, one or more client systems, such as client101and/or client102, which are communicatively coupled to the storage system104over the network103. The clients101,102may be any type of clients such as a server, a personal computer (e.g., desktops, laptops, and tablets), a “thin” client, a personal digital assistant (PDA), a Web enabled appliance, a gaming device, a media player, or a mobile phone (e.g., Smartphone), etc. Alternatively, any of the clients101,102may be a primary storage system that provides storage to other local clients, which may periodically back up the content stored therein to a backup storage system, such as the storage system104. The 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. The clients101,102may be in physical proximity or may be physically remote from one another. The storage system104may be located in proximity to one, both, or neither of the clients101,102.

The storage system104may be used as any type of server or cluster of servers. For example, the storage system104may be a storage server used for any of various different purposes, such as to provide multiple users with access to shared data and/or to back up data (e.g., mission critical data). In one embodiment, storage system104includes, but is not limited to, a file manager117, a cache management layer106, a deduplication storage engine107, storage units108,109, and a cache memory device114communicatively coupled to each other. The storage units108,109and the cache memory device114may 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). The storage units108,109may include a single storage device such as a hard disk, a tape drive, a semiconductor memory, a plurality of 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. The cache memory device114can include one or more of volatile, non-volatile, or a combination of volatile and non-volatile devices.

The file manager117may be executed by a processor to provide an interface to access files stored in the storage units108,109and the cache memory device114. The cache management layer106contains a cache manager115, file index116, and optionally a fingerprint (FP) index118. Cache management layer106and file manager117reside in memory of a processor in one embodiment.

In one embodiment, the file index116is used to access data cached in cache memory device114. The fingerprint index118is used to de-duplicate data stored in cache memory device114and the storage units108,109. In one embodiment the fingerprint index118is a partial index that covers a portion of data stored in the cache memory device and/or storage units108,109, with the remainder of the fingerprint data stored in the metadata110,111of an associated one of the storage units108,109. In one embodiment, the metadata110,111includes a file name, a storage unit where the segments associated with the file name are stored, reconstruction information for the file using the segments, and any other appropriate metadata information related to the files and underlying data objects on each storage unit.

In one embodiment, a copy of the metadata is stored on a storage unit for files stored on a storage unit so that files that are stored on the storage unit can be accessed using only the information stored on the storage unit. In one embodiment, a main set of metadata information can be reconstructed by using information of all storage units associated with the storage system in the event that the main metadata is lost, corrupted, damaged, etc. Metadata for a storage unit can be reconstructed using metadata information stored on a main storage unit or other storage unit or units (e.g., replica storage unit). Metadata information further includes index information (e.g., location information for segments in storage units). In one embodiment, metadata includes prime segment information that can be used to provide a consistent point of a file system and/or reconstruct a file system in the event of file system failure.

When data is to be stored in the storage units108,109, the deduplication storage engine107is configured to segment the file data into multiple chunks (also referred to as segments) according to a variety of segmentation policies or rules. The deduplication storage engine107may choose not to store a chunk in a storage unit if the chunk has been previously stored in the storage unit. In the event that the deduplication storage engine107does not to store the chunk in the storage unit, the deduplication storage engine107can store metadata enabling the reconstruction of the file using the previously stored chunk. As a result, chunks of file data are stored in a deduplicated manner as data objects112,113within one or more of the storage units108,109. The metadata110,111may be stored in at least some of storage units108,109, such that files and associated data objects112,113in a storage unit can be accessed independently of another storage unit. In general, the metadata of each storage unit includes sufficient information to provide access to the files that are backed by the data objects112,113on the storage unit.

FIG.2illustrates a deduplication file system200, according to an embodiment. The deduplication file system includes a fingerprint index202, such as the fingerprint index218ofFIG.2, a file segment tree203, and one or more storage containers204including metadata206and data208. One or more of the storage containers204can be stored on each of the storage units108,109ofFIG.1. The metadata206can contain at least a portion of the metadata110,111ofFIG.1. The data208can contain at least a portion of the data objects112,113ofFIG.1.

In one embodiment the fingerprint index202is a portion of the metadata206on the storage containers204and at least a portion of the fingerprint index202is stored or cached in memory. The fingerprint index202stores information to determine which of the storage containers204on which data referenced by a fingerprint is stored. In one embodiment the fingerprint index202stores fingerprint data in the form of fingerprint and container identifier pairs (e.g., <FP,CID>) which associate a fingerprint with a container identifier storing the storage segment associated with the fingerprint.

The file segment tree203is a portion of the metadata206that enables the deduplication file system200to reconstruct a file from the underlying data208. The file segment tree203may be referred to as an LP segment tree. In one embodiment the file segment tree203is a Merkle tree that may have multiple levels depending on the size of the file. The level zero (L0) segments of the tree are segments with user data. Each L0 segment is identified by a fingerprint, which is one of the fingerprints stored in the fingerprint index202. The fingerprints are content based fingerprints, such as a hash of the L0 data segment. A level one (L1) segment references one or more L0 segments via content based fingerprints. One or more L1 segments can then be referenced by a level 2 (L2) segment, up to the root node of the tree. Accordingly, the L0 segments contain the data208within the storage containers204. In some embodiments segments in layers L1 and up, referred to as LP segments are also stored in the data208and each LP segment also has an associated stored in the metadata206and in the fingerprint index202. Segments can be shared among multiple files and in one embodiment may be compressed and packed within a compression region. Multiple compression regions may be packed into a storage container.

Compression or Encryption Abnormality Detection

As described above, a file data to be stored in a deduplication storage system needs to go through a deduplication process for identifying redundant data segments of the file data such that only unique data segments are compressed and stored in the deduplication storage system.

In the deduplication process, the file data, which is transmitted from a client to the storage system via a data stream, can be segmented using two different techniques: fixed sized segmentation (FSS) and variable sized segmentation (VSS). Under the FSS, the file data can be segmented at fixed sized boundaries (e.g., 8 KB). This technique is typically used for applications that do not have data shifts, such as a primary storage logical unit number (LUN), or a virtual machine (VM) file. Under the VSS, the file data can be segmented at an arbitrary boundary (within bounds).

A propriety algorithm can be used to create data segments between 4 kB and 12 kB, with the average size being 8 kB. Once the file data has been segmented, it is fingerprinted. A storage system (e.g., the storage system104) can use a mutation of the SHA1 algorithm to create the fingerprint. This fingerprint can be looked up in a fingerprint index (e.g., the fingerprint index118). If the segment does not exist on the storage system, the segment must be written to a disk. Before writing the segment to the disk, the segment of the data can be compressed using a data compression algorithm (like LZ, or GZ). To achieve decent compression ratios, the compression can be performed multiple segments, which are written as a compression region (within a container).

The deduplication process is a process of identifying and compressing unique data segments in data streams. As used herein, unique data segments are those that cannot be located on the storage system using the fingerprint lookup operation mentioned above. Once the unique data segments are identified, they can be compressed and stored to the storage system. Thus, the deduplication is also referred to global compression, and the operation of compressing unique data segments is also called local compression. Since the global compression comprises identifying unique data segments and compressing the unique data segments, the local compression is part of the global compression.

However, if the file data is pre-compressed, re-compressing it yields no benefit. In some cases, the recompression would actually increase the size of the buffer. Similarly, if the file data is encrypted, the compression also would not yield benefit because the entropy of the data may, in some cases, cause an increase in the size of the compressed buffer. Encryption can cause a huge change in the entropy of the data due to the design of encryption algorithms.

With the VSS segmenting technique, the encrypted data stream would look like brand new data, and therefore, there would be no deduplication associated with the data stream. With the FSS technique, there can be two cases. In the first case where the encryption is performed at a segment boundary, unique data segments (changed data segments) would appear as completely new data, and unchanged data segments would land on the file system as encrypted and would be identified as redundant. Thus, in the first case, although the data stream is encrypted, deduplication may occur due to the presence of the unchanged data segments. In the second chase where the encryption is performed for the entire data stream, the entropy associated with encryption would kick in, and no segment in the entire data stream would get any duplication or compression benefits.

Thus, when an incoming data stream to a storage system is encrypted or compressed, the compressions (global and local) performed on the data stream in the storage system would yield zero or little benefits. Such features in encrypted data or compressed data would allow abnormalities in compression and/encryption to be detected based historical data streams.

FIG.3is a block diagram illustrating a deduplication storage system300for detecting abnormalities in data streams according to one embodiment of the invention.

More specifically,FIG.3illustrates a deduplication storage system for detecting abnormalities in data streams using machine learning techniques based on metadata of backups stored in the storage system.

As shown inFIG.3, a compression/encryption abnormality detector306can be provided in the storage system104to detect abnormalities in compression ratios in data streams that have been stored in the storage system104for various clients. The embodiment illustrated inFIG.3focuses on client101, which can be a database system301. However, a person skilled in the art would appreciate that the features illustrated inFIG.3would be applicable to any type of clients of the storage system104.

In one embodiment, the storage system104can receive backups in data streams305from client101, and store the backups via the global compression process. The data streams305represent different types of backup data (e.g., full backup data or incremental backup data) from the database system301. Metadata of each backup data from the database system301can be stored in the metadata110.

As shown in theFIG.3, the metadata110can include a local compression ratio and a global compression ratio for each backup from the database system301. The global compression ratio is a ratio between an uncompressed size of a data stream and a compressed size of the data stream, and the local compression ratio is a ratio between an uncompressed size of unique data segments in the data stream and a compressed size of the unique data segments in the data stream.

In one embodiment, backups from client101are tagged, which enables the storage system104to filter and list files (backups) generated by the client. Other methods used to track compression history of a backup lineage can include:

Method 1: Given a backup file, client101tracks the lineage for that backup file in its catalog. Since this method requires the lineage data to determine the history of the compression ratios, the storage system104could request the information from the client101.

Method 2: For Virtual Synthetic files, the lineage information can be embedded in the metadata110or another storage location. The storage system104can walk up the lineage tree using the VS metadata, and determine the historical compression ratios.

Method 3: Using the metadata110, the backup files can be tagged with the client ID. The latest n files with the same client id can be obtained in a filesystem namespace tree using a depth first search in the Btree and sorting the search result by the modified timestamp (mtime) information.

In one embodiment, the local compression ratio can be used to deduce information about a given data stream. For example, if the local compression on the data stream is near zero or negative, then then the data stream is either compressible, pre-compressed, or encrypted. If the global compression ratio of a given data stream is near zero, then the data stream may be a first generation of data that lands on the storage system104, or encrypted (unless the data stream is segmented using the FSS). However, the deduced information itself may not be not enough for the compression/encryption detector306to detect abnormalities in compression patterns.

Thus, the compression/encryption detector306uses machine learning techniques to identify a sudden change in compression ratios of backup data from the client101over particular period of time in the past. The particular period of time can be configured by the system administrator of the deduplication storage system300. For example, the period of time can be 7 days or 10 days or 30 days. The historical data is used to create a historical context for determining whether a particular slope change is considered abnormal.

For example, Table 1 lists the sizes of three backups from client101, and their local compression ratios and global compression ratios.

As shown in Table 1, the local compression ratios for the three backups are respectively 2, 2, and 1.92, which are very close to each other. So are the global compression ratios for the three backups, which are respectively 6.7, 6.65, and 6.8.

If the compression function is suddenly turned on this client, either inadvertently by the database administer, or intentionally by a ransomware, the local compression ratio and the global compression ratio of a new data stream would be as follows as shown in Table 2:

As shown above, both the local compression ratio and the global compression ratio of the backup n—which is received from client101after the compression function is turned on client101—is drastically smaller than the corresponding compression ratios shown in Table 1.

Referring back toFIG.1, the compression/encryption abnormality detector306can plot a local compression ratio curve using historical local compression ratios in a predetermined period of time in the past, and plot a global compression ratio curve using global compression ratios in the same predetermined period of time.

The local compression curve can be smoothened using a local compression smoother309, and the global compression ratio curve can be smoothened using a global compression ratio smoother311. Each of the local compression ratio smoother309and the global compression ratio smoother311can implement one of many smoothing algorithms, such as Savitzky-Golay filter.

An abnormality evaluator315can take a second derivative of each data point on the smoothened local compression curve to generate a second derivative curve for the local compression ratios, and take a second derivative of each data point on the smoothened global compression ratio curve to generate a second derivative curve for the global compression ratios. The abnormality evaluator315then identifies a slope (i.e. rate of change) for each data point on the second derivative curve for the local compression ratios and the second derivative curve for the global compression ratios. The abnormality evaluator315can identify any data point whose slope exceeds a predetermined threshold by comparing the slope of that data point with the threshold. In one embodiment, the threshold can be determined based on different datasets, or based on feedbacks from system administrators.

A data point with such a slope change can be identified as a data point with abnormality. In one embodiment, the change can be a change in amplitude of the curve in either direction. The threshold used to identify abnormalities can be configured by the administrator of the deduplication storage system300. Such an abnormality can be an indication that the corresponding backup is encrypted or compressed

In one embodiment, once a particular data point is identified as having an abnormality, the compression/encryption abnormality detector306can match the data point to a particular backup using the metadata110, and generates an alert message for display on a graphical user interface317to notify the administrator of the deduplication storage system300of the abnormality. Meanwhile, the compression/encryption abnormality detector306can send an alert message to the administrator of client101, such that both the administrator of client101and the administrator of the deduplication storage system300can take appropriate corrective actions if necessary.

FIGS.4A-4Billustrate an example of detecting a compression and/or encryption in data streams of a client according to one embodiment of the invention.FIGS.4A-4Buses local compression ratios to illustrate how an abnormality in compression ratios is detected. The machine learning techniques used inFIGS.4A-4Bcan be similarly applied to global compression ratios to detect an abnormality in the global compression ratios.

As shown inFIG.4A, on a plotted curve402is generated by connecting all the data points during the past 30 days, each data point representing a local compression ratio of a backup, and the local compression ratios during the past 30 hovering around 2.0. The plotted curve402is smoothened into a smoothened curve403. A curve404is then generated from the smoothened curve403by taking a second derivative of each data point on the smoothened curve403. A line405marks a data point where an abnormality in the corresponding local compression ratio has a change that exceeds a predetermined threshold.

FIG.4Bshows a different plotted curve408using local compression ratios over the past 30 days, a different smoothened curve409, and a different second derivative curve410of the smoothened curve409.

However, inFIG.4B, no data point is identified as having an abnormality in its local compression ratio, because the local compression ratios during the past 30 days were always close to 1, and no data point has a slope change that exceeds a predetermined threshold.

FIGS.4A-4Bis an illustrative example of detecting abnormal local compressions in data streams. It is for the purpose of demonstrating the process of detecting such an abnormality. In actual implementations, the compression ratio abnormality detector runs periodically (e.g., every 2 hours), and thus would detect compression ratios abnormalities in a data stream as soon as the data stream is deduplicated and stored to the storage system.

FIG.5illustrates a process500of detecting abnormalities in data streams according to one embodiment of the invention. Process500may be performed by a processing logic which may include software, hardware, or a combination thereof. For example, process500may be performed by the compression/encryption abnormality detector306described inFIG.3.

As shown inFIG.5, in operation501, the processing logic obtains a file lineage to get compression ratios of historical backups for a given source system for each client. The compression ratios are stored in a deduplication storage system, and can include both global compression ratios and local compression ratios of historical backups of the source system of the client. In one example, the source system can be a database or a web application of the client. The compression ratios can be compression rations of backups of the source system for a particular period of time (e.g., 10 days) in the past.

In operation503, the processing logic smoothens the compression ratios using a smoothening algorithm, such as Savitzky-Golay filter. In this operation, the processing logic generates a plotted curve for the global compression ratios and a plotted curve for the local compression ratios, and then smoothens each plotted curve.

In operation505, the processing logic finds a second derivative of each data point on the smoothed plotted curve for the global compression ratios, and the smoothened plotted curve for the local compression ratios. The second derivative of each data point is the slope of the data point.

In operation507, the processing logic compares the slope of each data point with a predetermined threshold.

In operation508, the processing logic determines whether any of the data points has a larger slope than the predetermined threshold. If no such data point is found, then the process logic will do nothing as shown in operation511. However, if at least one data point whose slope is larger than the threshold is identified, the processing logic generates an alert message for the administrator of the client and an alert message for the administrator of the deduplication storage system as shown in operation513.

FIG.6is a flow diagram illustrating a process600of detecting abnormalities in data streams according to one embodiment of the invention. Process600may 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, process600may be performed by the processing modules1528ofFIG.7or the compression/encryption abnormality detector306described inFIG.3.

Referring toFIG.6, in operation610, the processing logic retrieves global compression ratios of historical backups of a source system of a client and local compression ratios of the source system of the client over a predetermined period of time. In operation620, the processing logic plots a first curve using the global compression ratios and a second curve using the local compression ratios. In operation630, the processing logic smoothens each of the first curve and the second curve using a predetermined smoothening algorithm to generate a first smoothened curve and a second smoothened curve. In operation640, the processing logic finds a second derivative of each data point on each of the first smoothened curve and the second smoothened curve. In operation650, the processing logic identifies one or more data points whose slopes exceed a predetermined threshold on at least one smoothened curve from a group consisting of the first smoothened curve and the second smoothened curve.

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.