《DDD之形》把当前一些流行的架构给通览了一篇，那是不是万事大吉，随便挑一个形态实践就行呢？

正常情况对于有追求的程序员来讲，肯定不行，有两个原因

一因为完美，人人都是想要完美，每个架构实践都不是完美的，尤其离开业务场景去探讨架构，会使架构没法落地；因此你小抄的时候会变形，想把原先至少不太好的地方改得相对好些，但这样可能造成四不像

二因为没有意的形，只知其形，不得其意，必然会东施效颦；类似于第一点，完美，何为完美，还是得根据自身经验理解程序得出的结论，如果高度不够必然会画蛇添足

标准形态

根据DDD的理论，或者说DDD带来的优势，将三层架构进行演化，把业务逻辑层再细拆分成三层：应用层、领域层和基础设施层

分离业务逻辑与技术细节

DDD的标准形态

分层架构分为两种：严格分层架构和松散分层架构

严格分层，某层只能与直接位于其下方的层发生耦合；松散分层，允许任意上方层与任意下方层发生耦合

1. User Interface是用户接口层，主要用于处理用户发送的Restful请求和解析用户输入的配置文件等，并将信息传递给Application层的接口
2. Application层是应用层，负责多进程管理及调度、多线程管理及调度、多协程调度和维护业务实例的状态模型。当调度层收到用户接口层的请求后，委托Context层与本次业务相关的上下文进行处理
3. Domain层是领域层，定义领域模型，不仅包括领域对象及其之间关系的建模，还包括对象的角色role的显式建模
4. Infrastructure层是基础实施层，为其他层提供通用的技术能力：业务平台，编程框架，持久化机制，消息机制，第三方库的封装，通用算法，等等

DIP

上面的标准形态图形的左半边图，跟以往的很不一样，但从DIP角度看，低层服务应该依赖于高层组件

这是COLA2.0的分层，作者利用DIP对1.0版本进行了优化

1、核心业务逻辑和技术细节相分离，使用DIP，让Infrastructure反向依赖Domain

2、将repository上移到application层，把组装entity的责任转移到application

到此一切都很常规，很标准，但在落地时有几个问题：

一、Controller是哪一层，user interface层？还是infrastructure层？

这好像不是个问题，一般都放在user interface层，负责向用户展现信息以及解释用户命令；但细想一下，我们的controller都是基于底层框架，是框架提供的能力，那理论上放在infrastructure更合理一些。

二、再细化的架构元素放哪里？

其实这只是分层的大体方向，还有更细节的元素，在实践DDD的过程中，最常见的问题就是元素到底放在哪儿，比如Event,有各样的event，eventHandler，应用层、领域层都有，怎么区分呢？貌似回到了怎么区分应用服务与领域服务；还有各处javabean，哪些层能复用，谁复用谁

再比如COLA2.0，单从层次依赖图明显形成了循环依赖，落地不了；但作者把repository上移到了application层，又有些走不寻常路，一般来讲repository是放在domain层

如何办呢？大方向有了，但到小细节时，又有各种困惑，《SOLID之DIP》文中提到，分层至少有两层，一是业务领域层，二是其它层

这就是端口和适配器架构，可以算是六边形的简化版，但也从整体方向分成了两层，对应用层与用户接口层以及基础设施层进行了合并，无论是接受请求，还是输出数据都是gateway

但六边形架构仅仅区分了内外边界，提炼了端口与适配器角色，并没有规划限界上下文内部各个层次与各个对象之间的关系；怎么破？

这似乎是两个矛盾体，标准的层次分明了，但还是有些不确定性，对象放在哪个包不明确；而端口与适配器架构又太粗放；如何平衡？

本质上，领域驱动设计的限界上下文同样是对软件系统的切割，依据的关注点主要是根据领域知识的语境，从而体现业务能力的差异。在进入限界上下文内部，我们又可以针对限界上下文进行关注点的切割，并在其内部体现出清晰的层次结构，这个层次遵循整洁架构

根据张逸老师DDD课程中的案例

• 领域层：包含 PlaceOrderService、Order、Notification、OrderConfirmed 与抽象的 OrderRepository，封装了纯粹的业务逻辑，不掺杂任何与业务无关的技术实现。
• 应用层：包含 OrderAppService 以及抽象的 EventBus 与 NotificationService，提供对外体现业务价值的统一接口，同时还包含了基础设施功能的抽象接口。
• 基础设施层：包含 OrderMapper、RabbitEventBus 与 EmailSender，为业务实现提供对应的技术功能支撑，但真正的基础设施访问则委派给系统边界之外的外部框架或驱动器

重新审视六边形架构，匹配分层架构，两者可以融合

位于六边形边线之上的出口端口就应该既不属于领域层，又不属于基础设施层。它的职责与属于应用层的入口端口也不同，因为应用层的应用服务是对外部请求的封装，相当于是一个业务用例的外观

DDD引入repository放在了领域层，一是对应聚合根的概念，二是抽象了数据库访问，，但DDD限界上下文可能不仅限于访问数据库，还可能访问同样属于外部设备的文件、网络与消息队列。为了隔离领域模型与外部设备，同样需要为它们定义抽象的出口端口，这些出口端口该放在哪里呢？如果依然放在领域层，就很难自圆其说。例如，出口端口EventPublisher支持将事件消息发布到消息队列，要将这样的接口放在领域层，就显得不伦不类了。倘若不放在位于内部核心的领域层，就只能放在领域层外部，这又违背了整洁架构思想

从年初就开始温习SOLID原则，原则看似很简单，有些其实就是一句话，但对照这些原则去观看自己的过往代码，还是很多违背这些原则的，诚然，没有完美的实践，但需要保持在走向完美的路上

当然，如果你说天天在CRUD，从没有用到过这些原则，这就是另一个话题了

最近就写了一段很臭的代码，反省一下

1
2
3
4
5
6
7
8
9
10

public AbstractInvoice(InvoiceCode invoiceCode, InvoiceNo invoiceNo, PaperDrewDate paperDrewDate, CheckCode checkCode) {
    this.invoiceCode = invoiceCode;
    this.invoiceNo = invoiceNo;
    this.paperDrewDate = paperDrewDate;
    if (checkCode instanceof VerifyCheckCode) {
        this.checkCode = checkCode.toNormal();
    } else {
        this.checkCode = checkCode;
    }
}

这段代码很简单，业务是发票，一张发票由基本的几个要素组成：发票代码、发票号码、开票时间、检验码、金额

形象点，找个平常普通发票的票样

其次，这是一个抽象类，构建时带有发票几票素，这些InvoiceCode,InvoiceNo,PaperDrewDate,CheckCode都是简单的Primitive Domain(不了解这个概念也没关系，下回分解；简单讲就是业务自包含的基本类型)

完整的抽象类关系

但代码里面用到了instanceof，当用到这个关键字，而且是在抽象实体时，基本上可以断定是抽象的层次不够，
可能违背了LSP

LSP原则很明了：子类可以随时替换父类；这儿用了instanceof，说明有不可替换的成份在

再追看CheckCode的层次

一个简单的校验码，为什么也要抽象成这样？

1
2
3
4
5
6
7
8
9
10
11

public abstract class CheckCode {

    protected String checkCode;

    public CheckCode(String checkCode) {
        this.checkCode = checkCode;
    }
    
    public CheckCode(int length, String checkCode, boolean isNumeric) {
    }
}

校验码有几种形式

1. 标准的20位长度的完整检验码
2. 后6位简短的检验码，发票做验真业务时使用
3. 区块链发票的检验码，5位长度，字母数字组合

因为有三种形态，不同的长度就是不同的类型；验真时只需要简短检验码；查看完整信息时需要完整的检验码

在发票接口中，也有相应的获取行为，也正因为有这种形为，需要在创建发票对象时，把VerifyCheckCode转换成NormalCheckCode

1
2
3
4
5

public interface Invoice {

    public CheckCode getCheckCode();
    
    public String getVerifyCheckCode();

这儿有个疑问，为什么不在构建发票前，把verifyCheckCode转成normalCheckCode，而不是到Invoice的构建内部再转化，那也就没有instanceof的事

但再细想，对于发票来讲，其实只有一个checkCode属性，没有VerifyCheckCode，那只是在请求验真时的一种形态，所以在发票对象中，不应该有verifyCheckCode属性

所以Invoice对象应该是这样

1
2
3
4
5
6
7
8
9
10
11

public interface Invoice {

