FORM-2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2006
PROVISIONAL SPECIFICATION
(See section 10; rule 13)


A MESSAGING SYSTEM
TATA CONSULTANCY SERVICES LTD.
an Indian Company of Nirmal Building, 9th floor, Nariman Point, Mumbai 400 021,
Maharashtra, India

THE FOLLOWING SPECIFICATION DESCRIBES THE INVENTION


FIELD OF THE INVENTION
The present invention relates to the field of communication.
Particularly, the present invention relates to the field of communication between two or more distributed computers.
BACKGROUND OF THE INVENTION AND PRIOR ART
A messaging system forms the backbone of any application. It enables communication between various components of an application. The messaging system uses inter process communication (IPC) mechanisms to pass messages between processes. These messages contain data to be exchanged between the processes thus speeding up computational processing.
The inter process communication mechanisms along with data sharing also enable synchronization of data to ensure that no deadlock situation exists as multiple processes share a common resource. The IPC mechanisms are divided into methods for message passing, synchronization, shared memory, and remote procedure calls (RPC). Typically, these mechanisms work on either shared memory systems or distributed systems. In shared memory the processes communicate with each other using a common shared pool of memory, whereas in distributed design each process has its own memory.
With the advent of internet and technology more and more people are using the internet to trade and also purchase products online. The orders/requests placed by customers have increased from a million to a billion.
2
1 3 APR 2009

Thus, with the increase in the trading volumes and also the competition, the trading firms need to look for reliable, fast and efficient system to cater to their client needs and in turn increase customer satisfaction.
The financial institutions face challenges including reducing the response time to a request (latency) placed by a customer and decreasing the time taken to complete the request (throughput).
Thus, financial systems including trading and investments firms are trying to achieve high throughput with ultra-low latency in order processing. Latency is the time elapsed starting from the entry of order request in the trading application till the order is confirmed by the application. Latencies lower than a millisecond can offer a competitive advantage for financial institution. "A one millisecond advantage in trading applications can be worth $100 million a year" says information week in their article titled "Business at light speed".
Low Latency messaging is a challenging prospect as none of available operating system IPC (Inter process communication) mechanisms are capable of delivering a large message throughput with low latencies. In the commercial space there are messaging frameworks by 29 West and IBM. In the open source space there is OMQ.
In most cases it is seen that an increase in throughput is also accompanied by an increase in the latency. This is due to the use of locks and semaphores to ensure that only one process has access to the queue structures at any instance of time. Though this is an important requirement of traditional
3

shared memory designs it limits the speed with which a message is handed off from one process to another.
Therefore, there is a need for a robust messaging system which is capable of processing more than 1 millions messages per second and having message hand off latencies which are less than 10 micro-seconds.
OBJECTS OF THE INVENTION
It is an object of the present invention to improve the throughput of any trading and/or financial systems.
It is another object of the present invention to decrease the latency of trading and/or financial system to less than 500 microseconds.
It is still another object of the present invention to provide an efficient messaging system for reducing the computational time.
It is yet another object of the present invention to provide a cost effective messaging system.
SUMMARY OF THE INVENTION
The present invention envisages a high throughput and low latency messaging system for a trading and/or financial system.
Particularly, the messaging system envisaged by the present invention implements efficient inter-process communication between processes of the
4

same server (local messaging) as well as processes on different servers (remote messaging).
According to an embodiment of the present invention, the publish/subscribe model of communication has been implemented for providing efficient inter¬process communication.
According to a preferred embodiment of the present invention, the messaging system uses message queue data structure that has been implemented in a file. For speed of access, this file is mapped into the memory space of the process using the message queue.
Specifically, the messages in the queue are stored in the form of a circularly linked list. Every message buffer has a pointer to the next message buffer in the list.
According to another preferred embodiment of the present invention, lockless method of messaging has been provided where in local messaging, multiple readers read the same message without making message copies and in remote messaging additional sender and receiver processes are created which are responsible for remote communication. The sender and receiver processes use the local message queues for communication to the writer and reader processes respectively.
BRIEF DESCRIPTION OF ACCOMPANYING DRAWING
The invention will now be described in relation to the accompanying drawing in which,
5

