345
RocksDB事務實現TransactionDB分析
基本概念
1. LSN (log sequence number)
RocksDB中的每一條記錄(KeyValue)都有一個LogSequenceNumber(後麵統稱lsn)，從最初的0開始，每次寫入加1。該值為邏輯量，區別於InnoDB的lsn為redo log物理寫入字節量。
這個lsn在RocksDB內部的memtable中是單調遞增的，在WriteAheadLog(WAL)中以WriteBatch為單位遞增(count(batch.records)為單位)。
WriteBatch是一次RocksDB::Put()的原子操作集合，不同的WriteBatch間是遵循ACID特性(要麼完全成功要麼完全失敗，並且相互隔離)，結構如下：
WriteBatch :=
sequence: fixed64
count: fixed32
data: record[count]
從RocksDB外部能看到的LSN是按WriteBatch遞增的(LeaderWriter(或LastWriter)最後一次性更新)，所以進行snapshot讀時，使用的就是此lsn。
注意: 在WAL中每條WriteBatch的lsn並不嚴格滿足以下公式(比如2pc情況下):
lsn(WriteBatch[n]) < lsn(WriteBatch[n+1])，可能相等
2. Snapshot
Snapshot是RocksDB的快照，實際存儲的就是一個lsn.
class SnapshotImpl {
public:
// 當前的lsn
SequenceNumber number_;
private:
SnapshotImpl* prev_;
SnapshotImpl* next_;
SnapshotList* list_;
// unix時間戳
int64_t unix_time_;
// 是否屬於Transaction(用於寫衝突)
bool is_write_conflict_boundary_;
};
查詢時如果設置了snapshot為某個lsn, 那麼對於此snapshot的讀來說，隻能看到lsn(key)<=lsn(snapshot)的key，大於該lsn的key是不可見的。
snapshot的創建和刪除都需要由一個全局的DoubleLinkList (DBImpl::SnapshotList)管理，天然的根據創建時間(同樣也是lsn大小)的關係排序，使用之後需要通過DBImpl::ReleaseSnapshot釋放。snapshot還用於在RocksDB事務中實現不同的隔離級別。
3. 隔離級別
為了實現事務下的一致性非鎖定讀(讀可以並發)，不同的數據庫(引擎)實現了不同的讀隔離級別。SQL規範標準中定義了如下四種：
| ReadUncommited | ReadCommited | RepeatableRead | Serializable | |
|---|---|---|---|---|
| Oracle | No | Yes | No | Yes |
| MySQL | Yes | Yes | Yes | Yes |
| RocksDB | No | Yes | Yes | No |
ReadUncommitted 讀取未提交內容，所有事務都可以看到其他未提交事務的執行結果。存在髒讀。
ReadCommitted讀取已提交內容
，事務隻能看見其他已經提交事務所做的改變，多次讀取同一個記錄可能包含其他事務已提交的更新。
RepeatableRead 可重讀，確保事務讀取數據時，多次操作會看到同樣的數據行(InnoDB通過NextKeyLocking對btree索引加鎖解決了幻讀)。
Serializable串行化，強製事務之間進行排序，不會互相衝突。
大部分數據庫(如MySQL InnoDB、RocksDB)，通過MVCC都可以實現上述的在非排它鎖鎖定情況下的多版本並發讀。
RocksDB Transaction
簡單的例子:
// 基本配置,事務相關操作需要TransactionDB句柄
Options options;
options.create_if_missing = true;
TransactionDBOptions txn_db_options;
TransactionDB* txn_db;
// 用支持事務的方式opendb
TransactionDB::Open(options, txn_db_options, kDBPath, &txn_db);
// 創建一個事務上下文, 類似MySQL的start transaction
Transaction* txn = txn_db->BeginTransaction(write_options);
// 直接寫入新數據
txn->Put("abc", "def");
// ForUpdate寫，類似MySQL的select ... for update
s = txn->GetForUpdate(read_options, "abc", &value);
txn->Commit(); // or txn->Rollback();
RocksDB的一個事物操作，是通過事物內部申請一個WriteBatch實現的，所有commit之前的讀都優先讀該WriteBatch(保證了同一個事務內可以看到該事務之前的寫操作)，寫都直接寫入該事務獨有的WriteBatch中，提交時在依次寫入WAL和memtable，依賴WriteBatch的原子性和隔離性實現了ACID。
有些單獨寫操作也可以通過TransactionDB直接寫
txn_db->Put(write_options, "abc", "value");
txn_db->Get(read_options, "abc", &value);
用TransactionDB::Put()，內部會直接生成一個auto transaction，將這個單獨的操作封裝成一個transaction，並自動commit。所以在TransactionDB中，所有的入口內部都會轉化成trasaction(所以顯示的transaction是可以馬上讀取到了外麵TransactionDB::Put()的數據，注意這不屬於髒讀)這個和MySQL的形式是類似的，默認每個SQL都是個auto transaction。但這種transaction是不會觸發寫衝突檢測。
GetForUpdate
類似MySQL的select ... for update，RocksDB提供了GetForUpdate接口。區別於Get接口，GetForUpdate對讀記錄加獨占寫鎖，保證後續對該記錄的寫操作是排他的。所以一般GetForUpdate會配合snapshot和SetSnapshotOnNextOperation()進行讀，保證多個事務的GetForUpdate都可以成功鎖定，而不是一個GetForUpdatech成功其他的失敗。尤其是在一些大量基於索引更新的場景上。
事務並發
不同的並發事務之間，如果存在數據衝突，會有如下情況：
- 事務都是讀事務，無論操作的記錄間是否有交集，都不會鎖定。
- 事務包含讀、寫事務：
- 所有的讀事務不會鎖定，讀到的數據取決於snapshot設置。
- 寫事務之間如果不存在記錄交集，不會鎖定。
- 寫事務之間如果存在記錄交集，此時如果未設置snapshot，則交集部分的記錄是可以串行提交的。如果設置了snapshot，則第一個寫事務(寫鎖隊列的head)會成功，其他寫事務會失敗(之前的事務修改了該記錄的情況下)。
獨占寫鎖和寫衝突
RocksDB事務寫鎖是基於Key Locking行鎖的(實現上鎖力度會粗一些)，所以在多個Transaction同時更新一條記錄，會觸發獨占寫鎖定。如果還設置了snapshot的情況下，會觸發寫衝突分析。每個寫操作(Put/Delete/Merge/GetForUpdate)開始之前，會進行寫鎖定，見TransactionLockMgr代碼。如果存在記錄有交集，寫鎖定會鎖住一片key保證隻有一個事物會獨占寫。
內部實現還是比較精煉的，全局有個LockMaps結構，裏麵按照ColumnFamily級別和num_strips(默認16)級別做了shard進一步降低衝突(此處RocksDB還針對每個LockMap做了ThreadLocal優化)。最底層是一個ColumnFamily下某一個strip的LockMapStripe結構
struct LockMapStripe {
// 當下所有keys共用的os鎖
std::shared_ptr<TransactionDBMutex> stripe_mutex;
std::shared_ptr<TransactionDBCondVar> stripe_cv;
// key -> 記錄key， value -> 每個key對應的LockInfo結構
// map中所有的key共享上述os鎖，作者這裏提到了未來會有更細粒度的鎖
// TODO(agiardullo): Explore performance of other data structures.
std::unordered_map<std::string, LockInfo> keys;
};
struct LockInfo {
// 是否是獨占鎖(也可以是共享鎖)
bool exclusive;
// 等待這個key的所有事務鏈表
autovector<TransactionID> txn_ids;
// 鎖超時時間
uint64_t expiration_time;
};
關係圖
針對每一個LockMapStripe裏所有的key，有一個LockInfo(包含是否是排它鎖，這個key掛的事務ID列表,超時時間)的map，所有落在這個map裏的key如果存在並發寫的情況，則會等待寫鎖釋放。這裏有個粒度問題，兩個不相關的key如果落在同一個map裏，也會等寫鎖。不如InnoDB的頁鎖衝突小，RocksDB作者在注釋裏提到之後會有更好的方案
加鎖代碼：
Status TransactionImpl::TryLock(ColumnFamilyHandle* column_family,
const Slice& key, bool read_only,
bool exclusive, bool untracked) {
// tracked_keys_cf記錄著當前事務中所有操作的key(涉及所有ColumnFamily)
auto iter = tracked_keys_cf->second.find(key_str);
if (iter == tracked_keys_cf->second.end()) {
// 沒找該key說明之前該事務之前一定沒有獨占鎖定這個key
previously_locked = false;
} else {
if (!iter->second.exclusive && exclusive) {
// 如果之前是共享鎖，現在申請獨占鎖，則進行鎖升級
lock_upgrade = true;
}
previously_locked = true;
current_seqno = iter->second.seq;
}
if (!previously_locked || lock_upgrade) {
// 通過全局的LockMgr獨占鎖定該key(內部使用os鎖)，如果沒有其他事務操作該key(也可
// 能不同的key命中同一個LockMapStrip)，則TryLock理解返回並持有該key獨占寫鎖。否則，
// TryLock需要等待其他事務釋放該key的獨占寫鎖，或者等待其他事務鎖超時
s = txn_db_impl_->TryLock(this, cfh_id, key_str, exclusive);
}
......
// 如果沒有設置snapshot方式(可以通過創建事務的TransactionOptions指定snapshot或者
// 調用Transaction的SetSnapshot()方法)，則直接獲取最新的lsn
if (untracked || snapshot_ == nullptr) {
......
} else {
// 如果設置了snapshot，需要通過ValidateSnapshot判斷是否有其他事務對該key進行了
// 更改(如該事務等待TryLock獨占寫鎖時，其他獲得了該鎖的事務更新了該key)。具體實現
// 就是是在memtable，immemtable以及sst中取得該key最大的lsn對應的記錄(通過
// DBImpl::GetLatestSequenceForKey)，看該lsn是否大於當前snapshot的lsn，
// 大於則寫衝突。
if (s.ok()) {
s = ValidateSnapshot(column_family, key, current_seqno, &new_seqno);
........
}
}
if (s.ok()) {
// 將當前key寫入tracked_keys_cf
TrackKey(cfh_id, key_str, new_seqno, read_only, exclusive);
}
return s;
}
死鎖檢測/超時
創建事務時 TransactionOptions.deadlock_detect 選項可以支持死鎖檢測(默認不開啟，性能影響較大，尤其是熱點記錄場景下。依賴timeout機製解決死鎖)。如果多個事務之間發生死鎖，則當前檢測到死鎖的事物失敗(可以回滾)。死鎖檢測是通過剛才提到的LockInfo中全局事物ID列表以和當前事務ID進行環檢測實現，通過廣度優先遞歸遍曆當前事務ID依賴的事務ID，判斷其是否指向自己，如果能遞歸的找到自己的ID則說明有環，發生死鎖。deadlock_detect_depth參數可以指定檢測的深度，防止過深的依賴。
Optimistic Transaction
相較於悲觀鎖，RocksDB也實現了一套樂觀鎖機製的OptimisticTransaction，接口上和Transaction是一致的。不過在寫操作(Put/Delete/Merge/GetForUpdate)時，不會觸發獨占寫鎖和寫衝突檢測，而是在事務commit時("樂觀"鎖)，寫入WAL時判斷是否存在寫衝突，而commit失敗。這種方式的好處時，更新操作或者GetForUpdate()時，不用加獨占寫鎖，省去了加鎖的代價，樂觀的認為沒有寫衝突，推遲到事務提交時一次性提交所有寫入的key進行判斷。
MVCC
RocksDB實現的ReadCommited和RepeatableRead隔離級別，類似其他數據庫引擎，都使用MVCC機製。例如MySQL的InnoDB，通過undo page實現了行記錄的多版本，這樣可以在不同的隔離級別下，看到不同時刻的行記錄內容。不過undo需要undo頁的存儲空間以及redo日誌的保護(redo寫undo)，這跟其btree的in-place update有關，而RocksDB依靠其天然的AppendOnly，所有的寫操作都是後期merge，自然地就是key的多版本(不同版本可能位於memtable,immemtable,sst)，所以RocksDB首先MVCC是很容易的，隻需要通過snapshot(lsn)稍加限製即可實現。
例如需要讀取比某個lsn小的曆史版本，隻需要在讀取時指定一個帶有這個lsn的snapshot，即可讀到曆史版本。所以，在需要一致性非鎖定讀讀取操作時，默認ReadCommited隻需要按照當前係統中最大的lsn讀取(這個也是默認DB::Get()的行為)，即可讀到已經提交的最新記錄(提交到memtable後的記錄一定是已經commit的記錄，未commit之前記錄保存在transaction的臨時buffer裏)。在RepeatableRead下讀數據是，需要指定該事務的讀上界(即創建事務時的snapshot(lsn)或通過SetSnapshot指定的當時的lsn)，已提交的數據一定大於該snapshot(lsn)，即可實現可重複讀。
txn = txn_db->BeginTransaction(write_options);
// ReadCommited (default)
txn->Get(read_options, "abc", &value);
txn = txn_db->BeginTransaction(write_options, txn_options);
txn_options.set_snapshot = true;
// RepeatableRead
read_options.snapshot = txn->GetSnapshot();
s = txn->Get(read_options, "abc", &value);
可見snapshot對於MVCC有著很重要的意義：
- snapshot可以實現不同隔離級別的非鎖定讀
- snapshot可以用於寫衝突檢測
- snapshot由全局的snapshot鏈表進行管理，在compaction時，會保留該鏈表中snapshot不被回收
2PC兩階段提交
RocksDB除了實現了基本類型的事務，還實現了2pc(https://github.com/facebook/rocksdb/wiki/Two-Phase-Commit-Implementation。某種程度上看，需求來自於MySQL的MyRocks引擎，binlog和引擎日誌(redolog、wal)有一個XA的約束，防止出現寫一個日誌成功，另一個失敗的情況。所以需要引擎日誌實現2pc來支持binlog和引擎日誌的原子提交。
詳細文檔可參見 https://github.com/facebook/rocksdb/wiki/Two-Phase-Commit-Implementation
兩階段提交在原有的Transaction基礎之上，在寫記錄和commit之間增加了一個Prepare操作：
BeginTransaction;
Put()
Delete()
.....
Prepare(xid)
Commit(xid) // or Rollback(xid)
2PC實現原理
前麵幾個步驟和普通的Transaction基本都是一直的，主要是後麵Prepare和Commit有所區別。首先，2pc的事務有一個全局的事務表，所有2pc的事務都要有一個name，在設置name的同時，將該事務注冊到全局事務表裏：
Status TransactionImpl::SetName(const TransactionName& name) {
if (txn_state_ == STARTED) {
......
// 向事務管理器注冊事務
txn_db_impl_->RegisterTransaction(this);
......
}
- prepare階段
// 設置事務狀態為開始PREPARE
txn_state_.store(AWAITING_PREPARE);
// PREPARE之後不允許事務超時, 可能會遇到2pc的通病????
expiration_time_ = 0;
WriteOptions write_options = write_options_;
write_options.disableWAL = false;
// MarkEndPrepare會將當前batch開頭和結尾寫入PREPARE標記
// 正常的WriteBatch格式一般是:
// Sequence(0);NumRecords(2);Put(a,1);Delete(b);
// MarkEndPrepare之後:
// Sequence(0);NumRecords(4);BeginPrepare();Put(a,1);Delete(b);EndPrepare(transaction_id);
// 對WriteBatch開始和結束分別加入Begin/End，標識是個PREPARE
WriteBatchInternal::MarkEndPrepare(GetWriteBatch()->GetWriteBatch(), name_);
// 將更改之後的WriteBatch寫入db，這裏隻寫WAL，不寫memtable
s = db_impl_->WriteImpl(write_options, GetWriteBatch()->GetWriteBatch(),
/callback/ nullptr, &log_number_, /log ref/ 0,
/ disable_memtable/ true);
if (s.ok()) {
.......
txn_state_.store(PREPARED);
}
整個過程將修正後的prepared writebatch隻是寫入WAL日誌，並不會更新memtable，這樣保證了其他的普通事務和2pc事務是不能訪問到該2pc事務的記錄(memtable不可見)，保證了隔離性。這裏有個點需要注意，大部分RocksDB的寫操作都是一定寫memtable和WAL(可以disable)的，所以全局的LSN就會遞增。但prepare步驟是不寫入memtable的，所以LSN不會增加，這就解釋了文章開頭說的WAL中LSN並不一定滿足lsn(WriteBatch(n)) < lsn(WriteBatch(n+1))。
- commit階段
// 設置事務狀態為準備commit
txn_state_.store(AWAITING_COMMIT);
// 獲取臨時的一個WriteBatch buffer，區別於prepare之前的操作的WriteBatch
// 所以commit的WriteBatch和prepare的WriteBatch是單獨分開的，這也就是說2pc
// 是多個WriteBatch所以需要額外保證原子性。
WriteBatch* working_batch = GetCommitTimeWriteBatch();
// 寫入commit標識和事務ID
WriteBatchInternal::MarkCommit(working_batch, name_);
// WAL終止點(暫沒想到更好的叫法)，後續寫入的數據，WAL會全部忽略
working_batch->MarkWalTerminationPoint();
// 將包含prepare的全部數據追加到WriteBatch裏，這些數據是供memtable寫入用的
WriteBatchInternal::Append(working_batch, GetWriteBatch()->GetWriteBatch());
// 數據寫入memtable(包含prepare)，並將commit事件寫入WAL
s = db_impl_->WriteImpl(write_options_, working_batch, nullptr, nullptr,
log_number_);
if (!s.ok()) {
return s;
}
// 從全局事務表裏刪除該事務
txn_db_impl_->UnregisterTransaction(this);
commit階段主要做兩件事：
- 將commit標識寫入WAL
- 將數據寫入memtable(讓其他事務可以訪問到)
整體回顧整個2pc提交的流程，prepare階段生成BeginPrepare/EndPrepare相關的WAL記錄，並寫入WAL持久化(這裏可以防止crash時，仍舊可以構建出來該事務)，但為了保證隔離性，不會寫入memtable。commit階段將Commit的WAL記錄寫入WAL，並寫入memtable，讓其他事務可見。這裏用了多個WriteBatch，打破了RocksDB默認的單WriteBatch原子性的保證，所以需要在WAL記錄中增加額外標識，並在crash時，重建內存2pc事務狀態。
2PC Recovery
RocksDB的2pc是跨WriteBatch實現的prepare和commit，所以可能存在中間態，比如prepare之後commit之前crash了。這時候係統啟動時要重建所有的正在執行的事務(僅2pc事務，普通事務通過單個WriteBatch已經保證了原子性)。MemtableInserter作為處理WriteBatch中每一條記錄，在遇到BeginPrepare/EndPrepare時，會在內存中重建事務的上下文，具體可見MemtableInserter代碼本文不贅述。
MyRocks
RocksDB的TransactionDB支持了大部分MySQL對事務的規範，整體接口形式和行為基本一致，有些細節比如online ddl、gap locking的支持、需要binglog開啟row模式等有差別。
具體可見 https://github.com/facebook/mysql-5.6/wiki
最後更新：2017-11-21 18:03:43