大数据日知录：架构与算法 PDF 高清版

大数据是当前最为流行的热点概念之一，其已由技术名词衍生到对很多行业产生颠覆性影响的社会现象，作为最明确的技术发展趋势之一，基于大数据的各种新型产品必将会对每个人的日常生活产生日益重要的影响。

《大数据日知录：架构与算法》从架构与算法角度全面梳理了大数据存储与处理的相关技术。大数据技术具有涉及的知识点异常众多且正处于快速演进发展过程中等特点，其技术点包括底层的硬件体系结构、相关的基础理论、大规模数据存储系统、分布式架构设计、各种不同应用场景下的差异化系统设计思路、机器学习与数据挖掘并行算法以及层出不穷的新架构、新系统等。《大数据日知录：架构与算法》对众多纷繁芜杂的相关技术文献和系统进行了择优汰劣并系统性地对相关知识分门别类地进行整理和介绍，将大数据相关技术分为大数据基础理论、大数据系统体系结构、大数据存储，以及包含批处理、流式计算、交互式数据分析、图数据库、并行机器学习的架构与算法以及增量计算等技术分支在内的大数据处理等几个大的方向。通过这种体系化的知识梳理与讲解，相信对于读者整体和系统地了解、吸收和掌握相关的优秀技术有极大的帮助与促进作用。

目录

