前兩篇都是在介紹一些數(shù)據(jù)密集型應(yīng)用的名詞,包括可靠性,可擴(kuò)展性,可維護(hù)性,數(shù)據(jù)模型等,這一篇我們來從數(shù)據(jù)存儲的角度看看,不同的數(shù)據(jù)模型,怎樣存儲和檢索數(shù)據(jù).這里開始是比較硬核的內(nèi)容了,前面的感覺書里面寫的也比較簡單.

首先來看看兩個存儲引擎家族:日志結(jié)構(gòu)的存儲引擎和面向頁的存儲引擎.
面向頁的存儲引擎,比如B-Tree一般用于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫.
日志結(jié)構(gòu)的存儲引擎,比如LSM-Tree則用于大部分NoSQL的數(shù)據(jù)庫.

數(shù)據(jù)庫的核心:數(shù)據(jù)結(jié)構(gòu)

#!/bin/bash
function db_set() {
    echo "$1.$2" >> database
}
function db_get() {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

上面是一個最簡單的K-V數(shù)據(jù)庫.基于文本文件,每行代表一條記錄.
db_set函數(shù)運(yùn)行的非常快,因?yàn)椴捎米芳拥姆绞?對應(yīng)于磁盤的順序?qū)懖僮?基于日志結(jié)構(gòu)的數(shù)據(jù)庫系統(tǒng)一般也采用這種方式,即日志文件只能追加,不能修改.
但是如果database文件保存了太多的數(shù)據(jù),那么db_get函數(shù)的運(yùn)行將不盡如人意.因?yàn)槲覀兪菕呙枵麄€文件的.
為了提高查詢的效率我們需要引入索引這個概念.索引就是通過記錄一些額外的元數(shù)據(jù),然后使用這些元數(shù)據(jù)作為路標(biāo),幫助定位需要查詢的數(shù)據(jù).
這里有一個基本原理:索引只會提升查詢效率,但是一定會降低寫入效率.因?yàn)槊看螌懭攵及殡S了處理索引這個數(shù)據(jù)結(jié)構(gòu).

哈希索引

我們先從K-V索引開始.為了查詢的更快我們可以想到編程語言中的hash map(或者h(yuǎn)ash table)將我們的查詢效率從O(n)降低到O(1).
一種最簡單的想法是,我們在內(nèi)存中維護(hù)一張hash map,其中key就是數(shù)據(jù)庫中的鍵,value則是值相對于文件開始處的偏移量.這樣在查找的時候,就可以直接通過這張hash map找到對應(yīng)的偏移量,然后直接讀取value.
使用這種哈希索引的方式有以下缺陷:

1. 必須能在內(nèi)存中保存所有的key.
2. 針對區(qū)間查詢不友好.

但是使用這種方式存儲數(shù)據(jù)的時候,還需要一種方式來避免磁盤被用盡.我們可以將database文件拆分為多個固定大小的段,當(dāng)當(dāng)前文件達(dá)到這個限制時就關(guān)閉,然后新的寫入請求寫入新的文件中,然后就可以在這些段上進(jìn)行壓縮操作.
壓縮意味著去掉重復(fù)的鍵,對每個鍵只保留最新的value.同時在壓縮過程中也可以通過歸并的方式合并多個段,從而減少壓縮段的數(shù)量.
我們可以對每一個段維護(hù)一個對應(yīng)的hash map索引,這樣在查找時則先查找最新段的hash map,如果不存在在查找次新段的hash map,以此類推.由于合并的存在我們不會維護(hù)太多的段,所以這個迭代查詢是可以接受的.
這個想法還有一些需要解決的問題:

1. database的文件格式.使用純文本保存數(shù)據(jù)并不是最佳實(shí)踐.我們可以使用二進(jìn)制格式來替代.
2. 目前不支持刪除記錄.刪除記錄的時候我們的database文件需要記錄一個特殊的標(biāo)記,同時在hash map中刪除掉這個key.在合并段的時候如果發(fā)現(xiàn)這個標(biāo)記則丟棄這個key所有記錄.
3. 崩潰恢復(fù).如果系統(tǒng)崩潰,我們將丟失整個索引信息.雖然可以通過掃描所有的database文件進(jìn)行重建,但是這樣耗時很長.Bitcask通過將每個段的hash map的快照保存到磁盤上,可以更快的進(jìn)行恢復(fù).
4. 部分寫入的記錄.記錄寫入database文件時也可能發(fā)生崩潰,導(dǎo)致記錄沒有寫完整.Bitcask通過增加校驗(yàn)值的方式進(jìn)行檢查,發(fā)現(xiàn)以后直接丟棄該記錄.
5. 并發(fā)控制.寫操作是順序追加的,所以應(yīng)該只有一個線程執(zhí)行寫動作.但是可以并發(fā)的讀操作(讀寫鎖).

使用追加的方式存儲數(shù)據(jù)的優(yōu)勢:

1. 追加和分段合并都是順序?qū)懙膭幼?順序?qū)懘疟P性能要比隨機(jī)寫好很多.
2. 追加操作說明文件之前的記錄是不可變的,這樣進(jìn)行并發(fā)控制和崩潰恢復(fù)比較簡單.不會出現(xiàn)舊值和新值各一部分的情況.
3. 合并操作可以避免隨著時間的推移出現(xiàn)數(shù)據(jù)文件碎片化的問題.

SSTables和LSM-Tree

目前針對database中保存的內(nèi)容是完全按照寫入的順序追加進(jìn)來的.現(xiàn)在我們添加一條規(guī)則:要求對寫入的K-V對根據(jù)K進(jìn)行排序.
這似乎打破了順序?qū)懭氲囊?guī)則,不過先讓我們來看看這樣做帶來的好處吧.

1. 合并段更加高效了.思想類似于合并多個有序鏈表的方式.
2. 由于數(shù)據(jù)排列有序,現(xiàn)在不需要在內(nèi)存中保存整個Key的hash map了.可以采用稀疏的hash map索引.
3. 可以將兩個索引之間的數(shù)據(jù)保存在一個塊中并在寫入磁盤之前進(jìn)行壓縮.然后稀疏內(nèi)存索引的每個條目指向壓縮快的開頭.這樣在范圍掃描的時候可以減少磁盤的I/O.

構(gòu)建和維護(hù)SSTable
在磁盤上維護(hù)排序結(jié)構(gòu)是可行的(B-Tree),但是放在內(nèi)存中更好操作.我們可以使用一些排序樹結(jié)構(gòu)來保證在寫入database文件段時可以按照排序的方式順序?qū)懭胛募?比如:紅黑樹,AVL等.
這個存儲引擎的工作流程如下:

• 寫入新數(shù)據(jù)優(yōu)先添加到內(nèi)存中的紅黑樹結(jié)構(gòu)中.這個結(jié)構(gòu)也叫做內(nèi)存表
• 當(dāng)內(nèi)存表到達(dá)一定規(guī)模的時候?qū)⑵渥鳛镾STable文件寫入磁盤持久化.可以按照中序遍歷的方式遍歷內(nèi)存表,達(dá)到順序?qū)懭氪疟P的目的.
• 處理讀請求的時候,優(yōu)先查看內(nèi)存表,然后在查看最新的磁盤段文件,以此類推直到找到結(jié)果或者找不到結(jié)果.
• 后臺進(jìn)程周期性的執(zhí)行合并和壓縮過程.合并多個SSTable文件時丟棄那些被刪除或者覆蓋的值.

但是這個存儲還沒有處理崩潰的問題.這里我們采用在磁盤中單獨(dú)保留操作日志的方式.該日志用來恢復(fù)內(nèi)存表,同時當(dāng)內(nèi)存表保存為SStable文件的時候,可以丟棄相應(yīng)的日志文件.

這種索引結(jié)構(gòu)被稱為:以日志結(jié)構(gòu)的合并樹命名,即LSM-Tree.

