Redis可以存储可以存储键与5种不同数据结构类型之间的映射。五种数据类型为:STRING(字符串)、LIST(列表)、SET(集合)、HASH(散列)、ZSET(有序集合)。
一、字符串类型String
1、类型定义
String 数据结构是简单的 key-value 类型,使用string时,redis(大多数情况下)并不会理解或者解析其含义,无论使用json、xml还是纯文本在redis看来都是一样的,只是一个字符串,只能进行strlen、append等对字符串通用的操作,无法针对其内容进一步操作。
其基本操作命令有set、get、strlen、getrange、append:在大多数情况之外,就是string中存储的为纯数字的情况,redis可以将字符串当做数字进行进一步操作,这些操作包括decr、decrby、incr、incrby和incrbyfloat。
1)赋值:SET key value。如set hello world 2)取值:GET key。如get hello。返回是world 3)自增:INCR key。就是Mysql的AUTO_INCREMENT。每次执行INCR key时,该key的值都会+1.若key不存在,则先建立一个0,然后+1,返回1。
如果值不是整数则报错。该操作是原子操作。 4)自减:DECR key。将指定key的值减少1.如DECR num,就是num-1 5)自增N:INCRBY key increment用来给指定key的值加increment。如INCRBY num 5就是num+5 6)自减N:DECRBY key increment用来给指定key的值减increment。如DECRBY num 5就是num-5 7)增加浮点数:INCRBYFLOAT key increment。 8)向尾部追加:APPEND key value。如set test:key 123 append test:key 456 get test:key就是123456 9)获取长度:STRLEN key。 10)同时给多个key 赋值:MSET title 这是标题 description 这是描述 content 这是内容。 11)同时获取多个key的值:MGET title description content 12)位操作之获取:GETBIT key offset。如字符a在redis中的存储为01100001(ASCII为98),那么GETBIT key 2就是1,GET key 0就是0。 13)位操作之设置:SETBIT key offset value。如字符a在redis中的存储为01100001(ASCII为98),那么SETBIT key 6 0,SETBIT key 5 1
那么get key得到的是b。因为取出的二进制为01100010。 14)位操作之统计:BITCOUNT key [start] [end]:BITCOUNT key用来获取key的值中二进制是1的个数。而BITCOUNT key start end则是用来
统计key的值中在第start和end之间的子字符串的二进制是1的个数(好绕啊)。 15)位操作之位运算:BITOP operation resultKey key1 key2。operation是位运算的操作,有AND,OR,XOR,NOT。resultKey是把运算结构
存储在这个key中,key1和key2是参与运算的key,参与运算的key可以指定多个。
2、应用场景
- 缓存功能:字符串最经典的使用场景,redis最为缓存层,Mysql作为储存层,绝大部分请求数据都是redis中获取,由于redis具有支撑高并发特性,所以缓存通常能起到加速读写和降低 后端压力的作用。
- 计数器:许多运用都会使用redis作为计数的基础工具,他可以实现快速计数、查询缓存的功能,同时数据可以一步落地到其他的数据源。如:视频播放数、粉丝数、微博数就是使用redis作为计数的基础组件。
- 共享session:出于负载均衡的考虑,分布式服务会将用户信息的访问均衡到不同服务器上,用户刷新一次访问可能会需要重新登录,为避免这个问题可以用redis将用户session集中管理,在这种模式下只要保证redis的高可用和扩展性的,每次获取用户更新或查询登录信息都直接从redis中集中获取。
- 限速:处于安全考虑,每次进行登录时让用户输入手机验证码,为了短信接口不被频繁访问,会限制用户每分钟获取验证码的频率。
3、实现原理
- 通过 int、SDS(simple dynamic string)作为结构存储
- int用来存放整型数据,sds存放字节/字符串和浮点型数据
- redis3.2分支引入了五种sdshdr类型,
- 目的是为了满足不同长度字符串可以使用不同大小的Header,从而节省内存
具体请可以参考:Redis学习之Redis数据结构详解(RedisObject、SDS)
二、列表类型List
1、类型定义
Redis对链表(Linked-list)结构的支持使得其在键值存储的世界独树一帜,一个列表结构可以有序地存储多个字符串。
使用list时,value就是一个string数组,操作这组string时,可以像对待栈一样使用pop和push操作,但是这个栈两端都能进行操作;也可以像对待数组一样使用一个index参数来操作。list的操作命令略杂,主要分为两类:L开头的和R开头的,L代表LEFT或者LIST,进行一些从列表左端进行的操作,或者一些与端无关的操作;R代表RIGHT,进行一些从列表右端进行的操作。
1)向头部插入:LPUSH key value1 value2...。返回增加后的列表长度。 2)向尾部插入:RPUSH key value1 value2...。返回增加后的列表长度。 3)从头部弹出:LPOP key。返回被弹出的元素值。该操作先删除key列表的第一个元素,再将它返回。 4)从尾部弹出:RPOP key。返回被弹出的元素值。 5)列表元素个数:LLEN key。key不存在返回0。 6)获取列表的子列表:LRANGE start end。返回第start个到第end个元素的列表。包含start和end。支持负数索引。-1表示最后一个元素,-2表示倒数
第二个元素。 7)删除列表中指定值:LREM key count value。删除key这个列表中,所有值为value的元素,只删除count。如果有count+1个,那么就保留最后一个。
count不存在或者为0,则删除所有的。如果count大于0,则删除从头到尾的count个,如果count小于0,则删除从尾到头的count个。 8)获取指定索引值:LINDEX key index。如LINDEX key 0就是列表的第一个元素。index可以是负数。 9)设置索引和值:LSET key index value。这个操作只是修改指定key且指定index的值。如果index不存在,则报错。 10)保留片段,删除其它:LTRIM key start end。保留start到end之间的所有元素,含start和end。其他全部删除。 11)向列表插入元素:LINSERT key BEFORE/AFTER value1 value2。从列表头开始遍历,发现值为value1时停止,将value2插入,根据BEFORE
或者AFTER插入到value1的前面还是后面。 12)把一个列表的一个元素转到另一个列表:RPOPLPUSH list1 list2。将列表list1的右边元素删除,并把该与元素插入到列表list2的左边。原子操作。
2、应用场景
消息队列: redis的lpush+brpop命令组合即可实现阻塞队列,生产者客户端是用lupsh从列表左侧插入元素,多个消费者客户端使用brpop命令阻塞时的“抢”列表尾部的元素,多个客户端保证了消费的负载均衡和高可用性。
- 文章列表:每个用户都有属于自己的文章列表,现在需要分页展示文章列表,此时可以考虑使用列表,列表不但有序同时支持按照索引范围获取元素。
使用列表技巧:
lpush+lpop=Stack(栈)
lpush+rpop=Queue(队列)
lpush+ltrim=Capped Collection(有限集合)
lpush+brpop=Message Queue(消息队列)
3、实现原理
- 列表类型内部使用双向链表实现。
其内部数据结构为:
value对象内部以linkedlist或者ziplist来实现:
- 当list的元素个数和单个元素的长度比较小的时候,Redis会采用ziplist(压缩列表)来实现来减少内存占用。
- 否则就会采用linkedlist(双向链表)结构。
redis3.2之后,采用的一种叫quicklist的数据结构,实现ziplist和双向链表的二者结合,quicklist仍然是一个双向链表,只是列表的每个节点都是一个ziplist。
三、集合Set
1、类型定义
Redis的集合Set和列表List都可以存储多个字符串,但是列表可以存储多个相同的字符串,而集合则通过使用散列表来保证自己存储的每个字符串都是不相同的。Redis使用无序的方式存储元素。
集合类型是为了方便对多个集合进行操作和运算。集合中每个元素不同且没有顺序的概念,每个元素都是且只能是一个字符串。常用操作是对集合插入、删除、判断等操作。时间复杂度尾O(1)。可以进行交集、并集、差集运算。集合类型在redis中的存储是一个值为空的散列表(这些散列表只有键,但是没有与键相关的值)。
1)增加:SADD key value。 2)删除:SREM key value。 3)获取指定集合的所有元素:SMEMBERS key。 4)判断某个元素是否存在:SISMEMBER key value。 5)差集运算:SDIFF key1 key2...。对多个集合进行差集运算。 6)交集运算:SINNER key1 key2...。对多个集合进行交集运算。 7)并集运算:SUNION key1 key2...。对多个集合进行并集运算。 8)获取集合中元素个数:SCARD key。返回集合中元素的总个数。 9)对差集、交集、并集运算的结果存放在一个指定的key中:SDIFFSTORE storekey key1 key2。对key1和key2求差集,结果存放在key为storekey的
集合中。SINNERSTORE和SUNIONSTORE类似。 10)获取集合中的随即元素:SRANDMEMBER key [count]。参数count可选,如果count不存在,则随即一个。count大于0,则是不重复的count个元素。
count小于0,则是一共|count|个元素,可以重复。 11)随即弹出一个元素:SPOP key。随即从集合中弹出一个元素并删除,将该元素的值返回。
2、应用场景
- 标签(tag):集合类型比较典型的使用场景,如一个用户对娱乐、体育比较感兴趣,另一个可能对新闻感兴趣,这些兴趣就是标签,有了这些数据就可以得到同一标签的人,以及用户的共同爱好的标签,这些数据对于用户体验以及曾强用户粘度比较重要。
使用技巧:
sadd=tagging(标签)
spop/srandmember=random item(生成随机数,比如抽奖)
sadd+sinter=social Graph(社交需求)
3、实现原理
- 底层数据结构以intset或者值为空的hashtable来存储。
四、散列Hash
1、类型定义
Redis的散列可以存储多个键值对之间的映射,和字符串一样,存储的Redis是以字典(关联数组)的形式存储的,一个key对应一个value。在字符串类型中,value只能是一个字符串。那么在散列类型,也叫哈希类型中,value对应的也是一个字典(关联数组)。那么就可以理解,Redis的哈希类型/散列类型中,key对应的value是一个二维数组。但是字段的值只可以是字符串。也就是说只能是二维数组,不能有更多的维度。
散列的值既可以是字符串也可以是数字值,并且用户可以对散列存储的数字值进行自增操作以及自减操作。
1)赋值:HSET key field value。如hset user name lane。hset user age 23 2)取值:HGET key field。如hget user name,得到的是lane。 3)同一个key多个字段赋值:HMSET key field1 value1 field2 value2... 4)同一个KEY多个字段取值:HMGET key field1 fields2... 5)获取KEY的所有字段和所有值:HGETALL key。如HGETALL user得到的是name lane age 23。每个返回都是独立的一行。 6)字段是否存在:HEXISTS key field。存在返回1,不存在返回0 7)当字段不存在时赋值:HSETNX key field value。如果key下面的字段field不存在,则建立field字段,且值为value。如果field字段存在,则不执行
任何操作。它的效果等于HEXISTS + HSET。但是这个命令的优点是原子操作。再高的并发也不会怕怕。 8)自增N:HINCREBY key field increment。同字符串的自增类型,不再阐述。 9)删除字段:DEL key field1 field2...删除指定KEY的一个或多个字段。 10)只获取字段名:HKEYS key。与HGETALL类似,但是只获取字段名,不获取字段值。 11)只获取字段值:HVALS key。与HGETALL类似,但是只获取字段值,不获取字段名。 12)获取字段数量:HLEN key。
2、应用场景
- 缓存HashMap结构型数据
- 模拟数据库关联查询
由于Hash的value值就是一个HashMap数据结构,相对于字符串序列化缓存信息更加直观,并且在更新操作上更加便捷,所以常常用于**用户信息**等管理。
哈希类型和关系型数据库有所不同,哈希类型是稀疏的,而关系型数据库是完全结构化的,关系型数据库可以做复杂的关系查询,而redis去模拟关系型复杂查询开发困难,维护成本高。
3、实现原理
Redis 中的 Hash和 Java的 HashMap 更加相似,都是数组+链表的结构.当发生 hash 碰撞时将会把元素追加到链表上.值得注意的是在 Redis的Hash中value只能是字符串,如图所示:
源码如下:
struct dictht { dictEntry **table; //entry 数组 long size; //数组长度 long used //数组中的元素个数 ... } struct dictEntry{ void *key; //hash 的 key void *val; //hash 的 value dictEntry *next; //下一个dictEntry 链表结构 }
在 Java 中 HashMap 扩容是个很耗时的操作,需要去申请新的数组,为了追求高性能,Redis 采用了渐进式 rehash
策略.这也是 hash 中最重要的部分。那么什么是渐进式呢?
在 hash 的内部包含了两个hashtable,一般情况下只是用一个。如图所示:
数据搬迁的操作放在 hash 的后续指令中,也就是来自客户端对 hash 的指令操作.一旦客户端后续没有指令操作这个 hash.Redis就会使用定时任务对数据主动搬迁。
- 正常情况下,当 hashtable 中元素的个数等于数组的长度时,就会开始扩容,扩容的新数组是原数组大小的 2 倍.如果 Redis 正在做 bgsave(持久化) 时,可能不会去扩容,因为要减少内存页的过多分离(Copy On Write).但是如果 hashtable 已经非常满了,元素的个数达到了数组长度的 5 倍时,Redis 会强制扩容.
- 当hashtable 中元素逐渐变少时,Redis 会进行缩容来减少空间占用,并且缩容不会受 bgsave 的影响,缩容条件是元素个数少于数组长度的 10%.
五、有序集合类型ZSet
1、类型定义
有序集合和散列一样,都用于存储键值对:有序集合的键被称为成员(member),每个成员都是各不相同的,而有序集合的值则被称为分值(score),分值必须是浮点数,有序集合是Redis里面唯一一个既可以根据成员访问元素,又可以根据分值以及分值的排序来访问元素的结构。
集合类型是无序的,每个元素是唯一的。那么有序集合就是有序的,每个元素是唯一的。有序集合类型和集合类型的差别是,有序集合为每个元素配备了一个属性:分数。有序集合就是根据分数来排序的。有序集合是使用散列表和跳跃表实现的。所以和列表相比,操作中间元素的速度也很快。时间复杂度尾O(log(N))。Redis数据类型中的有序集合类型比Redis数据类型中的列表类型更加耗费资源。
1)增加:ZADD key sorce1 value1 sorce2 value2...。 2)获取分数:ZSCORE key value。获取key的有序集合中值为value的元素的分数。 3)获取排名在某个范围内的元素列表:ZRANFGE key start stop [WITHSCORE]。获取排名在start和end之间的元素列表,包含start和end2个元素。
每个元素一行。如果有WITHSCORE参数,则一行元素值,一行分数。时间复杂度为O(LOGn+m)。如果分数相同,则0<0<A<Z<a<z。 4)获取指定分数范围的元素:ZRANGEBYSCORE key min max [WITHSCORE] [LIMIT offset count]。获取分数在min和max之间的元素列表。含两头。
每个元素一行。如果有WITHSCORE参数,则一行元素值,一行分数。如果min大于max则顺序反转。 5)为某个元素增加分数:ZINCRBY key increment value。指定的有序集合的值为value的元素的分数+increment。返回值后更改后的分数。 6)获取集合中元素的数量:ZCARD key。 7)获取指定分数范围内的元素个数:ZCOUNT key min max。 8)删除一个或多个元素:ZREM key value1 value2... 9)根据排名范围删除元素:ZREMRANGEBYRANK key start end。删除排名在start和end中的元素。 10)按照分数范围删除元素:ZREMRANGEBYSCORE key min max。 11)获得元素排名(正序):ZRANK key value。获取value在该集合中的从小到大的排名。 12)获得元素排名(倒序):ZREVRANK key value。获取value在该集合中从大到小的排名。 13)有序集合的交集:ZINTERSTORE storekey key1 key2...[WEIGHTS weight [weight..]] [AGGREGATE SUM|MIN|MAX]。用来计算多个集合的交集,
结果存储在storekey中。返回值是storekey的元素个数。AGGREGATE为SUM则storekey集合的每个元素的分数是参与计算的集合分数和。MIN是参
与计算的分数最小值。MAX是参与计算分数最大值。WEIGHTS 设置每个集合的权重,如WEIGHTS 1 0.1。那么集合A的每个元素分数*1,集合B的每
个元素分数*0.1 14)有序集合的并集:ZUNIONSTORE storekey key1 kye2...[WEIGHTS weight [weight..]] [AGGREGATE SUM|MIN|MAX]
2、应用场景
- 显示最新评论:score就是一个有序生成的不断增长的序列号,因此可以获取最新多少条评论。
- 获取Top N系列:有序集合经典使用场景。例如视频网站需要对用户上传的视频做排行榜,榜单维护可能是多方面:按照时间、按照播放量、按照获得的赞数等。
- 做交集、差集
3、实现原理
- 内部是以ziplist或者skiplist+hashtable来实现。
skiplist,也就是跳跃表,跳跃表是一种随机化的数据结构,在查找、插入和删除这些字典操作上,其效率可比拟于平衡二叉树(如红黑树),如下图:
六、特殊名词
1、压缩列表ziplist
压缩表(ziplist)是列表键(3.2之前的版本)和哈希键的底层实现之一。
作为哈希键的实现底层条件:当一个哈希键只包含少量的键值对,并且每个键值对的键和值要么是小整数数值要么就是长度较短的字符串时,Redis就会使用压缩列表来作为哈希键的底层实现。
压缩列表是Redis为了节约内存而开发的,由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点(entry),每个节点保存一个字节数组或者一个整数值。
源码如下:
// ziplist的成员宏定义 // (*((uint32_t*)(zl))) 先对char *类型的zl进行强制类型转换成uint32_t *类型, // 然后在用*运算符进行取内容运算,此时zl能访问的内存大小为4个字节。 #define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl))) //将zl定位到前4个字节的bytes成员,记录这整个压缩列表的内存字节数 #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t)))) //将zl定位到4字节到8字节的offset成员,记录着压缩列表尾节点距离列表的起始地址的偏移字节量 #define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2))) //将zl定位到8字节到10字节的length成员,记录着压缩列表的节点数量 #define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t)) //压缩列表表头(以上三个属性)的大小10个字节 #define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE) //返回压缩列表首节点的地址 #define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) //返回压缩列表尾节点的地址 #define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1) //返回end成员的地址,一个字节。 /* We know a positive increment can only be 1 because entries can only be * pushed one at a time. */ #define ZIPLIST_INCR_LENGTH(zl,incr) { //增加节点数 if (ZIPLIST_LENGTH(zl) < UINT16_MAX) //如果当前节点数小于65535,那么给length成员加incr个节点 ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl))+incr); }
图示如下:
压缩列表的部分组成成员:压缩列表没有使用结构体,而是采用的对成员宏定义。
2、跳跃表SkipList
跳跃表是一种可以对有序链表进行近似二分查找的数据结构,redis在两个地方用到了跳跃表,一个是实现有序集合,另一个是在集群节点中用作内部数据结构。
跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。在大部分情况下,跳跃表的效率可以和平衡树相媲美,并且因为跳跃表的实现比平衡树要来得更为简单,所以有不少程序都使用跳跃表来代替平衡树。
Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员(member)是比较长的字符串时,Redis就会使用跳跃表来作为有序集合键的底层实现。
和链表、字典等数据结构被广泛地应用在Redis内部不同,Redis只在两个地方用到了跳跃表,一个是实现有序集合键,另一个是在集群节点中用作内部数据结构,除此之外,跳跃表在Redis里面没有其他用途。
跳跃表的结构如下图所示:
Redis的跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义,其中zskiplistNode结构用于表示跳跃表节点,而zskiplist结构则用于保存跳跃表节点的相关信息,比如节点的数量,以及指向表头节点和表尾节点的指针等等。
上图展示了一个跳跃表示例,位于图片最左边的是zskiplist结构,该结构包含以下属性:
- header:指向跳跃表的表头节点
- tail:指向跳跃表的表尾节点
- level:记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)
- length:记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)
位于zskiplist结构右方的是四个zskiplistNode结构,该结构包含以下属性:
- 层(level):节点中用L1、L2、L3等字样标记节点的各个层,L1代表第一层,L2代表第二层,依次类推。每个层都带有两个属性:前进指针和跨度。
- 前进指针:用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中,连线上带有数字的箭头就代表前进指针,而那个数字就是跨度。当程序从表头向表尾进行遍历时,访问会沿着层的前进指针进行。
- 后退(backward)指针:节点中用BW字样标记节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
- 分值(score):各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中,节点按各自所保存的分值从小到大排列。
- 成员对象(obj):各个节点中的o1、o2和o3是节点所保存的成员对象。
注意表头节点和其他节点的构造是一样的:表头节点也有后退指针、分值和成员对象,不过表头节点的这些属性都不会被用到,所以图中省略了这些部分,只显示了表头节点的各个层。
分值和成员:
- 节点的分值(score属性):是一个double类型的浮点数,跳跃表中的所有节点都按分值从小到大来排序。
- 节点的成员对象(obj属性):是一个指针,它指向一个字符串对象,而字符串对象则保存着一个SDS值。
在同一个跳跃表中,各个节点保存的成员对象必须是唯一的,但是多个节点保存的分值却可以是相同的:分至相同的节点将按照成员对象在字典中的大小来进行排序,成员对象较小的节点会排在前面(靠近表头的方向),而成员对象较大的节点则会排在后面(靠近表尾的方向)。
具体跳跃表原理请参考:IT虾米网
原创文章,作者:Maggie-Hunter,如若转载,请注明出处:https://blog.ytso.com/3807.html