1. 问题背景

会话保持是七层负载均衡的核心功能之一。对于同一会话的请求或者连接，通过会话保持机制，负载均衡软件会将其路由到同一个后端，以利用局部性原理来提高服务整体的效率。

在传统的 LB 产品之中，会话保持能力可以说是重中之重，比如 F5 软件就提供了丰富的会话保持机制供用户选择。而在云原生的场景当中，由于更多面向无状态的服务，服务实例动态启用和销毁，会话保持能力相对而言重要性有所降低。而作为云原生边缘网络代理，Envoy 在会话保持方面自然也相对薄弱。

在开源 Envoy 当中，只提供了基于一致性哈希的会话保持机制。具体来说，Envoy 提供了一个一致性哈希负载均衡算法进行流量的负载均衡。对于一组后端服务实例，Envoy 会根据服务实例名称或者地址来计算出一个哈希环。之后，对于每一个 HTTP 请求，Envoy 都会根据请求的特征计算一个哈希值，然后根据哈希值在后端哈希环中选择一个最合适的后端实例（通过折半查找）。该会话保持机制不需要保存额外的状态，最终结果只和计算所得的哈希值以及哈希环有关。此外，天然的，该会话保持机制也可以做到跨实例会话保持，也即是当拥有多个 Envoy 实例时，请求无论是由 Envoy A 实例转发或者是 Envoy B 实例转发，最终转发到的目标服务实例都是一致的。

Envoy 支持配置从不同的请求特征中计算哈希值，比如使用特定请求头，使用源地址 IP，或者使用 cookie 等。只要后端实例保持稳定，这一机制几乎是完美的。但是，事实上，后端实例并不总能够保持稳定，而且有一些特殊的场景，基于一致性哈希的负载均衡机制也无法实现。
因为基于一致性哈希的会话保持机制本质上是无状态会话保持。会话保持依赖的不是某个持续的状态值，而是算法实时计算的结果。

为了进一步的完善 Envoy 的会话保持能力，拓展 Envoy 的使用场景，比如在传统分布式系统中作为七层软负载均衡，轻舟微服务团队对 Envoy 负载均衡器做了进一步的增强，以支持有状态的会话保持机制。具体来说，有状态会话保持是为了解决以下问题：

保证当后端节点集状态发生变化时（节点被标记为 degrade 或者不健康、新增节点或者移除节点），属于已有会话的请求仍旧能够正确的路由到会话对应的节点。现有的基于一致性哈希的会话保持机制，当后端节点发生变化时，就会重新构造哈希环，导致会话保持的结果不稳定。
使得最小连接数等算法也能够具备会话保持能力。现有会话保持是构建在一致性哈希负载均衡算法的基础之上，但是如最小连接数，轮转等负载均衡算法不具备会话保持能力。
提高一致性哈希负载均衡策略的性能。一致性哈希算法通过折半查找的方法来找到合适的节点。如果使用有状态会话保持，可以有效的减少在具备大量节点时的节点搜索的开销。

2. 实例管理

要实现各种各样的负载均衡算法，自然需要实现对后端实例集合的管理，在 Envoy 中，为了实现后端实例的管理，使用了一个 PrioritySet 的数据类型。其主要的特点三个：

多优先级：一个 PrioritySet 包含多个优先级的多组后端实例；
数组结构：后端实例多以数组结构组织和管理；
线程隔离：每个线程中都有独立的 PrioritySet；

而要实现有状态会话保持，首先，必须要提供快速的实例搜索能力，这是开源 PrioritySet 并不具备的。为此，数据面扩展增强了 PrioritySet，在其中实现了一个以实例地址为 Key 的 HostMap，来提供跨优先级的快速搜索能力。

同时，为了尽可能的减小该项增强带来的额外内存开销，HostMap在各个线程的 PrioritySet 中共享。但是需要注意到，Envoy 特色功能之一就是可以动态更新后端实例列表，所以这个 HostMap 也需要更新（更新都在主线程中）并且面临线程安全问题。

一般来说，面对此类一写多读的数据更新，一个读写锁是一个不错的选择。但是在有状态会话保持中，HostMap 的搜索是高频操作，每个请求都是至少操作一次。而实例表更新则是一个相对来说非常低频的操作。为了一个低频的实例更新，而在每次请求中都引入一次读锁的开销，对于高性能网络代理来说，是很难让人接受的。所以为此需要设计一套机制来保证线程安全的实例更新的同时，保证搜索的无锁和高性能。

image.png

该机制简单原理如上所示，当需要更新实例表时，Envoy 会从已有的 HostMap 中创建一份拷贝，所有更新都在新的拷贝进行，而不是直接修改已有 HostMap，这样避免了已有的 HostMap 在多线程上读写的冲突。（当然，这并非毫无代价，每次更新都需要拷贝一次 HostMap，以主线程的拷贝开销换取工作现场的无锁操作）