單機(jī)存儲引擎就是哈希表幅聘、B樹等數(shù)據(jù)結(jié)構(gòu)在機(jī)械磁盤凡纳、SSD等持久化介質(zhì)上的實現(xiàn)。
單機(jī)存儲系統(tǒng)是單機(jī)存儲引擎的一種封裝帝蒿，對外提供文件荐糜、鍵值、表格或者關(guān)系模型葛超。

硬件基礎(chǔ)

CPU架構(gòu)

早期的CPU為單核芯片暴氏，工程師們很快意識到，僅僅提高單核的速度會產(chǎn)生過多的熱量且無法帶來相應(yīng)的性能改善巩掺。因此偏序，現(xiàn)代服務(wù)器基本為多核或多個CPU。經(jīng)典的多CPU架構(gòu)為對稱多處理結(jié)構(gòu)（Symmetric Multi-Processing,SMP）胖替，即在一個計算機(jī)上匯集了一組處理器研儒，它們之間對稱工作，無主次或從屬關(guān)系独令，共享相同的物理內(nèi)存及總線端朵，如圖所示。

圖上SMP系統(tǒng)由兩個CPU組成燃箭，每個CPU有兩個核心（core）冲呢，CPU與內(nèi)存之間通過總線通信。每個核心有各自的L1d Cache（L1數(shù)據(jù)緩存）及L1i Cache（L1指令緩存）招狸，同一個CPU的多個核心共享L2以及L3緩存敬拓，另外，某些CPU還可以通過超線程技術(shù)（Hyper-Threading Technology）使得一個核心具有同時執(zhí)行兩個線程的能力裙戏。

SMP架構(gòu)的主要特征是共享乘凸，系統(tǒng)中所有資源（CPU、內(nèi)存累榜、I/O等）都是共享的营勤，由于多CPU對前端總線的競爭，SMP的擴(kuò)展能力非常有限壹罚。為了提高可擴(kuò)展性葛作，現(xiàn)在的主流服務(wù)器架構(gòu)一般為NUMA（Non-Uniform Memory Access，非一致存儲訪問）架構(gòu)猖凛。它具有多個NUMA節(jié)點赂蠢，每個NUMA節(jié)點是一個SMP結(jié)構(gòu)，一般由多個CPU（如4個）組成形病，并且具有獨立的本地內(nèi)存客年、IO槽口等霞幅。

下圖為包含4個NUMA節(jié)點的服務(wù)器架構(gòu)圖，NUMA節(jié)點可以直接快速訪問本地內(nèi)存量瓜，也可以通過NUMA互聯(lián)互通模塊訪問其他NUMA節(jié)點的內(nèi)存司恳，訪問本地內(nèi)存的速度遠(yuǎn)遠(yuǎn)高于遠(yuǎn)程訪問的速度。由于這個特點绍傲，為了更好地發(fā)揮系統(tǒng)性能扔傅，開發(fā)應(yīng)用程序時需要盡量減少不同NUMA節(jié)點之間的信息交互。

IO總線

存儲系統(tǒng)的性能瓶頸一般在于IO烫饼，因此猎塞，有必要對IO子系統(tǒng)的架構(gòu)有一個大致的了解。以Intel x48主板為例杠纵，它是典型的南荠耽、北橋架構(gòu)，如圖所示比藻。北橋芯片通過前端總線（Front Side Bus,FSB）與CPU相連铝量，內(nèi)存模塊以及PCI-E設(shè)備（如高端的SSD設(shè)備Fusion-IO）掛接在北橋上。北橋與南橋之間通過DMI連接银亲，DMI的帶寬為1GB/s慢叨，網(wǎng)卡（包括千兆以及萬兆網(wǎng)卡），硬盤以及中低端固態(tài)盤（如Intel 320系列SSD）掛接在南橋上务蝠。如果采用SATAZ接口拍谐，那么最大帶寬為300MB/s。

網(wǎng)絡(luò)拓?fù)?br>

圖2-4為傳統(tǒng)的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)淞蠖危伎七^去一直提倡這樣的拓?fù)湫Γ譃槿龑樱钕旅媸墙尤雽樱‥dge）院喜，中間是匯聚層（Aggregation）气嫁，上面是核心層（Core）。典型的接入層交換機(jī)包含48個1Gb端口以及4個10Gb上行端口够坐，匯聚層以及核心層的交換機(jī)包含128個10Gb的端口。傳統(tǒng)三層結(jié)構(gòu)的問題在于可能有很多接入層的交換機(jī)接到匯聚層崖面，很多的匯聚層交換機(jī)接到核心層元咙。同一個接入層下的服務(wù)器之間帶寬為1Gb，不同接入層交換機(jī)下的服務(wù)器之間的帶寬小于1Gb巫员。由于同一個接入層的服務(wù)器往往部署在一個機(jī)架內(nèi)庶香，因此，設(shè)計系統(tǒng)的時候需要考慮服務(wù)器是否在一個機(jī)架內(nèi)简识，減少跨機(jī)架拷貝大量數(shù)據(jù)赶掖。例如感猛，Hadoop HDFS默認(rèn)存儲三個副本，其中兩個副本放在同一個機(jī)架奢赂，就是這個原因陪白。

為了減少系統(tǒng)對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的依賴，Google在2008年的時候?qū)⒕W(wǎng)絡(luò)改造為扁平化拓?fù)浣Y(jié)構(gòu)膳灶，即三級CLOS網(wǎng)絡(luò)咱士，同一個集群內(nèi)最多支持20480臺服務(wù)器，且任何兩臺都有1Gb帶寬轧钓。CLOS網(wǎng)絡(luò)需要額外投入更多的交換機(jī)序厉，帶來的好處也是明顯的，設(shè)計系統(tǒng)時不需要考慮底層網(wǎng)絡(luò)拓?fù)浔瞎浚瑥亩芊奖愕貙⒄麄€集群做成一個計算資源池弛房。

同一個數(shù)據(jù)中心內(nèi)部的傳輸延時是比較小的，網(wǎng)絡(luò)一次來回的時間在1毫秒之內(nèi)而柑。數(shù)據(jù)中心之間的傳輸延遲是很大的文捶，取決于光在光纖中的傳輸時間。例如牺堰，北京與杭州之間的直線距離大約為1300公里拄轻，光在信息傳輸中走折線，假設(shè)折線距離為直線距離的1.5倍伟葫，那么光傳輸一次網(wǎng)絡(luò)來回延時的理論值為1300×1.5×2/300000=13毫秒恨搓，實際測試值大約為40毫秒。

性能參數(shù)

磁盤讀寫帶寬還是不錯的筏养，15000轉(zhuǎn)的SATA盤的順序讀取帶寬可以達(dá)到100MB以上斧抱，由于磁盤尋道的時間大約為10ms，順序讀取1MB數(shù)據(jù)的時間為：磁盤尋道時間+數(shù)據(jù)讀取時間渐溶，即10ms+1MB/100MB/s×1000=20ms辉浦。存儲系統(tǒng)的性能瓶頸主要在于磁盤隨機(jī)讀寫。設(shè)計存儲引擎的時候會針對磁盤的特性做很多的處理茎辐，比如將隨機(jī)寫操作轉(zhuǎn)化為順序?qū)懴芙迹ㄟ^緩存減少磁盤隨機(jī)讀操作。

