文章目錄

• • 1. 基本事務操作
  • • 1.1 TransactionDB -- Pessimistic
    • 1.2 OptimisticTransactionDB
    • 1.3 Read Uncommitted
    • 1.4 SavePoint 回滾部分事務操作
    • 1.5 SetSnapshot
    • 1.6 GetForUpdate
    • 1.7 RepeatableRead
  • 2. 實現
  • • 2.1 WBWI(write batch with index) & WB(write batch)
    • 2.2 PessimisticTransaction 實現
    • 2.3 LockManager 以及 DeadLock detect 實現
    • • 2.3.1 LockManager 加鎖實現
      • 2.3.2 DeadLock 檢測實現
    • 2.4 OptimisticTransaction
    • • 2.4.1 kValidateSerial occ
      • 2.4.2 kValidateParallel occ
  • 3. 總結

很久之前簡單介紹了Rocksdb 事務的基本隔離性的應用以及簡單實現的描述 Rocksdb 事務： 隔離性的實現（一），其實里面有一些問題描述的非常模糊，對底層事務的實現細節講解得也不夠精確且也沒有形成遞進體系，所以今年年尾的最后一篇博客希望能夠將 Rocksdb 的事務體系描述清楚，能夠有效幫助做數據庫的同學了解事務的基本實現（基本的隔離級別的實現 rc、ru、si，分布式事務保證原子性的2PC 以及 事務周邊的rollback，死鎖檢測/死鎖避免 等都是如何做到的 ），更重要的是能夠看到大規模工業應用之后的事務所暴露出來的問題 和 這一些問題對應的優質解決方案，從而能夠讓我們將這一些思想靈活得借鑒到大規模的工業分布式環境之中。

接下來將詳細展開，以及在LSM-tree 模型下實現事務過程中存在的一些問題和對應的優化策略。

因為LSM-tree的 append模型，天然支持多版本，而且擁有WriteBatch 可以將多個版本的請求都緩存在內存中，從而更有利得解決并發事務下的讀寫沖突和寫寫沖突問題。

本文涉及到的源代碼對應的 rocksdb 版本是 6.25

1. 基本事務操作

Rocksdb 的事務實現 主要是通過TransactionDB 默認是(Pessimistic) 和 OptimisticTransactionDB 來提供事務操作。

1.1 TransactionDB – Pessimistic

使用 TransactionDB 進行事務操作，默認是 PessimisticTransactionDB，每次事務更新操作都會進行加鎖，會去檢測是否和其他事務有沖突。即 txn1 更新一個key1時會對當前key加鎖，事務txn2 在 txn1 提交前嘗試更新這個key1 則會失敗。

TransactionDB* txn_db;
TransactionDBOptions txndb_opts;
TransactionOptions txn_opts;Options opts;
std::string value;opts.create_if_missing = true;
opts.compression = kNoCompression;Status s = TransactionDB::Open(opts, txndb_opts, "./txn_db", &txn_db);
PrintStatus("TransactionDB::Open", s);// 開啟事務
Transaction* txn = txn_db->BeginTransaction(WriteOptions(), txn_opts);
assert(txn != nullptr);PrintStatus("txn->Put", txn->Put("key1", "value1"));
/// 其他事務嘗試更新這個key1，則更新失敗，會有鎖超時問題
PrintStatus("txn_db->Put", txn_db->Put(WriteOptions(), "key1", "value2"));
// 最終的事務提交
PrintStatus("txn->Commit", txn->Commit());

1.2 OptimisticTransactionDB

在樂觀事務下，不同事務之間的沖突檢測不會在每次更新操作時候進行檢測，而是在事務提交的時候進行。

