Reliable map-reduce communications in a decentralized, self-organizing communication orbit of a distributed network

• US 9,910,752 B2
• Filed: 04/22/2016
• Issued: 03/06/2018
• Est. Priority Date: 04/24/2015
• Status: Active Grant

• Current Assignee: Tanium Inc.
• Original Assignee: Tanium Inc.
• Inventors: Lippincott, Lisa, Hindawi, David, Hindawi, Orion, Lincroft, Peter
• Primary Examiner(s): Bonzo, Bryce P
• Assistant Examiner(s): Arcos, Jeison C
• Application Number:
  US15/136,790
• Publication Number:
  US 20160314037A1
• Time in Patent Office: 683 Days
• CPC Class Codes: G06F 11/00 Error detection; Error correction; Monitoring error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/0757 by exceeding a time limit, i.e. time-out, e.g. watchdogs
• CPC Class Codes: G06F 11/30 Monitoring
• CPC Class Codes: H04L 43/0864 Round trip delays

Abstract

Method and system for providing message communications with failure detection and recovery are disclosed. At a respective node of a non-static collection of nodes forming a linear communication orbit: the node identifies, from among the non-static collection of nodes, a set of forward contacts distributed in a forward direction along the linear communication orbit; the node monitors a propagation state of a first query that has departed from the respective node to travel in the forward direction along the linear communication orbit; and upon detecting a propagation failure of the first query based on the monitoring, the node sends the first query directly to a first forward contact among the set of forward contacts to initiate a failure recovery process within at least part of a segment of the linear communication orbit between the respective node and the first forward contact of the respective node.

Claims

1. A method of providing message communications with failure detection and recovery in a linear communication orbit formed by a non-static collection of machines, the method comprising:

at a respective machine of the non-static collection of machines forming the linear communication orbit;

identifying, from among the non-static collection of machines, a respective set of forward contacts that comprises a set of machines distributed in a forward direction along the linear communication orbit;

monitoring a respective propagation state of a first query that has departed from the respective machine to travel in the forward direction along the linear communication orbit, wherein the monitoring includes updating the respective propagation state of the first query based on a predetermined timeout for the respective propagation state; and

upon detecting a respective propagation failure of the first query based on the monitoring, sending the first query directly to a first forward contact among the set of forward contacts to initiate a respective failure recovery process within at least part of a respective segment of the linear communication orbit between the respective machine and the first forward contact of the respective machine.

2. The method of claim 1, wherein the first forward contact is the closest live forward contact to the respective machine among the set of forward contacts that is within an unanswered range of the first query on the linear communication orbit.

3. The method of claim 1, wherein sending the first query directly to the first forward contact among the set of forward contacts further comprises:

sending the first query directly to the first forward contact among the set of forward contacts after a respective attempt to send the first query directly to each forward contact located closer to the respective machine than the first forward contact has failed.

4. The method of claim 1, further comprising:

determining a respective responsibility tier of the respective machine for the first query based on a predetermined responsibility hierarchy rule, wherein the predetermined responsibility hierarchy rule assigns the non-static collection of machines into a respective responsibility hierarchy for the first query; and

determining whether the first query has reached beyond a respective responsibility range of the respective machine for the first query based on the respective responsibility tier of the respective machine for the first query.

5. The method of claim 4, wherein monitoring the respective propagation state of the first query further comprises:

putting the first query into at least one of a series of forward states corresponding to the responsibility tier of the respective machine for the first query based on a new known position of the first query in the linear communication orbit.

6. The method of claim 4, wherein monitoring the respective propagation state of the first query further comprises:

putting the first query into at least one of a series of forward states corresponding to the responsibility tier of the respective machine for the first query based on a failure to receive an acknowledgement associated with a lower forward state than the at least one forward state within a predetermined timeout period.

7. The method of claim 4, further comprising:

identifying, from among the non-static collection of machines, a respective set of backward contacts in a backward direction along the linear communication orbit;

receiving a second query from a first backward contact among the respective set of backward contacts, the second query having a respective propagation state indicating a respective propagation failure of the second query between the first backward contact of the respective machine and a machine positioned between the first backward contact and the respective machine in the linear communication orbit; and

in response to receiving the second query, sending the second query directly to a second backward contact among the set of backward contacts to recover from the respective propagation failure of the second query, wherein the second backward contact is located between the respective machine and the first backward contact in the linear communication orbit, and wherein the second backward contact resumes propagation of the second query within at least part of a respective segment of the linear communication orbit between the second backward contact and the respective machine.

8. The method of claim 7, further comprising:

determining a respective responsibility tier of the respective machine for the second query based on the predetermined responsibility hierarchy rule, wherein the predetermined responsibility hierarchy rule assigns the non-static collection of machines into a respective responsibility hierarchy for the second query, wherein the respective responsibility hierarchies of the first query and the second query are different from each other.

