算法

在上一篇文章中，通过阅读 《In Search of an Understandable Consensus Algorithm》 前三节的内容，对论文的大致内容做了简介，简单说明了一下 Replicated state machines 的用途以及 Paxos 本身存在的问题。 4. Designing for understandability several goals in designing Raft: it must providea complete and practical foundation for system building; it must be safe under all conditions and available under typical operating conditions; it must be efficient for common operations. Our most important goal — and most difficult challenge — was understandability. 从这里可以看出，Raft 设计的初衷就是为了易于理解和便于构建。 There were numerous points in the design of Raft where we had to choose among alternative approaches.

前一段时间，在一次开组会的时候，给小组成员简单介绍了一下 Raft 协议。大概四年前读过 Raft 的论文，这次分享的时候，好多好多细节都忘了。所以，再次把 《In Search of an Understandable Consensus Algorithm》 这篇论文找出来，重读一遍，做个笔记和摘要，方便后续学习和复习。 Abstract Raft is a consensus algorithm for managing a replicated log. 开篇摘要就点出了 Raft 的特点： Raft 是一种管理复制日志的共识算法。 In order to enhance understandability, Raft separates the key elements of consensus, such as leader election, log replication, and safety, and it enforcesa stronger degree of coherency to reduce the number of states that must be considered. 为了增强可理解性，Raft 将共识分解成几个关键元素，例如 Leader 选举，日志复制，以及安全性等；同时，为了降低需要考虑的状态的数量，还强制实施了更强的一致性。

