Archive

Archive for June, 2010

Introduction to Esper

June 27, 2010 2 comments

I am planning to introduce Esper with a simple problem and solution.

Introduction

Refer Wikipedia about Event Stream Processing. Esper is java (also in .net) based implementation for processing events using ESP technology. In simple, it helps to find needle in the haystack (of events).

Problem
We need to write a matching-engine (or crossing-engine) for an exchange NTE (hopefully there should not be any exchange with name NTE), for a new country named Indigo. Being it is a new exchange, It could match orders if symbol, quantity, and price exactly matches with other order with opposite trade type(buy vs sell). This exchange will be flooded with Orders every microsecond.

Possible approaches
What are all the option to design this exchange?
1) DB centric approach
2) Distributed cache based solution
3) ESP centric approach
4) …

Let us assume, our exchange deals with only stocks. One possible approach is, we can have single instance of DB. All incoming Orders could be inserted into table. There could be a trigger, which can try to find matching order (buy order with matching sell order) for every new incoming Order. Definitely a single instance of DB can’t handle all the orders. If needed, we could split the number of DB instances, based on products. Each instance of DB can handle some set of related symbols. Doesn’t this seems to be no brainer solution? With lot of hidden complexities. But neither this blog answers a complete solution.

One of the basic issue with DB based solution is, For every incoming Order, entire data has to be accessed. For each Order, it will trigger multiple queries to be executed against DB. Which may not be possible, when 1000’s of Orders are flooding into exchange.

One more option is firing SQL against in-memoy-cache products like MemeCache or Cache Coherence may work. But this blog doesn’t cover such a solution.

Esper way
We are trying to solve the same problem using Esper. Esper not falls under the category of DB, in-memory-cache. It takes completely different approach, it creates state machines. Every object which flows through these Esper engine may affect state machines. Esper generates events whenever such a state machines are affected.

One of the great advantage with Esper is, It doesn’t require to keep all the objects in memory, whereas it may consume more CPU processing power, but I don’t have any statistics to prove it, it is just my wild guess. In simple, instead of storing the data and execute the query repeatedly, Esper allows to store the query, and to fire the data against those queries. Whenever query matches given criteria (one or more object may satisfy this criteria), listener (Similar to event listeners) will get callback notification with matching data. Kindly excuse me, because I keep interchanging data, object, event. Events are immutable data, which could be Java bean (POJO), Xml, Hashmap.

State machine could be created using SQL like language called EQL, (Event Query Language). There are multiple products these days uses the terminology named EQL. But as per my knowledge there are no standards available. Everyone calls their ESP engine’s DSL as EQL.

Esper is available in open source, with commercial support, as part of other known products like BEA Event Server, MarketCetera product. And investment bank’s like Bank of America are using them.

Solution
Let me introduce Order. Order is generally placed by buyer/seller. Order is represented using java bean. It contains symbol, price, type of the trade (Buy or Sell).

package com.indigo.nte.order;

import org.apache.commons.lang.builder.ToStringBuilder;

public class Order {
	private int orderId;
	private String symbol;
	private double price;
	private boolean sell;
	private int quantity;

	protected Order() {
	}

	public boolean isBuy() {
		return !isSell();
	}

	public boolean isSell() {
		return sell;
	}

	public void setSell(boolean sell) {
		this.sell = sell;
	}

	public String getSymbol() {
		return symbol;
	}

	public void setSymbol(String symbol) {
		this.symbol = symbol;
	}

	public double getPrice() {
		return price;
	}

	public void setPrice(double price) {
		this.price = price;
	}

	public int getQuantity() {
		return quantity;
	}

	public void setQuantity(int quantity) {
		this.quantity = quantity;
	}

	public int getOrderId() {
		return orderId;
	}

	public void setOrderId(int orderId) {
		this.orderId = orderId;
	}

	public String toString() {
		return ToStringBuilder.reflectionToString(this);
	}
}

Order generator, This class creates a new Order object when getNext() is invoked, It randomly chooses a symbol and price using another class called MultiStockHint. There is an annotation named Hint, provided by Esper framework, but this StockHint is not related to Esper Hint class. It is utility to create random Order object.

public class OrderGenerator {
	......... //other attributes and methods are missing.
	public Order getNext() {
		StockHint hint = MultiStockHint.values()[random.nextInt(MultiStockHint.values().length)];
		Order ord = new Order();
		ord.setSell(random.nextBoolean());
		ord.setSymbol(hint.getSymbol());
		ord.setPrice(Math.floor(getPrice(hint)) );
		ord.setQuantity(random.nextInt(25)+1);
		ord.setOrderId(counter.incrementAndGet());
		return ord;
	}
}

