US 9,779,015 B1Granted

Oversubscribed storage extents with on-demand page allocation

AssigneeAmazon Technologies, Inc.

InventorsMatti Juhani Oikarinen, Pradeep Vincent, Matteo Frigo

Life of this patent

Estimating the term…

Loading patent…

Abstract

In response to receiving a write request directed to a particular logical block of a storage object, a page of free space (sufficient to accommodate the payload of the write request, but smaller in size than the logical block) of a particular extent that has been selected to store contents of the logical block is allocated. The current size of the extent is smaller than the combined sizes of logical blocks that are mapped to the extent. The page is modified in accordance with a payload indicated in the write request. In response to a subsequent write request directed to the particular extent, a determination is made that the particular extent would violate a free space threshold criterion if the payload of the write request were accommodated, and an extent expansion operation is initiated.

Claims22

Dependent claims

A system, comprising:

one or more computing devices configured to:
designate a particular extent of a distributed multi-tenant storage service to store contents of a particular logical block of a storage object, wherein the particular extent is configured to store contents of a plurality of logical blocks of one or more storage objects including the particular logical block in accordance with a physical storage oversubscription policy;
in response to a first write request directed to the particular logical block, wherein the first write request indicates a first payload that is smaller than a size of the particular logical block,
allocate one or more pages of free space of the extent to the particular logical block to accommodate the first payload, wherein a combined size of the one or more pages is smaller than the size of the particular logical block;
and
modify the one or more pages in accordance with the first payload;
and
in response to a subsequent write request directed to the particular extent,
determine that the particular extent comprises insufficient free storage space to accommodate a second payload indicated in the subsequent write request without violating a free space threshold criterion associated with the oversubscription policy;
initiate an extent expansion operation;
and
prior to a completion of the extent expansion operation,
allocate at least one page of free space of the extent to accommodate the second payload;
and
modify the at least one page in accordance with the second payload.

12 more elements

A method, comprising:

performing, by one or more computing devices:
selecting a particular extent of a storage service to store contents of a particular logical block of a storage object, wherein the particular extent is designated to store contents of a plurality of logical blocks of one or more storage objects, wherein a combined size of the plurality of logical blocks exceeds a current size of the particular extent;
in response to receiving a particular write request directed to the particular logical block, indicating a first payload,
allocating one or more pages of free space of the extent to the particular logical block to accommodate the first payload;
and
modifying the one or more pages in accordance with the first payload;
and
in response to receiving a subsequent write request directed to the particular logical block,
determining that the particular extent comprises insufficient free storage space to accommodate a second payload indicated in the subsequent write request without violating a free space threshold criterion;
and
initiating an extent expansion operation;
and
prior to a completion of the extent expansion operation, allocating a page of free space of the extent to the particular logical block to accommodate the second payload.

10 more elements

A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors:

in response to receiving a particular write request directed to a particular logical block of a storage object,
allocate one or more pages of free space of a particular extent selected to store contents of the particular logical block to accommodate a particular payload indicated in the particular write request, wherein a current size of the particular extent exceeds a combined size of a plurality of logical blocks whose contents are mapped to the particular extent;
and
modify the one or more pages in accordance with the particular payload;
and
in response to receiving a subsequent write request directed to the particular extent,
determine that the particular extent comprises insufficient free storage space to accommodate a second payload indicated in the subsequent write request without violating a free space threshold criterion;
and
initiate an extent expansion operation;
and
prior to a completion of the extent expansion operation, allocating a page of free space of the extent to accommodate the second payload.

8 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/231,106Filed 31 Mar 2014
Granted: 3 Oct 2017
Term ends: Not estimatedThe source records don’t support an estimate.

Classification8 codes

G06F 12/02
Accessing, addressing or allocating within memory systems or architectures: addressing or allocation; Relocation
G06F 3/061
Specifically adapted to achieve a particular effect: improving I/O performance
G06F 3/0644
Organizing or formatting or addressing of data: management of space entities, e.g. partitions, extents, pools
G06F 3/067
Adopting a particular infrastructure: distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]