從0開始，手寫MySQL事務

▌說在前面：從0開始，手寫MySQL的學習價值

尼恩曾經指導過的一個7年經驗小夥，憑借精通Mysql，搞定月薪40K。

從0開始，手寫一個MySQL的學習價值在于：

• 可以深入地了解MySQL的内部機制和原理，Mysql可謂是面試的絕對重點和難點
• 進而更好地掌握MySQL的使用和優化。
• 幫助你提高程式設計能力和解決問題的能力。
• 作為一個優質的履歷輪子項目，注意，這是高品質的履歷輪子項目

很多小夥伴的項目都很low，極度缺乏輪子項目，so，輪子項目這就來了。

注：本文以 PDF 持續更新，尼恩 架構筆記、面試題 的PDF檔案，請到公号【技術自由圈】取

▌手寫DB架構設計：

尼恩的風格： 開始寫代碼前，先做架構

從功能上來說，一個手寫DB系統架構分為以下幾個子產品：

• 資料管理器DM
• 事務管理器TM
• 版本管理器（VM）
• 表管理器（TBM）
• 索引管理器(IM)、

手寫DB架構設計設計圖，具體如下：

▌從0開始，手寫Mysql事務：

事務是應用程式中一系列嚴密的操作，所有操作必須成功完成，否則在每個操作中所作的所有更改都會被撤消。

也就是事務具有原子性，一個事務中的一系列的操作要麼全部成功，要麼一個都不做。

事務的結束有兩種，當事務中的所有步驟全部成功執行時，事務送出。

如果其中一個步驟失敗，将發生復原操作，撤消事務開始時的所有操作。

事務定義的語句如下

(1) BEGIN TRANSACTION：事務開始。

(2) END TRANSACTION：事務結束。

(3) COMMIT：事務送出。該操作表示事務成功地結束，它将通知事務管理器該事務的所有更新操作現在可以被送出或永久地保留。

(4) ROLLBACK：事務復原。該操作表示事務非成功地結束，它将通知事務管理器出故障了，資料庫可能處于不一緻狀态，該事務的所有更新操作必須復原或撤銷。

▌事務5種狀态：

事務是資料庫的基本執行單元，如果事務成功執行，則資料庫從一個一緻狀态進入另一個一緻狀态。

事務狀态 的狀态有以下5種

• 活動狀态：事務的初始狀态，事務執行時處于這個狀态。
• 部分送出狀态：當操作序列的最後一條語句執行後，事務就處于部分送出狀态。這時，事務雖然已經完全執行，但由于實際輸出可能還臨時駐留在記憶體中，在事務成功完成前還有可能出現硬體故障，是以，部分送出狀态并不等于事務成功執行。
• 失敗狀态：由于硬體或邏輯錯誤，使得事務不能繼續正常執行，事務就進入了失敗狀态，處于失敗狀态的事務必須復原。這樣，事務就進入了中止狀态。
• 中止狀态：事務復原并且資料庫恢複到事務開始執行前的狀态。
• 送出狀态：當事務成功完成後，稱事務處于送出狀态。隻有事務處于送出狀态後，才能說事務已經送出。

如果因為某種原因事務沒能成功執行，但其已經對資料庫進行了修改，這時候可能會導緻資料庫處于不一緻的狀态，需要對事務已經造成的變更進行撤銷（復原）。

▌事務5種狀态之間的轉換

• BEGIN TRANSACTION：開始運作事務，使事務進入活動狀态
• END TRANSACTION：說明事物中的所有讀寫操作都已完成，使事務進入部分送出狀态，把事務的所有操作對資料庫的影響存入資料庫。
• COMMIT：标志事務已經成功地完成，事務中的所有操作對資料庫的影響已經安全地存入資料庫，事務進入送出狀态，結束事務的運作。
• ABORT：标志事務進入失敗狀态，系統撤銷事務中所有操作對資料庫和其他事務的影響，結束事務的運作。

▌如何管理事務的狀态？

在手寫資料庫 MYDB 中，每一個事務都有一個 XID，這個 ID 唯一辨別了這個事務。

事務的 XID 從 1 開始标号，并自增，不可重複。

事務管理器TM通過維護XID檔案來維護事務的狀态，并提供接口供其他子產品來查詢某個事務的狀态。

規定 XID 0 是一個超級事務（Super Transaction）。

當一些操作想在沒有申請事務的情況下進行，那麼可以将操作的 XID 設定為 0。XID 為 0 的事務的狀态永遠是 committed。

每個事務有三種狀态:

• active，正在進行，尚未結束,即活動狀态
• committed，已送出狀态
• aborted，復原狀态

定義如下:

// 事務的三種狀态
//活動狀态
private static final byte FIELD_TRAN_ACTIVE   = 0;
//已送出狀态
private static final byte FIELD_TRAN_COMMITTED = 1;
//復原狀态
private static final byte FIELD_TRAN_ABORTED  = 2;
           

XID 檔案給每個事務配置設定了一個位元組的空間，用來儲存其狀态。

同時，在 XID 檔案的頭部，還儲存了一個 8 位元組的數字，記錄了這個 XID 檔案管理的事務的個數。

于是，事務 xid 在檔案中的狀态就存儲在 (xid-1)+8 位元組處，xid-1 是因為 xid 0（Super XID） 的狀态不需要記錄。

在TransactionManager中提供了一些接口供其他子產品調用,用來建立事務和查詢事務狀态，其接口方法如下:

//開啟事務
long begin();
//送出事務
void commit(long xid);
//撤銷事務
void abort(long xid);
// 判斷事務狀态-活動狀态
boolean isActive(long xid);
// 是否送出狀态
boolean isCommitted(long xid);
// 是否失敗狀态
boolean isAborted(long xid);
// 關閉事務管理TM
void close();           

▌建立xid檔案

我們需要建立一個xid檔案并建立TM對象,其具體實作如下:

public static TransactionManagerImpl create(String path) {
  File f = new File(path+TransactionManagerImpl.XID_SUFFIX);
  try {
    if(!f.createNewFile()) {
      Panic.panic(Error.FileExistsException);
    }
  } catch (Exception e) {
    Panic.panic(e);
  }
  if(!f.canRead() || !f.canWrite()) {
    Panic.panic(Error.FileCannotRWException);
  }

  FileChannel fc = null;
  RandomAccessFile raf = null;
  try {
    raf = new RandomAccessFile(f, "rw");
    fc = raf.getChannel();
  } catch (FileNotFoundException e) {
    Panic.panic(e);
  }

  // 寫空XID檔案頭
  ByteBuffer buf = ByteBuffer.wrap(new byte[TransactionManagerImpl.LEN_XID_HEADER_LENGTH]);
  try {
    //從零建立 XID 檔案時需要寫一個空的 XID 檔案頭，即設定 xidCounter 為 0，
    // 否則後續在校驗時會不合法：
    fc.position(0);
    fc.write(buf);
  } catch (IOException e) {
    Panic.panic(e);
  }

  return new TransactionManagerImpl(raf, fc);
}

//從一個已有的 xid 檔案來建立 TM
public static TransactionManagerImpl open(String path) {
  File f = new File(path+TransactionManagerImpl.XID_SUFFIX);
  if(!f.exists()) {
    Panic.panic(Error.FileNotExistsException);
  }
  if(!f.canRead() || !f.canWrite()) {
    Panic.panic(Error.FileCannotRWException);
  }

  FileChannel fc = null;
  RandomAccessFile raf = null;
  try {
    //用來通路那些儲存資料記錄的檔案
    raf = new RandomAccessFile(f, "rw");
    //傳回與這個檔案有關的唯一FileChannel對象
    fc = raf.getChannel();
  } catch (FileNotFoundException e) {
    Panic.panic(e);
  }

  return new TransactionManagerImpl(raf, fc);
}           

▌定義常量

我們看下TransactionManager接口的實作類TransactionManagerImpl.首先定義一些必要的常量

// XID檔案頭長度
static final int LEN_XID_HEADER_LENGTH = 8;
// 每個事務的占用長度
private static final int XID_FIELD_SIZE = 1;

