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

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

大数据日知录：架构与算法
跳转至： 导航、 搜索
目录

    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有序的数据转换为<key, List<value>>传给用户定义的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 大数据必读文献 

简单了...