云计算复习提纲

提纲说明

本提纲理论上仅适用于18级软院，请校对当年李传艺老师上课强调的考点和非考点之后进行阅读。

云计算起源与概述

追求算力的几种方法

1. 把一台计算机的计算性能提升的足够强大

   1. 集中式计算（将所有计算资源集中在一个物理系统之内）
   2. 并行计算（能有效提高计算效率，所有处理器紧耦合于中心共享）

2. 人多力量大，机多计算强

   1. 分布式计算（由众多自治计算机组成，各自拥有私有内存，通过计算机网络通信）

传统分布式计算系统

1. 计算机集群

   将多个可信、静态的独立节点连接起来协作完成计算

   计算机集群是计算抽象。

2. P2P网络

   每个节点既是客户端也是服务器，提供部分系统资源

   P2P系统是存储抽象，各个机器可以自由地加入或者是退出。

3. 计算网格

   将多个异构计算机（采用了不同的操作系统，但是能够进行有效的通信）动态、紧耦合地整合在一起完成计算任务

   计算网格已经开始接近云计算

云计算

云计算是2006.3提出的雏形（compute cloud）到之后在2006.8.9正式确定（Cloud Computing）

基本想法

云计算是一种完美的分布式计算结局方案——是对网格的优化。

定义

• 云计算式一种基于互联网的计算方式，通过这种方式，共享的软硬件资源和信息可以按需求提供给计算机各种终端和其他设备——维基百科
• 云计算是一种模型，可以实现随时随地、边界的、按需的从可配置计算资源共享池中获取所需要的资源（例如，网络、服务器、存储、应用程序及服务），资源可以快速攻击和释放，是管理的工作量和服务提供者的接入降低至最少。——NIST（美国国家标准与技术研究院）
• 云计算是一种计算方式，能通过Internet技术将可扩展的和弹性的IT能力作为服务交付给外部用户。——Gartner
• （长）云计算是一种商业计算模型，他将计算任务分布在大量计算构成的资源池上，使各种应用系统能够根据需要获取计算力、存储空间和信息服务——刘鹏
• （短）云计算是通过网络按需提供可动态伸缩的廉价计算服务——刘鹏

云计算VS网格计算

都能提升计算能力完成数据处理，构建虚拟资源池且动态可伸缩

网格计算

• 强调聚合分布的资源
• 强调虚拟组织，立足特定任务
• 利用中间件来屏蔽异构系统
• 面向科研，商业模式不清晰

云计算

• 强调使用专有的资源
• 不强调虚拟组织，重视通用性
• 不强调异构型
• 针对企业应用，商业模式清晰

大数据时代

云计算和人工智能是处理大数据的能力与方法，物联网和互联网+是大数据的来源于去向

大数据5V

1. Volume
2. Variety
3. Velocity
4. Value
5. Veracity

云计算的特点

• 超大规模
• 虚拟化
• 按需服务
• 通用
• 高可伸缩性
• 极其廉价
• 高可靠

云服务模型

IaaS

通过虚拟机方式对外提供计算和存储能力。

机器享有公网IP，多个虚拟机之间通过网络进行通信。

基本上可以说是租用独立的云计算机，由用户解决协同问题。用户交互接口向应用以web Service的方式提供访问接口

优势：

• 允许用户动态申请和释放资源
• 按使用量计费
• 更高的资源使用效率（节能）

PaaS

只是提供用户一个应用程序的运行环境，但是用户不需要考虑结点间的配合问题，但是这要求用户按照指定的编程环境和编程模型构建应用。

SaaS

针对性非常强，只提供某些专门用途的服务

云计算的实现机制

云计算体系结构分为：

1. SOA构建层（封装云计算能力成标准的web service服务，并纳入到SOA体系）
2. 管理中间件层（云计算的资源管理，并对众多应用任务进行调度）
3. 资源池层（将大量相同类型的资源构成同构或者接近同构的资源池）
4. 物理资源层（硬件以及软件的支持）

SOA

面向服务的体系结构（Service-oriented Architecture）

将服务作为分布式对象

管理中间件层

• 资源管理
• 用户管理
• 任务管理
• 安全管理

云的部署模型

公有云

可以被所有用户访问的云环境

社区云

只能由社区用户访问

私有云

由一家组织单独拥有

混合云

由两种或者更多的模型构成的云环境

云计算的优势

