FORM – 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE
Specification
(See section 10 and rule 13)
AN APPARATUS FOR ORDER MATCHING IN MATCHING ENGINE
FOR STOCK EXCHANGE
TATA CONSULTANCY SERVICES LIMITED

an Indian Company of Bombay House, 24, Ho, Sir Homi Mody Street,

THE FOLLOWING SPECIFICATION PARTICULARLY DESCRIBES THE INVENTION AND THE MANNER IN WHICH IT IS TO BE PERFORMED.

This invention relates to matching engines for stock exchanges.
Stock exchanges provide an electronic trading facility to.thousands of traders. At the core of trading system is the matching engine that maintains pending or passive orders of both buyers and sellers, and whenever a new order (active order) enters the exchange it attempts to match the order against the passive orders.
Typically, a known matching engine maintains an order book for buy orders and a corresponding order book for sell orders. This is the database of pending orders in the system. For an active buy order the matching engine needs to compare it with orders in the sell order book that are at either at lower price or the same price (in ascending order of price). Conversely, for an active sell order the matching engine needs to compare it with orders in the buy order book that are either at price higher or the same price (in descending order of price).
Before an order can be matched it needs to be validated. This includes basic checks on the security, investor, price, quantity and other such attributes of the order. In some stock exchanges there also a guard against short selling. In other words, an investor cannot 'sell' a security unless he holds enough positions to place the sell order. This guards against an investor first selling and later buying securities without having any security holdings to begin with.
Once an order is validated, it is a confirmed order in that the exchange has accepted it and will proceed to process it for matching as per the

description above. The matching engine needs to send an order confirmation back to the trader within a specific response time so that the trader can quickly know whether his order has been accepted or rejected by the exchange.
The matching engine, in real life, has to address several challenges in the context of a large stock exchange. This includes:
1. Processing hundreds to thousands of orders per second at peak
2. Sustaining the peak for several minutes, particularly, at start of and end of day
3. Ensuring tolerance to failures, such that, once an order is received it is not lost and order processing activity resumes in real time if there is a failure
4. Providing high order processing rates in a 'hot set' of securities
5. Validating basic order attributes and guarding against short selling for an investor holdings base of millions of records, at peak rates of thousands of orders per second
The first property is a common phenomenon in large stock exchanges. At the beginning of the day there is high trading activity, very often to determine the opening price of a security. At the end of the day, traders tend to square off their trading activity for the day and this results in a surge of processing typically towards the last 15min to 30min.
Property 3 is an essential feature of all stock exchanges, and this has often led to proliferation of fault-tolerant computers such as Tandem and Stratus. Although Unix systems, of late, provide higher performance and scalability they are often not used because they do not provide any built-

in fault-tolerant capability. Databases on Unix systems provide features for recovery but they are typically unable to process thousands of orders per second and at the same time recovery from failure in real time.
Property 4 is a natural phenomenon whenever there is an initial public offer (IPO) on a new security that is listed in the market. It is also quite common to see stock exchanges where a few securities dominate trading activity for several days at a stretch. A consequence of this property is that scalability can be significantly limited because of the sequential nature of processing a single security. In a stock exchange, for a single stock, one cannot allow multiple server processes to concurrently process orders since all orders need to be processed in a first-come-first-serve (FCFS) basis.
Property 5 also has significant implications on performance and recovery. An investor base of millions of records would typically require storage in a standard database management system (DBMS). However, for a standard DBMS to support thousands of validations per second and at the same time provide real-time recovery, is not a realistic assumption unless there is very large investment in infrastructure.
To summarize the challenges in a real life, large stock exchange: • Processing of thousands of orders and validations per second and at the same time recovering from failures in real time, typically rules out the use of standard DBMS products. At the same time, a standard DBMS is desired to store not only orders but also investor holding positions that will typically be in several millions.

