您现在的位置是:首页 > 正文

Redis源码篇

2024-01-30 22:39:49阅读 0

原理篇

在这里插入图片描述

字符串

Redis的字符串叫着"SDS",也就是Simple Dynamic String,是一个带长度信息的字符数组。包含

struct SDS{ 
    T capacity  容量
    T len 数组长度
    byte flags 标志位
    char[] content 数组内容
}

SDS的好处?

为了避免频繁分配新数组空间,支持动态扩容,规定字符串长度不得超过512MB,长度小于1MB时,扩容采用加倍策略,超过1MB后,每次扩容只会多分配1MB.

字符串的存储方式?

有三种储存方式。分别为embstr,raw,int。
先讲区别,当字符串是数字时,存储类型为int,当字符串长度小于等于44时,为embstr,它将RedisObject对象头和SDS对象连续存放在一起,malloc一次,当字符串长度大于44时,为raw,malloc两次,对象头和SDS对象不连续,ptr指针指向SDS对象。
为什么是44呢?
先来看Redis对象头的数据结构

struct RedisObject{
      int type //4bit 类型
      int encoding  //4bit 存储方式
      int lru  //24bit lru信息(lfu也用这个字段)
      int refcount  //4byte  引用计数
      void *ptr  //8byte  指向内容
}

RedisObject对象头需要占用16个字节。SDS开始占用3字节,后面补一位‘\0’,jemalloc一般一次会分配64字节,64-16-3-1=44字节,所有一般以44字节区分字符串的大小。

List(列表)

Redis的列表相当于链表而不是数组。
当元素比较小的时候采用Ziplist(压缩列表),将所有元素彼此紧挨着,分配的是一个连续的空间,当数据比较多的是时候变成quciklist(快速列表) 将多个ziplist用指针连接起来。

压缩列表

为什么不用链表实现压缩列表?因为链表必须维护指针,增加了内存损耗和内容碎片。

struct ziplist{ 
       int zlbytes  //整个压缩列表占用字节数
       int zltail_offset //最后一个元素距离压缩列表其实位置的偏移量
       int zllength  //元素个数
       T[] entries //元素内容
       int zlend //标准压缩列表的结束 值恒为 0XFF
}

offset字段快速定位到最后一个元素,然后倒着遍历。,entry随着元素类型不同,也会有不一样的结构。

struct entry{
    int prevlen     //前一个entry的字节长度
    int encoding   //元素类型编码
    byte[] content  //元素内容
}

用prevlen字段实现倒序遍历,是一个可变整数,当字符串小于254时,采用一个字节表示,如果达到或者超过254时,就使用5个字节表示(第一个字节是0xFE),剩下的四个字节表示字符串长度。
我们可能会有疑问,1个字节最大能表示到255,为什么要拿254作为临界值?因为255这个数用作了特殊的用途——标示ziplist的结尾,即用作了zlend字段。之前说过,为了防止混淆,每个真正存储数据的entry的第一个字段都不会为255,而prelen就是entry的第一个字段。
缺点:第一点是ziplist都是紧凑存储,没有冗余空间,每一次添加新元素都要重新分配内存。第二点是一个entry的长度发生改变,后边的prelen也发生改变,会出现级联更新现象。

快速列表

struct quicklist{
       quicklistNode* head
       quicklistNode* tail
       long count         //元素总和
       int nodes         //ziplist 节点的个数
       int compressDepth  //LZF算法压缩深度
}
struct   quicklistNode{
       quicklistNode* prev
       quicklistNode* next
       ziplist* zl     //如果当前节点的数据没有压缩,那么它指向一个ziplist结构;否则,它指向一个quicklistLZF结构。     
       int32 size      //ziplist的字节总数
       int16 count    //ziplist中的元素数量
       int2  encoding//存储类型 是元素字节数组话说LZF压缩存储
}

在这里插入图片描述

