一道滴滴的负载均衡前端面试题

这是之前我去面试滴滴时的一道面试题，它看起来可能不那么的偏前端，但我仍然觉得很有意思，我省略安全校验、意外错误处理等细节性的问题，单单来聊聊负载均衡相关的方面。当然了，我本身不是后端，这方面经验肯定不是十分足，欢迎各位赐教。

问题是这样的：我们要实现一个利用 WebSocket 进行实时通讯的基于 Web 的即时通讯应用，假设未来用户量会很大，我们要用到多个服务器，那我们如何实现两个用户间的通讯呢？

我们先来看看只有一台机器时的情况。

在连接上 WebSocket 后，我们会获得一个 Socket 对象，我们将该 Socket 对象放到一张映射表上存起来。之后，我们就可以根据该 Socket 对象所对应的 user 的 uuid 来获取到。

当 UserA 向 UserB 发送请求时，UserA 会在发送消息时携带上 UserB 的信息（比如 uuid），这样后端服务器就可以根据 UserA 提供的 UserB 的信息，从映射表中查到 UserB 对应的 Socket 对象，从而成功地向 UserB 发送消息。

用户量少的时候我们可以这样简单地用单台机器来处理，我们再来看看多台机器会遇到一些什么问题？

首先，我们面临的个问题就是：如何知道另一个用户在哪台服务器上？

我们可能个想法就是：所有机器都使用一张映射表，映射表里记录了每台机器都储存了哪些 Socket，当有新用户连接的时候，被负载均衡器分配到的服务器会向我们所有的其它服务器发送一条消息，以更新映射表，这样我们就成功地定位到了另一用户所在的服务器了。

但大家都会发现，这样的策略虽然简单，但非常的粗暴，当用户数和服务器数很多的时候，每次更新用户上下线都是一种很大的压力。

于是我们有了第二个想法：我们每台机器不再保存所有用户的映射，我们使用单台服务器（简称 S）来保存所有的用户映射，当某服务器需要寻找另一用户所在的服务器时，就向服务器 S 查询。

这样的策略显然是依赖单点服务器的，性能的瓶颈会在这单台服务器上。

回头一想，我们或许方向有点走错了，虽然我们要在单台机器上要依赖映射表，但在定位服务器时不一定也要用映射表啊！然后就是第三个想法：我们使用一种算法，来对 uuid 进行 hash，将得到的 hash 作为服务器的 ID 就可以了。

我们定义一个函数 hash，它接受一个参数 uuid，返回一个对应服务器的 ID：hash(uuid) => serverId。hash 函数我们用简单的算法 mod——也就是取模——来举例。比如我们有 6 台机器，uuid 为 7，那么我们的运算过程是这样的：hash(7) => mod(7, 6) => 1，于是我们就知道，uuid 为 7 的用户所在的服务器应该是 ID 为 1 的服务器。

这种方法可以让我们不再依赖单个节点。但它引入了新的问题：当我增加或减少机器数量的时候，会导致取模时的除数发生变化，这意味着我们需要把所有的在线用户进行重新计算，运算量非常庞大。

那么这个时候，杀手锏要来了：一致性哈希。

一致性哈希简单来讲，就是我们建立无数个虚拟节点（比如 2^32 个），把它们围成一个环状。然后，我们把一些真实的服务器放置在这些节点上，在执行 hash(uuid) 时，其除数为虚拟节点数，于是我们会得出一个虚拟节点的 ID，我们根据这个虚拟节点所在的位置，往后查找真实服务器，从而定位到用户所对应的服务器中。在增减服务器时，我们只需要移动很少量的对象（很少量的缓存会失效）。

关于一致性哈希，我找到一篇由 @刘梦馨 写的《聊聊一致性哈希》，这篇文章讲解得非常的通俗易懂，大家想了解更多关于一致性哈希的话建议大家去阅读。

参考文献：

• 一致哈希 - 维基百科
  
• 聊聊一致性哈希 - 知乎专栏
• 题图：ZStack 的伸缩性秘密（第二部分）无状态服务