STOCK EXCHANGE SYSTEM DESIGN | AMAZON INTERVIEW QUESTION DESIGN STOCK EXCHANGE

[@ashishmishra8755]

Content is good, But your voice is too low to hear even after increasing volume to 100% on ThinkPad

[@Rakesh-uk4sy]

As the voice is too low, i have put 100% volume but that caused very inconvenience because of sudden youtube ads with high volume

[@srinivasanvk57]

yes this is the only problem in the video. Everything else is good

[@vishalprabhakar14]

Shouldn't time complexity for LL be O(n), as one may end up scanning the whole list to find the right spot of insertion.

[@yogeshedekar6078]

SInce he mentioned heap I think Priority Queue would serve the purpose. From java standpoint since default remove operation from priority queue gives the smallest element we can use a regular priority queue for Sell orders and a max heap kind of priority queue that gives the maximum element when required for buy orders. That will take the overhead of sorting from program and add it in the data strtucture itself with each transaction of adding and removing at O(nlog(n)) complexity.

[@arpanbag001]

@@vikramsah6776 How can you do binary search on a LinkedList?

[@jeegs6up]

Agreed. Also max heap should take nlog(n). Binary search on a double LL though could yield you log(n).

[@akhilrajput6218]

@@jeegs6up I think a skip list can do the job, its a variation of Linked lists with O(logn) search/insert/delete capabilities, but it requires twice the space, but still O(n) in theory!

[@komalbhalge5119]

Content and explanation are easy to understand but if possible please try to increase the audio, it is very low.

[@EmadMokhtar]

Ask many people mentioned, you have the skills to make a simple & good explanation to the solution. Well done 👍

[@sharatchandra9198]

Extraordinary explanation. No where I found such a great interview and subject oriented explanation. thanks a ton

[@viditmathur8437]

How is the insertion in LL of order O(1) if we want to keep it sorted it will be O(N) no?

[@MayankKumar-qt1cu]

Heap is best suited here !

[@MClements999]

inserts with a binary search will match the heap at O(log(n)). That being said, as long as you are only polling the max or min (one trade at a time), heaps are probably best suited for the problem.

[@yaninghuang8971]

@@MClements999 How can you do binary search on a linkedlist? Linkedlist is not designed for log(n) sorting right? My 2 cents are O(n) is probably ok (so LL is ok) because we are not going to see crazy number of orders for one stock at one time and we are not really that sensitive to the latency (reliability matters) in the world of trading when users buy a stock.

[@MClements999]

@@yaninghuang8971 My mistake (was considering an arraylist). You're right about the time complexity being O(n) on a pure linked list.

[@huigao3371]

LL+hash map can have O(1)

[@ankk98]

Please make a video on system design for Zoom like video conference system

[@tubex1300]

Your system design really gave the clear explain with the use of the data structures

[@chetan_bommu]

Narendra, Content is Awesome but the quality of the audio is too low. Even on full volume on MacBook pro, It feels low. Please look into this issue for the next videos.

[@TechDummiesNarendraL]

I will try to fixit, thanks 🙂

[@anushree3744]

yes, volume is too low.

[@rechinraj111]

@@TechDummiesNarendraL even in ear phone it was low.

[@harshpatel105]

@Chetan Bommu Was it necessary to mention macbook pro? It is common sense, it will be low on all devices. Apple fanboy detected XD

[@MrNipunJoshi]

​@@harshpatel105 He may have meant to reference the specs of the audio system to better qualify his message as audio on other devices may be lower inherently (typically windows based laptops). We can avoid being mean, the world has a lot to deal with right now :)

[@manishmahajan6094]

Wow, Amazing. I am learning so much here

[@sharatchandra9198]

You are extremely good at this, you have helped me so much in understand the concepts in depth, I thank you for all the help

[@GargeeSharma]

Volume is very low and can barely hear even with 100% volume and then Ads in between get too loud

[@weddypoppa5796]

this is really good!! helps me understand the end to end architecture design of an stock exchange tool

[@mudassarh4268]

as usual, your stuff is always gold !!! Looking forward to such more videos !!!

