22 ms·

How we built Uber Engineering's highest query-per-second service using Go (2016)

185 points by godelmachine 7y ago

hobofan 7y ago
> High performance in throughput and latency. In our main data center serving non-China traffic alone, this service handled a peak load of 170k QPS with 40 machines running at 35% CPU usage on NYE 2015. The response time was < 5 ms at 95th percentile, and < 50 ms at the 99th percentile. > Geofence lookups are required on every request from Uber’s mobile apps and must quickly (99th percentile < 100 milliseconds) answer For a 100ms total budget, a ~50ms 99th percentile for a single microservice doesn't sound like something to boast about.
- bsaul 7y ago
  I don’t read this the way you do. I read it as their service had to answer under 100ms and they made it run under 50
- Rapzid 7y ago
  With that kinda volume the 99th is not interesting at all. Should be looking at the 99.99th.
  - sokoloff 7y ago
    The latency to human user is what matters. If I get an answer in under 100ms as a user 99% of the time, I don’t care whether 100 or 100K times per day someone else hits that 1% worst case.
    - ses1984 7y ago
      It has nothing to do with your experience being 99% good enough and more to do with the size of the revenue opportunity that could be lost messing up 1% of requests.
    - kevan 7y ago
      As an individual you don't care as long as you aren't in that 1%, but as a customer-obsessed service owner I absolutely care if a bad experience is happening 100k times per day. If you're operating at internet scale you need to look at both percentiles and absolute numbers to assess customer impact. Also keep in mind how percentiles compound when you have more than one service involved in serving a customer request. For example, let's say it takes 5 internal requests to serve an external customer request and each of those services measures latency SLAs at the 99th percentile. The customer request may only finish inside the SLA 95% of the time (99%^5)
    - scottlamb 7y ago
      > The latency to human user is what matters. Agreed, which is why the most surprising part of this article for me was this phrase: "In our main data center serving non-China traffic". The transit latency to the one main datacenter in the (non-China) world is a lot more significant than the server time here. (Over 50 ms just to cross the US; compare with their server-side latency numbers of 95%ile < 5 ms, 99%ile < 50 ms.) If they're serious about latency, their deployment is holding them back much more than their choice of programming language or algorithm. Or maybe the client is not the user's phone, but some other service running within the same datacenter?
  - sethammons 7y ago
    I would argue they should be considering max. Percentiles are good for understanding macro trends. But if every request is sacred, max needs to be monitored. Even at four nines, there are a couple dozen requests per second that are greater than what you are observing. How much greater? Who knows, if you are not observing max. Could be minutes in latency.
    - lclarkmichalek 7y ago
      Max is pretty horrible, as any comparison requires identical cohort sizes. P99.99 is much better if you want to go wild. Given that the service probably did not have a 100% success rate, and almost certainly had timeouts, the "max" would also likely be at the timeout.
      - sethammons 7y ago
        And that would be a good signal and worth investigating. Why timeouts? I run a few services doing billions of daily queries. I watch max in addition to percentiles.
      - hobofan 7y ago
        > and almost certainly had timeouts, the "max" would also likely be at the timeout You filter out the 504s, just the same way you would analyze it on a per-route basis for those metrics.
        spookthesunset 7y ago
        Sure but now your "100th percentile" would be nothing but the timeout. Quantifying things like service latency isn't a one-size fits all thing. Every service has its nuances and use cases that make it more meaningful to measure 99%, 99.9%, 99.99% or something else. .... just don't measure average like I've seen naive junior devs do. Average latency is the worst of all metrics to use as it will include all the outliers at the very tippy top of the spectrum and basically render the metric meaningless.
