Computer system and process for transferring streams of data between multiple storage units and multiple applications in a scalable and reliable manner

• US 6,785,768 B2
• Filed: 05/14/2002
• Issued: 08/31/2004
• Est. Priority Date: 12/24/1997
• Status: Expired due to Term

• Current Assignee: Avid Technology Incorporated
• Original Assignee: Avid Technology Incorporated
• Inventors: Peters, Eric C., Rabinowitz, Stanley, Jacobs, Herbert R.
• Primary Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US10/145,495
• Publication Number:
  US 20020162047A1
• Time in Patent Office: 840 Days
• Field of Search: 711/170, 711/112, 711/100, 711/114, 711/4, 725/92, 725/93, 725/97, 725/96, 709/104, 709/106, 709/105, 709/225, 709/226, 709/230, 709/231, 709/233, 707/205
• US Class Current: 711/112
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• 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 16/184 implemented as replicated file system
• CPC Class Codes: G06F 16/70 of video data
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06
• CPC Class Codes: H04N 21/2182 involving memory arrays, e.g. RAID disk arrays RAID arrays per se G06F3/0689; use of parity to protect data in RAID systems G06F11/1008
• 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/23116 involving data replication, e.g. over plural servers synchronization of replicated data G06F11/1658; error detection or correction by means of data replication G06F11/2053; replication in distributed file systems G06F16/10; replication in distributed file systems G06F16/27; replication or mirroring of data in data networks H04L67/1095
• 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/232 Content retrieval operation locally within server, e.g. reading video streams from disk arrays storage management G06F3/0604; details of querying and searching of video data from a database G06F16/739
• CPC Class Codes: H04N 21/2393 involving handling client requests scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04N 21/2396 characterized by admission policies admission control, resource allocation in open networks H04L12/5692; arrangements for network security using user profiles for access control H04L63/102; access security in wireless networks H04W12/08
• CPC Class Codes: H04N 21/2405 : Monitoring of the internal components or processes of the server, e.g. server load allocation of resources in multiprogramming arrangements G06F9/50; performance measurement of computer activity G06F11/34
• CPC Class Codes: H04N 21/241 : Operating system [OS] processes, e.g. server setup
• CPC Class Codes: H04N 21/262 : Content or additional data distribution scheduling, e.g. sending additional data at off-peak times, updating software modules, calculating the carousel transmission frequency, delaying a video stream transmission, generating play-lists scheduling strategies for dispatcher in multiprogramming arrangements G06F9/4881; arrangements for scheduling broadcast services or broadcast-related services H04H60/06; flow control in packet networks H04L47/10; establishing a time schedule or organising the servicing of application requests H04L67/62
• CPC Class Codes: H04N 21/44004 : involving video buffer management, e.g. video decoder buffer or video display buffer
• CPC Class Codes: H04N 21/442 : Monitoring of processes or resources, e.g. detecting the failure of a recording device, monitoring the downstream bandwidth, the number of times a movie has been viewed, the storage space available from the internal hard disk arrangements for monitoring broadcast services or broadcast-related services H04H60/29; arrangements for identifying or recognising characteristics with a direct linkage to broadcast information H04H60/35; monitoring of user activities for profile generation for accessing a video database G06F16/739; monitoring in wireless networks H04W24/00
• CPC Class Codes: H04N 21/47202 : for requesting content on demand, e.g. video on demand
• CPC Class Codes: H04N 21/6581 : Reference data, e.g. a movie identifier for ordering a movie or a product identifier in a home shopping application
• CPC Class Codes: H04N 21/8456 : by decomposing the content in the time domain, e.g. in time segments
• CPC Class Codes: H04N 7/17336 : Handling of requests in head-ends
• CPC Class Codes: Y10S 707/99953 : Recoverability
• CPC Class Codes: Y10S 707/99956 : File allocation

Abstract

Multiple applications request data from multiple storage units over a computer network. The data is divided into segments and each segment is distributed randomly on one of several storage units, independent of the storage units on which other segments of the media data are stored. Redundancy information corresponding to each segment also is distributed randomly over the storage units. The redundancy information for a segment may be a copy of the segment, such that each segment is stored on at least two storage units. The redundancy information also may be based on two or more segments. This random distribution of segments of data and corresponding redundancy information improves both scalability and reliability. When a storage unit fails, its load is distributed evenly over to remaining storage units and its lost data may be recovered because of the redundancy information. When an application requests a selected segment of data, the request may be processed by the storage unit with the shortest queue of requests. Random fluctuations in the load applied by multiple applications on multiple storage units are balanced nearly equally over all of the storage units. Small data files also may be stored on storage units that combine small files into larger segments of data using a log structured file system. This combination of techniques results in a system which can transfer both multiple, independent high-bandwidth streams of data and small data files in a scalable manner in both directions between multiple applications and multiple storage units.

Claims

1. A process for transferring temporal media data over a network from a plurality of storage units for playback on a client,

