US20110010460A1 - Brokerage Transaction Server and Method Using Encapsulated Messages - Google Patents

Abstract

Brokerage transactions servers and related methods are provided having low latency. A transaction fuser operates to split incoming order flow into multiple independent streams of data, all of which can be processed in parallel without dependencies between them, allowing back-end jobs to process this data in parallel and increase throughput. Multiple transactions that operate on the same data may be “collapsed” into a single transaction, which reflects the final end state of the order.

Description

CROSS REFERENCE TO RELATED APPLICATIONS
• This application claims the benefit of U.S. Provisional Patent Application No. 61/224,237, filed Jul. 9, 2009, titled “Brokerage Transaction Server and Method Using Encapsulated Messages,” the entire contents of which are hereby incorporated by reference herein, for all purposes.
TECHNICAL FIELD
• The present invention relates to systems and methods of processing exchange transaction information for exchange brokerage purposes, and more particularly to brokerage transactions servers and related methods.
BACKGROUND ART
• It is known in the prior art to provide brokerage transaction servers, which communicate with exchange servers on the one hand and with brokerage customer servers on the other hand. A representative brokerage transaction server (therein called a “gateway”) is described in U.S. Pat. No. 5,864,827, which is hereby incorporated herein by reference in its entirety. Technology-based brokerage customers frequently engage in algorithmic trading, which benefits from the ability to execute trades with minimal latency. Some latency is inevitable, because physical processes in computational devices are not instantaneous.
SUMMARY OF EMBODIMENTS
• Embodiments of the present invention provide brokerage transactions servers and related methods with low latency. In a first embodiment of the invention there is provided a method of processing exchange transaction information for exchange brokerage purposes in an inbound digital message stream in a first protocol dialect. The method of this embodiment includes, for each message in the stream:
• • in a receiver process, converting from the first protocol dialect to a canonical protocol;
  • in a trade process, applying business terms to the message; and
  • in a transmit process, converting from the canonical protocol to a second protocol dialect for transmission of the message in an outbound message stream.
• In a further related embodiment, the method includes:
• • storing in memory each successive change made to the message and any metadata created by the foregoing processes; and
  • in an encapsulation process, accessing memory and creating an encapsulated version of the message that includes (i) the message in original form prior to the receiver process, (ii) the metadata, and (iii) a representation of each successive change made to the message by any of the foregoing processes.
• In yet another embodiment, there is provided a brokerage transaction server, for processing exchange transaction information for exchange brokerage purposes in an inbound digital message stream in a first protocol dialect. The server of this embodiment includes:
• • for each message in the stream:
  • a receiver, coupled to the inbound stream, that converts the message from the first protocol dialect to a canonical protocol;
  • a trading domain processor that applies business terms to the message; and
  • a transmitter that converts the message from the canonical protocol to a second protocol dialect for transmission of the message in an outbound message stream.
• In a further related embodiment, the server further includes memory, coupled to the receiver, the trading domain processor, and the transmitter, that stores each successive change made to the message and any metadata created by the foregoing processes. The server also includes an encapsulation processor, coupled to the memory, that creates an encapsulated version of the message that includes (i) the message in original form prior to the receiver process, (ii) the metadata, and (iii) each successive change made to the message by any of the foregoing processes.
• In embodiments related to each of the foregoing embodiments, the inbound digital message stream is from an electronic exchange server. Optionally, the outbound message stream is directed to a brokerage customer server. Alternatively, the inbound digital message stream is from a brokerage customer server, and optionally, the outbound digital message stream is directed to an electronic exchange server.
• Alternatively or in addition, at least one of the first protocol dialect, the second protocol dialect, and the canonical protocol is a version of the FIX protocol. Optionally, the first protocol dialect, the second protocol dialect, and the canonical protocol are versions of the FIX protocol.
• In another related embodiment is a method of providing a record of receipt and processing by the brokerage transaction server relating to a specific message in the stream. In this embodiment, the method further includes:
• • for each message in the stream, storing in a storage medium the encapsulated version of the message;
  • retrieving from the storage medium an encapsulated version of the specific message; and
  • using data in the encapsulated version of the specific message to reconstruct the specific message as received and processing of the specific message by the brokerage transaction server.