/*OptimisticTransactionDB test*/
OptimisticTransactionDB* optimize_txn_db;
OptimisticTransactionOptions opti_txn_opts;
OptimisticTransactionDBOptions opti_txn_db_opts;PrintStatus("OptimisticTransactionDB::Open",OptimisticTransactionDB::Open(opts, "./opti_txn_db", &optimize_txn_db));// 開啟樂觀事務
Transaction* opti_txn = optimize_txn_db->BeginTransaction(WriteOptions(), opti_txn_opts);
assert(opti_txn != nullptr);// 當前事務更新 key1
PrintStatus("opti_txn->Put", opti_txn->Put("key1", "value1"));
// 外部事務在當前事務期間更新了 同樣的 key1 ，這里會成功
PrintStatus("optimize_txn_db->Put", optimize_txn_db->Put(WriteOptions(), "key1", "value2"));
// commit 失敗
PrintStatus("opti_txn->Commit", opti_txn->Commit());

悲觀事務 和 樂觀事務主要就是沖突檢測的位置不同，所以悲觀事務 在事務沖突概率較高的場景下能夠保證提前發現沖突而更早的觸發沖突事務的回滾。在沖突概率不高的情況下，悲觀事務每一個更新（Put,Delete,Merge,GetForUpdate）都會做沖突檢測，會引入較多的競爭開銷，從而降低性能，所以沖突概率不高的場景可以嘗試樂觀事務DB。

1.3 Read Uncommitted

這個不是 rocksdb支持的隔離級別，rocksdb 默認只支持 RC 和 Repeatable Read

不同的事務之間只能讀到事務已經提交的數據，同一個事務內部，能夠讀到未提交的數據。

// 事務寫入key1
PrintStatus("txn->Put", txn->Put("key1", "value1"));
// 讀到key1 的結果是 value1
PrintStatus("txn->Get", txn->Get(ReadOptions(), "key1", &value));
PrintStatus("txn->Delete", txn->Delete("key1"));
// Notfound
PrintStatus("txn->Get", txn->Get(ReadOptions(), "key1", &value));

因為未提交的事務都會在一個WriteBatch中，這樣當前事務內部按照操作順序能夠看到當前操作之前的所有操作。

1.4 SavePoint 回滾部分事務操作

Transaction 提供了回滾當前事務部分操作的能力，在事務中間的某一個位置設置一個 SavePoint，后面能會滾到這個位置。

// 當前事務寫入
PrintStatus("txn->Put", txn->Put("key1", "value1"));
// 設置回滾點
txn->SetSavePoint();
// 刪除
PrintStatus("txn->Delete", txn->Delete("key1"));
// 嘗試讀，讀不到，已經被刪除了
PrintStatus("txn->Get", txn->Get(ReadOptions(), "key1", &value));
// 回滾
txn->RollbackToSavePoint();
// 此時能夠讀到
PrintStatus("txn->Get", txn->Get(ReadOptions(), "key1", &value));

1.5 SetSnapshot

之前有描述，事務DB 會對每一個更新的key 進行加鎖，保證后續其他事務對 相同key的更新是失敗的。如果用戶想要在事務一開始的時候就標識 后續所有寫入的key 都要進行獨占，那可以通過 開啟事務之后設置一個 SetSnapshot 來進行后續當前事務 會獨占所有標識的key，減少一部分的沖突檢測邏輯。

SetSnapshot 之前 我們下面的邏輯是正常的：

Transaction* txn = txn_db->BeginTransaction(WriteOptions(), txn_opts);
assert(txn != nullptr);
// 即使外部的事務操作成功，因為是在當前事務更新之前更新的，并沒有沖突
PrintStatus("txn_db->Put", txn_db->Put(WriteOptions(), "key1", "value3"));
PrintStatus("txn->Put", txn->Put("key1", "value1"));PrintStatus("txn->Commit", txn->Commit());

通過 SetSnapshot 標識 之后所有的更新都被當前事務獨占，上面的外部事務更新就會失敗。

