redis object types

redis数据结构类型及实现

Object Types

/* Object types */
#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4

strings&Hashes&Set

HSET myhash field1 “Hello”

Hash对象是用zipmap存储的，查找、删除均为O(n)，但一般来说对象的field对象不会大多，所以说操作评价还是近似O(1)。如果field/value的大小超过一定限制后，Redis会在内部自动将zipmap替换成正常的Hash实现

SADD myset1 “Hello”

SINTER myset1 myset2

Set没有重复的值，对其有添加删除操作，可对都个结合求交、并等操作，key理解为集合的名字。新浪微博中的：“我和她都关注了”只需要一个SINTER命令就可以实现。

struct sdshdr{
    long len;
    long free;
    char buf[];
}

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

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

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

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

Lists

Lists是一个简单的strings类型的双向链表，按照插入顺序排序。可以通过命令从头部或者尾部添加删除元素，即可很方便的实现栈与队列操作。List还可以阻塞，很容易就实现了一个工作队列，而不用轮询。

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

ZSets

ZSets为Set的升级版本，即排序的Sets，在Set的基础之上增加了顺序（Score）属性，每次插入均需要指定，且会自动重新调整值的顺序。Score为double类型，ZSets实现为SkipList与HashTable的混合体。

元素到Score的映射是添加在HashTable中的，所以给定一个元素获取Score开销为O(1)，Score到元素的映射则为SkipList。

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;