分类目录归档:架构

用面向对象设计原则理解Golang中Interface

Interface接口

interface 是GO语言的基础特性之一。可以理解为一种类型的规范或者约定。它跟java,C# 不太一样,不需要显示说明实现了某个接口,它没有继承或子类或“implements”关键字,只是通过约定的形式,隐式的实现interface 中的方法即可。因此,Golang 中的 interface 让编码更灵活、易扩展。

如何理解go 语言中的interface ?只需记住以下三点即可。

  • interface是方法声明的集合
  • 任何类型的对象实现了在interface接口中声明的全部方法,则表明该类型实现了接口。
  • interface可以作为一种数据类型,实现了该接口的任何对象都可以给对应的接口类型变量赋值。

注意:

  • interface可以被任意对象实现,一个类型/对象也可以实现多个interface.
  • 方法不能重载,如eat(), eat(s string)不能同时存在
package main

import "fmt"

type Phone interface {
    call()
}

type NokiaPhone struct {
}

func (nokiaPhone NokiaPhone) call() {
    fmt.Println("I am Nokia, I can call you!")
}

type ApplePhone struct {
}

func (iPhone ApplePhone) call() {
    fmt.Println("I am Apple Phone, I can call you!")
}

func main() {
    var phone Phone
    phone = new(NokiaPhone)
    phone.call()

    phone = new(ApplePhone)
    phone.call()
}

输出结果

I am Nokia, I can call you!
I am Apple Phone, I can call you!

上述中体现了interface接口的语法,在main函数中,也体现了多态的特性。
同样一个phone的抽象接口,分别指向不同的实体对象,调用的call()方法,打印的效果不同,那么就是体现出了多态的特性。

面向对象中的开闭原则

平铺式的模块设计

那么作为interface数据类型,他存在的意义在哪呢?实际上是为了满足一些面向对象的编程思想。我们知道,软件设计的最高目标就是高内聚,低耦合。那么其中有一个设计原则叫开闭原则。什么是开闭原则呢,接下来我们看一个例子:

package main

import "fmt"

//我们要写一个类,Banker银行业务员
type Banker struct {
}

//存款业务
func (this *Banker) Save() {
    fmt.Println( "进行了 存款业务...")
}

//转账业务
func (this *Banker) Transfer() {
    fmt.Println( "进行了 转账业务...")
}

//支付业务
func (this *Banker) Pay() {
    fmt.Println( "进行了 支付业务...")
}

func main() {
    banker := &Banker{}

    banker.Save()
    banker.Transfer()
    banker.Pay()
}

输出结果

进行了 存款业务...
进行了 转账业务...
进行了 支付业务...

代码很简单,就是一个银行业务员,他可能拥有很多的业务,比如Save()存款、Transfer()转账、Pay()支付等。那么如果这个业务员模块只有这几个方法还好,但是随着我们的程序写的越来越复杂,银行业务员可能就要增加方法,会导致业务员模块越来越臃肿。

这样的设计会导致,当我们去给Banker添加新的业务的时候,会直接修改原有的Banker代码,那么Banker模块的功能会越来越多,出现问题的几率也就越来越大,假如此时Banker已经有99个业务了,现在我们要添加第100个业务,可能由于一次的不小心,导致之前99个业务也一起崩溃,因为所有的业务都在一个Banker类里,他们的耦合度太高,Banker的职责也不够单一,代码的维护成本随着业务的复杂正比成倍增大。

开闭设计原则

那么,如果我们拥有接口, interface这个东西,那么我们就可以抽象一层出来,制作一个抽象的Banker模块,然后提供一个抽象的方法。分别根据这个抽象模块,去实现支付Banker(实现支付方法),转账Banker(实现转账方法)如下:

那么依然可以搞定程序的需求。然后,当我们想要给Banker添加额外功能的时候,之前我们是直接修改Banker的内容,现在我们可以单独定义一个股票Banker(实现股票方法),到这个系统中。而且股票Banker的实现成功或者失败都不会影响之前的稳定系统,他很单一,而且独立。

所以以上,当我们给一个系统添加一个功能的时候,不是通过修改代码,而是通过增添代码来完成,那么就是开闭原则的核心思想了。所以要想满足上面的要求,是一定需要interface来提供一层抽象的接口的。