- foobarian 7y ago
  If that's 40 bare metal machines... assuming 60ish HT cores, and 35% CPU... that's not that earth shattering. We do that in Java :)
  - matt2000 7y ago
    My sense is that most people moving to Go are coming from Node and that explains their excitement about the performance. Not many upsides when you’re already on Java.
    - dashwav 7y ago
      I mean there is a definite performance gain from Java to Go, although I would agree most people probably wouldn't hit it - but if its just as easy to write, might as well use the better language. On top of that Go makes concurrency so much easier to factor in and program with, which in the backend server space is a very important asset over Java. As an interesting addendum, I found this to be a really interesting resource when comparing languages at a very base level, as it is very well written and you can actually look at the source code/ thesis papers for all of the implementations: https://github.com/ixy-languages/ixy-languages https://github.com/ixy-languages/ixy-languages
      - MrBuddyCasino 7y ago
        > I mean there is a definite performance gain from Java to Go I don't think thats true.
        erik_seaberg 7y ago
        The GC isn't very good yet, but brute-force sequential code can keep more state on the stack where it doesn't matter. (Just please codegen that instead of expecting everyone to read it.)
        marsdepinski 7y ago
        Go's GC is better than most of the Java GCs except the new ZGC and Azul's proprietary one. JIT makes some Java code faster. Ultimately, it's more about programmer expertise in a language rather than the actual language.
- sethammons 7y ago
  Per machine, that is 4,250k rps. For any http service we write in Go, that lines up with our general sizing estimates before we start work on a generic new service. After we start to hit the service with load, we start profiling and go from there. Sometimes it gets faster and sometimes it gets slower, but it is usually in the right ball park.
gunta 7y ago
it's sad to see these "moved from X language to Y language and it became faster!" every-time. If the CPU is the hugest bottleneck, the best answer is not to optimize the algorithm by going to a lower level language, but rather to invest in a different architecture like GPGPU or FPGA. For example, this paper shows a significant speed-up for PIP( Polygon in Point) algorithm, going from 15hs (CPU) to a mere 11sec (GPU) in task load-time. https://pdfs.semanticscholar.org/1e51/e3c681e1afc908a41ac253b7ef72f3285d1f.pdf https://pdfs.semanticscholar.org/1e51/e3c681e1afc908a41ac253...
- justincormack 7y ago
  That is high throughput design, not a low latency design, which is what they are optimising for here. It is a very different design space.
dang 7y ago
Related from 2018: https://news.ycombinator.com/item?id=16093192 https://news.ycombinator.com/item?id=16093192 and https://news.ycombinator.com/item?id=16084090 https://news.ycombinator.com/item?id=16084090. Discussed at the time: https://news.ycombinator.com/item?id=11205776 https://news.ycombinator.com/item?id=11205776.
scarejunba 7y ago
There's a famous 'rebuttal' post to this here https://medium.com/@buckhx/unwinding-uber-s-most-efficient-service-406413c5871d https://medium.com/@buckhx/unwinding-uber-s-most-efficient-s...
- abgfm 7y ago
  Thank you for this :))
  - buckhx 7y ago
    np ;)
- merb 7y ago
  well basically ubers blog posts are really low quality and from the outside their engineering descisions are kinda vague. like the switch from postgres to mysql. I'm still clueless how you can have so much money and one of the biggest engineering team, but still can't correctly engineer your stuff. I mean, everybody makes wrong decisions or errors in production code.
  - Slartie 7y ago
    From what I gathered off of several HN comments of Uber insiders, the size of their engineering team is actually more likely to be one of the causes for bad engineering decisions. They seem to have too many engineers running around for too little actual work to be done, which results in those engineers coming up with stuff to do to keep them busy (and of course to ensure they appear to be busy and worth their money to their superiors). One of the best ways to create yourself some work is to not choose an already-proven path to a solution, but invent a new one just for the sake of inventing a new one. Of course that's not how this kind of doing is justified - the justification is usually "the proven path does not scale to our needs" or "by using a special approach adapted to our needs we can be more efficient" or "the proven path is too complex, we can get by with something simpler and easier to maintain". Which might actually all be proper justifications, it's just that you should have some hard proof for these statements, like benchmark results of a comparison of different approaches. That part often gets skipped, which is actually ironic, because doing extensive evaluation and benchmarking and implementing different approaches first before choosing one for production actually serves quite well to create even more work to do.
