Performance Engineering of Stock Exchange
(Disclaimer : this is written by me, sometime back I had sent this in a mail, but many of my friends thought this is just a Forwarded mail & didn't read it :D )
Again this about a guest lecture I had attended way back on 30-10-2006 in IIT Bombay during one of my courses. It was by Dr. Rajesh Mansharamani, who is Principal Consultant & Head,
Performance Engineering Research Centre, TRDDC (Tata Research, Design
and Development Centre).
(Disclaimer: all the information in this post was written according data on 30th oct. 2006. Specifically many numbers may be outdated now. Also I may have mistakenly written something while recalling the lecture.)
First half part of the post is very small intro. to the domain knowledge & then the technical stuff follows.
Title of the talk was Performance Engineering of Stock Exchange of India:
10,000 orders/day to 10,000 orders/second.
This lecture was really nice one. Speaker talked about the the practical application. He explained about the evolution of one of the very vital Software(actually this can be a very narrow term. Rather I can say vital Automated System or something...as it included evrything from s/w, processor, in-memory database, to network issues & many more....).
It was about Bombay Stock Exchange i.e. BSE's software system.
Its obivously very crucial....as BSE is world's 3rd largest Capital Market & Largest Stock Market....(can't recall exact Commerce terms..)
turnover in BSE is Rs. 8000 crore/day. means Rs. 24crore / minute... so now u can imagin how important is the s/w running for such system..
He started of with introduction to Stock Market terms..
Buy Order Book - contains orders from the buyers..entries are no. of shares they want to buy & MAXIMUM price at which they want o buy.
Sell Order Book - contains offers from sellers..entries - no. of shares offered & price
(I think this was in the case of normal stocks... after this comes Concept of DERIVATIVES which is different from this )
Derivatives - its basically a estimation of future value & signing a contract in advance..
means lets say I am (a buyer/customer) signing a FUTURE CONTRACT for buying 100 shares of a COMPANY "X" in JAN 2007 with price Rs 200 per share....
these derivatives are declared by BSE 2-3 months in advance..so any one interested in buying can then register for this, by paying some amount (like token amount which we pay while renting/ buying home).. e.g. Rs. 1500 for 100 share.
Suppose in JAN 2007 - share price goes to Rs. 300, but as my Contract signed for Rs. 200, i will get it at Rs 200. So my profit is Rs. 100 per share.. AND if share price goes down to Rs. 150, so now as buyer I am getting loss of Rs. 50..so instead of this I just cancel buying this stock. PENAULTY here is the TOKEN amount... I will not get that back...
(here many interesting financial concepts are related....will talk on this more after some time, I wanna get more info. abt that..)
Again there are some more terms about Derivatives..
Call, put ~ similar to our http calls...
option - do u wanna keep this deal or wanna sell to someone...
holder , writer - its something about ownership of share..
Strike Value - value at the time of contract...
Spot Value - peak value..
That's the end of financial topics for a while.. People might have got bored by reading all this. Thank you for your patiences. ------------------------------
when BSE started of with s/w in 1994, there expectation was 10,000 trades per day & 50,000 transaction / day (it includes inquiry etc..)
& now they handle3 million trade/day.. 600 transactions per second..
see how much big these figures are.. & all these affect flow of MONEY....so S/W MUST (remember MUST) work correctly , efficiently..
They are using Stratus Fault Tolerant CPU (they were using 2 CPUs at that time, now using 6 CPUs...they divided them in pair of 2.. each pair is doing some specilized task such as STOCK , CAPITAL or....something.. )
They use Appletree in-memory database. They DONT use HARD disks to store the transaction data. As a day's transaction in all don't take much space as such.
Now hav a look at the problems BSE had with this s/w...And how they evolved...
PROBLEM1 - in 1994-97 evrything was going smoothly..so nobody really cared about s/w maintence or future growth.
in 1997 the s/w started degrading with QUEUE sizes at individual modules in the system increased upto 30,000! that means people were getting very high RESPONE TIME (generally which we can see nowadays also in cyber cafes in small cities)
( & in those days memory size supported were 32k. so Project Managers were really praying that this many people should not come at a time.)
SOLUTION 1 - they found one module which was sending reports to some Managers (dont recall who they are exactly, but may of BSE and related authorities.) AND INTERESTING THING was - It was SENDING REPORT for EVERY TRANSACTION.
so sending that report involved WRITING SOME INDEX IN THE DISK & doing some PROCESSING etc. so thing was 1% (manager ) activities were delaying 99 % (customer) activities.
So DECISION they took was instead of sending frequent reports, send a daily report at the end of the DAY.This helped in REDUCING that WRITING 8 indices to 4 indices (don't ask me why this is so ? it was reporting activity's internal task)
so this solution really worked. Performance increased DRASTICALLY. & then people waked up and decided to work for future needs.
(MORALE : while developing S/W, understand importance of BUSINESS NEEDS...& try to prioritize them..)
while designing ARCHITECTURE they followed approach - dont try for efficient algo.s in CODING only...instead KEEP THE GOAL of PERFORMANCE from the DESIGN itself....while ANALYSING BUSINESS NEEDS, while DESIGNING ARCHITECTURE TAKE CARE of PERFORMANCE ENGG....
BENCHMARKING PROCESS -
while testing the product, they used to start testing in the night at 10.30 upto 5 am...they were trying to simulate the WHOLE DAY...
(BSE scenario ---> it starts at 9/10 am closes 4/5 pm... & LOAD is HIGH in starting & ending half hours... for remaining day its less)
so instead of wasting so much time in simulating whole day, they decided to manage for only PEAK VALUES of LOAD....this implicitly takes care of low load which is present throughout the day...
(MORALE: while doing some work, there exists shortcuts which DO NOT involve RISK at all..!)
BROADCAST -
what we generally see on TV - share prices are shown continously throughout the day.
so BSE provides these agencies with values of stock.
previously they used to send all the stock prices at rate 10 or 100 /sec. if we take simple example of human eye which have capability of 10 images /sec , then how somebody can see 10s of prices getting updates per second ?
So BSE decreased rate of broadcast. all they noticed that - top 30 companies are involved 80% of TOTAL TRANSACTIONS, so send prices of these IMPORTANT stocks & frequently value changing STOCKs more frequntly than other companies.
so here came PRIORITIZED treatment to COMPANY data broadcast..
PROBLEM 2 - LEGACY S/W MAINTENCE...
they got troubled by some STRANGE thing because of which RESPONSE time significantly increased . so transactions failed..
so they tried to find out the cause of this slow speed .
& what was it ? GUESS. hint : it was a unnecssory overhead.
SOLUTION 2 - DEBUG STATEMENTS which were getting printed on console, (we PROGRAMMERs have habit of DEBUGGING by PRINT stmt.)
so becuase of such carelessness, there was big loss in share market.
(MORALE - ALWAYS check out for such small-small things which may cause BIG harm to you in future.)
with advent of new techonlogies they moved to MULTITHREADING at user level..
PROBLEM 3 - for sending data on networks the existing (at that it was something 16/ 64kbps... ) n/w was not so adaquate. but how to increase the capacity ? as BSE will not provide money for this.& no customers as well will upgrade their lines by investing some money.
SOLUTION - use some compression.
some guy from Pune developed compression technique customized to this application. but soon it failed, as packet structure always get changed drastically.
so instead they now went for Lempel Ziv Oberhumer (LZO) compression technique.
PROBLEM4 - PROBLEM 3 did not end ---
they compressed the packets. but they were sending it over TDMA.
so actual goal should also be to minimize the no. of TDMA frames used to send these packets.
now problem is u hav to fit these packets with heterogeneous sizes in frames, so as to minimize no. of frames.
SOLUTION 4 - its BEAN - PACKING problem which NP COMPLETE (we cant find answer in polynomial time...) so choose one optimal solution - their heuristic was Largest packet first..
PIPELINING - thoughput depends only on BOTTLENECK node / module in pipe...
so they tried to FINE TUNE BOTTLENECK modules...
NOW from hereafter comes much more TECHNICAL rather MATHEMATICAL stuff...
for the queues in the systems they came up with equations for response time etc.. (like what we did in that subject..)
herein its totally about queues & their performance. skipping that mathematical part.
-------------------------------------------------------------
They divided database on no. of SERVERS for parallel work...
only limitation becuase of this was ---> while calling for derivative contract, ppl can't have stocks from 2 different servers in one CONTRACT; but this doesn't matter, as BSE itself announces CONTRACTS.
There are some dedicated lines between BSE & stock brokers.(there is whole business story behind this as well..)
Now their goal is to support 10,000 transcations per second in 2015..
so they did SHANGHAI stock market case study.
its supporting big market. Architecture of that is really superb !
data structures that can be used in each of the submodules according to computing need -
heap - but can't find top 3/5 at a time.
binary search trees.
AVL / RED BLACK tree
message queues - for messaging between modules, uses FLUSH MODEL... rate of flush to disk... (like "sync" command)
PROBLEM 5 - HETEROGENIETY
as broker firms are using some third party s/w. (& also usual examples heterogeneity(nw/ etc.) that's always present in this computer world.)
they faced a problem when some firm always used to get TRANSACTION FAILED error..
generally when N/W connection breaks down..when it comes up, client must establish connection again.
if not then also Customer request for some transaction will be taken, but while giving response back to customer the SYSTEM doesn't know the customer - id BECAUSE there is no connection established between them
SOLUTION - third party s/w vendors didn't considered the case when n/w can break down. they must Re-Establish connection.
(MORALE - while interacting with others, there is always possibility of mismatch...be aware! )
PROBLEM 6 - COMMUNICATION problem for S/W ppl
when reporting some problem to non-techie / non-s/w person , it should be said in way that is understandable to that person.
IF S/W ppl SAY - We want to reduce 4 out of 8 index in database to improve performance, then who will understand ? instead tell them - if we send ONLY daily report to managers then it will help in better performance for all users.
in case of figures - 10,000 transaction per sec....etc...
tell them that we can do all the transactions of the day in 5 minutes..
so in all speaker talked about many of the practical aspects of what we learn in books....
here I skipped with mathematical part which he explained.
in all it was a great experience to have a lecture like this as a part of a course...!
thanks,
-Rahul
It was about Bombay Stock Exchange i.e. BSE's software system.
Its obivously very crucial....as BSE is world's 3rd largest Capital Market & Largest Stock Market....(can't recall exact Commerce terms..)
turnover in BSE is Rs. 8000 crore/day. means Rs. 24crore / minute... so now u can imagin how important is the s/w running for such system..
He started of with introduction to Stock Market terms..
Buy Order Book - contains orders from the buyers..entries are no. of shares they want to buy & MAXIMUM price at which they want o buy.
Sell Order Book - contains offers from sellers..entries - no. of shares offered & price
(I think this was in the case of normal stocks... after this comes Concept of DERIVATIVES which is different from this )
Derivatives - its basically a estimation of future value & signing a contract in advance..
means lets say I am (a buyer/customer) signing a FUTURE CONTRACT for buying 100 shares of a COMPANY "X" in JAN 2007 with price Rs 200 per share....
these derivatives are declared by BSE 2-3 months in advance..so any one interested in buying can then register for this, by paying some amount (like token amount which we pay while renting/ buying home).. e.g. Rs. 1500 for 100 share.
Suppose in JAN 2007 - share price goes to Rs. 300, but as my Contract signed for Rs. 200, i will get it at Rs 200. So my profit is Rs. 100 per share.. AND if share price goes down to Rs. 150, so now as buyer I am getting loss of Rs. 50..so instead of this I just cancel buying this stock. PENAULTY here is the TOKEN amount... I will not get that back...
(here many interesting financial concepts are related....will talk on this more after some time, I wanna get more info. abt that..)
Again there are some more terms about Derivatives..
Call, put ~ similar to our http calls...
option - do u wanna keep this deal or wanna sell to someone...
holder , writer - its something about ownership of share..
Strike Value - value at the time of contract...
Spot Value - peak value..
That's the end of financial topics for a while.. People might have got bored by reading all this. Thank you for your patiences. ------------------------------
when BSE started of with s/w in 1994, there expectation was 10,000 trades per day & 50,000 transaction / day (it includes inquiry etc..)
& now they handle3 million trade/day.. 600 transactions per second..
see how much big these figures are.. & all these affect flow of MONEY....so S/W MUST (remember MUST) work correctly , efficiently..
They are using Stratus Fault Tolerant CPU (they were using 2 CPUs at that time, now using 6 CPUs...they divided them in pair of 2.. each pair is doing some specilized task such as STOCK , CAPITAL or....something.. )
They use Appletree in-memory database. They DONT use HARD disks to store the transaction data. As a day's transaction in all don't take much space as such.
Now hav a look at the problems BSE had with this s/w...And how they evolved...
PROBLEM1 - in 1994-97 evrything was going smoothly..so nobody really cared about s/w maintence or future growth.
in 1997 the s/w started degrading with QUEUE sizes at individual modules in the system increased upto 30,000! that means people were getting very high RESPONE TIME (generally which we can see nowadays also in cyber cafes in small cities)
( & in those days memory size supported were 32k. so Project Managers were really praying that this many people should not come at a time.)
SOLUTION 1 - they found one module which was sending reports to some Managers (dont recall who they are exactly, but may of BSE and related authorities.) AND INTERESTING THING was - It was SENDING REPORT for EVERY TRANSACTION.
so sending that report involved WRITING SOME INDEX IN THE DISK & doing some PROCESSING etc. so thing was 1% (manager ) activities were delaying 99 % (customer) activities.
So DECISION they took was instead of sending frequent reports, send a daily report at the end of the DAY.This helped in REDUCING that WRITING 8 indices to 4 indices (don't ask me why this is so ? it was reporting activity's internal task)
so this solution really worked. Performance increased DRASTICALLY. & then people waked up and decided to work for future needs.
(MORALE : while developing S/W, understand importance of BUSINESS NEEDS...& try to prioritize them..)
while designing ARCHITECTURE they followed approach - dont try for efficient algo.s in CODING only...instead KEEP THE GOAL of PERFORMANCE from the DESIGN itself....while ANALYSING BUSINESS NEEDS, while DESIGNING ARCHITECTURE TAKE CARE of PERFORMANCE ENGG....
BENCHMARKING PROCESS -
while testing the product, they used to start testing in the night at 10.30 upto 5 am...they were trying to simulate the WHOLE DAY...
(BSE scenario ---> it starts at 9/10 am closes 4/5 pm... & LOAD is HIGH in starting & ending half hours... for remaining day its less)
so instead of wasting so much time in simulating whole day, they decided to manage for only PEAK VALUES of LOAD....this implicitly takes care of low load which is present throughout the day...
(MORALE: while doing some work, there exists shortcuts which DO NOT involve RISK at all..!)
BROADCAST -
what we generally see on TV - share prices are shown continously throughout the day.
so BSE provides these agencies with values of stock.
previously they used to send all the stock prices at rate 10 or 100 /sec. if we take simple example of human eye which have capability of 10 images /sec , then how somebody can see 10s of prices getting updates per second ?
So BSE decreased rate of broadcast. all they noticed that - top 30 companies are involved 80% of TOTAL TRANSACTIONS, so send prices of these IMPORTANT stocks & frequently value changing STOCKs more frequntly than other companies.
so here came PRIORITIZED treatment to COMPANY data broadcast..
PROBLEM 2 - LEGACY S/W MAINTENCE...
they got troubled by some STRANGE thing because of which RESPONSE time significantly increased . so transactions failed..
so they tried to find out the cause of this slow speed .
& what was it ? GUESS. hint : it was a unnecssory overhead.
SOLUTION 2 - DEBUG STATEMENTS which were getting printed on console, (we PROGRAMMERs have habit of DEBUGGING by PRINT stmt.)
so becuase of such carelessness, there was big loss in share market.
(MORALE - ALWAYS check out for such small-small things which may cause BIG harm to you in future.)
with advent of new techonlogies they moved to MULTITHREADING at user level..
PROBLEM 3 - for sending data on networks the existing (at that it was something 16/ 64kbps... ) n/w was not so adaquate. but how to increase the capacity ? as BSE will not provide money for this.& no customers as well will upgrade their lines by investing some money.
SOLUTION - use some compression.
some guy from Pune developed compression technique customized to this application. but soon it failed, as packet structure always get changed drastically.
so instead they now went for Lempel Ziv Oberhumer (LZO) compression technique.
PROBLEM4 - PROBLEM 3 did not end ---
they compressed the packets. but they were sending it over TDMA.
so actual goal should also be to minimize the no. of TDMA frames used to send these packets.
now problem is u hav to fit these packets with heterogeneous sizes in frames, so as to minimize no. of frames.
SOLUTION 4 - its BEAN - PACKING problem which NP COMPLETE (we cant find answer in polynomial time...) so choose one optimal solution - their heuristic was Largest packet first..
PIPELINING - thoughput depends only on BOTTLENECK node / module in pipe...
so they tried to FINE TUNE BOTTLENECK modules...
NOW from hereafter comes much more TECHNICAL rather MATHEMATICAL stuff...
for the queues in the systems they came up with equations for response time etc.. (like what we did in that subject..)
herein its totally about queues & their performance. skipping that mathematical part.
------------------------------
They divided database on no. of SERVERS for parallel work...
only limitation becuase of this was ---> while calling for derivative contract, ppl can't have stocks from 2 different servers in one CONTRACT; but this doesn't matter, as BSE itself announces CONTRACTS.
There are some dedicated lines between BSE & stock brokers.(there is whole business story behind this as well..)
Now their goal is to support 10,000 transcations per second in 2015..
so they did SHANGHAI stock market case study.
its supporting big market. Architecture of that is really superb !
data structures that can be used in each of the submodules according to computing need -
heap - but can't find top 3/5 at a time.
binary search trees.
AVL / RED BLACK tree
message queues - for messaging between modules, uses FLUSH MODEL... rate of flush to disk... (like "sync" command)
PROBLEM 5 - HETEROGENIETY
as broker firms are using some third party s/w. (& also usual examples heterogeneity(nw/ etc.) that's always present in this computer world.)
they faced a problem when some firm always used to get TRANSACTION FAILED error..
generally when N/W connection breaks down..when it comes up, client must establish connection again.
if not then also Customer request for some transaction will be taken, but while giving response back to customer the SYSTEM doesn't know the customer - id BECAUSE there is no connection established between them
SOLUTION - third party s/w vendors didn't considered the case when n/w can break down. they must Re-Establish connection.
(MORALE - while interacting with others, there is always possibility of mismatch...be aware! )
PROBLEM 6 - COMMUNICATION problem for S/W ppl
when reporting some problem to non-techie / non-s/w person , it should be said in way that is understandable to that person.
IF S/W ppl SAY - We want to reduce 4 out of 8 index in database to improve performance, then who will understand ? instead tell them - if we send ONLY daily report to managers then it will help in better performance for all users.
in case of figures - 10,000 transaction per sec....etc...
tell them that we can do all the transactions of the day in 5 minutes..
so in all speaker talked about many of the practical aspects of what we learn in books....
here I skipped with mathematical part which he explained.
in all it was a great experience to have a lecture like this as a part of a course...!
thanks,
-Rahul