• In another embodiment, the invention provides a method of processing a series of order transactions in an order stream before clearing processing. The method of this embodiment includes:
• • buffering the order stream in a buffer;
  • separating the order stream into a plurality of back-end processing streams, in such a manner that transactions in the buffer pertaining to the same order are fed to the same one of the back-end processing streams; and
  • in each of the back-end processing streams, collapsing transactions pertaining to the same order according to established criteria, to produce a compressed output.
• In a further related embodiment, buffering the order stream in a buffer includes storing, in a held set, a set of order IDs to be currently processed in the back-end processing streams; storing, in a held map, a map of order IDs that are currently in the held set to lists of transactions in queue for back-end processing; and storing, in an order map, a map of order IDs to lists of transactions in queue for back-end processing until there is an associated order ID currently in the held set.
• Yet another embodiment provides a clearing interface server for processing a series of order transactions in an order stream before clearing processing. The server of this embodiment includes:
• • a transaction inserter;
  • a first plurality of order data structures established in memory as a buffer coupled to the transaction inserter for storing data to be processed;
  • a second plurality of back-end processors coupled to the order data structures, in such a manner that transactions in the buffer pertaining to the same order are fed to the same one of the back-end processors, each back-end processor collapsing transactions pertaining to the same order according to established criteria, to produce a compressed output.