    public CheckCode getCheckCode();
}

public AbstractInvoice(InvoiceCode invoiceCode, InvoiceNo invoiceNo, PaperDrewDate paperDrewDate, CheckCode checkCode) {
        this.invoiceCode = invoiceCode;
        this.invoiceNo = invoiceNo;
        this.paperDrewDate = paperDrewDate;
        this.checkCode = checkCode;
}

对于primitive domain,CheckCode自包含中应该带有verifyCheckCode

每一种CheckCode都有各自不同的行为

一般通过instanceof判断子类型时，都有不满足LSP的嫌疑；在这个场景中也差不多，但抓住了这一点，重新思考一下，类层次与结构行为可以设计得更合理

接口隔离原则，ISP，Interface Segregation Principle

用于处理胖接口（fat interface）所带来的问题。如果类的接口定义暴露了过多的行为，则说明这个类的接口定义内聚程度不够好

第一种定义: Clients should not beforced to depend upon interfaces that they don’t use.

客户端不应该依赖它不需用的接口

第二种定义：The dependency of oneclass to another one should depend on the smallest possible interface。

类间的依赖关系应该建立在最小的接口上

ISP还是比较简单的，通过行为分离，达到高内聚效果

不遵循ISP

类A依赖接口I中的方法1、方法2、方法3，类B是对类A依赖的实现。类C依赖接口I中的方法1、方法4、方法5，类D是对类C依赖的实现。

对于类B和类D来说，虽然他们都存在着用不到的方法（也就是图中红色字体标记的方法），但由于实现了接口I，所以也必须要实现这些用不到的方法

显然接口I是个胖接口，客户端依赖了他不需要用的接口方法

遵循ISP

将原有的接口I拆分为三个接口，类A不需要用到“方法4”和“方法5”，就可以选择不依赖接口I3

实例

设计一个门接口，它包含了一款自动门所需要的功能，开关，自动关闭等。

但是并不是每个门都有自动关闭的功能，所以timeOut超时这个方法放在该接口中，就会导致所有实现这个接口的子类都会默认的继承了这个方法，哪怕子类中不对这个方法做处理。

把接口拆分成2个，拆分成Door和TimeClient，2个接口，这样Door就只保持原有的基本功能，而timeOut超时的方法则放到TimeClient接口中，这样就可以解决上述中接口臃肿的问题

VS SRP

很多人会觉的接口隔离原则跟之前的单一职责原则很相似，其实不然

其一，单一职责原则原注重的是职责；而接口隔离原则注重对接口依赖的隔离。

其二，单一职责原则主要是约束类，其次才是接口和方法，它针对的是程序中的实现和细节；而接口隔离原则主要约束接口接口，主要针对抽象，针对程序整体框架的构建

在单一职责原则中，一个接口可能有多个方法，提供给多种不同的调用者所调用，但是它们始终完成同一种功能，因此它们符合单一职责原则，却不符合接口隔离原则，因为这个接口存在着多种角色，因此可以拆分成更多的子接口，以供不同的调用者所调用。

比如说，项目中我们通常有一个Web服务管理的类，接口定义中，我们可能会将所有模块的数据调用方法都在接口中进行定义，因为它们都完成的是同一种功能：和服务器进行数据交互；但是对于具体的业务功能模块来说，其他模块的数据调用方法它们从来不会使用，因此不符合接口隔离原则

架构

在一般情况下，任何层次的软件设计如果依赖于不需要的东西，都会是有害。

从源代码层次来说，这亲的依赖关系会导致不必要的重新编译和重新部署

对更高层次的软件架构设计来说，问题也类似

如果D中包含了F不需要的功能，那么这些功能同样也会是S不需要的。对D中这些功能的修改会导致F需要被重新部署，后者又会导致S的重新部署。

更糟糕的是，D中一个无关功能的错误也可能会导致F和S运行出错

TIPS

采用接口隔离原则对接口进行约束时，要注意以下几点：

• 接口尽量小，但是要有限度。对接口进行细化可以提高程序设计灵活性是不挣的事实，但是如果过小，则会造成接口数量过多，使设计复杂化。所以一定要适度。
• 为依赖接口的类定制服务，只暴露给调用的类它需要的方法，它不需要的方法则隐藏起来。只有专注地为一个模块提供定制服务，才能建立最小的依赖关系。
• 提高内聚，减少对外交互。使接口用最少的方法去完成最多的事情。

运用接口隔离原则，一定要适度，接口设计的过大或过小都不好。设计接口的时候，只有多花些时间去思考和筹划，才能准确地实践这一原则

Reference

《整洁架构之道》

Interface Segregation Principle(ISP)–接口隔离原则

究竟什么才是“软件架构”？架构师的工作内容究竟是什么？

架构

“架构”这个词给人的直观感受就充满了权力与神秘感，因此谈论架构总让人有一种正在进行责任重大的决策或者深度技术分析的感觉。毕竟，进阶到软件架构这一层次是我们走技术路线的人的终极目标

应用程序有两个层面需求，第一类是功能性需求；第二类是非功能性需求

架构的重要性就在于非功能需求，这些非功能需求决定一个应用程序在运行时质量，比如可扩展性和可靠性。它们也决定了开发阶段的质量，包括可维护性、可测试性、可扩展性和可部署性。

架构设计的主要目标是支撑软件系统的全生命周期，设计良好的架构可以让系统便于理解、易于修改、方便维护、并且能轻松部署。软件架构的终极目标就是最大化程序员的生产力，同时最小化系统的总运营成本。

软件的系统架构应该为该系统的用例提供支持；软件系统的架构设计图也应该非常明确地凸显该应用程序会有哪些用例

架构设计不是与框架相关的，不应该是基于框架来完成，框架只是一个可用的工具和手段

一个良好的架构设计应该围绕着用例来展开，这样的架构设计可以在脱离框架、工具以及使用环境的情况下完整地描述用例

不管什么样的架构，它们都具有同一个设计目标：按照不同关注点对软件进行切割。也就是这些架构都会将软件切割成不同的层，至少有一层是只包含该软件的业务逻辑的，而用户接口、系统接口则属于其他层

计算机系统的软件架构是构建这个系统所需要的一组架构，包括软件元素、它们之间的关系以及两者的属性

所谓“架构”，是“以组件、组件之间的关系、组件与环境之间的关系为内容的某一系统的基本组织结构，以及指导上述内容设计与演化的原则”。之所以要确定系统的组件、组件关系以及设计与演化的原则，目的是通过不同层面的结构视图来促进团队的交流，为设计与开发提供指导。架构不仅仅是指我们设计产生的输出文档，还包括整个设计分析与讨论的过程，这个过程产生的所有决策、方案都可以视为是架构的一部分

架构这么多定义，怎么描述架构呢？

Phillip Krutchen在他经典的论文《Architectural Blueprints —The 4+1 View Model of Software Architecture》中提出了软件架构的4+1视图

• 逻辑视图：开发人员创建的软件元素。在面向对象的语言中，这些元素是类和包。它们之间的关系是类和包之间的关系，包括继承、关联和依赖。

• 实现视图：构建编译系统的输出。此视图由表示打包代码的模块和组件组成，组件是由一个或多个模块组成的可执行或可部署单元。在JAVA中，模块是JAR文件，组件通常是WAR文件或可执行JAR文件。它们之间的关系包括模块之间的依赖关系以及组件和模块之间的组合关系。

• 进程视图：运行时的组件。每个元素都是一个进程，进程之间的关系代表进程间通信。

• 部署视图：进程如何映射到机器。此视图中的元素由（物理或虚拟）计算机和进程组成。机器之间的关系代表网络。该视图还描述了进程和机器之间的关系。

除了这四个视图以外，4+1中的+1是指场景，它负责把视图串联在一起。每个场景负责描述在一个视图中的多个架构元素如何协作，以完成一个请求。例如，在逻辑视图中的场景，展现了类是如何协作的。同样，在进程视图中的场景，展现了进程是如何协作的

4+1视图是描述应用程序架构的绝佳方式。每一个视图都描述了架构的一个重要侧面。场景把视图中的元素如何协作串联在一起

良好的架构有如下特点：

• 独立于框架
• 要被测试
• 独立于UI
• 独立于数据库
• 独立于任何外部机构

架构师

架构师干什么？画PPT吗？写不写代码？

首先，软件架构师自身需要是程序员，并且必须一直坚持做一线程序员，绝对不要听从那些说应该让软件架构师从代码中解放出来以专心解决高阶问题的伪建议

软件架构师应该是能力最强的一群程序员，他们通常会在自身承接编程任务的同时，逐渐引导整个团队向一个能够最大化生产力的系统设计方向前进

概括一下：

有人讲【优秀程序员的价值,不在于其所掌握的几招屠龙之术,而是在细节中见真著】，那么架构师则不仅要有屠龙刀，还得有绣花针

zk相关文章已经有了三篇
《zookeeper-paxos》、
《zookeeper知识结构》、
《zookeeper知识结构2-zab协议》

但都没有到具体到应用，此篇弥补一下

talk is cheap,show me the code

client

如何使用zk

除了zk提供原生客户端，还有能过编程方式

zkcli

zkcli原生操作指令比较简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

zkcli    连接默认zookeeper服务器

zkcli -server ip:port    连接指定的zookeeper服务器

create -s -e path data [acl]    创建节点，-s表示顺序，-e表示临时，默认是持久节点，acl缺省表示不做任何权限限制

ls path [watch]    显示path下的节点，不递归显示,watch注册监听，命令行可忽视

ls2 path    显示当前节点下的节点和当前节点的属性信息

get path [watch]    获取path的属性信息和数据内容

set path data [version]    更新path的数据内容，version是做类似cas的功能的对应dataversion，命令行可忽略

delete path [version]    删除节点，不能递归删除，只能删除叶子节点

setacl path acl    设置节点acl,例子(scheme:id:password=:perm)-(digest:example:sha-1(base64(pwd))=:cdrwa) create delete read write admin

getacl path    获取path节点的acl

stat path    查看path的属性信息

quit 退出zkcli

ZkClient VS Curator

这两个常用的开源组件

相对zkclient,Curator已经成为Apache的顶级项目,不仅解决了非常底层的细节开发工作，包括连接重连、反复注册Watcher和NodeExistsException异常等,还提供了Zookeeper各种应用场景（Recipe，如共享锁服务、Master选举机制和分布式计算器等）的抽象封装

所以推荐使用curator

应用

主要介绍两种常见情景，一是分布式锁，二是master选举

分布式锁

为什么zk能实现分布式锁？

像redis原理是通过全局key是否存，而zk则是通过其特定的数据结构来实现：利用节点名称的唯一性

ZooKeeper抽象出来的节点结构是一个和unix文件系统类似的小型的树状的目录结构。ZooKeeper机制规定：同一个目录下只能有一个唯一的文件名。例如：我们在Zookeeper目录/jjk目录下创建，两个客户端创建一个名为Lock节点，只有一个能够成功

思路一：持久节点

利用名称唯一性，加锁操作时，只需要所有客户端一起创建/lock节点，只有一个创建成功，成功者获得锁。解锁时，只需删除/lock节点，其余客户端再次进入竞争创建节点，直到所有客户端都获得锁

代码片段

尝试加锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * 尝试加锁,直接创建节点，如果节点创建失败，说明加锁失败
 * @param lockName
 * @return
 */
public boolean tryLock(String lockName) {
    try {
        //创建节点
        String path = cf.create().creatingParentsIfNeeded().withMode(CreateMode.PERSISTENT).forPath(getLockPath(lockName), lockName.getBytes());
       logger.info(Thread.currentThread().getName()+ "try lock  success ,path:"+path+" tid:"+Thread.currentThread().getName());
        return true;
    }catch (KeeperException.NodeExistsException e) {
       logger.info("try lock fail,"+" tid:"+Thread.currentThread().getName());
    }catch (Exception ex) {
        ex.printStackTrace();
    }
    return false;
}

尝试加锁失败后，阻塞等待

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/**
 * 尝试加锁失败后，阻塞等待
 * @param lockName
 * @throws Exception
 */
public void waitForLock(String lockName) throws Exception {
    //监听子节点
    PathChildrenCache pathChildrenCache = new PathChildrenCache(cf, LOCK_PATH, false);
    pathChildrenCache.start(PathChildrenCache.StartMode.BUILD_INITIAL_CACHE);
    pathChildrenCache.getListenable().addListener(new PathChildrenCacheListener() {
        @Override
        public void childEvent(CuratorFramework client, PathChildrenCacheEvent event) throws Exception {
            switch (event.getType()) {
                case CHILD_REMOVED:
                    logger.info("path:" + event.getData().getPath() + " has removed,start to lock:{}",Thread.currentThread().getName());
                    countDownLatch.countDown();
                    break;
                default:
                    //logger.info(" has changeed,{},start to lock:{}",event.getType(),Thread.currentThread().getName());
                    break;
            }
        }
    });
    boolean hasLock = false;
    while(!hasLock) {
        Stat stat = cf.checkExists().forPath(getLockPath(lockName));
        //节点存在,此处与unlock非原子操作，如果在checkExists返回true时刻，成功unlock,那此端无限等待
        if (stat == null) {
            logger.info("waitForLock not exists:{}", Thread.currentThread().getName());
           hasLock = tryLock(lockName);

           if(hasLock) {
               logger.info("waitForLock get lock :{}", Thread.currentThread().getName());
               break;
           }
        } else {
            logger.info("waitForLock exists:{}", Thread.currentThread().getName());
            countDownLatch.await();
        }
    }
}

解锁

1
2
3
4
5
6

public boolean unlock(String lockName) throws Exception {
        logger.info("start unlock:" + lockName + " tid:" + Thread.currentThread().getName());
        cf.delete().forPath(getLockPath(lockName));
        logger.info("end unlock:" + lockName + " tid:" + Thread.currentThread().getName());
    return true;
}

这个方案比较简单，但会出现两个问题：

1. “惊群效应”，所有客户端都是监听这个节点变化，当一端释放锁时，别的端都会抢占
2. 如果加锁成功的client突然崩溃，那么锁无法正常释放，全局进入死锁状态

思路二：临时有序节点

为了应对上面的问题，可以使用临时有序节点：EPHEMERAL_SEQUENTIAL，之前的篇章中说明了临时节点特点，在client与zk断开连接时，临时节点会自动删除

加锁算法：

1. 客户端调用create()方法创建名为“/lock”的节点，需要注意的是，这里节点的创建类型需要设置为EPHEMERAL_SEQUENTIAL
2. 客户端调用getChildren(“lock”)方法来获取所有已经创建的子节点，同时在这个节点上注册上子节点变更通知的Watcher
3. 客户端获取到所有子节点path之后，如果发现自己在步骤1中创建的节点是所有节点中序号最小的，那么就认为这个客户端获得了锁
4. 如果在步骤3中发现自己并非是所有子节点中最小的，说明自己还没有获取到锁，就开始等待，直到下次子节点变更通知的时候，再进行子节点的获取，判断是否获取锁

解锁算法：

• 删除自己创建的那个子节点

代码片段

尝试加锁失败后，阻塞等待

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public void waitForLock(String lockName) throws Exception {
    logger.info("waitForLock {}:{}",beforeNode, Thread.currentThread().getName());
    boolean hasLock = false;
    while(!hasLock) {
       //是不是最小节点
        boolean isMin = isMinNode();
        if (isMin) {//是 则成功获取锁
            logger.info("waitForLock getLock:{}", Thread.currentThread().getName());
            break;
        } else {
            try {
                cf.getData().usingWatcher(new Watcher() {
                    @Override
                    public void process(WatchedEvent event) {
                        switch (event.getType()) {
                            case NodeDeleted:
                                logger.info("path:" + event.getPath() + " has removed,before:{},start to lock:{}", beforeNode, Thread.currentThread().getName());
                                countDownLatch.countDown();
                                break;
                        }
                    }
                }).forPath(beforeNode);
                logger.info("waitForLock waiting:{}", Thread.currentThread().getName());
                countDownLatch.await();
                logger.info("开始抢占:{},{}", Thread.currentThread().getName(), currentNode);
            }catch (KeeperException.NoNodeException e){
                logger.info("waitForLock has delete:{},{}",beforeNode, Thread.currentThread().getName());
            }
        }
    }
}

这个方案解决了思路一中的问题

1. 只监听当前节点的上一个节点，这样就解决了“惊群”现象
2. 临时节点，当连接断开后，就会自动删除，不会出现过期时间问题

完美了吗？

再回看《剖析分布式锁》。zk实现方式完美了吗？

显然示例中没有达到好锁的标准，更完善的实现可以看看curator中的InterProcessLock

单机

此锁高可用了吗？对比一下Redis，哪种方案更完美？

客户端1发生GC停顿的时候，zookeeper检测不到心跳，也是有可能出现多个客户端同时操作共享资源的情形

redis的最新set指令,zk的临时节点两个性质都是一样的，解决了因过期时间问题引起的死锁

有了“续命丸”方案，在单机情况下，redis更完美些，至少不会出现zk临时节点因session超时提前删除问题

集群

在集群下呢？ 线上环境，为了高可用不大会使用单点

如redis的cluster，哨兵模式;但由于Redis的主从复制（replication）是异步的，这可能会出现在数据同步过程中，master宕机，slave来不及同步数据就被选为master，从而数据丢失

1. 客户端1从Master获取了锁
2. Master宕机了，存储锁的key还没有来得及同步到Slave上
3. Slave升级为Master
4. 客户端2从新的Master获取到了对应同一个资源的锁

RedLock算法

为了应对这个情形， redis的作者antirez提出了RedLock算法，步骤如下(该流程出自官方文档)，假设我们有N个master节点(官方文档里将N设置成5，其实大等于3就行)

1. 获取当前时间（单位是毫秒）
2. 轮流用相同的key和随机值在N个节点上请求锁，在这一步里，客户端在每个master上请求锁时，会有一个和总的锁释放时间相比小的多的超时时间。比如如果锁自动释放时间是10秒钟，那每个节点锁请求的超时时间可能是5-50毫秒的范围，这个可以防止一个客户端在某个宕掉的master节点上阻塞过长时间，如果一个master节点不可用了，我们应该尽快尝试下一个master节点
3. 客户端计算第二步中获取锁所花的时间，只有当客户端在大多数master节点上成功获取了锁（在这里是3个），而且总共消耗的时间不超过锁释放时间，这个锁就认为是获取成功了
4. 如果锁获取成功了，那现在锁自动释放时间就是最初的锁释放时间减去之前获取锁所消耗的时间
5. 如果锁获取失败了，不管是因为获取成功的锁不超过一半（N/2+1)还是因为总消耗时间超过了锁释放时间，客户端都会到每个master节点上释放锁，即便是那些他认为没有获取成功的锁

