Method and apparatus for low latency data distribution

• US 9,047,243 B2
• Filed: 04/05/2012
• Issued: 06/02/2015
• Est. Priority Date: 12/14/2011
• Status: Active Grant

• Current Assignee: Exegy Incorporated
• Original Assignee: Ip Reservoir, LLC
• Inventors: Taylor, David E., Parsons, Scott, Schuehler, David Vincent, Strader, Todd Alan, Eder, Ryan L.
• Primary Examiner(s): Kim, Hee Soo
• Application Number:
  US13/440,118
• Publication Number:
  US 20130159449A1
• Time in Patent Office: 1,153 Days
• Field of Search: 709/213, 709/214, 709/212, 709/216
• US Class Current: 1/1
• CPC Class Codes: G06F 15/167 using a common memory, e.g. mailbox
• CPC Class Codes: G06F 15/17331 Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]
• CPC Class Codes: G06F 9/54 Interprogram communication
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

Various techniques are disclosed for distributing data, particularly real-time data such as financial market data, to data consumers at low latency. Exemplary embodiments include embodiments that employ adaptive data distribution techniques and embodiments that employ a multi-class distribution engine.

Claims

1. A method for data distribution, the method comprising:

maintaining a plurality of data records corresponding to a plurality of items, a data consumer being subscribed to information about the items, the records being indicative of a plurality of locations reserved for data about the items in a shared memory, the shared memory being shared between the data producer and the data consumer;

receiving a plurality of events corresponding to the items; and

adaptively distributing data representative of the events to the subscribed data consumer by (1) determining a plurality of locations in the shared memory for writing the event data based on the data records, and (2) performing a plurality of direct memory access (DMA) write operations for the event data to the shared memory at the determined locations to provide updates about the items without participation from any processing resources in the data consumer;

wherein the adaptively distributing step is performed by a processor.

2. The method of claim 1 wherein the processor is resident in a data producer, the data producer performing the maintaining, receiving, and adaptively distributing steps, wherein a plurality of data consumers are subscribed to a plurality of the items, the records being indicative of a plurality of locations in a plurality of shared memories reserved for data about the items, each shared memory being shared between the data producer and a data consumer, and wherein the adaptively distributing step comprises the processor performing the adaptively distributing step with the different data consumers independently of any read operations from the shared memories that are performed by the data consumers.

3. The method of claim 2 further comprising:

the data producer storing the received events in a memory cache;

the data producer determining whether any of the data consumers are subscribers to the items corresponding to the received events; and

the data producer performing the adaptively distributing step with respect to the event data in the cache for the data consumers that are determined to be subscribed to the items corresponding to the received events, wherein the adaptively distributing step comprises;

when there is write congestion for the data producer, the data producer updating the cache as new event data is received with the latest event for each item such that the DMA write operation will write the latest event for a particular item rather than a most previous event for that particular item if the most previous event had not yet been distributed to its subscribed data consumer; and

when there is read congestion for a data consumer and new event data has been received by the data producer for a particular item for which the congested data consumer has not yet read the most previous event data for that particular item written to the shared memory of the congested data consumer, the data producer overwriting the location in the shared memory for that particular item with the new event data via the DMA write operation.

4. The method of claim 2 wherein the maintaining step further comprises:

the data producer maintaining a plurality of client distribution records (CDRs), each CDR comprising a data consumer identifier, an interface address, a base address, and a shared memory size identifier;

the data producer maintaining a plurality of record offsets, each corresponding to one of the items;

the method further comprising;

the data producer maintaining a queue of pending transfers to the data consumers;

the data producer updating the queue with events based on the receiving step; and

the data producer performing the adaptively distributing step for the events in the queue such that the data producer DMA writes event data from the cache to the shared memories in the data consumers at locations in the shared memories determined from the CDRs and the record offsets.

5. The method of claim 4 wherein the record offsets are applicable across all of the data consumers.

6. The method of claim 4 wherein the step of maintaining the record offsets comprises the data producer maintaining different sets of record offsets for a plurality of the data consumers.

7. The method of claim 4 wherein the data producer continues to update a data record for an item in response to received new data for that item even if there is a pending transfer in the queue for that data record.

8. The method of claim 4 further comprising:

