How We Built Uber’s Highest Query per Second Service Using Go

I don&#x27;t think I&#x27;ve learned anything from this article. It&#x27;s interesting how quickly the keywords pick up on HN (Uber and Go).<p>More than 3 years ago we&#x27;ve implemented a reverse geocoder web-service that indexed complete Census TIGER dataset. The service handled over 15K reqs&#x2F;sec on a 2011 macbook, doing exact in polygon search(no approximations). We implemented an optimized (for in polygon search) R-tree data structure for the lookups.<p>Assuming Uber&#x27;s geofence lookups would rely on a much smaller dataset than TIGER, I think you could have come up with a much more efficient implementation requiring a fraction of the resources.<p>And again, use of Go; irrelevant.

This article is a little bit hand-wavy for me. Essentially they could use any languages to implement this, also there is no proof how channels could not be used. I bit more details would be essential to make this a good read, at least for me.

It&#x27;s interesting that they&#x27;re doing a spatial database without using a 2D spatial data structure. MySQL and PostGres both have data structures for this. But maybe they don&#x27;t have that many geofences per city.<p>They have an N readers, one writer problem. It&#x27;s possible to do that without blocking the readers. There was a YC article on a lockless solution to that yesterday. This is an easier problem. Each city&#x27;s geofences can be updated by making a copy, updating the copy, and atomically replacing the single reference to the copy. Any searches still running on the old copy continue to run on the old copy. Eventually, the GC deletes the old copy.

&quot;Instead of indexing the geofences using R-tree or the complicated S2, we chose a simpler route...&quot;<p>&quot;While the runtime complexity of the solution remains O(N), this simple technique reduced N from the order of 10,000s to the order of 100s.&quot;<p>It seems odd to me that they&#x27;re posting about the performance of Go, yet they deliberately chose a less optimal algorithm because the better ones were &quot;complicated&quot;. Or, if their simpler approach did in fact run faster than R-trees or S2, it would have been nice to see some benchmarks and a clearer explanation for why. Choosing the best algorithm seems more important than the language in a case like this one.

I was surprised to not see PostGIS at least mentioned. I&#x27;ve been using PostGIS professionally for the last few years and only have good things to say, the toolchain is very mature.<p>We make pretty extensive use of R-Tree indexes in PostGIS, tables with 10,000,000+ rows and shapes that roughly match streets, parcels, blocks, zip codes. While I don&#x27;t have 99th percentile data offhand average query time is &lt;1ms. Perhaps there are slow responses at the 99th percentile however I would be very surprised by this.

I would be interested in comparing the performance of Uber&#x27;s first pass &quot;city-fencing&quot; vs a pre-computed 1D array.<p>EG: Subdivide a flat projection of earth into n^2 squares. Create an array of length n^2. Set the value of each element in the array to a list of canidate geofences(which have area in that square).<p>Scale lat and long between 0 and 1. Then you can index directly into it with PrecomputedArray[floor(lat*n+long)]<p>This is trading space for time, may as well choose space here.

&gt; While historically Uber has been mostly a Node.js and Python shop, the Go language is becoming the language of choice for building many of Uber Engineering’s new services.<p>It feels like this type of narrative is becoming more common.

Ridiculous article.<p>&#x27;Highest QPS?&#x27;<p>This is a trivial geometric problem, any sane implementation should be several orders of magnitude faster than doing network IO. &#x2F;rant

I&#x27;m not terribly familiar with geo algorithms but I&#x27;m curious why it&#x27;s worthwhile taking the two layer approach.<p>Can&#x27;t you precompute the X and Y minima and maxima for each geo fence and throw out 99% of candidates extremely quickly? In other words store the bounding rectangle for each geofence. Even with 100,000s of entries we&#x27;re talking 4 primitive type comparisons per entry to exclude all non-possible candidates. I would have a hard time believing this is slower than ray casting to city geofences.

Why not PostgreSQL (PostGIS)?

<i>CPU intensive workload. Geofence lookups require CPU-intensive point-in-polygon algorithms. While Node.js works great for our other services that are I&#x2F;O intensive, it’s not optimal in this use case due to Node’s interpreted and dynamic-typed nature.</i><p>That&#x27;s misleading, math in V8 can be VERY fast (aside from the current absence of vectorization). See the benchmarks here: <a href="http:&#x2F;&#x2F;julialang.org" rel="nofollow">http:&#x2F;&#x2F;julialang.org</a>

How often does the fencing data change? If it&#x27;s infrequent I wonder if you could load the data on start up and simply restart nodes to refresh the data. That would avoid a mutex lock entirely.<p>However, a mutex lock&#x2F;unlock should take &lt;100ns. It doesn&#x27;t seem like that should be a bottleneck. It&#x27;d be interesting to hear more about the data, requirements, and response times (median, 90%, etc).

I&#x27;ve done something similar. I used the GPU (actually WebGL) and made several images of my geofences where each one was simply drawn as a bitmask (black and white). Then, I wrote a fragment shader to determine if a point is within a geofence by looking the pixel value. I rounded the lat&#x2F;long pairs to a precision that matched the resolution of my image.<p>Can&#x27;t remember the exact results but throughput was much higher than what I was able to achieve using highly optimized PostGIS queries.

really interesting to see that go channels weren&#x27;t used due to performance concerns. channels is the often advocated tech for concurency in this language so having to fall back to mutexes seems like a downpoint. I would have loved to see a benchmark in the article.

I built a route finding algorithm in Node.JS for one of my projects. I also do some geofence checks, but I use a geo-index (Mongodb).<p>Similar to other comments, the article is a bit lacking in detail. Regardless of language used, I would have liked to see a comparison of query times using a spatial index and not. From my limited experience with PostGIS, there are some inside polygons that perform poorly on large polygons, where Mongodb has done better, and vice versa with linestrings.

&quot;...service handled a peak load of 170k QPS with 40 machines running at 35% CPU usage on NYE 2015. The response time was &lt; 5 ms at 95th percentile, and &lt; 50 ms at the 99th percentile.&quot;<p>It&#x27;s ~4k per instance. I would like to know what the R&#x2F;W ratio is. And how often the index is updated is the key, aka locking operations, which should be mentioned in the article.<p>Also this article should give more comparison on other implementations, if possible. At least compare with Uber&#x27;s monolithic implementation.<p>The geo-datastructure part is very cool.

&gt; Because node.js is single threaded<p>cluster&#x27;s been around a while now, and is built in to node 5.x.

Am I the only one not able to access the site?

The article is about hiring a go developer that will write a better article

If you need an explanation of how Go might help your organization, this discusses how Uber does GeoFencing using the language.

A reliable runtime is listed in the three main benefits of using Go. Are the runtimes for the alternatives really any less reliable?<p>I can buy that the language is easy to learn since the feature set is very limited, but is productivity in the first week&#x2F;month really what to optimise for?<p>They also list performance as a benefit.<p>Go is a reasonable choice, but I doubt that the result would have been much different if they&#x27;d used any other modern statically typed language such as Rust, Scala, D, or even Nim.

&gt;Because Node.js is single threaded, background refreshing can tie up the CPU for an extended period of time (e.g., for CPU-intensive JSON parsing work), causing a spike in query response times.<p>I&#x27;m not the biggest node fan, but that is utterly false. How do you think asynchronous system calls get processed in libuv (the event loop that node uses.) ? threads. Of course you&#x27;ll park the background thread while you&#x27;re waiting in case of IO, but if it&#x27;s CPU intensive then you bet that you can use all cores with background work. You just need to know how to write C++ and read the documentation on the bindings