压缩列表是列表键和hash键的底层实现之一, 当一个键只包含少量列表项、且每个列表项要么是小整数值、要么是长度比较短的字符串、那么redis就会使用压缩列表作为底层实现

压缩列表的组成

压缩列表是Redis为了节约内存开发的, 是一系列特殊编码的连续内存块组成的顺序型数据结构,

一个压缩列表可以包含任意多个节点(entry), 每个节点可以保存一个字节数组或者一个整数值

zltytes: 压缩列表的总长度

zltail: 表示表头和表尾节点的位置偏移量

zllen: 表示压缩列表包含的节点数

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值, 字节数组可以是下边任意一种:

1. 长度小于等于63(2⁶-1)字节的字节数组
2. 长度小于等于16383 (2¹⁴-1)字节的字节数组
3. 长度小于等于 4294964295 (2³²-1)字节的字节数组

而整数值则可以是下边六种长度的一种:

1. 4位, 介于 0~12 之间的无符号整数
2. 1字节长的有符号整数
3. 3字节长的有符号整数
4. int16_t 类型的整数
5. int32_t 类型的整数
6. int64_t 类型的整数

每个压缩列表节点由 previous_entry_length、encoding、content 三个部分组成

previous_entry_length

节点的previous_entry_length 属性以字节为单位, 记录压缩列表前一个节点的长度, 可以是1字节 或者 5字节, 若前一个节点的长度＜254字节, 则 previous_entry_length 的长度为1字节, 前一个节点的长度保存在这里; 若前一节点的长度≥254字节, 则privous_entry_length 的属性为 5字节, 其中第一字节的值为 0xFE(254)

因为节点的previous_entry_length 属性记录了前一个节点的长度, 所以程序可以通过指针运算、根据当前节点的起始地址计算前一个节点的起始地址, 压缩列表的 从表尾向表头遍历 操作是使用这一原理实现的. 完整过程如下:

• 首先、我们拥有指向压缩列表表尾节点 entry4 起始地址的指针p1(指向表尾节点的指针可以通过指向压缩列表 起始地址的指针 + zltail 属性得到)
• 通过 p1 - entry4.previous_entry_lenght 可以得到指向entry4 节点的前一节点entry3 的起始地址指针p2
• 同理可以得到 entry2 的起始指针 p3 和 entry1 的起始指针 p4, 完成整个压缩列表的遍历

encoding

节点的 encoding 属性记录了content 属性所保存的数据类型及长度,

1. 一字节、两字节、五字节 长, 值的最高位为: 00、01 或 10 的是 字节数组编码, 这种编码表示节点的 content属性 保存着的是 字节数组, 数组长度由 编码除去最高两位之后的其它位记录
2. 一字节长, 值的最高位以11开头的是整数编码, 这种编码表示节点的 content属性 保存的是 整数值, 整数值的类型和长度由编码除去高两位之后的其它位记录

content 属性

节点的content属性 负责保存节点的值, 节点的值可以是一个字节数组或者整数、值的类型和长度由 encoding属性 来决定.

• 编码的最高两位 00 表示节点保存的是一个字节数组
• 编码的后六位 001011 记录字节数组的长度 11
• content属性保存着节点值 hello world

• 编码 11000000 表示节点保存的是一个 int16_t 类型的整数值
• content 属性保存着节点的值 10086

连锁更新

每个节点的previous_entry_length 属性记录了前一个节点的长度, 若<254字节, 需要1字节空间保存, 若≥254字节, 需要5字节空间保存, 假设现有1压缩列表, e1 ~ eN 节点的长度都在 250~253字节之间, 此时, 若需要插入一个长度≥254字节的节点new到表头, 那么new节点将成为e1的前置节点, 因为e1的previous_entry_length属性仅1字节, 无法保存new节点的属性, 需要重新对压缩列表执行空间分配, 扩展e1节点的previous_entry_length属性, 那么麻烦事儿来了…, e1原本的长度介于250~253之间, e2.privous_entry_length可以使用1字节, 现在e1的长度为 250+4 ~ 253+4, e2就需要5字节来记录e1的长度, …., 依次引起连锁更新, 程序需要不断扩展空间, 类似的、删除节点也可能早上连锁更新

最坏情况下、需要对压缩列表执行N次空间重分配工作, 每次空间重分配的最坏复杂度为 O(N), 所以连锁更新的最坏复杂度为 O(N²), 复杂度非常高, 但真正造成性能问题的概率很小:

• 压缩列表恰好有多个连续的、长度介于250~253字节之间的节点、连锁更新才可能被引发, 这种情况本身出现的概率较低
• 即时出现连锁更新、但只要被更新的节点不多、就不会对性能造成影响, eg、三五个节点的连锁更新绝不会影响性能

所以: ziplistPush的平均时间复杂度仅为 O(N), 可以放心的使用

重点回顾

• 压缩列表是一种为节约内存而开发的顺序型数据结构
• 压缩列表是列表键和hash键的底层实现之一
• 压缩列表可以包含多个节点、每个节点可以保存一个字节数组或者整数值
• 添加新节点到压缩列表、或者从压缩列表删除节点，可能会引起连锁更新操作, 但概率较低

redis中的五种数据对象都使用了不同的底层编码方式、那相互之间是如何转化的呢 ?

字符串对象

字符串对象的编码可以是int, raw 或者 embstr

若一个字符串对象保存的是整数值, 且这个整数值可以使用long类型来表示、则 字符串对象会将整数值保存在ptr属性 (将 void * 转换成 long), 将字符串的编码设置为 int.