• An a further related embodiment, the order data structures include a held set, in which are stored a set of order IDs to be currently processed in the back-end processing streams; a held map, in which is stored a map of order IDs that are currently in the held set to lists of transactions in queue for back-end processing; and an order map in which is stored a map of order IDs to lists of transactions in queue for back-end processing until there is an associated order ID currently in the held set.
• Yet another set of related embodiments provides, for each member of the set, a digital storage medium encoded with instructions that, when loaded into a digital computer system, establishes a distinct one of the methods and servers described above. More specifically, one embodiment of the present invention provides a non-transitory digital storage medium encoded with instructions that, when loaded into a digital computer, cause the computer to implement a method of processing exchange transaction information for exchange brokerage purposes in an inbound digital message stream in a first protocol dialect. The implemented method includes, for each message in the stream, in a receiver process, converting from the first protocol dialect to a canonical protocol; in a trade process, applying business terms to the message; and in a transmit process, converting from the canonical protocol to a second protocol dialect for transmission of the message in an outbound message stream. In a further related embodiment there is provided a non-transitory digital storage system wherein the method further includes: storing in memory each successive change made to the message and any metadata created by the foregoing processes; and in an encapsulation process, accessing memory and creating an encapsulated version of the message that includes (i) the message in original form prior to the receiver process, (ii) the metadata, and (iii) each successive change made to the message by any of the foregoing processes. Yet another embodiment provides a non-transitory digital storage medium encoded with instructions that, when loaded into a digital computer, cause the computer to implement a method of processing a series of order transactions in an order stream before clearing processing, wherein the method includes buffering the order stream in a buffer; separating the order stream into a plurality of back-end processing streams, in such a manner that transactions in the buffer pertaining to the same order are fed to the same one of the back-end processing streams; and in each of the back-end processing streams, collapsing transactions pertaining to the same order according to established criteria, to produce a compressed output.
BRIEF DESCRIPTION OF THE DRAWINGS
• The foregoing features of the invention will be more readily understood by reference to the following detailed description, taken with reference to the accompanying drawings, in which:
• FIG. 1 is a diagram of the architecture of a brokerage transaction server in accordance with an embodiment of the present invention;
• FIG. 2 is a diagram of logical flow of message processing by the brokerage transaction server ofFIG. 1;
• FIG. 3 is a diagram of an E-FIX message used in the embodiment ofFIG. 3; and
• FIG. 4 is a diagram of the software system architecture ofclearing interface server15 ofFIG. 1.
DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS
• Definitions. As used in this description and the accompanying claims, the following terms shall have the meanings indicated, unless the context otherwise requires:
• A “canonical protocol” associated with a brokerage transaction server is a protocol used internally by the brokerage transaction server as a format of transaction messages processed by the server. Embodiments of the present invention include a brokerage transaction server using a canonical protocol based on the Financial Information eXchange (“FIX”) Protocol, which is a series of messaging specifications for the electronic communication of trade-related messages. See the web site at http://www.fixprotocol.org for details on this protocol.
• A “protocol dialect” is a native protocol used by a brokerage exchange server or a brokerage customer server as a format of transaction messages.
• An “encapsulated version of a message” is a transaction message that includes (i) the message in original form prior to any processing, (ii) metadata relating to the message and its processing, and (iii) each successive change made to the message by any processing. When the original message is in the FIX protocol, an encapsulated version of the message is termed an “E-FIX” transaction message.
• FIG. 1 is a diagram of the architecture of a brokerage transaction server (which we sometimes call the “trading server”) in accordance with an embodiment of the present invention. The server of this embodiment includes a number of characteristics, including that it communicates with brokerage customer servers, (most) exchange servers, and some other trading platform entities using the FIX protocol. In embodiments herein, a brokerage transaction server communicates with additional internal servers for the purposes of clearing, report generation, risk monitoring, etc. Exchange-to-brokerage communications and customer-to-brokerage communication typically use variants of the FIX protocol, while internal communications among servers according to various embodiments described herein use E-FIX. (We describe E-FIX in detail below in connection withFIG. 3.)
• The present embodiment has been developed so that all of the information necessary for high availability, database maintenance, logging, reporting, etc., can be derived solely from the combined FIX streams passing through the brokerage transaction server, augmented by additional information included in E-FIX headers.
• InFIG. 1, the brokerage transaction server10 (sometimes herein called the trading server) includes the following principal architectural components, which are implemented in software: exchange handlers (of which the number may be arbitrary, here represented here byitems111,112, and113) for interfacing with exchange servers associated withexchanges101 of interest; customer handlers (of which the number may be arbitrary, here represented byitems121 and122) for interfacing with brokerage customer servers ofcustomers102;FIX session layer11, which supervises communications withexchanges102 and with customers and passes messages to and from trading domains12 (of which the number may be arbitrary). Thetrading domains12 implement the transaction server's business logic in message processing; andE-FIX manager14 manages all E-FIX transaction messages.
• For back-end processing of transactions, thebrokerage transaction server10 is in communication withclearing interface server15. The output of theclearing interface server15 goes to downstream clearing processing, indicated bycloud17. Because many customer orders do not lead to completed trades on exchanges, we have found it valuable to simplify downstream clearing processing by a preprocessing arrangement implemented by theclearing interface server15. The clearing interface server integrates related E-FIX transaction messages. As we describe in further detail in connection withFIG. 4, theclearing interface server15 includes atransaction inserter405 operating on a set oforder data structures16. In turn, a set of back-end processors410,411, and412 operate in parallel on the transactions inserted into theorder data structures16 to achieve the integration of related transaction messages, before they are passed on for clearing incloud17.
• Aseparate exchange handler111,112, or113 is used for interfacing with each different exchange server. Each exchange handler converts messages between the exchange's native protocol (which we call a “protocol dialect”) and the brokerage transaction server's canonical FIX. Such conversion may require anything from minor adjustments in the way an exchange uses particular FIX tags to wholesale protocol translation (e.g., when the exchange's server uses OUCH). Oneexchange handler111,112, etc. exists for each separate exchange server to which the trading server is able to connect (NET, ARCA, etc.). Each exchange handler is intended to handle all of the exchange-specific functions necessary for the trading server to operate with that exchange, allowing the remainder of the trading server implementation—in particular the trading domains—to remain exchange-independent.
• If customers conform to the canonical FIX protocol, there is no need to convert messages to or from canonical FIX in thecustomer handlers121 and122. However, in the event that a brokerage customer server uses a variant dialect protocol, a customer handler is implemented to translate between the variant dialect and canonical FIX.
• Once messages from the exchange servers have been translated into canonical FIX, they are passed to thetrading domain12 corresponding to the account associated with the connection on which the message was received. Thetrading domain12 handles the business processing associated with the brokerage function.
• A copy of every canonical FIX message that is processed by atrading domain12 is passed to theE-FIX manager14. TheE-FIX manager14 is responsible for managing all E-FIX transaction communications to and from the trading server and for maintaining a local E-FIX journal of such transactions. The time-ordered sequence of E-FIX messages that are generated as a result of FIX messages being passed to theE-FIX manager14 is called the “E-FIX stream.” By the time it reaches theE-FIX manager14, each FIX message is accompanied by a message descriptor that identifies the message's source, destination(s), trading domain, processing status (i.e., whether it was processed successfully, failed validation, rejected, etc.), modification history (a description of any changes—tag adds/modifies/deletes—made to the message in the course of processing it), billing information, etc. This information is used to construct the header used for E-FIX encapsulation.
• FIG. 2 is a diagram of logical flow of message processing by the brokerage transaction server ofFIG. 1. Here we consider processes implemented by the architecture ofFIG. 1. The brokerage transaction server ofFIG. 1, the trading server, is here identified asitem21. An input to thetrading server21, which may be a message stream from a server associated with a brokerage customer or with an exchange, is here given a generic label—since the processing stages experienced by any such message stream are similar—as aFIX source22. The message stream experiences pipeline processing through n stages (here, n=3), and is sent to itsFIX destination23. When theFIX source22 is an exchange server, then the FIX destination may be one or more brokerage customer servers; and vice versa: when theFIX source22 is a broker customer server, then the FIX destination may be one or more exchange servers. The processing strategy is to preserve the essential character of each message27 in the input stream and modifying the message as necessary to produce the desired message format in the output stream. The modifications and metadata, collectively indicated byitem28, associated with each message, are stored in memory during processing. At the end of processing, theE-FIX message29 is established from the data stored in memory, and the E-FIX message is stored in non-volatile storage so as to provide a historic record of the original message and to enable reconstruction of the message through all stages of processing.
• Embodiments of the present invention benefit by using canonical FIX in a number of ways. First, the canonical representation enables the business logic to process transactions independent of the protocol dialect of the relevant sources of data. Second, because the canonical protocol used here is based on FIX, and because many of the entities with which the brokerage transaction server is in communication use dialects of FIX, the translation overhead in converting into and out of the canonical protocol is kept to a minimum In this fashion numbers of fields in messages running through the brokerage transaction server require no translation in either direction. In various embodiments, canonical FIX is implemented both as a normalized version of FIX to provide a standard protocol in which the business logic can operate, and to minimize the translation overhead among protocol dialects.
• In the first stage of processing, indicated aspipeline stage 1,item24, the message is converted from its protocol dialect of FIX into the brokerage transaction server's canonical FIX protocol. (If the incoming message stream is already in canonical FIX, of course no conversion is necessary.) Inpipeline stage 2,item25, the message undergoes business-level validation and processing and is converted from its inbound format to its outbound format. (By such conversion, for example, a message from an exchange server identifying the brokerage server's broker as the trader will be reformatted to identify the brokerage customer as the trader.) In pipeline stage 3, item26, the message is converted from canonical FIX protocol to into the protocol dialect of theFIX destination23. (Again, if the FIX destination already uses canonical FIX, then of course no conversion is necessary.) As discussed previously, by the time the processed message is provided as an output to theFIX destination23, there has also been established a corresponding E-FIX message that is stored to document the receipt, processing, and export of the message.
• We now turn to E-FIX transaction message structure, which is shown inFIG. 3. As discussed, an E-FIX transaction message contains a copy of the FIX message that was processed by the trading server, along with additional information such as validation/processing status, timestamps, trading domain identification, and fees/rebates. In addition, each E-FIX transaction message contains a description of the modifications that were made to the encapsulated FIX message in the course of forwarding it to the destination exchange or customer. These transaction messages are identical to the entries written to the trading server's local E-FIX journal, which may be used to recover server state following a crash or power failure.
• The E-FIX protocol is primarily unidirectional, with information flowing from a brokerage transaction server to one or more auxiliary brokerage servers (such as the clearing interface server, discussed below), which we here call “E-FIX listeners.” The sequence of E-FIX messages corresponding to the activity on a brokerage transaction server is called an “E-FIX stream.” One E-FIX listener may be designated as the “synchronous” listener. The brokerage transaction server will attempt to maintain loose synchronization with that listener by limiting the number of outstanding (unacknowledged) transactions at any given time. E-FIX runs over a reliable transport protocol, such as TCP. This eliminates the need for explicit fragmentation, retransmission, acknowledgment, and sequencing. The only exception is a mechanism for optional application-level acknowledgment used to maintain synchronization with the synchronous listener.
• InFIG. 3, we see fields used in the E-FIX transaction message. Each E-FIX message begins with a fixed-size header. The format of the portions of the message following the header depends on the contents of the Type field. “EFIX” Marker (32 bits): The first four bytes of every E-FIX message contain the ASCII characters ‘E’, ‘F’, ‘I’, and ‘X’, respectively (i.e., the 32-bit integer 0x45464958 in network byte order). This marker allows the receiver to more easily detect errors that result in loss of synchronization with message boundaries within the TCP byte stream. Version (8 bits): Indicates the format of the E-FIX header. Type (8 bits): Indicates the type of the message. The following message types are defined:
• • 1. Join
  • 2. Transaction
  • 3. Acknowledgment
  • 4. End