cryptozeus 7y ago
I get all the criticism in comments but imo kudos to the team for going after the problem with new set of eyes and approaching in new language. At the end of the day you are under budget and have scalable fast microservice.
woeirua 7y ago
This is a very inefficient implementation. Really, just poor quality work overall, as anyone with even a basic understanding of spatial indexing would know that an R-tree would be many times faster, as illustrated here: https://medium.com/@buckhx/unwinding-uber-s-most-efficient-service-406413c5871d https://medium.com/@buckhx/unwinding-uber-s-most-efficient-s...
- not_a_cop75 7y ago
  So am I to understand this shows a little bit about why Uber is not the center of excellence it needs to be?
- thejigisup 7y ago
  clearly the most efficient solution is to pontificate about other people's implementations while never having done anything of the sort at that scale yourself.
  - jzoch 7y ago
    While he was a bit rude I wouldnt assume he hasn't built something at this sort of scale.
    - thejigisup 7y ago
      nah i think its a pretty fair assumption
      - woeirua 7y ago
        Let's just ignore the fact that in this case scale has nothing to do with the actual efficiency of the algorithm they implemented. As the link I posted mentioned, had they used a more efficient algorithm they could have used far fewer resources, or used the same resources to scale up further, with much faster response times overall.
      - forgottenpass 7y ago
        99% of people building at "scale" are borrowing bragging rights from a large company they happen to be employed by and/or tools they use while doing zero novel work unique to the size of their deployment. To say that these paper tigers are above the bikeshedding of all the plebs is quintessential software echochamber.
rayvy 7y ago
I think this write up is very fair for a solid engineering team. Is it groundbreaking and eye opening? Absolutely not, I’d say the most “hmm I didn’t know that” part of the entire thing was the part about R-Trees and S2. Is that bad? Absolutely not. These guys did the work, logged their performance and are sharing their story. However, and I believe this is where the animosity in the comments is coming from - given the elitist (for lack of a better term) attitude of these engineering types at these orgs (think of the poster children of the Valley), this is pretty...lacking. I mean, the part about using the Read/Write lock on the second attempt and instead trying to go with an installed package just screams Node.js, and honestly made me chuckle. I guess Leetcoding and Production Engineering really are different things. I genuinely expected more.
- 0xEFF 7y ago
  > I guess Leetcoding and Production Engineering really are different things. This is key point. They delivered value to the business. That's the only thing that matters.
  - ionforce 7y ago
    > They delivered value to the business. That's the only thing that matters. But this bit isn't true during the interview process.
    - vorpalhex 7y ago
      That's half of the interview process. The other half is convincing your future-peers you aren't a liability. Provide value, get along well, communicate decently.
  - privateprofile 7y ago
    > They delivered value to the business. That's the only thing that matters. Except this is an engineering blog post, so the engineering part actually matters. And, as demonstrated in the article [1] linked around this discussion, there were better engineering approaches that would have been even "better for business", as being more efficient means lower costs per transaction and/or higher throughput. [1] https://medium.com/@buckhx/unwinding-uber-s-most-efficient-service-406413c5871d https://medium.com/@buckhx/unwinding-uber-s-most-efficient-s...
PunchTornado 7y ago
To all the people "why not do it in Java / Java could have done it". Why not do it in a different language? Having Go and Node around is awesome because we can change the language. Don't you get bored to use just a single language? I'd get so so so bored if I didn't change languages every year. Glad that uber offers Go jobs.
- jryan49 7y ago
  Usually when you're trying to ship something, the more boring (predictable) parts the better.
  - PunchTornado 7y ago
    but is that the only goal? or you shouldn't enjoy the life? I find that I enjoy my life more as a programmer when I change things.
- jryan49 7y ago
  It's not but I also have more fun not getting paged in the middle of the night because something is broken ;) It's a balance for sure. I know it's cool to hate on Java, but I actually like Java for it's predictability, and my deep knowledge of it, and when using Intellij, it's a breeze for me to program in.
kuharich 7y ago
Prior discussion: https://news.ycombinator.com/item?id=11205776 https://news.ycombinator.com/item?id=11205776
paggle 7y ago
"For each lookup, we first find the desired city with a linear scan of all the city geofences, and then find the containing geofences within that city with another linear scan." Why wouldn't this be dogshit slow if they used all of the city geofences at once? I would think that first they would scan the country geofences, then the province geofences, then the city geofences, etc...
- mbo 7y ago
  It's almost like they could have used some sort of specialised tree data structure where each tree node was assigned to some spatial region on the map, where successive levels were assigned to increasingly smaller regions.

