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?

A data structure enables efficient access and modification of data by efficient data organization, data management, and data storage. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data. In simple words, a data structure is a way of organizing your data efficiently along with certain functions you can perform in it.

Befriending Data structures.

I never thought I’ll use data structures in my life until the day I and a few friends of mine from my company — Accubits Technologies decided to build an open-source trade engine. A trading engine is a high-performance application because a typical trade engine demands high availability, high throughput, low latency and should deliver consistent and excellent performance.

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.