Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > 数据库管理 > » 正文

redis中的hash实现

来源: pwlazy 分享至:

典型的数据结构

  • hashtable的一个封装


typedef struct dict {
    dictType *type; //函数集合
    void *privdata; 
    dictht ht[2];  //真正的hashtable,有两个的原因是在扩容以及rehash的时候使用
    int rehashidx; //是否处于rehash状态,-1是不属于
    int iterators; /* number of iterators currently running */
} dict;


  • 真正的hashtable


typedef struct dictht {
    dictEntry **table; // slot数组指针,slot中存放元素
    unsigned long size; //元素容量(实际就是hash中 slot的个数)
    unsigned long sizemask;(实际就是元素hash取模的基数(size-1))
    unsigned long used; //已经存储的元素个数
} dictht;


  • hashtable绑定的函数


typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;


  • 元素(链表结构,包含key和value以及下个元素的指针)


typedef struct dictEntry {

    void *key;
    void *val;
    struct dictEntry *next;
} dictEntry;


见图

典型场景

  • 创建 (dict.c:dictCreate)
    • 分配内存
    • 设置绑定函数(dict->type)
  • 添加(dict:dictAdd
    • 如果此时处于rehash状态,那么执行rehash(通常一步,下面会讲)
    • 通过dict:_dictKeyIndex返回slot索引(如果处于rehash状态,也会去遍历ht[1]),如果key存在则返回-1
      • 此时会通过(dict:_dictExpandIfNeeded)来看是否有必要扩容,下面会重点谈
    • 仍然检查是否rehash状态,如果不是则将选择ht[0]作为插入的table,否则选择ht[1]
    • 上面的步骤已经确定插入哪个table以及哪个slot,此时开始给entry分配内存
    • 将新entry插入到链表的表头
  • 查找(dict.c:dictFind)
    • 如果ht[0]为空,则返回null
    • 如果此时处于rehash状态,那么执行rehash(通常一步)
    • 计算key的hash值
    • 根据hash值确定slot(默认去找ht[0]的slot)
    • 遍历slot链表去查找相应的key
    • 在ht[0]中找不到key,如果此时处于rehash状态,那么再去查找ht[1]
  • 扩容的整体过程
    • 扩容(dict:_dictExpandIfNeeded)
      • 如果此时处于rehash状态,返回
      • 如果ht[0]为空,则扩展到初始尺寸(#define DICT_HT_INITIAL_SIZE     4)(slot数目为size-1)
      • 如果【ht[0]的元素个数超过初始尺寸】 && (【允许扩容(默认允许)】 || 【使用比例(容纳的元素个数/初始尺寸)大于阀值(5)】),开始扩容,初始尺寸扩大为原来的2倍
        • 此时仅仅是设置rehash标识(见dict属性rehashidx),并不迁移数据
        • rehashidx为-1表示不处于rehash状态,当处于rehash状态(rehashidx>-1)时rehashidx表示ht[1]待处理的slot索引(开始时是0)
        • 另外在事件循环中,每次处理时间函数时调用redis.c:serverCron->redis.c:tryResizeHashTables看是否需要扩容,扩容的标准是used>10*size
      • 在添加(dict:dictAdd)过程中会触发扩容操作
    • rehash( dict:dictRehash)
      • 有了上面这个rehash标识,就可以进行rehash(迁移数据)
      • 迁移数据是指从ht[0]-->ht[1]
      • 迁移数据也并不是一次就全部完成,默认情况每次迁移一个或者一部分slot
        • 在访问过程中是一次迁移一个slot
        • 在事件循环中,每次处理时间函数是调用redis.c:serverCron->redis.c:incrementallyRehash来继续rehash,最多迁移100个slot,如果超过1ms,就停止迁移
      • 等ht[0]全部迁移到ht[1],就切换ht[1]到ht[0]
      • 在添加(dict:dictAdd)、查找(dict.c:dictFind)过程中都会触发entry迁移

Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史