正文

ZooKeeper 很流行，有个基本的疑问：

• ZooKeeper 是用来做什么的？
• 之前没有ZK，为什么会诞生 ZK？

OK，解答一下上面的疑问：（下面是凭直觉说的）

• ZooKeeper 是用于简化分布式应用开发的，对开发者屏蔽一些分布式应用开发过程中的底层细节
• ZooKeeper 对外暴露简单的 API，用于支持分布式应用开发
• ZooKeeper 在提供上述功能的同时，其还是一个 高性能、高可用、高可靠的分布式集群

上面说这么多，总结一下，ZK 能解决分布式应用开发的问题，ZK 能很好的解决问题。到这一步，疑问就更多了：

1. 分布式应用开发，有哪些常见问题？ZK 是如何屏蔽这些底层细节的？
2. ZooKeeper 对外暴露了那些 API？这些 API 如何支持分布式应用开发的？这些 API 还能简化吗？API 的语义性怎么样？
3. ZooKeeper 自身是一个高性能、高可用、高可靠的分布式集群，那有个简单的问题：

• 高性能是指什么？ZooKeeper 为了达到高性能，做了哪些工作？
• 高可用同上
• 高可靠同上

Note：本篇 wiki 就是为了解决上述第一个疑问的。（其他疑问会在其他 blog 中逐步解答）

为什么有 ZooKeeper

一个应用程序，涉及多个进程协作时，业务逻辑代码中混杂有大量复杂的进程协作逻辑。

上述多进程协作逻辑，有 2 个特点：

• 处理复杂
• 处理逻辑可重用

因此，考虑将多进程协作的共性问题拎出，作为基础设施，让 RD 更加专注业务逻辑开发，即：

ZooKeeper 就是上述多进程协作基础服务的一种。

ZooKeeper 的特点

ZooKeeper 有几个简单特点：

• ZooKeeper 的 API：从 文件系统 API 得到的启发，提供简单的 API
• ZooKeeper 运行在专用服务器上，跟业务逻辑分离，保证了高容错性和可扩展性

ZooKeeper 是存储设施，但特别注意

• ZK上存储的数据聚焦为：协作数据（元数据），而不是应用数据，应用数据有自己的存储方案，例如 HDFS 等
• ZK 本质上，可以看作一种特殊的 FS

特别说明：

应用数据和元数据，由于使用场景不同，对一致性和持久性的要求有差异， 因此，架构设计、数据治理过程中，应将 2 类数据独立看待、独立存储。

ZooKeeper 的使命

ZK 要解决的核心问题：

ZK 目标：简化分布式应用开发中，多进程协作问题。为分布式应用，提供高效、可靠的分布式协调服务（基础服务），例如：

• 统一的命名服务
• 分布式锁
• 进程崩溃检测
• Leader 选举
• 配置管理：配置变更时，及时下发到各个 Client。

一个简单的问题：多进程的协作是什么？尼玛呀，有完没完，啥问题你都有，面对这个掉咋天的脑壳，还是回答一下。

多进程协作，整体分为 2 类：

1. 协作：多进程需要一同处理某些事情，一些进程采取行动是的其他进程能够正常工作，例如：主从结构，M 向 S 分配任务，S 才会执行，否则 S 就保持空闲状态
2. 竞争：两个进程不能同时工作，一个进程必须等待另个进程执行完毕，例如：主从结构，M 节点失效后，很多 S 都想成为 M，这时，就需要互斥锁，只有第一个获得锁的 S 成为 M

特别说明：

1. 不跨网络协作：多进程，可以在同一台物理主机上，同步原语很方便(比如？管道、共享内存、消息队列、信号量)
2. 跨网络协作：多进程，分布在不同的物理主机上，ZK 关注这一类

跨网络多进程协作，进程通信，基本思路有 2 个：

1. 消息机制：通过网络，直接信息交换，多消息传递算法，实现同步原语
2. 共享存储：利用外部共享存储，实现多进程协作，要求共享存储提供有序访问，ZK 采用这种方式

