首页 > 代码库 > 大数据日知录:架构与算法 笔记

大数据日知录:架构与算法 笔记

大数据日知录:架构与算法

跳转至: 导航、 搜索

目录

  • 1当谈论大数据时我们在谈论什么
  • 2数据分片与路由
  • 3数据复制与一致性
  • 4大数据常用算法与数据结构
  • 5集群资源管理与调度
  • 6分布式协调系统
  • 7分布式通信
  • 8数据通道
  • 9分布式文件系统
  • 10内存KV
  • 11列式数据库
  • 12大规模批处理
  • 13流式计算
  • 14交互式数据分析
  • 15图数据库
  • 16机器学习:范型与架构
  • 17机器学习:分布式算法*
  • 18增量计算
  • 19附录A 硬件体系结构及常用性能指标
  • 20附录B 大数据必读文献

当谈论大数据时我们在谈论什么

  1. IBM 3V(体积、速度、形式)+价值
  2. p7 通过分析Twitter中的公众情绪,使用社交网络预测道琼斯指数的走势?

数据分片与路由

  1. MemBase(CouchBase):“虚拟桶”
  2. DHT一致性哈希
    1. Dynamo “虚拟节点”

数据复制与一致性

  1. CAP:CP或AP?
  2. ACID
  3. BASE
    1. 软状态=有状态/无状态之间的中间状态?
  4. 一致性模型分类
    1. 强:所有进程在写操作之后立即看到最新的取值?
    2. 最终:“不一致窗口”(这个时间片段能够保证吗?否则太见鬼了)
      1. 单调读:如果读到数据的某个版本v,则所有后续操作都不能看到比v更老的版本(如何定义这个‘后续’?)
      2. 单调写:保证多次写操作的序列化?
    3. 因果
      1. “读你所写”
        1. 会话
  5. 副本更新策略
  6. 一致性协议
    1. 2PC:协调者/参与者
      1. 3PC:解决2PC存在长时阻塞的问题,将提交阶段分为预提交和提交
    2. 向量时钟
      1. 用于判断事件之间是否存在因果关系
    3. RWN(数据一致性:R+W>N)
    4. Paxos
      1. 保证Log副本数据的一致性?
    5. Raft
      1. 3个子问题:领导者选举、Log复制、安全性
      2. Term?

大数据常用算法与数据结构

  1. Bloom Filter
    1. 计数BF:基本信息单元由多个比特位表示
  2. SkipList:随机的查找/插入?
  3. LSM树:把大量的随机写转换成批量的序列写
    1. e.g. LevelDB
  4. Merkle哈希树(BitTorrent?哈)
  5. LZSS
    1. Snappy:匹配长度>=4
  6. Cuckoo哈希
    1. 用2个哈希函数,如果2个对应桶都不为空,则踢出老元素,同时对老元素重新执行插入 => 无限循环?重新选择hash函数
    2. 应用:CMU SILT

集群资源管理与调度

  1. 调度系统范型
    1. 集中式
    2. 两级
    3. 状态共享
  2. 资源调度策略
    1. FIFO
    2. 公平
    3. 能力
    4. 延迟
    5. 主资源公平(DRF):最大化目前分配到最少资源的用户的资源量
  3. Mesos:两级调度
  4. YARN:支持抢占

分布式协调系统

  1. Chubby锁服务
    1. p93 如无故障,一般情况下系统还是尽量将租约交给原先的主控服务器
    2. KeepAlive机制
    3. 每个“Chubby单元”的主控服务器将内存快照存储到另一个数据中心,避免了循环依赖?
  2. ZooKeeper
    1. 可能读到过期数据 => 读之前Sync操作
    2. 重放日志结合模糊快照(Fuzzy Snapshot)?
    3. ZNode:持久/临时

分布式通信

  1. 序列化与RPC框架
    1. PB与Thrift
    2. Avro:用JSON描述IDL?
  2. 消息队列
    1. ZeroMQ(轻量,不支持消息持久化) > Kafka(至少送达一次) > RabbitMQ > ActiveMQ?
      1. ISR(In-Sync Replicas)
  3. 应用层多播
    1. Gossip
      1. 反熵模型(随机泛洪?):Push/Pull/Push-Pull
      2. p117 如果将节点P通知Q时发现Q已经更新理解为“表白被拒绝”,则散布谣言模型可理解为:被拒绝的次数越多越沉默,到后来完全死心不再表白。缺点:不能保证所有节点最终获得更新(嗯,最大匹配并不是追求目标!)
      3. 应用:Cassandra集群管理

数据通道

  1. Log收集:Chukwa Scribe
  2. 数据总线:Databus Wormhole
  3. 导入导出:Sqoop?

分布式文件系统

  1. GFS
    1. 下一代Colossus?
  2. HDFS
    1. HA方案:ANN/SNN
  3. HayStack:合并小图片数据、减少“元数据”属性
  4. 存储布局:行式 列式 混合
    1. Dremel列存储:Name.Language.Code?(数据项,重复层,定义层)?
    2. 混合存储:RCFile、ORCFile、Parquet
  5. 纠删码/MDS*
    1. Reed-Solomon
    2. LRC
      1. 块局部性 与 最小码距:对(n,m)配置的MDS来说,分别是>=n和m+1

