場(chǎng)景一：?jiǎn)蝹€(gè)事務(wù)更新一條存在的數(shù)據(jù)

假設(shè)有表 user (id PK, name, age)，數(shù)據(jù)：[id=1, name='Alice', age=25]

你的 SQL： UPDATE user SET age = 26 WHERE id = 1;

底層動(dòng)作：

1. 事務(wù) A (主動(dòng)方) 發(fā)起更新請(qǐng)求。
2. Lock Manager 介入：
   • 查找 id=1 的索引記錄： Lock Manager 根據(jù) id=1（主鍵）找到對(duì)應(yīng)的主鍵索引樹(shù)葉子節(jié)點(diǎn)中的那條索引記錄。
   • 檢查這條索引記錄上的鎖狀態(tài)： 發(fā)現(xiàn) id=1 這條索引記錄此刻是無(wú)鎖狀態(tài)。
   • 在索引記錄上“粘貼”一個(gè)鎖標(biāo)記： Lock Manager 會(huì)在 id=1 這條具體的索引記錄上，打上一個(gè)**“X 鎖 (Exclusive Lock)”**的標(biāo)記。
     • 這個(gè)標(biāo)記就是一條內(nèi)部的內(nèi)存數(shù)據(jù)結(jié)構(gòu)，記錄著：“id=1 這條索引記錄，現(xiàn)在被事務(wù) A 以 X 模式鎖住，并且引用計(jì)數(shù)+1”。
   • 在對(duì)應(yīng)的表頭部“粘貼”一個(gè)意向鎖標(biāo)記： 同時(shí)，Lock Manager 還會(huì)順手在 user 表的內(nèi)部元數(shù)據(jù)結(jié)構(gòu)上，打上一個(gè)**“IX 鎖 (Intention Exclusive Lock)”**的標(biāo)記。
     • 這個(gè)標(biāo)記是：“user 表的某個(gè)地方，有事務(wù)正在嘗試或已經(jīng)持有 X 型行鎖。”
3. 事務(wù) A 執(zhí)行更新： 事務(wù) A 獲得鎖，可以安全地修改 id=1 這條索引記錄的 age 值。
4. 事務(wù) A 提交/回滾： 事務(wù) A 結(jié)束時(shí)，Lock Manager 會(huì)根據(jù)之前的記錄，移除 id=1 上的 X 鎖標(biāo)記，同時(shí)檢查 user 表是否還有其他 IX 鎖持有者，如果沒(méi)有，也移除 user 表上的 IX 鎖標(biāo)記。

場(chǎng)景二：事務(wù) A 更新數(shù)據(jù)，事務(wù) B 隨后讀取同一條數(shù)據(jù)

數(shù)據(jù)：[id=1, name='Alice', age=25]

你的 SQL (事務(wù) A)： UPDATE user SET name = 'Alicia' WHERE id = 1;
你的 SQL (事務(wù) B)： SELECT * FROM user WHERE id = 1;

底層動(dòng)作：

1. 事務(wù) A 獲得 id=1 的 X 鎖 (如場(chǎng)景一所述)。
   • id=1 索引記錄上：X 鎖，持有者 事務(wù) A。
   • user 表元數(shù)據(jù)上：IX 鎖，持有者 事務(wù) A。
2. 事務(wù) B 發(fā)起讀取請(qǐng)求。
3. Lock Manager 介入：
   • 查找 id=1 的索引記錄。
   • 檢查這條索引記錄上的鎖狀態(tài)： 發(fā)現(xiàn) id=1 這條索引記錄上有一個(gè) X 鎖，并且持有者是**事務(wù) A**。
   • 判斷沖突： 事務(wù) B 嘗試讀取，但 事務(wù) A 持有的是 X 鎖 (排他鎖)。X 鎖會(huì)阻止所有其他事務(wù)的讀寫(xiě)。
   • 不授予鎖，并等待： Lock Manager 不授予事務(wù) B 任何鎖，而是把事務(wù) B 放入一個(gè)等待隊(duì)列，同時(shí)啟動(dòng)事務(wù) B 的等待計(jì)時(shí)器。
     • “事務(wù) B 正在等待 id=1 這條索引記錄上的鎖。”
