How to significantly improve Java performance?

Question

The team over at LMAX have a presentation about how they were able to do 100k TPS at less than 1 ms of latency. They have backed up that presentation with a blog, technical paper (PDF) and the source code itself.

Recently, Martin Fowler published an excellent paper on the LMAX architecture and mentions that they are now able to handle six million orders per second and highlights a few of the steps that the team took to go up another order of magnitude in performance.

So far I've explained that the key to the speed of the Business Logic Processor is doing everything sequentially, in-memory. Just doing this (and nothing really stupid) allows developers to write code that can process 10K TPS.

They then found that concentrating on the simple elements of good code could bring this up into the 100K TPS range. This just needs well-factored code and small methods - essentially this allows Hotspot to do a better job of optimizing and for CPUs to be more efficient in caching the code as it's running.

It took a bit more cleverness to go up another order of magnitude. There are several things that the LMAX team found helpful to get there. One was to write custom implementations of the Java collections that were designed to be cache-friendly and careful with garbage.

Another technique to reach that top level of performance is putting attention into performance testing. I've long noticed that people talk a lot about techniques to improve performance, but the one thing that really makes a difference is to test it

Fowler mentioned that there are several things that were found, but he only mentioned a couple.

Are there other architectures, libraries, techniques or "things" that are helpful to reach such levels of performance?

Answer 1

There are all kinds of techniques for high-performance transaction processing and the one in Fowler's article is just one of many at the bleeding edge. Rather than listing a bunch of techniques which may or may not be applicable to anyone's situation, I think it's better to discuss the basic principles and how LMAX addresses a large number of them.

For a high-scale transaction processing system you want to do all of the following as much as possible:

1. Minimize time spent in the slowest storage tiers. From fastest to slowest on a modern server you have: CPU/L1 -> L2 -> L3 -> RAM -> Disk/LAN -> WAN. The jump from even the fastest modern magnetic disk to the slowest RAM is over 1000x for sequential access; random access is even worse.

2. Minimize or eliminate time spent waiting. This means sharing as little state as possible, and, if state must be shared, avoiding explicit locks whenever possible.

3. Spread the workload. CPUs haven't gotten much faster in the past several years, but they have gotten smaller, and 8 cores is pretty common on a server. Beyond that, you can even spread the work over multiple machines, which is Google's approach; the great thing about this is that it scales everything including I/O.

According to Fowler, LMAX takes the following approach to each of these:

1. Keep all state in memory at all times. Most database engines will actually do this anyway, if the entire database can fit in memory, but they don't want to leave anything up to chance, which is understandable on a real-time trading platform. In order to pull this off without adding a ton of risk, they had to build a bunch of lightweight backup and failover infrastructure.

2. Use a lock-free queue ("disruptor") for the stream of input events. Contrast to traditional durable message queues which are definitively not lock free, and in fact usually involve painfully-slow distributed transactions.

3. Not much. LMAX throws this one under the bus on the basis that workloads are interdependent; the outcome of one changes the parameters for the others. This is a critical caveat, and one which Fowler explicitly calls out. They do make some use of concurrency in order to provide failover capabilities, but all of the business logic is processed on a single thread.

LMAX is not the only approach to high-scale OLTP. And although it's quite brilliant in its own right, you do not need to use bleeding-edge techniques in order to pull off that level of performance.

Of all of the principles above, #3 is probably the most important and the most effective, because, frankly, hardware is cheap. If you can properly partition the workload across half a dozen cores and several dozen machines, then the sky's the limit for conventional Parallel Computing techniques. You'd be surprised how much throughput you can pull off with nothing but a bunch of message queues and a round-robin distributor. It's obviously not as efficient as LMAX - actually not even close - but throughput, latency, and cost-effectiveness are separate concerns, and here we're talking specifically about throughput.

If you have the same sort of special needs that LMAX does - in particular, a shared state which corresponds to a business reality as opposed to a hasty design choice - then I'd suggest trying out their component, because I haven't seen much else that's suited to those requirements. But if we're simply talking about high scalability then I'd urge you to do more research into distributed systems, because they are the canonical approach used by most organizations today (Hadoop and related projects, ESB and related architectures, CQRS which Fowler also mentions, and so on).