每个ziplist存多少元素

默认单个ziplist长度为8Kb,超过后就会另起一个ziplist。

优点

中合了数组和链表的优点。

hash(字典)

默认hash表的长度是4.当哈希对象保存的所有键值对的键和值的字符串长度都小于64字节,
哈希对象保存的键值对数量小于512个底层采用ziplist,数据量大变成hashtable。Redis默认的hash函数是siphash。

redisDb{
  dict
  expires
  blocking_keys
  ready_keys
  watched_keys
  id
  avg_ttl
  expires_cursor
  defray_later
}
dict{
    type
    privdata
    dictht ht[2]  //包含两个hashtable,一个存放值,一个用于字典扩容缩容
    rehashidx
    iterators
}
dictht{
    dictEntry table  //链表
    size    //第一维数组的长度
    sizemask   //
    userd    //hash表中元素个数
}
dictEntry{
   key
   union{
   val
   u64
   s64
   }
   dictEntry* next  //链表下一个节点
}

渐进式rehash

在这里插入图片描述

扩容和缩容

没有执行BGSAVE和BGREWRITEAOF指令的情况下,哈希表的负载因子大于等于1时进行扩容;
正在执行BGSAVE和BGREWRITEAOF指令的情况下,哈希表的负载因大于等于5时进行扩容;
负载因子小于0.1时,Redis自动开始对哈希表进行收缩操作;

set(集合)

struct intset{
 int32  encoding      //决定整数位宽
 int32 lenght       //元素个数
 int<T>  contents   //整数数组
}

它的内部是键值对是无序的,唯一的。它的内部实现相当于一个特殊的字典,字典中所有的value都是一个值NULL。
当数据可以用整形表示时,set集合将被编码为intset数据类型,intset是紧凑的数组结构,两个条件任务不满足时set将用dict存储数据。1.元素个数小于set-max-intset-entries,2.元素无法用整形表示

ZSET(有序集合)

struct zslnode{
     string value   //key
     double score  //分数
     zslnode*[] forwards   //多层连接指针
     zslnode*    backward   //回溯指针
}
struct  zsl{ 
      zslnode* header   //跳跃列表头指针
      int maxLevel       //跳跃列表当前的最高层
      map<String,zslnode*> ht      //hash结构的所有键值对
}

更新过程

当value存在,score更新时,一个简单的策略是先删除这个元素,然后再插入这个元素。

listpack

sstruct listpakc{
    int32 total_bytes  //占用的总字节数
    int16 size          //元素个数
    T[] entries        //紧凑排列的元素列表
    int8 end           //同zlend一样,恒为0xFF
}

比ziplist少了一个zltail_offset字段,这个字段可以通过total_bytes和最后一个元素的长度字段计数出来。但目前只有Stream结构使用。

SCAN

keys是遍历算法,复杂度是O(n),会阻塞主线程。

  1. SCAN的复杂度虽然也是O(n),但是它是通过游标分步进行的,不会阻塞主线程
  2. 提供limit参数
  3. 服务器不需要为游标保持状态,游标的唯一状态就是scan返回给客户端的游标整数

RDB

fork一个进程,遍历hashtable,利用copy on write ,把整个db dump保存下来。save,shutdown,slave命令会触发这个操作。
粒度较大,如果save之前宕机了,中间的操作没法恢复。

COW(copy on write)

怎么解决子进程做持久化,父进程的修改不影响持久化。
操作系统的cow机制,当父进程对其中一个页面的数据进行修改时,会将共享的页面复制一份分离出来,然后对这个复制的页面进行修改
写时复制技术的定义是:创建子进程不分配物理空间,只分配和父进程相同的虚拟内存空间,公用物理内存,无论是父进程还是子进程对物理内存进行改动,回复制相应的内存区域。

AOF

