11 Best Practices for Low Latency Systems

stopwatchIts been 8 years since Google noticed that an extra 500ms of  latency dropped traffic by 20% and Amazon realized that 100ms of extra latency dropped sales by 1%. Ever since then developers have been racing to the bottom of the latency curve, culminating in front-end developers squeezing every last millisecond out of their JavaScript, CSS, and even HTML. What follows is a random walk through a variety of best practices to keep in mind when designing low latency systems. Most of these suggestions are taken to the logical extreme but of course tradeoffs can be made. (Thanks to an anonymous user for asking this question on Quora and getting me to put my thoughts down in writing).

Choose the right language

Scripting languages need not apply. Though they keep getting faster and faster, when you are looking to shave those last few milliseconds off your processing time you cannot have the overhead of an interpreted language. Additionally, you will want a strong memory model to enable lock free programming so you should be looking at Java, Scala, C++11 or Go.

Keep it all in memory

I/O will kill your latency, so make sure all of your data is in memory. This generally means managing your own in-memory data structures and maintaining a persistent log, so you can rebuild the state after a machine or process restart. Some options for a persistent log include Bitcask, KratiLevelDB and BDB-JE. Alternatively, you might be able to get away with running a local, persisted in-memory database like redis or MongoDB (with memory >> data). Note that you can loose some data on crash due to their background syncing to disk.

Keep data and processing colocated

Network hops are faster than disk seeks but even still they will add a lot of overhead. Ideally, your data should fit entirely in memory on one host. With AWS providing almost 1/4 TB of RAM in the cloud and physical servers offering multiple TBs this is generally possible. If you need to run on more than one host you should ensure that your data and requests are properly partitioned so that all the data necessary to service a given request is available locally.

Keep the system underutilized

Low latency requires always having resources to process the request. Don’t try to run at the limit of what your hardware/software can provide. Always have lots of head room for bursts and then some.

Keep context switches to a minimum

Context switches are a sign that you are doing more compute work than you have resources for. You will want to limit your number of threads to the number of cores on your system and to pin each thread to its own core.

Keep your reads sequential

All forms of storage, wither it be rotational, flash based, or memory performs significantly better when used sequentially. When issuing sequential reads to memory you trigger the use of prefetching at the RAM level as well as at the CPU cache level. If done properly, the next piece of data you need will always be in L1 cache right before you need it. The easiest way to help this process along is to make heavy use of arrays of primitive data types or structs. Following pointers, either through use of linked lists or through arrays of objects, should be avoided at all costs.

Batch your writes

This sounds counterintuitive but you can gain significant improvements in performance by batching  writes. However, there is a misconception that this means the system should wait an arbitrary amount of time before doing a write. Instead, one thread should spin in a tight loop doing I/O. Each write will batch all the data that arrived since the last write was issued. This makes for a very fast and adaptive system.

Respect your cache

With all of these optimizations in place, memory access quickly becomes a bottleneck. Pinning threads to their own cores helps reduce CPU cache pollution and  sequential I/O also helps preload the cache. Beyond that, you should keep memory sizes down using primitive data types so more data fits in cache. Additionally, you can look into cache-oblivious algorithms which work by recursively breaking down the data until it fits in cache and then doing any necessary processing.

Non blocking as much as possible

Make friends with non blocking and wait free data structures and algorithms. Every time you use a lock you have to go down the stack to the OS to mediate the lock which is a huge overhead. Often, if you know what you are doing, you can get around locks by understanding the memory model of the JVM, C++11 or Go.

Async as much as possible

Any processing and particularly any I/O that is not absolutely necessary for building the response should be done outside the critical path.

Parallelize as much as possible

Any processing and particularly any I/O that can happen in parallel should be done in parallel. For instance if your high availability strategy includes logging transactions to disk and sending transactions to a secondary server those actions can happen in parallel.


Almost all of this comes from following what LMAX is doing with their Disruptor project. Read up on that and follow anything that Martin Thompson does.

Additional Blogs

Mathematical Purity in Distributed Systems: CRDTs Without Fear

mathThis is a story about distributed systems, commutativity, idempotency, and semilattices. It’s a real nail biter so put the kettle on to boil and settle in. Our story starts one bright morning at your budding mobile gaming startup a few days before the big launch. Lets watch.

The Simplest Thing That Works, Right?

Its Thursday and the big launch is just a few days away. You are putting the finishing touches on your viral referral loop when you think to yourself, “wouldn’t it be grand if we tracked how many levels our players complete”. Since you fully expect that you are about to release the next Candy Crush Saga you don’t want to build something that won’t scale so you bust out your favorite NoSQL database, MonogDB and turn on the webscale option. You lean back in your chair and after a few minutes of staring at the ceiling you come up with the perfect schema.

    _id: hash(<user_name>),
    level: <int>

