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

• US 7,487,309 B2
• Filed: 09/18/2006
• Issued: 02/03/2009
• Est. Priority Date: 12/24/1997
• Status: Expired due to Fees

• Current Assignee: Avid Technology Incorporated
• Original Assignee: Avid Technology Incorporated
• Inventors: Peters, Eric C., Fasciano, Peter J., Rabinowitz, Stanley, Jacobs, Herbert R.
• Primary Examiner(s): Bataille; Pierre-Michel
• Application Number:
  US11/522,758
• Publication Number:
  US 20070016727A1
• Time in Patent Office: 869 Days
• Field of Search: 711/112, 711/114, 711/111, 711/162, 711/165, 711/161, 714/6, 714/5, 714/7
• US Class Current: 711/162
• 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/182 Distributed file systems
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 16/70 of video data
• 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/01 Protocols
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer
• 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 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• 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/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. At least one additional copy of each segment also is distributed randomly over the storage units, such that each segment is stored on at least two storage units. This random distribution of multiple copies of segments of data improves both scalability and reliability. When an application requests a selected segment of data, the request is 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. This combination of techniques results in a system which can transfer multiple, independent high-bandwidth streams of data in a scalable manner in both directions between multiple applications and multiple storage units.

Claims

1. In a distributed data storage system comprising a plurality of independent storage units for storing the data and interconnected by a computer network, wherein data is stored on the plurality of storage units in files, wherein each file includes segments of data, wherein each segment has an identifier, and wherein two or more copies of each segment are distributed among the plurality of storage units, such that each segment is stored on at least two of the storage units, and wherein the segments of data are distributed nonsequentially among the plurality of storage units, a method for allowing one or more client systems to access data from the files, comprising:

within each client system;

accessing data that associates, for each segment of a file, the identifier of the segment with an indication of each of the storage units on which a copy of the segment is stored, to select a storage unit for each segment to be read from the file;

for each segment to be read from the file, sending a request for the segment to the selected storage unit, wherein the request includes the identifier of the requested segment of the file;

within each storage unit;

maintaining data defining information that associates, for each segment stored on the storage unit, the identifier of the segment with the location of the segment in the storage;

receiving a request over the computer network from one of the client systems for a segment of a file, wherein the received request includes the identifier of the requested segment of the file;

determining the location of the segment in the storage using the information that associates the identifier of the requested segment with the location of the segment in the storage;

retrieving the requested segment from the storage;

sending the retrieved segment over the computer network to the client system that requested the segment.

2. The method of claim 1, wherein the data for a file is stored in a segment table.

3. The method of claim 2, wherein the segment tables for a plurality of files is stored in a catalog.

4. The method of claim 3, wherein the catalog is stored in a central database accessible by all clients.

5. The method of claim 3, wherein the catalog is stored in each client.

6. The method of claim 3, wherein the catalog is distributed among the clients.

7. The method of claim 3, wherein the catalog is distributed among multiple databases accessible by the clients.

8. The method of claim 3, wherein the catalog is stored as a file on the plurality of storage units.

9. The method of claim 1, wherein the data that associates an identifier of a segment with an indication of each of the storage units on which a copy of the segment is stored is a function.

10. The method of claim 1, wherein the data comprises temporally continuous media data.

11. The method of claim 10, wherein the temporally continuous media data includes video data.

12. The method of claim 10, wherein the temporally continuous media data includes audio data.

13. The method of claim 1, wherein applications may request data from the plurality of storage units independently of each other or any centralized control.

14. The method of claim 1, wherein the storage unit is a server.

15. The method of claim 1, wherein the storage unit is an independently controlled disk storage unit.

16. A distributed data storage system for allowing one or more client systems to access data over a computer network, comprising:

a plurality of independent storage units for storing the data and interconnected by the computer network;

wherein the data is stored on the plurality of storage units in files, wherein each file includes segments of data, wherein each segment has an identifier, and wherein two or more copies of each segment are distributed among the plurality of storage units, such that each segment is stored on at least two of the storage units, and wherein the segments of data are distributed nonsequentially among the plurality of storage units;

computer readable storage including data that associates, for each segment of a file, the identifier of the segment with an indication of each of the storage units on which a copy of the segment is stored;

wherein each client system comprises;

a network interface connected to the computer network for receiving and sending data over the computer network; and

a processor connected to the network interface;

wherein the processor accesses the data that associates, for each segment of a file, the identifier of the segment with an indication of each of the storage units on which a copy of the segment is stored, to select a storage unit for each segment to be read from the file;

wherein the processor instructs the network interface to send a request, for each segment to be read from the file, to the selected storage unit for the segment, wherein the request includes the identifier of the requested segment of the file; and

wherein each storage unit comprises;

storage for storing the data;