若一个字符串对象保存的是一个字符串值, 且长度＞ 32字节, 那么该字符串对象会使用一个简单动态字符串 SDS 来保存、并将对象的编码设置为 raw

若字符串值的长度≤32字节, 会使用embstr来保存, 它和raw编码一样、都使用redisObject结构和sdshdr结构来表示字符串对象, 但raw编码会调用两次内存分配来分表创建redisObject结构和sdshdr结构, 而embstr编码则调用一次内存分配分配一块连续的空间, 依次包含redisObject 和 embstr结构

embstr编码的字符串对象在执行命令时、产生的效果与raw编码一致, 但获得的好处是:

1. emstr编码将创建对象时需要的内存分配次数从raw编码的两次降为1次
2. 释放时、也只需要调用一次内存释放函数, raw编码需要两次
3. embstr编码的字符串对象保存在连续空间, 比raw编码更好的利用缓存带来的优势

编码转换

int编码的字符串对象和embstr编码的字符串对象在满足条件的情况下, 会被转换为raw编码的字符串对象, 对于int编码的字符串对象来说、若向对象执行了一些明朗、使对象保存的不再是整数值、编码会从 int -> raw

eg. 通过append命令、向整数值的字符串对象追加一个字符串值, 因为追加操作指南对字符串值执行、所以会转为raw类型编码

因为redis没有为embstr编码的字符串对象编写修改程序(只有int和raw编码的字符串对象才有), 所以embstr编码的对象实际上是只读的, 当执行任何修改时、程序会先将对象的编码从embstr转化成raw, 再执行修改, 所以: embstr编码的对象在执行修改后、总会变成raw编码

字符串命令的实现

列表对象

列表对象的编码可以是ziplist 或者linkedlist

ziplist 编码的列表对象使用压缩列表作为底层实现, 每个压缩列表节点保存了一个列表元素, eg. 执行rpush命令

1
2

redis> rpush numbers 1 "three" 5
3

若使用的是ziplist编码、则值对象如下所示:

另外, linkedlist编码的列表对象使用双端链表作为底层实现, 每个双端链表节点保存一个字符串对象, 而每个字符串对象都保存了一个列表元素, eg. 上边numbers使用linkedlist编码如下:

linkedlist编码的列表对象在底层的双端链表结构中包含了多个字符串对象

注意:

为了简化字符串对象的表示, 使用了 StringObject来标记, 完整表示如下:

编码转换

列表对象满足下边两个条件时、使用ziplist编码

1. 列表对象保存的所有字符串元素的长度都＜64字节
2. 列表对象保存的元素数量小于512个

否则: 使用linkedlist编码

注意:

上限值可配置, list-max-ziplist-value 和 list-max-ziplist-entries 选项.

列表命令的实现

列表键的值为列表对象, 用于键操作的所有命令都是针对列表对象来构建的, 下边是部分实现

hash对象

hash对象的编码可以是ziplist或者hashtable

ziplist编码的hash对象使用压缩列表作为底层实现, 当有新的键值对要加入到hash对象时, 程序会先将保存了键的压缩列表节点推入表尾, 然后将保存了值的压缩列表节点推入到压缩列表表尾, 所以:

1. 保存了统一键值对的两个节点总是紧挨在一起, 保存键的节点在前、保存值的节点在后
2. 先添加到hash对象中的键值对会被放在压缩列表的表头方向, 后添加到hash对象中的键值对被放到表尾方向

eg. 执行hset命令

1
2
3
4
5
6

redis> hset profile name "test"
(integer) 1
redis> hset profile age 25
(integer) 1
redis> hset profile career "programmer"
(integer) 1

若profile使用的是ziplist编码, 值对象如下所示:

另一方面: hashtable编码的hash对象使用字典作为底层实现, hash对象中的每个键值对都使用一个字典键值对保存,

1. 字典的每个键是一个字符串对象、保存了键值对中的键
2. 字典的每个值都是字符串对象、保存了键值对的值

编码转换

当hash对象可以同时满足下边条件时、使用ziplist编码:

1. hash对象保存的所有键值对的键和值的长度都＜64字节
2. hash对象保存的键值对的数量＜512个

注意:

上限值可以使用hash-max-ziplist-value 和 hash-max-ziplist-entries选项配置

键和值的长度不满足、都会引起编码的转换.

hash命令的实现

因为hash键的值作为hash对象, 用于hash键的所有命令都是针对hash对象来构建的, 部分实现如下:

集合对象

集合对象的编码可以是intset 或者 hashtable

intset编码的集合对象使用整数集合作为底层实现, 集合对象包含的所有元素都被保存在整数集合里. eg.

1
2

redis> SADD numbers 1 3 5
(integer) 3

另一方面, hashtable编码的集合对象使用字典作为底层实现, 字典的每个键都是一个字符串对象、每个字符串对象包含了一个集合元素, 而字典的值全部被设置为 NULL

eg. 以下代码将创建一个如图示的hashtable编码集合对象

1
2

redis> sadd fruits "apple" "banana" "cherry"
(integer) 3

编码的转换

当集合对象满足下边两个条件时、使用intset编码:

1. 集合对象保存的所有元素都是整数值
2. 集合对象保存的元素数量不超过512个

注意:

第二个条件上限值可修改, set-max-intset-entries 选项, 当intset编码的集合对象任意条件不满足时、会执行对象的编码转换操作, 原本保存在整数集合中的所有元素会被转移并保存到字典里, 编码从intset -> hashtable, eg.

1
2
3
4
5
6
7
8
9
10
11
12
13

