Location-independent RAID group virtual block management

Patent 7111147 Issued on September 19, 2006. Estimated Expiration Date:

March 21, 2023. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

3876978

System for recovering data stored in failed memory unit
Patent #: 4092732
Issued on: 05/30/1978
Inventor: Ouchi

Plural channel error correcting methods and means using adaptive reallocation of redundant channels among groups of channels
Patent #: 4201976
Issued on: 05/06/1980
Inventor: Patel

Methods and means for simultaneously correcting several channels in error in a parallel multi channel data system using continuously modifiable syndromes and selective generation of internal channel pointers
Patent #: 4205324
Issued on: 05/27/1980
Inventor: Patel

Method and apparatus for encoding low redundancy check words from source data
Patent #: 4375100
Issued on: 02/22/1983
Inventor: Tsuji , et al.

Virtual storage system and method
Patent #: 4467421
Issued on: 08/21/1984
Inventor: White

Method of rewriting data in non-volatile memory, and system therefor
Patent #: 4517663
Issued on: 05/14/1985
Inventor: Imazeki , et al.

Method and apparatus for error detection and correction in systems comprising floppy and/or hard disk drives
Patent #: 4667326
Issued on: 05/19/1987
Inventor: Young , et al.

Error recovery method and apparatus
Patent #: 4688221
Issued on: 08/18/1987
Inventor: Nakamura , et al.

High capacity disk storage system having unusually high fault tolerance level and bandpass
Patent #: 4722085
Issued on: 01/26/1988
Inventor: Flora , et al.

More ...

Inventors

Assignee

Network Appliance, Inc.

Application

No. 10394890 filed on 03/21/2003

US Classes:

711/209, Including plural logical address spaces, pages, segments, blocks711/114, Arrayed (e.g., RAIDs)711/202, Address mapping (e.g., conversion, translation)714/6, Redundant stored data accessed (e.g., duplicated data, error correction coded data, or other parity-type data)714/5, Of memory or peripheral subsystem707/200, FILE OR DATABASE MAINTENANCE711/206Translation tables (e.g., segment and page table or map)

Examiners

Primary: Portka, Gary

Attorney, Agent or Firm

Cesari and McKenna, LLP

International Classes

G06F 11/07
G06F 12/16
G06F 12/08

Abstract

A technique maps the capacity of storage devices, such as disks, into any RAID group of a volume of a storage system regardless of the location of the RAID group within a volume block number (VBN) space of the volume. The technique separates disks and mapped VBN ranges, allowing for flexibility in the description and extension of RAID group capacities, while providing disk addition policies that support location-independent disk insertion into RAID groups. The technique also provides a disk label structure that supports the provision of multiple VBN ranges within a RAID group and within individual disks. Moreover, the technique provides file system support for allocation and topology management of the multiple mapped VBN ranges within disks and RAID groups, as well as noncontiguous VBN ranges across the RAID groups in the volume.

Other References

