Systems and methods of directory entry encodings

• US 7,593,938 B2
• Filed: 12/22/2006
• Issued: 09/22/2009
• Est. Priority Date: 12/22/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Isilon Systems Incorporated (Dell Technologies Inc.)
• Inventors: Lemar, Eric M., White, Nathan N.
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Spieler; William
• Application Number:
  US11/645,216
• Publication Number:
  US 20080154978A1
• Time in Patent Office: 1,005 Days
• Field of Search: 707/101, 707/1, 707/2, 707/3, 707/6, 707/100, 715/703
• US Class Current: 1/1
• CPC Class Codes: G06F 16/166 File name conversion
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

In general, the invention relates to supporting multiple different character encodings in the same file system. In one embodiment, a method is provided for filename lookup that supports multiple character encodings. The method comprises storing filename data in a first character encoding into an indexed data structure. The method further comprises receiving filename data in a second encoding. The method also comprises looking up filename data in the indexed data structure using the second encoding.

Claims

1. A system for filename lookup that supports multiple character encodings, comprising:

a computer system comprising a processor, a memory accessible by the processor, an indexed data structure stored on the memory, and at least one executable software module stored on the memory, wherein the at least one executable software module is executed by the processor, and wherein the at least one executable software module is configured to;

receive a request from a first process to store a name into an indexed data structure, the name in a first character encoding;

convert the name in the first character encoding into a first key, the first key based on a standard character encoding;

store a data element associated with the first key into the indexed data structure, the data element comprising an encoding tag identifying the first character encoding, the byte values of the name in the first character encoding, and address data for locating file data associated with the name;

receive a request from a second process to retrieve the data element, the request comprising the name in a second character encoding;

convert the name in the second character encoding into a second key, the second key based on the standard character encoding;

retrieve at least the address data of a data element indexed by the second key, from the indexed data structure if there is a data element indexed by the second key; and

return at least the retrieved address data, if any, to the second process if there is a data element indexed by the second key.

2. The system of claim 1, wherein the byte values of the name in the first character encoding comprise byte sequences that do not represent valid characters in the standard character encoding.

3. The system of claim 1, wherein the at least one executable software module is further configured to store the indexed data structure in the memory of the computer system, the indexed data structure comprising one of the following:

b−

tree, binary tree, tree, b+tree, sorted tree, Patricia tries, red-black trees, and fiat-file directories.

4. The system of claim 1, wherein said conversions comprise electronically converting the name in said first character encoding or said second character encoding respectively into a converted name in said standard character encoding and applying a hash function to the converted name to produce said first key or said second key respectively, said first key and said second key both comprising the same hash value.

5. The system of claim 4, wherein said conversions further comprise regularizing the name before applying the hash function, the regularizing comprising one or more of the following:

removing one or more problem characters, replacing one or more problem characters with one or more default characters, converting characters to a shared case, and normalizing.

6. The system of claim 4, wherein said retrieval of at least the address data of the data element comprises:

accessing a hash bucket associated with said hash value, the hash bucket comprising one or more data elements, each of the one or more data elements comprising an encoding tag identifying an associated character encoding, associated byte values, and associated address data;

while no exact match is found, for each one of the one or more data elements which has an associated character encoding different from said second character encoding, converting the associated byte values from the associated character encoding into a converted name in the second character encoding and comparing the converted name in the second character encoding to said name in the second character encoding, and for each one of the one or more data elements which has an associated character encoding equivalent to said second character encoding, comparing the associated byte values with said name in the second character encoding;

while no exact match is found, remembering the best matched data element;

if an exact match is found, retrieving at least the address data of the data element associated with the exact match; and

if no exact match is found, retrieving at least the address data of the data element associated with the best matched data element.

7. The system of claim 1, wherein the at least one executable software module is further configured to infer said first character encoding from a first configurable setting associated with said first process and infer said second character encoding from a second configurable setting associated with said second process.

8. The system of claim 1, wherein said name is a filename.

9. The system of claim 1, wherein said name is a directory name.

