Stock Delivery System -System Design
It’s a well-known fact that the Stock market is the hottest and most fast pacing in the world. Recently I was working with a stock analyzer web app by JP Morgan, built using ReactJS and python3 with manually fed data for testing purposes, for analyzing some past stocks and their ratios.
Imagine we are building some sort of service that will be called by up to 1,000 client applications to get simple end-of-day stock price information (open, close, high, low), assuming that we have already built a resilient system for analyzing and storing stocks data efficiently. How would we design the client-facing service that provides the information to client applications?
Naive Approach:
A straight forward and direct approach that comes to our mind is that we will be making an API having 2 basic endpoints:
1- Provide stock data for the day
2- Provide particular stock details / history
Let’s analyze the performance of the above approach:
Suppose the above 2 APIs are being used by all our clients, further some developers out there have built some mobile apps that use our API to fetch data. As we can clearly see that this system is a read-heavy system, as the write queries are far less than the reads.
Let’s assume we have 10000 customers.
Total read requests in a day = 10000 reads/day on an average that grows exponentially with the increase in the number of customers. Okay so that’s large, but can we do better? Lets pictorially analyze the queries and try to find a way out.
So as we can clearly see above that the below process is getting repeated again and again :
Now can you analyze the problem and its solution? If not then let’s take a programming example and explain how to approach the solution for it.
Let’s suppose we are writing a function isPrime(int number) that returns true if the number is a prime number and let’s suppose that the user is sending the same number again and again. So let’s try and implement the above function.
isPrime(int n){
if (n%2==0) return false;
for(int i=3;i<=Math.sqrt(n);i+=2) {
if(n%i==0)
return false;
}
return true;
}Complexity :- O(sqrt(N))
Great so we found it very fast. BUT is it efficient when the user, again and again, sends the same number? NO. So what’s the better approach?
Why not just save it in a global variable or array and once computed let server the requests directly from that array. That’s the same concepts which DYNAMIC PROGRAMMING follows, it computes the subqueries and serves all the requests for the overlapping sub-problems from the pre-computed result, thus reducing the overhead of uselessly repeating the same process again and again.
public HashMap<Integer, Integer> hmap=new HashMap<> ();isPrime(int n){
if(hmap.containsKey(n)){
return hmap.get(n);
}if (n%2==0) return false;
for(int i=3;i<=Math.sqrt(n);i+=2) {
if(n%i==0){
hmap.put(n, false);
return false;
}
}hmap.put(n, true);
return true;
}Complexity :- O(sqrt(N))
This same strategy is used by Sieve of Eratosthenes when you want to compute prime numbers within a finite range of (i.e you know the upper bound).
So now whenever the request for finding if 7 is prime or not comes it will just compute once and the next time it gets a 7 it just serves from the precomputed HashMap. This same strategy we are going to use in our server also. But here the naming convention is different. Its called CACHING.
If you want to know how caching works under the hood and what type mechanisms do we use to store and retrieve data to maintain consistency and efficiency than refer to my previous article :
So for each day, these 1000+ stocks are the overlapping queries, we will store these 1000 + stocks in the local cache of the memory, and whenever the user asks for the current date’s stock we will directly serve them to him from the cache. Every night when the stock data for the past day gets updated, we will refresh this cache memory of ours with the updated record.
Thus we reduced the load on the server from :
10000+ read requests on server/day -> TO -> 1 server request per/day.
Wow !! This is how powerful caching can be.
Okay so are we done? Think Again? What if your application servers over 10 million + stocks data. Cache memory has a limit to it. But can we store a million record keys in a single node? The answer is YES we can.
Note:- As per research and practical usage, a single Redis instance can hold up to 250 million keys.
But what if we are dealing with some other practical problem in which there are a hefty number of records? We can’t store very large data in a single cache node. So how do we approach this new problem now?
As we know REDIS supports distributed caching, which basically means we can have N nodes for storing different data.
But how will the records be distributed and retrieved from these nodes? Let’s have a closer look at the architecture we would be following. In this case, we would be using the method known as Indexing.
Firstly whats Indexing :
Indexing is a data structure technique to efficiently retrieve records from the database files based on some attributes on which the indexing has been done. Clustering Index − The clustering index is defined as an ordered data file.
Okay, but how will indexing help us in this scenario? Simple, we would be dividing the records into multiple sets of indexes and each node of Redis would be handling a set of indexes. Example: We are having 10000 records and we evenly divide it into 10 Redis nodes, such that each node is having 1000 records, thus the following architecture would look like the following:
But when a client asks for record number 1000 - 2000 how will the request know which Redis node has the following range of data? In this case, Zookeeper comes to rescue us.
That’s too much to intake :P. Don’t worry I would be having a separate blog on Distributed Indexing On Cache, where we would be discussing all Zookeeper, and how to use a distributed indexing mechanism with Redis, so we won’t be going deep into these technologies over here.
Now as the Zookeeper is maintaining the information as to which Redis node holds which set of indexes, thus when a query comes to access the records of range 1000 to 10000, the Zookeeper will redirect it to the corresponding Redis node holding that range of records. Let’s update the above-used architecture according to our use case:
This architecture is basically known as a 2 tier indexing architecture, where the first unit handles the addresses of the nodes holding the actual data, which in our case is the Zookeeper which holds the addresses of the corresponding Redis nodes as keys, and the corresponding value to each key is the range that particular node holds. To maintain data availability and consistency we are following the Master-Slave architecture for every Redis node, such that in case a master node fails the slave has the data intact for serving.
So are we done? Yes, but we can improve it even further. How?
What if we are dealing with objects as a single entry, where each object itself holds some data, then serving 10000 such objects in a single request might take a long time and will thus be inefficient. This means the response time for serving 10000 records is far greater than serving 100 records at a time. Thus the concept of paging comes into the picture.
Whats Paging?
In simple words, it means dividing data into pages, such that each page contains data and the link to the next page.
Thus the query will look something like this:
When a client sends a request, the request body will be containing a start index, and an offset (which basically is the number of records we want to access).
Each response contains the small range of data and a link to the next page(which in our case is the address to the next or same node holding the next range of data, i.e if a user asks for 1000–10000 records, the first response will contain the records of the range 1000–2000 and a link to the next page containing the rest range of data.
Note: Paging at the SERVER side is far more effective and efficient than paging at the CLIENT side.
Homework Question:- Let’s assume that my service had a slightly different use-case. Let’s say it provided stocks data to users according to the query they write, i.e the company they want to see the data for or maybe software for Realtime monitoring of stocks. What approach would you follow? Would you use the same approach? If your answer is yes then think again in terms of memory.
If you like this blog, then don’t forget to give a CLAP and follow for more updates.
