Systems for consistent modification of stored values

Described are techniques for reducing inaccurate values in databases by managing the order in which processes are enqueued and executed. A modification process to modify a first value in a database may be received. A precomputation process that modifies values dependent on the first value may be enqueued prior to enqueuing of the modification process to ensure that the modification process does not occur if the precomputation process fails. The modification process may be executed prior to executing the precomputation process to ensure that the precomputation process acts to modify the dependent values using the modified version of the first value.

BACKGROUND

In database systems, one or more stored values may be calculated using other stored values. Therefore, if a first value in the database is modified, other values dependent on that first value must also be modified for the data in the database to remain accurate.

DETAILED DESCRIPTION

Databases and other types of data structures may be used to store one or more values (e.g., records, resources, and so forth) as well as the relationships between values. For example, a first value may be used to calculate one or more other values, which in turn, may be used to calculate additional values. As such, if one value in a database is modified, other values in the database may become inaccurate until recalculated using the modified value. To account for potential inaccuracies, some database systems recalculate values at the time they are accessed by a process. However, recalculation of values at the time of access may introduce latency to a user experience, especially if the calculations used to determine an accessed value are numerous or complex. In some cases, it may be desirable to “precompute” one or more values to facilitate future access thereto. For example, one or more values that depend from a modified value may be recalculated at or near the time that the modified value becomes available. Precomputing of the one or more values may enable an accurate value to be available immediately upon access.

A number of processes may attempt to access one or more values in a database at any given time, especially in large scale databases, such as those used by online merchants to contain items offered for sale by numerous venders. To retain integrity of the values in the database, resource locks may be used to prevent multiple processes from acting on the same value simultaneously. For example, to access a value, a process must first request access to a lock associated with the value. If the lock is currently granted to another process, the requesting process may be placed on a queue for eventual access to the value. As such, when other processes are accessing values in a database, it may not be possible to modify a value or to recalculate one or more of the values that depend upon a modified value at or near the time when the modification to the value is provided to the database. If a precomputation process fails to update a respective value, while an associated modification process successfully modifies a value, one or more values within the database may become inaccurate.

This disclosure describes techniques that may be used to process modification and precomputation processes in one or more databases or other types of data stores, while facilitating consistent execution and output of the processes. When a modification to a first value, stored in a computer-readable storage medium (CRSM), is received, one or more values that depend on the first value (e.g., that are calculated using the first value) may be determined. A precomputation process configured to modify the dependent values may be generated and enqueued for access to the CRSM. Because enqueuing of the precomputation process may fail, the modification to the first value may not be enqueued until confirmation data indicating the enqueuing of the precomputation process is received. For example, if the modification process were enqueued prior to enqueuing the precomputation process, a failure in enqueuing the precomputation process would result in the first value being updated, upon execution of the modification process, while the dependent values remain static, and therefore inaccurate. Therefore, confirming enqueuing of the precomputation process prior to enqueuing an associated modification process ensures that if the first value is updated, dependent values will also be updated. Further, if the precomputation process is enqueued prior to enqueuing of the modification to the first value and enqueuing of the modification fails, the precomputation process may calculate the dependent values based on the unmodified first value, thus not introducing inaccuracy. Therefore, implementations described herein may be used to ensure, e.g., based on received confirmation data, that a precomputation process has been enqueued prior to enqueuing of a related modification process.

In some implementations, the precomputation process may determine whether the first value has been modified prior to attempting to calculate values dependent on the first value. For example, a precomputation process may be configured to access a value associated with a modification process to determine whether that value has been modified. A modification process may assign a version identifier to the first value. Responsive to a determination that the version identifier has been assigned to the value, the precomputation process may be executed to modify the dependent values. If it is determined that the version identifier has not been assigned to the value, the precomputation process may fail or the precomputation process may be delayed for a length of time then subsequently retried. Subsequent to the length of time, if the precomputation process determines that the version identifier has not been assigned to the value, this may indicate that the modification process has failed, and the precomputation process may be executed using the unmodified first value without creating inaccuracy.

In some implementations, the precomputation process may have a version identifier associated therewith. If correspondence between the version identifier of the precomputation process and that of the modified value is determined, the precomputation process may be executed to modify the dependent values. For example, if the version identifier associated with the value is identical to or newer than the version identifier associated with the precomputation process, this may indicate that the modification process or a later process has updated the first value, and the precomputation process may be executed. If a lack of correspondence between the version identifier associated with the precomputation process and that associated with the first value is determined, execution of the precomputation process may be delayed for a length of time. For example, if the version identifier associated with the first value is older than that associated with the precomputation process, this may indicate that the first value has not yet been modified. Execution of the precomputation process may be delayed for a length of time corresponding to a process time associated with the modification process (e.g., an expected time after which the modification process may be completed). Subsequent to the length of time, if correspondence with the version identifier associated with the value is determined, the precomputation process may be executed using the modified value. If a lack of correspondence is determined, the precomputation process may be executed using the unmodified value, or the precomputation process may fail. The lack of correspondence subsequent to the length of time may indicate that the modification process has failed. Therefore, executing the precomputation process based on the unmodified value may not generate inaccuracies in the database. The modification process and any associated precomputation processes may be subsequently retried.

In some implementations, execution of a precomputation process may fail. If a modification process is successfully executed while a precomputation process fails, dependent values may become inaccurate. Therefore, the precomputation process may be retried until it has been successfully executed. For example, upon determination that execution of a precomputation process has failed, the precomputation process may be deferred for a length of time, and then retried. The length of time for which the precomputation process is deferred may increase (e.g., exponentially) with each successive time that the precomputation process is retried.

In some implementations, a first precomputation process may be enqueued, prior to a second precomputation process that is configured to act on the same values. When the second precomputation process is enqueued, correspondence between the values associated with the first and second precomputation processes may be determined, and the first precomputation process may be removed from the queue. Removal of duplicate processes from a queue may reduce redundancy and inefficiency while conserving time and computation resources. For example, because the second precomputation process was generated more recently than the first precomputation process, the second precomputation process may be associated with a more recent modification process or other operation. Therefore, the second precomputation process may be configured to modify dependent values based on more recent modifications to other values. The dependent values modified by the second precomputation process would replace those modified by the first precomputation process, causing the first precomputation process in the queue to be redundant.

