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

图书标准信息

• 作者 张俊林 著
• 出版社 电子工业出版社
• 出版时间 2014-09
• 版次 1
• ISBN 9787121241536
• 定价 69.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 404页
• 字数 587千字
• 正文语种 简体中文
• 丛书 “十二五”国家重点图书出版规划项目

【内容简介】

　　大数据是当前流行的热点概念之一，其已由技术名词衍生到对很多行业产生颠覆性影响的社会现象，作为明确的技术发展趋势之一，基于大数据的各种新型产品必将会对每个人的日常生活产生日益重要的影响。
　　张俊林著的这本《大数据日知录：架构与算法》从架构与算法的角度全面梳理了大数据存储与处理的相关技术。大数据技术具有涉及的知识点异常众多且正处于快速演进发展过程中等特点，其技术点包括底层的硬件体系结构、相关的基础理论、大规模数据存储系统、分布式架构设计、各种不同应用场景下的差异化系统设计思路、机器学习与数据挖掘并行算法以及层出不穷的新架构、新系统等。本书对众多纷繁芜杂的相关技术文献和系统进行了择优汰劣并系统性地对相关知识分门别类地进行整理和介绍，将大数据相关技术分为大数据基础理论、大数据系统体系结构、大数据存储，以及包含批处理、流式计算、交互式数据分析、图数据库、并行机器学习的架构与算法以及增量计算等技术分支在内的大数据处理等几个大的方向。通过这种体系化的知识梳理与讲解，相信对于读者整体和系统地了解、吸收和掌握相关的技术有很大的帮助与促进作用。

【作者简介】

　　张俊林，是技术书籍《这就是搜索引擎:核心技术详解》的作者，目前担任畅捷通智能平台总监。在此之前，张俊林曾经在阿里巴巴搜索技术中心、百度商务搜索部凤巢广告平台以及新浪微博搜索部及数据系统部担任资深技术专家，新浪微博技术委员会成员，负责算法策略方向。张俊林还曾是智能信息聚合网站“玩聚网”的联合创始人之一。他的研发兴趣集中在：搜索技术、推荐系统、社交挖掘、自然语言处理与大数据算法架构等方面，并在以上领域有多年工业界实践经验。张俊林本科毕业于天津大学管理学院，1999年至2004年在中科院软件所直接攻读博士学位，研究方向是信息检索理论与自然语言处理，就学期间曾在ACL/COLING/IJCNLP等国际会议发表多篇学术论文，另外，他在此期间领导设计的搜索系统曾在美国国防部DARPA主持的TREC第二届高精度检索系统评测中在17只国际高水平研究团队激烈竞争中胜出并取得综合排名前列的优异成绩。

【目录】

第0 章 当谈论大数据时我们在谈什么 1
0.1 大数据是什么2
0.2 大数据之翼：技术范型转换.4
0.3 大数据商业炼金术6
0.4 “大数据”在路上.7
第1 章 数据分片与路由 9
1.1 抽象模型.10
1.2 哈希分片（HashPartition） 11
1.2.1 RoundRobin11
1.2.2 虚拟桶（VirtualBuckets） 12
1.2.3 一致性哈希（ConsistentHashing） .13
1.3 范围分片（RangePartition） 18
参考文献19
第2 章 数据复制与一致性20
2.1 基本原则与设计理念21
2.1.1 原教旨CAP 主义21
2.1.2 CAP 重装上阵（CAPReloaded）.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-PhraseCommit，2PC）33
2.4.2 向量时钟（VectorClock） 38
2.4.3 RWN 协议.40
2.4.4 Paxos 协议.42
2.4.5 Raft 协议.45
参考文献49
第3 章 大数据常用的算法与数据结构51
3.1 布隆过滤器（BloomFilter） 51
3.1.1 基本原理.52
3.1.2 误判率及相关计算52
3.1.3 改进：计数BloomFilter53
3.1.4 应用54
3.2SkipList55
3.3 LSM 树58
3.4 Merkle 哈希树（MerkleHash 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.2Snappy67
3.6 Cuckoo 哈希（CuckooHashing） 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 数据局部性（DataLocality） 75
4.2.3 抢占式调度与非抢占式调度.75
4.2.4 资源分配粒度（AllocationGranularity） .76
4.2.5 饿死（Starvation）与死锁（Dead Lock）问题.76
4.2.6 资源隔离方法77
4.3 资源管理与调度系统范型.77
4.3.1 集中式调度器（MonolithicScheduler）.78
4.3.2 两级调度器（Two-LevelScheduler） .79
4.3.3 状态共享调度器（Shared-StateScheduler） 79
4.4 资源调度策略.81
4.4.1 FIFO 调度策略81
4.4.2 公平调度器（FairScheduler）81
4.4.3 能力调度器（CapacityScheduler） 82
4.4.4 延迟调度策略（DelayScheduling）82
4.4.5 主资源公平调度策略（DominantResource Fair Scheduling）.82
4.5 Mesos.84
4.6YARN87
参考文献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 ZooKeeper96
5.2.1 体系结构.96
5.2.2 数据模型（DataModel） .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 ProtocolBuffer 与Thrift .108
6.1.2Avro.109
6.2 消息队列.110
6.2.1 常见的消息队列系统110
6.2.2 Kafka.111
6.3 应用层多播通信（Application-LevelMulti-Broadcast）114
6.3.1 概述.114
6.3.2 Gossip 协议.115
参考文献118
第7 章 数据通道.120
7.1 Log 数据收集.120
7.1.1Chukwa121
7.1.2Scribe122
7.2 数据总线123
7.2.1Databus125
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 Colossus137
8.2 HDFS138
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 纠删码（ErasureCode）.158
8.5.1 Reed-Solomon 编码.159
8.5.2 LRC 编码.164
8.5.3 HDFS-RAID 架构.166
参考文献.166
第9 章 内存KV 数据库.168
9.1 RAMCloud169
9.1.1 RAMCloud 整体架构169
9.1.2 数据副本管理与数据恢复170
9.2Redis172
9.3 MemBase.173
参考文献175