incorrect OrderBook for binance

[tristan-murfitt-elw]

Describe the bug Over time, internal binance orderbook can be incorrect because we don't regularly poll the snapshot. In comparison, coinbase WS feed automatically supplies regular snaps (and doesn't truncate the book!)

Tagging @jinusean because their recent PR https://github.com/bmoscon/cryptofeed/pull/580 touched a lot of this file and I'm sure they can help confirm!

More detail When fetching snapshot we truncate depth to 1000 (instead of the max of 5k, self.valid_depths[-1]): https://github.com/bmoscon/cryptofeed/blob/b367c0fdfcc5e4f0be6068c5d51a421cf4b4782b/cryptofeed/exchanges/binance.py#L259

A new snapshot only gets fetched when a message is dropped (missing seq num): https://github.com/bmoscon/cryptofeed/blob/b367c0fdfcc5e4f0be6068c5d51a421cf4b4782b/cryptofeed/exchanges/binance.py#L253

I think this means, after running for a while, the internal OB could be outdated with the real world. The initial 1000 levels are recorded, and we store deltas at all(?) levels, but we will never know about unchanged levels outside of those initial 1k levels. This is a problem if the market moves in one direction over time, and the real book has an unchanged (old) limit order but our internal OB doesn't.

Do you both agree? If so, @bmoscon do you think any other exchanges suffer from this problem?

Solution

• Increase snap depth to 5k to reduce the risk of this happening.
• Periodically fetch a new snapshot from the API (eg. every 30s)

Cryptofeed Version latest

[tristan-murfitt-elw]

Binance websocket docs "How to manage a local order book correctly"

Surprises me that they don't mention this potential issue (and tell you to regularly refresh snapshot)

[bmoscon]

@tristan-murfitt-elw - their docs indicate that we should use 1000 as the depth, are you sure that the websocket is providing book updates for all 5000 levels?

[tristan-murfitt-elw]

@bmoscon there are certainly more than 1000 levels in the binance order books so we should use the maximum available (as is done for other exchanges).

To test this, I set depth to 5 and watched the internal OB get larger and larger to 2000+ levels as the updates came in.

That being said, the main concern here is the stale book levels from not regularly refreshing the snapshot. Snapshot is 1k, book is definitely deeper than that, so if the market moves in one direction there will be inconsistency with internal OB vs the exchange

[jinusean]

I ran two scripts for about an hour that stored data from:

1. Cryptofeed's callback (1000ms).
2. Polling the RESTapi for the book snapshot (500ms).

There were about 5000+ snapshots for each data source, and 362 matching update_ids. All of the matching IDs had matching snapshots, without a single non-matching row. Perhaps there is a possibility for issues if we were using the full trade streams, but this doesn't seem to be the case in aggTrade consumption.

In regards to the ever expanding internal OB, I don't think this is much of an issue in terms of data integrity since the feed class will prune the extra levels before calling the data back to the user.

Implementing a validity check every 'x' intervals would make the system more robust, but it's not something I want to invest in right now without any empirical data.

[tristan-murfitt-elw]

Just did an experiment to get some empirical data and prove that this is a problem:

Experiment code and explanation here: https://github.com/bmoscon/cryptofeed/pull/606

Steps:

