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

• US 10,657,184 B2
• Filed: 06/01/2018
• Issued: 05/19/2020
• Est. Priority Date: 08/24/2017
• Status: Active Grant

• Current Assignee: Deephaven Data Labs, LLC
• Original Assignee: Deephaven Data Labs, LLC
• Inventors: Kent, IV, David R., Caudy, Ryan, Wright, Charles, Teodorescu, Radu
• Primary Examiner(s): Phillips, III, Albert M
• Application Number:
  US15/996,108
• Publication Number:
  US 20190065543A1
• Time in Patent Office: 718 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 hardware processors, cause the one or more hardware processors to perform operations including;

constructing a computer data system update propagation graph; and

adding a feedback provider listener to the computer data system update propagation graph, wherein the feedback provider listener provides feedback updates to one or more feedback data fields of a cyclicality feedback provider object when changes to one or more update propagation graph data fields corresponding to 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 is configured to listen for one or more of:

one or more changes in one or more data source, one or more state change events, or one or more state update events.

3. The system of claim 1, wherein the operations further include instantiating an object of a class that has been configured to operate as a cyclicality feedback provider object.

4. The system of claim 1, wherein the cyclicality feedback provider is configured to provide feedback from one or more data sources within an update propagation graph to one or more other data sources at a higher level within the update propagation graph.

5. 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.

6. The system of claim 5, 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 clock-state controlled 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.

7. The system of claim 6, 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 next change notification message to a corresponding data source and repeating determining whether the priority queue is empty; and

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

8. The system of claim 7, 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.

9. The system of claim 8, 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.

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

constructing a computer data system update propagation graph; and

adding a feedback provider listener to the computer data system update propagation graph, wherein the feedback provider listener provides feedback updates to one or more feedback data fields of a cyclicality feedback provider object when changes to one or more update propagation graph data fields corresponding to 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.

11. The computer-implemented method of claim 10, wherein the cyclicality feedback provider object is configured to listen for one or more of:

one or more changes in one or more data source, one or more state change events, or one or more state update events.

12. The computer-implemented method of claim 10, further comprising instantiating an object of a class that has been configured to operate as a cyclicality feedback provider object.

13. The computer-implemented method of claim 10, wherein the cyclicality feedback provider is configured to provide feedback from one or more data sources within an update propagation graph to one or more other data sources at a higher level within the update propagation graph.

14. The computer-implemented method of claim 10, 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.

15. The computer-implemented method of claim 14, 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 clock-state controlled 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.

16. The computer-implemented method of claim 15, 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 next change notification message to a corresponding data source and repeating determining whether the priority queue is empty; and

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

17. The computer-implemented method of claim 16, 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.

18. The computer-implemented method of claim 17, 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.

19. 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 computer data system update propagation graph; and

adding a feedback provider listener to the computer data system update propagation graph, wherein the feedback provider listener provides feedback updates to one or more feedback data fields of a cyclicality feedback provider object when changes to one or more update propagation graph data fields corresponding to 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.

20. The nontransitory computer readable medium of claim 19, wherein the cyclicality feedback provider object is configured to listen for one or more of:

one or more changes in one or more data source, one or more state change events, or one or more state update events.