固態(tài)磁盤（SSD）在最近幾年得到越來越多的關(guān)注拖陆，各大互聯(lián)網(wǎng)公司都有大量基于SSD的應(yīng)用弛槐。SSD的特點是隨機(jī)讀取延遲小，能夠提供很高的IOPS（每秒讀寫依啰，Input/Output Per Second）性能乎串。它的主要問題在于容量和價格，設(shè)計存儲系統(tǒng)的時候一般可以用來做緩存或者性能要求較高的關(guān)鍵業(yè)務(wù)速警。

存儲層次架構(gòu)

從分布式系統(tǒng)的角度看叹誉，整個集群中所有服務(wù)器上的存儲介質(zhì)（內(nèi)存鸯两、機(jī)械硬盤，SSD）構(gòu)成一個整體长豁，其他服務(wù)器上的存儲介質(zhì)與本機(jī)存儲介質(zhì)一樣都是可訪問的钧唐，區(qū)別僅僅在于需要額外的網(wǎng)絡(luò)傳輸及網(wǎng)絡(luò)協(xié)議棧等訪問開銷。

存儲系統(tǒng)的性能主要包括兩個維度：吞吐量以及訪問延時蕉斜，設(shè)計系統(tǒng)時要求能夠在保證訪問延時的基礎(chǔ)上逾柿，通過最低的成本實現(xiàn)盡可能高的吞吐量。磁盤和SSD的訪問延時差別很大宅此，但帶寬差別不大机错，因此，磁盤適合大塊順序訪問的存儲系統(tǒng)父腕，SSD適合隨機(jī)訪問較多或者對延時比較敏感的關(guān)鍵系統(tǒng)弱匪。二者也常常組合在一起進(jìn)行混合存儲，熱數(shù)據(jù)（訪問頻繁）存儲到SSD中璧亮，冷數(shù)據(jù)（訪問不頻繁）存儲到磁盤中萧诫。

單機(jī)存儲引擎

存儲引擎是存儲系統(tǒng)的發(fā)動機(jī)，直接決定了存儲系統(tǒng)能夠提供的性能和功能枝嘶。存儲系統(tǒng)的基本功能包括：增帘饶、刪、讀群扶、改及刻，其中崇堰，讀取操作又分為隨機(jī)讀取和順序掃描徙融。

哈希存儲引擎是哈希表的持久化實現(xiàn)便锨，支持增笤昨、刪、改旧困，以及隨機(jī)讀取操作寨蹋，但不支持順序掃描蹄胰，對應(yīng)的存儲系統(tǒng)為鍵值（Key-Value）存儲系統(tǒng)幕垦；

B樹（B-Tree）存儲引擎是B樹的持久化實現(xiàn)丢氢，不僅支持單條記錄的增、刪先改、讀卖丸、改操作，還支持順序掃描盏道，對應(yīng)的存儲系統(tǒng)是關(guān)系數(shù)據(jù)庫。當(dāng)然载碌，鍵值系統(tǒng)也可以通過B樹存儲引擎實現(xiàn)猜嘱；

LSM樹（Log-Structured Merge Tree）存儲引擎和B樹存儲引擎一樣衅枫，支持增、刪朗伶、改弦撩、隨機(jī)讀取以及順序掃描。它通過批量轉(zhuǎn)儲技術(shù)規(guī)避磁盤隨機(jī)寫入問題论皆，廣泛應(yīng)用于互聯(lián)網(wǎng)的后臺存儲系統(tǒng)益楼，例如Google Bigtable、Google LevelDB以及Facebook開源的Cassandra系統(tǒng)点晴。

數(shù)據(jù)模型

如果說存儲引擎相當(dāng)于存儲系統(tǒng)的發(fā)動機(jī)感凤，那么，數(shù)據(jù)模型就是存儲系統(tǒng)的外殼粒督。存儲系統(tǒng)的數(shù)據(jù)模型主要包括三類：文件陪竿、關(guān)系以及隨著NoSQL技術(shù)流行起來的鍵值模型。傳統(tǒng)的文件系統(tǒng)和關(guān)系數(shù)據(jù)庫系統(tǒng)分別采用文件和關(guān)系模型屠橄。關(guān)系模型描述能力強(qiáng)族跛，產(chǎn)業(yè)鏈完整，是存儲系統(tǒng)的業(yè)界標(biāo)準(zhǔn)锐墙。然而礁哄，隨著應(yīng)用在可擴(kuò)展性、高并發(fā)以及性能上提出越來越高的要求溪北，大而全的關(guān)系數(shù)據(jù)庫有時顯得力不從心桐绒，因此，產(chǎn)生了一些新的數(shù)據(jù)模型刻盐，比如鍵值模型掏膏，關(guān)系弱化的表格模型，等等敦锌。

文件模型

文件系統(tǒng)以目錄樹的形式組織文件馒疹，以類UNIX操作系統(tǒng)為例，根目錄為/乙墙，包含/usr颖变、/bin、/home等子目錄听想，每個子目錄又包含其他子目錄或者文件腥刹。文件系統(tǒng)的操作涉及目錄以及文件，例如汉买，打開/關(guān)閉文件衔峰、讀寫文件、遍歷目錄、設(shè)置文件屬性等垫卤。POSIX（Portable Operating System Interface）是應(yīng)用程序訪問文件系統(tǒng)的API標(biāo)準(zhǔn)威彰，它定義了文件系統(tǒng)存儲接口及操作集。POSIX主要接口如下所示穴肘。

Open/close：打開/關(guān)閉一個文件歇盼，獲取文件描述符；

Read/write：讀取一個文件或者往文件中寫入數(shù)據(jù)评抚；

Opendir/closedir：打開或者關(guān)閉一個目錄豹缀；

Readdir：遍歷目錄。

POSIX標(biāo)準(zhǔn)不僅定義了文件操作接口慨代，而且還定義了讀寫操作語義邢笙。例如，POSIX標(biāo)準(zhǔn)要求讀寫并發(fā)時能夠保證操作的原子性鱼响，即讀操作要么讀到所有結(jié)果鸣剪，要么什么也讀不到；另外丈积，要求讀操作能夠讀到之前所有寫操作的結(jié)果筐骇。POSIX標(biāo)準(zhǔn)適合單機(jī)文件系統(tǒng)，在分布式文件系統(tǒng)中江滨，出于性能考慮铛纬，一般不會完全遵守這個標(biāo)準(zhǔn)。

NFS（Network File System）文件系統(tǒng)允許客戶端緩存文件數(shù)據(jù)唬滑，多個客戶端并發(fā)修改同一個文件時可能出現(xiàn)不一致的情況告唆。舉個例子，NFS客戶端A和B需要同時修改NFS服務(wù)器的某個文件晶密，每個客戶端都在本地緩存了文件的副本擒悬，A修改后先提交，B后提交稻艰，那么懂牧，即使A和B修改的是文件的不同位置，也會出現(xiàn)B的修改覆蓋A的情況尊勿。

對象模型與文件模型比較類似僧凤，用于存儲圖片、視頻元扔、文檔等二進(jìn)制數(shù)據(jù)塊躯保，典型的系統(tǒng)包括Amazon Simple Storage（S3），Taobao File System（TFS）澎语。這些系統(tǒng)弱化了目錄樹的概念途事，Amazon S3只支持一級目錄验懊，不支持子目錄，Taobao TFS甚至不支持目錄結(jié)構(gòu)盯孙。與文件模型不同的是鲁森，對象模型要求對象一次性寫入到系統(tǒng)，只能刪除整個對象振惰，不允許修改其中某個部分。

關(guān)系模型

