大数据日知录：架构与算法 跳转至： 导航、 搜索 目录 1 当谈论大数据时我们在谈论什么 2 数据分片与路由 3 数据复制与一致性 4 大数据常用算法与数据结构 5 集群资源管理与调度 6 分布式协调系统 7 分布式通信 8 数据通道 9 分布式文件系统 10 内存KV 11 列式数据库 12 大规模批处理 13 流式计算 14 交互式数据分析 15 图数据库 16 机器学习：范型与架构 17 机器学习：分布式算法＊ 18 增量计算 19 附录A 硬件体系结构及常用性能指标 20 附录B 大数据必读文献 当谈论大数据时我们在谈论什么 IBM 3V（体积、速度、形式）＋价值 p7 通过分析Twitter中的公众情绪，使用社交网络预测道琼斯指数的走势？ 数据分片与路由 MemBase（CouchBase）：“虚拟桶” DHT一致性哈希 Dynamo “虚拟节点” 数据复制与一致性 CAP：CP或AP？ ACID BASE 软状态=有状态/无状态之间的中间状态？ 一致性模型分类 强：所有进程在写操作之后立即看到最新的取值？ 最终：“不一致窗口”（这个时间片段能够保证吗？否则太见鬼了） 单调读：如果读到数据的某个版本v，则所有后续操作都不能看到比v更老的版本（如何定义这个‘后续’？） 单调写：保证多次写操作的序列化？ 因果 “读你所写” 会话 副本更新策略 一致性协议 2PC：协调者/参与者 3PC：解决2PC存在长时阻塞的问题，将提交阶段分为预提交和提交 向量时钟 用于判断事件之间是否存在因果关系 RWN（数据一致性：R+W>N） Paxos 保证Log副本数据的一致性？ Raft 3个子问题：领导者选举、Log复制、安全性 Term？ 大数据常用算法与数据结构 Bloom Filter 计数BF：基本信息单元由多个比特位表示 SkipList：随机的查找/插入？ LSM树：把大量的随机写转换成批量的序列写 e.g. LevelDB Merkle哈希树（BitTorrent？哈） LZSS Snappy：匹配长度>=4 Cuckoo哈希 用2个哈希函数，如果2个对应桶都不为空，则踢出老元素，同时对老元素重新执行插入 => 无限循环？重新选择hash函数 应用：CMU SILT 集群资源管理与调度 调度系统范型 集中式 两级 状态共享 资源调度策略 FIFO 公平 能力 延迟 主资源公平（DRF）：最大化目前分配到最少资源的用户的资源量 Mesos：两级调度 YARN：支持抢占 分布式协调系统 Chubby锁服务 p93 如无故障，一般情况下系统还是尽量将租约交给原先的主控服务器 KeepAlive机制 每个“Chubby单元”的主控服务器将内存快照存储到另一个数据中心，避免了循环依赖？ ZooKeeper 可能读到过期数据 => 读之前Sync操作 重放日志结合模糊快照（Fuzzy Snapshot）？ ZNode：持久/临时 分布式通信 序列化与RPC框架 PB与Thrift Avro：用JSON描述IDL？ 消息队列 ZeroMQ（轻量，不支持消息持久化） > Kafka（至少送达一次） > RabbitMQ > ActiveMQ？ ISR（In-Sync Replicas） 应用层多播 Gossip 反熵模型（随机泛洪？）：Push/Pull/Push-Pull p117 如果将节点P通知Q时发现Q已经更新理解为“表白被拒绝”，则散布谣言模型可理解为：被拒绝的次数越多越沉默，到后来完全死心不再表白。缺点：不能保证所有节点最终获得更新（嗯，最大匹配并不是追求目标！） 应用：Cassandra集群管理 数据通道 Log收集：Chukwa Scribe 数据总线：Databus Wormhole 导入导出：Sqoop？ 分布式文件系统 GFS 下一代Colossus？ HDFS HA方案：ANN/SNN HayStack：合并小图片数据、减少“元数据”属性 存储布局：行式 列式 混合 Dremel列存储：Name.Language.Code？（数据项，重复层，定义层）？ 混合存储：RCFile、ORCFile、Parquet 纠删码/MDS* Reed-Solomon LRC 块局部性 与 最小码距：对(n,m)配置的MDS来说，分别是>=n和m+1 内存KV RAMCloud Redis MemBase 列式数据库 BigTable PNUTS MegaStore Spanner TrueTime：TT.now()返回一个时间区间，保证事件真实发生的时间一定落在这个区间内？ 大规模批处理 MapReduce Map任务把中间数据分成R份，然后通知Reduce任务来取（只有所有Map任务都完成，Reduce才能启动？） Reduce端Pull，而非Map端Push，可支持细粒度容错（精辟！！实际上是同步阻塞模式变成了异步触发） Reduce任务将中间结果Key有序的数据转换为>传给用户定义的reduce函数 注意，这里用户reduce操作的是全局的数据（可能涉及远程访问...） 可选的Combiner：即Map端合并相同key的value，减少了网络传输量 计算模式 求和 过滤 组织数据（Partition策略设计） Join Reduce-Side（注意，2个数据集合的key是一样的，不同的是value的类型，reducer需要做区分） 这个地方还是有点不明白，reducer收到的数据太多、内存装不下怎么办？ Map-Side（假设L大R小，左连接？，将R完全读入内存） DAG Dryad 图结构描述（分布式计算框架：如何根据一个全局的图描述自动创建各个计算节点及拓扑连接？） FlumeJava和Tez＊ 流式计算 系统架构 主从：Storm P2P：S4 Samza DAG拓扑结构（这里的拓扑构造倒是与DirectShow FilterGraph很相似） 计算节点 数据流：MillWheel (Key, Value, TimeStamp)；Storm (Tuple,...)；S4 [Key, Attributes] 送达保证 Storm“送达一次”：XOR MillWheel的：通过状态持久化（相当于C函数里的静态局部变量。。。） 状态持久化 MillWheel和Samza的：弱方式（节点B只有收到下游节点C发回的ACK，才能给上游A发送ACK） =>如果C没有及时回应，则B执行一次状态持久化，摆脱对C的依赖 Samza：某个计算节点可将其状态信息作为Kafka的一个消息队列 交互式数据分析 Hive Stinger改进：向量查询引擎、CBO Shark “部分DAG执行引擎”，本质上是对SQL查询的动态优化 数据共同分片：将要进行Join的列通过hash把相同Key的不同记录放到同一台机器，后续可避免Shuffle等网络传输开销 Dremel系 Dremel：不是将用户查询转换为MR任务，而是类MPP机制对存储在磁盘中的数据直接扫描（高级编译技术？） PowerDrill：将待分析的数据加载到内存？通过精巧的数据结构跳过无关数据？ Impala p262 Impalad使用C++编码，绕过NameNode直接读取HDFS，查询执行时采用LLVM本地代码生成（ＮＢ！） 虽然看起来不错，但仍需要进一步改进（容错、UDF） 操作符：Scan、HashJoin、HashAggregateion、Union、TopN、Exchange Presto（与Impala类似） 混合系：HadoopDB 图数据库 在线查询类 三层结构 Facebook TAO ＊数据一致性 常见图挖掘问题 PageRank 单源最短路径 二部图最大匹配 图数据分片 边切／点切：优化问题，实际中都是随机切分？ 计算模型 以节点为中心 GAS（收集-应用-分发） 同步执行 BSP MapReduce（反复迭代需要多次将中间结果输出到文件系统，影响系统效率） 异步执行 数据一致性：完全 > 边 > 顶点；序列一致性（额外的约束） 图数据库：Pregel Giraph（Map-Only, Netty） GraphChi（单机，并行滑动窗口PSW） PowerGraph（增量缓存） 机器学习：范型与架构 分布式机器学习 MapReduce BSP 每个超级步：分布计算>全局通信>路障同步 SSP ？ Spark与MLBase 参数服务器＊ 机器学习：分布式算法＊ 逻辑回归 并行随机梯度下降 矩阵分解：ALS-WR LambdaMART 谱聚类 深度学习：DistBelief 增量计算 Percolator p371 “快照隔离”，可解决写冲突？ Kineograph DryadInc 附录A 硬件体系结构及常用性能指标 附录B 大数据必读文献