Processing of hot securities poses a serious limitation to scalability unless the matching engine is highly engineered for this case.
Prior art matching engines known in the art are not in a position to perform the above functions adequately. The prior art matching engines in stock exchanges use 'stratus' or 'tandem' machines. These machines are fault-tolerant machines . Stratus machines are limited to only 2 CPU, whose clock speeds are far below those available on Unix and Windows platforms. On the other hand Tandem machines provide higher number of CPUs (up to 16) but the scalability across CPUs is significantly lower than Unix machines.
While one may still argue that both Stratus and Tandem systems have a future path, one cannot doubt the superior performance and scalability capabilities provided by open systems (i.e., Unix). In particular, for very large stock exchanges, it is not only the CPU intensive processing of matching but also the communication with other components that needs to be done at thousands to tens of thousands of messages per second. The difficulty with use of Unix systems lies with their limited features for fault-tolerance. The use of redundant network cards and links, and the use of storage area networks (SANs) in Unix systems can alleviate the issues with network and disk failure. However, CPU and memory failures are today not handled as robustly in Unix as they are on Stratus and Tandem machines, or even IBM mainframes.
The present invention relates to a Matching Engine used in Stock Exchange, which uses an Electronic Trading System.

Unix machines provide a very cost effective solution and it is up to the application architecture to ensure real time recovery. The Present Invention provides a High Performance and fault tolerant matching Engine that runs on Unix Systems for use in a a Stock Exchange System. The Matching Engine in accordance with this invention :
1. is Able to process hundreds to thousands of orders per second at
peak.
2. achieves a peak rate that can be sustained for several minutes
3. Ensures tolerance to failure, which guarantees that, once the order is received it is not, lost and orders processing activity resume in real time if there is failure.
4. Provides a high order processing rates in a 'hot set' of securities.
5. Validates basic order attributes and guarding against short selling for an investor holdings base of millions of records, at peak rates of thousands of orders per second.
The technology chosen for the matching engine in accordance with this invention is Unix. The current implementation of the matching engine has been tested successfully on HP-UX 1 li, but it can be easily ported to any flavour of Unix such as Solaris or AIX.
1. The embedded software in the stock exchange matching engine in accordance with this invention has been implemented in C
2. It has been developed and tested on 64-bit HP-UX 11i
3. It internally uses the following constructs of Unix
o Memory mapped files to store the order book and investor holdings

Sequential file write for order confirmations and for trade confirmations (these logs are used for recovery purpose).
In accordance with this invention there is provided in a matching engine for stock exchanges an apparatus for Order Matching consisting of
a) an In-memory Data structure adapted to be used for storing Orders in predefined index,
b) Accessing Means to access the In-Memory Data Structures for updating or storing the Order Data,
c) Creating Means for Creating an In Memory Order Book,
d) Initializing Means for Initializing the created In Memory Order Book,
e) In memory Data structure adapted to be used for storing Investor holding data,
f) Creating Means for Creating an Investor Holdings Table.
g) Viewing Means for viewing the current state of the Order Book,
h) Accessing Means to access the in memory Holding Data structures
for storing the Investor Holding data, and i) Means to write the order and holding data to a persistent data store.
In accordance with a preferred embodiment of this invention, the means for accessing the In Memory Order Book includes
• Means for Selecting the Orders based on predefined index,
• Means for Updating the Orders,
• Means for Deleting the Orders
• & means for Inserting a Data Record.

In the embodiment of the matching engine a high performance matching and holdings validation is possible because of the use of custom in-memory data structures. There are two key data structures that enable the high performance solution:
1. A combination of arrays and linked lists for the order book, referred to as a T-tree structure. This structure permits 0(1) access to a security's buy and sell orders that are maintained in sorted order of price. The matching of orders is guaranteed to occur in 0(1) time, and insertion of unmatched orders is sped up by the use of price range lists. Each price range list maintains a set of prices with a linked list of orders (in time priority) for the given price. The number of unique prices in the range is a control parameter .
2. A combination of arrays for the investor holdings table. This structure permits 0(1) access to an investor's holdings. The list of holdings is maintained in the form of an array in sorted order of security. Search for a given security is sped up by an empiric choice of linear versus binary search depending upon the number of securities.
A real time recovery methodology is provided for the matching engine. This comprises an active and a passive matching engine that will typically be across machines. Each maintains its own instance of the order book and holdings table. Order confirmations from the active matching engine are read by the passive matching engine and the passive order book is kept at the same state as the active order book. Upon failure of the active instance, the passive matching engine takes over once its input orders are synchronized using the recovery component of message queues.

