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

Detailed description of the invention

(Field of invention) The present invention relates to computer systems for capturing, authoring and playing multimedia programs, as well as distributed computer systems.

(background) There are several computer system architectures that support the distributed use of data through computer networks. These computer architectures are used in applications such as corporate intranets, distributed database applications, and video-on-demand services.

For example, a video-on-demand service is typically designed under the assumption that the user requests the entire movie and the selected movie has a considerable length. Therefore, video-on-demand servers are designed to support read-only access to the same movie by several subscribers, perhaps at different times. Such a server typically divides the data into several segments and sequentially distributes these segments to several computers or computer disks. This technique is commonly referred to as striping and is described, for example, in US Pat. Nos. 5,473,362, 5,583,868, and 5,610,841. One problem with striping movie data across several discs is that the entire movie can be lost due to a single disc or server failure. This is because every movie has at least one segment written on each disc.

A common technique for increasing reliability in data storage is called mirroring. A hybrid system using mirroring and sequential striping is shown in US Pat. No. 5,559,764 (Chen et al.). Mirroring must maintain two copies of each storage device, i.e. have primary storage and secondary backup storage for all data. Both copies can be used for load distribution. However, using this technique, if the primary storage fails, the entire load will be placed on the secondary backup storage.

Another problem with sequentially striping data across several discs is the increased accuracy of what is called the "convoy effect". The convoy effect occurs because requests for data segments from a file tend to be concentrated on one disk and then circulated from disk to disk ("convoy"). As a result, one disk is specifically burdened with requests at one time, while the other disks are lighter. Also, each new request to the disk must wait for the convoy to be processed, resulting in increased latency for the new request. To overcome the convoy effect, the data should be randomly striped. That is, the segments of the data file are stored in random order between disks rather than sequentially. Such a system is described in Proceedings of Multimedia '96, pp144-150, "Design and Performance Tradeoffs in" by R. Tewari et al. (R. Tewari et al.). Described in "Clustered Video Servers" (a design and performance trade-off for clustered video servers). Such systems still result in random overloads on a single disk, which is common. This is due to the randomness of data access.

These systems include a large number of independent high-bandwidth data streams that are scalable and reliable across a large number of storage devices and applications, especially isochronous media such as video and associated audio data. No data can be transferred individually. The need for such data transfer is particularly difficult in systems that support the capture, authoring, and playback of multimedia data. In particular, in authoring systems, access to data is typically done in small pieces, called clips, of larger data files. As for how to store data, these clips are often accessed arbitrarily, that is, in a random order, and it is difficult to perform efficient data transfer. (Overview) A computer network is used to randomly distribute data over a large number of storage devices connected to a large number of applications. Divide the data into segments. Store each segment in one of the storage devices. Redundant information based on one or more segments is also stored in a storage device different from the basic segment. The redundant information may be a copy of each segment, or may be calculated by an exclusive OR operation performed on two or more segments. The choice of each storage device that stores the segment or redundant information is random or pseudo-random and can be independent of the storage device that stores the other data segments. If the redundancy information is based on more than one segment, each of the segments is stored on a different storage device.

This random distribution of data segments improves both scalability and reliability. For example, because data is processed by accessing the segment, data fragments or clips are processed as efficiently as all of the data. The application can request data transfer from the storage device only if the data transfer is efficient, and can also request the storage device to preprocess the read request. Bandwidth utilization on a computer network can be optimized by scheduling data transfers between clients and storage devices. If one of the storage devices fails, its load is also randomly and nearly evenly distributed across the rest of the storage devices. A procedure for recovering from a storage device failure can also be provided.

Storage devices and applications can also operate independently without the use of a central control unit. For example, each client can schedule communication with the storage device using only local information. Therefore, storage devices and applications can be added and removed from the system. As a result, the system is extensible while in operation.

If the redundant information is a one-segment copy, system performance can be improved, but at the expense of increased memory. For example, if an application requests a selected data segment, the request can be processed by the storage device with the shortest queue of requests, so random variation in load applied by many applications on many storage devices. Is statistically and more equally balanced across all storage devices.

This combination of techniques provides a system capable of transferring a large number of independent high-bandwidth data streams in a scalable and reliable manner between a large number of storage devices and a large number of applications.

Therefore, in one aspect, the distributed data storage system includes a plurality of storage devices for storing data, and the segments of the data stored on the storage devices are distributed among the plurality of storage devices. Redundant information corresponding to each segment is also randomly distributed among the storage devices.

If the redundant data is a copy of one segment, each copy of each segment can be stored in a different storage device. Each copy of each segment is relative to the storage device<u style="single">specification</u>(relative<u style="single"></u>It can be assigned to one of multiple storage devices according to the probability distribution defined as a function of specification). The distributed data storage system can include computer readable media. Computer-readable logic is stored on this medium, a segment table accessible by the computer is defined using the instructions of the data segment, and from multiple storage devices that store a copy of the segment. Search for storage instructions. The plurality of storage devices may include first, second and third storage devices connected to a computer network.

In another aspect, a computer file system accesses an independent remote storage device through a computer network in response to a request from an application running on the computer and retrieves the data stored on the storage device. It is possible to read. The data segment and the corresponding redundant information are randomly distributed among the plurality of storage devices. If the redundancy information is a copy of a segment, the file system reads the data in response to the request and, for each segment of the selected data, selects one of the storage devices to store the segment. The file system can reconstruct the lost segment from other segments and redundant information. Each segment of request data is read from the storage device selected for that segment. When it receives data from the selected storage device, it feeds the data to the application. In this file system, storage devices can be selected so that the load of demand on multiple storage devices is substantially balanced. The storage device for the segment can be selected according to the estimated value of the storage device for the segment, which has the shortest estimated time to respond to the request.

More specifically, the file system can request data from one of the storage devices and indicate the estimated time. If the first storage device rejects the request, the file system can request the data from another storage device and can indicate a different estimated time. If the second storage device rejects the request, the file system requests the data from the first storage device. Each storage device rejects a data request if the storage device fails to meet the request within an estimated time. The storage device accepts the request when the storage device is met within the estimated time.

The file system can schedule data transfers from selected storage devices and read each segment so that the storage devices transfer data efficiently. More specifically, the file system can request data transfer from selected storage devices and indicate latency. If the selected storage device rejects the request to transfer the data, the data can be requested from another storage device, or the file system can request the data from the same storage device at a later time. .. Each storage device rejects the data transfer request if it is unable to transfer data from the storage device within the indicated latency. The storage device transfers the data if the selected storage device can transfer the data within the indicated latency.

In another aspect, a computer file system can access an independent remote storage device through a computer network and store data on the storage device in response to a request from an application running on the computer. Make it possible. The file system divides the data into multiple segments in response to the data storage request. Each segment is randomly distributed among multiple storage devices, with redundant information based on one or more segments. The file system verifies that the application stores that data.

In this file system, if the redundant data is a copy of a segment, the random distribution of the data will have at least two storage devices for each segment, randomly and independently of the storage devices selected for the other segments. It can be done by selection. You can request that the selected storage device store data for each segment. The file system can select a subset of storage devices, and can select a storage device that stores a segment from the storage devices in the selected subset.

File system functionality can also be obtained by other applications or through code libraries accessible through the application program interface. Therefore, another aspect is a client or process implemented to perform read or write functions, including storage selection and network transfer scheduling. Another aspect is the storage device or process realized thereby to perform read or write functions, including storage device selection and network transfer scheduling. Another aspect is a distributed computer system that achieves such functionality. These operations can be performed by the client or storage device using only local information, making the system easily extensible.

In another embodiment, the data is restored in a distributed data storage system having a plurality of storage devices for storing the data. When one storage device failure is detected, the data segments and redundant information stored on the storage device are randomly distributed among multiple storage devices. Identify the segment that stored the copy on the failed storage device to restore the data. Identify the storage device that stores the redundant data corresponding to the identified segment. Redundancy information is used to reconstruct copies of the identified segments and then randomly distribute them among multiple storage devices. Such data recovery can be used in combination with the read and write functionality of the file system or distributed storage system described herein.

In another aspect, the video data streams are combined to generate composite video data and stored in a distributed system with multiple storage devices for storing the video data. A copy of a segment of video data stored on a storage device is randomly distributed among multiple storage devices. Read from a storage device that contains a video data stream. These video data streams are combined to generate composite video data. Divide the composite video data into segments. Randomly distribute copies of segments of composite video data across multiple storage devices. Data can be read and stored using the techniques described herein. (Detailed explanation) The following detailed description, which should be read in connection with the accompanying drawings, illustrates examples of embodiments of the present invention. All references cited herein are expressly incorporated herein by reference.

For data transfer between many applications and many storage devices, especially for motion video and accompanying audio, and many independent high-bandwidth time-sensitive data streams such as other temporally continuous media. There are some problems in designing a scalable and reliable distributed system for transfer. In such a system, for example, the application used to author a motion video program is random to a few small pieces of several different files that may be distributed across several storage devices. May be accessed. Several applications may require immediate and simultaneous access to the same data, and any application must be able to access any media piece at any given time. Fault tolerance is also desirable for systems used for broadcasting or other punctual playback. Finally, the system must be extensible and scalable so that new storage devices and new applications can be easily added while the system is running. Other desirable characteristics of such a system include long average time to failure, non-failure at a single point, quick and operational repairability, and uninterrupted storage of the storage device. It includes being fault tolerant and being able to recover lost data.