缺陷

比如一下场景，两个客户端client 1和client 2，5个redis节点nodes (A, B, C, D and E)。

1. client 1从A、B、C成功获取锁，从D、E获取锁网络超时
2. 节点C的时钟不准确(如时钟跳跃)，导致锁快速超时(算法第4点)
3. client 2从C、D、E成功获取锁，从A、B获取锁网络超时
4. 这样client 1和client 2都获得了锁

对于步骤2，还有一种情况，比如节点C崩溃重启了，但客户端1在C上加的锁没有持久化下来，丢失了；节点C重启后，client2从C、D、E成功获取锁

对于这两种情况，redis作者antirez给出了两种人为补偿措施

• 一时钟问题，不允许人员修改时间
• 二节点重启，提出延迟重启的概念，即一个节点崩溃后，先不立即重启它，而是等待一段时间再重启，等待的时间大于锁的有效时间。采用这种方式，这个节点在重启前所参与的锁都会过期，它在重启后就不会对现有的锁造成影响

Redlock的问题，最关键的一点在于Redlock需要客户端去保证写入的一致性，后端5个节点完全独立，所有的客户端都得操作这5个节点。如果5个节点有一个leader，客户端只要从leader获取锁，其他节点能同步leader的数据，这样，分区、超时、冲突等问题都不会存在。所以为了保证分布式锁的正确性，我觉得使用强一致性的分布式协调服务能更好的解决问题

而强一致问题，zk可以完成，zk是个CP系统，zk内部机制就保证了各数据的一致性

分布式锁

到此，对分布式锁的实现可以总结一下

zookeeper可靠性比redis强太多，只是效率低了点，如果并发量不是特别大，追求可靠性，首选zookeeper

为了效率，则首选redis实现

总结

除了分布式锁，还有一个常用场景:master选举。在curator中也有相应封装：LeaderSelector；具体实现可以自行阅读源码

参考资料

基于zookeeper的分布式锁

《Is Redlock safe?》

《How to do distributed locking》

curator使用说明

分布式锁实现抉择

聊一聊分布式锁的设计

一本正经的胡说八道

对错自在你心，可能就是个饭后闲扯

所得

以前同事问，什么时候跳槽？或者什么时候会出去看看机会呢？我都会回答做到有所得的时候。有所得，当然不是说拷贝公司几份源码，那可是公司资产，不可误入歧途。但知识是自己的，成长是自己的

一直也是这么践行的，从出校门不懂的书生到能把书本知识灵活运用到一线工作，从毫无经验到开发工业级产品，从职场小白到带队主导开发流程，虽然经历的大多数公司已经倒闭了，但自己是实实在在的成长了。

是的，是所有得再考虑外面机会的，小池塘不能满足成长时，就要去大池塘

前些天跟老同事见面聊游戏开发周期，我问现在立项时还是提议半年开发一款产品吗？同事呵呵两声回答，半年开发一款早就得卷地铺走人了，现在两周就得上线。着实吓了我一跳，原来他们现在是主攻小游戏，依赖完备的微信生态，快速产品，快速变现

去年同事项目出了个爆款，公司整年有近3亿纯利，开发自然奖金不菲，当然也没有想像中那么多

我思考他们的开发模式，直接模仿国外游戏，改头换皮，再稍加修改，上线。大多数产品肯定是上得快，死得也快。如此环境，对技术人员的成长有多少帮助

绝大多数收益进入老板口袋，开发人员一直重复再重复，甚至有些游戏只是改了个名字，最后他们能得到什么？

