Replication of object graphs

• US 20080215593A1
• Filed: 01/23/2008
• Published: 09/04/2008
• Est. Priority Date: 10/25/2005
• Status: Active Grant

• Current Assignee: Waratek Limited (Waratek Holdings Ltd.)
• Original Assignee: John M. Holt
• Inventors: Holt, John M.
• Granted Patent: US 7,996,627 B2
• Time in Patent Office: Days
• US Class Current: 707/10
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

The updating of only some memory locations in a multiple computer environment in which at least one applications program (50) executes simultaneously on a plurality of computers M1, M2 . . . Mn each of which has a local memory, is disclosed. Objects A and B in each local memory are disclosed which each include primitive fields (11). However, the simultaneous operation of the application program (50) can result in a “non-primitive” reference field (10) in one machine which must then be replicated in all other machines. However, the reference field (10) references another object (H) in the one machine'"'"'s local memory so corresponding objects (T, K) must be created in the local memory of each other machine and be referenced by the corresponding non-primitive field (10).

Claims

1. In a multiple computer system comprising a plurality of computers, each including a local processor and a local memory coupled with the local processor, and including a first computer and a second computer interconnected via a communications link or network operating in a replicated shared memory arrangement, the local memory(ies) having a local memory location(s) and/or a memory value(s), a method of classifying said local memory(ies) comprising:

classifying said local memories into a first category of memory locations each of which contains or stores non-address values or content; and

classifying said local memories into a second category of memory locations each of which contains or stores memory address values or memory address contents of other memory location(s).

2. A method as in claim 1, further comprising:

a. maintaining a correspondence of or between ones of plural replica memory locations, where said ones of said plural replica memory locations are each on a different one of said multiple computers.

3. A method as in claim 1, further comprising:

a. maintaining a correspondence of or between ones of plural replica memory locations, said correspondence on each one of said multiple computers, and where said ones of said plural replica memory locations are each on a different one of said multiple computers.

4. A method as in claim 1, further comprising:

a. maintaining a correspondence table or record of or between ones of plural replica memory locations, where said ones of said plural replica memory locations are each on a different one of said multiple computers.

5. A method as in claim 1, further comprising:

a. maintaining a correspondence table or record of or between ones of plural replica memory locations, said correspondence table or record being on each one of said multiple computers, and where said ones of said plural replica memory locations are each on a different one of said multiple computers.

6. A method as in claim 4, including the further step of:

maintaining one or multiple correspondence table or record according to at least one of the following predetermined schemes;

(i) maintaining one said correspondence table or record for all said multiple computers on a further a server;

(ii) maintaining one said correspondence table or record on in each of said multiple computers;

(iii) maintaining multiple said correspondence tables or records in each of said multiple computers;

(iv) maintaining multiple said correspondence tables or records, one of each said multiple tables or records in each of said computers;

(v) maintaining one said correspondence table or record for each said memory location;

(vi) maintaining one said correspondence table or record for each said first category memory location;

(vii) maintaining one said correspondence table or record for each said second category memory location.

(viii) maintaining one said correspondence table for each plurality of said memory location(s); and

(ix) maintaining one said correspondence table for each plurality of said memory locations of potentially multiple pluralities.

7. A method as in claim 4, including the further step of:

a. maintaining one said correspondence table or record for all said multiple computers on a further a server.

8. A method as in claim 4, including the further step of:

a. maintaining one said correspondence table or record on in each of said multiple computers.

9. A method as in claim 4, including the further step of:

a. maintaining multiple said correspondence tables or records in each of said multiple computers.

10. A method as in claim 4, including the further step of:

a. maintaining multiple said correspondence tables or records, one of each said multiple tables or records in each of said computers.

11. A method as in claim 4, including the further step of:

a. maintaining one said correspondence table or record for each said memory location.

12. A method as in claim 4, including the further step of:

a. maintaining one said correspondence table or record for each said first category memory location.

13. A method as in claim 4, including the further step of:

a. maintaining one said correspondence table or record for each said second category memory location.

14. A method as in claim 6, including the further step of:

a. maintaining one said correspondence table for each plurality of said memory location(s).

15. A method as in claim 14, including the further step of:

a. maintaining one said correspondence table for each plurality of said memory locations of potentially multiple pluralities.

16. A method as in claim 14, wherein said plurality of said memory locations are plural memory locations of a related set of memory locations.

17. A method as in claim 16, wherein said related set of memory locations is an array of memory locations.

18. A method as in claim 17, wherein said array of memory locations comprise an array data structure.

19. A method as in claim 16 wherein said related set of memory locations are memory locations of an object or class.

20. A method as in claim 19, wherein said memory locations of an object or class are object fields or variables, or class fields or variables.

21. A method as in claim 1, wherein said other memory location(s) includes said first category memory location(s).

22. A method as in claim 1, wherein said other memory location(s) includes said second category memory location(s).

23. A method as in claim 1, wherein said other memory location(s) includes said containing or storing second category memory location(s).

24. A method as in claim 1, wherein said memory address value(s) are memory addresses of said other memory location(s).

25. A method as in claim 1, wherein said memory address value(s) are (or may be) empty or null or invalid memory addresses.

26. A method as in claim 1, wherein said memory address value(s) are pointers, references, handles, or links to or of said other memory location(s).

27. A method as in claim 1, wherein each said correspondence is assigned or allocated or associated with a substantially unique global name or identifier.

28. A method as in claim 1, wherein said each correspondence of said ones of said plural replica memory locations is assigned or allocated or associated with a global name or identifier.

29. A method as in claim 1, wherein:

either (i) each said correspondence is assigned or allocated or associated with a substantially unique global name or identifier, or (ii) said each correspondence of said ones of said plural replica memory locations is assigned or allocated or associated with a global name or identifier; and

wherein said correspondence comprises a recorded or indicated association of said ones of said plural replica memory locations.

30. A method as in claim 27, wherein said correspondence comprises a concordance table or record.

31. A method as in claims 1, wherein each said correspondence table or record is assigned or allocated or associated with a substantially unique global name or identifier.

32. A method as in claim 1, wherein each said correspondence table or record of said ones of said plural replica memory locations is assigned or allocated or associated with a global name or identifier.

33. A method as in claim 1, wherein each entry of said correspondence table or record is assigned or allocated or associated with a substantially unique global name or identifier.

34. A method as in claim 1, wherein each entry of said correspondence table or record of said ones of said plural replica memory locations is assigned or allocated or associated with a global name or identifier.

35. A method as in claim 27, wherein each said global name or identifier of each said correspondence is substantially unique.

36. A method as in claim 1, including the further step of:

a. utilising said memory address value(s) to access said other memory location(s).

37. A method as in claim 1, including the further step of:

a. utilising said memory address value(s) to access said other memory location(s).

38. A method as in claim 35, wherein said access includes reading or writing said other memory location(s).

39. A method as in claim 35, wherein said access includes loading values or content from, or storing values or content to, said other memory location(s).

40. A method as in claim 39, wherein said utilisation includes utilising said memory address value(s) of said second category memory location(s) by said processing units.

41. A method as in claim 39, wherein said utilisation includes utilising said memory address value(s) of said second category memory location(s) by said application program.

42. A method as in claim 41, wherein said application program includes executable instructions or executable code of said application program.

43. A method as in claim 1, wherein said plural replica memory locations comprises a plurality of substantially similarly replicated memory locations and/or values, each on a different one of said multiple computers, and which are substantially similarly updated with new values or content of any, so as to remain substantially similar, and where said substantially similar updating includes utilising said correspondence to identify the corresponding said ones of said plural replica memory locations on each one of said multiple computers which are to be updated.

44. A method as in claim 40, wherein said replica memory locations are said first category memory location(s), and where said new value(s) or content are said non-address value(s) or content, including the further step of:

a. receiving said new value(s) previously transmitted by another one of said multiple computers,

b. storing said received new value(s) or content to said identified corresponding ones of plural replica memory locations, on each receiving one of said computer(s).

45. A method as in claim 40, wherein said replica memory locations are said second category memory location(s), and where said new value(s) or content are said empty or null or invalid memory address value(s), including the further step of:

