Data caching, distribution and request consolidation in a local network

• US 10,412,188 B2
• Filed: 09/12/2017
• Issued: 09/10/2019
• Est. Priority Date: 03/24/2014
• Status: Active Grant

• Current Assignee: Tanium Inc.
• Original Assignee: Tanium Inc.
• Inventors: Hindawi, David, Hindawi, Orion, Lippincott, Lisa, Lincroft, Peter
• Primary Examiner(s): Naji, Younes
• Application Number:
  US15/702,617
• Publication Number:
  US 20180007160A1
• Time in Patent Office: 728 Days
• Field of Search: None
• CPC Class Codes: H04L 67/1089 Hierarchical topologies
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

A data caching and distribution method, performed by a plurality of computational machines in a linear communication orbit, includes generating a data request by a first machine to request specific data, and passing the data request along a data request path that tracks the linear communication orbit until the request is received at a second machine, in the linear communication orbit, that returns the specific data in response to the data request. The method includes, at a third machine between the second machine and the first machine in the linear communication orbit, conditionally storing the specific data in a local cache of the third machine according to a data caching method.

Claims

1. A method of data caching and distribution, comprising:

at a plurality of machines that are included in a linear communication orbit, wherein the linear communication orbit includes two end nodes, comprising a head node and a tail node, and the linear communication orbit is coupled to a server via one of the two end nodes;

generating a first data request by a first machine, in the linear communication orbit, to request first specific data;

passing the first data request along a first data request path in the linear communication orbit, until the first data request is received at a second machine, in the linear communication orbit, that returns the first specific data in response to the first data request;

returning the first specific data from the second machine to the first machine, using a first data return path in the linear communication orbit that is distinct from the first data request path in the linear communication orbit;

after returning the first specific data to the first machine, continuing to send the first specific data to a plurality of additional machines in the linear communication orbit, the plurality of additional machines including a third machine and conditionally storing the first specific data in a local cache of the third machine according to a data caching method;

generating, at the first machine, a second data request to request second specific data; and

passing the second data request along a second data request path until the second data request is received at a fourth machine in the linear communication orbit that returns the second specific data in response to the second data request using a second data return path in the linear communication orbit that overlaps but is distinct from the first data return path in the linear communication orbit;

wherein;

the plurality of machines includes the first machine, the second machine, the fourth machine and the plurality of additional machines;

the machines in the plurality of machines are ordered in an ordered sequence in the linear communication orbit based on a predefined set of rules, with the first machine between the second and third machines in the ordered sequence; and

the fourth machine is distinct from the second machine.

2. The method of claim 1, wherein:

each machine of the plurality of machines has a respective machine identifier; and

the plurality of machines have self-organized into the ordered sequence in accordance with a predefined order of respective machine identifiers of the plurality of machines.

3. The method of claim 1, wherein the second machine comprises a machine, in the linear communication orbit, that has a cached copy of the first specific data in a local cache of the machine or the head node if no machine in the first data request path has a locally cached copy of the first specific data.

4. The method of claim 1, wherein the second machine comprises a machine closest, along the first data request path, to the first machine that has a cached copy of the first specific data in a local cache of said closest machine.

5. The method of claim 1, wherein passing the first data request includes passing the first data request along the first data request path that tracks the linear communication orbit until (A) the first data request is received at a machine, in the linear communication orbit, that has a cached copy of the first specific data in a local cache of the machine or (B) the first data request is received at the head node, which obtains and returns the first specific data in response to the first data request.

6. The method of claim 1, wherein the plurality of machines that are included in the linear communication orbit are interconnected by a single local area network.

7. The method of claim 1, wherein:

the data caching method comprises a statistically random method of determining whether to cache respective data received from another machine.

8. The method of claim 1, wherein the first specific data comprises one of a plurality of shards, in an object, to be cached in the linear communication orbit, and wherein the data caching method is based on at least one of a size of the first specific data, a size of the object, a size of the local cache of a respective machine, a total size of available caches in the linear communication orbit, and a total size of a data set that includes the object.

9. The method of claim 1, the method including:

combining, at the first machine, a plurality of specific data, including the first specific data and the second specific data, to generate an object for use at the first machine.

10. The method of claim 9, wherein the plurality of specific data comprise shards of said object specified in a manifest.

