File server system and method for scheduling data streams according to a distributed scheduling policy

• US 20020143979A1
• Filed: 04/12/2002
• Published: 10/03/2002
• Est. Priority Date: 03/10/1999
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bolosky, William J., Douceur, John R.
• Granted Patent: US 7,146,424 B2
• Time in Patent Office: Days
• US Class Current: 709/231
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04N 21/2326 Scheduling disk or memory reading operations
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A distributed file server system has multiple data servers connected to stream data files continuously over a network to multiple clients. Each data server supports at least one storage device, such as a disk. Data files are distributed across the data servers so that data blocks of the data files are stored on each of the storage devices. The file server system has a scheduler located at each of the data servers to manage distributed portions of a schedule. Each data server sees a different portion of the schedule, but no one data server sees the whole schedule. The scheduler facilitates service of requested data streams from its corresponding data server according to a schedule portion that is available to the data server. The scheduler determines whether to insert a new data stream into the current slot it presently owns in its schedule portion, or to wait for a subsequent slot in the schedule. The scheduler follows a thrifty policy that attempts to maximize spacing of occupied slots as far apart as possible within the schedule, while minimizing the clustering of occupied slots. The scheduler also factors in a maximum acceptable slippage that dictates the highest number of slots that the scheduler is willing to slip in the schedule before starting the new data stream. The end result is an even distribution of the occupied slots within the schedule that reduces startup latency for late schedule insertion at the expense of slightly prolonging the startup latency of early schedule insertions.

Claims

1. In a file server system having multiple data servers connected to distribute data streams over a network, each data server supporting at least one storage device, wherein data files are distributed across the data servers and stored on each of the storage devices, a method comprising the following steps:

distributing among the data servers a schedule for serving requested ones of the data streams so that individual data servers view different portions of the schedule, the schedule being segmented into slots to which data streams are assigned for coordinating service of the requested data streams, the individual data servers having ownership of a current slot within their respective portions of the schedule;

receiving at a particular data server a request to insert a new data stream into the current slot in the portion of the schedule currently being viewed by the particular data server; and

evaluating at the particular data server whether to insert the new data stream into the current slot or to wait for a subsequent slot in the schedule based upon a distribution criteria indicating whether said insertion into the current slot, in comparison to said waiting for a subsequent slot, would result in a less even distribution of the scheduled data streams within the schedule.

2. A method as recited in claim 1, wherein the evaluating step includes the step of calculating an insertion spread indicating a number of contiguous vacant slots in the portion of the schedule currently being viewed by the particular data server.

3. A method as recited in claim 1, wherein the evaluating step includes the step of calculating an insertion width indicating a number of contiguous occupied slots in the portion of the schedule currently being viewed by the particular data server.

4. A method as recited in claim 1, wherein the evaluating step comprises the following steps:

calculating an insertion spread indicating a number of contiguous vacant slots in the portion of the schedule currently being viewed by the particular data server;

calculating an insertion width indicating a number of contiguous occupied slots in the portion of the schedule currently being viewed by the particular data server; and

choosing between inserting the new data stream into the current slot and waiting for a subsequent slot in a manner that maximizes the insertion spread and minimizes the insertion width.

5. A computer programmed to perform the steps recited in the method of claim 1.

6. A computer-readable medium having computer-executable instructions for performing the steps of the method as recited in claim 1.

7. In a distributed file server system having multiple data servers connected to distribute data streams over a network, each data server supporting at least one storage device, wherein data files are distributed across the data servers and stored on each of the storage devices, wherein a schedule for serving requested ones of the data streams is distributed among the data servers so that that individual data servers view different portions of the schedule, the schedule being segmented into slots to which data streams are assigned for coordinating service of the requested data streams, a method for operating one of the data servers comprising the following steps:

receiving a portion of the schedule;

making assumptions as to whether slots preceding the schedule portion and following the schedule portion are occupied; and

determining whether a new data stream should be inserted into the schedule portion based upon a policy that attempts to maximize distances between consecutively occupied slots and minimize contiguously occupied slots.

8. A method as recited in claim 7, wherein the making step comprises the step of assuming all future slots following the schedule portion are occupied.

9. A method as recited in claim 7, wherein the making step comprises the step of assuming all past slots preceding the schedule portion have an occupancy density approximately equal to that of the schedule portion.

10. A method as recited in claim 9, further comprising the step of deriving a bound representing a maximum number of past slots preceding the schedule portion on which said assumptions will be made.

11. A method as recited in claim 7, further comprising the step of tracking a number of contiguously vacant slots preceding the schedule portion.

12. A method as recited in claim 7, wherein the determining step comprises the step of computing the distances between the consecutively occupied slots.

13. A method as recited in claim 7, wherein the determining step comprises the step of deriving a highest number of the contiguously occupied slots.

14. A computer programmed to perform the steps recited in the method of claim 7.

15. A computer-readable medium having computer-executable instructions for performing the steps of the method as recited in claim 7.