内存KV

  1. RAMCloud
  2. Redis
  3. MemBase

列式数据库

  1. BigTable
  2. PNUTS
  3. MegaStore
  4. Spanner
    1. TrueTime:TT.now()返回一个时间区间,保证事件真实发生的时间一定落在这个区间内?

大规模批处理

  1. MapReduce
    1. Map任务把中间数据分成R份,然后通知Reduce任务来取(只有所有Map任务都完成,Reduce才能启动?)
      1. Reduce端Pull,而非Map端Push,可支持细粒度容错(精辟!!实际上是同步阻塞模式变成了异步触发)
      2. Reduce任务将中间结果Key有序的数据转换为<key, List<value>>传给用户定义的reduce函数
        1. 注意,这里用户reduce操作的是全局的数据(可能涉及远程访问...)
    2. 可选的Combiner:即Map端合并相同key的value,减少了网络传输量
    3. 计算模式
      1. 求和
      2. 过滤
      3. 组织数据(Partition策略设计)
      4. Join
        1. Reduce-Side(注意,2个数据集合的key是一样的,不同的是value的类型,reducer需要做区分)
          1. 这个地方还是有点不明白,reducer收到的数据太多、内存装不下怎么办?
        2. Map-Side(假设L大R小,左连接?,将R完全读入内存)
  2. DAG
    1. Dryad
      1. 图结构描述(分布式计算框架:如何根据一个全局的图描述自动创建各个计算节点及拓扑连接?)
    2. FlumeJava和Tez*

流式计算

  1. 系统架构
    1. 主从:Storm
    2. P2P:S4
    3. Samza
  2. DAG拓扑结构(这里的拓扑构造倒是与DirectShow FilterGraph很相似)
    1. 计算节点
    2. 数据流:MillWheel (Key, Value, TimeStamp);Storm (Tuple,...);S4 [Key, Attributes]
  3. 送达保证
    1. Storm“送达一次”:XOR
    2. MillWheel的:通过状态持久化(相当于C函数里的静态局部变量。。。)
  4. 状态持久化
    1. MillWheel和Samza的:弱方式(节点B只有收到下游节点C发回的ACK,才能给上游A发送ACK)
      1. =>如果C没有及时回应,则B执行一次状态持久化,摆脱对C的依赖
      2. Samza:某个计算节点可将其状态信息作为Kafka的一个消息队列

交互式数据分析

  1. Hive
    1. Stinger改进:向量查询引擎、CBO
  2. Shark
    1. “部分DAG执行引擎”,本质上是对SQL查询的动态优化
    2. 数据共同分片:将要进行Join的列通过hash把相同Key的不同记录放到同一台机器,后续可避免Shuffle等网络传输开销
  3. Dremel系
    1. Dremel:不是将用户查询转换为MR任务,而是类MPP机制对存储在磁盘中的数据直接扫描(高级编译技术?)
    2. PowerDrill:将待分析的数据加载到内存?通过精巧的数据结构跳过无关数据?
    3. Impala
      1. p262 Impalad使用C++编码,绕过NameNode直接读取HDFS,查询执行时采用LLVM本地代码生成(NB!)
      2. 虽然看起来不错,但仍需要进一步改进(容错、UDF)
      3. 操作符:Scan、HashJoin、HashAggregateion、Union、TopN、Exchange
    4. Presto(与Impala类似)
  4. 混合系:HadoopDB

图数据库

  1. 在线查询类
    1. 三层结构
    2. Facebook TAO
      1. *数据一致性
  2. 常见图挖掘问题
    1. PageRank
    2. 单源最短路径
    3. 二部图最大匹配
  3. 图数据分片
    1. 边切/点切:优化问题,实际中都是随机切分?
  4. 计算模型
    1. 以节点为中心
    2. GAS(收集-应用-分发)
    3. 同步执行
      1. BSP
      2. MapReduce(反复迭代需要多次将中间结果输出到文件系统,影响系统效率)
    4. 异步执行
      1. 数据一致性:完全 > 边 > 顶点;序列一致性(额外的约束)
  5. 图数据库:Pregel Giraph(Map-Only, Netty) GraphChi(单机,并行滑动窗口PSW) PowerGraph(增量缓存)

机器学习:范型与架构

  1. 分布式机器学习
    1. MapReduce
    2. BSP
      1. 每个超级步:分布计算>全局通信>路障同步
    3. SSP ?
  2. Spark与MLBase
  3. 参数服务器*

机器学习:分布式算法*

  1. 逻辑回归
  2. 并行随机梯度下降
  3. 矩阵分解:ALS-WR
  4. LambdaMART
  5. 谱聚类
  6. 深度学习:DistBelief

增量计算

  1. Percolator
    1. p371 “快照隔离”,可解决写冲突?
  2. Kineograph
  3. DryadInc

附录A 硬件体系结构及常用性能指标

附录B 大数据必读文献 

大数据日知录:架构与算法 笔记