每個關(guān)系是一個表格垄懂，由多個元組（行）構(gòu)成骑晶，而每個元組又包含多個屬性（列）。關(guān)系名草慧、屬性名以及屬性類型稱作該關(guān)系的模式（schema）桶蛔。例如，Movie關(guān)系的模式為Movie（title,year,length）漫谷，其中仔雷，title、year舔示、length是屬性碟婆，假設(shè)它們的類型分別為字符串、整數(shù)惕稻、整數(shù)竖共。

數(shù)據(jù)庫語言SQL用于描述查詢以及修改操作。數(shù)據(jù)庫修改包含三條命令：INSERT俺祠、DELETE以及UPDATE公给，查詢通常通過select-from-where語句來表達(dá)，它具有圖2-9所示的一般形式蜘渣。Select查詢語句計算過程大致如下（不考慮查詢優(yōu)化）：

1）取FROM子句中列出的各個關(guān)系的元組的所有可能的組合淌铐。

2）將不符合WHERE子句中給出的條件的元組去掉。

3）如果有GROUP BY子句蔫缸，則將剩下的元組按GROUP BY子句中給出的屬性的值分組腿准。

4）如果有HAVING子句，則按照HAVING子句中給出的條件檢查每一個組捂龄，去掉不符合條件的組释涛。

5）按照SELECT子句的說明，對于指定的屬性和屬性上的聚集（例如求和）計算出結(jié)果元組倦沧。

6）按照ORDER BY子句中的屬性列的值對結(jié)果元組進(jìn)行排序唇撬。

SQL查詢還有一個強(qiáng)大的特性是允許在WHERE、FROM和HAVING子句中使用子查詢展融，子查詢又是一個完整的select-from-where語句窖认。

另外，SQL還包括兩個重要的特性：索引以及事務(wù)。其中扑浸，數(shù)據(jù)庫索引用于減少SQL執(zhí)行時掃描的數(shù)據(jù)量烧给，提高讀取性能；數(shù)據(jù)庫事務(wù)則規(guī)定了各個數(shù)據(jù)庫操作的語義喝噪，保證了多個操作并發(fā)執(zhí)行時的ACID特性（原子性础嫡、一致性、隔離性酝惧、持久性）榴鼎。

鍵值模型

大量的NoSQL系統(tǒng)采用了鍵值模型（也稱為Key-Value模型），每行記錄由主鍵和值兩個部分組成晚唇，支持基于主鍵的如下操作：

Put：保存一個Key-Value對巫财。

Get：讀取一個Key-Value對。

Delete：刪除一個Key-Value對哩陕。

Key-Value模型過于簡單平项，支持的應(yīng)用場景有限，NoSQL系統(tǒng)中使用比較廣泛的模型是表格模型悍及。表格模型弱化了關(guān)系模型中的多表關(guān)聯(lián)闽瓢，支持基于單表的簡單操作，典型的系統(tǒng)是Google Bigtable以及其開源Java實現(xiàn)HBase并鸵。表格模型除了支持簡單的基于主鍵的操作鸳粉，還支持范圍掃描，另外园担，也支持基于列的操作届谈。主要操作如下：

Insert：插入一行數(shù)據(jù)，每行包括若干列弯汰；

Delete：刪除一行數(shù)據(jù)艰山；

Update：更新整行或者其中的某些列的數(shù)據(jù)；

Get：讀取整行或者其中某些列數(shù)據(jù)咏闪；

Scan：掃描一段范圍的數(shù)據(jù)曙搬，根據(jù)主鍵確定掃描的范圍，支持掃描部分列鸽嫂，支持按列過濾纵装、排序、分組等据某。

與關(guān)系模型不同的是橡娄，表格模型一般不支持多表關(guān)聯(lián)操作，Bigtable這樣的系統(tǒng)也不支持二級索引癣籽，事務(wù)操作支持也比較弱挽唉，各個系統(tǒng)支持的功能差異較大滤祖，沒有統(tǒng)一的標(biāo)準(zhǔn)。另外瓶籽，表格模型往往還支持無模式（schema-less）特性匠童，也就是說，不需要預(yù)先定義每行包括哪些列以及每個列的類型塑顺，多行之間允許包含不同列汤求。

SQL與NoSQL

隨著互聯(lián)網(wǎng)的飛速發(fā)展，數(shù)據(jù)規(guī)模越來越大严拒，并發(fā)量越來越高首昔，傳統(tǒng)的關(guān)系數(shù)據(jù)庫有時顯得力不從心，非關(guān)系型數(shù)據(jù)庫（NoSQL,Not Only SQL）應(yīng)運而生糙俗。NoSQL系統(tǒng)帶來了很多新的理念，比如良好的可擴(kuò)展性预鬓，弱化數(shù)據(jù)庫的設(shè)計范式巧骚，弱化一致性要求，在一定程度上解決了海量數(shù)據(jù)和高并發(fā)的問題格二，以至于很多人對“NoSQL是否會取代SQL”存在疑慮劈彪。然而，NoSQL只是對SQL特性的一種取舍和升華顶猜，使得SQL更加適應(yīng)海量數(shù)據(jù)的應(yīng)用場景沧奴，二者的優(yōu)勢將不斷融合，不存在誰取代誰的問題长窄。

關(guān)系數(shù)據(jù)庫在海量數(shù)據(jù)場景面臨如下挑戰(zhàn)：

事務(wù)　關(guān)系模型要求多個SQL操作滿足ACID特性滔吠，所有的SQL操作要么全部成功，要么全部失敗挠日。在分布式系統(tǒng)中疮绷，如果多個操作屬于不同的服務(wù)器，保證它們的原子性需要用到兩階段提交協(xié)議嚣潜，而這個協(xié)議的性能很低冬骚，且不能容忍服務(wù)器故障，很難應(yīng)用在海量數(shù)據(jù)場景懂算。

聯(lián)表　傳統(tǒng)的數(shù)據(jù)庫設(shè)計時需要滿足范式要求只冻，例如，第三范式要求在一個關(guān)系中不能出現(xiàn)在其他關(guān)系中已包含的非主鍵信息计技。假設(shè)存在一個部門信息表喜德，其中每個部門有部門編號、部門名稱酸役、部門簡介等信息住诸，那么在員工信息表中列出部門編號后就不能加入部門名稱驾胆、部門簡介等部門有關(guān)的信息，否則就會有大量的數(shù)據(jù)冗余贱呐。而在海量數(shù)據(jù)的場景丧诺，為了避免數(shù)據(jù)庫多表關(guān)聯(lián)操作，往往會使用數(shù)據(jù)冗余等違反數(shù)據(jù)庫范式的手段奄薇。實踐表明驳阎，這些手段帶來的收益遠(yuǎn)高于成本。

性能　關(guān)系數(shù)據(jù)庫采用B樹存儲引擎馁蒂，更新操作性能不如LSM樹這樣的存儲引擎呵晚。另外，如果只有基于主鍵的增沫屡、刪饵隙、查、改操作沮脖，關(guān)系數(shù)據(jù)庫的性能也不如專門定制的Key-Value存儲系統(tǒng)金矛。

隨著數(shù)據(jù)規(guī)模越來越大，可擴(kuò)展性以及性能提升可以帶來越來越明顯的收益勺届，而NoSQL系統(tǒng)要么可擴(kuò)展性好驶俊，要么在特定的應(yīng)用場景性能很高，廣泛應(yīng)用于互聯(lián)網(wǎng)業(yè)務(wù)中免姿。然而饼酿，NoSQL系統(tǒng)也面臨如下問題：