185 points by godelmachine 7y ago

> High performance in throughput and latency. In our main data center serving non-China traffic alone, this service handled a peak load of 170k QPS with 40 machines running at 35% CPU usage on NYE 2015. The response time was < 5 ms at 95th percentile, and < 50 ms at the 99th percentile. > Geofence lookups are required on every request from Uber’s mobile apps and must quickly (99th percentile < 100 milliseconds) answer For a 100ms total budget, a ~50ms 99th percentile for a single microservice doesn't sound like something to boast about.

bsaul 7y ago
I don’t read this the way you do. I read it as their service had to answer under 100ms and they made it run under 50
Rapzid 7y ago
With that kinda volume the 99th is not interesting at all. Should be looking at the 99.99th.
- sokoloff 7y ago
  The latency to human user is what matters. If I get an answer in under 100ms as a user 99% of the time, I don’t care whether 100 or 100K times per day someone else hits that 1% worst case.
  - ses1984 7y ago
    It has nothing to do with your experience being 99% good enough and more to do with the size of the revenue opportunity that could be lost messing up 1% of requests.
  - kevan 7y ago
    As an individual you don't care as long as you aren't in that 1%, but as a customer-obsessed service owner I absolutely care if a bad experience is happening 100k times per day. If you're operating at internet scale you need to look at both percentiles and absolute numbers to assess customer impact. Also keep in mind how percentiles compound when you have more than one service involved in serving a customer request. For example, let's say it takes 5 internal requests to serve an external customer request and each of those services measures latency SLAs at the 99th percentile. The customer request may only finish inside the SLA 95% of the time (99%^5)
  - scottlamb 7y ago
    > The latency to human user is what matters. Agreed, which is why the most surprising part of this article for me was this phrase: "In our main data center serving non-China traffic". The transit latency to the one main datacenter in the (non-China) world is a lot more significant than the server time here. (Over 50 ms just to cross the US; compare with their server-side latency numbers of 95%ile < 5 ms, 99%ile < 50 ms.) If they're serious about latency, their deployment is holding them back much more than their choice of programming language or algorithm. Or maybe the client is not the user's phone, but some other service running within the same datacenter?
- sethammons 7y ago
  I would argue they should be considering max. Percentiles are good for understanding macro trends. But if every request is sacred, max needs to be monitored. Even at four nines, there are a couple dozen requests per second that are greater than what you are observing. How much greater? Who knows, if you are not observing max. Could be minutes in latency.
  - lclarkmichalek 7y ago
    Max is pretty horrible, as any comparison requires identical cohort sizes. P99.99 is much better if you want to go wild. Given that the service probably did not have a 100% success rate, and almost certainly had timeouts, the "max" would also likely be at the timeout.
    - sethammons 7y ago
      And that would be a good signal and worth investigating. Why timeouts? I run a few services doing billions of daily queries. I watch max in addition to percentiles.
    - hobofan 7y ago
      > and almost certainly had timeouts, the "max" would also likely be at the timeout You filter out the 504s, just the same way you would analyze it on a per-route basis for those metrics.
      - spookthesunset 7y ago
        Sure but now your "100th percentile" would be nothing but the timeout. Quantifying things like service latency isn't a one-size fits all thing. Every service has its nuances and use cases that make it more meaningful to measure 99%, 99.9%, 99.99% or something else. .... just don't measure average like I've seen naive junior devs do. Average latency is the worst of all metrics to use as it will include all the outliers at the very tippy top of the spectrum and basically render the metric meaningless.
