Remote data object publishing/subscribing system having a multicast key-value protocol

• US 10,002,153 B2
• Filed: 05/14/2016
• Issued: 06/19/2018
• Est. Priority Date: 05/14/2015
• Status: Active Grant

• Current Assignee: Deephaven Data Labs, LLC
• Original Assignee: Illumon LLC
• Inventors: Teodorescu, Radu, Caudy, Ryan, Kent, IV, David R., Wright, Charles, Ferretti-Smythe, Juan Cristian, Ries, Brian
• Primary Examiner(s): LIN, SHEW FEN
• Application Number:
  US15/155,012
• Publication Number:
  US 20160335293A1
• Time in Patent Office: 766 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 data object publishing/subscribing via a multicast key-value protocol.

Claims

1. A system comprising:

a data source computing device including a first nontransitory memory containing instructions for a publishing process using a key-value protocol;

a first electronic communications channel including a first communications protocol, wherein the first channel is a broadcast channel;

a second electronic communications channel including a second communications protocol, wherein the second channel is a host-to-host retransmit request channel; and

a query computing device coupled to the data source computing device via the first electronic communications channel and the second electronic communications channel, the query computing device including a second nontransitory memory containing instructions for a subscriber process using the key-value protocol,

wherein the instructions for the publishing process stored in the first nontransitory memory include instructions that, when executed by the data source computing device, cause the data source computing device to perform publishing operations including;

receiving, at the data source computing device, an indication of new data available, wherein the new data includes at least one key-value pair;

updating, at the data source computing device, a sequence identifier value to generate an updated sequence identifier value for the at least one key-value pair;

packaging, at the data source computing device, at least a portion of the new data into a publisher message including the at least one key-value pair and the updated sequence identifier value;

broadcasting, from the data source computing device, the publisher message via the first electronic communication channel;

receiving, at the data source computing device, a retransmit request from the query computing device via the second electronic communications channel;

selecting a retransmit electronic communications channel from a plurality of available channels, the retransmit electronic communications channel being different than the second electronic communications channel; and

transmitting, from the data source computing device, requested retransmit data to the query computing device via the selected retransmit electronic communication channel,

wherein the instructions for the subscriber process stored in the second nontransitory memory include instructions that, when executed by the query computing device, cause the query computing device to perform subscriber operations including;

receiving, at the query computing device, a request for a first group of keys from a first remote query processor;

transmitting, from the query computing device via the second electronic communications channel, a request for current key-value data for the first group of keys from the data source computing device;

adding, at the query computing device, the current key-value data to a key-value map;

receiving, at the query computing device, a received key-value protocol broadcast message;

for each respective key of one or more keys in the received key-value protocol broadcast message that are in the key-value map;

evaluating, at the query computing device, a sequence identifier (ID) in the received key-value protocol broadcast message to determine a most recent data for the respective key, and

updating the value for that the respective key in the key-value map with the most recent data;

generating an updated data object based on current key-value data and/or the key-value protocol broadcast message;

propagating changes, using the subscriber process, based on the updated data object to one or more dependent objects according to an update propagation graph of data object dependencies to update an in-memory table of a subscriber system associated with the subscriber process;

transmitting, from the query computing device via the second electronic communications channel, a request for retransmit data from the data source computing device; and

receiving, at the query computing device, the requested retransmit data from the data source computing device via the retransmit electronic communication channel selected by the data source computing device,

wherein the first electronic communication channel and the second electronic communications channel are different channels.

2. The system of claim 1, wherein the first communications protocol includes an Internet protocol (IP) multicast protocol.

3. The system of claim 1, wherein the second communications protocol includes transmission control protocol (TCP).

4. The system of claim 1, wherein the data source computing device further includes:

a data source process coupled to the publishing process;

one or more key log files generated by the data source process; and

a log tailer process configured to access the one or more key log files.

5. The system of claim 4, wherein the data source computing device further includes:

one or more data log files, wherein the log tailer process is configured to access the one or more data log files.

6. The system of claim 1, wherein the query computing device further includes:

one or more remote query processors; and

a shared memory device having a memory location accessible by the subscriber process and at least one of the one or more remote query processors,

wherein the subscriber operations further include writing, from the subscriber process, data to the memory location of the shared memory device, and

