注：書本鏈接：GitHub - Vonng/ddia: 《Designing Data-Intensive Application》DDIA中文翻譯
注：譯者文本網(wǎng)站：簡(jiǎn)介 · ddia-cn
注：如有侵權(quán)俩莽，請(qǐng)聯(lián)系刪除

第三章：存儲(chǔ)與檢索

在 第二章 中幻妓，我們討論了數(shù)據(jù)模型和查詢語(yǔ)言巧号，即程序員將數(shù)據(jù)錄入數(shù)據(jù)庫(kù)的格式，以及再次要回?cái)?shù)據(jù)的機(jī)制混驰。在本章中我們會(huì)從數(shù)據(jù)庫(kù)的視角來(lái)討論同樣的問(wèn)題：數(shù)據(jù)庫(kù)如何存儲(chǔ)我們提供的數(shù)據(jù)，以及如何在我們需要時(shí)重新找到數(shù)據(jù)。

針對(duì) 事務(wù)性 負(fù)載優(yōu)化的和針對(duì) 分析性 負(fù)載優(yōu)化的存儲(chǔ)引擎之間存在巨大差異渊季。

注：我覺(jué)得這兩個(gè)概念與OLAP（在線分析處理）、OLTP（在線事務(wù)處理）是一致的审残。

日志結(jié)構(gòu)（log-structured） 的存儲(chǔ)引擎梭域，以及 面向頁(yè)面（page-oriented） 的存儲(chǔ)引擎（例如 B 樹）。

1搅轿、驅(qū)動(dòng)數(shù)據(jù)庫(kù)的數(shù)據(jù)結(jié)構(gòu)

許多數(shù)據(jù)庫(kù)在內(nèi)部使用了 日志（log）病涨，也就是一個(gè) 僅追加（append-only） 的數(shù)據(jù)文件。

（1）散列索引

• 鍵值數(shù)據(jù)（key-value Data）

• 散列映射（hash map） 或 散列表（hash table）

• 段（segment）

• 壓縮（compaction）

（2）SSTables和LSM樹

• 排序字符串表（Sorted String Table）

現(xiàn)在我們可以讓我們的存儲(chǔ)引擎以如下方式工作：

• 有新寫入時(shí)璧坟，將其添加到內(nèi)存中的平衡樹數(shù)據(jù)結(jié)構(gòu)（例如紅黑樹）既穆。這個(gè)內(nèi)存樹有時(shí)被稱為 內(nèi)存表（memtable）。

• 當(dāng) 內(nèi)存表 大于某個(gè)閾值（通常為幾兆字節(jié)）時(shí)雀鹃，將其作為 SSTable 文件寫入硬盤幻工。這可以高效地完成，因?yàn)闃湟呀?jīng)維護(hù)了按鍵排序的鍵值對(duì)黎茎。新的 SSTable 文件將成為數(shù)據(jù)庫(kù)中最新的段囊颅。當(dāng)該 SSTable 被寫入硬盤時(shí)，新的寫入可以在一個(gè)新的內(nèi)存表實(shí)例上繼續(xù)進(jìn)行。

• 收到讀取請(qǐng)求時(shí)踢代，首先嘗試在內(nèi)存表中找到對(duì)應(yīng)的鍵盲憎，如果沒(méi)有就在最近的硬盤段中尋找，如果還沒(méi)有就在下一個(gè)較舊的段中繼續(xù)尋找胳挎，以此類推饼疙。

• 時(shí)不時(shí)地，在后臺(tái)運(yùn)行一個(gè)合并和壓縮過(guò)程慕爬，以合并段文件并將已覆蓋或已刪除的值丟棄掉窑眯。

日志結(jié)構(gòu)合并樹（或 LSM 樹）

基于這種合并和壓縮排序文件原理的存儲(chǔ)引擎通常被稱為 LSM 存儲(chǔ)引擎。

Lucene医窿，是一種全文搜索的索引引擎磅甩，在 Elasticsearch 和 Solr 被使用，它使用類似的方法來(lái)存儲(chǔ)它的關(guān)鍵詞詞典【12,13】留搔。全文索引比鍵值索引復(fù)雜得多更胖，但是基于類似的想法：在搜索查詢中，由一個(gè)給定的單詞隔显，找到提及單詞的所有文檔（網(wǎng)頁(yè)却妨、產(chǎn)品描述等）。這也是通過(guò)鍵值結(jié)構(gòu)實(shí)現(xiàn)的：其中鍵是 單詞（term）括眠，值是所有包含該單詞的文檔的 ID 列表（postings list）彪标。在 Lucene 中，從詞語(yǔ)到記錄列表的這種映射保存在類似于 SSTable 的有序文件中掷豺，并根據(jù)需要在后臺(tái)執(zhí)行合并【14】捞烟。

