Method for allocating files in a file system integrated with a RAID disk sub-system

• US 6,038,570 A
• Filed: 05/31/1995
• Issued: 03/14/2000
• Est. Priority Date: 06/03/1993
• Status: Expired due to Term

• 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): HO, RUAY L
• Application Number:
  US08/464,591
• Time in Patent Office: 1,749 Days
• Field of Search: 395/600, 395/700, 395/800, 395/250, 395/425, 395/182.01, 395/182.05, 395/182.06, 364/200, 364/300, 707/1-10, 707/100-104, 707/200-206, 711/112, 711/113, 711/114, 711/156, 711/162, 711/168, 711/170, 371/10.2, 371/20.1
• 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 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• 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/0643 Management of files
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: Y10S 707/99955 Archiving or backup

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.

Claims

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

write allocating storage space in said RAID array for blocks of data to be stored in said RAID array by recording said write allocated storage space in a means for recording allocated storage space, said storage space comprising storage blocks in said plurality of storage means, said write allocation of said storage space in said RAID array comprising the steps of;

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

checking said block of data to determine if 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 means of said plurality of storage means in said RAID array has been write allocated;

selecting storage space in a second storage means of said plurality of storage means in said RAID array when said block of data is in said different file or is in said different read-ahead segment and selecting storage space in said first storage means when said block of data is not in said different file or in said different read-ahead segment, 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 means of said plurality of storage means in said RAID array;

determining if all blocks of data to be stored in said RAID array have been processed, repeating said steps of selecting a block of data for which storage space has not yet been allocated and selecting storage space for said block of data when all of said blocks of data to be stored in said RAID array have not been processed;

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 said blocks of data to be stored in said RAID array have been processed.

2. The method of claim 1 wherein each of a plurality of said plurality of storage means in said RAID array has associated with it a current write location pointer referencing a next available writable block of said data storage means and wherein said selected second storage means of said plurality of storage means in said RAID array comprises a storage means of said plurality of storage means that has a lowest current write location pointer.

3. The method of claim 2 wherein said means for recording allocated storage spaces in said RAID array comprises a blockmap for indicating storage block usage of said storage means and wherein said write allocated storage block is allocated by marking a current block referenced by said lowest current write location pointer in said blockmap.

4. The method of claim 3 wherein blocks of data in said list of writable blocks of data are written to one or more stripes of said RAID array when one or more of said blocks of data have been assigned one or more write allocated storage blocks having a location number that is less than a location number of a block referenced by said lowest current write location pointer.

5. The method of claim 1 wherein said means for recording allocated storage spaces in said RAID array comprises a blockmap for indicating storage block usage of said storage means.

6. A method for allocating storage space for files of a file system in a RAID array comprising N data storage means and parity storage means, each of said data storage means comprising a current write location (CWL) pointer referencing a next available writable block of said data storage means, comprising the steps of:

selecting an in-core inode referencing one or more dirty buffers from a plurality of inodes referencing dirty buffers;

write allocating storage space comprising one or more storage blocks of one or more of said data storage means of said RAID array for data in said one or more dirty buffers referenced by said inode by visiting said one or more dirty buffers in sequential order, said step of write allocating said storage space comprising the steps of;

checking said one or more dirty buffers to determine if each dirty buffer of said one or more dirty buffers contains data in a different file or in a different read-ahead segment from a preceding dirty buffer for which storage space in a first data storage means of said N data storage means of said RAID array has been write allocated;

selecting as a current data storage means a second data storage means of said N data storage means of said RAID array having a lowest CWL pointer when data in said buffer is in said different file or in said different read-ahead segment;

otherwise retaining said first data storage means as a current data storage means;

updating a blockmap of said file system to free any block of any data storage means previously assigned to said dirty buffer;

assigning a next available writable block referenced by said CWL pointer of said current data storage means to said dirty buffer;