redis> eval "for i=1, 512 do redis.call('sadd', keys[1], i) end" 1 integers
(nil)
redis> scard integers
(integer) 512
redis> object encoding integers
"intset"

redis> sadd integers 10086 // 再添加一个元素
(integer) 1
redis> scard integers
(integer) 513
redis> object encoding integers
"hashtable"

集合命令的实现

有序集合对象

有序集合的编码可以是ziplist 或者 skiplist

ziplist编码的压缩列表对象使用压缩列表作为底层实现, 每个集合元素使用两个紧挨着的压缩列表节点保存, 第一个节点保存元素的成员, 第二个元素保存元素的分值

压缩列表内的集合元素按照分值从小到大排序, 分值较小的元素放在靠近表头的方向.

eg. 执行 zadd命令、服务器将创建一个有序集合对象作为price键的值

1
2

redis> zadd price 8.5 apple 5.0 banana 6.0 cherry 
(integer) 3

若压缩列表的值对象使用的是ziplist编码, 则结构如下:

skiplist编码的有序集合对象使用zset结构作为底层实现, 一个zset结构同时包含一个字典和一个跳表:

1
2
3
4

typedef struct zset {
   zskiplist *zsl;
   dict *dict;
} zset;

zset结构中的zsl跳表按照分值从小到大保存了所有集合元素, 每个跳表节点都保存了一个集合元素, 跳表节点的 object属性 保存了元素的成员, 跳表节点的score属性 保存了元素的分值, 通过跳表可以对有序集合进行范围型操作, eg. zrank, zrange 等就是基于跳表实现的

此外, zset 结构中的dict字典为有序集合创建了一个从成员到分值的映射, 字典中的每个键值对都保存了一个集合元素: 字典的键保存了元素的成员, 字典的值保存了元素的分值, 通过字典, 程序可以使用 O(1) 复杂度查找给的成员的分支, zscore 命令就是根据这一特性实现的

有序集合每个元素的成员都是一个字符串对象, 而每个元素的分值都是一个double类型的浮点数, 注意: 虽然zset结构同时使用跳表和字典来保存有序集合元素, 但两者会通过指针共享相同元素的成员和分值, 所以不会产生重复的成员或者分值、也不存在额外的内存浪费

思考:

为什么有序集合需要同时使用跳跃表和字典来实现 ?

1
2
3
4

理论上, 有序集合可以单独使用字典或者跳表其中一种结构实现, 但无论使用字典还是跳表、都有各自的缺陷. 
eg. 若只使用字典实现, 以O(1)时间复杂度查找成员分值的特性会被保留、但因为字典以无序的方式来保存集合元素, 在执行`zrank`, `zrange` 时、需要对所有元素排序, 至少需要 O(Nlog N)的时间复杂度、及 O(n)的空间复杂度(创建一个数组保存排序后的元素).

若只是有跳表实现, 跳表执行范围查询的操作优点会被保留, 但因为没有字典, 根据成员查找分值的复杂度会从 O(1) 上升到 O(log N), 所以 redis选择了同时使用两种数据结构完成.

若price键创建的有序集合对象使用的是skiplist编码、结构如下:

*注意: *

为展示方便、上图在字典和跳表中重复展示了各个元素的成员和分值、但在实际中、字典和跳跃表会共享元素的成员和分值、不会造成任何内存浪费

编码的转化

有序集合对象同时满足下边条件时、使用ziplist编码

1. 有序集合保存的元素数量＜128个
2. 有序集合保存的所有元素成员长度＜64字节

注意

条件上限值可配置, zset-max-ziplist-entries 和 zset-max-ziplist-value 选项.

有序集合的命令实现

有序集合键的值为hash对象、用于有序集合键的所有命令都是针对hash键来构建的, 下边是部分实现:

对象

前边学习了Redis底层实现的各种数据结构, 包括SDS, list, skiplist, dict, intset, ziplist等, 但redis并未直接使用这些数据结构来构建数据库、而是基于这些数据结构构建了一个对象系统, 这个系统包括 字符串对象, 列表对象, hash对象, 集合对象, 有序集合对象这五种类型的对象.

通过这5种不同的对象、Redis可以在执行命令前, 根据对象的类型来判断一个对象是否可以执行给定的命令, 使用对象的另一个好处是, 可以针对不同的使用场景、为对象设置不同的数据结构的实现、优化对象在不同使用场景下的使用效率.

此外、Redis的对象系统还实现了基于引用计数技术的内存回收机制、当程序不再使用某个对象时、对象占用的内存会被自动释放, 且: Redis 还通过引用计数技术实现了对象共享机制, 可以在适当调节下、让多个数据库键共享同一个对象来节约内存

Redis的对象带有访问时间记录信息, 该信息可以用于计算数据库键的空转时长, 在服务器启用了 maxmemory功能的情况下、空转时长较大的键会被优先删除

对象的类型和编码

Redis使用对象表示数据库中的键和值, 当在redis数据库中创建一个键值对时、至少会创建两个对象: 键对象 和 值对象. eg. Set 命令在数据库中创建一个键值对

1
2

redis> set msg "hello world"
OK

就包含了一个键对象msg的字符串对象 和 一个值对象 hello world

Redis中每个对象由一个redisObject结构表示, 和保存数据有关的3个属性分表是 type属性、encoding属性 和 ptr属性

1
2
3
4
5
6

typedef struct redisObject {
  unsigned type:4; // 类型
  unsigned encoding:4; // 编码
  void *ptr; // 指向底层实现数据结构的指针
  //...
}

类型

对象的type属性记录了对象的类型, 属性值可以是下边任何一个