package main

import "fmt"

//抽象的银行业务员
type AbstractBanker interface {
    DoBusi() //抽象的处理业务接口
}

//存款的业务员
type SaveBanker struct {
    //AbstractBanker
}

func (sb *SaveBanker) DoBusi() {
    fmt.Println("进行了存款")
}

//转账的业务员
type TransferBanker struct {
    //AbstractBanker
}

func (tb *TransferBanker) DoBusi() {
    fmt.Println("进行了转账")
}

//支付的业务员
type PayBanker struct {
    //AbstractBanker
}

func (pb *PayBanker) DoBusi() {
    fmt.Println("进行了支付")
}

func main() {
    //进行存款
    sb := &SaveBanker{}
    sb.DoBusi()

    //进行转账
    tb := &TransferBanker{}
    tb.DoBusi()

    //进行支付
    pb := &PayBanker{}
    pb.DoBusi()
}

输出结果

进行了存款
进行了转账
进行了支付

当然我们也可以根据AbstractBanker设计一个小框架

//实现架构层(基于抽象层进行业务封装-针对interface接口进行封装)
func BankerBusiness(banker AbstractBanker) {
    //通过接口来向下调用,(多态现象)
    banker.DoBusi()
}

那么main中可以如下实现业务调用:

func main() {
    //进行存款
    BankerBusiness(&SaveBanker{})
    //进行存款
    BankerBusiness(&TransferBanker{})
    //进行存款
    BankerBusiness(&PayBanker{})
}

开闭原则定义:

​ 一个软件实体如类、模块和函数应该对扩展开放,对修改关闭。
​ 简单的说就是在修改需求的时候,应该尽量通过扩展来实现变化,而不是通过修改已有代码来实现变化。

接口的意义

好了,现在interface已经基本了解,那么接口的意义最终在哪里呢,想必现在你已经有了一个初步的认知,实际上接口的最大的意义就是实现多态的思想,就是我们可以根据interface类型来设计API接口,那么这种API接口的适应能力不仅能适应当下所实现的全部模块,也适应未来实现的模块来进行调用。 调用未来可能就是接口的最大意义所在吧,这也是为什么架构师那么值钱,因为良好的架构师是可以针对interface设计一套框架,在未来许多年却依然适用。

面向对象中的依赖倒转原则

耦合度极高的模块设计

代码实现如下

package main

import "fmt"

// === > 奔驰汽车 <===
type Benz struct {
  //...
}

func (this *Benz) Run() {
    fmt.Println("Benz is running...")
}

// === > 宝马汽车  <===
type BMW struct {
  //...
}

func (this *BMW) Run() {
    fmt.Println("BMW is running ...")
}

//===> 司机张三  <===
type Zhang3 struct {
    //...
}

func (zhang3 *Zhang3) DriveBenZ(benz *Benz) {
    fmt.Println("zhang3 Drive Benz")
    benz.Run()
}

func (zhang3 *Zhang3) DriveBMW(bmw *BMW) {
    fmt.Println("zhang3 drive BMW")
    bmw.Run()
}

//===> 司机李四 <===
type Li4 struct {
    //...
}

func (li4 *Li4) DriveBenZ(benz *Benz) {
    fmt.Println("li4 Drive Benz")
    benz.Run()
}

func (li4 *Li4) DriveBMW(bmw *BMW) {
    fmt.Println("li4 drive BMW")
    bmw.Run()
}

func main() {
    //业务1 张3开奔驰
    benz := &Benz{}
    zhang3 := &Zhang3{}
    zhang3.DriveBenZ(benz)

    //业务2 李四开宝马
    bmw := &BMW{}
    li4 := &Li4{}
    li4.DriveBMW(bmw)
}

输出结果:

zhang3 Drive Benz
Benz is running...
li4 drive BMW
BMW is running ...

我们来看上面的代码和图中每个模块之间的依赖关系,实际上并没有用到任何的interface接口层的代码,显然最后我们的两个业务 张三开奔驰, 李四开宝马,程序中也都实现了。但是这种设计的问题就在于,小规模没什么问题,但是一旦程序需要扩展,比如我现在要增加一个丰田汽车 或者 司机王五, 那么模块和模块的依赖关系将成指数级递增,想蜘蛛网一样越来越难维护和捋顺。