Figure 1 illustrates a schematic of the remote messaging system.
DESCRIPTION OF THE INVENTION
The invention will now be described with reference to the accompanying drawing which does not limit the scope and ambit of the invention. The description provided is purely by way of example and illustration.
According to the preferred embodiment of the present invention there is provided a messaging system for increasing the performance of a financial application with lower latency.
The present invention uses message queue data structures, which are implemented in a file. All the data structures and message buffers are located at a specific offset from the beginning of the file. For speed of access, this file is mapped into the memory space of the process using the message queue. It is also pinned to the physical memory using operating system primitives. We will now refer to this file as memory mapped file for the rest of the specification.
The messages in the queue are stored in the form of a circularly linked list. Every message buffer has a pointer to the next message buffer in the list. There also exists a data anchor pointer that points to the next element in the queue to be read from the list. After the reader process reads from this location the data anchor pointer advances to the next message buffer.
The free end pointer points to the free message buffer into which the next message can be written. The writer process refers to this pointer to copy the
6

incoming message. After the new message is copied the free end pointer advances to point to the next message buffer.
The present invention implements the message queuing in various modes namely point to point messaging, messaging for Publish/Subscribe model of communication and remote messaging.
Point to Point Messaging
To achieve as low latencies as possible, it is best to avoid locking and semaphores. This is possible if there are no race conditions. Having no race conditions implies that one process will update only one variable. In the message queuing case, it means that the writer and the reader process update only one variable. They can however read the variables updated by other processes.
Applying this principle to our memory mapped file, we apply the following constraints:
• Only the writer process can update the free end pointer.
• Only the reader process can update the data anchor pointer.
The method for queuing of a message into the message queue in local messaging includes:
1. Checking if the queue is full;
2. checking if the free end pointer points to the data anchor pointer after the message has been copied;
7

3. waiting till the above condition does not hold (This happens when the reader reads the first message from the message buffer, pointed to by the data anchor pointer);
4. copying the message into the message buffer pointed to by the free end pointer; and
5. updating the free end pointer to point to the next message buffer.
Below listed are the steps to be followed when the reader reads a message from the queue:
1. Checking if there is any data in the queue. If the free end pointer points to the data anchor pointer then the queue is empty. Wait till this condition is false. (This can happen only when the writer writes the next incoming message into the message buffer, pointed to by the free end pointer);
2. reading the message from the message buffer pointed to by the data anchor; and
3. Updating the data anchor to point to the next message buffer.
It is important to note that for the above lockless mode of message handoff to work it is essential that the order of instructions are not altered for any kind of optimization by the compiler, processor, chipset or memory controller. On the compiler we can use compiler switches to ensure that instructions are generated in the correct order. A test was run continuously for more than 2 days to ensure that this condition is not invalidated. In this test the writer and reader processes ran concurrently, with the writer inserting messages to the queue and the read reading messages off the queue.
8

The compiler during optimization causes the data anchor pointer and free end pointer into register variables. Hence these variables are declared as volatile variables which instruct the compiler to force reading the latest values of these variables in memory. The pointers to message buffers are declared as pointers to volatile data.
Publish Subscribe Messaging
In the 'publish-subscribe' model of messaging there are multiple readers reading the same message. One way to implement this will be to use as many memory mapped files as there are readers with the writer process copying the incoming message into all the files. This solution is not scalable as the number of readers increase and hence will result in low throughput and high memory utilization.
Another alternative is to extend the lockless message handoff mechanism discussed above to accommodate multiple readers, without having to make message copies. In such a case a message is considered read (or de-queued) if only all the readers have read the message.
This can be achieved by having every reader (or subscriber) having its own data anchor pointer. In addition the writer process will now have to check the data anchor pointers of all reader processes to ensure that the queue is not full. This is essential because of the change in the definition of a de¬queued message.
The method for message insertion in a 'publish-subscribe1 queue includes:
9

