Distributed scheduling in a multiple data server system

• US 5,867,657 A
• Filed: 06/06/1996
• Issued: 02/02/1999
• Est. Priority Date: 06/06/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bolosky, William J., Fitzgerald, Robert P.
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US08/684,840
• Time in Patent Office: 971 Days
• Field of Search: 395/200.3, 395/200.47, 395/200.49, 395/553, 395/559, 395/672, 395/673, 395/826, 395/865
• US Class Current: 725/115
• CPC Class Codes: G06F 11/2035 without idle spare hardware
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G11B 27/002 Programmed access in sequence to a plurality of record carriers or indexed parts, e.g. tracks, thereof, e.g. for editing; transfer of record carriers from magazine G11B15/68, G11B17/10; G11B17/22
• CPC Class Codes: H04N 7/17318 Direct or substantially direct transmission and handling of requests
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

The scheduling functionality for a distributed system having multiple data servers is spread across the data servers rather than being centralized at a single machine. The distribution of the scheduling across multiple servers enhances the scalability of the system and enhances the fault tolerance of the system. Viewer state records are employed that contain scheduling information for viewers. Scheduling occurs by circulating the viewer state records amongst the data servers that are to provide the requisite data. The data servers output data blocks in a predetermined sequence based on how the data blocks are striped across the data servers. Each viewer state record is forwarded to a first successor and second successors in the scheduling sequence. The task of adding a viewer to a schedule is also distributed to the data servers.

Claims

1. A computer-readable storage medium for use in a distributed system having multiple data servers upon which data blocks of a data sequence are stored, said medium holding instructions for performing the computer-implemented steps of:

forwarding an object that encapsulates scheduling information for reading of the data blocks of the data sequence to each of the data servers that stores a data block of the data sequence;

wherein in response to receiving the object, each data server schedules reading of a selected one of the data blocks that it stores, said selected data block being identified by the scheduling information in the object; and

sequentially reading the selected data blocks from consecutive ones of the data servers according to the scheduled reading to produce the data sequence for distribution.

2. The computer-readable storage medium of claim 1, further holding instructions for forwarding redundant copies of the object to each of the data servers that stores a data block of the data sequence to enhance fault tolerance.

3. The computer-readable storage medium of claim 1 wherein the scheduling information specifies a file that holds the data blocks of the data sequence.

4. The computer-readable storage medium of claim 3 wherein the scheduling information specifies what data block in the data file is to be read next.

5. The computer-readable storage medium of claim 1 wherein the medium also holds instructions, for each data server for updating the scheduling information encapsulated into the object to identify a next data block to be read after receiving the object.

6. The computer-readable storage medium of claim 1 wherein the data blocks hold multimedia data.

7. The computer-readable storage medium of claim 1 wherein the distributed system is a video-on-demand system.

8. The computer-readable storage medium of claim 1, wherein said object includes:

an indication of which selected block in the data sequences is to be output;

an indication of what file contains the selected block;

an indication of where the selected block is to be output; and

an indication of when the selected block is to be output.

9. The computer-readable storage medium of claim 8 wherein the object also includes an indication of whether the block is a mirrored secondary block.

10. A computer-readable storage medium for use in a distributed system having storage devices upon which are stored data blocks of a data sequence and data servers for reading the data blocks from the storage devices, said medium holding instructions for performing the computer-implemented steps of:

in response to receiving a viewer state record at a first of the data servers that encapsulates scheduling information for a read operation of a selected data block of a data sequence, scheduling the read operation of the selected data block at the first of the data servers; and

forwarding the viewer state record from the first data server to a second of the data servers that is responsible for reading a next data block of the data sequence after the selected data block and forwarding the viewer state record to a third of the data servers that is responsible for reading a data block after the next data block in the data sequence, for scheduling.

11. The computer-readable storage medium of claim 10, also holding instructions for ignoring a second viewer state record in response to receiving the second viewer state record at the first data server when a viewer state record like the second viewer state record has already been received at the first data server.

12. The computer-readable storage medium of claim 10, further holding instructions for performing the scheduled read operation of the selected data block at the first of the data servers.

