转载

Uber是如何基于Go语言构建高QPS服务的？

在2015年初，我们构建了一个只做一件事（也的确做的非常好）的微服务——查找地理围栏（geofence lookup）。一年后，这项服务已经成为Uber数百个正在运行的服务中每秒查询次数（QPS）最高的服务。接下来，本文将谈论我们构建这项服务的原因以及我们是如何使用 Go语言快速构建和扩展这项服务的。

背景

在Uber，一个地理围栏就表示地球表面上人为划分的一个地理区域。此外，我们进一步在基于地理的配置中使用地理围栏的概念。地理围栏的概念在很多地方发挥了很重要的作用——向用户展示在某个位置可使用的产品时，定义机场等特殊用途区域时以及在很多人同时呼叫实现动态定价时。

Colorado的一个地理围栏样例

在提取用户手机的经纬度坐标等基于地理位置的配置信息时，需要做的第一件事情就是确定该位置落在哪个地理围栏中。而该功能已经在多个服务或模块中被实现。但是，当我们从一体化架构转移到基于微服务的架构时，我们选择了将这项功能集中在一个新的单独的微服务中进行实现。

选择Go的原因

当我们评估所要使用语言的时候， Node.js 正是广大的服务设计团队普遍采用的编程语言。而我们也在Node.js的使用方面有着丰富的经验。然而，Go语言却由于以下原因满足了我们的需求：

高吞吐量和低延迟的需求。Uber的手机端App在发送请求时，必然会触发一次查找地理围栏的操作。而服务器必须要能够对每秒上万次的请求以99%的概率响应时间小于100ms的速度进行响应。
CPU密集型负载。查找地理围栏需要使用计算密集型的 Point-In-Polygon（PIP）算法。尽管Node.js可以很好的用于I/O密集型的服务，解释执行以及动态类型定义等的特性使得它并不适合于我们的使用场景。
非中断式的后台加载。为了保证查询操作是基于最新的地理围栏信息而进行的，服务必须要能够根据多个数据源的信息在后台实时刷新内存中的地理围栏数据。因为Node.js是单线程的，后台刷新很可能会占用一定的CPU时间（如CPU密集型的 JSON 的编译工作），最终导致部分查询的响应时间过长。但是，对于Go语言而言，这完全不是问题。 Goroutine 可以运行在多个CPU核上，并且可以在响应前端查询的同时后台并行进行刷新数据的工作。

是否建立地理信息索引——这是个问题

当给定了一个经纬度坐标的位置信息时，如何从上万个地理围栏中找到该位置所在的那一个呢？最直接而暴力的解决方法为：浏览所有的地理围栏，然后采用光线投射（Ray Casting）等算法进行PIP检查。但是，这种方法实在是太慢了。那么，我们怎么才能有效的缩小搜索空间呢？

由于Uber的商业模型是以城市为中心的，我们并没有采用 R-tree 或 S2 等结构来索引地理围栏，而是采用了一个相对要简单很多的算法；商业规则以及相关的地理围栏都和城市相关。这使得我们可以采用层次式的方式来组织地理围栏——第一层是定义城市边界的围栏，而第二层是城市内的城市围栏。

对于每一次查询，我们首先线性扫描所有的边界城市围栏，找到目的城市。然后，我们采用另外一种线性扫描的方法来找到城市内的目标城市围栏。尽管新算法的复杂度仍然是 O(N) ，它却把N从万降到了百，大大减少了算法执行的复杂性。

架构

根据设计需求，我们希望这项服务是无状态的。因此，每一次请求都可以发送给任意的服务实例，并获得相同的结果。这意味着每一个服务实例都必须掌握全局信息，而非局部信息。我们采用了一种确定性的轮询调度策略，从而保证了不同服务实例的地理围栏数据都是同步的。这样，该服务的架构也非常简单。后台任务周期性地轮询来自不同数据源的数据。而这些数据就保存在主存中以服务不同的查询。同时，数据被串行保存在本地文件系统中，以实现系统重启时的快速引导。

Uber是如何基于Go语言构建高QPS服务的？

查询地理围栏服务的架构

处理Go存储模型

我们的服务架构需要对内存中的地理索引信息进行并行读写访问。在特殊情况下，后台轮询任务修改索引，而前台查询引擎同时从索引中读取信息。相比于利用单线程的Node.js进行服务编写的情况而言， Go存储模型必然会遇到挑战。尽管Go语言可以利用goroutine和 channel 自然的实现并行读写，其带来的性能影响不可忽视。我们试图利用 sync/atomic 包中的 StorePointerLoadPointer 原语来自己管理内存屏障。但是，这导致了代码难以理解和维护。

最终，我们选择了一种折衷的方式——利用读写锁来保证对地理索引的同步访问。为了减少锁的竞争，新的索引片段在被自动交换到主索引之前都是处于隐藏状态的。相比于 StorePointerLoadPointer 方法，这种锁会轻微增加查询延迟。但是，我们维护代码库的工作却变得简单很多，非常值得。

我们的经验

回首过往，我们非常开心选择了 Go 语言来编写我们的服务。其带来的好处包括：

高的设计效率。对于C++，Java或Node.js的开发者而言，学习Go语言只需要几天。而且代码维护工作也很简单。（这一切都是因为静态类型检查。）
高吞吐量和低延迟。在我们处理非中国区流量的数据中心中，该服务在40台机器35%的CPU利用率的情况下的最高QPS为170,000。其响应时间为95%的概率低于5ms，99%的概率低于50ms。
超级可信。从启动到现在，该服务正常运行的时间为总时间的99.99%。唯一的一次停止服务也是由初级编程错误和第三方库中的文件描述符泄露bug引起的。最重要的是，我们迄今为止没发现任何有关Go运行时的问题。