Real-time distributed database system and method

• US 5,970,488 A
• Filed: 05/05/1997
• Issued: 10/19/1999
• Est. Priority Date: 05/05/1997
• Status: Expired due to Term

• Current Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Original Assignee: Northrop Grumman Corporation
• Inventors: Magnani, Timothy P., Somers, James E. Jr., Crowe, Douglas G., LaBarre, Gary K.
• Primary Examiner(s): Choules, Jack M.
• Application Number:
  US08/851,071
• Time in Patent Office: 897 Days
• Field of Search: 707/10, 707/8, 707/201
• US Class Current: 707/656
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/966 Distributed
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A distributed database system includes a plurality of nodes connected via a network medium. Each node runs at least one application and stores a database. Each database at least partially overlaps at least one other database. Each database includes a plurality of tables, and each table includes at least one record. Ownership of each table in the database is assigned to only one application, and only an owning application can modify a table owned by the owning application. Each node also schedules running of the applications on the node such that only one application reads from and writes to the database at a time, distributes updates made to the database to every other database, and updates the database in accordance with received distributed updates.

Claims

1. A method of forming a distributed database, comprising:

(a) providing a plurality of nodes connected via a communication medium;

(b) providing at least one application on each node;

(c) creating a database on each node, each database at least partially overlapping at least one other database, each database including a plurality of tables, and each table including at least one record, said step (c) including the substep of (c1) assigning ownership of each table in each database to only one application;

(d) allowing only an owning application to modify a table owned by said owning application;

(e) allowing only one application to read from and write to a database at a time;

(f) distributing updates made to each database to every other database; and

(g) updating each database in accordance with said distributed updates.

2. The method of claim 1, wherein said step (c) creates said database on each node such that said tables in each database are created in at least one of a static or dynamic manner.

3. The method of claim 1, wherein said step (d) comprises:

(d1) sending modification requests from non-owning applications to said owning application, said modification requests indicating a desired modification to a record in a table not owned by said non-owning applications;

(d2) receiving, by said owning application, said modification requests which request modification of a record in a table owned by said owning application;

(d3) generating, by said owning application, modifications to tables owned by said owning application;

(d4) generating, by said owning application, modifications to tables owned by said owning application based on received modification requests; and

(d5) modifying tables owned by said owning application in accordance modifications generated in said steps (d3) and (d4).

4. The method of claim 1, wherein said step (f) broadcasts said updates made to each database on said communication medium using a reliable computer broadcast system.

5. A method for generating a data update message corresponding to a database stored at a node in a distributed database system, which includes a plurality of nodes each storing a database, to distribute updates to each database, each database overlapping at least partially with a database stored on one other node, each database containing a plurality of tables, each table having a table update flag associated therewith and containing at least one record, each record having a record update flag associated therewith, said table update flag and said record update flag indicating that a corresponding table and record, respectively, have been modified when set, the method comprising:

(a) locating a modified table in said database based on said table update flags;

(b) locating a modified record in said modified table based on said record update flags;

(c) writing a header in said data update message, said header including a table identifier and record number, said table identifier identifying said modified table, said record number identifying said modified record in said modified table;

(d) writing contents of said modified record in said data update message; and

(e) sending said data update message to each node via a communication medium connecting said nodes.

6. The method of claim 5, further comprising the following steps prior to step (e):

(f) determining whether another modified record exists in said modified table based on said record update flags; and

(g) repeating said steps (c) and (d) for said another modified record if said step (f) determines that another modified record exists in said modified table.

7. The method of claim 6, further comprising the following steps prior to said step (e);

(h) determining whether another modified table exists in said database based on said table update flags if said step (f) determines that another modified record does exist in said modified table;

(i) repeating said steps (b)-(g) for said another modified table if said step (h) determines that another modified table exists in said database.

8. The method of claim 6, wherein said step (c) writes a table mark as part of said header, said table mark indicates whether said modified record corresponding to said header is from a different table than a record identified by said record number in the previous header written in said data update message.

9. The method of claim 6, further comprising:

(h) clearing said table update flag corresponding to said modified table if said step (f) determines that another modified record does not exist in said modified table.

10. The method of claim 5, further comprising:

(f) clearing said record update flag corresponding to said modified record after said step (d).

11. The method of claim 5, wherein said tables are at least one of statically and dynamically defined.

12. The method of claim 5, wherein said step (e) is preformed using a reliable network broadcast method.

13. A method for generating a data update message corresponding to a database stored at a node in a distributed database system, which includes a plurality of nodes each storing a database, to distribute updates to each database, each database overlapping at least partially with a database stored on one other node, each database containing a plurality of tables, each table having a table identifier associated therewith and containing at least one record, each record having a record number associated therewith, said database at each node having an updated table list associated therewith, said updated table list storing said table identifier for each modified table in said database, each table having an updated record list associated therewith, said updated record list storing said record number for each modified record in an associated table, the method comprising:

(a) locating a modified table in said database based on said updated table list;

(b) locating a modified record in said modified table based on said updated record list associated with said modified table;