a. receiving said new value(s) previously transmitted by another one of said multiple computers,

b. storing an empty or null or invalid memory address value or content to said identified corresponding ones of plural replica memory locations, on each receiving one of said computer(s).

46. A method as in claim 40, wherein said replica memory locations are said second category memory locations, and where said new value(s) or content are said memory address value(s), including the further step of:

a. receiving said new value(s) previously transmitted by another one of said multiple computers,

b. utilising said correspondence to determine (or resolve) the local memory address value(s) on each one of said computers to which said received new value(s) correspond,

c. storing said determined (or resolved) local memory address value(s) to said identified corresponding ones of plural replica memory locations, on each receiving one of said computer(s).

47. A method as in claim 40, wherein said replica memory locations are said second category memory locations, and where said new value(s) or content is/are said global name(s) or identifier(s), including the further step of:

a. receiving said new value(s) previously transmitted by another one of said multiple computers,

b. utilising said correspondence to determine (or resolve) the local memory address value(s) on each one of said computers to which said received new value(s) correspond.

c. storing said determined (or resolved) local memory address value(s) to said identified corresponding ones of plural replica memory locations, on each receiving one of said computer(s).

48. A method as in claim 43, wherein said replica memory locations comprise said second category memory locations, and where said new value(s) or content are said memory address value(s), and receiving said new value(s) transmitted by another one of said multiple computers, and where following utilising said correspondence to determine or resolve the local memory address value(s) on each one of said multiple computers to which said new value(s) correspond, it is determined that a corresponding memory location for said memory address value(s) is not replicated on one or more of said multiple computers, then including the step of:

a. replicating the said corresponding memory location(s) of said memory address value(s) to/in said one or more non-replicated computer(s); and

b. storing said determined or resolved local memory address value(s) to said identified corresponding ones of plural replica memory locations, on each one of said multiple computers in which said corresponding memory location for said memory address value(s) is replicated.

49. A method as in claim 43, wherein said replica memory locations are said second category memory locations, and where said new value(s) or content are said memory address value(s), and receiving said new value(s) transmitted by another one of said multiple computers, and where following utilising said correspondence to determine or resolve the local memory address value(s) on each one of said multiple computers to which said new value(s) correspond, it is determined that no corresponding memory location for said memory address value(s) is replicated on one or more of said multiple computers, then including the step of:

a. replicating the said corresponding memory location(s) of said memory address value(s) to/in said one or more non-replicating computer(s) in which said replica memory location(s) is replicated; and

b. storing said determined or resolved local memory address value(s) to said identified corresponding ones of plural replica memory locations, on each one of said multiple computers in which said corresponding memory location for said memory address value(s) is replicated.

50. A method as in claim 43, wherein said replica memory locations are said second category memory locations, and where said new value(s) or content are said memory address value(s), and receiving said new value(s) transmitted by another one of said multiple computers, and where following utilising said correspondence to determine or resolve the local memory address value(s) on each one of said multiple computers to which said new value(s) correspond, and further comprising:

if it is determined that a corresponding memory location for said memory address value(s) is not replicated on one or more of said multiple computers, then including the steps of;

(a) replicating the said corresponding memory location(s) of said memory address value(s) to/in said one or more non-replicated computer(s); and

(b) storing said determined or resolved local memory address value(s) to said identified corresponding ones of plural replica memory locations, on each one of said multiple computers in which said corresponding memory location for said memory address value(s) is replicated; and

if it is determined that no corresponding memory location for said memory address value(s) is replicated on one or more of said multiple computers, then including the steps of;

(c) replicating the said corresponding memory location(s) of said memory address value(s) to/in said one or more non-replicating computer(s) in which said replica memory location(s) is replicated, and

(d) storing said determined or resolved local memory address value(s) to said identified corresponding ones of plural replica memory locations, on each one of said multiple computers in which said corresponding memory location for said memory address value(s) is replicated.

51. A method as in claim 50, including the further step of:

a. updating said correspondence table(s), to include the replicated said corresponding memory locations of said memory address value(s) of said replicating.

