算法题复盘

发表于 2020-12-13 更新于 2024-01-31 分类于算法

以前做leetcode时积累了不少比较经典的问题，但是很少总结，经常做一道是一道，效率颇低，而且应付面试经常会碰到挺熟但还是被“卡住”的情况，遂做一总结。

只摘出Medium和Hard问题。
有的题可以有多个分类，我只将其归入最合适解法的那类中。
题目有大类、有子类，大类是链表、数组、动态规划，子类指的是单独的一种“套路”，比如树中的深度优先搜索是一种套路，动态规划中的背包也属于一种套路。

阅读全文 »

分布式事务实现

发表于 2020-12-06 更新于 2023-08-20 分类于分布式系统

这篇总结各种常见分布式事务的实现方式，有很多技术细节，但是没有提太多具体实现，之后有时间再梳理一下tcc-transaction这些框架。

阅读全文 »

分布式事务-从本地事务到分布式事务

发表于 2020-12-06 更新于 2022-10-09 分类于分布式系统

这篇文档集中于概念的梳理，不会谈太多实现上的细节。

阅读全文 »

单体式 & SOA & 微服务

架构、架构风格和系统架构

架构风格关注的是如何使用一些连接件来组合软件组件，在Web应用中，我们会使用覆盖网络来描述软件的架构，连接件可以是HTTP协议、数据库连接器等，在桌面应用中，连接器可以是读取用户输入的管道，等等。
系统架构关注的是软件组件是如何实例化的，比如要几台服务器、哪些组件要复制等。
平时说的架构一般指的是架构风格，但对实现细节的深究是成为架构师的必经之路。

为什么转微服务

单体式缺陷

一个归档包（例如war格式）包含所有功能的应用程序，通常称为单体程序。而架构单体应用的方法论，就是单体应用架构。
以一个电影售票系统为例，该系统UI和若干业务模块最终都被打包在一个war包中，该war包包含了整个系统的所有业务功能，这样的应用称为单体应用。
很多项目都是从单体应用开始的。单体应用比较容易部署、测试，在项目的初期，单体应用可以很好地运行。然而随着需求的不断增加，越来越多的人加入开发团队，代码库也在飞速膨胀。慢慢地，单体应用变得越来越臃肿，可维护性、灵活性逐渐减低，维护成本越来越高。
下面列举一些单体应用存在的问题。

复杂性高：当一个项目达到百万级别，整个项目包含的模块非常多、模块的边界模糊、依赖关系不清晰、代码质量参差不齐、混乱地堆砌在一起。整个项目非常复杂。每次修改代码都心惊胆战，甚至添加一个简单的功能，或者修改一个bug都会带来隐含的缺陷。
技术债务：随着时间推移、需求变更和人员更迭，会逐渐形成应用程序的技术债务（为了快速地解决问题，而采取的不规范的方案），并且越积越多。“不坏不修”，这在软件开发中非常常见，在单体应用中，这种思想更严重。已使用的系统设计或代码难以被修改，因为应用程序中的其他模块可能会以意料之外的方式使用它。
部署频率低：随着代码的增多，构建和部署的时间也会增加。而在单体应用中，每次功能的变更或缺陷的修复都会导致重新部署整个应用。全量部署的方式耗时长、影响范围大、风险高，这使得单体应用项目部署的频率较低。而部署频率低又导致两次发布之间会有大量功能的变更和缺陷修复，出错概率较高。
可靠性差：某个应用Bug，例如死循环、OOM等，可能导致整个应用崩溃。
扩展能力受限：单体应用只能作为一个整体进行扩展，无法根据业务模块的需要进行伸缩。例如，应用中有的模块是计算密集型的，它需要强劲的CPU；有的模块则是IO密集型的，需要更大的内存。由于这些模块部署在一起，不得不在硬件的选择上做出妥协。
阻碍技术创新：单体应用往往使用统一的技术平台或方案解决所有的问题，团队中的每个成员必须使用相同的开发语言和框架，要想引入新框架或新技术平台会非常困难。例如，一个使用Struts2构建的、有百万行代码的单体应用，如果想要换用Spring MVC，毫无疑问切换的成本是非常高的。
综上，随着业务需求的发展，功能的不断增加，单体架构很难满足互联网时代快速变化的需要。

SOA缺陷

微服务架构模式有点像SOA，他们都由多个服务构成，因此对SOA缺陷的讨论可以参照下面对微服务的讨论。但是，从另一个角度看，微服务架构模式是一个不包含Web服务(WS-)和ESB服务的SOA，微服务应用乐于采用简单轻量级协议，比如REST，而不是WS-，在微服务内部避免使用ESB以及ESB类似功能，微服务架构模式也拒绝使用canonical schema等SOA概念，因此可以认为微服务是轻量版的SOA。

微服务

为什么迁移到微服务

对单体式应用来说，任何一个小的变更，都会导致整个环境需要重新构建和部署；
随着应用的扩展，单体式应用越来越难以维持模块化；
伸缩单体式应用时，必须伸缩整个应用；

相对来说，微服务风格将应用作为一组服务来进行构建，每个服务都是独立可部署和可伸缩的，服务之间有着明显的模块边界，不同的服务可以使用不同的编程语言编写，并由不同的小组维护。

（Componentization via Services）组件化和服务

Component
a component is a unit of software that is independently replaceable and upgradeable.
Library
We define libraries as components that are linked into a program and called using in-memory function calls
Service
services are out-of-process components who communicate with a mechanism such as a web service request, or remote procedure call.
服务可能由多个进程组成，比如一个应用进程和一个仅供该服务使用的数据库；

微服务将服务作为整个应用的组件，其优势是：

services are independently deployable.
如果将library作为组件，对任一组件的变更都会导致整个应用需要重新部署，But if that application is decomposed into multiple services, you can expect many single service changes to only require that service to be redeployed. That’s not an absolute, some changes will change service interfaces resulting in some coordination, but the aim of a good microservice architecture is to minimize these through cohesive service boundaries and evolution mechanisms in the service contracts.
服务能提供一个更明确的组件接口

使用服务作为组件同样存在一些缺点：

远程调用比起进程内的调用更昂贵，因此远程API往往设计得更粗粒度，用起来也更加笨拙；
变更组件间的责任分配（比如将一个功能从一个服务迁移到另一个服务）很困难；

Organized around Business Capabilities（围绕业务功能组织/领域驱动设计）

应用拆分

之前：在将大型应用拆分为多个部分时，管理层往往侧重于技术层面，比如将产品开发分为UI团队、服务端逻辑处理团队、数据库团队，分别负责产品的前端、后台、数据库的开发和维护。但是任何一个修改都需要投入大量的时间和预算。
由Conway定律知：开发组织的沟通结构会影响软件的结构，如果一个队伍被分成了多个团队，而他们之间存在沟通壁垒，那么这个队伍负责的模块开发也会出现问题。因此管理人员最好确保软件的架构与团队的架构是相容的。

微服务项目：在使用微服务方法拆分应用时往往是处于业务功能考量的。将应用拆分为服务后，这样的服务必须包含其负责的业务领域的全栈实现，包括UI、持久存储及其他。最终每个服务的团队都是跨功能的，包含开发的各个层面。
服务边界与团队边界

服务大小的确定

没有固定规定。大如亚马逊的“两个披萨团队”（整个团队可以吃下两个披萨饼），意味着不超过十几个人。小如半打的团队支持半打的服务。

服务边界的确定

单体式应用总是可以围绕业务功能模块化，但是如果某个模块在组织时带入了太多的依赖，就会为团队成员带来太多的记忆负担（因为要知道依赖的模块的处理逻辑）。因此清晰的团队边界必须基于明确的服务组件边界。

Products not Projects（产品而不是项目）

传统的开发模块往往倾向于由开发人员构建项目，项目完成后转交给运维团队，并解散项目开发团队。
微服务需要避免这种“项目模式”，而更倾向于令团队在整个生命周期内拥有产品，亚马逊有一句格言：“you build, you run it”，开发团队需要负责生产软件的全部责任，并增加与用户的联系。
因此“产品模式”不是将软件看成一组待完成的功能，而是一个开发人员与用户之间的持续关系。

Smart endpoints and dumb pipes

在构建进程间的通信机制的时候，我们已经看到了许多产品和方法论强调在交互机制中设计更多的智能。一个很好的例子是ESB（Enterprise Service Bus），where ESB products often include sophisticated facilities for message routing, choreography, transformation, and applying business rules.

微服务和SOA的区别

比较浅显的解释：微服务和SOA之间的区别主要提现在服务之间的连接方式上，微服务没有强调一定要使用ESB来作为消息的载体，而是强调使用更轻量化的协议进行服务间的交互，相对来说更灵活，但也没办法通过ESB进行消息统计，如果需要进行服务链路追踪，可以考虑采用zipkin、sleuth等工具（底层在发送消息的同时会带上一个链路ID）。
最准确的说法：微服务是SOA的一种实现
最符合实际的说法：微服务是去ESB的SOA
背后实际上是两种思想的分歧：分布还是集中
当然这里说的不是服务的分布和集中。服务肯定是分布的，这是大前提，是SOA的本质理念之一。分歧在于对服务的治理，是分布还是集中。

SOA是什么？

《分布式Java应用：基础与实践》
SOA是面向服务架构，它强调系统之间以标准的服务方式进行交互，各系统可采用不同的语言、不同的框架来实现，交互则全部通过服务的方式进行。
https://blog.csdn.net/varyall/article/details/79088623、https://www.zhihu.com/question/37808426/answer/93335393
ESB和SCA（一种实现SOA的标准，由IBM、Oracle等几家业界领先的产商制订）不同，它不是由多个厂家联合制订的SOA实现的标准，可以认为ESB只是个概念，核心思想是基于消息中间件来实现系统间的交互。基于消息中间件所构建的此系统交互的中间场所称为总线，系统间交互的数据格式采用统一的消息格式，由总线完成消息的转化、路由，并发送到相应的目标应用，基于ESB构建的系统结构如下图所示：
SOA与ESB
通常ESB框架具备以下5个要素：

