大規(guī)模分布式存儲(chǔ)系統(tǒng)（原理解析與架構(gòu)實(shí)戰(zhàn)）完整版

大規(guī)模分布式存儲(chǔ)系統(tǒng)原理解析與架構(gòu)實(shí)戰(zhàn)目錄\h第一篇基礎(chǔ)篇\h第1章概述\h1.1分布式存儲(chǔ)概念\h1.2分布式存儲(chǔ)分類\h第2章單機(jī)存儲(chǔ)系統(tǒng)\h2.1硬件基礎(chǔ)\h2.2單機(jī)存儲(chǔ)引擎\h2.3數(shù)據(jù)模型\h2.4事務(wù)與并發(fā)控制\h2.5故障恢復(fù)\h2.6數(shù)據(jù)壓縮\h第3章分布式系統(tǒng)\h3.1基本概念\h3.2性能分析\h3.3數(shù)據(jù)分布\h3.4復(fù)制\h3.5容錯(cuò)\h3.6可擴(kuò)展性\h3.7分布式協(xié)議\h3.8跨機(jī)房部署\h第二篇范型篇\h第4章分布式文件系統(tǒng)\h4.1Google文件系統(tǒng)\h4.2TaobaoFileSystem\h4.3FacebookHaystack\h4.4內(nèi)容分發(fā)網(wǎng)絡(luò)\h第5章分布式鍵值系統(tǒng)\h5.1AmazonDynamo\h5.2淘寶Tair\h第6章分布式表格系統(tǒng)\h6.1GoogleBigtable\h6.2GoogleMegastore\h6.3WindowsAzureStorage\h第7章分布式數(shù)據(jù)庫(kù)\h7.1數(shù)據(jù)庫(kù)中間層\h7.2MicrosoftSQLAzure\h7.3GoogleSpanner\h第三篇實(shí)踐篇\h第8章OceanBase架構(gòu)初探\h8.1背景簡(jiǎn)介\h8.2設(shè)計(jì)思路\h8.3系統(tǒng)架構(gòu)\h8.4架構(gòu)剖析\h第9章分布式存儲(chǔ)引擎\h9.1公共模塊\h9.2RootServer實(shí)現(xiàn)機(jī)制\h9.3UpdateServer實(shí)現(xiàn)機(jī)制\h9.4ChunkServer實(shí)現(xiàn)機(jī)制\h9.5消除更新瓶頸\h第10章數(shù)據(jù)庫(kù)功能\h10.1整體結(jié)構(gòu)\h10.2只讀事務(wù)\h10.3寫事務(wù)\h10.4OLAP業(yè)務(wù)支持\h10.5特色功能\h第11章質(zhì)量保證、運(yùn)維及實(shí)踐\h11.1質(zhì)量保證\h11.2使用與運(yùn)維\h11.3應(yīng)用\h11.4最佳實(shí)踐\h第四篇專題篇\h第12章云存儲(chǔ)\h12.1云存儲(chǔ)的概念\h12.2云存儲(chǔ)的產(chǎn)品形態(tài)\h12.3云存儲(chǔ)技術(shù)\h12.4云存儲(chǔ)的核心優(yōu)勢(shì)\h12.5云平臺(tái)整體架構(gòu)\h12.6云存儲(chǔ)技術(shù)體系\h12.7云存儲(chǔ)安全\h第13章大數(shù)據(jù)\h13.1大數(shù)據(jù)的概念\h13.2MapReduce\h13.3MapReduce擴(kuò)展\h13.4流式計(jì)算\h13.5實(shí)時(shí)分析\h參考資料\h硬件基礎(chǔ)\h存儲(chǔ)系統(tǒng)\h分布式系統(tǒng)\h分布式文件系統(tǒng)\h分布式鍵值系統(tǒng)\h分布式表格系統(tǒng)\h分布式數(shù)據(jù)庫(kù)\hOceanBase\h云存儲(chǔ)\h離線分析\hOLAP\h流式計(jì)算注：原文檔電子版，非掃描，需要的清下載本文檔后留言謝謝。第一篇基礎(chǔ)篇本篇內(nèi)容第2章單機(jī)存儲(chǔ)系統(tǒng)第3章分布式系統(tǒng)第1章概述Google、Amazon、Alibaba等互聯(lián)網(wǎng)公司的成功催生了云計(jì)算和大數(shù)據(jù)兩大熱門領(lǐng)域。無(wú)論是云計(jì)算、大數(shù)據(jù)還是互聯(lián)網(wǎng)公司的各種應(yīng)用，其后臺(tái)基礎(chǔ)設(shè)施的主要目標(biāo)都是構(gòu)建低成本、高性能、可擴(kuò)展、易用的分布式存儲(chǔ)系統(tǒng)。雖然分布式系統(tǒng)研究了很多年，但是，直到近年來(lái)，互聯(lián)網(wǎng)大數(shù)據(jù)應(yīng)用的興起才使得它大規(guī)模地應(yīng)用到工程實(shí)踐中。相比傳統(tǒng)的分布式系統(tǒng)，互聯(lián)網(wǎng)公司的分布式系統(tǒng)具有兩個(gè)特點(diǎn)：一個(gè)特點(diǎn)是規(guī)模大，另一個(gè)特點(diǎn)是成本低。不同的需求造就了不同的設(shè)計(jì)方案，可以這么說(shuō)，Google等互聯(lián)網(wǎng)公司重新定義了大規(guī)模分布式系統(tǒng)。本章介紹大規(guī)模分布式系統(tǒng)的定義與分類。1.1分布式存儲(chǔ)概念大規(guī)模分布式存儲(chǔ)系統(tǒng)的定義如下：“分布式存儲(chǔ)系統(tǒng)是大量普通PC服務(wù)器通過(guò)Internet互聯(lián)，對(duì)外作為一個(gè)整體提供存儲(chǔ)服務(wù)?！狈植际酱鎯?chǔ)系統(tǒng)具有如下幾個(gè)特性：●可擴(kuò)展。分布式存儲(chǔ)系統(tǒng)可以擴(kuò)展到幾百臺(tái)甚至幾千臺(tái)的集群規(guī)模，而且，隨著集群規(guī)模的增長(zhǎng)，系統(tǒng)整體性能表現(xiàn)為線性增長(zhǎng)。●低成本。分布式存儲(chǔ)系統(tǒng)的自動(dòng)容錯(cuò)、自動(dòng)負(fù)載均衡機(jī)制使其可以構(gòu)建在普通PC機(jī)之上。另外，線性擴(kuò)展能力也使得增加、減少機(jī)器非常方便，可以實(shí)現(xiàn)自動(dòng)運(yùn)維?！窀咝阅堋o(wú)論是針對(duì)整個(gè)集群還是單臺(tái)服務(wù)器，都要求分布式存儲(chǔ)系統(tǒng)具備高性能?！褚子?。分布式存儲(chǔ)系統(tǒng)需要能夠提供易用的對(duì)外接口，另外，也要求具備完善的監(jiān)控、運(yùn)維工具，并能夠方便地與其他系統(tǒng)集成，例如，從Hadoop云計(jì)算系統(tǒng)導(dǎo)入數(shù)據(jù)。分布式存儲(chǔ)系統(tǒng)的挑戰(zhàn)主要在于數(shù)據(jù)、狀態(tài)信息的持久化，要求在自動(dòng)遷移、自動(dòng)容錯(cuò)、并發(fā)讀寫的過(guò)程中保證數(shù)據(jù)的一致性。分布式存儲(chǔ)涉及的技術(shù)主要來(lái)自兩個(gè)領(lǐng)域：分布式系統(tǒng)以及數(shù)據(jù)庫(kù)，如下所示：●數(shù)據(jù)分布：如何將數(shù)據(jù)分布到多臺(tái)服務(wù)器才能夠保證數(shù)據(jù)分布均勻？數(shù)據(jù)分布到多臺(tái)服務(wù)器后如何實(shí)現(xiàn)跨服務(wù)器讀寫操作？●一致性：如何將數(shù)據(jù)的多個(gè)副本復(fù)制到多臺(tái)服務(wù)器，即使在異常情況下，也能夠保證不同副本之間的數(shù)據(jù)一致性？●容錯(cuò)：如何檢測(cè)到服務(wù)器故障？如何自動(dòng)將出現(xiàn)故障的服務(wù)器上的數(shù)據(jù)和服務(wù)遷移到集群中其他服務(wù)器？●負(fù)載均衡：新增服務(wù)器和集群正常運(yùn)行過(guò)程中如何實(shí)現(xiàn)自動(dòng)負(fù)載均衡？數(shù)據(jù)遷移的過(guò)程中如何保證不影響已有服務(wù)？●事務(wù)與并發(fā)控制：如何實(shí)現(xiàn)分布式事務(wù)？如何實(shí)現(xiàn)多版本并發(fā)控制？●易用性：如何設(shè)計(jì)對(duì)外接口使得系統(tǒng)容易使用？如何設(shè)計(jì)監(jiān)控系統(tǒng)并將系統(tǒng)的內(nèi)部狀態(tài)以方便的形式暴露給運(yùn)維人員？●壓縮/解壓縮：如何根據(jù)數(shù)據(jù)的特點(diǎn)設(shè)計(jì)合理的壓縮/解壓縮算法？如何平衡壓縮算法節(jié)省的存儲(chǔ)空間和消耗的CPU計(jì)算資源？分布式存儲(chǔ)系統(tǒng)挑戰(zhàn)大，研發(fā)周期長(zhǎng)，涉及的知識(shí)面廣。一般來(lái)講，工程師如果能夠深入理解分布式存儲(chǔ)系統(tǒng)，理解其他互聯(lián)網(wǎng)后臺(tái)架構(gòu)不會(huì)再有任何困難。1.2分布式存儲(chǔ)分類分布式存儲(chǔ)面臨的數(shù)據(jù)需求比較復(fù)雜，大致可以分為三類：●非結(jié)構(gòu)化數(shù)據(jù)：包括所有格式的辦公文檔、文本、圖片、圖像、音頻和視頻信息等?！窠Y(jié)構(gòu)化數(shù)據(jù)：一般存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)中，可以用二維關(guān)系表結(jié)構(gòu)來(lái)表示。結(jié)構(gòu)化數(shù)據(jù)的模式（Schema，包括屬性、數(shù)據(jù)類型以及數(shù)據(jù)之間的聯(lián)系）和內(nèi)容是分開的，數(shù)據(jù)的模式需要預(yù)先定義?！癜虢Y(jié)構(gòu)化數(shù)據(jù)：介于非結(jié)構(gòu)化數(shù)據(jù)和結(jié)構(gòu)化數(shù)據(jù)之間，HTML文檔就屬于半結(jié)構(gòu)化數(shù)據(jù)。它一般是自描述的，與結(jié)構(gòu)化數(shù)據(jù)最大的區(qū)別在于，半結(jié)構(gòu)化數(shù)據(jù)的模式結(jié)構(gòu)和內(nèi)容混在一起，沒有明顯的區(qū)分，也不需要預(yù)先定義數(shù)據(jù)的模式結(jié)構(gòu)。不同的分布式存儲(chǔ)系統(tǒng)適合處理不同類型的數(shù)據(jù)，本書將分布式存儲(chǔ)系統(tǒng)分為四類：分布式文件系統(tǒng)、分布式鍵值（Key-Value）系統(tǒng)、分布式表格系統(tǒng)和分布式數(shù)據(jù)庫(kù)。1.分布式文件系統(tǒng)互聯(lián)網(wǎng)應(yīng)用需要存儲(chǔ)大量的圖片、照片、視頻等非結(jié)構(gòu)化數(shù)據(jù)對(duì)象，這類數(shù)據(jù)以對(duì)象的形式組織，對(duì)象之間沒有關(guān)聯(lián)，這樣的數(shù)據(jù)一般稱為Blob（BinaryLargeObject，二進(jìn)制大對(duì)象）數(shù)據(jù)。分布式文件系統(tǒng)用于存儲(chǔ)Blob對(duì)象，典型的系統(tǒng)有FacebookHaystack以及TaobaoFileSystem（TFS）。另外，分布式文件系統(tǒng)也常作為分布式表格系統(tǒng)以及分布式數(shù)據(jù)庫(kù)的底層存儲(chǔ)，如谷歌的GFS（GoogleFileSystem，存儲(chǔ)大文件）可以作為分布式表格系統(tǒng)GoogleBigtable的底層存儲(chǔ)，Amazon的EBS（ElasticBlockStore，彈性塊存儲(chǔ)）系統(tǒng)可以作為分布式數(shù)據(jù)庫(kù)（AmazonRDS）的底層存儲(chǔ)。總體上看，分布式文件系統(tǒng)存儲(chǔ)三種類型的數(shù)據(jù)：Blob對(duì)象、定長(zhǎng)塊以及大文件。在系統(tǒng)實(shí)現(xiàn)層面，分布式文件系統(tǒng)內(nèi)部按照數(shù)據(jù)塊（chunk）來(lái)組織數(shù)據(jù)，每個(gè)數(shù)據(jù)塊的大小大致相同，每個(gè)數(shù)據(jù)塊可以包含多個(gè)Blob對(duì)象或者定長(zhǎng)塊，一個(gè)大文件也可以拆分為多個(gè)數(shù)據(jù)塊，如圖1-1所示。分布式文件系統(tǒng)將這些數(shù)據(jù)塊分散到存儲(chǔ)集群，處理數(shù)據(jù)復(fù)制、一致性、負(fù)載均衡、容錯(cuò)等分布式系統(tǒng)難題，并將用戶對(duì)Blob對(duì)象、定長(zhǎng)塊以及大文件的操作映射為對(duì)底層數(shù)據(jù)塊的操作。圖1-1數(shù)據(jù)塊與Blob對(duì)象、定長(zhǎng)塊、大文件之間的關(guān)系2.分布式鍵值系統(tǒng)分布式鍵值系統(tǒng)用于存儲(chǔ)關(guān)系簡(jiǎn)單的半結(jié)構(gòu)化數(shù)據(jù)，它只提供基于主鍵的CRUD（Create/Read/Update/Delete）功能，即根據(jù)主鍵創(chuàng)建、讀取、更新或者刪除一條鍵值記錄。典型的系統(tǒng)有AmazonDynamo以及TaobaoTair。從數(shù)據(jù)結(jié)構(gòu)的角度看，分布式鍵值系統(tǒng)與傳統(tǒng)的哈希表比較類似，不同的是，分布式鍵值系統(tǒng)支持將數(shù)據(jù)分布到集群中的多個(gè)存儲(chǔ)節(jié)點(diǎn)。分布式鍵值系統(tǒng)是分布式表格系統(tǒng)的一種簡(jiǎn)化實(shí)現(xiàn)，一般用作緩存，比如淘寶Tair以及Memcache。一致性哈希是分布式鍵值系統(tǒng)中常用的數(shù)據(jù)分布技術(shù)，因其被AmazonDynamoDB系統(tǒng)使用而變得相當(dāng)有名。3.分布式表格系統(tǒng)分布式表格系統(tǒng)用于存儲(chǔ)關(guān)系較為復(fù)雜的半結(jié)構(gòu)化數(shù)據(jù)，與分布式鍵值系統(tǒng)相比，分布式表格系統(tǒng)不僅僅支持簡(jiǎn)單的CRUD操作，而且支持掃描某個(gè)主鍵范圍。分布式表格系統(tǒng)以表格為單位組織數(shù)據(jù)，每個(gè)表格包括很多行，通過(guò)主鍵標(biāo)識(shí)一行，支持根據(jù)主鍵的CRUD功能以及范圍查找功能。分布式表格系統(tǒng)借鑒了很多關(guān)系數(shù)據(jù)庫(kù)的技術(shù)，例如支持某種程度上的事務(wù)，比如單行事務(wù)，某個(gè)實(shí)體組（EntityGroup，一個(gè)用戶下的所有數(shù)據(jù)往往構(gòu)成一個(gè)實(shí)體組）下的多行事務(wù)。典型的系統(tǒng)包括GoogleBigtable以及Megastore,MicrosoftAzureTableStorage,AmazonDynamoDB等。與分布式數(shù)據(jù)庫(kù)相比，分布式表格系統(tǒng)主要支持針對(duì)單張表格的操作，不支持一些特別復(fù)雜的操作，比如多表關(guān)聯(lián)，多表聯(lián)接，嵌套子查詢；另外，在分布式表格系統(tǒng)中，同一個(gè)表格的多個(gè)數(shù)據(jù)行也不要求包含相同類型的列，適合半結(jié)構(gòu)化數(shù)據(jù)。分布式表格系統(tǒng)是一種很好的權(quán)衡，這類系統(tǒng)可以做到超大規(guī)模，而且支持較多的功能，但實(shí)現(xiàn)往往比較復(fù)雜，而且有一定的使用門檻。4.分布式數(shù)據(jù)庫(kù)分布式數(shù)據(jù)庫(kù)一般是從單機(jī)關(guān)系數(shù)據(jù)庫(kù)擴(kuò)展而來(lái)，用于存儲(chǔ)結(jié)構(gòu)化數(shù)據(jù)。分布式數(shù)據(jù)庫(kù)采用二維表格組織數(shù)據(jù)，提供SQL關(guān)系查詢語(yǔ)言，支持多表關(guān)聯(lián)，嵌套子查詢等復(fù)雜操作，并提供數(shù)據(jù)庫(kù)事務(wù)以及并發(fā)控制。典型的系統(tǒng)包括MySQL數(shù)據(jù)庫(kù)分片（MySQLSharding）集群，AmazonRDS以及MicrosoftSQLAzure。分布式數(shù)據(jù)庫(kù)支持的功能最為豐富，符合用戶使用習(xí)慣，但可擴(kuò)展性往往受到限制。當(dāng)然，這一點(diǎn)并不是絕對(duì)的。GoogleSpanner系統(tǒng)是一個(gè)支持多數(shù)據(jù)中心的分布式數(shù)據(jù)庫(kù)，它不僅支持豐富的關(guān)系數(shù)據(jù)庫(kù)功能，還能擴(kuò)展到多個(gè)數(shù)據(jù)中心的成千上萬(wàn)臺(tái)機(jī)器。除此之外，阿里巴巴OceanBase系統(tǒng)也是一個(gè)支持自動(dòng)擴(kuò)展的分布式關(guān)系數(shù)據(jù)庫(kù)。關(guān)系數(shù)據(jù)庫(kù)是目前為止最為成熟的存儲(chǔ)技術(shù)，它的功能極其豐富，產(chǎn)生了商業(yè)的關(guān)系數(shù)據(jù)庫(kù)軟件（例如Oracle,MicrosoftSQLServer,IBMDB2，MySQL）以及上層的工具及應(yīng)用軟件生態(tài)鏈。然而，關(guān)系數(shù)據(jù)庫(kù)在可擴(kuò)展性上面臨著巨大的挑戰(zhàn)。傳統(tǒng)關(guān)系數(shù)據(jù)庫(kù)的事務(wù)以及二維關(guān)系模型很難高效地?cái)U(kuò)展到多個(gè)存儲(chǔ)節(jié)點(diǎn)上，另外，關(guān)系數(shù)據(jù)庫(kù)對(duì)于要求高并發(fā)的應(yīng)用在性能上優(yōu)化空間較大。為了解決關(guān)系數(shù)據(jù)庫(kù)面臨的可擴(kuò)展性、高并發(fā)以及性能方面的問題，各種各樣的非關(guān)系數(shù)據(jù)庫(kù)風(fēng)起云涌，這類系統(tǒng)成為NoSQL系統(tǒng)，可以理解為“NotOnlySQL”系統(tǒng)。NoSQL系統(tǒng)多得讓人眼花繚亂，每個(gè)系統(tǒng)都有自己的獨(dú)到之處，適合解決某種特定的問題。這些系統(tǒng)變化很快，本書不會(huì)嘗試去探尋某種NoSQL系統(tǒng)的實(shí)現(xiàn)，而是從分布式存儲(chǔ)技術(shù)的角度探尋大規(guī)模存儲(chǔ)系統(tǒng)背后的原理。第2章單機(jī)存儲(chǔ)系統(tǒng)單機(jī)存儲(chǔ)引擎就是哈希表、B樹等數(shù)據(jù)結(jié)構(gòu)在機(jī)械磁盤、SSD等持久化介質(zhì)上的實(shí)現(xiàn)。單機(jī)存儲(chǔ)系統(tǒng)是單機(jī)存儲(chǔ)引擎的一種封裝，對(duì)外提供文件、鍵值、表格或者關(guān)系模型。單機(jī)存儲(chǔ)系統(tǒng)的理論來(lái)源于關(guān)系數(shù)據(jù)庫(kù)。數(shù)據(jù)庫(kù)將一個(gè)或多個(gè)操作組成一組，稱作事務(wù)，事務(wù)必須滿足原子性（Atomicity）、一致性（Consistency）、隔離性（Isolation）以及持久性（Durability），簡(jiǎn)稱為ACID特性。多個(gè)事務(wù)并發(fā)執(zhí)行時(shí)，數(shù)據(jù)庫(kù)的并發(fā)控制管理器必須能夠保證多個(gè)事務(wù)的執(zhí)行結(jié)果不能破壞某種約定，如不能出現(xiàn)事務(wù)執(zhí)行到一半的情況，不能讀取到未提交的事務(wù)，等等。為了保證持久性，對(duì)于數(shù)據(jù)庫(kù)的每一個(gè)變化都要在磁盤上記錄日志，當(dāng)數(shù)據(jù)庫(kù)系統(tǒng)突然發(fā)生故障，重啟后能夠恢復(fù)到之前一致的狀態(tài)。本章首先介紹CPU、IO、網(wǎng)絡(luò)等硬件基礎(chǔ)知識(shí)及性能參數(shù)，接著介紹主流的單機(jī)存儲(chǔ)引擎。其中，哈希存儲(chǔ)引擎是哈希表的持久化實(shí)現(xiàn)，B樹存儲(chǔ)引擎是B樹的持久化實(shí)現(xiàn)，而LSM樹（LogStructureMergeTree）存儲(chǔ)引擎采用批量轉(zhuǎn)儲(chǔ)技術(shù)來(lái)避免磁盤隨機(jī)寫入。最后，介紹關(guān)系數(shù)據(jù)庫(kù)理論基礎(chǔ)，包括事務(wù)、并發(fā)控制、故障恢復(fù)、數(shù)據(jù)壓縮等。2.1硬件基礎(chǔ)硬件發(fā)展很快，摩爾定律告訴我們：每18個(gè)月計(jì)算機(jī)等IT產(chǎn)品的性能會(huì)翻一番；或者說(shuō)相同性能的計(jì)算機(jī)等IT產(chǎn)品，每18個(gè)月價(jià)錢會(huì)降一半。但是，計(jì)算機(jī)的硬件體系架構(gòu)保持相對(duì)穩(wěn)定。架構(gòu)設(shè)計(jì)很重要的一點(diǎn)就是合理選擇并且能夠最大限度地發(fā)揮底層硬件的價(jià)值。2.1.1CPU架構(gòu)早期的CPU為單核芯片，工程師們很快意識(shí)到，僅僅提高單核的速度會(huì)產(chǎn)生過(guò)多的熱量且無(wú)法帶來(lái)相應(yīng)的性能改善。因此，現(xiàn)代服務(wù)器基本為多核或多個(gè)CPU。經(jīng)典的多CPU架構(gòu)為對(duì)稱多處理結(jié)構(gòu)（SymmetricMulti-Processing,SMP），即在一個(gè)計(jì)算機(jī)上匯集了一組處理器，它們之間對(duì)稱工作，無(wú)主次或從屬關(guān)系，共享相同的物理內(nèi)存及總線，如圖2-1所示。圖2-1SMP系統(tǒng)結(jié)構(gòu)圖2-1中的SMP系統(tǒng)由兩個(gè)CPU組成，每個(gè)CPU有兩個(gè)核心（core），CPU與內(nèi)存之間通過(guò)總線通信。每個(gè)核心有各自的L1dCache（L1數(shù)據(jù)緩存）及L1iCache（L1指令緩存），同一個(gè)CPU的多個(gè)核心共享L2以及L3緩存，另外，某些CPU還可以通過(guò)超線程技術(shù)（Hyper-ThreadingTechnology）使得一個(gè)核心具有同時(shí)執(zhí)行兩個(gè)線程的能力。SMP架構(gòu)的主要特征是共享，系統(tǒng)中所有資源（CPU、內(nèi)存、I/O等）都是共享的，由于多CPU對(duì)前端總線的競(jìng)爭(zhēng)，SMP的擴(kuò)展能力非常有限。為了提高可擴(kuò)展性，現(xiàn)在的主流服務(wù)器架構(gòu)一般為NUMA（Non-UniformMemoryAccess，非一致存儲(chǔ)訪問）架構(gòu)。它具有多個(gè)NUMA節(jié)點(diǎn)，每個(gè)NUMA節(jié)點(diǎn)是一個(gè)SMP結(jié)構(gòu)，一般由多個(gè)CPU（如4個(gè)）組成，并且具有獨(dú)立的本地內(nèi)存、IO槽口等。圖2-2為包含4個(gè)NUMA節(jié)點(diǎn)的服務(wù)器架構(gòu)圖，NUMA節(jié)點(diǎn)可以直接快速訪問本地內(nèi)存，也可以通過(guò)NUMA互聯(lián)互通模塊訪問其他NUMA節(jié)點(diǎn)的內(nèi)存，訪問本地內(nèi)存的速度遠(yuǎn)遠(yuǎn)高于遠(yuǎn)程訪問的速度。由于這個(gè)特點(diǎn)，為了更好地發(fā)揮系統(tǒng)性能，開發(fā)應(yīng)用程序時(shí)需要盡量減少不同NUMA節(jié)點(diǎn)之間的信息交互。圖2-2NUMA架構(gòu)示例2.1.2IO總線存儲(chǔ)系統(tǒng)的性能瓶頸一般在于IO，因此，有必要對(duì)IO子系統(tǒng)的架構(gòu)有一個(gè)大致的了解。以Intelx48主板為例，它是典型的南、北橋架構(gòu)，如圖2-3所示。北橋芯片通過(guò)前端總線（FrontSideBus,FSB）與CPU相連，內(nèi)存模塊以及PCI-E設(shè)備（如高端的SSD設(shè)備Fusion-IO）掛接在北橋上。北橋與南橋之間通過(guò)DMI連接，DMI的帶寬為1GB/s，網(wǎng)卡（包括千兆以及萬(wàn)兆網(wǎng)卡），硬盤以及中低端固態(tài)盤（如Intel320系列SSD）掛接在南橋上。如果采用SATAZ接口，那么最大帶寬為300MB/s。圖2-3IntelX48主板南北橋架構(gòu)2.1.3網(wǎng)絡(luò)拓?fù)鋱D2-4為傳統(tǒng)的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)洌伎七^(guò)去一直提倡這樣的拓?fù)?，分為三層，最下面是接入層（Edge），中間是匯聚層（Aggregation），上面是核心層（Core）。典型的接入層交換機(jī)包含48個(gè)1Gb端口以及4個(gè)10Gb上行端口，匯聚層以及核心層的交換機(jī)包含128個(gè)10Gb的端口。傳統(tǒng)三層結(jié)構(gòu)的問題在于可能有很多接入層的交換機(jī)接到匯聚層，很多的匯聚層交換機(jī)接到核心層。同一個(gè)接入層下的服務(wù)器之間帶寬為1Gb，不同接入層交換機(jī)下的服務(wù)器之間的帶寬小于1Gb。由于同一個(gè)接入層的服務(wù)器往往部署在一個(gè)機(jī)架內(nèi)，因此，設(shè)計(jì)系統(tǒng)的時(shí)候需要考慮服務(wù)器是否在一個(gè)機(jī)架內(nèi)，減少跨機(jī)架拷貝大量數(shù)據(jù)。例如，HadoopHDFS默認(rèn)存儲(chǔ)三個(gè)副本，其中兩個(gè)副本放在同一個(gè)機(jī)架，就是這個(gè)原因。圖2-4數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)洌ㄈ龑咏Y(jié)構(gòu)）為了減少系統(tǒng)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的依賴，Google在2008年的時(shí)候?qū)⒕W(wǎng)絡(luò)改造為扁平化拓?fù)浣Y(jié)構(gòu)，即三級(jí)CLOS網(wǎng)絡(luò)，同一個(gè)集群內(nèi)最多支持20480臺(tái)服務(wù)器，且任何兩臺(tái)都有1Gb帶寬。CLOS網(wǎng)絡(luò)需要額外投入更多的交換機(jī)，帶來(lái)的好處也是明顯的，設(shè)計(jì)系統(tǒng)時(shí)不需要考慮底層網(wǎng)絡(luò)拓?fù)?，從而很方便地將整個(gè)集群做成一個(gè)計(jì)算資源池。同一個(gè)數(shù)據(jù)中心內(nèi)部的傳輸延時(shí)是比較小的，網(wǎng)絡(luò)一次來(lái)回的時(shí)間在1毫秒之內(nèi)。數(shù)據(jù)中心之間的傳輸延遲是很大的，取決于光在光纖中的傳輸時(shí)間。例如，北京與杭州之間的直線距離大約為1300公里，光在信息傳輸中走折線，假設(shè)折線距離為直線距離的1.5倍，那么光傳輸一次網(wǎng)絡(luò)來(lái)回延時(shí)的理論值為1300×1.5×2/300000=13毫秒，實(shí)際測(cè)試值大約為40毫秒。2.1.4性能參數(shù)常見硬件的大致性能參數(shù)如表2-1所示。磁盤讀寫帶寬還是不錯(cuò)的，15000轉(zhuǎn)的SATA盤的順序讀取帶寬可以達(dá)到100MB以上，由于磁盤尋道的時(shí)間大約為10ms，順序讀取1MB數(shù)據(jù)的時(shí)間為：磁盤尋道時(shí)間+數(shù)據(jù)讀取時(shí)間，即10ms+1MB/100MB/s×1000=20ms。存儲(chǔ)系統(tǒng)的性能瓶頸主要在于磁盤隨機(jī)讀寫。設(shè)計(jì)存儲(chǔ)引擎的時(shí)候會(huì)針對(duì)磁盤的特性做很多的處理，比如將隨機(jī)寫操作轉(zhuǎn)化為順序?qū)懀ㄟ^(guò)緩存減少磁盤隨機(jī)讀操作。固態(tài)磁盤（SSD）在最近幾年得到越來(lái)越多的關(guān)注，各大互聯(lián)網(wǎng)公司都有大量基于SSD的應(yīng)用。SSD的特點(diǎn)是隨機(jī)讀取延遲小，能夠提供很高的IOPS（每秒讀寫，Input/OutputPerSecond）性能。它的主要問題在于容量和價(jià)格，設(shè)計(jì)存儲(chǔ)系統(tǒng)的時(shí)候一般可以用來(lái)做緩存或者性能要求較高的關(guān)鍵業(yè)務(wù)。不同的持久化存儲(chǔ)介質(zhì)對(duì)比如表2-2所示。從表2-2可以看出，SSD單位成本提供的IOPS比傳統(tǒng)的SAS或者SATA磁盤都要大得多，而且SSD功耗低，更加環(huán)保，適合小數(shù)據(jù)量并且對(duì)性能要求更高的場(chǎng)景。2.1.5存儲(chǔ)層次架構(gòu)從分布式系統(tǒng)的角度看，整個(gè)集群中所有服務(wù)器上的存儲(chǔ)介質(zhì)（內(nèi)存、機(jī)械硬盤，SSD）構(gòu)成一個(gè)整體，其他服務(wù)器上的存儲(chǔ)介質(zhì)與本機(jī)存儲(chǔ)介質(zhì)一樣都是可訪問的，區(qū)別僅僅在于需要額外的網(wǎng)絡(luò)傳輸及網(wǎng)絡(luò)協(xié)議棧等訪問開銷。如圖2-5所示，假設(shè)集群中有30個(gè)機(jī)架，每個(gè)機(jī)架接入40臺(tái)服務(wù)器，同一個(gè)機(jī)架的服務(wù)器接入到同一個(gè)接入交換機(jī)，不同機(jī)架的服務(wù)器接入到不同的接入交換機(jī)。每臺(tái)服務(wù)器的內(nèi)存為24GB，磁盤為10×1TB的SATA機(jī)械硬盤（15000轉(zhuǎn)）或者10×160GB的SSD固態(tài)硬盤。那么，對(duì)于每臺(tái)服務(wù)器，本地內(nèi)存大小為24GB，訪問延時(shí)為100ns，本地SATA磁盤的大小為4TB（假設(shè)利用率為40%），隨機(jī)訪問的尋道時(shí)間為10ms，本地SSD磁盤的大小為1TB（假設(shè)利用率為60%），訪問延時(shí)為0.1ms,SATA磁盤和SSD的訪問帶寬受限于SATA接口，最大不超過(guò)300MB/s。同一個(gè)機(jī)架下的服務(wù)器的內(nèi)存總量大致為1TB，訪問延時(shí)和帶寬受限于網(wǎng)絡(luò)，訪問延時(shí)大約為300μs，帶寬為100MB/s，磁盤總?cè)萘繛?60TB，訪問延時(shí)為網(wǎng)絡(luò)延時(shí)加上磁盤尋道時(shí)間，大約為11ms,SSD容量為40TB，訪問延時(shí)為網(wǎng)絡(luò)延時(shí)加上SSD訪問延時(shí)，大約為2ms。整個(gè)集群下所有服務(wù)器的內(nèi)存總量為30TB，訪問延時(shí)和帶寬受限于網(wǎng)絡(luò)，跨機(jī)架訪問需要經(jīng)過(guò)聚合層或者核心層的交換機(jī)，訪問延時(shí)大約為500μs，帶寬大約為10MB/s，磁盤和SSD的訪問延時(shí)分別為11ms以及2ms，帶寬為10MB/s。圖2-5存儲(chǔ)層次結(jié)構(gòu)圖存儲(chǔ)系統(tǒng)的性能主要包括兩個(gè)維度：吞吐量以及訪問延時(shí)，設(shè)計(jì)系統(tǒng)時(shí)要求能夠在保證訪問延時(shí)的基礎(chǔ)上，通過(guò)最低的成本實(shí)現(xiàn)盡可能高的吞吐量。磁盤和SSD的訪問延時(shí)差別很大，但帶寬差別不大，因此，磁盤適合大塊順序訪問的存儲(chǔ)系統(tǒng)，SSD適合隨機(jī)訪問較多或者對(duì)延時(shí)比較敏感的關(guān)鍵系統(tǒng)。二者也常常組合在一起進(jìn)行混合存儲(chǔ)，熱數(shù)據(jù)（訪問頻繁）存儲(chǔ)到SSD中，冷數(shù)據(jù)（訪問不頻繁）存儲(chǔ)到磁盤中。2.2單機(jī)存儲(chǔ)引擎存儲(chǔ)引擎是存儲(chǔ)系統(tǒng)的發(fā)動(dòng)機(jī)，直接決定了存儲(chǔ)系統(tǒng)能夠提供的性能和功能。存儲(chǔ)系統(tǒng)的基本功能包括：增、刪、讀、改，其中，讀取操作又分為隨機(jī)讀取和順序掃描。哈希存儲(chǔ)引擎是哈希表的持久化實(shí)現(xiàn)，支持增、刪、改，以及隨機(jī)讀取操作，但不支持順序掃描，對(duì)應(yīng)的存儲(chǔ)系統(tǒng)為鍵值（Key-Value）存儲(chǔ)系統(tǒng)；B樹（B-Tree）存儲(chǔ)引擎是B樹的持久化實(shí)現(xiàn)，不僅支持單條記錄的增、刪、讀、改操作，還支持順序掃描，對(duì)應(yīng)的存儲(chǔ)系統(tǒng)是關(guān)系數(shù)據(jù)庫(kù)。當(dāng)然，鍵值系統(tǒng)也可以通過(guò)B樹存儲(chǔ)引擎實(shí)現(xiàn)；LSM樹（Log-StructuredMergeTree）存儲(chǔ)引擎和B樹存儲(chǔ)引擎一樣，支持增、刪、改、隨機(jī)讀取以及順序掃描。它通過(guò)批量轉(zhuǎn)儲(chǔ)技術(shù)規(guī)避磁盤隨機(jī)寫入問題，廣泛應(yīng)用于互聯(lián)網(wǎng)的后臺(tái)存儲(chǔ)系統(tǒng)，例如GoogleBigtable、GoogleLevelDB以及Facebook開源的Cassandra系統(tǒng)。本節(jié)分別以Bitcask、MySQLInnoDB以及GoogleLevelDB系統(tǒng)為例介紹這三種存儲(chǔ)引擎。2.2.1哈希存儲(chǔ)引擎Bitcask是一個(gè)基于哈希表結(jié)構(gòu)的鍵值存儲(chǔ)系統(tǒng)，它僅支持追加操作（Append-only），即所有的寫操作只追加而不修改老的數(shù)據(jù)。在Bitcask系統(tǒng)中，每個(gè)文件有一定的大小限制，當(dāng)文件增加到相應(yīng)的大小時(shí)，就會(huì)產(chǎn)生一個(gè)新的文件，老的文件只讀不寫。在任意時(shí)刻，只有一個(gè)文件是可寫的，用于數(shù)據(jù)追加，稱為活躍數(shù)據(jù)文件（activedatafile）。而其他已經(jīng)達(dá)到大小限制的文件，稱為老數(shù)據(jù)文件（olderdatafile）。1.數(shù)據(jù)結(jié)構(gòu)如圖2-6所示，Bitcask數(shù)據(jù)文件中的數(shù)據(jù)是一條一條的寫入操作，每一條記錄的數(shù)據(jù)項(xiàng)分別為主鍵（key）、value內(nèi)容（value）、主鍵長(zhǎng)度（key_sz）、value長(zhǎng)度（value_sz）、時(shí)間戳（timestamp）以及crc校驗(yàn)值。（數(shù)據(jù)刪除操作也不會(huì)刪除舊的條目，而是將value設(shè)定為一個(gè)特殊的值用作標(biāo)識(shí)）。內(nèi)存中采用基于哈希表的索引數(shù)據(jù)結(jié)構(gòu)，哈希表的作用是通過(guò)主鍵快速地定位到value的位置。哈希表結(jié)構(gòu)中的每一項(xiàng)包含了三個(gè)用于定位數(shù)據(jù)的信息，分別是文件編號(hào)（fileid），value在文件中的位置（value_pos），value長(zhǎng)度（value_sz），通過(guò)讀取file_id對(duì)應(yīng)文件的value_pos開始的value_sz個(gè)字節(jié)，這就得到了最終的value值。寫入時(shí)首先將Key-Value記錄追加到活躍數(shù)據(jù)文件的末尾，接著更新內(nèi)存哈希表，因此，每個(gè)寫操作總共需要進(jìn)行一次順序的磁盤寫入和一次內(nèi)存操作。圖2-6Bitcask數(shù)據(jù)結(jié)構(gòu)Bitcask在內(nèi)存中存儲(chǔ)了主鍵和value的索引信息，磁盤文件中存儲(chǔ)了主鍵和value的實(shí)際內(nèi)容。系統(tǒng)基于一個(gè)假設(shè)，value的長(zhǎng)度遠(yuǎn)大于主鍵的長(zhǎng)度。假如value的平均長(zhǎng)度為1KB，每條記錄在內(nèi)存中的索引信息為32字節(jié)，那么，磁盤內(nèi)存比為32:1。這樣，32GB內(nèi)存索引的數(shù)據(jù)量為32GB×32=1TB。2.定期合并Bitcask系統(tǒng)中的記錄刪除或者更新后，原來(lái)的記錄成為垃圾數(shù)據(jù)。如果這些數(shù)據(jù)一直保存下去，文件會(huì)無(wú)限膨脹下去，為了解決這個(gè)問題，Bitcask需要定期執(zhí)行合并（Compaction）操作以實(shí)現(xiàn)垃圾回收。所謂合并操作，即將所有老數(shù)據(jù)文件中的數(shù)據(jù)掃描一遍并生成新的數(shù)據(jù)文件，這里的合并其實(shí)就是對(duì)同一個(gè)key的多個(gè)操作以只保留最新一個(gè)的原則進(jìn)行刪除，每次合并后，新生成的數(shù)據(jù)文件就不再有冗余數(shù)據(jù)了。3.快速恢復(fù)Bitcask系統(tǒng)中的哈希索引存儲(chǔ)在內(nèi)存中，如果不做額外的工作，服務(wù)器斷電重啟重建哈希表需要掃描一遍數(shù)據(jù)文件，如果數(shù)據(jù)文件很大，這是一個(gè)非常耗時(shí)的過(guò)程。Bitcask通過(guò)索引文件（hintfile）來(lái)提高重建哈希表的速度。簡(jiǎn)單來(lái)說(shuō)，索引文件就是將內(nèi)存中的哈希索引表轉(zhuǎn)儲(chǔ)到磁盤生成的結(jié)果文件。Bitcask對(duì)老數(shù)據(jù)文件進(jìn)行合并操作時(shí)，會(huì)產(chǎn)生新的數(shù)據(jù)文件，這個(gè)過(guò)程中還會(huì)產(chǎn)生一個(gè)索引文件，這個(gè)索引文件記錄每一條記錄的哈希索引信息。與數(shù)據(jù)文件不同的是，索引文件并不存儲(chǔ)具體的value值，只存儲(chǔ)value的位置（與內(nèi)存哈希表一樣）。這樣，在重建哈希表時(shí)，就不需要掃描所有數(shù)據(jù)文件，而僅僅需要將索引文件中的數(shù)據(jù)一行行讀取并重建即可，大大減少了重啟后的恢復(fù)時(shí)間。2.2.2B樹存儲(chǔ)引擎相比哈希存儲(chǔ)引擎，B樹存儲(chǔ)引擎不僅支持隨機(jī)讀取，還支持范圍掃描。關(guān)系數(shù)據(jù)庫(kù)中通過(guò)索引訪問數(shù)據(jù)，在MysqlInnoDB中，有一個(gè)稱為聚集索引的特殊索引，行的數(shù)據(jù)存于其中，組織成B+樹（B樹的一種）數(shù)據(jù)結(jié)構(gòu)。1.數(shù)據(jù)結(jié)構(gòu)如圖2-7所示，MySQLInnoDB按照頁(yè)面（Page）來(lái)組織數(shù)據(jù)，每個(gè)頁(yè)面對(duì)應(yīng)B+樹的一個(gè)節(jié)點(diǎn)。其中，葉子節(jié)點(diǎn)保存每行的完整數(shù)據(jù)，非葉子節(jié)點(diǎn)保存索引信息。數(shù)據(jù)在每個(gè)節(jié)點(diǎn)中有序存儲(chǔ)，數(shù)據(jù)庫(kù)查詢時(shí)需要從根節(jié)點(diǎn)開始二分查找直到葉子節(jié)點(diǎn)，每次讀取一個(gè)節(jié)點(diǎn)，如果對(duì)應(yīng)的頁(yè)面不在內(nèi)存中，需要從磁盤中讀取并緩存起來(lái)。B+樹的根節(jié)點(diǎn)是常駐內(nèi)存的，因此，B+樹一次檢索最多需要h-1次磁盤IO，復(fù)雜度為O（h）=O（logdN）（N為元素個(gè)數(shù)，d為每個(gè)節(jié)點(diǎn)的出度，h為B+樹高度）。修改操作首先需要記錄提交日志，接著修改內(nèi)存中的B+樹。如果內(nèi)存中的被修改過(guò)的頁(yè)面超過(guò)一定的比率，后臺(tái)線程會(huì)將這些頁(yè)面刷到磁盤中持久化。當(dāng)然，InnoDB實(shí)現(xiàn)時(shí)做了大量的優(yōu)化，這部分內(nèi)容已經(jīng)超出了本書的范圍。圖2-7B+樹存儲(chǔ)引擎2.緩沖區(qū)管理緩沖區(qū)管理器負(fù)責(zé)將可用的內(nèi)存劃分成緩沖區(qū)，緩沖區(qū)是與頁(yè)面同等大小的區(qū)域，磁盤塊的內(nèi)容可以傳送到緩沖區(qū)中。緩沖區(qū)管理器的關(guān)鍵在于替換策略，即選擇將哪些頁(yè)面淘汰出緩沖池。常見的算法有以下兩種。（1）LRULRU算法淘汰最長(zhǎng)時(shí)間沒有讀或者寫過(guò)的塊。這種方法要求緩沖區(qū)管理器按照頁(yè)面最后一次被訪問的時(shí)間組成一個(gè)鏈表，每次淘汰鏈表尾部的頁(yè)面。直覺上，長(zhǎng)時(shí)間沒有讀寫的頁(yè)面比那些最近訪問過(guò)的頁(yè)面有更小的最近訪問的可能性。（2）LIRSLRU算法在大多數(shù)情況下表現(xiàn)是不錯(cuò)的，但有一個(gè)問題：假如某一個(gè)查詢做了一次全表掃描，將導(dǎo)致緩沖池中的大量頁(yè)面（可能包含很多很快被訪問的熱點(diǎn)頁(yè)面）被替換，從而污染緩沖池?，F(xiàn)代數(shù)據(jù)庫(kù)一般采用LIRS算法，將緩沖池分為兩級(jí)，數(shù)據(jù)首先進(jìn)入第一級(jí)，如果數(shù)據(jù)在較短的時(shí)間內(nèi)被訪問兩次或者以上，則成為熱點(diǎn)數(shù)據(jù)進(jìn)入第二級(jí)，每一級(jí)內(nèi)部還是采用LRU替換算法。Oracle數(shù)據(jù)庫(kù)中的TouchCount算法和MySQLInnoDB中的替換算法都采用了類似的分級(jí)思想。以MySQLInnoDB為例，InnoDB內(nèi)部的LRU鏈表分為兩部分：新子鏈表（newsublist）和老子鏈表（oldsublist），默認(rèn)情況下，前者占5/8，后者占3/8。頁(yè)面首先插入到老子鏈表，InnoDB要求頁(yè)面在老子鏈表停留時(shí)間超過(guò)一定值，比如1秒，才有可能被轉(zhuǎn)移到新子鏈表。當(dāng)出現(xiàn)全表掃描時(shí)，InnoDB將數(shù)據(jù)頁(yè)面載入到老子鏈表，由于數(shù)據(jù)頁(yè)面在老子鏈表中的停留時(shí)間不夠，不會(huì)被轉(zhuǎn)移到新子鏈表中，這就避免了新子鏈表中的頁(yè)面被替換出去的情況。2.2.3LSM樹存儲(chǔ)引擎LSM樹（LogStructuredMergeTree）的思想非常樸素，就是將對(duì)數(shù)據(jù)的修改增量保持在內(nèi)存中，達(dá)到指定的大小限制后將這些修改操作批量寫入磁盤，讀取時(shí)需要合并磁盤中的歷史數(shù)據(jù)和內(nèi)存中最近的修改操作。LSM樹的優(yōu)勢(shì)在于有效地規(guī)避了磁盤隨機(jī)寫入問題，但讀取時(shí)可能需要訪問較多的磁盤文件。本節(jié)介紹LevelDB中的LSM樹存儲(chǔ)引擎。1.存儲(chǔ)結(jié)構(gòu)如圖2-8所示，LevelDB存儲(chǔ)引擎主要包括：內(nèi)存中的MemTable和不可變MemTable（ImmutableMemTable，也稱為FrozenMemTable，即凍結(jié)MemTable）以及磁盤上的幾種主要文件：當(dāng)前（Current）文件、清單（Manifest）文件、操作日志（CommitLog，也稱為提交日志）文件以及SSTable文件。當(dāng)應(yīng)用寫入一條記錄時(shí)，LevelDB會(huì)首先將修改操作寫入到操作日志文件，成功后再將修改操作應(yīng)用到MemTable，這樣就完成了寫入操作。圖2-8LevelDB存儲(chǔ)引擎當(dāng)MemTable占用的內(nèi)存達(dá)到一個(gè)上限值后，需要將內(nèi)存的數(shù)據(jù)轉(zhuǎn)儲(chǔ)到外存文件中。LevelDB會(huì)將原先的MemTable凍結(jié)成為不可變MemTable，并生成一個(gè)新的MemTable。新到來(lái)的數(shù)據(jù)被記入新的操作日志文件和新生成的MemTable中。顧名思義，不可變MemTable的內(nèi)容是不可更改的，只能讀取不能寫入或者刪除。LevelDB后臺(tái)線程會(huì)將不可變MemTable的數(shù)據(jù)排序后轉(zhuǎn)儲(chǔ)到磁盤，形成一個(gè)新的SSTable文件，這個(gè)操作稱為Compaction。SSTable文件是內(nèi)存中的數(shù)據(jù)不斷進(jìn)行Compaction操作后形成的，且SSTable的所有文件是一種層級(jí)結(jié)構(gòu)，第0層為L(zhǎng)evel0，第1層為L(zhǎng)evel1，以此類推。SSTable中的文件是按照記錄的主鍵排序的，每個(gè)文件有最小的主鍵和最大的主鍵。LevelDB的清單文件記錄了這些元數(shù)據(jù)，包括屬于哪個(gè)層級(jí)、文件名稱、最小主鍵和最大主鍵。當(dāng)前文件記錄了當(dāng)前使用的清單文件名。在LevelDB的運(yùn)行過(guò)程中，隨著Compaction的進(jìn)行，SSTable文件會(huì)發(fā)生變化，新的文件會(huì)產(chǎn)生，老的文件被廢棄，此時(shí)往往會(huì)生成新的清單文件來(lái)記載這種變化，而當(dāng)前文件則用來(lái)指出哪個(gè)清單文件才是當(dāng)前有效的。直觀上，LevelDB每次查詢都需要從老到新讀取每個(gè)層級(jí)的SSTable文件以及內(nèi)存中的MemTable。LevelDB做了一個(gè)優(yōu)化，由于LevelDB對(duì)外只支持隨機(jī)讀取單條記錄，查詢時(shí)LevelDB首先會(huì)去查看內(nèi)存中的MemTable，如果MemTable包含記錄的主鍵及其對(duì)應(yīng)的值，則返回記錄即可；如果MemTable沒有讀到該主鍵，則接下來(lái)到同樣處于內(nèi)存中的不可變Memtable中去讀??；類似地，如果還是沒有讀到，只能依次從新到老讀取磁盤中的SSTable文件。2.合并LevelDB寫入操作很簡(jiǎn)單，但是讀取操作比較復(fù)雜，需要在內(nèi)存以及各個(gè)層級(jí)文件中按照從新到老依次查找，代價(jià)很高。為了加快讀取速度，LevelDB內(nèi)部會(huì)執(zhí)行Compaction操作來(lái)對(duì)已有的記錄進(jìn)行整理壓縮，從而刪除一些不再有效的記錄，減少數(shù)據(jù)規(guī)模和文件數(shù)量。LevelDB的Compaction操作分為兩種：minorcompaction和majorcompaction。Minorcompaction是指當(dāng)內(nèi)存中的MemTable大小到了一定值時(shí)，將內(nèi)存數(shù)據(jù)轉(zhuǎn)儲(chǔ)到SSTable文件中。每個(gè)層級(jí)下有多個(gè)SSTable，當(dāng)某個(gè)層級(jí)下的SSTable文件數(shù)目超過(guò)一定設(shè)置值后，levelDB會(huì)從這個(gè)層級(jí)中選擇SSTable文件，將其和高一層級(jí)的SSTable文件合并，這就是majorcompaction。majorcompaction相當(dāng)于執(zhí)行一次多路歸并：按照主鍵順序依次迭代出所有SSTable文件中的記錄，如果沒有保存價(jià)值，則直接拋棄；否則，將其寫入到新生成的SSTable文件中。2.3數(shù)據(jù)模型如果說(shuō)存儲(chǔ)引擎相當(dāng)于存儲(chǔ)系統(tǒng)的發(fā)動(dòng)機(jī)，那么，數(shù)據(jù)模型就是存儲(chǔ)系統(tǒng)的外殼。存儲(chǔ)系統(tǒng)的數(shù)據(jù)模型主要包括三類：文件、關(guān)系以及隨著NoSQL技術(shù)流行起來(lái)的鍵值模型。傳統(tǒng)的文件系統(tǒng)和關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)分別采用文件和關(guān)系模型。關(guān)系模型描述能力強(qiáng)，產(chǎn)業(yè)鏈完整，是存儲(chǔ)系統(tǒng)的業(yè)界標(biāo)準(zhǔn)。然而，隨著應(yīng)用在可擴(kuò)展性、高并發(fā)以及性能上提出越來(lái)越高的要求，大而全的關(guān)系數(shù)據(jù)庫(kù)有時(shí)顯得力不從心，因此，產(chǎn)生了一些新的數(shù)據(jù)模型，比如鍵值模型，關(guān)系弱化的表格模型，等等。2.3.1文件模型文件系統(tǒng)以目錄樹的形式組織文件，以類UNIX操作系統(tǒng)為例，根目錄為/，包含/usr、/bin、/home等子目錄，每個(gè)子目錄又包含其他子目錄或者文件。文件系統(tǒng)的操作涉及目錄以及文件，例如，打開/關(guān)閉文件、讀寫文件、遍歷目錄、設(shè)置文件屬性等。POSIX（PortableOperatingSystemInterface）是應(yīng)用程序訪問文件系統(tǒng)的API標(biāo)準(zhǔn)，它定義了文件系統(tǒng)存儲(chǔ)接口及操作集。POSIX主要接口如下所示?！馩pen/close：打開/關(guān)閉一個(gè)文件，獲取文件描述符；●Read/write：讀取一個(gè)文件或者往文件中寫入數(shù)據(jù)；●Opendir/closedir：打開或者關(guān)閉一個(gè)目錄；●Readdir：遍歷目錄。POSIX標(biāo)準(zhǔn)不僅定義了文件操作接口，而且還定義了讀寫操作語(yǔ)義。例如，POSIX標(biāo)準(zhǔn)要求讀寫并發(fā)時(shí)能夠保證操作的原子性，即讀操作要么讀到所有結(jié)果，要么什么也讀不到；另外，要求讀操作能夠讀到之前所有寫操作的結(jié)果。POSIX標(biāo)準(zhǔn)適合單機(jī)文件系統(tǒng)，在分布式文件系統(tǒng)中，出于性能考慮，一般不會(huì)完全遵守這個(gè)標(biāo)準(zhǔn)。NFS（NetworkFileSystem）文件系統(tǒng)允許客戶端緩存文件數(shù)據(jù)，多個(gè)客戶端并發(fā)修改同一個(gè)文件時(shí)可能出現(xiàn)不一致的情況。舉個(gè)例子，NFS客戶端A和B需要同時(shí)修改NFS服務(wù)器的某個(gè)文件，每個(gè)客戶端都在本地緩存了文件的副本，A修改后先提交，B后提交，那么，即使A和B修改的是文件的不同位置，也會(huì)出現(xiàn)B的修改覆蓋A的情況。對(duì)象模型與文件模型比較類似，用于存儲(chǔ)圖片、視頻、文檔等二進(jìn)制數(shù)據(jù)塊，典型的系統(tǒng)包括AmazonSimpleStorage（S3），TaobaoFileSystem（TFS）。這些系統(tǒng)弱化了目錄樹的概念，AmazonS3只支持一級(jí)目錄，不支持子目錄，TaobaoTFS甚至不支持目錄結(jié)構(gòu)。與文件模型不同的是，對(duì)象模型要求對(duì)象一次性寫入到系統(tǒng)，只能刪除整個(gè)對(duì)象，不允許修改其中某個(gè)部分。2.3.2關(guān)系模型每個(gè)關(guān)系是一個(gè)表格，由多個(gè)元組（行）構(gòu)成，而每個(gè)元組又包含多個(gè)屬性（列）。關(guān)系名、屬性名以及屬性類型稱作該關(guān)系的模式（schema）。例如，Movie關(guān)系的模式為Movie（title,year,length），其中，title、year、length是屬性，假設(shè)它們的類型分別為字符串、整數(shù)、整數(shù)。數(shù)據(jù)庫(kù)語(yǔ)言SQL用于描述查詢以及修改操作。數(shù)據(jù)庫(kù)修改包含三條命令：INSERT、DELETE以及UPDATE，查詢通常通過(guò)select-from-where語(yǔ)句來(lái)表達(dá)，它具有圖2-9所示的一般形式。Select查詢語(yǔ)句計(jì)算過(guò)程大致如下（不考慮查詢優(yōu)化）：圖2-9SQL查詢1）取FROM子句中列出的各個(gè)關(guān)系的元組的所有可能的組合。2）將不符合WHERE子句中給出的條件的元組去掉。3）如果有GROUPBY子句，則將剩下的元組按GROUPBY子句中給出的屬性的值分組。4）如果有HAVING子句，則按照HAVING子句中給出的條件檢查每一個(gè)組，去掉不符合條件的組。5）按照SELECT子句的說(shuō)明，對(duì)于指定的屬性和屬性上的聚集（例如求和）計(jì)算出結(jié)果元組。6）按照ORDERBY子句中的屬性列的值對(duì)結(jié)果元組進(jìn)行排序。SQL查詢還有一個(gè)強(qiáng)大的特性是允許在WHERE、FROM和HAVING子句中使用子查詢，子查詢又是一個(gè)完整的select-from-where語(yǔ)句。另外，SQL還包括兩個(gè)重要的特性：索引以及事務(wù)。其中，數(shù)據(jù)庫(kù)索引用于減少SQL執(zhí)行時(shí)掃描的數(shù)據(jù)量，提高讀取性能；數(shù)據(jù)庫(kù)事務(wù)則規(guī)定了各個(gè)數(shù)據(jù)庫(kù)操作的語(yǔ)義，保證了多個(gè)操作并發(fā)執(zhí)行時(shí)的ACID特性（原子性、一致性、隔離性、持久性），后續(xù)會(huì)專門介紹。2.3.3鍵值模型大量的NoSQL系統(tǒng)采用了鍵值模型（也稱為Key-Value模型），每行記錄由主鍵和值兩個(gè)部分組成，支持基于主鍵的如下操作：●Put：保存一個(gè)Key-Value對(duì)?！馟et：讀取一個(gè)Key-Value對(duì)?！馜elete：刪除一個(gè)Key-Value對(duì)。Key-Value模型過(guò)于簡(jiǎn)單，支持的應(yīng)用場(chǎng)景有限，NoSQL系統(tǒng)中使用比較廣泛的模型是表格模型。表格模型弱化了關(guān)系模型中的多表關(guān)聯(lián)，支持基于單表的簡(jiǎn)單操作，典型的系統(tǒng)是GoogleBigtable以及其開源Java實(shí)現(xiàn)HBase。表格模型除了支持簡(jiǎn)單的基于主鍵的操作，還支持范圍掃描，另外，也支持基于列的操作。主要操作如下：●Insert：插入一行數(shù)據(jù)，每行包括若干列；●Delete：刪除一行數(shù)據(jù)；●Update：更新整行或者其中的某些列的數(shù)據(jù)；●Get：讀取整行或者其中某些列數(shù)據(jù)；●Scan：掃描一段范圍的數(shù)據(jù)，根據(jù)主鍵確定掃描的范圍，支持掃描部分列，支持按列過(guò)濾、排序、分組等。與關(guān)系模型不同的是，表格模型一般不支持多表關(guān)聯(lián)操作，Bigtable這樣的系統(tǒng)也不支持二級(jí)索引，事務(wù)操作支持也比較弱，各個(gè)系統(tǒng)支持的功能差異較大，沒有統(tǒng)一的標(biāo)準(zhǔn)。另外，表格模型往往還支持無(wú)模式（schema-less）特性，也就是說(shuō)，不需要預(yù)先定義每行包括哪些列以及每個(gè)列的類型，多行之間允許包含不同列。2.3.4SQL與NoSQL隨著互聯(lián)網(wǎng)的飛速發(fā)展，數(shù)據(jù)規(guī)模越來(lái)越大，并發(fā)量越來(lái)越高，傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)有時(shí)顯得力不從心，非關(guān)系型數(shù)據(jù)庫(kù)（NoSQL,NotOnlySQL）應(yīng)運(yùn)而生。NoSQL系統(tǒng)帶來(lái)了很多新的理念，比如良好的可擴(kuò)展性，弱化數(shù)據(jù)庫(kù)的設(shè)計(jì)范式，弱化一致性要求，在一定程度上解決了海量數(shù)據(jù)和高并發(fā)的問題，以至于很多人對(duì)“NoSQL是否會(huì)取代SQL”存在疑慮。然而，NoSQL只是對(duì)SQL特性的一種取舍和升華，使得SQL更加適應(yīng)海量數(shù)據(jù)的應(yīng)用場(chǎng)景，二者的優(yōu)勢(shì)將不斷融合，不存在誰(shuí)取代誰(shuí)的問題。關(guān)系數(shù)據(jù)庫(kù)在海量數(shù)據(jù)場(chǎng)景面臨如下挑戰(zhàn)：●事務(wù)關(guān)系模型要求多個(gè)SQL操作滿足ACID特性，所有的SQL操作要么全部成功，要么全部失敗。在分布式系統(tǒng)中，如果多個(gè)操作屬于不同的服務(wù)器，保證它們的原子性需要用到兩階段提交協(xié)議，而這個(gè)協(xié)議的性能很低，且不能容忍服務(wù)器故障，很難應(yīng)用在海量數(shù)據(jù)場(chǎng)景?！衤?lián)表傳統(tǒng)的數(shù)據(jù)庫(kù)設(shè)計(jì)時(shí)需要滿足范式要求，例如，第三范式要求在一個(gè)關(guān)系中不能出現(xiàn)在其他關(guān)系中已包含的非主鍵信息。假設(shè)存在一個(gè)部門信息表，其中每個(gè)部門有部門編號(hào)、部門名稱、部門簡(jiǎn)介等信息，那么在員工信息表中列出部門編號(hào)后就不能加入部門名稱、部門簡(jiǎn)介等部門有關(guān)的信息，否則就會(huì)有大量的數(shù)據(jù)冗余。而在海量數(shù)據(jù)的場(chǎng)景，為了避免數(shù)據(jù)庫(kù)多表關(guān)聯(lián)操作，往往會(huì)使用數(shù)據(jù)冗余等違反數(shù)據(jù)庫(kù)范式的手段。實(shí)踐表明，這些手段帶來(lái)的收益遠(yuǎn)高于成本?！裥阅荜P(guān)系數(shù)據(jù)庫(kù)采用B樹存儲(chǔ)引擎，更新操作性能不如LSM樹這樣的存儲(chǔ)引擎。另外，如果只有基于主鍵的增、刪、查、改操作，關(guān)系數(shù)據(jù)庫(kù)的性能也不如專門定制的Key-Value存儲(chǔ)系統(tǒng)。隨著數(shù)據(jù)規(guī)模越來(lái)越大，可擴(kuò)展性以及性能提升可以帶來(lái)越來(lái)越明顯的收益，而NoSQL系統(tǒng)要么可擴(kuò)展性好，要么在特定的應(yīng)用場(chǎng)景性能很高，廣泛應(yīng)用于互聯(lián)網(wǎng)業(yè)務(wù)中。然而，NoSQL系統(tǒng)也面臨如下問題：●缺少統(tǒng)一標(biāo)準(zhǔn)。經(jīng)過(guò)幾十年的發(fā)展，關(guān)系數(shù)據(jù)庫(kù)已經(jīng)形成了SQL語(yǔ)言這樣的業(yè)界標(biāo)準(zhǔn)，并擁有完整的生態(tài)鏈。然而，各個(gè)NoSQL系統(tǒng)使用方法不同，切換成本高，很難通用?！袷褂靡约斑\(yùn)維復(fù)雜。NoSQL系統(tǒng)無(wú)論是選型，還是使用方式，都有很大的學(xué)問，往往需要理解系統(tǒng)的實(shí)現(xiàn)，另外，缺乏專業(yè)的運(yùn)維工具和運(yùn)維人員。而關(guān)系數(shù)據(jù)庫(kù)具有完整的生態(tài)鏈和豐富的運(yùn)維工具，也有大量經(jīng)驗(yàn)豐富的運(yùn)維人員?？偠灾?，關(guān)系數(shù)據(jù)庫(kù)很通用，是業(yè)界標(biāo)準(zhǔn)，但是在一些特定的應(yīng)用場(chǎng)景存在可擴(kuò)展性和性能的問題，NoSQL系統(tǒng)也有一定的用武之地。從技術(shù)學(xué)習(xí)的角度看，不必糾結(jié)SQL與NoSQL的區(qū)別，而是借鑒二者各自不同的優(yōu)勢(shì)，著重理解關(guān)系數(shù)據(jù)庫(kù)的原理以及NoSQL系統(tǒng)的高可擴(kuò)展性。2.4事務(wù)與并發(fā)控制事務(wù)規(guī)范了數(shù)據(jù)庫(kù)操作的語(yǔ)義，每個(gè)事務(wù)使得數(shù)據(jù)庫(kù)從一個(gè)一致的狀態(tài)原子地轉(zhuǎn)移到另一個(gè)一致的狀態(tài)。數(shù)據(jù)庫(kù)事務(wù)具有原子性（Atomicity）、一致性（Consistency）、隔離性（Isolation）以及持久性（Durability），即ACID屬性，這些特性使得多個(gè)數(shù)據(jù)庫(kù)事務(wù)并發(fā)執(zhí)行時(shí)互不干擾，也不會(huì)獲取到中間狀態(tài)的錯(cuò)誤結(jié)果。多個(gè)事務(wù)并發(fā)執(zhí)行時(shí)，如果它們的執(zhí)行結(jié)果和按照某種順序一個(gè)接著一個(gè)串行執(zhí)行的效果等同，這種隔離級(jí)別稱為可串行化?？纱谢潜容^理想的情況，商業(yè)數(shù)據(jù)庫(kù)為了性能考慮，往往會(huì)定義多種隔離級(jí)別。事務(wù)的并發(fā)控制一般通過(guò)鎖機(jī)制來(lái)實(shí)現(xiàn)，鎖可以有不同的粒度，可以鎖住行，也可以鎖住數(shù)據(jù)塊甚至鎖住整個(gè)表格。由于互聯(lián)網(wǎng)業(yè)務(wù)中讀事務(wù)的比例往往遠(yuǎn)遠(yuǎn)高于寫事務(wù)，為了提高讀事務(wù)性能，可以采用寫時(shí)復(fù)制（Copy-On-Write,COW）或者多版本并發(fā)控制（Multi-VersionConcurrencyControl,MVCC）技術(shù)來(lái)避免寫事務(wù)阻塞讀事務(wù)。2.4.1事務(wù)事務(wù)是數(shù)據(jù)庫(kù)操作的基本單位，它具有原子性、一致性、隔離性和持久性這四個(gè)基本屬性。（1）原子性事務(wù)的原子性首先體現(xiàn)在事務(wù)對(duì)數(shù)據(jù)的修改，即要么全都執(zhí)行，要么全都不執(zhí)行，例如，從銀行賬戶A轉(zhuǎn)一筆款項(xiàng)a到賬戶B，結(jié)果必須是從A的賬戶上扣除款項(xiàng)a并且在B的賬戶上增加款項(xiàng)a，不能只是其中一個(gè)賬戶的修改。但是，事務(wù)的原子性并不總是能夠保證修改一定完成了或者一定沒有進(jìn)行，例如，在ATM機(jī)器上進(jìn)行上述轉(zhuǎn)賬，轉(zhuǎn)賬指令提交后通信中斷或者數(shù)據(jù)庫(kù)主機(jī)異常了，那么轉(zhuǎn)賬可能完成了也可能沒有進(jìn)行：如果通信中斷發(fā)生前數(shù)據(jù)庫(kù)主機(jī)完整接收到了轉(zhuǎn)賬指令且后續(xù)執(zhí)行也正常，那么轉(zhuǎn)賬成功完成了；如果轉(zhuǎn)賬指令沒有到達(dá)數(shù)據(jù)庫(kù)主機(jī)或者雖然到達(dá)但后續(xù)執(zhí)行異常（例如寫操作日志失敗或者賬戶余額不足），那么轉(zhuǎn)賬就沒有進(jìn)行。要確定轉(zhuǎn)賬是否成功，需要待通信恢復(fù)或者數(shù)據(jù)庫(kù)主機(jī)恢復(fù)后查詢賬戶交易歷史或余額。事務(wù)的原子性也體現(xiàn)在事務(wù)對(duì)數(shù)據(jù)的讀取上，例如，一個(gè)事務(wù)對(duì)同一數(shù)據(jù)項(xiàng)的多次讀取的結(jié)果一定是相同的。（2）一致性事務(wù)需要保持?jǐn)?shù)據(jù)庫(kù)數(shù)據(jù)的正確性、完整性和一致性，有些時(shí)候這種一致性由數(shù)據(jù)庫(kù)的內(nèi)部規(guī)則保證，例如數(shù)據(jù)的類型必須正確，數(shù)據(jù)值必須在規(guī)定的范圍內(nèi)，等等；另外一些時(shí)候這種一致性由應(yīng)用保證，例如一般情況下銀行賬務(wù)余額不能是負(fù)數(shù)，信用卡消費(fèi)不能超過(guò)該卡的信用額度等。（3）隔離性許多時(shí)候數(shù)據(jù)庫(kù)在并發(fā)執(zhí)行多個(gè)事務(wù)，每個(gè)事務(wù)可能需要對(duì)多個(gè)表項(xiàng)進(jìn)行修改和查詢，與此同時(shí)，更多的查詢請(qǐng)求可能也在執(zhí)行中。數(shù)據(jù)庫(kù)需要保證每一個(gè)事務(wù)在它的修改全部完成之前，對(duì)其他的事務(wù)是不可見的，換句話說(shuō)，不能讓其他事務(wù)看到該事務(wù)的中間狀態(tài)，例如，從銀行賬戶A轉(zhuǎn)一筆款項(xiàng)a到賬戶B，不能讓其他事務(wù)（例如賬戶查詢）看到A賬戶已經(jīng)扣除款項(xiàng)a但B賬戶卻還沒有增加款項(xiàng)a的狀態(tài)。（4）持久性事務(wù)完成后，它對(duì)于數(shù)據(jù)庫(kù)的影響是永久性的，即使系統(tǒng)出現(xiàn)各種異常也是如此。出于性能考慮，許多數(shù)據(jù)庫(kù)允許使用者選擇犧牲隔離屬性來(lái)?yè)Q取并發(fā)度，從而獲得性能的提升。SQL定義了4種隔離級(jí)別?！馬eadUncommitted（RU）：讀取未提交的數(shù)據(jù)，即其他事務(wù)已經(jīng)修改但還未提交的數(shù)據(jù)，這是最低的隔離級(jí)別；●ReadCommitted（RC）：讀取已提交的數(shù)據(jù)，但是，在一個(gè)事務(wù)中，對(duì)同一個(gè)項(xiàng)，前后兩次讀取的結(jié)果可能不一樣，例如第一次讀取時(shí)另一個(gè)事務(wù)的修改還沒有提交，第二次讀取時(shí)已經(jīng)提交了；●RepeatableRead（RR）：可重復(fù)讀取，在一個(gè)事務(wù)中，對(duì)同一個(gè)項(xiàng)，確保前后兩次讀取的結(jié)果一樣；●Serializable（S）：可序列化，即數(shù)據(jù)庫(kù)的事務(wù)是可串行化執(zhí)行的，就像一個(gè)事務(wù)執(zhí)行的時(shí)候沒有別的事務(wù)同時(shí)在執(zhí)行，這是最高的隔離級(jí)別。隔離級(jí)別的降低可能導(dǎo)致讀到臟數(shù)據(jù)或者事務(wù)執(zhí)行異常，例如：●LostUpdate（LU）：第一類丟失更新：兩個(gè)事務(wù)同時(shí)修改一個(gè)數(shù)據(jù)項(xiàng)，但后一個(gè)事務(wù)中途失敗回滾，則前一個(gè)事務(wù)已提交的修改都可能丟失；●DirtyReads（DR）：一個(gè)事務(wù)讀取了另外一個(gè)事務(wù)更新卻沒有提交的數(shù)據(jù)項(xiàng)；●Non-RepeatableReads（NRR）：一個(gè)事務(wù)對(duì)同一數(shù)據(jù)項(xiàng)的多次讀取可能得到不同的結(jié)果；●SecondLostUpdatesproblem（SLU）：第二類丟失更新：兩個(gè)并發(fā)事務(wù)同時(shí)讀取和修改同一數(shù)據(jù)項(xiàng)，則后面的修改可能使得前面的修改失效；●PhantomReads（PR）：事務(wù)執(zhí)行過(guò)程中，由于前面的查詢和后面的查詢的期間有另外一個(gè)事務(wù)插入數(shù)據(jù)，后面的查詢結(jié)果出現(xiàn)了前面查詢結(jié)果中未出現(xiàn)的數(shù)據(jù)。表2-3說(shuō)明了隔離級(jí)別與讀寫異常（不一致）的關(guān)系。容易發(fā)現(xiàn)，所有的隔離級(jí)別都保證不會(huì)出現(xiàn)第一類丟失更新，另外，在最高隔離級(jí)別（Serializable）下，數(shù)據(jù)不會(huì)出現(xiàn)讀寫的不一致。2.4.2并發(fā)控制1.數(shù)據(jù)庫(kù)鎖事務(wù)分為幾種類型：讀事務(wù)，寫事務(wù)以及讀寫混合事務(wù)。相應(yīng)地，鎖也分為兩種類型：讀鎖以及寫鎖，允許對(duì)同一個(gè)元素加多個(gè)讀鎖，但只允許加一個(gè)寫鎖，且寫事務(wù)將阻塞讀事務(wù)。這里的元素可以是一行，也可以是一個(gè)數(shù)據(jù)塊甚至一個(gè)表格。事務(wù)如果只操作一行，可以對(duì)該行加相應(yīng)的讀鎖或者寫鎖；如果操作多行，需要鎖住整個(gè)行范圍。表2-4中T1和T2兩個(gè)事務(wù)操作不同行，初始時(shí)A=B=25，T1將A加100，T2將B乘以2，由于T1和T2操作不同行，兩個(gè)事務(wù)沒有鎖沖突，可以并行執(zhí)行而不會(huì)破壞系統(tǒng)的一致性。表2-5中T1掃描從A到C的所有行，將它們的結(jié)果相加后更新A，初始時(shí)A=C=25，假設(shè)在T1執(zhí)行過(guò)程中T2插入一行B，那么，事務(wù)T1和T2無(wú)法做到可串行化。為了保證數(shù)據(jù)庫(kù)一致性，T1執(zhí)行范圍掃描時(shí)需要鎖住從A到C這個(gè)范圍的所有更新，T2插入B時(shí)，由于整個(gè)范圍被鎖住，T2獲取鎖失敗而等待T1先執(zhí)行完成。多個(gè)事務(wù)并發(fā)執(zhí)行可能引入死鎖。表2-6中T1讀取A，然后將A的值加100后更新B,T2讀取B，然后將B的值乘以2更新A，初始時(shí)A=B=25。T1持有A的讀鎖，需要獲取B的寫鎖，而T2持有B的讀鎖，需要A的寫鎖。T1和T2這兩個(gè)事務(wù)循環(huán)依賴，任何一個(gè)事務(wù)都無(wú)法順利完成。解決死鎖的思路主要有兩種：第一種思路是為每個(gè)事務(wù)設(shè)置一個(gè)超時(shí)時(shí)間，超時(shí)后自動(dòng)回滾，表2-6中如果T1或T2二者之中的某個(gè)事務(wù)回滾，則另外一個(gè)事務(wù)可以成功執(zhí)行。第二種思路是死鎖檢測(cè)。死鎖出現(xiàn)的原因在于事務(wù)之間互相依賴，T1依賴T2，T2又依賴T1，依賴關(guān)系構(gòu)成一個(gè)環(huán)路。檢測(cè)到死鎖后可以通過(guò)回滾其中某些事務(wù)來(lái)消除循環(huán)依賴。2.寫時(shí)復(fù)制互聯(lián)網(wǎng)業(yè)務(wù)中讀事務(wù)占的比例往往遠(yuǎn)遠(yuǎn)超過(guò)寫事務(wù)，很多應(yīng)用的讀寫比例達(dá)到6:1，甚至10:1。寫時(shí)復(fù)制（Copy-On-Write,COW）讀操作不用加鎖，極大地提高了讀取性能。圖2-10中寫時(shí)復(fù)制B+樹執(zhí)行寫操作的步驟如下。1）拷貝：將從葉子到根節(jié)點(diǎn)路徑上的所有節(jié)點(diǎn)拷貝出來(lái)。2）修改：對(duì)拷貝的節(jié)點(diǎn)執(zhí)行修改。3）提交：原子地切換根節(jié)點(diǎn)的指針，使之指向新的根節(jié)點(diǎn)。如果讀操作發(fā)生在第3步提交之前，那么，將讀取老節(jié)點(diǎn)的數(shù)據(jù)，否則將讀取新節(jié)點(diǎn)，讀操作不需要加鎖保護(hù)。寫時(shí)復(fù)制技術(shù)涉及引用計(jì)數(shù)，對(duì)每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)引用計(jì)數(shù)，表示被多少節(jié)點(diǎn)引用，如果引用計(jì)數(shù)變?yōu)?，說(shuō)明沒有節(jié)點(diǎn)引用，可以被垃圾回收。寫時(shí)復(fù)制技術(shù)原理簡(jiǎn)單，問題是每次寫操作都需要拷貝從葉子到根節(jié)點(diǎn)路徑上的所有節(jié)點(diǎn)，寫操作成本高，另外，多個(gè)寫操作之間是互斥的，同一時(shí)刻只允許一個(gè)寫操作。圖2-10寫時(shí)復(fù)制的B+樹3.多版本并發(fā)控制除了寫時(shí)復(fù)制技術(shù)，多版本并發(fā)控制，即MVCC（Multi-VersionConcurrencyControl），也能夠?qū)崿F(xiàn)讀事務(wù)不加鎖。MVCC對(duì)每行數(shù)據(jù)維護(hù)多個(gè)版本，無(wú)論事務(wù)的執(zhí)行時(shí)間有多長(zhǎng)，MVCC總是能夠提供與事務(wù)開始時(shí)刻相一致的數(shù)據(jù)。以MySQLInnoDB存儲(chǔ)引擎為例，InnoDB對(duì)每一行維護(hù)了兩個(gè)隱含的列，其中一列存儲(chǔ)行被修改的“時(shí)間”，另外一列存儲(chǔ)行被刪除的“時(shí)間”，注意，InnoDB存儲(chǔ)的并不是絕對(duì)時(shí)間，而是與時(shí)間對(duì)應(yīng)的數(shù)據(jù)庫(kù)系統(tǒng)的版本號(hào)，每當(dāng)一個(gè)事務(wù)開始時(shí)，InnoDB都會(huì)給這個(gè)事務(wù)分配一個(gè)遞增的版本號(hào)，所以版本號(hào)也可以被認(rèn)為是事務(wù)號(hào)。對(duì)于每一行查詢語(yǔ)句，InnoDB都會(huì)把這個(gè)查詢語(yǔ)句的版本號(hào)同這個(gè)查詢語(yǔ)句遇到的行的版本號(hào)進(jìn)行對(duì)比，然后結(jié)合不同的事務(wù)隔離級(jí)別，來(lái)決定是否返回改行。下面分別以SELECT、DELETE、INSERT、UPDATE語(yǔ)句來(lái)說(shuō)明。（1）SELECT對(duì)于SELECT語(yǔ)句，只有同時(shí)滿足了下面兩個(gè)條件的行，才能被返回：a）行的修改版本號(hào)小于等于該事務(wù)號(hào)。b）行的刪除版本號(hào)要么沒有被定義，要么大于事務(wù)的版本號(hào)。如果行的修改或者刪除版本號(hào)大于事務(wù)號(hào)，說(shuō)明行是被該事務(wù)后面啟動(dòng)的事務(wù)修改或者刪除的。在可重復(fù)讀取隔離級(jí)別下，后開始的事務(wù)對(duì)數(shù)據(jù)的影響不應(yīng)該被先開始的事務(wù)看見，所以應(yīng)該忽略后開始的事務(wù)的更新或者刪除操作。（2）INSERT對(duì)新插入的行，行的修改版本號(hào)更新為該事務(wù)的事務(wù)號(hào)。（3）DELETE對(duì)于刪除，InnoDB直接把該行的刪除版本號(hào)設(shè)置為當(dāng)前的事務(wù)號(hào)，相當(dāng)于標(biāo)記為刪除，而不是物理刪除。（4）UPDATE在更新行的時(shí)候，InnoDB會(huì)把原來(lái)的行復(fù)制一份，并把當(dāng)前的事務(wù)號(hào)作為該行的修改版本號(hào)。MVCC讀取數(shù)據(jù)的時(shí)候不用加鎖，每個(gè)查詢都通過(guò)版本檢查，只獲得自己需要的數(shù)據(jù)版本，從而大大提高了系統(tǒng)的并發(fā)度。當(dāng)然，為了實(shí)現(xiàn)多版本，必須對(duì)每行存儲(chǔ)額外的多個(gè)版本的數(shù)據(jù)。另外，MVCC存儲(chǔ)引擎還必須定期刪除不再需要的版本，及時(shí)回收空間。2.5故障恢復(fù)數(shù)據(jù)庫(kù)運(yùn)行過(guò)程中可能會(huì)發(fā)生故障，這個(gè)時(shí)候某些事務(wù)可能執(zhí)行到一半但沒有提交，當(dāng)系統(tǒng)重啟時(shí)，需要能夠恢復(fù)到一致的狀態(tài)，即要么提交整個(gè)事務(wù)，要么回滾。數(shù)據(jù)庫(kù)系統(tǒng)以及其他的分布式存儲(chǔ)系統(tǒng)一般采用操作日志（有時(shí)也稱為提交日志，即CommitLog）技術(shù)來(lái)實(shí)現(xiàn)故障恢復(fù)。操作日志分為回滾日志（UNDOLog）、重做日志（REDOLog）以及UNDO/REDO日志。如果記錄事務(wù)修改前的狀態(tài)，則為回滾日志；相應(yīng)地，如果記錄事務(wù)修改后的狀態(tài)，則為重做日志。本節(jié)介紹操作日志及故障恢復(fù)基礎(chǔ)知識(shí)。2.5.1操作日志為了保證數(shù)據(jù)庫(kù)的一致性，數(shù)據(jù)庫(kù)操作需要持久化到磁盤，如果每次操作都隨機(jī)更新磁盤的某個(gè)數(shù)據(jù)塊，系統(tǒng)性能將會(huì)很差。因此，通過(guò)操作日志順序記錄每個(gè)數(shù)據(jù)庫(kù)操作并在內(nèi)存中執(zhí)行這些操作，內(nèi)存中的數(shù)據(jù)定期刷新到磁盤，實(shí)現(xiàn)將隨機(jī)寫請(qǐng)求轉(zhuǎn)化為順序?qū)懻?qǐng)求。操作日志記錄了事務(wù)的操作。例如，事務(wù)T對(duì)表格中的X執(zhí)行加10操作，初始時(shí)X=5，更新后X=15，那么，UNDO日志記為＜T,X，5＞，REDO日志記為＜T,X，15＞，UNDO/REDO日志記為＜T,X，5，15＞。關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)一般采用UNDO/REDO日志，相關(guān)技術(shù)可以參考數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)方面的資料?？梢詫㈥P(guān)系數(shù)據(jù)庫(kù)存儲(chǔ)模型做一定程度的簡(jiǎn)化：1）假設(shè)內(nèi)存足夠大，每次事務(wù)的修改操作都可以緩存在內(nèi)存中。2）數(shù)據(jù)庫(kù)的每個(gè)事務(wù)只包含一個(gè)操作，即每個(gè)事務(wù)都必須立即提交（AutoCommit）。REDO日志要求我們將所有未提交事務(wù)修改的數(shù)據(jù)塊保留在內(nèi)存中。簡(jiǎn)化后的存儲(chǔ)模型可以采用單一的REDO日志，大大簡(jiǎn)化了存儲(chǔ)系統(tǒng)故障恢復(fù)。2.5.2重做日志存儲(chǔ)系統(tǒng)如果采用REDO日志，其寫操作流程如下：1）將REDO日志以追加寫的方式寫入磁盤的日志文件。2）將REDO日志的修改操作應(yīng)用到內(nèi)存中。3）返回操作成功或者失敗。REDO日志的約束規(guī)則為：在修改內(nèi)存中的元素X之前，要確保與這一修改相關(guān)的操作日志必須先刷入到磁盤中。顧名思義，用REDO日志進(jìn)行故障恢復(fù)，只需要從頭到尾讀取日志文件中的修改操作，并將它們逐個(gè)應(yīng)用到內(nèi)存中，即重做一遍。為什么需要先寫操作日志再修改內(nèi)存中的數(shù)據(jù)呢？假如先修改內(nèi)存中的數(shù)據(jù)，那么用戶就能立刻讀到修改后的結(jié)果，一旦在完成內(nèi)存修改與寫入日志之間發(fā)生故障，那么最近的修改操作無(wú)法恢復(fù)。然而，之前的用戶可能已經(jīng)讀取了修改后的結(jié)果，這就會(huì)產(chǎn)生不一致的情況。2.5.3優(yōu)化手段1.成組提交存儲(chǔ)系統(tǒng)要求先將REDO日志刷入磁盤才可以更新內(nèi)存中的數(shù)據(jù)，如果每個(gè)事務(wù)都要求將日志立即刷入磁盤，系統(tǒng)的吞吐量將會(huì)很差。因此，存儲(chǔ)系統(tǒng)往往有一個(gè)是否立即刷入磁盤的選項(xiàng)，對(duì)于一致性要求很高的應(yīng)用，可以設(shè)置為立即刷入；相應(yīng)地，對(duì)于一致性要求不太高的應(yīng)用，可以設(shè)置為不要求立即刷入，首先將REDO日志緩存到操作系統(tǒng)或者存儲(chǔ)系統(tǒng)的內(nèi)存緩沖區(qū)中，定期刷入磁盤。這種做法有一個(gè)問題，如果存儲(chǔ)系統(tǒng)意外故障，可能丟失最后一部分更新操作。成組提交（GroupCommit）技術(shù)是一種有效的優(yōu)化手段。REDO日志首先寫入到存儲(chǔ)系統(tǒng)的日志緩沖區(qū)中：a）日志緩沖區(qū)中的數(shù)據(jù)量超過(guò)一定大小，比如512KB；b）距離上次刷入磁盤超過(guò)一定時(shí)間，比如10ms。當(dāng)滿足以上兩個(gè)條件中的某一個(gè)時(shí)，將日志緩沖區(qū)中的多個(gè)事務(wù)操作一次性刷入磁盤，接著一次性將多個(gè)事務(wù)的修改操作應(yīng)用到內(nèi)存中并逐個(gè)返回客戶端操作結(jié)果。與定期刷入磁盤不同的是，成組提交技術(shù)保證REDO日志成功刷入磁盤后才返回寫操作成功。這種做法可能會(huì)犧牲寫事務(wù)的延時(shí)，但大大提高了系統(tǒng)的吞吐量。2.檢查點(diǎn)如果所有的數(shù)據(jù)都保存在內(nèi)存中，那么可能出現(xiàn)兩個(gè)問題：●故障恢復(fù)時(shí)需要回放所有的REDO日志，效率較低。如果REDO日志較多，比如超過(guò)100GB，那么，故障恢復(fù)時(shí)間是無(wú)法接受的?！駜?nèi)存不足。即使內(nèi)存足夠大，存儲(chǔ)系統(tǒng)往往也只能夠緩存最近較長(zhǎng)一段時(shí)間的更新操作，很難緩存所有的數(shù)據(jù)。因此，需要將內(nèi)存中的數(shù)據(jù)定期轉(zhuǎn)儲(chǔ)（Dump）到磁盤，這種技術(shù)稱為checkpoint（檢查點(diǎn)）技術(shù)。系統(tǒng)定期將內(nèi)存中的操作以某種易于加載的形式（checkpoint文件）轉(zhuǎn)儲(chǔ)到磁盤中，并記錄checkpoint時(shí)刻的日志回放點(diǎn)，以后故障恢復(fù)只需要回放checkpoint時(shí)刻的日志回放點(diǎn)之后的REDO日志。由于將內(nèi)存數(shù)據(jù)轉(zhuǎn)儲(chǔ)到磁盤需要很長(zhǎng)的時(shí)間，而這段時(shí)間還可能有新的更新操作，checkpoint必須找到一個(gè)一致的狀態(tài)。checkpoint流程如下：1）日志文件中記錄“STARTCKPT”。2）將內(nèi)存中的數(shù)據(jù)以某種易于加載的組織方式轉(zhuǎn)儲(chǔ)到磁盤中，形成checkpoint文件。checkpoint文件中往往記錄“STARTCKPT”的日志回放點(diǎn)，用于故障恢復(fù)。3）日志文件中記錄“ENDCKPT”。故障恢復(fù)流程如下：1）將checkpoint文件加載到內(nèi)存中，這一步操作往往只需要加載索引數(shù)據(jù)，加載效率很高。2）讀取checkpoint文件中記錄的“STARTCKPT”日志回放點(diǎn)，回放之后的REDO日志。上述checkpoint故障恢復(fù)方式依賴REDO日志中記錄的都是修改后的結(jié)果這一特性，也就是說(shuō)，即使checkpoint文件中已經(jīng)包含了某些操作的結(jié)果，重新回放一次或者多次這些操作的REDO日志也不會(huì)造成數(shù)據(jù)錯(cuò)誤。如果同一個(gè)操作執(zhí)行一次與重復(fù)執(zhí)行多次的效果相同，這種操作具有“冪等性”。有些操作不具備這種特性，例如，加法操作、追加操作。如果REDO日志記錄的是這種操作，那么checkpoint文件中的數(shù)據(jù)一定不能包含“STARTCKPT”與“ENDCKPT”之間的操作。為此，主要有兩種處理方法：●checkpoint過(guò)程中停止寫服務(wù)，所有的修改操作直接失敗。這種方法實(shí)現(xiàn)簡(jiǎn)單，但不適合在線業(yè)務(wù)。●內(nèi)存數(shù)據(jù)結(jié)構(gòu)支持快照。執(zhí)行checkpoint操作時(shí)首先對(duì)內(nèi)存數(shù)據(jù)結(jié)構(gòu)做一次快照，接著將快照中的數(shù)據(jù)轉(zhuǎn)儲(chǔ)到磁盤生成checkpoint文件，并記錄此時(shí)對(duì)應(yīng)的REDO日志回放點(diǎn)。生成checkpoint文件的過(guò)程中允許寫操作，但checkpoint文件中的快照數(shù)據(jù)不會(huì)包含這些操作的結(jié)果。2.6數(shù)據(jù)壓縮數(shù)據(jù)壓縮分為有損壓縮與無(wú)損壓縮兩種，有損壓縮算法壓縮比率高，但數(shù)據(jù)可能失真，一般用于壓縮圖片、音頻、視頻；而無(wú)損壓縮算法能夠完全還原原始數(shù)據(jù)，本文只討論無(wú)損壓縮算法。早期的數(shù)據(jù)壓縮技術(shù)就是基于編碼上的優(yōu)化技術(shù)，其中以Huffman編碼最為知名，它通過(guò)統(tǒng)計(jì)字符出現(xiàn)的頻率計(jì)算最優(yōu)前綴編碼。1977年，以色列人JacobZiv和AbrahamLempel發(fā)表論文《順序數(shù)據(jù)壓縮的一個(gè)通用算法》，從此，LZ系列壓縮算法幾乎壟斷了通用無(wú)損壓縮領(lǐng)域，常用的Gzip算法中使用的LZ77，GIF圖片格式中使用的LZW，以及LZO等壓縮算法都屬于這個(gè)系列。設(shè)計(jì)壓縮算法時(shí)不僅要考慮壓縮比，還要考慮壓縮算法的執(zhí)行效率。GoogleBigtable系統(tǒng)中采用BMDiff和Zippy壓縮算法，這兩個(gè)算法也是LZ算法的變種，它們通過(guò)犧牲一定的壓縮比，換來(lái)執(zhí)行效率的大幅提升。壓縮算法的核心是找重復(fù)數(shù)據(jù)，列式存儲(chǔ)技術(shù)通過(guò)把相同列的數(shù)據(jù)組織在一起，不僅減少了大數(shù)據(jù)分析需要查詢的數(shù)據(jù)量，還大大地提高了數(shù)據(jù)的壓縮比。傳統(tǒng)的OLAP（OnlineAnalyticalProcessing）數(shù)據(jù)庫(kù)，如SybaseIQ、Teradata，以及Bigtable、HBase等分布式表格系統(tǒng)都實(shí)現(xiàn)了列式存儲(chǔ)。本節(jié)介紹數(shù)據(jù)壓縮以及列式存儲(chǔ)相關(guān)的基礎(chǔ)知識(shí)。2.6.1壓縮算法壓縮是一個(gè)專門的研究課題，沒有通用的做法，需要根據(jù)數(shù)據(jù)的特點(diǎn)選擇或者自己開發(fā)合適的算法。壓縮的本質(zhì)就是找數(shù)據(jù)的重復(fù)或者規(guī)律，用盡量少的字節(jié)表示。Huffman編碼是一種基于編碼的優(yōu)化技術(shù)，通過(guò)統(tǒng)計(jì)字符出現(xiàn)的頻率來(lái)計(jì)算最優(yōu)前綴編碼。LZ系列算法一般有一個(gè)窗口的概念，在窗口內(nèi)部找重復(fù)并維護(hù)數(shù)據(jù)字典。常用的壓縮算法包括Gzip、LZW、LZO，這些算法都借鑒或改進(jìn)了原始的LZ77算法，如Gzip壓縮混合使用了LZ77以及Huffman編碼，LZW以及LZO算法是LZ77思想在實(shí)現(xiàn)手段的進(jìn)一步優(yōu)化。存儲(chǔ)系統(tǒng)在選擇壓縮算法時(shí)需要考慮壓縮比和效率。讀操作需要先讀取磁盤中的內(nèi)容再解壓縮，寫操作需要先壓縮再將壓縮結(jié)果寫入到磁盤，整個(gè)操作的延時(shí)包括壓縮/解壓縮和磁盤讀寫的延遲，壓縮比越大，磁盤讀寫的數(shù)據(jù)量越小，而壓縮/解壓縮的時(shí)間也會(huì)越長(zhǎng)，所以這里需要一個(gè)很好的權(quán)衡點(diǎn)。GoogleBigtable系統(tǒng)中使用了BMDiff以及Zippy兩種壓縮算法，它們通過(guò)犧牲一定的壓縮比換取算法執(zhí)行速度的大幅提升，從而獲得更好的折衷。1.Huffman編碼前綴編碼要求一個(gè)字符的編碼不能是另一個(gè)字符的前綴。假設(shè)有三個(gè)字符A、B、C，它們的二進(jìn)制編碼分別是0、1、01，如果我們收到一段信息是01010，解碼時(shí)我們?nèi)绾螀^(qū)分是CCA還是ABABA，或者ABCA呢？一種解決方案就是前綴編碼，要求一個(gè)字符編碼不能是另外一個(gè)字符編碼的前綴。如果使用前綴編碼將A、B、C編碼為：A：0B：10C：110這樣，01010就只能被翻譯成ABB。Huffman編碼需要解決的問題是，如何找出一種前綴編碼方式，使得編碼的長(zhǎng)度最短。假設(shè)有一個(gè)字符串3334444555556666667777777，它是由3個(gè)3，4個(gè)4，5個(gè)5，6個(gè)6，7個(gè)7組成的。那么，對(duì)應(yīng)的前綴編碼可能是：1）3:0004:0015:0106:0117:12）3:0004:0017:015:106:11第1種編碼方式的權(quán)值為（3+4+5+6）*3+7*1=61，而第2種編碼方式的權(quán)值為（3+4）*3+（5+6+7）*2=57。可以看出，第2種編碼方式的長(zhǎng)度更短，而且我們還可以知道，第2種編碼方式是最優(yōu)的Huffman編碼。Huffman編碼的構(gòu)造過(guò)程不在本書討論范圍之內(nèi)，感興趣的讀者可以參考數(shù)據(jù)結(jié)構(gòu)的相關(guān)圖書。2.LZ系列壓縮算法LZ系列壓縮算法是基于字典的壓縮算法。假設(shè)需要壓縮一篇英文文章，最容易想到的壓縮算法是構(gòu)造一本英文字典，這樣，我們只需要保存每個(gè)單詞在字典中出現(xiàn)的頁(yè)碼和位置就可以了。頁(yè)碼用兩個(gè)字節(jié)，位置用一個(gè)字節(jié)，那么一個(gè)單詞需要使用三個(gè)字節(jié)表示，而我們知道一般的英語(yǔ)單詞長(zhǎng)度都在三個(gè)字節(jié)以上。因此，我們實(shí)現(xiàn)了對(duì)這篇英文文章的壓縮。當(dāng)然，實(shí)際的通用壓縮算法不能這么做，因?yàn)槲覀冊(cè)诮鈮簳r(shí)需要一本英文字典，而這部分信息是壓縮程序不可預(yù)知的，同時(shí)也不能保存在壓縮信息里面。LZ系列的算法是一種動(dòng)態(tài)創(chuàng)建字典的方法，壓縮過(guò)程中動(dòng)態(tài)創(chuàng)建字典并保存在壓縮信息里面。LZ77是第一個(gè)LZ系列的算法，比如字符串ABCABCDABC中ABC重復(fù)出現(xiàn)了三次，壓縮信息中只需要保存第一個(gè)ABC，后面兩個(gè)ABC只需要把第一個(gè)出現(xiàn)ABC的位置和長(zhǎng)度存儲(chǔ)下來(lái)就可以了。這樣，保存后面兩個(gè)ABC就只需要一個(gè)二元數(shù)組＜匹配串的相對(duì)位置，匹配長(zhǎng)度＞。解壓的時(shí)候，根據(jù)匹配串的相對(duì)位置，向前找到第一個(gè)ABC的位置，然后根據(jù)匹配的長(zhǎng)度，直接把第一個(gè)ABC復(fù)制到當(dāng)前解壓緩沖區(qū)里面就可以了。如表2-7所示，{S}*表示字符串S的所有子串構(gòu)成的集合，例如，{ABC}*是字符串A、B、C、AB、BC、ABC構(gòu)成的集合。每一步執(zhí)行時(shí)如果能夠在壓縮字典中找到匹配串，則輸出匹配信息；否則，輸出源信息。執(zhí)行第1步時(shí)，壓縮字典為空，輸出字符‘A’，并將‘A’加入到壓縮字典；執(zhí)行第2步時(shí)，壓縮字典為{A}*，輸出字符‘B’，并將‘B’加入到壓縮字典；依次類推。執(zhí)行到第4步和第6步時(shí)發(fā)現(xiàn)字符ABC之前已經(jīng)出現(xiàn)過(guò)，輸出匹配的位置和長(zhǎng)度。LZ系列壓縮算法有如下幾個(gè)問題：1）如何區(qū)分匹配信息和源信息？通用的解決方法是額外使用一個(gè)位（bit）來(lái)區(qū)分壓縮信息里面的源信息和匹配信息。2）需要使用多少個(gè)字節(jié)表示匹配信息？記錄重復(fù)信息的匹配信息包含兩項(xiàng)，一個(gè)是匹配串的相對(duì)位置，另一個(gè)是匹配的長(zhǎng)度。例如，可以采用固定的兩個(gè)字節(jié)來(lái)表示匹配信息，其中，1位用來(lái)區(qū)分源信息和匹配信息，11位表示匹配位置，4位表示匹配長(zhǎng)度。這樣，壓縮算法支持的最大數(shù)據(jù)窗口為211=2048字節(jié)，支持重復(fù)串的最大長(zhǎng)度為24=16字節(jié)。當(dāng)然，也可以采用變長(zhǎng)的方式表示匹配信息。3）如何快速查找最長(zhǎng)匹配串？最容易想到的做法是把字符串的所有子串都存放到一張哈希表中，表2-7中第4步執(zhí)行前哈希表中包含ABC的所有子串，即A、AB、BC、ABC。這種做法的運(yùn)行效率很低，實(shí)際的做法往往會(huì)做一些改進(jìn)。例如，哈希表中只保存所有長(zhǎng)度為3的子串，如果在數(shù)據(jù)字典中找到匹配串，即前3個(gè)字節(jié)相同，接著再往后順序遍歷找出最長(zhǎng)匹配。3.BMDiff與Zippy在Google的Bigtable系統(tǒng)中，設(shè)計(jì)了BMDiff和Zippy兩種壓縮算法。BMDiff和Zippy（也稱為Snappy）也屬于LZ系列，相比傳統(tǒng)的LZW或者Gzip，這兩種算法的壓縮比不算高，但是處理速度非常快。如表2-8所示，Zippy和BMDiff的壓縮/解壓縮速度是Gzip算法的5～10倍。相比原始的LZ77，Zippy實(shí)現(xiàn)時(shí)主要做了如下改進(jìn)：1）壓縮字典中只保存所有長(zhǎng)度為4的子串，只有重復(fù)匹配的長(zhǎng)度大于等于4，才輸出匹配信息；否則，輸出源信息。另外，Zippy算法中的壓縮字典只保存最后一個(gè)長(zhǎng)度等于4的子串的位置，以ABCDEABCDABCDE為例，Zippy算法的過(guò)程參見表2-9。Zippy算法執(zhí)行完第4步后，發(fā)現(xiàn)“ABCD”出現(xiàn)過(guò)，于是在壓縮字典中記錄“ABCD”第一次出現(xiàn)的位置，即位置0。執(zhí)行到第6步時(shí)發(fā)現(xiàn)ABCD之前出現(xiàn)過(guò)，輸出匹配信息，同時(shí)將數(shù)據(jù)字典中記錄的ABCD的位置更新為第二個(gè)ABCD的位置，即位置5；執(zhí)行到第7步時(shí)，雖然ABCDE之前都出現(xiàn)過(guò)，但由于數(shù)據(jù)字典中記錄的是第二個(gè)ABCD的位置，因此，重復(fù)串為ABCD，而不是理想的ABCDE。Zippy的這種實(shí)現(xiàn)方式犧牲了壓縮比，但是提升了性能。2）Zippy內(nèi)部將數(shù)據(jù)劃分為一個(gè)一個(gè)長(zhǎng)度為32KB的數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊分別壓縮，多個(gè)數(shù)據(jù)塊之間沒有聯(lián)系，因此，只需要兩個(gè)字節(jié)（確切地說(shuō)，15個(gè)位）就可以表示匹配串的相對(duì)位置。另外，Zippy內(nèi)部還對(duì)匹配信息的表示進(jìn)行了精心的設(shè)計(jì)，采用變長(zhǎng)的表示方法。如果匹配長(zhǎng)度小于12個(gè)字節(jié)（由于前面4個(gè)字節(jié)總是相同，所以4＜=匹配長(zhǎng)度＜12，可以通過(guò)3個(gè)位來(lái)表示）且匹配位置小于2048，則使用兩個(gè)字節(jié)表示；否則，使用更多的字節(jié)表示。總而言之，Zippy對(duì)匹配信息的編碼和實(shí)現(xiàn)都非常精妙，感興趣的讀者可以閱讀開源的Snappy項(xiàng)目的源代碼。相比Zippy,BMDiff算法實(shí)現(xiàn)顯得更為激進(jìn)。BMDiff算法將待壓縮數(shù)據(jù)拆分為長(zhǎng)度為b（默認(rèn)情況下b=32）的小段0……b-1，b……2b-1，2b……3b-1，以此類推。BMDiff的字典中保存了每個(gè)小段的哈希值，因此，長(zhǎng)度為N的字符串需要的哈希表大小為N/b。與Zippy算法不同的是，BMDiff算法并沒有保存每個(gè)長(zhǎng)度為b的子串的哈希值，這種方式帶來(lái)的問題是，某些重復(fù)長(zhǎng)度超過(guò)b的子串可能無(wú)法被壓縮。例如，待壓縮字符串為EABCDABCD,b=4，字典中保存了EABC和DABC兩個(gè)子串，雖然ABCD重復(fù)出現(xiàn)了兩次，但無(wú)法被壓縮。然而，可以證明，只要重復(fù)長(zhǎng)度超過(guò)2b-1，