IP Library Granted Patent US 11,468,127
Granted Patent B1
US 11,468,127 · App. 16/291,284 · Granted Oct 11, 2022

Data delivery

Inventors: Matthew A. Armstrong (Kirkland, WA); Matthew B. Tolton (Seattle, WA); Hossein Ahmadi (Kirkland, WA); Michael Entin (Redmond, WA)
Assignee: Google LLC
G06F16/95
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,468,127
App. No.
16/291,284
Granted
Oct 11, 2022
Kind
B1
Abstract

This disclosure generally relates to data delivery in distributed applications. One example method includes identifying a data source associated with a shuffle operation, the data source configured provide data from a data set associated with the shuffle operation; identifying a data sink associated with the shuffle operation, the data sink configured to receive data provided by the data source; associating a shuffler component with the shuffle operation, the shuffler component configured to receive data from the data source and provide the data to the data sink; receiving, by the shuffler component, a first data portion from the data source; providing, by the shuffler component, the first data portion to the data sink; receiving, by the shuffler component, a second data portion from the data source, the second data portion being received from the data source prior to or concurrent with providing the first data portion to the data sink.

Claims (60)

1. A computer-implemented method, comprising:

receiving, from a distributed database application, a request that a shuffle operation execute on a data set associated with the shuffle operation and stored in a distributed database;

identifying, based on the shuffle operation, a data source configured to provide the data set associated with the shuffle operation;

identifying, based on the shuffle operation, a data sink configured to receive the data set;

configuring a first shuffler component that includes a first cache configured to receive the data set associated with the shuffle operation from the data source and provide the data set associated with the shuffle operation to the data sink;

determining a performance of the first shuffler component fails to satisfy a performance threshold;

in response to determining the performance of the first shuffler component fails to satisfy the performance threshold, configuring a second shuffler component that includes a second cache configured to receive the data set associated with the shuffle operation from the data source and provide the data set associated with the shuffle operation to the data sink;

storing a first portion of the data set received from the data source in the second cache of the second shuffler component;

providing, based on the configuration of the second shuffler component, the first portion of the data set associated with the shuffle operation from the second cache of the second shuffler component to the data sink; and

storing a second portion of the data set received from the data source in the second cache of the second shuffler component concurrently with the second shuffler component providing the first portion of the data set to the data sink from the second cache of the second shuffler component.

2. The computer-implemented method of claim 1 , wherein the data source comprises a plurality of data sources and the data sink comprises a plurality of data sinks.

3. The computer-implemented method of claim 1 , further comprising:

receiving a plurality of additional portions of the data set from the data source in the second cache of the second shuffler component; and

providing the plurality of additional portions of the data set from the second cache of the second shuffler component to the data sink, wherein providing the plurality of additional portions of the data set at least partially overlaps with receiving the plurality of additional portions of the data set.

4. The computer-implemented method of claim 1 , further comprising receiving a final portion of the data set from the data source in the second cache of the second shuffler component prior to providing the first portion of the data set to the data sink.

5. The computer-implemented method of claim 1 , further comprising providing the first portion of the data set from the second cache of the second shuffler component to a second data sink.

6. The computer-implemented method of claim 1 , further comprising:

receiving, flat the second shuffler component, a flow control indication from the data sink; and

in response to receiving the flow control indication, suspending the second cache of the second shuffler component providing the first portion and the second portion of the data set to the data sink.

7. The computer-implemented method of claim 6 , further comprising:

receiving, flat the second shuffler component, a flow resume indication from the data sink; and

in response to receiving the flow resume indication, resuming the second cache of the second shuffler component providing the first portion and the second portion of the data set to the data sink.

8. The computer-implemented method of claim 1 , wherein a determining the performance of the first shuffler component fails to satisfy the performance threshold comprises determining a memory usage of the first shuffler component fails to satisfy a memory usage threshold.

9. The computer-implemented method of claim 1 , wherein the data set comprises database records in a set of database records.

10. The computer-implemented method of claim 1 , further comprising configuring a third shuffler component that includes a third cache configured to receive the data set associated with the shuffle operation from the data source and provide the data set associated with the shuffle operation to the data sink in parallel with the second shuffler component receiving the data set associated with the shuffle operation from the data source and providing the data set associated with the shuffle operation to the data sink.

11. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:

receiving, from a distributed database application, a request that a shuffle operation execute on a data set associated with the shuffle operation and stored in a distributed database;

identifying, based on the shuffle operation, a data source configured to provide the data set associated with the shuffle operation;

identifying, based on the shuffle operation, a data sink configured to receive the data set;

configuring a first shuffler component that includes a first cache configured to receive the data set associated with the shuffle operation from the data source and provide the data set associated with the shuffle operation to the data sink;

determining a performance of the first shuffler component fails to satisfy a performance threshold;

in response to determining the performance of the first shuffler component fails to satisfy the performance threshold, configuring a second shuffler component that includes a second cache configured to receive the data set associated with the shuffle operation from the data source and provide the data set associated with the shuffle operation to the data sink;

storing a first portion of the data set received from the data source in the second cache of the second shuffler component;

providing, based on the configuration of the second shuffler component, the first portion of the data set associated with the shuffle operation from the second cache of the second shuffler component to the data sink; and

storing a second portion of the data set received from the data source in the second cache of the second shuffler component concurrently with the second shuffler component providing the first portion of the data set to the data sink from the second cache of the second shuffler component.

12. The system of claim 11 , wherein the data source comprises a plurality of data sources and the data sink comprises a plurality of data sinks.

13. The system of claim 11 , wherein the operations further comprise:

receiving a plurality of additional portions of the data set from the data source in the second cache of the second shuffler component; and

providing the plurality of additional portions of the data set from the second cache of the second shuffler component to the data sink, wherein providing the plurality of additional portions of the data set at least partially overlaps with receiving the plurality of additional portions of the data set.

14. The system of claim 11 , wherein the operations further comprise receiving a final portion of the data set from the data source in the second cache of the second shuffler component prior to providing the first portion of the data set to the data sink.

15. The system of claim 11 , wherein the operations further comprise providing the first portion of the data set from the second cache of the second shuffler component to a second data sink.

16. The system of claim 11 , wherein the operations further comprise:

receiving, by flat the second shuffler component, a flow control indication from the data sink; and

in response to receiving the flow control indication, suspending the second cache of the second shuffler component providing the first portion and the second portion of the data set to the data sink.

17. The system of claim 16 , wherein the operations further comprise:

receiving, flat the second shuffler component, a flow resume indication from the data sink; and

in response to receiving the flow resume indication, resuming the second cache of the second shuffler component providing the first portion and the second portion of the data set to the data sink.

18. The system of claim 11 , wherein determining the performance of the first shuffler component fails to satisfy the performance threshold comprises determining a memory usage of the first shuffler component fails to satisfy a memory usage threshold.

19. The system of claim 11 , wherein the data set comprises database records in a set of database records.

20. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

receiving, from a distributed database application, a request that a shuffle operation execute on a data set associated with the shuffle operation and stored in a distributed database;

identifying, based on the shuffle operation, a data source configured to provide the data set associated with the shuffle operation;

identifying, based on the shuffle operation, a data sink configured to receive the data set;

configuring a first shuffler component that includes a first cache configured to receive the data set associated with the shuffle operation from the data source and provide the data set associated with the shuffle operation to the data sink;

determining a performance of the first shuffler component fails to satisfy a performance threshold;

in response to determining the performance of the first shuffler component fails to satisfy the performance threshold, configuring a second shuffler component that includes a second cache configured to receive the data set associated with the shuffle operation from the data source and provide the data set associated with the shuffle operation to the data sink;

storing a first portion of the data set received from the data source in the second cache of the second shuffler component;

providing, based on the configuration of the second shuffle component, the first portion of the data set associated with the shuffle operation from the second cache of the second shuffler component to the data sink; and

storing a second portion of the data set received from the data source in the second cache of the second shuffler component concurrently with the second shuffler component providing the first portion of the data set to the data sink from the second cache of the second shuffler component.

Assignments (2)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 4, 2019
From: ARMSTRONG, MATTHEW A.; TOLTON, MATTHEW B.; AHMADI, HOSSEIN; ENTIN, MICHAEL
To: GOOGLE INC.
Reel/Frame 048495/0466 →
ENTITY CONVERSION Recorded Mar 4, 2019
From: GOOGLE INC.
To: GOOGLE LLC
Reel/Frame 048499/0394 →
Continuity (2)
Continuation 14210998 · Mar 14, 2014
Provisional Application 61783986 · Mar 14, 2013