Transaction* txn = txn_db->BeginTransaction(WriteOptions(), txn_opts);
assert(txn != nullptr);
txn->SetSnapshot();
// 即使外部的事務操作是在當前事務操作之前進行更新，這里也會失敗（對setsnapshot 之后所有的操作，當前txn都會獨占）
PrintStatus("txn_db->Put", txn_db->Put(WriteOptions(), "key1", "value3"));
PrintStatus("txn->Put", txn->Put("key1", "value1"));
// 樂觀事務 會在 Commit 的時候失敗
PrintStatus("txn->Commit", txn->Commit());

悲觀事務 DB 和樂觀 事務DB的差異是 悲觀事務DB的 在設置了snapshot之后的check 會在有操作的時候報出來；樂觀事務DB 則會在 commit 的時候報出來。

1.6 GetForUpdate

有的時候我們 一個事務內部 需要對某一個key 做RMW操作 即 讀改寫，并且保證這個操作是原子的。也就是不能僅僅在寫的時候才獨占這個key，應該在讀的時候就需要獨占，才能保證后續當前事務的寫是原子的。 即讀寫沖突的檢測，Rocksdb 目前僅能通過 GetForUpdate 來進行讀寫沖突的檢測。

這個時候，就需要 GetForUpdate 接口，保證讀的時候就獨占這個key

txn = txn_db->BeginTransaction(write_options);// 當前事務 獨占key1
Status s = txn->GetForUpdate(read_options, “key1”, &value);// 外部事務 更新 會失敗
s = db->Put(write_options, “key1”, “value0”);

當然，對于 悲觀事務DB 來說 也是提交前就進行沖突檢測，樂觀事務DB則在 Commit的時候進行沖突檢測。

1.7 RepeatableRead

可重復讀 的隔離級別 是一個比較重要的操作，用戶希望能一直讀到一個版本之前的數據 而不用擔心這個版本之后的更新產生對結果的影響。

TransactionOptions txn_opts;
ReadOptions rops;Transaction* txn = txn_db->BeginTransaction(WriteOptions(), txn_opts);
assert(txn != nullptr);
PrintStatus("txn->put", txn->Put("key1", "value2"));
PrintStatus("txn->Commit", txn->Commit());// 開啟設置snapshot，標識后續該事務 對所有自己更新的key都是獨占的
txn_opts.set_snapshot = true;
txn = txn_db->BeginTransaction(WriteOptions(), txn_opts);
assert(txn != nullptr);// 在其他事務更新之前設置一個snapshot
const Snapshot* snapshot = txn->GetSnapshot();
PrintStatus("txn_db->Put", txn_db->Put(WriteOptions(), "key1", "value3"));// 普通的讀，能夠讀到value3
PrintStatus("txn->Get", txn->Get(rops, "key1", &value));// snapshot 讀，讀到的是value2
rops.snapshot = snapshot;
PrintStatus("txn->Get", txn->Get(rops, "key1", &value));

2. 實現

2.1 WBWI(write batch with index) & WB(write batch)

在看具體事務實現之前需要先整體了解一下 WB 以及 WBWI，也就是write batch 和 write batch with index 這兩個為 引擎的更新操作提供的組件。

WB 這里不用說太多，使用基礎DB 的時候經常能夠用到，Put 這樣的更新接口被調用后會組織成一個WriteBatch 數據結構，將多個更新操作合并成一個請求，從而能夠進行原子提交。
事務DB中，我們使用常見好的事務DB 直接Put （默認是PermisticDB，也會先構造WriteBatch，在commit 的時候進行原子提交）。
這里的WB 數據結構形態大概如下：

整體是一個string-buf，將一個一個k/v請求拼接進去，比較簡單，這里就不過多介紹了。

主要介紹的是 為事務功能提供的 WBWI，wirte batch with index。其在WriteBatch 基本結構的基礎上構造了一個skiplist，用來提供 事務操作過程中的 read-your-write 以及 savepoint/rollback 等這樣的基本功能。