面向抽象层的依赖倒转设计

如上图所示,如果我们在设计一个系统的时候,将模块分为3个层次,抽象层、实现层、业务逻辑层。那么,我们首先将抽象层的模块和接口定义出来,这里就需要了interface接口的设计,然后我们依照抽象层,依次实现每个实现层的模块,在我们写实现层代码的时候,实际上我们只需要参考对应的抽象层实现就好了,实现每个模块,也和其他的实现的模块没有关系,这样也符合了上面介绍的开闭原则。这样实现起来每个模块只依赖对象的接口,而和其他模块没关系,依赖关系单一。系统容易扩展和维护。
我们在指定业务逻辑也是一样,只需要参考抽象层的接口来业务就好了,抽象层暴露出来的接口就是我们业务层可以使用的方法,然后可以通过多态的线下,接口指针指向哪个实现模块,调用了就是具体的实现方法,这样我们业务逻辑层也是依赖抽象成编程。
我们就将这种的设计原则叫做依赖倒转原则

来一起看一下修改的代码:

package main

import "fmt"

// ===== >   抽象层  < ========
type Car interface {
    Run()
}

type Driver interface {
    Drive(car Car)
}

// ===== >   实现层  < ========
type BenZ struct {
    //...
}

func (benz *BenZ) Run() {
    fmt.Println("Benz is running...")
}

type Bmw struct {
    //...
}

func (bmw *Bmw) Run() {
    fmt.Println("Bmw is running...")
}

type Zhang_3 struct {
    //...
}

func (zhang3 *Zhang_3) Drive(car Car) {
    fmt.Println("Zhang3 drive car")
    car.Run()
}

type Li_4 struct {
    //...
}

func (li4 *Li_4) Drive(car Car) {
    fmt.Println("li4 drive car")
    car.Run()
}

// ===== >   业务逻辑层  < ========
func main() {
    //张3 开 宝马
    var bmw Car
    bmw = &Bmw{}

    var zhang3 Driver
    zhang3 = &Zhang_3{}

    zhang3.Drive(bmw)

    //李4 开 奔驰
    var benz Car
    benz = &BenZ{}

    var li4 Driver
    li4 = &Li_4{}

    li4.Drive(benz)
}

输出结果

Zhang3 drive car
Bmw is running...
li4 drive car
Benz is running...

依赖倒转小案例

模拟组装2台电脑

  • 抽象层

​ 有显卡Card 方法display,有内存Memory 方法storage,有处理器CPU 方法calculate

  • 实现层

​ 有 Intel因特尔公司 、产品有(显卡、内存、CPU),有 Kingston 公司, 产品有(内存3),有 NVIDIA 公司, 产品有(显卡)

  • 逻辑层
  1. 组装一台Intel系列的电脑,并运行
  2. 组装一台 Intel CPU Kingston内存 NVIDIA显卡的电脑,并运行

代码实现

package main

import "fmt"

//------  抽象层 -----
type Card interface {
    Display()
}

type Memory interface {
    Storage()
}

type CPU interface {
    Calculate()
}

type Computer struct {
    cpu  CPU
    mem  Memory
    card Card
}

func NewComputer(cpu CPU, mem Memory, card Card) *Computer {
    return &Computer{
        cpu:  cpu,
        mem:  mem,
        card: card,
    }
}

func (this *Computer) DoWork() {
    this.cpu.Calculate()
    this.mem.Storage()
    this.card.Display()
}

//------  实现层 -----
//intel
type IntelCPU struct {
    CPU
}

func (this *IntelCPU) Calculate() {
    fmt.Println("Intel CPU 开始计算了...")
}

type IntelMemory struct {
    Memory
}

func (this *IntelMemory) Storage() {
    fmt.Println("Intel Memory 开始存储了...")
}

type IntelCard struct {
    Card
}

func (this *IntelCard) Display() {
    fmt.Println("Intel Card 开始显示了...")
}

//kingston
type KingstonMemory struct {
    Memory
}

func (this *KingstonMemory) Storage() {
    fmt.Println("Kingston memory storage...")
}

//nvidia
type NvidiaCard struct {
    Card
}