1. Place some limit sells in a binance book fairly far out from mid (low volume OB is easier to test)
2. Set the cryptofeed snapshot to only take first 20 levels, start cryptofeed. (I chose to turn off the max depth param because it's slow, non-default, and not necessary if you can just truncate your book after)
3. Wait for market to move up (towards your limit sells)
4. Observe that these orders are not in the cryptofeed internal OB

This scenario will happen even if you have 5000 levels in the book, because any prices outside of those first 5k may not be updated (so no deltas pushed from binance over the WS). This wouldn't happen if Binance gave us the full L2 order book. It will happen more often the smaller your initial snap is (hence why 5000 default is better than 1000).

Potential solution:

• Every N seconds, fetch a new snapshot
• If anything is in that snapshot and not in the internal OB, then add it (checking this is O(n * logn) operation because sorteddict lookup is O(logn))
• Be sure to check the timings that there wasn't a delta to remove said price level between requesting and retrieving snapshot

[Tiergarten]

An ideal solution would utilise the binance updateIds (if this can be performant): https://github.com/binance/binance-spot-api-docs/blob/master/web-socket-streams.md#diff-depth-stream

[jinusean]

@tristan-murfitt-elw sorry where in the code is the book truncated?

I'm currently running 3 scripts:

1. Polling rest api
2. Cryptofeed stream
3. Code from official binance-exchange github

So far all three sources are in sync, I'll keep it running for another day or so.

I also came across this forum question. The UI should not be considered the absolute truth.

@Tiergarten if we can prove that the snapshot data != cached order book data, then we can just replace the cache with the snapshot without bothering to do an update_id check.

[tristan-murfitt-elw]

@jinusean I added max depth of 20 to make it easy for me to simulate the orders on the live exchange and observe the cryptofeed internal OB to be inconsistent. The same problem can occur with a depth of 5k, albeit less frequently (because a price move to that level would take longer to happen, allowing more time for each level to be updated and receive a delta over the WS).

The binance exchange example is also therefore wrong, and suffers the same problem!!

I know the UI is the absolute truth in this example because I placed the orders myself and confirm I didn't get any fills. But these orders were not found in the cryptofeed internal book. So this can absolutely happen (all because Binance don't provide the full L2 book snaps)

we can just replace the cache with the snapshot without bothering to do an update_id check

this is what I propose too, but we should be careful with the timings: receiving updates while polling for the new snapshot

[tristan-murfitt-elw]

@jinusean what cryptofeed snapshot depth are you using for this experiment? the default is now set 5000 since this commit a few days ago https://github.com/bmoscon/cryptofeed/commit/1ce8ab42a253cad17fe1533a1a3c16c5b7518e69

So far all three sources are in sync, I'll keep it running for another day or so.

I wouldn't expect to see a sync error until the price moves past those first N levels.

eg. If I place a BTC sell order right now for $120,936.10 and nobody else updates this price level, when the price moves up to that range, cryptofeed is not going to have knowledge of the order (because initial snap was only 5k levels, and no update delta was received for that level)

[jinusean]

Ok let's just see if a discrepancy between the orderbook and snapshot ever occurs first. There's a chance the snapshots too are invalid, then we'd have to raise the issue to the Binance devs.

And receiving updates while polling for the snapshot shouldn't be an issue since the current implementation already uses a buffer to handle such situations. I just want to make sure the snapshot's data is actually different from the websocket data first.

[jinusean]

@jinusean what cryptofeed snapshot depth are you using for this experiment? the default is now set 5000 since this commit a few days ago 1ce8ab4

It's at 5000.

Oddly the official Binance script truncates the book if it ever goes beyond 1000 levels.

https://github.com/binance-exchange/binance-toolbox-python/blob/aa8cbde68cf7118cbbce7ff1a3d24ab18e0ba9bf/spot/manage_local_order_book.py#L72-L74

[tristan-murfitt-elw]

Ok let's just see if a discrepancy between the orderbook and snapshot ever occurs first.

See my example here https://github.com/bmoscon/cryptofeed/pull/606. If you perform this same test while running your experiment you'll see a discrepancy

Oddly the official Binance script truncates the book if it ever goes beyond 1000 levels.

This is quite common, and the same as what cryptofeed does if you set the max_depth. Most people are only interested in the top levels of the book. However, without regularly refetching the snapshot, there could be the inconsistency I found (as above). Might need to reach out to binance devs so they can at least update their docs/example to notify end users

[jinusean]

I can see the discrepancy in the UI but that doesn't mean there will be one between the snapshot and OB(?) Surely the difference will be caught if the script is run for 24hours.

