Prefetching to service multiple video streams from an integrated cached disk array

Claim 3

The method as claimed in claim 1, wherein the amount of advance of the prefetch commands before the fetch commands is increased to reduce loading of disk storage, and decreased to reduce allocation of cache memory.

Claim 4

The method as claimed in claim 1, wherein said cached disk storage subsystem responds to a prefetch command for a data segment on a priority basis by checking a directory to determine whether the data segment is in the cache, and when the data segment is not in the cache, staging the data segment from disk storage into the cache.

Claim 5

The method as claimed in claim 3, wherein said cached disk storage subsystem maintains, in cache, data specified by a prefetch command from a process at least until the process fetches the specified data from cache.

Claim 6

The method as claimed in claim 4, wherein said cached disk storage subsystem maintains, for a data segment in the cache, a wait list of processes having prefetched but not yet having fetched the data segment in the cache, and when said wait list becomes empty, said cached disk storage subsystem deallocates cache memory having been allocated to store the data segment.

Claim 9

The method as claimed in claim 6, which includes allocating the allocated portion of the cache memory by removing a cache slot from a head of a replacement queue, and which includes freeing the allocated portion of the cache memory by returning the cache slot to the head of the replacement queue.

Claim 10

The method as claimed in claim 5, which includes: in response to each prefetch command, placing each process issuing each prefetch command on a wait list associated with each allocated portion of the cache memory storing data specified by said each process issuing each prefetch command; removing said each process issuing each prefetch command from the wait list associated with said each allocated portion of the cache memory when the data specified by said each process issuing each prefetch command are fetched from the cached disk storage subsystem in response to the fetch command issued by said each process issuing each prefetch command; and freeing said each allocated portion of cache memory when the wait list associated with said each allocated portion of cache memory becomes empty.

Claim 11

The method as claimed in claim 6, wherein issuance of said each fetch command and said each prefetch command are scheduled by a scheduler in the video file server in response to a client request for a video data stream from a specified data set, and said scheduler schedules the issuance of said each prefetch command for said each process a certain time in advance of said each fetch command for said each process.

Claim 12

The method as claimed in claim 9, wherein the scheduler checks whether the video file server is already supplying a video data stream from the data set, and when the video file server is already supplying a video data stream from the data set, the scheduler decides either to schedule said each prefetch command for said each process a minimum time in advance of said each fetch command for said each process in order to conserve cache resources, or to schedule said each prefetch command for said each process some greater time in advance of said each fetch command for said each process in order to conserve disk resources.

Claim 15

The method as claimed in claim 11, including the step of buffering the fetched segments of video data in a stream server computer for delivery of said video stream from said stream server computer at said substantially constant data rate.

Claim 16

The method as claimed in claim 11, wherein said cached disk storage subsystem responds to a prefetch command for a data segment on a priority basis by checking a directory to determine whether the data segment is in the cache memory, and when the data segment is not in the cache memory, staging the data segment from the disk storage into the cache memory.

Claim 17

The method as claimed in claim 11, wherein said cached disk storage subsystem maintains, for each data segment in the cache memory, a wait list of processes having prefetched but not yet having fetched said each data segment in the cache memory, and when said wait list becomes empty, said cached disk storage subsystem frees a portion of the cache memory having been allocated to store said each data segment.

Claim 20

The method as claimed in claim 15, wherein the amount of advance of the prefetch commands before the fetch commands is determined from a difference in time between when said client of said data network will be fetching a data segment for said video data stream and when one of said other clients of said data network will be fetching the same data segment from said video data stream.

Claim 21

The method as claimed in claim 15, wherein said cached disk storage subsystem responds to a prefetch command for a data segment on a priority basis by checking a directory to determine whether the data segment is in the cache, and when the data segment is not in the cache, staging the data segment from disk storage into the cache.

Claim 22

The method as claimed in claim 15, wherein said cached disk storage subsystem maintains, for a data segment in the cache, a wait list of processes having prefetched but not yet having fetched the data segment in the cache, and when said wait list becomes empty, said cached disk storage subsystem frees the cache memory having been allocated to store said data segment.

Claim 23

