mit6824-06-Raft学习记录01

devtools/2024/11/7 8:58:20/

文章目录

  • 必要知识
    • 单点故障
    • 脑裂
    • 多数原则

近日开始学习分布式共识算法Raft,慢慢记录一些自己能看懂的东西。

优质博客:

  1. Raft原理详解

必要知识

单点故障

单点故障(single point of failure):服务器中某台机器出现故障。
前面介绍过的复制系统,都存在单点故障问题(single point of failure)。

  1. mapreduce中的cordinator
  2. GFS的master
  3. VM-FT的test-and-set存储服务器storage

而上诉的方案中,采用单机管理而不是采用多实例/多机器的原因,是为了避免脑裂(split-brain) 问题。

​ 不过大多数情况下,单点故障是可以接受的,因为单机故障率显著比多机出现一台故障的概率低,并且重启单机以恢复工作的成本也相对较低,只需要容忍一小段时间的重启恢复工作。

脑裂

以VM-FT系统为例了解学习脑裂:
以VM-FT的test-and-set存储服务器storage举例。假设我们复制storage服务器,使其有两个实例机器S1、S2。(即打破单机管理的场景,看看简单的多机管理下有什么问题)

​此时C1想要争取称为Primary,于是向S1和S2都发起test-and-set请求。假设因为某种原因,S2没有响应,S1响应,成功将0改成1,此时C1可能直接认为自己成为Primary。

​这里S2没有响应可以先简单分析两种可能:

  1. S2失败/宕机了,对所有请求方都无法提供服务:如果是这种情况,那么C1成为Primary不会有任何问题,S2就如同从来不曾存在,任何其他C同样只能访问到S1,他们都会知道自己无法成为Primary,并且整个系统只会存在C1作为Primary。

  2. S2和C1之间产生了网络分区(network partition),仅C1无法访问到S2:这时候如果存在C2也向S1和S2发出请求,此时S1虽然将0改成1会失败,但是S2会成功。如果我们的协议不够严谨,这里C2会认为自己成为了Primary,导致整个系统存在两个Primary。这也就是严重的脑裂问题。

​ 产生这种问题的原因在于,对于请求方,无法简单地判断上诉两种情况,因为对他们来说两种情况的表现都是一样的。

为避免出现脑裂,我们需要先解决网络分区问题,下面的多数原则就很好解决了网络分区问题。

多数原则

诸如Raft一类的协议用于解决单点故障问题,同时也用于解决网络分区问题。这类解决方案的基本思想即:大多数原则(majority rule),简单理解就是少数服从多数

​这里的majority指的是整个系统中无论机器的状态如何,只要获取到大于一半的赞成,则认为获取到majority。比如系统中有5台机器,2台宕机了,5台的一半为2.5,但2.5不为有效值,即获取3台机器赞成,认为获取到majority;如果5台中宕机3台,那么没有人能获取到至少3台的赞成,即无法得到majority。

​同样以VM-FT的test-and-set存储服务器storage举例,这次storage不是复制出2个实例,而是总共复制出3个实例,S1、S2、S3。

​此时C1同时向S1、S2、S3请求test-and-set,其中S1和S2成功将0改成1,S3因为其他问题没有响应,但是我们不关系为什么。这里按照majority rule,只要3个S中有2个给出成功响应,我们就认为C1能够成为Primary。此时就算同时有C2向S1、S2、S3发起请求,就算S3成功了,C2根据majorty rule,3台只成功1台,不能成为Primary。

​为什么根据majority rule,这里就不会出现脑裂,因为能确保多个C之间的请求有重叠部分(overlap),这样根据majority rule,多个C最后也能达成一致,因为只有1个C有可能成为多数的一方,其他C只能成为少数的一方

​在之后准备介绍的Raft,和这里描述的工作流程基本一致。

  • 在majority rule下,尽管发生网络分区,只会一个拥有多数的分区,不会有其他分区具有多数,只有拥有多数的分区能继续工作(比如这里3台被拆成1台、2台的分区,只有和后者成功通信的能继续工作)。
    而如果极端情况下所有分区都不占多数( 比如这里3台被拆成1台、1台、1台的分区),那么整个系统都不能运行。

  • ​上诉3台的场景,只能容忍1台宕机,如果宕机2台,那么任何人都无法达到majorty的情况。这里通过2f+1拓展可容忍宕机的机器数,f表示可容忍宕机的机器数量。2f+1,即使宕机了f台,剩下的f+1>f,仍然可以组成majority完成服务。

​例如,当f=2时,表示系统内最多可容忍2台机器处于宕机状态,那么至少需要部署5台服务器(2x2+1=5)。

问题:这里大多数是否包括参与者服务器本身,假设是raft,服务器会考虑自身吗?
回答:是的,通常我们看到的raft,candidate会直接vote自己。而leader处理工作时,也会vote记录自己。


http://www.ppmy.cn/devtools/131969.html

相关文章

基于Spring Boot 框架的试卷自动生成系统的设计与实现

项目描述 临近学期结束,还是毕业设计,你还在做java程序网络编程,期末作业,老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。你想解决的问题,今天给大家介绍…

Bert完形填空

转载自:| 03_language_model/03_Bert完形填空.ipynb | 基于transformers使用Bert模型做完形填空 |Open In Colab | 完形填空 利用语言模型,可以完成完形填空(fill mask),预测缺失的单词。 当前,效果最好的…

TS(类 接口 泛型)

文章目录 类复习相关知识属性修饰符public 修饰符属性的简写形式 protected修饰符private修饰符readonly修饰符 抽象类 接口(interface)定义类结构定义对象结构定义函数结构接口之间的继承接口自动合并 (可重复定义)一些相似的概念…

【docker】6. 镜像仓库/镜像概念

Docker Registry(镜像仓库) 什么是 Docker Registry 镜像仓库 (Docker Registry) 负责存储、管理和分发镜像,并且提供了登录认证能力,建立了仓库的索引。 镜像仓库管理多个 Repository, Repository 通过命名来区分。…

Django命令行操作用户(manage.py工具)

一、创建超级用户 python manage.py createsuperuser 之后会提示输入用户名、邮箱、密码。根据提示输入即可 二、创建普通用户 from django.contrib.auth.models import UserUser.objects.create_user(zhangsan,zhangsan163.com,123456) 使用 User.objects.create_user 方…

二叉树从右侧所能看到的节点值 (DFS)

给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例 1: 输入: [1,2,3,null,5,null,4] 输出: [1,3,4]示例 2: 输入: [1,null,3] 输出: [1,3]示例 3: 输入: [] 输出: []提示: 二…

软考:案例题分析1101

22年第一题:架构设计与评估 分析文字,识别需求和质量属性?这里需要记忆质量属性有那些,区分需求和质量属性,能区分出质量属性之间的区别。 我的回答: 差距分析: 根据题目中功能的特点&#xff…

【LeetCode】【算法】394. 字符串解码

LeetCode 394. 字符串解码 题目描述 给定一个经过编码的字符串,返回它解码后的字符串。 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的;输入字…