Consensus-based reliable messaging

• US 8,005,917 B2
• Filed: 09/30/2008
• Issued: 08/23/2011
• Est. Priority Date: 09/30/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Cooper, Brian Frank
• Primary Examiner(s): Wang; Liangche A.
• Application Number:
  US12/242,018
• Publication Number:
  US 20100082728A1
• Time in Patent Office: 1,057 Days
• Field of Search: 709/202, 709/205, 709/206, 709/208, 709213-216, 709/201, 709/223, 709/226
• US Class Current: 709/213
• CPC Class Codes: G06F 11/2041 with more than one idle spare processing component
• CPC Class Codes: G06F 11/2046 where the redundant components share persistent storage G06F11/2043 takes precedence
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: H04L 51/23 Reliability checks, e.g. acknowledgments or fault reporting
• CPC Class Codes: H04L 67/55 Push-based network services
• CPC Class Codes: H04L 67/562 Brokering proxy services

Abstract

A system includes a leader server capable of communicating with a plurality of follower servers and a network. The leader server is configured to determine when a message received from a client connected to the network has been committed to main memory in a majority of the leader and follower servers. The leader server and each of the follower servers that committed the message to main memory retain the message in main memory until requested to remove the message from main memory by a delivery agent or an archiver.

Claims

1. A system, comprising:

a first server connected to a plurality of follower servers and a network, the first server and each of the plurality of follower servers having a respective one of a plurality of main memories, the first server configured to determine when a message received from a client connected to the network has been committed to the respective one of the plurality of main memories in a predetermined number of the plurality of follower servers, wherein the first server and each of the plurality of follower servers that committed the message to the respective one of the plurality of main memories retain the message in the respective one of the plurality of main memories until requested to remove the message from the respective one of the plurality of main memories by a delivery agent or an archiver;

wherein the first server and each of the plurality of follower servers is configured to maintain a data structure in a respective one of the plurality of main memories, the data structure indicative of each one of the plurality of main memories that currently stores the message.

2. The system of claim 1, wherein the delivery agent requests the first server and each of the follower servers remove the message from the respective one of the plurality of main memories once a subscriber designated to receive the message acknowledges receipt of the message.

3. The system of claim 1, wherein the archiver requests the first server and each of the follower servers remove the message from the respective one of the plurality of main memories once the message has been stored by the archiver in an archive database.

4. The system of claim 3, wherein the delivery agent is configured to forward the message to a subscriber connected to the network by reading the message from the respective one of the plurality of main memories of any of the first server and each of the follower servers or from the archive database.

5. The system of claim 3, wherein a plurality of archivers are in communication with the first server, each of the plurality of archivers configured to store the message in a database associated with each of the plurality of archivers.

6. The method of claim 1, wherein the first server is configured to notify the plurality of follower servers of any updates to the data structure in the one of the plurality of main memories of the first server.

7. A method, comprising:

requesting by a first server that each of a plurality of follower servers commit a message to a respective one of a plurality of main memories;

determining by the first server that the message has been published when a predetermined number of the plurality of follower servers have committed the message to the respective one of the plurality of main memories of the predetermined number of the plurality of follower servers;

maintaining by the first server the message in a main memory of the first server until receiving a signal from a delivery agent or an archiver to remove the message from the main memory of the first server; and

maintaining a data structure by the first server in the main memory of the first server, the data structure identifying the servers in which the message is stored.

8. The method of claim 7, further comprising:

receiving a signal by the first server from the delivery agent to remove the message from the main memory when a subscriber designated to receive the message acknowledges receipt of the message; and

updating the data structure in the main memory of the first server by the first server to indicate that the message is no longer stored in the main memory of the first server.

9. The method of claim 7, further comprising:

receiving a signal by the first server from the archiver to remove the message from the main memory when the message has been stored by the archiver in an archive database; and

updating the data structure in the main memory of the first server by the first server to indicate that the message is no longer stored in the main memory of the first server.

10. The method of claim 7, further comprising:

updating the data structure in the main memory of the first server by the first server in response to the message being stored by the archiver.

11. The method of claim 7, further comprising:

updating the data structure in response to the message being removed from the main memory of the first server after having been delivered to a subscriber.

12. The method of claim 7, wherein each of the plurality of follower servers that committed the message to the respective one of the plurality of main memories maintain the message until receiving a signal to remove the message from the respective one of the plurality of main memories, the signal being received from a delivery agent upon delivery of the message to one or more subscribers or an archiver upon archiving of the message.

13. The method of claim 7, further comprising:

requesting by the first server that the plurality of follower servers that committed the message to the respective one of the plurality of main memories remove the message from the respective one of the plurality of main memories.

14. A non-transitory machine readable storage medium encoded program code, wherein when the program code is executed by a processor, the processor performs a method comprising:

requesting by a first server that each of a plurality of follower servers commit a message to a respective one of a plurality of main memories;

determining by the first server that the message has been published when a predetermined number of the plurality of follower servers have each committed the message to the respective one of the plurality of main memories;

maintaining by the first server the message in main memory of the first server until receiving a signal to remove the message from the main memory of the first server, the signal being received from a delivery agent or an archiver; and

maintaining by the first server a data structure in the main memory of the first server, the data structure identifying the servers in which the message is stored.

15. The non-transitory machine readable storage medium of claim 14, further comprising:

receiving by the first server a signal to remove the message from the main memory of the first server from the delivery agent when at least one subscriber designated to receive the message acknowledges receipt of the message;

removing the message from the main memory of the first server in response to the signal received from the delivery agent; and

updating the data structure in response to the message being removed from the main memory of the first server.

16. The non-transitory machine readable storage medium of claim 15, wherein each of the plurality of follower servers is configured to maintain a data structure in a respective one of the plurality of main memories, the data structure indicative of each one of the plurality of main memories that currently stores the message, the method further comprising:

notifying each of the plurality of follower servers to update the data structure in the respective one of the plurality of main memories to indicate that message is no longer stored in the main memory of the first server.

17. The non-transitory machine readable storage medium of claim 14, further comprising:

receiving a signal by the first server from the archiver to remove the message from the main memory of the first server when the message has been stored in at least one archive database by the archiver;

removing the message from the main memory of the first server in response to the signal received from the archiver; and

updating the data structure in response to the message being removed from the main memory of the first server.

18. The non-transitory machine readable storage medium of claim 17, wherein each of the plurality of follower servers is configured to maintain a data structure in a respective one of the plurality of main memories, the data structure indicative of each one of the plurality of main memories that currently stores the message, the method further comprising:

notifying each of the plurality of follower servers to update the data structure in the respective one of the plurality of main memories to indicate that message is no longer stored in the main memory of the first server.

19. The non-transitory machine readable storage medium of claim 14, wherein each of the plurality of follower servers that committed the message to the respective one of the plurality of main memories maintain the message until receiving a signal from a delivery agent or an archiver to remove the message from the respective one of the plurality of main memories.

20. The non-transitory machine readable storage medium of claim 14, wherein each of the plurality of follower servers is configured to maintain a data structure in a respective one of the plurality of main memories, the data structure indicative of each one of the plurality of main memories that currently stores the message, the method further comprising:

notifying each of the plurality of follower servers to update the data structure in the respective one of the plurality of main memories in response to a modification to the data structure in the main memory of the first server.

21. The non-transitory machine readable storage medium of claim 14, wherein each of the plurality of follower servers is configured to maintain a data structure in a respective one of the plurality of main memories, the data structure indicative of each one of the plurality of main memories that currently stores the message, the method further comprising:

receiving an update to the data structure of one of the plurality of main memories of one of the plurality of follower servers; and

in response to receiving the update, modifying the data structure in the main memory of the first server in accordance with the update and notifying other ones of the plurality of follower servers to modify the data structure in the respective one of the plurality of main memories in accordance with the update.

22. In a system that includes a plurality of respective processors each associated with a respective main memory and at least one or more archive storages and a network interface, a method comprising:

receiving a first message by at least one of the plurality of processors from a client over the network;

storing respective copies of the first message in the respective main memories associated with a selected number of the processors;

archiving at least one respective copy of the first message from at least one of the respective main memories in at least one archive storage;

removing the at least one respective copy of the first message from each of the at least one respective main memory from which a copy of the first message has been archived;

in the course of archiving, producing in each respective main memory a data structure indicative of each respective main memory and each at least one archive storage that currently stores the first message;

outputting the first message for delivery over the network to each of a multiplicity of subscribers;

removing the first message from each respective main memory and each at least one archive storage that currently contains the first message after delivery of the message to the multiplicity of subscribers; and

in the course of removing the first message after delivery of the message to the multiplicity of subscribers, referring to the data structure to determine each respective main memory and each at least one archive storage that currently contains the first message.

23. The method of claim 22 further comprising:

receiving an indication from a delivery agent that the first message has been delivered to the multiplicity of subscribers;

wherein removing the first message after delivery of the message to the multiplicity of subscribers is responsive to the received indication.