The two key data structures in the matching engine are the order book and the investor holdings table. The matching engine component provides a set of utilities for:
• Creation of Order Book
• Creation of Investor Holdings Table Binary and Ascii Dumps of Order Book
• Instantaneous snapshot (in Ascii) of Order Book by security
The matching engine has the following interfaces:
• Receive an order (through a custom message queue)
• Log and send an order confirmation (in synchronous mode)
• Log and send a trade confirmation
Once an order is received it is first validated for basic checks on its attributes. This includes checking for security id within range, checking for price validity and quantity validity. The order is then validated against short selling by checking the investor holdings positions. Any invalid order is rejected. A confirmed order has a confirmation message logged to disk after which the message is sent back to the trader. Thereafter, an order is matched against passive orders in the order book. For every trade that occurs a trade confirmation message is logged and sent to the respective traders.
The order confirmation message is logged in synchronous mode, which means that it is first guaranteed that the message is written to disk and

only then it is sent back to the trader. This ensures that in the event of a failure, from the order confirmation log one can ascertain all order confirmations that were sent back to the traders. The order confirmation log is also used as input to a passive recovery engine that maintains its state synchronous with the normal order matching engine.
The unique features of the Matching Engine in accordance with this invention include:
• T-tree based data structure for order matching engine that enables order matching at tens of thousands of orders per second (on state of the art hardware as of May 2003)
• Data structure for investor holdings table that enables real time access to millions of positions
• Recovery algorithm for matching engine that enables split second recovery
The invention will now be described with reference to the accompanying drawings
FIGURE 1 is a block diagram showing architecture of a High
performance, fault tolerant In Memory Matching system.
FIGURE 2 is a flow chart showing the steps carried out by the matching
engine for matching active buy orders.
FIGURE 3 is a flow chart showing the steps carried out by the matching
engine for matching active sell orders.
FIGURE 4 is a data structure used for storing the investors holding
records.

FIGURE 5 is a data structure used for storing the confirmed pending
orders.
FIGURE 6 is a block diagram showing the means to replicate the
transaction on an online basis.
FIGURE 7 is a block diagram showing architecture for recovering the
Matching Engine Component.
BACKGROUND
A stock market provides a facility for traders to buy and sell securities (colloquially known as stocks). Consider for example that a trader A posts an order to sell 100 units of security X at price 50.75. If subsequently a trader B posts an order to buy say 75 units of security X at price 51, this will result in match for the buyer. As a result a trade occurs wherein 75 units of security X are sold at price 50.75 from trader A to trader B.
Stock exchanges provide an electronic trading facility to thousands of traders. At the core of trading system is the matching engine that maintains pending or passive orders of both buyers and sellers, and whenever a new order (active order) enters the exchange it attempts to match the order against the passive orders.
This is the core component of the functionality. It provides validation, investor-holding check, and matching of orders entering the exchange. It generates order and trade confirmations to be sent back to the trader.

The matching engine maintains an order book for buy orders and a corresponding order book for sell orders. This is the database of pending & Confirmed orders in the system. For an active buy order the matching engine needs to compare it with orders in the sell order book that are at either at lower price or the same price (in ascending order of price). Conversely, for an active sell order the matching engine needs to compare it with orders in the buy order book that are either at price higher or the same price (in descending order of price).
Before an order can be matched it needs to be validated. This includes basic checks on the security, investor, price, quantity and other such attributes of the order. In some stock exchanges there also a guard against short selling. In other words, an investor cannot 'sell' a security unless he holds enough positions to place the sell order. This guards against aft investor first selling and later buying securities without having any security holdings to begin with.
Once an order is validated, it is a confirmed order in that the exchange has accepted it and will proceed to process it for matching as per the description above. The matching engine needs to send an order confirmation back to the trader within a specific response time so that the trader can quickly know whether his order has been accepted or rejected by the exchange.
Figure 1 of the accompanying drawings, shows a block diagram of the various components of the system.

