0%

前几天一个小伙伴在公司 slack 问到如下 Golang 代码为什么会卡死(Go Playground):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package main

import (
"fmt"
"runtime"
)

func main() {
var i byte
go func() {
for i = 0; i <= 255; i++ {
}
}()
fmt.Println("Dropping mic")
// Yield execution to force executing other goroutines
runtime.Gosched()
runtime.GC()
fmt.Println("Done")
}

这个问题很有意思,大概涉及到 Golang 中以下三个概念:

  1. byte 是什么
  2. goroutine 如何调度
  3. Golang GC 时会发生什么

本文尝试简单解释下为什么上面的程序会卡死。

首先,先看下 main 函数里启动的 goroutine 事实上是什么东西:

1
2
3
4
5
var i byte
go func() {
for i = 0; i <= 255; i++ {
}
}()

Golang 中,byte 其实被 alias 到 uint8 上了。所以上面的 for 循环会始终成立,因为 i++ 到 i=255 的时候会溢出,i <= 255 一定成立。也即是, for 循环永远无法退出,所以上面的代码其实可以等价于这样:

1
2
3
go func() {
for {}
}

其次,Goroutine 的调度是一个非常复杂的问题,这里并不打算详细介绍完整细节。
大概描述一下,目前版本的 Golang 中 goroutine 的调度(Scalable Go Scheduler Design Doc)基于 GPM 模型,G 代表 goroutine,M 可以看做真实的资源(OS Threads)。P 是 G-M 的中间层,组织多个 goroutine 跑在同一个 OS Thread 上。大概的模型如下(图偷自 Google 图片搜索):

image

如上图可以看到,一个 P 上会挂着多个 G,当一个 G 执行结束时,P 会选择下一个 G 继续执行。而当一个 G 执行太久没有结束,总也要给后面的 G 运行的机会吧。所以,Go scheduler 除了在一个 goroutine 执行结束时会调度后面的 goroutine 执行,还会在正在被执行的 goroutine 发生以下情况时让出当前 goroutine 的执行权,并调度后面的 goroutine 执行:

  • IO 操作
  • Channel 阻塞
  • system call
  • 运行较长时间

前三种这里我们不关心,最后一种情况下,如果一个 goroutine 执行时间太长,scheduler 会在其 G 对象上打上一个标志( preempt),当这个 goroutine 内部发生函数调用的时候,会先主动检查这个标志,如果为 true 则会让出执行权。(这里说得比较粗略,实际会复杂一些,不过并不是本文重点所以暂不关注细节。)

回到本文开始时的例子,main 函数里启动的 goroutine 其实是一个没有 IO 阻塞、没有 Channel 阻塞、没有 system call、没有函数调用的死循环。也就是,它无法主动让出自己的执行权,即使已经执行很长时间,scheduler 已经标志了 preempt。

如上图所示,一旦这个 G ( goroutine ) 拿到执行权,它后面的 G 将无法再被当前 P 调度获得执行权。上面程序为了让这个 G 对象一定拿到执行权,在 main goroutine 中主动执行 runtime.Gosched() 让出了执行权。

P 的数量由 GOMAXPROCS 设置,默认为机器的 CPU 数量。

这里又分为两种情况:

  1. 当这个程序跑在单核机器上的时候,P 默认只有一个,所以一旦调度到这个 G 对象就会卡死,因为永远没有机会再调度回 main goroutine 了。
  2. 当这个程序跑在多核机器上的时候,程序到这一步并不会卡死,因为另一个 P 所关联的 G 队列执行完了之后,会通过 Work-Stealing 算法偷取别的 P 对象上的 G,所以 main goroutine 还是有机会被别的 P 调度到。

可是文章开始时的代码,不论是在单核的机器上,还是在多核的机器上,都会卡死。

这就涉及到第三个点了:Golang 的 GC。

Golang 的 GC 本质上是基于标记-清除实现的(基于此不断改进过)。
见名知意,标记-清除分为两个阶段:

  • 标记
  • 清除

其中,标记阶段是需要 STW( Stop The World )的,也就是会让所有正在运行的 goroutine 停下来。大概源码在这个位置

1
2
3
4
5
6
7
8
func gcStart(mode gcMode, trigger gcTrigger) {

// ......
systemstack(stopTheWorldWithSema)
// ......

}

到这一步,死循环这个 goroutine 由于上面介绍的原因永远无法停下来,但是 main goroutine 阻塞在 GC STW 这里,等待所有 goroutine 停止执行。main goroutine 在等待一个永远不会为它停下的 G,于是,程序卡死了。

类似的,在设置 GOMAXPROCS 的时候,也需要 STW,所以下面的代码,和本文开始时的代码,卡死的原因是一样一样的(Go Playground):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main

import (
"fmt"
"runtime"
"time"
)

func forever() {
for {
}
}

func main() {
go forever()

time.Sleep(time.Millisecond) // 让出执行权
runtime.GOMAXPROCS(1926) // 等待 stw
fmt.Println("Done") // 永远执行不到
}

区区几行代码,里面的奥妙真不少呀。

经验较少的程序员在设计数据表的时候,经常会听到 DBA 老鸟建议在表上使用递增的主键 ID,而不是使用 UUID 等方式产生 ID。大体的措辞都是 InnoDB 使用自增的主键更快云云,本文尝试阐述为什么需要这样做。

聚簇索引

