安裝目錄插件臀蛛，閱讀體驗(yàn)更佳＝谩Ｋ敛丁颖变！
參考：http://www.reibang.com/p/a40ec70d9365

第一部分：【數(shù)據(jù)庫(kù)理論基礎(chǔ)】數(shù)據(jù)庫(kù)歷史演進(jìn)與未來(lái)展望

一掌实、時(shí)間軸

1. 導(dǎo)航型數(shù)據(jù)庫(kù)：

• IDS數(shù)據(jù)庫(kù)（網(wǎng)狀模型陪蜻，1964年，GE）
  優(yōu)點(diǎn)：更接近現(xiàn)實(shí)贱鼻、性能良好宴卖；
  缺點(diǎn)：結(jié)構(gòu)復(fù)雜，存取路徑對(duì)用戶不透明

• IMS數(shù)據(jù)庫(kù)（層次模型邻悬，1966年症昏，IBM）
  優(yōu)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單、查詢效率高
  缺點(diǎn)：不適用于現(xiàn)實(shí)世界父丰、查詢必須依賴父節(jié)點(diǎn)

2. 關(guān)系型數(shù)據(jù)庫(kù)：（1977年第一次數(shù)據(jù)庫(kù)大戰(zhàn)）

• IBMSystem R（1974年肝谭，IBM）
• Ingres（1977年）
• Oracle（1979年，關(guān)系型數(shù)據(jù)庫(kù)商業(yè)化開啟）
• IBM DB2（1983年蛾扇，IBM）
• Sybase SQL Server（1987年攘烛，Sybase和微軟合作）
• MS SQL Server（1989年，微軟買下了Sybase的代碼版權(quán)）
• PostgreSQL（1989年）
• MySQL（1995年）
• MonetDB（2004年）
• CStore（2004年）

3. NoSQL：（第二次數(shù)據(jù)庫(kù)大戰(zhàn)）

• 問(wèn)題：傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)采用集中式架構(gòu)镀首，沒法解決傳統(tǒng)互聯(lián)網(wǎng)時(shí)代的可擴(kuò)展和高并發(fā)問(wèn)題坟漱，因而數(shù)據(jù)庫(kù)逐漸進(jìn)入分布式和云時(shí)代，先說(shuō)下分布式系統(tǒng)（這是一個(gè)比較古老的領(lǐng)域蘑斧，直到最近一二十年才有機(jī)會(huì)從理論走向大規(guī)模工程實(shí)踐）
• 對(duì)于OLTP(online transaction processing) - 主要解決事務(wù)的處理能力靖秩。NoSQL弱一致性须眷，缺乏標(biāo)準(zhǔn)化竖瘾；擴(kuò)展性好，靈活- SQL 擴(kuò)展性查花颗，預(yù)定義schema捕传；強(qiáng)一致性
• 對(duì)于OLAP(online analytical processing) - 主要解決事務(wù)的查詢分析能力。MapReduce 用于數(shù)據(jù)分析扩劝，不是一個(gè)完整的數(shù)據(jù)庫(kù)系統(tǒng)庸论，催生了Spark，Hive
• Distributed/ Cloud DBMS ~2000s傳統(tǒng)數(shù)據(jù)庫(kù)有擴(kuò)展性棒呛，和高并發(fā)問(wèn)題

分布式系統(tǒng)：

• Google GFS（2003年聂示，解決分布式文件系統(tǒng)的問(wèn)題）

• Google MapReduce（2004年，解決如果在分布式文件系統(tǒng)和分布式KVS上面如何做分布式計(jì)算和分析的問(wèn)題）

• Google BigTable（2006年簇秒，解決分布式KV存儲(chǔ)問(wèn)題鱼喉， 弱化了強(qiáng)一致性，以換取強(qiáng)擴(kuò)展性）

  • 谷歌之所以產(chǎn)生這三個(gè)系統(tǒng)，是因?yàn)閿?shù)據(jù)強(qiáng)一致性對(duì)系統(tǒng)的水平擴(kuò)展扛禽，以及海量數(shù)據(jù)爆發(fā)式增長(zhǎng)的分析能力出現(xiàn)了斷層锋边，為了解決這個(gè)問(wèn)題，將數(shù)據(jù)強(qiáng)一致性的需求給弱化了编曼，換來(lái)能夠使用分布式的集群來(lái)做水平擴(kuò)展豆巨，谷歌這三個(gè)件發(fā)布后，衍生出了NoSQL掐场，也即Not Only SQL往扔，針對(duì)非結(jié)構(gòu)化、半結(jié)構(gòu)化的海量數(shù)據(jù)的處理系統(tǒng)熊户，出現(xiàn)了這第一代SQL

• HadooP（2005年瓤球，這個(gè)項(xiàng)目初衷就是要做出谷歌這三大件的開源實(shí)現(xiàn)）

• Amazon Dynamo（2007年，涉及思想是P2P技術(shù)敏弃，因?yàn)闆]有保證強(qiáng)一致性卦羡，沒有成為主流Spark（2009年）

• OceanBase（2010年，國(guó)內(nèi)分布式數(shù)據(jù)庫(kù)的翹楚）

• Windows Azure Storage（2011年麦到，微軟）

• Google Spanner（2012年绿饵，標(biāo)志著分布式數(shù)據(jù)庫(kù)進(jìn)入第二代）

• Amazon Aurora（2015年，運(yùn)行在公有云上瓶颠，將計(jì)算與存儲(chǔ)分離拟赊，從而實(shí)現(xiàn)存儲(chǔ)能力的可擴(kuò)展，設(shè)計(jì)思想the log is the database粹淋，和Google Spanner成為第二代的兩個(gè)流派）

• TiDB（2016年吸祟，國(guó)產(chǎn)數(shù)據(jù)庫(kù)）

• ByteSQL、ByteNDB（2020年桃移，字節(jié)跳動(dòng)）

二屋匕、百家爭(zhēng)鳴 - 各種數(shù)據(jù)庫(kù)版本與名家

百家爭(zhēng)鳴

三、星辰大海 - 數(shù)據(jù)庫(kù)未來(lái)的發(fā)展方向

• Hardware：軟硬件一體的研發(fā)
• Deployment：多寫架構(gòu),AI/ML (Adaptive Columnar/Row store switch,Adaptive Indexing,Adaptive Query Optimization)借杰，Edge 邊緣計(jì)算,Cloud 云計(jì)算 與安全
• Scalability：事務(wù)處理过吻，查詢優(yōu)化，高可用
• Data Model：多種存儲(chǔ)方式蔗衡，多種查詢接口纤虽，標(biāo)準(zhǔn) （SQL, KV, Doc, Graph, Time-series)，OLTP/OLAP融合

第二部分：【數(shù)據(jù)庫(kù)理論基礎(chǔ)】SQL 查詢引擎概述-關(guān)系模型與查詢優(yōu)化

一绞惦、SQL 語(yǔ)句分類

關(guān)系模型->關(guān)系代數(shù)（過(guò)程式）->SQL（聲明式）

SQL 語(yǔ)句分類

二逼纸、查詢流程概述

SQL->AST->Logical Plan Tree->Physical Plan Tree

查詢流程

三、基于規(guī)則的查詢優(yōu)化

基于關(guān)系代數(shù)等價(jià)性進(jìn)行邏輯變換济蝉，減少無(wú)用開銷

• 關(guān)系代數(shù)等價(jià)：關(guān)系代數(shù)表達(dá)式生成相同的結(jié)果集
• 依據(jù)關(guān)系代數(shù)的等價(jià)交換原則做一些邏輯變換
• 謂詞下推：1) 盡可能早地進(jìn)行過(guò)濾杰刽；2) 分解復(fù)雜的謂詞條件呻纹，下推；3) 分解連接條件专缠，笛卡爾積轉(zhuǎn)Join計(jì)算
• 投影下推：提前做投影雷酪，去除不需要的列信息
• 排序、Limit涝婉、聚合下推
• 投影消除：如果子集投影和投影操作相同哥力，則消除投影操作
• 排序消除：如果子集結(jié)果排序和排序操作相同，則消除排序操作

四墩弯、基于代價(jià)的查詢優(yōu)化

基于統(tǒng)計(jì)信息進(jìn)行代價(jià)搜索吩跋，選擇最優(yōu)的物理執(zhí)行計(jì)劃

第三部分：【數(shù)據(jù)庫(kù)理論基礎(chǔ)】SQL 查詢引擎概述 - 執(zhí)行引擎

一、查詢流程和表達(dá)式

1. 查詢流程

查詢的過(guò)程：SQL語(yǔ)句->查詢計(jì)劃->查詢結(jié)果

2. 查詢計(jì)劃

查詢計(jì)劃描述了執(zhí)行的動(dòng)作渔工，通過(guò)以下方式進(jìn)行描述

1. 運(yùn)算符（Operator）：Projection\TopK\Sort\Filter(Select)\HashJoin\Aggregation\TableScan...
2. 表達(dá)式（Expression）：R.id, S.id, S.age \ age >= 20 \ COUNT(S.id) + 1, AVG(S.age) <= 50 \ R.id = S.id \ ...
3. 運(yùn)算符中包含表達(dá)式

查詢計(jì)劃示例圖

3. 表達(dá)式（Expression）

3.1 表達(dá)式類型：常量锌钮，元組屬性引用，標(biāo)量函數(shù)引矩，聚合函數(shù)