事務如果沒有提交，所有的數據都還沒有寫入到memtable，都被緩存在WBWI之中。txn->Put 的時候 TryLock 完成之后會去更新WBWI，除了append write-batch 的 string-buffer 之外，會將這個請求在 wb中的offset/cf/key-offset/key-size 這樣的信息形成一個 writeIndexEntry 插入到單獨維護的跳表之中。這個時候，后續的 txn->Get 就能夠有效得讀到之前寫入但是還沒有提交的請求，其體結構如下：

我們的 txn->SetSavePoint 函數會將 當前 WriteBatchWithIndex 中的信息保存到一個 std::stack<SavePoint, autovector<SavePoint>> stack;，當前事務經過若干操作之后 后續的 txn->RollbackToSavePoint() 會進行彈棧，并將之前保存的狀態信息更新到現在的WBWI 之中，從而達到事務的回滾的目的。

SetSavePoint 和 RollbackToSavePoint 函數的邏輯分別在：void WriteBatch::SetSavePoint() ,WriteBatch::RollbackToSavePoint 之中。

因為WBWI 是在BeginTransaction 的時候構造的，所以每一個事務會有一個自己獨立的WBWI，其內部的數據結構不需要考慮同步問題。

2.2 PessimisticTransaction 實現

從之前的API 接口測試中，我們能夠知道 PessimisticTransaction 和 OptimisticTransaction 的主要差異是在事務沖突檢測的時機上，PessimisticTransaction 在事務有更新操作 或者 GetForUpdatae 的時候就會嘗試進行Key 的獨占，并進行相應的沖突檢測。

可看到在 Transaction::Put 的時候會根據上層配置的transactionDb類型來標識應該選擇哪一種 TryLock機制，默認是 PessimisticTransaction。TryLock 之后就會更新到 WBWI 之中。

接下來主要看一下 PessimisticTransaction 的 TryLock 是如何實現key 獨占 以及 沖突檢測的。

如果用戶配置了 TransactionOptions::skip_concurrency_control=true 的話，這里后面的key 獨占以及沖突檢測都會直接跳過。
前提是：

1. 需要應用自己保證 不會有key沖突
2. 需要應用保證recovery 的時候所有的回滾和commit 操作 都會新的事務啟動之前就完成。

這種情況下的性能肯定是最好的， 不過一致性就得自己保證了（應用有自己的事務體系，只用到了Rocksdb的部分事務能力）。

對輸入的key 的獨占邏輯如下：

PessimisticTransaction::TryLockPessimisticTransactionDB::TryLockPointLockManager::TryLock

比較老的版本 ，最后key 的加鎖過程入口是 TransactionLockMgr::TryLock，這里重構成了 PointLockManager::TryLock，主體邏輯都比較接近，主要是通過LockMgr 來實現，這里后面會詳細介紹，先關注主體實現。

到這里當前事務的 當前key 的就加鎖成功了，會獨占這個key，直到這個事務 Commit 之前其他的事務都是無法修改這個key，而其他的事務在這個事務獨占成功 但未 提交之前也會進入 上面的TryLock 邏輯之中，會嘗試等待這個 key的鎖釋放，直到超時。

回到 PessimisticTransaction::TryLock 邏輯中，前面的加鎖是為了標識這個key 后續不允許其他事務的修改。但是如果我們在事務的一開始就設置了 txn->SetSnapshot，則當前事務后續所有的更新操作都會默認獨占。可能有這樣的情況，就是在 SetSnapshot 之后 Put之前 外部事務可能對這個key 進行了修改并commit，這樣就不滿足Snapshot的語義了（一個事務設置snapshot之后 不允許其他事務的更新），這里當前事務后續的提交需要失敗才行，PessimisticTransaction::TryLock 后面的邏輯就是為了做一些沖突檢測。

一個簡略的時序圖場景如下：

因為 SetSnapshot 操作需要創建Snapshot 并將這個snapshot 插入到全局的雙向鏈表之中，所以會存在一種可能性就是txn1完成snapshot 之前 txn2 寫入并提交了一個新的更新。這個時候，txn1 繼續 Put的話需要語義上失敗。具體過程就是通過 ValidSnapshot 函數 check txn1 開始時 拿到的最新的 seq 和 現在db 中已經提交的最新的seq ，如果小的話txn1 就應該失敗。