[@venkatapavankumarsannisett2259]

Skip list would be good for the matching engine This way you can insert order using o(logn) assuming used power law probability for adding levels which can make search easier You get the dynamism of Linkedlist which can make insertions and deletions faster also implement fairness. With array you might have to resize the arrays when the orderbook is growing. Always play around with the head of orders (like heap).

[@bakulbhaikothari5435]

Remove and insert for partially traded is not advisable - imagine having multiple orders of 9USD - you will push the partial order at the 9USD queue instead of keeping it at first position

[@Phillip.K.J]

priceless your video has helped me a ton. wish you can keep uploading vids like this

[@vinayng9214]

Instead of showing the complete system design all at once, i think it will be more interesting and engaging if you can go block by block not just in explaining but in drawing the same too..

[@805bluebell]

Very crisp and clear explanation

[@snehakavinkar2240]

Great explanation! I have a few questions though 1. why do we need separate queues for different companies? 2. If queues are separate for companies then why common matching engine for all? 3. Where the orders history will get stored?In Cassandra? Will it generate new sequence ID while fetching orders history too? Thanks in advance!

[@nayeemzen3193]

You can scale each queue independently depending on volume

[@harshseth3231]

For GOOGLE stock we would have a separate active and passive engines, so there is a separate matching engine for all the queues.

[@shashankshekhar8970]

Separate queue are there to handle scale better, A TSLA queue will have nothing to do with GOOGL queue and thus they can be treated as totally sepaarte entitites. Also regarding the order history, once the order is executed it can not be changed, so it becomes immutable and since we are gonna have a heavy load of writes Cassandra becomes suitable for this use case

[@thankskrishna]

1. because we expect 100k order requests per second and in order to scale them, we need separate queues for each company to distribute the load 2. The common matching engine is not compulsory, you can have multiple instances of VMs too. 3. I think we are storing it in Cassandra because offers users “blazingly fast writes,” and the speed or accuracy is unaffected by large volumes of data.

[@ps2controllerreview]

Thank you for the explanation. This was very concise and clear

[@e431215]

Great video, I feel (apple,google,tesla) Kafka/queue between router will defeat the purpose of Cache. Since we already have primary and secondary matching engine, request should directly hit primary. Than it should be placed to Kafka.

[@namanbhayani1016]

Amazing content!! Really helpful to understand several aspects of a large system.

[@chetan7kk]

What happens if Passive Matching Engine is slightly faster and consumes more messages from Kafka, Keeping in-memory state in sync can be really difficult.

[@vasanthanchinnasamy]

Oh shit. Now I'm having same doubt.

[@ethanjyx]

same question - we did not talk about how to keep the matching engine in sync here

[@sandeeptadepalli5963]

@ Tech Dummies Narendra L, I am sensing a bug in the design please correct me, Inorder for the passive to takeover on failure it should be in the same state as the active which in the begining it can, But after a failure how will a recovered pasive matching engine get back to the same satate as active engine for future failures. Maintaining two systems in Sync is very unlikely Are there any systems in place. ?

[@chandradinata23]

i really like your video man, really helpful

[@amitjain3933]

Its very deep and fantastic way to explain the system. Can you please provide us system design of brokerage application like zerodha, icici direct etc. Actually it takes the order to customer and send to either NSE/BSE. How the real time price would be taken from exchange

[@micklemoon]

The passive matching engine instead of consuming from the queue can be a replica of the active engine. This will help in two ways: 1. We want each order to consumed and processed exactly once, and with passive engine the problem comes out to be at least once per engine instance, which IMO would be hard to achieve. 2. Also, if both active and passive consume from the queue there can be differences in processing leading to inconsistent processing due to concurrency concerns. A replica would simply ensure storing the same state as active one.

[@kobew1351]

i was also wondering about this. if both are actively consuming the events, the synchronization between the two can be challenging (e.g. what if the passive engine processes the events faster than active one? then since no db write is done, those events are lost after failover). However if using as a replica, the passive replica will need to know when to start consuming (as a queue consumer, consumers have to actively poll for new messages). So a periodical check (am i the active engine now?) will be needed.

