redis数据结构(四) 集合对象

在第一节我们有说到,集合对象的底层数据结构的实现可以是哈希表或者整数集合,对应的编码分别为OBJ_ENCODING_HTOBJ_ENCODING_INTSET

因此本节主要是关于Redis中的这两种数据结构的实现分析。

字典

我们都知道,字典其实就一个key和value的集合。但是c语言中没有字典,因此Redis构建了自己的字典实现。该结构主要由哈希对象和集合对象使用。

定义

先看下Redis中字典的定义:

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

type

type表示各种用途的字典,dictType的定义如下:

typedef struct dictType {
    // 哈希值计算函数,如Murmurhash
    uint64_t (*hashFunction)(const void *key);
    // key和val的duplicate(复制)函数
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    // key值比较函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // key和val的析构函数
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

privdata

私有数据

ht

ht属性是一个包含两个项的数组,数组中的每个项都是一个dictht哈希表,一般情况下,字典只使用ht[0]哈希表,ht[1]哈希表只会在对ht[0]进行rehash时使用。

dictht的定义如下:

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

tabledictEntry类型的数组,定义如下:

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

从定义可以看出来,所谓dictEntry实际就是一个哈希表结点,它们以单向链表的形式组织起来,每一个结点包含keyval,并有指向下一个结点的next指针。

因此,table大概就是这样:

* < <node1> -> <node3> -> ... -> <nodeN> >
       |                            |
    <node2>                      <nodeK>

所以从上面这个结构可以看出,Redis的字典结构在解决哈希冲突时采用的是链地址法。

dictht中另外的属性:

  • size:dict的大小
  • sizemask:用于计算哈希值的掩码,Redis通过MurMurHash算法计算出key的中间哈希值,然后将这个值和sizemask进行一个与操作。作为这个key的哈希值。
hash = dict->type->hashFunction(k0);
index = hash & sizemask
  • used:该dict中已有结点的数量

rehash

rehash主要用到dict.ht参数。

在设计与实践一书中说,rehash是由used/size的负载因子以及是否执行BGSAVE or BGREWRITEAOF两个命令来控制的。

但在最新版代码中,rehash只有在size == 0 or used == size的条件下才进行。代码如下:

static int _dictExpandIfNeeded(dict *ht) {
    /* If the hash table is empty expand it to the initial size,
     * if the table is "full" dobule its size. */
    if (ht->size == 0)
        return dictExpand(ht, DICT_HT_INITIAL_SIZE);
    if (ht->used == ht->size)
        return dictExpand(ht, ht->size*2);
    return DICT_OK;
}

且每次rehash,size将会扩展成乘以2之后向上去2的整数次幂的值。代码如下:

/* Expand or create the hashtable */
static int dictExpand(dict *ht, unsigned long size) {
    dict n; /* the new hashtable */
    unsigned long realsize = _dictNextPower(size), i;
    ...
    assert(ht->used == 0);
    free(ht->table);

    /* Remap the new hashtable in the old */
    *ht = n;
    return DICT_OK;
}

/* Our hash table capability is a power of two */
static unsigned long _dictNextPower(unsigned long size) {
    unsigned long i = DICT_HT_INITIAL_SIZE;

    if (size >= LONG_MAX) return LONG_MAX;
    while(1) {
        if (i >= size)
            return i;
        i *= 2;
    }
}

最终的realsize一定要是2的整数次幂。

整数集合

整数集合(intset)是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多时,Redis就会使用整数集合作为集合键的底层实现。

大致浏览了下intset的源码,相比较前面的list、dict而言,少很多。

定义

话不多说,我们还是直接看intset的源码,定义如下:

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

前面分析了这么多数据结构,这还是遇见的第一个源码和设计与实现书中相符的数据结构。

encoding

集合存放的数据的编码类型,有如下类型:

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

length

集合包含的元素数量

contents

contents数组是整数集合的底层实现:整数集合的每个元素都是contents数组的一个数组项(item),每个项在数组中按值的大小从小到大有序的排列,并且数组中不包含任何重复项。

虽然contents被声明成int8的数组,实际上确可以通过类型扩展,来存放int16、int32等更高的类型数据。这个存放更高类型的操作叫做升级

升级

主要是三步:

  1. 根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间。
  2. 将现在元素替换成新类型,同时在类型扩展占用空间变大的情况下移动旧元素到新的位置上,保证有序性。
  3. 添加新元素。

排序与去重

上面定义看起来挺简单的,那么是怎么实现元素有序且不重复的呢?

源码如下:

/* Search for the position of "value". Return 1 when the value was found and
 * sets "pos" to the position of the value within the intset. Return 0 when
 * the value is not present in the intset and sets "pos" to the position
 * where "value" can be inserted. */
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;

    /* The value can never be found when the set is empty */
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        /* Check for the case where we know we cannot find the value,
         * but do know the insert position. */
        if (value > _intsetGet(is,max)) {
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {
            if (pos) *pos = 0;
            return 0;
        }
    }

    while(max >= min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }

    if (value == cur) {
        if (pos) *pos = mid;
        return 1;
    } else {
        if (pos) *pos = min;
        return 0;
    }
}

代码挺长的,其实就是通过二分法,找到元素该插入的位置,如果这个位置的值恰好等于要插入的元素,说明重复了,直接return 1,否则return 0。

集合对象

集合的源码简单,集合对象的相关概念也没什么特殊要说明,这里记录一下它的编码的转换。

同时满足以下两种情况将会使用intset编码:

  • 集合对象保存的所有元素都是整数值
  • 元素数量不超过set-max-intset-entries选项所指定的数量(这个值github上的源码默认值是512)

否则使用ht(hashtable)编码。

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号