In some implementations, responsive to one or more of a determination that the first value has been modified or receipt of confirmation data indicating a modification of the first value, a backfill process may be generated and enqueued for access to the CRSM. The backfill process may be configured to recalculate one or more values in the CRSM based on the modification to the first value. For example, the first value may include a source value, such as business logic or another type of data upon which a large number of values within a database may depend. Continuing the example, the first value may include a fraud status associated with a vender. Modification of the fraud status associated with the vender may require recalculation of every item in a database associated with that vender. In some implementations, a backfill process may recalculate all or a portion of the values in a database, based at least in part on a modified source value, without independently determining the dependency of one or more of the values in the database. For example, the backfill process may access and recalculate each value in a database based on the current status of the values from which the recalculated values depend. To facilitate modification of a large number of values, a backfill process may be separated into a plurality of modification processes, one or more of which may be separately enqueued for access to one or more databases.

In some implementations, enqueuing a backfill process may include generating queue data in a separate queue from which other processes, such as modification or precomputation processes, are enqueued. One or more priority rules may be accessed to determine a priority corresponding to one or more of the backfill queue or the queue containing other processes. For example, a priority rule may include certain days and times, such as times historically associated with low use of a database by other processes, during which backfill processes enqueued on a backfill queue will be granted access to values prior to other processes. During other days and times, other processes may be granted access to values prior to backfill processes.

In some implementations, another process, such as a precomputation process, may be enqueued and executed, after a backfill process is enqueued but prior to execution of the backfill process. For example, a backfill process configured to modify a particular value may be enqueued, but prior to modification of that value by the backfill process, a precomputation process may modify the particular value based on one or more recent modifications to other values in the database. The backfill process may have a version identifier associated therewith, and the precomputation process may assign a different version identifier to a modified value. Upon accessing the modified value, the backfill process may determine a lack of correspondence between the version identifier associated with the backfill process and that associated with the modified value. For example, the version identifier associated with the modified value may be identified as more recent than the version identifier associated with the backfill process. The backfill process may refrain from modifying values having a more recent version identifier stored in association therewith. This may avoid redundant operations in which the backfill process replaces a value that has been recently updated with an identical value.

In some implementations, to prevent simultaneous access to a particular value by multiple processes, processes may be enqueued to a database using a host device to which a lock has been granted. For example, multiple processes having the same value or output associated therewith may be assigned to a single partition of a database. Each partition of the database may have a lock associated therewith, and each lock may be assigned to a host device. A process may be provided to the host device associated with the partition assigned to the process for that process to be enqueued. The host device may provide confirmation data indicative of receipt of the process. If one or more host devices fail, become unavailable, or if the number of processes accessing a particular partition exceeds the computation capabilities of the host device to which the partition is assigned, the host device may be disassociated from one or more partitions. A workload associated with one or more additional host devices may be determined, and the partition(s) from which the host device was disassociated may be assigned to one or more of the additional host devices.

Implementations described herein may thereby facilitate maintenance of accurate values in one or more databases or other types of data stores by ensuring that multiple related processes are enqueued and executed. For example, a single process of a group of related processes may be prevented from being enqueued or from being executed prior to receiving confirmation data regarding enqueuing or execution of a related process. Implementations described herein may also use dynamically changeable host devices assigned to partitions of a database to control access to stored values.

FIG. 1depicts a system100that may be used to receive, enqueue, and execute processes to modify one or more values within one or more databases102. The one or more databases102may store a plurality of values104. The depicted databases102may include any manner and any number of data stores, memories, or other computer-readable storage media (CRSM). For example, the databases102may include one or more electronic storage media, magnetic storage media, optical storage media, quantum storage media, mechanical computer storage media, and so forth. The databases102may include one or more database management systems (DBMS), such as MySQL, PostgreSQL, Microsoft SQL Server, Oracle, SAP, IBM DB2, DynamoDB, and so forth. The databases102may operate using one or more standards, such as Structured Query Language (SQL), Open Database Connectivity (ODBC), Java Database Connectivity (JDBC), and so forth.

FIG. 1depicts four example values104: a first value104(1), a second value104(2), a third value104(3), and a fourth value104(4). In the depicted implementation, the second value104(2) and the third value104(3) are dependent upon the first value104(1). For example, the first value104(1) may include a numerical value, represented as “A.” The second value104(2) may include the related value “A+1,” and the third value104(3) may include the related value “A*1.08”. Continuing the example, the first value104(1) may include a price associated with an item, while the second value104(2) may include the price of the item plus a shipping cost, and third value104(3) may include the price of the item including a sales tax. As such, if the first value104(1) were modified due to a change in the price of the item, the second value104(2) and the third value104(3) would also be affected due to their dependency on the first value104(1). The fourth value104(4) may include a source value104, applicable to numerous values104within the database(s)102. For example, the fourth value104(4) may include a tax rate upon which the second value104(2) and other similar values104in the database(s)102may be based.

To reduce latency in a user experience associated with the purchase of the item, the second value104(2) and the third value104(3) may be precomputed using the first value104(1) at or near the time that the first value104(1) is modified. For example,FIG. 1depicts one or more user devices106providing a modification process108configured to modify the first value104(1) to one or more servers110or other types of computing devices in communication with the database(s)102. The user device(s)106or server(s)110may include any type of computing device, such as mobile devices, smartphones, set-top boxes, tablet computers, personal computers, wearable computers, servers, or other types of computing devices.

A precomputation module112in the server(s)110may receive the modification process108and determine the value(s)104in the database(s)102associated with the modification process108. For example, the depicted modification process108may attempt to replace the first value104(1) (e.g., “A”) with an updated or modified first value104(1) (e.g., “B”). The precomputation module112may access database data114to determine one or more databases102that contain the first value104(1) and the specific location(s) of the first value104(1) in the database(s)102. In some implementations, the database data114may include metadata or other types of data indicative of relationships between the first value104(1) and one or more other values104. For example, by accessing the database data114, the precomputation module112may determine that the second value104(2) and the third value104(3) depend upon the first value104(1). The precomputation module112may also determine the nature of the dependencies between the values104from the database data114. In other implementations, the first value104(1) may have metadata or other types of data associated therewith that indicate one or more precomputation processes116to be performed upon modification of the first value104(1). In still other implementations, the modification process108may include one or more precomputation processes116to be performed in addition to the modification process108. Based on one or more of first value104(1), the modification process108, or the database data114, the precomputation module112may generate or access one or more precomputation processes116. The precomputation process(es)116may be configured to modify the second value104(2) and the third value104(3) based on the modification to the first value104(1) and the relationships between the values104.