the data producer determining whether the same updated data record is pending for transfer to a plurality of data consumers; and

in response to determining that the same updated data record is pending for transfer to a plurality of data consumers, the data producer grouping the DMA write operations for the updated data record to those data consumers.

9. The method of claim 8 further comprising the data producer performing the determining step using a hash table.

10. The method of claim 8 further comprising the data producer performing the determining step using a Bloom filter.

11. The method of claim 2 wherein the data producer performs the method steps across unicast DMA-capable interconnects.

12. The method of claim 2 wherein the data producer performs the method steps across multicast DMA-capable interconnects.

13. The method of claim 1 wherein the data comprises financial market data.

14. The method of claim 1 wherein the processor is resident within an intelligent network interface card (NIC).

15. The method of claim 1 wherein the processor is co-resident with a DMA engine.

16. The method of claim 1 wherein the processor is resident within a connection multiplexer.

17. The method of claim 1 wherein the processor is resident within an edge cache device.

18. The method of claim 1 wherein the processor is resident within a ticker plant.

19. The method of claim 1 wherein the processor comprises a coprocessor.

20. The method of claim 19 wherein the coprocessor comprises a reconfigurable logic device.

21. The method of claim 19 wherein the coprocessor comprises a multi-core processor.

22. The method of claim 19 wherein the coprocessor comprises a graphics processing unit (GPU).

23. An apparatus for data distribution comprising:

a processor; and

a memory;

wherein the processor is configured to;

maintain a plurality of data records corresponding to a plurality of items in the memory, a data consumer being subscribed to information about the items, the records being indicative of a plurality of locations reserved for data about the items in a shared memory, the shared memory being shared between the data producer and the data consumer;

receive a plurality of events corresponding to the items; and

adaptively distribute data representative of the events to the subscribed data consumer, wherein as part of the adaptive distribution the processor is configured to (1) determine a plurality of locations in the shared memory for writing the event data based on the data records, and (2) perform a plurality of direct memory access (DMA) write operations for the event data to the shared memory at the determined locations to provide updates about the items without participation from any processing resources in the data consumer.

24. A method for data distribution comprising:

generating a plurality of unique data streams for a plurality of data consumers, each unique data stream corresponding to a data consumer such that the unique data streams correspond to a plurality of data consumers in the aggregate, wherein each unique data stream comprises a plurality of update events for a plurality of items, the update events in each unique data stream relating to only a set of items that are of interest to that unique data stream'"'"'s corresponding data consumer; and

distributing the unique data streams to their associated data consumers via a plurality of direct memory access (DMA) write operations to a plurality of shared memories in the data consumers without processing feedback information from the data consumers; and

wherein the method steps are performed by a processor.

25. The method of claim 24 wherein the set of items that are of interest to the data consumers are the items to which each data consumer has subscribed, the method further comprising processor performing the generating step and the distributing step such that the data consumers are not required to filter out data from the unique data streams that are related to items for which the data consumers have not subscribed.

26. The method of claim 24 further comprising:

the processor tracking where to write the update events in the shared memories via a plurality of write pointers, wherein each data consumer is configured to read data from the shared memory via a read pointer, and wherein the processor has no visibility of the data consumers'"'"' read pointers when distributing the unique data streams the data consumers.

27. The method of claim 26 wherein the shared memory comprises a ring buffer.

28. The method of any of claim 27 wherein each update event comprises:

a header field;

an event field;

a checksum field; and

a blank header field.

29. The method of claim 28 wherein the header field comprises a token, a sequence and a length.

30. The method of claim 28 further comprising triggering a resynchronize operation in response to a read by the data consumer of a header field that contains an invalid unique token, an invalid message length, or an unexpected sequence number.

31. The method of claim 28 further comprising the data consumer restarting its event processing when an incorrect checksum is detected.

32. The method of claim 24 wherein the data streams comprise financial market data.

33. The method of claim 24 wherein the processor is resident within an intelligent network interface card (NIC).

34. The method of claim 24 wherein the processor is co-resident with a DMA engine.

35. The method of claim 24 wherein the processor is resident within a connection multiplexer.

36. The method of claim 24 wherein the processor is resident within an edge cache device.

