Method for operating a disk storage system which stores video data so as to maintain the continuity of a plurality of video streams

• US 5,732,239 A
• Filed: 05/19/1994
• Issued: 03/24/1998
• Est. Priority Date: 05/19/1994
• Status: Expired due to Fees

• Current Assignee: Starlight Networks, Inc. (Plantronics, Inc.)
• Original Assignee: Starlight Networks, Inc. (Plantronics, Inc.)
• Inventors: Baird, Randall B., Tobagi, Fouad A., Gang, Joseph Mark Jr., Pang, Joseph W. M.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): Ellis, Kevin L.
• Application Number:
  US08/246,220
• Time in Patent Office: 1,405 Days
• Field of Search: 395/441, 395/440, 395/439, 395/826
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 2211/1016 Continuous RAID, i.e. RAID system that allows streaming or continuous media, e.g. VOD
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: H04N 21/23103 using load balancing strategies, e.g. by placing or distributing content on different disks, different memories or different servers storage management G06F3/0604; allocation of resources considering the load in multiprogramming arrangements G06F9/505; techniques for rebalancing the load in a distributed system G06F9/5083; access to distributed or replicated servers, e.g. load balancing, in data networks H04L67/1001
• CPC Class Codes: H04N 21/2312 Data placement on disk arrays data placement in general G06F3/0604
• CPC Class Codes: H04N 21/2315 using interleaving
• CPC Class Codes: H04N 21/2326 Scheduling disk or memory reading operations
• CPC Class Codes: H04N 21/23805 Controlling the feeding rate to the network, e.g. by controlling the video pump
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments

Abstract

A method for increasing the storage capacity of a video server which utilizes an array of disks is disclosed. The server is operated so that the continuity of a plurality of bit streams is maintained. The inventive method has advantageous characteristics with respect to storage capacity, streaming capacity, start-up latency of new streams, amount of required buffer capacity, scalability, reliability and multiple bit rates.

Claims

1. A method for operating an array of N_d storage units which is organized into N_s sub-arrays of N_a storage units,

wherein data from one or more fries is striped across the entire array, with one segment in each stripe being allocated to each storage unit,

said method comprising the steps of defining a sequence of I/O cycles having a duration determined according to the equation N_s N_a S/W_base, where W_base is a bit rate, and scheduling I/O transactions by determining which segments are to be fetched or stored within said I/O cycles to maintain the continuity of a plurality of data streams, the I/O cycles of each sub-array being offset from that of an adjacent sub-array by (1/N_s) of an I/O cycle,

said streams having production or consumption cycles having a duration of N_a S/W_base and produce segments to be written into or consume segments from the N_s sub-arrays in a cyclic pattern,

wherein the consumption of segments fetched from a sub-array in a particular I/O cycle is restricted to begin no earlier than the beginning of the next I/O cycle for the sub-array and the production of segments to be written into a sub-array in a particular I/O cycle is restricted to end no later than the end of the previous I/O cycle for the sub-array.

2. A method for operating an array of N_d storage units

wherein data from each of a plurality of files is stored in the storage units in segments of S bits and striped across N*_d storage units where N*_d ≦

N_d and where N*_d is different for different files,

said method comprising the steps of defining a sequence of I/O cycles having a duration determined according to the equation N_c S/W_base, where N_c is an integer and W_base is a base rate of bits per second, and scheduling I/O transactions by determining which segments are to be stored in or fetched from said storage units in said I/O cycles so as to maintain the continuity of a plurality of streams,

a stream having a bit rate W_base having N_c I/O transactions in said storage units in each cycle, a stream having a bit rate larger than W_base having more than N_c I/O transactions in said storage units in each cycle and a stream having a bit rate smaller than W_base having less than N_c I/O transactions in each cycle.

3. A method for operating an array of N_d storage units

wherein data from a plurality of files is stored in said storage units in segments of S bits,

wherein N*_d consecutive segments from a file are allocated to N*_d of said storage units where N*_d <

N_d,

said method comprising the steps of defining a sequence of I/O cycles having a duration determined by the equation N_d '"'"'S/W_base, N_d '"'"'<

N_d and scheduling I/O transactions by determining which segments are to be fetched or stored within said I/O cycles to maintain the continuity of a plurality of data stream,

a stream with a bit rate W_base having N_d '"'"' I/O transactions in each I/O cycle.