In one embodiment, the system includes a number of applications connected to a number of separate and independent data storage devices by a computer network. Divide the data into segments. Redundant information for each segment is determined, and the segments and their redundant information are stored in separate storage devices. The choice of storage device for a segment is random or pseudo-random and can be independent of the storage device selected for another segment, such as the previous segment. Both redundant information and random data distribution improve the ability of systems to efficiently transfer data in both directions between applications and storage, resulting in greater fault tolerance.

Redundant information can be a copy of the segment. Replication of this segment also allows the system to control which storage devices a particular application accesses, such as by selecting the storage device with the shortest queue of requests. As a result, the random variation in load is distributed almost evenly across all storage devices.

The application can also request the storage device to transfer data only if the transfer is efficient. Properly scheduling communication on the network can reduce network congestion and increase network bandwidth.<u style="single">One layer</u>It can be used efficiently. It is also possible to eliminate the need for a central control point by having each client schedule communication with the storage device using local information.

FIG. 1A shows a computer system 40 as an example. This computer system includes a plurality of storage devices 42. A storage device is a device that includes a non-volatile computer readable medium, such as an optical disc, on which data can be stored. The storage device also has a high speed, typically non-volatile memory, in which data from the medium is read. Each storage device also has its own independent controller, which responds to requests for access to data stored on the medium, including, but not limited to, read and write access. For example, the storage device 42 can be a server computer and stores data in a data file in the server's file system. The computer system 40 can have any number of storage devices.

Application 44 is a system that requests access to storage device 42 through a request to storage device through computer network 46. The storage device 42 sends data to or receives data from application 44 through computer network 46. Application 44 can include a system that captures data received from a digital or analog source and stores the data on storage 42. Application 44 can also include a system that reads data from storage, such as a system for authoring, processing, or playing multimedia programs. Other application 44 can perform various failure recovery tasks. Application 44 may also be referred to as a "client". One or more Catalog Managers 49 are also available. A catalog manager is a database accessible by application 44 that holds information about the data available on storage 42. This embodiment can also be used to implement a broadcast news system as shown in PCT Publication WO 97/39411 dated October 23, 1997.

The data stored in the storage device 42 is divided into segments. Create redundant information based on one or more segments. For example, each segment may be copied. As a result, on at least two storage devices 42<u style="single">To</u>Each segment will be stored. Alternatively, redundant information can be created by exclusive ORing of two or more segments. Each segment is stored in a storage device 42 different from the redundant information. The choice of storage device for storing segments and their redundant information is random or pseudo-random and can be independent of storage devices for storing other data segments. In one embodiment, the same storage device does not store two consecutive segments. The probability distribution for selecting a storage device for storing segments and their redundant information should be uniform throughout the storage device, with similar storage device specifications such as capacity, bandwidth, and latency. This probability distribution can also be a function of the specifications of each storage device. Random distribution of data segments and corresponding redundant information improves both scalability and reliability.

Figure 1A shows an example of the random distribution of copies of a data segment. In FIG. 1A, the four storage devices 42 represented by w, x, y and z store the data divided into four segments represented by 1, 2, 3 and 4. An example of random distribution of segments and their copies is shown. Here, segments 1 and 3 are stored in storage device w, segments 3 and 2 are stored in storage device x, segments 4 and 1 are stored in storage device y, and segments 2 and 4 are stored in storage device z. ..

FIG. 1B shows an embodiment in which segments and their corresponding redundant information are randomly distributed among storage devices. In FIG. 1B, the four storage devices 42 represented by w, x, y and z store the data divided into four segments represented by 1, 2, 3 and 4. Redundancy information for a segment can be based on one or more segments. In this example, we use two segments in what we call a "redundant set". The exclusive OR of segments i, j in the redundancy set is calculated to obtain the redundancy information Rij. Redundancy information Rij and segment i are exclusively ORed to generate segment j. Similarly, segment i is generated by exclusive OR of redundancy information Rij and segment j. Each segment and redundancy information in the redundancy set is stored on a different storage device. Figure 1B shows an example of random distribution of segments and redundant information. Here, the redundant information R3, 4 for segments 3 and 4 is stored in the storage device w, the segments 2 and 3 are stored in the storage device x, the segment 1 is stored in the storage device y, and the segment 4 and the redundancy are stored. Information R1 and 2 are stored in the storage device z. It is also possible to create redundant information using many other techniques known in the field of fault tolerance.

If the redundancy information is a copy of the segment, then the random distribution of the segment is<u style="single">As shown in Figure 2A</u>Segment table 90<u style="single">Or</u>catalog<u style="single">To</u>It can be represented and tracked by it. That is, for data captured from a given source or from a given file, each segment represented by line 92A has two copies, called A and B. These are represented in column 94A. Column 94A in segment table 90A may also be referred to herein as "A list" or "B list", respectively. Alternatively, each list is seeded for the pseudo-random number generator used to generate the list.<u style="single"></u>It can be represented by number) or by other suitable data structures such as lists or record linked lists, arrays, trees, tables, etc. When using a pseudo-random number generator, care must be taken to ensure that the storage devices indicated by the numbers for any given segment in the A and B lists are not the same. The contents of column 94A indicate a storage device that stores a copy of the segment.

Random distribution of redundancy information based on a segment and two or more segments can be represented and tracked in a catalog as shown in segment table 90B or Figure 2B. That is, for data captured from a given source or from a given file, each segment represented by row 92B has a copy called A, represented within column 94B. Column 96B can be used to indicate where the corresponding redundant information is stored. There are several ways to indicate where redundant information is stored. If a redundant segment is identified as being in a table, the order of the segments in the table can be used to infer which segment corresponds to a given redundant segment. In this case, column 96B may be omitted. For example, the redundant information is as another segment with its own row 92B in the segment table 90B.<u style="single">deal with</u>It is also possible. Alternatively, column 96B can indicate the last segment in the redundant set that contains the segment. In this embodiment, line 92B of the last segment of the redundant set indicates a storage device that stores redundant information for the redundant set. In the embodiment shown in FIG. 2B, column 96B shows the segments in the redundant set for redundant information.

Each segment table or file map can also be stored separately from other segment tables. The segment table can be stored together as a catalog. Catalogs can be stored on individual clients on Catalog Manager 49, which is located in a central database, or can be distributed among several databases or clients. For example, it is possible to maintain a separate catalog for different types of media programs. For example, broadcast news organizations may have separate catalogs for sports news, weather forecasts, headline news, and the like. The catalog can also be stored on the storage device like any other data. For example, each client can access the catalog using a seed of a random number generator. Such catalogs can be identified and accessed by other clients, for example, by sending network broadcast messages to all catalog managers or clients and obtaining a copy of the catalog for individual segment tables. , Or can handle restore requests.

Each segment must have a unique identifier in order to access the data segments. A copy of the segment can have the same unique identifier. Redundant information based on two or more segments has its own identifier. A unique identifier for a segment is a combination of a unique identifier for a source such as a file and a segment number. A unique identifier for a source or file can be determined, for example, by system time, or by any other unique identifier determined when the data was captured from the source, or when the file was created. As described below, the file system accesses the catalog manager to obtain a file that lists the segment table for each source, or the storage device that stores the segment identifier and segment and redundancy information. Can be done. Each storage device can also have a separate file system, which contains the segment identifiers and the directory of locations on the storage device that stores them. An application program run by a client can request data from the client's file system using the source or file identifier, and perhaps a range of bytes within the source or file. The client's file system then uses a unique segment identifier to locate its source or file's segment table, determine which segment needs to be accessed, and read data for each segment. Select a device.

See again Figure 1A and Figure 1B. If application 44 requests access to a data segment selected in one of storage 42, storage puts the request on queue 48. Queue 48 is maintained by the storage device. Applications can make such requests independently of each other or to any central control unit, which makes the system easily scalable. When the redundancy information is a copy of a segment, the choice of storage to which the request is sent is statistically such that the random variation in load applied by multiple applications 44 on multiple storages 42 is statistically across all storages 42. And it can be controlled to be more evenly balanced. For example, each request from application 44 can be processed by a storage device that has the shortest request queue. With any kind of redundant information, the transfer of data between applications and storage can be scheduled to reduce network congestion. Data requests can be made in two stages. That is, a preliminary read request for transferring data from a disk to a buffer on a storage device, and a network transfer request for transferring data from a buffer to an application through a network. To handle these two different requests, queue 48 may include a disk queue and a network queue.

This combination of randomly distributed data segments and corresponding redundant information, as well as scheduling data transfers over the network, allows for a large number of independent, scalable, reliable, bidirectional data across many storage devices and many applications. A system capable of transferring high bandwidth data streams is obtained. By using the copy of the segment as redundant data, the storage device for read access can be selected based on the relative load of the storage device, and the processing capacity can be improved.

Next, with reference to FIG. 3, a process example of randomly distributing a large number of copies of a data segment in several storage devices will be described in more detail. An example process using redundant information based on one or more segments is described below in association with FIG. 24. The following description is based on a real-time capture of motion video data. Examples of other forms include, but are not limited to, other temporally continuous media such as audio, discrete media such as still images and text, or other data such as perceptual data. Can be generalized to data.

It is generally well known how to capture real-time motion video information into computer data files, as described in US Pat. Nos. 5,640601 and 5,577,190. The procedure can also be modified to include steps for dividing the captured data into segments, copying them, and randomly distributing copies of the segments among storage devices. First, in step 120, the capture system creates a segment table 90A (Figure 2A). It also typically creates an image index that maps each image to an offset to the data stream it captures. The indexed data can correspond to, for example, fields or frames. The index can cite other sample boundaries, such as time periods, for other types of data, such as audio. The capture system also gets a list of available storage devices. A method of identifying which storage device is available will be described in more detail below in association with FIGS. 10-12.