A queue module118may be configured to provide the precomputation process(es)116to the database(s)102and enqueue the precomputation process(es)116for access to the database(s)102. For example, the queue module118may generate queue data120indicative of the precomputation process(es)116for storage in the database(s)102. Continuing the example, the precomputation process(es)116may be provided to a host device (not shown) that has been granted a resource lock to access a partition of the database(s)102that contain one or more of the first value104(1), the second value104(2), or the third value104(3). The host device may maintain and manage a queue associated with the database(s)102and may provide confirmation data122to the server(s)110indicating that the precomputation process(es)116have been enqueued for access to the database(s)102. In other implementations, a separate device, service, or process may maintain the queue associated with the database(s)102.

As described previously, in some implementations, the server(s)110may refrain from enqueuing the modification process108for access to the database(s)102until confirmation data122indicating successful enqueuing of the precomputation process(es)116has been received. Failure to enqueue a precomputation process116prior to enqueuing a modification process108may result in updating one value104without updating one or more values104that are dependent on the value104, such that the dependent values104in the database102are inaccurate. For example, if the price of an item is updated using a modification process, but an associated precomputation process fails to update a dependent value corresponding to the price of the item, plus a shipping cost and a sales tax, the dependent value would be inaccurate. As such, enqueuing the modification process108after receipt of the confirmation data122indicating successful enqueuing of the precomputation process(es)116facilitates accuracy of the values104dependent upon the first value104(1).

One or more of the queue module118or a modification module124may provide the modification process108to the data base(s)102and enqueue the modification process108for access thereto. The modification module124may determine execution of the modification process108and modification of the first value104(1). In some implementations, additional confirmation data122may be received, indicating that the first value104(1) has been modified. In other implementations, the modification process108may assign or update a version identifier associated with the first value104(1). The precomputation process(es)116may also have a version identifier associated therewith. The version identifiers may be indicative of a time at which the precomputation process(es)116were generated or the first value104(1) was modified.

In some implementations, the precomputation process(es)116may access the first value104(1) to determine the version identifier associated therewith. If the version identifier associated with the first value104(1) is less recent than the version identifier associated with the precomputation process(es)116, this may indicate that the modification process108has not yet modified the first value104(1). Responsive to this determination, the precomputation process(es)116may be deferred and retried or the precomputation process(es)116may fail. A deferred precomputation process116may determine the version identifier associated with the first value104(1) at a later time. If the version identifier associated with the first value104(1) is still less recent than that associated with the precomputation process(es), the modification process108may have failed. In the event of a failed modification process108, the precomputation process(es)116may recalculate the second value104(2) and the third value104(3) using the unmodified first value104(1). In some implementations, the precomputation process(es)116may be deferred for a length of time corresponding to an expected time for execution of the modification process108, then retried. If the version identifier associated with the first value104(1) is older than that associated with the precomputation process(es)116upon retrial of the precomputation process(es)116, this may indicate that the modification process108has failed. Responsive to this determination, the precomputation process(es)116may fail, or the precomputation process(es)116may recalculate the second value104(2) and the third value104(3) using the unmodified first value104(1). If the version identifier of the first value104(1) is determined to be equal to or more recent than that associated with the precomputation process(es)116, this may indicate that the modification process108or a subsequent process has modified the first value104(1). Responsive to this determination, the precomputation process(es)116may be executed to modify the second value104(2) and the third value104(3) using the modified first value104(1).

FIG. 1also depicts a backfill module126associated with the server(s)110. The backfill module126may generate, enqueue, or execute one or more backfill processes responsive to updating of a source value104, such as business logic or another type of data upon which a large number of values104within the database(s)102may depend. For example, one or more user devices106may provide a modification process108configured to modify the fourth value104(4). In the depicted example system100, the fourth value104(4) may represent a sales tax rate applicable to items, while the third value104(3) represents a precalculated cost of an item, including a sales tax. Numerous values104in the database(s)102in addition to those depicted inFIG. 1may be affected by a modification of the fourth value104(4). As such, the fourth value104(4) or the modification process108configured to modify the fourth value104(4) may include a backfill process associated therewith. In other implementations, confirmation data122indicative of modification of the fourth value104(4) may be received, and the backfill module126may generate a backfill process responsive to the confirmation data122.

A backfill process may be configured to recalculate all or a portion of the values104in the database(s)102responsive to the modification of a source value104, such as the fourth value104(4), independent of relationships between values104indicated in the database data114. In some implementations, a backfill process may be configured to determine version identifiers associated with one or more values104and to refrain from modifying values104having version identifiers more recent than that associated with the backfill process. In other implementations, other filters may be applied to the backfill process to include or exclude certain values104from modification. For example, a backfill process may refrain from modifying values104within selected databases102, values104relating to certain types of data, and so forth.

FIG. 2depicts an example system200that may be used to generate, enqueue, and execute precomputation processes116using one or more host devices202. In the depicted implementation, the database(s)102may be divided into partitions204based upon the values104or other outputs therein that may be modified via modification processes108or precomputation processes116. Use of a single partition204assigned to a single value104or set of values104may enable a single lock to be assigned to the partition204to control access to the values104associated with the partition204. As such, use of partitions204may reduce the time and computational resources associated with use of resource locks in a large-scale database system by effectively converting the large scale database system into multiple smaller systems. Specifically,FIG. 2depicts three example sets of partitions204associated with the database(s)102: a first set of partitions204(1), a second set of partitions204(2), and a third set of partitions204(3). Each set of partitions204may include one or multiple partitions204.