性能優(yōu)化
如果查找不存在的Key時,LSM-Tree的查找效率很低,因?yàn)樾枰粩嗷厮荼４娴亩挝募?一般采用增加一個布隆過濾器來判斷不存在的鍵.
段文件的壓縮和合并時機(jī)存在兩種策略:分層壓縮,大小分級.
大小分級是將最新的和較小的SStable文件連續(xù)合并到較舊的和較大的SSTable文件中.
分層壓縮則是鍵的范圍分裂成多個更小的SSTable文件,舊數(shù)據(jù)被移動到單獨(dú)的層級.

LSM-Tree的優(yōu)勢:
因?yàn)閷懭氪疟P是順序的,所以使用這種索引結(jié)構(gòu)的數(shù)據(jù)庫支持非常高的寫入吞吐量.

B-Tree

B-Tree幾乎是所有關(guān)系型數(shù)據(jù)庫中的標(biāo)準(zhǔn)索引實(shí)現(xiàn).
B-Tree和SSTable一樣都是保留了按鍵排序的K-V對,只是B-Tree在設(shè)計(jì)理念上跟SSTable完全不一樣.
SSTable將文件分為不同的段,但是B-Tree將數(shù)據(jù)庫分解為固定大小的頁,傳統(tǒng)上大小為4kB,頁是讀寫的最小單元.
每個頁面都可以使用地址或者位置進(jìn)行標(biāo)識,這樣可以讓一個頁面引用另一個頁面,從而可以通過這些頁面間的引用構(gòu)建一個樹狀結(jié)構(gòu).
注意:B-Tree不是一個放在內(nèi)存中的數(shù)據(jù)結(jié)構(gòu),是一個維護(hù)在磁盤上的數(shù)據(jù)結(jié)構(gòu).

在B-Tree中查找時總是從根結(jié)點(diǎn)出發(fā),然后通過比較查找key和根結(jié)點(diǎn)中的key確定下一個要去讀取的頁,然后繼續(xù)比較,直到到達(dá)葉子節(jié)點(diǎn).該葉子結(jié)點(diǎn)中的要么保存著key的值,要么保存者指向key值的頁的引用.
更新和寫入B-Tree時,如果是更新,那么先找到該key對應(yīng)的葉子頁,然后修改該頁的值,并寫回磁盤.
寫入時,需要找到其范圍包含新key的頁,并將該鍵寫入.如果這個頁中沒有足夠的空間容納這個新key,那么這個頁將分裂為兩個半滿的頁,將新key寫入分裂以后的頁,其原來的父節(jié)點(diǎn)需要更新,保存新分裂出來的頁.
這個寫入算法確保了B-Tree的平衡.降低了樹的高度,進(jìn)而減小讀取磁盤的次數(shù).
使B-Tree可靠
為了能支持崩潰后恢復(fù),B-Tree還需要引入額外的數(shù)據(jù)結(jié)構(gòu):預(yù)寫日志(WAL).也叫做重做日志.這是一個僅支持追加的文件,每個B-Tree都必須先更新WAL再修改樹本身.
還需要對并發(fā)進(jìn)行控制.通常需要使用鎖來保護(hù)書的數(shù)據(jù)結(jié)構(gòu).

優(yōu)化B-Tree

• 不使用覆蓋頁和WAL進(jìn)行崩潰恢復(fù).采用寫時復(fù)制的方案.
• 保存鍵的縮略信息,而不是完整信息,節(jié)省頁空間,支持更多的鍵,降低樹高度(B+Tree).
• 添加額外的指針到樹中.保存向左或者向右的同級指針,方便順序掃描.
• B-Tree的變體:分形樹.

B-Tree VS. LSM-Tree

LSM-Tree優(yōu)勢:

• LSM-Tree支持比B-Tree更高的寫入吞吐量.因?yàn)長SM-Tree具有較低的寫放大,同時是順序?qū)懭氪疟P.而B-Tree最少需要寫入兩次(寫WAL, 寫樹中的頁),同時對于頁的修改,即使僅修改少量的字節(jié),也必須承擔(dān)整個頁的開銷.同時B-Tree的頁不一定是順序?qū)懭氲?新增的key可能同時要更新很多個頁.
• LSM-Tree支持壓縮,并且通常比B-Tree的文件小.B-Tree由于存在分裂頁的情況,頁中某些空間無法使用,會產(chǎn)生碎片.但是LSM-Tree可以通過合并的方式消除碎片.

