返回 登录
0

我们如何使用Go打造了Uber QPS最高的服务

阅读7167

原文:How We Built Uber Engineering’s Highest Query per Second Service Using Go
译者:孙薇

图片描述

2015年初,我们建立了一个微服务来负责这项任务:地理围栏查找(geofence lookups),结果完成很出色。如今已过一年,这项技术在Uber数以百计的生产应用中脱颖而出,成为了每秒查询量最高(QPS)的服务。本文讲述了我们建立这个服务的原因,还有近来Go语言对构建和扩展该服务速度的贡献。

背景

在Uber,地理围栏指的是地面上由人为定义的地理区域(或几何术语中的多边形),广泛用于地理位置的配置中。向用户展示在指定位置上有哪些产品可用,根据特定需求(比如机场)定义区域,在同时有多人请求搭车的周边区域执行动态定价,这些都非常重要。下图是位于科罗拉多州的一个地理围栏样例:

图片描述

第一步是检索地理位置的配置,根据用户的手机定位,查找经纬度之类的信息,以确定该位置处于哪个地理围栏中。这个功能曾经在多个服务/模块中都有实现,不过随着从单体架构迁移到面向(微)服务架构,我们选择将这个功能集成在新的单体微服务中。

准备出发!

根据我们的评估,那时最适合市场团队的语言是Node.js,因为我们在这种语言上有更多的内部知识和经验。但是,出于下面这些原因,Go更符合我们的需求:

  • 高吞吐量、低延迟的需求:从Uber移动应用发出的每个请求都需要查找地理围栏,而且必须在很短时间内(第99个百分位< 100毫秒)快速对大量(每秒成千上万个)查询作出响应;

  • CPU密集型的工作负载:地理围栏查找需要使用大量占用CPU资源的算法来查找点是否在多边形内(point-in-polygon)。尽管Node.js在输入/输出密集型的服务中使用效果良好,但由于Node本质上属于解释型动态类型的语言,在这种用例中并非最佳选择;

  • 无干扰后台加载:为了确保我们获取并执行查找的地理围栏数据是最新的,该服务必须后台读取多个来源的数据,持续刷新内存中的地理围栏数据。由于Node.js是单线程的,后台刷新会在相当长的时间内占用CPU(例如CPU密集型的JSON解析工作),从而延迟对查询的响应时间。对于Go来说这不是问题,用goroutines就可以通过多核CPU执行,后台任务与前台查询并行执行。

Geo索引:用还是不用,这是个问题

我们如何根据经纬度指定的位置,在成千上万个地理围栏中查找它属于其中的哪一个?使用简单匹配算法(brute-force)非常简单:只要一一查看所有地理围栏,并使用算法(比如光线投射算法)进行点是否在多边形内的比对。不过这个办法速度太慢。那么,如何有效地缩小搜索范围呢?

我们没有使用R-tree或复杂的S2算法,而是选择了更简单的办法来找出地理围栏:Uber的商业模型是以城市为中心的,其商业规则还有定义商业规则的地理围栏一般都与城市密切相关。这样我们就可以将地理围栏分为两种层级,第一层是城市地理围栏(定义城市边界的地理围栏),第二层是城市间的地理围栏。

每次查找,我们首先会通过线性扫描,查找所有的城市地理围栏,定位所在城市;然后再次通过线性扫描,找出其中包含的地理围栏。根据该解决方案的复杂程度,运行时长为O(n),n被大幅缩减到100s到10000s的数量级。

架构

我们希望这项服务是无状态的,以便适用于所有请求;同时在所有的服务实例中,每个请求的结果相同。这意味着每个服务实例都必须有全世界的信息,而不是某个分区的。我们使用确定性轮询调度,确保来自不同服务实例的地理围栏数据保持同步。这样一来,该服务的架构就非常简单了。后台任务定期对不同的数据库的地理围栏数据进行轮询,并将这些数据存储在主内存中,为查询提供服务;同时序列化到本地文件系统中,在服务重启时快速引导载入:
图片描述

上图是我们的地理围栏查找服务架构。

处理Go内存模型

我们的架构需要读取/写入并发访问内存中的geo索引,特别是:在前台查询引擎从索引读取时,后台轮询任务会对索引执行写入。对于习惯Node.js单线程的用户来说,Go的内存模型可能会构成挑战。在Go中,常用的方式是通过goroutines与channels同步并发读取/写入任务,出于对性能负面影响的担心,我们尝试使用sync/atomic数据包的StorePointer/LoadPointer基元自行管理内存屏障,却导致代码脆弱且难以维护。

最后我们进行了妥协,使用读写锁来同步到geo索引的访问。为了将锁定等待的时间减到最短,在转到主索引之前,我们另外构建了新的索引区段为查询提供服务。使用锁定导致查询的延迟相对于StorePointer/LoadPointer的办法来说有稍许增加,不过在我们看来利大于弊:代码简单化和可维护性的好处值得用稍许性能来换。

我们的经验

回顾之前的工作,我们非常庆幸选择了Go这种新语言来编写服务。

优势:

  • 开发人员工作效率很高:C++、Java或Node.js开发人员一般只需数日便可学会使用Go语言,而且这种语言的代码易于维护。(多亏了这种语言是静态类型的,免去了很多猜测和意外)。

  • 吞吐量和延迟表现都很好:仅在我们服务于非中国区的主数据中心上,在2015年新年前夜,该服务所处理查询数据的峰值负载就达到每秒查询量(QPS)17万,40台机器都占用了35%的CPU。第95个百分位响应时间小于5毫秒,第99个百分位响应时间小于50毫秒。

  • 超级可靠:从一开始该服务的正常运行时间就达到99.99%。唯一一次停机是由于初学者的编程错误,一个文件描述符将bug引入第三方数据库。重要的是:在Go运行时我们还没发现什么问题。

下一步的未来

尽管之前Uber的服务大多使用Node.js和Python,但Go语言逐渐成为许多Uber工程服务的新选择。


(责编/钱曙光,关注架构和算法领域,寻求报道或者投稿请发邮件qianshg@csdn.net,交流探讨可加微信qshuguang2008,备注姓名+公司+职位)

「CSDN 高级架构师群」,内有诸多知名互联网公司的大牛架构师,欢迎架构师加微信qshuguang2008入群,备注姓名+公司+职位。

评论