// 事務的三種狀态
//活動狀态
private static final byte FIELD_TRAN_ACTIVE   = 0;
//已送出狀态
private static final byte FIELD_TRAN_COMMITTED = 1;
//復原狀态
private static final byte FIELD_TRAN_ABORTED  = 2;

// 超級事務，永遠為commited狀态
public static final long SUPER_XID =1;

// XID 檔案字尾
static final String XID_SUFFIX = ".xid";

private RandomAccessFile file;
private FileChannel fc;
private long xidCounter;
//顯示鎖
private Lock counterLock;           

檔案讀寫都采用了 NIO 方式的 FileChannel，FileChannel 提供了一種通過通道來通路檔案的方式，它可以通過帶參數 position(int) 方法定位到檔案的任意位置開始進行操作，還能夠将檔案映射到直接記憶體，提高大檔案的通路效率。關于java的NIO 請參考<<java 高并發核心程式設計(卷1)>>.

▌校驗XID檔案是否合法

構造函數建立了一個 TransactionManager 之後，首先要對 XID 檔案進行校驗，以保證這是一個合法的 XID 檔案。

校驗的方式也很簡單，通過檔案頭的 8 位元組數字反推檔案的理論長度，與檔案的實際長度做對比。如果不同則認為 XID 檔案不合法。

TransactionManagerImpl(RandomAccessFile raf, FileChannel fc) {
  this.file = raf;
  this.fc = fc;
  //顯式鎖
  counterLock = new ReentrantLock();
  checkXIDCounter();
}

/**
 * 檢查XID檔案是否合法
 * 讀取XID_FILE_HEADER中的xidcounter，根據它計算檔案的理論長度，對比實際長度
 */
private void checkXIDCounter() {
  long fileLen = 0;
  try {
    fileLen = file.length();
  } catch (IOException e1) {
    Panic.panic(Error.BadXIDFileException);
  }
  if(fileLen < LEN_XID_HEADER_LENGTH) {
    //對于校驗沒有通過的，會直接通過 panic 方法，強制停機。
    // 在一些基礎子產品中出現錯誤都會如此處理，
    // 無法恢複的錯誤隻能直接停機。
    Panic.panic(Error.BadXIDFileException);
  }

  // java NIO中的Buffer的array()方法在能夠讀和寫之前，必須有一個緩沖區，
  // 用靜态方法 allocate() 來配置設定緩沖區
  ByteBuffer buf = ByteBuffer.allocate(LEN_XID_HEADER_LENGTH);
  try {
    fc.position(0);
    fc.read(buf);
  } catch (IOException e) {
    Panic.panic(e);
  }
  //從檔案開頭8個位元組得到事務的個數
  this.xidCounter = Parser.parseLong(buf.array());
  // 根據事務xid取得其在xid檔案中對應的位置
  long end = getXidPosition(this.xidCounter + 1);
  if(end != fileLen) {
    //對于校驗沒有通過的，會直接通過 panic 方法，強制停機
    Panic.panic(Error.BadXIDFileException);
  }
}           

鎖用的是可重入鎖ReentrantLock,ReentrantLock是JUC包提供的顯式鎖的一個基礎實作類，ReentrantLock類實作了Lock接口，它擁有與synchronized相同的并發性和記憶體語義，但是擁有了限時搶占、可中斷搶占等一些進階鎖特性。關于ReenttrantLock 内容可參考<<java高并發核心程式設計(卷2)>>.

檔案的理論長度：開頭的8個位元組+一個事務狀态所占用的位元組*事務的個數;

通過xid檔案開頭的 8 個位元組（記錄了事務的個數）反推檔案的理論長度與檔案的實際長度做對比。如果不等則認為 XID 檔案不合法。每次建立xid對象都會檢查一次.

對于校驗沒有通過的，會直接通過 panic 方法，強制停機。在一些基礎子產品中出現錯誤都會如此處理，無法恢複的錯誤隻能直接停機。

來擷取 xid 的狀态在檔案中的偏移getXidPosition()方法實作如下:

// 根據事務xid取得其在xid檔案中對應的位置
private long getXidPosition(long xid) {
    return LEN_XID_HEADER_LENGTH + (xid-1)*XID_FIELD_SIZE;
}           

▌開啟事務

begin() 開啟一個事務，并初始化事務的結構，将其存放在 activeTransaction 中，用于檢查和快照使用：

/**
 *begin() 每開啟一個事務，并計算目前活躍的事務的結構，将其存放在 activeTransaction 中，
 * 用于檢查和快照使用：
 * @param level
 * @return
 */
@Override
public long begin(int level) {
  lock.lock();
  try {
    long xid = tm.begin();
    //activeTransaction 目前事務建立時活躍的事務,，如果level!=0,放入t的快照中
    Transaction t = Transaction.newTransaction(xid, level, activeTransaction);
    activeTransaction.put(xid, t);
    return xid;
  } finally {
    lock.unlock();
  }
}           

▌改變事務狀态

事務xid的偏移量=開頭的8個位元組+一個事務狀态所占用的位元組*事務的xid;

通過事務xid計算出記錄該事務狀态的偏移量，再更改狀态。

具體實作如下:

// 更新xid事務的狀态為status
private void updateXID(long xid, byte status) {
  long offset = getXidPosition(xid);
  //每個事務占用長度
  byte[] tmp = new byte[XID_FIELD_SIZE];
  tmp[0] = status;
  ByteBuffer buf = ByteBuffer.wrap(tmp);
  try {
    fc.position(offset);
    fc.write(buf);
  } catch (IOException e) {
    Panic.panic(e);
  }
  try {
    //将資料刷出到磁盤,但不包括中繼資料
    fc.force(false);
  } catch (IOException e) {
    Panic.panic(e);
  }
}           

其中abort()和commit()這是調用了這個方法,

// 送出XID事務
public void commit(long xid) {
  updateXID(xid, FIELD_TRAN_COMMITTED);
}

// 復原XID事務
public void abort(long xid) {
  updateXID(xid, FIELD_TRAN_ABORTED);
}           

▌更新xid Header

每次建立一個事務時，都需要将檔案頭記錄的事務個數+1;

// 将XID加一，并更新XID Header
private void incrXIDCounter() {
  xidCounter ++;
  ByteBuffer buf = ByteBuffer.wrap(Parser.long2Byte(xidCounter));
  //遊标pos， 限制為lim， 容量為cap
  try {
    fc.position(0);
    fc.write(buf);
  } catch (IOException e) {
    Panic.panic(e);
  }
  try {
    fc.force(false);
  } catch (IOException e) {
    Panic.panic(e);
  }
}           

▌判斷事務狀态

根據xid-》擷取記錄事務xid的狀态的offset-》讀取事務xid的狀态-》是否等于status.

// 檢測XID事務是否處于status狀态
private boolean checkXID(long xid, byte status) {
  long offset = getXidPosition(xid);
  ByteBuffer buf = ByteBuffer.wrap(new byte[XID_FIELD_SIZE]);
  try {
    fc.position(offset);
    fc.read(buf);
  } catch (IOException e) {
    Panic.panic(e);
  }
  return buf.array()[0] == status;
}

// 活動狀态判斷
public boolean isActive(long xid) {
  if(xid == SUPER_XID) return false;
  return checkXID(xid, FIELD_TRAN_ACTIVE);
}

// 已送出狀态判斷
public boolean isCommitted(long xid) {
  if(xid == SUPER_XID) return true;
  return checkXID(xid, FIELD_TRAN_COMMITTED);
}

//復原狀态判斷
public boolean isAborted(long xid) {
  if(xid == SUPER_XID) return false;
  return checkXID(xid, FIELD_TRAN_ABORTED);
}           

▌關閉TM

//TM關閉
public void close() {
  try {
    fc.close();
    file.close();
  } catch (IOException e) {
    Panic.panic(e);
  }
}           

▌兩階段鎖實作事務操作：

▌兩階段鎖(2PL)功能介紹

事務排程一般有串行排程和并行排程;首先我們來了解以下幾個概念:

