Implementing matching engine correctly can be tricky when you consider variety of order types offered by real exchanges. In addition to core limit and market orders exchanges offer additional execution strategies: market-to-limit, various types of pegged orders, stop orders, and others. Matching different order types is non-trivial, and there are many edge cases. In addition there are different rules for matching orders when session opens (i.e. auction mode) vs. continuous trading.

The resulting complexity strongly suggests a test driven approach for developing correctly working engine. In the following series of posts I’m going to gradually build a prototype of a functionally rich equity matching engine. To make things interesting I’m going to model the functionality based on a real, publicly available specs from Euronext: https://europeanequities.nyx.com/trading/order-types

The complete source code for every posts in the series is available in my GitHub repo: https://github.com/prystupa/scala-cucumber-matching-engine

The foundation – limit order book

Implementing a matching engine inevitably requires maintaining buy and sell order books. In this first post I am going to test drive the implementation of a simple limit order book using Scala and Cucumber.

First lets start defining the domain model. All orders are created by brokers, are either to sell or to buy a given instrument, and have a known size and quantity. Limit orders, in addition, define a limit price, and will not execute if market conditions are inferior to the limit price:


Read More

One of my colleges (http://weblogs.asp.net/sweinstein/) brought up an interesting problem: there is a common theme in finance applications to subscribe to a market data source to receive real time updates on the instruments that this source covers. A late subscriber (the one that has not been subscribed since the start of the trading day, for example) usually expects to receive a snapshot per instrument before real time updates. So what is the best way to support snapshot guarantee, per instrument, from a “hot” underlying source using Rx? There are multiple ways to do it, of course, and here is my version of it:

public static IObservable<T> WithCachedSnapshot<T, TKey>(
    this IObservable<T> source,
    Func<T, TKey> keySelector)
{
    var cache = new Dictionary<TKey, T>();
    return Observable.Defer(() => {
            lock (cache)
                return cache.Values.ToList().ToObservable();
        })
        .Concat(source.Do(s => {
            lock (cache) cache[keySelector(s)] = s;
        }));
}

If you can’t take my word for it, here is the proof that it works:

[TestMethod()]
public void CacheByKeyTestHelper()
{
    // Arrange
    TestScheduler scheduler = new TestScheduler();
    var source = scheduler.CreateHotObservable(
        OnNext(100, new { Ticker = "MSFT", Price = 30.5 }),
        OnNext(101, new { Ticker = "IBM", Price = 130.2 }),
        OnNext(102, new { Ticker = "MSFT", Price = 31.5 }),
        OnNext(103, new { Ticker = "IBM", Price = 130.1 }),
        OnNext(104, new { Ticker = "AAPL", Price = 150.5 }));

    // Act
    var target = RxExtensions.WithCachedSnapshot(
        source,
        quote => quote.Ticker);
    var results = scheduler.Run(() => target, 0, 0, 105);
    var cachedResults = scheduler.Run(() => target, 0, 0, 200);

    // Assert
    results.AssertEqual(
        OnNext(100, new { Ticker = "MSFT", Price = 30.5 }),
        OnNext(101, new { Ticker = "IBM", Price = 130.2 }),
        OnNext(102, new { Ticker = "MSFT", Price = 31.5 }),
        OnNext(103, new { Ticker = "IBM", Price = 130.1 }),
        OnNext(104, new { Ticker = "AAPL", Price = 150.5 }));

    cachedResults.AssertEqual(
        OnNext(105, new { Ticker = "MSFT", Price = 31.5 }),
        OnNext(105, new { Ticker = "IBM", Price = 130.1 }),
        OnNext(105, new { Ticker = "AAPL", Price = 150.5 }));
}

private Recorded<Notification<T>> OnNext<T>(
    long ticks, T value)
{
    return new Recorded<Notification<T>>(
        ticks,
        new Notification<T>.OnNext(value));
}

This article shows some improvements to the original code presented in my previous post. Improvements are based on the feedback I received from Erik Meijer and his team and mainly focus on some built-in opportunities in Rx framework that I missed. Here is an extract from the original implementation of the running low feed:

// Daily low price feed
double min = double.MaxValue;
var feedLo = feed
    .Where(p => p < min)
    .Do(p => min = Math.Min(min, p))
    .Select(p => "New LO: " + p);

This implementation depends on the external (to the framework) state (current low value stored in “min” local variable), “Do” combinator to continuously update this state with every price tick, and a “Where” combinator to suppress the ticks that do not represent running low value. Turns out, there is a better, more elegant and framework friendly way to implement this. It relies on the built-in “Scan” and “HoldUntilChanged” combinators:

// Daily low price feed
var feedLo = feed
    .Scan(Math.Min)
    .HoldUntilChanged()
    .Select(p => "New LO: " + p);

The code above is functionally equivalent to the original one but is cleaner, more compact, and easier to read. This is how it works:

  • “Scan” operator is used to accumulate the running min value. “Scan” is similar to “Aggregate” in the LINQ-to-Objects world but, instead of collapsing the sequence to a single accumulated value, it keeps outputting the current accumulated value with every tick. As a result “Math.Min” function is continuously applied with every new tick with accumulated min value and new price as arguments and its result is “ticked out”. This produces a stream where every successive number is either less than or equal to the previous one. Close to what we need except we want to suppress duplicates.
  • “HoldUntilChanged” is another built-in combinator that wraps an underlying stream and only repeats a value from it if this value differs from the previous one. Perfect for removing successive duplicates (please, note, it will NOT remove ALL the duplicates, only successive ones, so it is not a proper substitute to Distinct, when such a combinator exists) . We use “HoldUntilChanged” instead of original “Where” clause.

Read More

Reactive Framework Labs

This article is one from the “Processing Financial Data with Microsoft Reactive Framework (Reactive Extensions for .NET)” series of articles that demonstrate some basic applications of Rx framework to financial data. This article shows how to calculate a running VWAP (volume weighted average price over a defined window of time). Other articles in the series are:

Visual Studio 2008 solution containing full source code for all examples can be downloaded here.

Calculating VWAP/Sliding Window Implementation

We will use this simple “Trade” type to represent a trade event. To simplify things we will only consider Price and Volume:

class Trade
{
    public double Price { get; set; }
    public int Volume { get; set; }
}

The following “TradeWithVWAP” type wraps underlying trade and attaches running VWAP value to it. It is used for calculation output:

class TradeWithVWAP
{
    public Trade Trade { get; set; }
    public double VWAP { get; set; }
}

Our main module starts with a simple market data generator that produces infinite stream of random prices ($30 to $33 range) at random volumes (1,000 to 100,000 shares) at a random frequency (0 to 3 seconds between trades). BuildVwapFeed functions takes generated trade stream and converts it to another stream with running VWAP attached to every trade. And finally we simply subscribe to VWAP-wrapped feed and output the results.

Read More

Reactive Framework Labs

This article is one from the “Processing Financial Data with Microsoft Reactive Framework (Reactive Extensions for .NET)” series of articles that demonstrate some basic applications of Rx framework to financial data streams. This article demonstrates automatic and transparent failover from primary data feed to a backup one implemented in terms of Microsoft Reactive Framework. Other articles in the series are:

Visual Studio 2008 solution containing full source code for all examples in this article can be downloaded here.

Failover Implementation

The effect of automatic failover is implemented using the “Catch” operator built into the Rx framework.  The “Catch” operator simply repeats the first stream until it fails. When the first stream fails, exception is swallowed and the second stream is subscribed to and repeated. You can chain any number of streams this way. Here is a code sample that uses “Catch” to switch from some primary feed to a backup:

Read More

Reactive Framework Labs

This article is one from the “Processing Financial Data with Microsoft Reactive Framework (Reactive Extensions for .NET)” series of articles that demonstrate some basic applications of Rx framework to financial data. This article shows how to throttle your incoming feed to a desired frequency. Other articles in the series are:

Visual Studio 2008 solution containing full source code for all examples can be downloaded here.

Throttling Implementation

The key operator here is “Sample”. Sampling at a desired rate effectively returns your a throttled stream. My intuition was that if underlying feed does not produce a value during the sampling interval, “Sample” will repeat the most recent available value when sampling is due. But it doesn’t and this makes it a perfect fit for throttling. Note that there is also an operator called “Throttle” but its name is misleading and its behavior most likely will not match your definition of throttling. The way implemented it will not emit any values at all if underlying feed produces faster than throttling interval, so it looks more like “Choke” to me.

Read More

Reactive Framework Labs

This article is one from the “Processing Financial Data with Microsoft Reactive Framework (Reactive Extensions for .NET)” series of articles that demonstrate some basic applications of Rx framework to financial data. This article focuses on detecting running high/low values (like daily max and min) from a market data feed. Other articles in the series are:

Visual Studio 2008 solution containing full source code for all examples can be downloaded here.

Detecting Running High/Low Prices

The key operators in this implementation are “Do” and “Where”, both built into the Reactive Framework. The first one is used to produce side effect of recording the running High or Low value, and the second is used to filter incoming values that do not produce newest High or Low:

Read More