In step 121, the capture system creates a data segment. The segment size may be, for example, 1/4 megabyte, 1/2 megabyte, or 1 megabyte for motion video information. The audio information may be divided into segments having a size, for example, 1/4 megabyte. To obtain consistency for segment size storage and transmission splitting, if possible, the segment size should be uncompressed or fixed data rate, disk block and track size, memory buffer size, network. It may be related to a multiple of the packet (eg 64K) and / or cell size (eg 53 bytes in ATM). If the data is uncompressed or compressed using fixed rate compression, the segments can be split at temporal sample boundaries to achieve alignment between the image index and the segment table. Generally speaking, the segment size should be increased to reduce system overhead. System overhead increases with smaller segments. On the other hand, if the amount of stored data and the segment size are such that the data is not distributed to all of the storage devices, the probability that the convoy effect will occur is high. In addition, the larger the segment size, the higher the latency to complete disk and network requests.

Then, in step 122, the capture system selects at least two storage devices 42 from the list of storage devices available to store the selected segment. The choice of storage device for copying one segment is random or pseudo-random. This selection can also be independent of the selection made for the immediately preceding or immediately following segment. The set of selected storage devices can also be a subset of all available storage devices. The selection of a set of storage devices can also be random or pseudo-random for each source or file. The size of this subset should ensure that each storage device has at least one different data segment, minimizing the likelihood of the convoy effect occurring. That is, the data must be at least twice as long (in a segment) as the number of storage devices in a set. The size of the subset must also be limited in order to reduce the likelihood that two or more storage devices in the subset will fail, i.e., double failure, at any given time point. .. For example, the probability that 2 out of 5 storage devices can fail is lower than the probability that 2 out of 100 storage devices can fail, and therefore the number of storage devices that distribute data must be limited. However, there is a trade-off between performance and subset size. For example, if 10 subsets are randomly selected from 100 storage devices and two of the 100 storage devices fail, 10 percent of the files will be adversely affected. Without a subset, 100 percent of the files will typically be adversely affected.

With double failure, the rare probability that two or more storage devices will fail, data segments can be lost. In a standard video stream, one segment loss can result in the loss of one or two frames per minute of program material. The frequency of such failures for a given source or file is a function of its bandwidth and number of storage devices. That is, s = size of lost data in megabytes (MB) n = initial number of storage devices average storage bandwidth per second in b = MB MTBF = Mean Time Between Failures MTTR = Mean time to failure or replacement MTDF = average time for double failure failure SMTBF = average time for all systems between failures Then

<maths num="1"><img file="JP4738457B2_D0001.tif" /></maths>Will be. As an example, in a system with 100 storage devices, each with a capacity of 50 gigabytes, with an MTTR of 1 hour and an MTBF of 1000 hours or 6 weeks, there is a certainty of double failure failure in 115 years. .. If the MTTR increases to 24 hours, there is a certainty that double failure will occur in 4.8 years.

See Figure 3 again. After selecting the two storage devices, the current segment is sent and stored in each of the selected storage devices in step 124. These write requests can be asynchronous rather than sequential. The capture system then waits in step 126 for the storage device to approve the storage completion of the segment. When storing data in real time while capturing, the data transfer in step 124 may be performed in two steps, similar to the read operation described in more detail below. That is, the client can first request the storage device to prepare a free buffer for storing the data. The storage device can answer the estimated time the buffer is available. When this estimated time is reached, the capture system can request the storage device to receive the data. The storage device may then receive the data in the buffer, transfer the data in the buffer to the storage medium, and send the approval to the capture system.

If the time expires before the capture system receives approval, the segment can be sent back to the same storage or a different storage. Other errors can also be handled by the capture system. It is also possible to have a separate thread for each copy of the segment to ensure successful storage on the selected storage device.

After successfully storing the data in storage, the chapter system updates segment table 90 in step 127. If it is determined in step 128 that the capture is complete, the process terminates. Otherwise, go back to step 121 and repeat the process for the next segment. The segment table can be maintained, for example, in the main memory of the capture system as part of the file system. In this example, the capture system manages the segment table and storage selection, but it is also possible for other parts of the system, such as Catalog Manager 49, to coordinate these activities. In step 129, the updated segment table can be sent, for example, to the catalog manager. Alternatively, the catalog manager can generate a segment table by using the accumulated knowledge of system operation, and can also send this table to the capture system on demand.

FIG. 4 is a flow chart describing in more detail how the storage device stores the captured data segments or redundant information. In step 140, the storage device receives a data segment from the capture system and stores the data in the storage device's buffer. Assuming that the storage device uses a data file for storage, the storage device opens the data file in step 142 and stores the data in the data file in step 144. The catalog manager can also specify the location to store the segment. The data can be attached to an existing data file or stored in a separate data file. As discussed earlier, in step 145, the storage or catalog manager uses a unique identifier for each segment and further stores a table that maps the segment identifier to that location on the storage. , It is also possible to track the segment. This table can provide data file abstraction on the storage device. When the storage actually writes data to its main storage depends on other read and write requests pending in other applications. The management of these simultaneous requests will be dealt with in more detail below. Then, in step 146, the file can be closed. At step 148, approval can be sent to the capture system.

Once the processes in Figures 3 and 4 are complete, the captured data is randomly distributed across several storage devices, using at least two copies for each segment. Many applications can request access to this data. The mode of making this access is probably random. Therefore, it is clear that any storage device can receive many requests from many applications to read data from a file stored on the storage device and to write data to the file. To manage requests, request queue 48 is maintained by each of the storage devices 42, as described above. In the following description of an example embodiment, the storage device maintains two queues, one for disk access requests and the other for network transfer requests. One embodiment of these disk and network queues will be described in more detail below in connection with FIG.

When an application program running on client 44 requests data, it selects the storage device to meet the request when storing each data segment on at least two storage devices. The segment table 90 for the request data is used for this purpose. Storage choices can be made by the application program requesting the data, by the file system of the client running the application program, by coordination between the storage devices, or by another application such as the Catalog Manager. .. The selection may be random or pseudo-random, or it may be based on the minimum frequency of use algorithm or the relative length of the storage queue. Choosing a storage device based on the relative length of the queues on the available storage devices allows the load of a large number of applications to be evenly distributed across the set of storage devices. Such selection will be described in more detail below in connection with FIGS. 16-18.

Hereinafter, the details of one specific embodiment will be further described. For this purpose, the storage device 42 may be implemented as a server or an independent control storage device, and application 44 will be referred to as a client. The client can execute application programs that perform various tasks. A suitable computer system for implementing a server or client typically includes a main unit, which usually includes a processor that connects to the memory system via an interconnect mechanism such as a bus or switch. Both the server and the client also have a network interface that connects them to the computer network. The network interface should be redundant to accommodate fault tolerance. The client can also have an output device such as a display and an input device such as a keyboard. Both input and output devices can be connected to the processor and memory system via an interconnect mechanism.

It should be understood that one or more output devices may be connected to the client system. Examples of output devices include communication devices such as cathode ray tubes (CRT) displays, liquid crystal displays (LCDs), printers, modems or network interfaces, as well as video and audio outputs. It will also be appreciated that one or more input devices may be connected to the client system. Examples of input devices include keyboards, keypads, trackballs, mice, pens and tablets, communication devices such as modems or network interfaces, video and audio digitizers, and scanners. It will be appreciated that the present invention is not limited to any particular input device or output device used in combination with a computer system, and even those described herein.

The computer system can be a general purpose computer system programmable using a high-end computer programming language, such as the "C" and "C ++" programming languages. The computer system can also be specially programmed special purpose hardware. In general purpose computer systems, the processor is typically a commercial processor, such as an x86 series processor available from Intel, such as the Pentium II with MMX technology. And similar devices available from AMD and Cyrix, 680X0 series microprocessors available from Motorola, Digital Equipment There is an Alpha series available from Corporation (Digital Equipment) and a PowerPC processor available from IBM. Many other processors are also available. Such microprocessors can run programs called operating systems, such as Windows® NT, Windows® 95, UNIX®, IRIX, Solaris, DOS. , VMS, VxWorks, OS / Warp, MacOSSystem 7 and OS8 operating systems. The operating system controls the execution of other computer programs and provides scheduling, debugging, I / O control, compilation, storage allocation, data management and memory management, as well as communication control and related services. Processors and operating systems define a computer platform for each application program in a high-level programming language.

Each server can be implemented using a large amount of main memory, eg, much more than 32 megabytes of memory, or, for example, an inexpensive computer with a disk capacity of several gigabytes. The disks can be one or more single disks, a redundant array of independent disks (RAID), or a combination thereof. For example, the server can be a system using a Pentium® or 486 microprocessor with a real-time operating system such as Windows® NT or VxWorks. Authoring systems, capture systems, and playback systems can be implemented using the platforms currently used in the art for this primary product. For example, MEDIA COMPOSER from Avid Technology, Inc. in Tewksbury, Massachusetts is a PowerPC microprocessor and MacOS System. I'm using a Power Macintosh computer from Apple Computer, Inc., which has 7 operating systems. Systems based on the Pentium® II processor with Windows® NT operating system and MMX technology from Intel are also available. Examples of playback systems include the "SPACE" system from Pluto Technologies International Inc. in Boulder, Colorado, or the AIRPLAY system from Avid Technology using the Macintosh platform. Catalog managers can be implemented using any platform that supports a suitable database system, such as the Informix database. Similarly, an asset manager that tracks the types of data available in the system can also be implemented using such a database.