David Hitz et al. TR3002 File System Design for a NPS File Server Appliance published by Network Appliance, Inc.
Common Internet File System (CIFS) Version: CIFS-Spec 0.9, Storage Networking Industry Association (SNIA), Draft SNIA CIFS Documentation Work Group Work-in-Progress, Revision Date: Mar. 26, 2001.
Fielding et al. (1999) Request for Comments (RFC) 2616, HTTP/1.1.
Anvin, Peter H, “The Mathematics of RAID 6,” Dec. 2004.
Auspex 4Front NS2000, System Architecture, Network-Attached Storage For a New Millennium, Auspex Engineering Technical Report 24, Jan. 1999.
Bestavros, Azer, et al., Reliability and Performance of Parallel Disks, Technical Memorandum 45312-891206-01TM, AT&T, Bell Laboratories, Department 45312, Holmdel, NJ, Dec. 1989.
Bitton, Dina, Disk Shadowing, Proceedings of the 14^thVLDB Conference, LA, CA (1988).
Bultman, David L., High Performance SCSI Using Parallel Drive Technology, In Proc. Buscon Conf., pp. 40-44, Anaheim, CA, Feb. 1988.
Chen, Peter et al., Two Papers on RAIDs. Technical Report, CSD-88-479, Computer Science Division, Electrical Engineering and Computer Sciences, University of California at Berkeley (1988).
Chen, Peter M., et al., An Evaluation of Redundant Arrays of Disks Using an Amdahl 5890, Performance Evaluation, pp. 74-85, 1990—check to see if exact same copy as one in WAFL.
Chen, Peter M.., et al, Maximizing Performance in a Striped Disk Array, Proc. 1990 ACM SIGARCH 17th Intern. Symp. on Comp. Arch., Seattle, WA, May 1990, pp. 322-331.
Chen, Peter M., et al., RAID:High Performance, Reliable Secondary Storage, ACM Computing Surveys, 26(2):145-185, Jun. 1994.
Chervenak, Ann L., Performance Measurement of the First RAID Prototype, Technical Report UCB/CSD 90/574, Computer Science Division (EESC), University of California, Berkeley, May 1990.
Copeland, George, et al., “A Comparison of High-Availability Media Recovery techniques,” in Proc. ACM-SIGMOD Int. Conf. Management of Data, 1989.
Courtright II, William V., et al., RAIDframe: A Rapid Prototyping Tool for RAID Systems, Computer Science Technical Report CMU-CS97-142, Carnegie Mellon University, Pittsburgh, PA 15213, Jun. 4, 1997.
Evans The Tip of the Iceberg:RAMAC Virtual Array—Part 1, Technical Support, Mar. 1997, pp. 1-4.
Gibson, Garth A., et al., Coding Techniques for Handling Failures in Large Disk Arrays, Technical Report UCB/CSD 88/477, Computer Science Division, University of California, (Jul. 1988.).
Gibson, Garth A., et al., Failure Correction Techniques for Large Disk Arrays, In Proceedings Architectural Support for Programming Languages and Operating Systems, Boston, Apr. 1989, pp. 123-132.
Gibson, Garth A., et al., Strategic Directions in Storage I/O Issues in Large-Scale Computing, ACM Computing Survey, 28(4):779-93, Dec. 1996.
Goldick, Jonathan S., et al., Multi-resident AFS: An Adventure in Mass Storage, In Proceedings of the 1995 USENIX Technical Conference, pp. 47-58, Jan. 1995.
Graham, Susan L., et al., Massive Information Storage, Management, and Use, (NSF Institutional Infrastructure Proposal), Technical Report No. UCB/CSD 89/493, Jan. 1989.
Gray, Jim et al., Parity striping of disc arrays: Low-Cost Reliable Storage with Acceptable Throughput. In Proceedings of the 16th Very Large Data Bases Conference, pp. 148-161, Brisbane, Australia, 1990.
Grimes, DW Martinez, Two Dimensional Parity Error Correction Procedure, IBM Technical Disclosure Bulletin 2686-2689, Oct. 1982.
Grimes, DW Martinez, Vertical Parity Generator for Two Dimensional Parity, IBM Technical Disclosure Bulletin 2682-2685, Oct. 1982.
Hellerstein, Lisa, et al,. Coding Techniques for Handling Failures in Large Disk Arrays. In Algorithmica vol. 2, No. 3, 182-208 (1994).
Hughes, James, et al., High Performance RAIT, Tenth NASA Goddard Conference on Mass Storage Systems and Technologies and Nineteenth IEEE Symposium on Mass Storage Systems, Adelphi, Maryland, USA, Apr. 2002.
Johnson, Theodore, et al, Tape Group Parity Protection, IEEE Symposium on Mass Storage, pp. 72-79, Mar. 1999.
Katz, Randy H. et al., Disk System Architectures for High Performance Computing, undated.
Kent, Jack et al., Optimizing Shadow Recovery Algorithms, IEEE Transactions on Software Engineering, 14(2):155-168, Feb. 1988.
Kim, Michelle Y., Synchronized Disk Interleaving, IEEE Transactions on Computers, C-35(11):978-988, Nov. 1986.
Kim, Michelle, et al., Asynchronous Disk Interleaving Approximating Access Delays, IEEE Transactions on Computers, vol. 40, No. 7, Jul. 1991, pp. 801-810.
Lawlor, F. D., Efficient Mass Storage Parity Recovery Mechanism, IBM Technical Disclosure Bulletin 24(2):986-987, Jul. 1981.
Lee, Edward K., et al., RAID-II: A Scalable Storage Architecture for High-Bandwidth Network File Service, Technical Report UCB/CSD 92/672, (Feb. 1992).
Li, Don, et al., Authors' Reply, IEEE Transactions on Communications, 46:575, May 1998.
Livny, Miron, et al., Multi-Disk Management Algorithms, In Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), pp. 69-77, Banff, Alberta, Canada, May 1987.
Meador, Wes E., Disk Array Systems, Proceedings of COMPCON, 1989, pp. 143-146.
Ng, Spencer, et al., Trade-Offs Between Devices and Paths in Achieving Disk Interleaving, IEEE International Symposium on Computer Architecture, 1988, pp. 196-201.
Ng, Spencer, Some Design Issues of Disk Arrays, Proceedings of COMPCON Spring '89, pp. 137-142. IEEE, 1989.
Park, Arvin, et al., Providing Fault Tolerance In Parallel Secondary Storage Systems, Technical Report CS-TR-057-86, Princeton, Nov. 1986.
Patel, Arvind M., Adaptive Cross-Parity (AXP) Code for a High-Density Magnetic Tape Subsystem, IBM Technical Disclosure Bulletin 29(6):546-562, Nov. 1985.
Patterson, D., et al., A Case for Redundant Arrays of Inexpensive Disks (RAID), Technical Report, CSD-87-391, Computer Science Division, Electrical Engineering and Computer Sciences, University of California at Berkeley (1987).
Patterson, D., et al., A Case for Redundant Arrays of Inexpensive Disks (RAID), SIGMOD International Conference on Management of Data, Chicago, IL, USA, Jun. 1-3, 1988, SIGMOD Record (17)3:109-16 (Sep. 1988).
Patterson, David A., et al., Introduction to Redundant Arrays of Inexpensive Disks (RAID). In IEEE Spring 89 COMPCON, San Francisco, IEEE Computer Society Press, Feb. 27-Mar. 3, 1989, pp. 112-117.
STORAGESUITE “Performance Without Compromise: The Virtual Storage Architecuture,”catalogue, 1997.
Reddy, A. L. Narasimha, et al., An Evaluation of Multiple-Disk I/O Systems, IEEE Transactions on Computers, vol. 38, No. 12, Dec. 1989, pp. 1680-1690.
Schulze, Martin E., Considerations in the Design of a RAID Prototype, Computer Science Division, Department of Electrical Engineering and Computer Sciences, Univ. of CA, Berkley, Aug. 25, 1988.
Schulze, Martin., et al., How Reliable is a RAID?, Proceedings of COMPCON, 1989, pp. 118-123.
Shirriff, Kenneth W., Sawmill: A Logging File System for a High-Performance RAID Disk Array, CSD-95-862, Jan. 1995.
Stonebraker, Michael, et al., The Design of XPRS, Proceedings of the 14^thVLDB Conference, LA, CA (1988).
Tanabe, Takaya, et al, Redundant Optical Storage System Using DVD-RAM Library, IEEE Symposium on Mass Storage, pp. 80-87, Mar. 1999.
TEKROM—“About RAID 6”.
Tweten, David, Hiding Mass Storage Under UNLX: NASA's MSS-H Architecture, IEEE Symposium on Mass Storage, pp. 140-145, May 1990.
Wilkes, John, et al., The HP AutoRAID hierarchical storage system, ACM Transactions on Computer Systems, Feb. 1996, vol. 14, pp. 108-136.