A first host device202(1) is shown having the first set of partitions204(1) and the second set of partitions204(2) assigned thereto. A second host device202(2) is shown having the third set of partitions204(3) assigned thereto. A third host device202(3) may control the assignment of partitions204to host devices202. For example, the third host device202(3) is depicted providing partition assignments206to the first host device202(1) and the second host device202(2). In some implementations, the third host device202(3) may monitor one or more of the other host devices202or the number of processes accessing one or more of the partitions204. The third host device202(3) may further provide or modify partition assignments206responsive to changes in the host devices202or partitions204. For example, if the first host device202(1) or second host device202(2) fails or becomes disassociated from a partition204, the third host device202(3) may reassign one or more partitions204previously assigned to the first host device202(1) or second host device202(2) to other host devices202. If a number of processes accessing one or more partitions204increases such that the computation capacity of a host device202is exceeded by the processes accessing partitions204assigned thereto, the third host device202(3) may reassign one or more of the partitions204assigned to that host device202to other host devices202. In some implementations, the first host device202(1), the second host device202(2), or one or more other host devices202may monitor the third host device202(3). In the event that the third host device202(3) fails, a different host device202may begin monitoring other host devices202and providing partition assignments206thereto. The ability to access and modify partition assignments206may be restricted using a resource lock, such that a single host device202may access and modify partition assignments206at a given time.

One or more user devices106are shown providing a modification process108to one or more servers110. The server(s)110may function as a router, which may be used to provide processes to the database(s)102. The server(s)110may further provide and receive processes and other data to and from the host devices202or one or more intermediate devices. For example, responsive to receipt of the modification process108from the user device(s)106, the server(s)110may provide queue data120indicative of the modification process108to one or more queue devices208. The user devices106, servers110, host devices202, or queue devices208may include any type of computing devices, such as mobile devices, smartphones, set-top boxes, tablet computers, personal computers, wearable computers, servers, or other types of computing devices. The queue data120may include one or more identifiers, metadata, or other types of data associated with the modification process108. In some implementations, the modification process108, itself, may be provided to the queue device(s)208, in lieu of queue data120, to be enqueued for access to the database(s)102.

The queue device(s)208may in turn provide the queue data120or the modification process108to the host device202associated with the partition204containing the value(s)104associated with the modification process108. For example,FIG. 2depicts the queue device(s)208providing the queue data120to the first host device202(1). In other implementations, a queue may be maintained by or associated with the host device(s)202or the server(s)110, rather than one or more separate queue device(s)208, thus eliminating use of the queue device(s)208. In some implementations, the first host device202(1) may generate one or more precomputation process(es)116based on the queue data120or the modification process108. In other implementations, the modification process108, the queue data120, or the value(s)104associated with the modification process108may include one or more precomputation processes116associated therewith. When the first host device202(1) determines that access to the database(s)102for one or more of the modification process108or the precomputation process(es)116is available, the first host device202(1) may provide the precomputation process(es)116to the server(s)110for provision to the database(s)102.

When the precomputation process(es)116have been enqueued for access to the database(s)102, prior to enqueuing of the modification process108to prevent inaccuracies in the database(s)102, one or more of the first host device202(1) or the queue device(s)208may provide confirmation data122to the server(s)110. Responsive to the confirmation data122, the server(s)110may provide the modification process108to the database(s)102to update one or more values104stored therein. The precomputation process(es)116may subsequently be executed to update dependent values stored in the database(s)102. In some implementations, the first host device202(1) may provide confirmation data122to the queue device(s)208to indicate that the precomputation process(es)116have been provided to the server(s)110.

FIG. 3illustrates a flow diagram of one possible implementation300of a flow of data between one or more servers110, queue devices208, and host devices202. The progression of time302is illustrated along the vertical axis, with time increasing toward the downward direction.

Block304illustrates receipt, by the server(s)110, of a modification process108from one or more user devices106. One or more modification processes108may be received from the user devices106, from other sources, or accessed from a data store associated with the server(s)110. In other implementations, the server(s)110may be used to generate a modification process108. The modification process108may be configured to modify one or more values104stored within one or more databases102.

Block306illustrates determination, by the server(s)110, of one or more precomputation processes116from the modification process108. In some implementations, the server(s)110may generate one or more precomputation processes116. For example, the precomputation module112may be used to determine one or more additional values104that depend upon the value104to be modified by the modification process108. In other implementations, the modification process108may include a precomputation process116associated therewith. In still other implementations, the value(s)104modified by the modification process108may include one or more precomputation processes116associated therewith.

Block308illustrates the server(s)110enqueuing the precomputation process(es)116to one or more queue devices208. In some implementations, queue data120indicative of the precomputation process(es)116may be provided to the queue device(s)208for entry on a queue for access to the database(s)102. In other implementations, the precomputation process(es)116themselves may be provided to the queue device(s)208. In still other implementations, the queue may be associated with the host device(s)202or the server(s)110, rather than one or more separate queue device(s)208, thus eliminating use of the queue device(s)208.

Block310illustrates providing, by the queue device(s)208, of confirmation data122to the server(s)110. The confirmation data122may indicate the enqueuing of the precomputation process(es)116for access to the database(s)102. Once the precomputation process(es)116have been durably enqueued for access to the database(s)102, the confirmation data122may be used to determine that the enqueuing of the precomputation process(es)116has not failed. As such, the value(s)104associated with the modification process108may be modified due to the fact that the enqueued precomputation process(es)116will subsequently update values104dependent from the value(s)104associated with the modification process108.

Block312illustrates modification of the value(s)104in the database(s)102using the modification process108. For example, after receipt of the confirmation data122indicating enqueuing of the precomputation process(es)116, the server(s)110may enqueue the modification process108for access to the database(s)102and execute the modification process108. One or more of the queue module118or the modification module124may be used to enqueue and subsequently execute the modification process108. In some implementations, modification of the value(s)104associated with the modification process108may include assigning, modifying, or updating a version identifier associated with the value(s)104.

Block314illustrates providing of the precomputation process(es)116, by the queue device(s)208, to the host device(s)202for processing. For example, the host device202assigned to the partition204associated with the values104to be modified by the precomputation process(es)116may index or otherwise process the precomputation process(es)116to facilitate execution thereof.