1. Checking if the queue is full. Checking if the free end pointer points to the data anchor pointer of any of the reader processes after the message has been copied. If so, then wait till this condition does not hold. (This happens when the slowest reader reads the first message from the message buffer, pointed to by it's data anchor pointer);
2. copying the message into the message buffer pointed to by the free end; and
3. updating the free end pointer to point to the next message buffer.
The method for de-queuing a message by the reader process remains the same. The only difference to note here is that every reader process has its own data anchor pointer.
Remote Messaging
The above description demonstrated local messaging, in which the reader and the writer processes run on the same server, communicating via the memory mapped file. Also, an important requirement is remote messaging in which both the processes run on different servers.
This requirement has been implemented using additional sender and receiver processes which are responsible for remote commuiiication. These processes use the local message queues for communication to the writer and reader processes respectively. The transport mechanism for remote communication is chosen to be TCP/IP. The latency using TCP/IP in a high speed network has been found to be less than 100 micro seconds. This has been adequate to implement high end trading systems with an end to ^nd latency of less than 1 milli second.
10

Referring to Figure 1, numerals 10 and 18 represent the two servers, served and server2 respectively. Served 10 is the writer and Server2 18 is the
reader.
The path taken by a message from the reader process 18 to the writer process 10 is as follows:
1. The writer represented by numeral 12 inserts the message in the local shared memory message queue represented by numeral 14, which is lockless implementation using the memory mapped file.
2. The sender represented by block 16 running on the same machine 10 as the writer dequeues the message from the message queue and sends it to the receiver represented by block 24 running on the remote server 18.
3. The receiver 24 running in the remote machine 18 receives the message and inserts the message in the remote shared memory message queue represented by numeral 22.
4. The reader represented by numeral 20 dequeues the message from the message queue 22.
Thus, following the above steps a low latency message queuing systems for enterprise applications can be achieved. One of the major uses of this messaging system is in building financial applications which require processing of hundreds of orders per second with the end to end latencies in sub-milliseconds. The messaging system envisaged by the present invention is capable of delivering messages with very low latencies primarily because of the lock less design.
11

TEST RESULTS:
The messaging system uses the lockless producer consumer method for achieving low latencies.
The point to point messaging throughput achieved using this invention is as high as 2.7 million messages per second with less than 10 micro-second latency where each message was of 512 bytes.
For Publish Subscribe throughput degrades gracefully to as much as 5.8 million messages per second across 11 subscribers with a message size of 512 bytes.
For remote messaging the present invention has been tested to deliver a messaging rate of 208000 messages/second with less than 100 microseconds of one-way latency between to Intel Clovertown systems over a 1 Gbps local area network with a message size of 512 bytes. On a 10 Gbps network between two Intel Nehalem servers the present invention has achieved more than 2 million messages/second of throughput.
The technical advances of the present invention include:
* Providing a messaging system with inter-process communication latencies less than 10 microseconds on the sane server, along with the messaging throughput exceeding 2 million messages per second;
* Providing a messaging system that can achieve an inter-process communication latency (one-way) of less than 100 microseconds across remote servers, along with the messaging throughput exceeding 2 million messages per second;
12

• Providing a messaging system that can achieve an inter-process communication throughput of more than 5 million messages per second across all readers with more than 10 reader processes (subscribers) reading the same (publisher) process.
13
13 APR 2009
While considerable emphasis has been placed herein on the particular features of this invention, it will be appreciated that various modifications can be made, and that many changes can be made in the preferred embodiments without departing from the principles of the invention. These and other modifications in the nature of the invention or the preferred embodiments 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.