Electrical computers and digital processing systems: multicomput – Computer-to-computer direct memory accessing
Reexamination Certificate
1999-04-05
2001-03-27
Lim, Krisna (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer-to-computer direct memory accessing
C711S100000, C711S112000, C711S114000
Reexamination Certificate
active
06209024
ABSTRACT:
BACKGROUND OF THE DISCLOSURE
1. Field of the Invention
The invention relates to a system for storing and accessing electronic data. More particularly, the invention relates to a method and apparatus for enabling multiple users to independently access previously stored streams of electronic data from an array of data storage devices.
2. Description of the Prior Art
In traditional electronic data storage and retrieval systems, the data is stored in a bank or array of memory elements controlled by a central processing unit (CPU). Such data storage systems form the basis of most contemporary computer systems. Typically, the memory elements are a combination of semiconductor memory, such as dynamic random access memory (DRAM) or static random access memory (SRAM), and rotating disk magnetic memory (disk drive memory), such as a “Winchester” hard disk drive. The semiconductor memory is used for storage of data that requires immediate access by the CPU, while the disk drive memory is typically used for storing data that is less frequently accessed by the CPU.
In a multimedia server that uses an array of disk drives for bulk storage of information, there are many variables that must be optimized to achieve an optimal transfer of information from the server to a plurality of independent clients (users) of the server. First, an optimal number of individual disk drives in the array must be chosen to support the maximum expected number of users. Since the cost associated with disk drives is a substantial portion of the total cost of the server, it is critical that the number of disk drives be minimized without substantially impacting performance.
To ensure that the data is continuously transferred from the system to the users, a relatively large capacity semiconductor memory is utilized to buffer the parallel output data streams from the disk drives. Such data buffering is especially necessary when the data is video or audio data that can not be interrupted during transfer to the users for viewing or processing. In such systems, the video and audio data is transferred from the disk drives to the buffer memory as distinct blocks of data. The blocks are serially arranged in the buffer memory such that as the buffer memory is read, the blocks form a contiguous data stream for each user. The substantial cost of semiconductor memory requires that the amount of memory be minimized without impacting the performance of the server.
For example, in a multimedia information storage system, the buffer memory must be very large and, as such, very costly. For example, in a round-robin type access system having M users, buffer memory must temporarily store a given user's data while the other M-1 users are serviced by the server. In a typical video storage system, where 500 kbyte blocks of data is simultaneously read from multiple disk drives for 1000 clients, the buffer memory must be approximately 1-3 Gbytes. Such a large capacity semiconductor memory array is extremely costly.
Another variable that must be optimized is latency, i.e., the delay between when a user requests information and when the server is capable of beginning the information transfer to the user. When the server is used as a video-on-demand server, it is important to minimize latency such that the system users do not experience undo delay when video playback control requests are sent to the server. For example, an excessive delay when a user requests that the system change from a play function to a fast forward or rewind function would be unacceptable. As such, it is important to minimize latency by rapidly executing requests as soon as they are received by the server.
Lastly, the resolution into a file (i.e., file access granularity) needs to be maximized. For example, if a user requests output data starting at a certain position in a file, but the server is able only to deliver data starting at a nearby file position g bytes away from the requested position. As such, the server's minimum guaranteed file resolution is at least g bytes. It is, of course, desirable to maximize the server's file resolution (i.e., to minimize g).
These variables (resolution, latency, buffer memory requirements, continuous data transmission requirements, and the like) can be addressed by altering the extent size used to store and access data. An extent is the amount of data that is read from a disk drive during each disk access. However, a trade-off must be addressed when extent size is increased or decreased, i.e., lengthening the extent size detrimentally impacts the latency and resolution.
Therefore, a need exists in the art for a multiple user data distribution system that balances the foregoing variables (i.e., balances the trade off between longer extent sizes and reasonable latency and resolution) to provide an improved method and apparatus for storing and accessing information in a data storage array.
SUMMARY OF THE INVENTION
The present invention advantageously overcomes the disadvantages heretofore associated with the prior art by utilizing a method and apparatus for optimally accessing an array of storage devices and optimally transmitting the data to the users. The array of storage devices is divided into parity groups of devices (e.g., G devices) such that blocks of data are stored on G-1 devices and the parity data is stored on the other device. In this manner, during a first service period, data is recalled from the entire parity group, checked for errors, corrected if necessary, and stored in a buffer. During the next service period, the buffered data from the group of devices is then supplied to the user in sequential order to ensure a continuous stream of data.
More specifically, the invention analyzes each data request from a user to identify an optimal storage device from which data should be retrieved to fulfill a user's request. If the optimal storage device can be accessed in the present service period, the data from the optimal device is retrieved and buffered. When data is retrieved, data from an entire parity group of storage devices is retrieved such that the data can be checked for errors and, if errors are found, the data can be corrected using the parity data. The corrected data is stored in the buffer. During the next service period, the data from the buffer is transmitted to the user.
REFERENCES:
patent: 5414455 (1995-05-01), Hopper et al.
patent: 5465343 (1995-11-01), Henson et al.
patent: 5915094 (1999-06-01), Kouloheris et al.
patent: 5974441 (1999-10-01), Rogers et al.
Armstrong James B.
Dandrea Robert G.
DIVA Systems Corporation
Lim Krisna
Thomason, Moser and Patterson
LandOfFree
Method and apparatus for accessing an array of data storage... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for accessing an array of data storage..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for accessing an array of data storage... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2452742