Dynamic application instance discovery and state management within a distributed system

• US 9,838,240 B1
• Filed: 11/18/2013
• Issued: 12/05/2017
• Est. Priority Date: 12/29/2005
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Cormie, John David, Fischman, Ami K., Vermeulen, Allan H.
• Primary Examiner(s): Jakovac, Ryan
• Application Number:
  US14/082,728
• Time in Patent Office: 1,478 Days
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0667 at data level, e.g. file, record or object virtualisation
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

Dynamic application instance discovery and state management within a distributed system. A distributed system may implement application instances configured to perform one or more application functions within the distributed system, and discovery and failure detection daemon (DFDD) instances, each configured to store an indication of a respective operational state of each member of a respective group of the number of application instances. Each of the DFDD instances may repeatedly execute a gossip-based synchronization protocol with another one of the DFDD instances, where execution of the protocol between DFDD instances includes reconciling differences among membership of the respective groups of application instances. A new application instance may be configured to notify a particular DFDD instance of its availability to perform an application function. The particular DFDD instance may be configured to propagate the new instance'"'"'s availability to other DFDD instances via execution of the synchronization protocol, without intervention on the part of the new application instance.

Claims

1. A distributed system, comprising:

a plurality of computing devices configured to implement;

a plurality of application instances configured to perform functions of the distributed system, wherein the plurality of application instances includes two or more different types of application instances, each type of application instance configured to perform one or more different functions of the distributed system; and

a plurality of discovery and failure detection daemon (DFDD) instances, wherein the plurality of DFDD instances are configured to store operational state information for the plurality of application instances, wherein the state information includes global state information common to all types of application instances and specific state information specific to at least one type of application instance and wherein at least one of the DFDD instances is configured to update the global state information according to a global state machine defining transitions between a plurality of global states including a state indicating the respective application instance is newly online, a state indicating the respective application instance is operating normally, a state indicating the respective application instance has lost communication with a respective DFDD instance, a state indicating the respective application instance has failed, and a state indicating the respective application instance is subject to a network split, according to one or more status reports received from the respective application instance;

wherein at least one of the plurality of DFDD instances is configured to repeatedly execute a peer-to-peer, gossip-based synchronization protocol with a peer instance of the DFDD instances, wherein the peer instance is randomly or pseudorandomly selected from among the plurality of DFDD instances, and wherein to execute the protocol, the peer DFDD instances are configured to exchange state information for at least one of the plurality of application instances including both the global state information and the specific state information.

2. The distributed system as recited in claim 1, wherein the state information for a given application instance includes information indicating a physical location of the application instance in the distributed system.

3. The distributed system as recited in claim 1, wherein at least a respective application instance of the plurality of application instances is configured to report its status to a DFDD instance at regular or irregular intervals, wherein the DFDD instance is configured to update global state information according to status reports of the application instance.

4. The distributed system as recited in claim 1, wherein each DFDD instance is one of a daemon process configured to operate within an operating system environment or an autonomous hardware or software agent configured to operate independently from an operating system environment.

14. The distributed system as recited in claim 1, wherein at least one of the plurality of DFDD instances is configured to monitor its own operational state.

15. The distributed system as recited in claim 1, wherein at least a respective application instance of the plurality of application instances is configured to report its status to a DFDD instance at regular or irregular intervals.

16. The distributed system as recited in claim 15, wherein a status report to be reported to the DFDD instance at regular or irregular intervals comprises an application identification (ID) corresponding to the respective application instance.

5. A method, comprising:

storing, by a plurality of discovery and failure detection daemon (DFDD) instances implemented on a plurality of computing devices, state information for a plurality of application instances configured to perform functions of a distributed system, wherein the plurality of application instances includes two or more different types of application instances, each type of application instance configured to perform one or more different functions of the distributed system, wherein the state information includes global state information common to all types of application instances and specific state information specific to at least one type of application and wherein the state information includes global state information according to a global state machine defining transition between a plurality of global states including a state indicating a respective application instance is newly online, a state indicating the respective application instance is operating normally, a state indicating the respective application instance has lost communication with a respective DFDD instance, a state indicating the respective application instance has failed, and a state indicating the respective application instance is subject to a network split, according to status reports of the application instance;

randomly or pseudorandomly selecting, by at least one of the plurality of DFDD instances, a peer instance of the plurality of DFDD instances; and

communicating, by the at least one of the plurality of DFDD instances, state information for one or more of the plurality of application instances to the other DFDD instance according to a peer-to-peer synchronization protocol, the state information including both the global state information and the specific state information.

6. The method as recited in claim 5, further comprising iteratively performing the selecting and the communicating.

7. The method as recited in claim 5, wherein the synchronization protocol is a gossip-based synchronization protocol.

8. The method as recited in claim 5, wherein, in the communicating, the at least one of the plurality of DFDD instances exchanges state information for the one or more of the plurality of application instances with the other DFDD instance according to the synchronization protocol.

9. The method as recited in claim 5, wherein the state information for a given application instance includes information for accessing the application instance by clients, the information including an Internet Protocol (IP) address and port number through which a client can establish a connection with the application instance of the distributed system.

10. The method as recited in claim 5, wherein the state information for a given application instance includes information indicating a physical location of the application instance in the distributed system.

11. The method as recited in claim 5, further comprising one or more of the application instances each periodically or aperiodically reporting its status to at least one of the plurality of DFDD instances, wherein the global state information for the respective application instance is updated according to the reported status.

12. The method as recited in claim 5, wherein the selecting and the communicating are performed among two or more of the plurality of DFDD instances that are configured to store state information for a respective group of the plurality of application instances.

17. The method of claim 5, further comprising monitoring, by at least one of the plurality of DFDD instances, its own operational state.

13. A non-transitory computer-accessible storage medium storing instructions that when executed by a computer implement a discovery and failure detection daemon (DFDD) configured to:

store operational state information for at least one of a plurality of application instances configured to perform functions of a distributed system, wherein the plurality of application instances includes two or more different types of application instances, each type of application instance configured to perform one or more different functions of the distributed system, wherein the state information includes global state information common to all types of application instances and specific state information specific to at least one type of application and wherein the state information includes global state information according to a global state machine defining transition between a plurality of global states including a state indicating a respective application instance is newly online, a state indicating the respective application instance is operating normally, a state indicating the respective application instance has lost communication with a respective DFDD instance, a state indicating the respective application instance has failed, and a state indicating the respective application instance is subject to a network split, according to status reports of the respective application instance; and

iteratively perform;

randomly or pseudorandomly select a peer DFDD instance from among a plurality of DFDD instances; and

execute a peer-to-peer, gossip-based protocol with the other peer instances of the DFDD instances, wherein to execute the protocol, the peer DFDD instances are configured to exchange state information for at least one of the plurality of application instances in the distributed system, the state information including both the global state information and the specific state information.

18. The non-transitory computer-accessible storage medium of claim 13, wherein the DFDD is further configured to monitor its own operational state.

19. The non-transitory computer-accessible storage medium of claim 13, wherein the DFDD is further configured to receive, from at least a respective application instance of the plurality of application instances, a status report of the respective application instance at regular or irregular intervals.

20. The non-transitory computer-accessible storage medium of claim 19, wherein the status report received by the DFDD at regular or irregular intervals comprises an application identification (ID) corresponding to the respective application instance and a status of the respective application instance.