foobarian 7y ago
If that's 40 bare metal machines... assuming 60ish HT cores, and 35% CPU... that's not that earth shattering. We do that in Java :)
- matt2000 7y ago
  My sense is that most people moving to Go are coming from Node and that explains their excitement about the performance. Not many upsides when you’re already on Java.
  - dashwav 7y ago
    I mean there is a definite performance gain from Java to Go, although I would agree most people probably wouldn't hit it - but if its just as easy to write, might as well use the better language. On top of that Go makes concurrency so much easier to factor in and program with, which in the backend server space is a very important asset over Java. As an interesting addendum, I found this to be a really interesting resource when comparing languages at a very base level, as it is very well written and you can actually look at the source code/ thesis papers for all of the implementations: https://github.com/ixy-languages/ixy-languages https://github.com/ixy-languages/ixy-languages
    - MrBuddyCasino 7y ago
      > I mean there is a definite performance gain from Java to Go I don't think thats true.
      - erik_seaberg 7y ago
        The GC isn't very good yet, but brute-force sequential code can keep more state on the stack where it doesn't matter. (Just please codegen that instead of expecting everyone to read it.)
        marsdepinski 7y ago
        Go's GC is better than most of the Java GCs except the new ZGC and Azul's proprietary one. JIT makes some Java code faster. Ultimately, it's more about programmer expertise in a language rather than the actual language.
sethammons 7y ago
Per machine, that is 4,250k rps. For any http service we write in Go, that lines up with our general sizing estimates before we start work on a generic new service. After we start to hit the service with load, we start profiling and go from there. Sometimes it gets faster and sometimes it gets slower, but it is usually in the right ball park.

gunta 7y ago

it's sad to see these "moved from X language to Y language and it became faster!" every-time. If the CPU is the hugest bottleneck, the best answer is not to optimize the algorithm by going to a lower level language, but rather to invest in a different architecture like GPGPU or FPGA. For example, this paper shows a significant speed-up for PIP( Polygon in Point) algorithm, going from 15hs (CPU) to a mere 11sec (GPU) in task load-time. https://pdfs.semanticscholar.org/1e51/e3c681e1afc908a41ac253b7ef72f3285d1f.pdf https://pdfs.semanticscholar.org/1e51/e3c681e1afc908a41ac253...

justincormack 7y ago
That is high throughput design, not a low latency design, which is what they are optimising for here. It is a very different design space.

dang 7y ago

Related from 2018: https://news.ycombinator.com/item?id=16093192 https://news.ycombinator.com/item?id=16093192 and https://news.ycombinator.com/item?id=16084090 https://news.ycombinator.com/item?id=16084090. Discussed at the time: https://news.ycombinator.com/item?id=11205776 https://news.ycombinator.com/item?id=11205776.

scarejunba 7y ago

There's a famous 'rebuttal' post to this here https://medium.com/@buckhx/unwinding-uber-s-most-efficient-service-406413c5871d https://medium.com/@buckhx/unwinding-uber-s-most-efficient-s...

abgfm 7y ago
Thank you for this :))
- buckhx 7y ago
  np ;)
merb 7y ago
well basically ubers blog posts are really low quality and from the outside their engineering descisions are kinda vague. like the switch from postgres to mysql. I'm still clueless how you can have so much money and one of the biggest engineering team, but still can't correctly engineer your stuff. I mean, everybody makes wrong decisions or errors in production code.
- Slartie 7y ago
  From what I gathered off of several HN comments of Uber insiders, the size of their engineering team is actually more likely to be one of the causes for bad engineering decisions. They seem to have too many engineers running around for too little actual work to be done, which results in those engineers coming up with stuff to do to keep them busy (and of course to ensure they appear to be busy and worth their money to their superiors). One of the best ways to create yourself some work is to not choose an already-proven path to a solution, but invent a new one just for the sake of inventing a new one. Of course that's not how this kind of doing is justified - the justification is usually "the proven path does not scale to our needs" or "by using a special approach adapted to our needs we can be more efficient" or "the proven path is too complex, we can get by with something simpler and easier to maintain". Which might actually all be proper justifications, it's just that you should have some hard proof for these statements, like benchmark results of a comparison of different approaches. That part often gets skipped, which is actually ironic, because doing extensive evaluation and benchmarking and implementing different approaches first before choosing one for production actually serves quite well to create even more work to do.

cryptozeus 7y ago

I get all the criticism in comments but imo kudos to the team for going after the problem with new set of eyes and approaching in new language. At the end of the day you are under budget and have scalable fast microservice.

woeirua 7y ago