(c) writing a header in said data update message, said header including said table identifier for said modified table and said record number for said modified record;

(d) writing contents of said modified record in said data update message; and

(e) sending said data update message to each node via a communication medium connecting said nodes.

14. The method of claim 13, further comprising the following steps prior to step (e):

(f) determining whether another modified record exists in said modified table based on said updated record list corresponding to said modified table; and

(g) repeating said steps (c) and (d) for said another modified record if said step (f) determines that another modified record exists in said modified table.

15. The method of claim 14, further comprising the following steps prior to said step (e):

(h) determining whether another modified table exists in said database based on said updated table list if said step (f) determines that another modified record does not exist in said modified table;

(i) repeating said steps (b)-(g) for said another modified table if said step (h) determines that another modified table exists.

16. The method of claim 14, wherein said step (c) writes a table mark as part of said header, said table mark indicates whether said modified record corresponding to said header is from a different table than a record identified by said record number in the previous header written in said data update message.

17. The method of claim 14, further comprising:

(h) clearing said updated record list associated with said modified table if said step (f) determines that another modified record does not exist in said modified table.

18. The method of claim 13, wherein said tables are at least one of statically and dynamically defined.

19. The method of claim 13, wherein said step (e) is performed using a reliable network broadcast method.

20. A method of updating a database stored at a node in a distributed database system, which includes a plurality of nodes each storing a database and connected via a communication medium, each database overlapping at least partially with a database stored on one other node, each database containing a plurality of tables, each table containing at least one record, the method comprising:

(a) receiving, at a node, a data update message on said communication medium, said data update message including at least one header associated with a record and contents of said record, said header including a table identifier identifying a table containing said record and a record number associated with said record;

(b) extracting said header from said data update message;

(c) locating said record in said database stored at said node based on said table identifier and said record number in said extracted header; and

(d) writing said contents of said record in said data update message into said record of said database located in step (c).

21. The method of claim 20, further comprising the following steps prior to step (c):

(e) determining whether said table containing said record exists in said database based on said table identifier;

(f) discarding said contents of said record if said step (e) determines that said table containing said record does not exist in said database; and

wherein

said step (c) locates said record if said step (e) determines that said table containing said record does exist in said database.

22. The method of claim 21, further comprising the following steps:

(g) determining whether more data exists in said data update message;

(h) extracting another header from said data update message if said step (g) determines that more data exists in said data update message, each header further including a table mark indicating whether said record associated with said header is from a different table than a record associated with the previous header in said data update message;

(i) determining whether said record associated with said another header is from a different table than a record associated with said previous header based on said table mark;

(j) repeating steps (c) and (d) if (1) said step (i) determines that said record associated with said another header is not from a different table than a record associated with said previous header and (2) said step (e) determined that said table containing said record associated with said previous header exists in said database;

(k) repeating step (f) if (1) said step (i) determines that said record associated with said another header is not from a different table than a record associated with said previous header and (2) said step (e) determined that said table containing said record associated with said previous header does not exists in said database; and

(l) returning to step (e) if said step (i) determines that said record associated with said another header is from a different table than a record associated with said previous header.

23. A distributed database system, comprising:

a plurality of nodes connected via a communication medium; and

wherein

each node includes,

at least one application;

a database stored on said node, said database at least partially overlapping at least one other database, said database including a plurality of tables, and each table including at least one record, ownership of each table in said database being assigned to only one application, and only an owning application being able to modify a table owned by said owning application;

scheduling means for scheduling running of said applications on said node such that only one application reads from and writes to said database at a time;

distributing means for distributing updates made to said database to every other database; and

updating means for updating said database in accordance with received distributed updates.

24. The system of claim 23, wherein each node further comprises:

means for creating said tables in said database in at least one of a static or dynamic manner.

25. The system of claim 23, wherein

non-owning applications send modification requests to said owning application, said modification requests indicating a desired modification to a record in a table not owned by said non-owning applications;

said owning application receives said modification requests which request modification of a record in a table owned by said owning application, first generates modifications to tables owned by said owning application, second generates modifications to tables owned by said owning application based on received modification requests, and modifies tables owned by said owning application in accordance with said first and second generated modifications.

26. The system of claim 23, wherein said distributing means broadcasts said updates made to said database on said communication medium using a reliable computer broadcast system.

27. A distributed database system, comprising:

a plurality of nodes connected via a communication medium, each node storing a database, each database overlapping at least partially with a database stored on one other node, each database containing a plurality of tables, each table having a table update flag associated therewith and containing at least one record, each record having a record update flag associated therewith, said table update flag and said record update flag indicating that a corresponding table and record, respectively, have been modified when set; and

wherein

each node locates a modified table in said database based on said table update flags, locates a modified record in said modified table based on said record update flags, first writes a header in a data update message, said header including a table identifier and record number, said table identifier identifying said modified table, said record number identifying said modified record in said modified table, second writes contents of said modified record in said data update message, and sends said data update message to each node via said communication medium.

28. The system of claim 27, wherein each node, prior to sending said data update message, first determines whether another modified record exists in said modified table based on said record update flags, and first repeats said first and second writing for said another modified record if said node determines that another modified record exists in said modified table.

