Systems and methods of directory entry encodings

• US 20080154978A1
• Filed: 12/22/2006
• Published: 06/26/2008
• 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.
• Granted Patent: US 7,593,938 B2
• Time in Patent Office: Days
• US Class Current: 707/201
• 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 module configured to;

store filename data in a first character encoding into an indexed data structure;

receive filename data in a second encoding; and

lookup filename data in the indexed data structure using the second encoding.

2. The system of claim 1, wherein the module is configured to store and to lookup filename data in a plurality of character encodings.

3. The system of claim 1, wherein the filename data may include byte sequences that do not represent valid characters in the first character encoding.

4. The system of claim 1, wherein a module configured to lookup filename data in the indexed data structure comprises a module configured to lookup filename data in the indexed data structure with O(log n) efficiency.

5. The system 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.

6. The system of claim 1, wherein the filename data received in the first character encoding is stored in the indexed data structure as originally provided by a user and wherein the filename data is indexed in the indexed data structure based on a converted value derived by the conversion of the filename data to a standard character encoding.

7. The system of claim 6, wherein a hash function is applied to the converted value and the resulting hash value is an index for the indexed data structure.

8. The system of claim 7, wherein the indexed value is regularized before applying the hash function, and wherein being regularized comprises at least one of the following:

converting to a standard character encoding, removing problem characters, and normalizing.

9. The system of claim 8, wherein being regularized further comprises converting lowercase and uppercase versions of characters to a shared case.

10. The system of claim 1, wherein the character encoding comprises one of the following:

Latin-1, UTF-8, UTF-8-MAC, EUC-JP, EUC-JP-MS, SHIFT-JIS, and ASCII.

11. A file system with filename lookup that supports multiple character encodings, comprising:

an indexed data structure indexed by a value based on a first character encoding, said indexed data structure comprising a plurality of entries corresponding to respective filenames in the file system, said entries comprising an encoding tag identifying a respective second character encoding and a filename stored in the respective second character encoding.

12. The system of claim 11, wherein said respective second character encoding is different for respective entries of said plurality of entries.

13. The system of claim 11, wherein said indexed data structure is an indexed data structure that allows lookup with O(log n) efficiency.

14. The system of claim 11, 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.

15. The system of claim 11, wherein the indexed data structure indexed by the value based on the first character encoding comprises an indexed data structure indexed by a hash value resulting from applying data represented in the first character encoding to a hash function.

16. The system of claim 15, wherein the indexed value is regularized before applying the hash function, and wherein being regularized comprises at least one of the following:

converting to the first character encoding, removing problem characters, converting to uppercase, and normalizing.

17. The system of claim 11, wherein the first character encoding comprises one of the following:

Latin-1, UTF-8, UTF-8-MAC, EUC-JP, EUC-JP-MS, SHIFT-JIS, and ASCII.

18. The system of claim 11, wherein the file system is a distributed system operating on a cluster of computer nodes.

19. The system of claim 11, wherein the second character encoding is an encoding that may be inferred from a particular access mechanism, including at least one of the following:

NFS, CIFS, FTP, HTTP, and WebDAV.

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

converting a filename from an encoding of a requester to a hashed value based on a standard encoding;

navigating to entries within an indexed data structure that correspond to the hashed value;

for the entries that correspond to the hashed value, comparing filename data stored in the entries to the filename; and

determining the best match filename, if any, between the filenames stored in the entries and the filename.

21. The system of claim 20, wherein navigating to entries within an indexed data structure comprises navigating with O(log n) efficiency.

22. The method of claim 20, wherein the converting a filename from an encoding of a requester to a hashed value further comprises regularizing the filename according to at least one of the following:

converting to the standard character encoding, removing problem characters, converting to uppercase, and normalizing.

23. The method of claim 20, wherein the indexed data structure is one of the following:

b-tree, binary tree, tree, and b+tree.

24. The method of claim 20, wherein the encoding of the requester is one of the following:

Latin-1, UTF-8, UTF-8-MAC, EUC-JP, EUC-JP-MS, SHIFT-JIS, and ASCII.

25. The method of claim 20, wherein comparing filename data stored in the entries to the filename comprises converting the filename data to the encoding of the requester.

26. The method of claim 20, wherein the file system is a distributed system operating on a cluster of computer nodes.

27. The method of claim 20, wherein the native encoding is an encoding that may be inferred from a particular access mechanism, including at least one of the following:

NFS CIFS, FTP, HTTP, and WebDAV.

28. The method of claim 20, further comprising, if there is a best match filename, listing the contents of the best match filename, wherein listing the contents comprises identifying an indexed data structure associated with the best match filename and converting the filenames in the indexed data structure associated with the best match filename to the encoding of the requester.

29. The method of claim 28, wherein converting the filenames in the indexed data structure associated with the best match filename to the encoding of the requester comprises converting characters that are untranslatable to the encoding of the requester into a standard replacement character.