Patent ID: 12210486

DETAILED DESCRIPTION

Specific embodiments will now be described with reference to the accompanying figures.

In the below description, numerous details are set forth as examples of embodiments described herein. It will be understood by those skilled in the art (who also have the benefit of this Detailed Description) that one or more embodiments of embodiments described herein may be practiced without these specific details, and that numerous variations or modifications may be possible without departing from the scope of the embodiments described herein. Certain details known to those of ordinary skill in the art may be omitted to avoid obscuring the description.

In the below description of the figures, any component described with regard to a figure, in various embodiments described herein, may be equivalent to one or more like-named components described with regard to any other figure. For brevity, descriptions of these components may not be repeated with regard to each figure. Thus, each and every embodiment of the components of each figure is incorporated by reference and assumed to be optionally present within every other figure having one or more like-named components. Additionally, in accordance with various embodiments described herein, any description of the components of a figure is to be interpreted as an optional embodiment, which may be implemented in addition to, in conjunction with, or in place of the embodiments described with regard to a corresponding like-named component in any other figure.

Throughout the application, ordinal numbers (e.g., first, second, third, etc.) may be used as an adjective for an element (i.e., any noun in the application). The use of ordinal numbers is not to imply or create any particular ordering of the elements, nor to limit any element to being only a single element unless expressly disclosed, such as by the use of the terms “before”, “after”, “single”, and other such terminology. Rather, the use of ordinal numbers is to distinguish between the elements. By way of an example, a first element is distinct from a second element, and the first element may encompass more than one element and succeed (or precede) the second element in an ordering of elements.

Throughout this application, elements of figures may be labeled as A to N. As used herein, the aforementioned labeling means that the element may include any number of items and does not require that the element include the same number of elements as any other item labeled as A to N. For example, a data structure may include a first element labeled as A and a second element labeled as N. This labeling convention means that the data structure may include any number of the elements. A second data structure, also labeled as A to N, may also include any number of elements. The number of elements of the first data structure and the number of elements of the second data structure may be the same or different.

As used herein, the phrase operatively connected, or operative connection, means that there exists between elements/components/devices a direct or indirect connection that allows the elements to interact with one another in some way. For example, the phrase ‘operatively connected’ may refer to any direct (e.g., wired directly between two devices or components) or indirect (e.g., wired and/or wireless connections between any number of devices or components connecting the operatively connected devices) connection. Thus, any path through which information may travel may be considered an operative connection.

In general, embodiments described herein relate to performing data assignment to sim-groups using fingerprint distribution mapping. For context, in a scaled-out data deduplication architecture, there are multiple nodes implementing multiple deduplication domains (also referred to herein as similarity groups, or sim-groups), respectively. Any data, in order to undergo data deduplication processing at one of these multiple nodes, may be directed or assigned thereto based on a number of factors. The key objective, nevertheless, lies with the distribution of said data across the multiple sim-groups to achieve a balance between optimal global data deduplication efficiency and node workloads there-throughout.

Embodiments described herein propose a sim-group assignment algorithm, which at least reflects the following: (a) a probabilistic technique that employs fingerprint distribution maps (or bin-maps) to assign data chunks to appropriate sim-groups in order to achieve optimal data deduplication efficiencies; (b) an inline or online machine learning based clustering algorithm, which handles dynamic, streaming data (rather than static datasets) and balances the sought optimization of data deduplication efficiencies with other considerations, such as node workloads; (c) a reinforcement learning technique that seeks to assign data to sim-groups corresponding to nodes exhibiting lesser workloads; (d) a reinforcement learning technique that seeks to assign data to sim-groups corresponding to nodes maintaining spatial locality data access behavior; and (e) a reinforcement learning technique that seeks to assign data to sim-groups based on an epsilon (ε)—greedy action selection algorithm.

FIG.1shows a system in accordance with one or more embodiments described herein. The system (100) may include one or more data sources (102A-102N), a cluster controller (104), and two or more work nodes (106A-106N). Each of these system (100) components is described below.

In one or many embodiment(s) described herein, any data source (102A-102N) may represent a physical (or a virtual) appliance or device wherefrom data sought to undergo data deduplication originates. As such, any data source (102A-102N) may, at least in part, be configured to receive, generate, process, store, and/or transmit data, as well as provide an environment in which any number of computer programs may execute or be maintained thereon. The computer program(s) may, for example, implement one or more services offered locally or over a network. Further, in providing an execution environment for any computer program(s) installed thereon, any data source (102A-102N) may include and allocate various resources (e.g., computer processors, memory, storage, virtualization, network bandwidth, etc.), as needed, to the computer program(s) or any other process(es). One of ordinary skill, however, will appreciate that any data source (102A-102N) may perform other functionalities without departing from the scope of the embodiments described herein. Examples of any data source (102A-102N) may include, but are not limited to, a desktop computer, a laptop computer, a network server, a tablet computer, a smartphone, a virtual machine, a container, a micro-service, or any other computing device (or a virtualization thereof) similar to the computing system illustrated and described with respect toFIG.3, below.

In one or many embodiment(s) described herein, the cluster controller (104) may represent any information technology (IT) infrastructure at least configured to assign data, received from any data source (102A-102N), to an appropriate work node (106A-106N) for data deduplication processing. To that end, the cluster controller (104) may include functionality to perform data assignment to sim-groups using fingerprint distribution mapping—the method for doing so being illustrated and described below with respect toFIGS.2A-2E. One of ordinary skill, however, will appreciate that the cluster controller (104) may perform other functionalities without departing from the scope of the embodiments described herein.

In one or many embodiment(s) described herein, the cluster controller (104) may be implemented through on-premises infrastructure, cloud computing infrastructure, or any hybrid infrastructure thereof. The cluster controller (104), accordingly, may be implemented using one or more network servers (not shown), where each network server may represent a physical or a virtual network server. Additionally, or alternatively, the cluster controller (104) may be implemented using one or more computing devices similar to the computing system illustrated and described with respect toFIG.3, below.

