Redis设计与实现：读书笔记之一

blueice

　　第一部分：数据结构与对象

• Redis支持的数据类型
  
  
  
  • 字符串对象
    
  • 列表对象
    
  •           Hash对象
    
  • 集合对象
    
  • 有序集合对象
    
  
  

　　2.数据结构

• Redis的所有数据类型都是：
  
  
  
  • key-value pair
    
  • 对象
    
  
  
• Redis的Key是字符串对象
  

　　3.公共命令
　　DEL key [key ...]
　　删除一个key
　　MIGRATE host port key destination-db timeout
　　原子性的将key从redis的一个实例移到另一个实例
　　PTTL key
　　获取key的有效毫秒数
　　SORT key [BY pattern] [LIMIT offset count] [GET pattern [GET pattern ...
　　对队列、集合、有序集合排序
　　DUMP key
　　导出key的值
　　MOVE key db
　　移动一个key到另一个数据库
　　RANDOMKEY
　　返回一个随机的key
　　TTL key
　　获取key的有效时间（单位：秒）
　　EXISTS key
　　查询一个key是否存在
　　OBJECT subcommand [arguments [arguments ...]]
　　检查内部的再分配对象
　　RENAME key newkey
　　将一个key重命名
　　TYPE key
　　获取key的存储类型
　　EXPIRE key seconds
　　设置一个key的过期的秒数
　　PERSIST key
　　移除key的过期时间
　　RENAMENX key newkey
　　重命名一个key,新的key必须是不存在的key
　　EXPIREAT key timestamp
　　设置一个UNIX时间戳的过期时间
　　PEXPIRE key milliseconds
　　设置一个key的过期的毫秒数
　　RESTORE key ttl serialized-value
　　Create a key using the provided serialized value, previously obtained using DUMP.
　　KEYS pattern
　　查找所有匹配给定的模式的键
　　PEXPIREAT key milliseconds-timestamp
　　设置一个带毫秒的UNIX时间戳的过期时间
　　SCAN cursor [MATCH pattern] [COUNT count]
　　增量迭代key
　　第二部分：简单动态字符串（Simple dynamic string，SDS,sdshdr）
　　1.SDS的定义

　　2.SDS优点

• Len计算的复杂度为O（1），传统的C语言求Length的复杂度为O（N）
  
• 通过空间预分配，减少了字符串修改时带来的内存重新分配的性能问题。
  
• 通惰性过释放，提升字符串缩短操作的性能。
  
• 通过len判断字符串是否结束，而不是'\0',确保数据是二进制安全的。
  

　　第三部分：链表（list）
　　1.链表定义
　　作为redis列表键的底层实现之一（当元素较多 或者包含的元素都是较长的字符串时）。

• dup函数用于复制链表节点所保存的值。
  
• free函数用于释放链表节点所保存的值。
  
• match函数用于对比链表中的值与输入的比对峙是否相等。
  

　　第三部分：字典（dict）
　　1.字典的实现与定义
　　字典是通过Hashtable实现的。是redis中哈希键的实现之一（当元素数量较多，或者元素值都是 比较长的字符串时）。

　　大小为4的空hashtable的结构如下：

• dictht.table属性是一个数组，记录了dictEntry。
  
• 每个dictEntry结构保存一个键值对
  
• dictht.size记录了哈希表的大小，即table数组的大小
  
• dictht.used记录了哈希表中已有的节点数量
  
• dictht.sizemask=size-1
  
• dictEntry.next属性指向另外一个哈希表节点的指针，可以将多个hast值相同的键值对连接在一起，以解决键冲突的问题
  

• dict.type和dict.privdata是针对不同类型的键值对，为创建多态字典而创建的。
  
• dict.ht是一个包含了两个元素的数组，一般 情况下只使用ht[0],ht[1]只在对ht[0]进行rehash时使用。
  
• rehashindex记录了rehash的进度。
  

　　2.Hash算法

• 当将一个新的键值对添加到字典中时，程序需要现对key值进行hash计算和索引值计算。然后根据索引值，将包含新键值对的dictEntry放到dictht.table的指定索引上。具体逻辑如下：
  

• 键冲突：当两个或以上的键被分配到dictht.table中的同一个索引上时，就会发出冲突。Redis通过dictEntry.Next创建链表解决此问题。程序默认总是把新节点放入到dictEntry.next的表头位置。
  

　　3.Rehash

• 随着操作的不断执行，哈希表保存的键值会逐渐增多或者减少，为了让哈希表的负载因子（used/size）保存在一个合理的范围内，当哈希表中的键值对数量数量太多和太少时，程度对哈希表的大小进行扩容或收缩。
  
• rehash步骤如下：
  
  
  
  • 为dict.ht[1]分配表空间，其大小取决于dict.ht[0].used.
    
  • 将保存在dict.ht[0]中的所有键值hash到dict.ht[1]中。Rehash是指重新计算哈希值和索引值。
    
  • 释放dict.ht[0]
    
  • 将dict.ht[1]设置为dict.ht[0]
    
  
  
• rehash时机
  
  
  
  • 服务没有执行BGSave或BGRewirteAOF命令，并且负载因子>1
    
  • 服务器只在执行BGSave或BGRewirteAOF命令，并且负载因子>5
    
  
  
• 渐进式rehash，如果ht数量巨大，一次性的rehash会阻塞服务。所以rehash都是渐进式的，步骤如下：
  
  
  
  • 为dict.ht[1]分配表空间，让字典同时持有两个哈希表
    
  • 将rehashindex设置为0（默认为-1），开始渐进式rehash。
    
  • 在rehash进行时，每次对字典进行CRUD操作，程序除了执行指定操作外，还会顺带将ht[0]在rehashindex索引上的所有键值对rehash到ht[1]上。完成后将rehashindex+1.
    
  • 随着字典操作的不断增加，ht[0]所有的值rehash到ht[1]中，rehashindex设置为-1，rehash完成。
    
  
  

　　第四部分：跳跃表（zskiplist）
　　1.定义
　　一种有序数据结构，通过在每个节点中维持多个指向其他节点的指针，达到快速访问节点的目的。是有序集合键的底层实现之一。

　　zskiplist结构：

• header：指向跳跃表的表头节点
  
• tail：指向跳跃表的表尾节点
  
• level：记录当前跳跃表内，层次最大的那个节点的层次（header不参与计算）。
  

　　zskiplistnode结构：

• level：
  

　　第五部分：整数集合（intset）
　　1.定义
　　用于保存整数值的集合数据结构。集合键的底层实现之一（当集合键都是数值，并且集合元素数量 不多时，才采用）。

• contents：contents中的项按照值大小从小到大有序排列，数组中不包含任何重复项。
  
• length：contents的长度。
  
• encoding：
  
  
  
  • =INTSET_ENC_INT16：contents为int16_t数组，数组中的每个项目也是int16_t类型，取值范围：-32768~32767
    
  • =INTSET_ENC_INT32：contents为int32_t数组，数组中的每个项目也是int32_t类型，取值范围：-2147483648~2147483647
    
  • =INTSET_ENC_INT64：contents为int64_t数组，数组中的每个项目也是int64_t类型，取值范围：-9223372036854775808~9223372036854775807
    
  
  

　　2.升级
　　当新加入的元素值比现有类型要长时，集合要先进行upgrade。步骤为：

• 根据新元素类型，扩展整数集合底层数组空间大小，并未新元素分配空间
  
• 将数据组中原有数值转换为与新元素相同的数据类型，并将转换后的数值放置到正确位置上
  
• 将新元素加入到新数组中
  

　　第七部分：压缩列表（ziplist）
　　1.定义
　　列表键和哈希键底层实现之一。当列表键值包含少量列表项目，并且要么每个列表项都是小值，要不是长度比较短的字符串，redis就使用压缩列表做列表键的底层实现。
　　是为节约内存而开发。
　　由一系列特殊编码的连续内存快组成的顺序型数据结构

　　2.连锁更新
　　entryX中的对象结构如下，

　　考虑一种情况，在一个压缩列表中，有多个连续的、长度介于250~253字节之间的节点，因为所有节点的长度都小于254，所以previous_entry_length属性都是一个字节长。如果在压缩表头加入一个长度大于254的新节点，后续节点的previous_entry_length都需要变为5个字节长度，从而引发连锁的结构变更。
　　实际应用中，这种情况较少。
　　第八部分：对象
　　1.定义
　　SDS、链表、字典、压缩列表、整数集合是Redis中的主要数据结构，但是Redis并没有直接使用这些数据结构实现键值对数据库。而是通过这些结构创建了一个对象系统，这些对象包括字符串对象、列表对象、哈希对象、集合对象、有序集合对象五类对象。
　　Redis使用对象表示数据库中的键与值。每当我们在数据库中创建一个键值对时，都会创建两个对象：键对象、值对象，每个对象都有redisObject结构表示。

　　说明：redisobject还包含了refcount、lru属性，分别用于计算引用次数、对空时长

• type:对象类型
  

• encoding:记录了对象的使用数据结构
  

　　2.字符串对象
　　字符串对象的编码可以是int、embstr、raw。

　　如果字符串的长度<=32，字符串对象使用embstr编码存储。 embstr比raw性能更高。
　　差异化：embstr需要一次构造、一次释放，二raw不是。
　　命令：  
　　APPEND key value
　　追加一个值到key上
　　GETBIT key offset
　　返回位的值存储在关键的字符串值的偏移量
　　MGET key [key ...]
　　获得所有key的值
　　SETEX key seconds value
　　设置key-value并设置过期时间（单位：秒）。seconds是过期时间。
　　BITCOUNT key [start] [end]
　　统计字符串指定起始位置的字节数
　　GETRANGE key start end
　　获取存储在key上的值的一个子字符串
　　MSET key value [key value ...]
　　设置多个key value
　　SETNX key value
　　SETNX是"SET if Not eXists
　　MSETNX key value [key value ...]
　　设置多个key value,仅当key存在时
　　GETSET key value
　　设置一个key的value，并获取设置前的值
　　SETRANGE key offset value
　　覆盖key对应的string的一部分，从指定的offset处开始，覆盖value的长度
　　DECR key
　　整数原子减1。对key对应的数字做减1操作。如果key不存在，那么在操作之前，这个key对应的值会被置为0。如果key有一个错误类型的value或者是一个不能表示成数字的字符串，就返回错误。这个操作最大支持在64位有符号的整型数字
　　INCR key
　　执行原子加1操作
　　PSETEX key milliseconds value
　　Set the value and expiration in milliseconds of a key
　　STRLEN key
　　获取指定key值的长度
　　DECRBY key decrement
　　原子减指定的整数
　　INCRBY key increment
　　执行原子增加一个整数
　　SET key value
　　设置一个key的value值
　　GET key
　　获取key的值
　　INCRBYFLOAT key increment
　　执行原子增加一个浮点数
　　SETBIT key offset value
　　设置或者清空key的value(字符串)在offset处的bit值
　　3.列表对象
　　列表对象的编码可以是：ziplist或linkedlist.

　　命令:
　　BLPOP key [key ...] timeout
　　删除，并获得该列表中的第一元素，或阻塞，直到有一个可用
　　LLEN key
　　获得队列(List)的长度
　　LREM key count value
　　从列表中删除元素
　　RPUSH key value [value ...]
　　从队列的右边入队一个元素
　　BRPOP key [key ...] timeout
　　删除，并获得该列表中的最后一个元素，或阻塞，直到有一个可用
　　LPOP key
　　从队列的左边出队一个元素
　　LSET key index value
　　设置队列里面一个元素的值
　　RPUSHX key value
　　设置队列里面一个元素的值
　　BRPOPLPUSH source destination timeout
　　弹出一个列表的值，将它推到另一个列表，并返回它;或阻塞，直到有一个可用
　　LPUSH key value [value ...]
　　从队列的左边入队一个或多个元素
　　LTRIM key start stop
　　修剪到指定范围内的清单
　　LINDEX key index
　　获取一个元素，通过其索引列表
　　LPUSHX key value
　　当队列存在时，从队到左边入队一个元素
　　RPOP key
　　从队列的右边出队一个元素
　　LINSERT key BEFORE|AFTER pivot value
　　在列表中的另一个元素之前或之后插入一个元素
　　LRANGE key start stop
　　从列表中获取指定返回的元素
　　RPOPLPUSH source destination
　　删除列表中的最后一个元素，将其追加到另一个列表
　　4.哈希对象
　　哈希对象的编码可以是ziplist或hashtable

　　命令：
　　HDEL key field [field ...]
　　删除一个或多个哈希域
　　HINCRBY key field increment
　　将哈希集中指定域的值增加给定的数字
　　HMGET key field [field ...]
　　获取hash里面指定字段的值
　　HSETNX key field value
　　设置hash的一个字段，只有当这个字段不存在时有效
　　HEXISTS key field
　　判断给定域是否存在于哈希集中
　　HINCRBYFLOAT key field increment
　　将哈希集中指定域的值增加给定的浮点数
　　HMSET key field value [field value ...]
　　设置hash字段值
　　HVALS key
　　获得hash的所有值
　　HGET key field
　　读取哈希域的的值
　　HKEYS key
　　获取hash的所有字段
　　HSCAN key cursor [MATCH pattern] [COUNT count]
　　迭代hash里面的元素
　　HGETALL key
　　HGETALL key
　　HLEN key
　　获取hash里所有字段的数量
　　HSET key field value
　　设置hash里面一个字段的值
　　5.集合对象
　　集合对象的编码可以是：intset或hashtable

　　命令
　　SADD key member [member ...]
　　添加一个或者多个元素到集合(set)里
　　SINTER key [key ...]
　　获得两个集合的交集
　　SMOVE source destination member
　　移动集合里面的一个key到另一个集合
　　SSCAN key cursor [MATCH pattern] [COUNT count]
　　迭代set里面的元素
　　SCARD key
　　获取集合里面的元素数量
　　SINTERSTORE destination key [key ...]
　　获得两个集合的交集，并存储在一个关键的结果集
　　SPOP key
　　删除并获取一个集合里面的元素
　　SUNION key [key ...]
　　添加多个set元素
　　SDIFF key [key ...]
　　获得队列不存在的元素
　　SISMEMBER key member
　　确定一个给定的值是一个集合的成员
　　SRANDMEMBER key [count]
　　从集合里面随机获取一个key
　　SUNIONSTORE destination key [key ...]
　　合并set元素，并将结果存入新的set里面
　　SDIFFSTORE destination key [key ...]
　　获得队列不存在的元素，并存储在一个关键的结果集
　　SMEMBERS key
　　获取集合里面的所有key
　　SREM key member [member ...]
　　从集合里删除一个或多个key
　　6.有序集合对象
　　有序集合对象的编码可以是ziplist、skiplist

　　skiplist编码的有序集合对象使用zset结构最为底层实现，其结构为：
　　Typeof struct zset
　　{
　　Zskiplist *zsl;
　　Dict *dict;
　　}

　　命令：
　　ZADD key score member [score member ...]
　　添加到有序set的一个或多个成员，或更新的分数，如果它已经存在
　　ZRANGE key start stop [WITHSCORES]
　　返回的成员在排序设置的范围，由指数
　　ZREMRANGEBYSCORE key min max
　　删除一个排序的设置在给定的分数所有成员
　　ZSCORE key member
　　获取成员在排序设置相关的比分
　　ZCARD key
　　获取一个排序的集合中的成员数量
　　ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]
　　返回的成员在排序设置的范围，由得分
　　ZREVRANGE key start stop [WITHSCORES]
　　在排序的设置返回的成员范围，通过索引，下令从分数高到低
　　ZUNIONSTORE destination numkeys key [key ...] [WEIGHTS weight [weight ..
　　添加多个排序集和导致排序的设置存储在一个新的关键
　　ZCOUNT key min max
　　给定值范围内的成员数与分数排序
　　ZRANK key member
　　确定在排序集合成员的索引
　　ZREVRANGEBYSCORE key max min [WITHSCORES] [LIMIT offset count]
　　返回的成员在排序设置的范围，由得分，下令从分数高到低
　　ZINCRBY key increment member
　　增量的一名成员在排序设置的评分
　　ZREM key member [member ...]
　　从排序的集合中删除一个或多个成员
　　ZREVRANK key member
　　确定指数在排序集的成员，下令从分数高到低
　　ZINTERSTORE destination numkeys key [key ...] [WEIGHTS weight [weight ...
　　相交多个排序集，导致排序的设置存储在一个新的关键
　　ZREMRANGEBYRANK key start stop
　　在排序设置的所有成员在给定的索引中删除
　　ZSCAN key cursor [MATCH pattern] [COUNT count]
　　迭代sorted sets里面的元素
　　7.内存回收
　　Redis通过构建了一个引用计数器，来跟踪对象的引用情况。在适当的时候进行回收。