COMPONENT DESCRIPTION is as follows
Reference numeral 1 represents the Input Message (Order Request)
Order Request consists of Investor information & security on which
Investor wants to trade, qty and price conditions (like price & qty at which Investor wants to trade) and buy / sell indicator which indicates the whether request is for buying or selling. Order Request has got following attributes
• Order Id
• Investor Id
• Security Id
• Buy-Sell Indicator
• Order Qty
• Order Price
Reference numeral 2 represents the Means to Read the Input Message and Write the response
Order Matching Component Reads the Input Message and Writes The Order and Trade Response using these API.
Reference numeral 3 represents the - Means to validate the Input Message
Orders are validated for following attributes: -
• Security Id
Security Master table is searched for the request security id in the order request message.

If the security id does not exists in the security master table then rejection message is send to Investor for the above order requested message.
• Investor Id
Investor Master Table is searched for the requested Investor id in the
order request message.
If the Investor id does not exists in the Investor master table then
rejection message is send to Investor for the above order requested
message.
• Order Price
Check is made whether requested order price is valid or not. If the order price is invalid (i.e. if order price is negative) then rejection message is send to Investor for the above order requested message.
• Order Qty
Check is made whether requested order quantity is valid or not. If the order qty is invalid (i.e. If Ord Qty <= 0) then rejection message is send to Investor for the above order requested message.
• Buy / Sell indicator
If the request type is not equal to buy or sell then the rejection message is send to Investor for the above order requested message.
Reference numeral 4 represents the - Means To Update The Holding Data
Once the order is validated for the requested attributes, the investor's positions are validated for sell orders, in order to prevent 'short-selling.' Number of positions in each security for different investors is maintained In Memory Holding Data Store [component 6] .The

incoming order is validated against these positions, and the positions
updated by subtracting the order quantity.
Holding Data is updated only for the sell orders.
Holding Data Validation and Updating takes place as follows
1. For an incoming order, take the investor id i, security s & quantity q.
2. For investor i, index in to the holdings array to get the SecPos array pointer.
3. Search for security s in SecPos.
4. If not found, order is invalid.
5. If found, subtract q from the positions in that security.
6. If positions fall below zero, order is invalid.
7. Otherwise, order is considered as valid.
8. If the order is valid then the Active Order is send to Order Matching System.
Reference numeral 5 represents the - Means To Access The Order Book and Match The Orders
The System attempts to match the incoming order request with best counter side order according to price condition specified by the request packet. The Counter side orders are maintained in the systems main memory.
Reference numeral 7 represents the - in memory order data store [order book]
Reference numeral 8 represents the -means to store data to a persistent data store 8- Means To Store The Data to Persistent Data Store (DPS)

DDS component is used to write the Order Confirmation and Trade Confirmation Message to Activity Log before sending it to Other System. Writing Of Each order and Trade Confirmation Message to Disk in synchronous mode will slow down the Process. So In Order to achieve high through put, it buffers the messages in some temporary buffer and after reaching certain predefined value or after certain time interval it flushes the data to Activity Log. This way order and trade confirmation messages are logged in synchronous mode , which guarantees that the message is written to disk and only then it is sent back to the trader. This ensures that in the event of a failure, from the order confirmation log one can ascertain all order confirmations that were sent back to the traders.
Reference numeral 9- represents the passive matching engine having means to replicate the transaction on an online basis
and reference numeral 10 represents means to maintain an activity log. As particularly described with reference to figure 6.
The incoming order is called an active order, and the orders pending in the book are called passive orders. An active order on the buy side will be matched against passive orders on the sell side and vice versa.
Active Order Qty is represented as Qa & Price as Pa
Passive Order Qty is represented as Qp & Price as Pp