LSM-Tree缺點(diǎn):

• 壓縮過程中會影響讀寫操作.但是B-Tree的延遲基本上跟有確定性.
• 由于功能和壓縮合并在同時運(yùn)行,高吞吐量的時候會導(dǎo)致磁盤的帶寬被占滿,并且有可能不滿足需求.
• 因?yàn)锽-Tree每個鍵在索引中都有一個確定的位置,然而LSM-Tree則存在多個副本,如果希望提供事務(wù)語義的場景,B-Tree是更好的方案.在許多關(guān)系型數(shù)據(jù)庫中,事務(wù)隔離是通過鍵范圍傷的鎖來實(shí)現(xiàn)的,并且在B-Tree的索引中,這些所可以直接定義到樹中.

其他索引結(jié)構(gòu)

無論是LSM_Tree索引還是B-Tree索引都是KV索引,只表示了一個key到一條記錄的方式.
二級索引也是很常見的,在關(guān)系型數(shù)據(jù)庫中可以通過CREATE INDEX命令創(chuàng)建二級索引.但是二級索引中一個Key可能對應(yīng)多條記錄.一般有兩種解決方案: 1. 在索引中針對key保存一個鏈表,每個鏈表對應(yīng)一條記錄的位置. 2. 通過追加一些標(biāo)識使每個鍵變得唯一.無論采用哪種方式,LSM-Tree和B-Tree都是可用的數(shù)據(jù)結(jié)構(gòu).

在有些場景中,通過索引找到對應(yīng)記錄的保存位置,然后在讀取這個文件對應(yīng)的位置獲取記錄增加了耗時,對于某些讀取場景不可接受,那么我們可以考慮在索引中直接保存對應(yīng)的值,這樣做的索引叫做聚集索引.MySQL中InnoDB存儲引擎中,主鍵的索引就是聚集索引.
這里有一點(diǎn)需要注意:增加索引僅能提升讀取效率,對應(yīng)的會增加寫操作的負(fù)擔(dān).

多列索引
在查詢多列數(shù)據(jù)的時候,我們需要多列索引.例如需要同時查詢表的多個列.
一種最常見的做法是級聯(lián)索引.他通過將一列追加到另外一列,將幾個字段組合成一個鍵.由于存在級聯(lián)的問題,所以按照非索引級聯(lián)的順序查詢會遇到問題.
另外一種做法是采用多維索引.多維索引可以使用R樹來實(shí)現(xiàn).

模糊索引
無論是單列索引還是多列索引都不能支持模糊查詢的操作.在Lucene中采用了一種索引結(jié)構(gòu)用來支持模糊查詢.這種索引是鍵中字符序列的有限狀態(tài)自動機(jī),類似于字典樹.

內(nèi)存中保存所有內(nèi)容
目前還有一種完全基于內(nèi)存的數(shù)據(jù)庫.這種數(shù)據(jù)庫一般用于緩存的處理.針對緩存的使用場景是不需要考慮崩潰恢復(fù)的.應(yīng)用代碼會幫助進(jìn)行緩存重建.
但是有一些內(nèi)存數(shù)據(jù)庫也是支持持久化的,一般采用如下方案:

1. 使用特殊硬件結(jié)構(gòu)供電.
2. 將更改記錄寫入磁盤
3. 定期保存快照到磁盤
4. 復(fù)制內(nèi)存中的狀態(tài)到其他機(jī)器等.
   盡管有些內(nèi)存數(shù)據(jù)庫會寫入磁盤,但是磁盤僅記錄了追加日志用于崩潰后恢復(fù).
   Redis和Couchbase通過一部寫入磁盤提供較弱的持久化.

