Building an Orderbook representation for a Bitcoin exchange
<p>I am trying to build an Orderbook representation for the <a href="http://poloniex.com/" rel="nofollow noreferrer">Poloniex Bitcoin exchange</a>. I am subscribing to the <a href="https://poloniex.com/support/api/" rel="nofollow noreferrer">Push-API</a> which sends updates of the Orderbook over Websocket. The problem is that my Orderbook gets <strong>inconsistent</strong> over time, i.e. orders which should have been removed are still in my book.</p>

<p>The Orderbook on the following picture has this format:</p>

<pre><code>Exchange-Name - ASK - Amount - Price | Price - Amount - BID - Exchange-Name
</code></pre>

<p><a href="https://i.stack.imgur.com/WYwVz.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/WYwVz.png" alt="enter image description here"></a></p>

<p>On the left side (<em>ASK</em>) are people who are selling a currency. On the right side (<em>BID</em>) are people who are buying a currency. <strong>BTCUSD</strong>, <strong>ETHBTC</strong> and <strong>ETHUSD</strong> describe the different markets. <strong>BTCUSD</strong> means Bitcoin is exchanged for US-Dollar, <strong>ETHBTC</strong> means Ethereum is exchanged for Bitcoin and <strong>ETHUSD</strong> means Ethereum is exchanged for US-Dollar.</p>

<p>Poloniex sends updates over Websocket in JSON-Format. Here is an example of such an update:</p>

<pre><code>[
   36,
   7597659581972377,
   8089731807973507,
   {},
   [
      {"data":{"rate":"609.00000029","type":"bid"},"type":"orderBookRemove"},{"data":{"amount":"0.09514285","rate":"609.00000031","type":"bid"},"type":"orderBookModify"}
   ],
   {
      "seq":19976127
   }
]
</code></pre>

<ul>
<li><strong>json[0]</strong> can be ignored for this question.</li>
<li><p><strong>json[1]</strong> is the market identifier. That means I send a request like "<em>Subscribe to market BTCUSD</em>" and they answer "<em>BTCUSD updates will be sent under identifier number 7597659581972377</em>".</p></li>
<li><p><strong>json[2]</strong> can be ignored for this question.</p></li>
<li><strong>json[3]</strong> can be ignored for this question.</li>
<li><strong>json[4]</strong> contains the actual update data. More about that later.</li>
<li><strong>json[5]</strong> contains a sequence number. It is used to execute the updates correctly if they arrive out of order. So if I receive 5 updates within 1 second by the order <em>1 - 3 - 5 - 4 - 2</em> they have to be executed like <em>1 - 2 - 3 - 4 - 5</em>. Each market gets a different "sequence-number-sequence".</li>
</ul>

<p>As I said, <strong>json[4]</strong> contains an <em>array</em> of updates. There are three different kinds in <code>json[4][array-index]["type"]</code>:</p>

<ol>
<li><strong>orderBookModify</strong>: The available amount for a specific price has changed.</li>
<li><strong>orderBookRemove</strong>: The order is not available anymore and must be removed.</li>
<li><strong>newTrade</strong>: Can be used to build a trade history. Not required for what I am trying to do so it can be ignored.</li>
</ol>

<p><code>json[4][array-index]["data"]</code> contains two values if it is a <strong>orderBookRemove</strong> and three values if it is a <strong>orderBookModify</strong>. </p>

<ul>
<li><strong>rate</strong>: The price.</li>
<li><strong>amount (only existant if it is a orderBookModify)</strong>: The <em>new</em> amount.</li>
<li><strong>type</strong>: <em>ask</em> or <em>bid</em>.</li>
</ul>

<p>There is also one kind of special message:</p>

<p><code>[36,8932491360003688,1315671639915103,{},[],{"seq":98045310}]</code></p>

<p>It only contains a sequence number. It is kind of a heartbeat message and does not send any updates. </p>

<h2>The Code</h2>

<p>I use three containers:</p>

<pre><code>std::map&lt;std::uint64_t,CMarket&gt; m_mMarkets;
std::map&lt;CMarket, long&gt; m_mCurrentSeq;
std::map&lt;CMarket, std::map&lt;long, web::json::value&gt;&gt; m_mStack;
</code></pre>

<p><code>m_mMarkets</code> is used to map the market-identifier number to the Market as it is stored inside my program. </p>