• 常量（Constant）：表達(dá)式中的常量值
• 元組屬性引用（Tuple Atribute Ref）：引用表中某個(gè)屬性的值
• 標(biāo)量函數(shù)（Scalar Function）：比較（,!=,>=,<=,in..）梁丘；邏輯 （AND,OR, XOR, NOT..）；算術(shù) (AND, SUB, MUL, DIV, MOD ..)旺韭；內(nèi)置函數(shù)（Buildin Function）氛谜；自定義函數(shù)（UDF）
• 聚合函數(shù)（Agg Function）：COUNT，MAX, MIN, SUM, AVG

表達(dá)式示例

3.2 表達(dá)式求值

整體是自底向上求值区端，分為 元組屬性求值值漫、標(biāo)量函數(shù)求值、聚合函數(shù)求值 三種：

• 元組屬性求值：輸入一個(gè)元組织盼，輸出元組中對(duì)應(yīng)屬性的值杨何；
• 標(biāo)量函數(shù)求值：Row Style 輸入一個(gè)元組，輸出一個(gè)標(biāo)量沥邻；Block Style 輸入一個(gè) Block术吝，輸出一個(gè) vector译柏；
• 聚合函數(shù)求值：Initialize 初始化聚合狀態(tài)厌漂；Update 根據(jù)當(dāng)前的 Tuple 更新聚合狀態(tài)号阿；Finalize 計(jì)算聚合最終狀態(tài)

聚合函數(shù)求值示例

二、常見運(yùn)算符

表達(dá)式和運(yùn)算符都是查詢計(jì)劃的一部分芦瘾，但是運(yùn)算符內(nèi)容比較多，所以單獨(dú)放一個(gè)章節(jié)

1. 排序（Sorting）

排序是查詢執(zhí)行中的基本算法集畅，在多個(gè)場(chǎng)景中使用近弟，Order by, group by, sortmerge join
排序類型：1) 內(nèi)存排序(In-memory sorting) 快排、堆排挺智、歸并排序等祷愉；2) 外部歸并排序( External Merge sorting) IO代價(jià)評(píng)估、兩路外部歸并、K路外部歸并二鳄。

2. 聚合（Aggregation）

聚合定義：將多個(gè)元組按照指定的聚合函數(shù)赴涵，生成一組聚合結(jié)果 。聚合經(jīng)常和分組（Grouping）操作配合使用订讼，在組內(nèi)聚合髓窜。
聚合的實(shí)現(xiàn)方式：流式聚合；哈希聚合欺殿。（具體使用什么方式是優(yōu)化器來(lái)決定的）

流式聚合操作流程：

• 對(duì)元組按照分組表達(dá)式求值寄纵，按結(jié)果排序；
• 順序掃描脖苏，對(duì)每個(gè)元組進(jìn)行聚合表達(dá)式求值程拭。

流式聚合適用場(chǎng)景：

• 聚合前數(shù)據(jù)已經(jīng)按照分組表達(dá)式有序
  • 分組列上存在索引
  • 上游運(yùn)算符按照分組列做了排序
• 要求聚合后的數(shù)據(jù)按照分組表達(dá)式有序

流式聚合操作示例

哈希聚合操作流程：

• 將元組以分組值為key，判斷hashtable是否存在該key對(duì)應(yīng)的聚合結(jié)果棍潘。
• 如果存在恃鞋，則將元組按照聚合函數(shù)合并到聚合結(jié)果中 (Update)
• 如果不存在，則以元組的分組值為Key在HashTable中創(chuàng)建一條新記錄 (Initialize)亦歉，再合并元組到初始化的聚合結(jié)果中 (Update）

哈希聚合操作示例

3. 連接（Join）

連接定義：將多表中符合條件的行連接成一行山宾。
為什么需要Join？：在數(shù)據(jù)庫(kù)建模階段鳍徽，將不同的實(shí)體創(chuàng)建獨(dú)立的表资锰；在查詢階段，獲取具有關(guān)聯(lián)關(guān)系的多個(gè)表的數(shù)據(jù)阶祭。
Join類型：分為 Inner join绷杜，Left Outer Join， Right Outer Join濒募。
實(shí)現(xiàn)算法：Nested Loop Join鞭盟，Sort Merge Join，Hash Join

• Join-Nested Loop Join：最簡(jiǎn)單瑰剃，兩次 for 循環(huán)遍歷兩個(gè)表齿诉。實(shí)現(xiàn)簡(jiǎn)單，適用于等值和非等值的Join條件晌姚，但是性能較差

Nested Loop Join 示例

• Join-Sort Merge Join：兩個(gè)階段：Sort階段和Merge階段粤剧，先將兩個(gè)表按照 Join Key 進(jìn)行排序，然后順序掃描排序后的表挥唠，根據(jù) Join 條件作出 Merge 的輸出抵恋。要求輸入表在 Join Key 上有序、輸出結(jié)果要求在 Join Key 上有序

Sort Merge Join 示例

• Join-Hash Join(1)：兩個(gè)階段：Build階段和Probe階段宝磨，先掃描左表創(chuàng)建內(nèi)存 Hash Table弧关，然后掃描右表盅安，查詢 Join Key 在 Hash Table 中是否存在并輸出結(jié)果。要求輸入表在 Join Key 上無(wú)序世囊，分布均衡别瞭、對(duì)輸出結(jié)果沒有順序要求、等值Join條件株憾。一般情況下將小表作為左表蝙寨。

Hash Join 示例

• Join-Grace Hash Join(2)：兩個(gè)階段：Parition階段和Probe階段，先分別掃描左表和右表号胚，按照 Hash Key 映射到不同分區(qū)籽慢，然后分別掃描兩表對(duì)應(yīng)的分區(qū)，做內(nèi)存 Join猫胁。適用于小表的數(shù)據(jù)量太大無(wú)法在內(nèi)存中創(chuàng)建Hash Table的情況箱亿。

Grace Hash Join 示例

4. 訪問(wèn)路徑（Access Path）

訪問(wèn)路徑：從關(guān)系表中讀取數(shù)據(jù)的方式 (從存儲(chǔ)中讀取數(shù)據(jù))，分為：Sequential Scan 全表掃描弃秆；Index Scan 索引掃描届惋；Multi-Index Scan 多索引聯(lián)合掃描。
具體采用哪種訪問(wèn)路徑由優(yōu)化器決定菠赚。
索引覆蓋：索引中包含了全部要訪問(wèn)的字段脑豹，無(wú)需掃描表本身。

訪問(wèn)路徑示例

三衡查、執(zhí)行模型

1. 火山模型（Vocano Model）：又稱迭代模型（Iterator Model）

是當(dāng)前的主流執(zhí)行模型：每個(gè) Operator 通過(guò) Next(row) 函數(shù)向上層 Operator 返回?cái)?shù)據(jù)瘩欺；每個(gè) Next(row) 調(diào)用返回一行數(shù)據(jù)；數(shù)據(jù)從下層逐層返回上層拌牲，像火山一樣俱饿。
優(yōu)點(diǎn)：占用內(nèi)存少，便于輸出控制塌忽，按需返回?cái)?shù)據(jù)
缺點(diǎn)：Next 調(diào)用次數(shù)多拍埠，開銷大
改進(jìn)：Next(batch) 批數(shù)據(jù)調(diào)用返回；Operator 內(nèi)部對(duì)批數(shù)據(jù)進(jìn)行并行處理（SIMD）

火山模型示例

2. 并行執(zhí)行模型

為什么并行執(zhí)行：降低時(shí)延土居，提升吞吐枣购，提升資源利用率。
包括單機(jī)并行和多機(jī)（分布式）并行
并行執(zhí)行的類型：查詢間并行 Intra-Query Parallelism擦耀、查詢內(nèi)并行 Inter-Query Parallelism（Operator 內(nèi)并行 Intra Operator棉圈、Operator 間并行 Inter Operator）
Operator 內(nèi)并行：需要引入 Exchange 運(yùn)算符

并行執(zhí)行模型示例。虛線即為并行分割方式

3. Exchange運(yùn)算符

Exchange Operator 用于在并行執(zhí)行時(shí)對(duì)數(shù)據(jù)進(jìn)行重分布

• 輸入流數(shù)量（N）埂奈；輸出流數(shù)量（M）
• 常見的 Exchange Operator 類型：Gather(N:1)迄损；Split(1:M)；Repartition(N:M)账磺；Brodcast(N:M)

Exchange Operator 類型示例

4. 并行聚合(repartition類似map-reduce)

并行聚合示例芹敌。左側(cè)為常規(guī)的數(shù)據(jù)流操作，右側(cè)表示第一次 LocalAgg 的結(jié)果太大導(dǎo)致沒辦法放到內(nèi)存中進(jìn)行直接操作垮抗，因此需要進(jìn)行重分布后氏捞，再次進(jìn)行聚合；第二次是直接可以 Gather 的冒版，因?yàn)樯洗沃胤植紩?huì)把相同的 Key 放到同一個(gè)分區(qū)中液茎。

5. 并行連接(broadcast類似spark的廣播變量)

并行連接示例。左側(cè)場(chǎng)景有限辞嗡，要求 R 是小表捆等。對(duì)于大表，則需要先拆分续室，再?gòu)V播進(jìn)行分區(qū)連接

第四部分：【數(shù)據(jù)庫(kù)理論基礎(chǔ)】數(shù)據(jù)庫(kù)存儲(chǔ)和索引概述