4. 事務(wù) A 提交： 釋放 id=1 上的 X 鎖，也釋放 user 表的 IX 鎖。
5. Lock Manager 通知： id=1 上的鎖被移除，Lock Manager 發(fā)現(xiàn)等待隊(duì)列中有事務(wù) B。
6. 事務(wù) B 被喚醒： 事務(wù) B 獲得執(zhí)行權(quán)限，讀取 id=1 這條記錄的新數(shù)據(jù)（比如 name='Alicia'）。

場(chǎng)景三：間隙鎖 (Gap Lock) 的具體行為 (防止幻讀)

數(shù)據(jù)：user (id PK)，記錄只有 [id=10], [id=30] (沒(méi)有 id=20)

你的 SQL (事務(wù) A)： SELECT * FROM user WHERE id BETWEEN 15 AND 25 FOR UPDATE; (注意這是范圍查詢且?guī)?FOR UPDATE)

底層動(dòng)作：

1. 事務(wù) A 發(fā)起請(qǐng)求。
2. Lock Manager 介入：
   • 查找索引： Lock Manager 根據(jù)條件 id BETWEEN 15 AND 25，在主鍵索引樹(shù)上進(jìn)行查找。
   • 發(fā)現(xiàn)沒(méi)有符合條件的記錄 (這是一個(gè)空區(qū)間/間隙)。
   • 在“間隙”上打鎖標(biāo)記： 盡管沒(méi)有找到具體的數(shù)據(jù)行，Lock Manager 依然會(huì)在索引結(jié)構(gòu)中，針對(duì) id=10 和 id=30 之間的**“范圍”（即 (10, 30) 這個(gè)間隙），打上一個(gè)“間隙鎖 (Gap Lock)”**的標(biāo)記。
     • 這個(gè)標(biāo)記就是：“索引中 id 值在 10 和 30 之間的空地，現(xiàn)在被事務(wù) A 鎖住，禁止插入新數(shù)據(jù)。”
     • 通常，這個(gè)間隙鎖是 X 類型的，因?yàn)樗柚蛊渌聞?wù)在這個(gè)間隙中進(jìn)行 INSERT 操作。
   • 在對(duì)應(yīng)的表頭部“粘貼”一個(gè)意向鎖標(biāo)記 (IX)。
3. 事務(wù) B 嘗試插入數(shù)據(jù)： INSERT INTO user (id) VALUES (20);
4. Lock Manager 介入：
   • 判斷插入位置： 發(fā)現(xiàn) id=20 應(yīng)該插入到 id=10 和 id=30 之間。
   • 檢查該間隙的鎖狀態(tài)： 發(fā)現(xiàn)這個(gè) (10, 30) 的間隙上有一個(gè)間隙鎖，持有者是**事務(wù) A**。
   • 不授予鎖，并等待： Lock Manager 不授予事務(wù) B 任何鎖，將事務(wù) B 放入等待隊(duì)列。
5. 事務(wù) A 提交： 釋放 (10, 30) 上的間隙鎖，以及 user 表的 IX 鎖。
6. Lock Manager 通知： 間隙鎖被移除，事務(wù) B 被喚醒，可以成功插入 id=20。

這些“鎖標(biāo)記”本質(zhì)上都是數(shù)據(jù)庫(kù)系統(tǒng)內(nèi)部維護(hù)的內(nèi)存數(shù)據(jù)結(jié)構(gòu)，它們記錄著：哪個(gè)事務(wù)在哪個(gè)資源（索引記錄或間隙或表）上持有哪種類型的鎖。當(dāng)其他事務(wù)請(qǐng)求時(shí)，Lock Manager 就去查這些標(biāo)記，進(jìn)行兼容性判斷，決定是立即授予、等待還是死鎖。
內(nèi)存中的鎖管理數(shù)據(jù)結(jié)構(gòu)，它們并不是簡(jiǎn)單的“標(biāo)記”那么純粹，而是一系列精巧組織的對(duì)象。

