Method and system for reliable distribution of messages

• US 9,906,483 B2
• Filed: 05/20/2016
• Issued: 02/27/2018
• Est. Priority Date: 10/14/2003
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Vosshall, Peter Sven, Robbins, Alan Stuart
• Primary Examiner(s): Sison, June
• Assistant Examiner(s): NGUYEN, STEVEN C
• Application Number:
  US15/161,095
• Publication Number:
  US 20170104709A1
• Time in Patent Office: 648 Days
• CPC Class Codes: H04L 1/08 by repeating transmission, e.g. Verdan system H04L1/1858 and H04L1/189 take precedence
• CPC Class Codes: H04L 1/1642 Formats specially adapted for sequence numbers
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/54 Store-and-forward switching systems packet switching systems H04L45/00, H04L47/00
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 51/23 Reliability checks, e.g. acknowledgments or fault reporting
• CPC Class Codes: H04L 51/234 for tracking messages

Abstract

A method and system for distributing messages sent from senders to receivers in a reliable and real-time manner. Some of the receivers are designated as recording receivers that are responsible for recording each message that it receives so it can provide to other receivers messages they have missed. When a sender distributes a message, it waits for an acknowledgement from a recorder that it received and recorded the message. If an acknowledgement is received, then the sender knows at least one recorder has a copy of the message that that recorder can provide to other receivers that missed the message. When a receiver detects that it missed a message, it then initiates a “hole filling” process that distributes a request for the missing message to the recorders. A recorder who can provide the missing message sends to the requesting receiver a response indicating it can provide the missing message.

Claims

1. A computer-implemented method for managing messages transmitted between a plurality of computing devices in which at least a portion of the plurality of computing devices can be designated as receivers that receive messages from a sender and wherein at least one of the designated receivers can also be designated as a recorder, the computer-implemented method comprising:

receiving, by a recorder within a plurality of recorders, a first message sent from a sender to a set of receivers, wherein the recorder is included in the set of receivers that receive messages from the sender, and wherein the sender is configured to send a second message only when a direct acknowledgement is received from one recorder in the plurality of recorders and without waiting for an acknowledgement from any other receiver in the set of receivers;

storing, by the recorder, the first message in a message log;

transmitting, by the recorder, a direct acknowledgement to the sender that the first message was received;

transmitting, by the recorder, an indication to one or more receivers in the set of receivers regarding a set of active messages that have been received by the recorder;

receiving, by the recorder, a query from a first receiver in the set of receivers regarding an active message within the set of active messages;

in response to receiving the query, transmitting a response to the first receiver indicating that the recorder can provide the active message;

receiving, by the recorder, a request from the first receiver to provide the active message;

retrieving, by the recorder, the active message from the message log; and

transmitting, by the recorder, the active message to the first receiver.

2. The computer-implemented method of claim 1, wherein the first receiver corresponds to the plurality of recorders.

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

receiving, by the recorder, a second query from a second receiver in the set of receivers regarding messages received after a first time;

retrieving, by the recorder, one or more messages from the message log, each of the one or more messages having a timestamp after the first time; and

transmitting, by the recorder, the one or more messages to the second receiver.

4. The computer-implemented method of claim 1 further comprising periodically sending, by the recorder, information regarding messages received by the recorder to one or more receivers in the set of receivers.

5. The computer-implemented method of claim 4, wherein the information regards only messages within the set of active messages.

6. The computer-implemented method of claim 1, wherein the query is based at least in part on a determination that the first receiver has not received the active message.

7. The computer-implemented method of claim 6, wherein the determination is based at least in part on the indication regarding the set of active messages that have been received by the recorder.

8. A system for managing messages transmitted between a plurality of computing devices comprising:

a memory configured to store computer-executable instructions;

a processor in communication with the memory and a data store; and

computer-executable instructions stored in the memory, wherein the computer-executable instructions, when executed by the processor, configure the processor to;

receive, from a sender, a first message sent to a set of receivers, wherein the sender is configured to send a second message only when a direct acknowledgement is received from one receiver in the set of receivers and without waiting for an acknowledgement from any other receiver in the set of receivers;

store the first message in the data store;

transmit, to the sender, a direct acknowledgement that the first message was received;

transmit, to one or more receivers in the set of receivers, a first indication regarding a set of active messages;

receive, from a first receiver in the set of receivers, a query regarding an active message in the set of active messages; and

in response to the query, transmit the active message to the first receiver.

9. The system of claim 8, wherein the processor is further configured to add the first message to the set of active messages.

10. The system of claim 8, wherein the first indication comprises a highest sequence number of the set of active messages.

11. The system of claim 8, wherein the processor is further configured to transmit the first indication periodically.

12. The system of claim 8, wherein the set of receivers includes one or more recorders, and wherein each recorder of the one or more recorders is configured to transmit a direct acknowledgement to the sender when the recorder receives a message from the sender.

13. The system of claim 8, wherein the processor is further configured to:

receive, from a second receiver in the set of receivers, a second query regarding a set of inactive messages stored in the data store;

in response to the second query, transmit, to the second receiver, a second indication regarding the set of inactive messages;

receive, from the second receiver, a request to transmit an inactive message in the set of inactive messages;

in response to the request, retrieve the inactive message from the data store; and

transmit the inactive message to the second receiver.

14. The system of claim 13, wherein the second indication comprises a highest sequence number of the set of inactive messages.

15. The system of claim 8, wherein the set of receivers includes one or more recorders, and wherein the processor is further configured to:

receive, from a first recorder of the one or more recorders, a second indication regarding the set of active messages;

identify, based at least in part on the second indication, a missing message in the set of active messages;

transmit, to at least one of the one or more recorders, a query regarding the missing message;

receive, from a second recorder of the one or more recorders, a response indicating that the second recorder can provide the missing message;

receive, from the second recorder, the missing message; and

store the missing message in the data store.

16. A computer-implemented method for managing messages transmitted between a plurality of computing devices in which at least a portion of the plurality of computing devices can be designated as receivers that receive messages from a sender and wherein at least one of the designated receivers can also be designated as a recorder, the computer-implemented method comprising:

receiving, by a first recorder within a plurality of recorders, a first message sent from a sender, wherein a set of receivers that receive messages from the sender includes the first recorder;

adding the first message to a set of active messages;

transmitting, by the first recorder, a direct acknowledgement to the sender that the first message was received, wherein the sender is configured to send a second message in response to the direct acknowledgement without waiting for an acknowledgement from any other recorder in the plurality of recorders;

identifying a missing message within the set of active messages;

transmitting, by the first recorder, to at least one of the plurality of recorders, a query regarding the missing message;

receiving, by the first recorder, a response from a second recorder indicating that the second recorder can provide the missing message;

transmitting, by the first recorder, a request to the second recorder to provide the missing message; and

receiving, by the first recorder, the missing message.

17. The computer-implemented method of claim 16, wherein the set of receivers includes the plurality of recorders.

18. The computer-implemented method of claim 16, wherein the indication regarding the set of active messages is received from the second recorder.

19. The computer-implemented method of claim 16, wherein the indication regarding the set of active messages comprises a highest sequence number of the set of active messages.

20. The computer-implemented method of claim 19, wherein the first message is a last message received by the first recorder, and wherein identifying the missing message comprises:

determining that the highest sequence number of the set of active messages is higher than a sequence number of the last message received by the first recorder; and

identifying a message having the highest sequence number within the set of active messages as the missing message.