37. The method of claim 24 wherein the processor is resident within a ticker plant.

38. The method of claim 24 wherein the processor comprises a coprocessor.

39. The method of claim 38 wherein the coprocessor comprises a reconfigurable logic device.

40. The method of claim 38 wherein the coprocessor comprises a multi-core processor.

41. The method of claim 38 wherein the coprocessor comprises a graphics processing unit (GPU).

42. An apparatus for data distribution comprising:

a processor configured to (1) generate a plurality of unique data streams for a plurality of data consumers, each unique data stream corresponding to a data consumer such that the unique data streams correspond to a plurality of data consumers in the aggregate, wherein each unique data stream comprises a plurality of update events for a plurality of items, the update events in each unique data stream relating to only a set of items that are of interest to that unique data stream'"'"'s corresponding data consumer, and (2) distribute the unique data streams to their associated data consumers via a plurality of direct memory access (DMA) write operations to a plurality of shared memories in the data consumers without processing feedback information from the data consumers.

43. A method for data distribution, the method comprising:

maintaining a plurality of data records corresponding to a plurality of items for which event data is to be distributed to a plurality of data consumers on a metered basis, the records identifying the subscribed data consumers for each item and metering data for each subscribed data consumer for each item such that the records support differing metering rates for a plurality of same items with respect to a plurality of different data consumers and differing metering rates for a plurality of different items with respect to a plurality of same data consumers;

receiving a plurality of events corresponding to the items; and

performing a metered distribution of data relating to the received events to the data consumers based on the data records such that the data distribution is metered on a per-data consumer/per item basis in accordance with the metering data in the data records that are applicable to the items corresponding to the received events; and

wherein the performing step is performed by a processor.

44. The method of claim 43 wherein the processor is resident in a data producer, the data producer performing the maintaining, receiving, and metered distribution steps, wherein the metering data comprises, for each item with respect to each subscribed data consumer for that item, (1) a meter rate applicable to the item-subscribed data consumer pair, and (2) a last time sent applicable to the item-subscribed data consumer pair.

45. The method of claim 44 wherein the metered distribution performing step utilizes a timing wheel with constant insertion time.

46. The method of claim 45 further comprising the processor performing a fanout operation, and wherein the processor performs the metered distribution and fanout operations independently.

47. The method of claim 44 further comprising the processor classifying data into metered and real-time classes on a per-event basis, the method further comprising the processor performing the metered distribution for the event data classified into the metered class.

48. The method of claim 47 further comprising the processor performing a fanout operation, and wherein the data classification, metered distribution, and fanout processing is performed in parallel.

49. The method of claim 43 wherein each data record comprises:

a client data map that maintains a list of data consumers with subscriptions to the data item;

a data item index number;

a global dirty bit;

a global last time sent;

a current image of the data item record;

a size of the data item record image.

50. The method of claim 49 wherein the client data map comprises:

a dirty bit;

a last time sent;

a client-specific meter rate.

51. The method of claim 43 wherein the processor is resident within a data distribution node.

52. The method of claim 43 wherein the data comprises financial market data.

53. The method of claim 43 wherein the processor is resident within an intelligent network interface card (NIC).

54. The method of claim 43 wherein the processor is co-resident with a DMA engine.

55. The method of claim 43 wherein the processor is resident within a connection multiplexer.

56. The method of claim 43 wherein the processor is resident within an edge cache device.

57. The method of claim 43 wherein the processor is resident within a ticker plant.

58. The method of claim 43 wherein the processor comprises a coprocessor.

59. The method of claim 58 wherein the coprocessor comprises a reconfigurable logic device.

60. The method of claim 58 wherein the coprocessor comprises a multi-core processor.

61. The method of claim 58 wherein the coprocessor comprises a graphics processing unit (GPU).

62. An apparatus for data distribution comprising:

a processor; and

a memory;

wherein the processor is configured to;

maintain a plurality of data records in the memory, the data records corresponding to a plurality of items for which event data is to be distributed to a plurality of data consumers on a metered basis, the records identifying the subscribed data consumers for each item and metering data for each subscribed data consumer for each item such that the records support differing metering rates for a plurality of same items with respect to a plurality of different data consumers and differing metering rates for a plurality of different items with respect to a plurality of same data consumers;

