Redis设计与实现之字符串哈希表列表

目录

一、字符串

1、字符串编码

2、编码的选择

二、哈希表

1、字典编码的哈希表

2、压缩列表编码的哈希表

3、编码的选择

4、哈希命令的实现

三、列表

1、 编码的选择

2、 列表命令的实现

3、阻塞的条件

4、 阻塞

5、 阻塞因 LPUSH 、RPUSH 、LINSERT 等添加命令而被取消

6、 先阻塞先服务(FBFS)策略

7、 阻塞因超过最大等待时间而被取消


一、字符串

REDIS_STRING (字符串)是 Redis 使用得最为广泛的数据类型,它除了是 SET 、GET 等命令 的操作对象之外,数据库中的所有键,以及执行命令时提供给 Redis 的参数,都是用这种类型 保存的。

1、字符串编码

字符串类型分别使用 REDIS_ENCODING_INT 和 REDIS_ENCODING_RAW 两种编码:

  • REDIS_ENCODING_INT 使用 long 类型来保存 long 类型值。

  • REDIS_ENCODING_RAW 则使用 sdshdr 结构来保存 sds (也即是 char* )、long long 、 double 和 long double 类型值。

    换句话来说,在 Redis 中,只有能表示为 long 类型的值,才会以整数的形式保存,其他类型 的整数、小数和字符串,都是用 sdshdr 结构来保存。

2、编码的选择

新创建的字符串默认使用 REDIS_ENCODING_RAW 编码,在将字符串作为键或者值保存进数据库时,程序会尝试将字符串转为 REDIS_ENCODING_INT 编码。 3.2.3 字符串命令的实现Redis 的字符串类型命令,基本上是通过包装 sds 数据结构的操作函数来实现的,没有什么需 要说明的地方。

二、哈希表

REDIS_HASH (哈希表) 是 HSET 、 HLEN 等命令的操作对象,它使用REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_HT 两种编码方式:

1、字典编码的哈希表

当哈希表使用字典编码时,程序将哈希表的键(key)保存为字典的键,将哈希表的值(value)保存为字典的值。

哈希表所使用的字典的键和值都是字符串对象。

下图展示了一个包含三个键值对的哈希表:

 

2、压缩列表编码的哈希表

当使用 REDIS_ENCODING_ZIPLIST 编码哈希表时,程序通过将键和值一同推入压缩列表,从而 形成保存哈希表所需的键 -值对结构: 

新添加的 key-value 对会被添加到压缩列表的表尾。 当进行查找/删除或更新操作时,程序先定位到键的位置,然后再通过对键的位置来定位值的位置。

3、编码的选择

创建空白哈希表时,程序默认使用 REDIS_ENCODING_ZIPLIST 编码,当以下任何一个条件被满

足时,程序将编码从切换为 REDIS_ENCODING_HT :
• 哈希表中某个键或某个值的长度大于 server.hash_max_ziplist_value (默认值为 64)。
• 压缩列表中的节点数量大于server.hash_max_ziplist_entries(默认值为512)。

4、哈希命令的实现

哈希类型命令的实现全都是对字典和压缩列表操作函数的包装,以及几个在两种编码之间进行转换的函数,没有特别要讲解的地方。

三、列表

REDIS_LIST (列表) 是 LPUSH 、 LRANGE 等命令的操作对象,它使用

REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_LINKEDLIST 这两种方式编码:

1、 编码的选择

创建新列表时 Redis 默认使用 REDIS_ENCODING_ZIPLIST 编码,当以下任意一个条件被满足时,列表会被转换成 REDIS_ENCODING_LINKEDLIST 编码:
• 试 图 往 列 表 新 添 加 一 个 字 符 串 值, 且 这 个 字 符 串 的 长 度 超 过server.list_max_ziplist_value (默认值为 64 )。
• ziplist 包含的节点超过 server.list_max_ziplist_entries (默认值为 512 )。