wherein the at least one of the one or more remote query processors is configured to access the same memory location of the shared memory device to read the data written by the subscriber process.

7. The system of claim 1,

wherein the first communications protocol includes an Internet protocol (IP) multicast protocol, and

wherein the second communications protocol includes transmission control protocol (TCP).

8. The system of claim 1, wherein the publishing operations further include:

transmitting another retransmission of the requested retransmit data to the query computing device via one of the plurality of available channels other than the selected retransmit electronic communication channel.

9. A method for subscription comprising:

receiving, at a query computing device, a request for a first group of keys from a first remote query processor;

transmitting, from the query computing device via a second electronic communications channel in a first communication protocol, a request for current key-value data for the first group of keys to a data source computing device;

adding, at the query computing device, the current key-value data to a key-value map;

receiving, at the query computing device, a key-value protocol broadcast message;

for each respective key of one or more keys in the received key-value protocol broadcast message that are in the key-value map;

evaluating, at the query computing device, a sequence identifier (ID) in the received key-value protocol broadcast message to determine a most recent data for the respective key, and

updating the value for the respective key in the key-value map with the most recent data;

generating an updated object based on the current key-value data and/or the key-value protocol broadcast message;

propagating changes, using a subscriber process, based on the updated data object to one or more dependent objects according to an update propagation graph of data object dependencies to update an in-memory table of a subscriber system associated with the subscriber process;

receiving, at a data source computing device, a retransmit request from the query computing device via the second electronic communications channel;

selecting, by the data source computing device, a selected retransmit electronic communications channel from a plurality of available channels, the retransmit electronic communications channel being different than the second electronic communications channel;

transmitting, from the data source computing device, requested retransmit data to the query computing device via the selected retransmit electronic communication channel; and

receiving, at the query computing device, the requested retransmit data from the data source computing device via the retransmit electronic communication channel selected by the data source computing device.

10. The method of claim 9, wherein the first communication protocol includes transmission control protocol (TCP).

11. The method of claim 9, further comprising:

writing, from a subscriber process being executed by the query computing device, data to a memory location of a shared memory device of the query computing device, the query computing device comprising one or more remote query processors,

wherein the memory location of the shared memory device is accessible by the subscriber process and at least one of the one or more remote query processors, and

wherein the at least one of the one or more remote query processors is configured to access the same memory location of the shared memory device to read the data written by the subscriber process.

12. The method of claim 9,

wherein the key-value protocol broadcast message is received at the query computing device via a first electronic communication channel, and

wherein the first electronic communication channel and the second electronic communications channel are different channels.

13. The method of claim 9,

wherein the key-value protocol broadcast message is received at the query computing device via a first electronic communication channel in a second communication protocol,

wherein the first electronic communication channel and the second electronic communications channel are different channels,

wherein the second communications protocol includes an Internet protocol (IP) multicast protocol, and

wherein the first communications protocol includes transmission control protocol (TCP).

14. The method of claim 9, the method further comprising:

transmitting another retransmission of the requested retransmit data to the query computing device via one of the plurality of available channels other than the selected retransmit electronic communication channel.

15. A system comprising:

a data source computing device including a first nontransitory memory containing instructions for a publishing process using a key-value protocol;

a first electronic communications channel including a first communications protocol, wherein the first channel is a broadcast channel;

a second electronic communications channel including a second communications protocol, wherein the second channel is a host-to-host retransmit request channel; and

a query computing device coupled to the data source computing device via the first electronic communications channel and the second electronic communications channel, the query computing device including;

a second nontransitory memory containing instructions for a subscriber process using the key-value protocol,

one or more remote query processors, and

a shared memory device having a memory location accessible by the subscriber process and at least one of the one or more remote query processors,

wherein the instructions for the publishing process stored in the first nontransitory memory include instructions that, when executed by the data source computing device, cause the data source computing device to perform publishing operations including;

receiving, at the data source computing device, an indication of new data available, wherein the new data includes at least one key-value pair;

updating, at the data source computing device, a sequence identifier value to generate an updated sequence identifier value for the at least one key-value pair;

packaging, at the data source computing device, at least a portion of the new data into a publisher message including a key-value pair and the updated sequence identifier value; and

broadcasting, from the data source computing device, the publisher message via the first electronic communication channel,

