309      阿裏雲  技術社區[雲棲]

OceanBase分布式存儲引擎公共模塊——基礎數據結構

OceanBase分布式存儲引擎公共模塊——基礎數據結構

1.哈希表

為了提高隨機讀取性能，UpdateServer支持創建哈希索引，這個哈希索引結構就是LightlyHashMap,代碼如下：

template <typename Key, typename Value>
class LightlyHashMap
{
public:
    //插入一個<key,value>對到哈希表
    inline int insert(const Key& key, const Value& value);
    //根據key查找value
    inline int get(const Key& key, const Value& value);
    //根據key刪除一個<key,value>對，如果value不為空，那麼，保存刪除的值到value中
    inline int erase(const Key& key, Value& value = NULL);
private;
    struct  Node
    {
        Key key;
        Value value;
        union
        {
            Node* next;
            int64_t flag;
        };
    };
    Node* buckets_; //哈希桶指針
    BitLock bit_lock_;//位鎖，用於保護哈希桶
};

LightlyHashMap采用鏈式衝突處理方法，即將所有哈希值相同的對鏈到同一哈希桶中，它包含如下三個方法：

• insert：往哈希表中插入一個對。這個函數首先根據key 的哈希值得到桶號，接著，往哈希桶中插入一個包含key和value值的Node節點。
• get：根據key查找value。這個函數首先根據key的哈希值得到桶號，接著，遍曆對應的鏈表，找到與傳入key相同的Node節點，返回其中的value值。
• erase：根據key刪除一個對。這個函數首先根據key的哈希值得到桶號，接著，遍曆對應的鏈表，找到並刪除與傳入key相同的Node節點。

LightlyHashMap設計用來存儲幾千萬甚至幾億個元素，它與普通哈希表的不同點在於以下兩點：
1. 位鎖（BitLock）：LightlyHashMap通過BitLock實現哈希值的鎖結構，每個哈希桶的鎖結構隻需要占用一個位（Bit）。如果哈希桶對應的位鎖值為0.表示沒有鎖衝突；否則，表現出鎖衝突。需要注意的是，LightlyHashMap沒有區分讀鎖和寫鎖，多個get請求也是衝突。可以對LightlyHashMap的BitLock做一些改進，例如用兩個位（Bit）表示哈希桶對應的鎖，其中一個位表示是否有讀衝突，另外一個位表示是否有寫衝突。
1. 延遲初始化（Lazy Initialization）：LightlyHashMap的哈希桶個數往往特別多（默認為1000萬個），即使僅僅對所有哈希桶執行一次memset操作，消耗的時間也是相當可觀的。因此，LightlyHashMap采用延遲初始化的策略，即將哈希桶劃分為多個單元，默認情況下每個單元包含65536個哈希桶。每次執行insert、get或者erase操作時都會判斷哈希桶所屬的單元是否已經初始化，如果未初始化，則對該單元內的所有哈希桶執行初始化操作。

2.B樹

UpdateServer的MemTable結構底層采用B樹結構索引其中的數據，代碼如下：

template<class K, class V, class Alloc>
class BTreeBase
{
public:
    //把,<key, value>對加到B樹中，overwrite參數表示是否覆蓋原有值
    int put(const K& key, const V& value, const bool overwrite = false);
    //獲取key對應的value
    int get(const K& key, V& value);
    //獲取掃描操作描述符
    int get_scan_handle(TScanHandle& handle);
    //設置掃描的數據範圍
    int set_key_range(TScanHandle& handle, const K& start_key, int32_t start_exclude, const K& end_key, int32_t end_exclude);
    //讀取下一行數據
    int get_next(TScanHandle& handle, K& key, V& value);
};

支持的功能如下：

• Put:插入一個對。
• Get：根據key獲取對應的value。
• Scan:掃描一段範圍內的數據行。首先，調用get_scan_handle獲取掃描操作描述符，其次，調用set_key_range設置掃描的數據範圍，最後，不斷地diao'yon調用get_next讀取下一行數據直到全部讀完。

為了提高讀寫並發能力，B樹實現時采用寫時複製（Copy-on-write）技術，修改每個索引節點時首先將該節點拷貝出來，接著在拷貝出來的節點上執行修改操作，最後在原子地修改其父節點的指針使其指向拷貝出來的節點。這種實現方式的好處在於修改操作不影響讀取，讀取操作永遠不會被阻塞。

最後更新：2017-07-13 17:02:40

  上一篇：  個人注冊域名需要注意哪些方麵？

  下一篇：  網站SEO優化：PC站、手機網站優化細節