Memory systems in computers typically include computer-readable and writable non-volatile recording media, such as magnetic disks, optical disks, flash memory and tape. The disc can be removable, such as a flop disc or CD-ROM, or fixed, such as a hard drive. A disc has a large number of tracks, in which signals are stored, typically in binary form, i.e., interpreted as a series of 1's and 0's. Such signals can define an application program executed by a microprocessor or information stored on a disk and processed by the application program. Typically, in operation, the processor reads data from a non-volatile recording medium into an integrated circuit memory element. Integrated circuit memory elements are typically volatile random access memories, such as dynamic random access memory (DRAM) or static memory (SRAM). Integrated circuit memory elements allow faster access to information by processors than disks. Processors typically manipulate data in integrated circuit memory and then copy the data to disk when processing is complete. Various mechanisms are known for managing data movement between a disk and an integrated circuit memory element, and the present invention is not limited thereto. It will also be appreciated that the present invention is not limited to any particular memory system.

It will be understood that the present invention is not limited to a particular computer platform, a particular processor, or a particular high-level programming language. In addition, the computer system may be a microprocessor computer system or may include a large number of computers connected through a computer network.

As mentioned above, each storage device 42 can have a file system for each application 44 when accessed through a server. The file system is typically part of the operating system and maintains files of data. Files are well-known logical structures, defined and implemented by the file system, that map the names and sequences of logical records of data to locations on physical storage media. The file system masks the physical location of the data from the application program, but the file system typically attempts to store the data in a single file within adjacent blocks on the physical storage media. The file can be specific to various record types, or it can be undefined and allowed to be interpreted or controlled by the application program. The file is called by the application program by its name or other identifier and is accessed through the file system using operating system-defined commands. The operating system performs the basic file actions for creating a file, opening the file, writing to the file, reading the file, and closing the file. These operations may be synchronous or asynchronous, depending on the file system.

As described herein, file or source data is stored on a segment-by-segment basis, and copies or other forms of redundant information are randomly distributed among a large number of storage devices.

Generally speaking for most file systems, in order to create a file, the operating system first identifies a space within the storage controlled by the file system. Then create an entry in the catalog for the new file. The catalog contains entries that indicate the names of available files and their location within the file system. Creating a file may also involve allocating a certain amount of available space to the file. In one embodiment, a segment table can be created for the file. When you open a file, the handle is typically returned to your application program, which you can use to access the file. When you close the file, the handle becomes invalid. The file system uses handles to identify the segment table for a file.

To write data to a file, the application program issues commands to the operating system, which provides both the file's indicators, such as filenames, handles or other descriptors, and the information to write to the file. specify. Generally speaking, given a file indicator, the operating system searches the directory to find the location of the file. Data can be written to a known location in the file or to the end of the file. Directory entries can store pointers at the end of the current file, called write pointers. This pointer can be used to calculate the physical location of the next available block after storage and write information to that block. The write pointer can be updated in the directory to indicate the new end of the file. In one embodiment, the write operation randomly distributes a copy of a segment of a file across storage devices and updates the segment table for the file. The write operation can also store segments and corresponding redundant information in different storage devices.

To read data from a file, the application program issues a command to the operating system to specify the file's indicator and the memory location in which the read data is located among the memory locations assigned to the application. To do. Generally speaking, given a file indicator, the operating system searches that directory for the relevant entry. The application program can specify an offset from the start of the file to use, or in a sequential file system, the directory can give a pointer to the next block of data to read. In one embodiment, storage selection and data transfer scheduling are implemented as part of the client's file system read operation.

The client uses a file system or special code library with a default application programming interface (API) to translate a request for a portion of a file into a request for a data segment from a selected storage device. The storage device can also have its own file system, completely separate from the client's file system. All segments on the storage device can be stored, for example, in a single file on the storage device. Alternatively, the client file system can use the storage device as raw storage on the network and use the catalog manager and segment table to achieve file extraction. The segment table of the file can also indicate the location of that segment on the selected storage device for each segment.

One of the main advantages of using a file system is that for application programs, files have no concerns about their physical storage medium or the location on that medium that the operating system uses to store data. It is a logical structure that can be created, opened, written, read, and closed. In a network file system, the file system manages data requests from specified files from various storage devices, and application programs know more about the physical storage or computer network in which the data is stored. There is no need. If the storage device has its own independent file system, the client file system also does not need to know the details of the storage device's storage mechanism. The storage device should be, for example, a file system associated with the Windows® NT file system, or a real-time operating system file system such as VxWorks, or a file system that allows asynchronous operation. Can be done.

The storage device is interconnected with the catalog manager using a client and optionally a computer network. A computer network is a set of communication channels that interconnect a set of computer devices or nodes that can communicate with each other. Nodes can be computers such as clients, storage and catalog managers, or various types of communication devices such as switches, routers, gateways and other network devices. As the communication channel, various transmission media including optical fiber, coaxial cable, copper twisted pair, satellite link, digital microwave radio and the like can be used.

A computer network has a topology that is a geometrical configuration of the connection of nodes by a network. Topological types include point-to-point connections, linear buses, circular connections, star connections, and multi-connection networks. The network can use various combinations of these basic topologies. The topology can change depending on the physical installation. An uninterrupted switch-based network can be used that connects each node, a client or storage device, directly to the same switch. In some embodiments, a large number of clients and storage devices can be connected to physical loops or subnetworks and interconnected to a switching fabric. The system can also be connected using a large number of switches.

The network also has a network architecture that defines protocols, message formats, and other standards for communication hardware and software to communicate between devices on the network. A commonly used network architecture is the International Standards Organization seven-layer model, known as the OpenSystems Interconnection reference model. The 7 layers are application, presentation, session, transport, network, link and physical layers. Each machine communicates with any other machine in one of these layers using the same communication protocol.

In one embodiment, the link layer preferably maintains the order in which the packages are received by the client, avoiding the potential for infinite latency. Therefore, suitable link layer protocols include asynchronous transfer mode (ATM) networks, such as OC3, OC12, or even higher bandwidth networks. ATM systems operating in AAL15 mode are preferred. Ethernet networks with capacities of 100Tx to Gigabit (1,000Tx) also provide efficient packet transmission from source to destination. Suitable Ethernet network platforms are available, for example, from 3Com, Santa Clara, CA. An example of an ATM system is available from Fore Systems, Warrendale, Pennsylvania, or Giga-Net, Concord, Massachusetts. Fiber Channel, FDDI, or HIPPI networks are also available. Different clients, catalog managers and storage devices can all communicate using the link layer protocol. Communication in this layer also reduces the overhead of memory copy executed to process the data encapsulated for each layer protocol. Bandwidth distributed network file systems from Polybus Systems Corporation in Tyngsborough, Massachusetts are also available.

So far, the computer platform of one embodiment has been described, but the operation and details of one embodiment will be further described below.

In one embodiment, there is a storage device and a process for maintaining the data stored on the storage device. For example, a failure recovery procedure may include making an additional copy of a file. In addition, files can be deleted or added based on the availability of the file, that is, the need for reliable access to the file. Finally, some maintenance procedures may involve deleting files on storage, copying files to another storage, and removing storage from the system. Files can also be stored or moved from the system to the archiving system. These processes will be described in more detail in relation to FIG. 5 and FIG. Such a data management process can be performed by a catalog manager, another storage device, or a client. Even if the client performs these processes, it does not occupy the resources of the catalog manager or storage and can be used for other important tasks such as responding to the client's data requests. ..

FIG. 5 is a flowchart describing in more detail how the failure can be recovered after the storage device becomes unavailable and the failure is detected. One method of detecting such a failure will be described in more detail below in association with FIGS. 10-12. Failure to repeatedly respond to a request can also be used to indicate a failure. The success of this process depends on the number of copies of each segment in the system, or the number of segments in the redundant set. Assuming that the copy number is N, the system operates without data loss even if N-1 storage devices fail. After a storage device fails, a new storage device can be installed in its place to reproduce the lost data or recreate the lost data and distribute it to all the remaining storage devices. Figure 5 describes the process when the redundant data is a copy of the segment. Figure 25, described below, shows the process when the redundancy information is based on two or more segments.

In step 200, an additional copy of the data can be made by first selecting the data, eg, a file or source to reproduce. The files to be reproduced can be selected in order of priority, and can also be selected either automatically or manually. This type of restore can reconstruct data from some files and make it available before data from other files is restored. In step 202, the source segment table is used to identify the lost data segment, i.e., the data stored on the lost storage device. In step 204, a new storage device is selected for each lost segment, as is typically the case when the data is first captured, if no new storage device is available to replace the failed storage device. Alternatively, select an exchange storage device. In step 206, a copy of the lost segment is read from alternative storage and stored in the selected storage. The file operations in steps 204-208 are asynchronous and can be performed by a separate thread for each segment. Such operations take advantage of the many-to-many read / write capabilities of this network architecture. Next, in step 208, the successful completion of the copy operation is followed by updating the segment table of the file. If the catalog manager maintains the segment table when the process is complete, the catalog manager can be updated with the new segment table in step 209. If the underlying segment table is represented by a seed to a pseudo-random sequence generator, it may be necessary to create and modify the actual table.