13. A computer-readable storage medium for use in a distributed system having video data servers for storing sequences of video data, said medium holding instructions for performing a method of distributed scheduling, comprising the computer-implemented steps of:

receiving a scheduling data structure at a selected one of the video data servers, said scheduling data structure holding information about an operation on a file to be scheduled by the selected video data server;

in response to receiving the scheduling data structure, scheduling the operation on the file at the selected video data server; and

updating the scheduling data structure and forwarding the scheduling data structure to a next of the video data servers that is to perform an operation on the file.

14. The computer-readable storage medium of claim 13 wherein the updating comprises specifying a next block of data to be read in a data sequence held in the file.

15. In a computer system having data servers with storage devices across which data blocks of data sequences are striped, said data servers being organized into a defined sequence, a method comprising the computer-implemented steps of:

dividing time into a repeating cycle of time slices for each data server, wherein a time slice is a sufficient amount of time to output a data block by one of the data servers and each data server has a like cycle of time slices such that each time slice has a position in the cycle and each cycle of a data server is offset in time relative to the cycle of its predecessor data server in the sequence of data servers;

designating aggregates of like positioned time slices in cycles of the data server as slots;

for a given slot, designating a time at which a selected one of the data servers owns the given slot such that only the selected data server is permitted to output a data block to a specified viewer at the time; and

at the designated time at which the selected data server owns the given slot, scheduling outputting of an identified data sequence by assigning the specified viewer to the given slot by the selected data server such that during time slices that make up the given slot, data blocks of the identified data sequence are output from the data servers to the specified viewer.

16. The method of claim 15, further comprising the steps of:

for an additional slot, designating a second time at which an additional one of the data servers owns the additional slot such that only the additional data server is permitted to output a data block to a given viewer at that second time; and

at the designated second time, scheduling outputting of a given data sequence by assigning the given viewer to the additional slot by the additional data server such that during time slices that make up the additional slot, data blocks of the given data sequence are output from the data servers to the given viewer.

17. In a distributed system having multiple data servers upon which data blocks of a data sequence are stored, a method of distributed scheduling of reading of the data blocks of the data sequence, comprising the computer-implemented steps of:

forwarding an object that encapsulates scheduling information for reading of the data blocks of the data sequence to each of the data servers that stores a data block of the sequence;

wherein in response to receiving the object, each data server schedules reading of a selected one of the data blocks that it stores as identified by the scheduling information in the object; and

sequentially reading the selected data blocks from consecutive ones of the data servers according to the scheduled reading to produce the data sequence for distribution.

18. The method of claim 17 wherein the forwarding is performed by each data server after the data server receives the object.

19. The method of claim 17, further comprising the step of forwarding redundant copies of the object to at least one of the data servers that stores a block of the data sequence to enhance fault tolerance.

20. In a distributed system having video data servers for storing sequences of video data, a method of distributed scheduling comprising the computer-implemented steps of:

receiving a scheduling data structure at a selected one of the video data servers, said scheduling data structure holding information about an operation on a file to be scheduled by the selected data server;

in response to receiving the scheduling data structure, scheduling the operation on the file at the selected video data server; and

updating the scheduling data structure and forwarding the scheduling data structure to a next of the video data servers that is to perform an operation on the file.

21. The method of claim 20 wherein the operation is a read operation for reading video data from the file.

22. The method of claim 20 wherein the distributed system is a video-on-demand system.

23. In a distributed system having storage devices upon which are stored data blocks of a data sequence and data servers for reading the data blocks from the storage devices, a method comprising the computer-implemented steps of:

passing a viewer state record that encapsulates scheduling information for a read operation of a selected data block of a data sequence to a first of the data servers;

in response to receiving the viewer state record, scheduling the read operation of the selected data block at the first of the data servers; and

forwarding the viewer state record from the first data server to a second of the data servers that is responsible for reading a next data block of the data sequence after the selected data block and forwarding the viewer state record to a third of the data servers that is responsible for reading a data block after the next data block in the data sequence for scheduling.

24. A distributed system, comprising:

storage devices for storing data blocks of a data sequence;

