上一篇有人跟我说比较深奥和抽象，确实，我写这个不是按照循序渐进的写法写的，而是先写那本OREILLY书最不清楚的部分，然后再写次不清楚的……到最后会覆盖zk的绝大多数特性，这时候会再给出一个阅读次序的建议。

    这篇来说说有关znode的一切，比较容易理解，也很容易通过zkCli.sh来实验。






分层名字空间




    上图是ZooKeeper的分层名字空间的示意图，可见这种结构很像典型的文件系统结构：以/分割各元素的一种路径，ZooKeeper名字空间的每个节点都是以这样一个路径来标识的。这样的节点统一称为znode。




Znode


    然而，ZooKeeper的名字空间和文件系统仍有着显著的差别。文件系统典型地有目录和文件，目录可包含其他目录或文件，文件则实际存储数据。而znode既可以有其他子znode，又可以存放数据（严格说是必须存放数据，真没有的话得给个“”），因此znode可以看做是目录和文件的合体。znode被用来存储Byte级或KB级的数据，如状态信息、配置信息、位置信息等，因此znode可存放数据量的最大值默认被设为1MB，请注意，该值不仅计算数据的Byte数，所有子节点的名字也要折算成Byte数计入，因此znode的子节点数也不是无限的。改大这个参数可以存储更多数据或包含更多子znode，但我非常不建议这样做，因为这与ZooKeeper的设计目的相悖，只有数据足够小，才能保证ZooKeeper的高读取性能。如果要存储大量数据，有的是其他解决方案。
    除了数据外，znode还管理了其他一些元数据，存储在stat对象中：
版本号：znode的数据每次更新时，该版本号递增。当客户端请求该znode时，数据和版本号会一起发回。另外，当znode重建时版本号会被重置，这似乎很自然，但很多时候这是巨坑的来源，比如：客户端执行了’set /test “testdata” 1’，即指定版本1写/test节点，之后该znode被删除重建，数据默认置为“”，版本号还是1，此时客户端请求时虽然该版本号仍然存在，但已经是错误的数据了。
ACL：即Access Control List，用来限定哪些账号可以操作该znode。ZooKeeper内置了4种ACL模式，第1种是any，即不鉴权；第2种是super，即不受任何ACL约束的管理员模式；第3种是digest，使用用户名和密码进行认证；第4种是SASL，通常使用Kerberos协议来认证，但Kerberos也是个大坑，并且对性能也有一定影响。
时间戳：其实就是zxid，存储该znode创建或修改时的时间戳，用于缓存验证或协调更新等。


    理解了这些就可以做点操作了，所有zkCli.sh的命令如下，主要掌握ls，get，set，create，delete几个就够玩了（应该明白为何zkCli下没有cd这样的命令）：
ZooKeeper -server host:port cmd args 
        connect host:port 
        get path [watch] 
        ls path [watch] 
        set path data [version] 
        rmr path 
        delquota [-n|-b] path 
        quit  
        printwatches on|off 
        create [-s] [-e] path data acl 
        stat path [watch] 
        close  
        ls2 path [watch] 
        history  
        listquota path 
        setAcl path acl 
        getAcl path 
        sync path 
        redo cmdno 
        addauth scheme auth 
        delete path [version] 

        setquota -n|-b val path 




Znode的四种类型


    持久节点/临时节点：持久节点只能用delete来删除，通常用来保存应用的持久化数据，比如主从模式下的任务分派情况，这种数据不应该由于主节点的崩溃而丢失。临时节点则顾名思义，除了客户端主动删除该节点时会消失外，创建该znode的客户端断开连接时该节点也会消失，因此它常用来检测会话的有效性，例如主从模式下的主节点注册一个znode，当该主节点崩溃或断开时，该znode会立即消失，于是应用可以检测到该故障并重新选举主节点，这种用法极为常见比如kafka。另外，临时节点不允许有子节点。
    有序节点：znode还可以被设置为有序节点，当这样的节点被创建时，一个会自动递增的序号会加到路径之后，比如客户端创建一个有序znode并指定路径为/tasks/task，则第一个创建的节点是/tasks/task-0000000001，该节点消亡后再创建这样的节点会产生/tasks/task-0000000002，以此类推。有序znode提供了创建具有唯一命名的znode的方式。
    这两种类型互相结合后就会产生znode的四种类型：持久的，临时的，持久有序的，临时有序的。




