On Thu, Nov 21, 2019 at 7:44 AM 'Rob Hodgkinson' via Programming <programm...@jsoftware.com> wrote: > Raul, I fear you have strayed off path again so as you inferred, I provide a > very brief background to this.
I did not know, and I felt I had to convey the ideas you were suggesting to me, to find out what you were talking about. > A large equities exchange can have 5,000 or 10,000 listed securities, futures > & options can inflate that an order of magnitude. > For each security an order book consists of bids and offers, it could be > anywhere from 10 to 200 rows, but each row is a price tier and could consist > of 10 - 1,000 orders in Time priority order. > > Our current platform (MarketGrid) runs one crypto client having an order book > in Leverage trading that is over 1,000 rows deep (not dissimilar to BITMEX). > Visibility is irrelevant, I am not talking the UI (which is a separate > browser based application and communicates via its own memory cache to the > engine), I am talking of the server, the part that does centralised in memory > order matching for the entire market. > > We run the matching engine on Linux servers with anywhere from 32GB to 1+ TB > physical memory, barely touching the disk with all our own housekeeping, > written mostly in C (have done since the 1990’s). > The transaction rates operate from 100,000 orders per second sustained > matching up to 300,000 to 400,000 orders per second on these engines, all fed > via APIs (FIX, ITCH, OUCH, Proprietary etc). > So we are talking single digit microsecond latency round-trip from the > client. Some markets run 24x7, others 9-5, 5-6 days a week, it all varies by > asset class. This is the kind of information I was looking for. That said, I am having trouble reconciling the concept of "single digit microsecond latency round-trip from the client" with traversing linked list structures of that size at that rate and not being able to do the same thing with arrays. (I can see achieving that some of the time -- relatively unloaded systems, and tree structures for quick traversal, but I'm pretty sure you're going to have stalls of some sort sooner or later. This might be manageable, though, if the requirements of the quirks of the algorithm are baked into the agreements about use of the system.) Then again, further down in this message, it seems like you're suggesting that you're not actually traversing the lists. > C kills C++ for this stuff (simply closer to the metal) and likewise both > kill array languages. > I have seen efforts by people to write matching engines in array languages > (eg BITMEX is written in kdb+) and they all fail at performance, barely able > to consume over 1,000 orders per second. > The key reason is the overhead of the array language to process incoming > orders arriving each in a single message upwards of 100,000 orders per second. > > You can append to arrays in array languages at this rate but you can’t > maintain indices for optimal search matching (head of list) and it is > likewise impractical to run shadows of the data. "Head of list" does not sound like "order matching". Maybe a part of a larger system that does order matching, but it seems to me that "head of list" means matching already happened. So, presumably, I'm missing out on some key details. > Cache misses do not impact this matching, it is physical memory and all > orders are stored as contiguous rows in the Orders table as are other tables. > The linked lists provide the only proven way to scale the matching speeds > required. Yeah, ok, but it sounds like you are feeding me contradictory views of the system. So -- again -- presumably I'm missing out on some key details. (And, this means that if I were to attempt to optimize for these cases, I would almost certainly do it wrong.) > So I stand by my comments, which were a constructive suggestion that an > “ordering attribute” in an array could be a mechanism to help an array > language become useful in this space, a I used sorted linked lists in C. > However relying solely on arrays for this kind of performance when receiving > and processing over 100,000 “events” (orders) per second will not do it. Color me... uncertain about what you have been claiming... Thanks, -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