Here comes the important Esper framework related code. MightyEsper is a class which matches two Order using the EQL. You can assume like as if it represents NTE exchange.

"select a.orderId, a.symbol, a.quantity, a.price, a.sell, b.orderId, b.symbol, b.quantity, b.price, b.sell  from ClientOrder.win:time(1800) as a, ClientOrder.win:time(1800) as b where a.symbol = b.symbol and a.price=b.price and a.quantity = b.quantity and a.sell != b.sell"

The above code should be familiar because it resembles like SQL, but only difference is ClientOrder.win:time(1800). BeanName:win:time(timespec) will fetch all the beans in the specified window of time. Here I use 1800 milliseconds. We could have also chosen BeanName:win:time_batch(timespec). Refer the Esper documentation for the differences.

To configure our Order bean as event, we are creating Configuration object and using that config object, an instance of Esper engine is created. We have also created statement object from Esper engine. Statement object has API to register listeners, Listeners gets the notification whenever a pattern or EQL matches for one or more event. In this case, Statement represents EQL to match two different object with opposite trade types. Here UpdateListener will get the notification, prints those matching orders.

package com.indigo.nte.esper;

import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

import com.espertech.esper.client.Configuration;
import com.espertech.esper.client.EPServiceProvider;
import com.espertech.esper.client.EPServiceProviderManager;
import com.espertech.esper.client.EPStatement;
import com.espertech.esper.client.EventBean;
import com.espertech.esper.client.UpdateListener;
import com.indigo.nte.order.Order;

public class MightyEsper {

	private static MightyEsper instance = new MightyEsper();
	private final EPServiceProvider esperEngine;

	private MightyEsper() {
		Configuration config = new Configuration();
		config.addEventType("ClientOrder", com.indigo.nte.order.Order.class);
		esperEngine = EPServiceProviderManager.getDefaultProvider(config);
		addOrderQtyMatching();
	}

	private void addOrderQtyMatching() {
		String stmt = null;
		stmt = "select a.orderId, a.symbol, a.quantity, a.price, a.sell, b.orderId, b.symbol, b.quantity, b.price, b.sell  from ClientOrder.win:time(1800) as a, ClientOrder.win:time(1800) as b "
				+ " where a.symbol = b.symbol and " + "a.price=b.price and a.quantity = b.quantity " + "and a.sell != b.sell";
		EPStatement statement = esperEngine.getEPAdministrator().createEPL(stmt);
		statement.addListener(new UpdateListener() {

			@Override
			public void update(EventBean[] newEvents, EventBean[] arg1) {
				Map bean1 = (Map) newEvents[0].getUnderlying();
				Map bean2 = (Map) newEvents[1].getUnderlying();
				printMapBean(bean1);
				printMapBean(bean2);
			}

			private void printMapBean(Map bean) {
				Set<Map.Entry> keyValue = bean.entrySet();
				for (Entry property : keyValue) {
					System.out.printf("\t" + property.getKey() + "  :  " + property.getValue() + "\t");
				}
				System.out.println("\n");
			}
		});

	}

	public static MightyEsper getInstance() {
		return instance;
	}

	public void placeOrder(Order order) {
		esperEngine.getEPRuntime().sendEvent(order);
	}

	public void registerTradeListener() {

	}
}

Below is the client code, which places the order in Esper engine. Now if we decorate the MightyEsper with other class named Exchange, then it would be meaningful and hides the complexities of internal implementation.

package com.indigo.nte.exchange;

import com.indigo.nte.esper.MightyEsper;
import com.indigo.nte.order.Order;

public class Exchange {
	private final static Exchange instance = new Exchange();
	private final MightyEsper esper = MightyEsper.getInstance();

	public static Exchange getInstance() {
		return instance;
	}

	public void placeOrder(Order order) {
		esper.placeOrder(order);
	}

}

Below is the client code, which is sending Order. Matching Orders are printed in console.

package com.indigo.nte.client;

import com.indigo.nte.esper.MightyEsper;
import com.indigo.nte.order.Order;
import com.indigo.nte.order.OrderGenerator;

package com.indigo.nte.client;

import com.indigo.nte.order.Order;
import com.indigo.nte.order.OrderGenerator;
import com.indigo.nte.exchange.Exchange;