Block316illustrates providing of the precomputation process(es)116, by the host device(s)202, to the server(s)110for execution in the database(s)102. In some implementations, the host device(s)202may index the precomputation process(es)116, determine a data path associated therewith, and so forth.

Block318illustrates providing, from the host device(s)202to the queue device(s)208, confirmation data122indicative of the precomputation process(es)116provided to the server(s)110. Responsive to receipt of the precomputation process(es)116by the server(s)110, block320illustrates the server(s)110executing the precomputation process(es)116. Responsive to receipt of the confirmation data122from the host device(s)202, block322illustrates the queue device(s)208deleting the precomputation process(es)116, or queue data120indicative thereof, from a queue.

In some implementations, execution of the precomputation process(es)116by the server(s)110may include accessing the value(s)104modified by the modification process108to determine whether the modification process108has successfully updated the value (s)104. For example, the modification process108may assign, modify, or update a version identifier associated with the modified value(s)104. When a precomputation process116determines that the version identifier associated with a value104to be equal to or more recent than a version identifier associated with the precomputation process116, the precomputation process116may recalculate one or more dependent values104based on the modified value104. If the precomputation process116determines that the version identifier associated with a value104is less recent than the version identifier associated with the precomputation process116, this determination may indicate that the modification process108has not yet updated the value104. A failure to update the value104may occur if the modification process108fails, if enqueuing of the modification process108fails, or if the modification process108has been enqueued but has not yet been executed. In some implementations, responsive to a determination that the value104has not been updated, the precomputation process116may be deferred, such as by enqueuing the precomputation process116on a queue for containing deferred processes. For example, execution of the precomputation process116may be delayed for a length of time corresponding to an expected time by which, absent a failure of the modification process108, the modification process108will have modified an associated value104. Subsequent to the length of time, the precomputation process116may access the value104to determine the version identifier associated therewith. If the precomputation process116determines that the version identifier associated with a value104is less recent than the version identifier associated with the precomputation process116, the precomputation process116may fail. In some implementations, the precomputation process116may be executed using the unmodified value104to recalculate the dependent values104. For example, if a modification process108configured to replace a first value104“A” with a value104“B” fails, the precomputation process116may recalculate one or more values104dependent from the first value104using a status of “A” for the first value104.

In some implementations, if successful execution of the precomputation process116is not determined, the precomputation process116may be retried. For example, confirmation data122indicative of successful execution of the precomputation process116may be received prior to removal of the precomputation process116from the queue. Until successful execution of the precomputation process116is determined, the precomputation process116may be retried indefinitely to avoid inaccuracy in the database(s)102that may be otherwise introduced (e.g., if the modification process108is executed while the precomputation process116fails to update dependent values104).

FIG. 4is a block diagram400of a computing device402configured to support operation of the system100. The computing device402may include one or more devices storing or in communication with the databases102, one or more servers110, one or more user devices106, one or more queue devices208, one or more host devices202, other computing devices402, or computer readable storage media (CRSM) accessible to any of the computing devices402.

One or more power supplies404may be configured to provide electrical power suitable for operating the components in the computing device402. In some implementations, the power supply404may include a rechargeable battery, fuel cell, photovoltaic cell, power conditioning circuitry, and so forth.

The computing device402may include one or more hardware processor(s)406(processors) configured to execute one or more stored instructions. The processor(s)406may include one or more cores. One or more clocks408may provide information indicative of date, time, ticks, and so forth. For example, the processor(s)406may use data from the clock408to generate a timestamp, trigger a preprogrammed action, and so forth.

The computing device402may include one or more communication interfaces410, such as input/output (I/O) interfaces412, network interfaces414, and so forth. The communication interfaces410may enable the computing device402, or components thereof, to communicate with other devices or components. The I/O interfaces412may include interfaces such as Inter-Integrated Circuit (I2C), Serial Peripheral Interface bus (SPI), Universal Serial Bus (USB) as promulgated by the USB Implementers Forum, RS-232, and so forth.

The I/O interface(s)412may couple to one or more I/O devices416. The I/O devices416may include any manner of input device or output device associated with a database102, a user device106, a server110, a queue device208, a host device202, or another computing device402. For example, I/O devices416may include touch sensors, buttons, keyboards, mouse devices, cameras, microphones, scanners, displays, speakers, haptic devices, printers, and so forth. In some implementations, the I/O devices416may be physically incorporated with the computing device402or may be externally placed.

The network interfaces414may be configured to provide communications between the computing device402and other devices, such as the I/O devices416, routers, access points, and so forth. The network interfaces414may include devices configured to couple to one or more networks including local area networks (LANs), wireless LANs, wide area networks (WANs), wireless WANs, and so forth. For example, the network interfaces414may include devices compatible with Ethernet, Wi-Fi, Bluetooth, ZigBee, Z-Wave, 3G, 4G, LTE, and so forth.

The computing device402may include one or more busses or other internal communications hardware or software that allows for the transfer of data between the various modules and components of the computing device402.

As shown inFIG. 4, the computing device402may include one or more memories418. The memory418may include one or more computer readable storage media (CRSM). As described previously, the CRSM may be any one or more of an electronic storage medium, a magnetic storage medium, an optical storage medium, a quantum storage medium, a mechanical computer storage medium, and so forth. The memory418may provide storage of computer-readable instructions, data structures, program modules, and other data for the operation of the computing device402. A few example modules are shown stored in the memory418, although the same functionality may alternatively be implemented in hardware, firmware, or as a system on a chip (SoC).

The memory418may include one or more operating system (OS) modules420. The OS module420may be configured to manage hardware resource devices such as the I/O interfaces412, the network interfaces414, the I/O devices416, and to provide various services to applications or modules executing on the processors406. The OS module420may implement a variant of the FreeBSD operating system as promulgated by the FreeBSD Project; UNIX or a UNIX-like operating system; a variation of the Linux operating system as promulgated by Linus Torvalds; the Windows operating system from Microsoft Corporation of Redmond, Wash., USA; or other operating systems.

