Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-04-28
2003-11-25
Vu, Kim (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06654772
ABSTRACT:
BACKGROUND OF THE INVENTION
This application relates generally to file systems, and more particularly, to extent based file systems.
Computer systems manipulate and store data files that often include a sequence of file segments. Each file segment occupies a consecutive sequence of physical storage blocks. The different file segments may, however, be stored at widely separated physical storage locations.
A file system makes the details of data storage of data files simpler for software application programs. The file system enables high-level applications to address stored data through abstract concepts such as directory name, file name, and offset rather than through actual physical storage addresses. This system for addressing data storage makes software applications less dependent on how data is physically stored so that the applications are less tied to the physical storage system and more portable.
FIG. 1
illustrates a file system that UNIX based systems employ to translate between abstract file names and physical storage addresses. The file system performs translations with the aid of two types of structures, which are stored on a data storage device
10
. The first type of structure is a directory
12
, which maps abstract directory names and file names to other directories
13
and index nodes (inodes)
15
,
16
, respectively. The second type of structure is the inode
15
,
16
, which maps abstract file segments to the physical data blocks
17
,
17
a
,
17
b
storing the segements.
The inodes
15
,
16
include lists of extents
21
-
27
. By definition, the consecutive extents
21
-
24
of each inode
15
correspond to consecutive file segments and indicate the storage addresses of the segments by an address pointer and a length. The address pointer indicates the physical address of the first data block, for example, blocks
55
,
59
, storing the file segment. The length indicates. the number of consecutive data blocks assigned to store the segment. For example, the extent
21
, which points to the address of the data block
55
and has length three, and includes the three data blocks
55
-
57
.
Each inode
15
,
16
can also include one or more special extents
24
,
27
stored at special positions of the inode
15
,
16
, that is, the last rows allocated in the inodes for extents. The special extents
24
,
27
point to data blocks that store additional extents. For example, the special extent
24
points to the data block
97
that stores additional extents
18
-
20
,
28
. The additional extents
18
-
20
point to strings of data blocks
95
storing segments, and enable extending the end of the file to increase the associated file's size. The last extent
28
of the data block
95
can also be a special extent thereby providing for further extensions of the end of the file.
Some file systems translate between large files and physical storage.
FIG. 2
illustrates a file system
30
capable of translating an abstract file
31
to data blocks stored on multiple physical disks
32
,
33
. To provide enough storage space for the large file
31
, the file system
34
interacts with an intermediate abstraction layer, a virtual logical volume
35
, which translates physical space
36
-
37
in the separate physical disks
32
-
33
into a single virtual space
38
. Then, software application
39
, which accesses the file
31
, sees the single large virtual volume
35
and is unaware of the separate devices
32
-
33
.
One objective of the present invention is to provide a file system that gives a more flexible method for extending an existing file.
Another objective of the present invention is to provide a file system adapted to storing large files.
SUMMARY OF THE INVENTION
In a first aspect, the invention provides a memory storage device having an operating system, which uses one inode to record and find segments of a data file. Each inode has a plurality of rows. Part of the rows are written with direct extents, which point to data blocks storing portions of file segments. At least two of the extents point to-data blocks whose addresses are in different logical volumes.
In a second aspect, the invention provides a memory storage device, which uses at least one inode for accessing file segments in storage devices. Each inode has a plurality of rows. A portion of the rows store extents pointing to data blocks. Each extent has a field to indicate whether the extent is an indirect extent or a direct extent and a field for a logical volume pointer.
In a third aspect, the invention provides a method for storing data files, which is performed by an operating system stored in a memory device. The method includes steps for writing extents to an inode assigned to the file, writing data to first and second data blocks, inserting an indirect extent in the inode between first and second ones of the extents, and writing a third extent to a third data block. The first and second ones of the extents point to the first and second data blocks. The indirect extent points to the third data block. The third extent points to a data block storing a segment of the file.
In a fourth aspect, the invention provides a distributed storage system. The storage system includes a global cache memory, a plurality of processors coupled to the global cache memory, and a plurality of data storage devices coupled to the global cache memory. Each processor has a local memory for storing an operating system. The devices and processors are capable of communicating by posting messages to each other in the cache memory. Each of the devices has a processor and local memory storing an operating system. Each operating system includes an extent based file system for abstracting file names to physical data blocks in the storage devices by assigning an inode to each file. Each inode adapted to store extents having a field to pointing to a logical volume.
REFERENCES:
patent: 5276867 (1994-01-01), Kenley et al.
patent: 5339411 (1994-08-01), Heaton, Jr.
patent: 5454103 (1995-09-01), Coverston et al.
patent: 5666532 (1997-09-01), Saks et al.
patent: 5774715 (1998-06-01), Madany et al.
patent: 5875444 (1999-02-01), Hughes
patent: 5897661 (1999-04-01), Baranovsky et al.
patent: 5918229 (1999-06-01), Davis et al.
patent: 5974503 (1999-10-01), Venkatesh et al.
patent: 5987506 (1999-11-01), Carter et al.
patent: 5991862 (1999-11-01), Ruane
patent: 5996047 (1999-11-01), Peacock
patent: 6029166 (2000-02-01), Mutalik et al.
patent: 6141773 (2000-10-01), St. Pierre et al.
patent: 6144969 (2000-11-01), Inokuchi et al.
patent: 6161111 (2000-12-01), Mutalik et al.
patent: 6353837 (2002-03-01), Blumenau
patent: 6397311 (2002-05-01), Capps
“The Design and Performance of a Shared Disk File System for IRIX,” Steve Soltis et al., Sixth NASA Goddard Space Flight Center Conference on Mass Storage and Technologies, Fifteenth IEEE Symposium on Mass Storage Systems, Mar. 23-26, 1998.
“A 64-Bit, Shared Disk File System for Linux,” Kenneth W. Preslan et al., Sixteenth IEEE Mass Storage Sys. Symposium, the Seventh NASA Goddard Conference on Mass Storage & Technologies, Mar. 15-18, 1999, San Diego.
Crow Preston F.
Mason, Jr. Robert S.
McClure Steven T.
Nagy Susan C.
Wheeler Richard G.
EMC Corporation
Gunther John M.
Ly Anh
Vu Kim
Wilson Penelope S.
LandOfFree
Multi-volume extent based file system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-volume extent based file system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-volume extent based file system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3116217