2、 列表命令的实现

因为两种底层实现的抽象方式和列表的抽象方式非常接近,所以列表命令几乎就是通过一对一地映射到底层数据结构的操作来实现的。 既然这些映射都非常直观,这里就不做赘述了,在以下的内容中,我们将焦点放在 BLPOP 、BRPOP 和 BRPOPLPUSH 这个几个阻塞命令的实现原理上。

3、阻塞的条件

BLPOP 、BRPOP 和 BRPOPLPUSH 三个命令都可能造成客户端被阻塞,以下将这些命令统 称为列表的阻塞原语。

阻塞原语并不是一定会造成客户端阻塞:

• 只有当这些命令被用于空列表时,它们才会阻塞客户端。

• 如果被处理的列表不为空的话,它们就执行无阻塞版本的 LPOP 、RPOP 或 RPOPL- PUSH 命令。

作为例子,以下流程图展示了 BLPOP 决定是否对客户端进行阻塞过程:

4、 阻塞

 当一个阻塞原语的处理目标为空键时,执行该阻塞原语的客户端就会被阻塞。 阻塞一个客户端需要执行以下步骤:

1. 将客户端的状态设为“正在阻塞”,并记录阻塞这个客户端的各个键,以及阻塞的最长时(timeout)等数据。

2. 将客户端的信息记录到server.db[i]->blocking_keys中(其中i为客户端所使用的数 据库号码)。

3. 继续维持客户端和服务器之间的网络连接,但不再向客户端传送任何信息,造成客户端 阻塞。

步骤 2 是将来解除阻塞的关键,server.db[i]->blocking_keys 是一个字典,字典的键是那 些造成客户端阻塞的键,而字典的值是一个链表,链表里保存了所有因为这个键而被阻塞的客 户端(被同一个键所阻塞的客户端可能不止一个):

在上图展示的 blocking_keys 例子中,client2 、client5 和 client1 三个客户端就正被 key1 阻塞,而其他几个客户端也正在被别的两个 key 阻塞。

当客户端被阻塞之后,脱离阻塞状态有以下三种方法:
1. 被动脱离:有其他客户端为造成阻塞的键推入了新元素。
2. 主动脱离:到达执行阻塞原语时设定的最大阻塞时间。
3. 强制脱离:客户端强制终止和服务器的连接,或者服务器停机。

以下内容将分别介绍被动脱离和主动脱离的实现方式。

5、 阻塞因 LPUSH 、RPUSH 、LINSERT 等添加命令而被取消

通过将新元素推入造成客户端阻塞的某个键中,可以让相应的客户端从阻塞状态中脱离出来(取消阻塞的客户端数量取决于推入元素的数量)。
LPUSH 、RPUSH 和 LINSERT 这三个添加新元素到列表的命令,在底层都由一个

pushGenericCommand 的函数实现,这个函数的运作流程如下图:

当向一个空键推入新元素时,pushGenericCommand 函数执行以下两件事:

1. 检查这个键是否存在于前面提到的 server.db[i]->blocking_keys 字典里,如果是的 话,那么说明有至少一个客户端因为这个 key 而被阻塞,程序会为这个键创建一个 redis.h/readyList 结构,并将它添加到 server.ready_keys 链表中。

2. 将给定的值添加到列表键中。 readyList 结构的定义如下:

readyList 结构的 key 属性指向造成阻塞的键,而 db 则指向该键所在的数据库。

typedef struct readyList { 
    redisDb *db;

    robj *key;
} readyList;

举个例子,假设某个非阻塞客户端正在使用 0 号数据库,而这个数据库当前的 blocking_keys属性的值如下:

如果这时客户端对该数据库执行 PUSH key3 value ,那么 pushGenericCommand 将创建一个 db 属性指向 0 号数据库、key 属性指向 key3 键对象的 readyList 结构,并将它添加到服务器 server.ready_keys 属性的链表中:

在我们这个例子中,到目前为止,pushGenericCommand 函数完成了以下两件事:

1. 将readyList添加到服务器。
2. 将新元素value添加到键key3。

虽然 key3 已经不再是空键,但到目前为止,被 key3 阻塞的客户端还没有任何一个被解除阻塞状态。

为了做到这一点,Redis 的主进程在执行完 pushGenericCommand 函数之后,会继续调用 handleClientsBlockedOnLists 函数,这个函数执行以下操作:

  1. 如果 server.ready_keys 不为空,那么弹出该链表的表头元素,并取出元素中的 readyList 值。

  2. 根据readyList值所保存的key和db,在server.blocking_keys中查找所有因为key 而被阻塞的客户端(以链表的形式保存)。

  3. 如果key不为空,那么从key中弹出一个元素,并弹出客户端链表的第一个客户端,然 后将被弹出元素返回给被弹出客户端作为阻塞原语的返回值。

  4. 根据readyList结构的属性,删除server.blocking_keys中相应的客户端数据,取消 客户端的阻塞状态。

  5. 继续执行步骤 3 和 4 ,直到 key 没有元素可弹出,或者所有因为 key 而阻塞的客户端都

    取消阻塞为止。

  6. 继续执行步骤 1 ,直到 ready_keys 链表里的所有 readyList 结构都被处理完为止。用一段伪代码描述以上操作可能会更直观一些:

    def handleClientsBlockedOnLists(): 
        # 执行直到 ready_keys 为空
        while server.ready_keys != NULL: 
            # 弹出链表中的第一个 readyList
            rl = server.ready_keys.pop_first_node() 
            # 遍历所有因为这个键而被阻塞的客户端
            for client in all_client_blocking_by_key(rl.key, rl.db):
                # 只要还有客户端被这个键阻塞,就一直从键中弹出元素
                # 如果被阻塞客户端执行的是 BLPOP ,那么对键执行 LPOP 
                # 如果执行的是 BRPOP ,那么对键执行 RPOP
                element = rl.key.pop_element()
                if element == NULL:
                    # 键为空,跳出 for 循环
                    # 余下的未解除阻塞的客户端只能等待下次新元素的进入了 
                    break
                else:
                    # 清除客户端的阻塞信息                             
                    server.blocking_keys.remove_blocking_info(client)     
                    # 将元素返回给客户端,脱离阻塞状态 
                    client.reply_list_item(element)

    6、 先阻塞先服务(FBFS)策略

    值得一提的是,当程序添加一个新的被阻塞客户端到 server.blocking_keys 字典的链表中 时,它将该客户端放在链表的最后,而当 handleClientsBlockedOnLists 取消客户端的阻塞 时,它从链表的最前面开始取消阻塞:这个链表形成了一个 FIFO 队列,最先被阻塞的客户端 总值最先脱离阻塞状态,Redis 文档称这种模式为先阻塞先服务(FBFS,first-block-first-serve)。

    举个例子,在下图所示的阻塞状况中,如果客户端对数据库执行 PUSH key3 value ,那么只有 client3 会被取消阻塞,client6 和 client4 仍然阻塞;如果客户端对数据库执行 PUSH key3 value1 value2 ,那么 client3 和 client4 的阻塞都会被取消,而客户端 client6 依然处于 阻塞状态:

7、 阻塞因超过最大等待时间而被取消

前面提到过,当客户端被阻塞时,所有造成它阻塞的键,以及阻塞的最长时限会被记录在客户端里面,并且该客户端的状态会被设置为“正在阻塞” 。

每次 Redis 服务器常规操作函数(server cron job)执行时,程序都会检查所有连接到服务器 的客户端,查看那些处于“正在阻塞”状态的客户端的最大阻塞时限是否已经过期,如果是的话, 就给客户端返回一个空白回复,然后撤销对客户端的阻塞。

可以用一段伪代码来描述这个过程:

def server_cron_job(): 
    # 其他操作 ...
    # 遍历所有已连接客户端
    for client in server.all_connected_client:
    # 如果客户端状态为“正在阻塞”,并且最大阻塞时限已到达 
        if client.state == BLOCKING and \
        client.max_blocking_timestamp < current_timestamp(): 
        # 那么给客户端发送空回复, 脱离阻塞状态
        client.send_empty_reply()
        # 并清除客户端在服务器上的阻塞信息
        server.blocking_keys.remove_blocking_info(client) 
# 其他操作 ...

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/251202.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【MySQL】(DDL) 数据类型 和 表操作-修改 删除

目录 介绍&#xff1a; 1.数值类型 3.日期类型 修改表&#xff1a; 示列&#xff1a; 介绍&#xff1a; 在之前建表语句内&#xff0c;用到了 int cvarchar &#xff0c;那么在mysql内除了 以上的数据类型 还有那些常见数据类型 mysql 中的数据类型有很多种 &#xff0c…

QML 自定义进度条组件开发

一、效果预览 二、介绍&#xff1a; 自定义的QML 屏幕亮度拖动进度条组件CusProgressBar 可跟鼠标移动 更改进度条样式 三、代码 import QtQuick 2.12 import QtQuick.Controls 2.12 import QtQuick.Controls.Material 2.12/***author:Zwj*csdn:来份煎蛋吧*date:2023/12/16*…

C++实现简单的猜数字小游戏

猜数字 小游戏介绍&#xff1a;猜数字游戏是令游戏机随机产生一个100以内的正整数&#xff0c;用户输入一个数对其进行猜测&#xff0c;需要你编写程序自动对其与随机产生的被猜数进行比较&#xff0c;并提示大了&#xff0c;还是小了&#xff0c;相等表示猜到了。如果猜到&…

Appium —— 初识移动APP自动化测试框架Appium

说到移动APP自动化测试&#xff0c;代表性的测试框架非Appium莫属&#xff0c;从今天开始我们将从APP结构解析、Appium框架学习、安卓/iOS自动化测试实战、自动遍历回归测试、自动化测试平台及持续集成&#xff0c;多个维度一起由浅入深的学废Appium 今天我们先来初步认识Appi…

nodejs+vue+微信小程序+python+PHP运动项目推荐系统-计算机毕业设计推荐

运动项目推荐系统的整体架构确定以后&#xff0c;再来看运动项目推荐系统的主要功能模块图。整体的功能模块包括前台和后台&#xff0c;前台只要实现了注册用户功能&#xff0c;主要的页面&#xff0c;包括首页&#xff0c;体育资讯&#xff0c;体育项目&#xff0c;公告信息等…

基于ASF-YOLO融合空间特征和尺度特征的新型注意力尺度序列融合模型开发构建医学场景下细胞分割检测识别系统,以【BCC、DSB2018数据集为基准】

作者提出了一种新的基于注意尺度序列融合的YOLO框架&#xff08;ASF-YOLO&#xff09;&#xff0c;该框架结合了空间和尺度特征&#xff0c;实现了准确快速的细胞实例分割。基于YOLO分割框架&#xff0c;我们使用尺度序列特征融合&#xff08;SSFF&#xff09;模块来增强网络的…

pybind11:对比C++和Python解线性方程组的速度

前言 上篇博客介绍了如何在用pybind11实现ndarray和C数组的转换自由&#xff0c;pybind11&#xff1a;实现ndarray转C原生数组&#xff08;没看过的朋友可以去看一看&#xff09;下面我们以一个实际的算法例子演示一下如何使用这个技术&#xff0c;方便的实现 Python 调用 C 写…

基于linux系统的Tomcat+Mysql+Jdk环境搭建(三)centos7 安装Tomcat

Tomcat下载官网&#xff1a; Apache Tomcat - Which Version Do I Want? JDK下载官网&#xff1a; Java Downloads | Oracle 中国 如果不知道Tomcat的哪个版本应该对应哪个版本的JDK可以打开官网&#xff0c;点击Whitch Version 下滑&#xff0c;有低版本的&#xff0c;如…

