范式與反范式

數(shù)據(jù)庫范式的要求

但在互聯(lián)網(wǎng)應(yīng)用中，為了性能或便于開發(fā)，違背范式的設(shè)計比比皆是，如字段冗余、字段存一個復雜的JSON串、分庫分表之后數(shù)據(jù)多維度冗余存儲、寬表等。如果系統(tǒng)是重業(yè)務(wù)性的系統(tǒng)，對性能、高并發(fā)的要求沒有那么高，最好保證數(shù)據(jù)庫的設(shè)計達到第三范式的要求。

分庫分表

為什么要分？

• 業(yè)務(wù)拆分，便于職責分工，便于系統(tǒng)擴展
• 應(yīng)對高并發(fā)，讀多寫少，可以通過從庫、加緩存解決，不一定分庫分表，讀少寫多，寫入的QPS達到數(shù)據(jù)庫的瓶頸，考慮分庫分表
• 數(shù)據(jù)隔離

拆分維度的選擇

• 建立映射表：建立輔助維度和主維度之間的映射關(guān)系
  問題：映射表本身也需要分庫分表，即使不分庫分表，寫入一條訂單的數(shù)據(jù)也可能需要同時寫兩個庫，屬于分布式事務(wù)問題。對于這種問題，通常也只能做一個后臺任務(wù)定時比對，保證訂單表和映射表的數(shù)據(jù)最終一致。
• 業(yè)務(wù)雙寫：同一份數(shù)據(jù)，兩套分庫分表。例如，一套按照用戶ID切分，一套按商戶ID切分。
  問題：同樣存在多個庫的分布式事務(wù)問題。
• 異步雙寫：還是兩套表，只是業(yè)務(wù)單寫。然后通過監(jiān)聽Binlog。同步到另外一套表上。
• 兩個維度統(tǒng)一到一個維度：比如把用戶ID作為訂單ID的某幾位，這樣訂單ID中就包含了用戶ID的信息。

Join查詢問題

• 把Join拆成多個單表查詢，不讓數(shù)據(jù)庫做Join，而是在代碼層對結(jié)果進行拼接。非常常見，降低慢查詢的概率
• 做寬表，重寫輕讀，另外做join表，提前把結(jié)果join好。
• 利用搜索引擎，利用ES的搜索引擎，把數(shù)據(jù)庫中的數(shù)據(jù)導入搜索引擎中進行查詢，從而解決join問題。

B+樹

• 范圍查詢
• 前綴匹配模糊查詢
• 排序和分頁

B+樹邏輯結(jié)構(gòu)

• 在葉子節(jié)點一層，所有記錄的主鍵按照從小到大的順序排序，并且形成了一個雙向鏈表，葉子節(jié)點的每一個key指向一條記錄。

• 非葉子節(jié)點取得是葉子節(jié)點里面key的最小值。這意味著所有非葉子節(jié)點的key都是冗余的葉子節(jié)點。同一層的非葉子節(jié)點也互相串聯(lián)，形成了一個雙向鏈表。

  
  
  主鍵對應(yīng)的索引結(jié)構(gòu)
  
  

  基于B+樹的特性，會發(fā)現(xiàn)對于offet這種特性，其實是用不到索引的。例如select xxx where xxx limit 1000,10，從offset=1000的位置開始取10條。雖然只取了10條，但實際上數(shù)據(jù)要把前面的1000條數(shù)據(jù)都遍歷才能知道offset=1000的位置在哪。合理的辦法是將offset的位置換算成某個max_id，然后用where語句實現(xiàn)，就變成select xxx wehere id>max_id limit 10;

B+樹物理結(jié)構(gòu)

對于磁盤，是以”塊“為單位進行讀寫的。InnoDB默認定義的塊大小是16KB，通過innodb_page_size參數(shù)指定。InnoDB每一次磁盤IO，讀取的都是16KB的整數(shù)倍的數(shù)據(jù)。無論是葉子節(jié)點，還是非葉子節(jié)點，都會裝在page里。16KB如果用來裝非葉子節(jié)點，一個page大概可以裝1000個key，意味著B+樹有1000個分叉；如果用來裝葉子節(jié)點，一個Page大概可以裝200條記錄?；谶@種估算，一個三層的B+樹可以存儲多少數(shù)據(jù)量呢？
第一層：一個節(jié)點是一個Page，里面存放了1000個key,對應(yīng)1000個分叉
第二次：1000個節(jié)點1000page，每個page存放1000個key，對應(yīng)10001000個分叉
第三層：10001000個節(jié)點，每個page存放200條記錄，即是10001000200=2億條記錄，總?cè)萘渴?6KB10001000，約為16GB。
把第一層和第二層的索引全裝入內(nèi)存里，也就約16MB的內(nèi)存。三層B+樹就可以支撐2億條記錄，并且一次基于主鍵的等值查詢，只需要一次IO.
page與page之間組成雙向鏈表，每一個page頭部有兩個關(guān)鍵字段；前一個page的編號，后一個page的編號。page里面存儲一條條的記錄，記錄之間用單向鏈表串聯(lián)。定位到了page，也就定位到了Page里面的記錄。因為Page會一次性讀入內(nèi)存，同一個page里面的記錄可以在內(nèi)存中順序查找。

