RocksDB執行緒局部快取

2019 年 10 月 3 日
筆記

概述

在開發過程中，我們經常會遇到並發問題，解決並發問題通常的方法是加鎖保護，比如常用的spinlock，mutex或者rwlock，當然也可以採用無鎖編程，對實現要求就比較高了。對於任何一個共享變數，只要有讀寫並發，就需要加鎖保護，而讀寫並發通常就會面臨一個基本問題，寫阻塞讀，或則寫優先順序比較低，就會出現寫餓死的現象。這些加鎖的方法可以歸類為悲觀鎖方法，今天介紹一種樂觀鎖機制來控制並發，每個執行緒通過執行緒局部變數快取共享變數的副本，讀不加鎖，讀的時候如果感知到共享變數發生變化，再利用共享變數的最新值填充本地快取；對於寫操作，則需要加鎖，通知所有執行緒局部變數發生變化。所以，簡單來說，就是讀不加鎖，讀寫不衝突，只有寫寫衝突。這個實現邏輯來源於Rocksdb的執行緒局部快取實現，下面詳細介紹Rocksdb的執行緒局部快取ThreadLocalPtr的原理。

執行緒局部存儲(TLS)

簡單介紹下執行緒局部變數，執行緒局部變數就是每個執行緒有自己獨立的副本，各個執行緒對其修改相互不影響，雖然變數名相同，但存儲空間並沒有關係。一般在linux 下，我們可以通過以下三個函數來實現執行緒局部存儲創建，存取功能。

int pthread_key_create(pthread_key_t *key, void (*destr_function) (void*)),  int pthread_setspecific(pthread_key_t key, const void *pointer) ,  void * pthread_getspecific(pthread_key_t key)

ThreadLocalPtr類

有時候，我們並不想要各個執行緒獨立的變數，我們仍然需要一個全局變數，執行緒局部變數只是作為全局變數的快取，用以緩解並發。在RocksDB中ThreadLocalPtr這個類就是來干這個事情的。ThreadLocalPtr類包含三個內部類，ThreadLocalPtr::StaticMeta，ThreadLocalPtr::ThreadData和ThreadLocalPtr::Entry。其中StaticMeta是一個單例，管理所有的ThreadLocalPtr對象，我們可以簡單認為一個ThreadLocalPtr對象，就是一個執行緒局部存儲(ThreadLocalStorage)。但實際上，全局我們只定義了一個執行緒局部變數，從StaticMeta構造函數可見一斑。那麼全局需要多個執行緒局部快取怎麼辦，實際上是在局部存儲空間做文章，執行緒局部變數實際存儲的是ThreadData對象的指針，而ThreadData裡面包含一個數組，每個ThreadLocalPtr對象有一個獨立的id，在其中佔有一個獨立空間。獲取某個變數局部快取時，傳入分配的id即可，每個Entry中ptr指針就是對應變數的指針。

ThreadLocalPtr::StaticMeta::StaticMeta() : next_instance_id_(0), head_(this) {    if (pthread_key_create(&pthread_key_, &OnThreadExit) != 0) {      abort();    }    ......  }    void* ThreadLocalPtr::StaticMeta::Get(uint32_t id) const {     auto* tls = GetThreadLocal();     return tls->entries[id].ptr.load(std::memory_order_acquire);  }    struct Entry {    Entry() : ptr(nullptr) {}    Entry(const Entry& e) : ptr(e.ptr.load(std::memory_order_relaxed)) {}    std::atomic<void*> ptr;  };

整體結構如下：每個執行緒有一個執行緒局部變數ThreadData，裡面包含了一組ThreadLocalPtr的指針，對應的是多個變數，同時ThreadData之間相互通過指針串聯起來，這個非常重要，因為執行寫操作時，寫執行緒需要修改所有thread的局部快取值來通知共享變數發生變化了。

 ---------------------------------------------------   |          | instance 1 | instance 2 | instnace 3 |   ---------------------------------------------------   | thread 1 |    void*   |    void*   |    void*   | <- ThreadData   ---------------------------------------------------   | thread 2 |    void*   |    void*   |    void*   | <- ThreadData   ---------------------------------------------------   | thread 3 |    void*   |    void*   |    void*   | <- ThreadData    struct ThreadData {    explicit ThreadData(ThreadLocalPtr::StaticMeta* _inst)        : entries(), inst(_inst) {}    std::vector<Entry> entries;    ThreadData* next;    ThreadData* prev;    ThreadLocalPtr::StaticMeta* inst;  };

讀寫無並發衝突

現在說到最核心的問題，我們如何實現利用TLS來實現本地局部快取，做到讀不上鎖，讀寫無並發衝突。讀、寫邏輯和並發控制主要通過ThreadLocalPtr中通過3個關鍵介面Swap，CompareAndSwap和Scrape實現。對於ThreadLocalPtr< Type* > 變數來說，在具體的執行緒局部存儲中，會保存3中不同類型的值：

1). 正常的Type* 類型指針；

2). 一個Type*類型的Dummy變數，記為InUse;

3). nullptr值，記為obsolote;