EXAMPLE NO 1:-
This example shows how the Matching Engine matches a Active limit buy order with limit sell order.
Active Buy Order Request Order No - 4 Security Id - 1 Order Qty -500 Order Price-101
Sell Order Book

Order
No Security Id Buy Sell Indicator ( B/S) Order Qty Price
1 1 S 200 100
2 1 S 300 101
3 1 S 400 101
In the Above case matching will match the order based on price and time priority. So First active Order will trade with Order No 1 which is The Best Sell Order available in the Sell Side. Then It will trade with Order No 2. So Order No 1 & 2 are deleted from the sell order book. And only order no 3 remains in the Order Book.

EXAMPLE 2 :
This example shows how the Matching Engine matches a Active limit sell
order with limit buy order.
Active Sell Order Request
Order No - 4
Security Id - 1
Order Qty -500
Order Price-101
Buy Order Book

Order
No Security Id Buy Sell Indicator ( B/S) Order Qty Price
1 1 B 200 102
2 1 B 300 100
3 1 B 400 100
In the Above case Matching Engine will match the order based on price and time priority. So First active Order will trade with Order No 1 which is The Best Buy Order available in the Buy Side and also it satisfies the Sell Order Request condition. So Trade is generated for Order Qty 200. Next Order, which has a price of 100, does not satisfy the Order Request condition. So Remaining 300 Quantity from the Requested Order is written to Buy Order Book.
Figure 2 shows a flow diagram for active buy order matching. Referring to figure 2

1. For an active buy order note the security T, price Pa, and quantity Qa.
2. Get list of passive sell orders for security T, in ascending order of price.
3. Pick first passive order from list. If the list is empty go to step 8. Otherwise, let us denote its price as Pp and quantity as Qp.
4. If Pp > Qa then go to step 8
5. Otherwise, a trade will take place at price Pp and quantity min (Qp, Qa). Generate two trade messages and log the trades on to activity file.
6. If Qa < Qp the active order has fully traded. Set Qa = 0 and go to step 8
7. Otherwise, Delete the Passive Order From the Order Book that has traded. Set the active quantity Qa = Qa - Qp, and go to step 3.
8. Matching is complete.
9. If the passive order (Qp) is traded partially then update the passive order in the order book
10. If the active Order Qa > 0, mark the active order as passive and insert it in to the buy order book.
Figure 3 shows a flow diagram for an active selling order matching. In the figure
1. For an active sell order note the security T, price pa, and quantity qa.
2. Get list of passive sell orders for security T, in ascending order of price.

3. Pick first passive order from list. If the list is empty go to step 8. Otherwise, let us denote its price as pp and quantity as qp.
4. If pp > pa then go to step 8
5. Otherwise, a trade will take place at price pp and quantity min (qp, qa). Generate two trade messages and log the trades on to activity file.
6. If qa < qp the active order has fully traded. Set qa - 0 and go to step 8
7. Otherwise, Delete the Passive Order From the Order Book that has traded. Set the active quantity qa - qa - qp, and go to step 3.
8. Matching is complete.
9. If the passive order (qp) is traded partially then update the passive order in the order book
10.If the active Order qa > 0, mark the active order as passive and insert it in to the buy order book.
Figure 4 shows a Data Structure For Storing Holding Data
Figure 4 indicates the data structure used for storing the investor's
positions in each security that an investor is holding. In this Data structure, there is a investor array indexed by investor id. For every investor i, there is an array of securities and positions, which is called SecPos. The SecPos array will vary in size from investor to investor. The list of holdings is maintained in the form of an array in sorted order of security. Search for a given security is sped up by an empiric choice of linear versus binary search depending upon the number of securities.
Means are provided to Create The In Memory Holding Data Store component 7 in figure 1. This means creates the In Memory Holding Data

