Historical data replay utilizing a computer system

• US 10,241,960 B2
• Filed: 05/14/2016
• Issued: 03/26/2019
• Est. Priority Date: 05/14/2015
• Status: Active Grant

• Current Assignee: Deephaven Data Labs, LLC
• Original Assignee: Deephaven Data Labs, LLC
• Inventors: Kent, IV, David R., Caudy, Ryan, Wright, Charles, Vydrov, Oleg, Teodorescu, Radu
• Primary Examiner(s): Richardson, James E
• Application Number:
  US15/155,010
• Publication Number:
  US 20160335361A1
• Time in Patent Office: 1,046 Days
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/1483 using an access-table, e.g. matrix or list
• CPC Class Codes: G06F 15/17331 Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/144 Query formulation
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/2291 : User-Defined Types; Storage management thereof
• CPC Class Codes: G06F 16/23 : Updating
• CPC Class Codes: G06F 16/2308 : Concurrency control transaction processing G06F9/466
• 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/2379 : Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/242 : Query formulation
• CPC Class Codes: G06F 16/2428 : Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: G06F 16/245 : Query processing
• CPC Class Codes: G06F 16/2453 : Query optimisation
• CPC Class Codes: G06F 16/24534 : Query rewriting; Transformation
• CPC Class Codes: G06F 16/24535 : of sub-queries or views
• CPC Class Codes: G06F 16/24537 : of operators
• CPC Class Codes: G06F 16/24539 : using cached or materialised query results
• CPC Class Codes: G06F 16/2455 : Query execution
• CPC Class Codes: G06F 16/24553 : of query operations
• CPC Class Codes: G06F 16/2456 : Join operations
• CPC Class Codes: G06F 16/24561 : Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/2457 : with adaptation to user needs
• CPC Class Codes: G06F 16/24575 : using context
• CPC Class Codes: G06F 16/248 : Presentation of query results
• CPC Class Codes: G06F 16/254 : Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• 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/278 : Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/285 : Clustering or classification
• CPC Class Codes: G06F 16/9024 : Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/907 : Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/951 : Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 : Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 : Presentation of query results
• CPC Class Codes: G06F 16/9566 : URL specific, e.g. using aliases, detecting broken or misspelled links
• CPC Class Codes: G06F 16/9574 : of access to content, e.g. by caching
• CPC Class Codes: G06F 17/40 : Data acquisition and logging for input to computer G06F3/00
• CPC Class Codes: G06F 21/00 : Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
• CPC Class Codes: G06F 21/6209 : to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 2201/805 : Real-time
• CPC Class Codes: G06F 2201/84 : Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2212/1052 : Security improvement
• CPC Class Codes: G06F 2212/154 : Networked environment
• CPC Class Codes: G06F 2212/163 : Server or database system
• CPC Class Codes: G06F 2212/60 : Details of cache memory
• 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: G06F 3/0482 : Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06F 3/0483 : Interaction with page-structured environments, e.g. book metaphor
• CPC Class Codes: G06F 3/04847 : Interaction techniques to control parameter settings, e.g. interaction with sliders or dials
• CPC Class Codes: G06F 3/0485 : Scrolling or panning
• CPC Class Codes: G06F 3/04895 : Guidance during keyboard input operation, e.g. prompting
• CPC Class Codes: G06F 3/0605 : by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0656 : Data buffering arrangements
• CPC Class Codes: G06F 3/067 : Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 40/117 : Tagging; Marking up details of markup languages G06F40/143; Designating a block; Setting of attributes style sheets, e.g. eXtensible Stylesheet Language Transformation [XSLT], G06F40/154
• CPC Class Codes: G06F 40/134 : Hyperlinking
• CPC Class Codes: G06F 40/166 : Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/174 : Form filling; Merging
• CPC Class Codes: G06F 40/177 : of tables; using ruled lines
• CPC Class Codes: G06F 40/18 : of spreadsheets form-filling G06F40/174
• CPC Class Codes: G06F 40/183 : Tabulation, i.e. one-dimensional positioning
• CPC Class Codes: G06F 40/216 : using statistical methods
• CPC Class Codes: G06F 40/274 : Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G06F 8/30 : Creation or generation of source code
• CPC Class Codes: G06F 8/41 : Compilation
• CPC Class Codes: G06F 8/427 : Parsing
• CPC Class Codes: G06F 8/60 : Software deployment
• CPC Class Codes: G06Q 40/04 : Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: H04L 12/18 : for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 51/046 : Interoperability with other network applications or services
• CPC Class Codes: H04L 51/212 : using filtering or selective blocking
• CPC Class Codes: H04L 61/5069 : for group communication, multicast communication or broadcast communication
• CPC Class Codes: H04L 63/101 : Access control lists [ACL]
• CPC Class Codes: H04L 63/102 : Entity profiles
• CPC Class Codes: H04L 67/01 : Protocols
• CPC Class Codes: H04L 67/1001 : for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/141 : Setup of application sessions admission control or resource allocation in data switching networks H04L47/70
• CPC Class Codes: H04L 67/34 : involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416
• CPC Class Codes: H04L 67/56 : Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/566 : Grouping or aggregating service requests, e.g. for unified processing
• CPC Class Codes: H04L 67/568 : Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/5681 : Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 69/16 : Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