• 并發控制:指多使用者共享的系統中，許多使用者可能同時對同一資料進行操作。
• 排程: 事務的執行次序
• 串行排程: 多個事務依次串行執行，且隻有當一個事務的所有操作都執行完後才執行另一個事務的所有操作。隻要是串行排程，執行的結果都是正确的。

• 并行排程:利用分時的方法同時處理多個事務。但是并行排程的排程結果可能是錯誤的，可能産生不一緻的狀态，包括有：丢失修改，不可重複讀和讀髒資料.

事務并行排程

在一個事務裡面，分為加鎖(lock)階段和解鎖(unlock)階段,也即所有的lock操作都在unlock操作之前,如下圖所示:

事務的加鎖和解鎖兩階段

在實際情況下，SQL是千變萬化、條數不定的,資料庫很難在事務中判定什麼是加鎖階段，什麼是解鎖階段。于是引入了S2PL(Strict-2PL),即:在事務中隻有送出(commit)或者復原(rollback)時才是解鎖階段， 其餘時間為加鎖階段。引入2PL是為了保證事務的隔離性，即多個事務在并發的情況下等同于串行的執行。

2階段加鎖 加鎖階段

第一階段是獲得封鎖的階段，稱為擴充階段：其實也就是該階段可以進入加鎖操作，在對任何資料進行讀操作之前要申請獲得S鎖，在進行寫操作之前要申請并獲得X鎖，加鎖不成功，則事務進入等待狀态，直到加鎖成功才繼續執行。就是加鎖後就不能解鎖了。

第二階段是釋放封鎖的階段，稱為收縮階段：當事務釋放一個封鎖後，事務進入封鎖階段，在該階段隻能進行解鎖而不能再進行加鎖操作。

▌兩階段鎖(2PL)事務實作

mysql中事務預設是隐式事務，執行insert、update、delete操作的時候，資料庫自動開啟事務、送出或復原事務。

是否開啟隐式事務是由變量autocommit控制的。

是以事務分為隐式事務和顯式事務。

隐式事務是由事務自動開啟、送出或復原，比如insert、update、delete語句，事務的開啟、送出或復原由mysql内部自動控制的。

顯式事務是需要手動開啟、送出或復原，由開發者自己控制。

▌手寫兩階段鎖(2PL)事務：

在實作事務隔離級别之前, 我們需要先來讨論一下 Version Manager(VM).

VM是基于兩階段鎖協定實作了排程序列的可串行化，并實作了MVCC 以消除讀寫阻塞。

同時實作了兩種隔離級别.VM 是手寫資料庫 MYDB的事務和資料版本管理核心.

▌事務存儲

對于一條記錄來說，MYDB 使用 Entry 類維護了其結構。

雖然理論上，MVCC 實作了多版本，但是在實作中，VM 并沒有提供 Update 操作，對于字段的更新操作由後面的表和字段管理（TBM）實作。

是以在 VM 的實作中，一條記錄隻有一個版本。

一條記錄存儲在一條 Data Item 中，是以 Entry 中儲存一個 DataItem 的引用即可：

public class Entry {

  private static final int OF_XMIN = 0;
  private static final int OF_XMAX = OF_XMIN+8;
  private static final int OF_DATA = OF_XMAX+8;

  private long uid;
  private DataItem dataItem;
  private VersionManager vm;

  public static Entry newEntry(VersionManager vm, DataItem dataItem, long uid) {
    Entry entry = new Entry();
    entry.uid = uid;
    entry.dataItem = dataItem;
    entry.vm = vm;
    return entry;
  }

  public static Entry loadEntry(VersionManager vm, long uid) throws Exception {
    DataItem di = ((VersionManagerImpl)vm).dm.read(uid);
    return newEntry(vm, di, uid);
  }

  public void release() {
    ((VersionManagerImpl)vm).releaseEntry(this);
  }

  public void remove() {
    dataItem.release();
  }
}           

規定一條Entry中存儲的資料格式如下:

[XMIN]  [XMAX]  [DATA]
8個位元組  8個位元組           

XMIN 是建立該條記錄（版本）的事務編号，而 XMAX 則是删除該條記錄（版本）的事務編号。DATA 就是這條記錄持有的資料。

根據這個結構，在建立記錄時調用的 wrapEntryRaw()方法如下：

public static byte[] wrapEntryRaw(long xid, byte[] data) {
  byte[] xmin = Parser.long2Byte(xid);
  byte[] xmax = new byte[8];
  return Bytes.concat(xmin, xmax, data);
}           

同樣，如果要擷取記錄中持有的資料，也就需要按照這個結構來解析：

// 以拷貝的形式傳回内容
public byte[] data() {
  dataItem.rLock();
  try {
    SubArray sa = dataItem.data();
    byte[] data = new byte[sa.end - sa.start - OF_DATA];
    System.arraycopy(sa.raw, sa.start+OF_DATA, data, 0, data.length);
    return data;
  } finally {
    dataItem.rUnLock();
  }
}           

這裡以拷貝的形式傳回資料，如果需要修改的話，需要遵循一定的流程：在修改之前需要調用 before() 方法，想要撤銷修改時，調用 unBefore() 方法，在修改完成後，調用 after() 方法。

整個流程，主要是為了儲存前相資料，并及時落日志。DM 會保證對 DataItem 的修改是原子性的。

@Override
public void before() {
  wLock.lock();
  pg.setDirty(true);
  System.arraycopy(raw.raw, raw.start, oldRaw, 0, oldRaw.length);
}

@Override
public void unBefore() {
  System.arraycopy(oldRaw, 0, raw.raw, raw.start, oldRaw.length);
  wLock.unlock();
}

@Override
public void after(long xid) {
  dm.logDataItem(xid, this);
  wLock.unlock();
}           

在設定 XMAX 的值中展現了如果需要修改的話,要遵循一定的規則, 而且這個版本對每一個XMAX之後的事務都是不可見的,等價于删除了. setXmax代碼如下:

public void setXmax(long xid) {
  dataItem.before();
  try {
    SubArray sa = dataItem.data();
    System.arraycopy(Parser.long2Byte(xid), 0, sa.raw, sa.start+OF_XMAX, 8);
  } finally {
    dataItem.after(xid);
  }
}           

▌開啟事務

begin() 每開啟一個事務，計算目前活躍的事務的結構，将其存放在 activeTransaction 中，

@Override
public long begin(int level) {
  lock.lock();
  try {
    long xid = tm.begin();
    Transaction t = Transaction.newTransaction(xid, level, activeTransaction);
    activeTransaction.put(xid, t);
    return xid;
  } finally {
    lock.unlock();
  }
}           

▌送出事務

commit() 方法送出一個事務，主要就是 free 掉相關的結構，并且釋放持有的鎖，并修改 TM 狀态，并把該事務從activeTransaction中移除。

@Override
public void commit(long xid) throws Exception {
  lock.lock();
  Transaction t = activeTransaction.get(xid);
  lock.unlock();

  try {
    if(t.err != null) {
      throw t.err;
    }
  } catch(NullPointerException n) {
    System.out.println(xid);
    System.out.println(activeTransaction.keySet());
    Panic.panic(n);
  }

  lock.lock();
  activeTransaction.remove(xid);
  lock.unlock();

  lt.remove(xid);
  tm.commit(xid);
}           

▌復原事務

abort 事務的方法則有兩種，手動和自動。

手動指的是調用 abort() 方法，而自動，則是在事務被檢測出出現死鎖時，會自動撤銷復原事務；或者出現版本跳躍時，也會自動復原：

/**
 * 復原事務
 * @param xid
 */
@Override
public void abort(long xid) {
  internAbort(xid, false);
}

private void internAbort(long xid, boolean autoAborted) {
  lock.lock();
  Transaction t = activeTransaction.get(xid);
  //手動復原
  if(!autoAborted) {
    activeTransaction.remove(xid);
  }
  lock.unlock();

  //自動復原
  if(t.autoAborted) return;
  lt.remove(xid);
  tm.abort(xid);
}           

▌删除事務

在一個事務 commit 或者 abort 時，就可以釋放所有它持有的鎖，并将自身從等待圖中删除。

并從等待隊列中選擇一個xid來占用uid.

解鎖時，将該 Lock 對象 unlock 即可，這樣其他業務線程就擷取到了鎖，就可以繼續執行了。