对于Redis保存的键值对来说、键总是一个字符串对象, 而值则可以是上边任意一种对象, 所以:

1. 当我们称呼一个键为字符串键时, 指的是对应的值是字符串对象
2. 当我们称呼一个键为列表键时, 指的是对应的值是列表对象

type命令的实现方式与此类似, 执行type命令返回的是值对象的类型, 而不是键对象的类型

编码和底层实现

对象的ptr指针指向对象的底层实现数据结构, 而这些数据结构由对象的encoding属性决定,

encoding属性记录了对象使用的编码, 即 对象使用了什么数据结构作为对象的底层实现, 可以是下表的任意一个

Reids每种类型的对象都至少使用了2种不同的编码

使用object encoding命令可以查看一个数据库键的值对象编码

1
2
3
4
5
6
7
8
9
10
11

redis> set msg "hello world"
OK

redis> object encoding msg
"embstr"

redis> set story "long long long ..."
OK

redis> object encoding story
"raw"

通过encoding属性来设定对象使用的编码、而不是为特定类型的对象关联一种固定的编码、极大的提高了redis的灵活性和效率, 允许redis在特定场景下未一个对象设置不同的编码, 优化使用效率.

eg. 在列表包含对象较少时, redis使用压缩列表作为底层实现, 因为:

1. 压缩列表比双端链表节省内存, 且元素数量少时、在内存中连续存储的压缩列表比双端链表可以更快的载入缓存
2. 随元素增多、使用压缩列表保存元素的优势消失时、对象会将底层实现从压缩列表转向功能更强、也适合保存大量元素的双端链表上

其它类型的对象也会使用不同类型的编码进行类似的优化

字典又称符号表, 关联数组, 映射, 是一种用于保存键值对的抽象数据结构

Redis构建了自己的字典实现, eg. set msg ‘test’会构建key为msg, value为test的键值对.

除了表示数据库之外, 字典还是hash键的底层实现之一(另外一种是ziplist)

字典实现

hash表

Redis字典所使用的哈希表由 dict.h/dictht 结构定义

1
2
3
4
5
6

typedef struct dictht {
  dictEntry **table; // hash表数组
  unsigned long size; // hash表大小
  unsigned long sizemask; // hash表大小掩码, 用于计算hash索引值, 总是=size-1
  unsigned long used; // 已有节点数量
}dictht;

hash表节点

1
2
3
4
5
6
7
8
9

typedef struct dictEntry {
  void *key; // 键
  union {
    void *val;
    unit64_tu64;
    int64_ts64;
  }v; // 值
  struct dictEntry *next;// 指向下个hash节点、形成链表
}

key属性保存着键值对中的键、而v属性则保存着键值对中的值, 它可以是一个指针, 或者是uint64_t类型的整数, 或者是 int64_t的整数

next属性是指向另一个节点的指针, 这个指针可以将多个hash值相同的键值对连接在一起, 解决键冲突问题

字典

Redis中的字典由 dict.h/dict 结构定义

1
2
3
4
5
6

typedef struct dict {
  dictType *type; // 类型特定函数
  void *privdata; // 私有数据
  dictht ht[2]; // hash表
  in trehashidx; // rehash索引, 当rehash不在进行时、值为-1
} dict;

type属性是一个指向 dictType结构的指针, 每个 dictType结构保存了一簇用于操作特定类型键值对的函数, Redis会为不同类型的字典设置不同类型的特定函数

privdata属性则保存了需要传给那些特定类型函数的可选参数

type和privdata是针对不同类型的键值对, 为创建多态字典设置的

1
2
3
4
5
6
7
8

typedef struct dictType {
  unsigned int (*hashFunction)(const void *key); // 计算hash值的函数
  void *(*keyDup)(void *privdata, const void *key); // 复制键的函数
  void *(valDup)(void *privdata, const void *obj); // 复制值的函数
  int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 对比键的函数
  void (*keyDestructor)(void *privdata, void *key); // 销毁键的函数
  void (*valDestructor)(void *privdata, void *obj); // 销毁值的函数
}dictType;

ht属性是一个包含两个项的数组, 数组中的每个项都是一个dictht哈希表, 一般只使用ht[0], ht[1]只会在对ht[0] 进行rehash时使用.

rehashidx记录当前rehash的进度, 若没有在进行rehash, 则值为 -1

完整的dict结构

hash算法

Redis计算hash值的方式如下:

1
2

hash = dict->type->hashFunction(key); // 使用hash字典设置的hash函数、计算key的hash值
index = hash & dict->ht[x].sizemask; // 根据sizemask和hash值、计算出hash索引

解决键冲突

当有两个或以上数量的键被分配到hash表数组同一个索引上时, 称为键冲突 collision, Redis的hash表使用 链地址法(separate chaining)来解决冲突, 每个hash表节点上有一个next指针, 多个hash表节点使用next指针构成单链表

dictEntry总是将新增节点添加到链表头部(时间复杂度为 O(1)), 因为没有tail指针.

rehash

随着操作的不断进行、hash表维护的键值对会增加或减少, 为了让hash表的负载因子(load factor)维持在一个合理的额范围, 当hash表保存键值对数量太大或太小时, 程序需要对hash表扩容或缩容, 扩容或缩容通过rehash进行, Rehash步骤如下:

1. 为字典的ht[1]hash表分配空间, hash表的空间大小取决于要执行的操作, 及ht[0]当前包含的键值对的数量(即: ht[0].used 属性值), 若为扩容, ht[1] 为第一个大于等于 (ht[0].used*2)d的*2ⁿ; 若为缩容, ht[1] 为第一个大于等于 (ht[0].used) 的 2ⁿ
2. 将ht[0]中的所有键值对rehash到ht[1]上, rehash是指: 重新计算键的hash值和索引值, 然后将键值对放到ht[1]hash表的对应位置
3. 当ht[0]包含的所有键值对迁移到ht[1]之后(ht[0]变为空表), 释放ht[0], 将ht[1]设置为 ht[0], 并在 ht[1]新创建一个空白hash表, 为下一次rehash做准备

1
2
3
4
5

eg. 扩容操作:
ht[0].used = 4, 4*2=8, 恰好是第一个大于等于4的2的n次方, 所以rehash后、ht[1]size为8

缩容操作:
ht[0].used = 4, 4=2², 恰好是第一个大于等于4的2的n次方, rehash后 ht[1].size = 4

hash表的扩展与收缩

满足下述任意条件时, 会自动扩展:

1. server 当前未执行bgsave 或者 bgrewriteaof, 且hash表的负载因子大于等于1

2. server 当前正在执行bgsave 或者 bgrewriteaof, 且 hash表的负载因子大于等于 5

   (持久化时、优先持久化操作)

1

load_factor = ht[0].used / ht[0].size; // 负载因子 = hash表已保存节数量 / hash表大小

若bgsave或者bgrewriteaof执行时, Redis需要创建当前服务器进程的子进程, 大多数操作系统使用写时复制(copy-on-write)优化子进程使用效率, 所以子进程存在期间, Server会提高rehash操作的负载因子, 尽可能避免此时rehash, 避免不必要的内存写入操作, 最大限度的节省内存.

另外:

hash表的负载因子小于0.1时, 程序会自动缩容

渐进式rehash

其实, hash表的rehash操作、不是一次集中完成的, 而是多次迭代进行的. 因为若 ht[0]里保存的key有百万计, 甚至更多, 一次rehash导ht[1], 庞大的计算量可能会导致Server一段时间的停止服务.

渐进式rehash步骤如下:

1. 为ht[1]分配空间, 让字典同时持有ht[0] 和 ht[1]两个hash表
2. 在字典中维护一个索引计数器变量 rehashidx, 设置为0, 表示rehash已经开始
3. 在rehash期间, 每次对字典add, del, find or update操作, 程序除了执行指定操作外, 还会顺带将 ht[0] hash表在 rehashidx索引上的所有键值对 rehash 到 ht[1], rehash完成、将rehashidx++.
4. 随字典操作的不断执行、某个时间点, ht[0]的所有键值对rehash到ht[1], rehash完成、将 rehashidx设为 -1.

渐进式rehash过程中会维护 ht[0] 和 ht[1] 两个hash表, 字典的删除、查找、更新等操作都会在两个hash表上进行, eg. 查找: 会先在 ht[0] 上查找、若未找到则 到 ht[1] 上查找

但: 插入操作只会在 ht[1] 上操作

1

ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];

字典API

dict总结

• 广泛用于实现Redis的各种功能, 包括数据库和hash键
• 作为hash表的底层实现, 每个字典有两个hash表、一个平时使用, 一个 rehash 时使用
• 使用 Murmurhash2 计算key的hash值
• 使用链地址法解决键冲突、同一个索引上的多个键值对连接成一个单链表
• rehash是渐进式完成、非一次性工作

链表提供了高效的节点重排能力, 及顺序性节点访问方式, Redis构建了自己的链表实现

链表和链表节点的实现

1
2
3
4
5

typedef struct listNode{
  struct listNode *prev; // 前置节点
  struct listNode *next; // 后置节点
  void *value; // 节点值
}listNode;

多个listNode节点通过 prev 和 next指针组成双端链表, 虽然仅使用多个listNode就可以组成链表, 使用 adlist.h/list 来持有链表会更方便操作.

1
2
3
4
5
6
7
8

typedef struct list{
  listNode *head; // 表头节点
  listNode *tail; // 表尾结点
  unsigned long len; // 链表包含的节点数量
  void *(*dup)(void *ptr); // 节点值复制函数
  void (*free)(void *ptr); // 节点值释放函数
  int (*match)(void *ptr, void *key); 节点值对比函数
} list;

list结构为链表提供了表头指针head、表尾指针tail, 及链表长度计数器len, 而udp, free, match成员则用于实现多态链表所需特定函数.

Redis 链表实现特性总结

• 双端: 有prev和next指针, 获取前置和后置节点的复杂度都是O(1)
• 无环: 表头的prev和表尾的next都指向NULL, 对链表的访问以NULL为终点
• 带表头和表尾指针: 通过list结构的head和tail指针获取链表的头结点和尾结点复杂度为 O(1)
• 带长度计数器: 程序使用list结构的len属性对list节点计数, 获取节点数量的复杂度O(1)
• 多态: 链表节点使用 void *指针保存节点值, 可通过list结构的dup, free, match三个属性为节点值设置类型特定的函数, 所以链表可用来保存不同类型的节点值

SDS 定义

每个sds.h/sdshdr 结构表示一个SDS值

1
2
3
4
5

struct sdshdr {
  int len; // 记录buf数组中已使用字节的数量 (=SDS所保存字符串的长度)
  int free; // 记录buf数组中未使用的字节的数量
  char buf[]; // 字节数组, 保存字符串  
}

• free属性值为0, 表示 SDS 未分配 未使用空间
• len 属性为5, 表示 SDS 保存了一个5字节长的字符串
• buf 属性是一个char类型的数组, 数组的前5个字节保存了 R, e,d,i, s, 五个字符, 最后一个字节保存了空字符串\0