SSDs are also going to become a game-changer; arguably, they already are. You can now have permanent storage with similar access times to RAM, and although server-grade SSDs are still horribly expensive, they will eventually come down in price once adoption rates grow. It's been researched extensively and the results are pretty mind-boggling and will only get better over time, so the whole "keep everything in memory" concept is a lot less important than it used to be. So once again, I'd try to focus on concurrency whenever possible.

Answer 2

I think the biggest lesson to learn from this is that you need to start with the basics:

• Good algorithms, appropriate data structures, and not doing anything "really stupid"
• Well-factored code
• Performance testing

During performance testing, you profile your code, find the bottlenecks, and fix them one by one.

Too many people jump right to the "fix them one by one" part. They spend a bunch of time writing "custom implementations of the java collections", because they just know that the whole reason their system is slow is because of cache misses. That may be a contributing factor, but if you jump right to tweaking low-level code like that, you're likely to miss the bigger issue of using an ArrayList when you should be using a LinkedList, or that the real reason your system is slow is because your ORM is lazy-loading children of an entity and thus making 400 separate trips to the database for every request.

Answer 3

Won't particularly comment on the LMAX code because I think that is amply descibed, but here are some examples of things I've done that have resulted in significant measurable performance improvements.

As always, these are techniques that should be applied once you know that you have a problem and need to improve performance - otherwise you are likely just to be doing premature optimisation.

• Use the right data structure, and create a custom one if needed - correct data structure design dwarfs the improvement you will ever get from micro-optimisations, so do this first. If your algorithm depends for performance on lots of fast O(1) random access reads, make sure you have a data structure that supports this! It's worth jumping through some hoops to get this right, e.g. finding a way that you can represent your data in an array to exploit very fast O(1) indexed reads.
• CPU is faster than memory access - you can do quite a lot of calculation in the time it takes to make one random memory read if the memory is not in L1/L2 cache. It's usually worth doing a calculation if it saves you a memory read.

• Help the JIT compiler with final - making fields, methods and classes final enables specific optimisations that really help the JIT compiler. Specific examples:

  • The compiler can assume that a final class has no subclasses, so can turn virtual method calls into static method calls
  • The compiler can treat a static final fields as a constant for a nice performance improvement, especially if the constant is then used in calculations that can be computed at compile time.
  • If a field containing a Java object is initialised as final, then the optimiser can eliminate both the null check and virtual method dispatch. Nice.

• Replace collection classes with arrays - this results in less readable code and is trickier to maintain but is almost always faster as it removes a layer of indirection and benefits from lots of nice array-access optimisations. Usually a good idea in inner loops / performance sensitive code after you have identified it as a bottleneck, but avoid otherwise for the sake of readability!

• Use primitives wherever possible - primitives are fundamentally faster than their object-based equivalents. In particular, boxing adds a huge amount of overhead and can cause nasty GC pauses. Don't allow any primitives to be boxed if you care about performance/latency.

• Minimise low-level locking - locks are very expensive at a low level. Find ways to either avoid locking entirely, or lock at a coarse-grained level so that you only need to lock infrequently over large blocks of data and the low-level code can proceed without having to worry at all about locking or concurrency issues.

• Avoid allocating memory - this might actually slow you down overall since JVM garbage collection is incredibly efficient, but is very helpful if you are trying to get to extremely low latency and need to minimise GC pauses. There are special data structures that you can use to avoid allocations - the http://javolution.org/ library in particular is excellent and notable for these.

Answer 4

Other than already stated in an excellent answer from Aaronaught I would like to note that code like that might be quite difficult to develop, understand and debug. "While very efficient... it is very easy to screw up..." as one of their guys mentioned in LMAX blog.

• For a developer used to traditional queries-and-locks, coding for a new approach might feel like riding the wild horse. At least that was my own experience when experimenting with Phaser which concept is mentioned in LMAX technical paper. In that sense I would say this approach trades lock contention for developer brain contention.

Given above, I think that those choosing Disruptor and similar approaches better make sure that they have development resources sufficient to maintain their solution.

Overall, Disruptor approach looks quite promising to me. Even if your company can't afford utilizing it eg for the reasons mentioned above, consider convincing your management to "invest" some effort into studying it (and SEDA in general) - because if they don't then there's a chance that one day their customers will leave them in favor of some more competitive solution requiring 4x, 8x etc less servers.