In one or many embodiment(s) described herein, any work node (106A-106N) may represent a physical (or a virtual) appliance or device whereon data assigned thereto undergoes data deduplication. As such, any work node (106A-106N) may, at least in part, be configured to: provide an execution environment wherein one or more computer programs (or processes) may implement any data deduplication process; receive any number of data chunks from the cluster controller (104) to undergo data deduplication; and provide, when requested by or periodically pushed to the cluster controller (104), various state and/or performance metrics (e.g., data deduplication efficiency, computer processor utilization, input-output (IO) operations per second (IOPS), data access latency, etc.) concerning itself. One of ordinary skill, however, will appreciate that any work node (106A-106N) may perform other functionalities without departing from the scope of the embodiments described herein.

For example, in one or many embodiment(s) described herein, any work node (106A-106N) may, at least in part, include functionality to store or maintain any deduplicated data thereon or on any underlying hardware. As such, any work node (106A-106N) may include or have access to physical storage wherein at least the deduplicated data may reside. Said physical storage may encompass non-transitory computer readable media on which at least the deduplicated data may be stored in whole or in part, and temporarily or permanently. Further, said physical storage may, at least in part, be implemented using persistent (i.e., non-volatile) storage. Examples of persistent storage may include, but may not be limited to, optical storage, magnetic storage, NAND Flash Memory, NOR Flash Memory, Magnetic Random Access Memory (M-RAM), Spin Torque Magnetic RAM (ST-MRAM), Phase Change Memory (PCM), or any other storage defined as non-volatile Storage Class Memory (SCM).

In one or many embodiment(s) described herein, any work node (106A-106N) may implement, and thus correspond to, a deduplication (or dedupe) domain. Said dedupe domain (also referred to herein as a similarity group, or sim-group) may refer to an environment or a space where objects (e.g., stream chunks) assigned thereto may, at least in part, share the same object portions (e.g., chunk segments) there-between. Any dedupe domain, furthermore, may employ local data deduplication impacting solely any objects assigned and/or maintained on the work node (106A-106N) corresponding thereto. Moreover, any work node (106A-106N) may form part of a deduplication work cluster (108). The deduplication work cluster (108), in turn, may refer to distributed computing architecture configured to achieving the common goal of data deduplication efficiency optimization.

Examples of any work node (106A-106N) may include, but are not limited to, a desktop computer, a laptop computer, a network server, a tablet computer, a smartphone, a virtual machine, a container, a micro-service, or any other computing device (or a virtualization thereof) similar to the computing system illustrated and described with respect toFIG.3, below.

In one or many embodiment(s) described herein, the above-mentioned system (100) components (or subcomponents thereof) may communicate with one another through a network (not shown) (e.g., a local area network (LAN), a wide area network (WAN) such as the Internet, a mobile network, any other network type, or any combination thereof). The network may be implemented using any combination of wired and/or wireless connections. Further, the network may encompass various interconnected, network-enabled subcomponents (or systems) (e.g., switches, routers, gateways, etc.) that may facilitate communications between the above-mentioned system (100) components (or subcomponents thereof). Moreover, in communicating with one another, the above-mentioned system (100) components (or subcomponents thereof) may employ any combination of wired and/or wireless communication protocols.

WhileFIG.1shows a configuration of components and/or subcomponents, other system (100) configurations may be used without departing from the scope of the embodiments described herein.

FIG.2A-2Eshow a flowchart describing a method for performing data assignment to sim-groups using fingerprint distribution mapping in accordance with one or more embodiments described herein. The various steps outlined below may be performed by the cluster controller (see e.g.,FIG.1). Further, while the various steps in the flowchart are presented and described sequentially, one of ordinary skill will appreciate that some or all steps may be executed in different orders, may be combined or omitted, and some or all steps may be executed in parallel.

Turning toFIG.2A, in Step200, a set of work nodes is discovered. In one or many embodiment(s) described herein, each work node in the set of work nodes may form part of a deduplication work cluster and thus may refer to a physical (or a virtual) appliance or device whereon data assigned thereto undergoes data deduplication. Further, discovery of any work node may employ any existing device discovery techniques or protocols.

In Step202, each work node, in the set of work nodes (discovered in Step200), is monitored. In one or many embodiment(s) described herein, monitoring of any work node may, for example, entail deployment of an agent (i.e., a computer program or process) by the cluster controller onto the work node, where said agent may be configured to, whether on-demand (i.e., by request) and/or periodically push/provide, various state and metrics concerning the work node to the cluster controller. By way of examples, said various state and metrics may include: a data deduplication efficiency (or ratio); computer processor utilization; input-output (IO) operations per second (IOPS); and data access latency. Further, said various state and metrics are not limited to the aforementioned specific examples.

In Step204, a fingerprint bit-mask is obtained. In one or many embodiment(s) described herein, the fingerprint bit-mask may refer to a sequence or an ordered series of binary bits (e.g., each binary bit representing a variable either reflecting a one (1) or a zero (0) value) of any arbitrary length. Said any arbitrary length, or cardinality of the fingerprint bit-mask, may match any arbitrary length or cardinality of a hash digest or value (also referred to herein as a fingerprint) outputted by a hash function (described more below). The fingerprint bit-mask, moreover, may serve (when applied by way of a bit-wise operation) to identify the value of one or more specific bits (amongst a target bit-field (e.g., the aforementioned fingerprint)) each aligned, in position, with one or more set-bits (defined below) amongst the fingerprint bit-mask. An example fingerprint bit-mask is illustrated and described with respect toFIG.4B, below.

In Step206, amongst the fingerprint bit-mask (obtained in Step204), a set-bits cardinality of one or more set-bits expressed therein is obtained. In one or many embodiment(s) described herein, a set-bit of the fingerprint bit-mask may reference any binary bit therein reflecting a one (1) value. A set-bits cardinality, accordingly, may refer to a numerical value indicating a total number of set-bits present within the fingerprint bit-mask. By way of an example, with a fingerprint bit-mask of 11001001, the set-bits cardinality associated therewith is four (4) referencing the four binary bits each reflecting a one (1) value.

In Step208, a set of sim-group bin-maps is initialized. In one or many embodiment(s) described herein, any sim-group bin-map may refer to a data structure (e.g., a vector or an array) that captures an approximate probability distribution of a superset of chunk segment fingerprints (described below—see e.g., Step218) for chunk segments (described below—see e.g., Step216) belonging to any stream chunk(s) (described below—see e.g., Step212) assigned to a corresponding sim-group.

