Monthly Archives: October 2010

Redis Data Struct

Posted on by
Reply

Redis的几个核心数据结构定义在redis.h和dict.h中。Redis服务器总的数据结构里的根节点是redisServer，下面包含一个redisDb结构数组。数组的大小定义在redis.conf中的databases项，客户端可以通过select命令选择相应的DB。

一个redisDb定义了redis数据库的基本数据结构，redisDb结构定义如下

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP) */
    dict *io_keys;              /* Keys with clients waiting for VM I/O */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;
} redisDb;

其中

  • dict 用于存储键值的哈希表结构
  • expires 用于存储键、过期时间的哈希表结构
  • blocking_keys 用于存储键、阻塞数据的哈希表结构。目前仅仅在阻塞式的blpop brpop中使用。
  • io_keys 存储等待将数据从swap读出的key （vmThreadedIOCompletedJob, dontWaitForSwappedKey, waitForSwappedKey）
  • watched_keys 用于支持WATCH命令，实现乐观锁功能
  • id 数据库编号

dict结构定义在dict.h中，主要的定义有：

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

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

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

每个dict中包含两个dictht结构，用来在rehash的时候进行数据交换。rehashidx用于记录rehash的进程，值是当前rehash的table索引。dictht中table二维数组，以hash值为索引。size是哈希表的大小，初始值是4，随着rehash的进行，变成大于size的最小2n。sizemask是size-1，用来与哈希值做&运算。

redis在引如virtual memory之前，就是以这样的数据结构运行在内存中的。