A data store422and one or more of the following modules may also be stored in the memory418. The modules may be executed as foreground applications, background tasks, daemons, and so forth. The data store422may use a flat file, database, linked list, tree, executable code, script, or other data structure to store information. In some implementations, the data store422or a portion of the data store422may be distributed across one or more other devices including the computing devices402, network attached storage devices, and so forth.

A communication module424may be configured to establish communications with one or more other computing devices402, such as user devices106, devices storing or managing the databases102, servers110, queue devices208, host devices202, remote CRSM, and so forth. The communications may be authenticated, encrypted, and so forth.

The memory418may also store the precomputation module112. The precomputation module112may be configured to determine one or more precomputation processes116associated with a modification process108. For example, the precomputation module112may determine a value104associated with a modification process108. The precomputation module112may further access database data114to determine one or more other values104dependent upon that value104and the relationship between the dependent value(s)104and the value104to be modified by the modification process104. Using the modification process108and the database data114, the precomputation module112may generate one or more precomputation processes116associated with the modification process108. In other implementations, the modification process108may include data indicative of one or more precomputation processes116associated therewith. The precomputation module112may access this data to determine the precomputation process(es)116. In still other implementations, one or more values104to be modified by the modification process108may include data indicative of one or more precomputation processes116associated therewith. For example, the values104may be configured to cause initiation of a precomputation process116upon modification thereof.

The memory418may also store the queue module118. The queue module118may be configured to enqueue precomputation processes116for access to databases102. For example, the queue module118may provide queue data120indicative of precomputation processes116to queue devices208, host devices202, servers110, or computing devices402associated with the databases102. In some implementations, the queue module118may provide the precomputation processes116to one or more computing devices402for enqueuing. In other implementations, the queue module118may maintain a queue of processes, such as precomputation or modification processes, for access to the databases102, provide confirmation data122to computing devices402indicative of successful enqueuing of processes, provide notifications to computing devices402indicative of executed or failed processes, and so forth.

The memory418may further store the modification module124. The modification module124may provide modification processes108or precomputation processes116to the databases102, determine execution of the modification processes108or precomputation processes116, modify values104in the databases102, modify version identifiers associated with the values104, and so forth. For example, responsive to receipt of confirmation data122indicating enqueuing of one or more precomputation processes116, the modification module124may provide a modification process108to one or more databases102, determine execution of the modification process108to modify one or more values104, and update the version identifiers associated with the modified values104. Subsequent execution of the precomputation process(es)116may include determination of the updated version identifiers prior to the precomputation process(es)116modifying values104dependent upon the values104modified by the modification process108.

The memory418is further depicted storing the backfill module126. The backfill module126may be used to generate, enqueue, or execute backfill processes to recalculate one or more values104in the databases102, subsequent to the modification of one or more other values104by modification processes108or precomputation processes116. For example, a modification process108may update a source value104, such as business logic or another type of data, the modification of which may affect a large number of values104within the database(s)102. In some implementations, one or more values104may include data indicative of a backfill process associated therewith, such that modification of the value(s)104results in the initiation of a backfill process by the backfill module126. In other implementations, a backfill process may be manually initiated, such as by a user device106. In still other implementations, a modification process108or precomputation process116may include data indicative of a backfill process associated therewith, such that execution of the modification process108or precomputation process116results in the initiation of a backfill process by the backfill module126. A backfill process may be configured to recalculate all or a portion of the values104in the database(s)102responsive to the modification of a source value104, independent of relationships between values104indicated in the database data114. In some implementations, the backfill module126may be configured to determine version identifiers associated with one or more values104and to refrain from modifying values104having version identifiers more recent than that associated with the backfill process. In other implementations, the backfill module126may be configured to apply other filters to the backfill process to include or exclude certain values104from modification. For example, a backfill process may refrain from modifying values104within selected databases102, values104relating to certain types of data, and so forth.

The memory418may store a partition assignment module426. The partition assignment module426may determine and modify partition assignments206associated with one or more host devices202. For example, the partition assignment module426may determine a host device202that may be used to monitor and provide partition assignments206to other host devices202. The partition assignment module426may be configured to monitor the status of host devices202to which partitions204have been assigned to determine failure or disassociation of one or more host devices202from one or more partitions204. Partitions204that have become disassociated from a host device202may be reassigned to other host devices202by the partition assignment module426. In some implementations, the partition assignment module426may monitor the number of processes accessing a partition204and the computation capacity associated therewith. If the computation capacity of one or more partitions204nears or exceeds the computation capacity of a host device202associated with the one or more partitions204, the partition assignment module426may reassign one or more partitions204from the host device202to other host devices202. The partition assignment module426may also be configured to determine one or more processes that were enqueued to a partition204that is not associated with the values104to which the process(es) pertain. Upon a determination that a process is enqueued to an incorrect partition204, the partition assignment module426may determine the correct partition204that is associated with the values104that pertain to the process and enqueue the process for access to the correct partition204.

The memory418may further store a resource lock module428. One or more of the values104and one or more of the partitions204may have locks associated therewith, to prevent simultaneous access to a value104or partition204by multiple processes. For example, the resource lock module428may ensure that a value104may not be accessed by multiple precomputation processes116simultaneously to avoid inaccuracies that may be introduced by concurrent operations. In some implementations, a host device202may be granted a lock to a partition204, and modification processes108or precomputation processes116attempting to access values104associated with that partition204may be provided to the host device202. In other implementations, the ability to monitor and modify partition assignments206associated with the host devices202may be restricted to a single host device202by granting a lock thereto. The resource lock module428may assign locks to processes and host devices202, revoke locks when processes or devices fail, and maintain a queue of processes or devices attempting to access locks. Lock data430indicative of processes (e.g., modification processes108or precomputation processes116) and devices to which locks have been granted, and indicative of processes and devices enqueued to receive locks, may be stored in the memory418.

Other modules432may also be present in the memory418. For example, encryption modules may be used to encrypt and decrypt communications between computing devices402. Output generation modules may be used to provide results of modification processes108or precomputation processes116to user devices106. User interface modules may receive modifications to the databases102, values104, and so forth, from one or more user devices106or other types of computing devices402. Other data434may include priority data, rules regarding constraints for access to certain databases102or certain values104, constraints regarding values104that may be modified by modification processes108and precomputation processes116, and so forth. Priority data may be used to determine an order in which access may be granted to one or more processes or computing devices402.