multiple data servers for reading the data blocks from the storage devices, wherein each data server has at least one of the storage devices from which it may read data;

a distributed schedule distributed among the data servers so that each data server holds a portion of the schedule, the distributed schedule defining when the data servers read selected data blocks, information within the distributed schedule being contained in objects that can be passed among the data servers;

a connection mechanism for connecting the data servers so that the objects may be forwarded among the data servers to prompt the data servers to schedule the reading of the data blocks of the data sequence; and

a network switch connected to the data servers to receive the data blocks read by the data servers, order the data blocks into the data sequence, and distribute the data sequence over a network.

25. In a computer system having video servers for providing video sequences to viewers in accordance with a schedule that is divisible into slots, a method comprising the computer-implemented steps of:

distributing among the video servers portions of the schedule so that individual video servers view different portions of the schedule but no one video server views the schedule in its entirety;

at a first of the video servers, applying an assignment protocol to determine a first slot in the schedule where a first of the viewers is to be scheduled to receive one of the video sequences and scheduling the first viewer in the first slot of the schedule; and

at a second of the video servers, applying an assignment protocol to determine a second slot in the schedule where a second of the viewers is to be scheduled to receive another of the video sequences and scheduling the second viewer server in the second slot of the schedule.

26. A computer-readable storage medium for use in a computer system having video servers for providing video sequences to viewers in accordance with a schedule that is divisible into slots, said medium holding instructions for performing the steps of:

distributing among the video servers portions of the schedule so that individual video servers view different portions of the schedule but no one video server views the schedule in its entirety;

at a first of the video servers, applying an assignment protocol to determine a first slot in the schedule where a first of the viewers is to be scheduled to receive one of the video sequences and scheduling the first viewer in the first slot of the schedule; and

at a second of the video servers, applying an assignment protocol to determine a second slot in the schedule where a second of the viewers is to be scheduled to receive another of the video sequences and scheduling the second viewer server in the second slot of the schedule.

27. In a computer system having multiple data servers in which a first data server holds a primary block of data and one or more other data servers hold secondary blocks of data that in aggregate form the primary block of data, a computer-readable storage medium holding instructions for performing a method comprising the steps of:

distributing among the video servers portions of the schedule so that individual video servers view different portions of the schedule but no one video server views the schedule in its entirety;

detecting failure of the first server to output the primary block of data when scheduled; and

outputting the secondary blocks from the one or more other data servers in place of the primary block of data.

28. The computer-readable storage medium of claim 27, further holding instructions for performing the step of scheduling output of the secondary block of data held at the second server to the destination via the data funnel.

29. The computer-readable storage medium of claim 28, further holding instructions for performing the step of forwarding the mirror view state record to the third server.

30. In a distributed system having multiple data servers connected to distribute data sequences 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 of:

distributing among the data servers a schedule for serving requested ones of the data sequences so that individual data servers view different portions of the schedule but no one data server views the schedule in its entirety; and

reading selected data blocks from the storage devices at the data servers according the schedule portions viewed by the data servers.

31. The method of claim 30, further comprising the step of cycling the schedule portions among the data servers so that the data servers read the data blocks sequentially to produce the requested ones of the data sequences.

32. The method of claim 30, wherein the schedule is segmented into slots to which the data sequences are assigned for coordinating service of the data sequences, individual data servers having ownership of a current slot within their respective schedule portions.

33. The method of claim 30, further comprising the steps of:

receiving at a particular data server a request to insert a new data stream into the current slot in the schedule portion 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.

34. The distributed system of claim 30, wherein the data servers pass objects that encapsulate scheduling information for reading the data blocks.

35. The distributed system of claim 30, wherein the data servers comprise video servers, and the distributed schedule schedules continuous distribution of the data blocks to form a streaming video sequence.

36. A distributed 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 device;

a distributed schedule distributed among the multiple data servers so that each data server holds a portion of the schedule but no one data server holds all of the schedule, the distributed schedule defining when selected data blocks are read by corresponding ones of the data servers to serve a data sequence; and

the data servers cycling the schedule portions among themselves to continue service of the data sequence.