52. A method as in claim 51, including the further step of:

a. storing the local memory address value(s) of said replicated corresponding memory locations of said memory address value(s), to said identified corresponding ones of plural replica memory locations, on each one of said multiple computers in which said replication took place.

53. A method as in claim 43, including the step of:

a. substantially similarly updating said plural replica memory locations of other computer(s) with new value(s) or content so as to remain substantially similar, where said plural replica memory location(s) are said first category memory locations, and where said new value(s) or content is said non-address value(s) or content.

54. A method as in claim 43, including the step of:

a. substantially similarly updating said plural replica memory locations of other computer(s) with new value(s) or content so as to remain substantially similar, where said plural replica memory location(s) are said second category memory locations, and where said new value(s) or content is said empty or null or invalid memory address value(s).

55. A method as in claim 43, including the step of:

a. substantially similarly updating said plural replica memory locations of other computer(s) with new value(s) or content so as to remain substantially similar, where said plural replica memory location(s) are said second category memory locations, and where said new value(s) or content is said memory address values or content, and where said substantially similar updating includes (comprises) utilising said correspondence to determine (or resolve) the local memory address value(s) on each one of said other computers on which said plural replica memory location(s) reside, and to which said new value(s) are to correspond.

56. A method as in claim 43, including the step of:

a. substantially similarly updating said plural replica memory locations of other computer(s) with new value(s) or content so as to remain substantially similar, where said plural replica memory location(s) are said second category memory locations, and where said new value(s) or content is said global name(s) or identifier(s), and where said substantially similar updating includes (comprises) utilising said correspondence to determine (or resolve) the said global name(s) or identifier(s) assigned to (or allocated to) or associated with said plural replica memory locations.

57. A method as in claim 55, whereupon following utilising said correspondence to determine (or resolve) the local memory address value(s) on each other one of said multiple computers to which said new value(s) are to correspond, it is determined that corresponding memory locations are not replicated on one or more of said other computers, then including the step of:

a. carrying out said updating of said plural replica memory locations of said other computer(s) in which corresponding memory locations are replicated to which said new value(s) are to correspond.

58. A method as in claim 57, including the further step of:

a. replicating corresponding memory locations to which said new value(s) are to correspond, to/in said one or more non-replicating computers.

59. A method as in claim 58, including the further step of:

a. updating said correspondence table(s), to include the replicated said corresponding memory locations of said memory address value(s) of said replicating.

60. A method as in claim 59, including the further step of:

a. carrying out said substantially similar updating with a different thread from the thread first causing said new value(s) or content to be stored (or updated) to a first of said plural replica memory locations.

61. A method as in claim 60, wherein said thread is a non-application program thread.

62. A method as in claim 61, wherein said non-application program thread does not operate or perform executable instructions or executable code of said application program.

63. A method as in claims 1, including the further step of:

a. modifying said application program before, during, or after loading by inserting one or more updating operations in order to affect said updating.

64. A method as in claim 63, wherein said application program is modified in accordance with a procedure from a group of procedures consisting of re-compilation at loading, pre-compilation at loading, compilation prior to loading, just-in-time compilation, re-compilation after loading but before execution of the relevant portion of the application program, and re-compilation after execution of the relevant portion of the application program has commenced.

65. A method as in claim 60 wherein said modification procedures operate on each said computer.

66. A method as in claim 65, wherein said modified application program is transferred from a first computer to all other of said multiple computers, and loaded by said other multiple computers upon receipt or thereafter.

67. A method as in claim 1, wherein said local memory(ies) of each said computer are independent of said local memory(ies) of each other computer.

68. A method as in claim 1, wherein said local processors may only access said local memory(ies) of the same computer in which the local processor is located.

69. A method as in claim 1, wherein at least a first application program written to operate on a single one of said computers, is operating substantially simultaneously on different ones of said multiple computers.

70. A method as in claim 69, wherein said application program operating substantially simultaneously on each of said different ones of said computers, may only access said local memory(ies) of the same computer.

71. A method as in claim 70, wherein said access is satisfied by said local memory(ies) of the same computer independently of (or without the aid of) said local memory(ies) of any other computer.

