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

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

String

实现

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

策略

• 空间预分配

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

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

• 惰性空间释放

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

应用

• 分布式锁

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

redis实现分布式锁

• 计数器 && 限速器

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

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

redis实现限速器

List

实现

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

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

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

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

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

应用

• 消息队列

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

redis实现消息队列

Hash

实现

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

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实现简单延时队列