How to implement a distributed and auto-scalable WebSocket server architecture on Kubernetes一文中虽然解决是WebSocket长连接问题，但可以为其他长连接负载均衡场景提供参考价值
WebRTC 是一套开放web标准，用于在客户端之间建立(端到端方式的)直接通信。WebRTC signaling 是WebRTC协议的前置步骤，它依赖signaling server在需要建立WebRTC连接的客户端之间转发协商协议。客户端和signaling server之间的连接通常使用WebSockets。
signaling server保存了客户端的信息，其工作模式如下：
- 使用HTTP库启动一个WebSocket服务，用于监听客户端的注册(即后可以与其他客户端建立WebSocket连接)请求
- 维护一个内存关系结构(如哈希或字典)，将
clientId与其WebSocket进行映射 - 当接收到发起端的WebSocket消息(当然，必须指定
clientId)时，会在map中查找接收端的注册信息，然后通过WebSocket将数据转发给接收端。
伪代码实现如下：
// Global variable that maps each clientId to its associated Websocket. clientIdToWebsocketMap = new Map() function main() { // Start the server and listen to registration requests. server = new WebsocketServer() server.listen("/register", registerHandler) } function registerHandler(request) { // For example, the client can send their clientId as a query parameter. clientId = request.queryParams.get("clientId") websocket = request.acceptAndConvertToWebsocket() websocket.onReceiveMessage = onReceiveMessageHandler clientIdToWebsocketMap.insert(clientId, websocket) } function onReceiveMessageHandler(message) { // We assume the message parsing logic to extract the recipientId from the message is defined elsewhere. recipientId, body = parseMessage(message) clientIdToWebsocketMap.get(recipientId).send(body) }
上面例子仅描述了一个signaling server，但单台signaling server的能力有限，当需要多实例时，就会遇到kubernetes中的长连接负载均衡问题。在讨论如何解决该问题之前，需要明确连个目标：
- 分布式约束：系统必须保证发送方的消息能够被正确转发到期望的接收方，即使二者并没有注册到相同的实例上。
- 均衡约束：系统在实例增加或减少的情况下必须保证负载均衡。
经典的解决方式
使用pub/sub broker来解决分布式约束
网上的大部分方式都推荐使用一个Pub/Sub broker来实现实例间的交互，如下：
这种方式可以解决分布式约束问题，但有两个关键限制：
- 每个signaling实例都会读取其他实例发布的消息，这会导致读取的消息数量是实例数的平方，但平均只有1/N 的消息是有效的(即被接收方所在的实例接收到)，大部分消息都会被丢弃。
- 有可能还需要对pub/sub broker实现自动缩放功能，复杂且增加了开支。
解决均衡约束
大部分默认的负载均衡算法为round-robin，但这种方式适用于HTTP短连接，不能在自动扩缩容情况下均衡WebSocket连接。另外有一种least-connected算法，可以将WebSocket连接请求分配给具有最少active连接的实例。这种方式可以保证在扩容情况下达到最终均衡。
这种方案的问题是并不是所有的负载均衡器都支持least-connected负载均衡算法，如Nginx支持，但 GCP’s HTTP(S) 负载均衡器不支持，这种情况下可能要诉诸于比较笨拙的办法，如readiness probes：即让具有最多负载的signaling实例暂时处于Unready状态(此时endpoint controller会从所有service上移除该pod)，以此来阻止负载均衡器向该实例发送新的连接请求。
我们的解决方案：使用基于哈希的负载均衡算法
使用rendezvous 希解决分布性约束
基于哈希的负载均衡算法是一种确定均衡流量的方法，根据客户端请求中的内容(如header的值、请求或路径参数以及客户端IP等)来计算哈希值。有两种著名的哈希算法： 一致性哈希 和 rendezvous 哈希。这里我们选择了后者，原因是它更加简单，且均衡性更好。算法如下：
H(val, I) = I_i - H is the hash-based algorithm - val is the value (extracted from the request) from which the hash is computed - I = {I_1, I_2, ..., I_N} is the set of all backend instances - I_i is the backend instance that was "selected" by the algorithm
如果使用客户端的clientId作为参数val，那么就可以将每个客户端映射到特定的signaling实例上。此外，只要知道clientId和后端实例，就可以通过该函数了解到客户端和实例的对应关系，这也意味着，如果一个signaling实例接收到发起端的消息，但没有在本地找到接收端，此时就可以通过哈希算法知道接收端位于哪个实例上。下面看下具体实施步骤：
- 当接收到新的WebSocket连接请求时，使用请求中的
clientId作为rendezvous 哈希的入参。 - 每个signaling实例需要了解系统中的其他实例，这可以通过kubernetes中的Headless Service关联signaling deployment，然后调用Kubernetes Endpoints API获得实例地址。
- 当signaling I₁从一个发起端接收到WebSocket消息时，会从请求中读取接收端的
clientId，然后从本地查找接收端，如果找到，则通过WebSocket将消息转发给对端即可，如果没有找到，则使用rendezvous 哈希算法，并使用clientId作为val，signaling实例的IPs作为I，计算出接收端注册的实例I₂。如果 I₂ = I₁ ，说明接收端已经断开连接或从未注册，反之则直接将消息转发给 I₂ 。 - I₁ 转发给 I₂的方式有很多种，这里采用普通的HTTP请求作为实例间通信。我们采用批量发送的方式来减少HTTP请求数量。
解决均衡约束
使用基于哈希的负载均衡可以优雅地解决分布性约束，通过kubernetes Endpoint API也可以很容易地获取signaling实例的变动。rendezvous哈希的一个特点是，当添加或删除后端实例时，会改变函数的参数I，函数的返回值只会影响一部分数据(如果实例从N-1扩展为N，则平均影响1/N的数据)。
但在实例变更之后，谁去负责重新分配注册的客户端？下面有两种方式解决该问题：
1.强制客户端断开连接
当一个signaling实例Iᵢ通过kubernetes Engpoint API探测到扩缩容事件后，它会遍历本地注册的所有客户端，然后使用rendezvous哈希算法针对更新后的实例集中的每个clientId重新计算所有结果。理论上，计算出的部分新结果不属于Iᵢ，此时Iᵢ可以断开这部分客户端的WebSocket连接，如果客户端有重连机制，就会重新发起建链，当请求到达负载均衡器之后，会被分配到正确的signaling实例上。
扩容前
在扩容后，触发客户端重连
该方式比较简单，但存在一些弊端：
- 首先客户端需要有重连机制
- 其次会打断客户端会话
- 增加了signaling服务实现代码和周边架构的耦合
- 在每次扩缩容之后会增加请求峰值。
出于上述原因，我们放弃了这种方式。
2.负载均衡器本身中重新映射Websocket
这里我们自己实现了负载均衡器，但仅用于代理WebSocket的请求和消息，不处理如TLS和ALPN之类的功能(这部分由前置的负载均衡处理)。实现步骤如下：
- 通过kubernetes API来发现signaling实例，并实现rendezvous哈希逻辑。
- 配置一个基本的Websocket服务监听连接请求，并根据rendezvous哈希计算(客户端的clientId)的结果将请求路由到后端signaling实例，最后将响应返回给客户端。如果返回结果有效，则与该客户端创建两条WebSocket连接：一条从客户端到负载均衡器，另一条从负载均衡器到signaling实例。
- 当负载均衡器从 客户端-复杂均衡器 的WebSocket上接收到消息后，它会通过 负载均衡器-signaling 进行转发，反之亦然。
- 最后根据扩缩容实现WebSocket的映射逻辑：当负载均衡器通过kubernetes API检测到signaling实例变动时，它会遍历所有客户端及其当前代理Websocket的
clientId，然后使用rendezvous哈希算法并代入新的后端实例重新计算结果。当返回的实例与当前客户端注册的不一致，则负载均衡器只会断开与该客户端相关的 负载均衡器-signaling 之间的WebSocket，并重新建立一条到正确的signaling实例的 负载均衡器-signaling 链接。
总结
文中最后使用自实现的负载均衡器来缓解后端实例扩缩容对客户端的影响。需要注意的是，rendezvous哈希算法在扩容场景下不大友好，需要重新计算所有key(文中为clientId)的哈希值，因此在数据量大的情况下会造成一定的性能问题，因此适合数据量减小或缓存场景。