此类游戏业务简单，公司组织也扁平，尤其服务端，平台提供了各种服务，小游戏前端已经在喊着要干掉服务端的口号，不 管哪个开发岗位，在几年后，当面对新机会时，怎么阐述自己的价值，是抄得更快速？还是因为运气，出了多少爆款？

由他而又思考到自己所谓的大公司，有人评价阿里工程师，说普遍被中间件惯坏了

不是背后说人坏话，只是一种现象，可能是大公司人的普遍问题
，进阿里是大多数技术人的梦想，包括我，但估计此生无缘，能力实在达不到阿里要求

面试造火箭，入职拧螺丝；公司越成熟，基础建设就越完备、基建设施模块化程度越高，工具体验做得越好，平台做得越完善，那么对上层做业务来讲，底层细节也就屏蔽越多

对业务来说本身是件好事，但对业务开发技术人员呢？有些领域技术变化很快，两三年可能迭代了好几轮，在深度、广度上有了质的飞跃，而你该怎么办，削足适履追求新技术吗？

回顾自己技术实力时，脱离了这些基础设施，还有多少生产力？尤其微服务会打散各个业务线，可能一条完整的业务链路都理不清

此时，还能有所得吗？得多少？褪去头顶公司光环，酒桌上的牛还能吹多大？

所思

有人说技术人就像丢在大海里的漂流瓶，努力漂泊，孤傲不羁，却怎么也不能融入大海，装不满自己空空如也的肚腩，因为他们不知道身体倾斜一点，才是最佳姿势，才有最快的装水速度

也许真是远离技术看技术，才有更大的格局

从事游戏开发很多年，一直觉得自己对游戏开发还是有见解的，但好像只是开发阶段的把握，而不是游戏本身的整体把握。

早些年总是抱怨，为什么我们技术这么好，为什么游戏总是死呢？其实考虑面太窄，没想过运营，商务，维护，推广等等事项，手上有把锤子，到处只看到钉子了

对于游戏类型，也很局限，最近看到一个外行人总结游戏类型，特别的汗颜

依据不同的投入类型，我们可以把游戏分成三大类：

1）反应。这类游戏，需要实时观察周围环境，并快速作出操作和应对。最典型的就是各种射击、动作、即时战略类游戏。

2）策略。这类游戏，需要综合考虑各种可能性，对未来作出规划，并安排好下一步行动。典型如各种策略模拟游戏。

3）沉浸。这类游戏，需要代入角色，理解和接受其世界观，阅读、记忆大量剧情，探索故事线。典型就是各种角色扮演游戏。

游戏的玩法可以千奇百怪，类型可以随意组合，但好的游戏，对玩家的要求，基本都不出这三类

这些只是单机玩法，大型网络游戏，还涉及到群体心理等等

在游戏行业打拼多年，尽然没有一个外行总结到位，抽象高度太低太低

技术里的世界不小，但技术外的世界更大

是该放下手中的技术，抬头看看外面的世界

功夫在诗外，也许再回头看技术时，别有一番天

当然千万别一时亢奋放弃技术，远离技术是在追求技术无法再提升格局的时候，跳出来，回头看

是从简入繁完成后，由繁化简的过程中的技法；无法打开一把锁时，不能只盯着锁看，因为钥匙可能在远离锁的地方

那么如何远离技术呢？远离程度呢？也许多读书是个切入口，《关于读书》这篇文章也许对你有所帮助，如果能找到牛人指点更好。

通过《zookeeper知识结构1》了解了zookeeper是什么？为什么使用zookeeper? 以及zookeeper内部数据结构，选举机制

zab定义

ZAB全称ZooKeeper Atomic Broadcast protocol

ZooKeeper原子广播协议，实现了主备模式下的系统架构，保持集群中各个副本之间的数据同步(数据最新，一致性)

原子广播

在具体深入zab之前，先搞明白原子广播

原子性好理解，不管是事务的ACID，还是多线程中，都有这个概念；广播也好理解，像系统中常引入消息队列进行消息广播

但两者合在一起，有点犯晕了，广播怎么需要原子性？哪部分操作不可分割呢？

所有事务请求的处理结果在整个集群中所有机器上的应用情况是一致的,也就是说,要么整个集群所有机器都成功应用了某一个事务, 要么就都没应用.

按照上面的解释，原子性体现在所有机器事务一致性,要么都接受广播，要么都不接受；为了更深入理解，从头开始深入一下这个机制的大致流程

在分布式中，这个机制有很多具体实现，比如2PC,3PC，paxos等等

副本

在这个机制介绍前，需要先介绍下分布式中的副本(Replication)

副本简直是处理故障恢复的的万能钥匙

数据副本的收益：

1. 提升系统可用性，需要挂更多的节点才会导致数据丢失
2. 提升系统性能，多个副本可以同时处理或者交给更快的机器处理

分布式系统采用副本可以获得可扩展性，高性能，可用性，容错性

1. 害怕数据不可用，采用副本吧，多副本能确保数据由于故障丢失的概率大大降低；
2. 计算太慢，采用副本吧，将计算散布到多台机器上；
3. I/O太慢，采用副本吧，将数据cache到local机器上，可以极大的提升吞吐

正常多副本，可以从任何副本请求数据

数据同步

为了多个副本上的数据同步，一般会加一个dispatche,client请求到dispatche上，dispatche会对请求进行排序，并按同样的顺序分发到各个副本，保持各副本数据一致

此时，dispatche成了系统中的单点，不具备高可用，所以会部署多个dispatch

每个dispatche相互通信，并且每个dispatche都可以分发到各个副本；此时就会出现上图中的并发更新一致性问题，类似于《深入浅出事务》中的第二类更新丢失

在并发操作时，应用本身对于数据的先后都是可以接受的，但在各个副本中的数据必须保持一致，也就是下图中的结果都是可以的

也就是讲，各个dispatche得以相同的顺序进行更新副本

顺序同步

解决并发更新不一致问题，思路就是对请求操作进行排序，按顺序执行

数据更新的过程如下：

1. 客户发送操作请求到任意一个节点的分发器上
2. 分发器接收到请求后，将请求广播到其他节点上的分发器，并且这些分发器之间会对所有的并发请求进行排序。最终每个节点的分发器上都会有一份完全一样的请求列表。这个功能通常称作原子广播（Atomic Broadcast） 或者 全局排序广播（Total Order Broadcast)
3. 分发器将列表中的操作请求按照顺序送给本节点的数据副本

在这个模型中，原子广播的逻辑和业务逻辑是分开的。这么做的好处是非常明显的，业务逻辑的实现不再受分布式需求的限制，原子广播的逻辑则不需要考虑业务逻辑的具体需求。独立的原子广播的逻辑可以被重用到很多的分布式的应用上

原型

根据上面的推导，得出一个最简单的原型

dispatche增加一个队列，也可以把它设计成日志文件（顺序追加的文件）或者管道等等，当有请求时，会按顺序存储到队列，但这个队列中的每个位置只能存储一次数据，存储后不能进行更改

请求操作

1. 收到客户端的数据存储请求后，选择一个存储位置。发送数据储存指令给其他的分发器，同时将数据存储到自己的存储队列中
2. 当收到其他分发器发送的存储指令后，将数据存储到自己的存储队列。如果该位置已经存储了数据，则返回失败

• 数据存储指令的内容:[存储位置，数据]
• 存储位置的选择:选择最小的空存储位

并发更新

当两个client分别发到不同到dispatche上请求，两个dispatche相互同步时，出现了不一致，违背了各个队列的每个位置只能存储一次元素，不能更改的原则

锁

对于并发问题，首先想到就是加锁，对于分布式系统怎么加锁呢？

2PC提供了好的思路

借鉴一下2pc，加锁过程如下：

第一步：加锁

1. 接受到请求，选择本地队列位置，并加锁
2. 发送加锁指令到别的dispatche2，dipatche2进行相同位置加锁，并回返lock ack

• 加锁指令：[位置]

第二步：更新

1. 收到所有dispatche都返回lock ack
2. 数据写入队列位置上，并发送存储指令给所有disptache
3. dispatche收到存储指令，把数据写入队列相应位置

死锁

并发考虑的两个问题：安全性与活跃性

dispatche1与dispatche2分别接收到请求，在第一步加锁时，先给自己队列加锁，再发送加锁指令给其它dispatche

此时，就出现死锁：如dispathe1对自身队列位置1加锁，再发送指令给disptache2的队列位置1加锁，但disptache2的队列位置1被自己锁住了，反之disptache1队列位置1也一样，此时双方进入死锁，永远阻塞

优先级锁

有一种策略，就是给锁增加一个优化级

• 每个锁请求都有一个优先级，优先级高的锁请求可以撤销优先级低的锁。
• 如果一个存储指令的锁被撤销了，就不能被执行

如图所示，两个dispatche分别接收到请求，p1 p2是各自锁的优先级，p1高于p2

1. dispatch1接收请求后，自己队列加锁；收到dispatch2的加锁请求，但p2优先级低于p1，所以被阻塞
2. dispatche2自身加锁后，收到dispatche1的加锁请求，由于p1高于p2，dispatche2撤销p2操作，p1成功加锁
3. dispatche1成功在所有dispatche上加锁

优先级：

1. 有先后次序,优先级不能相等
2. 不可重复

比如以dispatche的id作为优先级值，dispatcheId是不同的，也能区分优先级，但这样会出现不平衡，以id大的优先级高，那永远id为大的优先获取锁，加锁成功处理请求

为了更好的均衡各个客户的请求处理，可以采用下面的优先级定义：[数值，dispatcheID]

数值可以由各个dispatche指定，比如所有disptache都原子累加，这样可以保证每个dispathe的均衡，当数值相等时，再比较dispatcheId

节点故障

故障可能发生在每个阶段，一是加锁阶段，二是数据更新阶段；再细节大概有三种情况：

1. 加锁成功，但没有写入数据
2. 部分节点写入了数据
3. 故障dispatche已经写入数据，但没有同步到别的dispatche

加锁成功，没有写入数据

这个很好解决，通过优先级锁，另的节点发起一个更高优先级操作就可以覆盖先前的记录

部分节点写入数据

解决这个问题，需要加强一下更新操作，之前的更新操作，发送存储指令给各个节点，就结束了

现在不单单发送指令，还需要再广播