The speed and redundancy restoration of repopulation for unloaded systems using this process is defined by the following equations:

<maths num="2"><img file="JP4738457B2_D0002.tif" /></maths> here, s = size of lost data in megabytes (MB) n = initial number of storage devices Average storage bandwidth expressed in b = MB / sec User demand load, expressed in d = MB / sec For example, if one of the 10 storage devices fails and access to 50GB of storage is lost, then n = 10 storage devices and unit bandwidth b = 10MB / sec, then (n-1) = 9 and (b / 2) = 5. Therefore, if there is no other load, it will take about 20 minutes to restore. This absolute restore rate usually decreases as the reciprocal of the variable playback load on the client. For example, with a 50% load, the input time increases by 200%. When called, the redistribution task can be performed at a fast rate, switching the multi-dimensional storage checkerboard to a large number of storage devices, but the re-entry activity is done as appropriate according to the client file service request. The actual effect is that the failed storage device causes some loss in the total bandwidth of the storage device. Ensure that the most important files are restored first by deciding the priority of file selection for restoration.

FIG. 6 is a flow chart describing in more detail how additional copies of the data can be made. Calling this process provides an additional data copy of mission-critical or demanding data. You can also give a new copy a date stamp to indicate when the copy can be deleted. Given the selected data, in step 210, a segment of the data is selected. In step 212, each segment is randomly assigned a new storage device, ensuring that each storage device has at most one copy of a given segment. Next, in step 214, the segment is stored on the selected storage device. If the storage of this segment is completed successfully, the data segment table is updated in step 216. If it is determined in step 217 that all segments of data have not yet been copied, the process is repeated, returning to step 210 and selecting the next data segment. When the process is complete, the catalog manager can be updated with the new segment table in step 218 if the catalog manager has a segment table. Although this process is continuous across segments, each segment can be processed using a separate thread, and the file behavior in step 214 can be asynchronous. This process ensures that the copy is made quickly. By this procedure, the seed of the pseudo-random number generator can still be used to represent the segment table.

FIG. 7 is a flow chart detailing how to delete a copy of the data. This process can be called, for example, when the data is no longer requested much. For example, a date stamp on the copy can be used to indicate when to delete the data. Assuming the segment table shown in Figure 2 for a given data, in step 220 we select one of the copy sets, i.e. one column in the table. In step 222, each segment in the column is deleted. If the deletion operation is successfully completed for each segment in step 222, the segment table is updated in step 224. Steps 222 and 224 are repeated segment by segment. The process may be continuous throughout the segments, or each segment may be processed by a separate thread. When the process is complete, the catalog manager can be updated with the new segment table in step 226 if the catalog manager maintains the segment table.

FIG. 8 is a flow chart describing how to remove another active storage device from the system. For example, the file system is used to identify the data available on the storage device by identifying the list of files. First, the storage device is made available for writing new segments. This step can be performed, for example, by notifying the catalog manager or by sending a broadcast message to all clients. Redistribute the segments of each file onto other storage devices, and then remove the storage devices from the system. Given this list of files, in step 230 select the next file to process. In step 232, the segment table is used to identify all segments of this file on storage, including the segment that contains the redundant information. In step 234, the segment to be processed next is selected. In step 235, random selection from the remaining storage devices assigns a new storage device to the selected segment, ensuring that no storage device has more than one copy of a given segment. Next, in step 236, data is written to the newly selected storage device. If this write operation is successfully completed, the segment table is updated in step 237. If it is determined in step 238 that all the segments of a given file have been redistributed, then in step 239 the segment table can be sent to the catalog manager as appropriate. Segments can be processed by separate threads with sequential or asynchronous file processing. After updating the Catalog Manager, you can delete the segment from the old storage. If it is determined in step 240 that the next file exists, the process proceeds to the next file. Once all the files have been redistributed, this process is complete and the storage device can be removed from the system.

FIG. 9 is a flowchart illustrating how data can be copied for storage or backup. This process involves copying one copy of each segment of data from available storage to a backup storage system such as an archive storage medium. Each copy set and any redundant information can also be removed from all storage units. This process can be performed in step 250 by selecting a copy set, eg, A list, from a column in the segment table. Alternatively, it is also possible to read out each segment in turn and select a storage device for each segment using techniques applied by other applications as described above. In step 252, each segment from the selected copy set is read from its storage device and stored on the storage medium. If each segment is successfully copied to the storage medium, then in step 254 all remaining copy sets or all remaining segments from any redundant information can be removed from the storage device. Segments can be processed sequentially or by separate threads using asynchronous file processing. The catalog manager can then be updated in step 256.

This section describes how to monitor storage devices to determine availability and detect failures in relation to FIGS. 10-12. There are several ways to determine if a storage device is available: pole the storage device, handle exceptions from the storage device, or the storage device periodically applies or multiple applications. Includes notifying about its availability. In one embodiment, in addition to Catalog Manager 49 or any other client, both monitor which storage device 42 is active in the system and maintain a catalog of segment tables for each file. Can be done. One of the methods for monitoring the storage device is shown in FIGS. 10 to 12. Each storage device available on the system establishes a process that periodically informs the catalog manager that it is available. That is, this process can be thought of as a state machine with a first stage 60 in which the storage device periodically increments the counter in response to a timer interrupt or event from the system timer. When this counter reaches a certain amount, such as 100 milliseconds, a transition to another state 62 occurs. At the transition to state 62, the storage device sends a signal called "ping" to the catalog manager. It is preferable that this signal be a message as small as 1 ATM cell and do not use much bandwidth to transmit. This signal can also include the identifier of the storage device and possibly other information such as capacity, efficiency and / or bandwidth availability of the storage device. At the next timer interrupt or event, a transition is made that resets the counter and returns to state 60.

The catalog manager may want to keep track of available storage devices. For this purpose, the catalog manager can use List 70 of storage devices. An example is shown in FIG. This storage device list can be implemented as a table indexed by an identifier in the storage devices shown in 72. If a storage device is present or available, other information about bandwidth, memory capacity, or storage device power is available in column 74. There is also a count since the last "ping" from storage, as shown in column 76. If this count exceeds a predetermined amount, such as 300 milliseconds, the storage device is considered unusable and the failure recovery procedure described above can be followed. An example of a tracking process that maintains Listing 70 of storage is described in more detail in relation to FIG.

Figure 12 shows which storage devices are available to the catalog manager.<u style="single">Ka</u>A state machine that describes a tracking process that can be performed when making a determination. One of these state machines can also be established for each storage device as a process on the catalog manager. The first state 80 is a wait state and increments the count value 76 for the storage device in the storage device list 70 with respect to the storage device in response to the periodic timer interrupt. When a "ping" is received from the storage device, a transition to state 82 occurs. In state 82, verify the existence of this storage device in Listing 70. If the storage device is in Listing 70, the storage device count 76 can be reset, information about this storage device can be updated, and a transition back to state 80 is made. If the storage is not in the list, it is added to the list, the count is reset, and a transition is made to return to state 80. After a given increment, if the storage count is greater than a given time-out value, such as 300 milliseconds, then a failure recovery procedure is performed. That is, the storage device is removed from Listing 70 and the fault-tolerant procedure is performed in state 84. If the catalog manager receives a "ping" from storage and the storage does not have a corresponding tracking process, the catalog manager adds the storage to the list and the tracking process for this storage. To create.

In addition to having a catalog manager 49, the system can also include a database called an asset manager. The Asset Manager stores various information about the media sources available in the system, such as an index for each file. Catalog managers and asset managers can also be combined. A useful type of information stored in the Asset Manager is the table shown in Figure 13, which is equivalent data based on the source identifier and the extent within that source, as shown in US Pat. No. 5,267,351. -It is related to files. The source identifier is an indication of the source of the data and can be an analog source. In contrast, the data that is actually available is a digitized copy of the source stored on the storage device. That is, the table has an entry for the source identifier, a range within the source identifier 102, and an indication 104 of equivalent data from the source, such as a list of data files. Listing 104 can be used to identify one of the data files for the source and then access the segment table for that file to determine where the segments of the data are distributed on various storage devices. The segment table 90A in Figure 2A can also be included in this list in Figure 13, as shown in 106 and 108. The segment table 90B in Figure 2B can be included in Listing 104 as well. Equivalence between such data can be maintained by any application program.

The Catalog Manager is a database that monitors how data is distributed on various storage devices, so it should be designed to increase fault tolerance and availability and reduce its bottleneck probability. Is. Therefore, the catalog manager is implemented using traditional distributed database management techniques. Also with highly available machines such as those from Mrathon Technologies, Tandem Computers, Stratus, and Texas Micro, Inc. , It is also possible to implement a catalog manager. There may also be several catalog managers used by separate client applications. Alternatively, each client application can use standard techniques to maintain consistency between multiple data copies and maintain a copy of its own catalog locally. Thus, the catalog manager is not the center of failure. The client can also act as its own catalog manager. The catalog can also be treated as data, and its segments and redundant data are randomly distributed among storage devices. Each client may also have a segment table or a seed of a random number generator representing the segment table for each catalog.

Now that we have described how data can be captured and stored in a storage device, and how data storage on the storage device can be managed, authoring and playback will be performed. The client application will be described in more detail in relation to FIGS. 4 and 15.

Several types of systems can be used to author, process, and display multimedia data. These systems can be used to modify data, define different combinations of data, create new data, and display the data to the user. Various techniques for realizing these types of systems are known in the art.

