Persistent indexing and free space management for flat directory

Patent metadata

Field	Value
Publication number	US-10733144-B2
Application number	US-201615208956-A
Country	US
Kind code	B2
Filing date	Jul 13, 2016
Priority date	Jul 13, 2016
Publication date	Aug 4, 2020
Grant date	Aug 4, 2020

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:
maintaining by a processor of a storage system, an index file for a plurality of free space linked lists, the index file indicating a different storage location size associated with each free space linked list of available free space storage locations to store data using a flat directory by a file system of the storage system;
wherein different storage location size is based on a range of file name sizes supported by the file system;
linking by the processor, the index file to the available free space storage locations by pointing a starting node, in the index file, of each free space linked list to a first free storage location of each free space linked list;
computing by the processor, required free space for a file name to store data for the file name using the flat directory;
utilizing by the processor, the required computed free space and the index file to select a free space linked list from the plurality of free space linked lists;
storing by the processor, the data in a first free storage location of the selected free space linked list;
updating by the processor, the selected free space linked list by replacing in a starting node of the selected free space linked list, a first pointer to the first free storage location by a second pointer to a second free storage location of the selected free space linked list, indicating that the second free slot is a next available free storage location of the selected free space linked list; wherein the first pointer is stored in a header of the index file; and
updating by the processor, the header of the index file to replace the first pointer by the second pointer.

2. The method of claim 1 , wherein the file name to store data is provided by an application communicating with the storage system.

3. The method of claim 1 , further comprising: utilizing by the processor, the index file to map a hash value of the file name to a location cookie providing storage location for the file name, the hash value identifying the storage location for a lookup operation associated with the file name.

4. The method of claim 1 , wherein the index file is separate from the file system.

5. The method of claim 1 , further comprising: prior to the updating of the selected free space linked list, storing the second pointer to the second free storage location slot in the first free storage location.

6. The method of claim 1 , further comprising: removing the index file by the processor, for using a different version of the file system without changing content of the flat directory.

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

8. A computing device, comprising:
a memory comprising machine executable code for performing a method; and
a processor coupled to the memory; the processor configured to execute the machine executable code to cause the processor to:
maintain an index file for a plurality of free space linked lists, the index file indicating a different storage location size associated with each free space linked list of available free space storage locations to store data using a flat directory by a file system of the storage system; wherein different storage location size is based on a range of file name sizes supported by the file system;
link the index file to the available free space storage locations by pointing a starting node, in the index file, of each free space linked list to a first free storage location of each free space linked list;
search the index file to select a free space linked list from among the plurality of free space linked lists, based on free space required to store data for a file name;
store the data in a first free storage location of the selected free space linked list;
update the selected free space linked list by replacing in a starting node of the selected free space linked list, a first pointer to the first free storage location by a second pointer to a second free storage location of the selected free space linked list, indicating that the second free slot is a next available free storage location of the selected free space linked list; wherein the first pointer is stored in a header of the index file; and
update the header of the index file to replace the first pointer by the second pointer.

9. The computing device of claim 8 , wherein the file name to store data is provided by an application communicating with the storage system.

10. The computing device of claim 8 , wherein the index file maps a hash value of the file name to a location cookie providing storage location for the file name, the hash value used to identify the storage location for a lookup operation associated with the file name.

11. The computing device of claim 8 , wherein the index file is separate from the file system.

12. The computing device of claim 8 , wherein prior to the update of the selected free space linked list, the second pointer is stored in the first free storage location.

13. The computing device of claim 8 , wherein the processor is further configured to execute the machine executable code to cause the processor to: remove the index file for using a different version of the file system without changing content of the flat directory.

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

15. 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:
maintain an index file for a plurality of free space linked lists, the index file indicating a different storage location size associated with each free space linked list of available free space storage locations to store data using a flat directory by a file system of the storage system;
wherein the different storage location size is based on a range of file name sizes supported by the file system;
link the index file to the available free space storage locations by pointing a starting node, in the index file, of each free space linked list to a first free storage location of each free space linked list;
compute required free space for a filename to store data for the file name using the flat directory;
search the index file to select a free space linked list from the plurality of free space linked lists, based on the computed required free space;
store data in a first free storage location of the selected free space linked list;
update the selected free space linked list by replacing in a starting node of the selected free space linked list, a first pointer to the first free storage location by a second pointer to a second free storage location of the selected free space linked list, indicating that the second free slot is a next available free storage location of the selected free space linked list; wherein the first pointer is stored in a header of the index file; and
update the header of the index file to replace the first pointer by the second pointer.

16. The non-transitory machine readable storage medium of claim 15 , wherein the file name to store data is provided by an application communicating with the storage system.

17. The non-transitory, machine readable storage medium of claim 15 , wherein the index file is separate from the file system.

18. The non-transitory machine readable storage medium of claim 15 , wherein the index file maps a hash value of the file name to a location cookie providing storage location for the file name, the hash value used to identify the storage

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