一栋烤、數(shù)據(jù)庫(kù)存儲(chǔ)

1. 什么是數(shù)據(jù)庫(kù)存儲(chǔ)引擎

1.1 定義

存儲(chǔ)引擎就是如何存儲(chǔ)數(shù)據(jù)、如何檢索數(shù)據(jù)和如何更新數(shù)據(jù)等技術(shù)的實(shí)現(xiàn)方法

1.2 組成

權(quán)限及完成性管理器挺狰、事務(wù)管理器明郭、文件管理器、緩沖區(qū)管理器

1.3 存儲(chǔ)引擎的數(shù)據(jù)結(jié)構(gòu)

• 數(shù)據(jù)文件（Data Files）：存儲(chǔ)數(shù)據(jù)庫(kù)自身
• 數(shù)據(jù)字典（Data Dictionary）：存儲(chǔ)關(guān)于數(shù)據(jù)庫(kù)結(jié)構(gòu)的元數(shù)據(jù)
• 索引（Index）：提供對(duì)數(shù)據(jù)項(xiàng)的快速訪問(wèn)

數(shù)據(jù)庫(kù)引擎示例

2. 插入和檢索一條記錄

2.1 插入

1. 數(shù)據(jù)庫(kù)客戶端發(fā)送請(qǐng)求
2. 查詢處理器使用數(shù)據(jù)字典和統(tǒng)計(jì)信息生成最優(yōu)執(zhí)行計(jì)劃
3. 調(diào)用事務(wù)管理相關(guān)邏輯丰泊，例如加鎖薯定，分配事務(wù)號(hào)和時(shí)間戳，沖突檢測(cè)等
4. 調(diào)用文件管理器寫入WAL
5. 向緩存區(qū)管理器插入數(shù)據(jù)和索引

2.2 檢索

1. 數(shù)據(jù)庫(kù)客戶端發(fā)送請(qǐng)求
2. 查詢處理器使用數(shù)據(jù)字典和統(tǒng)計(jì)信息生成最優(yōu)執(zhí)行計(jì)劃瞳购，使
   用索引或者做全表掃描
3. 調(diào)用事務(wù)管理相關(guān)邏輯话侄，例如加鎖，分配事務(wù)號(hào)和時(shí)間戳
4. 向緩存區(qū)管理器查詢索引或者數(shù)據(jù)的緩存
5. 調(diào)用文件管理器查詢索引或者數(shù)據(jù)学赛，并寫入緩存區(qū)管理器

3. 數(shù)據(jù)庫(kù)存儲(chǔ)與分類

3.1 數(shù)據(jù)組織形式

• 行存
• 列存
• 行列混合存(PAX格式年堆、Spaner中采用；OceanBase的列組也可以看做這種形式)

3.2 數(shù)據(jù)粒度

• Page粒度：將多行記錄聚合為一個(gè) Page罢屈，數(shù)據(jù)和索引都是按照 Page 的粒度進(jìn)行訪問(wèn)嘀韧。存在讀寫放大；元數(shù)據(jù)少缠捌。如 MySQL, PostgreSQL等)
• Tuple粒度：?jiǎn)涡杏涗浘褪亲钚≡L問(wèn)單元锄贷，內(nèi)存數(shù)據(jù)庫(kù)、可以基于字節(jié)尋址的NVM數(shù)據(jù)庫(kù)通常采用此粒度（ByteNDB）曼月。讀寫放大小, 但元數(shù)據(jù)多谊却，內(nèi)部的節(jié)點(diǎn)也會(huì)多很多。

3.3 存儲(chǔ)位置

• 本地：成本高哑芹，受限單機(jī)容量等缺點(diǎn)炎辨。
• 遠(yuǎn)端(計(jì)算存儲(chǔ)分區(qū))：Share-Disk、Share-Storage聪姿。

3.4 數(shù)據(jù)集位置

• 內(nèi)存：數(shù)據(jù)集全部在內(nèi)存中碴萧，WAL只是作為故障恢復(fù)使用乙嘀，再利用 Checkpoint 加速恢復(fù)。常見于內(nèi)存數(shù)據(jù)庫(kù)破喻，適合需要高性能且數(shù)據(jù)量不大的表虎谢。如Azure 中的 Hekaton。
• 磁盤/NVM：數(shù)據(jù)集全部在持久化介質(zhì)中曹质，內(nèi)存只是起到緩存的作用婴噩，不影響正確性。

4. 常用存儲(chǔ)結(jié)構(gòu)

4.1 基于B+樹的 In-Place updates

定義：數(shù)據(jù)和索引都存儲(chǔ)在文件系統(tǒng)中羽德，通過(guò)B+樹索引某個(gè)元組几莽，原地進(jìn)行 insert/update/delete 等操作。
缺點(diǎn)：需要額外的軟件設(shè)計(jì)來(lái)維護(hù)文件的一致性宅静。比如更新16KB的數(shù)據(jù)章蚣，在底層文件系統(tǒng)是4KB為單位分四次寫入的，但是寫入4KB后掉電崩潰了坏为，就會(huì)導(dǎo)致別的數(shù)據(jù)還沒更新究驴，16KB的Page數(shù)據(jù)被損壞。InnerDB 使用 DoubleWrite 來(lái)處理這個(gè)問(wèn)題匀伏。
Mysql 和 PostgreSQL 都是采用此方式

In-Place updates

4,2 基于B+樹的 Copy-on-Write updates

定義：數(shù)據(jù)和索引都存儲(chǔ)在文件系統(tǒng)中洒忧，通過(guò)B+樹索引某個(gè)元組，采用 Copy on Write 的方式進(jìn)行 insert/update/delete 等操作够颠。
Copy on Write：更新時(shí)熙侍，先拷貝一份原數(shù)據(jù)做更新，然后替換原數(shù)據(jù)履磨。
MongoDB 采用此方式

Copy-on-Write updates

4,3 LSM的追加與合并

使用RocksDB作為數(shù)據(jù)庫(kù)的本地存儲(chǔ)蛉抓。
LSM優(yōu)點(diǎn)是寫入很快，但是存在讀放大問(wèn)題剃诅。
TiDB等在使用巷送。

4,4 LSM的KV分離實(shí)現(xiàn)

為了進(jìn)一步減少LSM的寫放大，提高系統(tǒng)性能矛辕，在寫 Log 之后笑跛，將指針插入索引，索引里面存元數(shù)據(jù)的指針聊品。
ByteNDB 中的 TerakKV飞蹂，ByteNDB for MemDB(Log Is Database)

LSM實(shí)現(xiàn)示例

二、數(shù)據(jù)庫(kù)索引

1. 索引概述

定義：索引是為了加速對(duì)表中數(shù)據(jù)行的檢索而創(chuàng)建的一種存儲(chǔ)結(jié)構(gòu)翻屈，索引是針對(duì)表而建立的陈哑，每個(gè)索引Entry中都會(huì)含有邏輯指針，以便加速檢索物理數(shù)據(jù)
索引的作用：索引就是用來(lái)減少IO數(shù)量，加速數(shù)據(jù)的查找惊窖。僅僅把表示關(guān)系的元組隨機(jī)存入各級(jí)存儲(chǔ)是不夠的刽宪，例如如下的查詢：SELECT FROM T WHERE id=1 必須遍歷每個(gè)存儲(chǔ)塊才能找到id=1的數(shù)據(jù)行

2. 索引的劃分

2.1 按數(shù)據(jù)的物理存儲(chǔ)劃分

聚集索引：索引鍵的順序和表記錄的物理順序一致，查詢快爬坑，一旦具有第一個(gè)索引值的紀(jì)錄被找到纠屋，具有連續(xù)索引值的記錄也一定物理的緊跟其后涂臣；更新慢盾计，因?yàn)樾枰S護(hù)物理節(jié)點(diǎn)的順序。
非聚集索引：索引鍵記錄的是表中的邏輯順序赁遗，但記錄的物理順序和索引的順序不一致署辉。更新快，查詢慢岩四。

2.2 索引鍵的覆蓋范圍

稠密索引：為每個(gè)索引鍵都建立索引項(xiàng)
稀疏索引：只為部分索引鍵建立索引項(xiàng)哭尝，只有聚集索引才能使用稀疏索引（因?yàn)樾枰业剿饕蟊闅v數(shù)據(jù)塊，因此對(duì)物理順序有要求）剖煌。

2.3 按索引鍵的特征劃分

主鍵索引：建立在主鍵上的索引被稱為主鍵索引材鹦，一張數(shù)據(jù)表只能有一個(gè)主鍵索引，索引列值不允許有空值耕姊，通常在創(chuàng)建表時(shí)一起創(chuàng)建
唯一索引：建立在UNIQUE字段上的索引被稱為唯一索引桶唐，一張表可以有多個(gè)唯一索引，索引列值允許為空茉兰，列值中出現(xiàn)多個(gè)空值不會(huì)發(fā)生重復(fù)沖突
普通索引/非唯一索引：建立在普通字段上的索引被稱為普通索引

2.4 按索引鍵的數(shù)量劃分

單列索引：索引鍵只包含數(shù)據(jù)行的一列
多列索引：索引鍵由數(shù)據(jù)行的多列組成尤泽，比如把數(shù)據(jù)看成多維的，比如地理位置

3. 常用索引結(jié)構(gòu)

3.1 Hash索引