监视和通知


    我们知道，访问ZooKeeper的基本方式是使用API，很多场景我们需要访问一个znode，如果使用轮询的方式，不仅不能实时知晓变更（取决于轮询间隔），更恶劣的是会大大增加ZooKeeper的负载。比较好的方式是，对该znode设置一个监视（watch），当某些事件发生时触发一个通知（notification）。注意监视点是一次性的，如果通知被触发后还需要继续监视该znode，则需要设置一个新的watch。
    ZooKeeper异步通知设置watch的客户端。但是ZooKeeper能够保证在znode的变更生效之后才会异步地通知客户端，然后客户端才能够看到znode的数据变更。由于网络延迟，多个客户端可能会在不同的时间看到znode数据的变更，但是看到变更的顺序是保证有序的。
    Znode可以设置两类watch，一个是Data Watches（该znode的数据变更导致触发watch事件），另一个是Child Watches（该znode的孩子节点发生变更导致触发watch事件）。API和watch间的关系如下表：

Java API


Data Watches


Child Watches


getData


设置






exists


设置






setData


触发






create


触发






getChildren






设置


create某znode的子节点






触发


delete


触发


触发
如删除的znode有父节点，其父节点上也触发



    当某个znode的变化可触发监视点时，ZooKeeeper会触发其上可触发的所有监视点，这在某些情况下可能会产生问题，如1000个客户端都在监视某znode的Data时，当该znode的数据发生变化，会触发1000个通知，这会造成性能的波动，比如同一时刻的提交操作可能延迟。解决这一问题，OREILLY书上给出了一个利用有序节点的办法（这块书上写的不错，但翻译依旧很烂，现实中很常用所以整理下）：例如n个客户端都抢一把锁。第一种方法是抢到的客户端创建/lock节点，其余客户端便监视该节点的删除事件，当占用锁的客户端完成操作断开时，/lock节点删除，其他客户端获得通知，这种方法就有性能问题。另一种方法是，所有客户端均创建有序节点/lock/lock-xxx，其中xxx为序号，xxx最小的客户端获得锁，其余客户端监视前一个节点，例如有/lock/lock-001，/lock/lock-002，/lock/lock-003三个节点时，001的客户端获得锁，002的客户端监视001的znode，003的客户端监视002的znode，当001的锁释放时，002即获得锁，以此类推，这种方式下每个znode上监视的客户端只有一个，尽管总watches数是一样的，却不会造成性能的波动。
    监视点也是有存储开销的，一个监视点对应服务端的一个Watcher对象，大约消耗300字节内存，因此管理大量的监视点也有不小的开销，运维人员应该注意连接数和产生的监视点数，以免造成OOM。
    另外，如果客户端与ZooKeeper断开连接，客户端就无法触发watches，除非再次与ZooKeeper建立连接。




    关于znode暂时能想到的就这些，如有遗漏会在后续的章节中进行补充。

