Method and system for reliable distribution of messages

Patent metadata

Field	Value
Publication number	US-9906483-B2
Application number	US-201615161095-A
Country	US
Kind code	B2
Filing date	May 20, 2016
Priority date	Oct 14, 2003
Publication date	Feb 27, 2018
Grant date	Feb 27, 2018

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.

First claim

We claim:

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 me

Assignees

• Amazon Tech Inc

Inventors

• Vosshall Peter Sven
• Robbins Alan Stuart

Classifications

• H04L43/106

  using time related information in packets, e.g. by adding timestamps · CPC title

• H04L51/30 Primary

  Electricity · mapped topic

• H04L12/18

  for broadcast or conference {, e.g. multicast} · CPC title

• H04L1/1642

  Formats specially adapted for sequence numbers · CPC title

• H04L1/08

  by repeating transmission, e.g. Verdan system {(H04L1/1858 and H04L1/189 take precedence)} · CPC title