在 InnoDB 中,每个表都会有一个聚簇索引,在定义了主键( primary key )的情况下,主键所在的列会被作为聚簇索引存储。所谓聚簇索引,意思是数据实际上是存储在索引的叶子节点上,「聚簇」的含义就是数据行和相邻的数据紧凑地存储在一起。因为不能(或者不值得)同时把数据行存储在两个不同的位置,所以一个表只能有一个聚簇索引。

关于 InnoDB 选择哪个列作为聚簇索引存储,大概的优先级为:

  1. 如果定义了主键( primary key ),则使用主键;
  2. 如果没有定义主键,则选择第一个不包含 NULL( NOT NULL )的 UNIQUE KEY;
  3. 如果也没有,则会隐式定义一个主键作为聚簇索引。

下图展示了聚簇索引中记录(数据)是如何存放的:

image

如上图所示,聚簇索引中,不但存储了索引,还存储了整张表的数据到叶子节点上。可以认为 InnoDB 中,聚簇索引「就是」表。对应的,InnoDB 的其它索引中,叶子节点所存储的,其实是主键的值。存储主键的值而不是数据行的位置,这样的存储方式可以减少当出现数据行移动或者数据页分裂时二级索引的维护工作。

聚簇与非聚簇表的数据存储方式

我们假设有如下数据表:

image

我们假设列 col1 是 primary key,那么,对应的聚簇索引存储结构就会如下:

image

(暂时不必关心 TID 和 RP,它们是事务 ID 和回滚指针)如上所示,聚簇索引除了存储 col1 的值之外,还会存储其它列的值(本例的 col2)。
如果 col2 设置了普通索引,对应地,col2 的索引存储结构如下:

image

可以看到,对应 B+ 树叶子节点上存储了对应行的主键的值。

抽象来看,InnoDB 通过如下结构存储主键索引(聚簇索引):

image

InnoDB 通过如下结构存储二级索引:

image

作为参考,MyISAM(另一个 MySQL 存储引擎)是这样存储主键索引和二级索引的:

image

InnoDB 表中按主键顺序插入

一般来讲,使用一个业务无关的自增( AUTO_INCREMENT )ID,可以保证数据在插入时会被按顺序写入。假设我们使用 UUID 作为聚簇索引,在插入数据的时候,聚簇索引所被插入的位置将变得完全随机。大量的随机插入会导致页分裂和碎片非常多。

下图展示了数据插入有序递增时,聚簇索引会如何存储插入的数据行:
image

可以看到,因为主键是有序的,InnoDB 把每一条记录都存储在上一条记录的后面。当当前页即将写满时(之所以是即将而不是已经,是因为 InnoDB 会预留一点空间用于以后修改数据,默认预留页的 1/16 大小),下一条记录被插入时,将会写入到新的页中去。所有被插入的数据,都将有序地放到聚簇索引最后的位置上去。

对应地,如果使用 UUID 作为主键索引,InnoDB 将完全随机地将数据插入到聚簇索引对应的位置上去:

image

如上,因为新插入的行的主键不一定比之前插入的大(由于是 UUID,将会非常随机),所以 InnoDB 将无法简单地总是把新行插入到索引的最后,而是需要根据主键 ID 的值为它寻找合适的索引位置,并为其分配空间。使用 UUID 作为聚簇索引,有以下缺点:

  • 写入的目标页可能已经写入到磁盘而不只是存在于内存中,又或者目标页还没有被加载到内存中,InnoDB 在插入前需要先找到并从磁盘中读取目标页到内存中去,这会产生大量的磁盘随机 IO。
  • 因为写入是乱序的,InnoDB 需要频繁地做页分裂操作,一遍为新的行分配空间。页分裂需要移动大量数据。
  • 有序频繁的页分裂,页会变得稀疏并被不规则地填充,所以最终数据会有碎片。

所以,在使用 InnoDB 时应该尽可能使用单调递增的主键 ID 顺序插入数据。单调递增的主键 ID 并不只有 AUTO INCREMENT 一种方式,比如一些分布式发号器算法,也能产生递增的 ID 序列。

小结

简述了为什么应该使用自增的 ID 而不是 UUID 作为 InnoDB 表的主键 ID。

注:本文截图摘自《高性能 MySQL》

字典(dict)是 Redis 实现中非常常用的数据结构,比如用来作为 set 和 hash 的底层实现之一,dict 也是 Redis 数据库中 redisDb 用来存储所有数据的基本格式。

dict 的实现

dictht(hash table) & dictEntry

Redis 中 dict 结构其实封装了 hash table( Redis 中叫做 dictht ),如下是 Redis4.0 中,dictht 的定义

1
2
3
4
5
6
typedef struct dictht {
dictEntry **table; // hash table 实际存储的位置
unsigned long size; // table 的大小
unsigned long sizemask;
unsigned long used; // 已经使用的长度
} dictht;

如上,table 属性指向一个 dictEntry 指针数组的开始位置,(其实就是 dictEntry 指针数组)用来存储每一组键值对。size 则记录 table 的长度,used 用来记录已经存储的节点数量。

如下是 dictEntry 的定义

1
2
3
4
5
6
7
8
9
10
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;

如上,key 则是一个键值对的键,v 是对应的值。每个 dictEntry 除了存储键值之外,还有一个 next 指针,用来指向 hash 相同时的下一个节点,以解决 hash 冲突问题。

如下图,假如 k1/k2 对应的 hash 相同,则会通过 next 指针连接起来:

1
2
3
4
5
6
7
8
9
10
11
12
13
+----------+
| dictht |
+----------+ +----------+
| table +--->| dictEntry|
| | +----------+
| size | | 0 +->NULL +---------+ +---------+
| | +----------+ | entry | next | entry | next
| sizemask| | 1 +------->+---------+----->+---------+----->NULL
| | +----------+ | k1 | v1 | | k2 | v2 |
| used | | 2 +->NULL +---------+ +---------+
+----------+ +----------+
| 3 +->NULL
+----------+

