 |
-- 會員 / 註冊 --
|
 |
|
|
|
大數據日知錄：架構與算法 ( 簡體 字) |
| 作者：張俊林 | 類別：1. -> 程式設計 -> 大數據 |
| 譯者： |
| 出版社：電子工業出版社 |  3dWoo書號： 39491
詢問書籍請說出此書號！【缺書】
NT售價： 345 元 |
| 出版日：9/1/2014 |
| 頁數：404 |
| 光碟數：0 |
|
站長推薦：   |
| 印刷： | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787121241536 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言：像移動互聯網、O2O、可穿戴設備等概念一樣，“大數據”從甫一提出到颶風般席卷并風靡全球，從最初的技術名詞到形成滲透到各行各業的社會現象，所耗時間僅幾年而已，其興也勃焉。
那么，大數據是否會像很多曾經火熱現在已難覓蹤跡的流行概念一樣，將來某日，人們靜心抬眼，發現風已去而水波不興，徒留夕陽下波光粼粼的漣漪，讓人不禁哀嘆其亡也忽焉？
本書的背景
目前看仿佛有此跡象，當一個概念火爆到從街頭隨便抓一個路人，他都能跟你滔滔不絕地侃侃而談；當一個新名詞鋪天蓋地而來，讓你熟悉到再見一次就要吐的程度，這些確實是典型的泡沫將破的征兆。目前業已出現越來越多的質疑聲音，在這種狂熱的氛圍下，理性的質疑是最難能可貴的，畢竟大數據歸根結底是少數派的游戲，而現狀好像是人人都處于大數據進行時的狀態，這讓其看上去顯得不甚理性。
但是，從社會發展趨勢的角度，很明顯大數據會是目前肉眼可及的視野范圍里能看到的最大趨勢之一。從傳統IT業到互聯網、互聯網到移動互聯網，從以智能手機和Pad為主要終端載體的移動互聯網到可穿戴設備的移動互聯網，然后再到萬物互聯的物聯網，這一定是不可違抗的發展規律和前進方向。伴隨著這個趨勢必然有越來越多、形態越來越豐富的超量數據不斷產生，而大數據明顯是由此衍生出來的明確且必然的發展趨勢。
所以，歸根結底，大數據概念是個短期內炒得過熱，但是從長期來看炒得不足的領域。再過十年如果回望現在，也許會發現：我們今天正在巍峨群山的山腳徘徊，試圖找出一條通往山頂的羊腸小道，如此而已。我們當然不能盲目跟風不斷追逐切換熱點，但是忽視趨勢的力量同樣也不是一個理性的選擇。
本書的內容
以上所述是本書誕生的大背景，目前市面上陸陸續續已經有不少講大數據的書，有面向大眾的概念普及類圖書，也有講解大數據技術的書，本書屬于第二類，專注于大數據處理有關的架構與算法，我相信這是一本比較全面地分門別類梳理大數據技術的書籍。從大約2010年年底起我開始關注并收集整理這方面的技術資料，當然那時還沒有聽說過大數據的概念，現在的所謂大數據已經是后來的事情了，最初引起我關注的是NoSQL相關的技術，尤其是Google和亞馬遜的一系列相關工作，當時隱約地覺得這是一種新的技術發展趨勢，甚至是一次技術范型的大轉換，所以逐步開始投入越來越多的精力到其中，這包括將相關技術資料分門別類地進行收集、閱讀和整理，利用業余時間開始一章一節地慢慢寫本書，以及在實際工作中盡可能地應用這些技術和系統等若干方面。
本書的寫作
斷斷續續完成本書花了大約3年左右的時間，和最初預估的時間還是比較吻合的，這一方面是由于我可投入的時間本身就不多，但是還是希望能夠寫出一本高質量的技術書籍，所以不得不慢工出細活；另外一方面是由于大數據處理作為一個新領域，其涉及的方方面面的技術點實在太多，而且正處于快速的發展過程中。這個領域是我接觸過的領域中知識涵蓋面最廣的，從底層的硬件開始，到涉及基礎理論、大規模數據存儲系統、分布式架構設計、各種不同適用場景下的差異化系統設計思路、機器學習與數據挖掘并行算法、層出不窮的新架構和新系統等，說無所不包有些夸張但是所需掌握知識點之多確實是很少見的。而且因為其處于快速發展的過程當中，所以各種技術紛繁蕪雜，并無一個成熟的知識分類體系可供參考，需要不斷梳理相關知識點之間的相互區別和聯系并進行分門別類，如何將紛雜多樣的技術梳理成清晰合理的章節內容曾讓我頭疼不已，當然發展到目前，整個大數據技術體系脈絡已經日漸明晰，我相信參考本書目錄可以清晰地發現這一點。另外一個阻礙是可參考的資料和系統多而雜，且質量良莠不齊，需要從中汰劣余優，盡可能選出有代表性及有發展潛力的理論、方案和系統，這也是很耗費精力的過程，盡管本書每章后只列出了很少一部分參考資料，但是實際參考的文獻與系統要數倍于此，只列出精華部分是為了節省讀者選擇高質量文獻的過程。
十幾年前當我還在中國科學院讀書的時候，就對互聯網的蓬勃發展及其對生活和工作各方面的影響感慨不已，當時最直觀的感受是最新的國際會議論文很容易獲得，往往是會議一開完就能從網上下載到感興趣的文獻，有時候會議沒開有些作者就把論文先放在網上供人參考。覺得有了互聯網這么強大的全球范圍信息便捷分享工具，盡管當時國內科研水平不算高，在最好的國際頂級會議發表論文還是較難的事情，但是隨著互聯網的普及，科研水準應該能夠獲得極為快速長足的發展，因為從追蹤最新技術進展的角度看大家的起跑線是一樣的，而中國人多的優勢慢慢應該能夠發揮出來，事實上也是如此，最近幾年各種國際頂級會議中，國人發表的論文比例越來越高可以證明這一點，而很明顯這個趨勢還會進一步加快。之所以提這個，是因為大數據相關技術研發道理其實也是一樣的，盡管目前國內在這方面的實力和國外相比還有很大的差距，優秀的系統和技術方案往往都是Google、亞馬遜、Facebook、Linkedin等這些國際知名互聯網公司提出的，國內工業界的技術水準大部分還僅僅停留在能把開源的大數據系統應用起來解決手頭碰到的問題這個階段，但是我相信在不遠的將來，國內會逐步涌現出具有國際水準的大數據系統與解決方案，其中的道理與上面所舉的學術進步的例子是一樣的。目前大部分優秀系統是開源的，相關技術文獻也很容易找到，作為有進取心的技術人員，現在所缺乏的不是沒有可參考的學習資料，相反是資料太多良莠不齊反而讓很多人無所適從，不知該如何下手。國內的技術人員只要肯下功夫、會下功夫，有好的職業發展環境和高的自我期許及技術理想，假以時日，越來越多的世界級水準的大數據處理系統出自國人之手是完全可以預料的，我期望本書對于這些技術人員在全面了解吸收并掌握大數據處理的優秀技術過程中，能貢獻綿薄之力。沈利也參與了本書的部分編寫工作。
致謝
感謝我的妻子、岳父、岳母，以及爸爸、媽媽，盡管歷時3年才得以完成本書，但是若是沒有你們的全身心支持，這本書2020年也無法面世。
對了，還有我的女兒，親愛的雪晴，從蹣跚邁出人生第一步，到咿咿呀呀說出第一句話，我總是想起，小小的你，迷茫地站在這遍布新奇的世界里，東張西望時無助的樣子，這總是令人心疼。你無數人生的第一次帶給我太多歡樂，而我陪你的時間又太少太少，每次聽到你用小手咚咚敲著書房緊閉的門，這經常讓我感到惶惑，不知道這么狠心對你是對還是錯，但是又不得不狠下心來。我相信將來一定會后悔沒有給你更多的時間，把你介紹給這斑斕而殘酷的世界，囑咐它在今后的日子里能善待你一些。我多想陪你甚至到你白發蒼蒼的歲月：在初秋的午后陽光下，看到你坐在院中的婆娑樹影里，給你的兒孫講故事，淺笑依然，仿似今天。我可以清楚地想象那時的場景，清晰得就像一切就發生在眼前。雖然我深切地知道這是永不可實現的奢望，但這個夢想會永遠放在我心里，就像你清澈的目光和純真的笑容一樣。
時間是我們的朋友，也是我們的敵人，希望你們能夠原諒我。
張俊林
2014年3月 |
內容簡介：大數據是當前最為流行的熱點概念之一，其已由技術名詞衍生到對很多行業產生顛覆性影響的社會現象，作為最明確的技術發展趨勢之一，基于大數據的各種新型產品必將會對每個人的日常生活產生日益重要的影響。
本書從架構與算法角度全面梳理了大數據存儲與處理的相關技術。大數據技術具有涉及的知識點異常眾多且正處于快速演進發展過程中等特點，其技術點包括底層的硬件體系結構、相關的基礎理論、大規模數據存儲系統、分布式架構設計、各種不同應用場景下的差異化系統設計思路、機器學習與數據挖掘并行算法以及層出不窮的新架構、新系統等。本書對眾多紛繁蕪雜的相關技術文獻和系統進行了擇優汰劣并系統性地對相關知識分門別類地進行整理和介紹，將大數據相關技術分為大數據基礎理論、大數據系統體系結構、大數據存儲，以及包含批處理、流式計算、交互式數據分析、圖數據庫、并行機器學習的架構與算法以及增量計算等技術分支在內的大數據處理等幾個大的方向。通過這種體系化的知識梳理與講解，相信對于讀者整體系統地了解、吸收和掌握相關的優秀技術有極大的幫助與促進作用。 |
目錄：第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 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 |
| 序： |
|