Any sim-group bin-map, accordingly, may be defined or described through: (a) a set of bins (e.g., vector/array elements), where the number of bins forming the set of bins may be derived from the set-bits cardinality (obtained in Step206) or, more specifically, through the mathematical expression 2C, where C equals the set-bits cardinality; (b) a different C-bit value, from a set of possible C-bit values, associated with or mapped to each bin in the set of bins; and a separate bin value, associated with or mapped to each bin in the set of bins, where any bin value may represent a counter indicating a frequency of fingerprint bit selections (described below—see e.g., Step222), for any stream chunk(s) assigned to a corresponding sim-group, that match the C-bit value associated with or mapped to a corresponding bin. An example sim-group bin-map is illustrated and described below with respect toFIG.4C.

In Step210, one or more data streams is/are received. In one or many embodiment(s) described herein, any data stream may refer to a continuous flow or transfer of data in any one or more formats (e.g., multimedia, text, image, video, audio, etc.). Further, each received data stream may originate, respectively, from a given data source (see e.g.,FIG.1).

In Step212, data from the data stream(s) (received in Step210) is partitioned into stream chunks. In one or many embodiment(s) described herein, any stream chunk across the data stream(s) may be of a predetermined, uniform size (e.g., four (4) MB). Further, any stream chunk may refer to a sequence or an ordered series of binary bits (e.g., each binary bit representing a variable either reflecting a one (1) or a zero (0) value) representing a portion of the data forming a data stream.

Hereinafter, a subset (i.e., Steps214,216,218,222,224,226,228,230,232,234,236,238,242,244,246,248,250,252,254,256,260,262,264,266,268,270,272,274,276,280,282,284,286,288,290,292, and294) of the remaining steps is performed, in series or in parallel, for each stream chunk (obtained via partitioning in Step212).

In Step214, a chunk bin-map, for the stream chunk, is initialized. In one or many embodiment(s) described herein, the chunk bin-map may refer to a data structure (e.g., a vector or an array) that captures an approximate probability distribution of a set of chunk segment fingerprints (described below—see e.g., Step218) for chunk segments (described below—see e.g., Step216) belonging to the stream chunk.

The chunk bin-map, accordingly, may be defined or described through: (a) a set of bins (e.g., vector/array elements), where the number of bins forming the set of bins may be derived from the set-bits cardinality (obtained in Step206) or, more specifically, through the mathematical expression 2C, where C equals the set-bits cardinality; (b) a different C-bit value, from a set of possible C-bit values, associated with or mapped to each bin in the set of bins; and a separate bin value, associated with or mapped to each bin in the set of bins, where any bin value may represent a counter indicating a frequency of fingerprint bit selections (described below—see e.g., Step222), for any chunk segment(s) belonging to the stream chunk, that match the C-bit value associated with or mapped to a corresponding bin. An example chunk bin-map is illustrated and described below with respect toFIG.4C.

In Step216, the stream chunk is partitioned into chunk segments. In one or many embodiment(s) described herein, any chunk segment across the stream chunks may be of a predetermined, uniform size (e.g., eight (8) KB). Further, any chunk segment may refer to a sequence or an ordered series of binary bits (e.g., each binary bit representing a variable either reflecting a one (1) or a zero (0) value) representing a portion of the data forming a stream chunk.

Hereinafter, another subset (i.e., Steps218,222,224, and226) of the remaining steps is performed, in series or in parallel, for each chunk segment (obtained via partitioning in Step216).

In Step218, a chunk segment fingerprint is generated for the chunk segment. In one or many embodiment(s) described herein, the chunk segment fingerprint may refer to a hash digest or a hash value produced through processing of the chunk segment using any existing hash function (e.g., any of the Secure Hash Algorithm series (SHA-1, SHA-2, SHA-3)). The chunk segment fingerprint may be expressed as a sequence or an ordered series of binary bits (e.g., each binary bit representing a variable either reflecting a one (1) or a zero (0) value) representing mapped data produced by the hash function given the chunk segment as input.

Turning toFIG.2B, in Step222, the fingerprint bit-mask (obtained in Step204) is applied to the chunk segment fingerprint (generated in Step218). In one or many embodiment(s) described herein, said application may entail performing a bit-wise AND operation between the fingerprint bit-mask and the chunk segment fingerprint. Further, through said application, one or more specific bits amongst the chunk segment fingerprint, which match the bit position(s) of the set-bit(s) amongst the fingerprint bit-mask, may be identified. Once identified, a value for each of the said specific bit(s) may be concatenated to produce/obtain a fingerprint bit selection. The fingerprint bit selection, therefore, may refer to a sequence or an ordered series of binary bits (e.g., each binary bit representing a variable either reflecting a one (1) or a zero (0) value) representing at least a portion of the data forming the chunk segment fingerprint. For example, when considering a fingerprint bit-mask of 11001001 and a chunk segment fingerprint of 10100011: the set-bits of the fingerprint bit-mask are in the first, second, fifth, and eight bit-positions (from left to right); and the identified values corresponding to these bit-positions (from left to right) in the chunk segment fingerprint are 1001, which represent the fingerprint bit selection.

In Step224, the fingerprint bit selection (obtained in Step222) is mapped to a matching bin, at least in part, defining or forming the chunk bin-map (initialized in Step214or updated in Step226(described below)). In one or many embodiment(s) described herein, the matching bin may refer to a bin, in the set of bins of the chunk bin-map, that may be associated with a C-bit value (where C equals the set-bits cardinality (obtained in Step206)), in the set of possible C-bit values, that matches the fingerprint bit selection. An example of said mapping is illustrated and described with respect toFIG.4G, below.

In Step226, the chunk bin-map (initialized in Step214or updated in a previous iteration of Step226) is updated. Particularly, in one or many embodiment(s) described herein, said updating may entail incrementing a bin value, associated with or mapped to the matching bin (identified in Step224), by one.

Hereinafter, in one or many embodiment(s) described herein, if all chunk segments (obtained in Step216) of the stream chunk (obtained in Step212) had been subjected to chunk segment processing (i.e., Steps218,222,224, and226), then the method proceeds to Step228. On the other hand, in one or many other embodiment(s) described herein, if at least one chunk segment of the stream chunk has yet to undergo chunk segment processing, then the method alternatively proceeds to Step218, where a next chunk segment of the chunk segments (obtained in Step216) commences chunk segment processing.