讀執行緒通過Swap介面來獲取變數內容，寫執行緒則通過Scrape介面，遍歷並重置所有ThreadData為(obsolote)nullptr，達到通知其他執行緒局部快取失效的目的。下次讀執行緒再讀取時，發現獲取的指針為nullptr，就需要重新構造局部快取。

//獲取某個id對應的局部快取內容，每個ThreadLocalPtr對象有單獨一個id，通過單例StaticMeta對象管理。  void* ThreadLocalPtr::StaticMeta::Swap(uint32_t id, void* ptr) {  //獲取本地局部快取  auto* tls = GetThreadLocal();      return tls->entries[id].ptr.exchange(ptr, std::memory_order_acquire);  }    bool ThreadLocalPtr::StaticMeta::CompareAndSwap(uint32_t id, void* ptr,                                                  void*& expected) {    //獲取本地局部快取    auto* tls = GetThreadLocal();    return tls->entries[id].ptr.compare_exchange_strong(        expected, ptr, std::memory_order_release, std::memory_order_relaxed);  }    //將所有管理的對象指針設置為nullptr，將過期的指針返回，供上層釋放，  //下次進行從局部執行緒棧獲取時，發現內容為nullptr，則重新申請對象。  void ThreadLocalPtr::StaticMeta::Scrape(uint32_t id, std::vector<void*>* ptrs, void* const replacement) {    MutexLock l(Mutex());    for (ThreadData* t = head_.next; t != &head_; t = t->next) {      if (id < t->entries.size()) {        void* ptr =            t->entries[id].ptr.exchange(replacement, std::memory_order_acquire);        if (ptr != nullptr) {    //搜集各個執行緒快取，進行解引用，必要時釋放記憶體    ptrs->push_back(ptr);        }      }    }  }    //初始化，或者被替換為nullptr後，說明快取對象已經過期，需要重新申請。  ThreadData* ThreadLocalPtr::StaticMeta::GetThreadLocal() {     申請執行緒局部的ThreadData對象，通過StaticMeta對象管理成一個雙向鏈表，每個instance對象管理一組執行緒局部對象。     if (UNLIKELY(tls_ == nullptr)) {       auto* inst = Instance();       tls_ = new ThreadData(inst);       {        // Register it in the global chain, needs to be done before thread exit        // handler registration                                                        MutexLock l(Mutex());        inst->AddThreadData(tls_);       }      return tls_;    }  }

讀操作包括兩部分，Get和Release，這裡面除了從TLS中獲取快取，還涉及到一個釋放舊對象記憶體的問題。Get時，利用InUse對象替換TLS對象，Release時再將TLS對象替換回去，讀寫沒有並發的場景比較簡單，如下圖，其中TLS Object代表本地執行緒局部快取，GlobalObject是全局共享變數，對所有執行緒可見。

下面我們再看看讀寫有並發的場景，讀執行緒讀到TLS object後，寫執行緒修改了全局對象，並且遍歷對所有的TLS object進行修改，設置nullptr。在此之後，讀執行緒進行Release時，compareAndSwap失敗，感知到使用的object已經過期，執行解引用，必要時釋放記憶體。當下次再次Get object時，發現TLS object為nullptr，就會使用當前最新的object，並在使用完成後，Release階段將object填回到TLS。

應用場景

從前面的分析來看，TLS作為cache，仍然需要一個全局變數，全局變數保持最新值，而TLS則可能存在滯後，這就要求我們的使用場景不要求讀寫要實時嚴格一致，或者能容忍多版本。全局變數和局部快取有交互，交互邏輯是，全局變數變化後，局部執行緒要能及時感知到，但不需要實時。允許讀寫並發，即允許讀的時候，使用舊值讀，待下次讀的時候，再獲取到新值。Rocksdb中的superversion管理則符合這種使用場景，swich/flush/compaction會產生新的superversion，讀寫數據時，則需要讀supversion。往往讀寫等前台操作相對於switch/flush/compaction更頻繁，所以讀superversion比寫superversion比例更高，而且允許系統中同時存留多個superversion。

每個執行緒可以拿superversion進行讀寫，若此時並發有flush/compaction產生，會導致superversion發生變化，只要後續再次讀取superversion時，能獲取到最新即可。細節上來說，擴展到應用場景，一般在讀場景下，我們需要獲取snapshot，並藉助superversion資訊來確認這次讀取要讀哪些物理介質(mem,imm,L0,L1…LN)。

1).獲取snapshot後，拿superversion之前，其它執行緒做了flush/compaction導致superversion變化

這種情況下，可以拿到最新的superversion。

2).獲取snapshot後，拿superversion之後，其它執行緒做了flush/compaction導致superversion變化

這種情況下，雖然superversion比較舊，但是依然包含了所有snapshot需要的數據。那麼為什麼需要及時獲取最新的superversion，這裡主要是為了回收廢棄的sst文件和memtable，提高記憶體和存儲空間利用率。

總結

RocksDB的執行緒局部快取是一個很不錯的實現，用戶使用局部快取可以大大降低讀寫並發衝突，尤其在讀遠大於寫的場景下，整個快取維護代價也比較低，只有寫操作時才需要鎖保護。只要系統中允許共享變數的多版本存在，並且不要求實時保證一致，那麼執行緒局部快取是提升並發性能的一個不錯的選擇。