Deallocating portions of provisioned data storage based on defined bit patterns indicative of invalid data

Patent metadata

Field	Value
Publication number	US-9606909-B1
Application number	US-201313857967-A
Country	US
Kind code	B1
Filing date	Apr 5, 2013
Priority date	Apr 5, 2013
Publication date	Mar 28, 2017
Grant date	Mar 28, 2017

Abstract

Systems and methods are disclosed which facilitate management of thin provisioned data storage. Specifically, portions of thinly provisioned data stores may be deallocated when they contain invalid data, such as data deleted by a user. A user may transmit notifications, which may include write requests corresponding to a defined bit pattern, to a provider of the data store (or to the data store itself) that data has been deleted. A management component may modify the data store, or metadata corresponding to the data store, to reflect the deletion. The management component may further monitor portions of the data store to determine whether individual portions contain entirely invalid data. If so, the portion may be deallocated from the thin provisioned data store, resulting in more efficient thin provisioning. Deallocation may be enabled even where deletion notifications from a user do not correspond directly to allocated storage portions.

First claim

What is claimed is:

1. A system for managing provisioned data stores, the system comprising:
one or more physical storage devices configured to provide a virtual data store accessible to a user computing device, wherein the virtual data store is associated with a reported capacity greater than an actual capacity allocated to the virtual data store, and wherein the actual capacity allocated to the virtual data store comprises a set of allocated portions of the one or more physical storage devices, wherein each allocated portion comprises a plurality of individually addressable data blocks, each individually addressable data block being writable independently from other individually addressable data blocks;
one or more processors implementing a storage management component, said one or more processors configured to:
receive a first request from the user computing device to write data to a first individually addressable data block of the virtual data store, wherein the data requested to be written corresponds to a defined bit pattern indicative of invalid data, and wherein the first individually addressable data block corresponds to a first allocated portion of the set of allocated portions;
write the defined bit pattern to the first individually addressable data block as an indicator that the first individually addressable data block contains only invalid data;
determine, based at least in part on data within the first allocated portion, that the first allocated portion does not contain only invalid data at least partly by determining that the first allocated portion includes both the first individually addressable data block that contains only invalid data and a second individually addressable data block that does not contain only invalid data;
in response to determining that the first allocated portion does not contain only invalid data, decline to deallocate the first allocated portion;
receive a second request from the user computing device, the second request requesting that the defined bit pattern be written to the second individually addressable data block within the first allocated portion;
write the defined bit pattern to the second individually addressable data block as an indicator that the second individually addressable data block contains only invalid data;
determine that the first allocated portion contains only invalid data based at least in part on existence of the defined bit pattern within the first and second individually addressable data blocks; and
deallocate the first allocated portion, wherein deallocation reduces the actual capacity allocated to the virtual data store.

2. The system of claim 1 , wherein the one or more processors implementing a storage management component are further configured to allocate additional portions to the virtual data store in response to a write request that may not be fulfilled by portions currently allocated to the virtual data store.

3. The system of claim 1 , wherein the one or more processors are further configured to, in response to deallocation of the first allocated portion, generate a deallocation indicator associated with the first allocated portion and indicative of the defined bit pattern.

4. The system of claim 3 , wherein the one or more processors are further configured to:
subsequent to deallocation of the first allocated portion, receive a request from the user computing device to read data from the first allocated portion;
generate the data requested to be read based at least in part on the deallocation indicator; and
transmit the generated data to the user computing device.

5. A computer-implemented method for managing provisioned data stores, the computer-implemented method comprising:
allocating one or more portions of a storage device to a user computing device, wherein said allocating enables the user computing device to write to and read from the one or more portions, wherein each portion includes a plurality of individually addressable data blocks, each of the individually addressable data blocks being writable by the user computing device independently from other individually addressable data blocks;
receiving a first request from the user computing device to write data to a first individually addressable data block of a first portion within the one or more portions, wherein the data requested to be written corresponds to a defined bit pattern indicative of invalid data;
storing an indicator that the first individually addressable data block contains only invalid data;
declining to deallocate the first portion in response to the first individually addressable data block containing only invalid data, based at least in part on detecting that the first portion includes a second individually addressable data block that does not contain only invalid data;
receiving a second request from the user computing device, the second request requesting to write the defined bit pattern to the second individually addressable data block of the first portion;
storing an indicator that the second individually addressable data block contains only invalid data;
determining, based at least in part on the indicators that the first individually addressable data block and the second individually addressable data block contain only invalid data, that the first portion contains only invalid data; and
deallocating the first portion from the user computing device.

6. The computer-implemented method of claim 5 , wherein storing the indicator that the first individually addressable data block contains only invalid data comprises writing the defined bit pattern to the first individually addressable data block.

7. The computer-implemented method of claim 6 , wherein determining that the first portion contains only invalid data comprises detecting that the first portion includes only blocks storing the defined bit pattern.

8. The computer-implemented method of claim 5 , wherein storing the indicator that the first individually addressable data block contains only invalid data comprises modifying metadata associated with the first individually addressable data block.

9. The computer-implemented method of claim 8 , wherein determining that the first portion contains only invalid data comprises reading the metadata associated with the individually addressable data blocks of the first portion.

10. The computer-implemented method of claim 8 , wherein determining that the first portion contains only invalid data comprises both reading the metadata associated with the individually addressable data blocks of the first portion and detecting that the first portion includes at least one individually addressable data block storing the defined bit pattern.

11. A non-transitory, computer-readable medium containing computer-executable instructions for managing provisioned data stores, the computer-executable instructions comprising:
first computer-executable instructions that, when executed by a processor, cause the processor to enable a user computing device to allocate one or more portions of a storage device to the user computing device, wherein each portion comprises a plurality of individually addressable data blocks, each of the individually addressable data blocks being writable by the user computing device independently from other individually addressable data blocks;
second computer-executable instructions that, when executed by the processor, cause the processor to:
receive a first request from the user computing device to write data to a first individually addressable data block of a first portion within the one or more portions, wherein the data requested to be written corresponds to a defined bit pattern indicative of invalid data;
store

Assignees

• Amazon Tech Inc

Inventors

• Vincent Pradeep

Classifications

• G06F12/0253

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title

• G06F2212/1056

  Simplification · CPC title

• G06F3/0652

  Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket · CPC title

• G06F3/0665

  at area level, e.g. provisioning of virtual or logical volumes · CPC title

• G06F2212/7205

  Cleaning, compaction, garbage collection, erase control · CPC title