标准的消息通信格式
ESB框架中要定义系统发送及接受消息时的消息格式，以便各个系统保持同样的方式与总线通信。
消息路由
消息路由是指当总线接收到消息后，根据消息中的数据来决定需要调用的系统。在更为复杂的情况下，还可基于消息路由实现功能编排，即当某个功能需要由多个系统共同完成时，可在总线上以流程的方式编排访问系统的顺序。例如某功能需要首先访问A系统，然后根据A系统返回的结果来决定是访问B系统还是C系统，在访问了B系统或C系统后又要根据结果同时提交给D、E系统执行，在这种情况下如果有流程编排的话实现起来会方便很多。
支持多种的消息交互类型
消息交互时要支持请求/响应和发布/订阅等方式，请求/响应方式会更加方便实现同步请求，发布/订阅方式则更加方便实现异步的消息广播。
支持多种网络协议
总线要和多个系统进行交互，通常要支持多种网络协议，例如TCP/IP、UDP/IP、HTTP等。
支持多种数据格式并能够进行相互转换
多个系统均须发送消息至总线，并由总线将消息转发，但各个系统消息中的数据格式可能不一致，此时总线要支持数据的转换。

不管是基于SCA标准、ESB，还是已有的SCA框架和ESB框架，在实现一个大型应用的SOA平台时都仍然有不少需要自行扩展实现的地方，尤其是在调试/跟踪、依赖管理及高性能、高可用方面。对于大型应用的服务化，SOA平台时一方面，如何推广实行也是一个重要因素。
以上提及的为一个基本的大型应用的SOA平台的特征，而对于一个更加完善的SOA平台，作者认为还须具备以下几点：

支撑集群环境
对于大型应用而言，通常会借助集群来支撑大的访问量，如何让服务交互和集群环境结合得更好是SOA平台中值得考虑的，例如典型的有软件负载均衡、服务接口或方法级的路由策略等。
完善的服务治理
服务治理的主要目的是为了保障服务能够稳定、高性能地运转，之前提及的依赖管理也属于服务治理中的一项，服务运行状况的监测、服务的安全控制、服务的流量限制、服务故障根源的推测及服务可用性的保障也都属于服务治理的范畴。要实现这些功能仅仅靠SOA平台还很难做到，通常还要有系统架构的配合。
服务QoS（Quality of Service）的支持
服务QoS的支持是指SOA平台按照服务配置的QoS来分配相应的迎接资源，例如A服务的QoS配置为每秒最多支撑5000请求，且响应时间95%需要在1秒以内，SOA平台要能收集目前服务的运行状况来合理地分配机器资源，要做到这点难度非常高。

微服务、SOA、水平分层架构之间的区别

微服务的演进

从发展历程上看，微服务是SOA和水平分层架构的后继者；
从架构优化思路上看，SOA属于对架构的垂直拆分，水平分层架构顾名思义是对架构进行水平方向上的拆分，微服务结合了二者；

CAP

CAP概念

CAP是描述分布式系统特性常用的一种理论，它使用数据一致性（Consistency）、服务可用性（Availability）和分区容错性（Partition-tolerance）三个指标来定义一个分布式系统，这三个特性不能被同时完全满足，其中，P 是必须要满足的，因为一般的业务系统并不允许网络中的消息被随意丢弃，因此多数的讨论都集中于 C 和 A 之间的权衡。
如果需要满足强一致性，则在对数据进行读写操作时势必都需要进行加锁操作并使用事务来保证分布式一致性，但同时也会对系统的效率产生非常大的影响，起到反作用、影响用户的体验，所以在设计时往往会放宽这个要求，采取最终一致性作为实现目标。服务的高可用性要求请求必须能够完成，这可以通过复制服务实例来实现，服务实例的复制需要投入更多地成本与维护人力，需要根据具体场景进行具体分析。

CAP应用

Lease 机制: Lease 机制牺牲了部分异常情况下的A，从而获得了完全的C 与很好的P。
Quorum 机制: Quorum 机制，在CAP 三大因素中都各做了折中，有一定的C，有较好的A，也有较好的P，是一种较为平衡的分布式协议。
两阶段提交协议: 两阶段提交系统具有完全的C，很糟糕的A，很糟糕的P。
Paxos 协议：同样是强一致性协议，Paxos 在CAP 三方面较之两阶段提交协议要优秀得多。Paxos 协议具有完全的C，较好的A，较好的P。Paxos 的A 与P 的属性与Quorum 机制类似，因为Paxos 的协议本身就具有Quorum 机制的因素。

Lease

Lease 机制是最重要的分布式协议，广泛应用于各种实际的分布式系统中。

基于lease 的分布式cache 系统

基本的问题背景如下：在一个分布式系统中，有一个中心服务器节点，中心服务器存储、维护着一些数据，这些数据是系统的元数据。系统中其他的节点通过访问中心服务器节点读取、修改其上的元数据。由于系统中各种操作都依赖于元数据，如果每次读取元数据的操作都访问中心服务器节点，那么中心服务器节点的性能成为系统的瓶颈。为此，设计一种元数据cache，在各个节点上 cache 元数据信息，从而减少对中心服务器节点的访问，提高性能。另一方面，系统的正确运行严格依赖于元数据的正确，这就要求各个节点上cache 的数据始终与中心服务器上的数据一致，cache 中的数据不能是旧的脏数据。最后，设计的cache 系统要能最大可能的处理节点宕机、网络中断等异常，最大程度的提高系统的可用性。
为此，利用lease 机制设计一套cache 系统，其基本原理为如下。中心服务器在向各节点发送数据时同时向节点颁发一个lease。每个lease 具有一个有效期，和信用卡上的有效期类似，lease 上的有效期通常是一个明确的时间点，例如12:00:10，一旦真实时间超过这个时间点，则lease 过期失效。这样lease 的有效期与节点收到lease 的时间无关，节点可能收到lease 时该lease 就已经过期失效。这里首先假设中心服务器与各节点的时钟是同步的，在下节中讨论时钟不同步对lease 的影响。中心服务器发出的lease 的含义为：在lease 的有效期内，中心服务器保证不会修改对应数据的值。因此，节点收到数据和lease 后，将数据加入本地Cache，一旦对应的lease 超时，节点将对应的本地cache 数据删除。中心服务器在修改数据时，首先阻塞所有新的读请求，并等待之前为该数据发出的所有lease 超时过期，然后修改数据的值。
基于lease 的cache，客户端节点读取元数据

判断元数据是否已经处于本地cache 且lease 处于有效期内1.1 是：直接返回cache 中的元数据1.2 否：向中心服务器节点请求读取元数据信息1.2.1 服务器收到读取请求后，返回元数据及一个对应的lease 1.2.2 客户端是否成功收到服务器返回的数据 1.2.2.1 失败或超时：退出流程，读取失败，可重试1.2.2.2 成功：将元数据与该元数据的lease 记录到内存中，返回元数据
基于lease 的cache，客户端节点修改元数据流程2.1 节点向服务器发起修改元数据请求。2.2 服务器收到修改请求后，阻塞所有新的读数据请求，即接收读请求，但不返回数据。2.3 服务器等待所有与该元数据相关的lease 超时。2.4 服务器修改元数据并向客户端节点返回修改成功。

上述机制可以保证各个节点上的cache 与中心服务器上的中心始终一致。这是因为中心服务器节点在发送数据的同时授予了节点对应的lease，在lease 有效期内，服务器不会修改数据，从而客户端节点可以放心的在lease 有效期内cache 数据。上述lease 机制可以容错的关键是：服务器一旦发出数据及lease，无论客户端是否收到，也无论后续客户端是否宕机，也无论后续网络是否正常，服务器只要等待lease 超时，就可以保证对应的客户端节点不会再继续cache 数据，从而可以放心的修改数据而不会破坏cache 的一致性。
上述基础流程有一些性能和可用性上的问题，但可以很容易就优化改性。优化点一：服务器在修改元数据时首先要阻塞所有新的读请求，造成没有读服务。这是为了防止发出新的lease 从而引起不断有新客户端节点持有lease 并缓存着数据，形成“活锁”。优化的方法很简单，服务器在进入修改数据流程后，一旦收到读请求则只返回数据但不颁发lease。从而造成在修改流程执行的过程中，客户端可以读到元数据，只是不能缓存元数据。进一步的优化是，当进入修改流程，服务器颁发的lease 有效期限选择为已发出的lease 的最大有效期限。这样做，客户端可以继续在服务器进入修改流程后继续缓存元数据，但服务器的等待所有lease 过期的时间也不会因为颁发新的lease 而不断延长。
最后，=cache 机制与多副本机制的区别。Cache 机制与多副本机制的相似之处都是将一份数据保存在多个节点上。但Cache 机制却要简单许多，对于cache 的数据，可以随时删除丢弃，并命中cache 的后果仅仅是需要访问数据源读取数据；然而副本机制却不一样，副本是不能随意丢弃的，每失去一个副本，服务质量都在下降，一旦副本数下降到一定程度，则往往服务将不再可用。

lease 机制的分析