Multimedia authoring, processing and playback systems typically have a data structure that represents a multimedia composition. This data structure is ultimately like digitized video or audio, using a source material identifier such as a unique identifier or filename, and possibly a time range within the source material that defines the clip. , Quote the source material clip. The identifier may be in any format as long as it is used with a list of equivalent data files to identify the filename of the source material. It is also possible to use an index to convert a time range in the source to a byte range in the corresponding file. This byte range can be used with the file's segment table to identify the storage device for retrieving the required segments and data.

FIG. 14 shows an example of a list structure that can be used to represent part of a multimedia composition. In the example shown in FIG. 14, there are several clips 260, each containing a citation to the source identifier, indicated by 262, and a range within the source, as indicated by 264. In general, it would be nice to have such a list for each track of media in the time composition. There are various data structures that can be used to represent the composition. In addition to the list structure, PCT Publication Application WO 93/21636, published October 28, 1993, shows a more complex structure. Typical examples of other multimedia compositions are as shown in the Open Media Framework Interchange Specification from Avid Technology, Inc., Advanced Authoring Format (AAF) from Multimedia Task Force, DirectShow from Microsoft, and PCT Publication wo 96/26600. Includes Bento from Apple Computer.

As mentioned earlier, the data structures used to represent multimedia programs can use a number of formats of data and display them in synchronism. The most common example is the production of a television program or movie that includes motion video (often two or more streams or tracks) and accompanying audio (often four or more streams or tracks). Is. As shown in FIG. 15, the client computer can have a corresponding set 290 of memory buffers 294 allocated in main memory. Each buffer can be implemented as a "serialized" buffer. In other words, the client inserts the data received from the storage device into these independently accessible parts and sequentially reads it from the buffer set. Since requests can be sent to several storage devices and data can be received at different times for the same stream, the buffer may not fill continuously on write, but reads sequentially on lines. We are displayed. In FIG. 15, filling in the buffer is indicated by the presence of data in the buffer. As shown in 293 and 295, any empty buffer can be filled at any time. However, each buffer set has a current read location 291 that reads data from it and advances over time, as shown in 297. Subsets 292,296 of these buffers can also be assigned to each data stream.

Each buffer in the buffer set has a size corresponding to a fixed number of data segments, and the segment size is the size of the segment stored in the storage device. Given that there are several, eg, four audio buffers per audio data stream 292, each buffer can accommodate several, eg, four segments. Similarly, each video stream 296 can have several buffers, eg, four buffers, each containing several, eg, four segments. Each of the buffers can be divided into independently accessible parts 298. The size of part 298 corresponds to the size of the data packet that is planned to be forwarded over the network.

Video and audio data can be stored in different data files and can be combined in any combination, so efficient management of data requests for these different streams on the client side can result in further performance gains. .. For example, a client application can identify a stream from which data can be read and then determine the amount of data to read, if any. The process of performing this type of read operation management is described in US Pat. No. 5,045,940. In general, the client determines which stream has the least amount of data available for display. If there is enough buffer space in the buffer set for the stream to read a certain amount of data efficiently, then that data is requested. In general, data is read efficiently if the space available in memory for the selected stream is large enough to hold one network transmission data unit. When it is determined that the data of a certain stream is requested, each segment of data is requested from the storage device selected from the storage devices in which each segment is stored.

The process of converting a composition into a data request and displaying the data will be described below in association with FIG. In order to know which file is requested from the storage device, the application program running on the client system has a data structure representing the composition as shown in FIG. 14, and the file name in these files in the step of FIG. And can be converted to a range. For example, a request can be sent to the asset manager for each source identifier and for each range within that source. In response, the Asset Manager can return the filename of the file containing the equivalent media corresponding to the received source identifier and range. A segment table of files and a list of available storage devices can also be catalog managers.

If the client requests a data segment for a particular data stream, the client selects a storage device for the requested segment in step 272. This choice in one embodiment, which provides redundancy by copying each segment, is described in more detail below in connection with FIGS. 17 and 18. In general, the storage device with the shortest queue 48 (Fig. 1) may be selected. The client then reads data for that segment from the selected storage device in steps 274-278. Step 274 may be understood as a pre-read step, where the client sends a request to the storage to read the desired data from the non-volatile storage to a faster, typically volatile storage. The request to the storage device can include an indication of how long it will take from the request to the client having to receive the request data, i.e., the deadline. If the pre-read request is accepted, the client waits in step 276. Requests are placed in storage queue 48, and then deadlines are used to prioritize requests as described below. In step 278, data is transferred from the storage device after the data becomes available in the buffer of the storage device. This step may include scheduling network usage to maximize network utilization efficiency. The received data is stored in an appropriate buffer on the client and finally processed and displayed in step 280. If the segment is lost in storage, the redundant information is used to reproduce the segment.

There are several ways to initiate a preread request, including storage selection in step 274 and data transfer in step 278. For example, Media Composer from Avid Technology, Inc. in Tewksbury, Massachusetts allows users to set either the number of clips or the amount of time as a look-ahead value, and how far ahead in composition the application data data. Indicates whether a read request should be initiated. A program schedule for television broadcast description can also be used for this purpose. Such information can be used to initiate storage selection and pre-read requests. Such pre-reading is feasible even if buffer space is not available in buffer 290 (Fig. 15), as shown in European Patent Application No. 0674414A2 published September 9, 1995. The amount of space available in buffer 290 (FIG. 15) can be used to initiate data transfer in step 278 (FIG. 16), or preread (step 274) and data transfer (step 278).

One process that allows the client to make a good estimate of the storage device with the shortest request queue without having to scour all available storage devices, in connection with FIGS. 17 and 18. explain. First, in step 330, the client sends a request with the threshold E1 to the first storage device. Threshhold E1 gives an estimate of the time that the request must be answered. This estimate can be expressed as a time value, the number of requests in the storage device's disk queue, such as 4, or some other measure. The meaning of this threshold is that, for example, if the storage device is able to respond to the request within a certain time limit, the request must be accepted by the storage device. The client receives the response from the storage device in step 332. The answer indicates whether the request was accepted and placed in the storage disk queue, or the request was rejected. This is determined in step 334. If the request is accepted, in step 336, the client is given an estimate of when the data will be available in the buffer of the storage device. For example, if the requested segment of data is already in the buffer, the storage device indicates that the data is immediately available. The client may then wait shortly after the estimated time elapses until it is time to request the transfer of data. If the request is rejected, the storage device returns an estimate of the amount of time that the storage device may actually take, such as the actual size of the number of entries in the disk queue. In step 340, this actual estimate is added to the value K to obtain the threshold E2. The value K is 2 to represent the number of entries in the disk queue. The threshold E1 and the value K are user-definable. In step 342, a request indicating the threshold E2 is sent to the second storage device. Then, in step 344, the client resembles the answer received in step 332. To receive the answer. If the answer determines in 346 that the request has been accepted, the client has an estimate of when the data will be available in the second storage, as shown in step 336, after which the client will You can wait to schedule the data transfer. Otherwise, in step 348, an unconditional request, i.e. a request with a large threshold, is sent to the first storage device. Next, the approval is received in step 350, and as shown in step 336, the estimated value at the time when the data becomes available in the buffer of the storage device is shown.

On the other hand, when a storage device receives a request, it does not know whether it is the first storage device or the second storage device selected by the client. Conversely, the storage device simply receives the request, as shown in step 360. In step 362, the threshold indicated in the request is compared to an estimate of the time the client has to wait for the storage device itself. For example, compare the size of the storage disk queue with the specified threshold. If the threshold in the supply is greater than the storage estimate, then a request is entered into the disk queue and in step 364, an estimate of when data becomes available in the storage buffer is determined. This estimate can be determined, for example, based on disk access speed, disk queue length, and possibly the latest performance moving average. In step 366, the approval is sent to the client. This includes the time point at which the data potential in the buffer of the storage device is estimated. Otherwise, send a rejection in step 368 to give this estimate, such as the actual length of the disk queue.

The storage device can also track which segment is in which buffer on the storage device. Segment data can be read from storage media into one of the free buffers or a buffer occupied by the least recently used segment. In this way, data for a segment can be made immediately available in a buffer by requesting the segment twice.

Alternatively, the client can use another method to select a storage device to retrieve the data. This will be discussed below. After sending the request, the client receives an authorization from storage indicating that the request has been placed in the storage's disk queue. Instead of receiving an estimate of when data becomes available in the storage buffer, the client waits until it receives a ready signal indicating that the storage has read the requested data into the storage's designated buffer memory. You can also do it. During this latency, the client can perform other tasks, such as issuing a request for another data segment, viewing the data, or processing the data. One problem with this alternative is that the client accepts an unsolicited message, a ready signal from storage, and in response, the client modifies the context and processes the message. The client may be performing other actions and in use. This process gives a more accurate estimate of when the data becomes available in the storage buffer, but it immediately adds complexity to the client due to the possibility of changing the context and processing incoming messages. Become.