a memory containing data defining information that associates, for each segment stored on the storage unit, the identifier of the segment with the location of the segment in the storage;

a network interface connected to the computer network for receiving and sending data over the computer network; and

a processor connected to the network interface, the memory and the storage;

wherein the processor, in response to a request received over the computer network from one of the client systems for a segment of a file, determines the location of the segment in the storage using the information that associates the identifier of the segment with the location of the segment in the storage, and retrieves the requested segment from the storage;

wherein the processor instructs the network interface to send the retrieved segment to the client system.

17. The distributed data storage system of claim 16, wherein the data for a file is stored in a segment table.

18. The distributed data storage system of claim 17, wherein the segment tables for a plurality of files is stored in a catalog.

19. The distributed data storage system of claim 18, wherein the catalog is stored in a central database accessible by all clients.

20. The distributed data storage system of claim 18, wherein the catalog is stored in each client.

21. The distributed data storage system of claim 18, wherein the catalog is distributed among the clients.

22. The distributed data storage system of claim 18, wherein the catalog is distributed among multiple databases accessible by the clients.

23. The distributed data storage system of claim 18, wherein the catalog is stored as a file on the plurality of storage units.

24. The distributed data storage system of claim 16, wherein the data that associates an identifier of a segment with an indication of each of the storage units on which a copy of the segment is stored is a function.

25. The distributed data storage system of claim 16, wherein the data comprises temporally continuous media data.

26. The distributed data storage system of claim 25, wherein the temporally continuous media data includes video data.

27. The distributed data storage system of claim 25, wherein the temporally continuous media data includes audio data.

28. The distributed data storage system of claim 16, wherein applications may request data from the plurality of storage units independently of each other or any centralized control.

29. The distributed data storage system of claim 16, wherein the storage unit is a server.

30. The distributed data storage system of claim 16, wherein the storage unit is an independently controlled disk storage unit.

31. A distributed data storage system for allowing one or more client systems to access data over a computer network, comprising:

a plurality of independent storage units for storing the data and interconnected by the computer network;

wherein the data is stored on the plurality of storage units in files, wherein each file includes segments of data, wherein each segment has an identifier, and wherein each segment and redundancy information for each segment are distributed among the plurality of storage units;

wherein each storage unit comprises;

storage for storing the data;

a memory containing data defining information that associates, for each segment stored on the storage unit, the identifier of the segment with the location of the segment in the storage;

a network interface connected to the computer network for receiving and sending data over the computer network; and

a processor connected to the network interface, the memory and the storage;

wherein the processor, in response to a request received over the computer network from one of the client systems for a segment of a file, determines the location of the segment in the storage using the information that associates the identifier of the segment with the location of the segment in the storage, and retrieves the requested segment from the storage;

wherein the received request includes the identifier of the requested segment of the file; and

wherein the processor instructs the network interface to send the retrieved segment to the client system.

32. The distributed data storage system of claim 31, wherein the redundancy information for a segment is a copy of the segment, and wherein each segment is stored on at least two of the storage units.

33. The distributed data storage system of claim 32, wherein the segments of data are distributed nonsequentially among the plurality of storage units.

34. The distributed data storage system of claim 33, further comprising computer readable storage including data that associates, for each segment of a file, the identifier of the segment with an indication of each of the storage units on which a copy of the segment is stored.

35. The distributed data storage system of claim 32, further comprising computer readable storage including data that associates, for each segment of a file, the identifier of the segment with an indication of each of the storage units on which a copy of the segment is stored.

36. The distributed data storage system of claim 31, wherein the segments of data are distributed nonsequentially among the plurality of storage units.

37. The distributed data storage system of claim 36, further comprising computer readable storage including data that associates, for each segment of a file, the identifier of the segment with an indication of each of the storage units on which a copy of the segment is stored.

38. The distributed data storage system of claim 31, further comprising computer readable storage including data that associates, for each segment of a file, the identifier of the segment with an indication of each of the storage units on which a copy of the segment is stored.

39. In a distributed data storage system comprising a plurality of independent storage units for storing the data and interconnected by a computer network, wherein data is stored on the plurality of storage units in files, wherein each file includes segments of data, wherein each segment has an identifier, and wherein each segment and redundancy information for each segment is distributed among the plurality of storage units, a method for processing requests from one or more client systems to access data from the files, comprising:

within each storage unit;

maintaining data defining information that associates, for each segment stored on the storage unit, the identifier of the segment with the location of the segment in the storage;

receiving a request over the computer network from one of the client systems for a segment of a file, wherein the received request includes the identifier of the requested segment of the file;

determining the location of the segment in the storage using the information that associates the identifier of the requested segment with the location of the segment in the storage;

retrieving the requested segment from the storage;

sending the retrieved segment over the computer network to the client system that requested the segment.