In Step228, the chunk bin-map (updated in Step226) is normalized. In one or many embodiment(s) described herein, statistical normalization may refer to the transformation of a dataset (e.g., chunk bin-map) such that any variations (or values) exhibited by the dataset ultimately falls between zero (0) and one (1).

In Step230, a determination is made as to whether a feedback event has been received. A feedback event may refer to an occurrence involving the submission of an alert or notice from any work node (or more specifically, from a cluster controller agent installed thereon) to the cluster controller. Said alert/notice may be triggered by a state or a metric, concerning the work node, meeting a respective criterion. By way of examples, said state or metric may include: a data deduplication efficiency (or ratio); computer processor utilization; input-output (IO) operations per second (IOPS); and data access latency. Further, said various state and metrics are not limited to the aforementioned specific examples. Said criterion, respective to a monitored data deduplication efficiency, for example, may reflect a certain data deduplication efficiency threshold, where the feedback event may be triggered as a result of the monitored data deduplication efficiency falling below the data deduplication efficiency threshold.

As such, in one or many embodiment(s) described herein, if it is determined that a feedback event has been received, then the method proceeds to Step232. On the other hand, in one or many other embodiment(s) described herein, if it is alternatively determined that a feedback event has not been received, then the method alternatively proceeds to Step244(see e.g.,FIG.2C). Moreover, although the determination is presented in the flowchart as transpiring after a chunk bin-map has been updated for every chunk segment (obtained in Step216), one of ordinary skill will appreciate that said determination (and thus said triggering of an alert/notice to the cluster controller) may transpire at any time following an initial monitoring of the set of work nodes (see e.g., Step202).

In Step232, following the determination (made in Step230) that a feedback event has indeed been received, an epsilon (ε)—greedy action selection algorithm is performed. In one or many embodiment(s) described herein, the E-greedy action selection algorithm may generally represent a reinforcement learning based decision making algorithm, which may also be referred to in artificial intelligence circles as the multi-armed bandit algorithm. In said algorithm, an agent chooses between a best known (or optimal) action and a random action based at least on a relationship between a randomized variable n, expressed as a numerical value between zero (0) and one (1), and a probability value e directed to choosing the random action. The probability value ε, however, is typically set as a low value (e.g., 0.01≤ε≤0.1), thereby ensuring that the optimal action is chosen with more frequency while also providing a small chance for the random action to be chosen. Regarding the aforementioned relationship: the random action is chosen if n<ε, otherwise the optimal action is chosen.

Concerning embodiments described herein, the optimal action may be represented via assignment of the stream chunk (obtained in Step212) to an optimal sim-group (or work node) based on one or more factors (described in more detail below), whereas the random action may be represented via assignment of the stream chunk to a random sim-group (or work node) (which may include the optimal sim-group or work node). Thus, summarily, in performing the ε-greedy action selection algorithm, a next action may be obtained, which may entail either the optimal action or the random action.

In Step234, a determination is made as to whether the next action (obtained in Step232) is directed to the assignment of the stream chunk (obtained in Step212) to a random sim-group (or work node) (e.g., a random action). In one or many embodiment(s) described herein, if it is determined that the next action is to assign the stream chunk to a randomly selected sim-group (or work node), then the method proceeds to Step236. On the other hand, in one or many other embodiment(s) described herein, if it is alternatively determined that the next action is to assign the stream chunk to an optimally selected sim-group (or work node), then the method alternatively proceeds to Step244(see e.g.,FIG.2C).

In Step236, following the determination (made in Step234) that the next action (obtained in Step232) is to assign the stream chunk (obtained in Step212) to a randomly selected sim-group (or work node), a sim-group is selected through random selection. In one or many embodiment(s) described herein, said random selection may employ any existing algorithm configured to randomly select one option (e.g., a sim-group) from a set of options (e.g., a set of sim-groups).

In Step238, the stream chunk (obtained in Step212) is assigned to the sim-group (selected in Step236). More specifically, in one or many embodiment(s) described herein, the stream chunk may be provided to the work node associated with the sim-group whereon, at the work node, the stream chunk undergoes data deduplication.

In Step240, a sim-group bin-map, for the sim-group (selected in Step236), is updated. In one or many embodiment(s) described herein, said updating may entail performing a bin-wise summation of the bin values for each same bin between the sim-group bin-map and the chunk bin-map (normalized in Step228) for the stream chunk. An example of said bin-wise summation is illustrated and described with respect toFIG.4H, below. Further, following said updating of the sim-group bin-map, the updated sim-group bin-map is subjected to normalization. Statistical normalization may refer to the transformation of a dataset (e.g., sim-group bin-map) such that any variations (or values) exhibited by the dataset ultimately falls between zero (0) and one (1)

Hereinafter, in one or many embodiment(s) described herein, if at least one stream chunk (obtained in Step212) of the data stream(s) (received in Step210) has yet to undergo one of the possible pipelines of stream chunk processing (e.g., Pipeline1: Steps214,216,218,222,224,226,228,230,232,234,236,238, and240; Pipeline2: Steps214,216,218,222,224,226,228,230,244,246,248,250,252,254, and256; Pipeline3: Steps214,216,218,222,224,226,228,230,244,246,248,256,260,262,264,266,268,270,272, and274; Pipeline4: Steps214,216,218,222,224,226,228,230,244,246,248,256,260,262,264,274,276,280,282,284,285,288,290,292, and294; or Pipeline5: Steps214,216,218,222,224,226,228,230,244,246,248,256,260,262,264,274,276,280,282,284,286,296,290,292, and294), then the method proceeds to Step214, where a next stream chunk of the stream chunks (obtained in Step212) commences stream chunk processing. On the other hand, unless a failure or a disaster befalls the system (see e.g.,FIG.1), the method may continue to cycle back to Step212(where additional stream chunks may be obtained) following the end of any stream chunk processing pipeline as the data stream(s) (received in Step210) are continuous and never-ending.