A cached disk storage subsystem responsive to a respective sequence of a prefetch command and a fetch command issued by each of a plurality of processes, said cached disk storage subsystem comprising: disk storage; a random access cache memory linked to the disk storage for staging data from the disk storage to an allocated portion of the cache memory in response to each prefetch command from each process when data specified by said each prefetch command from said each process are absent from the cache memory, the plurality of the processes having shared access to the data in the allocated portion of the cache memory, and a cache controller responsive to each fetch command from said each process for fetching the specified data from the cache memory, and responsive to said each prefetch command from said each process for (a) receiving information with said each prefetch command from said each process for preventing deallocation of the allocated portion of the cache memory whenever a process has prefetched but not yet fetched data stored in the allocated portion of the cache memory; (b) retaining the specified data in the allocated portion of the cache memory from the time that the cached disk storage subsystem responds to said each prefetch command from said each process to the time that the cached disk storage subsystem responds to said each fetch command from said each process; and (b) after responding to said each fetch command from said each process, when no information received with the prefetch commands indicates that another process has issued a prefetch command for the specified data and has not yet fetched the specified data, freeing the allocated portion of cache memory holding the specified data so that the allocated portion of cache memory becomes free to be allocated to receive different data.

Claim 24

A cached disk storage subsystem responsive to a respective sequence of a prefetch command and a fetch command issued by each of a plurality of processes, said cached disk storage subsystem comprising: disk storage; a random access cache memory linked to the disk storage for staging data from the disk storage to an allocated portion of the cache memory in response to each prefetch command from each process when data specified by said each prefetch command from said each process are absent from the cache memory, the plurality of the processes having shared access to the data in the allocated portion of the cache memory, and a cache controller responsive to each fetch command from said each process for fetching the specified data from the cache memory, and responsive to said each prefetch command from said each process for (a) receiving information with said each prefetch command from said each process for preventing deallocation of the allocated portion of the cache memory whenever a process has prefetched but not yet fetched data stored in the allocated portion of the cache memory; (b) retaining the specified data in the allocated portion of the cache memory from the time that the cached disk storage subsystem responds to said each prefetch command from said each process to the time that the cached disk storage subsystem responds to said each fetch command from said each process; and (b) after responding to said each fetch command from said each process, when no information received with the prefetch commands indicates that another process has issued a prefetch command for the specified data and has not yet fetched the specified data, freeing the allocated portion of cache memory holding the specified data so that the allocated portion of cache memory becomes free to be allocated to receive different data.

Claim 25

The cached disk storage subsystem as claimed in claim 19, wherein the cache controller is programmed for allocating the allocated portion of cache memory by removing a cache slot from a head of a replacement queue, and for freeing the allocated portion of cache memory by returning the cache slot to the head of the replacement queue.

Claim 26

The cached disk storage subsystem as claimed in claim 19, wherein the cache controller is programmed for: responding to each prefetch command by placing each process issuing said each prefetch command on a wait list associated with each allocated portion of cache memory storing data specified by said each process; removing each process from the wait list associated with said each allocated portion of cache memory when the data specified by said each process are fetched from the cached disk storage subsystem in response to the fetch command issued by said each process; and freeing said each allocated portion of cache memory when the wait list associated with said each allocated portion of cache memory becomes empty.

Claim 27

A video file server comprising, in combination: a controller server responsive to requests from network clients for video data sets for initiating execution of a process for satisfying each request by issuing a sequence of prefetch and fetch commands for prefetching and fetching specified data segments of each video data set; and a cached disk storage subsystem coupled to the controller server for responding to the prefetch and fetch commands issued by each process, said cached disk storage subsystem including: disk storage; a random access cache memory linked to the disk storage for staging each specified data segment from the disk storage to an allocated portion of the cache memory in response to each prefetch command when said each specified data segment is absent from the cache memory, and a cache controller responsive to each fetch command for fetching said each specified data segment from the cache memory, and for (a) receiving prefetch commands from a plurality of processes to prefetch data stored in a shared allocated portion of the cache memory, (b) receiving information with each prefetch command from each process for preventing deallocation of the shared allocated portion of the cache memory whenever a process has prefetched but not yet fetched data stored in the shared allocated portion of the cache memory, (c) retaining the data segment in the shared allocated portion of the cache memory until none of the plurality of processes have prefetched but not yet fetched data stored in the shared allocated portion of the cache memory, and (d) freeing the shared allocated portion of the cache memory when none of the plurality of processes have prefetched but not yet fetched data from the shared allocated portion of the cache memory.

Claim 28

