Atomic renaming and moving of data files while permitting lock-free look-ups

• US 7,987,166 B2
• Filed: 04/22/2007
• Issued: 07/26/2011
• Est. Priority Date: 03/30/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sarma, Dipankar, McKenney, Paul E., Soni, Maneesh
• Primary Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US11/738,501
• Publication Number:
  US 20070198520A1
• Time in Patent Office: 1,556 Days
• Field of Search: 707200-206, 707/625, 707/636, 707/705, 707/821, 707/822, 707/674, 707/704
• US Class Current: 707/704
• CPC Class Codes: G06F 16/10 File systems; File servers

Abstract

Atomic renaming and moving of data files, while permitting lock-free look-ups to the data files, is disclosed. A temporary record may be created within a hash chain encompassing a record for a data file and corresponding to a location of the data file within a computer file system. The temporary record is linked within the hash chain so that the temporary record points to the same records to which the record for the data file points. The record for the data file is renamed with a new name, and/or moved to a new location within the computer file system, and the temporary record is removed from the hash chain. Before the temporary record is removed, look-ups of the data file resolve to the temporary record, the temporary record causing the look-ups to wait until the record for the data file has been renamed and/or moved and the temporary record removed.

Claims

1. A computer-implemented method comprising:

renaming a data file of a computer system while permitting lock-free look-ups to the data file by utilizing a temporary record to which look-ups to the data file resolve while the data file is being renamed;

looking up the data file in a lock free-manner while the data file is being atomically renamed, by, while traversing records of a containing construct of a record for the data file to locate the record for the data file;

where a number of the records of the containing construct traversed so far exceeds a predetermined maximum number of records, reverting to a locking process to look up the data file;

where a currently traversed record of the containing construct has already been traversed, returning failure of the look-up of the data file;

where a currently traversed record of the containing construct does not match the data file, continuing traversal of the records of the containing construct;

where a currently traversed record of the containing construct matches the data file and is a temporary record for the data file, waiting until the temporary record has been removed and restarting look-up of the data file; and

,

where a currently traversed record of the containing construct matches the data file and is the record for the data file, returning the record such that look-up of the data file has succeeded.

2. The method of claim 1, wherein renaming the data file comprises atomically renaming the data file.

3. The method of claim 2, wherein atomically renaming the data file of the computer file system while permitting lock-free look-ups to the data file comprises atomically renaming the data file of the computer file system such that once a look-up of an old name of the data file necessarily fails, any subsequent look-up of a new name of the data file necessarily succeeds, and such that once a look-up of the new name of the data file necessarily succeeds, any subsequent look-up of the old name of the data file necessarily fails.

4. The method of claim 1, wherein the containing construct of the record for the data file is one of a hash chain and a sub-directory.

5. A computer-implemented method comprising:

atomically moving a data file from one location to another location within a computer file system while permitting lock-free look-ups to the data file by utilizing a temporary record to which look-ups to the data file resolve while the data file is being moved,

wherein atomically moving the data file from one location to another location within the computer file system comprises;

creating a temporary record within a hash chain encompassing a record for the data file and corresponding to an old location of the data file within the computer file system;

linking the temporary record within the hash chain so that the temporary record points to a before record to which the record for the data file points and to an after record to which the record for the data file points;

moving the record for the data file to another hash chain corresponding to a new location of the data file within the computer file system; and

,

removing the temporary record from the hash chain,

wherein while the temporary record exists within the hash chain, look-ups of the data file resolve to the temporary record, such that the temporary record causes the look-ups to wait until the record for the data file has been moved to the other hash chain and the temporary record removed.

6. The method of claim 5, further comprising, while traversing records of a containing construct of a record for the data file to locate the record for the data file:

where a number of the records of the containing construct traversed so far exceeds a predetermined maximum number of records, reverting to a locking process to look up the data file;

where a currently traversed record of the containing construct has already been traversed, returning failure of the look-up of the data file;

where a currently traversed record of the containing construct does not match the data file, continuing traversal of the records of the containing construct;

where a currently traversed record of the containing construct matches the data file and is a temporary record for the data file, waiting until the temporary record has been removed and restarting look-up of the data file; and

,

where a currently traversed record of the containing construct matches the data file and is the record for the data file, returning the record such that look-up of the data file has succeeded.

7. A computer-implemented method comprising:

creating a temporary record within a hash chain encompassing a record for a data file and corresponding to a location of the data file within a computer file system;

linking the temporary record within the hash chain so that the temporary record points to a before record to which the record for the data file points and to an after record to which the record for the data file points;

renaming the record for the data file with a new name; and

,

removing the temporary record from the hash chain,

wherein while the temporary record exists within the hash chain, look-ups of the data file resolve to the temporary record, such that the temporary record causes the look-ups to wait until the record for the data file has been renamed and the temporary record has been removed.