真实系统中，跨网络通信，有几个共性问题：

1. 消息延迟：由于网络原因，后发送先到达
2. 处理器性能：由于系统调度原因，消息到达后，延迟处理
3. 时钟偏移：不同物理主机，时钟发生偏移

ZK 精心设计用于屏蔽上述 3 个共性问题，使得这些问题在应用服务层面完全透明化。

ZooKeeper 特性

ZooKeeper 解决的本质问题

分布式系统的一致性问题：

1. 消息传递：延迟性，先发送的消息，不一定先到达；
2. 消息传递：丢失性，发送的消息，可能丢失；
3. 节点崩溃：分布式系统内，任何一个节点都可能崩溃；

在这种情况下，如何保证数据的一致性？

1. 提案投票：基于投票策略，2PC
2. 选举投票：基于投票策略，投出优先级最高的节点（包含最新数据的节点）

Paxos 目标：解决分布式一致性问题，提高分布式系统容错性的一致性算法。

Paxos 本质：基于消息传递的高度容错的一致性算法

ZooKeeper 定位

ZooKeeper 是：

1. 分布式协调服务
2. 高效、可靠
3. 方便应用程序，聚焦业务逻辑开发，而不需要过多关注分布式进程间协作细节

ZooKeeper 不直接暴露原语，而是，暴露一部分调用方法组成的 API，类似文件系统的 API，支持应用程序实现自己的原语。

ZooKeeper 特性

ZooKeeper 可以保证如下分布式一致性特性：

• 顺序一致性：同一个 Client 发起的事务请求，严格按照发起顺序执行
• 原子性：事务请求，要么应用到所有节点，要么一个节点都没有应用
• 单一视图：Client 无论连接到哪个节点，看到的服务端数据都是一致的（Note：不准确，其实是最终一致性）
• 可靠性：事务一旦执行成功，状态永久保留
• 实时性：事务一旦执行成功，Client 并不能立即看到最新数据，但 ZooKeeper 保证最终一致性

ZooKeeper 设计目标

ZooKeeper 致力于提供高性能、高可用、顺序一致性的分布式协调服务，保证数据最终一致性。

目标一：高性能（简单的数据模型）

1. 采用树形结构组织数据节点；
2. 全量数据节点，都存储在内存中；
3. Follower 和 Observer 直接处理非事务请求；

目标二：高可用（构建集群）

1. 半数以上机器存活，服务就能正常运行
2. 自动进行 Leader 选举

目标三：顺序一致性（事务操作的顺序）

1. 每个事务请求，都会转发给 Leader 处理
2. 每个事务，会分配全局唯一的递增id（zxid，64位：epoch + 自增 id）

目标四：最终一致性

1. 通过提议投票方式，保证事务提交的可靠性
2. 提议投票方式，只能保证 Client 收到事务提交成功后，半数以上节点能够看到最新数据

ZooKeeper 出现之前

ZK 出现之前，分布式系统常用两种方式，实现多进程协作：

1. 分布式锁管理器
2. 分布式数据库

ZK 更专注于进程协作，而不提供任何锁接口和通用的存储数据接口。（疑问：ZK 也可以提供啊，我们不使用就行了）

应用服务器，常见的 2 种需求：

1. Master-Slave Leader 选举：要求提供Master节点选举功能
2. 进程响应跟踪 崩溃检测：要求提供进程存活状态的跟踪
3. 分布式锁：互斥排它锁

ZK 为上述 2 种策略提供了基础 API。

ZooKeeper 不适用的场景：

1. 海量数据存储：ZK 本质是特殊的 FS，但 ZK 用于存储元数据，需要单独存储应用数据

总结

面试难免让人焦虑不安。经历过的人都懂的。但是如果你提前预测面试官要问你的问题并想出得体的回答方式，就会容易很多。

