Patent US5960446A successfully refreshed from Google Patents.
US5960446A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parallel file system and method with allocation map
Assignee: Google LLC
•
Filing: 1997-07-11
•
Granted: 1999-09-28
•
Expires: 2017-07-11
Abstract
Abstract A computer system having a shared disk file system running on on multiple computers each having their own instance of an operating system and being coupled for parallel data sharing access to files residing on network attached shared disks. Methods are provided for use as a parallel file system in a shared disk environment by use of a scalable directory service for the system with a stable cursor, a segmented allocation map. Dynamic prefetch and cached balance pools for multiple accesses improve the system. Extended file attributes are used for implementation of Access Control Lists in a parallel file system. Improvement to caching and cache performance development balance pools for multiple accesses. A metadata node manages file metadata for parallel read and write actions. For our system, tokens are used for metadata node selection and identification, and we have enhanced token modes for controlling file size, as well as smart caching of byte range tokens using file access patterns and a byte range lock algorithm using a byte range token interface. Locking techniques reduce the overhead of a token manager which is also used in the file system recovery if a computer participating in the management of shared disks becomes unavailable or failed.
Inventors
- 👤 Frank B. Schmuck
- 👤 Roger Lee Haskin
- 👤 Zvi Yosef Yehudai
- 👤 James Christopher Wyllie
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 07:30
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/10; G06F16/18; G06F16/1858; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99939; Y10S707/99941; Y10S707/99942; Y10S707/99951; Y10S707/99956
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
280 words
In a system employing a file system for storing file data and having a file structure that includes metadata, a method comprising: providing a parallel file system for multiple servers of the file system with a file structure residing on one or more disks directly accessible by multiple separate peer computer nodes, said file system allowing a computation that uses the file structure to be broken up into multiple pieces that can be run in parallel on separate computer nodes allowing users to login to any node of said multiple separate peer computer nodes which share in the management of the file system and to access multiple disks in the system which are directly attached to different server nodes, said file system managing sets of disks which hold data and metadata allowing said multiple separate peer computer nodes to share in the management of the file system without assignment of the files system management to a single computer node with disks containing the data and metadata being attached to different ones of the multiple peer computer nodes in a manner that makes the disks appear to be locally attached to each file system even though directly attached to a separate peer computer node and to appear the same for all instances of the file system, and allocating files with said multiple separate peer computer nodes in an allocation map which is part of said file structure which is stored as part of metadata for said file structure, wherein said allocation map is subdivided into a number of regions, whereby by using distinct regions said multiple separate peer computer nodes simultaneously allocate striped files in parallel without interfering with each other.
Claim 2
Dependent Claim
280 words
In a system employing a file system for storing file data and having a file structure that includes metadata, a method comprising: providing a parallel file system for multiple servers of the file system with a file structure residing on one or more disks directly accessible by multiple separate peer computer nodes, said file system allowing a computation that uses the file structure to be broken up into multiple pieces that can be run in parallel on separate computer nodes allowing users to login to any node of said multiple separate peer computer nodes which share in the management of the file system and to access multiple disks in the system which are directly attached to different server nodes, said file system managing sets of disks which hold data and metadata allowing said multiple separate peer computer nodes to share in the management of the file system without assignment of the files system management to a single computer node with disks containing the data and metadata being attached to different ones of the multiple peer computer nodes in a manner that makes the disks appear to be locally attached to each file system even though directly attached to a separate peer computer node and to appear the same for all instances of the file system, and allocating files with said multiple separate peer computer nodes in an allocation map which is part of said file structure which is stored as part of metadata for said file structure, wherein said allocation map is subdivided into a number of regions, whereby by using distinct regions said multiple separate peer computer nodes simultaneously allocate striped files in parallel without interfering with each other.
Claim 3
Dependent Claim
24 words
In a system employing a file system according to claim 1, wherein said file system locks regions to synchronize access to the allocation map.
Claim 4
Dependent Claim
52 words
In a system employing a file system according to claim 1, wherein said system is provided with a disk allocation for subdividing said allocation map into regions, and when said map is divided into K regions, each region controls 1/K of the blocks on each of N disks of the file system.
Claim 5
Dependent Claim
82 words
In a system employing a file system according to claim 3, wherein said allocation map may use the same block size as a regular file, and wherein said regions are composed of one or more disk segments, where each segment is at most the size of an allocation block and controls allocation of blocks on a subset of said N disks, and wherein if regions are less than half the size of map blocks, multiple regions are packed into each map block.
Claim 6
Dependent Claim
48 words
In a system employing a file system according to claim 1, wherein in the allocation of map regions, the number of regions is selected to be at least as large as the number of file system nodes, so that each node can be allocate from a different region.
Claim 7
Dependent Claim
66 words
In a system employing a file system according to claim 1, wherein the first segment of each region is stored at the beginning of the allocation map, followed by a second segment of each region, and the file system can be extended by adding more disks without reorganization of tie allocation map, and wherein additional segments are appended to the end of an existing allocation map.
Claim 8
Dependent Claim
68 words
In a system employing a file system according to claim 1, wherein said file system provides a token resource, and for allocation of successive blocks of a striped file, a node obtains a token for a region and allocates successive blocks according to a striping permutation using free blocks whose allocation map elements indicate their state is free in the region for which said node obtains a token.
Claim 9
Dependent Claim
36 words
In a system employing a file system according to claim 1, wherein there is included an allocation manager program for tracking nodes using an allocation region, and for tracking the free space remaining in each region.
Claim 10
Dependent Claim
39 words
In a system employing a file system according to claim 8, further including a step for directing block deallocation to each node that is using a region controlling the block being allocated with said allocation manager and file system.
Claim 11
Dependent Claim
201 words
In a system employing a file system for storing file data and having a file structure that includes metadata, a method comprising: providing a file system with a file structure residing on one or more disks accessible by multiple separate computer nodes, said file system allowing a computation that uses the file structure to be broken up into multiple pieces that can be run in parallel on separate computer nodes, and allocating with multiple separate computer nodes in an allocation map which is part of said file structure which is stored as part of metadata for said file structure, wherein said allocation map is subdivided into a number of regions, whereby by using distinct regions said multiple separate computer nodes simultaneously allocate striped files without interfering with each other; and wherein said allocation map may use the same block size as a regular file, and wherein said regions are composed of one or more disk segments, where each segment is at most the size of an allocation block and controls allocation of blocks on a subset of said N disks, and wherein if regions are less than half the size of map blocks, multiple regions are packed into each map block.
Claim 12
Dependent Claim
201 words
In a system employing a file system for storing file data and having a file structure that includes metadata, a method comprising: providing a file system with a file structure residing on one or more disks accessible by multiple separate computer nodes, said file system allowing a computation that uses the file structure to be broken up into multiple pieces that can be run in parallel on separate computer nodes, and allocating with multiple separate computer nodes in an allocation map which is part of said file structure which is stored as part of metadata for said file structure, wherein said allocation map is subdivided into a number of regions, whereby by using distinct regions said multiple separate computer nodes simultaneously allocate striped files without interfering with each other; and wherein said allocation map may use the same block size as a regular file, and wherein said regions are composed of one or more disk segments, where each segment is at most the size of an allocation block and controls allocation of blocks on a subset of said N disks, and wherein if regions are less than half the size of map blocks, multiple regions are packed into each map block.
Claim 13
Dependent Claim
185 words
In a system employing a file system for storing file data and having a file structure that includes metadata, a method comprising: providing a file system with a file structure residing on one or more disks accessible by multiple separate computer nodes, said file system allowing a computation that uses the file structure to be broken up into multiple pieces that can be run in parallel on separate computer nodes, and allocating with multiple separate computer nodes in an allocation map which is part of said file structure which is stored as part of metadata for said file structure, wherein said allocation map is subdivided into a number of regions, whereby by using distinct regions said multiple separate computer nodes simultaneously allocate striped files without interfering with each other; and wherein the first segment of each region is stored at the beginning of the allocation map, followed by a second segment of each region, and the file system can be extended by adding more disks without reorganization of the allocation map, and wherein additional segments are appended to the end of an existing allocation map.
Claim 14
Dependent Claim
185 words
In a system employing a file system for storing file data and having a file structure that includes metadata, a method comprising: providing a file system with a file structure residing on one or more disks accessible by multiple separate computer nodes, said file system allowing a computation that uses the file structure to be broken up into multiple pieces that can be run in parallel on separate computer nodes, and allocating with multiple separate computer nodes in an allocation map which is part of said file structure which is stored as part of metadata for said file structure, wherein said allocation map is subdivided into a number of regions, whereby by using distinct regions said multiple separate computer nodes simultaneously allocate striped files without interfering with each other; and wherein the first segment of each region is stored at the beginning of the allocation map, followed by a second segment of each region, and the file system can be extended by adding more disks without reorganization of the allocation map, and wherein additional segments are appended to the end of an existing allocation map.
Claim 15
Dependent Claim
155 words
In a system employing a file system for storing file data and having a file structure that includes metadata, a method comprising: providing a file system with a file structure residing on one or more disks accessible by multiple separate computer nodes, said file system allowing a computation that uses the file structure to be broken up into multiple pieces that can be run in parallel on separate computer nodes, and allocating with multiple separate computer nodes in an allocation map which is part of said file structure which is stored as part of metadata for said file structure, wherein said allocation map is subdivided into a number of regions, whereby by using distinct regions said multiple separate computer nodes simultaneously allocate striped files without interfering with each other; and wherein there is included an allocation manager program for tracking nodes using an allocation region, and for tracking the free space remaining in each region.
Claim 16
Dependent Claim
155 words
In a system employing a file system for storing file data and having a file structure that includes metadata, a method comprising: providing a file system with a file structure residing on one or more disks accessible by multiple separate computer nodes, said file system allowing a computation that uses the file structure to be broken up into multiple pieces that can be run in parallel on separate computer nodes, and allocating with multiple separate computer nodes in an allocation map which is part of said file structure which is stored as part of metadata for said file structure, wherein said allocation map is subdivided into a number of regions, whereby by using distinct regions said multiple separate computer nodes simultaneously allocate striped files without interfering with each other; and wherein there is included an allocation manager program for tracking nodes using an allocation region, and for tracking the free space remaining in each region.
Claim 17
Dependent Claim
158 words
In a system employing a file system for storing file data and having a file structure that includes metadata, a method comprising: providing a file system with a file structure residing on one or more disks accessible by multiple separate computer nodes, said file system allowing a computation that uses the file structure to be broken up into multiple pieces that can be run in parallel on separate computer nodes, and allocating with multiple separate computer nodes in an allocation map which is part of said file structure which is stored as part of metadata for said file structure, wherein said allocation map is subdivided into a number of regions, whereby by using distinct regions said multiple separate computer nodes simultaneously allocate striped files without interfering with each other; and wherein including a step for directing block deallocation to each node that is using a region controlling the block being allocated with said allocation manager and file system.
Claim 18
Dependent Claim
158 words
In a system employing a file system for storing file data and having a file structure that includes metadata, a method comprising: providing a file system with a file structure residing on one or more disks accessible by multiple separate computer nodes, said file system allowing a computation that uses the file structure to be broken up into multiple pieces that can be run in parallel on separate computer nodes, and allocating with multiple separate computer nodes in an allocation map which is part of said file structure which is stored as part of metadata for said file structure, wherein said allocation map is subdivided into a number of regions, whereby by using distinct regions said multiple separate computer nodes simultaneously allocate striped files without interfering with each other; and wherein including a step for directing block deallocation to each node that is using a region controlling the block being allocated with said allocation manager and file system.
References Cited (Backward Citations)
US4274139A
Cited
US5202971A
Cited
US5129088A
Cited
US5043876A
Cited
US5572699A
Cited
US5375233A
Cited
US5226159A
Cited
US5463736A
Cited
US5454108A
Cited
US5784646A
Cited
US5537588A
Cited
US5490270A
Cited
US5566297A
Cited
US5675769A
Cited
US5706472A
Cited
US5774715A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-27 | 2003-03-29 | 2003-09-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-27 | 2007-03-29 | 2007-09-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-27 | 2011-03-29 | 2011-09-28 | $7700.00 | Window Closed / Lapsed |