Back to results
US 8,949,489 B1Granted
Method for combining bulk and latency-sensitive input and output
AssigneeGoogle Inc.
InventorArif Merchant
Life of this patent
Estimating the term…
Abstract
Systems, mediums, and methods are provided for scheduling input/output requests to a storage system. The input output requests may be received, categorized based on their priority, and scheduled for retrieval from the storage system. Lower priority requests may be divided into smaller sub-requests, and the sub-requests may be scheduled for retrieval only when there are no pending higher priority requests, and/or when higher priority requests are not predicted to arrive for a certain period of time. By servicing the small sub-requests rather than the entire lower priority request, the retrieval of the lower priority request may be paused in the event that a high priority request arrives while the lower priority request is being serviced.
Claims30
A computing system, comprising:
- one or more request queues for holding input/output requests for data from a data storage, the input/output requests comprising:
- non-latency-sensitive input/output requests, wherein the computing system divides the non-latency-sensitive input/output requests into a plurality of sub-requests;
- and
- latency-sensitive input/output requests;
- an idle period analyzer for identifying when an idle period of latency-sensitive input/output requests is in effect, wherein the idle period analyzer determines a conditional probability that a next latency-sensitive input/output request will arrive prior to a completion of a next non-latency-sensitive sub-request, and schedules the next non-latency-sensitive sub-request when the conditional probability is below a specified threshold;
- and
- a scheduler for:
- scheduling the sub-requests when the idle period analyzer determines that the idle period is in effect, wherein the scheduler schedules at least two of the sub-requests sequentially while the idle period is in effect, and
- scheduling the latency-sensitive input/output requests when the latency-sensitive input/output requests are received.
6 more elements
An electronic device implemented method, comprising:
- identifying a first request to access first data stored in a data storage, the first request being a non-latency-sensitive request;
- dividing the first request into a plurality of sub-requests;
- queuing the sub-requests for retrieval from the data storage, wherein the sub-requests are queued so that at least two sub-requests are scheduled for retrieval such that when a first sub-request completes, a second sub-request is prepared for retrieval;
- queuing the sub-requests for retrieval from the data storage by:
- determining a conditional probability that a latency-sensitive input/output request will arrive prior to completion of a next non-latency-sensitive sub-request,
- identifying an idle period when the conditional probability is below a specified threshold,
- and scheduling the next non-latency-sensitive sub-request for the idle period,
- wherein the sub-requests are queued so that at least two sub-requests are scheduled for retrieval such that when a first sub-request completes, a second sub-request is prepared for retrieval;
- identifying a second request to access second data in the data storage, the second request being a latency-sensitive request;
- queuing the second request preferentially over a further sub-request of the first request so that the second request is scheduled prior to the further sub-request of the first request.
7 more elements
A non-transitory electronic device readable storage medium holding instructions that, when executed, cause one or more processors to:
- identify a first request to access first data stored in a data storage;
- identify that the first request is a non-latency-sensitive request;
- divide the first request into a plurality of sub-requests;
- queue the sub-requests for retrieval from the data storage by:
- determining a conditional probability that a latency-sensitive input/output request will arrive prior to completion of a next non-latency-sensitive sub-request,
- identifying an idle period when the conditional probability is below a specified threshold,
- and scheduling the next non-latency-sensitive sub-request for the idle period;
- fetch data that is the subject of each sub-request continuously so that a second sub-requests is fetched immediately after a first sub-request;
- identify a second request to access second data in the data storage;
- identify that the second request is a latency-sensitive request;
- queue the second request preferentially over a further sub-request of the first request.
8 more elements
A server for storing and manipulating data, the server comprising:
- a non-latency-sensitive request queue for holding non-latency-sensitive input/output requests for data stored in a data storage, wherein the non-latency-sensitive input/output requests are divided into a plurality of sub-requests and received via a network;
- a latency-sensitive request queue for holding latency-sensitive input/output requests for data stored in the data storage, wherein the latency-sensitive input/output requests are received via the network;
- an idle period analyzer for identifying when an idle period of latency-sensitive input/output requests is in effect, wherein the idle period analyzer determines a conditional probability that a next latency-sensitive input/output request will arrive prior to a completion of a next non-latency-sensitive sub-request, and schedules the next non-latency-sensitive sub-request when the conditional probability is below a specified threshold;
- and
- a scheduler for:
- scheduling the sub-requests when the idle period analyzer determines that the idle period is in effect, wherein the scheduler schedules at least two of the sub-requests sequentially while the idle period is in effect, and
- scheduling the latency-sensitive input/output requests when the latency-sensitive input/output requests are received;
- and
- an output port for transmitting a result of the non-latency-sensitive input/output requests and the latency-sensitive input/output requests over the network.
6 more elements
Dependencies are inferred from the claim text.