Method and system for reliable distribution of messages

• US 9,350,565 B1
• Filed: 10/14/2003
• Issued: 05/24/2016
• 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 Stewart
• Primary Examiner(s): Sison, June
• Assistant Examiner(s): Nguyen, Steven
• Application Number:
  US10/685,729
• Time in Patent Office: 4,606 Days
• Field of Search: 709/206
• US Class Current: 1/1
• 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 method in a computing system for distributing messages to a set of receivers, the method comprising:

for each of the messages,

distributing the message to the set of receivers, wherein at least one receiver in the set of receivers corresponds to a recorder, wherein the recorder records each message received, and provides to at least one of the other receivers in the set of receivers any message not successfully received by the at least one of the other receivers in the set of receivers;

after distributing the message to the set of receivers, waiting for a direct acknowledgement of receipt of the message from the recorder, wherein the direct acknowledgment includes a communication from the recorder confirming receipt of the message;

only when a direct acknowledgement from the recorder is received, and without waiting for receipt of an acknowledgement from any other receiver, proceeding to distribute another message; and

when a direct acknowledgement from the recorder is not received within a predetermined period of time, indicating a failure to distribute the message, and redistributing the message.

2. The method of claim 1 wherein each message is identified by batch identifier and sequence number within a batch and when the direct acknowledgement from the recorder is not received, the method further comprises generating a new batch identifier for distributing a subsequent message.

3. The method of claim 1 wherein each message is organized into a batch wherein a batch is terminated when receipt of a message of the batch is not directly acknowledged from a recorder.

4. The method of claim 1 wherein each message is organized into a batch representing a sequence of distributed messages whose receipt is directly acknowledged by the recorder.

5. The method of claim 1 wherein a subsequent message is distributed only after receiving the direct acknowledgement of receipt by the recorder of a last message that was distributed.

6. The method of claim 1 wherein the set of receivers corresponds to multiple recorders and wherein waiting for the direct acknowledgement of receipt of the message from the recorder includes waiting for a direct acknowledgement of receipt of the message from one of the multiple recorders.

7. The method of claim 6 wherein waiting for the direct acknowledgement of receipt of the message from the recorder includes waiting for a direct acknowledgement of receipt of the message from at least two of the multiple recorders.

8. The method of claim 6 wherein a receiver that did not receive a message identifies the recorder that is to provide the message.

9. The method of claim 8 wherein the receiver identifies the recorder by distributing a request to multiple recorders.

10. The method of claim 9 wherein the receiver distributes the request via broadcast.

11. The method of claim 9 wherein the receiver distributes the request via multicast.

12. The method of claim 8 wherein the identified recorder sends the message via unicast.

13. The method of claim 8 wherein the receiver that identifies a recorder is also a recorder.

14. The method of claim 1 wherein each message is distributed via broadcast.

15. The method of claim 1 wherein each message is distributed via multicast.

16. The method of claim 1 wherein each message is distributed via unicast.

17. A method in a computing system for distributing messages, the method comprising:

distributing a message to a set of receivers, wherein at least one of the receivers corresponds to a recorder of sent messages, wherein the recorder sends a communication to a sender confirming receipt of the message;

after distributing the message to the set of receivers, waiting for a direct acknowledgement of receipt of the message from one recorder;

only when a direct acknowledgement from one recorder is received, and without waiting for receipt of an acknowledgement from any other receiver in the set of receivers, proceeding to distribute another message; and

when a direct acknowledgement from one recorder is not received within a predetermined period of time, indicating a failure to distribute the message, and redistributing the message.

18. The method of claim 17 wherein a receiver detects that it has not received a message.

19. The method of claim 17 wherein the sender distributes messages via multicasting.

20. The method of claim 17 wherein the sender distributes messages via broadcasting.

21. The method of claim 18 wherein the receiver sends a request for a recorder who can provide the message via multicasting.

22. The method of claim 21 wherein the receiver sends the request that the recorder provide the message via unicasting.

23. The method of claim 22 wherein the recorder that is to provide the message sends the message via unicasting.

