Computer data system data source having an update propagation graph with feedback cyclicality

• US 10,002,154 B1
• Filed: 11/14/2017
• Issued: 06/19/2018
• Est. Priority Date: 08/24/2017
• Status: Active Grant

• Current Assignee: Deephaven Data Labs, LLC
• Original Assignee: Illumon LLC
• Inventors: Kent, IV, David R., Caudy, Ryan, Wright, Charles, Teodorescu, Radu
• Primary Examiner(s): Phillips, III, Albert
• Application Number:
  US15/813,142
• Time in Patent Office: 217 Days
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/235 Update request formulation
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2372 Updates performed during offline database operations
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 16/489 using time information
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

Described are methods, systems and computer readable media for data source refreshing using an update propagation graph with feedback cyclicality.

Claims

1. A system for updating a data object using an update propagation graph having a cyclicality feedback provider, the system comprising:

one or more hardware processors coupled to a nontransitory computer readable medium having stored thereon software instructions that, when executed by the one or more processors, cause the one or more processors to perform operations including;

constructing a cyclicality feedback provider including a cyclicality feedback provider object including one or more feedback data fields;

obtaining a reference to the cyclicality feedback provider object;

constructing a computer data system update propagation graph having one or more update propagation graph data fields that correspond to the one or more feedback data fields; and

adding a feedback provider listener to the computer data system update propagation graph, wherein the feedback provider listener provides feedback updates to the one or more feedback data fields of the cyclicality feedback provider object when changes to the one or more update propagation graph data fields corresponding to the one or more feedback data fields are detected, and wherein the feedback updates are provided to the one or more feedback data fields of the cyclicality feedback provider object based on a state of a logical clock and on completion of update processing for a given logical clock cycle.

2. The system of claim 1, wherein the cyclicality feedback provider object includes a computer data system table object.

3. The system of claim 1, wherein the update propagation graph includes a hybrid directed acyclic graph having a clock-state controlled cyclicality feedback provided by the cyclicality feedback provider and a state of a logical clock.

4. The system of claim 3, wherein the operations further include:

determining that a logical clock has transitioned to an update state;

processing events and updates to data sources of the update propagation graph for a current logical clock cycle, wherein processing the events and updates are performed on the hybrid directed acyclic graph as if the cyclicality feedback is not present; and

after the processing events and updates has completed, providing events and updates from the cyclicality feedback provider object to one or more data objects within the update propagation graph, wherein the events and updates from the cyclicality feedback provider object will be processed through the update propagation graph in a next logical clock cycle.

5. The system of claim 4, wherein processing events and updates to the data sources includes:

invoking a data source refresh method for a data source for which changes are being processed;

determining whether a priority queue for the data source is empty;

when the priority queue is not empty, retrieving a next change notification message from the priority queue and delivering the change notification to a corresponding data source and repeating determining whether the priority is queue is empty; and

when the priority queue is empty, setting the logical clock to an idle state.

6. The system of claim 5, wherein the operations further include:

performing a backtesting operation by providing predetermined input data to the update propagation graph as one or more events and updates to one or more data sources; and

receiving output results from the update propagation graph for each logical clock cycle.

7. The system of claim 6, wherein the operations further include:

comparing the output results received from the update propagation graph with one or more reference values; and

generating an output signal based on the comparing.

8. A computer-implemented method for updating a data object using an update propagation graph having a cyclicality feedback provider, the method comprising:

constructing a cyclicality feedback provider including a cyclicality feedback provider object including one or more feedback data fields;

obtaining a reference to the cyclicality feedback provider object;

constructing a computer data system update propagation graph having one or more update propagation graph data fields that correspond to the one or more feedback data fields; and

adding a feedback provider listener to the computer data system update propagation graph, wherein the feedback provider listener provides feedback updates to the one or more feedback data fields of the cyclicality feedback provider object when changes to the one or more update propagation graph data fields corresponding to the one or more feedback data fields are detected, and wherein the feedback updates are provided to the one or more feedback data fields of the cyclicality feedback provider object based on a state of a logical clock and on completion of update processing for a given logical clock cycle.