dict

Redis4.0 中 dict 的定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct dictType {
// 计算哈希值
uint64_t (*hashFunction)(const void *key);
// 复制 key
void *(*keyDup)(void *privdata, const void *key);
// 复制 value
void *(*valDup)(void *privdata, const void *obj);
// 比较 key
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 销毁 key
void (*keyDestructor)(void *privdata, void *key);
// 销毁 value
void (*valDestructor)(void *privdata, void *obj);
} dictType;


typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;

先看一下 dictType,由于 dictEntry 中的 key 是 void*,v 也可以是 void*,所以需要某种方式来操作具体的键和值。dictType 就定义了一组函数指针,dict 对象的 type 指针关联本 dict 对应的 key-value pair 实现的 dictType,以实现具体类型的计算哈希、复制键值、比较和销毁键值等操作。dict 通过这样的方式实现了多态。

dict 结构体中,prevdata 保存了需要传给 dictType 里的函数的特定参数(dictType 中各个函数签名中的 prevdata 指针)。

ht 是包含两个 dictht 对象的数组,ht[0] 存储数据,ht[1] 在 rehash 的时候会用到,下面就会提到。

rehashidx 记录 rehash 进度,本文后面会详细介绍。

在没有发生 rehash 的时候,ht[1] 是一个空的 dictht。

hash 冲突

所谓 hash table,本质是将 hash(key) 映射到自己的 table 数组中去。
对于一个 dict 对象,一个 dictEntry 经过下面的计算即可知道需要被映射到哪个位置:

1
2
hash = dict->type->hashFunction(dictEntry->key);
position = hash & dict->ht[0].sizemask;

想象这样的情况,如果两个 key 的哈希值相同,或者哈希值 & sizemask 相同,即两个不同的 key 被映射到 dictht.table 的同一个位置,也就是发生了 hash 冲突。

如上 dictEntry 结构中的 next 指针,Redis 通过这个指针将 hash 冲突的 dictEntry 连接到一起,以解决冲突。

由于 dictEntry 只有 next 指针,所以处于性能考虑,当 dictht 遇到 hash 冲突时,新的节点总是会被添加到这个链表的表头节点,也就是只需要 O(1) 时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
before: 包含 k1-v1 的 dictht:
+----------+
| dictht |
+----------+ +----------+
| table +--->| dictEntry|
| | +----------+
| size | | 0 +->NULL +---------+
| | +----------+ | entry |
| sizemask| | 1 +------->+---------+
| | +----------+ | k1 | v1 |
| used | | 2 +->NULL +---------+
+----------+ +----------+
| 3 +->NULL
+----------+

after: 当 k2 与 k1 的 hash 冲突时,k2 会被插入到链表表头节点:
+----------+
| dictht |
+----------+ +----------+
| table +--->| dictEntry|
| | +----------+
| size | | 0 +->NULL +---------+ +---------+
| | +----------+ | entry | next | entry | next
| sizemask| | 1 +------->+---------+----->+---------+----->NULL
| | +----------+ | k2 | v2 | | k1 | v1 |
| used | | 2 +->NULL +---------+ +---------+
+----------+ +----------+
| 3 +->NULL
+----------+

rehash 过程

当 dictEntry 被不断插入到 dictht 中或不断被删除时,dictht 对象的 table size 对于当前存储元素个数来讲可能太小或者太大。
衡量所谓「太大」和「太小」的标准,叫做负载因子( load factor ),这个值的计算规则为:

1
loadFactor = dictht.used / dictht.size

比如对于上面的例子,负载因子就是 2 / 4 = 0.5。

当:

  1. 服务器执行 BGSAVE/BGREWRITEAOF 命令且负载因子大于 5 时,Redis 会对 dictht 扩容;
  2. 服务器没有执行 BGSAVE/BGREWRITEAOF 命令且负载因子大于 1 时,Redis 会对 dictht 扩容;
  3. 负载因子小于 0.1 时,Redis 会对 dictht 缩容。

当满足这些条件时,将出发 Redis rehash 操作,具体步骤为:

  1. 为 dict->ht[1] 分配空间,具体大小取决于目前是要扩容还是缩容,以及 ht[0].used(当前 dict 大小):
    a. 当扩容时,新的大小为第一个大于 ht[0].used * 2 的 2^n 值;
    b. 当缩容时,新的大小为第一个 ≥ ht[0].used 的 2^n 值。
  2. 将 ht[0].table 中所有的键值对依次 rehash 到 ht[1].table 中去,即依次为每个 dictEntry 计算 key 的 hash,并映射到新的 dictht.table 中。
  3. 当 ht[0].table 所有 dictEntry 全部迁移到 ht[1].table 里之后,释放 ht[0],并将 ht[1] 设置为 ht[0],然后再在 ht[1] 创建空的 dictht。

渐进式 rehash

当 dict rehash 发生时,需要将 ht[0] 中所有 dictEntry 全部 rehash 到 ht[1] 中去。想象一下如果 dict 已经非常大时,这个操作将会非常慢,以至于影响 Redis 对外提供服务的性能。
所以在 Redis rehash 过程的实现中,这个过程并不是停机一次性完成的,而是会分多次进行,渐进式完成的。上面提到的 dict->rehashidx 属性,就是用来记录 rehash 流程的。