[@prashanthdebbadwar2470]

Great explanation! What happens when we receive a cancellation request for a buy request which is in maybe risk management or price matching status?

[@sandeeptadepalli5963]

Given this design if I want to implement an Cancellation, As the amount of traffic we get in the cancellation is not high, I would implement a cancellation system post the matching engine, The system stores an Order Id in a map, for every match we get it checks if any of the order is requested for cancellation then it cancels the match, and inserted back into the queue, if there is no element in teh set then then I will get a lock for it in the map and compelte the transaction once complete I will release the lock, but the problem with this is its not instantaneous

[@boombasach]

Very helpful and most importantly insightful. Couple of points : Choice of Kafka was good but was not clear if we will maintain Partition/Stock. Also I like your concept of serailisability perhaps we can eloboreate how often the snapshots will be taken. Keep up the good work.

[@fishlinghuL]

Hi, it is a great tutorial! Thanks. I have one question regarding the order matching algorithm. You mentioned that we are trying to match the buy order with high price with the sell order with low price, but this algorithm is not optimizing for completing the most number of orders. For example, we have (buy $10/5 shares), (buy $8/5 shares), (sell $10/5 shares), (sell $8/5 shares). All orders can be fulfilled if we match $10 to $10 and $8 to $8, but your algorithm will match (buy $10/5 shares) to (sell $8/5 shares), and the rest of orders cannot be fulfilled. Is this how the matching engine works in reality? Sorry if I am missing some context here. Thanks again for the video and answering questions :)

[@sandeeptadepalli5963]

I think the sequence in which the requests are placed also need to be honured. Lets say I have a big bulk order of ( buy $10/10000 shares) and some other buy/sell requests normally. In your suggested approach this would rarely be fullfilled as in a high volume trading senarios we can assume there will be always some orders that can be matched with exact match. even though I have placed the request to buy at 10USD a buy at 11 USD might happen before me which is not acceptable.

[@mahdihosseinali7492]

The algorithm is plain wrong. If this was the case, you could put buy orders of $1 million/share and get the lowest price. It's mostly first come first serve

[@rkakkar007]

1. If active and passive matching engine both are working/matching orders at the same time and have no idea of the master, both will require access to in-mem DB for reads & writes, which goes against the point of only 1 of them being active. 2. Same scenario, both engines are active, let's say one of the engine is slower in accepting requests from the queue, there can be an order mismatch, where one engine matches order differently than other for the same price. This will lead to inconsistent data I believe master-slave approach will be better here, where events are propogated to the slave in a timely fashion, the downside will be failure of orders if the master fails and will continue to fail until the slave gets active

[@VarunBansal7]

have questions around the same. how is active and passive matching engine staying in sync. both are getting data from the queue and maintaining and processing the buy and sell list independently. if active fails, we cannot be sure passive will have the same state as active and can take over

[@ameyasawant5663]

If we shard based on stock then 'hot' stocks wil have higher load while stocks which don't have much activity will have wasted resources.

[@kiratsaluja3522]

can we do it based on order id?

[@shashankshekhar8970]

@@kiratsaluja3522 Sharding based on order id will have all the traffic directed to the shards handling recent orders, while the older ones will be sitting idle. I agree with Ameya that it will sharding on stocks will create hot partitions but that is still the best option to go since all the orders for a specific stock can be found at one place and thats exactky what our queries would look like

[@tanakonda9864]

If a shard is 'hot' you can do one of two things. Shard the shard or create read replicas of shard and load balance the reads.

[@SakshiJain-bq6gc]

Wouldn't Queue partition by CompanyId in cause hot partitions? Like Google/Tesla stock gets more traded as compare to any random startup who just got public?

[@karana2260]

For forex like binance, they cant store millions of transaction in memory. I think storing top N in mem and keep pulling from disk as and when matching happens/writing bottom layers of mem to disk when new tx comes, is a good strategy too?

[@antoniowong6269]

