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

架构

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

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

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

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

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

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

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

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

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

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

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

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)，所以这里我们应该选择堆排序

参考资料

基于比较的内部排序总结

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

背景

图片分库存储时，每一张图片都可以定位到特定的服务器

hash

上图中，假设我们查找的是”a.png”，由于有4台服务器（排除从库），因此公式为hash(a.png) % 4 = 2 ，可知定位到了第2号服务器，这样的话就不会遍历所有的服务器，大大提升了性能！

一切都运行正常，再考虑如下的两种情况；

1. 一个 cache 服务器 m down 掉了（在实际应用中必须要考虑这种情况），这样所有映射到 cache m 的对象都会失效，怎么办，需要把 cache m 从 cache 中移除，这时候 cache 是 N-1 台，映射公式变成了 hash(object)%(N-1) ；
2. 由于访问加重，需要添加 cache ，这时候 cache 是 N+1 台，映射公式变成了 hash(object)%(N+1) ；

1 和 2 意味着什么？

这意味着突然之间几乎所有cache 都失效了。缓存雪崩，这是一场灾难

一致性hash

有什么方法可以改变这个状况呢，这就是 consistent hashing

比如有{N0, N1, N2}三个节点，陆续有多个资源要分配到这三个节点上，如何尽可能均匀的分配到这些节点上

算法

一致性哈希算法的思路为：先构造出一个长度为2^32 整数环，根据N0-3的节点名称的hash值（分布为[0,2^32 -1]）放到这个环上

整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32 -1，也就是说0点左侧的第一个点代表2^32 -1， 0和2^32 -1在零点中方向重合，我们把这个由2^32个点组成的圆环称为Hash环

下一步将各个服务器使用Hash进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设四台服务器使用ip地址哈希后在环空间的位置如下：

接下来使用如下算法定位数据访问到相应服务器：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器！

例如我们有Object A、Object B、Object C、Object D四个数据对象，经过哈希计算后，在环空间上的位置如下：

根据一致性Hash算法，数据A会被定为到Node A上，B被定为到Node B上，C被定为到Node C上，D被定为到Node D上

容错性

如果一个节点宕机了，会引起系统故障吗？

如上图，Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般的，在一致性Hash算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响

扩展性

如果在系统中增加一台服务器Node X

此时对象Object A、B、D不受影响，只有对象C需要重定位到新的Node X ！一般的，在一致性Hash算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响

综上所述，一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

数据倾斜

一致性Hash算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台服务器上）问题，例如系统中只有两台服务器，其环分布如下：

此时必然造成大量数据集中到Node A上，而只有极少量会定位到Node B上

然而，这又会造成一个“雪崩”的情况，即A节点由于承担了B节点的数据，所以A节点的负载会变高，A节点很容易也宕机，这样依次下去，这样造成整个集群都挂了

虚拟节点

计算机的任何问题都可以通过增加一个虚拟层来解决

解决上述数据倾斜问题，也可能通过使用虚拟层的手段：将每台物理缓存服务器虚拟为一组虚拟缓存服务器，将虚拟服务器的hash值放置在hash环上，Key在环上先找到虚拟服务器节点，再得到物理服务器的信息

例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点：

同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题

那么在实践中，一台物理服务器虚拟为多少个虚拟服务器节点合适呢？太多会影响性能，太少又会导致负载不均衡，一般说来，经验值是150，当然根据集群规模和负载均衡的精度需求，这个值应该根据具体情况具体对待

实现

判定哈希算法好坏的四个定义：

1. 平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件
2. 单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区
3. 分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性
4. 负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷

在具体实现时，主要考虑点选择适合的数据结构构造hash环

此数据结构的特点：插入与删除性能、快速找到特定元素的下一位

常见算法结构可以有回顾：

《一篇解决排序算法》

《树结构概述》

从时间复杂度方面选择，使用平衡二叉树数据结构，可以使得查找的时间复杂度降低为O(logN)

使用java，以TreeMap为例，TreeMap本身还提供了一个tailMap(K fromKey)方法，支持从红黑树中查找比fromKey大的值的集合，但并不需要遍历整个数据结构

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
42
43
44

