Allocating files in a file system integrated with a raid disk sub-system

• US 7,231,412 B2
• Filed: 08/08/2003
• Issued: 06/12/2007
• Est. Priority Date: 06/03/1993
• Status: Expired due to Fees

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Hitz, David, Rakitzis, Byron, Lau, James, Malcolm, Michael
• Primary Examiner(s): Vo; Tim
• Assistant Examiner(s): Dwivedi; Mahesh
• Application Number:
  US10/637,803
• Publication Number:
  US 20040064474A1
• Time in Patent Office: 1,404 Days
• Field of Search: 707/204, 707/102, 707/205, 711/100, 711/112, 711/113, 711/114
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

Integrating a file system with a RAID array that exports precise information about the arrangement of data blocks in the RAID subsystem. 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 present invention writes on the disk with the lowest CWL pointer. 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 are 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.

Claims

1. A method for storing blocks of data in a RAID array, said RAID array comprising a plurality of storage devices, the method comprising:

write allocating storage space in said RAID array for blocks of data to be stored in said RAID array by recording write allocated storage space, said storage space comprising storage blocks in said plurality of storage devices, wherein said write allocating includes;

selecting a block of data that is to be stored in said RAID array for which storage space has not yet been allocated;

determining whether said block of data is in a different file or in a different read ahead segment from a preceding block of data for which storage space in a first storage device of said plurality of storage devices in said RAID array has been write allocated;

selecting storage space in a second storage device of said plurality of storage devices in said RAID array if said block of data is in a different file or is in a different read ahead segment from said preceding block, and selecting storage space in said first storage device if said block of data is not in a different file or in a different read ahead segment from said preceding block;

assigning a write allocated storage block in said storage space to said block of data by associating an indicator of said write allocated storage block with said block of data;

adding said block of data to a list of writable blocks of data for said storage device;

determining whether all blocks of data to be stored in said RAID array have been processed, and repeating said selecting, said assigning and said adding if all of said blocks of data to be stored in said RAID array have not been processed; and

writing all unwritten blocks of data in said list of writable blocks of data to storage space allocated for said blocks of data if all of said blocks of data to be stored in said RAID array have been processed.

2. The method of claim 1 wherein said storage blocks are write allocated in a depth first, post visit traversal of said storage blocks.

3. The method of claim 1 wherein said list of blocks comprises a first plurality of blocks for one or more directories and a second plurality of blocks for one or more files.

4. The method of claim 1 wherein said storage blocks are specially formatted files.

5. The method of claim 4 wherein said storage blocks are write allocated on a least recently used basis.

6. The method of claim 1,

wherein each of a plurality of said plurality of storage devices in said RAID array has associated with it a current write location pointer referencing a next available writable block of said data storage device and wherein said selected second storage device of said plurality of storage devices in said RAID array comprises a storage device of said plurality of storage devices that has a lowest current write location pointer;

wherein said allocated storage spaces in said RAID array are recorded in a blockmap indicating storage block usage of said storage means;

wherein said write allocated storage block is allocated by marking a current block referenced by said lowest current write location pointer in said blockmap; and

wherein said write allocated storage block is allocated by scanning said blockmap for a second lowest current write location pointer, said second lowest current write location pointer referencing said write allocated storage block.

7. A system comprising:

a processor;

memory that stores instructions and data;

a RAID storage array comprising a plurality of storage devices; and

a cache;

wherein said processor executes said instructions to control said system to perform a process which comprises;

write allocating storage space in said RAID array for blocks of data to be stored in said RAID array by recording write allocated storage space in a place for recording allocated storage space, said storage space comprising storage blocks in said plurality of storage devices, said write allocating includes;

selecting a block of data that is to be stored in said RAID array for which storage space has not yet been allocated;

determining whether said block of data is in a different file or in a different read ahead segment from a preceding block of data for which storage space in a first storage device of said plurality of storage devices in said RAID array has been write allocated;

selecting storage space in a second storage device of said plurality of storage devices in said RAID array if said block of data is in a different file or is in a different read ahead segment from said preceding block and selecting storage space in said first storage device when said block of data is not in a first different file or in a different read ahead segment from said preceding block, said storage space comprising a write allocated storage block for said block of data;