func (this *NvidiaCard) Display() {
    fmt.Println("Nvidia card display...")
}

//------  业务逻辑层 -----
func main() {
    //intel系列的电脑
    com1 := NewComputer(&IntelCPU{}, &IntelMemory{}, &IntelCard{})
    com1.DoWork()

    //杂牌子
    com2 := NewComputer(&IntelCPU{}, &KingstonMemory{}, &NvidiaCard{})
    com2.DoWork()
}

输出结果

Intel CPU 开始计算了...
Intel Memory 开始存储了...
Intel Card 开始显示了...
Intel CPU 开始计算了...
Kingston memory storage...
Nvidia card display...

分布式基础知识

1. 中间件原理

中间件(middleware)是基础软件的一大类,属于可复用软件的范畴。

中间件处于操作系统软件与用户的应用软件的中间。中间件在操作系统、网络和数据库之上,应用软件的下层,总的作用是为处于自己上层的应用软件提供运行与开发的环境,帮助用户灵活、高效地开发和集成复杂的应用软件.

IDC的定义是:中间件是一种独立的系统软件或服务程序,分布式应用软件借助这种软件在不同的技术之间共享资源,中间件位于客户机服务器的操作系统之上,管理计算资源和网络通信。

中间件解决的问题是:

在中间件产生以前,应用软件直接使用操作系统、网络协议和数据库等开发,这些都是计算机最底层的东西,越底层越复杂,开发者不得不面临许多很棘手的问题,如操作系统的多样性,繁杂的网络程序设计、管理,复杂多变的网络环境,数据分散处理带来的不一致性问题、性能和效率、安全,等等。

这些与用户的业务没有直接关系,但又必须解决,耗费了大量有限的时间和精力。于是,有人提出能不能将应用软件所要面临的共性问题进行提炼、抽象,在操作系统之上再形成一个可复用的部分,供成千上万的应用软件重复使用。这一技术思想最终构成了中间件这类的软件。

中间件屏蔽了底层操作系统的复杂性,使程序开发人员面对一个简单而统一的开发环境,减少程序设计的复杂性,将注意力集中在自己的业务上,不必再为程序在不同系统软件上的移植而重复工作,从而大大减少了技术上的负担。

2. Hash冲突有什么解决办法

解决hash冲突的办法 有四种:

  • 开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列).
  • 再哈希法.
  • 链地址法.
  • 建立一个公共溢出区.

3. 微服务架构是什么样子的

通常传统的项目体积庞大,需求、设计、开发、测试、部署流程固定。新功能需要在原项目上做修改。

但是微服务可以看做是对大项目的拆分,是在快速迭代更新上线的需求下产生的。新的功能模块会发布成新的服务组件,与其他已发布的服务组件一同协作。 服务内部有多个生产者和消费者,通常以http rest的方式调用,服务总体以一个(或几个)服务的形式呈现给客户使用。

微服务架构是一种思想对微服务架构我们没有一个明确的定义,但简单来说微服务架构是:

采用一组服务的方式来构建一个应用,服务独立部署在不同的进程中,不同服务通过一些轻量级交互机制来通信,例如 RPC、HTTP 等,服务可独立扩展伸缩,每个服务定义了明确的边界,不同的服务甚至可以采用不同的编程语言来实现,由独立的团队来维护。

Golang的微服务框架kit中有详细的微服务的例子,可以参考学习.

微服务架构设计包括:

  1. 服务熔断降级限流机制 熔断降级的概念(Rate Limiter 限流器,Circuit breaker 断路器).
  2. 框架调用方式解耦方式 KitIstioMicro 服务发现(consul zookeeper kubeneters etcd ) RPC调用框架.
  3. 链路监控,zipkinprometheus.
  4. 多级缓存.
  5. 网关 (kong gateway).
  6. Docker部署管理 Kubenetters.
  7. 自动集成部署 CI/CD 实践.
  8. 自动扩容机制规则.
  9. 压测 优化.
  10. Trasport 数据传输(序列化和反序列化).
  11. Logging 日志.
  12. Metrics 指针对每个请求信息的仪表盘化.

微服务架构介绍详细的可以参考:

Microservice Architectures

4. 分布式锁实现

