大数据日知录：架构与算法 大数据领域专家力作，专注大数据架构和算法，全面梳理大数据相关技术

内容简介

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

目录

第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 抢占式VS.非抢占式调度 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 Proto

摘要与插图

前 言
像移动互联网、O2O、可穿戴设备等概念一样，“大数据”从甫一提出到飓风般席卷并风靡，从的技术名词到形成渗透到各行各业的社会现象，所耗时间仅几年而已，其兴也勃焉。
那么，大数据是否会像很多曾经火热现在已难觅踪迹的流行概念一样，将来某日，人们静心抬眼，发现风已去而水波不兴，徒留夕阳下波光粼粼的涟漪，让人不禁哀叹其亡也忽焉？
本书的背景
目前看仿佛有此迹象，当一个概念火爆到从街头随便抓一个路人，他都能跟你滔滔不绝地侃侃而谈；当一个新名词铺天盖地而来，让你熟悉到再见一次就要吐的程度，这些确实是典型的泡沫将破的征兆。目前业已出现越来越多的质疑声音，在这种狂热的氛围下，理性的质疑是能可贵的，毕竟大数据归根结底是少数派的游戏，而现状好像是人人都处于大数据进行时的状态，这让其看上去显得不甚理性。
但是，从社会发展趋势的角度，很明显大数据会是目前肉眼可及的视野范围里能看到的趋势之一。从传统IT业到互联网、互联网到移动互联网，从以智能手机和Pad为主要终端载体的移动互联网到可穿戴设备的移动互联网，然后再到万物互联的物联网，这一定是不可违抗的发展规律和前进方向。伴随着这个趋势必然有越来越多、形态越来越丰富的超量数据不断产生，而大数据明显是由此衍生出来的明确且必然的发展趋势。
所以，归根结底，大数据概念是个短期内炒得过热，但是从长期来看炒得不足的领域。再过十年如果回望现在，也许会发现：我们今天正在巍峨群山的山脚徘徊，试图找出一条通往山顶的羊肠小道，如此而已。我们当然不能盲目跟风不断追逐切换热点，但是忽视趋势的力量同样也不是一个理性的选择。
本书的内容
以上所述是本书诞生的大背景，目前市面上陆陆续续已经有不少讲大数据的书，有面向大众的概念普及类图书，也有讲解大数据技术的书，本书属于第二类，专注于大数据处理有关的架构与算法，我相信这是一本比较全面地分门别类梳理大数据技术的书籍。从大约2010年年底起我开始关注并收集整理这方面的技术资料，当然那时还没有听说过大数据的概念，现在的所谓大数据已经是后来的事情了，引起我关注的是NoSQL相关的技术，尤其是Google和亚马逊的一系列相关工作，当时隐约地觉得这是一种新的技术发展趋势，甚至是一次技术范型的大转换，所以逐步开始投入越来越多的精力到其中，这包括将相关技术资料分门别类地进行收集、阅读和整理，利用业余时间开始一章一节地慢慢写本书，以及在实际工作中尽可能地应用这些技术和系统等若干方面。
本书的写作
断断续续完成本书花了大约3年左右的时间，和预估的时间还是比较吻合的，这一方面是由于我可投入的时间本身就不多，但是还是希望能够写出一本高质量的技术书籍，所以不得不慢工出细活；另外一方面是由于大数据处理作为一个新领域，其涉及的方方面面的技术点实在太多，而且正处于快速的发展过程中。这个领域是我接触过的领域中知识涵盖面的，从底层的硬件开始，到涉及基础理论、大规模数据存储系统、分布式架构设计、各种不同适用场景下的差异化系统设计思路、机器学习与数据挖掘并行算法、层出不穷的新架构和新系统等，说无所不包有些夸张但是所需掌握知识点之多确实是很少见的。而且因为其处于快速发展的过程当中，所以各种技术纷繁芜杂，并无一个成熟的知识分类体系可供参考，需要不断梳理相关知识点之间的相互区别和联系并进行分门别类，如何将纷杂多样的技术梳理成清晰合理的章节内容曾让我头疼不已，当然发展到目前，整个大数据技术体系脉络已经日渐明晰，我相信参考本书目录可以清晰地发现这一点。另外一个阻碍是可参考的资料