IP Library Granted Patent US 11,394,780
Granted Patent B2
US 11,394,780 · App. 17/171,487 · Granted Jul 19, 2022

System and method for facilitating deduplication of operations to be performed

Inventors: Alexander Kesselman (Sunnyvale, CA); Alexandre Drobychev (San Jose, CA)
Assignee: Google LLC
H04L67/1097G06F3/067G06F3/0608G06F3/0641H04L67/1002
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 11,394,780
App. No.
17/171,487
Granted
Jul 19, 2022
Kind
B2
Abstract

A system, computer-readable storage medium storing at least one program, and a computer-implemented method for facilitating deduplication of operations to be performed is presented. An operation to be performed is received. A mapping function is applied to at least one parameter of the operation to produce a mapping value in a target mapping space, the target mapping space being partitioned between target servers in a set of target servers proportional to resource capacities of the target servers in the set of target servers. A target server in the set of target servers whose portion of the target mapping space includes the mapping value is identified. The operation is issued to the target server.

Claims (54)

1. A computer-implemented method performed on a server having at least one processor and memory, the method comprising:

receiving an operation to be performed within a distributed computing system;

in response to receiving the operation, determining a first mapping value for the operation based on at least a type of the operation or data included in the operation;

identifying a target resource corresponding to the first mapping value, wherein the target resource is partitioned between a plurality of target servers in the distributed computing system based on respective resource capacities of target servers of the plurality of target servers;

identifying, from among the plurality of target servers, a particular target server associated with the target resource;

issuing the operation to the particular target server;

receiving another operation including the type of the operation or the data; and

issuing the another operation to the particular target server.

2. The method of claim 1 , further comprising:

determining that at least one target server in the plurality of target servers has become unavailable; and

partitioning the target resource associated with the at least one target server between remaining target servers of the plurality of target servers based on resource capacities of the remaining target servers.

3. The method of claim 1 , wherein the target resource allocated to the particular target server comprises two or more non-contiguous portions of a target mapping space.

4. The method of claim 3 , comprising partitioning the target mapping space between the plurality of target servers based on the respective resource capacities of the target servers such that resources allocated to two or more of the target servers differ in size.

5. The method of claim 1 , wherein the respective resource capacity of a target server of the plurality of target servers comprises a composite capacity based on two or more of:

an amount of storage that is available for use at the target server;

an amount of processor time that is available for use at the target server;

an amount of memory that is available for use at the target server; and

availability of network resources for use by the target server.

6. The method of claim 1 , wherein determining the first mapping value comprises determining the first mapping value based on data included in the operation, and the data included in the operation comprises one of audio file data, video file data, documents, text data, or image data.

7. The computer-implemented method of claim 1 , wherein the operation includes a request to write data to the target servers, and the respective resource capacities of the target servers include a remaining amount of available storage space on the plurality of target servers.

8. A system, comprising:

at least one processor;

memory; and

instructions stored in the memory and executable by the at least one processor, the instructions causing the at least one processor to:

receive an operation to be performed within a distributed computing system;

in response to receiving the operation, determine a first mapping value for the operation based on at least a type of the operation or data included in the operation;

identify a target resource corresponding to the first mapping value, wherein the target resource is partitioned between a plurality of target servers in the distributed computing system based on respective resource capacities of target servers in the plurality of target servers;

identify, from among the plurality of target servers, a particular target server associated with the target resource; and

issue the operation to the particular target server;

receive another operation including the type of the operation or the data; and

issue the another operation to the particular target server.

9. The system of claim 8 , wherein the instructions cause the processor to:

determine that at least one target server in the plurality of target servers has become unavailable; and

partition the target resource associated with the at least one target server between remaining target servers of the plurality of target servers based on resource capacities of the remaining target servers.

10. The system of claim 8 , wherein the target resource allocated to the particular target server comprises two or more non-contiguous portions of a target mapping space.

11. The system of claim 8 , wherein the operation includes a request to perform a search query, and the respective resource capacities of the target servers include a number of queries per second that the plurality of target servers can process.

12. The system of claim 8 , wherein determine the first mapping value comprises determine the first mapping value based on data included in the operation, and the data included in the operation comprises one of audio file data, video file data, documents, text data, or image data.

13. The system of claim 8 , wherein the operation includes a request to write data, and the respective resource capacities of the target servers in the plurality of target servers include a remaining amount of available storage space on the target server.

14. A non-transitory computer-readable storage medium storing at least one program configured for execution by at least one processor of a computer system, the at least one program comprising instructions for:

receiving an operation to be performed within a distributed computing system;

in response to receiving the operation, determining a first mapping value for the operation based on at least a type of the operation or data included in the operation;

identifying a target resource corresponding to the first mapping value, wherein the target resource is partitioned between a plurality of target servers in the distributed computing system based on respective resource capacities of target servers of the plurality of target servers;

identifying, from among the plurality of target servers, a particular target server associated with the target resource;

issuing the operation to the particular target server;

receiving another operation including the type of the operation or the data; and

issuing the another operation to the particular target server.

15. The non-transitory computer-readable storage medium of claim 14 , wherein the at least one program further comprises instructions for:

determining that at least one target server in the plurality of target servers has become unavailable; and

partitioning the target resource associated with the at least one target server between remaining target servers of the plurality of target servers based on resource capacities of the remaining target servers.

16. The non-transitory computer-readable storage medium of claim 14 , wherein the target resource allocated to the particular target server comprises two or more non-contiguous portions of a target mapping space.

17. The non-transitory computer-readable storage medium of claim 14 , wherein the operation includes a request to perform a search query.

18. The non-transitory computer-readable storage medium of claim 14 , wherein the operation includes a request to perform a search query, and the respective resource capacities of target server include a number of queries per second that the plurality of target servers can process.

19. The non-transitory computer-readable storage medium of claim 14 , wherein determining the first mapping value comprises determining the first mapping value based on data included in the operation, and the data included in the operation comprises one of audio file data, video file data, documents, text data, or image data.

20. The non-transitory computer-readable storage medium of claim 14 , wherein the operation includes a request to write data to the target server, and the respective resource capacities of the target servers include a remaining amount of available storage space on the target server.

Assignments (2)
CHANGE OF NAME Recorded Mar 10, 2021
From: GOOGLE INC.
To: GOOGLE LLC
Reel/Frame 055547/0330 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 9, 2021
From: KESSELMAN, ALEX; DROBYCHEV, ALEXANDRE
To: GOOGLE INC.
Reel/Frame 055537/0865 →
Continuity (4)
Continuation 15785285 · Oct 16, 2017
Continuation 13874381 · Apr 30, 2013
Provisional Application 61640632 · Apr 30, 2012
Related Publication 20210168208A1 · Jun 3, 2021