redis基础数据结构以及其应用

柔光的暖阳◎ 2022-02-05 02:47 208阅读 0赞

最近在看redis相关的书籍，这里将一些知识点做下总结，以免以后遗忘。

主要包含redis基础数据结构、redis的一些策略以及redis的一些应用等内容。

--------------------

## String ##

### 实现 ###

redis的字符串是简单动态字符串，可以对其进行动态修改。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpeXVubG9uZzQx_size_16_color_FFFFFF_t_70][]

### 策略 ###

*  空间预分配

当对字符串进行append操作时，如果**修改后的字符串长度****len**小于1MB，那么redis会分配跟len大小相等的free空间，总分配空间是len\*2。

当大于1MB时，redis会分配1MB的free空间，总分配空间是len + 1MB。需要注意字符串最大长度512MB。

*  惰性空间释放

当对字符串进行缩短操作时，只是修改free和len的值，而不是使用内存分配来回收多余的内存。

### 应用 ###

*  分布式锁

redis常见的应用，实现起来也比较简单，不过redis分布式锁并不是阻塞式的，需要判断是否获取锁成功。

[redis实现分布式锁][redis]

*  计数器 && 限速器

利用命令incr或者incrby可以实现计数功能以及限速功能，实际上这是一个针对字符串的操作，redis中没有专用的整数类型，在执行incr时会将字符串转换为64位有符号整型来执行incr操作，且这是原子操作。

我们可以使用这个特性来获取如网站的pv等数据，同时有了计数器，我们可以设置超时时间expire，并可以限定用户在expire时间内最多执行操作的次数，超出次数就会拒绝，这样就实现了简单的限速器。

[redis实现限速器][redis 1]

--------------------

## List ##

### 实现 ###

redis中list是双向链表，这样添加和删除的效率会非常高，但是随机查找的效率会低一些。

由于双向链表每个节点都需要两个指针的空间，为了节约内存，redis采用ziplist（压缩列表）和链表相结合的策略实现list。

ziplist是redis为了节约内存而设计的，是连续的内存块组成的顺序型数据结构，一个ziplist可以包含任意多个节点，每个节点可以包含一个字节数组或者一个整数值。ziplist是list和hash的底层实现之一。

当list中只包含少量元素，并且每个元素要么就是小整数值，要么就是长度比较小的字符串时，redis就会使用ziplist表来作为list的底层实现。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpeXVubG9uZzQx_size_16_color_FFFFFF_t_70 1][]

redis会将双向链表的每个元素变为ziplist，这样就节约了很多空间。

### 应用 ###

*  消息队列

可以利用redis的list结构来实现消息队列功能，使用lpush、rpush来实现入队，lpop、rpop来实现出队列。

[redis实现消息队列][redis 2]

--------------------

## Hash ##

### 实现 ###

hash的实现是**数组+链表**的二维结构，当两个或者两个以上的元素被分配到了哈希表的同一个索引上面时，redis会将冲突的元素添加到索引对应的链表上。为了速度考虑，新添加的元素总是排在链表中其他元素的前面，即添加到链表的表头位置。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpeXVubG9uZzQx_size_16_color_FFFFFF_t_70 2][]

### Rehash ###

哈希表维护着一个负载因子，随着哈希表中元素数量越来越多或者越来越少，负载因子可能偏离合理范围，这时候redis会通过rehash的方式来扩大或者收缩哈希表，为其重新分配哈希表的空间。

为了不影响性能，redis采用**渐进式rehash**的方式，通过多次rehash来将旧的哈希表迁移到新的哈希表中，而在这期间，对哈希表的查找、更新、删除等操作需要同时操作两张表。当渐进式rehash完成之后，redis会回收旧表的内存。

--------------------

## Set ##

### 实现 ###

Set本身跟hash非常相似，其内部实现相当于一个hash，但是value都是null。

### 策略 ###

Set能保证添加进来的每个元素都是唯一的，有去重的功能，注意遍历Set时是乱序的。

当Set中最后一个元素被删除，Set的空间会被redis回收。

--------------------

## SortedSet ##

### 实现 ###

zset内部使用跳跃表来实现，跳跃表是一种有序的数据结构，它是分层的，每一层也都是有序的，每个元素都指向同一层的下一个元素和下一层的较大元素，在第一层找到最接近的值后，会跳到下一层。它支持平均log(N)、最差O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点，它的操作时间复杂度可以跟平衡树相媲美，但是实现起来比平衡树简单。

### 策略 ###

zset能保证内部每个元素的唯一性，同时也能保证所有元素的有序性，即可以根据元素的权重去排序。

当zset中最后一个元素被删除时，zset的空间会被redis回收。

redis为何使用跳跃表而不是平衡树？主要原因有三个：

*  平衡树实现复杂，且删除和更新时结点变化很多，内存占用比跳跃表多，redis对内存比较敏感，因此redis选择了跳跃表。
 *  zset中的一些批量操作，如zrange、zrevrange等，跳跃表的表现比平衡树更好。
 *  zset比平衡树更容易实现、调试。

### 应用 ###

[redis实现简单延时队列][redis 3]

--------------------

# #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpeXVubG9uZzQx_size_16_color_FFFFFF_t_70]: /images/20220205/b15b0bb3fdc64774be8caf0200b6d20a.png
[redis]: https://blog.csdn.net/liyunlong41/article/details/89817552
[redis 1]: https://blog.csdn.net/liyunlong41/article/details/89854808
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpeXVubG9uZzQx_size_16_color_FFFFFF_t_70 1]: /images/20220205/1b6c7d28ed5c48378d1ab0844c70a304.png
[redis 2]: https://blog.csdn.net/liyunlong41/article/details/89964656
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpeXVubG9uZzQx_size_16_color_FFFFFF_t_70 2]: /images/20220205/adadeff1528c4d8f959f58ecb115b64a.png
[redis 3]: https://blog.csdn.net/liyunlong41/article/details/89969536