也就是节点接受到存储指令，如果节点已经有数据写入，则与数据一起返回；这样当所有节点返回加锁成功后，检查是否有数据返回，如果有数据返回，则将数据放入存储指令，发送给所有节点

没有同步别的dispatche

需要增加一个“预存储队列”，预写入机制

当dispatche1发生故障时，其它的dispatche的预存储队列中已经存入了数据。其它节点接管dispatche1时，会先重发预存储队列中的数据到所有dispatche

预写入过程可以保证：如果数据被写入了任意的存储队列，那么所有节点的预存储队列都有这个数据

多数派

上面的广播机制中，加锁以及预写入都需要所有节点返回成功。如果任意一个节点有故障都会失败。在复杂网络环境下，整个系统很脆弱，不能高可用

因此可以改进为半数以上节点成功回复就可以

大多数派机制下，会带来一些更复杂的中间状态，整个过程：

1. 发送加锁指令
2. 收到加锁指令后，检查指定存储位置是否已经加锁，如没有，则返回加锁成功；如被加锁，则比较锁优先级，如果优先级更高，就撤销原有锁，重新加锁返回成功；如果已经预写入数据，则将数据一并返回
3. 当超过半数节点返回加锁成功后，检查是否有数据返回。如果有数据返回，则将优先级最高的数据存入预存储指令。如果没有数据返回，则将自己的数据写入预存储指令。发送预存储指令给所有dispatche,并写入自己的预存储队列
4. 收到预存储指令，将数据写入预存储队列。如果预存储锁被撤销，则返回失败
5. 当超过半数返回预存储成功，刚发送存储指令给所有dispatche，并写入自己的存储队列
6. 当收到存储队列，将数据写入自己存储队列中

ZAB详细

有了上面的原型，理解其它的具体协议就会轻松很多，在具体实现时，都会看到原型中的概念

ZAB协议是为分布式协调服务 Zookeeper 专门设计的一种支持 崩溃恢复 和 原子广播 协议

ZAB协议定义了选举（election）、发现（discovery）、同步（sync）、广播(Broadcast)四个阶段

原型抽象

根据上面的原型，结合zk的源码，梳理一下源码中对应原型的抽象

投票对象

这个对象对应着原型中的存储指令，优先级加锁指令

1
2
3
4
5
6
7

public Vote(long id, long zxid) {
    this.id = id;
    this.zxid = zxid;
    this.electionEpoch = -1;
    this.peerEpoch = -1;
    this.state = ServerState.LOOKING;
}

id：被推举的Leader的SID

zxid：被推举的Leader事务ID

为了保证事务的顺序一致性，zookeeper 采用了递增的事 务 id 号（zxid）来标识事务。

所有的提议（proposal）都在被提出的时候加上了 zxid。

实现中 zxid 是一个 64 位的数字

它高32 位是 epoch（ZAB 协议通过 epoch 编号来区分 Leader 周期变化的策略）用来标识 leader关系是否改变，每次一个 leader 被选出来，它都会有一个新的epoch=（原来的 epoch+1），标识当前属于那个 leader 的统治时期。

低 32 位用于递增计数

可以想象为中国古代的年号，例如万历十五年，万历是epoch，十五年是id

electionEpoch：逻辑时钟，用来判断多个投票是否在同一轮选举周期中，该值在服务端是一个自增序列，每次进入新一轮的投票后，都会对该值进行加1操作

peerEpoch：被推举的Leader的epoch

electionEpoch和peerEpoch的区别在于，electionEpoch记录的选举的轮次，而peerEpoch则指的是当前leader的任期

state：当前服务器的状态

FastLeaderElection

zk默认的选举算法，为什么需要选举可以参照《zookeeper知识结构1》

术语

• 外部投票：特指其他服务器发来的投票。
• 内部投票：服务器自身当前的投票。
• 选举轮次：Zookeeper服务器Leader选举的轮次，即logicalclock
• PK：对内部投票和外部投票进行对比来确定是否需要变更内部投票

electionEpoch和logicalclock的区别在于，electionEpoch指的是发出server的logicalclock，而logicalclock则指的是当前Server所处的选举的轮次

队列

• sendqueue：选票发送队列，用于保存待发送的选票。
• recvqueue：选票接收队列，用于保存接收到的外部投票。
• WorkerReceiver：选票接收器。其会不断地从QuorumCnxManager中获取其他服务器发来的选举消息，并将其转换成一个选票，然后保存到recvqueue中，在选票接收过程中，如果发现该外部选票的选举轮次小于当前服务器的，那么忽略该外部投票，同时立即发送自己的内部投票。
• WorkerSender：选票发送器，不断地从sendqueue中获取待发送的选票，并将其传递到底层QuorumCnxManager中

QuorumCnxManager

ClientCnxn是ZooKeeper客户端中用于处理网络I/O的一个管理器

在Leader选举的过程中也有类似的角色，那就是QuorumCnxManager——每台服务器启动的时候都会启动一个QuorumCnxManager，负责各台服务器之间的底层Leader选举过程中的网络通信

QuorumCnxManager这个类内部维护了一系列的队列，用于保存接收到的、待发送的消息，以及消息的发送器。

除接收队列以外，这里提到的所有队列都有一个共同点——按SID分组形成队列集合，我们以发送队列为例来说明这个分组的概念。

假设集群中除自身外还有4台机器，那么当前服务器就会为这4台服务器分别创建一个发送队列，互不干扰。

• queueSendMap：消息发送队列，用于保存那些待发送的消息。queueSendMap是一个Map，按照SID进行分组，分别为集群中的每台机器分配了一个单独队列，从而保证各台机器之间的消息发送互不影响。
• senderWorkerMap：发送器集合。每个SendWorker消息发送器，都对应一台远程ZooKeeper服务器，负责消息的发送。同样，在sendWorkerMap中，也按照SID进行了分组。
• lastMessageSent：最近发送过的消息。在这个集合中，为每个SID保留最近发送过的一个消息

在SendWorker的具体实现中，有一个细节需要我们注意一下：一旦ZooKeeper发现针对当前远程服务器的消息发送队列为空，那么这个时候就需要从lastMessageSent中取出一个最近发送过的消息来进行再次发送。这个细节的处理主要为了解决这样一类分布式问题：接收方在消息接收前，或者是在接收到消息后服务器挂掉了，导致消息尚未被正确处理。那么如此重复发送是否会导致其他问题呢？当然，这里可以放心的一点是，ZooKeeper能够保证接收方在处理消息的时候，会对重复消息进行正确的处理

lastMessageSent接近原型中的预存储队列

选票过程

• 1.自增选举轮次。Zookeeper规定所有有效的投票都必须在同一轮次中，在开始新一轮投票时，会首先对logicalclock进行自增操作。
• 2.初始化选票。在开始进行新一轮投票之前，每个服务器都会初始化自身的选票，并且在初始化阶段，每台服务器都会将自己推举为Leader
• 3.发送初始化选票。完成选票的初始化后，服务器就会发起第一次投票。Zookeeper会将刚刚初始化好的选票放入sendqueue中，由发送器WorkerSender负责发送出去。
• 4.接收外部投票。每台服务器会不断地从recvqueue队列中获取外部选票。如果服务器发现无法获取到任何外部投票，那么就会立即确认自己是否和集群中其他服务器保持着有效的连接，如果没有连接，则马上建立连接，如果已经建立了连接，则再次发送自己当前的内部投票
• 5.判断选举轮次。在发送完初始化选票之后，接着开始处理外部投票。在处理外部投票时，会根据选举轮次来进行不同的处理。
  • 5.1.外部投票的选举轮次大于内部投票。若服务器自身的选举轮次落后于该外部投票对应服务器的选举轮次，那么就会立即更新自己的选举轮次(logicalclock)，并且清空所有已经收到的投票，然后使用初始化的投票来进行PK以确定是否变更内部投票。最终再将内部投票发送出去。
  • 5.2.外部投票的选举轮次小于内部投票。若服务器接收的外选票的选举轮次落后于自身的选举轮次，那么Zookeeper就会直接忽略该外部投票，不做任何处理，并返回步骤4。
  • 5.3.外部投票的选举轮次等于内部投票。此时可以开始进行选票PK
• 6.选票PK。在进行选票PK时，符合任意一个条件就需要变更投票
  • 6.1.若外部投票中推举的Leader服务器的选举轮次大于内部投票，那么需要变更投票。
  • 6.2.若选举轮次一致，那么就对比两者的ZXID，若外部投票的ZXID大，那么需要变更投票。
  • 6.3.若两者的ZXID一致，那么就对比两者的SID，若外部投票的SID大，那么就需要变更投票。
• 7.变更投票。经过PK后，若确定了外部投票优于内部投票，那么就变更投票，即使用外部投票的选票信息来覆盖内部投票，变更完成后，再次将这个变更后的内部投票发送出去。
• 8.选票归档。无论是否变更了投票，都会将刚刚收到的那份外部投票放入选票集合recvset中进行归档。recvset用于记录当前服务器在本轮次的Leader选举中收到的所有外部投票（按照服务队的SID区别，如{(1, vote1), (2, vote2)…}）。
• 9.统计投票。完成选票归档后，就可以开始统计投票，统计投票是为了统计集群中是否已经有过半的服务器认可了当前的内部投票，如果确定已经有过半服务器认可了该投票，则终止投票。否则返回步骤4
• 10.更新服务器状态。若已经确定可以终止投票，那么就开始更新服务器状态，服务器首选判断当前被过半服务器认可的投票所对应的Leader服务器是否是自己，若是自己，则将自己的服务器状态更新为LEADING，若不是，则根据具体情况来确定自己是FOLLOWING或是OBSERVING。

以上10个步骤就是FastLeaderElection的核心，其中步骤4-9会经过几轮循环，直到有Leader选举产生。

总结

通过对原子广播原型的理解，更容易理解zab，对于paxos也一样

当然zab还有很多的细节，还能再深入，挖出很多知识点。但只看理论终归有些空洞，下一篇实践一下，详述zk版本分布式锁

参考资料

Leader选举

分布式系统

由浅入深理解Paxos协议

之前写过关于zookeeper的一篇文章《zookeeper-paxos》，paxos太难理解了，当时理解了，但现在又忘记了，机械学习果然是不行的