adding said dirty buffer to a buffer queue assigned to said current data storage means of N buffer queues assigned to said N data storage means of said RAID array;

writing data in buffers in said buffer queues to one or more stripes of said RAID array when a plurality of dirty buffers stored in said N buffer queues reference one or more write allocated blocks of a stripe below said lowest CWL pointer;

determining if all inodes in said list of inodes have been processed, repeating said steps of selecting an in-core inode and write allocating storage space for said one or more dirty buffers referenced by said inode when all of said inodes in said list of inodes have not been processed;

(D) writing to one or more stripes of said RAID array data in all unwritten buffers for which storage space has been write allocated in said RAID array.

7. The method of claim 6 wherein said list of inodes comprises a first plurality of inodes for one or more directories and a second plurality of inodes for one or more files.

8. The method of claim 7 wherein each directory of said one or more directories is a specially formatted file.

9. The method of claim 7 wherein said first plurality of inodes for one or more directories are selected for write allocation before said second plurality of inodes for one or more files.

10. The method of claim 9 wherein each inode of said second plurality of inodes is write allocated on a least recently used basis.

11. A method for integrating a file system having a plurality of files at least one of which has at least one data block, with a storage system comprising a plurality of storage devices having a plurality of storage blocks, said method comprising the steps of

providing said file system with current configuration information of said storage system, said current configuration information comprising information regarding which ones of said data blocks are allocated to which ones of said storage devices;

writing, responsive to said information, a sequence of said data blocks from said files to selected said storage blocks of selected said storage devices.

12. The method of claim 11 wherein said storage system comprises a RAID storage system.

13. The method of claim 12 wherein a plurality of said data blocks of said sequence of data blocks are stored in a plurality of buffers prior to being written to said selected storage blocks of said selected storage devices and wherein said data blocks stored in said plurality of buffers are written to stripes of said RAID storage system.

14. The method of claim 13 wherein writing of said blocks stored in said plurality of buffers to stripes of said RAID storage system is delayed until a plurality of data blocks to be written to a stripe have accumulated in said plurality of buffers.

15. The method of claim 14 wherein said plurality of data blocks to be written to a stripe comprises a number of data blocks equal to a number of writable blocks of said stripe.

16. The method of claim 14 wherein said plurality of blocks to be written to a stripe of said RAID storage system are passed in a group to said RAID storage system.

17. The method of claim 12 wherein a first criteria is used to select said storage blocks of said storage devices when a rate at which said data blocks are to be written to said storage system is below a threshold level and wherein a second criteria is used to select said storage blocks of said storage devices when a rate at which said data blocks are to be written to said storage system is above said threshold level.

18. The method of claim 17 wherein said second criteria comprises selecting storage blocks of stripes of said RAID storage system that have a plurality of writable storage blocks.

19. The method of claim 18 wherein said stripes whose storage blocks are selected comprise stripes having a minimum number J of writable storage blocks.

20. The method of claim 19 wherein said first criteria comprises selecting storage blocks of stripes of said RAID storage system that have at most "K" writable storage blocks, where K<

J.

21. The method of claim 11 wherein said step of writing comprises the step of selecting said selected storage blocks, responsive to said information such that an arrangement of said data blocks stored in said storage blocks optimizes a selected measure for reading from said storage devices.

22. A method as in claim 21, wherein said selected measure of reading from said storage devices is an average time to read one of said data blocks stored in said storage blocks.

23. A method as in claim 21, wherein said selected measure of reading from said storage devices is a maximum time to read one of said data blocks stored in said storage blocks.

24. The method of claim 11 wherein said step of writing comprises the step of selecting said selected storage blocks, responsive to said information such that an arrangement of said data blocks stored in said storage blocks optimizes a selected measure for writing to said storage devices.

25. A method as in claim 24, wherein said selected measure of writing to said storage devices is an average time to write one of said data blocks stored in said storage blocks.

