大数据日知录
出版日期:2014-9
ISBN:9787121241536
作者:张俊林
页数:404页
内容概要
张俊林是技术书籍《这就是搜索引擎：核心技术详解》（该书荣获全国第十二届输出版优秀图书奖）的作者，目前担任畅捷通智能平台总监。在此之前，张俊林曾经在阿里巴巴搜索技术中心、百度商务搜索部凤巢广告平台以及新浪微博搜索部及数据系统部担任资深技术专家，新浪微博技术委员会成员，负责算法策略方向。他还曾是智能信息聚合网站“玩聚网”的联合创始人之一。他的研发兴趣集中在：搜索技术、推荐系统、社交挖掘、自然语言处理与大数据算法架构等方面，并在以上领域有多年工业界实践经验。
张俊林本科毕业于天津大学管理学院，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 哈希分片（Hash Partition） ..............................11
1.2.1 Round Robin....................................11
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 Filter....................................53
3.1.4 应用............................................54
3.2 SkipList............................................55
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 Snappy..........................................67
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 YARN......................................87
参考文献..............................................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 Avro...............................109
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 Chukwa........................121
7.1.2 Scribe......................122
7.2 数据总线......................................123
7.2.1 Databus............................125
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
9.1 RAMCloud ..............................169
9.1.1 RAMCloud 整体架构................................169
9.1.2 数据副本管理与数据恢复................................170
9.2 Redis....................................172
9.3 MemBase ...............................173
参考文献................................................175
第10 章 列式数据库...........................................176
10.1 BigTable....................................177
10.1.1 BigTable 的数据模型..........................177
10.1.2 BigTable 的整体结构................................178
10.1.3 BigTable 的管理数据.............................179
10.1.4 主控服务器（Master Server）......................181
10.1.5 子表服务器（Tablet Server） ....................182
10.2 PNUTS 存储系统........................................186
10.2.1 PNUTS 的整体架构..............................186
10.2.2 存储单元...............................187
10.2.3 子表控制器与数据路由器..................................187
10.2.4 雅虎消息代理.............................188
10.2.5 数据一致性.........................................189
10.3 MegaStore..................................................190
10.3.1 实体群组切分......................191
10.3.2 数据模型........................................192
10.3.3 数据读/写与备份.................................193
10.4 Spanner .........................................194
10.4.1 SpanServer 软件栈.........................................195
10.4.2 数据模型.........................................196
10.4.3 TrueTime ...........................................196
参考文献..............................................197
第11 章 大规模批处理系统...................................199
11.1 MapReduce 计算模型与架构................................200
11.1.1 计算模型.......................................201
11.1.2 系统架构......................................203
11.1.3 MapReduce 计算的特点及不足......................................206
11.2 MapReduce 计算模式...........................206
11.2.1 求和模式（Summarization Pattern）................207
11.2.2 过滤模式（Filtering Pattern） ................208
11.2.3 组织数据模式（Data Organization Pattern） .....................210
11.2.4 Join 模式（Join Pattern）......................212
11.3 DAG 计算模型..........................................214
11.3.1 DAG 计算系统的三层结构............................214
11.3.2 Dryad .......................................215
11.3.3 FlumeJava 和Tez ........................................217
参考文献...........................................218
第12 章 流式计算........................................219
12.1 流式计算系统架构....................................222
12.1.1 主从架构............................................222
12.1.2 P2P 架构.....................................................223
12.1.3 Samza 架构..........................................224
12.2 DAG 拓扑结构..........................................224
12.2.1 计算节点.....................................................225
12.2.2 数据流..............................................226
12.2.3 拓扑结构..................................226
12.3 送达保证（Delivery Guarantees）..............................229
12.3.1 Storm 的送达保证机制.................................230
12.3.2 MillWheel 的“恰好送达一次”机制...........................233
12.4 状态持久化...........................................234
12.4.1 容错的三种模式....................................234
12.4.2 Storm 的状态持久化.......................................236
12.4.3 MillWheel 和Samza 的状态持久化......................237
参考文献............................................238
第13 章 交互式数据分析...................................240
13.1 Hive 系数据仓库.................................242
13.1.1 Hive .....................................242
13.1.2 StingerInitiative ................................250
13.2 Shark 系数据仓库..................................251
13.2.1 Shark 架构.........................................252
13.2.2 部分DAG 执行引擎（PDE） ........................253
13.2.3 数据共同分片.........................................254
13.3 Dremel 系数据仓库...................................254
13.3.1 Dremel...........................255
13.3.2 PowerDrill ..........................258
13.3.3 Impala.................................261
13.3.4 Presto...............................264
13.4 混合系数据仓库......................................265
参考文献.................................269
第14 章 图数据库：架构与算法................................271
14.1 在线查询类图数据库...........................272
14.1.1 三层结构.........................272
14.1.2 TAO 图数据库.................................273
14.2 常见图挖掘问题..........................................277
14.2.1 PageRank 计算.......................................278
14.2.2 单源最短路径（Single Source Shortest Path） ..................278
14.2.3 二部图最大匹配.............................279
14.3 离线挖掘数据分片..............................................279
14.3.1 切边法（Edge-Cut）......................................280
14.3.2 切点法（Vertex-Cut）...............................282
14.4 离线挖掘计算模型...................................284
14.4.1 以节点为中心的编程模型..........................284
14.4.2 GAS 编程模型...........................................285
14.4.3 同步执行模型.....................................286
14.4.4 异步执行模型...................................290
14.5 离线挖掘图数据库.................................292
14.5.1 Pregel..........................292
14.5.2 Giraph...............................299
14.5.3 GraphChi ............................301
14.5.4 PowerGraph.......................307
参考文献.......................................311
第15 章 机器学习：范型与架构.........................................313
15.1 分布式机器学习...........................................314
15.1.1 机器学习简介.............................................314
15.1.2 数据并行VS.模型并行.....................................316
15.2 分布式机器学习范型.....................317
15.2.1 三种范型...................................318
15.2.2 MapReduce 迭代计算模型........................319
15.2.3 BSP 计算模型...................................321
15.2.4 SSP 模型............................323
15.3 分布式机器学习架构...................................324
15.3.1 MapReduce 系列..................................325
15.3.2 Spark 及MLBase ..........................................327
15.3.3 参数服务器（Parameter Server）.............332
参考文献................................................335
第16 章 机器学习：分布式算法...............................337
16.1 计算广告：逻辑回归.......................................338
16.1.1 逻辑回归（Logistic Regression，LR）.............................338
16.1.2 并行随机梯度下降（Parallel Stochastic Gradient Descent）............341
16.1.3 批学习并行逻辑回归..................................341
16.2 推荐系统：矩阵分解................................................344
16.2.1 矩阵分解方法.......................................344
16.2.2 ALS-WR 算法............................................346
16.2.3 并行版ALS-WR 算法..............................347
16.3 搜索引擎：机器学习排序................................347
16.3.1 机器学习排序简介.................................348
16.3.2 LambdaMART.................................349
16.3.3 分布式LambdaMART........................................351
16.4 自然语言处理：文档相似性计算.......................................352
16.5 社交挖掘：谱聚类.................................355
16.5.1 社交挖掘实例...............................355
16.5.2 谱聚类....................................356
16.5.3 并行版谱聚类..........................................358
16.6 深度学习：DistBelief .............................................358
16.6.1 深度学习简介........................................359
16.6.2 DistBelief.....................360
参考文献.........................................364
第17 章 增量计算..........................................366
17.1 增量计算模式...........................367
17.1.1 两种计算模式...............................367
17.1.2 Hadoop 平台下增量计算的一般模式.............................368
17.2 Percolator................................370
17.2.1 事务支持..........................................371
17.2.2 “观察/通知”体系结构...........................373
17.3 Kineograph ............................374
17.3.1 整体架构.........................................375
17.3.2 增量计算机制....................................375
17.4 DryadInc ....................................376
参考文献..............................................................377
附录A 硬件体系结构及常用性能指标......................................378
附录B 大数据必读文献....................................380
作者简介
大数据是当前最为流行的热点概念之一，其已由技术名词衍生到对很多行业产生颠覆性影响的社会现象，作为最明确的技术发展趋势之一，基于大数据的各种新型产品必将会对每个人的日常生活产生日益重要的影响。
《大数据日知录：架构与算法》从架构与算法角度全面梳理了大数据存储与处理的相关技术。大数据技术具有涉及的知识点异常众多且正处于快速演进发展过程中等特点，其技术点包括底层的硬件体系结构、相关的基础理论、大规模数据存储系统、分布式架构设计、各种不同应用场景下的差异化系统设计思路、机器学习与数据挖掘并行算法以及层出不穷的新架构、新系统等。《大数据日知录：架构与算法》对众多纷繁芜杂的相关技术文献和系统进行了择优汰劣并系统性地对相关知识分门别类地进行整理和介绍，将大数据相关技术分为大数据基础理论、大数据系统体系结构、大数据存储，以及包含批处理、流式计算、交互式数据分析、图数据库、并行机器学习的架构与算法以及增量计算等技术分支在内的大数据处理等几个大的方向。通过这种体系化的知识梳理与讲解，相信对于读者整体和系统地了解、吸收和掌握相关的优秀技术有极大的帮助与促进作用。
《大数据日知录：架构与算法》的读者对象包括对NoSQL 系统及大数据处理感兴趣的所有技术人员，以及有志于投身到大数据处理方向从事架构师、算法工程师、数据科学家等相关职业的在校本科生及研究生。
发布书评
精彩书评 (总计4条)
-
对大数据的初步感官是使用hive(hadoop SQL接口)查询，等结果等的很焦急 ,然后陆续接触到了NoSQL存储（mongodb http://danqingdani.blog.163.com/blog/static/1860941952014110756412/ http://danqingdani.blog.163.com/blog/static/1860941952014214112153146/ ，redis http://danqingdani.blog.163.com/blog/static/18609419520142196591588/），但基本都只使用了查询功能，再就是与数据团队的合作知道了Spagobi,Pentaho等报表工具，周会上知道了日志传输平台容易出数据丢失不同步机器down掉的Bug——kafka消息系统与flume日志收集系统，然后在察看日志分析相关工具（我总是从工具入手来学习某一领域的知识），知道了elasticsearch 与 sphinx搜索引擎，漂亮的kibana前端web UI，在动手进行日志分析的时候，知道了hadoop取数据，序列化数据的解析（protocolBuffer， PB格式的听说却是三年前来自网游通信协议设计，还愚蠢地抱怨为啥不是标准的json格式，不好进行下一步处理）MapReduce批处理方式与Storm流式处理方式。而这本书正好将我陆续知道的一些零星概念串起来了，并确认了自己在大数据处理中的定位是数据分析（计算），不是数据存储，不是数据通信。如果你仅仅是想在大数据中书皮学一下，看本书第0章的两幅图就OK了。最后，作者估计是王菲的粉丝，开章语中有5首王菲的歌，我也很喜欢。 -
作为大数据学习的搜索引擎不错。毕竟初学者还是不知道都包含那些的，虽说互联网上类似的内容很多，但一般都不知道怎么整理，有了这些初步的，看起来也比较理论化的入门内容，有助于初学者找到入门的大致需要所学的内容。作者看的出经验丰富，所看过的只是也挺广泛的，存储，架构，平台，工具，算法，无一不涉及。看的出是行业里设计比较广泛的专家。 -
做数据库相关开发已经有将近4年时间了，做过nosql、mysql，分析过hadoop、spark，终于看到一本可以总领提纲的bigdata方向的书，本书涉及到bigdata相关的方方面面，看完之后，不得不感慨作者在该行业深厚的积累。之前也看到一些介绍bigdata相关的书籍，但大多是很high level的介绍，很难引起技术人员的共鸣，但是这本书，真的是和我自己平时做的东西非常相关，帮助我把平时零零散散的知识点汇集整理在一本书里，感觉非常亲切。本书确实是一本bigdata方向的经典书籍。
精彩短评 (总计50条)
-
科普 -
基本涉及当前大数据的方方面面，对拓展知识面，建立大数据的知识体系帮助很大。但正因为涉及面太广，细节多数是一带而过，在读完本书后，可以有针对性的通过其它途径对感兴趣的领域再深入研究 -
讲得很浅，各种罗列！有骨架，却没长肉 -
花了个几月的时间看，应该说内容非常全面，作者一定是有大量实际经验，对于想致力于搜索领域发展的朋友应该很有帮助，不管是架构，算法都可以看到很多新东西，初学者要有相当好的基础需要下很多功夫才能领悟，要有很强的全局观，知识面要求也很广。 -
分布式讲了很多。一本很好的工具书。 -
不错，介绍了各种大数据的架构和算法 -
花了整个周末的时间把书全部过了一遍，算是不错的导引类书籍了，尤其前面写的非常好（尤其是数据结构那章）。缺点在于深度不够... -
内容还行。但是作者太能装逼，每章前面放首歌词到底是为那般。差评。 -
大数据涉及的各种技术及相关理论，很好 -
很多经典论文翻译，作为泛读还行，要学东西就是想太多了。 -
作为科普还行，基本都只是提了个概念。 -
概念介绍类书籍，写得不错 -
对流行的大数据技术分门别类的都介绍了下。不错的入门书籍。 -
罗列了一堆框架和论文，但基本上都是点到为止，入门级的扫盲吧，翻翻还凑和。。。 -
挺喜欢这种地图类的书的，摸清脉络，形成体系。不过去到实际的目的地，这本根本不够啊，很多问题点都太粗率了。 -
航海图 -
前半部分介绍分布式系统的常见算法、结构等，全面了解不错；后半部分是大数据分析、机器学习等，没有看。 -
非常全面的一本书，读完感觉把脑海里的知识和架构体系重新梳理了一下。之所以四星是因为：虽然全面但是深浅不一，不适合作为工具书，且篇幅长，需要较多时间进行阅读。 -
应该是目前在大数据领域广度最大的一本书，追求了广度，自然就要放弃深度，适合有一定基础的人阅读，进一步拓展自己的视野。 -
概念居多，各种产品介绍居多，但是还是值得一看。 -
勉强读完，很多概念暂时理解不了，但是还是一本了解大数据知识的好书，以后还需要多次阅读。但是现在很多概念应该都更新了，需要作者来与时俱进了 -
梳理目录分类很管用 -
看不懂 -
不算很烂的书，但是此书仅仅是各种review, readme和paper的集合。很可惜大部分readme我已经看过了。于是减一星。ju360是个跟好的网站，很遗憾和谐了。
-
大杂烩，入个门。 -
不要买任何中国人写的技术书，纯粹浪费时间 -
看不太懂，呃呃～ -
还行，有的讲的泛，有的讲的细。完整版联系374741295@qq.com。支付宝支付5元到374741295@qq.com这个账号即可。 -
大数据技术索引类图书 -
很全面，脉络清晰 -
宏观了解 -
不错阿，百科全书式的技术笔记，讲解也很清楚。 -
在知识广度方面无出其右了。这么多概念自己整理要费极大功夫。有人帮你系统梳理如此庞大的知识体系是件很爽的事情，堪比大保健。 -
内容多，用来按图索骥不错 -
类似一个目录的存在，介绍了大数据的方方面面，更多的知识需要自己去扩展 -
可以算是作者关于大数据的笔记，比较粗糙，对很多重要的算法比较初略的写出，要了解详细一点的都要自己再找网上的文章看看。胜在这本书比较全面，对大数据入门，或者想了解大数据还是一个不错的选择。 -
大数据方面的百科全书，清晰的梳理了大数据相关的知识点，虽然深度没潜下去，但足以对各方面有更全面的认识，符合日知录的名字。14年的书在16年仍然有很好的参考价值。值得想了解或学习大数据方面的童鞋去读。稍后会把读书笔记和脑图上传。 -
这种级别的技术书籍还真不是随便可以驾驭的 从工程上出发还是多介绍一些trick比较实用 大而全的体系hold不住 -
内容很丰富，不过最后几章的算法还是看不懂 -
这本书适合大数据研究人员，入门级书，涉及的技术都还挺新，省去了很多读论文的时间，是一个很好的汇总。总之这个不是技术应用型的书。 -
挑着看的 -
和上一本搜索的书质量差不多，很多概念讲的很透 -
有广度有深度
注：这里的架构不是系统架构 -
需要重读 -
index -
除了zk mr storm ，好多都不懂 -
尚可 -
内容太多，最近不喜欢这个风格 -
2015.9.10读完
好书, 类似于地图的作用, 整个过一遍后知道整个系统是怎么组成的, 在哪个地方该用哪个组件, 有哪些组件可供选择. 看完后感觉对系统整体性的理解更有把握了, 消除了之前那种做东西的割裂感. 如果需要深入某一部分, 也知道这一部分属于系统的哪个位置. 以后该书可以拿来当参考手册 -
不光生态系统讲的好，关键是有作者自己的思考以及对读者的指引，每章后面对的参考文献都是经典，尤其全书最后附录2的文献更是必读