If the segment table keeps track of a copy of each segment, there are several other ways to select a storage device from the segment table for a file. For example, if the client is making a file read request, the client can randomly extract from either the "A" list or the "B" list for the file in question. Alternatively, the client reviews all of its currently outstanding requests, that is, those that have been sent but have not yet been executed, and the storage device on the A and B lists that has the least outstanding requests. , Can be extracted to a file. This selection method can reduce the likelihood that the client will conflict with its own outstanding requests and will spread the requests even more across all storage devices. Alternatively, instead of looking at the outstanding request, the client looks at the history of its latest request, for example the last "n" request, and for the next request, the A list for the least used segment so far and Any storage device can be extracted from the B list. This selection method will spread the demand even more across all storage devices and can avoid concentrating the demand on a particular storage device. The client can also request a measure of the length of its disk queue from each storage device. The client can issue a request to the storage device with the shortest disk queue. Another possibility is that the client can send a request to two storage devices and eventually receive data from only one. Using this method on a local area network, the client can undo unused requests. On a wide area network, the finally selected storage device can undo unused requests in other storage devices.

The storage device may also receive a large number of requests from a large number of applications. A queue 48 (Figure 1) is maintained for each storage device to manage requests from many applications and ensure that the most important requests are processed first. Queues can also be maintained in several parts, depending on the complexity of the system. That is, the storage device can maintain different queues for disk access and for network transfers. Queues are, for example, requests from punctual applications that use data with a specific time limit from playback to broadcast, from requests from other applications such as capture systems, authoring tools or service and maintenance applications. , It is also possible to separate. In addition, storage requests can be separated from requests from authoring tools as well as requests from service and maintenance programs. Requests from authoring tools can be further separated from service and maintenance requests.

FIG. 19 shows an embodiment of queue 48 utilizing disk queue 300 and network queue 320. The disk queue has four subqueues 302, 304, 306 and 308, one for play, capture, au ring, and service and maintenance client programs, respectively. Similarly, network queue 320 also has four subqueues 322,324,326 and 328. Each queue contains one or more entries 310, each of which has a request field 312 indicating the client making the request and the requested action, a priority field 314 indicating the priority of the request, and a buffer associated with the request. Includes buffer field 316 indicating. The request priority indication can be a deadline, a time stamp, an indication of the amount of memory available to the client, or an indication of the amount of data currently available to the client. If the storage device had a priority scheduling mechanism, it would be possible to indicate the type of priority stamp to use.

Priority values can be generated in many ways. Priority values for authoring or playback systems are generally a measure of when an application must receive request data. For example, in a read operation, the application can report (in milliseconds or frames or bytes) how much data is available for playback in the eyes of data loss. The priority indication to the capture system is generally a measure of when the client must transfer data from its buffer to storage. For example, in write operation, the application can report (in milliseconds, frames, or bytes) how much empty buffer space it can fill before the buffer overflows. When using milliseconds as the scale unit, the system has an absolute time clock that can be used as the basis for determining the order of requests in queue 49, with all applications and storage devices being this. It can be synchronized with the absolute time clock. If this synchronization is impractical, the application may also use the time associated with the application to indicate how long it will take for the request data to be received by the client after the request has been made and passed. Is. Assuming low communication latency, the storage device can also convert this relative time into an absolute time that is consistent with the storage device.

The storage device processes the requests in its subqueues 301 to 308 in the order of their priority. That is, first, the requests in the queue with the highest priority are processed in the order of their priority values, and then the requests in the queue with gradually lower priority are processed. For each request, the storage device transfers data between the disk and the buffer indicated by the request. Read requests process the request and then transfer the request from the disk queue to the network queue. A write request removes the request from the disk queue after the write operation is successfully completed.

In one embodiment, described in more detail below, the storage device uses network queues to prioritize network transfers in the process of scheduling these transfers. In this embodiment, the client requests the transfer of data over the network. If the storage device receives two such requests at about the same time, the storage device processes the request with the higher priority in its network queue. A read request processes the request and then removes the request from the network queue. A write request transfers the request from the network queue to the disk queue after the transfer is successfully completed. The priority depends on the availability of free buffers. If the time to process a request in the network queue has passed, the request is dropped, indicating that the client is no longer running or has not requested a network transfer in time.

It is also possible to schedule data transfers between the storage device and the client over the computer network to improve efficiency. That is, the scheduling of data transfer increases the bandwidth utilization of the computer network. Scheduling such network usage may be performed, especially if the bandwidth of the link between the client and the switch is as large as the bandwidth of the link between the storage device and the switch. That is, if the storage device sends the data and the client receives the data at the link speed of their respective network connections, the data is less likely to accumulate at the network switch or cause other significant delays.

A mechanism that causes each client to receive data from only one storage device and each storage device to send data to only one Ryan at any given time in order to increase the utilization of such a network. It is good to have. For example, each client may have only one token. The client sends this token to only one storage device, requesting the transfer of data to the selected segment. The token can indicate a deadline for the client to receive data, i.e. a measure of priority and a designated segment. Each storage device sends data to only one client at a time for which it received a token. The storage device receives only one token at a time. After transferring the data, the storage device also returns the token.

Other network scheduling processes are described below in connection with FIGS. 20 and 21. This process gives similar results, but does not use tokens. Rather, it specifies the segment and the amount of time E3 the client waits for a transfer to request a communication channel with the storage device. The client can also specify a new time deadline for the segment on which the client must receive the data.

The client process of transferring data over the network will now be described with reference to FIG. At any point during the reproduction of the composition, each buffer has a data segment associated with it, and a point at which data must be available in the buffer for continuous reproduction. As is known in the art, the application associates each of the buffers with a segment during the regeneration process. As shown earlier in association with FIGS. 17 and 18, each segment prepared by the client is associated with an estimated time for which data will be available in storage. Therefore, the client can order the buffers by their time limit and whether the requested data is required to be available in the buffer of the storage device. This ordering can be used by the client to select the next buffer to transfer the data in step 500. In step 502, the client requests a communication channel with the storage device and specifies a latency E3. This value E3 can be as short as 100 ms, for example, if the client does not need the data urgently, or if the client can perform other actions more efficiently. This value, E3, can be lengthened, for example, so that one of its buffers does not lose data if the client needs it urgently. At step 504, the client receives an answer from the storage device. If the storage device determines in step 506 that the request has been rejected, the revised estimated time is received with the message in step 508. In step 510, this revised estimated time can be used to update the buffer list for selecting buffers. The process returns to step 500 and selects another buffer. Buffers whose segments are on the same storage device as previously selected segments should probably not be selected. The storage device accepted the request in another way

The processing from the viewpoint of the storage device will be described below in relation to FIG. At step 520, the storage device receives a request from the client indicating the latency E3. If in step 522 it is determined that no data is yet available in the buffer of this storage device, the storage device rejects the request in step 524, calculates the estimated revision time and sends it to the client. Conversely, if it is determined in step 526 that the data is available and the storage device's network connection is not in use, then in step 528 the client becomes the "active client", the storage device grants a communication channel, and the data Transfer is possible. If the storage device's network connection is up to transfer data to other clients, the storage device will maintain the request from the "standby client" and after the data transfer to the "active client" is complete, " Transfer data to the "standby client". In order to determine if the current client is a "standby client", in step 530, the storage device multiplys the number of requests with fast deadlines in the network queue by the network transmission time for each request. Based on this, the time until the transfer can be performed is estimated. If it is determined in step 532 that the calculated available estimated time is greater than the latency E3, then the client indicates that it does not want to wait that long and rejects the request in step 524. Further, if it is determined in step 534 that the designated priority of this request is lower than the priority of any of the current standby clients, the request is rejected in step 524. Otherwise, in step 536, the request from any current waiting client is rejected and this new client is designated as the current waiting client. When the transfer to the active client is complete, the standby client becomes the active client and transfers data.

To transfer data from the client to the storage device, a similar process can be used to schedule a network transfer and transfer the data from the buffer in the storage device to the non-volatile storage. From the client's point of view, this process is described below in relation to FIG. This process can be used to perform steps 124 and 126 in FIG.

Unlike the read process, which allows a client to enter data at any point in its buffer set, the data transferred to storage is typically a read pointer from the buffer set used by the capture system. come from.

The capture system typically produces one or more video information streams and one or more audio information streams. Therefore, the capture system can select one of the data streams and receive the captured data, depending on the amount of free buffer space in the stream. The buffer at the current read pointer of this selected stream is selected in step 600. Next, in step 602, the write request is sent to the storage device. The request includes a segment identifier, a time deadline or other priority value, and a threshold E4 indicating the amount of time the client wants to wait. The time deadline is used by the storage device to prioritize network transfer requests. The Threshhold E4, like the Threshhold E3 discussed above, allows clients to efficiently schedule their own actions. After sending the request to the storage device, the client finally receives the response in step 604. If it is determined in step 606 that the request indicates that the write request has been rejected, the answer includes an estimated time before the storage device becomes available to receive the data in step 607. This estimated time can be used by the client to schedule other actions. If the storage device accepts a request to write data, in step 608 the client sends a portion of the segment of data to the storage device. In step 610, an answer indicating whether or not the write request was successful can be received in step 610. This is analyzed in step 612. In step 614, in case of failure, a restoration process may be involved. Otherwise, the process completes, as shown in step 616.

From the point of view of the storage device, the storage device receives the write request from the client in step 620. The request contains a time deadline or other priority stamp that is used to put the request into the network queue. Next, in step 622, the storage device determines whether a buffer is available to receive the data. The request may be rejected in step 624 if it is unlikely that there is no buffer available. Otherwise, in step 626, the request is queued to indicate that it has allocated a buffer to receive data, its priority stamp, and other information about the transfer. Next, in step 628, the storage device determines whether or not the network connection is in use. If the network connection is not in use, the storage device accepts the request in step 630 and sends a message to that effect to the client. The client then transfers the data, which is received by the storage device in step 632 and entered into the designated buffer. If step 634 determines that the specified buffer is currently full, then step 636 puts the buffer into the disk queue with the appropriate priority stamp. The processing of the storage disk queue eventually transfers the data from the buffer to persistent storage. Otherwise, the storage device waits until the client sends enough data to fill the buffer, as shown in step 638.