26. A method as in claim 24, wherein said selected measure of writing to said storage devices is a maximum time to write one of said data blocks stored in said storage blocks.

27. A method as in claim 24, wherein said selected measure of writing is to simultaneously maximize a measure of parallel storage of data blocks in a set of stripes and a measure of storage of data blocks common to a single file on a single storage device.

28. The method of claim 11 wherein data blocks from said sequence of data blocks are written to said storage devices of said storage system such that a plurality of consecutive data blocks from a file in said sequence of data blocks are stored in consecutive free storage blocks of a first storage device of said storage system.

29. The method of claim 28 wherein a maximum number I of consecutive data blocks from a file in said sequence of data blocks are stored in consecutive free storage blocks of a storage device, and wherein data blocks from said file in said sequence of data blocks in excess of said number I are stored in consecutive free storage blocks of a second storage device of said storage system.

30. The method of claim 29 wherein said first storage device is a storage device that has a lowest current write location.

31. The method of claim 11 wherein said step of writing said sequence of data blocks from files of said file system to selected storage blocks of selected storage devices of said storage system comprises the steps of:

examining a succeeding block in said sequence of data blocks to determine whether said block is from a different file than a preceding block in said sequence;

writing said succeeding block to a different one of said storage devices of said storage system from a storage device to which said preceding block is written if said succeeding block is from a different file.

32. The method of claim 31 wherein said second storage device is a storage device that has a lowest current write location.

33. The method of claim 11 wherein said step of writing said sequence of data blocks from files of said file system to selected storage blocks of selected storage devices of said storage system comprises the steps of:

examining a succeeding block in said sequence of data blocks to determine whether said block is from a different read ahead segment than a preceding block in said sequence, wherein a read ahead segment comprises N consecutive blocks in said sequence of data blocks from a file;

writing said succeeding block to a different one of said storage devices of said storage system from a storage device to which said preceding block is written if said succeeding block is from a different read ahead segment, otherwise writing said succeeding block to a same storage device as said preceding block.

34. The method of claim 33 wherein said different one of said storage devices is a storage device that has a lowest current write location.

35. The method of claim 11 wherein said step of writing said sequence of data blocks from files of said file system to selected storage blocks of selected storage devices of said storage system comprises the steps of:

examining a succeeding block in said sequence of data blocks to determine whether said block is from a different file than a preceding block in said sequence or whether said block is from a different read ahead segment than said preceding block, wherein a read ahead segment comprises N consecutive blocks in said sequence of data blocks from a file;

writing said succeeding block to a different one of said storage devices of said storage system from a storage device to which said preceding block is written if said succeeding block is from a different file or from a different read ahead segment, otherwise writing said succeeding block to a same storage device as said preceding block.

36. The method of claim 35 wherein said different one of said storage devices is a storage device that has a lowest current write location.

37. The method of claim 11 wherein said sequence of data blocks includes a plurality of data blocks that contain data modified from data previously stored in storage blocks of said storage system.

38. The method of claim 11 wherein said step of writing a sequence of data blocks from files of said file system to selected storage blocks of selected storage devices of said storage system comprises proceeding through each of said storage devices, filling in writable storage blocks, and wrapping to the beginning of a storage device when the end of the storage device is reached.

39. The method of claim 11 wherein said file system comprises a write-anywhere file system that allows file data as well as structures representing files to be written to any location on said storage devices.

40. The method of claim 11 wherein said sequence of data blocks from files of said file system written to said storage system comprises structures representing directories of said file system and structures representing files of said file system, and wherein storage blocks of said storage system are selected for said data blocks comprising structures representing directories of said file system before storage blocks of said storage system are selected for said data blocks comprising structures representing files of said file system.

41. The method of claim 11 wherein storage blocks of said storage system are selected for said sequence of data blocks from files of said file system on a basis of how recently a file has been used.

42. A method as in claim 11, wherein said file system comprises a set of current write location pointers.