72. A method as in claim 70, wherein said access includes reading and/or writing content or values stored or resident within said local memory(ies) of the same computer.

73. A method as in claim 71, wherein said access includes reading and/or writing content or values stored or resident within said local memory(ies) of the same computer.

74. A method as in claim 70, wherein said access is restricted to reading and/or writing content or values stored or resident within said local memory(ies) of the same computer.

75. A method as in claim 71, wherein said access is restricted to reading and/or writing content or values stored or resident within said local memory(ies) of the same computer.

76. A method as in claim 70, wherein said access includes reading and/or writing content or values of real or virtual memory addresses of or resident within said local memory(ies) of the same computer.

77. A method as in claim 71, wherein said access includes reading and/or writing content or values of real or virtual memory addresses of or resident within said local memory(ies) of the same computer.

78. A method as in claim 72, wherein said access includes reading and/or writing content or values of real or virtual memory addresses of or resident within said local memory(ies) of the same computer.

79. A method as in claim 70, wherein said access is restricted to reading and/or writing content or values of real or virtual memory addresses of or resident within said local memory(ies) of the same computer.

80. A method as in claim 71, wherein said access is restricted to reading and/or writing content or values of real or virtual memory addresses of or resident within said local memory(ies) of the same computer.

81. A method as in claim 72, wherein said access is restricted to reading and/or writing content or values of real or virtual memory addresses of or resident within said local memory(ies) of the same computer.

82. A method as in claim 70, wherein at least one memory location and/or memory value of said application program is substantially similarly replicated in said local memory(ies) of said different ones of said multiple computers.

83. A method as in claim 79, wherein said substantially similarly replicated memory location(s) and/or value(s) are stored non-identically in said local memory(ies) of said different ones of said multiple computers.

84. A method as in claim 80, wherein said substantially similarly replicated memory location(s) and/or memory value(s) are updated through in-due-course updating to remain substantially similar upon occasion of any one of said plurality of computers simultaneously operating said application program modifying, or causing to be modified, the value(s) or content(s) of said substantially similarly replicated memory location(s) and/or memory value(s).

85. A method as in claim 84, wherein each said substantially similarly replicated memory location(s) and/or value(s) of each one of said multiple computers is identified with a substantially similar identifier.

86. A method as in claim 84, wherein said in-due-course updating provides that said replicated memory locations are updated to remain substantially similar upon occasion of any one of said computers simultaneously operating said application program causing modification of the contents of said replicated memory location.

87. A method as in claim 1, wherein the memory location(s) and/or value(s) of said local memory(ies) may be classified into a first category of memory locations each of which contains or stores non-address values or content, and a second category of memory locations each of which contains or stores memory address values or memory address contents of other memory location(s).

88. A method as in claim 1, wherein:

said local memory(ies) of each said computer are independent of said local memory(ies) of each other computer;

said local processors may only access said local memory(ies) of the same computer in which the local processor is located;

at least a first application program written to operate on a single one of said computers, is operating substantially simultaneously on different ones of said multiple computers;

said application program operating substantially simultaneously on each of said different ones of said computers, may only access said local memory(ies) of the same computer;

said access is satisfied by said local memory(ies) of the same computer independently of (or without the aid of) said local memory(ies) of any other computer;

said access includes reading and/or writing content or values stored or resident within said local memory(ies) of the same computer, or said access is restricted to reading and/or writing content or values stored or resident within said local memory(ies) of the same computer;

said access includes reading and/or writing content or values of real or virtual memory addresses of or resident within said local memory(ies) of the same computer, or said access is restricted to reading and/or writing content or values of real or virtual memory addresses of or resident within said local memory(ies) of the same computer;

at least one memory location and/or memory value of said application program is substantially similarly replicated in said local memory(ies) of said different ones of said multiple computers;

said substantially similarly replicated memory location(s) and/or value(s) are stored non-identically in said local memory(ies) of said different ones of said multiple computers;

