算法

负载均衡算法及实践

D瓜哥
前几天在看一个资料时,看到关于负载均衡算法的介绍。最近也在研究 Spring Cloud 和 Apache Dubbo 等微服务框架。正好负载均衡是微服务框架中一个很重要的知识点。就动手做个整理和总结。方便后续学习。 听朋友建议,这篇文章还可以在算法对比,客户端负载均衡与服务端负载均衡区分等两方面做些补充。这些内容后续再补充加入进来。 常见的负载均衡算法 轮询(Round Robin)法 轮询选择指的是从已有的后端节点列表中按顺序依次选择一个节点出来提供服务。 优点:试图做到请求转移的绝对均衡。实现简单,使用广泛。 加权轮询(Weighted Round Robin)法 实际使用中各个节点往往都带有不同的权重,所以一般都需要实现带权重的轮询选择。 权重高的被选中的次数多,权重低的被选中的次数少。 优点:是 轮询(Round Robin)法 改良版。适用于服务器配置不一致时,可以将配置好的服务器多干活,配置差的服务器少干活以使机器的负载达到相同的水平。 静态轮询(Static Round Robin)法 HAProxy 中实现的一个负载均衡算法。 没有后台服务器的限制,服务器启动时,修改权重也不会生效。增删服务器时,服务器准备就绪后,会立即加入到服务队列中。 随机(Random)法 通过随机函数,根据后端服务器列表的大小值来随机选择其中一台进行访问。由概率统计理论可以得知,随着调用量的增大,其实际效果越来越接近于平均分配流量到每一台后端服务器,也就是轮询的效果。 加权随机(Weighted Random)法 与加权轮询法类似,加权随机法也是根据后端服务器不同的配置和负载情况来配置不同的权重。不同的是,它是按照权重来随机选择服务器的,而不是顺序。 原地址哈希(IP Hashing)法 源地址哈希的思想是获取客户端访问的IP地址值,通过哈希函数计算得到一个数值,用该数值对服务器列表的大小进行取模运算,得到的结果便是要访问的服务器的序号。 优点:保证了相同客户端 IP 地址将会被哈希到同一台后端服务器,直到后端服务器列表变更。根据此特性可以在服务消费者与服务提供者之间建立有状态的 Session 会话。 URI 哈希(URI Hashing)法 HAProxy 中实现的一个负载均衡算法。支持部分 URI(问号之前)和完整 URI 两种模式。

分布式事务概述

