《大数据日知录架构与算法》读书笔记
2022-04-29 14:48:57 28 举报AI智能生成
本文详解了大数据分布式架构和算法的理论
作者其他创作
大纲/内容
大数据基础理论
数据定义、数据分片与路由
大数据特点4V
大容量Volume
多形式Variety
高速率Velocity
价值Value
大数据处理流程
数据源-采集
数据管理-存储管理
数据分析-数据挖掘、机器学习、统计分析、时空序列分析
数据获取-可视化
数据分片-水平扩展、复制、路由
抽象模型：key-partition、partition-machine
哈希分片
哈希取模法Round Robin:H(key) = hash(key) mod K
优点：简单
缺点：不方便扩展
虚拟桶:对应数据分片
key-partition映射采用哈希函数
partition-machine映射采用表格管理
一致哈希方法
分布式哈希表（DHT），p2p网络
路由、加入新节点、离开新节点、虚拟结点
范围分片
主键有序排列，按照LSM树进行管理
key-partition采用记录主键排序分割
partition-machine保持对应关系
数据复制与一致性
数据库设计基本理念
CAP：Consistency/Availability/Partition Tolerance.强一致性、可用性、分区容忍性
ACID：atomicity/consistency/isolation/durability.原子性、一致性、事务独立、持久性
BASE：Basically Available/Soft State/ Eventual Consistency.基本可用，软状态，最终一致性
一致性模型分类
一致性关系图
副本更新策略
同时更新
不使用一致性协议，存在数据不一致问题
通过一致性协议预先处理
主从式更新
同步更新方式
异步更新方式
混合更新方式
任意节点更新
一致性协议
两阶段提交协议
阶段一：表决阶段
阶段二：提交阶段
一个协调者、多个参与者
向量时钟
生成事件之间的偏序关系的算法，通过将时间戳和事件绑定判断事件之间的因果相关性
RWN协议
R：一次成功的读取至少有R份数据成功
W：一次成功的写入至少有W份数据成功
N：备份数据的份数
R+W>N:满足数据一致性
Paxos协议
副本状态机
安全性
可用性
快速响应
单paxos：使得服务器的副本状态机对应某个固定位置的操作命令一致
多paxos：多个位置的操作命令一致。多个单paxos协议共同执行的结果
三个角色：倡议者、接收者、学习者
Raft协议
可理解性
实现实际系统的确定性
方法一：将一致性协议划分成3个子问题：（分解法）领导者选举、Log复制、安全性
方法二：将Paxos的P2P模式改造成Master-Slave模式
大数据常用的算法和数据结构
布隆过滤器
常被用来检测某个元素是否是巨量数据集合中的成员
集合大小n，位数组m，哈希函数个数k
首先：m位数组元素全部置0.其次，对集合中元素a经过k个哈希函数，最后，将w（小于等于k）个哈希结果位置置1
存在误判，但不存在漏判
误判率小于1%。三者与误判率之间的关系:
最优哈希函数个数k：
已知集合大小n，设定好误判率p；计算位数组m的公式：
优点：效率高。缺点：1、存在误判率。2、无法删除数据。
计数布隆过滤器，关于无法删除数据的缺点改进。
基本信息单元由多个bit代替一位bit来表示信息。只要基本信息单元不为0，则表示属于成员，删除成员只要将信息单元减1即可
SkipList
有序链表，并给每个节点添加更多的向后指针
采用随机数，来确定节点向后指针的个数，也即层数。最高层级MaxLevel
LSM树Log-structured Merge-tree
Log-structured Merge-tree，本质是将大量的随机写操作转换成批量的序列写
使用LSM的数据系统：BigTable、SILT、RAMCloud、Cassandra、LevelDB
LevelDB静态结构
内存中的Memtable、Immutable MemTable
磁盘:Current文件、manifest文件、.log文件、SSTable文件
当应用写入一条Key：Value记录时，LevelDB会先往log文件里写入，成功后将记录插进MemTable
一次写操作：包含一次磁盘顺序写和一次内存写入
MemTable采用SkipList数据结构
当MemTable数据到一个界限后，则将记录导出。形成新的log和MemTable，原先MemTable称为Immutable MemTable，导入磁盘形成-》SSTable
SSTable由Compaction操作形成层级结构，主键有序排列
Compaction操作类型：minor、major、full
minor Compaction：按照Immutable MemTable的记录由小到大遍历写入level 0的SSTable文件中，并建立index数据
major Compaction：对多个文件采用多路归并排序，找出最小key记录，并判断key是否要保存，完成L层和L+1层的合并形成新的文件
manifest记载了SSTable各个文件的管理信息，比如属于哪个level、文件名称、最小key和最大key
Current文件记载当前的manifest文件名
Merkle哈希树
在海量数据中快速定位少量变化的数据内容
使用的系统举例：BitTorrent、Git、比特币、Dynamo、Riak、Cassandra等
树的子节点是每个数据项或一批数据项对应的哈希值，中间节点保持对其所有子节点哈希值再次哈希的值，以此类推到根节点
Merkle哈希树示例
根节点，Top Hash 保持的是所有数据的整体哈希值
可以在O(log(n))时间内定位变化的数据内容
Snappy与LASS算法
Snappy是Google开源的数据压缩和解压缩算法库。优点：速度快
LZSS算法，LZ77的优化方案
词典编码分静态词典和动态词典
静态词典事先构造词典
动态词典，编码器从被压缩文本中自动导出词典，解码器边解码边构造解码词典
LZ77是一种动态词典编码
滑动窗口和前向缓冲区的概念
将前向缓冲区内的开始字符串与滑动窗口中的字符串进行最长匹配
LZSS对LZ77的改进：增加了最小匹配长度限制
最长匹配技巧
将滑动窗口内字符串的各种长度片段存入哈希表，哈希表的值记载其在滑动窗口内的出现位置
Snappy的设置
设定最小匹配长度为4
压缩数据时将整个数据切割成32KB大小的数据块分别压缩
Cuckoo 哈希
解决哈希冲突（Hash Collision）问题。高效查找！
查找、删除：O(1)时间复杂度；插入数据：常数时间
原理：使用不同的两个哈希函数H1(x)和H2(x)。
对x同时计算两个哈希函数，如果对应值为空，插入并结束
如果对应值都不为空，则替换出旧值y。
对y进行上述步骤。
设置最大替换次数。当达到最大替换次数时，要么增加哈希空间，要么替换哈希函数
应用系统：SILT系统（small index large table）
大数据系统体系结构
集群资源管理与调度
独立的资源管理与调度系统
优点1：集群整体资源利用率高
优点2：可增加数据共享能力
优点3：支持多类型计算框架和多版本计算框架
资源管理抽象模型
YARN、Mesos、Corona（Facebook）、Quincy（微软）
资源管理的概念
三要素：资源组织模型、调度策略、任务组织模型
资源组织模型将资源组成多层级队列的方式
调度策略：FIFO、公平调度、能力调度、延迟调度等
任务组织模型：平级多队列组织、层级队列的树形队列结构
通用架构
通用调度器由资源收集器（管理资源池）和资源调度策略（管理工作队列）构成
调度系统设计的基本问题
资源异质性与工作负载异质性
异质性是指组成元素构成的多元性和相互之间的差异性
资源的异质性：机器配置不一样
工作负债的异质性：应用不一样，批处理和高应用
数据局部性
设计原则：将计算任务推送到数据所在地进行
节点局部性（最优）
将计算任务分配到数据所在的机器节点
机架局部性（次之）
计算任务节点和数据所属节点在同一个机架
全局局部性（低效）
其他情况属于全局局部性
抢占式调度与非抢占式调度
资源分配粒度
作业级、任务级
群体分配策略、全分不分策略、资源储备策略
饿死与锁死问题
饿死现象：指计算任务持续长时间无法获得开始执行任务所需的最小资源量一直处于等待执行的状态
死锁问题：由于资源调度不当导致整个调度系统无法继续正常执行
资源隔离方法
资源隔离最常用手段是Linux容器（Linux Container ，LXC）
k8s，docker容器
资源管理与调度系统范型
集中式调度器
整个系统只运行一个全局的中央调度器实例
单路径调度器，按照顺序调度任务、无并发性
多路径调度器，支持多种调度策略
实现逻辑复杂、可扩展性差、缺乏灵活性、并发性差。无法适应大规模集群系统
两级调度器
分为中央调度器和框架调度器
中央调度器可以看到集群中所有机器的可用资源并管理状态，粗粒度地资源调度方式
各计算框架根据自身计算任务的特性进一步细粒度的分配从中央调度器获得的各种资源。典型：Mesos、YARN、Hadoop On Demand
状态共享调度器
Google的Omega调度系统。每个计算框架都可以看到整个集群中的资源，竞争获取资源
资源调度策略
FIFO调度策略
公平调度器
多用户作业调度器，资源池。公平策略是最大最小公平算法（Max-Min）
能力调度器
延迟调度策略
主资源公平调度策略
Mesos
YARN
构件：一个资源管理器RM、每个作业一个的应用服务器AM、每个机器一个的节点管理器NM
RM负责全局资源管理，包括调度器、AM服务器AMS、Client-RM接口以及RM-NM接口
调度器主要提供各种公平和能力策略调度，支持可插拔方式
Client-RM接口负责按照一定协议管理客户提交的作业
RM-NM接口主要和各种机器的NM通过心跳方式进行通信，获知信息
AMS负载系统内所有AM的最初启动与运行状态管理
YARN的RM支持“抢占式调度”
分布式协调系统
Chubby锁服务
强调协调系统的可靠性与高可用性，而不追求处理读写的高吞吐量
系统架构
理论基础是Paxos一致性协议
Chubby是一种“粗粒度”的锁服务
Chubby服务是由客户端链接的库程序和多个“Chubby单元”构成，一般一个数据中心部署一个“Chubby单元”
Chubby单元通常包含5个服务器，Paxos协议选举出一台作为“主控服务器”。主控服务器由“任期”，称之为“主控服务器租约”（Master Lease）
数据模型
Chubby类似于文件系统的目录和文件管理系统，在此基础上提供针对目录和文件的锁服务
要求对文件内容一次性全读或写，对资源的同步管理
会话与KeepAlive机制
RPC调用
客户端缓存
为减少客户端与服务器之间的通信量，允许客户端在本地缓存，由Chubby保证数据一致性
Zookeeper
体系结构
高吞吐的分布式协调系统，可处理上万客户端的并发请求
ZAB原子广播协议选举作为主控服务器，其他作为从属服务器。多票仲裁方式选取主控服务器
主控服务器将更新操作序列化（读可以是任意服务器，更新只能通过主控服务器）
"重放日志"和"模糊快照"进行容错
重放日志（Replay log）：将更新操作先写入外存日志、再写入内存数据
模糊快照（Fuzzy Snapshot）：周期性对内存数据做快照，但不对内存加锁。因此可能存在做快照时发生变化，而无法体现即模糊
数据模型
类似传统文件系统，树形的层级目录结构，节点是Znode
Znode节点分持久节点和临时节点
API：create、delete、setData、getData、exists、getChildren、sync
应用场景
领导者选举，Leader Election
配置管理，Configuration Management
组成员管理，Group Membership
任务分配
锁管理
双向路障同步
子主题
分布式通信
序列化与远程过程调用框架
Protocol Buffer 、Thrift
Avro
消息队列
Kafka
应用层多播通信
Gossip协议
数据通道
大数据存储
分布式文件系统
Google文件系统GFS
HDFS
NameNode、DataNode、Secondary NameNode、客户端
Secondary NameNode 提供检查点功能服务的服务器
HA方案
1、第三方共享存储：保证任一时刻只有一个NN能够写入
2、DataNode，需要保证只有一个NN发出删除命令
3、客户端：需要保证同一时刻只能有一个NN对客户端请求发出正确响应
Cloudera提供了基于QJM（Quorum Journal Manager）的HA放啊
NameNode联盟
将一个大的命名空间分割子空间，分别由单独的NN管理，互相独立。所有DATANode被多个NN共享，
与命名子空间通过数据块管理层作为中介建立映射关系
子命名空间-》多个数据块池
HayStack
对象存储系统
元数据的减少存储量：1、由多个图片数据拼接成一个数据文件。2、只保留元数据必须的属性数据
HayStack读：内存读取元数据-》磁盘读取图片数据
逻辑卷对应多个物理卷，数据冗余
HayStack目录服务-》CDN\HayStack缓存系统\HayStack存储系统
文件存储布局
行式存储
列式存储
列族方式
Dremel的列存储方式
混合存储
RCFile、ORCFile、Parquet
纠删码，代替冗余备份、减少存储成本
Reed-Solomon编码，RS编码
缺点，数据恢复时大量传输造成网络阻塞
（n，m）RS编码表示n个数据块+m个冗余校验信息块，最多可允许m块数据损失
LRC编码
在RS编码基础上通过增加数据冗余来获取校验数据的局部性
HDFS-RAID架构
RaidNode：对DRFS中的文件建立和维护对应的校验数据文件
BlockFixer：周期性扫描文件系统，从已经经过RS编码的文件中识别出损毁数据，并对其进行恢复
内存KV数据库
内存里对数据进行备份
RAMCloud
大规模集群下的纯内存KV数据库
RAMCloud整体架构
数据副本管理
LSM树方案存储数据
RAMCloud数据副本管理
数据快速恢复
恢复机制一：待备份数据分散到多个备份服务器，恢复内存数据时每台仅需传递少量数据，增加并发性
恢复机制二：将待重建内存数据分散到堕胎服务器来恢复，减少每台服务器需要恢复的数据量，增加并发性
RAMCloud数据恢复机制
内存保留一份数据，数据备份放在磁盘或SSD中
Redis
单机读写
Redis Cluster 集群版本
采用异步的主从复制方式
主从切换，选举策略
Membase（CouchBase）
集群环境下的内存KV数据库
将所有数据的主键空间映射到4096个虚拟桶中，并在“虚拟桶映射表”中记载每个虚拟桶主副数据的机器地址。两阶段提交协议更新虚拟桶映射表
同步写
主服务器的虚拟桶出问题，备份服务器切换
内存存放副本数据成本太高。作者建议方案：副本存放LSM树结构存储的LevelDB数据库
列式数据库
BigTable，HBase数据库
BigTable的数据模型
三维映射表，最基础的存储单元由（行主键、列主键、时间）三维主键所定位
存储表格时，将表格按照行主键切割成一个个若干行数据的子表
BitTable的整体结构
主控服务器、子表服务器、客户端程序
整体结构
BigTable管理数据
Chubby系统和元数据表共同维护系统管理数据
元数据表包含Root子表（其他子表的存放位置）和其他子表。
其他子表的每一行的“行主键”是由用户表表名和对应子表最后一行的行主键共同构成
客户端请求，通过chubby系统-》Root子表-》元数据表的其他子表。三级查询结构，获取存储数据具体位置
BigTable主控服务器
管理工作：自动发现新的“子表服务器”、故障“子表服务器”、负载均衡
启动流程
“主控”和“子表”服务器通信，获取子表服务器存储了那些子表并记录在内存管理数据中
“主控”通过周期性地扫描Servers目录下文件获知“新子表服务器”的加入
“主控”周期性地询问“子表”状态
BigTable子表服务器
子表管理、子表恢复、子表分裂、子表合并、子表写、子表读
更新子表数据
首先，CommitLog文件，之后MemTable。最后落地SSTable。LSM树结构
SSTable分为存储区和索引区。二分查找定位数据位置
读子表数据
按照行主键顺序存储
布隆过滤器快速查找文件
子表合并：微合并、部分合并、主合并
子表恢复
元数据子表读取管理信息
CommitLog对应的恢复点
PNUTS存储系统
时间轴一致性保证数据一致性
雅虎消息代理更新备份记录
MegaStore
将大规模数据进行细粒度切割，切分成若干实体群组
在实体群组内提供满足ACID意义的强一致性服务
数据模型：Schema->Table->Property
MegaStore包含实体群组主表Root Table 和 Child Table
Paxos协议保证数据一致性
Spanner
特点：数据中心级别的容灾能力、类SQL查询语言、完善的事务支持、半结构化数据模型定义
TrueTime机制为分布式事务打上具有全局比较意义的时间戳
TT.now()返回一个时间区间TTinterval
收藏
0 条评论
下一页
