基本数据类型
Redis的基本数据类型有五种,分别是
- String
- List
- Hash
- Set
- SortedSet 这些基本的数据类型构成了其他数据类型的基石,而这些基本数据类型又对应着不同的底层实现,不同的底层实现往往是针对不同的使用场景做的特殊的优化,下面将总结基本的数据类型,整理同底层实现的关系。
String
字符串在Redis使用是非常多的,虽然叫做字符串,但是其也能代表long类型,因此可以配合incr
指令完成自增等等,作为数字类型,其比较省空间的,因为其复用了RedisObject
中的指针字段(8字节)下面是RedisObject
的结构,其分为两部分,8字节的Redis对象元数据信息,8字节的指针,其中Redis对象的元数据信息存储了类型的LRU信息,真正的编码格式等等,而如果字符串存储的是数字类型,则复用了8字节的指针的位置。
当其存储字符串的时候,则其指针则指向了Redis中的SDS
结构,也就是简单动态字符串,既然是动态字符串,有动态二字说明其有自动扩容的能力,因此在SDS
的基本结构中,存在capacity
和len
这两个基本的属性,来标识当前一共有多少空间可用,和使用了多少空间。
针对SDS
的结构,Redis有两种不同的编码格式来存储简单动态字符串,分别是embstr
编码和raw编码
,其中embstr
是紧凑型的,RedisObject
和真正的字符串结构是连续存储的,而row
格式编码则是分开存储的,依赖RedisObject
中的指针来定位,当字符串的小于等于44字节的时候,使用embstr
编码,其他的情况使用row
编码,两种编码格式大概如下图所示。
需要注意的是,SDS在字符串的末尾增加了'\0'
,这样的好处了可以重用C函数,当然带来的坏处自然就是引入了定界符自然就不能支持完全的二进制数据了。
对于简单动态字符串,比较重要的就是其扩容机制,字符串长度小于1M使用加倍扩容方式,如果大小超过1M则扩容时以1M大小扩容。但是如果字符串总长度不能超过512M
List
列表的底层有不同的编码格式支持,其基本上可以看作一个链表,因此寻找下标多半是O(n)
的操作,但是当列表的元素非常少的时候,其内部使用ziplist
也就是压缩列表来存储,当元素特别多的时候,就转化为linkedlist了,不过为了减少malloc
的调用次数以及减少碎片,Redis使用了多个ziplist
串成一个链表实现,也就是所谓的quicklist
快速列表。下面将对ziplist
和quicklist
做一个简单的描述。
压缩列表是一个在内存中紧凑在一起的列表,其有一些基本的信息和entry
以及在ziplist
尾部的tail,是0xFF
标记压缩列表结束。 压缩列表的基本信息包括压缩列表的大小,压缩列表的长度以及最后一个entry的偏移,之所以要有这个偏移,是为了找到最后一个entry,而每个entry都记录上一个元素的大小,通过计算就知道上一个entry的地址,这样方便的从后向前进行遍历。压缩列表结构如下所示。
由于内存紧凑的,当发生修改的时候很容易发生内存的重新分配和复制的过程,因此都是在元素较少的时候使用,不仅仅是list
,zset
和 hash
容器对象在元素个数较少的时候也采用压缩列表。
快速列表quicklist
是多个ziplist
组成的双向链表,这样设计可以减少双向链表指针的开销,兼有ziplist
的优势又有linkedlist的优势
Hash
和Java的HashMap类似,其采用的也是拉链法来解决Hash冲突,而不同的是对于Redis这样的中间件,多个服务可能都在用,在rehash方面为了避免一次性执行rehash操作带来的阻塞,使用了渐进式rehash,所谓渐进式Rehash就是将一次rehash操作拆解为多次执行,Redis内部对于Hash字典类型有两个hashtable,当需要扩容的时候,先分配内存。
- 然后每处理一个请求,就将原来hashtable中的一个桶随机分配
- Redis还会在定时任务中对字典进行主动搬迁
Redis的Hash是具有扩容和缩容的条件的
- 一般情况下,当 hash 表中元素的个数桶的数目时,就会开始扩容,扩容的新数组是原数组大小的2倍
- 缩容的条件是元素个数低于数组长度也就是桶个数的10%
Set
Set其实就是Value为null
的hash,如果都存储的是整数类型的话,就会使用intset
来进行编码,如果插入了非整数的值,encoding将会从intset
变为hashtable
的机构。 和ziplist
相比,intset
是有序的,可以进行二分查找,而ziplist
是无序的
SortedSet
一个Set能排序自然而然想到的是基本的数据结构,TreeMap等AVLTree,而在Redis中使用SkipList来完成这样的工作。