Caused by: java.net.ConnectException: 拒绝连接: hadoop104/192.168.124.130:4142

项目场景&#xff1a;hadoop102接收消息&#xff0c;自定义拦截器&#xff0c;包含hello的发往hadoop103,不包含的发往hadoop104 报错原因&#xff1a; 原因1&#xff1a; 应该先开启接收方&#xff08;服务端&#xff09;&#xff0c;hadoop103,hadoop104,最后开启hadoop10…

编译android的C版本Lua库

本文讲述如何使用android studio 编译最新版本的Lua开源库),请自行下载。 我们提供的Demo,可以自行下载,工程结构如下: 本文编译的是Lua 5.4.6的版本,编译采用cmake的方式,我们支持编译静态库和动态库(我们在这一讲里:“Lua与***C在Android上的互调”是使用静态库)…

智能优化算法应用:基于JAYA算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于JAYA算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于JAYA算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.JAYA算法4.实验参数设定5.算法结果6.参考文献7.MA…

大数据与深度挖掘:如何在数字营销中与研究互动

数字营销最吸引人的部分之一是对数据的内在关注。 如果一种策略往往有积极的数据&#xff0c;那么它就更容易采用。同样&#xff0c;如果一种策略尚未得到证实&#xff0c;则很难获得支持进行测试。 数字营销人员建立数据信心的主要方式是通过研究。这些研究通常分为两类&…

Vue3快速上手笔记

Vue3快速上手 1.Vue3简介 2020年9月18日&#xff0c;Vue.js发布3.0版本&#xff0c;代号&#xff1a;One Piece&#xff08;海贼王&#xff09;耗时2年多、2600次提交、30个RFC、600次PR、99位贡献者github上的tags地址&#xff1a;https://github.com/vuejs/vue-next/release…

Docker单机部署OceanBase

文章目录 说明机器软硬件要求指导文档本次部署环境说明 OceanBase单机部署&#xff08;Docker&#xff09;一&#xff1a;拉取 OceanBase 数据库相关镜像二&#xff1a;启动 OceanBase 数据库实例完整启动日志展示 三&#xff1a;连接实例遇到报错&#xff1a;没有mysql客户端 …

selenium-grid4.3.0两种模式记录

selenium-grid4.3.0两种模式记录 本文运行&#xff0c;需要提前配置好Java11以及安装好Chrom、Firefox、Safari其中一个浏览器&#xff0c;如果是Chrom、Firefox需要下载对应版本的驱动&#xff0c;并给 webdriver 配置环境变量&#xff0c;Safari浏览器Mac系统会自带&#xf…

HiveSql语法优化二 :join算法

Hive拥有多种join算法&#xff0c;包括Common Join&#xff0c;Map Join&#xff0c;Bucket Map Join&#xff0c;Sort Merge Buckt Map Join等&#xff0c;下面对每种join算法做简要说明&#xff1a; Common Join Common Join是Hive中最稳定的join算法&#xff0c;其通过一个M…

案例067:基于微信小程序的小区租拼车管理信息系统

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序…

【MySQL】(DDL) 数据库操作

创建&#xff1a; create database 数据库名称; //创建数据库 create database if not exists 数据库名 ; //创建数据库并添加判断 &#xff08;如果存在就不创建不存在就创建 &#xff09; create database 数据库名 default charset 字符集 ; //创建数据库并设置字符集 查…

计算机毕业设计 基于SpringBoot的二手物品交易管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…

漏刻有时数据可视化Echarts组件开发(42)动态创建DIV容器

效果展示 引入外部文件 <script src"js/jquery.min.js"></script><script type"text/javascript" src"js/echarts.5.4.3.min.js"></script>CSS层叠样式表 实现一行3列效果&#xff0c;自动换行&#xff1b; .ecbox {he…