缺少統(tǒng)一標(biāo)準(zhǔn)。經(jīng)過幾十年的發(fā)展胚膊，關(guān)系數(shù)據(jù)庫已經(jīng)形成了SQL語言這樣的業(yè)界標(biāo)準(zhǔn)故俐，并擁有完整的生態(tài)鏈疮蹦。然而患雇，各個NoSQL系統(tǒng)使用方法不同，切換成本高痊远，很難通用肩榕。

使用以及運維復(fù)雜刚陡。NoSQL系統(tǒng)無論是選型，還是使用方式株汉，都有很大的學(xué)問筐乳，往往需要理解系統(tǒng)的實現(xiàn)，另外乔妈，缺乏專業(yè)的運維工具和運維人員蝙云。而關(guān)系數(shù)據(jù)庫具有完整的生態(tài)鏈和豐富的運維工具，也有大量經(jīng)驗豐富的運維人員路召。

事務(wù)與并發(fā)控制

事務(wù)規(guī)范了數(shù)據(jù)庫操作的語義勃刨，每個事務(wù)使得數(shù)據(jù)庫從一個一致的狀態(tài)原子地轉(zhuǎn)移到另一個一致的狀態(tài)波材。數(shù)據(jù)庫事務(wù)具有原子性（Atomicity）、一致性（Consistency）身隐、隔離性（Isolation）以及持久性（Durability）廷区，即ACID屬性，這些特性使得多個數(shù)據(jù)庫事務(wù)并發(fā)執(zhí)行時互不干擾贾铝，也不會獲取到中間狀態(tài)的錯誤結(jié)果隙轻。

多個事務(wù)并發(fā)執(zhí)行時，如果它們的執(zhí)行結(jié)果和按照某種順序一個接著一個串行執(zhí)行的效果等同垢揩，這種隔離級別稱為可串行化玖绿。可串行化是比較理想的情況叁巨，商業(yè)數(shù)據(jù)庫為了性能考慮斑匪，往往會定義多種隔離級別。事務(wù)的并發(fā)控制一般通過鎖機(jī)制來實現(xiàn)锋勺，鎖可以有不同的粒度秤标，可以鎖住行，也可以鎖住數(shù)據(jù)塊甚至鎖住整個表格宙刘。由于互聯(lián)網(wǎng)業(yè)務(wù)中讀事務(wù)的比例往往遠(yuǎn)遠(yuǎn)高于寫事務(wù)，為了提高讀事務(wù)性能牢酵，可以采用寫時復(fù)制（Copy-On-Write,COW）或者多版本并發(fā)控制（Multi-Version Concurrency Control,MVCC）技術(shù)來避免寫事務(wù)阻塞讀事務(wù)悬包。

事務(wù)

事務(wù)是數(shù)據(jù)庫操作的基本單位，它具有原子性馍乙、一致性布近、隔離性和持久性這四個基本屬性。

（1）原子性

事務(wù)的原子性首先體現(xiàn)在事務(wù)對數(shù)據(jù)的修改丝格，即要么全都執(zhí)行撑瞧，要么全都不執(zhí)行，例如显蝌，從銀行賬戶A轉(zhuǎn)一筆款項a到賬戶B预伺，結(jié)果必須是從A的賬戶上扣除款項a并且在B的賬戶上增加款項a，不能只是其中一個賬戶的修改曼尊。但是酬诀，事務(wù)的原子性并不總是能夠保證修改一定完成了或者一定沒有進(jìn)行，例如骆撇，在ATM機(jī)器上進(jìn)行上述轉(zhuǎn)賬瞒御，轉(zhuǎn)賬指令提交后通信中斷或者數(shù)據(jù)庫主機(jī)異常了，那么轉(zhuǎn)賬可能完成了也可能沒有進(jìn)行：如果通信中斷發(fā)生前數(shù)據(jù)庫主機(jī)完整接收到了轉(zhuǎn)賬指令且后續(xù)執(zhí)行也正常神郊，那么轉(zhuǎn)賬成功完成了肴裙；如果轉(zhuǎn)賬指令沒有到達(dá)數(shù)據(jù)庫主機(jī)或者雖然到達(dá)但后續(xù)執(zhí)行異常（例如寫操作日志失敗或者賬戶余額不足）趾唱，那么轉(zhuǎn)賬就沒有進(jìn)行。要確定轉(zhuǎn)賬是否成功蜻懦，需要待通信恢復(fù)或者數(shù)據(jù)庫主機(jī)恢復(fù)后查詢賬戶交易歷史或余額甜癞。事務(wù)的原子性也體現(xiàn)在事務(wù)對數(shù)據(jù)的讀取上，例如阻肩，一個事務(wù)對同一數(shù)據(jù)項的多次讀取的結(jié)果一定是相同的带欢。

（2）一致性

事務(wù)需要保持?jǐn)?shù)據(jù)庫數(shù)據(jù)的正確性、完整性和一致性烤惊，有些時候這種一致性由數(shù)據(jù)庫的內(nèi)部規(guī)則保證乔煞，例如數(shù)據(jù)的類型必須正確，數(shù)據(jù)值必須在規(guī)定的范圍內(nèi)柒室，等等渡贾；另外一些時候這種一致性由應(yīng)用保證，例如一般情況下銀行賬務(wù)余額不能是負(fù)數(shù)雄右，信用卡消費不能超過該卡的信用額度等空骚。

（3）隔離性

許多時候數(shù)據(jù)庫在并發(fā)執(zhí)行多個事務(wù)，每個事務(wù)可能需要對多個表項進(jìn)行修改和查詢擂仍，與此同時囤屹，更多的查詢請求可能也在執(zhí)行中。數(shù)據(jù)庫需要保證每一個事務(wù)在它的修改全部完成之前逢渔，對其他的事務(wù)是不可見的肋坚，換句話說，不能讓其他事務(wù)看到該事務(wù)的中間狀態(tài)肃廓，例如智厌，從銀行賬戶A轉(zhuǎn)一筆款項a到賬戶B，不能讓其他事務(wù)（例如賬戶查詢）看到A賬戶已經(jīng)扣除款項a但B賬戶卻還沒有增加款項a的狀態(tài)盲赊。

（4）持久性

事務(wù)完成后铣鹏，它對于數(shù)據(jù)庫的影響是永久性的，即使系統(tǒng)出現(xiàn)各種異常也是如此哀蘑。

出于性能考慮诚卸，許多數(shù)據(jù)庫允許使用者選擇犧牲隔離屬性來換取并發(fā)度，從而獲得性能的提升绘迁。SQL定義了4種隔離級別惨险。

Read Uncommitted（RU）：讀取未提交的數(shù)據(jù)，即其他事務(wù)已經(jīng)修改但還未提交的數(shù)據(jù)脊髓，這是最低的隔離級別辫愉；

Read Committed（RC）：讀取已提交的數(shù)據(jù)，但是将硝，在一個事務(wù)中恭朗，對同一個項屏镊，前后兩次讀取的結(jié)果可能不一樣，例如第一次讀取時另一個事務(wù)的修改還沒有提交痰腮，第二次讀取時已經(jīng)提交了而芥；

Repeatable Read（RR）：可重復(fù)讀取，在一個事務(wù)中膀值，對同一個項棍丐，確保前后兩次讀取的結(jié)果一樣；