在分析分布式锁的三种实现方式之前,先了解一下分布式锁应该具备哪些条件:

  1. 在分布式系统环境下,一个方法在同一时间只能被一个机器的一个线程执行;
  2. 高可用的获取锁与释放锁;
  3. 高性能的获取锁与释放锁;
  4. 具备可重入特性;
  5. 具备锁失效机制,防止死锁;
  6. 具备非阻塞锁特性,即没有获取到锁将直接返回获取锁失败。

分布式的CAP理论告诉我们“任何一个分布式系统都无法同时满足一致性(Consistency)、可用性(Availability)和分区容错性(Partition tolerance),最多只能同时满足两项”。
所以,很多系统在设计之初就要对这三者做出取舍。在互联网领域的绝大多数的场景中,都需要牺牲强一致性来换取系统的高可用性,系统往往只需要保证“最终一致性”,只要这个最终时间是在用户可以接受的范围内即可。

通常分布式锁以单独的服务方式实现,目前比较常用的分布式锁实现有三种:

  • 基于数据库实现分布式锁。
  • 基于缓存Redis实现分布式锁。
  • 基于Etcd实现分布式锁。

尽管有这三种方案,但是不同的业务也要根据自己的情况进行选型,他们之间没有最好只有更适合!

  • 基于数据库的实现方式

基于数据库的实现方式的核心思想是,在数据库中创建一个表,表中包含方法名等字段,并在方法名字段上创建唯一索引,想要执行某个方法,就使用这个方法名向表中插入数据,成功插入则获取锁,执行完成后删除对应的行数据释放锁。

使用基于数据库的这种实现方式很简单,但是对于分布式锁应该具备的条件来说,它有一些问题需要解决及优化:

1、因为是基于数据库实现的,数据库的可用性和性能将直接影响分布式锁的可用性及性能,所以,数据库需要双机部署、数据同步、主备切换;

2、不具备可重入的特性,因为同一个线程在释放锁之前,行数据一直存在,无法再次成功插入数据,所以,需要在表中新增一列,用于记录当前获取到锁的机器和线程信息,在再次获取锁的时候,先查询表中机器和线程信息是否和当前机器和线程相同,若相同则直接获取锁;

3、没有锁失效机制,因为有可能出现成功插入数据后,服务器宕机了,对应的数据没有被删除,当服务恢复后一直获取不到锁,所以,需要在表中新增一列,用于记录失效时间,并且需要有定时任务清除这些失效的数据;

4、不具备阻塞锁特性,获取不到锁直接返回失败,所以需要优化获取逻辑,循环多次去获取。

5、在实施的过程中会遇到各种不同的问题,为了解决这些问题,实现方式将会越来越复杂;依赖数据库需要一定的资源开销,性能问题需要考虑。

  • 基于Redis的实现方式

利用Redis的 SetNX来实现分布式锁,性能高, edis可持久化,也能保证数据不易丢失,redis集群方式提高稳定性。

  • 基于Etcd实现分布式锁

Etcd提供了实现分布式锁的特性:

  1. Raft一致性,是工程上使用较为广泛,强一致性、去中心化、高可用的分布式协议。

Raft提供了分布式系统的可靠性功能。详细的查看Raft.

  1. Lease功能

Lease功能,就是租约机制(TimeToLive,即TTL)。

  • Etcd可以对存储Key Value的数据设置租约,也就是给Key Value设置一个过期时间,当租约到期,Key Value将会失效而被Etcd删除。

  • Etcd同时也支持续约租期,可以通过客户端在租约到期之间续约,以避免Key Value失效;

  • Etcd还支持解约,一旦解约,与该租约绑定的Key Value将会失效而删除。

Lease 功能可以保证分布式锁的安全性,为锁对应的 key配置租约,即使锁的持有者因故障而不能主动释放锁,锁也会因租约到期而自动释放。

  1. Watch功能

监听功能。Watch机制支持监听某个固定的key,它也支持Watch一个范围(前缀机制),当被watch的key或范围发生变化时,客户端将收到通知。

在实现分布式锁时,如果抢锁失败,可通过 Prefix 机制返回的Key Value列表获得 Revision 比自己小且相差最小的 key(称为 pre-key),对 pre-key 进行监听,因为只有它释放锁,自己才能获得锁,如果 Watch 到 pre-key 的 DELETE 事件,则说明pre-ke已经释放,自己已经持有锁。

  1. Prefix功能