为什么不使用C原生字符串呢 ?

1. C字符串获取长度需要遍历, SDS则记录了自身长度(len), 将获取字符串长度的时间复杂度从O(N)降低到了O(1), 即使反复执行strlen, 也不会对系统造成任何影响
2. C字符串不记录自身长度, 容易造成缓冲区溢出, eg. strcat可以将字符串拼接, 执行这一操作时, 系统假定用户已分配了足够长度的内存, 假设不成立时, 就会造成缓冲区溢出(覆盖后边的字符)
3. C的实现是一个N+1字符长的数组, 每次增长或缩短一个C字符串, 都会重新分配内存
   • 若增长, eg. append、需要先扩容, 否则会产生内存溢出
   • 若缩容, eg. trim、需要先缩容, 否则会造成内存泄露
4. 为避免C字符串的缺陷, SDS通过未使用空间分配, 实现了空间预分配和惰性空间释放来优化.
   • 空间预分配: 当字符串扩展时, 不仅分配必须空间, 还会分配额外空间(len<1M时, free=len, len>=1M时, free=1M), 来减少连续执行字符串增长需要的内存分配次数, 将字符串连续增长N次需要的内存重分配次数从必定N次, 降低到最多N次
   • 惰性释放: 用free来标记被释放的空间, 而不真正操作内存, 也提供了API, 在需要时释放free空间, 不必担心惰性释放造成的空间浪费
5. C字符串用\0标记字符串结尾, 字符串本身不能包含空字符, 使得C字符串只能保存文本数据, 而不能保存图片、音频、视频、压缩文件等二进制数据. 而redis SDS字符靠len属性来判断字符串结尾, 是二进制安全的.
6. 兼容部分C字符. SDS总在结尾多分配一个字符\0 是为了保证C函数可以正常使用, 避免不必要的代码重复

总结

很感谢在某一个时间点恰好遇到了极课时间、让自己的迷茫稍减~
en. 如果你想试试看、可以挑自己感兴趣的课程扫描购买

加我微信 njyishi、可立即返现哦

Note. 如果有你需要的课程、下方二维码没有的、可联系我

专栏课程

深入理解计算机组成原理 返现24

数据结构与算法之美 返现24

设计模式之美 返现36

摄影入门 返现24

RPC实战与核心原理 返现24

趣谈linux操作系统 返现24

透视http协议 返现24

程序员的数学基础课 返现24

编译原理之美 返现24

从0开始学架构 返现24

Java并发编程实战 返现24

Java核心面试技术精讲 返现24

Java性能调优实战 返现24

分布式原理与算法解析 返现24

面试现场 返现18

深入拆解Tomcat&Jetty 返现24

图解google V8 返现18

MySQL实战45讲 返现24

分布式协议与算法实战 返现18

网络编程之实战 返现24

高并发系统设计40问 返现24

技术领导力实战 返现36

深入理解Kubernetes 返现24

消息队列高手课 返现24

即时消息技术剖析与实战 返现18

kafka核心技术与实战 返现24

Java业务开发常见错误100例 返现24

SRE实战手册 返现9.9

接口测试入门课 返现9.9

10X程序员工作法 返现24

程序员的法律课 返现24

说透敏捷 返现9.9

视频课程

Netty源码剖析与实战 返现24

MongoDB高手课 返现24

Zookeeper实战与源码分析 返现24

小马哥讲springboot核心思想 返现36

算法面试通关40讲 返现24

Elasticsearch核心技术与实战 返现24

零基础学Python 返现24

工作机制

基础说明

1
2

iptables并不是真正的防火墙、它只是位于用户空间的一个命令行工具, netfilter 才是真正的安全框架、iptables只是将我们定义的规则转交给netfilter. 
netfilter 是Linux操作系统核心层的一个数据包处理模块

规则链名称

规则链名称包括以下5个、也被称为5个钩子函数:

INPUT链: 处理输入数据包

OUTPUT链: 处理输出数据包

FORWARD链: 处理转发数据

PREROUTING链: 用于目的地址转换(DNAT)

POSTROUTING链: 用于源地址转换(SNAT)

报文流向

1
2
3
4

本机到某进程: prerouting -> input
本机转发: prerouting -> forward -> postrouting (直接在内核空间转发)
本机进程发出(通常为响应报文): output -> postrouting
即: 当启用你过来防火墙功能时、报文需要经过不同的关卡(链)、但根据情况的不同、会经过不同的链

为什么称为链

1

防火墙的作用就在于对经过的报文进行规则匹配、然后执行对应的动作、但是每个关卡上可能有很多规则、这些规则按照配置顺序从上到下执行、看起来就像是一个链

表

1
2
3
4
5
6
7
8
9

这么多的链都放了一系列的规则、但是有些很类似、比如A类规则是对ip或者短裤过滤; B类规则是修改报文... , 那么这些类似功能的规则能不能放在一起呢 ?
答案是可以的、iptables提供了如下规则的分类(表):
filter表: 负责过滤功能 , 防火墙; 内核模块 iptable_filter
nat表: 网络地址转换; 内核模块: iptable_nat
mangle表: 解析报文、修改报文、并重新封装 内核模块: iptable_mangle
raw表: 关闭nat表上启用的连接追踪机制; 内核模块: iptable_raw

当这些表处于同一条链时优先级如下:
raw -> mangle -> nat -> filter

防火墙的策略

通: 默认不允许、需要定义谁可以进入

堵: 默认允许、但需要证明自己的身份

filter功能: 定义允许或者不允许的策略, 工作在 input / output / forward 链