Turning toFIG.2C, in Step244, following the alternate determination (made in Step230) that a feedback event has not been received, or following the alternate determination (made in Step234) that a next action (obtained in Step232) is to assign the stream chunk (obtained in Step212) to an optimally selected sim-group (or work node), a similarity distance set is computed. In one or many embodiment(s) described herein, any similarity distance may generally refer to a distance measure between two objects in m-dimensional space, where m denotes a number of object features describing each object. Any similarity distance may further indicate a degree of similarity between said two objects—with a smaller similarity distance being indicative that said two objects are more similar, whereas a greater similarity distance is alternatively indicative that said two objects are less similar. Further, any similarity distance may be measured using any existing similarity distance algorithm or formula—examples of which may include, but are not limited to: a Euclidean distance; a Manhattan distance; a Minkowski distance; and a Bhattacharyya distance.

In terms of embodiments described herein, each similarity distance computed amongst the similarity distance set may measure a degree of similarity between the chunk bin-map (normalized in Step228) for the stream chunk (obtained in Step212) and the sim-group bin-map (initialized in Step208or updated in Steps240,256,274, or294) for each sim-group or work node in the set of work nodes (discovered in Step200). Further, the above-mentioned number of object features (m) for each of the chunk bin-map and any sim-group bin-map may equal the number of bins, at least in part, defining either.

In Step246, the similarity distance set (computed in Step244) is filtered based on a similarity distance threshold to obtain a similarity distance subset. In one or many embodiment(s) described herein, the similarity distance threshold may reference a predetermined scalar, numerical value reflecting a maximum similarity distance up to which the chunk bin-map may be considered sufficiently close (and thus similar) to any sim-group bin-map. Further, any similarity distance, in the similarity distance subset, may reflect a scalar, numerical value that equals or falls below the similarity distance threshold.

In Step248, a subset cardinality, of the similarity distance subset (obtained in Step246), is obtained. In one or many embodiment(s) described herein, the subset cardinality may reflect a scalar, numerical value equaling the number of similarity distances forming the similarity distance subset.

In Step250, a determination is made as to whether the subset cardinality (obtained in Step248) reflects a scalar, numerical value greater than one (1). In one or many embodiment(s) described herein, if it is determined that the subset cardinality equals one (1), then the method proceeds to Step252. On the other hand, in one or many other embodiment(s) described herein, if it is alternatively determined that the subset cardinality exceeds one (1), then the method alternatively proceeds to Step258.

In Step252, following the determination (made in Step250) that the subset cardinality (obtained in Step248) equals one (1), a sim-group is identified. In one or many embodiment(s) described herein, the identified sim-group may map to the single similarity distance within the similarity distance subset (obtained in Step246). That is, the single similarity distance may measure the degree of similarity between the chunk bin-map (normalized in Step228) for the stream chunk (obtained in Step212) and the sim-group bin-map (initialized in Step208or updated in Steps240,256,274, or294) for the identified sim-group.

In Step254, the stream chunk (obtained in Step212) is assigned to the sim-group (identified in Step252). More specifically, in one or many embodiment(s) described herein, the stream chunk may be provided to the work node associated with the sim-group whereon, at the work node, the stream chunk undergoes data deduplication.

In Step256, the sim-group bin-map, for the sim-group (identified in Step252), is updated. In one or many embodiment(s) described herein, said updating may entail performing a bin-wise summation of the bin values for each same bin between the sim-group bin-map and the chunk bin-map (updated in Step226) for the stream chunk. An example of said bin-wise summation is illustrated and described with respect toFIG.4H, below. Further, following said updating of the sim-group bin-map, the updated sim-group bin-map is subjected to normalization. Statistical normalization may refer to the transformation of a dataset (e.g., sim-group bin-map) such that any variations (or values) exhibited by the dataset ultimately falls between zero (0) and one (1)

Hereinafter, in one or many embodiment(s) described herein, if at least one stream chunk (obtained in Step212) of the data stream(s) (received in Step210) has yet to undergo one of the possible pipelines of stream chunk processing (e.g., Pipeline1: Steps214,216,218,222,224,226,228,230,232,234,236,238, and240; Pipeline2: Steps214,216,218,222,224,226,228,230,244,246,248,250,252,254, and256; Pipeline3: Steps214,216,218,222,224,226,228,230,244,246,248,256,260,262,264,266,268,270,272, and274; Pipeline4: Steps214,216,218,222,224,226,228,230,244,246,248,256,260,262,264,274,276,280,282,284,285,288,290,292, and294; or Pipeline5: Steps214,216,218,222,224,226,228,230,244,246,248,256,260,262,264,274,276,280,282,284,286,296,290,292, and294), then the method proceeds to Step214, where a next stream chunk of the stream chunks (obtained in Step212) commences stream chunk processing. On the other hand, unless a failure or a disaster befalls the system (see e.g.,FIG.1), the method may continue to cycle back to Step212(where additional stream chunks may be obtained) following the end of any stream chunk processing pipeline as the data stream(s) (received in Step210) are continuous and never-ending.

In Step258, following the alternate determination (made in Step250) that the subset cardinality (obtained in Step248) exceeds one (1), a workload state set is obtained. In one or many embodiment(s) described herein, any workload state may include one or more metrics (e.g., computer processor utilization, input-output (IO) operations per second (IOPS), etc.) descriptive of the workload currently being handled by a respective work node. As such, the workload state set may include at least two workload states each pertaining to a different work node. Furthermore, each work node, from which a workload state may be obtained, may correspond to a sim-group mapped to one of the at least two similarity distances forming the similarity distance subset (obtained in Step248). A sim-group may map to a similarity distance by way of being associated with a sim-group bin-map that, alongside the chunk bin-map (normalized in Step228) for the stream chunk (obtained in Step212), had been used to compute said similarity distance (in Step244).

Turning toFIG.2D, in Step262, the workload state set (obtained in Step258) is filtered based on one or more workload state thresholds (i.e., one per workload metric) to obtain a workload state subset. In one or many embodiment(s) described herein, any workload state threshold may reference a predetermined maximum value, in a format (e.g., scalar number, percentage, etc.) appropriate to a workload metric to which the workload state threshold corresponds, up to which a work node, at least in part, may be considered to have sufficient remaining capacity to handle more data deduplication work (e.g., via the assignment of more stream chunks thereto). Therefore, any workload state, in the workload state subset, may reflect one or more workload metrics each equaling or falling below their respective workload state threshold.

In Step264, a subset cardinality, of the workload state subset (obtained in Step262), is obtained. In one or many embodiment(s) described herein, the subset cardinality may reflect a scalar, numerical value equaling the number of workload states forming the workload state subset.