A video file server comprising, in combination: a controller server responsive to requests from network clients for video data sets for initiating execution of a process for satisfying each request by issuing a sequence of prefetch and fetch commands for prefetching and fetching specified data segments of each video data set; and a cached disk storage subsystem coupled to the controller server for responding to the prefetch and fetch commands issued by each process, said cached disk storage subsystem including: disk storage; a random access cache memory linked to the disk storage for staging each specified data segment from the disk storage to an allocated portion of the cache memory in response to each prefetch command when said each specified data segment is absent from the cache memory, and a cache controller responsive to each fetch command for fetching said each specified data segment from the cache memory, and for (a) receiving prefetch commands from a plurality of processes to prefetch data stored in a shared allocated portion of the cache memory, (b) receiving information with each prefetch command from each process for preventing deallocation of the shared allocated portion of the cache memory whenever a process has prefetched but not yet fetched data stored in the shared allocated portion of the cache memory, (c) retaining the data segment in the shared allocated portion of the cache memory until none of the plurality of processes have prefetched but not yet fetched data stored in the shared allocated portion of the cache memory, and (d) freeing the shared allocated portion of the cache memory when none of the plurality of processes have prefetched but not yet fetched data from the shared allocated portion of the cache memory.

Claim 29

The video file server as claimed in claim 22, further includes a scheduler for scheduling the prefetch commands and the fetch commands issued by each process, and wherein the scheduler responds to a request for a specified video data set by checking whether data segments are already being fetched from the specified video data set, and when data segments are already being fetched from the specified video data set, deciding either to schedule the prefetch command for each data segment in the specified video data set a minimum time in advance of the fetch command for each data segment in the specified video data set in order to conserve cache resources, or to schedule the prefetch command some greater time in advance of the fetch command in order to conserve disk resources.

Claim 30

A video file server comprising, in combination: a controller server responsive to requests from network clients for video data sets and initiating execution of a process for satisfying each request, each process issuing a sequence of prefetch and fetch commands for prefetching and fetching specified data segments of each video data set; and a cached disk storage subsystem coupled to the stream server for responding to the prefetch and fetch commands issued by each process; wherein said video file server includes a scheduler for scheduling the prefetch commands and the fetch commands issued by each process so that said segments of said each video data set are fetched from said cached disk storage subsystem in time for delivery to each network client at a substantially constant data rate so long as said segments of said each video data set are in cache of said cached disk storage subsystem when said each process issues said periodic fetch commands to said cached disk storage subsystem, and so that said segments of said each video data set are prefetched for said each process sufficiently in advance of said periodic fetch commands for said each process to insure that said segments of said each video data set are in said cache of said cached disk storage subsystem when said periodic fetch commands are issued by said each process to said cached disk storage subsystem; and wherein the cached disk storage subsystem includes a cache controller for receiving prefetch commands from a plurality of processes to prefetch data stored in a shared allocated portion of the cache memory, for receiving information with each prefetch command from each process for preventing deallocation of the shared allocated portion of the cache memory whenever a process has prefetched but not yet fetched data stored in the shared allocated portion of the cache memory, for retaining data in the shared allocated portion of the cache memory until none of the plurality of processes have prefetched but not yet fetched data stored in the shared allocated portion of the cache memory, and for freeing the shared allocated portion of the cache memory when none of the plurality of processes have prefetched but not yet fetched data from the shared allocated portion of the cache memory.

Claim 31

A video file server comprising, in combination: a controller server responsive to requests from network clients for video data sets and initiating execution of a process for satisfying each request, each process issuing a sequence of prefetch and fetch commands for prefetching and fetching specified data segments of each video data set; and a cached disk storage subsystem coupled to the stream server for responding to the prefetch and fetch commands issued by each process; wherein said video file server includes a scheduler for scheduling the prefetch commands and the fetch commands issued by each process so that said segments of said each video data set are fetched from said cached disk storage subsystem in time for delivery to each network client at a substantially constant data rate so long as said segments of said each video data set are in cache of said cached disk storage subsystem when said each process issues said periodic fetch commands to said cached disk storage subsystem, and so that said segments of said each video data set are prefetched for said each process sufficiently in advance of said periodic fetch commands for said each process to insure that said segments of said each video data set are in said cache of said cached disk storage subsystem when said periodic fetch commands are issued by said each process to said cached disk storage subsystem; and wherein the cached disk storage subsystem includes a cache controller for receiving prefetch commands from a plurality of processes to prefetch data stored in a shared allocated portion of the cache memory, for receiving information with each prefetch command from each process for preventing deallocation of the shared allocated portion of the cache memory whenever a process has prefetched but not yet fetched data stored in the shared allocated portion of the cache memory, for retaining data in the shared allocated portion of the cache memory until none of the plurality of processes have prefetched but not yet fetched data stored in the shared allocated portion of the cache memory, and for freeing the shared allocated portion of the cache memory when none of the plurality of processes have prefetched but not yet fetched data from the shared allocated portion of the cache memory.