store. This means reads The Holding Info File, which contains the Holding Information for different Investors.
The data structure for the order book are in figure 5.
FIGURE 5 indicates the data structure used for storing the untraded confirmed orders according to Price & Time Priority. A combination of arrays and linked lists for the order book, that we refer to as a T-tree structure. This structure permits O (.1) access to a security's buy and sell orders that are maintained in sorted order of price. In this Data Structure, there is a Central Array indexed by security to get the buy and sell orders for that security.
Organization of Sell orders: -
As shown in FIGURE 5 Link list of price range is maintained in ascending order.
(Henceforth called as PriceNodeH). Each PricenodeH contains a low price and a high price. The next node in the list pertains to a disjoint interval of price in ascending order. Each Price Range Node has a pointer to an OrderPriceArray that lists the unique prices of passive orders within the price range specified. In turn, the OrderPriceArray maintains a leaner linked list of orders per unique price in time priority (i.e., first-in-first-out list). When an active buy order comes, Order book is searched for sell order which are sorted in ascending order of price. This is available through the price range node. Matching will always take place from the head of the price range list. If no match is found, one will not need to proceed beyond the head of the list. Since Time priority of the Orders is maintained by leaner

linked list. So in Case Of Matching Active Order is most of the time trades with head of the Link list. So rearranging overhead is minimum in case of linear linked list as compared to other Binary trees. So performance of the data structure is maximum because for deletes and inserts rearranging and balancing overheads are less as compared to other Binary trees. Note: - if the Number of securities are less than 40 then leaner search is used for finding the Securities else binary search is used for locating the Security Id.
Organization of Buy orders: -
As shown in FIGURE 5 Link list of price range is maintained in
descending order.( Hence forth called as PriceNodeH ). Each
PricenodeH contains a low price and a high price.
The next node in the list pertains to a disjoint interval of price in
ascending order. Each Price Range Node has a pointer to an
OrderPriceArray that lists the unique prices of passive orders within
the price range specified. In turn, the OrderPriceArray maintains a
linked list of orders per unique price in time priority (i.e., first-in-first-
out list).
When an active sell order comes, Order Book is searched for buy
order arranged in descending order of price. This is available through
the price range node. Matching will always take place from the head
of the price range list. If no match is found, one will not need to
proceed beyond the head of the list.

Following are the APIS used for accessing the In Memory Order data store

Sr
No API Name Description
1 Trdxmdb -K.eyedPo sition This API is used for position the record in the In Memory Data store based on Security Id, Buy sell, Price and Time.
2 Trdxmdb_KeyedR ead This API is used for reading the record from the In Memory Data store.
3 Trdxmdb_KeyedW rite This API is used for writing the record to the In Memory Data store.
4 Trdxmdb_KeyedD elete This API is used for deleting the record from the In Memory Data store.
5 TrdxmdbKeyedU pdate This API is used for updating the Record to the In Memory Data store.
Means are provided to Create The In Memory Order Data Store
This utility provides a means to create a In Memory Order Data Store identified by a name. Following Arguments are passed for creating the Data Store. Range Of Security The Data Store To Handle

Order Data store Identifier
Maximum Order Capacity Of The Data Store.
Initialize The In Memory Order Data Store: -
This Utility provides a means to initialize the In Memory Order Data store identified by a name.
View The current state of the In Memory Order Data Store
This Utility provided a means to view the current state of the In
Memory Order data store. No of Block Free No Of Orders stored Reference numeral 10 will now be explained with reference to figure
6 which described the Means to Replicate the Transaction on an Online
Basis (Log Reader)
Recovery Setup consists of Active Matching Engine & Passive
Matching Engine.
Active Matching Engine receives the request from the Investor and logs the valid incoming order request to disk using DDS. Different log files are maintained for Order Confirmation and Trade Confirmation messages. When the Matching Engine receives The Order it assigns the Unique Order Seq No, which is unique across all the Orders logged from that Instance. Same manner Matching Engine generates the trades and Assigns the Unique Trade Seq No before logging the trade data to disk.