前缀机制:

目录机制,如两个 key 命名如下:key1=“/mykey/key1″ , key2=”/mykey/key2″,那么,可以通过前缀“/mykey”查询,返回包含两个 Key Value对的列表。可以和前面的watch功能配合使用。

通常呢, 例如我们创建一个名为 /mylock 的锁,两个争抢它的客户端进行写操作,实际写入的 key 分别为:key1=”/mylock/UUID1″key2=”/mylock/UUID2″,其中,UUID 表示全局唯一的 ID,确保两个 key 的唯一性。

很显然,写操作都会成功,但返回的Revision 不一样,那么,如何判断谁获得了锁呢?通过前缀 /mylock 查询,返回包含两个Key Value对的的 Key Value列表,同时也包含它们的 Revision,通过 Revision 大小,客户端可以判断自己是否获得锁,如果抢锁失败,则等待锁释放(对应的 key 被删除或者租约过期),然后再判断自己是否可以获得锁。

Lease 功能和 Prefix功能,能解决上面的死锁问题。

  1. Revision功能

每个 key 带有一个 Revision 号,每进行一次事务加一,因此它是全局唯一的,如初始值为 0,进行一次 put(key, value),key 的 Revision 变为 1;

同样的操作,再进行一次,Revision 变为 2;换成 key1 进行 put(key1, value) 操作,Revision 将变为 3。

这种机制有一个作用:

通过 Revision 的大小就可以知道进行写操作的顺序。在实现分布式锁时,多个客户端同时抢锁,根据 Revision 号大小依次获得锁,可以避免”惊群效应”,实现公平锁。

6. 互斥锁和读写锁和死锁问题是怎么解决

  • 互斥锁

互斥锁就是互斥变量mutex,用来锁住临界区的.

条件锁就是条件变量,当进程的某些资源要求不满足时就进入休眠,也就是锁住了。当资源被分配到了,条件锁打开,进程继续运行;读写锁,也类似,用于缓冲区等临界资源能互斥访问的。

  • 读写锁

通常有些公共数据修改的机会很少,但其读的机会很多。并且在读的过程中会伴随着查找,给这种代码加锁会降低我们的程序效率。读写锁可以解决这个问题。

注意:写独占,读共享,写锁优先级高

  • 死锁

一般情况下,如果同一个线程先后两次调用lock,在第二次调用时,由于锁已经被占用,该线程会挂起等待别的线程释放锁,然而锁正是被自己占用着的,该线程又被挂起而没有机会释放锁,因此就永远处于挂起等待状态了,这叫做死锁(Deadlock)。

另外一种情况是:若线程A获得了锁1,线程B获得了锁2,这时线程A调用lock试图获得锁2,结果是需要挂起等待线程B释放锁2,而这时线程B也调用lock试图获得锁1,结果是需要挂起等待线程A释放锁1,于是线程A和B都永远处于挂起状态了。

死锁产生的四个必要条件:

  1. 互斥条件:一个资源每次只能被一个进程使用.
  2. 请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放。
  3. 不剥夺条件:进程已获得的资源,在未使用完之前,不能强行剥夺。
  4. 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

这四个条件是死锁的必要条件,只要系统发生死锁,这些条件必然成立,而只要上述条件之一不满足,就不会发生死锁。

a. 预防死锁

可以把资源一次性分配:(破坏请求和保持条件).

然后剥夺资源:即当某进程新的资源未满足时,释放已占有的资源(破坏不可剥夺条件).

资源有序分配法:系统给每类资源赋予一个编号,每一个进程按编号递增的顺序请求资源,释放则相反(破坏环路等待条件).

b. 避免死锁

预防死锁的几种策略,会严重地损害系统性能。因此在避免死锁时,要施加较弱的限制,从而获得 较满意的系统性能。由于在避免死锁的策略中,允许进程动态地申请资源。因而,系统在进行资源分配之前预先计算资源分配的安全性。
若此次分配不会导致系统进入不安全状态,则将资源分配给进程;否则,进程等待。其中最具有代表性的避免死锁算法是银行家算法。