Serializable（S）：可序列化沧踏，即數(shù)據(jù)庫的事務(wù)是可串行化執(zhí)行的歌逢，就像一個事務(wù)執(zhí)行的時候沒有別的事務(wù)同時在執(zhí)行，這是最高的隔離級別翘狱。

隔離級別的降低可能導(dǎo)致讀到臟數(shù)據(jù)或者事務(wù)執(zhí)行異常秘案，例如：

Lost Update（LU）：第一類丟失更新：兩個事務(wù)同時修改一個數(shù)據(jù)項，但后一個事務(wù)中途失敗回滾潦匈，則前一個事務(wù)已提交的修改都可能丟失阱高；

Dirty Reads（DR）：一個事務(wù)讀取了另外一個事務(wù)更新卻沒有提交的數(shù)據(jù)項；

Non-Repeatable Reads（NRR）：一個事務(wù)對同一數(shù)據(jù)項的多次讀取可能得到不同的結(jié)果茬缩；

Second Lost Updates problem（SLU）：第二類丟失更新：兩個并發(fā)事務(wù)同時讀取和修改同一數(shù)據(jù)項赤惊，則后面的修改可能使得前面的修改失效；

Phantom Reads（PR）：事務(wù)執(zhí)行過程中凰锡，由于前面的查詢和后面的查詢的期間有另外一個事務(wù)插入數(shù)據(jù)荐捻，后面的查詢結(jié)果出現(xiàn)了前面查詢結(jié)果中未出現(xiàn)的數(shù)據(jù)。

表2-3說明了隔離級別與讀寫異常（不一致）的關(guān)系寡夹。容易發(fā)現(xiàn)，所有的隔離級別都保證不會出現(xiàn)第一類丟失更新厂置，另外菩掏，在最高隔離級別（Serializable）下，數(shù)據(jù)不會出現(xiàn)讀寫的不一致昵济。

并發(fā)控制

1.數(shù)據(jù)庫鎖

事務(wù)分為幾種類型：讀事務(wù)智绸，寫事務(wù)以及讀寫混合事務(wù)。相應(yīng)地访忿，鎖也分為兩種類型：讀鎖以及寫鎖瞧栗，允許對同一個元素加多個讀鎖，但只允許加一個寫鎖海铆，且寫事務(wù)將阻塞讀事務(wù)迹恐。這里的元素可以是一行，也可以是一個數(shù)據(jù)塊甚至一個表格卧斟。事務(wù)如果只操作一行殴边，可以對該行加相應(yīng)的讀鎖或者寫鎖憎茂；如果操作多行，需要鎖住整個行范圍锤岸。

表2-4中T1和T2兩個事務(wù)操作不同行竖幔，初始時A=B=25，T1將A加100是偷，T2將B乘以2拳氢，由于T1和T2操作不同行，兩個事務(wù)沒有鎖沖突蛋铆，可以并行執(zhí)行而不會破壞系統(tǒng)的一致性馋评。

表2-5中T1掃描從A到C的所有行，將它們的結(jié)果相加后更新A戒职，初始時A=C=25栗恩，假設(shè)在T1執(zhí)行過程中T2插入一行B，那么洪燥，事務(wù)T1和T2無法做到可串行化磕秤。為了保證數(shù)據(jù)庫一致性，T1執(zhí)行范圍掃描時需要鎖住從A到C這個范圍的所有更新捧韵，T2插入B時市咆，由于整個范圍被鎖住，T2獲取鎖失敗而等待T1先執(zhí)行完成再来。

多個事務(wù)并發(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這兩個事務(wù)循環(huán)依賴殖侵，任何一個事務(wù)都無法順利完成。

解決死鎖的思路主要有兩種：第一種思路是為每個事務(wù)設(shè)置一個超時時間镰烧，超時后自動回滾拢军，表2-6中如果T1或T2二者之中的某個事務(wù)回滾，則另外一個事務(wù)可以成功執(zhí)行怔鳖。第二種思路是死鎖檢測茉唉。死鎖出現(xiàn)的原因在于事務(wù)之間互相依賴，T1依賴T2，T2又依賴T1赌渣，依賴關(guān)系構(gòu)成一個環(huán)路魏铅。檢測到死鎖后可以通過回滾其中某些事務(wù)來消除循環(huán)依賴。

2.寫時復(fù)制

互聯(lián)網(wǎng)業(yè)務(wù)中讀事務(wù)占的比例往往遠(yuǎn)遠(yuǎn)超過寫事務(wù)坚芜，很多應(yīng)用的讀寫比例達(dá)到6:1览芳，甚至10:1。寫時復(fù)制（Copy-On-Write,COW）讀操作不用加鎖鸿竖，極大地提高了讀取性能沧竟。

1）拷貝：將從葉子到根節(jié)點路徑上的所有節(jié)點拷貝出來。

2）修改：對拷貝的節(jié)點執(zhí)行修改缚忧。

3）提交：原子地切換根節(jié)點的指針悟泵，使之指向新的根節(jié)點。

如果讀操作發(fā)生在第3步提交之前闪水，那么糕非，將讀取老節(jié)點的數(shù)據(jù)，否則將讀取新節(jié)點球榆，讀操作不需要加鎖保護(hù)朽肥。寫時復(fù)制技術(shù)涉及引用計數(shù)，對每個節(jié)點維護(hù)一個引用計數(shù)持钉，表示被多少節(jié)點引用衡招，如果引用計數(shù)變?yōu)?，說明沒有節(jié)點引用每强，可以被垃圾回收始腾。

寫時復(fù)制技術(shù)原理簡單，問題是每次寫操作都需要拷貝從葉子到根節(jié)點路徑上的所有節(jié)點空执，寫操作成本高浪箭，另外，多個寫操作之間是互斥的辨绊，同一時刻只允許一個寫操作奶栖。

3.多版本并發(fā)控制

除了寫時復(fù)制技術(shù)，多版本并發(fā)控制邢羔，即MVCC（Multi-Version Concurrency Control），也能夠?qū)崿F(xiàn)讀事務(wù)不加鎖桑孩。MVCC對每行數(shù)據(jù)維護(hù)多個版本拜鹤，無論事務(wù)的執(zhí)行時間有多長，MVCC總是能夠提供與事務(wù)開始時刻相一致的數(shù)據(jù)流椒。

以MySQL InnoDB存儲引擎為例敏簿，InnoDB對每一行維護(hù)了兩個隱含的列，其中一列存儲行被修改的“時間”，另外一列存儲行被刪除的“時間”惯裕，注意温数，InnoDB存儲的并不是絕對時間，而是與時間對應(yīng)的數(shù)據(jù)庫系統(tǒng)的版本號蜻势，每當(dāng)一個事務(wù)開始時撑刺，InnoDB都會給這個事務(wù)分配一個遞增的版本號，所以版本號也可以被認(rèn)為是事務(wù)號握玛。對于每一行查詢語句够傍，InnoDB都會把這個查詢語句的版本號同這個查詢語句遇到的行的版本號進(jìn)行對比，然后結(jié)合不同的事務(wù)隔離級別挠铲，來決定是否返回改行冕屯。

故障恢復(fù)