9. The computer-implemented method of claim 8, wherein the cyclicality feedback provider object includes a computer data system table object.

10. The computer-implemented method of claim 8, wherein the update propagation graph includes a hybrid directed acyclic graph having a clock-state controlled cyclicality feedback provided by the cyclicality feedback provider and a state of a logical clock.

11. The computer-implemented method of claim 10, further comprising:

determining that a logical clock has transitioned to an update state;

processing events and updates to data sources of the update propagation graph for a current logical clock cycle, wherein processing the events and updates are performed on the hybrid directed acyclic graph as if the cyclicality feedback is not present; and

after the processing events and updates has completed, providing events and updates from the cyclicality feedback provider object to one or more data objects within the update propagation graph, wherein the events and updates from the cyclicality feedback provider object will be processed through the update propagation graph in a next logical clock cycle.

12. The computer-implemented method of claim 11, wherein processing events and updates to the data sources includes:

invoking a data source refresh method for a data source for which changes are being processed;

determining whether a priority queue for the data source is empty;

when the priority queue is not empty, retrieving a next change notification message from the priority queue and delivering the change notification to a corresponding data source and repeating determining whether the priority is queue is empty; and

when the priority queue is empty, setting the logical clock to an idle state.

13. The computer-implemented method of claim 12, further comprising:

performing a backtesting operation by providing predetermined input data to the update propagation graph as one or more events and updates to one or more data sources; and

receiving output results from the update propagation graph for each logical clock cycle.

14. The computer-implemented method of claim 13, further comprising:

comparing the output results received from the update propagation graph with one or more reference values; and

generating an output signal based on the comparing.

15. A nontransitory computer readable medium having stored thereon software instructions that, when executed by one or more processors, cause the one or more processors to perform operations including:

constructing a cyclicality feedback provider including a cyclicality feedback provider object including one or more feedback data fields;

obtaining a reference to the cyclicality feedback provider object;

constructing a computer data system update propagation graph having one or more update propagation graph data fields that correspond to the one or more feedback data fields; and

adding a feedback provider listener to the computer data system update propagation graph, wherein the feedback provider listener provides feedback updates to the one or more feedback data fields of the cyclicality feedback provider object when changes to the one or more update propagation graph data fields corresponding to the one or more feedback data fields are detected, and wherein the feedback updates are provided to the one or more feedback data fields of the cyclicality feedback provider object based on a state of a logical clock and on completion of update processing for a given logical clock cycle.

16. The nontransitory computer readable medium of claim 15, wherein the cyclicality feedback provider object includes a computer data system table object.

17. The nontransitory computer readable medium of claim 15, wherein the update propagation graph includes a hybrid directed acyclic graph having a clock-state controlled cyclicality feedback provided by the cyclicality feedback provider and a state of a logical clock.

18. The nontransitory computer readable medium of claim 17, wherein the operations further include:

determining that a logical clock has transitioned to an update state;

processing events and updates to data sources of the update propagation graph for a current logical clock cycle, wherein processing the events and updates are performed on the hybrid directed acyclic graph as if the cyclicality feedback is not present; and

after the processing events and updates has completed, providing events and updates from the cyclicality feedback provider object to one or more data objects within the update propagation graph, wherein the events and updates from the cyclicality feedback provider object will be processed through the update propagation graph in a next logical clock cycle.

19. The nontransitory computer readable medium of claim 18, wherein processing events and updates to the data sources includes:

invoking a data source refresh method for a data source for which changes are being processed;

determining whether a priority queue for the data source is empty;

when the priority queue is not empty, retrieving a next change notification message from the priority queue and delivering the change notification to a corresponding data source and repeating determining whether the priority is queue is empty; and

when the priority queue is empty, setting the logical clock to an idle state.

20. The nontransitory computer readable medium of claim 19, wherein the operations further include:

performing a backtesting operation by providing predetermined input data to the update propagation graph as one or more events and updates to one or more data sources;

receiving output results from the update propagation graph for each logical clock cycle;

comparing the output results received from the update propagation graph with one or more reference values; and

generating an output signal based on the comparing.