这个渐进式 rehash 大概的流程如下:

  1. 为 dict->ht[1] 分配合适的空间,dict 此时同时持有 ht[0] 和 ht[1];
  2. 将 dict->rehashidx 设置为 0,代表 rehash 工作开始;
  3. 当 rehash 期间,对 dict 执行的增、删、改、查操作时,Redis 除了执行操作外,还会将 dict->ht[0].table[dict->rehashidx] 上的 dictEntry rehash 到 dict->ht[1] 中,并将 rehashidx 加一;
  4. 随着 dict rehash 不断进行,最终,dict->ht[0] 上的所有元素都被 rehash 至 dict->ht[1] 中,rehash 过程完成,将 rehashidx 置为 -1;
  5. 释放 ht[0],并将 ht[1] 设置为 ht[0],然后再在 ht[1] 创建空的 dictht。

在 rehash 过程中,如果有新的元素插入,则会直接被插入到 dict->ht[1] 中去,ht[0] 将不会再插入数据。
而这个过程中,dict->ht[0]、ht[1] 都有部分数据,因此在 rehash 进行时,dict 的查找、删除、更新都会在两个 dictht 对象上执行。比如删除一个 key,如果这个 key 在 dict->ht[0] 中不存在,还会再在 dict->ht[1] 中查找并删除(如果存在)。

小结

回顾了一下 Redis 中 dict 的实现,当遇到 hash 冲突时的解决办法,以及 Redis 中 dict 是如何扩容和缩容的。

所有后端开发的同学,一般都会使用到 Redis 作为数据存储或缓存。在我所知的很多互联网公司,Redis 都发挥着难以替代的作用。本文试图简单介绍下,Redis 实现中用到的一些数据结构。


Redis 用户侧支持的数据结构

完整的 Redis 命令参考可以查看 redisdoc.com

string

通过 key-value pair 的方式,存储字符串、整数、浮点数等对象。

1
2
3
+---------+    +---------+
| key +--->| value |
+---------+ +---------+

虽然叫做「 string 」,但其实更像是一个字节序列(底层存储也是一个字节数组),所以其实你可以存储任何东西到 string 中去。比如把 Python pickle 序列化后的对象、一张图片的二进制序列等任何东西存储为 string。
之所以说 string 是字节数组,一部分原因是其提供了直接操作 bit 的指令。
不完全等同于 byte array 的是,string 对象某些场景下可以直接在服务端被解释为一个 int/double 对象,然后直接进行一些数字相关的运算(加、减)。
string 对象是 Redis 中最基础的类型,因为后面几乎所有数据类型存储的值,都是 string 类型。

hash

Hash table,某些地方又被称为 map,概念上有点类似 Python 中的 dict 或 Golang 中的 map 等。其存储的是一系列 key-value 对。

list

List 对象概念上可以理解为 Python 中的 list、Java 中的 List、Golang 中的 slice 等。之所以说概念上,是因为这几者底层实现上其实并不相同,只是都是对一组数据的集合的抽象。

1
2
3
+-------+   +--------+--------+--------+--------+
| key +-->| value1 | value2 | ...... | value n|
+-------+ +--------+--------+--------+--------+

(逻辑上 list 是这样的,实现上下面再讲)
Redis 中 list 对象可以插入数据到 list 头或尾上,由于其底层实现是一个双向链表(某些场景下不是),所以插入两端都是 O(1) 的。

set

Set 对象有点像是 Python 里的 set,其存储的是多个互不相同的元素。由于 set 底层使用 hash table 存储(同上,某些场景下不是),所以其大部分操作都是 O(1) 的。

zset

zset 是有序集合,同 set 相似的是,其内部存储的元素也是不允许重复的。不同的是,set 中存储的元素是无序的,但是 zset 存储的元素是有序的。
通过为 zset 中每个元素设置一个 score,zset 根据元素的 score 排序。

其他(略)

  • HyperLogLog
  • GEO

实现用户侧数据结构的底层结构

Redis 是通过 C 语言实现的,由于 C 语言的朴素,Redis 并没有直接实现上面提到的数据结构,而是通过构件了一系列基础的数据结构,经过对象系统对下层结构的封装,来实现上层面向用户的各种结构。
下面,先介绍下这些底层结构。

SDS

SDS 是「 simple dynamic string 」的缩写,是对 C 字符串的抽象(其实 C 语言没有字符串…… 2333)。
SDS 的定义如下( Redis4.0 sds 定义,相比 3.0 及之前版本,目前版本包含多种格式的 sdshdr 定义):

1
2
3
4
5
6
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};

相比 C char array,sds 有以下优点:

  1. 获取字符串长度效率更优。C 字符串只是一个 ‘\0’ 结尾的 char 数组,如果需要获取字符串长度,需要遍历整个数组,遍历操作时间复杂度为 O(N)。而 sds len 属性记录了本身的长度,获取长度只需要 O(1) 复杂度。
  2. 避免数组长度溢出。类似 strcat(dst, src) 等函数,如果 dst 数组剩下的空间小于 src 的长度,则在字符串连接的时候会导致数组溢出。而在 sds 中,执行字符串拼接等修改操作时,会先通过 len、alloc 属性检查剩下的空间是否足够。当空间不足时,会先分配足够的空间。
  3. 减少内存分配次数。sds 会通过预申请内存,在连接字符串等操作时,减少对内存的申请操作。同时,如果 sds 所保存的字符串变短了,也并不会立即释放内存,而是通过 len 记录已使用,剩余空间作为 buffer 暂时保留。
  4. 二进制安全。因为 C 字符串会以 ‘\0’ 作为结束符,所以如果在 char array 中存储图片等二进制数据时,空字符会被认为是结束符。而 sds 通过 len 属性记录 buf 使用的长度,则可以避免这样的问题。
  5. 兼容部分 C 字符串函数。sds 也会在 buf 已使用的最后一位后(sds->buf[sds->len])插入一个 ‘\0’,这样在 sds 存储文本数据时,可以方便地复用一些 string.h 已有的函数。