此外，都说“面试造火箭，工作拧螺丝”，那对于准备面试的朋友，你只需懂一个字：刷！

给我刷刷刷刷，使劲儿刷刷刷刷刷！今天既是来谈面试的，那就必须得来整点面试真题，这不花了我整28天，做了份“Java一线大厂高岗面试题解析合集：JAVA基础-中级-高级面试+SSM框架+分布式+性能调优+微服务+并发编程+网络+设计模式+数据结构与算法等”

资料领取方式：点击这里免费下载

且除了单纯的刷题，也得需准备一本【JAVA进阶核心知识手册】：JVM、JAVA集合、JAVA多线程并发、JAVA基础、Spring 原理、微服务、Netty与RPC、网络、日志、Zookeeper、Kafka、RabbitMQ、Hbase、MongoDB、Cassandra、设计模式、负载均衡、数据库、一致性算法、JAVA算法、数据结构、加密算法、分布式缓存、Hadoop、Spark、Storm、YARN、机器学习、云计算，用来查漏补缺最好不过。

VM、JAVA集合、JAVA多线程并发、JAVA基础、Spring 原理、微服务、Netty与RPC、网络、日志、Zookeeper、Kafka、RabbitMQ、Hbase、MongoDB、Cassandra、设计模式、负载均衡、数据库、一致性算法、JAVA算法、数据结构、加密算法、分布式缓存、Hadoop、Spark、Storm、YARN、机器学习、云计算，用来查漏补缺最好不过。

前言

这个主要是说一下比较有意思的API，关于哈希集合方面的使用，这个主要是有时候在比赛的时候，直接拿过来用的话会方便很多。

TreeSet

这个呢是一个集合，首先说一下特点，这个玩意呢，首先他是一个集合，通过我们定义或者默认的hash函数，能够具备集合的数学性质。同样的，我们还可以设置一个比较器实现有序的存储。并且查找的时间复杂度大概在 logn ，还是相当不错的，在一些实在是想不到的题目里面合理地使用api可以事半功倍，就比如先前介绍的java大数问题是吧，当然使用这个的时候，不一定是最优解，不过抗住大部分的测试案例应该还是可以滴。

基础数据类型

这里的话要分两种使用方式，一个是基础数据类型的，一个是自己定义的复杂类型，或者使用的复杂类型的。对于基础数据类型我们直接add即可，对于复杂的，我们必须实现比较器。

    public static void test1(){
        TreeSet<Integer> set = new TreeSet<>();
        set.add(2);
        set.add(1);
        set.add(9);
        for (Integer integer : set) {
            System.out.println(integer);
        }
        System.out.println(set.contains(9));
    }
    

可以看到添加是无序的，但是输出是有序的。

这个就是最基本的使用，但是这个显然还不够。
请看接下来的操作。

    public static void test1(){
        TreeSet<Integer> set = new TreeSet<>();
        set.add(2);
        set.add(1);
        set.add(9);
        for (Integer integer : set) {
            System.out.println(integer);
        }
        System.out.println(set.contains(9));

        System.out.println("最小的是："+set.first());
        System.out.println("最大的是："+set.last());
        System.out.println("删除最小的元素:"+set.pollFirst());
        System.out.println("删除最大的元素:"+set.pollLast());
        System.out.println("删除最下的元素后剩下");
        for (Integer integer : set) {
            System.out.println(integer);
        }
        System.out.println("重新添加元素");
        set.add(2);
        set.add(1);
        set.add(9);
        for (Integer integer : set) {
            System.out.println(integer);
        }
        System.out.println("在集合当中<=7最近的元素是："+set.floor(7));
        System.out.println("在集合当中>=7最近的元素是："+set.ceiling(7));

        set.remove(1);
        set.remove(9);
        System.out.println("删除1，9之后剩下的元素");
        for (Integer integer : set) {
            System.out.println(integer);
        }

    }

结果如下：

复杂数据类型

