US-12625638-B1 - Capacity-based replication management across different data set distributions

US12625638B1US 12625638 B1US12625638 B1US 12625638B1US-12625638-B1

Abstract

An update performed to a first data set may be replicated to a second data set, where the first and second data sets may be organized according to different schemas. The replication of the update may comprise determining that a set-wide replication capacity for replicating across the second data set may suffice to perform the replication, as well as a store-specific replication capacity for replicating to an identified data store of the second data set. Based on a determination that the set-wide replication capacity and the store-specific replication capacity may suffice for replicating the update, the update may be caused to be replicated on the second data set.

Inventors

Sagar Mundra
Carlos Humberto Hasan Valdovino
Sharatkumar Nagesh Kuppahally
Somasundaram Perianayagam
Vinit Vikram Shah

Assignees

AMAZON TECHNOLOGIES, INC.

Dates

Publication Date: 20260512
Application Date: 20240930

Claims (20)

1 . A system, comprising: at least one processor; and a memory, storing program instructions that when executed by the at least one processor, cause the at least one processor to implement a database system, the database system is configured to: perform one or more updates received for a table, wherein the table is stored according to a first schema across a first plurality of storage nodes; determine one or more index updates for a secondary index for the table, wherein the secondary index is stored according to a second schema, different from the first schema, across a second plurality of storage nodes; identify a storage node of the second plurality of storage nodes to perform the one or more index updates according to the second schema; obtain, for the secondary index: an index-wide replication capacity for replicating to the secondary index across the second plurality of storage nodes; and a node-specific replication capacity for replicating to the identified storage node; and determine that there is sufficient capacity to perform the index update according to both the index-wide replication capacity and the node-specific replication capacity; and cause the identified storage node to perform the index update to the secondary index.
2 . The system of claim 1 , wherein prior to the determination that there is sufficient capacity to perform the index update, the database system is further configured to determine that there is not sufficient capacity to perform the index update according to either a prior index-wide replication capacity and a prior node-specific replication capacity and delay performing the update for a period of time before attempting again.
3 . The system of claim 2 , wherein the identified storage node determines that there is not sufficient capacity of the identified storage node to perform the index update, and wherein the identified storage node is configured to: reject the index update to the secondary index; and return an indication of rejection of the index update to the database system.
4 . The system of claim 3 , wherein in response to receiving a rejection indication from the identified storage node, the database system is configured to: analyze the received indication of rejection to determine the identified storage node rejected the index update; based on determining the identified storage node rejected the index update, wait for a specific window of time; and attempt again to perform the index update, comprising: obtain a further index-wide replication capacity and a further node-specific replication capacity, for the identified storage node; determine that there is sufficient capacity to perform the index update according to the further index-wide replication capacity and the further node-specific replication capacity; and cause the identified storage node to perform the index update to the secondary index.
5 . The system of claim 4 , wherein the database system comprises a non-relational database service.
6 . The system of claim 1 , wherein causing the identified storage node to perform the index update to the secondary index, comprises of: determine, by the identified storage node, that there is sufficient capacity of the identified storage node to perform the index update; perform, by the identified storage node, the index update to the secondary index; and return, by the identified storage node, an indication of confirmation of the index update performed to the secondary index to the database system.
7 . A method, comprising: for one or more updates to a first data set distributed across a first plurality of data stores, replicating at least one of the updates to a second data set, wherein the second data set is a distributed across a second plurality of data stores, wherein the distribution of the second data set across the second plurality of data stores is different than the distribution of the first data set across the first plurality of data stores, and wherein the replicating comprises: identifying a data store of the second plurality of data stores to replicate the at least one update to the second data set; determining that replication to the identified data store can proceed based, at least in part, on a determination that: a set-wide replication capacity for replicating across the second plurality of data stores of the second data set is sufficient to perform replication; and a store-specific replication capacity for replicating to the identified data store is sufficient to perform replication; and sending a request to the identified data store to perform the update to the second data set.
8 . The method of claim 7 , further comprising: wherein prior to determining that the replication to the identified data store can proceed: determining that a prior set-wide replication capacity or a prior store-specific replication capacity are not sufficient to perform the replication: delaying the replication of the at least one update for a period of time before re-attempting to perform the at least one update.
9 . The method of claim 7 , further comprising: receiving, by the identified data store, the request to update the second data set; and wherein performing the request to update the second data set, by the identified data store, comprises: determining, by the identified data store, that there is sufficient capacity of the identified data store to perform the at least one update; perform, by the identified data store, the at least one update to the second data set; and return, by the identified data store, an indication of confirmation of updating the second data set.
10 . The method of claim 9 , further comprising: wherein the one or more updates are maintained in a buffer; and wherein in response to receiving the indication of confirmation of the update to the second data set from the identified data store, removing the at least one update from the buffer.
11 . The method of claim 7 , further comprising: receiving, by the identified data store, the request to update the second data set; and wherein performing the request to update the second data set, by the identified data store, comprises: determining, by the identified data store, that there is not sufficient capacity of the identified data store to perform the at least one update; and returning an indication of rejection.
12 . The method of claim 11 , wherein in response to receiving the indication of rejection of updating the second data set, from the identified data store, the method comprising: waiting for a period of time; and attempting again to replicate the at least one update to the identified data store, comprising: determining that a further set-wide replication capacity and a further store-specific replication capacity suffice to perform the replication; and sending the request to the identified data store to perform the update to the second data set.
13 . The method of claim 7 , wherein replicating the at least one of the updates to the second data set comprises selecting the at least one update from the one or more updates based, at least in part, on respective arrival times for the one or more updates.
14 . One or more non-transitory, computer-readable storage media, storing program instructions that when executed on or across one or more computing devices cause the one or more computing devices to implement: for one or more updates to a first data set distributed across a first plurality of data stores, replicating at least one of the updates to a second data set, wherein the second data set is distributed across a second plurality of data stores, wherein the distribution of the second data set across the second plurality of data stores is different than the distribution of the first data set across the first plurality of data stores, and wherein the replicating comprises: identifying a data store of the second plurality of data stores to replicate the at least one update to the second data set; determining that replication to the identified data store can proceed based at least in part, on a determination that: a set-wide replication capacity for replicating across the second plurality of data stores of the second data set is sufficient to perform replication; and a store-specific replication capacity for replicating to the identified data store is sufficient to perform replication; and sending a request to the identified data store to perform the update to the second data set.
15 . The one or more non-transitory, computer-readable storage media of claim 14 , storing further program instructions that when executed on or across the one or more computing devices, cause the one or more computing devices to further implement: prior to determining that the replication to the identified data store can proceed: determining that a prior set-wide replication capacity or a prior store-specific replication capacity may not be sufficient to perform the replication; and delaying performing the replication for a period of time.
16 . The one or more non-transitory, computer-readable storage media of claim 14 , storing further program instructions that when executed on or across the one or more computing devices, further cause the one or more computing devices to implement: receiving, from the identified data store, an indication of rejection of replicating the update to the second data set; in response to receiving the indication of rejection, waiting for a period of time; and attempting again to replicate the update, wherein in attempting again to replicate the update, the program instructions cause the one or more computing devices to implement: determining that replication to the identified data store can proceed; and sending the request to the identified data store to perform the update to the second data set.
17 . The one or more non-transitory, computer-readable storage media of claim 14 , storing further program instructions that when executed on or across the one or more computing devices, further cause the one or more computing devices to implement: receiving, from the identified data store, an indication of acceptance of replicating the update to the second data set; removing the at least one update to replicate; and proceeding to another update to replicate to the second data set based, at least in part, on further one or more updates to the first data set.
18 . The one or more non-transitory, computer-readable storage media of claim 14 , wherein the one or more computing devices implement capacity-based management for replicating updates to the second data set, and wherein the one or more non-transitory, computer-readable storage media store further program instructions that when executed on or across the one or more computing devices, cause the one or more computing devices to further implement: receiving one or more further updates to the first data set to replicate to the second data set; determining that a capacity of the set-wide replication capacity or the store-specific replication capacity is not sufficient to perform the one or more further updates; and rejecting the received one or more further updates.
19 . The one or more non-transitory, computer-readable storage media of claim 14 , wherein the set-wide replication capacity for replicating across the second plurality of data stores is obtained from the second plurality of data stores.
20 . The one or more non-transitory, computer-readable storage media of claim 14 , wherein the first data set is a database table hosted by a database service of a provider network, and wherein the second data set is a global secondary index hosted by the database service.

