Persistent indexing and free space management for flat directory

Patent metadata

Field	Value
Publication number	US-11630803-B2
Application number	US-202016906293-A
Country	US
Kind code	B2
Filing date	Jun 19, 2020
Priority date	Jul 13, 2016
Publication date	Apr 18, 2023
Grant date	Apr 18, 2023

Abstract

Methods, non-transitory computer readable media, computing devices and systems for persistent indexing and space management for flat directory include creating, using at least one of said at least one processors, an index file to store mapping information, computing, using at least one of said at least one processor, a hash based on a lookup filename, searching, using at least one of said at least one processor, the index file to find all matching directory cookies based on the computed hash, selecting, using at least one of said at least one processor, the directory entity associated with the lookup filename from among the matched directory cookies, and returning, using at least one of said at least one processor, the determined directory entity.

First claim

What is claimed is:

1. A method, comprising:
creating, by a processor, an index file associated with a flat directory used by a file system of a storage system to store data, the index file storing mapping information including a hash value based on a file name of each flat directory file and an associated indication of a storage location storing data for each flat directory file, the index file linked with a plurality of free space linked lists, each linked list representing different available storage location size based on a range of file name sizes supported by the file system;
computing, by the processor, a hash value based on a lookup filename;
searching, by the processor, the index file to find a matching directory entry based on the computed hash value;
selecting, by the processor, a storage location associated with the matching directory entry;
returning, by the processor, the determined directory entity;
identifying, by the processor, a free space linked list from the plurality of free space linked lists; and
selecting, by the processor, a storage location from the identified free space linked list to store data for a file name in the flat directory, the storage location linked to the index file.

2. The method of claim 1 , wherein the index file is stored in a B+ format.

3. The method of claim 1 , further comprising:
linking, by the processor, the index file to a first free storage location of each free space linked list.

4. The method of claim 1 , further comprising:
updating, by the processor, the index file if at least one of content stored in the flat directory is edited and new content is stored in the flat directory.

5. A computing device, comprising:
a memory comprising machine executable code for performing a method;
at least one processor coupled to the memory, the processor configured to execute the machine executable code to cause the processor to:
create an index file associated with a flat directory used by a file system to store data, the index file storing mapping information including a hash value of a filename of each flat directory file and an associated indication of a storage location storing data for each flat directory file, the index file linked with a plurality of free space linked lists, each linked list representing different available storage location size based on a range of file name sizes supported by the file system;
compute a hash value based on a lookup filename;
search the index file to find a matching directory entry based on the computed hash value;
select a storage location associated with the matching directory entry;
return the determined directory entity;
identify a free space linked list from the plurality of free space linked lists; and
select a storage location from the identified free space linked list to store data for a file name in the flat directory, the storage location linked to the index file.

6. The computing device of claim 5 , wherein the index file is stored in a B+ format.

7. The computing device of claim 5 , wherein the processor is further configured to execute the machine executable code to cause the processor to:
link the index file to a first free storage location of each free space linked list.

8. The computing device of claim 5 , wherein the processor is further configured to execute the machine executable code to cause the processor to:
update the index file if at least one of content stored in the flat directory is edited and new content is stored in the flat directory.

9. A non-transitory, machine readable storage medium having stored thereon instructions for performing a method, comprising machine executable code which when executed by at least one machine, causes the machine to:
create an index file associated with a flat directory used by a file system of a storage system to store data, the index file storing mapping information including a hash value of a filename of each flat directory file and an associated indication of a storage location storing data for each flat directory file, the index file linked with a plurality of free space linked lists, each linked list representing different available storage location size based on a range of file name sizes supported by the file system;
compute a hash value based on a lookup filename;
search the index file to find a matching directory entry based on the computed hash value;
select a storage location associated with the matching directory entry;
return the determined directory entity;
identify a free space linked list from the plurality of free space linked lists; and
select a storage location from the identified free space linked list to store data for a file name in the flat directory, the storage location linked to the index file.

10. The non-transitory storage medium of claim 9 , wherein the index file is stored in a B+ format.

11. The non-transitory storage medium of claim 9 , wherein the machine executable code further causes the machine to:
link the index file to a first free storage location of each free space linked list.

12. The non-transitory storage medium of claim 9 , wherein the machine executable code further causes the machine to:
update the index file if at least one of content stored in the flat directory is edited, and new content is stored in the flat directory.

13. The non-transitory storage medium of claim 9 , wherein a header of the index file links the index file to a free directory block for storing a flat directory entry.

14. The non-transitory storage medium of claim 9 , wherein the index file is separate from the file system executed by the storage system.

15. The non-transitory storage medium of claim 9 , wherein identify the free space linked list from the plurality of free space linked lists further comprises:
compute required free space for the file name to store data; and
utilize the required computed free space and the index file to select the free space linked list.

16. The method of claim 1 , further comprising:
utilizing, by the processor, a header of the index file to link the index file to a free directory block for storing a flat directory entry.

17. The method of claim 1 , wherein the index file is separate from the file system executed by the storage system.

18. The method of claim 1 , wherein identifying, by the processor, the free space linked list from the plurality of free space linked lists, further comprising:
computing, by the processor, required free space for the file name to store data; and
utilizing, by the processor, the required computed free space and the index file to select the free space linked list.

19. The computing device of claim 5 , wherein a header of the index file links the index file to a free directory block for storing a flat directory entry.

20. The computing device of claim 5 , wherein the index file is separate from the file system executed by the computing device.

Assignees

• Netapp Inc

Inventors

• Basrani Ravi

Classifications

• G06F16/152

  using file content signatures, e.g. hash values · CPC title

• G06F16/137 Primary

  Hash-based (content-based indexing of textual data G06F16/31) · CPC title

• G06F16/1727

  Details of free space management performed by the file system (saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064) · CPC title