关于复杂数据类型的操作其实，咱们只需要实现一个比较器即可。

下面是我们定义的数据类型

class Node {
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int x=0;
    public int y=0;

    @Override
    public String toString() {
        return "Node{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

之后我们实现一个比较器

class NodeCompere implements Comparator<Node> {

    @Override
    public int compare(Node o1, Node o2) {
        return (o1.x - o2.x);
    }
}

之后使用

    public static void test2(){
        TreeSet<Node> set = new TreeSet<>(new NodeCompere());
        set.add(new Node(1,1));
        set.add(new Node(3,1));
        set.add(new Node(2,1));
        for (Node node : set) {
            System.out.println(node);
        }
    }
    
}

同样的：

    public static void test2(){
        TreeSet<Node> set = new TreeSet<>(new NodeCompere());
        set.add(new Node(1,1));
        set.add(new Node(3,1));
        set.add(new Node(2,1));
        for (Node node : set) {
            System.out.println(node);
        }
        System.out.println("最下的元素是："+set.first());
        Node node = new Node(5, 1);
        System.out.println("在set当中<=node的最近的节点是："+set.floor(node));
    }
    
}

这里的话比较的规则也确实是你定义的比较器

小技巧

除了上面的方式我们可以实现集合有序外，事实上我们还可以直接使用链表来实现set接口来实现有序的集合输出。
例如这道蓝桥杯的题目

试题 历届真题 修改数组【第十届】【省赛】【A组】

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　给定一个长度为 N 的数组 A = [A₁, A₂, · · · AN]，数组中有可能有重复出现的整数。
　　现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改
　　A₂, A₃, · · · , AN。
　　当修改 Ai 时，小明会检查 Ai 是否在 A₁ ∼ Ai−₁ 中出现过。如果出现过，则小明会给 Ai 加上 1 ；如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直到 Ai 没有在
　　A₁ ∼ Ai−₁ 中出现过。
　　当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。现在给定初始的 A 数组，请你计算出最终的 A 数组。
输入格式
　　第一行包含一个整数 N。
　　第二行包含 N 个整数 A₁, A₂, · · · , AN 。
输出格式
　　输出 N 个整数，依次是最终的 A₁, A₂, · · · , AN。
样例输入
5
2 1 1 3 4
样例输出
2 1 3 4 5
评测用例规模与约定
　　对于 80% 的评测用例，1 ≤ N ≤ 10000。
　　对于所有评测用例，1 ≤ N ≤ 100000，1 ≤ Ai ≤ 1000000。

我们可以直接这样

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Set<Integer> integers = new LinkedHashSet<>();
        Scanner scanner = new Scanner(System.in);
        int length = scanner.nextInt();
        for(int i=0;i<length;i++){
            int value = scanner.nextInt();
            while (integers.contains(value)){
                value++;
            }
            integers.add(value);
        }

        Iterator<Integer> iterator = integers.iterator();
        while (iterator.hasNext()){
            System.out.print(iterator.next()+" ");
        }
    }
}

当然这种方式并不能很好地通过数据集，只能拿到80分。不过有时候，没必要苛求完美，竞赛注意的还是效率和分值。没必要为了20的提升丢掉大分。

TreeMap

这个也同样重要，有时候，我们的往往会带有键值对去比较。当然这里其实也是完全可以通过复合数据类型，来代替 key - value的形式，不过这里也同样说一下。

这样的好处其实是在刚刚的例子里面,我们是通过 Node 的 x 来做比较的。实际上你可以选择直接把 x 当中key，其余部分变为value。

同样的这里也分对于基础类型和复合类型的操作，并且我们这里的比较主要是正对key的比较。

基础类型

这个基础类型与那个TreeSet类似，就不说了。

这里咱们主要说说复合类型。