• 经济性
• 可扩展和可伸缩性
• 虚拟化
• 高可靠
• 管理简单
• 安全

云计算的技术难点

• 数据中心安全控制
• 构建高度同构化的虚拟资源
• 高可用性的实现
• 容错的实现
• 节能
• 云安全与隐私安全

云计算的风险

• 安全漏洞
• 降低了运营管理控制
• 可移植性有限
• 法律法规问题

虚拟化技术

虚拟化技术的核心思想是利用软件或固件管理程序构成虚拟化层，把物理资源映射为虚拟资源 。在虚拟资源上可以安装和部署多个虚拟机 ，实现多用户共享物理资源 ，技术首先由IBM提出

虚拟化实现

添加一个成为虚拟化层的软件，管理客户操作系统。

虚拟化层软件用于虚拟化基础设施

虚拟化层次

虚拟硬件环境、处理器、内存和I/O设备

不同层次的虚拟化

硬件级虚拟化

1. 为程序提供与原始硬件机器基本一致的环境
2. 运行在该虚拟硬件环境中的程序性能损失应该较低
3. 系统资源应该处于VMM的完全控制中

可以分为全虚拟化与半虚拟化

初始化一个硬件级虚拟机非常慢

操作系统级虚拟化

看作是寄居虚拟化的一种在操作系统中插入一个虚拟化层

优点：

1. 最小的启动或停止开销，资源需求低，可扩展性强
2. 需要时，可同步虚拟机与宿主操作系统环境状态的变化
3. 在同一个主操作系统上运行的多个操作系统级虚拟机共享同一个操作系统内核
4. 在虚拟化层中允许虚拟机中进程访问尽可能多的主机资源

缺点：

1. 同一个容器中的操作系统级虚拟机必须使用相同的客户操作系统
2. 资源隔离较差

虚拟机 VS Docker容器

• 客户操作系统 vs. 独立/共享二进制文件和库
• 20s启动 vs. 500ms启动
• 较高应用灵活性 vs. 低成本高性能
• 适合没有编排的多个应用使用 vs. 适用于编排条件下多个副本相同的应用扩展

发展趋势

多种虚拟化共同发展，容器成为云计算的主流

数据中心虚拟化

现阶段的数据中心规模不断增大、成本逐渐上升、管理日趋复杂所以使用虚拟化实现资源的动态分配和调度。

虚拟化类型

主要分为三种类型：服务器虚拟化、存储虚拟化、网络虚拟化

服务器虚拟化

这种虚拟化就是硬件级的虚拟化，包括了CPU虚拟化、内存虚拟化、IO设备虚拟化

存储虚拟化

概念：存储虚拟化将系统中分散的存储资源整合起来。

技术：在虚拟层通过使用数据镜像、数据校验和多路径等技术，利用负载均衡、数据迁移、数据块重组等技术整合和重组底层物理资源。

分为基于主机的存储虚拟化、基于存储设备的存储虚拟化、基于网络的存储虚拟化

网络虚拟化（不考）

传统数据中心的网络传输效率较低，因为使用的数据接口的格式不统一

云计算使用之后使用了统一的交换网络

引入虚拟化之后数据中心的网络虚拟化分为核心层、接入层和虚拟机网络虚拟化三个层面

桌面虚拟化（不考）

第一代桌面虚拟技术

实现了在同一个独立的计算机硬件平台上，同时安装多个操作系统，并同时运行这些操作系统

第二代桌面虚拟化技术

进一步将桌面系统的运行环境与安装环境、应用与桌面配置文件进行了拆分，从而大大降低了管理复杂度与成本，提高了管理效率。

虚拟机迁移

从源到目的地的方式分为：

• 物理机到虚拟机 P2V
• 虚拟机到虚拟机 V2V（云计算中关注的重点：实时迁移）
• 虚拟机到物理机 V2P

动态实时迁移：保持虚拟机运行的同时，将其从一个计算机迁移到另一个计算机，并在目的地计算机恢复运行。

内存迁移

这是最困难的地方

分为三个阶段，Push阶段，Stop-and-Copy阶段、Pull阶段，有三种迁移方法：

网络资源迁移

协议状态等迁移

存储设备迁移

目前使用NAS作为存储设备进行数据共享，所以不太需要存储设备的迁移。

虚拟机隔离技术

虚拟机之间在没有授权许可的情况下，互相之间不可通信、不可联系的一种技术。

现有的虚拟机隔离机制有：