（3）B樹

我們前面看到的日志結(jié)構(gòu)索引將數(shù)據(jù)庫(kù)分解為可變大小的段，通常是幾兆字節(jié)或更大的大小当船，并且總是按順序?qū)懭攵翁饣Ｏ啾戎拢珺 樹將數(shù)據(jù)庫(kù)分解成固定大小的 塊（block） 或 分頁(yè)（page）德频，傳統(tǒng)上大小為 4KB（有時(shí)會(huì)更大）苍息，并且一次只能讀取或?qū)懭胍粋€(gè)頁(yè)面。這種設(shè)計(jì)更接近于底層硬件壹置，因?yàn)橛脖P空間也是按固定大小的塊來(lái)組織的竞思。

• 分支因子（branching factor）

• 預(yù)寫式日志（WAL，即 write-ahead log钞护，也稱為 重做日志盖喷，即 redo log）

• 鎖存器（latches，輕量級(jí)鎖）

（4）比較B樹和LSM樹

• 寫入放大（write amplification）：在數(shù)據(jù)庫(kù)的生命周期中每筆數(shù)據(jù)導(dǎo)致對(duì)硬盤的多次寫入

2难咕、其他索引結(jié)構(gòu)

（1）將值存儲(chǔ)在索引中

• 堆文件（heap file）

在 聚集索引（在索引中存儲(chǔ)所有的行數(shù)據(jù)）和 非聚集索引（僅在索引中存儲(chǔ)對(duì)數(shù)據(jù)的引用）之間的折衷被稱為 覆蓋索引（covering index） 或 包含列的索引（index with included columns）课梳，其在索引內(nèi)存儲(chǔ)表的一部分列【33】距辆。這允許通過(guò)單獨(dú)使用索引來(lái)處理一些查詢（這種情況下，可以說(shuō)索引 覆蓋（cover） 了查詢）【32】惦界。

（2）多列索引

• 最常見(jiàn)的多列索引被稱為 連接索引（concatenated index）

注：這個(gè)就是Mysql Innodb中的復(fù)合索引

• 多維索引（multi-dimensional index） 是一種查詢多個(gè)列的更一般的方法挑格，這對(duì)于地理空間數(shù)據(jù)尤為重要。

• 空間填充曲線（space-filling curve） 將二維位置轉(zhuǎn)換為單個(gè)數(shù)字沾歪，然后使用常規(guī) B 樹索引。

（3）全文搜索和模糊索引

（4）在內(nèi)存中存儲(chǔ)一切

• 反緩存（anti-caching）：通過(guò)在內(nèi)存不足的情況下將最近最少使用的數(shù)據(jù)從內(nèi)存轉(zhuǎn)移到硬盤雾消，并在將來(lái)再次訪問(wèn)時(shí)將其重新加載到內(nèi)存中灾搏。

注：例如redis的內(nèi)存淘汰策略

• 非易失性存儲(chǔ)器（non-volatile memory, NVM）

3、事務(wù)處理還是分析立润？

數(shù)據(jù)倉(cāng)庫(kù)（data warehouse）

（1）數(shù)據(jù)倉(cāng)庫(kù)

• 將數(shù)據(jù)存入倉(cāng)庫(kù)的過(guò)程稱為 “抽取 - 轉(zhuǎn)換 - 加載（ETL）”

（2）星型和雪花型：分析的模式

4狂窑、列式存儲(chǔ)

（1）列壓縮

（2）內(nèi)存帶寬和矢量化處理

（3）列式存儲(chǔ)中的排序順序

• 幾個(gè)不同的排序順序

（4）寫入列式存儲(chǔ)

（5）聚合：數(shù)據(jù)立方體和物化視圖

• 物化視圖（Materialized View）

本章小結(jié)

在本章中，我們?cè)噲D深入了解數(shù)據(jù)庫(kù)是如何處理存儲(chǔ)和檢索的桑腮。將數(shù)據(jù)存儲(chǔ)在數(shù)據(jù)庫(kù)中會(huì)發(fā)生什么泉哈？稍后再次查詢數(shù)據(jù)時(shí)數(shù)據(jù)庫(kù)會(huì)做什么？

在高層次上破讨，我們看到存儲(chǔ)引擎分為兩大類：針對(duì) 事務(wù)處理（OLTP） 優(yōu)化的存儲(chǔ)引擎和針對(duì) 在線分析（OLAP） 優(yōu)化的存儲(chǔ)引擎丛晦。這兩類使用場(chǎng)景的訪問(wèn)模式之間有很大的區(qū)別：