虽然曾经有一篇文章讲阿里不使用zk做服务发现，但大多数公司的分布式架构中基本都能看到zk的身影，而且他躲在里面，你可能看不到他，感受不到他的存在

对于架构体系中的这样一位选手，了解，学习，研究是相当有必要的

ZK是什么

ZooKeeper 是一个分布式的，开放源码的分布式应用程序协调服务，是Google的Chubby 一个开源的实现

ZooKeeper 是集群的管理者，监视着集群中各节点的状态，根据节点提交的反馈进行下 一步合理的操作。最终，将简单易用的接口和功能稳定，性能高效的系统提供给用户

zooKeeper is a centralized service for maintaining configuration information, naming, providing distributed synchronization, and providing group services

这大概描述了Zookeeper的作用，配置管理，名字服务，提供分布式同步以及集群管理

为什么需要ZK

知道了zk的定义，其实跟不知道差不多，还是要追根溯源，看看zk今世因缘，存在的意义

zk的历史很多地方都有介绍，这儿就不赘述了

相对历史，更想知道为什么需要zk？

以前经历的系统，都是使用redis做为服务中心了，不管使用single redis,还是redis cluster，能胜任架构需求，全局命名服务、订阅发布监听服务列表、分布式锁足矣

一度怀疑zk的价值，也阻碍了进一步学习的热情，但存在即合理

设计 ZooKeeper 的目的是为了减轻分布式应用程序所承担的协调任务

还是从ZK的定义追溯它的作用

配置管理

在我们的应用中除了代码外，还有一些就是各种配置。比如数据库连接等

一般我们都是使用配置文件的方式，在代码中引入这些配置文件。但是当我们只有一种配置，只有一台服务器，并且不经常修改的时候，使用配置文件是一个很好的做法，但是如果我们配置非常多，有很多服务器都需要这个配置，而且还可能是动态的话使用配置文件就不是个好主意了。

这个时候往往需要寻找一种集中管理配置的方法，我们在这个集中的地方修改了配置，所有对这个配置感兴趣的都可以获得变更。比如我们可以把配置放在数据库里，然后所有需要配置的服务都去这个数据库读取配置

但是，因为很多服务的正常运行都非常依赖这个配置，所以需要这个集中提供配置服务的服务具备很高的可靠性。

一般我们可以用一个集群来提供这个配置服务，但是用集群提升可靠性，那如何保证配置在集群中的一致性呢？ 这个时候就需要使用一种实现了一致性协议的服务了。Zookeeper就是这种服务，它使用Zab这种一致性协议来提供一致性

名字服务

比如为了通过网络访问一个系统，我们得知道对方的IP地址，但是IP地址对人非常不友好，这个时候我们就需要使用域名来访问。

但是计算机是不能是别域名的。

怎么办呢？

如果我们每台机器里都备有一份域名到IP地址的映射，这个倒是能解决一部分问题，但是如果域名对应的IP发生变化了又该怎么办呢？于是我们有了DNS这个东西。

我们只需要访问一个大家熟知的(known)的点，它就会告诉你这个域名对应的IP是什么。

在我们的应用中也会存在很多这类问题，特别是在我们的服务特别多的时候，如果我们在本地保存服务的地址的时候将非常不方便，但是如果我们只需要访问一个大家都熟知的访问点，这里提供统一的入口，那么维护起来将方便得多了

分布式锁

比如在一个分布式环境中，为了提高可靠性，我们的集群的每台服务器上都部署着同样的服务

但是，一件事情如果集群中的每个服务器都进行的话，那相互之间就要协调，编程起来将非常复杂。而如果我们只让一个服务进行操作，那又存在单点。通常还有一种做法就是使用分布式锁，在某个时刻只让一个服务去干活，当这台服务出问题的时候锁释放，立即fail over到另外的服务

这在很多分布式系统中都是这么做，这种设计有一个更好听的名字叫Leader Election(leader选举)。比如HBase的Master就是采用这种机制。但要注意的是分布式锁跟同一个进程的锁还是有区别的，所以使用的时候要比同一个进程里的锁更谨慎的使用

这儿其实说了两个作用

1. 传统意义的锁，如《剖析分布式锁》，保护对共享资料操作
2. master选举，像JOB，为了高可用，会有多台服务器部署同一套JOB程序，但在运行时，只有一台服务器真正执行业务，此时，需要选择一台服务器，如果这台机器挂了，别的机器需要顶替上来

集群管理

在分布式的集群中，经常会由于各种原因，比如硬件故障，软件故障，网络问题，有些节点会进进出出。有新的节点加入进来，也有老的节点退出集群。这个时候，集群中其他机器需要感知到这种变化，然后根据这种变化做出对应的决策

比如我们是一个分布式存储系统，有一个中央控制节点负责存储的分配，当有新的存储进来的时候我们要根据现在集群目前的状态来分配存储节点

这个时候我们就需要动态感知到集群目前的状态，这也就是注册中心

CAP

分布式系统在设计时，都会考虑一下CAP，在现有理论下，CAP是不能同时满足的，所以需要根据业务场景选择合适的设计要求

CAP定义在《zookeeper-paxos》中有详细说明

ZooKeeper是个CP（一致性+分区容错性）的，即任何时刻对ZooKeeper的访问请求能得到一致的数据结果，同时系统对网络分割具备容错性；但是它不能保证每次服务请求的可用性。也就是在极端环境下，ZooKeeper可能会丢弃一些请求，消费者程序需要重新请求才能获得结果。

ZooKeeper是分布式协调服务，它的职责是保证数据在其管辖下的所有服务之间保持同步、一致；所以就不难理解为什么ZooKeeper被设计成CP而不是AP特性的了

而且， 作为ZooKeeper的核心实现算法Zab，就是解决了分布式系统下数据如何在多个服务之间保持同步问题的

特点

• 顺序一致性：从同一客户端发起的事务请求，最终将会严格地按照顺序被应用到 ZooKeeper 中去。
• 原子性：所有事务请求的处理结果在整个集群中所有机器上的应用情况是一致的，也就是说，要么整个集群中所有的机器都成功应用了某一个事务，要么都没有应用。
• 单一系统映像：无论客户端连到哪一个 ZooKeeper 服务器上，其看到的服务端数据模型都是一致的。
• 可靠性：一旦一次更改请求被应用，更改的结果就会被持久化，直到被下一次更改覆盖。

znode

在谈到分布式的时候，我们通常说的“节点”是指组成集群的每一台机器
然而，在 ZooKeeper 中，“节点”分为两类：

1. 第一类同样是指构成集群的机器，我们称之为机器节点。
2. 第二类则是指数据模型中的数据单元，我们称之为数据节点一ZNode

与Linux文件系统不同的是，Linux文件系统有目录和文件的区别，而Zookeeper的数据节点称为ZNode，ZNode是Zookeeper中数据的最小单元，每个ZNode都可以保存数据，同时还可以挂载子节点，因此构成了一个层次化的命名空间，称为树

• 每一个znode默认能够存储1MB的数据（对于记录状态性质的数据来说，够了）

• 可以使用zkCli命令，登录到zookeeper上，并通过ls、create、delete、sync等命令操作这些znode节点

znode除了名称、数据以外，还有一套属性：zxid

ZooKeeper状态的每一次改变, 都对应着一个递增的Transaction id, 该id称为zxid. 由于zxid的递增性质, 如果zxid1小于zxid2, 那么zxid1肯定先于zxid2发生

创建任意节点, 或者更新任意节点的数据, 或者删除任意节点, 都会导致Zookeeper状态发生改变, 从而导致zxid的值增加

此外，znode还有操作权限。如果我们把以上几类属性细化，又可以得到以下属性的细节：

• czxid：创建节点的事务的zxid
• mzxid：对znode最近修改的zxid
• ctime：以距离时间原点(epoch)的毫秒数表示的znode创建时间
• mtime：以距离时间原点(epoch)的毫秒数表示的znode最近修改时间
• version：znode数据的修改次数
• cversion：znode子节点修改次数
• aversion：znode的ACL修改次数
• ephemeralOwner：如果znode是临时节点，则指示节点所有者的会话ID；如果不是临时节点，则为零。
• dataLength：znode数据长度。
• numChildren：znode子节点个数。

znode是由客户端创建的，它和创建它的客户端的内在联系，决定了它的存在性：

1. PERSISTENT-持久化节点：创建这个节点的客户端在与zookeeper服务的连接断开后，这个节点也不会被删除（除非您使用API强制删除）。
2. PERSISTENT_SEQUENTIAL-持久化顺序编号节点：当客户端请求创建这个节点A后，zookeeper会根据parent-znode的zxid状态，为这个A节点编写一个全目录唯一的编号（这个编号只会一直增长）。当客户端与zookeeper服务的连接断开后，这个节点也不会被删除。
3. EPHEMERAL-临时目录节点：创建这个节点的客户端在与zookeeper服务的连接断开后，这个节点（还有涉及到的子节点）就会被删除。
4. EPHEMERAL_SEQUENTIAL-临时顺序编号目录节点：当客户端请求创建这个节点A后，zookeeper会根据parent-znode的zxid状态，为这个A节点编写一个全目录唯一的编号（这个编号只会一直增长）。当创建这个节点的客户端与zookeeper服务的连接断开后，这个节点被删除。

另外，无论是EPHEMERAL还是EPHEMERAL_SEQUENTIAL节点类型，在zookeeper的client异常终止后，节点也会被删除。

服务的四种状态

服务器具有四种状态，分别是LOOKING,FOLLOWING,LEADING,OBSERVING

• LOOKING
  寻找leader状态
  当前服务器处于该状态时，它会认为当前集群中没有leader，因此需要进入leader选举状态
• FOLLOWING
  跟随者状态
  表示当前服务器的角色是Follower角色
• LEADING
  领导者状态
  表示当前服务器是Leader
• OBSERVING
  观察者状态
  表示当前服务器角色是Observer

角色

最典型集群模式：Master/Slave 模式（主备模式）

在这种模式中，通常 Master 服务器作为主服务器提供写服务，其他的 Slave 服务器从服务器通过异步复制的方式获取 Master 服务器最新的数据提供读服务

zookeeper都是集群形式部署的，而zk服务又分为不同角色来执行不同的任务,ZooKeeper中没有选择传统的 Master/Slave 概念

