Eventually-consistent data stream consolidation

• US 8,705,537 B1
• Filed: 06/10/2012
• Issued: 04/22/2014
• Est. Priority Date: 06/10/2012
• Status: Active Grant

• Current Assignee: Jolly Seven, Series 70 of Allied Security Trust I (Allied Security Trust)
• Original Assignee: Andrei Teodor Borac
• Inventors: Borac, Andrei Teodor
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Boakye, Alexander O
• Application Number:
  US13/492,914
• Time in Patent Office: 681 Days
• Field of Search: 370/394, 370/389, 370/471, 370/412, 370/413, 370/395.71, 370/395.7, 370/428, 370/432, 370/474, 370/473, 370/312, 370/349, 709/224, 709/232, 709/247, 714/2, 714/15
• US Class Current: 370/394
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems

Abstract

One embodiment of a computer-implemented method for eventually-consistent data stream consolidation comprises associating an application-generated undo record with each packet and supplying undo records to the application in order to rewind the application state prior to effecting a merge operation on the packet stream. Other embodiments are described.

Claims

1. A computer-implemented method for updating the state of an application logic to reflect a plurality of update packets entering a local packet stream, each of said plurality of update packets having a packet timestamp, said local packet stream comprising a first plurality of local packets, each of said first plurality of local packets having a packet timestamp, the method comprising:

(a) calculating an overwrite point, said overwrite point calculated to precede any location in said local packet stream at which one of said plurality of update packets is to be inserted;

(b) supplying, to said application logic, a first plurality of undo records, each of said first plurality of undo records having previously been elicited by one of a second plurality of local packets, each of said second plurality of local packets being after said overwrite point in said local packet stream;

(c) executing a merge operation, said merge operation interleaving said plurality of update packets amongst said second plurality of local packets, said merge operation arranging packets in order of increasing packet timestamp, said merge operation eliminating duplicate packets, said merge operation resulting in an updated local packet stream comprising a third plurality of local packets;

(d) supplying, to said application logic, a fourth plurality of local packets, each of said fourth plurality of local packets being one of said third plurality of local packets, each of said fourth plurality of local packets being after said overwrite point in said updated local packet stream;

(e) obtaining, from said application logic, a second plurality of undo records, each of said second plurality of undo records having been elicited by one of said fourth plurality of local packets.

2. The method of claim 1, wherein each packet timestamp is calculated as a combination of a clock value and a packet checksum.

3. The method of claim 2, wherein said clock value is the output of a Lamport clock, and said packet checksum is obtained by applying a collision-resistant hash function to the contents of a packet.

4. The method of claim 1, wherein and the method further comprises:

(a) storing each of said second plurality of undo records in an undo record storage location logically associated with the packet that elicited the undo record.

5. The method of claim 4, wherein said first plurality of local packets is stored in a virtual file and the method further comprises:

(a) supplying, to said application logic, a list of virtual file offsets, each of said list of virtual file offsets indicating the location, in said virtual file, of one of said fourth plurality of local packets;

(b) supplying, upon receiving a read request from said application logic, to said application logic, a packet, said read request incorporating a virtual file offset, said packet being loaded from said virtual file offset of said virtual file.

6. The method of claim 5, wherein each packet timestamp is calculated as a combination of a clock value and a packet checksum.

7. The method of claim 6, wherein said clock value is the output of a Lamport clock, and said packet checksum is obtained by applying a collision-resistant hash function to the contents of a packet.

8. The method of claim 5, wherein the method further comprises:

(a) supplying, to said application logic, a first plurality of redo records, each of said first plurality of redo records having previously been elicited by one of said fourth plurality of local packets;

(b) obtaining, from said application logic, a second plurality of redo records, each of said second plurality of redo records being elicited by one of said fourth plurality of local packets;

(c) storing each of said second plurality of redo records in a redo record storage location logically associated with the packet eliciting the redo record.

9. The method of claim 1, wherein the method further comprises:

(a) supplying, to said application logic, a first plurality of redo records, each of said first plurality of redo records having previously been elicited by one of said fourth plurality of local packets;

