System and method for handling out-of-order data supplied by a real-time feed

• US 20040107389A1
• Filed: 11/30/2002
• Published: 06/03/2004
• Est. Priority Date: 11/30/2002
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Elvery, Michael John, Brown, Kevin
• Granted Patent: US 7,051,245 B2
• Time in Patent Office: Days
• US Class Current: 714/50
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system and associate method handle out-of-order data supplied by a real-time feed, and ingests the real-time feed fast enough to keep up with the feed rate while storing the data in a database in a time-ordered or other sequential manner without discarding any data. The present system adds a second unordered list for out-of-order data received from the feed or from a replay feed. A data element received from the feed, which has a time stamp earlier than the last data element placed in the ordered list, is placed in the unordered list. If replay data is received, the replay data elements are placed in the unordered list without verifying the time stamp. The data is then flushed from these memory lists to a database. Both the ordered list and the unordered list are inputted into the database. The database handles the ordering and merging of these two lists on insertion. The ordered data is still available to the user for real-time query in memory while all data elements are available for analysis in the database.

Claims

1. A method for handling out-of-sequence data supplied by a real-time feed, comprising:

receiving data on a real-time basis;

checking if the data is out-of-sequence;

if the data contains out-of-sequence data, inserting the out-of-sequence data in an unordered list;

if the data contains in-sequence data, inserting the in-sequence data in an ordered list;

checking the unordered list for unflushed data;

if the unflushed data is found in the unordered list, flushing the unflushed data; and

ordering the data that has been flushed, in a predetermined sequence.

2. The method of claim 1, further comprising checking if the data contains replay data from a replay stream.

3. The method of claim 2, wherein if the data contains replay data, inserting the replay data in the unordered list.

4. The method of claim 1, further comprising periodically checking the ordered list and the unordered list for the unflushed data.

5. The method of claim 4, wherein flushing the unflushed data comprises flushing the unflushed data to a database.

6. The method of claim 5, further comprising if the unflushed data is not found, rechecking the ordered list and the unordered list at a later time.

7. The method of claim 5, wherein the database orders the data that has been flushed in a predetermined sequence.

8. The method of claim 7, wherein ordering the flushed data in a predetermined sequence comprises flushing the flushed data in a time ordered manner.

9. The method of claim 8, wherein checking if the data is out-of-sequence further comprises comparing time stamps of sequential data elements in the real-time feed.

10. The method of claim 9, further comprising if the data contains replay data, inserting the replay data in the unordered list.

11. A computer program product having instruction codes for handling out-of-sequence data supplied by a real-time feed, comprising:

a first set of instruction codes for checking if data received on a real-time basis is out-of-sequence;

if the data contains out-of-sequence data, the first set of instruction codes inserts the out-of-sequence data in an unordered list;

if the data contains in-sequence data, the first set of instruction codes inserts the in-sequence data in an ordered list;

a second set of instruction codes for checking the unordered list for unflushed data; and

if the unflushed data is found in the unordered list, the second set of instruction codes flushes the unflushed data and orders the data that has been flushed, in a predetermined sequence.

12. The computer program product of claim 11, further comprising a third set of instruction codes for checking, if the data contains replay data from a replay stream.

13. The computer program product of claim 12, wherein if the data contains replay data, the third set of instruction codes inserts the replay data in the unordered list.

14. The computer program product of claim 11, wherein the second set of instruction codes further periodically checks the ordered list and the unordered list for the unflushed data.

15. The computer program product of claim 14, wherein the second set of instruction codes flushes the unflushed data to a database.

16. The computer program product of claim 15, wherein if the unflushed data is not found, the first set of instruction codes rechecks the ordered list and the unordered list at a later time.

17. The computer program product of claim 15, wherein the database orders the data that has been flushed in a predetermined sequence.

18. The computer program product of claim 17, wherein the database orders the flushed data in a time ordered manner.

19. The computer program product of claim 18, wherein the first set of instruction codes further compares time stamps of sequential data elements in the real-time feed.

20. The computer program product of claim 19, further comprising a third set of instruction codes that checks if the data contains replay data from a replay stream, and if the data contains replay data, the third set of instruction codes inserts the replay data in the unordered list.

21. A system having instruction codes for handling out-of-sequence data supplied by a real-time feed, comprising:

means for checking if data received on a real-time basis is out-of-sequence;

if the data contains out-of-sequence data, the checking means inserts the out-of-sequence data in an unordered list;

if the data contains in-sequence data, the checking means inserts the in-sequence data in an ordered list;

flushing means for checking the unordered list for unflushed data; and

if the unflushed data is found, the flushing means flushes the unflushed data and orders the data that has been flushed, in a predetermined sequence.

22. The system of claim 21, further comprising a replay means for checking if the data contains replay data from a replay stream.

23. The system of claim 22, wherein if the data contains replay data, the replay means inserts the replay data in the unordered list.

24. The system of claim 21, wherein the flushing means further periodically checks the ordered list and the unordered list for the unflushed data.

25. The system of claim 24, wherein the flushing means flushes the unflushed data to a database.

26. The system of claim 25, wherein if the unflushed data is not found, the checking means rechecks the ordered list and the unordered list at a later time.

27. The system of claim 25, wherein the database orders the data that has been flushed in a predetermined sequence.

28. The system of claim 27, wherein the database orders the flushed data in a time ordered manner.

29. The system of claim 28, wherein the checking means further compares time stamps of sequential data elements in the real-time feed.

30. The system of claim 29, further comprising a replay means for checking if the data contains replay data from a replay stream, and if the data contains replay data, the replay means inserts the replay data in the unordered list.