Claim 32

The video file server as claimed in claim 24, further including stream server computers linked to the cached disk storage subsystem and the controller server for buffering the fetched segments of video data for delivery of said video data segments from said stream server computer at said substantially constant data rate to said network clients.

Claim 33

The video file server as claimed in claim 24, wherein the cache controller is programmed for responding to a prefetch command for a data segment on a priority basis by checking a directory to determine whether the data segment is in the cache, and when the data segment is not in the cache, staging the data segment from disk storage into the cache.

Claim 34

The video file server as claimed in claim 26, wherein the cache controller is programmed for maintaining, for each data segment in the cache, a wait list of processes having prefetched but not yet having fetched the data segment in the cache, and when said wait list becomes empty, for freeing the cache memory having been allocated to store said each data segment.

Claim 35

The video file server as claimed in claim 24, wherein the scheduler selects an amount of advance of the prefetch commands issued by said each process before the respective fetch commands issued by said each process in order to increase the amount of advance when other clients of said data network will be requesting video data segments included in the video data set being fetched by said each process.

Claim 36

The video file server as claimed in claim 24, wherein the scheduler selects an amount of advance of the prefetch commands issued by said each process before the respective fetch commands issued by said each process, wherein the amount of advance of the prefetch commands before the fetch commands is determined from a difference in time between when a data segment for a data set will be fetched by said each process and when another process will be fetching the same data segment from said data set.

Claim 37

The video file server as claimed in claim 24, wherein the scheduler selects an amount of advance of the prefetch commands issued by said each process before the respective fetch commands issued by said each process, wherein the amount of advance of the prefetch commands before the fetch commands is selected in dependence upon the availability of resources in the cached disk storage subsystem in order to conserve the resources in the cached disk storage subsystem.

Claim 38

The video file server as claimed in claim 30, wherein the scheduler increases the amount of advance of the prefetch commands before the fetch commands in order to reduce loading of disk storage, and decreases the amount of advance of the prefetch commands before the fetch commands in order to reduce allocation of cache memory.

Claim 41

The method as claimed in claim 32, which includes allocating a portion of the cache memory by removing a cache slot from a replacement queue, and which includes freeing an allocated portion of the cache memory by returning a cache slot to the replacement queue.

Claim 42

A cached disk storage subsystem, said cached disk storage subsystem comprising, in combination: disk storage; random access cache memory; a cache controller for responding to prefetch commands for staging data specified by respective processes from the disk storage to respective allocated portions of the cache memory when the specified data are absent from the cache memory, said cached disk storage subsystem responding to fetch commands from the respective processes for fetching the specified data from the cache memory, wherein a plurality of the processes share access to data in at least one of the allocated portions of the cache memory, said cache controller being programmed for: (a) responding to each prefetch command for staging data specified by each process by placing said each process on a wait list for the allocated portion of the cache memory storing the data specified by said each process; and (b) responding to each fetch command from said each process for said data specified by said each process by removing said each process from said wait list for said allocated portion of the cache memory storing said data specified by said each process, and when the wait list becomes empty, freeing said allocated portion of the cache memory storing said data specified by said each process so that said allocated portion of the cache memory storing said data specified by said each process becomes free to be allocated to receive different data.

Claim 43

A cached disk storage subsystem, said cached disk storage subsystem comprising, in combination: disk storage; random access cache memory; a cache controller for responding to prefetch commands for staging data specified by respective processes from the disk storage to respective allocated portions of the cache memory when the specified data are absent from the cache memory, said cached disk storage subsystem responding to fetch commands from the respective processes for fetching the specified data from the cache memory, wherein a plurality of the processes share access to data in at least one of the allocated portions of the cache memory, said cache controller being programmed for: (a) responding to each prefetch command for staging data specified by each process by placing said each process on a wait list for the allocated portion of the cache memory storing the data specified by said each process; and (b) responding to each fetch command from said each process for said data specified by said each process by removing said each process from said wait list for said allocated portion of the cache memory storing said data specified by said each process, and when the wait list becomes empty, freeing said allocated portion of the cache memory storing said data specified by said each process so that said allocated portion of the cache memory storing said data specified by said each process becomes free to be allocated to receive different data.

Claim 44

The cached disk storage subsystem as claimed in claim 34, wherein the cache controller is programmed for allocating a portion of the cache memory by removing a cache slot from a replacement queue, and for freeing an allocated portion of the cache memory by returning a cache slot to the replacement queue.