You flip over to your mobile app and wire up a “new level” message that gets sent back to your servers. Then, in the server code you process the message and increment the appropriate MongoDB record.

But we don’t even have that many levels!

Your app launches with a feeble roar (its ok, just wait for TechCrunch to pick it up) and you decide to check in on your analytics. You start poking around and quickly notice that some user has played to level 534 when there are only 32 levels in the game. What gives? You poke around some more and realize that this user is actually your co-worker Lindsey. You wander over to her desk to see if she can think of anything that might have caused this. The two of you pour over the logs from the app on her phone only to find a lot of network timeouts and retries. Thats when Lindsey says “You know, I was at my parents house last night showing them the game and the cell service there is pretty crappy. I wonder if the game kept resending the “new level” message thinking that the send had timed out, when in fact the server had received the message but wasn’t able to acknowledge the message fast enough.” Your stomach quickly sinks as you realize that this behavior will totally screw up your numbers. The two of you wander over to a whiteboard and in short order you realized the MongoDB increment function has to go. Instead, the two of you conclude that the game should send a “level X” method to the server and the server will simply write the level number into MongoDB. A quick update to your server and a lengthy update of the app later (because Apple) your analytics are starting to look better.


What you’ve just experienced is a the pain that comes from a system that lacks idempotency. Idempotent operations are ones that can be safely retried without effecting the end result of the system. In the first design, the increment function is not idempotent since when it is retried it increments the MongoDB number again even though it shouldn’t. By storing the level number that is sent along with the message you transformed the system into one that is idempotent since storing the same level number over and over will always end up with the same result.

I know I played more levels than that!

TechCrunch is taking its sweet time to cover your awesome game so after blindly throwing half of your seed money at Google AdWords you decide to check in on the analytics again. This time, you start by looking at your personal record and notice another oddity; you’ve beaten all 32 levels and yet your analytics record has only recorded up to level 30. You mull it over for a few minutes and realize when you beat the game you were on the subway where there wasn’t any cell reception. You take out your phone and check the logs and sure enough you still have two “level X” messages waiting to be sent back to the server. You start up the game and watch the logs as the last two messages are safely sent off to your servers. For fun you’ve been tailing the server logs as well and notice something interesting; the two messages where handled by two different servers. “Just the load balancer doing its job” you think. Back to MongoDB you go, but instead of the 32 you were hoping for, you see a 31 staring you in the face. What the? And then it hits you. The “level 31″ message must have been processed a little bit slower than the “level 32″ message and overwrote the 32 in MongoDB. “Damn this stuff is hard”. You head back to Lindey’s desk and explain the problem to her. The two of you hit the whiteboard again and decided that what you really should do is update the value in MongoDB to be the maximum of the value in MongoDB and the value in the message. Luckily this change can be done solely on the server side (no waiting for Apple). A quick deploy later and you are feeling pretty smug.


This time you were bitten by the lack of commutativity in your system. Commutative operations are ones that can be processed in any order without effecting the end result of the system. In the second design updating the value in MongoDB was not commutative since it blindly overwrote any previous value resulting in a last write wins situation. By using the maximum function you transformed the system into one that is commutative since the maximum of a stream of numbers always returns the same result regardless of the order of the numbers.

Monotonic Semilattices

Now we are breaking out the big words. As it turns out, if you create a system that is idempotent and commutative (and associative but that almost always goes hand in hand with commutative) you have created a semilattice. Moreover, in your particular case, you created a monotonic semilattice. That is to say, you created an idempotent and commutative system that grows only in one direction. Specifically, the number in MongoDB only increases. Now why is this interesting? Well, monotonic semilattices are the building blocks for Conflict-free Replicated Data Types. These things are all the rage and Riak has already implemented one CRDT for their distributed counters feature.

Wrapping Up

So as you can see none of this stuff is particularly hard but when these simple principals are combined they can make life much easier. Go forth and wrangle some distributed systems!

Dropping ACID on your NoSQL

acid-tripA lot has been said about NoSQL and the resulting backlash of NewSQL. NoSQL reared its head in reaction to the severe pain of sharding traditional open source SQL databases and quickly took the software community by storm. However, scalability wasn’t the only selling point. Many made the argument that SQL itself was to blame and that developers should rise up and throw off the shackles of this repressive language. Fast forward a few years and, while NoSQL alternatives are here to stay, it is quite clear that SQL is far from being overthrown. Instead, we now have a new breed of SQL options, the so called NewSQL databases, that offer the familiarity of SQL, with all its tooling and frameworks, while still giving us the scalability we need in this web scale world. It is in the midst of all this commotion that a quiet trend is emerging, one that is going mostly unnoticed, a trend of dropping ACID on your NoSQL.


