搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 信息安全club > 大数据和云计算读书笔记(2)

大数据和云计算读书笔记(2)

信息安全club 2018-07-01

(书接上文)

哈希分片(Hash Partition) 
最为常见的3种哈希分片方式分别为:Round Robin、虚拟桶和一致性哈希方法。

    Round Robin 
    Round Robin就是常用的哈希取模法,利用哈希函数将数据映射到编号从0到k-1的物理机上。 

    H(key)=hash(key) mod K


    这种分片方式的优点是实现简单,缺点是缺乏灵活性,无法进行横向扩展。


    虚拟桶(Virtual Buckets) 
        虚拟桶机制将所有记录首先通过哈希函数映射到虚拟桶,记录和虚拟桶是多对一的关系,第二层映射是虚拟桶和物理机之间的映射,也是多对一的关系,其具体实现方式是通过查表来实现的,以Membase为例,虚拟桶运行机制如下图所示:

    大数据和云计算读书笔记(2)


        1)路由问题 
        通过以上方式就可以将海量数据分不到集群中的不同节点中,实现数据分片功能。那么如何根据key和哈希函数H来定位到记录内容呢?    一种直观的解决办法就是沿着有向环顺序查找,如果H(key)在本节点管理范围内就返回结果,如果不在则将其交给后继节点继续查找,这样最多遍历所有节点就可以给出结果。 
    很明显以上方法是一个低效的查找方式,为例加快查找速度,可以为每个节点配置路由表。路由表存储m条路由信息(m为哈希空间的二进制数值比特位长度,即哈希空间长度=2^m),其中第i项存储距离当前节点距离为2^i的数据节点。如N14的节点路由表如下所示:

距离 1(2^0) 2(2^1) 4(2^2) 8(2^3) 16(2^4)
机器节点 N20 N20 N20 N25 N5


算法:假设当前执行操作的节点为Nc,其初始值为Ni,Nc的后继节点为Ns,重复执行下列步骤。 
步骤1,判断是否c < j <= s,如果为真,则结束查找,说明key如果存在,则在Nc的后继节点Ns上,Ns返回结果。 
步骤2,否则,Nc查找路由表,找到小于j的最大编号节点Nh(如果所有路由项都大于j,则选择第m-1项作为Nh),Nc向Nh发送消息,由Nh代为查找,Nh此时作为新的Nc继续按照步骤1,步骤2递归进行查找。 
此算法的时间复杂度为O(logn),类似于二分查找。

下图为N14节点接收到H(key)=27时的查找过程: 

大数据和云计算读书笔记(2)


2)加入新节点 
    如果P2P网络加入一个新节点Nnew,首先Nnew能够和任意节点Nx进行通信,通过Nx按照“路由算法”查询Nnew的对应哈希值H(Nnew)=new,找到Nnew的后继节点Ns,假设Ns的前趋节点为Np,那么需要做两件事将Nnew加入网络: 
一. 改变Np、Nnew和Ns的前趋后继节点记录,以体现新的网络架构。 
二. 数据的重新分片与分布,将Ns节点中存储的应该由Nnew承载的数据(Ns节点上哈希值小于等于new的记录)迁移到Nnew节点上。 
    在非并发环境中以上事务较易完成,但是在并发环境中,可能Np和Ns之间同时有多个节点加入,为了避免出现问题,需按照以下两个步骤完成: 
一. 将Nnew的后继节点设置为null。 
二. 这一步并非为新加入节点设立的,而是所有节点周期性自动完成,稳定性检测。


  • 稳定性检测

算法: 
步骤1,假设Ns为Nc的后继节点,Nc向Ns询问其前趋节点Np,Ns向Ns答复,一般情况下,如果Np=Nc则转入第4步。 
步骤2,如果Np介于Nc和Ns之间,Nc记录下Np为其后继节点。 
步骤3,令Nx是Nc的后继节点,其可能是Ns或者Np,这取决于步骤2的判断结果。如果Nx的前趋节点为空或者Nc位于Nx和它的前趋节点之间,那么Nc给Nx发消息告诉Nx,Nc就是Nx的前趋节点,Nx将其前趋节点设置为Nc。 
步骤4,Nx将其部分数据迁移到Nc上,即将Nx上哈希值小于等于c的记录迁移到Nc上。

示例,将N8加入上述网络 
1.根据步骤一,将N8的后继节点设为N14,前趋节点置为null,如下图所示: 

大数据和云计算读书笔记(2)


2.N8进行稳定性检测,步骤1中,N8发现N14的前趋节点不是自己,进入步骤2,由于N5没有介于N8和N14之间,所以直接进入步骤3,因为N8位于N5和N14之间,所以N8向N14发消息,告知N14的前趋节点改为N8,N14的前趋指向N8,如下图所示: 

大数据和云计算读书笔记(2)


3.进入步骤4,N14将部分数据迁移到N8。

一段时间后,N5开始进行稳定性检测,经过步骤N5被告知,N14的前趋节点是N8而不是自己,所以进入步骤2,由于N8介于N5和N14之间,所以N5将后继节点改为N8,如下图所示: 

大数据和云计算读书笔记(2)

进入步骤3,由于N8的前趋节点为空,所以N5通知N8其前趋节点为N5,所以N8将前趋节点置为N5,如下图所示: 


进入步骤4,N8没有需要向N5迁移的数据,结束。 
这样,N8节点就顺利的加入了网络。


(3)当前节点离开网络 
    当前节点离开网络有两种方式:正常离开和异常离开。正常离开的节点在离开前可以做些准备工作,包括通知相应节点修改前趋后继以及将持有数据迁移到相应机器上。异常离开通常是由于机器故障导致,为避免数据丢失,可以采用将数据备份的方式解决。 
关于路由表失效问题,可以通过对每个节点定期检查路由表的方式解决。 
(4)虚拟节点 
    上述一致性哈希算法存在两个问题,一个是数据映射是随机的,可能导致集群的负载不均衡,另一个是集群中的节点存在性能上的差异,可能会导致低性能节点高负载的情况,而且新节点加入时只能缓解其后继一个节点的容量饱和问题,不能有效的缓解集群中其他节点的容量饱和问题。针对以上问题,引入“虚拟节点”的概念,即将一台物理机器虚拟成若干个虚拟节点,分别映射到一致性哈希环的不同位置。这样就解决了上述问题。

范围分片(Range Partition) 


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《大数据和云计算读书笔记(2)》的版权归原作者「PPM嬉皮逸」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注PPM嬉皮逸微信公众号

PPM嬉皮逸微信公众号:gh_0dfaeadd6645

PPM嬉皮逸

手机扫描上方二维码即可关注PPM嬉皮逸微信公众号

PPM嬉皮逸最新文章

精品公众号随机推荐