17. A method as recited in claim 16, wherein the examining step comprises determining whether all of the queued requests can be inserted into the schedule under the policy without exceeding a preset slip period measured as a time between when a request is received and when a corresponding data stream is served.

18. A method as recited in claim 16, further comprising the step of distributing the schedule among the data servers so that that individual data servers view different portions of the schedule, wherein the receiving, queuing, and examining steps are performed locally at individual ones of the data servers.

19. A method as recited in claim 16, further comprising the step of maintaining a central schedule which is used to coordinate service of the requested data streams, wherein the receiving, queuing, and examining steps are performed centrally.

20. A method as recited in claim 16, wherein the examining step comprises the step of computing the distances between the consecutively occupied slots.

21. A method as recited in claim 16, wherein the examining step comprises the step of deriving a highest number of the contiguously occupied slots.

22. A computer programmed to perform the steps recited in the method of claim 16.

23. A computer-readable medium having computer-executable instructions for performing the steps of the method as recited in claim 16.

25. A continuous media file server system as recited in claim 24, wherein the scheduler is configured to assume all future slots following the schedule portion are occupied.

26. A continuous media file server system as recited in claim 24, wherein the scheduler is configured to assume all past slots preceding the schedule portion have an occupancy density approximately equal to that of the schedule portion.

27. A continuous media file server system as recited in claim 26, wherein the scheduler is configured to derive a bound representing a maximum number of past slots preceding the schedule portion on which said assumptions will be made.

28. A continuous media file server system as recited in claim 24, wherein the scheduler is configured to track a number of contiguously vacant slots preceding the schedule portion.

29. A continuous media file server system as recited in claim 24, wherein the scheduler is configured to compute the distances between the consecutively occupied slots.

30. A continuous media file server system as recited in claim 24, wherein the scheduler is configured to derive a highest number of the contiguously occupied slots.

16. In a file server system having multiple data servers connected to distribute data streams over a network, each data server supporting at least one storage device, wherein data files are distributed across the data servers and stored on each of the storage devices, the system maintaining a schedule for serving requested ones of the data streams, the schedule being segmented into slots to which data streams are assigned for coordinating service of the requested data streams, a method comprising the following steps:

receiving multiple requests to insert new data streams into the schedule;

queuing the requests in a queue; and

examining the schedule to determine whether all of the queued requests can be inserted into the schedule under a policy that attempts to maximize distances between consecutively occupied slots and minimize contiguously occupied slots.

24. A continuous media file server system, comprising:

multiple data servers, each data server supporting at least one storage device, wherein data files are distributed across the data servers so that data blocks of the data files are stored on each of the storage devices;

multiple schedulers located at corresponding ones of the data servers, each scheduler facilitating service of requested data streams from its corresponding data server according to a portion of a schedule that is available to the scheduler, the schedule portion having slots which are assigned to the requested data streams; and

each scheduler being configured to make assumptions as to whether slots preceding the schedule portion and following the schedule portion are occupied as having been assigned to a requested data stream, each scheduler determining whether a new data stream can be inserted into the schedule portion based upon a policy that attempts to maximize distances between consecutively occupied slots and minimize contiguously occupied slots.

31. A file server system, comprising:

multiple data servers, each data server supporting at least one storage device, wherein data files are distributed across the data servers so that data blocks of the data files are stored on each of the storage devices;

a scheduler to coordinate service of requested data streams from the data servers according to a schedule;

a queue to hold multiple requests to insert new data streams into the schedule; and

the scheduler being configured to examine the schedule to determine whether all of the queued requests can be inserted into the schedule under a policy that attempts to maximize distances between consecutively occupied slots and minimize contiguously occupied slots.

32. A file server system as recited in claim 31, further comprising a controller coupled to the data servers, wherein the scheduler resides at the controller.

33. A file server system as recited in claim 31, wherein the scheduler resides at each of the data servers.

34. A file server system as recited in claim 31, wherein the scheduler determines whether all of the queued requests can be inserted into the schedule under the policy without exceeding a preset slip period measured as a time between when a request is received and when a corresponding data stream is served.

35. A scheduler embodied as a computer program on a computer-readable medium, the scheduler being implemented in a distributed file server system having multiple data servers connected to distribute data streams over a network, each data server supporting at least one storage device, wherein data files are distributed across the data servers and stored on each of the storage devices, wherein a schedule for serving requested ones of the data streams is distributed among the data servers so that that individual data servers view different portions of the schedule, the schedule being segmented into slots to which data streams are assigned for coordinating service of the requested data streams, the scheduler comprising:

code means for receiving a portion of the schedule;

code means for making assumptions as to whether slots preceding the schedule portion and following the schedule portion are vacant or occupied; and

code means for determining whether a new data stream can be inserted into the schedule portion based upon a policy that attempts to maximize distances between consecutively occupied slots and minimize contiguously occupied slots.