MVC(Model－View－Control)在我看来是一种设计思想，能够帮助我们设计出结构清晰的和序。而且，我还认为，既然是一种思想，就还可以应用的更多其它的领域。
   MVC从英文名字就能理解其一共划分为三大模块：
   Model:模型层，主包数据的处理，即是业务逻辑。所有与数据有关的操作都应当在这个模块中实现.
   View：视图层，即展现给用户的，其次就是提交用户的请求。它将模型层处理好的数据通过一定的编排后，以用户易易于接受的方式展示出来，所以这个层面主要是由美工做的。
   Control:控制层 控制层就像连接模型层和视图层的管道，负责所有的请求与转发业务。主要由Servlet实现。它既不管具体业务是怎么处理的，也不管用户看到的是什么。它根据用户的请求把事件转发至相应的处理单元，再将处理结果转发给用户。
　
 MVC模型的优点
    1. 低耦合性，视图层和业务层的分离，可以使得更改视图层的代码而不用重新编译模型和控制器代码。三层分离，又增加了程序设计的灵活性，当一个应用的业务流程或者业务规则需要改变时只需改动MVC的模型层，而界面表现的改变只需改动MVC的视图层。
    2. MVC的三层分离可以让不同的开发者负责不同的模块，就可以分工，分工就可以快速部署，就可以提高效率，相当大的缩短开发时间，按照传统的责任划分来处理软件开发过程，使开发者专心于一个领域，从而极大地提高了软件的开发效率，也因此，MVC模型适合于团队开发。
    3. 高重用性和可试性，MVC模式允许使用各种不同样式的视图来访问同一个服务器的代码，包括任何WEB（HTTP）浏览器或者无线浏览器（WAP）。
    4. 可维护性，三层的分离使得WEB应用更易于维护和修改。
    5. 较低的生命周期成本。
    6. 有利于软件工程化管理，不同的层各司其职，每一层不同的应用具有某些相同的特征，有利于工程化、工具化管理程序代码。
    7. 模型的部分，因为足够抽象，可以方便地重复利用，另一方面利用单元测试工具对模型进行单元测试，保证工程质量。

  MVC模型的缺点
    1. 增加了系统结构和实现的复杂性。对于简单的界面，严格遵循MVC，使模型、视图和控制器分离，会增加结构的复杂性，并肯能产生过多的更新操作，降低运行效率。
    2. 视图与控制器过于紧密的连接。视图与控制器是相互分离的，但却又是联系紧密的部件，视图没有控制器的存在，其应用是有限的，反之亦然，这就妨碍了他们的独立重用。
    3. 视图对模型数据的低效率访问。依据模型操作接口的不同，视图可能需要多次调用才能获得足够的显示数据。对为变化数据的不必要的频繁访问，也将损害操作。
    4. MVC模式应用于J2ME上增大了代码体积。据不完全统计，使用了MVC模式后，代码体积约是不是用的1.5倍，这对于存储容量十分有限的移动设备是致命的。
    5. MVC的3个定义不是很具体，对于3个部件的具体功能还存在着一些争议，给初学者留下不少陷阱，加大了使用MVC模式的难度。
    6. 目前，一般高级的界面工具或构造器不支持MVC模式，改造这些工具一适应MVC需要和建立分离的部件的代价很高，从而也造成了使用MVC的困难。

文章目录
01 | 前缀树
02 | 贪心算法
1.按最低字典序拼接字符串
2.切分金条总代价最小
3.最多做k个项目的最大利润（IPO）
4.安排最多的宣讲场次

01 | 前缀树


前缀树又名字典树，单词查找树，Trie树，多路树形结构，和hash效率有一拼，是一种用于快速检索的多叉树结构。多用于词频搜索或者模糊查询。


查询时只与样本长度有关，而与样本量无关。


如下图所示，将字母写在边上。




代码实现：
public class Code_01_TrieTree {	
	public static class TrieNode {
		public int path;
		public int end;
		public TrieNode[] nexts;

		public TrieNode() {
			path = 0;   //有多少个结点到达过
			end = 0;    //有多少个字符串以这个结点结尾
			nexts = new TrieNode[26];  //通向子节点的路，如果题目所给的范围不确定就用map
		}
	}

	public static class Trie {
		private TrieNode root;

		public Trie() {
			//准备一个头结点
			root = new TrieNode();
		}

		//将一个单词插入
		public void insert(String word) {
			if (word == null) {
				return;
			}
			char[] chs = word.toCharArray();
			TrieNode node = root;
			int index = 0;
			for (int i = 0; i < chs.length; i++) {
				index = chs[i] - 'a';
				if (node.nexts[index] == null) {
					node.nexts[index] = new TrieNode();
				}
				node = node.nexts[index];
				node.path++;
			}
			node.end++;
		}