數(shù)據(jù)庫運行過程中可能會發(fā)生故障，這個時候某些事務(wù)可能執(zhí)行到一半但沒有提交拂苹，當(dāng)系統(tǒng)重啟時安聘，需要能夠恢復(fù)到一致的狀態(tài)，即要么提交整個事務(wù)瓢棒，要么回滾浴韭。數(shù)據(jù)庫系統(tǒng)以及其他的分布式存儲系統(tǒng)一般采用操作日志（有時也稱為提交日志，即Commit Log）技術(shù)來實現(xiàn)故障恢復(fù)音羞。操作日志分為回滾日志（UNDO Log）囱桨、重做日志（REDO Log）以及UNDO/REDO日志。如果記錄事務(wù)修改前的狀態(tài)嗅绰，則為回滾日志舍肠；相應(yīng)地，如果記錄事務(wù)修改后的狀態(tài)窘面，則為重做日志翠语。本節(jié)介紹操作日志及故障恢復(fù)基礎(chǔ)知識。

操作日志

為了保證數(shù)據(jù)庫的一致性财边，數(shù)據(jù)庫操作需要持久化到磁盤肌括，如果每次操作都隨機(jī)更新磁盤的某個數(shù)據(jù)塊，系統(tǒng)性能將會很差酣难。因此谍夭，通過操作日志順序記錄每個數(shù)據(jù)庫操作并在內(nèi)存中執(zhí)行這些操作，內(nèi)存中的數(shù)據(jù)定期刷新到磁盤憨募，實現(xiàn)將隨機(jī)寫請求轉(zhuǎn)化為順序?qū)懻埱蟆?br>

操作日志記錄了事務(wù)的操作紧索。例如，事務(wù)T對表格中的X執(zhí)行加10操作菜谣，初始時X=5珠漂，更新后X=15晚缩，那么，UNDO日志記為＜T,X,5＞媳危，REDO日志記為＜T,X,15＞荞彼，UNDO/REDO日志記為＜T,X,5,15＞。

關(guān)系數(shù)據(jù)庫系統(tǒng)一般采用UNDO/REDO日志待笑，相關(guān)技術(shù)可以參考數(shù)據(jù)庫系統(tǒng)實現(xiàn)方面的資料鸣皂。可以將關(guān)系數(shù)據(jù)庫存儲模型做一定程度的簡化：

1）假設(shè)內(nèi)存足夠大，每次事務(wù)的修改操作都可以緩存在內(nèi)存中。

2）數(shù)據(jù)庫的每個事務(wù)只包含一個操作农尖，即每個事務(wù)都必須立即提交（Auto Commit）北专。

REDO日志要求我們將所有未提交事務(wù)修改的數(shù)據(jù)塊保留在內(nèi)存中。簡化后的存儲模型可以采用單一的REDO日志，大大簡化了存儲系統(tǒng)故障恢復(fù)。

重做日志

存儲系統(tǒng)如果采用REDO日志，其寫操作流程如下：

1）將REDO日志以追加寫的方式寫入磁盤的日志文件慎宾。

2）將REDO日志的修改操作應(yīng)用到內(nèi)存中。

3）返回操作成功或者失敗浅悉。

REDO日志的約束規(guī)則為：在修改內(nèi)存中的元素X之前趟据，要確保與這一修改相關(guān)的操作日志必須先刷入到磁盤中。顧名思義术健，用REDO日志進(jìn)行故障恢復(fù)汹碱，只需要從頭到尾讀取日志文件中的修改操作，并將它們逐個應(yīng)用到內(nèi)存中荞估，即重做一遍咳促。

為什么需要先寫操作日志再修改內(nèi)存中的數(shù)據(jù)呢？假如先修改內(nèi)存中的數(shù)據(jù)勘伺，那么用戶就能立刻讀到修改后的結(jié)果跪腹，一旦在完成內(nèi)存修改與寫入日志之間發(fā)生故障，那么最近的修改操作無法恢復(fù)飞醉。然而冲茸，之前的用戶可能已經(jīng)讀取了修改后的結(jié)果，這就會產(chǎn)生不一致的情況缅帘。

優(yōu)化手段

1.成組提交

存儲系統(tǒng)要求先將REDO日志刷入磁盤才可以更新內(nèi)存中的數(shù)據(jù)轴术，如果每個事務(wù)都要求將日志立即刷入磁盤，系統(tǒng)的吞吐量將會很差钦无。因此逗栽，存儲系統(tǒng)往往有一個是否立即刷入磁盤的選項，對于一致性要求很高的應(yīng)用铃诬，可以設(shè)置為立即刷入祭陷；相應(yīng)地，對于一致性要求不太高的應(yīng)用趣席，可以設(shè)置為不要求立即刷入兵志，首先將REDO日志緩存到操作系統(tǒng)或者存儲系統(tǒng)的內(nèi)存緩沖區(qū)中，定期刷入磁盤宣肚。這種做法有一個問題想罕，如果存儲系統(tǒng)意外故障，可能丟失最后一部分更新操作霉涨。

成組提交（Group Commit）技術(shù)是一種有效的優(yōu)化手段按价。REDO日志首先寫入到存儲系統(tǒng)的日志緩沖區(qū)中：

a）日志緩沖區(qū)中的數(shù)據(jù)量超過一定大小，比如512KB笙瑟；

b）距離上次刷入磁盤超過一定時間楼镐，比如10ms。

當(dāng)滿足以上兩個條件中的某一個時往枷，將日志緩沖區(qū)中的多個事務(wù)操作一次性刷入磁盤框产，接著一次性將多個事務(wù)的修改操作應(yīng)用到內(nèi)存中并逐個返回客戶端操作結(jié)果。與定期刷入磁盤不同的是错洁，成組提交技術(shù)保證REDO日志成功刷入磁盤后才返回寫操作成功秉宿。這種做法可能會犧牲寫事務(wù)的延時，但大大提高了系統(tǒng)的吞吐量屯碴。

2.檢查點

如果所有的數(shù)據(jù)都保存在內(nèi)存中描睦，那么可能出現(xiàn)兩個問題：

故障恢復(fù)時需要回放所有的REDO日志，效率較低导而。如果REDO日志較多忱叭，比如超過100GB，那么嗡载，故障恢復(fù)時間是無法接受的窑多。

內(nèi)存不足。即使內(nèi)存足夠大洼滚，存儲系統(tǒng)往往也只能夠緩存最近較長一段時間的更新操作埂息，很難緩存所有的數(shù)據(jù)。

因此遥巴，需要將內(nèi)存中的數(shù)據(jù)定期轉(zhuǎn)儲（Dump）到磁盤千康，這種技術(shù)稱為checkpoint（檢查點）技術(shù)。系統(tǒng)定期將內(nèi)存中的操作以某種易于加載的形式（checkpoint文件）轉(zhuǎn)儲到磁盤中铲掐，并記錄checkpoint時刻的日志回放點拾弃，以后故障恢復(fù)只需要回放checkpoint時刻的日志回放點之后的REDO日志。

由于將內(nèi)存數(shù)據(jù)轉(zhuǎn)儲到磁盤需要很長的時間摆霉，而這段時間還可能有新的更新操作豪椿，checkpoint必須找到一個一致的狀態(tài)奔坟。checkpoint流程如下：

1）日志文件中記錄"START CKPT"。

2）將內(nèi)存中的數(shù)據(jù)以某種易于加載的組織方式轉(zhuǎn)儲到磁盤中搭盾，形成checkpoint文件咳秉。checkpoint文件中往往記錄"START CKPT"的日志回放點，用于故障恢復(fù)鸯隅。

3）日志文件中記錄"END CKPT"澜建。

故障恢復(fù)流程如下：

1）將checkpoint文件加載到內(nèi)存中，這一步操作往往只需要加載索引數(shù)據(jù)蝌以，加載效率很高炕舵。