import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash<T> {

 private final HashFunction hashFunction;
 private final int numberOfReplicas;
 private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();

 public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
     Collection<T> nodes) {
   this.hashFunction = hashFunction;
   this.numberOfReplicas = numberOfReplicas;

   for (T node : nodes) {
     add(node);
   }
 }

 public void add(T node) {
   for (int i = 0; i < numberOfReplicas; i++) {
     circle.put(hashFunction.hash(node.toString() + i), node);
   }
 }

 public void remove(T node) {
   for (int i = 0; i < numberOfReplicas; i++) {
     circle.remove(hashFunction.hash(node.toString() + i));
   }
 }

 public T get(Object key) {
   if (circle.isEmpty()) {
     return null;
   }
   int hash = hashFunction.hash(key);
   if (!circle.containsKey(hash)) {
     SortedMap<Integer, T> tailMap = circle.tailMap(hash);
     hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
   }
   return circle.get(hash);
 }
}

dubbo实现

理解完理论，再扒一下工业级产品的运用，dubbo负载均衡策略之一ConsistentHashLoadBalance

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

private final TreeMap<Long, Invoker<T>> virtualInvokers;

ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
    this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
    this.identityHashCode = identityHashCode;
    URL url = invokers.get(0).getUrl();
    this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);
    String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, "hash.arguments", "0"));
    argumentIndex = new int[index.length];
    for (int i = 0; i < index.length; i++) {
        argumentIndex[i] = Integer.parseInt(index[i]);
    }
    for (Invoker<T> invoker : invokers) {
        String address = invoker.getUrl().getAddress();
        for (int i = 0; i < replicaNumber / 4; i++) {
            byte[] digest = md5(address + i);
            for (int h = 0; h < 4; h++) {
                long m = hash(digest, h);
                virtualInvokers.put(m, invoker);
            }
        }
    }
}

整体思想是一样的，虚拟节点+TreeMap,但实现得更精致，使用MD5加密KEY，更加平衡性，整体的思路解释：

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

//对所有节点，生成nCopies个虚拟结点  
for(Node node : nodes) {  
    //每四个虚拟结点为一组，为什么这样？下面会说到  
    for(int i=0; i<nCopies / 4; i++) {  
        //getKeyForNode方法为这组虚拟结点得到惟一名称  
        byte[] digest=HashAlgorithm.computeMd5(getKeyForNode(node, i));  
    /** Md5是一个16字节长度的数组，将16字节的数组每四个字节一组，分别对应一个虚拟结点，这就是为什么上面把虚拟结点四个划分一组的原因*/  
        for(int h=0;h<4;h++) {  
          //对于每四个字节，组成一个long值数值，做为这个虚拟节点的在环中的惟一key
          //结果转换为long类，这是因为生成的结果是一个32位数，若用int保存可能会产生负数。而一致性hash生成的逻辑环其hashCode的范围是在 0 - MAX_VALUE之间。因此为正整数，所以这里要强制转换为long类型，避免出现负数。
            Long k = ((long)(digest[3+h*4]&0xFF) << 24)  
                | ((long)(digest[2+h*4]&0xFF) << 16)  
                | ((long)(digest[1+h*4]&0xFF) << 8)  
                | (digest[h*4]&0xFF);  
            allNodes.put(k, node);  
        }  
    }  
}

总结

QA

为什么hash一致性的数据空间范围是2^32次方？

这个问题有两种答案，一是技术限制、一是实际场景：

1. 因为，java中int的最大值是2^31-1最小值是-2^31,2^32刚好是无符号整形的最大值
2. 因为一致性hash算法是来做服务器的负载均衡，而服务器的IP地址是32位，所以是2^32-1次方的数值空间

进一步追尾基础，为什么java中int的最大值是2^31-1最小值是-2^31？

因为，int的最大值最小值范围设定是因为一个int占4个字节，一个字节占8位，二进制中刚好是32位

根据算法特性，一致性hash是最好的选择吗？

下一篇介绍另一种实现google maglev hashing算法

参考资料

《大型网站技术架构》

对一致性Hash算法，Java代码实现的深入研究

为什么hash环是32位

没有一身好内功，招式再多都是空;算法绝对是防身必备，面试时更是不可或缺；跟着算法渣一起从零学算法

线性排序

常见的三种以线性时间运行的算法：计数排序、基数排序和桶排序

需要注意的是线性排序算法是非基于比较的排序算法，都有使用限制才能达到线性排序的效果

线性排序是个神奇的算法，比基数排序及桶排序神奇得多

定义

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法

算法

计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上

