Low Latency Unix/Linux

Most low latency/high frequency programming jobs (based on job specs) appear to be implemented on unix platforms. In a lot of the specs they make particular request for people with “low latency linux” type of experience.

Assuming this does not mean a real-time linux OS, could people give me help with what this could be referring to? I know you can set CPU affinity to threads, but I am assuming they are asking for much more to it than that.

Kernel tuning? (although I heard manufacturers like solarflare produce kernel bypass network cards anyway)?

What about DMA or possibly shared memory between processes? If people could give me brief ideas I can go and do the research on google.

(This question will probably require somebody familiar with High Frequency Trading)

I’ve done a fair amount of work supporting HFT groups in IB and Hedge Fund settings. I’m going to answer from the sysadmin view, but some of this is applicable to programming in such environments as well.

There are a couple of things an employer is usually looking for when they refer to “Low Latency” support. Some of these are “raw speed” questions (do you know what type of 10g card to buy, and what slot to put it in?), but more of them are about the ways in which a High Frequency Trading environment differs from a traditional Unix environment. Some examples:

Unix is traditionally tuned to support running a large number of processes without starving any of them for resources, but in an HFT environment, you are likely to want to run one application with an absolute minimum of overhead for context switching, and so on. As a classic small example, turning on hyperthreading on an Intel CPU allows more processes to run at once — but has a significant performance impact on the speed at which each individual process is executed. As a programmer, you’re likewise going to have to look at the cost of abstractions like threading and RPC, and figure out where a more monolithic solution — while less clean — will avoid overhead.
TCP/IP is typically tuned to prevent connection drops and make efficient use of the bandwidth available. If your goal is to get the lowest latency possible out of a very fast link — instead of to get the highest bandwidth possible out of a more constrained link — you’re going to want to adjust the tuning of the network stack. From a programming side, you’ll likewise going to want to look at the available socket options, and figure out which ones have defaults more tuned for bandwidth and reliability than for reducing latency.
As with networking, so with storage — you’re going to want to know how to tell a storage performance problem from an application problem, and learn what patterns of I/O usage are least likely to interfere with your program’s performance (as an example, learn where the complexity of using asynchronous IO can pay off for you, and what the downsides are).
Finally, and more painfully: we Unix admins want as much information on the state of the environments we monitor as possible, so we like to run tools like SNMP agents, active monitoring tools like Nagios, and data gathering tools like sar(1). In an environment where context switches need to be absolutely minimized and use of disk and network IO tightly controlled, though, we have to find the right tradeoff between the expense of monitoring and the bare-metal performance of the boxes monitored. Similarly, what techniques are you using that make coding easier but are costing you performance?

Finally, there are other things that just come with time; tricks and details that you learn with experience. But these are more specialized (when do I use epoll? why do two models of HP server with theoretically identical PCIe controllers perform so differently?), more tied to whatever your specific shop is using, and more likely to change from one year to another.

In addition to the excellent hardware/setup tuning answer from @jimwise, “low latency linux” is implying:

C++ for reasons of determinism (no surprise delay while GC kicks in), access to low-level facilities (I/O, signals), language power (full use of TMP and STL, type safety).
prefer speed-over-memory: >512 Gb of RAM is common; databases are in-memory, cached up-front, or exotic NoSQL products.
algorithm choice: as-fast-as-possible versus sane/understandable/extensible, e.g. lock-free, multiple bit arrays instead of array-of-objects-with-bool-properties.
full use of OS facilities such as Shared Memory between processes on different cores.
secure. HFT software is usually co-located in an Stock Exchange so malware possibilities are unacceptable.

Many of these techniques have overlap with games development which is one reason why the financial software industry absorbs any recently-redundant games programmers (at least until they pay their rent arrears).

The underlying need is to be able to listen to a very high bandwidth stream of market data such as security (stocks, commodities, fx) prices and then make a very fast buy/sell/do-nothing decision based on the security, the price and current holdings.

Of course, this can all go spectacularly wrong, too.

So i’ll elaborate on the bit arrays point. Let’s say we have a High Frequency Trading system that operates on a long list of Orders (Buy 5k IBM, Sell 10k DELL, etc). Let’s say we need to quickly determine if all of the orders are filled, so that we can move onto the next task. In traditional OO programming, this is going to look like:

class Order {
  bool _isFilled;
  ...
public:
  inline bool isFilled() const { return _isFilled; }
};

std::vector<Order> orders;
bool needToFillMore = std::any_of(orders.begin(), orders.end(), 
  [](const Order & o) { return !o.isFilled(); } );