This is a very inefficient implementation. Really, just poor quality work overall, as anyone with even a basic understanding of spatial indexing would know that an R-tree would be many times faster, as illustrated here: https://medium.com/@buckhx/unwinding-uber-s-most-efficient-service-406413c5871d https://medium.com/@buckhx/unwinding-uber-s-most-efficient-s...

not_a_cop75 7y ago
So am I to understand this shows a little bit about why Uber is not the center of excellence it needs to be?
thejigisup 7y ago
clearly the most efficient solution is to pontificate about other people's implementations while never having done anything of the sort at that scale yourself.
- jzoch 7y ago
  While he was a bit rude I wouldnt assume he hasn't built something at this sort of scale.
  - thejigisup 7y ago
    nah i think its a pretty fair assumption
    - woeirua 7y ago
      Let's just ignore the fact that in this case scale has nothing to do with the actual efficiency of the algorithm they implemented. As the link I posted mentioned, had they used a more efficient algorithm they could have used far fewer resources, or used the same resources to scale up further, with much faster response times overall.
    - forgottenpass 7y ago
      99% of people building at "scale" are borrowing bragging rights from a large company they happen to be employed by and/or tools they use while doing zero novel work unique to the size of their deployment. To say that these paper tigers are above the bikeshedding of all the plebs is quintessential software echochamber.

rayvy 7y ago

I think this write up is very fair for a solid engineering team. Is it groundbreaking and eye opening? Absolutely not, I’d say the most “hmm I didn’t know that” part of the entire thing was the part about R-Trees and S2. Is that bad? Absolutely not. These guys did the work, logged their performance and are sharing their story. However, and I believe this is where the animosity in the comments is coming from - given the elitist (for lack of a better term) attitude of these engineering types at these orgs (think of the poster children of the Valley), this is pretty...lacking. I mean, the part about using the Read/Write lock on the second attempt and instead trying to go with an installed package just screams Node.js, and honestly made me chuckle. I guess Leetcoding and Production Engineering really are different things. I genuinely expected more.

0xEFF 7y ago
> I guess Leetcoding and Production Engineering really are different things. This is key point. They delivered value to the business. That's the only thing that matters.
- ionforce 7y ago
  > They delivered value to the business. That's the only thing that matters. But this bit isn't true during the interview process.
  - vorpalhex 7y ago
    That's half of the interview process. The other half is convincing your future-peers you aren't a liability. Provide value, get along well, communicate decently.
- privateprofile 7y ago
  > They delivered value to the business. That's the only thing that matters. Except this is an engineering blog post, so the engineering part actually matters. And, as demonstrated in the article [1] linked around this discussion, there were better engineering approaches that would have been even "better for business", as being more efficient means lower costs per transaction and/or higher throughput. [1] https://medium.com/@buckhx/unwinding-uber-s-most-efficient-service-406413c5871d https://medium.com/@buckhx/unwinding-uber-s-most-efficient-s...

PunchTornado 7y ago

To all the people "why not do it in Java / Java could have done it". Why not do it in a different language? Having Go and Node around is awesome because we can change the language. Don't you get bored to use just a single language? I'd get so so so bored if I didn't change languages every year. Glad that uber offers Go jobs.

jryan49 7y ago
Usually when you're trying to ship something, the more boring (predictable) parts the better.
- PunchTornado 7y ago
  but is that the only goal? or you shouldn't enjoy the life? I find that I enjoy my life more as a programmer when I change things.
jryan49 7y ago
It's not but I also have more fun not getting paged in the middle of the night because something is broken ;) It's a balance for sure. I know it's cool to hate on Java, but I actually like Java for it's predictability, and my deep knowledge of it, and when using Intellij, it's a breeze for me to program in.

kuharich 7y ago

Prior discussion: https://news.ycombinator.com/item?id=11205776 https://news.ycombinator.com/item?id=11205776

paggle 7y ago

"For each lookup, we first find the desired city with a linear scan of all the city geofences, and then find the containing geofences within that city with another linear scan." Why wouldn't this be dogshit slow if they used all of the city geofences at once? I would think that first they would scan the country geofences, then the province geofences, then the city geofences, etc...

mbo 7y ago
It's almost like they could have used some sort of specialised tree data structure where each tree node was assigned to some spatial region on the map, where successive levels were assigned to increasingly smaller regions.