[tristan-murfitt-elw]

discrepancy is between the UI (and real world!) vs the cryptofeed orderbook.

if you fetch a snapshot from binance again when this happens, the new snapshot is also different to the cryptofeed internal one! (I didn't push this code but it's easy to replicate)

[jinusean]

Can you try replicating the issue with this branch https://github.com/jinusean/cryptofeed/tree/binance-snapshot-depth

You can set the max_depth to whatever you want since the snapshots will always fetch with max_depth=5000 so the internal ob will have the max levels. And all the callback data will only be a pruned copy.

[hk-yuan]

Hi @jinusean , correct me if I'm wrong but the only difference I could see between that branch and @tristan-murfitt-elw 's test branch is this self.max_depth. By setting max_depth as max(self.valid_depths) in your branch it makes the experiment more difficult to assess (who knows whether a price level >5k from mid won't get updated after the market also moves in its direction even exists when you run your script ... (!) ); the issue is more obvious with fewer depths which is why I believe @tristan-murfitt-elw forced it down to 20 and placed his own orders in on the actual exchange. I hope an image might illustrate the issue better:

Dotted box shows snapshot at max_depth (it's shown to be 4 here but can be 5k - doesn't really matter unless it's truly the full orderbook). Let's also assume this is the actual snapshot depth rather than pruned depth. Over time the market can move, in this case we're looking at ASK so let's say it moves up - our bottom levels get dropped and max_depth should encompass levels not present in the first snapshot.

We receive deltas which update the values (I've shown a "change from T0" column just for illustration here). If a particular level, which was outside the original snapshot, receives a delta - that's fine, it will be captured at T1. If a particular level doesn't receive a delta then will we ever see it until another snapshot?

The value of fetch max_depth isn't a problem in of itself, it's the fact that we don't take more regular snapshots to fill the gaps.

[jinusean]

@hk-yuan thank you for clarifying. I was under the impression there were no price levels beyond > 5000 since the assets I tested had no more than 1500 levels.

In that case, we can store a boolean whenever the order book depth hits 5000 (whether it's from the original snapshot or via deltas). And then we can fetch another snapshot once the size drops below a certain level. For added security we can do a timed refetch (every hour?).

@tristan-murfitt-elw what do you think?

[tristan-murfitt-elw]

@hk-yuan much better explanation than mine, thanks!

@jinusean in practice I expect a lot of books to have more than 5k levels (I think coinbase BTC markets can be close to 20k levels per side!)

The main problems are:

• If cryptofeed user sets a smaller max depth (eg. 100), the refetch needs to occur more frequently because there's a much higher risk of the market price moving close to the ends of the original snapshot
• When fetching a new snapshot, it must apply updates that were received over the WS during the snapshot REST GET request
• We don't want to buffer the incoming updates while fetching the snapshot because that'll prevent these updates being pushed through to cryptofeed internal OB and callbacks to users (huge latency)
• How many other exchanges is this a problem for. Kraken too? More?

Triggering fetch of new snapshot

• On a timer is definitely a good idea. Timer should be set based on the depth the user has chosen. For <10 depth this likely needs to be every few seconds! For 5k depth it can probably be done every few mins (as it completely depends on how volatile the market is... a flash crash is a perfect example)
• Fetching when the size drops below a certain level may not work too well - the book usually increases in size over time as more deltas far outside of the original snapshot depth get sent over the WS

Processing the new snapshot

1. Send REST GET request for new snap
2. While it's in flight, continue sending updates through to internal OB and callbacks
3. While it's in flight, also buffer and collect the updates
4. Snapshot response comes back, apply the buffered updates to it. Then loop over every bid/ask level and check if it's in our internal orderbook. If it's in the book it should always match the size exactly (otherwise something went very wrong). Extra levels in our internal book are normal and expected and we want to keep these. Extras in the new snapshot are these stale prices we've been discussing, and these should just be added into the book.
5. Simulate book "updates" for each of these levels that should be added to the internal OB.

[jinusean]

• If cryptofeed user sets a smaller max depth (eg. 100), the refetch needs to occur more frequently because there's a much higher risk of the market price moving close to the ends of the original snapshot If we set the snapshot level == max_depth, we will never get an update for the (max_depth + 1) level, and it will be too costly for the rate limit to constantly fetch new snapshots every second, especially if we are observing multiple pairs. Instead, how about we always fetch the snapshot with the max level of 5000, that way we can minimize the frequency of api calls. This applies to the next bullet point.

• Fetching when the size drops below a certain level may not work too well - the book usually increases in size over time as more deltas far outside of the original snapshot depth get sent over the WS Assuming that users don't need all 5000 levels, let's say we fetch a snapshot limit=5000, and receive a book with 5000 levels. Then we'd mark 'last_book_price=snapshot[5000].price'. Once the index of last_book_price drops down to a threshold_index, we will trigger a new snapshot and repeat the process. For example, if we set max_depth=2000, threshold_index can be something like 3000 since there is a very slim chance price levels will drop by 1000 during the snapshot fetch.

• How many other exchanges is this a problem for. Kraken too? More? No idea as I've only used/worked on Binance.

• Processing the new snapshot

4. Can't we just replace our internal OB with the snapshot once the snapshot's update_id is greater than the obs?

[tristan-murfitt-elw]

If we set the snapshot level == max_depth, we will never get an update for the (max_depth + 1) level

This isn't the case. If you get 5000 snapshot from Binance, their WS feed will still give you every delta that happens. If I place a BTC sell order at $1,000,000 it will still get an update through the feed.

It's bad practice to set the max_depth field in cryptofeed because it actually diffs the new vs old OB every snapshot, truncates to your max_depth, and then simulates all the necessary updates. Doing this per update is very slow and (from experience) is not a good idea

Can't we just replace our internal OB with the snapshot once the snapshot's update_id is greater than the obs?

Problems with this are:

1. Our internal OB has extra useful data in it (from WS updates that aren't in the most recent snap)
2. We still need to simulate updates for any "stale" prices in the new snap which should've been in the internal book (for any downstream subscribers of the book deltas)

[jinusean]

If we set the snapshot level == max_depth, we will never get an update for the (max_depth + 1) level

This isn't the case. If you get 5000 snapshot from Binance, their WS feed will still give you every delta that happens. If I place a BTC sell order at $1,000,000 it will still get an update through the feed.

I meant if we fetch a snapshot with limit=1000 and there are over 1000 levels, we'd never see that level in the deltas since it has already been applied prior to the subscription. Hence we should fetch a snapshot that is higher than the user defined max_depth. Ideally just fetch the maximum level allowed to minimize api calls.

It's bad practice to set the max_depth field in cryptofeed because it actually diffs the new vs old OB every snapshot, truncates to your max_depth, and then simulates all the necessary updates. Doing this per update is very slow and (from experience) is not a good idea

Right, the max_depth should be a soft limit for the user. The internal ob will/should maintain the max 5000 levels.

Can't we just replace our internal OB with the snapshot once the snapshot's update_id is greater than the obs?

Problems with this are:

1. Our internal OB has extra useful data in it (from WS updates that aren't in the most recent snap)
2. We still need to simulate updates for any "stale" prices in the new snap which should've been in the internal book (for any downstream subscribers of the book deltas)

Ok gotcha.

One last thing is, if we fetch a snapshot with limit=x, and we get orders sizes that are < x, is it safe to assume that there are/will be no missing orders? Running my test the other day for 24 hours, the orderbook was 100% in sync with new snapshots, albeit the orders size never went beyond 1500.

[bmoscon]

I did change the code to use the maximum book size for the snapshots. Shouldnt this largely correct this issue?

[villekuosmanen]

Based on my understanding the problem still exists in 5000 book size, it's just less likely to occur.

I can start looking into implementing the fix suggested by @tristan-murfitt-elw. Feel free to assign this issue to me. I'm new to working on the upstream branch of cryptofeed, but I've done some work on a fork during the past few weeks.

[peedrr]

• Periodically fetch a new snapshot from the API (eg. every 30s)

@villekuosmanen - is this the solution you're proposing to implement?

Can I suggest that, rather than a fixed period of time, we instead refresh on a count of delta messages received? By their nature, I am guessing that low volume pairs will not suffer from this problem as much as high volume pairs, therefore do not require such frequent refreshes.

If we request snapshots all at the same time, I'm concerned it will exacerbate another open issue whereby users who subscribe to large numbers of symbols are not able to resubscribe cleanly when their connections get reset at the 24 hour mark, because of the sudden surge of HTTP requests.

@tristan-murfitt-elw - thoughts on this?

[villekuosmanen]

@peedrr doing it based on numbers of messages could work. You could use max orderbook depth to set the max number of delta messages seen before refreshing. If we set the ratio of max delta messages seen before a refresh to 0.5, at the default parameters (book depth of 5000, depth_interval of 100ms, and assuming the book changes at every step) there would be ~ 4 minutes 10 seconds between snapshots. Although changing these parameters could cause strange things to happen, such as depth of 20 and depth_interval of 100ms which would refresh every two seconds which feels excessive.

In any case the exact details on how (and how frequently) a new snapshot is loaded can be worked out later.

[tristan-murfitt-elw]

@peedrr low volume pairs probably suffer with this problem more because books levels are updating less often (fewer limit orders being amended) so there's a higher risk of prices outside the initial 5k levels not triggering WS deltas. edit: with the exception of books which are so shallow Binance can actually return the full book without truncating!

Agree performance & rate limits are a concern.

As contributors to the library, we have a responsibility to ensure the data is correct. The longer we wait between snapshots, the more incorrect data is in the internal OB (starting at the outer layers).

• For users setting max depth to something small (eg. <50) this is a huge problem.
• For users setting max depth to the default (5000) this is not necessarily a problem for execution, because these are far out-the-money orders, but we cannot make assumptions on what end users will be using the data for. They may be analysing the full OB (and care about the data integrity even at 5000 levels deep)

[nirvana-msu]

max_depth parameter's behavior is very misleading. Let's say I set it to something like 10. It is quite likely that, even on the second update, I'll receive less than 10 levels in my callback. Specifically, what happens is:

1. Following first WS update, a snapshot is being fetched for exactly max_depth levels
2. Another WS update comes and it says a level (close to the top of the order book) is removed.
3. Update is applied to the snapshot, removing the level.
4. Order book with less than max_depth levels is pushed to the callback.

The way it is implemented now, max_depth is essentially unusable. I have to avoid setting it, and trim the levels within my callback.

@bmoscon a much more intuitive behavior would be if max_depth only defined the number of levels pushed to the user in the callback - but internally the library should do whatever is needed to maintain an accurate state. That means fetching snapshot for a lot more levels than max_depth, and re-fetching whenever price moves close enough to a level where the true order book state is not known (was not fetched).

[bmoscon]

@nirvana-msu not sure what you are talking about. Are you claiming that when you set max depth to 10 you're getting more than 10 levels in the orderbook? All max_depth does is prevent the orderbook from showing you more than that number of levels, you can get less than that many levels

[nirvana-msu]

@bmoscon no I'm saying the opposite - when I set max_depth to, say, 10 levels, very often I would receive fewer than 10 levels in my callback.

Given that the true order book has many thousand levels, when I set max_depth to 10, I expect to receive exactly 10 top levels, always (unless there really are no 10 levels in the true order book). But I receive fewer than 10.

[bmoscon]

@nirvana-msu please provide sample code or other information so I can reproduce this (exchange, trading pairs, etc). Also provide the version number you are on.