Abstract

Described are methods, systems and computer readable media for simulated replay of data using a computer system.

Claims

1. A computer system for using a production environment to execute query programs in a simulated mode, the system comprising:

one or more processors;

computer readable storage coupled to the one or more processors, the computer readable storage having stored thereon instructions that, when executed by the one or more processors, cause the one or more processors to perform operations including;

establishing a digital connection between a query processor and a query client device;

receiving real-time data and storing historical data in the production environment;

receiving at the query processor, a first query program with one or more first configuration instructions from the query client device;

the query processor determining from the one or more first configuration instructions from the query client device that a real-time mode is to be used when executing the first query program;

the query processor executing, in the real-time mode, the first query program in the production environment using production system code;

receiving at the query processor, a second query program with one or more second configuration instructions from the query client device;

the query processor parsing the one or more second configuration instructions;

the query processor determining from the one or more second configuration instructions from the query client device that a simulation mode is to be used when executing the second query program;

the query processor extracting a simulation period from the one or more second configuration instructions;

the query processor determining from the one or more second configuration instructions a simulation clock cycle and a clock cycle speed; and

while the system receives new real-time data and stores new historical data in the production environment, the query processor switching modes and executing, in the simulation mode, the second query program in the production environment using the same production system code used to execute the first query program in the real-time mode, the executing the second query program comprising;

preventing the second query program from accessing the new real-time data;

generating an update propagation graph (UPG) based on the second query program, the UPG having a plurality of nodes each corresponding to one of a plurality of data objects referenced by the second query program, the UPG having a structure representing the dependencies between the plurality of data objects in the second query program;

requesting real-time data simulated from the historical data stored in the production environment; and

for each clock cycle for the simulation period;

starting a simulated clock cycle;

determining data changes in the clock cycle;

applying the data changes according to an order determined by the UPG; and

updating dynamic simulated real-time action system dynamic tables.

2. The system of claim 1, the operations further comprising:

requesting, by the one or more processors, non-action system generated historical data; and

creating, by the one or more processors, anti-look-ahead bias historical filters.

3. The system of claim 2, the processing further comprising:

applying, by the query processor, the anti-look-ahead bias historical data filters to the requested non-action system generated real-time data simulated from historical data.

4. The system of claim 1, the operations further comprising:

when a simulated real-time action system does not exist, constructing, by the one or more processors, a simulated real-time action system;

the query processor connecting to the simulated real-time action system; and

generating, by the one or more processor, simulated real-time action system data.

5. The system of claim 1, wherein the requesting real-time data simulated from historical data includes the query processor sorting the data prior to use by sequence ID or by time stamp for only the current clock cycle.

6. The system of claim 1, wherein the first query program is different than the second query program.

7. The system of claim 1, wherein the one or more first configuration instructions are different than the one or more second configuration instructions.

8. The system of claim 1,

wherein the real-time data are simulated from historical data by reading a copy of underlying historical data and applying, after the reading, one or more changes to the read copy of underlying historical data;

and

wherein the underlying historical data are unchanged by the reading and the applying.

9. The system of claim 1, wherein the historical data includes data that were never available in a real-time environment.

10. A method for using a computer system in a production environment to execute query programs in a simulated mode, the method comprising:

establishing a digital connection between a query processor and a query client device;

the computer system receiving real-time data and storing historical data in the production environment;

receiving at the query processor, a first query program with one or more first configuration instructions from the query client device;

the query processor determining from the one or more first configuration instructions from the query client device that a real-time mode is to be used when executing the first query program;

the query processor executing, in the real-time mode, the first query program in the production environment using production system code;

receiving at the query processor, a second query program with one or more second configuration instructions from the query client device;

the query processor parsing the one or more second configuration instructions;

the query processor determining from the one or more second configuration instructions from the query client device that a simulation mode is to be used when executing the second query program;

the query processor extracting a simulation period from the one or more second configuration instructions; and

while the system receives new real-time data and stores new historical data in the production environment, the query processor switching modes and executing, in the simulation mode, the second query program in the production environment using the same production system code used to execute the first query program in the real-time mode, the executing the second query program comprising;

preventing the second query program from accessing the new real-time data; and

requesting real-time data simulated from the historical data stored in the production environment.

11. The method of claim 10, further comprising:

requesting non-action system generated historical data; and

creating anti-look-ahead bias historical filters.

12. The method of claim 11, further comprising:

applying the anti-look-ahead bias historical data filters to the requested non-action system generated real-time data simulated from historical data.