具體檢查的過程就是 從version 系統中 取一個local_version ，直接暴力遍歷這個version 中的 mem/imm,imm-list/sst ，拿到當前沖突key 一個最新的seq即可。
邏輯如下：

PessimisticTransaction::ValidateSnapshotTransactionUtil::CheckKeyForConflictsTransactionUtil::CheckKeyDBImpl::GetLatestSequenceForKeysv->mem->Getsv->imm->Getsv->imm->GetFromHistorysv->current->Get

其中哪一步成功了，就直接返回，不需要后續的讀了，越靠近上層的key-seq 越新。

做完 ValidateSnapshot ，如果當前事務沖突檢測通過了，則繼續后續的 WBWI 的更新即可。

到此，整個 PessimisticTransaction 大體 更新邏輯就是這樣的了。
至于 Get 接口，則是直接從 WBWI 中讀取就好了，調用 WriteBatchWithIndex::GetFromBatchAndDB 就好了；
還有 GetForUpdate 和 更新的邏輯差不多，也是需要先做完 TryLock 和 ValidateSnapshot 的檢測才繼續后續的讀取。

需要注意的是 我們在txn->SetSnapshot 之后 外部事務更新 且 后續的 txn->Get 是沒有問題的，但是 如果讀取使用的是 GetForUpdate ，則會檢測 read-write confict ，GetForUpdate 會失敗；它要求的一致性語義 和 write-write confict 要求的是一樣的。

2.3 LockManager 以及 DeadLock detect 實現

2.3.1 LockManager 加鎖實現

在 PessimisticTransaction 的 TryLock 底層，我們會發現當前事務想要給 key加鎖(保證 commit 之前對key 的獨占語義 )是通過 LockManager 實現的，接下來仔細看一下這個組件的實現原理，以及其如何進行死鎖檢測的。

后文描述的 OptimisticTransaction 事務 因為 TryLock 過程不需要檢測鎖沖突，所以不需要用到LockManager.

LockManager 組件結構大概如下：

在整個DB 內部維護了一個大的 LockMaps，它是一個 column family id 到 LockMap的一個 unodered_map。這個DB內部的每一個 cf 都有一個自己的LockMap。

// Map of ColumnFamilyId to locked key info
using LockMaps = std::unordered_map<uint32_t, std::shared_ptr<LockMap>>;
LockMaps lock_maps_;

LockMap 內部 默認會有16個(可以通過 TransactionDBOptions::num_stripes進行配置) LockMapStripe，根據要加鎖的Key 的hash值，會映射到對應的LockMapStripe，這里的目的應該將輸入的key 打散到不同的stripe中，防止一個stripe 膨脹過大。
每一個 Stripe 內部有三個數據結構，stripe粒度的 mutex 和 conditionvariable，還有一個最重要的 unordered_map，用來保存 不同的key的 LockInfo，lock_info 中會用數組存儲 操作當前key的 transactionId 以及 transaction experation_time，用來進行加鎖相關的判斷。

struct LockInfo {bool exclusive;autovector<TransactionID> txn_ids;// Transaction locks are not valid after this time in usuint64_t expiration_time;...
};

針對一個輸入的key，具體的加鎖過程如下：

1. 拿到當前線程緩存的 lock_maps_cache_，它是一個ThreadLocalPtr（線程性能加速），從中 根據ColumnFamily ID 找到對應的LockMap; 如果 lock_maps_cache_ 沒有， 則從全局的 LockMaps 查找，找到則添加到 lock_maps_cache_。
   關于ThreadLocalPtr的介紹可以查看 rocksdb 讀寫鏈路上的極致優化。