在前面的文章 HikariCP 源码分析 — ConcurrentBag 中，D瓜哥分析了一下 HikariCP 中一个非常重要的数据结构 ConcurrentBag。 今天，继续再介绍 HikariCP 中另一个很关键的数据结构： FastList。 FastList 本身的实现非常简单，要理解它的奥秘，就需要结合 Java 原生集合类的 ArrayList 来比较性地看。 构造函数 先来对比一下两者的构造函数。先来看看 FastList： FastList public final class FastList<T> implements List<T>, RandomAccess, Serializable { private static final long serialVersionUID = -4598088075242913858L; private final Class<?> clazz; private T[] elementData; private int size; /** * Construct a FastList with a default size of 32. * @param clazz the Class stored in the collection */ @SuppressWarnings("unchecked") public FastList(Class<?

前几天在看一个资料时，看到关于负载均衡算法的介绍。最近也在研究 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 两种模式。 这个算法可以把同一个 URI 的访问发送到同一台服务器上，以最大程度提高缓存命中率。 该算法支持两个可选参数 len 和 depth，后跟一个正整数。仅在需要基于URI的开头来平衡服务器时，这些选项可能会很有用。 len 参数指示算法仅应考虑URI开头的许多字符来计算哈希。请注意，将 len 设置为 1 几乎没有意义，因为大多数URI都以前导 / 开头。 depth 参数指示用于计算哈希的最大目录深度。请求中的每个斜杠都计为一个级别。如果同时指定了两个参数，则在达到任意一个参数时都将停止评估。 哈希算法也有很多中，而且不同算法各有优缺。回头单独开篇整理吧。 URL 参数(URL Parameter)法 HAProxy 中实现的一个负载均衡算法。根据 URL 参数的哈希值来选择服务器。

以前无意间搜资料了解到 HikariCP，一下子就被它的简洁代码和卓越性能吸引住了。以前也有翻过它的代码，但是不是很系统，最近再次翻阅，正好做些笔记，方便以后学习。 D瓜哥最近在学习 Java 并发知识。那就从 HikariCP 自定义的并发集合 ConcurrentBag 开始学习。 在 HikariCP 的 Wiki 中，有 Down the Rabbit Hole · ConcurrentBag 的章节来专门介绍 ConcurrentBag： ConcurrentBag 的灵感借鉴自 C# .NET 的 ConcurrentBag 类。但是实现却是完全不同的。这里的 ConcurrentBag 有如下特性： A lock-free design ThreadLocal caching Queue-stealing Direct hand-off optimizations 下面，通过代码来对此做个说明。 在 ConcurrentBag 类的定义中，声明了集合元素必须是 IConcurrentBagEntry 的子类。先来看看这个接口的定义： public interface IConcurrentBagEntry { int STATE_NOT_IN_USE = 0; int STATE_IN_USE = 1; int STATE_REMOVED = -1; int STATE_RESERVED = -2; boolean compareAndSet(int expectState, int newState); void setState(int newState); int getState(); } 接下来，看一下成员变量：

现在手机银行转账已经司空见惯。但是，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请求命令，执行事务的中断。 3PC只是解决了在异常情况下2PC的阻塞问题，但导致一次提交要传递6条消息，延时很大。 TCC TCC是Try、Commit、Cancel的缩写，TCC在保证强一致性的同时，最大限度提高系统的可伸缩性与可用性。 TCC（Try-Confirm-Cancel）又被称补偿事务，TCC 与 2PC 的思想很相似，事务处理流程也很相似，但 2PC 是应用于在 DB 层面，TCC 则可以理解为在应用层面的 2PC，是需要我们编写业务逻辑来实现。 TCC 的核心思想是："针对每个操作都要注册一个与其对应的确认（Try）和补偿（Cancel）"。 一个完整的业务包含一组子业务，Try操作完成所有的子业务检查，预留必要的业务资源，实现与其他事务的隔离；Confirm使用Try阶段预留的业务资源真正执行业务，而且Confirm操作满足幂等性，以遍支持重试；Cancel操作释放Try阶段预留的业务资源，同样也满足幂等性。“一次完整的交易由一系列微交易的Try 操作组成，如果所有的Try 操作都成功，最终由微交易框架来统一Confirm，否则统一Cancel，从而实现了类似经典两阶段提交协议（2PC）的强一致性。” 再来一个例子： 与2PC协议比较 ，TCC拥有以下特点： 位于业务服务层而非资源层 ，由业务层保证原子性 没有单独的准备(Prepare)阶段，降低了提交协议的成本 Try操作 兼备资源操作与准备能力 Try操作可以灵活选择业务资源的锁定粒度，而不是锁住整个资源，提高了并发度 缺点 应用侵入性强：TCC由于基于在业务层面，至使每个操作都需要有 try、confirm、cancel三个接口。 开发难度大：代码开发量很大，要保证数据一致性 confirm 和 cancel 接口还必须实现幂等性。 在 Seata 中，根据两阶段行为模式的不同，我们将分支事务划分为 Automatic (Branch) Transaction Mode 和 Manual (Branch) Transaction Mode.

本篇文章是 D瓜哥 读《算法导论》的读书笔记。记录下来是为了方便整理思路，以便啃下“动态规划”这块骨头。 目前侧重记录书中关于“动态规划原理”的介绍。接下来会把书中的例子结合 Java 代码演绎一遍。后续会根据D瓜哥的学习和理解，逐步完善。最终希望达到通过这一篇文章，就能学会、理解动态规划。 山高水远，道阻且长，愿一起努力！ — 2020年01月23日 动态规划（dynamic programming）与分治方法相似，都是通过组合子问题的解来求解原问题（在这里，“programming”指的是一种表格法，并非编写计算机程序）。 分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。 动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。 在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子问题。 动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了不必要的计算工作。 动态规划方法通常用来求解最优化问题（optimization problem）。 设计一个动态规划算法的步骤： 刻画一个最优解的结构特征。 递归地定义最优解的值。 计算最优解的值，通常采用自底向上的方法。 利用计算出的信息构造一个最优解。 算法原理 适合应用动态规划方法求解的最优化问题应该具备的两个要素：最优子结构和子问题重叠。 最优子结构 用动态规划方法求解最优化问题的第一步就是刻画最优解的结构。如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个好线索。 发掘最优子结构性质的通过模式 证明问题最优解的第一个组成部分是做出一个选择。做出这次选择会产生一个或多个待解的子问题。 对于一个给定问题，在其可能的第一步选择中，你假定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择。 给定可获得最优解的选择后，你确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间。 利用“剪切-粘贴”（cut-and-paste）技术证明：作为构造原问题最优解的组成部分，每个子问题的解就是它本身的最优解。证明这一点是利用反证法：假定子问题的解不是其自身的最优解，那么我们就可以从原问题的解中“剪切”掉这些非最优解，将最优解“粘贴”进去，从而得到原问题一个更优的解，这与最初的解是原问题最优解的前提假设锚段。 一个刻画子问题空间的好经验是：保持子问题空间尽可能简单，只在必要时才扩展它。 对于不同问题领域，最优子结构的不同体现在两个方面： 原问题的最优解中涉及多少个子问题，以及 在确定最优解使用哪些子问题时，我们需要考察多少种选择。 可以用子问题的总数和每个子问题需要考察多少种选择这两个因素的乘积来粗略分析动态规划算法的运行时间。 在动态规划方法中，通常自底向上地使用最优子结构。也就是说，首先求得子问题的最优解，然后求原问题的最优解。在求解原问题过程中，我们需要在涉及的子问题中做出选择，选出能得到原问题最优解的子问题。原问题最优解的代价通常就是子问题最优解的代价加上由此次选择直接产生的代价。 能够使用贪心算法的问题也必须具有最优子结构性质。贪心算法和动态规划最大的不同在于，它并不是首先寻找子问题的最优解，然后在其中进行选择，而是首先做出一次“贪心”选择—​在当时（局部）看来最优的选择—​然后求解选出的子问题，从而不必费心求解所有可能相关的子问题。 问题：使用贪心算法和动态规划的界线是什么？什么时候使用贪心？什么时候使用动态规划？ 重叠子问题 适合用动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须足够“小”，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。 如果递归算法反复求解相关的子问题，则就称为最优化问题具有重叠子问题（overlapping subproblems）性质。 与之相对的，适合用分治算法求解的问题通常在递归的每一步都生成全新的子问题。 动态规划算法通常这样利用重叠子问题性质：对每个子问题求解一次，将解存入一个表中，当再次需要这个子问题时直接查表，每次查表的代价为常量时间。 一个问题是否适合用动态规划求解同事依赖于子问题的无关性和重叠性。两个子问题如果不共享资源，它们就是独立的。而重叠是指两个子问题实际上是同一个子问题，只是作为不同问题的子问题出现而已。 将自顶向下的递归算法（无备忘录）与自底向上的动态规划算法进行比较，后者要高效得多，因为它利用了重叠子问题性质。 重构最优解 从实际考虑，通常将每个子问题所做的选择存在一个表中，这样就不必根据代价来重构这些信息。 备忘 可以保持自顶向下策略，同时达到与自底向上动态规划方法相似的效率。思路就是对自然但低效的递归算法加入备忘机制。维护一个表记录子问题的解，但仍然保持递归算法的控制流程。 带备忘的递归算法为每个子问题维护一个表项来保存它的解。每个表项的初值设为一个特殊值，表示尚未填入子问题的解。当递归调用过程中第一次额遇到子问题时，计算其解，并存入对应表项。随后每次遇到同一个问题，只是简单地查表，返回其解。 一个更通用的备忘方法是使用散列技术，以子问题参数为关键字。 通常情况下，如果每个子问题都必须至少求解一次，自底向上动态规划算法会比自顶向下备忘算法快，因为自底向上算法没有递归调用的开销，表的维护开销也更小。而且，对于某些问题，可以利用表的访问模式来进一步降低时空代价。相反，如果子问题空间中的某些子问题完全不必求解，备忘方法就会体现出优势了，因为它只会求解那些绝对必要的子问题。 参考资料 算法导论（原书第3版） Dynamic Programming vs Divide-and-Conquer - ITNEXT How to Solve Any Dynamic Programming Problem - Pramp Blog | Coding Interview & Job Search Resources for Developers

曾经写给学弟学妹的一封信。我觉得还行，发出来，希望对刚学计算机专业的朋友有所帮助。当然，如果哪位朋友有更好的想法，也请留言，大家讨论讨论。原文如下： 致师弟师妹的一封信 各位朋友： 大家好！ 从本周开始，我必须专心为我的前程奋斗了。很可惜不能和大家一起学习了。这封信就算是我和大家的一个告别吧。 首先，感谢史老师给我提供这个和大家一起学习和交流的机会，让我和大家一起度过了一段特殊而愉快的时光。 其次，我应该感谢大家。由于本人水平有限，也许我没能让大家从我这里学到太多知识，但是大家却让我学会了很多东西，锻炼了我很多方面的能力。单凭这一点，我就应该感谢大家。同时，很多人把我当朋友，更使我感激不尽。 再次，在这短暂而又宝贵的大学时光里，大家走的路应该和我的基本一样。我以一个过来人的身份，和大家分享一下我的学习经验吧，希望可以让大家少走甚至不走弯路。 先说一点我们所学科目的情况吧。 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就是我。(*__*) 嘻嘻…… 这句话是我从他的一句话里改编过来的！）） 其实，学计算机学科非常有趣！Linux里面，几行指令，我们就可以顺利的让鼠标在两个操作系统自由转换！Java里面几行，几十行代码就有一个漂亮的窗口！C#里面随便一个拖拽，也是一个不错的窗口！“只要一部计算机，就可以创造出无限的世界。”（出自蔡学镛《写程序，好好玩》，《Java夜未眠》里面的一篇，本书是本很搞笑的编程感触散文集，推荐看看。）加油吧！相信你行！ 二、坚持不懈。任何事情都不是可以一蹴而就的，都需要我们坚持！再送给大家一句话：失败只有一种，那就是半途而废！ 三、舍我其谁的豪迈和霸气。“Horse’s，Gosling能创造出来Java，我就不信我学不会！一个破Java，我还不放到眼里呢！！”，“别人能创造出来，我就不相信我学不会？！”不过，也要给大家提醒一句：“战略上，藐视敌人；战术上，重视敌人”！一定要下功夫学习才行！ 四、信心。一定要相信自己的能力！你是独一无二，无可替代的！信心能让你从一个更高的角度看待你的学习！能给你一种驾驭知识的成就感！这种感觉能让你从学习中找到乐趣！ 五、行动！上面的大道理，我们大家都懂！但是，谁实际做到呢？伟大与平凡的区别也许就在于这一点吧。我以我自己的高中、大学对比来看，行动与否结果绝对是不一样的！只想不做，最多是个空想家！所以，大家一定要“坚持不懈的行动”！ 最后，送给大家一句话：你充满了潜能，但你的努力还远远不够！再次怀念我们共同的学习时光！ 祝大家学有所成！ D瓜哥