In Step266, a determination is made as to whether the subset cardinality (obtained in Step264) reflects a scalar, numerical value greater than one (1). In one or many embodiment(s) described herein, if it is determined that the subset cardinality equals one (1), then the method proceeds to Step268. On the other hand, in one or many other embodiment(s) described herein, if it is alternatively determined that the subset cardinality exceeds one (1), then the method alternatively proceeds to Step276.

In Step268, following the determination (made in Step266) that the subset cardinality (obtained in Step264) equals one (1), a work node is identified. In one or many embodiment(s) described herein, the identified work node may map to the single workload state within the workload state subset (obtained in Step262).

In Step270, the stream chunk (obtained in Step212) is provided to the work node (identified in Step268) whereon, at the work node, the stream chunk undergoes data deduplication.

In Step272, the work node (identified in Step268) is mapped to a corresponding sim-group.

In Step274, the sim-group bin-map, for the sim-group (identified in Step272), is updated. In one or many embodiment(s) described herein, said updating may entail performing a bin-wise summation of the bin values for each same bin between the sim-group bin-map and the chunk bin-map (normalized in Step228) for the stream chunk. An example of said bin-wise summation is illustrated and described with respect toFIG.4H, below. Further, following said updating of the sim-group bin-map, the updated sim-group bin-map is subjected to normalization. Statistical normalization may refer to the transformation of a dataset (e.g., sim-group bin-map) such that any variations (or values) exhibited by the dataset ultimately falls between zero (0) and one (1)

Hereinafter, in one or many embodiment(s) described herein, if at least one stream chunk (obtained in Step212) of the data stream(s) (received in Step210) has yet to undergo one of the possible pipelines of stream chunk processing (e.g., Pipeline1: Steps214,216,218,222,224,226,228,230,232,234,236,238, and240; Pipeline2: Steps214,216,218,222,224,226,228,230,244,246,248,250,252,254, and256; Pipeline3: Steps214,216,218,222,224,226,228,230,244,246,248,256,260,262,264,266,268,270,272, and274; Pipeline4: Steps214,216,218,222,224,226,228,230,244,246,248,256,260,262,264,274,276,280,282,284,285,288,290,292, and294; or Pipeline5: Steps214,216,218,222,224,226,228,230,244,246,248,256,260,262,264,274,276,280,282,284,286,296,290,292, and294), then the method proceeds to Step214, where a next stream chunk of the stream chunks (obtained in Step212) commences stream chunk processing. On the other hand, unless a failure or a disaster befalls the system (see e.g.,FIG.1), the method may continue to cycle back to Step212(where additional stream chunks may be obtained) following the end of any stream chunk processing pipeline as the data stream(s) (received in Step210) are continuous and never-ending.

In Step276, following the alternate determination (made in Step266) that the subset cardinality (obtained in Step264) exceeds one (1), a data stream is identified. In one or many embodiment(s) described herein, the data stream may be one of the data stream(s) (received in Step210). Further, the stream chunk (obtained in Step212) may belong to, or had been a part of, the data stream prior to its partitioning therefrom. As such, the data stream may represent a spatial locality associated with the stream chunk. Spatial locality, in turn, may generally refer to an assumption in data access behavior which specifies that any data located close to any recently accessed data has a higher likelihood of being accessed themselves.

Therefore, in one or many embodiment(s) described herein, if assignment of the stream chunk is inconclusive based on similarity distance measures and workload metrics, then the stream chunk should be assigned to the same work node to which other stream chunk(s), also belonging to the identified data stream, has/have been assigned. By assigning any stream chunks (or at least a majority thereof), which belong to or derive from a same data stream, to a same work node, a spatial locality applied to the stream chunks may be maintained when said streams chunks are transferred from said same data stream to said same work node.

In Step278, any number of other stream chunks, each of which have already been assigned, is/are identified. In one or many embodiment(s) described herein, the other stream chunk(s) each belong to, or had been a part of, the data stream (identified in Step276), similar to the stream chunk (obtained in Step212), prior to their partitioning therefrom.

Turning toFIG.2E, in Step282, a sim-group collection is identified. In one or many embodiment(s) described herein, the sim-group collection may refer to, and thus include, one or more sim-groups to which the other stream chunk(s) (identified in Step278) had been assigned.

In Step284, within the sim-group collection (identified in Step282), a sim-group collection subset is searched for. That is, in one or many embodiment(s) described herein, the sought sim-group collection subset may include one or more sim-groups, from the sim-group collection, that each reflect a maximum stream chunk cardinality of the other stream chunk(s) (identified in Step278). The maximum stream chunk cardinality may refer to a scalar, numerical value equaling a highest number of the other stream chunk(s) assigned across the sim-group collection.

For example, consider that the sim-group collection includes five (5) sim-groups: sim-group1, sim-group2, sim-group3, sim-group4, and sim-group5. In said example, the number (or cardinality) of the other stream chunk(s) assigned, respectively, to each sim-group is found to be: 1, 3, 1, 1, and 2. In this case, the maximum stream chunk cardinality, which reflects the highest number of the other stream chunk(s) assigned across the sim-group collection, is 3 other stream chunks, which corresponds to sim-group2. The sim-group collection subset here thus only includes sim-group2.

By way of another example, consider the same sim-group collection from the previous example, however, the number (or cardinality) of the other stream chunk(s) assigned, respectively, to each sim-group is now found to be: 2, 5, 3, 1, and 5. In this case, the maximum stream chunk cardinality, which reflects the highest number of the other stream chunk(s) assigned across the sim-group collection, is 5 other stream chunks, which corresponds to sim-group2and sim-group5. The sim-group collection subset here thus includes sim-group2and sim-group5.

In Step286, a cardinality of the sim-group collection subset is obtained. In one or many embodiment(s) described herein, said cardinality may reflect a scalar, numerical value equaling the number of sim-groups forming the sim-group collection subset (searched for in Step284). Further, said number of sim-groups may include at least a portion of the sim-group(s) forming the sim-group collection (identified in Step282).

In Step288, a determination is made as to whether the cardinality of the sim-group collection subset (obtained in Step286) reflects a scalar, numerical value greater than one (1). In one or many embodiment(s) described herein, if it is determined that the subset cardinality exceeds one (1), then the method proceeds to Step290. On the other hand, in one or many other embodiment(s) described herein, if it is alternatively determined that the subset cardinality equals one (1), then the method alternatively proceeds to Step296.