• Flags (3 bits): Reserved, must be zero.
• Message Length (13 bits): An unsigned integer indicating the total length of the message, including the E-FIX header, in bytes. The maximum length of an E-FIX message is 8,191 bytes.
• Transaction ID (64 bits): The identifier associated with this transaction. Within a given trading day, the transaction IDs generated by a trading server are guaranteed to be unique and strictly increasing, i.e., each transaction ID is strictly greater than all earlier IDs generated that day. Transaction IDs are not globally unique across trading servers and/or trading days and are not guaranteed to be consecutive.
• Trading Domain ID (32 bits): The unique ID of the trading domain that processed the transaction. For messages that are not associated with a trading domain (e.g., certain session layer messages), this field contains zero.
• Source Account ID (32 bits): The unique ID of the market or client account that originated the transaction. For messages originated by the trading server itself (e.g., position responses), this field contains zero.
• Destination Account ID (32 bits): The unique ID of the market or client account to which the transaction was sent. For messages consumed by the trading server itself (e.g., position requests), this field contains zero.
• Timestamp (64 bits): The time at which the transaction was committed, expressed as a standard POSIX timeval value (i.e., the number of seconds and microseconds since midnight GMT on Jan. 1, 1970).
• Flags (8 bits): Note: In the descriptions below, bit7 is the least significant bit; bit0 is the most significant. Bit7: Acknowledgment Requested. Indicates that the receiving E-FIX listener should send an application-level E-FIX Acknowledgment message back to the trading server. The Acknowledgment message should contain the transaction ID of the Transaction message being acknowledged. This flag is used to maintain synchronization with the commit E-FIX listener (typically, the HA standby). Bit6: Indirect. Indicates that the transaction originated on another trading server. This flag is set by standby trading servers and by other devices that forward E-FIX messages received from an active server. Bit5: Exclude Primary. Indicates that the encapsulated FIX message was not sent to the destination account's primary FIX session, i.e., that it was sent only to the sessions indicated by the Destination Session options. Bit4: Truncated. Indicates that the received FIX message exceeded the maximum allowed length of2048 bytes and that the contents of the received message field have been truncated. Bits0-3: Reserved, must be zero.
• Status (8 bits): Indicates the status of trading server processing of the transaction.
• Reason (16 bits): Gives additional information related to the contents of the Status field.
• Options Length (16 bits): Indicates the length in bytes of the Options portion of the Transaction message. A length of zero indicates that the Options field is not present.
• FIX Message Length (16 bits): Indicates the length in bytes of the encapsulated FIX message. A length of zero indicates that the FIX Message field is not present.
• Receive Delta Length (16 bits): Indicates the length in bytes of the Receive Delta portion of the Transaction message. A length of zero indicates that the Receive Delta field is not present.
• Canonical Delta Length (16 bits): Indicates the length in bytes of the Canonical Delta portion of the Transaction message. A length of zero indicates that the Canonical Delta field is not present.
• Transmit Delta Length (16 bits): Indicates the length in bytes of the Transmit Delta portion of the Transaction message. A length of zero indicates that the Transmit Delta field is not present.
• Reserved (16 bits): Must be zero.
• Options (variable length): The Options field contains a list of optional items related to the transaction. Each item is encoded as a <type, length, value> triplet.
• The Option Type field identifies the option; Option Length is a 16-bit unsigned integer containing the length of the option, including the type and length fields, in bytes. Option Value is variable-length; its interpretation depends on the option type. The following option types are defined:
• • 1. Authority (variable-length). The username of the user that initiated the transaction.
  • 2. Source Session (32 bits). The session ID of the session on which the message was received (omitted if the message was received on the primary session).
  • 3. Destination Session (12 bytes). The 32-bit session ID and the 64-bit sequence number of each non-primary session to which the message was sent.
  • 4. Fee (variable-length). A 3-tuple encoded as <Authority> SOH <Execution ID> SOH <Amount>
  • 5. Rebate (variable-length). A 3-tuple encoded as <Authority> SOH <Execution ID> SOH <Amount>
  • 6. Fee Reversal (variable-length). A 4-tupal encoded as <Authority> SOH <Execution ID> SOH <Original Execution ID> SOH <Amount>
  • 7. Rebate Reversal (variable-length). A 4-tupal encoded as <Authority> SOH <Execution ID> SOH <Original Execution ID> SOH <Amount>
  • 8. Log Level (8 bits). An unsigned integer.
  • 9. External ID (variable-length). A market-specific character string.
  • 10. Received Message (variable-length). A copy of the message as received directly from the source. Intended primarily for non-FIX messages.
  • 11. Transmitted Message (variable-length). A copy of the message as transmitted directly to the destination. Intended for non-FIX messages and for FIX messages in cases where an exact copy is required in addition to the transmit Delta.
  • 12. Account (32 bits). The account ID of the account associated with the transaction, if different from the source account.
  • 13. Buying Power (96 bits). The current buying power of the account associated with the transaction. The value is expressed as a signed 64-bit integer with units specific to the trading domain (e.g., pennies for U.S. equities trading domains). The value is preceded by 32 bits of padding in order to preserve natural alignment. A single Transaction message may contain multiple occurrences of a given option type.