11. The method of claim 10, wherein generating the first data request by the first machine includes delaying generation of the first data request, with respect to time at which the manifest is received by the first machine, in accordance with a predefined request spreading method.

12. The method of claim 1, wherein the method further comprising:

generating at the third machine a third data request to request the first specific data; and

in accordance with a determination that predefined criteria in a request consolidation method are satisfied, forgoing passing the third data request along at least a part of a respective data request path that is associated with the third data request.

13. The method of claim 12, wherein the first machine consolidates the first and third data requests, and forgoes passing the third data request along the at least a part of a respective data request path that is associated with the third data request.

14. The method of claim 13, further comprising:

determining that the predefined criteria in the request consolidation method is satisfied, including determining at the first machine that the third data request has been received and processed during a predetermined period of time with respect to the first data request.

15. The method of claim 1, wherein the first specific data comprises one of a plurality of shards of an object, and the object is one of a group consisting of a software application, software application update, database, and database update.

16. The method of claim 1, further comprising:

passing the first specific data from the second machine to the first machine through a plurality of intervening machines in the linear communication orbit; and

at each machine of the plurality of intervening machines, located between the second machine and the first machine, caching a copy of the first specific data in a local cache of the machine if predefined local caching criteria are met.

17. The method of claim 1, further comprising:

passing the first specific data from the second machine to the first machine through a plurality of intervening machines in the linear communication orbit and continuing to pass the first specific data to the plurality of additional machines in the linear communication orbit until the first specific data are received by one of the end nodes; and

at each machine of a plurality of machines, selected from the plurality of intervening machines and the plurality of additional machines, caching a copy of the first specific data in a local cache in accordance with a determination that predefined local caching criteria are met.

18. The method of claim 17, wherein the second machine is a downstream machine between the first machine and the tail node, the first data request being passed downstream from the first machine to the second machine, the first specific data being returned upstream from the second machine to the first machine.

19. The method of claim 17, wherein the second machine is an upstream machine between the first machine and the head node, the first data request being passed from the first machine downstream to the tail node and upstream to the second machine, the first specific data being returned downstream from the second machine to the first machine.

20. The method of claim 17, wherein the second machine is the tail node or the head node, the first specific data being returned from the second machine to the first machine and conditionally stored in the plurality of machines, including the third machine, that are coupled within the linear communication orbit and do not have the first specific data.

21. The method of claim 1, wherein the linear communication orbit is organized from the plurality of machines based on a set of rules at a first time and subject to changes in configuration and membership when one or more machines join or exit the linear communication orbit.

22. A system, comprising:

one or more processors included in a plurality of machines;

memory having instructions stored thereon, which when executed by the one or more processors cause the one or more processors to perform operations comprising;

at the plurality of machines, which are included in a linear communication orbit, wherein the linear communication orbit terminates at two end nodes, comprising a head node and a tail node, and the linear communication orbit is coupled to a server via one of the two end nodes;

generating a first data request by a first machine, in the linear communication orbit, to request first specific data;

passing the first data request along a first data request path in the linear communication orbit, until the first data request is received at a second machine, in the linear communication orbit, that returns the first specific data in response to the first data request;

returning the first specific data from the second machine to the first machine, using a first data return path in the linear communication orbit that is distinct from the first data request path in the linear communication orbit;

after returning the first specific data to the first machine, continuing to send the first specific data to a plurality of additional machines in the linear communication orbit, the plurality of additional machines including a third machine and conditionally storing the first specific data in a local cache of the third machine according to a data caching method;

generating, at the first machine, a second data request to request second specific data; and

passing the second data request along a second data request path until the second data request is received at a fourth machine in the linear communication orbit that returns the second specific data in response to the second data request using a second data return path in the linear communication orbit that overlaps but is distinct from the first data return path in the linear communication orbit;

wherein;

the plurality of machines includes the first machine, the second machine, the fourth machine and the plurality of additional machines;

the machines in the plurality of machines are ordered in an ordered sequence in the linear communication orbit based on a predefined set of rules, with the first machine between the second and third machines in the ordered sequence; and

the fourth machine is distinct from the second machine.

23. The system of claim 22, wherein:

each machine of the plurality of machines has a respective machine identifier; and

