大数据日知录阅读

发表于 更新于 分类于

架构与算法

数据分片与路由

哈希分片

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
# 一致性哈希算法
给定一个由0-31组成的Hash值闭环,由5个机器存储对应的分片数据
顺时针方向最近的节点存储分片数据
N5->N14->N20->N25->N29->N5
N5(30,31,0,1,2,3,4,5)
N14(6,7,8,9,10,11,12,13,14)
N20(15,16,17,18,19,20)
N25(21,22,23,24,25)
N29(26,27,28,29)

举例:
N5发起存储[test]数据请求
先将[test]进行hash取值[0-31]得到18
逐级寻找对应的存储节点,N5<N14<18<N20
最终存储入N20节点

为了加快访问速度,引用了路由表
在每一个节点上记录了距离其他节点的距离信息
N14的路由表信息(距离->节点)
1(2^0)->N20
2(2^1)->N20
4(2^2)->N20
8(2^3)->N25
16(2^4)->N5
N14接收到查询Hash值为4的请求
先确定4是否在N20节点上,不在则寻找路由表,找到小于4的最大编号节点
发现找不到,取倒数第2项路由信息N25,请求N25取查询4的信息

范围分片

1
将所有记录的主键进行排序,在排好序的主键空间内将记录划分成数据分片

集群资源管理与调度

调度器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
集中式调度器
    整个系统中只运行一个全局的中央调度器,所有框架或计算任务又中央调度器满足
    单路径调度器(无论计算任务的类型,统一的调度策略进行资源管理与调度)
    多路径调度器(支持多种调度策略)
    
两级调度器
    将整个系统分为两个级别,中央调度器和框架调度器
    中央调度器可以将集群中所有机器的可用资源分配给计算框架
    计算框架接收到所需要的资源后,根据自身任务是用调度策略进一步分配资源(Mesos,Yarn,Hadoop On Demand)
    Mesos在具体实现中央调度器调度策略时,倾向于资源分配的公平性,如果各任务所需资源类似,是用Mesos比较合适
    
状态共享调度器
    每个计算框架都可以看到整个集群的资源,采用竞争的方式获取资源,增加了系统的并发性能
    但是系统存在大量资源竞争冲突时,失败者可能需要重新执行任务
    或者优先级高的任务始终能获得资源,而优先级低的任务可能一直获取不到资源

资源调度策略

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
FIFO调度策略
    根据提交的时间先后顺序/优先级次序放入线性队列中,先进先出的进行调度与资源分配
    新加入的作业容易长时间等待调度

公平调度器
    根据每个资源池的最小资源保障量,将系统中部分资源分配给各个资源池
    根据资源池的指定优先级将剩余资源按照比例分配给各个资源池
    在各个资源池中,按照作业优先级或者根据公平策略将资源分配给各个作业
    公平策略是最大最小公平算法的具体实现
    
能力调度器
    将用户与任务组织成多个队列,每个队列都有资源最低保障和使用上限
    一个队列资源有剩余,可以将剩余资源共享给其他队列
    调度时,优先将资源分配给资源使用率最低的队列
    队列内部按照作业优先级顺序使用FIFO策略调度
    资源使用率=已使用资源量/分配的资源量

延迟调度策略
    一般作为其他调度策略的辅助措施
    如果当前资源不满足,可以暂时放弃分配公平性,等待后续资源分配,当前资源跳过该任务分配给其他任务
    如果该任务跳过N次后仍然等不到满足的资源,则接受当前资源启动任务执行

主资源公平调度策略DRF
    最大最小公平算法基本思想:最大化目前分配到最少资源量的用户或任务的资源量
    DRF则将扩展到了多个资源的公平分配
    例如:
        系统共有9个CPU和18GB内存,A用户主资源CPU<3CPU,1GB>,B用户主资源内存<1CPU,4GB>
        A用户3/9总CPU量,1/18总内存量
        B用户1/9总CPU量,4/18总内存量
        经过DRF算法,A启动2个任务,B启动3个任务
        每个用户获得同样的主资源量,A占用2/3CPU,B占用2/3内存