Allocating space in a file system from sequential and random cursors

Patent metadata

Field	Value
Publication number	US-9703498-B1
Application number	US-201514753375-A
Country	US
Kind code	B1
Filing date	Jun 29, 2015
Priority date	Jun 29, 2015
Publication date	Jul 11, 2017
Grant date	Jul 11, 2017

Abstract

A technique for storage allocation provides a first cursor and a second cursor from which to allocate blocks within a physical address space of a file system. The file system uses the first cursor for allocating blocks for writes directed to sequential logical addresses and uses the second cursor for writes directed to random (non-sequential) logical addresses.

First claim

What is claimed is:

1. A method of storing data in a file system of a data storage system, the method comprising:
receiving write requests specifying data to be written to the file system at designated logical addresses of one or more files in the file system, the data specified in the write requests including a first set of data to be written at sequential logical addresses and a second set of data to be written at non-sequential logical addresses;
allocating storage for the first set of data from a first cursor, the first cursor (i) pointing to a first window of contiguous physical addresses in a physical address space of the file system and (ii) designating the first window exclusively for sequential data; and
allocating storage for the second set of data from a second cursor, the second cursor (i) pointing to a second window of contiguous physical addresses in the physical address space of the file system and (ii) designating the second window exclusively for non-sequential data.

2. The method of claim 1 ,
wherein the first window is disposed in a first region of the file system, the first region including multiple windows, and
wherein the second window is disposed in a second region of the file system, the second region including multiple windows, each of the windows in the first region and the second region having multiple allocation units.

3. The method of claim 2 , wherein the data specified in the write requests further includes a third set of data to be written at sequential logical addresses different from those to which the first set of data are directed, and wherein the method further comprises, prior to completing the act of allocating storage for the first set of data:
moving the first cursor to a third window of physical addresses, the third window being a next free window of physical addresses in the first region; and
initiating allocation of storage for the third set of data in the third window while still allocating storage for the first set of data in the first window.

4. The method of claim 2 , wherein the method further comprises, prior to completing the act of allocating storage for the first set of data:
moving the first cursor to a next free window of physical addresses in the first region; and
continuing to allocate storage for the first set of data in the first window after moving the first cursor to the next free window.

5. The method of claim 3 , wherein allocating storage for the second set of data includes:
allocating a first allocation unit of storage at the second cursor for accommodating a first portion of the second set of data;
moving the second cursor to a second allocation unit within the second window;
allocating the second allocation unit for accommodating a second portion of the second set of data; and
continuing to move the second cursor and to allocate allocation units in the second window for accommodating additional portions of the second set of data until all allocation units in the second window have been allocated.

6. The method of claim 5 , wherein the data specified by the write requests includes additional non-sequential data and wherein the method further comprises:
allocating one allocation unit at a time in a single direction through an additional window of physical addresses for accommodating the additional, non-sequential data while advancing the second cursor by one allocation unit at a time each time an allocation unit in the additional window is allocated;
in response to the second cursor advancing to an allocation unit in the additional window that has already been allocated, abandoning allocation of the additional non-sequential data in the additional window and advancing the second cursor to a new window of physical addresses; and
proceeding to allocate allocation units in the new window to accommodate a remaining portion of the additional non-sequential data.

7. The method of claim 5 , wherein the first cursor moves in one direction only through the physical address space of the file system, and
wherein, upon allocation being performed on a last free window of physical addresses in the first region, the method further comprises moving the first cursor to a third region of the file system, the third region including multiple windows of physical addresses each having multiple allocation units of storage, wherein at least one of the windows in the third region is free.

8. The method of claim 7 , wherein the second cursor moves in one direction only through the physical address space of the file system, and
wherein, upon allocation being performed on a last free allocation unit in the second region, the method further comprises moving the second cursor to a fourth region of the file system, the fourth region including multiple windows of physical addresses each having multiple allocation units of storage, wherein at least one of the windows in the fourth region is free.

9. The method of claim 8 , further comprising maintaining a main cursor, the main cursor indicating an earliest region in the physical address space of the file system that includes at least one free window.

10. The method of claim 9 , wherein the method further comprises, upon performing sequential allocation on a last free window available for sequential allocation in the physical address space of the file system, moving the first cursor to an earliest free window in the earliest region of the file system pointed-to by the main cursor.

11. The method of claim 9 , wherein the method further comprises, upon performing random allocation on a last free window available for non-sequential allocation of physical addresses in the physical address space of the file system, moving the second cursor to an earliest free window of physical address in the earliest region of the file system pointed-to by the main cursor.

12. The method of claim 5 , further comprising setting a next cursor to indicate a next free region having at least one free window in the physical address space of the file system.

13. The method of claim 5 , further comprising maintaining an allocation tree of physical addresses in the file system, the allocation tree having at least a first level of nodes representing respective regions and a second level of nodes representing respective groups of regions,
wherein for each node there is provided at least one of (i) a value indicating whether the portion of the file system address space aggregated under that node has any free windows and (ii) a value indicating a count of free windows aggregated under that node.

14. The method of claim 1 , further comprising storing data of file system in multiple disk drives.

15. The method of claim 14 , wherein the multiple disk drives that store the data of the file system are arranged in a set of RAID (Redundant Array of Independent Disks) groups.

16. A data storage system, comprising control circuitry that includes a set of processing units coupled to memory, the control circuitry constructed and arranged to:
receive write requests specifying data to be written to the file system at designated logical addresses of one or more files in the file system, the data specified in the write requests including a first set of data to be written at sequential logical addresses and a second set of data to be written at non-sequential logical addresses;
allocate storage for the first set of data from a first cursor, the first cursor (i) pointing to a first window of contiguous physical addresses in a physical address space of the file system and (ii) designating the first window exclusively for sequential data; and
allo

Assignees

• Emc Ip Holding Co Llc

Inventors

• Armangau Philippe
• Zhang Feng
• Rashid Ahsan
• Chawla Rohit
• Pan Hao
• Delgado Diane M

Classifications

• G06F3/065 Primary

  Replication mechanisms · CPC title

• G06F3/0631 Primary

  by allocating resources to storage systems · CPC title

• G06F3/0643

  Management of files · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/0619 Primary

  in relation to data integrity, e.g. data losses, bit errors · CPC title