要理解這個(gè)，我們得從 Lock Manager (鎖管理器) 的核心工作開(kāi)始。Lock Manager 維護(hù)著一張“活的地圖”，這張地圖記錄了哪些資源被鎖了，被誰(shuí)鎖了，鎖的類型是什么，以及誰(shuí)在等待這些鎖。

最底層數(shù)據(jù)結(jié)構(gòu)模擬：Lock Manager 的“活地圖”

想象 Lock Manager 就好比一個(gè)大型交通控制中心，它有幾塊巨大的顯示屏和一些重要的記錄本。

核心數(shù)據(jù)結(jié)構(gòu) 1：鎖哈希表 (Lock Hash Table) 或 鎖鏈表 (Lock List)

這是所有正在活動(dòng)的鎖及其等待者的“索引”。

• 目的：快速查找某個(gè)資源（比如某行數(shù)據(jù)）上是否有鎖，以及有哪些事務(wù)在等待。
• 實(shí)現(xiàn)：通常是一個(gè)哈希表（std::unordered_map 類似），鍵是資源標(biāo)識(shí)符，值是一個(gè)鏈表或隊(duì)列，里面包含了所有作用在該資源上的鎖對(duì)象和等待者。因?yàn)楣１淼牟檎宜俣瓤?，能迅速定位到某個(gè)資源。

模擬其內(nèi)部結(jié)構(gòu)：

// 這是一個(gè)高度簡(jiǎn)化的偽代碼，模擬內(nèi)存中的核心結(jié)構(gòu)

// 1. 資源標(biāo)識(shí)符 (Resource Identifier) - 鎖住哪個(gè)具體的“東西”
//    這是鎖的“粒度”所在，可以是一個(gè)Page ID + Index ID + Record ID，也可以是表ID
struct LockResource {
    enum ResourceType {
        TABLE_LOCK,    // 表級(jí)
        RECORD_LOCK,   // 行級(jí)
        GAP_LOCK       // 間隙
    };
    ResourceType type;
    long long tableId; // 表的唯一標(biāo)識(shí)
    long long pageId;  // 數(shù)據(jù)頁(yè)的唯一標(biāo)識(shí) (行鎖和間隙鎖可能需要)
    long long indexId; // 索引的唯一標(biāo)識(shí) (行鎖和間隙鎖需要)
    // 對(duì)于Record Lock，可能還需要存儲(chǔ)記錄的在頁(yè)面內(nèi)的具體位置或哈希值
    // 對(duì)于Gap Lock，可能需要存儲(chǔ)間隙的起始和結(jié)束點(diǎn)（如索引鍵值，或其他內(nèi)部指針）
    std::string recordKeyHash; // 簡(jiǎn)化表示：實(shí)際是索引鍵值的hash或物理位置
  
    // 確保 LockResource 可以作為哈希表的鍵
    bool operator==(const LockResource& other) const { /* 比較所有成員 */ }
    size_t operator()(const LockResource& res) const { /* 計(jì)算哈希值 */ }
};

// 2. 具體的鎖對(duì)象 (Lock Object) - 鎖本身的信息
struct LockObject {
    enum LockMode {
        IS_LOCK,   // Intention Shared (表級(jí)意向共享)
        IX_LOCK,   // Intention Exclusive (表級(jí)意向排他)
        S_LOCK,    // Shared (讀鎖，共享鎖)
        X_LOCK     // Exclusive (寫(xiě)鎖，排他鎖)
    };
    LockMode mode;
    long long transactionId; // 持有這個(gè)鎖的事務(wù)ID
    int lockCount;           // 鎖計(jì)數(shù) (用于可重入性), 比如 SELECT ...FOR UPDATE 兩次
    bool isWaiting;          // 這個(gè)事務(wù)是否正在等待這個(gè)鎖？
  