Description

BACKGROUND Data is often distributed to scale the storage capacity or processing capacity of systems that provide access to the data. For example, database tables or other data objects can be divided into partitions in order to leverage the capacity of different hosts, such as different servers or other computing devices, to separately provide access to individual partitions. However, replicating different portions of the partitioned data can further increase the complexity and costs of propagating changes to the data to other data replicas. For example, projections or views of a partitioned database table may be separately maintained. Propagating changes to the projection or views may increase the costs of processing updates at the original partitions of the database table as the original partitions of the database table may need to ensure that the appropriate projections or views of the database table are updated. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a logical block diagram illustrating capacity-based replication management for replicating changes across data set distributions, according to some embodiments. FIG. 2 is a logical block diagram illustrating a provider network offering a database service that may implement capacity-based replication management for replicating changes across data set distributions, according to some embodiments. FIG. 3 is a logical block diagram illustrating a conditional propagation architecture replicating index updates on a partition of the index using capacity-based replication management, according to some embodiments. FIG. 4 is a logical block diagram illustrating interactions to replicate updates to a secondary index based on prior updates performed at a source table, according to some embodiments. FIG. 5 is a logical block diagram illustrating example interactions to replicate updates to a secondary index based on prior updates performed at a source table when the secondary index rejects the update, according to some embodiments. FIG. 6 is a logical block diagram illustrating example interactions to perform conditional propagation updates on a secondary index based on table updates, according to some embodiments. FIG. 7 is a high-level flowchart illustrating various methods and techniques to implement capacity-based replication management for replicating changes across data set distributions, according to some embodiments. FIG. 8 is a high-level flow chart illustrating various methods and techniques to implement capacity-based replication management for propagating source table updates to respective secondary indexes, according to some embodiments. FIG. 9 is a block diagram illustrating an example computing system, according to some embodiments. While embodiments are described herein by way of example for several embodiments and illustrative drawings, those skilled in the art will recognize that the embodiments are not limited to the embodiments or drawings described. It should be understood, that the drawings and detailed description thereto are not intended to limit embodiments to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description or the claims. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include”, “including”, and “includes” mean including, but not limited to. DETAILED DESCRIPTION The techniques described herein may implement capacity-based replication management for replicating changes across data set distributions, according to some embodiments. Data sets may be distributed across one or more locations in a storage system, in some embodiments. In this way, clients can access and independently update different portions of the data set at the one or more locations in the storage system, in some embodiments. The arrangement of the data set may be optimal for some access requests (e.g., queries based on indexed fields or values in the table). However, to optimally process other access requests (e.g., queries based on non-indexed fields or values in a table), portions of the data set (or the entire data set) may be replicated in one or more other locations (e.g., a different storage nodes, systems, or hosts) in a different arrangement, subset, or format that is more performant for performing the other type of access requests according to a schema that defines the different arrangement, subset, or format, in some embodiments. For example, in some scenarios, locating items that have particular attributes may cause a scan across all (or a large number) of items in order to locate the items with the particular attributes. However, a projection