Pre-allocating resources with hierarchy-based constraints

Abstract

In a resource-pooling system, predictions can be made as to when and how resources may be needed by particular processes in the system. Requests can be made preemptively to client systems to pre-allocate resources such that resources are ready to use when needed. Client systems can submit constraints on how particular resources may be used by the system. In order to efficiently evaluate these constraints, the system may be organized into a hierarchy of groups, subsystems, and processes, and the constraints may be formulated to match this hierarchy. When resources need to be allocated, constraints may be evaluated using an algorithm that traverses levels of the hierarchy to quickly identify pre-allocations that are available for a particular process based on its location in the system hierarchy.

What is claimed is: 
     
       1. A non-transitory computer-readable medium comprising instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:
 organizing a plurality of subsystems in a system into a hierarchy of subsystems; 
 receiving a pre-allocation of a resource from a first client system and a constraint on how the resource can be used, wherein the resource is provided by the first client system, wherein the constraint indicates a portion of the hierarchy of subsystems that can use the resource, wherein the resource is reserved to the portion of the hierarchy of subsystems without yet being allocated to any specific process in the portion of the hierarchy of subsystems; 
 receiving a request for the resource for a process assigned to a subsystem in the hierarchy of subsystems; 
 determining whether the location of the process in the hierarchy of subsystems fulfills the constraint; and 
 in response to determining that the location of the process in the hierarchy of subsystems fulfills the constraint, allocating the resource to the process such that an amount of the resource is removed from the pre-allocation of the resource reserved to the portion of the hierarchy of subsystems and assigned to the process. 
 
     
     
       2. The non-transitory computer-readable medium of  claim 1 , wherein the operations further comprise:
 sending a request to a plurality of client systems to pre-allocate the resource to the system, wherein the request is based on a total resource expected to be used by a subsystem or process in the system, and individual requests to each of the plurality of client systems are based on percentage amounts assigned to each of the plurality of client systems. 
 
     
     
       3. The non-transitory computer-readable medium of  claim 1 , wherein the constraint identifies a specific process assigned to the subsystem for which the resource may be allocated. 
     
     
       4. The non-transitory computer-readable medium of  claim 1 , wherein the constraint identifies the subsystem such that the resource may be allocated to any process assigned to the subsystem. 
     
     
       5. The non-transitory computer-readable medium of  claim 1 , wherein the hierarchy of subsystems comprises one or more groups, wherein a group comprises a plurality of parent-child relationships within the hierarchy of subsystems that separates the group from other parent-child relationships in the hierarchy of subsystems. 
     
     
       6. The non-transitory computer-readable medium of  claim 5 , wherein the constraint identifies a group in the one or more groups such that the resource may be allocated to any process assigned to any subsystem in the group. 
     
     
       7. The non-transitory computer-readable medium of  claim 1 , wherein the constraint identifies the system such that the resource may be allocated to any process assigned to any subsystem in the system. 
     
     
       8. The non-transitory computer-readable medium of  claim 1 , wherein the operations further comprise:
 storing a data structure comprising an entry for each pre-allocation of resources, wherein each entry comprises an amount of the resource that has been pre-allocated, and a hierarchy of constraints based on the constraint. 
 
     
     
       9. The non-transitory computer-readable medium of  claim 8 , wherein the hierarchy of constraints comprises a plurality of fields, wherein each of the plurality of fields corresponds to a dimension in the hierarchy of subsystems. 
     
     
       10. The non-transitory computer-readable medium of  claim 9 , wherein the plurality of fields comprises values for a system identifier, a group identifier, a subsystem identifier, and a process identifier. 
     
     
       11. The non-transitory computer-readable medium of  claim 10 , wherein determining whether the location of the process in the hierarchy of subsystems fulfills the constraint comprises evaluating each field in the plurality of fields of the hierarchy of constraints, beginning with the process identifier and moving sequentially to the system identifier to determine whether each field in the hierarchy of constraints is fulfilled. 
     
     
       12. The non-transitory computer-readable medium of  claim 11 , wherein a field in the hierarchy of constraints is fulfilled if the value of the field matches a corresponding value for the process or if the value of the field is null. 
     
     
       13. The non-transitory computer-readable medium of  claim 1 , wherein the operations further comprise:
 automatically generating an entry in an update table indicating an amount of the resource used by the process. 
 
     
     
       14. The non-transitory computer-readable medium of  claim 13 , wherein the operations further comprise:
 processing each entry in the update table to update an amount of resources still pre-allocated for the system after the process uses the resource. 
 
     
     
       15. The non-transitory computer-readable medium of  claim 1 , wherein the operations further comprise:
 determining that the request for the resource requires an amount of the resource greater than what has been pre-allocated. 
 
     
     
       16. The non-transitory computer-readable medium of  claim 15 , wherein the operations further comprise:
 generating requests to a plurality of client systems to allocate resources sufficient to provide the amount of the resource required by the process. 
 
     
     
       17. The non-transitory computer-readable medium of  claim 1 , wherein a constraint identifying a specific subsystem in the hierarchy of subsystems may be fulfilled by a process assigned to the specific subsystem, but may not be fulfilled by a process assigned to a child subsystem of the specific subsystem in the hierarchy of subsystems. 
     
     
       18. The non-transitory computer-readable medium of  claim 1 , wherein the constraint identifies a range of process identifiers that may fulfill the constraint. 
     
     
       19. A method of pre-allocating resources with hierarchy-based constraints, the method comprising:
 organizing a plurality of subsystems in a system into a hierarchy of subsystems; 
 receiving a pre-allocation of a resource from a first client system and a constraint on how the resource can be used, wherein the resource is provided by the first client system, wherein the constraint indicates a portion of the hierarchy of subsystems that can use the resource, wherein the resource is reserved to the portion of the hierarchy of subsystems without yet being allocated to any specific process in the portion of the hierarchy of subsystems; 
 receiving a request for the resource for a process assigned to a subsystem in the hierarchy of subsystems; 
 determining whether the location of the process in the hierarchy of subsystems fulfills the constraint; and 
 in response to determining that the location of the process in the hierarchy of subsystems fulfills the constraint, allocating the resource to the process such that an amount of the resource is removed from the pre-allocation of the resource reserved to the portion of the hierarchy of subsystems and assigned to the process. 
 
     
     
       20. A system comprising:
 one or more processors; and 
 one or more memory devices comprising instructions that, when executed by the one or more processors, cause the system to perform operations comprising:
 organizing a plurality of subsystems in a system into a hierarchy of subsystems; 
 receiving a pre-allocation of a resource from a first client system and a constraint on how the resource can be used, wherein the resource is provided by the first client system, wherein the constraint indicates a portion of the hierarchy of subsystems that can use the resource, wherein the resource is reserved to the portion of the hierarchy of subsystems without yet being allocated to any specific process in the portion of the hierarchy of subsystems; 
 receiving a request for the resource for a process assigned to a subsystem in the hierarchy of subsystems; 
 determining whether the location of the process in the hierarchy of subsystems fulfills the constraint; and 
 in response to determining that the location of the process in the hierarchy of subsystems fulfills the constraint, allocating the resource to the process such that an amount of the resource is removed from the pre-allocation of the resource reserved to the portion of the hierarchy of subsystems and assigned to the process.