優(yōu)點(diǎn)：點(diǎn)查詢效率高
缺點(diǎn)：1) 主鍵被Hash后规脸，物理上是隨機(jī)分布坯约，不支持范圍查詢；2) 不支持模糊查詢莫鸭，例如 >闹丐，<, LIKE 等（需要索引的全部信息來(lái)計(jì)算hash）；3) 對(duì)于多列索引被因，不支持部分字段的前綴查詢卿拴；4) 重復(fù)值較多時(shí)，性能可能很差氏身；5) 查詢層無(wú)法利用索引的排序來(lái)提升性能巍棱。

3.2 B-Tree索引

優(yōu)點(diǎn)：1) 出度大，且葉子節(jié)點(diǎn)不包含表數(shù)據(jù)蛋欣，樹的高度小航徙，所以單次請(qǐng)求涉及的磁盤IO次數(shù)少；2) 任何關(guān)鍵字的查詢必須走從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)陷虎，查詢路徑長(zhǎng)度相同到踏，所以查詢效率穩(wěn)定杠袱；3) 從符合條件的某個(gè)葉子節(jié)點(diǎn)開始遍歷即可，所以范圍查詢效率高窝稿。
缺點(diǎn)：隨著新數(shù)據(jù)的插入楣富，葉子節(jié)點(diǎn)會(huì)慢慢分裂，邏輯上連續(xù)的葉子節(jié)點(diǎn)在物理上往往不連續(xù)伴榔，甚至分離的很遠(yuǎn)纹蝴，所以B-Tree最大的問(wèn)題就是會(huì)產(chǎn)生大量的隨機(jī)IO，影響性能踪少。

3.3 LSM(Log-Structured Merge Tree)

由于隨機(jī)讀寫比順序讀寫慢很多塘安，而LSM通過(guò) 內(nèi)存插入 與 磁盤的順序?qū)?來(lái)達(dá)到最優(yōu)的寫性能，從而大幅提升寫操作援奢，代價(jià)是犧牲一定的讀性能兼犯。隨著小樹越來(lái)越多，讀的性能可能會(huì)越來(lái)越差集漾，一次需要在適當(dāng)?shù)臅r(shí)候?qū)⒋疟P中的小樹進(jìn)行Merge切黔，多棵小樹變?yōu)橐豢么髽?br> 優(yōu)點(diǎn)：寫性能很好，例如基于LSM樹實(shí)現(xiàn)的HBase的寫性能比MySQL高了一個(gè)數(shù)量級(jí)具篇。
缺點(diǎn)：讀性能一般纬霞，后臺(tái)Compaction啟動(dòng)時(shí)咐汞，可能會(huì)影響前臺(tái)的IO访敌。

3.4 Bitmap位圖索引

比如對(duì)于查詢 Select * From table Where Gender='Male' And Marital='Married'; table 指的是員工信息表。
對(duì)于性別列來(lái)說(shuō)戒职，只有兩種取值秒紧，且各占50%绢陌，如果使用B-Tree索引，需要讀取到一半的數(shù)據(jù)熔恢，區(qū)分度低脐湾，因此此時(shí)沒有必要使用B-Tree索引。

優(yōu)點(diǎn)：1) 當(dāng) Select Count(XXX) 時(shí)叙淌，可以直接訪問(wèn)索引中的一個(gè)位圖就快速得出統(tǒng)計(jì)數(shù)據(jù)秤掌；2) 當(dāng)根據(jù)鍵值做 And Or 等查詢時(shí)，直接用索引的位圖進(jìn)行與或運(yùn)算鹰霍，快速得出結(jié)果行數(shù)據(jù)闻鉴。
缺點(diǎn)：不適用于取值范圍很廣、或者頻繁更新的列茂洒。

三孟岛、存儲(chǔ)與索引的發(fā)展趨勢(shì)

1. 存儲(chǔ)發(fā)展趨勢(shì)

1.1 云原生的分布式存儲(chǔ)

云原生數(shù)據(jù)庫(kù)運(yùn)行在容器中，具備快速部署、快速擴(kuò)縮容的能力渠羞；計(jì)算和存儲(chǔ)都需要具備云原生能力斤贰。
云原生的核心是通過(guò)虛擬化技術(shù)帶來(lái)池化資源，實(shí)現(xiàn)彈性次询、高可用荧恍、高效運(yùn)維。

1.2. 行列混存（HTAP）

HTAP（混合事務(wù) / 分析處理屯吊，Hybrid Transactional/Analytical Processing）
物聯(lián)網(wǎng)送巡、大數(shù)據(jù)、?控等縱多領(lǐng)域有實(shí)時(shí)更新和查詢的需求雌芽，HTAP數(shù)據(jù)庫(kù)能夠在一份數(shù)據(jù)上同時(shí)支撐業(yè)務(wù)系統(tǒng)運(yùn)行OLTP和OLAP授艰，避免在傳統(tǒng)架構(gòu)中，在線與離線數(shù)據(jù)庫(kù)之間大量的數(shù)據(jù)交互世落，是數(shù)據(jù)庫(kù)未來(lái)重要的發(fā)展方向

1.3 基于新硬件的高性能存儲(chǔ)

需求：高吞吐、低延時(shí)數(shù)據(jù)庫(kù)需求迫切糟需，(NVM/RDMA等新硬件設(shè)計(jì)的數(shù)據(jù)庫(kù))
互聯(lián)網(wǎng)金融屉佳、電商、O2O洲押、零售等行業(yè)武花，核心交易系統(tǒng)對(duì)高吞吐、低時(shí)延數(shù)據(jù)庫(kù)的需求越來(lái)越迫切杈帐，基于NVM/RDMA等新硬件設(shè)計(jì)的數(shù)據(jù)庫(kù)体箕，已在國(guó)內(nèi)外大廠被廣泛研究和應(yīng)用

1.4. 數(shù)據(jù)自動(dòng)分級(jí)存儲(chǔ)

利用已有的云服務(wù)，提高性能挑童，降低成本

2. 索引發(fā)展趨勢(shì)

2.1 無(wú)鎖高并發(fā)

傳統(tǒng)B+樹難以使用CPU多核能力累铅，高并發(fā)的情況下，鎖粒度大導(dǎo)致性能無(wú)法提升站叼。
B-Tree在數(shù)據(jù)庫(kù)領(lǐng)域被廣泛地用作索引娃兽，傳統(tǒng)的B-Tree并發(fā)控制算法加鎖粒度大，高并發(fā)訪問(wèn)下尽楔，性能較差投储，所以業(yè)界產(chǎn)生了許多基于B-Tree進(jìn)行高并發(fā)改造的樹形索引

2.2 BW-Tree

基于B+-Tree，將 Insert阔馋、Split 和 Merge 等操作通過(guò)多個(gè)原子操作來(lái)實(shí)現(xiàn)無(wú)鎖玛荞。
每個(gè)Page 管理的是 Base Page + Delta Record，來(lái)實(shí)現(xiàn)多版本呕寝。

2.3 Blink-Tree

基于B+-Tree勋眯，內(nèi)部節(jié)點(diǎn)增加了一個(gè)指向右兄弟的指針。
支持在不持有鎖的狀態(tài)下，從根節(jié)點(diǎn)訪問(wèn)到葉子結(jié)點(diǎn)凡恍，只對(duì)需要修改的節(jié)點(diǎn)加鎖志秃，是自底向上、自左向右的加鎖方式嚼酝。讀寫沖突的概率小浮还。（對(duì)于B+-Tree來(lái)說(shuō)，我們的Update和Sort對(duì)于一個(gè)葉子節(jié)點(diǎn)進(jìn)行操作即可闽巩，節(jié)點(diǎn)分裂和合并的操作占比很芯唷）

2.4 ART(自適應(yīng)前綴樹)

采用路徑壓縮的方式來(lái)減少內(nèi)存的占用。
通過(guò)在 Node 上增加 Lock 和 Version涎跨，遍歷過(guò)程中最多同時(shí)對(duì)兩個(gè)索引節(jié)點(diǎn)進(jìn)行加鎖洼冻，加鎖的范圍小，能夠支持高并發(fā)隅很。
點(diǎn)查詢性能高撞牢、范圍查詢性能低。

2.5 Mass-Tree

從結(jié)構(gòu)上來(lái)說(shuō)叔营，Mass Tree 是由一層或者多層的 B+-Tree 組成的 Trie 樹屋彪。
通過(guò)在 Node 上增加 Lock 和 Version，在 Insert 和 Split 時(shí)最多對(duì) Current 和 Parent Node 加鎖來(lái)支持高并發(fā)訪問(wèn)绒尊。

2.6 分布式化

計(jì)算存儲(chǔ)分離畜挥，且存儲(chǔ)分布式化的趨勢(shì)下，分布式索引是多寫架構(gòu)的關(guān)鍵技術(shù)婴谱，且能打破單機(jī)在容量和可靠性等方面的限制蟹但。這是多寫架構(gòu)的關(guān)鍵技術(shù)。

第五部分：【數(shù)據(jù)庫(kù)理論基礎(chǔ)】數(shù)據(jù)庫(kù)事務(wù)概述

一谭羔、認(rèn)識(shí)事務(wù)

1. 為什么需要事務(wù)

事務(wù)需求舉例

2. 什么是數(shù)據(jù)庫(kù)事務(wù)

