Data storage system with window allocation using window cache

Patent metadata

Field	Value
Publication number	US-9612754-B1
Application number	US-201514753476-A
Country	US
Kind code	B1
Filing date	Jun 29, 2015
Priority date	Jun 29, 2015
Publication date	Apr 4, 2017
Grant date	Apr 4, 2017

Abstract

A method of operating a data storage system includes writing the file system data as sequential data and non-sequential data to a storage volume, the sequential data being stored in windows each having a predetermined number of consecutive data blocks and being allocated dynamically as the sequential data is written. The method includes maintaining and using a window cache to identify existing windows for storing respective newly written sequential file system data in sequence with respective earlier-written file system data for which the existing windows were previously allocated, the window cache including a set of entries indexed by an identifier of (1) a file of the file system and (2) a window-size region of the file to which sequential data is being written, the entries including respective physical window addresses identifying respective ones of the existing windows and being obtained by lookup operations using respective values of the identifier.

First claim

What is claimed is:

1. A method of operating a data storage system to write file system data of an internal file system to an underlying storage volume, comprising:
writing the file system data as sequential data and non-sequential data to the storage volume, the sequential data being stored in windows each having a predetermined number of consecutive data blocks and being allocated dynamically as the sequential data is written; and
maintaining and using a window cache to identify existing windows for storing respective newly written sequential file system data in sequence with respective earlier-written file system data for which the existing windows were previously allocated, the window cache including a set of entries indexed by an identifier of (1) a file of the file system and (2) a window-size region of the file to which sequential data is being written, the entries including respective physical window addresses identifying respective ones of the existing windows and being obtained by lookup operations using respective values of the identifier.

2. The method of claim 1 , wherein the window cache includes a hash table of entries indexed by a hash value as the identifier of the file and the window-size region, and wherein the method further includes applying a hash function to a key to generate the hash value.

3. The method of claim 2 , wherein the key includes an inode number for the file and a window address for the window-size region.

4. The method of claim 1 , wherein maintaining and using the window cache includes, for a write operation for sequential data:
performing an atomic lookup/insert in the window cache to locate window information, the lookup using a lookup key including an identifier of a logical window area of a file being written to;
if the lookup/insert obtains a valid entry for the logical window, then returning block information stored in the entry and adjusting block preference information according to an offset within the logical window;
if the lookup/insert does not obtain a valid entry for the logical window, then performing a new allocation for the write operation and storing a corresponding new entry in the window cache for use in subsequent lookups.

5. The method of claim 4 , wherein storing a corresponding new entry includes:
first inserting an incomplete new entry marked as initializing;
while the entry is marked as initializing, blocking to temporarily prevent new lookups potentially involving the new entry;
upon completing allocation of a new window for the write operation, (1) updating the new entry with the new window information and marking the entry as not initializing, and (2) unblocking to allow the new lookups to proceed.

6. The method of claim 1 , wherein the window cache stores entries for a plurality of file systems and logical units of storage (LUNs) of the data storage system, and wherein the identifier indexing the entries is also an identifier of (3) the file system including the file to which the sequential data is being written.

7. The method of claim 6 , wherein the window cache is sized based on a first predetermined number of entries per LUN and a second predetermined number of LUNs of the data storage system, and further including use of a least recently used replacement mechanism to age entries for replacement by new entries as operation progresses.

8. The method of claim 1 , wherein each entry includes respective values of a set of fields including a block index field, a state field, a condition field, a lock field, and a window address field, and wherein:
a block index value is an index within a logical window where an allocated block exists;
a state value indicates operating state of the entry selected from Initializing, Valid, Invalid, and No Window;
a condition value is a variable used for synchronizing allocation operations;
a lock value is a variable used for synchronizing accesses and updates to the entry; and
a window address value is an address of a physical window.

9. The method of claim 1 , wherein maintaining and using the window cache includes respective operations for an out-of-windows condition, block relocation, window cache purging, and block remapping for defragmentation, and wherein:
for the out-of-windows condition, ceasing using existing window information of the window cache that may refer to windows whose entire space has been allocated, and updating or replacing the existing window information;
for block relocation operation, purging an entry for an affected block from the window cache;
for window cache purging operation, (a) purging all entries for a file system upon remounting of the file system, and (b) purging all entries for a LUN upon deletion of the LUN; and
for block remapping operation, examining the window cache for an entry similar to an entry that would be used for a new window allocation for an affected block.

10. The method of claim 1 , wherein the sequential data is being written by a set of multiple execution threads operating in parallel on different parts of a sequential stream and data blocks are written sufficiently out of address order that the nearness threshold is not met for some writes only because other writes by other execution threads have not yet occurred.

11. A data storage system including processing circuitry, physical storage devices, and interface circuitry coupling the processing circuitry to the physical storage devices, the processing circuitry storing and executing computer program instructions to cause the data storage system to realize a storage volume and associated internal file system, the storage volume realized using physical storage of the physical storage devices, the file system being configured and operative to:
write file system data as sequential data and non-sequential data to the storage volume, the sequential data being stored in windows each having a predetermined number of consecutive data blocks and being allocated dynamically as the sequential data is written; and
maintain and use a window cache to identify existing windows for storing respective newly written sequential file system data in sequence with respective earlier-written file system data for which the existing windows were previously allocated, the window cache including a set of entries indexed by an identifier of (1) a file of the file system and (2) a window-size region of the file to which sequential data is being written, the entries including respective physical window addresses identifying respective ones of the existing windows and being obtained by lookup operations using respective values of the identifier.

12. The data storage system of claim 11 , wherein the window cache includes a hash table of entries indexed by a hash value as the identifier of the file and the window-size region, and wherein the method further includes applying a hash function to a key to generate the hash value.

13. The data storage system of claim 12 , wherein the key includes an inode number for the file and a window address for the window-size region.

14. The data storage system of claim 11 , wherein maintaining and using the window cache includes, for a write operation for sequential data:
performing an atomic lookup/insert in the window cache to locate window information, the lookup using a lookup key including an identifier of a logical window area of a file being written to;
if the lookup/insert obtains a valid entry for the logical window, then returning block information stored in the entry and adjusting block preference information according to an offset within the logical window;
if the lookup/insert does not obtain a valid entry

Assignees

• Emc Corp
• Emc Ip Holding Co Llc

Inventors

• Delgado Diane M
• Armangau Philippe
• Rashid Ahsan

Classifications

• G06F3/0673

  Single storage device · CPC title

• G06F3/0611 Primary

  in relation to response time · CPC title

• G06F3/0656

  Data buffering arrangements · CPC title

• G06F2212/604

  Details relating to cache allocation · CPC title

• G06F12/023

  Free address space management · CPC title