EP1197836A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
A method for allocating files in a file system integrated with a raid disk sub-system
Assignee: NetApp Inc
•
Filing: 1994-06-02
•
Granted: —
•
Expires: 2014-06-02
Abstract
Abstract The present invention is a method for integrating a file system with a RAID array (1030) that exports precise information about the arrangement of data blocks in the RAID subsystem (1030). 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 (1022) in the disk array (1030) where the pointers simply advance through disks (1022) 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 (1030) efficiency by writing to multiple blocks in the stripe simultaneously. The second goal is to allocate adjacent blocks of a file on the same disk (1022), thereby improving read back performance. The first goal is satisfied by always writing on the disk (1022) with the lowest CWL pointer. For the second goal, another disk (1024) is chosen only when the algorithm starts allocating space for a new file, or when it has allocated N blocks on the same disk (1022) for a single file. The result is that CWL pointers are never more than N blocks apart on different disks (1024), and large files have N consecutive blocks on the same disk (1022).
Inventors
- 👤 David Hitz
- 👤 Michael Malcolm
- 👤 James Lau
- 👤 Byron Rakitzis
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-05 07:39
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/061; G06F3/0611; G06F3/0613; G06F3/0628; G06F3/0629; G06F3/0631; G06F3/0638; G06F3/0643; G06F3/0668; G06F3/0671; G06F3/0683; G06F3/0689; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99955
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
110 words
A method for allocating files in a file system comprising: a) selecting an inode having at least one dirty block from a list of inodes
having dirty blocks; b) write allocating blocks of data referenced by said inode to a storage means
in a RAID array wherein said storage means comprises a plurality of storage blocks and add
said blocks of data to a list of writeable blocks of data for said storage means; c) determining if all nodes have been processed, when all of said inodes in
said list of inodes have not been processed, continue repeating steps a-b; and, d) flushing all unwritten stripes to said RAID array.
Claim 2
Dependent Claim
15 words
The method of claim 1 wherein said blocks of data are stored in a cache.
Claim 3
Dependent Claim
30 words
The method of claim 1 or 2 wherein said blocks of data referenced by said
inode are write allocated in a depth-first, post visit traversal of said blocks of data.
Claim 4
Dependent Claim
35 words
The method of claim 1, 2 or 3 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.
Claim 5
Dependent Claim
19 words
The method of claim 4 wherein each directory of said one or more
directories is a specially formatted file.
Claim 6
Dependent Claim
34 words
The method of claim 4 or 5 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.
Claim 7
Dependent Claim
20 words
The method of claim 6 wherein said second plurality of inodes are write
allocated on a least recently used basis.
Claim 8
Independent Claim
103 words
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.
Claim 9
Dependent Claim
14 words
The method of claim 8 wherein said storage system comprises a RAID
storage system.
Claim 10
Dependent Claim
59 words
The method of claim 9 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.
Claim 11
Dependent Claim
44 words
The method of claim 10 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.
Claim 12
Dependent Claim
33 words
The method of claim 11 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.
Claim 13
Dependent Claim
33 words
The method of claim 11 or 12 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.
Claim 14
Dependent Claim
83 words
The method of claim 9, 10, 11, 12 or 13 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.
Claim 15
Independent Claim
105 words
The method of any one of claims 8 to 14 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.
Claim 16
Dependent Claim
21 words
The method of claim 15 wherein said second storage device is a storage
device that has a lowest current write location.
Claim 17
Independent Claim
141 words
The method of any one of claims 8 to 16 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.
Claim 18
Dependent Claim
24 words
The method of claim 17 wherein said different one of said storage
devices is a storage device that has a lowest current write location.
Claim 19
Independent Claim
39 words
The method of any one of claims 8 to 18 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.
Claim 20
Independent Claim
23 words
A method as in any one of claims 8 to 19, wherein said file system
comprises a set of current write location pointers.
Claim 21
Independent Claim
77 words
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.
Claim 22
Independent Claim
82 words
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.
Claim 23
Independent Claim
180 words
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.
Claim 24
Dependent Claim
25 words
A system as in claim 23, wherein said means for selecting operates to
select a storage device corresponding to a pointer having a lowest value.
Claim 25
Dependent Claim
35 words
A system as in claim 23 or 24, 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.
Claim 26
Dependent Claim
46 words
A system as in claim 23 or 24, 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.
Claim 27
Independent Claim
90 words
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.
Claim 28
Independent Claim
137 words
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.
Claim 29
Independent Claim
146 words
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.
Claim 30
Dependent Claim
78 words
A data structure for use in memory or storage of a computer system, 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.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.