Data processing: database and file management or data structures – Database design – Data structure types
Patent
1995-05-31
2000-03-14
Ho, Ruay Lian
Data processing: database and file management or data structures
Database design
Data structure types
364200, G06F 1730
Patent
active
060385707
ABSTRACT:
The present invention is a method for integrating a file system with a RAID array that exports precise information about the arrangement of data blocks in the RAID subsystem. The file system examines this information and uses it to optimize the location of blocks as they are written to the RAID system. Thus, the system uses explicit knowledge of the underlying RAID disk layout to schedule disk allocation. The present invention uses separate current-write location (CWL) pointers for each disk in the disk array where the pointers simply advance through the disks as writes occur. The algorithm used has two primary goals. The first goal is to keep the CWL pointers as close together as possible, thereby improving RAID efficiency by writing to multiple blocks in the stripe simultaneously. The second goal is to allocate adjacent blocks in a file on the same disk, thereby improving read back performance. The present invention satisfies the first goal by always writing on the disk with the lowest CWL pointer. For the second goal, a new disk is chosen only when the algorithm starts allocating space for a new file, or when it has allocated N blocks on the same disk for a single file. A sufficient number of blocks is defined as all the buffers in a chunk of N sequential buffers in a file. The result is that CWL pointers are never more than N blocks apart on different disks, and large files have N consecutive blocks on the same disk.
REFERENCES:
patent: 4075691 (1978-02-01), Davis et al.
patent: 4156907 (1979-05-01), Rawlings et al.
patent: 4333144 (1982-06-01), Whiteside et al.
patent: 4377843 (1983-03-01), Garringer et al.
patent: 4399503 (1983-08-01), Hawley
patent: 4456957 (1984-06-01), Schieltz
patent: 4459664 (1984-07-01), Pottier et al.
patent: 4488231 (1984-12-01), Burlington et al.
patent: 4527232 (1985-07-01), Bechtolsheim
patent: 4550368 (1985-10-01), Bechtolsheim
patent: 4685125 (1987-08-01), Zave
patent: 4710868 (1987-12-01), Cocke et al.
patent: 4719569 (1988-01-01), Ludemann et al.
patent: 4742447 (1988-05-01), Duvall et al.
patent: 4761785 (1988-08-01), Clark et al.
patent: 4766534 (1988-08-01), DeBenedictis
patent: 4780821 (1988-10-01), Crossley
patent: 4783730 (1988-11-01), Fischer
patent: 4803621 (1989-02-01), Kelly
patent: 4819159 (1989-04-01), Shipley et al.
patent: 4825354 (1989-04-01), Agrawal et al.
patent: 4875159 (1989-10-01), Cary et al.
patent: 4887204 (1989-12-01), Johnson et al.
patent: 4897781 (1990-01-01), Chang et al.
patent: 4914583 (1990-04-01), Weisshaar et al.
patent: 5134619 (1992-07-01), Henson et al.
patent: 5155835 (1992-10-01), Belsan
patent: 5163131 (1992-11-01), Row et al.
patent: 5195100 (1993-03-01), Katz et al.
patent: 5218695 (1993-06-01), Noveck et al.
patent: 5218696 (1993-06-01), Baird et al.
patent: 5235601 (1993-08-01), Stallmo et al.
patent: 5255270 (1993-10-01), Yanai et al.
patent: 5274799 (1993-12-01), Brant et al.
patent: 5274807 (1993-12-01), Hoshen et al.
patent: 5276840 (1994-01-01), Yu
patent: 5276867 (1994-01-01), Kenley et al.
patent: 5305326 (1994-04-01), Solomon et al.
patent: 5313626 (1994-05-01), Jones et al.
patent: 5315602 (1994-05-01), Noya et al.
patent: 5355453 (1994-10-01), Row et al.
patent: 5357509 (1994-10-01), Ohizumi
patent: 5379417 (1995-01-01), Lui et al.
B. Srinivasan, et al.: "Recoverable file system for microprocessor systems" Micropocessors and Microsystems, vol. 9, No. 4, May 1985, London, GB, pp. 179-183, XP002031805.
IBM Technical Dislosure Bulletin, vol. 36, No. 03, Mar. 1993, "Parity Preservation for Redundant Array of Independent Direct Access Storage Device Data Loss Minimization and Repair".
Tan, et al., "SOS--Stan's Own Server: A NFS File SErver for the IBM PC," Computer Science Research Department, Information and Computing Sciences Division, Lawrence Berkeley Laboratory, Aug. 17, 1988.
Sandberg, "The Sun Network File System: Design, Implementation and Experience," Sun Microsystems, Inc., Technical Report, 1986.
Hitz, "A System Administrator's Performance Monitor for Tuning NFS Network Servers," Auspex Systems, Inc. Technical Report 7, May 1991.
Nelson, Benchmark Methodology and Preliminary Performance Specifications for the Auspect NS5000 Network Server, Auspex Systems, Inc. Technical Report 2, Oct. 1989.
Nelson, et al., "How and Why SCSI is Better than IPI for NFS,"Auspex Systems, Inc. Technical Report 6, 2nd edition, Jul. 1992.
Schroder, "PEACE: The Distributed SUPRENUM Operating System," Parallel Computing, vol. 7 (1988), pp. 325-333.
Malcolm, "A Process Abstraction and its Application," Proc. Eighth Manitoba Conference on Numerical Math. and Computing, University of Manitoba at Winnipeg, 1978, pp. 33-50.
Nelson, et al., "The Myth of MIPS for I/O: An Overview of Functional Multiprocessing for NFS Network Servers," Auspex Systems, Inc. Technical Report 1, 6th edition, 2nd printing, Aug. 1992.
Cheriton, et al., "Thoth, a Portable, Real-Time Operating System," Communications of the ACM, Feb. 1979, vol. 22, No. 2, pp. 105-115.
Cheriton, "Multi-Process Structuring and the Thoth Operating System," Ph.D. thesis submitted to Department of Computer Science, University of British Columbia at Vancouver, 1979.
Sun Microsystems, Inc., Sun OS 5.0 Network Interfaces Programmer's Guide, p. 108, Jun. 1992.
Chutani, Sailesh, et al., "The Episode File System", USENIX Winter Conference, Jan. 30-24, 1992.
Sun Microsystems, "Network Programming Guide", Chapter 4, "Remote Procedure Call Programming Guide", Revision A of Mar. 27, 1990, pp. 65-128.
Bach, The Design of the Unix Operating System, Prentice-Hall, 1986, pp. 38-90 and 325-329.
Beach, Richard J., et al., The Message is the Medium: Multiprocess Structuring of an Interactive Paint Program. Computer Graphics, vol. 16, No. 3, Jul. 1982, pp. 277-287.
Britton, Dianne E., et al., An Interprocess Communication Facility for Distributed Applications, RCA Laboratiroes, David Sarnoff Research Centr, Princeton, NJ .COPYRGT. 1980 IEEE.
Carr, Robert, et al., The Power of PenPoint, Ch 5: The Class Manager, .COPYRGT. 1991 Addison Wesley.
Cashin, Inter Process Communication, Bell-Northern Research, Document No. 8005014, 1980.
Chao, Chia, et al., Mime: a high performance storage device with strong recovery quarantees, Hewlett-Packard Company, Mar. 18, 1992.
Cheriton, David R. The Thoth System: Multiprocess Structuring and Portability, Ch 2: Thoth Program Environment, and Ch 3: Thoth Kernel Design, .COPYRGT. 1982 North-Holland.
Cohen, Jacques, Garbarge Collection of Linked Data Structures, Department of Physics, Brandeis University, Waltham, MA Computing Surveys, vol. 13, No. 3, Sep. 1981, .COPYRGT. 1981.
Deitel, An Introduction to Operating Systems, Addison Wesley, 1984, pp. 302-334.
de Jonge, Wiebren, et al., The Logical Disk: A New Approach to Improving File Systems.
English, Robert M. et al., Loge: A Self-Organizing Disk Controller, Software and Systems Laboratory, .COPYRGT. 1991 Hewlett Packard.
File Systems, Chapter 5, pp. 251-273.
Hammond, Richard A. Experiences with the Series/1 Distributed System, Department of Electrical Engineering, U of Delaware, Newark, Delaware, .COPYRGT. 1980 IEEE.
Hanson, Per Brinch (editor), brochure: RC 400 Software Multiprogramming System, Ch 4: Process Communication, A/s Regnecentralen, Copenhagen--Apr. 1969.
Hartman, John H., et al., The Zebra Striped Network File System. .
Hitz, David, Technical Report TR01: An NFS File Server Appliance, Network Appliance Corporation.
Hitz, Dave et al., Technical Report 3002: File System Design for an NFS File Server Appliance, Network Appliance, Jan. 19, 1994.
Hitz, David, et al., Using Unix as One Component of a Lightweight Distributed Kernel for Multiporcessor File Servers, Auspex Technical Report 5, .COPYRGT. 1990 Auspex Systems Inc.
Jones, Anita K., et al., StarOS, a Multiprocessor Operating System for the Support of Task Forces, Association for Computing Machinery, 1979, pp. 117-127.
Lantz, Keith A., et al., Rochester's Intelligent Gateway, Computer .COPYRGT. 1982 IEEE.
Leffler, et al., The Design and Implementation of the 4.3BSD UNIX Operating System, Addison-Wesley, 1989, pp. 187-245.
Ousterhout,
Hitz David
Lau James
Malcolm Michael
Rakitzis Byron
Ho Ruay Lian
Network Appliance Inc.
LandOfFree
Method for allocating files in a file system integrated with a R 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 for allocating files in a file system integrated with a R, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for allocating files in a file system integrated with a R will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-179094