linkedlist

Redis 中 linkedlist 是一个双向链表(Redis4.0 linkedlist 定义):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;

typedef struct listIter {
listNode *next;
int direction;
} listIter;

typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned long len;
} list;

每个节点类似这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
+---------+           +----------+        +----------+        +----------+
| list | | listNode | | listNode | | listNode |
+---------+ +----------+ next +----------+ next +----------+ next
| head +-----------> +--------> +--------> +------->NULL
| | | value | | value | | value |
| tail +-+ NULL<--+ <--------+ <--------+ |
| | | prev+----------+ prev +----------+ prev +-^--------+
| len: 3 | | |
| | +---------------------------------------------------+
| dup +----> ...
| |
| free +----> ...
| |
| match +----> ...
+---------+

list 结构通过 head、tail 记录了链表头尾指针,配合每个节点的 next、prev,方便从头或者从尾遍历等操作。
另外,dup/free/match 等函数指针,则是用于实现链表的多态特性:

  1. dup 函数用于复制链表节点保存的值
  2. free 函数用于释放链表节点保存的值
  3. match 函数用于比较节点的值与另一个输入 key 是否相同

dict

dict 类似 Python 中的 dict 或 Golang 中的 map。
在 Redis 中,dict 通过一个 dict 结构实现,底层通过一个 hashtable 存储数据。
tashtable 和 dictEntry 的定义如下(Redis4.0 dict 定义):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;

typedef struct dictht {
dictEntry **table; // hash table 实际存储的位置
unsigned long size; // table 的大小
unsigned long sizemask;
unsigned long used; // 已经使用的长度
} dictht;

其中,dictEntry 是每个 key-value 对存储的结构,其 next 指针用于在 hash 冲突时,将多个 entry 连接一起:

1
2
3
4
5
6
7
8
9
10
11
12
13
+----------+
| dictht |
+----------+ +----------+
| table +--->| dictEntry|
| | +----------+
| size | | 0 +->NULL +---------+ +---------+
| | +----------+ | entry | next | entry | next
| sizemask| | 1 +------->+---------+----->+---------+----->NULL
| | +----------+ | k1 | v1 | | k2 | v2 |
| used | | 2 +->NULL +---------+ +---------+
+----------+ +----------+
| 3 +->NULL
+----------+

dict 的定义如下(Redis4.0 dict 定义):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef struct dictType {
// 计算哈希值
uint64_t (*hashFunction)(const void *key);
// 复制 key
void *(*keyDup)(void *privdata, const void *key);
// 复制 value
void *(*valDup)(void *privdata, const void *obj);
// 比较 key
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 销毁 key
void (*keyDestructor)(void *privdata, void *key);
// 销毁 value
void (*valDestructor)(void *privdata, void *obj);
} dictType;

typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;

其中:

  1. dictType 是一个包含一组针对不同类型 entry 特定操作函数的结构体。不同类型的 entry 通过不一样的实现,来达到多台的目的。
  2. prevdata 保存了需要传给 dictType 里的函数的特定参数(如上函数签名的 prevdata 指针)
  3. ht 是包含两个 dictht 对象的数组,ht[0] 存储数据,ht[1] 在 rehash 的时候会用到(这里只提一下,dict rehash 过程下次单写)
  4. rehashidx 记录 rehash 进度,这里不做过多介绍。

关于 dict 结构的一些细节,下次再详细介绍。

skiplist

skiplist(跳跃表) 是一种有序的结构,通过在每个节点中维护多个指向其他节点的指针来实现快速访问节点的目的。

skiplist 的定义如下(Redis4.0 skiplist 定义):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;

typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 头、尾指针
unsigned long length; // 长度
int level;
} zskiplist;

如上,zskiplistNode 由于保存每个节点的数据和各种指针等,zskiplist 用于保存整个 skiplist 相关信息。

intset

当 set 中只包含整数元素时且元素不多时,底层的数据结构便是 intset。
intset 的定义如下(Redis4.0 intset 定义):

1
2
3
4
5
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;

其中 contents 数组用于存储数据,intset 按照存储数字的大小有序排列在 contents 数组中。length 属性记录集合中元素的个数。
encoding 记录 contents 数组中存储的元素的类型:

  • INTSET_ENC_INT16 存储 int16 类型整数
  • INTSET_ENC_INT32 存储 int32 类型整数
  • INTSET_ENC_INT64 存储 int64 类型整数
1
2
3
4
5
6
7
8
9
10
11
+----------+
| intset |
+----------+
| encoding|
| INTSET_ENC_INT16
| |
| length |
| 5 |
| | +----+---+---+---+------+
| contents+------>+ -4 | 0 | 3 | 6 | 1024 |
+----------+ +----+---+---+---+------+

当新增元素到 intset 中时,如果新元素比现有元素类型长时,比如向 INTSET_ENC_INT16 编码的 intset 插入一个 32 位整数时,intset 需要先升级(upgrade),才能添加元素。所谓 upgrade 是将此 intset 的 enconding 更新为更长 bit 的编码格式上。当 intset 升级后不会降级,哪怕删除长 bit 元素后剩下全是短 bit 元素。

ziplist

