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

• US 20040064474A1
• Filed: 08/08/2003
• Published: 04/01/2004
• Est. Priority Date: 06/03/1993
• Status: Active Grant

• Current Assignee: Byron Rakitzis, David Hitz, James Lau, Michael Malcolm
• Original Assignee: Byron Rakitzis, David Hitz, James Lau, Michael Malcolm
• Inventors: Hitz, David, Rakitzis, Byron, Lau, James, Malcolm, Michael
• Granted Patent: US 7,231,412 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• 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

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 disks 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 allocating files in a file system comprising:

a) select an inode having at least one dirty block from a list of inodes having dirty blocks;

b) write allocate a tree of buffers referenced by said inode to a storage means in a RAID array;

c) determine if all inodes in said list of inodes have been processed, when all of said inodes in said list of inodes have not been processed, continue repeating steps a-b; and

,

d) flush all unwritten stripes to said RAID array.