深入浅出zookeeper之一:功能及本质

zookeeper(下文简写为zk)大家都不陌生。但是,看到很多同学对zookeeper的理解过于程式化,有些地方甚至需要背,是大可不必的。把本质理解了,概念性和功能介绍都可以推出来的,而且架构要活学活用,透过现象看本质,才能对技术和技术领悟有大的提升。下面来看下zk的功能及本质。

zookeeper的定义及用途

我们先了解官方的定义。

Apache ZooKeeper is an effort to develop and maintain an open-source server which enables highly reliable distributed coordination.

Apache ZooKeeper 是一个致力于开发和维护开源服务器,该服务器实现高可用的分布式协调框架。

ZooKeeper is a high-performance coordination service for distributed applications. It exposes common services – such as naming, configuration management, synchronization, and group services – in a simple interface so you don’t have to write them from scratch.

zookeeper是一个高性能的分布式应用协调服务框架。它以简单接口形式实现了一系列的通用服务,比如** 命名、配置管理、同步、分组 **等,因此你不必从一堆草稿中去实现他们.

zookeeper的本质功能

通过官方的定义介绍,我们知道了zk是一个server,擅长分布式协调功能。我们来分析下功能的本质实现是怎样的。

zk的数据模型是以znode的形式存储和组织。与标准文件系统类似,是一个树形结构,根节点是’/’。
zk的znode结构

图中每个节点都是一个znode,类似于文件系统中的一个文件,形成了一个树形结构,每个znode内部还可以存储不超过1M的数据。这些znode可以是持久的,还可以是短期的(ephemeral )。
短期的(ephemeral )znode当创建他的客户端session超时,会被zk主动删除。有点类似给文件加锁,进程异常退出后,锁立刻解除。

zk的数据模型类似文件系统,这点也没什么特别的。本质还是kv形式,如果kv的value还要求是kv格式,那么就和zk的数据模型一样。表示成树形的格式,更容易表示层级关系。

zk的特别之处在于:
0. zk内部的选主和写数据机制。有超过一半的zk集群节点选出来的主节点,成为集群的leader节点,负责主写和同步其他丛属follower节点。底层用的ZAB(ZooKeeper Atomic Broadcast)协议。
1. 短期的(ephemeral )znode功能。方便实现锁类操作,在分布式中处理超时状态。
2. 客户端可以设置监控watch某个znode的功能,当znode发生变化(版本号变更)时,会主动通知watch的客户端有变化了。该功能让客户端不必轮询,能够有序地知道znode变更顺序。

命名、配置管理、同步、分组等功能,都是通过1、2两点结合实现的。我们自研的业务如果想实现,也都能想到,或者用类似方式实现。

zk内部的选主和写数据机制。就不那么容易想了,只能依靠论文实现。所以这点更要好好学习下,这种方法很有特点,并且不容易想出来,也不容易理解。

与已有自研业务的区别

自研业务中,实现zk功能的,比较像的是配置中心(下文简称cc)。

一般实现cc,采用一主多从,主节点负责写,从节点只读。主节点通过binlog同步从节点,保证最终一致性。

主节点有两个写数据途径:

1、通过管理台的配置中心更新配置表;

2、通过客户端api上报服务状态,更新客户端节点负载和健康状况。

3、把心跳和变更回包作为一个协议,通知客户端配置更新。

如果从节点死机,不影响集群服务,对应的客户端寻找新的从节点去读。
如果主节点死机,cc只提供读服务,要人工来恢复。

影响:故障期间不能新增或修改配置以及配置项的负载。

如果用zk来实现cc,在正常情况下运行方式和cc是一样的。但是当主死机后,会用算法重新选出主,对客户端透明。让主节点死机停写的概率降低。但是如果有一半的节点死掉,会造成整个zk集群不可用。

对比:

自研cc zk
选主方式 人工配置,主死了集群只读,人工介入恢复 集群协商选主,自恢复后继续服务
集群完全不可用条件 所有节点都死掉 一半节点死掉(可能有分区问题造成zk内部同步有问题,但是节点是可以服务的)

zk的选主方式,并没有完胜一主多从的所有场景。
1. 算法比较复杂,不容易理解和实现。
2. 某些重要任务,出现主写问题,为了一致性,要人工介入恢复,自动选新主切换会造成数据丢失。
3. 对于业务特定的场景特点,做一些弥补方案,能降低单点主写的风险。例如搭建多套cc,并行写,都对外提供服务,因为配置节点健康和负载的少量不一致,对业务来说是可以接受的。还可以在业务中增加缓存,保证主死了能够有足够的时间恢复。

以上自研业务没有引入ZAB或paxos协议的原因。在出现zk之后,想用的业务可以直接在zk之上构建集群内节点选主功能。

注意事项

