In-Order Processing of Transactions

Abstract

The described technology relates to a real-time order processing systems such as, for example, an electronic trading application for equities and other tradable investment instruments. An example system relates to reordering messages received at a server over a communication network from distributed clients, in order to, among other things, eliminate or at least substantially reduce the effects of jitter (delay variance) experienced in the network. The reordering of messages may enable the example electronic trading system to improve the consistency of executing orders (e.g., performing transactions for buying/selling electronic inventories) in the time order of when the client's order entered the trading system's network.

1 . An electronic trading system, comprising:
 a communication infrastructure;   a server infrastructure system; and   a plurality of gateway infrastructure systems connected to the server infrastructure system by the communication infrastructure,   wherein each of the gateway infrastructure systems is configured to:
 receive incoming data transaction request messages from one or more client computer systems; 
 attach a respective gateway timestamp to each of the incoming data transaction request messages, the respective gateway timestamp corresponding to either a time at which the respective incoming data transaction request message is in the gateway infrastructure system or a time at which the incoming data transaction was in a network device located between the client computer system and the gateway infrastructure system; and 
 transmit the gateway timestamp-attached data transaction request messages to the server infrastructure system; 
   and wherein the server infrastructure system is configured to:
 receive the gateway timestamp-attached data transaction request messages from one or more of the gateway infrastructure systems; 
 reorder the received gateway timestamp-attached data transaction request messages in order of oldest to newest of the respective gateway timestamps of the gateway timestamp-attached data transaction request messages; and 
 provide the reordered gateway timestamp-attached data transaction request messages in order of oldest to newest of the respective gateway timestamps to a matching engine, wherein the matching engine is configured to process the data transaction request messages in order of receipt at the matching engine. 
   
     
     
         2 . The electronic trading system according to  claim 1 , wherein the server infrastructure system is further configured to attach a respective server timestamp to each of the respective received gateway timestamp-attached data transaction request messages, the respective server timestamp corresponding to a time at which the respective received gateway timestamp-attached data transaction request message is in the server infrastructure system,
 wherein the reordering is based on both the gateway timestamp and the server timestamp of respective ones of the server timestamp-attached data transaction request messages, and   wherein the received data transaction request messages are provided to the matching engine in order according to gateway timestamps of the respective received data transaction request messages.   
     
     
         3 . The electronic trading system according to  claim 2 , wherein the server infrastructure system further comprises a reorder buffer configured in a memory, wherein the reordering based on both the gateway timestamp and the server timestamp is performed using the reorder buffer. 
     
     
         4 . The electronic trading system according to  claim 3 , wherein the server infrastructure system is further configured to determine a transaction delay for the particular data transaction request message based upon a gateway timestamp and a server timestamp-attached to the particular data transaction request message, and (a) if the transaction delay is less than a threshold time interval, hold the particular data transaction request message in the reorder buffer, and (b) if the transaction delay is not less than the threshold time interval, transmit the particular transaction to the matching engine without holding the particular data transaction request message in the reorder buffer. 
     
     
         5 . The electronic trading system according to  claim 4 , wherein the server infrastructure system is further configured to:
 determine statistics for transaction delay of a plurality of gateway timestamp-attached data transaction request messages received at the server infrastructure systems, the statistics being based on a difference between a server time stamp and a gateway timestamp-attached to each of the plurality of data transaction request messages; and   select the threshold time interval based upon the determined statistics.   
     
     
         6 . The electronic trading system according to  claim 5 , wherein the server infrastructure system is further configured to select the threshold time interval based upon the determined statistics, an out of order packet tolerance threshold, and a reorder buffer delay threshold. 
     
     
         7 . The electronic trading system according to  claim 5 , wherein the server infrastructure system is further configured to repeatedly select the threshold time interval at regular time intervals and/or in accordance with load. 
     
     
         8 . The electronic trading system according to  claim 4 , wherein the server infrastructure system further comprises a timer associated with the reorder buffer, and wherein a duration of each data transaction request message in the reorder buffer is controlled by the timer based on server timestamps attached to the data transaction request messages. 
     
     
         9 . The electronic trading system according to  claim 8 , wherein the duration of a particular data transaction request message in the reorder buffer is controlled by the timer further based on a delay variance determined using a plurality of the data transaction request messages. 
     
     
         10 . The electronic trading system according to  claim 9 , wherein the timer is configured to trigger flushing of the particular data transaction request message from the reorder buffer when a sum of the determined delay variance and a value of the gateway timestamp of the particular data transaction request message equals or exceeds a current time. 
     
     
         11 . The electronic trading system according to  claim 8 , wherein the timer is configured in accordance with a maximum delay determined using a plurality of data transaction request messages. 
     
     
         12 . The electronic trading system according to  claim 11 , wherein the timer is configured to trigger flushing of a particular data transaction request message from the reorder buffer when a sum of the determined maximum delay and a value of the server timestamp of the particular data transaction request message equals or exceeds a current time. 
     
     
         13 . The electronic trading system according to  claim 3 , wherein the server infrastructure system includes a memory pipe which provides for communication between the reorder buffer and the matching engine. 
     
     
         14 . The electronic trading system according to  claim 13 , further comprising a field programmable gate array (FPGA) which includes the reorder buffer. 
     
     
         15 . The electronic trading system according to  claim 1 , further comprising a clock synchronization system including a respective clock synchronization module in each of the gateway infrastructure systems and in the server infrastructure system, wherein the clock synchronization system is configured to maintain synchronization of clocks in each gateway infrastructure system and the server infrastructure system within a predetermined threshold drift. 
     
     
         16 . The electronic trading system according to  claim 15 , wherein each of the gateway infrastructure systems and the server infrastructure system includes a respective hardware-based time stamping device that generates timestamps that are attached to data transaction request messages upon ingress. 
     
     
         17 . The electronic trading system according to  claim 16 , wherein the respective hardware-based time stamping device is located in a network interface card. 
     
     
         18 . The electronic trading system according to  claim 2 , wherein the server infrastructure system further comprises a first reorder buffer configured in a memory of the server infrastructure system to provide the reordering based on both the gateway timestamp and the server timestamp, and wherein each gateway infrastructure system comprises a second reorder buffer to provide reordering of data transaction request messages received from client computer systems and being transmitted to the server infrastructure system. 
     
     
         19 . The electronic trading system according to  claim 1 , wherein the received plurality of gateway timestamp-attached data transaction request messages each having a message type,
 wherein the server infrastructure system is further configured to
 selectively, based on the message type of each data transaction request message, distribute a first set of the received data transaction request messages into a first reorder buffer and a second set of the received data transaction request messages into a second reorder buffer; 
   wherein the reordering comprises
 separately reordering the first reorder buffer and the second reorder buffer. 
   
     
     
         20 . The electronic trading system according to  claim 19 , wherein the first set of data transaction request messages each has a message type of a buy order or a sell order, and wherein the second set of data transaction request messages each has a message type of a cancel order. 
     
     
         21 . The electronic trading system according to  claim 19 , wherein the first reorder buffer is associated with a first threshold time interval and the second reorder buffer is associated with a second threshold time interval,
 wherein the separately reordering includes reordering the first reorder buffer with respect to the first threshold time interval and reordering the second reorder buffer with respect to the second threshold time interval.   
     
     
         22 . The electronic trading system according to  claim 1 , wherein the received plurality of gateway timestamp-attached data transaction request messages each having a message type,
 wherein the server infrastructure system is further configured to
 configuring a first time threshold in associated with a first message type, and a second time threshold in associated with a second message type; 
 selectively, based on the message type of each data transaction request message, reorder a first set of the received data transaction request messages based on the first time threshold and reorder a second set of the received data transaction request messages based on the second time threshold. 
   
     
     
         23 . The electronic trading system according to  claim 1 , wherein the gateway infrastructure system is further configured to: select, based on a configuration setting, a timestamp as (a) the time at which the respective incoming data transaction request message is in the gateway infrastructure system, or (b) the time at which the incoming data transaction was in a network device located between the client computer system and the gateway infrastructure system; and use the selected timestamp for said attaching. 
     
     
         24 . A method performed using at least one processor of a server infrastructure system connected to a communication infrastructure, the method comprising:
 receiving a plurality of gateway timestamp-attached messages from gateway infrastructure systems connected to the communication infrastructure, wherein each of the gateway infrastructure systems receives messages from one or more client computer systems and attaches a respective gateway timestamp to each received message indicating a time of entry to the respective gateway system;   reordering the received plurality of gateway timestamp-attached messages in accordance with the respective gateway timestamps of the plurality of gateway timestamp-attached messages; and   providing the reordered plurality of gateway timestamp-attached messages to an application, wherein the application processes the messages in order of receipt at the application.   
     
     
         25 . The method according to  claim 24 , further comprising:
 attaching a respective server timestamp to each received gateway timestamp-attached message, the respective server timestamp corresponding to a time at which the respective received gateway timestamp-attached message is in the server infrastructure system,   wherein the reordering is based on both the gateway timestamp and the server timestamp of respective ones of the server timestamp-attached messages, and   wherein the received messages are provided to the application in order according to gateway timestamps of the respective received messages.   
     
     
         26 . The method according to  claim 25 , wherein the reordering based on both the gateway timestamp and the server timestamp is performed using a reorder buffer in a memory of the server infrastructure system. 
     
     
         27 . A non-transitory computer readable storage medium having stored therein computer program instructions that when executed by at least one processor of a server infrastructure system connected by a communication infrastructure to a plurality of gateway infrastructure systems, causes the server infrastructure system to perform operations comprising:
 receiving a plurality of gateway timestamp-attached messages from the gateway infrastructure systems connected to the communication infrastructure, wherein each of the gateway infrastructure systems receives messages from one or more client computer systems and attaches a respective gateway timestamp to each received message indicating a time of entry to the respective gateway system;   reordering the received plurality of gateway timestamp-attached messages in accordance with the respective gateway timestamps of the plurality of gateway timestamp-attached messages; and   providing the reordered plurality of gateway timestamp-attached messages to a application, wherein the application processes the messages in order of receipt at the application.