2）讀取checkpoint文件中記錄的"START CKPT"日志回放點，回放之后的REDO日志跟畅。

上述checkpoint故障恢復(fù)方式依賴REDO日志中記錄的都是修改后的結(jié)果這一特性咽筋，也就是說，即使checkpoint文件中已經(jīng)包含了某些操作的結(jié)果徊件，重新回放一次或者多次這些操作的REDO日志也不會造成數(shù)據(jù)錯誤晤硕。如果同一個操作執(zhí)行一次與重復(fù)執(zhí)行多次的效果相同，這種操作具有“冪等性”庇忌。有些操作不具備這種特性舞箍，例如，加法操作皆疹、追加操作疏橄。如果REDO日志記錄的是這種操作，那么checkpoint文件中的數(shù)據(jù)一定不能包含"START CKPT"與"END CKPT"之間的操作略就。為此捎迫，主要有兩種處理方法：

checkpoint過程中停止寫服務(wù)，所有的修改操作直接失敗表牢。這種方法實現(xiàn)簡單窄绒，但不適合在線業(yè)務(wù)。

內(nèi)存數(shù)據(jù)結(jié)構(gòu)支持快照崔兴。執(zhí)行checkpoint操作時首先對內(nèi)存數(shù)據(jù)結(jié)構(gòu)做一次快照彰导，接著將快照中的數(shù)據(jù)轉(zhuǎn)儲到磁盤生成checkpoint文件，并記錄此時對應(yīng)的REDO日志回放點敲茄。生成checkpoint文件的過程中允許寫操作位谋，但checkpoint文件中的快照數(shù)據(jù)不會包含這些操作的結(jié)果。

數(shù)據(jù)壓縮

數(shù)據(jù)壓縮分為有損壓縮與無損壓縮兩種堰燎，有損壓縮算法壓縮比率高掏父，但數(shù)據(jù)可能失真，一般用于壓縮圖片秆剪、音頻赊淑、視頻爵政；而無損壓縮算法能夠完全還原原始數(shù)據(jù)，本文只討論無損壓縮算法陶缺。早期的數(shù)據(jù)壓縮技術(shù)就是基于編碼上的優(yōu)化技術(shù)茂卦，其中以Huffman編碼最為知名，它通過統(tǒng)計字符出現(xiàn)的頻率計算最優(yōu)前綴編碼组哩。1977年，以色列人Jacob Ziv和Abraham Lempel發(fā)表論文《順序數(shù)據(jù)壓縮的一個通用算法》处渣，從此伶贰，LZ系列壓縮算法幾乎壟斷了通用無損壓縮領(lǐng)域，常用的Gzip算法中使用的LZ77罐栈，GIF圖片格式中使用的LZW黍衙，以及LZO等壓縮算法都屬于這個系列。設(shè)計壓縮算法時不僅要考慮壓縮比荠诬，還要考慮壓縮算法的執(zhí)行效率琅翻。Google Bigtable系統(tǒng)中采用BMDiff和Zippy壓縮算法，這兩個算法也是LZ算法的變種柑贞，它們通過犧牲一定的壓縮比方椎，換來執(zhí)行效率的大幅提升。

壓縮算法的核心是找重復(fù)數(shù)據(jù)钧嘶，列式存儲技術(shù)通過把相同列的數(shù)據(jù)組織在一起棠众，不僅減少了大數(shù)據(jù)分析需要查詢的數(shù)據(jù)量，還大大地提高了數(shù)據(jù)的壓縮比有决。傳統(tǒng)的OLAP（Online Analytical Processing）數(shù)據(jù)庫闸拿，如Sybase IQ、Teradata书幕，以及Bigtable新荤、HBase等分布式表格系統(tǒng)都實現(xiàn)了列式存儲。本節(jié)介紹數(shù)據(jù)壓縮以及列式存儲相關(guān)的基礎(chǔ)知識台汇。

壓縮算法

壓縮是一個專門的研究課題苛骨，沒有通用的做法，需要根據(jù)數(shù)據(jù)的特點選擇或者自己開發(fā)合適的算法苟呐。壓縮的本質(zhì)就是找數(shù)據(jù)的重復(fù)或者規(guī)律智袭，用盡量少的字節(jié)表示。

Huffman編碼是一種基于編碼的優(yōu)化技術(shù)掠抬，通過統(tǒng)計字符出現(xiàn)的頻率來計算最優(yōu)前綴編碼吼野。LZ系列算法一般有一個窗口的概念，在窗口內(nèi)部找重復(fù)并維護(hù)數(shù)據(jù)字典两波。常用的壓縮算法包括Gzip瞳步、LZW闷哆、LZO，這些算法都借鑒或改進(jìn)了原始的LZ77算法单起，如Gzip壓縮混合使用了LZ77以及Huffman編碼抱怔，LZW以及LZO算法是LZ77思想在實現(xiàn)手段的進(jìn)一步優(yōu)化。

存儲系統(tǒng)在選擇壓縮算法時需要考慮壓縮比和效率嘀倒。讀操作需要先讀取磁盤中的內(nèi)容再解壓縮屈留，寫操作需要先壓縮再將壓縮結(jié)果寫入到磁盤，整個操作的延時包括壓縮/解壓縮和磁盤讀寫的延遲测蘑，壓縮比越大灌危，磁盤讀寫的數(shù)據(jù)量越小，而壓縮/解壓縮的時間也會越長碳胳，所以這里需要一個很好的權(quán)衡點勇蝙。Google Bigtable系統(tǒng)中使用了BMDiff以及Zippy兩種壓縮算法，它們通過犧牲一定的壓縮比換取算法執(zhí)行速度的大幅提升挨约，從而獲得更好的折衷味混。

1.Huffman編碼

前綴編碼要求一個字符的編碼不能是另一個字符的前綴。假設(shè)有三個字符A诫惭、B翁锡、C，它們的二進(jìn)制編碼分別是0夕土、1盗誊、01，如果我們收到一段信息是01010隘弊，解碼時我們?nèi)绾螀^(qū)分是CCA還是ABABA哈踱，或者ABCA呢？一種解決方案就是前綴編碼梨熙，要求一個字符編碼不能是另外一個字符編碼的前綴开镣。如果使用前綴編碼將A、B咽扇、C編碼為：

A：0　B：10　C：110

這樣邪财，01010就只能被翻譯成ABB。Huffman編碼需要解決的問題是质欲，如何找出一種前綴編碼方式树埠，使得編碼的長度最短。

假設(shè)有一個字符串3334444555556666667777777嘶伟，它是由3個3怎憋，4個4，5個5，6個6绊袋，7個7組成的毕匀。那么，對應(yīng)的前綴編碼可能是：

1）3:000　4:001　5:010　6:011　7:1

2）3:000　4:001　7:01　5:10　6:11

第1種編碼方式的權(quán)值為（3+4+5+6）*3+7*1=61癌别，而第2種編碼方式的權(quán)值為（3+4）*3+（5+6+7）*2=57皂岔。可以看出展姐，第2種編碼方式的長度更短躁垛，而且我們還可以知道，第2種編碼方式是最優(yōu)的Huffman編碼圾笨。Huffman編碼的構(gòu)造過程不在本書討論范圍之內(nèi)教馆，感興趣的讀者可以參考數(shù)據(jù)結(jié)構(gòu)的相關(guān)圖書。

2.LZ系列壓縮算法