    // 指向下一個(gè)等待這個(gè)資源的鎖對(duì)象（如果存在的話）
    // 或者指向下一個(gè)被該事務(wù)持有的鎖對(duì)象
    LockObject* nextLockInResourceList; // 針對(duì)同一資源的所有鎖和等待者鏈表
    LockObject* nextLockInTxList;       // 某個(gè)事務(wù)持有的所有鎖鏈表
};

// 3. 鎖哈希表 - 核心的數(shù)據(jù)結(jié)構(gòu)
// Key: LockResource (哪個(gè)資源被鎖)
// Value: 一個(gè)鏈表/隊(duì)列，包含所有作用在該資源上的 LockObject
std::unordered_map<LockResource, std::list<LockObject>> globalLockHashTable;

理解 globalLockHashTable 里的“東西”：

• 每個(gè)節(jié)點(diǎn)上：
  • 沒(méi)有獨(dú)立的“鎖標(biāo)記”。相反，數(shù)據(jù)庫(kù)管理著一個(gè)集中的 Lock Manager。
  • 當(dāng)你說(shuō)的“節(jié)點(diǎn)”是表時(shí)，表上會(huì)有意向鎖（IS 或 IX）的記錄，這些記錄也會(huì)被存放在 globalLockHashTable 中。LockResource 的 type 會(huì)是 TABLE_LOCK。
  • 當(dāng)你說(shuō)的“節(jié)點(diǎn)”是行時(shí)，它指的就是索引記錄 (Index Record)。這才是 InnoDB 行級(jí)鎖的真正目標(biāo)。LockResource 的 type 會(huì)是 RECORD_LOCK 或 GAP_LOCK。

核心數(shù)據(jù)結(jié)構(gòu) 2：事務(wù)持有的鎖列表 (Transaction’s Lock List)

除了按資源查找鎖，Lock Manager 還需要知道一個(gè)事務(wù)到底持有哪些鎖，以便在事務(wù)提交或回滾時(shí)能迅速釋放它們。

• 目的：快速釋放一個(gè)事務(wù)持有的所有鎖。
• 實(shí)現(xiàn)：每個(gè)活躍事務(wù)內(nèi)部，或者 Lock Manager 維護(hù)一個(gè)映射：Transaction ID -> List of LockObject。

模擬其內(nèi)部結(jié)構(gòu)：

// 4. Per-Transaction Lock List - 每個(gè)活躍事務(wù)會(huì)有一個(gè)這樣的內(nèi)部列表
//   一個(gè)事務(wù) A 內(nèi)部可能有一個(gè)指針指向它所持有的第一個(gè) LockObject
//   或者 Lock Manager 維護(hù)一個(gè) map:
std::unordered_map<long long, std::list<LockObject*>> transactionLocksMap;
// 這個(gè) list 里面的 LockObject* 都是上面 globalLockHashTable 里的指針

可視化模擬：

假設(shè)有表 user (id PK, name)，數(shù)據(jù)：[id=1], [id=5], [id=10]

事務(wù) A 操作：UPDATE user SET name='New' WHERE id=1;
事務(wù) B 操作：SELECT * FROM user WHERE id BETWEEN 3 AND 7 FOR UPDATE;

Lock Manager 內(nèi)部狀態(tài)（簡(jiǎn)化）：