		//在结构中删除这个单词
		public void delete(String word) {
			if (search(word) != 0) {
				char[] chs = word.toCharArray();
				TrieNode node = root;
				int index = 0;
				for (int i = 0; i < chs.length; i++) {
					index = chs[i] - 'a';
					if (--node.nexts[index].path == 0) {
						//如果某个结点-1之后==0，则说明此节点之后的结点也是-1之后==0，因此直接=null即可。
						node.nexts[index] = null;
						return;
					}
					node = node.nexts[index];
				}
				node.end--;
			}
		}

		//查找某个单词插入了几次
		public int search(String word) {
			if (word == null) {
				return 0;
			}
			char[] chs = word.toCharArray();
			TrieNode node = root;
			int index = 0;
			for (int i = 0; i < chs.length; i++) {
				index = chs[i] - 'a';
				if (node.nexts[index] == null) {
					return 0;
				}
				node = node.nexts[index];
			}
			return node.end;
		}


		//查某个字符串前缀数量是多少
		public int prefixNumber(String pre) {
			if (pre == null) {
				return 0;
			}
			char[] chs = pre.toCharArray();
			TrieNode node = root;
			int index = 0;
			for (int i = 0; i < chs.length; i++) {
				index = chs[i] - 'a';
				if (node.nexts[index] == null) {
					return 0;
				}
				node = node.nexts[index];
			}
			return node.path;
		}
	}

	public static void main(String[] args) {
		Trie trie = new Trie();
		System.out.println(trie.search("zuo"));
		trie.insert("zuo");
		System.out.println(trie.search("zuo"));
		trie.delete("zuo");
		System.out.println(trie.search("zuo"));
		trie.insert("zuo");
		trie.insert("zuo");
		trie.delete("zuo");
		System.out.println(trie.search("zuo"));
		trie.delete("zuo");
		System.out.println(trie.search("zuo"));
		trie.insert("zuoa");
		trie.insert("zuoac");
		trie.insert("zuoab");
		trie.insert("zuoad");
		trie.delete("zuoa");
		System.out.println(trie.search("zuoa"));
		System.out.println(trie.prefixNumber("zuo"));

	}

}




举个栗子：一个字符串类型的数组arr1，另一个字符串类型的数组arr2。

arr2中有哪些字符，是arr1中出现的？请打印


对应上述代码中的search(String word)功能。

  


arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请 打印


对应上述代码中的prefixNumber(String pre)





arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印 arr2中出现次数最大的前缀。


对应上述代码中的prefixNumber(String pre)



02 | 贪心算法

不要企图证明贪心的正确性，想几个贪心策略之后，用对数器去证明正确的即可。


贪心算法：在对问题求解时，总是做出在当前看来是最好的选择(最小，最大，最优等等)。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
贪心算法的解题思路：把求解的问题分成若干个子问题，对每一子问题求解，得到子问题的局部最优解；把子问题的解局部最优解合成原来解问题的一个解。
贪心策略靠经验和积累，没有其他办法。

1.按最低字典序拼接字符串

给定一个字符串类型的数组strs，找到一种拼接方式，使得把所 有字符串拼起来之后形成的字符串具有最低的字典序。


字典序：对于字符串，先按首字符排序，如果首字符相同，再按第二个字符排序，以此类推。如aa,ab,ba,bb,bc就是一个字典序。
解题思路：str1.str2 <= str2.str1，则 str1 放前面，否则 str2 放前面(根据两个字符串拼接的结果的大小来决定排序)，不能直接根据str1和str2的大小比较决定位置排放，比如：b和ba，最小的字典序应该是bab而不是bba。
代码实现：
import java.util.Arrays;
import java.util.Comparator;

public class Code_05_LowestLexicography {

	public static class MyComparator implements Comparator<String> {
		@Override
		public int compare(String a, String b) {
			return (a + b).compareTo(b + a);
		}
	}

