Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1998-06-30
2001-08-14
Bragdon, Reginald G. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S158000, C709S213000
Reexamination Certificate
active
06275912
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to computer programming and systems, and more particularly to an automated method and computer apparatus for efficiently consolidating and storing data items to a storage device.
BACKGROUND OF THE INVENTION
Users of computers are demanding increased reliability and performance of their applications running on their computers. One bottleneck in a computer system is the rate at which hardware devices operate, including the rate at which an application program can store its data to them.
Alternatively, an application program could store its data in the random access memory (RAM) of the computer which typically provides access at a rate several orders of magnitude faster than that of a data file on a hard disk drive. However, RAM does not provide the data persistence and reliability of hardware devices in the advent of computer or application problems. Should an application or the computer crash, this data store in RAM is typically lost which is unacceptable to many applications. Thus, computer users and developers are desirous of more efficient and faster methods for storing their information to these hardware devices.
In attempting to provide both faster access and data persistence and reliability, memory-mapped files have been developed. Memory-mapped files provide a way for an application program to access data at rates approximating accessing RAM, while providing reliability as the data is also stored on a file on a hardware device (usually a hard disk drive). Memory-mapped files accomplish this by maintaining a file and its mirror image in RAM and on a hardware device. Once a file has been mapped by an application program into its virtual address space, the application can access it using memory pointers. Any modifications to the data in memory are updated to the hardware device using the operating system paging and caching mechanisms. Current techniques are inefficient, and users are desirous of increased speed and data integrity of these techniques.
Traditional data paging and caching methods operate by updating entire pages of memory when a single data element within the page has been modified (i.e., the page has become “dirty”). For example, Windows NT uses a lazy method of flushing the memory to the disk and writes entire pages at a time, rather than only the individually changed elements.
In other computing applications that update individual elements within a random access file, the storage of the data items to disk operates in a linear fashion. In this approach, a first data element is updated on disk, then a second data element, and so on. While this approach is simplistic, this method does not optimize the writing of these data elements to disk. In fact, the processing overhead is so high that the linear data writing approach does not allow data to be written at the fastest rate allowed by the hardware. Rather, the data logging rate is limited by software processing of individual write operations. A solution is needed for writing and reading of a large amount of data elements at random locations on a hardware device or within a file on a hardware device at high rates of speed which approach the physical limitations of the hardware device to which the data is being stored.
SUMMARY OF THE INVENTION
According to the invention, an automated method and computer apparatus are disclosed for efficiently writing data items to a hardware device. To increase the performance of writing to random portions of a hardware device (e.g., a disk drive) or within one or more files on the hardware device, an optimal data storage method is used to efficiently accumulate, consolidate and write data elements to the hardware device at a rate which approximates the maximum rate that the hardware device can support, which cannot be achieved using traditional data writing methods. In one embodiment, the present invention is used to maintain the hardware device image of a memory-mapped file by efficiently writing the modified data items to the storage device. In one configuration, these data items correspond to messages in a message queuing environment.
To overcome the processing limitations of the traditional methods, the performance of a write operation is divided between a data collector and a data writer which operate in different threads. These threads can either be within the same process or in different processes. The data writer manages the writing of the data elements to the hardware device, while the data collector accumulates, orders and consolidates the data items for efficient storage by the data writer. The data collector can either be part of an application program, or within a separate thread as part of a device driver.
Any data items to be written to disk are passed to the data collector from a data source (e.g., an application program, device driver, some other thread or process, or the like). Because the data storage rate of the hardware device is relatively slow compared to a write to RAM especially when random portions of a hardware device are accessed, the present invention employs a method to keep the data writer storing data to the disk. Moreover, because writing larger blocks of contiguous data items is more efficient than a plurality of write operations on individual contiguous data items, the data collector consolidates accumulated multiple write requests for contiguous data items into a single write request. In another embodiment, the consolidation of write requests is performed by the data writer.
Whenever the data writer has no more data items to store to the hardware device and the data collector has one or more items, the data writer acquires these one or more items and proceeds with storing them to the hardware device. While the data writer is busy, the data collector receives new write requests from the data source, and accumulates, consolidates and orders them for efficient storing to the hardware device. In this manner, the present invention efficiently stores a stream of write requests received by the data collector to the hardware device by adjusting to the storage locations of the accumulated data items, the CPU speed, and the storage rate of the hardware device. In one embodiment in a particular Windows NT configuration, a twenty fold increase in writing the stream of data items (a rate of 1500 per second) was realized using the present invention over storage operations for individual data items (a rate of 70 per second). In addition, gains of twenty-five to forty times have been achieved using the present invention when storing a large stream of data items to a hardware device.
These write requests typically include the location to store the data item and the value of the data item. Alternatively, in a manner more efficient for use with memory-mapped files, the write request includes the memory address of the data item and the length of the data item.
In one embodiment, the data collector receives and maintains the write requests in a data structure in sorted order by storage location (or memory address). This allows the data collector to readily determine when two data items are contiguous. The data collector consolidates these write requests for contiguous data items into a single write request with a larger data item.
Whenever the data writer has no more write requests, the data writer acquires the write requests stored in the data structure in the data collector. In one embodiment, the data collector locks the data collector's data structure, copies the write requests to its own data structure, and then resets and releases the data collector's data structure. Many other techniques and semaphores could be used in keeping within the scope and spirit of the invention for passing the data between the data collector and the data writer. For example, multiple data structures could be used where the data writer is passed a pointer to a non-empty data structure and the data collector is passed a pointer to an empty data structure to fill. Also, object-oriented techniques could be employed such as main
Anderson Matthew G.
Bragdon Reginald G.
Leydig Voit & Mayer Ltd
Microsoft Corporation
LandOfFree
Method and system for storing data items to a storage device 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 system for storing data items to a storage device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for storing data items to a storage device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2496600