wherein the temporal media data is divided into segments distributed over the plurality of storage units, wherein each storage unit has persistent storage and one or more buffers for storing data read from persistent storage for transmission over the network;

wherein the client has a sequence of playback buffers, wherein each playback buffer temporarily stores a segment of the temporal media data before playback, and wherein data in the sequence of playback buffers is played back according to the sequence of the playback buffers, such that each playback buffer has a playback time,

the process comprising;

issuing requests to the storage units to read segments of the temporal media data from the persistent storage into the one or more buffers on the storage units;

ordering empty playback buffers in the sequence of playback buffers by playback time and whether data for placement in each playback buffer is expected to be available in the one or more buffers in the storage units;

selecting the playback buffer with the earliest playback time and for which the data for placement in the playback buffer is expected to be available in the one or more buffers in the storage units; and

accessing the storage units for the data for placement in the selected playback buffer;

repeating the steps of issuing, ordering, selecting and accessing during playback.

2. The process of claim 1, wherein the segments of the temporal media data are stored nonsequentially on the storage units.

3. The process of claim 2, wherein each segment of the temporal media data is stored on one of the storage units and a copy of the segment is stored on another of the storage units, the process further comprising, for each segment, selecting one of the storage units.

4. The process of claim 3, wherein each storage unit includes a queue of requests and the selected storage unit is the storage unit with approximately the shortest queue of requests.

5. The process of claim 4, in a system in which multiple clients access the storage units, further comprising ensuring that each storage unit sends data to only one client at a time and each client requests data from only one storage unit at a time.

6. The process of claim 1, wherein each segment of the temporal media data is stored on one of the storage units and a copy of the segment is stored on another of the storage units, the process further comprising, for each segment, selecting one of the storage units.

7. The process of claim 6, wherein each storage unit includes a queue of requests and the selected storage unit is the storage unit with approximately the shortest queue of requests.

8. The process of claim 7, a system in which multiple clients access the storage units, further comprising ensuring that each storage unit sends data to only one client at a time and each client requests data from only one storage unit at a time.

9. The process of claim 2, in a system in which multiple clients access the storage units, further comprising ensuring that each storage unit sends data to only one client at a time and each client requests data from only one storage unit at a time.

10. The process of claim 1, in a system in which multiple clients access the storage units, further comprising ensuring that each storage unit sends data to only one client at a time and each client requests data from only one storage unit at a time.

11. A client system for transferring temporal media data over a network from a plurality of storage units for playback on the client system, wherein the temporal media data is divided into segments distributed over the plurality of storage units, wherein each storage unit has persistent storage and one or more buffers for storing data read from persistent storage for transmission over the network, wherein the client system comprises:

a sequence of playback buffers, wherein each playback buffer temporarily stores a segment of the temporal media data before playback, and wherein data in the sequence of playback buffers is played back according to the sequence of the playback buffers, such that each playback buffer has a playback time,

means for issuing requests to the storage units to read segments of the temporal media data from the persistent storage into the one or more buffers on the storage units;

means for ordering empty playback buffers in the sequence of playback buffers by playback time and whether data for placement in each playback buffer is expected to be available in the one or more buffers in the storage units;

means for selecting the playback buffer with the earliest playback time and for which the data for placement in the playback buffer is expected to be available in the one or more buffers in the storage units;

means for accessing the storage units for the data for placement in the selected playback buffer; and

means for controlling the means for issuing, ordering, selecting and accessing during playback.

12. The client system of claim 11, wherein the segments of the temporal media data are stored nonsequentially on the storage units.

13. The client system of claim 12, wherein each segment of the temporal media data is stored on one of the storage units and a copy of the segment is stored on another of the storage units, the client system further comprising, for each segment, means for selecting one of the storage units.

14. The client system of claim 13, wherein each storage unit includes a queue of requests and the selected storage unit is the storage unit with approximately the shortest queue of requests.

15. The client system of claim 14, in a system in which multiple clients access the storage units, further comprising means for ensuring that each storage unit sends data to only one client at a time and each client requests data from only one storage unit at a time.

16. The client system of claim 11, wherein each segment of the temporal media data is stored on one of the storage units and a copy of the segment is stored on another of the storage units, the client system further comprising, for each segment, means for selecting one of the storage units.

17. The client system of claim 16, wherein each storage unit includes a queue of requests and the selected storage unit is the storage unit with approximately the shortest queue of requests.

18. The client system of claim 17, in a system in which multiple clients access the storage units, further comprising means for ensuring that each storage unit sends data to only one client at a time and each client requests data from only one storage unit at a time.

19. The client system of claim 12, in a system in which multiple clients access the storage units, further comprising means for ensuring that each storage unit sends data to only one client at a time and each client requests data from only one storage unit at a time.

20. The client system of claim 11, in a system in which multiple clients access the storage units, further comprising means for ensuring that each storage unit sends data to only one client at a time and each client requests data from only one storage unit at a time.