crypto-toolbox / hft-orderbook Goto Github PK

I have hooked up the book to a level2 websocket stream from GDAX. Processing the initial snapshot works just as expected, but once I hit live orders, I always get the following error after a varying number of trades:
File "/home/joel/work/python/lob.py", line 144, in process self.add(order) File "/home/joel/work/python/lob.py", line 218, in add self.asks.insert(limit_level) File "/home/joel/work/python/lob.py", line 522, in insert current_node.right_child.balance_grandpa() File "/home/joel/work/python/lob.py", line 394, in balance_grandpa raise NotImplementedError

My orders are in the following format:
('dd57b02494f0d971ba04b81e0eaa8e3d79e2818c1d76a52d5374be357560f310', False, 9252.64, 0.00113473, 1524558443.6000874)
I am hashing the price as a string with sha256 in order to get a uid for the trade. I am running two processes, and the orderbook gets orders from a queue. So far, debugging has not shown any errors on my side, and I just want to make sure I am not missing something.

My code can be found here: https://gist.github.com/Huhnmonster/192d1ea6236e0be46be15f3e2dc50a71

It looks like a typo in lob.py (436:447).

    if self.balance_factor > 1:
        # right is heavier
        if self.right_child.balance < 0:
            # right_child.left is heavier, RL case
            self._rl_case()
        elif self.right_child.balance > 0:
            # right_child.right is heavier, RR case
            self._rr_case()
    elif self.balance_factor < -1:
        # left is heavier
        if self.left_child.balance < 0:
            # left_child.left is heavier, LL case
            self._ll_case()
        elif self.left_child.balance > 0:
            # left_child.right is heavier, LR case
            self._lr_case()

Should be changed to

    if self.balance_factor > 1:
        # right is heavier
        if self.right_child.balance_factor < 0:
            # right_child.left is heavier, RL case
            self._rl_case()
        elif self.right_child.balance_factor > 0:
            # right_child.right is heavier, RR case
            self._rr_case()
    elif self.balance_factor < -1:
        # left is heavier
        if self.left_child.balance_factor < 0:
            # left_child.left is heavier, LL case
            self._ll_case()
        elif self.left_child.balance_factor > 0:
            # left_child.right is heavier, LR case
            self._lr_case()

Because there is no such property "balance", but only "balance_factor"

If an Order is removed via pop(), if the pop operation would result in an empty OrderList for the Order's parent LimitLevel, that LimitLevel is not removed.

Let's consider the following book:

import lob as LOB
lob = LOB.LimitOrderBook()
orders = [
    LOB.Order(uid=1, is_bid=True, size=5, price=100),
    LOB.Order(uid=2, is_bid=True, size=5, price=95),
    LOB.Order(uid=3, is_bid=True, size=5, price=90),
    LOB.Order(uid=4, is_bid=False, size=5, price=200),
    LOB.Order(uid=5, is_bid=False, size=5, price=205),
    LOB.Order(uid=6, is_bid=False, size=5, price=210),
    ]
for order in orders:
     lob.process(order)

I'm looking at the limit level dictionary:
lob._price_levels
Since no limit level is aware of whether it is a bid or an ask level, it looks like determining this means querying:
lob._price_levels[100].orders.head.is_bid
(for an order book containing a price level of 100)

And therefore the obvious way to separate out bids and asks is:

bids = []
asks = []
for k, level in lob._price_levels.items():
    if level.orders.head.is_bid:
        bids.append(level)
    else:
        asks.append(level)

Now, since the query function should also be O(1), I would like to avoid iterating through every price level in the book where this is not necessary -- a book may have 10000 levels but only the first 20 may be relevant.

One way to do this would be:

levels_sorted = sorted(lob._price_levels.keys())
indices = {}
indices['bid'] = list(reversed(range(0, levels_sorted.index(lob.best_bid.price) + 1)))
indices['ask'] = list(range(levels_sorted.index(lob.best_ask.price), len(levels_sorted)))

def top_N_levels(n):
    levels = {}
    for side in ['bid', 'ask']:
        levels[side] = []
        for x in range(n):
            index = indices[side][x]
            level_price = levels_sorted[index]
            level = lob._price_levels[level_price]
            levels[side].append(level)
    return levels

top_N_levels(2)

It seems like there must be a better way of doing it...

Another option would involve starting at the top of the lob.bids or lob.asks price level tree, and iterate down it only as far as necessary.

Unfortunately, we are dealing with a binary tree, so trying to find the "next lowest" or "next highest" price might mean going all the way down to a leaf node... hardly efficient either...

We currently only provide the basic structs to build an HFT book. The following functions should be added to ease usage of this lib:

• Book struct and typedef, managing bids and asks, as well as limit and order_id maps.
• addOrderToBook Function
• removeOrderFromBook Function
• replaceOrderInBook Function
• Tests for these methods and structs in the CuTest test suite.

Hi:
Below test function is not getting run
void RunAllTests(void){

CuString *output = CuStringNew();
CuSuite* suite = CuSuiteNew();

CuSuiteAddSuite(suite, HFTLobGetSuite());
 CuSuiteRun(suite);
CuSuiteSummary(suite, output);
CuSuiteDetails(suite, output);
printf("%s\n", output->buffer);

}

Actually program getting stoped by this CuSuiteRun(suite) line . Any help on this?

Thanks

I'm attempting to simulate an exchange using this order book implementation, but I'm a bit confused about the matching algorithm and how to keep track of filled orders.

So I have the basic testcase:

from HFT_Orderbook.lob import LimitOrderBook, Order
lob = LimitOrderBook()
bid_order = Order(uid=1, is_bid=True, size=5, price=100)
ask_order = Order(uid=2, is_bid=False, size=5, price=200)
lob.process(bid_order)
lob.process(ask_order)
ask_order_2 = Order(uid=3, is_bid=False, size=5, price=100)
lob.process(ask_order_2)

In this situation, I would expect the bid to be cleared by ask_order_2, but if I query the LOB I get that the best bid is 10@100, which doesn't seem to make sense. However, if I decrease this price of my ask to 90, it clears the bid as you can see by querying lob.levels().

Is there something I'm misunderstanding about how matching works?

Next, I also need to be able to keep tracking of which orders were filled, at what price, and what UID. Is there any easy way to do this, or would I have to diff the order book to do this?

Thank you!

Check doc strings and comments for offenses of the grammatical variety, as well as spelling errors.

The documentation is currently a little thin.

From the tests I see how to add and remove orders.

And I see there is a top_level() function to get the best bid/ask.

But if all I needed was the best bid/ask then I would just use a ticker :)

How do I query the book to find the market depth, for example? Is there any way to return a list of bids and asks (price/size)?

Implement tests for C and Python code base.

C Tests

• TestCreateDummyTree
• TestOrderPushing
• TestOrderPopping
• TestRemoveOrder
• TestCreateRoot
• TestAddNewLimit
• TestLimitExists
• TestLimitIsRoot
• TestHasGrandpa
• TestGetGrandpa
• TestGetMaximumLimit
• TestGetMinimumLimit
• TestGetHeight
• TestGetBalanceFactor
• TestReplaceLimitInParent
• TestRemoveLimit
• TestRotateLL
• TestRotateLR
• TestRotateRR
• TestRotateRL

Python Tests

Cython-bound C function tests:

• TestOrderPushing
• TestOrderPopping
• TestRemoveOrder
• TestAddNewLimit
• TestRemoveLimit

Python Functions and Methods:

• TestCreateBook
• TestUpdateBook
• TestDeleteOrder
• TestAddOrder
• TestAddLimit
• TestRemoveLimit

Love this implementation;

Wondering what you find the main use of it is ?

Noticed your implementation of Websocket API's for other cryptocurrency exchanges,
Would you be interested in collaborating on a joint websocket api project ?

Best,
Sam

Dear nlsdfnbch,

Thanks for your work on this library.

I had a quick question. The following sequence of orders leads to a raise NotImplementedError:

        from lob import LimitOrderBook, Order
        lob = LimitOrderBook()
        orders = [
            Order(uid=5879, is_bid=False, size=550, price=26.0),
            Order(uid=5879, is_bid=False, size=0, price=26.0),
            Order(uid=5880, is_bid=False, size=80, price=38.0),
            Order(uid=5881, is_bid=False, size=100, price=22.7)
            ]
        
        for order in orders:
             lob.process(order)

This has been discussed here.

My question is: could you put out a small code example for calling the C implementation? The test sets are a really tough access point for non C literates~.

Basically, an example, say run the list of orders above but calling the C code, would really help!

The bintrees package provides a C implementation of AVL trees, FastAVLTree. If the aim is to write everything from scratch as an academic exercise, that's understandable -- but is there a practical reason not to use it?

Thanks for your implementation on this one, I looking at integrating it on my python based trading algorithm and would like to ask if just by using lob.py will suffice to use your orderbook? Or do I have to compile C implementation keep it running on the background?

TIA

Cythonize the C src code and use it in the Python module

As per WK Selph

Each order is also an
entry in a map keyed off idNumber, and each Limit is also an entry in a
map keyed off limitPrice.

It is therefore necessary to implement this for the C implementation.