大数据理论基础 by gy 4399 2019/5/1

大数据处理流程 4399 2019/5/1

分布式数据库：Bigtable,Hbase 可视化：曲线图等。 推荐系统…… 批处理：MR（任务在流动） 流式处理：Storm（数据在流动） 交互式分析：hive，shark 机器学习：Spark 分布式文件系统：GFS，HDFS； 分布式数据库：Bigtable,Hbase 推送：scribe（thrift），flume（agent），databus（监控log） 拉取：kafuka。 大多基于事件驱动：解耦。 4399 2019/5/1

大数据基本概念 4399 2019/5/1

CAP consistency:强一致性。 availability:可用性。高可用，低延迟。 partition tolerance:分区容忍性。网络分区时可以继续工作。 （网络分区：由于网络不通，造成部分节点之间无法通信，导致集群分为了不同的区域） 4399 2019/5/1

取舍，CAP不可兼得！ 异地机房A和B，两DB同时提供写入读取 1. 同时写A和B，出现网络故障时，无法同时保证CA。 鱼与熊掌，江山与美人 异地机房A和B，两DB同时提供写入读取 1. 同时写A和B，出现网络故障时，无法同时保证CA。 2. 机房间异步更新（最终一致性）。无法保证C。 3. 同时写A和B，网络故障时提供降级服务（只读）。无法满足A。 4399 2019/5/1

幂等性： f(f(x))=f(x) 调用方反复执行同一操作，与只执行一次操作结果相同。 保持幂等性有助于系统的容错性。 4399 2019/5/1

副本更新策略： 1. 同时更新。需要一致性协议保证数据一致性。 2. 主从更新。先提交到主副本，然后主副本通知从副本更新。 （1）同步方式。等待从副本更新完毕。强一致性，高延时。 （2）异步方式。弱一致性，低延时。redis，zookeeper。 （3）混合方式。等待部分从副本更新完毕。kafuka。 4399 2019/5/1

一致性协议： 多副本数据一致性；多节点状态一致（master选举）。 1. 两阶段提交协议。不难，不讲。 2. Paxos协议：一致性协议的基石。难懂，不讲。 3. Raft协议：Paxos协议的简化版。（演示动画：http://thesecretlivesofdata.com/raft/） 4. RWN协议：N份备份数据；一次更新，至少W份数据写入成功；一次读取，至少R份数据读取成功；R+W>N；so，读取操作一定可以读到最新的数据。 4399 2019/5/1

常见数据结构及算法： 1. 布隆过滤器：Bloom Filter。 2. LSM树。 3. SkipList。 看脸说话：我只说布隆过滤器 4399 2019/5/1

3. 对于元素w，分别计算其k个函数值，对应的二进制数组上如果均为1，则w属于S。 会误判不会漏判 作用：提高查找效率 1. 一个很长的m位的二进制数组。 2. 有k个函数h，对于集合S的成员a， 将第x为置为1。 3. 对于元素w，分别计算其k个函数值，对应的二进制数组上如果均为1，则w属于S。 4399 2019/5/1

大数据存储 4399 2019/5/1

数据分片： 中间的 partition-machine映射，将数据分片和物理机器解耦，方便扩展、数据迁移。 redis集群：将key映射到哈希槽，哈希槽映射到节点。 4399 2019/5/1

节点变动时（新增或者退出），只有其后续节点受影响。 常见的分片方式： 1. 范围分片。 2. 哈希分片。 一致性哈希： 节点变动时（新增或者退出），只有其后续节点受影响。 memcached客户端可使用一致性hash。 4399 2019/5/1

路由方式： 1. 客户端路由：客户端直接选择正确节点读写指定键（memcached客户端）。 2. 代理辅助路由：客户端将请求发送给代理，代理将请求转发到目标节点（redis代理twemproxy；nginx）。 3. 查询路由：是指你可以把一个请求发送给一个随机的节点，这时节点会把该查询转发给正确的节点（P2P集群）。 4. 混合方式：以上几种方式的混合（hdfs：namenode返回节点位置，客户端直接请求节点；redis集群：客户端自己保存路由表，同时如果key不在节点的负责范围内，节点返回新的路由给客户端）。 4399 2019/5/1

存储方式： 1. 行式存储（mysql）。 2. 列式存储（无关字段不需要读取，增加IO效率；高压缩比；将经常使用的列分为一组；infobright）。 3. 混合式存储（先按行分组，组内同一列的内存连续存储；保证同一行的记录在同一节点上；Hive：RCFile，ORCFile）。 4399 2019/5/1

我们可以这样来分析一个分布式存储系统： 1. 数据如何分片（在哪里）。 2. 如何进行路由，将请求定位到对应的分片上（怎么找）。 3. 数据如何存储。 4. HA怎么保证（多副本如何保持数据一致性；数据损坏时如何进行切换；数据如何恢复）。 4399 2019/5/1

大数据计算 4399 2019/5/1

资源管理框架： 1.数据局部性。 2.调度方式：抢占式与非抢占式。 3.资源分配粒度：群体分配（一次分配所需的所有资源）；增量分配。 4399 2019/5/1

调度器类型： 1. 集中式调度器（JobTracker）。 2. 两级调度器：中央调度器负责粗粒度的资源分配；各个计算框架在收到资源之后，根据任务特性，进行细粒度的资源分配（YARN）。 3. 状态共享调度器：所有计算框架可以看到整个集群的所有资源，采用竞争的方式获取自己所需的资源。 集中---->两级---->状态共享：逐步弱化中央调度器的功能 4399 2019/5/1

计算方式： 批处理 vs 流式计算 MR vs Strom 分发计算 vs 分发数据 MR vs Strom 数据并行 vs 计算并行 数据并行：数据分成不同的子集，并发运行同一逻辑。 计算并行：同一份数据，需要进行不同的计算，不同计算之间并发运行。 4399 2019/5/1

我们可以这样来分析一个分布式计算系统： 1. 对DAG的支持（任务如何表达）。 3. 资源调度策略（任务在哪里执行）。 4. 容错性（任务失败了怎么处理）。 4399 2019/5/1

推荐书籍： 4399 四三九九 2019/5/1

谢谢观看 by gy 4399 2019/5/1