nat选项: 定义地址转换功能, 工作在 prerouting / output / postrouting 链

为了让这些功能都工作、制定了表的定义, 来区分不同的工作功能和处理方式

常用功能

filter 定义允许或者不允许、工作在 input, output, forward 链上

nat 定义地址转换, 工作在 prerouting, output, postrouting 链上

mangle 修改报文原数据, 5个链都可以工作

注意: 设置多个规则链时、要把规则严格的放在前边、因为它是从上到下检查的~

规则动作

accept: 接收数据包

drop: 丢弃数据包

redirect: 重定向、映射、透明代理

snat: 源地址转换

dnat: 目标地址转换

masquerade: ip伪装(nat), 用于ADSL

log: 日志记录

思考:

其实iptables就是帮我们实现了网络包选择、地址转换、报文修改这些功能、为了实现这些功能、它划分了很多链、包括 prerouting、input、forward、output、postrouting, 定义了规则动作 accept、drop、redirect、snat、dnat、log、masquerade来实现这些功能.

实例

清空当前所有规则和计数

1
2
3

iptables -F # 清空所有防火墙规则
iptables -X # 删除用户自定义的空链
iptables -Z # 清空计数

配置允许ssh端口连接

1
2

iptables -A INPUT -s 192.168.1.0/24 -p tcp --dport 22 -j ACCEPT
# 22: ssh端口 -s 192.168.1.0/24 被允许的网段、 -j accept 接受这种类型的请求

允许本地回环地址可以正常使用

1
2

iptables -A INPUT -i lo -j accept
iptables -A INPUT -o lo -j accept

设置默认规则

1
2
3

iptables -P INPUT DROP # 配置默认的不让进
iptables -P FORWARD DROP # 默认的不允许转发
iptables -P OUTPUT ACCEPT # 默认的可以出去

配置白名单

1
2
3
4

iptables -A INPUT -p all -s 192.168.1.0/24 -j ACCEPT  # 允许机房内网机器可以访问
iptables -A INPUT -p all -s 192.168.140.0/24 -j ACCEPT  # 允许机房内网机器可以访问
iptables -A INPUT -p tcp -s 183.121.3.7 --dport 3380 -j ACCEPT 
# 允许183.121.3.7访问本机的3380端口

开启相应的服务端口

1
2
3

iptables -A INPUT -p tcp --dport 80 -j ACCEPT # 开启80端口，因为web对外都是这个端口
iptables -A INPUT -p icmp --icmp-type 8 -j ACCEPT # 允许被ping
iptables -A INPUT -m state --state ESTABLISHED,RELATED -j ACCEPT # 已经建立的连接得让它进来

保存规则到配置文件

1
2
3

cp /etc/sysconfig/iptables /etc/sysconfig/iptables.bak # 任何改动之前先备份，请保持这一优秀的习惯
iptables-save > /etc/sysconfig/iptables
cat /etc/sysconfig/iptables

列出已设置规则

1
2
3
4
5
6
7
8

iptables -L [-t 表名] [链名]

iptables -L -t nat                  # 列出 nat 上面的所有规则
#            ^ -t 参数指定，必须是 raw， nat，filter，mangle 中的一个
iptables -L -t nat  --line-numbers  # 规则带编号
iptables -L INPUT

iptables -L -nv  # 查看，这个列表看起来更详细

端口映射

1
2

iptables -t nat -A PREROUTING -d 210.14.67.127 -p tcp --dport 2222  -j DNAT --to-dest 192.168.188.115:22
# 将本机的 2222端口 映射到虚拟机的 22端口

防止SYN洪水攻击

1

iptables -A INPUT -p tcp --syn -m limit --limit 5/second -j ACCEPT

写在最后

iptables –help 可以看到更多的选项、可以看到每一个选项的解释、本文列出了一些简单使用、欢迎指正、交流~

背景

以 Colud Foundry 为代表的开源PaaS项目、在2013年已经度过了最艰难的概念普及和用户教育阶段、吸引了包括京东、华为、百度、IBM等一大批国内外技术厂商, 开启了以开源PaaS为核心构建平台服务能力的变革、而此时 Docker 项目却意外的出现了. Dot Cloud 公司开源了Docker项目.

PaaS平台被接纳的主要原因是提供了 应用托管能力, Cloud Foundry 最核心的组件是应用的打包和分发机制. cf push 基本上等同于将应用的可执行文件和启动脚本打进一个压缩包内, 上传到cf的存储中. 接着, 会通过调度器选择一个可运行该应用的虚拟机、通知虚拟机上的agent把应用压缩包下载启动.

若需要启动很多个来自不同用户的应用呢 ?

cf 会调用操作系统的 Cgroups 和 Namespace 机制来为每一个应用单独创建一个称为 沙盒的隔离环境、分别在隔离环境中运行.

Docker 实际上跟Cloud Foundry 基本类似、大部分功能和实现原理都一样. 然而、正是这一点点差异 造就了Docker, 它在几个月内快速崛起.

Docker image 就是这一点点的差异. PaaS之所以能帮助大规模用户部署应用到集群里、是因为提供了打包的功能、偏偏也就是打包这个功能、却成了一个软肋. 因为一旦用上PaaS、就必须为每种语言、每种框架甚至每个版本都得维护一个包, 比较麻烦的是本地运行很好的项目、需要修改很多东西和配置才能在PaaS里运行. 为了 cf push 这个一键部署的工作、打包这个前置工作特别麻烦