• 网络隔离
• 构建虚拟安全文件防护网
• 基于访问控制的逻辑隔离机制
• 硬件提供的内存保护机制
• 进程地址空间的保护机制，IP地址隔离

网络隔离

防止外部的网络攻击到达。系统控制通信数据

云数据中心

云数据中心的特征

• 高设备利用率（通过虚拟化技术对硬件进行整合）
• 绿色节能（服务器较为节能，供电技术，软件算法）
• 高可用性（各个部分冗余，灾容设计）
• 自动化管理（无人值守，远程管理）

云数据中心网络部署

• 构建方便简单
• 不便于拓展升级
• 任意一个核心交换机故障导致上千台服务器故障
• 低成本、高可扩展性、低配置开销、节能
• 有多种可使用的网络结构

改进树（FatTree，VL2）

FatTree使用两级路由表，允许两级前缀查询，消除了树形结构对上层链路的吞吐量的要求限制，内部通信能够提供多条并行链路。

VL2是一套可扩展且灵活的网络架构，微软数据中心采用。扁平寻址，负载均衡，使用CLOS拓扑结构建立扁平的第二层网络。

优势： VL2 是目前最易用于对现有数据中心网络改造的结构。
缺点： VL2 依赖于中心化的基础设施来实现 2 层语义和资源整合，面临单点失效和扩展性问题。

递归层次结构

解决可扩展性的较好选择，每个高层的网络拓扑由多个低层的递归单元按照递归规律互相连接构成，同时也是更高层次网络的一个递归单元。

服务器使用两个网卡端口：主用端口连接低层网络，备用端口连接高层网络。

光交换网络

在业务增长的时候数据中心内部和服务器间的数据流量增加，传统网络设备无法处理，使用光纤设备。

OSA基于光交换的数据中心网络体系结构

• 光交换矩阵（OSM）
• 波长选择交换机（WSS）

无线数据中心网络

静态链路和有线接口在突发流量和高负载情况下会降低整个数据中心的网络性能，所以使用无线网络的广播机制克服这个问题。

软件定义网络（SDN）

将网络的控制平面和数据转发平面分离

通过软件更新实现网络升级，无需针对硬件进行配置。

openflow是第一个针对SDN实现的标准接口，以良好的灵活性、规范性被堪称SDN通信协议的标准。

绿色节能技术

数据中心的耗能越来越大。

节能的方面：

• 配电系统（高压直流配电、市区直供配电）
• 空调系统（高温回风空调，低能耗加湿，自然冷空调系统）
• 集装箱数据中心（使用固定模块的数据中心设备）
• 管理系统
• 新能源（利用新能源供电）

自动化管理

使得在规模较大的情况下，实现较少人员对数据中心的高度智能和管理

资源的自动化调度和对业务的灵活响应

自动化管理的五个特征：

• 全面的可视性
• 自动的控制执行
• 多层次的无缝集成
• 综合与实时报告
• 全生命周期支持

自动化的实现的三个阶段：

• IT服务操作
• IT服务管理
• 数据中心自动化

容灾备份

容灾备份是通过在异地建立和维护一个备份存储系统，利用地理上的分离来保证系统和数据对灾难性事件的抵御能力。

抵抗程度分级：

• 数据级容灾：只保证数据的完整性可靠性和安全性，提供的服务会中断
• 应用级容灾：能保证不间断提供服务

容灾的核心是复制数据，使用的技术有快照技术，远程镜像技术，数据库复制技术和基于IP的SAN的远程数据容灾备份技术等。

Hadoop2.0（可能不考）

分布式存储

分布式文件系统（Distributed File System，DFS）

将多台机器硬盘以某种方式连接到一起，采用客户-服务器模式构建分布式存储集群，让master管理slave，在这种DFS中对内呈现出客户-服务器模式，对外呈现出统一存储空间，同一文件接口。

分布式计算

Google提出移动计算比移动数据更划算

采用客户-服务器模式构建分布式计算集群

在只使用分布式存储的情况下会出现每个计算机进行本地数据的计算，然后进行合并，但是如果使用了Hadoop的MapReduce框架，情况如下：

可靠性问题：冗余存储

不是通过单纯的增加额外的设备备份来达到目的，通过每台机器上的数据都能在集群中的另一台机器上找到，计算也是一样的，Master会知道每一份数据的存储位置，要求所有的存有带计算数据的机器都进行计算，去最快的运算结果。