首先需要三个数组，第一个数组记录A要排序的数列大小为n，第二个数组B要记录比某个数小的其他数字的个数所以第二个数组的大小应当为K（数列中最大数的大小），第三个数组C为记录排序好了的数列的数组，大小应当为n。

接着需要确定数组最大值并确定B数组的大小。并对每个数由小到大的记录数列中每个数的出现次数。因为是有小到大通过出现次数可以通过前面的所有数的出现次数来确定比这个数小的数的个数，从而确定其位置

假定20个随机整数的值，也就是第一个数组A：

9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9 ，7，9

数组A中最大数为10，数组B需要0~10索引

比如第一个整数是9，那么数组下标为9的元素加1：

第二个整数是3，那么数组下标为3的元素加1：

最终，数列遍历完毕时，数组的状态如下：

数组每一个下标位置的值，代表了数列中对应整数出现的次数。

有了这个“统计结果”，排序就很简单了。直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：

0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10

实现

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

/**
 * 计数排序
 * @param array
 */
public static void countSort(int []array){
    //最大最小数
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for ( int a:array) {
        if(min > a) {
            min = a;
        }
        if(max < a) {
            max = a;
        }
    }

    //数组索引数量,统计数组计数
    // max-min 主要是考虑到像[90,99,93,95]不是从很小数开始的数组排序，减小空间消耗
    int indexCount = max - min + 1;
    System.err.println("统计数组长度"+indexCount);
    int []countArray = new int[indexCount];

    for (int i=0;i<array.length;i++){
        System.err.println(array[i]-min);
        countArray[array[i]-min]++;
    }
    System.err.println("countArray:"+Arrays.toString(countArray));

    //排好序的数组
    int [] sortArray = new int[array.length];
    int index = 0;
    for (int i=0;i<indexCount;i++) {
        for (int j=0;j<countArray[i];j++){
            sortArray[index++] = min + i;
        }
    }
    //输出就是有序
    System.err.println(Arrays.toString(sortArray));
}

改进

上面的实现为什么要改进，主要是当两个元素相同时，算法的稳定性问题

改进之前，数组B存放的是元素出现的次数

改进之后，会引入一个新数组(也可以共用数组B)，存放的是元素的位置号(这个纯粹是个人理解，之前数组B是存放元素出现的次数，新数组存放每一个元素都加上前面所有元素出现次数之和，当找到对应排序数组元素时，新数组元素就是位置号)

语言比较空洞，直接来个示例(转自小灰程序员)

将数组arr中的数据当作是学生的成绩，要求不但要按照顺序从低到高排序，成绩相同时，按原有顺序显示：

统计数组从第二个元素开始，每一个元素都加上前面所有元素之和

第一步，我们遍历成绩表最后一行的小绿：

小绿是95分，我们找到countArray下标是5的元素，值是4，代表小绿的成绩排名位置在第4位。

同时，我们给countArray下标是5的元素值减1，从4变成3,，代表着下次再遇到95分的成绩时，最终排名是第3。

第二步，我们遍历成绩表倒数第二行的小白：

小白是94分，我们找到countArray下标是4的元素，值是2，代表小白的成绩排名位置在第2位。

同时，我们给countArray下标是4的元素值减1，从2变成1,，代表着下次再遇到94分的成绩时（实际上已经遇不到了），最终排名是第1。

第三步，我们遍历成绩表倒数第三行的小红：

小红是95分，我们找到countArray下标是5的元素，值是3（最初是4，减1变成了3），代表小红的成绩排名位置在第3位。

同时，我们给countArray下标是5的元素值减1，从3变成2,，代表着下次再遇到95分的成绩时（实际上已经遇不到了），最终排名是第2。

这样一来，同样是95分的小红和小绿就能够清楚地排出顺序了，也正因此，优化版本的计数排序属于稳定排序。

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
42
43
44
45
46
47

/**
 * 稳定计数排序
 * @param array
 */