內(nèi)存數(shù)據(jù)庫一般比基于磁盤的數(shù)據(jù)庫要更快,而且支持更多的數(shù)據(jù)結(jié)構(gòu)類型.
但是內(nèi)存數(shù)據(jù)庫快的原因并不在于不需要讀取磁盤,而是他們避免了使用寫磁盤的格式對內(nèi)存數(shù)據(jù)結(jié)構(gòu)編碼的開銷. 例如:使用SSTable的數(shù)據(jù)庫,需要在內(nèi)存中維護(hù)一顆平衡樹以便在寫磁盤的時候可以按照SSTable的要求寫入磁盤.

考慮操作系統(tǒng)的內(nèi)存管理方式,基于內(nèi)存的數(shù)據(jù)庫也可以使用類似的方式,通過將最近最少使用的記錄寫入磁盤,在讀取時重新從磁盤讀入內(nèi)存中,來突破內(nèi)存容量的限制.但是這里有一個前提:索引必須完整的保存在內(nèi)存中.

事務(wù)處理與分析處理

事務(wù),主要指組成一個邏輯單元的一組讀寫操作.
分為兩類:

1. 根據(jù)索引中的鍵查詢少量的數(shù)據(jù),然后根據(jù)用戶的輸入插入或者更新這些數(shù)據(jù)-在線事務(wù)處理(OLTP)
2. 查詢大量的數(shù)據(jù),每個記錄只讀取少量的列,并計(jì)算匯總統(tǒng)計(jì)信息(如,計(jì)數(shù),求和,平均值等)-在線分析處理(OLAP)

我們來對比下這兩種事務(wù)的特點(diǎn):

為了針對OLAP進(jìn)行優(yōu)化和支持,現(xiàn)在一般是通過數(shù)據(jù)倉庫進(jìn)行存儲和查詢數(shù)據(jù).

數(shù)據(jù)倉庫
傳統(tǒng)的數(shù)據(jù)也是支持進(jìn)行OLAP的,但是因?yàn)镺LAP需要進(jìn)行ETL(提取-轉(zhuǎn)換-導(dǎo)入)操作,很有可能影響線上應(yīng)用服務(wù)的OLTP服務(wù),所以我們使用一個稱為數(shù)據(jù)倉庫的數(shù)據(jù)庫為OLAP提供支持.
分離OLTP和OLAP事務(wù)使用的數(shù)據(jù)庫一個很大的優(yōu)勢就是我們可以根據(jù)OLAP的特點(diǎn)對其進(jìn)行優(yōu)化了.

數(shù)據(jù)倉庫數(shù)據(jù)組織模式

• 星型與雪花型分析模式
  星型模式是數(shù)據(jù)倉庫最基本的數(shù)據(jù)管理方式,也叫做維度建模.這種模式的中心是一張事實(shí)表,事實(shí)表的每一行表示在特定時間發(fā)生的事件.事實(shí)表有一些列會使用其他表的外鍵,這些列被叫做維度,那些被引用的表叫做維度表.
  星型模式來源與這個建模方式,當(dāng)數(shù)據(jù)可視化的時候,事實(shí)表被放在中心的位置,維度表分散在事實(shí)表周圍構(gòu)成星型.
  該模式的一個變體叫做雪花模式,雪花模式就是在星型模式的基礎(chǔ)上,將維度表進(jìn)一步細(xì)分子空間.
  一般事實(shí)表是一張比較寬的表,一般超過100列.維度表也可能會非常寬.但是在進(jìn)行數(shù)據(jù)分析的查詢時,我們可能只需要查詢幾列,但是星型模式下我們需要訪問大量的行(包含所有列),然后僅輸出指定的列.這樣就引出了下面的存儲方式.
• 列式存儲
  列式存儲的思路是:不要將一行中的所有值存儲在一起,而是將每列中的所有值存儲在一起.如果每一列的數(shù)據(jù)都單獨(dú)保存為文件,那么查詢的時候僅需要掃描對應(yīng)列的文件即可.
  列式存儲有一個隱形的約定:每個列式存儲的文件中都以相同的順序保存著數(shù)據(jù)行.這樣我們才可以從列存儲中重建每一行的數(shù)據(jù).