三層磁盤B+樹

B+樹物理存儲

非主鍵索引

在InnoDB中，非主鍵索引的葉子節(jié)點存儲的不是記錄的指針，而是主鍵的值。且值可以重復，一個key可能對應(yīng)多條記錄。對于非葉子節(jié)點，不僅存儲了索引字段的值，同時也存儲了對應(yīng)的主鍵的最小值。

非主鍵索引B+樹

事務(wù)與鎖

事務(wù)的四個隔離級別

事務(wù)并發(fā)問題

事務(wù)隔離級別

悲觀鎖和樂觀鎖

悲觀鎖，就是認為數(shù)據(jù)發(fā)生并發(fā)沖突的概率很大，所以讀之前就上鎖。利用select xxx for update語句。容易造成死鎖以及高并發(fā)場景下會造成用戶端的大量請求阻塞。
樂觀鎖，認為數(shù)據(jù)發(fā)生沖突的概率比較小，所以讀之前不上鎖，等到寫回去的時候再判斷數(shù)據(jù)是否被其他事務(wù)改了。類似于cas，給表結(jié)構(gòu)里加一列verson字段。在實現(xiàn)層面，就是利用update語句的原子性實現(xiàn)了cas。當且僅當version為期望值時，才更新成功。同時，version也必須加1.version的比較，數(shù)據(jù)的更新，version的加1,這三件事情是在一條update語句里面完成的，這是整個事情的關(guān)鍵所在。

分布式鎖

樂觀鎖的方案限制時select合update的是同一張表的同一條記錄。如果是更加復雜的場景，就需要使用分布式鎖來解決了。

死鎖檢測

兩個事務(wù)發(fā)生死鎖

多事務(wù)發(fā)生死鎖

以事務(wù)為頂點，以事務(wù)請求的鎖為邊，構(gòu)建一個有向圖，這個圖被稱為wait-for graph。死鎖檢測就是發(fā)現(xiàn)這種有向圖中存在的環(huán)。檢測到死鎖后，數(shù)據(jù)庫可以強制讓其中某個事務(wù)回滾，釋放掉鎖，把環(huán)斷開，死鎖就解除了。

事務(wù)實現(xiàn)原理之1：Redo Log

Write-Ahead

一個事務(wù)要修改多張表的多條記錄，多條記錄分布在不同的page里面，對應(yīng)到磁盤的不同位置。如果每個事務(wù)都直接寫磁盤，一次事務(wù)提交就要多次磁盤的隨機IO，性能達不到要求。解決方案：現(xiàn)在內(nèi)存中提交事務(wù)，然后寫日志（所謂的write-ahead log），然后后臺任務(wù)把內(nèi)存中的數(shù)據(jù)異步刷到磁盤。日志是順序地在尾部append，從而避免了一個事務(wù)發(fā)生多次磁盤隨機IO的問題。所謂的write-ahead log就是redo log。redo log寫入的本身也是異步的。在事務(wù)提交后，redo log先寫入內(nèi)存中的redo log buffer中，然后異步地刷到磁盤上的Redo Log。

redo log的異步刷盤

redo log物理結(jié)構(gòu)

• 磁盤的讀取和寫入是按”塊“為單位進行讀取和寫入。對于redo log來說，就是redo log block，為512字節(jié)。在早期的磁盤，一個扇區(qū)就是存儲512個字節(jié)數(shù)據(jù)。
• redo log為一個規(guī)定大小的文件，循環(huán)使用，寫到尾部之后，回到頭部覆寫。之所以能覆寫，因為一旦Page數(shù)據(jù)刷到磁盤上，日志數(shù)據(jù)就沒有存在的必要了。