lease 的定义：Lease 是由颁发者授予的在某一有效期内的承诺。颁发者一旦发出lease，则无论接受方是否收到，也无论后续接收方处于何种状态，只要lease 不过期，颁发者一定严守承诺；另一方面，接收方在lease 的有效期内可以使用颁发者的承诺，但一旦lease 过期，接收方一定不能继续使用颁发者的承诺。
Lease 机制具有很高的容错能力。首先，通过引入有效期，Lease 机制能否非常好的容错网络异常。Lease 颁发过程只依赖于网络可以单向通信，即使接收方无法向颁发者发送消息，也不影响lease 的颁发。由于lease 的有效期是一个确定的时间点，lease 的语义与发送lease 的具体时间无关，所以同一个lease 可以被颁发者不断重复向接受方发送。即使颁发者偶尔发送lease 失败，颁发者也可以简单的通过重发的办法解决。一旦lease 被接收方成功接受，后续lease 机制不再依赖于网络通信，即使网络完全中断lease 机制也不受影响。再者，Lease 机制能较好的容错节点宕机。如果颁发者宕机，则宕机的颁发者通常无法改变之前的承诺，不会影响lease 的正确性。在颁发者机恢复后，如果颁发者恢复出了之前的lease 信息，颁发者可以继续遵守lease 的承诺。如果颁发者无法恢复lease 信息，则只需等待一个最大的lease 超时时间就可以使得所有的lease 都失效，从而不破坏lease机制。
例如上节中的cache 系统的例子中，一旦服务器宕机，肯定不会修改元数据，重新恢复后，只需等待一个最大的lease 超时时间，所有节点上的缓存信息都将被清空。对于接受方宕机的情况，颁发者不需要做更多的容错处理，只需等待lease 过期失效，就可以收回承诺，实践中也就是收回之前赋予的权限、身份等。最后，lease 机制不依赖于存储。颁发者可以持久化颁发过的lease 信息，从而在宕机恢复后可以使得在有效期的lease 继续有效。但这对于lease 机制只是一个优化，如之前的分析，即使颁发者没有持久化lease 信息，也可以通过等待一个最大的lease 时间的方式使得之前所有颁发的lease 失效，从而保证机制继续有效。
Lease 机制依赖于有效期，这就要求颁发者和接收者的时钟是同步的。一方面，如果颁发者的时钟比接收者的时钟慢，则当接收者认为lease 已经过期的时候，颁发者依旧认为lease 有效。接收者可以用在lease 到期前申请新的lease 的方式解决这个问题。另一方面，如果颁发者的时钟比接收者的时钟快，则当颁发者认为lease 已经过期的时候，接收者依旧认为lease 有效，颁发者可能将lease 颁发给其他节点，造成承诺失效，影响系统的正确性。对于这种时钟不同步，实践中的通常做法是将颁发者的有效期设置得比接收者的略大，只需大过时钟误差就可以避免对lease 的有效性的影响。

基于lease 机制确定节点状态

分布式协议依赖于对节点状态认知的全局一致性，即一旦节点Q 认为某个节点 A 异常，则节点A 也必须认为自己异常，从而节点A 停止作为primary，避免“双主”问题的出现。解决这种问题有两种思路，第一、设计的分布式协议可以容忍“双主”错误，即不依赖于对节点状态的全局一致性认识，或者全局一致性状态是全体协商后的结果；第二、利用lease 机制。对于第一种思路即放弃使用中心化的设计，而改用去中心化设计，超过本节的讨论范畴。下面着重讨论利用 lease 机制确定节点状态。
由中心节点向其他节点发送lease，若某个节点持有有效的lease，则认为该节点正常可以提供服务。用于例2.3.1 中，节点A、B、C 依然周期性的发送heart beat 报告自身状态，节点Q 收到heart beat 后发送一个lease，表示节点Q 确认了节点A、B、C 的状态，并允许节点在lease 有效期内正常工作。节点Q 可以给primary 节点一个特殊的lease，表示节点可以作为primary 工作。一旦节点Q 希望切换新的primary，则只需等前一个primary 的lease 过期，则就可以安全的颁发新的lease 给新的 primary 节点，而不会出现“双主”问题。
在实际系统中，若用一个中心节点发送lease 也有很大的风险，一旦该中心节点宕机或网络异常，则所有的节点没有lease，从而造成系统高度不可用。为此，实际系统总是使用多个中心节点互为副本，成为一个小的集群，该小集群具有高可用性，对外提供颁发lease 的功能。chubby 和zookeeper 都是基于这样的设计。

lease 的有效期时间选择

工程中，常选择的lease 时长是10 秒级别，这是一个经过验证的经验值，实践中可以作为参考并综合选择合适的时长。

Quorum

先做这样的约定：更新操作（write）是一系列顺序的过程，通过其他机制确定更新操作的顺序（例如primary-secondary 架构中由primary 决定顺序），每个更新操作记为wi， i 为更新操作单调递增的序号，每个wi 执行成功后副本数据都发生变化，称为不同的数据版本，记作vi。假设每个副本都保存了历史上所有版本的数据。

write-all-read-one

Write-all-read-one（简称WARO）是一种最简单的副本控制规则，顾名思义即在更新时写所有的副本，只有在所有的副本上更新成功，才认为更新成功，从而保证所有的副本一致，这样在读取数据时可以读任一副本上的数据。
由于更新操作需要在所有的N 个副本上都成功，更新操作才能成功，所以一旦有一个副本异常，更新操作失败，更新服务不可用。对于更新服务，虽然有N 个副本，但系统无法容忍任何一个副本异常。另一方面，N 个副本中只要有一个副本正常，系统就可以提供读服务。对于读服务而言，当有N 个副本时，系统可以容忍N-1 个副本异常。从上述分析可以发现WARO 读服务的可用性较高，但更新服务的可用性不高，甚至虽然使用了副本，但更新服务的可用性等效于没有副本。

Quorum 定义

在Quorum 机制下，当某次更新操作wi 一旦在所有N 个副本中的W 个副本上都成功，则就称该更新操作为“成功提交的更新操作”，称对应的数据为“成功提交的数据”。令R>N-W，由于更新操作wi 仅在W 个副本上成功，所以在读取数据时，最多需要读取R 个副本则一定能读到wi 更新后的数据vi 。如果某次更新wi 在W 个副本上成功，由于W+R>N，任意R 个副本组成的集合一定与成功的W个副本组成的集合有交集，所以读取R 个副本一定能读到wi 更新后的数据vi。如图 2-10， Quorum 机制的原理可以文森图表示。
Quorum文森图
某系统有5 个副本，W=3，R=3，最初5 个副本的数据一致，都是v1，某次更新操作 w2 在前3 副本上成功，副本情况变成（v2 v2 v2 v1 v1）。此时，任意3 个副本组成的集合中一定包括 v2。在上述定义中，令W=N，R=1，就得到WARO，即WARO 是Quorum 机制的一种特例。与分析WARO 相似，分析Quorum 机制的可用性。限制Quorum 参数为W+R=N+1。由于更新操作需要在W 个副本上都成功，更新操作才能成功，所以一旦N-W+1 个副本异常，更新操作始终无法在W 个副本上成功，更新服务不可用。另一方面，一旦N-R+1 个副本异常，则无法保证一定可以读到与W 个副本有交集的副本集合，则读服务的一致性下降。
再次强调：仅仅依赖quorum 机制是无法保证强一致性的。因为仅有quorum 机制时无法确定最新已成功提交的版本号，除非将最新已提交的版本号作为元数据由特定的元数据服务器或元数据集群管理，否则很难确定最新成功提交的版本号。在下一节中，将讨论在哪些情况下，可以仅仅通过quorum 机制来确定最新成功提交的版本号。
Quorum 机制的三个系统参数N、W、R 控制了系统的可用性，也是系统对用户的服务承诺：数据最多有N 个副本，但数据更新成功W 个副本即返回用户成功。对于一致性要求较高的Quorum 系统，系统还应该承诺任何时候不读取未成功提交的数据，即读取到的数据都是曾经在W 个副本上成功的数据。

读取最新成功提交的数据

Quorum 机制只需成功更新N 个副本中的W 个，在读取R 个副本时，一定可以读到最新的成功提交的数据。但由于有不成功的更新情况存在，仅仅读取R 个副本却不一定能确定哪个版本的数据是最新的已提交的数据。对于一个强一致性Quorum 系统，需要读取到W个相同版本的数据，若未达到W个，则继续读取其他副本，直到成功读取到W 个该版本的副本，则该数据为最新的成功提交的数据；如果在所有副本中该数据的个数肯定不满足W 个，则R 中版本号第二大的为最新的成功提交的副本。例：在读取到（v2 v1 v1）时，继续读取剩余的副本，若读到剩余两个副本为（v2 v2）则v2 是最新的已提交的副本；若读到剩余的两个副本为（v2 v1）或（v1 v1）则v1 是最新成功提交的版本；若读取后续两个副本有任一超时或失败，则无法判断哪个版本是最新的成功提交的版本。
可以看出，在单纯使用Quorum 机制时，若要确定最新的成功提交的版本，最多需要读取R+ （W-R-1）=N 个副本，当出现任一副本异常时，读最新的成功提交的版本这一功能都有可能不可用。实际工程中，应该尽量通过其他技术手段，回避通过Quorum 机制读取最新的成功提交的版本。例如，当quorum 机制与primary-secondary 控制协议结合使用时，可以通过读取primary 的方式读取到最新的已提交的数据。

基于Quorum 机制选择primary副本

