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

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