而是引入了Leader、Follower 和 Observer 三种角色

在区分zk服务器角色之前，需要解释几个概念：

• 事务请求
  在zk中，那些会改变服务器状态的请求称为事务请求（创建节点、更新数据、删除节点、创建会话等等）
• 非事务请求
  从zk读取数据但是不对状态进行任何修改的请求称为非事务请求

领导者Leader

1. 事务请求的唯一调度和处理者，保证集群事务处理的顺序性；
2. 集群内部各服务器的调度者
3. 只有一个

跟随者（Follower）

1. 处理客户端非事务请求，转发事务请求给Leader服务器
2. 参与事务请求Proposal的投票
3. 参与Leader选举的投票

观察者（Observer):

1. Follower 和 Observer 唯一的区别在于 Observer 机器不参与 Leader 的选举过程
2. 也不参与写操作的“过半写成功”策略，因此 Observer
3. 机器可以在不影响写性能的情况下提升集群的读性能

数据流

1. 在Client向Follwer发出一个写的请求
2. Follwer把请求发送给Leader
3. Leader接收到以后开始发起投票并通知Follwer进行投票
4. Follwer把投票结果发送给Leader
5. Leader将结果汇总后如果需要写入，则开始写入同时把写入操作通知给Leader，然后commit;
6. Follwer把请求结果返回给Client

leader选举

选举(election)是分布式系统实践中常见的问题，通过打破节点间的对等关系，选得的leader(或叫master、coordinator)有助于实现事务原子性、提升决议效率

为什么需要选举

集群本身有很多种类，如tomcat集群，集群里面每一台机器是对等的，所以其自身不存在leader之说

另外一类，如fastDfs，其依赖于独特的HASH算法，建立文件名和路径之间的映射关系，写操作都是通过namenode分发到各台datanode之上，算法保证了文件名的独一无二，也不存在leader的说法

还有memcache集群，集群里面的机器之间彼此无心跳，通过一致性hash尽可能将key值的存储分散化，降低单一memcahe服务器down机的影响。

还有一类是主从复制，主节点负责写，从节点负责读，提高读的性能。从节点定期通过心跳与主节点沟通，一旦主节点挂掉了，从节点马上接手主节点的任务

对于分布式应用，难以避免出现网络的抖动。比如，
主节点暂时失去响应，如瞬时负载过高，网络拥塞或者其他原因导致主节点暂时失去响应，超过响应超时时间，这个时候从节点启动，承担起leader的职责，但是原先的主节点又恢复了服务。这个时候，如果没有选举机制（不能仅仅自己宣告自己是leader，还要广而告之，让其他服务器或者客户端知道自己是leader），有可能会存在两个leader节点，导致集群发生混乱

上图示例一下此类场景

主节点出现问题，那就是单点故障

传统方式是采用一个备用节点，这个备用节点定期给当前主节点发送ping包，主节点收到ping包以后向备用节点发送回复Ack，当备用节点收到回复的时候就会认为当前主节点还活着，让他继续提供服务

当主节点挂了，这时候备用节点收不到回复了，然后他就认为主节点挂了接替他成为主节点如下图

但是这种方式就是有一个隐患，就是网络问题，来看一网络问题会造成什么后果，如下图

也就是说我们的主节点的并没有挂，只是在回复的时候网络发生故障，这样我们的备用节点同样收不到回复，就会认为主节点挂了，然后备用节点将他的Master实例启动起来，

这样我们的分布式系统当中就有了两个主节点也就是—双Master，

出现Master以后我们的从节点就会将它所做的事一部分汇报给了主节点，一部分汇报给了从节点，这样服务就全乱了

选举

场景

在哪些场景下需要进行leader选举

1. 服务器初始化启动
2. 服务器运行期间无法和Leader保持连接

初始化时

若进行Leader选举，则至少需要两台机器，这里选取3台机器组成的服务器集群为例。在集群初始化阶段，当有一台服务器Server1启动时，其单独无法进行和完成Leader选举，当第二台服务器Server2启动时，此时两台机器可以相互通信，每台机器都试图找到Leader，于是进入Leader选举过程。选举过程如下

• 1.每个Server发出一个投票。由于是初始情况，Server1和Server2都会将自己作为Leader服务器来进行投票，每次投票会包含所推举的服务器的myid和ZXID，使用(myid, ZXID)来表示，此时Server1的投票为(1, 0)，Server2的投票为(2, 0)，然后各自将这个投票发给集群中其他机器。
• 2.接受来自各个服务器的投票。集群的每个服务器收到投票后，首先判断该投票的有效性，如检查是否是本轮投票、是否来自LOOKING状态的服务器
• 3.处理投票。针对每一个投票，服务器都需要将别人的投票和自己的投票进行PK，PK规则如下
  • 3.1.优先检查ZXID。ZXID比较大的服务器优先作为Leader
  • 3.2.如果ZXID相同，那么就比较myid。myid较大的服务器作为Leader服务器

对于Server1而言，它的投票是(1, 0)，接收Server2的投票为(2, 0)，首先会比较两者的ZXID，均为0，再比较myid，此时Server2的myid最大，于是更新自己的投票为(2, 0)，然后重新投票，对于Server2而言，其无须更新自己的投票，只是再次向集群中所有机器发出上一次投票信息即可。

• 4.统计投票。每次投票后，服务器都会统计投票信息，判断是否已经有过半机器接受到相同的投票信息，对于Server1、Server2而言，都统计出集群中已经有两台机器接受了(2, 0)的投票信息，此时便认为已经选出了Leader。
• 5.改变服务器状态。一旦确定了Leader，每个服务器就会更新自己的状态，如果是Follower，那么就变更为FOLLOWING，如果是Leader，就变更为LEADING。

Leader挂掉

在Zookeeper运行期间，Leader与非Leader服务器各司其职，即便当有非Leader服务器宕机或新加入，此时也不会影响Leader，但是一旦Leader服务器挂了，那么整个集群将暂停对外服务，进入新一轮Leader选举，其过程和启动时期的Leader选举过程基本一致。假设正在运行的有Server1、Server2、Server3三台服务器，当前Leader是Server2，若某一时刻Leader挂了，此时便开始Leader选举。选举过程如下

• 1.变更状态。Leader挂后，余下的非Observer服务器都会讲自己的服务器状态变更为LOOKING，然后开始进入Leader选举过程
• 2.每个Server会发出一个投票。在运行期间，每个服务器上的ZXID可能不同，此时假定Server1的ZXID为123，Server3的ZXID为122；在第一轮投票中，Server1和Server3都会投自己，产生投票(1, 123)，(3, 122)，然后各自将投票发送给集群中所有机器。
• 3.接收来自各个服务器的投票。与启动时过程相同。
• 4.处理投票。与启动时过程相同，此时，Server1将会成为Leader。
• 5.统计投票。与启动时过程相同。
• 6.改变服务器的状态。与启动时过程相同

过程

理想状态

1. 在第一轮中，按照“我最牛逼，我怕谁”的原则，每个节点都推荐它自己为集群的leader节点
2. 按照我们假设的理想条件，节点S1首先收到了S2发送来的推荐者“2”，节点S1发现“2”要比它之前推荐的“1”（也就是它自己）牛。根据谁牛推荐谁的原则，“S1”清空自己的票箱，重新选举“2”（注意，此时“S1”的新票箱中已经有两票选举“2”了，一票是它自己，另外一票是”S2”，并且所有节点都是Looking状态）
3. 同样的事情发生在“S2”身上：”S2”收到了”S3”发过来的推荐信息，发现“3”这个被推举者比之前自己推举的“2”要牛，于是也清空自己的票箱，发起一轮新的投票，此时“S2”选举“3”。依次类推”S3”、”S4”
4. 这里要注意S5这个节点，在第一轮接受到了来源于“S1”——“S4”的推举者（一定注意，每一次接受信息，都会广播一次“我坚持推举的人”），发现“还是推荐的5最牛”，于是“我继续推举S5吧”
5. 以上这个过程在整个理想的网络环境上一直持续。到了第四轮，“S1”收到了“S2”发送来的推举者“5”，发现“5”要比当前“S1”推荐的“4”要牛。所以“S1”清空了自己的票箱，重新推举“5”（发送给其他所有节点）
6. 关键的第五轮来了，我们再重复一下，经过之前的选举，现在“S2”——“S5”都已经推举“5”为Leader了，而且都处于第四轮。这时他们收到了”S1”发来的新的“第五轮”投票，于是都和之前一样，做相同的一件事：清空自己的票箱，重新向其他所有节点广播自己的第五轮投票“5”
7. 于是，节点X，收到了大于N / 2 +１的选举“5”的投票，且都是第五轮投票。这样每个节点就都知道了自己的角色。，选举结束。所有将成为Follower状态的节点，向将要成为Leader的节点发起最后一次“工作是否正常”的询问。得到肯定的ack后，整个集群的工作状态就确认了

非理想状态

过程中出现了宕机、网络延迟、网络物理层断开等情况

在第三轮的选举过程后，“S1”,“S2”两个节点就断开了，他们的投票信息根本没有发送出去

• “S3”收到了“S4”,“S5”发来的投票信息，这时“S3”的票箱处于第3轮，并且发现了占大多数的投票结果：大家选举“S5”为Leader节点
• 同样的事情也发生在“S4”身上。这样“S3”,“S4”两个节点率先知道了投票结果，在最后一次询问Leader节点是否能正常工作，并得到了肯定的ACK之后，“S3”,“S4”两个节点变成了Follower状态
• 之后，无论“S3”,“S4”两个节点收到了任何节点的投票信息，都直接向源节点反馈投票结果，不会再进行投票了。
• 在投票完成后，“S1”,“S2”重新连入后，虽然他们发起了投票，但是不会再收到投票反馈了。直接根据“S3”或者“S4”发来的结果状态，变成Follower状态

总结

此篇zookeeper的基础内容基本都包含了

了解这些基本已经入门

下一篇学习其中最核心的zab协议，理解原子性广播概念，以及zab的实现过程

参考资料

面试问题，请说明zookeeper的选举机制

zookeeper选举机制

Zookeeper的Leader选举

再起航系列,一枚互联网菜鸟的成长历程

春风三月，却是很多职场人的混沌时节