So what is this trend? Well it is a middle ground between the NoSQL world and the NewSQL world where ACID guarantees are provided across multiple keys but without the overhead of SQL. Until recently if you wanted multi-key transactions you had to use a NewSQL database; the ideas of SQL and ACID were intertwined and no one seemed to be trying to untangle them. However, in the past year and a half or so that has changed.


The first one of these databases to come to my attention was HyperDex. I was originally drawn to the project when I learned of its approach to secondary indexes which they call “hyperspace hashing”. In a traditional key-value store the values are placed in a 1-dimensional ring based on the primary key. In HyperDex the values are placed in n-dimentional space based on the primary and any secondary keys that are specified. This allows secondary index queries to be routed to a subset of the servers in the cluster instead of every server as is the case with secondary indexes in traditional key-value stores. I highly recommend reading the research paper to get a better understanding. However, it was only recently with the addition of Hyperdex Warp that ACID support was added. I won’t go into the details of how Warp works but instead I’ll direct you to the research paper describing  it.


The next database on the scene was FoundationDB. While HyperDex, being developed at Cornell University, has a strong research influence, FoundationDB instead comes from a practical engineering background. Not only has the FoundationDB team built a compelling, ACID compliant, NoSQL store but they ended up building Flow, a C++ actor library, and a trifecta of testing tools to ensure that FoundationDB is as fast and as resilient as possible. More recently they acquired Akiban, makers of an interesting SQL database, and have started building a SQL layer on top of their key value store. This approach is very similar to the approach that Google took when creating F1 and not unlike the the approach that NuoDB is taking. It will be interesting to follow that NewSQL trend.


Finally we come to Spanner, Google’s geo-distributed datastore. While significantly more vast in scale than either HyperDex or FoundationDB it still shares the common thread of ACID transactions in a NoSQL store. Of course the interesting part of Spanner that everyone is talking about is TrueTime which uses atomic clocks and GPS to create a consistent ordering of transactions across the globe. Its going to be a while before that becomes common place outside of Google data centers but its a fascinating solution to the normal assumptions about synchronized clocks in distributed systems.

Web Scale Analytics Reading List

columnsBig data is taking the world by storm and with it comes an explosion of new ideas and technologies looking to help us understand what this data is telling us. With VLDB 2012 under way I decided to take another look at the literature to see what advances are out there as well as refresh on the classics. The result of this deep dive is the web scale analytics reading list below. The list is grouped at a high level into column oriented database solutions and online analytical processing (OLAP) solutions. Column oriented databases are by far more powerful but also more complicated to implement. As such, much of the work on column oriented databases is being done at companies that are building one as a product. The obvious exception being Google. OLAP systems on the other hand, while less powerful, are simpler to implement. For this reason we see a variety of companies rolling their own solutions in response to their growing analytics problems.

Column Oriented Databases

Online Analytical Processing

A Sequential I/O Reading List

Hard Drive SpindleOver the past year I’ve been collecting links on the growing trend of rooting out all random I/O in large scale distributed systems. It has always been apparent that rotational media suffered a random I/O penalty but as bandwidth improvements continue and latency improvements languish the difference between sequential and random I/O is becoming unbearable. SSDs have been hailed as a fix, and in large part they remove the pain of random reads, but at the cost of requiring sequential writes. And now, as it now turns out, even RAM benefits from sequential I/O due to the increasingly complex structure of new and faster chips. In an effort to help others who might be stumbling into this area here is a curated list of the best posts and papers I have found on the topic.

Rotational Media

Solid State Drives


Benchmarking More Seq Traversal Idioms in Scala

Last week I had the luxury of spending some quality time with YourKit and our production system at Localytics and was pleasantly surprised to see things humming right along. Most of our time was spent building collections and iterating over them which got me thinking. What is the most efficient way to traverse a collection in Scala? After a quick trip to google I had two blog posts in hand.

The first post was from way back in 2009. While its main focus was on the impact of JVM options on Scala iteration it pointed out that Vectors seem to be more performant than Lists for iteration. However, being from 2009, I was curious if this result still stood. The second post was from 2012 and benchmarked various ways of iterating over a List while applying two different transformations. The post didn’t benchmark Vector but the author was particularly rigorous with his methodology; making use of Caliper and posting his code on github. I highly recommend reviewing the post.

I forked the repo, added two more tests, ensured the server vm was being used and re-ran the tests.



java version "1.6.0_24"
OpenJDK Runtime Environment (IcedTea6 1.11.1) (6b24-1.11.1-4ubuntu2)
OpenJDK Server VM (build 20.0-b12, mixed mode)


Scala code runner version 2.9.1 -- Copyright 2002-2011, LAMP/EPFL


Ubuntu 12.04


Dual Intel(R) Xeon(R) CPU E5410 @ 2.33GHz (EC2 c1.medium)


Functional Vector