我们在zk上构建服务的时候,要注意zk死一半节点就全集群死掉的特点。要考虑到如果zk集群不服务,业务有备选方案,能够对外尽力服务。例如zk充当配置中心,client要设置缓存,或默认配置。

为了节约资源,zk集群必须是奇数台机器。但是zk的机器数变多,对性能会有较大影响。写数据同步和选主都会变得越来越慢。

解决方法:
1. 读多写少:增加观察者节点来扩展读性能。观察者节点不参与主从节点的协商和选举,只负责同步主节点。
2. 读少写多:根据业务特点划分set,做到平行扩展。

总结

zookeeper通过ZAB协议实现了集群内部选主和写同步功能,提高了服务的健壮性,和写操作的有序性。是实现的难点,背后有严密的数学理论推理。

通过实现,短期的(ephemeral )znode和主动通知节点变更消息的功能,客户端能够及时知道监听节点变化,在客户端和zk断开连接后,也能够自动释放节点。轻松地实现锁类服务和监听更新类需求。这些是实现名字服务、配置管理、同步、分组等服务的基础。

后面会再写介绍ZAB协议和zk典型应用场景用法的文章

教人怎样读书的书——《如何阅读一本书》

读书能够让人增长心智,提高认知,对一个个分散的问题找到解决方法。

在读书本身这件事上,也是有方法可循。

《如何阅读一本书》就是教人怎样读书的书。对于经常读书的人,可以学习下其中的方法,走一些捷径。

这本书的两个作者是莫提默·J. 艾德勒查尔斯·范多伦他们是《大英百科全书》的编辑,在1940年就写出了这本书。虽然年代久远,但是对于读书来说,里面的方法是很实用的,一点都不过时。

阅读的四个阶段

阅读分为四个阶段:基础阅读、检视阅读、分析阅读、主题阅读。由浅入深,每个阶段都包括前一阶段的全部内容,前一阶段是后一阶段的基础。

四个阶段不是要分成四个步骤,当你阅读技巧熟练时,可以在一次阅读中完成多个阶段。

基础阅读

就像小学生识字,或读外国文献一样,把书中的文字和句子内容认识出来,读懂语义,是最初级的阅读。一般经过学校训练的学生,都具备这种能力。当读某种国外文字时,我们有时会退化到基础阅读,要逐字逐句地翻译理解句子的意思。

检视阅读

阅读一本书时,要先对书的主题有所研究,不用一开始就详细地读书的每个细节。对书的内容主题有个大概的了解,让我们在一开始就先界定这本书是否有用,哪些地方是我们要重点读的有个界定。

  1. 先看书名页,注意副标题,可以对书的主题有概念。将书分类。
  2. 研究目录页,对书的架构有概括性了解,目录是一本书的纲要,作者花费很多心思在目录的组织上,我们能够通过目录了解一本书的架构。
  3. 书的索引,书衣上的出版社介绍,都是概括书主要内容的重要线索。
  4. 略读书的内容,遇到难懂的内容也不要停下来,这步的主要目标是对书有个整体的把握。要快速的把书读完,哪些需要慢慢读的部分,留到后续的分析阅读中去读。

看书名页、目录页、索引都是比较容易忽略的,但是里面对全书的架构有概括的描述,是最值得在初读一本书时重点看的。

检视阅读相当于略读,大体读懂书的内容即可,不懂的可以留到后面读,先对书有整体把握,知道书在讲什么,是什么类型的书,是否是自己需要读的书籍。

分析阅读

分析阅读是详细地读一本书,发掘作者的观点,和论述的方法。对一本书的整体和细节都有详细的了解。能够描述出一本书的架构,每部分都是写的怎么,每个部分论述是怎么组织的。就是精读一本书。

在分析阅读时,最好不借助外力,自己一个人阅读,如果经常这么做,就越发现不用外界助理了。

当下各种书摘书评都很多,但是那是别人经过处理的,难免会有些丢失,如果总依赖这种,会在短时间内觉得知识丰富了,但是对于图书的一些精髓,和你阅读时能够受到的触发或感受,是得不到的,长远看对心智的成长是不利的。

在精读时要独立思考,评判性地读一本书,书中的观点是否正确,为什么正确,为什么错误,要有理有据。这样才能吃透一本书。

主题阅读

主题阅读不局限于一本书了,而是要对一个问题,找一系列的书来论证该问题。要先找到相关的书,然后对这些书做过滤和筛选,找到这些书中对问题有关系的部分。抽取出对问题有帮助的内容。来解决这个主题的问题。

有点像大学写论文,要把相关文献都读一遍进行总体归纳。我们平时对一个技术问题进行研究时,也要翻阅大量的书籍,或通过搜索引擎读大量的网页,最终总结出知识点。

