LeeYzero的博客

上一篇 Lab2A: 选主 中介绍了Raft选主的实现，本篇介绍Raft日志复制的原理和实现。实验二共包含四个子实验：

• Lab2A: 选主
• Lab2B: 日志复制
• Lab2C: 持久化
• Lab2D: 日志压缩

本文是第二个子实验，需要实现Raft日志复制。由于Raft的强领导人特性，命令都是通过Leader顺序追回到日志中，然后通过Leader复制到各Follower中，由于Raft的日志安全特性，使得集群节点中的日志最终达到一致。在开始实验前，先阅读以下材料：

• 阅读论文：In Search of an Understandable Consensus Algorithm，以下简称论文。
• 阅读实验指导：6.824 Lab 2: Raft Part2B
• 阅读Students’ Guide to Raft，本文中介绍了些论文中没有给出的实现细节。

Raft日志复制是Raft协议最核心的部分，也是最难的部分。论文中将日志复制和安全性是分开讨论的，实现的时候我们需要将这两部分结合起来。另外论文中对一些实现细节是空白的，如日志冲突的优化，这要求我们要实现的时候要考虑各种边界问题。

基本原理

选主成功后，Leader就开始接收客户端的请求。每个请求是能够被复制状态机执行的命令（command）。Leader首先将命令作为一个日志记录（entry）追回到日志中，然后并行地向集群中的其它节点发起AppendEntries RPC请求。当日志记录被安全复制到其它节点后，Leader将该记录应用到状态机中，并将状态机执行的结果返回给客户端。如果Follower崩溃或网络丢包，Leader会不断重试向Follower发送AppendEntries RPC，走到Follower最终全部保存了Leader的日志记录。

以上就是Raft日志复制的全部流程，它涉及到很多细节，这里我主要说一下日志记录和安全性。

日志可以理解成是一个包含日志记录(entry)的列表，每个日志记录包含了三个信息：

• Term：Leader生成日志记录时任期号
• Index：日志记录在日志中的索引号
• Command：可以被状态机执行的命令

Term和Index主要用于日志一致冲突检测（下面会介绍）；Command是上层状态机的一个概念，Raft其实并不理解，只是Raft需要解决Command的一致性问题，所以Raft把Command当成一个上下文参数存储到一个日志记录中，当Raft认为一个日志记录在集群中已经达成一致后，Raft只是将这个Command再较交给状态机去执行。这个地方说的达成一致，就是指日志已经被安全复制。

在讨论什么叫安全复制之前，先直接抛出Raft给出的安全性保证，这些保证在论文中的详细论述和证明，在此不一一展开

上一篇 Lab2: 概述 中简要介绍了Raft，本篇介绍Raft选主的原理和实现。实验二共包含四个子实验：

• Lab2A: 选主
• Lab2B: 日志复制
• Lab2C: 持久化
• Lab2D: 日志压缩

本文是第一个子实验，需要实现Raft选主。Raft具有强领导人特性，也就是说Raft需要先选举出领导人后才能进行后续操作。在开始实验前，先阅读以下材料：

• 阅读论文：In Search of an Understandable Consensus Algorithm，以下简称论文。
• 阅读实验指导：6.824 Lab 2: Raft Part2A
• 参考Raft可视化选举过程，可以更直观地理解Raft选主。

基本原理

Raft有三种角色：领导人（leader）、候选人（candidate）和追随者（follower），每个Raft节点都可能是这三种状态中的一种，但大部情况下，集群中只有leader和follower两种角色的节点。三种角色的转换关系如下图：

节点启动时设置为follower状态，处于follower状态的节点如果在选举超时时间内没有收到leader的心跳消息将转换为candidate状态，candidate状态的结点会发起投票，首先会给自己投票，然后全网广播，让其它节点给自己投票，如果candidate节点收到了半数以上（majority）的投票，节点转换成leader状态。成为leader状态的节点会定时向全网发送心跳，以表示leader健在，让其它节点都安份点，别挑战leader的权威。集群中的candidate节点在收到leader的心跳后，转换为follower状态。

以上的节点的状态转移可以形象理解为，每个follower都有一颗不安分的心，如果在一段时间内（选举超时时间）没有收到leader的心跳消息，就跳出来参加竞选，让群集中的其它节点都选举它当leader，如果超时半数的节点都同意，那它就成为leader了。同样，为了不让其它节点再把自己推翻，它要不断地向群集广播心跳以维护自己的leader地位。

每次选举都有一个任期（Term），标识惟一的一次选举。一个candidate发起选举时，会出现三种情况：

1、赢得选举，成为leader。
2、集群中其它节点已经赢得选举，转换为follower。
3、投票发生分裂，均没有赢得选举，等待选举超时，重新选举。