读取数据时依照一致性要求的不同可以有不同的做法：如果需要强一致性的立刻读取到最新的成功提交的数据，则可以简单的只读取primary 副本上的数据即可，也可以通过上节的方式读取；如果需要会话一致性，则可以根据之前已经读到的数据版本号在各个副本上进行选择性读取；如果只需要弱一致性，则可以选择任意副本读取。
在primary-secondary 协议中，当primary 异常时，需要选择出一个新的primary，之后secondary 副本与primary 同步数据。通常情况下，选择新的primary 的工作是由某一中心节点完成的，在引入 quorum 机制后，常用的primary 选择方式与读取数据的方式类似，即中心节点读取R 个副本，选择 R 个副本中版本号最高的副本作为新的primary。新primary 与至少W 个副本完成数据同步后作为新的primary 提供读写服务。首先，R 个副本中版本号最高的副本一定蕴含了最新的成功提交的数据。再者，虽然不能确定最高版本号的数是一个成功提交的数据，但新的primary 在随后与secondary 同步数据，使得该版本的副本个数达到W，从而使得该版本的数据成为成功提交的数据。
例：在N=5，W=3，R=3 的系统中，某时刻副本最大版本号为（v2 v2 v1 v1 v1），此时v1 是系统的最新的成功提交的数据，v2 是一个处于中间状态的未成功提交的数据。假设此刻原primary 副本异常，中心节点进行primary 切换工作。这类“中间态”数据究竟作为“脏数据”被删除，还是作为新的数据被同步后成为生效的数据，完全取决于这个数据能否参与新primary 的选举。下面分别分析这两种情况。
Quorum选举1
第一、如上图，若中心节点与其中3 个副本通信成功，读取到的版本号为（v1 v1 v1），则任选一个副本作为primary，新primary 以v1 作为最新的成功提交的版本并与其他副本同步，当与第1、第2 个副本同步数据时，由于第1、第2 个副本版本号大于primary，属于脏数据，可以简单地丢弃有脏数据的副本（这样相当于副本没有数据），也可以通过一些类似于undo log的机制来删除脏数据。实践中，新primary 也有可能与后两个副本完成同步后就提供数据服务，随后自身版本号也更新到v2，如果系统不能保证之后的v2 与之前的v2 完全一样，则新 primary 在与第1、2 个副本同步数据时不但要比较数据版本号还需要比较更新操作的具体内容是否一样。
Quorum选举2
第二、若中心节点与其他3 个副本通信成功，读取到的版本号为（v2 v1 v1），则选取版本号为 v2 的副本作为新的primary，之后，一旦新primary 与其他2 个副本完成数据同步，则符合v2 的副本个数达到W 个，成为最新的成功提交的副本，新primary 可以提供正常的读写服务。

负载均衡

数据一致性保证

保证分布式系统数据一致性的6种方案

高可用

高可用级别

FT (Fault Tolerance) 双机热备
通过创建与主实例保持虚拟同步的虚拟机，使应用在服务器发生故障的情况下也能够持续可用。
如果主实例发生了故障，则会发生即时且透明的故障切换。
虽然FT功能很强大，但是在虚拟化中很少用到FT功能，一是对资源浪费比较严重，二是性能下降比较快，由于是指令级别的同步，因而两台虚拟机之间的距离非常近，无法完全达到容灾的目的，三是如果主虚拟机因为执行非法指令蓝屏，则辅助虚拟机也马上就会发生，根本无法保证业务延续性。
虚拟机HA
虚拟机HA主要指在有一个共享存储池的情况下，当一台物理机挂了，这台物理机上的虚拟机可以迁移到其他物理机的机制。
为了保证虚拟机的无状态特性，需要将状态存储到一个共享存储中，比如MySQL、Apollo。
在HA状态下，虚拟机的恢复时间一般在秒级别，也即当监控探测到物理机挂了之后，可以迅速在空闲的物理机上将虚拟机启动起来。
同城双活
同城双活最重要的是数据如何从一个数据中心同步到另一个数据中心，并且在一个数据中心故障的时候，可以实现存储设备的切换，保证状态能够快速切换到另一个数据中心。主流的存储厂商都提供在高速光纤互联情况下，在一定距离之内的两台存储设备的近实时的同步，数据双活是一切双活的基础。
异地容灾
由于异地距离比较远，不可能像双活一样采取近同步的方式，只能通过异步的方式进行同步，也可以预见的是，容灾切换的时候，数据会丢失一部分。
异地备份
备份是比容灾更加不灵活的一种方式，和容灾的不同是，容灾需要使得虚拟机的资源时刻准备着，等需要切换的时候，马上就用，数据和虚拟机还是热数据。而备份更多的是以冷数据的方式，将虚拟机镜像，数据库镜像等变成文件存放在价格比较便宜的存储上面，成本比容灾要低得多。

副本控制

副本控制协议指按特定的协议流程控制副本数据的读写行为，使得副本满足一定的可用性和一致性要求的分布式协议。副本控制协议要具有一定的对抗异常状态的容错能力，从而使得系统具有一定的可用性，同时副本控制协议要能提供一定一致性级别。由CAP 原理可知，要设计一种满足强一致性，且在出现任何网络异常时都可用的副本协议是不可能的。为此，实际中的副本控制协议总是在可用性、一致性与性能等各要素之间按照具体需求折中。
副本控制协议可以分为两大类：“中心化(centralized)副本控制协议”和“去中心化(decentralized)副本控制协议”。

中心化副本控制协议

中心化副本控制协议的基本思路是由一个中心节点协调副本数据的更新、维护副本之间的一致性。图给出了中心化副本协议的通用架构。中心化副本控制协议的优点是协议相对较为简单，所有的副本相关的控制交由中心节点完成。并发控制将由中心节点完成，从而使得一个分布式并发控制问题，简化为一个单机并发控制问题。所谓并发控制，即多个节点同时需要修改副本数据时，需要解决“写写”、“读写”等并发冲突。单机系统上常用加锁等方式进行并发控制。对于分布式并发控制，加锁也是一个常用的方法，但如果没有中心节点统一进行锁管理，就需要完全分布式化的锁系统，会使得协议非常复杂。中心化副本控制协议的缺点是系统的可用性依赖于中心化节点，当中心节点异常或与中心节点通信中断时，系统将失去某些服务（通常至少失去更新服务），所以中心化副本控制协议的缺点正是存在一定的停服务时间。

primary-secondary 协议

在primary-secondary 类型的协议中，副本被分为两大类，其中有且仅有一个副本作为primary 副本，除primary 以外的副本都作为secondary 副本。维护primary 副本的节点作为中心节点，中心节点负责维护数据的更新、并发控制、协调副本的一致性。
Primary-secondary 类型的协议一般要解决四大类问题：数据更新流程、数据读取方式、Primary 副本的确定和切换、数据同步（reconcile）。

数据更新基本流程

数据更新都由primary 节点协调完成。
外部节点将更新操作发给primary 节点
primary 节点进行并发控制即确定并发更新操作的先后顺序
primary 节点将更新操作发送给secondary 节点
primary 根据secondary 节点的完成情况决定更新是否成功并将结果返回外部节点

primary-secondary副本控制协议
在工程实践中，如果由primary 直接同时发送给其他N 个副本发送数据，则每个 secondary 的更新吞吐受限于primary 总的出口网络带宽，最大为primary 网络出口带宽的1/N。为了解决这个问题，有些系统（例如，GFS，Redis的级联同步），使用接力的方式同步数据，即primary 将更新发送给第一个secondary 副本，第一个secondary 副本发送给第二secondary 副本，依次类推。

数据读取方式

数据读取方式也与一致性高度相关。如果只需要最终一致性，则读取任何副本都可以满足需求。如果需要会话一致性，则可以为副本设置版本号，每次更新后递增版本号，用户读取副本时验证版本号，从而保证用户读到的数据在会话范围内单调递增。使用primary-secondary 比较困难的是实现强一致性。

由于数据的更新流程都是由primary 控制的，primary 副本上的数据一定是最新的，所以如果始终只读primary 副本的数据，可以实现强一致性。如果只读primary 副本，则secondary 副本将不提供读服务。实践中，如果副本不与机器绑定，而是按照数据段为单位维护副本，仅有primary 副本提供读服务在很多场景下并不会造出机器资源浪费。
将副本分散到集群中个，假设primary 也是随机的确定的，那么每台机器上都有一些数据的primary 副本，也有另一些数据段的secondary 副本。从而某台服务器实际都提供读写服务。
由primary 控制节点secondary 节点的可用性。当primary 更新某个secondary 副本不成功时，primary 将该secondary 副本标记为不可用，从而用户不再读取该不可用的副本。不可用的 secondary 副本可以继续尝试与primary 同步数据，当与primary 完成数据同步后，primary 可以副本标记为可用。这种方式使得所有的可用的副本，无论是primary 还是secondary 都是可读的，且在一个确定的时间内，某secondary 副本要么更新到与primary 一致的最新状态，要么被标记为不可用，从而符合较高的一致性要求。这种方式依赖于一个中心元数据管理系统，用于记录哪些副本可用，哪些副本不可用。某种意义上，该方式通过降低系统的可用性来提高系统的一致性。

primary 副本的确定与切换

在primary-secondary 类型的协议中，另一个核心的问题是如何确定primary 副本，尤其是在原primary 副本所在机器出现宕机等异常时，需要有某种机制切换primary 副本，使得某个secondary 副本成为新的primary 副本。
通常的，在primary-secondary 类型的分布式系统中，哪个副本是primary 这一信息都属于元信息，由专门的元数据服务器维护。执行更新操作时，首先查询元数据服务器获取副本的primary 信息，从而进一步执行数据更新流程。
由于分布式系统中可靠的发现节点异常是需要一定的探测时间的，这样的探测时间通常是10 秒级别，这也意味着一旦primary 异常，最多需要10 秒级别的发现时间，系统才能开始primary 的切换，在这10 秒时间内，由于没有primary，系统不能提供更新服务，如果系统只能读primary 副本，则这段时间内甚至不能提供读服务。从这里可以看到，primary-backup 类副本协议的最大缺点就是由于primary 切换带来的一定的停服务时间。

数据同步

