Possible refactoring of market engine

[theoreticalbts]

The main purpose of this ticket is to provide a place to carefully evaluate the costs and benefits before deciding whether to move forward with a refactoring of the market engine for 0.8.0.

The details of the proposed refactoring are documented here: https://github.com/theoreticalbts/bitshares/blob/market_refactor/docs/market-engine-0.8.0.md

The document will be of some use even if we do not proceed with the refactoring, as it establishes some useful terminology.

[theoreticalbts]

This post summarizes the reasons why I feel the refactoring is necessary.

The current code suffers from serious deficiencies. The biggest one is that the code dealing with feed-dependent nature of short orders will need to be re-written. As @vikramrajkumar cogently pointed out in #1370 the develop branch's present implementation does not use pending_chain_state and is therefore not undoable. Lack of undo semantics will likely result in severe network problems and failure to reach consensus.

Margin orders also need split into two types based on expiration / cover (or actually three types, if you consider inactive orders to be a type).

Since we're doing the splitting logic for two order types anyway, and we have to rewrite most of it anyway, we might as well make a general framework for splitting orders which can be adapted to relative orders as well; see #1342.

The problems are so severe that I considered recommending backing out the market engine changes and moving relative orders out of 1.0. Unfortunately, the bug that started all this -- #1315 -- is indisputably alive and well on the master branch.

So given that we must rewrite substantial parts of the market engine anyway, we may as well do it right and make a clean implementation with conceptual clarity and explicitly documented design.

Since I've done substantial thinking about the issues (see link in OP), I think I'm the best person to claim this task. I'd like to start the rewrite immediately, and in the interests of avoiding wasted or duplicated effort, I'd like to warn everyone (including @bytemaster) to hold off on making any changes to the market engine code, as further patches will likely need to be tossed or heavily modified after the refactoring.

I should have a working (or at least compiling) version of the refactored market engine (hopefully ~48 hours).

[theoreticalbts]

Here's a list of problems I've spotted which may arise from the architecture, based on a brief read-through of the code:

• The multi-branch if statement starting at https://github.com/BitShares/bitshares/tree/780030ed0813080e81737cc5bc79592ac28a0830/libraries/blockchain/market_engine.cpp#L196 is problematic. Is this supposed to have cases for every pair of order types? If so, it should have many more cases -- but a 16 case if statement is a problematic in its own right.
• https://github.com/BitShares/bitshares/tree/780030ed0813080e81737cc5bc79592ac28a0830/libraries/blockchain/market_engine.cpp#L182 looks wrong.
• There is no documentation and no planning of the overall algorithm, so it is difficult to figure out its correctness.
• Only one branch of the multi-branch if results in fees being handled.
• API of get_next_ask and get_next_bid are not well-specified
• Prioritization of margin calls is wonky

[arhag]

So given that we must rewrite substantial parts of the market engine anyway, we may as well do it right and make a clean implementation with conceptual clarity and explicitly documented design.

+5%

I should have a working (or at least compiling) version of the refactored market engine (hopefully ~48 hours).

Looks way too optimistic but I wish you luck!

Other things to say after reading your document:

• Make sure that called cover orders are not "at the feed price" but rather are limit orders with a price limit at 10% below the feed price in BitAsset/BTS.
• Inoperative (I don't like that name) cover orders are ones manually initiated by the short position owner, correct? In that case, it should be possible for the owner to cancel an inoperative cover order. Also, an inoperative cover order should be at some specified price (either an absolute price or a price relative to the price feed with a price limit).
• An inoperative cover order should be cancelled and be replaced (by the blockchain) with either an expired cover order (if the short position expires) or a called cover order (if the short position is margin called). Furthermore, an expired cover order should be cancelled and be replaced (by the blockchain) with a called cover order (if the short position is margin called). Once a called cover order is created, it can only be destroyed by being fully matched.
• Make sure that an expired cover order (which can match with orders up to its price limit at the price feed) can match with mobile short orders (which are stuck at the price feed). No <= vs < errors please.
• A mobile relative order that is exactly at the price feed (0% offset) should have matching priority over mobile short orders.
• Please be really careful (and document properly) about all the various ways percentage fees and overlap fees work. What happens when a UIA has a fee defined and it is trading against a BitAsset. Is the percentage fee on the UIA, and any overlap goes to the BitAsset? How does overlap work in BitAsset/BitAsset pairs? How do fees work in UIA-A/UIA-B markets if UIA-A has a percentage fee of 1% defined and UIA-B has a percentage fee of 2% defined. Specific examples should be documented and could be used as test cases.
• Although asking to add limit orders to the new market engine at this point is going beyond what I could reasonably wish for, I still would appreciate if you read this (if you haven't already) and think about whether this new market engine framework could be designed in a way to make it not too difficult to add that limit order functionality to the market engine in the future (without requiring another rewrite).

[vikramrajkumar]

@theoreticalbts You can refer to account_db_interface::store and account_db_interface::remove for an example of how to ensure index consistency through arbitrary state transitions and rewinds. account_records are currently our most complex record type in terms of additional indices.

[bytemaster]

While I agree with the need to refactor, I disagree with doing it at this point in time. A refactor will easily take a month (not 48 hours).

The refactor needs to factor in far more than what has even been discussed in this ticket.

[theoreticalbts]

A refactor will easily take a month (not 48 hours).

We'll see about that :)

But if I don't have it finished (at least roughly) by tomorrow -- the big question becomes, what are we going to do?

The alternative is to launch our shiny new 1.0 release with the current market engine in master, which we know doesn't work correctly due to fundamental architectural issues ( #1315 ).

We cannot use the relative orders implementation currently in the develop branch because it has a serious risk of forking the network (since it doesn't use pending_chain_state). We could pour substantial development effort into making it work "well enough" with the current engine, but the value of that is questionable for two reasons:

• If people want relative order functionality badly enough, they can write trading bot scripts that interface to the RPC.
• With @bytemaster's comment above agreeing with the need to refactor, that means there is unanimous support among the core developers (in-person discussions yesterday made it clear that everyone else was on board). If we all know refactoring is needed, it is clear that investment of development resources in the current engine should be minimized since all the code written will be re-written anyway.

The refactor needs to factor in far more than what has even been discussed in this ticket.

Please be specific!

[vikramrajkumar]

@theoreticalbts Please see my revised comments on the pending state issue here: https://github.com/BitShares/bitshares/issues/1370#issuecomment-73932688

[theoreticalbts]

After much internal discussion, we've finally decided that the solution is that, in the interests of stability and getting 1.0 out the door, relative orders must go. Anything that can be done with relative orders can be done better with a trading bot script, because relative orders by definition are limited to moving at the same speed as feed updates.