Patent EP0376045A2 successfully refreshed from Google Patents.
Patent US5893086A successfully refreshed from Google Patents.
US5893086A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parallel file system and method with extensible hashing
Assignee: International Business Machines Corp
•
Filing: 1997-07-11
•
Granted: 1999-04-06
•
Expires: 2017-07-11
Abstract
Abstract A computer system having a shared parallel disk file system running on a network for multiple computers each having their own instance of an operating system and with a protocol that makes disks appear to be locally attached to each file system. This parallel file system in a shared disk environment uses scalable directory service method improvements to caching and cache performance developments balance pools for multiple accesses. A metadata node manages file metadata, and 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. Synchronous and asynchronous takeover of a metadata node occurs for correction of metadata which was under modification and a new computer node to be a metadata node for that file. Locks are not constantly required to allocate new blocks on behalf of a user. Hash buckets are used and each hash bucket is stored in a sparse file at an offset given as i*s, where i is the hash bucket number and s is the hash bucket size, an where a directory starts out as an empty file, where the file size increases to the size where it needs to be split by inserting records, and wherein upon a split, an additional bucket is written increasing the file size from s to 2*s upon the first split. Lookup operations are performed with a step of computing the hash value of the key being looked up, as well as a hash tree depth as log-base-2 of the file size divided by hash bucket size, and with compute steps also computed for an insert operation.
Inventors
- 👤 Frank B. Schmuck
- 👤 James Christopher Wyllie
- 👤 Thomas E. Engelsiepen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 10:54
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1402; G06F11/1415; G06F11/1435; G06F16/00; G06F16/10; G06F16/13; G06F16/137; G06F16/18; G06F16/1858; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
324 words
In a system which is used for storing and indexing a large set of data records and supports fast insert, delete and lookup operations and also sequential retrieval of all data records of said set, a method comprising: providing a file system for said system which allows storing and retrieving data by specifying a key that identifies a data record, providing for a set of data records an index or directory with a single initial hash bucket, and storing in said initial hash by use of a hash function all records of a set of data records to be stored as long as they fit into said initial hash bucket, and when the initial hash bucket is full, splitting by adding a second hash bucket and adding one bit to said hash function used to place records whereby those records without said one bit are moved into said initial hash bucket while those records with said one bit are moved into said second hash bucket and wherein new records are added to the initial bucket or said second bucket depending upon the value of the bit for said hash function, and if a hash bucket fills up again, the bucket is split and two bits for the hash function determine where records from the second bucket are to be placed, while the records in the initial bucket are not effected by a new split of said second bucket, but can be split as well, and wherein each hash bucket is stored in a sparse file at an offset given as i*s, where i is the hash bucket number and s is the hash bucket size, an where a directory starts out as an empty file, where the file size increases to the size where it needs to be split by inserting records, and wherein upon a split, an additional bucket is written increasing the file size from s to 2*s upon the first split.
Claim 2
Dependent Claim
324 words
In a system which is used for storing and indexing a large set of data records and supports fast insert, delete and lookup operations and also sequential retrieval of all data records of said set, a method comprising: providing a file system for said system which allows storing and retrieving data by specifying a key that identifies a data record, providing for a set of data records an index or directory with a single initial hash bucket, and storing in said initial hash by use of a hash function all records of a set of data records to be stored as long as they fit into said initial hash bucket, and when the initial hash bucket is full, splitting by adding a second hash bucket and adding one bit to said hash function used to place records whereby those records without said one bit are moved into said initial hash bucket while those records with said one bit are moved into said second hash bucket and wherein new records are added to the initial bucket or said second bucket depending upon the value of the bit for said hash function, and if a hash bucket fills up again, the bucket is split and two bits for the hash function determine where records from the second bucket are to be placed, while the records in the initial bucket are not effected by a new split of said second bucket, but can be split as well, and wherein each hash bucket is stored in a sparse file at an offset given as i*s, where i is the hash bucket number and s is the hash bucket size, an where a directory starts out as an empty file, where the file size increases to the size where it needs to be split by inserting records, and wherein upon a split, an additional bucket is written increasing the file size from s to 2*s upon the first split.
Claim 3
Dependent Claim
66 words
The method for said system of claim 1 wherein after several splits the several hash buckets are treated as a binary hash tree, whereby a record is found by traversing the tree from a root initial bucket node to a leaf hash bucket node using the hash bucket bits as a key to decide which branch to follow at each inner node of said binary tree.
Claim 4
Dependent Claim
20 words
The method for said system of claim 1 wherein a sequential directory scan is accomplished by a depth-first tree transversal.
Claim 5
Dependent Claim
53 words
The method for said system of claim 1 wherein several buckets are processed as a binary hash tree represented as a sparse file on disk, where records are relocated when a hash bucket is split, and a sequential directory scan traverses said hash tree such that all existing entries are returned exactly once.
Claim 6
Dependent Claim
293 words
In a system which is used for storing and indexing a large set of data records and supports fast insert, delete and lookup operations and also sequential retrieval of all data records of said set, a method comprising: providing a file system for said system which allows storing and retrieving data by specifying a key that identifies a data record, providing for a set of data records an index or directory with a single initial hash bucket, and storing in said initial hash by use of a hash function all records of a set of data records to be stored as long as they fit into said initial hash bucket, and when the initial hash bucket is full, splitting by adding a second hash bucket and adding one bit to said hash function used to place records whereby those records without said one bit are moved into said initial hash bucket while those records with said one bit are moved into said second hash bucket and wherein new records are added to the initial bucket or said second bucket depending upon the value of the bit for said hash function, and if a hash bucket fills up again, the bucket is split and two bits for the hash function determine where records from the second bucket are to be placed, while the records in the initial bucket are not effected by a new split of said second bucket, but can be split as well, and wherein lookup operations are performed with a step of computing the hash value of the key being looked up, as well as a hash tree depth as log-base-2 of the file size divided by hash bucket size, and said compute steps are also computed for an insert operation.
Claim 7
Dependent Claim
293 words
In a system which is used for storing and indexing a large set of data records and supports fast insert, delete and lookup operations and also sequential retrieval of all data records of said set, a method comprising: providing a file system for said system which allows storing and retrieving data by specifying a key that identifies a data record, providing for a set of data records an index or directory with a single initial hash bucket, and storing in said initial hash by use of a hash function all records of a set of data records to be stored as long as they fit into said initial hash bucket, and when the initial hash bucket is full, splitting by adding a second hash bucket and adding one bit to said hash function used to place records whereby those records without said one bit are moved into said initial hash bucket while those records with said one bit are moved into said second hash bucket and wherein new records are added to the initial bucket or said second bucket depending upon the value of the bit for said hash function, and if a hash bucket fills up again, the bucket is split and two bits for the hash function determine where records from the second bucket are to be placed, while the records in the initial bucket are not effected by a new split of said second bucket, but can be split as well, and wherein lookup operations are performed with a step of computing the hash value of the key being looked up, as well as a hash tree depth as log-base-2 of the file size divided by hash bucket size, and said compute steps are also computed for an insert operation.
Claim 8
Dependent Claim
50 words
The method for said system of claim 5 wherein for a sparse file a hole is aligned on file system block barriers and file metadata that contains the location of a file's disk blocks is cached, such that the bucket size is the same as the file system block size.
Claim 9
Dependent Claim
111 words
The method for said system of claim 5 and wherein lookup operations are performed with a step of computing the hash value of the key being looked up, as well as a hash tree depth as log-base-2 of the file size divided by hash bucket size, and said compute steps are also computed for an insert operation. wherein a scan operation is provided that can be invoked repeatedly to return the contents of a hash tree as a sequential directory scan, wherein each call returns one or more records plus a content information value that is passed to a next scan call in order to retrieve a next set of records.
Claim 10
Dependent Claim
18 words
The method for said system of claim 5 wherein hash bucket merges are handled during a sequential scan.
Claim 11
Dependent Claim
16 words
The method for said system of claim 5 wherein said system is a parallel file system.
Claim 12
Dependent Claim
46 words
The method for said system of claim 5 wherein said system is a used for one or more shared disk file systems implemented for multiple computers interconnected over a communication network with a protocol that makes disks appear to be locally attached to each file system.
References Cited (Backward Citations)
US4274139A
Cited
US4956772A
Cited
US5202971A
Cited
US5043876A
Cited
US5226159A
Cited
US5463736A
Cited
US5440732A
Cited
US5432852A
Cited
US5542087A
Cited
US5454108A
Cited
US5742806A
Cited
US5490270A
Cited
US5566297A
Cited
US5687361A
Cited
US5748952A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-04-05 | 2002-10-05 | 2003-04-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-04-05 | 2006-10-05 | 2007-04-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-04-05 | 2010-10-05 | 2011-04-06 | $7700.00 | Window Closed / Lapsed |