Score-based scheduling of service requests in a grid services computing platform

• US 7,130,891 B2
• Filed: 12/05/2003
• Issued: 10/31/2006
• Est. Priority Date: 02/04/2002
• Status: Expired due to Term

• Current Assignee: Cloud Software Group
• Original Assignee: DataSynapse, Inc. (Cloud Software Group)
• Inventors: Lee, Peter, Bernardin, James
• Primary Examiner(s): DINH, KHANH Q
• Assistant Examiner(s): DINH, KHANH Q
• Application Number:
  US10/728,732
• Publication Number:
  US 20050021594A1
• Time in Patent Office: 1,061 Days
• Field of Search: 709/203, 709/224, 709/228, 709/217, 709/218, 707/2, 707/4, 707/10, 711/133, 705/14
• US Class Current: 709/218
• CPC Class Codes: G06F 2209/503 Resource availability
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A service-oriented framework allows client applications to services hosted on a distributed computing access computational grid. Services facilitate remote, parallel execution of code in a way that is scalable, fault-tolerant, dynamic and language-independent. Services can be written in a variety of languages, and do not need to be compiled or linked with vendor-supplied code. A client written in one language can invoke a Service written in another. A benefit of the invention over traditional approaches is that it virtualizes the Service. Rather than send a request directly to the remote machine hosting the Service, a client request is sent to a manager, which enqueues until an Engine is available. The first Engine to dequeue the request hosts the Service. This mechanism, in which a single virtual Service instance (the client-side object) is implemented by one or more physical instances (Engine processes), provides for fault tolerance and essentially unlimited scalability.

Claims

1. A method for providing computational services to a client using a grid-based distributed computing system, the system including a plurality of engines and at least one grid manager, the method comprising:

deploying executable code corresponding one or more service(s) such that the engines can access the executable code;

registering the service(s) with the grid manager;

creating instance(s) of the service(s) invocable by the client; and

,

using one or more of the instance(s) to invoke one or more of the registered service(s), wherein invoking a service comprises;

communicating a service request to the grid manager;

using the grid manager to assign the service request to an available engine by (i) obtaining neediness score(s) for pending service request(s), each neediness score based on at least (a) an amount of time that engines have spent running task(s) associated with the requested service and (b) an amount of time that the request for the service has spent waiting to be assigned, (ii) obtaining affinity scores reflecting the affinity of available engine(s) to requested service(s), and (iii) applying an adaptive scheduling algorithm to assign the service request to one or more available engine(s); and

,

executing code corresponding to the requested service on at least one of the assigned engine(s).

2. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein the adaptive scheduling algorithm select(s) from available engine(s) based, at least in part, on one or more of the neediness score(s).

3. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein the adaptive scheduling algorithm select(s) from available engine(s) based, at least in part, on one or more of the affinity score(s).

4. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein the adaptive scheduling algorithm select(s) from available engine(s) based, at least in part, on one or more of the neediness score(s) and one or more of the affinity score(s).

5. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein the adaptive scheduling algorithm selectively supports redundant scheduling.

6. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein deploying executable code comprises storing executable code on a shared file system accessible to the engines.

7. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein deploying executable code comprises using a file update mechanism provided by the grid manager to distribute executable code to the engines.

8. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 7, wherein using a file update mechanism to distribute the executable code to the engines comprises distributing executable code to the engines when the grid manager is idle.

9. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein creating an instance of a service comprises invoking a service creation method.

10. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein communicating a service request to the grid manager comprises invoking a synchronous invocation method.

11. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein communicating a service request to the grid manager comprises invoking an asynchronous invocation method.

12. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein communicating a service request to the grid manager comprises synchronously invoking a client-side proxy that corresponds to the service.

13. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein communicating a service request to the grid manager comprises asynchronously invoking a client-side proxy that corresponds to the service.

14. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein communicating a service request to the grid manager comprises communicating a synchronous service request via a client-side Web Services Description Language (wsdl) proxy.

15. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein communicating a service request to the grid manager comprises communicating an asynchronous service request via a client-side wsdl proxy.

16. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, further comprising providing a fail-over grid manager.

17. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein each affinity score is computed, at least in part, from information representing the amount of the requested service'"'"'s state that is already present on the engine-in-question.

18. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 1, wherein requested service(s) are first ranked according to neediness score(s), then assigned to engine(s) according to affinity score(s).

19. A method for providing computational services to a client using a grid-based distributed computing system, the system including a plurality of engines and at least one grid manager, the method comprising:

registering service(s) with the grid manager;

deploying executable code(s) corresponding to the registered service(s) using a file update mechanism to distribute the executable code(s) to the engines, wherein at least some of said executable codes(s) are distributed while the grid manager is idle;

creating instance(s) of the service(s) that permit invocation by client(s); and

,

using one or more of the instance(s) to invoke one or more of the registered service(s), wherein invoking a service comprises;

communicating a service request to the grid manager;

using the grid manager to assign the service request to an available engine by (1) computing a neediness score for the service request based, at least in part, on (i) a priority weight for the requested service, (ii) an amount of time that engines have spent running task(s) associated with the requested service, and (iii) an amount of time that the request for the service has spent waiting to be assigned, and (2) applying an adaptive scheduling algorithm to assign the service request to one or more available engine(s); and

,

executing code(s) corresponding to the requested service on at least one of the assigned engine(s).

20. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 19, wherein the adaptive scheduling algorithm selectively supports redundant scheduling.

21. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 19, further comprising deploying executable code corresponding to the registered service(s) on a shared file system accessible to the engines.

22. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 19, wherein said deploying of executable code occurs when the grid manager is idle.

23. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 19, wherein communicating a service request to the grid manager comprises synchronously invoking a client-side proxy that corresponds to the service.

24. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 19, wherein communicating a service request to the grid manager comprises asynchronously invoking a client-side proxy that corresponds to the service.

25. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 19, wherein communicating a service request to the grid manager comprises communicating a synchronous service request via a client-side wsdl proxy.

26. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 19, wherein communicating a service request to the grid manager comprises communicating an asynchronous service request via a client-side wsdl proxy.

27. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 19, wherein requested service(s) are first ranked according to neediness score(s), then assigned to engine(s) according to affinity score(s).

28. A method for providing computational services to a client using a grid-based distributed computing system, the system including a plurality of engines and at least one grid manager, the method comprising:

obtaining executable code corresponding one or more service(s);

registering the service(s);

providing client-side proxy(s) for the registered service(s); and

,

using one or more of the proxy(s) to invoke one or more of the registered service(s), wherein invoking a service comprises;

communicating a service request via a corresponding client-side proxy;

assigning the service request to at least one available engine by (i) obtaining a neediness score for the service request, said neediness score based on at least (a) an amount of time that engines have spent running task(s) associated with the service and (b) an amount of time that the request for the service has spent waiting to be assigned, (ii) obtaining affinity scores reflecting the affinity of available engine(s) to the requested service, and (iii) applying an adaptive scheduling algorithm to assign the service request to one or more available engine(s); and

,

servicing the request on at least one of the assigned engine(s).

29. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 28, wherein the service request is assigned based, at least in part, on the neediness score and one or more of the affinity score(s).

30. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 28, wherein the executable code is obtained from a shared file system accessible to the engines.

31. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 28, wherein communicating a service request comprises invoking a synchronous invocation method.

32. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 28, wherein communicating a service request comprises invoking an asynchronous invocation method.

33. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 28, wherein communicating a service request comprises communicating a synchronous service request via a client-side wsdl proxy.

34. A method for providing computational services to a client using a grid-based distributed computing system, as defined in claim 28, wherein communicating a service request comprises communicating an asynchronous service request via a client-side wsdl proxy.