public class Client {
	public static void main(String... args) {
		OrderGenerator generator = OrderGenerator.getInstance();
		Exchange exchange = Exchange.getInstance();
		while (true) {
			Order ord = generator.getNext();
			System.out.println(ord.toString());
			exchange.placeOrder(ord);
		}
	}
}

Esper provides so many features, it is possible to implement a full-fledged crossing engine. But this blog attempts only basic crossing feature. Developing a complete crossing engine for known exchanges like Globex would be interesting excercise.

Below is the output of execution of the program. I have skipped few rows to make it more readable.

com.indigo.nte.order.Order@13136e5[orderId=1,symbol=DELL,price=17.0,sell=true,quantity=7]
com.indigo.nte.order.Order@a69b6b[orderId=2,symbol=MSFT,price=23.0,sell=true,quantity=4]
com.indigo.nte.order.Order@13515e[orderId=3,symbol=MSFT,price=24.0,sell=true,quantity=19]
com.indigo.nte.order.Order@273f4e[orderId=4,symbol=MSFT,price=23.0,sell=false,quantity=13]
com.indigo.nte.order.Order@1aacc14[orderId=5,symbol=DELL,price=12.0,sell=true,quantity=10]
com.indigo.nte.order.Order@17d7c7f[orderId=6,symbol=MSFT,price=21.0,sell=true,quantity=21]
com.indigo.nte.order.Order@53d3cf[orderId=7,symbol=MSFT,price=24.0,sell=false,quantity=3]
com.indigo.nte.order.Order@ee21f5[orderId=8,symbol=DELL,price=11.0,sell=false,quantity=16]
com.indigo.nte.order.Order@6014f7[orderId=9,symbol=DELL,price=11.0,sell=false,quantity=9]
com.indigo.nte.order.Order@1abbec4[orderId=10,symbol=MSFT,price=25.0,sell=false,quantity=6]
com.indigo.nte.order.Order@2c03ff[orderId=11,symbol=GOOG,price=595.0,sell=true,quantity=9]
………….
com.indigo.nte.order.Order@1f7abae[orderId=84,symbol=MSFT,price=24.0,sell=false,quantity=10]
com.indigo.nte.order.Order@8d2280[orderId=85,symbol=DELL,price=10.0,sell=true,quantity=22]
com.indigo.nte.order.Order@a51027[orderId=86,symbol=MSFT,price=27.0,sell=false,quantity=10]
com.indigo.nte.order.Order@790192[orderId=87,symbol=IBM,price=105.0,sell=false,quantity=8]
com.indigo.nte.order.Order@381a9c[orderId=88,symbol=MSFT,price=24.0,sell=true,quantity=19]
com.indigo.nte.order.Order@1a5e65f[orderId=89,symbol=DELL,price=19.0,sell=true,quantity=18]
com.indigo.nte.order.Order@11adeb7[orderId=90,symbol=MSFT,price=22.0,sell=true,quantity=20]
com.indigo.nte.order.Order@22e177[orderId=91,symbol=MSFT,price=20.0,sell=false,quantity=13]
com.indigo.nte.order.Order@842e74[orderId=92,symbol=IBM,price=106.0,sell=false,quantity=3]
com.indigo.nte.order.Order@41f227[orderId=93,symbol=IBM,price=129.0,sell=true,quantity=18]
com.indigo.nte.order.Order@5d3ac0[orderId=94,symbol=GOOG,price=589.0,sell=false,quantity=15]
com.indigo.nte.order.Order@1d978ea[orderId=95,symbol=IBM,price=100.0,sell=true,quantity=15]
com.indigo.nte.order.Order@2f4813[orderId=96,symbol=MSFT,price=25.0,sell=false,quantity=16]
com.indigo.nte.order.Order@1bef987[orderId=97,symbol=AAPL,price=176.0,sell=false,quantity=7]
com.indigo.nte.order.Order@152643[orderId=98,symbol=IBM,price=126.0,sell=false,quantity=16]
com.indigo.nte.order.Order@11ee017[orderId=99,symbol=DELL,price=11.0,sell=true,quantity=23]
com.indigo.nte.order.Order@15d45d9[orderId=100,symbol=MSFT,price=20.0,sell=true,quantity=13]

a.quantity : 13 a.orderId : 100 a.sell : true b.sell : false b.quantity : 13 b.orderId : 91 b.price : 20.0 b.symbol : MSFT a.price : 20.0 a.symbol : MSFT

It immediately reports the matching order when it encounters. Doesn’t it amazing? Hats off to Esper team.

Advertisements
Categories: Uncategorized