In different implementations, different computing devices402may have different capabilities or capacities. For example, the server(s)110may have significantly more processor406capability and memory418capacity compared to other computing devices402, such as devices associated with the databases102, user devices106, and so forth.

FIG. 5is a flow diagram500illustrating a method for confirming enqueuing of a precomputation process116prior to enqueuing a modification process108to prevent inaccuracy in values104dependent on the value104associated with the modification process108. Attempts to enqueue a process for access to one or more databases102may fail. In some implementations, if a modification process108is enqueued prior to a precomputation process116, and the enqueuing of the precomputation process116fails, the modification process108may modify a first value104. However, due to the failure to enqueue the precomputation process116, one or more values104dependent on the first value104may not be modified. Conversely, if the precomputation process116is enqueued prior to the modification process108, and the enqueuing of the modification process108fails, the precomputation process116may calculate dependent values104based on the unmodified first value104. As such, the values104in the databases102would not become inaccurate, and the modification process108may be subsequently retried. Therefore, enqueuing of the precomputation process116prior to enqueuing of an associated modification process108may facilitate maintenance of accurate values104within the databases102.

Block502receives a modification process108associated with a first value104(1). For example, one or more user devices106or other types of computing devices402may provide a modification process108to one or more servers110in communication with one or more databases102. The modification process108may be configured to add a value104to the database(s)102, delete a value104from the database(s)102, replace or modify a value104, merge multiple values104into a single value104, divide a single value104into multiple values104, and so forth. Values104within the database(s)102may include any manner of data, including tables, resources, textual data, audio data, video data, image data, and so forth. In some implementations, a modification process108may be accessed by one or more servers110for enqueuing and subsequent execution. For example, a modification process108may be stored in the server(s)110or a CRSM in communication therewith, and the server(s)110may be configured to access and initiate the modification process108, periodically or at a single time.

Block504determines a precomputation process116associated with at least one second value104(2), based at least partially on the modification process108associated with the first value104(1). For example, a relationship between the first value104(1) and one or more second values104(2) that depend upon the first value104(1) may be determined using database data114. A precomputation module112may generate a precomputation process116based on the modification process108, the first value104, the one or more second values104, the relationships between the values104, and so forth. In some implementations, a precomputation process116may be accessed by one or more servers110for enqueuing and subsequent execution. For example, a value104may have data indicative of a precomputation process116associated therewith, such that modification of the value104results in initiation of the precomputation process116. A modification process108may also have data indicative of a precomputation process116associated therewith, such that the precomputation process116may be determined from the received or accessed modification process108.

Block506attempts to enqueue the precomputation process116for access to the at least one second value104. The precomputation process116, or queue data120indicative thereof, may be provided to a queue device208, a host device202, or another computing device402associated with the database(s)102. When the precomputation process116has been successfully enqueued for access to the database(s)102, confirmation data122indicative of the enqueuing of the precomputation process116may be generated, e.g., by the precomputation module112.

Block508determines whether confirmation data122indicative of successful enqueuing of the precomputation process116was received, e.g., by the server(s)110. If the confirmation data122was not received, the modification process108may not be enqueued. Instead, block506may be repeated, and enqueuing of the precomputation process116may be attempted again. In other implementations, both the precomputation process116and the associated modification process108may fail, until a subsequent modification process108is received.

If the confirmation data122indicative of successful enqueuing of the precomputation process116is received, block510attempts to enqueue the modification process108for access to the first value104. The enqueued modification process108may subsequently be executed to modify the first value104. The enqueued precomputation process116may be executed subsequent to execution of the modification process108to modify the at least one second value104based on the modified first value104. If successful execution of the precomputation process116is not confirmed, the precomputation process116may be retried until it has been successfully executed to modify the at least one second value104.

FIG. 6is a flow diagram600illustrating a method for confirming execution of a modification process108prior to executing a precomputation process116to prevent inaccuracy in values104dependent on the value104associated with the modification process. For example, attempts to enqueue a modification process108for access to one or more databases102may fail or the execution of the modification process108may fail or be delayed. If the precomputation process116is executed prior to execution of the modification process108, the precomputation process116may calculate one or more dependent values104based on an unmodified value104. If the modification process108then subsequently modifies the unmodified value104, the values104in the database102may become inaccurate. As such, if it is determined that a modification process108has not been executed, execution of an associated precomputation process116may be delayed for a length of time sufficient to ensure that the modification process108has been executed or has failed. Therefore, execution of the modification process108prior to execution of an associated precomputation process116may facilitate maintenance of accurate values104within the databases102.

Block602enqueues a precomputation process116for access to a database102. As described previously, a precomputation module112may generate or access a precomputation process116and provide the precomputation process116, or queue data120indicative thereof, to a queue device208, host device202, or other computing device402associated with the database102. The precomputation process116may be configured to modify one or more values104in the database102based at least partially on a modified value104associated with a modification process108.

Block604receives confirmation data122indicative of successful enqueuing of the precomputation process116. Receipt of the confirmation data122may indicate that the enqueuing of the precomputation process116has not failed and that the precomputation process116will occur in the future, depending on the wait time associated with the queue.

Block606enqueues a modification process108for access to the database102responsive to receipt of the confirmation data122. As described previously, confirmation of successful enqueuing of the precomputation process116prior to enqueuing the modification process108may prevent creation of inaccurate values104in the database102. For example, if the enqueuing of the precomputation process116fails and the modification process108is executed, values104dependent upon the modified value104will not be updated based on the modification.

Block608attempts to execute the modification process108to modify a value104in the database102and update a version identifier associated with the value104. Once an enqueued modification process108is executed and granted access to the database102, such as through use of a resource lock, the modification process108may access and act upon a value104. For example, the modification process108may add a value104to a database102, remove a value104, set a value104to null, modify or replace the value104, merge multiple values104into a single value104, separate a single value104into multiple values104, and so forth. In some implementations, the value104may have a version identifier associated therewith, and the modification process108may access the version identifier. If the version identifier associated with the value104is more recent than a version identifier associated with the modification process108, this determination may indicate that a more recent process acted upon the value104during the time that the modification process108was generated, enqueued, or executed. Responsive to this determination, the modification process108may refrain from acting upon the value104. If the version identifier associated with the value104is equal to or less recent than that associated with the modification process108, or if the value104lacks a version identifier, the modification process108may act upon the value104. In addition to modifying the value104, the modification process108may update the version identifier associated with the value104. The updated version identifier may indicate that the modification process108has modified the value104.