D瓜哥
现在手机银行转账已经司空见惯。但是,D瓜哥一直在思考,银卡跨行转账是如何保证事务一致性的?借机就对分布式事务,做了简单地了解。 2PC 两阶段提交(2pc, two-phase commit protocol),2pc是非常经典的强一致性、中心化的原子提交协议。中心化是指协议中有两类节点:一个中心化协调者节点(coordinator)和N个参与者节点(participant、cohort)。 顾名思义,两阶段提交协议的每一次事务提交分为两个阶段: 在第一阶段,协调者询问所有的参与者是否可以提交事务(请参与者投票),所有参与者向协调者投票。 在第二阶段,协调者根据所有参与者的投票结果做出是否事务可以全局提交的决定,并通知所有的参与者执行该决定。在一个两阶段提交流程中,参与者不能改变自己的投票结果。两阶段提交协议的可以全局提交的前提是所有的参与者都同意提交事务,只要有一个参与者投票选择放弃(abort)事务,则事务必须被放弃。 两阶段提交协议也依赖与日志,只要存储介质不出问题,两阶段协议就能最终达到一致的状态(成功或者回滚) 优点 强一致性,只要节点或者网络最终恢复正常,协议就能保证顺利结束;部分关系型数据库(Oracle)、框架直接支持 缺点 网络抖动导致的数据不一致: 第二阶段中协调者向参与者发送commit命令之后,一旦此时发生网络抖动,导致一部分参与者接收到了commit请求并执行,可其他未接到commit请求的参与者无法执行事务提交。进而导致整个分布式系统出现了数据不一致。 超时导致的同步阻塞问题: 2PC中的所有的参与者节点都为事务阻塞型,当某一个参与者节点出现通信超时,其余参与者都会被动阻塞占用资源不能释放。 单点故障的风险: 由于严重的依赖协调者,一旦协调者发生故障,而此时参与者还都处于锁定资源的状态,无法完成事务commit操作。虽然协调者出现故障后,会重新选举一个协调者,可无法解决因前一个协调者宕机导致的参与者处于阻塞状态的问题。 基于两阶段提交的分布式事务在提交事务时需要在多个节点之间进行协调,最大限度地推后了提交事务的时间点,客观上延长了事务的执行时间,这会导致事务在访问共享资源时发生冲突和死锁的概率增高,随着数据库节点的增多,这种趋势会越来越严重,从而成为系统在数据库层面上水平伸缩的"枷锁", 这是很多Sharding系统不采用分布式事务的主要原因。 3PC 三阶段提交协议(3pc Three-phase_commit_protocol)主要是为了解决两阶段提交协议的阻塞问题,从原来的两个阶段扩展为三个阶段,并且增加了超时机制。 3PC 的三个阶段分别是 CanCommit、PreCommit、DoCommit CanCommit 协调者向所有参与者发送CanCommit命令,询问是否可以执行事务提交操作。如果全部响应YES则进入下一个阶段。 PreCommit 协调者向所有参与者发送PreCommit命令,询问是否可以进行事务的预提交操作,参与者接收到PreCommit请求后,如参与者成功的执行了事务操作,则返回Yes响应,进入最终commit阶段。一旦参与者中有向协调者发送了No响应,或因网络造成超时,协调者没有接到参与者的响应,协调者向所有参与者发送abort请求,参与者接受abort命令执行事务的中断。 DoCommit 在前两个阶段中所有参与者的响应反馈均是YES后,协调者向参与者发送DoCommit命令正式提交事务,如协调者没有接收到参与者发送的ACK响应,会向所有参与者发送abort请求命令,执行事务的中断。

动态规划入门

D瓜哥
Tip 本篇文章是 D瓜哥 读《算法导论》的读书笔记。记录下来是为了方便整理思路,以便啃下“动态规划”这块骨头。 目前侧重记录书中关于“动态规划原理”的介绍。接下来会把书中的例子结合 Java 代码演绎一遍。后续会根据D瓜哥的学习和理解,逐步完善。最终希望达到通过这一篇文章,就能学会、理解动态规划。 山高水远,道阻且长,愿一起努力!  — 2020年01月23日 动态规划(dynamic programming)与分治方法相似,都是通过组合子问题的解来求解原问题(在这里,“programming”指的是一种表格法,并非编写计算机程序)。 分治方法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,求出原问题的解。 动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题(子问题的求解是递归进行的,将其划分为更小的子子问题)。 在这种情况下,分治算法会做许多不必要的工作,它会反复地求解那些公共子问题。 动态规划算法对每个子子问题只求解一次,将其解保存在一个表格中,从而无需每次求解一个子子问题时都重新计算,避免了不必要的计算工作。 动态规划方法通常用来求解最优化问题(optimization problem)。 设计一个动态规划算法的步骤: 刻画一个最优解的结构特征。 递归地定义最优解的值。 计算最优解的值,通常采用自底向上的方法。 利用计算出的信息构造一个最优解。 算法原理 适合应用动态规划方法求解的最优化问题应该具备的两个要素:最优子结构和子问题重叠。 最优子结构 用动态规划方法求解最优化问题的第一步就是刻画最优解的结构。如果一个问题的最优解包含其子问题的最优解,则称此问题具有最优子结构性质。因此,某个问题是否适合应用动态规划算法,它是否具有最优子结构性质是一个好线索。 发掘最优子结构性质的通过模式 证明问题最优解的第一个组成部分是做出一个选择。做出这次选择会产生一个或多个待解的子问题。 对于一个给定问题,在其可能的第一步选择中,你假定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的,只是假定已经知道了这种选择。 给定可获得最优解的选择后,你确定这次选择会产生哪些子问题,以及如何最好地刻画子问题空间。 利用“剪切-粘贴”(cut-and-paste)技术证明:作为构造原问题最优解的组成部分,每个子问题的解就是它本身的最优解。证明这一点是利用反证法:假定子问题的解不是其自身的最优解,那么我们就可以从原问题的解中“剪切”掉这些非最优解,将最优解“粘贴”进去,从而得到原问题一个更优的解,这与最初的解是原问题最优解的前提假设锚段。