四个阅读阶段,和我们做系统架构也很类似。

  • 基础阅读——刚接触一个业务时,要会业务模块的语言,熟悉用的组件的功能,否则没办法接手一个业务。
  • 检视阅读——对业务部署有大体的了解,熟悉架构图,知道每个模块间的调用关系。

  • 分析阅读——对每个模块内部,每条协议,每个方法都详细了解,对这个业务抽丝剥茧,全部熟悉。

  • 主题阅读——找和模块相关的主题,例如缓存怎么设计,消息系统怎么设计,把业内类似的系统都了解,总结出方法论,
    对系统设计有整体思考和对比。

读书的态度

读书要主动阅读,带着问题和目标去读,如果不喜欢,被动阅读,不如不读。

主动阅读要能提出四个主要问题:

  1. 这本书在谈什么?
  2. 作者细说了什么,怎么说的?
  3. 这本书说的有道理吗?是全部有道理,还是部分有道理?
  4. 这本书和你有什么关系?

很多人读书是被动的,被人逼着读,或者听说某本书好就去读,不是自己真的感兴趣。这样的读是低效的,是浪费时间。要思考上面的四个问题,特别是最后一个问题,在每次要翻开一本书时,都想想,这本书到底和你有关系吗?

总阅读在能力范围之内的书,是没法提升阅读能力的。必须能操纵超越能力的书,阅读超越头脑的书,能够帮助思想成长。除非能增长心智,否则学不到东西。

好读者也是阅读要求高的,阅读时也是很主动的。

书中的方法论只是理论,要通过读其他的书,来练习读书的方法,才能提高心智,成为一个好的读者。

读书要分主次,消遣或资讯类的不用详细读,甚至可以不读,这类书知识提高了读的量,但是并没有太多实质的东西,
只是让你知道了某些事情。特别现在的新闻app,都是些无用的新闻,但是却很“有趣”,把时间花在这些内容上,得不偿失。

即使是书籍,有用的,称得上精华的,也不足万分之一,要有独立思考和筛选的能力,读好书,多读书。

为什么读书?

读更多的书,才能更了解世界,更了解人类,提高我们的心智和认知,减少我们的困惑,真正的提升自己,而获取更好的生活。

一本好书能够叫你了解这个世界以及你自己。你不只是更懂得如何读的更好,还懂得生命。你变得更有智慧,
而不只是更有知识。你会成为一位智者,对人类生命中的永恒真理有更深刻的体认。

从读书、读好书、会读书开始,做个心智健全,对人类、世界更了解的人!

了解一致性hash算法

定义

一致性hash算法,在维基百科的定义是:

Consistent hashing is a special kind of hashing such that when a hash table is resized, only K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped because the mapping between the keys and the slots is defined by a modular operation.

翻译过来的意思就是当hash表更新节点的数量时,只有k/n的关键字位置有变化,其他关键字的位置映射关系不变。与其他的hash算法比,其他的算法节点个数n变化后,更多的key关键字和节点的映射会发生变化。

使用场景

一致性hash主要用在路由中,对有状态的服务,根据key进行转发到对应的服务中。保证相同的key一直落到同一个服务器,当有服务节点增减时,只有少量(k/n)的请求位置是变化的。减少重新建立缓存或存储的成本。

原理实现

前提:

  • 每个请求的key范围[0,2^32),一共有k个key;
  • 一共有N个节点,结点和服务器对应。

常规实现

取key所映射的所有值最大空间(2^32)个,组成一个环,然后随机在这个环上落N个点,相邻的两个点形成一个左闭右开(关于左闭右开参考《聊聊左闭右开区间》)区间。共有N个区间。

对于每个key,一定只落在N个区间中的一个,它属于该区间所分配的节点。

当有服务节点增减时,会有区间新增或消失,平均只有k/N个key会受影响,变更属于的节点。

如下图,在插入nodeC之前,2、3、8key都属于nodeA,当插入nodeC后2、3归属C,属于B的节点不会改变。

image common hash

改进:增加虚节点

常规实现在实际应用中会遇到问题。当N的数量太少时,会导致N个节点所管辖的区间并不均匀。

既然是N的数量太少,那增加N的数量不就行了?正解,可以成倍地增加N的数量,一个实际的节点扩充为100倍的虚节点,每个key先查找属于哪个虚节点,再查看该虚节点属于那个实节点。

由于众多虚节点的引入,使每个实节点被分配到的key数量的差距变少。

image vnode common

从图中可见,增加了nodeA和nodeD的虚节点后,把区间分得更细小,会使分布更均匀。还可以通过设置权值,让不同处理能力的实节点,处理不同量级的key。

实践经验

通过上面的讲解,可以熟悉一致性hash的算法,但是在实际使用中,还是有很多需要注意的地方。

如何加入虚节点