assigning said write allocated storage block for said block of data to said block of data by associating an indicator of said write allocated storage block with said block of data;

adding said block of data to a list of writable blocks of data for said storage device of said plurality of storage devices in said RAID array;

determining whether all blocks of data to be stored in said RAID array have been processed, and repeating said selecting, said assigning and said adding if all of said blocks of data to be stored in said RAID array have not been processed; and

writing all unwritten blocks of data in said list of writable blocks of data to storage space allocated for said blocks of data if all of said blocks of data to be stored in said RAID array have been processed;

wherein said storage blocks are stored in said cache.

8. The system of claim 7 wherein said storage blocks are write allocated in a depth first, post visit traversal of said storage blocks.

9. The system of claim 7 wherein said list of blocks comprises a first plurality of blocks for one or more directories and a second plurality of blocks for one or more files.

10. The system of claim 7 wherein said storage blocks are specially formatted files.

11. The system of claim 10 wherein said storage blocks are write allocated on a least recently used basis.

12. The system of claim 7,

wherein each of a plurality of said plurality of storage device in said RAID array has associated with it a current write location pointer referencing a next available writable block of said data storage device and wherein said selected second storage device of said plurality of storage devices in said RAID array comprises a storage device of said plurality of storage devices that has a lowest current write location pointer;

wherein said place for recording allocated storage spaces in said RAID array comprises a blockmap for indicating storage block usage of said storage devices;

wherein said write allocated storage block is allocated by marking a current block referenced by said lowest current write location pointer in said blockmap; and

wherein said write allocated storage block is allocated by scanning said blockmap for a second lowest current write location pointer, said second lowest current write location pointer referencing said write allocated storage block.

13. A memory storing information including instructions, the instructions executable by a processor to cause the processor to perform a process of storing blocks of data in a RAID array, said RAID array comprising a plurality of storage devices, the process including:

write allocating storage space in said RAID array for blocks of data to be stored in said RAID array by recording write allocated storage space in a place for recording allocated storage space, said storage space comprising storage blocks in said plurality of storage devices, wherein said write allocating includes;

selecting a block of data that is to be stored in said RAID array for which storage space has not yet been allocated;

determining whether said block of data is in a different file or in a different read ahead segment from a preceding block of data for which storage space in a first storage device of said plurality of storage devices in said RAID array has been write allocated;

selecting storage space in a second storage device of said plurality of storage devices in said RAID array if said block of data is in a different file or is in a different read ahead segment from said preceding block, and selecting storage space in said first storage device when said block of data is not in a first different file or in a different read ahead segment from said preceding block, said storage space comprising a write allocated storage block for said block of data;

assigning said write allocated storage block for said block of data to said block of data by associating an indicator of said write allocated storage block with said block of data;

adding said block of data to a list of writable blocks of data for said storage device of said plurality of storage devices in said RAID array;

determining whether all blocks of data to be stored in said RAID array have been processed, and repeating said selecting, said assigning and said adding if all of said blocks of data to be stored in said RAID array have not been processed; and

writing all unwritten blocks of data in said list of writable blocks of data to storage space allocated for said blocks of data when all of said blocks of data to be stored in said RAID array have been processed;

wherein said storage blocks are stored in a cache.

14. The memory of claim 13 wherein said storage blocks are write allocated in a depth first, post visit traversal of said storage blocks.

15. The memory of claim 13 wherein said list of blocks comprises a first plurality of blocks for one or more directories and a second plurality of blocks for one or more files.

16. The memory of claim 13 wherein said storage blocks are specially formatted files.

17. The memory of claim 16 wherein said storage blocks are write allocated on a least recently used basis.

18. The memory of claim 13,

wherein each of a plurality of said plurality of storage device in said RAID array has associated with it a current write location pointer referencing a next available writable block of said data storage device and wherein said selected second storage device of said plurality of storage devices in said RAID array comprises a storage device of said plurality of storage devices that has a lowest current write location pointer;

wherein said place for recording allocated storage spaces in said RAID array comprises a blockmap for indicating storage block usage of said storage devices;

wherein said write allocated storage block is allocated by marking a current block referenced by said lowest current write location pointer in said blockmap; and

wherein said write allocated storage block is allocated by scanning said blockmap for a second lowest current write location pointer, said second lowest current write location pointer referencing said write allocated storage block.