Agree. And I *think* all orders will have to be persisted to disk / DB first, in case if the node crashes. Order cancellation can be done by maintaining cancellation order in another data structure (hashmap??) When an order is about to be executed, cancellation structure is checked against, and order will be discarded if record is found.

[@Asuraii]

@@antoniowong6269 I Agree, all orders and their executions need to be stored otherwise if both node crashes; picking from the last redis cached like he mentioned is not good enough as you may have lost data within those 10 seconds.I would also do the cancel like you mentioned.

[@kamleshpar9847]

Good explanation , I have one doubt both Active n passive Matching engine will be able to consume the message same time from Queue , If its point to point messaging ?

[@madhu9829]

Great video. Covered almost all topics.

[@nicetomeetugaming7024]

Thanks sir, amazing content!

[@RaviPrakash-vu6hf]

Hi Narendra, Thanks for the explanation, I have a doubt regarding the flow of orders from the queue to the matching engine. 1. Will the matching engine keep on polling orders from the queue to VM, will it be better to introduce event-based polling? 2. A corner case, it is possible that all orders are only SELL orders or only BUY orders, and if we are keeping orders in memory, how long will we keep the order in memory, and will it make sense to limit the order count which would be loaded in memory, because memory is always limited. 3. One Queue and one VM architecture don't seem to be horizontally scalable - If orders are in memory, we can never have more than one VM, will it make sense to push orders to some in-memory DB like Redis and VM would not store any orders in memory and would rather only run the matching algorithm.

[@ankitgupta-ph4nk]

I also wanted to ask the your second question

[@aniketverma7786]

You are the best

[@diabydembo9018]

Beautiful work, Thank you

[@jsdev6744]

Great video! regarding the accumlator sequencer, can you give more insight into how this should be designed? I"m trying to create a scalable ordered id generator

[@lisai1129power]

Question about Matching engine, should it use multi-thread or single thread to handle the data? If multi-thread, locking might be needed and it will affects performance much.

[@Cristianoankit7]

10:22 - How can Linked List have O(1) time complexity for keeping a sorted order. It should be O(n) right?

[@ElvinYX]

True. That should be a mistake. In fact we can't implement order book with just heap because we need to support update of the orders.

[@sachintripathi5742]

Awesome Video. Content is too good. Increase in Video & Audio Quality Can make it better. Thanks For Sharing Narendra.

[@uditagrawal6603]

How will the cancellations be handled in case if order has already passed RMS but not executed yet, could you please clarify?

[@anushree3744]

Please make videos on system design building blocks as well

[@DineshGowda24]

@Tech Dummies Narendra L Amazing explanation, I have a question. Rather than using zookeeper for leader management in FSM of active & passive machining engine, i could use something like Raft right? Where raft maintains the consensus, takes timely snap shot & all the computation is done in leader. If leader goes down some else in the replicate set is elected.

[@dwaijam]

Insertion in Linked List will not be O(1). it will be O(n)

[@utubemanan]

max-min-heap can be used. with O(lg n ) for all heap related operations

[@ashwinsreekumar1297]

@techdummies really enjoy your video. Can you post a video about inventory management system?

[@pratiksarvan]

Hello, content is good. Just one suggestion. I have seen your other videos as well. Don’t explain how a particular system works but explain how we can build similar system. Like you explained in previous videos how Uber, Twitter works. People don’t expect you to explain how these system works in interview. They expect you to know how can you build your own system like this.

[@Possibivity]

I second that.

[@ckthecool]

Great efforts & very well explained. Thanks for sharing your knowledge with us.

[@rogerjin7259]

How to ensure a low latency processing if the design is using a distributed queues (via networking) in middle of trading flow. Shouldn't we have all these process within memory of the match server to eliminate network hops?

[@adammelnyk8696]

The issue I have with the order processing being in memory is that you need to guess what the volume for each is going to be and leave a large buffer in case there is a sudden spike in volume on a particular stock. In the example, if TSLA, GOOG, and AAPL are all on the same server, if any one of them suddenly spikes, and you start running out of memory, you need to spin up a separate server and change your sharding / routing strategy on the fly for where the stocks are being processed. Either that or you have one processor per stock and hope you have enough memory.