列壓縮
采用列式存儲以后,我們可以通過位圖編碼的方式對保存的數(shù)據(jù)進(jìn)行壓縮.
例如:
fact_sales表

列式存儲磁盤布局:

date_key文件內(nèi)容: 140102,140102,140102,140102,140103,140103,140103,140103
product_sk文件內(nèi)容: 69,69,69,74,31,31,31,31
store_sk文件內(nèi)容:4,5,5,3,2,3,3,8

使用位圖編碼壓縮以后:

product_sk列值: 69,69,69,74,31,31,31,31
product_sk=69: 11100000
product_sk=74: 00010000
product_sk=31: 00001111
使用更為緊密的壓縮:游程編碼 (8位的情況)
product_sk=31: 4,4 (4個0, 4個1)
product_sk=69: 0,3 (0個0, 3個1,剩下為0)
product_sk=74: 3,1 (3個0, 1個1, 剩下為0)

在使用位圖編碼以后,加入要查詢:

WHERE product_sk in (31, 69);

則只需要product_sk=31和product_sk=69兩個向量執(zhí)行按位或操作.
這樣的位圖編碼壓縮可以用在索引當(dāng)中,同時加快讀取的速度.
將這樣的索引放在內(nèi)存中,我們可以把壓縮以后的列數(shù)據(jù)塊放在cpu的緩存當(dāng)中,同時使用迭代訪問,加速數(shù)據(jù)的讀取.

列存儲中的排序
首先有一個前提:單獨(dú)對列存儲的某一列進(jìn)行排序是沒有意義的.這會打破列存儲的約定.
但是排序可以帶來更好的讀取速度.如果數(shù)據(jù)是有序的,那么在查詢的時候可能就不需要掃描所有的元數(shù)據(jù)了.
但是這給寫入帶來了困難.
考慮前面提到的LSM-Tree,我們可以在內(nèi)存中保存一個有序的內(nèi)存表,然后在達(dá)到閾值的時候?qū)懭肓写鎯Υ疟P.內(nèi)存中的這個有序結(jié)構(gòu)是面向行的還是面向列的是無所謂的事情.然后我們可以在后臺執(zhí)行列文件的合并,并批量寫入新的文件.
在查詢的時候需要查看磁盤上的數(shù)據(jù)和內(nèi)存中最近寫入的數(shù)據(jù),并且合并處理.

聚合:數(shù)據(jù)立方體和物化視圖

在進(jìn)行數(shù)據(jù)分析的時候經(jīng)常會使用一些聚合函數(shù),例如SQL提供的count,sum,avg等.如果每次查詢時都需要通過原始數(shù)據(jù)才能得到,會帶來不必要的時間損耗.我們可以先緩存這些常用的聚合數(shù)據(jù),這種緩存的方式被叫做物化視圖.物化視圖在關(guān)系型數(shù)據(jù)庫中被定義為標(biāo)準(zhǔn)視圖:一個類似表的對象,其內(nèi)容為一些查詢結(jié)果.
因?yàn)槲锘晥D依賴原始數(shù)據(jù)而得到結(jié)果,所以當(dāng)原始數(shù)據(jù)發(fā)生變化的時候物化視圖也需要變.
物化視圖一個常見的特例是數(shù)據(jù)立方體:它是由不同維度分組的聚合網(wǎng)格.
例如:

上面就是一個數(shù)據(jù)立方體的例子,可以按照這張表的行或者列得到去掉一個維度的總和.其中每一個單元格都是data-product組合的所有事實(shí)屬性的聚合(這里是sum)
不只是對于兩個維度,針對任意維度我們都可以創(chuàng)建這樣一份數(shù)據(jù)立方體,只是我們不是很容易理解.
數(shù)據(jù)立方體的優(yōu)勢:某些查詢會非程饣快,相當(dāng)于使用了緩存.
缺點(diǎn)也很明顯,數(shù)據(jù)立方體沒有原始數(shù)據(jù)帶來的靈活性.