8. The method of claim 7, further comprising, prior to removing the temporary record from the hash chain, moving the record for the data file to another hash chain corresponding to a new location of the data file within the computer file system, wherein while the temporary record exists within the hash chain, look-ups of the data file resolve to the temporary record, such that the temporary record causes the look-ups to wait until the record for the data file has been renamed and moved to the other hash chain and the temporary record has been removed.

9. The method of claim 7, further comprising looking-up the data file in a lock-free manner, by traversing records of the hash chain encompassing the record for the data file to locate the record for the data file, and where a currently traversed record of the hash chain matches the data file and is a temporary record for the data file, waiting until the temporary record has been removed and then restarting look-up of the data file.

10. A computer-implemented method comprising:

creating a temporary record within a hash chain encompassing a record for a data file and corresponding to a location of the data file within a computer file system;

linking the temporary record within the hash chain so that the temporary record points to a before record to which the record for the data file points and to an after record to which the record for the data file points;

moving the record for the data file to another hash chain corresponding to a new location of the data file within the computer file system; and

,

removing the temporary record from the hash chain,

wherein while the temporary record exists within the hash chain, look-ups of the data file resolve to the temporary record, such that the temporary record causes the look-ups to wait until the record for the data file has been moved and the temporary record removed.

11. The method of claim 10, further comprising, prior to moving the record for the data file to the other hash chain, renaming the record for the data file with a new name, wherein while the temporary record exists within the hash chain, look-ups of the data file resolve to the temporary record, such that the temporary record causes the look-ups to wait until the record for the data file has been renamed and moved to the other hash chain and the temporary record removed.

12. The method of claim 10, further comprising looking-up the data file in a lock-free manner, by traversing records of the hash chain encompassing the record for the data file to locate the record for the data file, and where a currently traversed record of the hash chain matches the data file and is a temporary record for the data file, waiting until the temporary record has been removed and then restarting look-up of the data file.

13. A computer-implemented system comprising:

a file system in which a plurality of files are stored; and

,

means for at least one of atomically renaming and atomically moving from one location to another one of the files within the file system, while permitting lock-free file look-ups,

wherein atomically renaming the one of the files is achieved by the means;

creating a temporary record within a hash chain encompassing a record for a data file and corresponding to a location of the data file within the file system, the data file being the one of the files;

linking the temporary record within the hash chain so that the temporary record points to a before record to which the record for the data file points and to an after record to which the record for the data file points;

renaming the record for the data file with a new name; and

,

removing the temporary record from the hash chain,

where while the temporary record exists within the hash chain, look-ups of the data file resolve to the temporary record, such that the temporary record causes the look-ups to wait until the record for the data file has been renamed and the temporary record has been removed,

wherein atomically moving the one of the files is achieved by the means;

creating a temporary record within a hash chain encompassing a record for the data file and corresponding to the location of the data file within the file system;

linking the temporary record within the hash chain so that the temporary record points to a before record to which the record for the data file points and to an after record to which the record for the data file points;

moving the record for the data file to another hash chain corresponding to a new location of the data file within the computer file system; and

,

removing the temporary record from the hash chain,

where while the temporary record exists within the hash chain, look-ups of the data file resolve to the temporary record, such that the temporary record causes the look-ups to wait until the record for the data file has been moved and the temporary record removed.

14. The system of claim 13, wherein the system comprises a plurality of computing nodes over which the file system is implemented.

15. The system of claim 13, wherein the system comprises a single computing node within which the file system is implemented.

16. A non-transitory computer-readable data storage medium to store a computer program that when executable by a processor causes a method to be performed, comprising:

creating a temporary record within a hash chain encompassing a record for a data file and corresponding to a location of the data file within a computer file system;

linking the temporary record within the hash chain so that the temporary record points to a before record to which the record for the data file points and to an after record to which the record for the data file points;

renaming the record for the data file with a new name; and

,

removing the temporary record from the hash chain,

wherein while the temporary record exists within the hash chain, look-ups of the data file resolve to the temporary record, such that the temporary record causes the look-ups to wait until the record for the data file has been renamed and the temporary record has been removed.

17. A non-transitory computer-readable data storage medium to store a computer program that when executable by a processor causes a method to be performed, comprising:

creating a temporary record within a hash chain encompassing a record for a data file and corresponding to a location of the data file within a computer file system;

linking the temporary record within the hash chain so that the temporary record points to a before record to which the record for the data file points and to an after record to which the record for the data file points;

moving the record for the data file to another hash chain corresponding to a new location of the data file within the computer file system; and

,

removing the temporary record from the hash chain,

wherein while the temporary record exists within the hash chain, look-ups of the data file resolve to the temporary record, such that the temporary record causes the look-ups to wait until the record for the data file has been moved and the temporary record removed.