Redis 存储原理(1)

Stella981
• 阅读 750

Redis现在基本也算是后台开发的基础服务,基本像Mysql一样普遍在应用中使用了。我第一次接触的Nosql是memcache用来解决夸服务session共享问题。后来因为memcache无法持久化问题改为使用Redis。这次主要针对Redis做一个整理。

Redis数据类型

类型

特点说明

String

类型是 Redis 最基本的数据类型,string 类型的值最大能存储 512MB

Hash

Redis hash 是一个 string 类型的 field 和 value 的映射表,hash 特别适合用于存储对象。

List

Redis 列表是简单的字符串列表,按照插入顺序排序。你可以添加一个元素到列表的头部(左边)或者尾部(右边)

Set

Redis 的 Set 是 string 类型的无序集合。集合是通过哈希表实现的,所以添加,删除,查找的复杂度都是 O(1)

ZSet

与Set不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序

HyperLogLog

在 2.8.9 版本添加是用来做基数统计的算法,HyperLogLog 的优点是,在输入元素的数量或者体积非常非常大时,计算基数所需的空间总是固定 的、并且是很小的

Bitmaps

可做为布隆过滤器使用

GeoHash

Redis 3.2 版本地理空间位置(纬度、经度、名称)

存储(实现)原理

数据模型

以set k1 hello为例,因为Redis是KV的数据库,它是通过hashtable实现的(我们把这个叫做外层的哈希)。所以每个键值对都会有一个dictEntry(源码位置:dict.h),里面指向了key和value的指针。next指向下一个dictEntry。

typedef struct dictEntry {
    void *key; /* Key关键字定义 */
    union {
        void *val;  /* value定义 */
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;/*下一个节点*/
} dictEntry;

Redis 存储原理(1)

key是字符串,但是Redis没有直接使用C的字符数组,而是存储在自定义的SDS中。

value既不是直接作为字符串存储,也不是直接存储在SDS中,而是存储在redisObject中。实际上五种常用的数据类型的任何一种,都是通过redisObject来存储的。

redisObject

redisObject定义在src/server.h文件中

typedef struct redisObject {
    unsigned type:4; /*对象类型,包括 OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET*/
    unsigned encoding:4;/* 具体数据结构*/
    unsigned lru:LRU_BITS; /*24位,对象最后一次被命令程序访问的时间,与内存回收有关*/
                           /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;/*引用计数。当refcount为0的时候,表示该对象已经不被任何对象引用,则可以进行垃圾回收了*/
    void *ptr;/*指向对象实际的数据结构*/
} robj;


127.0.0.1:6379>set num1 1 
OK
127.0.0.1:6379>set str1 "aaaadddddddddddddddddddddddddddddddccccccccccccccccccc"
OK
127.0.0.1:6379>set str2 beijing
OK
127.0.0.1:6379>object encoding num1
"int"
127.0.0.1:6379>object encoding str1
"embstr"
127.0.0.1:6379>object encoding str2 
"raw

字符串类型的内部编码有三种:

1、int,存储8个字节的长整型(long,2^63-1)。

2、embstr,代表embstr格式的SDS(SimpleDynamicString简单动态字符串),存储小于44个字节的字符串。

3、raw,存储大于44个字节的字符串(3.2版本之前是39字节)。

/* <object.c>
 * Create a string object with EMBSTR encoding if it is smaller than
 * OBJ_ENCODING_EMBSTR_SIZE_LIMIT, otherwise the RAW encoding is
 * used.
 *
 * The current limit of 44 is chosen so that the biggest string object
 * we allocate as EMBSTR will still fit into the 64 byte arena of jemalloc. */
#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
什么是SDS?

Redis中字符串的实现。在3.2以后的版本中,SDS又有多种结构(sds.h):sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64,用于存储不同的长度的字符串,分别代表:
2^5=32byte
2^8=256byte
2^16=65536byte=64KB
2^32byte=4GB。

为什么Redis要用SDS实现字符串?

C语言本身没有字符串类型(只能用字符数组char[]实现)。

1、使用字符数组必须先给目标变量分配足够的空间,否则可能会溢出。

2、如果要获取字符长度,必须遍历字符数组,时间复杂度是O(n)。

3、C字符串长度的变更会对字符数组做内存重分配。

4、通过从字符串开始到结尾碰到的第一个'\0'来标记字符串的结束,因此不能保存图片、音频、视频、压缩文件等二进制(bytes)保存的内容,二进制不安全。

SDS的特点:

1、不用担心内存溢出问题,如果需要会对SDS进行扩容。

2、获取字符串长度时间复杂度为O(1),因为定义了len属性。

3、通过“空间预分配”(sdsMakeRoomFor)和“惰性空间释放”,防止多次重分配内存。

4、判断是否结束的标志是len属性(它同样以'\0'结尾是因为这样就可以使用C语言中函数库操作字符串的函数了),可以包含'\0'。

c字符串

SDS

embstr

只读

获取字符串长度的复杂度为O(N)

获取字符串长度的复杂度为O(1)

API是不安全的,可能会造成缓冲区溢出

API是安全的,不会早晨个缓冲区溢出

修改字符串长度N次必然需要执行N次内存重分配

修改字符串长度N次最多需要执行N次内存重分配

只能保存文本数据

可以保存文本或者二进制数据

可以使用所有<string.h>库中的函数

可以使用一部分<string.h>库中的函数

embstr和raw的区别?

embstr的使用只分配一次内存空间(因为RedisObject和SDS是连续的),而raw需要分配两次内存空间(分别为RedisObject和SDS分配空间)。

因此与raw相比,embstr的好处在于创建时少分配一次空间,删除时少释放一次空间,以及对象的所有数据连在一起,寻找方便。

而embstr的坏处也很明显,如果字符串的长度增加需要重新分配内存时,整个RedisObject和SDS都需要重新分配空间,因此Redis中的embstr实现为只读。

int和embstr什么时候转化为raw?

当int数据不再是整数,或大小超过了long的范围(2^631=9223372036854775807)时,自动转化为embstr。

127.0.0.1:6379>set s1 1 
OK
127.0.0.1:6379>append s1 a
(integer)2
127.0.0.1:6379>object encoding s1
"raw"
明明没有超过阈值,为什么变成raw了?
127.0.0.1:6379>set s2 a 
OK
127.0.0.1:6379>object encoding s2
"embstr"
127.0.0.1:6379>append s2 b
(integer)2
127.0.0.1:6379>object encoding s2
"raw"

对于embstr,由于其实现是只读的,因此在对embstr对象进行修改时,都会先转化为raw再进行修改。

因此,只要是修改embstr对象,修改后的对象一定是raw的,无论是否达到了44个字节。

当长度小于阈值时,会还原吗?

关于Redis内部编码的转换,都符合以下规律:编码转换在Redis写入数据时完成,且转换过程不可逆,只能从小内存编码向大内存编码转换(但是不包括重新set)

为什么要对底层的数据结构进行一层包装呢?

通过封装,可以根据对象的类型动态地选择存储结构和可以使用的命令,实现节省空间和优化查询速度。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Stella981 Stella981
3年前
Nginx + lua +[memcached,redis]
精品案例1、Nginxluamemcached,redis实现网站灰度发布2、分库分表/基于Leaf组件实现的全球唯一ID(非UUID)3、Redis独立数据监控,实现订单超时操作/MQ死信操作SelectPollEpollReactor模型4、分布式任务调试Quartz应用
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这