Storage allocation techniques for large writes using list formed from each block

Patent metadata

Field	Value
Publication number	US-12517671-B2
Application number	US-202418731828-A
Country	US
Kind code	B2
Filing date	Jun 3, 2024
Priority date	Jan 6, 2023
Publication date	Jan 6, 2026
Grant date	Jan 6, 2026

Abstract

Techniques of the present disclosure can include: identifying blocks of storage available for allocation; generating a list denoting an allocation order of storage chunks of the blocks; receiving a write I/O operation that writes data to a first logical address; allocating a storage chunk in accordance with the allocation order of the list, wherein a first block includes the storage chunk and a second storage chunk; storing the first data in the storage chunk of the first block; removing the second storage chunk from the list; and creating a mapping between the first logical address and the first block indicating the second storage chunk is reserved for storing content written to a logical address included in a volume logical address range comprising the first logical address. The allocation order can spread allocation distance between blocks and chunks of the same block to avoid contention during flushes.

First claim

What is claimed is:

1 . A computer-implemented method comprising:
identifying a plurality of blocks of storage available for allocation, wherein each of the plurality of blocks is partitioned into N storage chunks; generating a main list denoting an allocation order of a first plurality of storage chunks, including:
forming N sets of lists, wherein each of the N sets of lists identifies corresponding ones of the N storage chunks from each of the blocks of the plurality of blocks, wherein a first set of the N sets of lists includes a first storage chunks of the N storage chunks from each of the plurality of blocks, and wherein a second set of the N sets of lists includes a second storage chunks of the N storage chunks from each of the plurality of blocks;
receiving a first write I/O operation that writes first data to a first target logical address; and
responsive to receiving the first write I/O operation, performing first processing including:
allocating a first storage chunk from the first storage chunks in accordance with the allocation order denoted by the main list, wherein a first block of the plurality of blocks includes the first storage chunk and a second storage chunk of the second storage chunks; and
storing the first data in the first storage chunk of the first block.

2 . The computer-implemented method of claim 1 , wherein forming the N sets of lists includes:
for each of the first storage chunks from each of the plurality of blocks, placing said each of the first storage chunks in a selected list of the first set having an associated index L, wherein L=j modulo J2, wherein j is a block index uniquely identifying said each block of the plurality of blocks, and wherein J2 denotes a number of block descriptors stored in a single page.

3 . The computer-implemented method of claim 2 , wherein forming the N sets of lists includes:
for each of the second storage chunks from each of the plurality of blocks, placing said each of the second storage chunks in a selected list of the second set having an associated index L2, wherein L2=J2+ (j modulo J2).

4 . The computer-implemented method of claim 1 , wherein said first processing includes:
removing the second storage chunk of the first block from the main list; and creating, in a mapping table, a first mapping between the first target logical address and the first block, wherein the first mapping indicates that the second storage chunk of the first block is available for allocation and is reserved for storing content written to a logical address included in a first volume logical address range, wherein the first volume logical address range includes the first target logical address.

5 . The computer-implemented method of claim 4 , wherein the mapping table is a hash table, and logical addresses are used as keys to index into the hash table to a corresponding hash table entry associated with a volume logical address range and a reserved storage chunk.

6 . The computer-implemented method of claim 5 , further comprising:
determining, in accordance with one or more criteria, whether to remove one or more reserved storage chunks of the mapping table, wherein the one or more reserved storage chunks includes the second storage chunk associated with the first mapping; and responsive to determining to remove the one or more reserved storage chunks from the mapping table, performing second processing including:
removing the second storage chunk associated with the first mapping from the mapping table indicating that the second storage chunk is no longer reserved; and
adding the second storage chunk of the first block to the main list indicating that the second storage chunk is available for subsequent allocation in accordance with the allocation order denoted by the main list.

7 . The computer-implemented method of claim 6 , wherein said adding the second storage chunk to the main list includes adding the second storage chunk to a head of the main list.

8 . The computer-implemented method of claim 7 , wherein after said adding the second chunk to the head of the main list is performed, the head of the main list identifies the second storage chunk as a next subsequent chunk to be allocated in accordance with the allocation order denoted by the main list.

9 . The computer-implemented method of claim 6 , wherein the one or more criteria includes a condition that indicates to remove the one or more reserved storage chunks from the mapping table periodically after a specified amount of time has elapsed.

10 . The computer-implemented method of claim 6 , wherein the one or more criteria includes a condition that indicates to remove the one or more reserved storage chunks from the mapping table periodically after a specified number of chunk allocations is performed.

11 . The computer-implemented method of claim 10 , further comprising:
performing the specified number of chunk allocations, including allocating one or more chunks from the main list in accordance with the allocation order denoted by the main list.

12 . The computer-implemented method of claim 11 , further comprising:
performing the specified number of chunk allocations, including allocating one or more other reserved chunks each associated with a corresponding mapping of the mapping table and each associated with a corresponding volume logical address range.

13 . The computer-implemented method of claim 3 , wherein lists of the first set are ordered by increasing values of L associated with the lists of the first set, and wherein lists of the second set are ordered by increasing values of L2 associated with the lists of the second set.

14 . The computer-implemented method of claim 13 , wherein the plurality of blocks are included in a plurality of storage areas, wherein each of the plurality of storage areas has an associated unique index k, wherein each storage chunk in each list of the first set and the second set has an associated index k identifying a particular one of the plurality of storage areas which includes said each storage chunk, and
wherein storage chunks in said each list are ordered in said each list based on increasing values of k corresponding to particular ones of the plurality of storage areas to which the storage chunks of said each list belong, and wherein the storage chunks of said each list having a same associated index k are ordered based on increasing block index values for j corresponding to blocks which include the storage chunks of said each list.

15 . The computer-implemented method of claim 14 , wherein said generating the main list further comprises:
appending the N sets of lists to a tail of an existing main list, wherein the tail denotes an end of the main list and is associated with a corresponding end storage chunk, wherein a head of the main list identifies a next storage chunk to be allocated in the allocation order, wherein the allocation order denoted by the main list is a consecutive allocation ordering of storage chunks from the head of the main list to the tail of the main list.

16 . A system comprising:
one or more processors; and one or more memories comprising code stored thereon that, when executed, performs a method comprising:
identifying a plurality of blocks of storage available for allocation, wherein each of the plurality of blocks is partitioned into N storage chunks;
generating a main list denoting an allocation order of a first plurality of storage chunks, including:
forming N sets of lists, wherein each of the N sets of lists identifies corresponding ones of the N storage chunks from

Assignees

• Dell Products Lp

Inventors

• Shknevsky Alexander
• Baruch Oran
• Rahamim Maor
• Vankamamidi Vamsi K

Classifications

• G06F3/0689

  Disk arrays, e.g. RAID, JBOD · CPC title

• G06F3/061 Primary

  Improving I/O performance · CPC title

• G06F3/0644

  Management of space entities, e.g. partitions, extents, pools · CPC title

• G06F3/064 Primary

  Management of blocks · CPC title

• G06F3/067

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