	public static String lowestString(String[] strs) {
		if (strs == null || strs.length == 0) {
			return "";
		}
		Arrays.sort(strs, new MyComparator());
		String res = "";
		for (int i = 0; i < strs.length; i++) {
			res += strs[i];
		}
		return res;
	}

	public static void main(String[] args) {
		String[] strs1 = { "jibw", "ji", "jp", "bw", "jibw" };
		System.out.println(lowestString(strs1));

		String[] strs2 = { "ba", "b" };
		System.out.println(lowestString(strs2));

	}
}



2.切分金条总代价最小

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如 长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。一群人想整分整块金 条，怎么分最省铜板？
例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为 10+20+30=60. 金条要分成10,20,30三个部分。 如果， 先把长 度60的金条分成10和50，花费60 再把长度50的金条分成20和30， 花费50 一共花费110铜板。 但是如果， 先把长度60的金条分成30和30，花费60 再把长度30 金条分成10和20，花费30 一共花费90铜板。
输入一个数组，返回分割的最小代价。



解题思路：

典型的哈夫曼编码问题
如下图所示：两个叶子节点合并过程中代价就是他们的和，最后只需将所有的非叶子节点值相加即为总代价。


贪心步骤如下：

1）将数组中元素加到小根堆中

2）每次从小根堆中弹出两数（最小的两个）进行相加得c，总代价+c，将c放回到小根堆中

3）重复1、2步骤，直至堆中只剩下一个数时结束。



当总共的代价是由子代价一种累加累乘或者是一个公式都有可能用哈夫曼编码贪出来。


根据自定义的比较器不同来实现不同的堆，比较器就是贪心的标准。


代码实现：
public class LowestCost {
 
    // 最小堆
    public class MyComparator implements Comparator<Integer>{
 
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;   // 谁小把谁放在前面: -表示o1小
        }
    }
 
    public int lowestCost(int[] arr){
        // 优先级队列是小根堆，谁在前面，就把谁的优先级设置小点
        PriorityQueue<Integer> pq = new PriorityQueue<>(new MyComparator());
        for (int i : arr) {
            pq.add(i);
        }
        int costTotal = 0;   // 总的代价
        int costOne = 0;     // 两数合并的代价
        // 等于1的时候，说明堆里面只有一个元素了，即已经合并完成
        while(pq.size() > 1){
            costOne = pq.poll() + pq.poll();   // 合并堆里面最小的两个元素
            costTotal += costOne;              // 两小数合并的结果
            pq.add(costOne);                 // 将两小数合并的结果重新添加到堆里
        }
        return costTotal;
    }
 
    public static void main(String[] args) {
        LowestCost lc = new LowestCost();
        int[] arr = {10, 20, 30, 40};
        int res = lc.lowestCost(arr);
        System.out.println(res);      // 190 = 10 + 20 + 30 + 30 + 40 + 60
    }
}



3.最多做k个项目的最大利润（IPO）

输入： 参数1:代价数组costs; 参数2: 利润数组profits; 参数3：正数k； 参数4：启动资金W 。costs[i]表示i号项目的花费 profits[i]表示i号项目的利润， k表示你不能并行、只能串行的最多做k个项目 。

说明：你每做完一个项目，马上获得的收益，可以支持你去做下 一个 项目。 一次只能做一个项目。

输出： 你最后获得的最大钱数。



解题思路：

准备一个小根堆，这个小根堆是按照花费，谁花费低谁放到小根堆的头部。
准备一个大根堆，这个大根堆是按照收益高，谁收益高谁放在大根堆的头部。
若小根堆不为空，项目也没做完 K 个，则每次先从小根堆解锁能够做的项目，放入大根堆
大根堆不为空，从大根堆弹出堆顶项目来做（即利润最大的项目，每次只弹出堆顶一个项目来做）；
把 W 加上利润，初始资金增加，再重复3)、4）步骤。



举个栗子：




代码实现：
public class IPO {
 
