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

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

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本地代码生成（ＮＢ！）
      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 大数据必读文献