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)表示哈希桶对应的锁,其中一个位表示是否有读冲突,另外一个位表示是否有写冲突。
  2. 延迟初始化(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)技术,修改每个索引节点时首先将该节点拷贝出来,接着在拷贝出来的节点上执行修改操作,最后在原子地修改其父节点的指针使其指向拷贝出来的节点。这种实现方式的好处在于修改操作不影响读取,读取操作永远不会被阻塞。

上一篇:构建freeswitch, make cd-moh-install提示文件错误


下一篇:OSS restful API 调用 put,上传文件,python发http request示例