目录

应用场景

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;

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;//该哈希表已有节点的数量 
}

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

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;

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

字典

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

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省内存但是查找效率低。
• 数据多时，使用字典+跳表：

字典用来根据数据查score，跳表用来根据score查找数据（查找效率高）。

redis为什么使用跳表

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

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

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

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