据报道，Uber 仅在过去4年的时间里，业务就激增了 38 倍。Uber 首席系统架构师Matt Ranney在一个非常有趣和详细的访谈《可扩展的 Uber 实时市场平台》中告诉我们 Uber 软件是如何工作的。
本次访谈中没有涉及你可能感兴趣的峰时定价（Surge pricing，译注：当Uber 平台上的车辆无法满足大量需求时，将提升费率来确保乘客的用车需求）。但我们了解到 Uber 的调度系统，他们如何实现地理空间索引、如何扩充系统、如何提高可用性和如何处理故障，例如在处理数据中心故障时，他们甚至会把司机电话作为一个外部分布式存储系统用于恢复系统。
访谈的总体印象是 Uber 成长得非常快速。很多他们选择的的架构是快速成长的结果，同时也想让组建不久的团队可以尽可能快地移动。因为他们的主要目标是让团队的工程速度尽可能得快，所以在后台使用了大量的技术。
在经历一个稍显混乱但非常成功的开端后，Uber 似乎学习到很多：他们的业务和他们需要做什么才能成功。他们早期的调度系统只是为了送人。由于 Uber 的使命成长为除了送人以外，还要处理箱子和杂物（编注：Uber 已涉及快递业务。请看伯乐在线的这篇《Uber 用大数据的惊艳方式》），他们的调度系统已经被抽象并构建在可靠的和智能的架构基础上。
虽然 Matt 认为他们的架构可能有点疯狂，使用一致性哈希环和 gossip 协议的想法非常适合他们的使用场景。
很难不被 Matt 干事业的激情所迷住。当谈到他们的调度系统——DISCO，他兴奋地说就像学校里的旅行推销员问题（traveling salesman problem）。这是一个很酷的计算机科学问题。虽然解决方案不是最优的，但这是现实世界中一个规模很大，要求实时性，由容错和可扩展的部件建立起来的问题。这是不是很酷？
让我们看看 Uber 内部是如何工作的。下面是我对 Matt’s 谈话的注释：
统计
Uber地理空间索引的目标是每秒一百万次写入，读取速度比写入速度快很多倍
调度系统有数以千计的节点
平台
Node.js （译者注：Node.js是一个开源的、跨平台的、用于服务器和网络应用的运行环境。Node.js应用用JavaScript编写）
Python 语言
Java 语言
Go 语言
iOS 和 Android 上的本机应用程序
微服务
Redis（译者注：Redis是一个开源、支持网络、基于内存、键值对存储的数据库，使用ANSI C编写。）
Postgres（译者注：PostgreSQL标榜自己是世界上最先进的开源数据库。）
MySQL 数据库
Riak （译者注：Riak是由技术公司basho开发的一个类Dynamo的分布式Key-Value系统。以分布式、水平扩展性、高容错性等特点著称。）
Twitter 公司提供基于 Redis的 Twemproxy （译者注：一个快速和轻量的代理）
谷歌的 S2 地理函数库
ringpop —— 一致哈西环
TChannel —— 网络多路复用和 RPC 帧协议 （译者注：RPC，Remote Procedure Call，远程过程调用）
Thrift （译者注：Thrift是一个跨语言的服务部署框架）
概述
Uber 是一个用来连接乘客和司机的运输平台。
挑战：实时匹配动态的需求和供给。在供给方面，司机可以自由地做他们想做到的任何事情。在需求方面，乘客可以随时要求运输服务。
Uber 的调度系统是一个实时的市场平台，通过移动电话来匹配司机和乘客。
新年前夕是 Uber 一年中最忙碌的时候。
很容易忘记这个行业如此之快地取得了巨大的进步。技术日新月异，更新换代也很快。二三十年前移动电话，互联网和 GPS 只在科学小说里出现，现在我们对这些早已习以为常。
架构概述
驱动了所有这些的原因是乘客和司机在他们的手机上运行本机应用程序。
后台主要是服务移动电话的流量。客户端通过移动数据和尽力而为的互联网和后台沟通。10 年前你可以想象有个基于移动数据的业务吗？而我们现在可以做这样的事情，太棒了。没有使用私有网络，没有花哨的 Q0S （服务质量），仅仅是开放的互联网。
客户端连接调度系统，它协调司机和乘客，供给和需求。
调度系统几乎都是用 node.js 编写的。
原来计划把它移植到 io.js 上，不过后来 io.js 和 node.js 合并了。
你可以用 javascript 做一些有趣的分布式系统的工作。
决不能低估激情带来的生产力，而且节点开发者都相当有激情。他们可以非常快速地完成很多事情。
整个 Uber 系统可能看上去相当简单。为什么你还需要这些子系统和这些人呢？只要它看上去是那样，那就是成功的标志。只要看上去他们很简单地完成了他们的工作，就有很多事情需要去做。
地图或 ETA（预期到达时间）。为了让调度做出更加智能的选择，必须要获取地图和路线信息。
街道地图和曾经的行驶时间可以用来预测当前的行驶时间。
语言很大程度上取决于系统集成。所以这里有 Python、C++ 和 Java。
服务。这里有大量的业务逻辑服务。
使用了一种微服务的方法。
大部分用 Python 编写。
数据库。使用了很多不同的数据库。
最老的系统是用 Postgres 编写的。
Redis 也使用了很多。有些是基于 Twemproxy。有些是基于一个客制化的集群系统。
MySQL 数据库
Uber 正在建立他们自己的分布式列存储，那是一堆精心策划的 MySQL 实例。
有些调度服务还停留在 Riak 上。
旅行后期的流水处理。一个旅行结束后要处理很多事情。
收集评分。
发邮件。
更新数据库。
安排支付。
用 Python 编写。
钱。Uber 集成了很多支付系统。
旧的调度系统
原有调度系统的局限性开始限制了公司的成长，不得不改变它。
尽管Joel Spolsky声称几乎整个系统都被重写了。但大部分其它系统没有被触及，甚至有些调度系统的服务也被保留下来。
旧系统是为专用客车运输所设计的，做了很多假设：
每个车辆一个乘客，不适用Uber Pool（拼车服务）。
运送人的想法深深嵌入到数据模型和接口里。这样限制了扩展到新的市场和产品上，比如运送食物和箱子。
最初的版本是按城市划分的。对于可扩展性而言是好的，因为每个城市可以独自运营。但当越来越多的城市加入，这变得越来越难以管理。城市有大有小，负载也不一样。
由于建造得很快，他们没有单点故障，都是多点故障。
新的调度系统
为了解决城市分片和支持更多产品，供给和需求的概念应该是广义的，所以供给服务和需求服务被创建出来。
供给服务跟踪所有供给的性能和状态机。
有很多属性模型可以跟踪车辆：座位数目、车辆类型、是否有儿童座椅、可以放进轮椅吗，诸如此类。
配置需要被追踪。例如，一辆车可能有三个座位但是有两个都被占用了。
需求服务跟踪需求、订单和需求的方方面面。
如果一名乘客要求一个小车座位，库存必须满足需求。
如果一名乘客为了更便宜的价钱，不介意和别人分享一辆车，这也是要建模的。
如果需要移动一个箱子，或者递送食物呢？
匹配所有供给和需求的逻辑是一个被称为 DISCO（调度优化）的服务。
旧系统只匹配当前可用的供给，这意味着当前路上等着工作的车辆。
DISCO 支持未来规划和使用可用的信息。例如，在旅行过程中修改路线。
geo 供给。基于供给来自哪里和哪里需要它，DISCO 需要一个地理空间索引做决策。
geo 需求。需求也需要一个 geo 索引。
要使用所有这些信息需要有一个更好的路由引擎。
调度
当车辆移动的位置更新被发送到 geo 供应商。为了匹配乘客和司机，或者仅是在地图上显示车辆，DISCO 发送一个请求给 geo 供应商。
geo 供应商先粗略过滤一遍，得到附近满足需求的候选人。
然后列表和需求发送给路线或 ETA（预计到达时间），以计算它们距离远近的ETA，是基于道路系统而不是地理上的。
根据 ETA 排序然后把它返回给供应商，再派给司机。
在机场，他们不得不模拟一个虚拟的出租车队列。考虑到他们到达的顺序，供应商必须被排队。
地理空间索引
必须有相当的可扩展性。设计目标是每秒处理一百万次写入。写入的速度源自司机每 4 秒 发送的移动更新。
读取速度的目标是要比写入速度快很多，因为每个打开应用的人都在进行读取操作。
通过一个简化的假设——仅跟踪可调度的供给，旧地理空间索引可以很好地工作。大部分供给正在忙着做其它事情，所以支持可用供给的子集就很容易。在为数不多的进程中，有一个全局索引存储在内存里。很容易做简单的匹配。
在新世界里必须跟踪所有状态下的供给。此外也必须跟踪它们涉及的路线。这是相当多的数据。
新的服务运行在好几百个进程上。
地球是一个球体。仅依靠经度和纬度很难做出总结和近似。所以 Uber 通过 Google S2 函数库将地球分割成微小的单元。每个单元有一个唯一的 ID。
可以通过一个 64 位整数（int64）代表地球上的每一平方厘米。Uber 使用一个等级为 12 的单元，根据你所在的位置，面积从3.31 到 6.38 平方公里。盒子根据它们在球体中的位置，改变它们的形状和大小。
S2 可以给出一个形状的覆盖面积是多大。如果你想以伦敦为中心画一个半径 1 公里的圆，S2 可以告诉你填充这块区域需要多少单元。
由于每个单元都有一个 ID，这个 ID 可以作为一个分区键。当供给到达一个位置，这个位置的单元ID 就知道了。可以用一个做为分区键的单元 ID来更新供给位置。然后发送多个副本。
当 DISCO 需要找到附近位置的供给，会以乘客所在位置为中心计算一个圆的面积。借助单元 ID，让所有在这个范围内的分区都反馈供给数据。
所有这些都是可扩展的。尽管它不像你想象得那样高效，但因为扇出相对便宜，写入负载总是可以通过增加更多的节点来加以扩充。读取负载可以通过使用复制来扩充。如果需要更大的读取能力，可以增加复制因子。（译者注：fanout，扇出，IC 概念，一个逻辑门在正常工作下，其输出端可接的同族系 IC门的数目，成为此门的扇出數。简单的说，其所能推動同种类的次级门的数目就称为扇出。）
一个限制条件是单元尺寸固定在等级 12 的大小。未来可能会支持动态的单元尺寸。但这需要权衡利弊，单元格越小，查询的扇出就越多。
路线
讨论完地理空间，我们来讨论路线的选择必须分级。
有一些主要目的：
减少空载（extra driving）。开车是人们的工作，他们希望可以更有效率。空载不会给他们带来收入（译者注：感觉此处有笔误）。理想情况下，司机一直在行驶中。一堆赚钱的工作排队等着他们。
减少等待。乘客等待要尽可能的短。
整体 ETA 最少。（整体预计到达时间）
旧系统让需求查询当前可用的供给，加以匹配并最终完成。这很容易实现和让人理解。这在专车运输下工作得相当好。
仅看当前可用的，不能做出好的选择。
其想法是一个正在运送乘客的司机可能更适合这位叫车的客户，因为目前空闲的司机距离比较远。挑选正在途中的司机减少了客户的等待时间，也让远程司机的空载时间降到最小。
在可预见的未来，这个模型可以更好地处理动态条件。
例如，一名客户附近刚好有一名司机上线，但是这个客户之前已经分派给另一位距离位置远一点的司机，这种情况下就不应该改变调度决策。
另一个例子是客户希望可以分享一辆车。通过在非常复杂的情况下尝试预测未来，可以进行更多的优化。
当考虑到运送箱子或者食物，所有这些决策会更加有趣。在这些情况下，人们通常会做其它事情，就需要有其他不同的考量。
可扩展的调度
调度使用 node.js 构建。
他们构建了一个有状态的服务，所以无状态的扩展方法不能工作。
Node 运行在一个单独进程上，所以必须想一些办法让 Node 可以运行在同一台机器的多个 CPU 上和多台机器上。
用 Javascript 重新实现所有 Erlang 的实现是个笑话。
扩展 Node 的一个解决方案是 ringpop，它是一个基于 gossip 协议的一致哈希环，实现了一种可扩展的和容错的应用层分区。
在 CAP 术语中，ringpop 是一个AP系统，权衡一致性和可用性。一些不一致性要比无法服务更好解释。最好是可以一直可用只是偶尔出错。
ringpop 是一个可以包含在每一 Node 进程的嵌入式模块。
Node 基于一个成员集合实现 gossip 。一旦所有节点相互认可，它们可以独立和高效地进行查询和转发的决策。
这是真正得可扩展。增加更多的进程可以完成更多的工作。这可以被用来切分数据，或作为一个分布的闭锁系统、或协调一个发布或者订阅的会合点、或者一个长时间轮询的 socket。
Gossip 协议一种基于可扩充可传导的弱一致性进程组成员协议（SWIM，Scalable Weakly-consistent Infection-style Process Group Membership Protocol）。为了提升收敛时间已经做了一些改善。
一系列在线的成员都在“传播流言”（gossip around 译注：双关用语）。当更多的节点加入，它就是可扩充的。SWIM 中的 “ S ” 代表可扩展的，并且的确可以工作。这可以扩展到数千个节点的程度。
SWIM结合了 健康检查和成员变更，并把它们作为协议的一部分。
在一个 ringpop 系统中，所有 Node 进程都包含 ringpop 模块。它们在当前成员中“传播流言”。
从外面看，如果 DISCO 想要使用地理空间，每个节点都是相等的。可以选择任意一个健康的节点。通过检查哈希环，接受请求的节点会负责把这个请求转发给正确的节点。如下图所示：
让这些跃点和对端可以相互沟通听上去很疯狂，但可以得到一些很好的特性，比如在任意机器上增加实例就可以扩充服务。
ringpop 的构建基于 Uber 自己的远程过程调用（RPC，Remote Procedure Call）机制，被称为 TChannel。
这是一个双向的请求和响应协议，它的灵感来自 Twitter 的 Finale。
一个重要的目标是控制跨不同语言的性能。特别是在 Node 和 Python中，很多现有的 RPC 机制不能很好地工作。 需要 redis 级别的性能。TChannel 已经比 HTTP 快 20 倍。
需要一个高性能的转发路径，这样中间层不需要知道整个负载，就可以很容易做出转发的决策。
需要适合的流水线，这样就不会有排头拥塞的问题，任何时候任何方向都可以发送请求和响应，每个客户端也是一个服务器。
需要嵌入负载检验、跟踪和一流的功能。在系统内处理中，每个请求都应该是可被跟踪的。
需要一个干净的脱离 HTTP 的方法。HTTP可以非常自然地被封装到 TChannel 里 。
Uber 正在远离 HTTP 和 Json 业务。都在迁往基于 TChannel 的 Thrift。
ringpop 基于持久连接的 TChannel 实现 gossip 协议 。同样这些持久连接被用来扩展或者转发应用流量。 TChannel 也被用来进行服务间的通信。
调度可用性
可用性很重要。Uber 有竞争对手而且切换成本非常低。如果 Uber 只是短暂挂掉，这些钱就会被其他人赚走。其他产品的粘性更强，客户也愿意再次尝试它们。 Uber 不一定如此。
让每件事情都可以重试。如果有些事情不能工作，那它就要可以重试。这就是如何绕过错误。这要求所有的请求是幂等的。例如一次调度的重试，不能调度两次或者刷两次某人的信用卡。 （译者注：一个幂等操作的特点是其任意多次执行所产生的影响均与一次执行的影响相同）
让每件事情都可以终止。失败是一个常见的情况。任意终止进程不应该造成损害。
只有崩溃。没有优雅的关闭。优雅的关闭不需要练习。需要练习的是当不遇期的事情发生了（要怎么办）。
小块。要把事情失败的成本降到最低就是把它们分成小块。可以在一个实例中处理全部流量，但如果它挂掉了怎么办？如果有两个，就算一个挂了，只是性能减半。所以服务要可以被拆分。这听上去像一个技术问题，但更像一个文化问题。很容易就拥有一对数据库。这是一件很自然的事情，但配对就不好。如果你能够自动发起一个和重新启动新的备用，随机终止它们是相当危险的。
终止一切。就算终止所有数据库来确保可以从失败中恢复过来。这需要改变数据库的使用策略。他们选择 Riak 而不是 MySQL。这也意味着使用 ringpop 而不是 redis。因为 redis 实例通常相当大和昂贵，终止一个 redis 实例是一个很昂贵的操作。
把它分成小块。谈到文化转变。通常服务 A 通过一个负载均衡器和服务 B 沟通。如果均衡器挂掉会怎样？你要如何处理这种情况？如果你没有练习过你永远都不知道。你应该终止负载均衡器。你如何绕过负载均衡器？负载均衡的逻辑已经在服务里面。客户端需要有一些信息知道如何绕过问题。这和 Finagle 的工作方式类似。
一个集群的 ringpop 节点创建了服务发现和路由系统，让整个系统有可扩展性和应对后台的压力。
整个数据中心的故障
虽然不会经常发生，但还是会出现一个意想不到的级联故障或者一个上游网络提供商的故障。
Uber 维护了一个备份的数据中心，通过适当的开关可以把所有事情都切换到备份的数据中心。
问题是在途的旅行数据可能不在备份的数据中心。他们会把司机手机当作旅行数据的源头而不是数据的副本。
结果调度系统会周期发送一个加密的状态摘要给司机的手机。现在假设有一个数据中心发生故障转移。司机手机下一次发送位置更新给调度系统，调度系统将会检测到它不知道这个旅行，它会问（手机）要状态摘要。然后调度系统根据状态摘要进行更新，这个旅行会继续就像什么事情都没有发生过。
不足之处
Uber 解决可扩展性和可用性问题的不足之处，可能在于 Node 处理转发请求和发送信息给大量扇出所带来的高延迟。
在一个扇出系统中，微小的波动和故障都会有惊人的影响。系统的扇出越高出现高延迟请求的机会就越大。
一个好的解决方案是可以跨服务器取消备份的请求。这个一流的功能已经内嵌到 TChannel 中。一个请求的信息同时发送给服务 B1 和 B2。发送给服务 B2 的请求会有些延迟。当 B1 完成这个请求，它会在 B2 上取消这个请求。由于这个延迟通常情况下 B2 不会工作。但如果 B1 出了问题，B2 就可以处理这个请求，这样会比 B1 先尝试超时后 B2 再尝试情况下的反馈要快一些。
更多背景请参考《Google的延迟容忍系统：用不可预测的部分得到一个可预测的整体》。
参考文章
S2map.com—— 查看 S2 覆盖面积和绘制图形
关于作者：至秦
