《BIG DATA大数据日知录 架构和算法》读书笔记

1.数据分片和路由

• Hash
  • Hash
    • H(Key) = hash(key) mod K
  • 虚拟桶（Virtual Buckets）
    • 先hash到桶，在Hash，多加一层Hash便于扩展
  • 一致性Hash
    • 分布式Hash表（DHT），P2P对等网络，构成环，节点加入和离开自动调整
• 范围
  • 如HBase中的LSM树

2.数据复制和一致性

• 基本原则
  • CAP（强一致性、可用性和分区容忍性），CP、AP，涉及到网络分区的（P），CAP不可兼得
  • ACID（原子、一致、隔离、持久）
  • BASE（基本可用B允许偶尔失败、软状态Soft State、最终一致性Eventual Consistency）
    • BASE原则是牺牲一致性达到高可用
  • 幂等性（f(f(x)) = f(x)），反复调用，状态正确
• 一致性模型
  • 强一致性
  • 最终一致性，一个时间窗口内数据允许不一致
  • 因果一致性
• 副本更新策略 *
• 一致性协议
  • 两阶段提交协议（2PC）
  • 向量时钟（Vector Clock）
  • RWN协议（成功读取R +　成功写入W > 数据备份数N）
  • Paxos协议
    • 安全、可用
    • 副本状态机、Log
    • Proposer、Acceptor、Learner
  • Raft协议
    • 可理解、确定

3.常用算法和数据结构

• Bloom Filter布隆过滤器
  • 用位表示元素是否存在，1到多个独立的hash，空间效率极高
  • 改进，加入计数，用于删除成员
• Skip List跳跃表
  • 可替代平衡二叉树，O(Log(n))
• LSM树
  • 大量随机写，转化为批量顺序写
• Merkle哈希树
  • 层级的hash树
  • 快速定位数据变化部分
  • 比特币
• Snappy和LZSS压缩算法
• Cuckoo哈希
  • 采用交换解决hash冲突

4.集群资源管理和调度

• 要解决的基本问题
  • 资源异质性、工作负载异质性，即组成元素差异较大
  • 数据局部性
  • 抢占式调度和非抢占式调度
  • 资源分配粒度，Job还是Task
  • Starvation和Dead Lock
  • 资源隔离
• 资源管理和调度泛型
  • 集中式调度器、Borg
  • 两级调度器，mesos、YARN
  • 状态共享调度器、Omega
• Mesos
• YARN
  • RM，资源管理器，Resource Manager
  • AM，作业的应用服务器，Application Manager
  • NM，每个机器的节点服务器，Node Manager

5.分布式协调系统

• Chubby，Google
  • 基于Paxos一致性协议
• ZooKeeper
  • 可扩展、高吞吐、分布式协调系统
  • 应用场景：领导选举、配置管理、组成员管理、任务分配、锁管理
  • HBase、Storm、Solr、Kafka...

6.分布式通信

• 序列化、反序列化
  • Protocol Buffer
  • Thrift
  • Avro，json定义schema
• 消息队列
  • Kafka
• 多播通信（Application-Level Multi-broadcast）
  • Gossip协议，Epidemic Protocol感染协议，如Cassandra维护机器节点状态

7.数据通道

• Log采集
  • Chukwa，基于Hadoop
  • Scribe，Facebook
• 数据总线，数据变化通知通道，一般基于数据库日志挖掘
  • Databus、LinkedIn
  • Wormhole、Facebook
• 数据导入导出
  • Sqoop，hadoop和其他关系或者nosql之前的导入导出

8.分布式文件系统

• GFS，Google
  • Colossus，下一次GFS
• HDFS，Hadoop
• HayStack，对象存储系统，Facebook
• Erasure Code 纠删码
  • 减少数据备份，提供可靠性
  • Reed-Solomon编码
  • LRC编码
  • HDFS-RAID架构

9.内存kv数据库

• RAMCloud
• Redis
• MemBase，CouchBase

10.列数据库

• BigTable
• PNUTS
• MegaStore
• Spanner
• BigTable在跨行、跨表的强一致性需求场景表现不佳，MegaStore一定程度上缓解，但是写性能不佳，Spanner进一步升级，支持类SQL和事务

11.大规模批处理系统

• MapReduce
  • 求和，Summarization Pattern
  • 过滤，Filtering Pattern，top10等
  • 组织数据，Data Organization Pattern，分片、排序
  • Join模式，Join Pattern，Reduce-Side、Map-Side Join
• DAG计算模型
  • Dryad，微软
  • FlumeJava，Google
  • Tez，Apache

12.流式计算

• 架构
  • 主从，Store
  • P2P，S4
  • Samza

13.交互式数据分析

• Hive系，Facebook
  • SQL-on-Hadoop
  • 耦合Hadoop导致效率低下
  • StingerIntiative，改进Hive
• Shark系
  • 基于Spark
• Dremel系，需要关注
  • Dremel、PowerDrill、Impala、Presto
• 混合
  • Hadoop DB

14.图数据库：架构和算法

• 图挖掘问题
  • PageRank计算
  • 单源最短路径
  • 二部图最大匹配
• 在线
  • TAO， Facebook
• 离线
  • Pregel，Google
  • Giraph，基于Hadoop的开源版本
  • GraphChi
  • PowerGraph

15.机器学习：泛型和架构

• 概念
  • 监督学习，分类、回归
  • 非监督学习，聚类
• 分布式学习泛型
  • 同步泛型
  • 异步泛型
  • 部分同步泛型
• 计算模型
  • mapreduce迭代计算模型
  • BSP，整体同步并行计算
  • SSP，部分同步
• 架构
  • Hadoop
    • 利用平台，Oryx Cloudera, Mahout Apache
    • 改造平台，Twister, Haloop
  • Spark及MLBase *
  • Parameter Server
    • DistBelief
    • Petuum

16.机器学习：分布式算法

• 计算广告
  • 逻辑回归
  • 并行随机梯度下降
  • 批学习并行逻辑回归
• 推荐系统
  • 矩阵分解
  • ALS-WR算法
  • 并行ALS-WR算法
• 搜索引擎
  • 机器学习排序
  • LambdaMART
  • 分布式LambdaMART
• 自然语言处理
  • 文档相似性计算
• 社交挖掘
  • 谱聚类
  • 并行谱聚类
• 深度学习
  • DistBelief

17.增量计算

• Percolator
• Kineograph
• DryadInc

http://my.oschina.net/serverx/blog/693701