定義：數(shù)據(jù)庫(kù)管理系統(tǒng)執(zhí)行過(guò)程的一個(gè)邏輯單位华糖，由一個(gè)有限的數(shù)據(jù)庫(kù)操作序列構(gòu)成
目的：為數(shù)據(jù)庫(kù)數(shù)據(jù)提供一致性能力，這種一致性哪怕是在異常狀態(tài)下也成立口糕；當(dāng)多個(gè)應(yīng)用并發(fā)訪問(wèn)數(shù)據(jù)庫(kù)時(shí)缅阳，提供一種隔離方法，防止彼此的操作互相干擾景描；為數(shù)據(jù)庫(kù)系統(tǒng)提供了一個(gè)從異呈欤恢復(fù)到正常狀態(tài)的方法。

3. 事務(wù)的基本特性

ACID：Atomic超棺、Consistency向族、Isolation、Durability
Atomic：原子性棠绘。操作要么都成功件相，要么都失敗
Consistency：一致性再扭。數(shù)據(jù)庫(kù)數(shù)據(jù)從一個(gè)狀態(tài)變化為另一個(gè)狀態(tài)，無(wú)論是否異常夜矗，數(shù)據(jù)都保持一致性（比如轉(zhuǎn)賬場(chǎng)景泛范，AB兩方的賬戶總額永遠(yuǎn)是一致的）。
Isolation：隔離性紊撕。允許多個(gè)并發(fā)事務(wù)同時(shí)對(duì)數(shù)據(jù)庫(kù)數(shù)據(jù)進(jìn)行讀寫和修改罢荡，且互相不影響，看起來(lái)像是串行執(zhí)行一樣对扶，并且不會(huì)出現(xiàn)數(shù)據(jù)不一致区赵。
Durability：持久性。數(shù)據(jù)庫(kù)數(shù)據(jù)操縱是持久化操作浪南，只要執(zhí)行成功笼才，就需要落盤持久化保證。

如何保證ACID

二络凿、并發(fā)控制

1. 再談Isolation

Isolation定義：就是數(shù)據(jù)庫(kù)允許多個(gè)并發(fā)事務(wù)同時(shí)對(duì)數(shù)據(jù)進(jìn)行讀寫和修改的能力骡送，且互相之間不影響，看起來(lái)像串行執(zhí)行一樣喷众，并且不會(huì)出現(xiàn)由于事務(wù)交叉執(zhí)行而導(dǎo)致的數(shù)據(jù)不一致各谚。

Isolation舉例。左圖為問(wèn)題定義到千，以及該問(wèn)題的一致性定義；右圖為串行執(zhí)行的示例

并行執(zhí)行示例一-正確的事務(wù)調(diào)度

并行執(zhí)行示例二-錯(cuò)誤的事務(wù)調(diào)度

如何判斷一個(gè)事務(wù)調(diào)度是正確的赴穗？：如果一個(gè)并發(fā)事務(wù)的調(diào)度執(zhí)行結(jié)果能和多種串行執(zhí)行的其中一個(gè)結(jié)果相等憔四，我們認(rèn)為這是一個(gè)正確的調(diào)度，稱之為 serializable schedule般眉。

2. 并發(fā)問(wèn)題與隔離級(jí)別

2.1 并發(fā)異象

并發(fā)導(dǎo)致的并發(fā)異象：臟讀(Dirty Read, Read Uncommitted data)了赵，臟寫(Dirty Write, Overwrite Uncommitted data)，不可重復(fù)讀(Unrepeatable Read)甸赃，幻讀(Phantom Read)

• 臟讀：前一個(gè)事務(wù)執(zhí)行柿汛，修改了數(shù)據(jù)A，未Commit情況下另一個(gè)事務(wù)讀取到了修改后的A數(shù)據(jù)埠对，結(jié)果前一個(gè)事務(wù)執(zhí)行了回滾络断，導(dǎo)致第二個(gè)事務(wù)出現(xiàn)并發(fā)異象。
• 臟寫：前一個(gè)事務(wù)執(zhí)行项玛，修改了數(shù)據(jù)A貌笨，未Commit情況下另一個(gè)事務(wù)執(zhí)行寫操作，修改了A和B然后Commit襟沮，執(zhí)行完成后锥惋，前一個(gè)事務(wù)繼續(xù)修改B昌腰，導(dǎo)致A和B結(jié)果異常。
• 不可重復(fù)讀：前一個(gè)事務(wù)執(zhí)行膀跌，讀取數(shù)據(jù)A遭商，接著另一個(gè)事務(wù)修改了A數(shù)據(jù)并Commit，前一個(gè)事務(wù)后續(xù)繼續(xù)讀取A數(shù)據(jù)捅伤，導(dǎo)致前一個(gè)事務(wù)對(duì)于A數(shù)據(jù)的兩次讀取結(jié)果不同劫流，導(dǎo)致并發(fā)異象。
• 幻讀：第一個(gè)事務(wù)先篩選讀取了一些數(shù)據(jù)暑认，操作過(guò)程中困介，第二個(gè)事務(wù)新插入一行數(shù)據(jù)并Commit，在第一個(gè)事務(wù)中以相同的篩選條件讀取到的數(shù)據(jù)個(gè)數(shù)與第一次讀取不同蘸际，導(dǎo)致并發(fā)異象座哩。

2.2 四大隔離級(jí)別

如果能避免所有的并發(fā)時(shí)產(chǎn)?的異象，則可以得到serializable schedule粮彤。在真實(shí)場(chǎng)景中根穷，有時(shí)候并不需要如此高的一致性，因此根據(jù)場(chǎng)景可以犧牲一些一致性來(lái)提高整體的性能导坟，根據(jù)并發(fā)異象屿良，定義出4大隔離級(jí)別。

4大隔離級(jí)別惫周。第四行最后一列應(yīng)該是 Not Possible（圖片寫錯(cuò)了）

2.3 并發(fā)沖突

并發(fā)產(chǎn)生的異象尘惧，本質(zhì)上是出現(xiàn)了沖突：
W-W沖突：兩個(gè)事務(wù)先后修改了同一個(gè)數(shù)據(jù)庫(kù)的相同 object。
W-R沖突：事務(wù)T1修改某個(gè) object 之后（未提交）递递，事務(wù)T2對(duì)修改的 object 進(jìn)行了讀操作喷橙。
R-W沖突：事務(wù)T1讀取了某個(gè) object 或者某個(gè) range 之后，事務(wù)T2對(duì)所讀取的 object 或者 range 進(jìn)行了修改登舞。

2.4 序列化圖

序列化圖的定義：
序列化圖是用有向圖的方式表示事務(wù)相互之間的沖突依賴關(guān)系贰逾，圖中每個(gè)節(jié)點(diǎn)表示一個(gè)事務(wù)，有向邊表示存在一種依賴關(guān)系菠秒。

基于序列化圖的并發(fā)異象定義：
我們將事務(wù)對(duì)不同object的依賴關(guān)系表示到同一張序列化圖中疙剑，所謂異象就是找不到正確的序列化順序，即存在某種環(huán)践叠。

2.5 MVCC言缤，引出SI隔離級(jí)別（Snapshot Isolation）

為了提高數(shù)據(jù)庫(kù)的并發(fā)性能，提出了MVCC（Multi-Version Concurrency Control）來(lái)實(shí)現(xiàn)讀寫互不阻塞酵熙，從而提高數(shù)據(jù)庫(kù)的并發(fā)性能轧简。
在MVCC下，定義出一種新的隔離級(jí)別——SI（Snapshot Isolation）：用 ts 表示事務(wù)的執(zhí)行順序（對(duì)事務(wù)進(jìn)行排序）匾二；事務(wù)的讀從已經(jīng)committed的快照中讀取數(shù)據(jù)哮独；SI允許事務(wù)使用很舊的ts執(zhí)行拳芙，從而不被任何寫操作阻塞，可以讀一個(gè)歷史數(shù)據(jù)皮璧。
SI的并發(fā)異象——Write Skew

3. 并發(fā)控制的概念

為了解決上述并發(fā)異象舟扎，引出并發(fā)控制。
定義：所謂的并發(fā)控制悴务，就是一種保證并發(fā)執(zhí)行的事務(wù)在某一種隔離級(jí)別上能夠正確執(zhí)行睹限。達(dá)到要求的數(shù)據(jù)一致性目的的事務(wù)調(diào)度機(jī)制。

4. 并發(fā)控制的分類

按照樂觀程度劃分：從悲觀到樂觀讯檐，分別有基于Lock羡疗，基于TS，基于驗(yàn)證的并發(fā)控制協(xié)議别洪。
單版本VS多版本：從悲觀到樂觀叨恨，多版本下分別有MV2PL，MVTO挖垛，MVOCC幾種并發(fā)控制協(xié)議實(shí)現(xiàn)痒钝。

5. 常見的并發(fā)控制協(xié)議

5.1 2PL

鎖的分類：S-Lock（共享鎖，讀鎖）痢毒；X-Lock（互斥鎖送矩，寫鎖）
鎖的兼容性：只有S-Lock和S-Lock互相兼容，其余情況均不兼容哪替。
兩階段：Growing Phase（事務(wù)申請(qǐng)所需要的所有鎖栋荸，加鎖失敗則等待）和 Shrinking Phase（釋放Growing階段獲取的鎖，不允許再請(qǐng)求新鎖）

2PL占用鎖的趨勢(shì)凭舶。第一階段只能獲取鎖蒸其，不能釋放鎖，第二階段必須釋放鎖库快，不能獲取鎖，否則會(huì)出現(xiàn)并發(fā)異象