2. 根據 輸入Key 的Hash，從上一步中拿到的LockMap 中取出 key 被映射到的 LockMapStripe，并對該 Stripe 加鎖（后續的處理中可能涉及對 stripe 內部 unordered_map keys 的更新）同時用 txn->GetID(), txn->GetExpirationTime() 構造一個LockInfo。

3. 帶著這個LockInfo 先判斷這個key 所在的 LockMapStripe 的 keys 中是否有這個key，有則說明之前已經加過鎖，取出這個 key 在 keys 中 的lockinfo ：如果用戶只允許一個key 加鎖 ，即key 的LockInfo 是獨占鎖，且已有的lockinfo已經超時，這里 則替換成 傳入的 LockInfo；如果用戶允許多個事務 搶占當前key 的鎖，會將這個事務ID 添加到 wait-ids 數組，等待加鎖；

   如果 LockMapStripe 的 keys 中沒有這個key，則將當前key 以及 傳入的LockInfo 添加到keys 對應的 unordered_map 之中。

   需要注意的是這里有一個 stripe 允許的最大 加鎖key 的數量判斷(構造 LockManager 的時候 通過TransactionDBOptions::max_num_locks 控制，默認是不進行限制的)，超過這個限制同樣加鎖失敗。

4. 如果第三步 還是加鎖失敗， 到第四步 會進入一個 大的超時循環中，在這個循環中會等待加鎖，等待的超時時間是逐 key 對應的LockInfo 中的超時時間，如果等待的時間過了超時時間，當前事務就會加鎖失敗返回，每一個 txn 都會進入到這個 循環中進行。

2.3.2 DeadLock 檢測實現

在上面的第四步中，因為每一個嘗試加鎖的 txn 在第一次沒有獲取到鎖的時候 都會進入到 大循環中等待獲得鎖，這里并發事務場景下可能會出現死鎖問題，所有會有死鎖檢測機制，實現邏輯是在 PointLockManager::IncrementWaiters 之中。

這里涉及到 死鎖檢測的幾個參數如下：

• TransactionOptions::deadlock_detect 是否開啟死鎖檢測，開啟則會進行
• TransactionOptions::deadlock_detect_depth 因為維護的是一個 txn 圖，這里會有死鎖檢測的深度設置，越深肯定消耗的CPU計算越多

死鎖檢測的核心是想要在一個 有向無環圖 中檢測 有沒有 wait-circle，即類似如下圖：

上圖中通過尖頭標識依賴，A–>C，txn A想要獲得鎖必須等到 txn C 釋放才能獲得。
顯然這個 wait-circle 是不會死鎖的， 只要 txn C 能夠釋放，那么其他的事務就能繼續推進，但是調整一下C的依賴可能就會死鎖了。

這樣的依賴圖 中出現了環，E–>A, A–>C, C–>E ，那就會死鎖了。

所以，我們的死鎖檢測就是拿著當前事務前面嘗試獲取鎖時 得到的一個 wait-ids 數組 和已有的wait-circle 來構建一個 有向無環圖，在這個 有向無環圖中 按照 前面用戶配置的 depth 進行 wait-circle 的檢測。

知道了核心目的，這里的代碼邏輯就很簡單了：
死鎖檢測入口是在PointLockManager::IncrementWaiters里面，通過前面對當前 txn 構造好的 wait-ids 數組構造 wait_txn_map_ 和 rev_wait_txn_map_ 兩個 HashMap。

• rev_wait_txn_map_ 用來保存 活躍事務 和 該事務在 有向無環圖中的節點個數（也可以理解為權重）
• wait_txn_map_ 用來保存整個活躍事務視圖，用于 廣度優先遍歷。保存的內容是 當前事務 和 該事務有關聯的事務信息TrackedTrxInfo

接下來就是經典的廣度優先遍歷的實現了，通過提前resize 好的兩個vector queue_values 和 queue_parents ，resize的大小是 前面說的 deadlock_detect_depth。 queue_values 保存層序，即每一層的所有節點；queue_parents 用來記錄當前層的父節點的下標，方便后面在發現死鎖環之后 進行死鎖路徑的回溯。