Block610determines whether the precomputation process116determined the updated version identifier associated with the value104. When the precomputation process116is granted access to the database102, it may access the value104that was to be modified by the modification process108to determine the version identifier associated therewith. In some implementations, the precomputation process116may determine whether the version identifier associated with the modified value104is more recent or less recent than that associated with the precomputation process116. In other implementations, the precomputation process116may simply be configured to determine the presence or absence of an expected version identifier associated with the modification process108.

If the precomputation process116determines the updated version identifier, block612executes the precomputation process116to modify one or more additional values104based on the modified value104. For example, determination of the updated version identifier associated with the modified value104may indicate that the modification process108previously acted on the value104. Based on this determination, the precomputation process116may update values104dependent on the modified value104by recalculating the dependent values104based on the current, modified value104associated with the modification process108.

If the precomputation process116does not determine the updated version identifier, block614defers execution of the precomputation process116for a length of time corresponding to a process time associated with the modification process108. For example, the precomputation process116may be enqueued a subsequent time for future access to the database102. In some implementations, the precomputation process116may be enqueued in a separate queue configured to contain deferred processes. The length of time the precomputation process116is deferred may correspond to an expected length of time for enqueuing or execution of the modification process108.

Block616determines whether the updated version identifier was determined, subsequent to the length of time, by the precomputation process116. When the precomputation process116is again granted access to the database102, it may access the value104that was to be modified by the modification process108to determine the version identifier associated therewith. If the precomputation process116determines the updated version identifier, this determination may indicate that the modification process108was executed to modify the value104during the time that the precomputation process116was deferred. Responsive to this determination, block612may be performed, and the precomputation process116may be executed to modify one or more additional values104based on the modified value104.

If the updated version identifier is not determined by the precomputation process116, the modification process108may have failed. Block618executes the precomputation process116to modify one or more additional values104based on the unmodified value104. Because the precomputation process116performs modifications based on the current (e.g., unmodified) status of the value104, the values104in the database102do not become inaccurate. In other implementations, the precomputation process116may fail rather than performing modifications based on the unmodified value104.

FIG. 7is a flow diagram700illustrating a method for executing a backfill process and determining one or more values104to remain unmodified due to modification thereof by a more recent process. A backfill process may be manually executed or automatically triggered to modify one or more values104in a database102responsive to the modification of a value104that may affect one or more other values104. For example, modification of a value104representative of a sales tax rate for a particular region may affect every value104representing a precomputed sales price that includes sales tax for items sold in that region. As another example, modification of a value104representative of a fraud status of a vendor may affect every value104associated with an item sold by that vendor. As such, a backfill process may be used to recalculate potentially large numbers of values104when a source value104that affects numerous other values104is modified. In some implementations, a backfill process may recalculate all or a portion of values104within a database102independent of the relationship of each value104to the modified value104. Because a backfill process may require significant time and computational resources, backfill processes may be enqueued on a separate queue configured to contain backfill processes. One or more priority rules may be used to determine when processes from the backfill queue are executed in lieu of other processes attempting to access the database(s)102. In some implementations, to conserve time, computational resources, and prevent the backfill process from generating inaccurate values104in a database102, the backfill process may be configured to determine whether modification of one or more particular values104is necessary based on version identifiers associated therewith.

Block702executes a modification process108to modify a value104in a database102and a version identifier associated therewith. Block704determines the modified version identifier associated with the modified value104. For example, a precomputation process116may access the modified value104prior to execution thereof to determine the version identifier and confirm whether the value104was modified by the modification process108. Block706executes the precomputation process116, responsive to the modified version identifier, to modify one or more additional values104in the database102.

In the depicted implementation, one or more of the values104modified by the modification process108or the precomputation process116may be a source value104that affects one or more other values104in the database102. Block708enqueues and executes a backfill process to modify other values104in the database102, responsive to at least one of the modified values104. The backfill process may be configured to recalculate all or a portion of the values104in the database102. In some implementations, one or more filters may be applied to the backfill process. For example, the backfill process may be restricted to recalculating certain types of values104, values104having certain flags or categories, and so forth.

In block710, while the backfill process is enqueued or executing, at least one of the other values may be modified using an additional process, and the version identifier associated therewith may be updated. For example, while a backfill process is generated and enqueued on a backfill queue, one or more modification processes108or precomputation processes116may be generated, enqueued, and executed. The additional process(es) may modify values104that the backfill process is configured to modify. Because the additional process(es) were generated and executed subsequent to the time that the backfill process was generated, the values104modified by the additional process(es) may be more current than or identical to the modified values104that will be generated by the backfill process when executed.

Block712grants the backfill process access to a value104. To conserve time, computational resources, and prevent the backfill process from creating inaccurate values104or overwriting identical values104in the database102, the backfill process may determine the version identifier associated with the accessed value104. In some implementations, the backfill process may have a version identifier associated therewith, and the backfill process may be configured to determine whether the version identifier associated with the value104is more or less recent than the version identifier associated with the backfill process. In other implementations, the backfill process may be configured to detect the presence or absence of an expected version identifier. For example, the backfill process may be configured to access a value104, determine the version identifier associated with that value104, and compare the determined version identifier to an expected version identifier.

Block714determines whether the value104includes an updated version identifier. The presence of an updated version identifier may indicate that the value104was modified by a process subsequent to the generation of the backfill process. As such, modification of that value104by the backfill process may unnecessarily consume time and computation resources to generate an identical value104. Block716indicates the backfill process leaving the value104unmodified when it is determined that the value104includes an updated, associated version identifier. The backfill process may then access a subsequent value104, as indicated in block712. If the value104does not include an updated version identifier associated therewith, then the backfill process may modify the value104, as indicated in block718. The backfill process may then access a subsequent value104, as indicated in block712.