先执行指令再日志存盘
AOF 重写,使用bgrewriteaof指令对AOF日志进行瘦身。当程序对AOF日志文件进行写操作时,实际上是将内容写到了内核为文件描述符分配的一个内存缓存中,然后内核会异步将脏数据刷回磁盘。
fsync可以设置1s一次,一个指令一次。

网站文章

  • 深入理解JVM:java对象的创建过程?

    深入理解JVM:java对象的创建过程?

    Step1:类加载检查 虚拟机遇到一条 new 指令时,首先将去检查这个指令的参数是否能在常量池中定位到这个类的符号引用,并且检查这个符号引用代表的类是否已被加载过、解析和初始化过。如果没有,那必须先...

    2024-01-30 22:39:42
  • 敏捷软件开发 之 第6章《一次编程实践》读书笔记

    敏捷软件开发 之 第6章《一次编程实践》读书笔记

    3月箴言人的思想是了不起的,只要专注于某一项事业,就一定会做出使自己感到吃惊的成绩来。—— 马克·吐温本章是详细表述了一个保龄球记分功能的开发过程本章重要前提(也许我们中的大多数并不是很清楚保龄球的记分规则,而编写程序我认为最重要的的就是先理清规则):第一步:得知需求并分析需求;第二步:根据需求规则,写出基本测试用例(这个用例尚未添加任何逻辑);第三步:将规则中的...

    2024-01-30 22:39:34
  • 【设计模式】建造器模式(Builder Pattern)

    【设计模式】建造器模式(Builder Pattern)

     ???? 核心通过建造器,使用多个简单的对象一步一步构造出一个复杂的对象。 ???? 问题场景你现在从一名程序开发者转行为了一名房屋建筑师。你的任务就是建房子。你很快建好了一个 房子(House) ...

    2024-01-30 22:39:02
  • oracle网络访问权限,ORACLE的网络配置,与权限初步

    1、服务器1.1常用工具emnetmgrnetca1.2相关配置文件listener.oratnsnames.oraC:/oracle/product/10.2.0/db_1/NETWORK/ADMI...

    2024-01-30 22:38:57
  • 08 - 安装脚本Section - [Setup]

    安装脚本Section[Setup] section此section包含安装程序和卸载程序使用的全局设置。您创建的任何安装都需要包含指令。这是[Setup]的示例:[Setup]AppName=My ...

    2024-01-30 22:38:49
  • 文件上传-.user.ini的妙用

    文件上传-.user.ini的妙用

    文件上传漏洞-.user.ini在文件上传中的妙用

    2024-01-30 22:38:42
  • 数组过滤c语言,将NSArray过滤到Objective-C中的新NSArray中

    有很多方法可以做到这一点,但到目前为止,最肯定的方法是使用[NSPredicate predicateWithBlock:]:NSArray *filteredArray = [array filte...

    2024-01-30 22:38:13
  • SVN上传文件

    SVN上传文件

    SVN使用技巧

    2024-01-30 22:38:05
  • MongoDB模糊查询($regex查询、正则表达式匹配查询) 热门推荐

    MongoDB模糊查询($regex查询、正则表达式匹配查询) 热门推荐

    MongoDB的模糊查询可以使用 $regex 运算符通过正则表达式来进行匹配查询。 $regex :为查询中的模式匹配字符串提供正则表达式功能 。 语法: { &lt; field &gt;: { $ regex : / pattern / , $ options : ‘’ } } { &lt; field &gt;: { $ regex : ‘pattern’ , $ optio...

    2024-01-30 22:37:58
  • linux中命令tat,照着书敲linux下载安装命令?大汇总来咯!!!

    linux中命令tat,照着书敲linux下载安装命令?大汇总来咯!!!

    linux下载安装的命令一. 本地上传1.1 使用scp命令1.2 使用xshell工具1.3 常用方法二. 网络远程下载2.1 curl_一种下载文件的工具2.2 wget_软件下载工具(非安装方式...

    2024-01-30 22:37:29