43. A method as in claim 11, wherein at least one said data block comprises information about said file system.

44. A method as in claim 11, wherein at least one said file comprises a directory and wherein said directory comprises at least one said data block having information about said file system.

45. A method as in claim 11, wherein said current configuration information comprises a mapping between said data blocks and said storage blocks.

46. A method for integrating a file system having a plurality of files, with a storage system having a plurality of storage devices having a plurality of storage blocks, said method comprising

providing said file system with information regarding which ones of said storage blocks are allocated to which ones of said storage devices;

and

writing, responsive to said information, a sequence of data blocks from said files to selected said storage blocks of selected said storage devices.

47. A method for storing a plurality of data blocks on a plurality of storage devices, each said storage device having a plurality of storage blocks, said method comprising

providing, for each said storage device, a pointer to one of said storage blocks on that storage device;

and

writing a data block to a selected said storage block on a selected said storage device and updating said pointer for said storage device, in such manner as to preserve a predetermined relationship between pairs of said pointers for said storage devices;

wherein

selected ones of said storage blocks for a first said storage device correspond to selected ones of said storage blocks for a second said storage device;

pairs of said storage blocks for a first said storage device comprise a distance relationship; and

said predetermined relationship comprises maintaining a least possible value for said distance relationship between said pointer for said first storage device and said pointer for said second storage device, while still allowing up to N blocks from a single file to be written to a single storage device, wherein N is a predetermined integer.

48. A method for storing a plurality of data blocks on a plurality of storage devices, each said storage device having a plurality of storage blocks, said method comprising

providing, for each said storage device, a pointer to one of said storage blocks on that storage device;

and

writing a data block to a selected said storage block on a selected said storage device and updating said pointer for said storage device, in such manner as to preserve a predetermined relationship between pairs of said pointers for said storage devices;

wherein

each said pointer comprises an index value to a selected said storage block on a said storage device; and

said relationship comprises maintaining a least possible distance between each pair of said index values, while still allowing up to N blocks from a single file to be written to a single storage device, wherein N is a predetermined integer.

49. A method for storing a plurality of data blocks on a plurality of storage devices, each said storage device having a plurality of storage blocks, said method comprising

providing, for each said storage device, a pointer to one of said storage blocks on that storage device;

and

writing a data block to a selected said storage block on a selected said storage device and updating said pointer for said storage device, in such manner as to preserve a predetermined relationship between pairs of said pointers for said storage devices;

comprising

receiving a set of consecutive data blocks from a first said file; and

writing said consecutive data blocks to a set of consecutive free storage blocks on a single said storage device.

50. A method for storing a plurality of data blocks on a plurality of storage devices, each said storage device having a plurality of storage blocks, said method comprising

providing, for each said storage device, a pointer to one of said storage blocks on that storage device;

and

writing a data block to a selected said storage block on a selected said storage device and updating said pointer for said storage device, in such manner as to preserve a predetermined relationship between pairs of said pointers for said storage devices;

comprising

receiving a set of consecutive data blocks from a first said file;

writing said consecutive data blocks to a set of consecutive free storage blocks on a first said storage device, up to a selected maximum number of storage blocks; and

writing subsequent data blocks to a set of storage blocks on a second said storage device.

51. A method for storing a plurality of data blocks on a plurality of storage devices, each said storage device having a plurality of storage blocks, said method comprising

providing, for each said storage device, a pointer to one of said storage blocks on that storage device;

writing a data block to a selected said storage block on a selected said storage device and updating said pointer for said storage device, in such manner as to preserve a predetermined relationship between pairs of said pointers for said storage devices;

receiving a set of data blocks from a first and a second said file;

writing said data blocks from said first file to a first said storage device; and

writing said data blocks from said second file to a second said storage device.

52. A system comprising

a file system having a plurality of files, at least some of said files having at least one file block;

a plurality of storage devices, each having a plurality of storage blocks;