前两种情况都比较容易理解，第3种情况发生在集群中有多个候选者时，候选者获得的选票均没有过半，相当于这个任期（Term）没有选举出领导人。任期相当于一个递增的时钟向量（Clock Vector），如果放在时间维度，每个任期包含选举周期和任期内的操作，其中任期内的操作是可选的，这种情况相当于这个任期没有选举出领导人，下图可以直观看出时间维度任期的变化过程：

上图中，正常情况下，每个任期（Term）都包含一个选举周期和任期内的普通操作，但任期3（Term=3）发生投票分裂，没有选举出领导人，任期4发生重新选举，选举出新领导人后，进行后续操作。

6.824 是MIT推出的一个分布式系统课程，讲师是大名鼎鼎的Robert Tappan Morris。Lab2 是课程中的第二个实验，实验要求需要用Go语言实现Raft。Raft是为可理解而设计的共识算法（consensus algorithm），它在性能和容错性上等价于Paxos，但结构却完全不一样。Raft通过减少状态空间和将问题分解为几个独立的子问题，使得Raft更容易理解，也更利于工程实现。

在开始实验前，需要先阅读以下材料：

• 6.824 Schedule: Spring 2022
• In Search of an Understandable Consensus Algorithm
• Lab Guidance
• Students’ Guide to Raft

以上材料是必读的，在YouTube上有一个配套的教学视频，英文比较吃力的同学可以在B站看翻译后的视频。

共识算法是分布式系统最核心的部分，也是非常难的部分，Paxos的主要问题是难以理解，而且作者Leslie Lamport在论文中并没有给出具体的实现细节，正如Chubby的实现者所述：

There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. . . . the final system will be based on an unproven protocol.

大概意思是说，Paxos算法的描述和现实世界实际需求存在着显著差距，最终的系统都是基于未经证明的协议。

Architectural Styles and the Design of Network-based Software Architectures（架构风格与基于网络应用软件的架构设计）是 Roy Fielding 在2000年发表的博士论文。这篇论文一经发表，就引起了关注，并且对互联网开发产生了深远的影响。论文中首次提出的REST架构风格基本上成为目前Web架构的指导规范，如果一个Web架构符合REST架构风格，我们称为RESTful架构。

大部分人只看到这篇论文提出的REST架构风格，却忽略了REST架构风格提出的背景及方法论。这篇论文前半部分给出了一种通用的架构设计评估方法，我认为是更值得学习的地方。本来想用一文章来介绍这篇论文，发现篇幅有点收不住，于是拆分成两篇：

• Part1：主要介绍论文背景、架构风格的定义、评估应用软件架构设计的方法以及基于网络应用的架构属性与架构风格。
• Part2：主要介绍Web架构面临的问题、REST架构风格以及REST在Web架构中的应用。

之前搭建了一个 codeserver 的开发环境，但还遗留了配置HTTPS访问域名的问题。本周正好有空搞下，本来打算花钱买一个HTTPS证书，发现 Let’s Encrypt 提供了免费的HTTPS证书，而且还提供了配套的工具让网站开启HTTPS变得非常简单，本文记录下安装步骤。

在介绍安装步骤之前先简单介绍一下 HTTPS 的工作原理，不感兴趣的同学可以直接跳过。

简单来说，HTTPS 就是安全的HTTP（S表示Secure的意思），我们知道HTTP报文是采用明文传输的，报文容易被窃听或篡改。HTTPS 是在传输层和应用层中加一个安全层（SSL），负责对报文进行加密和解密。

传统的对称加密（加密解密使用相同密钥）要在传输两端共享密钥，涉及到密钥安全问题。而非对称加密（公钥加密，私钥解密）可以完美解决密钥交换问题。非对称加密的公钥是公开的，任何人都可以使用这个公钥进行加密。

但别人又怎么相信这个公钥是你发布的呢，这又是一个信任问题，解决办法是引入一个可信息的第三方机构。通常的做法是将这个公钥放到一个证书（Certificate）中，然后由这个可信任的第三方机构来统一认证和颁发。这个可信任的第三方机构就是证书颁发机构（CA，Certificate Authority）。

拿到证书后，怎么验证这个证书是不是第三方机构颁发的呢？（哈哈，是不是感觉问题好多呀），答案是使用数字签名技术，简单来说就是为证书的内容做一个签名，并附到证书的末尾，这个签名具有惟一性和不可伪造性。

客户端（通常是浏览器）收到证书时会对证书合法性进行检查。如果这个机构是可信任的权威机构颁发的，浏览器可能已经知道其公开密钥了（浏览器会预先安装很多签名颁发机构的证书），这样，就可以通过数字签名来验证证书的完整性了。