只要一部计算机,就可以创造出无限的世界

D瓜哥
曾经写给学弟学妹的一封信。我觉得还行,发出来,希望对刚学计算机专业的朋友有所帮助。当然,如果哪位朋友有更好的想法,也请留言,大家讨论讨论。原文如下: 致师弟师妹的一封信 各位朋友: 大家好! 从本周开始,我必须专心为我的前程奋斗了。很可惜不能和大家一起学习了。这封信就算是我和大家的一个告别吧。 首先,感谢史老师给我提供这个和大家一起学习和交流的机会,让我和大家一起度过了一段特殊而愉快的时光。 其次,我应该感谢大家。由于本人水平有限,也许我没能让大家从我这里学到太多知识,但是大家却让我学会了很多东西,锻炼了我很多方面的能力。单凭这一点,我就应该感谢大家。同时,很多人把我当朋友,更使我感激不尽。 再次,在这短暂而又宝贵的大学时光里,大家走的路应该和我的基本一样。我以一个过来人的身份,和大家分享一下我的学习经验吧,希望可以让大家少走甚至不走弯路。 先说一点我们所学科目的情况吧。 Linux:一定要动手敲指令。在我们一年半的学习时光里,我认为Linux是我们所学的所有实践性学科里面最简单的一科了!只要把指令记好用熟就行了!另外,指令不需要背,用多了自然就记住了。(相信95%的同学都知道cd是什么意思吧!为什么呢?因为用它的次数多!)多提一点,一定要多尝试! Java或者C#或者PHP(由于个人比较喜欢Java,所以,一下描述Java的地方,你可以同样换成C#或在PHP等):这是我们大家必须要下苦功夫学好的课!而且一定一定要学精!它们在我们的课程体系结构中的作用,就像是地基对于这个房子的作用!根基不好,房子很难建高的!即使建好也是豆腐渣工程。毕竟“空中楼阁”只存在于我们的想象中。它们是学习JSP、ASP.NET、J2EE、“游戏开发”、网页开发等等的基础,Java或者C#或者PHP学不会,这些课很难学好!(我这里有Java的教学视频,感兴趣的同学可以来我寝室拷贝。也可以上网下载:http://www.verycd.com/topics/93279/(请下载J2SE的)) 数据库:重点是关系模型、 SQL语句以及后面的数据库设计。做动态网站的技术、做桌面程序,甚至做手机应用等,都会用到数据库!以后工作中数据模型设计、数据查询等都要求有比较扎实的数据库基础才行。 数据结构:我个人认为学习数据结构就是学习一种解决问题的思想。其实,类库已经实现了我们所学的所有的数据结构,到时会用就行了! 现在NBA正在进行季后赛,就用乔丹的一句话,作为所有学科的一个共同的建议送给大家: I can accept failure, but I can’t accept not trying. — Michael Jordan 其实学习就是不断尝试,不断总结,不断进取的一个过程。我可以用我的尝试告你一个正确的结果,但是自己尝试出来的结果印象更加深刻! 再说一点我的个人的学习感触吧。我个人认为,这些比我们大家在学校学到知识更为重要!知识马上就会过时,但是学习的方法却可以带领我们走的更远。 一、享受学习。如果我们把学习当成像玩游戏、听音乐一样的娱乐活动时,我想这会给我们一种全新的感觉。Study hard,have fun,make history! By Jeff Bezos & Joy Lee (努力学习,乐在其中,并创造历史!—Jeff Bezos(Amazon.com的创办者兼CEO,Joy Lee就是我。(*__*) 嘻嘻…… 这句话是我从他的一句话里改编过来的!))