詳細的算法實現這里就不細講了，廣度優先算法而已。

結束條件是：

1. 在 deadlock_detect_depth 這個檢測深度下如果沒有發現 當前事務id 和 已有活躍事務依賴圖 中不會有相等的情況，則認為不會死鎖，返回未發現死鎖。
2. 如果發現有相等的，也就是在依賴圖 下找到了環的存在，則通過 queue_parents 數組來回溯當前事務在依賴圖中的依賴路徑，保存到 dlock_buffer_ 中，同時將該事務信息 從 事務依賴圖中 踢出 DecrementWaitersImpl，也就是將 當前txn 的 wait-ids 逆著走一遍初始化的過程，返回發現死鎖。

因為死鎖檢測到的準確度與 deadlock_detect_depth 配置有關系，如果上層的事務并發很大，想要有效避免死鎖問題，就需要合理得配置這個選項了，當然也需要和性能做一個trade-off，依賴圖很大，深度又很深的話，那一次 Trylock 操作的開銷可就不可忽視了。

這里實現上有一個細節，存儲 事務的依賴圖 rocksdb 并沒有選擇 std 的 unordered_map，而是自己利用 std::arrya 和 autovector(rocksdb 自己的用于小數據存儲的vector, 減少擴容 以及 添加元素時 產生的內存分配的開銷，開始時直接resize了一個大小) 實現了一個簡易的 HashMap。
原因是 std::unordered_map 在 每一次 插入 或者 刪除元素的時候 由于需要維護 iterator 的有效性(紅黑樹需要調整父子節點的指針鏈接關系)，需要進行內存的分配和釋放，這在 TryLock 中 尤其是高并發下，會造成不必要的開銷。
所以，這里還是選擇用 array + autovector，array 作為hash-bucket，autovector 存儲每一個bucket內部的元素即可。

2.4 OptimisticTransaction

接下來看一下 OptimisticTransaction 的實現，相對來說就簡單很多了， 相比于 PessimisticTransaction 的主要差異就是 沖突檢測的時機 是在 Commit 階段才進行。
它在 TryLock 的時候 會將當前 要更新的 key的信息添加到 LockTracker 中：

要追蹤的信息主要包括當前key的 cf, seq, 是否只讀，是否是獨占的；其中 seq 是取用戶設置的snapshot（如果設置了的話）的 seq，如果沒有設置，則直接從basedb 中取最新的。

這里 LockTracker 結構大概是這樣的：

為每一個cf 維護一個 TrackedKeyInfos 的unordered_map，其中保存這個cf 追蹤的key 以及 其 TrackedKeyInfo信息。

接下來 看看 Commit 的時候 樂觀事務DB 怎么做沖突檢測，按照經驗，看上面記錄的信息，肯定是 seq 是沖突檢測的核心了。
Commit 的代碼中提供了兩種 Occ (optimistic concurrent control)策略: kValidateParallel 和 kValidateSerial ，在2020.6 月份及以前的版本 應該是只有一種 occ 策略，也就是 kValidateSerial 的實現。

先來分別看一下兩種實現的具體差異，再想想為什么分別會有這兩種策略，希望能為我們在分布式事務的設計中提供一些借鑒思路。

2.4.1 kValidateSerial occ

實現入口是在 OptimisticTransaction::CommitWithSerialValidate 中

直接拿到 basedb，調用 WriteWithCallback 函數，其中 callback 的實現是 OptimisticTransactionCallback::Callback，也就是 OptimisticTransaction::CheckTransactionForConflicts。
在WriteWithCallback 會在每次寫入之前對所有要寫入的請求執行 callback，WriteImpl 中 writer->CheckCallback(this)，檢測是否滿足寫入的要求。