不一致的secondary 副本需要与primary 进行同步（reconcile）。
通常不一致的形式有三种：一、由于网络分化等异常，secondary 上的数据落后于primary 上的数据。二、在某些协议下，secondary 上的数据有可能是脏数据，需要被丢弃。所谓脏数据是由于primary 副本没有进行某一更新操作，而secondary 副本上反而进行的多余的修改操作，从而造成secondary 副本数据错误。三、secondary 是一个新增加的副本，完全没有数据，需要从其他副本上拷贝数据。
对于第一种secondary 数据落后的情况，常见的同步方式是回放primary 上的操作日志（通常是redo 日志），从而追上primary 的更新进度。对于脏数据的情况，较好的做法是设计的分布式协议不产生脏数据。如果协议一定有产生脏数据的可能，则也应该使得产生脏数据的概率降到非常低得情况，从而一旦发生脏数据的情况可以简单的直接丢弃有脏数据的副本，这样相当于副本没有数据。另外，也可以设计一些基于undo 日志的方式从而可以删除脏数据。如果secondary 副本完全没有数据，则常见的做法是直接拷贝primary 副本的数据，这种方法往往比回放日志追更新进度的方法快很多。但拷贝数据时primary 副本需要能够继续提供更新服务，这就要求primary 副本支持快照(snapshot)功能。即对某一刻的副本数据形成快照，然后拷贝快照，拷贝完成后使用回放日志的方式追快照形成后的更新操作。

去中心化副本控制协议

去中心化副本控制协议没有中心节点，协议中所有的节点都是完全对等的，节点之间通过平等协商达到一致。从而去中心化协议没有因为中心化节点异常而带来的停服务等问题。
去中心化协议的最大的缺点是协议过程通常比较复杂。尤其当去中心化协议需要实现强一致性时，协议流程变得复杂且不容易理解。由于流程的复杂，去中心化协议的效率或者性能一般也较中心化协议低。一个不恰当的比方就是，中心化副本控制协议类似专制制度，系统效率高但高度依赖于中心节点，一旦中心节点异常，系统受到的影响较大；去中心化副本控制协议类似民主制度，节点集体协商，效率低下，但个别节点的异常不会对系统总体造成太大影响。

参考

概念

《分布式系统原理介绍 (刘杰)》

架构

软件架构风格汇总

单体式 & SOA & 微服务比较

微服务入门到设计

软件架构入门
Microservices Resource Guide
Microservices——a definition of this new architectural term
Conway’s law
<<微服务设计>>

实例

Redis 性能调优

发表于 2020-11-10 更新于 2023-08-20 分类于缓存

记录下Redis的一些优化点，以后可能随时会有用到。

阅读全文 »

Redis作为缓存系统

发表于 2020-11-09 更新于 2023-08-20 分类于缓存

缓存系统如何工作

缓存的两个特征

在一个层次化的系统中，缓存一定是一个快速子系统，数据存在缓存中时，能避免每次从慢速子系统中存取数据。对应到互联网应用来说，Redis 就是快速子系统，而数据库就是慢速子系统了。
缓存系统的容量大小总是小于后端慢速系统的，我们不可能把所有数据都放在缓存系统中。

Redis作为旁路缓存

作为缓存，我们在访问数据时可能会：

命中：直接将缓存中的数据返回；
miss：缓存缺失，回源到MySQL读取数据，加载到缓存中；

这种情况下，Redis就作为旁路缓存使用，读取缓存、读取数据库和更新缓存的操作都需要在应用程序中来完成。

如果是只读缓存，那么上述的旁路缓存设计就足够了；
如果是读写缓存，还有同步直写（写缓存的同时写DB）和异步写回（写缓存后异步写DB）这两种策略，各有优缺点。
同步直写效率低，但是一致性高；
异步写回效率高，但是一致性低。

Redis 加入秒杀系统

秒杀系统特点

瞬时并发量非常高
一般数据库并发能力是千级别，而Redis的并发能力是万级别甚至更高（加入Cluster以后会更高）。
所以Redis在秒杀系统中的主要作用就是拦截大部分的流量。
读多写少
用户秒杀下单前需要先检查商品是否还有库存，查询库存其实就是简单的键值对查询，而Redis最擅长的就是键值对的存储。

秒杀流程梳理

上面提到Redis的高并发、数据结构特性使得它很适合秒杀场景，但是具体是哪些功能会用到Redis呢？

秒杀活动前
秒杀活动前的一段时间，用户会不断地刷新商品详情页，这个阶段一般会尽量把商品详情页的页面元素静态化，然后使用CDN或是浏览器把这些静态化元素缓存起来。
这个阶段已经有CDN和浏览器，还不需要Redis。
秒杀活动开始阶段
这时大量用户会不断刷新商品详情页并点击秒杀按钮，会产生大量并发请求查询库存，如果通过则触发库存扣减和订单处理。
这个阶段的主要压力在于库存的查验，可以使用Redis保存库存并用于查验。
这里库存的扣减也是放到Redis中执行的，如果放到数据库中，一方面同步数据库和缓存会带来额外的开销，另一方面如果下单量超过了实际库存可能出现超售。
库存的查验和扣减需要保证原子性，可以通过Redis的事务或Lua脚本来实现，或者使用分布式锁来同步。
秒杀活动结束后
这个阶段虽然还会有用户刷新（等待其他用户退单），但是请求已经变得很少了，服务端一般能应付。

缓存满了怎么办？

缓存淘汰（缓存失效策略和主键失效机制）

作为缓存系统都要定期清理无效数据，就需要一个主键失效和淘汰策略，比如 Redis 只能存 5G 数据，可是你写了 10G，那多出来的 5G 数据怎么删？你的数据已经设置了过期时间，但是时间到了，内存占用率还是比较高？这就需要深入到 Redis 的主键失效和淘汰策略中去了。

key 的过期时间控制

在 Redis 当中，有生存期的 key 被称为 volatile。在创建缓存时，要为给定的 key 设置生存期，当 key 过期的时候（生存期为 0），它可能会被删除。

影响生存时间的一些操作
生存时间可以通过使用 DEL 命令来删除整个 key 来移除，或者被 SET 和 GETSET 命令覆盖原来的数据，也就是说，修改 key 对应的 value 和使用另外相同的 key 和 value 来覆盖以后，当前数据的生存时间不同。
比如说，对一个 key 执行 INCR 命令，对一个列表进行 LPUSH 命令，或者对一个哈希表执行 HSET 命令，这类操作都不会修改 key 本身的生存时间。另一方面，如果使用 RENAME 对一个 key 进行改名，那么改名后的 key 的生存时间和改名前一样。
RENAME 命令的另一种可能是，尝试将一个带生存时间的 key 改名成另一个带生存时间的 another_key ，这时旧的 another_key (以及它的生存时间)会被删除，然后旧的 key 会改名为 another_key ，因此，新的 another_key 的生存时间也和原本的 key 一样。使用 PERSIST 命令可以在不删除 key 的情况下，移除 key 的生存时间，让 key 重新成为一个 persistent key 。
如何更新生存时间
可以对一个已经带有生存时间的 key 执行 EXPIRE 命令，新指定的生存时间会取代旧的生存时间。过期时间的精度已经被控制在 1ms 之内，主键失效的时间复杂度是 O（1），
EXPIRE 和 TTL 命令搭配使用，TTL 可以查看 key 的当前生存时间。设置成功返回 1；当 key 不存在或者不能为 key 设置生存时间时，返回 0 。
最大缓存配置
在 redis 中，允许用户设置最大使用内存大小 server.maxmemory
默认为 0，没有指定最大缓存，如果有新的数据添加，超过最大内存，则会使 redis 崩溃，所以一定要设置。redis 内存数据集大小上升到一定大小的时候，就会实行数据淘汰策略。

key 的删除策略

redis 采用的是定期删除+惰性删除策略。

为什么不用定时删除策略?
定时删除,用一个定时器来负责监视 key,过期则自动删除。虽然内存及时释放，但是十分消耗 CPU 资源。在大并发请求下，CPU 要将时间应用在处理请求，而不是删除 key,因此没有采用这一策略.
定期删除+惰性删除是如何工作的呢?
定期删除，redis 默认每个 100ms 检查，是否有过期的 key,有过期 key 则删除。需要说明的是，redis 不是每个 100ms 将所有的 key 检查一次，而是随机抽取进行检查(如果每隔 100ms,全部 key 进行检查，redis 岂不是卡死)。因此，如果只采用定期删除策略，会导致很多 key 到时间没有删除。
于是，惰性删除派上用场。也就是说在你获取某个 key 的时候，redis 会检查一下，这个 key 如果设置了过期时间那么是否过期了？如果过期了此时就会删除。
采用定期删除+惰性删除就没其他问题了么?
不是的，如果定期删除没删除 key。然后你也没即时去请求 key，也就是说惰性删除也没生效。这样，redis 的内存会越来越高。那么就应该采用内存淘汰机制。

Redis 的数据淘汰策略

在 redis.conf 中有一行配置

1	# maxmemory-policy volatile-lru

redis 提供 6种数据淘汰策略：

no-enviction（驱逐）：禁止驱逐数据，当内存不足以容纳新写入数据时，新写入操作会报错（应该没人用）
volatile-lru：当内存不足以容纳新写入数据时，从已设置过期时间的数据集（server.db[i].expires）中挑选最近最少使用的数据淘汰（这种情况一般是把 redis 既当缓存，又做持久化存储的时候才用。不推荐）
volatile-ttl：当内存不足以容纳新写入数据时，从已设置过期时间的数据集（server.db[i].expires）中挑选将要过期的数据淘汰（不推荐）
可以在一些需要“置顶”的业务场景里采用，比如一些新闻、视频需要置顶，这些数据不需要设置过期时间，volatile-ttl就不会删除它们。
volatile-random：当内存不足以容纳新写入数据时，从已设置过期时间的数据集（server.db[i].expires）中任意选择数据淘汰（不推荐）
allkeys-lru：当内存不足以容纳新写入数据时，从数据集（server.db[i].dict）中挑选最近最少使用的数据淘汰（推荐）
allkeys-random：从数据集（server.db[i].dict）中任意选择数据淘汰

注意这里的 6 种机制：

volatile 和 allkeys 规定了是对已设置过期时间的数据集淘汰数据还是从全部数据集淘汰数据；
lru、ttl 以及 random 是三种不同的淘汰策略，ttl 和 random 比较容易理解、实现也会比较简单，lru 会对 key 按失效时间排序，然后取最先失效的 key 进行淘汰。
如果没有设置 expire 的 key, 不满足先决条件(prerequisites); 那么 volatile-lru, volatile-random 和 volatile-ttl 策略的行为, 和 noeviction(不删除) 基本上一致。