13. The method of claim 10, further comprising:

when a simulated real-time action system does not exist, constructing a simulated real-time action system;

the query processor connecting to the simulated real-time action system; and

generating simulated real-time action system data.

14. The method of claim 13, further comprising replacing the simulated real-time action system with a second simulated real-time action system.

15. The method of claim 10, further comprising:

the query processor determining from the parsing of the one or more second configuration instructions, a simulation clock cycle and a clock cycle speed;

for each clock cycle for the simulation period, the query processor;

starting a simulated clock cycle;

determining any data changes in the clock cycle;

applying the data changes to an update propagation graph; and

updating dynamic simulated real-time action system dynamic tables.

16. The method of claim 10, wherein real-time data simulated from historical data includes sorting the data by sequence ID or by time stamp for only the current clock cycle prior to use.

17. The method of claim 10,

wherein the real-time data are simulated from historical data by reading a copy of underlying historical data and applying, after the reading, one or more changes to the read copy of underlying historical data;

and

wherein the underlying historical data are unchanged by the reading and the applying.

18. The method of claim 10, wherein the historical data includes data that were never available in a real-time environment.

19. The method of claim 10, further comprising:

generating an update propagation graph (UPG) based on the second query program, the UPG having a plurality of nodes each corresponding to one of a plurality of data objects referenced by the second query program, the UPG having a structure representing the dependencies between the plurality of data objects in the second query program;

the query processor determining from the parsing of the one or more second configuration instructions a simulation clock cycle and a clock cycle speed; and

for each clock cycle for the simulation period;

starting a simulated clock cycle;

determining data changes in the clock cycle;

applying the data changes according to an order determined by the UPG; and

updating dynamic simulated real-time action system dynamic tables.

20. The method of claim 10, wherein the first query program is different than the second query program.

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

establishing a digital connection between a query processor and a query client device;

the computer system receiving real-time data and storing historical data in a production environment;

receiving at the query processor, a first query program with one or more first configuration instructions from the query client device;

the query processor determining from the one or more first configuration instructions from the query client device that a real-time mode is to be used when executing the first query program;

the query processor executing, in the real-time mode, the first query program in the production environment using production system code;

receiving at the query processor, a second query program with one or more second configuration instructions from the query client device;

the query processor parsing the one or more second configuration instructions;

the query processor determining from the one or more second configuration instructions from the query client device that a simulation mode is to be used when executing the second query program;

the query processor extracting a simulation period from the one or more second configuration instructions; and

while the computer system receives new real-time data and stores new historical data in the production environment, the query processor switching modes and executing, in the simulation mode, the second query program in the production environment using the same production system code used to execute the first query program in the real-time mode, the executing the second query program comprising;

preventing the second query program from accessing the new real-time data; and

requesting real-time data simulated from the historical data stored in the production environment.

22. The nontransitory computer readable medium of claim 21, the operations further comprising:

requesting non-action system generated historical data; and

creating anti-look-ahead bias historical filters.

23. The nontransitory computer readable medium of claim 22, the operations further comprising:

applying the anti-look-ahead bias historical data filters to the requested non-action system generated real-time data simulated from historical data.

24. The nontransitory computer readable medium of claim 21, the operations further comprising:

when a simulated real-time action system does not exist, constructing, by the one or more processors, a simulated real-time action system;

the query processor connecting to the simulated real-time action system; and

generating simulated real-time action system data.

25. The nontransitory computer readable medium of claim 21, the operations further comprising:

the query processor determining from the parsing of the one or more second configuration instructions, a simulation clock cycle and a clock cycle speed;

for each clock cycle for the simulation period, the query processor;

starting a simulated clock cycle;

determining any data changes in the clock cycle;

applying the data changes to an update propagation graph; and

updating dynamic simulated real-time action system dynamic tables.

26. The nontransitory computer readable medium of claim 21,

wherein the real-time data are simulated from historical data by reading a copy of underlying historical data and applying, after the reading, one or more changes to the read copy of underlying historical data;

and

wherein the underlying historical data are unchanged by the reading and the applying.

27. The nontransitory computer readable medium of claim 21, wherein the historical data includes data that were never available in a real-time environment.

28. The nontransitory computer readable medium of claim 21, the operations further including:

generating an update propagation graph (UPG) based on the second query program, the UPG having a plurality of nodes each corresponding to one of a plurality of data objects referenced by the second query program, the UPG having a structure representing the dependencies between the plurality of data objects in the second query program;

the query processor determining from the parsing of the one or more second configuration instructions a simulation clock cycle and a clock cycle speed; and

for each clock cycle for the simulation period;

starting a simulated clock cycle;

determining data changes in the clock cycle;

applying the data changes according to an order determined by the UPG; and

updating dynamic simulated real-time action system dynamic tables.

29. The nontransitory computer readable medium of claim 21, wherein the first query program is different than the second query program.