Back to results
US 9,875,141 B2Granted
Managing pools of dynamic resources
AssigneeMicrosoft Technology Licensing, LLC
InventorsJoseph L. Hellerstein, Eric Lynn Eilebrecht, Vance Morrison, Paul Ringseth
Life of this patent
Estimating the term…
Abstract
Computer systems attempt to manage resource pools of a dynamic number of similar resources and work tasks in order to optimize system performance. Work requests are received into the resource pool having a dynamic number of resources instances. An instance-throughput curve is determined that relates a number of resource instances in the resource pool to throughput of the work requests. A slope of a point on the instance-throughput curve is estimated with stochastic gradient approximation. The number of resource instances for the resource pool is selected when the estimated slope of the instance-throughput curve is zero.
Claims19
A method of managing a resource pool comprising a dynamic number of resource instances executing work requests from a work queue, the number of thread instances in the resource pool based on a control setting which specifies a desired number of resources to be in the pool, the method comprising:
- retaining measurement information of the resource pool including a previous history of throughput measurements for a previous control setting and a current history of throughput measurements for a current control setting such that when a new control setting is established the current history becomes the previous history and the new control setting becomes the current control setting;
- entering an initializing state, the initializing state comprising:
- collecting throughput measurements of the thread pool operating at the current control setting until there is a plurality of throughput measurements in the current history and there is less than a selected threshold of variance for a mean throughput of the current history;
- and
- when there is less than the selected threshold of variance, establishing a first new control setting as the current control setting and exiting the initializing state;
- and
- in response to exiting the initializing state, entering a climbing state, the climbing state comprising:
- collecting throughput measurements of the resource pool operating at the current control setting until there is a plurality of throughput measurements in the current history and there is less than the selected threshold of variance for the mean throughput of the current history;
- when there is less than the selected threshold of variance, estimating, via stochastic gradient approximation, the slope of a point on an instance-throughput curve using the previous history, the previous control setting, the current history, and the current control setting, the instance-throughput curve relating the number of thread instances in the thread pool to throughput of the resource pool and the point corresponding to the desired number of resources specified in the current control setting;
- when the estimated slope is zero, reentering the climbing state;
- and
- when the estimated slope is not zero, calculating a next new control setting using the estimated slope, establishing the calculated next new control setting as the current control setting, and reentering the climbing state;
- the collecting throughput measurements in the initializing state and in the climbing state comprising receiving, from a measurement interface of the resource pool, a plurality of throughput measurements and for each received throughput measurement:
- receiving, from the measurement interface, an actual number of resources representing the number of resource instances executing work requests in the resource pool when the received throughput measurement was taken;
- comparing the desired number of resources specified in the current control setting to the actual number of resources;
- discarding the received throughput measurement if either the desired number of resources is less than the actual number of resources or the desired number of threads is greater than the actual number of resources and the work queue is not empty;
- adding the received throughput measurement to the current history if the received throughput measurement was not discarded;
- determining, by applying a change-point detection technique to the throughput measurements in the current history, whether the shape of the instance-throughput curve has changed;
- and
- in response to determining the shape of the instance-throughput curve has changed, deleting the previous and current history and reentering the initializing state.
17 more elements
A system for managing a thread pool comprising a dynamic number of thread instances to execute work requests from a work queue, the number of thread instances in the thread pool based on a control setting that specifies a desired number of threads to be in the pool, the system comprising:
- a memory to store a set of executable instructions;
- and
- a processor configured to execute the set of instructions to cause the system to:
- retain measurement information of the thread pool including a previous history of throughput measurements for a previous control setting and a current history of throughput measurements for a current control setting such that when a new control setting is established the current history becomes the previous history and the new control setting becomes the current control setting;
- enter an initializing state, the initializing state comprising the system being caused to:
- collect throughput measurements of the thread pool operating at the current control setting until there is a plurality of throughput measurements in the current history and there is less than a selected threshold of variance for a mean throughput of the current history;
- and
- when there is less than the selected threshold of variance, establish a first new control setting as the current control setting and exit the initializing state;
- and
- in response to exiting the initializing state, enter a climbing state, the climbing state comprising the system being caused to:
- collect throughput measurements of the thread pool operating at the current control setting until there is a plurality of throughput measurements in the current history and there is less than the selected threshold of variance for the mean throughput of the current history;
- when there is less than the selected threshold of variance, estimate, via stochastic gradient approximation, the slope of a point on an instance-throughput curve using the previous history, the previous control setting, the current history, and the current control setting, the instance-throughput curve relating the number of thread instances in the thread pool to throughput of the thread pool and the point corresponding to the desired number of threads specified in the current control setting;
- when the estimated slope is zero, reenter the climbing state;
- and
- when the estimated slope is not zero, calculate a next new control setting using the estimated slope, establish the calculated next new control setting as the current control setting, and reenter the climbing state;
- the system being caused to collect throughput measurements in the initializing state and in the climbing state comprising the system being caused to receive, from a measurement interface of the thread pool, a plurality of throughput measurements and for each received throughput measurement:
- receive, from the measurement interface, an actual number of threads representing the number of thread instances executing work requests in the thread pool when the received throughput measurement was taken;
- compare the desired number of threads specified in the current control setting to the actual number of threads;
- discard the received throughput measurement if either the desired number of threads is less than the actual number of threads or the desired number of threads is greater than the actual number of threads and the work queue is not empty;
- add the received throughput measurement to the current history if the received throughput measurement was not discarded;
- determine, by applying a change-point detection technique to the throughput measurements in the current history, whether the shape of the instance-throughput curve has changed;
- and
- in response to the shape of the instance-throughput curve having changed, delete the previous and current history and reenter the initializing state.
20 more elements
A computer-readable storage medium, which does not include a transitory propagating signal, to store computer-executable instructions to manage a thread pool comprising a dynamic number of thread instances to execute work requests from a work queue, the number of thread instances in the thread pool based on a control setting that specifies a desired number of threads to be in the pool, the instructions, when executed by a processor, cause the processor to:
- retain measurement information of the thread pool including a previous history of throughput measurements for a previous control setting and a current history of throughput measurements for a current control setting such that when a new control setting is established the current history becomes the previous history and the new control setting becomes the current control setting;
- enter an initializing state, the initializing state comprising the processor being caused to:
- collect throughput measurements of the thread pool operating at the current control setting until there is a plurality of throughput measurements in the current history and there is less than a selected threshold of variance for a mean throughput of the current history;
- and
- when there is less than the selected threshold of variance, establish a first new control setting as the current control setting and exit the initializing state;
- and
- in response to exiting the initializing state, enter a climbing state, the climbing state comprising the processor being caused to:
- collect throughput measurements of the thread pool operating at the current control setting until there is a plurality of throughput measurements in the current history and there is less than the selected threshold of variance for the mean throughput of the current history;
- when there is less than the selected threshold of variance, estimate, via stochastic gradient approximation, the slope of a point on an instance-throughput curve using the previous history, the previous control setting, the current history, and the current control setting, the instance-throughput curve relating the number of thread instances in the thread pool to throughput of the thread pool and the point corresponding to the desired number of threads specified in the current control setting;
- when the estimated slope is zero, reenter the climbing state;
- and
- when the estimated slope is not zero, calculate a next new control setting using the estimated slope, establish the calculated next new control setting as the current control setting, and reenter the climbing state;
- the processor being caused to collect throughput measurements in the initializing state and in the climbing state comprising the processor being caused to receive, from a measurement interface of the thread pool, a plurality of throughput measurements and for each received throughput measurement:
- receive, from the measurement interface, an actual number of threads representing the number of thread instances executing work requests in the thread pool when the received throughput measurement was taken;
- compare the desired number of threads specified in the current control setting to the actual number of threads;
- discard the received throughput measurement if either the desired number of threads is less than the actual number of threads or the desired number of threads is greater than the actual number of threads and the work queue is not empty;
- add the received throughput measurement to the current history if the received throughput measurement was not discarded;
- determine, by applying a change-point detection technique to the throughput measurements in the current history, whether the shape of the instance-throughput curve has changed;
- and
- in response to the shape of the instance-throughput curve having changed, delete the previous and current history and reenter the initializing state.
17 more elements
Dependencies are inferred from the claim text.