{
  "globalLockHashTable": {
    // 資源1: 用戶表, TABLE_LOCK類型
    "Resource_Table_user": [
      {
        "mode": "IX_LOCK",          // 意向排他鎖
        "transactionId": "TxA",
        "lockCount": 1,
        "isWaiting": false
      },
      {
        "mode": "IX_LOCK",          // 意向排他鎖 (TxB也會(huì)加IX)
        "transactionId": "TxB",
        "lockCount": 1,
        "isWaiting": false
      }
    ],
    // 資源2: id=1 的索引記錄, RECORD_LOCK類型
    "Resource_Record_user_id_1": [
      {
        "mode": "X_LOCK",           // 排他鎖
        "transactionId": "TxA",
        "lockCount": 1,
        "isWaiting": false
      }
    ],
    // 資源3: "(1,5)" 間隙（id=5前面），GAP_LOCK類型
    "Resource_Gap_user_(1,5)": [
      {
        "mode": "X_LOCK",           // 間隙鎖是排他的
        "transactionId": "TxB",
        "lockCount": 1,
        "isWaiting": false
      }
    ],
    // 資源4: "id=5" 記錄，RECORD_LOCK類型
    "Resource_Record_user_id_5": [
      {
        "mode": "X_LOCK",           // Next-key lock會(huì)包含記錄本身
        "transactionId": "TxB",
        "lockCount": 1,
        "isWaiting": false
      }
    ],
    // 資源5: "(5,10)" 間隙，GAP_LOCK類型
    "Resource_Gap_user_(5,10)": [
      {
        "mode": "X_LOCK",           // 間隙鎖是排他的
        "transactionId": "TxB",
        "lockCount": 1,
        "isWaiting": false
      }
    ]
    // ... 其他資源
  },
  "transactionLocksMap": {
    "TxA": [
      "Resource_Table_user[IX_LOCK_TxA]",
      "Resource_Record_user_id_1[X_LOCK_TxA]"
    ],
    "TxB": [
      "Resource_Table_user[IX_LOCK_TxB]",
      "Resource_Gap_user_(1,5)[X_LOCK_TxB]",
      "Resource_Record_user_id_5[X_LOCK_TxB]",
      "Resource_Gap_user_(5,10)[X_LOCK_TxB]"
    ]
  }
}

死鎖檢測(cè)器的“行為”：

死鎖檢測(cè)器會(huì)定期（或在每次等待發(fā)生時(shí)）遍歷 globalLockHashTable 中的等待鏈表，并結(jié)合 transactionLocksMap 來(lái)構(gòu)建一個(gè)**“等待圖 (Waits-for Graph)”**。

等待圖：

• 節(jié)點(diǎn)：事務(wù) ID (TxA, TxB)。
• 邊：如果 TxA 在等待 TxB 釋放某個(gè)鎖，則從 TxA 指向 TxB。

偽算法：

1. “老鐵，數(shù)據(jù)庫(kù)里現(xiàn)在誰(shuí)在等誰(shuí)??？”
2. 遍歷 globalLockHashTable 里的每一個(gè) LockObject。
3. 如果 LockObject.isWaiting 是 true：
   • 找出這個(gè) LockObject 對(duì)應(yīng)的 LockResource。
   • 找出目前正在持有這個(gè) LockResource 上的沖突鎖的那個(gè) LockObject 的 transactionId (假設(shè)是 TxC)。
   • 那么，LockObject.transactionId 正在等待 TxC。
   • 在內(nèi)存的**“等待圖”**中，就畫(huà)一條邊：LockObject.transactionId --> TxC。
4. “圖畫(huà)好了！現(xiàn)在我們看看有沒(méi)有循環(huán)”
5. 在“等待圖”中進(jìn)行深度優(yōu)先搜索 (DFS) 或拓?fù)渑判?/strong>等算法來(lái)檢測(cè)是否存在環(huán)。
   • 如果發(fā)現(xiàn) TxA --> TxB --> TxC --> TxA 這樣的循環(huán)，警報(bào)！死鎖！
6. “有了循環(huán)！挑選一個(gè)受害者，把它回滾，讓它釋放所有鎖，打破這個(gè)循環(huán)！”