29. The system of claim 28, wherein each node, prior to sending said data update means, second determines whether another modified table exists in said database based on said update flags table if said node determines that another modified record does exist in said modified table, and second repeats said second locating, said first writing, said second writing, said first determining and said second repeating for said another modified table if said node determines that another modified table exists in said database.

30. The system of claim 28, wherein each node, in performing said first writing, writes a table mark as part of said header, said table mark indicates whether said modified record corresponding to said header is from a different table than a record identified by said record number in the previous header written in said data update message.

31. The system of claim 28, wherein each node clears said table update flag corresponding to said modified table if said node determines that another modified record does not exist in said modified table.

32. The system of claim 27, wherein each node clears said record update flag corresponding to said modified record after said second writing.

33. The system of claim 27, wherein said tables are at least one of statically and dynamically defined.

34. The system of claim 27, wherein each node uses a reliable network broadcast system to send said data update messages.

35. A distributed database system, comprising:

a plurality of nodes connected via a communication medium, each node storing a database, each database overlapping at least partially with a database stored on one other node, each database containing a plurality of tables, each table having a table identifier associated therewith and containing at least one record, each record having a record number associated therewith, said database at each node having an updated table list associated therewith, said updated table list storing said table identifier for each modified table in said database, each table having an updated record list associated therewith, said updated record list storing said record number for each modified record in an associated table; and

wherein

each node first locates a modified table in said database based on said updated table list, second locates a modified record in said modified table based on said updated record list associated with said modified table, first writes a header in a data update message, said header including said table identifier for said modified table and said record number for said modified record, second writes contents of said modified record in said data update message, and sends said data update message to each node via said communication medium.

36. The system of claim 35, wherein each node, prior to sending said data update message, first determines whether another modified record exists in said modified table based on said updated record list corresponding to said modified table, and first repeats said first and second writing for said another modified record if said node determines that another modified record exists in said modified table.

37. The system of claim 36, wherein each node, prior to sending said data update message, second determines whether another modified table exists in said database based on said updated table list if said node determines that another modified record does not exist in said modified table, and second repeats said second locating, said first writing, said second writing, said first determining and said second repeating for said another modified table if said node determines that another modified table exists.

38. The system of claim 36, wherein each node, in performing said second writing, writes a table mark as part of said header, said table mark indicates whether said modified record corresponding to said header is from a different table than a record identified by said record number in the previous header written in said data update message.

39. The system of claim 36, wherein each node clears said updated record list associated with said modified table if said node determines that another modified record does not exist in said modified table.

40. The system of claim 35, wherein said tables are at least one of statically and dynamically defined.

41. The system of claim 35, wherein each node uses a reliable network broadcast system to send said data update message.

42. A distributed database system, comprising:

a plurality of nodes each storing a database and connected via a communication medium, each database overlapping at least partially with a database stored on one other node, each database containing a plurality of tables, each table containing at least one record;

at least one node receiving a data update message on said communication medium, said data update message including at least one header associated with a record and contents of said record, said header including a table identifier identifying a table containing said record and a record number associated with said record;

said node extracting said header from said data update message, locating said record in said database stored at said node based on said table identifier and said record number in said extracted header, and writing said contents of said record in said data update message into said located record of said database.

43. The system of claim 42, wherein said node, prior to writing said contents of said record, first determines whether said table containing said record exists in said database based on said table identifier, and discards said contents of said record if said node determines that said table containing said record does not exist in said database;

and wherein

said node performs said locating and said writing if said node determines that said table containing said record does exist in said database.

44. The system of claim 43, wherein

said node second determines whether more data exists in said data update message, extracts another header from said data update message if said node determines that more data exists in said data update message, each header further including a table mark indicating whether said record associated with said header is from a different table than a record associated with the previous header in said data update message;

said node third determines whether said record associated with said another header is from a different table than a record associated with said previous header based on said table mark;

said node repeats said locating and said writing if (1) said node determines that said record associated with said another header is not from a different table than a record associated with said previous header and (2) said node determined that said table containing said record associated with said previous header exists in said database;

said node repeats said discarding if (1) said node determines that said record associated with said another header is not from a different table than a record associated with said previous header and (2) said node determined that said table containing said record associated with said previous header does not exist in said database; and

said node returns to said first determining if said node determines that said record associated with said another header is from a different table than a record associated with said previous header.

45. A method of communication between applications in a distributed database system which includes a plurality of nodes connected via a network medium, each node running at least one application and storing a database, each database at least partially overlapping at least one other database, each database including a plurality of tables, and each table including at least one record and being owned by only one application, the method comprising:

(a) sending modification requests from non-owning applications to an owning application via said communication medium, said modification requests indicating a desired modification to a record in a table not owned by said non-owning application and owned by said owning application;

(b) receiving, by said owning application, modification requests which request modification of a record in a table owned by said owning application; and

(c) modifying tables owned by said owning application in accordance with modifications generated by said owning application and modifications in said received modification requests.