Distributed scheduling in a multiple data server system
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
36 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12)
-
-
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. - View Dependent Claims (14)
-
-
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. - View Dependent Claims (16)
-
-
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. - View Dependent Claims (18, 19)
-
-
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. - View Dependent Claims (21, 22)
-
-
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. - View Dependent Claims (28, 29)
-
-
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. - View Dependent Claims (31, 32, 33, 34, 35)
-
-
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.
-
Specification