• OLTP 系統(tǒng)通常面向最終用戶，這意味著系統(tǒng)可能會(huì)收到大量的請(qǐng)求提陶。為了處理負(fù)載烫沙，應(yīng)用程序在每個(gè)查詢中通常只訪問(wèn)少量的記錄。應(yīng)用程序使用某種鍵來(lái)請(qǐng)求記錄隙笆，存儲(chǔ)引擎使用索引來(lái)查找所請(qǐng)求的鍵的數(shù)據(jù)锌蓄。硬盤查找時(shí)間往往是這里的瓶頸。

• 數(shù)據(jù)倉(cāng)庫(kù)和類似的分析系統(tǒng)會(huì)少見(jiàn)一些撑柔，因?yàn)樗鼈冎饕蓸I(yè)務(wù)分析人員使用瘸爽，而不是最終用戶。它們的查詢量要比 OLTP 系統(tǒng)少得多铅忿，但通常每個(gè)查詢開(kāi)銷高昂剪决，需要在短時(shí)間內(nèi)掃描數(shù)百萬(wàn)條記錄。硬盤帶寬（而不是查找時(shí)間）往往是瓶頸辆沦，列式存儲(chǔ)是針對(duì)這種工作負(fù)載的日益流行的解決方案昼捍。

在 OLTP 這一邊，我們能看到兩派主流的存儲(chǔ)引擎：

• 日志結(jié)構(gòu)學(xué)派：只允許追加到文件和刪除過(guò)時(shí)的文件肢扯，但不會(huì)更新已經(jīng)寫入的文件妒茬。Bitcask、SSTables蔚晨、LSM 樹乍钻、LevelDB肛循、Cassandra、HBase银择、Lucene 等都屬于這個(gè)類別多糠。

• 就地更新學(xué)派：將硬盤視為一組可以覆寫的固定大小的頁(yè)面。B 樹是這種理念的典范浩考，用在所有主要的關(guān)系數(shù)據(jù)庫(kù)和許多非關(guān)系型數(shù)據(jù)庫(kù)中夹孔。

日志結(jié)構(gòu)的存儲(chǔ)引擎是相對(duì)較新的技術(shù)。他們的主要想法是析孽，通過(guò)系統(tǒng)性地將隨機(jī)訪問(wèn)寫入轉(zhuǎn)換為硬盤上的順序?qū)懭氪钌耍捎谟脖P驅(qū)動(dòng)器和固態(tài)硬盤的性能特點(diǎn)，可以實(shí)現(xiàn)更高的寫入吞吐量袜瞬。

關(guān)于 OLTP怜俐，我們最后還介紹了一些更復(fù)雜的索引結(jié)構(gòu)，以及針對(duì)所有數(shù)據(jù)都放在內(nèi)存里而優(yōu)化的數(shù)據(jù)庫(kù)邓尤。

然后拍鲤，我們暫時(shí)放下了存儲(chǔ)引擎的內(nèi)部細(xì)節(jié)，查看了典型數(shù)據(jù)倉(cāng)庫(kù)的高級(jí)架構(gòu)汞扎，并說(shuō)明了為什么分析工作負(fù)載與 OLTP 差別很大：當(dāng)你的查詢需要在大量行中順序掃描時(shí)季稳，索引的重要性就會(huì)降低很多。相反佩捞，非常緊湊地編碼數(shù)據(jù)變得非常重要绞幌，以最大限度地減少查詢需要從硬盤讀取的數(shù)據(jù)量。我們討論了列式存儲(chǔ)如何幫助實(shí)現(xiàn)這一目標(biāo)一忱。

作為一名應(yīng)用程序開(kāi)發(fā)人員莲蜘，如果你掌握了有關(guān)存儲(chǔ)引擎內(nèi)部的知識(shí)，那么你就能更好地了解哪種工具最適合你的特定應(yīng)用程序帘营。當(dāng)你調(diào)整數(shù)據(jù)庫(kù)的優(yōu)化參數(shù)時(shí)票渠，這種理解讓你能夠設(shè)想增減某個(gè)值會(huì)產(chǎn)生怎樣的效果。

盡管本章不能讓你成為一個(gè)特定存儲(chǔ)引擎的調(diào)參專家芬迄，但它至少大概率使你有了足夠的概念與詞匯儲(chǔ)備去讀懂你所選擇的數(shù)據(jù)庫(kù)的文檔问顷。