receive a plurality of events corresponding to the items; and

perform a metered distribution of data relating to the received events to the data consumers based on the data records such that the data distribution is metered on a per-data consumer/per-item basis in accordance with the metering data in the data records that are applicable to the items corresponding to the received events.

63. An apparatus for distributing data, the apparatus comprising:

a multi-class distribution engine (MDE), the MDE configured to distribute a plurality of events corresponding to a plurality of items and belonging to a plurality of classes on a class-specific basis from a data producer to a plurality of data consumers according to at least two members of the group consisting of (1) a critical data distribution technique wherein all events are distributed to a data consumer for reading thereby, (2) an adaptive data distribution technique wherein (i) all events are distributed to a data consumer for reading thereby if no congestion exists with respect to the data producer and that data consumer, and (ii) conflated events are distributed to a data consumer for reading thereby if congestion exists with respect to the data producer and that data consumer, and (3) a metered data distribution technique wherein events are distributed to the data consumers for reading thereby in accordance with metering policies that vary on a per data consumer/per item basis.

64. The apparatus of claim 63 wherein the MDE is further configured to distribute the events on a class-specific basis from a data producer to the data consumers via a plurality of direct memory access (DMA) write operations to a plurality of shared memories in the data consumers according to at least two members of the group consisting of (1) the critical data distribution technique, (2) the adaptive data distribution technique, and (3) the metered data distribution technique.

65. The apparatus of claim 64 wherein the MDE comprises an update classification engine (UCE), the UCE configured to determine a class for each event, the MDE further configured to (1) select a distribution technique for each event from among the at least two members based on the determined class for that event, and (2) distribute the events to the data consumers in accordance distribution technique selected therefor.

66. The apparatus of claim 64 wherein the MDE comprises (1) a plurality of output interconnection interfaces, (2) a plurality of transmission engines, and (3) a scheduler configured to ensure that each transmission engine utilizes a specified fraction of the bandwidth available on the output interconnection interfaces.

67. The apparatus of claim 64 wherein the MDE is configured for processing streaming financial market data.

68. The apparatus of claim 64 wherein the MDE is resident in a distribution node.

69. The apparatus of claim 68 wherein the distribution node comprises:

a shared memory data cache;

a control plane;

a consumer distribution record memory;

the MDE;

an upstream DMA interconnect adapter; and

a downstream DMA interconnect adapter.

70. The apparatus of claim 68 wherein the distribution node comprises:

a shared memory data cache;

a control plane;

a consumer distribution record memory;

the MDE;

an upstream DMA interconnect adapter; and

a downstream message interconnect adapter.

71. The apparatus of claim 68 wherein the distribution node comprises:

a shared memory data cache;

a control plane;

a consumer distribution record memory;

the MDE;

an upstream message interconnect adapter; and

a downstream message interconnect adapter.

72. The apparatus of claim 64 wherein the MDE is further configured to select a data distribution technique from among the group according to a static configuration.

73. The apparatus of claim 64 wherein the MDE is further configured to dynamically select a data distribution technique from among the group.

74. The apparatus of claim 64 wherein the MDE is resident within a connection multiplexer.

75. The apparatus of claim 64 wherein the MDE is resident within an edge cache device.

76. The apparatus of claim 64 wherein the MDE is resident within a ticker plant.

77. The apparatus of claim 64 wherein the MDE is resident on a coprocessor.

78. The apparatus of claim 77 wherein the coprocessor comprises a reconfigurable logic device.

79. The apparatus of claim 77 wherein the coprocessor comprises a multi-core processor.

80. The apparatus of claim 77 wherein the coprocessor comprises a graphics processing unit (GPU).

81. A method for distributing data comprising:

receiving a plurality of events for distribution to a plurality of data consumers, the events corresponding to a plurality of items;

determining a class for each received event from among a plurality of classes;

selecting a distribution technique for each received event from among a plurality of distribution techniques based on the class determined therefor, the plurality of distribution techniques comprising at least two members of the group consisting of (1) a critical data distribution technique wherein all events are distributed to a data consumer for reading thereby, (2) an adaptive data distribution technique wherein (i) all events are distributed to a data consumer for reading thereby if no congestion exists with respect to the data producer and that data consumer, and (ii) conflated events are distributed to a data consumer for reading thereby if congestion exists with respect to the data producer and that data consumer, and (3) a metered data distribution technique wherein events are distributed to the data consumers for reading thereby in accordance with metering policies that vary on a per data consumer/per item basis; and