ziplist 是 list 和 hash 的一种底层实现。当 list 元素较少且只包含整数或短字符串时,底层会通过 ziplist 存储数据。
ziplist 是为了节约内存而设计的一种结构,本质上就是一个约束了特殊格式的 char array,或者更正确的说法,是字节序列。展开这个字节序列,大致约束的格式是这样:

1
2
3
+---------+--------+-------+--------+-----+--------+-------+ 
| zlbytes | zltail | zllen | entry1 | ... | entryN | zlend |
+---------+--------+-------+--------+-----+--------+-------+

每部分的含义是:

field type sizeof 用途
zlbytes uint32_t 4 记录 ziplist 长度(bytes)
zltail uint32_t 4 记录 ziplist 尾节点距开始的字节数,通过 zltail 可以方便地找到尾节点地址
zllen uint16_t 2 记录 ziplist 节点数量:当超过 2bit 长度时,真正的节点数量需要遍历整个 ziplist 才能得到
entry ziplist 存储的元素 / ziplist 存储的元素,具体长度由具体存储的内容决定
zlend uint8_t 1 值衡为 0xFF,标记 ziplist 结束

对于每个 entry 节点,又可以展开为这样的格式:

1
2
3
+-----------------------+----------+---------+ 
| previous_entry_length | encoding | content |
+-----------------------+----------+---------+

每部分的含义是:

field sizeof 用途
previous_entry_length 1 or 5 前一个元素的长度(bytes),分两种情况:1. 前一个元素小于 254 bytes,则使用一个字节记录;2. 前一个元素长度大于 254 bytes,则这个字段第一字节衡为 0xFE,后面 4 位表示前一个元素长度
encoding 1 or 2 or 5 记录当前元素的数据类型和长度(具体本文暂略)。
content / 保存节点存储的数据

Redis 是如何通过底层结构构件上层数据类型的

上面介绍了用户侧使用的几种常见数据类型,也介绍了 Redis 底层用于支持上层结构而实现的一些结构。下面介绍下 Redis 是如何通过下层的结构构件上层的数据类型的。

redisObject 对象

Redis 不直接实现上层的数据类型,是为了方便在不同场景下可以替换下层合适的数据结构,同时对上层使用屏蔽下层实现细节。在不同场景下,面对性能和内存占用不同而使用不同的下层结构支持同一个上层对象。

redisObject 对象完成了这层转换(Redis4.0 redisObject 定义):

1
2
3
4
5
6
7
8
9
typedef struct redisObject {
unsigned type:4; // 类型
unsigned encoding:4; // 编码
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr; // 指向底层实现数据结构的指针
} robj;

如上结构,type 属性记录了对象的类型,对应上层面向用户的那些数据类型(string/list/hash 等)。对应的类型,可以通过在 redis-cli 中调用 TYPE key 查看每个 key 对应的类型。

而 encoding 则对应着这个 redisObject 下层使用的数据类型(如上 sds/ziplist/dict 等),常见的 encoding 有:

encoding 对应的底层结构
REDIS_ENCODING_INT 整数
REDIS_ENCODING_RAW sds
REDIS_ENCODING_EMBSTR embstr 编码的 sds
REDIS_ENCODING_HT dict
REDIS_ENCODING_LINKEDLIST linkedlist
REDIS_ENCODING_ZIPLIST ziplist
REDIS_ENCODING_INTSET intset
REDIS_ENCODING_SKIPLIST skiplist

对应的下层结构,可以通过在 redis-cli 中调用 OBJECT ENCODING key 查看每个 key 对应的底层实现的数据结构。

string –> int/raw/embstr

string 类型在不同场景下,下层分别由 int/raw/embstr 编码方式来实现( embstr 是经过优化的用于保存短字符串的编码方式)。

  1. 如果 value 是一个整数,且整数长度在 8 bytes 以内,则 string 对象的编码类型为 int,redisObject 的 ptr 指针将指向一个 long 型对象。
  2. 如果 value 是一个字符串值,且长度大于 32 字节,则 string 对象编码类型为 raw,对应 redisObject 的 ptr 指针将指向一个 sds 对象。
  3. 如果 value 是一个字符串值,且长度小于等于 32 字节,则会通过 embstr 编码保存。

当 int 编码的 value 被重新赋值为字符串或通过 incr 等命令自增到超过 64 位长度时,则 Redis 会将其编码方式从 int 转换为 raw。
当 embstr 编码的 value 发生修改时,编码方式会变为 raw 方式,换言之,embstr 是 read only 的。

list –> ziplist/linkedlist

list 的底层实现则分为 ziplist 和 linkedlist 两种。

  1. 当 list 中所有元素长度都小于 list-max-ziplist-value 字节,且元素数量少于 list-max-ziplist-entries 时,底层会选择使用 ziplist。
  2. 否则,使用 linkedlist。

当 ziplist 编码存储的 list 不满足上面 1 的两个条件任意一个时,Redis 就会将对应 value 的编码方式从 ziplist 转换为 linkedlist。

hash –> ziplist/hashtable

hash 的底层实现可以为 ziplist 或者 hashtable 两种格式。

  1. 当 hash 对象所有 key-value pair 长度都小于 hash-max-ziplist-value,且 key-value pair 数量小于 hash-max-ziplist-entries 时,底层会使用 ziplist 保存 hash 对象。
  2. 否则,使用 hashtable。

当使用 ziplist 作为 hash 底层存储结构时,每个 key-value 对会连续地放置在 ziplist 中:

1
2
3
4
5
6
+---------+--------+-------+------+--------+------+--------+-----+------+--------+-------+
| zlbytes | zltail | zllen | key1 | value1 | key2 | value2 | ... | keyN | valueN | zlend |
+---------+--------+-------+--^---+---^----+------+--------+-----+------+--------+-------+
| |
+-------+
key-value 对

同 list,当 hash 对象不满足如上 1 的两个条件任意一个时,编码方式就会从 ziplist 转换为 hashtable。

set –> intset/hashtable

set 的底层实现由 intset 和 hashtable 两种。

  1. 当 set 所有元素都是整数对象,且元素数量小于 set-max-intset-entries 时,使用 intset 作为底层编码方式。
  2. 否则,使用 hashtable。

如下分别是使用 intset 和 hashtable 时,set 对象的存储方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
+---------------+
| redisObject |
+---------------+ +-------------+
| type | | intset |
| REDIS_SET | +-------------+
+---------------+ | encoding |
| encoding | | INTSET_ENC_INT16
| REDIS_ENCODING_INTSET +-------------+
+---------------+ | length |
| ptr +-------->| 3 |
+---------------+ +-------------+ +---+---+---+
| ... | | contents +-->| 1 | 3 | 5 |
+---------------+ +-------------+ +---+---+---+


+---------------+
| redisObject |
+---------------+ +-------------+
| type | | dict |
| REDIS_SET | +-------------+
+---------------+ | StringObject|
| encoding | | "haha" +-->NULL
| REDIS_ENCODING_HT +-------------+
+---------------+ | StringObject|
| ptr +-------->+ "hehe" +-->NULL
+---------------+ +-------------|
| ... | | StringObject|
+---------------+ | "keke" +-->NULL
+-------------+

zset –> ziplist/skiplist

有序集合有 ziplist 和 skiplist 两种方式作为底层的存储结构。

  1. 当 zset 保存的元素小于 zset-max-ziplist-entries 个,且所有元素长度都小于 zset-max-ziplist-value 字节时,zset 底层通过 ziplist 存储。
  2. 否则,使用 skiplist 存储。

同上面其他结构一样,当 1 条件任一不满足时,底层的数据存储结构将转换为第二种。


小结

简单总结了下 Redis 用户端常用的数据结构,以及底层抽象的各种数据结构,以及二者是如何组合起来的。

Redis 面向用户侧的各种数据结构,并不直接实现,而是通过对象系统,在特定的条件下选择特定的底层结构,以在效率和存储空间之间平衡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
     +----------+         +----------+               +----------+         +----------+
| string | | list | | zset | | ... |
+----+-----+ +----+-----+ +----+-----+ +----------+
| | |
/ \ | +-------------------+
/ | \ | | |
/ | \ | | |
+-/ | \----+ +--+---+-------+ +----------------------------+
| | | | | | |
+---v-+ +v----+ +v-------+ +---v---v-+ +--v--------+ +-----------+ +--------+ +-v--------+ +-----+
| int | | raw | | embstr | | ziplist | | linkedlist| | hashtable | | intset | | skiplist | | ... |
+-----+ +-----+ +--------+ +----^----+ +-----------+ +---^-----^-+ +-^------+ +----------+ +-----+
| | | |
| | | |
| | | |
| +----------+ | +-+------+-+
+---+ hash +-----------+ | set |
+----------+ +----------+

记录下通过 Lets’s Encrypt 开启 HTTPS 加成的步骤。这里以 Ubuntu16.04 + nginx 为例。我原本服务器 nginx 就已经配置好对应的域名,这里略过。

首先,安装 certbot :

1
2
3
sudo add-apt-repository ppa:certbot/certbot
sudo apt-get update
sudo apt-get install python-certbot-nginx

开放 443 端口,先检查下防火墙:

1
sudo ufw status

如果防火墙没有打开,是这样的:

1
2
xlzd$ sudo ufw status
Status: inactive

那就什么也不管就好。如果开了,大概输出是这样:

1
2
3
4
5
6
7
Status: active

To Action From
-- ------ ----
OpenSSH ALLOW Anywhere
Nginx HTTP ALLOW Anywhere
OpenSSH (v6) ALLOW Anywhere (v6)

如果防火墙处于打开状态,执行一下:

1
sudo ufw allow 'Nginx Full'

然后就可以生成证书了:

1
sudo certbot --nginx -d fuckthe.app -d www.fuckthe.app

第一次执行的时候,会提示你输入一个邮箱地址。

等执行成功之后,会看到大概这样的输出:

1
2
3
4
5
6
7
8
Please choose whether or not to redirect HTTP traffic to HTTPS, removing HTTP access.
-------------------------------------------------------------------------------
1: No redirect - Make no further changes to the webserver configuration.
2: Redirect - Make all requests redirect to secure HTTPS access. Choose this for
new sites, or if you're confident your site works on HTTPS. You can undo this
change by editing your web server's configuration.
-------------------------------------------------------------------------------
Select the appropriate number [1-2] then [enter] (press 'c' to cancel): 1

选 2 即可,会被自动写入到 nginx 配置中去。

在 crontab 中配置一下自动更新证书:

1
2
30 2 * * 1 /usr/bin/certbot renew --dry-run >> /var/log/le-renew.log
35 2 * * 1 /usr/bin/nginx -s reload

下次再要加新域名的时候,只需继续执行 sudo certbot --nginx -d domain.com 就可以啦~

Done.

名字取得有点标题党了,就在刚刚,闲的无聊,通过微博接口和 Pushbullet 接口做了一个近实时关注别人的小工具。
具体原理比较简单,就是不断轮询微博接口,发现有新的微博的时候,通过 Pushbullet 的接口推送消息到手机和电脑。