死鎖處理之死鎖檢測(cè)（Deadlock Detection）

wait-for 圖示例

根據(jù)wait-for圖就事務(wù)等待關(guān)系钥顽。當(dāng)出現(xiàn)環(huán)時(shí)表示出現(xiàn)了死鎖义屏。系統(tǒng)后臺(tái)定時(shí)監(jiān)測(cè) wait-for 圖，如果發(fā)現(xiàn)環(huán)則選擇合適的事務(wù) abort蜂大。

死鎖處理之死鎖預(yù)防（Deadlock Prevention）
當(dāng)事務(wù)去請(qǐng)求一個(gè)已經(jīng)被持有的鎖時(shí)闽铐，數(shù)據(jù)庫(kù)系統(tǒng)為了防止死鎖，殺死一個(gè)事務(wù)奶浦，這種防患于未然的方式不需要 wait-for 圖兄墅，但是提高了被殺死的比率。

• Wound-Wait模式：搶占式澳叉，殺死比自己新的事務(wù)隙咸，否則等待沐悦。
• Wait-Die模式：非搶占式，如果自己比別的事務(wù)新五督，則自殺藏否，否則等待。

5.2 T/O

T/O 的核心思想就是利用時(shí)間戳來(lái)決定事務(wù)之間的等價(jià)執(zhí)行順序：如果TS(Ti)<TS(Tj)充包，那么數(shù)據(jù)庫(kù)必須保證實(shí)際的schedule先執(zhí)行Ti副签，后執(zhí)行Tj的結(jié)果等價(jià)。
(1) 數(shù)據(jù)元數(shù)據(jù)：
W-TS(X)：最后一次寫X發(fā)生的時(shí)間戳基矮；
R-TS(X)：最后一次讀X發(fā)生的時(shí)間戳淆储。
(2) 讀：
TTS<W-TS(X)：該對(duì)象對(duì)該事務(wù)不可見，abort事務(wù)家浇，取一個(gè)新的時(shí)間戳重新開始（不能讀到未來(lái)值）
TTS>W-TS(X)：該對(duì)象對(duì)該事務(wù)可見本砰，更新R-TS(X)=max(TTS,R-TS(X))蓝谨，為了滿足 repeatable read灌具，可以保留一份X的值。
(3) 寫：
TTS<W-TS(X) || TTS<R-TS(X)：abort 事務(wù)譬巫，重新開始（意味著寫過(guò)時(shí)）
TTS>W-TS(X) && TTS>R-TS(X)：更新事務(wù)X咖楣，W-TS(X)=TTS，如果有必要芦昔，可以保留X的副本诱贿，保證Ti結(jié)束前能夠讀到相同的X。

Basic T/O優(yōu)點(diǎn)：不會(huì)造成死鎖咕缎，無(wú)事務(wù)需要等待珠十；如果單個(gè)事務(wù)設(shè)計(jì)數(shù)據(jù)不多，不同事務(wù)之間沖突較小的OLTP凭豪，可以節(jié)省2PL控制鎖的額外成本焙蹭，提高并發(fā)。
Basic T/O缺點(diǎn)：長(zhǎng)事務(wù)容易與短事務(wù)沖突而餓死嫂伞；復(fù)制數(shù)據(jù)孔厉、維護(hù)、更新時(shí)間戳存在額外的成本帖努；可能產(chǎn)生不可恢復(fù)的schedule撰豺。

T/O 不可恢復(fù) schedule 舉例：T2讀取A操作B并完成提交，由于T1 abort 導(dǎo)致 T2 執(zhí)行結(jié)果是錯(cuò)誤的拼余，但是沒有副本可供恢復(fù)

5.3 OCC

OCC 是比T/O更為樂觀的并發(fā)控制協(xié)議污桦，默認(rèn)各個(gè)事務(wù)之間不會(huì)沖突，因此直接為每個(gè)事務(wù)復(fù)制一個(gè)私有空間來(lái)并發(fā)執(zhí)行讀寫操作匙监，在最終commit時(shí)凡橱，才進(jìn)行沖突判定小作。
Optimistic Consurrency Control（OCC）：同樣是基于時(shí)間戳對(duì)事務(wù)進(jìn)行排序；所有讀取的數(shù)據(jù)都復(fù)制到私有空間中梭纹，所有的修改都在私有空間中進(jìn)行躲惰；分為 Read Phase，Validate Phase 和 Write Phase 三個(gè)階段变抽。
Validate Phase：進(jìn)行驗(yàn)證的階段础拨，負(fù)責(zé)判定該事務(wù)是否與其他并發(fā)事務(wù)存在沖突。向前驗(yàn)證（驗(yàn)證該事務(wù)開始到提交之間已經(jīng)提交的事務(wù)）和向后驗(yàn)證（驗(yàn)證該事務(wù)開始到提交之間還未提交的事務(wù)）。

NDB體系下的內(nèi)存數(shù)據(jù)庫(kù)使用的就是MVOCC的版本控制協(xié)議

三、日志及恢復(fù)

1. 數(shù)據(jù)庫(kù)恢復(fù)

定義：就是在數(shù)據(jù)庫(kù)出現(xiàn)故障后亡笑，對(duì)數(shù)據(jù)庫(kù)的數(shù)據(jù)進(jìn)?恢復(fù)黎做，并可以滿??致性要求：

• Durability Of Update：已經(jīng)commit事務(wù)的修改只怎，故障恢復(fù)后仍然存在
• Failure Atomic：失敗事務(wù)的所有修改都不可?（主要指事務(wù)commit時(shí)，commit半途掉電或者失敗導(dǎo)致需要回滾所有之前的落盤操作）

2. Buffer Pool 機(jī)制

定義：修改數(shù)據(jù)庫(kù)數(shù)據(jù)時(shí)，是對(duì)緩存的修改，最后再將修改后的數(shù)據(jù)寫回到持久化存儲(chǔ)蛀柴，這個(gè)過(guò)程稱為 buffer pool 管理機(jī)制。

• 告知用戶事務(wù)已經(jīng)提交成功前矫夯，相應(yīng)的數(shù)據(jù)必須已經(jīng)持久化——Durability Of Update
• 如果事務(wù)終止鸽疾，任何數(shù)據(jù)修改都不應(yīng)該持久化——Failure Atomic（主要指事務(wù)commit時(shí)，commit半途掉電或者失敗導(dǎo)致需要回滾所有之前的落盤操作）

Buffer Pool 機(jī)制舉例（No Force: redo 日志训貌，Steal: undo 日志）

在 Durability Of Update 要求下制肮，如果事務(wù)提交成功，則必須完成數(shù)據(jù)持久化递沪，如果告知用戶前不必須完成持久化數(shù)據(jù)豺鼻，則需要引入 redo 日志記錄操作，用于異常情況下的操作回放保證數(shù)據(jù)持久化的一致性款慨；
在 Failure Atomic 要求下儒飒，數(shù)據(jù)必須一致性下盤(即No-Steal機(jī)制)，但是如果某個(gè)事務(wù)的數(shù)據(jù)過(guò)多檩奠，下盤無(wú)法保證一致性约素，則為Steal機(jī)制，需要引入 Undo 日志笆凌，在異常恢復(fù)后通過(guò) undo log 恢復(fù)失敗的事務(wù)士葫，保證事務(wù)回滾一致性乞而。

基于redo log 和 undo log 的其他組合機(jī)制

最常用的Buffer Pool 機(jī)制是WAL機(jī)制

3. WAL 機(jī)制

3.1 WAL

定義：Write-Ahead Log 指的是 DBMS 出了維護(hù)正常的數(shù)據(jù)文件外，還額外維護(hù)一個(gè)日志文件慢显，記錄做所有事務(wù)對(duì)DBMS數(shù)據(jù)的完整修改記錄爪模，這些記錄能夠幫助數(shù)據(jù)庫(kù)在恢復(fù)數(shù)據(jù)時(shí)執(zhí)行 undo/redo欠啤。
目的：因?yàn)?strong>傳統(tǒng)磁盤的順序訪問(wèn)性能遠(yuǎn)遠(yuǎn)好于隨機(jī)訪問(wèn)，WAL機(jī)制意圖利用順序?qū)慙og來(lái)記錄對(duì)數(shù)據(jù)庫(kù)的操作屋灌，每次修改數(shù)據(jù)內(nèi)容前洁段，先順序?qū)慙og來(lái)提高性能。

3.2 WAL Protocol——Steal + No-Force 機(jī)制

1. DBMS先將事務(wù)的操作記錄放在內(nèi)存中
2. 在數(shù)據(jù)落盤前共郭，所有?志必須先落盤(redo日志)
3. 在操作?志落盤后祠丝，事務(wù)被認(rèn)為已經(jīng)提交成功(此時(shí)redo已落盤, 就可以返回給用戶. 但數(shù)據(jù)還未落盤)
4. 數(shù)據(jù)庫(kù)數(shù)據(jù)異步落盤(redo日志提前落盤, 數(shù)據(jù)異步落盤)

3.3 日志內(nèi)容

• 事務(wù)開始需要寫 BEGIN 日志，事務(wù)結(jié)束需要寫 COMMIT 日志
• Transaction ID（事務(wù)ID）
• Object ID（數(shù)據(jù)記錄ID）
• Before Value（修改前的值除嘹，用于 Undo 操作）
• After Value（修改后的值写半，用于 Redo 操作）

3.4 問(wèn)題及解決