memory or storage having information regarding which ones of said file blocks are stored on which ones of said storage devices; and

means responsive to said information for writing data from said file blocks to said storage blocks;

wherein said storage devices comprise a RAID storage subsystem.

53. A system comprising

a file system having a plurality of files, at least some of said files having at least one file block;

a plurality of storage devices, each having a plurality of storage blocks;

memory or storage having information regarding which ones of said file blocks are stored on which ones of said storage devices; and

means responsive to said information for writing data from said file blocks to said storage blocks;

wherein each said storage block for a first said storage device corresponds to a storage block for a second said storage device,

said system comprising for each said storage device, a pointer representing one said storage block for said storage device; and

wherein said means for writing data comprises (a) means for selecting a first storage device for writing to, (b) means for writing to the storage block represented by the pointer for said first storage device, and (c) means for updating said pointer for said first storage device, wherein said means for selecting assures that no two said pointers differ by more than a selected amount.

54. A system as in claim 53, wherein said means for selecting operates to select a storage device corresponding to a pointer having a lowest value.

55. A system as in claim 53, wherein said means for selecting operates to select a first storage device for a first file, and to select a second storage device for a second file.

56. A system as in claim 53, wherein said means for selecting operates to select a first storage device for a first N file blocks of a first file, and to select a second storage device for a next file block of said first file.

57. A system comprising

a file system having a plurality of files, at least some of said files having at least one file block;

a plurality of storage devices, each having a plurality of storage blocks;

memory or storage having information regarding which ones of said file blocks are stored on which ones of said storage devices; and

means responsive to said information for writing data from said file blocks to said storage blocks;

wherein each of said storage devices comprises a magnetic disk, a magneto-optical disk, or an optical disk.

58. A system comprising

a file system having a plurality of files, at least some of said files having at least one file block;

a plurality of storage devices, each having a plurality of storage blocks;

memory or storage having information regarding which ones of said file blocks are stored on which ones of said storage devices;

means responsive to said information for writing data from said file blocks to said storage blocks;

means for receiving a first plurality of file blocks in a first order, said first plurality of file blocks to be written to said storage devices;

memory for storing said first plurality of file blocks; and

means for writing said first plurality of file blocks to a first plurality of storage blocks in a second order, wherein said second order differs from said first order.

59. A system comprising

a file system having a plurality of files, at least some of said files having at least one file block;

a plurality of storage devices, each having a plurality of storage blocks;

memory or storage having information regarding which ones of said file blocks are stored on which ones of said storage devices;

means responsive to said information for writing data from said file blocks to said storage blocks;

means for receiving a first plurality of file blocks in a first order, said first plurality of file blocks to be written to said storage devices;

memory for storing said first plurality of file blocks; and

means for writing said first plurality of file blocks to first plurality of storage blocks in a second order, wherein said second order differs from said first order;

wherein said first plurality of storage blocks comprises a stripe.

60. A system comprising

a file system having a plurality of files, at least some of said files having at least one file block;

a plurality of storage devices, each having a plurality of storage blocks;

memory or storage having information regarding which ones of said file blocks are stored on which ones of said storage devices;

means responsive to said information for writing data from said file blocks to said storage blocks;

means for receiving a first plurality of file blocks in a first order, said first plurality of file blocks to be written to said stroage devices;

memory for storing said first plurality of file blocks; and

means for writing said first plurality of file blocks to first plurality of storage blocks in a second order, wherein said second order differs from said first order;

wherein said means for writing comprises means for waiting for file blocks sufficient to complete an entire stripe of corresponding storage blocks for a plurality of storage devices.

61. In a computer system having memory or storage, a data structure in said memory or storage, said data structure comprising

a current write location pointer for each storage device of a plurality of said storage devices;

each said current write location pointer comprising an index of one storage block of a plurality of said storage blocks for a corresponding said storage device;

each pair of said current write location pointers having a defined maximum distance responsive to a preselected distance function.