val wLength = wordsIndexedSeq.map( _.length )
val wCaps = wordsIndexedSeq.map( isCapitalized )
(wLength, wCaps)


val n = wordsList.length
val wLength = List.newBuilder[Int]
val wCaps = List.newBuilder[Boolean]
for( word <- wordsList ) {
  wLength += word.length
  wCaps += isCapitalized(word)
( wLength.result(), wCaps.result() )


Each style of iteration was tested with four different sized collections. The graph shows how many times slower each style was versus the OldSchool style (i.e. arrays and while loops).



  • Nothing beats arrays and while loops (i.e. the OldSchool solution)
  • Vector beats out List
  • Vector interestingly gets better with more items
  • In contrast to the original post none of the List optimizations seem like a clear win to me

Decoding strings with an unknown encoding

Unicode SnowmanWe’ve all been there, the system is humming along when you bring up the UI only to see “Espa?ol” staring you back in the face. What is this? Why is there a question mark in there? Well, you’ve been bitten by they mystical world of unicode. Usually this issue is an easy fix; always use UTF-8 encoding. However, what to do if you don’t own the whole code path? What if you have to support poorly written third party client libraries? What if you have client libraries in the wild that will never be updated? What if these client libraries out right lie about what encoding they are using? Follow me and we’ll find out.

Bytes To String

On the JVM there are two standard ways of converting bytes to Strings; new String(bytes[], encoding) and using the NIO Charset. Since they both accomplish the same feat my decision came down to performance. Luckily someone else did the heavy lifting and figured out that new String(bytes[], encoding) ekes out a small win over NIO Charset. However, this option poses a challenge. How do we know if the decoding succeeded? The NIO option can throw an Exception (effective but slow) or insert a Unicode Replacement Character (easy to find with a String.contains()) if it encounters a some bytes that cannot be decoded . new String(bytes[], encoding) does no such thing. It blindly decodes characters and will output random garbage in the resulting string if the decoding chokes on some bad byte values. We need a way to find those garbage characters.

Regex for non unicode characters

The clue that got me on the right track was an odd looking pattern in the javadoc for Pattern.

[\p{L}&&[^\p{Lu}]] Any letter except an uppercase letter (subtraction)

It seemed that \p{L} was some magical regex incantation for any unicode letter and after some additional searching it appeared that that was exactly the case. Of course what we really want to find are characters that are not unicode letters, spaces, punctuation or digits. Lucky for us there are matching groups for all of these, leading us to this regex:


Performance Testing

Since performance is of particular concern it was important to test the overhead of this regex check. I fired up the Scala REPL and tested the using new String(bytes[], encoding) with the above regex as compared to NIO Coded using String.contains() to check for the replacement character. After all that work it turns out that the regex was significantly more expensive than String.contains(). So much so that the NIO code was about 2x as fast. So, in the end, I ended up going with the simpler NIO option.

The Code

import io.Codec
import java.nio.ByteBuffer

val UTF8 = "UTF-8"
val ISO8859 = "ISO-8859-1"

def bytesToString(bytes: Array[Byte], encoding: String) = {
  val upper = encoding.toUpperCase
  val codec = if (ISO8859 == upper) Codec.ISO8859 else Codec.UTF8
  val decoded = codec.decode(ByteBuffer.wrap(bytes)).toString
  if (!decoded.contains(REPLACEMENT_CHAR)) {
  } else {
    val otherCodec = if (ISO8859 == upper) Codec.UTF8 else Codec.ISO8859
    val otherDecoded = otherCodec.decode(ByteBuffer.wrap(bytes)).toString
    if (!otherDecoded.contains(REPLACEMENT_CHAR)) {
    } else {
      val utf8 = if (ISO8859 == upper) otherDecoded else decoded
      utf8.replace(REPLACEMENT_CHAR, '?')


Thanks to Joni Salonen for pointing out that I was wrong about new String() not inserting the unicode replacement char. In light of that info the following code is just a touch faster.

val UTF8 = "UTF-8"
val ISO8859 = "ISO-8859-1"
def bytesToString(bytes: Array[Byte], encoding: String) = {
  val upper = encoding.toUpperCase
  val firstEncoding = if (ISO8859 == upper) ISO8859 else UTF8
  val firstDecoded = new String(bytes, firstEncoding)
  if (!firstDecoded.contains(REPLECEMENT_CHAR)) {
  } else {
    val secondEncoding = if (ISO8859 == upper) UTF8 else ISO8859
    val secondDecoded = new String(bytes, secondEncoding)
    if (!secondDecoded.contains(REPLECEMENT_CHAR)) {
    } else {
      val utf8 = if (ISO8859 == upper) secondDecoded else firstDecoded
      utf8.replace(REPLECEMENT_CHAR, '?')

Get every new post delivered to your Inbox.