加入虚节点能够解决分布不均的问题,但是如何加入也是有技巧的。如果完全随机,就是撞大运编程。要利用搜索算法,加入节点时要检测,保证每个实节点的区间不能差异太大。必要时要回溯,剪枝,或者用启发性搜索。

节点配置同步

一个大系统,每个真实节点有1000个虚节点,一共1000个实节点,有1M条目数据。每当更新节点信息时,要保证快速更换、传递更新数据,而且要有检查功能。节点配置的同步、检测也会有很多细节问题。

三门问题的解释和程序验证

一个游戏:有3扇关闭着的门,其中2扇门后面各有一只羊,另一扇门后面有一辆车。
参与者:一个游戏者和一个主持人。主持人事先知道各扇门后的物品,而游戏者不知道。
游戏目的:游戏者选择到车。
游戏过程:1、游戏者随机选定一扇门;2、在不打开此扇门的情况下,主持人打开另一扇有羊的门。3、此时面对剩下2扇门,游戏者有一次更改上次选择的机会。
问题:游戏者是否应该改变上次的选择,以使选到车的概率较大?

问题的学名叫《蒙提霍尔问题》,阅读原文有来龙去脉。

答案有换和不换两种,有的认为是换概率是2/3,有的认为是不换和换都一样,概率是50%,因为后面剩两个概率是相同的。

正确答案是应该换,几种解释:

  1. 游戏者坚持每次都换,开始选中羊的概率是2/3, 在第一次选中羊的情况下,换了就能够得到车,所以换能得到车的概率是2/3。
  2. 假设有1000个门,只有一个后面有车,如果主持人帮游戏者打开选后的998个门,要不要换?当然换,排除了错误答案的情况,换的概率会高很多。

除了思考的方式,还可以写个程序,用实验的方式验证。(在一些不容易想的问题上,可以用程序模拟多次独立事件,直观查看结果,但不一定和理论完全一样)

代码和结果如下,如果在主持人提示后换的话,也是2/3的概率选中车。

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "time.h"

#define DOOR_COUNT 3
int getrand( int max )
{
    double max_rand = RAND_MAX * 1.0;
    return (rand() /max_rand) * max;
}
int choose( int changed )
{
    char door[ DOOR_COUNT ] = { 0 };
    int moto_index = getrand( DOOR_COUNT );//车子所在的门序号
    door[ moto_index ] = 1;
    int choose_index = getrand( DOOR_COUNT );//游戏者第一次选的门序号
    int left_index = -1;
    int display_index = -1;
    int i;
    for (i = 0; i < DOOR_COUNT; i++) {
        if( i == choose_index  )
            continue;
        if( i == moto_index )
            continue;
        display_index = i;//主持人打开的门序号
        break;
    }
    for( i=0; i < DOOR_COUNT; ++i )
    {
        if( i == choose_index  )
            continue;
        if( i == display_index )
            continue;
        left_index = i;//最后没打开的门序号
    }
    printf("moto_index = %d first_choose_index = %d display_index = %d left_index = %d\n",
            moto_index, choose_index, display_index, left_index);
    if( changed == 1)
        choose_index = left_index;
    if( choose_index == moto_index )
        return 1;
    return 0;
}
int main(int argc, const char *argv[])
{
    srand( ( unsigned  )time( NULL ) );
    int count = 10000;
    int changed = 1;//交换
    int motocount = 0;
    int i;
    for (i = 0; i < count; i++) {
        int iRet = choose( changed );
        motocount += iRet;
    }
    printf( "changed = %d count = %d motocount = %d, rate = %0.2f\n",
            changed, count, motocount, motocount*1.0/count);
    system( "pause" );
    return 0;
}

运行结果

moto_index = 0 first_choose_index = 1 display_index = 2 left_index = 0
moto_index = 2 first_choose_index = 2 display_index = 0 left_index = 1
moto_index = 1 first_choose_index = 2 display_index = 0 left_index = 1
......
moto_index = 2 first_choose_index = 0 display_index = 1 left_index = 2
moto_index = 2 first_choose_index = 0 display_index = 1 left_index = 2
moto_index = 0 first_choose_index = 0 display_index = 1 left_index = 2
moto_index = 1 first_choose_index = 0 display_index = 2 left_index = 1
moto_index = 2 first_choose_index = 0 display_index = 1 left_index = 2
moto_index = 0 first_choose_index = 1 display_index = 2 left_index = 0
moto_index = 1 first_choose_index = 0 display_index = 2 left_index = 1
moto_index = 0 first_choose_index = 2 display_index = 1 left_index = 0
moto_index = 2 first_choose_index = 1 display_index = 0 left_index = 2
moto_index = 0 first_choose_index = 2 display_index = 1 left_index = 0
changed = 1 count = 10000 motocount = 6692, rate = 0.67