平稳扩展：可支持RevenueCat每日12亿次API请求的缓存
本文介绍了RevenueCat的缓存设计方案，涉及到缓存的一致性和高可靠性，译自：Scaling smoothly: RevenueCat’s data-caching techniques for 1.2 billion daily API requests
在RevenueCat，每天需要处理12亿条请求，为此，我们要实现以下两点：
- 在多个web服务器之间执行负载分担
- 使用缓存加速访问，并保障后端系统和数据存储。
缓存系统由多个配置了大量ram和网络容量的服务器组成，为了实现快速检索，将数据存储到内存或闪存中。缓存服务器是key-value类型的，且大部分是memcached。为了保证快速且简易，服务器之间通常不会共享任何内容，即一个key-value存储不会依赖其他系统，由客户端来选择使用哪个服务器来存储或检索数据。客户端通常使用哈希对不同的key进行分片，并将其分布到对应的缓存服务器上，以此来分发数据并达到负载均衡。
缓存系统需要实现如下三点：
- 低延迟：缓存必须要足够快。如果缓存服务器出现故障(如服务器没有响应)，则不能尝试重新和缓存服务器建立新的连接，否则，一旦积累了成千上万个请求，则可能会导致web服务器卡死。
- Up and warm：缓存需要在线，并保存大部分热点数据。如果缓存失败，则会导致后端系统过载
- 一致性：缓存不能持有过期或错误的数据
本文的实现主要是围绕memcached开发的，其实现key参考源码，但文中讨论的技术点也适用于其他缓存场景。
低延迟
建立连接池
相对于缓存操作来说，TCP连接的建立要慢的多。TCP握手需要2-3个额外的报文，以及到缓存服务器的一次往返报文。
- 缓存服务器通常受网络流量的限制，因此降低报文数量非常重要
- 由于缓存响应来自内存，因此速度非常快(约为100us)，而相同AZ的网络往返时间约为500~700us，因此网络占响应的主导因素。如果加上连接建立的时间，则几乎会让响应时间翻倍。
我们的缓存客户端创建了一个连接池，可以配置启动时创建的连接数以及连接池可以包含的最大连接数。你可能需要设置最佳缓存连接数，防止在峰值时频繁创建新的连接。
故障检测
有时候缓存服务器会无法响应，这通常是因为一些小问题导致的，如短暂的网络问题，短暂的流量峰值等。通常可以通过重试缓存操作来完成任务，但风险也极大。如果缓存无法在短时间内恢复，此时重试操作可能会影响到整个服务基础设施。
考虑如下场景：
假设一个服务器每秒接收1000个请求，其中缓存处理95%的请求，DB处理5%的请求。缓存处理一个请求的时间约10ms，DB处理一个请求的时间约50ms，因此平均响应时间为12ms，服务器平均并发处理的请求数为12。
如果一个缓存服务器无法响应，则需要考虑重试请求，此时有两种选择：
- 立即重试： 如果采用立即重试的方式，则会使缓存的请求翻倍。如果服务器因为过载而无法响应，这种方式将会继续加重服务器的负载，导致其无法恢复。如果服务器是因为事务原因无法响应，此·时也会遇到相同的问题。在尝试重试之前，通常需要等待一段时间。
- 在一小段时间后重试： 假设等待时间为100ms，重试的请求可能会多次命中相同的缓存服务器，假设仅命中一次，并假设只有25%的请求需要从该缓存服务器上检索数据，此时延迟增加为100ms*25/100=25ms，即原始的延迟增加了3倍，这也意味着服务器的容量需要增加3倍。在这种情况下，单个服务器将无法承受这种规模的流量，数据库的连接速度会变慢，进而导致请求变慢，如果缓存出现故障，会进一步增加服务器的负载。在负载过重的情况下，一次100毫秒的等待重试可就以让整个服务器群崩溃。
如果缓存服务器无法响应，此时应该执行故障检测，认为缓存出现miss，并继续执行下一步操作，不要执行缓存重试。
再进一步，可以在一段时间内将其标记为故障，且在这段时间不再连接到该缓存服务器。TCP是面向连接的协议，它内部存在很多超时机制，因此可以将其认为是潜在的"等待时间"。
总结一下，如何实现低延迟：
- 设置较低的超时时间：设置较低的连接和接收超时时间，这样可以更快地认为一个服务器出现故障，防止长时间等待响应。缓存延迟非常稳定，P99很低，这要归功于服务器只使用了RAM，因此可以激进地将其认为是100ms。
- 故障检测&标记：出现故障时，客户端可以在一段时间内(几秒)将服务器标记为宕机。此时可以使用连接池内的健康连接，如果没有，则应该将该请求标记为失败并退出，不应该尝试创建新的连接。
- 将故障认为是缓存miss，应用应该回退到使用源数据。
Up and warm
服务器无法一直在线，你需要假设它们可能会出现故障，并给出应对方式。 此外还需要保证能够使用大部分热点数据来预热缓存池。你需要监控缓存命中率，保证缓存有足够的容量来处理热点数据。此外重启服务器会丢失数据，这对如何操作缓存服务器组施加了很多限制。 下面介绍RevenueCat如何保证缓存在线和预热。
对故障做出规划
服务器会产生故障，那么该如何最小化故障影响？你可能需要增加很多缓存服务器，缓存服务器的数据越多，单个缓存服务器宕机产生的影响就越小。但过多的缓存也增加了成本压力，且浪费资源。下面是缓存服务器数据对故障的影响对比图：
可以看到，当存在大量小型的缓存服务器时，的确可以降低单个服务器故障所造成的影响。 但小的缓存服务器也会带来hot keys的问题。当一个请求占比较大时，包含该请求key的服务器的负载要远大于其他服务器，可能会导致处理饱和等问题。而如果缓存服务器较大，则hot keys并不会给整体负载带来的巨大偏差。
缓存服务器数量和大小的划分取决于一系列因素，如容量、访问模式、流量等等。 总之，你需要了解后端的容量，并设计缓存层，确保在至少2个缓存服务器宕机的情况下仍然能够正常运作。如果对后端进行了分片，则需要确保缓存和后端的分片是正交的，这样一台缓存服务器宕机造成的影响会分散到所有后端服务器上，而不会造成某台服务器的高负载。
备用缓存池
缓存服务器会处理大量流量，但如果为了在两台缓存服务器宕机的情况下正常运作，而采取增加后端实例的做法，是一种过度扩展。下面给出了一些"备用"缓存集群的方式，如果一个服务器出现故障，则客户端可以尝试连接到备用缓存池。
镜像池(mirrored pool)
镜像池中，数据会写入两个缓存池中，由于它们的数据是同步且预热的，因此可以在需要的时候从备用缓存池中读取数据。
镜像池应该采用不同的"salt"(hash中使用的随机字符串)，这样当一个缓存池中的服务器宕机后，该服务器的keyspace会以不同的方式分布到备用缓存池中，备用缓存池中的所有服务器都会获得一部分keyspace。如果使用相同的salt，则会使备用缓存池中的某个服务器的负载翻倍，进而导致过载甚至级联故障。
这种方式的主要缺点是成本，在内存中保存大量数据的方式本身就很昂贵，更不用说保存两份相同的数据。但如果在不同的AZ中运行web服务器时就可以采用这种方式(每个AZ有一份自己的缓存池)。由于请求会首先到本AZ的缓存上，这样既保证了请求速度，也降低了跨AZ传输带来的延迟，通过这种方式也抵消了重复数据带来的成本。
排水池(Gutter pool)
排水池是一个小型的缓存池，当主缓存池的缓存服务器出现故障后，作为一个临时存储。你需要为其设置一个很短的TTL，如10s。这样就可以缓存请求最热点的数据，防止请求到达后端服务，以此来降低后端所需的容量。 由于配置了较小的TTL，因此它不像镜像池那样可以有效降低后端压力，但它不需要保证双写的一致性，因此更容易维护，也更简单经济。
专有缓存池
Memcache非常简单，所有的数据都归属于相同的keyspace，数据被划分为块，称为slabs，每个slab用于固定大小的数据。当Memcache的内存耗尽后，它会采用LRU的方式释放内存，以此来接纳新的数据。但有时需要将一个块从一个容量更改为另一个容量，从而需要清除整个块；而有时在接收到新的大小的数据时，由于没有太多专门适用于它的slab，导致这些数据很快被(从缓存中)驱逐出去。
简单地说，难以控制缓存中应该保存哪些数据。有时你需要预热特定的数据集，特别是一些计算成本较大的数据或驱逐后会导致不精确的计数器。 最好的方式就是为特定场景创建特定的缓存池，这样就可以保证关键场景拥有足够的缓存容量。你需要持续监测每种场景下的缓存命中率，并据此来创建缓存池或特定的缓存服务器。
这种方式的唯一缺点是，web服务器需要为每个池中的每个缓存服务器创建对应的连接。可以采用代理的方式降低打开的连接数目。
Hot keys
在现实场景中，某些keys或变成hot keys，最典型的例子是，当需要从每个请求、某些限速器或大客户的API密钥中拉取配置时...
在一些极端场景中，一个单独的memcache都无法处理一个请求的key。下面是一个业界使用的解决方案：
- 分割key：使用版本的方式对key进行分片。例如将keyX变为keyX/1, keyX/2, keyX/3等，每个子key将被放到不同的服务器上。客户端会从一个服务器读取数据(通常取决于client id)，但会写到所有服务器上，以此来保证数据的一致性。这种方式最难的部分在于，如何探测hot keys，如何构建pipeline来让所有客户端知道需要切分哪些keys，切成多少块，以及如何协调所有客户端在同一时间执行操作，避免不一致。由于hot keys通常是由真实事件或某些趋势触发的，因此它们并不是静态的，你需要快速完成上述操作。
- 本地缓存：这是一种在客户端探测hot keys并缓存到本地的简单机制。由于本地缓存不提供一致性保证，因此比较适用于那些极少变更的数据。通过设置较低的TTL并选择合适的缓存keys，可以找到一个可接受的折衷方案。memcache的 meta-command 协议可以帮助找到hot keys，它支持返回上次访问key的时间，并且可以实现基于概率的热点缓存。如果你看到一个key在过去X秒内被访问了很多次，则说明它是hot key。
惊群效应(thundering herds)
如果一个hot key过期或被删除时，所有的web服务器会触发缓存miss，并同时从后端服务器获取数据，可能会导致负载峰值，增加请求延迟和处理饱和度，进而级联回整个web服务层。
在RevenueCat中，我们通常会在写时保证缓存的一致性，以此来降低惊群效应。除此之外还有其他缓存模式：
- 设置低TTLs：使用一个相对较小的TTL来刷新缓存周期，适用于非用户数据，如配置。
- 使缓存失效：例如可以流式修改DB，并使缓存中的数据失效。
这些模式下，如果keys过期或设置失效的是hot key，则可能会因为惊群效应导致很多问题
我们的meta-memcache库提供了如下两种实现来避免这些问题：
- 重缓存(Recache)策略：使用重缓存TTL来实现重缓存策略。当剩余的TTL<给定的值，其中一个客户端会返回缓存miss，并更新缓存的值，而其他客户端则可以继续使用现有的值
- 过期策略：在删除命令中，可以选择性地将key标记为过期，并触发上述机制：某个客户端会返回缓存miss并更新缓存的值，其他客户端则继续使用老的值。
惊群效应还有第三种场景：当驱逐一个大量请求的key时。归功于memcache的LRU缓存过期方式，这种情况通常很少见，但不代表不会发生，如缓存服务器重启时。此时会出现大量请求miss，所有的web服务器会同一时间请求后端服务器。我们提供了一种Lease(租赁)策略。和上面策略类似，只有一个客户端有权重置缓存值，但此时其他客户端不再使用老的数据，它们会等待缓存更新。上面我们讨论过等待缓存带来的风险，但这种方式对后端的影响也非常大，因此使用这种策略时需要了解它带来的影响。
重分片
有时缓存集群的容量会被耗尽，如果在此时新增数据，会导致从缓存中驱逐老的数据，命中率下降，负载增大。
通常解决这种问题的方式是增加更多的服务器，但这种方式可能会影响客户端对数据的分片，因此需要特别小心。根据采用的分片机制，你可能需要重新调整所有的keyspace，但这会使所有的缓存失效。
为了避免这种情况，你可以采用一致性哈希算法，该算法会维护大部分keys的位置，只会变更新增服务器百分比范围内的keys。
迁移
有时候需要更换缓存服务器，此时可以采取每次替换一个的方式，并在替换后给缓存留出预热的时间，但这种方式非常耗费时间，而且可能导致问题。 有次我们接收到云厂商的维护通告，即需要在一周内重启我们的缓存服务器，因此我们为缓存客户端制定了一个迁移策略。
它会执行一个客户端驱动的平滑迁移流程：
- 预热目标缓存池，通过镜像方式将数据写入该缓存池
- 将部分到原缓存池的读操作同步到目标缓存池，此时可以预热所读取的数据
- 在某个时候完成足够的缓存预热后，就可以将所有的读操作转移到新的缓存池，此时仍然保证缓存池双写。通过这种方式可以保证数据一致，在目标缓存预热不充分或出现过载问题时可以选择回退
- 最后将流量全部迁移到目标缓存池后，就可以删除原始缓存池
该流程是通过迁移客户端所接收的配置进行的：迁移模式和迁移阶段开始时间(使用时间戳表示)的映射，以此来协调所有服务器，并在同一时间改变行为。注意，需要确保所有服务器的时间是同步的，以保持毫秒范围内的时间偏差。
为了保证高度一致性，一开始只需将新增的读操作(目前不存在的)发送到目标缓存池，这样可以避免和写操作竞争。同时这部分读操作采用了no-reply模式，即不会关心也不会等待响应，避免增加额外的请求延迟。
一些非幂等的操作，如计数器或锁等都无法保证一致性的操作都不应该复制到目标缓存池，且这些数据通常也不需要预热。
这种迁移客户端的方式帮助我们在2-3小时内使用16台服务器替换了完整的集群，保证了高命中率，且对数据库的影响很低，对最终用户也没有明显的影响。
一致性
除了缓存服务器，我们还有很多web服务器来处理并发流量，即使一个web服务器，它也可以在多个CPU上并发处理请求，这意味着可能会出现缓存一致性问题。 一个导致一致性问题的例子如下：
在上面例子中，一开始缓存是空的：
- Web server1 尝试读取缓存，返回miss，然后回退到DB读取数据，读取到数据"red"并尝试回填到缓存中
- Web server2 正好执行一个写操作，需要将数据设置为"green"，并同时更新DB和缓存
缓存写入时机的不同会导致不同的结果。如果缓存的数据和DB不匹配，则表示发生了数据不一致。
你可能觉得只要将缓存回填操作从"set"改为"add"就可以了，只有在缓存为空的时候才能执行"add"操作。这种方式可以解决上述场景中的问题，但无法涵盖其他场景：
- Web server1可能会写入失败、超时、丢失或缓存服务器宕机，导致无法更新缓存，此时可以执行"add"操作，但数据仍然是旧的
- 可能存在滞后的数据库副本，在回填操作之间引入竞争。
我们的meta-memcache库支持很多底层meta命令，用于处理一致性和高吞吐量问题：
- compare-and-swap：检测写数据竞争，在读取时会获取到一个token，并在写入时携带该token，如果在读取后修改了该值，则token将不匹配，写入失败。
- leases：只有一个客户端有权更新缓存。Memcache可以标记缓存miss，这样其他客户端就知道当前有另一个客户端正在更新缓存，而不会相互竞争。
- 使用重缓存策略实现stale-while-revalidate：在一个客户端更新缓存的同时，其他客户端可以使用老的数值
- 标记过期：相比删除一个key，你可以将其标记为过期，这样某个客户端就可以更新缓存。注意需要重新校验缓存，并防止发生惊群效应。
- 较低的TTLs：使用较低的TTL可以确保在key过期前刷新它。
- 写入失败跟踪：跟踪写入错误
这里我们只列举了保证缓存一致性的常见策略。
写入失败跟踪
写入失败通常表示缓存出现了不一致，无法写入期望的数据，此时缓存状态不明，可能出现了错误。
正如前面所述，在处理缓存时重试缓存可能会造成短时间的性能问题，甚至产生级联错误。
我们的策略是在第一时间抛出错误，并记录写入失败的keys。我们的缓存客户端会注册一个写入失败处理器，它会收集这些密钥，消除重复数据，并让每个报告的keys对应的缓存至少失效一次。
通过这种简单的机制可以认为写入总是成功的，大大简化了CRUD操作中的缓存一致性。
两个存储中的CRUD一致性
在写入数据时，你需要同时更新DB和缓存，以保证一致性。由于数据库通常提供了事务的概念，因此两个存储会面临如何保证一致性的复杂问题。
我们已经实现了访问数据的CRUD策略，它们实现了高度一致的缓存机制，并且可以很容易重用，只需要配置行为、数据源等。我们强烈建议为CRUD访问构建抽象，抽象掉更新DB和缓存的细微差别，这样产品工程师就可以关注业务逻辑，并且这些策略经过长期实践，可以安全地使用。
下面介绍我们是如何实现高度一致性缓存的CRUD操作。
READ
首选尝试读取缓存，如果缓存miss，则从DB中读取，并回填到缓存中。
为了防止并发写入导致的竞争，我们采用"新增"的方式执行缓存回填操作。
并发回填产生的竞争问题不大，即使某些缓存副本的数据存在滞后。如果读取了旧的数据，这是因为该数据刚刚被刷新，且很快会有缓存写入来修复该问题。如果写入失败，则写入失败跟踪器会保证让受影响的keys失效。
还有可能发生缓存写入正常工作，但key却立马失效，以及从老的读取操作中回填缓存的场景，对于这些场景的处理方式为：
- 将缓存keys嵌入到DB事务中(postgresql允许在WAL中写入用户数据，mysql允许嵌入一些元数据作为查询注释)，然后，在读取副本成功后，让WAL/binlog尾部的keys失效。
- 设置更新延迟，使延迟时间超过副本滞后时间，类似于写入失败跟踪器。
幸运的是，副本的延迟通常小于100ms，因此缓存被驱逐的概率通常也比较小，我们不需要实现这些功能。
UPDATE
更新DB和缓存的方式有：
- 首先写入DB，然后写入缓存。缓存写入可能会全部失败，即使是写入失败跟踪器也可能会产生故障。这样在DB提交之后会阻塞服务器。
- 如果反过来，如果DB写入失败，则缓存会具有新的数据，导致数据不一致。
我们在缓存操作前后实现了一些策略：
- 缓存写入前：降低缓存TTL到某个值，如30s
- 写入DB
- 缓存写入后：更新缓存数值
考虑如下场景：
- 步骤1和2之间产生故障：此时DB没有变更，缓存也是一致的。缓存会通过降低TTL被回填。
- 步骤2和3之间产生故障：在写入DB之后，并没有更新缓存，此时老数据会被保留一段时间，但由于降低了TTL的缘故，该数据会很快过期，并被新数据填充。
- 我们还会记录写入失败(降低TTL还考虑到了写入失败的场景)，因此如果因为某种原因出现缓存写入失败时，我们会在缓存服务器可用时，使受影响的keys失效，以保证一致性。
总之，在DB操作前降低TTL是一种简单有效地实现高一致性更新的方式。
CREATE
由于我们的id来自DB，而DB提供了避免竞争所需的序列化(id是唯一)。因此可以在DB写入后使用一个简单的"添加"操作。
DELETE
在我们的应用场景中不存在删除竞争，因此可以发起简单的删除操作。但由于删除操作并不会在缓存中留下任何踪迹，因此可能会产生回填竞争(特别是读取DB副本时出现较大延迟时)。你可以使用"删除标记"以及降低TTL来避免这种竞争。