(b) obtaining, from said application logic, a second plurality of redo records, each of said second plurality of redo records being elicited by one of said fourth plurality of local packets;

(c) storing each of said second plurality of redo records in a redo record storage location logically associated with the packet eliciting the redo record.

10. The method of claim 1, wherein said first plurality of local packets is stored in a virtual file and the method further comprises:

(a) supplying, to said application logic, a list of virtual file offsets, each of said list of virtual file offsets indicating the location, in said virtual file, of one of said fourth plurality of local packets;

(b) supplying, upon receiving a read request from said application logic, to said application logic, a packet, said read request incorporating a virtual file offset, said packet being loaded from said virtual file offset of said virtual file.

11. The method of claim 10, wherein the method further comprises:

(a) supplying, to said application logic, a first plurality of redo records, each of said first plurality of redo records having previously been elicited by one of said fourth plurality of local packets;

(b) obtaining, from said application logic, a second plurality of redo records, each of said second plurality of redo records being elicited by one of said fourth plurality of local packets;

(c) storing each of said second plurality of redo records in a redo record storage location logically associated with the packet eliciting the recto record.

12. An apparatus for updating the state of an application logic to reflect a plurality of update packets entering a local packet stream, each of said plurality of update packets having a packet timestamp said local packet stream comprising a first plurality of local packets, each of said first plurality of local packets having a packet timestamp, said apparatus comprising:

(a) a CPU, said said CPU having at least one processor core;

(b) a network interface, said network interface being communicatively connected to said CPU, said network interface having previously received said plurality of update packets from a remote computer;

(c) a system memory, said system being communicatively connected to said CPU, said system memory storing a plurality of instructions, said plurality of instructions configuring said CPU for;

(1) calculating an overwrite point, said overwrite point calculated to precede any location in said local packet stream at which one of said plurality of update packets is to be inserted;

(2) supplying, to said application logic, a first plurality of undo records, each of said first plurality of undo records having previously been elicited by one of a second plurality of local packets, each of said second plurality of local packets being after said overwrite point in said local packet stream;

(3) executing a merge operation, said merge operation interleaving said plurality of update packets amongst said second plurality of local packets, said merge operation arranging packets order of increasing packet timestamp, said merge operation eliminating duplicate packets said merge operation resulting in an updated local packet stream comprising a third plurality of local packets;

(4) supplying, to said application logic, a fourth plurality of local packets, each of said fourth plurality of local packets being one of said third plurality of local packets each of said fourth plurality of local packets being after said overwrite point in said updated local packet stream;

(5) obtaining, from said application logic, a second plurality of undo record each of said second plurality of undo records having been elicited by one of said fourth plurality of local packets.

13. The apparatus of claim 12, wherein said plurality of instructions further configure said CPU for:

(1) storing each of said second plurality of undo records in an undo record storage location logically associated with the packet that elicited the undo record.

14. The apparatus of claim 13, wherein said first plurality of local packets is stored in a virtual file and said plurality of instructions further configure said CPU for:

(1) supplying, to said application logic, a list of virtual file offsets, each of said list of virtual file offsets indicating the location, in said virtual file, of one of said fourth plurality of local packets;

(2) supplying, upon receiving a read request from said application logic, to said application logic, a packet, said read request incorporating a virtual file offset, said packet being loaded from said virtual file offset of said virtual file.

15. The apparatus of claim 14, wherein each packet timestamp is calculated as a combination of a clock value and a packet checksum.

16. The apparatus of claim 15, wherein said clock value is the output of a Lamport clock, and said packet checksum is obtained by applying a collision resistant hash function to the contents of a packet.

17. The apparatus of claim 14, wherein said plurality of instructions further configure said CPU for:

(1) supplying, to said application logic, a first plurality of redo records, each of said first plurality of redo records having previously been elicited by one of said fourth plurality of local packets;

(2) obtaining, from said application logic, a second plurality of redo records, each of said second plurality of redo records being elicited by one of said fourth plurality of local packets;

(3) storing each of said second plurality of redo records in a redo record storage location logically associated with the packet eliciting the redo record.