β

redis设计与实现1

e路相扶&&hunter_wyg 5 阅读

1.sds类型

typedef struct sdshdr {
int len; //used => strlen 时间复杂度O(1)
int free; //unused
char buf[]; //saved your string
}

2.空间分配

)空间预分配 1byte 存入的\0 结束符
    - 不超过1M的len, len = free  总length(buf) = len+free+1byte
    - 超过1M的len, free=1M 总length(buf) = len+1M+1byte
)惰性空间释放
    - 缩短sds的len的时候,多余的不会立即释放,存入free, 等待合适时间释放

3.二进制安全策略

存入和读出一样,结束长度读的是len的记录

4.redis链表是一个双向无环链表【列表键,发布与订阅,慢查询,监视器等】【adlist.h】

typedef struct list {
listNode *head;//list head
listNode *tail;//list tail
void *(*dup) (void *ptr);//节点值复制函数
void (*free) (void *ptr);//释放函
int (*match) (void *ptr, void *key);//节点值对比函数
}
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
}
typedef struct listIter {
listNode *next;
int direction;
} listIter;
5.字典 key-value,哈希键的底层实现【键值对较多或者键值对的元素较长的时候】

6.哈希表【dict.h】

/* This is our hash table structure. Every dictionary has two of this as we
 implement incremental rehashing, for the old to the new table. */

` \ typedef struct dictht { dictEntry **table;//哈希表数组 unsigned long size;//哈希表大小 unsigned long sizemask;//size-1 哈希表大小掩码和哈希值用于计算索引值 unsigned long used;//哈希表已有节点 } dictht; /* Expand or create the hashtable */ static int dictExpand(dict *ht, unsigned long size) { ……. n.size = realsize; n.sizemask = realsize-1; ….. }

//哈希表节点
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;//下个哈希表节点,行程链表
} dictEntry;

` \ 7.字典【dict.h】

` \ typedef struct dict { dictType type;//类型特定函数 void *privdata; //私有数据 dictht ht[2];//哈希表 【一般字典只使用ht[0], ht[1]是对ht[0]进行rehash时使用】 long rehashidx; / rehashing not in progress if rehashidx == -1 / unsigned long iterators; / number of iterators currently running */ } dict;

typedef struct dictType { uint64_t ( 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; ` \ 8.哈希算法【dict.h】

作者:e路相扶&&hunter_wyg
风筝,是风的追随者;我们是技术的追随者~超越
原文地址:redis设计与实现1, 感谢原作者分享。

发表评论