public void remove(long xid) {
  lock.lock();
  try {
    List<Long> l = x2u.get(xid);
    if(l != null) {
      while(l.size() > 0) {
        Long uid = l.remove(0);
        selectNewXID(uid);
      }
    }
    waitU.remove(xid);
    x2u.remove(xid);
    waitLock.remove(xid);

  } finally {
    lock.unlock();
  }
}

// 從等待隊列中選擇一個xid來占用uid
private void selectNewXID(long uid) {
  u2x.remove(uid);
  List<Long> l = wait.get(uid);
  if(l == null) return;
  assert l.size() > 0;

  while(l.size() > 0) {
    long xid = l.remove(0);
    if(!waitLock.containsKey(xid)) {
      continue;
    } else {
      u2x.put(uid, xid);
      Lock lo = waitLock.remove(xid);
      waitU.remove(xid);
      lo.unlock();
      break;
    }
  }

  if(l.size() == 0) wait.remove(uid);
}           

▌插入資料

insert() 則是将資料包裹成 Entry，交給 DM 插入即可：

@Override
public long insert(long xid, byte[] data) throws Exception {
  lock.lock();
  Transaction t = activeTransaction.get(xid);
  lock.unlock();

  if(t.err != null) {
    throw t.err;
  }

  byte[] raw = Entry.wrapEntryRaw(xid, data);
  return dm.insert(xid, raw);
}           

▌讀取事務

read() 方法讀取一個 entry，根據隔離級别判斷下可見性即可.

@Override
public byte[] read(long xid, long uid) throws Exception {
  lock.lock();
  //目前事務xid讀取時的快照資料
  Transaction t = activeTransaction.get(xid);
  lock.unlock();

  if(t.err != null) {
    throw t.err;
  }

  Entry entry = null;
  try {
    //通過uid找要讀取的事務dataItem
    entry = super.get(uid);
  } catch(Exception e) {
    if(e == Error.NullEntryException) {
      return null;
    } else {
      throw e;
    }
  }
  try {
    if(Visibility.isVisible(tm, t, entry)) {
      return entry.data();
    } else {
      return null;
    }
  } finally {
    entry.release();
  }
}           

▌事務的ACID特性：

事務是通路并更新資料庫中各種資料項的一個程式執行單元。事務的目的是要麼都修改，要麼都不做。

大多數場景下， 應用都隻需要操作單一的資料庫，這種情況下的事務稱之為本地事務（Local Transaction）。

本地事務的ACID特性是資料庫直接提供支援。

為了達成本地事務，Mysql 做了很多工作，比如復原日志、重做日志、MVCC 、讀寫鎖等。

對于InnoDB存儲引擎而言，其預設的事務隔離級别是Repeatable read，完全遵循和滿足事務的ACID特性。

