写点什么

深入 Redis 数据结构和底层原理

作者:Barry Yan
  • 2022-11-11
    北京
  • 本文字数:2413 字

    阅读完需:约 8 分钟

深入Redis数据结构和底层原理

1 概述

Redis 为什么能支持每秒钟十万级的高并发?


  • 基于内存的存取方式

  • 高效的数据结构

  • 单线程,使用多路 I/O 复用模型,非阻塞 IO

  • ......


其中一个重要的原因,就是 Redis 中高效的数据结构,因此我们就专门的来研究下 Redis 的核心数据结构,Go!

2 五大基本数据结构

分别是 String、List、Set、ZSet、Map


  • String 类型:一个 String 类型的 value 最大可以存储 512M

  • List 类型:list 的元素个数最多为 2^32-1 个,也就是 4294967295 个。

  • Set 类型:元素个数最多为 2^32-1 个,也就是 4294967295 个。

  • Hash 类型:键值对个数最多为 2^32-1 个,也就是 4294967295 个。

  • Sorted set 类型:跟 Sets 类型相似,但是有序。

2.1 String

(1)使用


127.0.0.1:6379> set str helloOK127.0.0.1:6379> get str"hello"
复制代码


(2)原理



(3)源码


typedef char *sds;
/* Sdshdr5从未被使用过,我们只是直接访问标记字节,在这里是为了记录类型5 SDS字符串的布局。*/struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; /* 3LSB的类型,5MSB的字符串长度 */ char buf[];};struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; uint8_t alloc; /* 排除头和空结束符 */ unsigned char flags; char buf[];};struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; uint16_t alloc; unsigned char flags; char buf[];};struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; uint32_t alloc; unsigned char flags; char buf[];};struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; uint64_t alloc; unsigned char flags; char buf[];};
复制代码

2.2 List

(1)使用


127.0.0.1:6379> lpush items a b c(integer) 3127.0.0.1:6379> lrange items 1 101) "b"2) "a"127.0.0.1:6379> lrange items 0 101) "c"2) "b"3) "a"127.0.0.1:6379> lpush items d(integer) 4127.0.0.1:6379> lrange items 0 101) "d"2) "c"3) "b"4) "a"127.0.0.1:6379> lpop items"d"127.0.0.1:6379> lrange items 0 101) "c"2) "b"3) "a"
复制代码


(2)原理



(3)源码


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;
复制代码

2.3 Set

(1)使用


127.0.0.1:6379> sadd set_items a b c c d d(integer) 4127.0.0.1:6379> smembers set_items1) "c"2) "b"3) "d"4) "a"127.0.0.1:6379> sadd set_items e(integer) 1127.0.0.1:6379> smembers set_items1) "d"2) "a"3) "e"4) "b"5) "c"127.0.0.1:6379>
复制代码


(2)原理



(3)源码


typedef struct intset {    uint32_t encoding;    uint32_t length;    int8_t contents[];} intset;
复制代码

2.4 ZSet

(1)使用


127.0.0.1:6379> zadd zset_items 1 a 2 c 3 b(integer) 3127.0.0.1:6379> zrange zset_items 0 101) "a"2) "c"3) "b"127.0.0.1:6379> add 2 d(error) ERR unknown command 'add'127.0.0.1:6379> zadd zset_items 2 d(integer) 1127.0.0.1:6379> zrange zset_items 0 101) "a"2) "c"3) "d"4) "b"
复制代码


(2)原理



(3)源码


/* ZSET使用特殊版本的跳表 */typedef struct zskiplistNode {    sds ele;    double score;     struct zskiplistNode *backward;    struct zskiplistLevel { // 跳表的层数        struct zskiplistNode *forward;        unsigned long span;    } level[];} zskiplistNode;
typedef struct zskiplist { struct zskiplistNode *header, *tail; //头指针和尾指针 unsigned long length; int level;} zskiplist;
typedef struct zset { dict *dict; //哈希表 zskiplist *zsl; //跳表} zset;
复制代码

2.5 Map

(1)使用


127.0.0.1:6379> hmset map name zs age 12OK127.0.0.1:6379> hgetall map1) "name"2) "zs"3) "age"4) "12"127.0.0.1:6379> hget map name"zs"127.0.0.1:6379> hmset map school zzOK127.0.0.1:6379> hgetall map1) "name"2) "zs"3) "age"4) "12"5) "school"6) "zz"127.0.0.1:6379> hdel map age(integer) 1127.0.0.1:6379> hgetall map1) "name"2) "zs"3) "school"4) "zz"127.0.0.1:6379>
复制代码


(2)原理



(3)源码


typedef struct dictEntry {    void *key;    union {        void *val;        uint64_t u64;        int64_t s64;        double d;    } v;    struct dictEntry *next;} dictEntry;
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;
/* 这是哈希表结构。 当我们实现增量重哈希时,每个字典都有两个这样的表,从旧表到新表。 */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]; long rehashidx; unsigned long iterators; /* 当前运行的迭代器数量 */} dict;
复制代码

3 重点讲下跳表(SkipList)这个数据结构

3.1 图解

3.2 查找过程


发布于: 刚刚阅读数: 3
用户头像

Barry Yan

关注

做兴趣使然的Hero 2021-01-14 加入

Just do it.

评论

发布
暂无评论
深入Redis数据结构和底层原理_redis_Barry Yan_InfoQ写作社区