Replicated resource management system for managing resources in a distributed application and maintaining a relativistic view of state

• US 20010042139A1
• Filed: 08/01/2001
• Published: 11/15/2001
• Est. Priority Date: 03/31/2000
• Status: Abandoned Application

• Current Assignee: Google Inc. (Alphabet Inc.)
• Original Assignee: Aprisma Management Technologies
• Inventors: Jeffords, Jason, Dev, Roger
• Application Number:
  US09/918,832
• Publication Number:
  US 20010042139A1
• Time in Patent Office: Days
• US Class Current: 719/316
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

A method and apparatus for accessing resource objects contained in a distributed memory space in a communications network, including dividing the distributed memory space into a plurality of memory pools, each pool containing a collection of resource objects, providing a plurality of resource manager objects, each resource manager object having an associated set of memory pools and a registry of network unique identifiers for the resource objects in those pools, and accessing a given resource object via its network identifier. Another aspect of the invention is to provide a relativistic view of state of a plurality of objects, each object generating a state vector representing that object'"'"'s view of its own state and the state of all other objects, each object sending its state vector to other objects, and each object maintaining a state matrix of the state vectors.

Claims

1. A method of accessing resource objects contained in a distributed memory space in a communications network comprising:

dividing the distributed memory space into one or more memory pools, each memory pool containing a collection of resource objects, each resource object being a software object having a network unique identifier and containing methods and attributes;

providing a plurality of resource manager objects, each resource manager object having an associated set of memory pools and a registry of the network unique indentifiers for the resource objects in the associated set of memory pools; and

accessing a given resource object via its network unique identifier in the registry of the resource manager object.

2. The method of

claim 1

, further including providing a plurality of processes to perform a distributed processing function, each process having an associated resource manager object, and the plurality of processes sharing the methods and attributes of the resource objects in at least one associated memory pool in order to provide the distributed processing function.

3. The method of

claim 1

, further comprising constructing a distributed application, utilizing a plurality of processes located on a plurality of host systems in the network, by providing each process with an application interface to the resource manager objects.

4. The method of any one of claims 2 and 3, wherein the processes perform one or more of the following steps:

(a) examine the resource objects;

(b) use the resource objects;

(c) instantiate the resource objects;

(d) delete resource objects from the associated memory pool;

(e) change the attributes of the resource objects;

(f) synchronize the change of attributes of the resource objects;

(g) receive attribute change notifications for the resource objects;

(h) use any one of object level messaging and object level remote procedure calls for any one of steps (a) through (g).

5. The method of any one of claims 1, 2 and 3 wherein the resource manager objects perform one or more of the following steps:

(i) object transport;

(j) object level message delivery;

(k) automatic object replication;

(l) resource manager object synchronization;

(m) failure detection.

6. The method of

claim 3

, further comprising applying application specific logic for deriving application specific objects from the resource objects.

7. The method of

claim 2

, wherein the plurality of processes communicate through object level messaging and object level remote procedure calls.

8. The method of

claim 2

, further comprising:

assigning ownership of each of the resource objects to any one of the processes, wherein work requested by calling a method of an owned resource object is performed by the process that owns the called resource object.

9. The method of

claim 8

, wherein:

if one of the processes fails, the ownership of resource objects of the failed process is automatically reassigned to another one of the processes.

10. The method of

claim 2

, wherein each resource manager object maintains state information which is used for one or more of the following:

coordination of work among the processes;

determining validity of data obtained from the processes;

fault detection and isolation;

voting and agreement paradigms.

11. The method of

claim 10

, wherein each resource manager object maintains state information for a contact status determination and for its associated memory pools and the resource manager objects synchronize the state information.

12. The method of

claim 10

, wherein the state information forms a state matrix and synchronization requires the state matrix to be determinant.

13. The method of

claim 10

, wherein each resource manager object maintains a relativistic view of state based upon state information received from other resource manager objects.

14. The method of

claim 3

, wherein the distributed application is a network switch control application, and memory pools are provided relating to the following services:

network topology;

policy;

directory; and

calls.

15. The method of

claim 2

, wherein the resource manager objects perform process level failure detection.

16. The method of

claim 2

, wherein the processes are organized in a peer-to-peer configuration.

17. The method of

claim 2