wherein the instructions for the subscriber process stored in the second nontransitory memory include instructions that, when executed by the query computing device, cause the query computing device to perform subscriber operations including;

receiving, at the query computing device, a request for a first group of keys from a first remote query processor;

transmitting, from the query computing device via the second electronic communications channel, a request for current key-value data for the first group of keys from the data source computing device;

adding, at the query computing device, the current key-value data to a key-value map;

receiving, at the query computing device, a key-value protocol broadcast message;

for each respective key of one or more keys in the received key-value protocol broadcast message that are in the key-value map;

evaluating, at the query computing device, a sequence identifier (ID) in the received key-value protocol broadcast message to determine a most recent data for the respective key, and

updating the value for the respective key in the key-value map with the most recent data;

generating an updated object based on the current key-value data and/or the key-value protocol broadcast message;

propagating changes, using the subscriber process, based on the updated data object to one or more dependent objects according to an update propagation graph of data object dependencies to update an in-memory table of a subscriber system associated with the subscriber process; and

writing, from the subscriber process, data to the memory location of the shared memory device, the at least one of the one or more remote query processors being configured to access the same memory location of the shared memory device to read the data written by the subscriber process.

16. The system of claim 15, wherein the first communications protocol includes an Internet protocol (IP) multicast protocol.

17. The system of claim 15, wherein the second communications protocol includes transmission control protocol (TCP).

18. The system of claim 15, wherein the data source computing device further includes:

a data source process coupled to the publishing process;

one or more key log files generated by the data source process; and

a log tailer process configured to access the one or more key log files.

19. The system of claim 18, wherein the data source computing device further includes:

one or more data log files, wherein the log tailer process is configured to access the one or more data log files.

20. The system of claim 15, wherein the first electronic communication channel and the second electronic communications channel are different channels.

21. The system of claim 15,

wherein the first electronic communication channel and the second electronic communications channel are different channels,

wherein the first communications protocol includes an Internet protocol (IP) multicast protocol, and

wherein the second communications protocol includes transmission control protocol (TCP).

22. The system of claim 15, wherein the publishing operations further include:

transmitting another retransmission of the requested retransmit data to the query computing device via one of the plurality of available channels other than the selected retransmit electronic communication channel.

23. A method for subscription comprising:

receiving, at a query computing device comprising one or more remote query processors, a request for a first group of keys from a first remote query processor;

transmitting, from the query computing device via a second electronic communications channel in a first communication protocol, a request for current key-value data for the first group of keys to a data source computing device;

adding, at the query computing device, the current key-value data to a key-value map;

receiving, at the query computing device, a key-value protocol broadcast message;

for each respective key of one or more keys in the received key-value protocol broadcast message that are in the key-value map;

evaluating, at the query computing device, a sequence identifier (ID) in the received key-value protocol broadcast message to determine a most recent data for the respective key, and

updating the value for the respective key in the key-value map with the most recent data;

generating an updated object based on the current key-value data and/or the key-value protocol broadcast message;

propagating changes, using a subscriber process, based on the updated data object to one or more dependent objects according to an update propagation graph of data object dependencies to update an in-memory table of a subscriber system associated with the subscriber process; and

writing, from a subscriber process being executed by the query computing device, data to a memory location of a shared memory device of the query computing device accessible by the subscriber process and at least one of the one or more remote query processors, the at least one of the one or more remote query processors being configured to access the same memory location of the shared memory device to read the data written by the subscriber process.

24. The method of claim 23, wherein the first communication protocol includes transmission control protocol (TCP).

25. The method of claim 23,

wherein the key-value protocol broadcast message is received at the query computing device via a first electronic communication channel, and

wherein the first electronic communication channel and the second electronic communications channel are different channels.

26. The method of claim 23,

wherein the key-value protocol broadcast message is received at the query computing device via a first electronic communication channel in a second communication protocol,

wherein the first electronic communication channel and the second electronic communications channel are different channels,

wherein the second communications protocol includes an Internet protocol (IP) multicast protocol, and

wherein the first communications protocol includes transmission control protocol (TCP).

27. The method of claim 23, the method further comprising:

transmitting another retransmission of the requested retransmit data to the query computing device via one of the plurality of available channels other than the selected retransmit electronic communication channel.