10. The system of claim 1, wherein the indexed data structure corresponds to a directory structure in a file system, the indexed data structure comprising multiple data elements, the data elements corresponding to files and directories in the directory structure.

11. The system of claim 1, wherein the at least one executable software module is further configured to indicate to the second process that no match is found if there is no data element indexed by the second key.

14. The method of claim 1, wherein the indexed data structure is one of the following:

b−

tree, binary tree, tree, b+tree, sorted tree, Patricia tries, red-black trees, and flat-file directories.

12. A method for filename lookup that supports multiple character encodings, comprising:

storing, on a computer system, an indexed data structure, the computer system comprising a processor and memory;

receiving, at the computer system, a request from a first process to store a name into an indexed data structure, the name in a first character encoding;

converting, by the computer system, the name in the first character encoding into a first converted name in a standard character encoding;

converting, by the computer system, the first converted name in the standard character encoding into a first key;

storing a data element associated with the first key into the indexed data structure, the data element comprising an encoding tag identifying the first character encoding, the byte values of the name in the first character encoding, and address data for locating file data associated with the name;

receiving a request, by the computer system, from a second process to retrieve the data element, the request comprising the name in a second character encoding;

converting, by the computer system, the name in the second character encoding into a second converted name in a standard character encoding;

converting, by the computer system, the second converted name in the standard character encoding into a second key;

determining, by the computer system, whether one or more data elements within the indexed data structure correspond to the second key;

if it is determined that one or more data elements within the indexed data structure correspond to the second key;

traversing, by the computer system, one or more data elements within the indexed data structure that correspond to the second key;

comparing, by the computer system, the name to the one or more data elements that correspond to the second key;

determining, by the computer system, an exact match, if any, between the one or more data elements that correspond to the second key and the name;

if an exact match is determined, returning, by the computer system, the data associated with the exact matched data element to the second process, otherwise if an exact match is not determined, determining, by the computer system, the best match between the one or more data elements that correspond to the second key and the name; and

returning, by the computer system, data associated with the best matched data element to the second process.

13. The method of claim 12, wherein said converting the first converted name in the standard character encoding comprises regularizing the first converted name according to one or more of the following:

removing one or more problem characters, replacing one or more problem characters with one or more default characters, converting characters to a shared case, and normalizing.

15. The method of claim 12, wherein the one or more data elements that correspond to the second key comprise an associated character encoding and associated byte values, and said comparing comprises converting the associated byte values from the associated character encoding to the second character encoding.

16. The method of claim 12, wherein the computer system is a distributed computer system operating on a cluster of computer nodes.

17. The method of claim 12, further comprising inferring said first character encoding from a first configurable setting associated with said first process and inferring said second character encoding from a second configurable setting associated with said second process.

18. The method of claim 12, further comprising, if there is a best matched data element and the address data in said best matched data element addresses directory data, identifying one or more filenames associated with said directory data and converting the one or more filenames to one or more converted filenames in the second character encoding;

and wherein said returning comprises returning the one or more converted filenames to the second process.

19. The method of claim 18, wherein converting the one or more filenames comprises converting one or more characters that are untranslatable to the second character encoding into one or more standard replacement characters.

20. The method of claim 12, wherein said converting the second converted name in the standard character encoding comprises regularizing the second converted name according to one or more of the following:

removing one or more problem characters, replacing one or more problem characters with one or more default characters, converting characters to a shared case, and normalizing.

21. The method of claim 12, wherein said converting the first converted name in the standard character encoding comprises regularizing the first converted name according to one or more of the following:

removing one or more problem characters, replacing one or more problem characters with one or more default characters, converting characters to a shared case, and normalizing, and

wherein said converting the second converted name in the standard character encoding comprises regularizing the second converted name according to one or more of the following;

removing one or more problem characters, replacing one or more problem characters with one or more default characters, converting characters to a shared case, and normalizing.

22. The method of claim 12, further comprising:

returning, by the computer system, an indication that no match is found if it is determined that no data elements within the indexed data structure correspond to the second key.