• FIX Message (variable length): The encapsulated FIX message.
• Receive Delta (variable length): The Receive Delta field describes the modifications that were made to the encapsulated FIX message in order to convert it to canonical FIX. Modifications include adding, replacing, and deleting FIX fields. This field consists of a sequence of items, each of which is terminated by an ASCII SOH character. Each item is either an ASCII-encoded FIX tag number (integer) or a tag number followed by an equals sign (‘=’) and a value string. Stand-alone tag numbers represent FIX fields that were removed from the original message during processing; tag=value items represent FIX fields that were either added (if not present in the original message) or replaced (if present in the original message). Tags should not be repeated. If the Transaction message does not contain an encapsulated FIX message (i.e., the FIX Message Length contains zero), then the Receive Delta conceptually operates on an empty FIX message.
• Canonical Delta (variable length): The Canonical Delta field describes the modifications that were made to the received canonical FIX message (i.e., the result of applying the Receive Delta to the encapsulated FIX message) in the course of FIX session layer and trading domain processing. This field has the same format as the Receive Delta field.
• Transmit Delta (variable length): The Transmit Delta field describes the modifications that were made to the transmitted Canonical FIX message (i.e., the result of applying the Receive Delta and Canonical Delta to the encapsulated FIX message) in order to conform to the requirements of the destination. This field has the same format as the Receive Delta and Canonical Delta fields.
• As discussed above, each E-FIX transaction message is sent to all connected E-FIX listeners, including theclearing interface server15 ofFIG. 1. The contents of the E-FIX message stream are sufficient to reconstruct the order flow state information needed during back-end processing.FIG. 4 is a diagram of the software system architecture ofclearing interface server15 ofFIG. 1. In accordance with an embodiment of the present invention, the clearing interface, typically running on a computer physically distinct from that of the brokerage transaction server, is in communication with the brokerage transaction server to establish and store the order state resulting from transactions, handled by the brokerage transaction server, in a manner to represent the disposition of orders from brokerage customers. Because theinterface server15 integrates related E-FIX transaction messages, we also call it a “transaction fuser.” The transaction fuser of this embodiment operates to split the incoming order flow into multiple independent streams of data, all of which can be processed in parallel without any dependency between them. This allows the back-end job to process this data in parallel and increase throughput. Since the back-end job does not care about intermediate order states, wherever possible, multiple transactions which operate on the same data should be “collapsed” into a single transaction which reflects the final end state of the order.
• The single input of the fuser ofFIG. 4 is coupled to theE-FIX manager14 ofFIG. 1. This input goes to atransaction inserter405, which in turn is coupled throughorder data structures16 ofFIG. 1 (implemented asitems401,402,403, and404 discussed below) to a plurality of back-end processors, here identified asitems410,411, and412. The number of back-end processors depends on how much parallelism theclearing processing17 ofFIG. 1 can handle. The fuser itself has no limit to the number of outputs it can provide. Moreover, there is a back-channel by which the back-end processors can inform thetransaction inserter405 of when they are done processing a set of data relating to orders.
• The fuser has a number of additional components, stored internally, not visible to the producer or consumers of the order flow. These are the held set404, the heldmap403, theorder map402, and theorder ID queue401. The held set404 is a set of order IDs which are currently being processed by the back-end job. The heldmap403 is a map of order IDs to lists of transactions which are currently being “held.” A transaction is “held” if it is inserted into the queue, but its associated order ID is present in the held set404. Theorder map402 is a map of order IDs to lists of transactions which are currently available to be consumed by the back-end job. Theorder ID queue401 is a queue of order IDs which have transactions that are currently available to be consumed by the back-end job. These are generally queued in the order in which they are inserted into the fuser.
• Thetransaction inserter405 implements the following procedure: (a) Obtain the associated order ID from the transaction. (b) Check if that order ID is present in the held-set404. If it is, insert the transaction into the held-map403. Otherwise, insert the transaction in the order-map402, and push the order ID onto the back of theorder ID queue401, if there was no previous transaction(s) for that order in the order-map402. (Here by “insert the transaction” for the order-map and held-map, we mean looking up the list of transactions for that associated order ID, and if the list exists, inserting it at the end of the list, otherwise, creating a new list with just that single transaction.)
• Each back-end processor410,411, and412 operates to implement the following procedure: (a) Remove an order ID from theorder ID queue401. If there is none present, there is no data available to be processed. (b) Insert that order ID into the held-set404. (c) Look up that order ID in the order-map402, and return the list of transactions for that order, removing it from the order-map402.
• The back-end processor repeats the above removal procedure multiple times until it has obtained the amount of work it desires to process. It then “flattens” the list of transactions into a single transaction representing the end-result it cares about (the flattening procedure is dependent on the exact nature of the back-end job), and then processes the data.
• At some point, the back-end processor finishes processing the data and wishes to consume more. It can repeat the removal procedure to obtain more data, but first it must perform a “finalization” procedure to notify thetransaction inserter405 that order data obtained previously by the back-end processor has now been processed. The finalization procedure is as follows: (a) Remove the associated order ID from the held-set404. (b) Look up the associated order ID in the held-map403. If any transactions are present, move them into the order-map402, removing them from the held-map403, and inserting the associated order ID into theorder ID queue401.
• The above procedure is repeated for each associated order ID for transactions the back-end processor last obtained from theinserter405.
• Note that we assume that only one entity is using the “insertion procedure” at any given time (the producer of the order-flow), but multiple entities (the back-end job) can be executing the “removal” and “finalization” procedure simultaneously. The fuser uses appropriate locking to protect concurrent modification of its data structures. In this manner, the back-end processors can operate as independent parallel processes to remove data, process it, and finalize it.
• When a back-end processor removes data from thetransaction inserter405, the back-end processor always removes all transactions connected to a particular order in thetransaction inserter405; therefore it will be the only one handling data for that order. If an additional transaction for that order is inserted into the fuser while that process is still processing transactions for that order, that new transaction will be put in the held set404 and heldmap403. Therefore it will not be made available for another process to obtain until the process which holds the rest of that order's transactions and “finalizes” that order ID. This approach frees the new transaction from the held-set and held-map, and makes it available for any process to obtain. This mechanism ensures that a given back-end processor has the guarantee that when it obtains transactions for an order from the fuser, no other back-end processor will simultaneously also obtain transactions for that order. That is to say, the transactions for a single order will always be serialized with respect to each other.
• Removing from thetransaction inserter405 always returns a list of transactions. These transactions all relate to the same order, and the list reflects the ordering in which they were inserted into the fuser. It is then a straightforward matter for downstream processes to walk this list and flatten the transactions in whatever manner desired.
• Theorder ID queue401 is not strictly necessary, as the back-end processor can pick an arbitrary order ID that is present in theorder map402. However, since order IDs are inserted into theorder ID queue401 in the order in which they are inserted into the fuser (or finalized), then it is advantageous to use this queue to try to process orders which have been in the fuser longest.
• The fuser has the interesting property that it becomes more effective and efficient for the back-end job the fuller it becomes. That is to say, it scales well with how fast the back-end job is operating. If the back-end job is keeping up with the current rate of order-flow generation, then very few, if any, transactions will be in the fuser at any given point, so almost no linking of transactions will be done. However, once the back-end job begins to fall behind the rate of production, the fuser will begin to fill. At this point, there are more and more transactions in the fuser, and a transaction being inserted has a much higher probability it will encounter a transaction for the same order in the fuser, and these related transactions will be linked together. When the (overwhelmed) back-end job goes to remove transactions for that order, it will be able to flatten them together into one transaction. If it had been keeping up, it would have removed each transaction on two different occasions, and would have done (roughly) twice as much work. Therefore, the more the back-end job falls behind, the more linking that is performed, and the less work the back-end job must actually perform. Of course, this approaches a limit, as the number of transactions for any given order is bounded. Under any significant load, it has been observed that all the transactions connected to a given order are almost always linked together into just one composite transaction.
• The software structures described in this application may be implemented in general purpose digital computers, running standard operating systems such as Linux. Accordingly, when such a computer is loaded with suitable instructions stored in a digital storage medium, there can be established embodiments of the brokerage transaction server described above and claimed below, and there can be established embodiments of the clearing interface server described above. A digital storage medium storing such instructions is also within the scope of embodiments described herein. A computer running embodiments of the brokerage transaction server application has network connections to the brokerage customer servers, to the exchange servers, and to the computer hosting the clearing interface. Such computers may usefully have multiple CPUs. Alternatively the software structures may be implemented directly in hardware, using, for example, field programmable gate arrays (FPGAs) or application specific integrated circuits (ASICs).
• The embodiments of the invention described above are intended to be merely exemplary; numerous variations and modifications will be apparent to those skilled in the art. All such variations and modifications are intended to be within the scope of the present invention as defined in any appended claims.
• Some of the functions performed by the brokerage transactions server have been described with reference to flowcharts and/or block diagrams. Those skilled in the art should readily appreciate that functions, operations, decisions, etc. of all or a portion of each block, or a combination of blocks, of the flowcharts or block diagrams may be implemented as computer program instructions, software, hardware, firmware or combinations thereof. Those skilled in the art should also readily appreciate that instructions or programs defining the functions of the present invention may be delivered to a processor in many forms, including, but not limited to, information permanently stored on non-writable storage media (e.g. read-only memory devices within a computer, such as ROM, or devices readable by a computer I/O attachment, such as CD-ROM or DVD disks), information alterably stored on writable storage media (e.g. floppy disks, removable flash memory and hard drives) or information conveyed to a computer through communication media, including wired or wireless computer networks. Furthermore, although some aspects of the brokerage transactions servers have been described with reference to a flowchart, those skilled in the art should readily appreciate that functions, operations, decisions, etc. of all or a portion of each block, or a combination of blocks, of the flowchart may be combined, separated into separate operations or performed in other orders. Moreover, while the embodiments are described in connection with various illustrative data structures, one skilled in the art will recognize that the system may be embodied using a variety of data structures. Furthermore, disclosed aspects, or portions of these aspects, may be combined in ways not listed above. Accordingly, the invention should not be viewed as being limited to the disclosed embodiments.