c. 检测死锁

首先为每个进程和每个资源指定一个唯一的号码,然后建立资源分配表和进程等待表.

d. 解除死锁

当发现有进程死锁后,便应立即把它从死锁状态中解脱出来,常采用的方法有.

e. 剥夺资源

从其它进程剥夺足够数量的资源给死锁进程,以解除死锁状态.

f. 撤消进程

可以直接撤消死锁进程或撤消代价最小的进程,直至有足够的资源可用,死锁状态.消除为止.所谓代价是指优先级、运行代价、进程的重要性和价值等。

7. Etcd的Raft一致性算法原理

Etcd中的Raft一致性算法原理:

Raft将系统中的角色分为领导者(Leader)、跟从者(Follower)和候选人(Candidate).

  1. Leader:接受客户端请求,并向Follower同步请求日志,当日志同步到大多数节点上后告诉Follower提交日志。
  2. Follower:接受并持久化Leader同步的日志,在Leader告之日志可以提交之后,提交日志。
  3. Candidate:Leader选举过程中的临时角色。

Raft要求系统在任意时刻最多只有一个Leader,正常工作期间只有Leader和Followers。

Raft算法角色状态转换如下:

Follower只响应其他服务器的请求。如果Follower超时没有收到Leader的消息,它会成为一个Candidate并且开始一次Leader选举。收到大多数服务器投票的Candidate会成为新的Leader。Leader在宕机之前会一直保持Leader的状态。

Raft算法将时间分为一个个的任期(term),每一个term的开始都是Leader选举。在成功选举Leader之后,Leader会在整个term内管理整个集群。如果Leader选举失败,该term就会因为没有Leader而结束。

Leader选举:

Raft 使用心跳(heartbeat)触发Leader选举。当服务器启动时,初始化为Follower。Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat,就会等待一段随机的时间后发起一次Leader选举。

Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC (RPC细节参见八、Raft算法总结)。

结果有以下三种情况:
1.赢得了多数的选票,成功选举为Leader;
2.收到了Leader的消息,表示有其它服务器已经抢先当选了Leader;
3.没有服务器赢得多数的选票,Leader选举失败,等待选举时.

Raft日志同步保证如下两点:

  1. 如果不同日志中的两个条目有着相同的索引和任期号,则它们所存储的命令是相同的。
  2. 如果不同日志中的两个条目有着相同的索引和任期号,则它们之前的所有条目都是完全一样的。

Leader通过强制Followers复制它的日志来处理日志的不一致,Followers上的不一致的日志会被Leader的日志覆盖。
Leader为了使Followers的日志同自己的一致,Leader需要找到Followers同它的日志一致的地方,然后覆盖Followers在该位置之后的条目。
Leader会从后往前试,每次AppendEntries失败后尝试前一个日志条目,直到成功找到每个Follower的日志一致位点,然后向后逐条覆盖Followers在该位置之后的条目。

Raft增加了如下两条限制以保证安全性:

  1. 拥有最新的已提交的log entry的Follower才有资格成为Leader。
    这个保证是在RequestVote RPC中做的,Candidate在发送RequestVote RPC时,要带上自己的最后一条日志的term和log index,其他节点收到消息时,如果发现自己的日志比请求中携带的更新,则拒绝投票。日志比较的原则是,如果本地的最后一条log entry的term更大,则term大的更新,如果term一样大,则log index更大的更新。

  2. Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志,旧term日志的提交要等到提交当前term的日志来间接提交(log index 小于 commit index的日志被间接提交)。

日志压缩:

在实际的系统中,不能让日志无限增长,否则系统重启时需要花很长的时间进行回放,从而影响可用性。Raft采用对整个系统进行snapshot来解决,snapshot之前的日志都可以丢弃。

每个副本独立的对自己的系统状态进行snapshot,并且只能对已经提交的日志记录进行snapshot。

做snapshot既不要做的太频繁,否则消耗磁盘带宽, 也不要做的太不频繁,否则一旦节点重启需要回放大量日志,影响可用性。推荐当日志达到某个固定的大小做一次snapshot。
做一次snapshot可能耗时过长,会影响正常日志同步。可以通过使用copy-on-write技术避免snapshot过程影响正常日志同步.