24. The method of claim 17 wherein the sender distributes a message only after an acknowledgement that the last sent message has been received by a recorder.

25. The method of claim 17 wherein the messages are distributed in order and when a message is received out of order, a receiver detects that it is missing a message.

26. The method of claim 25 wherein each message has a sequence number.

27. The method of claim 25 wherein the messages are sequential within a batch.

28. The method of claim 17 wherein each message has a timestamp and a receiver performs a recovery of messages by:

sending to at least one recorder a request to provide messages with a timestamp after a specified time to respond; and

after receiving from a recorder a response;

sending to the recorder a request that the recorder is to provide the messages; and

receiving from the recorder the messages.

29. The method of claim 28 wherein the receiver during recovery also requests from a recorder an indication of messages received by the recorder at the specified time.

30. The method of claim 28 wherein the messages received during recovery are grouped into multiple communications.

31. The method of claim 28 wherein recovery occurs at receiver initialization.

32. The method of claim 17 wherein each message has a timestamp and a receiver requests a recorder to provide messages with a timestamp after the time specified by the receiver.

33. A method in a computing system of a receiver for receiving messages comprising:

receiving from a sender messages, each message having a sequence indicator;

receiving from a recorder, wherein a recorder is solely responsible for acknowledging and recording each message received from the sender and for providing to at least one receiver any message not successfully received by the at least one receiver, a notification including an indication of the last active message received by the recorder; and

after receiving a message from the sender,

determining whether any message has been missed based on the sequence indicator of the received message from the sender and the notification received by the recorder; and

when an active message has been missed,

identifying a recorder who can provide the missed active message;

requesting the identified recorder to provide an indication that the missed active message may be provided; and

when receiving, within a predetermined time period, the indication from the identified recorder indicating that the missed active message can be provided, sending to the identified recorder a request that the recorder provide the missed active message; and

receiving the missed active message from the recorder;

when not receiving, within the predetermined time period, the indication from the identified recorder indicating that the missed active message can be provided, sending to at least one other recorder another request for a recorder to respond who can provide the missed active message.

34. The method of claim 33 wherein the received messages are provided to an application.

35. The method of claim 33 wherein the receiver that receives the messages is also a recorder.

36. The method of claim 33 further comprising:

periodically receiving from a recorder an indication of a highest sequence number of a message received by the recorder; and

determining based on the received indication whether any messages are missing.

37. The method of claim 33 further comprising requesting a recorder to provide messages with a timestamp after a time specified by the receiver.

44. The method of claim 33, wherein the method further comprises receiving from a recorder a notification including an indication of the last inactive message received by the recorder.

38. A system for distributing messages to a set of receivers, comprising:

a hardware computing system including a memory and a processor in communication with the memory, the processor configured to execute specific computer-executable instructions to provide;

a component implemented on the hardware computing system, wherein the component sends messages to the set of receivers and the component, after sending a message, waits for a direct acknowledgement of receipt of the message from one receiver in the set of receivers that is designated as a recorder, does not wait for an acknowledgment of receipt of the message from any other receiver in the set of receivers, and sends a subsequent message, and wherein the recorder records messages received and provides to at least one other receiver in the set of receivers any messages not successfully received by the at least one other receiver; and

a component implemented on the hardware computing system, wherein the component, when the direct acknowledgement from the recorder is not received within the predetermined period of time, indicates a failure to distribute the message, and redistributes the message.

39. The system of claim 38 wherein the messages are identified by batch identifier and sequence number within a batch and when the direct acknowledgement from the recorder is not received, a new batch identifier for distributing subsequent messages is generated.

40. The system of claim 38 wherein messages are organized into batches, wherein a batch is terminated when receipt of a message of the batch is not directly acknowledged.

41. The system of claim 38 wherein multiple receivers are recorders and wherein waiting for the direct acknowledgment comprises waiting for a direct acknowledgement from at least two recorders.

42. The system of claim 41 wherein a receiver that did not receive a message identifies the recorder from the at least two recorders that is to provide the message.

43. The system of claim 38 wherein the receiver that identifies a recorder is also a recorder.