Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
11  
"What other architectures, libraries, techniques or "things" are helpful to reach such levels of performance?" Why ask? That quote is the definitive list. There are lots and lots of other things, none of which have the kind impacts of the items in that list. Anything else anyone can name won't be as helpful as that list. Why ask for bad ideas when you've quoted one of the best optimization lists ever produced? –  S.Lott Jul 29 '11 at 12:21
    
It would be nice to learn which tools they used to see how the generated code ran on the system. –  user1249 Jul 29 '11 at 14:29
    
I have heard of folks swear by all kinds of techniques. What I have found most effective is system level profiling. It can show you bottlenecks in the ways your program and workload are exercising the system. I would suggest adhering to well known guidelines regarding performance and writing modular code so that you can easily tune it later... I don't think you can go wrong with system profiling. –  ritesh Aug 1 '11 at 23:46

4 Answers 4

up vote 19 down vote accepted

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.

share|improve this answer
    
Discussing the principles is underlying principles is great and your comment is excellent and ... unless fowler's paper hadn't had a reference in a foot note to cache oblivious algorithms en.wikipedia.org/wiki/Cache-oblivious_algorithm (which fits nicely into category number 1 you have above) I would have never stumbled upon them. So ... with respect to each category you have above, do you know of the top 3 things that a person should know? –  Dakotah North Jul 29 '11 at 18:14
    
@Dakotah: I would not even start to worry about cache locality unless and until I had completely eliminated disk I/O, which is where the vast majority of time is spent waiting in the vast majority of applications. Aside from that, what do you mean by "top 3 things that a person should know"? Top 3 what, to know about what? –  Aaronaught Jul 29 '11 at 18:34
    
The jump from RAM access latency (~10^-9s) to magnetic disk latency (~10^-3s average-case) is another few orders of magnitude greater than 1000x. Even SSDs still have access times measured in hundreds of microseconds. –  Sedate Alien Aug 14 '11 at 22:39
    
@Sedate: Latency yes, but this is more a question of throughput than raw latency, and once you get past access times and into total transfer speed, disks aren't quite so bad. That's why I made the distinction between random and sequential access; for random access scenarios it does primarily become a latency issue. –  Aaronaught Aug 14 '11 at 22:56
    
@Aaronaught: Upon re-reading, I suppose that you are correct. Perhaps a point should be made that all data access should be as sequential as possible; significant benefits can also be had when accessing data in-order from RAM. –  Sedate Alien Aug 14 '11 at 23:55

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.

share|improve this answer

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.

share|improve this answer

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.
share|improve this answer
    
I disagree with making methods final. The JIT is able to figure out that a method gets never overridden. Moreover, in case a subclass gets loaded later it can undo the optimization. Also note that "avoid allocating memory" may also make the job of the GC harder and thus slow you down - so use with caution. –  maaartinus Aug 20 '11 at 9:19
    
@maaartinus: regarding final some JITs might figure it out, others might not. It's implementation dependent (as are many performance tuning tips). Agree about the allocations - you have to benchmark this. Usually I've found it is better to eliminate allocations, but YMMV. –  mikera Sep 6 '13 at 10:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.