Persistent object storage with sequential updates

Patent metadata

Field	Value
Publication number	US-12436709-B1
Application number	US-202117364820-A
Country	US
Kind code	B1
Filing date	Jun 30, 2021
Priority date	Jun 30, 2021
Publication date	Oct 7, 2025
Grant date	Oct 7, 2025

Abstract

An object storage data store may be implemented using storage devices providing multiple extents, where individual ones of the extents include multiple independently addressable, contiguous blocks and where updating an extent is performed by updating the respective independently addressable, contiguous blocks sequentially using a series of write operations. The storage devices may include shingled magnetic recording devices and may include conventional persistent storage devices. The key value data store may implement a superblock structure, index structure, and data store structure using respective portions of the multiple extents, where updates to each of the structures is performed sequentially using a series of write operations. The key value data store may further implement a cache for the index structure to minimize input-output (IO) density of the object storage data store.

First claim

What is claimed is:

1. A system, comprising:
one or more storage devices respectively comprising a plurality of extents, wherein individual ones of the plurality of extents comprise a plurality of independently addressable, contiguous blocks;
at least one processor; and
a memory storing program instructions that when executed cause the at least one processor to implement an object store, the object store configured to:
write the respective independently addressable, contiguous blocks sequentially to update individual ones of the plurality of extents;
implement a data store using a data portion of the plurality of extents, the data store storing a plurality of elements respectively comprising one or more portions, wherein individual ones of the portions of the plurality of elements are stored in respective extents of the data portion of the plurality of extents, and wherein to update individual ones of the portions of the plurality of elements the object store is configured to update the independently addressable, contiguous blocks of the respective extents of the data portion of the plurality of extents sequentially;
implement an index using an index portion of the plurality of extents, wherein the index identifies the plurality of elements stored in the data store, and wherein to update a portion of respective portions of the index stored on individual ones of the index portion of the plurality of extents the object store is configured to:
identify a group of leaf nodes representing a contiguous key range to maximize a number of in-memory updates to the contiguous key range;
integrate the in-memory updates of the identified group of leaf nodes into index data for the portion of the index;
reserialize the index data into an updated group of leaf nodes to be sequentially written to the portion of the index; and
update the independently addressable, contiguous blocks of the index data for the portion of the index sequentially; and

provide an object storage interface to clients of the object store using the implemented index and data store.

2. The system of claim 1 , the object store further configured to:
implement a background reclamation process, configured to:
copy a plurality of the portions of the plurality of elements to a new extent of the data portion of the plurality of extents, wherein the new extent is contiguously populated with the plurality of the portions, wherein the copying frees at least one of the extents of the data portion of the plurality of extents, and wherein the copying reorganizes at least some of the portions of the plurality of elements according to likelihood of future access.

3. The system of claim 1 , the object store further configured to:
implement an index cache using one or more additional storage devices, the index cache configured to:
cache the index on the one or more additional storage devices to reduce the rate of read accesses performed on the index.

4. The system of claim 1 , wherein the one or more storage devices are shingled magnetic recording (SMR) storage devices respectively comprising a plurality of recording zones, and wherein individual ones of the plurality of extents correspond to respective groups of one or more of the plurality of recording zones.

5. A method, comprising:
configuring one or more storage devices to provide a plurality of extents respectively comprising a plurality of contiguous,
independently addressable blocks, wherein writing data to an extent of the plurality of extents comprises writing the respective independently addressable, contiguous blocks of the extent sequentially;
receiving a request to write an object for a client of an object store via an object storage interface;
writing the object to a data store, the writing comprising writing a portion of the object to a data extent of the plurality of extents sequentially; and
updating an index identifying the object in the data store, the updating comprising:
identifying a group of leaf nodes representing a contiguous key range to maximize a number of in-memory updates to the contiguous key range;
integrating the in-memory updates of the identified group of leaf nodes into index data for a portion of the index;
reserializing the index data into an updated group of leaf nodes to be sequentially written to the portion of the index; and
writing the portion of the index to an index extent of the plurality of extents sequentially.

6. The method of claim 5 , further comprising:
copying the portion of the object to a new extent of the plurality of extents, wherein the new extent is contiguously populated with the portion of the object and at least a second portion of the object, and wherein the copying frees the data extent for reuse.

7. The method of claim 5 , further comprising:
caching the index on one or more additional storage devices to reduce the rate of read accesses performed on the index.

8. The method of claim 5 , wherein the index is structured according to a log-structured merge tree and is partitioned into at least a first portion resident in memory and a second portion stored in the index portion of the plurality of extents.

9. The method of claim 5 , wherein the one or more storage devices are shingled magnetic recording (SMR) storage devices respectively comprising a plurality of recording zones, and wherein individual ones of the plurality of extents correspond to respective groups of one or more of the plurality of recording zones.

10. The method of claim 5 , further comprising:
implementing a plurality of superblocks using a superblock portion of the plurality of extents, wherein updating individual ones of the plurality of superblocks comprises updating the independently addressable, contiguous blocks of the respective extents of the superblock portion of the plurality of extents sequentially.

11. The method of claim 10 , wherein the one or more storage devices are persistent storage devices respectively emulating the behavior of SMR storage devices using the plurality of extents, and wherein respective write pointers for the plurality of recording zones are maintained in the plurality of superblocks.

12. The method of claim 5 , wherein the object store is an object storage service offered as part of a provider network, wherein requests to access data objects stored in the object storage service are received according to an Application Programming Interface (API) for the object storage service.

13. One or more non-transitory computer-accessible storage media storing program instructions that when executed on or across one or more computing devices cause the one or more computing devices to perform:
configuring one or more storage devices to provide a plurality of extents respectively comprising a plurality of contiguous, independently addressable blocks, wherein writing data to an extent of the plurality of extents comprises writing the respective independently addressable, contiguous blocks of the extent sequentially;
receiving a request to store an object for a client of the object store via an object storage interface;
writing the object to a data store, the writing comprising writing at least a portion of the object to a data extent of the plurality of extents sequentially; and
updating an index identifying the object in the data store, the updating comprising:
identifying a group of leaf nodes representing a contiguous key range to maximize a number of in-memory updates to the contiguous key range;
integrating the in-memory updates of the identified group of leaf nodes into index data for a portion of the index;
reserializing the index data into an updated group of leaf no

Assignees

• Amazon Tech Inc

Inventors

• Slatton Thomas Grant
• Markle Seth W
• Bornholt James Alexander
• Joshi Rajeev
• Warfield Andrew Kent

Classifications

• G06F3/067

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

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F3/0679

  Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP] · CPC title

• G06F3/0655 Primary

  Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices · CPC title