If it is determined in step 628 that the storage device's network connection is in use, the storage device calculates in step 640 the estimated time until the storage device's network connection becomes available. If this calculation time is greater than the specified latency E4 determined in step 642, then in step 643 the request is rejected by an estimate of the available time of the storage device. If the storage device can transfer data within the latency E4 indicated by the client, in step 644, the storage device compares the request priority with the request priority of any client currently waiting. To do. If the priority of this request is lower than the request of the currently waiting client, this request is rejected. Otherwise, it rejects the request from the currently waiting client, makes this new request the next request, and processes it in step 646.

An additional embodiment used when creating redundant information from two or more segments will be described in connection with FIGS. 24 and 25.

First, with reference to FIG. 24, a process example of randomly distributing data segments over several storage devices and storing data segments together with redundant information will be described in detail. This process is generally similar to the process described above in relation to Figure 3. First, in step 700, the capture system creates segment table 90B (Figure 2B). It also typically creates an image index that maps each image to an offset in the data stream it captures. The indexed image can correspond to, for example, a field or frame of video. The index can be relative to another sample boundary, such as a time period, for other types of data, such as audio. The capture system also obtains a list of available storage devices, as described above. The capture system also receives instructions for the redundant set size automatically or from the user based on the list of available storage devices. In general, the redundant set size should be less than the number of storage devices available and may be a very small subset. Counters are also used to track which segments are in a given redundancy set. This counter resets to zero in step 700. The exclusive OR memory is also used, and all are reset to binary non-assertive values, for example, "0".

Then, in step 720, a data segment is created in the capture system. The appropriate size for this segment was discussed earlier in relation to the description in Figure 3. The counter is also incremented in step 720.

In step 722, the current segment is locally stored as the exclusive OR of any segment already stored in the exclusive OR memory. At step 724, a storage device is selected for this segment. The choice of storage device for the segment is random or pseudo-random. This choice can be independent of the choices made for any previous redundant set. However, the choice must ensure that each segment in the redundant set is stored on a different storage device. As discussed earlier in the context of the discussion in Figure 3, each file can only use a subset of the available storage devices.

After selecting a storage device for the segment, this segment is sent to and stored in the storage device in step 726. Then, in step 728, the capture system waits for the storage device to approve the storage completion of the segment. If the data must be captured and stored in real time, the data transfer in step 726 may be done in two steps, similar to the read operation as discussed earlier. After successfully storing the data in storage, the capture system updates segment table 90B in step 730.

If the counter is currently determined in step 732 to be equal to the size of the redundant set, the contents of the local exclusive OR memory are redundant information. In this case, this redundant information is stored in the storage device. That is, the counter is reset in step 734. In step 736, a storage device is selected for redundant information. In step 738, the redundant information is sent to the selected storage device. Then, in step 740, the capture system waits for approval of successful storage. At step 742, the segment table can be updated.

If it is determined in step 744 that the capture is complete, the process ends. At this point, in step 745, any redundant information stored in the exclusive OR memory must be stored in the storage device using the same procedure as in steps 734 to 742. Then, in step 746, the updated segment table is sent to the catalog manager. If the counter is not equal to the size of the redundant set in step 732, or if it is determined in step 744 that the capture is not complete, the process continues, creating the next segment of data in step 720 and incrementing the counter. ..

As discussed earlier in relation to Figure 5, redundant information allows data to be restored in the event of one of the storage devices failing. FIG. 25 shows the process of performing such failure recovery when the redundancy information is based on a redundancy set containing two or more segments. The files to restore are selected in step 750 as shown in Figure 5. In step 752, identify all the lost segments of the file. Then, in step 754, the redundant set containing the lost segment is read. This step consists of reading the redundant information for the set created by the exclusive OR of the segments in the set, and then reading the remaining segments of the redundant set. Then, in step 756, the exclusive OR of the remaining segments and redundant information is calculated and the lost segments are reconstructed. Similar to step 204 of FIG. 5, then in step 758, a storage device is selected for each reconstructed lost segment. Stores the reconstructed lost segment in the selected storage device. In step 760, the segment table is updated when the store operation is completed successfully. Then, in step 762, the updated segment table is sent to the catalog manager.

It is also possible to convert a file that has one type of redundant information, eg, a copy of a segment, into another type of redundant information, eg, an exclusive OR of two or more segments. For example, the process shown in Figure 6 can be used to make additional copies of the data. After completing this process, other forms of redundant data (the result of the segment's exclusive OR) can be removed. Similarly, the process shown in FIG. 24 can also be used with the stored data to create an exclusive OR of redundant information. After creating such information, an extra copy of the data can be removed using the process shown in Figure 7. The form in which a file has redundant information may differ from file to file, and may be based on, for example, the priority associated with the file, and instructions on the form of redundant information may be stored in the catalog manager. It is possible.

By scheduling data transfers over the network, and by balancing the load on storage and choosing access to randomly distributed data segments with redundant information, the system has a large number of applications and a large number of storage. A large number of data streams can be transferred to and from the device in both directions in a highly scalable, reliable, and efficient manner. This is especially useful for distributed multimedia products.

One of the applications that can be realized using such a computer network is a function that sends and returns a large number of streams to another external digital effect system, which is commonly used in live production. These systems can be complex and costly. Most disc-based non-linear video editing systems have a disc subsystem and bus architecture that cannot simultaneously record effect return streams while maintaining a large number of playback streams and can be used in an online environment. Gender is restricted. With this system, several types of streams can be sent to the effect system, which outputs the effect data stream and stores it on a large number of storage devices. Several types of streams can be multiple camera sources, or layers of dual digital video effects.

It is also possible to have a large number of storage devices, supply data to one client, and satisfy clients who require high bandwidth data streams with higher bandwidth than any other storage device. .. For example, if each of the 20 storage devices has a 10MB / s link to the switch and the client has a 200MB / s link to the switch, the client will read 200MB / s from the 20 storage devices at the same time. This allows, for example, high definition television (HDTV) data stream transfer.

Using the procedures outlined above, the storage and client operate with local information and without central configuration management or control. Storage devices can be added to the system during operation without the need to shut down the system. The storage simply goes into operation, informs the client of its availability, and then establishes a process to respond to access requests. This extensibility complements the functionality and reliability of the system.

Although some embodiments have been described above, it will be apparent to those skilled in the art that what has been described so far is merely an example, not a limitation, and is presented as an example. Many changes and other embodiments are within the scope of those skilled in the art and shall be deemed to fall under the appended claims and their equivalents.

<figref num="1A">FIG. 1A is a block diagram of an example computer system.</figref><figref num="1B">FIG. 1B is a block diagram of another embodiment of the system of FIG. 1A.</figref><figref num="2">FIG. 2A shows a data structure that maps a data segment to the storage device 42 in FIG. 1A. FIG. 2B shows a data structure that maps the segments of the data storage device 42 in FIG. 1B.</figref><figref num="3">In one embodiment, it is a flowchart describing how to capture data and distribute it among several storage devices.</figref><figref num="4">In one embodiment, it is a flowchart describing how the storage device processes a data storage request.</figref><figref num="5">It is a flowchart describing how to perform failure recovery when a storage device becomes unavailable.</figref><figref num="6">It is a flowchart describing how an additional data copy can be made.</figref><figref num="7">It is a flowchart describing how a data copy can be deleted.</figref><figref num="8">It is a flowchart describing how a storage device can be removed from a system.</figref><figref num="9">It is a flowchart describing how data can be stored or copied as a backup.</figref><figref num="10">It is a state diagram of the process on the storage device for notifying the catalog manager of the availability of the storage device.</figref><figref num="11">Shows a list of storage devices that the catalog manager can maintain.</figref><figref num="12">It is a phase diagram showing how the catalog manager can monitor the storage device.</figref><figref num="13">Shows a table for tracking media data file equivalence.</figref><figref num="14">Shows a list structure representing a motion video sequence consisting of several clips.</figref><figref num="15">The structure of the buffer memory for the client to support the playback of two motion video data streams and four related audio data streams is shown.</figref><figref num="16">It is a flowchart describing how a client processes a multimedia composition and makes a request for data from a selected storage device.</figref><figref num="17">In one embodiment, the flow chart describes how the client requests the storage device to transfer data from the primary storage to the buffer.</figref><figref num="18">The storage device is a flowchart describing how to respond to the request from the client in FIG.</figref><figref num="19">An example of a disk queue for prioritizing disk access requests for data and a network queue for prioritizing network data transfer requests are shown.</figref><figref num="20">In one embodiment, it is a flowchart describing how a client requests a storage device to transfer data over a network.</figref><figref num="21">In one embodiment, it is a flowchart describing how the storage device processes data transfer requests from a large number of clients.</figref><figref num="22">6 is a flow chart describing an embodiment of a network scheduling process executed when a client transfers data from the client to a storage device.</figref><figref num="23">6 is a flow chart describing an embodiment of a network scheduling process executed when a storage device transfers data from a client to the storage device.</figref><figref num="24">In another embodiment, it is a flow chart describing how data can be captured and distributed among several storage devices.</figref><figref num="25">In another embodiment, it is a flow chart describing how failure recovery can be performed if the storage device becomes unavailable.</figref>