    // 项目节点
    public class Node{
        private int profit;    // 项目利润
        private int cost;      // 项目成本
 
        public Node(int profit, int cost){
            this.profit = profit;
            this.cost = cost;
        }
    }
 
    /**
     * @param k ：最多做k个项目
     * @param fund ：总的资金
     * @param profits ：每个项目的利润数组
     * @param cost ：每个项目的成本数组
     * @return
     */
    public int findMaxCapital(int k, int fund, int[] profits, int[] cost){
        // 初始化每个项目节点信息
        Node[] nodes = new Node[profits.length];
        for (int i = 0; i < profits.length; i++) {
            nodes[i] = new Node(profits[i], cost[i]);
        }
        // 优先级队列是谁小谁放在前面，比较器决定谁小
        PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());       // 成本小顶堆
        PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());   // 利润大顶堆
        for (int i = 0; i < nodes.length; i++) {
            minCostQ.add(nodes[i]);   // 将所有的项目插入成本堆中
        }
        // 开始解锁项目，赚取利润
        for (int i = 0; i < k; i++) {
            // 解锁项目的前提条件：成本堆中还有项目未被解锁并且该项目的成本小于当前的总资金
            while(!minCostQ.isEmpty() && minCostQ.peek().cost <= fund){
                maxProfitQ.add(minCostQ.poll());   // 将当前成本最小的项目解锁
            }
            if(maxProfitQ.isEmpty()){
                // 如果maxProfitQ为空，则说明没有当前资金能够解锁的新项目了，之前解锁的项目也做完了，即无项目可做了
                return fund;   // 最后的总金额
            }
            fund += maxProfitQ.poll().profit;   // 做利润最大的项目
        }
        return fund;   // k个项目都做完了
    }
 
    // 成本小顶堆：成本最小的在堆顶
    public class MinCostComparator implements Comparator<Node>{
        @Override
        public int compare(Node o1, Node o2) {
            return o1.cost - o2.cost;
        }
    }
 
    // 利润大顶堆：利润最大的在堆顶
    public class MaxProfitComparator implements Comparator<Node>{
        @Override
        public int compare(Node o1, Node o2) {
            return o2.profit - o1.profit;
        }
    }
}	



4.安排最多的宣讲场次

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目 的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数 组，里面 是一个个具体的项目)，你来安排宣讲的日程，要求会 议室进行 的宣讲的场次最多。

返回这个最多的宣讲场次。


解题思路：

不能按照哪个项目开始的早先安排哪个，因为可能开始早的占用时间非常长，显然不合理；
项目持续的时间短优先安排也不合理，因为可能存在时间短的项目时间点正好在其他两个时间长项目中间，这样因为这一个项目就会浪费掉其他两个项目，显然也是不合理的；
按照哪个项目先结束来排。先做结束最早的项目，然后淘汰因为这个做这个项目而不能做的项目（时间冲突），依次这样去做。


代码实现：
public class BestArrange {	 
    public class Program{
        public int start;    // 项目开始时间
        public int end;      // 项目结束时间
 
        public Program(int start, int end){
            this.start = start;
            this.end = end;
        }
    }
 
    /**
     * @param programs ：项目数组
     * @param cur ：当前时间
     * @return ：能够安排的最大项目数
     */
    public int getBestArrange(Program[] programs, int cur){
        // 也可以用堆来做，都一样
        Arrays.sort(programs, new ProgramComparator());
        int res = 0;
        for (int i = 0; i < programs.length; i++) {
            // 只有当前时间早于第i个项目的开始时间时，才可以安排
            if(cur <= programs[i].start){
                res++;   // 安排上了
                cur = programs[i].end;   // 当前时间推移到本次安排项目的结束时间，下个项目的开始时间必须在这个时间之后
            }
        }
        return res;
    }
 
    // 按照项目的结束时间早来排序，即实现小根堆
    public class ProgramComparator implements Comparator<Program>{
        @Override
        public int compare(Program o1, Program o2) {
            return o1.end - o2.end;
        }
    }
}