[@actiondangerousvideosactio8369]

Awesome one doubt So as u mentioned that at a time both active and passive matching machine will work and in case of active machine failure the zookeeper will give the charge to passive engine, but will it copy the lists record from active engine one OR it will continue processing with its own lists of sell and buy In the 2nd way of continuing on its own inmemory data it will make system unreliable

[@samar19925]

fix the sound plz overall 100% useful content

[@shubhamdas1783]

Will you have only one instance of Accumulator Sequence or multiple, if we have heavy load we may need to have multiple servers . then in that case there could be duplicate id right ?

[@elachichai]

This is very good. But how do/did you learn these? Books, Whitepapers, Lectures, Mostly Work?

[@franciscofreire4608]

I would like know too

[@AdamYang-707]

shard by stock name in RDBMS, partition by stock name in the first mq. How do you trade off between hot spot issue with access latency? latency >> hot spot(could cause availability issue)

[@saurabhahuja6707]

Thanks sir for your valuable information.Please create design Tiktok

[@sumitkumar03]

Thanks Narendra. Very helpful video.Well explained.

[@GauranshNagarey]

Nice video and other videos are also great! keep going.

[@HktDarren]

It's a really good video, but in this digraph when does it sends the data to the main stock exchange (NASDAQ, NYSE)?

[@SzTz100]

Brilliant

[@9430057539]

which software you use for the diagram?

[@arpanchandrashekhar5539]

Can you make a video for distributed task scheduler?

[@sahnawaz]

great design. any idea how do we handle when payment fails?

[@gurjarc1]

at 10:25 , in the video, you say LL is o (1). i guess it is o(n). as when inserting you need to search and insert in the right place. So insert, delete will implicitely mean a search. so in my opinion Linked List is O(n)

[@sanjudhanriya3482]

Can we add an order prediction engine somewhere in this architecture? If we can, then where would that be. What technology we can use for order prediction and measure it’s accuracy?

[@Arupchakraborty2004]

Thanks much for sharing it , it is very informative session. Although I believe , it is very difficult to present all these information at interview at real time. As per the interview process, it is good to start with asking good questions for any system design and clarify it. Please also share some light into your videos with this aspects. If you can also share some tips and tricks to remember things that would be great as well. Thanks again for your awesome work, you are like a guru in system design.

[@loknath9]

Content is good. Most of the things are covered, except one point which I feel is also important. How the response(Txn completed/Partially fulfilled etc...) is propagated back to the user? Considering the Buy/Sell request API call is async.

[@arjunsharma8938]

That can piggyback on payment system. He did cover that payment system will deduct money from wallet according to transaction result. Implied is that details of transaction are passed to him.

[@nicetomeetugaming7024]

Web socket.

[@RahulBansal14]

When sending the Tick infromation from servers to clients. You mentioned at 34:50 that real exchanges maintain fixed number of connections per server and instead of looping through all the connections they broadcast. Can you explain in detail what do you mean by broadcast. How is brodcast implemented? Thanks

[@kunzhou5159]

I think broadcast here is at the level of a switch or a router. High frequency trading happens on machines with direct connections to the exchanges and likely they are on the same switch or network topology.

[@chezzyfries]

He means broadcast in terms of a multicast. The router just sends the packets to all its connections and that saves time

[@cagarwal]

How do we support cancel order? I understand we can't cancel once the order is matched. What about before it is matched?

[@theteamamericashow2575]

Amazing

[@Malpekar-mo4wb]

Awesome video, But voice recording low.

[@chandshantanu]

Thanks a lot for this video

[@deepakgururani4939]

Which tool is being used in the video for graphic/diagrams? Thanks in advance.

[@ZhuYang]

Which tool you are using to draw the diagram? Thanks.

[@karana2260]

awesome, If possible - can you done one on slack please?

[@NikashKumar]