4. The method of claim 3 wherein N*_d is different for different files.

5. A method for operating an array of N_d storage units,

wherein data from a plurality of files are stored in said storage units in segments of S bits,

wherein N_d consecutive segments from a file are allocated so that there is one segment on each of the N_d storage units,

said method comprising the steps of defining a sequence of I/O cycles having a duration determined according to the equation N_d '"'"'S/W_base, N_d '"'"'<

N_d, wherein W_base is a base rate of bits per second and scheduling I/O transactions by determining which segments are to be fetched or stored within said I/O cycles to maintain the continuity of a plurality of data streams,

during one I/O transaction, a stream with a bit rate of W_base fetching from or storing to each of N_d '"'"' storage units one segment in each I/O cycle, and

during one I/O transaction, a stream with a bit rate other than W_base fetching or storing fewer or greater than N_d '"'"' segments in each I/O cycle.

6. The method of claim 5 wherein for each I/O cycle, all of the I/O transactions scheduled within each such cycle from said plurality of streams are sorted separately according to locations of the segments on each storage unit.

7. The method of claim 5 wherein each of said storage units is a disk.

8. The method of claim 5 wherein said cycles are grouped into super-cycles comprised of N_super cycles, and in cycle i of a super-cycle, stream j has L_i,j I/O transactions where L_i,j is an integer.

9. The method of claim 5 wherein the number N_d '"'"' is different for different streams.

10. The method of claim 5 wherein each of said storage units is an array of disks.

11. The method of claim 10 wherein a server is associated with each array of disks.

12. The method of claim 5 wherein said segments from said files are allocated to said storage units in a regular cyclic pattern.

13. The method of claim 6 wherein N_d consecutive segments from a file have the same physical address in said N_d storage units.

14. The method of claim 5 wherein each of said cycles is divided in G subcycles.

15. The method of claim 14 wherein said plurality of streams is divided into G groups and in each subcycle N_d '"'"' I/O transactions are scheduled for the streams in one group.

16. The method of claim 14 wherein said plurality of streams is divided into groups and in each subcycle one I/O transaction is performed for each stream in each of each of N_d '"'"' groups.

17. A method for operating an array of N_d storage units,

wherein said storage traits are organized into N_s s sub-arrays of N_a storage units each,

wherein data from one or more files are organized into substripes comprised of N_a consecutive segments of S bits,

wherein said substripes are allocated to said sub-arrays so that each substripe is allocated to one sub-array,

said method comprising the steps of:

defining a sequence of I/O cycles having a duration determined according to the equation N_a S/W_base, wherein W_base is a base rate of bits per second and scheduling I/O transactions by determining which segments are to be fetched or stored within said I/O cycles to maintain the continuity of a plurality of data streams,

a stream with a bit rate of W_base having N_a I/O transactions in each I/O cycle such that one substripe of N_a segments is fetched from or written into one sub-array.

18. The method of claim 17 wherein for each I/O cycle, the I/O transactions scheduled within each such cycle from said plurality of streams are sorted separately according to locations of said segments on each sub-array.

19. The method of claim 17 wherein each of said storage units comprises a disk.

20. The method of claim 17 wherein all of the substripes from at least one file are allocated to one sub-array.

21. The method of claim 17 wherein substripes from one or more files are randomly assigned to said sub-arrays.

22. The method of claim 17 wherein substripes from one or more of said files are cyclically allocated to said sub-arrays in a regular pattern.

23. The method of claim 17 wherein said I/O cycles are organized into super-cycles of N_super cycles and in the i^th cycle of a super-cycle a stream j has L_i,j substripes written into or fetched from said sub-arrays, where L_i,j is an integer.

24. The method of claim 17 wherein said streams are organized into groups which are desynchronized from one another.

25. The method of claim 17 wherein the number of sub-arrays and the number of storage units in a sub-array is different for different files.

26. The method of claim 17 wherein the division of said arrays into sub-arrays is different for different files.

27. The method of claim 17 wherein each of said storage units comprises an array of disks.

28. The method of claim 27 wherein a server is associated with each array of disks.

29. The method of claim 17 wherein said cycles are divided into G subcycles.

30. The method of claim 29 wherein in each sub-cycle, one substripe is fetched or written into a sub-array for each stream in one of G groups.

31. The method of claim 29 wherein in each sub-cycle, one substripe is fetched from or written into a sub-array for each stream in N_a groups.