总结性文章，让人难以落笔。可能观察生活、体察自己不够细心；也许是成长缓慢，后知后觉；更可能本身就是平庸，普通人平平淡淡，没有什么轰烈可期的事情。但不管多难，终需落笔，无论什么原因，总得回顾总结

来到互联网行业已经两年，在这个时间节点，可能再次处于混沌

在第一年里，从好奇，新鲜，无知，疑惑 到 熟悉，充足；再到第二年，可能就是重复，机械，麻木，厌烦了。

在刚换行时，一切都是新鲜，好奇的。经过一年时间的积累，对业务已经熟悉，能够应对各种业务需求，并能很好地实践业务场景中的技术栈，自己的能力圈在扩大，给人一种很充实的感觉

慢慢地，从刚开始还能对技术栈的细节，深度保持一颗期待之心，陷入了各种业务需求中，毕竟是要解决问题体现价值的，不能仅仅学习新鲜事物，这也是前辈们常讲的不要抱着进大公司学习技术的心态，热爱学习的人在哪儿都能学习，并且学好

你也是这么被洗脑的，因此你熟悉了各种业务场景，处理各样的业务咨询以及各环境的故障，帮上下游解决问题，开始重复生活，机械操作，厌烦了，总会厌烦，也有能力厌烦，毕竟你支撑了团队，混熟了业务线上的同事，老油条诞生了，大公司的螺丝钉也铸成了

这些感受都是来自外界的刺激，似乎是常理的周期反应，此时需要一丝保持平静，进步的心，都会向外寻找答案，寻求机会。一切都得向外扩张

但不管如何向外，都会落空，不踏实，终需回归自我，向内而问。不忘初心，方得始终

从工作之初，有一种思想一直占据内心，那就是跟随团队，公司成长，是最夯实，也是最快的成长试。奈何，在实现中，几任老东家都走向了末路，而我也付之东流。尤其这次，完全换了行业，一切从零开始，命也，运也？

以前厌倦了项目总是失败，总是从头开始，总想着能有一个成功的项目，不停地迭代，走向完美。这一次终于满足了，就一个项目不停地迭代，让你迭代个够。每一次迭代，历史包袱特别大，想想都替命运着急，过去走在创新的路上，嫌弃没有积累，现在迭代，又抱怨历史包袱了，人真难伺候

混沌期总是迷茫，没有方向。牛人总有规划，人生规划。普通人总是在寻找方向，选择方向，而又没有方向

在《再起航三转行互联网》中，提到程序员分为两类：技术型和产品型

技术型，一直在路上，只要没有脱离技术型公司，这永远在路上，技术人不可能，也不能丢弃技术。不管老酒装新瓶，还是新酒装老瓶，都是保持与技术的距离。但也得认清自己，不可能做到技术大牛，技术领跑者。智商，经历沉淀都已经让我无法走上这条路

产品型，但你能跨越三十五岁魔咒吗？体力，精力方面是得向年轻人低头的。

那前途在何方？哪片土地是你希望的田野？

管理领导？但现在不在其位置，考虑学习太多理论，都是形而上学。终归要落实到形而下学上

路在何方呢？

何时拨开云雾，走出混沌！

可能需要未来的你给出答案

现在可以没有答案，甚至说未来也没有答案，但行动不能停止，思考更不能停止

从第二年的开始，已经开始关注速度《再起航二成长速度》，第一年得以业务为核心，了解熟悉业务，把手头工作处理好。第二年就得把在第一年关注好奇的技术进行深入研究了，所以开始以组件为单位，一个一个了解学习，以微服务为基架，深入每一个环节

是的，来大公司不是学习的，老板聘用你，不是让你来学习的，但自己得知道，学习一刻都不能停，到大公司，的确不是学习的，在哪儿都能学习，主要是有一个场景，一个能更加深入层次学习的场景，好比之前的《剖析分布式锁》，在一般公司错误的写法，准确的说，不严谨的实现也能胜任，但更大业务量时，能不能胜任，需要思考，更多的时候，需要一个场景告诉你，你当下的完美，可能是个大大的残次品

现在不管是外部大环境，还是公司内部小环境，都不理想，尤其公司现在的体量，是不需要我的陪伴成长的，所以前方还有别的路，创业别想，成熟条件完全没有，那只能去一家与自己相匹配的公司，一起成长

公司不能大，也不能小。中型有成长的公司，核心业务部门，深入业务；或者基础架构，让面试造火箭，名副其实

可能现在格局太小，总是以技术为一切；此篇只是总结当前的一种状态，不抱怨，不迷信，何时开悟走出混沌，尽人事，知天命，一切随缘

从第一篇《算法概要》开始，到此篇已经经历了将近四个月时间，常见的基础排序已经温习完成

内外排序

内部排序：待排序记录存放在计算机随机存储器中（说简单点，就是内存）进行的排序过程

外部排序：待排序记录的数量很大，以致于内存不能一次容纳全部记录，所以在排序过程中需要对外存进行访问的排序过程

衡量效率

内部排序：比较次数，也就是时间复杂度

外部排序：IO次数，也就是读写外存的次数

IO对排序的影响可以阅读《深入浅出索引》体会

算法

详细介绍

算法渣-排序-冒泡

冒泡排序，应该是很多人会且只会的算法；两两比较交换

为了减小比较与交换的次数，通过双向比较(鸡尾酒排序)、设定是否交换位实现

算法渣-排序-快速排序

快速排序，相对冒泡又改进了，都是交换，但引入了分治思想

算法渣-排序-插入

插入排序，像打牌时，整理牌一样，通过比较、移动来达到排序

算法渣-排序-希尔

希尔，相对插入做了改进，不是一步一步的移动，而是大步大步的移动

算法渣-排序-选择

选择，类似插入的反向操作；插入排序是边读边排，每当读入一个新的数时，目前的数组一定是排好序的。而选择排序不同，它必须是读完所有的数据之后才能开始排序的

算法渣-排序-堆排序

堆排序，借助堆数据结构，构造堆结构，选取堆顶元素，不再需要遍历所有元素选择

算法渣-排序-归并排序

归并排序，也是分治思想，但与快速有些区别；归并排序是由下向上的，先处理子数组然后再合并。而快速排序正好相反，它的过程是由上向下的，先分出两个子区间，再对子区间进行排序

算法渣-排序-基数排序

算法渣-排序-桶排序

算法渣-排序-计数排序

线性排序算法,非基于比较的排序算法，性能很高，但都有限制才能达到线性排序的效果

场景

对于排序算法选择，不能单从时间复杂上看，简单算法都是O(n^2),就不考虑，只选择改进算法

插入排序 vs 快速排序 vs 归并排序

由下图可以看出，在输入规模小于100时，插入排序要好于归并和快速排序。在输入规模小于200时，插入排序优于归并排序。规模在30以下时，插入排序效率要比快速排序高50%以上，规模在50以下时，插入排序比归并排序效率高90%以上

改进算法

在数据量大时，使用改进算法

1. 就时间性能而言， 希尔排序、快速排序、树形选择排序、堆排序和归并排序都是较为先进的排序方法。耗时远小于O(N^2)级别的算法。
2. 先进算法之中，快排的效率是最高的。 但其缺点十分明显：在待排序列基本有序的情况下，会蜕化成起泡排序，时间复杂度接近 O(N^2)。
3. 希尔排序的性能让人有点意外，这种增量插入排序的高效性完全说明了：在基本有序序列中，直接插入排序绝对能达到令人吃惊的效率。但是希尔排序对增量的选择标准依然没有较为满意的答案，要知道增量的选取直接影响排序的效率。
4. 归并排序的效率非常不错，在数据规模较大的情况下，它比希尔排序和堆排序都要好。
5. 堆排序在数据规模较小的情况下还是表现不错的，但是随着规模的增大，时间代价也开始和上面两种排序拉开的距离。

总结

总的来说，并不存在“最佳”的排序算法。必须针对待排序列自身的特点来选择“良好”的算法。下面有一些指导性的意见：

1. 数据规模很小，而且待排序列基本有序的情况下，选择直接插入排序绝对是上策。不要小看它O(N^2)级别
2. 数据规模不是很大，完全可以使用内存空间。而且待排序列杂乱无序(越乱越开心)，快排永远是不错的选择，当然付出log(N)的额外空间是值得的。
3. 海量级别的数据，必须按块存放在外存(磁盘)中。此时的归并排序是一个比较优秀的算法

试题

【京东】假设你只有100Mb的内存，需要对1Gb的数据进行排序，最合适的算法是（ ）

A. 归并排序　　B. 插入排序　　C. 快速排序　　D. 冒泡排序

根据题目，我们可以知道，我们现有的内存限制使得我们无法把数据一次性加载到内存中，所以我们只能先加载一部分数据，对其排序后存入磁盘中。然后再加载一些数据，把它们“合并”到已排序的数据集中去，重复这个过程直到排序完成，显然最能胜任这个工作的是归并排序。

【2016阿里巴巴校招笔试题】现有1GB数据进行排序，计算资源只有1GB内存可用，下列排序方法中最可能出现性能问题的是（ ）

A. 堆排序　　B. 插入排序　　C. 归并排序　　D. 快速排序　　E. 选择排序　　F. 冒泡排序

根据题目的描述，我们能够很明确的知道这道题考察我们的是原地排序的概念，这里我们只需要选择非原地排序的占用额外空间最大的算法，显然答案是”C. 归并排序”。

【2015阿里巴巴研发工程师笔试题】个数约为50K的数列需要进行从小到大排序，数列特征是基本逆序(多数数字从大大小，个别乱序)，以下哪种排序算法在事先不了解数列特征的情况下性能最优

A. 冒泡排序　　B. 改进冒泡排序　　C. 选择排序　　D. 快速排序　　E. 堆排序　　F.插入排序

根据题目中的描述，首先我们可以排除A、B、C，因为它们的时间复杂度都是O(n^2)。接下来我们看下D选项，我们前面提到过，快速排序在最坏情况下的时间复杂度会退化至O(n^2)，F选项的插入排序在逆序数很大时性能也很差（O(n^2)）。而堆排序在最坏情况下的复杂度也为O(logn)，所以这里我们应该选择堆排序

参考资料

基于比较的内部排序总结

常见比较排序算法的耗时测试