This Activity Log File is maintained On SAN (Storage Area Network), which is accessed by Passive Matching Engine (standby Matching Engine) running on different M/C.
The Log Reader, which runs on M/C 2, reads the Order Confirmation from Activity Log, which is stored On SAN and shared across different servers and writes the Order Data to Passive Matching Engine. Tapping of Order Confirmation message can be done through tapping of the network or reading of the order confirmation log. Passive Matching Engine does not send the Order and trade confirmations messages over the network. In other words, the passive Matching Engine just builds the state of the order books and the state of the transaction log files. Passive Matching Engine also builds the holding positions.
Master Data
Master Data Contains Security Master File and Investor Master File.
These master Files are used for validating The Input Message (Order
request).
The invention also envisages means for recovery of the matching
engine in case of corruption. This means is illustrated in figure 7 of
the accompanying drawings.
A failure of the matching engine process can result in corruption of the order book and loss of an order being processed. On the other hand, failure of the machine on which matching itself will result in complete loss of the order book and pending orders in the input queue to matching. To reconstruct the order book in real time will be next to

impossible particularly for large stock exchanges. We therefore need a passive Matching Engine that shadows the Active Matching Engine and which can take over in real time in case of failure.
FIGURE 7 depicts the architecture for Matching Engine recovery. In the normal case, the Active Matching Engine sends its order and trade confirmations to a DDS process that synchronously writes the confirmations to a shared SAN (with Passive Matching Engine), and then sends the messages to the Receiver. The Sender & Receiver maintains a forward log of orders sent to Matching and a reverse log of confirmations received. The Log Reader, which runs on Passive Matching Engine Machine, reads the Order Confirmation messages from log file sends it to Passive Matching Engine. It matches the orders and updates the Passive Order books.
In the normal case the Passive Matching Engine only updates the Passive Holdings Table and Passive Order Book. It does not write any confirmations to disk or send any messages to receiver. In this way it maintains its state up to date with the Active Matching Engine up to the order it has last received.
Following are the different components in the FIGURE 7
Sender
Sender is the Process, which receives the Order request packet from investor and sends it to Matching Engine. Sender generates the sequence number for each packet before logging the data to disk and

sends it to Matching Engine through Persistent & Reliable Message
Queue.
Log File Name - Sender Log (Maintains the Seq. Number for Each
Order Request)
Persistent & Reliable Message Queue (TCSMQ)
Message Queues guarantees reliable delivery of the message without any data loss in the packet even if the Matching Server crashes.
Active Matching Engine
Matching Engine receives the Order Request packet and after validating & updating the holding record the order packet is logged to disk with the unique sequence number.
Log File - Order Log File ( Seq Number For Order Messages) Trade Log File ( Seq Number For Trade Messages)
Passive Matching Engine
Log Reader which runs on Passive Matching Engine reads the order
confirmation message from the log file which is stored on SAN. And
sends the order request to Passive Matching Engine builds the state of
the order books and the state of the transaction log files. Also it builds
the holding positions.
Log File - Trade Log File ( Seq Number for Trade Messages)
Receiver
Receiver process reads the Order & Trade confirmation sent by
Matching Engine through Persistent Message Queues. After receiving
the messages it is logged to disk file and message is sent to investor.

When the Active Matching Engine fails / Active Matching Engine Machine Crashes, The Detection Process which runs on the passive Matching Engine detects the failure and starts the recovery on the Passive Matching Engine as follows
Step l:
First step is to stop the sender from sending further order request packets To Matching. So Detection process sends the signal to The sender to stop sending the order packets.
Step 2:
• Get last order confirmation sequence number from order confirmation log on SAN.
• Get the order sequence number of the first packet in the Fwd Queue
• If The seq no of the first packet in the Fwd queue is less by 1 then no packets are lost during failure.
• If there is any packet loss then those packets are read from the queue and send it to the Passive Matching Engine. Which updates the holding record, matches the Orders, updates Order and Trade Logs.
• Then gets the sequence number of last Order packet from the Response Queue.
• If the last packet seq number in Response Queue is lesser than seq number of the last packet in Order Log file then send the lost packet to Response Queue.
Step 3:

• After recovering the Lost Order packets, Trade log is checked to recover Lost trade packets.
• Get the Last Trade packet seq number from Response Queue.
• If the Last Trade Confirmation Seq Number from Response Queue is less than Last Trade Seq Number found in the Trade Log then send the lost packets from Trade Log File.
Step 4:
• Upon Completion of Step 2 & 3, the Passive Matching Engine is ready to take over as active.
• Now Passive Matching Engine Starts Listening On Fwd Queue.
• Passive Matching Engine state is changed from Passive to Active.
• Detection Process again sends the signal to sender to start sending the Order Packets.
UNIQUE FEATURES OF THE INVENTION
A number of stock exchanges use proprietary or third party solutions
for order matching. To the best of the inventors' knowledge the
following features are unique about this invention:
High performance and fault tolerant solution on Unix and Linux
systems, as opposed to the standard solutions available on fault
tolerant machines such as Stratus and Tandem
Order matching at the rate of 50,000+ orders/sec on 2 CPU HP
Titanium with full persistence of orders and trades.
Recovery time of less than 0.5 sec demonstrated on 8 CPU HP
Keystone connected to an XP 1028 SAN

The Engine in accordance with this invention was successfully benchmarked in an integrated end-to-end prototype to process between 13,000 to 19,000 orders per second. In some of the benchmarks, the number of trades was as high as the number of orders. The benchmark also demonstrated application recovery from failure within 0.5 seconds. The benchmark had 34 million investors and 170 million holding positions. The matching engine has also been separately tested and measured to process (on the same hardware) in the range of 25,000 to 50,000 orders per second as a separate component in itself.
While considerable emphasis has been placed herein on the structures and structural interrelationships between the component parts of the preferred embodiments, it will be appreciated that many embodiments can be made and that many changes can be made in the preferred embodiments without departing from the principals of the invention. These and other changes in the preferred embodiment as well as other embodiments of the invention will be apparent to those skilled in the art from the disclosure herein, whereby it is to be distinctly understood that the foregoing descriptive matter is to be interpreted merely as illustrative of the invention and not as a limitation.

We Claim:
[1] An apparatus for Order Matching in matching engines for stock
exchanges, said apparatus consisting of
a)an In-memory Data structure adapted to be used for storing Orders in
predefined index,
b)accessing Means to access the In-Memory Data Structures for updating or
storing the Order Data,
c)Creating Means for Creating an In Memory Order Book,
d)Initializing Means for Initializing the created In Memory Order Book,
e)In memory Data structure adapted to be used for storing Investor holding
data,
f) Creating Means for Creating an Investor Holdings Table.
g)Viewing Means for viewing the current state of the Order Book,
h)Accessing Means to access the in memory Holding Data structures for
storing the Investor Holding data, and
i)Means to write the order and holding data to a persistent data store.
j) means to recover the matching engine in case of failure.
2] An apparatus for Order Matching in matching engines for stock exchanges as claimed in claim 1, in which the means for accessing the In Memory Order Book includes
• Means for Selecting the Orders based on predefined index,
• Means for Updating the Orders,
• Means for Deleting the Orders
• & means for Inserting a Data Record.

3] An apparatus for Order Matching in matching engines for stock exchanges as claimed in claim 1, in which the means for recovery of the matching engine consists of a passive matching engine which shadows the matching engine
4] An apparatus for Order Matching in matching engines for stock exchanges as described herein with reference to the accompanying drawings.
Dated this 16th day of June 2004
Mohan Dewan of R K Dewan & Co Applicants' Patent Attorney