Non-Mutating Tree-Structured File Identifiers

• US 20070168364A1
• Filed: 01/13/2006
• Published: 07/19/2007
• Est. Priority Date: 01/13/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John, Howell, Jonathan
• Granted Patent: US 7,574,457 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/164 File meta data generation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Non-mutating tree-structured file identifiers are used to identify files stored in a file system. Each of multiple files in the file system has a corresponding non-mutating file identifier, and these file identifiers are assigned and maintained using a tree structure.

Claims

1. One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computing device, cause the one or more processors to:

identify a plurality of files in a file system using a plurality of non-mutating file identifiers; and

maintain the plurality of non-mutating file identifiers in a tree structure.

2. One or more computer readable media as recited in claim 1, wherein the file system comprises a serverless distributed file system.

3. One or more computer readable media as recited in claim 1, wherein to maintain the plurality of non-mutating file identifiers is to maintain the plurality of non-mutating file identifiers across a plurality of computing devices, with different ones of the plurality of non-mutating file identifiers being stored on different ones of the plurality of computing devices.

4. One or more computer readable media as recited in claim 1, wherein each of the plurality of non-mutating file identifiers is a string of integers that is separate from a plurality of corresponding file path names, and wherein for at least some of the plurality of non-mutating file identifiers, links between each adjacent pair of integers in the string of integers represent different components in a file path name for the corresponding one of the plurality of files.

5. One or more computer readable media as recited in claim 4, wherein the plurality of instructions further cause the one or more processors to resolve which of the plurality of file path names corresponds to a particular one of the plurality of non-mutating file identifiers.

6. One or more computer readable media as recited in claim 1, wherein each of the plurality of non-mutating file identifiers is a string of integers, and for each of the plurality of non-mutating file identifiers, a parent file identifier in the tree structure for at least a portion of the file identifier can be determined by removing a last integer from the portion.

7. One or more computer readable media as recited in claim 1, wherein for each of the plurality of non-mutating file identifiers, a value x represents an integer that is a component of the non-mutating file identifier, a value n represents how many components make up the non-mutating file identifier, and the non-mutating file identifier has a structure of:

X₁.X₂.X₃ . . . X_n.

8. One or more computer readable media as recited in claim 1, wherein the plurality of instructions further cause the one or more processors to resolve which of a plurality of directory servers a particular non-mutating file identifier is managed by, and wherein the particular non-mutating file identifier is separate from a corresponding file path name.

9. One or more computer readable media as recited in claim 1, wherein the instructions further cause the one or more processors to:

identify each component of a non-mutating file identifier of the plurality of non-mutating file identifiers to be encoded;

encode each identified component; and

concatenate the encoded components to obtain an encoded file identifier.

10. One or more computer readable media as recited in claim 9, wherein to encode each identified component is to, for each identified component:

convert the component into a binary representation;

identify a number of bits in the binary representation;

decrement the number of bits by one to obtain an updated number of bits;

generate a string of 1'"'"'s having a length equal to the updated number of bits;

add a 0 to the end of the string of 1'"'"'s; and

add, after the 0, all of the bits of the binary representation except for a leading 1 in the binary representation.

11. A method comprising:

maintaining non-mutating file identifiers for a plurality of files in a file system; and

assigning file identifiers to the plurality of files in accordance with a tree structure.

12. A method as recited in claim 11, wherein each of the non-mutating file identifiers is a string of integers, and wherein for at least some of the non-mutating file identifiers, links between each adjacent pair of integers in the string of integers represent different components in a file path name for a corresponding one of the plurality of files.

13. A method as recited in claim 11, wherein each of the non-mutating file identifiers is a string of integers, and for each of the non-mutating file identifiers, a parent non-mutating file identifier in the tree structure for at least a portion of the non-mutating file identifier can be determined by removing a last integer from the portion.

14. A method as recited in claim 11, further comprising:

identifying each component of a non-mutating file identifier to be encoded;

encoding each identified component; and

concatenating the encoded components to obtain an encoded file identifier.

15. A method as recited in claim 11, further comprising:

resolving which of a plurality of directory servers in the file system one of the non-mutating file identifiers is managed by, wherein the one of the non-mutating file identifiers is separate from corresponding file path names in the file system.

16. One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computing device, cause the one or more processors to:

identify each component of a first non-mutating file identifier to be encoded;

encode each identified component; and

concatenate the encoded components to obtain a first encoded file identifier.

17. One or more computer readable media as recited in claim 16, wherein to encode each identified component is to, for each identified component:

convert the component into a binary representation;

identify a number of bits in the binary representation;

decrement the number of bits by one to obtain an updated number of bits;

generate a string of 1'"'"'s having a length equal to the updated number of bits;

add a 0 to the end of the string of 1'"'"'s; and

add, after the 0, all of the bits of the binary representation except for a leading 1 in the binary representation.

18. One or more computer readable media as recited in claim 16, wherein the instructions further cause the one or more processors to:

identify each encoded component in a second encoded file identifier;

decode each identified encoded component; and

generate a second non-mutating file identifier from the decoded components.

19. One or more computer readable media as recited in claim 18, wherein to decode each identified encoded component is to, for each identified encoded component:

generate a binary string by removing the leading 1'"'"'s and the first 0 from the identified encoded component; and

adding a leading 1 to the generated binary string.

20. One or more computer readable media as recited in claim 16, wherein a value x represents an integer that is a component of the first non-mutating file identifier, a value n represents how many components make up the first non-mutating file identifier, and the first non-mutating file identifier has a structure of:

X₁.X₂.X₃ . . . X_n.