云平台用一句话概括就是成千上万台机器被抽象成按需使用的资源池。但资源池只是表象真正让这个池子有序转动的是一系列藏在后台的算法决策一台新实例该落在哪台物理机、一个请求到网关后该转发给哪个后端、数据写了三个副本后怎么保证它们彼此一致、流量突然暴涨时系统要不要提前扩容。这篇是系列里的第十五篇也是云计算专题下的算法篇。之前聊过云的基本架构、虚拟化、存储与网络这次专门把算法两个字拎出来讲。我不会按教科书罗列几十个算法而是从云平台真实面临的问题出发把调度、负载均衡、共识、存储数据算法、自动扩缩容这几个核心场景摊开讲清楚它们背后的原理、选型逻辑和实操中容易踩的坑。适合刚接触云计算的人建立全景认知也适合已经写过一些云上代码、想搞明白底层机制的同学。1. 一篇文章看懂云计算算法到底分布在哪儿1.1 云平台背后四个天天在跑的决策场景先说结论云平台的算法并不玄乎它们集中分布在四个高频场景里。第一个是实例调度。用户提交创建一台云服务器的请求调度器要在几毫秒内从成千上万个物理节点中挑一个出来让这台实例跑上去。这个选择必须满足用户的资源规格、网络归属、高可用要求还要尽量让整集群负载均衡。这是典型的约束满足与优化问题。第二个是流量调度。请求从公网进入负载均衡器再转发到后端真实服务节点。负载均衡器要根据每个节点的健康状态、权重、当前连接数做出即时路由决策。用户感知到的快与慢稳定or报错很多时候就取决于这一跳的判断。第三个是多副本一致性。数据在云上往往保存多份副本分布在不同的机器甚至不同的机房。每次写入都可能涉及多个副本同时修改怎么保证它们最终看到同一份数据、并且互相不打架就是共识算法和分布式事务要处理的事。第四个是容量自动化。平台要持续监控每个业务的CPU、内存、QPS等指标判断是否需要扩缩容。这个决策是动态的、持续发生的。这个场景把自动化三个字体现得最充分也是算法发挥预测能力的地方。1.2 云计算算法追求的两个底层目标效率与确定性很多同学第一次接触云计算算法时会问为什么云平台里跑的大多不是那些看起来高大上的机器学习模型而是一些经典算法我的理解是云平台的关键路径有两个底层追求一是效率二是确定性。效率容易理解同样一台物理机能塞更多虚拟机或容器成本就更低同样一个网关能转发更多请求吞吐就更高。算法在这里的作用是把资源利用率往上顶。而确定性指的是当集群出现网络分区、机器宕机、流量突增时系统的行为必须是可预期的不能靠统计概率去赌。比如负载均衡不能平均分配请求时要有明确的备用策略写入副本达不到多数派时必须明确拒绝写入而不是自己猜一个结果。所以云平台的关键路径上大量使用的是可证明、可预测的经典算法比如一致性哈希、Raft共识、纠删码。机器学习更多被用在容量预测、异常检测这类提前预判场景因为那里允许一定程度的误差需要的是趋势判断而不是绝对正确。2. 调度与负载均衡算法你的请求被谁接走2.1 轮询、加权轮询与最少连接三种最基础的负载均衡策略负载均衡是云平台上最贴近用户感知的算法战场。所有请求进到系统第一道关就是它。我们从小到大拆解。最基础的是轮询Round Robin。请求按顺序轮流分给后端节点A、B、C三个节点就 A→B→C→A 这样循环。它的优点是实现极其简单、无状态适合所有后端能力相似的场景。缺点也非常明显完全不感知后端负载。如果某个节点已经忙到快超时轮询照样把新请求塞进去反而拖慢了整体响应。于是有了加权轮询。给每个节点配一个权值比如 ABC 511表示 A 预期承担更多流量。一般实现会采用平滑加权轮询在按比例分配的同时避免连续打向同一个节点造成那个节点瞬间过载。这种方式在配置好权重后就很稳定适合后端性能差异明确的场景。但静态权重说到底还是靠人去估计不够灵动。最常用的动态策略是最少连接Least Connections每次选择当前活跃连接数最少的节点。它能自动适应后端处理速度的差异某个节点处理快连接数下降得快就会被多分配处理慢的连接数上升自然少分。当然它也有盲区比如有些请求虽然连接数少但特别消耗CPU这时候光看连接数就不够实践中还会结合CPU负载、内存占用等做综合打分。我接触过的生产系统大多是最少连接 节点健康检查 过载保护三者配合而不是单靠一种算法打天下。2.2 一致性哈希与虚拟节点缓存和路由的经典解法到达负载均衡层之后很多请求还要继续往后端缓存或数据库路由。这里最经典的问题是对 key 做哈希后决定数据放在哪里。很多人第一次学分布式路由时第一个念头是取模key 的哈希结果对节点数 N 取余得到0到N-1之间的值对应到具体节点。这个方案在小规模集群下没有任何问题。但一旦节点数量从3变成4几乎所有 key 的映射都变了意味着大量缓存失效、数据需要迁移。在云上节点是天天变化的这种牵一发动全身的行为完全不可接受。一致性哈希就是来解决这个问题的。思路是把哈希值组织成一个首尾相接的环范围0到2^32-1每个节点通过哈希计算放到环上。当需要查找某个 key 时计算 key 的哈希值然后沿顺时针方向找到的第一个节点就是它的归属节点。当集群新增一个节点时只有环上从新节点逆时针到上一个节点之间的 key 会被重新映射其他 key 完全不受影响。在均匀分布假设下新增一个节点大约只需要迁移1/N的数据旧节点从3变4时大约只有四分之一的 key 受影响效果比取模好太多。但一致性哈希还有一个大坑节点数量少时哈希环容易分布不均出现数据倾斜。比如只有三五个节点可能恰好挤在环的一段结果大量 key 都落到某个节点上其他节点闲得没事干。解决方案是引入虚拟节点每个物理节点在环上注册几十个甚至上百个虚拟位置让它们在环上均匀散开。这样做既保持了数据映射的分散性又让节点增减时的迁移负担更小。这个技巧现在基本是一致性哈希的标配谁不加虚拟节点谁吃亏。2.3 从单机调度到集群调度位置、资源与约束的三方博弈负载均衡管的是请求去哪集群调度管的是实例放在哪。这就是云平台里最重的调度器面对的问题。单机调度时我们只需要考虑一台机器上几个进程怎么抢CPU和内存方法很成熟比如时间片轮转、优先级队列、多级反馈队列。但云平台的集群调度要复杂得多因为它要同时满足三类约束。第一是资源约束。每台物理机的CPU、内存、磁盘、网络带宽都是有限的调度器必须确保放上去的虚拟机和容器总需求不超过剩余容量。听起来简单真做起来要反复做容量核对和碎片整理不然会出现每台机器都剩了零碎资源但装不下一台新实例的情况。第二是亲和性约束。很多场景要求实例必须靠近它在用的数据这叫数据本地性有些场景要求主备节点分布在不同机架甚至不同机房这叫反亲和性。这些约束不是必要条件而是优化目标会让调度问题从能否放入变成如何放入最好复杂度立刻上去。第三是故障域约束。云平台要把一台物理机宕机的影响控制在最小范围。如果容器编排平台把所有副本都调度到同一台机器上那这台机器一挂服务就全部不可用。调度器需要在副本之间尽量拉开物理距离让它们处在不同的故障域中。这一点做到位了后面再谈高度可用才有意义。从架构上看调度器也有不同的组织方式单一集中式调度器实现简单但容易成为瓶颈两级调度器把资源分配和任务调度拆开扩展性更好共享状态调度器用乐观并发模型提高吞吐。选哪种并没有绝对标准取决于集群规模、任务类型和运维能力。我的建议是中小规模优先简单可靠大规模再上更复杂的分层调度架构不要一上来就想做最强的。3. 共识算法与分布式一致性让多副本说同一种话3.1 为什么云上的一致性这么难先看一个日常场景。用户往云数据库里写了张三的余额从100变成200系统为了保证数据安全把这条修改同步到了三个副本。网络是很不靠谱的副本1可能写成功了副本2延迟了副本3所在机器直接宕机了。这时候读请求打到副本2看到的还是100用户会认为数据丢了。这背后的核心理论是CAP定理网络发生分区时系统必须在一致性和可用性之间做取舍。如果你保证所有副本都一致那么部分副本不可达时就得拒绝读写牺牲可用性如果你保证随时可读写就得允许副本之间存在短暂的不一致。云平台的处理方式是给用户配置项对资金类数据默认强一致对朋友圈点赞这类数据允许最终一致。但无论哪种选择底层都需要机制来协调副本之间的状态这就是共识算法。共识要解决的问题很朴素多个节点如何就某个值达成一致即使其中有节点故障或网络延迟。难点在于节点之间只能通过不可靠的网络通信而且谁也不知道哪个节点会突然宕机。我们追求的不仅是大家都同意而且是这个决定一旦做出就不能被推翻。3.2 Paxos和Raft选举、投票与日志复制谈共识算法绕不开Paxos和Raft。Paxos是经典理论的代表它把节点分成提议者、接受者和学习者三种角色通过两阶段的准备-提交流程达成一致。第一阶段提议者生成一个编号向多数派询问我能不能提这个议案第二阶段如果获得批准再正式提交。这种设计非常优雅但理解门槛高工程实现难度大很多人学了半天还是搞不清细节。Raft就是为了让共识算法可理解而生的。它把共识问题拆成了三个子问题领导者选举、日志复制、安全性。在Raft中集群每个任期选举出一个领导者所有写请求都经由领导者处理领导者把日志条目复制给大多数节点后这条日志才算提交成功。任期号是全局单调递增的网络分区时只有拥有最新日志的节点才有可能当选这保证了已经提交的数据不会因为选举而丢失。我用一个生活类比来解释假设班级里要定一份活动账本选一个班长来记账班长把每条账目念给全体同学听至少过半同学记录一致这条账才算大家认可。如果班长失联大家就重新选举但只有手头账本最全的人更有资格当选这样才能保证以前的记录不被新班长推翻。这就是Raft在云平台里的真实工作方式。3.3 共识算法在云计算里的落地场景与性能代价共识算法不是只在论文里跑它大量出现在云平台的基础组件里。分布式协调服务用共识算法做选主和分布式锁配置文件管理用共识算法保证所有节点拿到同一份配置数据库主从高可用中主节点挂了之后由哪个从节点接管也是靠共识算法投票决定。但共识算法不是免费的午餐。最直接的成本是时延每次写入都要等大多数节点确认跨机房场景下这一来一回可能增加几十甚至上百毫秒。所以在生产系统里很少全局都用强一致通常是把需要强一致的数据范围尽量缩小比如只让元数据走共识而把业务数据做成最终一致。另一个常见问题是多数派的表述容易让人误解它不是超过一半节点在线就行而是要求写入请求必须同时被超过一半的节点接受。这意味着如果网络把一个集群劈成两半只有包含多数派的那个分区能继续服务少数派分区即使内部节点都健康也只能拒绝写入这就是为了防止脑裂带来的不可控。我建议在学习时先掌握Raft再回头对比Paxos事半功倍。工程里重点看四个参数选举超时、心跳间隔、日志复制批量大小、快照策略它们直接影响集群的稳定性和性能。4. 数据可靠与高效纠删码、去重与压缩在存储算法中的配合4.1 纠删码用一点计算换大量存储空间云存储有一个绕不开的指标存储成本。早期最朴素的多副本策略是三副本系统把数据原样复制三份任意一份损坏都能用其他两份恢复。三副本的可靠性和恢复逻辑都非常简单但代价极其昂贵空间利用率只有三分之一。存10TB有效数据实际要占30TB物理空间。纠删码Erasure Coding是一种更聪明的办法。它的核心思想是把数据切分成k个数据块通过编码计算生成m个校验块一共km个块分布在不同的机器上。读取时只要任意k个块正常就能把原始数据完整算出来。比如常见的102纠删码10个数据块加2个校验块空间利用率10/12≈83%远高于三副本的33%同时可以容忍任意2块同时丢失。纠删码和副本之间的取舍并不是简单的哪个更好。副本的优势是读取速度快、恢复时只需复制另一份CPU开销为零纠删码的优势是空间利用率高但读取时需要从多个块拉数据并做编码计算数据恢复时要读取k个块并重新计算消耗大量网络带宽和CPU。所以实际存储系统往往是分层的热数据用多副本保证性能冷数据和温数据切成纠删码降低成本。选择k和m时也有讲究k越大空间利用率越高但单块故障时的恢复代价也越大m越大容错能力越强但额外空间开销也大。我在实践中见过的配置从42到123都有关键看数据重要度和集群规模。另外有个细节容易被忽略纠删码的块绝不能放在同一个故障域里。如果你把数据块和校验块都放在同一台物理机上这台机器一坏所有块一起丢纠删码的保护效果瞬间清零。所以云厂商在做纠删码时会把不同块强制打散到不同机架、不同可用区这给调度器又加了一条约束。4.2 数据去重与布隆过滤器怎么判断这块数据我见过云上存储的大量数据其实是重复的。比如同一份镜像文件被不同用户使用、同一份日志在多台机器上重复采集如果不做处理存储成本会爆炸式增长。数据去重就是干这个的。最简单的去重思路是算哈希把数据块或整个文件的哈希值作为指纹保存下来新的数据块进来时先查指纹如果存在相同的指纹就只保存一个指向已有块的引用不再重复存内容。这里面的关键问题有两个一是怎么划分数据块二是怎么快速判断指纹是否出现过。划分数据块有两种典型做法。固定大小分块实现简单但插入或删除几个字节后后续所有块的边界都会错位导致明明内容大体相同却因为边界对不上而无法去重。内容定义分块CDC是一种更聪明的方式它通过滑动窗口计算内容的哈希特征在内容上寻找自然的切分边界这样即使数据中间插入了一段内容只要其他部分保持连续仍然能被识别成相同的块。代价是计算量变大但去重率明显提高。至于快速判断指纹是否见过布隆过滤器是一个经典选择。它用m个位的位数组和k个哈希函数对每个指纹计算k个位置并置1。查询时如果k个位置都为1就认为可能存在只要有一个位置为0就确定不存在。布隆过滤器最大的优势是用极小的空间完成海量数据的判重。代价是存在误报它只说没有是绝对可信的有却可能出错。因此在工业实现中布隆过滤器会先帮忙排除掉绝大多数肯定没出现过的块剩下的少数疑似对象再去精确查询哈希索引库速度与准确性兼得。4.3 压缩算法选择的权衡延迟优先还是空间优先去重解决的是相同块只存一份压缩解决的是单个块里能不能再瘦身。日志、文本、结构化数据往往有很大的冗余压缩后体积能降一大半。压缩算法不是越厉害越好。像gzip这类算法压缩率不错但压缩和解压都需要较多CPU而一些为速度设计的算法则在压缩率上有所妥协但解压吞吐非常高适合在请求路径上使用。云存储系统里常见的做法是分层选择热数据、高频读取的文件用快速压缩算法尽量减少解压延迟冷数据、备份文件则用高压缩率算法反正读取频率低多花几秒钟解压完全可以接受。还有一个实操经验先去重再压缩或者先压缩再去重顺序不同效果不同。如果先压缩可能导致本应相同的数据块因为压缩后的内容不同而无法去重如果先做块级去重再对唯一的块压缩整体收益通常更好。当然也要看具体数据特征比如已经压缩过的图片和视频文件再压缩收益很低这一步可以通过文件类型做快速判断。5. 自动化闭环指标采集、预测算法与自动扩缩容5.1 自动扩缩容的本质是控制问题云平台最大的卖点之一是弹性流量小的时候少用资源省钱流量大的时候秒级扩容支撑业务。但弹性不是口号它背后是一套自动化的决策闭环——采集指标、判断水位、调整实例数。这套机制本质上不是算法竞赛而是控制理论问题。最直白的方法是阈值策略CPU平均使用率超过80%就扩容一台低于20%就缩容一台。阈值策略实现简单效果也直观但生产环境用起来非常容易翻车。一是抖动问题某次监控采样瞬间飙到高值系统立刻扩容可下一秒流量又回落白白多出一台机器二是振荡问题扩容后CPU降下来但随即触发缩容缩完又涨回去集群在两个阈值之间反复摇摆用户看到的就是容量一直在调整但始终不在合适状态。稍微成熟一点的做法有三个方面。第一指标平滑监控指标先做滑动平均或指数平滑不拿原始值直接触发决策第二设置滞回区间扩容触发点设高一点缩容触发点设低很多中间留出缓冲区避免因为轻微波动来回切换第三引入冷却时间一次扩容动作之后一段时间内不允许缩容让系统稳定下来再说。这些土办法在真实场景中非常有效先把它们吃透比直接上复杂算法靠谱得多。如果从控制理论的角度看上面这些方法背后其实就是比例-积分-微分控制的思想比例项对当前偏差立即响应积分项对持续累积的偏差做纠正微分项抑制偏差的变化趋势。很多云平台的自动扩缩容组件并不会写成PID控制器但你把它拆开看基本都是这个套路。5.2 时间序列预测让扩容提前一步发生阈值策略有一个天生的毛病反应滞后。它必须等流量已经涨上来、指标已经超标才动手而扩容本身需要时间等新实例准备好流量高峰可能已经过去了。想要解决滞后就不能只看现在还要预判未来。云上资源使用数据有一个非常好的特点强周期性。互联网业务的访问量往往有典型的白天高、晚上低工作日与周末不同每周、每天都有相似曲线的规律这些规律让时间序列预测算法有了用武之地。简单有效的方法是指数平滑它对历史数据做加权平均越近的数据权重越大能捕捉近期趋势和水平变化适合没有明显周期性的业务。如果数据有明显的日周期、周周期可以用周期分解类方法把序列拆成趋势项、周期项和随机项分别预测再合并。ARIMA这类自回归模型处理带有相关性的数据更灵活但对调参要求高使用时需要做数据平稳性检验和残差分析。不管用什么预测方法有两件事必须提醒。第一预测结果不是用来直接触发扩容的通常要加一个安全系数比如预测值乘以1.2或1.5再结合当前实际水位做决策。第二模型需要定期重训练。业务是会变的一个模型的预测效果随时间推移会衰减我见过有些系统上线初期预测准得惊人三个月后误差越来越大后来一查是业务做了一次大促活动用户行为模式彻底变了。监控预测误差指标比如平均绝对百分比误差非常必要误差一旦超过阈值就要触发重新训练或人工介入。5.3 更前沿的智能调度算法能不能直接用最近几年关于强化学习、遗传算法、图神经网络用在云资源调度上的研究很多。强化学习的思路是把调度问题建模成智能体与环境的交互过程智能体根据系统状态做出调度动作再根据资源利用率、能耗等指标获得奖励逐步学习最优策略。这类方法理论上能自适应非常复杂的负载模式但离大规模线上落地还有距离。最主要的问题是训练成本高、状态空间巨大而且试错过程在真实环境中风险不可控——流量高峰时让一个没学好的智能体去调度代价可能非常惨重。我的观点是前沿方法适合在离线环境中做仿真、在特定场景做小范围试点生产系统的关键路径还是应该优先保证可解释性和稳定性。真想引入可以先用模拟环境验证再以旁路推荐的方式逐步接入。6. 算法选型经验与避坑实录6.1 选型前先问自己的四个问题很多人在设计云上系统时一上来就说我们要用一致性哈希我们用Raft保证强一致。算法是人家的场景是自己的。我建议在做选型之前先问自己四个问题。第一数据规模有多大。几百个节点的集群和几万个节点的集群算法选择完全不一样。小规模集群用最简单的取模加副本绰绰有余强行引入一致性哈希反而增加维护成本。第二延迟和吞吐要求是什么。每次读请求需要几毫秒还是几十毫秒无所谓写入链路能不能接受多数派确认的额外开销这些问题直接决定了你是不是要上共识算法、要不要做跨区域强一致。第三一致性要求有多高。是强一致、会话一致还是最终一致支付订单这类场景绝对不能靠最终一致糊弄但用户头像的更新就不必小题大做。第四运维能力能不能接住。越是精巧的算法配置参数越多出问题时越难排查。一个团队如果没有专门的分布式系统支持选Raft类组件时要特别谨慎因为选主失败、网络分区、日志落后的排障门槛并不低。6.2 我踩过的几个典型坑先说一致性哈希。前几年做分布式缓存时我最初只是简单地把节点hash到环上没有加虚拟节点。结果集群有六个节点时出现了明显的热点一个节点承载了将近35%的流量其他节点平均只有10%。加虚拟节点后热点立刻缓解。后来我才意识到节点数越少虚拟节点的数量越要舍得配几十上百个虚拟位置一点都不夸张。再说纠删码。有次设计冷数据存储一心想追求最高空间利用率把编码参数配到了162。看着空间利用率很高可真遇到一块磁盘故障后恢复数据需要读取16个块并做大量编码计算恢复时间比我预想的长很多。如果当时选择102虽然空间利用率低一些但故障恢复会快得多。纠删码的关键不是能省多少空间而是故障来了能不能扛得住。还有扩缩容。我见过一个系统把扩容阈值设为50%、缩容阈值设为35%结果两个阈值相差太小系统一天之内扩缩容了二十多次。后来我们把扩容设为80%、缩容设为30%中间加冷却时间终于消停了。自动扩缩容看似简单阈值设计才是真正的艺术必须根据业务波动特征反复调。最后是布隆过滤器。它的误报率让人容易产生错觉反正只是多查询一次问题不大。但如果不监控误报率增长当数据量远超设计容量时位数组很快被置满几乎每个查询都返回可能存在去重系统的查询开销大幅上升整个写入链路被拖慢。设计时给布隆过滤器留足容量余量定期评估它的负载程度非常必要。6.3 场景到算法的快速决策表目标场景推荐算法/机制关键注意事项无状态服务请求分发加权轮询、最少连接后端规格不均匀时优先加权策略分布式缓存/键值路由一致性哈希 虚拟节点节点数量少时要多配虚拟节点选主、分布式锁、配置同步Raft类共识算法注意多数派时延开销缩小强一致范围大块数据持久化存储多副本 纠删码分层热数据用副本冷数据用纠删码数据去重CDC分块 布隆过滤器指纹库先分块去重再压缩监控误报率冷数据压缩高压缩率算法读取频率低时压缩时间可以放宽自动扩缩容平滑指标 滞回区间 时间序列预测预测结果要乘安全系数定期重训练最后分享一点个人体会。云计算里的算法选型最忌讳的是从这个算法很酷出发而应该从系统失败时会怎样出发。一个好的算法方案不是把所有东西做到最强而是让系统在节点宕机、网络分区、流量突增这些坏情况下依然处于一个可控、可理解、可恢复的状态。我看云平台的调度和一致性机制时经常想起城市交通算法就是那些交规和信号灯拥堵时虽然不能保证每辆车都是最快但能保证整个路网不会彻底瘫痪。带着这个视角去学你再看云平台的每一个算法决策就不会觉得它们是孤立的数学题了。