Docker image 从根本上解决了这个问题. 所谓 Docker 镜像, 其实就是一个压缩包. 大多数Docker 镜像包含一个完整的操作系统和所有文件、目录, 这个压缩包的环境、与本地完全一致. 那么、如果本地环境是 CentOS 7.2, 使用CentOS 7.2 的ISO做一个压缩包、再把应用可执行文件也压缩进去, 就可以得到一个与本地完全一致的环境了. 它包含了应用运行的所有依赖.

这就是 Docker 镜像的精髓.

docker build "image name" 就可以制作成一个压缩包.

docker run "image name" 就是用Docker创建一个沙盒来解压镜像、然后在其中运行应用.

docker run 创建的沙盒, 也是使用 Cgroups 和 namespace创建的隔离环境.

Docker崛起

Docker解决了应用打包和发布的问题, 且将一个存后端的技术概念通过友好的设计和封装、交给了广大的开发者. 得以迅速受到青睐. 一个以容器为中心的全新云计算市场、即将呼之欲出, 此时 dotCloud 公司、却突然改名 Docker, 意味着, 任何公司都不能在商业活动中再使用这个词及鲸鱼的logo. 14年, 又发布了 Swarm 项目. 兜兜转转, Docker 公司还是回到了如何让开发者把应用部署到我的项目这个主题上.

此时, PaaS 已经变成了一套以 Docker 容器为技术核心、以Docker镜像为打包标准的、全新的容器化思路.

这、正是 Docker 项目从开始悉心运作容器化概念和努力经营 Docker 生态系统的目的. 而 Swarm 项目、正是承载Docker接下来所有这些努力的关键.

综合来说、Docker的崛起有3个因素:

1. Docker镜像通过技术手段解决了 PaaS平台的根本性问题.
2. Docker 容器和开发者之间与生俱来的密切关系
3. PaaS概念已深入人心的完美契机.

群雄并起

自增值保存在哪儿

实际上表的结构定义保存在 .frm 文件里、但是不会保存自增值、自增值的保存跟具体引擎有关:
MySIAM 引擎保存在数据文件中.
Innodb的自增保存在内存, 8.0版本之后、提供持久化.
8.0 之前的版本只保存在内存中、每次重启、第一次打开表的时候、会找自增值的最大值 max(id), 将 max(id) + 1, 作为当前表的自增值.
8.0将自增值的变更记录在了redo log中、重启时依靠redo log恢复重启之前的值.

自增值修改机制

MySQL、若字段id被定义为 auto_increment, 在插入一行数据的时候、自增值的行为如下:

1. 若插入数据时id字段指定为0、null或者未指定值、那么就把这个表当前 auto_increment值填到自增字段.
2. 若插入数据时、id字段指定了具体值 、直接使用语句指定值.
   若待插入值是 X、当前自增是 Y
   1) X<Y, 自增保持不变
   2) 若X>=Y, 将自增修改为新的值
   从auto_increment_offset 开始、以 auto_increment_increment为步长、持续叠加、直到找到第一个大于X的值、作为新的自增值

自增值的修改时机

若表t已有记录(1,1,1)、再执行

1

insert into t values(null, 1, 1);

语句执行流程是:

1. 调用innodb引擎接口、写入一行、传入值(0, 1, 1);
2. innodb发现用户没有指定自增id值、获取表t当前的自增值为2;
3. 将传入行的值改为 (2,1,1);
4. 将表的自增改为3
5. 继续执行插入、由于已经存在c=1的记录、出现唯一键冲突、报错返回.
   所以、主键自增修改是在真正的插入操作之前、真正执行的时候唯一键冲突、id=2插入失败、但自增值不会回退. 这之后的数据插入自增基础就是3、所以, 唯一键冲突是导致自增id不连续的第一种原因.

事务回滚也会产生类似的现象、这是第二种原因.

那么为什么MySQL不设计自增值可以回滚呢 ?

假设有两个并行事务、在申请自增值的时候、为了避免两个事务申请到相同的自增id、就需要加锁、顺序申请.

1. 假设事务A申请到id=2、事务B申请到id=3, 此时表t的自增值是4, 之后继续执行
2. 事务B正确提交、事务A出现唯一键冲突.
3. 若允许事务A将自增值回退、则出现、表里已有id=3的行、而当前自增是2 的现象
4. 接下来其它语句申请到 id=2、然后再申请到id=3、就会出现主键冲突.
   解决这个冲突有两个办法:
5. 每次申请id之前、先判断表里是否已存在这个id、若存在、就跳过、但成本较高、本来申请id是一个很快的操作、现在还要去主键索引上判断id是否存在
6. 把自增id的锁范围扩大、必须等上一个事务执行完成、下一个才能申请. 但会大大的影响并发性能.
   所以、MySQL放弃了自增值回退、只保证自增、不保证连续.

自增锁优化

自增锁并不是事务锁、每次申请完就释放、以便别的事务再申请. 一起看下自增锁演进的过程:

5.0版本、自增锁是语句级别、若一个语句申请了一个表自增锁、锁会等语句结束才释放. 影响并发度.
5.1.22新增参数 innodb_autoinc_lock_mode, 默认1
设为0: 表示采用5.0版本策略、语句执行结束释放锁
设为1: 普通insert、自增锁申请之后、立即释放; 类似insert…select批量插入语句、要等语句结束才释放
设为2: 所有语句都是申请后就释放.

批量插入语句、预先不知道要申请多少个自增id、一种直接想法是: 需要是就申请一个. 但若需要10w个自增的话、就需要申请10w次、会速度很慢、且影响并发插入性能.所以、批量申请的话、Mysql会使用指数级分配.

这是自增出现不连续的第三个原因.