redis就数据结构 单线程 高可用 缓存应用

reidis 数据结构

!> redis中键的类型是字符串,值的数据类型有很多

  1. 字符串
  2. 列表
  3. 字典
  4. 集合
  5. 有序集合
  6. bitmap
  7. hyperloglog
  8. geospatial
  9. stream(5.0推出的数据类型。支持多播的可持久化的消息队列,用于实现发布订阅功能,借鉴了kafka的设计。

对应的底层实现:底层实现

字符串:

  1. embstr编码:是专门用于保存短字符串的一种优化编码方式,跟正常的字符编码会调用两次内存分配函数来分别创建 redisObject 和 sdshdr 结构(动态字符串结构),而 embstr 编码则通过调用一次内存分配函数来分配一块连续的内存空间

列表

两种实现方法:

  1. 压缩列表(ziplist):相较于数组存储每个元素大小固定,必须以元素中最长的作为长度存储,因此压缩列表相比于数据会节省内存。如图所示:WYwtSB
  2. 双向循环链表

使用压缩列表的条件(列表中存储的数据量比较少):

  1. 列表中保存的单个数据(有可能是字符串类型)小于64字节
  2. 列表中数据个数少于512个

压缩列表的两个好处:

  1. 节省内存
  2. 支持不同类型数据的存储。
  3. 因为数据存储在一片连续的内存空间,通过键获取值为列表类型的数据,读取效率非常高。

字典

两种实现方法:

  1. 压缩列表
  2. 散列表

当存储数据量比较少,才会使用压缩列表,具体需要同时满足如下两个条件:

  1. 字典中保存的键和值的大小都要小于64字节
  2. 字典中键值对的个数都要小于512个

散列表:redis使用murmurhash2这种运行速度快,随机性号的哈希算法作为哈希函数。
对于哈希冲突,使用链表法进行解决,除此之外,还支持散列表的动态扩容、缩容。
由于散列表中数据量增大,装载因子不断增大,因此为了避免性能下降,当装载因子大于1的时候,会进行扩容,扩容大小为原来的2倍左右。
装载因子小于0.1的情况下会触发缩容,缩小为字典中数据个数的大约2倍大小。
由于扩容和缩容需要做大量的数据搬移和哈希值的重新计算,比较耗时,redis中我们使用散列表中的渐进式扩容缩容策略,将数据的搬移分批进行,避免了大量数据一次性搬移导致的服务停顿。

集合

两种实现方式:

  1. 有序数组
  2. 散列表

当同时满足如下两个条件的时候就使用有序数组:

  1. 存储的数据都是整数
  2. 存储的数据元素个数不超过512个

有序集合

两种实现方式

  1. 压缩列表
  2. 跳表

数据量比较小的时候,redis会用压缩列表来实现有序集合,有两个前提:

  1. 所有数据的大小都要小于64字节
  2. 元素个数要小于128个

如何将数据结构持久化到硬盘?我们主要有两种解决思路。

  1. 第一种是清除原有的存储结构,只将数据存储到磁盘中。当我们需要从磁盘还原数据到内存 的时候,再重新将数据组织成原来的数据结构。实际上,Redis 采用的就是这种持久化思 路。
    1.1 不过,这种方式也有一定的弊端。那就是数据从硬盘还原到内存的过程,会耗用比较多的时 间。比如,我们现在要将散列表中的数据存储到磁盘。当我们从磁盘中,取出数据重新构建 散列表的时候,需要重新计算每个数据的哈希值。如果磁盘中存储的是几 GB 的数据,那重 构数据结构的耗时就不可忽视了。
  2. 第二种方式是保留原来的存储格式,将数据按照原有的格式存储在磁盘中。我们拿散列表这 样的数据结构来举例。我们可以将散列表的大小、每个数据被散列到的槽的编号等信息,都 保存在磁盘中。有了这些信息,我们从磁盘中将数据还原到内存中的时候,就可以避免重新 计算哈希值。

References

  1. redis九大数据类型数据结构及底层源码
  2. 数据结构与算法之美:52

note info 默认主题色,适合中性的信息

标题(可选)

Windows 10不是為所有人設計,而是為每個人設計

查看代码测试

评论