使用策略规则

如果数据呈现幂律分布，也就是一部分数据访问频率高，一部分数据访问频率低，则使用 allkeys-lru
如果数据呈现平等分布，也就是所有的数据访问频率都相同，则使用 allkeys-random

自定义缓存淘汰策略

除了缓存服务器自带的缓存失效策略之外（Redis 默认有 6 种策略可选），我们还可以根据具体的业务需求自定义缓存淘汰策略，常见的策略有两种：

定时去清除过期的缓存；
当有用户请求过来时，再判断这个请求所用到的缓存是否过期，过期的话就去底层系统得到新数据并更新缓存；

两种策略各有优劣，第一种的缺点是维护大量缓存的 key 是比较麻烦的，第二种的缺点是每次用户请求过来都要判断缓存失效，逻辑相对比较复杂。需要根据应用场景的特点来权衡选择。

缓存淘汰的实现

设置过期时间
过期时间到了后，Redis 会在读的时候判断是否过期并清除，或者由一个定时任务执行清除操作。
超过 maxmemory 回收
可以设置淘汰机制，比如 LRU、LFU。

LRU 算法的一种简单实现
简单版本的 LRU 算法分两个部分：

一个链表记录 key 的最终访问次序，比如最新访问的在链表头部，最久没访问的在链表末尾，LRU 淘汰机制就是删除链表末尾的节点；
一个散列表记录某个 key 是否存在，并可以找到其在链表中的位置；

Redis 中的 LRU 实现

Redis-LRU算法
代码位置：evict.c/freeMemoryIfNeeded
Redis 中并没有直接使用上述的 LRU 算法，主要是因为维护LRU链表开销较大，而是退一步使用了抽样淘汰的机制：

每次从缓存对象集合中随机取出一部分样本（20个key），进行下面的过期检测；
按 LRU 算法排序；
取 idle 值（评分）最小的淘汰；
如果有多于25%的key是过期了的，则重复步骤1。

为了支持LRU，Redis中使用了一个全局的LRU时钟server.lruclock：

#define REDIS_LRU_BITS 24

// 最近一次使用时钟
unsigned lruclock:REDIS_LRU_BITS; /* Clock for LRU eviction */

Redis会在serverCron()中调用updateLRUClock来定期更新LRU时钟：

#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */

int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
    ...
    
    server.lruclock = getLRUClock();
    
    ...
}

unsigned int getLRUClock(void) {
    return (mstime()/REDIS_LRU_CLOCK_RESOLUTION) & REDIS_LRU_CLOCK_MAX;
}

LRU 时间的精度可以通过修改 REDIS_LRU_CLOCK_RESOLUTION 常量来改变。
更新频率即serverCron被调用的频率，和hz参数有关，默认为100ms一次。

计算一个key的最长没有访问时间时，需要注意时钟回卷的情况：
server.unixtime是系统当前的unix时间戳，当lruclock的值超出REDIS_LRU_CLOCK_MAX时，会从头开始计算，所以在计算一个key的最长没有访问时间时，可能key本身保存的lru访问时间会比当前的lruclock还要大，这个时候需要计算额外时间：