, wherein ownership of each resource object is assigned to one of the processes, and the work requested by calling a method of an owned resource object is performed by the process that owns the called resource object.

18. The method of

claim 17

, wherein the network unique identifier is an object identifier (OID) that is unique across process boundaries, and the OID comprises:

PoolOID.ServiceAddress.InstanceID where;

PoolOID identifies the memory pool which contains the resource object;

ServiceAddress identifies the process that created the resource object; and

InstanceID is a unique ID identifying an instance of an object under the prefix given by PoolOID.

19. The method of

claim 1

, wherein the resource manager objects provide location-independent object-level messaging based on objectOIDs.

20. The method of

claim 17

, wherein upon failure of one of the processes, each resource object owned by the failed process calls an ownership arbitration method in order to assign ownership to another process.

21. The method of

claim 17

, wherein object ownership is reassigned in order to redistribute the processing load.

22. The method of

claim 17

, wherein object ownership is reassigned in order to allow a resource manager object to leave an associated memory pool.

23. The method of

claim 2

, wherein each memory pool is assigned a pool identifier which is unique across process boundaries.

24. The method of

claim 2

, wherein each resource manager object is assigned a resource manager object identifier which is unique across process boundaries.

25. The method of

claim 1

, further including transporting distributable representations of resource objects to the resource manager objects for an associated memory pool.

26. The method of

claim 1

, wherein each resource object includes one or more methods for changing an attribute'"'"'s value and one or more methods for sending the attribute'"'"'s value to the resource manager objects of the associated memory pool.

27. The method of

claim 8

, wherein when a first joining process of a first resource manager object seeks to join a first memory pool, the first memory pool is synchronized by:

the first resource manager object sending a join pool request to the other resource manager objects;

each resource manager object already joined in the first memory pool responding to the request by sending all the resource objects owned by its associated process to the joining process; and

the first resource manager object sending all of the resource objects owned by the joining process to the already joined processes.

28. A method of maintaining a relativistic view of state of a plurality of distributed resource objects comprising:

each resource object having a logical object name, a logical object state, and access to a method for communicating with other objects;

each resource object generating a state vector representing that object'"'"'s view of its own state and the state of all other objects, the state vector comprising a one-dimensional associative array of logical object name to logical object state, wherein the logical object name is an index into the vector and the logical object state is stored in a slot associated with the index;

each resource object sending its state vector to the other resource objects; and

each resource object maintaining a state matrix comprising a two-dimensional associative array of the state vectors having rows and columns indexed by logical object names.

29. The method of

claim 28

, wherein the state matrix is determined to be “

row determinant”

if and only if each of its row state vectors are determinant, and the state matrix is determined to be “

column determinant”

if and only if each of its column state vectors are determinant.

30. The method of

claim 29

, wherein the state matrix is determined to be “

fully determinant”

if and only if it is both row determinant and column determinant.

31. The method of

claim 28

, further comprising providing a plurality of processes, each process having an associated set of resource objects, each resource object having attributes and methods, and the plurality of processes confirming the existence of a determinant state matrix prior to using attributes and methods of the resource objects in order to provide a distributed processing function.

32. The method of

claim 28

, further comprising applying application specific logic to the state vectors by deriving application specific objects.

33. The method of

claim 32

, further comprising applying application specific logic to the state matrices by deriving application specific objects.

34. The method of

claim 33

, wherein the application specific objects are used to determine a contact status of processes in a distributed processing function.

35. The method of

claim 28

, wherein the logical object state of each resource object represents a contact status having one of three possible conditions:

(a) no information about the object has been obtained;

(b) contact with the object has been established; and

(c) contact with a previously contacted object has been lost.

36. The method of

claim 35

, wherein when the contact status of an object changes, the object sends a state vector describing the changed state to all other objects with which it has established contact.

37. In a communications network having a distributed memory space in a plurality of hosts, apparatus for managing the distributed memory space comprising:

the distributed memory space being divided into a plurality of memory pools, each memory pool containing a collection of resource objects, each resource object being a software object having a network unique identifier and containing methods and attributes; and

a plurality of resource manager objects located on different hosts in the network, each resource manager object having an associated set of memory pools and a replicated set of resource objects for the associated memory pools.

38. In a distributed computing method, wherein a number of cooperating processes require access to resource objects, the improvement comprising:

a) providing a distributed memory space containing resource objects;