冗余存储不仅提高了分布式存储的可靠性，也提高了分布式计算的可靠性

Hadoop简介

2006年完成大部分开发，成为Hadoop。Hadoop1.0和Hadoop2.0 的架构差异较大

• Hadoop1.0

  • Hadoop Common：支持其他两个模块的公用组件
  • Hadoop DFS：分布式文件系统
  • Hadoop MapReduce：分布式计算框架

• Hadoop2.0（新增）

  • 分布式存储HDFS
  • 分布式操作系统Yarn
  • 通过调用程序库，可使用简单的编程模型处理分布在不同机器上的大规模数据
  • 采用客户-服务器模式，很容易从一台机器扩展至成千上万台机器，每台机器均能提供本地存储和本地计算

主要应用领域

• 构建大型分布式集群（存储加计算）
• 数据仓库（存储）
• 数据挖掘（计算）

Hadoop2.0体系架构

• 公共组件Common
• 分布式文件系统HDFS
• 分布式操作系统Yarn（分布式资源管理系统）
• MapReduce引擎

Common

• 定位：其他模块的公共组件，定义程序员取得集群服务的编程接口，为其它模块提供公用API
• 作用：降低Hadoop设计的复杂性，减少其他模块间的耦合性，增强Hadoop健壮性。
• 功能：
  • 提供公用API和程序员编程接口
  • 本地Hadoop库
  • 超级用户
  • 服务器级别认证
  • HTTP认证

HDFS

• 定位：高容错、高扩展、高可靠，并提供服务访问接口。
• 内部特性：
  • 荣誉备份、副本存放、副本选择、心跳检测
  • 数据完整性检测、云数据磁盘失效
  • 简单一致性模型、流式数据访问、客户端缓存
  • 流水线复制、架构特征、超大规模数据集

Yarn

• 定位：管理计算机资源，提供用户和程序访问系统资源API

Spark原理（可能不考）

原因

Hadoop所使用的mapreduce效率还是较低，且如果需要输出作为输入，需要较长时间。并且在mapreduce过程中过于频繁的硬盘读写也是一个速度瓶颈。所以Spark就产生了，基于RDDD进行计算，独立性更强，速度更快，支持多种语言

高层库

Spark SQL

分布式SQL引擎，在Spark程序中使用API进行调用

Spark Streaming

实时分析大量数据，处理周期短。

Spark Graphx

以图为基础数据结构的算法实现和相关应用

Spark MLlib

解决机器学习的问题（分类、回归、类聚、协同过滤）

Spark实践（可能不考）