9. The method of claim 7, wherein sending the second query directly to the second backward contact among the set of backward contacts further comprises:

identifying the farthest live backward contact among the set of backward contacts that is within a respective unanswered range of the second query.

10. The method of claim 7, wherein sending the second query directly to the second backward contact among the set of backward contacts further comprises:

sending the second query directly to the farthest live backward contact among the set of backward contacts after a respective attempt to send the second query directly to each backward contact located farther away from the respective machine than said farthest live backward contact has failed.

11. The method of claim 10, further comprising:

putting the second query into at least one of a series of backward states corresponding to the respective responsibility tier of the respective machine for the second query based on a new known position of the second query within the respective segment of the linear communication orbit between the second backward contact and the machine.

12. The method of claim 10, further comprising:

putting the second query into at least one of a series of backward states corresponding to the respective responsibility tier of the respective machine for the second query based on a failure to receive more answers for the second query for the respective segment of the linear communication orbit between the second backward contact and the respective machine within a predetermined timeout period.

13. The method of claim 7, wherein the respective predetermined responsibility hierarchy rule assigns the non-static collection of machines into the respective responsibility hierarchy for the first query based on a similarity between a predetermined characteristic of the first query and a respective corresponding characteristic assigned to each machine of the non-static collection of machines.

14. The method of claim 13, wherein the set of forward contacts are distributed along the linear communication orbit in the forward direction away from the respective machine in an order of increasing similarity between the respective corresponding characteristic assigned to the respective machine and the respective corresponding characteristic assigned to each of the set of forward contacts.

15. The method of claim 14, wherein the set of backward contacts are distributed along the linear communication orbit in the backward direction away from the respective machine in an order of increasing similarity between the respective corresponding characteristic assigned to the respective machine and the respective corresponding characteristic assigned to each of the set of backward contacts.

16. The method of claim 15, wherein the respective machine and each machine in the sets of backward and forward contacts for the respective machine identify each other as a direct contact based on a common contact selection rule implemented by the respective machine and said each machine.

23. The method of claim 1, wherein the predetermined timeout for the respective propagation state is established in accordance with an estimated round-trip latency between the respective machine and another machine along the linear communication orbit.

17. A non-transitory computer-readable medium, having instructions stored thereon, which when executed by one or more processors cause the processors to perform operations comprising:

at a respective machine of a non-static collection of machines forming a linear communication orbit;

identifying, from among the non-static collection of machines, a respective set of forward contacts that comprises a set of machines distributed in a forward direction along the linear communication orbit;

monitoring a respective propagation state of a first query that has departed from the respective machine to travel in the forward direction along the linear communication orbit, wherein the monitoring includes updating the respective propagation state of the first query based on a predetermined timeout for the respective propagation state; and

upon detecting a respective propagation failure of the first query based on the monitoring, sending the first query directly to a first forward contact among the set of forward contacts to initiate a respective failure recovery process within at least part of a respective segment of the linear communication orbit between the respective machine and the first forward contact of the respective machine.

18. The computer-readable medium of claim 17, wherein the first forward contact is the closest live forward contact to the respective machine among the set of forward contacts that is within an unanswered range of the first query on the linear communication orbit.

19. The computer-readable medium of claim 17, wherein sending the first query directly to the first forward contact among the set of forward contacts further comprises sending the first query directly to the first forward contact among the set of forward contacts after a respective attempt to send the first query directly to each forward contact located closer to the respective machine than the first forward contact has failed.

20. A system, comprising:

one or more processors; and

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

at a respective machine of a non-static collection of machines forming a linear communication orbit;

identifying, from among the non-static collection of machines, a respective set of forward contacts that comprises a set of machines distributed in a forward direction along the linear communication orbit;

monitoring a respective propagation state of a first query that has departed from the respective machine to travel in the forward direction along the linear communication orbit, wherein the monitoring includes updating the respective propagation state of the first query based on a predetermined timeout for the respective propagation state; and

upon detecting a respective propagation failure of the first query based on the monitoring, sending the first query directly to a first forward contact among the set of forward contacts to initiate a respective failure recovery process within at least part of a respective segment of the linear communication orbit between the respective machine and the first forward contact of the respective machine.

21. The system of claim 20, wherein the first forward contact is the closest live forward contact to the respective machine among the set of forward contacts that is within an unanswered range of the first query on the linear communication orbit.

22. The system of claim 20, wherein sending the first query directly to the first forward contact among the set of forward contacts further comprises sending the first query directly to the first forward contact among the set of forward contacts after a respective attempt to send the first query directly to each forward contact located closer to the respective machine than the first forward contact has failed.