所以，客户端和服务端进行HTTPS通信时，除了进行正常的TCP三次握手外，还需要进行SSL握手，这个过程主要是从服务端拿到证书、验证证书的合法性，然后交换加密密钥。后续的通信就可以使用这个加密密钥对报文加密和解密了。

突然发现写多了（化繁为简能力还有提高），以上就是HTTPS的大致原理，当然HTTPS的细节交互更加复杂，以上概述只是让大家对HTTPS有个宏观上的认识。有了这个背景，我们就知道启用HTTPS主要需要以下两个步骤：

• 从CA机构获取一个受信任的HTTPS证书。
• 将证书部署到服务端。

Let’s Encrypt 就是一个可信息的证书颁发机构，它颁发的免费数字证书浏览器是信任的，而且它还提供便捷的安装和续约工具，下面就进入安装环节吧。

写在前面

跳跃表是一种可以替代平衡树的数据结构。跳跃表采用概率上的平衡而不是强制要求节点的平衡，使得其在插入和删除时更容易实现，而且具有更好的效率。由于跳跃表具有良好的性能和算法实现的简单性，被广泛应用于工程实践中，如redis、leveldb等。

本文是对William Pugh的论文Skip Lists: A Probabilistic Alternative to Balanced Trees的解读，主要介绍算法核心思想和算法实现，对于算法的时间和空间复杂度分析并不是本文的重点，这部分内容在论文中有详细介绍。

写在前面

MySQL是一款开源的关系型数据库，广泛应用于Web后端的数据存储。索引是MySQL非常重要技术组成部分，深入理解MySQL的索引原理，有助于我们建立高性能的索引以及对索引进行调优。

MySQL支持多种索引类型，如B-Tree索引、哈希索引、全文索引等。索引是在存储引擎中实现的，在实际环境中，应用比较多的是InnoDB存储引擎和MyISAM存储引擎，这两个存储引擎底层都是使用的B-Tree索引。所以，为了不引起歧义，本文讨论的MySQL索引，没有特殊说明，都是指的B-Tree索引。

背景

最近由于组织架构调整，团队引入不少新成员。这些成员来自不同的团队和背景，每个人的日志打印风格难免也有所差异，十分有必要制定一个统一的日志打印规范。

规范日志打印主要有以下作用：

• 让系统运行状态更透明，提高线上故障排查效率。
• 减少代码风格差异，利于代码阅读和维护。
• 统一日志格式，利于外围工具（日志监控报警工具等）处理。

团队成员在研发过程中应该遵守该规范，文档内容可能会与你的喜好冲突，请尽量用包容的心态接受。如果有不合理之处，请先在组内提出建议，组内一致表决通过后修改规范。

最近换了一台mac，配置了一下终端（terminal）环境，在此记录一下，以便后续查阅，同时给分享给网友作为参考。本文不会细无具细，只会列举出主要步骤和相关配置参考资料。主要包括以下四个部分：

• 安装 iTerm2
• 安装 oh-my-zsh
• 配置 powerlevel10k
• 配置插件

终端效果:

最近读了《如何阅读一本书》，很遗憾自己没有早点读到这本书，同时也庆幸自己现在读到这本书。阅读的目标有两种，一种是为了获取资讯，另一种是为了增进理解。《如何阅读一本书》便是一本教你如何通常阅读以增进理解的实用书籍。

打开你的手机，看看你一周的花在各大手机APP上的时间。抖音、快手、知乎、B站、微信公众号…，这些time killer是不是占用了大量的时间？看起来你每天（被）输入了大量信息，但这些信息是否真能增进我们对自己世界的了解呢。很遗憾，并没有。发生这一现象的原因主要有两点：

• 这些媒体经过精心的设计，对资讯进行精美的包装，让受众根本用不着自己做结论。他们直接将包装后的观点装进自己的脑海中，缺乏对事物的思考。
• 这些媒体提供的绝大部分是资讯类信息，而且比较零碎，缺乏逻辑性。太多的资讯如同太少的资讯一样，都是对理解力的阻碍。现代媒体正以压倒性的泛滥资讯阻碍了我们的理解力。

诚然，互联网上的确有很多非常不错的知识。但书籍（也包括电子书）仍然是获取知识最重要的信息来源。如何通过阅读以增进理解力本身是一种艺术，《如何阅读一本书》提供了很多值得参考的规则，值得花时间投入学习。但诚如作者所说，对于一本实用性的书，当你读完并赞同作为的观点后，作者的任务就完成了，但作为读者，你的任务才刚刚开始。作者在书中所建议的方法对你是不是有效，需要你在实践中寻找答案。