<p><code>m_mCurrentSeq</code> is used to store the current sequence number for each market.</p>

<p><code>m_mStack</code> stores the updates by market and sequence-number (that's what the <code>long</code> is for) until they can be executed.</p>

<p>This is the part which receives the updates:</p>

<pre><code>// ....

// This method can be called asynchronously, so lock the containers.
this-&gt;m_muMutex.lock();

// Map the market-identifier to a CMarket object.
CMarket market = this-&gt;m_mMarkets.at(json[1].as_number().to_uint64());

// Check if it is a known market. This should never happen!
if(this-&gt;m_mMarkets.find(json[1].as_number().to_uint64()) == this-&gt;m_mMarkets.end())
{
    this-&gt;m_muMutex.unlock();
    throw std::runtime_error("Received Market update of unknown Market");
}

// Add the update to the execution-queue
this-&gt;m_mStack[market][(long)json[5]["seq"].as_integer()] = json;

// Execute the execution-queue
this-&gt;executeStack();

this-&gt;m_muMutex.unlock();

// ....
</code></pre>

<p>Now comes the execution-queue. I think this is where my mistake is located.</p>

<p>Function: "executeStack": </p>

<pre><code>for(auto&amp; market : this-&gt;m_mMarkets) // For all markets
{
    if(this-&gt;m_mCurrentSeq.find(market.second) != this-&gt;m_mCurrentSeq.end()) // if market has a sequence number
    {
        long seqNum = this-&gt;m_mCurrentSeq.at(market.second);

        // erase old entries
        for(std::map&lt;long, web::json::value&gt;::iterator it = this-&gt;m_mStack.at(market.second).begin(); it != this-&gt;m_mStack.at(market.second).end(); )
        {
            if((*it).first &lt; seqNum)
            it = this-&gt;m_mStack.at(market.second).erase(it);
            else
            ++it;
        }

        // This container is used to store the updates to the Orderbook temporarily.
        std::vector&lt;Order&gt; addOrderStack{};

        while(this-&gt;m_mStack.at(market.second).find(seqNum) != this-&gt;m_mStack.at(market.second).end())// has entry for seqNum
        {
            web::json::value json = this-&gt;m_mStack.at(market.second).at(seqNum);

            for(auto&amp; v : json[4].as_array())
            {
                if(v["type"].as_string().compare("orderBookModify") == 0)
                {
                    Order::Type t = v["data"]["type"].as_string().compare("ask") == 0 ? Order::Type::Ask : Order::Type::Bid;
                    Order newOrder(std::stod(v["data"]["rate"].as_string()), std::stod(v["data"]["amount"].as_string()), t, market.second, this-&gt;m_pclParent, v.serialize());

                    addOrderStack.push_back(newOrder);

                } else if(v["type"].as_string().compare("orderBookRemove") == 0)
                {
                    Order::Type t = v["data"]["type"].as_string().compare("ask") == 0 ? Order::Type::Ask : Order::Type::Bid;
                    Order newOrder(std::stod(v["data"]["rate"].as_string()), 0, t, market.second, this-&gt;m_pclParent, v.serialize());

                    addOrderStack.push_back(newOrder);

                } else if(v["type"].as_string().compare("newTrade") == 0)
                {
                    //
                } else
                {
                    throw std::runtime_error("Unknown message format");
                }
            }

            this-&gt;m_mStack.at(market.second).erase(seqNum);
            seqNum++;
        }

        // The actual OrderList gets modified here. The mistake CANNOT be inside OrderList::addOrderStack, because I am running Orderbooks for other exchanges too and they use the same method to modify the Orderbook, and they do not get inconsistent.

        if(addOrderStack.size() &gt; 0)
        OrderList::addOrderStack(addOrderStack);

        this-&gt;m_mCurrentSeq.at(market.second) = seqNum;

    }
}
</code></pre>

<p>So if this runs for a longer period, the Orderbook becomes inconsistent. That means Orders which should have been removed are still available and there are wrong entrys inside the book. I am not quite sure why this is happening. Maybe I did something wrong with the sequence-numbers, because it seems that the Update-Stack does not always get executed correctly. I have tried everything that came to my mind but I could not get it to work and now I am out of ideas what could be wrong. If you have any questions please feel free to ask.</p>