In Step290, following the determination (made in Step288) that the cardinality of the sim-group collection subset (obtained in Step286) exceeds one (1), a sim-group, of the sim-groups forming the sim-group collection subset, is selected. In one or many embodiment(s) described herein, the sim-group may be selected through random selection. Further, said random selection may employ any existing algorithm configured to randomly select one option (e.g., the sim-group) from a set of options (e.g., the sim-group collection subset).

In Step292, the stream chunk (obtained in Step212) is assigned to the sim-group (selected in Step290or identified in Step296). More specifically, in one or many embodiment(s) described herein, the stream chunk may be provided to the work node associated with the sim-group whereon, at the work node, the stream chunk undergoes data deduplication.

In Step294, the sim-group bin-map, for the sim-group (selected in Step290or identified in Step296), is updated. In one or many embodiment(s) described herein, said updating may entail performing a bin-wise summation of the bin values for each same bin between the sim-group bin-map and the chunk bin-map (normalized in Step228) for the stream chunk. An example of said bin-wise summation is illustrated and described with respect toFIG.4H, below. Further, following said updating of the sim-group bin-map, the updated sim-group bin-map is subjected to normalization. Statistical normalization may refer to the transformation of a dataset (e.g., sim-group bin-map) such that any variations (or values) exhibited by the dataset ultimately falls between zero (0) and one (1)

Hereinafter, in one or many embodiment(s) described herein, if at least one stream chunk (obtained in Step212) of the data stream(s) (received in Step210) has yet to undergo one of the possible pipelines of stream chunk processing (e.g., Pipeline1: Steps214,216,218,222,224,226,228,230,232,234,236,238, and240; Pipeline2: Steps214,216,218,222,224,226,228,230,244,246,248,250,252,254, and256; Pipeline3: Steps214,216,218,222,224,226,228,230,244,246,248,256,260,262,264,266,268,270,272, and274; Pipeline4: Steps214,216,218,222,224,226,228,230,244,246,248,256,260,262,264,274,276,280,282,284,285,288,290,292, and294; or Pipeline5: Steps214,216,218,222,224,226,228,230,244,246,248,256,260,262,264,274,276,280,282,284,286,296,290,292, and294), then the method proceeds to Step214, where a next stream chunk of the stream chunks (obtained in Step212) commences stream chunk processing. On the other hand, unless a failure or a disaster befalls the system (see e.g.,FIG.1), the method may continue to cycle back to Step212(where additional stream chunks may be obtained) following the end of any stream chunk processing pipeline as the data stream(s) (received in Step210) are continuous and never-ending.

In Step296, following the alternate determination (made in Step266) that the cardinality of the sim-group collection subset (obtained in Step286) equals one (1), the single sim-group, forming the sim-group collection subset (searched for in Step284), is identified.

Hereinafter, the method proceeds to Step292(described above).

FIG.3shows a computing system in accordance with one or more embodiments described herein. The computing system (300) may include one or more computer processors (302), non-persistent storage (304) (e.g., volatile memory, such as random access memory (RAM), cache memory), persistent storage (306) (e.g., a hard disk, an optical drive such as a compact disk (CD) drive or digital versatile disk (DVD) drive, a flash memory, etc.), a communication interface (6312) (e.g., Bluetooth interface, infrared interface, network interface, optical interface, etc.), input devices (310), output devices (308), and numerous other elements (not shown) and functionalities. Each of these components is described below.

In one or many embodiment(s) described herein, the computer processor(s) (302) may be an integrated circuit for processing instructions. For example, the computer processor(s) may be one or more cores or micro-cores of a central processing unit (CPU) and/or a graphics processing unit (GPU). The computing system (300) may also include one or more input devices (310), such as a touchscreen, keyboard, mouse, microphone, touchpad, electronic pen, or any other type of input device. Further, the communication interface (312) may include an integrated circuit for connecting the computing system (300) to a network (not shown) (e.g., a local area network (LAN), a wide area network (WAN) such as the Internet, mobile network, or any other type of network) and/or to another device, such as another computing device.

In one or many embodiment(s) described herein, the computing system (300) may include one or more output devices (308), such as a screen (e.g., a liquid crystal display (LCD), a plasma display, touchscreen, cathode ray tube (CRT) monitor, projector, or other display device), a printer, external storage, or any other output device. One or more of the output devices may be the same or different from the input device(s). The input and output device(s) may be locally or remotely connected to the computer processor(s) (302), non-persistent storage (304), and persistent storage (306). Many different types of computing systems exist, and the aforementioned input and output device(s) may take other forms.

Software instructions in the form of computer readable program code to perform embodiments described herein may be stored, in whole or in part, temporarily or permanently, on a non-transitory computer readable medium such as a CD, DVD, storage device, a diskette, a tape, flash memory, physical memory, or any other computer readable storage medium. Specifically, the software instructions may correspond to computer readable program code that, when executed by a processor(s), is configured to perform one or many embodiment(s) described herein.

FIGS.4A-4Hshow an example scenario in accordance with one or more embodiments described herein. The example scenario presented in conjunction with components illustrated inFIGS.4A-4His for explanatory purposes only and not intended to limit the embodiments described herein.

Concerning the example scenario, consider the example system (400) illustrated inFIG.4Aas the setting. The example system (400) includes two (2) data sources—i.e. Data Source1(402A) and Data Source2(402B)—operatively connected to a Cluster Controller (404), which in turn is operatively connected to a Deduplication Work Cluster (408) including three (3) work nodes—i.e., Work Node1(406A), Work Node2(406B), and Work Node3(406C). As for operations, each data source (402A,402B) transmits a continuous flow of its respective data as a data stream to the Cluster Controller (404), where the latter then assigns said data, to undergo data deduplication processing, to the work nodes (406A-406C) per embodiments described herein.

To the extent of the embodiments described herein, prior to processing any received data from the data sources (402A,402B), the Cluster Controller (404) begins by discovering, and subsequently monitoring, each of the three work nodes (406A-406C). Thereafter, the Cluster Controller (404) obtains a fingerprint bit-mask—e.g., the example fingerprint bit-mask (410) illustrated inFIG.4B. As presented, the example fingerprint bit-mask (410) includes sixteen (16) bits each capable of reflecting a binary value of either a one (1) or a zero (0). Further, of the sixteen (16) bits, three (3) bits—at bit positions5,6, and7—each reflect the binary one (1) value, thereby designating these three (3) bits as set-bits (412).