全部都是各种源代码，人都裂开了。`

OpenStack（重点）

简介

概述

OpenStack是一个管理计算、存储和网络资源的数据中心云计算开放平台，通过一个仪表盘，为管理员提供了所有的管理控制，同时通过web界面为其用户提供资源。

架构（前三个为核心部件）

• Nova（计算）
• Glance（镜像服务）
• Swift（对象存储）
• Keystone（身份服务）
• Neutron（网络&地址管理）
• Cinder（块存储）
• Horizon（UI界面）
• Manila（文件共享存储服务）

虚拟机创建过程

• 资源准备
  • 通过 Keystone 进行用户身份认证，通过认证后，用户即可与 Openstack API 节点通信，触发创建请求
  • 通过调度器获得启动虚拟机的最佳位置：通过工作守护进程获得物理节点上的资源状态； Nova scheduler
• 创建流程
  • 调用身份认证进行身份验证
  • 生成用于后续调用的令牌
  • 访问镜像服务以获取镜像列表，并获取目标基础镜像
  • 处理计算服务 API 请求
  • 处理计算服务对安全组和密钥调用的请求
  • 调用网络服务 API 确定可用网络
  • 通过计算节点调度程序选择 Hypervisor 节点
  • 调用块存储服务 API 为实例分配卷
  • 通过计算服务 API 调用再 Hypervisor 节点启动实例
  • 调用网络服务 API 为实例分配网络资源

架构设计

用户使用Web中提供的API对内部的API进行调用。

核心服务之间的依赖关系
运行 Openstack 服务的节点

• 云控制器：控制所有服务的节点
• 网络节点：运行网络服务的节点
• 计算节点：运行虚拟机的节点（也可以运行网络服务）

部署（重点）

DevOps

是一种软件研发管理的思想、方法论，他追求的是一种没有隔阂的理想研发写作的状态。

DevOps+OpenStack

要求

openstack软件和部署云基础架构的持续增长的复杂性必须被简化。

方式

基础架构中的所有内容都必须被自动化

将openstack分解为多个部分

要点

简化和模块化OpenStack需要根据需求进行定制

Ansible

基础架构自动化引擎：安装Ansible自身部署系统和管理的目标系统。

下面看的有点一知半解

云控制器

集群就能提高可用性，只要有多的机器即可。

• 非对称集群（只有在主服务器故障时备用服务器才会接管系统）

• 对称集群（正常情况下所有节点工作，作为负载均衡）

很多OpenStack的功能体现在基础架构服务中。

• 基础架构服务

  • 不属于 OpenStack 对外提供的公共服务，但被多个 Openstack 组件使用

  • 消息队列：必须是集群式 的； RabbitMQ ZeroMQ Qpid

  • 整合数据库： OpenStack 的环境数据，使用数据等； MySQL 和 MongoDB

• OpenStack 服务

  • 身份、镜像、计算、网络、存储等

Keystone

身份认证和服务目录（其他所有服务项Keystron注册API端点）

由多个Provider组成，都有自己的职责。

• 身份提供者 Identity Provider ：服务用户、管理员用户、终端用户
• 资源提供者 resource Provider project 、 domain
• 认证提供者 Authorization Provider ：用户和用户组和他们角色之间的关系
• 令牌提供者 Token Provider ：访问 openstack 服务需要一个有效的令牌，通过身份提供者的认证后获得令牌
• 目录提供者 Catalog Provider ：维护服务和 API 端点的目录
• 策略提供者 Policy Provider ：策略由多条规则组成，每条规则定义了哪些用户和角色被允许访问哪些资源

Nova管理组件及API

Nova是计算组织控制器，处理Openstack云中实例生命周期的所有活动。

其他服务

• Glance负责镜像管理
• 仪表盘服务
• 计量服务

计算节点

Hypervisor

是计算节点的核心，又称VMM

计算节点运行nova-compute服务，负责启动和终止虚拟机。

Magnum

• Bay 是一组运行 COE 软件的节点，表示一个容器集群
• Pod 是 COE 最基本的部署调度单元，逻辑上对应一个服务实例，运行一组容器，必须有一个作为网络路由

Nova单元

所有计算节点都需要与消息总线和数据库服务器通信，随着计算节点增多，使得消息队列和数据库过载，因此产生 Nova 计算单元

云计算核心算法

云计算的基础是分布式集群技术，所以需要良好的资源和任务调度算法

集群的基础算法有：

• Paxos算法
  • 朴素Paxos
  • Multi-Paxos
  • Raft算法
• DHT算法
• Gossip协议

Paxos算法

基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。

分布式一致性问题就是在分布式环境下多个节点或进程对某个值进行决议，在没有延时，丢包的理想网络环境中很容易做到，但是在实际操作中会出现问题。

共识算法

Consensus Algorithm，即使是在部分节点故障，网络延时、网络分割的情况下，多个节点均能对某个事情达成一致的看法。

介绍

主要是算法比较难理解

可以由一个或多个提议进程发起提案，所有进程对这个提案达成一致之后完成。

不存在恶意破坏整体一致性的节点，每一个节点都可信任。

具体过程

• 提议者向所有的决策者发送提案ID和Value等待回复。

  初始化的提案请求是prepare请求，只有提案ID，之后的是accept请求 ，是接受了决策者返回之后发出的，这时候有ID和Value

• 决策者如果已经收到其他提议者的Value就返回这个值，如果没有收到就返回空

• 决策者回应的时候就许下承诺（不接受更老的相同ID提案请求，不接受更老的accept请求）

• 提议者收到大多数的决策者的回复之后对ID和Value再次进行发送广播（Value值如果收到了就直接对最新的Value进行广播，如果没收到就随机）

• 决策者收到这个广播之后进行accept处理之后再次回应

• 提议者收到多数回应之后表示提案成功，将决议发给所有的Learner

活锁

由于可能由两个提议者一直循环提出编号递增的提案，死循环，没有value，可以选定一个主Proposer，只有这个都可以提出提案。

典型场景1（数据副本一致性）

• 主从同步方式

  主数据收到请求之后要求所有副本执行相同操作之后返回，所有副本执行成功之后主数据才会进行自我操作然后返回。不能保证可用性

• 主从异步复制

  主数据直接对自己进行操作并返回之后要求所有的副本进行相同操作，不能保证一致性。

典型场景2（多副本状态机）

多台机器拥有完全相同的状态，运行完全相同的确定性状态机。使用这个来解决单节点故障的解决方案。

Multi-Paxos

如果只有一个人发起请求，就可以省去prepare请求，直接使用随机值作为value。

在知乎上找到了一篇比较详细的说明文章，可以参考：https://zhuanlan.zhihu.com/p/42912831

后面还有算法的详细解析：https://zhuanlan.zhihu.com/p/45742830

说实话本人还是看不懂，欢迎评论解答

Raft算法

Raft算法可以看官方GitHub主页，有对应的文档。

官方也提供了动画演示网页。通过观看来了解算法

DHT算法

Distributed Hash Table，分布式哈希表

云计算模式——按照功能划分服务器类型

物联网模式——客户端服务器的重要集中式架构

对等计算模型——所有节点地位相同，共同作为服务器

因为单点服务器更容易故障。

DHT算法可以实现在P2P网络中节点连接和通信的一种方式，实现了各个节点之间的地位对等。

P2P网络拓扑结构

• 集中式拓扑结构

  由中央服务器进行统一目录管理，但是当节点规模过大时会有瓶颈

• 分布式非结构化拓扑模式

  没有中央服务器，每个节点存储自己的信息，但是超出一定范围之后互相之间并不知情，导致搜索具有盲目性

• 分布式结构化拓扑

  和上一个基本相同但是在网络搜索信息时，互相知道信息可能存储在哪些节点，搜索效率较高。

DHT算法就是依据分布式结构化拓扑模式

算法原理简介

主要服务数据存储，核心是资源定位。

采用分布式+hash+数据表

数据存储在多个节点上，节点是对等的，是数据表的一部分，使用一致性Hash函数继续那个代表数据的key和value映射到具体的节点上。

核心：将节点和key散列到同样的空间中，节点散列后得到ID，均匀分布在散列空间中，实现负载均衡。

一致性Hash

普通的Hash算法会导致当由服务器失效或者新的服务器添加的时候原有Hash表完全变动，需要全部重新结算，所以使用一致性Hash

一致性Hash把Cache和资源视为同等概念，都进行Hash，所以Hash结果和Cache数量无关。

这种算法能保证：

• 单调性（在新的Cache加入系统时不会干扰原有系统）
• 平衡性（Hash的结果能够尽可能分不到所有的Cache中去，实现负载均衡。）

算法优点

• 只需要给定资源的Key就能够在网络中查找资源具体数据，而不需要指定资源IP等网络信息

• 能够很好的共享下层设施，形成一个统一的基于内容的命名层，增加了寻找对象的灵活性

• 网络时自组织和自治的，降低了执行、维护和管理的代价

只要节点愿意提供网络带宽和PC资源就能直接使用。

DHT算法的具体实现有Chord、Pastry，Kademlia

Chord（不考）

对Node和Key使用相同的Hash函数映射到同一个标识符空间，保证一致性哈希。

散列空间中的标识符看作首位相连的环，标识符可能是节点也可能是资源

Node使用IP作为Hash输入，数据资源可以使用名称

简单的情况下寻找资源就直接在圆环上依次寻找，可伸缩方法节点中有路由表，通过路由表查询能够到找到比较接近的节点位置，直接进行跳转。如果在路由表的最后一项都比资源小，直接跳转到路由表最远端节点。

节点加入

一个节点通知后面一个节点他自己的存在，然后通知后一个节点他的接入，后一个节点将加入的节点设置为自己的前序节点。之后圆环进入稳定阶段，每个节点规律性检查自己的后续节点的前序节点是不是自己。

节点退出

需要修改相邻节点的前序节点和后续节点，并修改路由列表

Pastry（不考）

核心思想就是让一个节点知道更多的关于其他节点的信息，也有一个路由表，每一个节点都会有叶子节点集和路由表。

每个节点的标识符为n位，路由表有n行，第一行是n位与本节点都不相同的节点，第二行一位相同……

标准表述：路由表的（i，j）的意义是这个节点的前i位与路由表所在节点相同，且（i+1）的位置的值为j

在叶子节点集中是最贴近当前节点的前后几个节点，各占一半。

具体可以看图

应该不会考，李传艺自己都搞不清楚。

Gossip协议（不考）