問(wèn)題：WAL機(jī)制下，隨著操作無(wú)限增長(zhǎng)尉咕，在故障恢復(fù)時(shí)則需要讀取更多的日志叠蝇，執(zhí)行更多的恢復(fù)和回滾操作。
目的：避免日志無(wú)限增長(zhǎng)年缎，恢復(fù)時(shí)讀取所有的日志悔捶，加速恢復(fù)。
手段：checkpoint

4. checkpoint

周期性地將所有的數(shù)據(jù)也持久化到存儲(chǔ)設(shè)備中单芜，然后在日志中寫入一條 CHECKPOINT蜕该。恢復(fù)時(shí)只關(guān)注最后一條 CHECKPOINT 之后的日志數(shù)據(jù)進(jìn)行 undo 和 redo缓溅。

checkpoint 前的 redo 日志, 其數(shù)據(jù)已落盤, redo 日志就無(wú)需再保存, 節(jié)省了磁盤空間.

mysql的三種日志: redo log, undo log, binlog

四蛇损、分布式事務(wù)

1. 數(shù)據(jù)庫(kù)架構(gòu)發(fā)展

數(shù)據(jù)庫(kù)架構(gòu)發(fā)展

單機(jī) -(讀擴(kuò)展)-> 讀寫分離 -(寫擴(kuò)展)-> 多寫分布式數(shù)據(jù)庫(kù)

2. XA分布式數(shù)據(jù)庫(kù)原理

定義：XA規(guī)范是由 X/Open 組織提出的分布式事務(wù)處理規(guī)范，主要定義了事務(wù)管理器 TM 和局部資源管理器 RM 之間的接口坛怪。

XA分布式規(guī)范

3. 分布式事務(wù)提交協(xié)議—2PC

2PC示例

2PC分布式協(xié)議的一些問(wèn)題點(diǎn)如下淤齐，此處不詳細(xì)講述
同步阻塞：本地事務(wù)在 prepare 階段鎖定資源，如果有其他的事務(wù)也要修改賬戶信息袜匿，必須等待前面的事務(wù)完成更啄，導(dǎo)致系統(tǒng)性能下降。
協(xié)調(diào)節(jié)點(diǎn)故障：如果第一個(gè)階段 prepare 成功了居灯，但是第二個(gè)階段協(xié)調(diào)節(jié)點(diǎn)發(fā)出 commit 指令之前宕機(jī)了祭务，所有服務(wù)的數(shù)據(jù)均處于鎖定狀態(tài)，事務(wù)將無(wú)限期地等待怪嫌。
數(shù)據(jù)不一致：如果第一階段 prepare 成功了义锥，但是第二階段協(xié)調(diào)節(jié)點(diǎn)向某個(gè)結(jié)點(diǎn)發(fā)送 commit 命令時(shí)失敗，就會(huì)導(dǎo)致數(shù)據(jù)不一致岩灭。

我的另一個(gè)針對(duì)分布式事務(wù)的筆記

第六部分：【MySQL 數(shù)據(jù)庫(kù)運(yùn)維】一條 SQL 的生命歷程

一拌倍、整體執(zhí)行過(guò)程

SQL 整體執(zhí)行過(guò)程

連接器 -> 查詢緩存 -> 分析器 -> 優(yōu)化器 -> 執(zhí)行器 -> 修改前記錄寫入undo log -> 寫入redo log(prepare狀態(tài)) -> 寫入binlog -> 寫入redo log(commit 狀態(tài))

二、組件介紹

1 連接器

連接器負(fù)責(zé)連接和管理連接。

• 長(zhǎng)連接: 連接成功后, 每次執(zhí)行都用同一個(gè)連接
• 短連接: 每次執(zhí)行完都斷開連接, 下次執(zhí)行新建一個(gè)連接
• 空閑連接會(huì)進(jìn)入sleep狀態(tài)柱恤，live timeout 默認(rèn)為 8小時(shí)数初，沒有操作則斷連。

2 緩存器

判斷SQL是否在緩存中梗顺，如果存在則直接返回泡孩。
緩存失效場(chǎng)景：1) SQL不一致；2) 存在不確定的函數(shù)調(diào)用(now()等)寺谤；3) 不使用任何表查詢(沒有from)仑鸥；4) 查詢 mysql\information_schema\performance_schema 等表不走緩存；5) 在存儲(chǔ)的函數(shù)矗漾、觸發(fā)器或事件的主體內(nèi)執(zhí)行的查詢锈候；6) 表發(fā)生更改則該表全部緩存失效(insert update delete truncate alter drop等)；

3 分析器

詞法分析：判定詞法敞贡，根據(jù)關(guān)鍵字進(jìn)行拆分
語(yǔ)法分析：判定語(yǔ)法泵琳，是否符合mysql的語(yǔ)法規(guī)范

4 優(yōu)化器

使用統(tǒng)計(jì)信息來(lái)估算最佳的索引，根據(jù)執(zhí)行計(jì)劃選擇最優(yōu)的選擇誊役，匹配合適的方案获列，匹配最優(yōu)的索引。
未使用最優(yōu)索引的優(yōu)化方法：可以通過(guò) analyze table 重新計(jì)算表的統(tǒng)計(jì)信息蛔垢；可以 force index 來(lái)強(qiáng)制選取索引击孩；可以刪除不好的索引或者新建一個(gè)更優(yōu)的索引；調(diào)整sql來(lái)讓優(yōu)化器能夠選取最優(yōu)索引鹏漆。

5 執(zhí)行器

執(zhí)行器調(diào)用對(duì)應(yīng)的存儲(chǔ)引擎執(zhí)行sql巩梢。表的查詢權(quán)限檢查是在此階段進(jìn)行的。

6 存儲(chǔ)引擎層

6.1 redolog

redo log 是 InnoDB 引擎特有的
redo log 是物理日志艺玲，記錄“某個(gè)數(shù)據(jù)頁(yè)上面做了什么修改”
redo log 是循環(huán)寫的括蝠，空間固定，會(huì)用完饭聚，用完則復(fù)用原來(lái)的內(nèi)存空間

6.2 binlog

bin log 是 MySQL 的 server 所實(shí)現(xiàn)的忌警，所有的引擎均可使用
bin log 是邏輯 日志，記錄語(yǔ)句的原始邏輯秒梳，比如 “給 ID=2 這一行的 c 字段加 1”
bin log 是可以追加寫入的法绵。單個(gè)文件到達(dá)一定的大小會(huì)切換下一個(gè)文件進(jìn)行寫入，不會(huì)覆蓋之前的日志

6.3 InnoDB 內(nèi)部執(zhí)行流程

InnoDB 內(nèi)部執(zhí)行流程

三酪碘、SQL 執(zhí)行舉例

排序使用 sort buffer朋譬，如果內(nèi)存空間足夠，則 1 次回表兴垦；如果內(nèi)存不足此熬，則先回表讀取排序字段排序，之后返回?cái)?shù)據(jù)時(shí)進(jìn)行第 2 次回表。

四犀忱、Q&A

1. Undo log 存儲(chǔ)在哪里？需不需要落盤扶关？需要的話啥時(shí)候落盤阴汇？所有表的undo log都是集中存放，還是以表為維度劃分文件节槐？

在InnoDB的實(shí)現(xiàn)里面搀庶，Undo log本質(zhì)上不是Log，而是隸屬于Undo Tablespace的頁(yè)面铜异，Undo Tablespace和正常表空間一樣哥倔，修改都通過(guò)redo log記錄，所以從落盤的角度揍庄，和正常表頁(yè)面是一樣的咆蒿，都是背景線程定期從緩沖區(qū)里面將臟頁(yè)刷盤。
Undo log落盤時(shí)機(jī)不重要蚂子，因?yàn)樗胷edo管理沃测；undo log是集中存放的

2. MySQL查詢優(yōu)化器是如何估算代價(jià)的，會(huì)考慮哪些因素食茎？這個(gè)分析過(guò)程自身的代價(jià)又是怎么去平衡的蒂破？

考慮的因素主要是cpu計(jì)算開銷和IO開銷，IO分隨機(jī)IO和順序IO别渔，是一個(gè)很復(fù)雜的計(jì)算量化標(biāo)準(zhǔn)附迷，具體可以看下李海翔的《數(shù)據(jù)庫(kù)查詢優(yōu)化器的藝術(shù):原理解析與SQL性能優(yōu)化》，后續(xù)我們課程也會(huì)涉及

3. 如何判斷一個(gè)事務(wù)真正的執(zhí)行成功了哎媚，通過(guò)生成relog還是binlog喇伯？

事務(wù)提交成功最簡(jiǎn)單的標(biāo)志就是commit命令執(zhí)行成功，但commit命令會(huì)觸發(fā)redo log 進(jìn)入prepare->寫binlog -〉redo log進(jìn)入commit狀態(tài)抄伍，binlog是server層的東西艘刚，作為兩階段事物提交的是協(xié)調(diào)者，如果redo處于prepare狀態(tài)無(wú)binlog截珍，則回滾攀甚；如果處于prepare狀態(tài)，有binlog則commit

4. 一個(gè)事務(wù)里的多條 SQL 是如何同步給從庫(kù)的岗喉？為什么優(yōu)先用 row 格式的 binlog秋度？如果一下子改很多行，會(huì)不會(huì)瞬間存儲(chǔ)壓力比較大钱床？