Based on a cardinality—i.e., three (3)—of the set-bits (412), the Cluster Controller (404) understands that any bin-map (see e.g., the example initialized sim-group/chunk bin-map (414) illustrated inFIG.4C) generated and initialized hereinafter, whether for a sim-group or for a stream chunk, is defined by a number of bins equaling the mathematical expression 2C, where C is the said set-bits (412) cardinality. The number of bins defining any bin-map is thus 23=8 bins. Each bin, further, is associated with one of a set of possible values that can be reflected, through concatenation, by the set-bits (412) of the example fingerprint bit-mask (410). Said set of possible (3-bit) values (416) includes: 000, 001, 010, 011, 100, 101, 110, and 111. In defining any bin-map (414), these possible values are arranged in a one value per bin association in ascending order from the left-most bin to the right-most bin. In completing the definition of any bin-map (414), each bin thereof is further associated with a bin value representing a counter indicating a frequency of fingerprint bit selections (exemplified below) that match the possible (3-bit) value (416) mapped to the bin.

As there are three (3) work nodes (406A-406C) each corresponding to a respective sim-group, the Cluster Controller (404) generates and initializes three (3) sim-group bin-maps each resembling, at least initially, the example initialized sim-group/chunk bin-map (414).

From here, and with reference toFIG.4D, the Cluster Controller (404) commences receipt of two data streams—e.g., example data stream1(418A) and example data stream2(418B)—from the two data sources (402A,402B), respectively. Said two data streams (418A,418B) are each subsequently partitioned inline into stream chunks. In this example scenario, the stream chunks, from each data stream (418A,418B), are to be processed serially by way of a single data queue—e.g., example data queue (420). Within the single data queue (420), the stream chunks, from each data stream (418A,418B), await to be processed in an alternating order.

In processing any given stream chunk, the Cluster Controller (404) first generates and initializes a chunk bin-map, which, at least initially, resembles the example initialized sim-group/chunk bin-map (414). Turning toFIG.4E, and in continuance of said processing by the Cluster Controller (404), each stream chunk—e.g., example stream chunk (422)—is partitioned into chunk segments—i.e., Chunk Segment1(424A), Chunk Segment2(424B), Chunk Segment3(424C), and Chunk Segment4(424D). Each of these chunk segments (424A-424D) is subsequently inputted into a hash function (426), thereby producing a corresponding chunk segment fingerprint (428A-428D) as the hash function (426) output.

As illustrated inFIG.4F, the Cluster Controller (404) then applies the example fingerprint bit-mask (410) to each example chunk segment fingerprint (428A-428D). Each said application entails a bit-wise AND operation between the example fingerprint bit-mask (410) and an example chunk segment fingerprint (428A-428D), which results in the identification of a fingerprint bit selection (430A-430D). Any fingerprint bit-selection (430A-430D) reflects the concatenated bit values of specific bits of a chunk segment fingerprint (428A-428D) located at the same bit positions—i.e., bit positions bit positions5,6, and7—as the set-bits (412) of the fingerprint bit-mask (410). Accordingly, the fingerprint bit selections (430A-430D), respectively, for the chunk segment fingerprints (428A-428D) are: 001, 011, 010, and 110.

Next, as shown inFIG.4G, the Cluster Controller (404) updates the chunk bin-map (414) for the given stream chunk (422). Said updating entails, for each fingerprint bit selection (430A-430D): mapping the fingerprint bit selection (430A-430D) to a matching bin of the 8 bins defining the chunk bin-map (414), where the matching bin is associated with a possible 3-bit value equaling the fingerprint bit selection (430A-430D); and incrementing an existing bin value of the matching bin by one. In performing the aforementioned with respect to each fingerprint bit selection (430A-430D), an updated chunk bin-map (414A) results. Thereafter, the example chunk bin-map (414A) undergoes normalization. Through said statistical normalization: all bin values (i.e., [0, 1, 1, 1, 0, 0, 1, 0]) of the chunk bin-map (414A) are summed together to obtain a bin value total (i.e., 4); and then, each bin value of the chunk bin-map (414A) is divided by the bin value total to produce a normalized chunk bin-map (414B) with normalized bin values (i.e., [0, 0.25, 0.25, 0.25, 0, 0, 0.25, 0]).

Moreover, whether based on similarity distances, workload states, spatial locality, or application of an ε-greedy action selection algorithm, the Cluster Controller (404) ultimately identifies or selects one of the three (3) sim-groups corresponding, respectively, to one of the three (3) work nodes (406A-406C). For this example scenario, assume a Sim-Group2is identified/selected to which the stream chunk (422) is assigned.

Following the previous processing of several stream chunks, an existing, normalized sim-group bin-map (414C) for Sim-Group2is as presented at the top ofFIG.4H. Upon the stream chunk (422) being assigned to Sim-Group2, the existing, normalized sim-group bin-map (414C) thereof is updated using the normalized chunk bin-map (414B) for the stream chunk (422). Said updating entails a bin-wise summation of the bin values reflected in the existing, normalized Sim-Group2bin-map (414C) and the normalized chunk bin-map (414B), thereby resulting in an updated Sim-Group2bin-map (414D). Thereafter, the updated Sim-Group2bin-map (414D) undergoes normalization. Through said statistical normalization: all bin values (i.e., [0.12, 0.44, 0.29, 0.35, 0.35, 0.27, 0.42, 0.02]) of the updated Sim-Group2bin-map (414D) are summed together to obtain a bin value total (i.e., 2.26); and then, each bin value of the updated Sim-Group2bin-map (414D) is divided by the bin value total to produce a normalized Sim-Group2bin-map (414E) with normalized bin values (i.e., [0.05, 0.20, 0.13, 0.16, 0.16, 0.12, 0.19, 0.009]).

While embodiments described herein have been described with respect to a limited number of embodiments, those skilled in the art, having benefit of this disclosure, will appreciate that other embodiments can be devised which do not depart from the scope of the embodiments described herein. Accordingly, the scope of the embodiments described herein should be limited only by the attached claims.