// 使用近似 LRU 算法，计算出给定对象的闲置时长
unsigned long long estimateObjectIdleTime(robj *o) {
    unsigned long long lruclock = LRU_CLOCK();
    if (lruclock >= o->lru) {
        return (lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;
    } else {
        return (lruclock + (REDIS_LRU_CLOCK_MAX - o->lru)) *
                    REDIS_LRU_CLOCK_RESOLUTION;
    }
}

Redis中和LRU相关的淘汰策略包括：

volatile-lru：设置了过期时间的key参与近似的lru淘汰策略；

allkeys-lru：所有的key均参与近似的lru淘汰策略。
涉及淘汰的源码如下所示：

int freeMemoryIfNeeded(void) {
...

            /* volatile-lru and allkeys-lru policy */
            // 如果使用的是 LRU 策略，
            // 那么从一集 sample 键中选出 IDLE 时间最长的那个键
            else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
                server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
            {
                struct evictionPoolEntry *pool = db->eviction_pool;

                while(bestkey == NULL) {
                    evictionPoolPopulate(dict, db->dict, db->eviction_pool);
                    /* Go backward from best to worst element to evict. */
                    for (k = REDIS_EVICTION_POOL_SIZE-1; k >= 0; k--) {
                        if (pool[k].key == NULL) continue;
                        de = dictFind(dict,pool[k].key);

                        /* Remove the entry from the pool. */
                        sdsfree(pool[k].key);
                        /* Shift all elements on its right to left. */
                        memmove(pool+k,pool+k+1,
                            sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
                        /* Clear the element on the right which is empty
                         * since we shifted one position to the left.  */
                        pool[REDIS_EVICTION_POOL_SIZE-1].key = NULL;
                        pool[REDIS_EVICTION_POOL_SIZE-1].idle = 0;

                        /* If the key exists, is our pick. Otherwise it is
                         * a ghost and we need to try the next element. */
                        if (de) {
                            bestkey = dictGetKey(de);
                            break;
                        } else {
                            /* Ghost... */
                            continue;
                        }
                    }
                }
            }

...
}

Redis会基于server.maxmemory_samples配置选取固定数目的key，然后比较它们的lru访问时间，然后淘汰最近最久没有访问的key，maxmemory_samples的值越大，Redis的近似LRU算法就越接近于严格LRU算法，但是相应消耗也会变高，对性能有一定影响，maxmemory_samples这个值默认为5。

缓存系统中存在的问题

旁路缓存的雪崩、击穿、穿透问题
旁路缓存的不一致问题

缓存穿透

缓存穿透即即黑客故意去请求缓存中不存在的数据，导致所有的请求都怼到数据库上，从而数据库连接异常。这也是经常提的缓存命中率问题。
应付大规模缓存穿透的方案如下：

利用互斥锁，缓存失效的时候，先去获得锁，得到锁了，再去请求数据库。没得到锁，则休眠一段时间重试
采用异步更新策略，无论 key 是否取到值，都直接返回。value 值中维护一个缓存失效时间，缓存如果过期，异步起一个线程去读数据库，更新缓存。需要做缓存预热(项目启动前，先加载缓存)操作。
提供一个能迅速判断请求是否有效的拦截机制，比如，利用布隆过滤器，内部维护一系列合法有效的 key，将这些数据 hash 到一个足够大的 bitmap 中。迅速判断出，请求所携带的 Key 是否合法有效。如果不合法，则直接返回。

如果一个查询返回的数据为空（不管是数据不存在，还是系统故障），我们仍然把这个空结果进行缓存，但它的过期时间会很短，最长不超过 5 分钟，通过这个直接设置的默认值存放到缓存，这样第二次到缓存中获取就有值了，而不会继续访问数据库，这种办法最简单粗暴。

public Object queryProduct() {
    int cacheTime = 30;
    String cacheKey = "product";
    
    String cacheValue = getFromRedis(cacheKey);
    if (cacheValue != null) {
        return cacheValue;
    } else {
        // 击穿到db
        cacheValue = getFromDB();
        if (cacheValue == null) {
            // 如果发现为空，则缓存个默认值
            cacheValue = "";
        }
        putToRedis(cacheKey, cacheValue, cacheTime);
        return cacheValue;
    }
}

把空结果也给缓存起来，这样下次同样的请求就可以直接返回空了，即可以避免当查询的值为空时引起的缓存穿透。同时也可以单独设置一个缓存区域存储空值，对要查询的key进行进行预先校验，然后再放行给后面的正常缓存处理逻辑。

缓存雪崩

缓存雪崩即缓存同一时间大面积的失效（例如：我们设置缓存时采用了相同的过期时间，在同一时刻出现大面积的缓存过期），这个时候又来了一波请求，结果请求都怼到数据库上，而对数据库 CPU 和内存造成巨大压力，从而导致数据库连接异常，严重的会造成数据库宕机，从而形成一系列连锁反应，造成整个系统崩溃。
缓存雪崩的解决方案如下：

使用互斥锁，但是该方案吞吐量明显下降了，适用于并发量不是特别多的情况下。具体地来说，使用最多的方案是加锁排队，伪代码如下：

public Object queryProduct() {
    int cacheTime = 30;
    String cacheKey = "product";
    String lockKey = cacheKey;
    
    String cacheValue = getFromRedis(cacheKey);
    if (cacheValue != null) {
        return cacheValue;
    } else {
        synchronized (lockKey) {
            cacheValue = getFromRedis(cacheKey);
            if (cacheValue != null) {
                return cacheValue;
            } else {
                cacheValue = getFromDB();
                putToRedis(cacheKey, cacheValue, cacheTime);
            }
        }
        return cacheValue;
    }
}

加锁排队只是为了减轻数据库的压力，并没有提高系统吞吐量。假设在高并发下，缓存重建期间key是锁着的，这时过来1000个请求、999个都在阻塞，同样会导致用户等待超时，属于治标不治本的方案，而且还需要解决分布式锁的问题。

设置过期标志更新缓存。给每一个缓存数据增加相应的缓存标记，记录缓存是否失效，如果缓存标记失效，则更新数据缓存，实现伪代码如下所示：

public Object queryProduct() {
    int cacheTime = 30;
    String cacheKey = "product";
    // 缓存标记
    String signKey = cacheKey + "_sign";

    String signValue = getFromRedis(signKey);
    String cacheValue = getFromRedis(cacheKey);
    if (signValue != null) {
        return cacheValue;
    } else {
        putToRedis(signKey, "1", cacheTime);
        threadPool.submit(() -> {
            cacheValue = getFromDB();
            putToRedis(cacheKey, cacheValue, cacheTime * 2);
        });
        return cacheValue;
    }
}

缓存标记记录缓存数据是否过期，如果过期会触发通知另外的线程在后台去更新实际 key 的缓存。
缓存数据的过期时间比缓存标记的时间延长 1 倍，例如：标记缓存时间 30 分钟，数据缓存 60 分钟，这样，当缓存标记 key 过期后，实际缓存还能把旧数据返回给调用端，直到另外的线程在后台更新完成后，才会返回新缓存。

给缓存的失效时间，加上一个随机值，避免集体失效。
双缓存。我们有两个缓存，缓存 A 和缓存 B。缓存 A 的失效时间为 20 分钟，缓存 B 不设失效时间。自己做缓存预热操作。然后细分以下几个小点：
1. 从缓存 A 读数据库，有则直接返回
2. A 没有数据，直接从 B 读数据，直接返回，并且异步启动一个更新线程。
3. 更新线程同时更新缓存 A 和缓存 B。

缓存预热

缓存预热就是系统上线后，提前将相关的缓存数据直接加载到缓存系统，避免在用户请求的时候，先查询数据库，然后再将数据缓存的问题，用户可以直接查询事先被预热的缓存数据。常见的缓存预热方案包括：

直接写个缓存刷新页面，上线时手工操作下；
数据量不大，可以在项目启动的时候自动进行加载；
定时刷新缓存。

缓存和数据库双写一致性问题

一致性问题是分布式常见问题，讨论比较多的是最终一致性和强一致性。数据库和缓存双写，就必然会存在不一致的问题。
在回答这个问题前，必须先强调一个前提，就是如果对数据有强一致性要求，不能放缓存。我们所做的一切，只能保证最终一致性，从根本上来说，只是降低不一致发生的概率，无法完全避免，因此，我们说有强一致性要求的数据，不能放缓存。

首先，采取正确更新策略，先更新数据库，再删缓存。
其次，因为可能存在删除缓存失败的问题，提供一个补偿措施即可，例如利用消息队列。

具体的设计方案和优缺点可以参考：【原创】分布式之数据库和缓存双写一致性方案解析

下面是对所有策略的分析：

先失效缓存 -> 后更新数据库数据

缺点
如果缓存失效失败,根据策略可能会影响后续的正常的数据更新操作
直接失效缓存会增加后续的一次缓存查询的 Miss
优点
避免数据库更新成功,缓存失效失败,导致缓存中是旧数据
场景
对缓存准确率要求比较高的业务
异常情况
线程 A 需要更新数据库数据，失效缓存；
线程 B 发现缓存没有命中，查询数据库中取出旧的值；
线程 A 更新数据库数据，提交事务，线程 A 将数据放入缓存。

延时双删

在《先失效缓存 -> 后更新数据库数据》这种方案的基础上，增加了一个延时过期的步骤。
即：过期Redis -> 更新数据库 -> 延迟一会再过期一次Redis
这样就可以缓解上边提到的脏读问题了。
但是缺点是过期两次，会占用更多的数据库资源。

先更新数据库数据 -> 后失效缓存

缺点
如果数据更新成功,但是缓存失效失败,缓存中存放的是旧数据
直接失效缓存会增加一次缓存查询的 Miss
优点
更新数据不会强依赖缓存,就算失效缓存失败,也不会影响数据库的更新
场景
对缓存和数据库的一致性要求不是很高的场景
异常情况
在更新数据库数据和失效缓存之前的所有查询,查询到的都是旧数据

更新数据库数据 -> 更新缓存

优点
避免了一次额外的缓存查询 Miss
实时性比较高
缺点
数据库更新成功，但是更新缓存失败，缓存中存储的是旧数据
选择同步还是异步来更新缓存呢？如果是同步更新，更新磁盘成功了，但是更新缓存失败了，你是不是要反复重试来保证更新成功？如果多次重试都失败，那这次更新是算成功还是失败呢？如果是异步更新缓存，怎么保证更新的时序？
比如，我先把一个文件中的某个数据设置成 0，然后又设为 1，这个时候文件中的数据肯定是 1，但是缓存中的数据可不一定就是 1 了。因为把缓存中的数据更新为 0，和更新为 1 是两个并发的异步操作，不一定谁会先执行。
这些问题都会导致缓存的数据和磁盘中的数据不一致，而且，在下次更新这条数据之前，这个不一致的问题它是一直存在的。当然，这些问题也不是不能解决的，比如，你可以使用分布式事务来解决，只是付出的性能、实现复杂度等代价比较大。
场景
缓存粒度比较小,缓存的数据不需要经过计算(更新商品数据,但是缓存还需要用户数据)
异常情况
A 线程查询缓存发现缓存中没有数据,查询数据库；
B 线程更新数据库并且更新了缓存；
A 再把查询的数据放入缓存,缓存中将会是旧数据

更新缓存 -> 更新数据库数据

优点
避免了一次额外的缓存查询 Miss
缺点
缓存更新成功,但是数据库更新失败,导致缓存数据是旧数据;
并且更新缓存失败,根据策略可能导致更新数据库失败。
场景
缓存粒度比较小,缓存的数据不需要经过计算(更新商品数据,但是缓存还需要用户数据)
异常情况
在更新缓存成功和更新数据库数据之前拿到的缓存是和数据库不一致的(不过这种情况造成的负面影响很小)

更新数据库数据 -> 定时同步到缓存

优点
实现简单、鲁棒性高
就算某次同步过程中发生了错误，等到下一个同步周期也会自动把数据纠正过来。
缺点
缓存更新不实时。
如果缓存的数据太大，更新速度慢到无法接受，可以选择增量更新，每次只更新从上次缓存同步至今这段时间内变化的数据，代价是实现起来会稍微有些复杂。

缓存更新总结

如果对一致性要求没有那么高，一般是先更新数据库然后删除缓存。
如果对一致性要求比较高，那么在缓存删除失败后，需要把删除事件放到队列里消费。
如果对一致性要求更高点，那么需要将更新数据库、更新缓存、查询缓存的操作放到一个队列里消费

如何解决 redis 的并发竞争 key 问题

这个问题大致就是，同时有多个子系统去 set 一个 key。这个时候要注意什么呢？大家思考过么。百度上的答案基本都是推荐用 redis 事务机制，但这里不推荐使用 redis 的事务机制。因为我们的生产环境，基本都是 redis 集群环境，做了数据分片操作，你一个事务中有涉及到多个 key 操作的时候，这多个 key 不一定都存储在同一个 redis-server 上。因此，Redis 的事务机制，十分鸡肋。

如果对这个 key 操作，不要求顺序
这种情况下，准备一个分布式锁，大家去抢锁，抢到锁就做 set 操作即可，比较简单。
如果对这个 key 操作，要求顺序
假设有一个 key1,系统 A 需要将 key1 设置为 valueA,系统 B 需要将 key1 设置为 valueB,系统 C 需要将 key1 设置为 valueC.
期望按照 key1 的 value 值按照 valueA–>valueB–>valueC 的顺序变化。这种时候我们在数据写入数据库的时候，需要保存一个时间戳。假设时间戳如下
系统 A key 1 {valueA 3:00}
系统 B key 1 {valueB 3:05}
系统 C key 1 {valueC 3:10}
那么，假设这会系统 B 先抢到锁，将 key1 设置为{valueB 3:05}。接下来系统 A 抢到锁，发现自己的 valueA 的时间戳早于缓存中的时间戳，那就不做 set 操作了。以此类推。
其他方法，比如利用队列，将 set 方法变成串行访问也可以。

缓存降级

当访问量剧增、服务出现问题（如响应时间慢或不响应）或非核心服务影响到核心流程的性能时，仍然需要保证服务还是可用的，即使是有损服务。系统可以根据一些关键数据进行自动降级，也可以配置开关实现人工降级。
降级的最终目的是保证核心服务可用，即使是有损的。而且有些服务是无法降级的（如加入购物车、结算）。
在进行降级之前要对系统进行梳理，看看哪些服务是必须誓死保护的、哪些是可降级的。比如可以参考日志级别设置预案：

一般：比如有些服务偶尔因为网络抖动或者服务正在上线而超时，可以自动降级；
警告：有些服务在一段时间内成功率有波动（如在 95~100%之间），可以自动降级或人工降级，并发送告警；
错误：比如可用率低于 90%，或者数据库连接池被打爆了，或者访问量突然猛增到系统能承受的最大阀值，此时可以根据情况自动降级或者人工降级；
严重错误：比如因为特殊原因数据错误了，此时需要紧急人工降级。

缓存污染

什么是缓存污染呢？在一些场景下，有些数据被访问的次数非常少，甚至只会被访问一次。当这些数据服务完访问请求后，如果还继续留存在缓存中的话，就只会白白占用缓存空间。这种情况，就是缓存污染。

我们来看一下各种过期策略是否能解决缓存污染问题：

allkeys-random：对所有key进行随机的淘汰，因为不确定之后同一个key是否还会被访问到，所以这个策略会导致缓存缺失问题。
volatile-random：和allkeys-random类似。
volatile-ttl：针对的是设置了过期时间的数据，把这些数据中剩余存活时间最短的筛选出来并淘汰掉，这种策略并不能直接反映数据被再次访问的情况，也有导致缓存缺失的问题。
一般业务会根据数据生效时间范围来决定数据的过期时间，因此过期时间短的很有可能就是用一下就不用的数据，所以这种情况下volatile-ttl是可以缓解缓存污染问题的。
lru
把使用最少的淘汰掉。
但是使用LRU策略在处理扫描式单次查询操作时，无法解决缓存污染，因为这些key被扫描过一次后最近访问时间都是一样的。因为存在这种问题，因此Redis4.0增加了LRU淘汰策略。
lfu
与 LRU 策略相比，LFU 策略中会从两个维度来筛选并淘汰数据：一是，数据访问的时效性（访问时间离当前时间的远近）；二是，数据的被访问次数。
LFU 缓存策略是在 LRU 策略基础上，为每个数据增加了一个计数器，来统计这个数据的访问次数。当使用 LFU 策略筛选淘汰数据时，首先会根据数据的访问次数进行筛选，把访问次数最低的数据淘汰出缓存。如果两个数据的访问次数相同，LFU 策略再比较这两个数据的访问时效性，把距离上一次访问时间更久的数据淘汰出缓存。

缓存数据迁移

什么时候会遇到要将Redis数据迁入、迁出的情况？比如要将Sentinel集群迁移到Cluster集群。
目前一个比较常用的Redis数据迁移工具是Redis-shake。
Redis-shake 的基本运行原理，是先启动 Redis-shake 进程，这个进程模拟了一个 Redis 实例。然后，Redis-shake 进程和数据迁出的源实例进行数据的全量同步。
源实例先把 RDB 文件传输给 Redis-shake，Redis-shake 会把 RDB 文件发送给目的实例，等到同步完毕后，源实例再将增量命令发送给Redis-shake，Redis-shake 负责把这些增量命令再同步给目的实例。

《设计数据密集型应用》

发表于 2020-11-08 更新于 2022-10-09 分类于读书

一～四章讲单机数据库。
五～九章讲分布式数据库，适合多看几遍。
十～十二讲数据如何被更高效地处理，即批处理、流处理。

阅读全文 »

Lab_2_Raft

发表于 2020-11-04 更新于 2022-10-09 分类于 6.824

前置知识

GFS

Fault-Tolerant Virtual Machines（容错虚拟机）

Raft

Apollo 原理总结

发表于 2020-10-20 更新于 2023-08-20 分类于分布式系统

概念

App: App信息
AppNamespace: App下Namespace的元信息
Cluster: 集群信息
Namespace: 集群下的namespace
Item: Namespace的配置，每个Item是一个key, value组合
Release: Namespace发布的配置，每个发布包含发布时该Namespace的所有配置
Commit: Namespace下的配置更改记录
Audit: 审计信息，记录用户在何时使用何种方式操作了哪个实体。

Apollo架构

Apollo架构——图片来自Apollo-github

Apollo Client：为应用提供配置查询功能；
Apollo Config Service：提供配置的读取、推送等功能，服务对象是 Apollo Client；
Apollo Portal：Apollo管理界面，为开发者提供配置修改功能；
Apollo Admin Service：提供配置修改、发布等功能，服务对象是Apollo Portal。

服务发现和负载均衡

在Apollo中，Config Service和Admin Service都是多实例、无状态部署的，需要将自己注册到Eureka。
Eureka负责服务发现，在Eureka之上Apollo又架了一层Meta Server用于封装Eureka的服务发现接口：

Client通过域名访问Meta Server获取Config Service服务列表（IP+Port），而后直接通过IP+Port访问服务，同时在Client侧会做load balance、错误重试；
Portal通过域名访问Meta Server获取Admin Service服务列表（IP+Port），而后直接通过IP+Port访问服务，同时在Portal侧会做load balance、错误重试。

为什么Apollo使用Eureka而不是别的服务发现组件，比如ZooKeeper？

提供了完整的服务注册和发现实现，用起来省心；
项目基础是SpringCloud，已经有应用Eureka的基础；

Meta Server部署在哪里？
Meta Server只是一个逻辑角色，在部署时和Config Service是在一个JVM进程中的，所以IP、端口和Config Service一致

服务端实现原理

服务端的主要任务是维护配置信息，以及将配置信息推送到客户端。

服务端推送大体流程

用户在Portal操作配置发布
Portal调用Admin Service的接口操作发布
Admin Service发布配置后，发送ReleaseMessage给各个Config Service
Config Service收到ReleaseMessage后，通知对应的客户端

发送ReleaseMessage给Config Service的过程

Apollo配置信息的发布——图片来自Apollo-github
用户操作配置发布后，Admin Service会往ReleaseMessage表插入一条消息记录，然后Config Service定时轮询这张表来消费消息。
ApolloPortol会调Admin服务发出消息，这时，Admin Service作为Producer发出消息，各个ConfigService作为Consumer消费消息，为了减少对外部的依赖，Apollo发送消息的功能是通过数据库自己实现的一个简单的消息队列。

Admin操作Release：com.ctrip.framework.apollo.portal.controller.ReleaseController#createRelease
在Admin Service的后台操作界面上可以看到Release操作入口。
Admin向ReleaseMessage表插入一条消息记录：com.ctrip.framework.apollo.adminservice.controller.ReleaseController#publish
该消息的内容就是配置发布的AppId+Cluster+Namespace。
注意在“发消息”前，先把发布信息存到了Release表中。
定时扫描消息，
扫描消息：com.ctrip.framework.apollo.biz.message.ReleaseMessageScanner
定时任务逻辑：批量处理，每次扫描500条，每条消息分别触发所有消息监听器（ReleaseMessageListener）。
定时任务线程池配置：每100毫秒执行一次，core线程数只有1，但是总线程数为Integer.MAX_INT。
Config Service通知客户端
代码入口：NotificationControllerV2#handleMessage
注意NotificationControllerV2这个Controller本身也是个消息监听器。
Config Service会从消息中获取配置发布的AppId+Cluster+Namespace，然后通知客户端（通知客户端的过程见下面）。

Config Service通知客户端的过程

客户端发起一个HTTP请求到Config Service
入口：/notifications/v2，对应NotificationControllerV2（注意和上面的消息监听器是同一个类）。
Config Service将请求挂起
通过Spring 的 DeferredResult将请求挂起，默认等待60秒。
如果在等待期间有该客户端关注的配置（Namespace）发布，则NotificationControllerV2会调用DeferredResult#setResult传入变化的Namespace信息，同时该请求也会立刻返回。
反之，如果60秒内都没有该客户端关注的配置发布，则返回HTTP状态码304给客户端。
客户端请求最新的Namespace配置
如果Config Service返回了配置信息、客户端获取到变化的Namespace信息后，客户端就会立即请求Config Service获取该Namespace的最新配置。

客户端实现原理

客户端主要任务是从Config Service获取配置信息（Push和Pull都有），并在本地维护一个配置文件缓存。
Apollo配置在客户端的维护——图片来自Apollo-github

客户端long-polling

客户端会和服务端维持一个长连接，以及时接收到配置的变更信息。
入口：com.ctrip.framework.apollo.internals.RemoteConfigLongPollService#startLongPolling
客户端长轮询的是Config Service的配置变更通知接口。当有新通知时就会触发RemoteConfigRepository，立即轮询Config Service的配置读取/configs/{appId}/{clusterName}/{namespace:.+}接口。

客户端定时Pull

客户端定时从Config Service拉取应用的配置信息，使用的接口和上面的long-polling一样：/configs/{appId}/{clusterName}/{namespace:.+}。
入口：RemoteConfigRepository#scheduleLongPollingRefresh
这是一个fallback机制，主要目的是防止推送机制失效导致配置不更新。
客户端定时拉取会上报本地版本，所以一般情况下，对于定时拉取的操作，服务端都会返回304 - Not Modified。
定时频率默认为每5分钟拉取一次，客户端也可以通过在运行时指定System Property: apollo.refreshInterval来覆盖，单位为分钟。

客户端本地对配置的维护

客户端从Apollo配置中心服务端获取到应用的最新配置后，会保存在内存中
客户端会把从服务端获取到的配置在本地文件系统缓存一份
在遇到服务不可用，或网络不通的时候，依然能从本地恢复配置
应用程序可以从Apollo客户端获取最新的配置、订阅配置更新通知

参考

Sentinel原理总结

发表于 2020-09-15 更新于 2022-10-09 分类于分布式系统

Sentinel vs Hystrix

Sentinel 与 Hystrix 的对比

阅读全文 »

单体式 & SOA & 微服务

架构、架构风格和系统架构

为什么转微服务

单体式缺陷

SOA缺陷

微服务

为什么迁移到微服务

（Componentization via Services）组件化和服务

Organized around Business Capabilities（围绕业务功能组织/领域驱动设计）

应用拆分

服务大小的确定

服务边界的确定

Products not Projects（产品而不是项目）

Smart endpoints and dumb pipes

微服务和SOA的区别

SOA是什么？

微服务、SOA、水平分层架构之间的区别

CAP

CAP概念

CAP应用

Lease

基于lease 的分布式cache 系统

lease 机制的分析

基于lease 机制确定节点状态

lease 的有效期时间选择

Quorum

write-all-read-one

Quorum 定义

读取最新成功提交的数据

基于Quorum 机制选择primary副本

负载均衡

数据一致性保证

高可用

高可用级别

副本控制

中心化副本控制协议

primary-secondary 协议

数据更新基本流程

数据读取方式

primary 副本的确定与切换

数据同步

去中心化副本控制协议

参考

概念

架构

单体式 & SOA & 微服务 比较

微服务入门到设计

实例

缓存系统如何工作

缓存的两个特征

Redis作为旁路缓存

Redis 加入秒杀系统

秒杀系统特点

秒杀流程梳理

缓存满了怎么办？

缓存淘汰（缓存失效策略和主键失效机制）

key 的过期时间控制

key 的删除策略

Redis 的数据淘汰策略

自定义缓存淘汰策略

缓存淘汰的实现

Redis 中的 LRU 实现

缓存系统中存在的问题

缓存穿透

缓存雪崩

缓存预热

缓存和数据库双写一致性问题

先失效缓存 -> 后更新数据库数据

延时双删

先更新数据库数据 -> 后失效缓存

更新数据库数据 -> 更新缓存

更新缓存 -> 更新数据库数据

更新数据库数据 -> 定时同步到缓存

缓存更新总结

如何解决 redis 的并发竞争 key 问题

缓存降级

缓存污染

缓存数据迁移

前置知识

GFS

单体式 & SOA & 微服务比较