Pushbullet 是一个跨平台的消息推送工具,可以很方便将消息在各端间传递,同时也提供了 API 接口供通过程序调用。PYPI 上有一个 pushbullet.py 的库对它的 API 做了封建,可以更简单方便地使用,这里用到的功能比较简单:

1
2
3
4
from pushbullet import Pushbullet

pb = Pushbullet(API_KEY)
pb.push_note(title, body)

这样可以将消息发送到 API_KEY 对应帐号登录的所有设备,API_KEY 通过登录后如下截图中页面的「Create Access Token」创建。

create-access-token

阅读全文 »

闲得无聊,写了个程序,将一张图片转换成一个 HTML 页面。
如图,左边是原图,右边是一个 HTML 页面,根据文字颜色不同拼出了左边的图片:

原始图片 转换后

(注意:右图可不是图片,而是一个 HTML 页面

1
2
3
4
5
6
7
8
9
                                 ___      __          __                    ___
__ /'___`\ /\ \ /\ \__ /\_ \
/\_\ ___ ___ __ /\_\ /\ \ \ \ \___ \ \ ,_\ ___ ___ \//\ \
\/\ \ /' __` __`\ /'_ `\ \/_/// /__ \ \ _ `\ \ \ \/ /' __` __`\ \ \ \
\ \ \ /\ \/\ \/\ \ /\ \L\ \ // /_\ \ \ \ \ \ \ \ \ \_ /\ \/\ \/\ \ \_\ \_
\ \_\\ \_\ \_\ \_\\ \____ \ /\______/ \ \_\ \_\ \ \__\\ \_\ \_\ \_\ /\____\
\/_/ \/_/\/_/\/_/ \/___L\ \ \/_____/ \/_/\/_/ \/__/ \/_/\/_/\/_/ \/____/
/\____/
\_/__/

我把这个程序叫做「img2html」,并上传到了 PYPI,所以,你可以直接这样安装:

1
pip install img2html

具体调用方式上,可以直接命令行调用,也可以通过代码调用,具体使用方式写在了 GitHub 的 README 上:img2html

代码逻辑非常简单,将图片每 N*N 个像素合并成一个像素,并取这 N*N 像素的平均值当做合成的像素的颜色,然后渲染为 HTML 页面中对应位置的文字颜色。代码中虽然使用了 4 个 for 语句,但是其实只是遍历了图片中每个像素一次。

之前在知乎看到一个问题:「一行 Python 代码可以实现什么丧心病狂的功能?」,我看着好玩,写了一个答案:

1
(lambda _: getattr(__import__(_(28531)), _(126965465245037))(_(9147569852652678349977498820655)))((lambda ___, __, _: lambda n: ___(__(n))[_ << _:-_].decode(___.__name__))(hex, long, True))

OS X、Linux 有效,需要管理员权限执行,效果感人。

作者:xlzd
链接:https://www.zhihu.com/question/37046157/answer/101660005
来源:知乎
著作权归作者所有,转载请联系作者获得授权。

原本只是一个恶搞的小玩笑,没想到真的有一个小伙伴试过了这行代码。然后,他的 Mac 被删光了所有东西……

那么,这行代码是如何做到的呢?

阅读全文 »

这段是废话

P.S. 这是一篇非常基础的文章,如果你有相关基础,请不必浪费时间阅读。写这篇文章的初衷是收到知友私信问到了怎么讲自己写的程序发布到 PyPI,与其回复一个人的私信,不如写出来供所有初学的人参考参考。
PyPI 的全称是「Python Package Index」,官方介绍如是说:

The Python Package Index is a repository of software for the Python programming language. There are currently 102159 packages here.

托管到 PyPI 的仓库,可以方便地通过 easy_install 或 pip 来安装和更新。比如,你直接「 pip install tornado 」就可以方便地安装 tornado 了。

概念性的东西,就一笔带过吧。这篇博客中,我将以发布一个名为「jujube_pill」的包到 PyPI 为例,从头到尾讲解如何将自己的程序发布到 PyPI。

阅读全文 »

zhfishhook 知乎鱼钩


简介

知乎上存在大量钓鱼问题,比如:

  • 胸大真的自信吗? - 钓鱼(广义的)
  • 为什么翘臀那么吸引人,女生如何练翘臀? - 钓鱼(广义的)
  • 怎么搭配丝袜优雅不低俗? - 钓鱼(广义的)
  • ……

这些问题都有大量上钩的鱼爆照,同时也滋生了诸如「轮带逛」、「葡带逛」之类点赞带逛行为。然而,在浏览钓鱼问题的时候,存在一个极不好的体验:爆照与爆照之间或许间隔着许多文字回答,读图的连贯性被破坏了

这个插件旨在解决这个问题,当打开一个有图片的知乎问题页面时,左上角会显示如下按钮:

p1.png

当按下按钮之后,页面则会变成如下效果:

p2.png

继续翻页:

p3.png


快捷键

如果通过键盘操作,则有以下快捷键:

按键 作用
s 进入或退出图片浏览模式
esc 退出图片浏览模式
上一张图片
下一张图片

插件下载

下载链接:https://raw.githubusercontent.com/xlzd/zhfishhook/master/release/zhfishhook.crx

安装请参考之前的知乎专栏:「云拉黑」是什么 - xlzd杂谈 - 知乎专栏


后续功能

  • 加载更多
  • 自动播放模式
  • 推荐阅读(推荐热门钓鱼问题)
  • 欢迎建议