在 CheckTransactionForConflicts 中做的事情，就是拿著 前面 TryLock 過程中獲取到的 LockTracker 信息 進行seq num的比較，和 PessimisticTransaction 事務中的 ValidSnapshot 做的事情一樣，檢測 tracker 中要提交的key 的 seq 是否比當前db 中最新的 已經commit 的 seq小，用來確定這個事務執行 中間是否有外部事務 對當前key 的更新(完成 commit的操作)。

	TransactionUtil::CheckKeyForConflictsTransactionUtil::CheckKeyDBImpl::GetLatestSequenceForKeysv->mem->Getsv->imm->Getsv->imm->GetFromHistorysv->current->Get

如果做完沖突檢測，這一批事務的 tracker key都沒有問題，則可以提交，繼續后續的寫入(寫WAL)，否則會返回失敗。

occ 策略中的 另一個策略在沖突檢測這里都是差不多的。

2.4.2 kValidateParallel occ

這個策略的入口是 OptimisticTransaction::CommitWithParallelValidate。
關于沖突檢測的內部實現就不過多介紹了，都是一樣的，主要是這個策略如何調度 沖突檢測的。

在寫入之前 會先對所有的 tracked_locks_ 中的多事務的 key 按照順序進行加鎖，然后統一進行 多事務的沖突檢測，沖突檢測通過之后直接調度寫入。

這里有一個 issue 來簡單描述了 推出 kValidateParallel occ 策略的原因: kValidateSerial 太慢了。
雖然 optimisticTransaction 是建議 事務沖突概率較小的場景下才用，但是正常的多cf 寫入的時候有人發現它比 baseDb和 permisticDB 慢了 5倍，看起來像是很多CPU 沒有被利用起來的樣子。
原因是因為 舊版本的實現 也就是 kValidateSerial 策略中：

1. OptimisticTransactionCallback::AllowWriteBatching 返回是false，也就是在 不會調度 rocksdb 的寫模型中 的 leader writer 批量寫其他 writer的請求，這樣的話大量的并發就沒有什么用了， 都是順序寫wal。
2. OptimisticTransaction 本身就是在 commit 階段進行沖突檢測，所以 寫入之前會有一些額外的CPU消耗（拿沖突key 的最新seq的過程 需要從上到下掃LSM-tree，直到拿到當前key在basedb 最新提交的seq）

這一些過程導致 在 舊版本的實現中 性能最差（即使是正常的請求處理），主要影響還是在 利用 Callback 去做沖突檢測的過程為了保證沖突檢測的有效性而關閉 group commit 功能。

所以，新的版本 主要就是解決這個問題，將callback 去掉，挪到了 write之前，畢竟沖突檢測不論什么時候都得做，而挪到寫鏈路之前做 并不會影響group-commit 的邏輯，沖突檢測通過之后還是正常的 寫邏輯。

相關的issue和pr 可以參考：
https://github.com/facebook/rocksdb/issues/4402
https://github.com/facebook/rocksdb/pull/6240

occ 策略希望能用一種樂觀的方式處理并發事務場景，雖然在高并發的低沖突事務處理下優勢明顯，但是在正常的事務處理邏輯中不應該有更多的性能損耗， 可能是因為使用場景較少的原因，這個性能問題才在18年提出 20年才修復。

3. 總結

限于篇幅原因，本來還想繼續展開 為myrocks 提供的 2PC 和 為 PessimisticTransactionDB 所做的長事務內存優化的 WritePreparedTxnDB 以及 WriteUnPreparedTxnDB ，先暫時推后吧。

總的來說，通過Rocksdb 的完整 事務實現過程 我們能夠大體了解到 基本隔離級別的實現 以及 事務并發場景時 read-write confict 和 write-write conflict 的有效解決方案。因為 Rocksdb 是引擎底座，這一些實現方案 以及 底層的代碼細節都是經過工業界長期驗證的，值得學習參考。

---

不出意外應該是今年的最后一篇博客了，后面幾天會寫一寫年末總結，為這 “多災多難” 的一年畫一個句號了。

總結

以上是生活随笔為你收集整理的Rocksdb的事务（二）：完整事务体系的 详细实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。