public static void countSort1(int []array) {
    //最大最小数
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for ( int a:array) {
        if(min > a) {
            min = a;
        }
        if(max < a) {
            max = a;
        }
    }

    //数组索引数量,统计数组计数
    // max-min 主要是考虑到像[90,99,93,95]不是从很小数开始的数组排序，减小空间消耗
    int indexCount = max - min + 1;
    System.err.println("统计数组长度"+indexCount);
    int []countArray = new int[indexCount];

    for (int i=0;i<array.length;i++){
        System.err.println(array[i]-min);
        countArray[array[i]-min]++;
    }
    System.err.println("countArray:"+Arrays.toString(countArray));
    //位置数组
    int []pointArray = new int[indexCount];

    int sum =0;
    for (int i = 0;i<indexCount;i++){
        sum += countArray[i];
        pointArray[i] = sum;
    }
    System.err.println("pointArray:"+Arrays.toString(pointArray));
    System.err.println("aaaaaArray:"+Arrays.toString(array));
    //排好序的数组
    int [] sortArray = new int[array.length];
    for (int i=array.length-1;i>=0;i--) {
            sortArray[pointArray[array[i]-min] -1 ] = array[i];
            pointArray[array[i]-min]--;
    }
    //输出就是有序
    System.err.println(Arrays.toString(sortArray));
}

总结

复杂度

假设array元素有N个，取值范围是M。

时间复杂度：3N(计算最大最小数、计数、排好序的数组) + M(位置数组)，去掉系数，时间复杂度是O(N+M)

空间复杂度：只考虑统计数组，那就是M

局限性

1.当数列最大最小值差距过大时，并不适用计数排序。

比如给定20个随机整数，范围在0到1亿之间，这时候如果使用计数排序，需要创建长度1亿的数组。不但严重浪费空间，而且时间复杂度也随之升高。

2.当数列元素不是整数，并不适用计数排序。

如果数列中的元素都是小数，比如25.213，或是0.00000001这样子，则无法创建对应的统计数组。这样显然无法进行计数排序。

引申阅读

算法渣-排序-基数排序

算法渣-排序-桶排序

参考资料

漫画：什么是计数排序

1. 为什么需要限流
2. 如何限流

限流主要就是考虑这两点

为什么需要限流

之前已经介绍了熔断，降级，为什么还需要一个限流呢？是不是多此一举呢？

先来个结论：

熔断是为了防止雪崩，明哲保身；而限流则是在已有条件下，最大限制发挥系统效能

根据《熔断机制》可以知道，熔断有三种状态，[熔断关闭],[半熔断],[熔断开启]三种状态，如果系统压力过大，一个服务就会在三种状态来回切换

会出现一种情况，就像一辆开在崎岖山路上的法拉利，不管车的性能多好，都需要不停的加速减速

要想速度达到最佳，就得让车开在一条笔直的高速公路上

系统就是一条河，服务就像行驶在河里的船，岸的两边，一边是熔断，另一边就是限流；一个保障系统安全，一个保持最大限度运转，让系统达到高可用

如何限流

限流如何实施？

1. 量化限流阀值
2. 确定限流策略、算法
3. 被限制流量的处理

限流阀值，这个其实就是通过系统压力测试来确定

这个工作其实在系统开发之初就需要有初步的估量，涉及到业务规模，增长速度，架构选择等等，根据现有资源及其服务能力，给出上限值

在《计数器算法》中已经说明了几种限流算法：固定窗口、滑动窗口、漏桶、令牌桶

有人总结为【两窗两桶】，很形象

固定窗口：临界问题，一旦流量波动，计数器提前计满，剩余时间都会被限流

滑动窗口：固定窗口的「固定周期」已经很小，那么使用滑动窗口也就没有意义，虽然大大减小临界问题，但总归需要预估一个窗口量，很难把握，过小引起性能和资源损耗

漏桶：不管进来多少量，出去的速率是恒定的，“出口”速度固定；当桶容量满时，就会被限流

令牌桶：“进口”速度固定；只要令牌的生成速度大于等于请求被处理的速度,系统就能正常处理

有了限流策略，那制定在服务端还是客户端呢？

从效果上讲，肯定是客户端，限制越靠入口，系统就越安全，可以防止不必要的无效流量进入服务端系统

你也可能想到对网络资源的浪费，但一般各个服务都是在同一IDC机房，因此这点不必考虑

但成本相对在服务端过高，放在客户端，客户端的数量与扩张速度也是动态的，无法评估，对每个端的限流阀值分配与下发都很复杂

因此一般都是在服务端进行限流

至于被限制的流量如何处理？大多数情况是直接抛弃，在系统之初，就有了对流量预判，从设计到资源准备都很充足，会有合理的限流阀值；如果有突发流量，可能配合监控及时增加机器，横向扩展

总结

限流与熔断，一个让系统保持最大活跃性，一个保障安全，两者技术手段有重叠，但意义完全不同，所以两者都是微服务中不可少的两个服务治理手段