said substantially similarly replicated memory location(s) and/or memory value(s) are updated through in-due-course updating to remain substantially similar upon occasion of any one of said plurality of computers simultaneously operating said application program modifying, or causing to be modified, the value(s) or content(s) of said substantially similarly replicated memory location(s) and/or memory value(s);

each said substantially similarly replicated memory location(s) and/or value(s) of each one of said multiple computers is identified with a substantially similar identifier; and

said in-due-course updating provides that said replicated memory locations are updated to remain substantially similar upon occasion of any one of said computers simultaneously operating said application program causing modification of the contents of said replicated memory location.

89. A method as in claim 1, further comprising:

maintaining a correspondence of or between ones of plural replica memory locations, where said ones of said plural replica memory locations are each on a different one of said multiple computers.

maintaining one or multiple correspondence table or record according to at least one predetermined scheme;

wherein said other memory location(s) includes at least one of said first category memory location(s) and said second category memory location(s);

wherein each said correspondence is assigned or allocated or associated with a substantially unique global name or identifier;

utilising said memory address value(s) to access said other memory location(s);

wherein said plural replica memory locations comprises a plurality of substantially similarly replicated memory locations and/or values, each on a different one of said multiple computers, and which are substantially similarly updated with new values or content of any, so as to remain substantially similar, and where said substantially similar updating includes utilising said correspondence to identify the corresponding said ones of said plural replica memory locations on each one of said multiple computers which are to be updated; and

wherein said replica memory locations are said second category memory locations, and where said new value(s) or content are said memory address value(s), and receiving said new value(s) transmitted by another one of said multiple computers, and where following utilising said correspondence to determine or resolve the local memory address value(s) on each one of said multiple computers to which said new value(s) correspond, and further comprising;

if it is determined that a corresponding memory location for said memory address value(s) is not replicated on one or more of said multiple computers, then including the steps of;

(a) replicating the said corresponding memory location(s) of said memory address value(s) to/in said one or more non-replicated computer(s); and

(b) storing said determined or resolved local memory address value(s) to said identified corresponding ones of plural replica memory locations, on each one of said multiple computers in which said corresponding memory location for said memory address value(s) is replicated; and

if it is determined that no corresponding memory location for said memory address value(s) is replicated on one or more of said multiple computers, then including the steps of;

replicating the said corresponding memory location(s) of said memory address value(s) to/in said one or more non-replicating computer(s) in which said replica memory location(s) is replicated, and storing said determined or resolved local memory address value(s) to said identified corresponding ones of plural replica memory locations, on each one of said multiple computers in which said corresponding memory location for said memory address value(s) is replicated;

substantially similarly updating said plural replica memory locations of other computer(s) with new value(s) or content so as to remain substantially similar, where said plural replica memory location(s) are said first category memory locations, and where said new value(s) or content is said non-address value(s) or content;

carrying out said substantially similar updating with a different thread from the thread first causing said new value(s) or content to be stored (or updated) to a first of said plural replica memory locations; and

modifying said application program before, during, or after loading by inserting one or more updating operations in order to affect said updating.

90. A computer program stored on a computer readable memory device comprising instructions which, when executed on a computer, perform in at least one single computer capable of interoperating with at least one other computer coupled to at least one said single computer at least intermittently via a communications network to form a multiple computer system having a plurality of computers wherein each computer has a local memory and the multiple computer system operating in a replicated shared memory arrangement, the local memory(ies) having a local memory location(s) and/or a memory value(s), a method of classifying said local memory(ies) comprising:

classifying said local memories into a first category of memory locations each of which contains or stores non-address values or content; and

classifying said local memories into a second category of memory locations each of which contains or stores memory address values or memory address contents of other memory location(s).

91. A multiple computer system comprising:

a plurality of computers, each including a local processor and a local memory coupled with the local processor, and including a first computer and a second computer interconnected via a communications link or network operating in a replicated shared memory arrangement, the local memory(ies) having a local memory location(s) and/or a memory value(s);

means for classifying said local memories into a first category of memory locations each of which contains or stores non-address values or content; and

means for classifying said local memories into a second category of memory locations each of which contains or stores memory address values or memory address contents of other memory location(s).