b) providing a plurality of pool objects, each pool object identifying an associated set of resource objects for dividing the resource objects in the distributed memory space into pools;

c) providing each cooperating process with a resource manager object object, each resource manager object object identifying an associated set of pools in which the cooperating process requires access to the contained resource objects;

d) each resource manager object object replicating the resource objects in its associated set of pools and providing access by the cooperating process to the replicated resource objects; and

e) each resource manager object object synchronizing its state with the other resource manager object objects.

39. The method of

claim 38

, wherein the synchronizing step includes:

determining whether the resource manager object object is in an active state.

40. The method of

claim 39

, wherein the synchronizing step includes:

determining the state of the pool objects.

41. The method of

claim 40

, wherein the synchronizing step includes:

determining the state of the resource objects.

42. The method of any one of claims 38 and 40, wherein the determining step includes:

generating a state vector comprising the object'"'"'s view of itself and relative view of other objects.

43. The method of

claim 42

, wherein the determining step comprises:

determining whether the state vector is determinant.

44. The method of

claim 42

, wherein the determining step comprises:

generating a state matrix of state vectors.

45. The method of

claim 44

, wherein the determining step comprises:

determining whether the state matrix is determinant.

46. The method of

claim 38

, further comprising:

assigning ownership of each resource object to any one of the processes, wherein the owning process is responsible for the work performed by the owned resource object.

47. The method of

claim 46

, further comprising the step of:

the resource manager objects determining a distribution of workload among the processes.

48. The method of

claim 46

, further comprising the step of:

a new cooperating process joining the computing function by sending a join pool message to the resource manager objects.

49. The method of

claim 46

, further comprising the step of:

a cooperating process leaving the computing function by sending a leave pool message to the resource manager objects already joined to the pool.

50. The method of

claim 38

, further comprising the step of:

storing the resource objects in a persistent storage medium.

51. The method of

claim 42

, further comprising:

applying application specific logic to the state vectors by derivation to provide application specific state vectors.

52. The method of

claim 44

, further comprising:

applying application specific logic to the state matrices by derivation for providing application specific state matrices.

53. The method of

claim 52

, further comprising:

determining the contact status of the cooperating processes from the application specific state matrices.

54. Apparatus for performing a distributed computing function in a system having a plurality of hosts, each host having a local processer and memory comprising:

a first host including a first process and a first resource manager object which identifies one or more pools containing resource objects which the first process requires access to;

a second host including a second process and a second resource manager object which identifies one or more pools containing resource objects which the second process requires access to;

each resource object being contained in the local memory of the host having the process which requires access to the resource object;

wherein each of the first and second processes can access the resource object in local memory contained in the same host as the process.

55. In a system comprising a plurality of hosts and a connection device for enabling communication between the hosts, each host having a local processor and local memory and the combined local memories comprising a distributed memory space, a software system for enabling the hosts to perform a distributed computing function comprising:

a plurality of cooperating processes contained on different hosts;

each cooperating process having a resource manager object identifying an associated set of pools in which the cooperating process requires access;

a plurality of pool objects for dividing the distributed memory space into pools, each pool object identifying an associated set of resource objects contained in the distributed memory space;

each host which contains a cooperating process having the pool objects and the resource objects to which the cooperating process requires access.

56. A software system for maintaining a relativistic view of state of a plurality of objects, wherein the objects are distributed among various host systems, comprising:

a state vector comprising a one-dimensional associative array of logical object name to logical object state, wherein the state vector is generated by an object and describes what that object thinks is the state of all objects in the vector.

57. The system of

claim 56

, further comprising:

a state matrix comprising a two-dimensional associative array composed of state vectors.

58. In a distributed computing method, wherein a number of cooperating processes require access to resource objects, the improvement comprising:

the cooperating processes maintaining a distributed shared memory space, wherein each resource object has state information that is accessible within each cooperating process; and

the cooperating processes using the shared state information simultaneously, and communicating through object level messaging and remote procedure calls to distribute the processing load.

59. The method of

claim 58

, wherein each cooperating process is assigned ownership of one or more resource objects, and the owning process is responsible for performing all processing for the owned object.

60. The method of

claim 59

, wherein when a cooperating process fails, all objects owned by the failed process have the ownership changed to another cooperating process still participating in the distributed computing method.