binlog 有幾種模式：statement(記錄一條條的sql語(yǔ)句荚斯，從庫(kù)進(jìn)行操作重放)、row(記錄一行行數(shù)據(jù)變更的event，打包event給從庫(kù)進(jìn)行數(shù)據(jù)修改事期，要么成功要么失敗)滥壕、Mixed（自動(dòng)模式）
目前我們線上使用的都是row模式，一致性更好兽泣，dbus等依賴

5. 如果MySQL在一個(gè)事務(wù)中crash绎橘，InnoDB是如何保證redo log和binlog的一致性的？

簡(jiǎn)單來(lái)講唠倦，binlog和redo log的一致性保證靠的是一個(gè)內(nèi)部的二階段提交協(xié)議：

• 寫入redo log称鳞，處于prepare狀態(tài)
• 寫binlog
• 修改redo log狀態(tài)為commit
  非常詳細(xì)的流程可以參考 這里。

6. 如果線上MySQL不小心執(zhí)行了一條“邪惡”的SQL稠鼻，造成必須停服恢復(fù)數(shù)據(jù)冈止，如何保證停服時(shí)間最短？

這種情況應(yīng)該是說(shuō)惡意用戶準(zhǔn)備”刪庫(kù)跑路“候齿，如果不小心碰到了這種情況熙暴，需要從備份數(shù)據(jù)里面恢復(fù)（PITR可以到秒級(jí)），恢復(fù)時(shí)間長(zhǎng)短和數(shù)據(jù)量相關(guān)毛肋。

7. 如果MySQL一個(gè)事務(wù)在prepare成功后crash怨咪，怎么恢復(fù)數(shù)據(jù)？

在prepare階段crash后润匙，事務(wù)會(huì)回滾诗眨，此時(shí)還沒生成 binlog。

8. MySQL 的 Planner/Optimizer 會(huì)傾向于選擇穩(wěn)定的代價(jià)（比如對(duì)一些查詢孕讳，固定訪問(wèn)某個(gè)索引）還是一定選擇 cost 上更優(yōu)的代價(jià)匠楚？這個(gè)過(guò)程是否需要 DBA 介入？

MySQL的Optimizer是基于cost的選擇方式厂财，過(guò)程不需要人為干預(yù)芋簿，他會(huì)根據(jù)索引和表的統(tǒng)計(jì)信息計(jì)算cost，選擇最優(yōu)索引璃饱∮虢铮可以通過(guò)explain format = json .... 查看具體細(xì)節(jié)。
如果有兩個(gè)索引存在重復(fù)索引的情況荚恶，同樣的語(yǔ)句在兩個(gè)索引之間來(lái)回切換導(dǎo)致業(yè)務(wù)不可控撩穿，此時(shí)要么優(yōu)化索引，要么手動(dòng)使用Hint（也要注意谒撼，索引的變更食寡，也要記得更新下帶hint的查詢，否則可能會(huì)導(dǎo)致SQL報(bào)錯(cuò)）

9. MySQL 的 secondary index 需不需要維護(hù)多版本廓潜？怎么樣才能保證讓他訪問(wèn)到正確版本的數(shù)據(jù)抵皱？

沒有多版本善榛，鎖和多版本主要是基于主鍵實(shí)現(xiàn)的

10. 同一條sql查詢語(yǔ)句在主庫(kù)和從庫(kù)執(zhí)行的時(shí)候可能走不同索引嗎？

可能的呻畸，走什么索引是優(yōu)化器根據(jù)統(tǒng)計(jì)信息做的決策移盆，同個(gè)SQL在同個(gè)實(shí)例多次執(zhí)行都可能走不一樣的索引

11. 事務(wù)回滾，寫 undo log伤为，修改了數(shù)據(jù)頁(yè)的內(nèi)容味滞，這個(gè)時(shí)候會(huì)寫redo log嗎？

是的钮呀，undo也是數(shù)據(jù)頁(yè)，內(nèi)存中也在innodb_buffer_pool中管理昨凡，所以他的變更爽醋，也被視為一種page的變更記錄redo，所以如果事務(wù)回滾便脊，那么redo相當(dāng)于會(huì)寫兩遍

12. 用唯一索引和用主鍵更新某一條記錄會(huì)有性能區(qū)別嗎蚂四？

理論上來(lái)說(shuō)有區(qū)別，主鍵直接定位記錄哪痰，唯一索引先定位主鍵再定位記錄遂赠，實(shí)際情況下差別很小

13. 編程語(yǔ)言的 mysql-driver 客戶端和 MySQL Server 之間交互傳輸?shù)恼?qǐng)求和結(jié)果使用的是什么格式的？文本還是二進(jìn)制晌杰？會(huì)使用壓縮算法嗎跷睦？

mysql有自己的二進(jìn)制協(xié)議，見 https://dev.mysql.com/doc/internals/en/client-server-protocol.html

14. 怎么理解物理日志和邏輯日志肋演？

物理日志是物理存儲(chǔ)的更改日志抑诸，也就是page，邏輯日志是數(shù)據(jù)的邏輯更改的日志爹殊，邏輯日志記錄某行記錄邏輯結(jié)構(gòu)從什么改成什么蜕乡，物理日志是磁盤上從什么樣改成了什么樣

15. 寫入redo log，undo log梗夸、bin log层玲、B+樹的順序是什么呢？redo log和undo log分別會(huì)在什么時(shí)候發(fā)揮作用呢反症？redo log和bin log可以合并嗎辛块？

redo log的目的是為了保證數(shù)據(jù)庫(kù)寫入數(shù)據(jù)的持久性，undo log是為了用來(lái)做事務(wù)的回滾操作惰帽，保證事務(wù)的原子性憨降。同時(shí)可以用來(lái)構(gòu)建數(shù)據(jù)修改之前的版本，支持多版本讀该酗。
binlog是MySQL server層的日志授药，redo log是MySQL innodb層的日志士嚎，不可以合并

16. RDS的proxy層做了什么？在整個(gè)執(zhí)行流程中哪個(gè)環(huán)節(jié)悔叽？

SQL轉(zhuǎn)發(fā)/限流/流量轉(zhuǎn)發(fā)/相關(guān)監(jiān)控等莱衩，driver之后數(shù)據(jù)庫(kù)之前
client->driver->dbproxy-DB實(shí)例

17. Mysql MVCC怎么解決 write skew、lost update娇澎？

write skew笨蚁、lost update：指的是兩個(gè)事務(wù)在并發(fā)寫操作上發(fā)生的異常，均讀到舊數(shù)據(jù)并更新為新數(shù)據(jù)趟庄，導(dǎo)致其中一個(gè)更新被覆蓋括细。
select for update方式

18. 刪除（delete）數(shù)據(jù)的時(shí)候，有無(wú)索引有區(qū)別嗎戚啥？

有區(qū)別奋单，沒有索引的刪除就會(huì)掃描全表。刪除數(shù)據(jù)最好幾十條猫十、幾百條的刪除览濒。一次性刪除上萬(wàn)條數(shù)據(jù)會(huì)導(dǎo)致主從延遲較大。

19. 存在 binlog 寫成功拖云，事務(wù)回滾的情況嗎贷笛？

沒有

20. 數(shù)據(jù)刪除后，會(huì)不會(huì)造成磁盤碎片宙项，mysql會(huì)在什么時(shí)機(jī)做數(shù)據(jù)合并壓縮嗎乏苦？

會(huì)造成磁盤碎片，mysql不會(huì)合并壓縮杉允，但是會(huì)合并數(shù)據(jù)頁(yè)邑贴，并留有空白數(shù)據(jù)頁(yè)，后續(xù)會(huì)恢復(fù)使用叔磷。

第七部分：【MySQL 數(shù)據(jù)庫(kù)運(yùn)維】MySQL 生態(tài)系統(tǒng)構(gòu)建介紹

第八部分：【MySQL 數(shù)據(jù)庫(kù)運(yùn)維】MySQL Online DDL 詳解

第九部分：【MySQL 數(shù)據(jù)庫(kù)運(yùn)維】MySQL 高可用架構(gòu)設(shè)計(jì)與實(shí)現(xiàn)

第十部分：【MySQL 數(shù)據(jù)庫(kù)運(yùn)維】MySQL 復(fù)制的前世今生

第十一部分：【MySQL 數(shù)據(jù)庫(kù)運(yùn)維】MySQL 的鎖與最佳實(shí)踐

第十二部分：【MySQL 數(shù)據(jù)庫(kù)內(nèi)核深度解析】MySQL 8.0 執(zhí)行器深度解析

第十三部分：【MySQL 數(shù)據(jù)庫(kù)內(nèi)核深度解析】MySQL Binlog 格式及機(jī)制深度解析

第十四部分：【MySQL 數(shù)據(jù)庫(kù)內(nèi)核深度解析】InnoDB B+ Tree 管理機(jī)制深度解析

第十五部分：【MySQL 數(shù)據(jù)庫(kù)內(nèi)核深度解析】InnoDB REDO 日志機(jī)制深度解析

第十六部分：【MySQL 數(shù)據(jù)庫(kù)內(nèi)核深度解析】InnoDB 事務(wù)與隔離級(jí)別深度解析

第十七部分：【MySQL 數(shù)據(jù)庫(kù)內(nèi)核深度解析】MySQL 8.0 Undo Log 機(jī)制深入解析

第十八部分：【MySQL 數(shù)據(jù)庫(kù)內(nèi)核深度解析】InnoDB 存儲(chǔ)物理格式深度解析