LZ系列壓縮算法是基于字典的壓縮算法墅拭。假設(shè)需要壓縮一篇英文文章，最容易想到的壓縮算法是構(gòu)造一本英文字典涣狗，這樣谍婉，我們只需要保存每個單詞在字典中出現(xiàn)的頁碼和位置就可以了。頁碼用兩個字節(jié)镀钓，位置用一個字節(jié)穗熬，那么一個單詞需要使用三個字節(jié)表示，而我們知道一般的英語單詞長度都在三個字節(jié)以上丁溅。因此唤蔗，我們實現(xiàn)了對這篇英文文章的壓縮。當(dāng)然窟赏，實際的通用壓縮算法不能這么做妓柜，因為我們在解壓時需要一本英文字典，而這部分信息是壓縮程序不可預(yù)知的涯穷，同時也不能保存在壓縮信息里面棍掐。LZ系列的算法是一種動態(tài)創(chuàng)建字典的方法，壓縮過程中動態(tài)創(chuàng)建字典并保存在壓縮信息里面拷况。

LZ77是第一個LZ系列的算法作煌，比如字符串ABCABCDABC中ABC重復(fù)出現(xiàn)了三次，壓縮信息中只需要保存第一個ABC赚瘦，后面兩個ABC只需要把第一個出現(xiàn)ABC的位置和長度存儲下來就可以了粟誓。這樣，保存后面兩個ABC就只需要一個二元數(shù)組＜匹配串的相對位置起意，匹配長度＞鹰服。解壓的時候，根據(jù)匹配串的相對位置揽咕，向前找到第一個ABC的位置获诈，然后根據(jù)匹配的長度仍源，直接把第一個ABC復(fù)制到當(dāng)前解壓緩沖區(qū)里面就可以了。

如表2-7所示舔涎，{S}*表示字符串S的所有子串構(gòu)成的集合笼踩，例如，{ABC}*是字符串A亡嫌、B嚎于、C、AB挟冠、BC于购、ABC構(gòu)成的集合。每一步執(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é)表示匹配信息？記錄重復(fù)信息的匹配信息包含兩項拜银，一個是匹配串的相對位置殊鞭，另一個是匹配的長度。例如尼桶，可以采用固定的兩個字節(jié)來表示匹配信息操灿，其中，1位用來區(qū)分源信息和匹配信息泵督，11位表示匹配位置趾盐，4位表示匹配長度。這樣，壓縮算法支持的最大數(shù)據(jù)窗口為2_{11}=2048字節(jié)救鲤，支持重復(fù)串的最大長度為2_{4}=16字節(jié)久窟。當(dāng)然，也可以采用變長的方式表示匹配信息本缠。

3）如何快速查找最長匹配串斥扛？最容易想到的做法是把字符串的所有子串都存放到一張哈希表中，表2-7中第4步執(zhí)行前哈希表中包含ABC的所有子串丹锹，即A稀颁、AB、BC楣黍、ABC匾灶。這種做法的運行效率很低，實際的做法往往會做一些改進(jìn)租漂。例如阶女，哈希表中只保存所有長度為3的子串，如果在數(shù)據(jù)字典中找到匹配串哩治，即前3個字節(jié)相同秃踩，接著再往后順序遍歷找出最長匹配。

3.BMDiff與Zippy

在Google的Bigtable系統(tǒng)中锚扎，設(shè)計了BMDiff和Zippy兩種壓縮算法吞瞪。BMDiff和Zippy（也稱為Snappy）也屬于LZ系列犹菱，相比傳統(tǒng)的LZW或者Gzip蚌堵，這兩種算法的壓縮比不算高瓶盛，但是處理速度非常快翠勉。Zippy和BMDiff的壓縮/解壓縮速度是Gzip算法的5～10倍。

列式存儲

傳統(tǒng)的行式數(shù)據(jù)庫將一個個完整的數(shù)據(jù)行存儲在數(shù)據(jù)頁中霉颠。如果處理查詢時需要用到大部分的數(shù)據(jù)列对碌，這種方式在磁盤IO上是比較高效的。一般來說蒿偎，OLTP（Online Transaction Processing朽们，聯(lián)機(jī)事務(wù)處理）應(yīng)用適合采用這種方式。

一個OLAP類型的查詢可能需要訪問幾百萬甚至幾十億個數(shù)據(jù)行诉位，且該查詢往往只關(guān)心少數(shù)幾個數(shù)據(jù)列骑脱。例如，查詢今年銷量最高的前20個商品苍糠，這個查詢只關(guān)心三個數(shù)據(jù)列：時間（date）叁丧、商品（item）以及銷售量（sales amount）。商品的其他數(shù)據(jù)列，例如商品URL拥娄、商品描述蚊锹、商品所屬店鋪，等等稚瘾，對這個查詢都是沒有意義的牡昆。

如圖2-11所示，列式數(shù)據(jù)庫是將同一個數(shù)據(jù)列的各個值存放在一起孟抗。插入某個數(shù)據(jù)行時迁杨，該行的各個數(shù)據(jù)列的值也會存放到不同的地方。上例中列式數(shù)據(jù)庫只需要讀取存儲著“時間凄硼、商品铅协、銷量”的數(shù)據(jù)列，而行式數(shù)據(jù)庫需要讀取所有的數(shù)據(jù)列摊沉。因此狐史，列式數(shù)據(jù)庫大大地提高了OLAP大數(shù)據(jù)量查詢的效率。當(dāng)然说墨，列式數(shù)據(jù)庫不是萬能的骏全，每次讀取某個數(shù)據(jù)行時，需要分別從不同的地方讀取各個數(shù)據(jù)列的值尼斧，然后合并在一起形成數(shù)據(jù)行姜贡。因此，如果每次查詢涉及的數(shù)據(jù)量較小或者大部分查詢都需要整行的數(shù)據(jù)棺棵，列式數(shù)據(jù)庫并不適用楼咳。

很多列式數(shù)據(jù)庫還支持列組（column group,Bigtable系統(tǒng)中稱為locality group），即將多個經(jīng)常一起訪問的數(shù)據(jù)列的各個值存放在一起烛恤。如果讀取的數(shù)據(jù)列屬于相同的列組母怜，列式數(shù)據(jù)庫可以從相同的地方一次性讀取多個數(shù)據(jù)列的值，避免了多個數(shù)據(jù)列的合并缚柏。列組是一種行列混合存儲模式苹熏，這種模式能夠同時滿足OLTP和OLAP的查詢需求。

由于同一個數(shù)據(jù)列的數(shù)據(jù)重復(fù)度很高币喧，因此轨域，列式數(shù)據(jù)庫壓縮時有很大的優(yōu)勢。例如杀餐，Google Bigtable列式數(shù)據(jù)庫對網(wǎng)頁庫壓縮可以達(dá)到15倍以上的壓縮率干发。另外，可以針對列式存儲做專門的索引優(yōu)化怜浅。比如铐然，性別列只有兩個值蔬崩，“男”和“女”，可以對這一列建立位圖索引：

如圖2-12所示搀暑，“男”對應(yīng)的位圖為100101沥阳，表示第1、4自点、6行值為“男”桐罕；“女”對應(yīng)的位圖為011010，表示第2桂敛、3功炮、5行值為“女”。如果需要查找男性或者女性的個數(shù)术唬，只需要統(tǒng)計相應(yīng)的位圖中1出現(xiàn)的次數(shù)即可薪伏。另外，建立位圖索引后0和1的重復(fù)度高粗仓，可以采用專門的編碼方式對其進(jìn)行壓縮嫁怀。