US-12619600-B2 - Systems and methods for scalable database technology

Abstract

Methods and systems are described for increasing scalability in cooperative processing systems by reducing issues due to contention (e.g., waiting or queueing for shared resources) and coherency (e.g., delay for data to become consistent) using reciprocal delta tables. The system allows for both proposing and committing changes to a state table without the changes being executed on the state table via recording changes in a series of transactions with delta tables. By eliminating a need to wait for unlocking of a state table as changes are executed, downtime for a client will reduce and processing can be more efficient.

Inventors

• Dennis Flanagan

Assignees

• Dennis Flanagan

Dates

Publication Date

20260505

Application Date

20240712

Claims (20)

1. 1 . A computer-implemented method of committing proposed changes to a relational database as branches to the relational database, the method comprising: accessing, by control circuitry, a state table stored in non-transitory memory; determining a first self-validating delta table based on a first proposed change to the state table at a first timestamp, wherein the first self-validating delta table comprises a first delta value equal to the first proposed change to the state table and a first revert value set to a first current value of the state table; generating a first pointer to a first branch comprising the first self-validating delta table for the first proposed change to the state table; determining a second self-validating delta table based on a second proposed change to the state table at a second timestamp, wherein the second self-validating delta table comprises a second delta value equal to the second proposed change to the state table and a second revert value set to a second current value of the state table; generating a second pointer to a second branch comprising the second self-validating delta table for the second proposed change to the state table; determining whether the first timestamp is before the second timestamp; and based on determining the first timestamp is before the second timestamp, placing on the state table, without locking the state table, the first pointer to the first branch indicating the first proposed change is committed to the state table.
2. 2 . The method of claim 1 further comprising: determining whether there is a conflict with the first self-validating delta table and the second self-validating delta table without locking the state table; and based on determining there is no conflict with the first self-validating delta table and the second self-validating delta table, placing on the state table, without locking the state table, the second pointer to the second branch indicating the second proposed change is committed to the state table.
3. 3 . The method of claim 2 , wherein the placing on the state table, without locking the state table, the first pointer to the first branch is performed by a first server and placing on the state table, without locking the state table, the second pointer to the second branch is performed by a second server different from the first server.
4. 4 . The method of claim 1 further comprising: determining whether there is a conflict with the first self-validating delta table and the second self-validating delta table without locking the state table; and based on determining there is a conflict with the first self-validating delta table and the second self-validating delta table, providing a notification that there is conflict that needs to be resolved.
5. 5 . The method of claim 1 further comprising: determining a third self-validating delta table based on a third proposed change to the state table at a third timestamp after the second timestamp, wherein the third self-validating delta table comprises a third delta value and a third revert value; generating a third pointer to a third branch comprising the third self-validating delta table for the third proposed change to the state table; determining whether there is a conflict with the second self-validating delta table and the third self-validating delta table without locking the state table; and based on determining there is no conflict with the second self-validating delta table and the third self-validating delta table, generating a combined branch by combining the third branch with the second branch, wherein the combined branch comprises a combined self-validating delta table.
6. 6 . The method of claim 5 further comprising: determining whether there is a conflict with the first self-validating delta table and the combined self-validating delta table without locking the state table; and after determining there is no conflict with the first self-validating delta table and the combined self-validating delta table, placing on the state table, without locking the state table, the second pointer to the second branch and the third pointer to the third branch to indicate the second proposed change and the third proposed change are committed to the state table.
7. 7 . The method of claim 5 further comprising: determining whether there is a conflict with the first self-validating delta table and the combined self-validating delta table without locking the state table; based on determining there is a conflict with the first self-validating delta table and the combined self-validating delta table, providing a notification that there is conflict that needs to be resolved; and placing on the state table, without locking the state table, the second pointer to the second branch indicating the second proposed change is committed to the state table.
8. 8 . The method of claim 1 , wherein the placing on the state table, without locking the state table, the first pointer to the first branch further comprises determining whether there is a conflict with the first self-validating delta table and the state table without locking the state table.
9. 9 . The method of claim 1 further comprising: determining a fourth self-validating delta table based on a fourth proposed change to the state table at a fourth timestamp, wherein the fourth self-validating delta table comprises a fourth delta value and a fourth revert value; generating a fourth pointer to a fourth branch comprising the second self-validating delta table for the fourth proposed change to the state table; determining that the fourth timestamp and the second timestamp occur at a same time; determining there is a conflict with the second self-validating delta table and the fourth self-validating delta table without locking the state table; and based on determining that the fourth timestamp and the second timestamp occur at a same time and there is a conflict with the second self-validating delta table and the fourth self-validating delta table: (1) providing a notification that there is conflict that needs to be resolved; and (2) placing on the state table, without locking the state table, the fourth pointer to the fourth branch indicating the fourth proposed change is committed to the state table based upon the fourth self-validating delta table having a higher assigned sequence value.
10. 10 . The method of claim 1 wherein at least one of the first delta value, the first revert value, the second delta value, or the second revert value is a null value.
11. 11 . A computer-implemented method of committing proposed changes to a relational database as branches to the relational database, the method comprising: accessing, by control circuitry, a state table stored in non-transitory memory; determining a first self-validating delta table based on a first proposed change to the state table at a first timestamp, wherein the first self-validating delta table comprises a first delta value equal to the first proposed change to the state table and a first revert value set to a first current value of the state table; generating a first pointer to a first branch comprising the first self-validating delta table for the first proposed change to the state table; determining a second self-validating delta table based on a second proposed change to the state table at a second timestamp after the first timestamp, wherein the second self-validating delta table comprises a second delta value equal to the second proposed change to the state table and a second revert value set to a second current value of the state table; generating a second pointer to a second branch comprising the second self-validating delta table for the second proposed change to the state table; determining whether there is a conflict with the first self-validating delta table and the second self-validating delta table without locking the state table; and after determining there is no conflict with the first self-validating delta table and the second self-validating delta table: placing on the state table, without locking the state table, the first pointer to the first branch indicating the first proposed change is committed to the state table; and placing on the state table, without locking the state table, the second pointer to the second branch indicating the second proposed change is committed to the state table.
12. 12 . The method of claim 11 , wherein the placing on the state table, without locking the state table, the first pointer to the first branch comprises placing on the state table, without locking the state table, the first pointer to the first branch after determining, without locking the state table, there is no conflict with the first self-validating delta table and the state table.
13. 13 . The method of claim 11 further comprising placing on the state table, without locking the state table, the second pointer to the second branch after determining, without locking the state table, there is no conflict with the second self-validating delta table and the state table.
14. 14 . The method of claim 11 , wherein the placing on the state table, without locking the state table, the second pointer to the second branch further comprises: determining a third self-validating delta table based on a third proposed change to the state table at a third timestamp after the first timestamp, wherein the third self-validating delta table comprises a third delta value and a third revert value; generating a third pointer to a third branch comprising the third self-validating delta table for the third proposed change to the state table; determining whether there is a conflict with the second self-validating delta table and the third self-validating delta table without locking the state table; based on determining there is no conflict with the second self-validating delta table and the third self-validating delta table, generating a combined branch by combining the third branch with the second branch, wherein the combined branch comprises a combined self-validating delta table; determining whether there is a conflict with the first self-validating delta table and the combined self-validating delta table without locking the state table; and after determining there is no conflict with the first self-validating delta table and the combined self-validating delta table, placing on the state table, without locking the state table, the second pointer to the second branch and the third pointer to the third branch to indicate the second proposed change and the third proposed change are committed to the state table.
15. 15 . The method of claim 11 , wherein the placing on the state table, without locking the state table, the second pointer to the second branch further comprises: determining a fourth self-validating delta table based on a fourth proposed change to the state table at a fourth timestamp before the second timestamp, wherein the fourth self-validating delta table comprises a fourth delta value and a fourth revert value; generating a fourth pointer to a third branch comprising the fourth self-validating delta table for the fourth proposed change to the state table; determining, without locking the state table, whether there is a conflict with the second self-validating delta table and the fourth self-validating delta table; based on determining there is a conflict with the second self-validating delta table and the fourth self-validating delta table, generating a notification that there is a conflict.
16. 16 . The method of claim 15 further comprising placing on the state table, without locking the state table, the fourth pointer to the fourth branch indicating the fourth proposed change is committed to the state table.
17. 17 . A computer-implemented method of committing proposed changes to a relational database as branches to the relational database, the method comprising: accessing, by control circuitry, a state table stored in non-transitory memory; determining a first self-validating delta table based on a first proposed change to the state table at a first timestamp, wherein the first self-validating delta table comprises a first delta value equal to the first proposed change to the state table and a first revert value set to a first current value of the state table; generating a first pointer to a first branch comprising the first self-validating delta table for the first proposed change to the state table; determining, without locking the state table, there is no conflict with the first self-validating delta table and the state table; and placing on the state table, without locking the state table, the first pointer to the first branch indicating the first proposed change is committed to the state table.
18. 18 . The method of claim 17 , wherein accessing, by control circuitry, the state table stored in non-transitory memory further comprises: determining a second self-validating delta table based on a second proposed change to the state table at a second timestamp after the first timestamp, wherein the second self-validating delta table comprises a second delta value and a second revert value; generating a second pointer to a second branch comprising the second self-validating delta table and the second time index for the second proposed change to the state table; and the method further comprises: determining whether there is a conflict with the first self-validating delta table and the second self-validating delta table without locking the state table; and placing on the state table, without locking the state table, the second pointer to the second branch indicating the second proposed change is committed to the state table based on determining there is no conflict with the first self-validating delta table and the second self-validating delta table.
19. 19 . The method of claim 17 , wherein accessing, by control circuitry, the state table stored in non-transitory memory further comprises: determining a third self-validating delta table based on a third proposed change to the state table at a third time index, wherein the third self-validating delta table comprises a third delta value and a third revert value; generating a third pointer to a third branch comprising the third self-validating delta table and the third time index for the third proposed change to the state table; wherein determining, without locking the state table, there is no conflict with the first self-validating delta table and the state table further comprises: determining whether there is a conflict with the first self-validating delta table and the third self-validating delta table without locking the state table; generating a combined branch by combining the third branch with the first branch, wherein the combined branch comprises a combined self-validating delta table, based on determining there is no conflict with the first self-validating delta table and the third self-validating delta table; determining whether there is a conflict with the state table and the combined self-validating delta table without locking the state table; placing on the state table, without locking the state table, the first pointer to the first branch and the third pointer to the third branch to indicate the first proposed change and the third proposed change are committed to the state table.
20. 20 . The method of claim 17 , wherein accessing, by control circuitry, the state table stored in non-transitory memory further comprises: determining a fourth self-validating delta table based on a fourth proposed change to the state table at a fourth time index, wherein the fourth self-validating delta table comprises a fourth delta value and a fourth revert value; wherein determining, without locking the state table, there is no conflict with the first self-validating delta table and the state table further comprises determining whether there is a conflict with the first self-validating delta table and the fourth self-validating delta table without locking the state table; and wherein placing on the state table, without locking the state table, the first pointer to the first branch further comprises, based on determining there is a conflict with the first self-validating delta table and the fourth self-validating delta table, generating a notification that there is a conflict.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS This patent application is a continuation of U.S. patent application Ser. No. 16/456,787 filed Jun. 28, 2019, issued as U.S. Pat. No. 12,038,909, which is hereby incorporated by reference herein in its entirety. BACKGROUND The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the inventor hereof, to the extent the work is described in this background section, as well as aspects of the description that does not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as being prior art against the present disclosure. The present disclosure relates to systems for cooperative processing, and more particularly to scalability in cooperative processing systems. Moore's Law, which effectively states that processor speeds, or overall processing power for a computer, will double every two years, has predicted processing speeds for the last half-century. This processing power is typically tied to the number of transistors, but as the size of transistors shrinks to its physical limits (e.g., atomic scales), the increasing processing power predicted by Moore's Law appears to be approaching its limit. Likewise, the amounts of data in need of processing for evolving fields such as advanced analytics, artificial intelligence, and Big Data are exponentially increasing size. In view of the ever-increasing demand for more processing power and the physical limitations on processing power for a given computer, one solution is to use an increasing number of processors working in parallel. For example, a given processor may break a given task into a series of sub-tasks. Each sub-task, which itself may require immense amounts of data processing, may be assigned to individual processors. However, the use of multiple processors to compensate for limits to processing power of a single computer also has limits. For example, in order to update data with reliability (e.g., in case of failure of the system and/or individual clients) and to prevent errors (e.g., from multiple clients accessing and/or modifying the data set concurrently), a system must work through proposed changes to that data through a series of transactions that are atomic, consistent, isolated and durable (“ACID”). Prior to combining, each participating dataset must be validated. Validating the datasets allows a system to detect any potential problems with field names (e.g., invalid characters in field names) as well as detecting conflicting values. For example, if conflicting values are detected, a system must resolve these values. Typically, resolving these values is based on a time-stamp or version number associated with the proposed dataset. The earlier time-stamp or version number is typically used to determine which conflicting value governs. With respect to processes performed on a common dataset (e.g., a state table), a system may work through a queue of proposals (e.g., delta tables representing the results of sub-tasks). A delta table is a table that shows the changes with respect to the initial state table. In delta tables, each record for a proposed delta table is validated against a corresponding record of the state table. Once the values have been validated, the proposed delta table is committed, and the values of the state table are updated based on values (proposed changes) of the delta table. During this time, the state table is locked. Once a proposal is executed or committed on the initial state table, which now corresponds to the state table after the delta table is committed, the now-modified state table is released. A system retrieves the next proposed delta table in the queue, which corresponds to the next sub-task processed by the next client. To process the next sub-task, a modified state table is now released to start validation and combination process with another delta table. Thus, by working through a queue for each proposal, which corresponds to a respective sub-task, a system processes an overall task through the use of multiple parallel clients. However, because the initial state table must remain locked, as additional processors are added to a system the queue of processors waiting to access the state table increases, and the system experiences diminishing rate of return for processing power. That is, such a system experiences scalability issues due to contention (e.g., waiting or queueing for shared resources) and coherency (e.g., delay for data to become consistent). SUMMARY Accordingly, methods and systems are disclosed herein for increasing scalability in cooperative processing systems by reducing issues due to contention (e.g., waiting or queueing for shared resources) and coherency (e.g., delay for data to become consistent). Embodiments allow for concurrent processing without an initial dataset being locked. That is, embodiments may allow for both the proposal and committing of