the plurality of machines have self-organized into the ordered sequence in accordance with a predefined order of respective machine identifiers of the plurality of machines.

24. The system of claim 22, wherein the second machine comprises a machine, in the linear communication orbit, that has a cached copy of the first specific data in a local cache of the machine or the head node if no machine in the first data request path has a locally cached copy of the first specific data.

25. The system of claim 22, wherein the second machine comprises a machine closest, along the first data request path, to the first machine that has a cached copy of the first specific data in a local cache of said closest machine.

26. The system of claim 22, wherein passing the first data request includes passing the first data request along the first data request path that tracks the linear communication orbit until (A) the first data request is received at a machine, in the linear communication orbit, that has a cached copy of the first specific data in a local cache of the machine or (B) the first data request is received at the head node, which obtains and returns the first specific data in response to the data request.

27. The system of claim 22, wherein the plurality of machines that are included in the linear communication orbit are interconnected by a single local area network.

28. The system of claim 22, wherein:

the data caching method comprises a statistically random method of determining whether to cache respective data received from another machine.

29. The system of claim 22, wherein the first specific data comprises one of a plurality of shards, in an object, to be cached in the linear communication orbit, and wherein the data caching method is based on at least one of a size of the first specific data, a size of the object, a size of the local cache of a respective machine, a total size of available caches in the linear communication orbit, and a total size of a data set that includes the object.

30. The system of claim 22, wherein the instructions stored in the memory include instructions for:

combining, at the first machine, a plurality of specific data, including the first specific data and the second specific data, to generate an object for use at the first machine.

31. The system of claim 23, wherein the plurality of specific data comprises shards of said object specified in a manifest.

32. The system of claim 31, wherein generating the first data request by the first machine includes delaying generation of the first data request, with respect to time at which the manifest is received by the first machine, in accordance with a predefined request spreading method.

33. The system of claim 22, wherein the instructions stored in the memory include instructions for:

generating at the third machine a third data request to request the first specific data; and

in accordance with a determination that predefined criteria in a request consolidation method are satisfied, forgoing passing the third data request along at least a part of a respective data request path that is associated with the third data request.

34. The system of claim 33, wherein the first machine consolidates the first and third data requests, and forgoes passing the third data request along the at least a part of a respective data request path that is associated with the third data request.

35. The system of claim 34, wherein the instructions stored in the memory include instructions for:

determining that the predefined criteria in the request consolidation method is satisfied, including determining at the first machine that the third data request has been received and processed during a predetermined period of time with respect to the first data request.

36. The system of claim 22, wherein the first specific data comprises one of a plurality of shards of an object, and the object is one of a group consisting of a software application, software application update, database, and database update.

37. The system of claim 22, wherein the instructions stored in the memory include instructions for:

passing the first specific data from the second machine to the first machine through a plurality of intervening machines in the linear communication orbit; and

at each machine of the plurality of intervening machines, located between the second machine and the first machine, caching a copy of the first specific data in a local cache of the machine if predefined local caching criteria are met.

38. The system of claim 22, wherein the instructions stored in the memory include instructions for:

passing the first specific data from the second machine to the first machine through a plurality of intervening machines in the linear communication orbit and continuing to pass the first specific data to the plurality of additional machines in the linear communication orbit until the first specific data are received by one of the end nodes; and

at each machine of a plurality of machines, selected from the plurality of intervening machines and the plurality of additional machines, caching a copy of the first specific data in a local cache in accordance with a determination that predefined local caching criteria are met.

39. The system of claim 38, wherein the second machine is a downstream machine between the first machine and the tail node, the first data request being passed downstream from the first machine to the second machine, the first specific data being returned upstream from the second machine to the first machine.

40. The system of claim 38, wherein the second machine is an upstream machine between the first machine and the head node, the first data request being passed from the first machine downstream to the tail node and upstream to the second machine, the first specific data being returned downstream from the second machine to the first machine.

41. The system of claim 38, wherein the second machine is the tail node or the head node, the first specific data being returned from the second machine to the first machine and conditionally stored in the plurality of machines, including the third machine, that are coupled within the linear communication orbit and do not have the first specific data.

42. The system of claim 22, wherein the linear communication orbit is organized from the plurality of machines based on a set of rules at a first time and subject to changes in configuration and membership when one or more machines join or exit the linear communication orbit.