distributing the events on a class-specific basis to the data consumers according to the selected distribution technique for each event; and

wherein the method steps are performed by a multi-class distribution engine (MDE).

82. A method for data consumption comprising:

receiving data in a shared memory via DMA write operations from a data producer;

maintaining a table that identifies locations in the shared memory data where a plurality of items can be found;

receiving a read request corresponding to an item;

accessing the maintained table in response to the received read request to determine the location where data for the item corresponding to the read request can be found;

reading data from the shared memory at the location determined in response to the accessing step; and

performing a coherency checking operation on the read data;

wherein the method steps are performed by a processor.

83. The method of claim 82 further comprising:

the processor generating a notification when new data for an item has been written to the shared memory by the data producer; and

wherein the read request receiving step comprises the processor receiving the read request in response to the generated notification.

84. The method of claim 83 further comprising:

maintaining a last record cache; and

the processor performing a delta comparison operation between the data read from the shared memory and data within the last record cache to determine which record fields were updated and to indicate the updated fields to a data consumer.

85. The method of claim 83 further comprising:

maintaining a plurality of update notification filter rules specified by the data consumer; and

the processor performing a filtering operation to determine whether to notify the data consumer that an update has occurred for a subscribed data item.

86. The method of claim 83 further comprising:

the processor processing the generated notifications to determine whether the notifications should be passed to a plurality of consuming applications.

87. The method of claim 83 wherein the data comprises financial market data.

88. The method of claim 83 wherein the processor comprises a coprocessor.

89. The method of claim 88 wherein the coprocessor comprises a reconfigurable logic device.

90. The method of claim 88 wherein the coprocessor comprises a multi-core processor.

91. The method of claim 88 wherein the coprocessor comprises a graphics processing unit (GPU).

92. The method of claim 82 wherein the processor is co-resident with a DMA engine in direct communication with a DMA interconnect adapter such that data is written to shared memory directly accessible by the processor and data need not cross a data consumer system interconnect into system memory or require involvement by system software.

93. An apparatus comprising:

a processor configured to (1) receive data in a shared memory via DMA write operations from a data producer, (2) maintain a table that identifies locations in the shared memory data where a plurality of items can be found, (3) receive a read request corresponding to an item, (4) access the maintained table in response to the received read request to determine the location where data for the item corresponding to the read request can be found, (5) read data from the shared memory at the location determined in response to the access operation, and (6) perform a coherency checking operation on the read data.

94. The apparatus of claim 93 wherein the processor is resident on a reconfigurable logic device to offload an application programming interface (API) function from a data consumer.

95. The apparatus of claim 94 further comprising a direct memory access (DMA) interconnect adapter in communication with the reconfigurable logic device.

96. A method for data distribution comprising:

receiving a plurality of events for distribution to a plurality of data consumers;

determining a class for the events from among a plurality of classes;

selectively delivering the events to a first queue or a second queue based on the determined classes for the events;

a metering engine reading events from the first queue;

the metering engine performing a metering function on the events read from the first queue to control a metered transmission of the events read from the first queue;

the metering engine delivering metered events to a third queue in accordance with the metering function;

a fanout engine downstream from the metering engine reading events from the second queue and metered events from the third queue;

the fanout engine distributing the read events from the second and third queues to the data consumers such that the events in the second queue are distributed to the data consumers on a non-metered basis and the events in the third queue are distributed to the data consumers on the metered basis.

97. The method of claim 96 wherein the metering engine and the fanout engine are resident on a reconfigurable logic device, the metering engine and the fanout engine operating simultaneously with respect to each other as the streaming events are received and processed.

98. The method of claim 97 wherein the events comprise a plurality of financial market data messages.

99. The method of claim 96 wherein the second queue is for real-time data traffic, and wherein the distributing step comprises the fanout engine distributing the events in the second queue to the data consumers on a real-time basis and distributing the events in the third queue to the data consumers on the metered basis.