low audio, :(

[@subodhnilose3100]

Great video & really like your channel. I have a couple of questions & wonder if you could point me to resources to get deeper understanding: 1. When limit orders have price difference $10 buy & $9 sell. What happens with the difference? How does it reflect into the stock price? 2. How are order with market price matched? Do they get into the same queue or matched with market sell instead of limit? It will have its own queue or list or heap rather than what you described for limit orders? 3. Finally, how does the market price get determined based on the limit orders e.g. when buyers and sellers are specifying price. I am sure it's much complicated and please feel free to point me to any specific resource.

[@nicetomeetugaming7024]

3. law of demand and supply.

[@nicetomeetugaming7024]

3. It's not really difficult, let's say for ex. some one posted a limit order at $2 price for 1quantity. If market order is placed for selling 1quantity then the current price of the stock will be $2.

[@nicetomeetugaming7024]

1. The difference is called spread. Market makers profit from the difference between bid and ask.

[@taofeng5769]

If the Buy order($10 / 5 stocks) matches with the Sell order($8 / 5 stocks), does the stock exchange earn that $2 price difference in this case?

[@nicetomeetugaming7024]

Stock exchange charge fees for every trade that's performed on their platform.

[@xiongwe]

I am wondering that as well, but I bet this detail is not important in real system design interview.

[@ameynaik1755]

Do we need some kind of transactions?

[@lapujain]

Hi Naren,another awesome video. Thank you. I am stuck at one Active/Passive point and not able to think what shall we do in case if the buy order is placed before the system is down and in between when the system is getting up again, user placed a cancel order for the same. How can we handle this scenario.

Thanks for the video but as all say voice volume is too low. you need to target -12db when publishing videos. thanks again

[@gandharvadeshpande3926]

How is insertion in this case O(1), i understand insertion when you know the position is O(1) but tomorrow if a seller with a price which isn't the smallest or largest comes, you would need to traverse to check where to insert

[@sandip3591]

@Tech Dummies Narendra L: Could you please explain how in actual protocol's like FIX protocol work in these kind of systems. How the information related to trade being placed is encoded using this protocol at user, sent to exchange decoded at exchange, matched the trade order and again encoded the confirmation of order if its executed/pending/rejected with the related data sent to traders terminal.

[@vikramsah6776]

How did you do the required research? I am trying to implement something on similar terms. Could anyone please suggest some resources?

[@bakulbhaikothari5435]

How is insertion in LL an O(1)? You need to keep sorting - that means a worst case complexity of O(n)

[@gmmkeshav]

what is done for pre-market orders

[@AkashJadhavIT]

hi Sir please make a series on Object Oriented System Design.

[@yashchandraverma3131]

Good Information...but sound is very low.

[@SolidSystemDesign]

Great stuff .. One question : how will the system handle order cancellation ?

[@MidgarZolom]

Does anyone know which drawing / whiteboarding site this is?

[@MuthuKumar-ub1mp]

Great video, audio is very low

[@Hacks00145]

Very nice video, just one suggestion can you be work on better audio

[@akshitbansal5651]

thanks for the video. for better videos, please buy a good mic

[@alokuttamshukla]

Audio is very low. Is it just me?

[@karthiksitharam]

It is low. I maxed out on all devices :D

[@rplusgdj]

Not sure, it works fine for me with ear phones.

[@TechDummiesNarendraL]

@alok don't have studio setup as such, staying in cramped up single room. Amazon not delivering mic. Corona problems.

[@alokuttamshukla]

@@TechDummiesNarendraL No worries. We understand. Just that this had particularly low. Been a regular follower of your content.

[@maxsjohn]

Hi, Thanks so much for the video....The audio volume is low so if I keep to max and view and if an Ads pops out it will MAX out volume in between due to Ads..

[@repetitionsidestepmiki3125]

Can anyone tell me how to add a function of stoping trading when get to the tracsanction upper limit?

[@hemantyadav5034]

I would rather suggest to use the 2 unordered_maps , one for seller and one for buyer. You can keep increment the decrement the order quantity if the price is matching for the buyer and seller. As our first preference to match is the price and then quantity, we will use price as the key and quantity as the value. All lookup and adding new order(buy/sell) will be O(1).