Redis | Redis的底层数据结构实现、命令应用场景

2021/11/22 2:10:05

本文主要是介绍Redis | Redis的底层数据结构实现、命令应用场景,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

应用场景

1、缓存

2、数据共享

3、分布式锁

4、全局ID

5、计数器

6、限流

7、Top问题

8、消息队列

9、用户关注、推荐模型

10、排行榜

底层数据结构实现

string

list

hash

set

intset

zset


应用场景

1、缓存

一般使用String类型。

缓存热点数据(weibo 热搜)、对象缓存、页面缓存,降低数据库压力

2、数据共享

redis相对于引用是独立服务,可以在多个应用之间共享

例如:共享session

3、分布式锁

String类型sexnx,只有在不存在时才能添加成功。

public static boolean getLock(String key) {
   Long flag =  jedis.setnx(key,"1");
   if (flag == 1) return true;
   else   return false;     
}

4、全局ID

给定一个全局发号器 ,一次给定一段号,每个服务器使用完再来申请。

incrby 通过步长设置来获取,利用Redis操作的原子性。

Twitter:snowflow:雪花算法

美团:Leaf

5、计数器

incr方法

例如:文章阅读量、微博的点赞量

6、限流

一般通过访问的IP加其他信息作为key,访问一次加1,超过设定的阈值直接返回。

7、Top问题

微博热搜按照访问量 (zset处理)。

8、消息队列

list提供了两端操作的方法,rpush/lpush.rpop/rpush等操作。

通过操作可以实现队列,栈等结构。

9、用户关注、推荐模型

sdiff set1 set2 获取差集 推荐(好友推荐、粉丝推荐、关注话题推荐)

sinter set1 set2 获取交集(共同好友、共同话题)

sunion set1 set2 获取并集(所有好友,所有话题)

10、排行榜

新闻排行榜、微博热搜

底层数据结构实现

string

使用一种叫简单动态字符串(SDS)的数据类型来实现。

/*保存字符串对象的结构*/ 
struct sdshdr { 
    int len; // buf 中已占用空间的长度 
    int free; // buf 中剩余可用空间的长度 
    char buf[]; // 数据空间 
};

SDS 相比C 字符串的优势:

  • SDS保存了字符串的长度,而C字符串不保存长度,需要遍历整个数组(找到’\0’为止)才能取到字符串长度。

  • 修改SDS时,检查给定SDS空间是否足够,如果不够会先拓展SDS 的空间,防止缓冲区溢出。C字符串不会检查字符串空间是否足够,调用一些函数时很容易造成缓冲区溢出(比如strcat字符串连接函数)。

  • SDS预分配空间的机制,可以减少为字符串重新分配空间的次数。

list

使用双向链表来实现

typedef struct listNode { 
//前节点 
struct listNode *prev; 
//后节点 
struct listNode *next; 
//节点值 
void *value; 
} listNode; 
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;

img

Redis 的链表实现的特性可以总结:

  • 双端:链表节点带有prev和next指针,获取某个节点的前置节点和后置节点的复杂度都是O(1)。
  • 无环:表头节点的prev指针和表尾节点的 next指针都指向NULL,对链表的访问以NULL为终点。
  • 带表头指针和表尾指针:通过list结构的head指针和tail指针,程序获取链表的表头节点和表尾节点的复杂度为O(1)。
  • 带链表长度计数器:程序使用list结构的len属性来对list持有的链表节点进行计数,程序获取链表中节点数量的复杂度为O(1)。
  • 多态:链表节点使用void*指针来保存节点值,并且可以通过list结构的dup,free、match三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。

hash

hash结构里其实是一个字典,字典底层由哈希表构成,每个哈希表有多个哈希表节点,每个哈希节点保存一个键值对,redis的哈希表是一个dictht结构体。

typedef struct dictht { 
    dictEntry **table;//哈希表数组 
    unsigned long size;//哈希表大小 
    unsigned long sizemask;//哈希表大小掩码,用于计算索引值 
    unsigned long used;//该哈希表已有节点的数量 
}

img

哈希表节点的结构体如下:

typeof struct dictEntry{ 
    void *key;//键 
    union{ //不同键对应的值的类型可能不同,使用union来处理这个问题 
        void *val; 
        uint64_tu64; 
        int64_ts64; 
    } 
    struct dictEntry *next; 
}

当要将一个新的键值对添加到字典里面时,程序需要先根据键值对的键计算出哈希值和索引值,然后再根据索引值,将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。其中解决哈希冲突的方法是链地址法。为了让哈希表的装载因子维持在一个合理的范围之内,需要对哈希表的大小进行扩展或者收缩,这叫做rehash。字典中总共有两个哈希表dictht结构体,ht[0]用来存储键值对,ht[1]用于rehash时暂存数据,平时它指向的哈希表为空,需要扩展或者收缩ht[0]的哈希表时才为它分配空间。比如扩展哈希表,就是为ht[1]分配一块大小为ht[0]两倍的空间,然后把ht[0]的数据通过rehash的方式全部迁移到ht[1],最后释放ht[0],使ht[1]成为ht[0],再为ht[1]分配一个空哈希表。收缩哈希表类似。

渐进式rehash:redis并不是专门找时间一次性地进行rehash,而是渐进地进行,rehash期间不影响外部对ht[0]的访问,要求修改字典时要把对应数据同步到ht[1]中,全部数据转移完成时,rehash结束。

set

set可以用intset或者字典实现

intset

typedef struct intset { 
//类型 
uint32_t encoding; 
//长度 
uint32_t length; 
//数据 
int8_t contents[]; 
} intset;

img

整数集的结构 类型为 intset_enc_int16 ,长度5(数组contents长度) ,contents 数组结构存储数据。只有当数据全是整数值,而且数量少于512个时,才使用intset,intset是一个由整数组成的有序集合,可以进行二分查找。

img

字典

不满足intset使用条件的情况下都使用字典(拉链法),使用字典时把value设置为null。

img

zset

zset中的每个元素包含数据本身和一个对应的分数(score)。

经典例子:一个zset的key是"math",代表数学课的成绩,然后可以往这个key里插入很多数据。输入数据的时候,每次需要输入一个姓名和一个对应的成绩。那么这个姓名就是数据本身,成绩就是它的score。

zset的数据本身不允许重复,但是score允许重复。

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;

zset底层实现原理:

  • 数据少时,使用ziplist:ziplist占用连续内存,每项元素都是(数据+score)的方式连续存储,按照score从小到大排序。ziplist为了节省内存,每个元素占用的空间可以不同,对于大的数据(long long),就多用一些字节来存储,而对于小的数据(short),就少用一些字节来存储。因此查找的时候需要按顺序遍历。ziplist省内存但是查找效率低。
  • 数据多时,使用字典+跳表:

img

字典用来根据数据查score,跳表用来根据score查找数据(查找效率高)。

redis为什么使用跳表

理论上来讲,查找、插入、删除以及迭代输出有序序列这几个操作,红黑树也可以完成,时间复杂度和跳表是一样的。

redis使用跳表而不是红黑树的原因:

  • 按照区间查找数据这个操作,红黑树的效率没有跳表高。跳表可以在 O(logn)时间复杂度定位区间的起点,然后在原始链表中顺序向后查询就可以了。

  • 相比于红黑树,跳表还具有代码更容易实现、可读性好、不容易出错、更加灵活等优点。



这篇关于Redis | Redis的底层数据结构实现、命令应用场景的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程