DEV
BLOG
  • Design
  • Data
  • Discernment

We believe in AI and every day we innovate to make it better than yesterday. We believe in helping others to benefit from the wonders of AI and also in extending a hand to guide them to step their journey to adapt with future.

Know more

Our solutions in action for customers

DOWNLOAD

Featured Post

How we spoke to data in 2 days

What would you do in two days? Let me be more precise, what would you do on a weekend? Depending on the kind of person you are, the answers may differ. Some may wanna stay in, have a good sleep, take it slow. If you are like me, you would be on the road riding […]

Know More

MENU

  • HOME
  • SERVICES
  • PRODUCTS
  • CASE STUDIES
  • INDUSTRIES
  • CAREERS
  • CONTACT US

Artificial Intelligence

Blockchain

Enterprise Solutions

Blog
White Papers
Resources
Videos
News

Befriending Data Structures: A retrospective of building a trade engine

  • mm
    by Goutham Krishna on Thu Jan 23

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 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. 

Author

  • mm
    Goutham Krishna

Goutham is a technologist and developer who specializes in Blockchain technologies and Cryptocurrencies. Though he’s worked within numerous privacy and security sectors, Goutham's recent emphasis has been on solutions built on Ethereum, Tezos, smart contracts, and smart signatures, in particular, decentralized self-sovereign identity.

Related Posts

Drive into stories worth discussing

  • mm
    Creating a private blockchain using Hyperledger Besu
    Prasanth Venugopalan
  • mm
    Reverse Engineering Openseas to build an NFT Market place
    Shehin FN

Categories

View articles by categories

  • Uncategorized

Subscribe now to get our latest posts

All Rights Reserved. Accubits INC 2020