『大数据日知录:架构与算法』知识点记录

最近读了『大数据日知录:架构与算法』这本书。感觉讲的东西很多,大数据平台及大数据分析常用的一些模型、架构、算法均有涉及,偏基础和底层。但是并不是特别系统,总体而言更像是作者自己的学习笔记整理,没有一条主线串联起来。加上作者文笔感觉一般,很多东西表达的不是很好理解,对于初涉大数据领域的我来说,各种概念、术语扑面而来,一时半会有点消化吸收不能,因此整理一个要点列表,待日后慢慢回味。

第一章:数据分片与路由

哈希分片(Hash Partition)

分为三种。

  • Round Robin
  • 虚拟桶(Virtual Buckets)
  • 一致性哈希(Consistent Hashing)
    • 分布式哈希表(DHT)
    • 一致性哈希路由算法

范围分片

第二章:数据复制与一致性

CAP

三者不可得兼

  • 强一致性(Consistency)
  • 可用性(Availability)
  • 分去容忍性(Partition Tolerance)

CAP Reloaded

  • ACID 原则
    • 原子性(Atomicity)
    • 一致性(Consistency)
    • 事务独立(Isolation)
    • 持久性(Durability)
  • BASE 原则
    • 基本可用(Basically Available)
    • 软状态/柔性状态(Soft State)
    • 最终一致性(Eventual Consistency)
  • 幂等性(Idempotent)

一致性模型

  • 强一致性
  • 最终一致性
  • 因果一致性
  • 「读你所写」一致性
  • 会话一致性
  • 单调读一致性
  • 单调写一致性

副本更新策略

  • 同时更新
  • 主从式更新
  • 任意节点更新

一致性协议

  • 两段式提交(Two-Phrase Commit,2PC)
    • vote -> commit
  • 三段式提交/3PC
    • 2PC 的改进
  • 向量时钟(Vector Clock)
  • Paxos 协议

第三章:大数据常用的算法与数据结构

Bloom Filter

用于判断数据是否存在某个巨大数据集中

SkipList

快速遍历

LSM 树

写操作效率高

Merkle 哈希树(Merkle Hash Tree)

快速侦测部分数据变动

Snappy 与 LZSS 算法

基于动态辞典编码的数据压缩算法

Cuckoo 哈希(Cuckoo Hashing)

第四章:集群资源管理与调度

调度系统设计

  • 资源异质性与工作负载异质性
  • 数据局部性(Data Locality)
  • 抢占式调度/非抢占式调度
  • 资源分配粒度(Allocation Granularity)
  • 饿死(Starvation)与死锁(Dead Lock)

资源管理与调度系统范型

  • 集中式器
  • 两级调度器
  • 状态共享调度器

调度策略

  • FIFO
  • 公平调度器(Fair Scheduler)
  • 能力(Capacity)调度器
  • 延迟调度策略
  • 主资源公平调度策略

实现

  • Mesos
  • YARN

第五章:分布式协调系统

Chubby 锁服务

ZooKeeper

第六章:分布式通信

序列化与远程过程调用框架

  • Protocol Buffer/Thrift
  • Avro

消息队列

  • Kafka

应用层多播通信

  • Gossip 协议

第七章:数据通道

Log 数据收集

  • Chukwa
  • Scribe

数据总线

  • Databus
  • Wormhole

数据导入导出

  • Sqoop

第八章:分布式文件系统

Google 文件系统(GFS)

HDFS

HeyStack 存储系统

文件存储布局

  • 行式存储
  • 列式存储
    • 列族
    • Dremel
  • 混合式存储
    • RCFile
    • ORCFile
    • Parquet

纠删码(Erasure Code)

  • Reed-Solomon
  • LRC
  • HDFS-RAID

第九章:内存 KV 数据库

RAMCloud

Redis

MemBase

第十章:列式数据库

BigTable

PNUTS

MegaStore

Spanner

第十一章:大规模批处理系统

MapReduce

  • 计算模式
    • 求和模式
    • 过滤模式
    • 组织数据模式
    • JOIN 模式

DAG 计算模型

  • Dryad
  • FlumeJava/Tez

第十二章:流式计算

系统架构

  • 主从
  • P2P
  • Samza

DAG 拓扑结构

送达保证

  • At-Least Once
  • At-Most Once
  • Exact-Once

状态持久化

  • 容错模式
    • Standby
    • Hot Standby
    • Checkpointing

第十三章:交互式数据分析

Hive

  • HiveSQL
  • Stinger Initiative

Shark

  • 部分 DAG 执行引擎(PDE)

Dremel

  • PowerDrill
  • Impala
  • Presto

混合式

第十四章:图数据库:架构与算法

在线查询类图数据库

  • TAO 图数据库

常见图挖掘问题

  • PageRank
  • 单源最短路径(Single Source Shortest Path)
  • 二部图最大匹配

离线挖掘数据分片

  • 切边法(Edge-Cut)
  • 切点法(Vertex-Cut)

离线挖掘数据模型

  • 节点为中心
  • GAS 编程模型
  • 同步执行模型
  • 异步执行模型

离线挖掘图数据库

  • Pregel
  • Giraph
  • GraphChi
  • PowerGraph

第十五章:机器学习:范型与架构

分布式机器学习

  • 数据并行
  • 模型并行

分布式机器学习范型

  • 三种范型
    • 同步范型
    • 异步范型
    • 部分同步范型
  • MapReduce 迭代计算模型
  • BSP 计算模型
  • SSP 模型

分布式机器学习架构

  • MapReduce 系列
  • Spark & MLBase
  • 参数服务器

第十六章:机器学习:分布式算法

广告(逻辑回归)

  • 逻辑回归(Logistic Regression,LR)
  • 并行随机梯度下降(Parallel Stochastic Gradient Descent)
  • 批学习并行逻辑回归

推荐系统(矩阵分解)

  • 矩阵分解
  • ALS-WR
  • 并行版 ALS-WR

搜索引擎(排序)

  • 机器学习排序
  • LambdaMART
  • 分布式 LambdaMART

NLP

  • 文档相似性计算

社交挖掘

  • 谱聚类

深度学习

  • DistBelief

第十七章:增量计算

增量计算模式

Percolator

Kineograph

DryadInc