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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.