# US 2019/0171362 A1 · Backup server selection based on data commonality

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0171362 A1
- Document ID: US20190171362A1
- Status: Published application
- Kind: A1
- Application number: 15/321,500
- Filed: 2016-03-29
- Published: 2019-06-06
- Earliest claimed: 2016-03-29
- Assignees: EMC Corporation
- Applicants: EMC Corporation
- Inventors: Nickolay Alexandrovich Dalmatov
- Web page: https://patentgrep.com/patent/US20190171362A1

## CPC

- G06F 3/065: {Replication mechanisms}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 7/02: Comparing digital values (G06F7/06, {G06F7/22,} G06F7/38 take precedence)
- G06F 11/1453: {using de-duplication of the data}
- G06F 16/00: Information retrieval; Database structures therefor; File system structures therefor
- H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC}
- G06F 11/1464: {for networked environments}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Techniques of backing up data stored on host computing devices involve selecting a backup server from among multiple servers on which to back up host data based on a measure of commonality between the host data and data stored in the backup servers. Prior to sending data for backup, a host sends a set of host data representations to a backup system. Each host data representation is based on a respective hash value computed from a respective block of the host data. The backup system compares the set of host data representations with server data representations for each backup server and computes a commonality score for each backup server. The backup system then selects a backup server on which to place the host data based at least in part on the commonality scores. Host data are then directed to the selected backup server for backup.

## Claims

### Claim 1

A method of backing up data stored on host computing devices, the method comprising:
receiving, by processing circuitry of a backup system, (i) a request to back up host data stored on a host computing device and (ii) a set of multiple host data representations, each host data representation based on a respective hash value computed from a respective block of the host data of the host computing device;
computing multiple commonality scores, including one commonality score for each of multiple backup servers in the backup system, each commonality score for a respective backup server indicating a measure of commonality between the set of host data representations and a respective set of server data representations for that backup server, each backup server including a respective set of storage devices; and
backing up the host data by (i) selecting one of the backup servers on which to back up the host data based at least in part on the commonality scores, and (ii) storing the host data in the set of storage devices of the selected backup server.

### Claim 2 (depends on 1)

A method as in claim 1, wherein selecting the backup server on which to back up the host data includes (i) comparing the commonality scores to identify a backup server having the highest commonality score and (ii) identifying the selected backup server as the backup server having the highest commonality score.

### Claim 3 (depends on 2)

A method as in claim 2, wherein receiving the set of multiple host data representations includes receiving, as each data representation, the respective hash value,
wherein each hash value was computed by applying a cryptographic hash function to the respective block of host data,
wherein each of the backup servers stores a respective set of data blocks, and
wherein the method further comprises, for each backup server, generating the set of server data representations for that backup server by applying the cryptographic hash function to each of the set of data blocks of that backup server to produce, as the set of server data representations for that backup server, a set of hash values for that backup server.

### Claim 4 (depends on 3)

A method as in claim 3, wherein computing the multiple commonality scores includes, for each of the backup servers, counting a number of matches between the hash values received from the host and the set of hash values for that backup server to produce a total for that backup server, wherein the selected backup server is the backup server for which the largest total is produced.

### Claim 5 (depends on 4)

A method as in claim 4, wherein each hash value is M bits in length, and wherein applying the cryptographic function to each of the set of data blocks of each backup server includes (i) applying a hash function to generate a N-bit result and (ii) sampling the N-bit result to produce an M-bit result, wherein M is less than N.

### Claim 6 (depends on 2)

A method as in claim 2, wherein the set of host data representations includes a bloom filter of blocks of the host data, the bloom filter including (i) a set of cryptographic hash functions and (ii) a bit string of a predetermined length, each of the set of cryptographic hash functions mapping a block of host data to a respective position in the bit string such that the bit string has a set of mapped positions and a set of unmapped positions, each mapped position in the bit string having a first value, each unmapped position in the bit string having a second value;
wherein each of the backup servers stores respective blocks of data;
wherein the method further comprises, for each of the backup servers,
applying each of the set of cryptographic hash functions to a block of data of that backup server to produce a bit position of that hash function for that block of data;
wherein computing the multiple commonality scores includes, for each of the backup servers, (i) applying each of the cryptographic hash functions to a block of data of that backup server to produce a set of bit positions and (ii) reducing the commonality score for that backup server in response to at least one of the produced set of bit positions of the bit string of the bloom filter having the second value.

### Claim 7 (depends on 1)

A method as in claim 1, wherein the host data representations received by the backup system pertain to a subset of all of the data blocks stored in the host computing device.

### Claim 8 (depends on 7)

A method as in claim 7, wherein each set of server data representations for a backup server pertains to a subset of all of the data blocks stored on that backup server.

### Claim 9 (depends on 1)