ACID是原子性(Atomicity）、一緻性（consistency）、隔離性（isolation）、持久性（durability） 4個單詞的縮寫。

InnoDB是通過日志和鎖來保證事務的ACID特性：

• 通過資料庫鎖的機制，保證事務的隔離性；
• 通過Redo Log（重做日志）來保證事務的隔離性；
• 通過Undo Log（撤銷日志）來保證事務的原子性和一緻性；

▌原子性(Atomicity）

事務必須是一個原子的操作序列單元， 事務中包含的各項操作在一次執行過程中，要麼全部成功，要麼全部不執行，任何一項失敗，整個事務復原，隻有全部都執行成功，整個事務才算成功。

在操作任何資料之前， 首先将資料備份到Undo Log，然後進行資料的修改。如果出現了錯誤或者使用者執行了了Rollback 語句，系統可以利用Undo Log 中的備份将資料恢複到事務開始之前的狀态，以此保證資料的原子性。

▌一緻性（consistency）

事務的執行不能破壞資料庫資料的完整性和一緻性，事務在執行之前和之後，資料庫都必須處于一緻性狀态。

一緻性包括兩方面的内容，分别是限制一緻性和資料一緻性；

• 限制一緻性： 建立表結構時所指定的外鍵、check（mysql不支援）、唯一索引等限制。
• 資料一緻性： 是一個綜合性的規定，因為它是由原子性、持久性、隔離性共同保證的結果，而不是單單依賴于某一種技術。

▌隔離性（isolation）

在并發情況中，并發的事務是互相隔離的，一個事務的執行不能被其他事務幹擾。

即不同的事務并發操作相同的資料時，每個事務都有各自完整的資料空間，即一個事務内部的操作及使用的資料對其他并發事務是個隔離的，并發執行的各個事務之間不能互相幹擾。

▌持久性（durability）

持久性也稱為永久性（permanence），指一個事務一旦送出，它對資料庫中對應資料的狀态變更就應該是永久性的。 即使發生系統崩潰或者機器當機，隻要資料庫能夠重新開機，那麼一定能夠将其恢複到事務成功結束時的狀态。

Redo Log記錄的是新資料的備份，在事務送出前，隻要将Redo Log 持久化即可，不需要将資料持久化，當系統崩潰時，雖然資料咩有持久化，但是Redo Log 已經持久化。系統可以根據Redo Log的内容，将所有資料恢複到崩潰之前的狀态，這就是使用Redo Log 保障資料的持久化的過程。

總結

資料的完整性主要展現的是一緻性特性，資料的完整性是通過原子性、隔離性、持久性來保證的，這三個特性又是通過redo Log 和Undo Log 來保證的。ACID 特性的關系下圖所示：

▌死鎖：

在mysql中，兩階段鎖協定(2PL)通常包括擴張和收縮兩個階段。在擴張階段,事務将擷取鎖,但不能釋放任何鎖。在收縮階段，可以釋放現有的鎖但不能擷取新的鎖,這種規定存在着死鎖的風險。

例如：當T1’在擴張階段，擷取了Y的讀鎖，并讀取了Y，此時想要去擷取X的寫鎖，卻發現T2’的讀鎖鎖定了X，而T2’也想要擷取Y的寫鎖。簡而言之，T1’不得到X是不會釋放Y的，T2’不得到Y也是不會釋放X的，這便陷入了循環，便形成了死鎖。

2PL 會阻塞事務，直至持有鎖的線程釋放鎖。可以将這種等待關系抽象成有向邊，例如：Tj 在等待 Ti，就可以表示為 Tj --> Ti。這樣，無數有向邊就可以形成一個圖。檢測死鎖隻需要檢視這個圖中是否有環即可。

▌死鎖檢測

建立一個LockTable對象，在記憶體中維護這張圖，維護結構如下:

public class LockTable {
  private Map<Long, List<Long>> x2u;  // 某個XID已經獲得的資源的UID清單
  private Map<Long, Long> u2x;        // UID被某個XID持有
  private Map<Long, List<Long>> wait; // 正在等待UID的XID清單
  private Map<Long, Lock> waitLock;   // 正在等待資源的XID的鎖
  private Map<Long, Long> waitU;      // XID正在等待的UID
  ......
}           

在每次出現等待的情況時，就嘗試向圖中增加一條邊，并進行死鎖檢測。如果檢測到死鎖，就撤銷這條邊，不允許添加，并撤銷該事務。

// 不需要等待則傳回null，否則傳回鎖對象
// 會造成死鎖則抛出異常
public Lock add(long xid, long uid) throws Exception {
  lock.lock();
  try {
    //某個xid已經獲得的資源的UID清單，如果在這個清單裡面，則不造成死鎖，也不需要等待
    if(isInList(x2u, xid, uid)) {
      return null;
    }
    //表示有了一個新的uid，則把uid加入到u2x和x2u裡面，不死鎖，不等待
    // u2x  uid被某個xid占有
    if(!u2x.containsKey(uid)) {
      u2x.put(uid, xid);
      putIntoList(x2u, xid, uid);
      return null;
    }
    //以下就是需要等待的情況
    //多個事務等待一個uid的釋放
    waitU.put(xid, uid);
    //putIntoList(wait, xid, uid);
    putIntoList(wait, uid, xid);
    //造成死鎖
    if(hasDeadLock()) {
      //從等待清單裡面删除
      waitU.remove(xid);
      removeFromList(wait, uid, xid);
      throw Error.DeadlockException;
    }
    //從等待清單裡面删除
    Lock l = new ReentrantLock();
    l.lock();
    waitLock.put(xid, l);
    return l;

  } finally {
    lock.unlock();
  }
}           

調用 add，如果不需要等待則進行下一步，如果需要等待的話，會傳回一個上了鎖的 Lock 對象。調用方在擷取到該對象時，需要嘗試擷取該對象的鎖，由此實作阻塞線程的目的，

try {
  l = lt.add(xid, uid);
} catch(Exception e) {
  t.err = Error.ConcurrentUpdateException;
  internAbort(xid, true);
  t.autoAborted = true;
  throw t.err;
}
if(l != null) {
  l.lock();
  l.unlock();
}           

▌判斷死鎖

查找圖中是否有環的算法實際上就是一個深搜，需要注意的是這個圖不一定是連通圖。具體的思路就是為每個節點設定一個通路戳，都初始化為 1，随後周遊所有節點，以每個非 1 的節點作為根進行深搜，并将深搜該連通圖中遇到的所有節點都設定為同一個數字，不同的連通圖數字不同。這樣，如果在周遊某個圖時，遇到了之前周遊過的節點，說明出現了環。

判斷死鎖的具體實作如下:

private boolean hasDeadLock() {
  xidStamp = new HashMap<>();
  stamp = 1;
  System.out.println("xid已經持有哪些uid x2u="+x2u);//xid已經持有哪些uid
  System.out.println("uid正在被哪個xid占用 u2x="+u2x);//uid正在被哪個xid占用

  //已經拿到鎖的xid
  for(long xid : x2u.keySet()) {
    Integer s = xidStamp.get(xid);
    if(s != null && s > 0) {
      continue;
    }
    stamp ++;
    System.out.println("xid"+xid+"的stamp是"+s);
    System.out.println("進入深搜");
    if(dfs(xid)) {
      return true;
    }
  }
  return false;
}

private boolean dfs(long xid) {
  Integer stp = xidStamp.get(xid);
  //周遊某個圖時，遇到了之前周遊過的節點，說明出現了環
  if(stp != null && stp == stamp) {
    return true;
  }
  if(stp != null && stp < stamp) {
    return false;
  }
  //每個已獲得資源的事務一個獨特的stamp
  xidStamp.put(xid, stamp);
  System.out.println("xidStamp找不到該xid，加入後xidStamp變為"+xidStamp);
  //已獲得資源的事務xid正在等待的uid
  Long uid = waitU.get(xid);
  System.out.println("xid"+xid+"正在等待的uid是"+uid);
  if(uid == null){
    System.out.println("未成環，退出深搜");
    //xid沒有需要等待的uid,無死鎖
    return false;
  }
  //xid需要等待的uid被哪個xid占用了
  Long x = u2x.get(uid);
  System.out.println("xid"+xid+"需要的uid被"+"xid"+x+"占用了");
  System.out.println("=====再次進入深搜"+"xid"+x+"====");
  assert x != null;
  return dfs(x);
}           

在一個事務 commit 或者 abort 時，就可以釋放所有它持有的鎖，并将自身從等待圖中删除。

public void remove(long xid) {
  lock.lock();
  try {
    List<Long> l = x2u.get(xid);
    if(l != null) {
      while(l.size() > 0) {
        Long uid = l.remove(0);
        selectNewXID(uid);
      }
    }
    waitU.remove(xid);
    x2u.remove(xid);
    waitLock.remove(xid);

  } finally {
    lock.unlock();
  }
}           

while 循環釋放掉了這個線程所有持有的資源的鎖，這些資源可以被等待的線程所擷取：

// 從等待隊列中選擇一個xid來占用uid
private void selectNewXID(long uid) {
  u2x.remove(uid);
  List<Long> l = wait.get(uid);
  if(l == null) return;
  assert l.size() > 0;

  while(l.size() > 0) {
    long xid = l.remove(0);
    if(!waitLock.containsKey(xid)) {
      continue;
    } else {
      u2x.put(uid, xid);
      Lock lo = waitLock.remove(xid);
      waitU.remove(xid);
      lo.unlock();
      break;
    }
  }

  if(l.size() == 0) wait.remove(uid);
}           

從 List 開頭開始嘗試解鎖，還是個公平鎖。解鎖時，将該 Lock 對象 unlock 即可，這樣業務線程就擷取到了鎖，就可以繼續執行了。

測試代碼如下:

public static void main(String[] args) throws Exception {
  LockTable lock = new LockTable();
  lock.add(1L,3L);
  lock.add(2L,4L);
  lock.add(3L,5L);
  lock.add(1L,4L);

  System.out.println("+++++++++++++++++++++++");
  lock.add(2L,5L);
  System.out.println("++++++++++++++++");
  lock.add(3L,3L);
  System.out.println(lock.hasDeadLock());
}           

執行結果如下:

xid已經持有哪些uid x2u={1=[3], 2=[4], 3=[5]}
uid正在被哪個xid占用 u2x={3=1, 4=2, 5=3}
xid1的stamp是null
進入深搜
xidStamp找不到該xid，加入後xidStamp變為{1=2}
xid1正在等待的uid是4
xid1需要的uid被xid2占用了
=====再次進入深搜xid2====
xidStamp找不到該xid，加入後xidStamp變為{1=2, 2=2}
xid2正在等待的uid是null
未成環，退出深搜
xid3的stamp是null
進入深搜
xidStamp找不到該xid，加入後xidStamp變為{1=2, 2=2, 3=3}
xid3正在等待的uid是null
未成環，退出深搜
+++++++++++++++++++++++
xid已經持有哪些uid x2u={1=[3], 2=[4], 3=[5]}
uid正在被哪個xid占用 u2x={3=1, 4=2, 5=3}
xid1的stamp是null
進入深搜
xidStamp找不到該xid，加入後xidStamp變為{1=2}
xid1正在等待的uid是4
xid1需要的uid被xid2占用了
=====再次進入深搜xid2====
xidStamp找不到該xid，加入後xidStamp變為{1=2, 2=2}
xid2正在等待的uid是5
xid2需要的uid被xid3占用了
=====再次進入深搜xid3====
xidStamp找不到該xid，加入後xidStamp變為{1=2, 2=2, 3=2}
xid3正在等待的uid是null
未成環，退出深搜
++++++++++++++++
xid已經持有哪些uid x2u={1=[3], 2=[4], 3=[5]}
uid正在被哪個xid占用 u2x={3=1, 4=2, 5=3}
xid1的stamp是null
進入深搜
xidStamp找不到該xid，加入後xidStamp變為{1=2}
xid1正在等待的uid是4
xid1需要的uid被xid2占用了
=====再次進入深搜xid2====
xidStamp找不到該xid，加入後xidStamp變為{1=2, 2=2}
xid2正在等待的uid是5
xid2需要的uid被xid3占用了
=====再次進入深搜xid3====
xidStamp找不到該xid，加入後xidStamp變為{1=2, 2=2, 3=2}
xid3正在等待的uid是3
xid3需要的uid被xid1占用了
=====再次進入深搜xid1====
           

▌高并發場景如何做事務隔離：

▌事務的隔離級别功能分析

鎖和多版本控制（MVCC）技術就是用于保障隔離性的， InnoDB支援的隔離性有4種，從低到高分别是

• 讀未送出（READ UNCOMMITTED）
• 讀已送出（READ COMMITTED）
• 可重複讀（REPEATABLE READ）
• 可串行化（SERIALIZABLE）。

▌讀未送出（READ UNCOMMITTED）

在讀未送出隔離級别下，允許髒讀的情況發生。未送出意味着這些資料可能會復原，讀到了不一定最終存在的資料。讀未送出隔離級别容易出現髒讀問題;

髒讀指的就是在不同的事務下，目前事務可以讀到另外事務未送出的資料，簡單說就是讀到髒資料。 而所謂的髒資料是指事務對緩沖池中行記錄的修改，并且還沒有被送出。

如果讀到了髒資料，即一個事務可以讀到另一個事務中未送出的資料，顯然違反了資料庫的隔離性。

髒讀發生的條件是需要事務的隔離級别為Read uncommitted， 在生産環境中，絕大部分資料庫至少會設定成Read Committed ，是以在生産環境下發送的機率很小。

▌讀已送出（READ COMMITTED）

隻允許讀到已送出的資料， 即事務A在将n從0累加到10的過程中， B無法看到n的中國值，隻能看到10.

在已送出隔離級别下，禁止了髒讀， 但是運作不可重複讀的情況發生。

讀已送出滿足了隔離的簡單定義:一個事務隻能看見已經送出事務所做的改變.

oracle 、sql server 預設的隔離級别是讀已送出。

讀已送出隔離級别容易出現不可重複讀問題.不可重複讀是指一個事務内多次讀取同一資料集合的資料不一樣的情況。

事務A 多次讀取同一資料，但事務B在事務A多次讀取的過程中，對資料作了更新并比較，導緻事務A多次讀取同一資料時，結果不一緻了。

髒讀和不可重複讀的差別是：髒讀讀到的是未送出的資料，而不可重複讀讀到的确實已送出的資料，但是違反了資料庫事務一緻性原則。

在一般情況下，不可重複讀的問題是可以接受的，因為其讀到的是已經送出的資料， 本身不會帶來很大的問題。Oracle、SQL server 資料庫事務的預設隔離級别設定為Read Committed，RC 隔離級别是允許不可重複讀的現象。Mysql 預設的隔離級别是RR， 通過使用Next-Key Lock 算法來避免不可重複讀的現象。

不可重複讀和幻讀的差別是：

• 不可重複讀的重點在修改: 同樣的條件，第一次讀取過的資料，再次讀取出來發現值不一樣了。
• 幻讀的重點在新增或删除：同樣的條件，第一次和第二次讀取出來的記錄數不一樣。

▌可重複讀（REPEATABLE READ）

保證在事務過程中，多次讀取同一資料時，其值都和事務開始時刻時是一緻的。

在可重複讀隔離級别下，禁止髒讀和不可重複讀，但是存在幻讀。

幻讀是指一個事務的兩次查詢中資料筆數不一緻，例如有一個事務查詢了幾列(Row)資料，而另一個事務卻在此時插入了新的幾列資料，先前的事務在接下來的查詢中，就會發現有幾列資料是它先前所沒有的。

mysql 預設的隔離級别是 可重複讀，檢視mysql 目前資料庫的事務隔離級别指令如下

show variables like 'tx_isolation';
或
select @@tx_isolation;           

設定事務隔離級别：

set tx_isolation='READ-UNCOMMITTED';
set tx_isolation='READ-COMMITTED';
set tx_isolation='REPEATABLE-READ';
set tx_isolation='SERIALIZABLE';           

可重複讀在理論上,會導緻另一個棘手的問題:幻讀. 幻讀至目前使用者讀取某一範圍的資料行時 ,另一個事務又在該範圍内插入新行,當使用者再讀取該範圍的資料行時 ,會發現有新的"幻影"行. InnoDB存儲引擎通過多版本并發控制（MVCC，Multiversion Concurrency Control）機制解決了該問題。

▌可串行化（SERIALIZABLE）

最嚴格的事務，要求所有事務被串行執行，并不能并發執行.

它通過強制事務排序,使之不可能互相沖突,進而解決幻讀問題.

換句話說就是在每個讀的資料行上加上共享鎖.

可串行可能導緻大量的逾時現象和鎖競争.

總結：

隔離級别	髒讀（Dirty Read）	不可重複讀（NoRepeatable Read）	幻讀（Phantom Read）
讀未送出（Read uncommitted）	可能	可能	可能
讀已送出(Read committed	不可能	可能	可能
可重複讀（Repeatable read）	不可能	不可能	可能
可串行化（Serializable）	不可能	不可能	不可能

▌MVCC：

MVCC全稱是Multi-Version Concurrent Control，即多版本并發控制,其原理與copyonwrite類似。

▌并發事務帶來的問題

▌讀-讀

即并發事務相繼讀取同一記錄.

因為讀取記錄并不會對記錄造成任何影響，是以同個事務并發讀取同一記錄也就不存在任何安全問題，是以允許這種操作。不存在任何問題，也不需要并發控制.

▌寫-寫

即并發事務相繼對同一記錄做出修改.

如果允許并發事務都讀取同一記錄，并相繼基于舊估對這一記錄做出修改，那麼就會出現前一個事務所做的修改被後面事務的修改覆寫，即出現送出覆寫的問題。

另外一種情況，并發事務相繼對同一記錄做出修改，其中一個事務送出之後之後另一個事務發生復原，這樣就會出現已送出的修改因為復原而丢失的問題，即復原覆寫問題.

是以是存線上程安全問題的,兩種情況都可能存在更新丢失問題.

▌寫-讀或讀-寫

即兩個并發事務對同一記錄分别進行讀操作和寫操作。

如果一個事務讀取了另一個事務尚未送出的修政記錄，那麼就出現了髒讀的問題；

如果我們加以控制使得一個事務隻能讀取其他已送出事務的修改的資料，那麼這個事務在另一個事務送出修改前後讀取到的資料是不一樣的，這就意味看發生了不可重複讀；

如果一個事務根據一些條件查詢到一些記錄，之後另一事物向表中插入了一些記錄，原先的事務以相同條件再次查詢時發現得到的結果跟第一次查詞得到的結果不一緻，這就意味着發生了幻讀。

針對寫-讀或讀-寫出現的問題,MySQL的InnoDB實作了MVCC來更好地處理讀寫沖突，可以做到即使存在并發讀寫，也可以不用加鎖，實作"非阻塞并發讀"。

那麼,總結一下,需要MVCC的原因是由于資料庫通常使用鎖來實作隔離性,最原生的鎖,鎖住一個資源後會禁止其他任何線程通路統一資源。但是很多應用的一個特點是讀多寫少的場景，很多資料的讀取次數遠大于修改的次數,而讀取資料間互相排斥顯得不是很必要.是以就使用了一種讀寫鎖的方法，讀鎖和讀鎖之間不互斥，而寫鎖和寫鎖、讀鎖都互斥。這樣就很大提升了系統的并發能力。

之後人們發現并發讀還是不夠，又提出了能不能讓讀寫之間也不沖突的方法，就是讀取資料時通過一種類似快照的方式将資料儲存下來，這樣讀鎖就和寫鎖不沖突了，不同的事務session會看到自己特定版本的資料。當然快照是一種概念模型，不同的資料庫可能用不同的方式來實作這種功能。

在MVCC協定下，每個讀操作, 會看到一個一緻性的snapshot 快照，并且可以實作非阻塞的讀。讀這個snapshot 快照，不用加鎖。除了snapshot 快照版本之外， MVCC允許資料具有多個版本，版本編号可以是時間戳，或者是全局遞

增的事務ID，在同一個時間點，不同的事務看到的資料是不同的。

首先,了解MVCC 之前,我們需要明确兩個定義

• 目前讀：讀取的資料是最新版本，讀取資料時還要保證其他并發事務不會修改目前的資料，目前讀會對讀取的記錄加鎖。比如：select …… lock in share mode（共享鎖）、select …… for update | update | insert | delete（排他鎖）
• 快照讀：每一次修改資料，都會在 undo log 中存有快照記錄，這裡的快照，就是讀取undo log中的某一版本的快照。這種方式的優點是可以不用加鎖就可以讀取到資料，缺點是讀取到的資料可能不是最新的版本。一般的查詢都是快照讀，比如：select * from t_user where id=1; 在MVCC中的查詢都是快照度。

▌mvcc 的實作原理

MySQL中MVCC主要是通過行記錄中的隐藏字段（隐藏主鍵 row_id、事務ID trx_id、復原指針 roll_pointer）、undo log（版本鍊）、ReadView（一緻性讀視圖）來實作的。

▌隐藏字段

MySQL中，在每一行記錄中除了自定義的字段，還有一些隐藏字段：

• row_id：當資料庫表沒定義主鍵時，InnoDB會以row_id為主鍵生成一個聚集索引。
• trx_id：事務ID記錄了新增/最近修改這條記錄的事務id，事務id是自增的。
• roll_pointer：復原指針指向目前記錄的上一個版本（在 undo log 中）。

▌ReadView

ReadView一緻性視圖主要是由兩部分組成：所有未送出事務的ID數組和已經建立的最大事務ID組成。比如：[100,200],300。事務100和200是目前未送出的事務，而事務300是目前建立的最大事務（已經送出了）。當執行SELECT語句的時候會建立ReadView，但是在讀取已送出和可重複讀兩個事務級别下，生成ReadView的政策是不一樣的：讀取已送出級别是每執行一次SELECT語句就會重新生成一份ReadView，而可重複讀級别是隻會在第一次SELECT語句執行的時候會生成一份，後續的SELECT語句會沿用之前生成的ReadView（即使後面有更新語句的話，也會繼續沿用）。

ReadView 就是MVCC在對資料進行快照讀時，會産生的一個"讀視圖"。ReadView中有4個比較重要的變量：

• m_ids：活躍事務id清單，目前系統中所有活躍的（也就是沒送出的）事務的事務id清單。
• min_trx_id：m_ids 中最小的事務id。
• max_trx_id：生成 ReadView 時，系統應該配置設定給下一個事務的id（注意不是 m_ids 中最大的事務id），也就是m_ids 中的最大事務id + 1 。
• creator_trx_id：生成該 ReadView 的事務的事務id。

▌版本鍊

修改資料的時候，會向 redo log 中記錄修改的頁内容（為了在資料庫當機重新開機後恢複對資料庫的操作），也會向 undo log 記錄資料原來的快照（用于復原事務）。undo log有兩個作用，除了用于復原事務，還用于實作MVCC。

用一個簡單的例子來畫一下MVCC中用到的undo log版本鍊的邏輯圖：

當事務100（trx_id=100）執行了 insert into t_user values(1,'彎彎',30); 之後：

當事務102（trx_id=102）執行了 update t_user set name='李四' where id=1; 之後：

當事務102（trx_id=102）執行了 update t_user set name='王五' where id=1; 之後：

而具體版本鍊的比對規則如下，首先從版本鍊中拿出最上面第一個版本的事務ID開始逐個往下進行比對：

具體版本鍊

（其中min_id指向ReadView中未送出事務數組中的最小事務ID，而max_id指向ReadView中的已經建立的最大事務ID）

某個事務進行快照讀時可以讀到哪個版本的資料，ReadView 的規則如下：

（1）當版本鍊中記錄的 trx_id 等于目前事務id（trx_id = creator_trx_id）時，說明版本鍊中的這個版本是目前事務修改的，是以該快照記錄對目前事務可見。

（2）當版本鍊中記錄的 trx_id 小于活躍事務的最小id（trx_id < min_trx_id）時，說明版本鍊中的這條記錄已經送出了，是以該快照記錄對目前事務可見。

（3）當版本鍊中記錄的 trx_id 大于下一個要配置設定的事務id（trx_id > max_trx_id）時，該快照記錄對目前事務不可見。

（4）當版本鍊中記錄的 trx_id 大于等于最小活躍事務id且版本鍊中記錄的trx_id小于下一個要配置設定的事務id（min_trx_id<= trx_id < max_trx_id）時，如果版本鍊中記錄的 trx_id 在活躍事務id清單 m_ids 中，說明生成 ReadView 時，修改記錄的事務還沒送出，是以該快照記錄對目前事務不可見；否則該快照記錄對目前事務可見。

當事務對 id=1 的記錄進行快照讀時select * from t_user where id=1，在版本鍊的快照中，從最新的一條記錄開始，依次判斷這4個條件，直到某一版本的快照對目前事務可見，否則繼續比較上一個版本的記錄。

MVCC主要是用來解決RU隔離級别下的髒讀和RC隔離級别下的不可重複讀的問題，是以MVCC隻在RC（解決髒讀）和RR（解決不可重複讀）隔離級别下生效，也就是MySQL隻會在RC和RR隔離級别下的快照讀時才會生成ReadView。

差別就是，在RC隔離級别下，每一次快照讀都會生成一個最新的ReadView；在RR隔離級别下，隻有事務中第一次快照讀會生成ReadView，之後的快照讀都使用第一次生成的ReadView。

MySQL 通過 MVCC，降低了事務的阻塞機率。

例如：T1 想要更新記錄 X 的值，于是 T1 需要首先擷取 X 的鎖，接着更新，也就是建立了一個新的 X 的版本，假設為 x3。

假設 T1 還沒有釋放 X 的鎖時，T2 想要讀取 X 的值，這時候就不會阻塞，MYDB 會傳回一個較老版本的 X，例如 x2。這樣最後執行的結果，就等價于，T2 先執行，T1 後執行，排程序列依然是可串行化的。如果 X 沒有一個更老的版本，那隻能等待 T1 釋放鎖了。

是以隻是降低了機率。

▌手寫事務隔離級别：

如果一個記錄的最新版本被加鎖，當另一個事務想要修改或讀取這條記錄時，MYDB 就會傳回一個較舊的版本的資料。

這時就可以認為，最新的被加鎖的版本，對于另一個事務來說，是不可見的。

▌已送出讀

即事務在讀取資料時, 隻能讀取已經送出事務産生的資料。

版本的可見性與事務的隔離度是相關的。

MYDB 支援的最低的事務隔離程度，是“讀送出”（Read Committed），即事務在讀取資料時, 隻能讀取已經送出事務産生的資料。保證最低的讀送出的好處，第四章中已經說明（防止級聯復原與 commit 語義沖突）。

MYDB 實作讀送出，為每個版本維護了兩個變量，就是前面提到的 XMIN 和 XMAX：

• XMIN：建立該版本的事務編号
• XMAX：删除該版本的事務編号

XMIN 應當在版本建立時填寫，而 XMAX 則在版本被删除，或者有新版本出現時填寫。

XMAX 這個變量，也就解釋了為什麼 DM 層不提供删除操作，當想删除一個版本時，隻需要設定其 XMAX，這樣，這個版本對每一個 XMAX 之後的事務都是不可見的，也就等價于删除了。

在讀送出下，版本對事務的可見性邏輯如下：

(XMIN == Ti and                             // 由Ti建立且
    XMAX == NULL                            // 還未被删除
)
or                                          // 或
(XMIN is commited and                       // 由一個已送出的事務建立且
    (XMAX == NULL or                        // 尚未删除或
    (XMAX != Ti and XMAX is not commited)   // 由一個未送出的事務删除
))           

若條件為 true，則版本對 Ti 可見。那麼擷取 Ti 适合的版本，隻需要從最新版本開始，依次向前檢查可見性，如果為 true，就可以直接傳回。

以下方法判斷某個記錄對事務 t 是否可見：

private static boolean readCommitted(TransactionManager tm, Transaction t, Entry e) {
  long xid = t.xid;
  long xmin = e.getXmin();
  long xmax = e.getXmax();
  if(xmin == xid && xmax == 0) return true;

  if(tm.isCommitted(xmin)) {
    if(xmax == 0) return true;
    if(xmax != xid) {
      if(!tm.isCommitted(xmax)) {
        return true;
      }
    }
  }
  return false;
}           

▌可重複讀

不可重複度，會導緻一個事務在執行期間對同一個資料項的讀取得到不同結果。如下面的結果，加入 X 初始值為 0：

T1 begin
R1(X) // T1 讀得 0
T2 begin
U2(X) // 将 X 修改為 1
T2 commit
R1(X) // T1 讀的            

可以看到，T1 兩次讀 X，讀到的結果不一樣。如果想要避免這個情況，就需要引入更嚴格的隔離級别，即可重複讀.

T1 在第二次讀取的時候，讀到了已經送出的 T2 修改的值（這個修改事務為原版本的XMAX，為新版本的XMIN），導緻了這個問題。于是我們可以規定：事務隻能讀取它開始時,就已經結束的那些事務産生的資料版本.

這條規定,事務需要忽略2點:

(1) 在本事務後開始的事務的資料;

(2)本事務開始時還是active狀态的事務的資料.

對于第一條，隻需要比較事務 ID，即可确定。而對于第二條，則需要在事務 Ti 開始時，記錄下目前活躍的所有事務 SP(Ti)，如果記錄的某個版本，XMIN 在 SP(Ti) 中，也應當對 Ti 不可見。

于是，可重複讀的判斷邏輯如下：

(XMIN == Ti and                 // 由Ti建立且
 (XMAX == NULL or               // 尚未被删除
))
or                              // 或
(XMIN is commited and           // 由一個已送出的事務建立且
 XMIN < XID and                 // 這個事務小于Ti且
 XMIN is not in SP(Ti) and      // 這個事務在Ti開始前送出且
 (XMAX == NULL or               // 尚未被删除或
  (XMAX != Ti and               // 由其他事務删除但是
   (XMAX is not commited or     // 這個事務尚未送出或
XMAX > Ti or                    // 這個事務在Ti開始之後才開始或
XMAX is in SP(Ti)               // 這個事務在Ti開始前還未送出
))))           

于是，需要提供一個結構，來抽象一個事務，以儲存快照資料（該事務建立時還活躍着的事務）：

// vm對一個事務的抽象
public class Transaction {
  public long xid;
  public int level;
  public Map<Long, Boolean> snapshot;
public Exception err;
public boolean autoAborted;

//事務id  隔離級别  快照
public static Transaction newTransaction(long xid, int level, Map<Long, Transaction> active) {
  Transaction t = new Transaction();
  t.xid = xid;
  t.level = level;
  if(level != 0) {
    //隔離級别為可重複讀,讀已送出不需要快照資訊
    t.snapshot = new HashMap<>();
    for(Long x : active.keySet()) {
      t.snapshot.put(x, true);
    }
  }
  return t;
}

public boolean isInSnapshot(long xid) {
  if(xid == TransactionManagerImpl.SUPER_XID) {
    return false;
  }
  return snapshot.containsKey(xid);
}
}           

構造方法中的 active，儲存着目前所有 active 的事務。

于是，可重複讀的隔離級别下，一個版本是否對事務可見的判斷如下：

private static boolean repeatableRead(TransactionManager tm, Transaction t, Entry e) {
  long xid = t.xid;
  long xmin = e.getXmin();
  long xmax = e.getXmax();
  if(xmin == xid && xmax == 0) return true;

  if(tm.isCommitted(xmin) && xmin < xid && !t.isInSnapshot(xmin)) {
    if(xmax == 0) return true;
    if(xmax != xid) {
      if(!tm.isCommitted(xmax) || xmax > xid || t.isInSnapshot(xmax)) {
        return true;
      }
    }
  }
  return false;
}           

▌版本跳躍

版本跳躍問題，考慮如下的情況，假設 X 最初隻有 x0 版本，T1 和 T2 都是可重複讀的隔離級别：

T1 begin
T2 begin
R1(X) // T1讀取x0
R2(X) // T2讀取x0
U1(X) // T1将X更新到x1
T1 commit
U2(X) // T2将X更新到x2
T2 commit           

這種情況實際運作起來是沒問題的，但是邏輯上不太正确。

T1 将 X 從 x0 更新為了 x1，這是沒錯的。但是 T2 則是将 X 從 x0 更新成了 x2，跳過了 x1 版本。

讀送出是允許版本跳躍的，而可重複讀則是不允許版本跳躍的。

解決版本跳躍的思路：如果 Ti 需要修改 X，而 X 已經被 Ti 不可見的事務 Tj 修改了，那麼要求 Ti 復原。

MVCC 的實作，使得撤銷或是復原事務時：隻需要将這個事務标記為 aborted 即可。

根據前一章提到的可見性，每個事務都隻能看到其他 committed 的事務所産生的資料，一個 aborted 事務産生的資料，就不會對其他事務産生任何影響了，也就相當于，這個事務不曾存在過

if(Visibility.isVersionSkip(tm, t, entry)) {
  System.out.println("檢查到版本跳躍，自動復原");
  t.err = Error.ConcurrentUpdateException;
  internAbort(xid, true);
  t.autoAborted = true;
  throw t.err;
}           

前面我們總結了,Ti 不可見的Tj,有兩種情況:

(1) XID(Tj) > XID(Ti) 修改版本在Ti之後建立

(2) Tj in SP(Ti) Ti建立時修改版本已經建立但是還未送出

版本跳躍的檢查首先取出要修改資料X的最新送出版本,并檢查該最新版本的建立者對目前事務是否可見.具體實作如下:

public static boolean isVersionSkip(TransactionManager tm, Transaction t, Entry e) {
  long xmax = e.getXmax();
  if(t.level == 0) {
    return false;
  } else {
    return tm.isCommitted(xmax) && (xmax > t.xid || t.isInSnapshot(xmax));
  }
}           

▌作者介紹：

一作：Mark， 資深大資料架構師、Java架構師，近20年Java、大資料架構和開發經驗。資深架構導師，成功指導了多個中級Java、進階Java轉型架構師崗位。

二作：尼恩，資深系統架構師、IT領域資深作家、著名部落客。近20年高性能Web平台、高性能通信、高性能搜尋、資料挖掘等領域的3高架構研究、系統架構、系統分析、核心代碼開發工作。資深架構導師，成功指導了多個中級Java、進階Java轉型架構師崗位。

▌說在後面：

持續疊代、持續更新 是 尼恩團隊的宗旨，

持續疊代、持續更新 也是 《從0開始，手寫MySQL》的靈魂。

後面會收集更多的面試真題，同時，遇到面試難題，可以來尼恩的社群《技術自由圈（原瘋狂創客圈）》中交流和求助。

咱們的目标，打造宇宙最牛的《手寫MySQL》面試寶典。

▌技術自由的實作路徑 PDF 擷取：

▌實作你的架構自由：

• 《吃透8圖1模闆，人人可以做架構》PDF
• 《10Wqps評論中台，如何架構？B站是這麼做的！！！》PDF
• 《阿裡二面：千萬級、億級資料，如何性能優化？ 教科書級 答案來了》PDF
• 《峰值21WQps、億級DAU，小遊戲《羊了個羊》是怎麼架構的？》PDF
• 《100億級訂單怎麼排程，來一個大廠的極品方案》PDF
• 《2個大廠 100億級 超大流量 紅包 架構方案》PDF

… 更多架構文章，正在添加中

▌實作你的 響應式 自由：

• 《響應式聖經：10W字，實作Spring響應式程式設計自由》PDF
• 這是老版本 《Flux、Mono、Reactor 實戰（史上最全）》PDF

▌實作你的 spring cloud 自由：

• 《Spring cloud Alibaba 學習聖經》 PDF
• 《分庫分表 Sharding-JDBC 底層原理、核心實戰（史上最全）》PDF
• 《一文搞定：SpringBoot、SLF4j、Log4j、Logback、Netty之間混亂關系（史上最全）》PDF

▌實作你的 linux 自由：

• 《Linux指令大全：2W多字，一次實作Linux自由》PDF

▌實作你的 網絡 自由：

• 《TCP協定詳解 (史上最全)》PDF
• 《網絡三張表：ARP表, MAC表, 路由表，實作你的網絡自由！！》PDF

▌實作你的 分布式鎖 自由：

• 《Redis分布式鎖（圖解 - 秒懂 - 史上最全）》PDF
• 《Zookeeper 分布式鎖 - 圖解 - 秒懂》PDF

▌實作你的 王者元件 自由：

• 《隊列之王： Disruptor 原理、架構、源碼 一文穿透》PDF
• 《緩存之王：Caffeine 源碼、架構、原理（史上最全，10W字 超級長文）》PDF
• 《緩存之王：Caffeine 的使用（史上最全）》PDF
• 《Java Agent 探針、位元組碼增強 ByteBuddy（史上最全）》PDF

▌實作你的 面試題 自由：

4000頁《尼恩Java面試寶典》PDF 40個專題

....

注：以上尼恩 架構筆記、面試題 的PDF檔案，請到公号【技術自由圈】取

還需要啥自由，可以告訴尼恩。 尼恩幫你實作.......