Claims (5)

1. A method of processing a series of order transactions in an order stream before clearing processing, the method comprising:

buffering the order stream in a buffer;

separating the order stream into a plurality of back-end processing streams, in such a manner that transactions in the buffer pertaining to the same order are fed to the same one of the back-end processing streams; and

in each of the back-end processing streams, collapsing transactions pertaining to the same order according to established criteria, to produce a compressed output.

2. A method according toclaim 1, further comprising:

wherein buffering the order stream in a buffer includes storing, in a held set, a set of order IDs to be currently processed in the back-end processing streams; storing, in a held map, a map of order IDs that are currently in the held set to lists of transactions in queue for back-end processing; and storing, in an order map, a map of order IDs to lists of transactions in queue for back-end processing until there is an associated order ID currently in the held set.

3. A clearing interface server for processing a series of order transactions in an order stream before clearing processing, the server comprising:

a transaction inserter;

a first plurality of order data structures established in memory as a buffer coupled to the transaction inserter for storing data to be processed; and

a second plurality of back-end processors coupled to the order data structures, in such a manner that transactions in the buffer pertaining to the same order are fed to the same one of the back-end processors, each back-end processor collapsing transactions pertaining to the same order according to established criteria, to produce a compressed output.

4. A clearing interface server according toclaim 3, further comprising:

wherein the order data structures include a held set, in which are stored a set of order IDs to be currently processed in the back-end processing streams; a held map, in which is stored a map of order IDs that are currently in the held set to lists of transactions in queue for back-end processing;

and an order map in which is stored a map of order IDs to lists of transactions in queue for back-end processing until there is an associated order ID currently in the held set.

5. A non-transitory digital storage medium encoded with instructions that, when loaded into a digital computer, cause the computer to implement a method of processing a series of order transactions in an order stream before clearing processing, wherein the method comprises:

buffering the order stream in a buffer;

separating the order stream into a plurality of back-end processing streams, in such a manner that transactions in the buffer pertaining to the same order are fed to the same one of the back-end processing streams; and

in each of the back-end processing streams, collapsing transactions pertaining to the same order according to established criteria, to produce a compressed output.

Images