A method as in claim 1, wherein each set of server data representations for a backup server pertains to a subset of all of the data blocks stored on that backup server.

### Claim 10 (depends on 1)

A method as in claim 1, wherein backing up the host data further includes performing a load balancing assessment, the load balancing assessment producing a load balancing result indicating relative loading of the backup servers, and
wherein selecting one of the backup servers on which to back up the host data is also based in part on the load balancing result.

### Claim 11

A computer program product including a set of non-transitory, computer-readable storage media storing executable instructions, which when executed by a computer, causes the computer to perform a method of backing up data stored on host computing devices, the method comprising:
receiving (i) a request to back up host data stored on a host computing device and (ii) a set of multiple host data representations, each host data representation based on a respective hash value computed from a respective block of the host data of the host computing device;
computing multiple commonality scores, including one commonality score for each of multiple backup servers in the backup system, each commonality score for a respective backup server indicating a measure of commonality between the set of host data representations and a respective set of server data representations for that backup server, each backup server including a respective set of storage devices; and
backing up the host data by (i) selecting one of the backup servers on which to back up the host data based at least in part on the commonality scores, and (ii) storing the host data in the set of storage devices of the selected backup server.

### Claim 12 (depends on 11)

A computer program product as in claim 11, wherein selecting the backup server on which to back up the host data includes (i) comparing the commonality scores to identify a backup server having the highest commonality score and (ii) identifying the selected backup server as the backup server having the highest commonality score.

### Claim 13 (depends on 12)

A computer program product as in claim 12, wherein receiving the set of multiple host data representations includes receiving, as each data representation, the respective hash value,
wherein each hash value was computed by applying a cryptographic hash function to the respective block of host data,
wherein each of the backup servers stores a respective set of data blocks, and
wherein the method further comprises, for each backup server, generating the set of server data representations for that backup server by applying the cryptographic hash function to each of the set of data blocks of that backup server to produce, as the set of server data representations for that backup server, a set of hash values for that backup server.

### Claim 14 (depends on 13)

A computer program product as in claim 13, wherein computing the multiple commonality scores includes, for each of the backup servers, counting a number of matches between the hash values received from the host and the set of hash values for that backup server to produce a total for that backup server, wherein the selected backup server is the backup server for which the largest total is produced.

### Claim 15 (depends on 14)

A computer program product as in claim 14, each hash value is M bits in length, and wherein applying the cryptographic function to each of the set of data blocks of each backup server includes (i) applying a hash function to generate a N-bit result and (ii) sampling the N-bit result to produce an M-bit result, wherein M is less than N.

### Claim 16 (depends on 12)

A computer program product as in claim 12, wherein the set of host data representations includes a bloom filter of blocks of the host data, the bloom filter including (i) a set of cryptographic hash functions and (ii) a bit string of a predetermined length, each of the set of cryptographic hash functions mapping a block of host data to a respective position in the bit string such that the bit string has a set of mapped positions and a set of unmapped positions, each mapped position in the bit string having a first value, each unmapped position in the bit string having a second value;
wherein each of the backup servers stores respective blocks of data;
wherein the method further comprises, for each of the backup servers, applying each of the set of cryptographic hash functions to a block of data of that backup server to produce a bit position of that hash function for that block of data;
wherein computing the multiple commonality scores includes, for each of the backup servers, (i) applying each of the cryptographic hash functions to a block of data of that backup server to produce a set of bit positions and (ii) reducing the commonality score for that backup server in response to at least one of the produced set of bit positions of the bit string of the bloom filter having the second value.

### Claim 17 (depends on 11)

A computer program product as in claim 11, wherein each set of server data representations for a backup server pertains to a subset of all of the data blocks stored on that backup server.

### Claim 18 (depends on 17)

A computer program product as in claim 17, wherein each set of server data representations for a backup server pertains to a subset of all of the data blocks stored on that backup server.

### Claim 19 (depends on 11)

A computer program product as in claim 11, wherein each set of server data representations for a backup server pertains to a subset of all of the data blocks stored on that backup server.

### Claim 20

An electronic apparatus comprising memory and controlling circuitry coupled to the memory, the controlling circuitry being constructed and arranged to:
receive (i) a request to back up host data stored on a host computing device and (ii) a set of multiple host data representations, each host data representation based on a respective hash value computed from a respective block of the host data of the host computing device;
compute multiple commonality scores, including one commonality score for each of multiple backup servers in the backup system, each commonality score for a respective backup server indicating a measure of commonality between the set of host data representations and a respective set of server data representations for that backup server, each backup server including a respective set of storage devices; and
back up the host data by (i) selecting one of the backup servers on which to back up the host data based at least in part on the commonality scores, and (ii) storing the host data in the set of storage devices of the selected backup server.