复合类型

    public static void test3(){
        TreeMap<Node,Integer> map = new TreeMap<>(new NodeCompere());
        map.put(new Node(1,1),1);
        map.put(new Node(3,1),2);
        map.put(new Node(2,1),3);
        Node node = new Node(5, 1);
        System.out.println("在map当中<=node的最近的节点的key是："+map.floorKey(node));
        System.out.println("在map当中>=node的最近的节点的key是："+map.ceilingKey(node));
    }
    
}

你其实可以发现，我们用法其实完全是和TreeSet类似的，只不过我们在对应的方法后面加上了 key 这个后缀。

演示代码（完整）

OK，以上就是全部。底层实现那必然是红黑树，平衡树。

import java.util.Comparator;
import java.util.TreeMap;
import java.util.TreeSet;

public class TreeMapTest {

    public static void main(String[] args) {
        test3();
    }


    public static void test1(){
        TreeSet<Integer> set = new TreeSet<>();
        set.add(2);
        set.add(1);
        set.add(9);
        for (Integer integer : set) {
            System.out.println(integer);
        }
        System.out.println(set.contains(9));

        System.out.println("最小的是："+set.first());
        System.out.println("最大的是："+set.last());
        System.out.println("删除最小的元素:"+set.pollFirst());
        System.out.println("删除最大的元素:"+set.pollLast());
        System.out.println("删除最下的元素后剩下");
        for (Integer integer : set) {
            System.out.println(integer);
        }
        System.out.println("重新添加元素");
        set.add(2);
        set.add(1);
        set.add(9);
        for (Integer integer : set) {
            System.out.println(integer);
        }
        System.out.println("在集合当中<=7最近的元素是："+set.floor(7));
        System.out.println("在集合当中>=7最近的元素是："+set.ceiling(7));

        set.remove(1);
        set.remove(9);
        System.out.println("删除1，9之后剩下的元素");
        for (Integer integer : set) {
            System.out.println(integer);
        }

    }

    public static void test2(){
        TreeSet<Node> set = new TreeSet<>(new NodeCompere());
        set.add(new Node(1,1));
        set.add(new Node(3,1));
        set.add(new Node(2,1));
        for (Node node : set) {
            System.out.println(node);
        }
        System.out.println("最下的元素是："+set.first());
        Node node = new Node(5, 1);
        System.out.println("在set当中<=node的最近的节点是："+set.floor(node));
    }

    public static void test3(){
        TreeMap<Node,Integer> map = new TreeMap<>(new NodeCompere());
        map.put(new Node(1,1),1);
        map.put(new Node(3,1),2);
        map.put(new Node(2,1),3);
        Node node = new Node(5, 1);
        System.out.println("在map当中<=node的最近的节点的key是："+map.floorKey(node));
        System.out.println("在map当中>=node的最近的节点的key是："+map.ceilingKey(node));
    }
    
}







class Node {
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int x=0;
    public int y=0;

    @Override
    public String toString() {
        return "Node{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

class NodeCompere implements Comparator<Node> {

    @Override
    public int compare(Node o1, Node o2) {
        return (o1.x - o2.x);
    }
}

有序集合

List

ArrayList

ArrayList集合底层采用了数组这种数据结构。
ArrayList集合是非线程安全的。

LinkedList

LinkedList集合底层采用了双向链表数据结构。

Vector

vector集合底层采用了数组这种数据结构
vector集合是线程安全的。
vector所有的方法都有synchronized关键字修饰，所以线程安全，但是效率较低，现在保证线程安全有别的方案，所有Vector使用较少。

Set

HashSet

实际上HashSet集合在new的时候，底层实际上new了一个HashMap集合，向HashSet集合中存储元素，实际上是存储到HashMap集合中了，HashMap集合是一个哈希表数据结构

TreeSet

TreeSet 集合底层实际是TreeMap。new TreeSet集合的时候，底层实际上new了一个TreeMap集合。往TreeMap集合中放数据的时候，实际上是将数据放在TreeMap集合中，
TreeMap集合底层采用了二叉树数据结构。

参考文献

java8在线AIP