the algorithmic complexity of this code going to be O(N) as it is a linear scan. Let’s take a look at the performance profile in terms of memory accesses: each iteration of the loop inside std::any_of() is going to call o.isFilled(), which is inlined, so becomes a memory access of _isFilled, 1 byte (or 4 dependending on your architecture, compiler and compiler settings) in an object of let’s say 128 bytes total. So we’re accessing 1 byte in every 128 bytes. When we read the 1 byte, presuming worst-case, we’ll get a CPU data cache miss. This’ll cause a read request to RAM which reads an entire line from RAM (see here for more info) just to read out 8 bits. So the memory access profile is proportional to N.

Compare this with:

const size_t ELEMS = MAX_ORDERS / sizeof (int);
unsigned int ordersFilled[ELEMS];

bool needToFillMore = std::any_of(ordersFilled, &ordersFilled[ELEMS+1],
   [](int packedFilledOrders) { return !(packedOrders == 0xFFFFFFFF); }

the memory access profile of this, assuming worst-case again, is ELEMS divided by the width of a RAM line (varies – could be dual-channel or triple-channel, etc).

So, in effect, we’re optimising algorithms for memory access patterns. No amount of RAM will help – it’s the CPU data cache size that causes this need.

Does this help?

There’s an excellent CPPCon talk all about low-latency programming (for HFT) on YouTube: https://www.youtube.com/watch?v=NH1Tta7purM

Since I had put not one or two high frequency software in production I would say the most important things:

Hardware configuration and system administrators together with networking engineers do NOT define good outcome of number of orders processed by trading system , but they can downgrade it big time if they don’t know basics outlined above.
The only person who actually makes the system to do high frequency trading is a computer scientist who puts together the code in c++

Among the knowledge used is

A. Compare And Swap operations.
- how CAS is used in processor and how computer supports it to be used in so called No-Locking structure processing. Or Lock-free processing.
  I will not go into writing a whole book here. In brief GNU compiler and Microsoft compiler do support direct use of CAS instructions. It allows your code to have “No.Wair” while extracting element from queue or putting a new one into the queue.
The talented scientist will use more. He should find in recent new “patterns” one that appeared in Java first. Called DISRUPTOR pattern. Fold in LMAX exchange in Europe explained to the high frequency community that thread-based utilization in modern processors would loose processing time on memory cache release by CPU if the daya queue is not aligned with the size of modern cpu cache= 64

So for that readon they made public a java code that allows multi-threading process to use hardware CPU cache correctly without conflict resolutions. And good computer scientist HAVE to find that pattern was already ported to c++ or do porting himself.

This is a proficiency way beyond any admin configuration. This is in real heart of high frequency today.
The computer science guy HAS to write a lot of C++ code not only to help QA people. But to also
- validate in the traders face proven achieved speed
- condemn used different old technologies and expose them with his own code to show they fail to produce good results
- write hos own multi-threading communication c++ code based on proven pupe/ select kernel speed instead of using again old technologies. I will give u example – modern tcp library is ICE. And folks who did it are bright. But their priorities were in the field of compativility with many languages. So. You can do better in c++. So search for highest performance exaples based on ASYNCHRONOUS select- call. And do not go for multiple consumers multiple producers – not for HF.
  And you will be amazed to find that pipe is used ONLY FOR kernel notification of arrived message.
  You can put the 64-bit message number there – but for content you go to you no-locking CAS queue. Triggered by asynchronous kernel select() call.
- moreover. Learn about assigning with c++ thread affinity to your thread that does piping/ queuing of your messages. That thread should have core affinity. Nobody else should use the same CPU core number.
- and so on.

As you can see – high frequency is a DEVELOPING FIELD. You can not be just a C++ programmer to succeed.

And when I say to succeed I mean that the hedge fund you would work for WILL recognize tour efforts in yearly compensation beyond the numbers people and recruiters talking about.

The times of simple constructor / destructor FAQ are gone forever.and c++…itself migrated with new compilers to relieve you from memory management and to enforce no-inheritence of big depth in classes. Waste of time. Code reusing paradigm changed . It is not just about how many classes you made in polymorph. It is about straight confirmed time performance of code you can reuse.

So it’s your choice to go into learning curve there, or not. It will never hit a stop sign.

Filed under: softwareengineering - @ 23:50

Thẻ: c++, latency, linux, performance

Thiết kế website giá rẻ

Danh mục

Low Latency Unix/Linux