• 第0 章 当谈论大数据时我们在谈什么 1
• 0.1 大数据是什么 2
• 0.2 大数据之翼：技术范型转换 4
• 0.3 大数据商业炼金术 6
• 0.4 “大数据”在路上 7
• 第1 章 数据分片与路由 9
• 1.1 抽象模型10
• 1.2 哈希分片（Hash Partition） 11
• 1.2.1 Round Robin11
• 1.2.2 虚拟桶（Virtual Buckets） 12
• 1.2.3 一致性哈希（Consistent Hashing） 13
• 1.3 范围分片（Range Partition） 18
• 参考文献19
• 第2 章 数据复制与一致性20
• 2.1 基本原则与设计理念21
• 2.1.1 原教旨CAP 主义21
• 2.1.2 CAP 重装上阵（CAP Reloaded）23
• 2.1.3 ACID 原则24
• 2.1.4 BASE 原则24
• 2.1.5 CAP/ACID/BASE 三者的关系25
• 2.1.6 幂等性（Idempotent）26
• 2.2 一致性模型分类26
• 2.2.1 强一致性27
• 2.2.2 最终一致性28
• 2.2.3 因果一致性28
• 2.2.4 “读你所写”一致性29
• 2.2.5 会话一致性29
• 2.2.6 单调读一致性30
• 2.2.7 单调写一致性30
• 2.3 副本更新策略30
• 2.3.1 同时更新30
• 2.3.2 主从式更新31
• 2.3.3 任意节点更新32
• 2.4 一致性协议32
• 2.4.1 两阶段提交协议（Two—Phrase Commit，2PC）33
• 2.4.2 向量时钟（Vector Clock） 38
• 2.4.3 RWN 协议40
• 2.4.4 Paxos 协议42
• 2.4.5 Raft 协议45
• 参考文献49
• 第3 章 大数据常用的算法与数据结构51
• 3.1 布隆过滤器（Bloom Filter） 51
• 3.1.1 基本原理52
• 3.1.2 误判率及相关计算52
• 3.1.3 改进：计数Bloom Filter53
• 3.1.4 应用54
• 3.2 SkipList55
• 3.3 LSM 树58
• 3.4 Merkle 哈希树（Merkle Hash Tree） 62
• 3.4.1 Merkle 树基本原理62
• 3.4.2 Dynamo 中的应用63
• 3.4.3 比特币中的应用63
• 3.5 Snappy 与LZSS 算法65
• 3.5.1 LZSS 算法65
• 3.5.2 Snappy67
• 3.6 Cuckoo 哈希（Cuckoo Hashing） 67
• 3.6.1 基本原理68
• 3.6.2 应用：SILT 存储系统68
• 参考文献70
• 第4 章 集群资源管理与调度71
• 4.1 资源管理抽象模型72
• 4.1.1 概念模型72
• 4.1.2 通用架构73
• 4.2 调度系统设计的基本问题74
• 4.2.1 资源异质性与工作负载异质性74
• 4.2.2 数据局部性（Data Locality） 75
• 4.2.3 抢占式调度与非抢占式调度75
• 4.2.4 资源分配粒度（Allocation Granularity） 76
• 4.2.5 饿死（Starvation）与死锁（Dead Lock）问题76
• 4.2.6 资源隔离方法77
• 4.3 资源管理与调度系统范型77
• 4.3.1 集中式调度器（Monolithic Scheduler）78
• 4.3.2 两级调度器（Two—Level Scheduler） 79
• 4.3.3 状态共享调度器（Shared—State Scheduler） 79
• 4.4 资源调度策略81
• 4.4.1 FIFO 调度策略81
• 4.4.2 公平调度器（Fair Scheduler）81
• 4.4.3 能力调度器（Capacity Scheduler） 82
• 4.4.4 延迟调度策略（Delay Scheduling）82
• 4.4.5 主资源公平调度策略（Dominant Resource Fair Scheduling）82
• 4.5 Mesos 84
• 4.6 YARN87
• 参考文献90
• 第5 章 分布式协调系统91
• 5.1 Chubby 锁服务92
• 5.1.1 系统架构93
• 5.1.2 数据模型94
• 5.1.3 会话与KeepAlive 机制95
• 5.1.4 客户端缓存95
• 5.2 ZooKeeper 96
• 5.2.1 体系结构96
• 5.2.2 数据模型（Data Model） 97
• 5.2.3 API 98
• 5.2.4 ZooKeeper 的典型应用场景98
• 5.2.5 ZooKeeper 的实际应用103
• 参考文献104
• 第6 章 分布式通信106
• 6.1 序列化与远程过程调用框架107
• 6.1.1 Protocol Buffer 与Thrift 108
• 6.1.2 Avro109
• 6.2 消息队列110
• 6.2.1 常见的消息队列系统110
• 6.2.2 Kafka 111
• 6.3 应用层多播通信（Application—Level Multi—Broadcast）114
• 6.3.1 概述114
• 6.3.2 Gossip 协议115
• 参考文献118
• 第7 章 数据通道120
• 7.1 Log 数据收集120
• 7.1.1 Chukwa121
• 7.1.2 Scribe122
• 7.2 数据总线123
• 7.2.1 Databus125
• 7.2.2 Wormhole 127
• 7.3 数据导入/导出128
• 参考文献129
• 第8 章 分布式文件系统131
• 8.1 Google 文件系统（GFS） 132
• 8.1.1 GFS 设计原则132
• 8.1.2 GFS 整体架构133
• 8.1.3 GFS 主控服务器134
• 8.1.4 系统交互行为136
• 8.1.5 Colossus 137
• 8.2 HDFS 138
• 8.2.1 HDFS 整体架构139
• 8.2.2 HA 方案140
• 8.2.3 NameNode 联盟143
• 8.3 HayStack 存储系统145
• 8.3.1 HayStack 整体架构146
• 8.3.2 目录服务147
• 8.3.3 HayStack 缓存148
• 8.3.4 HayStack 存储系统的实现148
• 8.4 文件存储布局150
• 8.4.1 行式存储151
• 8.4.2 列式存储151
• 8.4.3 混合式存储156
• 8.5 纠删码（Erasure Code）158
• 8.5.1 Reed—Solomon 编码159
• 8.5.2 LRC 编码164
• 8.5.3 HDFS—RAID 架构166
• 参考文献166
• ……
• 第9 章 内存KV 数据库168
• 第10 章 列式数据库176
• 第11 章 大规模批处理系统199
• 第12 章 流式计算219
• 第13 章 交互式数据分析240
• 第14 章 图数据库：架构与算法271
• 第15 章 机器学习：范型与架构313
• 第16 章 机器学习：分布式算法337
• 第17 章 增量计算366
• 附录A 硬件体系结构及常用性能指标378
• 附录B 大数据必读文献380