分布式缓存设计的评估
让我们根据我们的要求评估我们的设计。
让我们根据设计要求评估我们提出的设计。
高性能
以下是我们做出的一些有助于提高整体性能的设计选择：
- 我们使用了一致性哈希。在该算法下查找key需要时间复杂度为O(log(N))，其中N代表缓存分片的个数。
- 在缓存服务器内部，使用平均需要恒定时间的哈希表来定位键。
- LRU 逐出方法使用恒定时间访问和更新双向链表中的缓存条目。
- 缓存客户端和服务器之间的通信是通过TCP和UDP协议完成的，速度也非常快。
- 由于我们添加了更多的副本，这些可以减少我们在单台机器上有高请求负载时必须面对的性能损失。
- 该设计的一个重要特性是从 RAM 添加、检索和提供数据。因此，执行这些操作的延迟非常低。
提示
高性能的一个关键参数是驱逐算法的选择，因为缓存命中和未命中的数量取决于它。缓存命中率越高，性能越好。
为了了解驱逐算法的重要性，我们假设如下：
- 缓存命中服务时间 ( -百分位数）：5 毫秒
- 缓存未命中服务时间( -百分位数：30 毫秒（这包括从数据库获取数据和设置缓存的时间）
假设使用最常用 (MFU) 算法的缓存未命中率为 10%，而使用 LRU 算法的缓存未命中率为 5%。然后，我们使用以下公式：
在这里，这意味着以下内容：
：有效访问时间。
：发生缓存命中的次数百分比。
：发生高速缓存未命中的次数百分比。
：服务缓存命中所需的时间。
：服务缓存未命中所需的时间。
对于 MFU，我们看到以下内容：
对于 LRU，我们看到以下内容：
上面的数字突出了驱逐算法对提高缓存命中率的重要性。每个应用程序都应进行实证研究，以确定为特定工作负载提供更好结果的驱逐算法。
可扩展性
我们可以根据需求和不断变化的服务器负载创建分片。当我们向集群添加新的缓存服务器时，由于一致性哈希，我们还必须进行有限数量的重新哈希计算。
添加副本可以减少热分片上的负载。处理热键问题的另一种方法是在这些键的范围内进行进一步的分片。虽然单个键成为热键的情况很少见，但缓存客户端有可能设计解决方案来避免单个热键争用问题。例如，缓存客户端可以智能地避免单个键成为瓶颈的情况，或者我们可以对特定键使用动态复制方法。尽管如此，解决方案很复杂，超出了本课的范围。
高可用性
我们通过冗余缓存服务器提高了可用性。冗余为我们的设计增加了一层可靠性和容错能力。我们还使用了 leader-follower 算法 来方便地管理集群分片。但是，我们还没有实现高可用性，因为我们有两个分片副本，目前，我们假设副本位于数据中心内。
通过将领导服务器和跟随服务器分配到不同的数据中心，可以实现更高的可用性。但这种高可用性是以一致性为代价的。我们假设在同一个数据中心内进行同步写入。但是在不同数据中心同步写入强一致性会严重影响性能，这在缓存系统中是不受欢迎的。我们通常使用跨数据中心的异步复制。
对于数据中心内的复制，我们可以获得强一致性和良好的性能。我们可以妥协跨数据中心复制的强一致性以实现更好的可用性（参见 CAP 和 PACELC 定理）。
注释:CAP定理（CAP theorem），又被称作布鲁尔定理（Brewer's theorem），它指出对于一个分布式系统来说，不可能同时满足以下三点：
一致性（Consistency)（所有节点在同一时间具有相同的数据）。
可用性（Availability）（保证每个请求不管成功或者失败都有响应）。
分区容错性（Partition tolerance）（系统中任意信息的丢失或失败不会影响系统的继续运作）。
根据定理，分布式系统只能满足三项中的两项而不可能满足全部三项。
PACELC理论是建立在CAP理论之上的，二者都描述了一致性(Consistency)、可用性(Availability)和分区容忍性(Partition Tolerance)之间的约束与取舍。而PACELC理论则更进一步描述了即使在没有Partition的场景下，也存在Latency和Consistency之间的取舍，从而为分布式系统的Consistency模型提供了一个更为完整的理论依据。
一致性
可以以同步或异步模式将数据写入缓存服务器。在缓存的情况下，异步模式有利于提高性能。因此，我们的缓存系统存在不一致问题。或者，强一致性来自同步写入，但这会增加整体延迟，并且性能会受到影响。
不一致也可能由错误的配置文件和服务引起。想象这样一个场景，缓存服务器在写入操作期间宕机，并且在其恢复后立即对其执行读取操作。我们可以通过在合理确定它是最新的之前不允许它为请求提供服务来避免任何加入或重新加入服务器的这种情况。
负担能力
我们提出的设计成本低，因为使用商品硬件创建这样的系统是可行且实用的。
思考要点
警告
问题一:
如果领导者节点在领导者-跟随者协议中失败会怎样？ 在这种情况下可以使用两种可能的解决方案： 使用领导者选举算法从一组可用的追随者中选出一个新的领导者。 使用单独的分布式配置管理服务来监控和选择领导者。
问题二:
向缓存服务器引入同步复制是个好主意吗？
缓存集群上的同步复制会带来性能损失，因为将相同数据复制到所有缓存服务器需要时间。因此，在异步复制和同步复制的使用中分别需要在性能和一致性之间进行权衡。 答案取决于用例。对于缓存服务器，如果复制服务器与主服务器非常接近，同步复制是一个不错的选择。
问题三:
假设大量并发请求被转发到单个分片服务器。如果服务器使用 LRU 算法，有些请求会导致缓存未命中并向缓存写入新条目，而有些请求会导致缓存命中并最终从服务器读取。这些并发请求可能相互竞争。因此，可能需要一些锁定机制。但是，为所有读写操作锁定整个数据结构将大大降低性能。您认为将如何处理这样的问题？ 隐藏答案 通常，对于共享数据的并发访问，信号量、监视器、互斥锁等一些锁定机制是不错的选择。但是随着用户数量（缓存命中时读取器或缓存未命中时写入器）的增长，锁定整个数据结构并不是一个合适的解决方案。在这种情况下，我们可以考虑以下选项： 有限锁定：在这种策略中，只有整个数据结构的特定部分才会被锁定。虽然一些线程或进程可以同时读取数据结构，但一些线程可能会暂时阻止对数据结构的特定部分的访问。 离线驱逐：离线驱逐可能是一种可能性，而不是对数据结构进行实际更改，只有在执行不同操作时才会记录所需的更改，直到有必要提交更改。如果高速缓存命中率很高，则此解决方案是理想且简单的，因为发生高速缓存未命中时可能需要更改数据结构。 无锁实现：已经提出了多种解决方案，表明双向链表的同时读写是可行的，可以支持大量并发读写。
摘要
我们研究了缓存的基础知识，并设计了具有良好可用性、高性能、高可扩展性和低成本的分布式缓存。我们的机制使用副本维持高可用性，但如果所有副本都在一个数据中心，这样的方案将无法解决整个数据中心的故障。现在我们已经了解了设计的基础知识，让我们探索流行的开源框架，如 Memcached 和 Redis。