Befriending Data Structures: A retrospective of building a trade engine

Data structures are one of the most complex and underrated topics in the field of computer science. It is very rare to see a developer, especially a web developer implementing this amazing concept into action. This is because a majority of developers have a perception of ‘ARRAYS’ as a ‘one size fits all’ solution for all data structure problems. But, the moment you harness the power of data structures, there is no going back. You’ll be lured by the level of optimizations offered by data structures in terms of space and time complexity. In this article, I share my experience when I decided to implement data structures for an open-source trade engine platform.

What is a data structure?

Befriending Data structures.

A trade engine is nothing but a matching engine of a crypto-asset exchange. The sole purpose of the trade engine is to match the buy order and sell order. Initially, our obvious choice was to add the incoming data into a database and fetch it out using a query. We thought this as a safe bet in terms of consistency and less overhead. We built the MVP using conventional methods of DB queries and using Arrays, but to our disappointment, the MVP never came close to the throughput we expected. We had all the logics in perfected, but what we lacked was a scalable implementation.

After a series of researches, we decided to go with an in-memory database called Redis. We did a trial implementation and moved the matching engine and order book into Redis. Fingers crossed, everyone was rooting for a perfect implementation that achieved the desired results. But, it turns out, it was a total disaster considering the effort we put in and the results we got. The throughput was comparatively better, but still not up to our expectations.

Back to research, on further investigations on other stock exchanges as well as other high-performance matching engines, we realized that data structure was the way forward. Our next challenge was to decide on what data structure to use. There is a trade-off between space-time optimization and processing power. Our aim was to build a trade engine that is super fast even if it takes a bit more computation power and space. Since the matching engine relies on faster data access, insertion, and deletion, we decided to go on with a tree data structure. Our first choice was the AVL tree, but the reorientation of the tree on each insertion was an issue. So, we moved to the RB tree data structure which provides the same time complexity with less rotation at the time of insertion.

RB treemap (a map-based implementation of RB tree) implementation was very promising and we produced the best suite with a log(n) complexity. The ability of the RB tree to build a custom comparator for the treemap was also useful and fit for the use case we were working on. With this modification in core engine logic with data structure, we were able to achieve a throughput above our expectations.

Originally published at https://dev.accubits.com on January 23, 2020.

--

--

Accubits Technologies is an enterprise solutions development company focusing on AI and Blockchain technologies, based in Virginia, USA. https://accubits.com/

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Accubits Technologies Inc

Accubits Technologies is an enterprise solutions development company focusing on AI and Blockchain technologies, based in Virginia, USA. https://accubits.com/